JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2016, Vol. 51 ›› Issue (8): 98-104.doi: 10.6040/j.issn.1671-9352.0.2015.435

Previous Articles     Next Articles

Adaptive divide and conquer algorithm for cost-sensitive attribute reduction

HUANG Wei-ting1, ZHAO Hong2, ZHU William2   

  1. 1. School of Computing, Minnan Normal University, Zhangzhou 363000, Fujian, China;
    2. Lab of Granular Computing, Minnan Normal University, Zhangzhou 363000, Fujian, China
  • Received:2015-09-14 Online:2016-08-20 Published:2016-08-08

PDF (PC)

838

Abstract: 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.

Key words: cost-sensitive, adaptive divide and conquer, granular computing, attribute reduction, rough sets

CLC Number: 

  • TP18
[1] PAWLAK Z. Rough sets[J]. International Journal of Computer and Information Sciences, 1982, 11(5):341-356.
[2] TURNEY P D. Cost-sensitive classification: empirical evaluation of a hybrid genetic decision tree induction algorithm[J]. Journal of Artificial Intelligence Research, 1995, 2(1):369-409.
[3] 张伶卫, 万文强. 基于云计算平台的代价敏感集成学习算法研究[J]. 山东大学学报(工学版), 2012, 42(4):19-23. ZHANG Lingwei, WAN Wenqiang. Study on the cost-sensitive ensemble learning algorithm based on the cloud computing platform[J]. Journal of Shandong University(Engineering Science), 2012, 42(4):19-23.
[4] 蒋盛益, 谢照青, 余雯. 基于代价敏感的朴素贝叶斯不平衡数据分类研究[J]. 计算机研究与发展, 2011, 48:387-390. JIANG Shengyi, XIE Zhaoqing, YU Wen. Naive Bayes classification algorithm based on cost sensitive for imbalanced data distribution[J]. Journal of Computer Research and Development, 2011, 48:387-390.
[5] JIANG Liangxiao, LI Chaoqun, WANG Shasha. Cost-sensitive Bayesian network classifiers[J]. Pattern Recognition Letters, 2014, 45(8):211-216.
[6] 李宁, 郭乔进, 谢俊元, 等. 基于Cascade结构的代价敏感的医学图像ROI检测方法[J]. 模式识别与人工智能, 2010, 23(2):228-234. LI Ning, GUO Qiaojin, XIE Junyuan, et al. Cost-sensitive ROI detection method for medical images based on cascade architecture[J]. Pattern Recognition and Artificial Intelligence, 2010, 23(2):228-234.
[7] LI Jingkuan, MIN Fan, ZHU William. Fast randomized algorithm for minimal test cost attribute reduction[J]. Proc ICRITO, 2013, 6:12-17.
[8] HE Huaping, MIN Fan. Accumulated cost based test-cost-sensitive attribute reduction[M]. Rough Sets, Fuzzy Sets, Data Mining and Granular Computing. Berlin: Springer, 2011: 244-247.
[9] 刘春英. 基于关联度的代价敏感决策树生成方法[J]. 长春工业大学学报(自然科学版), 2013, 34(2):218-222. LIU Chunying. A method of generating cost-sensitive decision tree based on correlation degree[J]. Journal of Changchun University of Technology(Natural Science Edition), 2013, 34(2):218-222.
[10] JIA Xiuyi, LIAO Wenhe, TANG Zhenmin, et al. Minimum cost attribute reduction in decision-theoretic rough set models[J]. Information Sciences an International Journal, 2013, 219(1):151-167.
[11] LIAO Shujiao, LIU Jiabin, MIN Fan, et al. Minimal-test-cost reduct problem on neighborhood decision systems[J]. Journal of Information & Computational Science, 2012, 9(14):4083-4098.
[12] ZHAO Hong, MIN Fan, ZHU William. Test-cost-sensitive attribute reduction based on neighborhood rough set[C]. IEEE International Conference on Granular Computing, 2011:802-806.
[13] MIN Fan, ZHU William. Attribute reduction on data with error ranges and test costs[J]. Information Sciences, 2012, 211:48-67.
[14] MIN Fan, ZHU William. Minimal cost attribute reduction through backtracking[J]. Communications in Computer & Information Science, 2011, 258:100-107.
[15] MIN Fan, HE Huaping, QIAN Yuhua, et al. Test-cost-sensitive attribute reduction[J]. Information Sciences, 2011, 181(22):4928-4942.
[16] PAN Guiying, MIN Fan, ZHU William. A genetic algorithm to the minimal test cost reduct problem[C]. IEEE International Conference on Granular Computing, 2011: 539-544.
[17] LIU Jiabin, MIN Fan, LIAO Shujiao, et al. Test cost constraint attribute reduction through a genetic approach[J]. Journal of Information & Computational Science, 2013, 10(3):839-849.
[18] XU Zilong, MIN Fan, LIU Jiabin, et al. Ant colony optimization to minimal test cost reduction[C]. IEEE International Conference on Granular Computing, 2012, 40(6):585-590.
[19] DERVIS K, AKAY B. A comparative study of artificial bee colony algorithm[J]. Applied Mathematics and Computation, 2009, 214(1):108-132.
[20] PINAR C, BESDOK E. A conceptual comparison of the cuckoo search, particle swarm optimization, differential evolution and artificial bee colony algorithms[J]. Artificial Intelligence Review, 2013, 39(4):315-346.
[1] HE Yi, SHAO Yabin, FENG Hui, GUO Ruilian. A classifier model based on the fast granular hypercube generation algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(5): 65-78.
[2] . Rotated granular support vector machine classifier algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(5): 102-113.
[3] . Fuzzy rough c-means based on the knowledge measure [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(1): 49-64.
[4] HUA Youlin, SHAO Yabin, ZHU Xueqin. Multi-granularity support vector regression algorithm based on granular ball computing [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(7): 104-115.
[5] WU Hai, NIU Jiaojiao, TIE Wenyan, ZUO Jiankun. Concept lattice construction method based on granular concept network [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(12): 21-31.
[6] CHEN Yumin, ZHENG Guangyu, JIAO Na. Multi-label learning based on granular neural networks [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(5): 1-11.
[7] ZHENG Chenying, CHEN Yingyue, HOU Xianyu, JIANG Lianji, LIAO Liang. A neighbourhood granular fuzzy C-means clustering algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(5): 35-44.
[8] SONG Suyang, YE Jun, ZENG Guangcai, SUN Qing. Multi-granularity rough set attribute reduction algorithm based on optimized discernibility matrix [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(5): 52-62.
[9] GAO Hefei, LI Yan, WANG Shuo. Feature selection for partial label learning based on neighborhood rough sets [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(5): 100-113.
[10] FANG Fengqi, WU Weizhi. Knowledge reduction in decision set-valued systems [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(5): 82-89.
[11] LIU Changshun, LIU Yan, SONG Jingjing, XU Taihua. Attribute reduction algorithm based on discreteness of the universe [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(5): 26-35.
[12] LUO Jun-li, QIAO Xi-min, WU Hong-bo. Structure and attribute reduction on non-commutative residual lattices 〈∈,∈Q〉-generalized fuzzy singular filter of interval-set [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(3): 49-57.
[13] ZHANG Jiao-jiao, ZHANG Shao-pu, FENG Tao. Dominance relationship and reduction of Pythagorean fuzzy systems [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(3): 96-110.
[14] Jie TANG,Ling WEI,Rui-si REN,Si-yu ZHAO. Granule description using possible attribute analysis [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(1): 75-82.
[15] LI Jin-hai, HE Jian-jun, WU Wei-zhi. Optimization of class-attribute block in multi-granularity formal concept analysis [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(5): 1-12.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd