JUCS - Journal of Universal Computer Science 28(6): 591-619, doi: 10.3897/jucs.67953
Extracting concepts from triadic contexts using Binary Decision Diagram
expand article infoJulio Cesar Vale Neves, Luiz Enrique Zarate, Mark Alan Junho Song
‡ Pontificia Universidade Catolica de Minas Gerais (PUC Minas), Belo Horizonte, Brazil
Open Access
Abstract

Due to the high complexity of real problems, a considerable amount of research that deals with high volumes of information has emerged. The literature has considered new applications of data analysis for high dimensional environments in order to manage the difficulty in extracting knowledge from a database, especially with the increase in social and professional networks. Tri- adic Concept Analysis (TCA) is a technique used in the applied mathematical area of data analysis. Its main purpose is to enable knowledge extraction from a context that contains objects, attributes, and conditions in a hierarchical and systematized representation. There are several algorithms that can extract concepts, but they are inefficient when applied to large datasets because the compu- tational costs are exponential. The objective of this paper is to add a new data structure, binary decision diagrams (BDD), in the TRIAS algorithm and retrieve triadic concepts for high dimen- sional contexts. BDD was used to characterize formal contexts, objects, attributes, and conditions. Moreover, to reduce the computational resources needed to manipulate a high-volume of data, the usage of BDD was implemented to simplify and represent data. The results show that this method has a considerably better speedup when compared to the original algorithm. Also, our approach discovered concepts that were previously unachievable when addressing high dimensional contexts.

Keywords
Formal Concept Analysis, Binary Decision Diagram, Triadic Concept Analysis