基于模擬退火改進的近鄰傳播聚類在群決策中的應用＊

張 煜，王 磊，俞 璐，馬 昊，郁 楠

(1.陸軍工程大學通信工程學院，江蘇 南京 210007；2.解放軍31121部隊)

0 引言

隨著信息通信技術(shù)的迅猛發(fā)展，只有少數(shù)精英參與的小群體決策已無法適應信息社會的發(fā)展。為了體現(xiàn)決策的科學性和民主性，由不同經(jīng)驗背景和知識結(jié)構(gòu)的成員，從不同視角和評判準則對方案進行評價，并依據(jù)特定的規(guī)則集結(jié)為群體判斷的多屬性群體決策，已廣泛應用于實際復雜決策問題中。然而，決策成員數(shù)量大、評判準則類型多、準則間關(guān)聯(lián)關(guān)系復雜，使得決策群體難以形成比較一致的決策。因此，對群體成員進行偏好聚類，形成若干子群體從而減少群體集結(jié)的復雜度，這是群體決策的重要基礎(chǔ)。

聚類是一種典型的無監(jiān)督學習算法，根據(jù)相似性度量準則將數(shù)據(jù)分組成多個簇或者類，并且最大化類內(nèi)數(shù)據(jù)的同質(zhì)性和類間數(shù)據(jù)的異質(zhì)性。相似性度量一般可以分為基于距離的、基于密度的、基于連接的三類，其中基于距離的最常用。在群體決策聚類應用方面，XU 等將偏好矢量間的相關(guān)度作為相似性度量，TANG 等以偏好矢量間的歐氏距離作為相似性度量，Ma 等針對猶豫模糊語言術(shù)語以期望距離和猶豫度相結(jié)合作為相似性度量，其中矢量相關(guān)度應用較為廣泛。為適用群決策應用，合理度量決策者意見相似性，實現(xiàn)整體相似性與最大分歧點的折衷，本文擬結(jié)合皮爾遜相關(guān)系數(shù)和切比雪夫距離作為度量決策者給出的評價向量間相似性的準則。

聚類算法研究上，K-means 聚類作為最經(jīng)典的聚類算法因原理簡單、計算量小得到了廣泛應用，F(xiàn)uzzy C-means 聚類引入模糊數(shù)作為隸屬度降低了對聚類個數(shù)的敏感度，隨著應用深入Hierarchical、K-medoids、DBSCAN等經(jīng)典聚類算法及各類改進不斷推出。在群決策應用上，LIU 等針對FCM 聚類算法存在的局部極值和伸縮性差等問題提出了基于全部最小連通支配集的改進聚類算法，XU等提出基于群體智能的改進的蟻群聚類算法，TANG等對K-means 聚類進行改進，結(jié)合群體共識達成應用于群決策。2007 年，Brendan J.Frey 提出的近鄰傳播聚類(Affinity Propagation，AP)是一種快速有效的聚類算法，具有無需設(shè)置聚類簇個數(shù)、聚類中心為原始數(shù)據(jù)、對野值不敏感等優(yōu)點。模擬退火算法(Simulated Annealing，SA)是基于Monte-Carlo迭代求解策略的一種隨機尋優(yōu)算法，具有強大的全局尋優(yōu)能力。本文擬發(fā)揮模擬退火算法在全局參數(shù)尋優(yōu)方面的優(yōu)勢，提升AP算法的穩(wěn)定性和聚類效果，并將其應用于群決策。

1 基礎(chǔ)理論

1.1 多屬性群體決策問題

1.2 相似性度量

1.2.1 皮爾遜相關(guān)系數(shù)

用于度量兩個向量之間的相似程度時，相關(guān)系數(shù)越大，兩向量的相似性越強，反之相似性越弱。

評價向量V和V間的皮爾遜相關(guān)系數(shù)為：

1.2.2 切比雪夫距離

用于度量兩個向量之間的相似程度時，切比雪夫距離越大則兩個向量越不相似，距離越小則兩個向量越相似。

評價向量V和V間的切比雪夫距離為：

1.3 一致性度量

在群決策應用中，子群體的一致性由子群體成員間的平均相似性度量，群體的一致性由各子群體的一致性指標的加權(quán)和度量。

第i 個子群體G(含q個成員)的一致性指標ρ為：

群體的一致性指標為：

其中，k為子群體的個數(shù)。

2 新的相似性度量

在相似性度量方面，距離度量側(cè)重于衡量向量間的接近程度，一般不考慮分量的取值分布；相關(guān)性度量側(cè)重衡量向量間的相似性，一般不考慮向量間的整體距離。在決策者對方案進行評價時，可能出現(xiàn)整體評價相似但個別屬性評價上存在較大分歧的情況，從單一指標判斷兩者意見是否一致存在不足。皮爾遜相關(guān)系數(shù)作為使用最為廣泛的相關(guān)性度量，能減小不同決策者評價尺度差異的影響，反應決策者在方案評價的整體相似性。切比雪夫距離作為向量空間中的一種度量，以各維度上數(shù)值差的最大值定義為兩點之間的距離，能有效評估決策者對方案評價的最大分歧。本文擬結(jié)合兩者優(yōu)勢，將皮爾遜相關(guān)系數(shù)和切比雪夫距離的加權(quán)組合作為評價向量相似性的度量準則。

評價向量V和V間的相似性為：

其中，∈[0,1]，為折衷參數(shù)，可根據(jù)對兩者的重視程度不同進行調(diào)節(jié)，當=1 時退化為皮爾遜相關(guān)系數(shù)，當=0時退化為切比雪夫距離。

3 改進的近鄰傳播聚類算法

3.1 近鄰傳播算法

近鄰傳播算法(Affinity Propagation，AP)是一種快速有效的聚類算法，具有無需事先確定聚類簇個數(shù)、以已有數(shù)據(jù)點為聚類中心、對數(shù)據(jù)野值不敏感、對相似度矩陣無對稱性要求、結(jié)果誤差小等優(yōu)點。算法主要過程為：①根據(jù)數(shù)據(jù)點之間的相似度組成×的相似度矩陣；②根據(jù)各點成為聚類中心的可能程度，選擇公共或差異化偏向度(,)；③根據(jù)公式⑹～⑻不斷交換歸屬度(,)和吸引度(,)，節(jié)點選擇(,)+(,)最大的節(jié)點作為自己的代表，如圖1所示；④如果達到預設(shè)的迭代次數(shù)或者聚類中心不再變化，迭代終止完成聚類中心選擇。

圖1 AP算法信息傳遞示意圖

(,)和(,)的信息傳遞公式為：

3.2 模擬退火算法

模擬退火算法(Simulated Annealing，SA)是基于Monte-Carlo 迭代求解策略的一種隨機尋優(yōu)算法，結(jié)合概率突跳特性在解空間中隨機尋找目標函數(shù)的最優(yōu)解，能有效避免陷入局部極小并最終趨于全局最優(yōu)。算法主要過程為：①從某一較高初溫T出發(fā)，隨機生成一個初始解，并計算目標函數(shù)值()；②在當前解周圍擾動產(chǎn)生新解；③當≤0 時接受新解，當＞0 時利用Metropolis 準則以概率(-/)判定是否接受新解；④使溫度T 按比例下降，重復步驟2～4 迭代尋找問題最優(yōu)解；⑤當達到最大迭代次數(shù)或滿足終止條件時，輸出最優(yōu)解。如圖2所示。

圖2 模擬退火算法流程圖

3.3 基于模擬退火改進的近鄰傳播聚類算法

近鄰傳播聚類算法通過吸引度與歸屬度的交換競爭選出子群體代表，與群決策中通過選舉代表參與進一步?jīng)Q策的過程相吻合，算法對群決策應用的適用性較好。然而傳統(tǒng)AP 聚類需選取合適的偏向度參數(shù)組合才可得到最佳聚類效果，但人工調(diào)節(jié)偏向度參數(shù)需了解數(shù)據(jù)特點、調(diào)節(jié)難度大，而且同組參數(shù)對不同數(shù)據(jù)的適用性也不同，造成偏向度參數(shù)可移植性不強，聚類結(jié)果穩(wěn)定性不高。本文以近鄰傳播聚類為基本框架，結(jié)合模擬退火算法進行偏向度尋優(yōu)設(shè)置，可在無需人工調(diào)節(jié)參數(shù)情況下獲得穩(wěn)定的聚類結(jié)果。

⑴相似度度量。傳統(tǒng)AP 聚類算法一般選擇負的歐式距離作為其相似度度量，本文以定義5 描述的相似度度量為標準，考慮整體相似性與最大分歧點同等重要將參數(shù)設(shè)為=0.5，則-1 ≤s≤0.5。為適用AP聚類算法的更新公式，在聚類過程中將相似矩陣所有元素減1使其取值小于0。

⑵差異化偏向度。采用相同偏向度設(shè)置時，認為全部樣本點成為代表的可能性相等；采用差異化偏向度設(shè)置時，偏向度大的點成為代表的可能性更大。在現(xiàn)實中，因立場觀念、教育程度、經(jīng)驗見識等不同，群體中必然會形成權(quán)威個體，其成為代表的可能性應該更高，采用差異化的偏向度更加符合應用實際且能取得更好的聚類效果。

⑶結(jié)合模擬退火。人工設(shè)置差異化偏向度輸入?yún)?shù)多且要了解數(shù)據(jù)特點，實時性和可移植性較差。為通過算法尋找最優(yōu)偏向度，將差異化偏向度設(shè)置為模擬退火算法的解集，以聚類結(jié)果計算的群體一致性指標為目標函數(shù)，通過迭代獲得最優(yōu)偏向度。同時，為了提高算法效率，由具有良好區(qū)間遍歷性的混沌序列迭代產(chǎn)生新解。

4 實例應用

力爭2030 年前實現(xiàn)碳達峰、2060 年前實現(xiàn)碳中和，是我國的重大戰(zhàn)略部署。要實現(xiàn)碳達峰、碳中和目標，促進新能源汽車發(fā)展是重要途徑，隨著新能源汽車數(shù)量的提升，充換電站建設(shè)成為急需跟進的關(guān)鍵領(lǐng)域。某公司擬在a1、a2、a3 三個位置選取一個作為充換電站建設(shè)點位，集結(jié)30 位各領(lǐng)域?qū)＜遥x擇供電能力、交通便利、經(jīng)濟效益、安全風險等5個指標(均表示為效益型)，并賦予指標權(quán)重={0.20.20.20.20.2}，進行項目選址的群體決策。決策過程如下：

：獲得評價向量，如表1所示。

表1 評價向量表

：對各方案分別進行聚類與子集代表選擇，以各聚集G的成員數(shù)與決策者總數(shù)的比值λ= q/作為聚集代表的權(quán)重，結(jié)果如表2所示。

表2 聚類結(jié)果

：將各聚集代表的意見加權(quán)集結(jié)為各方案的最終評價值，如表3所示。

表3 方案最終評價值

步驟4：根據(jù)最終評價值進行方案排序：1 ?2 ?3。

5 對比分析

5.1 相似性度量對比

為驗證本文所提相似性度量的有效性，對兩組共六個評價向量間的相似度量進行比較，如圖3所示。

圖3 對比示意圖

通過表4 的對比可知，兩組向量對的歐氏距離相同，因此，歐氏距離無法區(qū)分兩組向量對；另一方面，第一組向量對的相關(guān)系數(shù)相同但切比雪夫距離不同，第二組向量對的切比雪夫距離相同但相關(guān)系數(shù)不同，如使用單一相似性度量，將無法進行區(qū)分，而本文的相似性度量方法有較好的區(qū)分度。

表4 相似性度量對比

5.2 算法改進分析

本文對AP 聚類的改進，是通過模擬退火進行差異化偏向度擇優(yōu)，仿真實驗以對方案a1 下各決策者的聚類為例，以群體的一致性作為評價指標，對不同的偏向度設(shè)置方法進行比較，如圖4所示。方法一：將偏向度向量的所有元素都相同，設(shè)置為各數(shù)據(jù)相似度的中位數(shù)。方法二：將偏向度向量的所有元素都相同，通過循環(huán)迭代尋優(yōu)確定。方法三：通過本文算法尋找最優(yōu)差異化偏向度。實驗結(jié)果對比如圖4所示。

圖4 算法改進對比圖

從圖4 可知，方法二通過迭代選擇最優(yōu)相同偏向度較方法一有效提升了一致性指標，方法三通過模擬退火選擇最優(yōu)差異化偏向度進一步提升了聚類效果，說明了本文方法的有效性。

5.3 不同算法比較

為了說明本文算法的良好性能，統(tǒng)一采用定義5確定的相似性度量和定義4 確定的一致性指標，將本文方法與常用于群決策的幾類聚類算法進行比較：文獻[19]中的Hierarchical 聚類、文獻[20]中的K-mean聚類和文獻[21]中的Fuzzyc-mean 聚類，對比結(jié)果如表5所示。

表5 不同算法聚類結(jié)果對比

由表5 可知，本文算法的聚類一致性指標優(yōu)于其他三個算法，證明算法的有效性。另一方面，K-mean和Fuzzyc-mean 均需事先設(shè)置聚集個數(shù)，且初值敏感性強聚類結(jié)果不穩(wěn)定，而本文算法由模擬退火進行全局尋優(yōu)無需人工設(shè)置參數(shù)，聚類結(jié)果穩(wěn)定可靠，而且選出的子群體代表適用于群決策應用。

6 結(jié)論

在大數(shù)據(jù)時代背景下，隨著決策參與個體的不斷豐富，信息集結(jié)前進行合理的聚類顯得越發(fā)重要。本文在定義新的相似性度量基礎(chǔ)上，有效利用模擬退火算法設(shè)置最優(yōu)差異化偏向度，改進的AP 聚類算法無需人工調(diào)節(jié)參數(shù)就可獲得穩(wěn)定的聚類結(jié)果和良好的一致性指標，經(jīng)實驗對比證明了其良好性能。由于篇幅有限，本文在評價信息上未采用區(qū)間模糊數(shù)、概率語言術(shù)語等較先進的評價模式，在聚類后，對子群體代表的評價信息進行簡單的加權(quán)集結(jié)。下一步，可將信息表示方式擴展至概率語言集等不同信息表示環(huán)境，還可對共識達成和排序方法進行擴展研究。