褚軻欣，荀亞玲

(太原科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

0 引 言

作為一種無監(jiān)督學(xué)習(xí)方法,聚類分析是數(shù)據(jù)挖掘、機器學(xué)習(xí)等領(lǐng)域的主要研究內(nèi)容之一。聚類分析根據(jù)某種相似性度量將數(shù)據(jù)對象劃分為多個類簇,并使得在同一個類簇中的不同數(shù)據(jù)對象之間相似度較大,不同類簇中的數(shù)據(jù)對象之間相似度較小[1]。在商務(wù)智能[2]、圖像處理[3]、市場分析[4]、模式識別[5]、基因研究[6]等領(lǐng)域應(yīng)用廣泛。但隨著數(shù)據(jù)類型日益復(fù)雜化和多樣化,人為設(shè)置參數(shù),聚類效果對參數(shù)敏感且參數(shù)不易確定,成為當(dāng)前聚類分析面臨的主要挑戰(zhàn)之一。

層次聚類分析是一類典型的聚類分析方法,通過某種相似性度量確定數(shù)據(jù)對象之間的相似性,并對數(shù)據(jù)集中的數(shù)據(jù)對象不斷地合并或分裂,可識別任意形狀的簇。但由于層次聚類的合并或分裂依賴于事先人為設(shè)定的相似度閾值,相似度閾值的取值直接影響最終的聚類簇個數(shù)與聚類質(zhì)量[7]；在沒有先驗知識的情況下,相似度閾值參數(shù)難以確定；分類數(shù)據(jù)作為一類重要數(shù)據(jù)類型,對其層次聚類分析研究較少。根據(jù)自適應(yīng)閾值法的思想[8-11]，該文提出了一種基于相似度均值的分類數(shù)據(jù)層次聚類分析算法。利用相似度均值，作為層次聚類簇合并或分裂的重要依據(jù),解決了層次聚類分析中的參數(shù)人為設(shè)定問題。主要貢獻如下：

·提出了一種基于相似度均值的分類數(shù)據(jù)相似度閾值自動選取方法；

·給出了一種邊界數(shù)據(jù)對象分配策略；

·提出了一種基于相似度均值的分類數(shù)據(jù)層次聚類分析算法。

1 相關(guān)工作

聚類分析的目的是使得劃分后的數(shù)據(jù)點簇內(nèi)彼此相似,簇間彼此相異。目前,聚類算法主要包括密度聚類算法[12]、模型聚類算法[13]、網(wǎng)格聚類算法[14]、劃分聚類算法[15]以及層次聚類算法[16-18]等。

層次聚類是一種基于原型的聚類方法,試圖在不同層次對數(shù)據(jù)集進行劃分,從而形成樹形的聚類結(jié)構(gòu)。通過繪制樹狀圖,以可視化的方式來解釋聚類結(jié)果,可解釋性強[19-20]，可以對任意形狀的簇進行聚類[7]。層次聚類分析的典型成果主要包括：C-Ward[17]算法在Ward算法[21]的基礎(chǔ)上,在層次聚類過程中依據(jù)聚類的中間結(jié)果動態(tài)更新必連和不連約束,以保證最終的聚類結(jié)果同時滿足必連和不連約束。該算法保證了數(shù)據(jù)樣本點獲得更為合理的聚合順序,從而得到更為準(zhǔn)確的聚類結(jié)果。ROCK算法[7]是一種用于分類數(shù)據(jù)的層次聚類分析算法。該算法采用隨機抽樣技術(shù)與鏈接的相似性度量計算兩個數(shù)據(jù)對象相似度,考慮了周圍數(shù)據(jù)對象的影響,但要求用戶事先選定聚類數(shù),且相似度函數(shù)只考慮數(shù)據(jù)對象之間是否相似而未考慮相似程度,所以對閾值較為敏感。Similarity算法[22]提出了一種新的局部相似性度量,僅使用星型鄰域子圖,通過網(wǎng)絡(luò)節(jié)點相似性度量的減函數(shù)來定義節(jié)點間的廣義距離。相對全局的相似性度量,克服了傳統(tǒng)局部相似性度量在某些情形下對節(jié)點相似性的低估傾向,但矩陣的存儲形式難以適用于大型網(wǎng)絡(luò)。DHCC算法[23]基于多重對應(yīng)分析(MCA)初始化,提出了初始化和細(xì)化聚類分割的有效步驟,能夠無縫發(fā)現(xiàn)嵌入在子空間中的集群。該算法不采用全局細(xì)化,對初始誤差傳播問題不敏感,但會受異常對象的影響。MGR算法[24]是一種基于信息論提出的算法，該算法利用信息論中的平均增益比(MGR)和簇熵概念確定聚類屬性,并在屬性定義的分區(qū)中選擇等價類作為一個聚類簇，循環(huán)迭代直到輸出所有的數(shù)據(jù)對象，其算法時間復(fù)雜度較低。MTMDP算法[25]采用概率粗糙集理論的分區(qū)屬性選擇方法TMDP與粒度概念相結(jié)合,根據(jù)等價關(guān)系,將數(shù)據(jù)對象劃分為一組子集(粒子)。MTMDP算法的操作數(shù)是粒子而不是單獨的數(shù)據(jù)對象,是一種魯棒的聚類算法,用于處理分類數(shù)據(jù)聚類過程中的不確定性。MNIG算法[26]對現(xiàn)有的聚類方法進行了系統(tǒng)的分析，總結(jié)了各自的優(yōu)缺點，建立了一個統(tǒng)一的分層聚類框架并對該框架的每一步進行了改進，得到了性能更好的MNIG算法。

綜上所述,隨著對分類數(shù)據(jù)層次聚類分析研究的逐漸深入,針對分類數(shù)據(jù)的層次聚類算法獲得了較好的聚類效果。但其聚類分析算法大都需要人為設(shè)定終止條件與相似度閾值等參數(shù),控制聚類簇的合并或分裂,從而導(dǎo)致聚類效果受人為設(shè)定參數(shù)的影響較大。

2 相似性度量與聚類分析

聚類分析是指將物理或抽象對象的集合分組為由相似的對象組成的多個類簇的分析過程,因此如何描述數(shù)據(jù)對象間的相似性是聚類分析的重要問題。相似性度量是度量數(shù)據(jù)對象之間相似性的重要方法,參照文獻[27],相關(guān)概念定義如下：

設(shè)分類數(shù)據(jù)集D含有N個屬性,其中屬性Ai的取值集合記作：Dom(Ai),Dom(Ai)={ai,1,ai,2,…,ai,f},表示屬性Ai具有f個不同的取值。屬性值ai,j(ai,j∈Dom(Ai))關(guān)于屬性Ai的支持度是數(shù)據(jù)集D中屬性Ai取值等于ai,j的數(shù)據(jù)對象的個數(shù),記作：

Sup(Ai|ai,j)=|{x|x∈D,xi=ai,j}|

1≤j≤f,1≤i≤N

(1)

其中，xi表示數(shù)據(jù)對象x在屬性Ai上的取值。

相似度反映了數(shù)據(jù)對象之間的相似程度,取值區(qū)間為[0,1]。對于任意的x,y∈D,x與y的相似度Sc(x,y)、相似性度量θ(xi,yi)可定義為：

(2)

(3)

其中，Wi表示屬性Ai所占的權(quán)重,即：

在公式(3)中,分類數(shù)據(jù)的相似度計算引入相似性度量θ(xi,yi),當(dāng)xi≠yi時,θ(xi,yi)=0。代入公式(2)計算相似度Sc(x,y),若θ(xi,yi)=0,無論該屬性維計算得到的權(quán)重值Wi多大,那么該屬性維的相似程度Wiθ(xi,yi)都為0,相當(dāng)于該屬性維在計算相似度Sc(x,y)的過程中沒有發(fā)揮作用。因此,最終計算得到的相似度并未準(zhǔn)確代表各數(shù)據(jù)對象之間真實的相似程度。

3 分類數(shù)據(jù)的層次聚類分析

3.1 相似度均值與層次聚類分析

層次聚類分析作為一種典型的聚類分析方法,通過對數(shù)據(jù)集中的數(shù)據(jù)對象不斷地合并或分裂,可較容易地發(fā)現(xiàn)類的層次關(guān)系,可聚類任意形狀的簇[7]。目前,層次聚類分析算法主要是根據(jù)人為設(shè)定的相似度閾值參數(shù),實現(xiàn)聚類簇的合并或分裂。因此,相似度閾值作為層次聚類分析中的唯一參數(shù),受人為因素的影響,并影響著最終聚類簇個數(shù)與聚類質(zhì)量[28-29]。

由公式(2)中屬性Ai的權(quán)重Wi計算公式可知,將屬性Ai的熵Hc(Ai)的累加和Soe重新定義如下：

(4)

其中，Hc(Ai)表示屬性Ai的熵。

依據(jù)文獻[30]中兩次歸一化過程,將較大數(shù)量級的值歸一化到距離目的數(shù)量級相差不大的范圍內(nèi)的過程記為第一次歸一化過程。根據(jù)Soe表示的相似度的數(shù)量級別,首先將Soe按縮放比例縮放到[1,10]之間。由于余數(shù)的取值會影響歸一化值的準(zhǔn)確性,對余數(shù)做四舍五入處理,即：余數(shù)小于5時,歸一化縮放比例值不變；余數(shù)大于等于5時,歸一化縮放比例值加一。因此,歸一化縮放比例值scale_n,第一次歸一化值r_nor定義如下：

(5)

(6)

其中：?」、「?表示向下、向上取整,Soe表示分類屬性Ai的熵Hc(Ai)的累加和。

在公式(6)中,歸一化的目是使預(yù)處理的數(shù)據(jù)被合理地限定在一定范圍內(nèi),提高數(shù)據(jù)對象相似度的表現(xiàn)力,使數(shù)據(jù)對象的相似度值較平穩(wěn)分布在[1,10]之間。四舍五入的思想能使被保留部分與實際值差值不超過最后一位的二分之一,使得誤差和最小。因此,四舍五入的方法在第一次歸一化過程中可以減少Soe縮放誤差,提高第一次歸一化值r_nor的準(zhǔn)確性。

參照文獻[30],將第一次歸一化值歸一化到目的數(shù)量級的過程記為第二次歸一化過程。進一步采用歸一化與四舍五入相結(jié)合的思想,將r_nor縮放到[0,1]的數(shù)量級,得到第二次歸一化值f_nor。第二次歸一化值f_nor定義如下：

f_nor=r_nor/20

(7)

其中，r_nor表示第一次歸一化值。

在公式(7)中,歸一化目的是使預(yù)處理的數(shù)據(jù)被限定在一定范圍內(nèi),避免由于特征本身表達方式的原因而導(dǎo)致在絕對數(shù)值上的小數(shù)據(jù)被大數(shù)據(jù)“吃掉”的情況,以保證每個特征被平等對待并處于同一數(shù)量級,從而使不同維度之間的特征在數(shù)值上有可比性。第二次歸一化在第一次歸一化的基礎(chǔ)上,得到了更準(zhǔn)確的歸一化值,并將第二次歸一化值f_nor歸一化到目標(biāo)范圍(即：[0,1])之間。第二次歸一化值f_nor可以較準(zhǔn)確地反映相似度總體水平,縮小相似度極端值的出現(xiàn)頻率。

根據(jù)上述公式(7)所得f_nor,為縮小相似度差異,將公式(3)重新定義為平穩(wěn)相似性度量,并描述如下：

(8)

其中，θs(xi,yi)稱之為平穩(wěn)相似性度量；f_nor表示屬性值不相同(即:xi≠yi)時的第二次歸一化值,取值范圍為[0,1]。

在公式(8)中，θs(xi,yi)保持屬性值相同(即：xi=yi時)的取值不變,等于1,屬性值不同(即：xi≠yi)時的取值等于f_nor,f_norf是一個動態(tài)值。對于每個屬性維,不會再出現(xiàn)Wiθ(xi,yi)=0,忽略相似度計算過程中丟失重要屬性維的情況。f_nor近似反映了數(shù)據(jù)集中所有數(shù)據(jù)對象相似度的分布趨勢,使得Sc(x,y)變化比較平穩(wěn),可以正確表示數(shù)據(jù)對象之間的相似度,為計算相似度閾值做準(zhǔn)備。

(9)

其中，|x|表示任意數(shù)據(jù)對象x的編碼,|D|表示數(shù)據(jù)集D的數(shù)據(jù)對象總數(shù)。

3.2 邊界數(shù)據(jù)對象分配策略

由于層次聚類方法使得所有的數(shù)據(jù)對象在全部簇中有且僅出現(xiàn)一次,這樣的合并方式使得邊界數(shù)據(jù)對象無法被友好地確定屬于哪一個簇的邊界點或噪聲點。針對以上兩種邊界數(shù)據(jù)對象的分布情況,邊界數(shù)據(jù)對象分配策略如下：

4 基于相似度均值的分類數(shù)據(jù)層次聚類分析算法HCAS

Algorithm：HCAS (Hierarchical clustering analysis for Classified data based on Average Similarity)

Input：分類數(shù)據(jù)集D

Output: Clusters

從數(shù)據(jù)集D提取N；//*N為屬性個數(shù)

Fori=1 to|D|do //*依據(jù)公式(2),計算相似度Sc(x,y),并插入List_Sim中；

Forj=i+1 to|D|do //*x,y分別為第i個,第j個數(shù)據(jù)對象；

Forz=1 toNdo

利用公式(4)-(8),計算平穩(wěn)相似性度量θs(xi,yi)；

利用公式(1)-(2)計算相似度Sc(x,y)并插入List_Sim中；

End For

End For

End For

Clusters={ };

For allSc(x,y) in List_Sim do //*依據(jù)相似度均值,獲得初始聚類簇,并標(biāo)記邊界數(shù)據(jù)對象

Switch(Clusters中的聚類簇Q)

Casex屬于Q:Q=Q+{y},Break;

Casey屬于Q:Q=Q+{x},Break;

Casex與y都不屬于Q：

Clusters=Clusters+{x,y},Break;

End Switch

End If

將出現(xiàn)在兩個以上初始聚類簇中的數(shù)據(jù)對象x,在List_B中,標(biāo)記x為邊界數(shù)據(jù)對象；

End For

For all 邊界數(shù)據(jù)對象xin List_B do //* 按邊界數(shù)據(jù)對象分配策略分配邊界數(shù)據(jù)對象

依據(jù)3.2節(jié)中邊界數(shù)據(jù)對象分配策略,將x重新分配到Clusters中的聚類簇；

End For

return Clusters

時間復(fù)雜性分析：

5 實驗結(jié)果分析

實驗環(huán)境：CPU Intel?酷睿TMi7-4710MQ,內(nèi)存為12 GB，操作系統(tǒng)為Microsoft Windows 10,采用java語言,在jdk1.8、jre1.8、eclipse-jee-neon-3環(huán)境下,實現(xiàn)了HCAS算法與對比的分類數(shù)據(jù)層次聚類算法：ROCK[7]、MGR[24]、MTMDP[25]、MNIG[26]。

數(shù)據(jù)集：人工合成和UCI[32]數(shù)據(jù)集,詳見表1。其中：Class表示聚類個數(shù)，Instance表示數(shù)據(jù)對象個數(shù)，N表示屬性個數(shù)。

表1 數(shù)據(jù)集

評價指標(biāo)：準(zhǔn)確率Accuracy (ACC)、蘭德指數(shù)Rand Index (RI)、Fowlkes and Mallows Index (FMI)、F1指數(shù)[33-34]四個評價指標(biāo),更客觀地衡量聚類效果。ACC表示衡量分類正確的記錄個數(shù)占總記錄個數(shù)的比例；RI表示衡量聚類結(jié)果與真實簇標(biāo)簽之間的相似性；FMI表示兩兩精度和召回率的幾何平均值；F1表示準(zhǔn)確率與召回率二者的調(diào)和均值。

實驗對比的分類數(shù)據(jù)層次聚類算法參數(shù)設(shè)置：將對比算法ROCK、MGR、MTMDP與MNIG的聚類個數(shù)參數(shù)設(shè)置為正確的聚類個數(shù),然后設(shè)置ROCK算法參數(shù)θ的取值區(qū)間,運行多次,選擇最優(yōu)的聚類效果作為最終的結(jié)果[27]。實驗數(shù)據(jù)集的預(yù)處理方式為：刪除數(shù)據(jù)集中含有缺失屬性值的記錄；刪除數(shù)據(jù)集中分布在不同類別中的相同數(shù)據(jù)對象。

5.1 相似度均值的穩(wěn)定性分析

表2 相似度均值的穩(wěn)定性

續(xù)表2

5.2 聚類效果分析

為了驗證HCAS算法的聚類性能,在UCI數(shù)據(jù)集上,給出了ROCK、MGR、MTMDP、MNIG和HCAS算法性能比較,其實驗結(jié)果詳見表3，其中k表示聚類簇個數(shù)。

表3 UCI數(shù)據(jù)集上的聚類算法性能比較

續(xù)表3

由表3可知，HCAS算法在四種評價指標(biāo)上的聚類性能都好于ROCK、MGR、MTMDP、MNIG算法。其主要原因是：在HCAS算法中,采用了平穩(wěn)相似性度量,避免忽略重要屬性維,使數(shù)據(jù)對象之間的相似度計算更加準(zhǔn)確；HCAS由于采用了邊界數(shù)據(jù)對象分配策略,使得模糊邊界數(shù)據(jù)對象被最大概率分配到正確的聚類簇中,提高了層次聚類分析的聚類質(zhì)量；ROCK算法對于相似度較小但屬于一個聚類簇的邊界數(shù)據(jù)對象不友好,從而導(dǎo)致邊界數(shù)據(jù)對象分配不準(zhǔn)確,聚類效果較差。MTMDP算法由于提高了每次分裂葉子節(jié)點選取的準(zhǔn)確度,所以聚類效果較穩(wěn)定。MGR算法用度量分區(qū)之間的相似性，來構(gòu)造與每個屬性關(guān)聯(lián)的分區(qū)盡可能接近的分區(qū)，所以聚類效果較好。MNIG算法綜合現(xiàn)有的聚類方法建立統(tǒng)一的分層聚類框架，并對框架的每一步進行改進，從MNIR選擇的屬性生成的分區(qū)中選擇最好的分區(qū)，所以其聚類效果優(yōu)于MGR算法。

5.3 抗噪性

為了驗證HCAS算法的抗噪性,采用表1所示Type1數(shù)據(jù)集,分別添加5%、10%、15%的噪聲數(shù)據(jù),比較HCAS算法的聚類性能指標(biāo),其實驗結(jié)果如圖2所示。

由圖2可知,隨著數(shù)據(jù)集中噪聲數(shù)據(jù)比例的增大, ACC、FMI、RI和F1都呈現(xiàn)降低趨勢。其原因是：隨著噪聲數(shù)據(jù)的增多,噪聲數(shù)據(jù)干擾了相似度計算的準(zhǔn)確性,使HCAS算法錯將一部分噪聲數(shù)據(jù)對象當(dāng)作邊界數(shù)據(jù)對象添加到聚類簇中,造成了評價指標(biāo)的下降。隨著在數(shù)據(jù)集中每增加5%的噪聲數(shù)據(jù),評價指標(biāo)降低約0.03到0.05之間,噪聲數(shù)據(jù)對聚類結(jié)果影響不大,HCAS算法在有噪聲的數(shù)據(jù)集中依然具有較高的聚類質(zhì)量,說明HCAS算法具有良好的抗噪性。

6 結(jié)束語

針對層次聚類相似度閾值需要人為設(shè)定的問題,定義了一種相似度均值計算方法,并作為層次聚類簇合并或分裂的重要依據(jù),有效解決了相似度閾值參數(shù)人為設(shè)定問題；采用相似度均值,給出了一種邊界數(shù)據(jù)對象分配策略,并提出了一種基于相似度均值的分類數(shù)據(jù)層次聚類分析算法。該算法充分利用數(shù)據(jù)對象在數(shù)據(jù)集中的分布特點,自動確定相似度閾值,降低了人為因素的干擾,提高了聚類質(zhì)量。下一步工作是針對混合屬性數(shù)據(jù)層次聚類分析,研究相似度閾值的自動設(shè)定。