一種基于多屬性權重的分類數據子空間聚類算法

龐寧　張繼福　秦嘯

聚類是根據數據對象之間的相似程度,將數據集合理劃分成若干數據子集的過程,每個子集稱為一個簇.聚類分析的目標是使得劃分后的數據點在簇內彼此相似,在簇間彼此相異.經典的聚類算法主要包括劃分聚類算法[1?3]、層次聚類算法[4?6]、基于密度[7]和網格[8]的聚類算法以及譜聚類[9]等,但沒有任何一種聚類算法可以普遍適用于揭示各種多維數據集所呈現出來的多種多樣的結構[10].隨著高維海量數據的廣泛應用,數據類型也日益復雜化和多樣化,以處理數值型數據為主的傳統聚類算法已無法滿足高維分類數據的聚類需求.而分類數據廣泛分布在各應用領域中,分類數據的聚類分析已成為目前數據挖掘領域中極具挑戰性的研究方向之一[11?16].

目前,分類數據聚類研究需要解決以下兩個問題:1)由于高維屬性空間的稀疏性,大量冗余屬性或不相關屬性使得全屬性空間下的聚類結果毫無意義[17],因此,屬性權重的度量成為提高高維分類數據聚類效果的關鍵問題之一;2)由于分類數據缺乏數值型數據固有的幾何特征,不能進行數值運算,同時,也無法使用衡量數值型數據的距離方法去判定分類數據的相似性[18],因此,適合分類數據的簇集質量判斷標準會直接影響聚類精度.本文針對分類數據,定義了一種基于多屬性頻率的屬性權重計算新方法,并在此基礎上,采用多目標聚類準則,結合層次聚類思想,提出了一種適合分類數據的子空間聚類算法.該算法無需設定初始參數,可以識別和處理噪音點,并根據數據自身的結構特征,在相關屬性子空間上聚類.本文的主要貢獻如下:

1)定義了一種基于多屬性頻率的屬性權重計算方法;

2)給出了一種基于多目標簇集質量的聚類準則;

3)提出了一種基于多屬性權重的分類數據子空間聚類算法.

1　相關工作

傳統分類數據聚類算法[1,19?20]認為各屬性維在聚類過程中的作用是無差別的,全屬性空間下的聚類算法雖然可以有效解決低維數據的聚類問題,但面對高維數據時,有效性會顯著降低.為了克服傳統聚類算法存在的不足,各種降維技術被用于降低高維屬性空間維度,主要的解決思路包括:特征轉換[21]和特征選擇[22?23].文獻[21]總結對比了幾種主要的特征轉化技術,如主成分分析(Principal components analysis,PCA)、核主成分分析(Kernel principal component analysis,KPCA)和獨立分量分析(Independent component analysis,ICA)在高維空間向低維空間映射過程中的效果差異,上述技術均采用將高維屬性組合生成新屬性的思路,存在新組合屬性的解釋性差,數據簇不易理解的缺陷.文獻[22]在粗糙集理論的基礎上,提出一種貪婪的混合屬性約簡算法,該算法利用所推導出的屬性重要性度量規則,可以有效降低屬性空間的維度;文獻[23]提出一種基于對偶圖特征選擇聚類算法,該算法使用自表示特征保存數據空間和屬性空間的幾何信息,在數據空間的自表示系數矩陣上加入稀疏約束以分析屬性重要性,選取重要屬性提高聚類質量.特征選擇的方法可有效約簡屬性空間,但這種將原屬性空間中的若干屬性提取出來構成新屬性空間的方法,會造成部分信息丟失.因此,針對高維數據,基于特征轉換和特征提取技術的聚類效果仍無法滿足實際需求.

近幾年,在傳統降維技術研究的基礎上,基于屬性子空間的聚類研究受到了廣泛關注.大量文獻[24?35]均驗證了在高維數據背景下,全屬性空間上無法形成有意義的簇集,類簇存在于不同的相關屬性子空間中,屬性權重的度量不再以整個屬性維為單元,同一屬性在不同數據點上的重要度不同,因此,屬性子空間算法是目前解決高維數據聚類問題的有效途徑之一[24].子空間聚類算法不僅可以將相似數據聚合成若干類簇,同時針對不同類簇會給出各自獨立的相關屬性子空間.子空間的思想最初用于解決數值型數據的聚類問題[24?27].隨著針對分類數據挖掘需求的不斷增長,各種高維分類數據的子空間聚類算法應運而生[28?35],典型算法有:文獻[28]采用最小化目標函數的思想,提出了一種面向分類數據近似最優劃分的子空間算法(Subspace clustering for categorical data,SUBCAD),該算法奠定了與聚類相關子空間的理論基礎,但該算法所給出的目標函數無法確保在迭代過程是遞減的;文獻[29]提出了一種基于圖論的分類數據子空間聚類算法(Mining subspace clustering algorithm,CLICKS),利用密度參數將聚類問題轉化成加權圖的思想,以屬性值之間的共現頻次作為權值,反復搜索k個最大分離的類,該算法以屬性值的共現次數為基礎提高了聚類精度,但聚類效果依賴于初始密度參數,同時基于加權圖的權重計算增加了時間成本;文獻[30]基于屬性值在本地屬性維上出現的次數,計算該值在單屬性上的頻率,提出一種通過質量判斷函數反復迭代判斷數據歸屬的方法(Projected clustering algorithm for categorical data,PROCAD),但該方法在判斷多類別和屬性值域元素個數較少的數據集時,會出現聚類效果變差的現象;文獻[31]提出了一種分階段的無參層次聚類算法(Top-down clustering of high-dimensional categorical data,AT-DC),該算法以屬性值在數據簇中的條件概率作為權重,判斷數據點對類簇的影響,利用全局聚類質量函數,將簇迭代分裂為子簇,雖然該算法給出了類簇的劃分,卻沒有給出與簇集相關的屬性子空間,而且聚類結果與數據的輸入順序相關;文獻[32]提出了一種層次分裂聚類算法(Divisive hierarchical clustering of categorical data,DHCC),該算法采用多元對應分析思想,將數據點對應到一維空間中并初步分為兩個子簇,再利用數據點與子簇相似度調整子簇內的數據點,不斷迭代上述分裂過程直至整個簇集總質量無法提高為止,該算法同樣可以避免參數對聚類結果的干擾,但該算法的時間復雜度取決于多元對應分析的效率,同時該算法在低維屬性空間上的聚類效果會降低;文獻[33]在文獻[34]的基礎上,提出一種雙加權K-Modes聚類算法(A mixed attribute weighting k-modes algorithm,MWKM),利用最小化簇內誤差平方和的思想,自動調整屬性在各數據簇中的重要度,屬性權值與該屬性在簇內分布的離散程度相關,該算法計算速度快,但算法需要設定參數;文獻[35]提出一種熵加權聚類算法(An entropy weighting k-means algorithm,EWKM),該算法同樣采用拉格朗日乘子優化單目標函數,推導屬性權值公式,將表現屬性對于聚類不確定性的熵引入權重計算中,屬性權值與該屬性在簇內的熵成反比,該算法也需要設定大量初始參數,同時文獻[33?35]均是在K-Modes算法的基礎上提出的,這類算法在處理類簇尺寸差異較大的數據集時,往往會出現“均勻效應”現象[36],數據常常會聚合成尺寸相對均勻的簇.

綜上所述,子空間聚類算法思想是基于各屬性在聚類過程中權重的差異,在重要屬性組成的相關屬性子空間中,根據聚類目標函數將數據點劃分到不同類簇內.多數子空間聚類算法[30?35]在選取構成子空間的相關屬性時,僅以屬性取值的單屬性權重作為衡量標準,沒有考慮到其他屬性對于該屬性值權重的影響,即屬性取值在整個屬性空間上的分布特征.文獻[29]在考慮多屬性之間的關聯對屬性權重的影響時,需遍歷整個數據空間以統計屬性值的同現次數,從而增加了聚類過程的時空復雜性.作為判斷聚類質量的關鍵,數據點與簇的相似度計算是整個聚類算法的核心,僅以類內數據點緊湊作為聚類目標會影響到簇集質量[33?35],聚類結果容易受到非平衡數據分布的影響,同時,參數也會干擾聚類算法的穩定性.因此,要有效地解決高維分類數據背景下的子空間聚類問題,需要解決的關鍵問題為:利用屬性值在多維屬性上的分布特征,獲取高權值屬性以構建各數據點的相關屬性子空間;在屬性子空間的基礎上,將類內緊湊與類間分離相結合作為判斷簇集質量的聚類準則,以解決基于單目標函數聚類算法無法有效處理非平衡數據集的問題.據集的其他點不同,服從不同的分布,可判定為噪音點.

表1　符號表示及含義Table 1　Symbol and notation

2　問題描述與求解策略

分類數據(Categorical data)是指數據屬性值是分類型的數據,分類屬性又稱標稱屬性,分類屬性取值都是有限無序的,且不可比較大小,也無法進行數值運算.參考文獻[30]與表1定義的符號,問題描述如下:

分類數據的子空間聚類目標是將數據集U內的n個數據點劃分為若干個類簇Cs以及噪音集NOS,數據點xk由d個分類屬性值組成,可形式化表示為xk={xk1,xk2,···,xkd},在屬性子空間SAs下,類簇Cs由數據點集SDs構成,Cs可表示為二元組(SDs,SAs).例如圖1,U共有10個數據點,每個數據點由8個分類屬性值組成,數據集可劃分為三個類簇和噪音集,分別表示為C1,C2,C3和NOS.

從圖1可以發現,各簇對應的相關子空間規模不一定相同,例如,簇C1的子空間為{a1,a2},而C2和C3的子空間分別為{a2,a3,a4},{a4,a5,a6},同時各簇之間沒有交集(SDi∩SDj=?),即數據點的歸屬具有唯一性;屬性值分布過于稠密或過于稀疏,均無法反映類簇的特征,例如,屬性a7和a8不會出現在任一類簇的屬性子空間中;數據x10明顯與數

圖1　聚類示例圖Fig.1　Clustering sample

針對上述子空間聚類問題,由第1節的相關工作分析可知,現有分類數據聚類方法在計算屬性權重時存在的問題:1)盡管單屬性權重計算方法有利于提高時間效率,但僅以單屬性評價屬性權值會造成屬性值聚類區分度下降,例如圖1,屬性a3不屬于C1的屬性子空間,在C1的形成過程中,盡管具有相同取值(R),屬性值x33的聚類作用應遠低于x43的作用,若僅以R值在a3上的出現頻率來衡量屬性值權重,則無法反映出x33與x43聚類能力的差異,因此,區分同頻率屬性值的權重需要借助其他相關屬性;在依靠多屬性計算屬性值權重時,若以遍歷全數據空間為代價,計算基于多屬性的屬性值權重會降低算法的時間效率.2)單目標聚類準則雖然可以根據聚類過程中數據點的分布特征自動調整各屬性權值,但僅以數據點與簇中心的距離作為聚類準則,對于廣泛分布的非平衡數據,邊緣數據很容易被誤判到其他類中,影響最終的聚類效果,同時,單目標聚類算法需要最優化聚類目標函數,存在設置參數等問題.

采用多屬性頻率計算屬性權重,有效地體現了屬性值在屬性空間中的分布特征,可解決單屬性計算權重所帶來的聚類區分度下降等問題,例如,從屬性空間分布上分析,由于屬性值x43與x42(RS),x43與x44(RV)在數據集上同時出現的頻率均為30%,而x33與其他屬性的同現頻率僅為10%,因此,利用屬性a2與a4,基于多屬性頻率計算屬性值x43與x33的權重,可以有效區分兩屬性值的權重差異.在簇內距離最小化目標的基礎上,結合簇間分離最大化目標作為聚類準則,有助于邊緣數據的正確劃分;單個類中心無法反映大類特征也是造成非平衡數據均勻化的原因之一[37],因此,采用層次凝聚聚類思想,利用子簇代表大類的多個類中心,通過迭代合并子簇,將大類的子簇聚集在一起,從而解決非平衡數據的聚類問題.子空間聚類問題的求解步驟為:1)屬性權值的計算.基于粗糙集利用多屬性頻率計算各屬性值的權重,該方法不僅考慮到多屬性維之間的關聯對屬性值權重的影響,同時,基于粗糙集理論,利用數據點在不同屬性下等價類之間的交集,統計多屬性上屬性值的同現次數,無需遍歷整個數據空間,提高了時間效率;2)基于多目標聚類準則的層次凝聚聚類.利用簇內緊湊和簇間分離的聚類目標,給出簇集質量函數,在聚類過程中采用一種自底向上的凝聚聚類策略,將聚類過程分為初聚類和合并聚類兩個階段,初聚類階段利用多目標簇集質量函數先將最相似的數據點生成子簇,在合并聚類階段,迭代合并各子簇以提高整個簇集質量,形成最終的類簇;3)噪音點檢測.在聚類之前,利用最小化區間離散度的方法,濾掉那些低權值的點,即噪音點以提高聚類效果;4)屬性相關子空間識別.根據簇內各屬性對簇的依附度,確定各簇的相關屬性子空間.

3　基于多屬性權重的分類數據子空間聚類

由第2節可知,分類數據聚類步驟主要由四個階段構成,即:分類屬性權重計算,基于多目標聚類準則的層次凝聚聚類,噪音點識別和識別屬性相關子空間.

3.1　分類屬性權重

3.1.1　分類屬性權重計算依據

解決第2節所提出的權重計算問題,需要考慮兩個因素:1)屬性取值在本地屬性上的出現頻率,該值反映了屬性值的局部重要程度;2)用其他相關屬性度量該屬性值與相關屬性值的共現頻率,該值刻畫了屬性值的全局重要性.為了避免計算共現頻率而增加的時間成本,可按照屬性值將各屬性劃分為若干個數據集合,為了表述方便,用符號Si(xk)表示在屬性ai上與xk具有相同屬性值的數據集合.統計屬性值xki與xkj的同現次數,相當于求解集合Si(xk)與Sj(xk)交集的基數,即|Si(xk)∩Sj(xk)|.例如圖1,按照屬性值,屬性a1可分為集合:{x1,x2,x3},{x4,x8,x9},{x5,x10},{x6}和{x7},a2可分為{x1,x2,x3},{x4,x5,x6,x7},{x8},{x9}和{x10},求S1(x3)∩S2(x3)得{x1,x2,x3},可知屬性值x31與x32同時出現了3次.

3.1.2　分類屬性權重

在粗糙集理論[38]中,R表示論域上的等價關系,[x]R表示包含x的R等價類,等價類內的所有對象在關系R中等價.可以將上述統計屬性值同現次數的問題轉換為求解屬性等價類交集的問題.同時,本文采用文獻[39]給出的計算等價類算法(參見文獻[39]中的算法1),利用快速排序思想,根據屬性值預先對數據集進行排序處理,文獻[39]理論推導出該算法的時間復雜度降至O(|A||U|lg|U|),并實驗證明了該算法可有效地提高計算等價類的運行效率.

對于任意ai∈A,設xki∈Vai,從本地屬性ai的角度度量屬性值xki單屬性權重,則可以定義為

其中,[xk]ai內的數據點在屬性ai上的取值與xk相同,|[xk]ai|反映了屬性值xki在ai上出現的次數.參考文獻[30]采用取對數運算,可避免圖1中屬性a7和a8對聚類結果的干擾,利用式(1)可得,Wa8(x18)=0.09,而屬性a7上任意屬性值,均有Wa7(xk7)=0.

從相關屬性aj的角度度量xki的多屬性權重,可以定義為

其中,[xk]aj表示包含數據xk的aj等價類,|[xk]aj∩[xk]ai|表示兩等價類交集的元素個數,即屬性值xki與xkj的同現次數,0＜Waj(xki)≤1,Waj(xki)的定義表明屬性值xkj與xki同現次數占[xk]ai的比例越大,從aj的角度上所反映的xki聚類作用越大.根據式(2),可證明多屬性權值Waj(xki)的三條性質,證明過程見附錄A.

用W(xki)表示綜合權重,并做歸一化處理,使得0≤W(xki)＜1,計算公式定義為

基于粗糙集的多屬性度量方法可以有效提高屬性的聚類能力,解決僅依靠單屬性無法區分同頻次屬性值權重的問題.例如圖1,使用式(1)計算得,Wa3(x33)=Wa3(x43),無法區分屬性值x33和x34聚類能力的差別;利用式(3),可得W(x33)=0.13,W(x43)=2×W(x33)=0.25,可解決第2節提出的單屬性權重聚類區分度下降的問題.

3.2　基于多目標聚類準則的層次凝聚聚類

聚類準則是聚類過程中判斷數據點劃分的主要依據,通常采用簇集質量函數表示.簇集質量是指聚類結果的質量,該值代表數據劃分的合理程度,簇集質量可以采用單目標和多目標兩種方式,多目標簇集質量更有利于挖掘數據集的內部結構.

3.2.1　多目標聚類準則依據

基于單目標準則的聚類算法,常用最小化類內誤差平方和的方法聚類,該方法容易導致大類邊緣的數據點被誤劃到其他類中,因此,在簇內數據緊湊的基礎上,采用簇間數據分離的原則可避免邊緣數據誤判,有效處理非平衡數據的聚類問題.

綜合簇內緊湊和簇間分離兩個目標來評價簇集質量,1)簇集質量應取決于簇內數據是否緊湊,簇內緊湊程度與簇投影到重要屬性上的屬性值相關,該屬性值權值越大,出現的頻率越高,則簇集質量越好;2)簇集的質量也與簇間數據分離程度相關,為了使不同的簇盡可能分離,簇投影在重要屬性上的屬性值應盡量集中,不同的簇在高權值屬性維上的取值應盡可能不同.

3.2.2　多目標簇集質量判斷

為了計算簇集總質量,需要先分別計算各簇質量.參照文獻[20]和文獻[31],基于屬性值采用如下定義的Q(Cs)來描述簇Cs的質量,其質量值可分別從簇內緊湊度和簇間分離度來度量,Com(xki)用于表示用屬性值xki所度量的簇內緊湊度,Sep(xki)是用屬性值xki度量的簇間分離度.

簇內緊湊度Com(xki)可以從兩個方面評價:屬性值xki在簇Cs內的分布,可由屬性值xki在屬性ai上的概率P(ai=xki)以及該值在簇Cs內的概率P(ai=xki|Cs)的乘積來度量,該值主要體現了屬性值xki在Cs上的集中程度;屬性值xki對于類簇的重要性,由該值的權重W(xki)表示.簇間分離度Sep(xki)則取決于屬性值xki專屬于簇Cs的程度,可以用xki出現在簇Cs屬性ai上的概率P((ai=xki)∧(xk∈Cs))與整個數據集上xki出現的概率P(ai=xki)的比例表示,該值越大,說明ai上的屬性值xki越集中地出現在Cs中.經推導,Q(Cs)可由以下符號組成的表達式表示:count(xki,ai,Cs)表示在類簇Cs內,投影在ai上的值為xki的數據點數目;n代表數據集的數據總量;W(xki)是屬性值xki的權值;count(xki,ai)是指在屬性ai上xki出現的總次數.

假設簇集C={C1,C2,···,Ck},采用Q(C)描述簇集整體質量,可用下式來刻畫簇集質量.

Q(C)反映了在簇集C的劃分方式下,數據分布的整體質量.該值越大,意味著這種劃分方案越合理,Q(Cs)則表示簇Cs的質量,P(Cs)代表Cs中的數據點占整個數據集的比例,P(Cs)的主要作用是協調各簇之間的相互作用以達到最佳的整體聚類效果.

3.2.3　基于多目標聚類準則的層次凝聚聚類

在多目標聚類準則的基礎上,層次凝聚聚類過程可分為初聚類和合并聚類兩個階段.初聚類階段,隨機挑選一個數據點作為第一個子簇,使用式(7),依次計算其他待聚類數據點與現有子簇的簇集質量,根據簇集質量最大化原則,決定該數據點分配到已有的某個子簇中或者生成的新子簇.初聚類的目標是將數據中最相似的數據點劃分為若干子簇,子簇具有純度高、規模小的特點,可以代表大類的多個類中心,子簇的形成不僅可以有效避免非平衡數據的均勻化,同時也為迭代合并階段提高了時間效率;初聚類階段利用簇集質量函數,按照簇集質量最大化原則,將每個數據點依次選擇分配到已有的子簇中或者生成的新子簇.合并聚類的任務是找到同屬一個類簇的所有子簇,迭代合并各子簇以提高數據集的聚類質量,直到整個迭代過程中沒有產生合并子簇的操作為止;該過程采用層次凝聚思想,以式(7)度量的簇集質量函數最大化為基礎,將最相近的兩個子簇合并.該階段充分利用了高純度子簇,來迭代合并最相似的子簇,有效地加速了聚類形成的過程.

3.3　噪音點檢測

噪音點是指那些與正常數據點有顯著區別的特殊點.對于各屬性權重都相對偏低的數據點,可認為投影到任何維上都無法找到相似點,即為噪音異常點.為了判斷噪音點,可引入如下定義的聚合度概念Os(xk).

Os(xk)體現了數據點xk在各屬性維上的聚類能力.Os(xk)值越小,說明xk越有可能是噪音點.

具體識別步驟:按照聚合度Os(xk),先將所有數據點升序排序;利用區間離散度找到最佳的劃分點xm,m的取值使滿足min(),即,該劃分點使得區間[x1,xm]和區間[xm+1,xn]的離散度之和在所有劃分點中最小;以最小化區間離散度為目標,采用類似k-means的聚類思想,將數據點劃分為兩類,其中,低聚合度區間[x1,xm]中的數據點就是聚類能力較差的噪音點.

Os(xk)表示區間[xi,xj]上聚合度的平均值.|j?i|表示j與i差的絕對值.值越小,說明區間內的點越接近.

3.4　屬性相關子空間

屬性相關子空間是由最能反映類簇特征的一組屬性組成.計算各屬性相對于簇的依附程度是確定屬性子空間的關鍵,采用R(ai,Cs)刻畫屬性ai對于簇Cs的依附程度.參照式(4),依附程度可用如下表達式描述:

屬性子空間的識別方法與噪音點識別類似,根據屬性依附度R(ai,Cs),以區間離散度最小化為目標,將降序屬性區間[a1,ad]分為區間[a1,am]和[am+1,ad],高依附度區間[a1,am]就是屬性子空間.

4　基于多屬性權重的分類數據子空間聚類算法SAC

依據第2節和第3節,基于多屬性權重的子空間聚類算法SAC基本思想,可歸納為:首先利用粗糙集概念分別計算屬性值權重,由式(1)～(3)完成,計算過程可由函數WAC來實現;其次利用式(8)計算各數據點的聚合度,采用式(9)劃分數據區間,判斷并去除噪音點,此過程由函數NAI完成;利用式(7),實現將數據集到簇集的轉化過程,該過程由初聚類階段和合并聚類階段構成,分別由兩個函數INC和MEC實現;最后基于式(10)給出的屬性相對簇的依附度,確定與簇相關的屬性子空間,具體實現由函數SUI完成.具體算法描述如下:

1)函數WAC:計算屬性權重函數

輸入.屬性取值xki;

輸出.權值W(xki);

begin

保存xk在各屬性ai上的等價類[xk]ai;

分別根據式(1)、式(2),式(3),計算Wai(xki),

Waj(xki),W(xki),并輸出W(xki);

end

2)函數NAI:噪音點識別

輸入.數據集U;

輸出.噪音集NOS;

begin

根據式(8)計算各點聚合度Os(xi),并按照聚合度對

xi升序排序;

minind=0;

fori=1 ton

{將數據序列分割為L[x1,xi]和H[xi+1,xn];根據式(9),分別計算區間L和H的離散度Ds(L)和Ds(H);

minind=min((Ds(L)+Ds(H)),minind);}NOS←L[x1,xminind],并輸出噪音集NOS;

end

3)函數INC:初聚類

輸入.′U=U?NOS,W(xki);

輸出.子簇集SC;

begin

SC={{x1}};

fori=2 to|′U|

{Qmax=0;idmax=0;

forj=1 to|SC|

{sum1=Q({xi}∪scj);

sum2=Q({xi})+Q(scj);

if(sum1＞sum2)&&(sum1＞Qmax)

{Qmax=Q({xi}∪scj);idmax=j;}

if(idmax＞0)scidmax←scidmax∪{xi};

else{xi}作為新簇;}

輸出子簇集SC;}

end

4)函數MEC:合并聚類

輸入.子簇集SC;

輸出.最終的簇集C;

begin

repeat

maxind=0;

fori=1 to|SC|

forj=1 to|SC|

{利用式(7),計算SCi與SCj合并后的簇集質量Q(SC(t));

s=Q(SC(t))?Q(SC(t?1)),SC(t?1)是上次

迭代的簇集質量值;

if(maxind＜s)

{maxind=s;maxi=i;maxj=j;}}

合并SCmaxi和SCmaxj;

until(maxind==0);

C←SC,并輸出簇集C;

end

5)函數SUI:相關子空間識別

輸入.簇集C;

輸出.各簇Cs的屬性相關子空間SAs;

begin

用式(10),計算Cs內各屬性維aj的依附度R(aj,Cs),

并將簇內各屬性降序排序;

minind=0;

fori=1 tod

{將屬性序列分割為L[a1,ai]和H[ai+1,ad];

minind=min(區間L離散度+區間H離散度,minind)};

SAs←H[a1,aminind],輸出SAs;

end

上文描述的SAC算法,運行時間隨數據量的增加呈線性增長.該算法主要由三個函數組成,分別為屬性權重計算、初步聚類和合并聚類,因此,算法SAC的時間復雜度分析主要包含以下三個階段:設n=|U|,d=|A|,s=MAXai∈A|Vai|,k代表子簇的數量,c=MAXscs∈SC|scs|(scs是初聚類形成的子簇),t為最大迭代次數.

1)計算屬性值權重的時間復雜度.該階段的時間消耗主要集中在相關屬性對屬性值權重的度量上,由于算法SAC采用粗糙集的等價類概念,統計同現屬性值的比較范圍由n縮小至s,該階段的時間復雜度為O(n×s×d2).

2)初步聚類的時間復雜度.該階段的主要操作是計算子簇內數據屬性值對簇集質量的影響,該階段的時間復雜度為O(n×k×c×d).

3)合并聚類的時間復雜度.該階段的時間消耗主要集中在尋找可合并子簇的操作上,該階段的時間復雜度為O(t×c×d×k2).

綜合上述三個階段的分析,算法SAC時間復雜度為O(n×s×d2+n×k×c×d+t×c×d×k2).由于真實海量數據,n?d,n?s,n?c,相對于n而言,算法SAC所消耗的時間是線性增長的.

5　實驗及分析

實驗環境:3.2GHz Intel Core i5處理器,2GB內存,windows 7的操作系統,ECLIPSE 1.0的編輯環境,并采用Java 7.0語言實現了本文SAC算法、CLICKS[29]算法、PROCAD[30]算法以及EWKM[35]算法,AT-DC[31]、DHCC[32]算法代碼由作者提供.上述5種算法用于進行對比實驗,這些算法均可以解決高維分類數據的聚類問題.其中,CLICKS算法是一種基于圖論的聚類算法,該算法以屬性值同現信息作為聚類依據;PROCAD算法是針對分類數據的子空間聚類算法,該算法以屬性值在單屬性上的頻率計算屬性權重;AT-DC和DHCC是無參數的層次聚類的典型算法,其中,ATDC算法以屬性值在簇中的條件概率作為屬性權重,DHCC算法采用多元對應分析思想決定各屬性在聚類過程中的作用;EWKM算法是基于經典KModes算法的改進算法,利用最小化簇內誤差平方和的思想計算屬性權重.SAC算法是一種分類數據的子空間聚類算法,算法基于粗糙集,利用多屬性維取值的頻次衡量各屬性權重,采用層次凝聚策略聚類.SAC算法、PROCAD算法、AT-DC算法和DHCC算法均是無參算法,無需設置參數;CLICKS算法的主要參數包括k,α和minsup,其中,k設置為實際簇數,α和minsup從0.1～0.9按步長0.1取值實驗,實驗取平均值作為實驗結果;算法EWKM的參數主要包括k,m,α和r,其中,k為實際簇數,m和α設為1,r分別設為1,2和5.數據集主要分為人工合成數據集、UCI數據集以及真實光譜數據三大類,表2詳細描述了實驗數據集的具體信息.

聚類算法的評價指標可以分為內部和外部兩類,外部評價指標通常適用于有人工標示聚類結果的數據集,使用聚類算法所得到的聚類結果與根據人的先驗知識給出的結果進行對比,可以有效地評價聚類算法是否適合于該數據集.參照文獻[30?31],分別采用調整蘭德系數ARI(Adjusted rand index)、純度Purity、雅克比系數Jaccard、蘭德指數RI(Rand index)四個外部評價指標,ARI主要測試聚類結果和真實類之間的相似度.Purity評測聚類結果中各簇起支配作用的數據比例.Jaccard系數主要判斷隸屬于同一類的數據對在同一簇的比例.RI主要評測同類數據對是否被聚合以及異類數據對是否可以分開.其中,ARI,Jaccard和RI三個指標不僅注重對比兩種結果中各簇內元素的分布狀況,更偏重兩種聚類結果在類簇數目上的差距;而指標Purity更側重于衡量簇內占主導地位數據點的比例.

表2　數據集Table 2　Dataset

5.1　人工合成數據集

為了全面測試算法的聚類效果,結合文獻[40]給出的合成數據方法,構造了圖2所示的四種合成數據集.

如圖2(a)所示,數據集Type 1各簇之間的數據點以及屬性相關子空間獨立存在,互不相交;Type 2代表簇間數據點有交集,如圖2(b)所示,從不同的子空間分析,x3可以分屬于兩個不同的簇;Type 3代表各簇屬性相關子空間有交集,如圖2(c),屬性a2既屬于簇C1的相關子空間,又屬于C2的子空間;如圖2(d),Type 4與Type 1數據分布特征一致,不同的是,Type 4是簇尺寸差異較大的非平衡數據集.

5.1.1　可擴展性

在數據集Type 3上,主要測試各算法在數據容量上的可擴展性,分別選取6000,10000,20000,40000和60000作為數據量測試節點,實驗結果如圖3.從圖3可以發現,隨著數據量的增加,所有算法的聚類時間都呈現近似線性增長的趨勢,SAC算法所消耗的時間在所對比的算法中僅比PROCAD少.在數據集Type 2上,主要測試各算法在屬性維度上的可擴展性,維度測試節點分別選擇50,100,150和200維,結果如圖4.如圖4所示,隨著維度的增加,除CLICKS以外,其余算法的聚類耗時呈現線性增長的態勢,SAC算法消耗的時間雖然比算法AT-DC和DHCC多,但遠低于CLICKS算法,略低于PROCAD算法.

從圖3可知,SAC算法與PROCAD算法時間成本高于其他三種算法,原因是這兩種算法在衡量屬性權重時,需要計算數據點所有屬性值的重要度,當數據量增加時,會比以整個屬性為度量單位的算法費時.從圖4可知,CLICKS算法的時間效率明顯受限于維數,原因是該算法將聚類問題轉化為有權圖劃分問題,而圖上的權值取決于數據點之間的同現次數,當屬性維增多或者屬性值域元素增多時,統計各維度上所有屬性值的同現次數非常耗費時間.盡管SAC算法基于屬性值間的同現頻次計算權重,隨著數據集屬性規模的增長,會增加計算成本,但該算法在聚類過程中采用粗糙集縮小屬性查找范圍,縮短權重計算時間,同時基于子簇的合并過程可以大大提高聚類迭代速度,因此,圖3與圖4所示的擴展性實驗結果表明,SAC算法的運行時間隨數據量和維度呈線性增長.

5.1.2　抗噪性

抗噪性實驗主要包括兩方面:SAC算法在合成數據上對比不同維度之間的抗噪性能變化以及在真實光譜數據上的抗噪性能;SAC算法與其他5種聚類算法在合成數據集上的抗噪性對比實驗.

在Type 1數據集上,數據總量為10000,分別包含900,1800,3150和4500個噪音點作為測試節點,并觀察在15,30,40和50維屬性空間上算法SAC抗噪性能的變化.圖5(a)和圖5(b)分別反映了在不同維度空間下,噪音點數量的變化對算法SAC聚類指標ARI和Purity的影響.從圖5可知,SAC算法在噪音點的影響下,性能較穩定,ARI與Purity指標均高于90%,尤其是50維的屬性空間,所有指標均在96%以上,說明SAC算法具有良好的抗噪性能.由圖5(a)和圖5(b)可知,SAC算法的抗噪能力與屬性空間規模,噪音點比例有關.在加入相同噪音點的數據環境下,抗噪性能與屬性空間的維數成正比.當屬性空間越小、噪音點越多,聚類效果所受影響越大,其主要原因是SAC算法是基于屬性之間的同現概率獲取屬性權重,當屬性空間過小時,不利于挖掘簇的聚類模式.

圖3　數據量可擴展性Fig.3　Scalability with data

圖4　維度可擴展性Fig.4　Scalability with dimendionality

為了測試SAC算法在真實數據上的抗噪能力,選擇包含8315條208維恒星光譜記錄的數據集,分別加入1000,2000和3000條噪音記錄.表3顯示在不同噪音環境下,SAC去除噪音點的數目以及各性能指標的變化,表明噪音點對真實數據的聚類影響以及SAC算法的抗噪能力.從表3可知,與無噪音點時SAC性能指標相比,所有指標值均下降,其中,ARI下降最多,Purity最少;同時,聚類性能下降的程度與噪音數目成正比.算法SAC可以識別并去除大部分噪音點,少量殘留的噪音基本上會聚為若干類簇,這些類簇僅包含噪音點,這樣的聚類結果對Purity影響最小,但增加的類簇數目使得其他性能指標顯著下降.

在Type 1數據集上,選取50維屬性,10000個數據點構成測試數據,包含噪音點數分別為900,1800,3150和4500.隨著噪音點數的增加,對比SAC算法和其他五種算法的聚類效果.圖5(c)反映了噪音點數量的變化對不同算法聚類指標ARI的影響.從圖5(c)可知,算法SAC和PROCAD在抗噪性上的表現均優于其他4種算法,原因是算法SAC和PROCAD都具有檢測噪音點的能力,聚類之前已去除了噪音點的干擾,保證聚類性能的穩定.同時,由于多屬性權重有助于更精準地反映出數據點各屬性的聚類能力,可以更準確地檢測到噪音點,因此,基于單屬性權重算法PROCAD的抗噪性比算法SAC略低.

5.1.3　不同類型數據集的聚類性能對比

采用圖2所描述四個合成數據集Type 1,Type 2,Type 3,Type 4作為實驗數據集.四個數據集規模相同,即10000個數據點,50維屬性,可聚為6個簇;Type 1,Type 2,Type 3是平衡數據,各簇尺寸基本一致,Type 4簇的尺寸差異較大,其中,C1和C2有3000點,是其他簇的三倍.

圖6顯示在四種合成數據集上,隨維度變化,SAC聚類指標ARI、Purity的變化情況.由圖6可知,盡管Type 1和Type 4數據分布相同,但簇的尺寸有差異,特別是Type 4各簇規模差距很大.SAC算法在Type 1和Type 4上的聚類效果良好,各指標均可達到100%,說明SAC算法的聚類效果與簇尺寸是否平衡無關;而Type 2和Type 3的實驗結果顯示,SAC聚類效果與數據分布緊密相關,隨著維度的增加,Type 2和Type 3數據分布的變化可能會造成最終聚類性能的下降.

表3　SAC在光譜數據上性能指標變化Table 3　Noise immunity on the spectral data for SAC

圖5　抗噪性實驗Fig.5　Immunity to noise

圖6　SAC算法在四種數據集上的對比實驗Fig.6　Contrast experiment on four data sets for SAC

由于大簇的邊緣數據容易受到小簇類中心的干擾,單一類中心無法反映大簇特征等原因,非平衡數據往往更容易聚成尺寸相等的類簇.由圖6 Type 1和Type 4上的聚類效果可知,SAC算法沒有受到類簇尺寸差異的影響.原因是SAC算法利用多目標聚類準則,強化大類邊緣數據與小簇之間的類間分離作用;同時分階段的層次聚類過程采用子簇的形式,利用多個類中心表示大類,從而避免出現“均勻效應”的現象.在Type 2和Type 3上,SAC算法的ARI和Purity值,隨著維數增加而下降.原因是隨數據維度增加,Type 2中數據交集和Type 3中的屬性子空間交集范圍均在擴大,當交集比例過大時,類簇之間的差異會隨之減少,在合并聚類階段,原本分屬兩個類的數據點會聚為一類.

圖7顯示在50維,10000個數據點的數據規模上,SAC與其他5種算法在四類數據集上的ARI性能指標差異.從圖7可見,SAC算法在四類數據集上的聚類效果均優于其他算法,并且該算法在不同數據集上的聚類性能較穩定.

文獻[15]指出,CLICKS算法在數據集Type 2和Type 3上聚類性能不佳的主要原因是該算法會產生大量冗余簇;而算法PROCAD、DHCC和AT-DC在四類數據集上的性能差別不大,盡管算法DHCC和AT-DC無法給出簇集的相關子空間,但在高維屬性空間下,這三類算法對數據集結構不敏感;算法EWKM是基于K-Modes提出的,這類算法在識別尺寸差別較大的簇集時,會出現“均勻效應”,因此,該算法在數據集Type 4上的聚類性能會降低.

圖7　各算法在四種數據集上的(ARI)對比Fig.7　Contrast experiment on four data sets(ARI)for all algorithms

5.2　UCI數據集

實驗分別選取Voting,Splice,Mushroom和Zoo四個UCI數據集,這些數據集均由分類數據組成,其中,Zoo中只含有一個數值型屬性;數據集均帶有類別標識,可以用外部評價指標,更客觀地度量各算法的聚類效果.

Voting數據集共包含435條記錄,每條記錄由16個議題的投票結果和一個類標簽構成;屬性值域{Y,N};所有的記錄可以分為兩個簇,其中267條記錄是democrat的投票結果,republican的投票記錄有168條.Splice數據集共由3190個數據點,60個屬性維以及一個類標簽構成;每一個數據點是一組基因序列,屬性值對應該序列上的一個位置,屬性值域為{A,T,G,C};數據點共分為三個簇,分別是EI(767個數據點)、IE(768個數據點)和Neither(1655個數據點).Mushroom數據集包含8124個數據點,22個屬性;各屬性分別用來描述蘑菇的各種性狀,max|Vai|=10;數據集共分為兩類,共有3916條poisonous記錄表示該蘑菇有毒,4208個帶有edible標簽的數據表示可食用.Zoo數據集共有101個數據點,17個屬性,1個類標簽;數據集可以分為7類,分別為Mammal(41個數據點)、Bird(20個數據點)、Reptile(5個數據點)、Fish(13個數據點)、Amphibian(4個數據點)、Insect(8個數據點)和Invertebrate(10個數據點).

從表4和圖8可知,SAC算法在Voting和Splice上的聚類效果均優于其他三種算法;在Mushroom 上,PROCAD 算法ARI、Jaccard和RI指標均高于其他算法;而AT-DC算法在Zoo上的實驗效果最優.其主要原因:1)SAC在Voting和Splice數據集上的效果最優,原因是這兩類數據集的共同特點是屬性值域元素個數都較少,其中,Congressional Voting的屬性值是布爾型;數據集Splice的屬性值僅有四個,通常屬性值的取值范圍較小,會造成單屬性權值的區分度不明顯,進而影響到基于單屬性聚類算法的最終聚類結果,而SAC算法利用多屬性的同現概率可以很好地解決這一問題,進一步提高算法的聚類效果,該結論可由表5和表6的聚類結果得到驗證.2)SAC在Mushroom上的聚類性能僅次于PROCAD,而在Zoo上也是略低于AT-DC,原因是SAC算法用式(3)強化了多屬性頻率對屬性權重的影響,所以,即使同一個類的數據,SAC會根據子簇模式上的差異劃分出若干純度極高的子簇,經過合并所形成的簇集純度依舊非常高,但同時也會造成簇劃分較細的問題,簇集細化會保證算法的聚類純度,但也影響了其他三項指標,該現象在表7和表8中都有體現.

表4　UCI數據集上的算法性能Table 4　Algorithm performance on UCI

圖8　UCI數據集上的算法性能Fig.8　Algorithm performance on UCI

表5　Voting集上的實驗結果Table 5　Experimental results on Voting

5.3　屬性相關子空間

Zoo數據集規模較小,但屬性維較多,有利于分析結果,且該數據集所對應的類別較多,可以更全面地反映出數據中不同結構的差異,因此Zoo數據集有利于測試SAC算法在屬性相關子空間上的識別能力.

表6　Splice集上的實驗結果Table 6　Experimental results on Splice

從表9可知,SAC算法的聚類結果可以分為三類:劃分完全準確的簇,例如C1和C3等;應該分裂卻聚在一起的簇,例如C2和C5等;應聚合為一個簇,卻分為兩個簇,例如C4、C8和C9.針對上述三類情況,分別從數據特點的角度,對SAC算法聚類結果的合理性進行分析.

1)被準確劃分的數據點特征是:該類數據間具有很強的結構特征,同時,簇內數據點在該結構特征上屬性取值也非常一致.例如C1由37種哺乳動物構成,其相關子空間上各屬性的含義,分別是有毛發、非蛋生、哺乳、無鰭和有4條腿,這些特征是哺乳動物的共同典型特征.

表7　Zoo集上的實驗結果Table 7　Experimental results on Zoo

表8　Mushroom集上的實驗結果Table 8　Experimental results on Mushroom

2)本屬異類卻聚合在一起的數據點特征是:該類數據點在某種劃分方式下可以分為兩類,而從其他分類角度上分析,這些數據又具有一些共同的特殊特征,可以歸為一類.例如,C2是由76.5% 的魚類和23.5%的哺乳動物組成,其中作為哺乳動物的Dolphin(海豚)、Porpoise(鼠海豚)、Seal(海豹)和Sealion(海獅)有著明顯水生動物的特征,例如它們有鰭,具有水生能力等,所以從水生動物的角度上分析,這4種動物和 fi sh類的數據可以聚合在一起.

3)本屬同類卻分為兩個簇的數據點特征是:該類數據點雖然同屬一類,但數據點仍具有各自特點.例如,同屬于無脊椎動物的Octopus(章魚)、Scorpion(蝎子)和Star fi sh(海星),根據腿數的不同也可以分為C8和C9兩類.

從上述分析中可知,SAC算法在識別屬性相關子空間時,可以識別出特征信息明顯的關鍵屬性子集作為屬性子空間,該屬性子集不僅在簇內具有高權值的特點,而且高權值的屬性取值又具有專屬性,例如,屬性Legs在每個簇上的取值幾乎都不同,原因是多屬性權重計算方法在挖掘重要屬性時更注重該屬性在整個屬性空間中的分布特征,并非僅依靠單屬性的出現頻率,因此,基于多屬性頻率的屬性權重聚類方法所提取的屬性子空間對聚類結果更具解釋性.

表9　Zoo數據集中的相關子空間Table 9　Relevant subspace on Zoo data set

5.4　天體光譜數據

根據國家天文臺提供的恒星光譜數據,選取了8315條208維光譜記錄作為實驗數據,該數據集按照恒星溫度由低至高排序可以將恒星光譜分為7類(分別用A,B,F,G,K,M和O表示)[41?42].由于光譜數據的大部分屬性是數值型數據,需要按照不同離散程度將光譜數據前200維屬性做等距離散化處理.

表10給出各種等距離散化方法與SAC聚類性能指標之間的關系.指標Purity與離散化程度是單調遞增的關系,而其他三項指標會呈先揚后抑趨勢.造成該現象的主要原因是SAC算法擅長處理具有獨立不相關的屬性子空間(如Type 1)的數據集,離散化程度越高,對于簇的特征劃分的越細致,因此,聚類結果中的大量高純度簇,會提高聚類結果的純度,但劃分過細也會造成其他三項性能指標的下降.

表10　各種離散化方法下的SAC聚類性能指標對比Table 10　Clustering performance of different discretization methods

使用11等距離散化方法預處理光譜數據,并實驗對比SAC算法與其他5種算法在真實數據上的聚類性能差異.從表11可知,算法SAC的各性能指標均高于其他算法,PROCAD、DHCC和AT-DC性能無明顯差異,算法EWKM 的性能最低.光譜數據實驗得到了與合成數據相似的實驗結果,主要原因是光譜數據是非平衡數據,其中類A的規模是類O的3倍,算法EWKM 不擅長處理這類數據,聚類性能較差;盡管光譜數據所形成的類簇較多,但各簇的值域元素較多,同時具有高維度,因此,算法PROCAD和DHCC的聚類性能均較穩定.

表11　各算法在光譜數據上的對比實驗Table 11　Algorithm performance on spectral data

5.5　結束語

采用屬性相關子空間,挖掘隱藏在高維屬性空間中的簇是高維分類數據聚類領域中的研究難點和熱點之一.本文基于粗糙集采用多屬性頻率權重,提出一種分類數據子空間聚類算法SAC.該算法基于粗糙集采用多屬性頻率計算屬性權重,解決了使用單屬性計算權重所帶來的問題,同時借助粗糙集可以提高統計多屬性頻率的時間效率;針對噪音點對聚類效果的影響,使用區間離散度方法,有效地刪除了噪音點;基于層次凝聚聚類思想,利用多目標簇集質量函數迭代合并子簇,解決單目標聚類函數聚類結果不精確的問題;利用屬性相對簇的依附度,提取屬性相關子空間,提高了聚類簇的可理解性;大量的實驗結果驗證了算法SAC的正確性和有效性.下一步研究工作是將SAC算法由分類數據擴展到混合數據.

附錄A

性質A1.當時,屬性值xki的多屬性權值最大,其值為1.

證明.由下近似集的定義可知:∈U|[xk]aj?[xk]ai},且={x∈U|[xk]ai?[xk]aj}.

因為xk∈可得,[xk]aj?[xk]ai,又因為[xk]ai?[xk]aj,所以可得,[xk]ai=[xk]aj,可得,[xk]aj∩[xk]ai=[xk]ai?|[xk]aj|=|[xk]ai|,可得,Waj(xki)=1.

該情況表明,對于數據xk,在屬性ai的取值為xki,則在屬性aj的取值一定為xkj.用屬性aj度量屬性值xki的權重應該取最大值.例如圖1中x11,用屬性a2計算x11權重,可得Wa2(x11)=3/3=1.□

性質 A2.當[xk]aj∩[xk]ai={xk}時,屬性值xki的多屬性權重取值最小,值為1/|[xk]ai|.

證明.因為[xk]aj與[xk]ai的交集內只有一個數據點xk,所以|[xk]aj∩[xk]ai|=1,可得,

當[xk]aj∩[xk]ai={xk}時,說明屬性值xki和xkj僅同時出現一次.即使屬性值xki單屬性權值較大,但從屬性aj上看,xki與aj的相關性較低,該屬性值的全局重要性較低,例如圖1,屬性值x41在屬性a2下的多屬性權重值,Wa2(x41)=1/3=0.33.□

證明.由上近似集定義可知,={x∈U|[xk]ai∩[xk]aj/=?},位于集合內的數據權值取決于[xk]aj與[xk]ai交集的大小,該值反映了屬性值xki和xkj的同現次數.交集元素越多,表明屬性值xki與屬性aj越相關,該屬性值在聚類過程中的作用越大,例如圖1,用a3度量x42的權重,Wa3(x42)=3/4=0.75.□

1 Wu Xh,Wu B,Sun J,Qiu S W,Lix.A hybrid fuzzy K-harmonic means clustering algorithm.Applied Mathematical Modelling,2015,39(12):3398?3409

2 Jiang Yi-Zhang,Deng Zhao-Hong,Wang Jun,Qian Peng-Jiang,Wang Shi-Tong.Collaborative partition multi-view fuzzy clustering algorithm using entropy weighting.Journal of Software,2014,25(10):2293?2311(蔣亦樟,鄧趙紅,王駿,錢鵬江,王士同.熵加權多視角協同劃分模糊聚類算法.軟件學報,2014,25(10):2293?2311)

3 Bai L,Liang J Y.Cluster validity functions for categorical data:a solution-space perspective.Data Mining and Knowledge Discovery,2015,29(6):1560?1597

4 Bouguettaya A,Yu Q,Liux,Zhoux,Song A.Efficient agglomerative hierarchical clustering.Expert Systems with Applications,2015,42(5):2785?2797

5 Zhou Chen-Xi,Liang Xun,Qi Jin-Shan.A semi-supervised agglomerative hierarchical clustering method based on dynamically updating constraints.Acta Automatica Sinica,2015,41(7):1253?1263(周晨曦,梁循,齊金山.基于約束動態更新的半監督層次聚類算法.自動化學報,2015,41(7):1253?1263)

6 Jeon Y,Yoon S.Multi-threaded hierarchical clustering by parallel nearest-neighbor chaining.IEEE Transactions on Parallel and Distributed Systems,2015,26(9):2534?2548

7 Kim Y,Shim K,Kim M S,Sup Lee J.DBCURE-MR:an efficient density-based clustering algorithm for large data using MapReduce.Information Systems,2014,42:15?35

8 Mansoori E G.GACH:a grid-based algorithm for hierarchical clustering of high-dimensional data.Soft Computing,2014,18(5):905?922

9 Shang Rh,Zhang Z,Jiao L C,Wang W B,Yang S Y.Global discriminative-based nonnegative spectral clustering.Pattern Recognition,2016,55:172?182

10 Sun Ji-Gui,Liu Jie,Zhao Lian-Yu.Clustering algorithms research.Journal of Software,2008,19(1):48?61(孫吉貴,劉杰,趙連宇.聚類算法研究.軟件學報,2008,19(1):48?61)

11 Park I K,Choi G S.Rough set approach for clustering categorical data using information-theoretic dependency measure.Information Systems,2015,48:289?295

12 Chen L F,Wang S R,Wang K J,Zhu J P.Soft subspace clustering of categorical data with probabilistic distance.Pattern Recognition,2016,51:322?332

13 Cao F Y,Liang J Y,Bai L,Zhaox W,Dang C Y.A framework for clustering categorical time-evolving data.IEEE Transactions on Fuzzy Systems,2010,18(5):872?882

14 Li M,Deng S B,Wang L,Feng S Z,Fan J P.Hierarchical clustering algorithm for categorical data using a probabilistic rough set model.Knowledge-Based Systems,2014,65:60?71

15 Hex,Feng J,Konte B,Mai St,Plant C.Relevant overlapping subspace clusters on categorical data.In:Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2014.213?222

16 Ji J C,Pang W,Zheng Y L,Wang Z,Ma Z Q.A novel arti fi cial bee colony based clustering algorithm for categorical data.PLoS ONE,2015,10(5):e0127125

17 Gan G,Wu J,Yang Z.PARTCAT:a subspace clustering algorithm for high dimensional categorical data.In:Proceedings of the 2006 IEEE International Joint Conference on Neural Network Proceedings.IEEE,2006:4406?4412

18 Bouveyron C,Girard S,Schmid C.High-dimensional data clustering.Computational Statistics and Data Analysis,2007,52(1):502?519

19 Guha S,Rastogi R,Shim K.ROCK:a robust clustering algorithm for categorical attributes.In:Proceedings of the 15th International Conference on Data Engineering.Sydney,Australia:IEEE,1999.512?521

20 Barbar′a D,Li Y,Couto J.COOLCAT:an entropy-based algorithm for categorical clustering.In:Proceedings of the 11th ACM International Conference on Information and Knowledge Management.McLean,VA,USA:ACM,2002.582?589

21 Cao L J,Chu K S,Chong W K,Leeh P,Gu Q M.A comparison of PCA,KPCA and ICA for dimensionality reduction in support vector machine.Neurocomputing,2003,55(1?2):321?336

22 Hu Qh,Xie Zx,Yu D R.Hybrid attribute reduction based on a novel fuzzy-rough model and information granulation.Pattern Recognition,2007,40(12):3509?3521

23 Shang Rh,Zhang Z,Jiao L C,Liu C Y,Li Y Y.Selfrepresentation based dual-graph regularized feature selection clustering.Neurocomputing,2016,171:1242?1253

24 Parsons L,Haque E,Liuh.Subspace clustering for high dimensional data:a review.ACM SIGKDD Explorations Newsletter,2004,6(1):90?105

25 Yip K Y,Cheung D W,Ng M K.HARP:a practical projected clustering algorithm.IEEE Transactions on Knowledge and Data Engineering,2004,16(11):1387?1397

26 M¨uller E,G¨unnemann S,Assent I,Seidlt.Evaluating clustering in subspace projections of high dimensional data.Proceedings of the VLDB Endowment,2009,2(1):1270?1281 27 Bouguessa M,Wang S R.Mining projected clusters in highdimensional spaces.IEEE Transactions on Knowledge and Data Engineering,2009,21(4):507?522

28 Gan G J,Wu Jh.Subspace clustering for high dimensional categorical data.ACM SIGKDD Explorations Newsletter,2004,6(2):87?94

29 Zaki M J,Peters M,Assent I,Seidlt.CLICKS:an effective algorithm for mining subspace clusters in categorical datasets.Data and Knowledge Engineering,2007,60(1):51?70

30 Bouguessa M.Clustering categorical data in projected spaces.Data Mining and Knowledge Discovery,2015,29(1):3?38

31 Cesario E,Manco G,Ortale R.Top-down parameter-free clustering of high-dimensional categorical data.IEEE Transactions on Knowledge and Data Engineering,2007,19(12):1607?1624

32 Xiongt K,Wang S R,Mayers A,Monga E.DHCC:divisive hierarchical clustering of categorical data.Data Mining and Knowledge Discovery,2012,24(1):103?135

33 Bai L,Liang J Y,Dang C Y,Cao F Y.A novel attribute weighting algorithm for clustering high-dimensional categorical data.Pattern Recognition,2011,44(12):2843?2861

34 Chan E Y,Ching W K,Ng M K,Huang J Z.An optimization algorithm for clustering using weighted dissimilarity measures.Pattern Recognition,2004,37(5):943?952

35 Jing L P,Ng M K,Huang J Z.An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data.IEEE Transactions on Knowledge and Data Engineering,2007,19(8):1026?1041

36 Xiongh,Wu J J,Chen J.K-means clustering versus validation measures:a data-distribution perspective.IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,2009,39(2):318?331

37 Liang J Y,Bai L,Dang C Y,Cao F Y.The k-means-type algorithms versus imbalanced data distributions.IEEE Transactions on Fuzzy Systems,2012,20(4):728?745

38 Qu Kai-She,Zhai Yan-Hui,Liang Ji-Ye,Li De-Yu.Representation and extension of rough set theory based on formal concept analysis.Journal of Software,2007,18(9):2174?2182(曲開社,翟巖慧,梁吉業,李德玉.形式概念分析對粗糙集理論的表示及擴展.軟件學報,2007,18(9):2174?2182)

39 Liu Shao-Hui,Sheng Qiu-Jian,Wu Bin,Shi Zhong-Zhi,Hu Fei.Research on efficient algorithms for rough set methods.Chinese Journal of Computers,2003,26(5):524?529(劉少輝,盛秋戩,吳斌,史忠植,胡斐.Rough集高效算法的研究.計算機學報,2003,26(5):524?529)

40 Kim M,Ramakrishna R S.Projected clustering for categorical datasets.Pattern Recognition Letters,2006,27(12):1405?1417

41 Zhang Ji-Fu,Jiang Yi-Yong,Hu Li-Hua,Cai Jiang-Hui,Zhang Su-Lan.A concept lattice based recognition method of celestial spectra outliers.Acta Automatica Sinica,2008,34(9):1060?1066(張繼福,蔣義勇,胡立華,蔡江輝,張素蘭.基于概念格的天體光譜離群數據識別方法.自動化學報,2008,34(9):1060?1066)

42 Zhang J F,Zhaox J,Zhang S L,Yin S,Qinx.Interrelation analysis of celestial spectra data using constrained frequent pattern trees.Knowledge-Based Systems,2013,41:77?88