一褪子、了解 K-means。

　K-Means算法是無監(jiān)督的聚類算法骗村，它實(shí)現(xiàn)起來比較簡單嫌褪，聚類效果也不錯(cuò)，因此應(yīng)用很廣泛胚股。K-Means算法有大量的變體笼痛，本文就從最傳統(tǒng)的K-Means算法講起，在其基礎(chǔ)上講述K-Means的優(yōu)化變體方法信轿。包括初始化優(yōu)化K-Means++, 距離計(jì)算優(yōu)化elkan K-Means算法和大數(shù)據(jù)情況下的優(yōu)化Mini Batch K-Means算法晃痴。

? ??K-Means算法的思想很簡單残吩，對于給定的樣本集，按照樣本之間的距離大小倘核，將樣本集劃分為K個(gè)簇泣侮。讓簇內(nèi)的點(diǎn)盡量緊密的連在一起，而讓簇間的距離盡量的大紧唱。

二活尊、傳統(tǒng)K-Means算法流程。

1漏益、隨機(jī)選擇K個(gè)聚類的初始中心蛹锰。

2、對任意一個(gè)樣本點(diǎn)绰疤，求其到K個(gè)聚類中心的距離铜犬，將樣本點(diǎn)歸類到距離最小的中心的聚類。

3轻庆、每次迭代過程中癣猾，利用均值等方法更新各個(gè)聚類的中心點(diǎn)（質(zhì)心）。

4余爆、對K個(gè)聚類中心纷宇，利用2、3步迭代更新后蛾方，如果位置點(diǎn)變化很小(可以設(shè)置閾值)像捶，則認(rèn)為達(dá)到穩(wěn)定狀態(tài)，迭代結(jié)束桩砰。（畫圖時(shí)拓春，可以對不同的聚類塊和聚類中心可選擇不同的顏色標(biāo)注）

優(yōu)點(diǎn)?

1、原理比較簡單五芝，實(shí)現(xiàn)也是很容易痘儡，收斂速度快。?

2枢步、聚類效果較優(yōu)沉删。?

3、算法的可解釋度比較強(qiáng)醉途。?

4矾瑰、主要需要調(diào)參的參數(shù)僅僅是簇?cái)?shù)k。

缺點(diǎn)?

1隘擎、K值的選取不好把握?

2殴穴、對于不是凸的數(shù)據(jù)集比較難收斂?

3、如果各隱含類別的數(shù)據(jù)不平衡，比如各隱含類別的數(shù)據(jù)量嚴(yán)重失衡采幌，或者各隱含類別的方差不同劲够，則聚類效果不佳。?

4休傍、 最終結(jié)果和初始點(diǎn)的選擇有關(guān)征绎，容易陷入局部最優(yōu)。

5磨取、對噪音和異常點(diǎn)比較的敏感人柿。

三、 K-Means初始化優(yōu)化

二分K-Means

????解決K-Means算法對初始簇心比較敏感的問題忙厌，二分K-Means算法是一種弱化初始質(zhì)心的一種算法凫岖。

算法流程：

1、將所有樣本數(shù)據(jù)作為一個(gè)簇放到一個(gè)隊(duì)列中逢净。

2哥放、從隊(duì)列中選擇一個(gè)簇進(jìn)行K-Means算法劃分，劃分為兩個(gè)子簇汹胃，并將子簇添加到隊(duì)列中婶芭。

3、循環(huán)迭代步驟2操作着饥，直到中止條件達(dá)到(聚簇?cái)?shù)量、最小平方誤差惰赋、迭代次數(shù)等)宰掉。

4、隊(duì)列中的簇就是最終的分類簇集合赁濒。

從隊(duì)列中選擇劃分聚簇的規(guī)則一般有兩種方式轨奄；分別如下：

1、對所有簇計(jì)算誤差和SSE(SSE也可以認(rèn)為是距離函數(shù)的一種變種)拒炎，選擇SSE最大的聚簇進(jìn)行劃分操作(優(yōu)選這種策略)挪拟。

2、選擇樣本數(shù)據(jù)量最多的簇進(jìn)行劃分操作：

K-Means++

????由于 K-means 算法的分類結(jié)果會(huì)受到初始點(diǎn)的選取而有所區(qū)別击你，因此有提出這種算法的改進(jìn):?K-means++?玉组。

????其實(shí)這個(gè)算法也只是對初始點(diǎn)的選擇有改進(jìn)而已，其他步驟都一樣丁侄。初始質(zhì)心選取的基本思路就是惯雳，初始的聚類中心之間的相互距離要盡可能的遠(yuǎn)。

算法流程：

1鸿摇、隨機(jī)選取一個(gè)樣本作為第一個(gè)聚類中心 c1石景；

2、計(jì)算每個(gè)樣本與當(dāng)前已有類聚中心最短距離（即與最近一個(gè)聚類中心的距離），用?D(x)表示潮孽；這個(gè)值越大揪荣，表示被選取作為聚類中心的概率較大；最后往史，用輪盤法選出下一個(gè)聚類中心仗颈。

3、重復(fù)步驟2怠堪，知道選出 k 個(gè)聚類中心揽乱。

4、選出初始點(diǎn)（聚類中心）粟矿，就繼續(xù)使用標(biāo)準(zhǔn)的 k-means 算法了凰棉。

盡管K-Means++在聚類中心的計(jì)算上浪費(fèi)了很多時(shí)間，但是在迭代過程中陌粹，k-mean 本身能快速收斂撒犀，因此算法實(shí)際上降低了計(jì)算時(shí)間。

K-Means||

? ? ? 解決K-Means++算法缺點(diǎn)而產(chǎn)生的一種算法掏秩；主要思路是改變每次遍歷時(shí)候的取樣規(guī)則或舞，并非按照K-Means++算法每次遍歷只獲取一個(gè)樣本，而是每次獲取K個(gè)樣本蒙幻，重復(fù)該取樣操作O(logn)次(n是樣本的個(gè)數(shù))映凳，然后再將這些抽樣出來的樣本聚類出K個(gè)點(diǎn)，最后使用這K個(gè)點(diǎn)作為K-Means算法的初始聚簇中心點(diǎn)邮破。實(shí)踐證明：一般5次重復(fù)采用就可以保證一個(gè)比較好的聚簇中心點(diǎn)诈豌。

算法流程：

1、在N個(gè)樣本中抽K個(gè)樣本抒和，一共抽logn次矫渔，形成一個(gè)新的樣本集，一共有Klogn個(gè)數(shù)據(jù)摧莽。

2庙洼、在新數(shù)據(jù)集中使用K-Means算法，找到K個(gè)聚簇中心镊辕。

3油够、把這K個(gè)聚簇中心放到最初的樣本集中，作為初始聚簇中心丑蛤。

4叠聋、原數(shù)據(jù)集根據(jù)上述初始聚簇中心，再用K-Means算法計(jì)算出最終的聚簇受裹。

Canopy算法

????????Canopy屬于一種‘粗’聚類算法碌补，即使用一種簡單虏束、快捷的距離計(jì)算方法將數(shù)據(jù)集分為若干可重疊的子集canopy，這種算法不需要指定k值厦章、但精度較低镇匀，可以結(jié)合K-means算法一起使用：先由Canopy算法進(jìn)行粗聚類得到k個(gè)質(zhì)心，再使用K-means算法進(jìn)行聚類袜啃。

?算法流程：

?1汗侵、將原始樣本集隨機(jī)排列成樣本列表L=[x1,x2,...,xm]（排列好后不再更改），根據(jù)先驗(yàn)知識(shí)或交叉驗(yàn)證調(diào)參設(shè)定初始距離閾值T1群发、T2晰韵，且T1>T2 。

2熟妓、從列表L中隨機(jī)選取一個(gè)樣本P作為第一個(gè)canopy的質(zhì)心雪猪，并將P從列表中刪除。

3起愈、從列表L中隨機(jī)選取一個(gè)樣本Q只恨，計(jì)算Q到所有質(zhì)心的距離，考察其中最小的距離D：

如果D≤T1抬虽，則給Q一個(gè)弱標(biāo)記官觅，表示Q屬于該canopy，并將Q加入其中阐污；

如果D≤T2休涤，則給Q一個(gè)強(qiáng)標(biāo)記，表示Q屬于該canopy笛辟，且和質(zhì)心非常接近滑绒，所以將該canopy的質(zhì)心設(shè)為所有強(qiáng)標(biāo)記樣本的中心位置，并將Q從列表L中刪除隘膘；

?如果D>T1，則Q形成一個(gè)新的聚簇杠览，并將Q從列表L中刪除弯菊。

4、重復(fù)第三步直到列表L中元素個(gè)數(shù)為零踱阿。

注意

1管钳、‘粗’距離計(jì)算的選擇對canopy的分布非常重要，如選擇其中某個(gè)屬性软舌、其他外部屬性才漆、歐式距離等。

2佛点、當(dāng)T2<D≤T1時(shí)醇滥，樣本不會(huì)從列表中被刪除黎比，而是繼續(xù)參與下一輪迭代，直到成為新的質(zhì)心或者某個(gè)canopy的強(qiáng)標(biāo)記成員鸳玩。

3阅虫、T1、T2的取值影響canopy的重疊率及粒度：當(dāng)T1過大時(shí)不跟，會(huì)使樣本屬于多個(gè)canopy颓帝，各個(gè)canopy間區(qū)別不明顯；當(dāng)T2過大時(shí)窝革，會(huì)減少canopy個(gè)數(shù)购城，而當(dāng)T2過小時(shí)，會(huì)增加canopy個(gè)數(shù)虐译，同時(shí)增加計(jì)算時(shí)間瘪板。

4、canopy之間可能存在重疊的情況菱蔬，但是不會(huì)存在某個(gè)樣本不屬于任何canopy的情況篷帅。

5、Canopy算法可以消除孤立點(diǎn)拴泌，即刪除包含樣本數(shù)目較少的canopy魏身，往往這些canopy包含的是孤立點(diǎn)或噪音點(diǎn)。

Canopy算法常用應(yīng)用場景

????由于K-Means算法存在初始聚簇中心點(diǎn)敏感的問題蚪腐，常用使用Canopy+K-Means算法混合形式進(jìn)行模型構(gòu)建箭昵。

1、先使用canopy算法進(jìn)行“粗”聚類得到K個(gè)聚類中心點(diǎn)回季。

2家制、K-Means算法使用Canopy算法得到的K個(gè)聚類中心點(diǎn)作為初始中心點(diǎn)，進(jìn)行“細(xì)”聚類泡一。

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

1颤殴、執(zhí)行速度快(先進(jìn)行了一次聚簇中心點(diǎn)選擇的預(yù)處理)；

2鼻忠、不需要給定K值涵但，應(yīng)用場景多。

3帖蔓、能夠緩解K-Means算法對于初始聚類中心點(diǎn)敏感的問題矮瘟。

Mini Batch K-Means

????Mini Batch K-Means算法是K-Means算法的一種優(yōu)化變種，采用小規(guī)模的數(shù)據(jù)子集(每次訓(xùn)練使用的數(shù)據(jù)集是在訓(xùn)練算法的時(shí)候隨機(jī)抽取的數(shù)據(jù)子集)減少計(jì)算時(shí)間塑娇，同時(shí)試圖優(yōu)化目標(biāo)函數(shù)澈侠；Mini Batch K-Means算法可以減少K-Means算法的收斂時(shí)間，而且產(chǎn)生的結(jié)果效果只是略差于標(biāo)準(zhǔn)K-Means算法埋酬。

?算法流程：

1哨啃、首先抽取部分?jǐn)?shù)據(jù)集烧栋，使用K-Means算法構(gòu)建出K個(gè)聚簇點(diǎn)的模型。

2棘催、繼續(xù)抽取訓(xùn)練數(shù)據(jù)集中的部分?jǐn)?shù)據(jù)集樣本數(shù)據(jù)劲弦，并將其添加到模型中，分配給距離最近的聚簇中心點(diǎn)醇坝。

3邑跪、更新聚簇的中心點(diǎn)值。

4呼猪、循環(huán)迭代第二步和第三步操作画畅，直到中心點(diǎn)穩(wěn)定或者達(dá)到迭代次數(shù)，停止計(jì)算操作宋距。

四轴踱、聚類大綱

http://www.reibang.com/p/f0727880c9c0