Objetivo de Dasgupta

En el estudio de agrupamiento jerárquico, el objetivo de Dasgupta es una medida de la calidad de una agrupación, definida a partir de una medida de similitud de los elementos a agrupar. Lleva el nombre de Sanjoy Dasgupta, quien lo formuló en 2016. ^[1]​ La propiedad clave es que, cuando la similitud proviene de un espacio ultramétrico, la agrupación óptima para esta medida de calidad sigue la estructura subyacente del espacio ultramétrico. En este sentido, se puede esperar que los métodos de agrupamiento que producen buenos agrupamientos para este objetivo se aproximen a la verdad básica subyacente a la medida de similitud dada. ^[2]​

En la formulación de Dasgupta, el argumento en un problema de agrupamiento consiste en puntajes de similitud entre ciertos pares de elementos, representados como un grafo no dirigido . ${\displaystyle G=(V,E)}$, con los elementos como sus vértices y con las similitudes como pesos reales no negativos en sus aristas. Los pesos grandes indican elementos que deben considerarse más similares entre sí, mientras que los pesos pequeños o los bordes faltantes indican pares de elementos que no son similares. Un agrupamiento jerárquico se puede describir como un árbol (no necesariamente un árbol binario) cuyas hojas son los elementos que se agruparán; los grupos son entonces los subconjuntos de elementos que descienden de cada nodo del árbol, y el tamaño ${\displaystyle |C|}$ de cualquier agrupación ${\displaystyle C}$ es su número de elementos. Para cada arista ${\displaystyle uv}$ del grafo de entrada, sea ${\displaystyle w(uv)}$ el peso de la arista ${\displaystyle uv}$ y sea ${\displaystyle C(uv)}$ el grupo más pequeño de una agrupación que contiene tanto a ${\displaystyle u}$ como a ${\displaystyle v}$ . Dasgupta define el costo de un agrupamiento como ^[1]​

${\displaystyle \sum _{uv\in E}w(uv)\cdot |C(uv)|.}$

El agrupamiento óptimo para este objetivo es NP-difícil de encontrar. Sin embargo, es posible encontrar un agrupamiento que se aproxime al valor mínimo del objetivo en tiempo polinomial mediante un algoritmo de agrupamiento divisivo (de arriba hacia abajo) que subdivide repetidamente los elementos utilizando un algoritmo de aproximación para el problema de corte más disperso, el problema de encontrar un partición que minimiza la relación entre el peso total de las aristas cortadas y el número total de aristas cortadas. ^[1]​ De manera equivalente, con fines de aproximación, se puede minimizar la relación entre el peso total de las aristas cortadas y el número de elementos en el lado más pequeño del corte. Usando la mejor aproximación conocida para el problema de corte más disperso, la relación de aproximación de este enfoque es ${\displaystyle O({\sqrt {\log n}})}$ . ^[3]​