董芷欣

(格拉斯哥大學(xué), 計(jì)算機(jī)學(xué)院, 格拉斯哥 G128QQ, 英國)

0 引言

機(jī)器學(xué)習(xí)算法為大數(shù)據(jù)處理在學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛使用給予了強(qiáng)大的推動(dòng)力[1]。在自然語言處理和計(jì)算機(jī)視覺領(lǐng)域,無監(jiān)督學(xué)習(xí)算法應(yīng)用十分廣泛,而無監(jiān)督學(xué)習(xí)中適用范圍最廣的學(xué)習(xí)任務(wù)是聚類。聚類算法的過程旨在實(shí)現(xiàn)“類內(nèi)的相似性和類間的排他性”的目標(biāo)[2-4]。“簇”的劃分是聚類算法實(shí)現(xiàn)的核心問題,而聚類簇個(gè)數(shù)的確定是“簇”的劃分的必要條件之一[5-6]。本文根據(jù)不同聚類算法的實(shí)現(xiàn)過程,將聚類簇個(gè)數(shù)的劃分方式歸納為顯式指定和超參數(shù)推斷2種方法。前者的應(yīng)用算法為k-means和高斯混合聚類;后者則由層次聚類算法和Louvain算法實(shí)現(xiàn)。研究聚類簇個(gè)數(shù)的劃分方式有助于編程者對(duì)不同聚類算法的實(shí)現(xiàn),如有效性指標(biāo)的選擇、模型參數(shù)的調(diào)整、聚類算法的優(yōu)化等。為更好地論述和比較2種劃分方式的實(shí)現(xiàn)過程,本文選取數(shù)字切片數(shù)據(jù)進(jìn)行案例研究,代碼使用Jupyter notebook實(shí)現(xiàn)。對(duì)于不同聚類算法的結(jié)果計(jì)算Silhouette score判斷不同模型的擬合優(yōu)度、V-measure判斷聚類結(jié)果與原類別之間的契合度。

1 聚類數(shù)確定方法

1.1 顯式指定法

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

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

1.2 超參數(shù)推斷法

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

2 聚類有效性評(píng)估

由不同的數(shù)據(jù)結(jié)構(gòu)決定的聚類方法并不會(huì)適用于各種數(shù)據(jù)模型,因此對(duì)聚類結(jié)果的有效性評(píng)估是非常重要的[7]。本文選取輪廓系數(shù)和V-measure作為衡量指標(biāo)對(duì)聚類算法進(jìn)行評(píng)估。

2.1 輪廓系數(shù)(silhouette score)

聚類結(jié)果的評(píng)價(jià)可轉(zhuǎn)化為對(duì)于簇內(nèi)和簇間相似度的衡量。簇的凝聚性(cohesion)度量簇內(nèi)樣本密切程度,而分離性(separation)度量簇間相異程度[8]。較小的簇內(nèi)凝聚度和較大的簇間分離度可以使聚類結(jié)果更加理想化。輪廓系數(shù)便是類的密集與分散程度的評(píng)價(jià)指標(biāo)。由樣本個(gè)體的輪廓系數(shù)可推導(dǎo)出數(shù)據(jù)集某次聚類的輪廓系數(shù)sk:

(1)

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

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

2.2 V-measure

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

3 案例研究

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

圖1 降維后的數(shù)據(jù)集的結(jié)構(gòu)分布圖

表1 組織圖像種類及對(duì)應(yīng)樣本數(shù)

3.1 運(yùn)算過程

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

圖2 軟件流程圖

3.2 顯式指定簇個(gè)數(shù)

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

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

圖3 肘部法則確定k值

表2 k-means模型聚類結(jié)果

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

表3 高斯混合模型聚類結(jié)果

3.3 超參數(shù)推斷簇個(gè)數(shù)

Louvain算法和層次聚類法可以通過對(duì)超參數(shù)的設(shè)置實(shí)現(xiàn)聚類。本文分別對(duì)Louvain算法的解析度參數(shù)(決定社區(qū)規(guī)模)以及AgglomerativeClustering算法的距離閾值參數(shù)進(jìn)行調(diào)參。通過對(duì)參數(shù)范圍內(nèi)不同取值所得輪廓系數(shù)及V-measure數(shù)值比較,綜合2種評(píng)估指標(biāo)調(diào)整參數(shù)。

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

圖4 Louvain算法解析度曲線

表4 Louvain模型聚類結(jié)果

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

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

圖6 AHC linkage參數(shù)比較曲線圖

表5 層次聚類模型聚類結(jié)果

3.4 結(jié)果比較分析

通過比較4類算法的分類結(jié)果(見表6)發(fā)現(xiàn),高斯混合模型和層級(jí)聚類模型對(duì)于silhouette score和V-measure的表現(xiàn)結(jié)果較好(均>0.4),而k-means算法和Louvain算法雖然在聚類效果上表現(xiàn)較好,但與原類別的相似程度相差較大。對(duì)于顯式指定法中簇個(gè)數(shù)的確定方法,網(wǎng)格搜索結(jié)果優(yōu)于肘部法則。

表6 分類結(jié)果比較

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

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

4 總結(jié)

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