第12卷第3期 智能系统学报 Vol.12 No.3 2017年6月 CAAI Transactions on Intelligent Systems Jun.2017 D0I:10.11992/is.21704025 网络出版地址：http:/kns.cmki.net/kcms/detail/23.1538.TP.20170703.1853.010.html 广义分布保持属性约简研究 高学义12，张楠2，童向荣12，姜丽丽12 (1.烟台大学数据科学与智能技术山东省高校重，点实验室，山东烟台264005：2.烟台大学计算机与控制工程学 院，山东烟台264005) 摘要：属性约简是粗糙集理论的重要研究内容之一。分布约简保证约简前后每个对象的概率分布保持不变，即保 证每条规则的置信度在约简前后不发生改变。实际应用中，人们往往更加关注可信度较高或较低的规则。因此，在 本文中引入了广义分布保持属性约简，该属性约简可以保证规则的置信度P(P∈[0，α]或[B,1])在约简前后不变。 同时，给出了广义分布保持属性约简的判定方法与基于差别矩阵的广义分布保持属性约简算法，深入讨论了几种特 殊情形下的广义分布保持约简。最后，在4个UCI数据集上进行的实验分析表明，几种特殊情形下的广义分布保持 属性约简可退化为已有的一些属性约简，且在不同置信区间下求得的广义分布保持属性约简存在包含关系，验证了 相关结论的正确性。 关键词：分布保持：属性约简：粗糙集：概率分布：差别矩阵 中图分类号：TP181文献标志码：A文章编号：1673-4785(2017)03-0377-09 中文引用格式：高学义，张楠，童向荣，等.广义分布保持属性约简研究[J].智能系统学报，2017,12(3)：377-385 英文引用格式：GAO Xueyi,ZHANG Nan,TONG Xiangrong,etat.Research on attribute reduction using generalized distribution preservation[J].CAAI transactions on intelligent systems,2017,12(3):377-385. Research on attribute reduction using generalized distribution preservation GAO Xueyi2,ZHANG Nan'2,TONG Xiangrong'2,JIANG Lili2 (1.Key Lab for Data Science and Intelligent Technology of Shandong Higher Education Institutes,Yantai University,Yantai 264005, China;2.School of Computer and Control Engineering,Yantai University,Yantai 264005,China) Abstract:Attribute reduction is a pertinent issue in rough set theory.Distribution reduction ensures that the probability distribution of each target does not change before and after reduction;i.e.,it ensures that the confidence of every rule remains unchanged before and after reduction.In actual applications,people are often interested in rules that have higher or lower confidences.Thus,attribute reduction based on generalized distribution preservation is proposed in this paper.Confidences in [0,a]or [B,1]were unchanged using the proposed technique.We also propose judgment methods for generalized-distribution-preservation attribute reduction and investigate the generalized attribute-reduction algorithm based on a discernibility matrix.Some special cases with respect to generalized-distribution-preservation attribute reduction are discussed in depth.Finally,experiments on four data sets downloaded from UCI show that some special cases with respect to generalized distribution preservation reduction could degenerate into some existing attribute reductions and inclusion relations exist in generalized distribution preservation attribute reduction under different confidence intervals,verifying the correctness of the relevant conclusions. Keywords:distribution preservation;attribute reduction;rough sets;probability distribution;discernibility matrix 粗糙集理论是由波兰学者Pawlak教授于1982 年提出的一种用于处理和分析不确定、不精确数据 的数学方法与工具[1-]。目前，粗糙集理论在机器 收稿日期：2017-04-19.网络出版日期：2017-07-03. 基金项目：国家自然科学基金项目(61403329,61572418,61502410. 学习、决策分析、模式识别、数据挖掘和智能信息处 61572419):山东省自然科学基金项目(ZR2013FQ020, 理等领域得到了广泛应用。 ZR2015PF010):山东省高等学校科技计划项目(J15LN09 116LN17). 属性约简或知识约简是粗糙集理论的重要研 通信作者：张楠.E-mail:zhangnane0851@163.com
第 １２ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．３ ２０１７ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ． ２１７０４０２５ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０７０３．１８５３．０１０．ｈｔｍｌ 广义分布保持属性约简研究 高学义１，２ ，张楠１，２ ，童向荣１，２ ，姜丽丽１，２ （１． 烟台大学 数据科学与智能技术山东省高校重点实验室，山东 烟台 ２６４００５； ２． 烟台大学 计算机与控制工程学 院，山东 烟台 ２６４００５） 摘 要：属性约简是粗糙集理论的重要研究内容之一。 分布约简保证约简前后每个对象的概率分布保持不变，即保 证每条规则的置信度在约简前后不发生改变。 实际应用中，人们往往更加关注可信度较高或较低的规则。 因此，在 本文中引入了广义分布保持属性约简，该属性约简可以保证规则的置信度 Ｐ（Ｐ∈［０，α］或［ β，１］）在约简前后不变。 同时，给出了广义分布保持属性约简的判定方法与基于差别矩阵的广义分布保持属性约简算法，深入讨论了几种特 殊情形下的广义分布保持约简。 最后，在 ４ 个 ＵＣＩ 数据集上进行的实验分析表明，几种特殊情形下的广义分布保持 属性约简可退化为已有的一些属性约简，且在不同置信区间下求得的广义分布保持属性约简存在包含关系，验证了 相关结论的正确性。 关键词：分布保持；属性约简；粗糙集；概率分布；差别矩阵 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０３－０３７７－０９ 中文引用格式：高学义，张楠，童向荣，等．广义分布保持属性约简研究［Ｊ］． 智能系统学报， ２０１７， １２（３）： ３７７－３８５． 英文引用格式：ＧＡＯ Ｘｕｅｙｉ，ＺＨＡＮＧ Ｎａｎ，ＴＯＮＧ Ｘｉａｎｇｒｏｎｇ，ｅｔ ａｔ． Ｒｅｓｅａｒｃｈ ｏｎ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｕｓｉｎｇ ｇｅｎｅｒａｌｉｚｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｐｒｅｓｅｒｖａｔｉｏｎ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（３）： ３７７－３８５． Ｒｅｓｅａｒｃｈ ｏｎ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｕｓｉｎｇ ｇｅｎｅｒａｌｉｚｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｐｒｅｓｅｒｖａｔｉｏｎ ＧＡＯ Ｘｕｅｙｉ １，２ ， ＺＨＡＮＧ Ｎａｎ １，２ ， ＴＯＮＧ Ｘｉａｎｇｒｏｎｇ １，２ ， ＪＩＡＮＧ Ｌｉｌｉ １，２ （１．Ｋｅｙ Ｌａｂ ｆｏｒ Ｄａｔａ Ｓｃｉｅｎｃｅ ａｎｄ Ｉｎｔｅｌｌｉｇｅｎｔ Ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｓｈａｎｄｏｎｇ Ｈｉｇｈｅｒ Ｅｄｕｃａｔｉｏｎ Ｉｎｓｔｉｔｕｔｅｓ， Ｙａｎｔａｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｙａｎｔａｉ ２６４００５， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｎｔｒｏｌ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｙａｎｔａｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｙａｎｔａｉ ２６４００５， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｉｓ ａ ｐｅｒｔｉｎｅｎｔ ｉｓｓｕｅ ｉｎ ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ． Ｄｉｓｔｒｉｂｕｔｉｏｎ ｒｅｄｕｃｔｉｏｎ ｅｎｓｕｒｅｓ ｔｈａｔ ｔｈｅ ｐｒｏｂａｂｉｌｉｔｙ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｅａｃｈ ｔａｒｇｅｔ ｄｏｅｓ ｎｏｔ ｃｈａｎｇｅ ｂｅｆｏｒｅ ａｎｄ ａｆｔｅｒ ｒｅｄｕｃｔｉｏｎ； ｉ．ｅ．， ｉｔ ｅｎｓｕｒｅｓ ｔｈａｔ ｔｈｅ ｃｏｎｆｉｄｅｎｃｅ ｏｆ ｅｖｅｒｙ ｒｕｌｅ ｒｅｍａｉｎｓ ｕｎｃｈａｎｇｅｄ ｂｅｆｏｒｅ ａｎｄ ａｆｔｅｒ ｒｅｄｕｃｔｉｏｎ． Ｉｎ ａｃｔｕａｌ ａｐｐｌｉｃａｔｉｏｎｓ， ｐｅｏｐｌｅ ａｒｅ ｏｆｔｅｎ ｉｎｔｅｒｅｓｔｅｄ ｉｎ ｒｕｌｅｓ ｔｈａｔ ｈａｖｅ ｈｉｇｈｅｒ ｏｒ ｌｏｗｅｒ ｃｏｎｆｉｄｅｎｃｅｓ． Ｔｈｕｓ， ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｇｅｎｅｒａｌｉｚｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｐｒｅｓｅｒｖａｔｉｏｎ ｉｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ． Ｃｏｎｆｉｄｅｎｃｅｓ ｉｎ ［０， α］ ｏｒ ［β， １］ ｗｅｒｅ ｕｎｃｈａｎｇｅｄ ｕｓｉｎｇ ｔｈｅ ｐｒｏｐｏｓｅｄ ｔｅｃｈｎｉｑｕｅ． Ｗｅ ａｌｓｏ ｐｒｏｐｏｓｅ ｊｕｄｇｍｅｎｔ ｍｅｔｈｏｄｓ ｆｏｒ ｇｅｎｅｒａｌｉｚｅｄ⁃ｄｉｓｔｒｉｂｕｔｉｏｎ⁃ｐｒｅｓｅｒｖａｔｉｏｎ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｎｄ ｉｎｖｅｓｔｉｇａｔｅ ｔｈｅ ｇｅｎｅｒａｌｉｚｅｄ ａｔｔｒｉｂｕｔｅ⁃ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ａ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ． Ｓｏｍｅ ｓｐｅｃｉａｌ ｃａｓｅｓ ｗｉｔｈ ｒｅｓｐｅｃｔ ｔｏ ｇｅｎｅｒａｌｉｚｅｄ⁃ｄｉｓｔｒｉｂｕｔｉｏｎ⁃ｐｒｅｓｅｒｖａｔｉｏｎ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｒｅ ｄｉｓｃｕｓｓｅｄ ｉｎ ｄｅｐｔｈ． Ｆｉｎａｌｌｙ， ｅｘｐｅｒｉｍｅｎｔｓ ｏｎ ｆｏｕｒ ｄａｔａ ｓｅｔｓ ｄｏｗｎｌｏａｄｅｄ ｆｒｏｍ ＵＣＩ ｓｈｏｗ ｔｈａｔ ｓｏｍｅ ｓｐｅｃｉａｌ ｃａｓｅｓ ｗｉｔｈ ｒｅｓｐｅｃｔ ｔｏ ｇｅｎｅｒａｌｉｚｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｐｒｅｓｅｒｖａｔｉｏｎ ｒｅｄｕｃｔｉｏｎ ｃｏｕｌｄ ｄｅｇｅｎｅｒａｔｅ ｉｎｔｏ ｓｏｍｅ ｅｘｉｓｔｉｎｇ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎｓ ａｎｄ ｉｎｃｌｕｓｉｏｎ ｒｅｌａｔｉｏｎｓ ｅｘｉｓｔ ｉｎ ｇｅｎｅｒａｌｉｚｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｐｒｅｓｅｒｖａｔｉｏｎ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ ｃｏｎｆｉｄｅｎｃｅ ｉｎｔｅｒｖａｌｓ， ｖｅｒｉｆｙｉｎｇ ｔｈｅ ｃｏｒｒｅｃｔｎｅｓｓ ｏｆ ｔｈｅ ｒｅｌｅｖａｎｔ ｃｏｎｃｌｕｓｉｏｎｓ． Ｋｅｙｗｏｒｄｓ： ｄｉｓｔｒｉｂｕｔｉｏｎ ｐｒｅｓｅｒｖａｔｉｏｎ； ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ； ｒｏｕｇｈ ｓｅｔｓ； ｐｒｏｂａｂｉｌｉｔｙ ｄｉｓｔｒｉｂｕｔｉｏｎ； ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ 收稿日期：２０１７－０４－１９． 网络出版日期：２０１７－０７－０３． 基金项目：国家自然科学基金项目（ ６１４０３３２９， ６１５７２４１８， ６１５０２４１０， ６１５７２４１９）；山 东 省 自 然 科 学 基 金 项 目 （ ＺＲ２０１３ＦＱ０２０， ＺＲ２０１５ＰＦ ０１０）；山东省高等学校科技计划项目（ Ｊ１５ＬＮ０９， １１６ＬＮ１７）． 通信作者：张楠．Ｅ⁃ｍａｉｌ：ｚｈａｎｇｎａｎ０８５１＠ １６３．ｃｏｍ． 粗糙集理论是由波兰学者 Ｐａｗｌａｋ 教授于 １９８２ 年提出的一种用于处理和分析不确定、不精确数据 的数学方法与工具［１－４］ 。 目前，粗糙集理论在机器 学习、决策分析、模式识别、数据挖掘和智能信息处 理等领域得到了广泛应用。 属性约简或知识约简是粗糙集理论的重要研
·378 智能系统学报 第12卷 究内容之一，其本质是获取保持知识库某种分类能 (P(D[u:]),P(D2[u:]),P(Du:])). 力在约简前后不发生改变的最小属性子集描述，国 其中，P(D|[]4)=|D,n[u,]4l/八[u:]al,ie{1, 内外学者做了大量的相关研究工作。1992年， 2,…,nj∈{1,2，…，|U/Dl}o SkowrontS)提出了差别矩阵的概念，为获取信息系统 定义2设决策表DT=(U,ATUD,V,f),U= 或决策表的所有约简或最小约简提供了理论基础： {41,山2，…，un},U/D={D1,D2,…,D1wom},记d为 1998年，Kryszkiewicz讨论了基于差别矩阵的不完 D,对应的决策值，则Hu:∈U,A二AT,u:在A下关于 备信息系统广义决策保持属性约简问题：2003年， 决策属性D的[α，B]决策-置信度序偶集定义为 张文修等)给出了分布约简和分配约简的差别矩 Y(u:)=(d,P(DI[u:])> 阵约简方法，并提出了最大分布约简；2007年，徐伟 a≤P(Dl[山：]a)≤BAa≤P(Dl[u:]Ar)≤B吲 华等[劉给出了优势关系下基于差别矩阵的分布约 式中：i∈{1,2，…，n}j∈{1,2，…，U/D},a和B 简和最大分布约简：2009年，苗夺谦等[提出了不 满足(a=0∧Be[0,1])或(a∈[0,1]∧B=1)。 可分辨关系保持属性约简和相应的差别矩阵构造 根据定义2，若对于Vu∈U,均满足Ya(u)= 方法：2010年，张楠等10讨论了区间值信息系统下 Y:(u),则称A是广义分布协调集。若A是广义 的属性约简问题。为了提高属性约简的算法效率， 分布协调集，且A的任意子集不是广义分布协调 多种启发式属性约简算法相继被提出。1999年，苗 集，则称A为广义分布保持约简。据此，给出广义 夺谦等山从信息论的角度给出了属性重要度的度 分布保持约简的形式化定义如下。 量方法，在此基础上提出了基于互信息的启发式约 定义3给定决策表DT=(U,ATUD,V,f), 简算法：2002年，王国胤等1提出了基于条件信息 U={山1，山2，…，山n},VACAT,若A是一个广义分布 嫡的启发式属性约简算法：2010年，钱宇华等1)提 保持约简，当且仅当以下两个条件成立： 出了正向近似的基本概念并将其应用于启发式属 1)YuU,Y (u)=Y (u); 性约简的构造过程，提高了属性约简的计算效率： 2)HBCA,YAa(u）≠Y(w)。 2011年，钱宇华等[4-s1进一步将正向近似应用于不 式中：a和B满足(a=0八B∈[0,1])或(a∈[0,1]A 完备决策表的启发式属性约简，改善了不完备决策 B=1),i,je{1,2,…,n}。 表下启发式属性约简的求取效率：陈红梅等[16-17)]在 由定义3可知，对于置信度在[α，B]内的规则， 动态属性约简方面做了大量的研究工作；文献[18- 它们的置信度在广义分布保持约简前后保持不变。 19]对现有的属性约简之间的关系进行了深入讨论 2广义分布保持属性约简的判定与 与研究。 分布约简保证每个对象在约简前后的概率分 方法 布保持不变，即保证每条规则的置信度在约简前后 首先，给出广义分布协调集的等价证明。 不发生改变。在实际应用中，人们往往更关注可信 定理1设决策表DT=(U,ATUD,V,f),U= 度较高或较低的规则20)，分布约简的标准过于严 {u1,2,…,un},A≤AT,则A是广义分布协调集 格，很多对实际决策无用的规则的置信度在约简前 当且仅当对于Hu,4,∈U,当Y(u,)≠Y(u) 后也要保持不变，很可能使得最终约简过于冗长， 成立时，有[4：]4∩[]4=☑。其中，a和B满足 对实际决策造成一定的干扰。本文在分布约简的 (a=0AB∈[0,1])或（∈[0,1]AB=1)。 基础上，通过弱化分布约简的约简标准，提出了一 证明不妨记p([4:]4)={[山]r:[u]ArC 种新的属性约简，即广义分布保持属性约简，该属 [u:]4},其中i,j∈{1,2，…，n}。由于ACAT,故 性约简可以保证规则的置信度(P∈[0，α]或[B, p([u:])构成[u:]a的一个划分。 1])在约简前后不变，并对广义分布保持属性约简 “→”：设A是决策表DT上的广义分布协调 的方法和相关性质进行了研究和讨论。 集。4，叫eU,当[山，]4n[4,]4≠时，有[4]4= [4]A。因此Ya(山，)=Ya(w)。但有Y(u:)= 1广义分布保持属性约简 Y(u,)成立，并且有Y(4,)=Ya(u,),从 定义1)设决策表DT=(U,ATUD,V,f),论域 而Y(u)=Y(4,)。因此，若Y(u:）≠ U={山1,2，…，山n},则H:∈U,ACAT,对象：在属性 Y(4),有[u]an[4]=0。 A下关于决策属性集D的概率分布定义为u,(u,)= “=”:对于H4,∈U,当[u]灯≤[u:]A时，有
究内容之一，其本质是获取保持知识库某种分类能 力在约简前后不发生改变的最小属性子集描述，国 内外 学 者 做 了 大 量 的 相 关 研 究 工 作。 １９９２ 年， Ｓｋｏｗｒｏｎ ［５］提出了差别矩阵的概念，为获取信息系统 或决策表的所有约简或最小约简提供了理论基础； １９９８ 年，Ｋｒｙｓｚｋｉｅｗｉｃｚ ［６］讨论了基于差别矩阵的不完 备信息系统广义决策保持属性约简问题；２００３ 年， 张文修等［７］ 给出了分布约简和分配约简的差别矩 阵约简方法，并提出了最大分布约简；２００７ 年，徐伟 华等［８］给出了优势关系下基于差别矩阵的分布约 简和最大分布约简；２００９ 年，苗夺谦等［９］ 提出了不 可分辨关系保持属性约简和相应的差别矩阵构造 方法；２０１０ 年，张楠等［１０］ 讨论了区间值信息系统下 的属性约简问题。 为了提高属性约简的算法效率， 多种启发式属性约简算法相继被提出。 １９９９ 年，苗 夺谦等［１１］从信息论的角度给出了属性重要度的度 量方法，在此基础上提出了基于互信息的启发式约 简算法；２００２ 年，王国胤等［１２］ 提出了基于条件信息 熵的启发式属性约简算法；２０１０ 年，钱宇华等［１３］ 提 出了正向近似的基本概念并将其应用于启发式属 性约简的构造过程，提高了属性约简的计算效率； ２０１１ 年，钱宇华等［１４－１５］进一步将正向近似应用于不 完备决策表的启发式属性约简，改善了不完备决策 表下启发式属性约简的求取效率；陈红梅等［１６－１７］ 在 动态属性约简方面做了大量的研究工作；文献［１８－ １９］对现有的属性约简之间的关系进行了深入讨论 与研究。 分布约简保证每个对象在约简前后的概率分 布保持不变，即保证每条规则的置信度在约简前后 不发生改变。 在实际应用中，人们往往更关注可信 度较高或较低的规则［２０］ ，分布约简的标准过于严 格，很多对实际决策无用的规则的置信度在约简前 后也要保持不变，很可能使得最终约简过于冗长， 对实际决策造成一定的干扰。 本文在分布约简的 基础上，通过弱化分布约简的约简标准，提出了一 种新的属性约简，即广义分布保持属性约简，该属 性约简可以保证规则的置信度（ Ｐ∈［ ０，α］ 或［ β， １］）在约简前后不变，并对广义分布保持属性约简 的方法和相关性质进行了研究和讨论。 １ 广义分布保持属性约简 定义 １ ［７］ 设决策表 ＤＴ＝（Ｕ，ＡＴ∪Ｄ，Ｖ， ｆ），论域 Ｕ＝｛ｕ１，ｕ２，…，ｕｎ ｝，则∀ｕｉ∈Ｕ，Ａ⊆ＡＴ，对象 ｕｉ 在属性 Ａ 下关于决策属性集 Ｄ 的概率分布定义为 μＡ（ｕｉ） ＝ （Ｐ（Ｄ１ ［ｕｉ］Ａ），Ｐ（Ｄ２ ［ｕｉ］Ａ），…，Ｐ（Ｄ Ｕ／ Ｄ ［ｕｉ］Ａ））。 其中，Ｐ（Ｄｊ ［ｕｉ］ Ａ ） ＝ Ｄｊ∩［ｕｉ］ Ａ ／ ［ｕｉ］ Ａ ，ｉ∈｛１， ２，…，ｎ｝，ｊ∈｛１，２，…， Ｕ／ Ｄ ｝。 定义 ２ 设决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ），Ｕ ＝ ｛ｕ１ ，ｕ２ ，…，ｕｎ ｝，Ｕ／ Ｄ ＝ ｛Ｄ１ ，Ｄ２ ，…，Ｄ｜ Ｕ／ Ｄ｜ ｝，记 ｄｊ 为 Ｄｊ 对应的决策值，则∀ｕｉ∈Ｕ，Ａ⊆ＡＴ，ｕｉ 在 Ａ 下关于 决策属性 Ｄ 的［α，β］决策－置信度序偶集定义为 Υ ［α，β］ Ａ （ｕｉ） ＝ ｛〈ｄｊ，Ｐ（Ｄｊ ［ｕｉ］ Ａ ）〉 α ≤ Ｐ（Ｄｊ ［ｕｉ］Ａ） ≤ β ∧ α ≤ Ｐ（Ｄｊ ［ｕｉ］ＡＴ） ≤ β｝ 式中：ｉ∈｛１，２，…，ｎ｝，ｊ∈｛１，２，…， Ｕ／ Ｄ ｝，α 和 β 满足（α＝ ０∧β∈［０，１］）或（α∈［０，１］∧β ＝ １）。 根据定义 ２，若对于∀ｕ∈Ｕ，均满足 Υ ［α，β］ Ａ （ｕ）＝ Υ ［α，β］ ＡＴ （ｕ），则称 Ａ 是广义分布协调集。 若 Ａ 是广义 分布协调集，且 Ａ 的任意子集不是广义分布协调 集，则称 Ａ 为广义分布保持约简。 据此，给出广义 分布保持约简的形式化定义如下。 定义 ３ 给定决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ ）， Ｕ＝ ｛ｕ１ ，ｕ２ ，…，ｕｎ ｝，∀Ａ⊆ＡＴ，若 Ａ 是一个广义分布 保持约简，当且仅当以下两个条件成立： １）∀ｕｉ⊆Ｕ，Υ ［α，β］ Ａ （ｕｉ）＝ Υ ［α，β］ ＡＴ （ｕｉ）； ２）∀Ｂ⊂Ａ，Υ ［α，β］ Ｂ （ｕｊ）≠Υ ［α，β］ Ａ （ｕｊ）。 式中：α 和 β 满足（α＝０∧β∈［０，１］）或（α∈［０，１］∧ β ＝ １），ｉ，ｊ∈｛１，２，…，ｎ｝。 由定义 ３ 可知，对于置信度在［α，β］内的规则， 它们的置信度在广义分布保持约简前后保持不变。 ２ 广义分布保持属性约简的判定与 方法 首先，给出广义分布协调集的等价证明。 定理 １ 设决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ ），Ｕ ＝ ｛ｕ１ ，ｕ２ ，…，ｕｎ ｝，∀Ａ⊆ＡＴ，则 Ａ 是广义分布协调集 当且仅当对于∀ｕｉ，ｕｊ∈Ｕ，当 Υ ［α，β］ ＡＴ （ｕｉ）≠Υ ［α，β］ ＡＴ （ｕｊ） 成立时，有［ ｕｉ ］ Ａ ∩［ ｕｊ ］ Ａ ＝ ⌀。 其中，α 和 β 满足 （α＝ ０∧β∈［０，１］）或（α∈［０，１］∧β ＝ １）。 证明 不妨记 ρ（［ ｕｉ ］ Ａ ） ＝ ｛［ ｕｊ ］ ＡＴ ：［ ｕｊ ］ ＡＴ ⊆ ［ｕｉ ］ Ａ ｝，其中 ｉ，ｊ∈｛１，２，…，ｎ｝。 由于 Ａ⊆ＡＴ，故 ρ（［ｕｉ］ Ａ ）构成［ｕｉ］ Ａ 的一个划分。 “⇒”： 设 Ａ 是决策表 ＤＴ 上的广义分布协调 集。 ∀ｕｉ，ｕｊ∈Ｕ，当［ｕｉ］ Ａ∩［ ｕｊ］ Ａ≠⌀时，有［ ｕｉ］ Ａ ＝ ［ｕｊ］Ａ。 因此 Υ ［α，β］ Ａ （ｕｉ ）＝ Υ ［α，β］ Ａ （ｕｊ ）。 但有 Υ ［α，β］ ＡＴ （ｕｉ ）＝ Υ ［α，β］ Ａ （ｕｉ） 成立，并且有 Υ ［α，β］ ＡＴ （ ｕｊ ） ＝ Υ ［α，β］ Ａ （ ｕｊ ），从 而 Υ ［α，β］ ＡＴ （ｕｉ）＝ Υ ［α，β］ ＡＴ （ ｕｊ ）。 因此， 若 Υ ［α，β］ ＡＴ （ ｕｉ ） ≠ Υ ［α，β］ ＡＴ （ｕｊ），有［ｕｉ］ Ａ∩［ｕｊ］ Ａ ＝⌀。 “⇐”：对于∀ｕｉ ∈Ｕ，当［ｕｊ］ ＡＴ ⊆［ｕｉ］ Ａ 时，有 ·３７８· 智 能 系 统 学 报 第 １２ 卷
第3期 高学义，等：广义分布保持属性约简研究 .379· [u:]4n[w]4≠☑，故Yg()=Y(u)。即对 “←”：不妨假设3(u,山)eD°，使得AnM)= 于HDeU/D,记d为D对应的决策值，若(d, ②，显然Y(u)≠Y(y,)。HaeA,必然有a年 P(D[u,]Ar)）eY(u,),则必有(d,P(D Ma,也即f(a,4,)=f(a,马)。故有[4]a=[u,]A [4]Ar)》eYg1(4)成立，并且P(D|[u]r)= [u:]4∩[4]A≠0，由定理1可得A不是广义分布协调 P(D:[4]Ar),其中，k∈{1,2，…，|U/D}。为后续 集。定理得证。 证明方便，不妨记p([u:]a)={p1,P1,…P1p(,。 定义5设DT=(U,ATUD,V,f),M1为广 由于p([:]a)={[u:]r:[u:]Ar[u:]a},故有 义分布保持约简的差别矩阵，其对应的差别函数为 Ie(I DF(Ma间)=∧{VMaI1≤i≤j≤n 式中：VM]=Va(a∈Ma)表示Ma]中所有 P(D [u;])=- ie.() I[u:] 属性的析取，且a和B满足（α=0∧B∈[0,1]）或 p.Del le.I (a∈[0,1]ΛB=1)。 u]T([u]= 通过化DF(M])的主合取范式转化为主析 Ip([a】) 取范式即可得到所有广义分布保持属性约简。 习 le,I Pna.)TaRepa1 定理3设DT=(U,ATUD,V,fD,Ma1为DT ( e,I 的广义分布保持约简的差别矩阵，且α和B满足 {Pa,Illr)'Tp,ep[ul. (a=0∧B∈[0,1])或(a∈[0,1]AB=1)。DF P(DI[u:]Ar） (Ma,刷])是由Ma]导出的差别函数，DF(Ma])的 因此，Y刷(u:)=Ya(u),从而A是广义分 极小析取范式为 布协调集，证毕。 DF(M)=立(Ra,)。 k=1x=1 定理1给出了判断属性子集是广义分布协调集 记Ak={as=1,2,…,9},则{A4k=1,2,…, 的方法，由此可进一步得到广义分布保持约简的方 t是决策表的所有广义分布保持约简，其中t表示 法，在此可给出广义分布差别矩阵的概念。 DF(Ma])的极小析取范式中的合取项数目。 定义4给定决策表DT=(U,ATUD,V,f), 证明Vk≤t,HMa)∈Ma],由极小析取 U=山1，山2，…，n},AT={a1,a2,…,a1r}为条件 范式的定义知A∩M1≠⑦，再由定理2可得A 属性集，D={d}为决策属性，记 D°={(u,4)Y(:)≠Y(4)月 是广义分布协调集。同时，DF(Ma)=(A), 定义 若在A:中去掉任意一个属性形成A:,则必然 AT))()D 3Ma)∈Ma],使得A∩M]=☑，故A不是 广义分布协调集，从而A是广义分布保持约简。 AT,(4,4）年D° 由于DF(Ma])中包含了所有的Ma),因此 为(u,4)的广义分布可辨识属性集，Ma刷= 不存在其他的广义分布保持约简，定理得证。 {Ma|i,j∈{l,2,…,n}为决策表的-个nxn的 广义分布差别矩阵，其为对称矩阵，α和B满足(a= 3广义分布保持属性约简算法 0AB∈[0,1])或(a∈[0,1]∧B=1)。 本节给出广义分布保持约简算法(generalized 定理2设DT=(U,ATUD,V,f),VACAT, distribution preservation reduction algorithm,GDPRA), 则A是广义分布协调集一H山，叫∈U,若M≠ 算法描述如下。 O,有AnMa]≠☑。其中，a和B满足(a=0 输入决策表DT=(U,ATUD,V,f),a和B。 B∈[0,1])或(a∈[0,1]AB=1). 输出DT的所有广义分布保持属性约简。 证明若(u,4)使D·,显然有A∩M≠☑。 1)计算每个对象在条件属性集下关于决策属 反之，则有 性的置信度分布ur0 “→”：由于A是广义分布协调集，故对于 2)根据每个对象的置信度分布ur获取每个对 (u,4)∈D°，Y(u,)≠Y(4,),由定理1可 象的[α，B]决策-置信度序偶集。 得[u:]an[4]a=。因此，3aeA,不等式f(a, 3)根据对象之间的决策-置信度序偶集构造相 u:)≠f(a,u)成立，故aeMa,即AnMa≠O。 应的广义分布差别矩阵
［ｕｉ］ Ａ∩［ｕｊ］ Ａ≠⌀，故 Υ ［α，β］ ＡＴ （ｕｉ）＝ Υ ［α，β］ ＡＴ （ｕｊ）。 即对 于∀Ｄｋ∈Ｕ／ Ｄ，记 ｄｋ 为 Ｄｋ 对应的决策值，若〈 ｄｋ， Ｐ（Ｄｋ ［ｕｉ］ ＡＴ ）〉 ∈ Υ ［α，β］ ＡＴ （ ｕｉ ）， 则 必 有 〈 ｄｋ， Ｐ（Ｄｋ ［ｕｊ］ ＡＴ ）〉 ∈Υ ［α，β］ ＡＴ （ ｕｊ ） 成立，并且 Ｐ（Ｄｋ ［ｕｉ］ＡＴ ） ＝ Ｐ（Ｄｋ ［ｕｊ］ＡＴ），其中，ｋ∈｛１，２，…， Ｕ／ Ｄ ｝。 为后续 证明方便，不妨记 ρ（［ｕｉ］ Ａ ）＝ ｛ρ１ ，ρ１ ，…，ρ ρ（［ｕｉ ］ Ａ ） ｝。 由于 ρ（［ｕｉ］ Ａ）＝ ｛［ｕｉ］ＡＴ ∶ ［ｕｉ］ ＡＴ⊆［ｕｉ］ Ａ ｝，故有 Ｐ（Ｄｋ ［ｕｉ］Ａ） ＝ ∑ ρ（［ｕｉ ］Ａ ） ｓ ＝ １ ｛ ρｓ ∩ Ｄｋ ：ρｓ ∈ ρ（［ｕｉ］Ａ）｝ ［ｕｉ］Ａ ＝ ∑ ρ（［ｕｉ ］ Ａ ） ｓ ＝ １ ρｓ ∩ Ｄｋ ρｓ · ρｓ ［ｕｉ］ Ａ ：ρ { ｓ ∈ ρ（［ｕｉ］ Ａ ）} ＝ ∑ ρ（［ｕｉ ］ Ａ ） ｓ ＝ １ Ｐ（Ｄｋ ρｓ）· ρｓ ［ｕｉ］ Ａ ：ρ { ｓ ∈ ρ（［ｕｉ］ Ａ ）} ＝ ∑ ρ（［ｕｉ ］Ａ ） ｓ ＝ １ Ｐ（Ｄｋ ［ｕｉ］ＡＴ）· ρｓ ［ｕｉ］Ａ ：ρ { ｓ ∈ ρ（［ｕｉ］Ａ）} ＝ Ｐ（Ｄｋ ［ｕｉ］ ＡＴ ） 因此，Υ ［α，β］ ＡＴ （ｕｉ） ＝ Υ ［α，β］ Ａ （ ｕｉ），从而 Ａ 是广义分 布协调集，证毕。 定理 １ 给出了判断属性子集是广义分布协调集 的方法，由此可进一步得到广义分布保持约简的方 法，在此可给出广义分布差别矩阵的概念。 定义 ４ 给定决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ， ｆ ）， Ｕ＝ ｛ｕ１ ，ｕ２ ，…，ｕｎ ｝，ＡＴ ＝ ｛ ａ１ ，ａ２ ，…，ａ ＡＴ ｝ 为条件 属性集，Ｄ＝ ｛ｄ｝为决策属性，记 Ｄ ∗ ＝ ｛（ｕｉ，ｕｊ） Υ ［α，β］ ＡＴ （ｕｉ） ≠ Υ ［α，β］ ＡＴ （ｕｊ）｝ 定义 Ｍ ［α， β］ ｉｊ ＝ ｛ａ ∈ ＡＴ ｆ（ａ，ｕｉ） ≠ ｆ（ａ，ｕｊ）｝，（ｕｉ，ｕｊ）∈Ｄ ∗ ＡＴ， （ｕｉ，ｕｊ） ∉ Ｄ { ∗ 为（ ｕｉ， ｕｊ ） 的 广 义 分 布 可 辨 识 属 性 集， Ｍ ［α，β］ ＝ ｛Ｍ ［α，β］ ｉｊ ｉ，ｊ∈｛１，２，…，ｎ｝｝为决策表的一个 ｎ×ｎ 的 广义分布差别矩阵，其为对称矩阵，α 和 β 满足（α ＝ ０∧β∈［０，１］）或（α∈［０，１］∧β ＝ １）。 定理 ２ 设 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ ），∀Ａ⊆ＡＴ， 则 Ａ 是广义分布协调集⇔∀ｕｉ，ｕｊ∈Ｕ，若 Ｍ ［α，β］ ｉｊ ≠ ⌀，有 Ａ∩Ｍ ［α，β］ ｉｊ ≠⌀。 其中，α 和 β 满足（ α ＝ ０∧ β∈［０，１］）或（α∈［０，１］∧β ＝ １）。 证明 若（ｕｉ，ｕｊ）∉Ｄ ∗ ，显然有 Ａ∩Ｍ ［α，β］ ｉｊ ≠⌀。 反之，则有 “⇒”： 由 于 Ａ 是 广 义 分 布 协 调 集， 故 对 于 ∀（ｕｉ，ｕｊ）∈Ｄ ∗ ，Υ ［α，β］ ＡＴ （ｕｉ）≠Υ ［α，β］ ＡＴ （ｕｊ），由定理 １ 可 得［ｕｉ］ Ａ∩［ｕｊ］ Ａ ＝ ⌀。 因此，∃ａ∈Ａ，不等式 ｆ （ ａ， ｕｉ）≠ｆ（ａ，ｕｊ）成立，故 ａ∈Ｍ ［α，β］ ｉｊ ，即 Ａ∩Ｍ ［α，β］ ｉｊ ≠⌀。 “⇐”：不妨假设∃（ｕｉ，ｕｊ）∈Ｄ ∗ ，使得 Ａ∩Ｍ ［α，β］ ｉｊ ＝ ⌀，显然 Υ ［α，β］ ＡＴ （ｕｉ）≠Υ ［α，β］ ＡＴ （ｕｊ ）。 ∀ａ∈Ａ，必然有 ａ∉ Ｍ ［α，β］ ｉｊ ，也即 ｆ （ａ，ｕｉ ） ＝ ｆ （ａ，ｕｊ ）。 故有［ｕｉ］Ａ ＝ ［ｕｊ］Ａ， ［ｕｉ］Ａ∩［ｕｊ］Ａ≠⌀，由定理 １ 可得 Ａ 不是广义分布协调 集。 定理得证。 定义 ５ 设 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ ），Ｍ ［α，β］ 为广 义分布保持约简的差别矩阵，其对应的差别函数为 ＤＦ（Ｍ ［α，β］ ） ＝∧ ｛∨ Ｍ ［α，β］ ｉｊ １ ≤ ｉ ≤ ｊ ≤ ｎ｝ 式中：∨Ｍ ［α，β］ ｉｊ ＝ ∨ａ（ ａ∈Ｍ ［α，β］ ｉｊ ）表示 Ｍ ［α，β］ ｉｊ 中所有 属性的析取，且 α 和 β 满足（α ＝ ０∧β∈［０，１］） 或 （α∈［０，１］∧β ＝ １）。 通过化 ＤＦ（Ｍ ［α，β］ ） 的主合取范式转化为主析 取范式即可得到所有广义分布保持属性约简。 定理 ３ 设 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ， ｆ），Ｍ ［α，β］为 ＤＴ 的广义分布保持约简的差别矩阵，且 α 和 β 满足 （α＝ ０∧β∈［ ０，１］） 或（ α∈［ ０，１］ ∧β ＝ １）。 ＤＦ （Ｍ ［α，β］ ）是由 Ｍ ［α，β］导出的差别函数，ＤＦ（Ｍ ［α，β］ ）的 极小析取范式为 ＤＦ（Ｍ ［α，β］ ） ＝∨ ｔ ｋ ＝ １ （∧ ｑｋ ｓ ＝ １ ａｉ ｓ ）。 记 Ａｋ ＝ ｛ ａｉ ｓ ｓ ＝ １，２，…，ｑｋ｝，则｛Ａｋ ｋ ＝ １，２，…， ｔ｝是决策表的所有广义分布保持约简，其中 ｔ 表示 ＤＦ（Ｍ ［α，β］ ）的极小析取范式中的合取项数目。 证明 ∀ｋ ≤ ｔ，∀Ｍ ［α，β］ ｉｊ ∈ Ｍ ［α，β］ ，由极小析取 范式的定义知 Ａｋ ∩ Ｍ ［α，β］ ｉｊ ≠ ⌀，再由定理 ２ 可得 Ａｋ 是广义分布协调集。 同时，ＤＦ（Ｍ ［α，β］ ） ＝∨ ｔ ｋ ＝ １ （Ａｋ）， 若在 Ａｋ 中 去 掉 任 意 一 个 属 性 形 成 Ａｋ ′， 则 必 然 ∃Ｍ ［α，β］ ｉｊ ∈ Ｍ ［α，β］ ，使得 Ａｋ ′ ∩ Ｍ ［α，β］ ｉｊ ＝ ⌀，故 Ａｋ ′ 不是 广义分布协调集，从而 Ａｋ 是广义分布保持约简。 由于 ＤＦ（Ｍ ［α，β］ ） 中包含了所有的 Ｍ ［α，β］ ｉｊ ，因此 不存在其他的广义分布保持约简，定理得证。 ３ 广义分布保持属性约简算法 本节给出广义分布保持约简算法（ｇｅｎｅｒａｌｉｚｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｐｒｅｓｅｒｖａｔｉｏｎ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ，ＧＤＰＲＡ）， 算法描述如下。 输入 决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ， ｆ ），α 和 β。 输出 ＤＴ 的所有广义分布保持属性约简。 １） 计算每个对象在条件属性集下关于决策属 性的置信度分布 μＡＴ 。 ２） 根据每个对象的置信度分布 μＡＴ获取每个对 象的［α，β］决策－置信度序偶集。 ３） 根据对象之间的决策－置信度序偶集构造相 应的广义分布差别矩阵。 第 ３ 期 高学义，等：广义分布保持属性约简研究 ·３７９·
·380. 智能系统学报 第12卷 4)根据广义分布差别矩阵构造广义分布差别 Y98.(1)={} 函数，并通过吸收率进行简化。 Y08,(u2)={ 5)在DF(Ma))基础上通过结合律获取所有 Y9.(u3)=⑦ 的广义分布保持约简。 Ya.(u4)=⑦ 其中，a和B满足(a=0∧B∈[0,1])或(a∈ 3)构造广义分布差别矩阵 [0,1]ΛB=1)。 [a,B]=[0,0.3]时对应的广义分布差别矩阵 由于上述算法是通过差别矩阵获取决策表的 如表2所示，[a,β]=[0.8,1]时对应的广义分布差 所有的广义分布保持约简，故算法在最坏情况下的 别矩阵如表3所示。 时间复杂度为O(|AT2),最坏情况下的空间复 表2广义分布差别矩阵1 杂度为O(|ATIU2),其中1U1为样本空间中的对 Table 2 Generalized distribution discernibility matrix 1 象数目，|AT为条件属性数，下面通过例1简要说 M[o.0.3] 明GDPRA的执行过程。 AT {a2} a2,a3}}a2,a3 例1如表1所示，论域为U={山1，山2，山3，u4}, {a2} AT {a3 {a3} AT={a1,a2,a3,a4}为条件属性集，D={d为决策属 u3 {a2,a3} {a3} AT AT 性，分别求[a,B]=[0,0.3]以及[a,B]=[0.8,1]时 的所有广义分布保持约简。 {a2,a3} {a3} AT AT 表1决策表 表3广义分布差别矩阵2 Table 1 Decision table Table 3 Generalized distribution discernibility matrix 2 a a Mlas.1] 41 2 AT 1 1 0 0 {a2} {a2,a3}{a2,a3} la2l AT {a3} {a3} 1 0 0 1 u3 {a2,a} 1a31 AT AT u3 1 0 2 {a2,a3}1a3} AT AT 1 0 4)获取差别函数并进行简化 1)获取每个对象的置信度分布 DF(Mo.aJ)=(a2)A(a3） U/AT={E1,E2,E3} DF(Ma8.)=(a2)A(a3) U/D={D1,D2,D3 5)通过结合律获取所有的广义分布保持约简 E,={u1} 由计算得，[a,B]=[0,0.3]时和[a,B]=[0.8, E2={u2} 1]时的所有广义分布保持约简均为{a2,a3}。 E3={u3,u4} D1=u1} 4一些特殊情形下的讨论 D2={u2,u4} 值得注意的是，给定决策表DT=(U,ATUD,V, D3={u3} ),当α和B取某些特殊值时，广义分布保持约简可 (41)=(1,0,0) 以退化为目前已存在的一些约简，本节将根据α和 u(42)=(0,1,0) B不同的特殊取值情况展开讨论，并给出相应的结 r(3)=(0,0.5,0.5) 论。其中，将MN、Mpos以及Ms分别记为广义决 r(44)=(0,0.5,0.5) 策可辨识矩阵、正域可辨识矩阵以及分布可辨识矩 2)获取每个对象的[α，B]决策-置信度序偶集 阵，同时，将M、M以及M分别记为对象山， 当a=0,B=0.3时 和”：对应在广义决策可辨识矩阵、正域可辨识矩阵 Y9a(41)={,} 以及分布可辨识矩阵的可辨识属性集，其中论域为 Y9aJ(2)={,} U={u1,山2，…，4n},i,je{1,2,…,n}。 Y00J(u3)={} 1)a=B=0时 Y0aJ(u4)={ 当α和B取值均为0时，广义分布保持约简实 当x=0.8,B=1时 质是保证对于置信度为0的规则在约简前后的置信
４） 根据广义分布差别矩阵构造广义分布差别 函数，并通过吸收率进行简化。 ５） 在 ＤＦ（Ｍ ［α，β］ ）基础上通过结合律获取所有 的广义分布保持约简。 其中，α 和 β 满足（α ＝ ０∧β∈［０，１］） 或（α∈ ［０，１］∧β ＝ １）。 由于上述算法是通过差别矩阵获取决策表的 所有的广义分布保持约简，故算法在最坏情况下的 时间复杂度为 Ｏ（ ＡＴ ｜ Ｕ｜ ２ ），最坏情况下的空间复 杂度为 Ｏ（ ＡＴ Ｕ ２ ），其中｜Ｕ ｜ 为样本空间中的对 象数目， ＡＴ 为条件属性数，下面通过例 １ 简要说 明 ＧＤＰＲＡ 的执行过程。 例 １ 如表 １ 所示，论域为 Ｕ ＝ ｛ｕ１ ，ｕ２ ，ｕ３ ，ｕ４ ｝， ＡＴ＝ ｛ａ１ ，ａ２ ，ａ３ ，ａ４ ｝为条件属性集，Ｄ＝ ｛ｄ｝为决策属 性，分别求［α，β］ ＝ ［０，０．３］以及［α，β］ ＝ ［０．８，１］时 的所有广义分布保持约简。 表 １ 决策表 Ｔａｂｌｅ １ Ｄｅｃｉｓｉｏｎ ｔａｂｌｅ Ｕ ａ１ ａ２ ａ３ ａ４ ｄ ｕ１ １ １ ０ １ ０ ｕ２ １ ０ ０ １ １ ｕ３ １ ０ １ １ ２ ｕ４ １ ０ １ １ １ １）获取每个对象的置信度分布 Ｕ／ ＡＴ ＝ ｛Ｅ１ ，Ｅ２ ，Ｅ３ ｝ Ｕ／ Ｄ＝ ｛Ｄ１ ，Ｄ２ ，Ｄ３ ｝ Ｅ１ ＝ ｛ｕ１ ｝ Ｅ２ ＝ ｛ｕ２ ｝ Ｅ３ ＝ ｛ｕ３ ，ｕ４ ｝ Ｄ１ ＝ ｛ｕ１ ｝ Ｄ２ ＝ ｛ｕ２ ，ｕ４ ｝ Ｄ３ ＝ ｛ｕ３ ｝ μＡＴ（ｕ１ ）＝ （１，０，０） μＡＴ（ｕ２ ）＝ （０，１，０） μＡＴ（ｕ３ ）＝ （０，０．５，０．５） μＡＴ（ｕ４ ）＝ （０，０．５，０．５） ２）获取每个对象的［α，β］决策－置信度序偶集 当 α＝ ０，β ＝ ０．３ 时 Υ ［０，０．３］ ＡＴ （ｕ１ ）＝ ｛＜１，０＞，＜２，０＞｝ Υ ［０，０．３］ ＡＴ （ｕ２ ）＝ ｛＜０，０＞，＜２，０＞｝ Υ ［０，０．３］ ＡＴ （ｕ３ ）＝ ｛＜０，０＞｝ Υ ［０，０．３］ ＡＴ （ｕ４ ）＝ ｛＜０，０＞｝ 当 α＝ ０．８，β ＝ １ 时 Υ ［０．８，１］ ＡＴ （ｕ１ ）＝ ｛＜０，１＞｝ Υ ［０．８，１］ ＡＴ （ｕ２ ）＝ ｛＜１，１＞｝ Υ ［０．８，１］ ＡＴ （ｕ３ ）＝ ⌀ Υ ［０．８，１］ ＡＴ （ｕ４ ）＝ ⌀ ３）构造广义分布差别矩阵 ［α，β］ ＝ ［０，０．３］ 时对应的广义分布差别矩阵 如表 ２ 所示，［α，β］ ＝ ［０．８，１］时对应的广义分布差 别矩阵如表 ３ 所示。 表 ２ 广义分布差别矩阵 １ Ｔａｂｌｅ ２ Ｇｅｎｅｒａｌｉｚｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ １ Ｍ ［０，０．３］ ｕ１ ｕ２ ｕ３ ｕ４ ｕ１ ＡＴ ｛ａ２ ｝ ｛ａ２ ，ａ３ ｝ ｛ａ２ ，ａ３ ｝ ｕ２ ｛ａ２ ｝ ＡＴ ｛ａ３ ｝ ｛ａ３ ｝ ｕ３ ｛ａ２ ，ａ３ ｝ ｛ａ３ ｝ ＡＴ ＡＴ ｕ４ ｛ａ２ ，ａ３ ｝ ｛ａ３ ｝ ＡＴ ＡＴ 表 ３ 广义分布差别矩阵 ２ Ｔａｂｌｅ ３ Ｇｅｎｅｒａｌｉｚｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ ２ Ｍ ［０．８，１］ ｕ１ ｕ２ ｕ３ ｕ４ ｕ１ ＡＴ ｛ａ２ ｝ ｛ａ２ ，ａ３ ｝ ｛ａ２ ，ａ３ ｝ ｕ２ ｛ａ２ ｝ ＡＴ ｛ａ３ ｝ ｛ａ３ ｝ ｕ３ ｛ａ２ ，ａ３ ｝ ｛ａ３ ｝ ＡＴ ＡＴ ｕ４ ｛ａ２ ，ａ３ ｝ ｛ａ３ ｝ ＡＴ ＡＴ ４）获取差别函数并进行简化 ＤＦ（Ｍ ［０，０．３］ ） ＝ （ａ２ ） ∧ （ａ３ ） ＤＦ（Ｍ ［０．８，１］ ） ＝ （ａ２ ） ∧ （ａ３ ） ５）通过结合律获取所有的广义分布保持约简 由计算得，［α，β］ ＝ ［０，０．３］时和［α，β］ ＝ ［０．８， １］时的所有广义分布保持约简均为｛ａ２ ，ａ３ ｝。 ４ 一些特殊情形下的讨论 值得注意的是，给定决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ， ｆ），当 α 和 β 取某些特殊值时，广义分布保持约简可 以退化为目前已存在的一些约简，本节将根据 α 和 β 不同的特殊取值情况展开讨论，并给出相应的结 论。 其中，将 ＭＧＥＮ、ＭＰＯＳ以及 ＭＤＩＳ分别记为广义决 策可辨识矩阵、正域可辨识矩阵以及分布可辨识矩 阵，同时，将 Ｍ ＧＥＮ ｉｊ 、Ｍ ＰＯＳ ｉｊ 以及 Ｍ ＤＩＳ ｉｊ 分别记为对象 ｕｉ 和 ｕｊ 对应在广义决策可辨识矩阵、正域可辨识矩阵 以及分布可辨识矩阵的可辨识属性集，其中论域为 Ｕ＝ ｛ｕ１ ，ｕ２ ，…，ｕｎ ｝，ｉ，ｊ∈｛１，２，…，ｎ｝。 １）α＝ β ＝ ０ 时 当 α 和 β 取值均为 ０ 时，广义分布保持约简实 质是保证对于置信度为 ０ 的规则在约简前后的置信 ·３８０· 智 能 系 统 学 报 第 １２ 卷
第3期 高学义，等：广义分布保持属性约简研究 .381· 度均为0，而对于置信度不为0的规则在约简前后 当Y(u)=Y(u)时，有Y(u)= 的置信度均不为0，由此可得如下结论。 Y(u)=☑或(u:)=Y(w)≠☑成立。 定理4设决策表DT=(U,ATUD,Vf),对于 对于前者，HDeU/D,使得[u:]Ar∩D:≠[u:]Ar成 VRCAT且R≠O,a=B=0,若R是决策表DT的一 立并且[u]灯∩D≠[山]Ar成立，故有 个广义分布保持约简，则R必定同时是决策表DT ,w∈BNDAT(D);对于后者，3D∈U/D,使 的一个广义决策保持约简。 ([:]r∩D=[u:]Ar)A([4]Ar∩D=[]Ar)成 证明不妨设u,山∈U,其中[山：]ar∩[4]r= 立，即f(:,d)=f(w,d),故由定义4可知Ms= O,同时设U/D={D,D2,…,Dwom}。若有Y90(u)≠ M=AT。 Yo(4)成立，则3D.∈U/D,其中ke{1,2,…, 综上，由于4：，山∈U,故在=B=1的条件下， |U/D},使得[u:]r∩Ds=☑A4]r∩D≠或 Ms=M.成立，故R是决策表DT的广义分布保 [u:]r∩D≠A[山]r∩Dk=☑成立，也即 持约简，则R必定同时是决策表DT的一个正域保 δr(u:)≠8r(u)成立，故由定义4可知有M0.o= 持约简，证毕。 M={a∈ATf(u:,a)≠f(4,a)}成立；反之，若 3)a=0,B=1时 Y9(u,)=Y9,0(4),则DeU/D,有[u:]rn 当α=0，B=1时，广义分布保持约简实质是保 D,≠☑A[w]a∩D≠☑或[u:]arnD= 证了置信度在[0,1]内的所有规则在约简前后的置 ☑A[4]r∩D=成立，故8Ar(u:)=δm(u),由定 信度不变，同时易得，此时对象的[，B]决策-置信 义4可知M.o1=M=AT成立。由于Hu,4,e 度序偶集等价于在决策等价类划分上的置信度分 U,故在a=B=0条件下，有Mcv=Mo,成立，故R 布，由此可得如下结论。 是决策表DT的一个广义分布保持约简，则R必定 定理6决策表DT=(U,ATUD,V,f),对于 同时是决策表DT的一个广义决策保持约简，证毕。 VRCAT且R≠☑，a=0且B=1,若R是决策表DT 2)a=B=1时 的一个广义分布保持约简，则R必定同时是决策表 显然，当=B=1时，广义分布保持约简实质是 DT的一个分布保持约简。 保证了置信度为1的规则在约简前后的置信度保持 证明不妨设V4,4,eU,其中[山：]rn[4,]Ar= 不变，由此可得如下结论。 ⑦，U/D={D1,D2,,D1n}:若Y0(u,)≠Y 定理5决策表DT=(U,ATUD,V,f),对于 (),则3D∈U/D,使得P(DI[u:]Ar)≠P(DI VRCAT且R≠☑，令a=B=1,若R是决策表DT []Ar),故有uT(:)≠uT(u)成立，所以由定义4 的一个广义分布保持约简，则R必定同时是决策表 可知Ms=Mo.={aEATlf:,a)≠f(4,a)};反 DT的一个正域保持约简。 之，若Y9(u,)=Y0(y)成立，则D∈U/D,有 证明不妨设Hu,4∈U,其中，[u:]rn P(D[u:]r)=P(D[,]r)成立，则由定义4可 [4,]Ar=,U/D=D,D2,…,D1wn,分情况进行 知M=M=AT;由于H4,4eU,故在a=0, 如下讨论。 B=1的条件下，有Ms=Mo,成立，故R是决策表 当Y(w）≠Y(u)成立时，有M.={a∈ DT的一个广义分布保持约简，必定同时是决策表 ATfu,a)≠f(y,a)}成立。假设Y(u,)≠0且 DT的一个分布保持约简，证毕。 Y(y)≠，则3D∈UWD,使得P(D.I[u:]r)= 综上，图1给出了广义分布保持约简与上述几 P(D[y]r)=1成立，故有u:,4∈POSr(D)且f(u, 种约简之间的关系。 d)≠f(4,d)成立，即M={a∈ATf(4,a)≠f(马， a=B=1 正域保持约简 a)}=M成立。若假设不成立，则有(u:EPOSAT(D)A L,∈BNDAT(D)或(4∈POSAT(D)A4:∈BNDAT a-0,1 “义分布保持约简 分布保持约简 (D)成立；若f(4,d)≠f,d)成立，则有M= 1 aEATIf(u,,a)≠f(4,a)=Mg.,若f(u,d)= a=B-0 广义决策保持约简 f(u,d),则有Mos=AT,同时必然4∈[u:]r,4∈ [4]r,使得f(u,d)≠f代u,d),故M={aeAT| 图1几种不同约简之间的关系 f,a)≠f4,a)}=M写.，故M=M写山。 Fig.1 Relationships among different reductions
度均为 ０，而对于置信度不为 ０ 的规则在约简前后 的置信度均不为 ０，由此可得如下结论。 定理 ４ 设决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ ），对于 ∀Ｒ⊆ＡＴ 且 Ｒ≠⌀，α＝ β ＝ ０，若 Ｒ 是决策表 ＤＴ 的一 个广义分布保持约简，则 Ｒ 必定同时是决策表 ＤＴ 的一个广义决策保持约简。 证明 不妨设∀ｕｉ，ｕｊ∈Ｕ，其中［ｕｉ］ＡＴ∩［ｕｊ］ＡＴ ＝ ⌀，同时设 Ｕ／ Ｄ＝｛Ｄ１，Ｄ２，…，Ｄ｜Ｕ／ Ｄ｜ ｝。 若有 Υ ［０，０］ ＡＴ （ｕｉ）≠ Υ ［０，０］ ＡＴ （ ｕｊ ） 成立，则∃Ｄｋ ∈Ｕ／ Ｄ，其中ｋ∈｛ １，２，…， Ｕ／ Ｄ ｝，使得［ｕｉ］ ＡＴ∩Ｄｋ ＝ ⌀∧［ｕｊ］ ＡＴ∩Ｄｋ≠⌀或 ［ｕｉ］ ＡＴ ∩ Ｄｋ ≠ ⌀ ∧ ［ｕｊ］ ＡＴ ∩ Ｄｋ ＝ ⌀ 成 立， 也 即 δＡＴ（ｕｉ）≠δＡＴ（ｕｊ）成立，故由定义 ４ 可知有 Ｍ ［０，０］ ｉｊ ＝ Ｍ ＧＥＮ ｉｊ ＝ ｛ａ∈ＡＴ ｆ（ ｕｉ，ａ） ≠ｆ（ ｕｊ，ａ）｝ 成立；反之，若 Υ ［０，０］ ＡＴ （ ｕｉ ） ＝ Υ ［０，０］ ＡＴ （ ｕｊ ），则∀Ｄｋ ∈Ｕ／ Ｄ，有［ｕｉ］ ＡＴ ∩ Ｄｋ≠ ⌀ ∧ ［ｕｊ］ ＡＴ ∩ Ｄｋ ≠ ⌀ 或 ［ｕｉ］ ＡＴ ∩ Ｄｋ ＝ ⌀∧［ｕｊ］ ＡＴ∩Ｄｋ ＝⌀成立，故 δＡＴ（ｕｉ）＝ δＡＴ（ｕｊ），由定 义 ４ 可知 Ｍ ［０，０］ ｉｊ ＝ Ｍ ＧＥＮ ｉｊ ＝ ＡＴ 成立。 由于∀ｕｉ，ｕｊ ∈ Ｕ，故在 α ＝ β ＝ ０ 条件下，有 ＭＧＥＮ ＝ Ｍ ［０，０］ 成立，故 Ｒ 是决策表 ＤＴ 的一个广义分布保持约简，则 Ｒ 必定 同时是决策表 ＤＴ 的一个广义决策保持约简，证毕。 ２）α＝ β ＝ １ 时 显然，当 α＝ β ＝ １ 时，广义分布保持约简实质是 保证了置信度为 １ 的规则在约简前后的置信度保持 不变，由此可得如下结论。 定理 ５ 决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ），对于 ∀Ｒ⊆ＡＴ 且 Ｒ≠⌀，令 α ＝ β ＝ １，若 Ｒ 是决策表 ＤＴ 的一个广义分布保持约简，则 Ｒ 必定同时是决策表 ＤＴ 的一个正域保持约简。 证明 不 妨 设 ∀ｕｉ， ｕｊ ∈ Ｕ， 其 中， ［ｕｉ］ ＡＴ ∩ ［ｕｊ］ ＡＴ ＝⌀，Ｕ／ Ｄ＝ ｛Ｄ１ ，Ｄ２ ，…，Ｄ Ｕ／ Ｄ ｝，分情况进行 如下讨论。 当 Υ ［１，１］ ＡＴ （ｕｉ）≠Υ ［１，１］ ＡＴ （ｕｊ）成立时，有 Ｍ ［１，１］ ｉｊ ＝ ｛ａ∈ ＡＴ ｆ（ｕｉ，ａ）≠ｆ（ｕｊ，ａ）｝成立。 假设 Υ ［１，１］ ＡＴ （ｕｉ）≠⌀ 且 Υ ［１，１］ ＡＴ （ｕｊ）≠⌀，则∃Ｄｋ∈Ｕ／ Ｄ，使得 Ｐ（Ｄｋ ［ｕｉ］ＡＴ ） ＝ Ｐ（Ｄｋ ［ｕｊ］ＡＴ）＝ １ 成立，故有 ｕｉ，ｕｊ∈ＰＯＳＡＴ（Ｄ）且 ｆ（ｕｉ， ｄ）≠ｆ（ｕｊ，ｄ）成立，即 Ｍ ＰＯＳ ｉｊ ＝ ｛ａ∈ＡＴ ｆ（ｕｉ，ａ）≠ｆ（ｕｊ， ａ）｝ ＝Ｍ ［１，１］ ｉｊ 成立。 若假设不成立，则有（ｕｉ∈ＰＯＳＡＴ（Ｄ）∧ ｕｊ∈ＢＮＤＡＴ （ Ｄ）） 或 （ ｕｊ ∈ ＰＯＳＡＴ （ Ｄ） ∧ ｕｉ ∈ ＢＮＤＡＴ （Ｄ））成立；若 ｆ（ ｕｉ，ｄ）≠ｆ（ｕｊ，ｄ）成立，则有 Ｍ ＰＯＳ ｉｊ ＝ ｛ａ∈ＡＴ ｆ（ｕｉ，ａ）≠ｆ（ｕｊ，ａ）｝ ＝ Ｍ ［１，１］ ｉｊ ，若 ｆ（ ｕｉ，ｄ） ＝ ｆ（ｕｊ，ｄ），则有 Ｍ ＰＯＳ ｉｊ ＝ＡＴ，同时必然∃ｕｉ′∈［ｕｉ］ＡＴ，ｕｊ′∈ ［ｕｊ］ ＡＴ ，使得ｆ（ｕｉ′，ｄ）≠ｆ（ｕｊ′，ｄ），故 Ｍ ＰＯＳ ｉ′ｊ′ ＝ ｛ ａ∈ＡＴ ｆ（ｕｉ′，ａ）≠ｆ（ｕｊ′，ａ）｝ ＝Ｍ ［１，１］ ｉｊ ，故 Ｍ ＰＯＳ ｉ′ｊ′ ＝Ｍ ［１，１］ ｉｊ 。 当 Υ ［１，１］ ＡＴ （ ｕｉ ） ＝ Υ ［１，１］ ＡＴ （ ｕｊ ） 时， 有 Υ ［１，１］ ＡＴ （ ｕｉ ） ＝ Υ ［１，１］ ＡＴ （ｕｊ）＝ ⌀ 或 Υ ［１，１］ ＡＴ （ ｕｉ） ＝ Υ ［１，１］ ＡＴ （ ｕｊ）≠⌀成立。 对于前者，∀Ｄｋ∈Ｕ／ Ｄ，使得［ｕｉ］ ＡＴ∩Ｄｋ≠［ｕｉ］ ＡＴ成 立 并 且 ［ｕｊ］ ＡＴ ∩ Ｄｋ ≠ ［ｕｊ］ ＡＴ 成 立， 故 有 ｕｉ，ｕｊ∈ＢＮＤＡＴ（Ｄ）； 对 于 后 者， ∃Ｄｋ ∈ Ｕ／ Ｄ， 使 （［ｕｉ］ ＡＴ∩Ｄｋ ＝ ［ｕｉ］ ＡＴ ） ∧（ ［ｕｊ］ ＡＴ ∩Ｄｋ ＝ ［ｕｊ］ ＡＴ ） 成 立，即 ｆ（ ｕｉ，ｄ） ＝ ｆ（ｕｊ，ｄ），故由定义 ４ 可知 Ｍ ＰＯＳ ｉｊ ＝ Ｍ ［１，１］ ｉｊ ＝ＡＴ。 综上，由于∀ｕｉ，ｕｊ∈Ｕ，故在 α＝ β ＝ １ 的条件下， ＭＰＯＳ ＝Ｍ ［１，１］成立，故 Ｒ 是决策表 ＤＴ 的广义分布保 持约简，则 Ｒ 必定同时是决策表 ＤＴ 的一个正域保 持约简，证毕。 ３） α＝ ０，β ＝ １ 时 当 α ＝ ０，β ＝ １ 时，广义分布保持约简实质是保 证了置信度在［０，１］内的所有规则在约简前后的置 信度不变，同时易得，此时对象的［α，β］决策－置信 度序偶集等价于在决策等价类划分上的置信度分 布，由此可得如下结论。 定理 ６ 决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ ），对于 ∀Ｒ⊆ＡＴ 且 Ｒ≠⌀，α＝ ０ 且 β ＝ １，若 Ｒ 是决策表 ＤＴ 的一个广义分布保持约简，则 Ｒ 必定同时是决策表 ＤＴ 的一个分布保持约简。 证明 不妨设∀ｕｉ，ｕｊ∈Ｕ，其中［ｕｉ］ＡＴ∩［ｕｊ］ＡＴ ＝ ⌀，Ｕ／ Ｄ＝ ｛Ｄ１ ，Ｄ２ ，…，Ｄ Ｕ／ Ｄ ｝；若 Υ ［０，１］ ＡＴ （ｕｉ）≠Υ ［０，１］ ＡＴ （ｕｊ ），则∃Ｄｋ ∈Ｕ／ Ｄ，使得 Ｐ（Ｄｋ ［ｕｉ］ ＡＴ ） ≠Ｐ（Ｄｋ ［ｕｊ］ ＡＴ ），故有 μＡＴ（ｕｉ）≠μＡＴ（ｕｊ）成立，所以由定义 ４ 可知 Ｍ ＤＩＳ ｉｊ ＝Ｍ ［０，１］ ｉｊ ＝ ｛ａ∈ＡＴ ｆ（ｕｉ，ａ）≠ｆ（ｕｊ，ａ）｝；反 之，若 Υ ［０，１］ ＡＴ （ｕｉ）＝ Υ ［０，１］ ＡＴ （ｕｊ）成立，则∀Ｄｋ∈Ｕ／ Ｄ，有 Ｐ（Ｄｋ ［ｕｉ］ ＡＴ ）＝ Ｐ（Ｄｋ ［ｕｊ］ ＡＴ ）成立，则由定义 ４ 可 知 Ｍ ＤＩＳ ｉｊ ＝ Ｍ ［０，１］ ｉｊ ＝ ＡＴ；由于∀ｕｉ，ｕｊ ∈Ｕ，故在 α ＝ ０， β ＝ １ 的条件下，有 ＭＤＩＳ ＝ Ｍ ［０，１］ 成立，故 Ｒ 是决策表 ＤＴ 的一个广义分布保持约简，必定同时是决策表 ＤＴ 的一个分布保持约简，证毕。 综上，图 １ 给出了广义分布保持约简与上述几 种约简之间的关系。 图 １ 几种不同约简之间的关系 Ｆｉｇ．１ Ｒｅｌａｔｉｏｎｓｈｉｐｓ ａｍｏｎｇ ｄｉｆｆｅｒｅｎｔ ｒｅｄｕｃｔｉｏｎｓ 第 ３ 期 高学义，等：广义分布保持属性约简研究 ·３８１·
.382. 智能系统学报 第12卷 例2表1所示决策表，论域U={u1,山2，u3, 一个广义分布保持约简，进一步，若给定置信度区 u4},AT={a1,a2,a3,a,}为条件属性集，D={d}为决 间[a',B],且满足[a',B]≤[a,B],则3A'≤A,使 策属性。由 得A'是置信度区间[α'，B]下的一个广义分布保持 U/AT={E1,E2,E3} 约简，且满足A'二A。其中，a和B满足(a=0∧B∈ E1={u1} [0,1])或(a∈[0,1]ΛB=1)。 E2={u2} 证明由已知条件得，[a',B]C[a,B],Hu∈ E2={山3，u4} U,有Ya剧(u)=Ya](u)。则u∈U,必然有 U/D={D1,D2,D3} Ye(u)=Yg(u),故A是决策表在置信度区 D1={u1} 间[α'，B]下的一个广义分布协调集。假设A是决 D2={42,u4} 策表在置信度区间[α'，B]下的一个广义分布约简， D3={u3} 则有A'CA:反之，必然3A'CA,使得Y0F](u)= POST(D)=u1,u2 Ya](u),故3A'CA,使得A'≤A成立，证毕。 8Ar(u1)={0} 5实验分析 8Ar(u2)={1} 8Ar(u3)={1,2 本节采用4个UCI数据集进行实验，数据集信 8Ar(u4)={1,2 息如表5所示，其中，|U川表示数据集的样本数， um(u1)=(1,0,0) |AT表示数据集的特征数，|D表示分类数。对于 uA(2)=(0,1,0) 数据集的预处理，处理策略如下：缺失特征值通过 r(u3)=(0,0.5,0.5) 用该缺失特征值所对应特征下的多数特征值进行 r(u4）=(0,0.5,0.5) 填充，连续型特征进行等频离散化，名词性特征值 求得正域保持约简为a2,a3},广义决策保持约 用整数进行替换，所有数据集的预处理均在Weka 简为{a2,a3},分布保持约简为{a2,a3}。 3.6下进行。实验环境如下：Windows7旗舰版32位 因此，当a=B=1时，可得：Y(1)={(0,1)}, 操作系统，intel Pentium G640C处理器，主频 Y(42）={(1,1)},Y(4）=⑦， 2.8GHz,内存6.0GB,所有算法均采用MATLAB Y(u)=0。 R2010h编写实现。 据此构造广义分布差别矩阵，如表4所示。 表5UCI数据集信息 表4广义分布差别矩阵 Table 5 Information of UCI data sets Table 4 Generalized distribution discernibility matrix 数据集 IUI ATI DI Mu. 42 Haberman's Survival 306 3 2 AT {a2} {a2,a3 {a2,a3 Blood Transfusion Service Center 748 2 {a2} AT {a3} {a3} Stone Flakes 79 3 us {a2,a3} {a3} AT AT Airfoil Self-Noise 1503 5 16 4 {a2,a3} {a} AT AT 注：BTSC为数据集Blood Transfusion Service Center的 由广义分布差别矩阵可得所有的广义分布保 缩写 持约简为{a2,a3},与正域约简一致。同理，a=B=0 实验分为两部分。第1部分验证置信度区间分 时的广义分布保持约简为a2,a3},与广义决策约简 别为[1.0,1.0]、[0.0,0.0]以及[0.0,1.0]时，广义分 一致；a=0,B=1时的广义分布保持约简为{a2, 布保持约简可分别退化为正域保持约简、广义决策 a3},与分布约简一致。 保持约简以及分布约简，同时，也可验证广义分布 由定理4~6可得如下结论。 保持约简算法的正确性：第2部分验证在较小的置 推论1设DT=(U,ATUD,V,f),置信度区间 信度区间下求得的广义分布保持约简是在较大的 为[a,B],VACAT,且A是置信度区间[a,B]下的 置信度区间下求得的广义分布保持约简的子集
例 ２ 表 １ 所示决策表，论域 Ｕ ＝ ｛ ｕ１ ，ｕ２ ，ｕ３ ， ｕ４ ｝，ＡＴ ＝ ｛ａ１ ，ａ２ ，ａ３ ，ａ４ ｝为条件属性集，Ｄ＝ ｛ｄ｝为决 策属性。 由 Ｕ／ ＡＴ ＝ ｛Ｅ１ ，Ｅ２ ，Ｅ３ ｝ Ｅ１ ＝ ｛ｕ１ ｝ Ｅ２ ＝ ｛ｕ２ ｝ Ｅ２ ＝ ｛ｕ３ ，ｕ４ ｝ Ｕ／ Ｄ＝ ｛Ｄ１ ，Ｄ２ ，Ｄ３ ｝ Ｄ１ ＝ ｛ｕ１ ｝ Ｄ２ ＝ ｛ｕ２ ，ｕ４ ｝ Ｄ３ ＝ ｛ｕ３ ｝ ＰＯＳＡＴ（Ｄ）＝ ｛ｕ１ ，ｕ２ ｝ δＡＴ（ｕ１ ）＝ ｛０｝ δＡＴ（ｕ２ ）＝ ｛１｝ δＡＴ（ｕ３ ）＝ ｛１，２｝ δＡＴ（ｕ４ ）＝ ｛１，２｝ μＡＴ（ｕ１ ）＝ （１，０，０） μＡＴ（ｕ２ ）＝ （０，１，０） μＡＴ（ｕ３ ）＝ （０，０．５，０．５） μＡＴ（ｕ４ ）＝ （０，０．５，０．５） 求得正域保持约简为｛ａ２ ，ａ３ ｝，广义决策保持约 简为｛ａ２ ，ａ３ ｝，分布保持约简为｛ａ２ ，ａ３ ｝。 因此，当 α＝β ＝ １ 时，可得：Υ ［１，１］ ＡＴ （ｕ１ ）＝ ｛〈０，１〉｝， Υ ［１，１］ ＡＴ （ ｕ２ ） ＝ ｛〈 １， １ 〉｝， Υ ［１，１］ ＡＴ （ ｕ３ ） ＝ ⌀， Υ ［１，１］ ＡＴ （ｕ４ ）＝ ⌀。 据此构造广义分布差别矩阵，如表 ４ 所示。 表 ４ 广义分布差别矩阵 Ｔａｂｌｅ ４ Ｇｅｎｅｒａｌｉｚｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ Ｍ ［１，１］ ｕ１ ｕ２ ｕ３ ｕ４ ｕ１ ＡＴ ｛ａ２ ｝ ｛ａ２ ，ａ３ ｝ ｛ａ２ ，ａ３ ｝ ｕ２ ｛ａ２ ｝ ＡＴ ｛ａ３ ｝ ｛ａ３ ｝ ｕ３ ｛ａ２ ，ａ３ ｝ ｛ａ３ ｝ ＡＴ ＡＴ ｕ４ ｛ａ２ ，ａ３ ｝ ｛ａ３ ｝ ＡＴ ＡＴ 由广义分布差别矩阵可得所有的广义分布保 持约简为｛ａ２ ，ａ３ ｝，与正域约简一致。 同理，α ＝ β ＝ ０ 时的广义分布保持约简为｛ａ２ ，ａ３ ｝，与广义决策约简 一致；α ＝ ０， β ＝ １ 时的广义分布保持约简为｛ ａ２ ， ａ３ ｝，与分布约简一致。 由定理 ４～６ 可得如下结论。 推论 １ 设 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ ），置信度区间 为［α，β］，∀Ａ⊆ＡＴ，且 Ａ 是置信度区间［α，β］下的 一个广义分布保持约简，进一步，若给定置信度区 间［α′，β′］，且满足［α′，β′］⊆［α，β］，则∃Ａ′⊆Ａ，使 得 Ａ′是置信度区间［α′，β′］下的一个广义分布保持 约简，且满足 Ａ′⊆Ａ。 其中，α 和 β 满足（α ＝ ０∧β∈ ［０，１］）或（α∈［０，１］∧β ＝ １）。 证明 由已知条件得，［α′，β′］⊆［α，β］，∀ｕ∈ Ｕ，有 Υ ［α，β］ Ａ （ ｕ） ＝ Υ ［α，β］ ＡＴ （ ｕ）。 则 ∀ｕ ∈ Ｕ， 必然有 Υ ［α′，β′］ Ａ （ｕ）＝ Υ ［α′，β′］ ＡＴ （ ｕ），故 Ａ 是决策表在置信度区 间［α′，β′］下的一个广义分布协调集。 假设 Ａ 是决 策表在置信度区间［α′，β′］下的一个广义分布约简， 则有 Ａ′⊆Ａ；反之，必然∃Ａ′⊂Ａ，使得 Υ ［α′，β′］ Ａ′ （ ｕ） ＝ Υ ［α′，β′］ Ａ （ｕ），故∃Ａ′⊆Ａ，使得 Ａ′⊆Ａ 成立，证毕。 ５ 实验分析 本节采用 ４ 个 ＵＣＩ 数据集进行实验，数据集信 息如表 ５ 所示，其中， Ｕ 表示数据集的样本数， ＡＴ 表示数据集的特征数， Ｄ 表示分类数。 对于 数据集的预处理，处理策略如下：缺失特征值通过 用该缺失特征值所对应特征下的多数特征值进行 填充，连续型特征进行等频离散化，名词性特征值 用整数进行替换，所有数据集的预处理均在 Ｗｅｋａ ３．６下进行。 实验环境如下：Ｗｉｎｄｏｗｓ ７ 旗舰版 ３２ 位 操 作 系 统， Ｉｎｔｅｌ Ｐｅｎｔｉｕｍ Ｇ６４０Ｃ 处 理 器， 主 频 ２．８ ＧＨｚ，内 存 ６．０ ＧＢ， 所 有 算 法 均 采 用 ＭＡＴＬＡＢ Ｒ２０１０ｂ 编写实现。 表 ５ ＵＣＩ 数据集信息 Ｔａｂｌｅ ５ Ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ＵＣＩ ｄａｔａ ｓｅｔｓ 数据集 Ｕ ＡＴ Ｄ Ｈａｂｅｒｍａｎ’ｓ Ｓｕｒｖｉｖａｌ ３０６ ３ ２ Ｂｌｏｏｄ Ｔｒａｎｓｆｕｓｉｏｎ Ｓｅｒｖｉｃｅ Ｃｅｎｔｅｒ ７４８ ４ ２ Ｓｔｏｎｅ Ｆｌａｋｅｓ ７９ ７ ３ Ａｉｒｆｏｉｌ Ｓｅｌｆ⁃Ｎｏｉｓｅ １５０３ ５ １６ 注：ＢＴＳＣ 为数据集 Ｂｌｏｏｄ Ｔｒａｎｓｆｕｓｉｏｎ Ｓｅｒｖｉｃｅ Ｃｅｎｔｅｒ 的 缩写 实验分为两部分。 第 １ 部分验证置信度区间分 别为［１．０，１．０］、［０．０，０．０］以及［０．０，１．０］时，广义分 布保持约简可分别退化为正域保持约简、广义决策 保持约简以及分布约简，同时，也可验证广义分布 保持约简算法的正确性；第 ２ 部分验证在较小的置 信度区间下求得的广义分布保持约简是在较大的 置信度区间下求得的广义分布保持约简的子集。 ·３８２· 智 能 系 统 学 报 第 １２ 卷
第3期 高学义，等：广义分布保持属性约简研究 ·383. 5.1广义分布保持属性约简的退化情形 5.2不同置信度区间下约简的包含关系 本节中，分别令[a,B]取值为[1.0,1.0]、[0.0 本部分实验设置如下：首先，固定α的值为0.0， 0.0]和[0.0,1.0]，并求4个UCI数据集的广义分布 令B取值范围为0.0-1.0，取值间隔为0.2，记录随B 保持约简，然后，分别求它们在正域保持约简算法 取值的变化在不同置信度区间下求得的广义分布 positive region preservation reduction algorithm, 保持约简。同样的，固定B的值为1.0，令α取值范 PRPRA),广义决策保持约简算法(algorithm of 围为0.0~1.0，取值间隔为0.2，记录随a取值的变 generalized decision preservation reduction,AGDPR) 化在不同置信度区间下求得的广义分布保持约简， 以及分布保持约简算法(distribution preservation 实验结果如表9~12所示。 reduction algorithm,DPRA)下的约简，通过前后对 表9数据集1：Haberman's survival 比，验证广义分布保持约简在3个特殊置信度区间 Table 9 Data set 1:Haberman's survival 下的退化情况，实验结果如表6~8所示。 [a,β] 约简 [a,B] 约简 表6 GDPRA和PRPRA的约简结果([a&,B]=[1,1]) Table 6 Reduction results for GDPRA and PRPRA [0.0.0.0] 12,3 [0.0.1.0] {1.2,3} ([xB]=[1,1]) [0.0.0.2] 11,2,3 [0.2.1.0] {1.2,3} 数据集 GDPRA PRPRA [0.0,0.4] 11,2,3 [0.4.1.0] {1.2,3} Haberman's Survival 12,3} {2,3 [0.0.0.6] 11.2.3} [0.6,1.0] {1.2,3} BTSC {1,49 11,4 [0.0.0.8] {1.2.3 [0.8.1.0] {1.2,3} Stone Flakes {2,6,7} {2,6,71 Airfoil Self-Noise {1,2.3.4}11.2.3,41 [0.0.1.0] 11,2,3 [1.0.1.0] {2,3} 表7 GDPRA和GDECPRA的约简结果([&，B]=[0,O]) 表10 数据集2：blood transfusion service center Table 7 Reduction results for GDPRA and GDECPRA Table 10 Data set 2:blood transfusion service center ([a,B]=[0,0]) [a,β] 约简 [a,β] 约简 数据集 GDPRA GDECPRA [0.0.0.0] {1,4 0.0.1.0]{1,2,4},11,3,4 Haberman's Survival {2,3 12,3 [0.0,02]{1,2.4},{1.3,4} [0.2.1.0]{1.2.4},{1.3.4} BTSC 11,4 {1,4} [0.0.0.4]}1,2.4},{1.3,4} [0.4.1.0] 11.2.4},13.4 Stone Flakes {2,3,4,5,6,7}{2,3,4,5,6,7 「0.0.0.61{1,2.4，{1.3.480.6.1.0111,2.4}，{1.3.4} Airfoil Self-Noise {1.2,3.4.5} {1.2,3.4.5} 表8 GDPRA和DPRA的约简结果([，B]=[0,1]) 「0.0.0.811,2.4，{1.3,4}[0.8,1.01 112.4},13.4 Table 8 Reduction results for GDPRA and DPRA [0.0.1.0]{1,2.4}.{1.3,4} [1.0.1.0] 11,4} ([w,B]=[0,1]) 表11 数据集3：stone flakes 数据集 GDPRA DPRA Table 11 Data set 3:stone flakes Haberman's Survival {1,2,3} {1,2.3} [a,β] 约简 [a,B] 约简 BTSC {1.2.4},1.3.4}{1.2.4},{1,3.4 [0.0.0.0] {2,3.4.5.6.7} [0.0.1.0] {2.3,4.56.7} Stone Flakes {2,3,4,5,6,7} {2,3,4,5,6,7 [0.0,0.2] {2,3,4,5,6,7 「0.2.1.01 12,3,4,5,6,7 Airfoil Self-Noise {1.2.3,4.5} {1.2.3,4.5 「0.0.0.41{2,3,4.5.6.7 [0.4,1.0] {2.3,4,5,6.71 当[a,B]分别为[1.0,1.0]、[0.0,0.0]以及 [0.0,0.6]{2,3,4,5.6,7 [0.6.1.0] {2,3.4,5.6.7} [O.O,1.0]时，GDPRA的约简结果分别同PRPRA AGDPR以及DPRA的约简结果一致，验证了相关结 [0.0,0.8]{2,3,4,5.6.7} [0.8,1.0] {2,4,5,6,7} 论的正确性。 [0.0,1.0]{2,3,4,5,6,7 1.0.1.0] {2.6.7
５．１ 广义分布保持属性约简的退化情形 本节中，分别令［α，β］取值为［１．０，１．０］、［０．０， ０．０］和［０．０，１．０］，并求 ４ 个 ＵＣＩ 数据集的广义分布 保持约简，然后，分别求它们在正域保持约简算法 （ ｐｏｓｉｔｉｖｅ ｒｅｇｉｏｎ ｐｒｅｓｅｒｖａｔｉｏｎ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ， ＰＲＰＲＡ）， 广 义 决 策 保 持 约 简 算 法 （ ａｌｇｏｒｉｔｈｍ ｏｆ ｇｅｎｅｒａｌｉｚｅｄ ｄｅｃｉｓｉｏｎ ｐｒｅｓｅｒｖａｔｉｏｎ ｒｅｄｕｃｔｉｏｎ， ＡＧＤＰＲ） 以及 分 布 保 持 约 简 算 法 （ ｄｉｓｔｒｉｂｕｔｉｏｎ ｐｒｅｓｅｒｖａｔｉｏｎ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ，ＤＰＲＡ） 下的约简，通过前后对 比，验证广义分布保持约简在 ３ 个特殊置信度区间 下的退化情况，实验结果如表 ６～８ 所示。 表 ６ ＧＤＰＲＡ 和 ＰＲＰＲＡ 的约简结果（［α，β］ ＝［１，１］） Ｔａｂｌｅ ６ Ｒｅｄｕｃｔｉｏｎ ｒｅｓｕｌｔｓ ｆｏｒ ＧＤＰＲＡ ａｎｄ ＰＲＰＲＡ （［α，β］ ＝［１，１］） 数据集 ＧＤＰＲＡ ＰＲＰＲＡ Ｈａｂｅｒｍａｎ’ｓ Ｓｕｒｖｉｖａｌ ｛２，３｝ ｛２，３｝ ＢＴＳＣ ｛１，４｝ ｛１，４｝ Ｓｔｏｎｅ Ｆｌａｋｅｓ ｛２，６，７｝ ｛２，６，７｝ Ａｉｒｆｏｉｌ Ｓｅｌｆ－Ｎｏｉｓｅ ｛１，２，３，４｝ ｛１，２，３，４｝ 表 ７ ＧＤＰＲＡ 和 ＧＤＥＣＰＲＡ 的约简结果（［α，β］ ＝［０，０］） Ｔａｂｌｅ ７ Ｒｅｄｕｃｔｉｏｎ ｒｅｓｕｌｔｓ ｆｏｒ ＧＤＰＲＡ ａｎｄ ＧＤＥＣＰＲＡ （［α，β］ ＝［０，０］） 数据集 ＧＤＰＲＡ ＧＤＥＣＰＲＡ Ｈａｂｅｒｍａｎ’ｓ Ｓｕｒｖｉｖａｌ ｛２，３｝ ｛２，３｝ ＢＴＳＣ ｛１，４｝ ｛１，４｝ Ｓｔｏｎｅ Ｆｌａｋｅｓ ｛２，３，４，５，６，７｝ ｛２，３，４，５，６，７｝ Ａｉｒｆｏｉｌ Ｓｅｌｆ－Ｎｏｉｓｅ ｛１，２，３，４，５｝ ｛１，２，３，４，５｝ 表 ８ ＧＤＰＲＡ 和 ＤＰＲＡ 的约简结果（［α，β］ ＝［０，１］） Ｔａｂｌｅ ８ Ｒｅｄｕｃｔｉｏｎ ｒｅｓｕｌｔｓ ｆｏｒ ＧＤＰＲＡ ａｎｄ ＤＰＲＡ （［α，β］ ＝［０，１］） 数据集 ＧＤＰＲＡ ＤＰＲＡ Ｈａｂｅｒｍａｎ’ｓ Ｓｕｒｖｉｖａｌ ｛１，２，３｝ ｛１，２，３｝ ＢＴＳＣ ｛１，２，４｝，｛１，３，４｝ ｛１，２，４｝，｛１，３，４｝ Ｓｔｏｎｅ Ｆｌａｋｅｓ ｛２，３，４，５，６，７｝ ｛２，３，４，５，６，７｝ Ａｉｒｆｏｉｌ Ｓｅｌｆ－Ｎｏｉｓｅ ｛１，２，３，４，５｝ ｛１，２，３，４，５｝ 当［ α，β］ 分别为［ １． ０，１． ０］、 ［ ０． ０，０． ０］ 以及 ［０．０，１．０］ 时，ＧＤＰＲＡ 的约简结果分别同 ＰＲＰＲＡ、 ＡＧＤＰＲ 以及 ＤＰＲＡ 的约简结果一致，验证了相关结 论的正确性。 ５．２ 不同置信度区间下约简的包含关系 本部分实验设置如下：首先，固定 α 的值为０．０， 令 β 取值范围为 ０．０～１．０，取值间隔为 ０．２，记录随 β 取值的变化在不同置信度区间下求得的广义分布 保持约简。 同样的，固定 β 的值为 １．０，令 α 取值范 围为 ０．０～１．０，取值间隔为 ０．２，记录随 α 取值的变 化在不同置信度区间下求得的广义分布保持约简， 实验结果如表 ９～１２ 所示。 表 ９ 数据集 １：Ｈａｂｅｒｍａｎ’ｓ ｓｕｒｖｉｖａｌ Ｔａｂｌｅ ９ Ｄａｔａ ｓｅｔ １：Ｈａｂｅｒｍａｎ’ｓ ｓｕｒｖｉｖａｌ ［α，β］ 约简 ［α，β］ 约简 ［０．０，０．０］ ｛２，３｝ ［０．０，１．０］ ｛１，２，３｝ ［０．０，０．２］ ｛１，２，３｝ ［０．２，１．０］ ｛１，２，３｝ ［０．０，０．４］ ｛１，２，３｝ ［０．４， １．０］ ｛１，２，３｝ ［０．０，０．６］ ｛１，２，３｝ ［０．６， １．０］ ｛１，２，３｝ ［０．０，０．８］ ｛１，２，３｝ ［０．８， １．０］ ｛１，２，３｝ ［０．０，１．０］ ｛１，２，３｝ ［１．０， １．０］ ｛２，３｝ 表 １０ 数据集 ２：ｂｌｏｏｄ ｔｒａｎｓｆｕｓｉｏｎ ｓｅｒｖｉｃｅ ｃｅｎｔｅｒ Ｔａｂｌｅ １０ Ｄａｔａ ｓｅｔ ２：ｂｌｏｏｄ ｔｒａｎｓｆｕｓｉｏｎ ｓｅｒｖｉｃｅ ｃｅｎｔｅｒ ［α，β］ 约简 ［α，β］ 约简 ［０．０，０．０］ ｛１，４｝ ［０．０，１．０］ ｛１，２，４｝，｛１，３，４｝ ［０．０，０．２］ ｛１，２，４｝，｛１，３，４｝ ［０．２，１．０］ ｛１，２，４｝，｛１，３，４｝ ［０．０，０．４］ ｛１，２，４｝，｛１，３，４｝ ［０．４，１．０］ ｛１，２，４｝，｛１，３，４｝ ［０．０，０．６］ ｛１，２，４｝，｛１，３，４｝ ［０．６，１．０］ ｛１，２，４｝，｛１，３，４｝ ［０．０，０．８］ ｛１，２，４｝，｛１，３，４｝ ［０．８，１．０］ ｛１，２，４｝，｛１，３，４｝ ［０．０，１．０］ ｛１，２，４｝，｛１，３，４｝ ［１．０，１．０］ ｛１，４｝ 表 １１ 数据集 ３：ｓｔｏｎｅ ｆｌａｋｅｓ Ｔａｂｌｅ １１ Ｄａｔａ ｓｅｔ ３：ｓｔｏｎｅ ｆｌａｋｅｓ ［α，β］ 约简 ［α，β］ 约简 ［０．０，０．０］ ｛２，３，４，５，６，７｝ ［０．０，１．０］ ｛２，３，４，５，６，７｝ ［０．０，０．２］ ｛２，３，４，５，６，７｝ ［０．２，１．０］ ｛２，３，４，５，６，７｝ ［０．０，０．４］ ｛２，３，４，５，６，７｝ ［０．４，１．０］ ｛２，３，４，５，６，７｝ ［０．０，０．６］ ｛２，３，４，５，６，７｝ ［０．６，１．０］ ｛２，３，４，５，６，７｝ ［０．０，０．８］ ｛２，３，４，５，６，７｝ ［０．８，１．０］ ｛２，４，５，６，７｝ ［０．０，１．０］ ｛２，３，４，５，６，７｝ ［１．０，１．０］ ｛２，６，７｝ 第 ３ 期 高学义，等：广义分布保持属性约简研究 ·３８３·
·384. 智能系统学报 第12卷 表12数据集4：airfoil self-.noise computers,2009,32(7):1229-1246 Table 12 Data set 4:airfoil self-noise [5]SKOWRON A,RAUSZER C.The discernibility matrices [a,B] 约简 [a,B] 约简 and functions in information systems[.Theory and decision [0.0.0.0] {1,2.3.4.5} [0.0.1.0] {1,2,3,4.5} 1 library,1992,11:331-362. [6]KRYSZKIEWICZ M.Rough set approach to incomplete [0.0,0.2] 11,2,3,4,5 [0.2.1.0] 11,2,3,4,5 information systems[J].Information sciences,1998,112 [0.0.0.4] {1.2.3.4,5} [0.4.1.0] 11.2.3.4.5} (1/2/3/4)：39-49. [0.0,0.6] {1,2,3,4,5 [0.6,1.01 11,2,3,4 [7]张文修，米据生，吴伟志.不协调目标信息系统的知识 [0.0,0.8] {1,2,3,4,5} 「0.8.1.01 {1,2,3,41 约简[J].计算机学报，2003,26(1)：12-18. [0.0,1.0] {1,2,3,4,5 [1.0,1.0] 11,2,3,4} ZHANG Wenxiu,MI Jusheng,WU Weizhi.Knowledge reductions in inconsistent information systems[J].Chinese 6 结束语 journal of computers,2003,26(1):12-18. 实际中，具有较高或较低置信度的规则往往更 [8]徐伟华，张文修.基于优势关系下不协调目标信息系统 易受到人们的关注，若通过分布约简进行规则提 的分布约简[J].模糊系统与数学，2007,21(4)： 124-131. 取，提取的规则可能过于冗长，不便于实际决策。 XU Weihua,ZHANG Wenxiu.Distribution reduction in 因此，本文对分布约简的约简标准进行弱化，提出 inconsistent information systems based on dominance 了广义分布保持约简的概念。理论与实验分析表 relations[J].Fuzzy systems and mathematics,2007,21 明，当置信度区间取某些特殊值时，广义分布保持 (4):124-131. 属性约简可退化为现有的一些属性约简，表明了广 [9]MIAO Duoqian,ZHAO Yan,YAO Yiyu,et al.Relative 义分布保持属性约简具有一定的泛化性能，同时为 reducts in consistent and inconsistent decision tables of the 深入研究不同属性约简之间的相互关系开阔了研 Pawlak rough set model[J].Information sciences,2009, 究思路。实验数据表明，广义分布保持属性约简较 179(24):4140-4150. 分布约简可以获取更加简短的规则，且根据实际需 [10]张楠，苗夺谦，岳晓冬.区间值信息系统的知识约简 要可以调整置信度区间以获取所需规则，使得广义 [J].计算机研究与发展，2010,47(8)：1362-1371. 分布保持属性约简可以适应不同的实际需求。但 ZHANG Nan,MIAO Duoqian,YUE Xiaodong. 考虑到本文提出的算法主要是通过差别矩阵获取 Approaches to knowledge reduction in interval-valued information systems[J].Journal of computer research and 所有的广义分布保持属性约简，其时间和空间复杂 development,2010,47(8):1362-1371. 度较高，不便于在实际应用中推广，具有一定的局 [11]苗夺谦，胡桂荣.知识约简的一种启发式算法[J].计 限性，故开发更为高效的广义分布保持属性约简算 算机研究与发展，1999,36(6)：681-684 法是未来主要的研究工作之一。 MIAO Duoqian,HU Guirong.A heuristic algorithm for 参考文献： reduction of knowledge[J].Journal of computer research and development,1999,36(6):681-684. [1]PAWLAK Z.Rough sets[J].International journal of com- [12]王国胤，于洪，杨大春.基于条件信息嫡的决策表约简 puter and information sciences,1982,11(5):341-356. [J].计算机学报，2002,25(7)：759-766， [2]PAWLAK Z.Rough sets:theoretical aspects of reasoning about WANG Guoyin,YU Hong,YANG Dachun.Decision table data[M].Boston:Kluwer Academic Publishers,1992. reduction based on conditional information entropy[J]. [3]张文修.粗糙集理论与方法[M].北京：科学出版 Chinese journal of computers,2002,25(7):759-766. 社，2001. [13]QIAN Yuhua,LIANG Jiye,PEDRYCZ W,et al.Positive [4]王国胤，姚一豫，于洪.粗糙集理论与应用研究综述 approximation:an accelerator for attribute reduction in [J].计算机学报，2009,32(7)：1229-1246. rough set theory J].Artificial intelligence,2010,174 WANG Guoyin,YAO Yiyu,YU Hong.A survey on rough (9):597-618 set theory and applications J].Chinese journal of [14]QIAN Yuhua,LIANG Jiye,PEDRYCZ W,et al.An
表 １２ 数据集 ４：ａｉｒｆｏｉｌ ｓｅｌｆ⁃ｎｏｉｓｅ Ｔａｂｌｅ １２ Ｄａｔａ ｓｅｔ ４： ａｉｒｆｏｉｌ ｓｅｌｆ⁃ｎｏｉｓｅ ［α，β］ 约简 ［α，β］ 约简 ［０．０，０．０］ ｛１，２，３，４，５｝ ［０．０，１．０］ ｛１，２，３，４，５｝ ［０．０，０．２］ ｛１，２，３，４，５｝ ［０．２，１．０］ ｛１，２，３，４，５｝ ［０．０，０．４］ ｛１，２，３，４，５｝ ［０．４，１．０］ ｛１，２，３，４，５｝ ［０．０，０．６］ ｛１，２，３，４，５｝ ［０．６，１．０］ ｛１，２，３，４｝ ［０．０，０．８］ ｛１，２，３，４，５｝ ［０．８，１．０］ ｛１，２，３，４｝ ［０．０，１．０］ ｛１，２，３，４，５｝ ［１．０，１．０］ ｛１，２，３，４｝ ６ 结束语 实际中，具有较高或较低置信度的规则往往更 易受到人们的关注，若通过分布约简进行规则提 取，提取的规则可能过于冗长，不便于实际决策。 因此，本文对分布约简的约简标准进行弱化，提出 了广义分布保持约简的概念。 理论与实验分析表 明，当置信度区间取某些特殊值时，广义分布保持 属性约简可退化为现有的一些属性约简，表明了广 义分布保持属性约简具有一定的泛化性能，同时为 深入研究不同属性约简之间的相互关系开阔了研 究思路。 实验数据表明，广义分布保持属性约简较 分布约简可以获取更加简短的规则，且根据实际需 要可以调整置信度区间以获取所需规则，使得广义 分布保持属性约简可以适应不同的实际需求。 但 考虑到本文提出的算法主要是通过差别矩阵获取 所有的广义分布保持属性约简，其时间和空间复杂 度较高，不便于在实际应用中推广，具有一定的局 限性，故开发更为高效的广义分布保持属性约简算 法是未来主要的研究工作之一。 参考文献： ［１］ＰＡＷＬＡＫ Ｚ． Ｒｏｕｇｈ ｓｅｔｓ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｃｏｍ⁃ ｐｕｔｅｒ ａｎｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， １９８２， １１（５）： ３４１－３５６． ［２］ＰＡＷＬＡＫ Ｚ． Ｒｏｕｇｈ ｓｅｔｓ： ｔｈｅｏｒｅｔｉｃａｌ ａｓｐｅｃｔｓ ｏｆ ｒｅａｓｏｎｉｎｇ ａｂｏｕｔ ｄａｔａ［Ｍ］． Ｂｏｓｔｏｎ：Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ Ｐｕｂｌｉｓｈｅｒｓ， １９９２． ［３］ 张 文 修． 粗 糙 集 理 论 与 方 法 ［ Ｍ］． 北 京： 科 学 出 版 社， ２００１． ［４］王国胤， 姚一豫， 于洪． 粗糙集理论与应用研究综述 ［Ｊ］． 计算机学报， ２００９， ３２（７）： １２２９－１２４６． ＷＡＮＧ Ｇｕｏｙｉｎ， ＹＡＯ Ｙｉｙｕ， ＹＵ Ｈｏｎｇ． Ａ ｓｕｒｖｅｙ ｏｎ ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ ［ Ｊ ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２００９， ３２（７）： １２２９－１２４６． ［５］ ＳＫＯＷＲＯＮ Ａ， ＲＡＵＳＺＥＲ Ｃ． Ｔｈｅ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｃｅｓ ａｎｄ ｆｕｎｃｔｉｏｎｓ ｉｎ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ［Ｊ］． Ｔｈｅｏｒｙ ａｎｄ ｄｅｃｉｓｉｏｎ ｌｉｂｒａｒｙ， １９９２， １１： ３３１－３６２． ［６ ］ ＫＲＹＳＺＫＩＥＷＩＣＺ Ｍ． Ｒｏｕｇｈ ｓｅｔ ａｐｐｒｏａｃｈ ｔｏ ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， １９９８， １１２ （１ ／ ２ ／ ３ ／ ４）： ３９－４９． ［７］张文修， 米据生， 吴伟志． 不协调目标信息系统的知识 约简［Ｊ］． 计算机学报， ２００３， ２６（１）： １２－１８． ＺＨＡＮＧ Ｗｅｎｘｉｕ， ＭＩ Ｊｕｓｈｅｎｇ， ＷＵ Ｗｅｉｚｈｉ． Ｋｎｏｗｌｅｄｇｅ ｒｅｄｕｃｔｉｏｎｓ ｉｎ ｉｎｃｏｎｓｉｓｔｅｎｔ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ［ Ｊ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２００３， ２６（１）： １２－１８． ［８］徐伟华， 张文修． 基于优势关系下不协调目标信息系统 的分 布 约 简 ［ Ｊ］． 模 糊 系 统 与 数 学， ２００７， ２１ （ ４ ）： １２４－１３１． ＸＵ Ｗｅｉｈｕａ， ＺＨＡＮＧ Ｗｅｎｘｉｕ． Ｄｉｓｔｒｉｂｕｔｉｏｎ ｒｅｄｕｃｔｉｏｎ ｉｎ ｉｎｃｏｎｓｉｓｔｅｎｔ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ ｂａｓｅｄ ｏｎ ｄｏｍｉｎａｎｃｅ ｒｅｌａｔｉｏｎｓ［ Ｊ］． Ｆｕｚｚｙ ｓｙｓｔｅｍｓ ａｎｄ ｍａｔｈｅｍａｔｉｃｓ， ２００７， ２１ （４）：１２４－１３１． ［９］ ＭＩＡＯ Ｄｕｏｑｉａｎ， ＺＨＡＯ Ｙａｎ， ＹＡＯ Ｙｉｙｕ， ｅｔ ａｌ． Ｒｅｌａｔｉｖｅ ｒｅｄｕｃｔｓ ｉｎ ｃｏｎｓｉｓｔｅｎｔ ａｎｄ ｉｎｃｏｎｓｉｓｔｅｎｔ ｄｅｃｉｓｉｏｎ ｔａｂｌｅｓ ｏｆ ｔｈｅ Ｐａｗｌａｋ ｒｏｕｇｈ ｓｅｔ ｍｏｄｅｌ ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２００９， １７９（２４）： ４１４０－４１５０． ［１０］张楠， 苗夺谦， 岳晓冬． 区间值信息系统的知识约简 ［Ｊ］． 计算机研究与发展， ２０１０， ４７（８）： １３６２－１３７１． ＺＨＡＮＧ Ｎａｎ， ＭＩＡＯ Ｄｕｏｑｉａｎ， ＹＵＥ Ｘｉａｏｄｏｎｇ． Ａｐｐｒｏａｃｈｅｓ ｔｏ ｋｎｏｗｌｅｄｇｅ ｒｅｄｕｃｔｉｏｎ ｉｎ ｉｎｔｅｒｖａｌ⁃ｖａｌｕｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ｒｅｓｅａｒｃｈ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ， ２０１０， ４７（８）： １３６２－１３７１． ［１１］苗夺谦， 胡桂荣． 知识约简的一种启发式算法［ Ｊ］． 计 算机研究与发展， １９９９， ３６（６）： ６８１－６８４． ＭＩＡＯ Ｄｕｏｑｉａｎ， ＨＵ Ｇｕｉｒｏｎｇ． Ａ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｒｅｄｕｃｔｉｏｎ ｏｆ ｋｎｏｗｌｅｄｇｅ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ｒｅｓｅａｒｃｈ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ， １９９９， ３６（６）： ６８１－６８４． ［１２］王国胤， 于洪， 杨大春． 基于条件信息熵的决策表约简 ［Ｊ］． 计算机学报， ２００２， ２５（７）： ７５９－７６６． ＷＡＮＧ Ｇｕｏｙｉｎ， ＹＵ Ｈｏｎｇ， ＹＡＮＧ Ｄａｃｈｕｎ． Ｄｅｃｉｓｉｏｎ ｔａｂｌｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｃｏｎｄｉｔｉｏｎａｌ ｉｎｆｏｒｍａｔｉｏｎ ｅｎｔｒｏｐｙ ［ Ｊ ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２００２， ２５（７）： ７５９－７６６． ［１３］ＱＩＡＮ Ｙｕｈｕａ， ＬＩＡＮＧ Ｊｉｙｅ， ＰＥＤＲＹＣＺ Ｗ， ｅｔ ａｌ． Ｐｏｓｉｔｉｖｅ ａｐｐｒｏｘｉｍａｔｉｏｎ： ａｎ ａｃｃｅｌｅｒａｔｏｒ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｉｎ ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ ［ Ｊ ］． Ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１０， １７４ （９）： ５９７－６１８． ［１４］ ＱＩＡＮ Ｙｕｈｕａ， ＬＩＡＮＧ Ｊｉｙｅ， ＰＥＤＲＹＣＺ Ｗ， ｅｔ ａｌ． Ａｎ ·３８４· 智 能 系 统 学 报 第 １２ 卷
第3期 高学义，等：广义分布保持属性约简研究 ·385· efficient accelerator for attribute reduction from incom-plete [20]ZHANG Xiao,MEI Changlin,CHEN Degang,et al. data in rough set framework[J].Pattern recognition, Multi-confidence rule acquisition and confidence-preserved 2011,44(8):1658-1670. attribute reduction in interval-valued decision systems[J]. [15]钱宇华，梁吉业，王锋.面向非完备决策表的正向近似 International journal of approximate reasoning,2014,55 特征选择加速算法[J].计算机学报，2011,34(3)： (8):1787-1804. 435-442 作者简介： QIAN Yuhua,LIANG Jiye,WANG Feng.A positive 高学义，男，1992年生，硕士研究 approximation based accelerated algorithm to feature selection from incomplete decision tables [J].Chinese 生，主要研究方向为粗糙集、数据挖掘 journal of computers,2011,34(3):435-442. 与机器学习。 [16]CHEN Hongmei,LI Tianrui,RUAN Da,et al.A rough- set based incremental approach for updating approximations under dynamic maintenance environments[J].IEEE transactions on knowledge and data engineering,2013,25 张楠，男，1979年生，博士，主要研 (2):274-284. 究方向为粗糙集、认知信息学与人工 [17]CHEN Hongmei,LI Tianrui,LUO Chuan,et al.A rough set- 智能。 based method for updating decision rules on attribute values' coarsening and refining[J].IEEE transactions on knowledge and data engineering,2014,26(12):2866-2899. [18]JIA Xiuyi,SHANG Lin,ZHOU Bing,et al.Generalized attribute reduct in rough set theory[J].Knowledge-based 童向荣，男，1975年生，教授，博土， systems,2015,91:204-218. 主要研究方向为多Agent系统、分布式 [19]ZHOU Jie,MIAO Duoqian,PEDRYCZ W,et al.Analysis 人工智能与数据挖掘技术。 of alternative objective functions for attribute reduction in complete decision tables [J].Soft computing,2011,15 (8):1601-1616
ｅｆｆｉｃｉｅｎｔ ａｃｃｅｌｅｒａｔｏｒ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｆｒｏｍ ｉｎｃｏｍ⁃ｐｌｅｔｅ ｄａｔａ ｉｎ ｒｏｕｇｈ ｓｅｔ ｆｒａｍｅｗｏｒｋ ［ Ｊ ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２０１１， ４４（８）： １６５８－１６７０． ［１５］钱宇华， 梁吉业， 王锋． 面向非完备决策表的正向近似 特征选择加速算法［ Ｊ］． 计算机学报， ２０１１， ３４ （ ３）： ４３５－４４２． ＱＩＡＮ Ｙｕｈｕａ， ＬＩＡＮＧ Ｊｉｙｅ， ＷＡＮＧ Ｆｅｎｇ． Ａ ｐｏｓｉｔｉｖｅ ａｐｐｒｏｘｉｍａｔｉｏｎ ｂａｓｅｄ ａｃｃｅｌｅｒａｔｅｄ ａｌｇｏｒｉｔｈｍ ｔｏ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｆｒｏｍ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｔａｂｌｅｓ ［ Ｊ ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２０１１， ３４（３）： ４３５－４４２． ［１６］ＣＨＥＮ Ｈｏｎｇｍｅｉ， ＬＩ Ｔｉａｎｒｕｉ， ＲＵＡＮ Ｄａ， ｅｔ ａｌ． Ａ ｒｏｕｇｈ⁃ ｓｅｔ ｂａｓｅｄ ｉｎｃｒｅｍｅｎｔａｌ ａｐｐｒｏａｃｈ ｆｏｒ ｕｐｄａｔｉｎｇ ａｐｐｒｏｘｉｍａｔｉｏｎｓ ｕｎｄｅｒ ｄｙｎａｍｉｃ ｍａｉｎｔｅｎａｎｃｅ ｅｎｖｉｒｏｎｍｅｎｔｓ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｋｎｏｗｌｅｄｇｅ ａｎｄ ｄａｔａ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１３， ２５ （２）： ２７４－２８４． ［１７］ＣＨＥＮ Ｈｏｎｇｍｅｉ， ＬＩ Ｔｉａｎｒｕｉ， ＬＵＯ Ｃｈｕａｎ， ｅｔ ａｌ． Ａ ｒｏｕｇｈ ｓｅｔ⁃ ｂａｓｅｄ ｍｅｔｈｏｄ ｆｏｒ ｕｐｄａｔｉｎｇ ｄｅｃｉｓｉｏｎ ｒｕｌｅｓ ｏｎ ａｔｔｒｉｂｕｔｅ ｖａｌｕｅｓ’ ｃｏａｒｓｅｎｉｎｇ ａｎｄ ｒｅｆｉｎｉｎｇ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｋｎｏｗｌｅｄｇｅ ａｎｄ ｄａｔａ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１４， ２６（１２）： ２８６６－２８９９． ［１８］ ＪＩＡ Ｘｉｕｙｉ， ＳＨＡＮＧ Ｌｉｎ， ＺＨＯＵ Ｂｉｎｇ， ｅｔ ａｌ． Ｇｅｎｅｒａｌｉｚｅｄ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔ ｉｎ ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ［ Ｊ］． Ｋｎｏｗｌｅｄｇｅ－ｂａｓｅｄ ｓｙｓｔｅｍｓ， ２０１５， ９１： ２０４－２１８． ［１９］ＺＨＯＵ Ｊｉｅ， ＭＩＡＯ Ｄｕｏｑｉａｎ， ＰＥＤＲＹＣＺ Ｗ， ｅｔ ａｌ． Ａｎａｌｙｓｉｓ ｏｆ ａｌｔｅｒｎａｔｉｖｅ ｏｂｊｅｃｔｉｖｅ ｆｕｎｃｔｉｏｎｓ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｉｎ ｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｔａｂｌｅｓ ［ Ｊ］． Ｓｏｆｔ ｃｏｍｐｕｔｉｎｇ， ２０１１， １５ （８）： １６０１－１６１６． ［ ２０ ］ ＺＨＡＮＧ Ｘｉａｏ， ＭＥＩ Ｃｈａｎｇｌｉｎ， ＣＨＥＮ Ｄｅｇａｎｇ， ｅｔ ａｌ． Ｍｕｌｔｉ⁃ｃｏｎｆｉｄｅｎｃｅ ｒｕｌｅ ａｃｑｕｉｓｉｔｉｏｎ ａｎｄ ｃｏｎｆｉｄｅｎｃｅ⁃ｐｒｅｓｅｒｖｅｄ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｉｎ ｉｎｔｅｒｖａｌ⁃ｖａｌｕｅｄ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍｓ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ａｐｐｒｏｘｉｍａｔｅ ｒｅａｓｏｎｉｎｇ， ２０１４， ５５ （８）： １７８７－１８０４． 作者简介： 高学义，男，１９９２ 年生，硕士研究 生，主要研究方向为粗糙集、数据挖掘 与机器学习。 张楠，男，１９７９ 年生，博士，主要研 究方向为粗糙集、认知信息学与人工 智能。 童向荣，男，１９７５ 年生，教授，博士， 主要研究方向为多 Ａｇｅｎｔ 系统、分布式 人工智能与数据挖掘技术。 第 ３ 期 高学义，等：广义分布保持属性约简研究 ·３８５·