k-significa ++ algoritmo y afloramientos

Question

Es bien sabido que el k-means el algoritmo sufre en la presencia de valores atípicos. k-means++ es un método eficaz para el grupo de centro de initalization. Yo estaba pasando por el PPT por los fundadores del método, Sergei Vassilvitskii y David Arthur http://theory.stanford.edu/~sergei/diapositivas/MURCIÉLAGOS-Medios.pdf (lámina 28), que muestra que el centro del cúmulo de inicialización no es afectada por valores atípicos como se ve a continuación.

Como por el k-means++ método, el farthermost puntos son más propensos a ser el inicial de los centros. De esta manera, el valor atípico punto (el de más a la derecha) deben también ser un primer centroide del grupo. ¿Cuál es la explicación de la figura?

Answer 1

Sí, el valor atípico os más probabilidades de ser elegido. Pero también hay muchos más inliers, la posibilidad de elegir uno de ellos también es considerable. Digamos que tiene un valor atípico que es 10 veces más, entonces es 100 veces más probabilidades de ser el piquete de un inlier. Si usted tiene 100 inliers, las probabilidades son del 50%, y si usted tiene 1000 inliers, la probabilidad de acertar el valor atípico es de aproximadamente 10%.

Pero a pesar de todo yo diría k++ es probablemente más propensos a escoger valores atípicos inicial de los centros (en el ejemplo anterior, al azar de la tomara en 1% resp. 0.1%), y por lo tanto probablemente más sensible a los valores atípicos (y de hecho, muchas personas reportan poca mejoría con k-means++). Sin embargo, no tiene mucho de una diferencia: cualquier k-means método se ve afectada, porque todos tienen que optimizar el mismo objetivo. Y la suma de cuadrados es un objetivo sensible a los valores atípicos, independientemente de cómo optimizar. Porque el problema está en el objetivo, recogiendo el valor atípico como centro, se puede producir una "mejor" resultado. El óptimo global puede tener este aspecto!

Answer 2

Esto parece explicarse en la diapositiva 27.

Ellos proponen la elección de la primera centroide del grupo al azar, como por clásico de k-means. Pero el segundo es el elegido de manera diferente. Nos fijamos en cada punto x, y asignar un peso igual a la distancia entre x y el primer elegido centroide, elevado a una potencia alfa. Alfa puede tomar varios valores interesantes.

Si alfa es 0, tenemos el clásico de k-means el algoritmo, debido a que todos los puntos tienen un peso de 1, para que todos tengan la misma probabilidad de ser elegido.

Si alfa es infinito (o, en la práctica, un número muy grande) tenemos que el punto Más alejado del método, donde el punto más alejado tiene un gran peso, que hace que sea muy probable que para ser recogidos. Como se ha visto en las diapositivas, 24-26, esto hace que sea sensible a los valores atípicos.

Se propone la configuración de la alfa 2. Esto le da una buena probabilidad de escoger a los puntos más alejados de la primera recogido centroide, pero no de forma automática escoger el más alejado. Esto le da a su método de k-means++, la propiedad de ser menos sensible a los valores atípicos.