概率優勢關系下的粗糙集模型及屬性約簡

施玉杰, 楊宏志, 魏 玲

(1.鄭州大學 數學與統計學院， 河南 鄭州 450001;2.河南財經政法大學 河南 鄭州 450046;3.西北大學 數學學院, 陜西 西安 710127)

?

·數理科學·

概率優勢關系下的粗糙集模型及屬性約簡

施玉杰1, 楊宏志2, 魏 玲3

(1.鄭州大學 數學與統計學院， 河南 鄭州 450001;2.河南財經政法大學 河南 鄭州 450046;3.西北大學 數學學院, 陜西 西安 710127)

針對序信息系統,提出了一種新的優勢關系,并探討了概率優勢關系粗糙集模型及其性質;定義了概率優勢類結構差異度的概念,給出一種概率優勢關系下的屬性約簡理論及算法。為基于優勢關系序信息系統的知識發現提供了新的方法和思路。

序信息系統;概率優勢關系;粗糙集;屬性約簡

粗糙集理論是波蘭數學家Pawlak教授于1982年提出的一種處理具有不精確、不確定和模糊性的數學工具[1-2],已經廣泛用于人工智能、機器學習、決策支持和分析、數據挖掘、知識發現等領域,并取得了豐碩的研究成果[3-7]。經典粗糙集理論主要以等價關系為基礎,比較適合處理分類問題。然而在實際問題中,有些信息系統中屬性取值是可比較的,涉及多屬性決策領域的比較與排序問題,此時使用等價關系就不能獲得很好的結論。于是,Greco,Slowinski等人拓展了粗糙集理論,提出了基于優勢關系的粗糙集理論[8-11]。近年來,很多學者對優勢關系下的信息系統進行了大量深入的研究,其中優勢關系下屬性約簡問題也越來越多地受到關注[12-16]。

以往研究序信息系統時使用的優勢關系是比較嚴格的,要求可比較的對象在所有屬性取值上都大于或等于,這種定義對噪聲十分敏感,且得到的優勢類比較有限,可能導致很多對象在多屬性下無法比較。文獻[17]定義了一種概率優勢關系,研究基于該關系下的排序問題,并把這種方法應用于實際問題。但是，該文獻中定義的優勢關系還有改進的空間。此外,概率優勢關系下粗糙集的性質及屬性約簡問題目前研究甚少。

針對傳統優勢關系要求過于嚴格,及目前概率優勢關系研究的不完善等問題,本文改進已有的概率優勢關系,使之更加合理,并分析探討了概率優勢關系粗糙集模型的一些性質。進而引入概率優勢類結構間差異度的概念,并給出相應的性質和結論,在此基礎上給出概率優勢關系下序信息系統屬性約簡的理論與方法,豐富了基于優勢關系下序信息系統中知識發現的研究。

1 概率優勢關系

首先介紹傳統序信息系統中的優勢關系,然后給出改進后的概率優勢關系。

定義1[4]一個信息系統是一個四元組I=(U，AT， V, f ),U是非空有限的對象集;AT是非空有限的屬性集; f: U×AT→V為關系函數,它表示U中每一個對象的屬性取值,V=∪a∈ATVa為屬性值域。

在信息系統中,如果某屬性取值是遞增或者遞減的關系,則該屬性稱為一個準則;由若干準則組成的集合稱為準則集。如果一個信息系統的所有屬性都是準則,則被稱為序信息系統[18]。因遞增和遞減的關系僅由所考察準則的意義決定,對理論研究并無影響,為表述方便,本文只針對遞增的優勢關系進行研究。

定義2[4]在序信息系統I=(U, AT, V, f)中,對于A?AT,屬性子集A對應的優勢關系表示為:

對象x在屬性集A下所對應的優勢類為:

該定義中的優勢關系要求在每一個屬性下都成立,條件過于嚴格,導致一些對象之間無法比較優劣。而概率優勢關系的提出能有效地彌補這一缺陷,從而為深入研究優勢關系下的序信息系統提供新的方法。

定義3[17]設序信息系統I=(U, AT, V, f),?x,y∈U,a∈AT,記

pa(x, y)稱為對象x與y在屬性a下的二值判斷,若pa(x, y)=0,表明在屬性a下,y的取值一定小于x,相應地,pa(x, y)=1表明y在屬性a下的取值不小于x的取值。

其中|A|表示屬性集A中的屬性個數。PA(x, y)的全體PA=[PA(x, y)]n×n稱為I在A下的二值判斷頻率矩陣,簡稱判斷矩陣。

定義5[17]設序信息系統I=(U, AT, V, f),對于A?AT,給定閾值α,那么該序信息系統在屬性子集A下的α概率優勢關系定義為:

對象x在屬性集A下的α概率優勢類定義為:

然而該定義下有些對象的優勢類不是十分合理,比如,一個序信息系統中,對象x在4個屬性下的取值為 (1, 2, 1, 1),對象y在4個屬性下的取值為(1, 1, 1, 1),按照定義5中給出概率優勢關系及優勢類,只要滿足閾值小于0.75,都能得到y在x的優勢類中,而事實上y并不優于x。因此上述概率優勢關系還可進一步改進。下面我們給出改進后的α概率優勢關系及優勢類。

定義6 設序信息系統I=(U, AT, V, f),對于A?AT,給定閾值α,該序信息系統在屬性子集A下的α概率優勢關系定義為:

PA(x, y)≥PA(y, x), 0.5≤α≤1};

對象x在屬性集A下的α概率優勢類表示為:

顯然定義6中，若α=1,則退化為定義2的優勢關系,所以上述概率優勢關系是傳統優勢關系的一種推廣。

2 概率優勢關系下粗糙集模型及性質

針對序信息系統,概率優勢關系下的粗糙集模型有一些好的性質和結論成立。

性質1 設序信息系統I=(U, AT, V, f),對于屬性集A?AT,給定閾值α,由概率優勢關系及概率優勢類的定義,易知有以下性質:

性質2 設序信息系統I=(U, AT, V, f),A?AT,則定義7給出的α概率優勢關系下的上近似和下近似滿足以下性質:

這些性質可根據定義6及定義7證得。

3 基于概率優勢關系的屬性約簡

序信息系統屬性約簡問題是粗糙集理論研究的熱點之一,本節我們探討概率優勢關系下序信息系統屬性約簡的問題。

3.1 概率優勢關系下優勢類結構差異度

在序信息系統中,傳統優勢關系和優勢類之間滿足單調性,也即屬性個數越多,其對應的優勢關系及優勢類就越小。但概率優勢關系下該性質不再適用。因此以往尋找屬性約簡的方法在概率優勢關系下有一定的局限性。然而引入概率優勢類結構差異度來尋找概率優勢關系下序信息系統的屬性約簡能有效地避免因不滿足單調性引起的弊端。

定義8 設 I=(U, AT, V, f)為一個序信息系統,?A, B?AT,給定閾值α(0.5≤α≤1),

定義9 設序信息系統I=(U, AT, V, f),屬性集A, B?AT,給定閾值α,?x∈U,對象x在屬性集A, B下的α概率優勢類結構差異度定義為:

簡記為s(≥A,≥B)。其中Δ為集合之間的對稱差運算,即AΔB=(A-B)∪(B-A),|·|為集合的基數。

性質3 設序信息系統I=(U, AT, V, f),A, B?AT,給定閾值α,則0≤s(≥A,≥B)≤1。

性質4 設序信息系統I=(U, AT, V, f),?A, B?AT,給定閾值α,有0≤S (≥A, ≥B)≤1。

該性質由定義10及性質3可證。

3.2 概率優勢關系下的屬性約簡

定義11 設I=(U, AT, V, f)為一個序信息系統,給定閾值α,若對于A?AT,滿足:

則稱屬性子集A是序信息系統I在α概率優勢關系下的一個約簡。若僅滿足(1),則稱A是序信息系統I在α概率優勢關系下的一個協調集。

定理1 設序信息系統I=(U, AT, V, f),給定閾值α,?A, B?AT,S (≥A,≥B)=0的充分必要條件為

該定理說明序信息系統中,兩個屬性集合間的概率優勢類結構差異度為0，等價于它們具有完全相同的概率優勢類。

結合定義11及定理1,我們可以得到關于概率優勢關系下序信息系統屬性約簡的判定定理。

定理2 設序信息系統I=(U, AT, V, f),給定閾值α,若對于A?AT,有S (≥A, ≥AT)=0,且?a∈A,有S (≥A-{a}, ≥AT)>0,則屬性集子集A為α概率優勢關系下序信息系統的一個約簡。

3.3 概率優勢關系下的屬性約簡算法

利用上一節概率優勢關系下序信息系統約簡的定義及判定定理,本節給出一種概率優勢關系下尋找屬性約簡的算法。

輸入:信息系統I=(U, AT, V, f),對象集U=(x1, x2, …, xn),屬性集AT=(a1, a2, …, am),給定閾值α(0.5≤α≤1)

輸出:概率優勢關系下序信息系統屬性約簡C

Step1 令A0=?,i=1;

Step2 ?a∈AT-Ai-1,依次計算S(≥Ai-1∪{a}, ≥AT),找到S(≥Ai-1∪{a}, ≥AT)取值最小時對應的a,令Ai=Ai-1∪{a}；

Step3 若S(≥Ai, ≥AT)=0成立,轉Step4，否則,i=i+1,轉Step2;

Step4 ?a∈Ai,若S(≥Ai-{a}, ≥AT)>0,則轉Step6;

Step5 若?a*∈Ai,S(≥Ai-{a*}, ≥AT)=0,刪除屬性a*,Ai=Ai—{a*},轉Step4;

Step6 算法結束,輸出約簡C=Ai。

該算法的主要思想是通過逐步添加屬性來尋找協調集,每次添加的屬性都能保證與屬性全集間的概率優勢類結構差異度最小,直至結果為0，即找到了一個協調集;進而再根據定理2判斷此時的協調集是否為約簡。該算法能確保所找到的約簡屬性個數最少。

例1 表1是文獻[12]中給出的一個序信息系統,其中對象集U=(x1, x2, …, x5),屬性集AT=(a1, a2, a3, a4),下面根據上述算法求α概率優勢關系下序信息系統的一個約簡。

表1 序信息系統表

不妨取α=0.7。

然后計算AT與{ai}(i=1, 2, 3, 4)之間的α概率優勢類結構差異度:

因為a1與a4下的概率優勢類結構差異度最小且相等,不妨先取屬性a1,此時概率優勢類結構差異度不為0,于是進行下一步操作。

于是{a1, a4}為概率優勢關系下的一個協調集,因為單個屬性都不是協調集,所以{a1, a4}為約簡。

顯然,{a1, a4}下的概率優勢類與AT下的完全一樣,即{a1, a4}為保持了該序信息系統概率優勢類不變的約簡,從而驗證了該算法的正確性。

4 結 語

本文針對傳統優勢關系要求過于嚴格,以及已有概率優勢關系定義的不完整性,提出一種更加合理的概率優勢關系。進而研究了概率優勢關系粗糙集模型的性質,提出概率優勢類結構差異度的概念,并給出了一種該關系下屬性約簡的算法。此算法能有效地找到概率優勢關系下序信息系統的一個約簡。在序信息系統中,定義概率優勢關系,并研究相關的性質和結論,在一定程度上豐富了序信息系統中知識獲取和發現的理論。本文的后續將研究如何給出更簡單的概率優勢關系下屬性約簡算法,并進一步研究概率優勢關系下不完備序信息系統中粗糙集的相關性質和屬性約簡問題。

[1] PAWLAK Z. Rough Sets[J]. International Journal of Computer and Information Science, 1982, 11(5): 341-356.

[2] PAWLAK Z. Rough Sets[J]. Communication of the ACM, 1995, 38(1): 89-95.

[3] 常犁云, 王國胤, 吳渝. 一種基于Rough Set理論的屬性約簡及規則提取方法[J]. 軟件學報, 1999, 10(11): 1206-1211.

[4] 張文修, 梁怡, 吳偉志. 信息系統與知識發現[M]. 北京: 科學出版社, 2003.

[5] LINGRAS P J, YAO Y Y. Data mining using extensions of the rough set model [J]. Journal of the American Society for Information Science, 1998, 49(5): 415-422.

[6] LI M, DENG S B, WANG L, et al. Hierarchical Clustering Algorithm for Categorical Date Using a Probabilistic Rough Set Model[J]. Knowledge Based Systems, 2014, 65: 60-71.

[7] 王國胤, 張清華, 馬希驁，等. 知識不確定問題的粒計算模型[J].軟件學報, 2011, 22(4): 676-694.

[8] GRECO S, MATARAZZO B, SLOWINSKI R. Rough approximation of a preference relation by dominance relation[J].European Journal of Operation Research, 1999, 117: 63-83.

[9] GRECO S, MATARAZZO B, SLOWINSKI R. Rough Approximation by Dominance Relations[J].International Journal of Intelligent Systems, 2002, 17: 153-171.

[10] 徐偉華, 張文修. 基于優勢關系下的協調近似空間[J]. 計算機科學, 2005, 32(9):164-165.

[11] SHAO M W, ZHANG W X. Dominance Relation and Rules in an Incomplete Ordered Information System[J]. International Journal of Intelligent Systems, 2005, 20(5):13-27.

[12] 桂現才.序信息系統屬性約簡的一種啟發式算法[J].計算機工程與應用, 2008,44(27):168-171.

[13] 徐偉華, 張曉燕, 鐘堅敏,等.序信息系統中屬性約簡的啟發式算法[J]. 計算機工程, 2010, 36(17):69-71.

[14] XU W H, LI Y, LIAO X W. Approaches to attribute reductions based on rough set and matrix computation in inconsistent ordered information systems[J].Knowledge Based Systems, 2012, 27: 78-91.

[15] 呂躍進,韋碧鵬,胡明明.基于相對優勢類差量的序信息系統屬性約簡算法[J].模糊系統與數學, 2013, 27(1):142-148.

[16] 孟慧麗, 趙曉焱, 徐久成. 序信息系統的貼近度及屬性約簡算法[J]. 計算機科學, 2014, 41(12):189-191.

[17] 翁世洲, 呂躍進. 基于概率優勢關系的排序方法及應用[J]. 山西大學學報(自然科學版), 2015, 38(3):439-446.

[18] 徐偉華. 序信息系統與粗糙集[M]. 北京:科學出版社,2013.

(編 輯 亢小玉)

A rough set model and attribute reduction based on probabilistic dominance relation

SHI Yujie1, YANG Hongzhi2, WEI Ling3

(1.School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China;2.Henan University of Economics and Law, Zhengzhou 450046, China；3.School of Mathematics, Northwest University, Xi′an 710127， China)

For the ordered information systems, a modified definition of dominance relation is proposed and the relevant properties of rough set model based on probabilistic dominance relation are discussed firstly. Then a new definition of structure diversity on probabilistic dominance classes is proposed, following with a novel algorithm and some theories about attribute reduction. This study provides a new method to the theoretical basis of knowledge discovery in ordered information systems.

ordered information systems; probabilistic dominance relation; rough sets; attribution reduction

2015-11-01

國家自然科學基金資助項目(11371014)

施玉杰，女，河南周口人，從事形式概念分析、粗糙集理論研究。

O212；TP18

A

10.16152/j.cnki.xdxbzr.2016-05-005