基于偏好不一致熵的有序決策

潘 偉，佘 堃

(1.電子科技大學 信息與軟件工程學院，成都 610054； 2.西華師范大學 計算機學院，四川 南充 637009) (*通信作者電子郵箱panwei@cwnu.edu.cn)

基于偏好不一致熵的有序決策

潘 偉1,2*，佘 堃1

(1.電子科技大學 信息與軟件工程學院，成都 610054； 2.西華師范大學 計算機學院，四川 南充 637009) (*通信作者電子郵箱panwei@cwnu.edu.cn)

針對多規則有序決策系統中的偏好決策問題，根據有序決策的偏好不一致特性，提出了一種基于偏好不一致熵的偏好決策方法。首先，定義了樣本的偏好不一致熵(PIEO)，用來度量特定樣本相對于樣本集的偏好不一致程度；然后，根據偏好決策中不同屬性對決策的重要性不同的特點，提出了一種加權的樣本偏好不一致熵，并結合屬性偏好不一致熵在度量屬性重要性方面的能力，給出了一種基于屬性偏好不一致熵的權值的計算方法；最后，提出了一種基于樣本偏好不一致熵的偏好決策算法。采用Pasture Production和Squalsh兩個數據集進行仿真實驗，基于全局偏好不一致熵分類后，各屬性的偏好不一致熵普遍比基于向上和向下偏好不一致熵分類后的熵值小，而且更接近原始決策的偏好不一致熵，這說明基于全局偏好不一致熵的分類比其他兩種情況的分類效果好。分類偏離度最小低至0.128 2,這說明分類的結果比較接近原始決策。

有序決策；偏好不一致熵；分類；偏好關系

0 引言

有序決策問題，即條件屬性和決策屬性均存在序結構的決策問題，是多規則決策中的一類重要問題。在這種系統中，被評估對象往往由一組屬性(條件屬性)描述，在決策分析領域，把這一類問題統稱為多標準有序決策(或偏好分析)問題[1-3]。有序決策問題在實際應用中廣泛出現，如投稿論文的錄用決策、人力資源考核、信譽評估、投資風險分析以及學生評定等。

對于有序決策問題，通常分為兩種情況。一種是偏好一致的有序決策，在這種系統中，隱含的一致性假設為，條件屬性值越大的對象，其決策往往也更好。比如在學生評定系統中，如果學生甲與學生乙其他各方面的表現都完全相同，但學生甲的創新能力比學生乙強，那么，如果學生乙被評定為優秀，那么學生甲也應該評為優秀。另一種就是偏好不一致的有序決策。在這種系統中，存在一些對象，其擁有更好的條件屬性值，但其決策卻更差。對于偏好一致的有序決策系統，決策方法比較簡單，但在現實應用當中，由于可用信息的多規則和多源性，更多地是偏好不一致的情況。顯然，由于偏好的不一致性，導致其決策往往具有不確定性。

1948年，Shannon[4]指出，任何信息都存在冗余，冗余大小與信息中每個符號(數字、字母或單詞)的出現概率或者說不確定性有關，并借鑒了熱力學的概念，定義了信息熵來表示信息中排除了冗余后的平均信息量。從此，信息熵成為了度量不確定性的重要工具，許多研究者把信息熵拓展到了各種不同領域，定義了各種各樣的信息熵[5-8]。在有序決策研究領域，2009年，Hu等[9]提出排序熵和排序互信息的概念，并且應用排序互信息來啟發式構建有序決策樹[10]。此算法較好地體現出序的結構信息，但是此算法在擴展屬性選取時，需度量每個屬性取值，在大規模的訓練集且樣例的每個屬性取值不同的情況下，其計算復雜度會很高[11]。文獻[12]定義了偏好不一致熵，用來度量多規則有序決策中各屬性由于偏好不一致帶來的決策不確定程度，并將其應用于特征選擇和樣本壓縮。該熵是基于屬性的，熵值的大小能夠反映出該條件屬性對決策的重要程度。

本文借鑒文獻[12]的基本思想，基于有序決策的基本目標，定義了一種新的偏好不一致熵(樣本的偏好不一致熵)。樣本的偏好不一致熵能夠表示每一個樣本的偏好不一致程度。一個樣本被賦予不同的決策，它的偏好不一致熵也是不一致的。熵值越大，表示該決策會導致較大的不確定性；熵值越小，該決策就越趨合理。在多規則決策中，不同的屬性的重要程度是不一樣的。本文以文獻[12]提出的偏好不一致熵作為屬性重要度加權，提出了一種多規則有序決策方法。

1 偏好關系與偏好不一致熵

在這一部分，將簡單介紹文獻[12]中介紹和定義的偏好關系與偏好不一致熵等基本概念。

1.1 偏好關系

一個決策系統是一個元組PS=〈U,C∪D〉，其中，U是非空對象集，C={a1,a2,…,am}是條件屬性集，D={d1,d2,…,dn}是決策集。如果d1

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

其中：f{x,a}是對象x在屬性a的取值，f{x,D}是對象x的決策。R≥和R>均被稱為向上的偏好關系，R≤和R<均被稱為向下的偏好關系。

根據偏好關系的定義，偏好信息粒子被定義為：

(9)

(10)

(11)

(12)

1.2 偏好不一致熵

定義1[12]給定偏好不一致的有序決策系統PS=〈U,C∪D〉，U是非空對象集，C={a1,a2,…,am}是條件屬性集，D={d1,d1,…,dn}是決策集。?x∈U,A?C，其向上的偏好不一致集和向下的偏好不一致集可分別表示為uiconS(x,a)和diconS(x,a)。

(13)

(14)

可以很容易地得到如下結論。

uiconS(x,a∪b)=uiconS(x,a)∩uiconS(x,b)

(15)

diconS(x,a∪b)=diconS(x,a)∩diconS(x,b)

(16)

定義2[12]給定偏好不一致的有序決策系統PS=〈U,C∪D〉。?A?C,x∈U，偏好不一致度(PICD)可以定義為：

向上偏好不一致度：

upicd(x,A)=|uiconS(x,A)|/|U|

(17)

向下偏好不一致度：

dpicd(x,A)=|diconS(x,A)|/|U|

(18)

對于偏好不一致度，?a1,a2?C有如下公式成立。

upicd(x,a1)≥upicd(x,a1∪a2)

(19)

upicd(x,a2)≥upicd(x,a1∪a2)

(20)

dpicd(x,a1)≥upicd(x,a1∪a2)

(21)

dpicd(x,a2)≥upicd(x,a1∪a2)

(22)

偏好不一致度反映了有序決策系統中樣本x的條件屬性a與決策的偏好不一致程度：值越大，不一致程度就越高；值越小，一致度就越高；值為0，則表明屬性與決策完全一致。屬性與決策的偏好不一致，導致了決策的不確定性。

(23)

用偏好不一致度代替香農信息熵中的概率p,可得到偏好不一致熵。

定義3[12]給定偏好不一致的有序決策系統PS=〈U,C∪D〉，U是非空對象集，C={a1,a2,…,am}是條件屬性集，D={d1,d1,…,dn}是有序決策集。?A?C，屬性A的偏好不一致熵(Preference Inconsistence-based Entropy, PIE)能被定義為：

向上的偏好不一致熵：

(24)

向下的偏好不一致熵：

(25)

定義3定義的偏好不一致熵能度量屬性與決策的偏好不一致所引起的決策不確定性大小。由定義3可以看出，偏好不一致熵都是大于或等于0的。偏好不一致熵大于0則表示該屬性(或屬性子集)與決策是偏好不一致的。熵值越大，屬性(或屬性子集)與決策是偏好不一致度就越大，由此屬性作出決策的不確定性就越大。熵等于0則表示該屬性與決策是偏好一致的，決策的偏好對該屬性是確定的。顯然，熵值越小，屬性與決策的一致度就越高，屬性對決策的影響就越大，該屬性對決策就越重要，因此，基于屬性的偏好不一致熵的特征選擇和屬性約簡是合適的。

偏好分析的一個重要任務是偏好決策。也就是說，給定一個未知決策的樣本，需要以訓練樣本集為參照，通過分析樣本條件屬性的偏好，為其賦予一個最合適的類標簽。對于樣本分類，需要度量樣本與整個樣本集的一致程度，顯然，定義3定義的基于屬性的偏好不一致熵不具有這方面的能力。在下文將定義樣本的偏好不一致熵，并將其應用于樣本分類。

2 樣本的偏好不一致熵與偏好決策

定義4 給定偏好不一致的有序決策系統PS=〈U,C∪D〉，U是非空對象集，C={a1,a2,…,am}是條件屬性集，D={d1,d1,…,dn}是有序決策集。?x∈U，定義樣本x的偏好不一致熵(Preference Inconsistence-based Entropy of Object, PIEO)如下。

向上的偏好不一致熵：

(26)

向下的偏好不一致熵：

(27)

全局偏好不一致熵：

(28)

與屬性的偏好不一致熵度量的是特定屬性或屬性集合在偏好決策中的重要程度不同，樣本的偏好不一致熵反映的是特定樣本與整個訓練樣本集的偏好不一致程度。熵值越小，樣本與訓練樣本集的一致度就越大。在有監督的偏好決策中，為測試樣本賦予不同的類別，其偏好不一致熵通常是不一樣的，偏好不一致熵最小的決策應為最優決策。

在多規則決策系統中，不同的條件屬性對決策的影響通常是不一樣的。定義4的樣本的偏好不一致熵沒有考慮不同屬性對決策影響的差異。通過前面的分析可以知道，定義3給出的屬性的偏好不一致熵能夠有效反映屬性對決策的重要程度。熵值越小，屬性對決策越重要。用屬性的偏好不一致熵進行加權，可以得到樣本的偏好不一致熵的改進形式。

定義5 給定偏好不一致的有序決策系統PS=〈U,C∪D〉，U是非空對象集，C={a1,a2,…,am}是條件屬性集，D={d1,d1,…,dn}是有序決策集。?x∈U，定義樣本x的加權的偏好不一致熵(weighted Preference Inconsistence-based Entropy of Object, wPIEO)如下。

向上的偏好不一致熵：

(29)

向下的偏好不一致熵：

(30)

全局偏好不一致熵：

(31)

(32)

(33)

其中:N為大于max(1/AH(a))(AH(a)≠0時)的常數，AH為定義3定義的關于屬性的偏好不一致熵。計算UWH時，AH為UAH；計算DWH時，AH為DAH。AH(a)=0，表明屬性a與決策偏好一致，其重要性非常高，因此需要為其賦予更大的權值，通常取N取3～5倍的max(1/AH(a))。

對于偏好不一致有序決策系統PS=〈U,C∪D〉，?x∈U, 為x賦予不同的類標簽，樣本x的偏好不一致熵通常是不一樣的。顯然 ，樣本x的最佳決策應該使樣本x的偏好不一致熵最小，即:

(34)

其中，OH表示樣本的偏好不一致熵。對于向上的偏好決策，OH為UOH；對于向上的偏好決策，OH就為DOH。

下面將給出一種基于樣本偏好不一致熵的樣本分類算法。

算法1 基于PIEO的樣本分類算法(CPIEO)。

算法的時間復雜度為O(n)(n為決策系統條件屬性的個數)。由于樣本的類別通常都只有有限的幾項，因此該算法的時間消耗主要由偏好不一致熵的時間決定。如果希望決策盡可能好，則可以用向上的偏好不一致熵進行計算；如果希望決策盡可能差，則應用向下的偏好不一致熵進行計算；否則，應該用全局的偏好不一致熵進行計算。

3 實驗分析

本文從WEKA(http://www.cs.waikato.ac.nz/ml/weka/)下載了兩個數據集：PastureProduction和SquashHarvest。將基于這兩個數據集通過實驗來分析本文所提出的偏好決策算法的性能和有效性。為此，針對有序決策系統的特點，本文定義了分類偏離度和分類偏好一致度來度量分類的效果。

定義6 假設PS=〈U,C∪D〉是偏好不一致有序決策系統。其中，U是非空對象集，C={a1,a2,…,am}是條件屬性集，D={d1,d1,…,dn}是決策集。?x∈U，c(x)是對象x被賦予的類標簽，o(x)是對象x的原始類標簽。本文定義分類偏離度為：

(35)

定義7 假設PS=〈U,C∪D〉是偏好不一致有序決策系統，U是非空有限對象集，C={a1,a2,…,am}是條件屬性集，D={d1,d1,…,dn}是決策集。?x∈U，c(x)是對象x被賦予的類標簽，o(x)是對象x的原始類標簽。本文定義分類偏好一致度如下。

向上的分類一致度：

(36)

向下的分類一致度：

(37)

在分類問題中，通常用分類的準確度來評價一個算法的優劣，但具體到多規則的有序決策問題中，除了要分析分類的準確度之外，還需要分析決策的決策者的偏好問題，因此，本文定義了分類偏離度和偏好一致度分別從這兩個維度來對決策算法進行分析。分類偏離度反映的是分類結果與測試樣本原始類別的偏離程度，分類偏離度越小，分類的準確度就越高，算法就越好。分類偏好一致度度量的是分類結果與原始決策的偏好一致程度，分類偏好一致度越大，算法就越能反映決策者的偏好，算法也就越好。下面，就用這兩個指標來對分析提出的算法的有效性。

數據集PastureProduction是由DaveBarker在1973—1994年間從北島地區收集的，其目的是要分析各種生物和物理因素對牧場生產的影響。該數據集收集了36個樣本，每個樣本記錄了一個圍場的相關數據。每個樣本包括22個屬性，其中19個是植被情況，其余3個分別表示土壤的化學成分、物理和生物特性，以及土壤水分變化。所有的記錄都被分成了三個類別，高、中、低，分別表示該圍場的產量情況。

數據集SquashHarvest是由新西蘭的一家作物與食品研究機構收集的。收集該數據集的目的是為了研究南瓜在成熟和運輸過程中的各種變化，以確定最佳的采摘時間，以便在運到日本市場后能有最好的口感。SquashHarvest數據集共采集了52個樣本，每個樣本包括24個屬性指標。樣本的質量被分為了不可接受、可接受和很好三個等級。為便于計算和處理，分別用1、2和3來分別表示這三個等級。為便于表示，把數據集PastureProduction的條件屬性依次標記為1，2，3，…，21，22，把數據集SquashHarvest的條件屬性依次標記為1，2，3，…，23，24。

為了便于比較，用基于屬性的偏好不一致熵(PIE)來度量各種情況下的分類效果。圖1～4展示了SquashHarvest和PastureProduction兩個數據集在原始決策、基于全局偏好不一致熵分類、基于向上偏好不一致熵和向下偏好不一致熵分類情況下各屬性的偏好不一致熵。其中的曲線為各種情況下得到的屬性的偏好不一致熵的包絡。從圖1和圖3可以看出，基于全局偏好不一致熵分類后，各屬性的向上偏好不一致熵與原始決策的向上偏好不一致熵非常接近(甚至有部分屬性的向上偏好不一致熵比原始決策的向上偏好不一致熵更小)，而從圖2和圖4則可以發現各屬性的向下偏好不一致熵普遍比原始決策的向下偏好不一致熵略大，這說明這兩個數據集的原始決策均是基于向上的偏好做出的;同時還可以看出，基于全局偏好不一致熵分類后，其各屬性的偏好不一致熵普遍比基于向上和向下偏好不一致熵分類后的熵值小，而且更接近原始決策的偏好不一致熵，這說明基于全局偏好不一致熵的分類比其他兩種情況的分類效果好。

圖1 向上的偏好不一致熵(Squash)

表1是SquashHarvest和PastureProduction兩個數據集在各種情況下進行分類的分類偏離度和分類偏好一致度的比較。其中，RWH表示樣本的全局偏好不一致熵，UWH表示樣本的向上偏好不一致熵，DWH表示樣本的向下偏好不一致熵。

表1 不同偏好不一致熵方法分類效果比較

表1的第2和第5行是基于樣本的全局偏好不一致熵得到的結果，第3和第6行是基于樣本的向上偏好不一致熵得到的結果，第4和第7行是基于樣本的向下偏好不一致熵得到的結果。從表1可以看出：各種情況下的分類偏離度都不大，最低為0.128 2，最大為0.282 1，這說明各種情況下的偏好決策均與原始決策比較接近；而由于原始決策的偏好不一致，各種情況下的分類偏好一致度波動相對較大，但均大于0.5，這說明分類結果與原始決策的偏好是基本一致的。

圖2 向下的偏好不一致熵(Squash)

圖3 向上的偏好不一致熵(Pasture)

圖4 向下的偏好不一致熵(Pasture)

4 結語

針對偏好不一致有序系統中的樣本決策問題，基于偏好信息粒子和樣本的偏好不一致度，定義了樣本的偏好不一致熵，并擴展到加權的偏好不一致熵，進而提出了樣本的偏好決策算法。為了評價算法的有效性，依據偏好決策的特點，定義了分類偏離度和分類偏好一致度來度量偏好決策的合理性。采用PastureProduction和SquashHarvest兩個數據集進行仿真實驗。實驗結果表明，提出的方法在解決偏好不一致有序決策系統中的樣本分類問題方面具有較好的效果，當基于全局偏好不一致熵進行分類時，能夠得到與原始決策比較接近的結果；但是，在實驗中也發現，由于偏好的不一致導致了決策的不確定性，分類的準確度不是很高。在以后的工作中，將進一步對相關的模型和算法進行分析，研究提高分類準確度的方法。

)

[1]BASZCZYNSKIJ,GRECOS,SOWINSKIR.Multi-criteriaclassification—anewschemeforapplicationofdominance-baseddecisionrules[J].EuropeanJournalofOperationalResearch, 2007, 181(3): 1030-1044.

[2]WANGYM,PARKANC.OptimalaggregationoffuzzypreferencerelationswithanapplicationtobroadbandInternetserviceselection[J].EuropeanJournalofOperationalResearch, 2008, 187(3): 1476-1486.

[3] 徐澤水.基于不同類型殘缺判斷矩陣的群決策方法[J].控制與決策,2006,21(1):28-33.(XUZS.Groupdecisionmakingmethodbasedondifferenttypesofincompletejudgmentmatrices[J].ControlandDecision, 2006, 21(1): 28-33.)

[4]SHANNONCE.Amathematicaltheoryofcommunication[J].BellSystemTechnicalJournal, 1948(3): 379-423, 623-656.

[5]YANGJ,QIUW.Ameasureofriskandadecision-makingmodelbasedonexpectedutilityandentropy[J].EuropeanJournalofOperationalResearch, 2005, 164(3): 792-799.

[6]ZENGK,SHEK,NIUX.Multi-granulationentropyanditsapplication[J].Entropy, 2013, 15: 2288-2302.

[7]HUQH,YUDR.Neighborhoodentropy[C]//Proceedingsofthe2009InternationalConferenceonMachineLearningandCybernetics.Piscataway,NJ:IEEE, 2009,3: 1776-1782.

[8]LOTFIFH,FALLAHNEJADR.ImpreciseShannon’sentropyandmultiattributedecisionmaking[J].Entropy, 2010, 12: 53-62.

[9]HUQ,GUOM,YUD,etal.Informationentropyforordinalclassification[J].ScienceChina(InformationSciences), 2010, 53(6): 1188-1200.

[10]HUQ,CHEX,ZHANGL,etal.Rankentropy-baseddecisiontreesformonotonicclassification[J].IEEETransactionsonKnowledgeandDataEngineering, 2012, 24(11): 2052-2064.

[11] 陳建凱,王熙照,高相輝.改進的基于排序熵的有序決策樹算法[J].模式識別與人工智能,2014,27(2):134-140.(CHENJK,WANGXZ,GAOXH.Improvedordinaldecisionstreesalgorithmsbasedonrankentropy[J].PatternRecognitionandArtificalIntelligence, 2014, 27(2): 134-140.)

[12]PANW,SHEK,WEIP.Preferenceinconsistence-basedentropy[J].Entropy, 2016, 18: 96.

ThisworkispartiallysupportedbytheNaturalScienceFoundationoftheEducationDepartmentofSichuanProvince(12ZA178),theKeyTechnologySupportProgramofSichuanProvince(2015GZ0102),theFoundationofVisualComputingandVirtualRealityKeyLaboratoryofSichuanProvince(KJ201406).

PAN Wei, born in 1976, Ph. D. candidate, associate professor. His research interests include rough set, granular computing, cloud computing and knowledge discovery.

SHE Kun, born in 1967, Ph. D., professor. His research interests include intelligent cloud, secure cloud and big data analysis.

Ordered decision-making based on preference inconsistence-based entropy

PAN Wei1,2*, SHE Kun1

(1.SchoolofInformationandSoftwareEngineering,UniversityofElectronicScienceandTechnologyofChina,ChengduSichuan610054,China; 2.ComputerSchool,ChinaWestNormalUniversity,NanchongSichuan637009,China)

Aiming at the problem of preference decision in multi-rule ordered decision-making system, according to the preference inconsistency of ordered decision-making, a preference decision-making method based on preference inconsistent entropy was proposed. Firstly, the Preference Inconsistence Entropy of Object (PIEO) was defined and used to measure the degree of preference inconsistency for a particular sample relative to the sample set. Then, according to that different attributes have different importances to the preference decision, a weighted Preference Inconsistence-based Entropy of Object (wPIEO) was proposed. Moreover, combining wPIEO with attribute preference inconsistency entropy in measuring attribute importance, a weighting method based on attribute preference inconsistent entropy was proposed. Finally, a preference decision algorithm based on sample preference inconsistent entropy was proposed. Two data sets, Pasture Production and Squalsh, were used to simulate the experiment. After the global Preference Inconsistent Entropy (gPIE) classification, the preference inconsistent entropy of each attribute was generally smaller than the entropy value based on the preference inconsistent entropy classification based on the up and down preferences, and it was closer to the preference inconsistent entropy of the original decision, which indicates that the classification based on gPIE was better than the other two cases. The classification deviation was as low as 0.128 2, indicating that the classification results are close to the original decision.

ordered decision-making; preference inconsistence-based entropy; classification; preference relation

2016- 08- 26;

2016- 10- 14。

四川省教育廳自然科學基金重點資助項目(12ZA178)；四川省重大項目支撐計劃項目(2015GZ0102)；四川省可視計算和虛擬現實重點實驗室建設基金資助項目(KJ201406)。

潘偉(1976—)，男，四川武勝人，副教授，博士研究生，主要研究方向：粗糙集、粒計算、云計算和知識發現； 佘堃(1967—)，男，四川成都人，教授，博士生導師，博士，CCF會員，主要研究方向：智能云、安全云、大數據。

1001- 9081(2017)03- 0796- 05

10.11772/j.issn.1001- 9081.2017.03.796

TP18

A