关于属性约减和集合覆盖问题的探讨.pdfVIP

关于属性约简和集合覆盖问题的探讨 陈彩云 李治国 (南开大学组合教学研究中心，天津 300071) E-mail:chencaivun@ 摘 要 论文探讨了粗糙集的属性约简和集合是盖问题之间的联系。通过构造信息系统的相关矩阵将粗糙集的属性约 简问题与集合段盖问题联系起来，从而将粗糙集的属性约简问题简化为集合及盖问题。然后用儿个定理及其证明说明了 这种联系是存在的。基于这种联系，推断出求最小属性约简问题算法的近似度的上下界为InOUI)-Inln(IUI)+0(1)和 (1-o(I))In(I(川)。最后，利用两个范例分别演示了如何具体地构造相关矩阵以及如何将解决集合提盖问劫的思想和方 法应用到解决属性约简问题中来，由此推理如果将丈献5中的解决集合覆盖问题的启发式方法应用列解决最小属性约 简中，属性约简的复杂度为o(rm+mt)、并且能以78%的’概‘率”得到最小属性约简 关键词 属性约简 集合履盖 NP-hard问题 粗糙集 文章编号 1002-8331-(2004)02-0044-03 文献标识码 A 中图分类号 TP18 AStudyofReductionofAttributesandSetCoveringProblem Chen Caiyun LiZhiguo (CenterforCombinatoricsofNankaiUniversity,Tianjin300071) Ibispaperdiscussestherelationshipbetweenthereductionofattributesandsetcoveringbyconstructingthe andthengivesseveralthen-.. tointerpretthisrelationship.Theauthorsdeducetheupperboundand thelowerboundofapproximationisIn(IUI)-lnln(IUI)+0(1)and(I-o(1))In(IUI)respectively.hrtheendtheygivetwo examplesmdemonstratehowtoennstmctthe relation matrix and how ideasandmethodsofsetcoveringcanhe a即liedintotheproblemofreductionofattributes.Andatthesametimetheinferthatcomplexityandtheprecisionof thereductionofattributesiso(rnr+m})and78percentrespectivelyfromtheheuristicalgorithmappearinginreference5 Keywords:ReductionofAttributes,5etCovering,NP-hardpmblem,Roughsets 1 引言 后举例说明如何具体运用集合ill盖的思想和方法解决属性约 粗糙集是波兰Z.Pawlak教授提出的一种数据分析理 简间题，从而进一步阐述了两个间题之间的联系 最后给出了 论1-1。该理论为发现重要数据结构和复杂对象的分类提供了强 总结及将来要研究的工作。 有力的基础。目前已经在数据挖掘、模式识别、人工智能和分类 领域等有很广泛的应用。它的核心内容之一就是属性约简。国 2 粗糙集基本理论Rl 内外很多专家对之进行了研究，已经知道，求粗糙集的最小属 2.1信息系统 性约简是一个NP-hard问题P1。尽管粗糙集的理论研究已取得 信息系统由4元集组成，记为S=U,p,v户，其中: 很大的进展，但在属性约简方面的具体实现算法还不多见。已 U:由个研究对象卜i,xz,xn)组成的非空集合。称为闭域; 有的 如基于信息嫡、基于差别矩阵等算法虽然在某些问题上 口:由n个属性匆,q