分治策略下的代价敏感属性选择回溯算法

来源：计算机科学与探索杂志2016年第10期北京时间：

作者：黄伟婷，赵红，祝峰

单位：1. 闽南师范大学 计算机学院，福建 漳州 3630002. 闽南师范大学 粒计算及其应用重点实验室，福建 漳州 363000

摘要：代价敏感属性选择是数据挖掘的一个重要研究领域，其目的在于通过权衡测试代价和误分类代价，获得总代价最小的属性子集。针对经典回溯算法运行时间较长的缺点，结合分治思想，提出了一种改进的回溯算法。改进算法引入了两个相关参数，根据数据集规模自适应调整参数，并按参数大小拆分数据集，降低问题规模，以提高经典回溯算法的执行效率。针对较大规模数据集的实验结果表明，与经典的回溯算法相比，改进算法在保证效果的同时至少提高20%的运算效率；与启发式算法相比，改进算法在保证效率的同时取得了具有更小总代价的属性集合，可应用于实际问题。

关键词：粗糙集,粒计算,代价敏感,属性选择,自适应分治