層次聚類的算法研究

周世杰

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

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

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

1.引言

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

監(jiān)督學(xué)習(xí)是對帶標(biāo)注的數(shù)據(jù)進(jìn)行學(xué)習(xí)，優(yōu)化模型參數(shù)，使得最大程度的擬合標(biāo)注數(shù)據(jù)。非監(jiān)督學(xué)習(xí)是指我們根據(jù)類別未知（沒有被標(biāo)記）的訓(xùn)練樣本解決模式識別中的各種問題，稱為非監(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)，是有知識、有信息的，從屬于監(jiān)督學(xué)習(xí)。而聚類沒有具體的分類標(biāo)準(zhǔn)，主要任務(wù)是對大量沒有分類標(biāo)準(zhǔn)且沒有標(biāo)注的數(shù)據(jù)進(jìn)行合理歸類，從屬于非監(jiān)督學(xué)習(xí)。

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

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

2.層次聚類算法原理

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

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

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

2.1單點間的距離計算

記兩個單點x=（x1，x2，…，xn），y=（y1，y2，…，yn），其中n表示向量的維度。可以用兩點間的距離公式度量兩點的距離。用D來表示它們的距離，則有

dpoint（x，y）=■

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

2.2簇與簇間距離計算

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

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

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

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

其中ci，cj，表示不同的簇，p，p'表示不同簇中的單點。

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

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

平均值距離法將兩個聚類各自的中心點作為兩個簇之間的距離。

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

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

平均距離法將兩個聚類的所有點的距離的平均值作為兩個簇之間的距離。

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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