層次聚類分析算法的思考及實(shí)現(xiàn)

1、層次聚類分析算法的思考及實(shí)現(xiàn)一.概述對(duì)急劇增長(zhǎng)的數(shù)據(jù)加以組織和從數(shù)據(jù)中學(xué)習(xí)有價(jià)值信息的需要，使得聚類成為一個(gè)非常活躍的研究領(lǐng)域。不采用概括技術(shù)，人們很難從充斥著大量信息的數(shù)據(jù)庫(kù)中發(fā)現(xiàn)知識(shí)?；镜慕y(tǒng)計(jì)量（如均值、方差）或者直方圖可以提供對(duì)于數(shù)據(jù)的初步感覺。然而，聚類分析可以 解釋對(duì)象之間、特征之間以及對(duì)象和特征之間錯(cuò)綜復(fù)雜的關(guān)系。它是數(shù)據(jù)挖掘中研究和應(yīng)用的一個(gè)重要部分。聚類分析簡(jiǎn)單來(lái)講就是將數(shù)據(jù)對(duì)象分組成多個(gè)類或簇，在同一個(gè)簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差別較大。聚類分析是無(wú)指導(dǎo)學(xué)習(xí)。它與數(shù)據(jù)挖掘中的的分類不同，在分類模塊中，對(duì)于目標(biāo)數(shù)據(jù)庫(kù)中存在哪些類這一信息我們是知道的，在那

2、里要做的就是將每一條記錄屬于哪一類標(biāo)記出來(lái)；與此相似但又不同的是，聚類是在預(yù)先不知道目標(biāo)數(shù)據(jù)庫(kù)到底有多少類的情況下，希望將所有的紀(jì)錄組成不同的類或者說(shuō)“聚類”（cluster）并且使得在這種分類情況下，以某種度量為標(biāo)準(zhǔn)的相異度，在同一聚類之間最小化， 而在不同聚類之間最大化。1 傳統(tǒng)算法介紹聚類分析方法主要有以下幾種：劃分方法，層次方法，基于密度的方法，基于網(wǎng)格的方法和基于模型的方法。本文主要討論層次聚類方法。層次聚類方法是聚類分析的一個(gè)重要方法。這種方法對(duì)給定的數(shù)據(jù)集合進(jìn)行層次的分 解，根據(jù)層次的分解如何形成， 它又可分為凝聚法（也稱自底向上方法）和分裂法（也稱為從上 向下方法），而凝聚的層

3、次聚類方法應(yīng)用得更多，該方法采用自底向上的策略，首先將每個(gè) 對(duì)象作為一個(gè)簇，然后合并這些原子簇為越來(lái)越大的簇，直到所有的對(duì)象都在一個(gè)簇中，或者某個(gè)終結(jié)條件被滿足。資格廣泛采用的簇間距離度量方法分別為：最小距離、最大距離、 平均值的距離、平均距離。本文主要討論層次聚類算法中的平均距離算法。層次聚類算法基本思想及其分析:假定有N個(gè)對(duì)象被聚類，其距離矩陣大小為N*N，采用平均距離的凝聚層次聚類方法的基本過(guò)程如下：1）將每一個(gè)數(shù)據(jù)對(duì)象視為一類，每類僅一個(gè)對(duì)象，計(jì)算它們之間的最短距離D,類與類之間的距離就是她們所包含對(duì)象之間的距離，得到初始化距離矩陣；（或者初始化矩陣作為已知參數(shù)給出）2）將距離最近的兩

4、個(gè)類合并成一個(gè)新的類；3）重新計(jì)算所有類之間的距離；4）重復(fù)2和3步，知道所有類最后合并成一個(gè)類或者達(dá)到結(jié)束條件（該條件可人 為指定）層次聚類算法每合并完一個(gè)類后，就必須重新計(jì)算合并后類之間的距離，也就是重新計(jì)算距離矩陣，對(duì)于有大量數(shù)據(jù)的數(shù)據(jù)庫(kù)而言，該計(jì)算量是驚人的。假定聚類的對(duì)象有N個(gè)，那么按照層次聚類算法的思想，第一次合并之前距離矩陣大小為N*N，第二次合并之前必須重新計(jì)算類與類之間的距離，距離矩陣大小變?yōu)?N-1)*(N-1)，依次類推，直至所有類合并為一個(gè)類為止，相應(yīng)的計(jì)算量為N*N階，對(duì)于海量數(shù)據(jù)來(lái)說(shuō)，這需要耗費(fèi)大量的存儲(chǔ)空間和計(jì)算時(shí)間。為了節(jié)省大量的計(jì)算時(shí)間，需要想辦法在計(jì)算距離時(shí)

5、應(yīng)用到上次計(jì)算的結(jié)果，從而提高數(shù)據(jù)計(jì)算效率。2 傳統(tǒng)算法分析在上述算法中第一步時(shí)間復(fù)雜度為0(n*n)，第二步的時(shí)間復(fù)雜度為0(n*n)(因?yàn)樾枰獙?duì)距離矩陣進(jìn)行檢索，找出距離最小的兩個(gè)類)，第三步的時(shí)間復(fù)雜度同樣為0(n*n)(對(duì)類之間距離進(jìn)行更新，二維距離矩陣個(gè)數(shù)為1/2n*n)，第四步的時(shí)間復(fù)雜度為0(1)，第五步為0(1)，由于第三步要運(yùn)行N-1次，因此整個(gè)算法的時(shí)間復(fù)雜度為0(n*n*n)?？臻g復(fù)雜度來(lái)看，由于算法需要建一個(gè)N階相異度矩陣，故空間復(fù)雜度為0(n*n)?？梢钥闯觯谌綖檎麄€(gè)算法的瓶頸，要是能降低第三步的時(shí)間復(fù)雜度，整個(gè)算法的性能就能得到提高。3算法的改進(jìn)對(duì)上述算法分析不

6、難看出，算法整個(gè)的計(jì)算過(guò)程實(shí)際上就是第二步與第三步的不斷重復(fù) 過(guò)程，因此要想辦法在第二步與第三步上盡可能地降低算法的時(shí)間復(fù)雜度，或者減少計(jì)算類之間距離時(shí)不必要的計(jì)算量，針對(duì)第二步，因?yàn)樾枰页鏊蓄愔g距離的最小值，而為了尋找最小值傳統(tǒng)算法是遍歷整個(gè)距離矩陣，進(jìn)而找出，在此步不妨將堆的思想引入進(jìn)來(lái)，首先為數(shù)據(jù)集中的所有數(shù)據(jù)對(duì)象建立基于堆的優(yōu)先隊(duì)列，優(yōu)先隊(duì)列中各個(gè)數(shù)據(jù)對(duì)象之間的距離從小到大排好，這樣在找對(duì)象之間最小距離的時(shí)候便不用遍歷，直接取出最小距離即可。而堆排序的基本思想就是把所有數(shù)據(jù)元素集合構(gòu)成一個(gè)完全二叉樹結(jié)構(gòu)，則每次選擇出一個(gè)最大(或最小)的數(shù)據(jù)元素只需比較完全二叉樹的高度此，即log

7、n，則整個(gè)堆排序的時(shí)間復(fù)雜度為nlogn。在數(shù)據(jù)存儲(chǔ)問(wèn)題上，也就是選用什么樣的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)，該問(wèn)題對(duì)于算法的最終實(shí)現(xiàn)也是至關(guān)重要的。最初想到的便是二維數(shù)組，因?yàn)檫@種存儲(chǔ)結(jié)構(gòu)可以方便的表示出各個(gè) 點(diǎn)之間的距離，直觀明了，但是考慮到該算法只有第一步初始化的時(shí)候是計(jì)算各個(gè)離群點(diǎn)之 間的距離而后續(xù)循環(huán)步驟均是對(duì)不同的類之間的距離進(jìn)行計(jì)算，而二維數(shù)組的行列無(wú)法正確表示出這些對(duì)象，所以該方案不可行，經(jīng)過(guò)長(zhǎng)時(shí)間思考，最終選定一種數(shù)據(jù)結(jié)構(gòu)，如下圖所示：該存儲(chǔ)結(jié)構(gòu)中第一部分為類1第二部分為類2,第三部分為兩個(gè)類之間的距離，而類1與類2中為一個(gè)線性列表，其中每一項(xiàng)為一個(gè)點(diǎn)。當(dāng)進(jìn)行第一步的計(jì)算時(shí)，兩個(gè)類中分別

8、 只有一個(gè)點(diǎn)，類間距離即為兩點(diǎn)之間的距離（由已知給出），有不同的點(diǎn)聚為一類時(shí)，在該類的線性列表中將包含該類中所有的點(diǎn)，類與類間的距離通過(guò)平均歐式距離計(jì)算得到。而第三步中傳統(tǒng)算法涉及到計(jì)算目前所有類之間的距離問(wèn)題，在數(shù)據(jù)量比較大的時(shí)候這個(gè)過(guò)程是相當(dāng)麻煩的， 因?yàn)樽隽颂嗟闹貜?fù)計(jì)算， 我們完全可以利用前一次已經(jīng)計(jì)算好的結(jié) 果，對(duì)上一循環(huán)過(guò)程所產(chǎn)生的結(jié)果進(jìn)行部分修改，而不是整體刪除，整體重新計(jì)算。如給定五個(gè)點(diǎn)1、2、3、4?？梢员硎境上卤?23133143233243341可看出在該表中點(diǎn)3與點(diǎn)4的距離最短為1,所以將這兩個(gè)點(diǎn)合并為一類，更新距離列 表，將原來(lái)與點(diǎn)3與點(diǎn)4有關(guān)的所有距離項(xiàng)刪除（包含點(diǎn)

9、3與點(diǎn)4）然后添加新類與剩下所有類的距離，而表中原來(lái)未涉及到點(diǎn)3與點(diǎn)4的距離則不用更新，此過(guò)程只需計(jì)算N次,而非N*N次。更新后的距離列表如下圖所示：1233,4133,423三.改進(jìn)后算法的實(shí)現(xiàn)改進(jìn)后的算法使用JAVA語(yǔ)言實(shí)現(xiàn)，用JAVA語(yǔ)言中ArrayList代表上述算法描述中的線 性列表。如下表所示：ArrayListlArrayList2類間距離程序運(yùn)行的主界面如下所示:該程序輸入?yún)?shù)有四個(gè)1.考慮到一般的聚類分析都是針對(duì)大量數(shù)據(jù)，所以設(shè)置參數(shù)的輸入為文件輸入，其中可以用TXT格式的記事本文件，也可用EXCEL表格來(lái)作為已知參 數(shù)，2.“點(diǎn)集個(gè)數(shù)”用來(lái)指出點(diǎn)集的總個(gè)數(shù)。3.“計(jì)算過(guò)程文

10、件”用來(lái)設(shè)置計(jì)算過(guò)程文件的保存，考慮到數(shù)據(jù)量大時(shí)，對(duì)每一次聚類中間結(jié)果都顯示到主界面中的話，不僅不方便用戶查看同時(shí)影響界面美觀，故為了清晰記錄整個(gè)聚類的過(guò)程， 所以將該過(guò)程通過(guò)文件的形式保 存，方便用戶日后查看。4.“目標(biāo)類個(gè)數(shù)”用來(lái)指定將點(diǎn)集聚成多少個(gè)類，默認(rèn)為1。其中程序運(yùn)行的最終結(jié)果會(huì)顯示在主界面中。F面通過(guò)一個(gè)實(shí)例來(lái)演示該程序。1選擇文件（該文件只是用來(lái)測(cè)試，數(shù)據(jù)量較小，故用0 4 5 6 7 90 0 1 2 3 50 0 0 2 2 40 0 0 0 3 20 0 0 0 0 20 0 0 0 0 0供包含六個(gè)點(diǎn)，點(diǎn)之間距離通過(guò)二維數(shù)組給出2設(shè)置其他相應(yīng)參數(shù)?！包c(diǎn)集個(gè)數(shù)”為6, “目標(biāo)類個(gè)數(shù)”設(shè)置為3?！坝?jì)算過(guò)程文件” 設(shè)置為D:234234.TXT。3點(diǎn)擊“計(jì)算”按鈕程序運(yùn)行結(jié)果如下所示:TXT格式），文件內(nèi)容如下IO385I31LM35MI5時(shí)仏0IM1 21 3- 5町削7-081- 2服5MH. ? 2-5町3. 5 7.5t* 5 2.51, 2JI3, 5 3,2503, 5 7-51, 2 9.3333333333333333, 5(4, 1, 2 3-0說(shuō)明：該過(guò)程文件每一步均有分割線作為標(biāo)記，其中每一