Principe fondamental de l'algorithme

Contrairement au K-means classique, où toutes les caractéristiques contribuent uniformément au calcul de distance, l'algorithme K-means à pondération dynamique adaptative affecte des poids spécifiques à chaque caractéristique pour chaque cluster. Ces poids sont ajustés itérativement afin d'optimiser la qualité du partitinonement.

Fondements théoriques

Fonction objectif

La fonction objectif J(W,Z,Λ) à minimiser est définie comme suit :

J(W,Z,Λ) = ∑i=1n ∑k=1K uik ∑j=1d λkjβ (xij - zkj)2

Avec les notations suivantes :

• uik ∈ {0,1} : indicatrice d'appartenance de l'échantillon i au cluster k
• zkj : coordonnée du centroïde du cluster k pour la caractéristique j
• λkj : poids associé à la caractéristique j dans le cluster k
• β > 1 : paramètre d'exposant de pondération

Mise à jour des poids des caractéristiques

La formule de mise à jour des poids λkj est :

λkj = 1 / ∑l=1d [Dkj/Dkl]1/(β-1)

où Dkj = ∑i=1n uik(xij - zkj)2 représente la dispersion intra-cluster pour la caractéristique j.

Ajustement adaptatif des poids

Une méthode alternative de mise à jour utilise une transition douce basée sur la dispersion courante :

λkj(t+1) = α λkj(t) + (1-α) * exp(-γ Dkj) / ∑l=1d exp(-γ Dkl)

Étapes algorithmiques

Entrée : Données X, nombre de clusters K, itérations maximales T, exposant β
Sortie : Étiquettes de clusters, centroïdes, matrice des poids

1. Initialisation :
   - Sélectionner K centroïdes initiaux aléatoirement
   - Initialiser les poids λ_{kj} = 1/d
   
2. Pour t = 1 jusqu'à T :
   a. Étape d'affectation :
      Pour chaque échantillon x_i, calculer la distance pondérée vers chaque centroïde :
      dist_{ik} = ∑_{j=1}^d λ_{kj}^β (x_{ij} - z_{kj})^2
      Affecter x_i au cluster le plus proche
   
   b. Étape de mise à jour des centroïdes :
      z_{kj} = (∑_{i:u_{ik}=1} x_{ij}) / (∑_{i:u_{ik}=1} 1)
   
   c. Étape de mise à jour des poids :
      Calculer la dispersion D_{kj} pour chaque cluster et caractéristique
      Mettre à jour les poids selon la formule dédiée
   
   d. Critère de convergence :
      Arrêter si les affectations ne changent plus ou si ΔJ < seuil
   
3. Retourner les résultats finaux

Implémentation MATLAB

function [etiquettes, centroids, poids, historique_critere] = kmeans_adaptatif_pondere(X, K, iter_max, beta)
% Implémentation du K-means avec pondération dynamique adaptative
% Paramètres :
%   X : matrice des données (n observations × d caractéristiques)
%   K : nombre de clusters souhaité
%   iter_max : limite supérieure d'itérations
%   beta : exposant de pondération (>1)

[~, nb_caract] = size(X);
rng('default');

% Initialisation des centroïdes par échantillonnage aléatoire
indices_init = randperm(size(X,1), K);
centroids = X(indices_init, :);
poids = ones(K, nb_caract) / nb_caract;
historique_critere = zeros(iter_max, 1);

for etape = 1:iter_max
    % Calcul des distances pondérées
    dists = zeros(size(X,1), K);
    for idx_cluster = 1:K
        ecarts = bsxfun(@minus, X, centroids(idx_cluster,:));
        dists(:,idx_cluster) = sum(ecarts.^2 .* poids(idx_cluster,:).^beta, 2);
    end
    
    % Affectation des observations
    [~, etiquettes] = min(dists, [], 2);
    
    % Mise à jour des centroïdes
    for idx_cluster = 1:K
        masque = etiquettes == idx_cluster;
        if any(masque)
            centroids(idx_cluster,:) = mean(X(masque,:), 1);
        end
    end
    
    % Recalcul des poids
    for idx_cluster = 1:K
        sous_ensemble = X(etiquettes == idx_cluster, :);
        if ~isempty(sous_ensemble)
            variances = var(sous_ensemble, 0, 1);
            variances(variances < eps) = eps;
            for j = 1:nb_caract
                denominateur = sum((variances(j)./variances).^(1/(beta-1)));
                poids(idx_cluster,j) = 1/denominateur;
            end
        end
    end
    
    % Calcul du critère de convergence
    valeur_courante = 0;
    for idx_cluster = 1:K
        masque = etiquettes == idx_cluster;
        if any(masque)
            ecart_pondere = sum(poids(idx_cluster,:).^beta .* var(X(masque,:),0,1));
            valeur_courante = valeur_courante + ecart_pondere;
        end
    end
    historique_critere(etape) = valeur_courante;
    
    % Vérification de convergence
    if etape > 1 && abs(historique_critere(etape) - historique_critere(etape-1)) < 1e-6
        historique_critere = historique_critere(1:etape);
        break
    end
end

% Visualisation de la convergence
figure;
plot(historique_critere, 'LineWidth',1.5);
xlabel('Itération');
ylabel('Valeur du critère');
title('Convergence de la fonction objectif');
grid on;
end

Variante basée sur l'entropie informationnelle

function poids_entropiques = calcul_poids_entropie(X, centroids, etiquettes, K, alpha)
% Calcul des poids via modulation entropique
% alpha : paramètre de régularisation

[~, nb_dim] = size(X);
poids_entropiques = zeros(K, nb_dim);

for k = 1:K
    indices_cluster = find(etiquettes == k);
    if isempty(indices_cluster)
        poids_entropiques(k,:) = 1/nb_dim;
        continue
    end
    
    donnees_cluster = X(indices_cluster, :);
    scores_caract = 1./(1 + var(donnees_cluster, 0, 1));
    scores_norm = scores_caract/sum(scores_caract);
    poids_entropiques(k,:) = exp(-alpha*scores_norm);
    poids_entropiques(k,:) = poids_entropiques(k,:)/sum(poids_entropiques(k,:));
end
end

Configuration des paramètres

% Recommandations de paramétrage
K = 3;              % Nombre de clusters à ajuster selon le jeu de données
iter_max = 100;     % Nombre maximal d'itérations
beta = 2;           % Exposant typiquement compris entre 2 et 3
alpha = 0.1;        % Facteur de modulation entropique

% Exécution typique
[etiquettes, centroids, poids, convergence] = kmeans_adaptatif_pondere(X, K, iter_max, beta);

Caractéristiques distinctives

• Sélection de caractéristiques intégrée : identification automatique des variables discriminantes pour le clustering
• Apprentissage adaptatif : ajustement dynamique des poids au fil des itérations
• Robustesse accrue : meilleure tolérance aux caractéristiques non informatives ou bruitées
• Transparence interprétative : matrice des poids offrant une lecture directe de l'importance relative des variables