[latexpage]
¿Qué es el Análisis clúster?
Análisis Clúster o Clustering es un proceso que agrupa los datos en clases, tal que objetos dentro de una clase sean lo más semejantes entre sí, pero muy diferentes con otros objetos de otra clase. El proceso de agrupación de un conjunto de objetos físicos o abstractos en clases u objetos similares es llamado clustering.
Un clúster es una colección de datos u objetos que son similares entre sí dentro del mismo clúster y diferentes a otros objetos en otros clústeres. El análisis clúster ha sido ampliamente usado en numerosas aplicaciones, incluyendo investigación de mercado, reconocimiento de patrones, análisis de datos, y procesamiento de imágenes.
En el mundo de los negocios, clustering apoya al área de mercadotecnia a descubrir grupos distintos en las bases de sus clientes y caracterizar grupos de consumo basados en patrones de compra. In biología, es utilizado para derivar taxonomías de animales y plantas, identificar genes con funciones semejantes.
Clustering es también llamado segmentación de datos en algunas aplicaciones porque clustering particiona conjuntos grandes de datos en grupos de acuerdo a sus semejanzas. Como una rama de la estadística, el análisis clúster ha sido extensamente estudiado por muchos años, enfocándose principalmente en análisis clúster basado en distancia.
Las herramientas para análisis clúster usan los algoritmos k-medias, k-medias, y muchos más métodos han sido programados en software de análisis estadístico, tales como S-PLUS, SPSS, y SAS. En aprendizaje automático o máquinas de aprendizaje, clustering es un ejemplo de aprendizaje no supervisado.
A diferencia de la clasificación, clustering y aprendizaje automático no se basan en una clase predefinida y en ejemplos de entrenamiento de clases etiquetadas. Por esta razón clustering es una forma de aprendizaje por observación, en lugar de aprendizaje por ejemplos. En Minería de datos, los esfuerzos se concentran en métodos de búsqueda para análisis de clúster eficientes y efectivos en bases de datos grandes.
Tipos de datos en análisis clúster
En esta sección se estudian los tipos de datos qué frecuentemente se utilizan en el análisis cluster y cómo prepararlos para este tipo de análisis. Supóngase que un conjunto de datos que será agrupado contiene n objetos, que representan personas, casa, documentos, países, y asó por el estilo. Los algoritmos principales para clustering trabajan con los siguientes tipos de estructuras.
Matriz de datos (o estructura objeto por variable), ésta representa $n$ objetos, tales como personas, con p-variables (también llamadas medidas o atributos), tales como edad, talla, género, y así por el estilo. La estructura tiene la forma de una matriz $nxp$ ($n$ objetos por $p$ variables):
\[ \bordermatrix{
&&&&&\cr
& x_{11} & \cdots & x_{1k} & \cdots & x_{1p} \cr
& \vdots & \cdots & \vdots & \cdots & \vdots \cr
& x_{n1} & \cdots & x_{nk} & \cdots & x_{np} \cr
}\]
Matriz de disimilitud (o estructura objeto por objeto), ésta almacena una colección proximidades que están disponibles para todos los pares de $\textit{n}$ objetos. Es frecuentemente representada por una matriz de $\textit{n}$ por $\textit{n}$
\[ \bordermatrix{
&&&&&\cr
& 0 & & & & \cr
& d(2,1) & 0 & & & \cr
& d(3,1) & d(3,2) & 0 & & \cr
& \vdots & \vdots & \vdots & \ddots& \cr
& d(n,1) & d(n,2) & \cdots & \cdots & 0 \cr
} \]
Donde $d(i,j)$ es la diferencia medida o disimilitud entre los objetos $i$ y $j$. En general, $d(i,j)$ es un número positivo que es cero cuando dos objetos $i$, $j$ son semejantes, (el mismo).
Los renglones y las columnas de la matriz de datos representan entidades diferentes, mientras que la matriz de disimilitud representa la misma entidad. Muchos algoritmos de clustering trabajan con matrices de disimilitud. Si los datos son representados en la forma de una matriz de datos, ésta puede ser transformada en una matriz de disimilitud antes de aplicar dichos algoritmos.
Variables de escala o intervalo
En esta sección se discute las variables de escala o intervalo y su estandarización.
¿Qué es una variable de escala o intervalo?
Las variables de escala o intervalo son medidas continuas de una escala de aproximación lineal. Ejemplos comunes son la altura, ancho, coordenadas etc.
La unidad de medida puede afectar el análisis cluster. Por ejemplo, cambiando las unidades de medida de metros a pulgadas para la altura, o de kilos a libras para el peso, puede conducir a diferentes estructuras de clustering.
En general expresando una variable en unidades pequeñas se obtiene frecuentemente rangos extensos de la misma, y así un efecto grande en los resultados de la estructura de los clusters Para evitar la elección de la unidad de medida, los datos deberán ser estandarizados. Las medidas estandarizadas pretenden transformar a todas las variables en un rango equivalente (o peso).
Esta modificación en particular es muy útil cuando no se tiene conocimiento previo de los datos. Sin embargo, en algunas aplicaciones, los usuarios intencionalmente dan un peso a cierto conjunto de variables elegidas en relación a los objetivos de estudio.
¿Cómo pueden ser estandarizados los datos de una variable?
Para estandarizar la unidad de medida, una elección es convertir la medida en variable adimensionales. Dada una medida para la variable f, esta puede ser transformada como sigue:
Calcular la desviación media absoluta, $s_f$
\[ s_f =\frac{1}{n} ( {\left| x_{1f}-m_f \right| + \cdots + \left| x_{nf} – m_f \right|} )%
\]
donde $x_{if},\cdots,x_{nf}$ son $n$ valores de $f$, y $m_f$ es el valor de la media de $f$, esto es, $m_f = \frac{1}{n}(x_{1f}+ \cdots + x_{nf})$
Calcular la medida estandarizada
\[ z_{if} = \frac{x_{if}-m_f}{s_f} \]
La desviación media absoluta
$s_f$, es más robusta para los datos atípicos que la desviación estándar $\sigma_f$. Cuando se calcula la desviación media absoluta, no es afectada en proporción, por lo tanto, el efecto de los datos atípicos es poco. La ventaja consiste en que la transformación de los datos atípicos descrita no los convierte en valores pequeños, así estos datos pueden ser localizables.
La estandarización puede o no ser útil en aplicaciones particulares. La elección de estandarizar y cómo hacerlo es criterio del analista. La disimilitud entre dos objetos descritos por variables de escala o intervalo se calcula a través de la distancia entre cada par de objetos.
Distancia Euclidiana
Entre ellas está la distancia Euclidiana, la cual se define de la siguiente forma
\[ d(i,j) = \sqrt{ (x_{i1} – x_{j1})^2 +(x_{i2}- x_{j2} )^2 +\cdots +(x_{in} – x_{jn})^2 } \]
donde $i = (x_{i1}, x_{i2},\ldots , x_{in} )$ y $j = (x_{j1}, x_{j2}, \ldots , x_{jn} )$ son dos conjuntos de datos \textit{n-dimensional}
Distancia Manhattan
Otra métrica conocida es la distancia Manhattan (o city block) definida como:
\[ d(i,j) = \left| x_{i1} – x_{j1} \right| + \left| x_{i2} – x_{j2} \right| + \ldots + \left| x_{in} – x_{jn} \right| \]
Ambas distancias (Euclidiana y Manhattan) satisfacen los siguientes requisitos matemáticos de una función de distancia:
- $d(i,j) \geq 0$ La distancia es siempre positiva. (No negatividad)
- $d(i,i) = 0$ La distancia entre el mismo objeto es cero. (Definición positiva)
- $d(i,j) = d(j,i)$ La distancia es simétrica.
- $d(i,j) \leq d(i,h) + d(h,j)$ Cumple con la desigualdad triangular.
Distancia Minkowsk
La distancia Minkowski es una generalización de ambas distancias (Euclidiana y Manhattan), está se define como:
\[ d(i,j) = ( \left| x_{i1} – x_{j1} \right|^p + \left| x_{i2} – x_{j2} \right|^p + \ldots + \left| x_{in} – x_{jn} \right|^p )^{1/p} \]
Donde $p$ es un número entero positivo. Esta distancia también es llamada norma $Lp$, en alguna literatura. Si $p = 1$ obtenemos la distancia Manhattan, y si $p = 2$ la Euclidiana.
Variables Binarias
La disimilitud entre dos variables binarias, simétricas o asimétricas
Una variable binaria tiene sólo dos estados 0 o 1, donde 0 significa que la variable está ausente, y 1 significa que la variable está presente. El tratamiento de variables binarias cómo si fueran de escala o intervalo puede derivar en resultados de agrupamiento engañosos.
Por lo mismo son necesarios métodos específicos que calculen las disimilitudes. ¿Cómo se calcula la disimilitud entre dos variables binarias? Un enfoque implica calcular la matriz de disimilitud dados datos binarios. Si todas las variables se consideran con el mismo peso, se obtiene una tabla de contingencia de $2×2$
Matriz para calcular la disimiltud binaria
El número $q$ es el número de 1 que tienen ambos objetos, así $t$ es el número de 0 que tienen ambos, el número $s$ es el número 1 que tiene el objeto $j$ y que el objeto $i$ tiene 0, $r$ es el número de 0 que tiene el objeto $j$ y que el número de 1 que tiene el objeto $i$. El número total de variables es $p$ donde $p = q + r + s + t$.
¿Cuál es la diferencia entre la variable binarias simétrica y asimétrica? Una variable binaria es simétrica si ambos de sus estados tienen el mismo peso. La medida de disimilitud (o distancia) se define como:
\[ d(i, j) = (r + s)/(q + r + s + t) \]
Entonces una variable binaria asimétrica es una variable binaria no simétrica. Es decir, si los resultados de los estados no son igualmente importantes. La disimilitud basada en tales variables es llamada disimilitud binaria asimétrica, donde el número de relaciones negativas, $t$, es considerada no importante así es ignorada en el cálculo, como se muestra en la ecuación
\[ d(i, j) = (r + s)/(q + r + s) \]
Adicionalmente se puede medir la distancia entre dos variables basada en la noción de semejanza en lugar de disimilitud. La semejanza binaria asimétrica entre dos objetos $i$ y $j$, o $sim(i, j)$ es:
\[ sim(i, j) = q/(q+r+s)= 1-d(i, j) \]
El coeficiente $sim(I,j)$ es llamado el coeficiente Jaccard.
Clasificación general de métodos para clúster
Muchos algoritmos de agrupamiento existen en la literatura. Es difícil realizar una categorización completa de los métodos de clúster porque estas categorías pueden traslaparse, de tal forma que un método puede tener características de diferentes categorías. Sin embargo, se puede presentar una descripción organizada de los diferentes métodos clúster.
Métodos de particionamiento
Dada una base de datos de n objetos con n tuplas, un método de particionamiento construye k particiones de los datos, donde cada partición representa un clúster con k <= n. Esto es, clasifica los datos en k grupos, los cuales satisfacen las siguientes restricciones: 1) cada grupo contiene por lo menos un objeto y 2) cada objeto pertenece solamente a un grupo. Nótese que la segunda condición puede ser relajada con alguna técnica de particionamiento borroso (fuzzy).
Dado k, el número de particiones para construir, un método de particionamiento crea una partición inicial. Entonces se usa un técnica de relocalización iterativa que intenta mejorar la partición a través del movimiento de los objetos de un grupo hacia otro. El criterio general de una buena partición consiste en que objetos en el mismo clúster estén cercas o relacionado con los demás, mientras objetos de diferentes clúster están lejos o son diferentes.
Para mejorar una optimización global de clustering basado en partición se requiere de una enumeración exhaustiva de todas las posibles particiones. Como alternativa muchas aplicaciones adoptan uno de métodos heurísticos: tales como el algoritmo k-medias, donde cada clúster es representado por el valor medio de los objetos en el clúster y 2) el algoritmo k.medoids, donde cada clúster es representado por uno de los objetos localizado cercas del centro del clúster
Estos métodos heurísticos de agrupamiento trabajan bien para encontrar clúster con formas esféricas de pequeñas a medianas basases de datos. Para encontrar clúster con formas complejas y clúster para grandes cantidades de datos, los métodos de particionamiento necesitan ser mejorados.
Métodos jerárquicos
Un método jerárquico crea una descomposición jerárquica de un conjunto de objetos. Un método jerárquico puede ser clasificado como aglomerativo o divisivo, dependiendo cómo la descomposición jerárquica está formada.
El método aglomerativos , también llamado de abajo hacia arriba, comienza formando un grupo por cada objeto. Éste sucesivamente agrupa los objetos o grupos que están cercas unos de otros, hasta que todos los grupos están fusionados en uno sólo (el nivel más alto de la jerarquía), o hasta que una condición determinada se cumpla.
Los métodos divisivos, también llamados de arriba hacia abajo, define todos los objetos como un solo grupo. En todas las iteraciones sucesivas, el clúster es dividido en grupos más pequeños, hasta que cada objeto es un grupo., o se detiene hasta una condición determinada.
Los métodos jerárquicos tienen el defecto que una vez hecho un paso (agrupación o división) este no puede deshacerse Esta rigidez es útil siempre que se desee que el costo de computo sea pequeño ya que no se tiene que preocupara por el número de combinaciones de los diferentes grupos.
Sin embargo, estas técnicas no pueden corregir decisiones erróneas, existen dos enfoques para mejorar la calidad del agrupamiento jerárquico:
- realizar un cuidadoso análisis de los ”enlaces” de los objetos en cada partición de la jerarquía
- integrar aglomeración jerárquica y otros enfoques al utilizar por primera vez los algoritmos jerárquicos para agrupar objetos en micro-grupos, y seguido realizar macro-grupos sobre los micro-grupos usando otros métodos de agrupamiento tal como la agrupación iterativa.
Métodos basados en densidad
La mayoría de los objetos se agrupan por métodos de partición basados en la distancia entre ellos. Tales métodos solamente pueden definir grupos pertenecientes a formas esféricas y tienen mucha dificultad para descubrir grupos en formas arbitrarias. Otros métodos de agrupamiento han sido desarrollados sobre la noción de densidad.
La idea general es hacer grande el grupo, tanto como su densidad (número de objetos o puntos) en la vecindad hasta que exceda un umbral; esto es, para cada punto dentro de un grupo dado, la vecindad de un radio dado tiene que contener hasta el último por lo menos un número mínimo de puntos. Éste método puede ser utilizado para filtrar ruidos (datos atípicos) y descubrir grupos de formas arbitrarias.
Métodos basados en cuadrícula
Éstos métodos discretizan el espacio del objeto en un número finito de células que se derivan de una estructura cuadriculada. Todas las operaciones de agrupamiento son realizadas en la estructura cuadriculada.
La principal ventaja de esta técnica consiste en que el proceso se realiza muy rápido, el cual es independiente del número de objetos y sólo depende del número de celdas en cada dimensión del espacio cuántico.
Métodos basados en modelos
Estos métodos basados en modelos determinan un modelo hipotético para cada grupo y encuentra el mejor ajuste de los datos para el modelo dado. Un algoritmo basado en modelos puede localizar grupos construyendo una función de densidad que refleja la distribución espacial de los datos.
Esto también conduce a una forma automática de determinar el número de grupos desde un enfoque estadística, tomando en cuenta el ruido y datos atípicos, así se obtiene un método de agrupamiento robusto.
Agrupamientos
La elección del algoritmo de agrupamiento depende de los datos disponibles y del objetivo de la aplicación. Si el análisis clúster es utilizado como una herramienta de descripción o exploración, es recomendable probar los diferentes algoritmos con los mismos datos para comprobar cuales pueden ser los datos relevantes.
Algunos algoritmos de agrupamiento integran las ideas de varios métodos, así que es difícil clasificar los algoritmos en una única clase o categoría de métodos. Además, algunas aplicaciones pueden tener criterios para agrupar que requieren la integración de diversas técnicas de agrupamiento.
Existe dos tareas importante de agrupamiento que merecen mencionarse. Una es agrupamiento de datos con alta dimensioanalidad y la otra es agrupamiento basado en restricciones.
Agrupamiento de datos con alta dimensioanalidad
Es en particular una tarea importante en el análisis de clúster porque algunas aplicaciones requieren que el análisis de los objetos contengan un largo número de características o dimensiones.
Algunas de ellas pueden ser relevantes. Si el número de las dimensiones incrementa, los datos son cada vez más escasos, así que la distancia entre cada par de puntos llega a ser insignificante y el promedio de la densidad de puntos en cualquier lugar de los datos es probablemente baja.
Agrupamiento con restricciones
Este enfoque permite realizar agrupamiento utilizando especificaciones del usuario o restricciones orientadas a la aplicación. Una restricción expresa un requerimiento del usuario o describe propiedades que se desean contengo los grupos., suministra un efectivo significado de comunicación en el proceso de agrupamiento. Diversas clases de restricciones pueden ser especificadas, algunas por el usuario otras por establecidas por la aplicación.
Métodos de Partición
Sea $D$, un conjunto de datos de $n$ objetos, y $k$ el número de grupo a formar, un algoritmo de particionamiento organiza los objetos en $k$ particiones con $k \leq n$, donde cada partición representa un grupo. El grupo está formado de tal forma que optimiza un criterio de partición objetivo, tal como una función de disimilitud basada en alguna distancia, de forma que objetos del mismo grupo sean lo más semejantes posible, mientras objetos de diferentes grupos sean distintos.
Técnica de centros móviles o centroide, el método k-media
El algoritmo k medias toma los parámetros de entrada, $k$, y realiza una partición de un conjunto de $n$ objetos en $k$ grupos tal que el resultado de la similitud intraclase es alta, pero la similitud interclase es baja. La similitud del grupo es medida con respecto al valor medio de los objetos en el grupo, que puede ser visto como el centroide del grupo o centro de gravedad.
El algoritmo $k$-medias primero selecciona aleatoriamente $k$ objetos, cada uno representa inicialmente el promedio del grupo o centro. Para cada uno de los objetos restantes, un objeto es asignado al grupo al cual es más semejante, basándose en la distancia entre el objeto y el promedio del grupo. Ahora se calcula el nuevo promedio para cada grupo. Este proceso se repite hasta que el criterio de la función converge. Frecuentemente, es usado el criterio del error cuadrado definido como:
\[ E = \sum\limits_{i=1}^{k}{ \sum\limits_{p\in C_{i}}^{} {\left| p-m_{i} \right|^2}} \]
k-medias
Ahora explicaré desde un punto de vista formal el algoritmo k-medias
Partición. Si I $:= \left[ a, b \right]$ es un intervalo acotado cerrado en R, entonces una partición de I es un conjunto finito ordenado $P:=\left{ x_0 , x_1, \ldots , x_n \right}$ de puntos en I tales que
\[
a = x_0 < x_1 < x_2 < \cdots < x_n = b
\]
En un espacio vectorial se tiene que
Sea $ X := \left{ x_1, \ldots , x_m \right} $ un conjunto de vectores en $\mathds{R}^n$. Una Parición $\Pi$ de $X$ se define como
\[ \Pi := \left{ \pi_1, \ldots, \pi_k \right} \]
$\pi_1 \cup \cdots \cup \pi_k = \left{ x_1, \ldots , x_m \right}$ y $\pi_i \cap \pi_j = \emptyset$ si $i \neq j$
Sea $q$ una función de valor real con dominio en $X$, entonces, la calidad de la \textit{partición} está dada por
\[
Q(\Pi) = q(\pi_1) + \cdots + q(\pi_k)
\]
Ahora se desea identificar una partición óptima
\[
\Pi^0 = \left{ \pi^0_1 , \ldots , \pi^0_k \right}
\]
En general la solución está disponible cuando la dimensión de un vector es uno. Para encontrar la partición deseada la forma más fácil de hacerlo es, dada una partición
\[
\Pi^{(t)} = \left{ \pi^{(t)}_1, \ldots , \pi^{(t)}_k \right}
\]
Construir una partición
\[
\Pi^{(t+1)} = \left{ \pi^{(t+1)}_1, \ldots , \pi^{(t+1)}_k \right}
\]
tal que
- Hay grupos $\pi^{(t)}_i , \pi^{(t)}_j$ y $x \in \pi^{(t)}_i$
- $\pi^{(t+1)}_i = \pi^{(t)}_i – \left{ x \right}$, $ \pi^{(t)}$
Referencias
- Data Minig, soluciones con Enterprise Miner, César Pérez y Daniel Santín. Alfaomega
- EStadística para investigadores, introducción al diseño de experimentos, análisis de datos y construcción de modelos. Goerce Box, William Hunter y Stuart Hunter. Editorial Reverté
- Introducción a la minería de Datos. José Hernández Orallo, José Ramírez Quintana y César Ferri Ramírez. Pearson, Prentice Hall
- Análisis Multivariable. Hair, Anderson, Tatham y Black. Pearson, Prentice Hall
- Cluster Analysis in Tests Market Selection Green,P.E.;Frank,R.E. y Robinson,P.J. Management Science
- Cluster Analysis, J.Willey & Son