Comprensión básica del algoritmo de agrupamiento de Jarvis-Patrick

El algoritmo de agrupamiento de Jarvis Patrick es una técnica de agrupamiento basada en gráficos que reemplaza la vecindad entre dos puntos con la similitud SNN, que se calcula como se describe en el algoritmo SNN. A continuación, se acostumbra a un umbral para dispersar esta array de similitudes SNN.

Nota: La ‘esparsificación’ es una técnica en la que la cantidad de datos que deben procesarse se reduce drásticamente. 

Algoritmo SNN (similitud del vecino más cercano compartido):

1. Encuentre los k-vecinos más cercanos de todos los puntos.
2. si dos puntos, x e y no parecen estar entre los k-vecinos más cercanos entre sí, entonces
3. similitud ( x , y )<–0
4. más
5. similitud ( x , y )<– el número de vecinos compartidos
6. terminara si

ALGORITMO DE CLUSTERING JARVIS-PATRICK: Hay 3 entradas, necesarias para que el algoritmo funcione. 

• Función de distancia , para calcular la distancia entre dos puntos dados.
• ‘ k ‘, número de los vecinos más cercanos para tomar nota, mientras se forman grupos.
• ‘ kmin ‘, el número mínimo de vecinos compartidos para agrupar dos puntos cualesquiera.

El funcionamiento del algoritmo es el siguiente:

1. Se encuentran los vecinos más cercanos ‘k’ de todos los puntos.
2. Un par de puntos se colocan dentro del mismo grupo, si dos puntos comparten más de ‘t’ vecinos y también los dos puntos están en la lista de vecinos más cercanos ‘k’ del otro.

• Por ejemplo, podríamos elegir la lista de vecinos más cercanos de tamaño 30 y colocar puntos dentro del mismo grupo, si comparten más de 15 vecinos más cercanos.

Ejemplo: agrupación de Jarvis-Patrick de un conjunto de datos bidimensional.

• Apliquemos el agrupamiento de Jarvis-Patrick al conjunto de datos de ‘peces’ (como se muestra en (a) a continuación), para buscar los grupos (que se muestran en (b) a continuación). El tamaño de la lista de vecinos más cercanos era 20, y dos puntos se colocaban dentro del grupo idéntico si compartían un mínimo de 10 puntos. Los diversos grupos se muestran mediante diferentes marcadores y diferentes sombreados. Los puntos cuyo marcador es una ‘x’ fueron clasificados como ruido por Jarvis-Patrick. Se encuentran principalmente dentro de las regiones de transición entre grupos de densidad variada.

Agrupación de Jarvis-Patrick de un conjunto de puntos bidimensional

• Requisitos de almacenamiento del algoritmo de agrupamiento de Jarvis-Patrick: O (km), ya que no es realmente necesario almacenar toda la array de similitud, ni siquiera inicialmente.
• Complejidad temporal básica del agrupamiento de Jarvis-Patrick: O (m^2), ya que la creación de la lista de k vecinos más cercanos puede requerir el cálculo de la proximidad O (m^2) .
• Sin embargo, para ciertos tipos de datos, como datos euclidianos de baja dimensión, por ejemplo, un árbol kd, se puede utilizar para buscar los k vecinos más cercanos sin calcular la array de similitud completa, de manera más eficiente. Esto podría reducir la complejidad del tiempo de O (m^2) a O (m log m).

Fortalezas:

1. Dado que el agrupamiento de Jarvis-Patrick se basa en la noción de similitud de SNN, es bueno para lidiar con el ruido y puede manejar grupos de diferentes tamaños, formas y densidades.
2. El algoritmo funciona bien para datos de alta dimensión.
3. El algoritmo es maravilloso para encontrar grupos estrechos de objetos fuertemente relacionados.

Limitaciones:

1. La agrupación en clústeres de Jarvis-Patrick define un clúster como un componente conectado dentro del gráfico de similitud SNN. Por lo tanto, si un grupo de objetos se divide en dos grupos o se dejan juntos, puede depender de un solo enlace. Por lo tanto, el agrupamiento de Jarvis-Patrick es algo frágil, es decir, puede dividir verdaderos grupos o unir grupos que deben mantenerse separados.
2. En este algoritmo, no todos los objetos están agrupados. Sin embargo, estos objetos se agregarán a los clústeres existentes y, en algunos casos, no se requiere un clúster completo. Cuando se coloca junto a otros algoritmos de agrupamiento, elegir los mejores y más simples valores para los parámetros puede ser un desafío.