1. Kmeans聚類算法簡介
由于具有出色的速度和良好的可擴展性，Kmeans聚類算法算得上是最著名的聚類方法。Kmeans算法是一個重復移動類中心點的過程，把類的中心點，也稱重心(centroids)，移動到其包含成員的平均位置，然后重新劃分其內(nèi)部成員。k是算法計算出的超參數(shù)，表示類的數(shù)量；Kmeans可以自動分配樣本到不同的類，但是不能決定究竟要分幾個類。k必須是一個比訓練集樣本數(shù)小的正整數(shù)。有時，類的數(shù)量是由問題內(nèi)容指定的。例如，一個鞋廠有三種新款式，它想知道每種新款式都有哪些潛在客戶，于是它調(diào)研客戶，然后從數(shù)據(jù)里找出三類。也有一些問題沒有指定聚類的數(shù)量，最優(yōu)的聚類數(shù)量是不確定的。后面我將會詳細介紹一些方法來估計最優(yōu)聚類數(shù)量。
Kmeans的參數(shù)是類的重心位置和其內(nèi)部觀測值的位置。與廣義線性模型和決策樹類似，Kmeans參數(shù)的最優(yōu)解也是以成本函數(shù)最小化為目標。Kmeans成本函數(shù)公式如下：
μiμi是第kk個類的重心位置。成本函數(shù)是各個類畸變程度(distortions)之和。每個類的畸變程度等于該類重心與其內(nèi)部成員位置距離的平方和。若類內(nèi)部的成員彼此間越緊湊則類的畸變程度越小，反之，若類內(nèi)部的成員彼此間越分散則類的畸變程度越大。求解成本函數(shù)最小化的參數(shù)就是一個重復配置每個類包含的觀測值，并不斷移動類重心的過程。首先，類的重心是隨機確定的位置。實際上，重心位置等于隨機選擇的觀測值的位置。每次迭代的時候，Kmeans會把觀測值分配到離它們最近的類，然后把重心移動到該類全部成員位置的平均值那里。
2.1 根據(jù)問題內(nèi)容確定
這種方法就不多講了，文章開篇就舉了一個例子。
2.2 肘部法則
如果問題中沒有指定kk的值，可以通過肘部法則這一技術(shù)來估計聚類數(shù)量。肘部法則會把不同kk值的成本函數(shù)值畫出來。隨著kk值的增大，平均畸變程度會減??；每個類包含的樣本數(shù)會減少，于是樣本離其重心會更近。但是，隨著kk值繼續(xù)增大，平均畸變程度的改善效果會不斷減低。kk值增大過程中，畸變程度的改善效果下降幅度最大的位置對應的kk值就是肘部。為了讓讀者看的更加明白，下面讓我們通過一張圖用肘部法則來確定最佳的kk值。下圖數(shù)據(jù)明顯可分成兩類：
從圖中可以看出，k值從1到2時，平均畸變程度變化最大。超過2以后，平均畸變程度變化顯著降低。因此最佳的k是2。
2.3 與層次聚類結(jié)合
經(jīng)常會產(chǎn)生較好的聚類結(jié)果的一個有趣策略是，首先采用層次凝聚算法決定結(jié)果粗的數(shù)目，并找到一個初始聚類，然后用迭代重定位來改進該聚類。
2.4 穩(wěn)定性方法
穩(wěn)定性方法對一個數(shù)據(jù)集進行2次重采樣產(chǎn)生2個數(shù)據(jù)子集，再用相同的聚類算法對2個數(shù)據(jù)子集進行聚類，產(chǎn)生2個具有kk個聚類的聚類結(jié)果，計算2個聚類結(jié)果的相似度的分布情況。2個聚類結(jié)果具有高的相似度說明kk個聚類反映了穩(wěn)定的聚類結(jié)構(gòu)，其相似度可以用來估計聚類個數(shù)。采用次方法試探多個kk，找到合適的k值。
2.5 系統(tǒng)演化方法
系統(tǒng)演化方法將一個數(shù)據(jù)集視為偽熱力學系統(tǒng)，當數(shù)據(jù)集被劃分為kk個聚類時稱系統(tǒng)處于狀態(tài)kk。系統(tǒng)由初始狀態(tài)k=1k=1出發(fā)，經(jīng)過分裂過程和合并過程，系統(tǒng)將演化到它的穩(wěn)定平衡狀態(tài)?kiki?，其所對應的聚類結(jié)構(gòu)決定了最優(yōu)類數(shù)?kiki?。系統(tǒng)演化方法能提供關于所有聚類之間的相對邊界距離或可分程度，它適用于明顯分離的聚類結(jié)構(gòu)和輕微重疊的聚類結(jié)構(gòu)。
2.6 使用canopy算法進行初始劃分
基于Canopy Method的聚類算法將聚類過程分為兩個階段
(1) 聚類最耗費計算的地方是計算對象相似性的時候，Canopy Method在第一階段選擇簡單、計算代價較低的方法計算對象相似性，將相似的對象放在一個子集中，這個子集被叫做Canopy，通過一系列計算得到若干Canopy，Canopy之間可以是重疊的，但不會存在某個對象不屬于任何Canopy的情況，可以把這一階段看做數(shù)據(jù)預處理；
(2) 在各個Canopy內(nèi)使用傳統(tǒng)的聚類方法(如Kmeans)，不屬于同一Canopy的對象之間不進行相似性計算。
從這個方法起碼可以看出兩點好處：首先，Canopy不要太大且Canopy之間重疊的不要太多的話會大大減少后續(xù)需要計算相似性的對象的個數(shù)；其次，類似于Kmeans這樣的聚類方法是需要人為指出K的值的，通過(1)得到的Canopy個數(shù)完全可以作為這個k值，一定程度上減少了選擇k的盲目性。
其他方法如貝葉斯信息準則方法(BIC)可參看文獻[4]。
選擇適當?shù)某跏假|(zhì)心是基本kmeans算法的關鍵步驟。常見的方法是隨機的選取初始中心，但是這樣簇的質(zhì)量常常很差。處理選取初始質(zhì)心問題的一種常用技術(shù)是：多次運行，每次使用一組不同的隨機初始質(zhì)心，然后選取具有最小SSE(誤差的平方和)的簇集。這種策略簡單，但是效果可能不好，這取決于數(shù)據(jù)集和尋找的簇的個數(shù)。
第二種有效的方法是，取一個樣本，并使用層次聚類技術(shù)對它聚類。從層次聚類中提取kk個簇，并用這些簇的質(zhì)心作為初始質(zhì)心。該方法通常很有效，但僅對下列情況有效：(1)樣本相對較小，例如數(shù)百到數(shù)千(層次聚類開銷較大)；(2)?kk相對于樣本大小較小。
第三種選擇初始質(zhì)心的方法，隨機地選擇第一個點，或取所有點的質(zhì)心作為第一個點。然后，對于每個后繼初始質(zhì)心，選擇離已經(jīng)選取過的初始質(zhì)心最遠的點。使用這種方法，確保了選擇的初始質(zhì)心不僅是隨機的，而且是散開的。但是，這種方法可能選中離群點。此外，求離當前初始質(zhì)心集最遠的點開銷也非常大。為了克服這個問題，通常該方法用于點樣本。由于離群點很少(多了就不是離群點了)，它們多半不會在隨機樣本中出現(xiàn)。計算量也大幅減少。
第四種方法就是上面提到的canopy算法。
常用的距離度量方法包括：歐幾里得距離和余弦相似度。兩者都是評定個體間差異的大小的。
歐氏距離是最常見的距離度量，而余弦相似度則是最常見的相似度度量，很多的距離度量和相似度度量都是基于這兩者的變形和衍生，所以下面重點比較下兩者在衡量個體差異時實現(xiàn)方式和應用環(huán)境上的區(qū)別。
借助三維坐標系來看下歐氏距離和余弦相似度的區(qū)別：
從圖上可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐標(即個體特征維度的數(shù)值)直接相關；而余弦相似度衡量的是空間向量的夾角，更加的是體現(xiàn)在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐標軸原點，那么這個時候余弦相似cosθ是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發(fā)生改變，這就是歐氏距離和余弦相似度的不同之處。
根據(jù)歐氏距離和余弦相似度各自的計算方式和衡量特征，分別適用于不同的數(shù)據(jù)分析模型：歐氏距離能夠體現(xiàn)個體數(shù)值特征的絕對差異，所以更多的用于需要從維度的數(shù)值大小中體現(xiàn)差異的分析，如使用用戶行為指標分析用戶價值的相似度或差異；而余弦相似度更多的是從方向上區(qū)分差異，而對絕對的數(shù)值不敏感，更多的用于使用用戶對內(nèi)容評分來區(qū)分用戶興趣的相似度和差異，同時修正了用戶間可能存在的度量標準不統(tǒng)一的問題(因為余弦相似度對絕對數(shù)值不敏感)。
因為歐幾里得距離度量會受指標不同單位刻度的影響，所以一般需要先進行標準化，同時距離越大，個體間差異越大；空間向量余弦夾角的相似度度量不會受指標刻度的影響，余弦值落于區(qū)間[-1,1]，值越大，差異越小。但是針對具體應用，什么情況下使用歐氏距離，什么情況下使用余弦相似度？
從幾何意義上來說，n維向量空間的一條線段作為底邊和原點組成的三角形，其頂角大小是不確定的。也就是說對于兩條空間向量，即使兩點距離一定，他們的夾角余弦值也可以隨意變化。感性的認識，當兩用戶評分趨勢一致時，但是評分值差距很大，余弦相似度傾向給出更優(yōu)解。舉個極端的例子，兩用戶只對兩件商品評分，向量分別為(3,3)和(5,5)，這兩位用戶的認知其實是一樣的，但是歐式距離給出的解顯然沒有余弦值合理。
我們把機器學習定義為對系統(tǒng)的設計和學習，通過對經(jīng)驗數(shù)據(jù)的學習，將任務效果的不斷改善作為一個度量標準。Kmeans是一種非監(jiān)督學習，沒有標簽和其他信息來比較聚類結(jié)果。但是，我們還是有一些指標可以評估算法的性能。我們已經(jīng)介紹過類的畸變程度的度量方法。本節(jié)為將介紹另一種聚類算法效果評估方法稱為輪廓系數(shù)(Silhouette Coefficient)。輪廓系數(shù)是類的密集與分散程度的評價指標。它會隨著類的規(guī)模增大而增大。彼此相距很遠，本身很密集的類，其輪廓系數(shù)較大，彼此集中，本身很大的類，其輪廓系數(shù)較小。輪廓系數(shù)是通過所有樣本計算出來的，計算每個樣本分數(shù)的均值，計算公式如下：
aa是每一個類中樣本彼此距離的均值，bb是一個類中樣本與其最近的那個類的所有樣本的距離的均值。
輸入：聚類個數(shù)k，數(shù)據(jù)集XmxnXmxn。?
輸出：滿足方差最小標準的k個聚類。
(1) 選擇k個初始中心點，例如c[0]=X[0] , … , c[k-1]=X[k-1]；
(2) 對于X[0]….X[n]，分別與c[0]…c[k-1]比較，假定與c[i]差值最少，就標記為i；
(3) 對于所有標記為i點，重新計算c[i]={ 所有標記為i的樣本的每個特征的均值}；
(4) 重復(2)(3)，直到所有c[i]值的變化小于給定閾值或者達到最大迭代次數(shù)。
Kmeans的時間復雜度：O(tkmn)，空間復雜度：O((m+k)n)。其中，t為迭代次數(shù)，k為簇的數(shù)目，m為樣本數(shù)，n為特征數(shù)。
7.1 優(yōu)點
(1). 算法原理簡單。需要調(diào)節(jié)的超參數(shù)就是一個k。
(2). 由具有出色的速度和良好的可擴展性。
7.2 缺點
(1). 在 Kmeans 算法中?kk?需要事先確定，這個?kk?值的選定有時候是比較難確定。
(2). 在 Kmeans 算法中，首先需要初始k個聚類中心，然后以此來確定一個初始劃分，然后對初始劃分進行優(yōu)化。這個初始聚類中心的選擇對聚類結(jié)果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結(jié)果。多設置一些不同的初值，對比最后的運算結(jié)果，一直到結(jié)果趨于穩(wěn)定結(jié)束。
(3). 該算法需要不斷地進行樣本分類調(diào)整，不斷地計算調(diào)整后的新的聚類中心，因此當數(shù)據(jù)量非常大時，算法的時間開銷是非常大的。
(4). 對離群點很敏感。
(5). 從數(shù)據(jù)表示角度來說，在 Kmeans 中,我們用單個點來對 cluster 進行建模，這實際上是一種最簡化的數(shù)據(jù)建模形式。這種用點來對 cluster 進行建模實際上就已經(jīng)假設了各 cluster的數(shù)據(jù)是呈圓形(或者高維球形)或者方形等分布的。不能發(fā)現(xiàn)非凸形狀的簇。但在實際生活中，很少能有這種情況。所以在 GMM 中，使用了一種更加一般的數(shù)據(jù)表示，也就是高斯分布。
(6). 從數(shù)據(jù)先驗的角度來說，在 Kmeans 中,我們假設各個 cluster 的先驗概率是一樣的,但是各個 cluster 的數(shù)據(jù)量可能是不均勻的。舉個例子,cluster A 中包含了10000個樣本,cluster B 中只包含了100個。那么對于一個新的樣本,在不考慮其與A cluster、 B cluster 相似度的情況,其屬于 cluster A 的概率肯定是要大于 cluster B的。
(7). 在 Kmeans 中，通常采用歐氏距離來衡量樣本與各個 cluster 的相似度。這種距離實際上假設了數(shù)據(jù)的各個維度對于相似度的衡量作用是一樣的。但在 GMM 中，相似度的衡量使用的是后驗概率?αcG(x|μc,∑c)αcG(x|μc,∑c)?，通過引入?yún)f(xié)方差矩陣,我們就可以對各維度數(shù)據(jù)的不同重要性進行建模。
(8). 在 Kmeans 中，各個樣本點只屬于與其相似度最高的那個 cluster ，這實際上是一種 hard clustering 。
針對Kmeans算法的缺點，很多前輩提出了一些改進的算法。例如 K-modes 算法，實現(xiàn)對離散數(shù)據(jù)的快速聚類，保留了Kmeans算法的效率同時將Kmeans的應用范圍擴大到離散數(shù)據(jù)。還有K-Prototype算法，可以對離散與數(shù)值屬性兩種混合的數(shù)據(jù)進行聚類，在K-prototype中定義了一個對數(shù)值與離散屬性都計算的相異性度量標準。當然還有其它的一些算法，這里我 就不一一列舉了。
Kmeans 與 GMM 更像是一種 top-down 的思想，它們首先要解決的問題是，確定 cluster 數(shù)量，也就是 k 的取值。在確定了 k 后,再來進行數(shù)據(jù)的聚類。而 hierarchical clustering 則是一種 bottom-up 的形式，先有數(shù)據(jù)，然后通過不斷選取最相似的數(shù)據(jù)進行聚類。
