聚類

在無監(jiān)督學習中，目標是通過對無標記訓練樣本的學習來揭示數(shù)據(jù)的內(nèi)在性質(zhì)及規(guī)律。在這類任務中，常用的算法是聚類(cluster)算法。 聚類算法試圖將樣本劃分為若干個通常是不相交的子集，每個子集表明一個簇，也叫類別，通過這樣的操作，可以將無規(guī)律的樣本劃分為一堆堆的樣本子集合。簇所對應的概念語義及個數(shù)需要由使用者把握和命名。

性能度量

聚類要求，簇內(nèi)相似，簇間盡可能不同。直白一點的意思是，我們希望物以類聚，即簇內(nèi)的樣本之間相似度要高，而簇間的樣本相似度要低。如何度量相似度？一般而言是使用距離來度量。最常用的是使用閔可夫斯基距離：?

?當P=2時候，閔可夫斯基距離變?yōu)闅W氏距離：?

?當p=1時候，閔可夫斯基距離變?yōu)槁D距離：?

?當p=0時候，閔可夫斯基距離變?yōu)榍斜妊┓蚓嚯x：?

• 樣本之間距離越大，說明樣本之間相似度越低

• 樣本之間距離越小，說明樣本之間相似度越高

聚類算法

k-means聚類?算法大致流程如下：

• 第一步，設定k值，表明要劃分為k簇，這也是算法唯一的一個超參數(shù)；

• 第二步，從數(shù)據(jù)集中隨機選擇k個樣本出來作為初始化的簇中心，這里注意，初始化的好壞會對最終結果有影響！

• 第三步，計算每個樣本與這些簇中心的距離，樣本離哪個簇中心最近，就將其劃分為哪一簇；

• 第四步，根據(jù)每一簇的樣本計算均值，并更新該簇的簇中心。

• 重復上述第三步和第四步，直到達到簇中心不再變化表明算法穩(wěn)定。

學習向量量化（LVQ）?學習向量量化試圖找到一組原型向量來刻畫聚類結構，但是LVQ假設樣本帶有類別標記，學習過程中利用樣本的監(jiān)督信息來輔助聚類。 算法大致流程：

• 第一步： 初始化一組原型向量，并且對每個原型向量都預設有類別標記；

• 第二步：從樣本中隨機選擇樣本，計算樣本與原型向量之間的距離，找出與之最相近的原型向量；

• 第三步：如果上述步驟的原型向量的預設標簽與假設的標簽一致的話，對原型向量進行更新，讓更新后的原型向量更接近樣本；如果上述步驟的原型向量的預設標簽與假設的標簽不一致的話，對原型向量進行更新，讓更新后的原型向量更遠離樣本；

• 重復進行第二步和第三步，直到滿足停止條件。

高斯混合聚類?高斯混合聚類采用概率模型來表達聚類原型，簇劃分的原則是原型對應的后驗概率。 使用EM算法來求解最大后驗概率。

密度聚類?密度聚類，即基于密度的聚類。假設樣本的聚類結構可以通過樣本分布的緊密程度來表達。密度聚類算法考察樣本之間的可連接性，并基于可連接擴展聚類簇以獲得最終的聚類結果。 DBSCAN（density-based-spatial clustering of applications with noise） 這里有些概率要理解：

• 鄰域：畫一個圈包含的樣本；

• 核心對象：樣本多大的圈能至少包含MinPts個樣本，這樣的樣本叫做核心對象；

• 密度直達：樣本A在樣本B的鄰域中，則B是核心對象，A由B密度直達；

• 密度可達：可以傳遞的那種； 算法思想是由密度可達關系導出最大的密度相連樣本集合作為一個簇。 算法大致流程：

• 第一步：先根據(jù)領域找到所有的核心對象；

• 第二步：以任一核心對象為出發(fā)點，找出與其密度可達的樣本生成聚類簇，直到所有核心對象都被訪問過；

• 第三步：然后從數(shù)據(jù)集中將這些圈好的樣本去掉，開始下一輪；

• 重復進行第二步和第三步，直到所有的核心對象都被訪問過。

層次聚類?層次聚類試圖在不同層次上對數(shù)據(jù)進行劃分，從而形成樹形的聚類結構，可以采取自上而下或者自下而上的分拆策略。 AGNES（Agglomerative Nesting）是采用自下而上的層次聚類算法。 算法思想是將數(shù)據(jù)集中每個樣本看作是一個初始聚類簇，然后在算法運行的每一步中找到距離最近的兩個聚類簇進行合并，不斷重復，直到達到設定的簇數(shù)。 最小距離：由兩個簇最近樣本決定 最大距離：由兩個簇最遠樣本決定 平均距離：由兩個簇的所有樣本決定 算法大致流程：

• 第一步：設置當前的簇數(shù)；

• 第二步：當簇數(shù)大于想要的簇數(shù)時候，找出距離最近的兩個簇數(shù)，合并兩個簇數(shù)為一個簇數(shù)，并對合并得到的聚類簇的距離進行更新

• 第三步：不斷重復上述過程，直到達到想要的簇數(shù)；

參考文獻

• 周志華 機器學習