Clustering (聚類)是常見(jiàn)的unsupervised learning (無(wú)監(jiān)督學(xué)習(xí))方法，簡(jiǎn)單地說(shuō)就是把相似的數(shù)據(jù)樣本分到一組（簇），聚類的過(guò)程，我們并不清楚某一類是什么（通常無(wú)標(biāo)簽信息），需要實(shí)現(xiàn)的目標(biāo)只是把相似的樣本聚到一起，即只是利用樣本數(shù)據(jù)本身的分布規(guī)律。

聚類算法可以大致分為傳統(tǒng)聚類算法以及深度聚類算法：

• 傳統(tǒng)聚類算法主要是根據(jù)原特征+基于劃分/密度/層次等方法。

• 深度聚類方法主要是根據(jù)表征學(xué)習(xí)后的特征+傳統(tǒng)聚類算法。

二、kmeans聚類原理

kmeans聚類可以說(shuō)是聚類算法中最為常見(jiàn)的，它是基于劃分方法聚類的，原理是先初始化k個(gè)簇類中心，基于計(jì)算樣本與中心點(diǎn)的距離歸納各簇類下的所屬樣本，迭代實(shí)現(xiàn)樣本與其歸屬的簇類中心的距離為最小的目標(biāo)（如下目標(biāo)函數(shù)）。

其優(yōu)化算法步驟為：

1.隨機(jī)選擇 k 個(gè)樣本作為初始簇類中心（k為超參，代表簇類的個(gè)數(shù)?？梢詰{先驗(yàn)知識(shí)、驗(yàn)證法確定取值）；

2.針對(duì)數(shù)據(jù)集中每個(gè)樣本 計(jì)算它到 k 個(gè)簇類中心的距離，并將其歸屬到距離最小的簇類中心所對(duì)應(yīng)的類中；

3.針對(duì)每個(gè)簇類，重新計(jì)算它的簇類中心位置；

4.重復(fù)迭代上面 2 、3 兩步操作，直到達(dá)到某個(gè)中止條件（如迭代次數(shù)，簇類中心位置不變等）。

.... 完整代碼可見(jiàn)：https://github.com/aialgorithm/Blog 或文末閱讀原文

#kmeans算法是初始化隨機(jī)k個(gè)中心點(diǎn)
random.seed(1)
center?=?[[self.data[i][r]?for?i?in?range(1,?len((self.data)))]??
??????????????????????for?r?in?random.sample(range(len(self.data)),?k)]

#最大迭代次數(shù)iters
for?i?in?range(self.iters):
????class_dict?=?self.count_distance()?#計(jì)算距離，比較個(gè)樣本到各個(gè)中心的的出最小值，并劃分到相應(yīng)的類
????self.locate_center(class_dict)?#?重新計(jì)算中心點(diǎn)
????#print(self.data_dict)
????print("----------------迭代%d次----------------"%i)
????print(self.center_dict)??#聚類結(jié)果{k:{{center:[]},{distance：{item：0.0}，{classify:[]}}}}
????if?sorted(self.center)?==?sorted(self.new_center):
????????break
????else:
????????self.center?=?self.new_center
...

可見(jiàn)，Kmeans 聚類的迭代算法實(shí)際上是 EM 算法，EM 算法解決的是在概率模型中含有無(wú)法觀測(cè)的隱含變量情況下的參數(shù)估計(jì)問(wèn)題。

在 Kmeans 中的隱變量是每個(gè)類別所屬類別。Kmeans 算法迭代步驟中的 每次確認(rèn)中心點(diǎn)以后重新進(jìn)行標(biāo)記 對(duì)應(yīng) EM 算法中的 E 步 求當(dāng)前參數(shù)條件下的 Expectation 。而 根據(jù)標(biāo)記重新求中心點(diǎn) 對(duì)應(yīng) EM 算法中的 M 步 求似然函數(shù)最大化時(shí)（損失函數(shù)最小時(shí)）對(duì)應(yīng)的參數(shù) 。EM 算法的缺點(diǎn)是容易陷入局部極小值，這也是 Kmeans 有時(shí)會(huì)得到局部最優(yōu)解的原因。

三、選擇距離度量

kmeans 算法是基于距離相似度計(jì)算的，以確定各樣本所屬的最近中心點(diǎn)，常用距離度量有曼哈頓距離和歐式距離，具體可以見(jiàn)文章【全面歸納距離和相似度方法(7種)】

• 曼哈頓距離 公式：

• 歐幾里得距離 公式：

曼哈頓、歐幾里得距離的計(jì)算方法很簡(jiǎn)單，就是計(jì)算兩樣本(x,y)的各個(gè)特征i間的總距離。如下圖（二維特征的情況）藍(lán)線的距離即是曼哈頓距離（想象你在曼哈頓要從一個(gè)十字路口開(kāi)車到另外一個(gè)十字路口實(shí)際駕駛距離就是這個(gè)“曼哈頓距離”，也稱為城市街區(qū)距離），紅線為歐幾里得距離：

四、k 值的確定

kmeans劃分k個(gè)簇，不同k的情況，算法的效果可能差異就很大。K值的確定常用：先驗(yàn)法、手肘法等方法。

• 先驗(yàn)法

先驗(yàn)比較簡(jiǎn)單，就是憑借著業(yè)務(wù)知識(shí)確定k的取值。比如對(duì)于iris花數(shù)據(jù)集，我們大概知道有三種類別，可以按照k=3做聚類驗(yàn)證。從下圖可看出，對(duì)比聚類預(yù)測(cè)與實(shí)際的iris種類是比較一致的。

• 手肘法

可以知道k值越大，劃分的簇群越多，對(duì)應(yīng)的各個(gè)點(diǎn)到簇中心的距離的平方的和（類內(nèi)距離，WSS）越低，我們通過(guò)確定WSS隨著K的增加而減少的曲線拐點(diǎn)，作為K的取值。

手肘法的缺點(diǎn)在于需要人為判斷不夠自動(dòng)化，還有些其他方法如：

• 使用 Gap statistic 方法，確定k值。
• 驗(yàn)證不同K值的平均輪廓系數(shù)，越趨近1聚類效果越好。
• 驗(yàn)證不同K值的類內(nèi)距離/類間距離，值越小越好。
• ISODATA算法：它是在k-均值算法的基礎(chǔ)上，增加對(duì)聚類結(jié)果的“合并”和“分裂”兩個(gè)操作，確定最終的聚類結(jié)果。從而不用人為指定k值。

五、Kmeans的缺陷

5.1 初始化中心點(diǎn)的問(wèn)題

kmeans是采用隨機(jī)初始化中心點(diǎn)，而不同初始化的中心點(diǎn)對(duì)于算法結(jié)果的影響比較大。所以，針對(duì)這點(diǎn)更新出了Kmeans++算法，其初始化的思路是：各個(gè)簇類中心應(yīng)該互相離得越遠(yuǎn)越好?；诟鼽c(diǎn)到已有中心點(diǎn)的距離分量，依次隨機(jī)選取到k個(gè)元素作為中心點(diǎn)。離已確定的簇中心點(diǎn)的距離越遠(yuǎn)，越有可能（可能性正比與距離的平方）被選擇作為另一個(gè)簇的中心點(diǎn)。如下代碼。

#?Kmeans?++?算法基于距離概率選擇k個(gè)中心點(diǎn)
????????????#?1.隨機(jī)選擇一個(gè)點(diǎn)
????????????center?=?[]
????????????center.append(random.choice(range(len(self.data[0]))))
????????????#?2.根據(jù)距離的概率選擇其他中心點(diǎn)
????????????for?i?in?range(self.k?-?1):
????????????????weights?=?[self.distance_closest(self.data[0][x],?center)?
?????????????????????????for?x?in?range(len(self.data[0]))?if?x?not?in?center]
????????????????dp?=?[x?for?x?in?range(len(self.data[0]))?if?x?not?in?center]
????????????????total?=?sum(weights)
????????????????#基于距離設(shè)定權(quán)重
????????????????weights?=?[weight/total?for?weight?in?weights]
????????????????num?=?random.random()
????????????????x?=?-1
????????????????i?=?0
????????????????while?i?????????????????????x?+=?1
????????????????????i?+=?weights[x]
????????????????center.append(dp[x])
????????????center?=?[self.data_dict[self.data[0][center[k]]]?for?k?in?range(len(center))]

5.2 核Kmeans

基于歐式距離的 Kmeans 假設(shè)了了各個(gè)數(shù)據(jù)簇的數(shù)據(jù)具有一樣的的先驗(yàn)概率并呈現(xiàn)球形分布，但這種分布在實(shí)際生活中并不常見(jiàn)。面對(duì)非凸的數(shù)據(jù)分布形狀時(shí)我們可以引入核函數(shù)來(lái)優(yōu)化，這時(shí)算法又稱為核 Kmeans 算法，是核聚類方法的一種。核聚類方法的主要思想是通過(guò)一個(gè)非線性映射，將輸入空間中的數(shù)據(jù)點(diǎn)映射到高位的特征空間中，并在新的特征空間中進(jìn)行聚類。非線性映射增加了數(shù)據(jù)點(diǎn)線性可分的概率，從而在經(jīng)典的聚類算法失效的情況下，通過(guò)引入核函數(shù)可以達(dá)到更為準(zhǔn)確的聚類結(jié)果。

5.3 特征類型

kmeans是面向數(shù)值型的特征，對(duì)于類別特征需要進(jìn)行onehot或其他編碼方法。此外還有 K-Modes 、K-Prototypes 算法可以用于混合類型數(shù)據(jù)的聚類，對(duì)于數(shù)值特征簇類中心我們?nèi)〉檬歉魈卣骶?，而類別型特征中心取得是眾數(shù)，計(jì)算距離采用海明距離，一致為0否則為1。

5.4 特征的權(quán)重

聚類是基于特征間距離計(jì)算，計(jì)算距離時(shí)，需要關(guān)注到特征量綱差異問(wèn)題，量綱越大意味這個(gè)特征權(quán)重越大。假設(shè)各樣本有年齡、工資兩個(gè)特征變量，如計(jì)算歐氏距離的時(shí)候，(年齡1-年齡2)2 的值要遠(yuǎn)小于(工資1-工資2)2 ，這意味著在不使用特征縮放的情況下，距離會(huì)被工資變量（大的數(shù)值）主導(dǎo)。因此，我們需要使用特征縮放來(lái)將全部的數(shù)值統(tǒng)一到一個(gè)量級(jí)上來(lái)解決此問(wèn)題。通常的解決方法可以對(duì)數(shù)據(jù)進(jìn)行“標(biāo)準(zhǔn)化”或“歸一化”，對(duì)所有數(shù)值特征統(tǒng)一到標(biāo)準(zhǔn)的范圍如0~1。

歸一化后的特征是統(tǒng)一權(quán)重，有時(shí)我們需要針對(duì)不同特征賦予更大的權(quán)重。假設(shè)我們希望feature1的權(quán)重為1，feature2的權(quán)重為2，則進(jìn)行0～1歸一化之后，在進(jìn)行類似歐幾里得距離（未開(kāi)根號(hào)）計(jì)算的時(shí)候，我們將feature2的值乘根號(hào)2就可以了，這樣feature2對(duì)應(yīng)的上式的計(jì)算結(jié)果會(huì)增大2倍，從而簡(jiǎn)單快速的實(shí)現(xiàn)權(quán)重的賦權(quán)。如果使用的是曼哈頓距離，特征直接乘以2 權(quán)重也就是2 。

如果類別特征進(jìn)行embedding之后的特征加權(quán)，比如embedding為256維，則我們對(duì)embedding的結(jié)果進(jìn)行0～1歸一化之后，每個(gè)embedding維度都乘以 根號(hào)1/256，從而將這個(gè)類別全部的距離計(jì)算貢獻(xiàn)規(guī)約為1，避免embedding size太大使得kmeans的聚類結(jié)果非常依賴于embedding這個(gè)本質(zhì)上是單一類別維度的特征。

5.5 特征的選擇

kmeans本質(zhì)上只是根據(jù)樣本特征間的距離（樣本分布）確定所屬的簇類。而不同特征的情況，就會(huì)明顯影響聚類的結(jié)果。當(dāng)使用沒(méi)有代表性的特征時(shí)，結(jié)果可能就和預(yù)期大相徑庭！比如，想對(duì)銀行客戶質(zhì)量進(jìn)行聚類分級(jí)：交易次數(shù)、存款額度就是重要的特征，而如客戶性別、年齡情況可能就是噪音，使用了性別、年齡特征得到的是性別、年齡相仿的客戶！

對(duì)于無(wú)監(jiān)督聚類的特征選擇：

• 一方面可以結(jié)合業(yè)務(wù)含義，選擇貼近業(yè)務(wù)場(chǎng)景的特征。

• 另一方面，可以結(jié)合缺失率、相似度、PCA等常用的特征選擇（降維）方法可以去除噪音、減少計(jì)算量以及避免維度爆炸。再者，如果任務(wù)有標(biāo)簽信息，結(jié)合特征對(duì)標(biāo)簽的特征重要性也是種方法（如xgboost的特征重要性，特征的IV值。）

• 最后，也可以通過(guò)神經(jīng)網(wǎng)絡(luò)的特征表示（也就深度聚類的思想。后面在做專題介紹），如可以使用word2vec，將高維的詞向量空間以低維的分布式向量表示。

參考文獻(xiàn):?

1、https://www.bilibili.com/video/BV1H3411t7Vk?spm_id_from=333.999.0.0?

2、https://zhuanlan.zhihu.com/p/407343831?

3、https://zhuanlan.zhihu.com/p/78798251