Vektorový model

Dokumentografické informační systémy (DIS) se od sebe liší v paradigmatech, na kterých je postaveno vyhledávání rele...


Dokumentografické informační systémy (DIS) se od sebe liší v paradigmatech, na
kterých je postaveno vyhledávání relevantních dokumentů, tj., jak jsme uvedli v
minulé Databázové abecedě, v databázovém modelu. Nejstarším a v současnosti
nejrozšířenějším modelem textové databáze je model Boolský. Teoretické základy
odpovídajících DIS byly navrženy již v 50. letech. V současné době jsou hlavním
nástrojem i známých "vyhledávacích strojů" na Internetu, jako je AlstaVista,
HotBot a další. Je zajímavé a pro informatika poněkud překvapující, že v těchto
nástrojích se Boolský model zahrnuje pod tzv. pokročilé vyhledávání, přestože
jde o zcela běžný a známý způsob práce.
Každý dokument, uložený v primárním souboru, je identifikován množinou termů
(deskriptorů), které mu byly přiřazeny indexátorem. Dotazem se rozumí
posloupnost termů (deskriptorů), pospojovaných logickými operátory OR
(disjunkce), AND (konjunkce), operátorem NOT (negace) a závorkami. Dotazem je
tedy např. logický výraz "databáze" AND NOT "osobní počítače" OR "zpracování
textu".
Odpovědí na dotaz jsou ty dokumenty, jejichž popis splňuje zadanou podmínku.
Častým rozšířením boolského modelu je povolení použití zástupných znaků
(wildcards) ,* a ,? v termech dotazu. Závorky zpřehledňují syntaxi, často
však nejsou nutné díky precedenčním pravidlům. Naopak některé vyhledávající
stroje vyžadují (těžko říci proč) důsledné závorkování každé aplikace
příslušného operátoru. Např. A AND B AND C je třeba zapsat jako ((A AND B) AND
C).
Ač jde o jednoduchý princip, narážejí Boolské DIS při praktickém použití i na
řadu problémů: lPokládání efektivních dotazů, tj. dotazů, které vyberou z
databáze co nejvíce relevantních dokumentů při potlačení výstupu dokumentů
nerelevantních, vyžaduje jisté zkušenosti, často i znalost databáze.
lPři konjunktivním dotazu jsou zamítnuty dokumenty, které neobsahují jeden z
termů, stejně jako dokumenty, které neobsahují žádný z uvedených termů.
lPři disjunktivním dotazu jsou vybrány dokumenty, které obsahují jeden z termů,
stejně jako dokumenty, které obsahují všechny uvedené termy.
lVšechny dokumenty na výstupu jsou systémem chápány jako stejně dobré. Uživatel
by však chtěl dokumenty setříděné tak, aby na začátku byly "ty nejlepší"
dokumenty.
Metoda reprezentace dat pomocí vektorového modelu je přibližně o 20 let mladší
než předchozí. Hlavním rysem vektorového modelu je reprezentace záznamů,
reprezentujících dokumenty, a uživatelských dotazů pomocí vektorů.
Představme si, že se pohybujeme v databázi, kde množina termů T, podle kterých
se vyhledává,
se skládá z termů "databáze", "term", "koeficient přesnosti", "koeficient
úplnosti", "zpracování textu". Nechť databáze obsahuje tři záznamy (texty)
obsahující termy:
(1) databáze, term, koeficient úplnosti,
(2) koeficient úplnosti, koeficient přesnosti,
(3) databáze, zpracování textu
Reprezentace těchto záznamů pomocí vektorů je:
(1,1,1,0,0)
(0,0,1,1,0)
(1,0,0,0,1)
kde 1, resp. 0 sděluje fakt, že daný term z T existuje, resp. neexistuje v
záznamu. Uvažujme dotaz na dokumenty s termy "databáze" a "zpracování textu".
Jeho vektor bude (1,0,0,0,1). Vyzkoušíme-li v Boolském stylu dotaz (konjunkce)
vzhledem k záznamům, zjistíme, že dokument (3) je hitem. Zajímavý však může být
i dokument (1), obsahuje term "databáze", dokument (2) je zřejmě nerelevantní.
Tato fakta lze též zjistit ekvivalentním způsobem, vynásobíme-li vektor dotazu
skalárně s vektory databáze, tj. např. (1,1,1,0,0)Ň(1,0,0,0,1) = 1. Postupným
provedením tří součinů obdržíme čísla 1, 0, 2 a můžeme tedy seřadit dokumenty
do pořadí (3), (1), (2).
Když budeme udržovat pro jednotlivé dokumenty počty výskytů jejich termů v
rámci dokumentu, získáme jednoduchý systém vážení. Např. pro dokument (1) by
mohl vypadat vektor vah jako (3,0,0,0,2). Aplikací skalárního součinu s
vektorem dotazu bychom obdrželi číslo 5. Je vidět, že tato čísla již
nevyjadřují jednoduše shodu termů dotazu s termem v dokumentu, ale něco víc,
jaké-si kvantitativní ohodnocení míry podobnosti dokumentu s dotazem. Pro
relevanci by totiž mohlo být významné, že daný term se vyskytuje v dokumentu
vícekrát než druhý term. Tato idea je základem vektorového modelu.
Předpokládejme, že pro indexaci všech dokumentů v databázi bylo použito celkem
n různých termů t1...tn, potom každý dokument Di ze souboru dokumentů D je
reprezentován vektorem
Di = (wi1,wi2, ...,win),
kde wij?<0;1> n,
kde wij je váha náležející termu tj v identifikaci dokumentu Di. Váha wij
ohodnocuje důležitost jednotlivých termů pro identifikaci dokumentu podle
obsahu. Váha rovna 0 představuje nejnižší důležitost, váha rovna 1 pak
důležitost nejvyšší.
Soubor dokumentů D je ve vektorovém modelu popsán maticí D,
ve které i-tý řádek odpovídá
i-tému dokumentu, a j-tý sloupec j-tému termu z množiny T.
Dotaz Q je možné formulovat jako n-místný vektor vah
Q = (q1, q2, ..., qn), kde qj?0;1>.
Na základě dotazu Q lze pro každý dokument Di spočítat tzv. koeficient
podobnosti (angl. similarity). Tento koeficient si lze představit jako
"vzdálenost" vektoru dokumentu od vektoru dotazu ve vektorovém prostoru <0;1>n.
Pro výpočet podobnosti dokumentu Di vzhledem k dotazu Q se používá řada vzorců.
V nejjednodušším případě může být koeficient podobnosti definován vztahem
(a) Sim(Q,Di) = Sk=1,..,n(qk * wik)
nebo
(b) Sim(Q,Di) = Sk=1,..,n(qk * wik)/S÷(Sk=1,..,n(wik)2 * Sk=1,..,n(qk)2)
Druhému ze vztahů se říká kosinová míra. V praxi není míra (a) příliš
využívána. Nebere totiž do úvahy žádnou normalizaci vektorů v databázi.
Vyhodnocení dotazu ve vektorovém modelu je proces, který vybírá záznamy a
předkládá je uživateli podle snižujícího se SIM. To současně umožňuje řídit
výstup, tj. uživatel dostává nejprve ty "nejrelevantnější" záznamy. Namísto
upřesňování dotazu přidáváním dalších Boolských operátorů (a termů), mění se
váhy termů v dotazu, případně se i vylaďují váhy termů v matici D.
Všimněme si, že když všechny nenulové váhy ve vektorech nahradíme jedničkami,
tak se dostaneme do Boolských systémů. Dotaz Q pak představuje disjunkci termů,
koeficienty podobnosti udávají počet termů v Di, které se shodují s některými
termy v dotazu Q.
DIS, založený na vektorovém modelu, vyhodnocuje koeficienty podobnosti pro
jednotlivé záznamy a předkládá je uživateli v pořadí, určeném snižující se
hodnotou koeficientu podobnosti.
Oproti Boolským systémům umožňují triviálně řešit problém řízení výstupu. Pro
omezení množství výstupních dokumentů má uživatel 2 možnosti. Může předepsat
maximální přípustný počet záznamů, který je ochoten akceptovat, případně
stanovit spodní prahovou hodnotu koeficientu podobnosti dokumentů, nad níž jsou
ještě dokumenty považovány za relevantní.
Při ladění dotazu uživatel může, kromě přidávání a ubírání termů, měnit hodnoty
vah (významnosti) termů pro určení hledaných dokumentů.
Ve vektorovém modelu nelze rozlišit konjunktivní a disjunktivní dotaz.
Realizace operace NOT v pravém slova smyslu (tj. vyber dokumenty, které
neobsahují term "term") je ve vektorovém modelu špatně implementovatelná. Do
jisté míry lze tuto operaci nahradit rozšířením standardního modelu, kdy pro
váhy termů v dotazu použijeme interval <-1;1> místo obvyklého intervalu <0;1>.
Záporné číslo qj potom úměrně snižuje podobnost dotazu vůči dokumentu, který je
j-tým termem identifikován.
Určování vah
Většina automatických způsobů indexování je založena na pozorování, že
významnost termů pro indexování přímo souvisí s frekvencí výskytu termu v
dokumentu. Frekvence termu v dokumentu je číslo, které udává počet výskytů
termu v dokumentu. Frekvenci termu tj v dokumentu Di označíme symbolem TFij.
Samotná TF ještě nezajišťuje kvalitní výsledky informačního systému. Je nutné
vzít do úvahy také frekvenci, s jakou se daný term vyskytuje v celé kolekci
dokumentů, neboť nejvhodnějšími termy jsou ty, které se vyskytují zhruba v
polovině všech dokumentů. Proto se frekvence termu v dokumentu obvykle násobí
opravnými koeficienty.
Jedna z používaných metod využívá tzv. frekvenci podle invertovaného dokumentu
(IDF). IDF pro term t klesá se zvyšujícím se počtem dokumentů, ke kterým je
term t přiřazen.
IDF je definován předpisem
IDFj = log(m/kj) + 1
kde m je celkový počet dokumentů v kolekci a kj je počet dokumentů, ke kterým
je term tj přiřazen.
Váha termu tj v dokumentu je Di tedy tvořena součinem
wij = TFij * IDFj,
Další otázkou je, jak určit váhy dotazu qk. Salton a Buckley v roce 1988
shrnuli 20leté experimentování s vektorovým modelem a vyzkoušeli 287 různých
možností přiřazování vah termům v dokumentu a termům v dotazu. Vedle kosinové
míry pro koeficient SIM a vah termů pomocí TF a IDF se ukázal jako nejvhodnější
následující výpočet vah termů v dotazu:
qk = (0,5 + (0,5* TFk)/maxTF) * IDFk
kde TFk je frekvence termu tk v dotazu Q, maxTF je maximum z frekvencí dotazu a
IDFk je IDF termu tk v dané kolekci dokumentů. Zřejmě, je-li dotaz zadán pouze
množinou různých termů (bez frekvencí), je qk rovno přímo IDFk. Vzorec pro qk
se vlastně plně využije pro dotazy, které jsou zadány pomocí věty v přirozeném
jazyce, nebo obecněji pomocí dokumentu. Nic totiž nebrání v tom, zadat dotaz
tak, že použijeme relevantní dokument jako dotaz sám. To lze parafrázovat slovy
najdi k danému dokumentu Q všechny takové dokumenty D ze souboru, které mu jsou
podobné. Pro dlouhé dotazy, obsahující hodně výskytů termů, lze výpočet qk
aproximovat pouze pomocí TFk. Pro krátké dokumenty D zase stačí
váhy termů wij aproximovat jako 0 nebo 1, podle toho, zdali se v D term tij
vyskytuje nebo ne.
Třebaže se vektorovým modelům vytýká, že předpokladem jejich dobré funkce je
nezávislost termů (což obvykle není splněno), převyšují DIS na nich založené v
provozu klasické Boolské systémy. Uvádějí se příklady zvýšení koeficientu
přesnosti i o více než 100 %.
Přestože i vektorový model je ideově starší technika, praxe s rozsáhlými
textovými systémy ukázala, že se vyplatí se jím zabývat. Vážení termů a
setřídění výstupu podle relevance je dnes u vyhledávacích mechanismů na
Internetu záležitost vysoce aktuální. Co je uživateli platné, je-li v odpovědi
1 000 dokumentů, které prohledáváme systematicky od prvního, přičemž ten
nejlepší je zrovna ten tisící. Použití vážení může tuto činnost pozitivně
ovlivnit, tj. uživatel má šanci efektivněji zpracovat nabízený výsledek.
8 0120 / or









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.