方連花， 李克典

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

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

方連花， 李克典

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

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

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

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

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

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

1 基礎(chǔ)知識(shí)

定義1 設(shè)（U，A，F(xiàn)）為信息系統(tǒng)，若在U上有正規(guī)概率分布P，即對(duì)于任意的x∈U，有P（｛x｝）＞0，則稱（U，A，F(xiàn)）為隨機(jī)信息系統(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上的一個(gè)信任測(cè)度。

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

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

定義5 設(shè)（（U，P），A，F(xiàn)）為隨機(jī)信息系統(tǒng)，對(duì)于任意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上均勻分布產(chǎn)生的mass函數(shù)。

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

則稱下近似算子與上近似算子是對(duì)偶的。

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

則稱信任測(cè)度Bel與似然測(cè)度Pl是對(duì)偶的。

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

2 屬性重要性的等價(jià)刻畫

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

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

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

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

（1）a為劃分核心，當(dāng)且僅當(dāng)RA－｛a｝≠RA。

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

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

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

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

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

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

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

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

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

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

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

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

定理8 設(shè)（（U，P），A，F(xiàn)）為隨機(jī)信息系統(tǒng)，對(duì)于屬性集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的一個(gè)分劃，且?x∈U，［x］B－｛a｝∩Ei≠??［x］B－｛a｝?Ei。則

這說明對(duì)于任意的i≤s，有：

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

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

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

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

由定理3和定理6可得：

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

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

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

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

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

于是通過計(jì)算得：

所以有：

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

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

又因?yàn)閁／＝｛E1，E2｝＝｛｛x1，x3｝，｛x2，x4，x5，x6，x7，x8｝｝，則通過計(jì)算得：

所以有：

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

3 隨機(jī)目標(biāo)信息系統(tǒng)的屬性約簡

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

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

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

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

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

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

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

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

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

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

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

對(duì)于任意的B?A，記

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

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

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

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

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

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

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

表2 辨識(shí)矩陣

于是可得：

從而有：

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

根據(jù)定理11可進(jìn)一步確定分別決定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。對(duì)于D1＝｛x1，x3，x9｝，在表2的第1列總共有4個(gè)，于是 mass函數(shù)為m1（B′1）＝1／4，m1（B′2）＝2／4，m1（B′3）＝1／4。

同理，對(duì)于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。

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

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

4 結(jié)束語

隨機(jī)信息系統(tǒng)中的不同屬性對(duì)于劃分的作用是不同的，因此研究屬性特征的等價(jià)刻畫及刪除其中的冗余屬性問題是很有意義的。本文結(jié)合粗糙集理論和證據(jù)理論，研究了隨機(jī)信息系統(tǒng)中屬性特征的等價(jià)刻畫，并構(gòu)造了以等價(jià)類為比較對(duì)象的簡化辨識(shí)矩陣，研究了協(xié)調(diào)與不協(xié)調(diào)隨機(jī)目標(biāo)信息系統(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］周 彤，張家錄.隨機(jī)信息系統(tǒng)屬性相關(guān)性及在知識(shí)約簡中的應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（14）：140－143.

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

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

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

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

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

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

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

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

［12］張文修，仇國芳.基于粗糙集的不確定決策［M］.北京：清華大學(xué)出版社，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

國家自然科學(xué)基金資助項(xiàng)目（10971185；10971186；71140004）；福建省省屬高?？蒲袑ｍ?xiàng)資助項(xiàng)目（JK2011031）

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

李克典（1956－），男，河南柘城人，漳州師范學(xué)院教授，碩士生導(dǎo)師.

（責(zé)任編輯 閆杏麗）