K-Means介紹
K-means算法是聚類分析中使用最廣泛的算法之一舱权。它把n個對象根據(jù)他們的屬性分為k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高募胃；而不同聚類中的對象相似度較小旗唁。其聚類過程可以用下圖表示：
如圖所示，數(shù)據(jù)樣本用圓點(diǎn)表示痹束，每個簇的中心點(diǎn)用叉叉表示检疫。(a)剛開始時是原始數(shù)據(jù)，雜亂無章祷嘶，沒有l(wèi)abel屎媳，看起來都一樣，都是綠色的论巍。(b)假設(shè)數(shù)據(jù)集可以分為兩類烛谊，令K=2，隨機(jī)在坐標(biāo)上選兩個點(diǎn)嘉汰，作為兩個類的中心點(diǎn)晒来。(c-f)演示了聚類的兩種迭代。先劃分郑现，把每個數(shù)據(jù)樣本劃分到最近的中心點(diǎn)那一簇湃崩；劃分完后，更新每個簇的中心接箫，即把該簇的所有數(shù)據(jù)點(diǎn)的坐標(biāo)加起來去平均值攒读。這樣不斷進(jìn)行”劃分—更新—劃分—更新”，直到每個簇的中心不在移動為止辛友。
該算法過程比較簡單薄扁，但有些東西我們還是需要關(guān)注一下，此處废累，我想說一下"求點(diǎn)中心的算法"
一般來說邓梅，求點(diǎn)群中心點(diǎn)的算法你可以很簡的使用各個點(diǎn)的X/Y坐標(biāo)的平均值。也可以用另三個求中心點(diǎn)的的公式：
1）Minkowski Distance 公式 ——λ 可以隨意取值邑滨，可以是負(fù)數(shù)日缨，也可以是正數(shù)，或是無窮大掖看。
2）Euclidean Distance 公式—— 也就是第一個公式 λ=2 的情況
3）CityBlock Distance 公式—— 也就是第一個公式 λ=1 的情況
這三個公式的求中心點(diǎn)有一些不一樣的地方匣距，我們看下圖（對于第一個 λ 在 0-1之間）面哥。
（1）Minkowski Distance （2）Euclidean Distance （3）CityBlock Distance
上面這幾個圖的大意是他們是怎么個逼近中心的，第一個圖以星形的方式毅待，第二個圖以同心圓的方式尚卫，第三個圖以菱形的方式。
Kmeans算法的缺陷
聚類中心的個數(shù)K 需要事先給定尸红，但在實際中這個 K 值的選定是非常難以估計的吱涉，很多時候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個類別才最合適
Kmeans需要人為地確定初始聚類中心外里，不同的初始聚類中心可能導(dǎo)致完全不同的聚類結(jié)果邑飒。（可以使用Kmeans++算法來解決）
針對上述第2個缺陷，可以使用Kmeans++算法來解決
K-Means ++ 算法
k-means++算法選擇初始seeds的基本思想就是：初始的聚類中心之間的相互距離要盡可能的遠(yuǎn)级乐。
從輸入的數(shù)據(jù)點(diǎn)集合中隨機(jī)選擇一個點(diǎn)作為第一個聚類中心
對于數(shù)據(jù)集中的每一個點(diǎn)x疙咸，計算它與最近聚類中心(指已選擇的聚類中心)的距離D(x)
選擇一個新的數(shù)據(jù)點(diǎn)作為新的聚類中心，選擇的原則是：D(x)較大的點(diǎn)风科，被選取作為聚類中心的概率較大
重復(fù)2和3直到k個聚類中心被選出來
利用這k個初始的聚類中心來運(yùn)行標(biāo)準(zhǔn)的k-means算法
從上面的算法描述上可以看到撒轮，算法的關(guān)鍵是第3步，如何將D(x)反映到點(diǎn)被選擇的概率上贼穆，一種算法如下：
先從我們的數(shù)據(jù)庫隨機(jī)挑個隨機(jī)點(diǎn)當(dāng)“種子點(diǎn)”
對于每個點(diǎn)题山，我們都計算其和最近的一個“種子點(diǎn)”的距離D(x)并保存在一個數(shù)組里，然后把這些距離加起來得到Sum(D(x))故痊。
然后顶瞳，再取一個隨機(jī)值，用權(quán)重的方式來取計算下一個“種子點(diǎn)”愕秫。這個算法的實現(xiàn)是慨菱，先取一個能落在Sum(D(x))中的隨機(jī)值Random，然后用Random -= D(x)戴甩，直到其<=0符喝，此時的點(diǎn)就是下一個“種子點(diǎn)”。
重復(fù)2和3直到k個聚類中心被選出來
利用這k個初始的聚類中心來運(yùn)行標(biāo)準(zhǔn)的k-means算法
可以看到算法的第三步選取新中心的方法甜孤，這樣就能保證距離D(x)較大的點(diǎn)协饲，會被選出來作為聚類中心了。至于為什么原因比較簡單缴川，如下圖 所示：
假設(shè)A茉稠、B、C把夸、D的D(x)如上圖所示而线，當(dāng)算法取值Sum(D(x))*random時，該值會以較大的概率落入D(x)較大的區(qū)間內(nèi)，所以對應(yīng)的點(diǎn)會以較大的概率被選中作為新的聚類中心吞获。
k-means++代碼：http://rosettacode.org/wiki/K-means%2B%2B_clustering
KNN(K-Nearest Neighbor)介紹
算法思路：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別况凉，則該樣本也屬于這個類別谚鄙。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別各拷。
看下面這幅圖：
KNN的算法過程是是這樣的：
從上圖中我們可以看到，圖中的數(shù)據(jù)集是良好的數(shù)據(jù)闷营，即都打好了label烤黍，一類是藍(lán)色的正方形，一類是紅色的三角形傻盟，那個綠色的圓形是我們待分類的數(shù)據(jù)速蕊。
如果K=3，那么離綠色點(diǎn)最近的有2個紅色三角形和1個藍(lán)色的正方形娘赴，這3個點(diǎn)投票规哲，于是綠色的這個待分類點(diǎn)屬于紅色的三角形
如果K=5，那么離綠色點(diǎn)最近的有2個紅色三角形和3個藍(lán)色的正方形诽表，這5個點(diǎn)投票唉锌，于是綠色的這個待分類點(diǎn)屬于藍(lán)色的正方形
我們可以看到，KNN本質(zhì)是基于一種數(shù)據(jù)統(tǒng)計的方法竿奏！其實很多機(jī)器學(xué)習(xí)算法也是基于數(shù)據(jù)統(tǒng)計的袄简。
KNN是一種memory-based learning，也叫instance-based learning泛啸，屬于lazy learning绿语。即它沒有明顯的前期訓(xùn)練過程，而是程序開始運(yùn)行時候址，把數(shù)據(jù)集加載到內(nèi)存后吕粹，不需要進(jìn)行訓(xùn)練，就可以開始分類了岗仑。
具體是每次來一個未知的樣本點(diǎn)昂芜，就在附近找K個最近的點(diǎn)進(jìn)行投票。
再舉一個例子赔蒲，Locally weighted regression (LWR)也是一種 memory-based 方法泌神，如下圖所示的數(shù)據(jù)集。
用任何一條直線來模擬這個數(shù)據(jù)集都是不行的舞虱，因為這個數(shù)據(jù)集看起來不像是一條直線欢际。但是每個局部范圍內(nèi)的數(shù)據(jù)點(diǎn)，可以認(rèn)為在一條直線上矾兜。每次來了一個位置樣本x损趋，我們在X軸上以該數(shù)據(jù)樣本為中心，左右各找?guī)讉€點(diǎn)椅寺，把這幾個樣本點(diǎn)進(jìn)行線性回歸浑槽，算出一條局部的直線蒋失，然后把位置樣本x代入這條直線，就算出了對應(yīng)的y桐玻，完成了一次線性回歸篙挽。也就是每次來一個數(shù)據(jù)點(diǎn)，都要訓(xùn)練一條局部直線镊靴，也即訓(xùn)練一次铣卡，就用一次。LWR和KNN很相似偏竟，都是為位置數(shù)據(jù)量身定制煮落，在局部進(jìn)行訓(xùn)練。
KNN和K-Means的區(qū)別
