基于局部搜索的软集最小正规参数约简方法

软集在解决不确定性问题的决策分析过程中,参数约简是关键和棘手的问题.软集正规参数约减方法采用全局搜索方式求解最大的参数约简集,存在候选属性集计算量大和冗余度高的问题,针对这一问题提出一种基于局部搜索的软集最小参数约简方法.给出频度和等价类、最小生成元的概念,在此基础上给出分层局部搜索的软集最小参数约简算法,减少搜索空间和加速逐层约简的过程,最后求出软集最小正规约简的最优解.通过分析和实例证明该软集参数约简方法,大幅度减小了候选参数约简集数量,降低运算的复杂度.

方差辗转的软集参数约简算法

软集是一种处理不确定数据的理论、工具,通常用于决策论中。软集的参数约简是指删除对决策几乎没有影响的冗余参数,自从0-1线性规划算法提出以来,软集的参数约简问题基本得到了解决,但0-1线性规划算法实现复杂,需要依赖整数规划算法。在此,考虑软集的实际应用背景,将软集与概率论结合,设计出一个在大数据背景下的软集参数约简方法——方差辗转法,该算法的时间复杂度为O(m 2n),而0-1线性规划通常视为NP难问题。方差辗转法实现简单,在物集(或全集)较小,不超过属性集大小的2倍时,效果较差,但随着物集(或全集)大小的增长,效率会逐步上升,最终运算效率会全面优于0-1线性规划算法的,对于约简稠密度高的软集效率会更高。