Si le clustering k-means est une forme de modélisation de mélange gaussienne, peut-il être utilisé lorsque les données ne sont pas normales?

Je lis Bishop sur l'algorithme EM pour GMM et la relation entre GMM et k-means.

Dans ce livre, il est dit que k-means est une version difficile à attribuer de GMM. Je me demande si cela implique que si les données que j'essaie de regrouper ne sont pas gaussiennes, je ne peux pas utiliser k-means (ou du moins ce n'est pas approprié à utiliser)? Par exemple, que se passe-t-il si les données sont des images de chiffres manuscrits, constitués de 8 * 8 pixels chacun avec une valeur de 0 ou 1 (et supposent qu'ils sont indépendants donc ce devrait être un mélange de Bernoulli)?

Je suis un peu confus à ce sujet et j'apprécierai toutes vos pensées.

clustering data-mining k-means gaussian-mixture eddie.xie
la source

Si vous demandez s'il est valide d'effectuer un regroupement k-means sur des données non normales, la réponse est oui si les données sont supposées être continues. Les données binaires ne sont pas continues. Certaines personnes utilisent k-means sur de telles données, ce qui est autorisé sur le plan heuristique, mais théoriquement invalide.

ttnphns

Il n'y a pas de modèle de probabilité pour les k-moyennes, il n'y a donc pas d'hypothèse de normalité à invalider. (cela ne signifie pas pour autant que cela fonctionnera bien)

conjectures

@conjectures Hmm ... Mais k-menas est équivalent à GMM, et GMM suppose normal.

eddie.xie

@ttnphns Merci pour votre réponse! Donc, je suppose que si j'utilise TF-IDF pour transférer du texte en partitions et le rendre continu, je peux postuler et c'est valide?

eddie.xie

Je réalise soudain que le GMM est un mélange (somme de) quelques gaussiens et qu'il devrait pouvoir exprimer n'importe quelle distribution avec suffisamment de mélanges. Ainsi, même GMM et K-means sont équivalents ne signifie pas que K-means ne peut pas utiliser de données non normales car GMM peut exprimer n'importe quelle distribution. Est-ce exact?

eddie.xie

Réponses:

Dans des situations EM GMM typiques, on prend en compte la variance et la covariance. Cela ne se fait pas en k-means.

Mais en effet, l'une des heuristiques populaires pour k-means (remarque: k-means est un problème, pas un algorithme) - l'algorithme Lloyd - est essentiellement un algorithme EM, utilisant un modèle centroïde (sans variance) et des affectations dures.

Lorsque vous effectuez un regroupement de style k-means (c.-à-d. Minimisation de la variance), vous

minimiser par coïncidence la distance euclidienne au carré, car la contribution de la variance WCSS (somme intra-cluster) = la distance euclidienne au carré
affecter par coïncidence des objets au cluster le plus proche par distance euclidienne, car la fonction sqrt est monotone (notez que la moyenne n'optimise pas les distances euclidiennes, mais la fonction WCSS)
représenter des grappes utilisant uniquement un centroïde
obtenir des grappes en forme de cellules de Voronoï, c'est-à-dire des polygones
cela fonctionne mieux avec les clusters sphériques

La fonction objective k-means peut être formalisée comme suit:

{argmin}_{S} \sum_{je = 1}^{k} \sum_{X_{j} \in S_{je}} \sum_{ré = 1}^{ré} {(X_{j ré} - μ_{je ré})}^{2}

$\text{argmin}_S \sum_{i=1}^{k} \sum_{x_j \in S_i} \sum_{d=1}^{D} \left(x_{jd} - \mu_{id} \right)^2$

S = {S_{1} \dots S_{k}}

$S=\{S_1 \ldots S_k\}$

k

$k$

D

$D$

x_{j d}

$x_{jd}$

j

$j$

d

$d$

On dit généralement que k-means suppose des grappes sphériques. Il est également communément admis que les amas k-means sont des cellules de Voronoï, c'est-à-dire non sphériques. Les deux sont corrects et les deux sont faux. Tout d'abord, les grappes ne sont pas des cellules Voronoi complètes, mais uniquement les objets connus qu'elles contiennent. Il n'est pas nécessaire de considérer l'espace mort entre les clusters comme faisant partie de l'un ou l'autre cluster, car la présence d'un objet affecterait le résultat de l'algorithme. Mais il n'est pas beaucoup mieux de l'appeler "sphérique" non plus, simplement parce que la distance euclidienne est sphérique. K-means ne se soucie pas de la distance euclidienne. Tout ce que c'est, c'est une heuristique pour minimiser les variances . Et c'est en fait ce que vous devriez considérer comme k-means: minimisation de la variance.

Anony-Mousse -Reinstate Monica
la source

Permettez-moi de vous suggérer d'affiner un peu certaines de vos expressions - pour plus de précision. Par exemple, qu'est-ce que c'est minimize squared euclidean distanceou minimize the variances? Il doit y avoir des mots «somme de» ou «regroupés» ou autres, parce que nous avons plus de 2 clusters, n'est-ce pas?

ttnphns

BTW, puisque k-means minimise la somme regroupée dans le cluster de d ^ 2 divisée par le nombre d'objets dans le cluster respectif, votre point coincidentally minimize Euclidean distance, because the sqrt function is monotoneest, pour être précis, pas correct.

ttnphns

La fonction objective appropriée, pour laquelle vous pouvez prouver la convergence, est WCSS, somme des carrés intra-cluster . Et en effet, cela ne minimise pas les distances euclidiennes, mais la distance centroïde par euclidienne la plus proche est également l'affectation optimale du WCSS.

Anony-Mousse -Reinstate Monica

Votre formulation reste malheureusement douteuse . Qu'est - ce que la phrase minimize squared Euclidean distance, because WCSS variance contribution = squared euclidean distance moyenne ? Êtes-vous en train de dire que «les carrés au carré entre les objets en grappes sont minimisés parce que le WCSS des écarts est minimisé», ou simplement «le WCSS des écarts est minimisé, qui - les écarts - sont des distances euclidiennes par nature»? Ou quelque chose d'autre?

ttnphns

Évidemment, k-means n'est un bon choix que si vous voulez un modèle centroïde de vos données. Si vous souhaitez optimiser les distances par paires, utilisez le clustering hiérarchique.

Anony-Mousse -Reinstate Monica

GMM utilise des collines qui se chevauchent et s'étendent à l'infini (mais ne comptent pratiquement que pour 3 sigma). Chaque point obtient tous les scores de probabilité des collines. De plus, les collines sont "en forme d'oeuf" [d'accord, ce sont des ellipses symétriques ] et, en utilisant la matrice de covariance complète, peuvent être inclinées .

K-signifie assigner un point à un seul cluster, de sorte que les scores des autres centres de cluster sont ignorés (sont implicitement remis à zéro / ne se soucient pas). Les collines sont des bulles de savon sphériques. Lorsque deux bulles de savon se touchent, la frontière entre elles devient un plan (hyper-) plat. Tout comme lorsque vous soufflez une mousse de nombreuses bulles de savon, les bulles à l'intérieur ne sont pas plates mais sont carrées, de sorte que les frontières entre de nombreuses (hyper-) sphères forment en fait une partition Voronoi de l'espace. En 2D, cela a tendance à ressembler vaguement à un emballage rapproché hexagonal, pensez à une ruche (bien sûr, les cellules de Voronoi ne sont pas garanties d'être des hexagones). Une colline K-signifie est ronde et ne s'incline pas, elle a donc moins de pouvoir de représentation; mais il est beaucoup plus rapide à calculer, surtout dans les dimensions supérieures.

Parce que K-means utilise la métrique de distance euclidienne, il suppose que les dimensions sont comparables et de poids égal. Donc, si la dimension X a des unités de miles par heure, variant de 0 à 80, et la dimension Y a des unités de livres, variant de 0 à 400, et que vous ajustez des cercles dans cet espace XY, alors une dimension (et sa propagation) va être plus puissant que l'autre dimension et éclipsera les résultats. C'est pourquoi il est habituel de normaliser les données lors de la prise de K-means.

GMM et K-means modélisent les données en ajustant les meilleures approximations à ce qui est donné. GMM s'adapte aux œufs inclinés et K-means s'adapte aux sphères jusqu'à ce qu'il soit. Mais les données sous-jacentes pourraient avoir la forme de n'importe quoi, ce pourrait être une spirale ou une peinture de Picasso, et chaque algorithme fonctionnerait toujours et prendrait son meilleur coup. Le fait que le modèle résultant ressemble ou non aux données réelles dépend du processus physique sous-jacent générant les données. (Par exemple, les mesures de retard sont unilatérales; un gaussien est-il un bon ajustement? Peut-être.)

$R^n$

Ainsi, votre image binaire 8x8 va être interprétée comme un hypercube à 64 dimensions dans le premier hyperquadrant. Les algorithmes utilisent ensuite des analogies géométriques pour trouver des clusters. La distance, avec K-moyennes, apparaît comme une distance euclidienne dans un espace à 64 dimensions. C'est une façon de le faire.

Seigneur Dragon
la source

Notez que les deux algorithmes supposent également implicitement que les axes spatiaux sont également denses en tous points, de sorte que l'ajustement exponentiel, logarithmique ou sinusoïdal des données variant bénéficie généralement d'une pré-transformation pour remapper les données dans un domaine variant de manière approximativement linéaire.

DragonLord