屬性重要度與證據(jù)理論結(jié)合的加權(quán)排序方法

蔡明禮，馮濤*，王榮欣

（河北科技大學(xué)理學(xué)院，河北石家莊，050018）

1 引言

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

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

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

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

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

2 基本概念

2.1 粗糙集理論

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

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

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

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

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

2.2 證據(jù)理論

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

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

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

2.3 信息熵與條件信息熵

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

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

3 基于屬性重要度與證據(jù)理論的加權(quán)排序

3.1 數(shù)據(jù)預(yù)處理

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

Min-max標(biāo)準(zhǔn)化也稱為離差標(biāo)準(zhǔn)化，是對原始數(shù)據(jù)的線性應(yīng)換，使有有值映射到[0,1]之間。轉(zhuǎn)換函數(shù)如下：

Z-score標(biāo)準(zhǔn)化方法這種方法給予原始數(shù)據(jù)的均值和標(biāo)準(zhǔn)差進(jìn)行數(shù)據(jù)的標(biāo)準(zhǔn)化。經(jīng)過處理的數(shù)據(jù)符合標(biāo)準(zhǔn)正態(tài)分布，即均值為0，標(biāo)準(zhǔn)差為1，轉(zhuǎn)化函數(shù)為其中為所有樣本數(shù)據(jù)的均值，為所有樣本數(shù)據(jù)的標(biāo)準(zhǔn)差[16]。

這兩種方法的缺陷在于對粗糙集中的信息系統(tǒng)標(biāo)準(zhǔn)化后不能使對象產(chǎn)生明確的分類，基于此種原因的考慮。我們下面分別針對數(shù)據(jù)集和非數(shù)據(jù)集兩類條件屬性集提出新的歸一化方法：

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

Fig.1 function圖1 函數(shù)

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

則對象xk的鄰域內(nèi)所包含的有素并且滿足：

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

3.2 信息粒重要度

屬性重要度的度量方法是通過去掉某個條件屬性后前后相對于決策D正域的改應(yīng)程度來刻畫某個條件屬性的重要程度，考慮到實際問題中當(dāng)通過每個屬性對對象產(chǎn)生的劃分均由每個對象自己構(gòu)成一個等價類時，這時再采用這種方法計算可能會出現(xiàn)某些屬性的重要度為零的情況?；诖朔N問題，在多粒度信息系統(tǒng)中提出一種新的刻畫每一個信息粒重要度的方法：

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

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

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

表1 給定信息表

下面根據(jù)本文所提出方法進(jìn)行預(yù)處理后的表格為：

表2 預(yù)處理后的表格

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)。此時包含在最低與最高水平的有素個數(shù)為當(dāng)去掉信息粒后，決策值為d=1最高水平與最低水平分別應(yīng)為(4,3,2)，(1,3,1)。此時包含在最低與最高水平的有素個數(shù)為x1，求得每個信息粒的權(quán)重根據(jù)公式有：

3.3 信息粒權(quán)重

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

3.4 條件屬性重要度

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

3.5 條件屬性權(quán)重

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

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

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

在信息粒C2下：

優(yōu)先對信息熵非零屬性進(jìn)行指派：

在信息粒C3下：

優(yōu)先對重要度非零的進(jìn)行指派：

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

3.6 mass函數(shù)賦值

在指派h個對象對決策的mass函數(shù)值時，所構(gòu)成的全集總個數(shù)為h2個，考慮到排序?qū)ο蟮牟煌?，給出不同的mass函數(shù)賦值的方法，這里給出從h個對象里挑選出k個對象的初始賦值方法。在未考慮權(quán)重影響指派過程中每個對象的mass函數(shù)值應(yīng)為m(A)，因此需要賦值的對象共為

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

表3 信息粒權(quán)重表

計算評價水平：得到：

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

考慮綜合權(quán)重：

3.7 類概率函數(shù)排序

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

f共有個函數(shù)值。

例3.5：接例3.4

得到：

4 實際應(yīng)用

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

表4 174個符合條件對象其中20個進(jìn)行實驗

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

根據(jù)排序有有現(xiàn)選出前十組分配方案：

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

5 有束語

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

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