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

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

引言

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

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

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

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

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

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

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

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

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

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

　　(2)對所有求出的距離選擇與未標(biāo)記數(shù)據(jù)樣本距離最近的k(k≤n)個已標(biāo)記數(shù)據(jù)樣本;

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

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

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

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

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

　　(1)對該數(shù)據(jù)集中任意一個數(shù)據(jù)樣本求其到兩個中心的距離，將該數(shù)據(jù)樣本歸屬到數(shù)據(jù)樣本距離短的類;

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

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

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

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

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

參考文獻(xiàn)：

　　[1]Macqueen J. Some methods for classification and analysis of multivariate observations[C]. Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, 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算法在光測圖像關(guān)鍵事件評估中的應(yīng)用[J]. 光電工程, 2014, (08): 66-72

　　[7]王淵, 劉業(yè)政, 姜元春. 基于粗糙KNN算法的文本分類方法[J]. 合肥工業(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/OL]. http://yann.lecun.com/exdb/mnist/

本文來源于中國科技期刊《電子產(chǎn)品世界》2016年第1期第79頁，歡迎您寫論文時引用，并注明出處。