An Algorithm using Context Reduction for Efficient Incremental Generation of Concept Set

Article type: Research Article

Authors: Kovács, László^{; *; †}

Correspondence: [†] Address for correspondence: Miskolci Egyetem, Informatikai Intézet, H-3515 Miskolc-Egyetemváros, Hungary.

Note: [*] The author thanks Sándor Radeleczki and the anonymous referees for constructive comments and valuable suggestions.

Abstract: The theory of Formal Concept Analysis (FCA) provides efficient methods for conceptualization of formal contexts. The methods of FCA are applied mainly on the field of knowledge engineering and data mining. The key element in FCA applications is the generation of a concept set. The main goal of this research work is to develop an efficient incremental method for the construction of concept sets. The incremental construction method is used for problems where context may change dynamically. The paper first proposes a novel incremental concept set construction algorithm called ALINC, where the insertion loop runs over the attribute set. The combination of object-level context processing and ALINC is an object level incremental algorithm (OALINC) where the context is built up object by object. Based on the performed tests, OALINC dominates the other popular batch or incremental methods for sparse contexts. For dense contexts, the OINCLOSE method, which uses the InClose algorithm for processing of reduced contexts, provides a superior efficiency. Regarding the OALINC/OINCLOSE algorithms, our test results with uniform distribution and real data sets show that our method provides very good performance in the full investigated parameter range. Especially good results are experienced for symmetric contexts in the case of word clustering using context-based similarity.

Keywords: Formal Concept Analysis, concept set, incremental concept set generation, InClose method

DOI: 10.3233/FI-2019-1776

Journal: Fundamenta Informaticae, vol. 165, no. 1, pp. 43-73, 2019