Comment mesurer la forme d'un cluster?

Je sais que cette question n'est pas bien définie, mais certains clusters ont tendance à être elliptiques ou se situent dans un espace dimensionnel inférieur tandis que les autres ont des formes non linéaires (dans les exemples 2D ou 3D).

Existe-t-il une mesure de non-linéarité (ou "forme") des grappes?

Notez que dans l'espace 2D et 3D, ce n'est pas un problème de voir la forme d'un cluster, mais dans les espaces de dimension supérieure, il est difficile de dire quelque chose sur la forme. En particulier, existe-t-il des mesures de la conformation du cluster convexe?

J'ai été inspiré pour cette question par de nombreuses autres questions de regroupement où les gens parlent de clusters mais que personne ne peut les voir (dans les espaces de dimension supérieure). De plus, je sais qu'il existe des mesures de non-linéarité pour les courbes 2D.

J'aime les modèles Gaussian Mixture (GMM).

L'une de leurs caractéristiques est que, dans le domaine probit , ils agissent comme des interpolateurs par morceaux. Une implication de ceci est qu'ils peuvent agir comme une base de remplacement, un approximateur universel. Cela signifie que pour les distributions non gaussiennes, comme celles lognormales, weibull ou plus folles non analytiques, tant que certains critères sont remplis - le GMM peut approximer la distribution.

Donc, si vous connaissez les paramètres de l'approximation optimale AICc ou BIC à l'aide de GMM, vous pouvez projeter cela à des dimensions plus petites. Vous pouvez le faire pivoter et regarder les axes principaux des composants du GMM approximatif.

La conséquence serait une manière informative et visuellement accessible de regarder les parties les plus importantes des données de dimension supérieure en utilisant notre perception visuelle de visualisation 3D.

EDIT: (bien sûr, whuber)

Il existe plusieurs façons de regarder la forme.

• Vous pouvez regarder les tendances des moyens. Une lognormale est approximée par une série de gaussiens qui se rapprochent progressivement et dont les poids diminuent le long de la progression. La somme se rapproche de la queue plus lourde. En n dimensions, une séquence de ces composants ferait un lobe. Vous pouvez également suivre les distances entre les moyens (convertir en dimension élevée) et les cosinus de direction entre les deux. Cela se convertirait à des dimensions beaucoup plus accessibles.
• Vous pouvez créer un système 3D dont les axes sont le poids, la magnitude de la moyenne et la magnitude de la variance / covariance. Si vous avez un nombre de clusters très élevé, c'est un moyen de les visualiser les uns par rapport aux autres. C'est un moyen précieux de convertir 50k pièces avec 2k mesures chacune en quelques nuages ​​dans un espace 3D. Je peux exécuter le contrôle de processus dans cet espace, si je le souhaite. J'aime la récursivité de l'utilisation du contrôle basé sur le modèle de mélange gaussien sur les composants du modèle de mélange gaussien qui correspond aux paramètres de la pièce.
• En termes de désencombrement, vous pouvez jeter par très petit poids, ou par poids par covariance, ou autre.
• Vous pouvez tracer le nuage GMM en termes de BIC, $R^2$, Distance de Mahalanobis aux composants ou dans l'ensemble, probabilité d'appartenance ou dans l'ensemble.
• Vous pouvez le regarder comme des bulles qui se croisent . L'emplacement de probabilité égale (zéro divergence Kullback-Leibler) existe entre chaque paire de clusters GMM. Si vous suivez cette position, vous pouvez filtrer par probabilité d'appartenance à cet emplacement. Il vous donnera des points de limites de classification. Cela vous aidera à isoler les «solitaires». Vous pouvez compter le nombre de ces limites au-dessus du seuil par membre et obtenir une liste de «connectivité» par composant. Vous pouvez également regarder les angles et les distances entre les emplacements.
• Vous pouvez rééchantillonner l'espace en utilisant des nombres aléatoires étant donné les fichiers PDF gaussiens, puis effectuer une analyse des composants principaux sur celui-ci, et regarder les formes propres et les valeurs propres qui leur sont associées.

ÉDITER:

Que signifie la forme? Ils disent que la spécificité est l'âme de toute bonne communication. Que voulez-vous dire par «mesure»?

Des idées sur ce que cela peut signifier:

• Sensation / sensation de la norme générale du globe oculaire. (accessibilité visuelle extrêmement qualitative)
• mesure de la forme GD&T (coplanarité, concentricité, etc.) (extrêmement quantitative)
• quelque chose de numérique (valeurs propres, covariances, etc ...)
• une coordonnée de dimension réduite utile (comme les paramètres GMM devenant des dimensions)
• un système à bruit réduit (lissé en quelque sorte, puis présenté)

La plupart des "plusieurs façons" sont une variante de celles-ci.

Cela peut être assez simpliste, mais vous pouvez obtenir un aperçu en effectuant une analyse des valeurs propres sur chacun de vos clusters.

Ce que j'essaierais, c'est de prendre tous les points attribués à un cluster et de les ajuster avec une gaussienne multivariée. Ensuite, vous pouvez calculer les valeurs propres de la matrice de covariance ajustée et les tracer. Il existe plusieurs façons de procéder; peut-être la plus connue et la plus utilisée est appelée analyse en composantes principales ou ACP .

Une fois que vous avez les valeurs propres (également appelées spectre), vous pouvez examiner leurs tailles relatives pour déterminer comment "étiré" le cluster est dans certaines dimensions. Moins le spectre est uniforme, plus l'amas est "en forme de cigare" et plus le spectre est uniforme, plus l'amas est sphérique. Vous pourriez même définir une sorte de métrique pour indiquer à quel point les valeurs propres ne sont pas uniformes (entropie spectrale?); voir http://en.wikipedia.org/wiki/Spectral_flatness .

Comme avantage secondaire, vous pouvez examiner les principaux composants (les vecteurs propres associés à de grandes valeurs propres) pour voir «où» les clusters «en forme de cigare» pointent dans votre espace de données.

Naturellement, il s'agit d'une approximation grossière pour un cluster arbitraire, car elle ne modélise que les points du cluster comme un seul ellipsoïde. Mais, comme je l'ai dit, cela pourrait vous donner un aperçu.

Les algorithmes de clustering de corrélation tels que 4C, ERiC ou LMCLUS considèrent généralement les clusters comme des variétés linéaires. C'est-à-dire des hyperplans k-dimensionnels dans un espace d-dimensionnel. Eh bien, pour 4C et ERiC uniquement localement linéaire, ils peuvent donc être en fait non convexes. Mais ils essaient toujours de détecter des grappes de dimensionnalité locale réduite.

Trouver des grappes de forme arbitraire dans des données de haute dimension est un problème assez difficile. En particulier, en raison de la malédiction de la dimensionnalité qui laisse exploser l'espace de recherche et, en même temps, nécessite également que vous disposiez de données d'entrée beaucoup plus importantes si vous voulez toujours des résultats significatifs . Beaucoup trop d'algorithmes ne font pas attention à ce que ce qu'ils trouvent est toujours significatif ou pourrait aussi être aléatoire.

Donc, en fait, je crois qu'il y a d'autres problèmes à résoudre avant de penser à la convexité de la non-convexité d'amas complexes dans un espace de grande dimension.

Jetez également un œil à la complexité du calcul de la coque convexe dans des dimensions supérieures ...

De plus, avez-vous un vrai cas d'utilisation pour cela au-delà de la curiosité?

Si votre dimensionnalité n'est pas beaucoup plus élevée que 2 ou 3, il pourrait être possible de projeter le cluster d'intérêt dans l'espace 2D plusieurs fois et de visualiser les résultats ou d'utiliser votre mesure 2D de non-linéarité. J'ai pensé à cela à cause de la méthode Random Projections http://users.ics.aalto.fi/ella/publications/randproj_kdd.pdf .

Des projections aléatoires peuvent être utilisées pour réduire la dimensionnalité afin de construire un index. La théorie est que si deux points sont proches dans les dimensions D et que vous prenez une projection aléatoire dans les dimensions d avec d

Pour être concret, vous pouvez penser à projeter un globe sur une surface plane. Peu importe comment vous le projetez, New York et New Jersey seront ensemble, mais vous ne ferez que rarement cohabiter New York et Londres.

Je ne sais pas si cela peut vous aider rigoureusement mais cela pourrait être un moyen rapide de visualiser les clusters.