集值信息系統(tǒng)基于限制相容關(guān)系的屬性約簡(jiǎn)

喬全喜，秦克云

QIAO Quanxi1，2,QIN Keyun1

1.西南交通大學(xué) 數(shù)學(xué)系，成都 610031

2.河南理工大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河南 焦作 454000

集值信息系統(tǒng)基于限制相容關(guān)系的屬性約簡(jiǎn)

喬全喜1，2，秦克云1

QIAO Quanxi1，2,QIN Keyun1

1.西南交通大學(xué) 數(shù)學(xué)系，成都 610031

2.河南理工大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河南 焦作 454000

討論集值信息系統(tǒng)基于限制相容關(guān)系的屬性約簡(jiǎn)方法；給出相似水平核心屬性的特征。通過(guò)實(shí)例說(shuō)明該算法能夠得到集值信息系統(tǒng)的相對(duì)約簡(jiǎn)。

粗糙集；集值信息系統(tǒng)；對(duì)稱(chēng)限制；相容關(guān)系；屬性約簡(jiǎn)

1 引言

粗糙集理論是由波蘭數(shù)學(xué)家Pawlak提出的處理不精確、不完全數(shù)據(jù)的有效工具[1-2]。它依據(jù)對(duì)象之間的不可分辨性將論域中的對(duì)象聚類(lèi)成基本知識(shí)，利用基本知識(shí)，通過(guò)上、下近似運(yùn)算來(lái)描述數(shù)據(jù)對(duì)象的不確定性，從而導(dǎo)出概念的分類(lèi)或決策規(guī)則。目前，粗糙集理論已廣泛應(yīng)用于屬性約簡(jiǎn)[3-9]、規(guī)則提取[10-11]、模式識(shí)別與分類(lèi)[12-13]等人工智能領(lǐng)域。經(jīng)典粗糙集模型對(duì)知識(shí)的表達(dá)是建立在完備信息系統(tǒng)中的屬性所誘導(dǎo)的等價(jià)關(guān)系基礎(chǔ)上的，但在實(shí)際應(yīng)用中，由于問(wèn)題的復(fù)雜性，通常人們得到的數(shù)據(jù)是不精確和不完善的。如果信息系統(tǒng)中某個(gè)對(duì)象的屬性是未知的，則稱(chēng)這種信息系統(tǒng)為不完備信息系統(tǒng)；如果一些對(duì)象的某個(gè)屬性值不是取一個(gè)值，也不是取空集，而是取幾個(gè)值，這種信息系統(tǒng)稱(chēng)之為集值信息系統(tǒng)。近年來(lái)，一些學(xué)者針對(duì)集值信息系統(tǒng)的知識(shí)發(fā)現(xiàn)與屬性約簡(jiǎn)做了許多研究工作。文獻(xiàn)[3]基于相容關(guān)系TA討論了集值信息系統(tǒng)的約簡(jiǎn)理論與方法，給出了該集值信息系統(tǒng)與其完備化信息系統(tǒng)的關(guān)系，提出了最大分布約簡(jiǎn)與最優(yōu)完備化概念，得到了從集值信息系統(tǒng)獲取決策規(guī)則的方法。2006年Guan等人[4]在文獻(xiàn)[3]的基于相容關(guān)系TA確定的最大相容類(lèi)在集值信息系統(tǒng)上，定義了兩種類(lèi)型的上、下粗糙近似算子，構(gòu)造了相應(yīng)的粗糙集模型，然后通過(guò)引入最大相容類(lèi)的屬性描述，給出了集值信息系統(tǒng)的規(guī)則提取與優(yōu)化方法，并根據(jù)定義的粗糙集模型討論了集值信息系統(tǒng)的三種類(lèi)型的屬性約簡(jiǎn)。宋笑雪等在文獻(xiàn)[14-15]中借助集合包含關(guān)系在集值信息系統(tǒng)上定義了一種新的相容關(guān)系，并研究了集值決策表在兩種不同關(guān)系TA與下的廣義約簡(jiǎn)方法和最優(yōu)廣義決策規(guī)則的提取，給出了協(xié)調(diào)集值決策表的屬性約簡(jiǎn)與不協(xié)調(diào)集值決策表的分配約簡(jiǎn)，并討論了協(xié)調(diào)集值決策系統(tǒng)中不同類(lèi)型的屬性特征。Qian等人在文獻(xiàn)[5]中比較詳細(xì)地討論了集值有序信息系統(tǒng)的優(yōu)勢(shì)粗糙集方法，對(duì)集值信息系統(tǒng)給出了更細(xì)致的刻畫(huà)。文獻(xiàn)[16]提出了描述子的概念，構(gòu)建了一種新的粗糙集模型定義方法，并由協(xié)調(diào)描述子導(dǎo)出最優(yōu)確定性決策規(guī)則，由非協(xié)調(diào)描述子導(dǎo)出了最優(yōu)結(jié)合決策規(guī)則，討論了描述子的相對(duì)約簡(jiǎn)以及一些不確定度量方法。文獻(xiàn)[17]基于描述子概念討論了不完備信息系統(tǒng)上可信決策規(guī)則的提取，并利用區(qū)分矩陣法給出了向上與向下描述子的相對(duì)約簡(jiǎn)，得到了不完備決策信息系統(tǒng)的最優(yōu)可信決策規(guī)則。文獻(xiàn)[18-19]基于限制相容關(guān)系和對(duì)稱(chēng)限制相容關(guān)系，分析比較了相應(yīng)的粗糙集模型與已有粗糙集擴(kuò)展模型之間的關(guān)系。文獻(xiàn)[9]基于變精度相容關(guān)系對(duì)集值信息系統(tǒng)及集值決策表的約簡(jiǎn)理論與方法進(jìn)行了比較深入、系統(tǒng)的研究。本文針對(duì)對(duì)稱(chēng)限制相容關(guān)系，研究集值信息系統(tǒng)以及集值決策表的屬性約簡(jiǎn)的理論與方法，并給出了相應(yīng)水平核心。

2 集值信息系統(tǒng)中的限制相容關(guān)系

設(shè)U是對(duì)象構(gòu)成的非空有限集合，以下稱(chēng)為論域。按照Pawlak粗糙集理論，知識(shí)是對(duì)對(duì)象進(jìn)行分類(lèi)的能力。因此，U上的知識(shí)可以形式化地表示為U的劃分，U上的知識(shí)庫(kù)可以通過(guò)信息系統(tǒng)進(jìn)行描述。

定義1[20]一個(gè)信息系統(tǒng)是一個(gè)三元組S=(U，A，F(xiàn))，其中：

（1）U={x1，x2，…，xn}為對(duì)象集，每個(gè) xi(1≤i≤n)稱(chēng)為一個(gè)對(duì)象；

（2）A={a1，a2，…，am}為屬性集，每個(gè)aj(1≤j≤m)稱(chēng)為一個(gè)屬性；

（3）F={fl|1≤l≤m}為對(duì)象屬性值映射，其中fl:U→Vl，Vl是屬性al的值域。

設(shè)S=(U，A，F(xiàn))是信息系統(tǒng)。對(duì)于任意a∈A，由a可以確定論域U上的一個(gè)等價(jià)關(guān)系，稱(chēng)為由a確定不可區(qū)分關(guān)系，記為ind(a)，定義如下：

對(duì)于任意x，y∈U，(x，y)∈ind(a)當(dāng)且僅當(dāng)：fa(x)=fa(y)。

因此，信息系統(tǒng)本質(zhì)上就是知識(shí)庫(kù)，每一個(gè)屬性決定一個(gè)知識(shí)。

集值信息系統(tǒng)是信息不確定與不完整的一種反映形式，具體可以定義如下：

定義2[20]稱(chēng)三元組S=(U，A，F(xiàn))為集值信息系統(tǒng)，其中U={x1，x2，…，xn}為對(duì)象集，A={a1，a2，…，am}為屬性集，F(xiàn)={fl|1≤l≤m}為對(duì)象屬性值映射，其中 fl:U→P0(Vl)，Vl是屬性al的值域，P0(Vl)表示Vl的所有非空子集構(gòu)成的集合。若S=(U，A，F(xiàn))是一個(gè)集值信息系統(tǒng)，d是論域U上一個(gè)決策屬性，則稱(chēng)S=(U，A∪j5i0abt0b，F(xiàn))是一個(gè)集值決策表。

設(shè)S=(U，A，F(xiàn))是一個(gè)集值信息系統(tǒng)，對(duì)任意a∈A，x∈U，fa(x)的值從語(yǔ)義方面主要有兩種解釋方式[4-5]：

（1）fa(x)的值被合取地解釋。例如，設(shè)a表示屬性“語(yǔ)言能力”，則 fa(x)={漢語(yǔ)，英語(yǔ)，法語(yǔ)}可以解釋為對(duì)象x會(huì)說(shuō)漢語(yǔ)、英語(yǔ)和法語(yǔ)；又如當(dāng)按動(dòng)物的“食性”將一群動(dòng)物分類(lèi)時(shí)，若以“0”表示“食草”，以“1”表示“食肉”，則可用無(wú)序數(shù)組{0，1}來(lái)表示“既食草又食肉”。

（2）fa(x)的值被析取地解釋。例如，設(shè)a表示屬性“語(yǔ)言能力”，則 fa(x)={漢語(yǔ)，英語(yǔ)，法語(yǔ)}也可以解釋為對(duì)象x會(huì)說(shuō)漢語(yǔ)、英語(yǔ)和法語(yǔ)中的一種語(yǔ)言。對(duì)于不完備信息系統(tǒng)，如果對(duì)象x在屬性a下取空值并且空值存在，則 fa(x)可以表示取屬性a的值域Va中的任何值，這時(shí)可以用a的所有可能取值Va作為 fa(x)的取值；如果已知 fa(x)必定不取某些值，比如不取b、c，則可用Va-{b，c}作為 fa(x)的取值。因此，不完備信息系統(tǒng)可以轉(zhuǎn)化為析取解釋的集值信息系統(tǒng)進(jìn)行研究。

定義3[3]設(shè)(U，A，F(xiàn))是集值信息系統(tǒng)，任意屬性子集B?A，定義二元關(guān)系：

定義4[14]設(shè)(U，A，F(xiàn))是集值信息系統(tǒng)，任意屬性子集B?A，定義二元關(guān)系：

定義5[18]設(shè)(U，A，F(xiàn))是集值信息系統(tǒng)，任意屬性子集B?A，定義二元關(guān)系：

定義6[19]設(shè)(U，A，F(xiàn))是集值信息系統(tǒng)，任意屬性子集B?A，定義二元關(guān)系：

其中：

以上相容關(guān)系分別從不同的角度出發(fā)刻畫(huà)了集值信息系統(tǒng)中對(duì)象之間的相似性，顯然有：

接下來(lái)針對(duì)對(duì)稱(chēng)限制相容關(guān)系，研究集值信息系統(tǒng)以及集值決策表的屬性約簡(jiǎn)理論與方法。

3 對(duì)稱(chēng)限制相容關(guān)系的屬性約簡(jiǎn)

設(shè)S=(U，A，F(xiàn))是集值信息系統(tǒng)，B?A，α∈(0，1]，令

定理1[19]設(shè)(U，A，F(xiàn))是集值信息系統(tǒng)，RαB是如上定義的二元關(guān)系，則有：

（1）RαB是自反、對(duì)稱(chēng)二元關(guān)系；

下面討論集值信息系統(tǒng)基于限制相容關(guān)系的屬性約簡(jiǎn)方法，并給出相似水平核心屬性的特征。

定義7設(shè)S=(U,A,F)是集值信息系統(tǒng)，B?A，α∈(0,1]，若，則稱(chēng)B是S的一個(gè)α分類(lèi)協(xié)調(diào)集。若B是S 的 α分類(lèi)協(xié)調(diào)集，且對(duì)于 B的任意真子集C?B，有，則稱(chēng)B是S的一個(gè)α分類(lèi)約簡(jiǎn)。

集值信息系統(tǒng)S的α分類(lèi)約簡(jiǎn)是保持所有對(duì)象的α相容類(lèi)不變的極小屬性子集。S的α分類(lèi)約簡(jiǎn)是存在的，并且可能不唯一。S的所有α分類(lèi)約簡(jiǎn)構(gòu)成的集合記為redα(S)，而S的所有α分類(lèi)約簡(jiǎn)的交集稱(chēng)為S的α分類(lèi)核，記為coreα(S)，即coreα(S)=redα(S)。

根據(jù)定理1容易知道，B?A是集值信息系統(tǒng)S的α分類(lèi)協(xié)調(diào)集等價(jià)于，或者等價(jià)于?x∈U，。

定義8設(shè)S=(U，A，F(xiàn))是一個(gè)集值信息系統(tǒng)，x，y∈U，為對(duì)象x與y的α區(qū)分屬性集；并稱(chēng)

為集值信息系統(tǒng)S的α區(qū)分矩陣。

明顯地，dα(x，y)≠?當(dāng)且僅當(dāng)(x，y)?RαA，并且對(duì)任意B?A，B∩dα(x，y)≠?當(dāng)且僅當(dāng)(x，y)?RαB。

根據(jù)定義8，對(duì)任意 x，y∈U及相似水平 α都有dα(x，x)=?，dα(x，y)=dα(y，x)，即集值信息系統(tǒng)的α區(qū)分矩陣Mα是主對(duì)角線(xiàn)上元素全為?的對(duì)稱(chēng)矩陣。

定理2設(shè)S=(U，A，F(xiàn))是一個(gè)集值信息系統(tǒng)，B?A，α∈(0，1]是相似水平，則B是S的α分類(lèi)協(xié)調(diào)集的充分必要條件是：其中：

充分性：假設(shè)?dα(x，y)∈，B∩dα(x，y)≠?。如果B不是 α分類(lèi)協(xié)調(diào)集，那么必有，這表明存在(x，y)∈，但(x，y)?.由(x，y)?知 dα(x，y)≠?，于是由假設(shè)就有 B∩dα(x，y)≠?，從而(x，y)?，這就與(x，y)∈矛盾。因此A是α分類(lèi)協(xié)調(diào)集。

定理3設(shè)S=(U，A，F(xiàn))是一個(gè)集值信息系統(tǒng)，α∈(0，1]是相似水平，則 c∈coreα(S)的充分必要條件是：存在dα(x，y)∈，使dα(x，y)={c}。

證明 必要性：設(shè)c∈coreα(S)，即c是S的一個(gè)α分類(lèi)核心屬性。記

容易看到?dα(x，y)∈，都有 B∩dα(x，y)≠?。于是由定理2知B是α分類(lèi)協(xié)調(diào)集，從而存在C?B，使C是S的α分類(lèi)約簡(jiǎn)，但明顯地有c?C，這就與c是α分類(lèi)核心屬性矛盾。因此必有dα(x，y)∈Mα(c)，使| dα(x，y)|=1，從而dα(x，y)={c}。

充分性：假設(shè)存在dα(x，y)∈，使dα(x，y)={c}。對(duì)于S的任意α分類(lèi)約簡(jiǎn)B，由定理2知B∩dα(x，y)≠?，從而有 c∈B，故有 c∈coreα(S)。對(duì)于集值信息系統(tǒng)(U，A，F(xiàn))，若α，β∈(0，1]，α≤β，則有。從而對(duì)于任意x∈U，有。即隨著相似水平的提高，集值信息系統(tǒng)的相容類(lèi)或知識(shí)將會(huì)變得更細(xì)。另外，對(duì)于任意x，y∈U，顯然有dα(x，y)?dβ(x，y)，即隨著相似水平的提高，可以區(qū)分x、y的屬性更多。

基于區(qū)分矩陣與區(qū)分函數(shù)，通過(guò)計(jì)算區(qū)分函數(shù)的極小析取范式可以找到完備信息系統(tǒng)的所有約簡(jiǎn)，這一方法也可以推廣到集值信息系統(tǒng)。

是集值信息系統(tǒng) S的 α區(qū)分函數(shù)，其中 ?dα(x，y)表示dα(x，y)中所有屬性的析取。

定理4設(shè)S=(U，A，F(xiàn))是一個(gè)集值信息系統(tǒng)，α∈(0，1]，B?A，則B是S的α分類(lèi)約簡(jiǎn)的充分必要條件是：?A是α區(qū)分函數(shù)Δα(S)的極小析取范式中的一個(gè)合取子式。

例1考慮表1給出的集值信息系統(tǒng)。

表1 集值信息系統(tǒng)

取閾值α=0.5，經(jīng)計(jì)算可得：

同理，對(duì)于任意x，y∈U，可求得d0.5(x，y)，構(gòu)成區(qū)分矩陣如下：

于是，區(qū)分函數(shù)為：

從而S有唯一的0.5分類(lèi)約簡(jiǎn){a1，a2，a5}。

如果取閾值α=0.7，通過(guò)計(jì)算可得區(qū)分矩陣如下：

其中 X1={a1，a2，a4，a5}，X2={a1，a2，a3，a4，a5}，X3={a1，a2，a3，a5}。于是區(qū)分函數(shù)為：

故有六個(gè)0.7分類(lèi)約簡(jiǎn)：{a1，a5}，{a2，a5}，{a3，a5}，{a4，a5}，{a1，a2，a3}和{a2，a3，a4}。

4 結(jié)論

集值信息系統(tǒng)對(duì)象關(guān)于屬性取集合值是信息不確定的一種反映形式。本文討論了集值信息系統(tǒng)基于相對(duì)限制相容關(guān)系的屬性約簡(jiǎn)方法，給出了相似核心屬性的特征以及相對(duì)約簡(jiǎn)的計(jì)算方法。今后，將在本文的基礎(chǔ)上，進(jìn)一步討論集值決策表基于相對(duì)限制相容關(guān)系的分配約簡(jiǎn)和正域約簡(jiǎn)方法。

[1]Pawlak Z.Rough sets[J].InternationalJournalofComputer and Information Science，1982，11：341-356.

[2]Pawlak Z.Rough sets：theoretical aspects of reasoning about data[M].Boston：Kluwer Academic Publishers，1991.

[3]Zhang W X，Mi J S.Incomplete information system and its optimal selections[J].Computers and Mathematics with Applications，2004，48：：691-698.

[4]Guan Y Y，Wang H K.Set-valued information systems[J]. Information Sciences，2006，176：2507-2525.

[5]Qian Y，Dang C，Liang J，et al.Set-valued ordered information systems[J].Information Sciences，2009，179：2809-2832.

[6]Li F，Yin Y Q.Approaches to knowledge reduction of covering decision systems based on information theory[J].Information Sciences，2009，179：1694-1704.

[7]洪曉蕾，王燕，莫執(zhí)文，等.集值不完備信息系統(tǒng)上的一種知識(shí)約簡(jiǎn)方法[J].四川師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，30（3）：266-269.

[8]陳子春，秦克云.集值信息系統(tǒng)在相容關(guān)系下的屬性約簡(jiǎn)[J].模糊系統(tǒng)與數(shù)學(xué)，2009，23（1）：150-154.

[9]陳子春.集值信息系統(tǒng)的知識(shí)發(fā)現(xiàn)與屬性約簡(jiǎn)研究[D].成都：西南交通大學(xué)，2011.

[10]Tsumoto S.Mining diagnostic rules from clinical databases using rough sets and medical diagnostic model[J].Information Sciences，2004，162：65-80.

[11]Tsai Y C，Cheng C H，Chang J R.Entropy-based fuzzy rough classification approach for extracting rules[J].Expert Systems with Application，2006，31（2）：436-443.

[12]Hu Q H，Yu D R，Xie Z X.Neighborhood classifiers[J].Expert Systems with Application，2008，34：866-876.

[13]Li Y，Shiu S C K，Pal S K.Combining feature reduction and case selection in building CBR classifiers[J].IEEE Transactions on Knowledge and Data Engineering，2006，18：415-429.

[14]宋笑雪，解爭(zhēng)龍，張文修.集值決策信息系統(tǒng)的知識(shí)約簡(jiǎn)與規(guī)則提取[J].計(jì)算機(jī)科學(xué)，2007，34（4）：182-184.

[15]宋笑雪，張文修.基于集值決策屬性的集值信息系統(tǒng)[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（17）：8-10.

[16]Leung Y，Wu W Z，Zhang W X.Knowledge acquisition in incomplete information systems：a rough set approach[J]. European Journal of Operational Research，2006，168（1）：164-180.

[17]Yang X，Xie J，Song X，et al.Credible rules in incomplete decision system based on descriptors[J].Knowledge-Based Systems，2009，22：8-17.

[18]吳鵬，楊勇，張阿紅.基于集值的Rough集擴(kuò)充模型[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（32）：134-136.

[19]鮑忠奎，楊善林.集值信息系統(tǒng)的粗糙集擴(kuò)展模型[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（35）：22-24.

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

1.Department of Mathematics,Southwest Jiaotong University,Chengdu 610031,China

2.School of Mathematics&Information Science,Henan Polytechnic University,Jiaozuo,Henan 454000,China

This paper is devoted to the discussion of attribute reduction of set-valued information system based on symmetry restriction tolerance relation.The characteristic of similar level core attribute is introduced.The example shows that this algorithm can obtain the relative reduction of set-valued information system.

rough set;set-valued information system;symmetry restriction;tolerance relation;attribute reduction

A

TP18；TP301

10.3778/j.issn.1002-8331.1209-0117

QIAO Quanxi,QIN Keyun.Attribute reduction of set-valued information system based on restriction tolerance relation. Computer Engineering and Applications,2013,49（7）：24-27.

國(guó)家自然科學(xué)基金（No.60875034）。

喬全喜（1964—），男，博士生，研究領(lǐng)域：粗糙集理論及其應(yīng)用；秦克云（1962—），男，博士生導(dǎo)師，研究領(lǐng)域：代數(shù)邏輯與智能信息處理。E-mail：qiaoqx@hpu.edu.cn

2012-09-19

2012-12-03

1002-8331（2013）07-0024-04

CNKI出版日期：2012-12-24 http://www.cnki.net/kcms/detail/11.2127.TP.20121224.1515.005.html