miniatura|250px|Cada cuadrado corresponde a un elemento, sus coordenadas representan sus características, los colores son el resultado del agrupamiento, que en este caso identificó 3 grupos. Análisis de grupos o agrupamiento es la tarea de agrupar objetos por similitud, en grupos o conjuntos de manera que los miembros del mismo grupo tengan características similares. Es la tarea principal de la minería de datos exploratoria y es una técnica común en el análisis de datos estadísticos.
Además es utilizada en múltiples campos comoː
aprendizaje automático reconocimiento de patrones análisis de imágenes búsqueda y recuperación de información bioinformática compresión de datos computación gráfica.
El análisis de grupos es un problema, es un planteamiento general, y existen miles de algoritmos que lo resuelven, cada uno con sus propias características. Muchos algoritmos difieren significativamente en su idea de qué constituye un grupo y cómo encontrarlos eficientemente.
El agrupamiento, por tanto, puede ser formulado como un problema multi-objetivo de optimización. El algoritmo apropiado y sus parámetros dependen del conjunto de datos que se analiza y el uso que se le dará a los resultados.
El agrupamiento como tal no es una tarea con solución directa, sino un proceso iterativo o interactivo que implica ensayo y error. Este proceso de prueba y error es iterativo en la medida que sea automático, e interactivo en la medida que requiera intervención humana. Es una práctica usual ejecutar un algoritmo de agrupamiento (un proceso iterativo), y a partir de los resultados ajustar los parámetros y repetir la operación (resultando en un proceso interactivo).
Las aplicaciones del agrupamiento se dividen en dos tipos principalesː
aquellas en la que los grupos constituyen el resultado buscado es el caso de análisis de grupos, minería de datos, análisis de imágenes otras en las que los grupos constituyen el punto de partida para la clasificaciones de nuevas muestras de datos, desconocidas al momento de procesar el agrupamiento es el caso de clasificación automática en el mundo del aprendizaje de máquina
Otras denominaciones Además del término agrupamiento, hay un número de términos con significados similares, incluyendoː
análisis de grupos clasificación automática clustering (agrupamiento, en inglés) taxonomía numérica botryología (del griego βότρυς "uva") análisis tipológico tipología aglutinado análisis Q
Historia El análisis de grupo estuvo originado en antropología por Driver y Kroeber en 1932 e introducido a psicología por Zubin en 1938 y Robert Tryon en 1939,Bailey, Ken (1994). Tryon, Robert C. (1939). que también fue utilizado por Cattell al principio de 1943Cattell, R. B. (1943). para clasificación de la personalidad psicológica basada en teoría de rasgos. El primer uso del término moderno data clustering (agrupamiento de datos) se remonta a 1954,
El algoritmo de agrupamiento K-means fue publicado en 1955, y generalmente se lo considera el primer algoritmo de agrupamiento. Si bien hay dudas sobre la existencia previa de otros algoritmos de agrupamiento, K-means es el más antiguo entre los que se utilizan en la actualidad y el más influyente. Curiosamente, durante más de diez años, K-means fue redescubierto en diversas disciplinas científicas. Hasta 1967 se registran cuatro publicaciones en disciplinas diferentes que proponen como novedoso el mismo algoritmo de agrupamiento. El hecho de que varios científicos no relacionados desarrollen el mismo algoritmo da a entender la existencia de un denominador común, posiblemente el auge de la computación.
Desde 1963 hasta 2001 se han publicado 5 libros sobre agrupamiento considerados clásicos de su época. Aun así el interés por los algoritmos de agrupamiento se disparó en la primera década de este siglo, con un pico de búsquedas en Google Scholar en 2009.A History of Cluster Analysis Using the Classification Society's Bibliography Over Four Decades, 2013, arXiv:1209.0125v2 En esa década se desarrollaron miles de algoritmos nuevos, de creciente especificidad y complejidad, predominantemente para los ámbitos de minería de datos y de aprendizaje de máquina.
Definiciones
Grupo La idea de un grupo de datos similares resulta incompleta y subjetiva, por el sencillo hecho de que la definición de similitud es parte del problema específico que se requiere resolver y no es parte del problema general de agrupamiento. Éste es el principal motivo de que existan miles de algoritmos de agrupamiento.
Aun así, los investigadores emplean diferentes modelos de grupo, y para cada uno de estos modelos se utilizan diferentes algoritmos. La idea de un grupo, cuando es encontrado por algoritmos diferentes, varía significativamente en sus propiedades. Entender estos "modelos de grupo" es clave para entender las diferencias entre los algoritmos.
Típicamente los modelos de grupo incluyen estos otros modelos de: Conectividad: por ejemplo, agrupamiento jerárquico construye modelos basados en la distancia de las conexiones Centroide: por ejemplo, el algoritmo k-means representa cada grupo por un solo vector medio Distribución: los grupos son modelados utilizando distribuciones estadísticas, como la distribución normal multivariada utilizada por el algoritmo Expectation-maximization Densidad: por ejemplo, DBSCAN y OPTICS definen grupos como regiones densas conectadas en el espacio de los datos Subespacios: en Bi-agrupamiento (también conocido como Co-clustering o two-mode-clustering), los grupos son modelados con ambas características, miembros del grupo y atributos relevantes Grupo: algunos algoritmos no proporcionan un modelo refinado para sus resultados y solo proporcionan la información de la agrupación Grafos: un clique, i.e., un subconjunto de nodos en un grafo tal que cada dos nodos en el subconjunto están conectados por una arista puede ser considerado como un prototipo o forma de grupo. Relajaciones del requisito de completa conectividad (una fracción de las aristas puede faltar) es conocida como quasi-cliques, como en el algoritmo HCS
Agrupamiento Un agrupamiento es esencialmente un conjunto de tales grupos, normalmente conteniendo todos los objetos en el conjunto de datos. Además, puede especificar la relación de los grupos a cada uno de los otros, por ejemplo, una jerarquía de grupos contenida en cada otro. Los agrupamientos pueden ser aproximadamente clasificados como: Duro: cada objeto pertenece a un grupo o no Suave o difuso: cada objeto pertenece a cada grupo según un grado de pertenencia (p. ej. la probabilidad de pertenecer al grupo) Hay también otras distinciones posibles de agrupamientos: con partición estricta: aquí cada objeto pertenece a exactamente un grupo con partición estricta con ruido: los objetos también pueden no pertenecer a ningún grupo, y están considerados ruido o anomalías con solapamiento (También: agrupamiento alternativo, agrupamiento multi-objetivo): contrario a agrupamiento duro, los objetos pueden pertenecer a más de un grupo jerárquico: objetos que pertenecen a un grupo hijo también pertenecen al grupo padre de subespacios: contrario a agrupamiento con solapamiento, dentro de un único sub-espacio definido, los grupos deben solaparse
Algoritmos Los algoritmos de agrupamiento pueden ser categorizados de varias maneras, por ejemplo por suː
modelo de grupo eficiencia computacional o velocidad de cómputo eficacia en el problema específico
En adelante se listan solamente los algoritmos más prominentes, ya que existen más de 100 publicados. No todos proporcionan modelos para sus grupos y por esto pueden no ser fácil categorizarlos. No existe un algoritmo de agrupamiento "correcto", como se pudo haber notado, "el agrupamiento está en el ojo del observador". El algoritmo más apropiado para un problema particular a menudo necesita ser escogido experimentalmente, a no ser que haya una razón matemática para preferir un modelo de grupo sobre otro. Se debería tener en cuenta que un algoritmo que está diseñado para determinado modelo no tiene ninguna posibilidad de obtener buenos resultados en un conjunto de datos con un modelo diferente. Por ejemplo, k-means no puede encontrar grupos no convexos. Agrupamiento basado en conectividad (agrupamiento jerárquico) El agrupamiento basado en conectividad, también conocido como agrupamiento jerárquico, está basado en la idea principal de que los objetos más cercanos están más relacionados que los que están alejados. Estos algoritmos conectan "objetos" para formar "los grupos" basados en su distancia. Un grupo puede ser descrito, en gran parte, por la distancia máxima que se necesitó para conectar todas las partes del grupo. A distancias diferentes, se formarán grupos diferentes, los cuales pueden ser representados utilizando un dendrograma, el cual explica de donde proviene el nombre "agrupamiento jerárquico": estos algoritmos no solo proporcionan una partición del conjunto de datos, sino en cambio, proporcionan una jerarquía extensa de grupos que se fusionan con cada otro a ciertas distancias. En un dendrograma, el eje "y" marca la distancia en qué los grupos se fusionan, mientras que los objetos están colocados a lo largo del eje "x", tal que los grupos se mezclan.
El agrupamiento basado en conectividad es una familia entera de métodos que difiere en cómo las distancias están computadas. Aparte de la elección habitual de funciones de distancia, el usuario también necesita decidir el criterio de conexión (como un grupo consta de objetos múltiples, hay candidatos múltiples para computar la distancia) para utilizar. Las elecciones populares son conocidas como agrupamiento por enlace simple (el mínimo de distancias entre objetos), agrupamiento por enlace completo (el máximo de distancias entre objetos) o UPGMA ("Unweighted Pair Group Method with Arithmetic Mean", también conocido como agrupamiento por enlace medio). Además, agrupamiento jerárquico puede ser aglomerativo (empezando con simples elementos y agregándoles a grupos) o divisivos (empezando con el conjunto de datos completo y dividiéndolo en particiones). Estos métodos no producirán una única partición del conjunto de datos, sino una jerarquía donde el usuario puede escoger los grupos apropiados. No son muy robustos con el ruido, ya que puede que no aparezcan como grupos adicionales; pueden incluso causar que otros grupos se fusionen (conocido como "fenómeno de cadena", en particular con agrupamiento por enlace simple). En el caso general, la complejidad es para agrupamiento aglomerativo y para divisivo, el cual les hace demasiado lentos para conjuntos de datos grande. Para algunos casos especiales, métodos óptimos más eficientes son conocidos (de complejidad : SLINK para enlace simple y CLINK para agrupamiento por enlace completo. En la comunidad de minería de datos estos métodos están reconocidos como fundación teórica del análisis de grupos, pero a menudo considerados obsoletos. Aun así proporcionaron inspiración para muchos de los métodos más actuales como agrupamiento basado en densidad.
Agrupamiento basado en centroide