層次聚類的方法及應(yīng)用

姜子林

很多機(jī)器學(xué)習(xí)算法為各行各業(yè)注入新鮮血液，也使數(shù)據(jù)挖掘有了更多應(yīng)用場(chǎng)景。由于我們生活中的大量數(shù)據(jù)是沒有標(biāo)注的，故很多時(shí)候我們需要聚類的算法，即根據(jù)數(shù)據(jù)本身的性質(zhì)自動(dòng)分類。而本文中，我們分析了聚合式層次聚類的方法步驟，并探究了其在實(shí)際問題中的應(yīng)用。

【關(guān)鍵詞】人工智能 機(jī)器學(xué)習(xí) 層次聚類 可視化

1 引言

在近幾十年內(nèi)，人工智能和機(jī)器學(xué)習(xí)發(fā)展迅速并且在各個(gè)領(lǐng)域都有著重要的應(yīng)用，如數(shù)據(jù)挖掘，計(jì)算機(jī)視覺，自然語(yǔ)言處理等。而在大數(shù)據(jù)時(shí)代，面對(duì)海量數(shù)據(jù)，往往我們得到的數(shù)據(jù)中先驗(yàn)知識(shí)較少，需要從數(shù)據(jù)本身的分布結(jié)構(gòu)特性去自動(dòng)分析數(shù)據(jù)的屬性和知識(shí)，這就是無(wú)監(jiān)督學(xué)習(xí)。在無(wú)監(jiān)督學(xué)習(xí)中，本文詳細(xì)介紹了層次聚類的方法，包括計(jì)算點(diǎn)之間的距離和類之間的距離，逐步聚合，直到最后為每一類貼標(biāo)簽。并且為了對(duì)層次聚類有更深刻的理解我們對(duì)層次聚類做了實(shí)驗(yàn)，應(yīng)用到一個(gè)鳶尾花花瓣的長(zhǎng)度和寬度數(shù)據(jù)上，從可視化的結(jié)果中發(fā)現(xiàn)層次聚類確實(shí)把相距較遠(yuǎn)的簇成功分開了，成功的識(shí)別出了數(shù)據(jù)中的分布結(jié)構(gòu)。

2 方法

主流的聚類方法包括k-means，層次聚類，mean-shift等。這些算法的共同特點(diǎn)都是以等長(zhǎng)度向量（分布在同一空間中）的集合作為算法的輸入，以每一個(gè)向量所屬類別標(biāo)簽作為輸出，而類別劃分的原則都是越臨近越容易被分到一類，但具體到效果因?yàn)榉椒ú煌煌Ｆ渲?，層次聚類的基本思想概括起?lái)就是初始把每個(gè)點(diǎn)單獨(dú)看做一個(gè)類別，然后依次合并兩個(gè)最近的類別，直到需要合并的類別距離大于一個(gè)閾值為止。

在我們用計(jì)算機(jī)實(shí)現(xiàn)層次聚類的過(guò)程中，需要以下步驟：

（1）計(jì)算每?jī)蓚€(gè)點(diǎn)之間的距離，并且存儲(chǔ)在一個(gè)向量里。這里我們用歐式距離作為距離度量。

（2）初始每個(gè)點(diǎn)作為一類，逐步合并最近的兩類，而兩類之間距離的算法是：一類和另一類各挑出一個(gè)點(diǎn)，算出距離，考慮所有情況，再去計(jì)算平均值。

（3）畫出反映聚類合并過(guò)程的樹狀圖。

（4）觀察樹狀圖，確定分割閾值，并且為每一個(gè)點(diǎn)打上聚類得到的類別標(biāo)簽。閾值是指最大值，而分割閾值是指設(shè)立的一個(gè)值，在該值以下所擁有的最少類的數(shù)量。

3 實(shí)驗(yàn)

這一節(jié)我們主要介紹在實(shí)驗(yàn)中我們使用到的數(shù)據(jù)以及具體處理過(guò)程，包括我們使用到的庫(kù)和函數(shù)。我們使用python中sklearn庫(kù)里的iris（鳶尾花）數(shù)據(jù)集，我們實(shí)驗(yàn)中采用其中共150個(gè)鳶尾花花瓣的長(zhǎng)度和寬度作為樣本進(jìn)行聚類實(shí)驗(yàn)。分別引入matplotlib.pyplot（用于畫圖的一個(gè)庫(kù)）、sklearn中的一個(gè)子庫(kù)datasets（一個(gè)數(shù)據(jù)庫(kù)）、以及pylab和scipy.cluster.hierarchy庫(kù)。從datasets庫(kù)中引入iris的屬性（萼片長(zhǎng)度（Sepal.Length）、萼片寬度（Sepal.Width）、花瓣長(zhǎng)度（Petal.Length）、花瓣寬度（Petal.Width））選取后兩種屬性進(jìn)行分析。設(shè)置對(duì)象為150對(duì)，設(shè)為150類。將其分別分為二、三、四類（X=2、1.25、1.15）可明顯看出二類或三類更加容易區(qū)分，說(shuō)明該算法對(duì)數(shù)據(jù)的分布簇型結(jié)構(gòu)的發(fā)現(xiàn)是有效的。

在可視化過(guò)程中，首先對(duì)于樹狀圖，進(jìn)行層次聚類過(guò)程中，聚類的兩類用線段連接，依次進(jìn)行下去。然后對(duì)于散點(diǎn)圖，例如分成兩類的情況，則分別用兩種顏色分辨兩類，橫坐標(biāo)為花瓣長(zhǎng)度或?qū)挾?，縱坐標(biāo)為每?jī)深惖木嚯x，最后將文字轉(zhuǎn)化為圖片，輸入即可得到所要的圖形。

4 結(jié)果展示

圖1是將層次聚類用樹狀圖的方式進(jìn)行表述，橫軸長(zhǎng)度代表每一類大小，縱軸表示相對(duì)距離。而每一組連線都代表著將距離最近的兩點(diǎn)聯(lián)系起來(lái)，而這一條連線所取的高度即為兩點(diǎn)距離。

具體畫圖過(guò)程：從sklearn庫(kù)中挑選出datasets這個(gè)庫(kù)，再?gòu)膁atasets子庫(kù)中讀取iris（鳶尾花）數(shù)據(jù)。挑選出后兩種屬性，即可得出圖像，從這幅圖中明顯可以看出距離和越小越密集。依次向上進(jìn)行層次聚類的過(guò)程中類間越來(lái)越大。

圖2、圖3、圖4三幅圖中，橫軸表示花瓣長(zhǎng)度，縱軸代表花瓣寬度，分別代表著將用層次聚類分為兩類、三類、四類（X=2、1.25、1.15）。X=2時(shí)易得長(zhǎng)度為1-2與3-6分別為一類，層次十分清晰。用相同方法分析X=1.25、1.15時(shí)，三類較清晰，而分為四類時(shí)層次聚類不明顯，排除分為四類。

5 討論

在該聚類過(guò)程中，有以下幾點(diǎn)需要注意。類之間的距離的定義，我們這里選取平均距離作為兩個(gè)類之間的距離定義，這里也可以選取兩個(gè)類距離最近或最遠(yuǎn)的兩點(diǎn)之間的距離作為類之間的距離。

另外，在聚類過(guò)程中，有一個(gè)需要預(yù)先定義的參數(shù)就是類的個(gè)數(shù)。類數(shù)的定義可以根據(jù)一些數(shù)學(xué)指標(biāo)來(lái)確定，如使得所有平均類間距離和平均類內(nèi)距離的比值最大。當(dāng)然，還有一個(gè)判斷標(biāo)準(zhǔn)就是可視化出來(lái)，來(lái)觀察聚類效果如何，在本工作中，數(shù)據(jù)是二維的，如果維度大于二維，可以通過(guò)一些降維方法（構(gòu)造一個(gè)從高維到二維空間的映射，使得原高維空間中點(diǎn)的鄰近性在二維空間中盡量得以保留）來(lái)可視化。

6 結(jié)論

層次聚類是一種通過(guò)聚合形式逐步形成層次結(jié)構(gòu)從而劃分?jǐn)?shù)據(jù)點(diǎn)類別的算法。我們通過(guò)鳶尾花數(shù)據(jù)的聚類實(shí)驗(yàn)驗(yàn)證這個(gè)算法的特性，并且用可視化方法觀察了聚類結(jié)果，算法有效的發(fā)現(xiàn)了數(shù)據(jù)點(diǎn)中的簇狀結(jié)構(gòu)。而使用這種聚類方法可以很清晰的將大量繁雜的數(shù)據(jù)庫(kù)聚類成幾類，方法簡(jiǎn)單，利用圖像也使聚類層次更加清晰，是一種簡(jiǎn)單直觀的聚類方法。

參考文獻(xiàn)

[1]http：//scitools.org.uk/iris/.

[2]Fisher，R.A."The use of multiple measurements in taxonomic problems" Annual Eugenics，7，Part II，179-188 （1936）；also in "Contributions to Mathematical Statistics"（John Wiley，NY，1950）.

[3]Johnson，Stephen C."Hierarchical clustering schemes."Psychometrika32.3（1967）：241-254.

[4]段明秀.層次聚類算法的研究及應(yīng)用[D].中南大學(xué)，2009.

作者單位

湖北省宜昌市第一中學(xué) 湖北省宜昌市 443003