Rocchioův algoritmus - Rocchio algorithm - Wikipedia

The Rocchioův algoritmus je založen na metodě relevantní zpětná vazba nalezen v vyhledávání informací systémy, které vycházely z Systém SMART Information Retrieval System který byl vyvinut v letech 1960-1964. Stejně jako mnoho jiných vyhledávacích systémů byl i Rocchio zpětnovazební přístup vyvinut pomocí Vektorový vesmírný model. The algoritmus je založen na předpokladu, že většina uživatelů má obecnou představu o tom, které dokumenty by měly být označeny jako relevantní nebo nerelevantní.^[1] Proto je vyhledávací dotaz uživatele revidován tak, aby obsahoval libovolné procento relevantních a nerelevantních dokumentů jako prostředek ke zvýšení vyhledávač je odvolání a případně také přesnost. Počet relevantních a nerelevantních dokumentů, které lze zadat a dotaz je dán váhami proměnných a, b, c uvedených níže v Sekce algoritmu.^[1]

Algoritmus

The vzorec a definice proměnných pro zpětnou vazbu o důležitosti Rocchio jsou následující:^[1]

${ displaystyle { overrightarrow {Q_ {m}}} = { bigl (} a cdot { overrightarrow {Q_ {o}}} { bigr)} + { biggl (} b cdot { tfrac { 1} {| D_ {r} |}} cdot sum _ {{ overrightarrow {D_ {j}}} v D_ {r}} { overrightarrow {D_ {j}}} { biggr)} - { biggl (} c cdot { tfrac {1} {| D_ {nr} |}} cdot sum _ {{ overrightarrow {D_ {k}}} v D_ {nr}} { overrightarrow { D_ {k}}} { biggr)}}$

Variabilní	Hodnota
${ displaystyle { overrightarrow {Q_ {m}}}}$	Upravený vektor dotazu
${ displaystyle { overrightarrow {Q_ {o}}}}$	Původní dotaz vektor
${ displaystyle { overrightarrow {D_ {j}}}}$	Vektor souvisejícího dokumentu
${ displaystyle { overrightarrow {D_ {k}}}}$	Vektor nesouvisejícího dokumentu
${ displaystyle a}$	Původní váha dotazu
${ displaystyle b}$	Hmotnost souvisejících dokumentů
${ displaystyle c}$	Hmotnost nesouvisejících dokumentů
${ displaystyle D_ {r}}$	Sada souvisejících dokumentů
${ displaystyle D_ {nr}}$	Sada nesouvisejících dokumentů

Jak je ukázáno ve vzorci, související váhy (A, b, C) jsou odpovědní za formování upravených vektor ve směru blíže nebo dále od původního dotazu, souvisejících dokumentů a nesouvisejících dokumentů. Zejména hodnoty pro b a C by měly být zvýšeny nebo sníženy proporcionálně k sadě dokumentů klasifikovaných uživatelem. Pokud se uživatel rozhodne, že upravený dotaz by neměl obsahovat výrazy z původního dotazu, souvisejících dokumentů nebo nesouvisejících dokumentů, pak odpovídající váha (A, b, C) hodnota pro kategorii by měla být nastavena na 0.

V pozdější části algoritmu proměnné ${ displaystyle D_ {r}}$ , a ${ displaystyle D_ {nr}}$ jsou prezentovány jako sady vektory obsahující souřadnice souvisejících dokumentů a nesouvisejících dokumentů. Ačkoli ${ displaystyle D_ {r}}$ a ${ displaystyle D_ {nr}}$ nejsou samy vektory, ${ displaystyle { overrightarrow {Dj}}}$ a ${ displaystyle { overrightarrow {Dk}}}$ jsou vektory používané k iteraci dvěma sadami a formování vektoru shrnutí. Tyto částky jsou normalizovány (děleny) podle velikosti jejich příslušné sady dokumentů ( ${ displaystyle D_ {r}}$ , ${ displaystyle D_ {nr}}$ ).

Chcete-li vizualizovat změny, ke kterým dochází na upraveném vektoru, podívejte se na obrázek níže.^[1] Jak se váhy pro konkrétní kategorii dokumentů zvyšují nebo snižují, souřadnice upraveného vektoru se začínají pohybovat buď blíže, nebo dále od těžiště sbírky dokumentů. Pokud se tedy zvýší váha souvisejících dokumentů, pak upravených vektorů souřadnice bude odrážet blíže k těžišti souvisejících dokumentů.

Časová složitost

Variabilní	Hodnota
${ displaystyle mathbb {D}}$	Sada označených dokumentů
${ displaystyle L_ {ave}}$	Průměrný počet žetonů na dokument
${ displaystyle mathbb {C}}$	Sada tříd
${ displaystyle V}$	Slovník / sada termínů
${ displaystyle L_ {a}}$	Počet tokenů v dokumentu
${ displaystyle M_ {a}}$	Počet typů v dokumentu

The časová složitost pro trénink a testování algoritmu jsou uvedeny níže a následuje definice každého z nich proměnná. Všimněte si, že ve fázi testování lze časovou složitost snížit na výpočet euklidovská vzdálenost mezi třídou těžiště a příslušný dokument. Jak ukazuje: ${ displaystyle Theta ( vert mathbb {C} vert M_ {a})}$ .

Školení = ${ displaystyle Theta ( vert mathbb {D} vert L_ {ave} + vert mathbb {C} vert vert V vert)}$
Testování = ${ displaystyle Theta (L_ {a} + vert mathbb {C} vert M_ {a}) = Theta ( vert mathbb {C} vert M_ {a})}$ ^[1]

Používání

Rocchio klasifikace

Přestože hodnocení dokumentů jako nerelevantní má výhody, a relevantní výsledkem hodnocení dokumentů bude uživateli zpřístupnění přesnějších dokumentů. Proto tradiční hodnoty pro váhy algoritmu (A, b, C) v Rocchio klasifikace jsou obvykle kolem a = 1, b = 0,8, a c = 0,1. Moderní vyhledávání informací systémy se posunuly k eliminaci nesouvisejících dokumentů nastavením c = 0 a tedy pouze zaúčtování souvisejících dokumentů. I když ne všichni vyhledávací systémy eliminovali potřebu nesouvisejících dokumentů, většina omezila účinky na upravený dotaz pouze tím, že zohlednila nejsilnější nesouvisející dokumenty v Dnr soubor.

Omezení

Algoritmus Rocchio často nedokáže klasifikovat multimodální třídy a vztahy. Například země Barma byl přejmenován na Myanmar v roce 1989. Proto se dva dotazy „Barma“ a „Myanmar“ objeví mnohem dále od sebe v vektorový vesmírný model, ačkoli oba mají podobný původ.^[1]

Viz také

Nejbližší klasifikátor těžiště, aka Rocchio klasifikátor

Reference

^ ^A ^b ^C ^d ^E ^F Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze: Úvod do získávání informací, strana 163-167. Cambridge University Press, 2009.

[ir-manning-1] A ^b ^C ^d ^E ^F Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze: Úvod do získávání informací, strana 163-167. Cambridge University Press, 2009.

[1]