基于Bucket Sort的快速属性约简算法

利用桶排序思想设计了一个求解U/C的算法,其时间复杂度降为O(∣C∣∣U∣).由此,给出一种无需求解正域便能判断正域是否变化的方法.基于以上方法,提出一种快速属性约简算法.该算法的求解策略是在每次迭代过程中求解决策表相对核,如果在某次迭代过程中找不到这样的核属性,则任意排除一个条件属性.最后通过实验分析了该算法在最坏情况下的时间复杂性,其复杂性降为O(∣C∣2∣U/C∣).

Fast Algorithm for Computing Attribute Reduction Based on Bucket Sort

An algorithm based on Bucket Sort for computing U/C is proposed, whose complexity is cut down to O(|C||U|). And a method is designed to estimate whether the change of positive region or not, which doesn’t compute positive region. A fast attribute reduction algorithm based on U/C is introduced. The reduction strategy of the algorithm is to compute relative core. If in some iteration the algorithm can not find such cores, it will eliminate one condition attribute preparing for finding relative core in the next iteration. The time complexity of the algorithm in the worst case is analyzed and its temporal complexity is O(|C|²|U/C|).