基于案例學(xué)習(xí)的多層次聚類指標(biāo)客觀權(quán)重極大熵挖掘模型

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

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

1 引言

在實(shí)際多屬性聚類決策問題中，特征指標(biāo)的聚類權(quán)重是影響聚類結(jié)果準(zhǔn)確性的重要因素之一，聚類指標(biāo)的合理配置問題一直是國內(nèi)外學(xué)者的研究熱點(diǎn)，并且已取得了豐富的研究成果。

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

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

以上研究雖然能夠有效解決部分多層次屬性指標(biāo)的賦權(quán)問題，但仍不能完全滿足實(shí)際多維聚類決策的需要，具體問題體現(xiàn)在對于對象歷史聚類信息的利用程度還有所欠缺。歷史聚類信息綜合反映了各層次指標(biāo)對于對象所屬類別的影響程度，通過對歷史聚類案例的有效學(xué)習(xí)不僅有助于發(fā)掘?qū)ο缶垲惖谋举|(zhì)客觀規(guī)律，還能進(jìn)一步挖掘出對象各個屬性指標(biāo)的權(quán)重信息。對于多屬性聚類決策而言，案例學(xué)習(xí)是指通過決策者學(xué)習(xí)推理特定典型案例集的決策結(jié)果，計(jì)算出部分或全部決策參數(shù)，從而構(gòu)建出對應(yīng)的決策模型，再應(yīng)用于對所有對象進(jìn)行評價的方法[20]。目前代表性的模型包括UTADIS[21]以及基于案例距離的決策模型[22]，這兩種方法雖然為多屬性決策問題提供了具有借鑒意義的參考，但并未直接涉及對象屬性指標(biāo)的客觀賦權(quán)問題。

為充分挖掘已有的歷史聚類案例信息，本文基于向量空間模型將聚類對象轉(zhuǎn)化為多維屬性特征空間向量，運(yùn)用余弦距離測算對象底層指標(biāo)屬性之間的相似程度，然后根據(jù)對象屬性指標(biāo)的層次性結(jié)構(gòu)以及相應(yīng)各層指標(biāo)的權(quán)重系數(shù)綜合測算出對象之間的相似程度，最后根據(jù)歷史聚類案例中的同類對象具有較高的相似度特點(diǎn)，建立了基于案例學(xué)習(xí)的多層次聚類指標(biāo)客觀權(quán)重極大熵挖掘模型，從而測算各個層次指標(biāo)對整個對象所屬類別的影響程度。

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

在多屬性決策過程中，決策者往往通過評價對象特征屬性之間的相似程度，將評價對象劃分到不同的類別中去。某些對象之所以能夠歸屬到同一類中，是因?yàn)槠渥匀槐举|(zhì)屬性具有較高的相似性。在進(jìn)行相似性評價過程中，觀測對象往往具有多個屬性指標(biāo)，并且指標(biāo)之間還存在一定的層次結(jié)構(gòu)關(guān)系，為對象的相似性測度帶來了很大的不便。對此，本部分將根據(jù)對象相似性的各種影響因素的屬性范圍，將其分成不同的評價方面、要素和因素，其中每個待評價對象會包含若干個評價方面，每個評價方面又含有多個評價要素，每個評價要素又含有不同的評價因素(如圖1所示)。由于每個評價層次的各個指標(biāo)對對象間相似性的影響程度不盡相同，因此需要對各層次的指標(biāo)賦以相應(yīng)的權(quán)重以合理地區(qū)分其重要程度。

圖1 對象聚類指標(biāo)層次結(jié)構(gòu)示意圖

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

向量空間模型(Vector Space Model)是由Salton[23]于20世紀(jì)70年代提出的決策對象表征模型，該模型能夠?qū)ο髮傩灾笜?biāo)的相似度計(jì)算轉(zhuǎn)化成向量空間中的向量距離運(yùn)算。根據(jù)向量空間模型的構(gòu)建思想，對于一個由多層次屬性指標(biāo)構(gòu)成的聚類對象而言，每個屬性指標(biāo)都將看作是一個多維向量，其中底層指標(biāo)向量表示某一類要素的集合，其向量元素為某一要素的觀測值；上層指標(biāo)向量為其下屬次級指標(biāo)的集合，其向量元素是一個包含其下屬次級指標(biāo)屬性值及其相應(yīng)的權(quán)重的二維向量。

定義1 聚類對象的底層指標(biāo)向量為

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

(1)

式中向量元素xi表示觀測到的第i個影響要素的觀測值，n表示該指標(biāo)影響要素的數(shù)量。

定義2 聚類對象的上層指標(biāo)向量為

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

(2)

式中的向量元素yi表示該指標(biāo)的第i個下屬次級指標(biāo)的觀測值；wi表示該指標(biāo)的第i個下屬次級指標(biāo)的權(quán)重值；m表示該指標(biāo)下屬的次級指標(biāo)數(shù)量。

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

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)

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

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

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

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

(4)

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

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

kh…j…l

(5)

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

表1 對象相似度表

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

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

證明：采用反正法。假設(shè)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不屬于同一類相矛盾。所以假設(shè)不成立，原命題成立。

3 基于案例學(xué)習(xí)的多層次聚類指標(biāo)客觀權(quán)重極大熵權(quán)重挖掘模型

在確定對象聚類指標(biāo)權(quán)重過程中，針對歷史聚類案例中相似對象的類別從屬關(guān)系，可以通過各聚類指標(biāo)所傳達(dá)的類別信息量確定其權(quán)重系數(shù)。根據(jù)極大熵準(zhǔn)則[24]，在已知部分信息的基礎(chǔ)上，認(rèn)為權(quán)重熵值達(dá)到最大且滿足約束條件時所得到的權(quán)重值出現(xiàn)的可能性最大，因此可構(gòu)建基于案例學(xué)習(xí)的多層次聚類指標(biāo)客觀權(quán)重極大熵挖掘模型。具體建模步驟如下：

步驟1: 確定目標(biāo)函數(shù)

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

(6)

式(6)中，w表示各個評價層次中的指標(biāo)權(quán)重，ni表示第i評價層的指標(biāo)數(shù)量，fi(w)表示第i評價層的指標(biāo)權(quán)重熵函數(shù)，

步驟2：約束條件確定

(1)各評價層次中指標(biāo)的權(quán)重之和為1，即

(7)

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

根據(jù)目標(biāo)函數(shù)和約束條件，可建立如下多目標(biāo)規(guī)劃來求解各層次指標(biāo)權(quán)重，如下式所示：

(8)

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

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

(2)當(dāng)0≤λi≤1時，若設(shè)F(w1)

綜上，U(F(w))是F(w)的單調(diào)遞增函數(shù)。因此新的單目標(biāo)規(guī)劃的最優(yōu)解是原規(guī)劃的有效解。證畢

定理3基于案例學(xué)習(xí)的多層次聚類指標(biāo)客觀權(quán)重的極大熵挖掘模型存在唯一的最優(yōu)解

證明：由極大熵模型：

若極大熵模型是一個凸集上的凸規(guī)劃問題，則必存在唯一的最優(yōu)解

由定理1和規(guī)劃模型的標(biāo)準(zhǔn)表達(dá)式

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

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

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

4 案例分析

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

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

大量的刑事案件表明，有很多指標(biāo)的屬性內(nèi)容無法直接客觀、準(zhǔn)確的描述，如受害人在對嫌疑人的

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

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

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

將各層指標(biāo)的權(quán)重值作為待定系數(shù)，求解5個案件的兩兩相似度如表3所示。

表2 底層特征指標(biāo)的屬性信息

表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為身份特征的權(quán)重，w2為體型特征的權(quán)重，w3為口音特征權(quán)重，w4為作案時間權(quán)重，w5為作案工具特征，w6為嫌疑人特征，w7為作案特征權(quán)重。對于整個案例而言，各層指標(biāo)的重要性程度并無實(shí)質(zhì)性差異，因此在極大熵客觀權(quán)重配置模型中將各個目標(biāo)函數(shù)的權(quán)重配置為1/3，最終基于歷史分類信息的極大熵客觀權(quán)重配置模型如下式所示。

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

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

表4 與其他方法的比較

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

5 結(jié)語

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