Chapitre 3 : Algorithmes et complexité

Les algorithmes de data mining doivent passer à l’échelle. Ce chapitre rappelle les notions d’efficacité et de complexité, et les parcours DFS/BFS — outils indispensables pour explorer l’espace des motifs (chap6).

Objectifs

À la fin de ce chapitre, vous devez pouvoir :

  • Définir un algorithme et raisonner sur son efficacité

  • Estimer une complexité (temps, mémoire) et comprendre la croissance exponentielle

  • Implémenter et distinguer les parcours DFS et BFS

1. Algorithme et efficacité

Un algorithme est une suite finie d’instructions résolvant un problème. En data mining, l’efficacité est cruciale : les espaces de recherche sont énormes (p. ex. pour \(n\) produits, il y a \(2^n\) combinaisons possibles d’items).

On évalue un algorithme par sa complexité :

  • temporelle (temps d’exécution selon la taille de l’entrée) ;

  • spatiale (mémoire utilisée).

On l’exprime en notation Grand O (voir aussi le cours AQL). Une croissance exponentielle (\(O(2^n)\)) rend l’approche naïve impraticable : d’où le besoin d’heuristiques et de propriétés (comme l’antimonotonicité, au chap6) pour élaguer l’espace de recherche.

2. Recherche / exploration : DFS et BFS

Explorer l’espace des candidats revient à parcourir un arbre (ou un treillis, lattice) de possibilités. Deux parcours fondamentaux :

  • DFS (Depth-First Search, parcours en profondeur) : on descend une branche jusqu’au bout avant de revenir en arrière (backtracking). Peu de mémoire.

  • BFS (Breadth-First Search, parcours en largeur) : on explore niveau par niveau. Pratique pour exploiter les propriétés « par niveau » (a priori).

DFS (récursif) — exploration de toutes les combinaisons d’un alphabet :

def dfs(P, alphabet):
    print(P)                      # P est un candidat (un sous-ensemble)
    for e in alphabet:
        dfs(P + [e], alphabet)

dfs([], alphabet)

Cette exploration naïve génère toutes les combinaisons. Pour la rendre efficace, on ajoute un ordre virtuel sur les éléments (ne brancher que sur les éléments suivants) puis on élague avec une propriété (a priori) — c’est exactement la démarche du Frequent Itemset Mining.

Exercice

  1. Pour un alphabet de 4 éléments, combien de sous-ensembles l’exploration naïve génère-t-elle ?

  2. Modifiez la fonction dfs pour ne brancher que sur les éléments après le dernier ajouté. Combien de candidats génère-t-elle alors ?