| Resumen |
In graph theory, a clique C of a given graph G is a fully connected subgraph. The problems of finding
a maximal clique, that is, a clique that is not included in a larger clique, and finding a minimum clique
partition are problems belonging to the NP-Hard complexity class. However, said problems have multiple
interesting applications in computer science and other disciplines, such as bioinformatics, communication
systems, and social networks. We propose a machine learning algorithm for classification that models a
given dataset into a special kind of rejectability graph and produces a set of classification rules expressed
using Boolean logic. The algorithm works by iteratively finding a clique from the rejectability graph and
extracting a Boolean function out of it, until it creates a complete clique partition of the initial graph.
To improve the explainability of the model, finding the fewest number of Boolean clauses is desired. As
a consequence, the algorithm aims to find the minimum clique partition by repeatedly finding a maximal
clique and removing it from the rejectability graph. Given that the time complexity for a brute force
approach to solving those problems grows exponentially, using classical algorithms is impractical. To
navigate the large search space for the maximal clique problem, our proposal uses a modification to the
traditional Artificial Ant Colony (ACO) and a Genetic Algorithm for finding good approximations using
reasonable resources within a practical time range. |
