不完备多粒度决策系统的局部最优粒度选择
|
摘要
粒计算是知识表示和数据挖掘的一个重要方法.从粒计算来看,一个粒是由多个比较小的颗粒组成的更大的一个单元.在许多实际应用中,由于不同标记尺度对数据集进行分割会得到不同层次的粒度,许多人在用粒计算解决问题时自然而然地考虑不同层次的粒度问题.这就促使思考如何选择一个合适的粒度层次来解决问题.围绕不完备多粒度决策系统,研究了基于局部最优粒度的规则提取方法.1)介绍了不完备多粒度决策系统的概念;2)在协调的不完备多粒度决策系统中定义了最优粒度和局部最优粒度、介绍了基于局部最优粒度的属性约简和规则提取方法,在不协调的不完备多粒度决策系统中引入了广义决策、定义了广义最优粒度和广义局部最优粒度,并给出了基于广义局部最优粒度的属性约简和规则提取方法;3)给出了在公开的数据集上的实验结果.
Granular computing is an approach for knowledge representing and data mining.With the view point of granular computing,the notion of a granule is interpreted as one of the numerous small particles forming a larger unit.In many real-life applications,there are different granules at different levels of scale in data sets having hierarchical scale structures.Many people apply granular computing for problem solving by considering multiple levels of granularity.This allows us to focus on solving a problem at the most appropriate level of granularity by ignoring unimportant and irrelevant details.In this paper,rule extraction based on the local optimal granularities in incomplete multi-granular decision systems is explored.Firstly,the concept of incomplete multi-granular decision systems is introduced.Then the notions of the optimal granularity and the local optimal granularity in consistent incomplete multi-granular decision system are defined,and the approaches to attribute reduction and rule extraction based on the local optimal granularities are illustrated;the generalized decisions in inconsistent incomplete multi-granular decision systems are further introduced,the generalized optimal granularity and the generalized local optimal granularity are also defined,and the approaches to attribute reduction and rule extraction based on the generalized local optimal granularities are investigated.Finally,the experimental results on the public datasets are discussed.
Granular computing is an approach for knowledge representing and data mining.With the view point of granular computing,the notion of a granule is interpreted as one of the numerous small particles forming a larger unit.In many real-life applications,there are different granules at different levels of scale in data sets having hierarchical scale structures.Many people apply granular computing for problem solving by considering multiple levels of granularity.This allows us to focus on solving a problem at the most appropriate level of granularity by ignoring unimportant and irrelevant details.In this paper,rule extraction based on the local optimal granularities in incomplete multi-granular decision systems is explored.Firstly,the concept of incomplete multi-granular decision systems is introduced.Then the notions of the optimal granularity and the local optimal granularity in consistent incomplete multi-granular decision system are defined,and the approaches to attribute reduction and rule extraction based on the local optimal granularities are illustrated;the generalized decisions in inconsistent incomplete multi-granular decision systems are further introduced,the generalized optimal granularity and the generalized local optimal granularity are also defined,and the approaches to attribute reduction and rule extraction based on the generalized local optimal granularities are investigated.Finally,the experimental results on the public datasets are discussed.
引文
[1]Zadeh L A.Fuzzy sets and information granularity[G]//Advances in Fuzzy Set Theory and Applications.Amsterdam:North-Holland,1979:3-18
[2]Hobbs J R.Granularity[C]//Proc of the 9th Int Joint Conf on Artificial Intelligence.San Francisco,CA:Morgan Kaufmann,1985:432-435
[3]Lin T Y.Granular computing on binary relations I:Data mining and neighborhood systems[G]//Rough Sets in Knowledge Discovery.Heidelberg:Physica-Verlag,1998:107-121
[4]Lin T Y.Granular computing:Structures,representations,and applications[G]//LNAI 2639:Proc of the 9th Int Conf on Rough Sets,Fuzzy Sets,Data Mining,and Granular Computing.Berlin:Springer,2003:16-24
[5]Yao Yiyu.Granular computing:Basic issues and possible solutions[C]//Proc of the 5th Joint Conf on Computing and Information.Durham,NC:Duke University Press,2000:186-189
[6]Zhang Ling,Zhang Bo.Quotient Space Based Problem Solving:A Theoretical foundation of Granular Computing[M].Beijing:Tsinghua University Press,2014(in Chinese)(张铃,张钹.基于商空间的问题求解:粒度计算的理论基础[M].北京:清华大学出版社,2014)
[7]Liang Jiye,Qian Yuhua,Li Deyu,et al.Theory and method of granular computing for big data mining[J].Scientia Sinica:Informationis,2015,45(11):1355-1369(in Chinese)(梁吉业,钱宇华,李德玉,等.大数据挖掘的粒计算理论与方法[J].中国科学:信息科学,2015,45(11):1355-1369)
[8]Yao J T,Vasilakos A V,Pedrycz W.Granular computing:Perspectives and challenges[J].IEEE Trans on Cybernetics,2013,43(6):1977-1989
[9]Liu Qing,Qiu Taorong,Liu Lan.The research of granular computing based on nonstandard analysis[J].Chinese Journal of Computers,2015,38(8):1618-1627(in Chinese)(刘清,邱桃荣,刘斓.基于非标准分析的粒计算研究[J].计算机学报,2015,38(8):1618-1627)
[10]Hu Jie,Li Tianrui,Wang Hongjun,et al.Hierarchical cluster ensemble model based on knowledge granulation[J].Knowledge-Based Systems,2016,91:179-188
[11]Yang Xibei,Qian Yuhua,Yang Jingyu.Hierarchical structures on multigranulation spaces[J].Journal of Computer Science and Technology,2012,27(6):1169-1183
[12]Xu Ji,Wang Guoyin,Yu Hong.Review of big data processing based on granular computing[J].Chinese Journal of Computers,2015,38(8):1497-1517(in Chinese)(徐计,王国胤,于洪.基于粒计算的大数据处理[J].计算机学报,2015,38(8):1497-1517)
[13]Liu Qing,Liu Qun.Granules and applications of granular computing in logical reasoning[J].Journal of Computer Research and Development,2004,41(4):546-551(in Chinese)(刘清,刘群.粒及粒计算在逻辑推理中的应用[J].计算机研究与发展,2004,41(4):546-551)
[14]Hu Qinghua,Yu Daren,Xie Zongxia,et al.Fuzzy probabilistic approximation spaces and their information measures[J].IEEE Trans on Fuzzy Systems,2006,14(2):191-201
[15]Zhao Suyun,Wang Xizhao,Chen Degang,et al.Nested structure in parameterized rough reduction[J].Information Sciences,2013,248(6):130-150
[16]Shao Mingwen,Leung Y,Wu Weizhi.Rule acquisition and complexity reduction in formal decision contexts[J].International Journal of Approximate Reasoning,2014,55(1):259-274
[17]Zhang Qinghua,Xue Yubin,Wang Guoyin.Optimal approximation sets of rough sets[J].Journal of Software,2016,27(2):295-308(in Chinese)(张清华,薛玉斌,王国胤.粗糙集的最优近似集[J].软件学报,2016,27(2):295-308)
[18]Duan Jie,Hu Qinghua,Zhang Lingjun,et al.Feature selection for multi-label classification based on neighborhood rough sets[J].Journal of Computer Research and Development,2015,52(1):56-65(in Chinese)(段洁,胡清华,张灵均,等.基于邻域粗糙集的多标记分类特征选择算法[J].计算机研究与发展,2015,52(1):56-65)
[19]Pawlak Z.Rough sets[J].International Journal of Computer and Information Science,1982,11(5):341-356
[20]Deng Dayong,Xu Xiaoyu,Huang Houkuan.Concept drifting detection for categorical evolving data based on parallel reducts[J].Journal of Computer Research and Development,2015,52(5):1071-1079(in Chinese)(邓大勇,徐小玉,黄厚宽.基于并行约简的概念漂移探测[J].计算机研究与发展,2015,52(5):1071-1079)
[21]Fu Zhiyao,Gao Ling,Sun Qian,et al.Evaluation of vulnerability severity based on rough sets and attributes reduction[J].Journal of Computer Research and Development,2016,53(5):1009-1017(in Chinese)(付志耀,高岭,孙骞,等.基于粗糙集的漏洞属性约简及严重性评估[J].计算机研究与发展,2016,53(5):1009-1017)
[22]Zhang Wenxiu,Mi Jusheng,Wu Weizhi.Knowledge reductions in inconsistent information systems[J].Chinese Journal of Computers,2003,26(1):12-18(in Chinese)(张文修,米据生,吴伟志.不协调目标信息系统的知识约简[J].计算机学报,2003,26(1):12-18)
[23]Wang Guoyin,Yu Hong,Yang Dachun.Decision table reduction based on conditional information entropy[J].Chinese Journal of Computers,2002,25(7):759-766(in Chinese)(王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报,2002,25(7):759-766)
[24]Mi Jusheng,Wu Weizhi,Zhang Wenxiu.Approaches to knowledge reduction based on variable precision rough set model[J].Information Sciences,2004,159(3/4):255-272
[25]Miao Duoqian,Hu Guirong.A Heuristic algorithm for reduction of knowledge[J].Journal of Computer Research and Development,1999,36(6):681-684(in Chinese)(苗夺谦,胡桂荣.知识约简的一种启发式算法[J].计算机研究与发展,1999,36(6):681-684)
[26]Skowron A,Rauszer C.The discernibility matrices and functions in information systems[G]//Intelligent Decision Support-Handbook of Applications and Advances of the Rough Sets Theory.Amsterdam:Kluwer Academic Publishers,1992:331-362
[27]Qian Yuhua,Liang Jiye,Yao Yiyu,et al.MGRS:A multigranulation rough set[J].Information Sciences,2010,180(6):949-970
[28]Wu Weizhi,Leung Yee.Theory and applications of granular labelled partitions in multi-scale decision tables[J].Information Sciences,2011,181(18):3878-3897
[29]Wu Weizhi,Leung Yee.Optimal scale selection for multiscale decision tables[J].International Journal of Approximate Reasoning,2013,54(8):1107-1129
[30]Wu Weizhi,Chen Ying,Xu Youhong,et al.Optimal granularity selections in consistent incomplete multi-granular labeled decision systems[J].Pattern Recognition and Artificial Intelligence,2016,29(2):108-115(in Chinese)(吴伟志,陈颖,徐优红,等.协调的不完备多粒度标记决策系统的最优粒度选择[J].模式识别与人工智能,2016,29(2):108-115)
[31]Wu Weizhi,Gao Cangjian,Li Tongjun.Ordered granular labeled structures and rough approximations[J].Journal of Computer Research and Development,2014,51(12):2623-2632(in Chinese)(吴伟志,高仓健,李同军.序粒度标记结构及其粗糙近似[J].计算机研究与发展,2014,51(12):2623-2632)
[32]Gu Shenming,Wu Weizhi.On knowledge acquisition in multi-scale decision systems[J].International Journal of Machine Learning and Cybernetics,2013,4(5):477-486
[33]Gu Shenming,Wu Weizhi.Knowledge acquisition in inconsistent multi-scale decision systems[G]//LNCS 6954:Proc of the 6th Int Conf on Rough Sets and Knowledge Technology.Berlin:Springer,2011:669-678
[34]Wu Weizhi.Attribute reduction based on evidence theory in incomplete decision systems[J].Information Sciences,2008,178(5):1355-1371
[35]Kryszkiewicz M.Rough set approach to incomplete information systems[J].Information Sciences,1998,112(1/2/3/4):39-49
[36]Yang Xibei,Song Xiaoning,Chen Zehua,et al.On multigranulation rough sets in incomplete information system[J].International Journal of Machine Learning and Cybernetics,2012,3(3):223-232
[2]Hobbs J R.Granularity[C]//Proc of the 9th Int Joint Conf on Artificial Intelligence.San Francisco,CA:Morgan Kaufmann,1985:432-435
[3]Lin T Y.Granular computing on binary relations I:Data mining and neighborhood systems[G]//Rough Sets in Knowledge Discovery.Heidelberg:Physica-Verlag,1998:107-121
[4]Lin T Y.Granular computing:Structures,representations,and applications[G]//LNAI 2639:Proc of the 9th Int Conf on Rough Sets,Fuzzy Sets,Data Mining,and Granular Computing.Berlin:Springer,2003:16-24
[5]Yao Yiyu.Granular computing:Basic issues and possible solutions[C]//Proc of the 5th Joint Conf on Computing and Information.Durham,NC:Duke University Press,2000:186-189
[6]Zhang Ling,Zhang Bo.Quotient Space Based Problem Solving:A Theoretical foundation of Granular Computing[M].Beijing:Tsinghua University Press,2014(in Chinese)(张铃,张钹.基于商空间的问题求解:粒度计算的理论基础[M].北京:清华大学出版社,2014)
[7]Liang Jiye,Qian Yuhua,Li Deyu,et al.Theory and method of granular computing for big data mining[J].Scientia Sinica:Informationis,2015,45(11):1355-1369(in Chinese)(梁吉业,钱宇华,李德玉,等.大数据挖掘的粒计算理论与方法[J].中国科学:信息科学,2015,45(11):1355-1369)
[8]Yao J T,Vasilakos A V,Pedrycz W.Granular computing:Perspectives and challenges[J].IEEE Trans on Cybernetics,2013,43(6):1977-1989
[9]Liu Qing,Qiu Taorong,Liu Lan.The research of granular computing based on nonstandard analysis[J].Chinese Journal of Computers,2015,38(8):1618-1627(in Chinese)(刘清,邱桃荣,刘斓.基于非标准分析的粒计算研究[J].计算机学报,2015,38(8):1618-1627)
[10]Hu Jie,Li Tianrui,Wang Hongjun,et al.Hierarchical cluster ensemble model based on knowledge granulation[J].Knowledge-Based Systems,2016,91:179-188
[11]Yang Xibei,Qian Yuhua,Yang Jingyu.Hierarchical structures on multigranulation spaces[J].Journal of Computer Science and Technology,2012,27(6):1169-1183
[12]Xu Ji,Wang Guoyin,Yu Hong.Review of big data processing based on granular computing[J].Chinese Journal of Computers,2015,38(8):1497-1517(in Chinese)(徐计,王国胤,于洪.基于粒计算的大数据处理[J].计算机学报,2015,38(8):1497-1517)
[13]Liu Qing,Liu Qun.Granules and applications of granular computing in logical reasoning[J].Journal of Computer Research and Development,2004,41(4):546-551(in Chinese)(刘清,刘群.粒及粒计算在逻辑推理中的应用[J].计算机研究与发展,2004,41(4):546-551)
[14]Hu Qinghua,Yu Daren,Xie Zongxia,et al.Fuzzy probabilistic approximation spaces and their information measures[J].IEEE Trans on Fuzzy Systems,2006,14(2):191-201
[15]Zhao Suyun,Wang Xizhao,Chen Degang,et al.Nested structure in parameterized rough reduction[J].Information Sciences,2013,248(6):130-150
[16]Shao Mingwen,Leung Y,Wu Weizhi.Rule acquisition and complexity reduction in formal decision contexts[J].International Journal of Approximate Reasoning,2014,55(1):259-274
[17]Zhang Qinghua,Xue Yubin,Wang Guoyin.Optimal approximation sets of rough sets[J].Journal of Software,2016,27(2):295-308(in Chinese)(张清华,薛玉斌,王国胤.粗糙集的最优近似集[J].软件学报,2016,27(2):295-308)
[18]Duan Jie,Hu Qinghua,Zhang Lingjun,et al.Feature selection for multi-label classification based on neighborhood rough sets[J].Journal of Computer Research and Development,2015,52(1):56-65(in Chinese)(段洁,胡清华,张灵均,等.基于邻域粗糙集的多标记分类特征选择算法[J].计算机研究与发展,2015,52(1):56-65)
[19]Pawlak Z.Rough sets[J].International Journal of Computer and Information Science,1982,11(5):341-356
[20]Deng Dayong,Xu Xiaoyu,Huang Houkuan.Concept drifting detection for categorical evolving data based on parallel reducts[J].Journal of Computer Research and Development,2015,52(5):1071-1079(in Chinese)(邓大勇,徐小玉,黄厚宽.基于并行约简的概念漂移探测[J].计算机研究与发展,2015,52(5):1071-1079)
[21]Fu Zhiyao,Gao Ling,Sun Qian,et al.Evaluation of vulnerability severity based on rough sets and attributes reduction[J].Journal of Computer Research and Development,2016,53(5):1009-1017(in Chinese)(付志耀,高岭,孙骞,等.基于粗糙集的漏洞属性约简及严重性评估[J].计算机研究与发展,2016,53(5):1009-1017)
[22]Zhang Wenxiu,Mi Jusheng,Wu Weizhi.Knowledge reductions in inconsistent information systems[J].Chinese Journal of Computers,2003,26(1):12-18(in Chinese)(张文修,米据生,吴伟志.不协调目标信息系统的知识约简[J].计算机学报,2003,26(1):12-18)
[23]Wang Guoyin,Yu Hong,Yang Dachun.Decision table reduction based on conditional information entropy[J].Chinese Journal of Computers,2002,25(7):759-766(in Chinese)(王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报,2002,25(7):759-766)
[24]Mi Jusheng,Wu Weizhi,Zhang Wenxiu.Approaches to knowledge reduction based on variable precision rough set model[J].Information Sciences,2004,159(3/4):255-272
[25]Miao Duoqian,Hu Guirong.A Heuristic algorithm for reduction of knowledge[J].Journal of Computer Research and Development,1999,36(6):681-684(in Chinese)(苗夺谦,胡桂荣.知识约简的一种启发式算法[J].计算机研究与发展,1999,36(6):681-684)
[26]Skowron A,Rauszer C.The discernibility matrices and functions in information systems[G]//Intelligent Decision Support-Handbook of Applications and Advances of the Rough Sets Theory.Amsterdam:Kluwer Academic Publishers,1992:331-362
[27]Qian Yuhua,Liang Jiye,Yao Yiyu,et al.MGRS:A multigranulation rough set[J].Information Sciences,2010,180(6):949-970
[28]Wu Weizhi,Leung Yee.Theory and applications of granular labelled partitions in multi-scale decision tables[J].Information Sciences,2011,181(18):3878-3897
[29]Wu Weizhi,Leung Yee.Optimal scale selection for multiscale decision tables[J].International Journal of Approximate Reasoning,2013,54(8):1107-1129
[30]Wu Weizhi,Chen Ying,Xu Youhong,et al.Optimal granularity selections in consistent incomplete multi-granular labeled decision systems[J].Pattern Recognition and Artificial Intelligence,2016,29(2):108-115(in Chinese)(吴伟志,陈颖,徐优红,等.协调的不完备多粒度标记决策系统的最优粒度选择[J].模式识别与人工智能,2016,29(2):108-115)
[31]Wu Weizhi,Gao Cangjian,Li Tongjun.Ordered granular labeled structures and rough approximations[J].Journal of Computer Research and Development,2014,51(12):2623-2632(in Chinese)(吴伟志,高仓健,李同军.序粒度标记结构及其粗糙近似[J].计算机研究与发展,2014,51(12):2623-2632)
[32]Gu Shenming,Wu Weizhi.On knowledge acquisition in multi-scale decision systems[J].International Journal of Machine Learning and Cybernetics,2013,4(5):477-486
[33]Gu Shenming,Wu Weizhi.Knowledge acquisition in inconsistent multi-scale decision systems[G]//LNCS 6954:Proc of the 6th Int Conf on Rough Sets and Knowledge Technology.Berlin:Springer,2011:669-678
[34]Wu Weizhi.Attribute reduction based on evidence theory in incomplete decision systems[J].Information Sciences,2008,178(5):1355-1371
[35]Kryszkiewicz M.Rough set approach to incomplete information systems[J].Information Sciences,1998,112(1/2/3/4):39-49
[36]Yang Xibei,Song Xiaoning,Chen Zehua,et al.On multigranulation rough sets in incomplete information system[J].International Journal of Machine Learning and Cybernetics,2012,3(3):223-232