動車組運維效率關(guān)聯(lián)規(guī)則挖掘優(yōu)化算法

張 春 周 靜

(北京交通大學(xué)計算機(jī)與信息技術(shù)學(xué)院 北京 100044) (高速鐵路網(wǎng)絡(luò)管理教育部工程研究中心(北京交通大學(xué)) 北京 100044)

動車組運維效率關(guān)聯(lián)規(guī)則挖掘優(yōu)化算法

張 春 周 靜

(北京交通大學(xué)計算機(jī)與信息技術(shù)學(xué)院 北京 100044) (高速鐵路網(wǎng)絡(luò)管理教育部工程研究中心(北京交通大學(xué)) 北京 100044)

(chzhang1@bjtu.edu.cn)

隨著動車組運營時間和運營里程的增長，動車組運維系統(tǒng)積累了大量的數(shù)據(jù).利用高效的關(guān)聯(lián)規(guī)則挖掘算法從動車組運維數(shù)據(jù)中快速發(fā)現(xiàn)有用的信息，對于提高動車組關(guān)鍵部件運維效率具有重要意義.針對動車組運維數(shù)據(jù)的數(shù)據(jù)量巨大、價值密度低的特點，設(shè)計一種基于近似最小完美Hash函數(shù)的AMPHP(approximate minimum perfect hashing and pruning)算法，相較于傳統(tǒng)的直接Hash和修剪(direct hashing and pruning, DHP)算法，它可以過濾掉所有的非頻繁項集，無需額外的數(shù)據(jù)庫掃描.為了突破單機(jī)算法的性能限制，借鑒SON算法思想對AMPHP算法進(jìn)行并行化改進(jìn)，提出AMPHP-SON算法，進(jìn)一步提高算法性能.使用實際的動車組牽引電機(jī)運維數(shù)據(jù)進(jìn)行測試分析，實驗結(jié)果表明，AMPHP-SON算法具有很好的時間性能，且挖掘出的規(guī)則可以有效地指導(dǎo)動車組修程修制優(yōu)化，從而達(dá)到提高動車組運維效率的目的.

關(guān)聯(lián)規(guī)則挖掘；DHP算法；近似最小完美Hash函數(shù)；SON算法；動車組

在復(fù)雜的高速鐵路動車組中，對故障部件的維修往往需要多個系統(tǒng)、多個環(huán)節(jié)、多個部門的協(xié)同，不僅涉及故障定位等本身因素，還包括設(shè)備、備品備件、人員、工位、維修計劃等.因此，為了提高故障維修效率，不僅需要各個裝置自身的故障判斷規(guī)則，同時還需要相關(guān)的信息傳遞及相互影響的規(guī)則.而隨著動車組運營時間和運營規(guī)模的增大，動車組運維系統(tǒng)積累了大量的數(shù)據(jù)，如何從這些海量數(shù)據(jù)中快速發(fā)現(xiàn)有用的信息成為亟待解決的問題.對于以上的這些需求，利用關(guān)聯(lián)規(guī)則挖掘(association rule mining)技術(shù)也可以有效地實現(xiàn).

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領(lǐng)域最活躍的研究方法之一，可以用來發(fā)現(xiàn)事情之間的聯(lián)系，在事務(wù)數(shù)據(jù)集中發(fā)現(xiàn)頻繁項集是一個基礎(chǔ)概念.令I(lǐng)={i1,i2,…,im}，其中i1,i2,…,im為m個不同的項(item)；令T={t1,t2,…,tn}是所有事務(wù)的集合，可稱為事務(wù)數(shù)據(jù)集(transaction dataset).包含0個或多個項的集合被稱為項集(itemset),它的一個重要性質(zhì)是支持度計數(shù)(support count)，即包含特定項集的事務(wù)個數(shù).支持度(Support)為包含特定項集的事務(wù)的個數(shù)占整個事務(wù)數(shù)據(jù)集中的比例.滿足最小支持度閾值的所有項集被稱為頻繁項集.

Apriori算法[1]是一種經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法，但會產(chǎn)生大量的候選集且需要重復(fù)掃描數(shù)據(jù)庫，效率低；直接Hash和修剪(direct hashing and pruning, DHP)算法是在Apriori算法的基礎(chǔ)上，利用Hash修剪技術(shù)改進(jìn)的算法，它有效減小了候選集大小，在性能上得到了一定的提高.但在面對大數(shù)據(jù)量的事物數(shù)據(jù)庫時，DHP算法的Hash過濾效果不夠好，且時間開銷也會隨之增大.為了解決上述2個問題，本文提出了相應(yīng)的解決方案：1)基于近似最小完美Hash函數(shù)設(shè)計一種新的近似最小完美Hash和修剪(approximate minimum perfect hashing and pruning, AMPHP)算法，可以百分百地過濾出非頻繁項集，無需額外地掃描數(shù)據(jù)庫；2)基于SON算法的思想，對AMPHP算法進(jìn)行并行化改進(jìn)，提出AMPHP-SON算法，以減少時間開銷.

關(guān)聯(lián)規(guī)則挖掘最早是為了發(fā)現(xiàn)超市交易數(shù)據(jù)庫中不同的商品之間的關(guān)系的，現(xiàn)廣泛應(yīng)用于客戶關(guān)系管理(customer relationship management, CRM)領(lǐng)域[2].而利用快速、高效的數(shù)據(jù)挖掘算法從動車組的運維數(shù)據(jù)中挖掘出有效的信息，對于提高動車組運維效率具有重要的意義.因此本文將改進(jìn)的AMPHP-SON算法應(yīng)用于動車組運維效率關(guān)聯(lián)規(guī)則挖掘，以發(fā)現(xiàn)影響動車組關(guān)鍵部件運維效率的重要因素，進(jìn)而支撐動車組修程修制優(yōu)化，提高運維效率，降低運維成本.實驗證明，本文提出的AMPHP-SON算法具有很好的時間性能，且挖掘出的規(guī)則可以有效地指導(dǎo)動車組運用維修.

1 相關(guān)工作

1.1 DHP算法

為了解決Apriori算法的效率瓶頸問題，Park等人[3]提出了基于Hash修剪技術(shù)的DHP算法.DHP算法使用Hash函數(shù)來高效地產(chǎn)生候選項目集，利用Hash表地址對應(yīng)的計數(shù)值刪除不是頻繁項集的候選項集，這樣減少了需要驗證的候選項集，特別是解決了生成頻繁2-項集時的性能瓶頸問題.DHP算法在尋找k-1-項目集Lk-1時，為候選集Ck生成一個Hash表，并且根據(jù)這張Hash表來過濾候選集Ck.在生成Hash表的時候無法避免沖突的產(chǎn)生，因此DHP算法設(shè)置了散列桶(桶中只存儲Hash到該桶中的元素個數(shù)，并不存儲元素本身)，將產(chǎn)生沖突的候選項集放入桶中并增加對應(yīng)的桶計數(shù).但當(dāng)項目個數(shù)較多或者事物集較大時，大部分桶計數(shù)都將會達(dá)到預(yù)設(shè)的最小支持度計數(shù)，對候選集的過濾效果不夠好，且為了判斷這些桶中的候選集是否為頻繁項集，還需再次掃描數(shù)據(jù)庫.這種情況下DHP算法的性能可能還不如Apriori算法好.

為了解決上述DHP算法壓縮效果不好，還需再次掃描數(shù)據(jù)庫的問題，Tseng等人[4]提出了多階段索引和修剪(multi-phase indexing and pruning, MPIP)算法[5].MPIP算法的主要貢獻(xiàn)是使用最小完美Hash函數(shù)解決了DHP算法中的Hash沖突問題，它可以為每一個項目集產(chǎn)生唯一的Hash地址，并在不浪費空間的情況下將它們映射到Hash表中，也即Hash表的長度等于所有項目集的個數(shù).Hash表的每一項都是該地址所對應(yīng)的項目集的支持度，因此可以用來過濾候選項集并直接給出頻繁項集，可以避免重復(fù)掃描數(shù)據(jù)庫，從而減少對磁盤IO的訪問.“最小完美Hash函數(shù)”[6]在概念上很完美，生成的思想也很不錯，但在動車組的大數(shù)據(jù)應(yīng)用環(huán)境中卻并不合適，因為當(dāng)數(shù)據(jù)集很大時，生成最小完美Hash函數(shù)的開銷也會非常大.吳恒等人提出另一種基于動態(tài)鏈改進(jìn)的DLDHP算法[7]，他們使用鏈接技術(shù)解決Hash沖突問題，但鏈接技術(shù)需要使用額外的數(shù)據(jù)結(jié)構(gòu)，節(jié)點中同時存儲元素本身、元素計數(shù)和指針域，浪費內(nèi)存空間；并且在Hash函數(shù)設(shè)計不當(dāng)時，Hash表會退化成鏈表，其查找效率非常低.

1.2 SON算法

SON算法是基于作者Savasere，Omiecinski，Navathe的名字而命名的[8]，它能夠在2次掃描的代價下去掉所有的偽反例和偽正例[9].其基本思路是，將輸入文件分成多個組塊，將每個組塊看成是一個樣本數(shù)據(jù)，然后在該組塊上運行任一種關(guān)聯(lián)規(guī)則算法.如果每個組塊占整個文件的比例為p，而s是支持度閾值，可以使用ps作為支持度閾值，發(fā)現(xiàn)每個組塊上的頻繁項集，這是第1次掃描.一旦所有的組塊都采用了上述方法進(jìn)行了處理，就可以將所有在一個或多個組塊上發(fā)現(xiàn)的頻繁項集進(jìn)行合并,這些項集為候選項集.如果某個項集在任意組塊上都不頻繁，那么它在每個組塊上的支持度都低于ps，由于組塊的數(shù)目是1p，因此該項集在所有數(shù)據(jù)集上的支持度將低于(1p)ps=s.所以，在所有數(shù)據(jù)集上頻繁的項集至少會在一個組塊上是頻繁的.第2次掃描中對所有候選項集計數(shù)并選出支持度不低于s的頻繁項集.

2 基于近似最小完美Hash函數(shù)的AMPHP算法

2.1 近似最小完美Hash函數(shù)

為了解決DHP算法中的Hash沖突問題，也避免MPIP算法中生成最小完美Hash函數(shù)的巨大開銷，本文提出一種近似最小完美Hash函數(shù)(approximate minimum perfect hashing function)來代替，并最終提出AMPHP算法.近似最小完美Hash函數(shù)不會產(chǎn)生Hash沖突，且所用空間即Hash表的長度也接近事物數(shù)據(jù)庫中不重復(fù)項集的個數(shù).

I={i1,i2,…,im}為全集，按序編號分別為1,2,…,m，對于給定的2項組合，給出Hash函數(shù)：

H({im,in})=S(m-1)+n-1-m(m+1)2，

(1)

其中，S為事物數(shù)據(jù)庫中項的總數(shù)加1；m和n為自然數(shù)，分別為im，in的編號，且m

以下證明任意2個不同的2-項集不會映射到Hash表的同一個單元中，即不會產(chǎn)生沖突.

命題1. 若H({im1,in1})=H({im2,in2})，則必須m1=m2且n1=n2.

證明. 假設(shè)存在m1≠m2，n1≠n2，使得H({im1,in1})=H({im2,in2})成立.

令G=H({im1,in1})-H({im2,in2})=S(m1-1)+n1-1-m1(m1+1)2-[S(m2-1)+n2-1-m2(m2+1)2]=(m2-m1)(1+m2+m1-2S)2+(n1-n2).

1)m1=m2，n1≠n2.

G=(m2-m1)(1+m2+m1-2S)2+(n1-n2)=n1-n2≠0.

2)m1≠m2，n1=n2.

G=(m2-m1)(1+m2+m1-2S)2+(n1-n2)=(m2-m1)(1+m2+m1-2S)2.

因為m1≠m2，所以m2-m1≠0；因為m1

3)m1≠m2且n1≠n2.

假設(shè)m10).

① 若m2-m1=1，則m2=S-x-a+1.

所以n2=n1+[1+(S-x-a+1)+(S-x-a)-2S]2=n1-x-a+1.

又n1=S-x,所以n2=S-2x-a+1.

又m2=S-x-a+1,所以n2

② 若m2-m1>1,則n2≤n1+1+S-x-a+m2-2S=S-x+1+S-x-a+m2-2S=m2-2x-a+1.

又x,a均為自然數(shù)，a>0,所以n2≤m2,與已知矛盾.

同理，當(dāng)m1>m2時，可得相同結(jié)論.故，必須m1=m2且n1=n2時，H({im1,in1})=H({im2,in2})才成立.

證畢.

因此對于給定的Hash函數(shù)H({im,in})=S(m-1)+n-1-m(m+1)2，任意2個不同的2-項集不會映射到Hash表的同一個單元中，即不會產(chǎn)生沖突.在掃描事物數(shù)據(jù)庫中的每條交易產(chǎn)生L1的同時，對每條交易的所有2項組合作一個Hash計數(shù)，對2-項集{im,in}進(jìn)行計數(shù)時，就將Hash表對應(yīng)位置中的計數(shù)值加1.當(dāng)掃描事物數(shù)據(jù)庫完成以后，不但得到L1而且還得到一個Hash表H，H當(dāng)中的每個單元的值是一個計數(shù)累加.判斷該單元中計數(shù)值是否大于等于支持度閾值，如果是，則這2項組合為L2中的一員，否則就不是L2中的成員.

2.2 AMPHP算法

我們采用表1所示的事物數(shù)據(jù)庫來舉例說明AMPHP算法的流程.項A，B，C，D，E的序號分別為1，2，3，4，5，對于給定的Hash函數(shù)H({im,in})=S(m-1)+n-1-m(m+1)2，其中S=5，對該事物數(shù)據(jù)庫中每條交易的所有2項組合作Hash計數(shù)：

Table 1 Transaction Database

例如，對于二項集{A,C}，A,C的序號分別為1和3，則H({i1,i3})=5×(1-1)+3-1-(1+1)2=1，即{A,C}映射到Hash表地址1所對應(yīng)的單元中，將Hash表地址1所對應(yīng)的單元中的計數(shù)值加1.具體的Hash過程如圖1所示：

Fig. 1 Hash process of AMPHP algorithm圖1 AMPHP算法的Hash過程

如圖1所示，AMPHP算法采用近似最小完美Hash函數(shù)，在生成L1掃描事物數(shù)據(jù)庫的同時，有效地將每一個2-項集映射到Hash表唯一的地址中進(jìn)行計數(shù)，通過將計數(shù)值與預(yù)設(shè)的支持度閾值s進(jìn)行比較，從而可以過濾掉所有的非頻繁2-項集.從圖1可以看出，AMPHP算法在1次數(shù)據(jù)庫掃描中可以同時得到L1和L2，在第1次和第2次迭代中不會產(chǎn)生候選項集，具有很好的空間和時間性能.

3 AMPHP-SON算法

3.1 AMPHP-SON算法思想

AMPHP算法雖然本身已經(jīng)具有很好的時間和空間性能，但基于單機(jī)處理的數(shù)據(jù)挖掘只能處理簡單、小規(guī)模的數(shù)據(jù)集.而隨著動車組運維數(shù)據(jù)的積累，事物數(shù)據(jù)庫不斷增大，單機(jī)性能已無法滿足在大數(shù)據(jù)集中快速發(fā)現(xiàn)有用規(guī)則的需求.因此本文借鑒SON算法的思想，對AMPHP算法進(jìn)行并行化改進(jìn)[10]，最終提出AMPHP-SON算法.

Fig. 2 Flow of SON algorithm圖2 SON算法流程

SON算法非常適合于并行計算環(huán)境.每個組塊可以并行處理，它們產(chǎn)生的頻繁項集合并成候選項集.將所有候選項集分布到多個處理器上進(jìn)行處理，每個處理器計算每個候選項集在1個組塊上的支持度，最后對它們求和得到每個候選項集在整個數(shù)據(jù)集上的支持度.上述過程可以很自然地使用2輪MapReduce迭代實現(xiàn)[11]，如圖2所示，其中pi為每個Map任務(wù)所得到輸入文件占總輸入文件的比例，F(xiàn)i為滿足本Map任務(wù)支持度閾值的項集，vi為候選集在本Map任務(wù)所分配數(shù)據(jù)集上的支持度，s為支持度閾值.從圖2可以看出，SON算法第1輪迭代求出局部頻繁項集，第2輪迭代求出全局頻繁項集[12].但其缺點是仍需要2次掃描數(shù)據(jù)庫，而掃描數(shù)據(jù)庫進(jìn)行磁盤IO會占用大量的時間.

為了減少掃描數(shù)據(jù)庫的次數(shù)，在SON算法的第1次掃描數(shù)據(jù)庫中使用AMPHP算法，直接計算每個項集在各自組塊上的計數(shù)值，然后在Reduce階段統(tǒng)計每個項集在整個數(shù)據(jù)集上的支持度，通過與預(yù)設(shè)的支持度閾值進(jìn)行比較，得出頻繁項集.具體過程如圖3所示，其中pi為每個Map任務(wù)所得到輸入文件占總輸入文件的比例，F(xiàn)i為滿足本Map任務(wù)支持度閾值的項集，vi為候選集在本Map任務(wù)所分配數(shù)據(jù)集上的支持度，s為支持度閾值.

Fig. 3 Flow of AMPHP-SON algorithm圖3 AMPHP-SON算法流程

3.2 AMPHP-SON算法實現(xiàn)

本文提出的AMPHP-SON算法是基于AMPHP算法的分區(qū)算法，它只需要1輪MapReduce迭代即可找出頻繁項集.Map階段和Reduce階段的具體任務(wù)和關(guān)鍵代碼如下所述.

1) Map階段

Map階段，該階段每個Map任務(wù)完成從事物數(shù)據(jù)集的某一個分區(qū)中讀取到事務(wù)，并將該分區(qū)中所有的事務(wù)存儲在本地內(nèi)存中，然后利用AMPHP算法算出本分區(qū)的局部頻繁項集，最后輸出的是一個鍵值對〈Fi,vi〉，其中Fi是本分區(qū)的一個局部頻繁項集，vi是該局部頻繁項集在本分區(qū)的支持度.以下為Mapper類的部分關(guān)鍵代碼：

Class Mapper{

ListtSet；

MaplocalFI；

map(key,value){

transaction=genTransaction(value)；

tSet.add(transaction)；

}

cleanup(){

localFI=genFrequentItemsets(transaction)；

for(inti=1;(fis=localFI.get(i))≠null;i++)

for(f:fis)

write(f,v)；

}

genFrequentItemsets(transaction){

L1=find(transaction,minsupport);

for(intk=2;Lk≠?;k++){

Ck=Apriori_gen(Lk-1);

Lk=AMPHP_Hash(Dk);

Dk+1=pruning(Dk);

}

}}

2) Reduce階段

Reduce階段，該階段的每個Reduce任務(wù)會處理1組局部頻繁項集，上個階段所有的Map任務(wù)輸出的相同局部頻繁項集會集中到同一個Reduce任務(wù)上進(jìn)行處理，Reduce任務(wù)就是合并計算該局部頻繁項集在整個數(shù)據(jù)集上的支持度，將其支持度與支持度閾值相比較，最終得出全局頻繁項集.Reducer類的部分關(guān)鍵代碼如下：

Class Reducer{

reduce(key,value){

write(f,v)；

}

}

4 動車組運維效率關(guān)聯(lián)關(guān)系分析

4.1 應(yīng)用環(huán)境

整個實驗是在Hadoop平臺下運行的，采用了Hadoop的1.0.4穩(wěn)定版本.硬件設(shè)備為9臺x86架構(gòu)的PC，其中1臺是Master節(jié)點，其余8臺是Slave節(jié)點.主設(shè)備節(jié)點采用Intel至強(qiáng)處理器，內(nèi)存為2 GB；從設(shè)備節(jié)點采用了AMD 4核處理器，主頻為2.7 GHz，內(nèi)存為2 GB.

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

本實驗數(shù)據(jù)的來源是國內(nèi)某動車組運用檢修段2012—2014年的所有動車組牽引電機(jī)檢修數(shù)據(jù).經(jīng)過缺省值處理、歸一化、離散化[13]等一系列數(shù)據(jù)預(yù)處理操作之后，選取50 GB大小的數(shù)據(jù)集.

4.3 結(jié)果分析

在上述實驗環(huán)境和實驗數(shù)據(jù)的基礎(chǔ)上，應(yīng)用本文提出的AMPHP-SON算法對動車組牽引電機(jī)運維數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘，得出的動車組運維效率關(guān)聯(lián)規(guī)則部分結(jié)果如表2所示：

Table 2 Partial Results of the Association Rules of EMU Operation and Maintenance Efficiency

如表2所示，規(guī)則“車型B,編組編號AA,110萬km=>低[Support=1.53%,Confidence=9.25%]”的含義是車型B編組編號AA的動車組，在運行累計里程達(dá)110萬km時，運維效率低，支持度為1.53%，置信度為9.25%.該規(guī)則符合實際意義，即臨近大修時牽引電機(jī)易出現(xiàn)故障，且故障原因較復(fù)雜，因此檢修過程慢，運維效率低.規(guī)則“設(shè)備011,人員103=>較高[Support=1.23%,Confidence=11.27%]”的含義是人員103使用設(shè)備011對牽引電機(jī)進(jìn)行檢修，運維效率較高，支持度為1.23%，置信度為11.27%.根據(jù)該規(guī)則我們可以推測設(shè)備011的檢修性能較好，人員103檢修專業(yè)技能較強(qiáng)，利用該規(guī)則我們可以合理安排人員和設(shè)備，從而達(dá)到提高運維效率的目的.規(guī)則“經(jīng)度:110.14—112,緯度:22.5—42.37=>較低[Support=2.08%,Confidence=10.93%]”的含義是在經(jīng)度為110.14—112且緯度為22.5—42.37的地域內(nèi)，牽引電機(jī)的運維效率較低.從該規(guī)則可以初步預(yù)測該地域內(nèi)環(huán)境比較惡劣，牽引電機(jī)容易發(fā)生故障，從而導(dǎo)致維修次數(shù)增加，備品備件不足，因此運維效率較低.規(guī)則“車型A,編組編號AC,7月=>低[Support=1.43%,Confidence=8.17%]”的含義是車型A編組編號AC的動車組在7月份牽引電機(jī)的維修效率低.該規(guī)則符合實際意義，即7月份溫度較高導(dǎo)致牽引電機(jī)故障頻發(fā)，引起維修次數(shù)增加，備品備件不足，從而運維效率低.上兩條規(guī)則給我們的指導(dǎo)意義是根據(jù)不同的地域和時間合理制定備品備件的訂購計劃，以達(dá)到提高運維效率的目的.

4.4 性能分析

為了評估本文所提出算法的性能，我們首先將單機(jī)版的AMPHP算法與傳統(tǒng)的Apriori算法、DHP算法以及他人改進(jìn)的MPIP算法、DLDHP算法進(jìn)行比較，實驗數(shù)據(jù)集的大小分別為1 GB，5 GB，10 GB，20 GB，30 GB，實驗結(jié)果如圖4所示：

Fig. 4 Performance comparison of five algorithms圖4 5種算法性能比較

Fig. 5 Performance comparison of AMPHP and AMPHP-SON algorithm圖5 AMPHP算法與AMPHP-SON算法性能比較

圖4顯示，在數(shù)據(jù)集較小的情況下，傳統(tǒng)的Apriori算法和DHP算法的性能優(yōu)于AMPHP算法，因為數(shù)據(jù)集較小，產(chǎn)生的候選項集也小，對候選項集的判斷不會耗費太多時間，但是近似最小完美Hash函數(shù)的生成和Hash表的構(gòu)建都需要耗費額外的時間;在數(shù)據(jù)集較大的情況下，產(chǎn)生的候選項集也隨之增大，AMPHP算法使用近似最小完美Hash函數(shù)構(gòu)建Hash表有效地過濾掉所有的非頻繁項集，節(jié)省了再次掃描數(shù)據(jù)庫的時間，因而性能較好.

為了對單機(jī)串行的AMPHP算法和多機(jī)并行AMPHP-SON算法進(jìn)行比較，實驗數(shù)據(jù)集的大小分別為10 GB，20 GB，30 GB，40 GB，50 GB，并行AMPHP-SON算法的分區(qū)數(shù)為4，實驗結(jié)果如圖5所示:

圖5顯示，在數(shù)據(jù)集較小的情況下，單機(jī)串行的AMPHP算法的性能優(yōu)于多機(jī)并行AMPHP-SON算法，因為此時Hadoop平臺自身消耗的時間將遠(yuǎn)遠(yuǎn)超過數(shù)據(jù)處理的時間;在數(shù)據(jù)集較大的情況下，Hadoop集群用于數(shù)據(jù)處理的時間將會遠(yuǎn)遠(yuǎn)大于集群自身所耗費的時間，并行的AMPHP-SON算法將任務(wù)分配給多個節(jié)點同時進(jìn)行處理，其性能優(yōu)于串行的AMPHP算法.

為了測試分區(qū)數(shù)對AMPHP-SON算法性能的影響，我們在將50 GB的數(shù)據(jù)集分成1塊、2塊、4塊、8塊的情況下分別運行AMPHP-SON算法，運行結(jié)果如圖6所示：

Fig. 6 Performance of AMPHP-SON algorithm under different partitions圖6 不同分區(qū)數(shù)下AMPHP-SON算法性能

圖6顯示了隨著數(shù)據(jù)集劃分塊數(shù)的增加，AMPHP-SON算法的運行能夠得到接近線性的加速比，如圖7所示：

Fig. 7 Speedup ratio of AMPHP-SON algorithm圖7 AMPHP-SON算法的加速比

5 結(jié)束語

本文提出的AMPHP-SON算法，使用近似最小完美Hash函數(shù)過濾掉所有的非頻繁項集，且借鑒SON算法將關(guān)聯(lián)規(guī)則挖掘任務(wù)分配給多個節(jié)點共同完成，可以快速地從動車組海量運維數(shù)據(jù)中挖掘出有用的信息，以指導(dǎo)動車組修程修制優(yōu)化，提高動車組運維效率.

[1]Agrawal R. Mining association rules between sets of items in large databases[J]. ACM SIGMOD Record, 1993, 22(2): 207-216

[2]Linoff G S, Berry M J A. Data Mining Techniques: For Marketing, Sales, and Customer Relationship Management[M]. Hoboken, NJ: Wiley Publishing, 2011: 54-55

[3]Park J S, Chen M S, Yu P S. An effective Hash-based algorithm for mining association rules[J]. ACM SIGMOD Record, 2010, 24(2): 175-186

[4]Tseng J C R, Hwang G J, Tsai W F. A minimal perfect hashing scheme to mining association rules from frequently updated data[J]. Journal of the Chinese Institute of Engineers, 2006, 29(3): 391-401

[5]Chiou C K, Tseng J C R. An incremental mining algorithm for association rules based on minimal perfect hashing and pruning[C]Proc of Int Conf on Web Technologies and Applications. Berlin: Springer, 2012: 106-113

[6]Witten I H, Moffat A, Bell T C. Managing Gigabytes: Compressing and Indexing Documents and Images[M]. 2nd ed. San Francisco, CA: Morgan Kaufmann, 1999

[7]Wu Heng, Wu Genxiu, Mao Linchuan, et al. An algorithm for mining association rules of dynamic chain address based on DHP[J]. Journal of Jiangxi Normal University: Natural Science Edition, 2015(5): 463-468 (in Chinese)(吳恒, 吳根秀, 毛臨川, 等. 一種基于DHP的動態(tài)鏈地址關(guān)聯(lián)規(guī)則挖掘算法[J]. 江西師范大學(xué)學(xué)報: 自然科學(xué)版, 2015(5): 463-468)

[8]Savasere A, Omiecinski E, Navathe S B. An efficient algorithm for mining association rules in large databases[C]Proc of Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 1995: 432-444

[9]Rajaraman A, Ullman J D. Mining of Massive Datasets[M]. Cambridge, UK: Cambridge University Press, 2012

[10]Xiao Tao, Yuan Chunfeng, Huang Yihua. PSON: A parallelized SON algorithm with MapReduce for mining frequent sets[C]Proc of the 4th Int Symp on Parallel Architectures, Algorithms and Programming. Los Alamitos, CA: IEEE Computer Society, 2011: 252-257

[11]Guo Jinwei, Pi Jianyong. Implementation of SON algorithm based on MapReduce[J]. Journal of Computer Applications, 2014, 34(S1): 100-102 (in Chinese)(郭進(jìn)偉, 皮建勇. 基于MapReduce的SON算法實現(xiàn)[J]. 計算機(jī)應(yīng)用, 2014, 34(S1): 100-102)

[12]Xu Hui, Sun Qi, Yang Lin, et al. Parallel algorithm design for mining association rules based on big data[J]. Computer Science, 2014, 10(41): 434-437 (in Chinese)(徐慧, 孫琪, 楊林, 等. 面向大數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘算法并行化設(shè)計[J]. 計算機(jī)科學(xué), 2014, 10(41): 434-437)

[13]Hu Hui. Research and implementation of mining association rules for EMU failure data based on Hadoop[D]. Beijing: Beijing Jiaotong University, 2015: 21-22 (in Chinese)(胡輝. 基于Hadoop的動車組故障數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘研究與實現(xiàn)[D]. 北京: 北京交通大學(xué), 2015: 21-22)

Zhang Chun, born in 1966. Master. Senior engineer. Her main research interests include big data, data mining and modern railway information technology.

Zhou Jing, born in 1992. Master. Her main research interests include big data, data mining and modern railway information technology.

Optimization Algorithm of Association Rule Mining for EMU Operation and Maintenance Efficiency

Zhang Chun and Zhou Jing

(SchoolofComputerandInformationTechnology,BeijingJiaotongUniversity,Beijing100044) (EngineeringResearchCenterofNetworkManagementTechnologyforHighSpeedRailway(BeijingJiaotongUniversity),MinistryofEducation,Beijing100044)

With the increase of EMU operation time and mileage, EMU operation and maintenance system has accumulated a large amount of data. Using the high-performance association rule mining algorithms to quickly find useful information from the EMU operation and maintenance data, is of significant importance for improving the operation and maintenance efficiency of the key components of the EMU. In the view of the characteristics of EMU operation and maintenance data—huge volume and low value density, we design the AMPHP algorithm based on the approximate minimal perfect Hash function. Compared with the traditional DHP algorithm, it can filter out all the infrequent item sets without additional database scanning. In order to break the limitation of the single machine algorithm and further improve the performance of the algorithm, we use the idea of SON algorithm for reference to parallelize the AMPHP algorithm and finally propose the AMPHP-SON algorithm. Some experiments have been performed on the operation and maintenance data of EMU traction motor. The experimental result shows that the AMPHP-SON algorithm has good time performance and the rules dug out can be effectively used to guide the optimization of the repair class and repair system of EMU, so as to improve the efficiency of EMU operation and maintenance.

association rules mining; DHP (direct hashing and pruning) algorithm; approximate minimum perfect Hash function; SON algorithm; EMU

2016-07-05；

2017-02-22

國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2015AA043701) This work was supported by the National High Technology Research and Development Program of China (863 Program)(2015AA043701).

周靜(14120456@bjtu.edu.cn)

TP311