| dbo:abstract
|
- In the study of hierarchical clustering, Dasgupta's objective is a measure of the quality of a clustering, defined from a similarity measure on the elements to be clustered. It is named after Sanjoy Dasgupta, who formulated it in 2016. Its key property is that, when the similarity comes from an ultrametric space, the optimal clustering for this quality measure follows the underlying structure of the ultrametric space. In this sense, clustering methods that produce good clusterings for this objective can be expected to approximate the ground truth underlying the given similarity measure. In Dasgupta's formulation, the input to a clustering problem consists of similarity scores between certain pairs of elements, represented as an undirected graph , with the elements as its vertices and with non-negative real weights on its edges. Large weights indicate elements that should be considered more similar to each other, while small weights or missing edges indicate pairs of elements that are not similar. A hierarchical clustering can be described as a tree (not necessarily a binary tree) whose leaves are the elements to be clustered; the clusters are then the subsets of elements descending from each tree node, and the size of any cluster is its number of elements. For each edge of the input graph, let denote the weight of edge and let denote the smallest cluster of a given clustering that contains both and . Then Dasgupta defines the cost of a clustering to be The optimal clustering for this objective is NP-hard to find. However, it is possible to find a clustering that approximates the minimum value of the objective in polynomial time by a divisive (top-down) clustering algorithm that repeatedly subdivides the elements using an approximation algorithm for the sparsest cut problem, the problem of finding a partition that minimizes the ratio of the total weight of cut edges to the total number of cut pairs.Equivalently, for purposes of approximation, one may minimize the ratio of the total weight of cut edges to the number of elements on the smaller side of the cut. Using the best known approximation for the sparsest cut problem, the approximation ratio of this approach is . (en)
- 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. 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 subyacente a la medida de similitud dada. 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 . , 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 de cualquier agrupación es su número de elementos. Para cada arista del grafo de entrada, sea el peso de la arista y sea el grupo más pequeño de una agrupación que contiene tanto a como a . Dasgupta define el costo de un agrupamiento como 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 , 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. 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 . (es)
|
| rdfs:comment
|
- In the study of hierarchical clustering, Dasgupta's objective is a measure of the quality of a clustering, defined from a similarity measure on the elements to be clustered. It is named after Sanjoy Dasgupta, who formulated it in 2016. Its key property is that, when the similarity comes from an ultrametric space, the optimal clustering for this quality measure follows the underlying structure of the ultrametric space. In this sense, clustering methods that produce good clusterings for this objective can be expected to approximate the ground truth underlying the given similarity measure. (en)
- 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. 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 subyacente a la medida de similitud dada. (es)
|
