第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)={<0,1>} 函数，并通过吸收率进行简化。 Y08,(u2)={<1,1> 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)={<1,0>,<2,0>} 以及分布可辨识矩阵的可辨识属性集，其中论域为 Y9aJ(2)={<0,0>,<2,0>} U={u1,山2，…，4n},i,je{1,2,…,n}。 Y00J(u3)={<0,0>} 1)a=B=0时 Y0aJ(u4)={<0,0> 当α和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
度均为 ０，而对于置信度不为 ０ 的规则在约简前后 的置信度均不为 ０，由此可得如下结论。 定理 ４ 设决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ ），对于 ∀Ｒ⊆ＡＴ 且 Ｒ≠⌀，α＝ β ＝ ０，若 Ｒ 是决策表 ＤＴ 的一 个广义分布保持约简，则 Ｒ 必定同时是决策表 ＤＴ 的一个广义决策保持约简。 证明 不妨设∀ｕｉ，ｕｊ∈Ｕ，其中［ｕｉ］ＡＴ∩［ｕｊ］ＡＴ ＝ ⌀，同时设 Ｕ／ Ｄ＝｛Ｄ１，Ｄ２，…，Ｄ｜Ｕ／ Ｄ｜ ｝。 若有 Υ ［０，０］ ＡＴ （ｕｉ）≠ Υ ［０，０］ ＡＴ （ ｕｊ ） 成立，则∃Ｄｋ ∈Ｕ／ Ｄ，其中ｋ∈｛ １，２，…， Ｕ／ Ｄ ｝，使得［ｕｉ］ ＡＴ∩Ｄｋ ＝ ⌀∧［ｕｊ］ ＡＴ∩Ｄｋ≠⌀或 ［ｕｉ］ ＡＴ ∩ Ｄｋ ≠ ⌀ ∧ ［ｕｊ］ ＡＴ ∩ Ｄｋ ＝ ⌀ 成 立， 也 即 δＡＴ（ｕｉ）≠δＡＴ（ｕｊ）成立，故由定义 ４ 可知有 Ｍ ［０，０］ ｉｊ ＝ Ｍ ＧＥＮ ｉｊ ＝ ｛ａ∈ＡＴ ｆ（ ｕｉ，ａ） ≠ｆ（ ｕｊ，ａ）｝ 成立；反之，若 Υ ［０，０］ ＡＴ （ ｕｉ ） ＝ Υ ［０，０］ ＡＴ （ ｕｊ ），则∀Ｄｋ ∈Ｕ／ Ｄ，有［ｕｉ］ ＡＴ ∩ Ｄｋ≠ ⌀ ∧ ［ｕｊ］ ＡＴ ∩ Ｄｋ ≠ ⌀ 或 ［ｕｉ］ ＡＴ ∩ Ｄｋ ＝ ⌀∧［ｕｊ］ ＡＴ∩Ｄｋ ＝⌀成立，故 δＡＴ（ｕｉ）＝ δＡＴ（ｕｊ），由定 义 ４ 可知 Ｍ ［０，０］ ｉｊ ＝ Ｍ ＧＥＮ ｉｊ ＝ ＡＴ 成立。 由于∀ｕｉ，ｕｊ ∈ Ｕ，故在 α ＝ β ＝ ０ 条件下，有 ＭＧＥＮ ＝ Ｍ ［０，０］ 成立，故 Ｒ 是决策表 ＤＴ 的一个广义分布保持约简，则 Ｒ 必定 同时是决策表 ＤＴ 的一个广义决策保持约简，证毕。 ２）α＝ β ＝ １ 时 显然，当 α＝ β ＝ １ 时，广义分布保持约简实质是 保证了置信度为 １ 的规则在约简前后的置信度保持 不变，由此可得如下结论。 定理 ５ 决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ），对于 ∀Ｒ⊆ＡＴ 且 Ｒ≠⌀，令 α ＝ β ＝ １，若 Ｒ 是决策表 ＤＴ 的一个广义分布保持约简，则 Ｒ 必定同时是决策表 ＤＴ 的一个正域保持约简。 证明 不 妨 设 ∀ｕｉ， ｕｊ ∈ Ｕ， 其 中， ［ｕｉ］ ＡＴ ∩ ［ｕｊ］ ＡＴ ＝⌀，Ｕ／ Ｄ＝ ｛Ｄ１ ，Ｄ２ ，…，Ｄ Ｕ／ Ｄ ｝，分情况进行 如下讨论。 当 Υ ［１，１］ ＡＴ （ｕｉ）≠Υ ［１，１］ ＡＴ （ｕｊ）成立时，有 Ｍ ［１，１］ ｉｊ ＝ ｛ａ∈ ＡＴ ｆ（ｕｉ，ａ）≠ｆ（ｕｊ，ａ）｝成立。 假设 Υ ［１，１］ ＡＴ （ｕｉ）≠⌀ 且 Υ ［１，１］ ＡＴ （ｕｊ）≠⌀，则∃Ｄｋ∈Ｕ／ Ｄ，使得 Ｐ（Ｄｋ ［ｕｉ］ＡＴ ） ＝ Ｐ（Ｄｋ ［ｕｊ］ＡＴ）＝ １ 成立，故有 ｕｉ，ｕｊ∈ＰＯＳＡＴ（Ｄ）且 ｆ（ｕｉ， ｄ）≠ｆ（ｕｊ，ｄ）成立，即 Ｍ ＰＯＳ ｉｊ ＝ ｛ａ∈ＡＴ ｆ（ｕｉ，ａ）≠ｆ（ｕｊ， ａ）｝ ＝Ｍ ［１，１］ ｉｊ 成立。 若假设不成立，则有（ｕｉ∈ＰＯＳＡＴ（Ｄ）∧ ｕｊ∈ＢＮＤＡＴ （ Ｄ）） 或 （ ｕｊ ∈ ＰＯＳＡＴ （ Ｄ） ∧ ｕｉ ∈ ＢＮＤＡＴ （Ｄ））成立；若 ｆ（ ｕｉ，ｄ）≠ｆ（ｕｊ，ｄ）成立，则有 Ｍ ＰＯＳ ｉｊ ＝ ｛ａ∈ＡＴ ｆ（ｕｉ，ａ）≠ｆ（ｕｊ，ａ）｝ ＝ Ｍ ［１，１］ ｉｊ ，若 ｆ（ ｕｉ，ｄ） ＝ ｆ（ｕｊ，ｄ），则有 Ｍ ＰＯＳ ｉｊ ＝ＡＴ，同时必然∃ｕｉ′∈［ｕｉ］ＡＴ，ｕｊ′∈ ［ｕｊ］ ＡＴ ，使得ｆ（ｕｉ′，ｄ）≠ｆ（ｕｊ′，ｄ），故 Ｍ ＰＯＳ ｉ′ｊ′ ＝ ｛ ａ∈ＡＴ ｆ（ｕｉ′，ａ）≠ｆ（ｕｊ′，ａ）｝ ＝Ｍ ［１，１］ ｉｊ ，故 Ｍ ＰＯＳ ｉ′ｊ′ ＝Ｍ ［１，１］ ｉｊ 。 当 Υ ［１，１］ ＡＴ （ ｕｉ ） ＝ Υ ［１，１］ ＡＴ （ ｕｊ ） 时， 有 Υ ［１，１］ ＡＴ （ ｕｉ ） ＝ Υ ［１，１］ ＡＴ （ｕｊ）＝ ⌀ 或 Υ ［１，１］ ＡＴ （ ｕｉ） ＝ Υ ［１，１］ ＡＴ （ ｕｊ）≠⌀成立。 对于前者，∀Ｄｋ∈Ｕ／ Ｄ，使得［ｕｉ］ ＡＴ∩Ｄｋ≠［ｕｉ］ ＡＴ成 立 并 且 ［ｕｊ］ ＡＴ ∩ Ｄｋ ≠ ［ｕｊ］ ＡＴ 成 立， 故 有 ｕｉ，ｕｊ∈ＢＮＤＡＴ（Ｄ）； 对 于 后 者， ∃Ｄｋ ∈ Ｕ／ Ｄ， 使 （［ｕｉ］ ＡＴ∩Ｄｋ ＝ ［ｕｉ］ ＡＴ ） ∧（ ［ｕｊ］ ＡＴ ∩Ｄｋ ＝ ［ｕｊ］ ＡＴ ） 成 立，即 ｆ（ ｕｉ，ｄ） ＝ ｆ（ｕｊ，ｄ），故由定义 ４ 可知 Ｍ ＰＯＳ ｉｊ ＝ Ｍ ［１，１］ ｉｊ ＝ＡＴ。 综上，由于∀ｕｉ，ｕｊ∈Ｕ，故在 α＝ β ＝ １ 的条件下， ＭＰＯＳ ＝Ｍ ［１，１］成立，故 Ｒ 是决策表 ＤＴ 的广义分布保 持约简，则 Ｒ 必定同时是决策表 ＤＴ 的一个正域保 持约简，证毕。 ３） α＝ ０，β ＝ １ 时 当 α ＝ ０，β ＝ １ 时，广义分布保持约简实质是保 证了置信度在［０，１］内的所有规则在约简前后的置 信度不变，同时易得，此时对象的［α，β］决策－置信 度序偶集等价于在决策等价类划分上的置信度分 布，由此可得如下结论。 定理 ６ 决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ ），对于 ∀Ｒ⊆ＡＴ 且 Ｒ≠⌀，α＝ ０ 且 β ＝ １，若 Ｒ 是决策表 ＤＴ 的一个广义分布保持约简，则 Ｒ 必定同时是决策表 ＤＴ 的一个分布保持约简。 证明 不妨设∀ｕｉ，ｕｊ∈Ｕ，其中［ｕｉ］ＡＴ∩［ｕｊ］ＡＴ ＝ ⌀，Ｕ／ Ｄ＝ ｛Ｄ１ ，Ｄ２ ，…，Ｄ Ｕ／ Ｄ ｝；若 Υ ［０，１］ ＡＴ （ｕｉ）≠Υ ［０，１］ ＡＴ （ｕｊ ），则∃Ｄｋ ∈Ｕ／ Ｄ，使得 Ｐ（Ｄｋ ［ｕｉ］ ＡＴ ） ≠Ｐ（Ｄｋ ［ｕｊ］ ＡＴ ），故有 μＡＴ（ｕｉ）≠μＡＴ（ｕｊ）成立，所以由定义 ４ 可知 Ｍ ＤＩＳ ｉｊ ＝Ｍ ［０，１］ ｉｊ ＝ ｛ａ∈ＡＴ ｆ（ｕｉ，ａ）≠ｆ（ｕｊ，ａ）｝；反 之，若 Υ ［０，１］ ＡＴ （ｕｉ）＝ Υ ［０，１］ ＡＴ （ｕｊ）成立，则∀Ｄｋ∈Ｕ／ Ｄ，有 Ｐ（Ｄｋ ［ｕｉ］ ＡＴ ）＝ Ｐ（Ｄｋ ［ｕｊ］ ＡＴ ）成立，则由定义 ４ 可 知 Ｍ ＤＩＳ ｉｊ ＝ Ｍ ［０，１］ ｉｊ ＝ ＡＴ；由于∀ｕｉ，ｕｊ ∈Ｕ，故在 α ＝ ０， β ＝ １ 的条件下，有 ＭＤＩＳ ＝ Ｍ ［０，１］ 成立，故 Ｒ 是决策表 ＤＴ 的一个广义分布保持约简，必定同时是决策表 ＤＴ 的一个分布保持约简，证毕。 综上，图 １ 给出了广义分布保持约简与上述几 种约简之间的关系。 图 １ 几种不同约简之间的关系 Ｆｉｇ．１ Ｒｅｌａｔｉｏｎｓｈｉｐｓ ａｍｏｎｇ ｄｉｆｆｅｒｅｎｔ ｒｅｄｕｃｔｉｏｎｓ 第 ３ 期 高学义，等：广义分布保持属性约简研究 ·３８１·