Divergència d'una línia de base aleatòria

La divergència d'una línia de base aleatòria és una tècnica per a l'avaluació de l'agrupació de documents. Garanteix mesures de qualitat, quan el treball realitzat són agrupacions ineficaces de donar puntuacions més altes per a agrupaments que no proporcionen cap resultat útil.

Figura 1: Un agrupament produït per l'algorisme Clustering

Figura 2: Una línia de base aleatòria

Aquests conceptes es defineixen i s'analitzen utilitzant mètodes intrínsecs i extrínsecs a l'avaluació de l'agrupació de documents. Això inclou als grups clàssics d'enfocaments de categories i un enfocament nou que s'utilitza en la recuperació de la informació.

La divergència d'una línia de base aleatòria és capaç de diferenciar agrupacions ineficaces i agrupar-les. També realitza una normalització similar a la mesura d'informació mútua normalitzada (NMI).

Per a què serveix

Moltes mesures d'un agrupament poden donar puntuacions més altes que per a altres solucions d'agrupament, aquestes puntuacions altes són a causa del canvi del nombre de grups o del nombre documents en els agrupaments. Les mesures que fan que un agrupament sigui ineficaç poden ser ajustades, fent una agrupació generada aleatòriament amb el mateix nombre de grups i amb el mateix nombre de documents en cada agrupament.

Les figures 1 i 2 destaquen aquest exemple, en que cada línia de base aleatòria distribueix documents en grups de la mateixa mida, igual que els grups realitzats per l'algorisme clustering. A més de l'assignació aleatòria de documents en grups, la línia de base aleatòria apareix igual que a la solució real. Per tant cada agrupació avaluada requereix una línia de base aleatòria que és específica per a cada agrupació.

La línia de base és creada per barrejar els documents de manera uniforme a l'atzar i dividir-los en grups de la mateixa mida de l'agrupació que s'està mesurant. La puntuació per a l'agrupació aleatòria de línia de base es resta de l'agrupació que s'està mesurant.

Quan s'aplica

La divergència d'una línia de base aleatòria es pot aplicar a qualsevol mesura d'agrupament de qualitat, només si la qualitat de l'agrupament és intrínseca o extrínseca. No obstant això, es requereix una mesura existent d'agrupament de qualitat, per a prendre-la com a base.

No és una mesura per si mateix, sinó un enfocament per assegurar que un agrupament s'està realitzant de forma correcta. Tot i que pot ser utilitzat per a qualsevol tipus d'avaluació d'agrupacions.

Qüestions a tractar abans de l'aplicació

Hi ha dos qüestions a tractar a l'hora d'aplicar la tècnica d'avaluació de la divergència d'una línia de base aleatòria.

En primer lloc, les diferents mides dels agrupaments poden provocar qualificacions arbitràriament altes. Per tant, s'ha de tenir en compte al realitzar aquest mètode d'avaluació les mides de les agrupacions, s'ha d'intentar que les agrupacions siguin d'un nombre semblant.

I en segon lloc, s'ha de determinar que l'algorisme d'agrupament es realitza a partir de l'aprenentatge de manera efectiva, per a una mesura de qualitat. La divergència d'una línia de base aleatòria s'encarrega de les solucions que no són bones. Si l'ordenament dels agrupaments no són millors que el soroll aleatori, aconsegueixen una puntuació 0. Una puntuació negativa s'aconsegueix quan les puntuacions a l'atzar d'un valor positiu, és utilitzat per a la majoria de les mesures del conjunt de dades, és a dir, quan fem ús d'una manera reiterada d'un valor per a gran part de les mesures, ens dona una puntuació negativa.

Com s'aplica

Sent ω = {w1, w2,.. ., wK } les agrupacions de documents de la col·lecció D i ξ = {c1, c2,.. ., cJ } les diferents categories. Cada agrupació i categoria és un subgrup de la col·lecció.

∀c∈ξ,w∈ω∶ c,w ⊂D

Es defineix la probabilitat d'una categoria en una línia base donada com una agrupació, P_b (c_j│w_k)= (|c_j |)/(∑_i*c_i). La probabilitat d'una categoria donada a una agrupació en la línia base només depèn de les diferents categories. La línia base és una aleatorització uniforme d'una llista de documents que ha estat dividida en agrupacions les quals coincideixen amb la distribució del nombre d'elements de les agrupacions de la solució avaluada. És a dir, en cada agrupació de la línia base hi ha un soroll uniforme, aquest no depèn de la representació del document. conseqüentment, és d'esperar que la probabilitat d'aparició de cada una de les categories serà proporcional al nombre d'elements de cada una.

Per exemple si tenim tres categories: A, B, C amb un nombre d'elements 10, 20, 30 respectivament, s'espera que cada una de les agrupacions en la línia base contingui aproximadament 10/60 A, 20/60 B i 30/60 C. Aquestes només reflecteixen la distribució del nombre d'elements en cada categoria.

Interpretarem qualsevol mesura com una probabilitat, tot i que formalment no és el cas per a totes elles, ens serveix com a explicació. Definim la probabilitat d'una categoria en una agrupació donada pel terreny veritat com a: P_s (c_j│w_k) = qualsevol mesura de qualitat.

La mesura de Puresa assigna una probabilitat a cada agrupació quan no hi ha una única categoria de terreny veritat. El sumatori de totes les probabilitats combinades és igual a u; ∑_j*(|c_j ∩ w_k |)/(|w_k|)=1 i a cada agrupació se li assigna la categoria amb la màxima semblança estimada, P_Puresa (c_j│w_k)= argmax_cj* (|c_j ∩ w_k |)/(|w_k|). Aquesta és la proporció de l'agrupació que té la majoria d'etiquetes de la categoria corresponent. Quan es disposa d'una mostra desconeguda i la classifiquem mitjançant agrupacions amb dades etiquetades, utilitzant com a referència l'etiqueta de l'agrupació més propera. Definim d com un document de D. El terreny veritat es restringeix per tal d'obtenir una sola etiqueta; un document d, només té una etiqueta en una categoria del terreny veritat, ∀d ∈D,c_i ∈ ξ,c_j ∈ ξ∶d∈ c_i ∧d ∉ c_(j) ∧ c_i ≠ c_j.

La mesura ajustada és la diferència següent P_a (c_j│w_k)=P_s (c_j│w_k)-P_b (c_j│w_k)

Bibliografia

• De Vries, Christopher; Geva, Shlomo; Trotman, Andrew. Document Clustering Evaluation: Divergence from a Random Baseline (pdf) (en anglès) [Consulta: 25 novembre 2013].