周世杰

【摘要】在實(shí)際應(yīng)用中往往需要對(duì)大量信息或者數(shù)據(jù)進(jìn)行分類或者劃分，而層次聚類算法可以在最少的假設(shè)下實(shí)現(xiàn)對(duì)數(shù)據(jù)的聚類。本文介紹了層次聚類算法原理，將其拆解為單點(diǎn)距離計(jì)算、簇間整合以及中間狀態(tài)選擇，并且總結(jié)了層次聚類算法的實(shí)際應(yīng)用。

【關(guān)鍵詞】層次聚類 ?分類 ?距離

【中圖分類號(hào)】G63 ? 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】2095-3089（2018）40-0240-02

1.引言

在現(xiàn)實(shí)生活中，常常需要對(duì)事物進(jìn)行歸類或者劃分，將整體劃分成具有不同特征的小組，針對(duì)每個(gè)小組的特性進(jìn)行決策往往可以達(dá)到事半功倍的效果。當(dāng)已知具體的分類標(biāo)準(zhǔn)，并且具有可供學(xué)習(xí)的具有類別標(biāo)簽的數(shù)據(jù)，我們可以建立分類模型，對(duì)數(shù)據(jù)進(jìn)行建模學(xué)習(xí)，進(jìn)而對(duì)未知的新樣本分類到既定的分類體系中，這個(gè)過程叫作分類。然后，在很多的應(yīng)用場(chǎng)景中，缺少一個(gè)明確的分類體系和準(zhǔn)確的標(biāo)注數(shù)據(jù)，這時(shí)需要引入聚類算法。

監(jiān)督學(xué)習(xí)是對(duì)帶標(biāo)注的數(shù)據(jù)進(jìn)行學(xué)習(xí)，優(yōu)化模型參數(shù)，使得最大程度的擬合標(biāo)注數(shù)據(jù)。非監(jiān)督學(xué)習(xí)是指我們根據(jù)類別未知（沒有被標(biāo)記）的訓(xùn)練樣本解決模式識(shí)別中的各種問題，稱為非監(jiān)督學(xué)習(xí)。簡單來說監(jiān)督學(xué)習(xí)就是看輸入的數(shù)據(jù)是否有標(biāo)簽，輸入的數(shù)據(jù)有標(biāo)簽，則為監(jiān)督學(xué)習(xí)，沒有標(biāo)簽則為非監(jiān)督學(xué)習(xí)。

分類任務(wù)有具體的分類標(biāo)準(zhǔn)，是有知識(shí)、有信息的，從屬于監(jiān)督學(xué)習(xí)。而聚類沒有具體的分類標(biāo)準(zhǔn)，主要任務(wù)是對(duì)大量沒有分類標(biāo)準(zhǔn)且沒有標(biāo)注的數(shù)據(jù)進(jìn)行合理歸類，從屬于非監(jiān)督學(xué)習(xí)。

聚類算法對(duì)具體的應(yīng)用場(chǎng)景幾乎沒有假設(shè)要求，不需要額外的信息（標(biāo)注的數(shù)據(jù)），可以解決更多更復(fù)雜和更寬泛的問題，能夠處理許多分類任務(wù)解決不了的問題。

常見的聚類算法有k-means聚類和層次聚類，本文主要介紹層次聚類算法。

2.層次聚類算法原理

層次聚類法原理主要分為凝聚的算法和分裂的算法。凝聚的算法指的是自下而上的算法，分裂是自上而下的算法。凝聚的和分裂的算法在本質(zhì)上是一致的，下面我們以更常用的凝聚為例，具體的介紹層次聚類的算法原理和步驟。

凝聚的層次聚類，首先初始狀態(tài)是每個(gè)樣本自成一類，通過計(jì)算兩兩之間的距離，把最相近的合并成一類，以此類推，自下而上的合并，最終所有的樣本合并成一個(gè)大類，即最終狀態(tài)[1]。

在算法不斷迭代的過程中，主要涉及到了單點(diǎn)間的距離計(jì)算、簇與簇之間的距離計(jì)算和選擇中間狀態(tài)等問題。

2.1單點(diǎn)間的距離計(jì)算

記兩個(gè)單點(diǎn)x=（x1，x2，…，xn），y=（y1，y2，…，yn），其中n表示向量的維度?？梢杂脙牲c(diǎn)間的距離公式度量兩點(diǎn)的距離。用D來表示它們的距離，則有

dpoint（x，y）=■

除了兩點(diǎn)間距離公式以外，還可以使用其他的距離定義，一般根據(jù)實(shí)際應(yīng)用情況選擇恰當(dāng)?shù)木嚯x定義或者距離公式。

2.2簇與簇間距離計(jì)算

除了需要對(duì)單點(diǎn)進(jìn)行距離計(jì)算外，還需要對(duì)簇和簇計(jì)算它們的距離。其中常見的簇與簇之間的距離計(jì)算方法有：最小距離法、最大距離法、平均值距離法和平均距離法。

這幾種方法各有各的好處。我們要根據(jù)具體的場(chǎng)景來選擇我們具體的用哪種方法。下面我們來逐個(gè)介紹這幾種方法。

最小距離法將兩個(gè)聚類的所有數(shù)據(jù)點(diǎn)最近的距離代表兩個(gè)簇之間的距離。

dmin（ci，cj）=min■d■（p，p'）

其中ci，cj，表示不同的簇，p，p'表示不同簇中的單點(diǎn)。

最大距離法將指兩個(gè)聚類的所有數(shù)據(jù)點(diǎn)最遠(yuǎn)的距離代表兩個(gè)簇之間的距離。

dmax（ci，cj）=max■d■（p，p'）

平均值距離法將兩個(gè)聚類各自的中心點(diǎn)作為兩個(gè)簇之間的距離。

dmean（ci，cj）=d■（m■，m■）

其中mi是簇ci的平均值，mj是簇cj的平均值。

平均距離法將兩個(gè)聚類的所有點(diǎn)的距離的平均值作為兩個(gè)簇之間的距離。

davg（ci，cj）=■■■■■d■（p，p'）

其中，n■，nj分別為簇ci，cj中樣本的數(shù)量。

這四種方法各有不同，適用于不同的場(chǎng)景或者不同的領(lǐng)域。最小距離法和最大距離法相比較于其他的兩種方法來說的話，更加的直觀，計(jì)算復(fù)雜度較低。但是最小距離和最大距離，只考慮了兩個(gè)簇之間的極端情況，沒有考慮到內(nèi)部的細(xì)致差異。我們可以根據(jù)實(shí)際應(yīng)用情況選擇不同的簇間整合方法。

2.3選擇中間狀態(tài)

選擇中間狀態(tài)也是很重要的一步，因?yàn)槲覀兊某跏紶顟B(tài)和終止?fàn)顟B(tài)都是樸素的，是沒有信息的，我們有價(jià)值的狀態(tài)量都在中間，所以我們要根據(jù)預(yù)期數(shù)量、類別的容忍程度方法來確定我們的中間狀態(tài)。

如果存在預(yù)期的聚類數(shù)量，可以根據(jù)預(yù)期的簇類數(shù)量選擇中間狀態(tài)為最終聚類結(jié)果。但是層次聚類的優(yōu)勢(shì)，在于可以不事先預(yù)設(shè)預(yù)期的簇類數(shù)量，而是通過數(shù)據(jù)的信息決定最終的類別數(shù)量。所以，一般根據(jù)類別的容忍程度，通過設(shè)定閾值，如果簇間合并距離超過閾值則停止，從而得到最終的聚類結(jié)果。

中間狀態(tài)的選擇體現(xiàn)了層次聚類算法的靈活性和適應(yīng)性，可以根據(jù)不同的數(shù)據(jù)類型和分布，不同的應(yīng)用場(chǎng)景選擇最終的聚類結(jié)果。

3.應(yīng)用總結(jié)

隨著信息的高速發(fā)展，信息的大量膨脹，如何有效并且高效的利用信息和數(shù)據(jù)變成一個(gè)非常重要的難題。對(duì)大量信息進(jìn)行分類整理往往是整合利用數(shù)據(jù)的第一步，所以聚類在實(shí)際生活中的使用非常廣泛，是很多應(yīng)用的基礎(chǔ)。

層次聚類最常見的一種應(yīng)用是文本聚類[2]。通過對(duì)網(wǎng)上大量的網(wǎng)站和信息進(jìn)行聚類，提高信息檢索的準(zhǔn)確性，進(jìn)而提升人們獲取信息的效率。對(duì)實(shí)時(shí)的新聞或者網(wǎng)絡(luò)評(píng)論進(jìn)行聚類，可以實(shí)時(shí)了解輿論動(dòng)向和發(fā)展，有利于進(jìn)行輿情分析和控制。研究文獻(xiàn)包含了大量的領(lǐng)域前沿知識(shí)和發(fā)展成果，對(duì)文獻(xiàn)進(jìn)行合理的聚類和劃分[3]，能夠幫助讀者快速的發(fā)現(xiàn)有效的相關(guān)信息，了解相關(guān)領(lǐng)域的前沿發(fā)展，提高信息獲取的效率。

對(duì)時(shí)空數(shù)據(jù)進(jìn)行聚類分析，也可以從大量時(shí)空數(shù)據(jù)中獲取信息。從過對(duì)歷史的犯罪數(shù)據(jù)進(jìn)行熱點(diǎn)分析和區(qū)域聚類，有利于人們根據(jù)犯罪活動(dòng)熱點(diǎn)區(qū)域進(jìn)行有針對(duì)性的警力部署[4]，指導(dǎo)公安機(jī)關(guān)破案，并且制定針對(duì)性的警務(wù)戰(zhàn)術(shù)策略，進(jìn)行有效的干預(yù)。

除此之外，電子商務(wù)已成為人們?nèi)粘ＯM(fèi)的重要形式，如何有針對(duì)性的向消費(fèi)者推薦商品是電子商務(wù)中非常重要的環(huán)節(jié)。合理的個(gè)性化推薦能夠提高消費(fèi)者的購買力，降低購物成本，加大用戶粘性，從而對(duì)電子商務(wù)平臺(tái)形成良性循環(huán)。在個(gè)性化推薦中，往往涉及到對(duì)不同用戶的聚類和對(duì)平臺(tái)上成千上萬的商品的聚類。通過用戶和用戶之間的相似性以及商品和商品之間的相似性，實(shí)現(xiàn)個(gè)性化推薦。

參考文獻(xiàn)：

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

[2]石曉敬，韓燮.文本聚類算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì)， 2010（9）：2013-2015

[3]陳旭玲，樓佩煌.改進(jìn)層次聚類算法在文獻(xiàn)分析中的應(yīng)用[J].數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用，2009（4）：277-287.

[4]陳鵬，馬偉.層次聚類法在空間犯罪熱點(diǎn)分析中的應(yīng)用[J].中國人民公安大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2013（1）：64-67.