李長清，張燕蘭

（1.閩南師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，福建漳州363000；2.閩南師范大學(xué)計算機(jī)學(xué)院，福建漳州363000）

不完備信息系統(tǒng)下基于分辨度的屬性約簡算法

李長清1，張燕蘭2

（1.閩南師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，福建漳州363000；2.閩南師范大學(xué)計算機(jī)學(xué)院，福建漳州363000）

針對不完備信息系統(tǒng)問題，引入容差關(guān)系下分辨度的概念，并由此提出一種基于分辨度的不完備信息系統(tǒng)屬性約簡算法，該算法更符合實際應(yīng)用的需要.文章通過實例比較，證明該方法可行、有效.

不完備信息系統(tǒng)；容差關(guān)系；分辨度；屬性約簡

波蘭學(xué)者Pawlak Z.于1982年提出的經(jīng)典粗糙集理論［1］是一種處理不精確、不確定和模糊知識信息的數(shù)學(xué)工具，已經(jīng)被成功應(yīng)用于模式識別、人工智能、決策與分析、機(jī)器學(xué)習(xí)、智能信息處理［2-7］等領(lǐng)域.這種經(jīng)典的粗糙集理論研究是限制嚴(yán)格的等價關(guān)系下的完備信息系統(tǒng).而在應(yīng)用中，由于數(shù)據(jù)測量和獲取的限制，大量的數(shù)據(jù)存在缺失現(xiàn)象，信息系統(tǒng)普遍都不完備，因而，為處理這種不完備現(xiàn)象進(jìn)行的研究引起廣泛的關(guān)注.

1997年，Krysckiewcz M.［8］利用容差關(guān)系代替經(jīng)典粗糙集中的等價關(guān)系，提出了一種不完備信息系統(tǒng)下基于容差關(guān)系的粗糙集拓展模型.隨后，很多學(xué)者對不完備信息系統(tǒng)的處理進(jìn)行了深入研究.例如，Meng等人［10］通過所研究對象關(guān)于屬性得到的各種劃分，給出了一種快速的屬性約簡算法；Wu［11］結(jié)合證據(jù)理論得到了不完備決策信息系統(tǒng)的屬性約簡方法；于海燕等人［12］在不完備決策信息中將決策表進(jìn)行分解，然后按決策表提供的確定信息進(jìn)行分層提取而得到確定規(guī)則；黃兵等人［13］研究了相容矩陣和分配決策矩陣，通過矩陣間的相互關(guān)系得到了不完備信息系統(tǒng)的一種有效處理方法；李長清［14］等人針對容差關(guān)系存在的局限性，給出一種基于重要度相似關(guān)系的粗糙集模型；汪凌［15］引入相容關(guān)系下條件屬性矩陣和決策屬性矩陣的相關(guān)概念，并由此提出一種基于矩陣的不完備信息決策系統(tǒng)規(guī)則獲取算法；胡峰等人［16］提出了一種基于決策熵的不完備信息處理方法.

為了推進(jìn)不完備決策信息系統(tǒng)的進(jìn)一步研究，參照Krysckiewcz M.在文獻(xiàn)［8-9］中提出的不完備信息系統(tǒng)的屬性約簡，本文從不完備信息系統(tǒng)中基于容差關(guān)系的分類特點，給出分辨度的概念，借助這個概念給出了一種有效的屬性約簡算法.

1　不完備信息系統(tǒng)

定義1［4］設(shè)S=〈U，A∪｛d｝〉為一個信息系統(tǒng)，其中U是論域，A∪｛d｝是非空有限屬性集，A為條件屬性集合，｛d｝為決策屬性集合，且A∪｛d｝≠?.?a∈A∪｛d｝，有a∶U→Va，其中Va為a的值域.若存在u∈U，a∈A，使a（u）=*，則稱S是不完備信息系統(tǒng)；否則稱S是完備信息系統(tǒng).

定義2［4］設(shè)S為不完備信息系統(tǒng)，?≠B?A，B上的容差關(guān)系定義為：

2　基于分辨度的約簡算法

定義6設(shè)U為論域，A=｛A1，A2，…，Am｝和B=｛B1，B2，…，Bn｝為U上的兩個分類，若對?Ai∈A，?Bj∈B，使Ai?Bj，則稱A細(xì)于B.

根據(jù)定義5和定義6，容易得到下面的這個定理.

定理1設(shè)S為不完備信息系統(tǒng)，?≠B?A，a∈A，若U/TB細(xì)于U/T｛a｝，則LB細(xì)于U/T｛a｝，從而KB（a）=0.

定理2設(shè)S為不完備信息系統(tǒng)?≠B?A， b∈B，若滿足KB-｛b｝（b）＞0，則b為屬性集B的核.

證明由于KB-｛b｝（b）＞0，故U中至少存在兩點x1和x2在B-｛b｝中不可分辨，而對屬性b可分辨.于是屬性集B-｛b｝和B對論域U的分類情況不相同，因此b是核.

根據(jù)定理1，若某個屬性對屬性集分類情況不產(chǎn)生變化，則可知分辨度是0，于是該屬性冗余，從而可刪除.現(xiàn)在通過定理1與定理2，便得到一種約簡算法.

在不完備信息系統(tǒng)S中，從核開始，逐步增加核以外相對分辨度最大的屬性，驗證所得屬性集與原屬性集的分辨度相等情況，一直到分辨度相等時，算法終止，從而得屬性約簡集.

算法具體過程如下：

輸入：一個不完備信息系統(tǒng)S=〈U，A∪｛d｝〉，其中U為論域，A為條件屬性集，d為決策屬性.

輸出：A的約簡集Red.

步驟1：求出A的分辨度KA；步驟2：求出核屬性集

令Red=core.驗證是否滿足KRed=KA，若滿足，則轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟3；

步驟3：若a∈A-Red滿足

則令Red=Red∪｛a｝；

步驟4：驗證是否滿足KRed=KA，若滿足，則轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟3；

步驟5：輸出Red，算法結(jié)束，所得到的Red就是系統(tǒng)的約簡集.

我們以一個實例來分析此算法.

在一個不完備信息系統(tǒng)S=〈U，A∪｛d｝〉中，U=｛u1，u2，…，u6｝為論域，A=｛a1，a2，a3，a4｝為條件屬性集，d為決策屬性，見表1.

步驟1：計算A的分辨度KA：

步驟2：求核core：

容易求得各屬性的相對分辨度為：

3　實例分析

表1　不完備信息系統(tǒng)Tab.1Incomplete information system

步驟5：輸出Red=｛a2，a3｝，于是｛a2，a3｝就是約簡集.

在經(jīng)典的不完備信息系統(tǒng)S=〈U，A∪｛d｝〉中，一個集合B?A稱為此不完備信息系統(tǒng)的一個約簡，若TB=TA，且?C?B，TC≠TA.

對于上例給定的不完備信息系統(tǒng)，由經(jīng)典的不完備信息系統(tǒng)的約簡定義可以通過逐步驗證得到約簡集為｛a2，a3｝.

以上兩種約簡方法得到的約簡集是一樣的.由比較可以看出，用經(jīng)典的約簡方法只考慮了約簡集與原條件屬性集分類能力的一致性；而用相對分辨度進(jìn)行約簡時，不但簡化了容差類，而且兼顧了各條件屬性間的依賴關(guān)系，更符合實際應(yīng)用的需要.

4　小結(jié)

屬性約簡一直以來都是粗糙集理論的熱點課題.在前人已有成果的基礎(chǔ)上，本文在不完備信息系統(tǒng)容差關(guān)系下進(jìn)行研究，通過簡化容差類進(jìn)行屬性約簡，同時兼顧了各條件屬性集間的依賴關(guān)系，比經(jīng)典的約簡方法更符合實際應(yīng)用的需要.有關(guān)結(jié)論對不完備信息系統(tǒng)的研究具有一定的參考價值.

［1］Pawlak Z.Rough sets［J］.International Journal of Comput?er and Information Science，1982，11：341-356.

［2］Pawlak Z，Busse J G，slowinski R，et al.Rough sets［J］. communications of the ACM，1995，38（11）：89-95.

［3］王國胤.Rough理論與知識獲?。跰］.西安：西安交通大學(xué)出版社，2001.

［4］張文修，仇國芳.基于粗糙集的不確定決策［M］.北京：科學(xué)出版社，2005.

［5］王超，羅可.不完備信息系統(tǒng)中基于限制容差關(guān)系的屬性約簡方法［J］.計算機(jī)應(yīng)用，2011，31（12）：3236-3239.

［6］莫京蘭，呂躍進(jìn)，郭恒.廣義不完備信息系統(tǒng)中一種拓展粗糙集模型［J］.計算機(jī)工程與應(yīng)用，2012，48（19）：126-130.

［7］陳家俊，蘇守寶，金萍.一種對象完備度優(yōu)先填補(bǔ)的決策樹規(guī)則提取算法［J］.計算機(jī)應(yīng)用與軟件，2014，31（5）：264-267.

［8］Kryszkiewicz M.Rough set approach to imcomplete infor?mation systems［J］.Information Sciences，1998，112：39-49.

［9］Kryszkiewicz M.Rules in imcomplete information systems［J］.Information Sciences，1999，113：271-292.

［10］Meng Z Q，Shi Z Z.A fast to attribute reduction in incom?plete decision systems with tolerance relation-based rough sets［J］.Information Sciences，2009，179：2774-2793.

［11］Wu W Z.Attribute reduction based on evidence theory in incomplete decision systems［J］.Information Sciences，2008：1355-1371.

［12］于海燕，王道平，張霞.基于粒計算的不完備信息系統(tǒng)的規(guī)則提取方法［J］.計算機(jī)工程與應(yīng)用，2009，45（8）：143-145.

［13］黃兵，周獻(xiàn)中.不完備信息系統(tǒng)分配約簡與規(guī)則提取的矩陣算法［J］.計算機(jī)工程，2005，31（17）：20-22.

［14］李長清，李克典.不完備信息系統(tǒng)下基于重要度相似關(guān)系的粗集模型［J］.海南師范大學(xué)學(xué)報：自然科學(xué)版，2008，21（4）：401-403.

［15］汪凌.不完備決策系統(tǒng)規(guī)則獲取的相容矩陣算法［J］.計算機(jī)工程與應(yīng)用，2015，51（1）：130-142.

［16］胡峰，陳曦，王小燕.基于決策熵的不完備信息系統(tǒng)的知識約簡方法［J］.計算機(jī)工程與設(shè)計，2013，34（1）：289-292.

責(zé)任編輯：劉紅

An Attribute Reduction Algorithm Based on Discernibility in Incomplete Information Systems

LI Changqing1，ZHANG Yanlan2
（1.School of Mathematics and Statistics，Minnan Normal University，Zhangzhou 363000，China；2.College of Computer，Minnan Normal University，Zhangzhou 363000，China）

For incomplete information systems，the concept of discernibility under tolerance relation was introduced.More?over，an attribute reduction algorithm in incomplete information systems based on discernibility was presented.Dependency relation between attributes can be known from the reduction gained by the algorithm.It is more suited to the needs of practi?cal application.An example was used to illustrate that the algorithm was feasible and more effective through comparison.

incomplete information systems；tolerance relation；discernibility；attribute reduction

TP 18

A

1674-4942（2015）04-0359-03

2015-09-17

國家自然科學(xué)基金項目（11471153，11526109）；福建省自然科學(xué)基金項目（2015J05011，2013J01029）；福建省中青年教師教育科研基金項目（JA14200，JA13198）；福建省省屬高校專項計劃資助項目（JK2014028）