基于STL通用Apriori算法的實(shí)現(xiàn)與應(yīng)用

王鋒

(中國(guó)藥科大學(xué)信息管理教研室，江蘇南京211169)

1.引言

為了提高學(xué)校的教學(xué)質(zhì)量，加快高校教學(xué)改革的步伐，現(xiàn)在許多高校每學(xué)期都組織學(xué)生對(duì)任課教師評(píng)分，已經(jīng)積累了大量數(shù)據(jù)。從這些大量數(shù)據(jù)中發(fā)現(xiàn)規(guī)律，分析學(xué)生喜歡什么樣的教師，什么樣的學(xué)生對(duì)老師打分高，教師評(píng)價(jià)得分與所授學(xué)生成績(jī)有什么關(guān)系，等等。

找出數(shù)據(jù)中隱藏的知識(shí)后，將可以為我校的教師所用，幫助他們改變教學(xué)方式，提高教學(xué)效果，也可為行政部門所用，幫助他們決策。

基于上述原因，筆者將數(shù)據(jù)挖掘技術(shù)引入教學(xué)評(píng)估領(lǐng)域。該挖掘平臺(tái)是一個(gè)通用的用于關(guān)聯(lián)規(guī)則挖掘的軟件，不僅僅可以用于教學(xué)評(píng)價(jià)中，而且可以用于其它行業(yè)中。利用C++Builder開發(fā)完成了一個(gè)通用的用于關(guān)聯(lián)規(guī)則挖掘的類CSTLApriori，利用這個(gè)類，可以對(duì)Access中的數(shù)據(jù)表直接進(jìn)行多字段(維度)的數(shù)據(jù)挖掘。

2.基本定義與定理

關(guān)聯(lián)規(guī)則[1]是由R.Agrawal于1993年提出的，設(shè)I={i1，i2，…，im}是一組物品（項(xiàng)目）集，D是一組事務(wù)集（稱之為事務(wù)數(shù)據(jù)庫(kù)），D中的每個(gè)事務(wù)T是一組物品（項(xiàng)目），顯然滿足T?I。

定義1稱事務(wù)T支持物品（項(xiàng)目）集X，如果X?T。

定義2稱項(xiàng)目集X具有大小為s%的支持度，如果D中有s%的事務(wù)支持項(xiàng)目集X，記為sup(X)。

定義3支持度不小于用戶定義的最小支持度m in_sup的項(xiàng)目集稱為頻繁項(xiàng)目集(或稱頻繁集)，反之，則稱為非頻繁項(xiàng)目集，項(xiàng)目集中項(xiàng)目的數(shù)量叫做項(xiàng)目集的維數(shù)或長(zhǎng)度。

定義4關(guān)聯(lián)規(guī)則是如下形式的一種蘊(yùn)含：X→Y，其中，X?I，Y?I，且X∩Y=φ。

定義5稱關(guān)聯(lián)規(guī)則X→Y在事務(wù)數(shù)據(jù)庫(kù)D中有大小為s%的支持度，如果項(xiàng)目集（X∪Y）的支持度為s%，即support(X→Y)=P(X∪Y)。

定義6稱規(guī)則X→Y在事務(wù)數(shù)據(jù)庫(kù)D中有大小為c%的可信度，如果D中支持項(xiàng)目集X的事務(wù)中有c%的事務(wù)同時(shí)也支持項(xiàng)目集Y，即confidence(X→Y)=P(X∪Y)/P(X)

定義7設(shè)由頻繁集構(gòu)成的集合為S，S的否定邊界，記作Bd-（S）。

Bd(S)={X∣X?S，|x|=1}∪{X|?Y?X，Y∈S，且X?S}也就是說(shuō)，所有不是頻繁集的單個(gè)元素，以及所有本身不是頻繁集，但其子集均是頻繁集的項(xiàng)目集所組成的集合構(gòu)成了S的否定邊界。

定理1：頻繁集的子集一定是頻繁集。

定理2：非頻繁集的父集一定也是非頻繁集。

3.關(guān)聯(lián)規(guī)則的經(jīng)典算法Apriori的性質(zhì)

頻繁項(xiàng)集的所有非空子集都必須也是頻繁的，根據(jù)這個(gè)性質(zhì)，我們分析如何由LK－1推出LK。算法分兩步完成(apriori-gen由Join和Prune完成)[1]。

(1)連接步

為了找LK，通過(guò)LK－1與自己連接產(chǎn)生候選K項(xiàng)集，該候選項(xiàng)集記為CK。

設(shè)L1和L2是LK－1中的項(xiàng)集，記號(hào)Li[j]表示Li的第j項(xiàng)。如果L1[1]=L2[1]∧……∧L1[k-2]=L2[k-2]∧L1[k-1]＜L2[k-1]，則LK－1∞LK－1，連接條件是兩個(gè)項(xiàng)的前k-2項(xiàng)相同，連接結(jié)果為：L1[1]L1[2]……L1[k-1]L2[k-1]。

(2)剪枝步

聯(lián)結(jié)之后的結(jié)果CK是LK的超集，它的成員可能是不頻繁的，這時(shí)就要從掃描數(shù)據(jù)庫(kù)確定CK中每個(gè)候選的計(jì)數(shù)，從而確定LK。

確定LK可用Apriori性質(zhì)對(duì)CK進(jìn)行剪枝，把子集不在LK－1中的候選K項(xiàng)從CK中刪除。

4.Apriori算法在教學(xué)評(píng)價(jià)中的應(yīng)用

4.1 數(shù)據(jù)準(zhǔn)備

筆者就我校實(shí)際情況，采用ASP技術(shù)和SQL Server數(shù)據(jù)庫(kù)開發(fā)研制了一套開放性好、具有身份識(shí)別功能、能快速準(zhǔn)確處理評(píng)價(jià)數(shù)據(jù)和計(jì)算評(píng)價(jià)結(jié)果的教學(xué)評(píng)估系統(tǒng)。

本階段目標(biāo)是準(zhǔn)確及時(shí)地完成系統(tǒng)進(jìn)行評(píng)價(jià)所必須的各項(xiàng)數(shù)據(jù)的收集、核對(duì)、修改等操作。特別是有些數(shù)據(jù)信息在進(jìn)行評(píng)價(jià)數(shù)據(jù)采集時(shí)是不必要的，但是在數(shù)據(jù)挖掘分析時(shí)卻十分重要。例如：系統(tǒng)在進(jìn)行數(shù)據(jù)挖掘分析時(shí)，需要分析教師的教學(xué)效果同教師的年齡、學(xué)歷、職稱等是否相關(guān)，這就要求系統(tǒng)有完整的參評(píng)教師檔案數(shù)據(jù)[2]，而在評(píng)價(jià)信息采集時(shí)，并不需要教師的以上信息。

本階段主要任務(wù)是對(duì)不同數(shù)據(jù)源數(shù)據(jù)的正確集成。本次數(shù)據(jù)挖掘需要四方面的數(shù)據(jù)：教學(xué)評(píng)價(jià)系統(tǒng)中教師得分?jǐn)?shù)據(jù)、學(xué)生成績(jī)數(shù)據(jù)、教師基本情況數(shù)據(jù)和學(xué)生基本情況數(shù)據(jù)。這些數(shù)據(jù)都存在于不同的應(yīng)用系統(tǒng)中，本過(guò)程需要將這些來(lái)自不同系統(tǒng)的數(shù)據(jù)源集成到本系統(tǒng)的操作數(shù)據(jù)庫(kù)中。

4.2 數(shù)據(jù)清理

數(shù)據(jù)清理的主要工作就是填補(bǔ)記錄中遺漏的數(shù)據(jù)值。

在以上四種數(shù)據(jù)中有一些我們感興趣的屬性缺少值，對(duì)于這些空缺的屬性值可以使用數(shù)據(jù)清理技術(shù)來(lái)填補(bǔ)。

有很多種方法可以為屬性填寫空缺值：

(l)忽略元組：當(dāng)元組中有多個(gè)屬性缺少值時(shí)通常這樣做。

(2)人工填寫空缺值：一般地說(shuō)，該方法很費(fèi)時(shí)，并且當(dāng)數(shù)據(jù)集很大、缺少很多值時(shí)，該方法可能行不通。

(3)使用一個(gè)全局常量填充空缺值：將空缺的屬性值用同一個(gè)常數(shù)(如"Unknown")替換。

(4)使用屬性的平均值填充空缺值。

(5)使用與給定元組屬同一類的所有樣本的平均值。

(6)使用最可能的值填充空缺值：可以用回歸方法、貝葉斯方法或決策樹歸納確定。

本系統(tǒng)采用忽略元組的方法刪除有大量空缺屬性的記錄。由于本系統(tǒng)數(shù)據(jù)量巨大，所以對(duì)挖掘結(jié)果影響較小。

4.3 數(shù)據(jù)的表述方式進(jìn)行轉(zhuǎn)換

由于學(xué)生成績(jī)數(shù)據(jù)以及教師得分?jǐn)?shù)據(jù)是連續(xù)型數(shù)據(jù)，算法不好處理，需要進(jìn)行離散化[4]。

離散化技術(shù)方法可以通過(guò)劃分區(qū)間來(lái)減少一個(gè)連續(xù)(取值)屬性的取值個(gè)數(shù)。可以用一個(gè)標(biāo)號(hào)來(lái)代替一個(gè)區(qū)間內(nèi)的實(shí)際數(shù)據(jù)值。現(xiàn)實(shí)生活中的有些數(shù)據(jù)是連續(xù)型的，而許多知識(shí)發(fā)現(xiàn)算法對(duì)于連續(xù)的取值無(wú)法處理。況且連續(xù)的取值是沒(méi)有必要的，例如某學(xué)生“成績(jī)?yōu)?3”與“成績(jī)?yōu)?4”在一般情況下沒(méi)有必要加以區(qū)分，可以近似地視為同一值“中”。雖然在數(shù)據(jù)離散化過(guò)程中忽略了一些細(xì)節(jié)，但這樣所獲得的離散化數(shù)據(jù)會(huì)更易于理解、效率更高。

4.4 用STL存儲(chǔ)項(xiàng)集

在本算法中，用何種存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)各種項(xiàng)集是一個(gè)技術(shù)難點(diǎn)。

本人在對(duì)程序的數(shù)據(jù)結(jié)構(gòu)定義和算法實(shí)現(xiàn)的時(shí)候大量采用了C++的標(biāo)準(zhǔn)模板庫(kù)(STL，Standard Template Library)，比較好地解決這個(gè)問(wèn)題。

STL是一些“容器”的集合，這些“容器”有l(wèi)ist，vector，set，map等，如圖1，STL也是算法和其它一些組件的集合。

STL中的種種數(shù)據(jù)結(jié)構(gòu)和算法都是專家精心編寫的，對(duì)同一問(wèn)題的實(shí)現(xiàn)一般是比較經(jīng)典的，不僅在速度上有優(yōu)勢(shì)，而且還避免了許多低層次上的內(nèi)存泄漏問(wèn)題。

關(guān)聯(lián)規(guī)則所涉及到的數(shù)據(jù)結(jié)構(gòu)和基本算法都是以往的常用數(shù)據(jù)結(jié)構(gòu)和算法，如向量類、集合類、快速排序算法等，而STL正是包含了這樣許多通用的數(shù)據(jù)結(jié)構(gòu)和基本算法的庫(kù)。

圖1 STL常用容器

關(guān)聯(lián)規(guī)則所涉及到的數(shù)據(jù)結(jié)構(gòu)和基本算法都是以往的常用數(shù)據(jù)結(jié)構(gòu)和算法，如向量類、集合類、快速排序算法等，而STL正是包含了這樣許多通用的數(shù)據(jù)結(jié)構(gòu)和基本算法的庫(kù)。

以存儲(chǔ)項(xiàng)集(包含候選項(xiàng)集，頻繁項(xiàng)集)的數(shù)據(jù)結(jié)構(gòu)為例，其包含兩部分：

(1)以字符串形式保存的項(xiàng)的集合；

(2)項(xiàng)集的支持計(jì)數(shù)。

實(shí)現(xiàn)這種存儲(chǔ)結(jié)構(gòu)，傳統(tǒng)的辦法是結(jié)構(gòu)體鏈表。首先，聲明一個(gè)結(jié)構(gòu)體：

然后，用這個(gè)結(jié)構(gòu)體的鏈表link存儲(chǔ)項(xiàng)集。

本文的方法是采用STL中的map＜string，int＞，前者為字符串形式保存的項(xiàng)的集合，后者支持計(jì)數(shù)。

在候選項(xiàng)集的剪枝和規(guī)則生成時(shí)，程序需要頻繁地在map或者鏈表link中查找指定項(xiàng)集，后者采用折半查找，對(duì)應(yīng)的時(shí)間復(fù)雜度為log(n)，前者只能順序查找，時(shí)間復(fù)雜度為n/2。當(dāng)對(duì)大數(shù)據(jù)量進(jìn)行挖掘時(shí)，后者的效率優(yōu)勢(shì)很明顯；其次，STL的map提供了find()函數(shù)，用于根據(jù)key進(jìn)行查找，而對(duì)鏈表link的查找只能手工編程實(shí)現(xiàn)，不如后者易于實(shí)現(xiàn)。

另外，STL實(shí)際是一種宏，但比宏安全可靠的多。它在編譯期間就被處理了，因此根本不會(huì)影響程序的執(zhí)行速度。

4.5 通用關(guān)聯(lián)規(guī)則挖掘的類的定義

本人利用C++Builder開發(fā)完成了一個(gè)通用的用于關(guān)聯(lián)規(guī)則挖掘的類CSTLApriori，利用這個(gè)類，可以對(duì)access中的數(shù)據(jù)表直接進(jìn)行多字段(維度)的關(guān)聯(lián)挖掘。

下面是類中數(shù)據(jù)成員及成員函數(shù)的說(shuō)明：

4.6 程序主體

CSTLAprior類可以提供給用戶使用，用戶只需知道該類主要函數(shù)的功能，直接調(diào)用即可。

4.7 結(jié)果

運(yùn)行挖掘程序后，通過(guò)選擇不同字段進(jìn)行挖掘，得出一系列有意義的規(guī)則，如下：

(1)挖掘?qū)W生成績(jī)與教師得分的內(nèi)在關(guān)系

ID規(guī)則條件規(guī)則結(jié)論支持度可信度提升度1學(xué)生成績(jī)：良教師得分：優(yōu)0.19 0.41 2.13 2學(xué)生成績(jī)：優(yōu)教師得分：優(yōu)0.12 0.37 2.89

(2)挖掘職稱與教師得分的內(nèi)在關(guān)系

ID規(guī)則條件規(guī)則結(jié)論支持度可信度提升度489職稱：副教授教師得分：優(yōu)上0.12 0.53 4.22 493職稱：講師教師得分：優(yōu)上0.18 0.48 2.60 499職稱：助教教師得分：優(yōu)上0.18 0.51 3.81

(3)挖掘?qū)W位與教師得分的內(nèi)在關(guān)系

ID規(guī)則條件規(guī)則結(jié)論支持度可信度提升度17最高學(xué)位：博士教師得分：優(yōu)上0.11 0.55 4.65 18最高學(xué)位：碩士教師得分：優(yōu)上0.27 0.50 2.60

(4)挖掘?qū)W生性別與教師得分的內(nèi)在關(guān)系

ID規(guī)則條件規(guī)則結(jié)論支持度可信度提升度324學(xué)生性別：男教師得分：優(yōu)上0.20 0.52 2.52 367學(xué)生性別：女教師得分：優(yōu)上0.30 0.50 1.65

4.8 模式理解和評(píng)估

以下對(duì)以上產(chǎn)生的4條規(guī)則進(jìn)行解讀：

(1)可看出第一條可信度要高出第二條，也就是說(shuō)，在給教師打分為優(yōu)的同學(xué)中，成績(jī)?yōu)榱嫉谋瘸煽?jī)?yōu)閮?yōu)的比例要高。這也反映了成績(jī)優(yōu)秀的同學(xué)對(duì)老師的要求比成績(jī)良好的同學(xué)要高些。

(2)可看出第一條可信度要明顯高于第二條，并高于第三條。也就是說(shuō)，教師得分為優(yōu)的副教授比例要明顯高于講師，也高于助教。這說(shuō)明副教授最受學(xué)生歡迎，其次是助教。這結(jié)論有點(diǎn)背離許多人的常識(shí)，但也說(shuō)明了一個(gè)問(wèn)題：助教年輕有朝氣，而且對(duì)待工作的態(tài)度比講師更為積極，與學(xué)生更融洽。而講師這個(gè)階段可能由于家庭的負(fù)擔(dān)較重，在教學(xué)工作中投入的精力比助教這個(gè)階段要少。

(3)可看出第一條可信度要明顯高于第二條。博士學(xué)位的教師科研水平較高，有寬廣的知識(shí)面，教學(xué)中經(jīng)常鼓勵(lì)學(xué)生刻苦鉆研，向?qū)W生介紹學(xué)科的學(xué)術(shù)動(dòng)態(tài)，指導(dǎo)學(xué)生進(jìn)行科學(xué)研究。把教學(xué)與科研有機(jī)地結(jié)合起來(lái)，促進(jìn)學(xué)生科研能力的增長(zhǎng)，深受學(xué)生歡迎。

(4)可看出第一條可信度要高于第二條。說(shuō)明女生對(duì)待評(píng)教態(tài)度更嚴(yán)肅，男生顯得"大大咧咧"，這與常識(shí)相符。

5.結(jié)束語(yǔ)

本文的創(chuàng)新點(diǎn)在于將STL運(yùn)用于Apriori算法的各種項(xiàng)集中，提高了程序的運(yùn)行效率，并將核心算法封裝成類，其它領(lǐng)域用戶只需知道各函數(shù)的功能，即可很方便地使用。

本算法也成功應(yīng)用到高校的評(píng)教系統(tǒng)中，比較客觀地反映教師教學(xué)中存在的問(wèn)題，促進(jìn)教師隊(duì)伍的進(jìn)一步改革、發(fā)展和完善，而且還能為領(lǐng)導(dǎo)的宏觀決策提供有效的依據(jù)。

[1] Jiawei Han，Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰等譯.北京：機(jī)械工業(yè)出版社，2003.

[2] 董彩云，曲守寧.數(shù)據(jù)挖掘及其在高校教學(xué)系統(tǒng)中的應(yīng)用[J].濟(jì)南大學(xué)學(xué)報(bào)，2004，18(1)：65-68.

[3] 張彥釗等.關(guān)聯(lián)規(guī)則在教學(xué)評(píng)價(jià)數(shù)據(jù)分析中的應(yīng)用[J].微計(jì)算機(jī)應(yīng)用，2005，(26).

[4] 王婷婷.關(guān)聯(lián)規(guī)則在教學(xué)評(píng)價(jià)中的應(yīng)用[J].中國(guó)科教創(chuàng)新導(dǎo)刊，2008，(23).