施玉杰, 楊宏志, 魏 玲

(1.鄭州大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 河南 鄭州 450001;2.河南財(cái)經(jīng)政法大學(xué) 河南 鄭州 450046;3.西北大學(xué) 數(shù)學(xué)學(xué)院, 陜西 西安 710127)

?

·數(shù)理科學(xué)·

概率優(yōu)勢關(guān)系下的粗糙集模型及屬性約簡

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

(1.鄭州大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 河南 鄭州 450001;2.河南財(cái)經(jīng)政法大學(xué) 河南 鄭州 450046;3.西北大學(xué) 數(shù)學(xué)學(xué)院, 陜西 西安 710127)

針對序信息系統(tǒng),提出了一種新的優(yōu)勢關(guān)系,并探討了概率優(yōu)勢關(guān)系粗糙集模型及其性質(zhì);定義了概率優(yōu)勢類結(jié)構(gòu)差異度的概念,給出一種概率優(yōu)勢關(guān)系下的屬性約簡理論及算法。為基于優(yōu)勢關(guān)系序信息系統(tǒng)的知識發(fā)現(xiàn)提供了新的方法和思路。

序信息系統(tǒng);概率優(yōu)勢關(guān)系;粗糙集;屬性約簡

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

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

針對傳統(tǒng)優(yōu)勢關(guān)系要求過于嚴(yán)格,及目前概率優(yōu)勢關(guān)系研究的不完善等問題,本文改進(jìn)已有的概率優(yōu)勢關(guān)系,使之更加合理,并分析探討了概率優(yōu)勢關(guān)系粗糙集模型的一些性質(zhì)。進(jìn)而引入概率優(yōu)勢類結(jié)構(gòu)間差異度的概念,并給出相應(yīng)的性質(zhì)和結(jié)論,在此基礎(chǔ)上給出概率優(yōu)勢關(guān)系下序信息系統(tǒng)屬性約簡的理論與方法,豐富了基于優(yōu)勢關(guān)系下序信息系統(tǒng)中知識發(fā)現(xiàn)的研究。

1 概率優(yōu)勢關(guān)系

首先介紹傳統(tǒng)序信息系統(tǒng)中的優(yōu)勢關(guān)系,然后給出改進(jìn)后的概率優(yōu)勢關(guān)系。

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

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

定義2[4]在序信息系統(tǒng)I=(U, AT, V, f)中,對于A?AT,屬性子集A對應(yīng)的優(yōu)勢關(guān)系表示為:

對象x在屬性集A下所對應(yīng)的優(yōu)勢類為:

該定義中的優(yōu)勢關(guān)系要求在每一個(gè)屬性下都成立,條件過于嚴(yán)格,導(dǎo)致一些對象之間無法比較優(yōu)劣。而概率優(yōu)勢關(guān)系的提出能有效地彌補(bǔ)這一缺陷,從而為深入研究優(yōu)勢關(guān)系下的序信息系統(tǒng)提供新的方法。

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

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

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

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

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

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

定義6 設(shè)序信息系統(tǒng)I=(U, AT, V, f),對于A?AT,給定閾值α,該序信息系統(tǒng)在屬性子集A下的α概率優(yōu)勢關(guān)系定義為:

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

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

顯然定義6中，若α=1,則退化為定義2的優(yōu)勢關(guān)系,所以上述概率優(yōu)勢關(guān)系是傳統(tǒng)優(yōu)勢關(guān)系的一種推廣。

2 概率優(yōu)勢關(guān)系下粗糙集模型及性質(zhì)

針對序信息系統(tǒng),概率優(yōu)勢關(guān)系下的粗糙集模型有一些好的性質(zhì)和結(jié)論成立。

性質(zhì)1 設(shè)序信息系統(tǒng)I=(U, AT, V, f),對于屬性集A?AT,給定閾值α,由概率優(yōu)勢關(guān)系及概率優(yōu)勢類的定義,易知有以下性質(zhì):

性質(zhì)2 設(shè)序信息系統(tǒng)I=(U, AT, V, f),A?AT,則定義7給出的α概率優(yōu)勢關(guān)系下的上近似和下近似滿足以下性質(zhì):

這些性質(zhì)可根據(jù)定義6及定義7證得。

3 基于概率優(yōu)勢關(guān)系的屬性約簡

序信息系統(tǒng)屬性約簡問題是粗糙集理論研究的熱點(diǎn)之一,本節(jié)我們探討概率優(yōu)勢關(guān)系下序信息系統(tǒng)屬性約簡的問題。

3.1 概率優(yōu)勢關(guān)系下優(yōu)勢類結(jié)構(gòu)差異度

在序信息系統(tǒng)中,傳統(tǒng)優(yōu)勢關(guān)系和優(yōu)勢類之間滿足單調(diào)性,也即屬性個(gè)數(shù)越多,其對應(yīng)的優(yōu)勢關(guān)系及優(yōu)勢類就越小。但概率優(yōu)勢關(guān)系下該性質(zhì)不再適用。因此以往尋找屬性約簡的方法在概率優(yōu)勢關(guān)系下有一定的局限性。然而引入概率優(yōu)勢類結(jié)構(gòu)差異度來尋找概率優(yōu)勢關(guān)系下序信息系統(tǒng)的屬性約簡能有效地避免因不滿足單調(diào)性引起的弊端。

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

定義9 設(shè)序信息系統(tǒng)I=(U, AT, V, f),屬性集A, B?AT,給定閾值α,?x∈U,對象x在屬性集A, B下的α概率優(yōu)勢類結(jié)構(gòu)差異度定義為:

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

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

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

該性質(zhì)由定義10及性質(zhì)3可證。

3.2 概率優(yōu)勢關(guān)系下的屬性約簡

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

則稱屬性子集A是序信息系統(tǒng)I在α概率優(yōu)勢關(guān)系下的一個(gè)約簡。若僅滿足(1),則稱A是序信息系統(tǒng)I在α概率優(yōu)勢關(guān)系下的一個(gè)協(xié)調(diào)集。

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

該定理說明序信息系統(tǒng)中,兩個(gè)屬性集合間的概率優(yōu)勢類結(jié)構(gòu)差異度為0，等價(jià)于它們具有完全相同的概率優(yōu)勢類。

結(jié)合定義11及定理1,我們可以得到關(guān)于概率優(yōu)勢關(guān)系下序信息系統(tǒng)屬性約簡的判定定理。

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

3.3 概率優(yōu)勢關(guān)系下的屬性約簡算法

利用上一節(jié)概率優(yōu)勢關(guān)系下序信息系統(tǒng)約簡的定義及判定定理,本節(jié)給出一種概率優(yōu)勢關(guān)系下尋找屬性約簡的算法。

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

輸出:概率優(yōu)勢關(guān)系下序信息系統(tǒng)屬性約簡C

Step1 令A(yù)0=?,i=1;

Step2 ?a∈AT-Ai-1,依次計(jì)算S(≥Ai-1∪{a}, ≥AT),找到S(≥Ai-1∪{a}, ≥AT)取值最小時(shí)對應(yīng)的a,令A(yù)i=Ai-1∪{a}；

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

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

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

Step6 算法結(jié)束,輸出約簡C=Ai。

該算法的主要思想是通過逐步添加屬性來尋找協(xié)調(diào)集,每次添加的屬性都能保證與屬性全集間的概率優(yōu)勢類結(jié)構(gòu)差異度最小,直至結(jié)果為0，即找到了一個(gè)協(xié)調(diào)集;進(jìn)而再根據(jù)定理2判斷此時(shí)的協(xié)調(diào)集是否為約簡。該算法能確保所找到的約簡屬性個(gè)數(shù)最少。

例1 表1是文獻(xiàn)[12]中給出的一個(gè)序信息系統(tǒng),其中對象集U=(x1, x2, …, x5),屬性集AT=(a1, a2, a3, a4),下面根據(jù)上述算法求α概率優(yōu)勢關(guān)系下序信息系統(tǒng)的一個(gè)約簡。

表1 序信息系統(tǒng)表

不妨取α=0.7。

然后計(jì)算AT與{ai}(i=1, 2, 3, 4)之間的α概率優(yōu)勢類結(jié)構(gòu)差異度:

因?yàn)閍1與a4下的概率優(yōu)勢類結(jié)構(gòu)差異度最小且相等,不妨先取屬性a1,此時(shí)概率優(yōu)勢類結(jié)構(gòu)差異度不為0,于是進(jìn)行下一步操作。

于是{a1, a4}為概率優(yōu)勢關(guān)系下的一個(gè)協(xié)調(diào)集,因?yàn)閱蝹€(gè)屬性都不是協(xié)調(diào)集,所以{a1, a4}為約簡。

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

4 結(jié) 語

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

[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理論的屬性約簡及規(guī)則提取方法[J]. 軟件學(xué)報(bào), 1999, 10(11): 1206-1211.

[4] 張文修, 梁怡, 吳偉志. 信息系統(tǒng)與知識發(fā)現(xiàn)[M]. 北京: 科學(xué)出版社, 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ì)算模型[J].軟件學(xué)報(bào), 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] 徐偉華, 張文修. 基于優(yōu)勢關(guān)系下的協(xié)調(diào)近似空間[J]. 計(jì)算機(jī)科學(xué), 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] 桂現(xiàn)才.序信息系統(tǒng)屬性約簡的一種啟發(fā)式算法[J].計(jì)算機(jī)工程與應(yīng)用, 2008,44(27):168-171.

[13] 徐偉華, 張曉燕, 鐘堅(jiān)敏,等.序信息系統(tǒng)中屬性約簡的啟發(fā)式算法[J]. 計(jì)算機(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ìn),韋碧鵬,胡明明.基于相對優(yōu)勢類差量的序信息系統(tǒng)屬性約簡算法[J].模糊系統(tǒng)與數(shù)學(xué), 2013, 27(1):142-148.

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

[17] 翁世洲, 呂躍進(jìn). 基于概率優(yōu)勢關(guān)系的排序方法及應(yīng)用[J]. 山西大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 38(3):439-446.

[18] 徐偉華. 序信息系統(tǒng)與粗糙集[M]. 北京:科學(xué)出版社,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

國家自然科學(xué)基金資助項(xiàng)目(11371014)

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

O212；TP18

A

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