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

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

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

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

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

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

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

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

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

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

1 引言

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

2 粗糙集概念

3 相關(guān)定理

綜上所述，命題成立。

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

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

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

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

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

算法求核算法

6 實例分析

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

表1 決策表

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

7 結(jié)束語

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

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

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

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

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

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

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

[7]徐章艷，楊炳儒，宋威.基于區(qū)分對象對集的高效屬性約簡算法[J].模式識別與人工智能，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]王國胤.Rough集理論在不完備信息系統(tǒng)中的擴(kuò)充[J].計算機研究與發(fā)展，2002，39（10）：1238-1243.

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

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

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

[14]曾艷燕，徐章艷，舒文豪，等.一種基于不完備決策表的求核算法[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ǔ)上，針對不完備決策表提出了基于差別矩陣的區(qū)分對象對集定義，并證明求不完備決策表的核可以轉(zhuǎn)化到求基于差別矩陣的區(qū)分對象對集上。在此基礎(chǔ)上，提出了一種基于區(qū)分對象對的不完備決策表求核算法，該算法的時間復(fù)雜度為：max{O(|C||U||Upos|)，O(K|C||U|)}，優(yōu)于同類算法的時間復(fù)雜度；用實例說明了新算法的有效性。

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

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.

國家自然科學(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