Neighborhood decision tree construction algorithm based on variable-precision neighborhood equivalent granules

doi:10.11772/j.issn.1001-9081.2021071168

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (2): 382-388.DOI: 10.11772/j.issn.1001-9081.2021071168

Special Issue: 人工智能

• Artificial intelligence • Previous Articles Next Articles

Neighborhood decision tree construction algorithm based on variable-precision neighborhood equivalent granules

Xin XIE¹^,², Xianyong ZHANG¹^,²(), Xuanye WANG¹^,², Pengfei TANG¹^,²

^1.School of Mathematical Sciences，Sichuan Normal University，Chengdu Sichuan 610068，China
^2.Institute of Intelligent Information and Quantum Information，Sichuan Normal University，Chengdu Sichuan 610068，China

Received:2021-07-07 Revised:2021-08-09 Accepted:2021-08-10 Online:2022-02-11 Published:2022-02-10
Contact: Xianyong ZHANG
About author:XIE Xin， born in 1996， M. S. candidate. His research interests include uncertain machine learning.
ZHANG Xianyong， born in 1978， Ph. D.， professor. His research interests include uncertainty analysis， intelligent computing， machine learning.
WANG Xuanye， born in 1995， M. S. candidate. His research interests include uncertain machine learning.
TANG Pengfei， born in 1996， M. S. candidate. His research interests include rough set， granular computing.
Supported by:
National Natural Science Foundation of China(61673258);Sichuan Science and Technology Program(2021YJ0085)

变精度邻域等价粒的邻域决策树构造算法

谢鑫¹^,², 张贤勇¹^,²(), 王旋晔¹^,², 唐鹏飞¹^,²

^1.四川师范大学数学科学学院，成都 610068
^2.四川师范大学智能信息与量子信息研究所，成都 610068

通讯作者: 张贤勇
作者简介:谢鑫（1996—），男，四川资中人，硕士研究生，主要研究方向：不确定性机器学习；
张贤勇（1978—），男，四川宜宾人，教授，博士生导师，博士，主要研究方向：不确定性分析、智能计算、机器学习；
王旋晔（1995—），男，四川达州人，硕士研究生，主要研究方向：不确定性机器学习；
唐鹏飞（1996—），男，重庆人，硕士研究生，主要研究方向：粗糙集、粒计算。
基金资助:
国家自然科学基金资助项目(61673258);四川省科技计划项目(2021YJ0085)

Abstract

Abstract:

Aiming at the shortcomings such as information loss and poor effect of the existing decision tree algorithms for continuous data classification， a Neighborhood Decision Tree （NDT） construction algorithm was proposed. Firstly， the variable-precision neighborhood equivalent granules on the neighborhood decision information system were mined， and the related properties were discussed. Secondly， the neighborhood Gini index measure was constructed based on the variable-precision neighborhood equivalent granules to measure the uncertainty of the neighborhood decision information system. Finally， the neighborhood Gini index measure was used to induce the tree node selection conditions， and the variable-precision neighborhood equivalent granules were used as the tree splitting rules to construct NDT. Experimental results on UCI datasets show that the accuracy of NDT algorithm is generally improved by about 20 percentage points compared with those of Iterative Dichotomiser 3 （ID3） algorithm， Classification And Regression Tree （CART） algorithm， C4.5 algorithm and combining Information Gain and Gini Index （IGGI） algorithm， indicating that the proposed NDT algorithm is effective.

Key words: uncertainty measurement, Gini index, neighborhood decision information system, decision tree, machine learning

摘要：

针对现有决策树算法对连续性数据分类的信息丢失、效果不佳等缺点，提出一种邻域决策树（NDT）构造算法。首先，挖掘了邻域决策信息系统上的变精度邻域等价粒，并探讨了相关性质；然后基于变精度邻域等价粒构建邻域基尼指数度量，以度量邻域决策信息系统的不确定性；最后，用邻域基尼指数度量诱导出树节点的选取条件，并以变精度邻域等价粒为树分裂规则，从而构建NDT。在UCI数据集进行实验的结果表明，NDT算法的准确度比基于信息熵的决策树算法ID3、基于基尼指数的决策树算法CART、基于信息增益率的决策树（C4.5）算法和融合信息增益和基尼指数（IGGI）算法平均提高了20个百分点左右，验证了NDT算法的有效性。

关键词: 不确定性度量, 基尼指数, 邻域决策信息系统, 决策树, 机器学习

CLC Number:

TP18

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.

Figures/Tables 7

Tab. 1 Example decision table

$U$	$c 1$	$c 2$	$c 3$	$c 4$	$c 5$	$D$
$x 1$	0.8	1.0	0.7	0.5	0.4	1
$x 2$	0.9	0.8	0.6	0.5	0.9	1
$x 3$	0.6	1.0	0.4	0.8	1.0	2
$x 4$	1.0	0.4	0.8	0.7	0.5	1
$x 5$	0.7	0.6	0.3	0.2	0.4	1
$x 6$	0.5	0.2	0.1	0.9	0.3	2
$x 7$	0.9	0.3	0.7	0.5	0.6	2

Tab. 1 Example decision table

$U$	$c 1$	$c 2$	$c 3$	$c 4$	$c 5$	$D$
$x 1$	0.8	1.0	0.7	0.5	0.4	1
$x 2$	0.9	0.8	0.6	0.5	0.9	1
$x 3$	0.6	1.0	0.4	0.8	1.0	2
$x 4$	1.0	0.4	0.8	0.7	0.5	1
$x 5$	0.7	0.6	0.3	0.2	0.4	1
$x 6$	0.5	0.2	0.1	0.9	0.3	2
$x 7$	0.9	0.3	0.7	0.5	0.6	2

Tab. 2 Function values of two measures with δ=0.5 and β=0.7

度量	$c 1$	$c 2$	$c 3$	$c 4$	$c 5$
$N G (*)$	0.00	1.14	0.24	0.33	0.65
$N G (D, *)$	0.49	0.83	0.38	1.15	0.95

Tab. 2 Function values of two measures with δ=0.5 and β=0.7

度量	$c 1$	$c 2$	$c 3$	$c 4$	$c 5$
$N G (*)$	0.00	1.14	0.24	0.33	0.65
$N G (D, *)$	0.49	0.83	0.38	1.15	0.95

Tab. 3 Function values of four measures with δ=0 and β=1

度量	$c 1$	$c 2$	$c 3$	$c 4$	$c 5$
$N G (*)$	0.82	0.82	0.82	0.73	0.82
$N G (D, *)$	0.14	0.14	0.14	0.19	0.00
$G i n i (c)$	0.82	0.82	0.82	0.73	0.82
$G i n i (D, c)$	0.14	0.14	0.14	0.19	0.00

Tab. 3 Function values of four measures with δ=0 and β=1

度量	$c 1$	$c 2$	$c 3$	$c 4$	$c 5$
$N G (*)$	0.82	0.82	0.82	0.73	0.82
$N G (D, *)$	0.14	0.14	0.14	0.19	0.00
$G i n i (c)$	0.82	0.82	0.82	0.73	0.82
$G i n i (D, c)$	0.14	0.14	0.14	0.19	0.00

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

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

Fig. 1 Accuracy comparison of different algorithms

Fig. 2 Comparison of leaf number of different algorithms

References 19

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]	Xuebin CHEN, Zhiqiang REN, Hongyang ZHANG. Review on security threats and defense measures in federated learning [J]. Journal of Computer Applications, 2024, 44(6): 1663-1672.
[2]	Zihao YAO, Yuanming LI, Ziqiang MA, Yang LI, Lianggen WEI. Multi-object cache side-channel attack detection model based on machine learning [J]. Journal of Computer Applications, 2024, 44(6): 1862-1871.
[3]	Wei SHE, Yang LI, Lihong ZHONG, Defeng KONG, Zhao TIAN. Hyperparameter optimization for neural network based on improved real coding genetic algorithm [J]. Journal of Computer Applications, 2024, 44(3): 671-676.
[4]	Yi ZHENG, Cunyi LIAO, Tianqian ZHANG, Ji WANG, Shouyin LIU. Image denoising-based cell-level RSRP estimation method for urban areas [J]. Journal of Computer Applications, 2024, 44(3): 855-862.
[5]	Xuebin CHEN, Changsheng QU. Overview of backdoor attacks and defense in federated learning [J]. Journal of Computer Applications, 2024, 44(11): 3459-3469.
[6]	Renke SUN, Zhiyu HUANGFU, Hu CHEN, Zhongnian LI, Xinzheng XU. Survey of neural architecture search [J]. Journal of Computer Applications, 2024, 44(10): 2983-2994.
[7]	Wenze CHAI, Jing FAN, Shukui SUN, Yiming LIANG, Jingfeng LIU. Overview of deep metric learning [J]. Journal of Computer Applications, 2024, 44(10): 2995-3010.
[8]	Chunyong YIN, Yongcheng ZHOU. Automatically adjusted clustered federated learning for double-ended clustering [J]. Journal of Computer Applications, 2024, 44(10): 3011-3020.
[9]	Haoyang CUI, Hui ZHANG, Lei ZHOU, Chunming YANG, Bo LI, Xujian ZHAO. Multi-similarity K-nearest neighbor classification algorithm with ordered pairs of normalized real numbers [J]. Journal of Computer Applications, 2023, 43(9): 2673-2678.
[10]	Jing ZHONG, Chen LIN, Zhiwei SHENG, Shibin ZHANG. Quantum K-Means algorithm based on Hamming distance [J]. Journal of Computer Applications, 2023, 43(8): 2493-2498.
[11]	Mengjie LAN, Jianping CAI, Lan SUN. Self-regularization optimization methods for Non-IID data in federated learning [J]. Journal of Computer Applications, 2023, 43(7): 2073-2081.
[12]	Xiaohui HUANG, Kaiming YANG, Jiahao LING. Order dispatching by multi-agent reinforcement learning based on shared attention [J]. Journal of Computer Applications, 2023, 43(5): 1620-1624.
[13]	Shaochen HAO, Zizuan WEI, Yao MA, Dan YU, Yongle CHEN. Network intrusion detection model based on efficient federated learning algorithm [J]. Journal of Computer Applications, 2023, 43(4): 1169-1175.
[14]	Xiaofei SUN, Jingyuan ZHU, Bin CHEN, Hengzhi YOU. Virtual screening of drug synthesis reaction based on multimodal data fusion [J]. Journal of Computer Applications, 2023, 43(2): 622-629.
[15]	Junpeng ZHANG, Yujie SHI, Rui JANG, Jingjing DONG, Changjian QIU. Review on advances in recognition and classification of cognitive impairment based on EEG signals [J]. Journal of Computer Applications, 2023, 43(10): 3297-3308.

Neighborhood decision tree construction algorithm based on variable-precision neighborhood equivalent granules

变精度邻域等价粒的邻域决策树构造算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 19

Related Articles 15

Recommended Articles

Metrics