Etiquetado de clúster

El Etiquetado de Clúster está estrechamente relacionado con el agrupamiento de documentos. Este proceso intenta seleccionar etiquetas descriptivas para los grupos obtenidos a través de un algoritmo de clúster ya sea de Particionado de Clúster o Clúster Jerárquico. Por ejemplo, un grupo de documentos que hablen sobre varios protocolos de internet puede ser etiquetado como Protocolos de Internet. Generalmente las etiquetas se obtienen producto de analizar el contenido de los documentos pertenecientes al clúster. Una buena etiqueta no solo resume la idea central de los documentos agrupados sino que los diferencia de los otros clústeres.

En muchas aplicaciones de Particionado de Clúster o Clúster Jerárquico, particularmente en las tareas de análisis y en interfaces de usuario, los usuarios humanos interactúan con clústeres. En tales trasfondos, debemos etiquetar grupos, a fin de que los usuarios puedan ver de qué se trata un grupo. Los métodos de etiquetado de clústeres pueden clasificarse en: Diferenciales e Internos.

Etiquetado Diferencial de Clúster

Selecciona las etiquetas de un clúster mediante la comparación de los términos en un clúster con los términos que aparecen en otros clúster. Las técnicas utilizadas para la selección de características (feature selection) en recuperación de información también se puede aplicar al etiquetado diferencial de clúster, las más utilizadas son información mutua y chi-cuadrado. Términos que tienen baja frecuencia no son los mejores en la representación de todo el conjunto y se pueden omitir en el etiquetado de un clúster. Al omitir los términos poco usuales y usando una prueba diferencial, se pueden obtener mejores resultados en el etiquetado de clústeres

Algoritmo General

De manera general los algoritmos basados en Etiquetado Diferencial de Clúster siguen un patrón común que se basa en la selección de los k términos más útiles de un clúster como etiqueta para este. Señalar aquí que la definición de más útiles es la que hace particular un algoritmo respecto a otro. En el algoritmo general se define A(t,c) como la medida de utilidad del término t para la clase c.

1. SelectTerms(C,k);
2. V ⃪ ExtractTerms(C);
3. L ⃪ [];
4. foreach t ϵ V do
5. A(t,c) ⃪ ComputeUtility(t,c);
6. Append(L,< A(t,c),t >);
7. end
8. return TermsWithLargestValues(L,k);

Este algoritmo calcula una medida de utilidad A(t,C) para cada término t en el clúster C y selecciona los k términos del clúster que tienen los valores más altos de medida de utilidad A(t,C), todos los demás términos son descartados para seleccionar la etiqueta de C. Precisamente los algoritmos información mutua y chi-cuadrado test son variantes para calcular la utilidad A(t,c) de un término a un clúster

Información Mutua

En el campo de las probabilidades la información mutua da una medida del grado de dependencia entre dos variables aleatorias. La información mutua de dos variables X y Y está definida como:

$I(X,Y)=\sum _{x\in X}\sum _{y\in Y}p(x,y)\log \left({\frac {p(x,y)}{p_{1}(x)p_{2}(y)}}\right)\qquad (1)$

donde p(x,y) es la función de distribución de la probabilidad conjunta de las dos variables, p₁(x) es la función de distribución de X y p₂(y) es la función de distribución de Y .En el caso que nos ocupa, el etiquetado de clústeres, la variable X está asociada a la pertenencia de un documento a un clúster, y Y está asociada a la presencia de un término en un documento seleccionado al azar. Ambas variables pueden tomar valores {0,1}, en cuyo caso la ecuación puede ser reescrita como:

$I(C,T)=\sum _{c\in 0,1}\sum _{t\in 0,1}p(C=c,T=t)\log \left({\frac {p(C=c,T=t)}{p(C=c)p(T=t)}}\right)\qquad (2)$

En este caso, p(C =1) representa la probabilidad de que un documento seleccionado al azar pertenezca a un clúster en particular y p(C =0) la probabilidad de que no pertenezca, de forma similar p(T =1) es la probabilidad de que un documento seleccionado aleatoriamente contenga un término determinado y p(T =0) de que no lo contenga, p(C,T) es la probabilidad de que dos de los sucesos descritos anteriormente ocurran de manera simultánea, por ejemplo p(0,1) es la probabilidad de que un documento no sea miembro del clúster c y contenga al término t .

	Documentos en "comercio"	Documentos que no están en "comercio"
Documentos que contienen"tarifa"	60	10,000
Documentos que no contienen "tarifa"	200	500,000

Total de documentos = (60 + 200 + 10,000 + 500,000) = 510,260
P (C = 1, T = 1) = 60/510,260
P (C = 1, T = 0) = 200/510,260
P (C = 0, T = 1) = 10,000/510,260
P (C = 0, T = 0) = 500,000/510,260
P (C = 1) = (# documentos en el clúster) / (total de documentos) = (60 + 200) / 510,260 = 260/510,260
P (C = 0) = (# de documentos fuera del clúster) / (total de documentos) = (10,000 + 500,000) / 510,260 = 510,000/510,260
P (T = 1) = (# de documentos que contienen el término) / (total de documentos) = (60 + 10,000) / 510,260 = 10,060/510,260
P (T = 0) = (# de documentos que no contienen el término) / (total de documentos) = (200 + 500,000) / 510,260 = 500,200/510,260
Sustituyendo los valores en la ecuación (2) y calculando nos queda que:
I(C,T) = 0.000280655
Podemos calcular una etiqueta para el clúster "comercio" calculando I(C,T) para cada término y seleccionando los k que reporten los mayores valores de I.

Selección X² o Chi-cuadrado

La prueba X² puede ser usada para calcular la probabilidad de que la ocurrencia de un evento cumpla las expectativas iniciales. En particular se usa para determinar cuándo dos eventos probabilísticos A y B son estadísticamente independientes o sea P(AB)=P(A)P(B).

$\chi ^{2}=\sum _{a\in A}\sum _{b\in B}{\frac {(O_{a,b}-E_{a,b})^{2}}{E_{a,b}}}$

donde O_a,b es la frecuencia observada de a y b ocurriendo simultáneamente, y E_a,b es la frecuencia con que se espera que ocurran.

Para el caso particular de etiquetado de clústeres , A se asocia a la pertenencia de un documento a un clúster y B está asociada a la presencia de un término en un documento. Ambas variables pueden tomar valores {0,1} y la ecuación anterior se reescribe como:

$\chi ^{2}=\sum _{a\in 0,1}\sum _{b\in 0,1}{\frac {(O_{a,b}-E_{a,b})^{2}}{E_{a,b}}}$

Por ejemplo: O_1,0 es el número de documentos observados que se encuentran en un clúster específico y que no contienen cierto término. Como hipótesis inicial se asume que los dos eventos son independientes, por tanto la probabilidad de que ambos ocurran se calcula multiplicando las probabilidades individuales:
E_1,0 = N ∗ P(C =1) ∗ P(T =0)
siendo N es la cantidad de documentos en la colección.

Etiquetado interno de clúster

Etiquetado interno de clúster (Cluster-internal labeling) selecciona etiquetas que solo dependen de los contenidos del clúster de interés. No se hace comparación alguna con los otros clúster.El Etiquetado interno de clúster puede usar una variedad de métodos, tales como encontrar términos que ocurran frecuentemente en el centroide o encontrar el documento que queda más cercano al centroide.

Etiquetado de Centroides

Un modelo frecuentemente usado en el campo de la Recuperación de información es el modelo de espacio vectorial, el cual representa documentos como vectores. Las entradas en el vector corresponden a términos en el vocabulario. Los vectores binarios tienen valores de 1 si el término está presente dentro de un documento particular y 0 si está ausente. Muchos vectores hacen uso de pesos que reflejan la importancia de un término en una colección de documentos. Para un particular clúster de documentos, podemos calcular el centroide mediante encontrar la media aritmética de todos los vectores de documentos. Si una entrada en el vector centroide tiene un valor alto, entonces el término correspondiente ocurre frecuentemente dentro del clúster. Una desventaja de usar Etiquetado de Centroides (Centroid labeling) es que él puede escoger palabras como "place" y "word" que tienen una alta frecuencia en un texto escrito, pero también poca relevancia para los contenidos de un clúster particular.

Etiquetado de Títulos

Una alternativa para Etiquetado de Centroides es Etiquetado de Títulos (Title Labeling). Aquí, encontramos el documento dentro del clúster que tiene la distancia Euclidiana más pequeña hasta el centroide, y usamos su título como etiqueta para el clúster. Una desventaja al usar los títulos de los documentos es que ellos proveen información adicional que no estaría presente en una lista de términos. Sin embargo, ellos además tienen el potencial para desencaminar al usuario, ya que un documento podría ser no representativo de todo el clúster.

Etiquetado de Conocimiento Externo

El etiquetado de clústeres puede ser hecho indirectamente usando conocimiento externo (external knowledge) tal como conocimiento pre-categorizado. En tales métodos, un conjunto de importantes características textuales del clúster son primero extraídas del clúster de documentos. Estas características pueden ser usadas para recuperar los (pesados) K-mas_cercanos documentos categorizados de los cuales pueden ser extraídas los candidatos para etiquetas de clúster. El paso final envuelve el ranking de dichos candidatos. Métodos convenientes son aquellos que están basados en un proceso de votado o de fusión el cual es determinado usando el conjunto de documentos categorizados y las características originales del clúster.

Etiquetado Jerárquico de Clúster

Para el etiquetado jerárquico, surgen complicaciones adicionales en el etiquetado de clúster. No solo necesitamos distinguir un nodo interno en el árbol de sus hijos, sino también de su padre y los hijos de su padre. Los documentos en los nodos hijos son por definición también miembros de su nodo padre, o sea no podemos usar un método diferencial ingenuo para encontrar etiquetas que distingan al padre de sus hijos. Sin embargo, un criterio más complejo, basado en una combinación de frecuencia en el conjunto de la colección y prevalencia en un clúster dado, puede determinar si un término es una etiqueta más informativa para un hijo o para un nodo padre.

La organización jerárquica es popular porque representa la información a diferentes niveles de detalle y es conveniente para la exploración interactiva. Al tope de la jerarquía, la colección es organizada en unas pocas categorías generales: mientras una persona desciende en la jerarquía, ella consigue más detalle sobre la cada vez más específica categoría. Típicamente a cada documento le es asignado un descriptor que describe al documento que el contiene. Una meta las técnicas con clúster jerárquico es mejorar la habilidad de los usuarios para explorar la colección, así que es muy importante que la jerarquía tenga buenos descriptores de clúster. Estos descriptores pueden ser cualquiera de las etiquetas de categoría.

El Etiquetado Jerárquico de Clúster particiona una colección de documentos en un número más pequeño de clústeres, y cada clúster es luego particionado en sub-clústeres de manera recursiva. Los clústeres jerárquicos pueden ser construidos por métodos aglomérativos que empiezan con cada documento en su propio clúster y luego repetidamente agrupan clústeres similares en un clúster más abarcador, o por métodos divisivos que empiezan con todos los documentos en un clúster y luego repetidamente dividen cada clúster en sub-clústeres más detallados.

Cuando se etiquetan clústeres jerárquicos, uno asume la existencia de una jerarquía de clústeres de documentos. La tarea es asignar un buen descriptor a cada nodo clúster en la jerarquía. Los más comunes descriptores de clúster son o etiquetas concisas, o listas de términos y frases. Por ejemplo, un clúster de documentos sobre procesamiento de lenguaje natural puede ser descrito por la etiqueta “procesamiento de lenguaje natural” o la lista de términos “etiqueta, texto, lingüista, léxico, cuerpo, etiquetador, palabra, sintaxis, gramática.” Una lista de términos es frecuentemente menos útil que una simple etiqueta de categoría, porque requiere que el usuario infiera el concepto implicado por los términos. Sin embargo, una lista de términos es la opción más común para etiquetar automáticamente clústeres porque falla airosamente; una persona puede frecuentemente inferir la descripción general incluso cuando un poco de términos seleccionados son pobres opciones. Ha habido acercamientos a identificar etiquetas de clúster desde distribución de palabras en la jerarquía. Popescul propuso usar la prueba estadística χ2 para detector diferencia en la distribución de palabras a través de la jerarquía. En cada nodo clúster en la jerarquía, empezando desde la raíz, la prueba χ2 es usada para detectar un conjunto de palabras que es igualmente probable de ocurrir en alguno de los sub-clústeres del nodo actual. Esas palabras son consideradas términos no descriptivos para cada sub-clúster del nodo actual, y por tanto son removidas de cada sub-clúster. Después de que la prueba χ2 es usada para remover palabras no descriptivas de cada nodo clúster, el algoritmo etiqueta cada clúster con la lista de las restantes palabras en ese nodo ranqueadas por la frecuencia de la palabra.

Enlaces externos

• Hierarchical Clustering
• Automatically Labeling Hierarchical Clusters

Referencias

1. ^ Manning, Christopher D., Prabhakar Raghavan, and Hinrich Schutze. Introduction to Information Retrieval. Cambridge: Cambridge UP, 2008. Cluster Labeling. Stanford Natural Language Processing Group. Web. 25 Nov. 2009. <http://nlp.stanford.edu/IR-book/html/htmledition/cluster-labeling-1.html>.
2. ^ Manning, Christopher D., Prabhakar Raghavan, and Hinrich Schutze. Introduction to Information Retrieval. Cambridge: Cambridge UP, 2008. Mutual Information. Stanford Natural Language Processing Group. Web. 25 Nov. 2009. <http://nlp.stanford.edu/IR-book/html/htmledition/mutual-information-1.html>.
3. ^ Manning, Christopher D., Prabhakar Raghavan, and Hinrich Schutze. Introduction to Information Retrieval. Cambridge: Cambridge UP, 2008. Chi2 Feature Selection. Stanford Natural Language Processing Group. Web. 25 Nov. 2009. <http://nlp.stanford.edu/IR-book/html/htmledition/feature-selectionchi2-feature-selection-1.html>.
4. ^ David Carmel, Haggai Roitman, Naama Zwerdling. Enhancing cluster labeling using Wikipedia. SIGIR 2009: 139-146

• Datos: Q1096936

1. Manning, Christopher D. (2007). An Introduction to Information Retrieval. Cambridge University Press.