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

李紅，張志賓

（北京航空航天大學 經濟管理學院，北京100083）

組合聚類旨在融合多個聚類結果以獲得比傳統聚類方法更好的樣本劃分。一方面，組合聚類相當于基礎聚類結果的加權平均，對噪聲、孤立點和抽樣變化不敏感，且聚類不穩定性能從組合分布中得到彌補，從而使組合聚類結果具有更好的魯棒性［1］；另一方面，組合聚類在搜索最優解的過程中，有可能找到比所有基礎聚類都好的劃分結果，使組合聚類結果具有一定的新穎性。

近年來，國內外學者提出了多種組合聚類實現模型，一般可分為如下幾類：圖／超圖劃分方法、協聯矩陣法、投票法、組合優化法及啟發式求解等。

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

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

投票法通過投票和重標記策略獲取組合聚類結果。例如，Zhou和Tang［12］基于多種投票策略對基礎聚類進行組合；Fu等［13］建立了模糊投票矩陣和多數仲裁者度量，并利用其獲取組合聚類結果；陳曉云和陳剛［14］提出了加權投票的聚類集成方法。

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

無論何種方法，各基礎聚類獲得的樣本劃分結果都是組合聚類的重要先驗信息。本文利用基礎聚類對樣本劃分的完全或部分一致性，構建了基于投票的快速模擬退火（Rapid Simulated Annealing Based on Voting，BV-RSA）模型，該模型引入超點運動和投票箱機制來約束退火過程中的節點運動模式，實現組合聚類近似最優解的快速搜索。

1 BV-RSA模型框架

給定數據樣本集X＝｛x1，x2，…，xn｝，一組基礎聚類集Π ＝｛π1，π2，…，πr｝，基礎聚類矩陣為Zn×r，矩陣元素zij為數據樣本xi在基礎聚類πj中的簇標簽，組合聚類通常被形式化為如下的組合優化問題：

式中：U為衡量π和πi相似度的效用函數；wi為基礎聚類πi的權重。

BV-RSA模型解決式（1）組合優化問題的流程框架如圖1所示。

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

其基本思想是：以經典模擬退火算法為基礎，引入超點運動和投票箱機制來約束節點運動模式，以加快退火過程中近似最優解搜索。超點運動機制將基礎聚類中獲得完全一致性劃分的若干數據樣本定義為一個超點，并用超點取代其代表的樣本子集參與退火過程，從而控制它們保持退火運動一致性，以加速節點聚簇行為。投票箱機制利用基礎聚類對樣本劃分的部分一致性，為超點構造投票箱，超點運動方向受投票箱約束，以適當降低其標簽變更的隨機性，從而加快退火過程。

在式（1）的優化問題中，BV-RSA模型對U沒有特殊要求，任何聚類評價的外部指標都可作為模型的效用函數。與文獻［15］一樣，本文采用聚類比較的Rand Index作為效用函數，其計算式為

式中：ni為組合聚類第i個簇包含的樣本數量；為基礎聚類πq的第j個簇包含的樣本數量；為組合聚類第i個簇與πq的第j個簇包含的公共樣本數量。

2 超點和投票箱機制

2.1 超點和超點運動

通常，有相當數量的數據樣本在基礎聚類中獲得了一致性劃分，這為組合聚類提供了先驗信息。特別地，若2個數據樣本在所有基礎聚類中總是被劃分到同一簇中，則其具有must-link特性。must-link特性具有傳遞性，由此形成超點。

表1給出了12個數據樣本的3次基礎聚類結果及其超點劃分示例。

由超點定義可知，超點內部的數據樣本在所有基礎聚類中具有一致的簇標簽，在組合聚類中也應被分配到同一個簇。BV-RSA模型用超點取代其內部數據樣本參與退火過程，在降低樣本數量的同時，保障了超點內部各樣本的簇標簽始終保持一致，稱之為超點運動機制。

定義2不屬于任何超點的數據樣本被看作是特殊超點，稱之為平凡超點；而包含多個數據樣本的超點稱為非平凡超點。

表1 基礎聚類與超點示例Tab le 1 An exam p le of basic partition and super-objects

顯然，非平凡超點的基數大于1，平凡超點的基數等于1。由此，將模擬退火的運動主體統一為超點，基礎聚類矩陣Zn×r在去掉重復行后轉化為超點基礎聚類矩陣Ym×r。其中，m為平凡超點和非平凡超點的總數。

超點影響力與其基數正相關，因此退火過程的每次迭代將按超點基數的降序處理每個超點。由此，非平凡超點總是先于平凡超點被處理。

2.2 投票箱與標簽選擇

在經典模擬退火算法中，節點運動方向是隨機選擇的。對于組合聚類問題，這意味著隨機變換數據樣本的簇標簽，然后判斷該變更能否通過退火檢驗。隨機標簽選擇使退火過程難于控制：檢驗閾值設置得高，則算法常結束于局部最優解，聚類質量低；檢驗閾值設置得低，目標函數可能在原地反復搖擺，算法收斂緩慢。BV-RSA模型基于基礎聚類對樣本劃分的部分一致性，采用投票箱和隨機選擇融合的方法確定超點運動方向。

定義3已知超點基礎聚類矩陣Ym×r＝［y1，y2，…，ym］T，設yu和yv為與超點Su和Sv對應的矩陣行向量，則

在BV-RSA模型的退火過程中，當前運動節點（設為超點Su）的標簽選擇策略是：從Su的投票箱Bu中隨機選出一個節點Sv，將Sv在組合聚類當前狀態下的簇標簽作為Su擬變更的新標簽。該策略將基礎聚類對樣本劃分的部分一致性作為約束節點運動方向的先驗信息，同時保留了一定程度的算法隨機性。

3 BV-RSA模型的算法實現

3.1 算法描述

BV-RSA模型的具體實現算法描述如下，包括初始化和迭代退火2個子過程。

1）初始化過程

步驟1計算超點集合SS＝｛S1，S2，…，Sm｝，并按超點基數進行排序。

步驟2對每個Su∈SS（u＝1，2，…，m），計算其投票箱Bu。

步驟3刪除Zn×r的重復行，獲得超點基礎聚類矩陣Ym×r。

步驟4按特定策略，初始化每個超點的簇標簽，形成π的初值。

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

2）迭代退火過程

步驟1對每個超點Su∈SS（u＝1，2，…，m），執行如下操作：①提取Su在π中的簇標簽（設為i），即Lπ（Su）＝i；②從Su的投票箱Bu中隨機選出具有投票權的一個超點（設為Sv），提取Sv在π中的簇標簽（設為i′），即Lπ（Sv）＝i′；③計算超點Su標簽由i變為i′引起的目標函數值變化，若P（π（Su）：Lπ（Su）→i′）＞P0，則接受Su標簽變更，令Lπ（Su）＝i′。

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

初始化過程主要完成3項工作：①計算超點集、超點投票箱和超點基礎劃分矩陣；②為退火過程設置控制參數；③按指定策略生成組合聚類的初始劃分，例如：為每個超點隨機分配簇標簽（R策略），或隨機選擇一個基礎聚類（矩陣Ym×r的某一列）作為初始狀態（C策略）。

退火過程以迭代方式進行，通過不斷改變超點簇標簽，逐漸逼近組合聚類的近似最優解。每次迭代過程分2個階段進行：第1階段，對所有非平凡超點進行標簽選擇和變更檢驗，處理順序按超點基數由大到小依次進行；第2階段，處理所有平凡超點。當目標函數值不再發生變化或達到指定迭代次數時，退火過程結束。

3.2 退火檢驗的增量計算

表2 實驗數據集描述Table 2 Description of experim ental datasets

由式（6）和式（7）可導出h1和的更新計算方法如式（8）和式（9）所示。而只與基礎聚類相關，在退火檢驗時不需要重新計算。

由式（2）、式（8）和式（9），可增量計算超點Su標簽變化引起的目標函數值變化。設Δτ為標簽變更前后的目標函數值差額，T為當前退火溫度，若式（10）給出的P值大于檢驗閾值P0，則接受Su的標簽變更。

4 實驗分析及模型應用

4.1 數據集和實驗設置

本文選用如表2所示的15個公開數據集來檢驗BV-RSA模型的有效性。

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

4.2 實驗結果分析

表3給出了BV-RSA模型與基準算法的精度比較。在全部15個數據集中，BV-RSA模型在10個數據集上獲得了最優結果。CSPA算法在glass和reviews和tr12數據集結果最優，但在有些數據集上效果不理想，特別是mnist數據集樣本點較多，CSPA算法沒有輸出結果。這是因為CSPA算法對每個基礎聚類都需要計算一次相似度矩陣，在基礎聚類數量多、數據集規模大時，算法計算壓力和內存開銷過高，較難適應大數據集上的組合聚類任務。比較而言，MCLA 算法與BV-RSA模型的結果相近，但BV-RSA模型在大數據集letter和mnist上的表現更好一些。

在魯棒性方面，圖2給出了k1b數據集在不同基礎聚類數量的情況下，各模型的組合聚類準確率的波動情況。從圖2中可以看出：BV-RSA模型的C策略（BV-RSA／C）、BV-RSA模型的R策略（BV-RSA／R）和CSPA模型面對不同數量的基礎聚類時，表現出了相對穩定的模型精度；而模型MCLA和HGPA則有一定程度的準確率波動。

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

4.3 網約車司機分群應用

本文利用BV-RSA模型對某網約車平臺的司機脫敏數據進行了分群應用，以幫助該平臺強化司機細分管理，并在約車高峰時段輔助提高運力調度的有效性。

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

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

圖2 基礎聚類數量對模型精度的影響Fig.2 Impact of number of basic clusters on model precision

表4 輸入數據描述Tab le 4 Descrip tion of input data

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

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

5 結 論

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

1）引入了超點運動機制，使滿足完全一致性劃分條件的若干數據樣本以成組方式參與退火過程，在壓縮樣本空間的同時，加快了節點聚類速度。

2）對于每個超點，根據基礎劃分的部分一致性構造其投票箱，超點運動的隨機性受投票箱約束。該機制保留了解空間搜索的部分隨機性，同時引入啟發信息加快模擬退火過程的收斂。

3）BV-RSA模型采用與文獻［15］同樣的效用函數，推導了超點運動引起效用函數變化的增量計算方法，降低了模擬退火檢驗的計算開銷。

15個標準數據集上的實驗表明，BV-RSA模型在10個數據集上獲得了最優結果，且模型精度對基礎聚類數量的變化不敏感，表現出良好的魯棒性。

在后續研究中，將進一步設計BV-RSA模型的并行計算方案，拓寬其在大數據集上的應用。