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

摘要：提出了一種新的基于PCA和K－均值聚類的有監督二叉分裂層次聚類方法PCASHC，用K－均值聚類進行逐次二叉聚簇分裂，選擇PCA第一主成分相距最遠樣本點作為K－均值聚類初始聚簇中心，解決了K－均值聚類初始中心隨機選擇導致結果不確定的問題，用聚簇樣本類別方差作為聚簇樣本不純度控制聚簇分裂水平，避免過擬合，可學習到合適的聚類數目。用四組UCI標準數據集對其進行了10折交叉驗證分類誤差檢驗，與另外七種分類器相比說明PCASHC有較高的分類精度。

關鍵詞：數據挖掘； 機器學習； 有監督聚類； 分裂層次聚類

中圖分類號：TP301文獻標志碼：A

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

0引言

聚類分析依照物以類聚原理將研究對象分組，可以提供樣本分布的結構信息，是一種重要數據挖掘方法，在自然科學和社會科學中得到廣泛應用。經典聚類方法是無監督學習方法，要預先指定聚簇數目，如果聚簇數目不正確，無法得到正確聚類結果。因此正確的聚簇數目是很重要的聚類參數和樣本結構信息，從樣本特征數據中學習到合適的聚簇數目意義重大。

K－均值聚類方法和層次聚類方法都需要提供正確的聚簇數目。前人曾用逐步增加聚簇數目的K－均值聚類或層次聚類方法尋找正確的聚簇數目，但拐點不明顯時無法使用[1]。

為了通過數據挖掘從樣本特征數據中學習到正確的聚簇數目，可以利用帶有類別標簽的樣本進行有監督聚類。有監督聚類因有樣本類別標簽分布信息的教師監督信號，極大地降低了信息的不確定性，工作效率較高，分類結果為明確的真實類別，能反映出子類等樣本分布結構。

有監督聚類的目的是找出劃分樣本為聚簇內樣本純度大而數量盡可能少的聚簇聚類方案。現有多種形式，如學習向量量化網絡[2，3]、基于劃分和增量的動態聚類方法[4，5]、支持向量機[5]等。學習向量量化網絡在競爭學習網絡中按分類結果對錯進行獎懲來調整權值學習。基于劃分和增量的動態聚類方法常用聚簇內類別不純度懲罰指標最小化方法。支持向量機結合樣本類別的約束信息，通過核函數非線性映射到高維希爾伯特空間，使其在新的空間中同類樣本相聚一起，異類樣本分離加大，可以用超平面劃分，實現有監督聚類。這些方法在要求指定聚簇數目、學習及分類效率和提供顯式的子類分布結構信息上各有長短。

K－均值聚類（又稱C－均值聚類）是一種普遍采用的基于劃分的動態聚類方法，是在選定的相似性距離度量和評價聚類結果質量的準則函數基礎上給定某個初始分類后，用迭代算法找出使準則函數取極值的最好聚類結果[1]。其最佳初始劃分尚無解決良方，現多用隨機方法，有較大不確定性。

非監督的增量逐次K－均值聚類法有時可以學習聚簇數目。它是通過逐漸增加聚簇數目K和進行K－均值聚類法，直到評價聚類結果質量的準則函數值對K的變化率達到一個拐點時停止，此時的K作為正確的聚類數目。如果沒有明顯的拐點，則此法失效。

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

合并層次聚類算法計算復雜度較大，為固定的O(N2)，只能用于中小樣本學習;分裂層次聚類法可用K－均值聚類法等基于劃分的動態聚類方法進行分裂，計算復雜度隨樣本分布情況而變化，最好時與K－均值聚類法相同，為O(N)，多數近于O(N log2(N))，極為罕見的極端分布最差時為O(N2)。因為是在已有聚簇基礎上進行繼續分裂，所以比每次從頭開始的增量逐次K－均值聚類法計算量要小。

用有監督逐步增加聚簇數目的K－均值聚類或層次聚類方法可以找到正確的聚簇數目，但合并層次聚類方法計算復雜度較大。因K－均值聚類初始化困難而多用隨機初始化，帶來了K－均值聚類結果不確定問題。

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

1原理和算法

1．1原理

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

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

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

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

在不斷分裂的層次聚類過程中可以通過類別不純度及其閾值來控制擬合程度：當聚簇樣本類別的不純度小于閾值時，聚簇停止分裂；否則繼續分裂成更小的子聚簇。

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

2．1．2PCASHC分類方法

用PCASHC把已知類別訓練樣本聚類成若干聚簇，用MATLAB統計工具箱的線性分類器classify和訓練樣本及其聚簇類把待測樣本分類成聚簇類別，按聚簇類原來的模式類別變換成模式類別。

2．1．3測試方法

本實驗以10組交叉驗證的方式，將樣本材料隨機分成10組，每組輪流當測試樣本， 其余為訓練樣本，如此執行完10次后，得到了10組分類誤差率，共進行10次，把分類誤差率作為該樣本集的平均誤差率。

2．1．4實驗結果分析

用目前具有一定代表性的七種分類器對此四個數據集進行分類的10折交叉驗證結果進行了比較，對比數據來源于網頁[9]。

由表1和圖1可見，在分類器對Ecoli、Glass、Iris和Wine 四種數據集的分類誤差當中，PCASHC有兩項最好（其中對Ecoli數據集各種分類器誤差都較大時SHCC誤差最小），兩項第二，說明PCASHC分類精度較高。

3結束語

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

參考文獻：

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

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

[3]程劍鋒，徐俊艷.基于EM 算法的有監督LVQ神經網絡及其應用[J].系統工程與電子技術，2005，27(1):121－123.

[4]宋彤，宋保強.一種新的監督聚類學習方法及其在故障診斷中的應用[J].計算機工程與科學， 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].北京:機械工業出版社，2003:442-447.

[7]趙鵬大，胡旺亮，李紫金. 礦床統計預測[M].北京:地質出版社，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.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”