基于案例學習的多層次聚類指標客觀權重極大熵挖掘模型

曹穎賽，劉思峰，方志耕，曾友春，王 歡

(1.南京航空航天大學經濟與管理學院，江蘇 南京 210016；2.陸軍軍事交通學院汽車士官學校運輸指揮系，安徽 蚌埠 233011)

1 引言

在實際多屬性聚類決策問題中，特征指標的聚類權重是影響聚類結果準確性的重要因素之一，聚類指標的合理配置問題一直是國內外學者的研究熱點，并且已取得了豐富的研究成果。

概括起來，傳統的指標權重確定方法大致可以分為兩大類：主觀賦權法和客觀賦權法。其中，主觀賦權法，是指基于決策者的知識經驗或偏好，按照重要性程度對各指標進行比較、賦值和計算而得出權重的方法。典型主觀賦權方法包括：專家調查法(Delphi法)[1]、層次分析法(AHP法)[2]、偏好比率法[3]、環比評分法[4]、二項系數法[5]、比較矩陣法[6]和重要性排序法[7]等。這些方法僅僅體現了決策者的工作經驗以及自身對指標的偏好程度，所給出的權重系數比較粗略。對此國內外學者們不斷在原有思路與方法的基礎上進行探索和創新，并基于指標客觀數據的差異程度提出了一系列客觀權重確定方法，包括：主成分分析法[8]、熵技術法[9]、離差最大化法[10]、均方差法[11]和多目標規劃法[12]等，這些方法旨在突出對象在評價指標之間的客觀差異性。此外，還有大量研究致力于綜合指標權重主、可觀信息以提升決策的準確性。丁濤等[13]提出了一種權重自調整方法，旨在平衡主觀賦權和客觀賦權所帶來的誤差，從而提高評價的合理性。程硯秋[14]基于區間相似度、序列比對等原理，對特定專家給出的指標主觀權重進行了修正，以增加群決策的有效性。金佳佳等[15]還從關聯的角度融合了主觀先驗信息與客觀信息，并將其轉化為求解綜合權重的約束條件，旨在提高權重配置的可信度。

然而上述方法大多僅聚焦于單層聚類指標的客觀權重配置問題，但在實際多屬性聚類決策領域中，觀測對象往往包含多個特征指標，并且特征指標之間還具有一定的層次結構。目前，針對多層次聚類指標賦權問題普遍采用的還是主觀性較強的層次分析(AHP)方法[16-17]。在運用層次分析方法對多層次聚類指標進行賦權時，需要專家對于指標的重要性信息進行主觀判斷比較，在一定程度上影響了指標權重的客觀性。Zhang等[18]運用優化模型求得了多層次指標之間的相互影響系數并在此基礎上求解了相應指標的權重，最后將指標賦權結果應用至城市可持續發展評價研究中。Boroushaki[19]通過測算各層次指標所包含的信息熵大小求解出了指標權重大小，并運用修正TOPSIS算法給出了空間多屬性決策問題的解決步驟。

以上研究雖然能夠有效解決部分多層次屬性指標的賦權問題，但仍不能完全滿足實際多維聚類決策的需要，具體問題體現在對于對象歷史聚類信息的利用程度還有所欠缺。歷史聚類信息綜合反映了各層次指標對于對象所屬類別的影響程度，通過對歷史聚類案例的有效學習不僅有助于發掘對象聚類的本質客觀規律，還能進一步挖掘出對象各個屬性指標的權重信息。對于多屬性聚類決策而言，案例學習是指通過決策者學習推理特定典型案例集的決策結果，計算出部分或全部決策參數，從而構建出對應的決策模型，再應用于對所有對象進行評價的方法[20]。目前代表性的模型包括UTADIS[21]以及基于案例距離的決策模型[22]，這兩種方法雖然為多屬性決策問題提供了具有借鑒意義的參考，但并未直接涉及對象屬性指標的客觀賦權問題。

為充分挖掘已有的歷史聚類案例信息，本文基于向量空間模型將聚類對象轉化為多維屬性特征空間向量，運用余弦距離測算對象底層指標屬性之間的相似程度，然后根據對象屬性指標的層次性結構以及相應各層指標的權重系數綜合測算出對象之間的相似程度，最后根據歷史聚類案例中的同類對象具有較高的相似度特點，建立了基于案例學習的多層次聚類指標客觀權重極大熵挖掘模型，從而測算各個層次指標對整個對象所屬類別的影響程度。

2 基于對象特征屬性空間向量的聚類分析

在多屬性決策過程中，決策者往往通過評價對象特征屬性之間的相似程度，將評價對象劃分到不同的類別中去。某些對象之所以能夠歸屬到同一類中，是因為其自然本質屬性具有較高的相似性。在進行相似性評價過程中，觀測對象往往具有多個屬性指標，并且指標之間還存在一定的層次結構關系，為對象的相似性測度帶來了很大的不便。對此，本部分將根據對象相似性的各種影響因素的屬性范圍，將其分成不同的評價方面、要素和因素，其中每個待評價對象會包含若干個評價方面，每個評價方面又含有多個評價要素，每個評價要素又含有不同的評價因素(如圖1所示)。由于每個評價層次的各個指標對對象間相似性的影響程度不盡相同，因此需要對各層次的指標賦以相應的權重以合理地區分其重要程度。

圖1 對象聚類指標層次結構示意圖

2.1 對象特征屬性空間向量表征

向量空間模型(Vector Space Model)是由Salton[23]于20世紀70年代提出的決策對象表征模型，該模型能夠將對象屬性指標的相似度計算轉化成向量空間中的向量距離運算。根據向量空間模型的構建思想，對于一個由多層次屬性指標構成的聚類對象而言，每個屬性指標都將看作是一個多維向量，其中底層指標向量表示某一類要素的集合，其向量元素為某一要素的觀測值；上層指標向量為其下屬次級指標的集合，其向量元素是一個包含其下屬次級指標屬性值及其相應的權重的二維向量。

定義1 聚類對象的底層指標向量為

VBottom=[x1,x2,…,xi,…xn]

(1)

式中向量元素xi表示觀測到的第i個影響要素的觀測值，n表示該指標影響要素的數量。

定義2 聚類對象的上層指標向量為

VUpper=[(y1,w1),(y2,w2),…,(yi,wi),…,(ym,wm)]

(2)

式中的向量元素yi表示該指標的第i個下屬次級指標的觀測值；wi表示該指標的第i個下屬次級指標的權重值；m表示該指標下屬的次級指標數量。

綜上，聚類對象的向量空間模型可表示如下：

C={t1,w1[t1.1,w1.1(t1.1.1,w1.1.1;…;t1.1.k,w1.1.k);…;t1.j,w1.j();…];…;ti,wi[()];…}

(3)

式中，各個指標下各自又包含其下屬次級指標，ti,wi為聚類對象的一級指標觀測值及其權重，ti.j,wi.j為待評價對象的二級指標觀測值及其權重，依次類推直至底層的評價因素集合。

2.2 基于對象相似度的聚類分析

對于具有多層次聚類屬性指標的待聚類對象而言，對象之間的相似度測算需要逐層求解各評價方面、評價要素和因素的相似程度，即首先求解最底層要素的相似程度，然后依次逐層向上求解各個評價因素的相似程度，直至求解整個對象的相似程度。考慮到余弦距離能夠通過求解兩個向量夾角余弦值的方式度量兩個對象之間的一致性，本部分將采用向量的余弦距離測度要素之間的相似程度。

定義3 若底層要素A的n維向量表示為A=[A1,A2,…,An]，底層要素B的n維向量表示為B=[B1,B2,…,Bn]，則底層要素A與B之間的相似度為

(4)

由式(4)可知，在將對象轉化為空間向量之后，兩向量之間夾角越小，其余弦值越大，兩個要素越相似。

定義4 若某待聚類對象有n層評價指標，底層因素個數為m1，其各個因素的相似度為siml，權重為kl(l=1,2,…,m1)；第i層中的第j個指標的權重為kj(j=1,2,…,mi)，則任意兩個對象之間的相似度可表示為

kh…j…l

(5)

由式(5)可知，基于對象底層指標要素之間的相似度以及指標的層次結構關系，可以自下而上逐層求解對象之間的相似程度。若存在n個待聚類對象，通過求解兩兩對象之間的相似度，可以得到對象之間的相似度如表1所示。

表1 對象相似度表

根據相應的相似度臨界值sim*，即可判定出對象的所屬類別，即當sim(i,j)≥sim*時，對象i和j便屬于同一類。

定理1針對某一對象而言，同一類內對象之間的相似度最小值大于不同類對象間相似度的最大值，即若對象i和j同屬于類Sα，對象k屬于類Sβ，則min{sim(i,j)}>max{sim(i,k)}。

證明：采用反正法。假設min{sim(i,j)}≤max{sim(i,k)}，由于對象i和j同屬于一類，若相似度的分類臨界值為sim*，則sim(i,j)≥sim*，所以由sim*≤min{sim(i,j)}，min{sim(i,j)}≤max{sim(i,k)}推得max{sim(i,k)}≥sim*，因此對象i和k同屬于一類，這與對象i和k不屬于同一類相矛盾。所以假設不成立，原命題成立。

3 基于案例學習的多層次聚類指標客觀權重極大熵權重挖掘模型

在確定對象聚類指標權重過程中，針對歷史聚類案例中相似對象的類別從屬關系，可以通過各聚類指標所傳達的類別信息量確定其權重系數。根據極大熵準則[24]，在已知部分信息的基礎上，認為權重熵值達到最大且滿足約束條件時所得到的權重值出現的可能性最大，因此可構建基于案例學習的多層次聚類指標客觀權重極大熵挖掘模型。具體建模步驟如下：

步驟1: 確定目標函數

對于一個包含由多個評價方面、要素和因素組成的多層次指標屬性的聚類對象而言，其任一指標權重wi是該指標在其所在的評價層指標集合中所占的比重，是一個隨機變量并具有一定的不確定性。按照極大熵準則，在已知部分信息的基礎上當各個評價層次的權重熵值達到最大且滿足約束條件時所得到的權重值出現的可能性最大。因此可構建多層次聚類指標客觀權重極大熵挖掘模型的目標函數如下式所示：

(6)

式(6)中，w表示各個評價層次中的指標權重，ni表示第i評價層的指標數量，fi(w)表示第i評價層的指標權重熵函數，

步驟2：約束條件確定

(1)各評價層次中指標的權重之和為1，即

(7)

(2)在歷史聚類案例中相同類別對象之間具有較高的相似度，即sim(i,j)>sim(i,k)，其中對象i和j同屬一類Sα，而對象k屬于類Sβ。

根據目標函數和約束條件，可建立如下多目標規劃來求解各層次指標權重，如下式所示：

(8)

定理2存在一組權重系數[λ1,λ2,…,λn]∈(0,1)，使得多目標極大熵聚類指標客觀權重挖掘問題能夠通過線性加權的方式轉化為單目標極大熵客觀權重配置問題。

(1)當0<λi<1時，若設F(w1)≤F(w2)，即fi(w1)≤fi(w2),i=1,2,…,n，且至少存在一個j(1≤j≤n)，使得fj(w1)

(2)當0≤λi≤1時，若設F(w1)

綜上，U(F(w))是F(w)的單調遞增函數。因此新的單目標規劃的最優解是原規劃的有效解。證畢

定理3基于案例學習的多層次聚類指標客觀權重的極大熵挖掘模型存在唯一的最優解

證明：由極大熵模型：

若極大熵模型是一個凸集上的凸規劃問題，則必存在唯一的最優解

由定理1和規劃模型的標準表達式

首先判斷目標函數的凹凸性，目標函數F(w)的海塞矩陣為

由于00所以|H|>0恒成立，因此該目標函數F(w)為凸函數，而約束條件為線性約束條件，所以為凸集。

綜上，該極大熵模型為凸集上的凸規劃問題，必存在唯一的最優解。證畢

4 案例分析

刑事犯罪案件雖然種類繁多，但是幾乎所有案件都包含有類似作案時間，作案地點，作案手段，嫌疑人特征，損失物品等特征屬性。合理地對案件進行串并處理，不僅能提高案件的偵破效率，還能促進案例庫的規范化管理以便于未來的案例推理學習。在案件串并過程中，案件屬性特征的權重配置決定了串并結果的合理性。本案例在運用向量空間模型表征各類案件特征屬性指標的基礎上，對案件之間的相似程度進行測算，最后運用已有的歷史案件串并信息，構建聚類指標極大熵客觀權重挖掘模型以確定案件各個屬性特征的權重。

某公安部門歷史案例庫中已有分好類的5個案例集C={C1,C2,C3,C4,C5}，案例屬性特征如圖2所示，并且已知其分類信息為C1,C2,C3同屬一類，C4和C5各成一類。

大量的刑事案件表明，有很多指標的屬性內容無法直接客觀、準確的描述，如受害人在對嫌疑人的

圖2 刑事案件屬性特征示意圖

身高及年齡身份進行描述時，只能給出大致模糊性的表述，呈現出“亦此亦彼”的特點。考慮到模糊子

集常用于處理不精確數據，因此采用模糊子集表示某指標下的屬性值屬于該指標某一要素的概率。以刑事案例中的嫌疑人身份向量表述為例，假設其設定的身份序列為(青年，中年，老年)，若某案件的嫌疑人身份向量為[0.2,0.7,0.1]，則表示該案件的嫌疑人身份屬于青年的概率為0.2，屬于中年的概率為0.7，屬于老年的概率為0.1。該案例庫中的5個案例集的底層指標屬性信息如表2所示。

將各層指標的權重值作為待定系數，求解5個案件的兩兩相似度如表3所示。

表2 底層特征指標的屬性信息

表3 案件相似度信息

由案例的分類信息可得

sim(1,2)>sim(1,4),sim(1,5),sim(2,4),sim(2,5);

sim(1,3)>sim(1,4),sim(1,5),sim(3,4),sim(3,5);

sim(2,3)>sim(2,4),sim(2,5),sim(3,4),sim(3,5)

令w1為身份特征的權重，w2為體型特征的權重，w3為口音特征權重，w4為作案時間權重，w5為作案工具特征，w6為嫌疑人特征，w7為作案特征權重。對于整個案例而言，各層指標的重要性程度并無實質性差異，因此在極大熵客觀權重配置模型中將各個目標函數的權重配置為1/3，最終基于歷史分類信息的極大熵客觀權重配置模型如下式所示。

最后解得w1=0.471，w2=0.487，w3=0.042，w4=0.515，w5=0.485，w6=0.974，w7=0.026

由此可以得出，對整個刑事案件而言,嫌疑人特征較為重要，其權重高達0.974，這符合人們對刑事案件偵破的直觀認識和了解；在嫌疑人特征方面，嫌疑人體型特征權重和口音特征幾乎相同但都遠高于身份特征，說明在定位搜尋犯罪嫌疑人時其身份特征信息容易被忽略。在作案特征屬性中，作案時間特征重要性稍高于作案工具特征。運用其他客觀權重配置方法求解得到案件各個屬性特征指標的權重值如表4所示。

表4 與其他方法的比較

從變異系數法和熵值法求得的權重結果來看，兩種方法僅能從底層指標屬性的觀測值信息中挖掘出單層聚類指標的權重信息，無法為更高層次的指標進行賦權。除此之外，從其單層指標的賦權結果不難發現，運用變異系數法求得的底層指標權重分布較為均勻(只有在嫌疑人特征屬性中能夠看出口音特征遠遠高于其他兩項特征；而從熵值法的權重配置的結果來看作案工具特征和嫌疑人口音特征相對重要)，無法明顯區分出其他各個指標的對于案件所屬類別的重要性影響程度。

5 結語

本文從評價聚類對象的相似度信息出發，構建了聚類對象特征屬性指標空間向量表征模型，并在此基礎上，采用余弦距離方法測度對象底層指標屬性之間的相似度，最后根據對象的指標層次結構及各層次屬性指標的權重系數綜合測算對象之間的相似程度。基于歷史聚類案例中屬于相同類別對象之間相似度較大，不同類別對象間的相似度較小特點，運用極大熵準則，構建了基于對象歷史聚類案例信息的多層次聚類指標客觀權重挖掘模型。最后以刑事案件的屬性指標權重配置問題進行案例研究并與其他權重配置方法進行對比分析，計算結果表明本文提出的方法在多層次聚類指標客觀賦權的合理性方面優于其他方法，為多層次指標對象聚類過程中的指標權重系數確定問題提供了一種新的解決方法和思路。