Vektorrom-modellen

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

Vektorrom-modellen også kjent som Term vektor-modellen er en algebraisk modell brukt for å representere tekst dokumenter (samt alle andre objekter) som vektorer bestående av identifikatorer, som for eksempel ved å bruke term vekt som parameter verdi. Modellen blir brukt blant annet innen informasjonsgjenfinning, indeksering, informasjonsfiltrering og relevansrangering.

Definisjoner[rediger | rediger kilde]

En term kan representere både ett nøkkelord og en lengre frase.

Dokumenter og spørringer kan bli representert som vektorer, ved å bruke en tallverdi som representerer termen som parameter.

Eksempel:

d_j = ( w_{1,j} ,w_{2,j} , \dotsc ,w_{t,j} )
q = ( w_{1,q} ,w_{2,q} , \dotsc ,w_{t,q} )

Hver term representerer en dimensjon innen vektorrommet, med andre ord har vektorrommet like mange dimensjoner som termer. Dette betyr at vektorrommet kan ha uendelige dimensjoner. Hvis termen finnes innen dokumentet kan verdien bli regnet og er dermed høyere enn null. Det finnes flere metoder for utregning av termvekt, hvorav en av de beste er vekting etter tf-idf (se eksempel).

Plasseringene i vektorrommet kan så bli sammenlignet med spørringen gjennom en rekke metoder (basert på bruksområde).

Applikasjoner[rediger | rediger kilde]

Vector space model.jpg

Kalkulering av relevans kan bli gjort på flere vis, hvor metoden brukt blir basert på ønsket utfall. En måte å regne gjøre dette er å sammenligne deviasjonen av vinklene mellom hvert dokument og spørringen representert som en vektor. Men i praksis er det enklere å regne ut cosinus likheten mellom de to vektorene, i stedet for mellom vinklene:

Eksempel:


\cos{\theta} = \frac{\mathbf{d_2} \cdot \mathbf{q}}{\left\| \mathbf{d_2} \right\| \left \| \mathbf{q} \right\|}

Hvor \mathbf{d_2} \cdot \mathbf{q} representerer skjæringspunktet (altså prikkproduktet) mellom dokumentet(d2 i bildet til høyre) og spørringens (q i bildet) vektorer, \left\| \mathbf{d_2} \right\| er normen av d2, og \left\| \mathbf{q} \right\| er normen av q. Normen til en vektor er kalkulert med:


\left\| \mathbf{q} \right\| = \sqrt{\sum_{i=1}^n q_i^2}

Siden ingen vektorer i denne modellen kan være negative, vil en cosinus verdi av null tilsi at vektorene til dokumentet og spørringen er ortogonale i forhold til hverandre og har dermed ingen likhet (spørring ordene fins altså ikke i dokumentet).

Eksempel: tf-idf vekting[rediger | rediger kilde]

I den originale vektorrom modellen foreslått av Salton, Wong and Yang [1] er term vekten i dokumentene produkter av lokale og globale parametere. I modellen kjent som term frequency-inverse document frequency er vekten brukt i vektorene i dokumentet d definert som \mathbf{v}_d = [w_{1,d}, w_{2,d}, \ldots, w_{N,d}]^T, hvor:


w_{t,d} = \mathrm{tf}_{t,d} \cdot \log{\frac{|D|}{|\{d' \in D \, | \, t \in d'\}|}}

og

  • \mathrm{tf}_{t,d} er term frekvensen av termen t i dokument d (ett lokalt parameter)
  • \log{\frac{|D|}{|\{d' \in D \, | \, t \in d'\}|}} er den inverse dokument frekvensen (ett globalt parameter), hvor:

|D| er det totale nummeret av dokumenter i ett sett og |\{d' \in D \, | \, t \in d'\}| er antallet dokumenter som inneholder termen t.

Cosinus likheten mellom dokument dj og spørring q kan dermed bli regnet ut ved:

\mathrm{sim}(d_j,q) = \frac{\mathbf{d_j} \cdot \mathbf{q}}{\left\| \mathbf{d_j} \right\| \left \| \mathbf{q} \right\|} = \frac{\sum _{i=1}^N w_{i,j}w_{i,q}}{\sqrt{\sum _{i=1}^N w_{i,j}^2}\sqrt{\sum _{i=1}^N w_{i,q}^2}}

Fordeler[rediger | rediger kilde]

Vektorrom modellen har disse fordelene over Boolean Modellen:

  1. Vektorrom-modellen er en enkel modell basert på lineær algebra.
  2. Termvekten er ikke binær.
  3. Tillater beregning av en kontinuerlig grad av likhet mellom spørringer og dokumenter.
  4. Tillater rangering av dokumenter basert på deres antatte relevans.
  5. Tillater delvis likheter.

Ulemper[rediger | rediger kilde]

  1. Lange dokumenter blir dårlig representert på grunn av de har dårlige likhets verdier (lave prikkprodukt og høy dimensionalitet).
  2. Spørring termer må være identisk til de i dokumentene.
  3. Dokumenter med lik kontekst men forskjellig vokabular blir ikke assosiert, noe som fører til falske negativer.
  4. Rekkefølgen termene følger i dokumentet blir ikke inkludert.
  5. Antar teoretisk at termer er statistisk uavhengig.
  6. Vekting er intuitivt, men ikke veldig formelt.

Mange av disse ulempene kan bli unngått ved å legge til flere metoder, som for eksempel Singulær verdi dekomposisjon eller bruk av en Tesaurus.

Gratis open source programmvare[rediger | rediger kilde]

  • Apache Lucene. Apache Lucene er en høy ytelses, fullfunksjons tekst søkemotor bibliotek skrevet i Java.
  • SemanticVectors. Semantiske Vektor indekser, skapt ved å påføre en tilfeldig Projeksjons algoritme til termin-dokument matriser opprettet ved bruk av Apache Lucene.
  • Gensim er et Python + NumPy rammeverk for Vektorrom modellering. Den inneholder inkrementelle (minneeffektive) algoritmer for blant annet TF-IDF, Latent semantisk indeksering og Latent Dirichlet Allocation.
  • Weka. Weka er populær data mining pakke for Java som inkluderer WordVectors og Bag of Words modeller.
  • Compressed vector space in C++ av Antonio Gulli
  • Text to Matrix Generator (TMG) MATLAB verktøykasse som kan brukes til ulike oppgaver i tekst mining spesifikt i) indeksering, ii) gjenfinning, iii) dimensionalitets reduksjon, iv) clustering, v) klassifisering. Meste parten av TMG er skrevet i MATLAB og deler i Perl. Den inneholder implementeringer av LSI, gruppert LSI, NMF, samt andre metoder.
  • SenseClusters, En open source pakke som støtter kontekst og ord clustering ved hjelp av Latent semantisk analyse og ord co-forekomst matriser.
  • S-Space Package, et samling av algoritmer for å utforske og arbeide med statistisk semantikk.
  • Vector Space Model Software Workbench Samling av 50 kildekodeprogrammer for utdanning.

Videre lesing[rediger | rediger kilde]

Se også[rediger | rediger kilde]

Referanser[rediger | rediger kilde]

  1. ^ G. Salton, A. Wong, C. S. Yang, A vector space model for automatic indexing, Communications of the ACM, v.18 n.11, p.613-620, Nov. 1975