基于软集的属性约简方法的研究

发布时间：2020-04-24 11:15

【摘要】：在当今社会中,决策已成为一种普遍的日常行为,并被广泛应用于各个领域。由于现实世界中存在着复杂多变性,从而导致了很多信息都是不确定和模糊的,包含着这些不确定性和模糊性信息的决策问题,对人们的决策判断造成了非常大的影响。为了能进一步减少软集正规参数约简方法中的搜索空间、更加全面的反映出软集中的冗余信息、更好的处理大数据背景下的不确定性数据,本文从关联规则提取以及数据本身的角度出发,分别提出了基于局部搜索的软集最小正规参数约简方法和基于离散贡献度的软集参数约简启发式方法,具体的研究内容如下:(1)针对软集正规约简算法筛选候选参数约简集效率低和搜索的参数约简集结果不全面等问题,提出了一种基于局部搜索的软集最小正规参数约简算法。该方法通过引入频度和、等价类和最小生成元概念来构造软集参数约简的最小候选集,并利用最小生成元分布在低幂集,最小生成元的超集不在最小候选集中等性质,给出基于局部搜索的软集参数约简算法,可减少搜索空间和加速逐级搜索速度,从而提高了筛选候选参数约简集的效率及质量,降低了已有的软集参数约简算法的计算复杂度。通过实验进行对比,验证了基于局部搜索的软集最小正规参数约简算法搜索效率更高,结果更合理。(2)在研究基于0-1线性规划的软集参数约简方法的基础上,考虑软集的实际应用背景,针对软集正规参数约简算法在约简数据较大的软集时效果较差的问题,将软集与概率论结合,给出软集的软标准差和约简路径的概念,利用软标准差提出一种软集参数约简的启发式算法。通过理论和实例证明了算法的完备性,将此方法和基于0-1线性规划的软集参数约简方法进行对比分析,验证了基于离散贡献度的软集参数约简启发式方法的可行性和正确性。
【图文】：

分层模型,候选集

图 4.1 软集的分层模型在以下两种约束条件下将减小搜索空间，加快算法的速度：如果存在e A，则设 A E，使得 ( )FS A 。如果是软集S 的的最小候选集，那么它的超集是是的最小候选集。述定义和结论，下面给出基于局部搜索的软集参数约简算法的MPR algorithm集： S ( F,A)性集： 1 2 nU h ,h ,...,h数集： 1 2 mE e ,e ,...,e数候选集始化 k 1层可生成属性集kGen 和可约简集，，即 kGen e n， ( ) ( ) 0H HRe s e A| S e or S e n；

运行时间,候选集,参数,算法

① 参数候选集NENPR 算法找出的是一个基数最大的参数候选集，但如果出现几同的最大候选集，如例 3.7 中所示以下三个最大参数候选集 4 6 7e ,e ,e ， 1e及 5 7 8e ,e ,e 都可以作为最大参数候选集，此时无论选择哪一个集合作为候选集都不能完全的反映出参数候选集中的所有信息。而 MPR 算法通找出所有的最小候选参数约简集，有效的反映出软集中所有可约简的冗② 搜索空间NENPR 算法从软集 ( F ,E )中搜索出所有 A E，AS nq 的集合，再选集中寻找出最大的候选约简集，这是一个从 1 到|E|的全搜索。搜索大，呈指数级增长，时间复杂度为 ( ( ))2 223 4 2 1m /m m mO C C ... C m /。算法通过局部搜索分层算法以搜索树的方式快速地找出所有满足的所有最小候选集，搜索空间较小。③ 实验结果将 MPR 算法和 NENPR 算法在不同的对象和参数个数情况下进一能测试，比较结果如图 4.6 至图 4.9 所示。
【学位授予单位】：青海师范大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：O225

【参考文献】