丁祥武 譚 佳 王 梅

(東華大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201620)

?

一種分類數(shù)據(jù)聚類算法及其高效并行實(shí)現(xiàn)

丁祥武 譚 佳 王 梅

(東華大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201620)

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

分類數(shù)據(jù) CLOPE p-CLOPE RW-CLOPE Spark

0 引 言

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

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

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

1 相關(guān)工作

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

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

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

2 CLOPE算法

分類數(shù)據(jù)的聚類算法CLOPE以簇的直方圖的高寬比作為全局評估函數(shù)(也稱全局收益函數(shù))，隨著每個(gè)簇中記錄重合度的增多，簇內(nèi)的統(tǒng)計(jì)直方圖的高寬比也逐漸增加。當(dāng)簇集的統(tǒng)計(jì)直方圖高寬比之和達(dá)到最大時(shí)，所對應(yīng)的聚類結(jié)果被認(rèn)為是最優(yōu)的聚類。

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

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

(1)

(2)

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

(3)

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

算法1 CLOPE算法

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

(1) while未到數(shù)據(jù)集尾部

(2) 讀下一條記錄;

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

(4) 將寫回?cái)?shù)據(jù)集;

/* 第2階段：迭代 */

(5)repeat

(6) moved = false;

(7) while未到數(shù)據(jù)集尾部

(8) 讀一條記錄;

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

(10) ifCi≠Cj

(11) 將寫回?cái)?shù)據(jù)集;

(12) moved = true;

(13) endif;

(14) until moved=false;

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

3 RW-CLOPE算法

3.1 對數(shù)據(jù)“洗牌”

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

圖1 “洗牌”模型流程圖

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

在算法每一輪的迭代過程中，都對上一輪輸出的最優(yōu)聚類數(shù)據(jù)集，利用“洗牌”模型按記錄粒度對數(shù)據(jù)集進(jìn)行打亂。使RW-CLOPE能夠從記錄粒度的隨機(jī)順序集中選擇最優(yōu)的聚類，幾乎完全排除了數(shù)據(jù)的輸入順序?qū)е碌木垲愘|(zhì)量不穩(wěn)定問題，從而在算法收斂時(shí)，能取得全局最優(yōu)聚類。

3.2 屬性維加權(quán)

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

表1 分類數(shù)據(jù)簇

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

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

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

(4)

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

(5)

根據(jù)特征T的信息熵，計(jì)算其對應(yīng)的權(quán)值Wj:

(6)

3.3 RW-CLOPE算法

本文提出了一種基于隨機(jī)順序迭代和屬性加權(quán)的新分類數(shù)據(jù)聚類方法RW-CLOPE。首先利用“洗牌”模型將數(shù)據(jù)集進(jìn)行隨機(jī)化打亂，然后對不同順序的數(shù)據(jù)集進(jìn)行聚類，選擇收益值最大的聚類作為最優(yōu)聚類，從而排除了輸入數(shù)據(jù)順序?qū)е碌木垲惒环€(wěn)定性問題；其次，根據(jù)每一維屬性對聚類貢獻(xiàn)度的不同，給每一維屬性賦予不同的權(quán)值并提出一個(gè)新的全局評估函數(shù)，其定義如下：

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

(7)

(8)

此時(shí)，該算法的全局評估函數(shù)為：

(9)

其中r為簇內(nèi)控制記錄相似度的排斥因子，L為簇的個(gè)數(shù)。

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

算法2 RW-CLOPE算法

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

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

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

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

(4) 讀取一條記錄

(5) 根據(jù)profit最大化原則，將記錄t放入已有或新建的第i個(gè)簇中，更新簇對應(yīng)的權(quán)值向量

(6) 將記錄寫回?cái)?shù)據(jù)集Di

/*第2階段：迭代 */

(7)while(not convergence)

(8) repeat

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

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

(11) 從Di中讀一條記錄

(12) moved = false;

(13) 將記錄移動(dòng)到使profit最大的簇Cj中，同時(shí)更新簇對應(yīng)的權(quán)值向量

(14) ifCi≠Cj

(15) 將記錄寫回?cái)?shù)據(jù)集Dk

(16) moved = true;

(17) endif;

(18) 選擇收益值最優(yōu)的聚簇及對應(yīng)的數(shù)據(jù)集Dm

(19)until moved=false

3.4 并行實(shí)現(xiàn)

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

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

圖2 RW-CLOPE執(zhí)行流程圖

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

3.5 時(shí)間與空間復(fù)雜度

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

4 實(shí)驗(yàn)與分析

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

實(shí)驗(yàn)所使用的p-CLOPE實(shí)現(xiàn)代碼來自文獻(xiàn)[8]，CLOPE算法代碼是嚴(yán)格地按照文獻(xiàn)[1]的思想進(jìn)行實(shí)現(xiàn)的。CLOPE運(yùn)行在單機(jī)上，p-CLOPE算法與RW-CLOPE算法分別運(yùn)行在由7臺(tái)單機(jī)搭建的Hadoop及Spark集群上，每個(gè)節(jié)點(diǎn)的配置為8 GB的內(nèi)存，i7處理器。

4.1 蘑菇數(shù)據(jù)集

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

以下分別在數(shù)據(jù)集份數(shù)d取不同值的條件下用RW-CLOPE、CLOPE執(zhí)行聚類，用本文提出的profit作為衡量聚類質(zhì)量的指標(biāo)進(jìn)行測試，實(shí)驗(yàn)結(jié)果如圖3所示。其中X軸為排斥因子，Y軸為RW-CLOPE、CLOPE對應(yīng)的profit的比值。

圖3 蘑菇數(shù)據(jù)集RW-CLOPE與CLOPE對比圖

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

圖4 蘑菇數(shù)據(jù)集p-CLOPE實(shí)驗(yàn)對比圖

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

4.2 大豆疾病數(shù)據(jù)集

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

圖5 大豆疾病數(shù)據(jù)集實(shí)驗(yàn)對比圖

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

4.3 美國人口普查數(shù)據(jù)集

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

圖6 美國人口普查數(shù)據(jù)集

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

在這組百萬數(shù)據(jù)集下，我們還比較了p-CLOPE算法與RW-CLOPE算法在d取不同值時(shí)的執(zhí)行時(shí)間。其中X軸坐標(biāo)為排斥因子r，r的取值2.9、3.1、3.3、3.5，因?yàn)樵趐-CLOPE算法的實(shí)驗(yàn)結(jié)果中，r取這四個(gè)取值時(shí)對應(yīng)的聚類結(jié)果最優(yōu)。Y軸為RW-CLOPE與p-CLOPE的執(zhí)行時(shí)間比，實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 執(zhí)行時(shí)間對比圖

從圖7中我們可以看到，d數(shù)值越大，RW-CLOPE與p-CLOPE的執(zhí)行時(shí)間的比值也越大。這主要的原因是，p-CLOPE在中間結(jié)果上的時(shí)間開銷隨著d的增大而增大，由于受到實(shí)驗(yàn)環(huán)境的限制，這個(gè)實(shí)驗(yàn)中d的最大取值為720。

5 結(jié) 語

本文提出了一種基于隨機(jī)順序迭代和屬性加權(quán)的新分類數(shù)據(jù)聚類方法——RW-CLOPE。在聚類質(zhì)量方面，首先利用“洗牌”模型對數(shù)據(jù)集的順序進(jìn)行隨機(jī)化打亂，提高聚類質(zhì)量的穩(wěn)定性。其次，根據(jù)分類數(shù)據(jù)的信息熵給不同的屬性維賦予不同的權(quán)值來區(qū)分其對聚類質(zhì)量的貢獻(xiàn)度，極大程度上提高了聚類的質(zhì)量。在實(shí)現(xiàn)上，RW-CLOPE算法在Spark平臺(tái)上進(jìn)行了實(shí)現(xiàn)，使其能快速的處理海量數(shù)據(jù)。在3個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，RW-CLOPE算法比p-CLOPE算法取得更優(yōu)的聚類結(jié)果，處理海量數(shù)據(jù)時(shí)有更好的擴(kuò)展性。

[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] 彭雅麗,章志明,余敏.一種改進(jìn)的CLOPE算法在入侵檢測中的應(yīng)用[J].微計(jì)算機(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] 丁祥武,郭濤,王梅.一種大規(guī)模分類數(shù)據(jù)聚類算法及其并行實(shí)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展,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。上海市信息化發(fā)展資金項(xiàng)目(XX-XXFZ-05-16-0139)。丁祥武，副教授，主研領(lǐng)域：大數(shù)據(jù)和列存儲(chǔ)技術(shù)，分布式處理，多核及眾核并行技術(shù)。譚佳，碩士。王梅，教授。

TP312

A

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