一種基于變鄰域搜索的啟發(fā)式聚類算法

金 萍，陳家俊，徐華麗

（皖西學(xué)院信息工程學(xué)院，安徽 六安237012）

0 引言

聚類分析是數(shù)據(jù)挖掘的重要任務(wù)，是一種典型的無監(jiān)督學(xué)習(xí)方法，成為對(duì)數(shù)據(jù)進(jìn)行合理歸類的重要手段［1-2］。聚類是根據(jù)數(shù)據(jù)的某些屬性，按照預(yù)先定義的相似度將數(shù)據(jù)劃分成若干類，并最大化類內(nèi)數(shù)據(jù)對(duì)象的相似性，而最小化類間數(shù)據(jù)對(duì)象的相似性，以發(fā)現(xiàn)數(shù)據(jù)中隱藏的有用信息。直到目前為止還沒有相關(guān)文獻(xiàn)給出聚類的統(tǒng)一定義。基于不同的應(yīng)用目的，研究者們采用不同的模型定義聚類問題。本文研究以組合優(yōu)化模型定義的聚類問題，它是求解數(shù)值型數(shù)據(jù)聚類的重要方法，有著廣泛的應(yīng)用背景。

所有可能的M集合就構(gòu)成了該類聚類問題的搜索空間CX，窮舉CX中的每個(gè)結(jié)果就能獲得最優(yōu)聚類結(jié)果。文獻(xiàn)［3］已經(jīng)證明，即使在K＝2的情況下，該聚類問題也是NP-難解的，即不存在多項(xiàng)式時(shí)間的精確算法能求得聚類問題的全局最優(yōu)解。研究者們往往采用能在較短時(shí)間內(nèi)獲得可接受解的啟發(fā)式搜索（heuristic search）方法來求解該類聚類問題，并設(shè)計(jì)了經(jīng)典啟發(fā)式聚類算法，如K-means［1］、K-mediods［2］、PAM［4］及CLARANS［5］等。圖1給出了啟發(fā)式聚類算法的搜索示意圖。從圖1中可以看出，初始解A和初始解B引導(dǎo)算法收斂于不同質(zhì)量的聚類結(jié)果。這說明啟發(fā)式聚類算法對(duì)初始解十分敏感。

變鄰域搜索在搜索過程中，通過系統(tǒng)地改變鄰域結(jié)構(gòu)來拓展搜索范圍，獲得局部最優(yōu)解，再基于已獲得局部最優(yōu)解重新系統(tǒng)地改變鄰域結(jié)構(gòu)擴(kuò)展搜索范圍，以尋求另一個(gè)局部最優(yōu)解。由于變鄰域在搜索過程中不斷地重構(gòu)搜索鄰域，有效地避免了局部最優(yōu)解的困擾，能很好地提高搜索算法的質(zhì)量。

圖1 啟發(fā)式聚類算法搜索空間示意圖

本文引入變鄰域搜索技術(shù)改進(jìn)現(xiàn)有啟發(fā)式聚類算法初始解敏感問題，給出了一種基于變鄰域搜索的啟發(fā)式聚類算法HC＿VNS（Heuristic Clustering Algorithm based on Variable Neighborhood Search）。該算法：（1）從給定數(shù)據(jù)D中選取K 個(gè)數(shù)據(jù)對(duì)象構(gòu)成初始解Morg；（2）對(duì)于初始解Morg中的每個(gè)中心點(diǎn)，從數(shù)據(jù)集D-Morg中選擇其KN個(gè)最近鄰居，構(gòu)造與其對(duì)應(yīng)的可變搜索鄰域VNS；（3）以初始解Morg為搜索起點(diǎn)，引導(dǎo)啟發(fā)式聚類算法在VNS中搜索新的聚類中心Mlocal；（4）如果Mlocal優(yōu)于Morg，則用Mlocal替換Morg，并迭代執(zhí)行（2）～（3）直到達(dá)到預(yù)定目標(biāo)，否則，繼續(xù)在VNS中搜索聚類結(jié)果Mlocal；（5）依據(jù)產(chǎn)生的中心點(diǎn)集合，將D中剩余數(shù)據(jù)對(duì)象分配到與其最近中心點(diǎn)所表示的簇中，產(chǎn)生最終聚類結(jié)果C。實(shí)驗(yàn)結(jié)果表明，變鄰域搜索對(duì)提高啟發(fā)式聚類算法質(zhì)量非常有效。

本文的組織結(jié)構(gòu)如下：第1節(jié)介紹本文背景知識(shí)；第2節(jié)介紹基于變鄰域搜索的啟發(fā)式聚類算法框架；第3節(jié)給出了實(shí)驗(yàn)及實(shí)驗(yàn)結(jié)果分析；最后總結(jié)全文。

1 背景知識(shí)

給定包含N個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集D＝｛x1，…，xi，…，xN｝和任意聚類中心點(diǎn)集合M，其最近鄰居和可變鄰域的構(gòu)造方法描述如下。

定義1 給定數(shù)據(jù)集D和聚類中心點(diǎn)集合M＝｛m1，…，mk，…，mK｝，則mk∈M 的KN 個(gè)最近鄰居定義為：

其中xi∈D-M，σ為閥值參數(shù)，用于選擇KN個(gè)最近鄰居，“-”為集合減運(yùn)算。

定義2 給定數(shù)據(jù)集D和聚類中心點(diǎn)集合M，M的可變搜索鄰域VNS定義為：

定義3 給定數(shù)據(jù)集D，初始解（即K個(gè)聚類中心點(diǎn)）Morg及其對(duì)應(yīng)的可變搜索鄰域VNS，啟發(fā)式聚類算法HC＿VNS的聚類結(jié)果定義為：

其中C（mk）是以mk為中心的聚類。

2 基于變鄰域搜索的啟發(fā)式聚類算法框架

本節(jié)介紹基于變鄰域搜索的啟發(fā)式聚類算法HC＿VNS算法框架及時(shí)間復(fù)雜度分析。

2．1 HC＿VNS算法框架

算法1 HC＿VNS

輸入：數(shù)據(jù)集D，聚類個(gè)數(shù)K

輸出：聚類結(jié)果C

（1）從數(shù)據(jù)集D中任選K 個(gè)數(shù)據(jù)對(duì)象構(gòu)成初始中心點(diǎn)Morg；

（2）for（p＝1；p＜＝P；p＋＋）

（a）根據(jù)定義1～2，構(gòu)造 Morg的可變搜索鄰域VNSorg；

（b）以Morg為搜索起點(diǎn)，調(diào)用現(xiàn)有啟發(fā)式聚類算法在VNSorg中搜索新的聚類中心Mlocal；

（c）如果Mlocal優(yōu)于Morg，則 Morg←Mlocal；

否則繼續(xù)在VNSorg中搜索新的Mlocal；

（3）以步驟（2）產(chǎn)生的Morg聚類中心，將數(shù)據(jù)集D數(shù)據(jù)對(duì)象分配給與其最近的聚類中心，產(chǎn)生聚類結(jié)果C＝｛Cm1，…，Cmk，…，CmK｝；

（4）返回聚類結(jié)果C。

算法1給出了HC＿VNS算法框架。該算法主要包含3個(gè)步驟：選擇初始解、迭代構(gòu)造可變搜索鄰域和啟發(fā)式聚類。HC＿VNS算法的具體步驟：（1）從給定數(shù)據(jù)D中選取K個(gè)數(shù)據(jù)對(duì)象構(gòu)成初始解Morg（聚類中心點(diǎn)）；（2）對(duì)于初始解Morg中的每個(gè)中心點(diǎn)mk∈M org，k＝1，…，K，從數(shù)據(jù)集D-Morg中選擇mk的KN 個(gè)最近鄰N（mk）＝｛xi｝，構(gòu)造可變搜索鄰域VNSogr＝｛N（m1），…，N（mk），…，N（mK）｝；（3）以初始解Morg為搜索起點(diǎn)，引導(dǎo)啟發(fā)式聚類算法在VNSorg中搜索聚類中心Mlocal；（4）如果 Mlocal優(yōu)于Morg，則Morg←Mlocal，并迭代執(zhí)行（2）～（3）直到達(dá)到預(yù)定目標(biāo)，否則，繼續(xù)在VNSorg中搜索聚類結(jié)果Mlocal。最后將D中剩余數(shù)據(jù)對(duì)象分配給與其最近的聚類中心，產(chǎn)生聚類結(jié)果C。

2．2 時(shí)間復(fù)雜度分析

算法HC＿VNS的時(shí)間消耗主要集中在可變鄰域構(gòu)造與啟發(fā)式搜索2個(gè)部分。對(duì)于任意給定的數(shù)據(jù)集D，dist（）函數(shù)采用歐幾里德距離，算法可先計(jì)算每個(gè)數(shù)據(jù)對(duì)象的相似度，耗時(shí)O（N2），其后可直接依據(jù)該相似度構(gòu)建可變鄰域。步驟（a）對(duì)Morg中的每個(gè)數(shù)據(jù)對(duì)象，選擇與其最近的KN個(gè)鄰居，構(gòu)造可變搜索鄰域VNSorg，需耗時(shí)O（K＊KN）。步驟（b）以Morg為搜索起點(diǎn)，調(diào)用現(xiàn)有啟發(fā)式聚類算法在VNSorg中搜索新的聚類中心，其耗時(shí)與調(diào)用算法及VNSorg的規(guī)模有關(guān)。現(xiàn)有的啟發(fā)式聚類算法中K-means算法時(shí)間消耗與VNSorg的規(guī)模呈線性關(guān)系，而其它算法如PAM、K-medoids和CLARANS算法的時(shí)間消耗與VNSorg規(guī)模呈平方關(guān)系，即步驟（b）的時(shí)間消耗最多為O（K＊KN2）。步驟（2）通過P次迭代執(zhí)行可變鄰域構(gòu)建與啟發(fā)式搜索，以完成搜索更優(yōu)聚類中心的目的，其時(shí)間復(fù)雜度為O（P＊K＊KN2）。步驟（3）將數(shù)據(jù)集D的N 個(gè)數(shù)據(jù)對(duì)象分配給與其最近的聚類中心，產(chǎn)生聚類結(jié)果C，其時(shí)間消耗最多為O（K＊N）。

綜上所述，算法HC＿VNS的總消耗為：O（N2＋P＊（（K＋1）＊KN＋P＊K＊KN）2），其中相似度計(jì)算步驟通?？梢栽陬A(yù)處理階段完成，因此本文提出的算法時(shí)間消耗為O（P＊（（K＋1）＊KN＋P＊K＊KN2））。

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

3．3 性能評(píng)價(jià)標(biāo)準(zhǔn)

本文使用文獻(xiàn)［6］給出了一種兼顧簇內(nèi)相似性與簇間相異性的內(nèi)部質(zhì)量衡量方式來評(píng)價(jià)HC＿VNS算法性能。

3．2 實(shí)驗(yàn)結(jié)果

根據(jù)上述算法實(shí)現(xiàn)步驟，進(jìn)行實(shí)驗(yàn)仿真：實(shí)驗(yàn)平臺(tái)采用Intel Core I5 3．3GHz CPU＼4G 內(nèi)存計(jì)算機(jī)，在Windows XP環(huán)境下用Matlab7．5實(shí)現(xiàn)算法HC＿VNS以 及 對(duì) 比 算 法 K-means、NHCA［7］、CIGC［8］、ABRAC［9］。算法NHCA采用噪聲法重構(gòu)搜索空間，降低局部最優(yōu)解對(duì)啟發(fā)式聚類算法的影響。算法CIGC采用共有信息構(gòu)建初始解，引導(dǎo)啟發(fā)式聚類算法在解空間進(jìn)行搜索。而ABRAC算法則引入近似骨架概念設(shè)計(jì)新的啟發(fā)式聚類算法，提高聚類質(zhì)量。這3個(gè)改進(jìn)的啟發(fā)式聚類算法被成功地應(yīng)用于標(biāo)注挖掘［10-11］，不確定數(shù)據(jù)挖掘［12］，推薦系統(tǒng)［13］等領(lǐng)域。

本文分別在1個(gè)人工實(shí)驗(yàn)數(shù)據(jù)集和5個(gè)經(jīng)典的真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。

（1）人工實(shí)驗(yàn)數(shù)據(jù)集

因?yàn)橥ㄟ^比較輸入數(shù)據(jù)與輸出數(shù)據(jù)，可以更精確地評(píng)價(jià)聚類結(jié)果，本文首先在人工實(shí)驗(yàn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。表1給出了人工數(shù)據(jù)集Dataset1的基本情況。

表1 Dataset1

圖2給出了算法HC＿VNS及其對(duì)比算法K-means、NHCA、CIGC和ABRA在Dataset1上的實(shí)驗(yàn)對(duì)比結(jié)果。從圖中可以看出，經(jīng)典啟發(fā)式聚類算法K-means獲得的Q（C）值明顯高于其它對(duì)比算法，這說明K-means算法受到局部最優(yōu)解的影響很大。算法NHCA采用噪聲平滑技術(shù)“填平”搜索空間中的局部最優(yōu)解“陷阱”，降低啟發(fā)式聚類算法過早收斂概率，提高聚類質(zhì)量，因此該算法的質(zhì)量要明顯優(yōu)于K-means算法質(zhì)量。CIGC算法利用多個(gè)局部最優(yōu)解的共同信息，產(chǎn)生優(yōu)化的初始解，并以此初始解來引導(dǎo)啟發(fā)式聚類算法收斂于更優(yōu)結(jié)果。ABRA算法則利用局部最優(yōu)解和全局最優(yōu)解分布的“大坑”特征，引入骨架概念設(shè)計(jì)啟發(fā)式聚類算法。NHCA、CIGC、ABRA和HC＿VNS都采用了不同的優(yōu)化技術(shù)來避免局部最優(yōu)解對(duì)算法的影響，從而達(dá)到提高聚類質(zhì)量的目的。

圖2 5種對(duì)比算法在Dataset1上的實(shí)驗(yàn)結(jié)果

為了比較5種算法的效率，本文在數(shù)據(jù)集Dataset1上運(yùn)行對(duì)比算法，獲得的時(shí)間消耗如圖3所示。從圖中可以看出K-means算法基本與數(shù)據(jù)集的規(guī)模呈線性增長(zhǎng)關(guān)系，而其它優(yōu)化算法NHCA、CIGC和ABRA則幾乎呈平方量級(jí)增加。造成這個(gè)現(xiàn)象的原因是：優(yōu)化算法NHCA、CIGC和ABRA需要在數(shù)據(jù)集D上多次運(yùn)行啟發(fā)式聚類算法獲得局部最優(yōu)解，然后采用不同的優(yōu)化策略進(jìn)行算法質(zhì)量改進(jìn)，因此耗時(shí)較大。HC＿NVS的時(shí)間消耗比K-means算法還要低一些，這是因?yàn)镠C＿NVS每次進(jìn)行變鄰域重構(gòu)和啟發(fā)式搜索都是在數(shù)據(jù)對(duì)象的KN個(gè)鄰居中進(jìn)行，因此大大減少了時(shí)間消耗。

圖3 5種對(duì)比算法在Dataset1上的時(shí)間消耗對(duì)比

（2）實(shí)際數(shù)據(jù)集

為了驗(yàn)證算法HC＿VNS處理實(shí)際數(shù)據(jù)集的能力，本文從http：／／archive．ics．uci．edu／ml／datasets．html網(wǎng)站上下載了5個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集描述如表2所示。表2所示數(shù)據(jù)集包含規(guī)模、屬性和簇3個(gè)屬性，分別表示該數(shù)據(jù)集包含數(shù)據(jù)對(duì)象個(gè)數(shù)，數(shù)據(jù)對(duì)象的屬性個(gè)數(shù)以及該數(shù)據(jù)集包含的聚類個(gè)數(shù)。每個(gè)數(shù)據(jù)集屬性取值都是實(shí)數(shù)或整數(shù)。

表2 真實(shí)數(shù)據(jù)集

圖4給出了5種對(duì)比算法在5個(gè)實(shí)際數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。本文提出的HC＿VNS和改進(jìn)的啟發(fā)式聚類算法NHCA、CIGC、ABRA都能較好地處理真實(shí)數(shù)據(jù)，獲得較高質(zhì)量的聚類結(jié)果，明顯優(yōu)于傳統(tǒng)聚類算法K-means的聚類結(jié)果。但是在數(shù)據(jù)集BC、PRHD、CBD以及QM上的聚類結(jié)果不是太好，造成這個(gè)現(xiàn)象的原因是隨著數(shù)據(jù)維度的不斷增加，相似度的誤差越來越大，影響了啟發(fā)式聚類算法的效果。

圖4 5種對(duì)比算法在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

4 結(jié)語(yǔ)

本文利用可變鄰域搜索的優(yōu)點(diǎn)，設(shè)計(jì)了一種基于可變鄰域搜索的啟發(fā)式聚類算法，給出了算法框架，并分別在人工數(shù)據(jù)集和實(shí)際數(shù)據(jù)集上驗(yàn)證了算法的效率和效果。實(shí)驗(yàn)結(jié)果表明，可變鄰域搜索對(duì)提高啟發(fā)式聚類算法質(zhì)量十分有效。

［1］Maimon O．，Rokach L．Data Mining and Knowledge Discovery Handbood［M］．Spring，2010．

［2］孫吉貴，劉杰，趙連宇．聚類算法研究［J］．軟件學(xué)報(bào)，2008，19（1）：48-61．

［3］Drinesa P．，F(xiàn)rieze A．，Kannan R．Clustering Large Graphs Via the Singular Value Decomposition［J］．Machine Learning，2004，56（1-3）：9-33．

［4］Kaufman L．，Rousseeuw P．J．Finding Groups in Data：an Introduction to Cluster Analysis［M］．John Wiley ＆Sons，1990．

［5］Ng R．，Han J．CLARANS：A Method for Clustering Objects for Spatial Data Mining．IEEE Trans on Knowledge and Data Engineering［J］，2002，14（5）：1003-1016．

［6］宗瑜，江賀，張憲超，等．空間平滑搜索CLARANS算法．小型微型計(jì)算機(jī)系統(tǒng)［J］．2008，29（4）：667-671．

［7］金萍，宗瑜，李明楚．一種噪聲啟發(fā)式聚類算法［J］．合肥工業(yè)大學(xué)學(xué)報(bào)，2009，32（6）：786-790．

［8］金萍，宗瑜，李明楚．共有信息導(dǎo)向的啟發(fā)式聚類算法［J］．計(jì)算機(jī)工程與應(yīng)用，2010，46（31）：50-53．

［9］宗瑜，江賀，李明楚．近似骨架導(dǎo)向的歸約聚類算法［J］．電子與信息學(xué)報(bào)，2009，31（12）：2953-2957．（EI檢索）

［10］Xu G．D．，Zong Y．，Jin P．，et al．KIPTC：a Kernel Information Propagation Tag Clustering Algorithm［J］．Journal of Intelligent Information System，2015，45（1）：95-112．

［11］Rong P．，Xu G．D．，Peter D．，et al．Group Division for Recommendation in Tag-Based Systems［C］．CGC 2012：399-404．

［12］金萍，宗瑜，曲世超，等．面向不確定數(shù)據(jù)的近似骨架啟發(fā)式搜索算法［J］．南京大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，1（51）：197-205．

［13］Li X．，Xu G．D．，Chen E．H．，Zong Y．Learning Recency Based Comparative Choice towards Point-of-interest Recommendation［J］．Expert System and Application，2015，42（9）：4274-4283．