自動(dòng)連結(jié)鏈聚類算法

李隘優(yōu)

( 閩西職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)系,福建 龍巖 364021 )

摘要：針對(duì)傳統(tǒng)聚類算法存在時(shí)間性能低效且需要輸入?yún)?shù)的缺點(diǎn)，本文提出了一種自動(dòng)連結(jié)鏈聚類新算法.該算法在確立數(shù)據(jù)的基礎(chǔ)上,通過(guò)計(jì)算數(shù)據(jù)點(diǎn)與各頂點(diǎn)的距離并加以排序形成不同群組，然后快速搜尋出它們的相鄰點(diǎn)形成連結(jié)鏈網(wǎng)絡(luò)，再根據(jù)連結(jié)鏈的平均距離刪除過(guò)長(zhǎng)的連結(jié)鏈，從而達(dá)到聚類的目的.實(shí)驗(yàn)結(jié)果表明,本文算法與DBSCAN及Single-Link算法具有相同的聚類效果，但執(zhí)行時(shí)間約僅為這兩種算法的10%.

關(guān)鍵詞：自動(dòng)連結(jié)鏈； 聚類算法； 象限； 網(wǎng)絡(luò)

收稿日期：2015-06-28

作者簡(jiǎn)介：李隘優(yōu)(1980—)，男，講師，研究方向?yàn)樗惴ǚ治雠c設(shè)計(jì).

文章編號(hào)：1004-4353(2015)03-0254-03

中圖分類號(hào)：TP309.3

Automatic link-chain clustering algorithm

LI Aiyou

(DepartmentofComputer,MinxiVocational&TechnicalCollege,Longyan364021,China)

Abstract：Time performance for shortcomings and inefficiencies of traditional clustering algorithms require input parameters,this paper proposes a new algorithm. The algorithm on the basis of the data side established by the distance calculation of data points and the vertices and be able to sort the formation of different groups,and then quickly find out their adjacent points form a network link chain,according to the average distance is too long and then delete the link chain link chain,which serve the purpose of clustering. Experimental results show that the execution time of the automatic link chain clustering algorithm accounts for about 10% of the common algorithm.

Key words： automatic link-chain; clustering algorithm; quadrant； network

0引言

群集分析技術(shù)[1]由于能夠明顯突出群體間的差異性，因此被廣泛應(yīng)用于圖像識(shí)別、數(shù)據(jù)壓縮、影像處理、空間分析和生物信息特征分析等領(lǐng)域.但目前大多群集分析技術(shù)算法需要事先給出(或輸入)一個(gè)或多個(gè)參數(shù)，而確定適當(dāng)?shù)倪@些參數(shù)本身就不是一件易事，這不僅加大了聚類分析過(guò)程的復(fù)雜度，有時(shí)也影響了聚類結(jié)果[2].例如K-Means聚類算法[3]中，必需代入?yún)?shù)k以確立所要聚類的群體數(shù)，并需要反復(fù)嘗試及驗(yàn)算，才能得到較好的聚類結(jié)果，計(jì)算量非常大.這類代入?yún)?shù)的聚類算法需建立一套參數(shù)范圍估算的驗(yàn)算公式，才能有效地執(zhí)行群集分析.鑒于此，本文引入自動(dòng)連結(jié)鏈聚類算法(automatic link-chain clustering algorithm，ALC Algorithm)，它無(wú)需輸入?yún)?shù)，也無(wú)需反復(fù)針對(duì)聚類結(jié)果加以嘗試及驗(yàn)算.實(shí)驗(yàn)表明，該算法既保證了聚類的準(zhǔn)確率，又提高了聚類的速度.

1自動(dòng)連結(jié)鏈聚類(ALC)算法

自動(dòng)連結(jié)鏈聚類算法是近年來(lái)興起的一個(gè)簡(jiǎn)單聚類方式，它有別于基于階層式聚類法[4]、基于密度聚類法[5]、基于網(wǎng)格聚類法[6]及基于模型式聚類法[7]，但與分割式聚類法[8]接近.ALC算法在分割群體之前，每一個(gè)數(shù)據(jù)點(diǎn)必需找到各個(gè)象限中與它最接近的數(shù)據(jù)點(diǎn)，然后連結(jié)各點(diǎn)形成連結(jié)鏈網(wǎng)絡(luò).因此，從網(wǎng)絡(luò)中很容易就能發(fā)現(xiàn)數(shù)據(jù)點(diǎn)間的分布關(guān)系，通過(guò)刪除過(guò)長(zhǎng)的連結(jié)鏈，就能達(dá)到快速分割群體的目的.本文重點(diǎn)討論如何在這些數(shù)據(jù)群中，不輸入任何參數(shù)且只需使用少量的計(jì)算就能建立起連結(jié)鏈網(wǎng)絡(luò)結(jié)構(gòu).

ALC算法的具體步驟如下：

1)找出數(shù)據(jù)點(diǎn)邊界頂點(diǎn).尋找出數(shù)據(jù)點(diǎn)分布的邊界，以邊界的頂點(diǎn)作為排序基準(zhǔn)點(diǎn).如對(duì)于圖1所描繪的數(shù)據(jù)分布，根據(jù)數(shù)據(jù)點(diǎn)分布的情況尋找數(shù)據(jù)點(diǎn)的邊界，并以A、B、C、D點(diǎn)作為數(shù)據(jù)的邊界頂點(diǎn).

圖1　樣本分布邊界點(diǎn)

2)數(shù)據(jù)點(diǎn)對(duì)邊界頂點(diǎn)排序，形成不同群組.如將圖1中數(shù)據(jù)集合中的數(shù)據(jù)點(diǎn)分別對(duì)邊界頂點(diǎn)A、B、C、D進(jìn)行排序，即計(jì)算所有的數(shù)據(jù)點(diǎn)與A、B、C、D點(diǎn)的歐氏距離(Euclideandistance)：

其中k為維度；用計(jì)算出的距離加以排序形成不同群組，群組排序結(jié)果以SortA、SortB、SortC、SortD表示.

3) 快速搜尋鄰點(diǎn),形成連結(jié)鏈網(wǎng)絡(luò).要存儲(chǔ)一個(gè)連結(jié)鏈網(wǎng)絡(luò)數(shù)據(jù)就必須定義一個(gè)數(shù)據(jù)結(jié)構(gòu)，以便記錄連結(jié)鏈網(wǎng)絡(luò)信息.從任一個(gè)數(shù)據(jù)點(diǎn)開(kāi)始，根據(jù)上面所獲得的排序群組來(lái)搜尋每個(gè)象限中最接近(相鄰)的點(diǎn)并計(jì)算出它們之間的距離，如果該象限中沒(méi)有找到相鄰的點(diǎn)則以NULL表示；重復(fù)上述步驟，直到每個(gè)數(shù)據(jù)點(diǎn)都在每個(gè)象限中找到它的相鄰的點(diǎn).最終生成的連結(jié)鏈網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示.

圖2　連結(jié)鏈網(wǎng)絡(luò)生成圖

快速搜尋相鄰點(diǎn)的方法,如圖3所示，以P點(diǎn)搜尋第一象限相鄰的點(diǎn)為例，在排序群C序列中找到與P相鄰的排序點(diǎn)P2，以P2在排序群C序列中的位置作為搜尋范圍的起點(diǎn)；在排序群A序列中找到與P相鄰的排序點(diǎn)P1，以P1在排序群C序列中的對(duì)應(yīng)位置作為搜尋范圍的終點(diǎn)；在排序群C中，由P2(起點(diǎn))到P1(終點(diǎn))間的范圍為搜尋范圍(圖3中虛線所繪區(qū)域)，將大幅度地減少尋找相鄰點(diǎn)所需要比對(duì)數(shù)據(jù)點(diǎn)的次數(shù)，可大大縮短計(jì)算機(jī)的運(yùn)算時(shí)間.

圖3　P點(diǎn)搜尋第一象限的最近點(diǎn)

4)計(jì)算連結(jié)鏈的平均距離.生成連結(jié)鏈網(wǎng)絡(luò)后，必須進(jìn)行數(shù)據(jù)分析才可進(jìn)一步進(jìn)行聚類.根據(jù)所有的連結(jié)鏈的距離(即數(shù)據(jù)點(diǎn)間的差異性)計(jì)算出所有連結(jié)鏈的平均值(DAVG)，并以此作為聚類的標(biāo)準(zhǔn).

其中Des∈(DesA,DesB,DesC,DesD)，N為有效的連結(jié)鏈總數(shù).

5)刪除過(guò)長(zhǎng)的連結(jié)鏈.根據(jù)聚類的評(píng)估標(biāo)準(zhǔn)值DAVG進(jìn)行聚類，刪除連結(jié)鏈網(wǎng)絡(luò)中所有連結(jié)鏈距離大于DAVG的數(shù)據(jù)，被刪除的數(shù)據(jù)點(diǎn)歸到不同的群組中，存在連結(jié)鏈關(guān)系的數(shù)據(jù)點(diǎn)歸為同一群組，從而使數(shù)據(jù)產(chǎn)生群聚，形成聚類效果.

2實(shí)驗(yàn)與分析

為分析ALC算法的性能，與傳統(tǒng)Single-Link算法、DBSCAN算法進(jìn)行了對(duì)比分析.聚類算法執(zhí)行時(shí)間的實(shí)驗(yàn)設(shè)計(jì)：分別輸入500、1000、1500、2000、2500、3000、3500、4000、4500、5000個(gè)隨機(jī)樣本點(diǎn)，數(shù)據(jù)集合為二維坐標(biāo)點(diǎn)，數(shù)據(jù)數(shù)值范圍為±200，分別使用ALC、DBSCAN、Single-Link聚類算法進(jìn)行群集分析，其中DBSCAN、Single-Link聚類算法分別參考文獻(xiàn)[5]與文獻(xiàn)[4].由ALC進(jìn)行群集分析之后，將所得到的DAVG作為DBSCAN算法的Eps及Single-Link算法的Threshold參數(shù)值.不同算法執(zhí)行時(shí)間的結(jié)果如表1所示.

表1　不同聚類算法執(zhí)行時(shí)間的比較

由表1可知，3種聚類法都能將非固定形狀樣本數(shù)據(jù)分出相同的群組數(shù)量，但DBSCAN及Single-Link算法都需反復(fù)調(diào)整Eps及Threshold參數(shù)值才能得到較佳的聚類效果.3種聚類算法的效果雖然相同，但執(zhí)行效率上ALC算法所消耗的時(shí)間遠(yuǎn)小于DBSCAN和Single-Link算法，如圖4所示.

圖4　不同算法執(zhí)行時(shí)間的比較

3結(jié)論

本文提出的自動(dòng)連結(jié)鏈聚類算法克服了其他聚類算法使用參數(shù)而對(duì)聚類結(jié)果及效率產(chǎn)生不良影響的問(wèn)題，在不需要輸入?yún)?shù)的情況下，通過(guò)引入自動(dòng)連結(jié)鏈的方法，增加了數(shù)據(jù)點(diǎn)的線性可分概率，即擴(kuò)大了數(shù)據(jù)類之間的差異，從而提高了聚類的質(zhì)量.實(shí)驗(yàn)表明，該算法與Single-Link聚類算法及DBSCAN聚類算法具有相同的聚類效果，但其執(zhí)行時(shí)間僅為這兩種算法的10%，大大節(jié)省了運(yùn)算時(shí)間.由于目前的研究只針對(duì)了二維數(shù)據(jù)樣本上的聚類實(shí)驗(yàn)，高維度以及其他形態(tài)的數(shù)據(jù)集有待今后進(jìn)一步地研究.

參考文獻(xiàn)：

[1]張曉偉.聚類算法及在搜索引擎系統(tǒng)中的應(yīng)用[D].哈爾濱：哈爾濱理工大學(xué)，2014.

[2]Mali U,Bandyopadhyay S. Genetic algorithm-based clustering technique[J]. Pattern Recognition,2000,33(9):1455-1465.

[3]王輝,張望,范明.基于集群環(huán)境的K-Means聚類算法的并行化[J].河南科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,29(4):42-45.

[4]趙玉艷,郭景峰,鄭麗珍,等.一種改進(jìn)的BIRCH分層聚類算法[J].計(jì)算機(jī)科學(xué),2008,35(3):180-183.

[5]熊忠陽(yáng),吳林敏,張玉芳.針對(duì)非均勻數(shù)據(jù)集的DBSCAN過(guò)濾式改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用研究,2009,26(10):3721-3723.

[6]Song B C,Ra J B. A fast search algorithm for vector quantization using L2-norm pyramid of codewords[J]. IEEE Transactions Image Processing,2002,59(11):10-15.

[7]Jim Z C Lai,Yi-Ching Liaw. Fast-searching algorithm for vector quantization using projection and triangular inequality[J]. IEEE Transactions Image Processing,2004,13(12):1554-1562.

[8]吳昌友,王福林,馬力.采用鏈路聚類的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法[J].西安交通大學(xué)學(xué)報(bào),2014，48(8):73-79.