Selvorganiserende Nevrale Nettverk i Data Mining
-The Golden Retriever

Harald Holone

Data Mining

Etter hvert som mengdene med data i databaser rundt i verden øker voldsomt i størrelse ønsker brukerne å kunne finne mulige sammenhenger i dataene som ikke er kjent fra før. Slike sammenhenger kan brukes som støtte for avgjørelser i f.eks markedsføring. Dette er interessant f.eks i salgsavdelinger i store bedrifter, der man kan se på kunders vaner og dra nytte av disse for å få solgt mer varer til forskjellige kundegrupper.

Data Mining er idag et av de største moteordene i databaseindustrien, og det kommer stadig flere firmaer med løsninger på markedet. Både etablerte databaseprodusenter og uavhengige softwareprodusenter er med, og det vi ser idag er antakelig starten på utviklingen av en teknologi som om noen år vil være uunnværlig i dataanalyse og beslutningsstøttesystemer.

Oppgaven

Når det er snakk om f.eks salgsavdelinger som ønsker å analysere sine data dreier det seg ofte om svært store datamengder, fra 50GB til flere TB. I vår oppgave var ikke målet å lage et fullblods Data Mining system som kunne takle så store data, men å finne ut om det kunne la seg gjøre å implementere Data Mining med et selvorganiserende nevralt nettverk (se artikkel om nevrale nettverk i tidligere utgave av HØit) anvendt på mindre mengder data. Da vi startet prosjektet i januar var det allerede noen produkter på markedet, men de baserte seg stort sett på tradisjonelle metoder som beslutningstrær og statistikk. Markedet har endret seg ganske mye fra januar til juni, og det har dukket opp flere produkter som også anvender nevrale nett og fuzzy logikk.

Valg av nevralt nettverk

At vi skulle bruke et selvorganiserende nevralt nettverk var bestemt ved prosjektstart. Et 'vanlig' nevralt nettverk blir lært opp ved at man presenterer inputdata til nettverket sammen med ønsket output, dvs at man forteller nettverket hva slags data som blir presentert. Ved å presentere eksempler fra hver gruppe vil nettverket etter trening være i stand til å kjenne igjen inputdata som ligner på tidligere presenterte data og gi tilbakemelding om hvilken forhåndsdefinert gruppe det presenterte inputdataet antakelig tilhører.

Et selvorganiserende nevralt nettverk skiller seg fra et 'vanlig' nevralt nettverk ved at man ikke forteller nettverket hva slags data som blir presentert. Det er opp til nettverket selv å finne ut hvilke inputdata som ligner på hverandre og legge dem i samme gruppe, herav navnet selvorganiserende. Det er nettopp denne egenskapen ved selvorganiserende nettverk som gjorde dem til et selvklart valg i Data Mining sammenheng, målet er å finne ukjente korrelasjoner.

Etter å ha testet noen få selvorganiserende nettverk (Hamming, Winner-takes-all, ART1) for å få en føling med hvordan slike nettverk fungerer endte vi opp med å bruke nettverksmodellen ART2 (Adaptive Resonance Theory 2) i vårt prosjekt.

ART2

Grunnen til at vi valgte ART2 var at dette er et stabilt nettverk (det er i stand til å 'huske' selv sjeldent presenterte data), det takler kontinuerlige data, brukeren kan selv bestemme hvor like hverandre inputdata må være for å bli klassifisert til samme klasse, nettverket oppretter selv så mange klasser det trenger, og det jobber forholdsvis raskt. Justering av hvor 'strengt' nettverket skal være når det sammenlikner prototyper og inputmønster bestemmes av en parameter (kalt vigilanseparameter), et flyttall mellom 0 og 1. Med denne parameteren satt til 0 vil nettverket betrakte alle inputmønstre som medlemmer av samme gruppe. Når parameteren økes mot 1 blir nettverket strengere, og ved 1 må inputmønstre være identiske for å bli plassert i samme gruppe.

Et ART2 nettverk begynner uten noen klasser definert. Så fort det første inputmønsteret blir presentert blir den første klassen opprettet, og til denne klassen blir det opprettet en prototype som er en kopi av det første inputmønsteret. Videre fungerer nettverket som følger:

Nytt inputmønster blir presentert
En kryssmultiplikasjon av inputmønstret og hver prototype blir utført
Den prototypen som gir høyest resultat blir plukket ut som vinner
Den valgte prototypen blir sammenlignet med inputmønstret
Er de tilstrekkelig like blir denne prototypen justert og inputmønstret havner i denne klassen
Er de ikke like nok blir 'nest beste' prototype valgt som vinner, og testen utføres på nytt
Steg 6 foregår helt til en 'riktig' prototype blir funnet eller til det ikke er flere igjen
Er det ikke flere prototyper igjen blir det opprettet en ny klasse for dette inputmønstret

Implementasjonen

Nettverket ART2 har vi implementert i en klasse i C++ uten plattformavhengige systemkall, slik at det skal være enkelt å flytte koden til en annen plattform. Vi valgte å bruke Windows som plattform for vårt program, og fant det naturlig å legge klassen ART2 i en DLL slik at det var lett å få tilgang til nettverket f.eks fra MS Visual Basic. DLL'en består av selve nettverksklassen ART2 og noen aksessfunksjoner for å opprette, trene og slette nettverket, samt å se på prototypene til klassene under og etter trening.

Vi laget et grensesnitt i Visual Basic for å kontrollere de forskjellige delene av programmet. Valg av data som skal analyseres gjøres enkelt via ODBC eller fra en MS Access fil. Programmet benytter seg også av et RAMScan kort fra MRT via en VBX. På dette kortet blir inputdata og resultater lagret. Grunnen til at vi gjør dette er at vi enkelt og raskt kan presentere statistisk informasjon om hver klasse som nettverket deler inn inputmønstrene i.

I grensesnittet kan brukeren også justere vigilanseparameteren, velge antall kunstige input og verdiene på disse, samt justere gjennomsnitt for hver av parametrene i inputmønstrene.

Resultatene

Testresultatene som er presentert under er resultater etter en gjennomkjøring av dataene.

Nettverket er testet primært med to datasett. Det ene er IRIS, et datasett som er en slags standard innen nevralnettmiljøet. Dataene består av 150 forskjellige inputmønstre med 4 parametre hver. Dataene er delt inn i 3 klasser med 50 inputmønstre i hver.

Med justering av vigilanseparameteren og bruk av noen kunstige input delte nettverket vårt inn dataene i 3 klasser, og kun et input var klassifisert feil i følge fasiten. Dette resultatet er bedre enn det vi tidligere har oppnådd med Back-Propagation nettverk, som er et nettverk der man også sender med informasjon om hvilken klasse hvert input tilhører.

Vi testet også nettverket vårt mot et datasett som heter ZOO. Dette datasettet beskriver 101 navngitte dyr og hvilken av 7 grupper de tilhører. For hvert dyr finnes det 16 forskjellige opplysninger, f.eks om det legger egg, om det har fjær, om det lever under vann, hvor mange ben det har osv.

Under testingen med disse dataene eksperimenterte vi kun med vigilanseparameteren og ikke med kunstige input eller gjennomsnittsjusteringer. Nettverket delte inn dataene i en del klasser, noen av disse inneholdt hummer og kanari (bokstavelig talt), men det var også noen grupper som var svært positivt overraskende. Enkelte grupper bestod kun av fisker eller kun av fugler. Dette er et resultat vi er svært godt fornøyd med, ikke minst fordi det er et godt eksempel å vise til for å beskrive hva et Data Mining system kan klare.

Konklusjon

Det virker for oss helt klart at selvorganiserende nevrale nettverk kan anvendes i Data Mining systemer. Det største argumentet imot bruk av nevrale nett er at nevrale nettverk fungerer som en svart boks der det er vanskelig å begrunne de beslutningene som nettverket treffer. Vi håper at vår presentasjon av resultater gjør at nettverket blir noe mer enn en svart boks, og at det er mulig å se årsaker til at inputmønstre havner i samme klasse.

I vår prosjektrapport kommer vi med flere forslag til utvidelser av programmet. Både preprosessering av data og etterbehandling av resultater er viktige punkter som ville øke programmets nytteverdi. Dessuten er det også ønskelig at programmet selv er i stand til å finne 'riktig' vigilanseparameter slik at brukeren slipper å eksperimentere med denne. Med riktig vigilanseparameter menes at antall klasser som opprettes ligger i et område som brukeren har definert på forhånd. Det gjenstår også testing med større datamengder og på andre typer data.

Videre lesing

Advantages In Knowledge Discovery And Data Mining,
Fayyad, Piatetsky-Shapiro, Smyth, Uthurusamy
ISBN 0-262-56097-6

Data Mining - An Introduction

Pattern Recognition By Self-Organizing Neural Networks,
Carpenter, Grossberg
ISBN 0-262-03176-0

HØit Nr. 2-96

Selvorganiserende Nevrale Nettverk i Data Mining -The Golden Retriever