Guía para la agrupación en clústeres de K-Means con Java

En esta guía, cubriremos la teoría y la implementación de la agrupación en clústeres de K-Means, utilizando Core Java, con ejemplos prácticos y pros y contras del algoritmo.

Introducción

K-Means es uno de los algoritmos de agrupación en clústeres más simples y populares en la ciencia de datos. Divide los datos en función de su proximidad a uno de los K llamados centroides: puntos de datos que son la media de todas las observaciones en el grupo. Una observación es un único registro de datos de un formato específico.

Esta guía cubrirá la definición y el propósito del agrupamiento en general, cuál es la estructura básica del algoritmo K-Means, qué problemas comunes surgen al usarlo y cómo manejarlos, así como algunas variaciones del algoritmo o algoritmos similares que ser referenciado.

¿Qué es la agrupación en clústeres? {#lo que se está agrupando}

El agrupamiento es la división de datos en grupos que son significativos o útiles. Pueden ser ambos, pero también pueden ser solo uno de esos dos. Los humanos agrupan naturalmente los objetos que perciben en grupos y luego clasifican los nuevos objetos que encuentran en uno de dichos grupos.

Cuando eres niño, te das cuenta de que existe un árbol. Entiendes el concepto de un árbol al ver las características compartidas de los árboles, así como las diferencias de los árboles con otras cosas. Por ejemplo, algo que tiene un tronco, ramas y hojas en general puede constituir un árbol, por lo que las cosas que son similares de acuerdo con esos atributos son percibidas por usted como árboles. También son diferentes de cosas que no son árboles, como arbustos u hongos, porque difieren en ciertas características.

Cuando eras niño, (probablemente) no creaste una taxonomía completa del mundo vivo que te rodea para aprender a distinguir un perro de un árbol. Lo hiciste a través de la agrupación. Gradualmente, a medida que fue expuesto al mundo, se dio cuenta de que está viendo ciertas similitudes que se pueden usar para agrupar objetos porque se verán y se comportarán de manera similar cada vez que se encuentren.

El uso de ese conocimiento sobre la existencia de un grupo significativo de datos para luego reconocer nuevos objetos se denomina clasificación.

La agrupación significativa puede ayudarnos a comprender y comunicarnos sobre el mundo que nos rodea al agrupar cosas según su estructura natural.

Por ejemplo, crear taxonomías del mundo vivo nos ayuda a comunicarnos sobre biología y todas sus disciplinas y nos permite sacar conclusiones significativas, a pesar de que no siempre está perfectamente claro dónde se deben trazar las líneas.

La agrupación de páginas en la red mundial según su tema o contenido ayuda a los motores de búsqueda a recomendarnos cosas relacionadas con nuestras consultas o nuestros intereses.

Los clústeres significativos son esenciales para los estudios de biología, clima, medicina, negocios, etc.

Los clústeres útiles no reflejan necesariamente una estructura o agrupación del mundo real, sino abstracciones útiles. Se pueden usar para reducir la dimensionalidad de los datos al resumir múltiples atributos relacionados en uno, se pueden usar para comprimir datos creando una tabla de prototipos y asignando a cada prototipo un número entero para usarlo como abreviatura, así como para mejorar el rendimiento de algunos algoritmos de clasificación como Nearest Neighbor.

Un prototipo es un punto de datos representativo y puede ser una de las observaciones o simplemente un valor posible para una observación. En el caso de K-Means, el prototipo es la media de todas las observaciones en el grupo, de donde deriva su nombre.

Algoritmo de K-Means

K-Means es un algoritmo de agrupamiento basado en prototipos, lo que significa que su objetivo es asignar todas las observaciones a su prototipo más cercano.

Pseudocódigo

1
2
3
4
5
1. Select K initial centroids
REPEAT:
    2. Form K clusters by assigning each observation to its nearest centroid's cluster
    3. Recompute centroids for each cluster
UNTIL centroids do not change

k-means clustering in java

Algoritmo de K-Means explicado

El usuario especifica un número “K” y el algoritmo comienza seleccionando observaciones “K” del conjunto de datos. Esta selección se puede realizar de diferentes maneras y puede influir en gran medida en el resultado final, pero por ahora imagínese seleccionando aleatoriamente puntos “K” del conjunto de datos. Llamemos a esos puntos centroides de grupos.

El siguiente paso es revisar todas las observaciones y clasificarlas en grupos. Para cada observación, su grupo asignado es el mismo que el de su centroide más cercano. Si un punto está igualmente cerca de dos centroides, puede asignarse aleatoriamente a uno de ellos.

Para que este paso sea imparcial, tenemos que normalizar o estandarizar los datos primero antes de aplicar el algoritmo. Si no lo hacemos, los atributos con una distribución más amplia tendrán más peso en la clasificación y es posible que tengamos incluso más problemas con valores atípicos o puntos de datos extremos de lo que normalmente tendríamos.

Después de ordenar todos los puntos de datos en grupos, volvemos a calcular los centroides para cada grupo. Hacemos esto calculando el valor promedio de todas las variables y llamamos al resultado de esa operación el nuevo centroide. Después de crear el nuevo centroide, repetimos el proceso de surtido descrito anteriormente.

Es importante tener en cuenta que para calcular un valor medio tenemos que tratar con datos cuantitativos. Si tenemos datos cualitativos (nominales u ordinales), tenemos que usar una variación diferente del algoritmo (K-Medoid, K-Median, etc.) o una combinación de diferentes métodos según el tipo de atributo.

Además, si tenemos un objetivo específico en mente y dependiendo de la medida de distancia utilizada en el algoritmo, el método para elegir los nuevos centroides puede diseñarse específicamente para nuestro caso de uso y aún puede llamarse K-Means, aunque tales casos son extraño.

En el caso más básico, nuestro criterio de detención sería que el grupo asignado de cada observación no cambie de una iteración a la siguiente. A veces, podemos detenernos antes si el número de observaciones cuyos grupos cambiaron es lo suficientemente pequeño o si la diferencia en SSE (suma de errores cuadrados) es menor que un cierto umbral.

Por lo general, medimos la calidad de nuestro agrupamiento creando una función objetivo. Para K-Means, esta función objetivo a menudo se menciona como SSE (suma de errores cuadrados). Como su nombre implica, SSE es una suma de distancias de cada observación desde su centroide más cercano. Por lo tanto, nuestro objetivo al agrupar es minimizar SSE:

$$
SSE = \sum\limits_{i=1}^K \sum\limits_{j=1}^{\text{cluster size}} d((centroide)_i, (instancia)_j)^2
$$

Selección de centroides iniciales

La forma más fácil de elegir los centroides iniciales es simplemente elegir un número K y elegir K puntos aleatorios. Sin embargo, K-Means es extremadamente sensible a la selección inicial de los centroides y, en ocasiones, generará resultados completamente diferentes dependiendo de ello. Para encontrar un arreglo más óptimo, necesitamos resolver dos problemas:

  1. Cómo elegir K
  2. Cómo elegir los centroides iniciales K

Hay varias formas de determinar el número K:

  • Agrupación de medias X: intento de subdivisión y mantenimiento de las mejores divisiones de acuerdo con SSE hasta que se alcance un criterio de parada, como el Criterio de información de Akaike (AIC) o el Criterio de información bayesiano (BIC)
  • El método de la silueta: el coeficiente de silueta mide qué tan similar es cada elemento a su propio grupo (cohesión) en comparación con qué tan similar es a otros grupos (separación), maximizando este coeficiente usando un algoritmo genético en él nos puede dar un buen número para K

El enfoque que destacaremos en detalle, porque se usa comúnmente en la práctica, es el método del codo. Varianza es una expectativa de qué tan lejos se alejará un dato de la media.

Si tomamos la relación de la varianza de los centroides y la varianza de cada punto de datos (sus distancias esperadas de la media de todos los datos), para un buen agrupamiento, obtendremos algo cercano a 1. Sin embargo, si se vuelve demasiado cerca de 1, eso puede significar que estamos sobreajustando los datos, lo que hace que nuestro modelo se desempeñe perfectamente en los datos proporcionados, pero que no refleje la realidad también.

Es por eso que usamos algo llamado Método del codo. Ejecutamos el algoritmo K-Means con diferentes valores de K y los trazamos en un gráfico contra la relación mencionada anteriormente que obtenemos al final para cada uno de ellos. El valor de K que elegimos es aquel donde está el "codo" de la curva, es decir, donde comenzamos a obtener rendimientos decrecientes a medida que aumentamos K:

elbow curve method k-means clustering

Una vez que hayamos decidido K, debemos elegir los centroides de inicio de K. Elegir esto de manera óptima es un problema NP-difícil, por lo que se desarrolló un algoritmo para aproximar una buena solución. Veamos algunas animaciones de lo que podría pasar si las elegimos mal:

picking centroids k-means scenario 1

picking centroids k-means scenario 2

picking centroids k-means scenario 3

Uno de los algoritmos que resuelve aproximadamente este problema se llama K-Means++. Consta de los siguientes pasos:

  1. Elija un centroide al azar de los puntos de datos en el conjunto de datos, con probabilidad uniforme (todos los puntos tienen la misma probabilidad de ser elegidos).
  2. Para cada punto de datos x que aún no se haya elegido, calcule la distancia D(x) desde su centroide más cercano.
  3. Elija un nuevo punto de datos y al azar como un nuevo centroide, utilizando probabilidad ponderada donde y se elige con la probabilidad de la distancia al cuadrado.(D(y)*D(y)). En otras palabras, cuanto más lejos esté y de su centroide más cercano, mayor será la probabilidad de que sea elegido.
  4. Repita los pasos 2 y 3 hasta que se hayan elegido los centroides K.
  5. Ejecute K-Means estándar con los centroides inicializados.

Complejidad de tiempo y espacio {#complejidad de tiempo y espacio}

El tiempo requerido para K-Means es O(I·K·m·n), donde:

  • I es el número de iteraciones requeridas para la convergencia
  • K es el número de grupos que estamos formando
  • m es el número de atributos
  • **N es el numero de observaciones

Esto tiene sentido, porque para cada iteración O(I), tenemos que pasar por todas las observaciones O(n) y calcular su distancia O(m) desde cada centroide O (K).

La complejidad del espacio es O(m·(n+K)) porque estamos guardando n puntos de nuestro conjunto de datos más los K puntos para los centroides, cada punto con m atributos.

Implementación de K-Means en Java

Debido a su falta de soporte común para conjuntos de datos y minería de datos, no es sencillo implementar K-Means en Core Java. Puede encontrar el código de trabajo completo aquí, pero proporcionaremos una breve documentación de la clase auxiliar, DataSet, y la implementación del algoritmo en sí:

  • Conjunto de datos de clase
    • Class Record - a nested class, contains HashMap<String, Double> which stores one row of a table with the key corresponding to the attribute name and value corresponding to its, well, value.
    • Fields:
      • attrNames - list of attribute names
      • records - a list of Records
      • minimums and maximums - minimums and maximums for each attribute to be used to generate a random value between them.
      • indicesOfCentroids - a list of cluster centroids.
    • DataSet(String csvFileName) throws IOException - constructor, reads the data from the provided .csv file and initializes class fields with it.
    • HashMap<String, Double> calculateCentroid(int clusterNo) - recomputes a centroid for a given cluster.
    • LinkedList<HashMap<String,Double>> recomputeCentroids(int K) - recomputes all K centroids.
    • HashMap<String, Double> randomFromDataSet() - returns a random data point out of all of the available data points from the dataset (we need it to initiate the first centroid).
    • public HashMap<String,Double> calculateWeighedCentroid() - calculates the distance of all points from currently chosen centroids and weighs them all according to that distance, so the one furthest away is the most likely to be picked, and then picks one of them using selección de ruleta...)
    • static Double euclideanDistance(HashMap<String, Double> a, HashMap<String, Double> b) - calculates the distance between two data points.
    • Double calculateTotalSSE(LinkedList<HashMap<String,Double>> centroids) - calculates SSE of all clusters.

La clase tiene algunos métodos auxiliares más, pero esto debería ser suficiente para ayudarnos a comprender el algoritmo principal.

Ahora, avancemos e implementemos K-Means, usando esta clase como ayudante:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class KMeans {

    // Higher precision means earlier termination
    // and higher error
    static final Double PRECISION = 0.0;

    /* K-Means++ implementation, initializes K centroids from data */
    static LinkedList<HashMap<String, Double>> kmeanspp(DataSet data, int K) {
        LinkedList<HashMap<String,Double>> centroids = new LinkedList<>();

        centroids.add(data.randomFromDataSet());

        for(int i=1; i<K; i++){
            centroids.add(data.calculateWeighedCentroid());
        }

        return centroids;
    }

    /* K-Means itself, it takes a dataset and a number K and adds class numbers
    * to records in the dataset */
    static void kmeans(DataSet data, int K){
        // Select K initial centroids
        LinkedList<HashMap<String,Double>> centroids = kmeanspp(data, K);

        // Initialize Sum of Squared Errors to max, we'll lower it at each iteration
        Double SSE = Double.MAX_VALUE;

        while (true) {

            // Assign observations to centroids
            var records = data.getRecords();

            // For each record
            for(var record : records){
                Double minDist = Double.MAX_VALUE;
                // Find the centroid at a minimum distance from it and add the record to its cluster
                for(int i = 0; i < centroids.size(); i++){
                    Double dist = DataSet.euclideanDistance(centroids.get(i), record.getRecord());
                    if(dist < minDist){
                        minDist = dist;
                        record.setClusterNo(i);
                    }
                }
            }

            // Recompute centroids according to new cluster assignments
            centroids = data.recomputeCentroids(K);

            // Exit condition, SSE changed less than PRECISION parameter
            Double newSSE = data.calculateTotalSSE(centroids);
            if(SSE-newSSE <= PRECISION){
                break;
            }
            SSE = newSSE;
        }
    }

    public static void main(String[] args) {
        try {
            // Read data
            DataSet data = new DataSet("files/sample.csv");

            // Remove prior classification attr if it exists (input any irrelevant attributes)
            data.removeAttr("Class");

            // Cluster
            kmeans(data, 2);

            // Output into a csv
            data.createCsvOutput("files/sampleClustered.csv");

        } catch (IOException e){
            e.printStackTrace();
        }
    }
}

El archivo sample.csv contiene:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
A,B
1,3
2,4
1,2
3,4
1,2
2,2
2,1
10,12
14,11
12,14
16,13
1,1
4,4
10,11
15,13
13,12
4,1
4,3
4,5

La ejecución de este código da como resultado un nuevo archivo, sampleClustered.csv, que contiene:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
A,B,ClusterId
1.0,3.0,1
2.0,4.0,1
1.0,2.0,1
3.0,4.0,1
1.0,2.0,1
2.0,2.0,1
2.0,1.0,1
10.0,12.0,0
14.0,11.0,0
12.0,14.0,0
16.0,13.0,0
1.0,1.0,1
4.0,4.0,1
10.0,11.0,0
15.0,13.0,0
13.0,12.0,0
4.0,1.0,1
4.0,3.0,1
4.0,5.0,1

Tenemos dos grupos, 0 y 1 aquí. Y dependiendo de las características de cada uno de estos, el algoritmo los ha agrupado en uno de estos.

Posibles problemas con K-Means

K-Means tiene tanto problemas comunes estereotípicos para los algoritmos de agrupamiento como problemas específicos solo de K-Means. Repasemos algunos de los más comunes y cómo manejarlos.

Manejo de clústeres vacíos

Un problema con el que podemos encontrarnos es que a un grupo no se le asigna ninguna observación. Si esto sucede, necesitamos alguna forma de elegir el siguiente centroide para ese grupo, pero no tenemos observaciones para promediar. Existen múltiples enfoques para este problema.

  1. Podríamos simplemente elegir uno de los puntos, por ejemplo, la observación que está más alejada de cualquiera de los otros centroides. Este método es muy sensible a los valores atípicos y solo se recomienda si no hay ninguno.

  2. Alternativamente, podríamos encontrar el grupo con el SSE más grande y elegir un centroide de él. Hacer esto dividiría efectivamente ese grupo y reduciría el SSE general más que elegir un punto aleatorio.

valores atípicos

Los valores atípicos son un problema para K-Means porque atraen significativamente cualquier centroide al que se les atribuya, teniendo un peso indebido en el cálculo.

Pueden causar complicaciones adicionales con SSE, ya que pueden forzar agrupaciones subóptimas solo para que el centroide esté más cerca de los valores atípicos. Por lo general, se recomienda eliminar los valores atípicos antes de usar K-Means para evitar este problema.

Sin embargo, es importante tener en cuenta que, dependiendo de la aplicación para la que esté utilizando el algoritmo, mantener los valores atípicos puede ser fundamental. Por ejemplo, en la compresión de datos tiene que agrupar todos los puntos, incluidos los valores atípicos. En general, podríamos estar interesados ​​en valores atípicos para algunos propósitos (clientes muy rentables, individuos excepcionalmente saludables, [relaciones entre el tamaño del ala y la velocidad de apareamiento en Drosophila malerkotliana] (https://www.tandfonline.com/doi/ pdf/10.1080/11250009209386695)...).

Entonces, si bien la regla general definitivamente debería ser eliminar los valores atípicos, asegúrese de considerar el propósito de su agrupación y el conjunto de datos en el que está trabajando antes de tomar una decisión.

Mínimos locales y reducción de SSE con posprocesamiento {#mínimos locales y reducción de SSE con posprocesamiento}

Como suele ser el caso con estos algoritmos, K-Means no garantiza la optimización. Podría terminar en un mínimo local, el resultado que podría mejorarse con algunos ajustes.

Podemos reducir el SSE total dividiendo inteligentemente los grupos existentes o agregando un nuevo centroide. Si estamos dividiendo un clúster, es bueno elegir el que tenga el mayor SSE, que a menudo será también el que tenga el mayor número de puntos. Si agregamos un nuevo centroide, a menudo es bueno elegir el punto que está más alejado de todos los centroides existentes.

Si queremos disminuir el número de clústeres después (por ejemplo, para mantener exactamente “K” clústeres como resultado), también podemos usar dos técnicas diferentes. Podemos:

  1. Combinar dos clústeres (generalmente los más pequeños o los que tienen el SSE más bajo)
  2. Disperse un clúster eliminando su centroide y reasignando sus miembros a otros clústeres.

Búsqueda de clústeres inexistentes

K-Means encontrará K clústeres sin importar los datos subyacentes. Si hay 3 clústeres y ha establecido K en 5, encontrará 5 clústeres. Si no hay clústeres en absoluto, seguirá encontrando 5 clústeres:

uniform colormapped cluster

No hay forma de evitar esto en K-Means. En cambio, primero se debe verificar la estadistica de hopkin para ver si hay algún grupo en los datos mismos. La estadística de Hopkin funciona comparando el conjunto de datos con un conjunto uniforme de puntos generado aleatoriamente.

Digamos que tenemos nuestro conjunto de datos, X, y tiene n puntos de datos. Tomamos muestras de m de ellos para su análisis.

Luego generamos aleatoriamente otro conjunto de datos, Y, que sigue una distribución uniforme. Y también tiene m puntos de datos.

La distancia entre algún miembro de X y su vecino más cercano, la llamaremos w.

La distancia entre algún miembro de Y y su vecino más cercano en X, la llamaremos u.

La estadística de Hopkins resulta entonces como:

$$
H = \frac{\suma\límites_{i=1}^m u_i}{\suma\límites_{i=1}^m u_i +\suma\límites\ _{i=1}^m w_i}
$$

Si es probable que nuestro conjunto de datos sea aleatorio, la fórmula dará un número cercano a .5, mientras que para conjuntos de datos no aleatorios se acercará a 1.

Esto se debe a que las distancias dentro del conjunto y dentro del conjunto aleatorio serán aproximadamente iguales si nuestro conjunto también es aleatorio, por lo que obtendremos la mitad.

Si no es aleatorio, las distancias dentro del conjunto serán significativamente más pequeñas y contribuirán de manera insignificante al denominador, acercando el resultado a 1.

Tipos de clústeres subyacentes que puede reconocer

K-Means es muy bueno para reconocer cúmulos globulares de densidad constante y tamaño similar.

Esto significa que el grupo tendrá la forma de un círculo, una esfera o una hiperesfera, según la dimensión en la que esté trabajando. Esto es lógico, porque se basa en la distancia desde el centro para determinar si algo pertenece a un grupo. , por lo que sus bordes son más o menos equidistantes del centro, naturalmente, lo hace esférico:

tipos de clusters que k-means puede reconocer

Esto, sin embargo, significa que es terrible para reconocer grupos de diferentes formas. Realmente no se puede modificar para solucionar este problema porque es el núcleo del algoritmo, por lo que la única recomendación que podemos dar aquí es hacer todo lo posible para visualizar sus datos de antemano y ver las formas que desea agrupar. .

Si no puede hacer eso de manera efectiva, otra indicación de que esto puede ser un problema es un alto SEE al probar su agrupación de K-Means.

Si ese es el caso y no puede solucionarlo eliminando los valores atípicos o tomando medidas similares, considere usar un método de agrupación en clústeres diferente que se adapte mejor a las diferentes formas de clústeres (es decir, DBSCAN) y vea si sus resultados mejoran :

comparing k-means with dbscan

El segundo tipo muy obvio de conjunto de datos con el que K-Means tendrá problemas es un conjunto de datos lleno de grupos con tamaños inconsistentes. Si tiene un cúmulo grande y ancho y justo al lado un cúmulo pequeño, el cúmulo pequeño a menudo será absorbido por completo por el grande.

Esto se debe a que no tiene un impacto negativo severo en su SSE porque solo aumenta ligeramente su diámetro. Si de alguna manera terminamos con dos centroides en estos dos grupos, el grupo grande probablemente se dividiría en dos en lugar de detectar los grupos existentes reales.

Esto se debe nuevamente a que el SSE de un cúmulo grande y uno pequeño será mayor que el SSE de un cúmulo grande reducido a la mitad. De nuevo, como en las secciones anteriores, recomendamos la visualización y/o comparación de resultados con diferentes métodos (es decir, agrupación jerárquica) para determinar si esto causa problemas.

Y el tercer problema mencionado son los grupos de densidades variables. Los puntos densos van a tener un efecto mayor en el promedio que aquellos que no están tan densamente agrupados y estarán más cerca de su centroide que aquellos que no están tan densamente agrupados. Los cúmulos menos densos tendrán un SSE más grande y se dividirán y consumirán en los cúmulos densos circundantes.

Aquí hay una ilustración del problema de los grupos con diferentes tamaños y densidades:

comparando clusters de diferentes tamaños k-means

Variaciones de K-Means

Hay variaciones de este algoritmo que difieren principalmente en cómo se elige el centroide. Aquí hay una lista de algunos de ellos:

  • K-Modes: el centroide es el elemento creado al seleccionar la ocurrencia más frecuente en el grupo para cada atributo.
  • K-Medoids: similar a una media, pero se limita a ser un miembro real del conjunto de datos, en lugar de solo un valor posible.
  • K-Median: en lugar de la media, usamos la mediana o el "elemento medio" para cada atributo para crear nuestro centroide.
  • Expectativa: agrupamiento de maximización (EM) mediante modelos de mezcla gaussiana (GMM): detecta formas elípticas mediante el uso de tanto una media como una desviación estándar para definir la pertenencia a un clúster.

Conclusión

Proporcionamos una intuición detrás de K-Means al trazar paralelos con la experiencia humana, analizamos los detalles de cómo se puede implementar, varias preocupaciones que debemos tener en cuenta al implementarlo y los problemas comunes que encontramos al trabajar con él. También hemos mencionado algoritmos similares, así como algoritmos de agrupamiento alternativos para situaciones en las que K-Means se queda corto.