Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (2): 382-388.DOI: 10.11772/j.issn.1001-9081.2021071168
• Artificial intelligence • Previous Articles
Xin XIE1,2, Xianyong ZHANG1,2(), Xuanye WANG1,2, Pengfei TANG1,2
Received:
2021-07-07
Revised:
2021-08-09
Accepted:
2021-08-10
Online:
2021-08-09
Published:
2022-02-10
Contact:
Xianyong ZHANG
About author:
XIE Xin, born in 1996, M. S. candidate. His research interests include uncertain machine learning.Supported by:
谢鑫1,2, 张贤勇1,2(), 王旋晔1,2, 唐鹏飞1,2
通讯作者:
张贤勇
作者简介:
谢鑫(1996—),男,四川资中人,硕士研究生,主要研究方向:不确定性机器学习;基金资助:
CLC Number:
Xin XIE, Xianyong ZHANG, Xuanye WANG, Pengfei TANG. Neighborhood decision tree construction algorithm based on variable-precision neighborhood equivalent granules[J]. Journal of Computer Applications, 2022, 42(2): 382-388.
谢鑫, 张贤勇, 王旋晔, 唐鹏飞. 变精度邻域等价粒的邻域决策树构造算法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 382-388.
Add to citation manager EndNote|Ris|BibTeX
URL: http://www.joca.cn/EN/10.11772/j.issn.1001-9081.2021071168
0.8 | 1.0 | 0.7 | 0.5 | 0.4 | 1 | |
0.9 | 0.8 | 0.6 | 0.5 | 0.9 | 1 | |
0.6 | 1.0 | 0.4 | 0.8 | 1.0 | 2 | |
1.0 | 0.4 | 0.8 | 0.7 | 0.5 | 1 | |
0.7 | 0.6 | 0.3 | 0.2 | 0.4 | 1 | |
0.5 | 0.2 | 0.1 | 0.9 | 0.3 | 2 | |
0.9 | 0.3 | 0.7 | 0.5 | 0.6 | 2 |
Tab. 1 Example decision table
0.8 | 1.0 | 0.7 | 0.5 | 0.4 | 1 | |
0.9 | 0.8 | 0.6 | 0.5 | 0.9 | 1 | |
0.6 | 1.0 | 0.4 | 0.8 | 1.0 | 2 | |
1.0 | 0.4 | 0.8 | 0.7 | 0.5 | 1 | |
0.7 | 0.6 | 0.3 | 0.2 | 0.4 | 1 | |
0.5 | 0.2 | 0.1 | 0.9 | 0.3 | 2 | |
0.9 | 0.3 | 0.7 | 0.5 | 0.6 | 2 |
度量 | |||||
---|---|---|---|---|---|
0.00 | 1.14 | 0.24 | 0.33 | 0.65 | |
0.49 | 0.83 | 0.38 | 1.15 | 0.95 |
Tab. 2 Function values of two measures with δ=0.5 and β=0.7
度量 | |||||
---|---|---|---|---|---|
0.00 | 1.14 | 0.24 | 0.33 | 0.65 | |
0.49 | 0.83 | 0.38 | 1.15 | 0.95 |
度量 | |||||
---|---|---|---|---|---|
0.82 | 0.82 | 0.82 | 0.73 | 0.82 | |
0.14 | 0.14 | 0.14 | 0.19 | 0.00 | |
0.82 | 0.82 | 0.82 | 0.73 | 0.82 | |
0.14 | 0.14 | 0.14 | 0.19 | 0.00 |
Tab. 3 Function values of four measures with δ=0 and β=1
度量 | |||||
---|---|---|---|---|---|
0.82 | 0.82 | 0.82 | 0.73 | 0.82 | |
0.14 | 0.14 | 0.14 | 0.19 | 0.00 | |
0.82 | 0.82 | 0.82 | 0.73 | 0.82 | |
0.14 | 0.14 | 0.14 | 0.19 | 0.00 |
数据集 | 样本数 | 条件属性数 | 类数 |
---|---|---|---|
Crayo | 90 | 6 | 2 |
Iris | 150 | 4 | 3 |
wine | 178 | 13 | 3 |
plrx | 182 | 18 | 1 |
wpbc | 194 | 33 | 2 |
seg | 210 | 19 | 7 |
seeds | 210 | 7 | 3 |
glass | 214 | 10 | 6 |
heart | 270 | 13 | 2 |
ecoli | 336 | 7 | 7 |
ionosphere | 351 | 34 | 2 |
ILPD | 583 | 10 | 2 |
segment | 2 310 | 19 | 7 |
Tab. 4 UCI datasets
数据集 | 样本数 | 条件属性数 | 类数 |
---|---|---|---|
Crayo | 90 | 6 | 2 |
Iris | 150 | 4 | 3 |
wine | 178 | 13 | 3 |
plrx | 182 | 18 | 1 |
wpbc | 194 | 33 | 2 |
seg | 210 | 19 | 7 |
seeds | 210 | 7 | 3 |
glass | 214 | 10 | 6 |
heart | 270 | 13 | 2 |
ecoli | 336 | 7 | 7 |
ionosphere | 351 | 34 | 2 |
ILPD | 583 | 10 | 2 |
segment | 2 310 | 19 | 7 |
数据集 | 算法 | 准确度 | 叶子数 | 数据集 | 算法 | 准确度 | 叶子数 |
---|---|---|---|---|---|---|---|
Crayo | ID3 | 0.833 3 | 32.0 | glass | ID3 | 0.500 0 | 152.0 |
CART | 0.666 7 | 71.5 | CART | 0.500 0 | 143.5 | ||
C4.5 | 0.888 9 | 33.0 | C4.5 | 0.500 0 | 127.5 | ||
IGGI | 0.833 3 | 45.0 | IGGI | 0.522 7 | 175.5 | ||
NDT | 0.966 7 | 70.0 | NDT | 0.962 6 | 394.0 | ||
Iris | ID3 | 0.900 0 | 27.5 | heart | ID3 | 0.648 1 | 137.5 |
CART | 0.933 3 | 39.0 | CART | 0.592 6 | 266.0 | ||
C4.5 | 0.900 0 | 24.5 | C4.5 | 0.592 6 | 122.5 | ||
IGGI | 0.966 7 | 34.5 | IGGI | 0.648 1 | 147.0 | ||
NDT | 0.986 7 | 53.0 | NDT | 0.648 1 | 263.0 | ||
wine | ID3 | 0.861 1 | 30.5 | ecoli | ID3 | 0.794 1 | 176.5 |
CART | 0.638 9 | 155.0 | CART | 0.720 6 | 198.5 | ||
C4.5 | 0.944 4 | 37.5 | C4.5 | 0.691 2 | 158.0 | ||
IGGI | 0.861 1 | 64.5 | IGGI | 0.588 2 | 221.0 | ||
NDT | 1.000 0 | 213.0 | NDT | 0.907 7 | 573.0 | ||
plrx | ID3 | 0.473 7 | 115.0 | ionosphere | ID3 | 0.902 8 | 86.0 |
CART | 0.315 8 | 251.5 | CART | 0.902 8 | 146.5 | ||
C4.5 | 0.526 3 | 118.5 | C4.5 | 0.833 3 | 85.0 | ||
IGGI | 0.526 3 | 124.5 | IGGI | 0.861 1 | 98.5 | ||
NDT | 0.632 5 | 245.0 | NDT | 0.994 3 | 267.0 | ||
wpbc | ID3 | 0.700 0 | 88.0 | ILPD | ID3 | 0.703 4 | 410.5 |
CART | 0.500 0 | 387.5 | CART | 0.618 6 | 229.0 | ||
C4.5 | 0.425 0 | 86.5 | C4.5 | 0.652 5 | 280.0 | ||
IGGI | 0.700 0 | 108.5 | IGGI | 0.576 3 | 517.0 | ||
NDT | 0.986 7 | 266.0 | NDT | 0.994 9 | 669.0 | ||
seg | ID3 | 0.809 5 | 110.0 | segment | ID3 | 0.924 2 | 680.0 |
CART | 0.666 7 | 184.0 | CART | 0.889 6 | 830.5 | ||
C4.5 | 0.761 9 | 103.5 | C4.5 | 0.928 6 | 629.5 | ||
IGGI | 0.785 7 | 100.5 | IGGI | 0.937 2 | 516.0 | ||
NDT | 0.921 5 | 257.0 | NDT | 0.963 1 | 901.0 | ||
seeds | ID3 | 0.881 0 | 62.5 | 算术平均 | ID3 | 0.763 9 | 162.15 |
CART | 0.928 6 | 91.5 | CART | 0.682 6 | 230.31 | ||
C4.5 | 0.928 6 | 64.5 | C4.5 | 0.736 4 | 143.88 | ||
IGGI | 0.881 0 | 69.5 | IGGI | 0.745 2 | 170.92 | ||
NDT | 0.928 6 | 72.0 | NDT | 0.914 9 | 326.38 |
Tab. 5 Comparison of experimental results of different decision tree algorithms
数据集 | 算法 | 准确度 | 叶子数 | 数据集 | 算法 | 准确度 | 叶子数 |
---|---|---|---|---|---|---|---|
Crayo | ID3 | 0.833 3 | 32.0 | glass | ID3 | 0.500 0 | 152.0 |
CART | 0.666 7 | 71.5 | CART | 0.500 0 | 143.5 | ||
C4.5 | 0.888 9 | 33.0 | C4.5 | 0.500 0 | 127.5 | ||
IGGI | 0.833 3 | 45.0 | IGGI | 0.522 7 | 175.5 | ||
NDT | 0.966 7 | 70.0 | NDT | 0.962 6 | 394.0 | ||
Iris | ID3 | 0.900 0 | 27.5 | heart | ID3 | 0.648 1 | 137.5 |
CART | 0.933 3 | 39.0 | CART | 0.592 6 | 266.0 | ||
C4.5 | 0.900 0 | 24.5 | C4.5 | 0.592 6 | 122.5 | ||
IGGI | 0.966 7 | 34.5 | IGGI | 0.648 1 | 147.0 | ||
NDT | 0.986 7 | 53.0 | NDT | 0.648 1 | 263.0 | ||
wine | ID3 | 0.861 1 | 30.5 | ecoli | ID3 | 0.794 1 | 176.5 |
CART | 0.638 9 | 155.0 | CART | 0.720 6 | 198.5 | ||
C4.5 | 0.944 4 | 37.5 | C4.5 | 0.691 2 | 158.0 | ||
IGGI | 0.861 1 | 64.5 | IGGI | 0.588 2 | 221.0 | ||
NDT | 1.000 0 | 213.0 | NDT | 0.907 7 | 573.0 | ||
plrx | ID3 | 0.473 7 | 115.0 | ionosphere | ID3 | 0.902 8 | 86.0 |
CART | 0.315 8 | 251.5 | CART | 0.902 8 | 146.5 | ||
C4.5 | 0.526 3 | 118.5 | C4.5 | 0.833 3 | 85.0 | ||
IGGI | 0.526 3 | 124.5 | IGGI | 0.861 1 | 98.5 | ||
NDT | 0.632 5 | 245.0 | NDT | 0.994 3 | 267.0 | ||
wpbc | ID3 | 0.700 0 | 88.0 | ILPD | ID3 | 0.703 4 | 410.5 |
CART | 0.500 0 | 387.5 | CART | 0.618 6 | 229.0 | ||
C4.5 | 0.425 0 | 86.5 | C4.5 | 0.652 5 | 280.0 | ||
IGGI | 0.700 0 | 108.5 | IGGI | 0.576 3 | 517.0 | ||
NDT | 0.986 7 | 266.0 | NDT | 0.994 9 | 669.0 | ||
seg | ID3 | 0.809 5 | 110.0 | segment | ID3 | 0.924 2 | 680.0 |
CART | 0.666 7 | 184.0 | CART | 0.889 6 | 830.5 | ||
C4.5 | 0.761 9 | 103.5 | C4.5 | 0.928 6 | 629.5 | ||
IGGI | 0.785 7 | 100.5 | IGGI | 0.937 2 | 516.0 | ||
NDT | 0.921 5 | 257.0 | NDT | 0.963 1 | 901.0 | ||
seeds | ID3 | 0.881 0 | 62.5 | 算术平均 | ID3 | 0.763 9 | 162.15 |
CART | 0.928 6 | 91.5 | CART | 0.682 6 | 230.31 | ||
C4.5 | 0.928 6 | 64.5 | C4.5 | 0.736 4 | 143.88 | ||
IGGI | 0.881 0 | 69.5 | IGGI | 0.745 2 | 170.92 | ||
NDT | 0.928 6 | 72.0 | NDT | 0.914 9 | 326.38 |
1 | PAWLAK Z. Rough sets[J]. International Journal of Computer and Information Sciences, 1982, 11(5): 341-356. 10.1007/bf01001956 |
2 | QIAN W B, HUANG J T, WANG Y L, et al. Label distribution feature selection for multi-label classification with rough set[J]. International Journal of Approximate Reasoning, 2021, 128: 32-55. 10.1016/j.ijar.2020.10.002 |
3 | JIAO L, YANG H L, LI S G. Three-way decision based on decision-theoretic rough sets with single-valued neutrosophic information[J]. International Journal of Machine Learning and Cybernetics, 2020, 11(3): 657-665. 10.1007/s13042-019-01023-3 |
4 | ZHANG K, ZHAN J M, WU W Z. Novel fuzzy rough set models and corresponding applications to multi-criteria decision-making[J]. Fuzzy Sets and Systems, 2020, 383: 92-126. 10.1016/j.fss.2019.06.019 |
5 | YAO Y Y. Three-way granular computing, rough sets, and formal concept analysis[J]. International Journal of Approximate Reasoning, 2020, 116: 106-125. 10.1016/j.ijar.2019.11.002 |
6 | WANG H. Nearest neighbors by neighborhood counting[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(6): 942-953. 10.1109/tpami.2006.126 |
7 | 樊雲瑞,张贤勇,杨霁琳.模糊邻域粗糙集的决策熵不确定性度量[J].计算机工程与设计, 2021, 42(5): 1300-1306. 10.1016/j.patrec.2021.03.001 |
FAN Y R, ZHANG X Y, YANG J L. Uncertainty measurement of decision-entropies based on fuzzy neighborhood rough sets[J]. Computer Engineering and Design, 2021, 42(5): 1300-1306. 10.1016/j.patrec.2021.03.001 | |
8 | JIANG F, SUI Y F, ZHOU L. A relative decision entropy-based feature selection approach[J]. Pattern Recognition, 2015, 48(7): 2151-2163. 10.1016/j.patcog.2015.01.023 |
9 | 马立川,彭佳怡,裴庆祺,等.一种高效的决策树隐私分类服务协议[J].通信学报, 2021, 42(8): 80-89. |
MA L C, PENG J Y, PEI Q Q, et al. Efficient privacy-preserving decision tree classification protocol[J]. Journal on Communications, 2021, 42(8): 80-89. | |
10 | 杨小娟.决策树算法在学生课程成绩分析中的应用研究[D].昆明:云南师范大学, 2021: 51-60. 10.21127/yaoyimr20210003 |
YANG X J. Research on the application of decision tree algorithm in the analysis of students’ course performance[D]. Kunming: Yunnan Normal University, 2021: 51-60. 10.21127/yaoyimr20210003 | |
11 | 金庞,周波,王国民,等.决策树模型及logistic回归模型对精神分裂症患者自杀的影响因素分析[J].中国卫生统计, 2021, 38(3): 442-445. 10.3969/j.issn.1002-3674.2021.03.033 |
JIN P, ZHOU B, WANG G M, et al. Analysis of influencing factors of suicide by decision tree model and logistic regression model in patients with schizophrenia[J]. Chinese Journal of Health Statistics, 2021, 38(3): 442-445. 10.3969/j.issn.1002-3674.2021.03.033 | |
12 | 唐亮,李飞.基于决策树的车联网安全态势预测模型研究[J].计算机科学, 2021, 48(S1): 514-517. 10.11896/jsjkx.200700158 |
TANG L, LI F. Research on forecasting model of internet of vehicles security situation based on decision tree[J]. Computer Science, 2021, 48(S1): 514-517. 10.11896/jsjkx.200700158 | |
13 | 高虹雷,门昌骞,王文剑.一种特征值区间划分的模型决策树加速算法[J].小型微型计算机系统, 2021, 42(6): 1136-1143. 10.3969/j.issn.1000-1220.2021.06.003 |
GAO H L, MEN C Q, WANG W J. Acceleration algorithm of model decision tree with feature value interval partition[J]. Journal of Chinese Computer Systems, 2021, 42(6): 1136-1143. 10.3969/j.issn.1000-1220.2021.06.003 | |
14 | BREIMAN L, FRIEDMAN J H, OLSHEN R A, et al. Classification and Regression Trees[M]. Boca Raton: Routledge, 1984: 358. 10.2307/2530946 |
15 | QUINLAN J R. Induction of decision trees[J]. Machine Learning, 1986, 1(1): 81-106. 10.1007/bf00116251 |
16 | QUINLAN J R. C4.5: Programs for Machine Learning[M]. San Francisco: Morgan Kaufmann, 1993: 11-30. |
17 | 谢鑫,张贤勇,杨霁琳.融合信息增益与基尼指数的决策树算法[J/OL].计算机工程与应用. (2021-04-19) [2021-05-09]. , |
ZHANG X Y, YANG J L. Decision tree algorithm fusing information gain and Gini index[J/OL]. Computer Engineering and Applications. (2021-04-19) [2021-05-09]. | |
18 | DUA D, GRAFF C. UCI machine learning repository[DS/OL]. [2021-05-10]. . |
19 | BENOÎT G. Data discretization for novel relationship discovery in information retrieval[J]. Journal of the American Society for Information Science and Technology, 2002, 53(9): 736-746. 10.1002/asi.10079 |
[1] | MAO Mingze, CAO Ruihao, YAN Chungang. Semi-supervised classification algorithm based on weight diversity [J]. Journal of Computer Applications, 2021, 41(9): 2473-2480. |
[2] | GUO Mian, ZHANG Jinyou. Computation offloading policy for machine learning in mobile edge computing environments [J]. Journal of Computer Applications, 2021, 41(9): 2639-2645. |
[3] | QIN Binbin, PENG Liangkang, LU Xiangming, QIAN Jiangbo. Research progress on driver distracted driving detection [J]. Journal of Computer Applications, 2021, 41(8): 2330-2337. |
[4] | JIANG Qianyu, WANG Fengying, JIA Lipeng. Malware detection method based on perceptual hash algorithm and feature fusion [J]. Journal of Computer Applications, 2021, 41(3): 780-785. |
[5] | QIN Jing, ZUO Changqing, WANG Zumin, JI Changqing, WANG Baofeng. Design of abnormal electrocardiograph monitoring model based on stacking classifier [J]. Journal of Computer Applications, 2021, 41(3): 887-890. |
[6] | MENG Xiangrui, YANG Wenzhong, WANG Ting. Survey of sentiment analysis based on image and text fusion [J]. Journal of Computer Applications, 2021, 41(2): 307-317. |
[7] | Mei WANG, Chuanhai XU, Yong LIU. Multi-kernel learning method based on neural tangent kernel [J]. Journal of Computer Applications, 2021, 41(12): 3462-3467. |
[8] | Keyang CHENG, Chunyun MENG, Wenshan WANG, Wenxi SHI, Yongzhao ZHAN. Research advances in disentangled representation learning [J]. Journal of Computer Applications, 2021, 41(12): 3409-3418. |
[9] | Xiaolong LIU, Shitong WANG. Open set fuzzy domain adaptation algorithm via progressive separation [J]. Journal of Computer Applications, 2021, 41(11): 3127-3131. |
[10] | Haojie LOU, Yuanlin ZHENG, Kaiyang LIAO, Hao LEI, Jia LI. Defect target detection for printed matter based on Siamese-YOLOv4 [J]. Journal of Computer Applications, 2021, 41(11): 3206-3212. |
[11] | WANG Yahui, QIAN Yuhua, LIU Guoqing. Ordinal decision tree algorithm based on fuzzy advantage complementary mutual information [J]. Journal of Computer Applications, 2021, 41(10): 2785-2792. |
[12] | ZHOU Xiang, ZHAI Junhai, HUANG Yajie, SHEN Ruicai, HOU Yingzhen. Instance selection algorithm for big data based on random forest and voting mechanism [J]. Journal of Computer Applications, 2021, 41(1): 74-80. |
[13] | JIANG Yangsheng, WANG Shengnan, TU Jiaqi, LI Sha, WANG Hongjun. Comprehensive prediction of thermal comfort and energy consumption for high-speed railway stations [J]. Journal of Computer Applications, 2021, 41(1): 249-257. |
[14] | ZHU Lin, YU Haitao, LEI Xinyu, LIU Jing, WANG Ruofan. Brain network feature identification algorithm for Alzheimer's patients based on MRI image [J]. Journal of Computer Applications, 2020, 40(8): 2455-2459. |
[15] | LIANG Denggao, ZHOU Anmin, ZHENG Rongfeng, LIU Liang, DING Jianwei. WeChat payment behavior recognition model based on division of large and small burst blocks [J]. Journal of Computer Applications, 2020, 40(7): 1970-1976. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||