基于Bucket Sort的快速属性约简算法
来源期刊：控制与决策2011年第2期
论文作者：蒋瑜 刘胤田 李超
文章页码：207 - 212
关键词：粗糙集;正区域;属性约简;桶排序;
摘 要：利用桶排序思想设计了一个求解U/C的算法,其时间复杂度降为O(∣C∣∣U∣).由此,给出一种无需求解正域便能判断正域是否变化的方法.基于以上方法,提出一种快速属性约简算法.该算法的求解策略是在每次迭代过程中求解决策表相对核,如果在某次迭代过程中找不到这样的核属性,则任意排除一个条件属性.最后通过实验分析了该算法在最坏情况下的时间复杂性,其复杂性降为O(∣C∣2∣U/C∣).
蒋瑜，刘胤田，李超
成都信息工程学院软件工程学院
摘 要：利用桶排序思想设计了一个求解U/C的算法,其时间复杂度降为O(∣C∣∣U∣).由此,给出一种无需求解正域便能判断正域是否变化的方法.基于以上方法,提出一种快速属性约简算法.该算法的求解策略是在每次迭代过程中求解决策表相对核,如果在某次迭代过程中找不到这样的核属性,则任意排除一个条件属性.最后通过实验分析了该算法在最坏情况下的时间复杂性,其复杂性降为O(∣C∣2∣U/C∣).
关键词：粗糙集;正区域;属性约简;桶排序;
