raggruppamento con elementi uguali
Supponiamo di avere una serie di osservazioni: $\mathbf{X} = \{x_{1}, \dots, x_{n}\}\subseteq \mathbb{R}^{d}$, contenente $n$ osservazioni per una dimensionalità fissa $d$. Supponiamo di avere un numero intero fisso$k$. Il clustering k-means (con distanza l2) è il problema di trovare i centroidi dei cluster$S_{1}, \dots, S_{k}$ che minimizzano $$ cost(S_{1}, \dots, S_{1}) = \sum_{j=1}^{k}\sum_{x\in S_{j}}||x - q_{j}||^{2}, $$ dove $q_{1}, \dots, q_{k} \in \mathbb{R}^{d}$ sono i centroidi, cioè $q_{j} = \frac{1}{|S_{j}|}\sum_{x\in S_{j}}x$.
Supponiamo, lì dentro $\mathbf{X} = \{x_{1}, \dots, x_{n}\}$ ci sono elementi uguali $\{x\} \subset \mathbf{X}$.
È possibile che in una soluzione globale (teorica) questi siano uguali tra loro $\{x\}$ appartengono a diversi cluster?
Risposte
Per prima cosa dobbiamo distinguere tra la soluzione k-mean globalmente ottimale e il risultato ottenuto da un algoritmo k-means. Ce ne sono parecchi in giro e, a meno che il set di dati non sia molto piccolo, forniranno un ottimo locale che non è necessariamente quello globale. (Dici "globale" nella tua domanda, quindi presumo tu intenda la soluzione ottimale a livello globale; solo per essere sicuro.)
La risposta alla tua domanda inizia con "non normalmente"; loro$\|x-q_j\|$-i valori sono ovviamente uguali per tutti $q_j$, quindi una volta che l'algoritmo converge (o il file globalmente ottimale $q_j$ sono noti), verranno tutti assegnati al più vicino $q_j$, che è lo stesso per tutti.
Si verifica una situazione eccezionale che non è trattata dall'argomento di cui sopra, se non solo diverse $x$ sono uguali, ma sono anche alla stessa distanza di due o più $q_j$. In realtà non conosco alcun algoritmo che in questo caso possa assegnarli a cluster diversi, ma non posso escludere che esistano tali implementazioni.
Infatti non ho provato a dimostrarlo ma sospetto che l'ottimo globale non separerà mai osservazioni uguali, perché è probabile che se le osservazioni uguali sono separate, si può ottenere una soluzione migliore inserendole tutte nel cluster che ha di loro (o solo qualsiasi cluster se sono distribuiti uniformemente). Non sembra avere senso che queste osservazioni influenzino più di una media di cluster (rendendolo potenzialmente peggiore per la maggior parte delle altre osservazioni in quel cluster). Probabilmente si potrebbe dimostrarlo trascorrendo un pomeriggio a fare matematica, ma qui nessuna garanzia, solo un'ipotesi.
Quello che ho esaminato è un numero di esempi 1-d con punti uguali seduti tra due metà dei dati come 1,2,3,3,4,5. In effetti ottieni una soluzione migliore ($k=2$) in termini di costo se metti i due 3 entrambi in un cluster con 1,2, o con 4,5, invece che uno a sinistra e uno a destra (puoi verificarlo calcolando esplicitamente le funzioni di costo) .