楊浩敏，馬 超，吳海燕

(重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044)

0引言

關(guān)聯(lián)分類算法［1］是基于關(guān)聯(lián)規(guī)則的分類算法。相對于決策樹算法、貝葉斯算法、KMeans 算法以及支持向量機(jī)等分類算法，關(guān)聯(lián)分類算法在準(zhǔn)確率和可拓展性方面有著不錯的表現(xiàn)，成為分類算法研究領(lǐng)域重要的分支。關(guān)聯(lián)分類算法總體上可以分為2 大類:顯式關(guān)聯(lián)分類算法和lazy 關(guān)聯(lián)分類算法［2］。

顯式關(guān)聯(lián)分類算法的訓(xùn)練和分類這2 個(gè)環(huán)節(jié)是彼此獨(dú)立的，在國際上比較有影響力的算法主要有CBA［3］算法和CMAR［4］算法。

Lazy 關(guān)聯(lián)分類算法將訓(xùn)練階段推遲到了分類階段，典型算法是Veloso A 等人于2006 年提出的。該算法先將待分類樣本對訓(xùn)練樣本做投影操作，然后利用挖掘出來的關(guān)聯(lián)規(guī)則構(gòu)建分類器，能夠較好地解決顯式關(guān)聯(lián)分類算法存在的small disjunction 和候選規(guī)則集過大的問題。Elena Baralis 等人在2008 年提出采用lazy 思想進(jìn)行剪枝的L3算法［5］，嚴(yán)格意義屬于顯式關(guān)聯(lián)分類。2013 年，付萌等人利用混合策略方法［6］，將lazy 方法的優(yōu)點(diǎn)應(yīng)用到顯式關(guān)聯(lián)分類中;李賓飛等人則將lazy 方法應(yīng)用到數(shù)量型關(guān)聯(lián)分類中［7］。在lazy 關(guān)聯(lián)分類算法中，每個(gè)待分類樣本都要對訓(xùn)練樣本進(jìn)行投影并構(gòu)建一個(gè)分類器，對多個(gè)待分類樣本進(jìn)行分類時(shí)效率很低。

分布式關(guān)聯(lián)規(guī)則挖掘算法能夠提升lazy 關(guān)聯(lián)分類關(guān)聯(lián)規(guī)則挖掘環(huán)節(jié)的效率，典型算法是基于Apriori的并行算法［8］。D.W.Cheung 于1996 年提出了FDM算法［9］，利用局部剪枝基于Apriori 的并行算法進(jìn)行改進(jìn)，減少各個(gè)分區(qū)間的數(shù)據(jù)通訊量。王越在2003年提出了帶有中心節(jié)點(diǎn)的C-DMA(Center-Data Mining Algorithim)算法［10］，將全局剪枝放到中心節(jié)點(diǎn)中進(jìn)行，將數(shù)據(jù)通訊局限在中心節(jié)點(diǎn)和各個(gè)分節(jié)點(diǎn)之間。張春生等人利用數(shù)據(jù)局部性對C-DMA 算法進(jìn)行改進(jìn)［11］，提出分段支持度，使得分片之間幾乎不用進(jìn)行數(shù)據(jù)交換，不僅提高了算法的執(zhí)行效率，也提高了算法挖掘全局規(guī)則的能力。針對lazy 關(guān)聯(lián)分類算法特有的投影操作，并未見分布式實(shí)現(xiàn)。

應(yīng)用分布式關(guān)聯(lián)規(guī)則挖掘算法的lazy 關(guān)聯(lián)分類算法稱為分布式lazy 關(guān)聯(lián)分類(DLAC)算法。現(xiàn)有的DLAC 算法存在2 個(gè)主要問題:1)對多個(gè)待樣本進(jìn)行分類時(shí)效率低下;2)投影操作未分布式實(shí)現(xiàn)。第一個(gè)問題是lazy 關(guān)聯(lián)分類本身的問題，第二個(gè)問題是分布式關(guān)聯(lián)規(guī)則挖掘算法應(yīng)用于lazy 關(guān)聯(lián)分類所帶來的問題。針對上述2 個(gè)問題，本文提出一種改進(jìn)型的分布式lazy 關(guān)聯(lián)分類PDLAC 算法，對滿足條件的多個(gè)待分類樣本進(jìn)行聚合，然后進(jìn)行分布式投影并分布式地挖掘關(guān)聯(lián)規(guī)則，最后構(gòu)建分類器。對滿足條件的多個(gè)待分類樣本進(jìn)行聚合，有效地解決lazy 關(guān)聯(lián)分類算法對多個(gè)待分類樣本進(jìn)行分類的效率問題;分布式投影解決了分布式關(guān)聯(lián)規(guī)則挖掘算法應(yīng)用于lazy關(guān)聯(lián)分類時(shí)的不足。

1 分布式lazy 關(guān)聯(lián)分類算法

DLAC 算法主要由2 部分組成:lazy 關(guān)聯(lián)分類算法和分布式關(guān)聯(lián)規(guī)則挖掘算法C-DMA。

1.1 Lazy 關(guān)聯(lián)分類算法

lazy 關(guān)聯(lián)分類算法是在顯式關(guān)聯(lián)分類算法的基礎(chǔ)上發(fā)展而來的。

典型的顯式關(guān)聯(lián)分類算法是CBA 算法，算法步驟如下:

1)離散化訓(xùn)練樣本和待樣本中的連續(xù)屬性。

2)使用關(guān)聯(lián)規(guī)則挖掘算法Apriori，挖掘出候選的關(guān)聯(lián)規(guī)則CARs。

3)使用分類器構(gòu)造算法CBA-CB，從候選的關(guān)聯(lián)規(guī)則CARs 中選擇合適的關(guān)聯(lián)規(guī)則來構(gòu)建分類器。

關(guān)聯(lián)分類中涉及的基本概念:

假 設(shè) T={t1，t2，...，tn}為事務(wù)集，Ti={t1i，t2i，...，tni}為一個(gè)事務(wù)，t1i，t2i，...，tni稱為Ti的子項(xiàng)，Ti的子集稱為項(xiàng)集S，S?Ti。設(shè)項(xiàng)集A、B，那么關(guān)聯(lián)規(guī)則定義為“A→B”。在關(guān)聯(lián)分類當(dāng)中，A 一般為屬性的集合，B 一般為類別。

關(guān)聯(lián)規(guī)則A→B 可用如下參數(shù)描述:

支持度:

置信度:

步驟2)中使用關(guān)聯(lián)規(guī)則挖掘算法Apriori 挖掘出支持度較高的關(guān)聯(lián)規(guī)則。步驟3)中優(yōu)先選擇CARs中置信度高的關(guān)聯(lián)規(guī)則插入分類器，并刪除該關(guān)聯(lián)規(guī)則覆蓋的訓(xùn)練樣本對象，如果該關(guān)聯(lián)規(guī)則沒有覆蓋任何訓(xùn)練樣本對象，則不加入分類器當(dāng)中。對于訓(xùn)練樣本中不被CARs 關(guān)聯(lián)規(guī)則覆蓋的樣本對象，選擇大部分樣本所屬類別作為默認(rèn)類。

lazy 關(guān)聯(lián)分類算法對每一個(gè)待分類樣本構(gòu)建一個(gè)分類器。算法步驟如下:

1)每一個(gè)待分類樣本對訓(xùn)練樣本進(jìn)行投影。

2)在投影后的訓(xùn)練樣本中，使用關(guān)聯(lián)規(guī)則挖掘算法挖掘支持度較高的關(guān)聯(lián)規(guī)則。

3)選擇置信度最好的一條關(guān)聯(lián)規(guī)則，對待分類樣本進(jìn)行分類。

1.2 分布式關(guān)聯(lián)規(guī)則挖掘算法

C-DMA 算法是由FDM 算法發(fā)展而來的，是對并行Apriori 算法的一種改進(jìn)，算法的具體步驟如下，其算法流程圖如圖1 所示。

圖1 C-DMA 算法流程圖

1)將訓(xùn)練樣本分區(qū)，K=1。

2)在各個(gè)分區(qū)中挖掘K 候選關(guān)聯(lián)規(guī)則，根據(jù)局部支持度，對候選關(guān)聯(lián)規(guī)則進(jìn)行裁剪。

3)匯總各個(gè)分區(qū)的候選關(guān)聯(lián)規(guī)則，根據(jù)全局支持度，對候選關(guān)聯(lián)規(guī)則進(jìn)行剪枝。

4)根據(jù)剪枝后的K 候選關(guān)聯(lián)規(guī)則，生成K+1 候選關(guān)聯(lián)規(guī)則，K=K+1。

5)循環(huán)步驟2)～4)，直到無法生成候選關(guān)聯(lián)規(guī)則。

1.3 DLAC 算法存在的問題

顯式關(guān)聯(lián)分類算法直接從訓(xùn)練樣本中挖掘關(guān)聯(lián)規(guī)則，構(gòu)建分類器，多個(gè)待分類樣本使用同一個(gè)分類器。lazy 關(guān)聯(lián)分類算法采用lazy 分類思想［12］，每一個(gè)待分類樣本先對訓(xùn)練樣本做投影，然后挖掘關(guān)聯(lián)規(guī)則構(gòu)建分類器，每一個(gè)待分類樣本都對應(yīng)一個(gè)分類器。經(jīng)過研究，lazy 關(guān)聯(lián)分類能夠較好地解決顯式關(guān)聯(lián)分類算法存在的small disjunction 和候選規(guī)則集過大的問題，但也存在以下2 個(gè)缺點(diǎn):

1)對多個(gè)待分類樣本進(jìn)行分類時(shí)，效率很低。

2)分類器中只有一條規(guī)則，容易導(dǎo)致過度擬合的問題。

分布式關(guān)聯(lián)規(guī)則挖掘算法C-DMA 應(yīng)用于lazy 關(guān)聯(lián)分類中的時(shí)候，只在關(guān)聯(lián)規(guī)則挖掘一個(gè)環(huán)節(jié)做了分布式實(shí)現(xiàn)，投影操作并沒有分布式實(shí)現(xiàn)。

2 改進(jìn)型的分布式lazy 關(guān)聯(lián)分類算法

2.1 PDLAC 算法概述

基于上面的分析，本文提出改進(jìn)型的分布式lazy關(guān)聯(lián)分類PDLAC 算法。PDLAC 算法對待分類樣本進(jìn)行KMeans 聚類;其次，判斷類內(nèi)的待分類樣本是否滿足聚合條件，滿足進(jìn)行聚合，不滿足則類內(nèi)的每個(gè)待分類樣本單獨(dú)成為一類;然后，進(jìn)行分布式投影并使用C-DMA 算法挖掘關(guān)聯(lián)規(guī)則;最后，構(gòu)建分類器對類內(nèi)的一個(gè)或多個(gè)待分類樣本進(jìn)行分類。算法主要解決以下3 個(gè)問題:1)如何對待分類樣本進(jìn)行聚合;2)如何分布式實(shí)現(xiàn)投影操作;3)分類器如何構(gòu)造。

基于lazy 方法的分布式關(guān)聯(lián)分類算法模型如圖2 所示。其算法步驟如下:

1)對待分類樣本進(jìn)行KMeans 聚類。

2)對每一個(gè)類別判斷是否滿足聚合條件，滿足則進(jìn)行聚合，不滿足則每個(gè)待分類樣本單獨(dú)成為一類。

3)每一個(gè)待分類樣本聚合對訓(xùn)練樣本進(jìn)行分布式投影操作。

4)使用C-DMA 算法挖掘關(guān)聯(lián)規(guī)則。

5)對每一類待分類樣本構(gòu)建一個(gè)分類器。

6)使用分類器對類內(nèi)的樣本進(jìn)行分類。

圖2 PDLAC 算法流程圖

2.2 待分類樣本聚合

對待分類樣本進(jìn)行聚合，使得多個(gè)相似的待分類樣本只需進(jìn)行一次投影操作和關(guān)聯(lián)規(guī)則挖掘。具體做法是使用KMeans 算法對待分類樣本進(jìn)行聚類，判斷類別是否符合聚合條件，如果符合聚合條件則進(jìn)行聚合，進(jìn)行屬性聚合，并進(jìn)行分布式投影和關(guān)聯(lián)規(guī)則分布式挖掘，最后構(gòu)建該類別的分類器并進(jìn)行分類;如果不符合聚合條件，每個(gè)待分類樣本直接進(jìn)行分布式投影并分布式挖掘關(guān)聯(lián)分類規(guī)則，選取置信度最高的規(guī)則對待分類樣本進(jìn)行分類。對待分類樣本進(jìn)行聚合，需要解決2 個(gè)關(guān)鍵問題:KMeans 聚類的粒度問題，聚合判斷條件。

KMeans 聚類的時(shí)候，聚類的類別個(gè)數(shù)與粒度成反比關(guān)系。確定了類別的個(gè)數(shù)就確定了聚類的粒度。假設(shè)訓(xùn)練樣本每個(gè)維度的可選項(xiàng)個(gè)數(shù)為c，如果不同維度的可選項(xiàng)個(gè)數(shù)不同則取平均值，待分類樣本個(gè)數(shù)為N，那么聚類的類別個(gè)數(shù)KMeans_ClassNum=3N/c。

待分類樣本經(jīng)過KMeans 聚類，形成多個(gè)類別，對每個(gè)類別中的待分類樣本的屬性進(jìn)行聚合。I1，I2，...，In表示某個(gè)類別的待分類樣本，I 表示樣本聚合的結(jié)果，I=I1∪I2∪...∪In。LenI 表示聚合后I 的長度，LenIn表示I1，I2，...，In的平均長度，LenIn=LenIi/n。

聚合判斷條件是ln LenI/ln LenIn＜ln n。

2.3 分布式投影

分布式投影將待分類樣本或樣本聚合的結(jié)果分發(fā)到各個(gè)訓(xùn)練樣本分片中去，在各個(gè)分片中進(jìn)行獨(dú)立的投影操作，示意圖如圖3 所示。

圖3分布式投影示意圖

2.4 分類器構(gòu)造

分類器表示為R，C-DMA 算法生成的關(guān)聯(lián)規(guī)則表示為CARs，CARs 中的一條關(guān)聯(lián)規(guī)則表示為r，某個(gè)聚類的待分類樣本表示為S。分類器構(gòu)造的基本思想是挑選r 中優(yōu)先級較高的規(guī)則，使之能夠完整覆蓋S。最終形成的分類器形如:

其中，〈ri，r2，...，rn〉左邊的優(yōu)先級高于右邊，且分類器中不存在缺省類。

若規(guī)則ri和rj滿足以下任一條件，則ri的優(yōu)先級高于rj，記為ri＞rj。

分類器構(gòu)造的步驟如下:

1)按照優(yōu)先級對關(guān)聯(lián)規(guī)則進(jìn)行排序。

2)依次挑選CARs 中的關(guān)聯(lián)規(guī)則加入R 中。根據(jù)關(guān)聯(lián)規(guī)則優(yōu)先級高低，用每條關(guān)聯(lián)規(guī)則檢測待分類樣本S，刪除S 中被r 覆蓋的樣本，如果r 能夠覆蓋至少一個(gè)待分類樣本，則將r 加入到R 中。

3)當(dāng)CARs 中規(guī)則遍歷完或不再有待分類樣本時(shí)，結(jié)束規(guī)則選擇過程。

3 實(shí)驗(yàn)與對比分析

3.1 實(shí)驗(yàn)環(huán)境

1)硬件環(huán)境。

實(shí)驗(yàn)的計(jì)算服務(wù)器使用曙光TC4600 刀片服務(wù)器，每臺刀片的CPU 為16 核，內(nèi)存32 G，存儲為SAS硬盤300 G;交換機(jī)使用SummitX460-48t-10G 千兆交換機(jī)，背板帶寬320 Gpbs。

2)分布式環(huán)境。

分布式環(huán)境使用Spark 1.0.1，部署模式為Standalone 模式，1 個(gè)Master 節(jié)點(diǎn)，3 個(gè)Worker 節(jié)點(diǎn)，見表1。Worker 節(jié)點(diǎn)上部署HDFS，用于存放數(shù)據(jù)。Worker 節(jié)點(diǎn)都可以用于分布式計(jì)算，并行最小粒度為1 CPU，所以該環(huán)境支持最高的并行度為36。

表1 分布式環(huán)境

3.2 實(shí)驗(yàn)數(shù)據(jù)

為了測試本文提出的基于lazy 方法的分布式關(guān)聯(lián)分類算法的性能，本文選用第一屆全國高校云計(jì)算創(chuàng)新應(yīng)用大賽K-頻繁項(xiàng)集挖掘并行算法使用數(shù)據(jù)集，用于本文算法時(shí)，隨機(jī)給數(shù)據(jù)添加類別標(biāo)識。由于本文提出的算法主要在提升算法效率，所以添加標(biāo)識的做法并不會影響實(shí)驗(yàn)結(jié)果的可信度。由于實(shí)驗(yàn)數(shù)據(jù)在HDFS 中的分片數(shù)目為15，所以本文的實(shí)驗(yàn)的并行度為15。實(shí)驗(yàn)數(shù)據(jù)表如表2 所示。

表2 實(shí)驗(yàn)數(shù)據(jù)

3.3 結(jié)果與分析

為了驗(yàn)證分布式投影對算法性能的提升，在不同minSup 下，從數(shù)據(jù)集中任意抽取5 條待分類規(guī)則，對分布式投影的DLAC 算法與傳統(tǒng)DLAC 算法的性能比較。同一支持度下的算法耗時(shí)為5 次耗時(shí)的平均值。算法設(shè)定的minConf 為60%。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 分布投影的DLAC 與傳統(tǒng)DLAC 性能比較

為了驗(yàn)證待分類樣本聚合對算法性能的提升，本文對比了不同待分類樣本數(shù)量下使用聚合方法的DLAC 算法與傳統(tǒng)DLAC 算法的性能。算法設(shè)定的minSup 為20%，minConf 為60%。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 PDLAC、使用聚合方法的DLAC 與傳統(tǒng)DLAC 性能比較

從圖4 中可以看出，在不同的minSup 下，使用分布式投影能夠很好地提升DLAC 算法的性能，但性能提升的幅度隨著minSup 的減小而遞減。分布式投影能夠提升性能主要是因?yàn)榉植际酵队跋啾却型队坝兄阅艿奶嵘?。性能提升幅度遞減是因?yàn)橥队安僮髦贿M(jìn)行一次，而隨著最小支持度的減少，候選規(guī)則集會非線性增大，分布式投影的性能提升對比候選規(guī)則集挖掘的時(shí)間比重越來越低。

從圖5 中可以看出，使用聚合方法的DLAC 算法的性能遠(yuǎn)高于傳統(tǒng)的DLAC 算法，主要是因?yàn)榫酆鲜沟脻M足條件的待分類樣本使用同一個(gè)分類器，大大減少了對每個(gè)待分類構(gòu)建一個(gè)分類器的時(shí)間。PDLAC算法所用的時(shí)間遠(yuǎn)小于DLAC 算法，因?yàn)镻DLAC 算法集合了分布式投影與聚合方法的優(yōu)點(diǎn)。隨著待分類樣本數(shù)目的增加，PDLAC 算法性能提升越大，因?yàn)榇诸悩颖驹蕉?，能夠使用同一分類器進(jìn)行的分類的待分類樣本越多，相比對每個(gè)待分類樣本構(gòu)建一個(gè)分類器，時(shí)間節(jié)省越多。

圖4、圖5 的結(jié)果表明本文提出的算法——PDLAC 算法更加優(yōu)越，不僅解決了分布式關(guān)聯(lián)規(guī)則挖掘算法應(yīng)用于lazy 關(guān)聯(lián)分類時(shí)的不足，也解決了lazy 關(guān)聯(lián)分類本身存在的對多個(gè)待分類樣本分類時(shí)效率低的問題。

4 結(jié)束語

本文提出了一種改進(jìn)型的分布式lazy 關(guān)聯(lián)分類PDLAC 算法，使用聚合方法與分布式投影改進(jìn)傳統(tǒng)的DLAC 算法。實(shí)驗(yàn)結(jié)果分析表明，PDLAC 算法相比傳統(tǒng)的DLAC 算法，性能有著較大幅度的提升。對滿足條件的多個(gè)待分類樣本進(jìn)行聚合，有效地解決lazy 關(guān)聯(lián)分類算法對多個(gè)待分類樣本進(jìn)行分類的效率問題;分布式投影解決了分布式關(guān)聯(lián)規(guī)則挖掘算法應(yīng)用于lazy 關(guān)聯(lián)分類時(shí)的不足。

下一步的工作是繼續(xù)研究PDLAC 算法在待分類樣本沒有顯著關(guān)聯(lián)情況下的性能，并進(jìn)一步改進(jìn)算法使之適合待分類樣本沒有顯著關(guān)聯(lián)的情況。

［1］Thabtah F.A review of associative classification mining［J］.The Knowledge Engineering Review，2007，22(1):37-65.

［2］Veloso A，Meira W，Zaki M J.Lazy association classification［C］// Proc.of the 6th IEEE International Conference on Data Mining.2006:645-654.

［3］Liu Bing，Hsu W，Ma Yiming.Integrating classification and association rule mining［C］// Proc.of the 4th International Conference on Knowledge Discovery and Data Mining.1998:80-86.

［4］Li Wenmin，Han Jiawei，Pei Jian.CMAR:Accurate and efficient classification based on multiple class-association rules［C］// Proc.of IEEE International Conference on Data Mining.2001:369-376.

［5］Baralis E，Chuusano S，Garza P.A lazy approach to associative classification［J］.IEEE Transactions on Knowledge and Data Engineering，2008，20(2):156-171.

［6］李學(xué)明，付萌，李賓飛.基于混合策略的關(guān)聯(lián)分類方法［J］.計(jì)算機(jī)應(yīng)用，2013，30(3):724-727.

［7］李學(xué)明，李賓飛，楊濤，等.基于lazy 方法的數(shù)量型關(guān)聯(lián)分類［J］.計(jì)算機(jī)應(yīng)用，2013，33(8):2184-2187.

［8］Symth P，Goodman R M.An information theoretic approach to rule induction from databases［J］.IEEE Transaction on Knowledge and Data Engineering，1992，4(4):301-316.

［9］Cheung D W，Ng V T，F(xiàn)u A W.Efficient mining of association rules in distributed database［J］.IEEE Transactions on Knowledge and Data Engineering，1996，8(6):911-922.

［10］王越.分布式關(guān)聯(lián)規(guī)則挖掘的方法研究［D］.重慶:重慶大學(xué)，2003:17-18.

［11］張春生，李艷，莊麗艷，等.基于局部性原理的分布式關(guān)聯(lián)規(guī)則挖掘算法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48(21):143-145.

［12］Friedman J，Kohavi R，Yun Y.Lazy decision trees［C］//Proc.of the 13rd National Conference on Art Intelligence.1996:717-724.

［13］Wang Ke，Zhou Senqiang，He Yu.Growing decision trees on support-less association rules［C］// Proc.of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2000:265-269.