Označování klastrů - Cluster labeling - Wikipedia

v zpracování přirozeného jazyka a vyhledávání informací, označení klastru je problém s výběrem popisných, člověkem čitelných štítků pro klastry produkované a shlukování dokumentů algoritmus; standardní klastrové algoritmy obvykle takové štítky neprodukují. Algoritmy označování klastrů zkoumají obsah dokumentů pro každý klastr, aby našli popis, který shrnuje téma každého klastru a odlišuje klastry od sebe navzájem.

Diferenciální označení klastrů

Diferenciální označení klastru označuje klastr porovnáním výrazu distribuce napříč klastry pomocí technik používaných také pro výběr funkcí v klasifikace dokumentů, jako vzájemné informace a chi-kvadrát výběr funkcí. Pojmy, které mají velmi nízkou frekvenci, nejsou nejlepší při reprezentaci celého klastru a lze je při označení klastru vynechat. Vynecháním těchto vzácných výrazů a použitím diferenciálního testu lze dosáhnout nejlepších výsledků s označováním diferenciálních klastrů.^[1]

Bodová vzájemná informace

V polích teorie pravděpodobnosti a teorie informace, vzájemná informace měří míru závislosti dvou náhodné proměnné. Vzájemná informace o dvou proměnných X a Y je definován jako:

${ displaystyle I (X, Y) = součet _ {x v X} { součet _ {y v Y} {p (x, y) log_ {2} left ({ frac {p (x , y)} {p_ {1} (x) p_ {2} (y)}} vpravo)}}}$

kde p (x, y) je společné rozdělení pravděpodobnosti ze dvou proměnných, p₁(X) je rozdělení pravděpodobnosti X a p₂(y) je rozdělení pravděpodobnosti Y.

V případě označení klastru je proměnná X spojena s členstvím v klastru a proměnná Y je spojena s přítomností termínu.^[2] Obě proměnné mohou mít hodnoty 0 nebo 1, takže rovnici lze přepsat takto:

${ displaystyle I (C, T) = součet _ {c v {0,1}} { součet _ {t v {0,1}} {p (C = c, T = t) log_ { 2} left ({ frac {p (C = c, T = t)} {p (C = c) p (T = t)}} right)}}}$

V tomto případě, p (C = 1) představuje pravděpodobnost, že náhodně vybraný dokument je členem konkrétního klastru, a p (C = 0) představuje pravděpodobnost, že tomu tak není. Podobně, p (T = 1) představuje pravděpodobnost, že náhodně vybraný dokument obsahuje daný termín, a p (T = 0) představuje pravděpodobnost, že tomu tak není. The společná funkce rozdělení pravděpodobnosti p (C, T) představuje pravděpodobnost, že dojde ke dvěma událostem současně. Například, p (0, 0) je pravděpodobnost, že dokument není členem klastru C a neobsahuje výraz t; p (0, 1) je pravděpodobnost, že dokument není členem klastru C a obsahuje výraz T; a tak dále.

Chi-čtvercový výběr

Pearsonův chí-kvadrát test lze použít k výpočtu pravděpodobnosti, že výskyt události odpovídá počátečním očekáváním. Zejména lze použít k určení, zda jsou dvě události, A a B. statisticky nezávislé. Hodnota chí-kvadrát statistiky je:

${ displaystyle X ^ {2} = součet _ {a v A} { součet _ {b v B} { frac {(O_ {a, b} -E_ {a, b}) ^ {2 }} {E_ {a, b}}}}}$

kde Ó_{a, b} je pozorováno frekvence společného výskytu aab, a E_{a, b} je očekávaný frekvence společného výskytu.

V případě označení klastru je proměnná A spojena s členstvím v klastru a proměnná B je spojena s přítomností termínu. Obě proměnné mohou mít hodnoty 0 nebo 1, takže rovnici lze přepsat takto:

${ displaystyle X ^ {2} = součet _ {a v {0,1}} { součet _ {b v {0,1}} { frac {(O_ {a, b} -E_ { a, b}) ^ {2}} {E_ {a, b}}}}}$

Například, Ó_1,0 je pozorovaný počet dokumentů, které jsou v konkrétním klastru, ale neobsahují určitý termín, a E_1,0 je očekávaný počet dokumentů, které jsou v konkrétním klastru, ale neobsahují určitý termín. Náš počáteční předpoklad je, že tyto dvě události jsou nezávislé, takže očekávané pravděpodobnosti společného výskytu lze vypočítat vynásobením jednotlivých pravděpodobností:^[3]

E_1,0 = N * P (C = 1) * P (T = 0)

kde N je celkový počet dokumentů ve sbírce.

Klastrové interní značení

Označení interního klastru vybírá štítky, které závisí pouze na obsahu zájmového klastru. S ostatními klastry se neprovádí žádné srovnání. Interní označování klastru může používat celou řadu metod, jako je hledání termínů, které se často vyskytují v těžišti, nebo hledání dokumentu, který leží nejblíže těžišti.

Centroid štítky

Často používaný model v oblasti vyhledávání informací je model vektorového prostoru, který představuje dokumenty jako vektory. Položky ve vektoru odpovídají podmínkám v slovní zásoba. Binární vektory mají hodnotu 1, pokud je výraz přítomen v konkrétním dokumentu, a 0, pokud chybí. Mnoho vektorů využívá váhy, které odrážejí význam termínu v dokumentu a / nebo důležitost termínu v kolekci dokumentů. Pro konkrétní shluk dokumentů můžeme vypočítat těžiště hledáním aritmetický průměr všech vektorů dokumentů. Pokud má položka ve vektoru těžiště vysokou hodnotu, pak se v klastru často vyskytuje odpovídající výraz. Tyto termíny lze použít jako označení pro cluster. Jednou z nevýhod používání těžiště označení je, že dokáže zachytit slova jako „místo“ a „slovo“, která mají v psaném textu vysokou frekvenci, ale mají malý význam pro obsah konkrétní klastr.

Kontextualizované štítky těžiště

Jednoduchým a nákladově efektivním způsobem překonání výše uvedeného omezení je vložení těžiště s nejvyšší váhou do struktury grafu, který poskytuje kontext pro jejich interpretaci a výběr.^[4]V tomto přístupu je termínová matice společného výskytu označována jako ${ displaystyle T_ {k}}$ je nejprve vytvořen pro každý klastr ${ displaystyle S_ {k}}$. Každá buňka představuje počet termínů ${ displaystyle i}$ vyskytuje se společně s termínem ${ displaystyle j}$ v určitém okně textu (věta, odstavec atd.) Ve druhé fázi matice podobnosti ${ displaystyle T_ {k} ^ {sim}}$ se získá vynásobením ${ displaystyle T_ {k}}$ s jeho transpozicí. My máme ${ displaystyle T_ {k} ^ {sim} = T_ {k} 'T_ {k} = (t _ {{sim} _ {ij}})}$. Být bodovým produktem dvou normalizovaných vektorů ${ displaystyle { tilde {t}} _ {i}}$ a ${ displaystyle { tilde {t}} _ {j}}$, ${ displaystyle t _ {{sim} _ {ij}}}$ označuje kosinovou podobnost mezi členy ${ displaystyle i}$ a ${ displaystyle j}$. Takto získané ${ displaystyle T_ {k} ^ {sim}}$ pak lze použít jako váženou matici sousedství grafu podobnosti výrazů. Centroidní výrazy jsou součástí tohoto grafu a lze je tedy interpretovat a skórovat kontrolou výrazů, které je v grafu obklopují.

Štítky nadpisů

Alternativou k označování těžišť je označování titulů. Zde najdeme dokument v klastru, který má nejmenší Euklidovská vzdálenost na těžiště a jeho název použít jako štítek klastru. Jednou z výhod používání názvů dokumentů je, že poskytují další informace, které by nebyly uvedeny v seznamu pojmů. Mají však také potenciál uvést uživatele v omyl, protože jeden dokument nemusí být reprezentativní pro celý klastr.

Štítky externích znalostí

Označování klastrů lze provést nepřímo pomocí externích znalostí, jako jsou předem kategorizované znalosti, jako je například Wikipedia.^[5] V takových metodách je sada důležitých textových funkcí klastru nejprve extrahována z dokumentů klastru. Tyto funkce lze potom použít k načtení (vážených) K-nejbližších kategorizovaných dokumentů, ze kterých lze extrahovat kandidáty na štítky klastrů. Posledním krokem je seřazení těchto kandidátů. Vhodné metody jsou takové, které jsou založeny na procesu hlasování nebo fúzi, který je určen pomocí sady kategorizovaných dokumentů a původních funkcí klastru.

Kombinace několika klastrových štítkovačů

Štítky klastrů několika různých štítkovačů klastrů lze dále kombinovat a získat tak lepší štítky. Například, Lineární regrese lze použít k osvojení optimální kombinace skóre štítkovače.^[6] Složitější technika je založena na a fúze přístup a analýza rozhodovacích schopností klastrových štítků různých štítkovačů.^[7]

externí odkazy

• Hierarchické shlukování
• Automaticky označovat hierarchické klastry

Reference