一種分類數據聚類算法及其高效并行實現

丁祥武 譚 佳 王 梅

(東華大學計算機科學技術學院 上海 201620)

?

一種分類數據聚類算法及其高效并行實現

丁祥武 譚 佳 王 梅

(東華大學計算機科學技術學院 上海 201620)

針對大規模、高維、稀疏的分類數據聚類，CLOPE算法相比于傳統的聚類算法在聚類質量及運行速度上都有很大的提升。然而CLOPE算法存在聚類的質量不穩定、沒有區分每維屬性對聚類的貢獻度、需要預先指定排斥因子r等問題。為此，提出基于隨機順序迭代和屬性加權的分類數據聚類算法(RW-CLOPE)。該算法利用“洗牌”模型對原始數據進行隨機排序以排除數據輸入順序對聚類質量的影響。同時，根據信息熵計算各個屬性的權重，以區別每維屬性對聚類的貢獻度，極大地提升了數據聚類的質量。最后，在高效的集群平臺Spark上，實現了RW-CLOPE算法。在三個真實數據集上的實驗結果表明：在數據集亂序后的份數相同時，RW-CLOPE算法比p-CLOPE算法取得更好的聚類質量。對蘑菇數據集，當CLOPE算法取得最優聚類結果時，RW-CLOPE比CLOPE取得高68%的收益值，比p-CLOPE取得高25%的收益值；針對大量數據，基于Spark的RW-CLOPE算法比基于Hadoop的p-CLOPE算法執行時間更短；計算資源充足時，隨機順序的數據集份數越多，執行時間的提升越明顯。

分類數據 CLOPE p-CLOPE RW-CLOPE Spark

0 引 言

目前，針對數值型數據的聚類算法雖然在不斷取得突破，但并不適合處理分類數據的聚類。分類數據在零售業、電子商務、醫療診斷、生物信息學等領域都有大量的應用。與數值型數據相比，分類數據的屬性值取自一個有限的離散的符號集合，如DNA序列數據以4種不同的符號A、T、G和C編碼，因此分類數據間的相似度量的定義更加困難。現有的數值型數據的聚類方法和工具難以直接應用于分類數據聚類，因此，研究分類數據的聚類算法具有重要的學術意義和應用前景。

在現有的分類數據聚類算法中，CLOPE[1]算法以其實現思想簡單、收斂速度快、聚類質量優等特點受到學術界的關注。自2004年由Yang等提出后，CLOPE算法被應用于數據流聚類、日志分析、入侵檢測等多個領域[2-4]，成為了當前主流的分類數據聚類算法之一。CLOPE算法根據簇直方圖的高寬比來表示這個簇內記錄的重疊程度并提出一個全局聚類指標用來評估聚簇的質量。與典型的分類數據聚類算法ROCK[5]、LargeItem[6]相比，CLOPE在單機上對同一份數據集進行聚類的運行速度快于LargeItem和ROCK，聚類質量優于LargeItem。盡管CLOPE算法的聚類質量及運行速度優于傳統聚類算法，但還存在一些缺陷，如需要預先指定排斥因子r、聚類的質量不穩定、 沒有區分各屬性對聚類的貢獻度差異等。聚類質量上的不足主要表現在兩個方面：1) 對內部排列順序不同的數據，CLOPE算法對應的聚類質量也不同。2) 當CLOPE用于非交易數據聚類時，忽視了屬性維權值對聚類質量的影響。針對這些問題，已經有學者提出了CLOPE的一些改進算法，如Li等[7]提出了一種修正的劃分模糊度，來實現對算法中排斥因子r的自動優選。丁祥武等[8]基于MapReduce平臺，提出了等分劃分再排列的思想，對不同輸入順序的數據進行聚類，再從中選出最優聚類，一定程度上降低了數據集順序對聚類質量的影響。但是，上述的改進工作存在如下不足：在聚類質量的穩定性上，p-CLOPE算法對數據集的打亂程度依賴于劃分后的塊數。當塊數較少時，數據的打亂程度低，無法取得最優的聚類結果；當劃分的塊數較大時，數據雖然打亂程度高，但花費了巨大的時間開銷。更為重要的是FUZZY CLOPE與p-CLOPE算法對非交易數據集進行聚類時，默認數據集中每一維的屬性對聚類的貢獻程度相同。然而現有研究表明，每一維屬性對聚類的貢獻程度是不一致的，給每一維屬性設置不合適的權值將很大程度上影響算法的聚類質量。

本文提出了一種基于隨機順序迭代和屬性加權的新分類數據聚類方法RW-CLOPE。該方法具體如下：首先利用“洗牌”模型，將待聚類的數據集進行隨機化打亂，幾乎完全克服了CLOPE算法的聚類質量受數據集內部排列順序的影響。在此基礎上，RW-CLOPE算法根據數據的信息熵，計算每一維屬性相應的權值以區分其對聚類的貢獻度。在實現上，利用Spark平臺的特性，設計了基于Spark的算法，改善了p-CLOPE算法的擴展性不足問題。在3個真實數據集上的實驗結果表明，與現有算法相比，該算法在聚類質量和聚類效率上有明顯的提升。

1 相關工作

依據是否為聚類過程定義顯式的目標優化函數，現有的分類數據聚類方法可以劃分為兩類。以層次聚類為代表的第1類方法，其目的是構造層次聚類樹，因而沒有必要顯式地定義聚類目標函數，其代表性算法包括凝聚性算法ROCK和分裂型算法DHCC等[9]。此類算法具有較高的算法復雜度，通常達到O(N2logN)。第2類算法的主要代表是基于分割熵或頻度統計信息定義聚類目標函數，然后定義用于優化目標函數的聚類搜索算法，其代表性算法包括基于熵的分類數據聚類算法[10]EBC(entropy-based categorical clustering)。該類算法通常使用蒙特卡羅抽樣法[11]實現聚類優化，具體實現為：隨機選擇一個對象，將其移動到另一個簇，使得移動之后的劃分具有更高的聚類質量(優化目標函數值)，重復這個過程直到目標函數值不再改變為止。因此，此類算法通常需通過大量的迭代來完成聚類。

依據聚類方式，現有分類數據的聚類算法可分為基于劃分的聚類算法和基于層次的聚類。1998年Huang等對k-means算法進行擴展，提出了針對分類數據的k-modes聚類算法[12]。該算法對k-means算法進行了3點擴展：引入了針對分類數據的相似性度量(簡單的0-1匹配)；使用modes代替means；在聚類的過程中使用基于頻度的方法修正modes，以使得聚類代價最小化。但是該算法經過有限次迭代后僅能收斂于局部最優值，其次，聚類結果依賴于初始的modes的選擇且modes不具有唯一性。1999年Huang等對Fuzzy k-means進行擴展，提出了針對分類數據的Fuzzy k-modes算法[13]。該算法使每個對象到所有的類有一個隸屬程度，由隸屬度構成的模糊劃分矩陣不僅可以為用戶提供更多的信息去決定最終的類，而且容易識別邊界對象，但是Fuzzy k-modes與k-modes算法一樣只能達到局部最優。為了尋找一個使模糊目標函數值最小且合適的模糊隸屬矩陣，Gan等將Fuzzy k-modes算法作為一個優化問題去處理，提出的Gentic fuzzy -modes算法[14]在UCI的標準數據集上進行測試，實驗結果表明，提出的算法在識別分類數據集中固有的類結構方面非常有效。1999年Guha等提出ROCK算法[5]，該算法的基本思想是首先對數據進行抽樣，根據相似度閾值和共享近鄰的概念構造一個凝聚的層次聚類算法，得到樣本集的聚類后再對整個數據集進行聚類。ROCK算法將共享近鄰數的全局信息作為評價數據點之間相關性的度量，而不是傳統的基于兩點間距離的局部度量函數。LargeItem算法[6]通過迭代優化一個全局評估函數來實現對大量分類數據的聚類，但其最小支持度θ和權重w很難確定。2004年Yang等提出了基于直方圖的聚類算法CLOPE[1]，用簇直方圖中的高寬比來表示這個簇內交易的重疊程度并提出一個全局聚類指標來評估聚簇的質量。

為了區別不同屬性對聚類貢獻程度的差異，從而提高聚類結果的質量，在數值聚類領域已經應用自動屬性加權技術。這種技術賦予每個屬性一個類依賴的權重并在聚類過程中給予優化，達到自動特征選擇的目的。由此對現有分類數據聚類方法又可以分為兩類：一類根據記錄到modes的平均距離來賦予屬性權重的方法，如：WKM算法[15]；另一類根據modes的頻度來計算權重的方法，如DHCC算法等。在這類方法中，權值的設定只依賴于modes，沒有考慮屬性值的總體分布，因而導致屬性在權重計算上的偏差，從而影響聚類結果的質量。譬如屬性項Atrribute1(A,A,T,T,G)與屬性項Atrribute2(T,A,C,G,G)在DHCC算法中將被賦予兩個相同的權重，然而這個結果與事實不符。Atrribute2上屬性值的分布比Atrribute1更密集，對簇的貢獻度更大，所以二者對簇的貢獻度應該給以區別。為了避免因為忽略屬性的非modes信息而導致的權值計算偏差，另一種加權方法即根據分類屬性值的總體分布情況賦予屬性維的權值，如基于信息論中熵概念的加權方法[16]。

2 CLOPE算法

分類數據的聚類算法CLOPE以簇的直方圖的高寬比作為全局評估函數(也稱全局收益函數)，隨著每個簇中記錄重合度的增多，簇內的統計直方圖的高寬比也逐漸增加。當簇集的統計直方圖高寬比之和達到最大時，所對應的聚類結果被認為是最優的聚類。

定義1[1]分類數據集D是一組記錄的集合{t1,t2,…,tn}。每條記錄是一些屬性項的集合{i1,i2,…,im}。聚類集合{C1,C2,…,Ck}是{t1,t2,…,tn}的一個劃分，也就是說C1∪…∪Ck={t1,t2,…,tn}而且對任意1 ≤i≤k，滿足Ci≠?，且Ci∩Cj=?。每一個Ci叫作一個簇，n、m、k分別表示交易的條數、屬性項的個數和簇的個數。

給定一個簇C，可以找到這個簇中所有的不同屬性項，一個屬性項出現的頻率表示有多少條記錄包含這個屬性項。用D(C)表示簇C中不同屬性項的集合，用Occ(i,C)表示屬性項i在簇C中出現的頻率。這樣可以畫出簇C的直方圖，用X軸表示屬性項，用Y軸表示每個屬性項出現的頻率；一個簇C的直方圖的面積S(C)和寬度W(C)為：

(1)

(2)

簇的高度定義為H(C)=S(C)/W(C)，全局評估函數為：

(3)

其中，排斥因子r是一個正實數，用來控制簇內記錄的相似程度。當r較大時，簇內的記錄必須有較多的公共項；相反，較小的r可用來對稀疏數據分組。通過調整排斥因子r的大小可以得到不同的簇個數，r越大，簇的個數越多。對于每個確定的r都可以找到一個劃分C使得收益值Profit(C)最大。具體的算法如下：

算法1 CLOPE算法

/* 第1階段：初始化 */

(1) while未到數據集尾部

(2) 讀下一條記錄;

(3) 據profit最大化原則，將t放入已有或新建的第i個簇中;

(4) 將寫回數據集;

/* 第2階段：迭代 */

(5)repeat

(6) moved = false;

(7) while未到數據集尾部

(8) 讀一條記錄;

(9) 據profit最大化原則，將t放入已有或新建的簇Cj中;

(10) ifCi≠Cj

(11) 將寫回數據集;

(12) moved = true;

(13) endif;

(14) until moved=false;

CLOPE算法分為兩個階段：聚類生成階段與聚類調整階段。在第1階段，CLOPE依據數據集中記錄的順序依次入簇，得到初始聚類劃分。在第2階段每一輪迭代中，將前一輪得到的聚類作為下一輪的輸入，根據profit最大化的原則對前一輪得到的聚類進行調整，迭代結束時得到最終的聚類。由此，CLOPE算法得到的最終聚類依賴于第1階段的聚類，而第1階段的聚類，對同一數據集的不同輸入順序，得到的聚類是不同的。因此，CLOPE聚類的結果隨輸入順序的不同而不同。這個特點，使得CLOPE算法的聚類質量存在很大的隨機性。針對這個問題，p-CLOPE算法采用將待聚類數據集進行等分劃分再排列的方式進行順序打亂，然后對不同排列的數據進行CLOPE聚類，迭代的每一輪都選擇上一輪的最優聚類作為輸入并隨機打亂數據塊之間的順序后進行調整。迭代結束后，選擇最后一輪中的profit值最大的聚類作為最優聚類輸出。p-CLOPE算法雖然能緩解數據輸入順序對聚類質量的影響，但是數據輸入順序按劃分塊打亂，打亂程度不夠徹底，導致最后的聚類質量仍然受限即只能收斂于局部最優聚類。此外，在對非交易數據進行CLOPE聚類時，CLOPE算法默認每一維數據對聚類質量的貢獻程度是相同的，沒有考慮每一維數據對聚類貢獻的差異性。

3 RW-CLOPE算法

3.1 對數據“洗牌”

經分析，CLOPE算法存在聚類質量隨處理數據順序不同而變動的問題，其后p-CLOPE算法雖然考慮到輸入順序對聚類質量的影響，但是p-CLOPE算法通過對劃分塊進行全排序以打亂數據順序的粒度比較粗，使得無法得到最優聚類。為了解決這個問題，本文利用“洗牌”模型對數據按記錄粒度進行隨機化打亂。與等塊劃分再排列的打亂數據順序的方法相比，本文提出的隨機順序方法更徹底地消除了順序對聚類質量的影響。“洗牌”模型在處理每條記錄時，都是隨機從數據集中抽出一條記錄，與剩余數據集中的最后一條記錄交換，即把這個隨機抽取的記錄放到尚未處理數據集的最后一個位置。假設待聚類的數據集D為{x1,x2,x3,x4,x5},則執行一次“洗牌”模型的流程如圖1所示。

圖1 “洗牌”模型流程圖

對數據集D，執行一次“洗牌”模型的流程為：首先從數據集D中隨機選擇一條記錄如x3與D中的最后一條記錄x5交換，即將D中的最后輸入的一條記錄進行了隨機化處理。然后從未被隨機化的前4條記錄{x1,x2,x5,x4}中隨機抽取一條記錄如x2與最后一條記錄x4交換，再從{x1,x4,x5}中隨機抽取如x1與x5交換。最后將x4與x5交換，此時D中所有的記錄都進行了隨機化處理，至此完成了一次“洗牌”操作。

在算法每一輪的迭代過程中，都對上一輪輸出的最優聚類數據集，利用“洗牌”模型按記錄粒度對數據集進行打亂。使RW-CLOPE能夠從記錄粒度的隨機順序集中選擇最優的聚類，幾乎完全排除了數據的輸入順序導致的聚類質量不穩定問題，從而在算法收斂時，能取得全局最優聚類。

3.2 屬性維加權

在對非交易數據進行聚類時，CLOPE算法默認每個簇中的每一維數據對聚類貢獻度一致，忽略了屬性維對聚簇貢獻度的差異性。如表1中的3個分類屬性，易知它們的取值范圍為{A,T,C,G}，在Attribute1中A和T出現的頻率分別為0.4、0.4。在Attribute2中，A和T出現的頻率分別為0.8、0.2。其中，Attribute2對簇C1的貢獻度明顯比Attribute1更大。因此，在聚類時，應該考慮到不同的屬性維對聚類貢獻度的差異性。表1由5個數據對象組成的分類數據簇。

表1 分類數據簇

針對不同屬性維對聚類貢獻度不一致問題，本文依據屬性維的信息熵給不同維度的數據賦與不同的權值。熵是信息論中描述消息攜帶平均信息量的度量，熵越大不確定性越大，其對應的權值越小，反之，熵越小不確定也越小，對應的權值就越大。

假設數據第j維的特征T是一個離散型隨機變量T，其取值集合為T，則變量T的熵H(Tj)定義如下：

H(Tj)=-∑t∈Tp(t)lnp(t)

(4)

其中p(t)為屬性值t在集合T中出現的概率：

(5)

根據特征T的信息熵，計算其對應的權值Wj:

(6)

3.3 RW-CLOPE算法

本文提出了一種基于隨機順序迭代和屬性加權的新分類數據聚類方法RW-CLOPE。首先利用“洗牌”模型將數據集進行隨機化打亂，然后對不同順序的數據集進行聚類，選擇收益值最大的聚類作為最優聚類，從而排除了輸入數據順序導致的聚類不穩定性問題；其次，根據每一維屬性對聚類貢獻度的不同，給每一維屬性賦予不同的權值并提出一個新的全局評估函數，其定義如下：

定義2 令X={x1,x2,…,xn}表示待聚類的數據集，xi={i1,i2,…,im}表示第i個樣本，聚類后的簇集為C={C1,C2,…,CL}。用occ(i,j,C)表示屬性i在簇C中第j維出現的頻率，Oj為在第j維上屬性的集合，wj為簇中第j維屬性對應的權值，用D(Ck)表示簇Ck中所有屬性項取值的集合。定義直方圖的面積S(Ck)及寬度W(Ck)如下：

(7)

(8)

此時，該算法的全局評估函數為：

(9)

其中r為簇內控制記錄相似度的排斥因子，L為簇的個數。

RW-CLOPE算法通過比較前后兩輪迭代的收益值來判斷算法是否收斂，并將每一輪最優聚類對應的數據集作為下一輪迭代的輸入數據集。隨著迭代次數的增加，profit值也不斷增加并最終趨于一個穩定值，當profit值不再變時，我們認為profit值取到全局最優，即聚類質量達到全局最優。其中RW-CLOPE算法的首輪迭代大致分為兩個階段：初始化及迭代階段。在初始化階段，利用“洗牌”模型生成預定義份數的數據，對每一份隨機順序根據profit最大化的原則得到初始聚類。在迭代階段，根據profit最大化的原則對第一階段得到的每份初始聚類進行調整，針對每一份隨機順序都得到一個最優聚類，然后選擇profit值最大的聚類作為本輪的最優聚類。在后續的每輪迭代中，通過洗牌模型對數據進行打亂，然后根據打亂后的記錄順序，對前一輪的最優聚類劃分進行調整，直至算法收斂。具體的算法如下：

算法2 RW-CLOPE算法

/* 第1階段：初始化 */

(1)通過“洗牌”將原始數據順序打亂，得到n份不同隨機順序的數據集D={D1,D2,…,Dn}，n為用戶定義的數據份數

(2)forDk∈{D1,D2,…,Dn}

(3) whileDk中有未被讀取的記錄

(4) 讀取一條記錄

(5) 根據profit最大化原則，將記錄t放入已有或新建的第i個簇中，更新簇對應的權值向量

(6) 將記錄寫回數據集Di

/*第2階段：迭代 */

(7)while(not convergence)

(8) repeat

(9) forDk∈{D1,D2,…,Dn}

(10) whileDk中有未被讀取的記錄

(11) 從Di中讀一條記錄

(12) moved = false;

(13) 將記錄移動到使profit最大的簇Cj中，同時更新簇對應的權值向量

(14) ifCi≠Cj

(15) 將記錄寫回數據集Dk

(16) moved = true;

(17) endif;

(18) 選擇收益值最優的聚簇及對應的數據集Dm

(19)until moved=false

3.4 并行實現

從3.3節可知，RW-CLOPE算法的每一輪迭代都先將輸入數據集隨機打亂成d(預定義值)份數據集，然后分別對不同順序的數據集進行聚類。再將該輪迭代的最優聚類劃分作為下一輪迭代的輸入，反復迭代，直至得到最優的聚類劃分。在串行實現中，算法的每一輪迭代都需要重復的執行“洗牌”操作和加權CLOPE聚類，以得到d份順序不同的數據集及d份數據集對應的最優聚類。為了提升算法的執行效率，本文將前后無關聯的任務分布地運行在不同節點上。在數據變序階段，通過廣播將輸入數據集的信息發送至每個節點，然后并行的在每個節點上執行“洗牌”操作，最后得到d份與輸入數據集順序不同的數據集。此后，將每一份數據的加權CLOPE操作放在不同計算單元上獨立完成，而比較全局收益值的計算統一放在一個計算單元上處理。在這個過程中，先并行打亂數據順序再并行計算最后全局比較收益值的大小，為并行聚類的實現提供了可能性。

我們在分布式基礎架構Spark上實現了RW-CLOPE算法，使用HDFS存儲數據，利用Spark中RDD的操作執行算法的并行化。具體來說，首先將待聚類的數據集D以指定的文本格式上傳到HDFS，通過Spark的廣播機制將數據集D信息分發到不同節點。然后在不同的節點上并行地執行“洗牌”操作，得到d份順序不同的數據集。其中，每得到一份數據集便將其分發到一個Map任務進行一輪迭代的聚類。等所有Map任務結束后，通過一次Reduce過程，比較d份數據集的收益值，選取收益值最大的數據集作為下次迭代的輸入數據。依次迭代，當最優聚類中的所有記錄都沒有移動時，聚類過程結束，即得到為全局最優聚類劃分。執行流程如圖2所示。

圖2 RW-CLOPE執行流程圖

在數據變序階段，與p-CLOPE算法中在單節點上進行數據的所有打亂操作相比，RW-CLOPE利用Spark中RDD的并行化操作，并行的執行“洗牌”模型，使其以較小的時間代價得到離散程度更為徹底的隨機數據。此外，RW-CLOPE算法是基于Spark平臺實現的，相比較于Hadoop平臺將中間結果存入硬盤的方法，Spark將中間結果或常用數據存入內存，很大程度上減小了算法在中間結果上的時間開銷。

3.5 時間與空間復雜度

CLOPE算法一次迭代的時間復雜度是O(N×K×A)，空間復雜度為O(M×K)。其中A是每天記錄的平均長度，N是總的記錄數，K是簇的個數,M為維度。與CLOPE算法相比，在每一輪迭代中，RW-CLOPE需要通過“洗牌”操作得到d份順序不同的數據集，然后對d份數據集分別進行聚類操作。其中“洗牌”操作每執行一次的時間復雜度為O(N)，所以RW-CLOPE算法每一輪迭代的時間復雜度為O(d×N2×K×A)，空間復雜度與CLOPE相當。RW-CLOPE算法在每輪迭代后都選出本輪的最優聚類作為下一輪迭代的輸入，所以能以更少的迭代次數達到收斂。

4 實驗與分析

本文主要的貢獻有如下3個方面：首先利用“洗牌”模型隨機地打亂數據集的排列順序，再對不同順序的數據集進行聚類，選擇profit值最大的聚類作為最優聚類，克服了CLOPE算法受數據集順序而導致的聚類質量不穩定問題。其次，根據每一維數據的信息熵，為每一維數據引入權值并將權值的更新自動化，極大程度上提升了聚類的質量。最后，在實現上，結合Spark平臺的特性，使其能高效地處理海量數據。本文實驗對比的對象為CLOPE算法及其同類算法p-CLOPE。實驗采用的3組數據集分別是蘑菇數據集、大豆疾病數據集以及美國人口普查數據集。在前兩個數據集中，主要比較了聚類質量。由于美國人口普查數據集規模較大，在該數據集中分別從聚類質量，時間性能兩個方面進行比較。實驗采用本文定義的全局收益值函數profit作為聚類質量評估指標，其數值越大，表明聚類質量越高。其中，CLOPE與p-CLOPE在計算profit時，默認每維屬性的權重相等，權值為1/維度。

實驗所使用的p-CLOPE實現代碼來自文獻[8]，CLOPE算法代碼是嚴格地按照文獻[1]的思想進行實現的。CLOPE運行在單機上，p-CLOPE算法與RW-CLOPE算法分別運行在由7臺單機搭建的Hadoop及Spark集群上，每個節點的配置為8 GB的內存，i7處理器。

4.1 蘑菇數據集

蘑菇數據集(Mushroom)也是原CLOPE算法測試過的數據集，來自加州大學歐文分校機器學習庫，包含記錄數為8 124，其中每條交易由22個屬性組成，根據是否可食用分為兩個類別。所有的屬性項共有116個不同的值，其中2 480個缺失屬性值用問題號‘?’表示。

以下分別在數據集份數d取不同值的條件下用RW-CLOPE、CLOPE執行聚類，用本文提出的profit作為衡量聚類質量的指標進行測試，實驗結果如圖3所示。其中X軸為排斥因子，Y軸為RW-CLOPE、CLOPE對應的profit的比值。

圖3 蘑菇數據集RW-CLOPE與CLOPE對比圖

從圖3中可知，RW-CLOPE算法的聚類質量明顯優于CLOPE，即經過“洗牌模型”及數據維加權這兩個步驟后，算法的聚類質量得到了明顯的提升。因此，下文中的實驗，我們只將RW-CLOPE與CLOPE的同類改進算法p-CLOPE進行比較。實驗中排斥因子r步長0.2，取值為1.1～3.9，d的取值為1、2、6、24、120、720對應于p-CLOPE算法中p取1～6時產生的數據份數，其實驗結果如圖4所示。

圖4 蘑菇數據集p-CLOPE實驗對比圖

從圖4中可以看出在d取不同值時，大多情況下RW-CLOPE與p-CLOPE profit的比值均大于1，即RW-CLOPE的聚類質量優于p-CLOPE。在文獻[1]中，CLOPE算法的聚類質量在r=3.1時取得最佳值。在文獻[8]中，當r=3.1時，p-CLOPE的收益值相對于CLOPE提升了35.1%。如圖4所示，本文實驗中RW-CLOPE在相同的條件下(r=3.1，p=4)，收益值比p-CLOPE大25%。

4.2 大豆疾病數據集

大豆疾病數據集(Soybean)共307條記錄，每個記錄由35個屬性組成，根據疾病的種類，數據樣本被分為19類。數據來自加州大學歐文分校機器學習庫，分別用p-CLOPE與RW-CLOPE對其執行聚類，并比較d取不同值時的聚類收益值。實驗結果如圖5所示。

圖5 大豆疾病數據集實驗對比圖

對比圖4與圖5，我們發現在d相同時，大豆數據集對應的收益比值總體上小于蘑菇數據集對應的比值。這是因為RW-CLOPE與p-CLOPE的profit比值和數據集中的記錄數相關，當記錄較少時，數據通過等分再劃分得到的離散程度與通過“洗牌”模型得到的離散程度之間的區別小，因此這兩種打亂數據排序的方法對聚類的質量區別相差不大。此外，如圖5所示，在d取不同值時，RW-CLOPE與p-CLOPE的收益比值總體上大于1。這是因為RW-CLOPE算法考慮到屬性維對聚類結果存在貢獻度的區別性，因此根據屬性維的信息熵給賦予不同的權值，從而極大程度上提升了聚類的質量。

4.3 美國人口普查數據集

美國人口普查數據集是從1990年美國人口普查全樣本數據中按1%的比例抽取的公共使用微數據樣本。包含的記錄條數2 458 285，數據由祖先、族群、拉美族裔來源、行業職業、語言、出生地等領域的68個屬性組成。與前2個數據集相比，這個數據集的交易條數達到百萬級別。當數據打亂份數d取不同值時，分別用RW-CLOPE與p-CLOPE執行聚類，實驗結果如圖6所示。

圖6 美國人口普查數據集

在圖6中，d取值為6、24(即p-CLOPE中p的取值為3、4)時，對應的RW-CLOPE與p-CLOPE的收益比值大于d取值為1、2時的收益比值，這是因為d值越大對應的數據份數越多。論證了CLOPE算法的聚類質量受數據的輸入順序的影響。相比于蘑菇數據集的實驗結果，我們發現在d=24，排斥因子取較大值時(也是實際有意義的情況)。在數據份數相同時，美國人口普查數據集對應的RW-CLOPE與p-CLOPE的收益比值大于蘑菇數據集對應的收益比值，這是因為數據量越大，“洗牌”模型相對于原始的等分劃分再排列的方式對數據的打亂就越徹底，因此RW-CLOPE算法越趨近于全局最優聚類。在圖6中，當d=1時，收益比值總體上大于1，這說明在輸入順序一致的情況下，加權CLOPE算法的聚類質量高于沒加權CLOPE。

在這組百萬數據集下，我們還比較了p-CLOPE算法與RW-CLOPE算法在d取不同值時的執行時間。其中X軸坐標為排斥因子r，r的取值2.9、3.1、3.3、3.5，因為在p-CLOPE算法的實驗結果中，r取這四個取值時對應的聚類結果最優。Y軸為RW-CLOPE與p-CLOPE的執行時間比，實驗結果如圖7所示。

圖7 執行時間對比圖

從圖7中我們可以看到，d數值越大，RW-CLOPE與p-CLOPE的執行時間的比值也越大。這主要的原因是，p-CLOPE在中間結果上的時間開銷隨著d的增大而增大，由于受到實驗環境的限制，這個實驗中d的最大取值為720。

5 結 語

本文提出了一種基于隨機順序迭代和屬性加權的新分類數據聚類方法——RW-CLOPE。在聚類質量方面，首先利用“洗牌”模型對數據集的順序進行隨機化打亂，提高聚類質量的穩定性。其次，根據分類數據的信息熵給不同的屬性維賦予不同的權值來區分其對聚類質量的貢獻度，極大程度上提高了聚類的質量。在實現上，RW-CLOPE算法在Spark平臺上進行了實現，使其能快速的處理海量數據。在3個真實數據集上的實驗表明，RW-CLOPE算法比p-CLOPE算法取得更優的聚類結果，處理海量數據時有更好的擴展性。

[1] Yang Y,Guan X,You J.CLOPE:A fast and effective clustering algorithm for transactional data[C]//Proc of the 8th ACM SIGKDD Int Conference on Knowledge Discovery and Data Mining.New York:ACM,2002:682-687.

[2] Kok-Leong Ong,Wenyuan Li,Wee-Keong Ng.SCLOPE:An algorithm for clustering data streams of categorical attributes[C]//Knowledge-Based Intelligent Information and Engineering Systems,2004,3181:209-218.

[3] Li Y F,Le J J,Wang M,et al.MR-CLOPE:A Map Reduce based transactional clustering algorithm for DNS query log analysis[J].Journal of Central South University,2015,22(9):3485-3494.

[4] 彭雅麗,章志明,余敏.一種改進的CLOPE算法在入侵檢測中的應用[J].微計算機信息,2006,8(24):58-60.

[5] Guha S,Rastogi R,Shim K.ROCK:A robust clustering algorithm for categorical attributes[C]//Proc of the 15th Int Conference on Data Engineering(ICDE 1999).Los Alamitos,CA.IEEE Comuter Society,1999:23.

[6] Wang K,Xu C,Liu B.Clustering transactions using large items[C]//Proc of the 8th Int Conference on Information and Knowledge Management.New York:ACM,1999:10.

[7] Li Jie,Gao Xinbo,Jiao Licheng.Fuzzy CLOPE algorithm and its parameter optimalchoice[J].Control and Decision,2004,19(11):1250-1254.

[8] 丁祥武,郭濤,王梅.一種大規模分類數據聚類算法及其并行實現[J].計算機研究與發展,2016,53(5):1063-1071.

[9] Xiong T,Wang S,Mayers A,et al.DHCC:Divisive hierarchical clustering of categorical data[J].Data Mining and Knowledge Discovery,2012,24(1):103-135.

[10] Li T,Ma S,Ogihara M.Entropy-Based criterion in categorical clustering[C]//Brodley CE. Proc.of the 21st Int’1 Conference on Machine Learning.Banff:ACM Press,2004:68.

[11] Christian P,Dickman B H,Gilman M J.Monto Carlo optimization[J].Journal of Optimization Theory and Applications,1989,60(1):149-157.

[12] Huang Zhexue.Extensions to the k-means algorithms for clustering large data sets with categorical values[J].Data Mining and Knowledge Discovery,1998,2(3):283-304.

[13] Huang Zhexue,Ng M K.A fuzzy k-modes algorithm for clustering categorical data[J].IEEE Transactions on Fuzzy Systems,1999,7(4):446-452.

[14] Gan G,Wu J,Yang Z.A genetic fuzzy k-modes algorithm for clustering categorical data[J].Expert System with Application,2008,36(2):1615-1620.

[15] Chan E Y,Ching W K,Ng M K,et al.An optimization algorithm for clustering using weighted dissimilarity measures[J].Pattern Recognition,2003,37(5):943-952.

[16] Andritsos P,Tzerpos V.Evaluating value weight schemas in the clustering of categorical data[C]//1stWorkshop on Machine Learning and Intelligent Optimization(LION),2007.

A CLUSTERING ALGORITHM OF CATEGORICAL DATA AND ITS EFFICIENT PARALLEL IMPLEMENTATION

Ding Xiangwu Tan Jia Wang Mei

(CollegeofComputerScienceandTechnology,DonghuaUniversity,Shanghai201620,China)

For large-scale, high-dimensional, sparse categorical data clustering, compared with the traditional clustering algorithm, CLOPE has a great improvement in the quality of clustering and running speed. However, CLOPE has some defects such as clustering quality instability, not to distinguish the attribute clustering contribution between each dimension, need to specify rejection factor r in advance. Therefore, this paper proposes a clustering algorithm for categorical data based on random sequence iteration and attribute weight (RW-CLOPE). RW-CLOPE use the “shuffle” model to sort the raw data randomly to eliminate the effect of data input sequence on clustering quality. At the same time, based on the information entropy, the calculation method of attribute weights is proposed to distinguish the attribute clustering contribution between each dimension which greatly improve the quality of data clustering．Finally, the RW-CLOPE algorithm has been implemented on the efficient cluster platform—Spark. Experiments on three different and real data show that RW-CLOPE algorithm achieves better clustering quality than p-CLOPE algorithm when the number of disordered dataset is the same．For the mushrooms dataset, when CLOPE achieve optimal results, RW-CLOPE can achieve 68% higher profit value than CLOPE and 25% higher profit value than p-CLOPE．The execution time of RW-CLOPE algorithm is much shorter than p-CLOPE algorithm when dealing massive data．When the computational resources are sufficient, the more the number of data sets in, the more obvious the improvement of the execution time is.

Categorical data CLOPE p-CLOPE RW-CLOPE Spark

2016-08-18。上海市信息化發展資金項目(XX-XXFZ-05-16-0139)。丁祥武，副教授，主研領域：大數據和列存儲技術，分布式處理，多核及眾核并行技術。譚佳，碩士。王梅，教授。

TP312

A

10.3969/j.issn.1000-386x.2017.07.046