具有多尺度决策的信息系统的最优全局剪枝选择

doi:10.13232/j.cnki.jnju.2023.01.002

南京大学学报(自然科学版) ›› 2023, Vol. 59 ›› Issue (1): 12–21.doi: 10.13232/j.cnki.jnju.2023.01.002

具有多尺度决策的信息系统的最优全局剪枝选择

于子淳¹, 吴伟志¹^,²()

^1.浙江海洋大学信息工程学院, 舟山, 316022
^2.浙江省海洋大数据挖掘与应用重点实验室, 浙江海洋大学, 舟山, 316022

收稿日期:2022-09-28 出版日期:2023-01-31 发布日期:2023-03-01
通讯作者: 吴伟志 E-mail:wuwz@zjou.edu.cn
基金资助:
国家自然科学基金(61976194)

On selection of optimal cuts in information systems with multi⁃scale decisions

Zichun Yu¹, Weizhi Wu¹^,²()

^1.School of Information Engineering，Zhejiang Ocean University，Zhoushan，316022，China
^2.Key Laboratory of Oceanographic Big Data Mining and Application of Zhejiang Province，Zhejiang Ocean University，Zhoushan，316022，China

Received:2022-09-28 Online:2023-01-31 Published:2023-03-01
Contact: Weizhi Wu E-mail:wuwz@zjou.edu.cn

摘要/Abstract

摘要：

作为人工智能领域的一个重要方向，粒计算在数据挖掘和知识发现方面的研究呈现较大的优势.针对具有多尺度决策的信息系统的知识获取问题，利用粒度树与剪枝来研究具有多尺度决策的信息系统的最优尺度选择问题.首先介绍了粒度树与剪枝的概念，每个属性和决策都有一个粒度树，每个粒度树都有许多不同的局部剪枝，代表特定属性下的尺度选择.不同属性和决策的一个局部剪枝组合形成全局剪枝，从而产生一个混合尺度决策表.其次，给出具有多尺度决策的信息系统基于粒度树与剪枝的最优全局剪枝选择的概念.最后将全局剪枝选择与最优尺度选择进行比较研究，还设计了一个算法来验证该方法的有效性.

关键词: 粒度树, 剪枝, 具有多尺度决策的信息系统, 粗糙集

Abstract:

As an important direction in research fields of artificial intelligence，granular computing has great advantages in data mining and knowledge discovery. To solve the problem of knowledge acquisition in information system with multi?scale decisions，the optimal scale selection problem of information systems with multi?scale decisions is studied by using granularity trees and cuts. The concepts of granularity trees and cuts are firstly introduced. Each attribute and decision has a granularity tree，and each granularity tree has many different local cuts，which represent the scale selection methods under a specific attribute. A local cut combination of different attributes and decision forms a global cut，resulting in a mixed scale decision table. Then，the concept of optimal cuts based on granularity trees and cuts in information systems with multi?scale decisions is presented. Finally，a comparative study between optimal cuts and optimal scale selections is performed and an algorithm is designed to verify the effectiveness of the method.

Key words: granularity tree, cut, information systems with multi?scale decisions, rough sets

中图分类号:

TP18

于子淳, 吴伟志. 具有多尺度决策的信息系统的最优全局剪枝选择[J]. 南京大学学报(自然科学版), 2023, 59(1): 12–21.

Zichun Yu, Weizhi Wu. On selection of optimal cuts in information systems with multi⁃scale decisions[J]. Journal of Nanjing University(Natural Sciences), 2023, 59(1): 12–21.

图/表 7

表1

一个具有多尺度决策的信息系统"

$U$	$a 11$	$a 12$	$a 21$	$a 22$	$a 31$	$a 32$	$d 1$	$d 2$
$x 1$	9	E	9	E	8	G	E	1
$x 2$	9	E	9	E	7	G	E	1
$x 3$	7	G	8	G	7	G	G	2
$x 4$	8	G	6	M	8	G	G	2
$x 5$	8	G	6	M	5	P	P	2
$x 6$	6	M	6	M	2	U	U	0
$x 7$	6	M	5	P	5	P	P	2
$x 8$	6	M	2	U	4	P	U	0
$x 9$	9	E	6	M	5	P	G	2
$x 10$	9	E	6	M	4	P	P	2
$x 11$	8	G	6	M	8	G	G	2
$x 12$	6	M	4	P	5	P	P	2

表1

图1

图2

图3

图4

表2

一个混合尺度决策表"

$U$	$a 1$	$a 2$	$a 3$	$d$
$x 1$	9	E	8	1
$x 2$	9	E	7	1
$x 3$	G	G	7	G
$x 4$	G	M	8	P
$x 5$	G	M	P	P
$x 6$	6	M	U	0
$x 7$	6	5	P	G
$x 8$	6	U	P	0
$x 9$	9	M	P	P
$x 10$	9	M	P	G
$x 11$	G	M	8	P
$x 12$	6	4	P	G

表2

表3

最优全局剪枝选择算法的时间复杂度"

步骤	时间复杂度
Step 1	$O A A 1 ⋯ A m D U$
Step 2	$O C S S O S S$
Step 3	$O O S S A$
Step 4	$O O S S m e i 1 ⋯ m e i m m g i U$
Step 5	$O C C S O C S$

表3

参考文献 39

1	Zadeh L A. Fuzzy sets and information granularity∥Gupta N，Ragade R，Yager R. Advances in fuzzy set theory and applications. Amsterdam，The Netherlands：North?Holland，1979：3-18.
2	Hobbs J R. Granularity∥Proceedings of the 9th International Joint Conference on Artificial Intelligence. San Francisco，CA，USA：Morgan Kaufmann，1985：432-435.
3	Lin T Y. Granular computing：From rough sets and neighborhood systems to information granulation and computing with words∥European Congress on Intelligent Techniques and Soft Computing. Palo Alto，CA，USA：Electric Power Research Institute，1997：1602-1606.
4	Lin T Y. Granular computing：Structures，representations，and applications∥Proceedings of the 9th International Conference on Rough Sets，Fuzzy Sets，Data Mining，and Granular Computing. Chongqing，China：Springer，2003：16-24.
5	Yao Y Y. Granular computing：Basic issues and possible solutions∥Proceedings of the 5th Joint Conference on Information Sciences. Durham，United Kingdom：Duke University Press，2000：186-189.
6	段洁，胡清华，张灵均，等. 基于邻域粗糙集的多标记分类特征选择算法. 计算机研究与发展，2015，52(1)：56-65.
	Duan J， Hu Q H， Zhang L J，et al. Feature selection for multi-label classification based on neighborhood rough sets. Journal of Computer Research and Development，2015，52(1)：56-65.
7	Kryszkiewicz M. Rough set approach to incomplete information systems. Information Sciences，1998，112(1-4)：39-49.
8	Leung Y， Wu W Z， Zhang W X. Knowledge acquisition in incomplete information systems：A rough set approach. European Journal of Operational Research，2006，168(1)：164-180.
9	Li D Y， Zhang B， Leung Y. On knowledge reduction in inconsistent decision information systems. International Journal of Uncertainty，Fuzziness and Knowledge?Based Systems，2004，12(5)：651-672.
10	Lin T Y， Yao Y Y， Zadeh L A. Data mining，rough sets and granular computing. Berlin Heidelberg：Springer，2002，537.
11	苗夺谦，王国胤，刘清，等. 粒计算：过去、现在与展望. 北京：科学出版社，2007：373.
12	苗夺谦，李德毅，姚一豫，等. 不确定性与粒计算. 北京：科学出版社，2011：171.
13	Pedrycz W， Skowron A， Kreinovich V. Handbook of granular computing. Hoboken：John Wiley & Sons，2008，1116.
14	Shao M W， Zhang W X. Dominance relation and rules in an incomplete ordered information system. International Journal of Intelligent Systems，2005，20(1)：13-27.
15	史倩玉，梁吉业，赵兴旺. 一种不完备混合数据集成聚类算法. 计算机研究与发展，2016，53(9)：1979-1989.
	Shi Q Y， Liang J Y， Zhao X W. A clustering ensemble algorithm for incomplete mixed data. Journal of Computer Research and Development，2016，53(9)：1979-1989.
16	Sun B Z， Ma W M， Gong Z T. Dominance?based rough set theory over interval?valued information systems. Expert Systems，2014，31(2)：185-197.
17	张维，苗夺谦，高灿，等. 邻域粗糙协同分类模型. 计算机研究与发展，2014，51(8)：1811-1820.
	Zhang W， Miao D Q， Gao C，et al. A neighborhood rough sets?based co?training model for classification. Journal of Computer Research and Development，2014，51(8)：1811-1820.
18	Pawlak Z. Rough sets：Theoretical aspects of reasoning about data. Dordrecht：Springer，1991，231.
19	Qian Y H， Liang J Y， Yao Y Y，et al. MGRS：A multi?granulation rough set. Information Sciences，2010，180(6)：949-970.
20	Qian Y H， Liang J Y， Dang C Y. Incomplete multigranulation rough set. IEEE Transactions on Systems，Man，and Cybernetics,Part A：Systems and Humans，2010，40(2)：420-431.
21	Yang X B， Song X N， Chen Z H，et al. On multigranulation rough sets in incomplete information system. International Journal of Machine Learning and Cybernetics，2012，3(3)：223-232.
22	Wu W Z， Leung Y. Theory and applications of granular labelled partitions in multi?scale decision tables. Information Sciences，2011，181(18)：3878-3897.
23	吴伟志，高仓健，李同军. 序粒度标记结构及其粗糙近似. 计算机研究与发展，2014，51(12)：2623-2632.
	Wu W Z， Gao C J， Li T J. Ordered granular labeled structures and rough approximations. Journal of Computer Research and Development，2014，51(12)：2623-2632.
24	戴志聪，吴伟志. 不完备多粒度序信息系统的粗糙近似. 南京大学学报(自然科学)，2015，51(2)：361-367.
	Dai Z C， Wu W Z. Rough approximations in incomplete multi?granular ordered information systems. Journal of Nanjing University (Natural Scien?ces)，2015，51(2)：361-367.
25	Wu W Z， Leung Y. Optimal scale selection for multi?scale decision tables. International Journal of Approximate Reasoning，2013，54(8)：1107-1129.
26	吴伟志，陈颖，徐优红，等. 协调的不完备多粒度标记决策系统的最优粒度选择. 模式识别与人工智能，2016，29(2)：108-115.
	Wu W Z， Chen Y， Xu Y H，et al. Optimal granularity selections in consistent incomplete multi?granular labeled decision systems. Pattern Recognition and Artificial Intelligence，2016，29(2)：108-115.
27	吴伟志，陈超君，李同军，等. 不协调多粒度标记决策系统最优粒度的对比. 模式识别与人工智能，2016，29(12)：1095-1103.
	Wu W Z， Chen C J， Li T J，et al. A comparative study on optimal granularities in inconsistent multi?granular labeled decision systems. Pattern Recognition and Artificial Intelligence，2016，29(12)：1095-1103.
28	She Y H， Li J H， Yang H L. A local approach to rule induction in multi?scale decision tables. Knowledge?Based Systems，2015(89)：398-410.
29	Gu S M， Wu W Z. On knowledge acquisition in multi?scale decision systems. International Journal of Machine Learning and Cybernetics，2013，4(5)：477-486.
30	Gu S M， Wu W Z. Knowledge acquisition in inconsistent multi?scale decision systems∥The 6th International Conference on Rough Sets and Knowledge Technology. Banff，Canada：Springer，2011：669-678.
31	Wu W Z， Qian Y H， Li T J，et al. On rule acquisition in incomplete multi?scale decision tables. Information Sciences，2017(378)：282-302.
32	Li F， Hu B Q. A new approach of optimal scale selection to multi?scale decision tables. Information Sciences，2017(381)：193-208.
33	Wu W Z， Leung Y. A comparison study of optimal scale combination selection in generalized multi?scale decision tables. International Journal of Machine Learning and Cybernetics，2020，11(5)：961-972.
34	郑嘉文，吴伟志，包菡，等. 基于熵的多尺度决策系统的最优尺度选择. 南京大学学报(自然科学)，2021，57(1)：130-140.
	Zheng J W， Wu W Z， Bao H，et al. Entropy based optimal scale selection for multi?scale decision systems. Journal of Nanjing University (Natural Science)，2021，57(1)：130-140.
35	Li W K， Huang J X， Li J J，et al. Matrix representation of optimal scale for generalized multi?scale decision table. Journal of Ambient Intelligence and Humanized Computing，2021，12(8)：8549-8559.
36	Huang Z H， Li J J， Dai W Z，et al. Generalized multi?scale decision tables with multi?scale decision attributes. International Journal of Approximate Reasoning，2019(115)：194-208.
37	She Y H， Zhao Z J， Hu M T，et al. On selection of optimal cuts in complete multi?scale decision tables. Artificial Intelligence Review，2021，54(8)：6125-6148.
38	Belohlavek R， De Baets B， Konecny J. Granularity of attributes in formal concept analysis. Information Sciences，2014(260)：149-170.
39	Shao M W， Lv M M， Li K W，et al. The construction of attribute (object)?oriented multi?granularity concept lattices. International Journal of Machine Learning and Cybernetics，2020，11(5)：1017-1032.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

[1]	徐伟华, 潘彦舟. 加权变精度直觉模糊序信息决策表的近似约简[J]. 南京大学学报(自然科学版), 2023, 59(1): 1-11.
[2]	章成旭, 叶绍强, 周恺卿, 欧云. 基于粗糙集和改进二进制布谷鸟搜索算法的高维数据特征选择[J]. 南京大学学报(自然科学版), 2022, 58(4): 584-593.
[3]	王文珏, 黄兵. 多尺度单值中智系统中基于优势粗糙集模型的最优尺度选择与约简[J]. 南京大学学报(自然科学版), 2022, 58(3): 495-505.
[4]	曾艺祥, 林耀进, 范凯钧, 曾伯儒. 基于层次类别邻域粗糙集的在线流特征选择算法[J]. 南京大学学报(自然科学版), 2022, 58(3): 506-518.
[5]	周悦丽, 林国平, 谢淋淋. 基于矩阵的动态局部相容粗糙集的增量方法[J]. 南京大学学报(自然科学版), 2022, 58(3): 519-531.
[6]	胡玉文, 徐久成, 张倩倩. 决策演化集的卷积预测[J]. 南京大学学报(自然科学版), 2022, 58(1): 1-8.
[7]	于子淳, 吴伟志. 用证据理论刻画协调的具有多尺度决策的信息系统的最优尺度选择[J]. 南京大学学报(自然科学版), 2022, 58(1): 71-81.
[8]	王敬前, 张小红. 基于极大相容块的不完备信息处理新方法及其应用[J]. 南京大学学报(自然科学版), 2022, 58(1): 82-93.
[9]	刘小伟, 景运革. 一种有效更新多源数据约简的增量算法[J]. 南京大学学报(自然科学版), 2021, 57(6): 1083-1091.
[10]	孙颖, 蔡天使, 张毅, 鞠恒荣, 丁卫平. 基于合理粒度的局部邻域决策粗糙计算方法[J]. 南京大学学报(自然科学版), 2021, 57(2): 262-271.
[11]	刘琼, 代建华, 陈姣龙. 区间值数据的代价敏感特征选择[J]. 南京大学学报(自然科学版), 2021, 57(1): 121-129.
[12]	郑嘉文, 吴伟志, 包菡, 谭安辉. 基于熵的多尺度决策系统的最优尺度选择[J]. 南京大学学报(自然科学版), 2021, 57(1): 130-140.
[13]	郑文彬, 李进金, 张燕兰, 廖淑娇. 基于矩阵的多粒度粗糙集粒度约简方法[J]. 南京大学学报(自然科学版), 2021, 57(1): 141-149.
[14]	毛振宇, 窦慧莉, 宋晶晶, 姜泽华, 王平心. 共现邻域关系下的属性约简研究[J]. 南京大学学报(自然科学版), 2021, 57(1): 150-159.
[15]	李同军,于洋,吴伟志,顾沈明. 经典粗糙近似的一个公理化刻画[J]. 南京大学学报(自然科学版), 2020, 56(4): 445-451.

具有多尺度决策的信息系统的最优全局剪枝选择

On selection of optimal cuts in information systems with multi⁃scale decisions

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 39

相关文章 15

Metrics

本文评价

推荐阅读 0