基于區分對象對的不完備決策表求核

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

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

2.江西藍天學院商學院，南昌 330029

3.鄂州市高級中學，湖北鄂州 436000

基于區分對象對的不完備決策表求核

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

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

2.江西藍天學院商學院，南昌 330029

3.鄂州市高級中學，湖北鄂州 436000

1 引言

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

2 粗糙集概念

3 相關定理

綜上所述，命題成立。

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

4 計算正區域的方法

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

5 基于區分對象對集的求核算法

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

算法求核算法

6 實例分析

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

表1 決策表

結合上述算法對該不完備決策表1進行求核：

7 結束語

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

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

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

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

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

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

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

[7]徐章艷，楊炳儒，宋威.基于區分對象對集的高效屬性約簡算法[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集理論在不完備信息系統中的擴充[J].計算機研究與發展，2002，39（10）：1238-1243.

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

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

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

[14]曾艷燕，徐章艷，舒文豪，等.一種基于不完備決策表的求核算法[J].計算機工程與應用，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

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

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

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.

國家自然科學基金（No.60963008）；廣西自然科學基金（No.2011GXNSFA018163）。

曾艷燕（1987—），女，碩士研究生，主要研究方向：粗糙集理論及應用與數據挖掘；徐章艷（1972—），男，博士，教授，主要研究方向：粗糙集，模糊集，數據挖掘；曾玲珍（1974—），女，助教；張姣（1986—），女，碩士研究生，主要研究方向：形式概念分析，粗糙集，描述邏輯；宋臘香，主要研究方向：粗糙集理論及應用與數據挖掘。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