一种不完备决策表的属性约简算法

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　一种不完备决策表的属性约简算法　王　帅，徐章艳，曾艳燕　ＷＡＮＧ　Ｓｈｕａｉ，ＸＵ　Ｚｈａｎｇｙａｎ，ＺＥＮＧ　Ｙａｎｙａｎ　广西师范大学计算机科学与信息工程学院，广西桂林５４　１　００４　Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｇｕａｎｇｘｉ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｇｕｉｌｉｎ，Ｇｕａｎｇｘｉ　５４　１　００４，Ｃｈｉｎａ　ＷＡＮＧ　Ｓｈｕａｉ，ＸＵ　Ｚｈａｎｇｙａｎ，ＺＥＮＧ　Ｙａｎｙａｎ．Ｏｎｅ　ａｔｔｒｉｂｕｔｅ　ｒｅｄｕｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｉｎｃｏｍｐｌｅｔｅ　ｄｅｃｉｓｉｏｎ　ｔａ・　ｂｌｅ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１２，４８（１４）：１３０－１３３．　Ａｂｓｔｒａｃｔ：Ｆｏｒ　ａｎ　ｉｎｃｏｍｐｌｅｔｅ　ｄｅｃｉｓｉｏｎ　ｔａｂｌｅ，ｔｈｅ　ｄｅｆｉｎｉｔｉｏｎ　ｏｆ　ｄｉｓｃｅｒｎｉｂｉｌｉｙ　ｔｏｂｊｅｃｔ　ｐａｉｒ　ｓｅｔ　ａｎｄ　ｔｈｅ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｄｅｆ－　ｉｎｉｔｉｏｎ　ｏｆ　ａｔｔｒｉｂｕｔｅ　ｒｅｄｕｃｔｉｏｎ　ａｒｅ　ｉｎｔｒｏｄｕｃｅｄ。Ｉｔ　ｉｓ　ｐｒｏｖｅｄ　ｔｈａｔ　ｔｈｅ　ｄｅｆｉｎｉｔｉｏｎ　ｏｆ　ａｔｔｒｉｂｕｔｅ　ｒｅｄｕｃｔｉｏｎ　ｉｓ　ｅｑｕｉｖａｌｅｎｔ　ｔｏ　ｔｈｅ　ｏｎｅ　ｂａｓｅｄ　ｏｎ　ｇｅｎｅｒａｌｉｚｅｄ　ｄｅｃｉｓｉｏｎ—ｍａｋｉｎｇ．Ｕｎｄｅｒ　ｔｈｉｓ　ｃｏｎｄｉｔｉｏｎ，ａｎ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｄｅｆｉｎｉｔｉｏｎ　ｏｆ　ｄｉｓｃｅｒｎｉｂｉｌｉ—　ｙ　ｔｏｂｊｅｃｔ　ｐａｉｒ　ｓｅｔ　ｉｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｒｏｕｇｈ　ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ　ｄｅｇｒｅｅ　Ｋ（ｃ　）ａｎｄ　ｃｏｍｐｌｅｔｅ　ｄｅｇｒｅｅ　Ｐ（ｃｆ）ａｓ　ｈｅｕｒｉｓｔｉｃ　ｉｎｆｏｒｍａ—　ｔｉｏｎ，ｃｏｍｂｉｎｉｎｇ　ｗｉｔｈ　ｑｕｉｃｋ　ｓｏｒｔｉｎｇ，ｔｈｅ　ｔｉｍｅ　ｃｏｍｐｌｅｘｉｙ　ｔｏｆ　ｈｅ　ｔｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｃｕｔ　ｄｏｗｎ　ｔｏ　ｏ￣ｃｌｌ　）．Ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ａｌｇｏｒｉｔｍ　Ｄｑ　ｈｃ　）ａｎｄ　Ｄｑ　ｃ　），ｔｈｅ　ｔｉｍｅ　ｃｏｍｐｌｅｘｉｙ　ｉｔｓ　ｅｆｆｅｃｔｉｖｅｌｙ　ｒｅｄｕｃｅｄ．Ａｎ　ｅｘａｍｐｌｅ　ｉｓ　ｕｓｅｄ　ｔｏ　ｉｌｌｕｓｔｒａｔｅ　ｔｈｅ　ａｄｖａｎｔａｇｅ　ａｎｄ　ｃｏｎｖｅｎｉｅｎｃｅ　ｏｆ　ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｍ．ｈ　Ｋｅｙ　ｗｏｒｄｓ：ｒｏｕｇｈ　ｓｅｔ；ｉｎｃｏｍｐｌｅｔｅ　ｄｅｃｉｓｉｏｎ　ｔａｂｌｅ；ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ　ｏｂｊｅｃｔ　ｐａｉｒ　ｓｅｔ；ａｔｔｒｉｂｕｔｅ　ｒｅｄｕｃｔｉｏｎ　摘要：对于不完备决策表，给出了区分对象对集和基于区分对象对集约简的定义，并证明出基于区分对象对　集的属性约简定义等价于基于广义决策的属性约简定义。在此基础上，提出一种基于区分对象对集的新算　法。新算法以区分度Ｋ（ｃ　）和完备度Ｐ（ｃ　）为启发信息，结合基数排序，使得算法最终时间复杂度为ｏ￣ｃＩＩＵ１　），　相比传统的算法时间复杂度ｏＧｃＩ　　）和ｏ（ｌ］ｃｌ　１１０　），时间复杂度有效降低。通过实例说明了新算法的＿ｒＥ确性　和有效性。　关键词：粗糙集；不完备决策表；区分对象对集；属性约简　文章编号：１００２．８３３１（２０１２）１４—０１３０．０４　文献标识码：Ａ　中图分类号：ＴＰ１８　１概述　粗糙集理论”堤：波兰科学家Ｐａｗｌａｋ于１　９８２提出　的一种新型数学工具。目前在机器学习、过程控制、　模式识别与数据挖掘等领域都取得成功的应用　。　简，文献［７］提出一种基于知识粒度的不完备信息系　统的属性约简，这些算法的时间复杂度均为　ｏｄｃＩ。ｌＵｌ　），文献［８］提出基于属性重要度的属性约简　算法，文献［９］提出一种基于同可区分度的属性约简　算法，文献【１Ｏ］提出一种基于差别矩阵的属性约简算　法，这些算法时间复杂度均为ｏ￣ＪｃＩ　　ＩＯｌ　）。　本文在相容关系的模型下，提出基于区分对象　经典的粗糙集理论基于完备信息系统，而在现实生　活中，信息的不完备现象广泛存在。目前，已有专家　学者对经典粗糙集理论在不完备信息系统下进行扩　充，例如文献［３］提出的容差关系，文献［４］等人提出的　非对称相似关系，文献［５］提出的限制容差关系等，文　献［６］提出一种基于信息量的不完备信息系统属性约　对集的属性约简定义，并证明其等价于基于广义决　策的属性约简。然后给出一种启发式的属性约简算　法，新算法以区分度Ｋ（ｃ　）和完备度Ｐ（ｃ　）作为启发信　基金项目：国家自然科学基金（Ｎｏ．６０９６３００８）；广西自然科学基金（Ｎｏ．２０１１ＧｘＮｓＦＡｏｌ８１６３）；广西研究生教育创新计划项目。　作者简介：王帅（１９８６一），男，硕士研究生，主要研究方向为粗糙集理论及应用、数据挖掘；徐章艳（１９７２一），男，博士，教授，主要研　究方向为粗糙集、模糊集、数据挖掘；曾艳燕（１９８７一），女，硕士研究生，主要研究方向为粗糙集理论及应用、数据挖掘。　Ｅ－ｍａｉｌ：ｈａｐｐｙｗａｎｇ８６＠１　２６．ｃｏｒｎ　收稿日期：２０１１－０９．２８　修回日期：２０１１－１２．２２　ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２—８３３１．２０１２．１４．０２７　王帅，徐章艳，曾艳燕：一种不完备决策表的属性约简算法　息，结合基数排序，算法的时间复杂度为ＯＧＣｌｌ￣　）。　最后通过实例说明新算法的正确性和有效性。　２基本概念　定义１五元组Ｓ＝　，Ｃ，Ｄ，Ｖ，ｆ）是一个决策　表，其中【，＝　，Ｘ　一，Ｘ　｝表示对象的非空有限集合，　称为论域；Ｃ＝（ｃ　，Ｃ　一，Ｃ　）表示条件属性的非空有　限集；Ｄ表示决策属性的非空有限集且ｃｎＤ＝（２）；　＝ａ∈ＣＵＤ　Ｕ　，　是属性口的值域；ｆ．Ｕｘ　ｃｕＤ　是一个信息函数，它对一个对象的每一个属性赋予　一个信息值，即Ｖａ∈ＣＵＤ，Ｘ∈Ｕ，有．厂　，ａ）∈　。　在五元组中，若至少有一个属性ａ∈Ｃ，使得　包含空值（用　表示），即至少有一个屙陛ａ∈Ｃ，存在　—个Ｘ∈Ｕ，使得厂　，ａ）＝　，则称之为不完备决策表。　定义２不完备决策表　＝（【，，Ｃ，Ｄ，Ｖ，ｆ）中，令　Ｂ　Ｃ，定义　上的容差关系　：　（　＝｛（　，　∈Ｕｘ　Ｖｂ∈Ｂ，ｆ　，ｂ）　，ｂ）ｖｆ（ｘ，６）＝　ｖｆＯ，，６）＝　）。　（　）　表示在　下与Ｘ具有容差关系的全体对象集为：　｛　∈　（　，　∈丁（　）｝。　定义３ｔ　在不完备决策表　＝（己，，Ｃ，Ｄ，Ｖ，ｆ）中，　令Ｂ　Ｃ，对任意Ｘ∈Ｕ，定义不完备决策表中的广　义决策函数ａ　）＝｛厂　，　ｂ，∈　（　｝。　定义４对不完备决策表　＝　，Ｃ，Ｄ，Ｖ，．　，　Ｖｂ∈　Ｃ，若　（　＝　－｛６１（　），则称ｂ在Ｂ中是可　省的（不必要的）；否则称ｂ在　中是不可省的（必要　的）。对ＶＢ　Ｃ，若其任一元素相对于Ｂ都是必要　的，则称　是独立的。　定义５　在不完备决策表．Ｓｆ＝　，Ｃ，Ｄ，Ｖ，ｆ）中，　令　ｃ，ａＢ　）＝ａｃ（　）且Ｖｂ∈Ｂ＝　ａＢ—ｆ　（　）≠ａ　（　），　则称　为不完备决策表的一个属性约简（基于广义　决策的属性约简定义）。　定义６在不完备决策表Ｓ＝　，Ｃ，Ｄ，Ｖ，ｆ）中，　对Ｖ　ｃ，定义：ＲＢ＝｛＜ｔ，　，＞　ｘｊ∈Ｕ，３ｂ∈Ｂ有　ｆ（ｘｆ，　≠厂（　，，ｂ）Ａｆ（ｘ　，ｂ）≠　人－厂（ｘｊ，６）≠　，且厂（　，，　Ｏｃ（　）｝，称＜　，ｘｊ＞为区分对象对，称　为由条件属　性集　得到的区分对象对集。　定义７在不完备决策表　：　，Ｃ，Ｄ，Ｖ，．　中，　Ｖ　ｃ若Ｒ　＝尺ｃ，且Ｖｂ∈Ｂ，　口㈨≠　ｃ，贝０称　是不完备决策表的一个属性约简（基于区分对象对　集的属性约简定义）。　３两种属性约简的等价性分析　引理在不完备决策表　＝　，Ｃ，Ｄ，Ｖ，ｆ）中，　Ｖｘ∈Ｕ，Ｂ　Ｃ。贝０有　（　）　（　。　证明由定义知命题成立。　定理１在不完备决策表　＝　，Ｃ，Ｄ，Ｖ，ｆ）中，　ＶＢ　Ｃ若Ｒ口＝　ｃ，则有　（　＝ａｃ（　）。　证明假设有　（　≠ａ　（　，则至少存在一个决　策属性ｄ，使得ｄ∈ａ　（　）＾ｄ仨ａｃ（　），由广义决策定　义可知，必存在一个对象ｘｊ，使得－厂（　ｄ）∈ａ　（　）且　（　，，　）　Ｏｃ（　），古炙　（　）≠　（　），贝０——　芭３ａ∈Ｃ—Ｂ，　使得ｆ（ｘ　，口）≠　＾　（　ｆ，　）≠　＾－厂（　ｆ，　）　厂（　ｆ，　）。又因　－厂（　，，　）　Ｏｃ　ｊ），故＜　，　，＞∈　ｃ，另一方面，由于　厂（　，，　∈　（　ｆ），故＜誓，　，＞　Ｒ口，这与Ｒ日＝　ｃ相矛　盾，故假设不成立，从而有ａ　（　＝ａ　（　成立。　定理２在不完备决策表　＝（　，Ｃ，Ｄ，Ｖ，ｆ）中，　ＶＢ　Ｃ，若　（　＝ａｃ（　，则有ＲＢ：　ｃ。　证明假设Ｒ　≠　ｃ，由引理知：　（　）　），　则至少存在＜　ｆ，ｘ，＞∈Ｒｆ但＜　，Ｘ　＞　Ｒ８。因为　＜　，　，＞∈Ｒ　，则根据区分对象对集的定义知：　ｌ厂　，ｄ）硭ａｃ（　ｆ）Ｎ．３　∈Ｃ勰ｌ厂　，口）≠木＾　（　，，日）≠木＾　ｆ（ｘ　，　（　，，　），从而有　（　）≠　（　，）。又因为　＜　，　，＞　Ｒ　，厂　，，　）　ａｃ（　则必定不存在ｂ∈Ｂ，使　得ｆ（ｘ　，ｂ）≠　ｖｆ％，６）≠　ｖｆ（ｘｆ，ｂ）≠厂　，，６），即　，∈　（　ｆ）。故有　（　，，　）∈　（　），从而得ａ口（　ｆ）≠ａｃ（　ｆ），　这与ａ　（　）＝　（　）相矛盾，故假设不成立，从而若　（　＝ａｃ（　），贝　Ｒ口＝　ｃ。　定理３基于区分对象对集的属性约简定义与基　于广义决策屙『生约简的定义等价。　证明由定理１和定理２可得。　注定理３说明基于区分对象对集的属性约简定　义与基于广义决策屙ｌ生约简定义是等价的，这样就可　以将基于广义决策屙ｆ生约简建立在区分对象对集上。　４基于区分对象对集的属性约简算法　４．１算法思想　定义８在不完备决策表　＝　，Ｃ，Ｄ，Ｖ，ｆ）中，对　Ｖｃ　∈Ｃ，Ｅ（ｃｉ）＝｛ｙｂ＇∈Ｕ，ｆ　，Ｃｆ）≠　），Ｐ（ｃｆ）＝ＩＥ（ｃｆ）Ｉ，　ｘ（ｃ　）＝Ｉ｛ｙｌＶｘ，　∈Ｅ（ｃ　），ｆ（ｘ，ｃｉ）　（　，ｃ　）｝Ｉ；其中Ｉ　Ｉ表　示集合　的元素数目。对Ｖｃ　∈Ｃ，称Ｐ（ｃ　）为条件　属性Ｃ　的完备度，Ｘ（ｃ　）为条件属性Ｃ　的区分度。　由定义可知：Ｋ（ｃ，）越大，对应的条件属性所区　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　分的对象越多，区分能力越强。Ｐ（ｃ　）表示条件属性　若有多个Ｘ（ｃ　）相等，则对相等的Ｋ（ｃ　）比较其对应　Ｘ（ｃ　）＋尸（ｃ　）大小，对应的属性序列为ｃ　ｃ　…，ｃ　；　令Ｒｅｄ＝｛ｃｊ１）；Ｒｃ＝（２ｊ。　步骤３用基数排序得到Ｕ／０　（　）＝｛ａ　，　：，…，ｍ｝，　其中任意　＝｛　１，　，，…，　，｝。　步骤４　ｆｏｒ（ｉｎｔｉ：１；ｆ　ｍ；ｉ＋＋）　ｆｏｒ（ｉｎｔｊ＝ｉ＋１；　ｍ；　＋＋）　Ｃ　下，取值确定的对象个数。当Ｘ（ｃ　）相同时，Ｐ（ｃ　）　越大，代表当前属性下，对象条件属性取值确定的个　数越多，完备程度越高，越符合现实意义。　本文以Ｋ（ｃ　）和Ｐ（ｃ　）作为启发信息进行属性约　简。首先依据Ｋ（ｃ　）大小，对条件属性进行排序；其　次当出现Ｋ（ｃ　）相同的情况时，再对相同的Ｋ（ｃ　），依　据Ｐ（ｃ　）对条件属性进行排序。　４．２算法描述　算法１求不完备决策表的容差类　）和广义　决策函数　（　）　输入不完备决策表　＝　，Ｃ，Ｄ，Ｖ，ｆ）　输出容差类　（　）和广义决策函数ａ。（　ｆ），＿∈Ｕ　（ｆ＝１，２，…，　）　骤１　（　，）：｛　｝，Ｏｃ（　）＝｛厂（　，　）｝。　步骤２　ｆｏｒ（ｉ＝１；ｆ　，ｚ；ｆ＋＋）　ｆｏｒ（ｊ＝１；／　；　＋＋）　ｉｆ　，Ｘ　）＝ｔｒｕｅ）　（　ｆ）＝Ｔｃ（　ｆ）Ｕ｛　，）　８ｃ（　）＝ｃ３ｃ　）Ｕ｛ｆ（ｘｊ，　）｝　步骤３输出　（　）和　（　）。　算法２求启发信息Ｋ（ｃ　），Ｐ（ｃ　）　输入不完备决策表　＝（　，Ｃ，Ｄ，Ｖ，ｆ）　输出启发信息Ｋ（ｃ　Ｐ（ｃ　）　步骤１令Ｂ（ｃ　）＝（２ｊ，Ｋ（ｃ　）＝０，Ｐ（ｃｆ）＝０。　步骤２　ｆｏｒ（ｉｎｔ　ｉ＝１；ｆ　ｒ；ｉ＋＋）　ｆｏｒ（ｉｎｔｊ＝１；　；　＋＋）　ｉｆ（ｆ（ｘｊ，ｃ　）≠　）　｛Ｐ（ｃｆ）＋＋；　ｉｆ（ｆ（ｘｊ，ｃ　）诺　（ｃｆ））　Ｂ（ｃ　）＝　（ｃｊ）Ｕ｛ｆ（ｘｊ，Ｃｉ））；　Ｋ（ｃ，）＋＋；｝　步骤３输出启发信息Ｋ（ｃ　Ｐ（ｃ　）。　算法３基于区分对象对集的属性约简算法　输入不完备决策表　＝　Ｃ，Ｄ，　，己厂＝｛　，　Ｘ２，…，Ｘ　），Ｃ＝｛ｃ１，Ｃ２，…，Ｃ　｝　输出不完备决策表的属性约简Ｒｅｄ　步骤１由算法１得到容差类Ｔ（ｘｆ），广义决策函　数　（　）（ｆ＝１，２，…，　。　步骤２由算法２得到启发信息Ｋ（ｃ　），Ｐ（ｃ　），先按照　Ｋ（ｃ　）从大到小排序得到：Ｋ（ｃｆ）１≥　（ｃ　…　（ｃ　），；　ｉｆ（ｆ（ｘｆ，Ｏｉｌ）≠厂（　，，ｃｎ）Ａｆ（ｘｆ，Ｃｉｌ）≠　Ａ　／　，，Ｃｆ１）≠爿ｃＡＵ（　，，　Ｏｃ（　））　Ｒｃ＝一　｛＜　ｆ，　，＞｝　步骤５　ｆｏｒ（ｉｎｔ　：２；　；　＋＋）　｛ｉｆ（Ｒ　＝　，跳转至步骤６；　ｅｌｓｅ　Ｒｅｄ＝ＲｅｄＵ｛ｃ　２｝；　对　ｆ中任一区分对象对＜　＾，Ｘ，＞，若ｆ（ｘ＾，ｅｌｋ）≠　ｆ（ｘｆ，Ｃ　）八ｆ（ｘ＾，Ｃ＊）≠女ｉｘ，ｆ（ｘｆ，Ｃｉｋ）≠　，贝０　Ｒｃ＝Ｒｃ一　｛＜　，Ｘｆ＞｝。　步骤６输出属性约简Ｒｅｄ。　４．３算法分析　４．３．１算法正确性分析　算法３的第３步求的区分对象对集为　ｃ１。。，，并　非Ｒ　。因为　中的对象对在条件属性Ｃ　下只有　两种情况：（１）在条件属性Ｃ　下能够区分；（２）在条件　属性Ｃ　上不能区分，则必定能在Ｃ—Ｃ　中的条件属　性内区分开来。除此之外，没有其他可能。因此直　接求得Ｒ　，既可以加快算法计算效率，又可以减　少存储空间。由算法３的第５步得知，算法的终止条　件为Ｒ　＝（２ｊ，此时Ｒｃ＝　，从而算法是正确的。　４－３．２算法复杂度分析　算法１时间复杂度为ｏＯｃｌｌ￣　），算法２的时间复杂　度为ｏｏｃＩＩ　，算法３中步骤３的时间复杂度为ｏｑ　，　步骤４的时间复杂度为０ｑａ　一１Ｏ１Ｄ＋ｌ０２ＩｄＯｌ一　一　ｌａ２１）＋…＋ｌ　一１ｌｌａ　Ｄ　Ｏ（１ａｌ｝２＋ｌａ２ｒ＋…＋ｌａ　ｒ）＝Ｄｑ　），　步骤５由步骤４知。　＿｛ｃ，｝Ｄ≤ｏ（Ｉｃ￣　），最多循环　ｌＣＩ一１次，故步骤５的时间复杂度为ｏｏｑｌ泖）。故算　法总的时间复杂度为ＯｄＣｌ　ｌＯｌ　）。　５实例分析　为更好地说明新算法的实效性，以文献［３］中的　不完备决策表为例进行分析说明。　由算法１计算　（　）（ｊ＝１，２，…，６）的结果如下：　ｃ｜　１）＝｛　１｝；　（　２）＝｛　２，Ｘ６｝　王帅，徐章艳，曾艳燕：一种不完备决策表的属性约简算法　表１ｔ　小汽车决策表　注：ｃｌ代表Ｐｒｉｃｅ；ｃ２代表Ｍｉｌｅａｇｅ；ｃ３代表Ｓｉｚｅ；　ｃ４代表Ｍａｘ－ｓｐｅｅｄ。　３）＝｛　３｝；　ｘ４）＝｛　４，　５｝　（　５）＝｛　５，　４，　６｝；　（　６）＝｛　６，　２，　５｝　ａｃ（　１）＝Ｏｃ（　２）＝｛ｇｏｏｄ）　ｃ　３）＝｛ｐｏｏｒ）　ｃ　４）＝０ｃ（ｊｆ５）＝Ｏｃ　６）＝｛ｇｏｏｄ，ｅｘｃｅｌ｝　由算法２可得：Ｋ（ｃ１）－－２，Ｐ（ｃ１）＝４；Ｋ（ｃ２）＝２，　Ｐ（ｃ２）＝２；Ｋ（ｃ３）＝２，Ｐ（ｃ３）＝６；Ｋ（ｃ４）＝２，Ｐ（ｃ４）＝５。　由算法３的步骤２得：由于Ｋ（ｃ　）＝　（ｃ　）＝　（ｃ　）＝　Ｋ（ｃ４）＝２；则依据Ｐ（ｃｆ）进一步判断：Ｋ（ｃ１）＋尸（ｃ】）＝６；　Ｋ（ｃ２）＋Ｐ（ｃ２）＝４；Ｋ（ｃ３）＋Ｐ（ｃ３）：８；Ｋ（ｃ４）＋Ｐ（ｃ４）＝７。　依据Ｋ（ｃ　）＋Ｐ（ｃ　）进行排序，得对应的条件属性序列　为ｃ３，ｃ４，ｃ１，ｃ２。由步骤３求得Ｕ／Ｏｃ　）＝｛ａ１，ａ２，ａ３）；　ａ１＝｛　ｌ，　２｝；ａ２＝｛　３｝；ａ３＝｛　４，　５，　６｝。由步骤４得　Ｒｃ㈧＝｛＜　１，　５＞，＜　２，　５＞｝。　由步骤５得Ｒｅｄ＝｛ｃ３，Ｃ４｝　时，Ｒ　＝（ｚ）。算法终止，从而属性约简为｛Ｃ　，Ｃ　｝。　实例说明：计算过程中，不仅运用区分度Ｋ（ｃ　）　体现条件属性区分能力，还运用Ｐ（ｃ　）体现条件属性　完备度，充分利用条件属性的信息；在计算　，时，若　按常规计算，得　ｃ＝｛＜　１，　３＞，＜　１，Ｘ５＞，＜　２，　３＞，　＜　２，　５＞，＜　３，　４＞，＜　３，　５＞，＜　３，　６＞｝。其实根据　启发信息，在条件属性序列已定的情况下，直接计算　Ｒｃ㈧＝｛＜　１，　５＞，＜　２，　５＞｝，可以大大减　问。　６结论　为降低基于广义决策表的属性约简算法的时间　复杂度，本文提出了基于区分对象对集的属性约简　定义。然后证明区分对象对集的屙陛约简和基于广　义决策的属性约简的等价性，给出基于区分对象对　集的属性约简的新算法，该算法具有以下优点：　（１）以区分度Ｋ（ｃ　）作为启发信息，体现出条件　属性的区分能力。　（２）当区分度相同时，运用完备度Ｐ（ｃ　），进一步　挖掘出条件屙陛的现实意义。　（３）构造区分对象对集过程中，利用基数排序和　等价关系，有效提高算法效率。　进一步工作，研究其他模型下的属性约简高效　算法。　参考文献：　［１］Ｐａｗｌａｋ　Ｚ．Ｒｏｕｇｈ　ｓｅｔｓ［Ｊ］．Ｉｎｔｅｎｒａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ，１９８２，１１（５）：３４１—３５６．　［２］徐章艳，刘作鹏，杨炳儒，等．一个复杂度为ｍａｘ（Ｏ（ＩＣＩｌ￣），　Ｏ（１ｃｌ　ｌＵ／Ｃ１））的快速属性约简算法［Ｊ】＿计算机学报，２００６，　２９（３）：３９１—３９９．　［３］Ｋｒｙｓｚｋｉｅｗｉｃｚ　Ｍ．Ｒｏｕｇｈ　ｓｅｔ　ａｐｐｒｏａｃｈ　ｔｏ　ｉｎｃｏｍｐｌｅｔｅ　ｉｎ—　ｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ，１９９８，１１２：３９—４９．　［４］Ｓｔｅｆａｎｏｗｓｋｉ　Ｊ，Ｔｓｏｕｋｉａｓ　Ａ．Ｉｎｃｏｍｐｌｅｔｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｔａｂｌｅｓ　ｎａｄ　ｒｏｕｇｈ　ｃｌａｓｓｉｉｆｃａｔｉｏｎ［Ｊ］．Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，　２００１，７（３）：５４５．５６６．　［５王国胤．５］Ｒｏｕｇｈ集理论在不完备信息系统中的扩充［Ｊ］．计算　机研究与发展，２００２，３９（１０）：１２３８—１２４３．　［６】黄兵，周献中，张蓉蓉．基于信息量的不完备信息系统属性　约简［Ｊ］．系统工程理论与实践，２００５，２５（４）：５５．６０．　［７］李秀红，史开泉．一种基于知识粒度的不完备信息系统的　屙『生约简算法［Ｊ］．计算机科学，２００６，３３（１１）：１６９．１９９．　［８］曾晓辉，文展．不完备信息系统的屙Ｉ生约简［Ｊ］．计算机工程，　２００９，３５（２４）：１８５．１８７．　［９］滕书华，昝德才，孙即祥，等．基于同可区分度的属性约简　算法［Ｊ］．模式识别与人工智能，２０１０，２３（５）：６３０．６３８．　［１０］舒文豪，徐章艳，钱文斌，等．不完备决策表的差别矩阵属　性约简算法［Ｊ］．计算　．工程与应用，２０１　ｌ，４７（２４）：１０３．１０５．　［１　１］Ｋｒｙｓｚｋｉｅｗｉｃｚ　Ｍ．Ｒｕｌｅｓ　ｉｎ　ｉｎｃｏｍｐｌｅｔｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓ—　ｔｅｍｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅｓ，１９９９，１１３（２）：２７１．２９２．