周 靖

（廣東石油化工學院計算機與電子信息學院 茂名 525000）

1 引言

混合條件屬性數(shù)據(jù)集是在同一個數(shù)據(jù)集中，同時存在分類條件屬性［1］和數(shù)值條件屬性［2］特征參數(shù)?；旌蠗l件屬性數(shù)據(jù)集的復雜性廣泛存在于實際應用領域中，如網(wǎng)絡入侵檢測、金融欺詐檢測、天氣預報、垃圾郵件識別等［3］。由于混合條件屬性包含的分類和數(shù)值特征參數(shù)的取值范圍、類別特性存在較大的差異，傳統(tǒng)針對單一條件屬性的聚類算法已不適合處理混合條件屬性對象，如何有效地規(guī)范混合條件屬性數(shù)據(jù)集的聚類過程是時下許多研究者面臨的重大挑戰(zhàn)。

針對混合條件屬性數(shù)據(jù)集的聚類分析，近年來，學者們提出了很多優(yōu)化算法。K-Protoypes［4～5］是處理混合條件屬性數(shù)據(jù)的經(jīng)典算法，該算法采用歐式距離度量數(shù)值條件屬性特征參數(shù)間的相似性，采用差別度匹配的方式處理分類條件屬性特征參數(shù)間的相似性。Hsu、Chen提出的CAVE算法［6］和文獻［7］均提出對分類條件屬性采用特征參數(shù)點熵度量，或配合層間距離計算相異度，對數(shù)值條件屬性則采用方差或各種距離測度計算方法來衡量相似性。文獻［8］通過定義條件語義屬性的相異性距離測量，提出一種基于數(shù)據(jù)內(nèi)在混合結(jié)構(gòu)的熵聚類SEC算法。文獻［9］對數(shù)據(jù)流的展現(xiàn)形式進行了區(qū)分，微聚類中采用針對維度的距離形式衡量相似性，在宏聚類中則采用變化了的密度聚類算法來處理微簇聚類。文獻［10］將混合屬性數(shù)據(jù)分為數(shù)值占優(yōu)、分類占優(yōu)和均衡三類形式，根據(jù)核心點確定密度關(guān)聯(lián)的實際對象來實現(xiàn)聚類。文獻［11］采用分別考慮屬性距離及關(guān)系強度的密度聚類方法，綜合處理條件屬性的關(guān)系及關(guān)系強度信息。由David等提出的SpectralCAT［12］算法，將數(shù)值條件屬性通過最優(yōu)檢測，利用譜聚類轉(zhuǎn)化為分類條件屬性，以犧牲特征信息為代價達到統(tǒng)一混合條件屬性的目的。文獻［13］提出了一種面向不平衡數(shù)據(jù)的迭代特征加權(quán)聚類算法，其依據(jù)每次迭代過程中，聚類簇的特征及類別特性重要性的衡量函數(shù)，確定條件屬性的特征權(quán)重。這類加權(quán)算法在混合條件屬性數(shù)據(jù)集中的聚類表現(xiàn)優(yōu)越。SBAC［4］算法思想來源于生物遺傳的分類問題，是一種圍繞凝聚性層次聚類的聚類算法，其優(yōu)點是能呈現(xiàn)混合條件屬性中內(nèi)聚性較大的簇。綜合上述研究，提出現(xiàn)有的對混合條件屬性對象的聚類算法存在以下缺陷：

1）鑒于混合條件屬性對象的特點在于由分類和數(shù)值條件屬性兩類特征形態(tài)完全不同的特征參數(shù)共同組成，大部分算法對混合條件屬性特征參數(shù)采取了“分而治之”的思想，在對兩類條件屬性特征參數(shù)相似性計算上，幾乎不存在任何相同的、相關(guān)的處理點。但混合條件屬性對象的組合形式對同一類別的共同指向，又意味著兩類特征參數(shù)對類別特征的顯示必然存在著相對或絕對的關(guān)聯(lián)，絕對的“分而治之”，對兩類特征參數(shù)所呈現(xiàn)出的類別特性的量化值，會存在較大的偏差，從而影響聚類的性能。

2）當混合條件屬性個數(shù)比例不平衡時，其所對應的特征參數(shù)也呈現(xiàn)不平衡的特性，而普通的類別特性加權(quán)方式往往忽略比例較低的條件屬性。而當混合條件屬性個數(shù)相對接近時，其所對應的特征參數(shù)對類別特性的呈現(xiàn)又會出現(xiàn)界定模糊的弊端，包括太多的特征噪音。

為了降低不同條件屬性間不同形式的處理方式所帶來的累積誤差，提出混合條件屬性的細化類別特征粒度系數(shù)聚類算法（Refining Category Char?acteristics Granularity Coefficients Clustering，RCC?GR-C）。其聚類核心在于對分類（熵定義類別凝聚性）和數(shù)值（歐式距離定義相似性）條件特征參數(shù)相對“分而治之”的前提下，引入細化類別特征粒度系數(shù)，關(guān)聯(lián)兩者特征對象對類別特性共同形態(tài)的呈現(xiàn)，并最終通過迭代穩(wěn)定系數(shù)的權(quán)重。

2 基于細化類別特征粒度系數(shù)的類別凝聚性概念描述及其分析

在介紹算法之前，先給出相關(guān)新算法的概念描述。概念中主要引入細化類別特征粒度系數(shù)的形式，關(guān)聯(lián)混合條件屬性間的相關(guān)類別特征。

定義 1 設數(shù)據(jù)集 S 記為 S=｛X1，X2，…，Xi，…，Xm｝=Sm×n，即S含有m個混合屬性數(shù)據(jù)對象，n表示對象的混合屬性數(shù)目。其中，任一Xi記為｛xi1，xi2，…，xip，x（i，p+1），x（i，p+2），…，xin｝，前 p個元素是數(shù)值條件屬性值，其它是分類條件屬性值。

定義2 針對分類條件屬性，若S初始化為t個簇，則xij在第j個分類條件屬性下的類別凝聚性記為V（xij），其采用信息熵的形式描述，定義如下：

其中， ||xij是屬性值xij在分類條件屬性j下出現(xiàn)的次數(shù)，是xij在分類條件屬性j下、第r簇中出現(xiàn)0；λj為類別特征細化粒度系數(shù)，直接面向數(shù)據(jù)集中從小到大的序列，下標值并不遵循原始條件屬性的維度順序；1。2?！?。l是自然數(shù)等差數(shù)列，l≤p，

定義3 針對p個分類條件屬性，Xi面向t個簇的分類粒度級別定義如下：

在類別凝聚性V（xij）的計算策略上，由于簇與簇之間的原始特征存在較大的差異，會造成V（xij）數(shù)值量級不在同一級別上，且數(shù)值級別趨向陡度大、不穩(wěn)定的結(jié)果。鑒于對象特征值分布比例是最能體現(xiàn)類別特征的指標之一，因此引入λj，在計算過程中盡可能地對類別特征不明顯的小簇設置細化程度較高的類別粒度級別，對大簇設置細化程度較低的類別粒度級別，即是對信息熵轉(zhuǎn)換的類別特征值進行細化調(diào)整。

對λj的有效性驗證，即證明λj存在于一個確定區(qū)間，且其取值范圍為( )0。2 p ，驗證如下。

也就是當p=k+1時，不等式成立。因此，由上述兩種情況，不等式對任意自然數(shù)p都成立。所以，λj的最大值小于2 p，證畢。

定義4 針對數(shù)值條件屬性，若S初始化為t個簇，則每個簇中心 Yi記為｛yb1，yb2，…，ybp，y（bp+1），y（b，p+2）…，yin｝，Xi與 Yi中任一數(shù)值條件屬性采用特征參數(shù)值的歐氏距離計算形態(tài)，來描述數(shù)值條件屬性部分的類別凝聚性，定義如下：定義5 針對數(shù)值條件屬性，Xi面向t個簇的分類粒度級別定義如下：

其中，φj是數(shù)值條件屬性的整體類別細化粒度調(diào)整參數(shù)，其所有粒度變量的說明同式（1），且有效性驗證參見λj的證明過程。

定義6 Xi面向t個簇的整體分類粒度級別，即合并式（2）和式（4），定義如下：

3 聚類算法策略設計

基于細化類別特征粒度系數(shù)聚類算法的基本步驟如下：

第1步 將數(shù)據(jù)對象集合D隨機分為k個簇，并在每個簇中隨機標注任一數(shù)據(jù)對象Xy作為簇中心，得到k個簇中心集合{X1?！y?！k}。

第2步 從k個簇中隨機選擇一個未被標注的數(shù)據(jù)對象Xi，標注它。

第3步 針對分類條件屬性，逐個計算Xi的p

第4步 對第y個簇的簇中心Xy，遵循第3步得到 Ran_S（Xy）。

第5步 針對數(shù)值條件屬性，逐個計算Xi的

第6步 對任意Xy，遵循第5步得到Ran_N（Xy）。

第7步根據(jù)式（5）計算Ran（Xi）和Ran（Xy），并計算增量值 SE=Ran（Xi）-Ran（Xy），若 SE＞0，Xi替換Xy成為第y個簇的簇中心，并撤銷Xy的簇中心標注；若SE≤0，從D中隨機選擇任意數(shù)據(jù)對象，重復第2步至第7步。

第8步 直到所有SE均為正，算法結(jié)束。

圍繞上述步驟，分析RCCGR-C算法的時間復雜度。算法簇中心的劃分的計算成本為O（kmn）；R=MAX（tp）及O（p2）分別表示針對分類條件屬性，類別凝聚性計算中單個不同特征值在t個簇中呈現(xiàn)不同值得最大數(shù)量及λj粒度變量排序過程的計算成本；O（km（n-p））表示針對數(shù)值條件屬性歐式距離方法的基本計算成本，O（（n-p）2）為 φj粒度變量排序過程中的計算成本；w是算法整體要求收斂所需的迭代次數(shù)。因此，RCCGR-C算法的時間復雜度為O（（2kmn+tp+2p2-kmp+n2-2np）w）。

4 實驗及結(jié)果分析

4.1 實驗環(huán)境及數(shù)據(jù)

所有實驗均在一臺高性能配置PC機上運行，配置如下：酷睿i7-4790 CPU，DDR3 8G內(nèi)存，1TB硬盤，WIN7操作系統(tǒng)，并采用Matlab結(jié)合Visual Stdio 2010中VC++的運行環(huán)境實現(xiàn)。實驗數(shù)據(jù)出自 http：//archive.ics.uci.edu/ml/datasets.html的 UCI數(shù) 據(jù) 集 ，采 用 Adult、Chess、Credit Approval及Hear-Disease混合條件屬性數(shù)據(jù)集。Adult共48842個數(shù)據(jù)對象，14維條件屬性，其中分類條件屬性8維，數(shù)值條件屬性6維，分為2類；Chess共28056個數(shù)據(jù)對象，6維條件屬性，其中分類條件屬性3維，數(shù)值條件屬性3維，分為17類；Hear-Dis?ease共303個數(shù)據(jù)對象，13個條件屬性，其中分類條件屬性8維，數(shù)值條件屬性5維，分為5類；Credit Approval共690個數(shù)據(jù)對象，16維條件屬性，其中分類條件屬性10維，數(shù)值條件屬性6維，分為2類。實驗數(shù)據(jù)中包含大規(guī)模、高維、低維、小型等數(shù)據(jù)對象，適用于驗證算法的伸縮性，且Credit Ap?proval和Hear-Disease數(shù)據(jù)集含缺省特征參數(shù)值。

4.2 λj及φj參數(shù)的聚類性能驗證

伸縮性是指聚類算法除了有針對性地能在特定數(shù)據(jù)規(guī)模、數(shù)據(jù)格式的樣本集中性能表現(xiàn)優(yōu)異之外，面對混合條件屬性的復雜數(shù)據(jù)環(huán)境，算法依舊能夠保持有效的聚類性能。RCCGR-C算法中λj、φj參數(shù)是關(guān)鍵，主要起到對性能伸縮性調(diào)節(jié)的作用。實驗過程中，對Adult的8維分類條件屬性，粒度變量取值范圍，即l取值從1～8，其中合的形態(tài)有=1種；（7，8）表示若l的取值為 7，所示，RCCGR-C與不接入λj系數(shù)的聚類算法（With?out Refining Category Characteristics Granularity Co?efficients Clustering，WRCCGR-C）分類屬性部分聚類性能對比如圖2所示。其中WRCCGR-C算法在策略設計中忽略了λj系數(shù)的計算過程。對Adult的性能間的關(guān)系如圖3所示，RCCGR-C與不接入φj系數(shù)的聚類算法WRCCGR-C數(shù)值屬性部分聚類性能對比如圖4所示。由于數(shù)值條件屬性數(shù)字量級、數(shù)字變化的多樣性，實驗中取數(shù)值條件屬性特征參數(shù)值小數(shù)點后有效數(shù)字兩位，且CC算法在策略設計中忽略了φj系數(shù)的計算過程。另外，對聚類準確率的計算，采用由Huang和Ng提出的評估標準［14～15］。

圖1 RCCGR-C中λj的聚類性能

圖2 WRCCGR-C與RCCGR-C（分類條件屬性）的聚類性能

圖3 RCCGR-C中φj的聚類性能

圖4 WRCCGR-C與RCCGR-C（數(shù)值條件屬性）的聚類性能

從圖1可以看出，針對分類條件屬性，l為8（涵蓋所有分類條件屬性）時，聚類準確性并不是最高的，甚至低于 l取值 3 時的情況，但當 l=4（ -λa=14.936）時，聚類準確性大幅度提高的陡度體現(xiàn)出λj系數(shù)突出的類別特征甄別能力。圖3顯示，針對數(shù)值條件屬性，l=6時，聚類準確性也不是最高的，當l=3（-φa=1.42）時，聚類準確率最高陡度值出現(xiàn)。這說明在實際情況中，完整的數(shù)據(jù)樣本中存在類別特征的混淆噪音很大，λj和φj在很大程度上能剔除不相關(guān)甚至干擾聚類的性能類別特征。對比圖1和圖3，針對Adult數(shù)據(jù)集，分類條件屬性對類別特征甄別的貢獻程度更高。圖2中，RCCGR-C算法中l(wèi)取值4，隨著聚類循環(huán)次數(shù)的增大，聚類準確率達到最高值后逐步趨于穩(wěn)定，與剔除λj系數(shù)的CC算法相比較，平均聚類準確率提高了將近7個百分點，算法體現(xiàn)出較強的穩(wěn)定性。圖4中，RCCGR-C算法中l(wèi)取值5，隨著循環(huán)次數(shù)的增大，聚類準確率也逐步提高，與剔除φj系數(shù)的WRCCGR-C算法相比較，平均聚類準確率也提高了3個百分點。顯然，λj及φj參數(shù)的設置在某種程度上相對關(guān)聯(lián)了兩類“分而治之”的條件屬性的類別特性，且在分類條件屬性個數(shù)與數(shù)值條件屬性個數(shù)比例相近時，條件屬性類別特性的界定也較為清晰，噪音剔除效果優(yōu)良，能有效提高聚類性能。但就Adult而言，系數(shù)設置對數(shù)值條件屬性類別特征抽取的敏感度明顯低于分類條件屬性，因而圖4的聚類準確率低于圖2的描述。

4.3 RCCGR-C與其它算法的比較

實驗選取了K-prototypes算法、GAVE算法和SBAC算法作為研究比較對象。從表1可以看出，RCCGR-C算法對混合條件屬性數(shù)據(jù)集的聚類效果是明顯的，且伸縮性能優(yōu)越，適用于大、小規(guī)模的數(shù)據(jù)集。RCCGR-C對數(shù)據(jù)集的平均聚類精度能達到90%以上，說明在每一輪循環(huán)聚類后，RCCGR-C中的類別特征細化粒度系數(shù)會動態(tài)地調(diào)整不同簇中混合條件屬性的綜合類別特性，同時相應地統(tǒng)一歸納混合特征參數(shù)的類別貢獻程度，使得條件屬性個數(shù)、類別特征顯著的一方的混合特征特性敏感度上升（更有利于混合特征特性的界定），不明顯的一方的混合特征特性敏感度下降（減少忽略重要的類別特征的幾率）。同時，避免常規(guī)聚類算法過度偏向包含過度特征噪音的大簇，而忽視類別特性更純粹的小簇的缺陷。因此，RCCGR-C對混合條件屬性數(shù)據(jù)的聚類性能，相比其它聚類方法，具有一定的優(yōu)越性。相對而言，其它三種算法，尤其對缺省特征值的Credit Approval和Hear-Disease數(shù)據(jù)集的動態(tài)適應調(diào)整能力較差，聚類精度都在80%以下，受樣本大小和類別質(zhì)量的影響，體現(xiàn)出較弱的聚類性能。從算法效率的角度看，RCCGR-C聚類效率優(yōu)勢并不明顯，這與其時間復雜度都屬于O（n2）級有關(guān)，但仍高于CAVE，且與K-prototypes算法接近。

表1 RCCGR-C算法與其它聚類算法在四類數(shù)據(jù)集上的實驗結(jié)果

5 結(jié)語

針對混合條件屬性數(shù)據(jù)的類別特征特點，本文提出RCCGR-C伸縮性聚類算法。通過配置類別特征細化粒度系數(shù)，統(tǒng)一分類條件屬性和數(shù)值條件屬性對類別特征的描述形式，合理呈現(xiàn)條件屬性類別特征權(quán)重。通過理論和實驗分析，RCCGR-C算法對不同的數(shù)據(jù)集是有效的，具備了較強的伸縮性。而對類別特征細化粒度系數(shù)及相關(guān)的粒度變量的擴展與優(yōu)化是后續(xù)需要研究的工作。