Kmeans應(yīng)用與特征選擇

柏宇軒

在各行各業(yè)發(fā)展中，都積累了大量的數(shù)據(jù)，而數(shù)據(jù)往往是沒有先驗標(biāo)簽的，我們需要在數(shù)據(jù)中自動發(fā)現(xiàn)規(guī)律，例如自動發(fā)現(xiàn)數(shù)據(jù)中有哪幾類，每一類有什么性質(zhì)。而kmeans聚類算法就是針對這一類問題的有效解決方案。本文中，我們介紹了kmeans的方法，并且進行了實驗，著重討論了質(zhì)心初始點的選取方式和聚類特征的選取方式，最終驗證了kmeans算法的有效性。

【關(guān)鍵詞】人工智能 機器學(xué)習(xí) 數(shù)據(jù)挖掘 聚類 kmeans

1 引言

近些年來，機器學(xué)習(xí)的發(fā)展日新月異，機器學(xué)習(xí)的兩大問題：分類和聚類也不斷有新的算法來填充。而對于大量樣本的數(shù)據(jù)，由于人工標(biāo)注成本很高，經(jīng)常是沒有標(biāo)簽的數(shù)據(jù)，需要用聚類算法來發(fā)現(xiàn)數(shù)據(jù)中有幾類，每一類是什么樣，有什么性質(zhì)，各類之間的關(guān)系是什么樣。Kmeans是聚類算法中簡單有效的一種，也稱為k均值算法。

本文先介紹kmeans聚類的方法，包括主要思想和具體步驟；然后把算法應(yīng)用在鳶尾花數(shù)據(jù)集上，并且改變特征的數(shù)量，來看對聚類結(jié)果的影響；接著，本文對kmeans算法的優(yōu)缺點進行了討論，并和其他算法進行比較，還介紹了該算法在使用時候需要注意的問題；最后，我們根據(jù)實驗結(jié)果總結(jié)結(jié)論，得出kmeans是有效的一種聚類算法，并且特征的選擇會對聚類結(jié)果產(chǎn)生很大影響。

2 方法

Kmeans的主要思想是將離散的許多數(shù)據(jù)點利用k個質(zhì)心進行聚類，分成k簇來區(qū)分相似性較小的數(shù)據(jù)點，并把相似性較大的數(shù)據(jù)點歸為一類。該方法利用不斷更新數(shù)據(jù)點的質(zhì)心歸屬和質(zhì)心的位置來最終收斂到最優(yōu)解。

Kmeans有四個主要步驟：

（1）利用kmeans++在n個數(shù)據(jù)點中取k個質(zhì)心：普通kmeans算法中，是隨機選取k個數(shù)據(jù)點最為初始的質(zhì)心，但這樣的結(jié)果可能會導(dǎo)致聚類迭代的過程中收斂速度慢或者收斂到局部最優(yōu)的結(jié)果。Kmeans++成功解決了這個問題，它改進了質(zhì)心初始化的方法：首先隨機選取一個數(shù)據(jù)點作為第一個質(zhì)心，接著，選取距離第一個點最遠的數(shù)據(jù)點作為第二個質(zhì)心，再接著選取距離第一個和第二個質(zhì)心距離之和最大的數(shù)據(jù)點最為第三個質(zhì)心，以此類推，選取出k個初始質(zhì)心點。

（2）把所有數(shù)據(jù)點都歸屬到離它最近的質(zhì)心，并且標(biāo)為相應(yīng)的類別號，從而把所有數(shù)據(jù)點分成k個簇。此處的距離通常選擇歐式距離。

（3）在各個簇內(nèi)部求均值確定新的質(zhì)心。

（4）重復(fù)第2，3步驟直到各個數(shù)據(jù)點的歸屬不變或者達到提前設(shè)定迭代次數(shù)。

3 實驗

在介紹完kmeans的方法之后，我們找了真實的數(shù)據(jù)集來做算法實驗。我們使用的數(shù)據(jù)集是sklearn機器學(xué)習(xí)庫里面的datasets子庫中的鳶尾花（iris）數(shù)據(jù)，共包括150個花的數(shù)據(jù)，每個數(shù)據(jù)有四個屬性（特征），分別是花萼長度，花萼寬度，花瓣長度，花瓣寬度。然后，我們選取不同的特征對花進行聚類，首先我們選擇花萼長度，花萼寬度作為特征聚類，然后我們選擇花瓣長度，花瓣寬度進行聚類，最后，我們一起用四個特征進行聚類，比較聚類結(jié)果。

對于質(zhì)心初始化方法，我們采用kmeans++中的初始化方法代替隨機選取初始質(zhì)心的方法。

對于聚類的個數(shù)，我們分別設(shè)為2，3，4來進行實驗，觀察實驗結(jié)果，通過可視化方法，判斷設(shè)為幾類才是最合適的。

4 結(jié)果展示

我們用散點圖標(biāo)注每個數(shù)據(jù)點，并且用顏色（紅，藍，綠，黃）區(qū)分它所屬的類別，來觀察數(shù)據(jù)點在特征空間的分布，判斷聚類結(jié)果十分合理。在每個圖中，橫坐標(biāo)代表花某一部分的長度，縱坐標(biāo)代表花某一部分的寬度，坐標(biāo)軸的單位都是厘米，每一種顏色是一簇。

首先我們僅用花萼長度，花萼寬度來聚類，聚類的類別個數(shù)分別設(shè)定為2，3，4，對應(yīng)從左到右三個圖?？梢钥闯龌ㄝ嚅L度和寬度的數(shù)據(jù)分布沒有特別明顯的簇狀分布，所以類別個數(shù)分為2，3，4看起來都有一定道理。

然后，我們用花瓣長度，花瓣寬度來聚類，聚類的類別個數(shù)分別設(shè)定為2，3，4，對應(yīng)從左到右三個圖。我們能看到很明顯有兩簇數(shù)據(jù)點分布較遠，中間隔著很大距離，即畫面左下角的簇和畫面中間到右上角的簇，故聚類類數(shù)選為2比較合理。此時，雖然聚成兩類有一個數(shù)據(jù)點被誤判，但大體能區(qū)分這兩部分，也是可取的。

最后，我們用花萼長度，花萼寬度，花瓣長度，花瓣寬度四個屬性共同去對花進行聚類，也就是這四個特征都會影響到聚類結(jié)果。在這里，特征空間維度數(shù)是4，所以我們分為兩個2維平面來進行可視化，即花萼的長度寬度和花瓣的長度寬度這兩張圖。對比第一行和第三行圖，我們發(fā)現(xiàn)，相比之下，第三行圖中聚類的界限不是那么清晰，這是因為另外兩個維度也起到了影響聚類的效果。同樣，對比第二行和第四行的圖，我們也能得到類似的結(jié)論。 在用四個特征共同聚類的時候，我們發(fā)現(xiàn)聚成三類的結(jié)果較為合理，每一簇的大小比較均勻。

5 討論

Kmeans作為應(yīng)用很廣泛的聚類算法，有著很多其他算法無法比擬的優(yōu)點，又有一些待改進的缺點。

其主要優(yōu)點有：

（1）我們可以用每一類的質(zhì)心來簡單的表征這一類的性質(zhì)，因為質(zhì)心實際上可以看做是這一類中最有代表性的點。通常的聚類算法只給出每個點的類別屬性，但并沒有一個量能直接反應(yīng)出每一類的特性。

（2）該算法不需要先驗知識，也就是我們在初始化過程中，默認每個點屬于每一類的先驗概率都是相同的。

（3）算法思想簡潔且步驟易懂。

主要缺點有：

（1）由于在對每個數(shù)據(jù)點去進行質(zhì)心的歸屬判斷的時候，判定歸為聚類最近的質(zhì)心，所以導(dǎo)致每個簇的形狀都是近似圓形的。例如，對于每一類都是狹長分布的情況，kmeans并不能給出很好的聚類效果。

（2）對異常值敏感，其原因和上一條相同，當(dāng)有離簇較遠的點時，聚類效果會有所下降。

在我們使用kmeans時，需要注意每一類質(zhì)心初始化使用kmeans++都會對最終聚類效果和聚類效率都有好處。在確定聚類的個數(shù)時，我們可以選取特定的數(shù)學(xué)指標(biāo)或者多嘗試并且根據(jù)可視化效果判斷聚成幾類最合適。

6 結(jié)論

綜上所述，kmeans是一種聚類的基本方法，由于kmeans聚類方法的特殊性，初始值的選擇對聚類結(jié)果影響很大。因此在聚類時需要注意的是初始點的選擇需要用kmeans++，這樣能提高聚類效率與聚類的效果。

在聚類過程中，特征的選擇也尤為重要，實際上，特征的選擇也就是選擇用什么來區(qū)分數(shù)據(jù)點，不同特征得到的聚類結(jié)果也有著不同的物理含義，比如用花萼的屬性聚類可以看做區(qū)分花萼，而用花萼花瓣的屬性（屬性更全）共同聚類可以看做是區(qū)分花本身。

總而言之，kmeans通常能取得較好的聚類效果，在優(yōu)化初始化質(zhì)心的方法并認真進行特征選擇后，聚類效果能得到進一步提升。

參考文獻

[1]http：//scikit-learn.org/stable/modules/generated/sklearn.datasets.load_iris.html.

[2]Arthur，David，and Sergei Vassilvitskii."k-means++：The advantages of careful seeding." Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms.Society for Industrial and Applied Mathematics，2007.

[3]Dash，Manoranjan，and Huan Liu. "Feature selection for clustering." Pacific-Asia Conference on knowledge discovery and data mining.Springer， Berlin，Heidelberg，2000.

[4]陳祖耀.聚類特征選 擇方法的研究和應(yīng)用[D].Diss，江南大學(xué)，2009.

作者單位

株洲市長鴻實驗學(xué)校 湖南省衡陽市 421008