采用偏序集層次聚類的多準(zhǔn)則決策方法

朱旭光，沈玉志

（1.遼寧工程技術(shù)大學(xué) 創(chuàng)新實(shí)踐學(xué)院，遼寧 阜新 123000；2.遼寧工程技術(shù)大學(xué) 教務(wù)處，遼寧 阜新 123000）

0 引言

決策通常指從多種可能中做出選擇和決定，多準(zhǔn)則決策是指在多維度空間中，將可能具有沖突、不可共度的方案集中做出選擇的過(guò)程. 傳統(tǒng)方法過(guò)于依賴指標(biāo)權(quán)重?cái)?shù)值，且不能展示解集的層次結(jié)構(gòu)，當(dāng)權(quán)重未知時(shí)傳統(tǒng)方法顯得力不從心，基于此，采用偏序集理論，融入偏好信息，將聚類分析應(yīng)用于多準(zhǔn)則決策，能較好的解決以上問(wèn)題.

傳統(tǒng)決策方法往往關(guān)注最優(yōu)解或滿意解，但有時(shí)決策結(jié)果并非單解，所以有些學(xué)者嘗試將多準(zhǔn)則決策方法與聚類方法相結(jié)合，進(jìn)而突出決策領(lǐng)域的優(yōu)勢(shì)，如文獻(xiàn)[1].文獻(xiàn)[2]提出一個(gè)決策模型，與聚類算法相結(jié)合，利用學(xué)習(xí)平臺(tái)上可用的不同數(shù)據(jù)集，根據(jù)學(xué)習(xí)者的行為和專業(yè)知識(shí)對(duì)學(xué)習(xí)者進(jìn)行分類.提出了一種多智能體方法，該方法使用智能代理來(lái)表示參與者，實(shí)現(xiàn)多準(zhǔn)則決策模型進(jìn)而優(yōu)化學(xué)習(xí)過(guò)程.類似研究還有文獻(xiàn)[3]～文獻(xiàn)[7]等，分別針對(duì)不同應(yīng)用，優(yōu)化了決策模型，利用不同決策方法或評(píng)價(jià)方法，對(duì)目標(biāo)樣本進(jìn)行考察.

聚類分析的決策方法沒(méi)能解決解集分層問(wèn)題，決策過(guò)程只注重方法和求解原則的選擇，而忽略了解的性質(zhì).決策過(guò)程的解往往不是單獨(dú)的，而是一個(gè)集合，這個(gè)集合可能是非完全序的，也可能是偏序的.已有研究沒(méi)有將層次聚類分析應(yīng)用于多準(zhǔn)則決策領(lǐng)域，沒(méi)有對(duì)決策結(jié)果進(jìn)行分層[8-18].基于此，嘗試采用偏序集理論，融入偏好信息，利用層次聚類分析優(yōu)化傳統(tǒng)多準(zhǔn)則決策方法，并驗(yàn)證方法的有效性.

1 基于偏序集層次聚類決策方法

1.1 層次聚類

層次聚類分析法中的層次關(guān)系，并不是類之間的上下級(jí)層次，而是在聚類過(guò)程中的范圍層次，即一種演繹-歸納層次，并沒(méi)有體現(xiàn)類與類之間的等級(jí)層次，即上下級(jí)層次關(guān)系.層次聚類的層，并沒(méi)有絕對(duì)的鄰接關(guān)系，可能從這幾個(gè)樣本開(kāi)始聚類，得到某種層次關(guān)系，類似地球土層.從其他樣本開(kāi)始聚類，又得到其他層次關(guān)系，總之，層次關(guān)系不固定，體現(xiàn)不出類別間的上下級(jí)關(guān)系以及相鄰層關(guān)系.

已有聚類算法并不適用如何解釋密度分散情況.此n1個(gè)樣本密度為d1，n2個(gè)樣本密度為d2，依次類推.d1，d2，……無(wú)法比較誰(shuí)更密.利用偏序集理論進(jìn)行層次聚類可解決，同類基本都在相鄰層次，有的層寬，有的層窄，分散點(diǎn)、離群點(diǎn)通常位于最頂層或最底層.

20世紀(jì)50年代，學(xué)者們已利用層次結(jié)構(gòu)進(jìn)行數(shù)據(jù)描述，典型的就是樹(shù)狀結(jié)構(gòu).對(duì)樹(shù)狀圖中包含的信息的解釋通常是以下類型：集合包含關(guān)系、對(duì)象集合的分區(qū)和有效集群劃分.在這種情況下，樹(shù)狀圖提供了一個(gè)精確的潛在展示模型.

通過(guò)在樹(shù)狀圖上進(jìn)行查找，相當(dāng)于在拓?fù)淇臻g以最佳逼近的方式找到聚類簇.這種方法是一種拓?fù)浞椒ǎɑ诩霞捌鋵傩裕?，是使用更廣泛的優(yōu)化或統(tǒng)計(jì)方法.總之，一個(gè)樹(shù)狀圖聚集了許多接近性或同分類關(guān)系的數(shù)據(jù)體，可以通過(guò)樹(shù)狀圖提供相應(yīng)的聚類結(jié)果.而利用偏序矩陣計(jì)算出哈斯矩陣，其對(duì)應(yīng)的哈斯圖，與這種層次結(jié)構(gòu)是非常契合的.

1.2 基于偏序集層次聚類

傳統(tǒng)層次聚類是從任意樣本開(kāi)始，計(jì)算任意樣本距離，將距離近的算作一類，再計(jì)算類間距離.從計(jì)算任意兩樣本距離再到類間距離測(cè)算，耗費(fèi)大量運(yùn)算時(shí)間.基于此，利用偏序集理論改寫層次聚類方法.

定義1設(shè)R是集合A上的一個(gè)二元關(guān)系，若R滿足

（1）自反性：對(duì)任意xA∈ ，有xRx.

（2）反對(duì)稱性：對(duì)任意,xyA∈ ，若xRy且yRx，則xy= .

（3）傳遞性：對(duì)任意 ,,xyzA∈ ，若xRy且yRz，則xRz.

則稱R為A上的偏序關(guān)系[19].

傳統(tǒng)二階聚類[20]首先構(gòu)建聚類特征樹(shù).把某樣本作為樹(shù)的根節(jié)點(diǎn)，依據(jù)距離計(jì)算公式，計(jì)算樣本間的親疏程度，可以標(biāo)定一個(gè)臨界值，把其他樣本放到最近的樣本中；如果某樣本沒(méi)落在臨界值里，即沒(méi)有找到與它足夠近的節(jié)點(diǎn)，就讓它成為一個(gè)新的節(jié)點(diǎn).而采用偏序集方法生成的哈斯圖，可以通過(guò)相鄰層次查看親疏程度，即在矩陣?yán)锿耆w現(xiàn)，所以更能提高聚類效率.

每一個(gè)樣本有多個(gè)指標(biāo)，這些指標(biāo)重要性可能相等，也可能有主次之分.如果各指標(biāo)同等重要，即所有指標(biāo)都是等權(quán)重的，則采用傳統(tǒng)偏序集計(jì)算方法.若這些指標(biāo)是非等權(quán)重的，那么，得到指標(biāo)的權(quán)重順序即可，采用岳立柱[21]等人提出的偏序集計(jì)算方法進(jìn)行比較運(yùn)算.算法步驟如下.

步驟1對(duì)于有多個(gè)指標(biāo)（準(zhǔn)則）的待分類數(shù)據(jù)，取某一重要指標(biāo)或某一變化范圍大的指標(biāo)，將該指標(biāo)下的值進(jìn)行排序，根據(jù)具體問(wèn)題也可不排序.

步驟2依據(jù)數(shù)據(jù)規(guī)模進(jìn)行劃分，可等分成n份或隨機(jī)分割.

步驟3根據(jù)步驟2所得出的指標(biāo)數(shù)值范圍，取各個(gè)劃分下的所有樣本.

步驟4從步驟3中任選1個(gè)樣本，同時(shí)，在其所在劃分中將其刪除.

步驟5計(jì)算步驟4中那例樣本與各個(gè)劃分中所有樣本對(duì)應(yīng)指標(biāo)之差，并求出平方，也可開(kāi)方取正值，對(duì)差值進(jìn)行多準(zhǔn)則聚類分層分析，共計(jì)n個(gè)哈斯圖.根據(jù)各個(gè)哈斯圖高度數(shù)值，即層次數(shù)值，算出每層平均節(jié)點(diǎn)個(gè)數(shù)Ti（i=1，2，…，n）.

步驟6計(jì)算步驟5中每個(gè)哈斯圖超過(guò)本圖Ti的層次個(gè)數(shù)Mi（i=1，2，…，n）.

步驟7計(jì)算步驟6中層次個(gè)數(shù)的總數(shù)即

步驟8得出種類數(shù)P=SUM/n，如此確定類別數(shù).

步驟9取最高層次所有樣本，如果所有哈斯圖最高層都只有一個(gè)節(jié)點(diǎn)，可以將其定為噪聲，否則，取出所有最高層對(duì)應(yīng)的樣本，作為一類.

步驟10循環(huán)步驟6，將取出了高層的各劃分剩余樣本與步驟4中樣本各個(gè)指標(biāo)做差，并求出平方，也可開(kāi)方取正值，再進(jìn)行聚類分層，即再求出n個(gè)哈斯圖，仍然取最高層所有樣本作為一類，并歸并入步驟6所得到的類中，如果某劃分所求出來(lái)的哈斯圖最高層只有一個(gè)節(jié)點(diǎn)，說(shuō)明此劃分對(duì)應(yīng)此類已經(jīng)聚類完畢，下次不用再計(jì)算.

步驟11循環(huán)步驟6、步驟7，直到所有劃分求出哈斯圖后，得出最高層只有一個(gè)節(jié)點(diǎn)時(shí)，此類聚類完畢.

步驟12從剩余各劃分中，任意選出一個(gè)樣本，同時(shí)，在其所在劃分中，將此樣本刪除，重復(fù)步驟5～步驟8，直至聚類結(jié)束.

步驟9中，如果多數(shù)劃分中最高層只有幾個(gè)節(jié)點(diǎn)，根據(jù)BIC準(zhǔn)則，可以認(rèn)定此判別樣本為噪聲，可以舍棄.否則，針對(duì)各劃分的數(shù)據(jù)比例，將高層節(jié)點(diǎn)作為一類.再?gòu)牡诙又腥稳∫粋€(gè)節(jié)點(diǎn)，進(jìn)行本劃分層次聚類，如步驟5.判斷節(jié)點(diǎn)是否基本為其同層或以下順序?qū)?，如果基本符合，說(shuō)明聚類正確，否則，重新選取樣本進(jìn)行聚類.

定義2設(shè)偏序集S為偏序關(guān)系R上的一個(gè)子集，如果都有最小上界和最大下界，則稱S關(guān)于偏序關(guān)系R為一個(gè)格[22].

一個(gè)格是指其任意非空有限子集都有一個(gè)上確界和一個(gè)下確界的偏序集合.一個(gè)形式背景上概念格就是一個(gè)偏序集簇[23].格論是抽象代數(shù)的分支，研究格的性質(zhì)有助于研究偏序集元素之間的分類和聚類.

根據(jù)格的理論，可以定義一個(gè)上確界和下確界，之后，根據(jù)此界限，確定聚類到第幾層，每個(gè)劃分都根據(jù)此上確界進(jìn)行最高層提取，超過(guò)了就不再提取，認(rèn)為聚類完畢，進(jìn)行下一輪聚類，直到所確定的種類全部聚類完畢.其中，上確界及下確界的確定可以依據(jù)數(shù)據(jù)規(guī)模，也可根據(jù)專家經(jīng)驗(yàn)，也可根據(jù)輪廓線理論找到，雖然哪種方式都存在一定主觀性，但對(duì)于融合了人的信息即偏好序的數(shù)據(jù)恰恰是很適用的.

定義3令Pi為每一輪迭代隨機(jī)抽取的樣本，經(jīng)賦權(quán)指標(biāo)加權(quán)比較后，得到各層的子集.最高層各節(jié)點(diǎn)為U1，第二層各節(jié)點(diǎn)為U2，第三層及以后以此類推，可知 ∩Ui=?.

定義4在一個(gè)總體數(shù)量為N的樣本集中，將N合理劃分成n個(gè)不相交子集，每個(gè)子集生成一個(gè)哈斯圖，根據(jù)各個(gè)哈斯圖高度數(shù)值，即層次數(shù)值，算出每層平均節(jié)點(diǎn)個(gè)數(shù)Ti（i=1，2，…，n）.計(jì)算出每個(gè)哈斯圖超過(guò)本圖Ti的層次個(gè)數(shù)Mi（i=1，2，…，n），求出層次個(gè)數(shù)的總數(shù)SUM，則聚類簇?cái)?shù)為P=SUM/n.

定義5在一個(gè)總體為n的樣本集中，若各樣本到某點(diǎn)距離相等，則稱該點(diǎn)為類別中心點(diǎn)，即質(zhì)心點(diǎn)，簡(jiǎn)稱為質(zhì)心[9].

定理1由定義5有聚類簇?cái)?shù)為P=SUM/n，當(dāng)P/n? 1時(shí)為最佳分類簇?cái)?shù).

證明P/n=(SUM/n) /n=SUM/n2，若P/n?1，則有SUM/n2?1，則，n≈SUM

（1）當(dāng)n=1時(shí)，若SUM≤1，則說(shuō)明所有樣本都是一類，此劃分已是最佳劃分，得證.若SUM＞1，因?yàn)槊總€(gè)類別中都是相對(duì)質(zhì)心向外發(fā)散，肯定會(huì)有最密的位置，根據(jù)哈斯圖原理，若有超過(guò)每層平均數(shù)的層，則該層就是一類質(zhì)心附近的點(diǎn)，所以，則最佳分類就是SUM.在數(shù)據(jù)樣本少時(shí)，可以如此確定聚類簇?cái)?shù)，當(dāng)樣本空間無(wú)限增大，此方法不穩(wěn)定.所以，此種情形下，當(dāng)n=1時(shí)，劃分不合理.

（2）當(dāng)n＞1時(shí)，若，則劃分太細(xì)，各劃分內(nèi)的樣本差異性不大，易造成誤判，在樣本空間數(shù)量較小時(shí)，尤其嚴(yán)重；若，說(shuō)明樣本劃分過(guò)于粗糙，各劃分內(nèi)部沒(méi)有突出類別特點(diǎn)，使各個(gè)子圖層次結(jié)構(gòu)復(fù)雜，又顯混亂，在樣本空間較大時(shí)，尤為明顯.

定義6在定義5基礎(chǔ)上，每個(gè)劃分中，第一個(gè)超出各層平均節(jié)點(diǎn)個(gè)數(shù)Ti（i=1，2，…，n）的層命名為質(zhì)心首層.

定理2離Pi越遠(yuǎn)，層級(jí)越低，若與Pi不屬于同一類，則，根據(jù)定義6，節(jié)點(diǎn)必在質(zhì)心首層之下.

證明采用反證法，設(shè)某節(jié)點(diǎn)平行于或高于質(zhì)心首層，那么，此節(jié)點(diǎn)距離Pi較近，距離近，說(shuō)明兩者屬于同一類，與條件矛盾，所以該節(jié)點(diǎn)與Pi不屬于同一類.

定理3最高層與Pi必屬于同一類.

證明采用反證法，假設(shè)最高層屬于多個(gè)類，令U11，…，U1n1，為一類，U1n1+1，…，U1n2為一類，U1n2+1，…，U1n3為一類…，那么，說(shuō)明Pi與多個(gè)類都相近，若從數(shù)值上考究，說(shuō)明Pi處于所有類別的交匯點(diǎn)，即Pi屬于公共點(diǎn)，而在定義中，不涉及公共點(diǎn)問(wèn)題，即只能說(shuō)明Pi為噪聲點(diǎn)，噪聲點(diǎn)應(yīng)該被剔除，除此以外，別無(wú)其他可能，所以，最高層當(dāng)屬同一類，否則與定義不符.證畢.

1.3 算法復(fù)雜度分析

算法復(fù)雜度主要包括時(shí)間復(fù)雜度及空間復(fù)雜度，對(duì)于N個(gè)樣本，d個(gè)指標(biāo)的數(shù)據(jù)集，時(shí)間復(fù)雜度計(jì)算如下.

1.2 節(jié)中步驟1至步驟4，基本為線性運(yùn)算，所以，時(shí)間復(fù)雜度為O(d?N)，步驟5中，算法復(fù)雜度為O(d?N2)，步驟6至步驟11，時(shí)間復(fù)雜度為O(d?N)，步驟12重復(fù)之前的過(guò)程，根據(jù)劃分情況，可估算出其重復(fù)次數(shù)不超過(guò) logd(N)，所以，算法總復(fù)雜度為

空間復(fù)雜度計(jì)算過(guò)程主要采用矩陣運(yùn)算，矩陣階數(shù)就是樣本數(shù)，因?yàn)橹饕沁M(jìn)行樣本比較運(yùn)算，若劃分為P類，則空間復(fù)雜度為

2 算例分析

2.1 多準(zhǔn)則匯總及聚類

經(jīng)過(guò)與對(duì)多名業(yè)務(wù)主管的交流，得知目前銀行貸款類業(yè)務(wù)主要在如下幾方面進(jìn)行考核，考察準(zhǔn)則如下.

（1）抵借比為欠款額與抵押物估值之比，值越大越不好.權(quán)重為ω1.

（2）抵押物價(jià)格波動(dòng)比例系數(shù)為價(jià)格波動(dòng)率的倒數(shù)，如果升值，價(jià)格波動(dòng)率大于1，如果貶值，價(jià)格波動(dòng)率小于1.可根據(jù)需要，每月統(tǒng)計(jì)1次，值越大越不好.權(quán)重為ω2.

（3）擔(dān)保方代償能力為還款額與擔(dān)保方月收入之比，值越大越不好.權(quán)重為ω3.

（4）還款能力為還款額與貸款方月收入之比，值越大越不好.權(quán)重為ω4.

（5）發(fā)生不可抗力情況損失率為損失額與資產(chǎn)總額之比，值越大越不好，比如各類災(zāi)害等.權(quán)重為ω5.

（6）貸款比率為貸款總額與現(xiàn)貸款之比，即（現(xiàn)貸款與其他貸款之和比現(xiàn)貸款，如果沒(méi)有其他貸款，此指標(biāo)值為1，否則大于1，比值越大越不好.權(quán)重為ω6.

（7）資產(chǎn)負(fù)債率由專業(yè)評(píng)估機(jī)構(gòu)核實(shí)并給出，數(shù)值越大越不好.權(quán)重為ω7.

（8）企業(yè)效益增長(zhǎng)比率為上一個(gè)月收入與當(dāng)前月收入之比，此指標(biāo)反映企業(yè)經(jīng)營(yíng)狀況，因?yàn)槠髽I(yè)經(jīng)營(yíng)情況跟季節(jié)等因素有關(guān)，所以這項(xiàng)指標(biāo)可信度最低.權(quán)重為ω8.

將各類貸款人匯總到一起，采用8項(xiàng)指標(biāo).根據(jù)以上指標(biāo)，某商業(yè)銀行提供的數(shù)據(jù)見(jiàn)表1、表2.

表1 某商業(yè)銀行2018年7月貸款方考核數(shù)據(jù)（部分?jǐn)?shù)據(jù)） Tab.1 creditor assessment data of a commercial bank in July 2018 (partial data)

表2 某商業(yè)銀行2018年8月貸款方考核數(shù)據(jù)（部分?jǐn)?shù)據(jù)） Tab.2 creditor assessment data of a commercial bank in August 2018 (partial data)

依據(jù)此權(quán)重順序進(jìn)行偏序集層次聚類.

步驟1指標(biāo)權(quán)重最大的是第4項(xiàng)，貸款人還款能力，依據(jù)該指標(biāo)對(duì)表1進(jìn)行排序.

步驟2將步驟1結(jié)果等分成2份，即兩個(gè)劃分.分別為（P12，P8，P16，P7，P4，P11，P18，P9，P1）和（P2，P5，P3，P13，P6，P10，P14，P17，P15）.

步驟3任選一個(gè)樣本，以P12為例，在其所在劃分中將其刪除.

步驟4計(jì)算P12與各個(gè)劃分中所有樣本對(duì)應(yīng)指標(biāo)之差，并求出平方，進(jìn)而繪制哈斯圖，如圖1、圖2.

圖1 哈斯圖1 Fig.1 Hasse graph 1

圖2 哈斯圖2 Fig.2 Hasse graph 2

步驟5計(jì)算步驟4中，每個(gè)哈斯圖各層平均節(jié)點(diǎn)個(gè)數(shù)Ti，求出超過(guò)Ti的層次個(gè)數(shù)SUM，即SUM=3

步驟6計(jì)算最佳劃分?jǐn)?shù)，， 所以n=2為最佳劃分，即這些數(shù)據(jù)應(yīng)該聚為2類.

步驟7逐層聚類.

步驟8通過(guò)哈斯圖節(jié)點(diǎn)合并，得到P1、P2、P3、P4、P8、P12、P16為一類，P5、P6、P7、P10、P11、P13、P14、P15、P18為一類，P17屬于異常點(diǎn)，與實(shí)際相符.

由以上實(shí)例可知，利用偏序集實(shí)現(xiàn)層次聚類，效果較好.

2.2 呆賬風(fēng)險(xiǎn)識(shí)別

通過(guò)哈斯圖可展現(xiàn)各類借款（貸款）人聚類狀態(tài)，依據(jù)層次信息，對(duì)債務(wù)人進(jìn)行考察.根據(jù)數(shù)據(jù)業(yè)務(wù)規(guī)模，可以通過(guò)單個(gè)或多個(gè)哈斯圖展現(xiàn).文中算例數(shù)據(jù)規(guī)模較小，所以，所有節(jié)點(diǎn)都匯聚在一個(gè)哈斯圖中.

根據(jù)表1，匯總出哈斯圖3.根據(jù)表2，匯總出哈斯圖4.從圖4中可以看出，P1節(jié)點(diǎn)層次發(fā)生了變化，雖然其仍按時(shí)還款，但根據(jù)圖4，可以評(píng)估其還款能力發(fā)生了變化，經(jīng)過(guò)調(diào)研發(fā)現(xiàn)某債務(wù)人因病住院導(dǎo)致公司業(yè)績(jī)受損.所以，當(dāng)節(jié)點(diǎn)層次發(fā)生變化時(shí)，金融部門工作人員應(yīng)該引起警覺(jué)，如果連續(xù)數(shù)月對(duì)應(yīng)節(jié)點(diǎn)所在層次仍然不能回落到初始狀態(tài)層次，則其欠款很可能會(huì)退變?yōu)榇糍~.后來(lái)此債務(wù)人公司倒閉，抵押物變賣用于治療疾病，這導(dǎo)致了呆賬形成.通過(guò)此例，可以總結(jié)出利用偏序集進(jìn)行層次聚類，能夠應(yīng)用于風(fēng)險(xiǎn)識(shí)別.

圖3 基于偏序集的2018年7月貸款方考核數(shù)據(jù)聚類哈斯圖 Fig.3 clustering Hasse graph of creditor assessment data based on partial order set in July 2018

圖4 基于偏序集的2018年8月貸款方考核數(shù)據(jù)聚類哈斯圖 Fig.4 clustering Hasse graph of creditor assessment data based on partial order set in August 2018

3 結(jié)論

（1）構(gòu)建了基于層次聚類算法的多準(zhǔn)則決策模型.通過(guò)劃分格，可得到最佳分類數(shù)，根據(jù)分類數(shù)，將決策結(jié)果劃分層次，由層次信息，可得到最優(yōu)解集.對(duì)關(guān)系矩陣運(yùn)算，生成哈斯矩陣，可得出類與類之間的層級(jí)關(guān)系，也可得出樣本間的層級(jí)關(guān)系.通過(guò)偏序集，可以快速準(zhǔn)確實(shí)現(xiàn)層次聚類，較傳統(tǒng)聚類方法方便快捷，計(jì)算量少.

（2）傳統(tǒng)聚類過(guò)程中，利用不同的距離公式得到不同的聚類結(jié)果，距離計(jì)算會(huì)增加時(shí)間復(fù)雜度.而利用偏序集原理實(shí)現(xiàn)的聚類，可以僅通過(guò)比較關(guān)系得到種類歸屬，時(shí)間復(fù)雜度及空間復(fù)雜度大為降低，通過(guò)層次關(guān)系找到種類歸屬.今后，擬利用偏序集原理實(shí)現(xiàn)更多聚類算法.