Tekstklassifisering

Automatisk dokumentklassifisering eller tekstklassifisering^{[trenger referanse]} handler om å gruppere tekster (dokumenter) etter felles emner (klasser), og navngi hver klasse med en eller flere passende merkelapper. Man tilordner hvert dokument som klassifiseres til en passende klasse ("single-label" klassifisering). I noen tilfeller kan et dokument også tilordnes til flere klasser ("multi-label" klassifisering). Klassifisering av dokumenter kan for eksempel hjelpe med å finne igjen dokumenter, eller det kan hjelpe å finne dokumenter som passer til et gitt informasjonsbehov. Innenfor informasjonsgjenfinning har tekstklassifisering blant annet blitt brukt til å automatisk detektere spam websider (for eksempel ved å tilordne hver aktuelle webside enten til klasse "spam" eller til klasse "ikke spam"), automatisk sortere personlig e-post og å automatisk oppdage websider med grov språkbruk. Klassifisering av tekster kan også gjøres etter egenskaper som sjanger eller år.

Å tilordne et dokument til en klasse kan gjøres som manuelt arbeid av et menneske (mer info her: klassifikasjon), noe som for eksempel ofte har blitt gjort innen bibliotekvitenskap. Slik tekstklassifisering kan være tidkrevende. Tilordningen kan også gjøres automatisk ved å lage et program som går gjennom dokumentene og bruker håndskrevne regler for å bestemme hvordan spesifikt innhold i hvert enkelt dokument kan knyttes til en klasse. Opprettelse og vedlikehold av slike regler kan være krevende og vil ofte forutsette god domenekjennskap av vedkommende som lager reglene. Det er også mulig å bruke teknikker innen maskinlæring (et underfelt av kunstig intelligens) for å gjøre tekstklassifisering. Denne artikkelen vil fokusere på sistnevnte.

Automatisk tekstklassifisering ved hjelp av teknikker innen maskinlæring

Maskinlæring vedrører design og utvikling av algoritmer som lærer mønstre som er tilstede i data som blir gitt som inndata. Mønstrene som læres kan så bli brukt for å gjøre prediksjoner relativt til nye data som ikke har blitt sett tidligere.

Maskinlæring algoritmer er fundamentalt avhengig av en lærefase, denne fasen blir brukt for å produsere en modell/funksjon som koder mønstre som er tilgjengelige i inndata.

Innenfor kunstig intelligens og maskinlæring kan tekstklassifisering gjøres ved hjelp av algoritmer som benytter seg av veiledet læring, ikke-veiledet læring eller delvis-veiledet læring. Algoritmer som gjør bruk av delvis-veiledet læring vil ikke bli gjennomgått i artikkelen.

Veiledet læring tekstklassifisering

Det vanlige for veiledet læring tekstklassifisering er at en mengde klasser og eksempel på dokumenter for hver klasse blir gitt. Dokumenteksemplene (treningsdokumentene) blir bestemt av en menneskelig spesialist og utgjør et treningssett - dette settet kan dernest bli brukt for å lære en klassifiseringsfunksjon. Dette er også kjent som treningsprosessen.

Når denne klassifiseringsfunksjonen har blitt lært kan den brukes til å klassifisere nye, usette dokumenter. Dette er også kjent som klassifiseringsprosessen.

Klassifiseringsprosessen kan for eksempel være basert på forekomst av termer i de nye dokumentene, som sammenlignes med forekomst av de vanligste termene for en gitt klasse. Jo flere termer i dokumentene, jo mer krevende blir det å klassifisere dem. Spesielt vanskelig blir det for sofistikerte klassifiseringsalgoritmer med høy beregningskompleksitet. Derfor er det mulig å lage en vektor for hvert dokument som kun består av de antatt viktigste termene for klassifiseringen, en såkalt feature vektor. Hvilke termer som inngår i vektoren kan for eksempel basere seg på term-vekter gitt av Tf-idf, men forsøk har vist at Khikvadratfordeling og informasjonsøkning (information gain) fungerer bedre. Feature vektoren kan brukes videre av klassifisereren istedenfor en dokumentrepresentasjon som baserer seg på alle ordene i et dokument. Det er vist at et dokument kan reduseres med flere størrelsesordener gjennom vektorisering, uten at det går ut over kvaliteten på klassifisering.

På en side er det slik at jo større antall treningsdokumenter man har, jo bedre blir klassifiseringen. Samtidig er det problematisk om klassifiseringen blir alt for tilpasset treningsdokumentene, slik at den ikke lenger kan brukes for å klassifisere nye, usette dokumenter på en god måte. Dette problemet er kjent som overtilpasning (overfitting).

For å evaluere tekstklassifiseringen kan vi bruke den på en mengde nye, usette dokumenter, hvis klasser allerede er bestemt av mennesker - et testsett. Hvis en stor andel av dokumentene i testsettet bestemmes likt av veiledet læring klassifiseringen og av menneskenes klassifisering, kan vi si at både treningsprosessen og klassifiseringsprosessen fungerer bra, og klassifisereren kan brukes til å klassifisere nye dokumenter (som da naturlig nok er utenfor testsettet).

Det bør i denne forbindelse også nevnes at klassifisering er en subjektiv prosess, slik sett vil to ulike menneskelige spesialister kunne være uenige om klassifisering, noe som gjør at 100% enighet mellom menneske og automatisert prosess ikke er et mål som lar seg oppfylle. For eksempel, gitt et dokument om EU som kun skal tilordnes en klasse ("single-label" klassifisering): Skal dette tilordnes en Europa klasse eller en Politikk klasse (eller eventuelt en annen klasse som stemmer overens med innholdet i dokumentet)?

Denne typen læring blir kalt veiledet læring fordi en veileder (et menneske som definerer klasser og merker treningsdokumenter) fungerer som en lærer som styrer læreprosessen.

Algoritmer

Noen av de beste algoritmene for tekstklassifisering er basert på veiledet læring. Representative algoritmer for veiledet læring tekstklassifisering inkluderer blant annet:

Beslutningstrær: Beslutningstre
Nærmeste nabo: k-NN, vektet kNN
Relevance feedback: Rocchio, Rocchio i en Query Zone
Naive Bayes: Binær uavhengighet Naive Bayes, Multinomial Naive Bayes
Support Vector Machines: SVM, SVM Multiple Klasser, SVM Multiple Kjerner
Ensemble: Stacking-basert Ensemble, Boosting-basert Ensemble

Ikke-veiledet læring tekstklassifisering

For ikke-veiledet læring tekstklassifisering brukes ikke et treningssett som inndata. Denne typen klassifisering passer best for store dokumentsamlinger som ikke har vært gjennomgått av en menneskelig spesialist på forhånd. Den er generelt ikke like god som veiledet læring tekstklassifisering.

Ikke-veiledet læring tekstklassifisering kan være innenfor clustering eller naiv tekst klassifisering.

Tekstclustering er egentlig et relatert problem til tekstklassifisering, da klassene på forhånd ikke har noen spesielle merkelapper (et treningssett med data merket av mennesker blir således ikke brukt). En clusteringalgoritme deler en dokumentsamling inn i K undermengder, basert på likheter mellom dokumentene. Hvilke undermengder man står igjen med er ikke nødvendigvis intuitivt for mennesker, men det er et alternativ dersom man mangler merkede data, og kan for eksempel hjelpe å oppdage nye mønstre i en dokumentsamling som ikke ville ha blitt fanget opp ved manuell gjennomgang.

I naiv tekstklassifisering matcher man dokument termer til forhåndsgitte merkelapper (termer) som er knyttet til en klasse, for å knytte et dokument mot klasse. Her brukes heller ikke et treningssett. Dette er en enkel form for klassifisering som kan forbedres ved å definere alternative merkelapper for hver klasse. Slik tekstklassifisering kan fungere bra for vertikale samlinger som er basert på spesielle kunnskapsområder (gjerne hvis en taksonomi er tilgjengelig), men for generelle samlinger kan den bli for restriktiv.

Algoritmer

Algoritmer innenfor clustering inkluderer blant annet:

Partisjonsclustering: k-means, bisecting k-means
Samlende (hierarkisk) clustering: Enkel link, komplett link, gjennomsnittlig link

Algoritmer innenfor naiv tekstklassifisering inkluderer blant annet:

Tekstklassifisering ved direkte match: Vector Model

Evaluering av tekstklassifiseringsmetoder

Et utall måter kan brukes for å evaluere (og dermed validere) nylig foreslåtte klassifiseringsmetoder. De mest brukte metrikkene for å bedømme kvaliteten av en tekstklassifiserer som tilordner hvert dokument til en klasse (single-label klassifiserere) er listet opp under.

Nøyaktighet og feil (accuracy and error)
Presisjon og gjenkalling (precision and recall)
F-skår (f.eks. F₁-skår
Kryssvalidering (cross-validation)
Standard-samlinger: Deriblant Reuters-21578 - den mest brukte samlingen i klassifiseringseksperimenter

Referanser

Baeza-Yates, Richardo; Ribeiro-Neto, Berthier (2011). Modern Information Retrieval: The concepts and technology behind search. Addison Wesley.
Manning, Christopher; Raghavan, Prabhakar; Schütze, Hinrich (2008). Introduction to Information Retrieval. Cambridge University Press.