褚軻欣，荀亞玲

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

0 引 言

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

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

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

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

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

1 相關(guān)工作

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

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

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

2 相似性度量與聚類(lèi)分析

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

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

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

1≤j≤f,1≤i≤N

(1)

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

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

(2)

(3)

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

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

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

3.1 相似度均值與層次聚類(lèi)分析

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

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

(4)

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

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

(5)

(6)

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

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

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

f_nor=r_nor/20

(7)

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

在公式(7)中,歸一化目的是使預(yù)處理的數(shù)據(jù)被限定在一定范圍內(nèi),避免由于特征本身表達(dá)方式的原因而導(dǎo)致在絕對(duì)數(shù)值上的小數(shù)據(jù)被大數(shù)據(jù)“吃掉”的情況,以保證每個(gè)特征被平等對(duì)待并處于同一數(shù)量級(jí),從而使不同維度之間的特征在數(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)稱(chēng)之為平穩(wěn)相似性度量；f_nor表示屬性值不相同(即:xi≠yi)時(shí)的第二次歸一化值,取值范圍為[0,1]。

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

(9)

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

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

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

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

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

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

Output: Clusters

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

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

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

Forz=1 toNdo

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

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

End For

End For

End For

Clusters={ };

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

Switch(Clusters中的聚類(lèi)簇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)在兩個(gè)以上初始聚類(lèi)簇中的數(shù)據(jù)對(duì)象x,在List_B中,標(biāo)記x為邊界數(shù)據(jù)對(duì)象；

End For

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

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

End For

return Clusters

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

5 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

續(xù)表2

5.2 聚類(lèi)效果分析

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

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

續(xù)表3

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

5.3 抗噪性

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

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

6 結(jié)束語(yǔ)

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