Algorimo "K-Means"

El algoritmo de k-means clustering es el referente principal entre los diversos métodos para seleccionar grupos representativos entre los datos.

Existen una serie matrices que constituyen el fundamento para la implementación de este tipo de algoritmo, entre ellas:
- Matriz de datos
- Matriz de distancias
- Matriz de centroides
- Matriz de pertenencias
Sus diferentes variantes se basan fundamentalmente en la forma de medir distancias entre los datos y los grupos, el criterio para definir la pertenencia de los datos a cada grupo y la forma de actualizar dichos grupos.

Algoritmo

El problema de k-means es determinar k medias de distribiciones Normales. Debemos de derivar una expresión para
Si  :

entonces:

El tener la sumatoria sobre las zij se justifica porque solamente una de ellas puede tener el valor de 1 para un ejemplo y las demás deben de ser cero.

El     

entonces es:

Finalmente debemos de tomar el valor esperado de esta probabilidad. En general para cualquier función lineal de z, E[f(z)] = f(E[z]). Como tenemos una función lineal de las z's:

donde:

El primer paso define Q en términos de los valores estimados de zij. El segundo paso encuentra los valores

    que maximizan la función Q.

Por lo que la hipótesis de máxima verosimilitud es la que minimiza la suma pesada de los errores al cuadrado. Esta cantidad se minimiza haciendo cada media como la media pesada de la muestra: