隨機信息系統(tǒng)屬性重要性的等價刻畫及其約簡

方連花， 李克典

（漳州師范學院 數(shù)學與信息科學系，福建 漳州 363000）

隨機信息系統(tǒng)屬性重要性的等價刻畫及其約簡

方連花， 李克典

（漳州師范學院 數(shù)學與信息科學系，福建 漳州 363000）

在基于等價關系的隨機信息系統(tǒng)中，文章以證據(jù)理論中的信任測度和似然測度為基本工具，給出了核心屬性、不必要屬性及相對必要屬性的一些等價刻畫，研究了隨機目標信息系統(tǒng)的屬性約簡問題，并利用實例說明了約簡方法的有效性。

隨機信息系統(tǒng)；核心屬性；不必要屬性；相對必要屬性；屬性約簡

證據(jù)理論又稱信度函數(shù)論，是研究認識不確定性問題的另一種理論。Dempster于1967年給出了上、下概率的概念，第1次明確給出了不滿足可加性的“概率”。1968年，Dempster針對統(tǒng)計問題給出了2批證據(jù)合成的原則，文獻［1］在Dempster工作的基礎上正式提出了證據(jù)理論，因此證據(jù)理論也稱為Dempster－Shafer理論或D－S證據(jù)理論。粗糙集理論［2］是近年來發(fā)展起來的一種處理不精確性、不確定性和模糊知識的軟計算工具，是繼概率論、模糊集及證據(jù)理論后的又一個刻畫不完整性和不確定性的數(shù)學工具。

粗糙集理論與證據(jù)理論是處理不確定性知識的工具，處理不確定性問題的研究方法是不同的，但卻有著某種相容性和很強的互補性。近年來，將粗糙集理論與證據(jù)理論相結合，研究隨機信息系統(tǒng)的知識發(fā)現(xiàn)問題成為一個有活力的研究方向，并且取得了一定的研究成果［3－9］。文獻［10］利用粗糙集理論研究了信息系統(tǒng)中屬性重要性的等價刻畫，文獻［11］利用證據(jù)理論研究了隨機目標信息系統(tǒng)的約簡問題，其中辨識矩陣是以單一元素為比較對象，計算量過大。

在前人研究的基礎上，本文以證據(jù)理論中的信任測度和似然測度為基本工具，討論了隨機信息系統(tǒng)中的核心屬性、不必要屬性和相對必要屬性的一些等價刻畫；構造了以等價類為比較對象的簡化辨識矩陣，為研究協(xié)調與不協(xié)調隨機目標信息系統(tǒng)的屬性約簡問題減少了工作量，從而進一步豐富和完善了證據(jù)理論。

1 基礎知識

定義1 設（U，A，F(xiàn)）為信息系統(tǒng)，若在U上有正規(guī)概率分布P，即對于任意的x∈U，有P（｛x｝）＞0，則稱（U，A，F(xiàn)）為隨機信息系統(tǒng)［9］，記為（（U，P），A，F(xiàn)）。

定義3 若集函數(shù)Bel：p（W）→［0，1］滿足［9］Bel（?）＝0，Bel（W）＝1，?｛Y1，Y2，…，Yn｝?p（W），則有：

其中，?≠I?｛1，2，…，n｝，則稱Bel為W上的一個信任測度。

定義4 若集函數(shù) Pl：p（W）→［0，1］滿足［9］Pl（?）＝0，Pl（W）＝1，?｛Y1，Y2，…，Yn｝?p（W），則有：

其中，?≠I?｛1，2，…，n｝，則稱Pl為W上的一個似然測度。

定義5 設（（U，P），A，F(xiàn)）為隨機信息系統(tǒng)，對于任意B?A，x∈U，記

則H（B）＝ ｛［x］B：x∈U｝為U上的劃 分，m（［x］B）＝P（［x］B）為U上的 mass函數(shù)。特別地，m（［x］B）＝｜［x］B｜／｜U｜（x∈U）為由U上均勻分布產生的mass函數(shù)。

在證據(jù)理論中有一對重要的數(shù)值型測度，即信任測度與似然測度，而在粗糙集理論中有一對非數(shù)值型的算子，即下近似算子與上近似算子，它們之間有著密切的聯(lián)系。在粗糙集理論中，如果下近似算子與上近似算子滿足關系：

則稱下近似算子與上近似算子是對偶的。

在證據(jù)理論中，如果信任測度Bel與似然測度Pl滿足：

則稱信任測度Bel與似然測度Pl是對偶的。

定理1 設（U，R）為Pawlak近似空間，則由它導出的下近似算子與上近似算子是對偶的，對于（U，σ（U／R））上的任何正規(guī)概率［11］P（?E∈σ（U／R），P（E）＝0當且僅當E＝?），記為U上一對對偶的信任測度與似然測度，其對應的mass函數(shù)為：

2 屬性重要性的等價刻畫

隨機信息系統(tǒng)中的不同屬性對于劃分的作用是不同的，有的屬性對于劃分是必不可少的，有的屬性在劃分中是可以被其他屬性代替的，有的屬性對于劃分是根本不需要的。因此，本文研究了對劃分起不同作用的屬性，給出其相應的特征。

定義6 設I＝（U，A，F(xiàn)）為一個信息系統(tǒng)，對于B?A，若RB＝RA，稱B為劃分協(xié)調集。若B為劃分協(xié)調集，而B的任何真子集均不是劃分協(xié)調集，則稱B為劃分約簡集［12］。

將信息系統(tǒng)中的屬性分類后，便于研究不同屬性的各自特征。在信息系統(tǒng)中，有核心屬性、不必要屬性及相對必要屬性的等價刻畫定理。

定理2 設（U，A，F(xiàn)）為信息系統(tǒng)，則有［10］：

（1）a為劃分核心，當且僅當RA－｛a｝≠RA。

（2）a為劃分不必要屬性，當且僅當R（a）?Ra，其中R（a）＝∪｛RB－｛a｝｜RB?RA，B?A｝。

（3）a為劃分相對必要屬性，當且僅當RA－｛a｝＝RA成立，且R（a）?Ra不成立。

定理3 設（U，A，F(xiàn)）為信息系統(tǒng)，則有：

（1）a為劃分核心，當且僅當RA－｛a｝?Ra不成立。

（2）a為劃分不必要屬性或者劃分相對必要屬性，當且僅當RA－｛a｝?Ra成立。

證明 由定理2知，a為劃分核心，當且僅當RA－｛a｝≠RA，即RA－｛a｝?／RA，而RA＝RA－｛a｝∩Ra，故有RA－｛a｝?Ra不成立，所以a為劃分不必要屬性或者劃分相對必要屬性，當且僅當RA－｛a｝?Ra成立。

定理4 設（（U，P），A，F(xiàn)）為隨機信息系統(tǒng)［11］，對于屬性 集B?A，U／RA＝ ｛C1，C2，…，Ct｝，則以下3個條件等價：

定理5 設（（U，P），A，F(xiàn)）為隨機信息系統(tǒng)［11］，令U／RA＝｛C1，C2，…，Ct｝，則以下3個條件等價：

（1）B?A為（U，A，F(xiàn)）的約簡集。

定理6 設（（U，P），A，F(xiàn)，D，G）為協(xié)調的隨機目標信息系統(tǒng)［11］，U／RD＝｛D1，D2，…，Dr｝，B?A，則以下3個條件等價：

定理7 設（（U，P），A，F(xiàn)，D，G）為協(xié)調的隨機目標信息系統(tǒng)［11］，U／RD＝｛D1，D2，…，Dr｝，則以下3個條件等價：

（1）B?A為（U，A，F(xiàn)，D，G）的約簡集。

定理8 設（（U，P），A，F(xiàn)）為隨機信息系統(tǒng)，對于屬性集B?A，RB＝RA，U／RA＝｛C1，C2，…，Ct｝，則有：

若RB－（a）?Ra，則?x∈U有［x］B－｛a｝?［x］a。

記JB－｛a｝（Ei）＝ ｛［x］B－｛a｝∈U／RB－｛a｝：［x］B－｛a｝?Ei｝，則JB－｛a｝（Ei）為Ei的一個分劃，且?x∈U，［x］B－｛a｝∩Ei≠??［x］B－｛a｝?Ei。則

這說明對于任意的i≤s，有：

（3）由（1）和（2）即可得證。

定理9 設（（U，P），A，F(xiàn)）為隨機信息系統(tǒng)，對于屬性集B?A，RB＝RA，U／RA＝｛C1，C2，…，Ct｝，則有：

證明 類似于定理8的證明。

定理10 設（（U，P），A，F(xiàn)）為隨機信息系統(tǒng)，U／Ra＝｛E1，E2，…，Es｝，則有：

由定理3和定理6可得：

例1 根據(jù)屬性特征的等價刻畫定理，求隨機信息系統(tǒng)I＝（（U，P），A，F(xiàn)）的屬性特征，其中m（［x］B）＝P（［x］B）＝｜［x］B｜／｜U｜，x∈U。隨機信息系統(tǒng)見表1所列。

表1 隨機信息系統(tǒng)

根據(jù)定義求得表1中隨機信息系統(tǒng)的劃分為：

其中，C1＝｛x1，x3｝；C2＝｛x2｝；C3＝｛x4，x5，x7｝；C4＝｛x6，x8｝。

令B＝A－｛a1｝，則有：

于是通過計算得：

所以有：

由定理8和定理9知，a1為該隨機信息系統(tǒng)的劃分核心。

令B1＝｛a1，a3｝，B2＝｛a1，a4｝，B3＝｛a3，a4｝，則有U／＝U／＝U／RA。

又因為U／＝｛E1，E2｝＝｛｛x1，x3｝，｛x2，x4，x5，x6，x7，x8｝｝，則通過計算得：

所以有：

由定理8和定理9知，a4為該隨機信息系統(tǒng)的劃分不必要屬性，同理可求得其相對必要屬性為a3、a4。

3 隨機目標信息系統(tǒng)的屬性約簡

按照屬性特征將對象進行分類是知識發(fā)現(xiàn)的本質問題，然而所有屬性對于隨機信息系統(tǒng)的分類并不是同等重要的。去掉不重要的屬性后并不影響分類的知識發(fā)現(xiàn)，該屬性為冗余屬性。隨機信息系統(tǒng)的屬性約簡是在保持知識庫的分類能力不變的條件下，刪除其中的冗余屬性。屬性約簡簡化了分類的標準，同時也使人們更加深入地認識了分類的實質。

在隨機信息系統(tǒng)（（U，P），A，F(xiàn)）中，U／RA＝｛C1，C2，…，Ct｝。記H＝｛（Ci，Cj）：i＞j｝，則H中的元素個數(shù)為｜H｜＝t（t－1）／2。

用fa（Ci）表示類Ci中對象關于a的屬性值，記r（Ci，Cj）＝｛a∈A：fa（Ci）≠fa（Cj）｝，j（B）＝｛（Ci，Cj）：r（Ci，Cj）＝B，（i＞j）｝。

設P為H上的均勻分布，則m（B）＝P（j（B））（B?A）為A上的mass函數(shù)，從而得到A上的信任測度Bel與似然測度Pl分別為：

定理11 設（（U，P），A，F(xiàn)）為隨機信息系統(tǒng)，則以下3個條件等價［11］：

（1）B?A為（（U，P），A，F(xiàn)）的約簡集。

（2）Pl（B）＝1，且對于任意B′?B有Pl（B′）＜1。

（3）Bel（～B）＝0，且對于任意B′?B有Bel（～B′）＞0。

本文首先研究協(xié)調隨機目標信息系統(tǒng)的屬性約簡問題。在文獻［11］中，它的辨識矩陣是以單個元素為比較對象的，此時要比較的對象過多。因此考慮以等價類為比較對象，重新給出辨識矩陣的定義。

定義8 對于協(xié)調隨機目標信息系統(tǒng)（（U，P），A，F(xiàn)，D，G），對任意的xs∈Ci，xt∈Cj，r（Ci，Cj）的定義如下：

記H＝｛（Ci，Cj）：i＞j｝，則｜H｜＝n（n－1）／2，其中｜U｜＝n。

對于任意的B?A，記

則m（B）＝｜j（B）｜／｜H｜為A上的 mass函數(shù)，從而得到信任測度Beld與似然測度Pld分別為：

定理12 設（（U，P），A，F(xiàn)，D，G）為協(xié)調的隨機目標信息系統(tǒng)，則以下3個條件等價：

（1）B?A為（U，A，F(xiàn)，D，G）的約簡集。

（2）Pld（B）＝1，且對于任意B1?B有Pld（B1）＜1。

（3）Beld（～B）＝0，且對于任意B1?B有Beld（～B1）＞0。

由Pld與Beld的對偶性易證“（2）?（3）”。

例2 考慮文獻［11］中給出的隨機目標信息系統(tǒng)（（U，P），A，F(xiàn)，D，G）的約簡，其中辨識矩陣以等價類為比較對象，并與文獻［11］中的方法進行比較。由計算可以得到r（Ci，Cj）（i＞j）的矩陣見表2所列，由于矩陣是對稱的，本文只寫出1／2的元素。

表2 辨識矩陣

于是可得：

從而有：

則｛a1，a2｝和｛a2，a3｝都是約簡，但｛a1，a3｝不是約簡。

根據(jù)定理11可進一步確定分別決定D1、D2和D3的約簡，其中，D1＝｛x1，x3，x9｝，D2＝｛x2，x4，x7，x10｝，D3＝｛x5，x6，x8｝。

假定用約簡｛a1，a2｝，在表2中分別用B′1＝｛a2｝代替B1，B′2＝｛a1｝代替B2，B′3＝｛a1，a2｝代替B3。對于D1＝｛x1，x3，x9｝，在表2的第1列總共有4個，于是 mass函數(shù)為m1（B′1）＝1／4，m1（B′2）＝2／4，m1（B′3）＝1／4。

同理，對于D2和D3也分別有mass函數(shù)：m2（B′1）＝1／3，m2（B′3）＝2／3，m3（B′2）＝2／7，m3（B′3）＝ 5／7。 于 是 Pl1（｛a1，a2｝）＝ 1，Pl2（｛a2｝）＝1，Pl3（｛a1｝）＝1，也即｛a1，a2｝決定了d＝1，｛a2｝決定了d＝2，｛a1｝決定了d＝3。

顯然，這與文獻［11］得到的結論是一致的。雖然它們的時間復雜度是一樣的，但是由此得到的辨識矩陣比文獻［11］中的要簡化，而且也減少了比較對象，從而降低了工作量。

對于不協(xié)調隨機目標信息系統(tǒng)的屬性約簡問題，許多學者從不同角度對其進行了研究。文獻［4］利用不協(xié)調隨機目標信息系統(tǒng)的分布約簡、最大分布約簡、分配約簡等方法來研究其上的約簡問題，文獻［11］將其轉化成協(xié)調的隨機目標信息系統(tǒng)來進行約簡。本文采用文獻［11］中的方法，通過將不協(xié)調隨機目標信息系統(tǒng)轉化成協(xié)調隨機目標信息系統(tǒng)，然后根據(jù)例2中的方法來研究協(xié)調隨機目標信息系統(tǒng)的約簡問題。

4 結束語

隨機信息系統(tǒng)中的不同屬性對于劃分的作用是不同的，因此研究屬性特征的等價刻畫及刪除其中的冗余屬性問題是很有意義的。本文結合粗糙集理論和證據(jù)理論，研究了隨機信息系統(tǒng)中屬性特征的等價刻畫，并構造了以等價類為比較對象的簡化辨識矩陣，研究了協(xié)調與不協(xié)調隨機目標信息系統(tǒng)的屬性約簡問題。

［1］Shafer G.A mathematical theory of evidence［M］.Prince－ton：Princeton University Press，1976：1－35.

［2］Pawlak Z.Rough sets：theoretical aspects of reasoning about data ［M］.Boston：Kluwer Academic Publishers，1991：1－30.

［3］周 彤，張家錄.隨機信息系統(tǒng)屬性相關性及在知識約簡中的應用［J］.計算機工程與應用，2011，47（14）：140－143.

［4］肖 文，王正友，王耀德.基于信任優(yōu)勢的不確定多屬性決策方法 ［J］.合肥工業(yè)大學學報：自然科學版，2010，33（9）：1401－1405.

［5］江效堯，程玉勝，胡林生.基于極大相容塊的粗糙性度量及其屬性約簡［J］.合肥工業(yè)大學學報：自然科學版，2012，35（4）：476－480.

［6］成蓉華，吳兆兵.隨機信息系統(tǒng)中基于不可辨識矩陣的屬性約簡［J］.云南民族大學學報：自然科學版，2007，16（4）：324－326.

［7］邱旭琴，魏立力.優(yōu)勢關系下隨機信息系統(tǒng)的屬性約簡［J］.計算機工程與應用，2011，47（2）：131－135.

［8］邱衛(wèi)根，胡志斌.基于隨機集的合成信息系統(tǒng)粗集模型［J］.計算機工程，2011，37（9）：210－212.

［9］張文修，吳偉志.基于隨機集的粗糙集模型：Ⅰ［J］.西安交通大學學報，2000，34（12）：75－79.

［10］張文修，仇國芳，吳偉志.粗糙集屬性約簡的一般理論［J］.中國科學：E輯，2005，35（12）：1304－1313.

［11］張文修，梁 怡，吳偉志.信息系統(tǒng)與知識發(fā)現(xiàn)［M］.北京：科學出版社，2003：134－175.

［12］張文修，仇國芳.基于粗糙集的不確定決策［M］.北京：清華大學出版社，2005：1－60.

Equivalent characterization of the importance of attribute and its reduction in random information systems

FANG Lian－h(huán)ua， LI Ke－dian
（Dept.of Mathematics and Information Science，Zhangzhou Normal University，Zhangzhou 363000，China）

By means of the belief measure and the plausibility measure in the evidence theory，the equivalent characterization of the importance of core attribute，unnecessary attribute and relatively necessary attribute in the equivalent relation based random information systems is discussed.And then the attribute reduction in the random objective systems is studied.Finally，an example is used to illustrate the validity of this method.

random information system；core attribute；unnecessary attribute；relatively necessary attribute；attribute reduction

TP18

A

1003－5060（2013）02－0165－06

10.3969／j.issn.1003－5060.2013.02.009

2012－07－11

國家自然科學基金資助項目（10971185；10971186；71140004）；福建省省屬高校科研專項資助項目（JK2011031）

方連花（1986－），女，安徽黃山人，漳州師范學院碩士生；

李克典（1956－），男，河南柘城人，漳州師范學院教授，碩士生導師.

（責任編輯 閆杏麗）