计算机科学

计算机科学 ›› 2019, Vol. 46 ›› Issue (10): 236-241.doi: 10.11896/jsjkx.190200270

• 人工智能 • 上一篇    下一篇

一致决策信息系统规则提取的形式向量方法

延安1, 闫心怡1, 陈泽华2   

  1. (太原理工大学电气与动力工程学院 太原030024)1
    (太原理工大学大数据学院 太原030024)2
  • 收稿日期:2019-02-11 修回日期:2019-05-15 出版日期:2019-10-15 发布日期:2019-10-21
  • 通讯作者: 陈泽华(1974-),女,博士,教授,CCF高级会员,主要研究方向为粒计算、智能信息处理与应用、工业大数据,E-mail:zehuachen@163.com。
  • 作者简介:延安(1991-),男,硕士生,CCF会员,主要研究方向为数据挖掘与数据分析、区块链技术;闫心怡(1994-),女,硕士生,主要研究方向为数据挖掘与数据分析、工业大数据。
  • 基金资助:
    本文受国家自然科学基金(61402319),山西省自然科学基金(2014021022-4),山西省重点研发计划重点项目(201603D11200)资助。

Formal Vector Method of Rule Extraction for Consistent Decision Information System

YAN An1, YAN Xin-yi1, CHEN Ze-hua2   

  1. (College of Electrical and Power Engineering,Taiyuan University of Technology,Taiyuan 030024,China)1
    (College of Data Science,Taiyuan University of Technology,Taiyuan 030024,China)2
  • Received:2019-02-11 Revised:2019-05-15 Online:2019-10-15 Published:2019-10-21

PDF (PC)

625

摘要： 知识表示与获取是人工智能领域的关键问题之一,规则提取是其中的一项重要研究内容。形式概念分析是针对大数据和不确定性知识的有效处理方法,被广泛应用于知识表示和数据挖掘等领域。形式概念分析可以实现决策信息系统的规则提取,首先将决策信息系统转化为形式背景生成概念,进而通过概念运算获取规则。然而,概念的生成是一项复杂的运算过程,且生成的规则往往存在冗余属性。在形式背景的基础上,定义并讨论了形式向量及其性质,构建了形式向量树形拓扑图,提出了一种基于形式向量的决策信息系统最简规则快速提取算法。引入粒度的思想,由粗到细求取不同粒度空间下的形式向量,通过条件形式向量和决策形式向量的关系提取规则。基于树形拓扑图实现了规则提取过程的可视化,并且通过剪枝操作极大地减少了规则提取过程的实际时间开销。通过数学证明与实例分析验证了算法的正确性和有效性,通过对比实验证明了算法不仅具备更好的时效性而且具备较高的识别率。

关键词: 规则获取, 决策信息系统, 粒计算, 形式背景, 形式向量

Abstract: Knowledge representation and acquisition is one of the key problems in the field of artificial intelligence,and rule acquisition is one of the important research contents.Formal concept analysis is an effective method to deal with big data and uncertain knowledge,which is widely used in knowledge representation and data mining.Formal concept analysis can realize the rule extraction of decision information system.Firstly,the decision information system is transformed into the formal context,then the concept is generated by the formal context and the rules are acquired by concept operation.However,the generation of concepts is a complex computational process,and the generated rules are often redundant.On the basis of the formal context,the formal vector and its properties were defined and discussed,the tree topology diagram of formal vector was constructed,and a rule extraction algorithm of the decision information system based on the formal vector was proposed.The algorithm is based on granular computing,the formal vector in each layer from coarse to fine granularity space is computed,and the rules are extracted by the relationship between the conditional formal vectors and the decision formal vectors.The visualization of the rule extraction process is realized based on the tree topology diagram.And the actual time cost of the rule extraction process is greatly reduced by pruning operation.Finally,the correctness and effectiveness of the algorithm were verified by mathematical proof and case analysis.The comparison experiment also shows that the algorithm has better timeliness and higher recognition rate at the same time.

Key words: Decision information system, Formal context, Formal vector, Granular computing, Rule acquisition

中图分类号: 

  • TP181
[1]周志华.机器学习[M].北京:清华大学出版社,2016:1-22.
[2]WANG G Y,YAO Y Y,YU H.A survey on rough set theory and applications[J].Chinese Journal of Computers,2009,32(7):1229-1246.(in Chinese)
王国胤,姚一豫,于洪.粗糙集理论与应用研究综述[J].计算机学报,2009,32(7):1229-1246.
[3]WILLE R.Restructuring lattice theory:an approach based on hierarchies of concepts [M].Springer Netherlands:Spring Dordrecht,1982:445-470.
[4]GANTER B.Formal concept analysis:mathematical foundations[M].Berlin:Springer Verlag,1999.
[5]ZHANG J,WEI L.Rules acquisition and attribute reduction of ordered formal decision contexts[J].Pattern Recognition & Artificial Intelligence,2016,29(11):976-984.(in Chinese)
张菁,魏玲.序决策形式背景的规则提取及属性约简[J].模式识别与人工智能,2016,29(11):976-984.
[6]LI J H,HUANG C C,MEI C L,et al.An intensive study on rule acquisition in formal decision contexts based on minimal closed label concept lattices[J].Intelligent Automation & Soft Computing,2016,23(3):1-15.
[7]WEI L,QI J J,ZHANG W X.Attribute reduction theory of concept lattice based on decision formal contexts[J].Science in China (Series E:Information Sciences),2008,38(2):195-208.(in Chinese)
魏玲,祁建军,张文修.决策形式背景的概念格属性约简[J].中国科学E辑:信息科学,2008,38(2):195-208.
[8]LI J H.On rule acquisition in decision formal contexts[J].International Journal of Machine Learning & Cybernetics,2013,4(6):721-731.
[9]KANG X P,MIAO D Q.A study on information granularity in formal concept analysis based on concept-bases[J].Knowledge-Based Systems,2016,105:147-159.
[10]SHAO M W,LEUNG Y,WU W Z.Rule acquisition and complexity reduction in formal decision contexts[J].International Journal of Approximate Reasoning,2014,55(1):259-274.
[11]ZHAI Y H,LI D Y,QU K S.Decision implication canonical basis:a logical perspective[J].Journal of Computer & SystemScie-nces,2015,81(1):208-218.
[12]LI D Y,ZHANG S X,ZHAI Y H.Method for generating decision implication canonical basis based on true premises[J].International Journal of Machine Learning & Cybernetics,2017,8(1):57-67.
[13]XU W H,LI W T.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.
[14]PAWLAK Z.Rough sets[J].International Journal of Computer and Information Science,1982,11(5):341-356.
[15]张文修.信息系统与知识发现[M].北京:科学出版社,2003:7-33.
[16]LI X,WANG S G,LI D Y,et al.Knowledge acquisition in incomplete information system based on formal concept analysis[J].Computer Science,2014,41(7):250-253,260.(in Chinese)
李想,王素格,李德玉,等.形式概念分析在不完备信息系统中的知识获取[J].计算机科学,2014,41(7):250-253,260.
[17]WAN Q,WEI L.Approximate concepts acquisition based on formal contexts[J].Knowledge-Based Systems,2015,75:78-86.
[18]DAI J H,TIAN H W,WANG W T,et al.Decision rule mining using classification consistency rate[J].Knowledge-Based Systems,2013,43(2):95-102.
[19]CHEN Z H,ZHANG Y,XIE G.Mining algorithm for concise decision rules based on granular computing[J].Control and Decision,2015,30(1):143-148.(in Chinese)
陈泽华,张裕,谢刚.基于粒计算的最简决策规则挖掘算法[J].控制与决策,2015,30(1):143-148.
[20]CHEN Z H,ZHANG Y,XIE G.CrC method of rule acquisition for inconsistent decision table[J].Control and Decision,2015,30(4):709-714.(in Chinese)
陈泽华,张裕,谢刚.不一致决策表规则获取的粒计算方法[J].控制与决策,2015,30(4):709-714.
[1] 方连花, 林玉梅, 吴伟志.
随机多尺度序决策系统的最优尺度选择
Optimal Scale Selection in Random Multi-scale Ordered Decision Systems
计算机科学, 2022, 49(6): 172-179. https://doi.org/10.11896/jsjkx.220200067
[2] 温馨, 闫心怡, 陈泽华.
基于等价关系的最小乐观概念格生成算法
Minimal Optimistic Concept Generation Algorithm Based on Equivalent Relations
计算机科学, 2021, 48(3): 163-167. https://doi.org/10.11896/jsjkx.200100046
[3] 王霞, 彭致华, 李俊余, 吴伟志.
一种基于概念可辨识矩阵的概念约简方法
Method of Concept Reduction Based on Concept Discernibility Matrix
计算机科学, 2021, 48(1): 125-130. https://doi.org/10.11896/jsjkx.200800013
[4] 饶梦,苗夺谦,罗晟.
一种粗糙不确定的图像分割方法
Rough Uncertain Image Segmentation Method
计算机科学, 2020, 47(2): 72-75. https://doi.org/10.11896/jsjkx.190500177
[5] 林洪,秦克云.
决策形式背景基于三支决策规则的属性约简
Attribute Reduction for Decision Formal Contexts Based on Threek-way Decision Rules
计算机科学, 2019, 46(3): 248-252. https://doi.org/10.11896/j.issn.1002-137X.2019.03.037
[6] 李仲玲, 米据生, 解滨.
不协调决策形式背景的属性约简
Attribute Reduction in Inconsistent Decision Formal Contexts
计算机科学, 2019, 46(12): 257-260. https://doi.org/10.11896/jsjkx.181102137
[7] 郑书富,余高锋.
基于形式背景的属性转移与知识发现
Attribute Transfer and Knowledge Discovery Based on Formal Context
计算机科学, 2018, 45(6A): 117-119.
[8] 秦克云,林洪.
决策形式背景属性约简的关系
Relationships among Several Attribute Reduction Methods of Decision Formal Context
计算机科学, 2018, 45(4): 257-259. https://doi.org/10.11896/j.issn.1002-137X.2018.04.043
[9] 杨烽.
利用粒计算的符号型数据分组算法
Symbolic Value Partition Algorithm Using Granular Computing
计算机科学, 2018, 45(11A): 445-452.
[10] 常欣欣, 秦克云.
基于对象导出三支概念格的形式背景粒约简方法
Approach for Granular Reduction in Formal Context Based on Objects-induced Three-way Concept Lattices
计算机科学, 2018, 45(10): 225-228. https://doi.org/10.11896／j.issn.1002-137X.2018.10.041
[11] 任睿思, 魏玲, 祁建军.
三支类背景上的规则获取
Rules Acquisition on Three-way Class Contexts
计算机科学, 2018, 45(10): 21-26. https://doi.org/10.11896／j.issn.1002-137X.2018.10.004
[12] 姜玉婷, 秦克云.
决策形式背景面向属性与面向对象的决策规则
Property-oriented and Object-oriented Decision Rules in Decision Formal Contexts
计算机科学, 2018, 45(10): 33-36. https://doi.org/10.11896／j.issn.1002-137X.2018.10.006
[13] 林洪, 秦克云.
决策形式背景三支粒约简
Three-way Granular Reduction for Decision Formal Context
计算机科学, 2018, 45(10): 47-50. https://doi.org/10.11896／j.issn.1002-137X.2018.10.009
[14] 陈丽芳, 代琪, 付其峰.
基于粒计算的极限学习机模型设计与应用
Design and Application of Extreme Learning Machine Model Based on Granular Computing
计算机科学, 2018, 45(10): 59-63. https://doi.org/10.11896／j.issn.1002-137X.2018.10.012
[15] 尚奥,裴晓鹏,吕迎春,陈泽华.
基于等价关系的完全确定时序逻辑电路状态化简算法
State Reduction Algorithm for Completely Specified Sequential Logic Circuit Based on Equivalence Relation
计算机科学, 2018, 45(1): 118-121. https://doi.org/10.11896/j.issn.1002-137X.2018.01.019
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发