一種改進的先驗概率粗集模型

陶 志，劉彩平

（中國民航大學理學院，天津 300300）

一種改進的先驗概率粗集模型

陶 志，劉彩平

（中國民航大學理學院，天津 300300）

基于容差關(guān)系和先驗概率容差關(guān)系的粗糙集模型是粗糙集理論的重要擴充，但卻均有其局限性。本研究結(jié)合上述兩種模型的優(yōu)點，提出了一種改進的先驗概率粗糙集模型，新模型是建立在對不完備決策系統(tǒng)屬性值統(tǒng)計數(shù)據(jù)的基礎(chǔ)上，既考慮了同一屬性取值的不同情況，又考慮到不同屬性之間的關(guān)聯(lián)性，可以有效提高分類精度和分類的合理性。該模型對屬性間存在明顯的關(guān)聯(lián)性且未知屬性值較少的系統(tǒng)具有很強的實用性。

粗糙集；不完備決策系統(tǒng)；改進的容差關(guān)系

粗糙集理論自1982年由波蘭學者Z.Pawlak提出以來[1]已被廣泛應(yīng)用于數(shù)據(jù)挖掘、人工智能、模式識別、機器學習及智能信息處理等領(lǐng)域。但Pawlak所提出的理論是基于信息系統(tǒng)是完備的這樣一個假設(shè)，而實際問題中由于數(shù)據(jù)采集手段及數(shù)據(jù)精度要求不同等原因，使得需處理更多的是不完備信息系統(tǒng)，即系統(tǒng)中的部分屬性值是未知的。這就要求對經(jīng)典的粗糙集理論進行擴充。目前，對不完備信息系統(tǒng)的處理主要有兩種方法：一種是間接法，即通過領(lǐng)域?qū)＜野阉笔У臄?shù)據(jù)補齊[2]，間接地把不完備信息系統(tǒng)轉(zhuǎn)化為完備系統(tǒng)；第二種是直接法，即直接把粗糙集理論中的相關(guān)概念在不完備信息系統(tǒng)中進行擴充[3-7]。間接法因為有領(lǐng)域?qū)＜业膮⑴c而主觀性比較強，而直接法由于其相對比較客觀，因此引起學者的廣泛關(guān)注。

針對不完備信息系統(tǒng)，目前主要提出了容差關(guān)系和相似關(guān)系兩種擴充模型[3-4]，以及對這兩種模型的改進形式（如限制容差關(guān)系[5]、限制非對稱相似關(guān)系[6]等）?；谏鲜鰞煞N改進模型，又有學者提出先驗限制容差關(guān)系粗糙集模型[7]和先驗限制非對稱相似關(guān)系粗糙集模型等基于先驗概率的粗集模型。然而，上述基于先驗概率的粗糙集模型對已知信息只考慮了單個屬性內(nèi)部的縱向比較，由單個屬性上屬性值出現(xiàn)的概率來確定該屬性中未知屬性的取值，卻忽略了各屬性間的聯(lián)系，對同一元素的其他已知屬性值不進行考查，因而造成了信息的浪費。事實上，許多屬性之間并不是相互獨立的，而是相互制約、相互推定的，即條件屬性之間也有決策關(guān)系存在。例如，中國法律規(guī)定男性公民到了22周歲才能登記結(jié)婚，那么對于一個婚姻情況未知的人，可以根據(jù)他的已知屬性年齡小于22歲以及他是男性推斷出他是未婚的。即使所得到的信息系統(tǒng)中婚姻狀況里出現(xiàn)概率最大的是已婚，也不能簡單按婚姻狀況的先驗概率確定這個人的婚姻狀況為已婚。這個例子說明，在對先驗信息進行處理時還應(yīng)該橫向參考這個元素的其他已知屬性值。本文通過對現(xiàn)有先驗概率粗集模型的研究，提出一種基于屬性間依賴關(guān)系的改進先驗概率容差關(guān)系，并討論了改進的先驗概率容差關(guān)系粗糙集模型的特點及其相關(guān)性質(zhì)。新模型對已知信息的利用更加充分，既提高了分類精度又使分類更趨合理，為不完備信息系統(tǒng)的數(shù)據(jù)處理提供了一種有效的新方法。

1 基本概念

1.1 不完備決策系統(tǒng)

對于四元組S=（U，AT=C∪D，V，f），U是對象的非空有限集合；AT=C∪D是屬性的非空有限集合，C稱為條件屬性集合，D稱為決策屬性集合，且C∩D= ?；?a∈AT，Va表示屬性a的值域；V=∪a∈ATVa表示AT的值域；f為U×AT→V的一個映射，f（x，a）= a（x）∈Va是對象x在屬性a上的取值。若至少存在一個屬性a∈C使a（x）=*，則稱S=（U，AT=C∪D，V，f）是一個不完備決策系統(tǒng)。

1.2 容差關(guān)系

Kryszkiewicz提出的容差關(guān)系認為未知屬性值僅僅是被遺漏但又是確實存在的，因此，“*”被解釋為一個任何可能的屬性值。

定義1 在不完備決策系統(tǒng)S=（U，AT=C∪D，V，f）中，若所有未知屬性值均被認為是遺漏形的（用“*”表示），則由屬性集A?C決定的容差關(guān)系為[3]：TA（x，y）??a∈A，a（x）=a（y）∨a（x）=*∨a（y）=*，x，y∈U。

顯然容差關(guān)系具有自反性和對稱性，但不滿足傳遞性。

定義2 在不完備決策系統(tǒng)S=（U，C∪D）中，對象集合X?U關(guān)于屬性集A?C基于容差關(guān)系的上近似集下近似集和近似精度分別為

其中

顯然

由于容差關(guān)系過于寬松，因此會將兩個明顯不相似的對象判定在同一個容差類中，進而造成不合理分類。為提高同一分類中兩個對象間的相似程度，朱顥東等人依據(jù)概率統(tǒng)計知識提出了基于先驗概率容差關(guān)系的粗集模型[7]，從而有效地提高了分類精度。

1.3 先驗概率容差關(guān)系

在不完備決策系統(tǒng)S=（U，C∪j5i0abt0b，V，f）中，對于任意一個屬性ai∈C，Vi={vi1，vi2，…，vimi}表示ai的值域，Pi={pi1，pi2，…，pimi}表示值域Vi中各個值出現(xiàn)的頻率，mi表示該屬性值域的大小，那么對象x，y在屬性ai∈C上的相似度為

相似度用來度量兩個對象間的相似程度，相似度越高說明兩對象在某個屬性上的相似性越高。

定義3 在不完備決策系統(tǒng)S=（U，AT=C∪D，V，f）中，由屬性A?AT所決定的先驗概率容差關(guān)系為：T（A）?RA（x，y）≥τ，x，y∈U。其中τ是預先設(shè)定好的閾值表示對象x和y在屬性集A上的相似度。

如果兩個對象在某一屬性集上的相似度大于某一閾值，即認為其滿足先驗概率容差關(guān)系，否則就認為不滿足。

定義4 在不完備決策系統(tǒng)S=（U，AT=C∪D，V，f）中，對象集合X?U關(guān)于屬性集A?C基于先驗概率容差關(guān)系的上近似集下近似集和近似精度分別為

先驗概率容差關(guān)系在確定未知屬性值時，僅從縱向上參考該屬性的已知取值，沒有考慮屬性之間的關(guān)聯(lián)性，因此會造成對未知屬性值的片面推斷和分類的不合理性。例如，已知有60個人，其中30個歐洲人，20個非洲人，10個亞洲人，且有一個亞洲人的膚色未知，如果按照先驗概率容差關(guān)系，那么這個亞洲人的膚色被定為白色或者黑色的可能性最大。但是，判斷這個人的膚色實際上不應(yīng)該參考所有人的膚色，而是應(yīng)該參考已知的9個亞洲人的膚色，這樣才更加合理?；谶@個思想，提出了改進的先驗概率容差關(guān)系，新關(guān)系全面均衡地考慮了屬性間的相互關(guān)聯(lián)及已知和未知屬性對相似性的影響，從而使對象間的分類更趨合理，分類精度也得到進一步提高。

2 改進的先驗概率容差關(guān)系

定義5 在不完備決策系統(tǒng)S=（U，AT=C∪D，V，f）中，由A?C所決定的改進先驗概率容差關(guān)系為

顯然，改進的先驗概率容差關(guān)系是自反的、對稱的，但不一定是傳遞的。

定義6 在不完備決策系統(tǒng)S=（U，AT=C∪D，V，f）中，對象集合X?U關(guān)于屬性集A?C基于改進的先驗概率容差關(guān)系的上近似集下近似集

3 改進的先驗概率容差關(guān)系的性質(zhì)

定理1 設(shè)S=（U，AT=C∪D，V，f）是一個不完備決策系統(tǒng)，由A?C決定的改進先驗概率容差關(guān)系為IT（A），則對于任意X，Y∈U，有：

證明由上、下近似定義直接驗證即得。

該定理表明，改進先驗概率容差關(guān)系的上、下近似集合保持原集合的包含關(guān)系不變。

定理2 設(shè)S=（U，AT=C∪D，V，f）是一個不完備決策系統(tǒng)，A?C，X?U，對于由A決定的容差關(guān)系TA和改進的先驗概率容差關(guān)系IT（A），下列關(guān)系成立：

證明顯然，對于?x，y∈U

而且

由定理2知，改進的先驗概率容差關(guān)系與容差關(guān)系相比減小了不確定性邊界，從而提高了分類精度。

4 實例分析

表1所示為一個不完備決策系統(tǒng)，a1，a2，a3，a4代表條件屬性，d是決策屬性。U/ind（d）={φ，ψ}，其中：φ={u1，u2，u3，u5，u6，u9，u10}，ψ={u4，u7，u8，u11，u12}。

表1 不完備決策系統(tǒng)Tab.1 Incomplete decision system

現(xiàn)在分別用文中所述的3種粗集模型來處理這個實例。

首先對于容差關(guān)系有

近似精度

對于先驗概率容差關(guān)系，如果取閾值τ=0.3，則有

由于對象u1和u2的后三個屬性值均相同，只有u2的第一個屬性值未知，按照常理他們不可區(qū)分的可能性非常大，但根據(jù)先驗概率容差關(guān)系模型他們卻是可區(qū)分的，這顯然不太符合實際和人在分類中的主觀感受（u7和u9及u10和u11也有類似情況）。改進的先驗概率容差關(guān)系恰好克服了上述不合理性。綜上，進一步驗證了改進的先驗概率容差關(guān)系既克服了容差關(guān)系分類過于粗糙的缺陷、提高了分類近似精度，又彌補了先驗概率容差關(guān)系分類的不足。

5 結(jié)語

本文分別分析了基于容差關(guān)系和先驗概率容差關(guān)系的粗糙集模型，并針對先驗概率容差關(guān)系模型在處理未知屬性時只參考已知縱向信息而對橫向信息運用不足的缺陷，提出一種改進的先驗概率容差關(guān)系，并在此基礎(chǔ)上建立了相應(yīng)的粗集擴充模型。新模型與容差關(guān)系模型相比提高了對象間的相似程度和分類精度，同時又克服了先驗概率容差關(guān)系模型在分類上的缺陷。通過實例演算，進一步驗證了改進的先驗概率容差關(guān)系的優(yōu)點。一般在信息系統(tǒng)數(shù)據(jù)量較大、屬性間存在明顯關(guān)聯(lián)關(guān)系且未知屬性值所占比重較小時，用這種模型進行數(shù)據(jù)處理和分析是可行且具有優(yōu)勢的。下一步應(yīng)在本文提出的改進先驗概率容差關(guān)系的基礎(chǔ)上，進一步研究不完備系統(tǒng)中屬性約簡和規(guī)則抽取算法，為實際應(yīng)用系統(tǒng)開發(fā)奠定理論基礎(chǔ)。

[1]PAWLAK Z.Rough set[J].International Journal of Computer and Information Science，1984，11：341-356.

[2]GRZYMALA-BUSSE J W，F(xiàn)U M.A Comparison of Several ApproachestoMissingAttributeValuesinDataMining[C]//ProcComputing.Berlin：Springer-Verlag，2000：378-385.

[3]KRYSZKIEWICZ M.Rough set approach to incomplete information system[J].Information Sciences，1998，112：39-49.

[4]STEFANOWSKI J，TSOUKIAS A.On the Extension of Rough Sets under Incomplete Information[C]//Proc of the 7th Int’1 Workshop on New Directions in Rough Sets，Data Mining，and Granular-Soft Computing. Berlin：Springer-Verlag，1999：73-81.

[5]王國胤.Rough集理論在不完備信息系統(tǒng)中的擴充[J].計算機研究與發(fā)展，2002，39（10）：1238-1243.

[6]瞿彬彬，盧炎生.基于限制非對稱相似關(guān)系模型的規(guī)則獲取算法研究[J].小型微型計算機系統(tǒng)，2007，28（7）：1221-1224.

[7]朱顥東，周 姝，鐘 勇.不完備信息系統(tǒng)粗集擴展模型[J].湖南科技大學學報（自然科學版），2009，24（3）：73-77.

（責任編輯：楊媛媛）

Rough set model based on improved prior probability

TAO Zhi，LIU Cai-ping
（College of Science，CAUC，Tianjin 300300，China）

Rough set models based on tolerance relation and a prior probability tolerance relation are important expansions of the rough set theory，yet there are some limitations.Combining the advantages of the two models，an improved prior probability rough set model is proposed.The new model is based on the statistics of property values in incomplete decision system，taking into account both the same attribute's different values and the correlation between different attributes.The model can effectively improve classification accuracy and rationality.The model has a strong practicability in system which has fewer unknown attribute values and exists a significant association in different attributes.

rough set；incomplete system；improved tolerance relation

TP18

：A

：1674-5590（2014）08-0048-04

2013-06-17；

：2013-10-14

國家自然科學基金項目（60672178）；中國民航大學科研基金項目（2010kys01）

陶 志（1963—），男，遼寧沈陽人，教授，博士，研究方向為復雜系統(tǒng)建模、粗糙集理論及其應(yīng)用等.