Règles d’association et modèles de mélange

Il y a dans les données des structures cachées que ni la classification ni la régression ne peuvent révéler. Les découvrir, c’est lire entre les lignes du monde.

— Adaptation libre d’un aphorisme sur l’apprentissage non supervisé

Ce dernier chapitre de la partie consacrée à l’apprentissage non supervisé explore deux familles de méthodes qui cherchent à mettre au jour des structures latentes dans les données. La première — les règles d’association — extrait des motifs fréquents et des relations entre variables dans des données transactionnelles. La seconde — les modèles de mélange — suppose que les données sont générées par un mélange de plusieurs distributions, chacune correspondant à un groupe latent. Ces deux approches partagent un objectif commun : révéler une organisation sous-jacente que les méthodes de clustering classiques ne capturent pas directement, soit parce qu’il s’agit de co-occurrences entre items, soit parce qu’un modèle probabiliste génératif est plus approprié.

Show code cell source

Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from itertools import combinations

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)
np.random.seed(42)

Règles d’association : concepts fondamentaux

L’analyse par règles d’association est née du problème de l”analyse du panier d’achat (market basket analysis) : étant donné un historique de transactions dans un supermarché, quels produits sont fréquemment achetés ensemble ?

Transactions et itemsets

Définition 182 (Transaction et itemset)

Soit \(\mathcal{I} = \{i_1, i_2, \ldots, i_m\}\) un ensemble fini d”items. Une transaction \(T\) est un sous-ensemble de \(\mathcal{I}\), c’est-à-dire \(T \subseteq \mathcal{I}\). Une base de transactions \(\mathcal{D} = \{T_1, T_2, \ldots, T_n\}\) est un multi-ensemble de transactions. Un itemset \(X\) est un sous-ensemble non vide de \(\mathcal{I}\). Un itemset contenant \(k\) items est appelé un \(k\)-itemset.

Exemple 15 (Base de transactions)

Considérons \(\mathcal{I} = \{\text{pain}, \text{beurre}, \text{lait}, \text{oeufs}, \text{farine}\}\) :

TID	Transaction
1	{pain, beurre, lait}
2	{pain, beurre, oeufs, farine}
3	{lait, oeufs}
4	{pain, beurre, lait, farine}
5	{pain, lait}

L’itemset \(\{\text{pain}, \text{beurre}\}\) est un 2-itemset présent dans les transactions 1, 2 et 4.

Mesures d’intérêt

Définition 183 (Support)

Le support d’un itemset \(X\) dans \(\mathcal{D}\) est la proportion de transactions contenant \(X\) :

\[\text{supp}(X) = \frac{|\{T \in \mathcal{D} : X \subseteq T\}|}{|\mathcal{D}|}\]

Un itemset est dit fréquent si \(\text{supp}(X) \geq \sigma_{\min}\).

Définition 184 (Règle d’association, confiance, lift et conviction)

Une règle d’association est une implication \(X \Rightarrow Y\) avec \(X, Y \subseteq \mathcal{I}\) et \(X \cap Y = \emptyset\). Ses mesures d’intérêt sont :

• Confiance : \(\text{conf}(X \Rightarrow Y) = \frac{\text{supp}(X \cup Y)}{\text{supp}(X)} = P(Y \mid X)\)

• Lift : \(\text{lift}(X \Rightarrow Y) = \frac{\text{supp}(X \cup Y)}{\text{supp}(X) \cdot \text{supp}(Y)}\)

• Conviction : \(\text{conv}(X \Rightarrow Y) = \frac{1 - \text{supp}(Y)}{1 - \text{conf}(X \Rightarrow Y)}\)

Un lift de 1 signifie indépendance ; un lift \(> 1\) indique une association positive. La conviction est asymétrique : elle mesure le degré de dépendance directionnelle de la règle.

Remarque 160

Le support et le lift sont symétriques, tandis que la confiance et la conviction sont asymétriques. Le choix des métriques dépend de l’application : en recommandation, on privilégie la confiance ; en analyse exploratoire, le lift est un bon point de départ.

Show code cell source

Hide code cell source

# Implémentation manuelle des mesures d'intérêt
def support(itemset, transactions):
    """Calcule le support d'un itemset."""
    count = sum(1 for t in transactions if itemset.issubset(t))
    return count / len(transactions)

def confidence(antecedent, consequent, transactions):
    """Calcule la confiance de la règle antecedent => consequent."""
    supp_union = support(antecedent | consequent, transactions)
    supp_ante = support(antecedent, transactions)
    return supp_union / supp_ante if supp_ante > 0 else 0

def lift_score(antecedent, consequent, transactions):
    """Calcule le lift de la règle antecedent => consequent."""
    conf = confidence(antecedent, consequent, transactions)
    supp_cons = support(consequent, transactions)
    return conf / supp_cons if supp_cons > 0 else 0

# Base de transactions du supermarché
transactions = [
    {'pain', 'beurre', 'lait'},
    {'pain', 'beurre', 'oeufs', 'farine'},
    {'lait', 'oeufs'},
    {'pain', 'beurre', 'lait', 'farine'},
    {'pain', 'lait'},
]

ante, cons = {'pain'}, {'beurre'}
print(f"Règle : pain => beurre")
print(f"  Support(pain ∪ beurre) = {support(ante | cons, transactions):.2f}")
print(f"  Confiance              = {confidence(ante, cons, transactions):.2f}")
print(f"  Lift                   = {lift_score(ante, cons, transactions):.2f}")
print()
ante2, cons2 = {'beurre'}, {'pain'}
print(f"Règle : beurre => pain")
print(f"  Confiance              = {confidence(ante2, cons2, transactions):.2f}")
print(f"  Lift                   = {lift_score(ante2, cons2, transactions):.2f}")

Règle : pain => beurre
  Support(pain ∪ beurre) = 0.60
  Confiance              = 0.75
  Lift                   = 1.25

Règle : beurre => pain
  Confiance              = 1.00
  Lift                   = 1.25

Algorithme Apriori

L’extraction de règles d’association passe par deux étapes : (1) trouver tous les itemsets fréquents et (2) générer les règles. L’algorithme Apriori (Agrawal et Srikant, 1994) est l’approche fondatrice.

Propriété anti-monotone

Proposition 48 (Propriété anti-monotone du support)

Si un itemset \(X\) est fréquent, alors tout sous-ensemble \(Y \subseteq X\) est également fréquent. Réciproquement, si \(X\) n’est pas fréquent, aucun sur-ensemble \(Z \supseteq X\) ne peut l’être :

\[\text{supp}(X) \leq \text{supp}(Y) \quad \forall\, Y \subseteq X\]

Proof. Pour toute transaction \(T\), si \(X \subseteq T\) alors \(Y \subseteq T\) puisque \(Y \subseteq X\). Donc l’ensemble des transactions contenant \(X\) est inclus dans celui contenant \(Y\), d’où \(\text{supp}(X) \leq \text{supp}(Y)\).

Description de l’algorithme

L’algorithme procède niveau par niveau : (1) calculer les 1-itemsets fréquents \(L_1\) ; (2) générer les \((k{+}1)\)-candidats \(C_{k+1}\) par jointure de paires de \(L_k\) ; (3) élaguer les candidats dont un sous-ensemble n’est pas fréquent ; (4) compter le support et ne garder que les fréquents \(L_{k+1}\) ; (5) répéter jusqu’à \(L_{k+1} = \emptyset\).

Remarque 161

La complexité d’Apriori dépend du nombre de transactions, du nombre d’items et du seuil de support. L’algorithme nécessite autant de parcours de la base qu’il y a de niveaux. En pratique, un seuil de support bien choisi limite drastiquement l’espace de recherche grâce à l’élagage anti-monotone.

Show code cell source

Hide code cell source

def apriori(transactions, min_support):
    """Algorithme Apriori simplifié."""
    items = set()
    for t in transactions:
        items.update(t)

    # 1-itemsets fréquents
    freq_itemsets = {}
    for item in items:
        s = frozenset([item])
        sup = support(s, transactions)
        if sup >= min_support:
            freq_itemsets[s] = sup

    L_k = list(freq_itemsets.keys())
    k = 1
    all_frequent = dict(freq_itemsets)

    while L_k:
        k += 1
        candidates = set()
        for i in range(len(L_k)):
            for j in range(i + 1, len(L_k)):
                union = L_k[i] | L_k[j]
                if len(union) == k:
                    all_sub_freq = all(
                        frozenset(c) in all_frequent
                        for c in combinations(union, k - 1)
                    )
                    if all_sub_freq:
                        candidates.add(union)
        L_k = []
        for c in candidates:
            sup = support(c, transactions)
            if sup >= min_support:
                all_frequent[c] = sup
                L_k.append(c)

    return all_frequent

freq = apriori(transactions, min_support=0.4)
print("Itemsets fréquents (support ≥ 0.4) :")
for itemset, sup in sorted(freq.items(), key=lambda x: (-len(x[0]), -x[1])):
    print(f"  {str(set(itemset)):30s} support = {sup:.2f}")

Itemsets fréquents (support ≥ 0.4) :
  {'beurre', 'pain', 'farine'}   support = 0.40
  {'pain', 'beurre', 'lait'}     support = 0.40
  {'pain', 'lait'}               support = 0.60
  {'beurre', 'pain'}             support = 0.60
  {'beurre', 'farine'}           support = 0.40
  {'beurre', 'lait'}             support = 0.40
  {'pain', 'farine'}             support = 0.40
  {'lait'}                       support = 0.80
  {'pain'}                       support = 0.80
  {'beurre'}                     support = 0.60
  {'oeufs'}                      support = 0.40
  {'farine'}                     support = 0.40

Show code cell source

Hide code cell source

def generate_rules(frequent_itemsets, transactions, min_confidence=0.6):
    """Génère les règles d'association à partir des itemsets fréquents."""
    rules = []
    for itemset, sup in frequent_itemsets.items():
        if len(itemset) < 2:
            continue
        for i in range(1, len(list(itemset))):
            for ante_tuple in combinations(itemset, i):
                ante = frozenset(ante_tuple)
                cons = itemset - ante
                conf = sup / frequent_itemsets.get(ante, 1e-10)
                if conf >= min_confidence:
                    l = sup / (frequent_itemsets.get(ante, 1e-10)
                               * frequent_itemsets.get(cons, 1e-10))
                    rules.append({'antecedent': set(ante), 'consequent': set(cons),
                                  'support': sup, 'confidence': conf, 'lift': l})
    return rules

rules = generate_rules(freq, transactions, min_confidence=0.6)
print(f"{len(rules)} règles trouvées (confiance ≥ 0.6) :\n")
for r in sorted(rules, key=lambda x: -x['lift']):
    print(f"  {r['antecedent']} => {r['consequent']}")
    print(f"    support={r['support']:.2f}  confiance={r['confidence']:.2f}"
          f"  lift={r['lift']:.2f}")

17 règles trouvées (confiance ≥ 0.6) :

  {'beurre'} => {'farine'}
    support=0.40  confiance=0.67  lift=1.67
  {'farine'} => {'beurre'}
    support=0.40  confiance=1.00  lift=1.67
  {'beurre'} => {'pain', 'farine'}
    support=0.40  confiance=0.67  lift=1.67
  {'farine'} => {'beurre', 'pain'}
    support=0.40  confiance=1.00  lift=1.67
  {'beurre', 'pain'} => {'farine'}
    support=0.40  confiance=0.67  lift=1.67
  {'pain', 'farine'} => {'beurre'}
    support=0.40  confiance=1.00  lift=1.67
  {'beurre'} => {'pain'}
    support=0.60  confiance=1.00  lift=1.25
  {'pain'} => {'beurre'}
    support=0.60  confiance=0.75  lift=1.25
  {'farine'} => {'pain'}
    support=0.40  confiance=1.00  lift=1.25
  {'beurre', 'farine'} => {'pain'}
    support=0.40  confiance=1.00  lift=1.25
  {'beurre', 'lait'} => {'pain'}
    support=0.40  confiance=1.00  lift=1.25
  {'beurre'} => {'pain', 'lait'}
    support=0.40  confiance=0.67  lift=1.11
  {'pain', 'lait'} => {'beurre'}
    support=0.40  confiance=0.67  lift=1.11
  {'pain'} => {'lait'}
    support=0.60  confiance=0.75  lift=0.94
  {'lait'} => {'pain'}
    support=0.60  confiance=0.75  lift=0.94
  {'beurre'} => {'lait'}
    support=0.40  confiance=0.67  lift=0.83
  {'pain', 'beurre'} => {'lait'}
    support=0.40  confiance=0.67  lift=0.83

Apriori avec mlxtend

La bibliothèque mlxtend fournit une implémentation optimisée. Elle est optionnelle : si elle n’est pas installée, les cellules suivantes seront ignorées, mais les concepts restent identiques à notre implémentation manuelle.

Show code cell source

Hide code cell source

try:
    from mlxtend.preprocessing import TransactionEncoder
    from mlxtend.frequent_patterns import apriori as mlx_apriori
    from mlxtend.frequent_patterns import association_rules as mlx_rules
    import pandas as pd
    MLXTEND_AVAILABLE = True
except ImportError:
    MLXTEND_AVAILABLE = False
    print("mlxtend non disponible — les cellules suivantes seront ignorées.")

if MLXTEND_AVAILABLE:
    dataset = [list(t) for t in transactions]
    te = TransactionEncoder()
    te_array = te.fit_transform(dataset)
    df = pd.DataFrame(te_array, columns=te.columns_)
    freq_items = mlx_apriori(df, min_support=0.4, use_colnames=True)
    regles = mlx_rules(freq_items, metric="confidence", min_threshold=0.6)
    cols = [c for c in ['antecedents', 'consequents', 'support', 'confidence',
                         'lift'] if c in regles.columns]
    print("Règles d'association (mlxtend) :")
    print(regles[cols].to_string())

mlxtend non disponible — les cellules suivantes seront ignorées.

Algorithme FP-Growth

L’algorithme FP-Growth (Han, Pei et Yin, 2000) résout les deux faiblesses principales d’Apriori : les multiples parcours de la base et la génération coûteuse de candidats.

Définition 185 (FP-tree)

Un FP-tree (Frequent Pattern tree) est un arbre préfixe compact encodant les transactions. Chaque noeud représente un item avec un compteur. Les items sont ordonnés par fréquence décroissante pour maximiser le partage de préfixes. La construction nécessite deux parcours : (1) calculer les fréquences et trier ; (2) insérer les transactions filtrées dans l’arbre.

Proposition 49 (Avantages de FP-Growth sur Apriori)

1. Pas de génération de candidats : l’extraction se fait directement par projection récursive (conditional pattern base).

2. Deux parcours de la base seulement, contre autant que la taille maximale des itemsets fréquents pour Apriori.

En pratique, FP-Growth est significativement plus rapide sur les bases volumineuses et les seuils de support bas.

Show code cell source

Hide code cell source

if MLXTEND_AVAILABLE:
    from mlxtend.frequent_patterns import fpgrowth
    freq_fp = fpgrowth(df, min_support=0.4, use_colnames=True)
    print("Itemsets fréquents (FP-Growth) :")
    print(freq_fp.to_string())
    print(f"\nNombre d'itemsets — Apriori : {len(freq_items)}, "
          f"FP-Growth : {len(freq_fp)}")

Applications des règles d’association

Exemple 16 (Analyse du panier d’achat)

L’application historique des règles d’association est le market basket analysis. Des règles comme \(\{\text{couches}\} \Rightarrow \{\text{bière}\}\) (confiance 0.68, lift 2.1) révèlent des associations surprenantes mais exploitables. Le lift distingue les co-occurrences fortuites (produits très fréquents) des associations véritablement intéressantes.

Les règles d’association s’appliquent aussi en bioinformatique (gènes co-exprimés), en médecine (combinaisons de symptômes), en web mining (séquences de navigation) et en détection de fraude (schémas de transactions suspects).

Remarque 162

L’extraction produit souvent un très grand nombre de règles. Pour filtrer : (1) exiger simultanément support, confiance et lift minimum ; (2) éliminer les règles redondantes (si \(X' \subset X\) donne une confiance similaire, préférer la règle plus simple) ; (3) valider avec l’expertise métier ; (4) utiliser des visualisations (graphes, heatmaps) pour l’exploration interactive.

---

La seconde partie de ce chapitre aborde les modèles de mélange, une famille de modèles génératifs probabilistes complémentaire aux règles d’association.

Modèles de mélange gaussien

Les modèles de mélange gaussien (Gaussian Mixture Models, GMM) constituent l’approche probabiliste fondamentale du clustering. Contrairement aux k-moyennes, les GMM modélisent l’appartenance à un cluster comme une variable latente et fournissent des probabilités d’appartenance.

Modèle génératif

Définition 186 (Modèle de mélange gaussien)

Un GMM à \(K\) composantes suppose que chaque \(\mathbf{x}_i \in \mathbb{R}^d\) est généré par :

1. Tirer \(z_i \sim \text{Catégorielle}(\pi_1, \ldots, \pi_K)\) avec \(\sum_k \pi_k = 1\), \(\pi_k \geq 0\).

2. Tirer \(\mathbf{x}_i \mid z_i = k \sim \mathcal{N}(\boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)\).

La densité marginale est \(p(\mathbf{x} \mid \boldsymbol{\theta}) = \sum_{k=1}^K \pi_k \, \mathcal{N}(\mathbf{x} \mid \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)\).

Définition 187 (Log-vraisemblance du mélange)

Pour un échantillon i.i.d. \(\{\mathbf{x}_1, \ldots, \mathbf{x}_n\}\) :

\[\ell(\boldsymbol{\theta}) = \sum_{i=1}^n \log \left(\sum_{k=1}^K \pi_k \, \mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)\right)\]

La somme à l’intérieur du logarithme empêche une optimisation en forme close, d’où le recours à l’algorithme EM.

Algorithme Espérance-Maximisation (EM)

Définition 188 (Algorithme EM pour les GMM)

Étape E : calculer les responsabilités \(\gamma_{ik} = P(z_i = k \mid \mathbf{x}_i, \boldsymbol{\theta}^{(t)})\) :

\[\gamma_{ik} = \frac{\pi_k^{(t)} \, \mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_k^{(t)}, \boldsymbol{\Sigma}_k^{(t)})}{\sum_{j=1}^K \pi_j^{(t)} \, \mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_j^{(t)}, \boldsymbol{\Sigma}_j^{(t)})}\]

Étape M : avec \(N_k = \sum_i \gamma_{ik}\), mettre à jour :

\[\boldsymbol{\mu}_k^{(t+1)} = \frac{1}{N_k} \sum_{i=1}^n \gamma_{ik} \, \mathbf{x}_i, \quad \boldsymbol{\Sigma}_k^{(t+1)} = \frac{1}{N_k} \sum_{i=1}^n \gamma_{ik} (\mathbf{x}_i - \boldsymbol{\mu}_k^{(t+1)})(\mathbf{x}_i - \boldsymbol{\mu}_k^{(t+1)})^\top, \quad \pi_k^{(t+1)} = \frac{N_k}{n}\]

Proposition 50 (Convergence de l’algorithme EM)

La log-vraisemblance est non décroissante à chaque itération : \(\ell(\boldsymbol{\theta}^{(t+1)}) \geq \ell(\boldsymbol{\theta}^{(t)})\). Cependant, EM ne garantit la convergence que vers un maximum local. En pratique, on lance EM plusieurs fois avec des initialisations différentes (n_init dans Scikit-learn) et on conserve la meilleure solution.

Show code cell source

Hide code cell source

from sklearn.mixture import GaussianMixture
from sklearn.datasets import make_blobs
from matplotlib.patches import Ellipse

X_gmm, y_true = make_blobs(n_samples=400, centers=[[-3, -3], [0, 3], [4, -1]],
                            cluster_std=[0.8, 1.2, 0.9], random_state=42)

gmm = GaussianMixture(n_components=3, covariance_type='full',
                       n_init=5, random_state=42)
gmm.fit(X_gmm)
labels_gmm = gmm.predict(X_gmm)
proba_gmm = gmm.predict_proba(X_gmm)

fig, axes = plt.subplots(2, 1, figsize=(9, 9))

ax = axes[0]
for k in range(3):
    mask = labels_gmm == k
    ax.scatter(X_gmm[mask, 0], X_gmm[mask, 1], s=20, alpha=0.6,
               label=f'Composante {k+1}')
ax.set_title("Clustering par GMM (assignation dure)")
ax.legend()
ax.set_xlabel("$x_1$"); ax.set_ylabel("$x_2$")

ax = axes[1]
entropy = -np.sum(proba_gmm * np.log(proba_gmm + 1e-10), axis=1)
sc = ax.scatter(X_gmm[:, 0], X_gmm[:, 1], c=entropy, cmap='YlOrRd', s=20, alpha=0.7)
plt.colorbar(sc, ax=ax, label="Entropie")
ax.set_title("Incertitude de l'assignation (entropie)")
ax.set_xlabel("$x_1$"); ax.set_ylabel("$x_2$")
plt.tight_layout()
plt.show()

Show code cell source

Hide code cell source

# Ellipsoïdes de confiance à 2σ
def draw_ellipses(gmm_model, ax, colors):
    for k in range(gmm_model.n_components):
        mean = gmm_model.means_[k]
        cov = gmm_model.covariances_[k]
        vals, vecs = np.linalg.eigh(cov)
        angle = np.degrees(np.arctan2(vecs[1, 0], vecs[0, 0]))
        width, height = 4 * np.sqrt(vals)
        ell = Ellipse(xy=mean, width=width, height=height, angle=angle,
                      edgecolor=colors[k], facecolor=colors[k], alpha=0.15, linewidth=2)
        ax.add_patch(ell)
        ax.scatter(*mean, marker='+', s=200, c=[colors[k]], linewidths=3, zorder=5)

fig, ax = plt.subplots(figsize=(8, 6))
colors = ['#4C72B0', '#DD8452', '#55A868']
for k in range(3):
    mask = labels_gmm == k
    ax.scatter(X_gmm[mask, 0], X_gmm[mask, 1], s=15, alpha=0.5,
               color=colors[k], label=f'Composante {k+1}')
draw_ellipses(gmm, ax, colors)
ax.set_title("GMM : composantes et ellipsoïdes de confiance (2σ)")
ax.legend(); ax.set_xlabel("$x_1$"); ax.set_ylabel("$x_2$")
plt.tight_layout()
plt.show()

Choix du nombre de composantes

Définition 189 (Critères BIC et AIC)

Le choix de \(K\) repose sur des critères d’information pénalisant la complexité :

\[\text{BIC} = -2\,\ell(\hat{\boldsymbol{\theta}}) + p \ln(n), \qquad \text{AIC} = -2\,\ell(\hat{\boldsymbol{\theta}}) + 2p\]

où \(p\) est le nombre de paramètres libres et \(n\) le nombre d’observations. Le modèle optimal minimise le critère. Le BIC pénalise davantage la complexité et tend vers des modèles plus parcimonieux.

Show code cell source

Hide code cell source

K_range = range(1, 8)
bics, aics = [], []
for K in K_range:
    model = GaussianMixture(n_components=K, covariance_type='full',
                             n_init=5, random_state=42)
    model.fit(X_gmm)
    bics.append(model.bic(X_gmm))
    aics.append(model.aic(X_gmm))

fig, ax = plt.subplots(figsize=(8, 5))
ax.plot(list(K_range), bics, 'o-', label='BIC', color='steelblue')
ax.plot(list(K_range), aics, 's--', label='AIC', color='coral')
ax.axvline(x=list(K_range)[np.argmin(bics)], color='steelblue', linestyle=':', alpha=0.7)
ax.set_xlabel("Nombre de composantes $K$")
ax.set_ylabel("Critère d'information")
ax.set_title("Sélection du nombre de composantes (GMM)")
ax.legend()
plt.tight_layout()
plt.show()
print(f"K optimal selon BIC : {list(K_range)[np.argmin(bics)]}")

K optimal selon BIC : 3

Mélange de Bernoulli

Les GMM supposent des données continues. Pour des données binaires (présence/absence de mots, réponses oui/non, pixels noirs/blancs), on utilise le mélange de Bernoulli.

Définition 190 (Modèle de mélange de Bernoulli)

Soit \(\mathbf{x}_i \in \{0, 1\}^d\). Un mélange de Bernoulli à \(K\) composantes :

1. Tire \(z_i \sim \text{Catégorielle}(\pi_1, \ldots, \pi_K)\).

2. Tire \(x_{ij} \mid z_i = k \sim \text{Bernoulli}(\mu_{kj})\) pour \(j = 1, \ldots, d\).

La vraisemblance marginale est

\[p(\mathbf{x}_i \mid \boldsymbol{\theta}) = \sum_{k=1}^K \pi_k \prod_{j=1}^d \mu_{kj}^{x_{ij}} (1 - \mu_{kj})^{1 - x_{ij}}\]

Définition 191 (EM pour le mélange de Bernoulli)

Étape E : \(\gamma_{ik} = \frac{\pi_k \prod_j \mu_{kj}^{x_{ij}} (1 - \mu_{kj})^{1 - x_{ij}}}{\sum_\ell \pi_\ell \prod_j \mu_{\ell j}^{x_{ij}} (1 - \mu_{\ell j})^{1 - x_{ij}}}\)

Étape M : \(\mu_{kj}^{(t+1)} = \frac{\sum_i \gamma_{ik} x_{ij}}{\sum_i \gamma_{ik}}, \quad \pi_k^{(t+1)} = \frac{1}{n}\sum_i \gamma_{ik}\)

Un lissage \(\epsilon \approx 10^{-6}\) sur \(\mu_{kj}\) évite les valeurs 0 ou 1 qui rendraient la log-vraisemblance non définie.

Show code cell source

Hide code cell source

class BernoulliMixture:
    """Mélange de Bernoulli estimé par EM."""
    def __init__(self, n_components=3, max_iter=100, tol=1e-6, eps=1e-6):
        self.K = n_components
        self.max_iter = max_iter
        self.tol = tol
        self.eps = eps

    def fit(self, X):
        n, d = X.shape
        self.pi = np.ones(self.K) / self.K
        self.mu = np.random.rand(self.K, d) * 0.5 + 0.25
        self.log_likelihoods = []
        for it in range(self.max_iter):
            gamma = self._e_step(X)
            ll = self._log_likelihood(X)
            self.log_likelihoods.append(ll)
            if it > 0 and abs(ll - self.log_likelihoods[-2]) < self.tol:
                break
            self._m_step(X, gamma)
        return self

    def _e_step(self, X):
        log_resp = np.zeros((X.shape[0], self.K))
        for k in range(self.K):
            log_bern = (X * np.log(self.mu[k] + self.eps)
                        + (1 - X) * np.log(1 - self.mu[k] + self.eps))
            log_resp[:, k] = np.log(self.pi[k] + self.eps) + log_bern.sum(axis=1)
        log_resp -= log_resp.max(axis=1, keepdims=True)
        resp = np.exp(log_resp)
        resp /= resp.sum(axis=1, keepdims=True)
        return resp

    def _m_step(self, X, gamma):
        Nk = gamma.sum(axis=0)
        self.pi = Nk / X.shape[0]
        self.mu = np.clip((gamma.T @ X) / Nk[:, None], self.eps, 1 - self.eps)

    def _log_likelihood(self, X):
        ll = np.zeros(X.shape[0])
        for k in range(self.K):
            log_bern = (X * np.log(self.mu[k] + self.eps)
                        + (1 - X) * np.log(1 - self.mu[k] + self.eps))
            ll += self.pi[k] * np.exp(log_bern.sum(axis=1))
        return np.log(ll + self.eps).sum()

    def predict(self, X):
        return self._e_step(X).argmax(axis=1)

# Données binaires synthétiques : 3 profils distincts
d = 20
true_mu = np.array([[0.9]*5 + [0.1]*5 + [0.5]*10,
                     [0.1]*5 + [0.9]*5 + [0.5]*10,
                     [0.5]*5 + [0.5]*5 + [0.9]*5 + [0.1]*5])
X_bin = np.vstack([np.random.binomial(1, true_mu[k], (100, d)) for k in range(3)])
np.random.shuffle(X_bin)

bm = BernoulliMixture(n_components=3, max_iter=200)
bm.fit(X_bin)

fig, axes = plt.subplots(2, 1, figsize=(9, 7))
axes[0].plot(bm.log_likelihoods, 'o-', markersize=3, color='steelblue')
axes[0].set_xlabel("Itération"); axes[0].set_ylabel("Log-vraisemblance")
axes[0].set_title("Convergence de l'EM (mélange de Bernoulli)")

im = axes[1].imshow(bm.mu, aspect='auto', cmap='YlOrRd', vmin=0, vmax=1)
axes[1].set_xlabel("Dimension"); axes[1].set_ylabel("Composante $k$")
axes[1].set_yticks(range(3)); axes[1].set_yticklabels([f"$k={k+1}$" for k in range(3)])
axes[1].set_title("Paramètres $\\mu_k$ estimés")
plt.colorbar(im, ax=axes[1], label="$\\mu_{kj}$")
plt.tight_layout()
plt.show()

Remarque 163

Le mélange de Bernoulli est adapté au clustering de documents représentés par des vecteurs binaires (présence/absence de mots). Chaque composante correspond à un profil thématique.

Allocation de Dirichlet latente (LDA)

L’allocation de Dirichlet latente (Blei, Ng et Jordan, 2003) est le modèle génératif de référence pour le topic modeling. Contrairement au mélange de Bernoulli où chaque document appartient à un seul cluster, le LDA suppose qu’un document traite de plusieurs sujets simultanément.

Modèle génératif du LDA

Définition 192 (Distribution de Dirichlet)

La distribution de Dirichlet \(\text{Dir}(\boldsymbol{\alpha})\) est définie sur le simplexe de dimension \(K-1\) :

\[p(\boldsymbol{\theta} \mid \boldsymbol{\alpha}) = \frac{\Gamma\!\left(\sum_k \alpha_k\right)}{\prod_k \Gamma(\alpha_k)} \prod_{k=1}^K \theta_k^{\alpha_k - 1}\]

Des valeurs \(\alpha_k < 1\) favorisent des distributions creuses ; \(\alpha_k > 1\) favorise l’uniformité.

Définition 193 (Modèle LDA)

Pour un corpus de \(M\) documents, un vocabulaire de \(V\) mots et \(K\) topics :

1. Pour chaque topic \(k\), tirer \(\boldsymbol{\beta}_k \sim \text{Dir}(\boldsymbol{\eta})\) (distribution sur les mots).

2. Pour chaque document \(m\) :

   • Tirer \(\boldsymbol{\theta}_m \sim \text{Dir}(\boldsymbol{\alpha})\) (proportions de topics).

   • Pour chaque mot \(n\) : tirer le topic \(z_{mn} \sim \text{Cat}(\boldsymbol{\theta}_m)\) puis le mot \(w_{mn} \sim \text{Cat}(\boldsymbol{\beta}_{z_{mn}})\).

Chaque document est un mélange de sujets, et chaque sujet est une distribution sur les mots.

Inférence

Proposition 51 (Inférence dans le LDA)

L’inférence exacte est intraitable. Deux approches sont courantes :

1. Inférence variationnelle : approximation par minimisation de la divergence KL (Scikit-learn).

2. Échantillonnage de Gibbs : simulation de la postérieure par échantillonnage conditionnel itératif (gensim).

Show code cell source

Hide code cell source

from sklearn.decomposition import LatentDirichletAllocation
from sklearn.feature_extraction.text import CountVectorizer

# Corpus jouet en français
corpus = [
    "le chat dort sur le canapé le chat aime dormir",
    "le chat joue avec la balle le chat court vite",
    "le chien court dans le jardin le chien joue dehors",
    "le chien dort dans sa niche le chien aime dormir",
    "la voiture roule vite sur la route la voiture freine",
    "le vélo roule sur la piste le vélo freine au feu",
    "la voiture consomme de essence la voiture pollue",
    "le chat mange des croquettes le chat boit du lait",
    "le chien mange des croquettes le chien boit de eau",
    "le vélo ne pollue pas le vélo est écologique",
]

vectorizer = CountVectorizer(min_df=1)
X_bow = vectorizer.fit_transform(corpus)
vocab = vectorizer.get_feature_names_out()
print(f"Vocabulaire : {len(vocab)} termes | Matrice : {X_bow.shape}")

Vocabulaire : 42 termes | Matrice : (10, 42)

Show code cell source

Hide code cell source

lda = LatentDirichletAllocation(n_components=3, max_iter=50,
                                 learning_method='batch', random_state=42)
doc_topics = lda.fit_transform(X_bow)

print("Topics découverts :\n")
for k, topic in enumerate(lda.components_):
    top_words = [vocab[i] for i in topic.argsort()[::-1][:6]]
    print(f"  Topic {k+1} : {', '.join(top_words)}")

# Visualisation
fig, ax = plt.subplots(figsize=(10, 5))
x_pos = np.arange(len(corpus))
bottom = np.zeros(len(corpus))
colors = ['#4C72B0', '#DD8452', '#55A868']
for k in range(3):
    ax.bar(x_pos, doc_topics[:, k], bottom=bottom, color=colors[k],
           label=f'Topic {k+1}', alpha=0.85)
    bottom += doc_topics[:, k]
ax.set_xlabel("Document"); ax.set_ylabel("Proportion")
ax.set_title("Distribution des topics par document (LDA)")
ax.set_xticks(x_pos)
ax.set_xticklabels([f"D{i+1}" for i in range(len(corpus))], fontsize=9)
ax.legend(loc='upper right')
plt.tight_layout()
plt.show()

Topics découverts :

  Topic 1 : voiture, la, vélo, pollue, le, de
  Topic 2 : le, chat, chien, la, sur, aime
  Topic 3 : de, voiture, la, le, vélo, route

Exemple complet : topic modeling sur 20 Newsgroups

Pour illustrer le LDA à plus grande échelle, nous utilisons le jeu de données 20 Newsgroups, un corpus classique d’environ 18 000 articles de forums Usenet. Nous sélectionnons cinq catégories.

Show code cell source

Hide code cell source

from sklearn.datasets import fetch_20newsgroups

categories = ['sci.space', 'rec.sport.baseball', 'talk.politics.guns',
              'comp.graphics', 'rec.autos']
newsgroups = fetch_20newsgroups(subset='train', categories=categories,
                                 remove=('headers', 'footers', 'quotes'),
                                 random_state=42)
print(f"Nombre de documents : {len(newsgroups.data)}")
print(f"Catégories : {newsgroups.target_names}")

vectorizer_ng = CountVectorizer(max_df=0.9, min_df=5, max_features=2000,
                                 stop_words='english')
X_ng = vectorizer_ng.fit_transform(newsgroups.data)
vocab_ng = vectorizer_ng.get_feature_names_out()
print(f"Matrice documents-termes : {X_ng.shape}")

Nombre de documents : 2914
Catégories : ['comp.graphics', 'rec.autos', 'rec.sport.baseball', 'sci.space', 'talk.politics.guns']

Matrice documents-termes : (2914, 2000)

Show code cell source

Hide code cell source

lda_ng = LatentDirichletAllocation(n_components=5, max_iter=30,
                                    learning_method='online',
                                    learning_offset=50., random_state=42)
doc_topics_ng = lda_ng.fit_transform(X_ng)

print("=" * 60)
print("TOPICS DÉCOUVERTS PAR LDA SUR 20 NEWSGROUPS")
print("=" * 60)
for k, topic in enumerate(lda_ng.components_):
    top_words = [vocab_ng[i] for i in topic.argsort()[::-1][:10]]
    print(f"\nTopic {k+1:2d} : {', '.join(top_words)}")

============================================================
TOPICS DÉCOUVERTS PAR LDA SUR 20 NEWSGROUPS
============================================================

Topic  1 : gun, people, guns, right, law, government, weapons, don, state, control

Topic  2 : space, image, data, edu, graphics, nasa, jpeg, program, available, use

Topic  3 : car, 00, new, cars, like, 000, just, good, engine, 02

Topic  4 : just, don, think, like, year, good, know, time, better, did

Topic  5 : file, 1993, 10, 12, 15, april, 11, 1992, 14, year

Show code cell source

Hide code cell source

fig, axes = plt.subplots(2, 1, figsize=(9, 9))

# Distribution des topics dominants
dominant_topic = doc_topics_ng.argmax(axis=1)
ax = axes[0]
ax.hist(dominant_topic, bins=np.arange(6) - 0.5, edgecolor='white',
        color='steelblue', alpha=0.8, rwidth=0.8)
ax.set_xticks(range(5))
ax.set_xticklabels([f"Topic {k+1}" for k in range(5)])
ax.set_xlabel("Topic dominant"); ax.set_ylabel("Nombre de documents")
ax.set_title("Distribution des topics dominants")

# Matrice catégorie × topic
ax = axes[1]
cat_topic = np.zeros((len(categories), 5))
for idx in range(len(categories)):
    cat_topic[idx] = doc_topics_ng[newsgroups.target == idx].mean(axis=0)
im = ax.imshow(cat_topic, aspect='auto', cmap='Blues')
ax.set_yticks(range(len(categories)))
ax.set_yticklabels([c.split('.')[-1] for c in categories], fontsize=9)
ax.set_xticks(range(5))
ax.set_xticklabels([f"T{k+1}" for k in range(5)])
ax.set_xlabel("Topic"); ax.set_ylabel("Catégorie réelle")
ax.set_title("Proportion moyenne de chaque topic par catégorie")
plt.colorbar(im, ax=ax, label="Proportion moyenne")
plt.tight_layout()
plt.show()

Remarque 164

Les topics découverts par le LDA correspondent souvent — au moins partiellement — aux catégories thématiques du corpus, même sans supervision. L’interprétation reste subjective : il est utile de lire quelques documents fortement associés à chaque topic pour valider les étiquettes assignées.

Choix du nombre de topics

Remarque 165

Le choix de \(K\) est analogue au choix du nombre de clusters. On peut utiliser : (1) la perplexité sur un ensemble de validation, \(\text{perplexity} = \exp(-\ell(\mathcal{D}_{\text{test}})/N_{\text{test}})\) ; (2) la cohérence des topics (topic coherence), mesurant la cohérence sémantique des mots-clés ; (3) l”interprétabilité humaine, en essayant plusieurs valeurs de \(K\).

Show code cell source

Hide code cell source

from sklearn.model_selection import train_test_split as tts

X_train_ng, X_test_ng = tts(X_ng, test_size=0.2, random_state=42)
K_values = [3, 5, 10]
perplexities = []
for K in K_values:
    lda_k = LatentDirichletAllocation(n_components=K, max_iter=5,
                                       learning_method='online', random_state=42)
    lda_k.fit(X_train_ng)
    perp = lda_k.perplexity(X_test_ng)
    perplexities.append(perp)
    print(f"K = {K:2d}  |  Perplexité = {perp:.1f}")

fig, ax = plt.subplots(figsize=(7, 4))
ax.plot(K_values, perplexities, 'o-', color='steelblue', markersize=8)
ax.set_xlabel("Nombre de topics $K$"); ax.set_ylabel("Perplexité (test)")
ax.set_title("Sélection du nombre de topics")
plt.tight_layout()
plt.show()

K =  3  |  Perplexité = 1709.2

K =  5  |  Perplexité = 1799.4

K = 10  |  Perplexité = 2120.3

Résumé

Ce chapitre a présenté deux familles complémentaires de méthodes pour découvrir des structures cachées :

1. Les règles d’association extraient des motifs de co-occurrence dans des données transactionnelles. Le support, la confiance et le lift identifient les associations intéressantes. Apriori et FP-Growth rendent l’extraction efficace à grande échelle.

2. Les modèles de mélange adoptent une perspective probabiliste. Le GMM fournit des assignations souples via l’algorithme EM. Le mélange de Bernoulli adapte cette approche aux données binaires. Le LDA généralise au topic modeling en permettant à chaque document d’être un mélange de sujets.

Remarque 166

Le choix entre ces méthodes dépend de la nature des données : données transactionnelles pour les règles d’association, données continues pour les GMM, données binaires pour le mélange de Bernoulli, et corpus de texte pour le LDA. En pratique, combiner plusieurs approches est souvent fructueux : par exemple, un GMM pour un premier clustering, puis des règles d’association au sein de chaque cluster pour affiner l’analyse.