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 tekstdokumenter (samt alle andre objekter) som vektorer bestående av identifikatorer, som for eksempel ved å bruke term vekt som parameterverdi. 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 beregnet 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. I praksis er det enklere å regne ut cosinuslikheten 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 cosinusverdi av null tilsi at vektorene til dokumentet og spørringen er ortogonale i forhold til hverandre og dermed helt mangler likhet (spørreordene 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 termvekten 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.

Cosinuslikheten 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. Det 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 delvise likheter.

Ulemper[rediger | rediger kilde]

  1. Lange dokumenter blir dårlig representert på grunn av at de har dårlige likhetsverdier (lave prikkprodukt og høy dimensionalitet).
  2. Spørretermer må være identiske 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 skjer intuitivt, men ikke formelt.

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

Gratis open source programmvare[rediger | rediger kilde]

  • Apache Lucene. Apache Lucene er et høyytelses-, fullfunksjons- tekstsøkemotorbibliotek skrevet i Java.
  • SemanticVectors. Semantiske vektorindekser, skapt ved å påføre en tilfeldig projeksjonsalgoritme til termin-dokumentmatriser 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 en 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 1) indeksering, 2) gjenfinning, 3) dimensionalitetsreduksjon, 4) clustering og 5) klassifisering. Mesteparten 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-forekomstmatriser.
  • S-Space Package, en samling av algoritmer for å utforske og arbeide med statistisk semantikk.
  • Vector Space Model Software Workbench Samling av 50 kildekodeprogrammer for utdanning.

Videre lesning[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