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

61

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.

micro
la source
2
Le regroupement peut également être considéré comme une réduction de fonctionnalité. Où vous exprimez chaque échantillon par son affectation en grappe ou par leur codage clairsemé (réduisez donc T à k ). Ces deux approches maintiennent le nombre de points de données constant tout en réduisant les dimensions de "fonctionnalité".
Jeff

Réponses:

74

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.nn1

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 :(K1)

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

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=2100

PCA vs K-means

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=2n1n2n=n1+n2 qRnqi=n2/nn1iqi=n1/nn2q=1qi=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.ki(xiμk)2qGqGn×nG=XcXcXn×2Xc

(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.qqGqppGpqp

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 .pn1/nn2n2/nn1q

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 principaleK=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.qp

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 [...].K1

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 à .K1

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    
l'amibe dit de réintégrer Monica
la source
2
Je viens de jeter un coup d'œil dans le papier de Ding & He. Dans le théorème 2.2, ils indiquent que si vous faites k-means (avec k = 2) d'un nuage de données de dimension p et que vous effectuez également une ACP (basée sur des covariances) des données, tous les points appartenant au groupe A seront négatifs et les points appartenant au groupe B seront positifs, sur les scores PC1. Déclaration intéressante, - il devrait être testé dans des simulations. Le problème, cependant, est qu’elle suppose une solution optimale au niveau mondial, je pense; mais comment savoir si le regroupement réalisé était optimal?
ttnphns
1
@ttnphns, j'ai mis à jour ma simulation et ma figure pour tester cette affirmation plus explicitement. Si les projections sur PC1 doivent être positives et négatives pour les classes A et B, cela signifie que l'axe PC2 doit servir de frontière entre elles. C'est très proche d'être le cas dans mes 4 simulations de jouets, mais dans les exemples 2 et 3, il y a quelques points qui sont du mauvais côté de PC2. En ce qui concerne la convergence, j’ai exécuté la kmeansfonction avec 100 réplications: elle choisit une initialisation aléatoire différente à chaque fois, puis choisit la meilleure solution. Elle devrait donc, espérons-le, garantir que l’optimum global est atteint.
amibe dit de réintégrer Monica
1
@ttnphns: Je pense avoir compris ce qui se passait, veuillez consulter ma mise à jour.
amibe dit de réintégrer Monica
Amibe, merci de digérer l'article en cours de discussion et de nous avoir livré vos conclusions (+2); et de me le faire savoir personnellement! J'espère revenir dans quelques jours pour lire et étudier votre réponse. Mais l'appréciant déjà maintenant.
ttnphns
1
Poste exceptionnel. Y a-t-il une raison pour laquelle vous avez utilisé Matlab et non R? Juste curieux parce que je suis le cours ML Coursera et Andrew Ng utilise également Matlab, par opposition à R ou Python. Est-ce un choix général de ML?
Antoni Parellada
10

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.xy

entrez la description de l'image ici

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).v1v2v2v2v2

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

entrez la description de l'image ici

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.xi=d(μi,δi)dδixiμidi

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).

shuriken x bleu
la source
3
La façon dont vos ordinateurs sont étiquetés dans le graphique semble incohérente avec la discussion correspondante dans le texte. Notez que, bien que PCA soit généralement appliqué aux colonnes, & k-mean aux lignes, les deux peuvent être appliqués à l’un ou l’autre. Je n'ai pas lu le journal, mais je parie que c'est ce dont ils parlent.
gung - Réintégrer Monica
Désolé, je voulais dire le chiffre supérieur: à savoir., Les étiquettes v1 & v2 pour les PC.
gung - Rétablir Monica
Bon point, il peut être utile (vous ne pouvez pas savoir pourquoi) de compresser des groupes de points de données. Recherchez des groupes à l'aide de k-moyennes, compressez les enregistrements en moins en utilisant pca. En ce qui concerne le regroupement des fonctionnalités, cela pourrait être réellement utile.
shuriken x blue
2
Donc, vous dites essentiellement que le papier est faux? Il énonce explicitement (voir 3ème et 4ème phrases dans l’abrégé) et prétend avoir prouvé mathématiquement qu’il existe un lien spécifique, alors que vous dites qu’il n’ya pas de lien.
Amibe dit Réintégrer Monica
Ce que j'en ai tiré: La PCA améliore les solutions de clustering K-means. La connexion est que la structure de cluster est incorporée dans les premiers K-1 composants principaux. C'est la contribution.
shuriken x blue
7

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(nd2+d3)

À 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.n2O(n2d+n3)O(knid)nk=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.

Anony-Mousse
la source
2
Il serait bon de voir une explication / une vue d’ensemble plus précise du document de Ding & He (auquel ce lien est lié). Je ne le connais pas (encore) moi-même, mais je l'ai vu mentionné suffisamment de fois pour être assez curieux.
amibe dit de réintégrer Monica
3
Tu veux dire ça ? Oui, je l'ai aussi rencontré. Je pense que cela ne fait qu'ajouter à ma confusion. J'espérais que ce serait le fil conducteur qui pourrait clarifier les choses pour moi ... Maintenant que j'y réfléchis, je devrais peut-être mettre une prime à sa base. Je ne pense pas que j'aurai le temps dans les prochains jours d'étudier ce sujet moi-même.
amibe dit de réintégrer Monica
3
Ce paragraphe wiki est très étrange. Il est dit que Ding & He (2001/2004) était à la fois faux et non nouveau! Pour démontrer que ce n'était pas nouveau, il cite un article de 2004 (?!). Pour démontrer que c'était faux, il cite un article plus récent de 2014 qui ne cite même pas Ding & He. De poisson.
amibe dit de réintégrer Monica
3
Peut-être citer à nouveau le spam. Wikipedia est plein de promotion personnelle.
Anony-Mousse
1
Je pense avoir compris ce qui se passe dans Ding & He, veuillez voir ma réponse. En dehors de cela, votre argument concernant la complexité algorithmique n’est pas tout à fait correct, car vous comparez la décomposition complète en vecteurs propres de la matrice avec l’extraction de k-moyennes seulement "composants". Ce n'est pas une comparaison juste. Si vous utilisez un algorithme itératif pour PCA et n'extrayez que composants, je m'attendrais à ce qu'il fonctionne aussi vite que K-means. Donc, je ne suis pas sûr qu'il soit correct de dire que c'est inutile pour de vrais problèmes et seulement pour un intérêt théorique. n×nkk
amibe dit de réintégrer Monica
4

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

Dan Feldman
la source
3

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
r poon
la source