Influence of dynamical changes on concept lattice and implication rules
- PDF / 990,845 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 0 Downloads / 220 Views
ORIGINAL ARTICLE
Influence of dynamical changes on concept lattice and implication rules Huilai Zhi1 • Jinhai Li2
Received: 2 May 2016 / Accepted: 22 September 2016 Ó Springer-Verlag Berlin Heidelberg 2016
Abstract Concept lattices are widely used as a knowledge structure in many real-life applications and the updating of a formal context is inevitable in most cases. How to effectively update the corresponding concept lattice as well as the embodied implication rules is still an open, interesting and important problem. The main objective of this paper is to give a solution to this problem. At first, we prove that in the updating process of the present concept lattice, whether to create a new concept and where to insert the new concept are solely determined by the lately created concepts or modified ones. And then, based on this finding, we propose an algorithm for the updating of concept lattice. Moreover, we carry out time complexity analysis and conduct experiments to show the effectiveness of our algorithm. Finally, we put forward some useful strategies for the updating of implication rules based on minimal generators. Keywords Formal concept analysis Concept lattice Incremental algorithm Implication rule
& Jinhai Li [email protected] Huilai Zhi [email protected] 1
School of Computer Science and Technology, Henan Polytechnic University, Jiaozuo 454000, Henan, People’s Republic of China
2
Faculty of Science, Kunming University of Science and Technology, Kunming 650500, Yunnan, People’s Republic of China
1 Introduction Formal concept analysis (FCA), proposed by Wille [45] in the early 1980s, is an effective method for analysis of object-attribute relational data and knowledge representation [35]. FCA provides relationships between generalization and specialization of formal concepts with a concept lattice and it is an important mathematical tool for human-level concept learning. Up to now, FCA has been applied to a variety of fields such as data mining [7, 13–16], knowledge representation and discovery [5, 6, 12, 26, 30–34, 51], and granular computing [20, 21, 24, 44, 46, 48, 49]. However, FCA-based real-life applications also face many challenges due to the dynamic changes of formal contexts. When adding new instances, concept lattices may grow extremely large in most cases and it has been proved that generating all formal concepts is a NP-hard problem [2, 18, 19]. Therefore, how to effectively deal with large and dynamic formal contexts has become a challenging and popular research topic. Facing dynamic formal contexts, incremental algorithms such as Godin’s approach [9], Object Intersection [4] and AddIntent [28], may often be a better choice in most occasions, since they reflect the additional changes only by making local alterations of the current concept lattice. Up to now, many efforts have been made to improve the performance [27, 38, 54]. However, due to the NP-complete problem, there is still room for further refinement, including the problems such as how to reduce the search space when we d
Data Loading...
