基于快速模擬退火的組合聚類算法

李紅，張志賓

（北京航空航天大學(xué) 經(jīng)濟(jì)管理學(xué)院，北京100083）

組合聚類旨在融合多個(gè)聚類結(jié)果以獲得比傳統(tǒng)聚類方法更好的樣本劃分。一方面，組合聚類相當(dāng)于基礎(chǔ)聚類結(jié)果的加權(quán)平均，對(duì)噪聲、孤立點(diǎn)和抽樣變化不敏感，且聚類不穩(wěn)定性能從組合分布中得到彌補(bǔ)，從而使組合聚類結(jié)果具有更好的魯棒性［1］；另一方面，組合聚類在搜索最優(yōu)解的過(guò)程中，有可能找到比所有基礎(chǔ)聚類都好的劃分結(jié)果，使組合聚類結(jié)果具有一定的新穎性。

近年來(lái)，國(guó)內(nèi)外學(xué)者提出了多種組合聚類實(shí)現(xiàn)模型，一般可分為如下幾類：圖／超圖劃分方法、協(xié)聯(lián)矩陣法、投票法、組合優(yōu)化法及啟發(fā)式求解等。

超圖劃分方法始于Strehl和Ghosh［2］的開創(chuàng)性工作，該研究設(shè)計(jì)并同時(shí)使用3種方法：CSPA（Cluster-based Sim ilarity Partitioning A lgorithm）、HGPA（Hyper Graph Partitioning Algorithm）和MCLA（Meta-Clustering A lgorithm），以返回最優(yōu)的組合聚類結(jié)果。隨后，若干學(xué)者對(duì)上述模型做了多方向擴(kuò)展，如Ayad［3］、Yang和Kamel［4］分別使用近鄰法和蟻群算法擴(kuò)展了CSPA模型。除超圖外，二分圖劃分、近鄰傳播等方法也被用于組合聚類研究［5-6］。

協(xié)聯(lián)矩陣法根據(jù)基礎(chǔ)聚類計(jì)算樣本之間的相似度或距離，生成協(xié)聯(lián)矩陣并在其上完成組合聚類。該方法最早由Fred和Jain［7］提出，其協(xié)聯(lián)矩陣由投票機(jī)制產(chǎn)生；Wang等［8］在生成協(xié)聯(lián)矩陣時(shí)進(jìn)一步考慮了簇的大小因素；Hu等［9］引入序貫三支決策方法來(lái)構(gòu)建協(xié)聯(lián)矩陣；Liu等［10］提出了基于協(xié)聯(lián)矩陣的譜聚類方法；Huang等［11］提出了局部加權(quán)的組合聚類策略。

投票法通過(guò)投票和重標(biāo)記策略獲取組合聚類結(jié)果。例如，Zhou和Tang［12］基于多種投票策略對(duì)基礎(chǔ)聚類進(jìn)行組合；Fu等［13］建立了模糊投票矩陣和多數(shù)仲裁者度量，并利用其獲取組合聚類結(jié)果；陳曉云和陳剛［14］提出了加權(quán)投票的聚類集成方法。

組合優(yōu)化法建立組合聚類目標(biāo)函數(shù)，通過(guò)優(yōu)化問(wèn)題求解，最大化組合聚類與基礎(chǔ)聚類集的相似性。由于全局最優(yōu)解搜索是一個(gè)NP-hard問(wèn)題，模擬退火［15］、因子圖［16］、最大期望（Expectation Maximization，EM）算法［17］等方法被用于求解近似最優(yōu)解。模擬退火是近似求解組合優(yōu)化問(wèn)題的經(jīng)典方法，被廣泛用于分類和聚類問(wèn)題［18-19］。Lu等［15］對(duì)模擬退火在組合聚類中的應(yīng)用進(jìn)行了探索，提出了標(biāo)簽變更時(shí)目標(biāo)函數(shù)的增量計(jì)算方法，但其標(biāo)簽變更采用了隨機(jī)選擇策略，算法收斂較慢。

無(wú)論何種方法，各基礎(chǔ)聚類獲得的樣本劃分結(jié)果都是組合聚類的重要先驗(yàn)信息。本文利用基礎(chǔ)聚類對(duì)樣本劃分的完全或部分一致性，構(gòu)建了基于投票的快速模擬退火（Rapid Simulated Annealing Based on Voting，BV-RSA）模型，該模型引入超點(diǎn)運(yùn)動(dòng)和投票箱機(jī)制來(lái)約束退火過(guò)程中的節(jié)點(diǎn)運(yùn)動(dòng)模式，實(shí)現(xiàn)組合聚類近似最優(yōu)解的快速搜索。

1 BV-RSA模型框架

給定數(shù)據(jù)樣本集X＝｛x1，x2，…，xn｝，一組基礎(chǔ)聚類集Π ＝｛π1，π2，…，πr｝，基礎(chǔ)聚類矩陣為Zn×r，矩陣元素zij為數(shù)據(jù)樣本xi在基礎(chǔ)聚類πj中的簇標(biāo)簽，組合聚類通常被形式化為如下的組合優(yōu)化問(wèn)題：

式中：U為衡量π和πi相似度的效用函數(shù)；wi為基礎(chǔ)聚類πi的權(quán)重。

BV-RSA模型解決式（1）組合優(yōu)化問(wèn)題的流程框架如圖1所示。

圖1 BV-RSA模型框架Fig.1 Framework of BV-RSA model

其基本思想是：以經(jīng)典模擬退火算法為基礎(chǔ)，引入超點(diǎn)運(yùn)動(dòng)和投票箱機(jī)制來(lái)約束節(jié)點(diǎn)運(yùn)動(dòng)模式，以加快退火過(guò)程中近似最優(yōu)解搜索。超點(diǎn)運(yùn)動(dòng)機(jī)制將基礎(chǔ)聚類中獲得完全一致性劃分的若干數(shù)據(jù)樣本定義為一個(gè)超點(diǎn)，并用超點(diǎn)取代其代表的樣本子集參與退火過(guò)程，從而控制它們保持退火運(yùn)動(dòng)一致性，以加速節(jié)點(diǎn)聚簇行為。投票箱機(jī)制利用基礎(chǔ)聚類對(duì)樣本劃分的部分一致性，為超點(diǎn)構(gòu)造投票箱，超點(diǎn)運(yùn)動(dòng)方向受投票箱約束，以適當(dāng)降低其標(biāo)簽變更的隨機(jī)性，從而加快退火過(guò)程。

在式（1）的優(yōu)化問(wèn)題中，BV-RSA模型對(duì)U沒(méi)有特殊要求，任何聚類評(píng)價(jià)的外部指標(biāo)都可作為模型的效用函數(shù)。與文獻(xiàn)［15］一樣，本文采用聚類比較的Rand Index作為效用函數(shù)，其計(jì)算式為

式中：ni為組合聚類第i個(gè)簇包含的樣本數(shù)量；為基礎(chǔ)聚類πq的第j個(gè)簇包含的樣本數(shù)量；為組合聚類第i個(gè)簇與πq的第j個(gè)簇包含的公共樣本數(shù)量。

2 超點(diǎn)和投票箱機(jī)制

2.1 超點(diǎn)和超點(diǎn)運(yùn)動(dòng)

通常，有相當(dāng)數(shù)量的數(shù)據(jù)樣本在基礎(chǔ)聚類中獲得了一致性劃分，這為組合聚類提供了先驗(yàn)信息。特別地，若2個(gè)數(shù)據(jù)樣本在所有基礎(chǔ)聚類中總是被劃分到同一簇中，則其具有must-link特性。must-link特性具有傳遞性，由此形成超點(diǎn)。

表1給出了12個(gè)數(shù)據(jù)樣本的3次基礎(chǔ)聚類結(jié)果及其超點(diǎn)劃分示例。

由超點(diǎn)定義可知，超點(diǎn)內(nèi)部的數(shù)據(jù)樣本在所有基礎(chǔ)聚類中具有一致的簇標(biāo)簽，在組合聚類中也應(yīng)被分配到同一個(gè)簇。BV-RSA模型用超點(diǎn)取代其內(nèi)部數(shù)據(jù)樣本參與退火過(guò)程，在降低樣本數(shù)量的同時(shí)，保障了超點(diǎn)內(nèi)部各樣本的簇標(biāo)簽始終保持一致，稱之為超點(diǎn)運(yùn)動(dòng)機(jī)制。

定義2不屬于任何超點(diǎn)的數(shù)據(jù)樣本被看作是特殊超點(diǎn)，稱之為平凡超點(diǎn)；而包含多個(gè)數(shù)據(jù)樣本的超點(diǎn)稱為非平凡超點(diǎn)。

表1 基礎(chǔ)聚類與超點(diǎn)示例Tab le 1 An exam p le of basic partition and super-objects

顯然，非平凡超點(diǎn)的基數(shù)大于1，平凡超點(diǎn)的基數(shù)等于1。由此，將模擬退火的運(yùn)動(dòng)主體統(tǒng)一為超點(diǎn)，基礎(chǔ)聚類矩陣Zn×r在去掉重復(fù)行后轉(zhuǎn)化為超點(diǎn)基礎(chǔ)聚類矩陣Ym×r。其中，m為平凡超點(diǎn)和非平凡超點(diǎn)的總數(shù)。

超點(diǎn)影響力與其基數(shù)正相關(guān)，因此退火過(guò)程的每次迭代將按超點(diǎn)基數(shù)的降序處理每個(gè)超點(diǎn)。由此，非平凡超點(diǎn)總是先于平凡超點(diǎn)被處理。

2.2 投票箱與標(biāo)簽選擇

在經(jīng)典模擬退火算法中，節(jié)點(diǎn)運(yùn)動(dòng)方向是隨機(jī)選擇的。對(duì)于組合聚類問(wèn)題，這意味著隨機(jī)變換數(shù)據(jù)樣本的簇標(biāo)簽，然后判斷該變更能否通過(guò)退火檢驗(yàn)。隨機(jī)標(biāo)簽選擇使退火過(guò)程難于控制：檢驗(yàn)閾值設(shè)置得高，則算法常結(jié)束于局部最優(yōu)解，聚類質(zhì)量低；檢驗(yàn)閾值設(shè)置得低，目標(biāo)函數(shù)可能在原地反復(fù)搖擺，算法收斂緩慢。BV-RSA模型基于基礎(chǔ)聚類對(duì)樣本劃分的部分一致性，采用投票箱和隨機(jī)選擇融合的方法確定超點(diǎn)運(yùn)動(dòng)方向。

定義3已知超點(diǎn)基礎(chǔ)聚類矩陣Ym×r＝［y1，y2，…，ym］T，設(shè)yu和yv為與超點(diǎn)Su和Sv對(duì)應(yīng)的矩陣行向量，則

在BV-RSA模型的退火過(guò)程中，當(dāng)前運(yùn)動(dòng)節(jié)點(diǎn)（設(shè)為超點(diǎn)Su）的標(biāo)簽選擇策略是：從Su的投票箱Bu中隨機(jī)選出一個(gè)節(jié)點(diǎn)Sv，將Sv在組合聚類當(dāng)前狀態(tài)下的簇標(biāo)簽作為Su擬變更的新標(biāo)簽。該策略將基礎(chǔ)聚類對(duì)樣本劃分的部分一致性作為約束節(jié)點(diǎn)運(yùn)動(dòng)方向的先驗(yàn)信息，同時(shí)保留了一定程度的算法隨機(jī)性。

3 BV-RSA模型的算法實(shí)現(xiàn)

3.1 算法描述

BV-RSA模型的具體實(shí)現(xiàn)算法描述如下，包括初始化和迭代退火2個(gè)子過(guò)程。

1）初始化過(guò)程

步驟1計(jì)算超點(diǎn)集合SS＝｛S1，S2，…，Sm｝，并按超點(diǎn)基數(shù)進(jìn)行排序。

步驟2對(duì)每個(gè)Su∈SS（u＝1，2，…，m），計(jì)算其投票箱Bu。

步驟3刪除Zn×r的重復(fù)行，獲得超點(diǎn)基礎(chǔ)聚類矩陣Ym×r。

步驟4按特定策略，初始化每個(gè)超點(diǎn)的簇標(biāo)簽，形成π的初值。

步驟5設(shè)置退火過(guò)程控制參數(shù)，包括：初始溫度T、溫度冷卻比C、變更接受閾值P0。

2）迭代退火過(guò)程

步驟1對(duì)每個(gè)超點(diǎn)Su∈SS（u＝1，2，…，m），執(zhí)行如下操作：①提取Su在π中的簇標(biāo)簽（設(shè)為i），即Lπ（Su）＝i；②從Su的投票箱Bu中隨機(jī)選出具有投票權(quán)的一個(gè)超點(diǎn)（設(shè)為Sv），提取Sv在π中的簇標(biāo)簽（設(shè)為i′），即Lπ（Sv）＝i′；③計(jì)算超點(diǎn)Su標(biāo)簽由i變?yōu)閕′引起的目標(biāo)函數(shù)值變化，若P（π（Su）：Lπ（Su）→i′）＞P0，則接受Su標(biāo)簽變更，令Lπ（Su）＝i′。

步驟2 若符合迭代結(jié)束條件，則算法結(jié)束；否則，令T＝T×C，重復(fù)退火過(guò)程的步驟1。

初始化過(guò)程主要完成3項(xiàng)工作：①計(jì)算超點(diǎn)集、超點(diǎn)投票箱和超點(diǎn)基礎(chǔ)劃分矩陣；②為退火過(guò)程設(shè)置控制參數(shù)；③按指定策略生成組合聚類的初始劃分，例如：為每個(gè)超點(diǎn)隨機(jī)分配簇標(biāo)簽（R策略），或隨機(jī)選擇一個(gè)基礎(chǔ)聚類（矩陣Ym×r的某一列）作為初始狀態(tài)（C策略）。

退火過(guò)程以迭代方式進(jìn)行，通過(guò)不斷改變超點(diǎn)簇標(biāo)簽，逐漸逼近組合聚類的近似最優(yōu)解。每次迭代過(guò)程分2個(gè)階段進(jìn)行：第1階段，對(duì)所有非平凡超點(diǎn)進(jìn)行標(biāo)簽選擇和變更檢驗(yàn)，處理順序按超點(diǎn)基數(shù)由大到小依次進(jìn)行；第2階段，處理所有平凡超點(diǎn)。當(dāng)目標(biāo)函數(shù)值不再發(fā)生變化或達(dá)到指定迭代次數(shù)時(shí)，退火過(guò)程結(jié)束。

3.2 退火檢驗(yàn)的增量計(jì)算

表2 實(shí)驗(yàn)數(shù)據(jù)集描述Table 2 Description of experim ental datasets

由式（6）和式（7）可導(dǎo)出h1和的更新計(jì)算方法如式（8）和式（9）所示。而只與基礎(chǔ)聚類相關(guān)，在退火檢驗(yàn)時(shí)不需要重新計(jì)算。

由式（2）、式（8）和式（9），可增量計(jì)算超點(diǎn)Su標(biāo)簽變化引起的目標(biāo)函數(shù)值變化。設(shè)Δτ為標(biāo)簽變更前后的目標(biāo)函數(shù)值差額，T為當(dāng)前退火溫度，若式（10）給出的P值大于檢驗(yàn)閾值P0，則接受Su的標(biāo)簽變更。

4 實(shí)驗(yàn)分析及模型應(yīng)用

4.1 數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置

本文選用如表2所示的15個(gè)公開數(shù)據(jù)集來(lái)檢驗(yàn)BV-RSA模型的有效性。

針對(duì)每個(gè)數(shù)據(jù)集，采用k-means算法生成50個(gè)基礎(chǔ)聚類，它們?cè)诮M合聚類目標(biāo)函數(shù)中采用均等權(quán)重，即wi＝0.02（i＝1，2，…，50）。模擬退火的初始狀態(tài)分別由R策略和C策略產(chǎn)生。除初始狀態(tài)外，其他控制參數(shù)分別為：標(biāo)簽變更檢驗(yàn)閾值P0＝0.8，初始溫度T＝0.05，溫度冷卻比C＝0.9。針對(duì)每個(gè)數(shù)據(jù)集，BV-RSA 模型運(yùn)行10次并取精度均值，分別與 CSPA、HGPA、MCLA［3］進(jìn)行比較。

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

表3給出了BV-RSA模型與基準(zhǔn)算法的精度比較。在全部15個(gè)數(shù)據(jù)集中，BV-RSA模型在10個(gè)數(shù)據(jù)集上獲得了最優(yōu)結(jié)果。CSPA算法在glass和reviews和tr12數(shù)據(jù)集結(jié)果最優(yōu)，但在有些數(shù)據(jù)集上效果不理想，特別是mnist數(shù)據(jù)集樣本點(diǎn)較多，CSPA算法沒(méi)有輸出結(jié)果。這是因?yàn)镃SPA算法對(duì)每個(gè)基礎(chǔ)聚類都需要計(jì)算一次相似度矩陣，在基礎(chǔ)聚類數(shù)量多、數(shù)據(jù)集規(guī)模大時(shí)，算法計(jì)算壓力和內(nèi)存開銷過(guò)高，較難適應(yīng)大數(shù)據(jù)集上的組合聚類任務(wù)。比較而言，MCLA 算法與BV-RSA模型的結(jié)果相近，但BV-RSA模型在大數(shù)據(jù)集letter和mnist上的表現(xiàn)更好一些。

在魯棒性方面，圖2給出了k1b數(shù)據(jù)集在不同基礎(chǔ)聚類數(shù)量的情況下，各模型的組合聚類準(zhǔn)確率的波動(dòng)情況。從圖2中可以看出：BV-RSA模型的C策略（BV-RSA／C）、BV-RSA模型的R策略（BV-RSA／R）和CSPA模型面對(duì)不同數(shù)量的基礎(chǔ)聚類時(shí)，表現(xiàn)出了相對(duì)穩(wěn)定的模型精度；而模型MCLA和HGPA則有一定程度的準(zhǔn)確率波動(dòng)。

表3 各模型聚類結(jié)果的精度比較Tab le 3 Com parison of clustering resu lt precision of d ifferen tm odels

4.3 網(wǎng)約車司機(jī)分群應(yīng)用

本文利用BV-RSA模型對(duì)某網(wǎng)約車平臺(tái)的司機(jī)脫敏數(shù)據(jù)進(jìn)行了分群應(yīng)用，以幫助該平臺(tái)強(qiáng)化司機(jī)細(xì)分管理，并在約車高峰時(shí)段輔助提高運(yùn)力調(diào)度的有效性。

本文采集了100 000條約車平司機(jī)信息及其2017年4月的接單數(shù)據(jù)作為模型輸入，輸入數(shù)據(jù)的具體格式如表4所示。k-means和BV-RSA組合聚類將網(wǎng)約車司機(jī)劃分為4個(gè)群體，各群體人數(shù)如圖3所示。

同時(shí)分析了各群體司機(jī)在不同時(shí)段的接單量分布。圖4和圖5分別給出了各類司機(jī)群體在工作日和周末的接單量分布，可以看出：與k-means方法相比，BV-RSA模型得到的各類司機(jī)群體，其群體內(nèi)部的接單量差異更小，表現(xiàn)出更好的內(nèi)聚性。同樣地，本文分析了各類司機(jī)群體在早高峰、晚高峰和常規(guī)時(shí)段的接單量分布，獲得了類似的分析結(jié)論，限于篇幅關(guān)系，不再一一贅述。

圖2 基礎(chǔ)聚類數(shù)量對(duì)模型精度的影響Fig.2 Impact of number of basic clusters on model precision

表4 輸入數(shù)據(jù)描述Tab le 4 Descrip tion of input data

圖3 k-means和BV-RSA模型的司機(jī)分群結(jié)果Fig.3 Driver grouping result obtained from k-means and BV-RSA model

圖5 各類司機(jī)群體的周末接單量分布Fig.5 Distribution of order quantity received by different driver groups on weekend

5 結(jié) 論

本文提出了BV-RSA模型，該模型的主要貢獻(xiàn)包括：

1）引入了超點(diǎn)運(yùn)動(dòng)機(jī)制，使?jié)M足完全一致性劃分條件的若干數(shù)據(jù)樣本以成組方式參與退火過(guò)程，在壓縮樣本空間的同時(shí)，加快了節(jié)點(diǎn)聚類速度。

2）對(duì)于每個(gè)超點(diǎn)，根據(jù)基礎(chǔ)劃分的部分一致性構(gòu)造其投票箱，超點(diǎn)運(yùn)動(dòng)的隨機(jī)性受投票箱約束。該機(jī)制保留了解空間搜索的部分隨機(jī)性，同時(shí)引入啟發(fā)信息加快模擬退火過(guò)程的收斂。

3）BV-RSA模型采用與文獻(xiàn)［15］同樣的效用函數(shù)，推導(dǎo)了超點(diǎn)運(yùn)動(dòng)引起效用函數(shù)變化的增量計(jì)算方法，降低了模擬退火檢驗(yàn)的計(jì)算開銷。

15個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)表明，BV-RSA模型在10個(gè)數(shù)據(jù)集上獲得了最優(yōu)結(jié)果，且模型精度對(duì)基礎(chǔ)聚類數(shù)量的變化不敏感，表現(xiàn)出良好的魯棒性。

在后續(xù)研究中，將進(jìn)一步設(shè)計(jì)BV-RSA模型的并行計(jì)算方案，拓寬其在大數(shù)據(jù)集上的應(yīng)用。