Wat is data mining?


'Computers have promised us a fountain of wisdom, but they have delivered a flood of information' (A frustrated MIS executive) (10)

Gedurende de laatste decennia hebben ondernemingen enorme hoeveelheden gegevens over alle mogelijke en onmogelijke onderwerpen gegenereerd, verzameld en opgeslagen. Bedrijven houden gegevens bij over hun klanten, boekhoudingen zijn geautomatiseerd, grootwarenhuizen schakelen over op kassa’s met scanners, banken beschikken over databases met miljoenen kredietkaarttransacties, telefoonmaatschappijen houden historieken bij met gegevens van alle telefoongesprekken en supportafdelingen houden gegevens bij over problemen met produkten en de bijbehorende oplossingen.

Schattingen over de groei van de hoeveelheid gegevens die wereldwijd in databases of een andere digitale vorm is opgeslagen lopen sterk uiteen. In (10) hebben Frawley et. al. het over een verdubbeling per 20 maand van de hoeveelheid gegevens en een nog snellere toename van het aantal databases. Algemeen wordt aangenomen dat er sprake is van een exponentiŽle groei. Het ziet er bovendien niet naar uit dat er vlug een eind zal komen aan deze trend. Databases zullen meer en meer gemeten worden in gigabytes en terabytes.

Vb.

De gegevens in de meeste databases worden bijgehouden ter ondersteuning van operationele processen maar meer en meer begint men te beseffen dat er meer in die databases zit. Deze bestanden met historische gegevens vormen een onschatbare bron van impliciete informatie. Impliciete informatie die kan gebruikt worden om te voorspellen of iemand kredietwaardig is, om een diagnose te stellen van een patiŽnt of om te verklaren waarom die bepaalde marketingcampagne zo’n een succes was.

De bedrijfsdatabase is geŽvolueerd van een opslagruimte tot een schatkamer vol impliciete informatie en het zoeken naar die impliciete informatie noemt men data mining.

1.1. Definitie van data mining

In de literatuur vinden we meestal dezelfde elementen terug in de definities of omschrijvingen van data mining. De meeste auteurs verwijzen naar hetgeen waarnaar gezocht wordt:

Vb.

Anderen beklemtonen het doel dat nagestreefd wordt:

Vb.

In enkele van de definities is ook terug te vinden hoe men deze doelstellingen wil bereiken:

Vb.

In (6) beschrijven Shortland en Scarfe data mining als het converteren van ‘volume data’ (grote en moeilijk handelbare data sets) naar ‘high-value data’ (waardevolle informatie, modellen die de onderliggende relaties bevatten).

Figuur 1 Omzetten van 'volume data' in 'high-value data'

 

De definitie die ik in mijn verhandeling zal aanhouden is de volgende:

Data mining is het gebruik van intelligente hulpmiddelen voor data analyse om te zoeken naar impliciete informatie en patronen in grote databases, met de bedoeling kennis te ontdekken die kan bijdragen tot een beter begrip van het probleemdomein.

Deze definitie vormt mijns inziens een goede combinatie van de verschillende facetten die in de hiervoor aangehaalde beschrijvingen en definities terug te vinden zijn.

De belangrijkste aspecten van mijn definitie zijn:

1.1.1. Intelligente hulpmiddelen

Ondanks de enorme vooruitgang op het vlak van de hardwarematige behandeling van gegevens, sukkelt de mogelijkheid tot verwerken en effectief gebruiken van die gegevens ver achterop. Een eerste reden hiervoor is dat de hulpmiddelen waarover de analist of de gebruiker momenteel beschikt volstrekt ontoereikend zijn voor het ontdekken van impliciete informatie. Ze zijn te weinig flexibel en vergen teveel begeleiding en voorkennis van de gebruiker. Dit maakt dat de interpretatie van gegevens de taak is van experts die getraind zijn in het probleemdomein ťn die weten hoe ze gegevens moeten analyseren. Dergelijke experts zijn er niet in overvloed en zijn dus duur.

Dit heeft als gevolg dat het merendeel van de gegevens gewoon wordt bijgehouden totdat men het veilig vindt om ze weg te gooien, een situatie die Shortland en Scarfe omschrijven als ‘data rich and information poor’(6) en die in (10) omschreven wordt als een steeds groter wordende kloof tussen ‘data generation’ en ‘data understanding’.

Om het hoofd te (blijven) bieden aan deze stormvloed aan gegevens, moet we kunnen beschikken over intelligente tools voor gegevensanalyse. Een dergelijk hulpmiddel voorziet de gebruiker van een set van vooruitstrevende middelen voor het zoeken naar en ontdekken van bruikbare kennis in een database, het organiseren van deze kennis naar verschillende standpunten, het testen van deze kennis op een set van voorbeelden en het integreren van nieuwe kennis met de bestaande KB.

De ontwikkeling van dergelijke hulpmiddelen vereist de samenwerking van specialisten op het vlak van machine learning, statistiek en databases. Machine learning levert het kennisontdekkingsalgoritme, statistische methoden maken het algoritme robuuster en databasetechnieken zorgen ervoor dat de gegevens op een efficiŽnte en gestructureerde manier opgeslagen, geraadpleegd en gewijzigd kunnen worden.

Naast intelligente tools op basis van machine learning, databases en statistiek worden de laatste tijd ook MDA (multi-dimensionele analyse) en Query-and-Reporting tools aangeprezen als data mining tools. Ik ga echter akkoord met de uitspraak dat deze tools geen echte data mining tools maar geavanceerde query tools zijn.

1.1.2. Impliciete informatie: deductie en inductie

Traditioneel wordt in een database enkel deductief gewerkt. Dit houdt in dat men met behulp van sql-operatoren expliciete informatie afleidt. Expliciete informatie is informatie die het logisch gevolg is van de gegevens in de database.

Vb.

Jan werkt op afdeling A.

Piet is de baas van afdeling A.

Dus Piet is de baas van Jan.

Het resultaat van deductie zijn uitspraken die zowel in de de database als in de werkelijke wereld correct zijn op voorwaarde dat de database correct is.

Data mining daarentegen werkt inductief. Bij inductie wordt impliciete informatie afgeleid, informatie die het resultaat is van generalisatie van de informatie in de database.

Vb.

Elke werknemer heeft een baas.

Dergelijke impliciete informatie bestaat uit veralgemeende uitspraken over de eigenschappen van objecten die gelden voor de database maar die niet noodzakelijk gelden in de werkelijke wereld.

 

1.1.3. Patronen

Definitie van een patroon(10):

Gebaseerd op een set van feiten (gegevens) F, een representatieformalisme R en een maatstaf voor (on)zekerheid C, is een patroon een uitspraak U in R die verbanden beschrijft in een subset van F, op zo’n manier dat U eenvoudiger is dan de opsomming van alle feiten in die subset.

Een patroon of regel kan dus een verband zijn tussen records, attributen, groepen records en attribuutsets.

Vb.

Een patroon wordt uitgedrukt in een representatieformalisme. De keuze van representatieformalisme gebeurt op basis van de doelstellingen die met het patroon beoogd worden.

Enkele voorbeelden van representatieformalismen zijn:

Voor meer informatie over representatieformalismen en hun voor- en nadelen verwijs ik naar deel 4.1, Robuuste algoritmes.

Afhankelijk van het beoogde doel zal ook naar een verschillend type patroon gezocht worden.

Vb.

Stel dat een bedrijf een mailing heeft verzonden naar alle gezinnen in provincie A en men wil nu dezelfde mailing over de rest van het land verspreiden. In dit geval kan men in de database met mensen die reeds gemaild zijn een karakteristiek patroon opzoeken voor diegenen die geantwoord hebben op het aanbod. Op basis van dit karakteristiek patroon kunnen dan voor de andere provincies alle mensen gemaild worden die aan dat profiel voldoen om zodoende de kostprijs van de mailing te minimaliseren en de respons te maximaliseren.

Vb.

Wanneer een bank wil bepalen of iemand die een lening aanvraagt kredietwaardig is kan ze op basis van gegevens over vroegere leningen (o.a. het geleende bedrag, het inkomen van de aanvrager en of de lening is terugbetaald) regels construeren die kunnen helpen bij de evaluatie van een aanvraag. Dergelijke regels noemen we classificatieregels.

1.1.3.1. Karakteristieke versus discriminerende patronen

Karakteristieke patronen

Een karakteristiek patroon is een beschrijving of samenvatting van wat de records van ťťn bepaalde klasse met elkaar gemeen hebben, ongeacht de karakteristieken van de andere klassen. Het is dus een beschrijving van de doelklasse. Dergelijke karakteristieke regels vormen een noodzakelijke voorwaarde om tot de doelklasse te behoren.

Een karakteristiek patroon heeft de volgende vorm:

doelklasse(x) ř conditie(x)

Een karakteristiek patroon is compleet wanneer het geldt voor alle voorbeelden in de doelklasse.

Discriminerende regels of classificatieregels

Een discriminerende regel of classificatieregel is een regel die voorbeelden van de doelklasse kan onderscheiden van voorbeelden van de contrasterende klassen. Het is een beschrijving van de verschillen tussen de doelklasse en de contrasterende klassen. Een discriminerende regel vormt een voldoende voorwaarde om tot een bepaald klasse te horen.

Een discriminerende regel heeft de volgende vorm:

conditie(x) ř doelklasse(x)

Een discriminerende regel of classificatieregel is consistent wanneer hij alle voorbeelden die voldoen aan de voorwaarde correct classificeert.

Correcte regels

Een correcte regel is een regel die zowel compleet karakteristiek als consistent discriminerend is. Het is een uitspraak die waar is voor alle positieve voorbeelden en niet waar is voor alle negatieve voorbeelden.

Een correcte regel heeft de volgende vorm:

doelklasse(x) Ř conditie(x)

1.1.3.2. Deterministische patronen versus waarschijnlijkheidspatronen

Bij data mining wordt gebruikt gemaakt van databases om patronen te ontdekken. Een database is een registratie van een deel van de werkelijkheid en bevat meestal vrij veel fouten. Bovendien zullen niet alle gegevens beschikbaar zijn of kan het probleemgebied zelf inherent onzeker zijn. Het merendeel van de patronen in een database zullen dus niet exact of deterministisch zijn maar statistisch of waarschijnlijk.

Dergelijke waarschijnlijkheidsregels zijn identiek aan de deterministische regels die hiervoor werden besproken maar worden aangevuld met een waarschijnlijkheidsmaat.

 

Vb.

doelklasse(x) ř conditie(x) met zekerheid van y %

conditie(x) ř doelklasse(x) met zekerheid van y %

doelklasse(x) Ř conditie(x) met zekerheid van y %

Wanneer een karakteristiek patroon slechts voor een deel van de voorbeelden in de doelklasse geldt spreken we dus over een karakteristieke benaderingsregel of een karakteristieke waarschijnlijkheidsregel.

Classificatieregels die slechts een deel van de voorbeelden die aan de voorwaarde voldoen correct classificeren noemen we discriminerende benaderingsregels of waarschijnlijke classificatieregel.

Aangezien de meeste regels benaderingsregels zijn, wordt echter meestal gewoon de terminologie ‘karakteristieke patronen en classificatiepatronen’ gebruikt. Wanneer de patronen correct of compleet zijn, dan worden ze expliciet deterministisch genoemd.

1.1.3.3. Detecteren van afwijkingen

We kunnen ook geÔnteresseerd zijn in het ontdekken van afwijkende gevallen. Afwijkingen kunnen immers wijzen op interessante gevallen, fraude of fouten in de gegevens.

Alle methoden voor het vinden van dergelijke patronen hebben een bepaalde aanpak gemeen, namelijk het zoeken naar significante verschillen tussen een observatie en een referentie. De observatie is gewoonlijk een veldwaarde of een combinatie van veldwaarden. De referentie kan een andere observatie zijn, een waarde afkomstig uit domeinkennis of een waarde berekend door middel van een model.

Vb.

In (54) beschouwt men afwijkingen als een indicatie van fouten. Wanneer een ontdekte regel geldt voor 99 van de 100 gevallen dan zal dat ene geval dat niet voldoet aan de regel verrassend en mogelijk ongepast zijn. Het ontdekken van dergelijke afwijkingen of anomalieŽn is een nuttige aanvulling op het ontdekken van karakteristieke regels en classificatieregels.

1.1.3.4. SequentiŽle patronen

Bij classificatieproblemen wordt een poging ondernomen te voorspellen tot welke klasse een object behoort. SeriŽle patronen daarentegen worden gebruikt om een toekomstig object te creŽren De voorspellingstaak is dus de volgende:

Net zoals bij de voorgaande patroontypes kan ook hier weer gesproken worden van 2 subtypes:

Vb.

Vervolledigen van de reeks ‘abababababababababa...’

Vb.

Voorspellen van het weer.

Een methode die op efficiŽnte en betrouwbare manier sequentiŽle voorspellingspatronen kan afleiden zou nuttig zijn voor het voorspellen van het weer, aardbevingen, de index, beursnoteringen, enz..

Een veel gebruikte methode is gebaseerd op het omzetten van een sequentieel patroon in een classificatieprobleem met behulp van een window.

Vb.

Een sequentiŽle dataset

Attribuut A Attribuut B

record 1 A1 B1

record 2 A2 B2

record 3 A3 B3

... ... ...

record m Am Bm

Het doel is het voorspellen van de waarde van attribuut Am+1, op basis van de attribuutwaarden van de x voorgaande records. De keuze van x wordt ook wel de keuze van een window genoemd en bepaalt het aantal relevante records. Het kiezen van een window komt overeen met het omzetten van een sequentieel patroon in een classificatiepatroon.

Vb.

De bovenstaande dataset omgezet met behulp van een window 2

onafhankelijke attributen afhankelijk attribuut

dummy record 1 - - - - A1

dummy record 2 - - A1 B1 A2

dummy record 3 A1 B1 A2 B2 A3

dummy record 4 A2 B2 A3 B3 A4

dummy record 5 A3 B3 A4 B4 A5

... ... ... ... ... ...

dummy record m Am-2 Am-2 Am-1 Bm-1 Am

dummy record m+1 Am-1 Bm-1 Am Bm Am+1

Elke record in de nieuwe dataset is dus samengesteld uit de waarde van attribuut A, gekoppeld aan de attribuutwaarden van de 2 voorgaande records in de originele dataset. Een dergelijke dataset kan dan als input dienen voor een classificatiealgoritme.

Een voorbeeld van een algoritme dat sequentiŽle patronen kan ontdekken in sequenties van objecten is OBSERVER-II. Meer details over de werking van OBSERVER-II kan je vinden in (70) en in deel 2.3.7. De overheid is een voorbeeld opgenomen van een toepassing van OBSERVER-II voor het voorspellen van gemiddelde temperaturen.

1.1.4. Kennis

Niet alle ontdekte patronen zijn ook kennis. In (10) stellen Frawley en Piatetsky-Shapiro dat patronen aan de volgende voorwaarden moeten voldoen vooraleer we over kennis kunnen spreken:

Begrijpelijk

De ontdekte kennis moet op een gepaste manier voorgesteld worden. Dit betekent dat alhoewel de ontdekte kennis niet altijd rechtstreeks door mensen moet gebruikt worden, ze wel voor die mensen verstaanbaar moet zijn.

Vb.

Correct

De ontdekte patronen vormen een vereenvoudigde beeld van de database. De mate waarin dit portret onvolledig, onjuist of onzeker is moet blijken uit een maatstaf van (on)zekerheid. Wanneer een patroon niet voldoende zekerheid biedt is het ongegrond en niet te beschouwen als kennis.

Interessant

De ontdekte patronen moeten interessant zijn voor de gebruiker. Dit houdt in dat de ontdekte patronen nieuw en bruikbaar moeten zijn en dat het ontdekkingsproces niet triviaal mag zijn.

Nieuw

Of een patroon nieuw is hangt af van het referentiekader waarin men werkt. Men kan als vergelijkingspunt zowel de kennis reeds aanwezig in het systeem als de kennis van de gebruiker gebruiken.

Vb.

Een systeem kan het volgende patroon ontdekken

Als ‘in-fout-bij-ongeluk = Ja’ Dan ‘Leeftijd > 16’

Voor het systeem is dit patroon nieuw zijn en dus nuttig terwijl het voor de gebruiker voor de hand liggend en oninteressant is.

Nuttig

Ontdekte patronen moeten nuttig zijn, d.w.z. dat ze een bijdrage moeten leveren tot de realisatie van de doelstellingen van de gebruiker.

Niet triviaal

De meeste databases bevatten ontelbare nieuwe en bruikbare patronen. Wanneer deze patronen eenvoudig kunnen worden berekend worden ze echter niet als kennis beschouwd.

Vb.

1.1.5. Inzicht verschaffen in het probleemdomein

Succesvolle interactie met zijn omgeving hangt samen met de mate waarin men toekomstige toestanden van een omgeving kan voorspellen en de mate waarin men veranderingen in de omgeving begrijpt.

voorspellen:

begrijpen:

Data miningsystemen worden gebruikt om patronen te herkennen in databases. Deze databases bevatten informatie over een klein, goed afgebakend deel van de omgeving.

Vb.

Wanneer in deze databases interessante patronen ontdekt worden hoopt men dat deze patronen ook kunnen gebruikt worden om dat deel van die omgeving te voorspellen en te begrijpen. Hierbij worden dus twee veronderstellingen gemaakt:

1. Er kunnen patronen gevonden worden.

2. De ontdekte database patronen kunnen veralgemeend worden.

Beide veronderstellingen hebben geleid tot verschillende experimenten die uitvoerig beschreven worden in de vaktijdschriften. Het besluit van de meest experimenten is dat deze veronderstellingen waar zijn wanneer:


1.2. Data mining, het samengaan van verschillende technieken

Data mining is geen eenvoudig probleem. De ontwikkeling van data miningalgoritmes vereist de samenwerking van specialisten in verschillende vakgebieden.

De principes achter data mining zijn niet nieuw. De gebruikte technieken zijn al jaren bekend. Veelal gaat het om een mix van technieken uit de kennistechnologie (zelflerende technieken) en de statistiek.

1.2.1. Data mining en huidige databasemanagementsystemen

1.2.1.1. Tekortkomingen van huidige DBMS’en

Bedrijven en overheidsinstellingen verzamelen gegevens omdat ze een potentieel belangrijke bron van informatie kunnen zijn en een competitief voordeel kunnen opleveren. Het opstellen van queries en het analyseren van de gegevens om deze waardevolle informatie te ontdekken is echter een moeilijke taak.

We kunnen de mogelijkheid die SQL biedt om gevallen die aan een bepaalde conditie voldoen uit een database te filteren als ‘discovery’ beschouwen omwille van het feit dat we hiermee interessante en bruikbare statements kunnen produceren. Het nadeel is echter dat deze technieken niet zelfstandig kunnen beslissen welk berekeningen de moeite waard zijn en niet kunnen evalueren wat de kwaliteit is van de gevonden patronen. Dit betekent dat de bruikbaarheid van de resultaten afhangt van de a priori veronderstellingen en hypothesen van de gebruiker. De gebruiker moet dus een query definiŽren en op basis van het verkregen resultaat conclusies trekken en de query eventueel verfijnen of veralgemenen. Een dergelijke aanpak, ook wel ‘data dredging’ of baggeren naar kennis genoemd, is enorm tijdrovend en niet haalbaar voor grote databases.

1.2.1.2. Wat kunnen de huidige DBMS’en bijdragen aan een efficiŽnt data mining tool

Een eerste voordeel van het gebruik van databases is dat de gegevens op een gestructureerde manier beschikbaar zijn.

Een tweede voordeel is dat het DBMS procedures voor het vlot opslaan, raadplegen en wijzigen van gegevens voorziet.

Bovendien kan een DBMS ook een oplossing bieden voor ťťn van de grootste obstakels bij het toepassen van machine learning technieken op databases: de grootte van de database. De grootte van de database heeft een invloed op de kost van de kwaliteitsevaluatie van een regel en voor de grootte van de zoekruimte. Enkele voorbeelden zijn:

1.2.2. Data mining en machine learning

1.2.2.1. Verschillen tussen een machine learning en een data miningomgeving

Machine learning

ArtificiŽle intelligentie of AI is het deelgebied van de informatica dat zich bezig houdt met de ontwikkeling van computerprogramma’s die resultaten behalen waarvoor men menselijk gedrag nodig zou achten (87). Machine learning (ML) of knowledge discovery (KD) is het deel van het AI onderzoek naar het automatiseren van inductieve leerprocessen of het door de computer ondersteund afleiden van omgevingsmodellen. Een machine learning systeem werkt met een kleine set van zorgvuldig gekozen laboratoriumgegevens die op twee manieren verzameld worden.

Experimenten

Het experimenteel verzamelen van trainingsvoorbeelden heeft de volgende voordelen:

Observatie

De onderzoekers kunnen niet kiezen welke situaties ze zullen creŽren maar wel welke observaties ze zullen maken.

Data mining

Data mining is een variante van machine learning waarbij de omgeving geobserveerd wordt door grote databases. De voordelen van experimenten of observaties bestaan niet voor een data miner. Data mining werkt per definitie met historische gegevens (archiefgegevens).

Dit betekent dat een data miner:

De gegevens in real-world databases zijn:

Bovendien zijn patronen in een bedrijfsomgeving meestal wazige verbanden i.p.v. precieze mathematische verbanden zoals we die bijvoorbeeld vinden in natuurwetenschappelijke domeinen.

1.2.2.2. Gevolg

Alhoewel het raamwerk van machine learning en data mining grotendeels hetzelfde is, zijn er dus enkele fundamentele verschillen tussen wetenschappelijke gegevens en bedrijfsgegevens en de te ontdekken patronen.

Figuur 2 Gelijkenis tussen machine learning en data mining

Een eerste gevolg is dat het ontdekken van regelmatigheden in een databaseomgeving moeilijker en delicater is dan in een machine learningomgeving. De bestaande machine learningalgoritmes moeten aangepast worden voor real-world data miningtoepassingen. Wetenschappelijke ontdekkingssystemen kunnen dus niet zonder meer gebruikt worden voor het ontdekken van kennis in databases.

Bovendien kan men niet verwachten dat met een niet ideale input (real-world databases), ideale resultaten kunnen worden behaald. De patronen ontdekt door data miners zullen geen prestigieuze, deterministische regelmatigheden zijn, maar ‘zwakke’ waarschijnlijkheidsregels. Bij machine learning wordt aangenomen dat een bepaald attribuut perfect kan worden beschreven in functie van de andere attributen, is dit zelden waar voor problemen in de werkelijke wereld. Dit wil zeggen dat de gekozen attributen elkaar, in het beste geval, onvolledig specificeren.

1.2.2.3. Wat kan machine learning bijdragen aan data mining

Machine learning heeft een lange traditie wat betreft het ontwerpen van en experimenteren met kennis, representaties en zoekstrategieŽn. Dit heeft verscheidene efficiŽnte algoritmes opgeleverd die succesvol zijn in het leren van eenvoudige patronen en die getest zijn in een grote variŽteit van applicaties.

Ondanks het feit dat er heel wat werk moet verricht worden om machine learningalgoritmes aan te passen voor data miningdoeleinden, vormt de ervaring, die is opgebouwd met machine learning, een goede basis voor het verdere data miningonderzoek.

1.2.3. Data mining en statistiek

1.2.3.1. Tekortkomingen van zuiver statistische methoden

Alhoewel statistiek een goede theoretische basis is voor gegevensanalyse (vb. gemiddelden, variatie, correlatiecoŽfficiŽnten, regressieanalyse en multidimensionele clusteranalyse) is een puur statistische aanpak ontoereikend.

Een eerste nadeel van statistische methoden is het feit dat ze niet flexibel genoeg zijn. Statistische analyse is sterk afhankelijk van en gelimiteerd tot het gekozen distributiemodel (vb. standaard normale distributie) en kunnen moeilijk verfijnd worden. Bovendien moet de keuze van het statistisch model en de distributiefunctie gebeuren op basis van een ‘educated guess’, omwille van het grote aantal en de mogelijke waarden van de attributen en het bestaan van een flinke natuurlijke variatie en diversiteit in de gegevens.

Statistische analyse vraagt teveel werk van de gebruiker, maakt gegevensanalyse omslachtig en resulteert vaak in overdonderende en moeilijk te interpreteren resultaten. Dit alles verkleint de kans dat er iets interessant gevonden wordt.

Twee bijkomende nadelen in het kader van data mining zijn dat:

1.2.3.2. Bijdrage van statistiek tot data mining

De resultaten van machine learningalgoritmes kunnen worden verbeterd wanneer we inzien dat de verbanden in de gegevens eigenlijk waarschijnlijk van aard zijn. Bij het zoeken naar dergelijke verbanden lijkt de keuze voor statistische technieken voor de hand liggend

De voordelen van het integreren van statistische methoden in machine learning zijn de volgende: