Louis Raimbault soutient sa thèse intitulée :
» Règles d’association: algorithmes de recherche et exploitation statistique «
dirigée par Mariane Pelletier et Abdelkader Mokkadem, le lundi 22 mai 2023 à 14h30, au bâtiment Fermat, amphi G.
Résumé :
Cette thèse est composée de deux parties.La première partie est consacrée aux algorithmes de recherche des règles d’association. La problématique centrale de cette partie est plus précisément la recherche des itemsets fréquents dans la mesure où il est simple et rapide d’obtenir les règles d’association une fois les itemsets fréquents trouvés. Dans cette partie, deux nouveaux algorithmes, PrefRec et SufRec, sont proposés. La construction de PrefRec, présentée dans le premier chapitre, est basée sur l’arbre préfixe, tandis que celle de SufRec, présentée dans le deuxième chapitre, est basée sur l’arbre suffixe. L’originalité de ces algorithmes est qu’ils sont récursifs par rapport aux items.
Plus précisément, soit B un ensemble d’items et soit F l’ensemble des itemsets fréquents associé. Une fois l’ensemble F obtenu, si un nouvel item est ajouté à l’ensemble B, alors les algorithmes existants doivent reprendre la totalité de la procédure pour extraire F’, le nouvel ensemble des itemsets fréquents. Ce n’est pas le cas des algorithmes PrefRec et SufRec qui utilisent exclusivement l’ensemble F et le nouvel item pour trouver quasi-instantanément le nouvel ensemble F’. Par ailleurs, deux versions de l’algorithme SufRec sont proposées, l’une des deux étant parallélisable. L’originalité de ce parallélisme est que, contrairement au parallélisme usuel, le nombre de tâches peut être strictement supérieur au nombre de processeurs. En effet, la version parallélisée de SufRec utilise q processeurs pour traiter n tâches : ces n tâches sont ordonnées et, dès qu’un processeur est libre, il prend en charge la première tâche non traitée. Ainsi, les processeurs traitent des nombres différents de tâches, la somme du nombre de tâches traitées par chacun d’entre eux étant égale à n. Les deux algorithmes PrefRec et SufRec ont été implémentés en C++ et une partie expérimentale compare l’efficacité de ces algorithmes avec celles des algorithmes Eclat, Fp-Growth et LCM.La deuxième partie de la thèse est consacrée à l’exploitation statistique des règles d’association. Cette partie aussi est constituée de deux chapitres. Dans le premier chapitre, une définition précise d’une règle d’association est donnée dans un cadre général. Ceci permet d’introduire de nouvelles règles, en définissant en particulier la notion de négation d’une règle, et celle de réunion et d’intersection d’antécédents ou de conséquents. En interprétant une règle d’association comme une règle de décision, de nouvelles mesures permettant d’évaluer l’intérêt d’une règle sont alors introduites. Le choix des mesures à privilégier dépend de la stratégie adoptée. Basée sur les propriétés des mesures introduites, une étude expérimentale conséquente est menée pour montrer comment construire des règles d’association optimales ayant un conséquent donné, et ce pour chacune des stratégies. Cette étude est réalisée à l’aide d’un package R ad hoc qui utilise l’algorithme PrefRec pour la recherche des itemsets fréquents.
Dans le deuxième chapitre, CAC (pour Characterization And Classification), une nouvelle procédure de classification supervisée, est introduite. Cette procédure utilise la notion de règles d’association pour trouver des caractérisations de la cible. Lorsque la base de données est exacte, ces caractérisations sont particulièrement intéressantes car elles permettent de résumer la base en peu de lignes. Que la base de données soit exacte ou non, ces caractérisations permettent aussi de réaliser une classification. La méthode de classification par CAC, présentée dans ce chapitre, se fait sur la base de deux caractérisations de la cible. Le chapitre termine avec une partie expérimentale montrant l’intérêt de la procédure de caractérisation et comparant l’efficacité de CAC et des méthodes Cart, SVM, Random Forest, Bagging et CBA.