基于Python聚類分析的聚類數確定方法對比

董芷欣

(格拉斯哥大學, 計算機學院, 格拉斯哥 G128QQ, 英國)

0 引言

機器學習算法為大數據處理在學術界和產業界的廣泛使用給予了強大的推動力[1]。在自然語言處理和計算機視覺領域,無監督學習算法應用十分廣泛,而無監督學習中適用范圍最廣的學習任務是聚類。聚類算法的過程旨在實現“類內的相似性和類間的排他性”的目標[2-4]?！按亍钡膭澐质蔷垲愃惴▽崿F的核心問題,而聚類簇個數的確定是“簇”的劃分的必要條件之一[5-6]。本文根據不同聚類算法的實現過程,將聚類簇個數的劃分方式歸納為顯式指定和超參數推斷2種方法。前者的應用算法為k-means和高斯混合聚類;后者則由層次聚類算法和Louvain算法實現。研究聚類簇個數的劃分方式有助于編程者對不同聚類算法的實現,如有效性指標的選擇、模型參數的調整、聚類算法的優化等。為更好地論述和比較2種劃分方式的實現過程,本文選取數字切片數據進行案例研究,代碼使用Jupyter notebook實現。對于不同聚類算法的結果計算Silhouette score判斷不同模型的擬合優度、V-measure判斷聚類結果與原類別之間的契合度。

1 聚類數確定方法

1.1 顯式指定法

k-means算法是最常用的聚類算法,算法隨機初始化k個聚類中心點,并計算數據中每個點到k個中心點的距離。將每個數據點與距離最近的中心點關聯并聚成一類,利用均值等方法更新該類的中心值并迭代計算直到得到滿意結果。高斯混合模型(GMM)也是一種常見的聚類算法,與K均值算法類似,同樣使用迭代計算。高斯混合模型假設每個簇的數據都是符合高斯分布的,當前數據呈現的分布就是各個簇的高斯分布疊加在一起的結果。這2種方法運算簡單、速度快,但聚類簇個數K值的確定對結果影響巨大。

在實現k-means和GMM聚類算法時,需要通過一些方法來確定聚類簇個數以便在進行聚類運算時顯式地指定簇個數。本文分別采用肘部運算法則和網格搜索法獲取類簇中心個數。肘部法則通過尋找損失值下降平穩的拐點來確定簇個數。以k-means為例,其以最小化樣本與類簇中心的平方誤差作為目標函數?；兂潭扰c簇內成員緊密程度呈負相關,畸變程度隨類別增加而降低,在達到臨界點后緩慢下降。臨界點作為聚類性能較好的點被選作為聚類算法實現時顯式指定的聚類個數。GMM聚類算法使用網格搜索法獲取類簇中心個數,網格搜索法在部分或全部訓練集上對多種參數組合進行交叉驗證,以得到每個參數組合的模型訓練效果,從而選出規定范圍內最優參數。

1.2 超參數推斷法

本文采用層次聚類算法和Louvain算法實現超參數推斷。層次聚類是一種常用的聚類算法,一般采用由下向上一層一層進行聚類。算法初始將樣本集中所有樣本點都作為一個獨立的類簇,然后依據某種準則(例如距離)合并這些初始的類簇,直到達到聚類數目或者達到事先設定條件。Louvain算法是一種基于圖形的社區檢測方法(community detection),每個數據點表示為1個節點,用一條邊表示2個數據點之間的相似性。算法首先將節點分配給不同的簇中,這些簇在社區內部具有緊密的聯系稱為模塊化,然后對簇進行重復測試直到模塊化不再變化。

2 聚類有效性評估

由不同的數據結構決定的聚類方法并不會適用于各種數據模型,因此對聚類結果的有效性評估是非常重要的[7]。本文選取輪廓系數和V-measure作為衡量指標對聚類算法進行評估。

2.1 輪廓系數(silhouette score)

聚類結果的評價可轉化為對于簇內和簇間相似度的衡量。簇的凝聚性(cohesion)度量簇內樣本密切程度,而分離性(separation)度量簇間相異程度[8]。較小的簇內凝聚度和較大的簇間分離度可以使聚類結果更加理想化。輪廓系數便是類的密集與分散程度的評價指標。由樣本個體的輪廓系數可推導出數據集某次聚類的輪廓系數sk:

(1)

其中,ai為樣本于其同簇中其他樣本的平均距離,bi為樣本與其他簇中所有樣本的平均距離的最小值,n為數據集中樣本個數,k為聚類數。

本文中使用輪廓系數可以直觀地比較出不同聚類算法對原數據集的聚類效果。

2.2 V-measure

除了使用輪廓系數對聚類效果進行內部評估外,本文還選擇了一種基于外部熵的評價方法V-measure對聚類性能進行外部評估。V-measure可以準確地結合和評估聚類的兩個理想方面,即同質性(homogeneity)和完整性(completeness)。同質性度量或完整性度量越大,2個類別劃分越接近。V-measure反映了聚類解決方法在將特定類別的所有數據點納入特定聚類中的成功程度,只對集群的質量進行評估[9]。本文使用該方法對比原類別與聚類所得的類別之間的相似程度。

3 案例研究

本文選用組織切片圖像數據集進行案例研究,此數據集包含5000張切片圖像(244×244×3),按組織種類可被分為9類:脂肪(ADI)、背景(BACK)、碎屑(DEB)、淋巴細胞(LYM)、黏液(MUC)、肌肉(MUS)、正常黏膜(NORM)、病間質(STR)和病上皮(TUM)。每種組織圖像的樣本數如表1所示。接著經過InceptionV3分類器的訓練,將原始數據轉換為5000組2048維向量,準確率為77.9%。最后采用UMAP降維方法繼續將維度降為100,得到5000組100維向量作為最終研究數據集。該數據集的結構分布如圖1所示。聚類算法包括K均值、GMM、層次聚類(AHC)和Louvain算法,通過計算silhouette score和V-measure評分來評估和比較效果。

圖1 降維后的數據集的結構分布圖

表1 組織圖像種類及對應樣本數

3.1 運算過程

依托于Jupyter notebook平臺,使用Python代碼編程實現基于2種聚類簇個數確定方法的4種聚類模型選擇。聚類算法編程的總體思路為在給定的聚類簇個數區間內選擇合適的效果評估方法得到最優簇個數值,使用機器學習庫中的算法包對數據集進行聚類得出最終每一類中的成員數,最后計算silhouette score和V-measure比較擬合優度和類別契合度。另外,實驗過程中對Scikit-learn庫中使用的算法包中除聚類簇個數外其他參數進行控制變量。軟件流程如圖2所示。

圖2 軟件流程圖

3.2 顯式指定簇個數

k-means算法和高斯混合模型都是在實現過程中需要顯式指定簇個數的聚類模型。 在使用Python的Scikit-learn機器學習庫中的算法模型進行聚類學習時,因所使用數據集的真實類別數為9,故在篩選k-means()的參數n_clusters和GaussianMixture()的參數n_components時,取值均從[1,10]范圍中選擇。

對k-means算法前期使用肘部法則篩選最優參數n_clusters,從圖3可以明顯地看出,變量k在4之后減小的幅度明顯變緩,因此選擇最優參數4作為本實驗中k-means模型的聚類簇個數,顯示指定參數n_clusters = 4。為固定構建的模型,設置隨機種子random_state=0, 其他參數均為默認值,結果如表2所示。

圖3 肘部法則確定k值

表2 k-means模型聚類結果

在使用高斯混合模型進行聚類時,前期使用網格搜索GridSearchCV()在[1, 10]范圍內得到GaussianMixture()中的參數n_components的最優值為6,因此確定6為本實驗中高斯混合模型的聚類簇個數。另外,在GaussianMixture()中設參數covariance_type=’shperical’,意味著每個分量有各自的簡單協方差矩陣; random_state=0, 其余參數均為默認值。高斯混合模型的聚類結果如表3所示。

表3 高斯混合模型聚類結果

3.3 超參數推斷簇個數

Louvain算法和層次聚類法可以通過對超參數的設置實現聚類。本文分別對Louvain算法的解析度參數(決定社區規模)以及AgglomerativeClustering算法的距離閾值參數進行調參。通過對參數范圍內不同取值所得輪廓系數及V-measure數值比較,綜合2種評估指標調整參數。

Scikit-learn中,Louvain()的解析度參數resolution可以靈活地控制社區劃分數量及規模[10]。 由圖4可知, resolution取值為0.9時,silhouette score最高且V-measure相對較高。因此,本文選擇0.9作為Louvain算法的解析度,設置超參數resolution =0.9,其余參數均為默認值,聚類結果如表4所示。

圖4 Louvain算法解析度曲線

表4 Louvain模型聚類結果

層次聚類算法中,在范圍1～10內對超參數distance_threshold調整,得到的輪廓系數和V-measure圖像如圖5所示,綜合比較后選取4為參數值。用Scikit-learn庫中AgglomerativeClustering()做最優層次聚類模型預測,超參數distance_threshold=4。 另外,通過比較不同linkage所得的silhouette score,如圖6所示,選擇average作為linkage的值,其余參數均為默認值。表5列出了層次聚類結果。

圖5 層次聚類算法silhouette score和V-measure曲線

圖6 AHC linkage參數比較曲線圖

表5 層次聚類模型聚類結果

3.4 結果比較分析

通過比較4類算法的分類結果(見表6)發現,高斯混合模型和層級聚類模型對于silhouette score和V-measure的表現結果較好(均>0.4),而k-means算法和Louvain算法雖然在聚類效果上表現較好,但與原類別的相似程度相差較大。對于顯式指定法中簇個數的確定方法,網格搜索結果優于肘部法則。

表6 分類結果比較

由圖7可知,4類算法均可對BACK類實現較完整地分離。另外,ADI類在k-means、GMM和AHC算法中可以被較完整分離。分離出聚類數最多的算法是GMM,可將ADI、LYM和BACK 3類分離。從數據角度分析,LYM和DEB類別易混淆,在4類算法中聚類效果較差的類別是TUM、STR、Norm和MUC。

圖7 4種算法的組織分類柱狀圖

4 總結

在確定聚類簇個數的方法中,肘部法則對于拐點的確定較為模糊,對于最終簇個數的確定可能存在爭議。由聚類結果柱狀圖可分析,原始數據可能存在類別不平衡問題,未來可使用downsampling或upsampling方法優化原始數據。在超參數決定簇個數的代碼實現中,本文只針對Louvain算法中的resolution參數以及AHC算法中的distance_threshold和linkage參數進行調整,其他參數均使用默認值或統一值,未來可從其他參數上做出調整以提高算法效率和結果表現。另外,k-means和Louvain算法的劃分類別與原始類別相似度相差較大,對于這2類算法的同質性和完整性度量應加以研究和優化。