Medoid

Los medoides son objetos representativos de un conjunto de datos o de un clúster dentro de un conjunto de datos cuya suma de disimilitudes con todos los objetos del clúster es mínima. ^{[ 1 ]} Los medoides son similares en concepto a las medias o centroides , pero siempre se restringen a ser miembros del conjunto de datos. Los medoides se utilizan con mayor frecuencia en datos cuando no se puede definir una media o un centroide, como en los gráficos. También se utilizan en contextos donde el centroide no es representativo del conjunto de datos, como en imágenes, trayectorias 3D y expresión génica ^{[ 2 ]} (donde, si bien los datos son dispersos, el medoide no tiene por qué serlo). También son de interés cuando se desea encontrar un representante utilizando alguna distancia distinta de la distancia euclidiana al cuadrado (por ejemplo, en calificaciones de películas).

Para algunos conjuntos de datos, puede haber más de un medoide, como ocurre con las medianas. Una aplicación común del medoide es el algoritmo de agrupamiento k-medoides , similar al algoritmo k-medias , pero que funciona cuando no se puede definir una media o un centroide. Este algoritmo funciona básicamente de la siguiente manera: primero, se elige un conjunto de medoides al azar; segundo, se calculan las distancias a los demás puntos; tercero, los datos se agrupan según el medoide al que son más similares; y cuarto, el conjunto de medoides se optimiza mediante un proceso iterativo.

Cabe destacar que un medoide no es equivalente a una mediana , una mediana geométrica ni un centroide . Una mediana se define únicamente en datos unidimensionales y solo minimiza la disimilitud con otros puntos para métricas definidas por una norma (como la distancia de Manhattan o la distancia euclidiana ). Una mediana geométrica se define en cualquier dimensión, pero a diferencia de un medoide, no necesariamente es un punto del conjunto de datos original.

Dejar${\textstyle {\mathcal {X}}:=\{x_{1},x_{2},\dots,x_{n}\}}$ser un conjunto de${\textstyle n}$puntos en un espacio con una función de distancia d. El medoide se define como

${\displaystyle x_{\text{medoid}}=\arg \min _{y\in {\mathcal {X}}}\sum _{i=1}^{n}d(y,x_{i}).}$

Los medoides son una alternativa popular a la media de los clústeres cuando la función de distancia no es la distancia euclidiana (al cuadrado), ni siquiera una métrica (ya que el medoide no requiere la desigualdad triangular ). Al dividir el conjunto de datos en clústeres, el medoide de cada clúster puede utilizarse como representante del mismo.

Los algoritmos de agrupamiento basados ​​en la idea de medoides incluyen:

• Particionamiento alrededor de los medoides (PAM), el algoritmo estándar de k-medoides
• Agrupamiento jerárquico alrededor de medoides (HACAM), que utiliza medoides en el agrupamiento jerárquico.

De la definición anterior, queda claro que el medoide de un conjunto${\displaystyle {\mathcal {X}}}$se puede calcular después de calcular todas las distancias por pares entre los puntos del conjunto. Esto tomaría ${\textstyle O(n^{2})}$evaluaciones a distancia (con${\displaystyle n=|{\mathcal {X}}|}$). En el peor de los casos, no se puede calcular el medoide con menos evaluaciones de distancia. ^{[ 3 ] [ 4 ]} Sin embargo, existen muchos enfoques que nos permiten calcular los medoides de forma exacta o aproximada en tiempo subcuadrático bajo diferentes modelos estadísticos.

Si los puntos se encuentran en la línea real, el cálculo del medoide se reduce a calcular la mediana, lo cual se puede hacer en${\textstyle O(n)}$mediante el algoritmo de selección rápida de Hoare. ^{[ 5 ]} Sin embargo, en espacios reales de dimensiones superiores, no se conoce ningún algoritmo de tiempo lineal. RAND ^{[ 6 ]} es un algoritmo que estima la distancia promedio de cada punto a todos los demás puntos mediante el muestreo de un subconjunto aleatorio de otros puntos. Toma un total de ${\textstyle O\left({\frac {n\log n}{\epsilon ^{2}}}\right)}$cálculos de distancia para aproximar el medoide dentro de un factor de${\textstyle (1+\epsilon \Delta)}$con alta probabilidad , donde${\textstyle \Delta }$es la distancia máxima entre dos puntos en el conjunto. Tenga en cuenta que RAND es un algoritmo de aproximación y, además, ${\textstyle \Delta }$Puede que no se conozca de antemano.

TOPRANK ^{[ 7 ]} aprovechó RAND , que utiliza las estimaciones obtenidas por RAND para centrarse en un pequeño subconjunto de puntos candidatos, evalúa la distancia promedio de estos puntos exactamente y elige el mínimo de ellos. TOPRANK necesita ${\textstyle O(n^{\frac {5}{3}}\log ^{\frac {4}{3}}n)}$Cálculos de distancia para encontrar el medoide exacto con alta probabilidad bajo una suposición de distribución sobre las distancias promedio.

trimed ^{[ 3 ]} presenta un algoritmo para encontrar el medoide con ${\textstyle O(n^{\frac {3}{2}}2^{\Theta (d)})}$ Evaluaciones de distancia bajo una suposición de distribución sobre los puntos. El algoritmo utiliza la desigualdad triangular para reducir el espacio de búsqueda.

Meddit ^{[ 4 ]} aprovecha una conexión del cálculo medoide con bandidos multi-brazos y utiliza un algoritmo de tipo límite de confianza superior para obtener un algoritmo que toma${\textstyle O(n\log n)}$Evaluaciones de distancia bajo supuestos estadísticos sobre los puntos.

El algoritmo de reducción a la mitad secuencial correlacionada ^{[ 8 ]} también aprovecha las técnicas de bandidos multi-brazos, mejorando el algoritmo Meddit . Al explotar la estructura de correlación en el problema, el algoritmo puede producir una mejora drástica (generalmente de 1 a 2 órdenes de magnitud) tanto en la cantidad de cálculos de distancia necesarios como en el tiempo de ejecución.

Aquí se puede encontrar una implementación de RAND , TOPRANK y trimed . Aquí y aquí se puede encontrar una implementación de Meddit . Aquí se puede encontrar una implementación de Correlated Sequential Halving .

Los medoides se pueden aplicar a diversas tareas de texto y PLN para mejorar la eficiencia y la precisión de los análisis. ^{[ 9 ]} Al agrupar datos de texto en función de su similitud, los medoides pueden ayudar a identificar ejemplos representativos dentro del conjunto de datos, lo que permite una mejor comprensión e interpretación de los mismos.

Técnicas para medir la similitud de texto en la agrupación basada en medoides

Al aplicar la agrupación basada en medoides a datos de texto, es fundamental elegir una medida de similitud apropiada para comparar documentos de manera efectiva. Cada técnica tiene sus ventajas y limitaciones, y la elección de la medida de similitud debe basarse en los requisitos y características específicas de los datos de texto que se analizan. ^{[ 14 ]} A continuación se presentan técnicas comunes para medir la similitud de texto en la agrupación basada en medoides:

similitud del coseno

La similitud del coseno es una medida ampliamente utilizada para comparar la similitud entre dos fragmentos de texto. Calcula el coseno del ángulo entre dos vectores de documento en un espacio de alta dimensión. ^{[ 14 ]} La similitud del coseno varía entre -1 y 1, donde un valor más cercano a 1 indica mayor similitud, y un valor más cercano a -1 indica menor similitud. Al visualizar dos líneas que parten del origen y se extienden hasta los puntos de interés respectivos, y luego medir el ángulo entre estas líneas, se puede determinar la similitud entre los puntos asociados. La similitud del coseno se ve menos afectada por la longitud del documento, por lo que puede ser más eficaz para producir medoides que sean representativos del contenido de un clúster en lugar de la longitud.

similitud de Jaccard

La similitud de Jaccard, también conocida como coeficiente de Jaccard, mide la similitud entre dos conjuntos comparando la proporción entre su intersección y su unión. En el contexto de los datos textuales, cada documento se representa como un conjunto de palabras, y la similitud de Jaccard se calcula en función de las palabras comunes entre ambos conjuntos. El valor de la similitud de Jaccard oscila entre 0 y 1, donde un valor más alto indica un mayor grado de similitud entre los documentos.

distancia euclidiana

La distancia euclidiana es una métrica de distancia estándar que se utiliza para medir la disimilitud entre dos puntos en un espacio multidimensional. En el contexto de los datos de texto, los documentos suelen representarse como vectores de alta dimensión, como los vectores TF, y la distancia euclidiana se puede utilizar para medir la disimilitud entre ellos. Una menor distancia euclidiana indica un mayor grado de similitud entre los documentos. ^{[ 14 ]} El uso de la distancia euclidiana puede dar como resultado medoides que sean más representativos de la longitud de un documento.

Editar distancia

La distancia de edición, también conocida como distancia de Levenshtein , mide la similitud entre dos cadenas de texto calculando el número mínimo de operaciones (inserciones, eliminaciones o sustituciones) necesarias para transformar una cadena en la otra. En el contexto de los datos de texto, la distancia de edición se puede utilizar para comparar la similitud entre documentos de texto cortos o palabras individuales. Una menor distancia de edición indica un mayor grado de similitud entre las cadenas. ^{[ 15 ]}

Aplicaciones de Medoid en modelos de lenguaje extensos

Medoides para analizar grandes incrustaciones de modelos de lenguaje.

Los medoides pueden emplearse para analizar y comprender las representaciones del espacio vectorial generadas por grandes modelos de lenguaje (LLM), como BERT, GPT o RoBERTa. Al aplicar la agrupación basada en medoides a las incrustaciones producidas por estos modelos para palabras, frases u oraciones, los investigadores pueden explorar las relaciones semánticas capturadas por los LLM. Este enfoque puede ayudar a identificar grupos de entidades semánticamente similares, proporcionando información sobre la estructura y organización de los espacios de incrustación de alta dimensión generados por estos modelos. ^{[ 16 ]}

Medoides para la selección de datos y el aprendizaje activo

El aprendizaje activo implica seleccionar puntos de datos de un conjunto de entrenamiento que maximicen el rendimiento del modelo. Los medoides pueden desempeñar un papel crucial en la selección de datos y el aprendizaje activo con modelos lineales de aprendizaje (MLA). La agrupación basada en medoides se puede utilizar para identificar muestras representativas y diversas de un gran conjunto de datos de texto, que luego se pueden emplear para ajustar los MLA de manera más eficiente o para crear mejores conjuntos de entrenamiento. Al seleccionar medoides como ejemplos de entrenamiento, los investigadores pueden obtener un conjunto de entrenamiento más equilibrado e informativo, lo que potencialmente mejora la generalización y la robustez de los modelos ajustados. ^{[ 17 ]}

Medoides para la interpretabilidad y seguridad del modelo

La aplicación de medoides en el contexto de los modelos lineales logarítmicos (MLL) puede contribuir a mejorar la interpretabilidad del modelo. Al agrupar las incrustaciones generadas por los MLL y seleccionar medoides como representantes de cada grupo, los investigadores pueden proporcionar un resumen más interpretable del comportamiento del modelo. ^{[ 18 ]} Este enfoque puede ayudar a comprender el proceso de toma de decisiones del modelo, identificar posibles sesgos y descubrir la estructura subyacente de las incrustaciones generadas por los MLL. A medida que el debate sobre la interpretabilidad y la seguridad de los MLL se intensifica, el uso de medoides puede ser una herramienta valiosa para lograr este objetivo.

Como método de agrupamiento versátil, los medoides pueden aplicarse a diversos problemas del mundo real en numerosos campos, desde la biología y la medicina hasta la publicidad, el marketing y las redes sociales. Su capacidad para manejar conjuntos de datos complejos con un alto grado de complejidad lo convierte en una herramienta poderosa en el análisis de datos actual.

• Vídeo de StatQuest k-means utilizado como referencia visual en la sección #Visualization_of_the_medoid-based_clustering_process