喬全喜，秦克云

QIAO Quanxi1，2,QIN Keyun1

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

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

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

喬全喜1，2，秦克云1

QIAO Quanxi1，2,QIN Keyun1

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

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

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

粗糙集；集值信息系統(tǒng)；對稱限制；相容關系；屬性約簡

1 引言

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

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

設U是對象構成的非空有限集合，以下稱為論域。按照Pawlak粗糙集理論，知識是對對象進行分類的能力。因此，U上的知識可以形式化地表示為U的劃分，U上的知識庫可以通過信息系統(tǒng)進行描述。

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

（1）U={x1，x2，…，xn}為對象集，每個 xi(1≤i≤n)稱為一個對象；

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

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

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

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

因此，信息系統(tǒng)本質上就是知識庫，每一個屬性決定一個知識。

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

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

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

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

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

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

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

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

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

其中：

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

接下來針對對稱限制相容關系，研究集值信息系統(tǒng)以及集值決策表的屬性約簡理論與方法。

3 對稱限制相容關系的屬性約簡

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

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

（1）RαB是自反、對稱二元關系；

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

定義7設S=(U,A,F)是集值信息系統(tǒng)，B?A，α∈(0,1]，若，則稱B是S的一個α分類協(xié)調集。若B是S 的 α分類協(xié)調集，且對于 B的任意真子集C?B，有，則稱B是S的一個α分類約簡。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

取閾值α=0.5，經計算可得：

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

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

從而S有唯一的0.5分類約簡{a1，a2，a5}。

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

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

故有六個0.7分類約簡：{a1，a5}，{a2，a5}，{a3，a5}，{a4，a5}，{a1，a2，a3}和{a2，a3，a4}。

4 結論

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

[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)上的一種知識約簡方法[J].四川師范大學學報：自然科學版，2007，30（3）：266-269.

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

[9]陳子春.集值信息系統(tǒng)的知識發(fā)現(xiàn)與屬性約簡研究[D].成都：西南交通大學，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]宋笑雪，解爭龍，張文修.集值決策信息系統(tǒng)的知識約簡與規(guī)則提取[J].計算機科學，2007，34（4）：182-184.

[15]宋笑雪，張文修.基于集值決策屬性的集值信息系統(tǒng)[J].計算機工程與應用，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集擴充模型[J].計算機工程與應用，2008，44（32）：134-136.

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

[20]張文修，梁怡，吳偉志.信息系統(tǒng)與知識發(fā)現(xiàn)[M].北京：科學出版社，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.

國家自然科學基金（No.60875034）。

喬全喜（1964—），男，博士生，研究領域：粗糙集理論及其應用；秦克云（1962—），男，博士生導師，研究領域：代數(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