Algoritmo de agrupamiento, k-medias: implementación paso a paso

Algoritmo de agrupamiento, k-medias: implementación paso a paso

Juan David Casseres Rodriguez

Universidad Tecnológica de Bolívar

Cartagena, Bolívar

juandavidcr7@gmail.com

Resumen – Para el agrupamiento basado en el algoritmo K-medias, tenemos un conjunto de N puntos de datos en el espacio d-dimensional Rd [1] y un número K de puntos de datos en el mismo espacio d-dimensional Rd, que llamaremos centroides. El objetivo es encontrar grupos en los datos y determinar un conjunto de K puntos en el cual la distancia media cuadrada entre cada punto de datos y su centroide sea mínima. El presente artículo muestra la implementación del algoritmo de agrupamiento k-medias y se expondrá un método para hallar ese conjunto de K puntos óptimos.

Palabras claves: Aprendizaje automatico, aprendizaje no supervisado, k-medias, centroides, conglomerados.

Abstract - For clustering based on the K-means algorithm, we have a set of N data points in the d-dimensional space Rd and a number K of data points in the same d-dimensional space Rd, it will be called Centroids. The goal is to find groups in the data and determine a set of K points in which the mean square distance between each data point and its centroid is minimal. The present article shows the implementation of the k-means clustering algorithm and a method to find the optimal set of K points.

Keywords: Machine learning, unsupervised learning, k-means, centroids, clustering

1. INTRODUCCIÓN

El aprendizaje automático son el conjunto de técnicas y algoritmos que nos permiten convertir los datos en información, aunque esta no sea mostrada de forma evidente en los datos. Estos diferentes algoritmos en función de la salida de estos mismos o en la tarea que deban resolver.

Hasta ahora la tarea era predecir el valor de una variable de salida Y. Esta salida podía ser continua(regresión) o podía ser discreta(clasificación), para un conjunto de datos, que servían como variables predictores. Este problema es catalogado como aprendizaje supervisado, ya que, a partir de una muestra de datos etiquetados con su respectiva salida, era posible construir una función que permitiera predecir el valor de Y para una nueva entrada de datos.

Ahora, existe el caso cuando solo tenemos los datos de nuestras variables predictoras, es decir no hay etiquetas que identifiquen las observaciones o entradas. Este es catalogado como aprendizaje no supervisado. En este caso la tarea consiste en analizar las observaciones que se tienen para ver si estas pueden ser agrupadas en clústeres “homogéneos”. Donde todas las observaciones que hagan parte de uno de estos grupos sean similares entre si, y diferentes de algún modo en las pertenecientes a los otros grupos.

Esta técnica de agrupamiento o clustering tienen muchas aplicaciones hoy en día y veremos cómo aplicar un algoritmo que nos ayude a resolver esta tarea, de acuerdo a un conjunto de datos proporcionado.

1. MARCO TEORICO

A. Minería de Datos

Surge como una tecnología emergente que sirve de soporte para el descubrimiento de conocimiento, que se revela a partir de patrones observables en datos estructurados o asociaciones que usualmente eran desconocidas [2].

B. Tipos de técnicas de Minería de Datos

No supervisadas: Los datos no están clasificados o etiquetados

Supervisadas: Los modelos predictivos requieren ser “entrenados”, utilizando un conjunto de datos donde conocemos el valor de salida de cada dato.

C. Clustering

El análisis de Clustering, es una técnica que permite analizar datos que no se encuentran etiquetados, formando grupos a partir de la similitud que estos tengan, el número de grupos es dos o más.

La similitud puede medirse a través de funciones de distancia, estas nos aseguraran que los individuos cercanos vayan para el mismo grupo.

D. Medidas de similitud

Las medidas de similitud establecen la forma en que se determina la proximidad que hay entre los datos. La distancia euclidiana es la más utilizada en la práctica.

[pic 1]

E. Algoritmo K-medias

El algoritmo de agrupación en K-medias es un tipo de aprendizaje no supervisado, que se utiliza cuando se tiene datos no etiquetados (es decir, datos sin categorías o valores de salida). El objetivo de este algoritmo es encontrar grupos en los datos, con el número de grupos representados por la variable K. El algoritmo funciona iterativamente para asignar cada punto de datos a uno de los grupos K en función de las características que se proporcionan. Los puntos de datos se agrupan según la similitud de sus características. Los resultados del algoritmo de agrupamiento K-medias son:

• Los centroides de los clústeres K, que se pueden usar para etiquetar nuevos datos
• Etiquetas para los datos (cada punto de datos se asigna a un solo grupo)

El algoritmo de agrupación de Κ-medias funciona de manera iterativa refinando el resultado a cada iteración.

Entradas: número de clústeres Κ y el conjunto de datos.

    El algoritmo comienza con una estimación inicial del valor de K centroides, que pueden ser generados aleatoriamente o seleccionados aleatoriamente a partir del conjunto de datos.

El algoritmo luego itera entre dos pasos:

1.Asignación de clúster.

    En este paso, cada punto de datos se asigna a su centroide más cercano, en función de la distancia euclidiana.

...