Agrupamiento con medidas de distancia asimétricas

¿Cómo agrupa una entidad con una medida de distancia asimétrica?

Por ejemplo, supongamos que está agrupando un conjunto de datos con los días de la semana como una característica: la distancia de lunes a viernes no es la misma que la distancia de viernes a lunes.

¿Cómo incorporas esto a la medida de distancia del algoritmo de agrupamiento?

Si la distancia MF es asimétrica porque el futuro es diferente del pasado, entonces se requiere una agrupación asimétrica genuina. Primero, se debe definir una función de distancia asimétrica.

Una forma de agrupamiento asimétrico, dada una función de distancia, es incrustar los datos originales en un nuevo espacio de coordenadas. Ver "Estructuras geométricas de algunos modelos sin distancia para MDS asimétrico" por Naohito Chino y Kenichi Shiraiwa, Behaviormetrika, 1992 ( pdf ). Esto se llama HCM (el modelo canónico hermitiano).

Encuentre una matriz hermitiana , donde Encuentre los valores propios y los vectores propios, luego escale cada vector propio por la raíz cuadrada de su valor propio correspondiente.$H$

$$H_{ij} = \frac 1 2 [d(x_i, x_j) + d(x_j, x_i)] + i \frac 1 2 [d(x_i, x_j) - d(x_j, x_i)]$$

Esto transforma los datos en un espacio de números complejos. Una vez que los datos están incrustados, la distancia entre los objetos x e y es solo x * y, donde * es la transposición del conjugado. En este punto, puede ejecutar k-means en los vectores complejos.

La agrupación espectral asimétrica también se ha realizado; consulte la tesis de Stefan Emilov Atev, "Uso de la asimetría en la agrupación espectral de trayectorias", Universidad de Minnesota, 2011, que proporciona el código MATLAB para un algoritmo especial.

Puede tomar algún tipo de media (como una media aritmética o, para distribuciones de probabilidad, la raíz cuadrada de la divergencia Jensen-Shannon).

Debe echar un vistazo a las estadísticas circulares (si desea trabajar "dentro" de una semana de optimización)

Si su función de distancia no es un núcleo Mercer válido, entonces , donde es la matriz de Gram. En este caso, queremos co-clustering, también llamado bi-clustering. Los algoritmos de esta clase producen indicadores de clúster simultáneamente para las filas y columnas.$X \neq X^T$$X$

El ejemplo que dio es el resultado de una métrica de distancia mal elegida. Una mejor métrica de distancia sería$|\text{days apart}|$

En general, su función de distancia debe ser un núcleo Mercer válido. A válido Mercer kernel es cualquier función de tomar dos observaciones que es continua, simétrica y tiene una covarianza definida positiva matriz .$\forall x \in D$