您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(理学版)》

《山东大学学报(理学版)》 ›› 2019, Vol. 54 ›› Issue (2): 30-40.doi: 10.6040/j.issn.1671-9352.9.2018.002

• • 上一篇    

形式概念分析的多粒度标记理论

李金海1,2,吴伟志3,4,邓硕1,2   

  1. 1. 昆明理工大学数据科学研究中心, 云南 昆明 650500;2. 昆明理工大学理学院, 云南 昆明 650500;3. 浙江海洋大学数理与信息学院, 浙江 舟山 316022;4. 浙江海洋大学浙江省海洋大数据挖掘与应用重点实验室, 浙江 舟山 316022
  • 发布日期:2019-02-25
  • 作者简介:李金海(1984— ),男,博士,教授,博士生导师,研究方向为粗糙集、概念格与粒计算. E-mail: jhlixjtu@163.com
  • 基金资助:
    国家自然科学基金资助项目(61562050,61573173,61573321,41631179);浙江省海洋大数据挖掘与应用重点实验室开放课题资助项目(OBDMA201502)

Multi-scale theory in formal concept analysis

LI Jin-hai1,2, WU Wei-zhi3,4, DENG Shuo1,2   

  1. 1. Data Science Research Center, Kunming University of Science and Technology, Kunming 650500, Yunnan, China;
    2. Faculty of Science, Kunming University of Science and Technology, Kunming 650500, Yunnan, China;
    3. School of Mathematics, Physics and Information Science, Zhejiang Ocean University, Zhoushan 316022, Zhejiang, China;
    4. Key Laboratory of Oceanographic Big Data Mining and Application of Zhejiang Province, Zhejiang Ocean University, Zhoushan 316022, Zhejiang, China
  • Published:2019-02-25

摘要: 通过正向尺度化和反向尺度化方法,研究信息系统与形式背景之间的相互转化关系,利用经典形式背景给出多粒度标记形式背景的定义,证明多粒度标记形式背景与多粒度标记信息系统在语义上等价。对于多粒度标记形式背景,不同粒度标记下的蕴涵规则之间可以相互推理。所得结论为今后进一步研究形式概念分析的多粒度标记方法提供了理论基础。

关键词: 粒计算, 粗糙集, 概念格, 形式背景, 多粒度标记

Abstract: By using forward and backward scaling approaches, the transformation relationship between information systems and formal contexts was clarified, and the notion of a multi-scale formal context was formally defined. It was verified that multi-scale formal contexts and multi-scale information systems could semantically be equivalent to each other. As for a multi-scale formal context, implication rules obtained from different scales were induced by each other. The obtained results could provide a theoretical reference for the further research of multi-scale approaches in formal concept analysis.

Key words: granular computing, rough set, concept lattice, formal context, multi-scale

中图分类号: 

  • TP18
[1] WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[C] //Ordered Sets. Berlin: Springer, 1982: 445-470.
[2] PAWLAK Z. Rough sets[J]. International Journal of Computer and Information Sciences, 1982, 11(5): 341-356.
[3] YAO Yiyu. Concept lattices in rough set theory[C] //Proceedings of 2004 Annual Meeting of the North American Fuzzy Information Processing Society. Washington: IEEE, 2004: 796-801.
[4] YAO Yiyu. A comparative study of formal concept analysis and rough set theory in data analysis [C] //Proceedings of 4th International Conference on Rough Sets and Current Trends in Computing(RSCTC 2004). Berlin: Springer, 2004: 59-68.
[5] DUNTSCH I, GEDIGA G. Modal-style operators in qualitative data analysis[C] //Proceedings of the 2002 IEEE International Conference on Data Mining. Washington: IEEE, 2002: 155-162.
[6] MEDINA J. Relating attribute reduction in formal, object-oriented and property-oriented concept lattices[J]. Computers and Mathematics with Applications, 2012, 64(6):1992-2002.
[7] YAO Yiyu. Rough-set concept analysis: interpreting RS-definable concepts based on ideas from formal concept analysis [J]. Information Sciences, 2016, 346-347: 442-462.
[8] 智慧来, 李金海. 基于必然属性分析的粒描述[J]. 计算机学报, 2018, 41(12):2702-2719. ZHI Huilai, LI Jinhai. Granule description based on necessary attribute analysis[J]. Chinese Journal of Computers, 2018, 41(12):2702-2719.
[9] CHEN Jinkun, LI Jinjin, LIN Yaojin, et al. Relations of reduction between covering generalized rough sets and concept lattices[J]. Information Sciences, 2015, 304: 16-27.
[10] TAN Anhui, LI Jinjin, LIN Guoping. Connections between covering-based rough sets and concept lattices[J]. International Journal of Approximation Reasoning, 2015, 56: 43-58.
[11] WANG Xia, ZHANG Wenxiu. Relations of attribute reduction between object and property oriented concept lattice [J]. Knowledge-Based Systems, 2008, 21(5): 398-403.
[12] 魏玲, 祁建军, 张文修. 概念格与粗糙集的关系研究[J]. 计算机科学, 2006, 33(3):18-21. WEI Ling, QI Jianjun, ZHANG Wenxiu. Study on relationships between concept lattice and rough set[J]. Computer Science, 2006, 33(3): 18-21.
[13] 王俊红, 梁吉业. 概念格与粗糙集[J]. 山西大学学报(自然科学版), 2003, 26(4): 307-310. WANG Junhong, LIANG Jiye. Concept lattice and rough set [J]. Journal of Shanxi University(Natural Science Edition), 2003, 26(4): 307-310.
[14] 仇国芳, 张志霞, 张炜.基于粗糙集方法的概念格理论研究综述[J]. 模糊系统与数学, 2014, 28(1): 168-177. QIU Guofang, ZHANG Zhixia, ZHANG Wei. A survey for study on concept lattice theory via rough set[J]. Fuzzy Systems and Mathematics, 2014, 28(1): 168-177.
[15] 张文修, 姚一豫, 梁怡. 粗糙集与概念格[M]. 西安: 西安交通大学出版社, 2006. ZHANG Wenxiu, YAO Yiyu, LIANG Yi. Rough set and concept lattice[M]. Xian: Xian Jiaotong University Press, 2006.
[16] 徐伟华, 李金海, 魏玲, 等. 形式概念分析理论与应用[M]. 北京: 科学出版社, 2016. XU Weihua, LI Jinhai, WEI Ling, et al. Formal concept analysis: theory and application[M]. Beijing: Science Press, 2016.
[17] ZADEH L A.Toward 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.
[18] LIN T Y. Granular computing on binary relations I: data mining and neighborhood systems[C] //Rough Sets in Knowledge Discovery. Berlin: Spring, 1998: 107-121.
[19] YAO Yiyu. Information granulation and rough set approximation[J]. International Journal of Intelligent Systems, 2001, 16: 87-104.
[20] PEDRYCZ W, SKOWRON A, KREINOVICH V. Handbook of granular computing[M]. New York: Wiley, 2008.
[21] 苗夺谦, 王国胤, 刘清, 等. 粒计算: 过去、现在与展望[M]. 北京: 科学出版社, 2007. MIAO Duoqian, WANG Guoyin, LIU Qing, et al. Granular computing: past, present and fature[M]. Beijing: Science Press, 2007.
[22] 苗夺谦, 徐菲菲, 姚一豫, 等. 粒计算的集合论描述[J]. 计算机学报, 2012, 35(2): 2351-2363. MIAO Duoqian, XU Feifei, YAO Yiyu, et al. Set-theoretic formulation of granular computing[J]. Chinese Journal of Computers, 2012, 35(2): 2351-2363.
[23] 梁吉业, 钱宇华, 李德玉, 等. 大数据挖掘的粒计算理论与方法[J].中国科学(信息科学), 2015, 45(11): 1355-1369. LIANG Jiye, QIAN Yuhua, LI Deyu, et al. Theory and method of granular computing for big data mining [J]. Science China(Information Sciences), 2015, 45(11): 1355-1369.
[24] 王国胤, 张清华, 马希骜, 等. 知识不确定性问题的粒计算模型[J]. 软件学报, 2011, 22(4): 676-694. WANG Guoyin, ZHANG Qinghua, MA Xi’ao, et al. Granular computing models for knowledge uncertainty [J]. Journal of Software, 2011, 22(4): 676-694.
[25] 徐计, 王国胤, 于洪. 基于粒计算的大数据处理[J]. 计算机学报, 2015, 38(8): 1497-1517. 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.
[26] 张燕平, 张铃, 吴涛.不同粒度世界的描述法——商空间法[J]. 计算机学报, 2004, 27(3): 238-333. ZHANG Yanping, ZHANG Ling, WU Tao. The representation of different granular worlds: a quotient space [J]. Chinese Journal of Computers, 2004, 27(3): 238-333.
[27] MA Jianmin, ZHANG Wenxiu, LEUNG Yee, et al. Granular computing and dual Galois connection[J]. Information Sciences, 2007, 177(23): 5365-5377.
[28] WU Weizhi, LEUNG Yee, MI Jusheng. Granular computing and knowledge reduction in formal contexts[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(10): 1461-1474.
[29] LI Jinhai, MEI Changlin, CHERUKURI A K, et al. On rule acquisition in decision formal contexts[J]. International Journal of Machine Learning and Cybernetics, 2013, 4(6): 721-731.
[30] GUO Lankun, HUANG Fangping, LI Qingguo, et al. Power contexts and their concept lattices[J]. Discrete Mathematics, 2011, 311: 2049-2063.
[31] WEI Ling, WAN Qing. Granular transformation and irreducible element judgment theory based on pictorial diagrams[J]. IEEE Transactions on Cybernetics, 2017, 46(2): 380-387.
[32] KANG Xiangping, MIAO Duoqian. A variable precision rough set model based on the granularity of tolerance relation [J]. Knowledge-Based Systems, 2016, 102: 103-115.
[33] 马垣, 曾子维, 迟呈英, 等. 形式概念及其新进展[M]. 北京: 科学出版社, 2011. MA Yuan, ZENG Ziwei, CHI Chengying, et al. Formal concept and its new progress[M]. Beijing: Science Press, 2011.
[34] LI Jinhai, REN Yue, MEI Changlin, et al. A comparative study of multigranulation rough sets and concept lattices via rule acquisition[J]. Knowledge-Based Systems, 2016, 91: 152-164.
[35] SHAO Mingwen, LEUNG Yee, WANG Xizhao, et al. Granular reducts of formal fuzzy contexts[J]. Knowledge-Based Systems, 2016, 114: 156-166.
[36] ZHANG Qinghua, XING Yuke. Formal concept analysis based on granular computing[J]. Journal of Computational Information Systems, 2010, 6(7): 2287-2296.
[37] 张文修, 徐伟华. 基于粒计算的认知模型[J]. 工程数学学报, 2008, 24(6): 957-971. ZHANG Wenxiu, XU Weihua. Cognitive model based on granular computing[J]. Chinese Journal of Engineering Mathematics, 2007, 24(6): 957-971.
[38] XU Weihua, PANG Jinzhong, LUO Shuqun. A novel cognitive system model and approach to transformation of information granules[J]. International Journal of Approximate Reasoning, 2014, 55(3): 853-866.
[39] XU Weihua, LI Wentao. Granular computing approach to two-way learning based on formal concept analysis in fuzzy datasets[J]. IEEE Transactions on Cybernetics, 2016, 46(2): 366-379.
[40] QIAN Yuhua, LIANG Jiye, YAO Yiyu, et al. MGRS: a multi-granulation rough set[J]. Information Sciences, 2010, 180: 949-970.
[41] QIAN Yuhua, LI Shunyong, LIANG Jiye, et al. Pessimistic rough set based decisions: a multigranulation fusion strategy [J]. Information Sciences, 2014, 264: 196-210.
[42] WU Weizhi, LEUNG YEE. Theory and applications of granular labeled partitions in multi-scale decision tables[J]. Information Sciences, 2011, 181: 3878-3897.
[43] WU Weizhi, QIAN Yuhua, LI Tongjun, et al. On rule acquisition in incomplete multi-scale decision tables[J]. Information Sciences, 2017, 378: 282-302.
[44] SHE Yanhong, LI Jinhai, YANG Hailong. A local approach to rule induction in multi-scale decision tables[J]. Knowledge-Based Systems, 2015, 89: 398-410.
[45] LI Feng, HU Baoqing. A new approach of optimal scale selection to multi-scale decision tables[J]. Information Sciences, 2017, 381: 193-208.
[46] LI Feng, HU Baoqing, WANG Jun. Stepwise optimal scale selection for multi-scale decision tables via attribute significance[J]. Knowledge-Based Systems, 2017, 129: 4-16.
[47] HAO Chen, LI Jinhai, FAN Min, et al. Optimal scale selection in dynamic multi-scale decision tables based on sequential three-way decisions[J]. Information Sciences, 2017, 415/416: 213-232.
[48] LUO Chuan, LI Tianrui, HUANG Yanyong, et al. Updating three-way decisions in incomplete multi-scale information systems[J]. Information Sciences, 2019, 476: 274-289.
[49] 吴伟志, 高仓健, 李同军. 序粒度标记结构及其粗糙近似[J]. 计算机研究与发展, 2014, 51(12): 2623-2632. 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.
[50] 顾沈明, 顾金燕, 吴伟志, 等. 不完备多粒度决策系统的局部最优粒度选择[J]. 计算机研究与发展, 2017, 54(7): 1500-1509. GU Shenming, GU Jinyan, WU Weizhi, et al. Local optimal granularity selections in incomplete multi-granular decision systems[J]. Journal of Computer Research and Development, 2017, 54(7): 1500-1509.
[51] 李金海, 吴伟志. 形式概念分析的粒计算方法及其研究展望[J]. 山东大学学报(理学版), 2017, 52(7): 1-12. LI Jinhai, WU Weizhi. Granular computing approach for formal concept analysis and its research outlooks[J]. Journal of Shandong University(Natural Science), 2017, 52(7): 1-12.
[52] 郝晨, 范敏, 李金海, 等. 多标记背景下基于粒标记规则的最优标记选择[J]. 模式识别与人工智能, 2016, 29(3): 272-280. HAO Chen, FAN Min, LI Jinhai, et al. Optimal scale selection in multi-scale contexts based on granular scale rules[J]. Pattern Recognition and Artificial Intelligence, 2016, 29(3): 272-280.
[53] XIE Junping, YANG Minhua, LI Jinhai, et al. Rule acquisition and optimal scale selection in multi-scale formal decision contexts and their applications to smart city[J]. Future Generation Computer Systems, 2018, 83: 564-581.
[54] BELOHLAVEK R, DE BAETS B, KONECNY J. Granularity of attributes in formal concept analysis[J]. Information Sciences, 2014, 260: 149-170.
[55] 曾望林, 折延宏. 面向对象的多粒度形式概念分析[J]. 计算机科学, 2018, 45(10): 51-53. ZENG Wanglin, SHE Yanhong. Object-oriented multigranulation formal concept analysis[J]. Computer Science, 2018, 45(10): 51-53.
[56] 张文修, 仇国芳. 基于粗糙集的不确定决策[M]. 北京:清华大学出版社, 2005. ZAHG Wenxiu, QIU Guofang. Uncertain decision making based on rough set[M]. Beijing: Tshinghua University Press, 2005.
[57] QU Kaishe, ZHAI Yanhui, LIANG Jiye, et al. Study of decision implications based on formal concept analysis[J]. International Journal of General Systems, 2007, 36(2): 147-156.
[58] GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. New York: Springer, 1999.
[59] QI Jianjun, WEI Ling, YAO Yiyu. Three-way formal concept analysis[C] //Rough Sets and Knowledge Technology. Berlin: Springer, 2014: 732-741.
[60] 米允龙, 李金海, 刘文奇,等. MapReduce框架下的粒概念认知学习系统研究[J].电子学报, 2018,46(2):289-297. MI Yunlong, LI Jinhai, LIU Wenqi, et al. Research on granular concept cognitive learning system under MapReduce framework [J]. Acta Electronica Sinica, 2018, 46(2):289-297.
[61] LI Jinhai, MEI Changlin, L(¨overU)Yuejin. Knowledge reduction in decision formal contexts [J]. Knowledge-Based Systems, 2011, 24(5): 709-715.
[62] LI Jinhai, HUANG Chenchen, MEI Changlin, et al. An intensive study on rule acquisition in formal decision contexts based on minimal closed label concept lattices[J]. Intelligent Automation & Soft Computing, 2017, 23(3): 519-533.
[1] 李同军,黄家文,吴伟志. 基于相似关系的不完备形式背景属性约简[J]. 山东大学学报(理学版), 2018, 53(8): 9-16.
[2] 左芝翠,张贤勇,莫智文,冯林. 基于决策分类的分块差别矩阵及其求核算法[J]. 山东大学学报(理学版), 2018, 53(8): 25-33.
[3] 张恩胜. 区间集概念格属性约简的组成与结构[J]. 山东大学学报(理学版), 2018, 53(8): 17-24.
[4] 任睿思,魏玲,祁建军. 三支弱协调决策形式背景的规则获取[J]. 山东大学学报(理学版), 2018, 53(6): 76-85.
[5] 张晓,杨燕燕. 覆盖决策系统的规则提取和置信度保持的属性约简算法[J]. 《山东大学学报(理学版)》, 2018, 53(12): 120-126.
[6] 李丽,管涛,林和. 基于泛系算子的泛系混合并联粗糙集模型[J]. 山东大学学报(理学版), 2017, 52(7): 22-29.
[7] 李金海,吴伟志. 形式概念分析的粒计算方法及其研究展望[J]. 山东大学学报(理学版), 2017, 52(7): 1-12.
[8] 黄桃林,牛娇娇,李金海. 基于粒辨识属性矩阵的动态形式背景约简更新方法[J]. 山东大学学报(理学版), 2017, 52(7): 13-21.
[9] 胡谦,米据生,李磊军. 多粒度模糊粗糙近似算子的信任结构与属性约简[J]. 山东大学学报(理学版), 2017, 52(7): 30-36.
[10] 汪小燕,沈家兰,申元霞. 基于加权粒度和优势关系的程度多粒度粗糙集[J]. 山东大学学报(理学版), 2017, 52(3): 97-104.
[11] 刘琳,魏玲,钱婷. 决策形式背景中具有置信度的三支规则提取[J]. 山东大学学报(理学版), 2017, 52(2): 101-110.
[12] 陈雪,魏玲,钱婷. 基于AE-概念格的决策形式背景属性约简[J]. 山东大学学报(理学版), 2017, 52(12): 95-103.
[13] 黄伟婷,赵红,祝峰. 代价敏感属性约简的自适应分治算法[J]. 山东大学学报(理学版), 2016, 51(8): 98-104.
[14] 覃丽珍, 李金海, 王扬扬. 基于概念格的知识发现及其在高校就业数据分析中的应用[J]. 山东大学学报(理学版), 2015, 50(12): 58-64.
[15] 张春英, 王立亚, 刘保相. 基于覆盖的区间概念格动态压缩原理与实现[J]. 山东大学学报(理学版), 2014, 49(08): 15-21.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!