Developed Algorithms for Maximum Pattern Generation in Logical Analysis of Data

Les données sont au coeur des industries et des organisations. Beaucoup d'entreprises possèdent de grandes quantités de données mais échouent à en tirer un bénéfice conséquent, bien souvent parce que ces données ne sont pas utilisées de façon productive. Il est indispensable de prendre des décisions importantes au bon moment, en utilisant des outils adaptés permettant d'extraire de l'information pratique et fiable de grandes quantités de données. Avec l'augmentation de la quantité et de la variété des données, le recours aux outils traditionnels facultatifs a été abandonné alors que l'importance de fournir des méthodes efficaces et prometteuses pour l'analyse de données se fait grandissante. La classification de données est l'un des moyens de répondre à ce besoin d'analyse de données. L'analyse Logique de Données (LAD : Logical Analysis of Data) est une nouvelle méthodologie d'analyse de données. Cette méthodologie qui combine l'optimisation, l'analyse combinatoire et la logique booléenne, est applicable pour le problème de classification des données. Son but est de trouver des motifs logiques cachés qui séparent les observations d'une certaine classe de toutes les autres observations. Ces motifs sont les blocs de base de l'Analyse Logique de Données dont l'objectif principal est de choisir un ensemble de motifs capable de classifier correctement des observations. La précision d'un modèle mesure à quel point cet objectif est atteint par le modèle. Dans ce projet de recherche, on s'intéresse à un type particulier de motifs appelé α-motif « α-pattern ». Ce type de motif permet de construire des modèles de classification LAD de très grande précision. En dépit du grand nombre de méthodologies existantes pour générer des α-motifs maximaux, il n'existe pas encore de méta-heuristique adressant ce problème. Le but de ce projet de recherche est donc de développer une méta-heuristique pour résoudre le problème des α-motifs maximaux. Cette méta-heuristique devra être efficace en termes de temps de résolution et aussi en termes de précision des motifs générés. Afin de satisfaire les deux exigences citées plus haut, notre choix s'est porté sur le recuit simulé. Nous avons utilisé le recuit simulé pour générer des α-motifs maximaux avec une approche différente de celle pratiquée dans le modèle BLA. La performance de l'algorithme développé est évaluée dans la suite. Les résultats du test statistique de Friedman montrent que notre algorithme possède les meilleures performances en termes de temps de résolution. De plus, pour ce qui est de la précision, celle fournie par notre algorithme est comparable à celles des autres méthodes. Notre précision possède par ailleurs de forts niveaux de confiance statistiques.

Abstract

Data is the heart of any industry or organization. Most of the companies are gifted with a large amount of data but they often fail to gain valuable insight from it, which is often because they cannot use their data productively. It is crucial to make essential and on-time decisions by using adapted tools to find applicable and accurate information from large amount of data. By increasing the amount and variety of data, the use of facultative traditional methods, were abolished and the importance of providing efficient and fruitful methods to analyze the data is growing. Data classification is one of the ways to fulfill this need of data analysis. Logical Analysis of Data is a methodology to analyze the data. This methodology, the combination of optimization, combinatorics and Boolean logic, is applicable for classification problems. Its aim is to discover hidden logical patterns that differentiate observations pertaining to one class from all of the other observations. Patterns are the key building blocks in LAD. Choosing a set of patterns that is capable of classifying observations correctly is the essential goal of LAD. Accuracy represents how successfully this goal is met. In this research study, one specific kind of pattern, called maximum α-pattern, is considered. This particular pattern helps building highly accurate LAD classification models. In spite of various presented methodologies to generate maximum α-pattern there is not yet any developed meta-heuristic algorithm. This research study is presented here with the objective of developing a meta-heuristic algorithm generating maximum α-patterns that are effective both in terms of computational time and accuracy. This study proposes a computationally efficient and accurate meta-heuristic algorithm based on the Simulated Annealing approach. The aim of the developed algorithm is to generate maximum α-patterns in a way that differs from the best linear approximation model proposed in the literature. Later, the performance of the new algorithm is evaluated. The results of the statistical Friedman test shows that the algorithm developed here has the best performance in terms of computational time. Moreover, its performance in terms of accuracy is competitive to other methods with, statistically speaking, high levels of confidence.