基于分布式數(shù)據(jù)挖掘方法的研究與應用

汪 麗，張 露

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

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

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

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

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算法及其改進算法[6－7]。盡管后來又有科研工作者提出了許多關(guān)聯(lián)規(guī)則挖掘算法，但Apriori算法仍是許多新算法的原型，很多算法都是基于Apriori算法的改進。

可將Apriori算法描述如下:

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

輸出為D中的頻繁項集L。

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

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

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

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

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

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

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

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

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

2 算法的仿真實驗與分析

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

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

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

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

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

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

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

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

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

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

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

表1 代碼表

使用所述的改進算法進行關(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)換為職稱=副教授≥學歷=碩士，支持度22.3%表明，在教師檔案數(shù)據(jù)庫有22.3%的記錄是職稱為副教授且學歷為碩士;而置信度71.7%表明，71.7%的副教授具有碩士學位，其余規(guī)則與此類似。

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

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

圖3 兩種Apriori算法在實例中運行時間對比圖

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

4 結(jié)論

基于MapReduce模型，對Apriori算法進行改進，提出了一種分布式的關(guān)聯(lián)數(shù)據(jù)挖掘算法，并對算法進行了模擬，通過仿真實驗可知，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].閃四清，陳茵，程雁，等，譯.北京:清華大學出版社，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].計算機應用與軟件，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è)學位研究生培養(yǎng)模式的系統(tǒng)結(jié)構(gòu)研究[D].廣州:華南理工大學圖書館，2010.