Quelle est la relation entre le clustering k-means et PCA?

Il est courant d'appliquer PCA (analyse en composantes principales) avant un algorithme de classification (tel que k-means). On pense que cela améliore les résultats de regroupement dans la pratique (réduction du bruit).

Cependant, je suis intéressé par une étude comparative et approfondie de la relation entre PCA et k-means. Par exemple, Chris Ding et Xiaofeng He, 2004, Clustering K-means via une analyse en composantes principales ont montré que "les composants principaux sont les solutions continues aux indicateurs d'appartenance à un cluster discret pour le clustering K-means". Cependant, j'ai du mal à comprendre ce document et Wikipedia prétend en fait que c'est faux .

En outre, les résultats des deux méthodes diffèrent quelque peu en ce sens que PCA permet de réduire le nombre de "caractéristiques" tout en préservant la variance, tandis que la mise en cluster réduit le nombre de "points de données" en résumant plusieurs points en fonction de leurs attentes / moyens. (dans le cas de k-moyennes). Donc, si le jeu de données consiste en $N$ points avec $T$ caractéristiques chacun, PCA vise à compresser les caractéristiques $T$ alors que le clustering vise à compresser les $N$ points de données.

Je cherche une explication profane des relations entre ces deux techniques + quelques papiers plus techniques reliant les deux techniques.

Il est vrai que la classification K-means et PCA semblent avoir des objectifs très différents et qu’à première vue, ils ne semblent pas être liés. Cependant, comme l'explique le document King-Clustering de Ding & He 2004 sur l' analyse en composantes principales , il existe un lien étroit entre elles.

L'intuition est que PCA cherche à représenter tous les vecteurs de données sous forme de combinaisons linéaires d'un petit nombre de vecteurs propres et à le faire pour minimiser l'erreur de reconstruction au carré moyen. En revanche, K-means cherche à représenter tous les n vecteurs de données via un petit nombre de centroïdes de grappes, c'est-à-dire de les représenter sous forme de combinaisons linéaires d'un petit nombre de vecteurs de centroïdes de grappes où les pondérations de combinaisons linéaires doivent être toutes nulles, à l'exception du simple 1 . Ceci est également fait pour minimiser l'erreur de reconstruction au carré moyen.$n$$n$$1$

Donc, K-means peut être vu comme une ACP super-épars.

Ce que fait le papier Ding & He, c’est pour rendre cette connexion plus précise.

Malheureusement, le papier Ding & He contient au mieux des formulations bâclées et peut facilement être mal compris. Par exemple, il pourrait sembler que Ding & He affirme avoir prouvé que les centroïdes de cluster de la solution de clustering K-means se situent dans le sous-espace de la PCA à la :$(K-1)$

Théorème 3.3. Le sous-espace centroïde de cluster est recouvert par les premières directions principales [...].$K-1$

Pour cela impliquerait que les projections sur l’axe PC1 seront nécessairement négatives pour un groupe et positives pour un autre groupe, c’est-à-dire que l’axe PC2 séparera parfaitement les groupes.$K=2$

C'est soit une erreur, soit une écriture bâclée; dans tous les cas, pris littéralement, cette affirmation est fausse.

$K=2$$100$

On peut clairement voir que même si les centroïdes de la classe ont tendance à être assez proches de la direction du premier PC, ils ne tombent pas exactement dessus. De plus, même si l’axe PC2 sépare parfaitement les grappes dans les sous-parcelles 1 et 4, quelques points se trouvent du mauvais côté dans les sous-parcelles 2 et 3.

Donc, l'accord entre K-means et PCA est assez bon, mais ce n'est pas exact.

$K=2$$n_1$$n_2$$n=n_1+n_2$ $\mathbf q\in\mathbb R^n$$q_i = \sqrt{n_2/nn_1}$$i$$q_i = -\sqrt{n_1/nn_2}$$\|\mathbf q\| = 1$$\sum q_i = 0$

Ding & He montrent que la fonction de perte de K-moyennes (que l'algorithme de K-moyennes minimise) peut être réécrite de manière équivalente en tant que , où est le matrice de Gram de produits scalaires entre tous les points: , où est le matrice de données et est la matrice de données centrée.$\sum_k \sum_i (\mathbf x_i - \boldsymbol \mu_k)^2$$-\mathbf q^\top \mathbf G \mathbf q$$\mathbf G$$n\times n$$\mathbf G = \mathbf X_c^\top \mathbf X_c$$\mathbf X$$n\times 2$$\mathbf X_c$

(Remarque: j'utilise une notation et une terminologie qui diffèrent légèrement de leur papier mais que je trouve plus claires).

Donc, la solution K-means est un vecteur unitaire centré maximisant . Il est facile de montrer que la première composante principale (normalisée pour avoir une somme unitaire de carrés) est le vecteur propre de la matrice de Gram, c’est-à-dire qu’il s’agit également d’un vecteur unitaire centré maximisant . La seule différence est que est en outre contraint de n'avoir que deux valeurs différentes alors que n'a pas cette contrainte.$\mathbf q$$\mathbf q^\top \mathbf G \mathbf q$$\mathbf p$$\mathbf p^\top \mathbf G \mathbf p$$\mathbf q$$\mathbf p$

En d'autres termes, K-means et PCA maximisent la même fonction objectif , la seule différence étant que K-means a une contrainte "catégorielle" supplémentaire.

Il va de soi que la plupart du temps, les solutions K-means (contrainte) et PCA (contrainte) seront très proches l'une de l'autre, comme nous l'avons vu plus haut dans la simulation, mais il ne faut pas s'attendre à ce qu'elles soient identiques. Prendre et définir tous ses éléments négatifs pour qu'ils soient égaux à et tous ses éléments positifs à ne donneront généralement pas exactement .$\mathbf p$$-\sqrt{n_1/nn_2}$$\sqrt{n_2/nn_1}$$\mathbf q$

Ding & He semblent bien le comprendre car ils formulent leur théorème comme suit:

Théorème 2.2. Pour la classification K-moyennes où , la solution continue du vecteur indicateur de la grappe est la [première] composante principale$K= 2$

Notez que les mots "solution continue". Après avoir prouvé ce théorème, ils expliquent en outre que PCA peut être utilisée pour initialiser les itérations de K-moyennes, ce qui est tout à fait logique étant donné que nous nous attendons à ce que soit proche de . Mais il faut encore effectuer les itérations, car elles ne sont pas identiques.$\mathbf q$$\mathbf p$

Cependant, Ding & He développe ensuite un traitement plus général pour et finit par formuler le théorème 3.3 comme suit:$K>2$

Théorème 3.3. Le sous-espace centroïde de cluster est recouvert par les premières directions principales [...].$K-1$

Je ne suis pas passé par les calculs de la section 3, mais je crois que ce théorème se réfère en fait également à la "solution continue" de K-means, c.-à-d. étalé [...] ".

Ding & He, cependant, ne font pas cette qualification importante, et écrivent en outre dans leur résumé que

Nous montrons ici que les composants principaux sont les solutions continues aux indicateurs d’appartenance à un cluster discret pour le clustering K-means. De manière équivalente, nous montrons que le sous-espace couvert par les centroïdes de cluster est donné par l'expansion spectrale de la matrice de covariance des données tronquée à .$K-1$

La première phrase est absolument correcte, mais la seconde ne l’est pas. Il m'est difficile de savoir s'il s'agit d'une écriture (très) bâclée ou d'une erreur réelle. J'ai très poliment envoyé un courrier électronique aux deux auteurs pour leur demander des éclaircissements. (Mise à jour deux mois plus tard: je n'ai jamais eu de leurs nouvelles.)

Code de simulation Matlab

figure('Position', [100 100 1200 600])

n = 50;
Sigma = [2 1.8; 1.8 2];

for i=1:4
    means = [0 0; i*2 0];

    rng(42)
    X = [bsxfun(@plus, means(1,:), randn(n,2) * chol(Sigma)); ...
         bsxfun(@plus, means(2,:), randn(n,2) * chol(Sigma))];
    X = bsxfun(@minus, X, mean(X));
    [U,S,V] = svd(X,0);
    [ind, centroids] = kmeans(X,2, 'Replicates', 100);

    subplot(2,4,i)
    scatter(X(:,1), X(:,2), [], [0 0 0])

    subplot(2,4,i+4)
    hold on
    scatter(X(ind==1,1), X(ind==1,2), [], [1 0 0])
    scatter(X(ind==2,1), X(ind==2,2), [], [0 0 1])
    plot([-1 1]*10*V(1,1), [-1 1]*10*V(2,1), 'k', 'LineWidth', 2)
    plot(centroids(1,1), centroids(1,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
    plot(centroids(1,1), centroids(1,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)
    plot(centroids(2,1), centroids(2,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
    plot(centroids(2,1), centroids(2,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)

    plot([-1 1]*5*V(1,2), [-1 1]*5*V(2,2), 'k--')
end

for i=1:8
    subplot(2,4,i)
    axis([-8 8 -8 8])
    axis square
    set(gca,'xtick',[],'ytick',[])
end    

PCA et K-means font des choses différentes.

PCA est utilisé pour l'apprentissage de la réduction de la dimension / sélection des fonctions / représentation, par exemple lorsque l'espace de fonctions contient trop de fonctions non pertinentes ou redondantes. Le but est de trouver la dimensionnalité intrinsèque des données.

Voici un exemple en deux dimensions qui peut être généralisé à des espaces de dimension supérieure. Le jeu de données a deux entités, et , chaque cercle est un point de données.$x$$y$

Dans l'image, a une magnitude supérieure à celle de . Ce sont les vecteurs propres. La dimension des données est réduite de deux dimensions à une dimension (choix limité dans ce cas) et cela se fait en projetant sur la direction du vecteur (après une rotation où devient parallèle ou perpendiculaire à l'un des axes) . En effet, est orthogonal à la direction de la plus grande variance. Une façon de penser à cela est une perte minimale d'informations. (Il y a toujours une perte car un axe de coordonnées est perdu).$v1$$v2$$v2$$v2$$v2$

K-means est un algorithme de classification qui renvoie le regroupement naturel des points de données, en fonction de leur similarité. C'est un cas particulier des modèles de mélange gaussien .

Dans l'image ci-dessous, le jeu de données a trois dimensions. Le tracé 3D à gauche permet de constater que la dimension peut être «supprimée» sans perdre beaucoup d'informations. PCA est utilisé pour projeter les données sur deux dimensions. Dans la figure à gauche, le plan de projection est également montré. Ensuite, K-moyennes peut être utilisé sur les données projetées pour étiqueter les différents groupes, sur la figure de droite, codés avec des couleurs différentes.$X$

La PCA ou d'autres techniques de réduction de dimensionnalité sont utilisées avant les méthodes non supervisées ou supervisées en apprentissage automatique. Outre les raisons évoquées par vous et celles que j'ai mentionnées ci-dessus, il est également utilisé à des fins de visualisation (projection en 2D ou 3D à partir de dimensions supérieures).

En ce qui concerne l'article, je ne pense pas qu'il y ait de lien, PCA ne dispose d'aucune information concernant le regroupement naturel des données et fonctionne sur l'ensemble des données, pas sur des sous-ensembles (groupes). Si certains groupes peuvent être expliqués par un vecteur propre (simplement parce que ce groupe particulier est réparti dans cette direction), ce n'est qu'une coïncidence et ne doit pas être considéré comme une règle générale.

"PCA vise à compresser les caractéristiques T alors que le clustering vise à compresser les N points de données."

En effet, la compression est une façon intuitive de penser à la PCA. Cependant, dans K-means, pour décrire chaque point par rapport à son cluster, vous avez toujours besoin d'au moins la même quantité d'informations (par exemple, des dimensions) , où est la distance et que est stocké. au lieu de . Et vous devez également stocker le pour savoir en quoi le delta est relatif. Vous pouvez bien sûr stocker et mais vous ne pourrez pas récupérer les informations réelles dans les données.$x_i = d( \mu_i, \delta_i)$$d$$\delta_i$$x_i$$\mu_i$$d$$i$

Le clustering ajoute vraiment des informations. Je pense qu’il s’agit de scinder les données en groupes naturels (qui ne doivent pas nécessairement être disjoints) sans savoir ce que l’étiquette signifie pour chaque groupe (enfin, jusqu’à ce que vous examiniez les données au sein des groupes).

Il est courant de blanchir les données avant d’utiliser k-means. La raison en est que k-means est extrêmement sensible à l’échelle, et lorsque vous avez des attributs mixtes, il n’ya plus d’échelle "vraie". Ensuite, vous devez normaliser, normaliser ou blanchir vos données. Aucune n'est parfaite, mais le blanchiment supprimera la corrélation globale qui peut parfois donner de meilleurs résultats. PCA / blanchissement est puisque vous utilisez la matrice de covariance.$O(n\cdot d^2 + d^3)$

À ma connaissance, la relation entre k-means et PCA ne se trouve pas dans les données d'origine . C’est utiliser PCA sur la matrice de distance (qui a entrées, et effectuer une PCA complète est donc - c’est-à-dire prohibitif, en particulier par rapport à k-means qui est où est le seul terme générique), et peut-être uniquement pour . K-means est un problème d'optimisation des moindres carrés, de même que la PCA. k-means essaie de trouver la partition des moindres carrés des données. La PCA trouve le vecteur d’appartenance à la grappe des moindres carrés.$n^2$$O(n^2\cdot d+n^3)$$O(k\cdot n \cdot i\cdot d)$$n$$k=2$

La première Eigenvector a la plus grande variance, donc le fractionnement sur ce vecteur (qui ressemble à l' appartenance de cluster, et non coordonnées de données d' entrée!) Des moyens optimisant entre la variance des grappes . En maximisant la variance entre les grappes, vous minimisez également la variance au sein d'une grappe.

Mais pour de vrais problèmes, c'est inutile. C'est seulement d'un intérêt théorique.

La résolution de k-moyennes sur son approximation de rang bas O (k / epsilon) (c'est-à-dire, projeter sur l'étendue du premier plus grand vecteur singulier comme dans PCA) donnerait une approximation (1 + epsilon) en terme d'erreur multiplicative.

En particulier, une projection sur le vecteur k-plus grand donnerait une approximation 2.

En fait, cette projection permet d’approximer la somme des distances au carré pour N'IMPORTE QUEL ensemble de k centres. Ensuite, nous pouvons calculer le coreset sur les données réduites afin de réduire les entrées en points poly (k / eps) qui se rapprochent de cette somme.

Voir: Dan Feldman, Melanie Schmidt et Christian Sohler: Transformer le big data en données minuscules: Ensembles de cores de taille constante pour k-means, PCA et clustering projectif. SODA 2013: 1434-1453

Relation intuitive entre PCA et KMeans

1. Théoriquement, l'analyse dimensionnelle de la PCA (la première dimension K conservant, par exemple, 90% de la variance ... n'a pas besoin d'avoir une relation directe avec le groupe K Means), mais l'intérêt de l'utilisation de la PCA provient: a) d'une considération pratique compte tenu de la nature des objets nous analysons nos tendances à se regrouper naturellement autour de / évoluer (à partir d’un certain segment) de leurs principales composantes (âge, sexe ..) ) en se concentrant sur ces dimensions clés En termes simples, c’est comme si l’axe XY nous permettait de maîtriser tout concept mathématique abstrait mais de manière plus avancée.

2. K signifie essayer de minimiser la distance globale dans un groupe pour un K donné

3. Pour un ensemble d'objets avec N paramètres de dimension, les objets similaires par défaut auront les paramètres MOST "similaires" à l'exception de quelques différences clés (par exemple, un groupe de jeunes étudiants en informatique, de jeunes danseurs, des humains… auront des caractéristiques très similaires (faible variance) mais quelques caractéristiques clés encore très diverses et capturant ces "Composants principaux" capturent essentiellement la majorité de la variance, par exemple la couleur, la zone de résidence ... Par conséquent, une distorsion faible si nous négligeons les caractéristiques de différences mineures, ou la conversion en les PC plus bas ne perdront pas beaucoup d'informations
4. Il est donc «très probable» et «très naturel» que les regrouper pour examiner les différences (variations) ait un sens pour l’évaluation des données (par exemple, si vous effectuez 1 000 enquêtes par semaine dans la rue principale, en les regroupant en fonction de critères ethniques). , l’âge ou le niveau d’instruction selon PC ont du sens) Sous la mission de K Means, nous essayons d’établir un nombre suffisant de K afin que ces éléments de groupe (dans un cluster) aient globalement la plus petite distance (minimisée) entre le centroïde et le coût. établir et faire fonctionner les K clusters est optimal (chaque membre en tant que cluster n'a pas de sens car cela est trop coûteux à maintenir et aucune valeur)
5. K signifie que le regroupement peut être facilement "inspecté visuellement" pour être optimal, si tel est le cas, par exemple si des groupes d'âge / ethnies / groupes religieux différents ont tendance à exprimer des opinions similaires, donc si vous regroupez ces enquêtes sur Ces PC, alors qui atteignent l’objectif de minisation (réf. 1). Aussi, ces PC (ethnie, âge, religion, etc.) sont assez souvent orthogonaux, donc distincts visuellement en visionnant le PCA.
6. Cependant, cette déduction intuitive conduit à une condition suffisante mais non nécessaire. (Réf. 2: Cependant, le fait que PCA soit un assouplissement utile du clustering k-means n’était pas un résultat nouveau (voir, par exemple, [35]), et il est simple de trouver des contre-exemples à la déclaration spécifiant que le sous-espace centroïde de cluster est étendu par les directions principales. [36])

Le choix de groupes basés sur / le long des points de contact peut aisément conduire à un mécanisme d'allocation confortable

Celui-ci pourrait être un exemple si x est le premier PC suivant l'axe X: (........... CC1 ............... CC2 ..... ....... Axe X CC3) où l'axe X dit capturer plus de 9X% de la variance et est le seul PC

6.Enfin, PCA est également utilisé pour visualiser après que K Means soit terminé (Réf 4)

Si la PCA affiche * notre résultat de regroupement en K comme étant orthogonal ou proche de, cela signifie que notre regroupement est correct, chacun présentant des caractéristiques uniques.

(* puisque, par définition, PCA découvre / affiche ces dimensions principales (1D à ​​3D) telles que, par exemple, K (PCA) capturera probablement une grande majorité de la variance.

Ainsi, PCA est à la fois utile pour visualiser et confirmer un bon regroupement, ainsi qu’un élément intrinsèquement utile pour déterminer le regroupement des moyennes K - à utiliser avant et après les K. moyens.

Référence:

1. https://msdn.microsoft.com/en-us/library/azure/dn905944.aspx
2. https://en.wikipedia.org/wiki/Principal_component_analysis
3. SEGMENTATION EN UTILISANT L'ANALYSE PRINCIPALE DES COMPOSANTS: APPLICATION DE L'AUTONOMIE PERSONNE ÂGÉE-HANDICAP (Combes & Azema)
4. http://cs229.stanford.edu/notes/cs229-notes10.pdf Andrew Ng