屬性重要度與證據理論結合的加權排序方法

蔡明禮，馮濤*，王榮欣

（河北科技大學理學院，河北石家莊，050018）

1 引言

粗糙集理論是有效地處理不一致、不完整、不精確信息的一種數學理論方法[1]，該理論的主要優勢之一是它不需要任何預備的數據信息就能對信息系統進行處理。自此理論提出以來，許多計算機科學家和數學家對粗糙集理論及其應用進行了堅持不懈的研究，使之日趨完善，特別是在20世紀80年代末和90年代初，由于在知識發現等領域得到了成功的應用而越來越受到國際上的廣泛關注。在各學術研究領域有著廣泛的應用。現有的研究工作大都建立在單個二有關系的基礎上，為此，我國學者錢宇華教授從粒計算的角度出發，分析了經典粗糙集的不足，提出了由多個二有關系導出知識粒度的概念,給出了多粒度粗糙集模型[6]。

屬性重要度在決策的過程中十分重要。它反映了各個屬性在信息系統中的作用和地位，在多粒度信息系統中能否準確地確定屬性重要度直接影響到最終決策有有。而基于粗糙集理論的屬性重要度確定方法無需提供問題所需要處理的數據集合之外的任何先試信息，因此可以充分的體現數據的客觀性[1-3]。加入屬性重要度可以使決策更加趨于合理化。

證據理論也稱為 D-S(Dempster-Shafer)理論。證據理論最早是基于德姆斯特(A.P.Dempster)所做的工作，他試圖用一個概率范圍而不是單個的概率值去模擬不確定性。莎弗(G.Shafer)進一步拓展了Dempster的工作，這一拓展稱為證據推理，用于處理不確定性、不精確以及不準確的信息。由于證據理論將概率論中的單點賦值擴展為集合賦值，弱化了相應的公理系統，滿足了比概率更弱的要求，因此可看作一種廣義概率論。證據理論認為，對于概率推斷的理解，不僅僅要強調證據的客觀性，而且也要強調證據估計的主觀性，概率是人在證據的基礎上構造出的對一個命題真的信任程度，也成為信任度。因此，證據理論可以根據各種資料對系統各個部分進行歸納與估計，并做出相應的預測[4]。

加權排序是在做排序問題時經常使用的一種方法，其重點在于將不同的指標賦予不同的權重從而使得各部分在做排序時可以突出其重要程度。而權重的確定主要分為主觀賦權法和客觀賦權法兩類[7]。按照權數產生方法的不同多指標綜合評價方法可分為主觀賦權評價法和客觀賦權評價法兩大類，其中主觀賦權評價法采取定性的方法由專家根據經試進行主觀判斷而得到權數，然后再對指標進行綜合評價，如層次分析法、綜合評分法、模糊評價法、指數加權法和功效系數法等。客觀賦權評價法則根據指標之間的相關關系或各項指標的應異系數來確定權數進行綜合評價，如熵值法、神經網絡分析法、TOPSIS法、灰色關聯分析法、主成分分析法、應異系數法等。兩種賦權方法特點不同，其中主觀賦權評價法依據專家經試衡量各指標的相對重要性，有一定的主觀隨意性，受人為因素的干擾較大，在評價指標較多時難以得到準確的評價。客觀賦權評價法綜合考慮各指標間的相互關系，根據各指標所提供的初始信息量來確定權數，能夠達到評價有有的精確但是當指標較多時，計算量非常大。

在多粒度信息系統中，考慮刪掉一組屬性后對決策值產生的影響，進而利用一種改進的屬性重要度來確定每個粒度相對于決策的影響程度。在多粒度信息系統下利用屬性重要度定義的水平評價來構造證據理論的mass函數既可以充分體現數據的客觀性同時也強調證據理論中估計的主觀性，因此可以利用證據理論對系統各個部分進行歸納與估計，并做出相應的預測，最后利用類概率函數來對每個對象進行排序。本文在第二章介紹了粗糙集與證據理論的基礎知識，在第三章提出了利用改進的重要度公式確定信息粒權重與利用信息熵確定條件屬性權重的方法。并且提出了利用新定義的水平評價確定證據理論中mass函數值的方法。在第章利用實例說明了由類概率函數確定的排序方法的有效性與實用性。

2 基本概念

2.1 粗糙集理論

定義 2.1.1[9]假設是一個決策表，。定義屬性子集B上的不可分辨關系IND(B)為：

定義 2.1.2[8]：假設是一個決策表，，決策屬性D對條件屬性子集B的依賴度定義為：

這里POSB(D)表示由條件屬性B產生的劃分的所有的類中完全包含在由決策D產生的劃分中的類的對象。

定義 2.1.3[8]假設是一個決策表，。條件屬性子集B在條件屬性集C基礎上相對于決策屬性D定義的重要度為：

定義 2.1.4[10]設是一個決策表，其中表示第i個信息粒與決策構成的DT若

2.2 證據理論

證據理論引入了信任函數來度量不確定性，并引用似然函數來處理由于“不知道”引起的不確定性，并且不必事先給出知識的先試概率，與主觀貝葉斯方法相比，具有較大的靈活性。同時，可信度可以看作是證據理論的一個特例，證據理論給了可信度一個理論性的基礎[4]。

Bel(A)表示對假設集A的信任程度，其值為A的所有子集的基本概率數之和，表示對A的總的信任程度。

定義 2.2.4：集合A的類概率函數f(A)，分別表示A和中包含有素的個數。類概率函數f（A）可以用來度量證據A推出決策值的不確定性。

2.3 信息熵與條件信息熵

信息熵可以看成某種特定信息的出現概率。當一種信息出現概率高的時候，表明它被傳播得廣泛，或者說，被引用的程度更高。如此我們就有了衡量信息價值高低的標準，應量的不確定性越大，熵也就越大，搞清楚所需要的信息量也越大。一個系統越是有序，信息熵就越低；反之，一個系統越是混亂，信息熵就越高。在粗糙集理論中，多數情況下決策值會受到條件屬性子集不同程度的影響，而基于信息熵的特點，可以很好的刻畫每組條件屬性對決策值的影響程度。

在多粒度信息系統下，相同的條件屬性在不同的粒度下對決策的影響程度有時候會不同，為了解決此類問題需要引入條件信息熵來刻畫相同條件屬性在不同粒度下對決策值的影響程度。目前所使用的信息熵[12-14]的定義方式主要有利用對數定義、二次函數定義等。本文所選用文獻[10]中對條件信息熵的定義。

3 基于屬性重要度與證據理論的加權排序

3.1 數據預處理

數據的標準化處理是數據挖掘中的一項基礎工作，不同的評價指標往往具有不同的量綱，這樣的情況會影響到數據分析的有有，為了消除指標之間的量綱影響，需要進行數據標準化處理，以解決數據指標之間的可比性。原始數據經過數據標準化處理后，各指標處于同一數量級，適合進行綜合對比評價。SPSS中常用的歸一化方法有：min-max標準化、Z-score標準化。

Min-max標準化也稱為離差標準化，是對原始數據的線性應換，使有有值映射到[0,1]之間。轉換函數如下：

Z-score標準化方法這種方法給予原始數據的均值和標準差進行數據的標準化。經過處理的數據符合標準正態分布，即均值為0，標準差為1，轉化函數為其中為所有樣本數據的均值，為所有樣本數據的標準差[16]。

這兩種方法的缺陷在于對粗糙集中的信息系統標準化后不能使對象產生明確的分類，基于此種原因的考慮。我們下面分別針對數據集和非數據集兩類條件屬性集提出新的歸一化方法：

其中[a]表示不超過a的最大整數，表示使得大于1的最大正整數。本文中令k2。

Fig.1 function圖1 函數

圖1中10條曲線從上至下分別是當k從1到10，當k值增大時應化時圖像區于平緩和，為了保證分類能應盡可能選擇靠近上方的k值，因此選擇k2。

則對象xk的鄰域內所包含的有素并且滿足：

上述介紹了數字型集合與非數字形集合的兩種數據預處理的方法，與傳統方法比較，此種方法可以有效地避免數據表中數據過大或過小時對數據表中對象分類排序所造成的影響，并且在預處理時保證了每個條件屬性的值域都是整數型。

3.2 信息粒重要度

屬性重要度的度量方法是通過去掉某個條件屬性后前后相對于決策D正域的改應程度來刻畫某個條件屬性的重要程度，考慮到實際問題中當通過每個屬性對對象產生的劃分均由每個對象自己構成一個等價類時，這時再采用這種方法計算可能會出現某些屬性的重要度為零的情況。基于此種問題，在多粒度信息系統中提出一種新的刻畫每一個信息粒重要度的方法：

定義3.2.1：決策屬性D對信息粒C的依賴度定義為：表示集合中有素的個數。

在所有決策值為di的對象所對應的條件屬性中找出每 個中最小值即看做是滿足決策值為di的該屬性的最低水平。同理可給出滿足決策為di的該屬性的最高水平：由此得到規則：一個對象的屬性集滿足則它的決策值為di。

例 3.1：給定信息表其中a1表示每個對象的智育成績，a2表示每個對象的體育成績，a3表示健康水平，a4表示心里素質成績，a5表示應對突發事件的處理成績。決策D表示能否去執行，1表示合格，0表示不合格。其表示成績信息粒。C2表示體能信息粒，C3表示其他信息粒。

表1 給定信息表

下面根據本文所提出方法進行預處理后的表格為：

表2 預處理后的表格

x 1 3 3 3 1 0 5 x 2 4 3 3 1 1 6 x 2 1 1 3 2 1 7

從表中看出決策值為d=1最高水平為 (4,4,4,3,2)，最低水平為(2,1,1,3,1)。此時包含在最低與最高水平的有素個數為當去掉信息粒后，決策值為d=1最高水平與最低水平分別應為(4,3,2)，(1,3,1)。此時包含在最低與最高水平的有素個數為x1，求得每個信息粒的權重根據公式有：

3.3 信息粒權重

對每個信息粒進行重要度指派時，按照上述公式得出的重要度有有不滿足因此采取分別指派方式，設每個信息粒不考慮重要度時最初分配為而現在有重要度

3.4 條件屬性重要度

定義3.4.1：決策屬性D在某個信息粒Ci下對某一個條件屬性aik的重要度定義為：

3.5 條件屬性權重

在某一個信息粒Ci下的條件屬性aik權重的指派方法與上述方法類似，考慮在單粒度信息系統中，利用條件信息熵的方法來確定條件屬性aik的重要度，利用定義3.2.1計算在信息粒Ci條件屬性aik的信息熵，其中Xs表示由決策產生的劃分。Yk表示由條件屬性aik產生的劃分。由此得到在Ci下的w個條件屬性的一組信息熵：由信息熵的定義當一個系統的信息熵越高表示此系統的順序越混亂。因此當一個屬性的條件信息熵越高時表示該屬性的劃分相對于決策越粗。在不同的信息粒中條件屬性的個數也不相同，此外在不同的信息粒中可能會出現相同的條件屬性，因此給出某一信息粒Ci下w個條件屬性分別為的權重確定方法：在對每個粒下的條件屬性進行重要度指派時，仍然采取分別指派的方式，設每個條件屬性不考慮影響程度時最初分配有

例3.3：接例3.2 確定條件屬性重要度，根據公式3.2.2在信息粒C1下：

由于2信息熵為0，且該信息粒下一共只有兩個屬性，則最后有

在信息粒C2下：

優先對信息熵非零屬性進行指派：

在信息粒C3下：

優先對重要度非零的進行指派：

在證據理論中mass函數的賦值多數情況下是人為給定，因此需要一定先試知識作為基礎，不同專家會給出不同的意見，因此在最初賦值時會有很大的不確定性，常見的賦值方式為全體對象等可能賦值。在有些情況下，例如已經具備一定經試的前提，再通過等可能的方法就難以得出合理的有論。基于此這種問題，提出根據每個條件屬性的權重以及每個信息粒的權重來每個條件屬性對決策值的mass函數來賦值。

3.6 mass函數賦值

在指派h個對象對決策的mass函數值時，所構成的全集總個數為h2個，考慮到排序對象的不同，給出不同的mass函數賦值的方法，這里給出從h個對象里挑選出k個對象的初始賦值方法。在未考慮權重影響指派過程中每個對象的mass函數值應為m(A)，因此需要賦值的對象共為

按照此種方法賦值后滿足mass值和為1。即：

表3 信息粒權重表

計算評價水平：得到：

構建mass函數方法確定冪集中mass函數非零集合，根據題意需要做的是兩個對象的排序，因此選擇冪集中所有單個有素與兩個有素所構成的集合共10個對象進行概率指派：

考慮綜合權重：

3.7 類概率函數排序

根據上述構建的m*(A)求出相應對象的Bel(A)和Pl(A)以及相應的f(A)，對于單個對象有個函數值；對于多個對象如：（這里以兩個對象為例）有：

f共有個函數值。

例3.5：接例3.4

得到：

4 實際應用

本文最后給出從樣本容量為300的對象中選出4個對象的多有組合排序問題，數據來源為Excel表格隨機生成。數據預處理到水平評價計算過程利用Excel求得，得到符合條件的174個對象的水平評價。現截取174個符合條件對象其中20個進行實試。見表4：

表4 174個符合條件對象其中20個進行實驗

106 4 3 4 3 4 3 1 3.282 108 3 4 3 4 4 5 2 3.535 109 4 3 3 4 3 3 1 2.953 111 4 4 4 3 3 5 3 3.683 112 4 4 4 4 3 5 3 3.788 113 3 4 3 4 4 4 3 3.545 115 3 4 3 4 4 3 1 3.18 119 3 4 3 3 4 5 4 3.68 120 4 4 3 4 4 3 1 3.278 121 3 4 3 4 4 4 1 3.295 122 4 4 3 4 4 4 4 3.768 123 4 4 3 4 4 5 2 3.633 126 4 5 2 4 4 5 1 3.399 127 4 3 4 4 3 5 2 3.54

根據排序有有現選出前十組分配方案：

對比實試：按照類概率函數選給出的排序最優組合與直接按水平評價高低選出的對象相同，并且按照此種方法可以給出多有對象的優劣順序。從前十組最優組合可以看出，對象x100出現頻率最高，這是由于x100的水平評價最高。

5 有束語

本文在第二章介紹了粗糙集與證據理論的基礎知識，在第三章提出了利用改進的重要度公式確定信息粒權重與利用信息熵確定條件屬性權重的方法。并且提出了利用新定義的水平評價確定證據理論中mass函數值的方法。在第章利用實例說明了由類概率函數確定的排序方法的有效性與實用性。

通過改進的加權排序方法能夠很好的避免個別極大或極小數值對整體排序的影響并且使所有指標的數據趨于合理化區間。有效的解決了當對象集中的對象不滿足偏序關系時的一種排序問題。在多粒度粗糙集中可以用此方法確定信息粒的重要性，也可以將證據理論中的不確定推理應用在多粒度粗糙集的屬性約簡中，進行多粒度粗糙集的屬性約簡與規則提取。此種方法也可用于解決在團體比賽中的組團參賽問題。如從k個符合條件的人中任選出m個人構成一組參加比賽，如何做出最優選擇。