k-means

k-NN

學(xué)習(xí)范式

無監(jiān)督學(xué)習(xí)算法

監(jiān)督學(xué)習(xí)算法

提出時間

1967年

1968年

適用問題

解決聚類問題

解決分類或回歸問題

核心思想

物以類聚，人以群分

近朱者赤，近墨者黑

算法原理

k-means是基于中心的聚類方法，通過迭代，將樣本分到k個類中，使得每個樣本與其所屬類的中心或均值最近；得到k個類別，構(gòu)成對空間的劃分。

k-NN算法簡單、直觀，給定一個訓(xùn)練數(shù)據(jù)集，對新的輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最近鄰的k個實(shí)例，這k個實(shí)例的多數(shù)屬于某個類，就把該輸入實(shí)例分為這個類。

算法流程

k-means聚類的算法是一個迭代過程，每次迭代包括兩個步驟。首先選擇k個類的中心，將樣本逐個指派到與其最近的中心的類中，得到一個聚類結(jié)果；然后更新每個類的樣本的均值，作為類的新的中心；重復(fù)上述步驟，直到收斂為止。

(1)當(dāng)有新的測試樣本出現(xiàn)時，計算其到訓(xùn)練集中每個數(shù)據(jù)點(diǎn)的距離；（距離度量）

(2)根據(jù)距離選擇與測試樣本距離最小的前k個訓(xùn)練樣本；（k值選擇）

(3)基于這k個訓(xùn)練樣本的類別來劃分新樣本的類別，通常選擇這k個訓(xùn)練樣本中出現(xiàn)次數(shù)最多的標(biāo)簽作為新樣本的類別。（決策規(guī)則）

算法圖示

k的意義

k是類的數(shù)目

k是用來計算的相鄰數(shù)據(jù)數(shù)

k的選擇

k是類的數(shù)目，是人為設(shè)定的數(shù)字?？梢試L試不同的k值聚類，檢驗(yàn)各自得到聚類結(jié)果的質(zhì)量，推測最優(yōu)的k值。聚類結(jié)果的質(zhì)量可以用類的平均直徑來衡量。一般地，類別數(shù)變小時，平均直徑會增加；類別數(shù)變大超過某個值以后，平均直徑會不變；而這個值正式最優(yōu)的k值。實(shí)驗(yàn)時，可以采用二分查找，快速找到最優(yōu)的k值。

k值的選擇會對k-NN的結(jié)果產(chǎn)生重大影響。

·如果選擇較小的k值，就相當(dāng)于用較小的鄰域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測，“學(xué)習(xí)”的近似誤差（approximation error）會減小，只有與輸入實(shí)例較近的（相似的）訓(xùn)練實(shí)例才會對預(yù)測結(jié)果起作用。但缺點(diǎn)是“學(xué)習(xí)”的估計誤差（estimation error）會增大，預(yù)測結(jié)果會對近鄰的實(shí)例點(diǎn)非常敏感。如果鄰近的實(shí)例點(diǎn)恰巧是噪聲，預(yù)測就會出錯。換句話說，k值的減小就意味著整體模型變得復(fù)雜，容易發(fā)生過擬合。

·如果選擇較大的k值，就相當(dāng)于用較大鄰域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測。其優(yōu)點(diǎn)是可以減少學(xué)習(xí)的估計誤差，但缺點(diǎn)是學(xué)習(xí)的近似誤差會增大。這時與輸入實(shí)例較遠(yuǎn)的（不相似的）訓(xùn)練實(shí)例也會對預(yù)測起作用，使預(yù)測發(fā)生錯誤。k值的增大就意味著整體的模型變得簡單。

·如果k=n，那么無論輸入實(shí)例是什么，都將簡單地預(yù)測它屬于在訓(xùn)練實(shí)例中最多的類。這時，模型過于簡單，完全忽略訓(xùn)練實(shí)例中的大量有用信息，是不可取的。

·在應(yīng)用中，k值一般取一個比較小的數(shù)值。通常采用交叉驗(yàn)證法來選取最優(yōu)的k值。

k與結(jié)果

k值確定后每次結(jié)果可能不同，從 n 個數(shù)據(jù)對象任意選擇 k 個對象作為初始聚類中心，隨機(jī)性對結(jié)果影響較大。

k-NN算法中，當(dāng)訓(xùn)練集、距離度量（如歐氏距離）、k值和決策規(guī)則（如多數(shù)表決）確定后，對于任何一個新輸入的實(shí)例，它所屬的類唯一確定。

復(fù)雜度

時間復(fù)雜度：O(n*k*t)，n為訓(xùn)練實(shí)例數(shù)，k為聚類數(shù)，t為迭代次數(shù)。

線性掃描時間復(fù)雜度：O(n)

kd樹方法時間復(fù)雜度：O(logn)

算法特點(diǎn)

是基于劃分的聚類方法；類別數(shù)k事先指定；以歐氏距離平方表示樣本之間的距離，以中心或樣本的均值表示類別；以樣本和其所屬類的中心之間的距離的總和為最優(yōu)化的目標(biāo)函數(shù)；得到的類別是平坦的、非層次化的；算法是迭代算法，不能保證得到全局最優(yōu)。

k-NN算法沒有顯式的學(xué)習(xí)過程；實(shí)現(xiàn)k-NN時，主要考慮問題是如何對訓(xùn)練數(shù)據(jù)進(jìn)行快速k近鄰搜索。

算法優(yōu)點(diǎn)

1、解決聚類問題的經(jīng)典算法，簡單、快速；

2、當(dāng)處理大數(shù)據(jù)集時，算法保持可伸縮性和高效率；

3、當(dāng)簇近似為高斯分布時，效果較好；

4、時間復(fù)雜度近于線性，適合挖掘大規(guī)模數(shù)據(jù)集。

1、對輸入數(shù)據(jù)無假定，如不會假設(shè)輸入數(shù)據(jù)是服從正太分布；

2、k-NN可以處理分類問題，同時天然可以處理多分類問題，比如鳶尾花的分類；

3、簡單，易懂，同時也很強(qiáng)大，對于手寫數(shù)字的識別，鳶尾花這一類問題來說，準(zhǔn)確率很高；

4、k-NN還可以處理回歸問題，也就是預(yù)測；

5、對異常值不敏感；

6、可以用于數(shù)值型數(shù)據(jù)，也可以用于離散型數(shù)據(jù)。

算法缺點(diǎn)

1、類別數(shù)k需要事先指定；

2、對初值敏感，即對于不同的初值，可能會導(dǎo)致不同結(jié)果；

3、不適合非凸形狀的簇或者大小差別很大的簇；

4、對噪聲和孤立點(diǎn)敏感；

5、屬于啟發(fā)式算法，不能保證得到全局最優(yōu)。

1、計算復(fù)雜度高，線性掃描方法需要計算輸入實(shí)例與每一個訓(xùn)練實(shí)例的距離，當(dāng)訓(xùn)練集很大時，計算非常耗時；可以通過kd樹等方法改進(jìn)；

2、嚴(yán)重依賴訓(xùn)練樣本集，對訓(xùn)練數(shù)據(jù)的容錯性差，如果訓(xùn)練數(shù)據(jù)集中，有一兩個數(shù)據(jù)是錯誤的，剛剛好又在需要分類的數(shù)值的旁邊，就會直接導(dǎo)致預(yù)測的數(shù)據(jù)的不準(zhǔn)確；

3、距離度量方法以及k值的選取都有比較大的影響，k值選擇不當(dāng)則分類精度不能保證。

相似點(diǎn)

都包含這樣的過程，給定一個點(diǎn)，在數(shù)據(jù)集中找離它最近的點(diǎn)，即二者都用到了NN（Nearest Neighbor）算法，一般用kd樹來實(shí)現(xiàn)NN。文章來源地址http://www.zghlxwxcb.cn/news/detail-675051.html