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

doi:10.11772/j.issn.1001-9081.2021071168

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (2): 382-388.DOI: 10.11772/j.issn.1001-9081.2021071168

• 人工智能 • 上一篇

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

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

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

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

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

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP18

谢鑫, 张贤勇, 王旋晔, 唐鹏飞. 变精度邻域等价粒的邻域决策树构造算法[J]. 计算机应用, 2022, 42(2): 382-388.

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.

图/表 7

表1 实例决策表

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

表1 实例决策表

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

表2 δ=0.5、β=0.7时两种度量的函数值

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

表2 δ=0.5、β=0.7时两种度量的函数值

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

表3 δ=0、β=1时四种度量的函数值

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

表3 δ=0、β=1时四种度量的函数值

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

表4 UCI 数据集

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

表5 不同决策树算法的实验结果对比

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 不同算法的准确度对比

Fig. 1 Accuracy comparison of different algorithms

图2 不同算法的叶子数对比

Fig. 2 Comparison of leaf number of different algorithms

参考文献 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]	李艳, 郭劼, 范斌. 元学习的不确定性特征构建及初步分析[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 343-348.
[2]	毛铭泽, 曹芮浩, 闫春钢. 基于权值多样性的半监督分类算法[J]. 计算机应用, 2021, 41(9): 2473-2480.
[3]	郭棉, 张锦友. 移动边缘计算环境中面向机器学习的计算迁移策略[J]. 计算机应用, 2021, 41(9): 2639-2645.
[4]	秦斌斌, 彭良康, 卢向明, 钱江波. 司机分心驾驶检测研究进展[J]. 计算机应用, 2021, 41(8): 2330-2337.
[5]	秦静, 左长青, 汪祖民, 季长清, 王宝凤. 基于堆叠分类器的心电异常监测模型设计[J]. 计算机应用, 2021, 41(3): 887-890.
[6]	姜倩玉, 王凤英, 贾立鹏. 基于感知哈希算法和特征融合的恶意代码检测方法[J]. 计算机应用, 2021, 41(3): 780-785.
[7]	孟祥瑞, 杨文忠, 王婷. 基于图文融合的情感分析研究综述[J]. 《计算机应用》唯一官方网站, 2021, 41(2): 307-317.
[8]	王梅, 许传海, 刘勇. 基于神经正切核的多核学习方法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3462-3467.
[9]	成科扬, 孟春运, 王文杉, 师文喜, 詹永照. 解耦表征学习研究进展[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3409-3418.
[10]	刘晓龙, 王士同. 渐进式分离的开放集模糊域自适应算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3127-3131.
[11]	楼豪杰, 郑元林, 廖开阳, 雷浩, 李佳. 基于Siamese-YOLOv4的印刷品缺陷目标检测[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3206-3212.
[12]	王雅辉, 钱宇华, 刘郭庆. 基于模糊优势互补互信息的有序决策树算法[J]. 计算机应用, 2021, 41(10): 2785-2792.
[13]	蒋阳升, 王胜男, 涂家祺, 李莎, 王红军. 面向高铁站的热舒适度和能耗综合预测[J]. 计算机应用, 2021, 41(1): 249-257.
[14]	周翔, 翟俊海, 黄雅婕, 申瑞彩, 侯璎真. 基于随机森林和投票机制的大数据样例选择算法[J]. 计算机应用, 2021, 41(1): 74-80.
[15]	朱琳, 于海涛, 雷新宇, 刘静, 王若凡. 基于MRI图像的阿尔茨海默症患者脑网络特征识别算法[J]. 计算机应用, 2020, 40(8): 2455-2459.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 19

相关文章 15

编辑推荐

Metrics