一虫埂、一句話介紹

聚類通常是指，對于未標記訓練樣本圃验，根據樣本的內在相似性掉伏，將樣本劃分為若干個不相交子集的學習算法。

二澳窑、最簡單的例子

一個不是很恰當的例子斧散。剛上大學的時候，大家來自天南海北摊聋，是一個個單獨的個體鸡捐。過一段時間以后，大家或是因為相同的興趣愛好麻裁，或是因為喜歡打同一個游戲箍镜，或是因為同一個宿舍，總之因為某種相似性煎源，會形成不同的團團伙伙色迂。

三、K均值算法(K-Means)

3.1手销、K均值算法的意義

K均值算法是最簡單的聚類算法歇僧，也是最能簡明地說明聚類思想和聚類過程的聚類算法，凡是講聚類的教材(大多)都會先講K均值聚類锋拖。

K均值聚類算法也包含了樸素的期望最大化(Expectation Maximization)思想诈悍，在吳軍博士的著作《數學之美》[1]中，吳軍博士就是用K均值算法舉例期望最大化算法的兽埃。

3.2侥钳、算法描述

3.3、K均值算法的缺點

A讲仰、是局部最優(yōu)解慕趴，而不是全局最優(yōu)解。這與初始聚類簇中心有關鄙陡，也就是說冕房，聚類結果對初始聚類簇中心敏感。

B趁矾、對樣本分布敏感：對球形分布的數據聚類效果好耙册，對非球形樣本聚類效果不好，尤其是帶狀毫捣、環(huán)狀樣本聚類效果很差详拙；對離群點敏感。

C蔓同、其他缺點饶辙。

四、聚類算法的種類[2]

根據聚類算法實現大的基本原理斑粱，聚類算法主要有以下幾種：

4.1弃揽、順序算法(Sequential Algorithm)

基本順序算法方案(Basic Sequential Algorithm Scheme,BSAS)最能說明順序算法的算法思想：給定相似性度量閾值和最大聚類數，按照順序給樣本分類则北，根據樣本到已有聚類的距離矿微，滿足一定條件將其分配到已有聚類中，不滿足條件則劃分到新生成的聚類中尚揣。

4.2涌矢、層次聚類算法(Hierarchical Clustering Algorithm)

又分為合并算法和分裂算法。合并算法在每一步減少聚類數量快骗，聚類結果來自于前一步的兩個聚類的合并娜庇；分裂算法原理正好相反。

4.3方篮、基于代價函數最優(yōu)的聚類算法(Clustering Algorithm based on Cost Function Optimization)

使用代價函數來量化判斷思灌，當代價函數達到局部最優(yōu)時，算法結束恭取。K均值算法如果采用歐式距離作為相似性度量的話泰偿，其代價函數是平方誤差和

代價函數J不是凸函數。

高斯混合聚類(Mixture-of-Gaussian)是另一個比較有名的此類算法蜈垮。

4.4耗跛、基于密度的算法(Density-based Algorithm)

該類算法把聚類視為空間中數據較為密集的區(qū)域。DBSCAN就是一種著名的密度聚類算法攒发。

值得一提的是调塌，2014年6月Alex Rodriguez, Alessandro Laio在《Science》期刊上發(fā)表了一篇論文，"Clustering by fast search and find of density peaks"惠猿，論文中提出了一種非常巧妙的聚類算法羔砾。

4.5、其他算法

五、聚類的幾個問題

5.1姜凄、相似性度量

無論哪種算法政溃，都離不開相似性度量，只有相似性度量可以說明樣本之間的相似性态秧。相同的樣本集董虱，選擇相同的算法，選擇不同的相似性度量申鱼，可能聚類的結果就會不同愤诱。

我在另一篇筆記中整理了一下常用的相似性度量，《相似性度量》捐友。

5.2淫半、聚類準則

如4.3所述，基于代價函數最優(yōu)的聚類算法都需要一個聚類準則匣砖，K均值算法的聚類準則是最小平方誤差和撮慨；高斯混合聚類聚類準則是最大化樣本出現的概率。

5.3脆粥、性能度量

聚類性能度量也稱為聚類有效性指標(Vadility Index),通過某種度量來評估聚類結果的好壞砌溺。[3]

5.4、超參數

超參數变隔，我的理解就是需要先驗地假設一些參數值规伐，這些參數是聚類過程的基礎參數。

很多聚類算法需要有超參數匣缘。K均值算法需要預先設定聚類簇數k猖闪；DBSCAN需要預先設定鄰域參數和簇內最少樣本，等等肌厨。

超參數的確定有很多方法培慌，比如K均值算法聚類簇數k可通過稱作“肘部法則[4]”的方法確定

六、參考

[1]柑爸、《數學之美》吵护，吳軍著

[2]、《模式識別(第四版)》表鳍，Sergios Theodoridis等著馅而，李晶皎等譯

[3]、《模式識別》譬圣，周志華著

[4]瓮恭、《斯坦福大學2014機器學習教程個人筆記完整版v4.21》,黃廣海整理