广义不完备多粒度标记决策系统的粒度选择
|
摘要
粒计算(granular computing,GrC)是知识表示和数据挖掘的一个重要方法,它模拟人类思考模式,以粒为基本计算单位,以建立大规模复杂数据和信息处理的有效计算模型为目标.粒计算主要研究粒的构造、解释、表示、粒度的选择以及用规则形式所描述的粒与粒之间的关系等.针对具有多粒度标记的不完备信息系统的知识获取问题,首先,介绍了广义不完备多粒度标记信息系统的概念,在该信息系统中定义了相似关系,给出了在不同粒度标记层面下信息粒的表示及其相互关系,并定义了基于相似关系的集合的下、上近似概念,给出了近似算子的性质;其次,定义了广义不完备多粒度标记决策系统中的粒度标记选择的概念,阐明了所有粒度标记选择全体构成了一个完备格;最后,讨论了广义不完备多粒度标记决策系统中的最优粒度标记选择问题,并用证据理论中的信任函数和似然函数刻画了协调的不完备多粒度标记决策系统的最优粒度选择特征.
Granular computing(GrC),which imitates human being's thinking,is an approach for knowledge representation and data mining.Its basic computing unit is called granules,and its objective is to establish effective computation models for dealing with large scale complex data and information. The main directions in the study of granular computing are the construction,interpretation,representation of granules,the selection of granularities and relations among granules which are represented by granular IF-THEN rules with granular variables and their relevant granular values.In order to investigate knowledge acquisition in the sense of decision rules in incomplete information systems with multi-granular labels,the concept of generalized incomplete multi-granular labeled information systems is first introduced.Information granules with different labels of granulation as well as their relationships from generalized incomplete multi-granular labeled information systems are then represented.Lower and upper approximations of sets with different levels of granulation are further defined and their properties are presented.The concept of granularity label selections in generalized incomplete multi-granular labeled information systems is also proposed.It is shown that the collection of all granularity label selections forms a complete lattice.Finally,optimal granular label selections in incomplete multi-granular labeled decision tables are also discussed.Belief and plausibility functions in the Dempster-Shafer theory of evidence are employed to characterize optimal granular label selections in consistent incomplete multi-granular labeled decision systems.
Granular computing(GrC),which imitates human being's thinking,is an approach for knowledge representation and data mining.Its basic computing unit is called granules,and its objective is to establish effective computation models for dealing with large scale complex data and information. The main directions in the study of granular computing are the construction,interpretation,representation of granules,the selection of granularities and relations among granules which are represented by granular IF-THEN rules with granular variables and their relevant granular values.In order to investigate knowledge acquisition in the sense of decision rules in incomplete information systems with multi-granular labels,the concept of generalized incomplete multi-granular labeled information systems is first introduced.Information granules with different labels of granulation as well as their relationships from generalized incomplete multi-granular labeled information systems are then represented.Lower and upper approximations of sets with different levels of granulation are further defined and their properties are presented.The concept of granularity label selections in generalized incomplete multi-granular labeled information systems is also proposed.It is shown that the collection of all granularity label selections forms a complete lattice.Finally,optimal granular label selections in incomplete multi-granular labeled decision tables are also discussed.Belief and plausibility functions in the Dempster-Shafer theory of evidence are employed to characterize optimal granular label selections in consistent incomplete multi-granular labeled decision systems.
引文
[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]Zadeh L A.Towards a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[J].Fuzzy Sets and Systems,1997,90(2):111-127
[4]Lin Tsau Young.Granular computing:From rough sets and neighborhood systems to information granulation and computing in words[C/OL]//Proc of European Congress on Intelligent Techniques and Soft Computing,1997[2017-05-12].http://xanadu.cs.sjsu.edu/~drtylin/publications/paperList/101_34rsnsigcw3.pdf
[5]Lin Tsau Young.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
[6]Yao Yiyu.Granular computing:Basic issues and possible solutions[C]//Proc of the 5th Joint Conf on Computing and Information.Durham:Duke University Press,2000:186-189
[7]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)
[8]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)
[9]Kryszkiewicz M.Rough set approach to incomplete information systems[J].Information Sciences,1998,112(1-4):39-49
[10]Leung Yee,Wu Weizhi,Zhang Wenxiu.Knowledge acquisition in incomplete information systems:A rough set approach[J].European Journal of Operational Research,2006,168(1):164-180
[11]Li Deyu,Zhang Bo,Leung Yee.On knowledge reduction in inconsistent decision information systems[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2004,12(5):651-672
[12]Lin Tsau Young,Yao Yiyu,Zadeh L A.Data Mining,Rough Sets and Granular Computing[M].New York:Physica-Verlag,2002
[13]Miao Duoqian,Wang Guoyin,Liu Qing,et al.Granular Computing:Past,Present and Future[M].Beijing:Science Press,2007(in Chinese)(苗夺谦,王国胤,刘清,等.粒计算的过去、现在与展望[M].北京:科学出版社,2007)
[14]Miao Duoqian,Li Deyi,Yao Yiyu,et al.Uncertainty and Granular Computing[M].Beijing:Science Press,2011(in Chinese)(苗夺谦,李德毅,姚一豫,等.不确定性与粒计算[M].北京:科学出版社,2011)
[15]Pedrycz W,Skowron A,Kreinovich V.Handbook of Granular Computing[M].New York:Wiley,2008
[16]Shao Mingwen,Zhang Wenxiu.Dominance relation and rules in an incomplete ordered information system[J].International Journal of Intelligent Systems,2005,20(1):13-27
[17]Shi Qianyu,Liang Jiye,Zhao Xingwang.A clustering ensemble algorithm for incomplete mixed data[J].Journal of Computer Research and Development,2016,53(9):1979-1989(in Chinese)(史倩玉,梁吉业,赵兴旺.一种不完备混合数据集成聚类算法[J].计算机研究与发展,2016,53(9):1979-1989)
[18]Sun Bingzhen,Ma Weimin,Gong Zengtai.Dominance-based rough set theory over interval-valued information systems[J].Expert Systems,2014,31(2):185-197
[19]Zhang Wei,Miao Duoqian,Gao Can,et al.A neighborhood rough sets-based co-training model for classification[J].Journal of Computer Research and Development,2014,51(8):1811-1820(in Chinese)(张维,苗夺谦,高灿,等.邻域粗糙协同分类模型[J].计算机研究与发展,2014,51(8):1811-1820)
[20]Pawlak Z.Rough Sets:Theoretical Aspects of Reasoning about Data[M].Amsterdam,Netherlands:Kluwer Academic Publishers,1991
[21]Qian Yuhua,Liang Jiye,Yao Yiyu,et al.MGRS:A multigranulation rough set[J].Information Sciences,2010,180(6):949-970
[22]Qian Yuhua,Liang Jiye,Dang Chuangyin.Incomplete multigranulation rough set[J].IEEE Trans on Systems,Man and Cybernetics,2010,40(2):420-431
[23]Yang Xibei,Song Xiaoning,Chen Zehua.On multigranulation rough sets in incomplete information system[J].International Journal of Machine Learning and Cybernetics,2012,3(3):223-232
[24]Wu Weizhi,Leung Yee.Theory and applications of granular labeled partitions in multi-scale decision tables[J].Information Sciences,2011,181(18):3878-3897
[25]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)
[26]Dai Zhicong,Wu Weizhi.Rough approximations in incomplete multi-granular ordered information systems[J].Journal of Nanjing University:Natural Sciences,2015,51(2):361-367(in Chinese)(戴志聪,吴伟志.不完备多粒度序信息系统的粗糙近似[J].南京大学学报:自然科学版,2015,51(2):361-367)
[27]Wu Weizhi,Leung Yee.Optimal scale selection for multiscale decision tables[J].International Journal of Approximate Reasoning,2013,54(8):1107-1129
[28]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)
[29]Wu Weizhi,Chen Chaojun,Li Tongjun,et al.A comparative study on optimal granularities in inconsistent multi-granular labeled decision systems[J].Pattern Recognition and Artificial Intelligence,2016,29(12):1103-1111(in Chinese)(吴伟志,陈超君,李同军,等.不协调多粒度标记决策系统最优粒度的对比[J].模式识别与人工智能,2016,29(12):1103-1111)
[30]She Yanhong,Li Jinhai,Yang Hailong.A local approach to rule induction in multi-scale decision tables[J].KnowledgeBased Systems,2015,89:398-410
[31]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
[32]Gu Shenming,Wu Weizhi.Knowledge acquisition in inconsistent multi-scale decision systems[G]//LNAI 6964:Proc of the 6th Int Conf on Rough Sets and Knowledge Technology.Berlin:Springer,2011:669-678
[33]Wu Weizhi,Qian Yuhua,Li Tongjun,et al.On rule acquisition in incomplete multi-scale decision tables[J].Information Sciences,2017,378:282-302
[34]Li Feng,Hu Baoqing.A new approach of optimal scale selection to multi-scale decision tables[J].Information Sciences,2017,381:193-208
[35]Wu Weizhi.Attribute reduction based on evidence theory in incomplete decision systems[J].Information Sciences,2008,178(5):1355-1371
[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]Zadeh L A.Towards a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[J].Fuzzy Sets and Systems,1997,90(2):111-127
[4]Lin Tsau Young.Granular computing:From rough sets and neighborhood systems to information granulation and computing in words[C/OL]//Proc of European Congress on Intelligent Techniques and Soft Computing,1997[2017-05-12].http://xanadu.cs.sjsu.edu/~drtylin/publications/paperList/101_34rsnsigcw3.pdf
[5]Lin Tsau Young.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
[6]Yao Yiyu.Granular computing:Basic issues and possible solutions[C]//Proc of the 5th Joint Conf on Computing and Information.Durham:Duke University Press,2000:186-189
[7]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)
[8]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)
[9]Kryszkiewicz M.Rough set approach to incomplete information systems[J].Information Sciences,1998,112(1-4):39-49
[10]Leung Yee,Wu Weizhi,Zhang Wenxiu.Knowledge acquisition in incomplete information systems:A rough set approach[J].European Journal of Operational Research,2006,168(1):164-180
[11]Li Deyu,Zhang Bo,Leung Yee.On knowledge reduction in inconsistent decision information systems[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2004,12(5):651-672
[12]Lin Tsau Young,Yao Yiyu,Zadeh L A.Data Mining,Rough Sets and Granular Computing[M].New York:Physica-Verlag,2002
[13]Miao Duoqian,Wang Guoyin,Liu Qing,et al.Granular Computing:Past,Present and Future[M].Beijing:Science Press,2007(in Chinese)(苗夺谦,王国胤,刘清,等.粒计算的过去、现在与展望[M].北京:科学出版社,2007)
[14]Miao Duoqian,Li Deyi,Yao Yiyu,et al.Uncertainty and Granular Computing[M].Beijing:Science Press,2011(in Chinese)(苗夺谦,李德毅,姚一豫,等.不确定性与粒计算[M].北京:科学出版社,2011)
[15]Pedrycz W,Skowron A,Kreinovich V.Handbook of Granular Computing[M].New York:Wiley,2008
[16]Shao Mingwen,Zhang Wenxiu.Dominance relation and rules in an incomplete ordered information system[J].International Journal of Intelligent Systems,2005,20(1):13-27
[17]Shi Qianyu,Liang Jiye,Zhao Xingwang.A clustering ensemble algorithm for incomplete mixed data[J].Journal of Computer Research and Development,2016,53(9):1979-1989(in Chinese)(史倩玉,梁吉业,赵兴旺.一种不完备混合数据集成聚类算法[J].计算机研究与发展,2016,53(9):1979-1989)
[18]Sun Bingzhen,Ma Weimin,Gong Zengtai.Dominance-based rough set theory over interval-valued information systems[J].Expert Systems,2014,31(2):185-197
[19]Zhang Wei,Miao Duoqian,Gao Can,et al.A neighborhood rough sets-based co-training model for classification[J].Journal of Computer Research and Development,2014,51(8):1811-1820(in Chinese)(张维,苗夺谦,高灿,等.邻域粗糙协同分类模型[J].计算机研究与发展,2014,51(8):1811-1820)
[20]Pawlak Z.Rough Sets:Theoretical Aspects of Reasoning about Data[M].Amsterdam,Netherlands:Kluwer Academic Publishers,1991
[21]Qian Yuhua,Liang Jiye,Yao Yiyu,et al.MGRS:A multigranulation rough set[J].Information Sciences,2010,180(6):949-970
[22]Qian Yuhua,Liang Jiye,Dang Chuangyin.Incomplete multigranulation rough set[J].IEEE Trans on Systems,Man and Cybernetics,2010,40(2):420-431
[23]Yang Xibei,Song Xiaoning,Chen Zehua.On multigranulation rough sets in incomplete information system[J].International Journal of Machine Learning and Cybernetics,2012,3(3):223-232
[24]Wu Weizhi,Leung Yee.Theory and applications of granular labeled partitions in multi-scale decision tables[J].Information Sciences,2011,181(18):3878-3897
[25]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)
[26]Dai Zhicong,Wu Weizhi.Rough approximations in incomplete multi-granular ordered information systems[J].Journal of Nanjing University:Natural Sciences,2015,51(2):361-367(in Chinese)(戴志聪,吴伟志.不完备多粒度序信息系统的粗糙近似[J].南京大学学报:自然科学版,2015,51(2):361-367)
[27]Wu Weizhi,Leung Yee.Optimal scale selection for multiscale decision tables[J].International Journal of Approximate Reasoning,2013,54(8):1107-1129
[28]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)
[29]Wu Weizhi,Chen Chaojun,Li Tongjun,et al.A comparative study on optimal granularities in inconsistent multi-granular labeled decision systems[J].Pattern Recognition and Artificial Intelligence,2016,29(12):1103-1111(in Chinese)(吴伟志,陈超君,李同军,等.不协调多粒度标记决策系统最优粒度的对比[J].模式识别与人工智能,2016,29(12):1103-1111)
[30]She Yanhong,Li Jinhai,Yang Hailong.A local approach to rule induction in multi-scale decision tables[J].KnowledgeBased Systems,2015,89:398-410
[31]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
[32]Gu Shenming,Wu Weizhi.Knowledge acquisition in inconsistent multi-scale decision systems[G]//LNAI 6964:Proc of the 6th Int Conf on Rough Sets and Knowledge Technology.Berlin:Springer,2011:669-678
[33]Wu Weizhi,Qian Yuhua,Li Tongjun,et al.On rule acquisition in incomplete multi-scale decision tables[J].Information Sciences,2017,378:282-302
[34]Li Feng,Hu Baoqing.A new approach of optimal scale selection to multi-scale decision tables[J].Information Sciences,2017,381:193-208
[35]Wu Weizhi.Attribute reduction based on evidence theory in incomplete decision systems[J].Information Sciences,2008,178(5):1355-1371