陳佳佳，張 旺，劉東海，張曉琴

（山西財(cái)經(jīng)大學(xué) 統(tǒng)計(jì)學(xué)院，太原 030006）

0 引言

作為機(jī)器學(xué)習(xí)中的分支，聚類分析是用特定的方式選擇初始類中心并將所有樣本分到與其相似性最大的類中的過程。聚類分析技術(shù)有著廣闊的應(yīng)用范圍：電子技術(shù)、電力系統(tǒng)、農(nóng)業(yè)研究、文本識別、經(jīng)濟(jì)分析等領(lǐng)域。聚類分析主要分為以K-means算法為代表的劃分聚類、以CURE算法[1]為代表的層次化聚類、以DBSCAN算法[2]為代表的密度聚類、以STING 算法為代表的網(wǎng)格式聚類、以EM 算法為代表的模型聚類。

在聚類算法的研究過程中，不同研究者給出了不同的算法。文獻(xiàn)[3]針對數(shù)值型數(shù)據(jù)提出了K-means算法，該算法計(jì)算量小、計(jì)算速度快、適用范圍比較廣泛。針對分類型數(shù)據(jù)，文獻(xiàn)[4]通過對比樣本點(diǎn)與類中心的異同，提出了基于簡單0-1 匹配計(jì)算距離的K-modes 算法。K-means、K-modes 算法簡單高效，但是只能處理固定的一類數(shù)據(jù)。在此基礎(chǔ)上，文獻(xiàn)[5]將K-means算法與K-modes算法簡單結(jié)合，分別對兩部分?jǐn)?shù)據(jù)計(jì)算距離后再賦予二者權(quán)重進(jìn)行調(diào)整，提出了針對混合型數(shù)據(jù)的K-prototypes算法（又稱為K-原型算法）。文獻(xiàn)[6]提出了K-centers算法，分類型數(shù)據(jù)類中心為頻率向量，數(shù)值型數(shù)據(jù)類中心仍為均值，某一個樣本的類中心即為兩個部分的結(jié)合，這對混合型數(shù)據(jù)聚類提供了新的思路。文獻(xiàn)[7]提出了適用于模糊場景中表示類別屬性的類中心。文獻(xiàn)[8]提出了一種改進(jìn)的K-prototypes 算法，將類中心表示為均值與頻率模糊類中心結(jié)合的形式。文獻(xiàn)[9]提出了一種由信息熵計(jì)算不同類型數(shù)據(jù)權(quán)重的K-prototypes 聚類算法，通過計(jì)算不同類別的類內(nèi)熵與類間熵得出每個屬性的權(quán)重。文獻(xiàn)[10,11]在文獻(xiàn)[9]的基礎(chǔ)上引入了權(quán)重屬性，重新定義類間熵等指標(biāo)，進(jìn)行了一定的改良。文獻(xiàn)[12]提出了結(jié)合均值與分布式質(zhì)心表示的混合屬性簇中心，并提出了一種新的相異性度量。文獻(xiàn)[13]提出了基于密度優(yōu)化的K-prototypes 算法，該算法能自動調(diào)整聚類個數(shù)與初始類中心，同時改進(jìn)了K-prototypes 算法的相異性度量。文獻(xiàn)[14]提出了一種指數(shù)形式的分類型數(shù)據(jù)相似性作為權(quán)重的計(jì)算方法，該權(quán)重計(jì)算方法會擴(kuò)大數(shù)據(jù)之間的差異性。文獻(xiàn)[15]提出針對最大相異性度量不唯一的特性改進(jìn)初始聚類中心選取方法。文獻(xiàn)[16]提出了自適應(yīng)函數(shù)將相異性度量轉(zhuǎn)化為相似性度量，選取多個初始中心，增加了聚類結(jié)果的魯棒性。

K-prototypes 算法具有適用范圍廣、計(jì)算速度快等優(yōu)點(diǎn)，但仍然存在一些缺陷：（1）之前的K-prototypes 算法對于分類型數(shù)據(jù)距離都是進(jìn)行0-1簡單匹配計(jì)算，文獻(xiàn)[5,9]引入頻率向量表示分布質(zhì)心后使用的也是歐氏距離。這種做法忽略了分類型數(shù)據(jù)與數(shù)值型數(shù)據(jù)的差別，分類型數(shù)據(jù)是離散的，直接使用0-1 匹配會損失很多信息，頻率向量表示分類型數(shù)據(jù)定和為1，并不適合用歐式距離作為相異性度量。（2）針對分類型數(shù)據(jù)的權(quán)重，大多需要每次迭代計(jì)算一次，雖然提升了聚類精度但是計(jì)算量大大提升，無法處理大數(shù)據(jù)問題。基于以上考慮，本文提出了一種α度量下的改進(jìn)K-prototypes 算法（α-metric K-prototypes Clustering Algorithm，以下簡稱α-K-prototypes 算法）。α-K-prototypes算法將均值與頻率向量結(jié)合來表示混合數(shù)據(jù)的類中心，并提出一種新的相異性度量方法。經(jīng)實(shí)驗(yàn)驗(yàn)證，α-K-prototypes 算法提升了對分類型、混合型數(shù)據(jù)的聚類精度，使算法性能得到進(jìn)一步提升。

1 相關(guān)知識

1.1 K-prototypes算法

定義1：樣本Xi到聚類中心Qz的距離為：

算法1：K-prototypes算法

K-prototypes 算法是基于定義2 中目標(biāo)函數(shù)準(zhǔn)則，將數(shù)據(jù)集X分為k個互不相交的類，其具體算法步驟如下：

步驟1：按照特定的方式確定k個初始類中心。

步驟2：計(jì)算某個數(shù)據(jù)與所有類中心的目標(biāo)函數(shù)，將數(shù)據(jù)分到使得目標(biāo)函數(shù)最小的類中，直至所有數(shù)據(jù)都完成分配。

步驟3：按照均值與最多次數(shù)屬性值結(jié)合的形式更新類中心。

步驟4：若步驟2、步驟3 計(jì)算出的距離總和未發(fā)生變化或達(dá)到迭代次數(shù)上限，則停止循環(huán)；否則重復(fù)進(jìn)行步驟2、步驟3。

1.2 分類型數(shù)據(jù)的模糊類中心表示形式

K-prototypes 算法僅使用簡單0-1 匹配計(jì)算距離會丟失很多信息，為更全面地表達(dá)樣本信息，文獻(xiàn)[9]引入了一種模糊類中心表達(dá)形式。

1.3 一種新的融合α 度量K-prototypes改進(jìn)算法

定義4：稱滿足以下條件的空間為D維成分?jǐn)?shù)據(jù)空間：

該空間中的元素即為成分?jǐn)?shù)據(jù)。

定義5：對于成分?jǐn)?shù)據(jù)x=(x1,x2,…,xD)，對稱對數(shù)比變換定義為：

定義6：記x、y為SD中的任意兩個成分?jǐn)?shù)據(jù)，其Aitchison距離表示為：

由公式可以看出第j個分類型屬性模糊類中心集合為Dj維成分?jǐn)?shù)據(jù)空間，第i個樣本在這個屬性上的頻率向量與第z個類在這個屬性上的模糊類中心頻率向量均符合成分?jǐn)?shù)據(jù)的定義。所有的樣本第j個屬性的頻率向量組合成為一個Dj維的成分?jǐn)?shù)據(jù)空間。Aitchison 距離為成分?jǐn)?shù)據(jù)進(jìn)行對稱對數(shù)比變換后的歐氏距離，可以更好地體現(xiàn)定合限制下不同維度之間的差異。使用樣本頻率向量與類中心頻率向量的Aitchison 距離作為相異性度量比使用拓展歐氏距離更好。由于樣本頻率向量中含有零值，而Aitchison距離無法度量含有零值的成分?jǐn)?shù)據(jù)，因此引入α度量。α度量[17]是由Tsagris 等針對成分?jǐn)?shù)據(jù)中不能處理含有零值數(shù)據(jù)的問題在2011年提出的。

定義7：設(shè)成分向量x=(x1,x2,…,xD)，進(jìn)行變換得到：

這種變換被稱為α-變換（α-transformation）。

定義8：對于任意的x,y?SD，定義x、y之間的α度量（α-metric）[18]為：

當(dāng)α→0 時，α度量為Aitchison 距離。當(dāng)α=1 時，α度量為維度D乘歐氏距離。

針對之前算法存在的問題，本文基于α度量，提出了一種更適合比較分類型數(shù)據(jù)差別的K-prototypes改進(jìn)算法（α-metric K-prototypes算法），見如下定義。

定義9：定義對象Xi與類中心Qz的距離為：

定義10：α-K-prototypes算法的目標(biāo)函數(shù)為：

算法2：α-K-prototypes算法

步驟1：從數(shù)據(jù)集X中隨機(jī)選取k個作為初始類中心。

步驟2：使用α度量計(jì)算某個數(shù)據(jù)與所有類中心的目標(biāo)函數(shù)，將數(shù)據(jù)分到使得目標(biāo)函數(shù)最小的類中，直至所有數(shù)據(jù)都完成分配。

步驟3：按照模糊類中心表達(dá)形式更新類中心。

步驟4：若步驟2、步驟3 計(jì)算出的距離總和未發(fā)生變化或達(dá)到迭代次數(shù)上限，則停止循環(huán)；否則重復(fù)進(jìn)行步驟2、步驟3。

算法2 中數(shù)據(jù)個數(shù)n、屬性個數(shù)m+p、類中心的個數(shù)k以及迭代次數(shù)t都會影響α-K-prototypes 算法的計(jì)算時間，最后得出α-K-prototypes 算法的時間復(fù)雜度為O(n(m+p)kt)。

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

2.1 權(quán)重調(diào)節(jié)系數(shù)

在α-K-prototypes 算法中，α度量具有一定的特殊性，當(dāng)α→0 時，α度量為Aitchison 距離；當(dāng)α=1 時，α度量為歐氏距離乘以頻率向量的維度Dj。假設(shè)樣本模糊類中心頻率向量x1=(1,0)，聚類中心的模糊類中心頻率向量q1=(0.5,0.5)，當(dāng)α=1 時，計(jì)算出的α度量為2；當(dāng)α=0.5時，計(jì)算出的值為8；當(dāng)α=0.1時，計(jì)算出的值為20000。α度量隨著α變小而逐漸增大，該數(shù)量級過大的主要原因是式中分母的α過小導(dǎo)致的。為了更好地在實(shí)際中應(yīng)用，對于式中的參數(shù)η，本文推薦使用η=λα2作為權(quán)重調(diào)整系數(shù)。在本文的系數(shù)確定中默認(rèn)分類型數(shù)據(jù)與數(shù)值型數(shù)據(jù)重要程度相等，所以λα2中取λ=1，即對象Xi與類中心Qz的距離為：

為體現(xiàn)權(quán)重調(diào)整系數(shù)的提升效果，在本文的對比中選取α=0.0001，并對比該系數(shù)對聚類效果的提升。從UCI數(shù)據(jù)庫中選取12個混合型數(shù)據(jù)對比驗(yàn)證設(shè)置調(diào)整系數(shù)后的指標(biāo)差距。圖1中由上到下分別為聚類精度（CA）[5]、調(diào)整的蘭特指數(shù)（ARI）[19]、標(biāo)準(zhǔn)互信息（NMI）[20]指標(biāo)下各數(shù)據(jù)集設(shè)置調(diào)整系數(shù)與不設(shè)置調(diào)整系數(shù)時的對比，其中設(shè)置調(diào)整系數(shù)即η=α2，不設(shè)置調(diào)整系數(shù)即η=1。從圖1可以看出，設(shè)置調(diào)整系數(shù)后效果僅在German數(shù)據(jù)集中有提升，在其他數(shù)據(jù)集上為持平或輕微提升。由于設(shè)置調(diào)整系數(shù)在實(shí)際應(yīng)用中有可解釋性，所以本文使用λα2作為權(quán)重調(diào)節(jié)系數(shù)。

圖1 調(diào)整系數(shù)對比

2.2 數(shù)據(jù)集的選擇與評價標(biāo)準(zhǔn)

為驗(yàn)證α-K-prototypes算法的有效性，將α-K-prototypes 算法與K-prototypes、K-centers、improved-K-prototypes算法進(jìn)行比較。從UCI數(shù)據(jù)庫中分別選取分類型和混合型數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對比。評價指標(biāo)包含CA、NMI、ARI。在不同評價標(biāo)準(zhǔn)下，將α-K-prototypes 算法與K-prototypes、K-centers、improved-K-prototypes 算法進(jìn)行比較。K-prototypes[5]、K-centers[6]算法中的參數(shù)γ設(shè)置為γ=1.5與γ=0.5，improved-K-prototypes[8]算法中參數(shù)設(shè)置為λ=8。

實(shí)驗(yàn)分析中選擇的數(shù)據(jù)集見表1，其中Agaricus、Hayes、Promoter、Tic-tac-toe 數(shù)據(jù)集均為分類型數(shù)據(jù)集，剩余3 個數(shù)據(jù)集Flag、German、Zoo均為混合型數(shù)據(jù)集。由于部分?jǐn)?shù)據(jù)集存在數(shù)據(jù)缺失情況，本文選擇直接刪除的方法。本文中涉及對比的部分均采用以相同初始點(diǎn)作為類中心進(jìn)行聚類重復(fù)運(yùn)行50次后計(jì)算得出的各評價指標(biāo)的平均值與方差進(jìn)行衡量。

表1 數(shù)據(jù)集信息描述

2.3 分類型數(shù)據(jù)聚類結(jié)果分析

選取表1 中的Agaricus、Hayes、Promoter、Tic-tac-toe，對比4種算法聚類結(jié)果在各指標(biāo)上的差別，計(jì)算結(jié)果如表2至表4所示。

表2 分類型數(shù)據(jù)CA指標(biāo)對比（均值±方差）

表3 分類型數(shù)據(jù)ARI指標(biāo)對比（均值±方差）

表4 分類型數(shù)據(jù)NMI指標(biāo)對比（均值±方差）

由表2 至表4 可以看出，Agaricus、Promoter 兩個數(shù)據(jù)集在α=1時效果最好，Hayes、Tic-tac-toe數(shù)據(jù)集在α較小時效果較好。在CA 指標(biāo)與ARI 指標(biāo)下，Agaricus、Hayes、Promoter、Tic-tac-toe 這4 個數(shù)據(jù)集分別在α=1，α=0.2，α=1，α=0.05 時效果最好。在NMI 指標(biāo)下，Agaricus、Hayes、Promoter、Tic-tac-toe 這4 個數(shù)據(jù)集分別在α=1，α=0.0001，α=1，α=0.8 時效果最好。選取表2 至表4 中α-K-prototypes 算法計(jì)算得出的最高數(shù)值作為α-K-prototypes 算法的結(jié)果，下頁圖2 給出4 種算法在3 種指標(biāo)下的結(jié)果比較，從左到右依次為CA指標(biāo)條形圖、ARI指標(biāo)條形圖、NMI指標(biāo)條形圖。從圖2可以看出，α-K-prototypes算法在計(jì)算分類型數(shù)據(jù)時效果是優(yōu)于其他3種算法的。

圖2 分類型數(shù)據(jù)集CA、ARI、NMI指標(biāo)對比

2.4 混合型數(shù)據(jù)聚類結(jié)果分析

選取表1 中的Flag、German、Zoo 這3 個混合型數(shù)據(jù)集，對比4 種算法聚類結(jié)果在各指標(biāo)上的差別，計(jì)算結(jié)果如下頁表5至表7所示。

表5 混合型數(shù)據(jù)CA指標(biāo)對比（均值±方差）

表6 混合型數(shù)據(jù)ARI指標(biāo)對比（均值±方差）

表7 混合型數(shù)據(jù)NMI指標(biāo)對比（均值±方差）

由表5 至表7 可以看出，F(xiàn)lag、German、Zoo 這3 個數(shù)據(jù)集在α較小時效果較好。在CA指標(biāo)與ARI指標(biāo)下，F(xiàn)lag、German、Zoo分別在α=0.2，α=0.0001，α=0.0001 時效果最好。在NMI 指標(biāo)下，F(xiàn)lag、German 兩個數(shù)據(jù)集分別在α=0.6，α=0.0001 時效果最好，Zoo 數(shù)據(jù)集在α=0.8 時略低于K-prototypes 算法。設(shè)定其中German、Zoo 兩個數(shù)據(jù)集的α-K-prototypes 算法α取值為0.0001。因?yàn)镕lag 數(shù)據(jù)集在α=1 時的各項(xiàng)指標(biāo)優(yōu)于在α=0.0001 時的各項(xiàng)指標(biāo)，為方便對比，設(shè)定Flag數(shù)據(jù)集的α-K-prototypes算法α取值為1。

圖3 給出了4 種算法在3 種指標(biāo)下的結(jié)果比較，從左到右依次為CA指標(biāo)條形圖、ARI指標(biāo)條形圖、NMI指標(biāo)條形圖。從圖3 可以看出，α-K-prototypes 算法在計(jì)算混合型數(shù)據(jù)時效果是優(yōu)于其他3種算法的。

圖3 混合型數(shù)據(jù)集CA、ARI、NMI指標(biāo)對比

2.5 顯著性檢驗(yàn)分析

表8 為置信度為95%的Wilcoxon 秩和檢驗(yàn)結(jié)果。檢驗(yàn)結(jié)果為1 表示在95%的置信度下認(rèn)為不同算法的指標(biāo)均值不相等，說明α-K-prototypes算法與其他算法在指定指標(biāo)下是有顯著差異的；檢驗(yàn)結(jié)果為0表示不同算法的指標(biāo)均值相等，認(rèn)為α-K-prototypes算法與其他算法在指定指標(biāo)下沒有顯著差異。由表8可以看出，在7個數(shù)據(jù)集上，α-K-prototypes算法與其他3種算法在CA、ARI、NMI指標(biāo)下均是有顯著差異的。

表8 提出算法與其他算法Wilcoxon秩和檢驗(yàn)結(jié)果h（p）

2.6 α 推薦準(zhǔn)則

在實(shí)際計(jì)算中，由于聚類的個數(shù)與樣本的標(biāo)簽是未知的，所以并不能通過對比聚類精度等指標(biāo)調(diào)整α。現(xiàn)給出一種較優(yōu)α推薦準(zhǔn)則。

定義11：第j個分類型屬性信息熵[21]為：

從UCI 數(shù)據(jù)庫中找出20 個數(shù)據(jù)集，其中包含11 個混合型數(shù)據(jù)集、9個分類型數(shù)據(jù)集。對于每個數(shù)據(jù)集，計(jì)算m個分類型屬性信息熵權(quán)重后，計(jì)算整體離散系數(shù)，計(jì)算結(jié)果如表9所示。

表9 數(shù)據(jù)集離散系數(shù)

圖4 為部分?jǐn)?shù)據(jù)集各指標(biāo)計(jì)算結(jié)果隨α變化的趨勢圖。從圖4 可以看出Auto、Soybean、Tae 數(shù)據(jù)集當(dāng)α=1 時在3 種指標(biāo)下效果優(yōu)于α→0 的結(jié)果，而Chess、Hayes、Lense數(shù)據(jù)集當(dāng)α→0 時在3種指標(biāo)下效果優(yōu)于α=1的結(jié)果。又由表2 至表7 中的結(jié)果發(fā)現(xiàn)，在實(shí)際應(yīng)用中α度量適用于α→0 或者α=1的情況，取其他值效果較好的情況較少，所以僅考慮α→0 以及α=1兩種情況。

圖4 部分?jǐn)?shù)據(jù)集指標(biāo)隨α 變化的趨勢

對比圖4 與表9，觀察數(shù)據(jù)集變化趨勢后發(fā)現(xiàn)α的取值與離散系數(shù)具有一定的關(guān)系，由此假設(shè)較優(yōu)α的計(jì)算準(zhǔn)則[22]為：

表10、表11分別給出了Vs<0.1與Vs≥0.1的數(shù)據(jù)集在α=0.0001和α=1下3種指標(biāo)的結(jié)果。為了檢驗(yàn)較優(yōu)α計(jì)算準(zhǔn)則是否在統(tǒng)計(jì)學(xué)上顯著，本文使用Wilcoxon秩和檢驗(yàn)進(jìn)行顯著性檢驗(yàn)。為了驗(yàn)證Vs<0.1數(shù)據(jù)集α=0.0001的結(jié)果顯著優(yōu)于α=1 的結(jié)果，記為α=0.0001 時不同數(shù)據(jù)集的CA指標(biāo)均值，為α=1時不同數(shù)據(jù)集的CA指標(biāo)均值，其余指標(biāo)類似。對于Vs<0.1 的數(shù)據(jù)集，原假設(shè)為α=0.0001時計(jì)算出的評價指標(biāo)大于等于α=1時計(jì)算出的評價指標(biāo)，備擇假設(shè)為α=0.0001時計(jì)算出的評價指標(biāo)小于α=1時計(jì)算出的評價指標(biāo)，具體結(jié)果見表12。表12中給出了Vs<0.1的數(shù)據(jù)集每種指標(biāo)下的原假設(shè)和備擇假設(shè)，以及每種檢驗(yàn)的P值，由于P值都大于0.05，因此不拒絕原假設(shè)，即α=0.0001時計(jì)算出的評價指標(biāo)顯著優(yōu)于α=1時計(jì)算出的評價指標(biāo)。對于Vs≥0.1 的數(shù)據(jù)集，原假設(shè)為α=0.0001時計(jì)算出的評價指標(biāo)小于等于α=1時計(jì)算出的評價指標(biāo)，備擇假設(shè)為α=0.0001時計(jì)算出的評價指標(biāo)大于α=1時計(jì)算出的評價指標(biāo)，具體計(jì)算結(jié)果見表13。表13 中給出了Vs≥0.1的數(shù)據(jù)集每種指標(biāo)下的原假設(shè)和備擇假設(shè)，以及每種檢驗(yàn)的P值，由于P值都大于0.05，因此不拒絕原假設(shè)，即α=1時計(jì)算出的評價指標(biāo)顯著優(yōu)于α=0.0001時計(jì)算出的評價指標(biāo)。由此說明較優(yōu)α計(jì)算準(zhǔn)則在統(tǒng)計(jì)學(xué)上是顯著的。

表10 Vs<0.1的數(shù)據(jù)集在α-K-prototypes算法下的指標(biāo)

表11 Vs ≥0.1的數(shù)據(jù)集在α-K-prototypes算法下的指標(biāo)

表12 Vs<0.1時較優(yōu)α 計(jì)算準(zhǔn)則Wilcoxon秩和檢驗(yàn)結(jié)果

表13 Vs ≥0.1時較優(yōu)α 計(jì)算準(zhǔn)則Wilcoxon秩和檢驗(yàn)結(jié)果

由上述計(jì)算可以認(rèn)為，當(dāng)Vs≥0.1時，數(shù)據(jù)集包含的數(shù)據(jù)量更多、各樣本間的差異更大，所以離散系數(shù)更大，此時使用歐氏距離計(jì)算，即α=1。當(dāng)Vs<0.1 時，數(shù)據(jù)集包含的信息量較少、各樣本間的差異較小，所以離散系數(shù)較小，此時使用Aitchison距離會分辨出各樣本間的差異，以更好地區(qū)分應(yīng)該屬于不同類別的樣本，即α→0。

3 結(jié)束語

在大數(shù)據(jù)背景下，混合型數(shù)據(jù)越來越多。其中分類型數(shù)據(jù)部分的類中心表現(xiàn)形式符合成分?jǐn)?shù)據(jù)定義，所以本文提出一種融合α度量的K-prototypes算法。針對α度量在α較小的時候距離太大的問題，加入λα2作為分類型數(shù)據(jù)的權(quán)重調(diào)整系數(shù)，使得α度量在不影響聚類甚至提高聚類精度的前提下更具有解釋性。最后基于實(shí)際應(yīng)用，給出了較優(yōu)α計(jì)算準(zhǔn)則。α-K-prototypes 算法引入了成分?jǐn)?shù)據(jù)的分析方法度量分類型數(shù)據(jù)的相異性。在多個數(shù)據(jù)集上實(shí)驗(yàn)對比后，證明了α-K-prototypes算法在分類型數(shù)據(jù)和混合型數(shù)據(jù)中均有比較明顯的提升作用，且在統(tǒng)計(jì)意義上顯著區(qū)別于其他三種算法。