4. Robuuste algoritmes


Zoals reeds beschreven in hoofdstuk 1 zijn machine learningtechnieken niet zonder meer toepasbaar voor data mining. Ze zijn immers bedoeld voor kleine, ruisvrije datasets. Machine learningalgoritmes moeten dus aangepast worden, robuuster gemaakt worden.

Een eerste aanpassing heb ik in het vorige hoofdstuk reeds aangehaald, namelijk het gebruik maken van domeinkennis en sturing door de gebruiker. Algoritmes moeten hun beslissingen over clusteren, partitioneren en generalisatie- en specialisatieoperaties baseren op domeinkennis om tot significante en nuttige ontdekkingen te komen op een aanvaardbare tijd. Maar domeinkennis alleen is niet genoeg. De probleemdomeinen waar data miningsystemen zullen moeten werken zijn veel complexer en veel vijandiger dan de relatief eenvoudige, wetenschappelijke toepassingen waarvoor machine learning traditioneel gebruikt wordt.

Een eerste bijkomende vereiste is dat algoritmes zoveel mogelijk verschillende types patronen moeten kunnen ontdekken. Dit betekent dat een algoritme moet werken met een zo krachtig mogelijk representatie- formalisme. Nadeel is wel dat een krachtiger representatieformalisme ook meer rekenwerk en dus een grotere complexiteit met zich meebrengt, hetgeen de afhankelijkheid van goede heuristieken doet toenemen.

Ten tweede moet een data miningalgoritme ook een oplossing bieden voor de inputproblemen die zich kunnen voordoen bij het leren in databases. Databases zijn namelijk vaak onvolledig, bevatten slechts een klein deel van alle mogelijke gevallen, kunnen enorm groot en dynamisch zijn en bevatten foute en onnauwkeurige gegevens. De belangrijkste oplossing voor deze problemen is het omvormen van de veelal deterministische machine learningtechnieken tot statistische data miningsystemen.


4.1. Representatieformalismen

Als een computer moet zoeken naar een patroon, dan moeten we natuurlijk wel vertellen wat een patroon is. We moeten dus een taal definiŽren waarin elke expressie een patroon is. Zo'n taal heet een representatieformalisme. In deze taal moet de gevonden kennis worden voorgesteld.

De keuze van representatieformalisme heeft een invloed op de regels die gevonden kunnen worden. Als er een patroon in de database zit dat niet in het formalisme is uit te drukken, dan zal de computer het niet vinden. Vanuit dit standpunt is het dus wenselijk dat een representatieformalisme zo krachtig mogelijk is. Anderzijds is het ook zo dat een krachtiger representatieformalisme resulteert in een grotere zoekruimte en dus in langere zoektijden. Men moet dus opnieuw volledigheid afwegen t.o.v. efficiŽntie. Als representatieformalisme willen we dus niet de krachtigste taal, maar een taal die zo krachtig mogelijk is onder de voorwaarde dat patronen binnen een aanvaardbare tijd gevonden worden (9).

Bovendien moeten we er rekening mee houden dat de manier waarop kennis gerepresenteerd wordt een grote invloed uitoefent op hoe die kennis waargenomen en gebruikt zal worden.

4.1.1. Propositionele representaties

CNF en DNF

Propositionele representaties hebben de vorm van een logische formule, bestaande uit attribuutwaarde-condities. Dit kan een formule in de Conjunctieve Normaal Vorm (CNF) zijn, d.w.z. een conjunctie van clauses, waar clauses disjuncties van attribuutwaardecondities zijn.

Vb.

‘(kleur = rood ŕ kleur = groen) Ŕ vorm = cirkel’

Een alternatief is de Disjunctieve Normaal Vorm (DNF), een disjunctie van termen, waar termen conjuncties van attribuutwaardecondities zijn. CNF presteert echter beter dan DNF, de gegenereerde beschrijvingen zijn kleiner dan de DNF-representaties voor dezelfde leertaken.

Vb.

‘(kleur = rood Ŕ vorm = cirkel)ŕ (kleur = groen Ŕ vorm = cirkel)’

Beslissingsbomen

Een beslissingsboom (decision tree) is een eenvoudige kennisrepresentatie die op succesvolle manier wordt toegepast door verschillende supervised machine learningsystemen (vb. ID3).

Een beslissingsboom classificeert voorbeelden in een eindig aantal klassen. Knopen in de boom zijn attributen, de pijlen zijn mogelijke attribuutwaarden of sets van attribuutwaarden en de bladeren zijn gemerkt met de verschillende klassen.

Een object wordt geclassificeerd door het volgen van een pad naar de voet van de boom, door bij elke knoop de pijl te nemen die overeenstemt met de waarde van het attribuut in het object.

Het voordeel van beslissingsbomen is dat ze een natuurlijke, begrijpelijke representatie geven van de ontdekte kennis en dat ze een efficiŽnte sequentiŽle verwerking mogelijk maken.

Een nadeel van beslissingsbomen is dat ze voor grote data miningprojecten zeer groot kunnen worden zodat ze moeilijk te interpreteren zijn door de gebruiker of domeinexpert. De vroege beslissingsboom-algoritmes zijn ook niet ontworpen om te werken met ontbrekende data, hetgeen leidt tot te grote en complexe beslissingsbomen.

 

Figuur 17 Voorbeeld van een beslissingsboom

Produktieregels

Produktieregels of conditie-actieparen zijn een eenvoudige vorm van propositionele regels. Het zijn alsdan-regels waar het conditionele gedeelte bestaat uit een propositionele expressie (bv. een expressie in CNF) of simpelweg uit een term en waarbij het rechtergedeelte een klasse of actie is.

Elk pad in een beslissingsboom kan ook als een produktieregel geschreven worden.

Vb.

als vooruitzicht = zonnig en vochtigheid = hoog dan klasse = negatief

als vooruitzicht = regenachtig en winderig = waar dan klasse = negatief

default klasse = positief

Voordelen van produktieregels

Decision lists

Een andere propositionele representatie is de beslissingslijst. Alle kennisstructuren in de vorm van beslissingsbomen, DNF en CNF kunnen omgezet worden naar beslissingslijsten. Een beslissingslijst is een lijst van paren.

Vb.

(f1,C1),(f2,C2),(f3,C3), ... ,(fr,Cr)

Elke fi duidt een elementaire descriptie aan, en elke Ci stelt een klasse voor, en de laatste descriptie fr de defaultklasse aanduidt. Een beslissingslijst kan dus gezien worden als een uitgebreide ‘if f1 then C1& elseif f2 then C2 ... else Cr’ regel waarbij de uitzonderingen vooraan komen.

Het nadeel van beslissingslijsten is dat uitzonderingen globaal gedefinieerd zijn.

 

Ripple-down rulesets

Ripple-down rulesets komen tegemoet aan de tekortkomingen van beslissingslijsten, ze laten toe uitzonderingen lokaal te definiŽren. Ripple-down rulesets zijn geneste if-then regels.

Vb.

if fi then

if fj then Cj

else Ci

else Cj

Ripple-down rulesets zijn gebaseerd op de observatie dat mensen overweg kunnen met het verwerven en onderhouden van complexe kennisstructuren door veranderingen aan te brengen in een specifieke context zodat het effect van de veranderingen lokaal is.

Nadelen van propositionele representaties

Propositionele representaties leggen sterke beperkingen op aan de vorm van de verbanden en patronen die kunnen voorgesteld worden. Patronen gedefinieerd in functie van relaties tussen objecten of attributen kunnen niet gerepresenteerd worden.

Vb.

Een klasse bestaande uit alle personen met ‘identieke voor- en familienaam’.

Met een propositionele representatie zouden alle personen met een identieke voor- en familienaam opgesomd worden. Een krachtiger representatie zou ons toelaten te stellen dat elke persoon waar ‘voornaam = familienaam’ tot die bepaalde klasse behoort, om zo de ware aard van die klasse te vatten.

Het is moeilijk om domeinkennis in het leerproces te gebruiken.

4.1.2. First Order Logic (FOL)

Algemeen

De tekortkomingen van propositionele representaties kunnen overwonnen worden door gebruik van een krachtiger representatie. First Order Logic of kortweg FOL is zo’n krachtiger representatieformalisme.

Vb.

Is_red(car)

Is(car,red)

Vb.

All cars have wheels.

For_all x (car(x) ŗ has_wheels(x))

Er bestaan enkele uitbreidingen bij FOL die erg bruikbaar kunnen zijn voor het representeren van kennis in een data miningsysteem.

Voor- en nadelen van FOL

Een krachtige representatie zoals FOL laat ons toe eenvoudige beschrijvingen te vinden voor klassen die een zeer complexe beschrijving nodig zouden hebben in een minder krachtige representatie. Langs de ene kant vermindert een krachtiger formalisme dus de complexiteit van het resultaat omdat het systeem eenvoudige beschrijvingen kan vinden, maar daartegenover staat dat wanneer we een meer expressief formalisme gebruiken, er meer verschillende beschrijvingen geconstrueerd kunnen worden, met als gevolg dat de beschrijvingsruimte vergroot en het vinden van de juiste beschrijving moeilijker wordt.

Andere voordelen van FOL:

4.1.3. Gestructureerde representaties

Semantische netten

Een semantisch netwerk is een grafiek waar de knooppunten concepten voorstellen en de pijlen relaties voorstellen tussen deze concepten.

Vb.

John is getrouwd met Mary.

Mary heeft rood haar.

John en Mary zijn beide mensen.

Alle mensen zijn zoogdieren.

Figuur 18 Voorbeeld van een semantisch net

Er bestaan twee vormen van verbanden:

Een semantisch netwerk kan eenvoudig omgezet worden in FOL:

Vb.

spouse(mary,john).

haircolor(mary,red).

human(john).

human(mary).

"X.human(X) ģ mammal(X).

Het belangrijkste voordeel van semantische netten is dat alle informatie gerelateerd aan een object eenvoudig gevonden kan worden door het volgen van alle links van dit object. Wanneer semantische netten gebruikt worden voor data mining, is elk voorbeeld in de trainingsset een semantisch net. Operaties op de voorbeelden bestaan uit grafiekmanipulaties. Patronen hier zijn subgrafieken die gedeeld worden door alle voorbeelden van dezelfde klasse.

Frames en schemata

Een frame of schema is een gestructureerd object, bestaande uit een naam en benoemde attributen - slots - gevuld met waarden voor een bepaald voorbeeld.

Vb.

Alle informatie over Mary kan in een frame met 4 slots gestopt worden.

framename person

slot 1 slot 2 slot 3 slot 4 isa: mammal name: Mary spouse: John haircolor: red

Bij deze slots horen facetten:

Slots en hun waarden, gedefinieerd op hogere niveaus in de hiŽrarchie worden overgeŽrfd door de lagere niveaus maar kunnen op een lager niveau toch met andere waarden gevuld worden. Op het hogere niveau heeft men dus defaultwaarden en deze kunnen voor uitzonderingsgevallen op lagere niveaus vervangen worden.

Hoewel frames voorgesteld kunnen worden in FOL, geven ze een beter inzicht in de structuur van de kennis dan een set van - logisch equivalente maar niet gestructureerde - eerste orde predikaten.

Voorbeelden van leersystemen die gebruik maken van frames:

Voordelen van gestructureerde representaties

Alhoewel gestructureerde representaties niet krachtiger zijn dan FOL, voorzien ze ons wel met een meer begrijpelijke representatie door:

Bovendien is een data miningsysteem zoals KATE efficiŽnt. Attributen of slots horen slechts bij het object waarvoor ze zinvol zijn. Dit betekent dat er minder zinloze voorwaarden geŽvalueerd moeten worden.

Vb.

Het attribuut ‘baard’ zal horen bij het object ‘man’ terwijl het attribuut ‘zwanger?’ zal horen bij het object vrouw.

4.1.4. Neurale netwerken

Een neuraal netwerk is een geheel van onderling verbonden neuronen. Deze neuronen of verwerkingseenheden zijn geordend in 3 of meer lagen: een inputlaag, ťťn of meerdere verborgen lagen en een outputlaag. Het aantal neuronen in de inputlaag komt overeen met het aantal onafhankelijke attributen. In het geval de output een continue waarde is volstaat ťťn outputneuron per afhankelijk attribuut. Wanneer het afhankelijke attribuut discrete waarden kan aannemen, moet ťťn outputneuron voorzien worden per mogelijke discrete waarde. Het geheel van deze lagen, neuronen en connecties noemt men de topologie van een neuraal netwerk.

Voorbeelden van netwerktopologieŽn:

Figuur 19 Voorbeeld van een neuraal netwerk

Een connectie tussen twee neuronen wijst erop dat de output van het eerste neuron een input is voor het tweede neuron. Met elke connectie is een gewicht gelieerd dat bepaalt in welke mate de output van het eerste neuron, het tweede neuron beÔnvloedt.

De activeringsfunctie van een neuron berekent de gewogen som van de inputs, trekt daar een drempelwaarde q van af en geeft de resulterende waarde door aan de volgende neuronen in het netwerk.

Figuur 20 Voorbeeld van een neuron en een activeringsfunctie

De kennis die in een neuraal netwerk zit bestaat dus uit:

Voor- en nadelen

Kennis gegenereerd met neurale netwerken is niet expliciet voorgesteld in de vorm van regels of conceptuele patronen maar zit impliciet in het netwerk zelf als gewichten en drempelwaarden. Daarom zijn neurale netwerken minder geschikt voor probleemgebieden waar de ontdekte kennis door mensen geverifieerd en geÔnterpreteerd moet worden. Daarom wordt het gebruik van neurale netwerken door sommige onderzoekers niet als data mining beschouwd.

Toch zijn er enkele redenen om een neurale netwerk als representatieformalisme te verkiezen.

Neurale netwerken zijn vooral geschikt voor problemen waarbij het ongepast of gecompliceerd is om de kennis voor te stellen in de vorm van regels.

 

Figuur 21 Patroon geschikt voor representatie m.b.v. regels (links) en een patroon geschikt voor representatie m.b.v. een neuraal netwerk (rechts)

Kennis in neurale netwerken kan enorm snel in een operationeel systeem gebruikt worden. Het volstaat het netwerk te trainen tot het een aanvaardbaar niveau behaalt en daarna de gewichten te bevriezen.

Bovendien bestaat er onderzoek naar het transformeren van neurale kennis naar een vorm die beter geschikt is voor mensen. Voorbeelden hiervan zijn o.a. sensitiviteitsanalyse en 3-dimensionele visualisatie.

Sensitiviteitsanalyse (76)

Eťnmaal het netwerk getraind is en de gewichten bevroren zijn wordt voor elke input het bereik, het minimum en het maximum berekend. De waarde van elke input wordt daarna gevarieerd terwijl de andere factoren constant gehouden worden. De hypothetische waarden worden dan door het netwerk gehaald om de verwachte output te berekenen. De uitkomst van het netwerk wordt dan geplot t.o.v. de verschillende waarden van de input. Op basis van deze grafieken wordt dan bekeken hoe en waar de uitkomst afhankelijk is van die factor.

3-dimensionele visualisatie

Hierbij wordt de sensitiviteitsanalyse uitgebreid tot een 3-dimensionele techniek. De 2 meest invloedrijke inputvariabelen worden geselecteerd daarna worden alle mogelijke combinaties van deze inputvariabelen in een 3-dimensionele grafiek uitgezet t.o.v. de output.


4.2. De database als beperkende factor

Een belangrijke beperkende factor voor data mining naast de keuze van het representatieformalisme is het feit dat we werken met databases. Vele algoritmes uit machine learning blijken moeilijk toepasbaar omwille van de speciale kenmerken van real-world databases:

Holsheimer en Siebes (9) verdelen de data mining problemen onder in 3 grote types die ik hier grotendeels zal overnemen:

1. beperkte informatie: niet alle informatie nodig voor het classificeren van een object is voorhanden.

2. gegevenscorruptie: de beschikbare informatie kan corrupt zijn of gedeeltelijk ontbreken

3. de grootte en het dynamische karakter van database

4.2.1. De grootte van de database

Machine learningsystemen gebruiken kleine trainingssets, een duizendtal objecten wordt reeds als veel beschouwd. De databases waarin data mining patronen tracht te ontdekken daarentegen, zijn over het algemeen enorm groot, zowel qua hoeveelheid informatie per object als qua aantal objecten in de database.

De snelle groei van de hoeveelheid gegevens beschikbaar in de wereld is dus niet alleen een stimulans voor maar het creŽert ook ťťn van de grootste uitdagingen van KDD:

4.2.1.1. De hoeveelheid informatie per object

De meeste databases bevatten vele attributen.

Vb.

Het RADIX/RX project dat de ARAMIS (American Rheumatism Association Medical Information System) database gebruikt. Deze database bevat informatie over de klinische bezoeken van patiŽnten:

Eerst en vooral dienen we op te merken dat het een voordeel is dat er zoveel informatie voorhanden is, omdat er dan meer kans bestaat dat er werkelijk patronen bestaan in de database.

Daartegenover staat echter het feit dat een groter aantal attributen ook betekent dat het aantal mogelijke beschrijvingen, en dus de grootte van de beschrijvingsruimte, toeneemt. Het aantal beschrijvingen hangt immers af van het aantal attributen en de grootte van de attribuutdomeinen. Bij het gebruik van set-descripties ( vb. kleur ő {rood,geel}) is het aantal beschrijvingen ongeveer gelijk aan 2x waar x = de som van de domeingroottes van de attributen.) Het is duidelijk dat voor een realistische database (waar x > 1000), de beschrijvingsruimte enorm groot wordt.

Oplossing

De beschikbare attributen zijn waarschijnlijk niet allemaal even relevant. Waarschijnlijk zitten er vrij veel overbodige gegevens tussen. Dergelijke redundantie kan 2 vormen aannemen:

De relevantie van een attribuut is afhankelijk van wat men wil ontdekken. De meeste algoritmes berekenen de informatiewinst die kan worden bekomen door het toevoegen van een voorwaarde op een bepaald attribuut met het oog op de gewenst classificatie. Sommige algoritmes maken zo’n berekening zelfs voor elk attribuut-waardepaar. Het is duidelijk dat wanneer we over zeer veel attributen beschikken die elk een aantal verschillende waarden kunnen aannemen, dit enorm veel rekenwerk met zich meebrengt. We moeten dus proberen het aantal relevante velden in de trainingsset te maximaliseren en het aantal irrelevante velden te minimaliseren.

Soms zijn attributen bovendien slechts relevant voor een bepaald deel van de trainingsset.

Vb.

Het attribuut ‘zwanger?’ is enkel relevant voor voorbeelden waarvoor geldt: ‘geslacht = vrouw’.

Het algoritme moet dus ‘weten’ dat bepaalde attributen slechts beperkt toepasselijk zijn. Dit is bijvoorbeeld mogelijk met behulp van frames of andere gestructureerde representaties.

De volgende vorm van redundantie is gegevensredundantie: attributen die afhankelijk zijn van of die beperkt worden door andere attributen.

Vb

Zulke afhankelijkheden kunnen opnieuw ontdekt worden als sterke deterministische patronen. Een dergelijke aanpak noemen we de ‘bootstrapping approach’. Nadeel is echter dat computertijd besteed wordt aan het ontdekken van kennis en patronen die eigenlijk reeds gekend zijn, hetgeen het zoekproces onnodig complex maakt. EfficiŽnter is het wanneer het data miningsysteem rechtstreeks over informatie over afhankelijkheden tussen attributen kan beschikken door het raadplegen van een knowledge base of de data dictionary.

4.2.1.2. Het aantal objecten in de database

Gedurende het zoekproces moet de kwaliteit van elke gegenereerde descriptie gecontroleerd worden. Er moet statistisch gecontroleerd worden of een beschrijving echt een regelmatigheid in de gegevens beschrijft. Hiervoor moet het systeem o.a. beschikken over de volgende informatie:

Het berekenen van de kwaliteit van een regel vereist dus het raadplegen van de database en aangezien deze databases enorm groot kunnen zijn, is ook het verwerken van queries duur.

Oplossingen

Meerdere beschrijvingen

Het algoritme kan meerdere beschrijvingen tegelijk construeren zodat deze geŽvalueerd kunnen worden met behulp van ťťn enkele database-acces. In dit geval moeten we de I/O kost afwegen t.o.v. de CPU kost (7). We kunnen kiezen tussen een klein aantal database-accessen met telkens een grote processing-overhead per access of het beperken van de berekeningen per access en meer accessen uitvoeren.

Werken met samples

In het geval van grote databases met miljoenen records is een complete analyse van de data onmogelijk. De ontdekkingsalgoritmes moeten dan betrouwen op ťťn of andere vorm van ‘sampling’ waarbij enkel een deel van de data beschouwd worden.

 

Vb.

Het werken met samples heeft dezelfde gevolgen als werken met schaarse gegevens. Het voordeel t.o.v. schaarse gegevens is echter dat bij ‘sampling’ een intelligente selectie van records kan gebeuren en dat wanneer het systeem geen aanvaardbare resultaten boekt, de sample kan uitgebreid worden.

Sampling brengt echter een extra onzekerheid met zich mee omdat systeem zich ons slechts op een klein deel van de beschikbare gegevens kan baseren. Data miningsystemen moeten bij het kiezen van de sample dus steunen op statistische analyse die bepaalt hoeveel groter de sample zou moeten zijn om het gewenste niveau van vertrouwen in de resultaten te bereiken.

Conceptuele beperkingen

We kunnen de patronen beperken tot deze die gebruik maken van de door de gebruiker gedefinieerde concepten en concepthiŽrarchieŽn.

Gebruik maken van een beperkte model base

Enkel de types van functies die bestaan in de model base kunnen gevonden en/of gecreŽerd worden. De grootte van de zoekruimte is dus afhankelijk van de inhoud van de model base.

4.2.2. Beperkte informatie

De informatie waarover we beschikken is onvolledig:

4.2.2.1. Ontbrekende velden

De meeste bedrijfsdatabases zijn niet ontworpen voor data mining maar voor operationele doeleinden. Dit betekent dat in een database niet altijd alle mogelijke informatie wordt bijgehouden. We kunnen dus aannemen dat er attributen of eigenschappen bestaan die relevant zijn voor de classificatie maar die niet opgenomen zijn in de database. In dat geval is het onmogelijk een regel te vinden die elk object correct classificeert. Om correcte regels te ontdekken moeten we beschikken over alle mogelijke relevante informatie en om bijna correcte regels te ontdekken moeten we beschikken over zoveel mogelijk relevante informatie.

Vb.

De klantgegevens van een bank volstaan waarschijnlijk niet om regels of patronen af te leiden die kunnen helpen bij het voorspellen of iemand kredietwaardig is wanneer in deze gegevens het attribuut ‘salaris’ ontbreekt.

Vb.

Een KD-system voor het identificeren en uitleggen van verkoopverschillen tussen regionale divisies van een onderneming. Zonder expliciete informatie regionale demografie en markt-factoren, zijn relevante, betekenisvolle ontdekkingen zeer onwaarschijnlijk.

Gegeven een leerprobleem uitgedrukt in termen van een vaste set van attributen en klassen, dan wordt een trainingsset met voorbeelden die ruisvrij zijn, onbeslist (inconclusive) genoemd wanneer er geen set van regels bestaat die, gebruik makend van de beschikbare attributen, alle mogelijke voorbeelden correct klasseert.

Een eerste nadeel van dergelijke trainingssets is dat een aantal positieve en negatieve voorbeelden identiek kunnen zijn. In dat geval noemen we de trainingsset inconsistent en kan lijken alsof de beschikbare gegevens fout zijn.

Vb.

Veronderstel dat we een regel wensen te ontdekken voor het stellen van een malariadiagnose maar we beschikken over een patiŽnt-database die geen informatie bevat over het aantal rode bloedcellen. In een dergelijke database zullen patiŽnten zitten die voor alle beschikbare relevante velden identiek zijn maar voor wie toch een verschillende diagnose gesteld is. Het niet vinden van correcte regels zou men dan onterecht kunnen wijten aan fouten in de gegevens.

Een duidelijk teken van onbeslistheid is wanneer een data miningsysteem, getraind op basis van ruisvrije gegevens, perfecte classificatie behaalt voor de trainingsset maar slecht scoort bij classificatie van de testset. Dit duidt op ‘overfitted patterns’, patronen waarbij gebruik gemaakt wordt van irrelevante attributen of velden om toch een correcte classificatie te behalen.

Een voorbeeld van onbesliste datasets en overfitting bij ID3 (28)

Op de reparatieafdeling wordt op basis van de volgende heuristieken beslist wat vervangen moet worden wanneer ťťn van hun produkten gevallen is:

IF widget was dropped AND fell less than 5 ft. THEN replace casing.

IF widget was dropped AND fell more than 5 ft. THEN replace widget.

Stel nu dat we op basis van onderstaande dataset en met behulp van ID3 een beslissingsboom willen afleiden. Merk op dat we niet beschikken over het attribuut ‘hoogte’.

 

Tabel 23 Dataset voor de diagnose van widget-problemen

Case Model Temp. Day Customer Abuse Outcome: replace

1 Basic High M Dropped Casing

2 Ultima Low Tu Dropped Casing

3 Excel Low W Dropped Casing

4 Excel High W Dropped Widget

5 Basic Low Th Dropped Widget

6 Ultima Low F Dropped Casing

7 Basic Low M Kicked Woozle

8 Ultima Low M Kicked Nozzle

De resulterende beslissingsboom maakt, om perfecte classificatie te behalen gebruik van irrelevante attributen en is dus ‘overfitted’. Een dergelijke beslissingsboom is geen benadering van de werkelijke onderliggende regels en zal naar alle waarschijnlijkheid slecht scoren wanneer hij wordt toegepast op nieuwe gevallen.

Figuur 22 De bijbehorende ID3 beslissingsboom

We willen dus dat er niet langer rekening gehouden wordt met de irrelevante attributen en dat het specialisatie proces stopt bij de stippellijn. Dit levert de volgende waarschijnlijkheidsregel op:

IF (Customer abuse = dropped) THEN Fix = replace casing (67 %) AND Fix = replace widget (33%)

Oplossing

Jammer genoeg zijn onbesliste datasets niet zeldzaam in de industrie. De meeste diagnostische databases bevatten slechts een fractie van de informatie nodig om nieuwe gevallen correct te classificeren. Uit het voorgaande voorbeeld blijkt echter dat zulke datasets zeker niet nutteloos zijn.

In sommige gevallen kunnen we identificeren welke relevante attributen ontbreken en een poging ondernemen deze attributen alsnog te verzamelen. Het nadeel van een dergelijke aanpak is dat sommige relevante attributen gewoon onbekend of onmeetbaar zijn, dat het aantal relevante factoren te groot wordt of dat sommige attributen te duur of te risicovol zijn om te verzamelen.

Een tweede mogelijkheid is dat enkel correcte regels geselecteerd worden. Het specialisatie-generalisatieproces stopt wanneer er geen relevante attributen meer zijn en selecteert enkel patronen die juist ťťn klasse toewijzen aan elke combinatie van attribuutwaarden. Nadeel hiervan is dat veel waardevolle informatie niet gevonden zal worden.

De beste oplossing echter is het aanvaarden dat een regel aanleiding kan geven tot meerdere voorspellingen. In dit geval zijn we tevreden met niet-deterministische of waarschijnlijkheidsregels die een uitspraak doen over de kans dat een bepaald object tot een klasse behoort.

4.2.2.2. De trainingsvoorbeelden zijn vaak schaars

Wanneer een data miningsysteem een classificatieregel construeert moet het ontdekken welke de grenzen van een klasse zijn. De exacte locatie van die grenzen kan alleen onderzocht worden wanneer de database voorbeelden bevat die net binnen of buiten de klasse vallen - de zogenaamde near misses en near hits. In het ideale geval representeren de voorbeelden dus een groot deel van alle mogelijke gevallen in het universum. Spijtig genoeg representeren de feiten in een database over het algemeen slechts een kleine subset van alle mogelijke gedrag. De informatie in een database is vaak schaars wanneer je de eigenlijke data records vergelijkt met het bereik van mogelijke combinaties.

Vb. (21)

Een database met 40 attributen, gemiddeld kan elk attribuut 4 waarden aannemen.

Het totaal aantal mogelijke combinaties = 440 of 1025 records.

Een grote database kan bestaan uit zowat 106 of 107 records of 10 miljoen records.

Een eerste probleem hiermee is dat de grenzen van een klasse niet exact bepaald kunnen worden. Dit betekent dat we er niet zeker van kunnen zijn dat nieuwe gevallen, en vooral dan grensgevallen, correct geclassificeerd zullen worden.

Bovendien zullen patronen die gegeneraliseerd zijn op basis van een klein deel van het universum waarschijnlijk ook alleen maar gelden voor dat deel van het universum. We moeten dus een onderscheid kunnen maken tussen algemeen geldende patronen en patronen die het resultaat zijn van het feit dat slechts een beperkt aantal voorbeelden voorhanden zijn in de database. We willen dus een indicatie van geldigheid of validiteit van onze beschrijving. We willen de kans kennen dat een ontdekte regel een nieuw voorbeeld verkeerd classificeert.

Oplossing

Evaluatie op basis van de testset

Het testen van de ontdekte patronen met behulp van de testset geeft een idee van het generaliserend vermogen van het systeem en dus van de mate waarin de gebruiker het systeem kan vertrouwen.

Ockham’s razor

Naast de evaluatie op basis van de testset beschikken we ook nog over een andere vuistregel voor het evalueren van de geldigheid van een ontdekt patroon: Ockham’s razor. Wanneer we voor een bepaalde omgeving meerdere modellen kunnen maken zullen sommige ervan eenvoudiger zijn dan andere. We veronderstellen dan dat eenvoudige modellen juister zijn dan complexe modellen. De gedachtengang achter deze regel is dat wanneer er meerdere mogelijke uitleggen voor een bepaald fenomeen zijn, het zinvol is het eenvoudigste te kiezen omdat deze waarschijnlijk beter de werkelijke aard van het fenomeen vat.

Interactie

Sommige systemen kunnen in interactie treden met hun omgeving. Dergelijke systemen genereren interessante voorbeelden en leggen deze voor aan de gebruiker die dan de klasse moet bepalen. (vb. MARVIN)

Stratified samples

Ook hier kan het nemen van een selectieve sample een oplossing bieden. Wanneer patronen vooral getraind zijn op grensgevallen zal hun prestatie bij het classificeren van nieuwe grensgevallen aanmerkelijk beter zijn.

4.2.3. Gegevenscorruptie

Data mining is een leerproces dat gebruik maakt van real-world databases en ťťn van de hoofdkenmerken van dergelijke databases is dat de gegevens nooit helemaal correct zijn. Fouten in de waarden van attributen of in de klasse-informatie worden over het algemeen ‘noise’ of ruis genoemd. Gegevenscorruptie leidt tot een verminderd vertrouwen in de ontdekte regels.

4.2.3.1. Ruis: foute of onnauwkeurige gegevens

Jammer genoeg bevatten de meeste real-world databases foute of onnauwkeurige gegevens omwille van manuele collectie en invoer. Ruis vormt dus een belangrijk probleem voor data mining in real-world databases. Immers, regels die op basis van inexacte gegevens ontdekt worden zullen onvermijdelijk inexact zijn. Algoritmes moeten dus robuust genoeg zijn om in gegevens die niet perfect zijn toch patronen te ontdekken die niet exact maar wel bruikbaar zijn.

Voorbeelden van ruis:

Invloed van ruis op de ontdekte patronen

Wanneer we een karakteristiek patroon voor een klasse van een database met een aantal corrupte voorbeelden proberen te creŽren, dan zal dit patroon ook voor die corrupte voorbeelden gelden. Dit komt overeen met het probleem van ‘overfitted patterns’. Ook hier zal het algoritme gebruik proberen maken van irrelevante gegevens om toch een correcte classificatie te behalen. Dit is natuurlijk niet de bedoeling, daarom moeten we een manier vinden om de invloed van verminkte of corrupte voorbeelden te minimaliseren.

Invloed van ruis bij het classificeren van nieuwe gevallen

Eens de beschrijvingen geconstrueerd zijn kan men de classificatieregels gebruiken om de klasse van nieuwe objecten te bepalen. Aangezien patronen globale beschrijvingen zijn van data waarin een zekere redundantie verwerkt is, is het systeem tot op een zekere hoogte tolerant voor speling in die gegevens. Bij experimenten is gebleken dat zelfs het toevoegen van een aanmerkelijke hoeveelheid ruis resulteerde in een laag niveau van foute classificatie van nieuwe objecten.

Een interessant fenomeen was bovendien dat regels die afgeleid werden uit een corrupte trainingsset beter presteren bij het classificeren van gegevens met ruis dan regels die afgeleid werden van dezelfde maar ruisvrije trainingsset.

Quinlan concludeert hieruit dat het niet nuttig is teveel tijd te spenderen aan het vermijden van ruis wanneer verwacht wordt dat de te classificeren voorbeelden eveneens veel ruis zullen bevatten.

Oplossing

Toch is het niet de bedoeling te blijven werken met onjuiste of onnauwkeurige gegevens. Daarom moet aandacht besteed worden aan:

Vermijden van ruis

Een eerste mogelijkheid is het vermijden van fouten in de gegevens door het toepassen van strenge, gestandaardiseerde integriteitsregels.

Herkennen en negeren van ruis

Het basisidee van de aanpak voorgesteld door Quinlan is dat een kleine hoeveelheid exceptionele of buitengewone gegevens beschouwd kan worden als ruis en dus kan genegeerd worden.

Minimaliseren van de impact van ruis

Aanpassen van de algoritmes om overweg te kunnen met ruis

Een techniek die veel gebruikt wordt bij het opbouwen van beslissingsbomen is prepruning, inspelen op het stopcriterium. Men kan bijvoorbeeld beslissen dat een tak een minimum aantal gevallen moet bevatten vooraleer hij verder gesplitst kan worden.

Vb.

ASSISTANT (46)

Men kan ook gebruik maken van postpruning, het snoeien van de boom na constructie. Hierbij wordt afgewogen of een conditie kan verwijderd worden zonder een te grote vermindering van de classificatiejuistheid, m.a.w. de classificatiejuistheid moet na het schrappen van de conditie onder een door de gebruiker vastgestelde drempelwaarde blijven.

4.2.3.2. Ontbrekende attribuutwaarden

In real-world databases kan het zijn dat attribuutwaarden ontbreken. Toch zouden we willen dat:

Invloed op het opbouwen van beschrijvingen

Bij de constructie van beschrijvingen kunnen we ontbrekende waarden op vier manieren behandelen. We kunnen voorbeelden met ontbrekende gegevens gewoonweg verwijderen. Dit is echter geen goede oplossing omdat, net zoals bij ruis, patronen die ontdekt zijn op basis van onvolledige records beter presteren bij het classificeren van nieuwe, eveneens onvolledige records. Bovendien zou het verwijderen van alle records waarin waarden ontbreken bijdragen tot het probleem van de schaarsheid.

Een interactief systeem zou kunnen vragen de ontbrekende waarden in te vullen. Gezien de grootte van de datasets waarmee gewerkt wordt, is dit echter niet realistisch.

Een derde mogelijkheid is het vervangen van de ontbrekende waarden door de meest waarschijnlijke waarde.

En de vierde, en meest gebruikte oplossing is dat de ontbrekende waarden beschouwd worden als een aparte waarde, namelijk de waarde ‘unknown’.

Invloed op het classificeren van nieuwe voorbeelden

Wanneer we voorbeelden proberen te classificeren waarin attribuutwaarden ontbreken kunnen we toch proberen een niet deterministische of waarschijnlijke classificatie te genereren. Dit is geen probleem wanneer we de waarde ‘onbekend’ hebben toegevoegd aan elk attribuutdomein zoals hierboven werd gesuggereerd.

Een andere techniek is de volgende:

Hoe eenvoudig deze techniek ook mag lijken, hij geeft aanleiding tot een ‘very graceful degradation’ wanneer het aantal onbekende waarden toeneemt.

4.2.3.3. Dynamische gegevens en incrementeel leren

Wanneer databases frequent aangevuld en/of gewijzigd worden is het waarschijnlijk dat kennis die vroeger uit de database is afgeleid inconsistent of verouderd is. Dergelijke wijzigingen wijzen op een trend of op het wijzigen van de karakteristieken van objecten. Sommige data miningsystemen eisen dat in dit geval het algoritme opnieuw getraind wordt, hetzij op de volledige dataset, hetzij op een meer recente sample. Dit houdt in dat we het dure ontdekkingsproces van nul moeten herbeginnen hetgeen niet efficiŽnt is.

Een ideaal kennisontdekkingssysteem is dus incrementeel, het moet wat het reeds geleerd heeft, kunnen aanpassen aan nieuwe gegevens. Die nieuwe informatie kan bestaan uit nieuwe voorbeelden maar ook uit nieuwe attributen. Het aanpassen van de ontdekte kennis aan nieuwe voorbeelden wordt ook wel incrementele verfijning genoemd. Het aanpassen van de ontdekte kennis aan nieuwe attributen is dan hiŽrarchische verfijning. Incrementele verfijning leidt tot meer betrouwbare resultaten omdat de ontdekte patronen op meer en/of recentere gevallen gebaseerd zijn. HiŽrarchische verfijning kan leiden tot juistere en meer begrijpelijke patronen.

De meeste systemen kunnen wel overweg met incrementele maar niet met hiŽrarchische verfijning. Een systeem dat wel met beide overweg kan is Thought:KDI.

Oplossing

Cognitieve systemen passen hun regels aan wanneer te veel incorrecte voorspellingen gemaakt worden. Een dergelijke aanpak zou ook kunnen werken in een data miningsysteem. Het systeem wordt dan automatisch opnieuw getraind wanneer het percentage foute classificaties of voorspellingen boven een bepaalde drempelwaarde stijgt.

Voorbeelden

Thought/KDI (31)

Een regel is inconsistent voor een database wanneer er een voorbeeld bestaat dat voldoet aan het conditionele gedeelte maar niet voldoet aan het besluit en een knowledge base is inconsistent voor een database indien er een inconsistent regel in de knowledge base zit. Een knowledge base is onvolledig voor een database wanneer er een voorbeeld in de database zit dat aan geen enkel conditionele gedeelte van de consistente regels voldoet.

De initiŽle KB, ontdekt door Thought/KDI is zowel consistent als compleet. Inconsistentie of onvolledigheid kan dus enkel veroorzaakt worden door nieuwe gegevens. Wanneer een nieuw voorbeeld een regel inconsistent maakt, moet de regel aangepast worden om deze nieuwe voorbeelden uit te sluiten. Wanneer de nieuwe voorbeelden een KB onvolledig maken, moet nieuwe kennis ontdekt worden in de voorbeelden die niet vallen onder de bestaande regels.

Votes (32)

Bij ‘climbing generalization trees’, het voortdurend vervangen van waarden en concepten door hun parent-concepten kunnen we de votes informatie gebruiken. Een nieuw voorbeeld wordt gegeneraliseerd tot hetzelfde niveau als de gegeneraliseerde tabel. Hebben we te maken met een nieuw gegeneraliseerde record dan wordt deze toegevoegd. Bestaat de gegeneraliseerde regel reeds dan wordt de votes informatie verhoogd.


4.3. Conclusie

In hoofdstuk 3 werd aangetoond dat machine learningalgoritmes gebruik moeten kunnen maken van domeinkennis om in databases in een aanvaardbare tijdspanne tot relevante en significante ontdekkingen te komen. Dit is echter niet genoeg. Een tweede belangrijke uitbreiding op machine learningalgoritmes vooraleer we kunnen spreken over data mining is het uitbreiden van de representatiemogelijkheden. Data miningalgoritmes moeten beschikken over een zo krachtig mogelijk representatieformalisme zonder de efficiŽntie uit het oog te verliezen. Een krachtig representatieformalisme betekent immers meer mogelijke patronen maar ook meer rekenwerk.

De derde en belangrijkste uitbreiding is het toelaten van statistische of waarschijnlijke patronen. In een data miningomgeving geldt de veronderstelling dat een klasse exact kan worden beschreven of voorspeld op basis van de beschikbare attributen niet. De beschikbare attributen kunnen immers foute of onnauwkeurige waarden bevatten en er kunnen waarden en attributen ontbreken. Bovendien zijn de onderliggende patronen vaak onderhevig aan trends. Om deze redenen moeten data miningalgoritmes in staat zijn om niet alleen deterministische patronen te ontdekken maar moeten ze ook statistische of waarschijnlijkheidsregels kunnen opsporen.

Deterministische algoritmes

Deterministische algoritmes hanteren een Booleaanse evaluatiefunctie. D.w.z. dat ze enkel patronen weerhouden die 100 % juist zijn.

Voorbeelden hiervan vinden we vooral bij oudere systemen die nog het meest aanleunen bij ML

Omdat ze streven naar perfecte classificatie kunnen symbolische of deterministische algoritmes niet overweg kunnen met ruis en leiden ze tot ‘overfitted patterns’, patronen die enorm ingewikkeld worden om ook te kunnen gelden voor uitzonderingen en foutieve voorbeelden

Statistische algoritmes

De nadelen van de symbolische aanpak kunnen vermeden worden door het integreren van statistische technieken in het de evaluatiecomponent. Statistische algoritmes evalueren patronen op basis van drempelwaarden voor onder andere het bereik, de juistheid van classificatie of de correctheid. Dergelijke drempelwaarden kunnen door de gebruiker worden ingesteld op basis van domeinkennis, subjectieve beoordeling en specifieke doelstellingen. Statistische data miningalgoritmes weerhouden de patronen die op elk vlak beter scoren dan de vastgestelde drempelwaarden.

Voorbeelden:

In het volgende hoofdstuk wordt er dieper ingegaan op de manier waarop de belangrijkste machine learningtechnieken aangepast zijn aan data mining.