改良的kmeans與K近鄰算法特性分析

章宦記

摘要：kmeans算法作為無監(jiān)督算法的一種，對(duì)初始點(diǎn)的選擇比較敏感；而k近鄰作為一種惰性且有監(jiān)督的算法，對(duì)k值和樣本間距離度量方式的選擇也會(huì)影響結(jié)果。改良的kmeans算法通過遍歷樣本，篩選初始點(diǎn)，其準(zhǔn)確率超過了k近鄰算法，同時(shí)穩(wěn)定性也優(yōu)于傳統(tǒng)的kmeans算法。無監(jiān)督算法在一些情況下優(yōu)于有監(jiān)督算法。

關(guān)鍵詞：初始點(diǎn)；無監(jiān)督；鄰近點(diǎn)；有監(jiān)督

DOI：10.3969/j.issn.1005-5517.2016.1.022

引言

上個(gè)世紀(jì)60年代，MacQueen首次提出kmeans算法^[1]，而后的數(shù)十年中，kmeans算法被廣泛應(yīng)用于各種領(lǐng)域，比如馬勇等人將kmeans算法應(yīng)用在醫(yī)療系統(tǒng)中^[2]，楊明峰等人將kmeans聚類算法應(yīng)用于對(duì)烤煙外觀的區(qū)域分類^[3]。同時(shí)很多的學(xué)者投入到對(duì)kmeans算法本身特性的研究中^[4-5]、目前kmeans算法已經(jīng)成為機(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘等領(lǐng)域比較重要的方法之一。而k近鄰算法是圖像以及文本分類領(lǐng)域應(yīng)用比較廣泛的算法之一^[6-7]，對(duì)k近鄰算法而言，k值的選擇以及樣本間距離的度量方式都會(huì)影響到分類的精確度。但是同樣有許多學(xué)者對(duì)該算法進(jìn)行了一些改善，比如孫秋月等^[8]通過對(duì)度量的樣本數(shù)據(jù)的每個(gè)維度賦不同權(quán)值的方式，降低了樣本數(shù)據(jù)分布不均勻?qū)е碌姆诸愓`差。嚴(yán)曉明等通過類別平均距離進(jìn)行加權(quán)對(duì)大于某一個(gè)閾值的數(shù)據(jù)樣本點(diǎn)進(jìn)行剔除的方式來提高k近鄰算法的精度^[9]。k近鄰算法本身是一種惰性的監(jiān)督算法，相較于其他監(jiān)督算法比如支持向量機(jī)、邏輯回歸、隨機(jī)樹等，具有算法簡(jiǎn)單、易于理解、易于實(shí)現(xiàn)、無需估計(jì)參數(shù)的特性。kmeans算法由于對(duì)初始點(diǎn)選擇較敏感，不同的初始點(diǎn)將會(huì)導(dǎo)致不同的聚類結(jié)果。因此本文對(duì)kmeans算法進(jìn)行改進(jìn)，改良的kmeans算法對(duì)二分類的結(jié)果可以接近k近鄰算法的正確率，甚至在k近鄰算法選擇不同的k值時(shí)，分類效果會(huì)優(yōu)于采用k近鄰算法的分類結(jié)果正確率，同時(shí)分類的結(jié)果也遠(yuǎn)高于隨機(jī)指定初始點(diǎn)的kmeans算法。

1 傳統(tǒng)的分類算法與改進(jìn)算法

1.1傳統(tǒng)的kmeans算法與k近鄰算法

對(duì)于傳統(tǒng)的kmeans算法而言、對(duì)于給定的數(shù)據(jù)集n個(gè)樣本，在不知道數(shù)據(jù)集的標(biāo)記時(shí)，通過指定該數(shù)據(jù)集中的K（K≤n）數(shù)據(jù)樣本作為初始中心，通過如下的方式進(jìn)行聚類：

（1）對(duì)該數(shù)據(jù)集中任意一個(gè)數(shù)據(jù)樣本求其到k個(gè)中心的距離，將該數(shù)據(jù)樣本歸屬到數(shù)據(jù)樣本距離中心最短的類；

（2）對(duì)于得到的類中的數(shù)據(jù)樣本，以求類的均值等方法更新每類中心：

（3）重復(fù)上述過程1和2更新類中心，如果類中心不變或者類中心變化小于某一個(gè)閾值，則更新結(jié)束，形成類簇，否則繼續(xù)。

但是對(duì)于傳統(tǒng)的kmeans聚類算法而言，由于隨機(jī)指定初始點(diǎn)，對(duì)kmeans算法通過迭代這樣一種啟發(fā)式的貪心算法而言不能形成一個(gè)全局最優(yōu)解，迭代最終收斂的結(jié)果可能都是局部最優(yōu)解。這樣分類的精度就會(huì)難以預(yù)料，對(duì)最終的樣本分類就難以消除隨機(jī)指定初始點(diǎn)造成的聚類結(jié)果不一致的影響。

對(duì)于傳統(tǒng)的k近鄰算法而言，對(duì)于給定的數(shù)據(jù)集，有n個(gè)數(shù)據(jù)樣本是已標(biāo)記的，另一部分?jǐn)?shù)據(jù)樣本是未標(biāo)記的，對(duì)未標(biāo)記的數(shù)據(jù)樣本，通過如下的方式進(jìn)行分類：

（1）度量每個(gè)未標(biāo)記數(shù)據(jù)樣本與所有已標(biāo)記數(shù)據(jù)樣本的距離：

（2）對(duì)所有求出的距離選擇與未標(biāo)記數(shù)據(jù)樣本距離最近的K（K≤n）個(gè)已標(biāo)記數(shù)據(jù)樣本；

（3）統(tǒng)計(jì)這k個(gè)已標(biāo)記的數(shù)據(jù)樣本，哪一類的數(shù)據(jù)樣本個(gè)數(shù)最多，則未標(biāo)記的數(shù)據(jù)樣本標(biāo)記為該類樣本K近鄰算法沒有一個(gè)數(shù)據(jù)樣本訓(xùn)練的過程，本身是一種惰性的監(jiān)督算法，該算法對(duì)k值的選擇以及距離的度量方式都會(huì)影響最終的分類精度。因?yàn)樵撍惴ㄖ皇沁x擇。

k個(gè)近鄰而沒有判斷近鄰中樣本是否分布得均勻。因此，該算法如果樣本分布不均勻，也會(huì)大大影響分類的結(jié)果。

1.2改進(jìn)的kmeans算法

由于傳統(tǒng)kmeans算法初始點(diǎn)的影響較大，因此可以做如下改進(jìn)。

對(duì)于給定的數(shù)據(jù)集樣本，kmeans可以通過兩兩比較數(shù)據(jù)集中數(shù)據(jù)樣本點(diǎn)間的距離，選擇距離最遠(yuǎn)的兩個(gè)點(diǎn)A，B作為初始標(biāo)記。同時(shí)為了去除噪聲對(duì)初始點(diǎn)的影響，對(duì)于選定的初始標(biāo)記點(diǎn)，可以選擇以初始標(biāo)記點(diǎn)為中心，與初始標(biāo)記點(diǎn)距離小于閾值的若干個(gè)點(diǎn)的幾何均值A(chǔ)'，B'作為最終的初始點(diǎn)。對(duì)于A初始標(biāo)記點(diǎn)的若干點(diǎn)的選擇原則是離初始標(biāo)記A距離與離B距離的比值大于一定閾值的若干點(diǎn)，而對(duì)于B初始標(biāo)記點(diǎn)的若干點(diǎn)的選擇原則是離初始標(biāo)記B距離與A距離的比值大于一定閾值的若干點(diǎn)。選定了初始點(diǎn)后，其后的步驟如下：

（1）對(duì)該數(shù)據(jù)集中任意一個(gè)數(shù)據(jù)樣本求其到A'，B'兩個(gè)中心的距離，將該數(shù)據(jù)樣本歸屬到數(shù)據(jù)樣本距離A'，B'短的類；

（2）對(duì)于得到的類中的數(shù)據(jù)樣本，求類的均值更新兩類中心；

（3）重復(fù)上述過程1和2更新類中心，如果類中心不變或者類中心變化小于某一個(gè)閾值，則更新結(jié)束，形成類簇，否則繼續(xù)。

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

采用手寫數(shù)字集M NIST Ha ndwritten Digits^[10]進(jìn)行實(shí)驗(yàn)，該數(shù)字集庫含有0-9的10類手寫訓(xùn)練數(shù)據(jù)集和0-9的10類手寫測(cè)試數(shù)據(jù)集。每個(gè)數(shù)據(jù)集樣本的大小是28*28的圖片，轉(zhuǎn)化成向量是1*784維大小。從手寫數(shù)據(jù)集中抽取標(biāo)記為1和2的兩類數(shù)據(jù)集樣本，從這類數(shù)據(jù)集中隨機(jī)抽取標(biāo)記為1和2的數(shù)據(jù)樣本各1000個(gè)，共計(jì)2000個(gè)數(shù)據(jù)樣本進(jìn)行實(shí)驗(yàn)分析。從這2000個(gè)數(shù)據(jù)樣本中隨機(jī)選擇1600個(gè)數(shù)據(jù)樣本（標(biāo)記為1和2的兩類數(shù)據(jù)各800個(gè)數(shù)據(jù)樣本）進(jìn)行k近鄰分析，400個(gè)數(shù)據(jù)樣本（標(biāo)記為1和2的兩類數(shù)據(jù)樣本各200個(gè)）進(jìn)行測(cè)試。對(duì)于改進(jìn)的kmeans算法，將小于閾值的5個(gè)點(diǎn)取幾何均值作為最終的初始點(diǎn)和傳統(tǒng)的kmeans算法采用400個(gè)數(shù)據(jù)樣本進(jìn)行測(cè)試。改進(jìn)的kmeans算法測(cè)試的正確率為84.25%，傳統(tǒng)的kmeans算法初始值不確定，可能的正確率為15.75%，51%以及83.75%等。很明顯，改進(jìn)的kmeans算法不管從精度還是穩(wěn)定性方面都優(yōu)于傳統(tǒng)的kmeans算法。k近鄰算法選擇曼哈頓距離和歐式距離作為距離度量的方式，同時(shí)改變k值對(duì)k近鄰算法的結(jié)果進(jìn)行測(cè)量，結(jié)果如圖1所示，橫軸表示k值選擇的樣本數(shù)，縱軸表示對(duì)應(yīng)的測(cè)試正確率。

從圖1中可以看出，隨著近鄰數(shù)的增多，在一定的范圍內(nèi)，k近鄰的精度是下降趨勢(shì)。對(duì)于選擇曼哈頓距離度量樣本間距離的k近鄰算法，當(dāng)k值大于200的時(shí)候，k近鄰算法對(duì)樣本的分類正確率明顯低于改良的kmeans算法對(duì)樣本分類的正確率。而采用歐式距離度量樣本間距離的k近鄰算法，當(dāng)k值大于380的時(shí)候，k近鄰算法對(duì)樣本的分類正確率才明顯低于改良的kmeans算法對(duì)樣本分類的正確率。因此對(duì)于k近鄰算法而言，k近鄰數(shù)目的選擇以及樣本間距離度量的方式對(duì)分類的結(jié)果都是至關(guān)重要的。同時(shí)從中可以發(fā)現(xiàn)，在某些情況下，無監(jiān)督的學(xué)習(xí)方式可能比有監(jiān)督的學(xué)習(xí)方式更有利，也更方便。

參考文獻(xiàn)：

[1]Macqueen J Some methods for dassification and analysis of multivariate observations[C]Proceedings of the fifth Berkeley symposium on mathematical statistics and probabihty， 1967： 281-297

[2]馬勇，一種改進(jìn)的K-means聚類分析算法在醫(yī)院信息系統(tǒng)中的應(yīng)用研究[J]信息資源管理學(xué)報(bào)，2012，（03）：93-96

[3]楊明峰，詹良，魏春陽，等基于K-means聚類分析的不同種植區(qū)烤煙外觀質(zhì)量區(qū)域分類[J]中國煙草科學(xué)，2012，（02）： 12-16

[4]張文明，吳江，袁小蛟基于密度和最近鄰的K-means文本聚類算法[J]計(jì)算機(jī)應(yīng)用，2010，（07）：1933-1935

[5]袁方，周志勇，宋鑫初始聚類中心優(yōu)化的k-means算法[J]計(jì)算機(jī)工程，2007，（03）：65-66

[6]陳帥均，蔣平，吳欽章改進(jìn)的KNN算法在光測(cè)圖像關(guān)鍵事件評(píng)估中的應(yīng)用[J]光電工程，2014，（08）：66-72

[7]王淵，劉業(yè)政，姜元春基于粗糙KNN算法的文本分類方法[J]臺(tái)肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，（12）：1513-1517

[8]孫秋月，基于SNN相似度的KNN分類算法研究[D]云南大學(xué)，2008

[9]嚴(yán)曉明，基于類別平均距離的加權(quán)KNN分類算法[J]計(jì)算機(jī)系統(tǒng)應(yīng)用，2014，（02）：128-132

[10]The MNIST database of handwritten digits[EB/OU. http：//yann.lecun.com/exdb/mnist/