Rocchio algoritm

Rocchio -algoritmen är baserad på en metod för relevansåterkoppling som finns i informationshämtningssystem som härrörde från SMART Information Retrieval System som utvecklades mellan 1960 och 1964. Liksom många andra hämtningssystem utvecklades Rocchio- algoritmen med hjälp av vektorrymdmodellen . Dess underliggande antagande är att de flesta användare har en allmän uppfattning om vilka dokument som bör betecknas som relevanta eller irrelevanta. Därför revideras användarens sökfråga för att inkludera en godtycklig procentandel av relevanta och irrelevanta dokument som ett sätt att öka sökmotorns återkallelse , och möjligen även precisionen . Antalet relevanta och irrelevanta dokument som tillåts att ange en fråga bestäms av vikten av a-, b- och c-variablerna som anges nedan i avsnittet Algoritm .

Algoritm

Formeln och variabeldefinitionerna för Rocchio-relevansfeedback är följande :

${\vec {Q}}_{m}=a\,{\vec {Q}}_{o}+b\,{\frac {1} {|D_{r}|}}\summa _{{\vec {D}}_{j}\in D_{r}}{\vec {D}}_{j}-c\,{\frac { 1}{|D_{nr}|}}\summa _{{\vec {D}}_{k}\in D_{nr}}{\vec {D}}_{k}$

Variabel	Värde
${\vec {Q}}_{m}$	Modifierad frågevektor
${\vec {Q}}_{o}$	Ursprunglig fråga vektor
${\vec {D}}_{j}$	Relaterad dokumentvektor
${\vec {D}}_{k}$	Icke-relaterad dokumentvektor
$a$	Originalfrågans vikt
$b$	Relaterade dokument Vikt
$c$	Icke-relaterade dokument vikt
$D_{r}$	Uppsättning relaterade dokument
$D_{nr}$	Uppsättning icke-relaterade dokument

Som visas i formeln är de associerade vikterna (a, b, c) ansvariga för att forma den modifierade vektorn i en riktning närmare, eller längre bort, från den ursprungliga frågan, relaterade dokument och icke-relaterade dokument. I synnerhet bör värdena för b och c ökas eller minskas proportionellt mot den uppsättning dokument som klassificeras av användaren. Om användaren beslutar att den ändrade frågan inte ska innehålla termer från vare sig den ursprungliga frågan, relaterade dokument eller icke-relaterade dokument, ska motsvarande viktvärde (a, b, c) för kategorin sättas till 0.

I den senare delen av algoritmen presenteras variablerna $D_{r}$ och $D_{nr}$ som uppsättningar av vektorer som innehåller koordinaterna för relaterade dokument och icke-relaterade dokument. Även om $D_{r}$ och $D_{nr}$ inte är vektorer själva, ${\vec {D}}_{j}$ och ${\vec {D}}_{k}$ är vektorerna som används för att iterera genom de två uppsättningarna och bilda vektorsummor . Dessa summor är normaliserade (dividerade) med storleken på deras respektive dokumentuppsättning ( ${\displaystyle D_{r}} ,$ D $\displaystyle D_{nr}}$ ).

För att visualisera förändringarna som äger rum på den modifierade vektorn, se bilden nedan. När vikterna ökas eller minskas för en viss kategori av dokument, börjar koordinaterna för den modifierade vektorn att röra sig antingen närmare eller längre bort från dokumentsamlingens tyngdpunkt . Om sålunda vikten ökas för relaterade dokument, kommer de modifierade vektorkoordinaterna att återspegla att de ligger närmare tyngdpunkten för relaterade dokument.

Tidskomplexitet

Variabel	Värde
$\mathbb {D}$	Märkt dokumentuppsättning
$L_{ave$	Genomsnittliga tokens per dokument
$\mathbb {C}$	Klassuppsättning
$V$	Ordförråd/Termuppsättning
$L_{a}$	Antal tokens i dokumentet
$M_{a}$	Antal typer i dokument

Tidskomplexiteten för att träna och testa algoritmen listas nedan och följs av definitionen av varje variabel . Observera att i testfasen kan tidskomplexiteten reduceras till den för att beräkna det euklidiska avståndet mellan en klass tyngdpunkt och respektive dokument. Som visas av: $\Theta (\vert \mathbb {C} \vert M_{a})$ .

Träning = $\Theta (\vert \mathbb {D} \vert L_{ave}+\vert \mathbb {C} \vert \vert V\vert )$ Testning = $\Theta (L_{a}+\vert \mathbb {C} \vert M_{a })=\Theta (\vert \mathbb {C} \vert M_{a})$

Användande

Rocchio klassificering

Även om det finns fördelar med att rangordna dokument som icke-relevanta, kommer en relevant dokumentrankning att resultera i att mer exakta dokument görs tillgängliga för användaren. Därför är traditionella värden för algoritmens vikter (a, b, c) i Rocchio-klassificeringen typiskt runt a = 1, b = 0,8 och c = 0,1. Moderna för informationssökning har gått mot att eliminera de icke-relaterade dokumenten genom att sätta c = 0 och därmed endast redovisa relaterade dokument. Även om inte alla hämtningssystem har eliminerat behovet av icke-relaterade dokument, har de flesta begränsat effekterna på modifierade frågor genom att endast ta hänsyn till de starkaste icke-relaterade dokumenten i uppsättningen D $\displaystyle D_{nr}} .$

Begränsningar

Rocchio-algoritmen misslyckas ofta med att klassificera multimodala klasser och relationer. Till exempel döptes landet Burma om till Myanmar 1989. Därför kommer de två frågorna "Burma" och "Myanmar" att visas mycket längre ifrån varandra i vektorrymdmodellen, även om de båda har liknande ursprung.

Se även

Närmaste tyngdpunktsklassificerare , aka Rocchio-klassificerare