汪 麗，張 露

(1.武漢理工大學(xué)統(tǒng)戰(zhàn)部，湖北 武漢 430070;2.武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430070)

隨著網(wǎng)絡(luò)和計(jì)算機(jī)技術(shù)的快速發(fā)展，信息也在爆炸式地增長并呈現(xiàn)出海量、多樣、異構(gòu)、動態(tài)變化等特性[1]。分布式計(jì)算平臺的出現(xiàn)解決了海量數(shù)據(jù)的存儲和計(jì)算的瓶頸問題，使海量數(shù)據(jù)的數(shù)據(jù)挖掘成為可能。將分布式與現(xiàn)有數(shù)據(jù)挖掘算法相結(jié)合，已成為研究的熱點(diǎn)[2]。

而隨著信息化建設(shè)的深入發(fā)展，高校都擁有大量的教育信息，其分布范圍在地理上越來越廣泛，數(shù)據(jù)結(jié)構(gòu)呈現(xiàn)多樣化的趨勢，使傳統(tǒng)的數(shù)據(jù)挖掘也不再適用[3]。針對Apriori算法進(jìn)行改進(jìn)，提出了一種分布式的關(guān)聯(lián)數(shù)據(jù)挖掘算法，利用MapReduce模型對算法進(jìn)行實(shí)現(xiàn)，并將改進(jìn)的關(guān)聯(lián)規(guī)則算法應(yīng)用于分布式教育決策支持系統(tǒng)中。

1 關(guān)聯(lián)規(guī)則挖掘算法及其分布式改進(jìn)

1.1 關(guān)聯(lián)規(guī)則挖掘算法

從廣義上講，數(shù)據(jù)挖掘的本質(zhì)即關(guān)聯(lián)分析。數(shù)據(jù)挖掘的目的是挖掘出潛藏在大量數(shù)據(jù)背后的有用知識，這種知識所反映的必然是不同對象不同屬性之間的關(guān)聯(lián)[4－5]。

在眾多的關(guān)聯(lián)規(guī)則算法中，最著名的是1993年AGRAWAL等提出的Apriori算法及其改進(jìn)算法[6－7]。盡管后來又有科研工作者提出了許多關(guān)聯(lián)規(guī)則挖掘算法，但Apriori算法仍是許多新算法的原型，很多算法都是基于Apriori算法的改進(jìn)。

可將Apriori算法描述如下:

輸入為事務(wù)數(shù)據(jù)庫D;最小支持度閾值Smin。

輸出為D中的頻繁項(xiàng)集L。

步驟為:①根據(jù)原事務(wù)集產(chǎn)生頻繁1項(xiàng)集L1;②根據(jù)頻繁k項(xiàng)集產(chǎn)生第k+1層候選集;③掃描事務(wù)集，找出第k+1層頻繁集;④循環(huán)步驟②和步驟③，直到第k+1層頻繁集為空。

Apriori算法的優(yōu)點(diǎn)是結(jié)構(gòu)簡單，易于理解，沒有復(fù)雜的推導(dǎo)。但同時該算法也存在兩個主要缺點(diǎn):①多次重復(fù)掃描數(shù)據(jù)庫和產(chǎn)生大量候選頻繁項(xiàng)集。在實(shí)際應(yīng)用中，多次重復(fù)掃描數(shù)據(jù)庫在需要挖掘很長的模式時將帶來巨大開銷;②在迭代過程中要在內(nèi)存中產(chǎn)生、處理和保存候選頻繁項(xiàng)集，這個數(shù)量有時候是非常大的，會導(dǎo)致算法在廣度和深度上的適應(yīng)性很差。

1.2 分布式Apriori算法設(shè)計(jì)

MapReduce模型是Google開發(fā)的一個針對大規(guī)模群組海量數(shù)據(jù)處理的分布式編程模型，它將運(yùn)行于大規(guī)模集群上復(fù)雜的并行計(jì)算過程高度地抽象成兩個函數(shù):Map和Reduce[8]。在實(shí)現(xiàn)上將并行化、容錯、數(shù)據(jù)分布和負(fù)載均衡等細(xì)節(jié)隱藏起來，然后把整個分布式過程看作由Map/Reduce來表達(dá)的一個類函數(shù)過程。Map階段，Map/Re－duce模型將輸入的數(shù)據(jù)集合拆分為若干數(shù)據(jù)片段，并將每一個數(shù)據(jù)片段對應(yīng)分配給一個Map任務(wù)，每一個Map任務(wù)對應(yīng)分配給集群中運(yùn)行的某一個塊服務(wù)器。每一個Map任務(wù)對其分配到的鍵/值對(K，V)調(diào)用用戶自定義的Map函數(shù)進(jìn)行計(jì)算后，生成相應(yīng)的中間結(jié)果鍵/值對集合M{(K1，V1)，(K2，V2)，…，(Ki，Vi)}。Map/Reduce模型會將中間結(jié)果鍵/值對集合M{(K1，V1)，(K2，V2)，…，(Ki，Vi)}進(jìn)行排序產(chǎn)生一個新的二元組(K'，V'*)集合，新集合中所有對應(yīng)鍵的相同值被歸類在一起，同時二元組集合也會被劃分出與Reduce任務(wù)數(shù)量相同的片段數(shù)。Reduce階段，二元組(K'，V'*)集合的片段將作為每一個Reduce任務(wù)的輸入，經(jīng)過一個用戶定義的Reduce函數(shù)處理后生成一個輸出的鍵/值對(K，V)。Map/Reduce框架最后會再一次將集群中所有節(jié)點(diǎn)上的Reduce任務(wù)生成結(jié)果進(jìn)行分發(fā)處理，形成最終輸出結(jié)果集合。

將原Apriori算法轉(zhuǎn)換為MapReduce實(shí)現(xiàn)，其重點(diǎn)就是找出原方法中的關(guān)鍵數(shù)據(jù)，將這些數(shù)據(jù)映射為MapReduce的key值和value值。Apriori算法在事務(wù)集掃描的過程中，其本質(zhì)是詞語計(jì)數(shù)的過程，核心是對項(xiàng)集進(jìn)行統(tǒng)計(jì)，故選取項(xiàng)集作為該階段的key值，value為1，則把事務(wù)數(shù)據(jù)庫水平均勻地分成規(guī)模相當(dāng)?shù)膎個數(shù)據(jù)子集，對n個數(shù)據(jù)子集進(jìn)行格式化，格式化后的記錄集為＜tid1，list1＞，＜ tid2，list2＞，…，＜ tidn，listn＞，產(chǎn)生＜key1，value1＞對，Map函數(shù)對輸入的數(shù)據(jù)子集的每個記錄＜tidi，listi＞進(jìn)行掃描，產(chǎn)生一個局部候選項(xiàng)集的集合C，生成并輸出中間＜key2，value2＞對，每個候選項(xiàng)集的 value為1，故集合C記作{ ＜itemset1，1 ＞，＜ itemset2，1＞，…，＜ itemsetn，1 ＞}。

當(dāng)數(shù)據(jù)庫很大，劃分后的每個數(shù)據(jù)子集中事務(wù)對應(yīng)的列表相近時，Map函數(shù)產(chǎn)生的中間key2值的數(shù)據(jù)大量重復(fù)，如果將這些數(shù)據(jù)通過網(wǎng)絡(luò)發(fā)送到指定的Reduce函數(shù)，將會耗費(fèi)網(wǎng)絡(luò)資源，增加延遲，降低I/O性能，可以在Map階段增加一個Combine類調(diào)用的Combine()函數(shù)，這樣映射過程所產(chǎn)生的中間結(jié)果鍵/值對，不會馬上寫到輸出，而會被收集到列表中，每個鍵/值對對應(yīng)一個列表，當(dāng)緩沖區(qū)內(nèi)的鍵/值對達(dá)到一定數(shù)量時，緩沖區(qū)內(nèi)數(shù)據(jù)會被清空轉(zhuǎn)移到Combine類的Reduce方法中，最后每個鍵與對應(yīng)的值列表以鍵/值對的形式映射輸出。以Map階段所產(chǎn)生的＜key2，value2＞對作為輸入，將Map函數(shù)輸出進(jìn)行一次合并，得到的新 ＜key2，value2＞為 ＜itemseti，S＞，其中 S表示itemseti在數(shù)據(jù)子集中的支持度計(jì)數(shù)，然后利用分區(qū)公式(1)，將Combine()函數(shù)產(chǎn)生的中間鍵/值對分成m個不同的分區(qū)，將每個分區(qū)分配給指定的Reduce函數(shù)。

其中:key為中間鍵值;M為分區(qū)數(shù)目;參數(shù)m1，m2，…，mn為 n項(xiàng)集中的項(xiàng)在事務(wù)數(shù)據(jù)庫的項(xiàng)集中的序數(shù)，默認(rèn)為按照字典順序排序的。

執(zhí)行Reduce函數(shù)的節(jié)點(diǎn)讀取Combine()函數(shù)提交的數(shù)據(jù) ＜itemseti，Si＞，同一個 Reduce函數(shù)會映射很多不同的候選項(xiàng)集，對itemsetikey值進(jìn)行排序，將具有相同候選項(xiàng)集的數(shù)據(jù)聚合在一起，形成＜itemseti，list(Si)＞，遍歷所有中間數(shù)據(jù)后，將 ＜itemseti，list(Si)＞傳遞給 Reduce函數(shù)。Reduce函數(shù)把相同itemseti的支持度進(jìn)行累加，就得到該候選項(xiàng)集在整個事務(wù)數(shù)據(jù)庫中的實(shí)際支持度計(jì)數(shù)，即S=S1+S2+…，與最小支持度計(jì)數(shù)Smin相比較，確定局部頻繁項(xiàng)集的集合L'，比較之后的m個Reduce函數(shù)的輸出項(xiàng)集合并就得到最終的頻繁項(xiàng)集的集合L。

與原算法相比，改進(jìn)的Apriori算法的優(yōu)點(diǎn)在于只需要對整個數(shù)據(jù)庫掃描一次，即可得到所有頻繁項(xiàng)集的集合，可極大地提高算法的執(zhí)行效率。

2 算法的仿真實(shí)驗(yàn)與分析

選擇10臺硬件配置不完全相同的PC機(jī)，使用一臺服務(wù)器作為NameNode，設(shè)定為JobTracker角色，其他 9臺 PC機(jī)作為 DataNode，即 Task－Tracker，實(shí)驗(yàn)環(huán)境架構(gòu)如圖1所示。

圖1 實(shí)驗(yàn)環(huán)境架構(gòu)圖

運(yùn)行MapReduce模型，由Master控制整個運(yùn)行環(huán)境的進(jìn)程調(diào)度和資源調(diào)度，將作業(yè)分配給多個相互獨(dú)立的處理器進(jìn)行處理，每個處理器處理數(shù)據(jù)的過程都是一樣的。在算法運(yùn)行的同時創(chuàng)建Map任務(wù)子進(jìn)程和Reduce任務(wù)子進(jìn)程，Map任務(wù)子進(jìn)程喚醒Mapper對輸入數(shù)據(jù)進(jìn)行處理并喚醒Combine()函數(shù)來合成Map函數(shù)處理后的數(shù)據(jù)集，Reduce任務(wù)子進(jìn)程喚醒 Reducer來執(zhí)行Reduce操作。

實(shí)驗(yàn)數(shù)據(jù)采用IBM的奎斯特合成數(shù)據(jù)產(chǎn)生器產(chǎn)生關(guān)聯(lián)規(guī)則挖掘?qū)ο髮?shí)驗(yàn)數(shù)據(jù)，實(shí)驗(yàn)使用的數(shù)據(jù)庫設(shè)為T30.I10.N200K.D200K，其中T30表示每個事務(wù)平均包含30項(xiàng)，I10表示頻繁項(xiàng)集的平均長度為10，N200K表示項(xiàng)總數(shù)為200 000，D200K表示事務(wù)總數(shù)為200 000。

不同節(jié)點(diǎn)數(shù)目下，Apriori算法和改進(jìn)的Apriori算法執(zhí)行時間對比如圖2所示。從圖2中可以看出，當(dāng)只有一個可利用節(jié)點(diǎn)時，兩種算法的時間性能基本一樣，但隨著節(jié)點(diǎn)數(shù)目的增多，改進(jìn)算法比原算法執(zhí)行時間要短，并且這種優(yōu)勢隨著節(jié)點(diǎn)數(shù)目的增加而擴(kuò)大，說明在異構(gòu)集群環(huán)境下，MapReduce模型的Apriori算法能夠提高關(guān)聯(lián)規(guī)則挖掘的執(zhí)行效率。

圖2 兩種Apriori算法時間性能對比圖

3 在教育決策支持系統(tǒng)中的應(yīng)用

建立先進(jìn)的教育評估系統(tǒng)，對發(fā)展教育，保障培養(yǎng)質(zhì)量尤為重要[9]。隨著評估工作的不斷深入，目標(biāo)越來越復(fù)雜，數(shù)據(jù)量越來越多，分布的范圍也越來越廣泛，數(shù)據(jù)結(jié)構(gòu)呈現(xiàn)出多樣化的趨勢，因此研究基于分布式的關(guān)聯(lián)數(shù)據(jù)挖掘算法在教育決策支持系統(tǒng)開發(fā)中的應(yīng)用是一個很好的嘗試。

從教學(xué)質(zhì)量評價系統(tǒng)數(shù)據(jù)庫中抽取基本表，如總體評價結(jié)果表、教師表、系所表;從師資管理系統(tǒng)數(shù)據(jù)庫中抽取基本表，如教師表、職稱代碼表、系所表。

在教學(xué)質(zhì)量評價系統(tǒng)和師資管理系統(tǒng)中均有對教師基本數(shù)據(jù)的定義，要將兩個表的數(shù)據(jù)進(jìn)行數(shù)據(jù)集成，集成后的表結(jié)構(gòu)為教師表(教師號，教師名，性別，年齡，系所名，職稱，學(xué)歷)。根據(jù)學(xué)生對教師評教的數(shù)據(jù)，還需要從教師檔案中獲取相關(guān)教師的其他屬性，在進(jìn)行評價處理之前需要去掉一些孤立點(diǎn)數(shù)據(jù)，得到教學(xué)評價信息表(教師號，教師名，性別，年齡，系所名，職稱，學(xué)歷，評價分?jǐn)?shù))。

記錄中的字段值采用代碼表，如表1所示，并將其轉(zhuǎn)換為相應(yīng)的事務(wù)。

表1 代碼表

使用所述的改進(jìn)算法進(jìn)行關(guān)聯(lián)規(guī)則挖掘需要兩個參數(shù):支持度和置信度，支持度是規(guī)則X－Y在交易數(shù)據(jù)庫中包含X和Y的交易數(shù)與所有交易數(shù)之比，置信度是包含X和Y的交易數(shù)與包含X的交易數(shù)之比，通過挖掘一共產(chǎn)生了30條關(guān)聯(lián)規(guī)則，其中部分關(guān)聯(lián)規(guī)則如表2所示。

第一條規(guī)則C3≥D2轉(zhuǎn)換為職稱=副教授≥學(xué)歷=碩士，支持度22.3%表明，在教師檔案數(shù)據(jù)庫有22.3%的記錄是職稱為副教授且學(xué)歷為碩士;而置信度71.7%表明，71.7%的副教授具有碩士學(xué)位，其余規(guī)則與此類似。

表2 部分關(guān)聯(lián)規(guī)則表

從以上的關(guān)聯(lián)規(guī)則可以得出:相關(guān)影響因素主要是學(xué)歷、年齡和職稱。職稱是副高以上或中青年或?qū)W歷碩士以上的教師其教學(xué)效果為優(yōu)秀的可能性較大。年齡在30～50歲之間的中青年教師評價分?jǐn)?shù)較高且支持度、置信度也較高，說明該高校實(shí)行的加強(qiáng)中青年教師培養(yǎng)和高層次人才引進(jìn)的人才戰(zhàn)略已初步取得成效，學(xué)校整體的師資結(jié)構(gòu)更加合理。在教育決策支持系統(tǒng)的數(shù)據(jù)庫中選擇一組事務(wù)集，大小分別為30 kB，60 kB，120 kB，240 kB，300 kB，360 kB，400 kB 且分布在不同的主機(jī)中，使原算法和改進(jìn)算法挖掘同樣大小的事務(wù)集，記錄運(yùn)行時間，如圖3所示。

圖3 兩種Apriori算法在實(shí)例中運(yùn)行時間對比圖

由圖3可知，兩種算法的運(yùn)行時間都隨著事務(wù)集增大而變長，但改進(jìn)算法的運(yùn)行時間要短于原算法，且隨著事務(wù)集大小的增加，這種優(yōu)勢更加明顯，說明改進(jìn)的分布式數(shù)據(jù)挖掘算法更適合于數(shù)據(jù)量越來越多、分布范圍在地理上越來越廣泛的分布式教育決策支持系統(tǒng)。

4 結(jié)論

基于MapReduce模型，對Apriori算法進(jìn)行改進(jìn)，提出了一種分布式的關(guān)聯(lián)數(shù)據(jù)挖掘算法，并對算法進(jìn)行了模擬，通過仿真實(shí)驗(yàn)可知，MapReduce模型的Apriori算法在異構(gòu)集群環(huán)境下，能夠提高關(guān)聯(lián)規(guī)則挖掘的執(zhí)行效率，減少算法的執(zhí)行時間。

[1] FU Y J.Distributed data mining:an overview[R].[S.l.]:IEEE TCDP Newsletter，2001.

[2] MARIO C，ANTONIO C，ANDREA P，et al.Distributed data mining on grids:services，tools，and applications[J].IEEE Transactions on Systems，Man，and Cybernetics:Part B，Cybernetics，2004，34(6):2451 －2465.

[3] KULKARNI U P，YARDI A R.Exploring the capabilities of mobile agents in distributed data mining[C]//Proceeding of the Tenth International Database Engineering＆ Applications Symposium.India:[s.n.]，2006:277－280.

[4] MINGSYAN C，JIAWEI H，PHILIP S Y.Data mining:an overview from a database perspective[J].IEEE Transaction on Knowledge and Data Engineering，1996，8(6):866 －883.

[5] MEHHED K.數(shù)據(jù)挖掘:概念、模型、方法和算法[M].閃四清，陳茵，程雁，等，譯.北京:清華大學(xué)出版社，2003:56－121.

[6] AGRAWAL R，TOMASZ I，ARAN S.Mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data.New York:ACM，1993:207－216.

[7] 錢少華，蔡勇，錢雪忠.基于數(shù)組的Apriori算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用與軟件，2006，23(2):111 －113.

[8] DEAN J，GHEMAWAT S.Map reduce:simplified data processing on large clusters[C]//OSDI'04:Sixth Symposium on Operating System Design and Implementation.San Francisco:[s.n.]，2004:107 －113.

[9] 廖文婕.我國專業(yè)學(xué)位研究生培養(yǎng)模式的系統(tǒng)結(jié)構(gòu)研究[D].廣州:華南理工大學(xué)圖書館，2010.