基于半監督學習的K-均值聚類算法研究

摘 要:定義了一個歐氏距離和監督信息相混合的新的最近鄰計算函數，從而將K-均值算法很好地應用于半監督聚類問題。針對K-均值算法初始質心敏感的缺陷，用粒子群算法的搜索空間模擬聚類的歐氏空間，迭代搜索找到較優的聚類質心，同時提出動態管理種群的策略以提高粒子群算法搜索效率。算法在UCI的多個數據集上測試都得到了較好的聚類準確率。

關鍵詞:半監督聚類; 改進的K-均值算法; 動態管理種群的粒子群算法

中圖分類號:TP311.13;TP18 文獻標志碼:A

文章編號:1001-3695(2010)03-0913-04

doi:10.3969/j.issn.1001-3695.2010.03.029

Semi-supervised learning based on K-means clustering algorithm

LIU Tao1， YIN Hong-jian2

(1.Dept. of Information Technology， Zhengzhou Teachers College， Zhengzhou 450044， China; 2.Computing Center of Information，Hunan Vocational College of Chemical， Zhuzhou Hunan 412004， China)

Abstract:This paper constructed a new classified function which mixed Euclidean distance with supervising information. Taking into account that K-means algorithm was sensitive to the initial center， used search space of particle swarm algorithm was used to simulate the clustering Euclidean space to find a better cluster center of clustering. At the same time， brought up a strategy of species dynamic management to improve the efficiency of particle swarm optimization search. The algorithm got a good clustering accuracy on a number of UCI testing data sets.

Key words:semi-supervised clustering; improved K-means algorithm; species particle swarm optimization based on the dynamic management

0 引言

近年來，數據挖掘技術得到迅速發展，聚類分析作為數據挖掘領域最為常用的技術之一也越來越頻繁地出現在實際應用領域，從而越來越多地引起人們的關注。半監督聚類是近幾年提出的一種新型聚類方法，它綜合了無監督學習和有監督學習的特點，提高了聚類質量，是近年來數據挖掘機器學習和模式識別領域的重要研究方向之一。半監督聚類的優越性主要在于針對無標簽樣本進行聚類時，可利用少量有監督的樣本信息。因此，如何在聚類算法中更好地利用有標簽樣本所包含的領域知識指導聚類過程，是進一步提高聚類質量的關鍵問題之一。

目前，半監督的聚類方法大致分為基于限制和基于距離測度函數學習兩類。前者在聚類過程中，利用帶標簽樣本信息對聚類過程進行約束，最終得到一個適當的劃分結果。具體的做法是:修改聚類的目標函數以滿足給定的約束，在聚類過程中遵循約束條件，利用帶標簽樣本信息初始化聚類參數并在聚類過程中約束數據的劃分。后者是基于某一距離測度函數進行聚類，在該方法中所使用的距離測度函數是通過對標簽數據學習所得到的更為可靠的距離測度函數。

目前，大多數半監督聚類算法來源于傳統聚類算法，由傳統聚類算法針對引入的有監督樣本信息進行擴展。其中，K-均值算法作為一種簡單高效的聚類算法，成為最早被擴展至半監督領域的方法之一，人們提出了若干種半監督K-均值聚類算法。其中，文獻[1]提出了一種基于遺傳算法的半監督K-均值聚類算法。其基本思想是:將離散度這一無監督聚類質量評價指標與聚類精度這一有監督分類質量評價指標組合為一個綜合性的半監督聚類質量評價指標，將這一指標作為目標函數，應用遺傳算法進行聚類的樣本劃分優化。在優化過程中，每個染色體編碼對應于傳統K-均值算法中的一組聚類中心。文獻[1]的實驗研究表明，該算法可獲得較高的聚類質量，但仍有一些需改進的問題。

首先在決定每個樣本劃分到k個簇中時，上述算法依然采用傳統的歐氏距離，這忽略了領域知識，使得已有標簽數據并沒有發揮監督作用。其次，在使用遺傳算法時，由于聚類中心編碼串的無序性，兩條染色體在等位基因之間，在空間位置上并不互相對應，當染色體所對應的聚類質心接近最優時，需要相對局部調整，而遺傳算法最重要的操作——交叉變異，會使質心位置劇烈振蕩，不但不會很有效地向最優質心靠攏，而且會使交叉變異后的染色體遠離最優初始聚類質心。

針對上述問題，本文提出了一種基于動態粒子群算法的改進半監督K-均值聚類算法PSO-Kmeans。該算法采用動態粒子群算法的搜索空間模擬所有聚類樣本的歐氏空間，用每個粒子的位置代表一組聚類質心，然后分別用K-均值算法聚類，計算適應函數，不斷迭代搜索，通過質心優化來獲得較好的聚類效果。根據半監督聚類的特點， 定義了一個歐氏距離與監督信息相結合的新的聚類質量評價函數，從而將K-均值算法很好地應用于半監督聚類問題。改進后的算法通過在UCI多個常用數據集上測試都取得了較優的聚類結果。

1 基于遺傳算法及K-均值算法的半監督聚類

半監督聚類是在大量無標簽數據中加入少量的有監督信息，以幫助聚類算法獲得更好的聚類效果。在實際應用中，有監督樣本信息表現形式有兩類，第一類是已知部分待聚類樣本的標簽，在聚類時就需要盡量把相同標簽的劃分成同一個簇，而不同標簽的盡量不在同一個簇;第二類是已知部分樣本的must-link或cannot-link點對信息，在聚類時就要求盡可能將受must-link約束的點對劃分至相同的簇，而將受cannot-link約束的點對劃分至不同的簇。從上述分析也可以看出，兩類有監督信息是類似且相通的，第一類有監督信息可方便地轉換為第二類。聚類質量評價指標是聚類分析的核心研究內容之一，傳統上主要采用聚類的類內緊致度及類間離散度來度量，要求類內緊致度及類間離散度盡可能大。而對半監督聚類質量的評價，除了考慮上述問題外，還需要考慮對有監督信息的滿足程度。

文獻[1]討論的是已知部分樣本標簽條件下的半監督聚類問題，提出了一種基于遺傳算法及K-均值聚類算法的半監督聚類方法。遺傳算法的每個隨機生成的染色體代表選擇的k個聚類中心向量，然后利用傳統K-均值聚類算法形成對應的聚類結果，而對此聚類結果的質量評價則成為該染色體的適應度。在評價聚類質量時，將傳統的基于類內緊致度和類間離散度的質量度量與針對部分有標簽樣本的聚類精度度量進行線性組合，形成一種綜合性的聚類質量度量。文獻[1]給出的實驗結果驗證了該算法的有效性，但是仍有一些不足之處。

首先，針對每個染色體所對應的聚類中心，采用傳統的K-均值聚類形成聚類結果，這意味著對有標簽數據的劃分仍然遵循歐氏距離最小原則，而忽視其標簽信息所隱含的約束條件。如圖1所示，其中三角形和菱形分別代表不同標簽的數據，圓形代表沒有標簽的數據，根據歐氏距離，樣本a應該劃分到B中，因為與簇A的歐氏距離稍大于B;然而由于簇中大部分是與a相同標簽的數據(即三角形)，根據領域知識，a應該劃分到A中。另外在應用遺傳算法時，染色體編碼表示聚類初始質心向量。產生下一代染色體通過交叉變異完成。交叉實際上是原有基因的重新組合，變異是隨機突變。當問題的解空間有限和離散時，遺傳算法可以通過基因重組和適當的變異搜索到較優的解。但對于搜索聚類的最優初始中心向量這樣的連續問題，交叉操作實際上進行的是多組初始中心向量的組合交換，并未生成新的初始中心向量或者向較優的初始中心向量移動。這使得獲得新的更優的初始中心向量的重任主要由變異來實現，這就大大降低了獲得更好的初始中心向量的概率。

針對上述問題可從如下方面進行改進:a)在決定把一個樣本劃入哪個簇時，對于無標簽數據，可根據其與質心的距離來決定;而對于帶標簽數據，則需要綜合考慮距離和類別標簽信息來確定。b)由于粒子群算法在搜索連續空間最優解方面具有天然的優勢，可以考慮采樣粒子群優化(PSO)算法代替遺傳算法進行聚類初始中心向量的尋優。下面首先介紹傳統的粒子群算法并提出一種新的基于動態粒子管理的粒子群算法。

2 動態粒子群優化算法

PSO算法是一種進化計算技術，源于對鳥群捕食的行為模擬，由Eberhart等人提出。系統首先初始化為一組隨機解， 通過迭代搜尋最優值。算法將粒子，也就是優化問題的解視為搜索空間中連續的點，這對于求解面向K-均值聚類最優初始中心向量非常有利。所有的粒子都有一個表示當前在解空間中位置的屬性Xi=(xi1，xi2，…，xin)，并由評價函數確定其適應度，每個粒子還有一個速度向量Vi=(vi1，vi2，…，vin)決定其運動的方向和距離。粒子之間通過共享當前最優粒子信息，在解空間中搜索。首先粒子群初始化為一群隨機粒子(隨機解)，然后通過迭代來尋找最優解。在每一輪的迭代中， 粒子通過速度更新當前位置，并通過適應值函數計算出其適應度，然后根據式(1)更新其當前速度。

Vi=ωVi+c1×rand()×(Pbesti-xi)+

c2×rand()(Gbesti-xi)(1)

接著按照式(2)更新粒子位置Xi。

Xi=Xi+Vi(2)

其中:Pbest表示粒子i的局部最優值， 即粒子i目前為止在搜索空間中到過的最佳點;Gbest表示整個粒子群的全局最優值， 即整個粒子群到目前為止在搜索空間中到過的最佳點;c1和c2是兩個正的常數，稱為學習因子;rand()表示0~1的隨機數;ω非負，稱為慣性因子，ω值較大，全局尋優能力強，局部尋優能力弱，若ω值較小則情況相反。根據上述PSO的粒子定義及粒子更新式(1)(2)可知，PSO的粒子采用連續值，因此較適合于求解連續值域上的數值優化問題。

粒子群算法的時空復雜度主要與粒子的數目大小有關，傳統上，粒子數目預先設定為一個固定值。在粒子群算法的搜索空間中，全局最優只有一個，粒子處于向全局最優移動的過程中，部分粒子對當前搜索并未起到實質性的促進作用。這就啟發了可以將一些無用的粒子刪除，或者動態增加一些更有促進作用的新粒子，從而提高算法的時空效率。因此提出如下方案進行種群的動態管理:

a)當粒子群全局最優連續s(s代表了種群管理的敏感度，s越小種群變化越頻繁)次沒有改變，說明現有種群需要新的粒子來提供啟發信息，則動態添加一個粒子，并用個體最優頻繁被更新的兩個粒子的位置組合成初始位置，以全部粒子的平均速度作為初始速度。

b)當粒子群全局最優連續s次改變，說明現有種群啟發信息已經有多余，則動態刪除個體最優更新最不頻繁的粒子。

c)若達到粒子種群數量上限，并需要提供新的粒子時，則動態添加一個粒子替換掉個體最優最近更新最不頻繁非全局最優粒子，并用個體最優頻繁被更新的兩個粒子的位置組合成初始位置，以全部粒子的平均速度作為初始速度。

加入動態管理種群后的粒子群算法，刪除了無用粒子，節省了運行時間，增加了新的粒子提高搜索能力，避免了陷入局部最優。

3 動態管理種群與K-均值結合算法——PSO-Kmeans

針對以上分析，提出粒子群算法與K-均值算法相結合的半監督聚類算法——PSO-Kmeans。算法在每一次粒子群迭代中都運行改進的K-均值算法，用聚類結果評價作為粒子適應度。

3.1 改進的樣本劃分判定函數

從第1章的分析可知，當樣本是有標簽數據時，把樣本劃分到與質心歐氏距離最近的簇中的做法并不能很好地利用領域知識，需要綜合考慮質心距離和簇中已有標簽數據的類別以及數量情況。因此作如下定義:

對于任一樣本數據Xi以及某個樣本集合Cj，定義函數

semi(Xi，Cj)=cannot_linked(Xi，Cj)+different(Xi，Cj)-(must_linked(Xi，Cj)+same(Xi，Cj))(3)

其中:cannot_linked(Xi，Cj)表示集合Cj中與Xi有cannot_linked 關系的樣本個數;different(Xi，Cj)表示集合Cj中與Xi具有不同類別標簽的樣本個數;must_linked(Xi，Cj)表示集合Cj中與Xi有must_linked 關系的樣本個數;same(Xi，Cj)表示集合Cj中與Xi有相同類別標簽的樣本個數。此外，若Xi是無標簽數據，則semi函數的值為0。

式(3)是對某個簇中標簽數據個數的統計。當考慮是否要把一個數據Xi劃分到簇Cj時，除了歐式距離，還要看簇Cj中已有標簽數據與Xi是否是同一標簽。如果semi(Xi，Cj)值較大，則說明簇Cj中不同標簽校對，則不傾向于將Xi劃分到Cj中，否則相反。

改進后的算法則把樣本Xi依據下述函數，將其歸入使得式(4)值最小的簇Ck(k=1，2，…，K)中。

∑mj=1(Xij-Ckj)2+λ×semi(Xi，Ck)(4)

其中λ取值按照式(5)計算

∑Kk=1∑mj=1(Xij-Ckj)2Nsemi(5)

其中:Nsemi是所有具有監督信息的樣本個數;∑Kk=1∑mj=1(Xij-Ckj)2是樣本Xi到所有質心的歐氏距離之和。

對比傳統歐氏距離判定方法，新的判定函數加入了半監督的信息λ×semi(Xi，Ck)，這樣就平衡了距離與類別的沖突，實現樣本的正確劃分。

3.2 定義目標函數

在1.3節中討論了可以采用聚類離散度和聚類不純度的線性組合作為優化的目標函數

α×cluster_dispersion()+β×cluster_impurity()(6)

其中:cluster_dipersion()是無監督學習的距離度量，一般采用所有樣本到期質心的距離之和作為離散度度量;cluster_impurity()是監督學習的簇中標簽數據純度度量，即衡量是否同一個簇中的標簽數據標簽盡量一致，一般采用基尼指數作為不純度度量。分別把上述兩種度量指標代入到式(6)，優化的目標函數成為

fun()=(α×∑Kk=1∑nkik∑mj=1(Xikj-Ckj)2+λk×semik())+β×Gini()(7)

其中:∑Kk=1∑nkik∑mj=1(Xikj-Ckj)2為所有樣本到其質心的歐氏距離之和;λk是第k個簇中樣本到質心歐氏距離的平均值;semik是第k個簇的監督信息數。

3.3 粒子設計

為了發揮粒子群算法的優勢，使得搜索空間和聚類空間匹配更自然，即用每個粒子代表一組K個質心，相應的數據結構為含有K個元素的向量，其中每個元素代表一個歐氏空間的點。粒子通過向全局最優移動，聚類的質心也不斷優化。

3.4 粒子適應度函數

粒子適應度定義為fit()=-fun()，針對每個粒子分別聚類，則很自然用聚類結果的評價指標作為粒子適應度，fun()值越小， fit()越大，聚類結果越好;相應地，粒子適應度越高。

3.5 PSO-Kmeans算法流程

算法1 PSO-Kmeans(D，N，K，Pn，Pmax，s)

輸入:數據集D，最大迭代次數N，聚類數K，初始粒子數目Pn，最大粒子數目Pmax，粒子動態管理敏感指數s。

輸出:具有類標簽的數據集D以及聚類準確率。

1)初始化粒子群

隨機生成K個聚類初始質心，用K個點的位置組成的數組初始化為一個粒子的初始位置，循環往復，形成Pn個粒子的初始位置及初始速度。

2)K-均值聚類

對于每個粒子所代表的一組質心，把每個樣本按照式(4)劃入到最近的簇中，然后計算每個粒子的fit()。

3)根據粒子適應度更新個體最優Pi及全局最優Pg

4)粒子移動

根據式(1)更新粒子速度，根據式(2)更新粒子位置。

5)動態管理種群

a)當粒子群全局最優連續s次沒有改變，并用個體最優頻繁被更新的兩個粒子的位置組合成初始位置，以全部粒子的平均速度作為初始速度。

b)當粒子群全局最優連續s次改變，則動態刪除個體最優更新最不頻繁的粒子。

c)若達到粒子種群數量上限并且最優連續s次沒有改變，則動態添加一個粒子替換掉個體最優更新最不頻繁非全局最優粒子，并用個體最優頻繁被更新的兩個粒子的位置組合成初始位置，以全部粒子的平均速度作為初始速度。

6)判斷是否達到最大迭代次數N，若達到則輸出聚類準確率，否則返回步驟2)繼續迭代。

相比于文獻[1]提到的GA-Kmeans算法，PSO-Kmeans算法把粒子群算法搜索空間與聚類空間對應得更加自然，用每個粒子的位置代表初始質心的位置。由于粒子速度是根據當前位置變化的，當遠離較優質心時，粒子速度較快，當靠近質心時，速度減慢，不會出現GA算法中的抖動現象，能夠連續向最優質心f方向移動，所以能很快找到較優質心。根據式(4)將歐氏距離和監督信息結合起來，用來判定所要劃分的簇，很好地平衡了歐氏距離和標簽屬性的沖突，所以算法具有更好的聚類準確率。

4 實驗結果以及分析

4.1 實驗數據及實驗環境

實驗采用多個UCI 數據集進行了驗證。本文研究的所有實驗均采用Intel 奔騰D2.8 GHz CPU、內存為2 GB的計算機上進行，算法用C++編程實現 。

4.2 實驗方案

文獻[1]提出了一種用遺傳算法優化K-均值算法(GA-Kmeans)，并用最近鄰即歐氏距離最小作為劃分聚類的指標。實驗采用這種算法以及K-means算法(與PSO-Kmeans算法使用相同的歸類函數以及目標函數)在相同的數據集以及相同的監督數據集上聚類，與本文所提出的算法作為對比。此外，采用固定粒子數目的PSO算法與動態管理種群的算法運行相同的代數后比較聚類精確度的方法，體現了動態管理種群的有效性。

4.3 實驗參數設置

分別隨機設置所有數據的10%作為已有標簽數據和實例限制數據為監督信息。為了消除設置監督信息的隨機性，針對每個實驗數據集生成五組不同的監督信息集合，對于每組監督信息集合，每種算法運行10次計算聚類準確度平均值。動態PSO中，開始粒子個數為3，粒子個數上限為30;s(種群變動頻繁程度指數)設置為2，即連續兩次沒有變化或者連續兩次變化則進行種群管理;固定PSO中，粒子個數設置為30，兩種算法的迭代次數都設置為1 000。

4.4 實驗結果匯總(表1)

表1 三種不同算法在相同數據集合以及相同監督數據集上的聚類正確率

數據集類數樣本數維數GA-Kmeans%PSO-Kmeans/%靜態PSO-Kmeans/%K-means/%

wine31781363.2071.2068.159.30

iris3150491.1090.4089.287.70

spectfheart732674531.7035.8033.925.40

balance scale5625444.9050.6046.237.90

housing35061352.3053.5050.150.50

ionosphere23513473.4075.2074.169.30

Pima indians2768869.6074.3071.265.80

waveform50005294053.4051.5049.548.10

4.5 實驗結果分析

由表1中多個數據集上的聚類結果可以看出:

a)改進PSO-Kmeans相比于傳統K-均值算法， 由于質心優化，改進后的算法聚類準確度有了很大提高。

b)與GA-Kmeans相比，由于粒子群空間與歐氏空間耦合度更高，在樣本歸類時加入了半監督信息，聚類結果PSO-Kmeans普遍更優。在iris數據集上，反常是由于iris數據集和本身聚類準確度很高，未能體現算法優勢。

c)靜態與動態管理種群的PSO-Kmeans算法相比，雖然動態PSO的種群數目在運行過程中總是小于等于靜態PSO，但是由于動態管理種群不斷增加新的有啟發能力的粒子并刪除沒有啟發能力的粒子的更新功能，如圖2所示，最后的聚類準確度上，動態管理種群的PSO-Kmeans算法還是遙遙領先。

d)圖3測試了標簽數據占數據集不同百分比(5%~40%)時各種算法的聚類精度。從結果可以看出，當監督信息較少時，兩種算法聚類結果精度差別并不大，逐漸增加監督數據所占百分比，GA-Kmeans聚類精度不再增加，與PSO-Kmeans差距越來越大。這說明在聚類過程中用加入監督信息的新的鄰近度量計算函數即∑mj=1(Xij-Ckj)2+λ×semi(Xi，Ck)，比單純歐氏空間距離能更好地利用監督信息，得到更好的聚類精度。

5 結束語

本文提出了一種用粒子群算法優化K-均值半監督聚類算法。聚類過程中，利用計算所得的樣本與每個質心的歐氏距離與監督信息之和的策略很好地平衡了歐氏距離和監督信息對聚類的影響，并用動態管理種群的方法提高了粒子群算法搜索的時空效率。理論分析和實驗結果表明，這種算法在聚類準確度上有顯著提高。

參考文獻:

[1]DEMRIZ A，BENNETT K P， EMBRECHTS M J. Semi-supervised clustering using genetic algorithm[C]//Proc of the Intelligent Engineering Systems through Artificial Neural Networks. New York:ASME Press， 1999:809-814.

[2]DAVIDSON I， BASU S. Survey of clustering with instance level constraints[J]. ACM Trans on Knowledge Discovery from Data， 2007，w(x，z):1-41.

[3] HAN Jia-wei， KAMBER M. 數據挖掘概念與技術[M]. 范明，孟小峰，譯. 北京:機械工業出版社， 2001.

[4]KENNEDY J， EBERHART R C. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. 1995:1942-1948.

[5]KENNEDY J，EBERHART R C. A discrete binary version of the particle swarm algorithm[C]//Proc of IEEE Conference on Systems， Man， and Cybernetics. 1997:4104-4108.

[6]LIU Yu， QIN Zheng， XU Zeng-lin， et al. Feature selection with particle swarms， computational and information science[C]//Proc of the 1st International Symposium on CIS. 2004:425-430.

[7]WANG Ling， YU Jin-shou. Fault feature selection based on modified binary PSO with mutation and its application in chemical process fault diagnosis[C]//Proc of ICNC. 2005:832-840.

[8]De FALCO I， CIOPPA D A， TARANTINO E. Facing classification problems with particle swarm optimization[J]. Applied Soft Computing， 2007，7(3):652-658.