曾艷燕，徐章艷，曾玲珍，張姣，宋臘香

1.廣西師范大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，廣西桂林 541004

2.江西藍(lán)天學(xué)院商學(xué)院，南昌 330029

3.鄂州市高級(jí)中學(xué)，湖北鄂州 436000

基于區(qū)分對(duì)象對(duì)的不完備決策表求核

曾艷燕1，徐章艷1，曾玲珍2，張姣1，宋臘香3

1.廣西師范大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，廣西桂林 541004

2.江西藍(lán)天學(xué)院商學(xué)院，南昌 330029

3.鄂州市高級(jí)中學(xué)，湖北鄂州 436000

1 引言

屬性約簡(jiǎn)是粗糙集理論的核心內(nèi)容之一，而決策表中屬性核的計(jì)算對(duì)解決屬性約簡(jiǎn)這一核心問(wèn)題具有極其重要的意義，他能有效縮小屬性約簡(jiǎn)算法在屬性空間的搜索范圍，降低屬性約簡(jiǎn)算法的復(fù)雜度，因此如何高效地求不完備決策表的核非常重要。近年來(lái)，許多學(xué)者對(duì)完備決策表的求核進(jìn)行了研究，并取得了大量的成果[1-7]。然而這些經(jīng)典的粗糙集求核方法在處理不完備決策表時(shí)仍存在一定的不足。對(duì)不完備決策表，Kryszkiewicz[8]提出容差關(guān)系，Stefanowski[9]等人提出非對(duì)稱相似關(guān)系，王國(guó)胤[10]提出限制容差關(guān)系，文獻(xiàn)[11-12]從知識(shí)粒度的角度對(duì)不完備決策表進(jìn)行分析，他們都是在以上模型上對(duì)不完備決策表進(jìn)行屬性約簡(jiǎn)，然后在屬性約簡(jiǎn)基礎(chǔ)上對(duì)不完備決策表進(jìn)行求核，時(shí)間復(fù)雜度為O(|C|2|U|2)，并不理想。直接對(duì)不完備決策表進(jìn)行求核的算法很少，文獻(xiàn)[13]從正區(qū)域的角度提出了求不完備決策表核的算法，文獻(xiàn)[14]從二進(jìn)制差別矩陣的角度提出了另一種對(duì)不完備決策表求核的算法。文獻(xiàn)[6-7]中對(duì)完備決策表提出區(qū)分對(duì)象對(duì)集的定義，并在區(qū)分對(duì)象對(duì)的基礎(chǔ)上對(duì)不完備決策表進(jìn)行求核。然而，對(duì)不完備決策表，目前還沒(méi)有人給出區(qū)分對(duì)象對(duì)的相應(yīng)定義。于是本文對(duì)不完備決策表提出了基于差別矩陣的區(qū)分對(duì)象對(duì)集定義，并將求不完備決策表的核轉(zhuǎn)化到求不完備決策表的區(qū)分對(duì)象對(duì)集上，相比于先求決策表的差別矩陣，再根據(jù)差別矩陣去求決策表的核的算法，本文算法所求出的區(qū)分對(duì)象對(duì)的個(gè)數(shù)通常遠(yuǎn)遠(yuǎn)小于差別矩陣的元素個(gè)數(shù)，大大減少了計(jì)算量，有效地降低算法的時(shí)間及空間復(fù)雜度。

2 粗糙集概念

3 相關(guān)定理

綜上所述，命題成立。

綜合定理2和定理3，說(shuō)明了在不完備決策表中，求核可以轉(zhuǎn)化到求基于差別矩陣的區(qū)分對(duì)象對(duì)集上。

4 計(jì)算正區(qū)域的方法

求正區(qū)域的計(jì)算時(shí)間主要花在計(jì)算容差類TC(x)(x∈U)上。一般來(lái)說(shuō)，求容差類TC(x)的算法是：對(duì)對(duì)象集U中的對(duì)象進(jìn)行兩兩比較，比較它們?cè)贑中的每個(gè)屬性是否滿足容差類的定義，若滿足，則屬于同一個(gè)容差類；或者對(duì)對(duì)象集U中的每個(gè)對(duì)象，根據(jù)其C的取值判斷是否屬于現(xiàn)有的容差類。在最壞的情況下，以上兩種方法在每個(gè)條件屬性下都需要O(|U|)2次比較，故最壞的時(shí)間復(fù)雜度為O(|C||U|2)[8]。文獻(xiàn)[15]計(jì)算容差類TC(x)的算法時(shí)間復(fù)雜度降為又因?yàn)門C(xi)?U，所以O(shè)(K)≤O(|U|)。顯然，該時(shí)間復(fù)雜度比一般的算法的時(shí)間復(fù)雜度O(|C||U|2)要低。

5 基于區(qū)分對(duì)象對(duì)集的求核算法

根據(jù)上述定義、定理和計(jì)算正區(qū)域的方法，下面給出基于區(qū)分對(duì)象對(duì)集的不完備決策表的求核算法。

算法求核算法

6 實(shí)例分析

為了更好地說(shuō)明本文算法的有效性，以下面不完備決策表為例進(jìn)行分析說(shuō)明（如表1）。

表1 決策表

結(jié)合上述算法對(duì)該不完備決策表1進(jìn)行求核：

7 結(jié)束語(yǔ)

本文首先引入了基于不完備決策表差別矩陣及其核的定義，然后給出基于差別矩陣的區(qū)分對(duì)象對(duì)定義。在此基礎(chǔ)上，利用區(qū)分對(duì)象對(duì)的概念設(shè)計(jì)了一種對(duì)不完備決策表進(jìn)行求核的算法。通過(guò)實(shí)例驗(yàn)證表明，該算法能有效地求得不完備決策表的核，為不完備決策表的屬性約簡(jiǎn)提供了一種新方法。

[1]王國(guó)胤.Rough Set理論與知識(shí)獲取[M].西安：西安交通大學(xué)出版社，2001：20-39.

[2]葉東毅，陳昭炯.一個(gè)新的二進(jìn)制可辨識(shí)矩陣及其核的計(jì)算[J].小型微型計(jì)算機(jī)系統(tǒng)，2004，25（6）：965-967.

[3]徐章艷，楊炳儒，宋威.基于簡(jiǎn)化的二進(jìn)制差別矩陣的快速求核算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2006，27（9）：1711-1714.

[4]葛浩，李龍澍，楊傳健.一種核屬性快速求解算法[J].控制與決策，2009，24（5）：738-742.

[5]徐章艷，舒文豪，錢文彬，等.基于序關(guān)系的快速計(jì)算正區(qū)域核的算法[J].計(jì)算機(jī)科學(xué)，2010，37（7）：208-211.

[6]徐章艷，楊炳儒，宋威，等.基于區(qū)分對(duì)象對(duì)集的快速求核算法[J].系統(tǒng)工程與電子技術(shù)，2008，30（4）：731-734.

[7]徐章艷，楊炳儒，宋威.基于區(qū)分對(duì)象對(duì)集的高效屬性約簡(jiǎn)算法[J].模式識(shí)別與人工智能，2006，19（5）：572-577.

[8]Kryszkiewicz M.Rough set approach to incomplete information systems[J].Information Sciences，1998，112（1）：39-49.

[9]Stefanowski J，Tsoukias A.Incomplete information tables and rough classification[J].Computational Intelligence，2001，7（3）：545-566.

[10]王國(guó)胤.Rough集理論在不完備信息系統(tǒng)中的擴(kuò)充[J].計(jì)算機(jī)研究與發(fā)展，2002，39（10）：1238-1243.

[11]李秀紅，史開(kāi)泉.一種基于知識(shí)粒度的不完備信息系統(tǒng)的屬性約簡(jiǎn)算法[J].計(jì)算機(jī)科學(xué)，2006，33（10）：169-170.

[12]徐久成，史進(jìn)玲，孫林.一種基于相對(duì)粒度的決策表約簡(jiǎn)算法[J].計(jì)算機(jī)科學(xué)，2009，36（3）：205-207.

[13]李曉瑜，徐章艷，王煒，等.不完備信息系統(tǒng)中一種新的求核算法[J].計(jì)算機(jī)工程，2011，37（11）：56-58.

[14]曾艷燕，徐章艷，舒文豪，等.一種基于不完備決策表的求核算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（1）：135-137.

[15]Shu Wenhao，Xu Zhangyan，Ruan Shen.A quick attribution reduction algorithm dased on incomplete decision table[J]. Advanced Materials Research，2011，171/172：154-158.

ZENG Yanyan1,XU Zhangyan1，ZENG Lingzhen2,ZHANG Jiao1,SONG Laxiang3

1.School of Computer Science and Information Engineering,Guangxi Normal University,Guilin,Guangxi 541004,China
2.School of Business,Jiangxi Blue Sky College,Nanchang 330029,China
3.Ezhou Senior Middle School,Ezhou,Hubei 436000,China

The definition of discernibility object pair set of incomplete decision table,based on discernibility matrix,is defined. And it is proved that computing the core of incomplete decision table is equal to computing the discernibility object pair set of incomplete decision table.Then an algorithm for computing core based on discernibility object pair set of incomplete decision table is proposed.And the time complexity of the new algorithm ismax{O(K|C||U|)，O(|C||U||Upos|)},which is better than the time complexity of the same kind of algorithms.At last,an example is used to illustrate the efficiency of the new algorithm.

rough set;incomplete decision table;discernibility matrix;discernibility object pair set;compute core

在差別矩陣的基礎(chǔ)上，針對(duì)不完備決策表提出了基于差別矩陣的區(qū)分對(duì)象對(duì)集定義，并證明求不完備決策表的核可以轉(zhuǎn)化到求基于差別矩陣的區(qū)分對(duì)象對(duì)集上。在此基礎(chǔ)上，提出了一種基于區(qū)分對(duì)象對(duì)的不完備決策表求核算法，該算法的時(shí)間復(fù)雜度為：max{O(|C||U||Upos|)，O(K|C||U|)}，優(yōu)于同類算法的時(shí)間復(fù)雜度；用實(shí)例說(shuō)明了新算法的有效性。

粗糙集；不完備決策表；差別矩陣；區(qū)分對(duì)象對(duì)集；求核

A

TP311

10.3778/j.issn.1002-8331.1201-0188

ZENG Yanyan,XU Zhangyan，ZENG Lingzhen,et al.Computing core based on discernibility object pair set in incomplete decision table.Computer Engineering and Applications,2013,49（19）：104-107.

國(guó)家自然科學(xué)基金（No.60963008）；廣西自然科學(xué)基金（No.2011GXNSFA018163）。

曾艷燕（1987—），女，碩士研究生，主要研究方向：粗糙集理論及應(yīng)用與數(shù)據(jù)挖掘；徐章艷（1972—），男，博士，教授，主要研究方向：粗糙集，模糊集，數(shù)據(jù)挖掘；曾玲珍（1974—），女，助教；張姣（1986—），女，碩士研究生，主要研究方向：形式概念分析，粗糙集，描述邏輯；宋臘香，主要研究方向：粗糙集理論及應(yīng)用與數(shù)據(jù)挖掘。E-mail：zengyanyan0925@163.com

2012-01-13

2012-04-23

1002-8331（2013）19-0104-04

CNKI出版日期：2012-06-01http://www.cnki.net/kcms/detail/11.2127.TP.20120601.1457.029.html