學習筆記【機器學習重點與實戰】——9 聚類演算法原理

1 K-Means

K-Means演算法,也被稱為K-均值演算法或K-平均,是一種廣泛使用的聚類演算法,或者為其它聚類演算法的基礎。

K-Means是發現給定資料集的 k 個簇的演算法。簇個數 k 是使用者給定的,每一個簇通過其質心(centroid), 即簇中所有點的中心來描述。

K-Means演算法過程虛擬碼表示如下:

建立k個點作為起始質心(經常是隨機選擇)
當任意一個點的簇分配結果發生改變時
對資料集中的每個資料點
對每個質心
計算質心與資料點之間的距離
將資料點分配到距其最近的簇
對每一個簇,計算簇中所有點的均值並將均值作為質心

演算法停止條件通常可設定為:最大執行輪數,最小調整幅度閾值。

其計算過程可表達如下圖:

這裡寫圖片描述

起始質心是隨機選取的,使得K-均值對初值敏感。

優點:

  1. 是解決聚類問題的一種經典演算法,簡單、快速
  2. 對處理大資料集,演算法保持可伸縮性和高效率
  3. 當簇近似為高斯分佈肘,它的效果較好

缺點:

  1. 在簇的平均值可彼定義的情況下才能使用,可能不適用於某些應用
  2. 必須事先給出k(要生成的簇的目),而且對初值敏感,對於不同的初值,可能會導致不同結果
  3. 不適合於發現非凸形狀的者大小差別很夫的簇
  4. 對躁聲和孤立點資料敫感

sklearn中程式碼實現如下:

from sklearn.cluster import KMeans
model = KMeans(n_clusters=4, init='random')

1.1 K-means

K-means演算法最開始隨機選取資料集中K個點作為聚類中心,使得K-均值對初值敏感。而K-means 按照如下的思想選取K個聚類中心:假設已經選取了n個初始聚類中心(0

from sklearn.cluster import KMeans
model = KMeans(n_clusters=4, init='k-means  ')

1.2 二分K-Means

為克服K-Means演算法收斂於區域性最小值的問題,有人提出了另一個稱為二分K – 均 值(bisecting K-means)的演算法。該演算法首先將所有點作為一個簇,然後將該簇一分為二。 之後選擇其中一個簇繼續進行劃分,選擇哪一個簇進行劃分取決於對其劃分時候可以最大程度降低 SSE(平方和誤差)的值。 上述基於 SSE 的劃分過程不斷重複,直到得到使用者指定的簇數目為止。

二分K-Means演算法過程虛擬碼表示如下:

將所有點看成一個簇
當簇數目小於 k 時
對於每一個簇
計算總誤差
在給定的簇上面進行 KMeans 聚類(k=2)
計算將該簇一分為二之後的總誤差
選擇使得誤差最小的那個簇進行劃分操作

另一種做法是選擇 SSE 最大的簇進行劃分,直到簇數目達到使用者指定的數目為止。

2 層次聚類

層次聚類(hierarchical clustering)試圖在不同層次對資料集進行劃分,從而形成樹形的聚類結構。資料集的劃分可採用”自底向上”的聚合策略,也可採用 “自頂向下” 的分拆策略。

2.1 “自底向上”的聚合策略

AGNES(AGglomerativeNESting)演算法即為”自底向上”的聚合策略。

最初將每個物件作為一個簇,然後這些簇根據某些準則被一步步地合併。兩個簇間的距離由這兩個不同中距離最
近的資料點對的相似度來確定;聚合的合併過程反覆進行直到所有的物件最終滿足數目。

聚類簇之間的距離可通過下面三種方式計算:

  1. 最小距離(”單連結”,single-linkage)

    兩個集合中最近的兩個樣本的距離;容易形成鏈狀結構。

dmin(Ci,Cj)=minx→i∈Ci,x→j∈Cjdistance(x→i,x→j)” role=”presentation” style=”text-align: center; position: relative;”>dmin(Ci,Cj)=minx⃗ i∈Ci,x⃗ j∈Cjdistance(x⃗ i,x⃗ j)dmin(Ci,Cj)=minx→i∈Ci,x→j∈Cjdistance(x→i,x→j)

d_{min}(C_i,C_j)=\min_{\vec{x}_i\in C_i,\vec{x}_j\in C_j}distance(\vec{x}_i,\vec{x}_j)

  1. 最大距離(”全連結”,complete-linkage)

    兩個集合中最遠的兩個樣本的距離(complete);若存在異常值則不穩定。

    dmax(Ci,Cj)=maxx→i∈Ci,x→j∈Cjdistance(x→i,x→j)” role=”presentation” style=”text-align: center; position: relative;”>dmax(Ci,Cj)=maxx⃗ i∈Ci,x⃗ j∈Cjdistance(x⃗ i,x⃗ j)dmax(Ci,Cj)=maxx→i∈Ci,x→j∈Cjdistance(x→i,x→j)

    d_{max}(C_i,C_j)=\max_{\vec{x}_i\in C_i,\vec{x}_j\in C_j}distance(\vec{x}_i,\vec{x}_j)

  2. 平均距離(”均連結”,average-linkage)

    A. 兩個集合中樣本間兩兩距離的平均值(average)

    davg(Ci,Cj)=1|Ci||Cj|∑x→i∈Ci∑x→j∈Cjdistance(x→i,x→j)” role=”presentation” style=”text-align: center; position: relative;”>davg(Ci,Cj)=1|Ci||Cj|∑x⃗ i∈Ci∑x⃗ j∈Cjdistance(x⃗ i,x⃗ j)davg(Ci,Cj)=1|Ci||Cj|∑x→i∈Ci∑x→j∈Cjdistance(x→i,x→j)

    d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum_{\vec{x}_i\in C_i}\sum_{\vec{x}_j\in C_j}distance(\vec{x}_i,\vec{x}_j)

    B. 兩個集合中樣本間兩兩距離的平方和(ward)

    dward(Ci,Cj)=∑x→i∈Ci∑x→j∈Cjdistance(x→i,x→j)2″ role=”presentation” style=”text-align: center; position: relative;”>dward(Ci,Cj)=∑x⃗ i∈Ci∑x⃗ j∈Cjdistance(x⃗ i,x⃗ j)2dward(Ci,Cj)=∑x→i∈Ci∑x→j∈Cjdistance(x→i,x→j)2

    d_{ward}(C_i,C_j)=\sum_{\vec{x}_i\in C_i}\sum_{\vec{x}_j\in C_j}distance(\vec{x}_i,\vec{x}_j)^2

sklearn中程式碼實現如下:

from sklearn.cluster import AgglomerativeClustering
AgglomerativeClustering(n_clusters=4, affinity='euclidean', linkage='ward')

affinity:距離計算方式,可取”euclidean”, “l1”, “l2”,”manhattan”, “cosine”, 或者 ‘precomputed’。

linkage:聚類簇之間的距離計算方式,可取”ward”, “complete”, “average”。

2.2 “自頂向下” 的分拆策略

DIANA(DlvisiveANAlysis)演算法即為”自頂向下” 的分拆策略。

是”自底向上”的聚合策略過程的反過程,屬於分裂的層次聚類,首先將所有的物件初始化到一個簇中,然後根據一些原則(比如最大的歐式距離),將簇分類。直到到達使用者指定的數目或者兩個簇之間的距離超過了某個閾值。

3 密度聚類

密度聚類亦稱”基於密度的聚類” (density-based clustering) ,此類演算法假設聚類結構能通過樣本分佈的緊密程度確定。通常情形下,密度聚類演算法從樣本密度的角度來考察樣本之間的可連線性,並基於可連線樣本不斷擴充套件聚類簇以獲得最終的聚類結果。

密度聚類演算法能克服基於距離的演算法只能發現“類圓形”(凸)的聚類的缺點,可發現任意形狀的聚類,且對噪聲資料不敏感。但計算密度單元的計算複雜度大,需要建立空間索引來降低計算量。

DBSCAN(Density-Based Spatial Clustering Of Applications with Noise)是一個比較有代表性的基於密度的聚類演算法。將簇定義為密度相連的點的最大集合,能夠把具有足夠高密度的區域劃分為簇,並可在有“噪聲”的資料中發現任意形狀的聚類。自適應劃分簇,不需要給定簇的大小。

基於一組”鄰域” (neighborhood) 引數 (ε,MinPts) 來刻畫樣本分佈的緊密程度。

相關概念包括:ε-鄰域,核心物件 (core object),密度直達 (directly density-reachable) ,密度可達(density-reachable) ,密度相連(density-connected) 。直觀顯示如下圖:

這裡寫圖片描述

圖中 (MinPts = 3):虛線顯示出 ε-鄰域,x1″ role=”presentation” style=”position: relative;”>x1x1x_1 是核心物件,x2″ role=”presentation” style=”position: relative;”>x2x2x_2 由 x1″ role=”presentation” style=”position: relative;”>x1x1x_1 密度直達,x3″ role=”presentation” style=”position: relative;”>x3x3x_3 由 x1″ role=”presentation” style=”position: relative;”>x1x1x_1 密度可達,x3″ role=”presentation” style=”position: relative;”>x3x3x_3 與 x4″ role=”presentation” style=”position: relative;”>x4x4x_4 密度相連。

DBSCAN演算法流程如下:

  • 如果一個點p的 ε-鄰域包含多於m個物件,則建立一個p作為核心物件的新簇;
  • 尋找併合並核心物件直接密度可達的物件;
  • 沒有新點可以更新簇時,演算法結束。

由上述演算法可知:

  • 每個簇至少包含一個核心物件;
  • 非核心物件可以是簇的一部分,構成了簇的邊緣(edge);
  • 包含過少物件的簇彼認為是噪聲。

sklearn中程式碼實現如下:

from sklearn.cluster import DBSCAN
DBSCAN(eps=eps, min_samples=min_samples) # 引數分別為 ε ,MinPts

4 譜聚類

譜聚類是一種基於圖的聚類方法,通過對樣本資料的拉普拉斯矩陣特徵向量進行聚類,從而達到對樣本資料聚類的目的。

方陣作為線性運算元,它的所有特徵值的全體統稱方陣的譜。方陣的譜半徑為最大的特徵值,矩陣A的譜半徑為(ATA” role=”presentation” style=”position: relative;”>ATAATAA^TA)的最大特徵值。

譜聚類的流程如下:

  • 給定一組據x1,x2,…xn” role=”presentation” style=”position: relative;”>x1,x2,…xnx1,x2,…xnx_1,x_2,…x_n,記任意兩個點之間的相似度(“距離”的減函式)為 Sij=&lt;xi,xj&gt;” role=”presentation” style=”position: relative;”>Sij=<xi,xj>Sij=<xi,xj>S_{ij}=,形成相似度圖(similarity graph):G=(V,E)。如果 xi” role=”presentation” style=”position: relative;”>xixix_i 和 xj” role=”presentation” style=”position: relative;”>xjxjx_j 之間的相似度 Sij” role=”presentation” style=”position: relative;”>SijSijS_{ij} 大於一定的閾值,那麼,兩個點是連線的,權值記做 Sij” role=”presentation” style=”position: relative;”>SijSijS_{ij}。
  • 接下來,可以用相似度圖來解決樣本資料的聚類問題:找到圖的一個劃分,形成若干個組(Group),使得不同組之間有較低的權值,組內有較高的權值。

譜聚類演算法的拉普拉斯矩陣包括:

  1. 未正則拉普拉斯矩陣:L = D-W
  2. 隨機遊走拉普拉斯矩陣:Lrw=D−1(D−W)” role=”presentation” style=”position: relative;”>Lrw=D−1(D−W)Lrw=D−1(D−W)L_{rw}=D^{-1}(D-W)
  3. 對稱拉普拉斯矩陣:Lsym=D−12(D−W)D−12″ role=”presentation” style=”position: relative;”>Lsym=D−12(D−W)D−12Lsym=D−12(D−W)D−12L_{sym}=D^{-\frac{1}{2}}(D-W)D^{-\frac{1}{2}}

sklearn中程式碼實現如下:

from sklearn.cluster import SpectralClustering
SpectralClustering(n_clusters=4, affinity='precomputed') 

5 標籤傳遞演算法

對於部分樣本的標記給定,而大多樣本的標記未知的情形,是半監督學習問題。

標籤傳遞演算法(LabelPropagation Algorithm,LPA),將標記樣本的標記通過一定的概率傳遞給未標記樣本,直到最終收斂。

標籤傳遞過程如下圖所示,左上角圖為初始狀態,有顏色的代表有標記的樣本值,灰色代表沒有標記的樣本值。數字分別代表各自的迭代次數。

這裡寫圖片描述

6 參考

  1. 機器學習升級版視訊 – 鄒博
  2. 《機器學習 – 周志華》第9章 聚類
  3. 《機器學習實戰》第10章 利用K-均值聚類演算法對未標註資料分組

===========文件資訊============
學習筆記由博主整理編輯,供非商用學習交流用
如本文涉及侵權,請隨時留言博主,必妥善處置
版權宣告:非商用自由轉載-保持署名-註明出處
署名(BY) :dkjkls(dkj卡洛斯)
文章出處:http://blog.csdn.net/dkjkls