基于覆盖度函数的概念格约简

姜峰; 范玉顺

doi:10.3724/SP.J.1146.2009.00099

基于覆盖度函数的概念格约简

doi: 10.3724/SP.J.1146.2009.00099

姜峰,
范玉顺

计量
- 文章访问数: 3742
- HTML全文浏览量: 94
- PDF下载量: 929
- 被引次数: 0
出版历程
- 收稿日期: 2009-01-19
- 修回日期: 2009-06-29
- 刊出日期: 2010-02-19

Coverage Density Based Approach for Concept Lattice Reduction

摘要

摘要: 该文针对基于概念格的大规模数据和规则挖掘中，概念节点数呈指数爆炸的问题，提出了概念覆盖度函数和概念格度量模型，进行概念格约简，从而使生成的标示概念格具有线性空间复杂度。给出了概念格约简的直求法、同步法和提取法3种算法。时空复杂度分析和仿真试验表明，所提方法可以大幅约简概念格规模，从而显著提高建格和规则挖掘效率。标示概念还具有特殊含义，在Web服务关系挖掘中有很好的应用。
- 数据挖掘; 形式概念分析; 概念格; 约简; Web关系挖掘
Abstract: To address the lattice size exponential explosion problem in large scale data and rule mining, concept coverage density function and measurement model are introduced to reduce redundant concepts. The pruned lattice, named marked-concept lattice, has linear space complexity and can be obtained through direct or synchronous construction or node-extraction. Analysis and simulation tests show that this reduction model not only significantly reduces normal concept lattice size, but also significantly improves lattice building and rule mining efficiency. Furthermore, marked concept carries crucial information and physical meanings, thus can make benefits for Web service relationship mining.

HTML全文

参考文献(1)

Ganter B and Wille R. Formal Concept Analysis Mathematical Foundations [M]. Berlin: Springer Press, 1999: 17-35.[2]Kuznetsov S O. Machine learning and formal concept analysis [J]. Lecture Notes in Computer Science, 2004, 2961: 3901-3926.[3]Hesse W and Tilley T. Formal concept analysis used for software analysis and modeling [J].Lecture Notes in Computer Science.2005, 3626:288-303[4]Laukaitis A and Vasilecas O. Formal concept analysis for business information systems [J]. Information Technology and Control, 2008, 37(1): 33-37.[5]Yahia S B and Jaoua A. Discovering Knowledge from Fuzzy Concept Lattice [M]. Kandel A, Last M, Bunke H edits: Data Mining and Computational Intelligence. Heidelberg: Springer Press, 2001: 167-190.[6]谢志鹏, 刘宗田. 概念格的快速渐进式构造算法[J]. 计算机学报, 2002, 25(5): 490-496. Xie Zhi-peng and Liu Zong-tian. A fast incremental algorithm for building concept lattice [J]. Chinese Journal of Computers, 2002, 25(5): 490-496.[7]蒋义勇, 张继福, 张素兰. 基于链表结构的概念格渐进式构造[J]. 计算机工程与应用, 2007, 43(11): 178-180.[8]Jiang Yi-yong, Zhang Ji-fu, and Zhang Su-lan. Incremental construction of concept lattice based on linked list structure [J]. Computer Engineering and Applications, 2007, 43(11):[9]8-180.[10]Fu H G and Nguifo E M. A parallel algorithm to generate formal concepts for large data [J]. Lecture Notes in Artificial Intelligence, 2004, 2961: 394-401.[11]刘利峰, 吴孟达, 王丹. 基于属性约简的概念格构造[J]. 计算机工程与科学, 2007, 29(6): 140-142.Liu Li-feng, Wu Meng-da, and Wang Dan. Building concept lattices based on attribute reduction [J].Computer Engineering Science.2007, 29(6):140-142[12]Formica A. Concept similarity in formal concept analysis: an information content approach [J].Knowledge-Based Systems.2008, 21(1):80-87[13]郭耀煌, 刘家诚, 刘常青等. 格序决策[M]. 上海: 上海科学技术出版社, 2003: 15.[14]Guo Yao-huang.[J].Liu Jia-cheng, and Liu Chang-qing, et al.. Lattice Decision [M]. Shanghai: Shanghai Science Technology Press.2003,:-[15]Godin R, Missaouir R, and Alaout H. Incremental concept formation algorithms based on Galois (concept) Lattices [J].Computational Intelligence.1995, 11(2):246-267[16]张玲, 林亚平, 陈治平等. 基于综合价值的Web主题信息搜集策略研究[J]. 系统仿真学报, 2005, 17(2): 323-326.Zhang Ling, Lin Ya-ping, and Chen Zhi-ping, et al.. Research of searching strategy in Web topic crawler [J]. Acta Simulata Systematica Sinica, 2005, 17(2): 323-326.[17]夏海江, 吴健, 邓水光. 基于序列挖掘的Web服务推荐研究. 计算机应用研究, 2007, 24(6): 75-78.Xia Hai-jiang, Wu Jian, and Deng Shui-guang. Research on recommendation of Web services based on sequence mining [J]. Application Research of Computers, 2007, 24(6): 75-78.[18]吴江霞, 杨放春. 支持事务机制的Web服务组合QoS属性预测方法[J].电子与信息学报.2008, 30(3):703-706浏览Wu Jiang-xia and Yang Fang-chun. QoS prediction of Web service composition with transaction mechanism [J].Journal of Electronics Information Technology.2008, 30(3):703-706[19]Davidov D, Rappoport A, and Koppel M. Fully unsupervised discovery of concept-specific relationships by Web mining [C]. 45th Annual Meeting of the Association of Computational Linguistics, Prague, Czech Republic, June 23-30, 2007: 232-239.

施引文献

资源附件(0)

访问统计