????????K-means 算法屬于聚類算法的一種叠荠。聚類算法就是把相似的對(duì)象通過靜態(tài)分類方法分成不同的組別或者更多的子集（subset），這樣讓在同一個(gè)子集中的成員對(duì)象都有相似的一些屬性龄章。聚類算法的任務(wù)是將數(shù)據(jù)集劃分為多個(gè)集群。在相同集群中的數(shù)據(jù)彼此會(huì)比不同集群的數(shù)據(jù)相似。通常來(lái)說瓦堵，聚類算法的目標(biāo)就是通過相似特征將數(shù)據(jù)分組并分配進(jìn)不同的集群中基协。
K-means 實(shí)現(xiàn)過程
K-means 聚類算法是一種非監(jiān)督學(xué)習(xí)算法，被用于非標(biāo)簽數(shù)據(jù)（data without defined categories or groups）菇用。該算法使用迭代細(xì)化來(lái)產(chǎn)生最終結(jié)果澜驮。算法輸入的是集群的數(shù)量 K 和數(shù)據(jù)集。數(shù)據(jù)集是每個(gè)數(shù)據(jù)點(diǎn)的一組功能惋鸥。?算法從 Κ 質(zhì)心的初始估計(jì)開始杂穷，其可以隨機(jī)生成或從數(shù)據(jù)集中隨機(jī)選擇。然后算法在下面兩個(gè)步驟之間迭代：
1.數(shù)據(jù)分配：
每個(gè)質(zhì)心定義一個(gè)集群卦绣。在此步驟中耐量，基于平方歐氏距離將每個(gè)數(shù)據(jù)點(diǎn)分配到其最近的質(zhì)心。更正式一點(diǎn)滤港，ci?屬于質(zhì)心集合?C?廊蜒，然后每個(gè)數(shù)據(jù)點(diǎn)?x?基于下面的公式被分配到一個(gè)集群中。
2. 質(zhì)心更新：
在此步驟中，重新計(jì)算質(zhì)心添履。這是通過獲取分配給該質(zhì)心集群的所有數(shù)據(jù)點(diǎn)的平均值來(lái)完成的屁倔。公式如下：
K-means 算法在步驟 1 和步驟 2 之間迭代，直到滿足停止條件（即暮胧，沒有數(shù)據(jù)點(diǎn)改變集群锐借，距離的總和最小化，或者達(dá)到一些最大迭代次數(shù)）往衷。
K 值的選擇
上述算法找到特定預(yù)選 K 值和數(shù)據(jù)集標(biāo)簽钞翔。為了找到數(shù)據(jù)中的集群數(shù)，用戶需要針對(duì)一系列 K 值運(yùn)行 K-means 聚類算法并比較結(jié)果炼绘。通常嗅战，沒有用于確定 K 的精確值的方法，但是可以使用以下技術(shù)獲得準(zhǔn)確的估計(jì)俺亮。
Elbow point 拐點(diǎn)方法
通常用于比較不同 K 值的結(jié)果的度量之一是數(shù)據(jù)點(diǎn)與其聚類質(zhì)心之間的平均距離驮捍。由于增加集群的數(shù)量將總是減少到數(shù)據(jù)點(diǎn)的距離，因此當(dāng) K 與數(shù)據(jù)點(diǎn)的數(shù)量相同時(shí)脚曾，增加 K 將總是減小該度量东且，達(dá)到零的極值。因此本讥，該指標(biāo)不能用作唯一目標(biāo)珊泳。相反鲁冯，繪制了作為 K 到質(zhì)心的平均距離的函數(shù)，并且可以使用減小率急劇變化的“拐點(diǎn)”來(lái)粗略地確定 K 色查。
DBI（Davies-Bouldin Index）
DBI 是一種評(píng)估度量的聚類算法的指標(biāo)薯演，通常用于評(píng)估 K-means 算法中 k 的取值。簡(jiǎn)單的理解就是：DBI 是聚類內(nèi)的距離與聚類外的距離的比值秧了。所以跨扮，DBI 的數(shù)值越小，表示分散程度越低验毡，聚類效果越好衡创。
還存在許多用于驗(yàn)證 K 的其他技術(shù)，包括交叉驗(yàn)證晶通，信息標(biāo)準(zhǔn)璃氢，信息理論跳躍方法，輪廓方法和 G 均值算法等等狮辽。
K-means 的缺點(diǎn)
需要提前確定 K 的選值或者需嘗試很多 K 的取值
數(shù)據(jù)必須是數(shù)字的一也，可以通過歐氏距離比較
對(duì)特殊數(shù)據(jù)敏感，很容易受特殊數(shù)據(jù)影響
對(duì)初始選擇的質(zhì)心/中心（centers）敏感
K-means 與 K-NN?的比較
之前介紹了?KNN （K 鄰近）算法喉脖，感覺這兩個(gè)算法的名字很接近塘秦，下面做一個(gè)簡(jiǎn)略對(duì)比。
K-means?：
聚類算法
用于非監(jiān)督學(xué)習(xí)
使用無(wú)標(biāo)簽數(shù)據(jù)
需要訓(xùn)練過程
K-NN：
分類算法
用于監(jiān)督學(xué)習(xí)
使用標(biāo)簽數(shù)據(jù)
沒有明顯的訓(xùn)練過程
一动看、KNN算法概述
鄰近算法，或者說K最近鄰(kNN爪幻，k-NearestNeighbor)分類算法是數(shù)據(jù)挖掘分類技術(shù)中最簡(jiǎn)單的方法之一菱皆。所謂K最近鄰，就是k個(gè)最近的鄰居的意思挨稿，說的是每個(gè)樣本都可以用它最接近的k個(gè)鄰居來(lái)代表仇轻。Cover和Hart在1968年提出了最初的鄰近算法。KNN是一種分類(classification)算法奶甘，它輸入基于實(shí)例的學(xué)習(xí)（instance-based learning）篷店，屬于懶惰學(xué)習(xí)（lazy learning）即KNN沒有顯式的學(xué)習(xí)過程，也就是說沒有訓(xùn)練階段臭家，數(shù)據(jù)集事先已有了分類和特征值疲陕，待收到新樣本后直接進(jìn)行處理。與急切學(xué)習(xí)（eager learning）相對(duì)應(yīng)钉赁。
KNN是通過測(cè)量不同特征值之間的距離進(jìn)行分類蹄殃。?
思路是：如果一個(gè)樣本在特征空間中的k個(gè)最鄰近的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也劃分為這個(gè)類別你踩。KNN算法中诅岩，所選擇的鄰居都是已經(jīng)正確分類的對(duì)象讳苦。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來(lái)決定待分樣本所屬的類別。
提到KNN吩谦，網(wǎng)上最常見的就是下面這個(gè)圖鸳谜，可以幫助大家理解。
我們要確定綠點(diǎn)屬于哪個(gè)顏色（紅色或者藍(lán)色）式廷，要做的就是選出距離目標(biāo)點(diǎn)距離最近的k個(gè)點(diǎn)咐扭，看這k個(gè)點(diǎn)的大多數(shù)顏色是什么顏色。當(dāng)k取3的時(shí)候懒棉，我們可以看出距離最近的三個(gè)草描，分別是紅色、紅色策严、藍(lán)色穗慕，因此得到目標(biāo)點(diǎn)為紅色。
算法的描述：
1）計(jì)算測(cè)試數(shù)據(jù)與各個(gè)訓(xùn)練數(shù)據(jù)之間的距離妻导；
2）按照距離的遞增關(guān)系進(jìn)行排序逛绵；
3）選取距離最小的K個(gè)點(diǎn)；
4）確定前K個(gè)點(diǎn)所在類別的出現(xiàn)頻率倔韭；
5）返回前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為測(cè)試數(shù)據(jù)的預(yù)測(cè)分類
二术浪、關(guān)于K的取值
K：臨近數(shù)，即在預(yù)測(cè)目標(biāo)點(diǎn)時(shí)取幾個(gè)臨近的點(diǎn)來(lái)預(yù)測(cè)寿酌。
K值得選取非常重要胰苏，因?yàn)椋?/p>
如果當(dāng)K的取值過小時(shí)，一旦有噪聲得成分存在們將會(huì)對(duì)預(yù)測(cè)產(chǎn)生比較大影響醇疼，例如取K值為1時(shí)硕并，一旦最近的一個(gè)點(diǎn)是噪聲，那么就會(huì)出現(xiàn)偏差秧荆，K值的減小就意味著整體模型變得復(fù)雜倔毙，容易發(fā)生過擬合；
如果K的值取的過大時(shí)乙濒，就相當(dāng)于用較大鄰域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)陕赃，學(xué)習(xí)的近似誤差會(huì)增大。這時(shí)與輸入目標(biāo)點(diǎn)較遠(yuǎn)實(shí)例也會(huì)對(duì)預(yù)測(cè)起作用颁股，使預(yù)測(cè)發(fā)生錯(cuò)誤么库。K值的增大就意味著整體的模型變得簡(jiǎn)單；
如果K==N的時(shí)候甘有，那么就是取全部的實(shí)例廊散，即為取實(shí)例中某分類下最多的點(diǎn)，就對(duì)預(yù)測(cè)沒有什么實(shí)際的意義了梧疲；
K的取值盡量要取奇數(shù)允睹，以保證在計(jì)算結(jié)果最后會(huì)產(chǎn)生一個(gè)較多的類別运准，如果取偶數(shù)可能會(huì)產(chǎn)生相等的情況，不利于預(yù)測(cè)缭受。
K的取法：
? 常用的方法是從k=1開始胁澳，使用檢驗(yàn)集估計(jì)分類器的誤差率。重復(fù)該過程米者，每次K增值1韭畸，允許增加一個(gè)近鄰。選取產(chǎn)生最小誤差率的K蔓搞。
一般k的取值不超過20胰丁，上限是n的開方，隨著數(shù)據(jù)集的增大喂分，K的值也要增大锦庸。
三、關(guān)于距離的選取
距離就是平面上兩個(gè)點(diǎn)的直線距離
關(guān)于距離的度量方法蒲祈，常用的有：歐幾里得距離甘萧、余弦值（cos）, 相關(guān)度 （correlation）, 曼哈頓距離 （Manhattan?distance）或其他。
Euclidean Distance 定義：
兩個(gè)點(diǎn)或元組P1=（x1梆掸，y1）和P2=（x2扬卷，y2）的歐幾里得距離是
距離公式為：（多個(gè)維度的時(shí)候是多個(gè)維度各自求差）
四、總結(jié)
KNN算法是最簡(jiǎn)單有效的分類算法酸钦，簡(jiǎn)單且容易實(shí)現(xiàn)怪得。當(dāng)訓(xùn)練數(shù)據(jù)集很大時(shí)，需要大量的存儲(chǔ)空間卑硫，而且需要計(jì)算待測(cè)樣本和訓(xùn)練數(shù)據(jù)集中所有樣本的距離汇恤，所以非常耗時(shí)
KNN對(duì)于隨機(jī)分布的數(shù)據(jù)集分類效果較差，對(duì)于類內(nèi)間距小拔恰，類間間距大的數(shù)據(jù)集分類效果好，而且對(duì)于邊界不規(guī)則的數(shù)據(jù)效果好于線性分類器基括。
KNN對(duì)于樣本不均衡的數(shù)據(jù)效果不好颜懊，需要進(jìn)行改進(jìn)。改進(jìn)的方法時(shí)對(duì)k個(gè)近鄰數(shù)據(jù)賦予權(quán)重风皿，比如距離測(cè)試樣本越近河爹，權(quán)重越大。
KNN很耗時(shí)桐款，時(shí)間復(fù)雜度為O(n)咸这，一般適用于樣本數(shù)較少的數(shù)據(jù)集，當(dāng)數(shù)據(jù)量大時(shí)魔眨，可以將數(shù)據(jù)以樹的形式呈現(xiàn)媳维，能提高速度酿雪，常用的有kd-tree和ball-tree。
