Comment puis-je savoir que mon algorithme de clustering k-means souffre de la malédiction de la dimensionnalité?

12

Je pense que le titre de cette question dit tout.

mathieu
la source
3
Je pense que vous allez devoir clarifier pour nous ce que vous entendez par un symptôme.
mdewey
Si "symptôme" est une version remise à la main de "test", alors vous pourriez peut-être prendre des sous-échantillons de votre ensemble de données - peut-être 66% de la taille de l'échantillon, effectuer votre analyse (kmeans, dans votre cas), puis voir comment nerveux les résultats sont. Par exemple, vous pouvez voir la fréquence à laquelle des observations particulières sont affectées au même cluster. Là encore, cela ne vaut peut-être pas la peine. Si vous vous inquiétez de la possibilité d'un problème de dimensionnalité, vous en avez probablement un. Vous pourriez envisager d'autres approches de clustering qui réduisent quelque peu la dimensionnalité.
generic_user
@generic_user si ce commentaire était une réponse, je le considérerais comme une réponse acceptée :)
mathieu
1
Cette question est suffisamment claire pour rester ouverte, OMI.
gung - Rétablir Monica
1
Souvent, vous rencontrez des problèmes beaucoup plus graves de k-means avant la «malédiction de la dimensionnalité». k-means peut fonctionner sur 128 données dimensionnelles (par exemple les vecteurs de couleur SIFT) si les attributs sont de bonne nature. Dans une certaine mesure, il peut même parfois fonctionner sur des données de texte à 10000 dimensions. Le modèle théorique de la malédiction ne s'applique jamais aux données réelles. Les problèmes les plus importants sont les caractéristiques incomparables, la rareté et l'impossibilité de visualiser et de revérifier le résultat.
A QUIT - Anony-Mousse

Réponses:

18

Cela aide à réfléchir à ce qu'est la malédiction de la dimensionnalité . Il y a plusieurs très bonnes discussions sur CV qui valent la peine d'être lues. Voici un point de départ: Expliquez «La malédiction de la dimensionnalité» à un enfant .

Je note que vous êtes intéressé par la façon dont cela s'applique au clustering moyens. Il convient de noter que k -means est une stratégie de recherche pour minimiser (uniquement) la distance euclidienne au carré. À la lumière de cela, il convient de réfléchir à la façon dont la distance euclidienne est liée à la malédiction de la dimensionnalité (voir: Pourquoi la distance euclidienne n'est-elle pas une bonne métrique dans les dimensions élevées? ). kk

La réponse courte de ces fils est que le volume (taille) de l'espace augmente à un rythme incroyable par rapport au nombre de dimensions. Même dimensions (ce qui ne me semble pas très «très dimensionnel») peuvent provoquer la malédiction. Si vos données étaient réparties uniformément dans cet espace, tous les objets deviennent approximativement équidistants les uns des autres. Cependant, comme le note @ Anony-Mousse dans sa réponse à cette question, ce phénomène dépend de la façon dont les données sont réparties dans l'espace; s'ils ne sont pas uniformes, vous n'avez pas nécessairement ce problème. Cela conduit à se demander si les données de haute dimension uniformément réparties sont très courantes (voir: la «malédiction de la dimensionnalité» existe-t-elle vraiment dans les données réelles? ). dix

Je dirais que ce qui importe n'est pas nécessairement le nombre de variables (la dimensionnalité littérale de vos données), mais la dimensionnalité effective de vos données. Dans l'hypothèse où dimensions sont «trop élevées» pour les k- moyennes, la stratégie la plus simple serait de compter le nombre de fonctionnalités dont vous disposez. Mais si vous vouliez penser en termes de dimensionnalité effective, vous pourriez effectuer une analyse des composants principaux (ACP) et regarder comment les valeurs propres chutent. Il est assez courant que la plupart des variations existent dans quelques dimensions (qui traversent généralement les dimensions d'origine de votre ensemble de données). Cela impliquerait que vous êtes moins susceptible d'avoir un problème avec les k- moyens dans le sens où votre dimensionnalité effective est en réalité beaucoup plus petite. dixkk

Une approche plus impliquée consisterait à examiner la distribution des distances par paires dans votre ensemble de données le long des lignes suggérées par @ hxd1011 dans sa réponse . L'examen de distributions marginales simples vous donnera une idée de l'uniformité possible. Si vous normalisez toutes les variables pour qu'elles se trouvent dans l'intervalle , les distances par paires doivent se trouver dans l'intervalle [ 0 , [0, 1]. Les distances très concentrées causeront des problèmes; d'un autre côté, une distribution multimodale peut être optimiste (vous pouvez voir un exemple dans ma réponse ici:Comment utiliser à la fois les variables binaires et continues dans le clustering?).[0, ]

Cependant, la question de savoir si les moyens fonctionneront est toujours une question compliquée. En supposant qu'il existe des regroupements latents significatifs dans vos données, ils n'existent pas nécessairement dans toutes vos dimensions ou dans les dimensions construites qui maximisent la variation (c'est-à-dire les principales composantes). Les grappes pourraient être dans les dimensions à plus faible variation (voir: Exemples d'ACP où les PC à faible variance sont «utiles» ). Autrement dit, vous pouvez avoir des clusters avec des points qui sont proches à l'intérieur et bien séparés entre sur seulement quelques-unes de vos dimensions ou sur des PC à faible variation, mais qui ne sont pas similaires à distance sur des PC à forte variation, ce qui entraînerait des k- moyennes d'ignorer les clusters que vous recherchez et de choisir des faux clusters à la place (quelques exemples peuvent être vus ici:kkComment comprendre les inconvénients des K-means ).

gung - Réintégrer Monica
la source
Il s'avère qu'il existe déjà une balise pour l' apprentissage multiple (aurait dû chercher en premier!). Pour résumer pour ceux qui ne le savent peut-être pas, l'idée est que, bien que les données de grande dimension aient tendance à être rares en termes de tout l'espace, elles peuvent être denses sur certaines hypersurface de cet espace.
GeoMatt22
+1 pour l'excellente réponse. Pourriez-vous nous en dire un peu plus sur la partie valeurs propres? Si la dimensionnalité effective est petite, recommandez-vous de faire l'ACP et de ne conserver que les premiers scores avec des valeurs propres élevées?
DataD'oh
@ DataD'oh, c'est certainement une possibilité, mais ce que je dis, c'est que vous n'avez pas besoin de faire ça. En effet, les données ne sont pas de grande dimension (lorsque seuls les premiers vecteurs propres ont des valeurs propres élevées), vous n'avez donc pas nécessairement besoin de faire quoi que ce soit - la malédiction de la dimensionnalité ne s'applique tout simplement pas.
gung - Réintègre Monica
@gung J'ai posté une nouvelle question . J'espère que ce n'est pas trop banal.
DataD'oh
7

Ma réponse n'est pas limitée aux moyennes de K, mais vérifiez si nous avons une malédiction de dimensionnalité pour toutes les méthodes basées sur la distance. K-means est basé sur une mesure de distance (par exemple, la distance euclidienne)

N0,5N(N-1)

Si nous avons le problème de la malédiction de la dimensionnalité, ce que vous verrez, c'est que ces valeurs sont très proches les unes des autres. Cela semble très contre-intuitif, car cela signifie que chacun est proche ou éloigné de chacun et que la mesure de la distance est fondamentalement inutile.


, qui vient de 1 x i = 016Xje=01Xj=01(Xje-Xj)2XjeXjrunifrnorm

Voici la simulation pour une dimension de 1 à 500, les caractéristiques sont une distribution uniforme de 0 à 1.

plot(0, type="n",xlim=c(0,0.5),ylim=c(0,50))
abline(v=1/6,lty=2,col=2)
grid()

n_data=1e3
for (p in c(1:5,10,15,20,25,50,100,250,500)){
    x=matrix(runif(n_data*p),ncol=p)
    all_dist=as.vector(dist(x))^2/p
    lines(density(all_dist))
}

entrez la description de l'image ici

Haitao Du
la source
1
P
amoeba
1
J'avais voté positivement à cause d'une démonstration du phénomène de rétrécissement euclidien sous des dimensions élevées. Mais la réponse ne démontre pas une souffrance de k-means se regroupant de la malédiction. La souffrance impliquerait que dans des dimensions élevées, des grappes raisonnablement bien séparées (et non des données aléatoires uniformes comme la vôtre) pourraient ne pas être découvertes avec autant de succès que dans des dimensions faibles. Vous n'avez pas abordé ce sujet.
ttnphns
P
@ttnphns merci pour votre commentaire et votre vote positif. Je verrai si je peux ajouter un paragraphe pour discuter de l'impact sur k moyennes.
Haitao Du