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

作者：林连海; 田立勤; 蔡铭楷; 李升宏

来源：计算机工程与科学, 2020, 42(02): 250-258.

• 软集
• 参数约简
• 概率论
• 方差辗转法
• 大数据

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

• 单位
  青海师范大学; 华北科技学院