基于不确定性与错误分类率博弈的序贯三支决策模型

doi:10.12263/DZXB.20210382

电子学报 ›› 2022, Vol. 50 ›› Issue (5): 1033-1041.DOI: 10.12263/DZXB.20210382

基于不确定性与错误分类率博弈的序贯三支决策模型

张清华, 黄志康, 高满, 艾志华

重庆邮电大学计算智能重庆市重点实验室，重庆 400065

收稿日期:2021-03-22 修回日期:2021-07-09 出版日期:2022-05-25
- 作者简介:
- 张清华男,1974年11月出生于重庆市.教授、博士生导师.现为重庆邮电大学科技处处长、先进技术研究院院长.主要从事粗糙集、模糊集、粒计算、不确定信息处理等相关研究.zhangqh@cqupt.edu.cn
  黄志康男,1994年4月出生于湖北省天门市.重庆邮电大学计算机科学与技术学院硕士.主要从事三支决策、粗糙集、粒计算等相关研究.1640565930@qq.com
  高满男,1994年11月出生于河南省南阳市.重庆邮电大学计算机科学与技术学院博士.主要从事粒计算、三支决策等相关研究.gaomandaner@qq.com
  艾志华男,1997年4月出生于江西省鹰潭市.重庆邮电大学计算机科学与技术学院硕士.主要从事粗糙集、三支决策等相关研究.1321724163@qq.com
- 基金资助:
- 国家重点研发计划课题 (2020YFC2003502); 国家自然科学基金 (61876201)

Sequential Three-Way Decision Model Based on the Game Between Uncertainty and Error Classification Rate

ZHANG Qing-hua, HUANG Zhi-kang, GAO Man, AI Zhi-hua

Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

Received:2021-03-22 Revised:2021-07-09 Online:2022-05-25 Published:2022-06-18
- Supported by:
- Subject of National Key Research and Development Program of China (2020YFC2003502); National Natural Science Foundation of China (61876201)

摘要/Abstract

摘要：

在实际分类决策中，序贯三支决策模型为决策者提供了一个渐进式的决策方法.然而，现有序贯三支决策模型的研究从提高分类精度或减少不确定性的动机来求取每一粒层的决策阈值，缺乏对二者的综合考虑.为了解决这个问题，本文结合博弈论的思想构建了基于错误分类率与边界域不确定性博弈的序贯三支决策模型.首先，分析了序贯三支决策模型中边界域不确定性与决策区域错误分类率的变化关系并构建了二者之间的博弈；其次，从博弈终止的条件出发，基于纯策略纳什均衡原理，提出了求取每一粒层自适应决策阈值的优化模型；再次，为了比较不同模型的效果，从多目标决策的角度，设计了基于TOPSIS（Technique for Order Preference by Similarity to an Ideal Solution）的阈值选取方法；最后，通过UCI数据集进行了两种模型的对比实验.实验结果表明：基于博弈论的序贯三支决策模型求取的决策阈值具有更小的错误分类率以及更合理的阈值结构.

关键词: 序贯三支决策, 博弈论, 纯策略纳什均衡, 多目标决策, 决策阈值, 不确定性

Abstract:

In actual classification decision, sequential three-way decision model provides decision-makers with a progressive decision-making method. However, the existing researches of the sequential three-way decision obtain the decision thresholds of each granularity layer motivated from improving classification accuracy or reducing uncertainty, which lacks a comprehensive consideration of the two factors. In order to solve this problem, this paper concerning the idea of game theory to construct a game-theoretic sequential three-way decision model between the error classification rate of decision regions and the uncertainty of the boundary region. Firstly, the relationship between the uncertainty of the boundary region and the error classification rate of the decision regions is analyzed, and then the game of the two players is constructed. Secondly, starting from the game stopping condition, an optimization model for calculating the adaptive decision thresholds of each granularity layer is designed based on the principle of pure strategy Nash equilibrium. Furthermore, to compare the performance of different models, from the perspective of multi-objective decision-making, another thresholds selection approach based on the TOPSIS(Technique for Order Preference by Similarity to an Ideal Solution) is designed. Finally, a comparative experiment of the two models was conducted through the UCI data sets. The experimental results show that the decision thresholds obtained by the game-theoretic sequential three-way decision model have a smaller error classification rate and a more reasonable threshold structure than multi-objective decision-making.

Key words: sequential three-way decisions, game theory, pure strategy Nash equilibrium, multi-objective decision, decision threshold, uncertainty

中图分类号:

TP18

张清华, 黄志康, 高满, 艾志华. 基于不确定性与错误分类率博弈的序贯三支决策模型[J]. 电子学报, 2022, 50(5): 1033-1041.

ZHANG Qing-hua, HUANG Zhi-kang, GAO Man, AI Zhi-hua. Sequential Three-Way Decision Model Based on the Game Between Uncertainty and Error Classification Rate[J]. Acta Electronica Sinica, 2022, 50(5): 1033-1041.

图/表 7

表1 ECRtotali和H(BNDi(X))随阈值改变而变化的趋势

	$E C R P O S i$	$E C R N E G i$	$E C R t o t a l i$	$H (B N D i (X))$
$α ↑$	$↓$	$→$	$↓$	$↑$
$β ↓$	$→$	$↓$	$↓$	$↑$
$α ↓$	$↑$	$→$	$↑$	$↓$
$β ↑$	$→$	$↑$	$↑$	$↓$

表1 ECRtotali和H(BNDi(X))随阈值改变而变化的趋势

	$E C R P O S i$	$E C R N E G i$	$E C R t o t a l i$	$H (B N D i (X))$
$α ↑$	$↓$	$→$	$↓$	$↑$
$β ↓$	$→$	$↓$	$↓$	$↑$
$α ↓$	$↑$	$→$	$↑$	$↓$
$β ↑$	$→$	$↑$	$↑$	$↓$

图1 不同策略下总收益示意图

表2 不同策略组合下错误分类率与不确定性博弈的收益表

		$H$
		$β$	$β + c H$	$β + 2 c H$	…	$β + k c H$
$E$	$α$	$< P E (α, β),$ $P H (α, β) >$	$< P E (α, β + c H), P H (α, β + c H) >$	$< P E (α, β + 2 c H), P H (α, β + 2 c H) >$	…	$< P E (α, β + k c H), P H (α, β + k c H) >$
	$α - c E$	$< P E (α - c E, β), P H (α - c E, β) >$	$< P E (α - c E, β + c H), P H (α - c E, β + c H) >$	$< P E (α - c E, β + 2 c H), P H (α - c E, β + 2 c H) >$	…	$< P E (α - c E, β + k c H), P H (α - c E, β + k c H) >$
	$α - 2 c E$	$< P E (α - 2 c E, β), P H (α - 2 c E, β) >$	$< P E (α - 2 c E, β + c H), P H (α - 2 c E, β + c H) >$	$< P E (α - 2 c E, β + 2 c H), P H (α - 2 c E, β + 2 c H) >$	…	$< P E (α - 2 c E, β + k c H), P H (α - 2 c E, β + k c H) >$
	…	…	…	…	…	…
	$α - j c E$	$< P E (α - j c E, β), P H (α - j c E, β) >$	$< P E (α - j c E, β + c H), P H (α - j c E, β + c H) >$	$< P E (α - j c E, β + 2 c H), P H (α - j c E, β + 2 c H) >$	…	$< P E (α - j c E, β + k c H), P H (α - j c E, β + k c H) >$

表2 不同策略组合下错误分类率与不确定性博弈的收益表

		$H$
		$β$	$β + c H$	$β + 2 c H$	…	$β + k c H$
$E$	$α$	$< P E (α, β),$ $P H (α, β) >$	$< P E (α, β + c H), P H (α, β + c H) >$	$< P E (α, β + 2 c H), P H (α, β + 2 c H) >$	…	$< P E (α, β + k c H), P H (α, β + k c H) >$
	$α - c E$	$< P E (α - c E, β), P H (α - c E, β) >$	$< P E (α - c E, β + c H), P H (α - c E, β + c H) >$	$< P E (α - c E, β + 2 c H), P H (α - c E, β + 2 c H) >$	…	$< P E (α - c E, β + k c H), P H (α - c E, β + k c H) >$
	$α - 2 c E$	$< P E (α - 2 c E, β), P H (α - 2 c E, β) >$	$< P E (α - 2 c E, β + c H), P H (α - 2 c E, β + c H) >$	$< P E (α - 2 c E, β + 2 c H), P H (α - 2 c E, β + 2 c H) >$	…	$< P E (α - 2 c E, β + k c H), P H (α - 2 c E, β + k c H) >$
	…	…	…	…	…	…
	$α - j c E$	$< P E (α - j c E, β), P H (α - j c E, β) >$	$< P E (α - j c E, β + c H), P H (α - j c E, β + c H) >$	$< P E (α - j c E, β + 2 c H), P H (α - j c E, β + 2 c H) >$	…	$< P E (α - j c E, β + k c H), P H (α - j c E, β + k c H) >$

表3 WIL每一粒层的决策阈值对实验结果(α,β)

层数	0.01		0.05		0.1
层数	博弈论	多目标	博弈论	多目标	博弈论	多目标
1	（0.88，0.12）	（0.62，0.38）	（0.9，0.1）	（0.6，0.4）	（0.7，0.3）	（0.6，0.4）
2	（0.85，0.15）	-	（0.75，0.25）	-	（0.8，0.2）	-
3	（0.67，0.33）	-	（0.7，0.3）	-	（0.7，0.3）	-
4	（0.51，0.49）	-	（0.55，0.45）	-	（0.6，0.4）	-
5	（0.51，0.49）	-	（0.55，0.45）	-	（0.6，0.4）	-

表4 不同数据集下的错误分类率

数据集	0.01		0.05		0.1
数据集	博弈论	多目标	博弈论	多目标	博弈论	多目标
BCW	5.86%	5.86%	6.15%	6%	6%	6.15%
MM	6.39%	22.05%	8.80%	7.11%	8.80%	22.05%
PRH	4.88%	4.88%	6%	5.07%	5.5%	5.14%
M	3.39%	2.03%	3.39%	0.87%	3.29%	1.18%
WIL	1.80%	24.90%	4.85%	24.90%	18.40%	24.90%
ORH	7.30%	10.18%	10.18%	10.18%	10.18%	10.18%
WP	17.52%	15.45%	36.95%	36.95%	36.95%	36.95%
CE	9.72%	9.72%	12.50%	12.50%	29.98%	29.98%
S	0.12%	0%	0.12%	0%	0%	0%
WC	8.41%	8.41%	28.18%	28.18%	28.18%	28.18%

表 5 不同数据集下运行时间对比(时间/s)

数据集	0.01		0.05		0.1
数据集	博弈论	多目标	博弈论	多目标	博弈论	多目标
BCW	0.0803	0.0857	0.0266	0.0344	0.0249	0.0227
MM	0.1916	0.2321	0.0872	0.1247	0.0826	0.0039
PRH	1.1732	1.2532	0.5431	0.8229	0.6348	0.7525
M	0.6091	0.7227	0.4477	0.6806	0.4363	0.5898
WIL	0.6540	0.0310	0.3899	0.0155	0.0841	0.0135
ORH	0.0267	0.0391	0.0179	0.0212	0.0152	0.0164
WP	0.2390	0.3677	0.0079	0.0086	0.0098	0.0141
CE	0.5055	0.5124	0.2995	0.3063	0.0027	0.0032
S	0.1826	0.1894	0.1249	0.1341	0.1231	0.1274
WC	0.1365	0.1449	0.0034	0.0557	0.0020	0.0039

图2 10个数据集在不同步长下的ECR对比

参考文献 25

1	张清华, 吕功勋, 陈玉洪, 谢秦. 基于字符型属性值更新的动态三支决策模型[J]. 电子学报, 2019, 47(2): 344⁃350.
	ZHANGQ H, LÜG X, CHENY H, XIEQ. A dynamic three-way decision model based on the updating of character attribute values[J]. Acta Electronica Sinica, 2019, 47(2): 344⁃350. (in Chinese)
2	张清华, 薛玉斌, 胡峰, 于洪. 粗糙集近似集的不确定性研究[J]. 电子学报, 2016, 44(7): 1574⁃1580.
	ZHANGQ H, XUEY B, HUF, YUH. Research on uncertainty of approximation set of rough set[J]. Acta Electronica Sinica, 2016, 44(7): 1574⁃1580. (in Chinese)
3	YAOY Y. Three-way decisions with probabilistic rough sets[J]. Information Sciences, 2010, 180(3): 341⁃353.
4	YAOY Y. Three-way decision: an interpretation of rules in rough set theory[C]//Proceedings of the International Conference on Rough Sets and Knowledge Technology. Berlin, Heidelberg, Germany: Springer, 2009. 642⁃649.
5	YAOY Y, DENGX F. Sequential three-way decisions with probabilistic rough sets[C]//Proceedings of the IEEE 10th International Conference on Cognitive Informatics and Cognitive Computing. Banff, AB, Canada: IEEE, 2011: 120⁃125.
6	YAOY Y. Granular computing and sequential three-way decisions[C]//Proceedings of the International Conference on Rough Sets and Knowledge Technology. Berlin, Heidelberg, Germany: Springer, 2013. 16⁃27.
7	YANGX, LIT R, LIUD, FUJITAH. A multilevel neighborhood sequential decision approach of three-way granular computing[J]. Information Sciences, 2020, 538: 119⁃141.
8	WANGM W, LIANGD C, XUZ S. Sequential three-way multiple attribute group decisions with individual attributes and its consensus achievement based on social influence[J]. Information Sciences, 2020, 518: 286⁃308.
9	SAVCHENKOA V. Fast inference in convolutional neural networks based on sequential three-way decisions[J]. Information Sciences, 2021, 560: 370⁃385.
10	HAOC, LIJ H, MINF, LIUW Q, TSANGE C C. Optimal scale selection in dynamic multi-scale decision tables based on sequential three-way decisions[J]. Information Sciences, 2017, 415⁃416: 213⁃232.
11	ZHANGH R, MINF, SHIB. Regression-based three-way recommendation[J]. Information Sciences, 2017, 378: 444⁃461.
12	YANGX, LIUD, YANGX B, LIUK Y, LIT R. Incremental fuzzy probability decision-theoretic approaches to dynamic three-way approximations[J]. Information Sciences, 2021, 550: 71⁃90.
13	李金海, 王飞, 吴伟志, 徐伟华, 杨习贝, 折延宏. 基于粒计算的多粒度数据分析方法综述[J]. 数据采集与处理, 2021, 36(3): 418⁃435.
	LIJ H, WANGF, WUW Z, XUW H, YANGX B, SHEY H. Review of multi‑granularity data analysis methods based on granular computing[J]. Journal of Data Acquisition and Processing, 2021, 36(3): 418⁃435. (in Chinese)
14	YANGX, LIT R, FUJITAH, LIUD, YAOY Y. A unified model of sequential three-way decisions and multilevel incremental processing[J]. Knowledge-Based Systems, 2017, 134: 172⁃188.
15	YANGB, LIJ H. Complex network analysis of three-way decision researches[J]. International Journal of Machine Learning and Cybernetics, 2020, 11(5): 973⁃987.
16	ZHANGQ H, XIAD Y, WANGG Y. Three-way decision model with two types of classification errors[J]. Information Sciences, 2017, 420: 431⁃453.
17	ZHANGQ H, PANGG H, WANGG Y. A novel sequential three-way decisions model based on penalty function[J]. Knowledge-Based Systems, 2020, 192: 105350.
18	ZHANGQ H, HUANGZ K, WANGG Y. A novel sequential three-way decision model with autonomous error correction[J]. Knowledge-Based Systems, 2021, 212: 106526.
19	PAWLAKZ. Rough sets[J]. International Journal of Computer and Information Sciences, 1982, 11(5): 341⁃356.
20	PAWLAKZ, SKOWRONA. Rough membership functions: a tool for reasoning with uncertainty[J]. Banach Center Publications, 1993, 28: 135⁃150.
21	QUINLANJ R. Induction of decision trees[J]. Machine Learning, 1986, 1(1): 81⁃106.
22	周志华. 机器学习[M]. 北京: 清华大学出版社, 2016: 73⁃95.
	ZHOUZ H. Machine Learning[M]. Beijing: Tsinghua University Press, 2016: 73⁃95. (in Chinese)
23	LEYTON-BROWNK, SHOHAMY. Essentials of game theory: A concise multidisciplinary introduction[J]. Synthesis Lectures on Artificial Intelligence and Machine Learning, 2008, 2(1): 1⁃88.
24	LIANGJ Y, CHINK S, DANGC Y, YAMR C M. A new method for measuring uncertainty and fuzziness in rough set theory[J]. International Journal of General Systems, 2002, 31(4): 331⁃342.
25	NIELSENM A. Neural Networks and Deep Learning[M]. San Francisco, USA: Determination Press, 2015: 67⁃85.

[1]	张浩, 胡昌华, 杜党波, 裴洪, 张建勋. 多状态影响下基于Bi‑LSTM网络的锂电池剩余寿命预测方法[J]. 电子学报, 2022, 50(3): 619-624.
[2]	伍邦谷, 张苏林, 石红, 朱鹏飞, 王旗龙, 胡清华. 基于多分支结构的不确定性局部通道注意力机制[J]. 电子学报, 2022, 50(2): 374-382.
[3]	智慧来, 张丽, 李金海. 旁观者视角下粒的多层次描述[J]. 电子学报, 2022, 50(11): 2568-2574.
[4]	陶凌, 陈安庆, 邓贞宙, 韩春雷, 王玉皞, 王平. 应用分形几何与混沌理论进行植物形态建模[J]. 电子学报, 2021, 49(9): 1776-1782.
[5]	张志勇, 程曦. 色散有损介质土壤对电磁回波影响的不确定性分析研究[J]. 电子学报, 2021, 49(3): 614-618.
[6]	罗睿辞, 叶蔚, 刘学洋, 孙基男, 张世琨. 基于拥塞博弈的微服务运行时资源管理方法[J]. 电子学报, 2019, 47(7): 1497-1505.
[7]	张恒巍, 黄世锐. Markov微分博弈模型及其在网络安全中的应用[J]. 电子学报, 2019, 47(3): 606-612.
[8]	李秋贤, 田有亮, 王缵. 基于全同态加密的理性委托计算协议[J]. 电子学报, 2019, 47(2): 470-474.
[9]	黄健明, 张恒巍. 基于随机演化博弈模型的网络防御策略选取方法[J]. 电子学报, 2018, 46(9): 2222-2228.
[10]	张恒巍, 李涛, 黄世锐. 基于攻防微分博弈的网络安全防御决策方法[J]. 电子学报, 2018, 46(6): 1428-1435.
[11]	张恒巍, 黄健明. 基于Markov演化博弈的网络防御策略选取方法[J]. 电子学报, 2018, 46(6): 1503-1509.
[12]	汪志勇, 张沪寅, 徐宁, 郝圣. 认知无线电网络中基于随机学习博弈的信道分配与功率控制[J]. 电子学报, 2018, 46(12): 2870-2877.
[13]	潘刚, 尚朝轩, 梁玉英, 蔡金燕, 孟亚峰. 相关竞争失效场合雷达功率放大系统可靠性评估[J]. 电子学报, 2017, 45(4): 805-812.
[14]	陈白, 辛敏洁, 刘伟静, 姚宁, 郝晓辰, 汝小月. 一种基于链路质量的自维护拓扑控制博弈算法[J]. 电子学报, 2016, 44(9): 2227-2234.
[15]	张清华, 薛玉斌, 胡峰, 于洪. 粗糙集近似集不确定性研究[J]. 电子学报, 2016, 44(7): 1574-1580.

基于不确定性与错误分类率博弈的序贯三支决策模型

Sequential Three-Way Decision Model Based on the Game Between Uncertainty and Error Classification Rate

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 25

相关文章 15

编辑推荐

Metrics