Merge reduction for cost-sensitive learning

被引：0
作者：
Zhang, Aiting [1 ]
Xu, Juan [1 ]
Chen, Wenbin [1 ]
Min, Fan [1 ]
机构：
[1] School of Computer Science, Southwest Petroleum University, Chengdu
来源：
Journal of Computational Information Systems | 2014年 / 10卷 / 23期
关键词：
Attribute reduction; Backtracking; Competition strategy; Cost-sensitive; Merge;
D O I：
10.12733/jcis12461
中图分类号：
学科分类号：
摘要：
Minimal test cost attribute reduction has attracted a lot of attention in the field of data mining. Many algorithms are proposed to this problem. Heuristic algorithms are fast, however inaccurate. The backtracking algorithm can always find the optimal result, but the time and space complexities are intolerable. In this paper, based on the backtracking algorithm, we present a simple yet effective algorithm called merge reduction to this problem. First, a number of subtables are obtained through dividing attributes randomly into groups. For each subtable, a reduct is obtained through backtracking. Then the reducts of each pair of adjacent groups are merged to form a new subtable. This process repeats until only one subtable is obtained and the final reduct computed. Since the result of one run is unsatisfactory, we employ the competition strategy to run the process a number of times and choose the best reduct. The proposed approach is compared with the λ-weighted reduction algorithm and the classical backtracking algorithm on four UCI datasets. Results confirm that our algorithm is more efficient and stable. Copyright © 2014 Binary Information Press.
引用
收藏
页码：10093 / 10102
页数：9
相关论文
共 20 条
  • [1] Ardagna D., Francalanci C., Trubian M., Practical machine learning tools and techniques with java implementations, Morgan Kaufmann Publishers, pp. 76-77, (2000)
  • [2] Barney J.B., Types of competition and the theory of strategy: Toward an integrative framework, Academy of Management Review, 11, pp. 791-800, (1986)
  • [3] Chawla N.V., Data mining for imbalanced datasets: An overview, Data Mining and Knowledge Discovery Handbook, pp. 853-867, (2005)
  • [4] Elkan C., The foundations of cost-sensitive learning, International Joint Conference on Artificial Intelligence
  • [5] Fan Min W.Z., Minimal cost attribute reduction through backtracking, Database Theory and Application, Bio-Science and Bio-Technology, 258, pp. 100-107, (2011)
  • [6] Bradford J.P., Kunz C., Pruning decision trees with misclassification costs, Machine Learning, 1398, pp. 131-136, (1998)
  • [7] Kumar V., Algorithms for constraint-satisfaction problems: A survey, AI Magazin
  • [8] Mackworth A.K., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial Intelligence, 25, pp. 65-74, (1985)
  • [9] Min F., Test-cost-sensitive attribute reduction, Information Sciences, pp. 4928-4942, (2011)
  • [10] Min F., Feature selection with test cost constraint, International Journal of Approximate Reasoning
12