基于ＰＣＡ和Ｋ－均值聚類的有監(jiān)督分裂層次聚類方法

摘要：提出了一種新的基于PCA和K－均值聚類的有監(jiān)督二叉分裂層次聚類方法PCASHC，用K－均值聚類進(jìn)行逐次二叉聚簇分裂，選擇PCA第一主成分相距最遠(yuǎn)樣本點(diǎn)作為K－均值聚類初始聚簇中心，解決了K－均值聚類初始中心隨機(jī)選擇導(dǎo)致結(jié)果不確定的問(wèn)題，用聚簇樣本類別方差作為聚簇樣本不純度控制聚簇分裂水平，避免過(guò)擬合，可學(xué)習(xí)到合適的聚類數(shù)目。用四組UCI標(biāo)準(zhǔn)數(shù)據(jù)集對(duì)其進(jìn)行了10折交叉驗(yàn)證分類誤差檢驗(yàn)，與另外七種分類器相比說(shuō)明PCASHC有較高的分類精度。

關(guān)鍵詞：數(shù)據(jù)挖掘； 機(jī)器學(xué)習(xí)； 有監(jiān)督聚類； 分裂層次聚類

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)05-1412-03

0引言

聚類分析依照物以類聚原理將研究對(duì)象分組，可以提供樣本分布的結(jié)構(gòu)信息，是一種重要數(shù)據(jù)挖掘方法，在自然科學(xué)和社會(huì)科學(xué)中得到廣泛應(yīng)用。經(jīng)典聚類方法是無(wú)監(jiān)督學(xué)習(xí)方法，要預(yù)先指定聚簇?cái)?shù)目，如果聚簇?cái)?shù)目不正確，無(wú)法得到正確聚類結(jié)果。因此正確的聚簇?cái)?shù)目是很重要的聚類參數(shù)和樣本結(jié)構(gòu)信息，從樣本特征數(shù)據(jù)中學(xué)習(xí)到合適的聚簇?cái)?shù)目意義重大。

K－均值聚類方法和層次聚類方法都需要提供正確的聚簇?cái)?shù)目。前人曾用逐步增加聚簇?cái)?shù)目的K－均值聚類或?qū)哟尉垲惙椒▽ふ艺_的聚簇?cái)?shù)目，但拐點(diǎn)不明顯時(shí)無(wú)法使用[1]。

為了通過(guò)數(shù)據(jù)挖掘從樣本特征數(shù)據(jù)中學(xué)習(xí)到正確的聚簇?cái)?shù)目，可以利用帶有類別標(biāo)簽的樣本進(jìn)行有監(jiān)督聚類。有監(jiān)督聚類因有樣本類別標(biāo)簽分布信息的教師監(jiān)督信號(hào)，極大地降低了信息的不確定性，工作效率較高，分類結(jié)果為明確的真實(shí)類別，能反映出子類等樣本分布結(jié)構(gòu)。

有監(jiān)督聚類的目的是找出劃分樣本為聚簇內(nèi)樣本純度大而數(shù)量盡可能少的聚簇聚類方案?，F(xiàn)有多種形式，如學(xué)習(xí)向量量化網(wǎng)絡(luò)[2，3]、基于劃分和增量的動(dòng)態(tài)聚類方法[4，5]、支持向量機(jī)[5]等。學(xué)習(xí)向量量化網(wǎng)絡(luò)在競(jìng)爭(zhēng)學(xué)習(xí)網(wǎng)絡(luò)中按分類結(jié)果對(duì)錯(cuò)進(jìn)行獎(jiǎng)懲來(lái)調(diào)整權(quán)值學(xué)習(xí)?；趧澐趾驮隽康膭?dòng)態(tài)聚類方法常用聚簇內(nèi)類別不純度懲罰指標(biāo)最小化方法。支持向量機(jī)結(jié)合樣本類別的約束信息，通過(guò)核函數(shù)非線性映射到高維希爾伯特空間，使其在新的空間中同類樣本相聚一起，異類樣本分離加大，可以用超平面劃分，實(shí)現(xiàn)有監(jiān)督聚類。這些方法在要求指定聚簇?cái)?shù)目、學(xué)習(xí)及分類效率和提供顯式的子類分布結(jié)構(gòu)信息上各有長(zhǎng)短。

K－均值聚類（又稱C－均值聚類）是一種普遍采用的基于劃分的動(dòng)態(tài)聚類方法，是在選定的相似性距離度量和評(píng)價(jià)聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù)基礎(chǔ)上給定某個(gè)初始分類后，用迭代算法找出使準(zhǔn)則函數(shù)取極值的最好聚類結(jié)果[1]。其最佳初始劃分尚無(wú)解決良方，現(xiàn)多用隨機(jī)方法，有較大不確定性。

非監(jiān)督的增量逐次K－均值聚類法有時(shí)可以學(xué)習(xí)聚簇?cái)?shù)目。它是通過(guò)逐漸增加聚簇?cái)?shù)目K和進(jìn)行K－均值聚類法，直到評(píng)價(jià)聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù)值對(duì)K的變化率達(dá)到一個(gè)拐點(diǎn)時(shí)停止，此時(shí)的K作為正確的聚類數(shù)目。如果沒(méi)有明顯的拐點(diǎn)，則此法失效。

層次聚類分析也是一種普遍采用的主要聚類方法[1，6，7]，用指定的樣本相似性距離度量和聚簇間相似性距離度量，用合并或分裂手段，把樣本從每個(gè)樣本自成一簇到所有樣本全為一簇的多級(jí)層次聚簇樹(shù)，但要靠人為指定聚簇?cái)?shù)目等參數(shù)來(lái)將其劃分為若干子聚簇。

合并層次聚類算法計(jì)算復(fù)雜度較大，為固定的O(N2)，只能用于中小樣本學(xué)習(xí);分裂層次聚類法可用K－均值聚類法等基于劃分的動(dòng)態(tài)聚類方法進(jìn)行分裂，計(jì)算復(fù)雜度隨樣本分布情況而變化，最好時(shí)與K－均值聚類法相同，為O(N)，多數(shù)近于O(N log2(N))，極為罕見(jiàn)的極端分布最差時(shí)為O(N2)。因?yàn)槭窃谝延芯鄞鼗A(chǔ)上進(jìn)行繼續(xù)分裂，所以比每次從頭開(kāi)始的增量逐次K－均值聚類法計(jì)算量要小。

用有監(jiān)督逐步增加聚簇?cái)?shù)目的K－均值聚類或?qū)哟尉垲惙椒梢哉业秸_的聚簇?cái)?shù)目，但合并層次聚類方法計(jì)算復(fù)雜度較大。因K－均值聚類初始化困難而多用隨機(jī)初始化，帶來(lái)了K－均值聚類結(jié)果不確定問(wèn)題。

為此本文提出了一種新的有監(jiān)督聚類方法，即主成分有監(jiān)督層次聚類方法(PCA supervised hierarchy clustering，PCASHC)。它用聚簇內(nèi)樣本不純度作為停止分裂的準(zhǔn)則函數(shù)進(jìn)行逐次二叉層次分裂，以聚簇樣本類別方差作為不純度測(cè)度，聚簇分裂用兩類K－均值聚類方法，用PCA第一主成分進(jìn)行確定性初始化的K－均值聚類，消除了通常K－均值聚類因隨機(jī)初始化引起的聚類結(jié)果不確定性，可學(xué)習(xí)到合適的聚簇?cái)?shù)目，學(xué)習(xí)效率較高。用多組UCI標(biāo)準(zhǔn)數(shù)據(jù)對(duì)其進(jìn)行了檢驗(yàn)，其結(jié)果與其他七種分類器比較，證明此方法有較高的分類精度。

1原理和算法

1．1原理

有監(jiān)督聚類的目標(biāo)是劃分出類別不純度最小的盡可能少的聚簇集合。分裂層次有監(jiān)督聚類是從所有樣本為一類開(kāi)始不斷分裂聚簇成多個(gè)子聚簇，直到聚簇樣本類別不純度小于指定閾值時(shí)停止。用K－均值聚類分裂層次有監(jiān)督聚類是用K－均值聚類方法把聚簇分裂成兩個(gè)或多個(gè)子聚簇。 K－均值聚類的主要問(wèn)題是初始化困難和隨機(jī)初始化帶來(lái)的結(jié)果不確定性問(wèn)題，這可用主成分分析方法解決。

主成分分析（principal component analysis，PCA）是一種把原來(lái)由多個(gè)變量表示的樣本轉(zhuǎn)換為可用較少的互不相關(guān)的新綜合變量表示的統(tǒng)計(jì)方法。新的綜合變量由多個(gè)原有變量線性組合而成，稱為主成分，可以通過(guò)計(jì)算特征值方法求得。然后在有用信息丟失最少的原則下保留特征值大的那部分主成分，舍棄那些僅含少量信息的主成分，從而達(dá)到降低維數(shù)的目的。其公式推導(dǎo)如下：

主成分分析中最大特征值λ1對(duì)應(yīng)的第一主成分u1在樣本屬性空間方差最大，延伸最長(zhǎng)，變量載荷最大，擁有樣本信息量最大。根據(jù)這個(gè)特點(diǎn)，可用相距最遠(yuǎn)的聚簇樣本第一主成分最大值和最小值作為兩個(gè)初始聚簇中心，進(jìn)行兩類K－均值聚類。由于這是確定性過(guò)程，解決了K－均值聚類方法分裂時(shí)其初始化聚簇難以確定和因初始值隨機(jī)選取而產(chǎn)生的結(jié)果不確定問(wèn)題。

在樣本屬性向量空間中，每個(gè)樣本為一點(diǎn)。兩個(gè)樣本點(diǎn)之間距離表示其不相似的程度，相距越近越相似。聚類是把相似的樣本劃為一組。但相似是相對(duì)的，所以聚類可以有不同層次級(jí)別：從每個(gè)樣本各自為一聚簇到所有樣本全為一聚簇，如果后者為擬合不足的話，前者則可能是擬合過(guò)度了，一般是介于這兩者之間的某個(gè)劃分。如何判斷是最佳擬合的聚簇劃分呢？帶類別樣本的分布提供了從分類角度判斷最佳聚簇劃分的信息。

在不斷分裂的層次聚類過(guò)程中可以通過(guò)類別不純度及其閾值來(lái)控制擬合程度：當(dāng)聚簇樣本類別的不純度小于閾值時(shí)，聚簇停止分裂；否則繼續(xù)分裂成更小的子聚簇。

聚簇樣本類別方差var(y)可以表示聚簇樣本的類別不純度，因此將其作為測(cè)度聚簇類別不純度的指標(biāo)。

2．1．2PCASHC分類方法

用PCASHC把已知類別訓(xùn)練樣本聚類成若干聚簇，用MATLAB統(tǒng)計(jì)工具箱的線性分類器classify和訓(xùn)練樣本及其聚簇類把待測(cè)樣本分類成聚簇類別，按聚簇類原來(lái)的模式類別變換成模式類別。

2．1．3測(cè)試方法

本實(shí)驗(yàn)以10組交叉驗(yàn)證的方式，將樣本材料隨機(jī)分成10組，每組輪流當(dāng)測(cè)試樣本， 其余為訓(xùn)練樣本，如此執(zhí)行完10次后，得到了10組分類誤差率，共進(jìn)行10次，把分類誤差率作為該樣本集的平均誤差率。

2．1．4實(shí)驗(yàn)結(jié)果分析

用目前具有一定代表性的七種分類器對(duì)此四個(gè)數(shù)據(jù)集進(jìn)行分類的10折交叉驗(yàn)證結(jié)果進(jìn)行了比較，對(duì)比數(shù)據(jù)來(lái)源于網(wǎng)頁(yè)[9]。

由表1和圖1可見(jiàn)，在分類器對(duì)Ecoli、Glass、Iris和Wine 四種數(shù)據(jù)集的分類誤差當(dāng)中，PCASHC有兩項(xiàng)最好（其中對(duì)Ecoli數(shù)據(jù)集各種分類器誤差都較大時(shí)SHCC誤差最?。瑑身?xiàng)第二，說(shuō)明PCASHC分類精度較高。

3結(jié)束語(yǔ)

理論和實(shí)驗(yàn)說(shuō)明：a）基于PCA和K－均值聚類的有監(jiān)督二叉分裂層次聚類方法是一種性能良好的有監(jiān)督學(xué)習(xí)方法，可由樣本類別分布信息自動(dòng)學(xué)習(xí)到聚簇?cái)?shù)目。b）用PCA第一主成分相距最遠(yuǎn)的二極端值樣本點(diǎn)作為初始聚簇中心來(lái)作二叉分裂K－均值聚類可得到確定性結(jié)果，避免了K－均值聚類的初值不確定性。c）用聚簇樣本類別方差作為聚簇樣本不純度控制聚簇分裂水平，使之達(dá)到最佳擬合，可自動(dòng)學(xué)習(xí)到有監(jiān)督聚類的最優(yōu)化聚簇劃分，無(wú)須人為指定聚簇間距離閾值、指定聚簇?cái)?shù)目或劃分最大樹(shù)深度等劃分聚簇的參數(shù)。聚簇樣本類別方差閾值默認(rèn)值為0，此時(shí)聚類結(jié)果為類別純凈的同類聚簇。d）PCASHC與分類器組合成的有監(jiān)督層次聚類分類器對(duì)四組UCI標(biāo)準(zhǔn)數(shù)據(jù)的10組交叉驗(yàn)證分類結(jié)果與七種其他代表性的分類器比較，具有較高的分類精度。

參考文獻(xiàn)：

[1]邊肇祺，張學(xué)工.模式識(shí)別[M].2版.北京:清華大學(xué)出版社， 2000:235-237.

[2]KOHONEN T. The self－learning map[J]. Proc of IEEE， 1990，78:1464－1480.

[3]程劍鋒，徐俊艷.基于EM 算法的有監(jiān)督LVQ神經(jīng)網(wǎng)絡(luò)及其應(yīng)用[J].系統(tǒng)工程與電子技術(shù)，2005，27(1):121－123.

[4]宋彤，宋保強(qiáng).一種新的監(jiān)督聚類學(xué)習(xí)方法及其在故障診斷中的應(yīng)用[J].計(jì)算機(jī)工程與科學(xué)， 2001，23(5):63-69.

[5]DETTLING M， BUHLMANN P. Supervised clustering of genes[C]//Proc of the 15th Conference in Computational Statistics. 2002.

[6]DUDA R O， HART P E， STORK D G.模式分類 [M].北京:機(jī)械工業(yè)出版社，2003:442-447.

[7]趙鵬大，胡旺亮，李紫金. 礦床統(tǒng)計(jì)預(yù)測(cè)[M].北京:地質(zhì)出版社，1983:157－161.

[8]NEWMAN D J， HETTICH S， BLAKE C L， et al.UCI repository of machine learning databases[EB/OL].(2006－10-06).http://www.ics.uci.edu/~mlearn/MLRepository.html.

[9][EB/OL].(2006－10-06).http://finalfantasyxi.inf.cs.cmu.edu/MATLABArsenal/MATLABArsenal.htm.

[10]FINLEY T， JOACHIMS T. Supervised clustering with support vector machines[C]//Proc of the 22nd International Conference on Machine Learning. Bonn:[s.n.]， 2005.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”