1. Kmeans聚類算法簡(jiǎn)介
由于具有出色的速度和良好的可擴(kuò)展性萌衬，Kmeans聚類算法算得上是最著名的聚類方法。Kmeans算法是一個(gè)重復(fù)移動(dòng)類中心點(diǎn)的過(guò)程，把類的中心點(diǎn)掌实，也稱重心(centroids)生均，移動(dòng)到其包含成員的平均位置听想，然后重新劃分其內(nèi)部成員。k是算法計(jì)算出的超參數(shù)马胧，表示類的數(shù)量汉买；Kmeans可以自動(dòng)分配樣本到不同的類，但是不能決定究竟要分幾個(gè)類佩脊。k必須是一個(gè)比訓(xùn)練集樣本數(shù)小的正整數(shù)录别。有時(shí)，類的數(shù)量是由問(wèn)題內(nèi)容指定的邻吞。例如组题，一個(gè)鞋廠有三種新款式，它想知道每種新款式都有哪些潛在客戶抱冷，于是它調(diào)研客戶崔列，然后從數(shù)據(jù)里找出三類。也有一些問(wèn)題沒(méi)有指定聚類的數(shù)量，最優(yōu)的聚類數(shù)量是不確定的赵讯。后面我將會(huì)詳細(xì)介紹一些方法來(lái)估計(jì)最優(yōu)聚類數(shù)量盈咳。
Kmeans的參數(shù)是類的重心位置和其內(nèi)部觀測(cè)值的位置。與廣義線性模型和決策樹類似边翼，Kmeans參數(shù)的最優(yōu)解也是以成本函數(shù)最小化為目標(biāo)鱼响。Kmeans成本函數(shù)公式如下：
μiμi是第kk個(gè)類的重心位置。成本函數(shù)是各個(gè)類畸變程度(distortions)之和组底。每個(gè)類的畸變程度等于該類重心與其內(nèi)部成員位置距離的平方和丈积。若類內(nèi)部的成員彼此間越緊湊則類的畸變程度越小，反之债鸡，若類內(nèi)部的成員彼此間越分散則類的畸變程度越大江滨。求解成本函數(shù)最小化的參數(shù)就是一個(gè)重復(fù)配置每個(gè)類包含的觀測(cè)值，并不斷移動(dòng)類重心的過(guò)程厌均。首先唬滑，類的重心是隨機(jī)確定的位置。實(shí)際上棺弊，重心位置等于隨機(jī)選擇的觀測(cè)值的位置晶密。每次迭代的時(shí)候，Kmeans會(huì)把觀測(cè)值分配到離它們最近的類模她，然后把重心移動(dòng)到該類全部成員位置的平均值那里稻艰。
2.1 根據(jù)問(wèn)題內(nèi)容確定
這種方法就不多講了，文章開篇就舉了一個(gè)例子缝驳。
2.2 肘部法則
如果問(wèn)題中沒(méi)有指定kk的值连锯，可以通過(guò)肘部法則這一技術(shù)來(lái)估計(jì)聚類數(shù)量。肘部法則會(huì)把不同kk值的成本函數(shù)值畫出來(lái)用狱。隨著kk值的增大运怖，平均畸變程度會(huì)減小夏伊；每個(gè)類包含的樣本數(shù)會(huì)減少摇展，于是樣本離其重心會(huì)更近。但是溺忧，隨著kk值繼續(xù)增大咏连，平均畸變程度的改善效果會(huì)不斷減低。kk值增大過(guò)程中鲁森，畸變程度的改善效果下降幅度最大的位置對(duì)應(yīng)的kk值就是肘部祟滴。為了讓讀者看的更加明白，下面讓我們通過(guò)一張圖用肘部法則來(lái)確定最佳的kk值歌溉。下圖數(shù)據(jù)明顯可分成兩類：
從圖中可以看出垄懂，k值從1到2時(shí)骑晶，平均畸變程度變化最大。超過(guò)2以后草慧，平均畸變程度變化顯著降低桶蛔。因此最佳的k是2。
2.3 與層次聚類結(jié)合
經(jīng)常會(huì)產(chǎn)生較好的聚類結(jié)果的一個(gè)有趣策略是漫谷，首先采用層次凝聚算法決定結(jié)果粗的數(shù)目仔雷，并找到一個(gè)初始聚類，然后用迭代重定位來(lái)改進(jìn)該聚類舔示。
2.4 穩(wěn)定性方法
穩(wěn)定性方法對(duì)一個(gè)數(shù)據(jù)集進(jìn)行2次重采樣產(chǎn)生2個(gè)數(shù)據(jù)子集碟婆，再用相同的聚類算法對(duì)2個(gè)數(shù)據(jù)子集進(jìn)行聚類，產(chǎn)生2個(gè)具有kk個(gè)聚類的聚類結(jié)果斩郎，計(jì)算2個(gè)聚類結(jié)果的相似度的分布情況脑融。2個(gè)聚類結(jié)果具有高的相似度說(shuō)明kk個(gè)聚類反映了穩(wěn)定的聚類結(jié)構(gòu)喻频，其相似度可以用來(lái)估計(jì)聚類個(gè)數(shù)缩宜。采用次方法試探多個(gè)kk，找到合適的k值甥温。
2.5 系統(tǒng)演化方法
系統(tǒng)演化方法將一個(gè)數(shù)據(jù)集視為偽熱力學(xué)系統(tǒng)锻煌，當(dāng)數(shù)據(jù)集被劃分為kk個(gè)聚類時(shí)稱系統(tǒng)處于狀態(tài)kk。系統(tǒng)由初始狀態(tài)k=1k=1出發(fā)姻蚓，經(jīng)過(guò)分裂過(guò)程和合并過(guò)程宋梧，系統(tǒng)將演化到它的穩(wěn)定平衡狀態(tài)?kiki?，其所對(duì)應(yīng)的聚類結(jié)構(gòu)決定了最優(yōu)類數(shù)?kiki?狰挡。系統(tǒng)演化方法能提供關(guān)于所有聚類之間的相對(duì)邊界距離或可分程度捂龄，它適用于明顯分離的聚類結(jié)構(gòu)和輕微重疊的聚類結(jié)構(gòu)。
2.6 使用canopy算法進(jìn)行初始劃分
基于Canopy Method的聚類算法將聚類過(guò)程分為兩個(gè)階段
(1) 聚類最耗費(fèi)計(jì)算的地方是計(jì)算對(duì)象相似性的時(shí)候加叁，Canopy Method在第一階段選擇簡(jiǎn)單倦沧、計(jì)算代價(jià)較低的方法計(jì)算對(duì)象相似性，將相似的對(duì)象放在一個(gè)子集中它匕，這個(gè)子集被叫做Canopy展融，通過(guò)一系列計(jì)算得到若干Canopy，Canopy之間可以是重疊的豫柬，但不會(huì)存在某個(gè)對(duì)象不屬于任何Canopy的情況告希，可以把這一階段看做數(shù)據(jù)預(yù)處理；
(2) 在各個(gè)Canopy內(nèi)使用傳統(tǒng)的聚類方法(如Kmeans)烧给，不屬于同一Canopy的對(duì)象之間不進(jìn)行相似性計(jì)算燕偶。
從這個(gè)方法起碼可以看出兩點(diǎn)好處：首先，Canopy不要太大且Canopy之間重疊的不要太多的話會(huì)大大減少后續(xù)需要計(jì)算相似性的對(duì)象的個(gè)數(shù)础嫡；其次指么，類似于Kmeans這樣的聚類方法是需要人為指出K的值的，通過(guò)(1)得到的Canopy個(gè)數(shù)完全可以作為這個(gè)k值，一定程度上減少了選擇k的盲目性涧尿。
其他方法如貝葉斯信息準(zhǔn)則方法(BIC)可參看文獻(xiàn)[4]系奉。
選擇適當(dāng)?shù)某跏假|(zhì)心是基本kmeans算法的關(guān)鍵步驟。常見(jiàn)的方法是隨機(jī)的選取初始中心姑廉，但是這樣簇的質(zhì)量常常很差缺亮。處理選取初始質(zhì)心問(wèn)題的一種常用技術(shù)是：多次運(yùn)行，每次使用一組不同的隨機(jī)初始質(zhì)心桥言，然后選取具有最小SSE(誤差的平方和)的簇集萌踱。這種策略簡(jiǎn)單，但是效果可能不好号阿，這取決于數(shù)據(jù)集和尋找的簇的個(gè)數(shù)并鸵。
第二種有效的方法是，取一個(gè)樣本扔涧，并使用層次聚類技術(shù)對(duì)它聚類园担。從層次聚類中提取kk個(gè)簇，并用這些簇的質(zhì)心作為初始質(zhì)心枯夜。該方法通常很有效弯汰，但僅對(duì)下列情況有效：(1)樣本相對(duì)較小，例如數(shù)百到數(shù)千(層次聚類開銷較大)湖雹；(2)?kk相對(duì)于樣本大小較小咏闪。
第三種選擇初始質(zhì)心的方法，隨機(jī)地選擇第一個(gè)點(diǎn)摔吏，或取所有點(diǎn)的質(zhì)心作為第一個(gè)點(diǎn)鸽嫂。然后，對(duì)于每個(gè)后繼初始質(zhì)心征讲，選擇離已經(jīng)選取過(guò)的初始質(zhì)心最遠(yuǎn)的點(diǎn)据某。使用這種方法，確保了選擇的初始質(zhì)心不僅是隨機(jī)的稳诚，而且是散開的哗脖。但是，這種方法可能選中離群點(diǎn)扳还。此外才避，求離當(dāng)前初始質(zhì)心集最遠(yuǎn)的點(diǎn)開銷也非常大。為了克服這個(gè)問(wèn)題氨距，通常該方法用于點(diǎn)樣本桑逝。由于離群點(diǎn)很少(多了就不是離群點(diǎn)了)，它們多半不會(huì)在隨機(jī)樣本中出現(xiàn)俏让。計(jì)算量也大幅減少楞遏。
第四種方法就是上面提到的canopy算法茬暇。
常用的距離度量方法包括：歐幾里得距離和余弦相似度。兩者都是評(píng)定個(gè)體間差異的大小的寡喝。
歐氏距離是最常見(jiàn)的距離度量糙俗，而余弦相似度則是最常見(jiàn)的相似度度量，很多的距離度量和相似度度量都是基于這兩者的變形和衍生预鬓，所以下面重點(diǎn)比較下兩者在衡量個(gè)體差異時(shí)實(shí)現(xiàn)方式和應(yīng)用環(huán)境上的區(qū)別巧骚。
借助三維坐標(biāo)系來(lái)看下歐氏距離和余弦相似度的區(qū)別：
從圖上可以看出距離度量衡量的是空間各點(diǎn)間的絕對(duì)距離，跟各個(gè)點(diǎn)所在的位置坐標(biāo)(即個(gè)體特征維度的數(shù)值)直接相關(guān)格二；而余弦相似度衡量的是空間向量的夾角劈彪，更加的是體現(xiàn)在方向上的差異，而不是位置顶猜。如果保持A點(diǎn)的位置不變沧奴，B點(diǎn)朝原方向遠(yuǎn)離坐標(biāo)軸原點(diǎn)，那么這個(gè)時(shí)候余弦相似cosθ是保持不變的长窄，因?yàn)閵A角不變滔吠，而A、B兩點(diǎn)的距離顯然在發(fā)生改變抄淑，這就是歐氏距離和余弦相似度的不同之處屠凶。
根據(jù)歐氏距離和余弦相似度各自的計(jì)算方式和衡量特征驰后，分別適用于不同的數(shù)據(jù)分析模型：歐氏距離能夠體現(xiàn)個(gè)體數(shù)值特征的絕對(duì)差異肆资，所以更多的用于需要從維度的數(shù)值大小中體現(xiàn)差異的分析，如使用用戶行為指標(biāo)分析用戶價(jià)值的相似度或差異灶芝；而余弦相似度更多的是從方向上區(qū)分差異郑原，而對(duì)絕對(duì)的數(shù)值不敏感，更多的用于使用用戶對(duì)內(nèi)容評(píng)分來(lái)區(qū)分用戶興趣的相似度和差異夜涕，同時(shí)修正了用戶間可能存在的度量標(biāo)準(zhǔn)不統(tǒng)一的問(wèn)題(因?yàn)橛嘞蚁嗨贫葘?duì)絕對(duì)數(shù)值不敏感)犯犁。
因?yàn)闅W幾里得距離度量會(huì)受指標(biāo)不同單位刻度的影響，所以一般需要先進(jìn)行標(biāo)準(zhǔn)化女器，同時(shí)距離越大酸役，個(gè)體間差異越大；空間向量余弦?jiàn)A角的相似度度量不會(huì)受指標(biāo)刻度的影響驾胆，余弦值落于區(qū)間[-1,1]涣澡，值越大，差異越小丧诺。但是針對(duì)具體應(yīng)用入桂，什么情況下使用歐氏距離，什么情況下使用余弦相似度驳阎？
從幾何意義上來(lái)說(shuō)抗愁，n維向量空間的一條線段作為底邊和原點(diǎn)組成的三角形馁蒂，其頂角大小是不確定的。也就是說(shuō)對(duì)于兩條空間向量蜘腌，即使兩點(diǎn)距離一定沫屡，他們的夾角余弦值也可以隨意變化。感性的認(rèn)識(shí)撮珠，當(dāng)兩用戶評(píng)分趨勢(shì)一致時(shí)谁鳍，但是評(píng)分值差距很大，余弦相似度傾向給出更優(yōu)解劫瞳。舉個(gè)極端的例子倘潜，兩用戶只對(duì)兩件商品評(píng)分，向量分別為(3,3)和(5,5)志于，這兩位用戶的認(rèn)知其實(shí)是一樣的涮因，但是歐式距離給出的解顯然沒(méi)有余弦值合理。
我們把機(jī)器學(xué)習(xí)定義為對(duì)系統(tǒng)的設(shè)計(jì)和學(xué)習(xí)伺绽，通過(guò)對(duì)經(jīng)驗(yàn)數(shù)據(jù)的學(xué)習(xí)养泡，將任務(wù)效果的不斷改善作為一個(gè)度量標(biāo)準(zhǔn)。Kmeans是一種非監(jiān)督學(xué)習(xí)奈应，沒(méi)有標(biāo)簽和其他信息來(lái)比較聚類結(jié)果澜掩。但是，我們還是有一些指標(biāo)可以評(píng)估算法的性能杖挣。我們已經(jīng)介紹過(guò)類的畸變程度的度量方法肩榕。本節(jié)為將介紹另一種聚類算法效果評(píng)估方法稱為輪廓系數(shù)(Silhouette Coefficient)。輪廓系數(shù)是類的密集與分散程度的評(píng)價(jià)指標(biāo)惩妇。它會(huì)隨著類的規(guī)模增大而增大株汉。彼此相距很遠(yuǎn)，本身很密集的類歌殃，其輪廓系數(shù)較大乔妈，彼此集中，本身很大的類氓皱，其輪廓系數(shù)較小路召。輪廓系數(shù)是通過(guò)所有樣本計(jì)算出來(lái)的，計(jì)算每個(gè)樣本分?jǐn)?shù)的均值波材，計(jì)算公式如下：
aa是每一個(gè)類中樣本彼此距離的均值股淡，bb是一個(gè)類中樣本與其最近的那個(gè)類的所有樣本的距離的均值。
輸入：聚類個(gè)數(shù)k各聘，數(shù)據(jù)集XmxnXmxn揣非。?
輸出：滿足方差最小標(biāo)準(zhǔn)的k個(gè)聚類。
(1) 選擇k個(gè)初始中心點(diǎn)躲因，例如c[0]=X[0] , … , c[k-1]=X[k-1]早敬；
(2) 對(duì)于X[0]….X[n]忌傻，分別與c[0]…c[k-1]比較，假定與c[i]差值最少搞监，就標(biāo)記為i水孩；
(3) 對(duì)于所有標(biāo)記為i點(diǎn)，重新計(jì)算c[i]={ 所有標(biāo)記為i的樣本的每個(gè)特征的均值}琐驴；
(4) 重復(fù)(2)(3)俘种，直到所有c[i]值的變化小于給定閾值或者達(dá)到最大迭代次數(shù)。
Kmeans的時(shí)間復(fù)雜度：O(tkmn)绝淡，空間復(fù)雜度：O((m+k)n)宙刘。其中，t為迭代次數(shù)牢酵，k為簇的數(shù)目悬包，m為樣本數(shù)，n為特征數(shù)馍乙。
7.1 優(yōu)點(diǎn)
(1). 算法原理簡(jiǎn)單布近。需要調(diào)節(jié)的超參數(shù)就是一個(gè)k。
(2). 由具有出色的速度和良好的可擴(kuò)展性丝格。
7.2 缺點(diǎn)
(1). 在 Kmeans 算法中?kk?需要事先確定撑瞧，這個(gè)?kk?值的選定有時(shí)候是比較難確定。
(2). 在 Kmeans 算法中显蝌，首先需要初始k個(gè)聚類中心预伺，然后以此來(lái)確定一個(gè)初始劃分，然后對(duì)初始劃分進(jìn)行優(yōu)化琅束。這個(gè)初始聚類中心的選擇對(duì)聚類結(jié)果有較大的影響扭屁，一旦初始值選擇的不好，可能無(wú)法得到有效的聚類結(jié)果涩禀。多設(shè)置一些不同的初值，對(duì)比最后的運(yùn)算結(jié)果然眼，一直到結(jié)果趨于穩(wěn)定結(jié)束艾船。
(3). 該算法需要不斷地進(jìn)行樣本分類調(diào)整，不斷地計(jì)算調(diào)整后的新的聚類中心高每，因此當(dāng)數(shù)據(jù)量非常大時(shí)屿岂，算法的時(shí)間開銷是非常大的。
(4). 對(duì)離群點(diǎn)很敏感鲸匿。
(5). 從數(shù)據(jù)表示角度來(lái)說(shuō)爷怀，在 Kmeans 中,我們用單個(gè)點(diǎn)來(lái)對(duì) cluster 進(jìn)行建模，這實(shí)際上是一種最簡(jiǎn)化的數(shù)據(jù)建模形式带欢。這種用點(diǎn)來(lái)對(duì) cluster 進(jìn)行建模實(shí)際上就已經(jīng)假設(shè)了各 cluster的數(shù)據(jù)是呈圓形(或者高維球形)或者方形等分布的运授。不能發(fā)現(xiàn)非凸形狀的簇烤惊。但在實(shí)際生活中，很少能有這種情況吁朦。所以在 GMM 中柒室，使用了一種更加一般的數(shù)據(jù)表示，也就是高斯分布逗宜。
(6). 從數(shù)據(jù)先驗(yàn)的角度來(lái)說(shuō)雄右，在 Kmeans 中,我們假設(shè)各個(gè) cluster 的先驗(yàn)概率是一樣的,但是各個(gè) cluster 的數(shù)據(jù)量可能是不均勻的。舉個(gè)例子,cluster A 中包含了10000個(gè)樣本,cluster B 中只包含了100個(gè)纺讲。那么對(duì)于一個(gè)新的樣本,在不考慮其與A cluster擂仍、 B cluster 相似度的情況,其屬于 cluster A 的概率肯定是要大于 cluster B的。
(7). 在 Kmeans 中熬甚，通常采用歐氏距離來(lái)衡量樣本與各個(gè) cluster 的相似度防楷。這種距離實(shí)際上假設(shè)了數(shù)據(jù)的各個(gè)維度對(duì)于相似度的衡量作用是一樣的。但在 GMM 中则涯，相似度的衡量使用的是后驗(yàn)概率?αcG(x|μc,∑c)αcG(x|μc,∑c)?复局，通過(guò)引入?yún)f(xié)方差矩陣,我們就可以對(duì)各維度數(shù)據(jù)的不同重要性進(jìn)行建模。
(8). 在 Kmeans 中粟判，各個(gè)樣本點(diǎn)只屬于與其相似度最高的那個(gè) cluster 亿昏，這實(shí)際上是一種 hard clustering 。
針對(duì)Kmeans算法的缺點(diǎn)档礁，很多前輩提出了一些改進(jìn)的算法角钩。例如 K-modes 算法，實(shí)現(xiàn)對(duì)離散數(shù)據(jù)的快速聚類呻澜，保留了Kmeans算法的效率同時(shí)將Kmeans的應(yīng)用范圍擴(kuò)大到離散數(shù)據(jù)递礼。還有K-Prototype算法，可以對(duì)離散與數(shù)值屬性兩種混合的數(shù)據(jù)進(jìn)行聚類羹幸，在K-prototype中定義了一個(gè)對(duì)數(shù)值與離散屬性都計(jì)算的相異性度量標(biāo)準(zhǔn)脊髓。當(dāng)然還有其它的一些算法，這里我 就不一一列舉了栅受。
Kmeans 與 GMM 更像是一種 top-down 的思想将硝，它們首先要解決的問(wèn)題是，確定 cluster 數(shù)量屏镊，也就是 k 的取值依疼。在確定了 k 后,再來(lái)進(jìn)行數(shù)據(jù)的聚類。而 hierarchical clustering 則是一種 bottom-up 的形式而芥，先有數(shù)據(jù)律罢，然后通過(guò)不斷選取最相似的數(shù)據(jù)進(jìn)行聚類。
