关于属性约简和集合覆盖问题的探讨

《关于属性约简和集合覆盖问题的探讨》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、关于属性约简和集合覆盖问题的探讨陈彩云李治国（南开大学组合数学研究中心，天津6"""7%）：8/9(:*;0<=;(:>?=@<>A?$;A9摘要论文探讨了粗糙集的属性约简和集合覆盖问题之间的联系。通过构造信息系统的相关矩阵将粗糙集的属性约简问题与集合覆盖问题联系起来，从而将粗糙集的属性约简问题简化为集合覆盖问题。然后用几个定理及其证明说明了这种联系是存在的。基于这种联系，推断出求最小属性约简问题算法的近似度的上下界为（）（）（）和*=8$BC/*=*=8$BCD9%（（））（）。最后，利用两个范例分别演示了如何具体地构造相关

2、矩阵以及如何将解决集合覆盖问题的思想和方%/4%*=8$BC法应用到解决属性约简问题中来，由此推理如果将文献中的解决集合覆盖问题的启发式方法应用到解决最小属性约E简中，属性约简的复杂度为（!），并且能以的“概率”得到最小属性约简。!645:;:7FG关键词属性约简集合覆盖问题粗糙集.’/0(12文章编号（）文献标识码中图分类号%""!/F66%/!""#"!/""##/"6HI’%F!"#$%&’()*%$+#,’-’(!##.,/$#*01-%"*#2’3*.,-45.’/6*728*-21,&$-9,:8,4$’（J<=K

3、<1LA1JA9M:=(KA1:;NAL.(=+(:O=:P<1N:K>，I:(=Q:=6"""7%）：!/0#.1+#I0:NR(R<12:N;?NN;A=NK1?;K:=SK0<1<*(K:A=9(K1:T(=2K0<=S:P

4、（）K0<*A)<1MA?=2AL(RR1AT:9(K:A=:N*=8$BC/*=*=8$BCD9%(=2%/4%*=8$BC1$U=K0<<=2K0<>S:P

5、9R*(=2K0L1A9K0<0

6、一种数据分析理&$’()*(+总结及将来要研究的工作。论,%-。该理论为发现重要数据结构和复杂对象的分类提供了强有力的基础。目前已经在数据挖掘、模式识别、人工智能和分类领域等有很广泛的应用。它的核心内容之一就是属性约简。国!粗糙集基本理论,!-内外很多专家对之进行了研究，已经知道，求粗糙集的最小属!$%信息系统性约简是一个问题,%-。尽管粗糙集的理论研究已取得信息系统由元集组成，记为，，，，其中：.’/0(12#!"#$%&’3很大的进展，但在属性约简方面的具体实现算法还不多见。已：由个研究对象，，⋯，组成的非空集合，称为闭域

7、；$4(((5%!)有的，如基于信息熵、基于差别矩阵等算法虽然在某些问题上：由%*个属性，，⋯，组成的有限非空集合；4+++5%!*取得了相当的成效，但到目前为止，还没有一个公认的、高效的：表示&"!&+"%+%中所有属性的值域，其中&+是属性属性约简算法,#-。论文将粗糙集属性约简问题和组合优化中的经典问题———集合覆盖问题联系起来，在它们之间找出了一种的值域。+"%：，，有("$+"%：全决策函数，使得对于任一’$,%#&’对应关系，使得求最小属性约简问题转化成求最小集合覆盖问（，）。通过作用，信息系统能用一个有限的数据表

8、表(+"&’!+题。集合覆盖问题是经典的问题，国内外已有很多著.’/0(12示，表的第行研究对象和第列属性-(.-+.有对应的值。名的专家对此进行了深入的研究，理论发展比较成熟。作者想 通过此篇论文，将属性约简问题简化为集合覆盖问题，并将解!$!等价类首先介绍一下不可区分关系