Análisis de grupos

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
El resultado de un análisis de grupo, mostrado como la coloración de cuadrados en tres grupos.

Análisis de grupos o agrupamiento es la tarea de agrupar un conjunto de objetos de tal manera que los miembros del mismo grupo (llamado clúster) sean más similares, en algún sentido u otro. 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 el aprendizaje automático, el reconocimiento de patrones, el análisis de imágenes, la búsqueda y recuperación de información, la bioinformática, la compresión de datos y la computación gráfica.

El análisis de grupos no es en sí un algoritmo específico, sino la tarea pendiente de solución. Se puede hacer el agrupamiento utilizando varios algoritmos que difieren significativamente en su idea de qué constituye un grupo y cómo encontrarlos eficientemente. Las ideas clásicas de grupo incluyen distancias pequeñas entre los miembros del mismo, áreas densas del espacio de datos, intervalos o distribuciones estadísticas particulares. El agrupamiento, por tanto, puede ser formulado como un problema multi-objetivo de optimización. El algoritmo apropiado y los valores de los parámetros (incluyendo valores como la función de distancia para utilizar, un umbral de densidad o el número de grupos esperado) depende del conjunto de datos que se analiza y el uso que se le dará a los resultados. Agrupamiento como tal no es una tarea automática, sino un proceso iterativo de minería de datos o interactivo de optimización multi-objetivo que implica prueba y fracaso. A menudo será necesario hacer un pre-procesamiento de los datos y un ajuste de los parámetros del modelo hasta que el resultado tenga las propiedades deseadas.

Además del término agrupamiento, hay un número de términos con significados similares, incluyendo clasificación automática, taxonomía numérica, botryology (del griego βότρυς "uva") y análisis tipológico. Las diferencias sutiles son a menudo en el uso de los resultados: mientras que en minería de datos, los grupos resultantes son el objeto de interés, en clasificación automática el objetivo es el poder de diferenciación entre grupos. Esto a menudo condujo a malentendidos entre los investigadores que provienen de campos de minería de datos y aprendizaje de máquina, desde entonces utilizan los mismos términos y con frecuencia los mismos algoritmos, pero tienen objetivos diferentes.

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,[1][2]​ que también fue utilizado por Cattell al principio de 1943[3]​ para clasificación de la personalidad psicológica basada en teoría de rasgos.

Definición[editar]

La idea de un clúster o grupo resulta compleja para concretar su definición exacta, en consecuencia existen tantos algoritmos de agrupamiento.[4]​ Hay un común denominador: un grupo de datos. 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: • Modelos de conectividad: por ejemplo, agrupamiento jerárquico construye modelos basados en la distancia de las conexiones.
• Modelos de centroide: por ejemplo, el algoritmo k-means representa cada grupo por un solo vector medio.
• Modelos de distribución: los grupos son modelados utilizando distribuciones estadísticas, como la distribución normal multivariada utilizada por el algoritmo Expectation-maximization.

•  Modelos de densidad: por ejemplo, DBSCAN y OPTICS definen grupos como regiones densas conectadas en el espacio de los datos.


• Modelos de sub-espacios: 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.
• Modelos de grupo: algunos algoritmos no proporcionan un modelo refinado para sus resultados y solo proporcionan la información de la agrupación.
• Modelos basados en grafo: 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. 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: • Agrupamiento Duro: cada objeto pertenece a un grupo o no

•  Agrupamiento Suave (también: Agrupamiento 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, por ejemplo: • Agrupamiento con partición estricta: aquí cada objeto pertenece a exactamente un grupo

•  Agrupamiento 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.
• Agrupamiento con solapamiento (También: agrupamiento alternativo, agrupamiento multi-objetivo): contrario a agrupamiento duro, los objetos pueden pertenecer a más de un grupo.


• Agrupamiento jerárquico: objetos que pertenecen a un grupo hijo también pertenecen al grupo padre.

•  Agrupamiento de subespacios: contrario a agrupamiento con solapamiento, dentro de un único sub-espacio definido, los grupos deben solaparse.

Algoritmos[editar]

Los algoritmos de agrupamiento pueden ser categorizados atendiendo a su modelo de grupo, como se dijo antes. Solo se listará en lo adelante los algoritmos más prominentes, ya que existen más de 100 publicados. No todos proporcionan modelos para sus grupos y pueden así no ser fácilmente categorizados.

No existe un algoritmo de agrupamiento "correcto", como se pudo haber notado, "el agrupamiento esta en el ojo del observador".[4]​ 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 que se obtengan buenos resultados en un conjunto de datos con un modelo diferente.[4]​ Por ejemplo, k-means no puede encontrar grupos no convexos.[4]

Agrupamiento basado en conectividad(agrupamiento jerárquico)[editar]

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 como 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,[5]​ el cual les hace demasiado lento para conjuntos de datos grande. Para algunos casos especiales, métodos óptimos más eficientes son conocidos (de complejidad : SLINK[6]​ para enlace simple y CLINK[7]​ 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[editar]

En agrupamiento basado en centroide, los grupos están representados por un vector central, el cual puede no necesariamente ser un miembro del conjunto de datos. Cuándo el número de grupos está fijado a k, k-means da una definición formal como un problema de optimización: encontrar los k centros de los grupos y asignar los objetos al centro del grupo más cercano, tal que el cuadrado de las distancias del grupo al centro están minimizadas.

Este problema de optimización es NP-duro, y por ello el objetivo común es buscar sólo soluciones aproximadas. Un bien conocido método aproximado es el algoritmo de Lloyd,[8]​ a menudo referido como "k-means". Aun así sólo encuentra un óptimo local, y generalmente se ejecuta varias veces con inicializaciones aleatorias. Variaciones de k-means a menudo incluyen otras optimizaciones como: escoger el mejor resultado de varias corridas, restringir el centroide a miembros del conjunto de datos (k-medoids), escoger medianas (k-medians), escoger los centros iniciales aleatoriamente (K-means++) o permitir una asignación de grupos difusa (Fuzzy c-means).

La mayoría de los tipos de k-means requieren que el número de grupos sea especificado por adelantado, el cual está considerado una de las más grandes dificultades de estos algoritmos. Además, los algoritmos prefieren grupos de aproximadamente media similar, debido a que siempre asignarán un objeto al más cercano centroide. Esto a menudo provoca cortes incorrectos en los bordes de los grupos (lo cual no es una sorpresa ya que el algoritmo optimiza los centroides, no las fronteras).

K-means tiene un número de propiedades teóricas interesantes. Primero, las particiones del espacio de datos son estructuras conocidas como esquemas de Voronói. Segundo, está conceptualmente cerca de la clasificación de k-nearest neighborhood, y por tanto muy popular en aprendizaje de máquina. Tercero, puede ser visto como una variación de la clasificación basada en modelos, y el algoritmo de Lloyd como variación del algoritmo Expectation-maximization para el modelo que se discutirá debajo.

Agrupamiento basado en distribuciones[editar]

El modelo de agrupamiento más estrechamente relacionado a la estadística es el modelo basado en distribuciones. Los grupos pueden entonces fácilmente ser definidos como los objetos que pertenecen más probablemente a la misma distribución. Una propiedad conveniente de esta aproximación es que esto se parece mucho a la manera en la que los conjuntos de datos artificiales están generados: por muestreos aleatorios de objetos de una distribución.

Mientras la fundación teórica de estos métodos es excelente, adolecen del problema clave conocido como sobreajuste u overfitting, a no ser que las restricciones estén incluidas en la complejidad del modelo. Un modelo más complejo normalmente será capaz de explicar los datos mejor, el cual hace escoger la complejidad apropiada del modelo inherentemente difícil.

Uno de los métodos más prominentes es conocido como modelo de mezcla Gaussiana (utilizado en el algoritmo de expectation-maximization). Aquí, el conjunto de datos es normalmente modelado con un número fijo (para evitar el sobreajuste) de distribuciones Gaussianas que está inicializado aleatoriamente, y cuyos parámetros son iterativamente optimizados para clasificar mejor al conjunto de datos. Esto convergerá a un óptimo local, múltiples corridas pueden producir resultados diferentes. Para obtener un agrupamiento duro, los objetos son a menudo entonces asignados a la distribución Gaussiana con mayor probabilidad de pertenecer ; para agrupamiento suave, esto no es necesario.

Agrupamiento basado en distribuciones produce modelos complejos para grupos que pueden capturar correlación y dependencia entre atributos. Aun así, estos algoritmos ponen una carga extra en el usuario: para muchos conjuntos de datos real, no puede haber ningún modelo matemático definido.

Agrupamiento basado en densidad[editar]

En agrupamiento basado en densidad,[9]​ los grupos están definidos como áreas de densidad más alta que en el resto del conjunto de datos. Objetos en áreas esparcidas son conocidos como ruido o puntos frontera.

El método de agrupamiento[10]​ más popular conocido es DBSCAN.[11]​ En contraste con muchos métodos más nuevos, presenta un modelo de grupo bien definido llamado "densamente alcanzable". Similar a agrupamiento basado en conectividad, está basado en conectar puntos dentro de cierto umbral de distancia. Aun así, sólo conecta aquellos puntos que satisfacen un criterio de densidad, en la variante original definido como número mínimo de otros objetos dentro de un radio dado. Un grupo consiste en objetos densamente conectados (los cuáles pueden formar un grupo de una forma arbitraria, en contraste a muchos otros métodos) más todos los objetos que están dentro del rango de estos. Otra propiedad interesante de DBSCAN es que su complejidad es bastante baja- requiere un número lineal de consultas de rango en la base de datos - y que descubrirá esencialmente los mismos resultados ( es determinista para núcleos y puntos de ruido, pero no para puntos de frontera) en cada corrida, por tanto no hay ninguna necesidad de correrlo varias veces. OPTICS[12]​ es una generalización de DBSCAN que elimina la necesidad de escoger un valor apropiado para el parámetro del rango, y produce un resultado jerárquico relacionado con la conexión del agrupamiento. DeLi-Clu,[13]​ es un algoritmo de agrupamiento basado en densidad que combina ideas de agrupamiento por enlace simple y de OPTICS, eliminando el parámetro del rango enteramente y ofreciendo mejoras de rendimiento sobre OPTICS por utilizar un R-tree como índice.

La principal dificultad de DBSCAN y OPTICS es que esperan alguna clase de caída de densidad para detectar fronteras de grupo. Además, no pueden detectar estructuras intrínsecas de grupo las cuales prevalecen en la mayoría de los conjuntos de datos de la vida real. Una variación de DBSCAN, EnDBSCAN,[14]​eficientemente detecta tales clases de estructuras. En conjuntos de datos con, por ejemplo, solapamiento de distribuciones Gaussianas - un caso de uso común en datos artificial - las fronteras de grupo producidas por estos algoritmos a menudo eran arbitrarias, porque las disminuciones de densidad del grupo eran continuas. En datos que contienen mezclas de Gaussianas, estos algoritmos son casi siempre batidos por métodos como EM debido a que estos son capaces de modelar esta clase de datos.

Mean-shift es una aproximación de agrupamiento donde cada objeto se mueve al área más densa en su proximidad, basado en una estimación de la densidad del núcleo. Finalmente, los objetos convergen a máximos locales de densidad. Similar a k-means, estos "atractores densos" pueden servir como representantes para el conjunto de datos, pero mean-shift puede detectar formas arbitrarias de los grupos similar a como lo hace DBSCAN. Debido al procedimiento iterativo costoso y estimación de densidad, mean-shift es normalmente más lento que DBSCAN o k-Means.

Desarrollos recientes[editar]

En años recientes el esfuerzo considerable ha sido puesto a mejorar el rendimiento de algoritmos existentes.[15][16]​ Entre ellos están CLARANS (Ng y Han, 1994),[17]​ y ABEDUL (Zhang et al., 1996).[18]​ Con la necesidad reciente de procesar datos más grandes y más grandes conjuntos (también conocidos como big data), la disposición para comerciar el significado semántico de los grupos generados ha sido incrementado. Esto dirigió al desarrollo de métodos de pre-agrupamiento como Canopy, los cuales pueden procesar conjuntos de datos enormes eficientemente, pero los grupos "resultantes" son meramente ásperas pre-particiones de los datos para entonces analizar las particiones con métodos existentes más lentos como k-means. Varias aproximaciones de agrupamiento han sido probadas basándose en semillas.[19]

Para alta dimensionalidad de los datos, muchos de los métodos que existen fallan, debido a las problemáticas particulares de las funciones de distancia para espacios de alta dimensionalidad. Esto llevó a la creación de nuevos algoritmos de agrupamiento para alta dimensionalidad que se enfocan en agrupamiento en subespacios (dónde sólo algunos atributos serán utilizados, y los modelos de grupo incluyen los atributos pertinentes para los grupo) y agrupamiento de correlación que también busca sub-espacios de grupos rotados arbitrariamente ("correlacionados") que pueden ser modelados dada una correlación de sus atributos. Ejemplos para tales algoritmos son CLIQUE[20]​ y SUBCLU.[21]

Ideas de métodos de agrupamiento basado en densidad (en particular la familia de algoritmos DBSCAN/OPTIC) han sido adaptadas a agrupamiento de subespacios (HiSC[22]​ y DiSH[23]​) y agrupamiento de correlación (HiCO ,[24]​ 4C[25]​ utilizando "conectividad por correlación" y ERIC[26]​ que explora correlación jerárquica de grupos basada en densidad).

Diferentes sistemas de agrupamiento basados en información mutua han sido propuestos. Uno es usando la distancia entre grupos propuesto por Marina Meilă;[27]​ otros proporcionan agrupamiento jerárquico.[28]​ Utilizando algoritmos genéticos, una gama ancha de diferentes funciones pueden ser optimizadas, incluyendo información mutua.[29]​ También el algoritmo "message passing", un desarrollo reciente en Informática y Física Estadística, se ha dirigido a la creación de tipos nuevos de algoritmos de agrupamiento.[30]

Otros métodos[editar]

  • Esquema algorítmico secuencial básico (BSAS)

Evaluación y valoración[editar]

La evaluación de los resultados de un agrupamiento a veces se refiere a como se validan los grupos.

Ha habido varias sugerencias para una medida de semejanza entre dos agrupamientos. Tal medida puede usarse para comparar que bien los diferentes algoritmos crean un agrupamiento en un conjunto de datos. Esta medida esta normalmente ligada al criterio que es considerado para evaluar la calidad de un método de agrupamiento.

Evaluación interna[editar]

Cuándo el resultado de un agrupamiento es evaluado basado en los datos agrupados por él se llama evaluación interna. Estos métodos normalmente asignan la puntuación mejor al algoritmo que produce grupos con alta similitud entre sus componentes y baja similitud entre los grupos. Un problema de utilizar los criterios internos en evaluación de grupo es que puntuaciones altas en una medida interna no necesariamente indica un buen resultado en recuperación de información.[31]​ Además, esta evaluación está predispuesta hacia algoritmos que usan el mismo modelo de grupo. Por ejemplo, k-means naturalmente optimiza distancias de objeto, y una criterio interno basado en distancia probablemente sobrevalore el resultado del agrupamiento.

Por tanto, las medidas de evaluación internas son más convenidas para conseguir alguna idea en situaciones donde un algoritmo actúa mejor que otro, pero esto no implicará que un algoritmo produce resultados más válidos que otro.[4]​ La validez medida por tal índice depende de la clase de estructura existente en el conjunto de datos. Un algoritmo diseñado para alguna clase de modelos no tiene ninguna posibilidad si el conjunto de dato contiene un conjunto radicalmente diferente de modelos, o si la evaluación mide un criterio radicalmente diferente.[4]​ Por ejemplo, k-means sólo puede encontrar grupos convexos, y muchos índices de evaluación suponen grupos convexos. En un conjunto de datos con grupos no convexos ni el uso de k-means, ni de un criterio de evaluación que supone convexidad, dará buenos resultados.

Los métodos siguientes se suelen usar para evaluar la calidad de los algoritmos basados en criterio interno:

  • Índice de Davies–Bouldin
El índice de Davies–Bouldin puede ser calculado por la fórmula siguiente:
donde n es el número de grupos, es el centroide de grupo x, es la distancia media de todos los elementos en grupo al centroide x, y es la distancia entre centroides y . Desde algoritmos que producen grupos con bajas distancias intra-grupo(alta semejanza intra-grupo) y alta distancia inter-grupo (baja semejanza inter-grupo) tendrá un bajo índice de Davies–Bouldin, el algoritmo de agrupamiento que produce la colección de grupos con menores índices de Davies–Bouldin está considerado el algoritmo mejor basado en este criterio.
  • Índice de Dunn
El índice de Dunn tiene como objetivos identificar densos y bien separados grupos. Está definido como la proporción entre la mínima distancia inter-grupo y la máxima distancia intra-grupo. Para cada partición de grupo, el índice de Dunn puede ser calculado por la fórmula siguiente:[32]
donde d(i,j) representa la distancia entre grupos i y j, y d '(k) mide la distancia intra-grupo del grupo k. La distancia inter-grupo d(i,j) entre dos grupos pueden ser cualquier número de medidas de distancia, como la distancia entre los centroides de los grupos. De modo parecido, la distancia intra-grupo d '(k) puede ser medida de diferentes formas, como la distancia máxima entre cualquier par de elementos en el grupo k. El criterio interno busca grupos con alta semejanza intra-grupo y baja semejanza inter-grupo, algoritmos que producen grupos con altos índices de Dunn son más deseables.
  • Coeficiente de silueta
El coeficiente de silueta contrasta la distancia media a elementos en el mismo grupo con la distancia media a elementos en otros grupos. Los objetos con un valor de silueta alto están considerados bien agrupados, los objetos con un valor bajo pueden ser ruido o anomalías. Estos índices trabajan bien con k-means, y es también utilizado para determinar el número óptimo de grupos.

Evaluación externa[editar]

En evaluación externa, los resultados de un agrupamiento son evaluados basados en datos que no fueron usados para el agrupamiento, como etiquetas de clases conocidas o marcadores externos. Tales marcadores constan de un conjunto de pre-elementos clasificados, y estos conjuntos son a menudo creados por humanos (expertos). Así, los conjuntos marcados pueden ser usados como patrón para la . Estos tipos de métodos de evaluación miden qué cercano está el agrupamiento del conjunto de clases predeterminadas. Aun así, recientemente se ha hablado si esto es adecuado para datos reales, o sólo en conjuntos de datos sintéticos con un factual "ground truth", donde las clases pueden contener estructura interna, los atributos presentes pueden no permitir la separación de los grupos o las clases pueden contener anomalías.[33]​ Además, de un punto de vista de descubrimiento del conocimiento, la reproducción de conocimiento sabido puede no necesariamente ser el resultado esperado.[33]​ En el escenario especial de Agrupamiento con restricciones, donde meta información (como etiquetas de clase) está utilizada ya en el proceso de agrupamiento, el control de la información para propósitos de evaluación es no trivial.[34]

Un número de medidas fue adoptado por las variantes utilizadas para evaluar tareas de clasificación. En lugar de contar el número de veces que una clase era correctamente asignada a un único punto de datos(conocido como ciertos positivos), lo que se hace es estimar para cada par de puntos simples que estén realmente en el mismo grupo cuanto se pronostica que estén en el mismo grupo.

Algunos de las medidas de calidad de un algoritmo de grupo que utiliza el criterio externo incluye:

  • Medida de Rand (William M. Rand 1971)[35]
El índice de Rand computa qué similar los grupos (regresados por el algoritmo de agrupamiento) son a las clasificaciones de los marcadores. Uno también puede ver el índice de Rand como medida del porcentaje de decisiones correctas hechas por el algoritmo. Puede ser computado utilizando la fórmula siguiente:
Dónde TP es el número de cierto positivos, TN es el número de cierto negativos, FP es el número de falso positivos, y FN es el número de falso negativos. Una característica con el índice de Rand es que falso positivos y falso negativos tienen el mismo peso. Esto puede ser una característica indeseable para alguna aplicación de un agrupamiento. La F-Medida está dirigida a resolver este problema.
La F-medida suele equilibrar la contribución de falso negativos por la ponderación recobrada a través de un parámetro . Precisión y recobrado pueden ser definidos como sigue:
Dónde P es el índice de precisión y R el índice de recobrado. Podemos calcular la F-medida utilizando la fórmula siguiente:[31]
Notar que cuando ,. En otras palabras, el recobrado no tiene ningún impacto en la F-medida cuándo , y creciente destina una cantidad creciente de peso para recordar en el final de F-medida.
El índice de Jaccard suele cuantificar la semejanza entre dos conjuntos de datos. El índice de Jaccard toma un valor entre 0 y 1. Un índice de 1 significa que los dos conjuntos son idénticos, y un índice de 0 indica que los conjuntos no tienen elementos comunes. El índice de Jaccard está definido por la fórmula siguiente:
Esto es sencillamente el número de los elementos únicos comunes a ambos conjuntos divididos por el número total de elementos únicos en ambos conjuntos.
  • • Índice de Fowlkes–Mallows (E. B. Fowlkes & C. L. Malvas 1983)[36]
El índice de Fowlkes-Mallows computa la semejanza entre los grupos devueltos por el algoritmo de agrupamiento y las clasificaciones de los marcadores. Entre más alto el valor del índice de Fowlkes-Mallows sea más similares son los grupos y las clasificaciones de los marcadores. Puede ser computado utilizando la fórmula siguiente:
Dónde TP es el número de ciertos positivos, FP es el número de falsos positivos, y FN es el número de falsos negativos. El índice FM es la media geométrica de la precisión y recobrado P y R, mientras la F-medida es su media armónica.[37]​ Además, precisión y recobrado son también conocidos como los índices de Wallace y .[38]


• La Información Mutua es una medida de cuánta información está compartida entre un agrupamiento y una clasificación "ground truth" que puede detectar una semejanza no lineal entre dos agrupamientos. La información mutua ajustada es una variante que tiene un sesgo reducido para números de grupo variable.

Una matriz de confusión puede usarse para visualizar rápidamente los resultados de un algoritmo de clasificación. Muestra qué diferente un grupo es del grupo de patrones antes creados por un experto.

Aplicaciones[editar]

Biología, biología computacional y bioinformáticas
 Ecología vegetal y animal:
Análisis de grupo suele usarse para describir y para hacer espacial y temporal comparaciones de comunidades de organismos en entornos heterogéneos; es también utilizado en Sistemática para generar grupos o filogenias artificiales de organismos (individual) en la especie, genus o nivel más alto que compartan un número de atributos
Transcriptomics:
Agrupamiento es usado para construir grupos de genes con patrones de expresión relacionados (también conocidos como coexpressed genes) como en HCS. A menudo tales grupos contienen proteínas relacionadas funcionalmente, como enzimas para una vía metabólica específica, o genes que son co-regulados.
Análisis de secuencia: Agrupamiento es usado para agrupar secuencias homólogas en familias de genes. Esto es un concepto muy importante en bioinformática, y biología evolutiva en general. Ver evolución por duplicación de gen.
Agrupamiento en genética humana: La semejanza de datos genéticos está utilizada en agrupamiento para inferir estructuras de población.
Medicina
Imágenes médicas:
En PET scans, análisis de grupo puede usarse para diferenciar entre tipos diferentes de tejido y sangre en una imagen tridimensional. En esta aplicación, la posición real no importa, pero la intensidad está considerada como un vector, con una dimensión para cada imagen que fue tomada con el tiempo. Esta técnica permite, por ejemplo, medida cuidadosa del índice de un rastro radioactivo entregado al área de interés, sin un muestreo separado de sangre arterial, una técnica intrusa que es más común hoy.

Análisis de actividad antimicrobial:

Análisis de grupo suele usarse para analizar patrones de resistencia de antibiótico, para clasificar compuestos antimicrobial es según su mecanismo de acción, para clasificar antibióticos según su actividad antibacterial.

Empresarial y marketing

Búsqueda de mercado:
Análisis de grupo es ampliamente utilizado en búsqueda de mercado cuándo se trabaja con datos multivariados de encuestas y tableros de prueba. Investigadores de marketing usan análisis de grupo para particionar la población general de consumidores en segmentos de mercado y para entender mejor las relaciones entre grupos diferentes de consumidores/potenciales clientes, y para uso en segmentación de mercado, posicionamiento de producto, desarrollo de productos nuevos y seleccionando mercados de prueba.

Agrupando elementos de compra:

Agrupamiento puede usarse para agrupar todos los elementos de compra disponibles en la web en un conjunto de productos únicos. Por ejemplo, todos los elementos en eBay puede ser agrupado en productos únicos. (eBay no tiene el concepto de un SKU)


World wide web

Análisis de red social:
En el estudio de redes sociales, agrupamiento puede usarse para reconocer comunidades dentro de grupos grandes de personas.


Agrupación de resultados de la búsqueda:

En el proceso de agrupación inteligente de los archivos y sitios web, agrupamiento puede usarse para crear un conjunto más pertinente de resultados de búsqueda comparados a motores de búsqueda normales como Google. Hay actualmente un número de herramientas de la web basadas en agrupamiento, como Clusty.

Slippy map optimization:

El mapa de fotos de Flickr y otros sitios usan agrupamiento para reducir el número de marcadores en un mapa. Esto los hace a ambos más rápidos y reduce la cantidad de grupos visuales.

Informática

Segmentación de imagen:
Agrupamiento puede usarse para dividir una imagen digital a regiones distintas para detección de frontera o reconocimiento de objetos.[39]

Algoritmos evolutivos:

Agrupamiento puede usarse para identificar nichos diferentes dentro de la población de un algoritmo evolutivo de modo que la oportunidad reproductiva puede ser distribuida más equitativamente entre la especie a evolucionar o subespecie.

Sistemas de recomendación:

Los sistemas de recomendación están diseñados para recomendar los elementos nuevos basados en los gustos de un usuario. A veces utilizan algoritmos de agrupamiento para pronosticar las preferencias de un usuario basados en las preferencias de otros usuarios en el grupo del usuario.

Detección de anomalía:

Anomalías/outliers son típicamente - pueden ser explícitamente o implícitamente - definidos con respecto a la estructura de los grupos en los datos.


Ciencia social
Análisis de delito:

Análisis de grupos puede usarse para identificar áreas donde hay incidencias más grandes de tipos particulares de delito. Para identificar estas áreas distintas o "sitios calientes" donde un delito similar ha pasado en un periodo de tiempo, es posible dirigir recursos de aplicación de la ley más eficazmente.

Minería de datos educacional:

Análisis de grupo es por ejemplo utilizado para identificar grupos de escuelas o alumnado con propiedades similares.


Otros

Robótica:
Los algoritmos de agrupamiento están utilizados para seguir objetos y detectar outliers en datos de los sensores.[3]

Química matemática:

Para encontrar semejanza estructural, etc., por ejemplo, 3000 compuestos químicos eran agrupados en el espacio de 90 índices topológicos.[40]
Climatología:
Para encontrar regímenes de tiempo o patrones atmosféricos de presión y nivel del mar.[41]

Geografía física: El agrupamiento de propiedades químicas en ubicaciones de muestra diferente.

Ver también[editar]

Tipos especializados de análisis de grupo[editar]

  • Agrupamiento de datos de alta dimensionalidad
  • Agrupamiento conceptual
  • Agrupamiento de consenso
  • Agrupamiento con restricciones
  • Data stream clustering
  • Agrupamiento secuencial
  • Agrupamiento espectral
  • HCS

Las técnicas utilizadas en análisis de grupo[editar]

Proyección de dato y preprocessing[editar]

Otro[editar]

  • Modelación ponderada de grupos
  • Maldición de la dimensionalidad
  • Determinando el número de grupos en un conjunto de datos
  • Coordenadas paralelas
  • Análisis de datos estructurados

Referencias[editar]

  1. Bailey, Ken (1994).
  2. Tryon, Robert C. (1939).
  3. a b Cattell, R. B. (1943).
  4. a b c d e f Estivill-Castro, Vladimir (20 de junio de 2002). «Why so many clustering algorithms — A Position Paper». ACM SIGKDD Explorations Newsletter 4 (1): 65-75. doi:10.1145/568574.568575. 
  5. Everitt, Brian (2011). Cluster analysis. Chichester, West Sussex, U.K: Wiley. ISBN 9780470749913. 
  6. Sibson, R. (1973). «SLINK: an optimally efficient algorithm for the single-link cluster method». The Computer Journal (British Computer Society) 16 (1): 30-34. doi:10.1093/comjnl/16.1.30. 
  7. Defays, D. (1977). «An efficient algorithm for a complete link method». The Computer Journal (British Computer Society) 20 (4): 364-366. doi:10.1093/comjnl/20.4.364. 
  8. Lloyd, S. (1982). «Least squares quantization in PCM». IEEE Transactions on Information Theory 28 (2): 129-137. doi:10.1109/TIT.1982.1056489. 
  9. Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (2011). «Density-based Clustering». WIREs Data Mining and Knowledge Discovery 1 (3): 231-240. doi:10.1002/widm.30. 
  10. Microsoft academic search: most cited data mining articles
  11. Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M., eds (1996). «A density-based algorithm for discovering clusters in large spatial databases with noise». Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. pp. 226–231. Plantilla:Citeseerx. ISBN 1-57735-004-9. 
  12. Ankerst, Mihael; Breunig, Markus M.; Kriegel, Hans-Peter; Sander, Jörg (1999). «OPTICS: Ordering Points To Identify the Clustering Structure». ACM SIGMOD international conference on Management of data. ACM Press. pp. 49–60. Plantilla:Citeseerx. 
  13. Achtert, E.; Böhm, C.; Kröger, P. (2006). «DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking». LNCS: Advances in Knowledge Discovery and Data Mining. Lecture Notes in Computer Science 3918: 119-128. ISBN 978-3-540-33206-0. doi:10.1007/11731139_16. 
  14. Roy, S.; Bhattacharyya, D. K. (2005). «An Approach to find Embedded Clusters Using Density Based Techniques». LNCS Vol.3816. Springer Verlag. pp. 523–535. 
  15. Sculley, D. (2010). «Web-scale k-means clustering». Proc. 19th WWW. 
  16. Huang, Z. (1998). «Extensions to the k-means algorithm for clustering large data sets with categorical values». Data Mining and Knowledge Discovery 2: 283-304. 
  17. R. Ng and J. Han. "Efficient and effective clustering method for spatial data mining". In: Proceedings of the 20th VLDB Conference, pages 144-155, Santiago, Chile, 1994.
  18. Tian Zhang, Raghu Ramakrishnan, Miron Livny. "An Efficient Data Clustering Method for Very Large Databases." In: Proc. Int'l Conf. on Management of Data, ACM SIGMOD, pp. 103–114.
  19. Can, F.; Ozkarahan, E. A. (1990). «Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases». ACM Transactions on Database Systems 15 (4): 483. doi:10.1145/99935.99938. 
  20. Agrawal, R.; Gehrke, J.; Gunopulos, D.; Raghavan, P. (2005). «Automatic Subspace Clustering of High Dimensional Data». Data Mining and Knowledge Discovery 11: 5. doi:10.1007/s10618-005-1396-1. 
  21. Karin Kailing, Hans-Peter Kriegel and Peer Kröger. Density-Connected Subspace Clustering for High-Dimensional Data. In: Proc. SIAM Int. Conf. on Data Mining (SDM'04), pp. 246-257, 2004.
  22. Achtert, E.; Böhm, C.; Kriegel, H. P.; Kröger, P.; Müller-Gorman, I.; Zimek, A. (2006). «Finding Hierarchies of Subspace Clusters». LNCS: Knowledge Discovery in Databases: PKDD 2006. Lecture Notes in Computer Science 4213: 446-453. ISBN 978-3-540-45374-1. doi:10.1007/11871637_42. 
  23. Achtert, E.; Böhm, C.; Kriegel, H. P.; Kröger, P.; Müller-Gorman, I.; Zimek, A. (2007). «Detection and Visualization of Subspace Cluster Hierarchies». LNCS: Advances in Databases: Concepts, Systems and Applications. Lecture Notes in Computer Science 4443: 152-163. ISBN 978-3-540-71702-7. doi:10.1007/978-3-540-71703-4_15. 
  24. Achtert, E.; Böhm, C.; Kröger, P.; Zimek, A. (2006). «Mining Hierarchies of Correlation Clusters». Proc. 18th International Conference on Scientific and Statistical Database Management (SSDBM): 119-128. ISBN 0-7695-2590-3. doi:10.1109/SSDBM.2006.35. 
  25. Böhm, C.; Kailing, K.; Kröger, P.; Zimek, A. (2004). «Computing Clusters of Correlation Connected objects». Proceedings of the 2004 ACM SIGMOD international conference on Management of data - SIGMOD '04. p. 455. ISBN 1581138598. doi:10.1145/1007568.1007620. 
  26. Achtert, E.; Bohm, C.; Kriegel, H. P.; Kröger, P.; Zimek, A. (2007). «On Exploring Complex Relationships of Correlation Clusters». 19th International Conference on Scientific and Statistical Database Management (SSDBM 2007). p. 7. ISBN 0-7695-2868-6. doi:10.1109/SSDBM.2007.21. 
  27. Meilă, Marina (2003). «Comparing Clusterings by the Variation of Information». Learning Theory and Kernel Machines. Lecture Notes in Computer Science 2777: 173-187. ISBN 978-3-540-40720-1. doi:10.1007/978-3-540-45167-9_14. 
  28. Kraskov, Alexander; Stögbauer, Harald; Andrzejak, Ralph G.; Grassberger, Peter (1 de diciembre de 2003) [28 November 2003]. Hierarchical Clustering Based on Mutual Information. arXiv:q-bio/0311039. 
  29. Auffarth, B. (July 18–23, 2010). «Clustering by a Genetic Algorithm with Biased Mutation Operator». WCCI CEC (IEEE). Plantilla:Citeseerx. 
  30. Frey, B. J.; Dueck, D. (2007). «Clustering by Passing Messages Between Data Points». Science 315 (5814): 972-976. PMID 17218491. doi:10.1126/science.1136800. 
  31. a b Manning, Christopher D.; Raghavan, Prabhakar; Schütze, Hinrich. Introduction to Information Retrieval. Cambridge University Press. ISBN 978-0-521-86571-5. 
  32. Dunn, J. (1974). «Well separated clusters and optimal fuzzy partitions». Journal of Cybernetics 4: 95-104. doi:10.1080/01969727408546059. 
  33. a b Färber, Ines; Günnemann, Stephan; Kriegel, Hans-Peter; Kröger, Peer; Müller, Emmanuel; Schubert, Erich; Seidl, Thomas; Zimek, Arthur (2010). «On Using Class-Labels in Evaluation of Clusterings». En Fern, Xiaoli Z.; Davidson, Ian; Dy, Jennifer. MultiClust: Discovering, Summarizing, and Using Multiple Clusterings. ACM SIGKDD. 
  34. Pourrajabi, M.; Moulavi, D.; Campello, R. J. G. B.; Zimek, A.; Sander, J.; Goebel, R. (2014). «Model Selection for Semi-Supervised Clustering». Proceedings of the 17th International Conference on Extending Database Technology (EDBT),. pp. 331–342. doi:10.5441/002/edbt.2014.31. 
  35. Rand, W. M. (1971). «Objective criteria for the evaluation of clustering methods». Journal of the American Statistical Association (American Statistical Association) 66 (336): 846-850. JSTOR 2284239. doi:10.2307/2284239. 
  36. E. B. Fowlkes & C. L. Mallows (1983), "A Method for Comparing Two Hierarchical Clusterings", Journal of the American Statistical Association 78, 553–569.
  37. L. Hubert et P. Arabie. Comparing partitions. J. of Classification, 2(1), 1985.
  38. D. L. Wallace. Comment. Journal of the American Statistical Association, 78 :569– 579, 1983.
  39. Bewley, A., & Upcroft, B. (2013). Advantages of Exploiting Projection Structure for Segmenting Dense 3D Point Clouds. In Australian Conference on Robotics and Automation [1]
  40. Bewley, A. «Real-time volume estimation of a dragline payload». IEEE International Conference on Robotics and Automation 2011: 1571-1576. 
  41. Huth, R. (2008). «Classifications of Atmospheric Circulation Patterns: Recent Advances and Applications». Ann. N.Y. Acad. Sci. 1146: 105-152.