代价敏感属性约简的自适应分治算法

代价敏感属性约简问题作为经典属性约简问题的自然扩展,将代价引入数据,使得属性约简问题更加具有现实意义。文章基于分治思想,先按列将数据集拆分为若干个互不相交的子数据集,然后对各子数据集进行约简,并把约简后的子数据集多路合并。依次继续执行约简和合并操作,最终得到最小测试代价约简。每个子数据集的大小及子数据集的总个数自适应于各个数据集的规模而非固定不变。为验证算法的有效性,选择四个UCI标准数据集进行实验,并与其他算法进行结果对比。实验结果表明,该算法能在较短时间内获得可接受的结果,更适应实际问题的需要。

Adaptive divide and conquer algorithm for cost-sensitive attribute reduction

Cost-sensitive attribute reduction problem is the natural extension of classical attribute reduction, and it is more practical than the classical one by introducing cost. Based on divide and conquer thought, this paper proposes a new algorithm to deal with cost-sensitive attribute reduction. Firstly, the dataset is splitted into disjoint sub-datasets according to the number of the column. Then some sub-datasets are merged after backtracking reduction on each sub-dataset. Finally, it continues reducting and merging, and gets minimal test cost reduction. The size of the sub-datasets and the number of the sub-datasets are adaptive to the scale of the dataset rather than fixed. This algorithm is tested on four UCI datasets to verify its effectiveness. Compared with other algorithms, the experimental results show that the proposed algorithm can provide the efficient solution in a relatively short time.