Automatisk informasjonssøk på Web ved bruk av Ferrets

Martin Kermit

Sammendrag

Den enorme informasjonsmengden på Web gjør at innhenting av informasjon er en tidkrevende prosess. Selv om det eksisterer effektive, allment tilgjengelige søkemotorer, unngås likevel ikke problemet med irrelevante treff og døde lenker. Et nytt system som automatiserer søkeprosessen for informasjon på Web basert på den enkelte brukers interesser ved bruk av en agent, eller en såkalt “Ferret”, er under utvikling ved avdelingen og presenteres i denne artikkelen.

Innledning

Til tross for at kjente søkemotorer som Altavista, Infoseek og Kvasir har utviklet seg til å gi bedre søkeresultater, er informasjonssøk likevel en tidkrevende prosess. Ofte kreves informasjonssøk med flere forskjellige søkemotorer fordi disse ikke gir samme resultater, i tillegg til at den store mengden av irrelevante og utdaterte treff fortsatt er tid-krevende å gjennomgå.

Det viser seg at brukere av Web ofte har spesielle interesser som gjør at brukeren til stadighet ønsker seg informasjon om enkelte spesielle emner. Hver bruker har gjerne et eget mønster for hvilken informasjon som søkes etter via Web. For eksempel kan det være at en Web-bruker til stadighet leser om Manchester United, veteranbiler samt priser på nye harddisker. Et slikt mønster kan dermed brukes til å automatisere søkeprosessen på Web, slik at nye dokumenter med samme tema kan letes opp av den personlige agenten, eller ’Ferret’en.

Ved bruk av en nettverksserver som lagrer nedlastede dokumenter fra Web lokalt på serveren, en såkalt proxy-server, kan informasjon om brukernes informasjonssøk på Web bli tilgjengelig. Basert på denne informasjonen som er tilgjengelig fra proxy-serveren ønsker vi å lage et system for å automatisere informas-jonssøk på Web. Det automatiske søkesystemet som beskrives i denne artikkelen, benytter informasjon fra en proxy-server til å danne et mønster av hver enkelt brukers interesser angående dokumenter på Web. Basert på denne informasjonen, skal da ’Ferret’en benyttes til å hente nye dokumenter tilpasset hver enkelt bruker.

Første ledd i en slik prosess vil dermed bestå av en analyse av innholdet av de ulike dokumentene som finnes lagret på proxy-serveren. Dokumentene tolkes syntaktisk ved bruk av en HTML-tolker for å lokalisere ord og setninger som karakteriserer hvert enkelt dokument. Ord og setninger, videre referert til som nøkkelord, fra dokumenter lastet ned fra Web av den enkelte bruker, sorteres så videre for å danne kategorier av dokumenter som inneholder similær informasjon. Et nevralt nettverk av feedforward-typen trenes så til å kunne klassifisere dokumentene til sin respektive kategori ved hjelp av dokumentenes nøkkelord. Videre benyttes nøkkelordene til nye informasjons-søk. Treff fra søkemotorene lastes så ned lokalt, dersom lenken eksisterer, for så å sendes tilbake til HTML-tolkeren og et nevralt nettverk som skal avgjøre treffets relevans i forhold til tidligere dokumenter nedlastet av brukeren. Dersom treffet var relevant, vil brukeren få presentert lenken som fører til det klassifiserte dokumentet. Systemet skal utvikles med tanke på å betjene mange brukere og krever da en kraftig proxy-server.

En studentgruppe har i vår arbeidet med oppsettet og en mulig løsning på hvordan søkesystemet kan implementeres. Prosjektet ble så etterfulgt av en student som hadde sommerjobb ved avdelingen, og har i ettertid fortsatt blant de ansatte. Til gjennomføringen av 'Ferret'-prosjekt-et har avdelingen gått til innkjøp av en multiprosessor-PC med rikelig med diskplass som har fått navnet felix.hiof.no. Siden navnetjenesten for nettverks-servere ved avdelingen i Sarpsborg har tradisjon for å velge navn på serverne fra kjente russiske personligheter, var navnet Felix et greit valg. Felix var nemlig grunn-leggeren av Cheka, forløperen til KGB. Felix må derfor ha vært en person med mye informasjon, slik som også vår felix.hiof.no vil være. I resten av artikkelen vil de forskjellige modulene som inngår i systemet gjennomgåes og diskuteres.

Web-Cache

En proxy-server er en Web-server som fungerer slik at personer som er koblet opp som brukere av serveren, får lagret informasjon på serveren om hvilke dokumenter som er lastet fra Web. Når serveren får beskjed om å laste et dokument fra Web, vil den først lete lokalt på maskinen, såkalt Web-cache, før dokumentet eventuelt lastes fra Web. Dokumenter som lastes vil bli lagret på serveren, med det formål at andre som laster de samme sidene skal kunne få disse hentet opp lokalt i stedet for å vente på at disse sidene hentes direkte fra Web. Desto flere brukere som er tilknyttet proxy-serveren, jo flere dokumenter vil være tilgjengelig.

Et slikt oppsett er ideelt for vårt formål, siden dokumenter som brukerne har lastet vil være lagret på serveren. Disse dokumentene, i tillegg til diverse logg-filer, vil dermed være tilgjengelige for videre prosessering av brukermønster. I vårt oppsett benyttes proxy-serveren “Squid” som kjører under operativ-systemet Linux.

Databasen

Det brukes en Webside til å registrere brukere, med informasjon om sys-temet. Registreringen skjer i en database, og brukeren får så en personlig hjemmeside. På denne siden presenteres nye lenker for brukeren, etter hvert som et mønster dannes. Databasens tabeller inneholder:

Brukerinfo
Brukernavn
Passord
E-post adresse
IP-nummer (oppdateres for hver gang brukeren logger inn)
Eventuell identitet
Eventuelt ønske om cookies (ja, nei eller persistent)
Referanseliste til linker brukeren har vært på
Samtlige linker (URL)
Tittel
Linker
Filnavn
Kategorier

Vi benytter oss av databasen i Modelator som eksporterte vår modell til SQL. Vi har valgt å bruke MySQL som databaseserver og PHP for å få et grensesnitt mellom server og klient (bruker). Oppdatering av databasen skjer ved disse anledningene:

Logganalysatoren ser at Squid har skrevet en ny linje i loggen, som møter kravene.
HTML-tolkeren plukker ut tittel fra dokumentet.
Det nevrale nettet kategoriserer siden, og oppdaterer kategoriene i databasen for å reflektere dette.

HTML-tolkeren

HTML-tolkeren er den delen av systemet som henter frem de lagrede HTML-dokumentene fra proxy-serveren og tolker informasjonen slik at det er mulig å skille mellom ord og setninger som forekommer i overskrifter, kursiv, eller som ren tekst. Den vil også være i stand til å se bort fra spesifikke HTML-tags som beskriver grafikk, og lignende.

På grunn av at mange dokumenter på Web er skrevet ved hjelp av forskjellige HTML-editorer, avviker HTML-koden til Web-dokumenter ofte fra det som er definert som HTML-standard. Dette gjør at en enhetlig analyse av hvilke deler av et vilkårlig dokument som er tittel, underoverskrift, osv. ikke er mulig uten å lage en egen tolker spesifikk for hver enkelt HTML-editor. En slik løsning er av opplagte årsaker ikke ønskelig.

Vår løsning på dette problemet benytter GNU-programmet LYNX, som er en programpakke for lesing av HTML-dokumenter. LYNX er i stand til å ta et hvilket som helst Web-dokument som input og gi det rene tekstinnholdet som output etterfulgt av alle lenker som det er referert til i dokumentet. LYNX er derfor det første leddet i vår HTML-tolker. Med kun det rene tekstinnholdet som utgangspunkt blir problemstillingen mer kompleks siden informasjon om hvilke deler av teksten som er overskrifter eller kursivert nå er gått tapt. Likevel kan LYNX gi ut dokumentets tittel, samt hvilke ord i teksten som er benyttet som HTML-referanser.

Uthenting av nøkkelord

For å kunne klassifisere ett eller flere Web-dokumenter trenger vi en eller flere klassifikatorer. For å kunne velge en fornuftig klassifikator må vi se litt nærmere på hva et gitt Web-dokument egentlig inneholder og sortere ut viktig og uviktig infor-masjon. Selve klassifiseringen består i å hente ut et gitt antall ord, nøkkel-ord, fra hvert enkelt dokument som er beskrivende for innholdet av dokumentet. Disse nøkkelordene danner grunnlag for å kategorisere dokumentene.

Uthenting av slike nøkkelord er muligens det mest kritiske leddet i det totale søkesystemet og har mange angrepsvinkler. Siden systemet ikke er implementert ennå, skal vi se på noen forskjellige muligheter.

Statistisk klassifisering

En mulig måte å hente ut nøkkelord er ved å rett frem telle antall fore-komster av hvert enkelt ord i dokumentet som skal klassifiseres. Deretter sorteres ordene etter hvilke ord som forekommer oftest. Denne metoden vil naturlig nok ha en svakhet i at hjelpeverb, preposisjoner og andre småord vil toppe listen. Dette problemet kan unngås dersom tellingen av ord konsulterer en ordliste som inneholder ord som ikke skal telles med, eller at det settes andre krav til ord som skal telles, slik som f.eks. at ord må ha en viss lengde, eller at ordet ikke skal forekomme for ofte.

Ord-databasen

En annen løsning kan være å gjøre ordtelling på samme måte som overfor, bare at telleren konsulterer en ordliste som inneholder ord som er gyldige i stedet for forbudte nøkkelord. Begge disse metodene vil kreve at det opprettes databaser over enten gyldige eller forbudte ord, noe som kan være svært vanskelig. En mulig løsning på hvordan opprette en slik database kan være ved f.eks. å benytte kun substantiv og eventuelt andre ordklasser fra ferdige ordlister som gyldige nøkkelord.

Hierarkisk oppdeling

Ved å ta utgangspunkt i at størrelsen på overskrifter som forekommer i dokumenter beskriver viktigheten av informasjon, kan et HTML-dokument hierarkisk oppdeles hvor den mest betydningsfulle overskriften er tittelfeltet eller <title> tagen. Deretter følger så overskriftene, fra <h1> til <h6>. Disse overskriftene danner dermed grunnlaget for uthenting av nøkkelord.

En slik løsning vil dermed redusere informasjonsmengden drastisk ved å benytte alle ord i de mest betydningsfulle overskriftene som nøkkelord, men er altså ikke mulig på grunn av at HTML-tolkeren benytter programmet LYNX, slik som beskrevet i forrige avsnitt.

Syntaktisk tolkning av grammatikk

Den mest elegante løsningen vil uten tvil være å få til en algoritme som “leser” dokumenter ved å tolke hvilke ord som er direkte objekter etter grammatiske kriterier. Slike gram-matiske tolkere forskes det mye på, uten at det finnes tilfredsstillende løsninger tilgjengelig. Denne løsnin-gen vil derfor være innviklet og kreve mye videre tankearbeid. (Likevel, den absolutt kraftigste).

Klassifisering og nevrale nettverk

Etter at et visst antall ord er plukket ut fra hvert dokument som er lagret på den enkelte bruker, vil det så foretaes en sammenlikning av ord som er felles for flere sider. Dersom det for eksempel finnes 100 Web-dokumenter registrert lastet av samme bruker, og det plukkes ut ti sentrale nøkkelord fra hvert dokument, vil dokumenter som inneholder felles tekststrenger klassifiseres i samme kategori, hvor kategorien vil kategoriseres ut fra alle tekst-strengene inneholdt av dokumentene.

Disse tekststrengene konverteres så til et heltall ved å tolke ascii-verdien til hvert tegn som bytes i et stort heltall, modulo et primtall litt under MAXINT for så å bli brukt som input til et feedforward nevralt nettverk av typen backpropagation.

Dette nettverket blir så trent slik at det gir de ulike kategoriene som output når tekst-strengene fra et dokument i samme kategori gis som input til nettverket. Nettverket fungerer deretter som en klassifikator som avgjør ut fra nøkkelordene fra et dokument om dokumentet er verdt å presentere for brukeren.

Systemet vil dermed kreve at hver enkelt bruker har sitt personlige nevrale nettverk. Et slikt nevralt nettverk må også trenes med dokumenter som ikke tilhører noen av brukerens ønskelige kategorier, slik at et dokument også kan klassifiseres som ubrukelig.

Videre søking etter informasjon

Alle nøkkelord som er plukket ut fra dokumenter i proxy-serveren benyt-tes så som input til søkemotorene som er tilgjengelige på nettet. Søkemotorene vil gi en stor mengde treff, hvor et gitt antall av de viktigste dokumentene vil bli hentet ned til proxy-serveren hvor de sendes til HTML-tolkeren som henter ut nøkkelord.

Nøkkelordene organiseres så i en enkelt matrise som blir benyttet som input til hver brukers nevrale nettverk. De sterkeste treffene vil deretter presenteres for brukeren. Dersom brukeren ikke mener at dokumentet presentert var fullstendig irrelevant, vil brukerens nevrale nettverk så trenes opp på nytt med de nye, godkjente treffene som også inngår i treningsmaterialet til nettet.

Videre utvikling

Målsetningen er at alle brukere av web innen Høgskolen i løpet av neste år skal ha mulighet til å kunne koble seg opp til felix.hiof.no og på den måten skaffe seg sin personlige ’Ferret’.

De neste skrittene i prosjektet blir dermed i første omgang å få til en prototype av systemet, siden all implementasjon ennå ikke er utført i sin helhet og flere mulige løsninger fortsatt er på idéstadiet og trenger videre utvikling.

Dersom det melder seg studenter, vil prosjektet også videreføres som studentprosjekt våren 1999. Vi vil av den grunn være åpne for innspill til prosjektet hvis noen skulle ha forslag til utvikling av systemet.

HØit Nr. 1-99