一種不規(guī)則形狀聚類算法

謝夢(mèng)燕，黃旭，趙青，王俊輝

(湖州師范學(xué)院 信息工程學(xué)院，浙江 湖州 313000)

摘要：數(shù)據(jù)量的增長(zhǎng)、數(shù)據(jù)復(fù)雜性日益突出對(duì)數(shù)據(jù)分析提出了更高的挑戰(zhàn).針對(duì)不規(guī)則形狀分布的大規(guī)模數(shù)據(jù)，基于數(shù)據(jù)的本質(zhì)特征對(duì)簡(jiǎn)單聚類策略進(jìn)行研究，同時(shí)對(duì)采用并行方法提高分析效率進(jìn)行了思考.模擬實(shí)驗(yàn)表明，這種方法能夠有效識(shí)別復(fù)雜分布的類別邊界.

關(guān)鍵詞：聚類；不規(guī)則形狀；機(jī)器學(xué)習(xí)；數(shù)據(jù)分析;并行算法;共享信息素矩陣

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1008-5564(2015)03-0009-06

收稿日期：2015-02-10

作者簡(jiǎn)介：謝鳴鳳(1990—)，女，安徽宿州人，南京航空航天大學(xué)理學(xué)院數(shù)學(xué)系碩士研究生，主要從事偏微分方程研究.

A Clustering Algorithm for Irregular Distribution

XIE Meng-yan, HUANG Xu, ZHAO Qing, WANG Jun-hui

(School of Information Engineering, Huzhou Teachers College, Huzhou 313000, China)

Abstract：The growing prominence of data growth and data complexity propose more challenges for data analysis techniques. For the irregular distribution of large-scale data, study on a simple clustering strategy was carried out based on the essential characteristics of data, and thoughts on improving the efficiency of data analysis was conducted by using the parallel method in this paper. The simulation test results show that this approach can effectively identify category boundary of complex distributions.

Key words：clustering; irregular distribution； machine learning； data analysis; parallel algorithm; shared pheromone matrix

聚類是機(jī)器學(xué)習(xí)領(lǐng)域一項(xiàng)重要的基礎(chǔ)技術(shù)，是典型的無監(jiān)督學(xué)習(xí)方法，它能夠在目標(biāo)數(shù)據(jù)對(duì)象中發(fā)現(xiàn)令人感興趣的數(shù)據(jù)分布模式.聚類分析的算法可以分為劃分法(Partitioning Methods)[1-2]、層次法(Hierarchical Methods)、基于密度的方法(density-based methods)[3-4]、基于網(wǎng)格的方法(grid-based methods)[5]、基于模型的方法(Model-Based Methods)等等.目前已廣泛應(yīng)用于基因、蛋白質(zhì)等生物數(shù)據(jù)分析[6]，以及社會(huì)計(jì)算[7-8]、神經(jīng)解剖學(xué)分析、衛(wèi)星遙感影像分析、多傳感器數(shù)據(jù)融合等諸多領(lǐng)域.

聚類方法通過對(duì)目標(biāo)數(shù)據(jù)進(jìn)行深入分析，試圖挖掘出目標(biāo)數(shù)據(jù)集合的分布規(guī)律，并基于此規(guī)律整理數(shù)據(jù).而實(shí)際的數(shù)據(jù)集合分布往往具有復(fù)雜的子類邊界，聚類算法通過簡(jiǎn)化邊界的數(shù)學(xué)描述來提供一種聚類結(jié)果.這些簡(jiǎn)化的數(shù)學(xué)描述往往包含用來描述聚類半徑、密度的相關(guān)參數(shù)等等.由于聚類分析的復(fù)雜性，聚類算法需要在算法執(zhí)行速度以及類邊界描述與實(shí)際類邊界的擬合程度之間作出權(quán)衡.然而，對(duì)于一些分布規(guī)律極為復(fù)雜的數(shù)據(jù)集合，即使是在損失效率的前提下也很難獲得良好的聚類效果.

1不規(guī)則形狀聚類

呈現(xiàn)不規(guī)則分布的復(fù)雜數(shù)據(jù)集存在一些典型問題[9]，在空間拓?fù)潢P(guān)系上，包括數(shù)據(jù)子集的分離、鄰接、包含、覆蓋等情況；在子集密度問題上，包含不同子集之間的密度差異、同一子集之間密度差異兩種情況；在子集形態(tài)方面，又存在子集形狀多樣性與子集大小性等問題.對(duì)于這一類不規(guī)則形狀的聚類問題，需從兩個(gè)方面進(jìn)行研究，一是子類的刻畫參數(shù)，二是并行處理方法.

最簡(jiǎn)單的類的刻畫參數(shù)是聚類半徑，如常用于蛋白質(zhì)結(jié)構(gòu)聚類的QT算法[10].該算法基于簡(jiǎn)單的半徑這一概念對(duì)子集進(jìn)行劃分，通過簡(jiǎn)化聚類過程提高執(zhí)行速度.此外還有數(shù)據(jù)密度、元素間距離等參數(shù).基于相鄰元素距離的分析方法是識(shí)別復(fù)雜子類的基礎(chǔ).假設(shè)點(diǎn)xi是聚類Ck的成員，即：xi∈Ck.在這里用d表示距離函數(shù)，如果點(diǎn)xj與點(diǎn)xi之間的距離小于事先設(shè)定的閾值T，即d(xi,xj)

在實(shí)際數(shù)據(jù)集中，相同聚類的數(shù)據(jù)一般呈現(xiàn)不均勻分布，且體現(xiàn)為連續(xù)變化趨勢(shì).數(shù)據(jù)的不均勻增加了選擇T的難度，而連續(xù)變化趨勢(shì)則提供了解決的思路.為更準(zhǔn)確地刻畫子集，可將相鄰點(diǎn)的距離閾值用函數(shù)進(jìn)行描述.最簡(jiǎn)單的描述方式是閾值變化函數(shù)：δ(Tn,Tm).其中Tm、Tn是在遠(yuǎn)離聚類中心的方向上相鄰元素間的距離.δ是連續(xù)函數(shù).那么判斷相鄰的兩個(gè)數(shù)據(jù)點(diǎn)xk、xj是否屬于同一子集可采用以下式子：d(xj,xk)<δ·d(xi,xj).其中xi、xj、xk是在遠(yuǎn)離聚類中心的方向上連續(xù)相鄰的三個(gè)點(diǎn).當(dāng)上述式子不成立時(shí)，認(rèn)為xk點(diǎn)處出現(xiàn)較大梯度，進(jìn)而認(rèn)為xk不適合與前兩個(gè)點(diǎn)劃為同一子類.

圖1　基于相鄰點(diǎn)距離的類歸屬分析示意圖

更進(jìn)一步，為刻畫出δ的變化趨勢(shì)可采用函數(shù)λ(δ).仍然以梯度作為判斷一個(gè)點(diǎn)是否屬于該類的條件.

如果用y統(tǒng)一上述不同的分析層次，則基于相鄰點(diǎn)距離的類歸屬分析示意圖如圖1所示.

圖中曲線為距離閾值函數(shù)，xi、xj、xk分別表示在遠(yuǎn)離聚類中心的方向上連續(xù)相鄰的三個(gè)點(diǎn)，y1、y2、y2′是相鄰距離分析值，根據(jù)采用的分析函數(shù)，可分別表示T、δ、λ等.如果xk點(diǎn)在規(guī)定的閾值范圍內(nèi)，即符合距離分析函數(shù)，則會(huì)出現(xiàn)在曲線上，與上一相鄰點(diǎn)的距離為y2，否則不會(huì)出現(xiàn)在曲線上，與上一相鄰點(diǎn)的距離為y2′.此處將呈現(xiàn)明顯的梯度.

對(duì)于大規(guī)模數(shù)據(jù)，常采用并行算法提高聚類效率，目前采用MapReduce[11]方法成為一種趨勢(shì).在并行計(jì)算過程中，各并行體之間的信息交流是影響并行算法效率、需著重解決的問題.本文著重在共享全局類別歸屬信息的并行處理方法方面進(jìn)行了思考.在并行聚類過程中，一方面，各并行體執(zhí)行相同的操作，即從初始點(diǎn)出發(fā)，逐步分析相鄰點(diǎn)的類別屬性，試探著對(duì)相鄰點(diǎn)進(jìn)行類別劃分.另一方面，各并行體通過共享全局類別歸屬信息對(duì)各自的分析行為進(jìn)行指導(dǎo).

2算法描述

以基于相鄰元素距離的分析方法為例，不規(guī)則形狀聚類算法基本思路是:隨機(jī)選擇聚類起點(diǎn)，并從當(dāng)前處理類別開始標(biāo)記類別序號(hào)；分別從各起點(diǎn)開始遍歷所有點(diǎn)；將當(dāng)前點(diǎn)xj與已處理過的點(diǎn)xi計(jì)算距離，對(duì)于距離小于給定閾值的情況，如果點(diǎn)xj無類別，則將該點(diǎn)標(biāo)記為與xi的類別相同，否則，將與xi類別相同的所有點(diǎn)標(biāo)記為點(diǎn)xj的類別；如果所有已處理過的點(diǎn)與xj的距離均大于閾值，則將xj設(shè)置為新類別.具體分析流程如圖2所示.

圖2　數(shù)據(jù)分析流程

該流程反映了基于簡(jiǎn)單距離分析閾值T的情況.在該流程圖中，d(xi,xj)

共享全局類別歸屬信息的并行處理方法的瓶頸在于類別信息的存儲(chǔ)以及數(shù)據(jù)通訊.算法借鑒了采用共享信息素矩陣(Sharingonepheromonematrix,SHOP)策略蟻群算法的實(shí)現(xiàn)思路[12]，通過在內(nèi)存設(shè)置共享區(qū)域來存儲(chǔ)類別歸屬信息，數(shù)據(jù)通訊通過直接讀寫公共內(nèi)存特定區(qū)域?qū)崿F(xiàn).并行機(jī)制如圖3所示.

與SHOP不同，SHOP的信息素矩陣采用連續(xù)值對(duì)各蟻群行為進(jìn)行指導(dǎo)，而本算法共享區(qū)域存儲(chǔ)離散的類別歸屬，更易于實(shí)現(xiàn).在該并行機(jī)制中，各并行體從隨機(jī)起點(diǎn)開始執(zhí)行，并通過全局類別歸屬矩陣交流各點(diǎn)的類別信息.如果在一定時(shí)間內(nèi)所處理的各點(diǎn)類別信息均無改變，則認(rèn)為達(dá)到全局收斂狀態(tài)，退出并行體.

圖3　并行機(jī)制

圖4　聚類數(shù)據(jù)及結(jié)果

3實(shí)驗(yàn)與結(jié)果分析

本文用C++語言實(shí)現(xiàn)上述算法.實(shí)驗(yàn)在選定的二維數(shù)據(jù)集合上對(duì)算法進(jìn)行驗(yàn)證，并與K-means聚類算法[5，13]進(jìn)行比較.通過生成坐標(biāo)方式產(chǎn)生二維數(shù)據(jù)集合，記錄在文本文件中，每行記錄一個(gè)點(diǎn)的信息，采用“編號(hào)、X坐標(biāo)、Y坐標(biāo)”的形式.為簡(jiǎn)單起見，數(shù)據(jù)坐標(biāo)采用區(qū)間[0,30]中的整數(shù)，并通過調(diào)整坐標(biāo)值使數(shù)據(jù)點(diǎn)呈不規(guī)則分布.假定數(shù)據(jù)點(diǎn)在坐標(biāo)系中縱、橫、斜向相鄰為同一子類，有間隔為不同子類.然后在該數(shù)據(jù)集上分別運(yùn)行本文算法和K-means算法.本文重在驗(yàn)證上述方案對(duì)呈不規(guī)則分布的復(fù)雜數(shù)據(jù)是否有效，只運(yùn)行了單并行體.模擬數(shù)據(jù)在二維坐標(biāo)系中的位置視圖以及實(shí)驗(yàn)結(jié)果如圖4所示.

圖4中標(biāo)注了兩條曲線，其中實(shí)線為運(yùn)行本文算法的聚類分界線，虛線為運(yùn)行K-means算法的聚類分界線.本文算法子類間距離閾值取1.5，K-means算法初始類別數(shù)為2.實(shí)驗(yàn)結(jié)果表明，本文算法給出的結(jié)果更符合對(duì)模擬數(shù)據(jù)的聚類預(yù)期.通過實(shí)驗(yàn)，本文認(rèn)為K-means算法傾向于聚集更為緊湊、形狀更為規(guī)則的子集，即K-means算法對(duì)于聚集成團(tuán)的聚類更有效，而本文算法對(duì)不規(guī)則形狀聚類在子類邊界的細(xì)節(jié)把握上更為準(zhǔn)確.

4結(jié)語

數(shù)據(jù)量的飛速增長(zhǎng)促使以聚類為代表的數(shù)據(jù)分析方法受到空前關(guān)注，而大規(guī)模數(shù)據(jù)的分布規(guī)律也越來越呈現(xiàn)出高度復(fù)雜性，大大增加了數(shù)據(jù)分析難度.對(duì)于不規(guī)則形狀分布的大規(guī)模數(shù)據(jù)，本文基于數(shù)據(jù)的本質(zhì)特征對(duì)簡(jiǎn)單聚類策略進(jìn)行了分析，同時(shí)在并行方法方面進(jìn)行了一些思考.在此基礎(chǔ)上進(jìn)行了模擬實(shí)驗(yàn).實(shí)驗(yàn)表明，這種方法能夠有效識(shí)別復(fù)雜分布的類別邊界.下一步將深入研究數(shù)據(jù)邊界的復(fù)雜刻畫方法，嘗試復(fù)雜距離分析函數(shù)在算法中的應(yīng)用，同時(shí)進(jìn)一步優(yōu)化并行方案，提高聚類效率，并結(jié)合復(fù)雜數(shù)據(jù)的各類具體應(yīng)用作進(jìn)一步驗(yàn)證.

[參考文獻(xiàn)]

[1]蔣亦樟,鄧趙紅,王駿,等.基于知識(shí)利用的遷移學(xué)習(xí)一般化增強(qiáng)模糊劃分聚類算法[J].模式識(shí)別與人工智能,2013,26(10):975-984.

[2]殷君偉,陳建明,薛百里,等.一種基于排序劃分的聚類初始化方法[J].微電子學(xué)與計(jì)算機(jī),2013,30(6):80-83,87.

[3]武佳薇,李雄飛,孫濤,等.鄰域平衡密度聚類算法[J].計(jì)算機(jī)研究與發(fā)展,2010,47(6):1044-1052.

[4]鄭苗苗,吉根林.一種基于密度的分布式聚類算法[J].南京大學(xué)學(xué)報(bào),2008,44(5):536-543.

[5]張真,任賀宇.一種基于動(dòng)態(tài)網(wǎng)格技術(shù)的K‐means初始質(zhì)心選取算法[J].微電子學(xué)與計(jì)算機(jī),2013,30(6):101-104.

[6]高翠芳，吳小俊.復(fù)雜生物數(shù)據(jù)集的聚類數(shù)自動(dòng)確定方法[J].生物信息學(xué),2010,8(4):295-298.

[7]竇炳琳,李澍淞,張世永.基于結(jié)構(gòu)的社會(huì)網(wǎng)絡(luò)分析[J].計(jì)算機(jī)學(xué)報(bào),2012,35(4):741-753.

[8]朱牧,孟凡榮,周勇.基于鏈接密度聚類的重疊社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)研究與發(fā)展,2013,50(12):2520-2530.

[9]鄧敏,劉啟亮,李光強(qiáng),等.空間聚類分析及應(yīng)用[M].北京:科學(xué)出版社,2011.

[10]LAURIEJ.KRUGLYAKS,YOOSEPHS.Exploringexpressiondata:identiffcationandanalysisofcoexpressedgenes[J].GenomeResearch,1999,9:1106-1115.

[11]魯偉明,杜晨陽,魏寶剛,等.基于MapReduce的分布式近鄰傳播聚類算法[J].計(jì)算機(jī)研究與發(fā)展,2012,49(8):1762-1772.

[12]呂強(qiáng)，高彥明，錢培德.共享信息素矩陣：一種新的并行ACO方法[J].自動(dòng)化學(xué)報(bào),2007,33(4):418-421.

[13]高瀅,劉大有,齊紅,等.一種半監(jiān)督K均值多關(guān)系數(shù)據(jù)聚類算法[J].軟件學(xué)報(bào),2008,19(11):2814-2821.

[責(zé)任編輯王新奇]

Vol.18No.3Jul.2015