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

Abstract: Cost-sensitive feature selection is an important research field in the process of data mining. It aims at obtaining an attribute subset of the lowest total cost, through balancing test cost and misclassification cost. According to the shortcoming of the classical backtracking algorithm with longer running time, combining divide and conquer thought, this paper proposes an improved backtracking algorithm. Introducing two related parameters, this algorithm computes adaptively parameters according to the dataset scale, and splits the dataset with these parameters. It can enhance the    efficiency of the classical backtracking algorithm by reducing the problem size. The experiments on the datasets with large scale show that this improved algorithm is effective and meets the need of practical problems. At the same time guaranteeing the effect, this improved algorithm promotes the efficiency of 20% at least than the classical backtracking algorithm. Compared with heuristic algorithm, this improved algorithm obtains an attribute set with a smaller total cost and ensures the efficiency.

Key words: rough sets, granular computing, cost-sensitive, feature selection, adaptive divide and conquer