Efficient approximation for counting of formal concepts generated from formal context

Miskolc Mathematical Notes

L. Kovács¹ 

[1]University of Miskolc, Department of Information Technology, Miskolc-Egyetemváros, Hungary,

DOI  :  10.18514/MMN.2018.2529

学科分类：数学（综合）

来源: Miskolci Egyetem

【 摘 要 】

The number of formal concepts generated from the input context is an important parameter in the cost functions of concept formation algorithms.The calculation of concept count for any arbitrary context is a hard, NP-complete problem and only rough approximation methods can be found in the literature to solve this problem.This paper introduces an efficient numerical approximation algorithm for contexts whereattribute probabilities are independent from the objects instances. The preconditions required by the approximation method are usually met in theFCA applications, thus theproposed method provides an efficient tool for practical complexity analysis, too.

【 授权许可】

CC BY