期刊文献+

多概念格的横向合并算法 被引量:50

Horizontal Union Algorithm of Multiple Concept Lattices
下载PDF
导出
摘要 由于概念格自身的完备性 ,构造概念格的时间复杂度一直是影响形式概念分析应用的主要因素 .本文首先从形式背景的纵向、横向合并出发 ,定义了内涵独立和内涵一致的形式背景和概念格 ;还定义了内涵一致的形式背景、概念的横向加运算和概念格的横向并运算 ,并证明了横向合并的子形式背景的概念格和子背景所对应的子概念格的横向并是同构的 .最后结合子概念格中概念间固有的泛化 -特化关系 ,提出一种多概念格的横向合并算法来构造概念格 .试验表明 ,该算法和直接用形式背景来构造概念格的算法相比 ,其时间复杂度有显著改善 .显然 。 Since the completeness of concept lattice, the time complexity of building concept lattice is a factor restricting the application of formal concept analysis. Based on the horizontal and vertical combination in formal contexts, this paper defines the independent or consistent contexts and lattices in attribute field; and also defines the horizontal addition operation between contexts or concepts and the horizontal union operation between concept lattices. In addition, we prove that the concept lattice of subcontexts horizontally combined is isomorphic to the horizontal union of sublattices of these subcontexts. Using the inherent general-special relation between concepts in sublatrice, the horizontal union algorithm of multiple concept lattices to construct the concept lattice is also presented. Experimental results show that the time complexity of this algorithm is much better than that of other construction algorithm of concept lattice from whole formal context. Evidently, our algorithm is very suitable for constructing concept lattice in parallel and distributed system.
出处 《电子学报》 EI CAS CSCD 北大核心 2004年第11期1849-1854,共6页 Acta Electronica Sinica
基金 国家自然科学基金项目 (No.60 2 750 2 2 )
关键词 概念格 形式背景 子格 子背景 横向合并 Algorithms Combinatorial mathematics Computational complexity Distributed parameter control systems Formal logic Theorem proving
  • 相关文献

参考文献8

  • 1Ganter B,Wille R.Formal Concept Analysis:Mathematical Foundations[M].Berlin:Springer-Verlag,1999.
  • 2Baltasar Fernandez-Manjon,Alfredo Fernandez-Valmayor.Building educational tools based on formal concept analysis[J].Education and Information Technologies,1998,3(3-4):187-201.
  • 3U Krohn,N J Davies,R Weeks.Concept lattices for knowledge management[J].BT Technol J,1999,17(4):108-113.
  • 4S O Kuznetsov.Machine learning on the basis of formal concept analysis[J].Automation and Remote Control,2001,62(10):1543-1564.
  • 5Godin R,Missaoui R,Alaoui H.Incremental concept formation algorithms based on Galois (concept) lattices[J].Computational Intelligence,1995,11(2):246-267.
  • 6Sergei O Kuznetsov,Sergei A Obiedkov.Algorithms for the construction of concept lattices and their diagram graphs[A].PKDD 2001,LNAI 2168[C].Freiburg:Springer-Verlag Heidelberg,2001.289-300.
  • 7Yun Li,Zongtian Liu,et al.Theoretical research on the distributed construction of concept lattices[A].Proceedings of the Second International Conference on Machine Learning and Cybernetics[C].Xian:Institude of Electrical and Electronics,2003.474-479.
  • 8Zongtian Liu,Liangsheng Li,Qing Zhang.Research on a union algorithm of multiple concept lattices[A].RSFDGrC 2003,LNAI 2639[C].Berlin:Springer-Verlag Heidelberg,2003.533-540.

同被引文献413

引证文献50

二级引证文献152

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部