5. Enkele frequent gebruikte technieken


Er bestaan enorm veel verschillende manieren om aan data mining te doen en al deze technieken zijn in de laatste jaren talloze keren aangepast en uitgebreid. Het is niet mijn bedoeling een volledig overzicht te geven van alle mogelijke technieken, alleen al over de verschillende types neurale netwerken zou men immers verschillende boekdelen kunnen schrijven. Wel behandel ik in dit hoofdstuk de meest gebruikte basistechnieken, aangevuld met enkele voorbeelden die een idee geven van de manier waarop de basistechnieken, die veelal hun oorsprong vinden in het machine learningonderzoek, aangepast kunnen worden om aan data mining te doen.

De beschreven technieken zijn:


5.1. Beslissingsboomalgoritmes

5.1.1. Algemeen

Ross Quinlan introduceerde het gebruik van beslissingsbomen voor classificatie in 1983. Hij baseerde zich daarbij op CLS (Concept Learning system, geÔntroduceerd in 1966). De meeste hedendaagse beslissingsboomalgoritmes zijn gebaseerd op ID3.

Een beslissingsboom is een boomstructuur waarvan elke tak een set van tests op attributen voorstelt, aan de hand waarvan men objecten aan vaste categorieŽn kan toewijzen. Een beslissingsboomalgoritme is een algoritme dat op basis van een set van voorbeelden ťťn of meerdere beslissingsbo(o)m(en) genereert. De zoekruimte van een beslissingsboomalgoritme bestaat uit alle bomen die kunnen worden geconstrueerd m.b.v. de attributen en waarden in de trainingsset.

De meeste beslissingsboomalgoritmes worden gebruikt in supervised learning.

5.1.1.1. Basisalgoritme voor het opbouwen van beslissingsbomen

Figuur 23 Basisalgoritme voor het opbouwen van beslissingsbomen

5.1.1.1.1. Stap 1: Attribuutselectie

De volgende figuren illustreren de invloed van de volgorde waarin attributen geselecteerd worden op de vorm en de complexiteit van de uiteindelijke beslissingsboom. Beide beslissingsbomen werden opgebouwd met behulp van dezelfde dataset.

Figuur 24 Beslissingsboom met B als root-variabele

Figuur 25 Beslissingsboom met A als root-variabele

Om de beste beslissingsboom te vinden moet de beste volgorde van attribuuttests bepaald worden. We hebben dus behoefte aan een evaluatiecriterium voor de verschillende beschikbare attributen. Dit evaluatiecriterium moet het algoritme in staat stellen het attribuut te selecteren dat de grootste informatiewinst oplevert en de resterende informatie in eventuele subbomen minimaliseert.

Voor het evalueren van de informatiewinst kunnen we, in plaats van de hele trainingsset te gebruiken, een willekeurig gekozen subset of ‘window’ gebruiken. Deze techniek versnelt het algoritme maar kan ten koste gaan van de precisie.

Enkele mogelijkheden voor het evalueren van de informatiewinst zijn:

De chi-square test

De chi-square test wordt gebruikt door sommige beslissingsboomsystemen om te bepalen in welke mate een attribuut nuttig kan zijn voor het bepalen van de klasse van een object. De chi-square test vertelt niet welke waarde overeenstemt met welke klasse.

Informatie entropie

ID3 berekent een entropie score voor elk attribuut en selecteert dan het attribuut dat correspondeert met de minimum entropie score om de trainingsset op te splitsen. Dit betekent dat bij elke attribuutselectie, ID3 het attribuut selecteert dat overeenkomt met de situatie waar de informatie in de overblijvende attributen minimaal is.

5.1.1.1.2. Stap 2: vertakken (branching, splitting of subtrees)

Het algoritme kan vertakkingen creŽren voor:

Sommige algoritmen construeren enkel binaire beslissingsbomen. Hierbij kunnen echter veel interessante patronen verloren gaan.

5.1.1.1.3. Stap 3: controleren van het stopcriterium

ID3 stopt wanneer alle voorbeelden in een knooppunt van dezelfde klasse zijn of wanneer ze allen dezelfde attribuutwaarden hebben

5.1.1.1.4. Stap 4: een klasse toewijzen

ID3 wijst aan elk blad een klasse toe op basis van meerderheid of waarschijnlijkheid.

5.1.1.2. Patroonevaluatie

De kwaliteit van een beslissingsboom hangt af van de complexiteit (cfr. Ockham’s razor) en de classificatie-juistheid behaald voor de testset.

5.1.1.3. Output: vertalen en vereenvoudigen van beslissingsbomen

Hoewel ze meestal efficiŽnt en accuraat genoeg zijn, zijn beslissingsbomen vaak te complex en te onoverzichtelijk voor experts of gebruikers.

Om deze nadelen op te lossen kan de beslissingsboom omgezet worden in een vereenvoudigde representatievorm. Een vaak gebruikte methode is het omzetten van de beslissingsboom in een regelset, om deze dan te vereenvoudigen:

1. verwijder irrelevante condities

2. combineer de regels met dezelfde conclusie door het combineren van waarden van attributen met behulp van logische disjunctie

5.1.1.4. Robuuster maken van beslissingsboomalgoritmes

Beslissingsboomalgoritmes, en vooral vroege versies zoals ID3, zijn bedoeld voor het ontdekken van sterke, categorische regels in plaats van waarschijnlijkheidsregels. Ze moeten aangepast of uitgebreid worden om overweg te kunnen met ruis, ontbrekende velden, enz. Dit houdt in dat moet afgestapt worden van de eis dat elke tak met maximaal ťťn klasse gemerkt mag zijn.

1e mogelijkheid: het blad merken met de klasse die domineert

2e∑mogelijkheid: het blad merken met alle klassen samen met hun waarschijnlijkheden

5.1.1.4.1. Ruis en ontbrekende velden: overfitting

Oplossing: prepruning en postpruning technieken gebruiken om de grootte van de boom te beperken en overfitting te vermijden

Prepruning: inspelen op het stopcriterium (26)

Bij prepruning wordt het stopcriterium aangepast zodat het algoritme ook niet deterministische patronen kan ontdekken. Dit is mogelijk door drempelwaarden te definiŽren voor de informatie entropie en de chi-square test of voor het minimum aantal gevallen in een knooppunt.

Het splitsen aan een knooppunt van een beslissingsboom stopt wanneer

Nadeel van drempelwaarden: een drempelwaarde die hoog genoeg is om irrelevante voorbeelden uit te sluiten, zal ook relevante voorbeelden uitsluiten. De constructie van de beslissingsboom kan dus te vlug gestopt worden zodat belangrijke informatie verborgen blijft

Een voorbeeld van prepruning op basis van de chi-square test samen met een vergelijkende test van ID3 zonder pruning, met pre-pruning en met post-pruning wordt beschreven in (26).

Postpruning (26)

Postpruning gebruikt een optimaliseringscriterium dat de complexiteit van een boom afweegt tegen de juistheid van classificatie. De juistheid van classificatie kan gemeten worden met behulp van de testset.

Postpruning kan gebeuren tijdens het opbouwen van de beslissingsboom of, zoals bij ID3, nadat de hele boom geconstrueerd is. De knooppunten met condities die geen (significante) invloed hebben op de classificatiejuistheid kunnen worden weggelaten. Deze methode resulteert in een eenvoudige beslissingsboom met een aanvaardbare classificatiejuistheid maar is traag en inefficiŽnt.

5.1.1.4.2. Ontbrekende attribuutwaarden

Bij de constructie van een beslissingsboom kunnen we:

Tijdens classificatie kunnen we alle takken van een conditie op een ontbrekende waarde doorzoeken en voor elk resulterend pad de waarschijnlijkheid schatten. De waarschijnlijkheid van een volledig pad is dan het produkt van de relatieve frequentie van de gekozen waarden voor de ontbrekende attributen. Het voordeel van deze techniek is de ‘graceful degradation’, zelfs het ontbreken van een aanzienlijk aantal gegevens leidt tot een relatief kleine toename van foute classificatie.

5.1.1.4.3. Incrementeel leren

De meeste beslissingsboomalgoritmes werken enkel wanneer de gehele trainingsset ineens beschikbaar is (vb. ID3). Dit betekent wanneer de database wijzigt, de volledige beslissingsboom opnieuw moet worden afgeleid. Er bestaan echter ook incrementele beslissingsboomalgoritmes die de beslissingsboom herstructureren zodat hij consistent blijft met vroegere en met nieuwe voorbeelden (vb. ID5R).

5.1.1.5. Praktijktoepassingen van ID3

ID3 is o.a. gebruikt voor het ontwikkelen van expertsystemen voor

5.1.2. INFERULE

ID3 is succesvol omwille van de eenvoud en efficiŽntie. Er is echter reeds veel onderzoek geweest met de bedoeling ID3 bruikbaar te maken voor real-world problemen door:

Hťt nadeel van programma’s zoals ID3 komt echter voort uit de impliciete veronderstelling dat er in de gegevens voldoende informatie beschikbaar is om exact te bepalen hoe elk geval geklasseerd moet worden. INFERULE, daarentegen, is ontworpen voor gebruik met data sets waarbij de beschikbare attributen niet voldoende zijn om ťťn bepaalde klasse toe te wijzen aan elk voorbeeld.

5.1.2.1. Het INFERULE-algoritme

INFERULE is een uitbreiding op het ID3 algoritme

Selectie van een attribuut-waardepaar

INFERULE construeert een beslissingsboom op basis van attribuut-waardeparen i.p.v. attributen zoals dat het geval is bij ID3. INFERULE berekent voor elk attribuut-waardepaar een geometrische afstand (R) tussen de verwachte klassevector of klassedistributie van de corresponderende subset en de klassevector van de initiŽle subset. Hoe groter het verschil tussen beide klassedistributies, hoe waarschijnlijker dat de opsplitsing op basis van dat bepaalde attribuut-waardepaar relevant is voor de classificatie van A. INFERULE selecteert dus het attribuut-waardepaar dat dit verschil maximaliseert.

Stopcriterium

Wanneer de waarde van R voor elke mogelijke combinatie van attribuut-waardeparen boven een bepaalde drempelwaarde uitstijgt wordt de specialisatie stopgezet. Uit experimenten (28) blijkt dat het verhogen van T tot 0,55 aanvankelijk leidt tot een sterke verbetering van het percentage correcte classificatie. Bij een T hoger dan 0,55 daalt het percentage correcte classificatie opnieuw (dit is consistent met overfitting).

Vertakken

INFERULE genereert enkel binaire beslissingsbomen omdat het gespecialiseerd wordt op het beste attribuut-waardepaar i.p.v. op het beste attribuut. Voordeel hiervan is dat de gegevens niet onnodig opgesplitst worden (bij ID3 wordt een knooppunt opgesplitst volgens alle mogelijke waarden, ook de irrelevante)

Database problemen

In (28) heeft men ook getest wat de invloed van het onbeschikbaar maken van attributen is, op het percentage correcte classificatie, het aantal gegenereerde regels en de tijd nodig om de regels te genereren. INFERULE presteerde hier op alle vlakken beter dan de binaire ID3-beslissingsboom en ID3 met pruning.

Voorbeeldtoepassing

Meer details over een toepassing van INFERULE op een database met reparatiegegevens van wagens is terug te vinden in (28) en (60).

5.1.3. KATE (36)

Omdat ID3 geen domeinkennis kan gebruiken, worden enorm veel nutteloze berekeningen uitgevoerd. Voor eenvoudige toepassingen kan dit minder kwaad maar voor complexe trainingssets krijgen we te maken met een combinatorische explosie. In dit geval moet domeinkennis gebruikt worden om de zoekruimte te beperken en irrelevante attributen te snoeien.

In KATE is het mogelijk domeinkennis te benutten dankzij het gebruik van frames als representatieformalisme. De voordelen hiervan zijn de OO-manier waarop domeinentiteiten en trainingsvoorbeelden gemodelleerd kunnen worden en de natuurlijkheid van de representatie. Bovendien zijn frames krachtig en efficiŽnt.

5.1.3.1. Algoritme en zoekstrategie

De zoekstrategie en het preferentiecriterium zijn gelijkaardig aan die gebruikt in ID3.

Attribuutselectie

Een slot kan vergeleken worden met een attribuut bij ID3. Het grote verschil is dat een slot altijd verbonden is met een object of een frame. Een frame bevat een beschrijving van alle eigenschappen die relevant zijn voor een bepaald concept. Voor de informatiewinst berekening houdt KATE dus alleen rekening met relevante eigenschappen in een bepaalde context.

Vb.

Een klasse MANNEN met een Booleaans eigenschap BAARD?.

Een klasse VROUWEN met een Booleaans eigenschap ZWANGER?.

Omdat KATE enkel test op de informatiewinst van een slot bij een object zal het nooit de status van ZWANGER? testen voor een man.

Vertakken

De frames worden gebruikt om domeinkennis voor te stellen over de entiteiten die de trainingsvoorbeelden beschrijven. Deze kennis wordt gebruikt om de set van eigenschappen die relevant zijn in een bepaalde context, en het aantal mogelijke waarden van deze eigenschappen te beperken. Dit helpt bij het vermijden van een combinatorische explosie wanneer het probleemdomein zeer complex is.

5.1.3.2. Praktijkvoorbeeld

De Franse Compagnie Bancaire heeft KATE gebruikt voor het evalueren van risico’s bij het lenen aan bedrijven. De training gebeurde op basis van 700 trainingsvoorbeelden met 80% onbekende waarden en 7 te identificeren klassen. De testset bestond uit 400 voorbeelden.

Tabel 24 Vergelijking van KATE met experts en een bestaande expertsysteem

KATE 73% perfecte voorspellingen een extra 10% van de voorspellingen waren correct (hoogste waarschijnlijkheid)

1 expert minder dan 70% correcte voorspellingen

een panel van 10 experts iets minder dan 80% correcte voorspellingen

een reeds bestaand ES scoorde 20% slechter dan KATE en duurde 6 maand voor ontwikkeling


5.2. Generalized rule induction

Het probleem van ‘generalized rule induction’ is complexer dan de constructie van een beslissingsboom. De voornaamste reden hiervoor is dat de veronderstelling dat we de gegevens in een eenvoudige verdeel-en-heersmanier kunnen doorzoeken wegvalt.

Generalized rule induction probeert de x beste regels te vinden in een dataset. Dit regelinductiealgoritme start met een initiŽle set van regels. Deze regels worden gebruikt om de voorbeelden te classificeren en hun performantie wordt berekend. Vervolgens worden de regels gegeneraliseerd, gespecialiseerd en gecombineerd om nieuwe regels te produceren die de voorbeelden beter classificeren. De performantie wordt opnieuw gemeten en het proces wordt herhaald totdat aan een stopcriterium wordt voldaan.

Het meest bekende algoritme is AQ11 (classificeerde sojaboonziektes beter dan experts).

Andere voorbeelden zijn:

5.2.1. ITRULE (14 & 29)

5.2.1.1. Data input

De input in een systeem voor regelinductie bestaat uit:

5.2.1.2. De zoekruimte

Stel dat we beschikken over n attributen die elk m waarden kunnen aannemen. Dan is het aantal te construeren regels gelijk aan

Vb.

10 binaire attributen: 196.820 mogelijke regels

Het is duidelijk dat we noch over de data, noch over de computerresources beschikken voor het onderzoeken van een dergelijk aantal regels. Daarom moeten we de set van mogelijke kandidaat regels beperken.

Manieren om de zoekruimte te beperken zijn:

DefiniŽren van een goede R

De keuze van R, het aantal te weerhouden regels, is van groot belang. We moeten zorgen niet teveel regels a priori uit te sluiten (potentieel belangrijke informatie kan dan verloren gaan) maar we mogen ook niet alle regels toelaten.

Clusteren

Een tweede manier om de zoekruimte te beperken is clusteren.

Specificeren van de maximale orde

Wanneer de specialisatie van een regel toeneemt daalt de eenvoud zodat de waarschijnlijkheid dat aan die regel voldaan wordt zeer klein wordt. We kunnen dus de te gecompliceerde regels uitsluiten.

5.2.1.3. Algoritme

Attribuutselectie

Het kritieke punt van het algoritme is het specialisatiecriterium omdat dit beslist hoeveel van de zoekruimte doorzocht moet worden.

Specialisatie is het proces waarbij we hopen de ‘goodness-of-fit’ (classificatiejuistheid) van een regel te verhogen door het toevoegen van een extra voorwaarde. De daaropvolgende afname in eenvoud van de regel moet gecompenseerd worden door een toename van de goodness-of-fit in zulke mate dat de algemene kwaliteit toeneemt. Een maatstaf die de ‘goodness-of-fit’ en de eenvoud van een hypothese afweegt is de J-measure (zie evaluatie van patronen).

5.2.1.4. Illustratie van de J-measure (14)

Het probleemgebied ‘reptielen’ bestaande uit 3 binaire attributen:

De samengestelde distributie over deze attributen vind je in de onderstaande tabel.

Tabel 25 De samengesteld distributie in het probleemgebied 'reptielen'

desert legs snake joint probability

0 0 0 0.0

0 0 1 0.1

0 1 0 0.5

0 1 1 0.0

1 0 0 0.0

1 0 1 0.25

1 1 0 0.15

1 1 1 0.0

Stel nu dat we geÔnteresseerd zijn in regels die het attribuut-waardepaar ‘snake=true’ in de rechterzijde bevestigen.

De regel

If habitat = desert then snake = true with probability = 0.625 j=0.225 J=0.09

is een redelijke regel. De a priori waarschijnlijkheid dat een reptiel een slang is, is 0.35. De a posteriori waarschijnlijkheid is 0.625.

Wanneer we deze regel specialiseren krijgen we:

If habitat = desert and legs = false then snake = true with probability=1 j=1.51 J=0.379

De informatie inhoud van deze regel is veel groter (0.379). De afname in eenvoud wordt meer dan goedgemaakt door de toename in goodness-of-fit.

Wanneer we bovenstaande regel nu generaliseren

If legs = false then snake = true with probability = 1 j=1.51 J=0.53

krijgen we de beste regel.

5.2.1.5. Toepassingen

ITRULE is met succes toegepast in financiŽle en politieke domeinen (14).

5.2.2. AQ15 (9)

AQ15 is een inductief leersysteem dat beslissingsregels genereert. Het maakt gebruik van domeinkennis (constructieve inductie) en is vooral geschikt voor de constructie van sterke regels.

5.2.2.1. Representatieformalisme

Beslissingsregels waarbij het conditionele deel een logische formule is.

beslissingsregel

conditie actie

conjunctie ŕ conjunctie

voorwaarde voorwaarde

(‘kleur=rood ŕ groen’ Ŕ ‘haar = lang’) ŕ ( ... ) ģ Ci = X

5.2.2.2. Het zoekalgoritme

Bij het opbouwen van een beslissingsregel doorzoekt AQ met behulp van heuristieken, alle logische expressies om die expressies te vinden die gelden voor alle positieve en voor geen van de negatieve voorbeelden.

stap1: selecteer een voorbeeld waarvoor de regel nog niet geldt.

stap2: genereer alle conjuncties die gelden voor dat voorbeeld en niet voor de negatieve voorbeelden

stap3: selecteer de beste conjunctie op basis van de kwaliteitsfunctie

stap4: voeg deze toe aan het conditionele deel van de beslissingsregel

Omdat er veel van dergelijke regels bestaan, zoekt AQ de beste regel op basis van een door de gebruiker gedefinieerd criterium.

5.2.2.3. Database problemen

Voor inconsistente gegevens en ruis voorziet AQ 3 oplossingen:

Voor het verminderen van de complexiteit wordt gebruikt gemaakt van rule-truncationtechnieken, het verwijderen van voorwaarden, indien dit niet leidt tot een te sterke toename van de foutmarge.

5.2.2.4. Domeinkennis

AQ gebruikt domeinkennis om nieuwe attributen te genereren. Het systeem gebruikt deze variabelen daarna om betere regels te construeren.

5.2.2.5. Incrementeel leren

AQ beschikt over een incrementele leermogelijkheid. Het systeem werkt volgens het principe van ‘learning with full memory’, d.w.z. dat het alle tot nu toe geziene voorbeelden en alle regels die reeds gevormd zijn onthoudt. Het voordeel hiervan is dat nieuwe beslissingsregels gegarandeerd correct zijn voor alle (oude en nieuwe) voorbeelden.

5.2.2.6. Praktijktoepassingen

Het systeem is getest voor medische domeinen en heeft daar regels ontdekt die eenzelfde niveau behaalden als domeinexperts:

5.2.3. CN2 (9)

CN2 is een aanpassing van AQ waarbij de technieken om te werken met ruis in het algoritme zelf zitten i.p.v. gebruik te maken van postprocessing. De output van CN2 is een beslissingslijst.

5.2.3.1. Zoekalgoritme

Het CN2 algoritme genereert een beslissingslijst op een iteratieve manier, bij elke iteratie wordt een regel geconstrueerd. Een regel wordt geconstrueerd door het zoeken naar een complex, een set van condities, die geldt voor een groot aantal voorbeelden van een arbitraire klasse Ci en slechts geldt voor een klein aantal andere klassen. Wanneer een goede complex gevonden wordt, verwijdert het algoritme deze voorbeelden waarvoor de complex geldt en voegt de regel ‘if <complex> then predict Ci’ toe aan het einde van de beslissingslijst. Voor de rest van de set wordt een nieuwe regel geconstrueerd totdat geen complex meer gevonden kan worden van voldoende kwaliteit.

5.2.3.2. Kwaliteitscriterium

Het kwaliteitscriterium bestaat uit twee testen:

5.2.3.3. Output

CN2 construeert eenvoudige, begrijpelijke, statistische of waarschijnlijke produktieregels in domeinen waar zich ruis kan voordoen.


5.3. Climbing generalization trees

5.3.1. Algemeen

‘Climbing generalization trees’ is een bottom-up zoekstrategie waarbij domeinkennis, in de vorm van domeinconcepten en concepthiŽrarchieŽn, gebruikt worden om beschrijvingen te genereren voor vooraf gedefinieerde subsets in een database.

Het gebruikte algoritme:

5.3.1.1. Stap 1: creatie van subtabellen

Voor elke klasse construeert het algoritme een relationele subtabel. Eventueel worden hierbij op basis van domeinkennis enkel de relevante attributen weerhouden. Elke record kan gezien worden als een logische formule gevormd door de conjunctie van zijn attribuut-waardeparen. De initiŽle beschrijving van de klasse is dus de disjunctie van deze conjuncties.

5.3.1.2. Stap 2: generaliseren

Het startknooppunt in de zoekruimte is de set van voorbeelden, de disjunctie van alle records, en het doel is het generaliseren van deze tabel in een klassedescriptie, een meer compacte tabel die geldt voor alle voorbeelden behorende tot deze klasse. Voor het generaliseren beschikken we over de technieken beschreven in ‘generalisatie operaties’.

5.3.1.3. Stap 3: verwijderen van identieke trainingsvoorbeelden

Na het generaliseren moeten de records die door de generalisatie identiek geworden zijn verwijderd worden.

5.3.1.4. Stap 4: controleren van het stopcriterium

De gebruiker kan een drempelwaarde definiŽren voor het maximum toegelaten aantal records in de resultaattabel of voor het maximaal aantal verschillende waarden die elk attribuut kan aannemen. Een kleine drempelwaarde leidt tot een kleinere regel maar resulteert in overgeneralisatie en het verlies van informatie. Een grote drempelwaarde leidt tot een complexe regel en te weinig gegeneraliseerde regels. De gebruiker zal dus het ontwerp en de drempelwaarden moeten aanpassen op basis van het bekomen resultaat.

5.3.1.5. Output

De uiteindelijke gegeneraliseerde tabel bestaat uit een klein aantal records (afhankelijk van de gebruikte drempelwaarden) die kan omgezet worden in een eenvoudige logische formule.

5.3.2. DBLearn

Het DBLearn systeem is een relatief eenvoudig systeem gebaseerd op een herhaalde generalisatie. Hiervoor maakt DBLearn gebruik van 2 technieken

DBLearn kan aangepast worden om consistente of complete regels te zoeken. In het eerste geval construeert DBLearn beschrijvingen die gelden voor alle voorbeelden in die klasse maar mogelijk ook voor enkele voorbeelden buiten die klasse. In het tweede geval zullen alle voorbeelden waarvoor de beschrijving geldt behoren tot de klasse maar geldt de regel niet noodzakelijk voor alle positieve voorbeelden.

DBLearn kan uitgebreid worden om overweg te kunnen met ruis en uitzonderingen. Een klein aantal ongebruikelijke voorbeelden wordt beschouwd als ruis of uitzondering en wordt genegeerd. Hiertoe wordt een speciaal attribuut ‘votes’ toegevoegd aan elk record in de gegeneraliseerde tabel. Dit attribuut registreert het aantal records uit de initiŽle tabel die gegeneraliseerd zijn naar de record in de gegeneraliseerde tabel.

Gebaseerd op de votes-informatie kunnen voor elke gegeneraliseerde record twee gewichten gedefinieerd berekend worden:

Incrementeel leren kan eveneens geÔmplementeerd worden door gebruik te maken van de votes-informatie. Wanneer een record toegevoegd wordt aan de database, wordt het gegeneraliseerd naar hetzelfde niveau als de records in de gegeneraliseerde tabel. Wanneer de record reeds in de tabel staat wordt de votes-informatie van het betreffende record verhoogd. In het andere geval wordt het als een nieuwe record toegevoegd aan de gegeneraliseerde tabel. Wanneer hierdoor het aantal records in de gegeneraliseerde tabel een bepaalde drempelwaarde overschrijdt wordt een verdere generalisatie van de tabel uitgevoerd.

5.3.3. Abstract-driven pattern discovery (8)

Een abstract is een samenvatting van de gegevens in functie van high-level categorieŽn of concepten. Een regel wordt dus uitgedrukt in termen van een door domeinkennis of de gebruiker vastgelegde woordenschat.

5.3.3.1. Input

De input bestaat uit de dataset en de data dictionary die domeinconcepten, classificatiehiŽrarchieŽn, abstractiefuncties en aggregatieprincipe bevat.

5.3.3.2. Een heuristieke en interactieve zoekstrategie

De gebruiker moet 3 soorten informatie specificeren:

Voorbeelden van aggregatiefuncties zijn sommatie, tellen, gemiddelden, maximum en minimum. Het systeem werkt interactief omdat de gebruiker, wanneer hij/zij niet tevreden is met de resultaten, de input kan aanpassen.

5.3.3.3. Algoritme

1. beschouw het abstract als een lege set

2. voor elk record in de onderliggende relatie doe het volgende

3. het opbouwen van het abstract eindigt wanneer alle records van de onderliggende relatie verwerkt zijn

5.3.3.4. Gebruikersinteractie en domeinkennis

Een voordeel van het gebruik van domeinkennis en classificatiehiŽrarchieŽn is het vermijden dat er oninteressante of triviale patronen, die meestal het resultaat van een functionele afhankelijkheid zijn, ontdekt worden.

Vb.

Manhattan yuppies live in New York, strength 100 %.

Een dergelijk patroon is triviaal en oninteressant omdat het een gevolg is van het feit dat Manhattan een deel is van New York.

Nadeel van het gebruik van heuristieken daarentegen, is dat het zoeken te zeer geconcentreerd wordt op een deel van de zoekruimte zodat mogelijk interessante patronen uitgesloten worden. Een oplossing zou een zogenaamd ‘ongehoorzaam’ algoritme kunnen zijn, een algoritme dat zich wel baseert op domeinkennis en gebruikersinteractie maar dat ook die delen van de zoekruimte doorzoekt die in de buurt liggen van de initiŽle input.

Voor een uitgewerkt voorbeeld, zie (8)

5.3.4. Een algoritme voor het ontdekken van discriminerende regels (56)

Wanneer we op zoek zijn naar discriminerende regels streven we naar een zo hoog mogelijke juistheid van classificatie. Om een classificatieregel af te leiden moeten we testen of een gegeneraliseerd concept in de doelklasse overlapt met een gegeneraliseerd concept in ťťn van de contrasterende klassen.

We moeten de gegevens opsplitsen in 2 delen:

Daarna wordt beide partities synchroon gegeneraliseerd. Een overlappend record is een record dat zowel in de doelklasse als in een contrasterende klasse voorkomt. Dergelijke overlappende records moeten gemarkeerd worden en deze markeringen moeten worden overgedragen bij verdere generalisatie. Om de onderscheidende kracht van de bekomen classificatieregel te kennen berekenen we de d-weight.

Een hoge d-weight duidt erop dat het concept voornamelijk afgeleid is van records uit de doelklasse.

Een lage d-weight wijst erop dat het concept voornamelijk afgeleid is van records uit de contrasterende klassen.

Wanneer we een classificatieregel ontdekken met een d-weight van 100 % dan is die regel consistent.

Wanneer zowel de d-weight als de t-weight geassocieerd zijn met dezelfde set van records, kunnen de classificatieregels en karakteristieke regels voorgesteld worden in dezelfde logische bi-directionele regel waarbij de beide gewichten geassocieerd zijn met de disjuncts.

5.3.4.1. Afleiden van benaderingsregels

Afleiden van karakteristieke benaderingsregels

Records in de gegeneraliseerde tabel met een lage t-weight zijn afgeleid van een klein aantal, meestal uitzonderlijke gevallen. Door het snoeien van dergelijke records kunnen we ervoor zorgen dat de gegeneraliseerde tabel geldt voor het merendeel van de gevallen. In de praktijk komt dit overeen met het definiŽren van een drempelwaarde.

Afleiden van benaderende classificatieregels

Gegeneraliseerde records met een lage t-weight zijn voornamelijk afgeleid van de records uit de contrasterende klassen. Ook hier kunnen we een drempelwaarde definiŽren opdat de gemarkeerde records met lage (en medium) d-weights gesnoeid zouden worden.

Zowel de d-drempelwaarde als de t-drempelwaarde kunnen gebruikt worden om regels die gebaseerd zijn op ruis of op uitzonderlijke gevallen, te snoeien. Deze drempelwaarden kunnen interactief afgesteld worden door de gebruikers of de experts.

5.3.4.2. Incrementeel leren

Met behulp van de votes-informatie kan vermeden worden dat het leerproces steeds vanaf nul moet herbeginnen. De werking hiervan heb ik reeds uitgelegd bij DBLearn.

Bij het verwijderen van records uit de database kan eveneens incrementeel leren worden toegepast. De votes-informatie wordt dan gewoon verminderd. Hiermee moet echter voorzichtig worden omgesprongen omdat het verminderen van de votes-informatie niet equivalent is met het terug afdalen van de concepthiŽrarchie. Deze techniek werkt dus niet goed wanneer er een groot aantal records verwijderd worden.


5.4. Neurale netwerken

Neurale netwerken zijn gebaseerd op de werking van het brein en bestaan uit:

5.4.1.1. Neuronen

Een neuraal netwerk bestaat uit een ingewikkeld netwerk van neuronen. Een neuron is een eenvoudige verwerkingseenheid die ťťn of meerdere inputs ontvangt en ťťn output produceert. Met elke input van een neuron is een gewicht geassocieerd dat het belang van die bepaalde input bepaalt.

De werking van een neuron is heel eenvoudig:

5.4.1.2. De activerings- of transferfunctie

Met behulp van de transferfunctie transformeert een neuron de gewogen som van zijn inputs naar een output. De transferfunctie kan de verschillende vormen aannemen. Meestal wordt de voorkeur gegeven aan een zacht limiterende transferfunctie omdat deze het ontdekken van complexere en meer subtiele patronen mogelijk maken.

5.4.1.3. De architectuur of topologie van een neuraal netwerk

Er bestaan verschillende types neurale netwerken waarvan de meest frequent gebruikte de multi-layer perceptron of het feed forward neuraal netwerk is (zie figuur 19).

De neuronen van een multi-layer perceptron zijn verdeeld over 3 of meer lagen:

Het aantal inputneuronen hangt af van het aantal relevante inputvariabelen. Het aantal verborgen lagen en verborgen neuronen is afhankelijk van de complexiteit van de te ontdekken patronen. Hoe meer verborgen lagen en neuronen, hoe complexer de patronen kunnen zijn maar ook hoe meer rekenwerk nodig zal zijn. Normaal wordt het aantal verborgen lagen en neuronen bij het eerste ontwerp niet te hoog gesteld. Het aantal output neuronen is afhankelijk van het type en het aantal outputvariabelen. In het geval van een continue outputvariabele volstaat 1 outputneuron, voor discrete outputvariabelen moet ťťn outputneuron voorzien worden per outputvariabele.

De neuronen van de inputlaag ontvangen elk slechts ťťn input. De output van de ene laag wordt dan doorgestuurd naar alle neuronen van de volgende laag.

In de meeste neurale netwerken vloeien de gegevens van de inputlaag naar de outputlaag. Sommige en netwerken laten echter ook toe dat gegevens terugvloeien.

Voorbeelden van netwerkarchitecturen zijn:

5.4.1.4. Trainen van het netwerk

Een netwerk wordt getraind door het invoeren van de voorbeelden in het netwerk en het aanpassen van de gewichten. In het geval van supervised learning bestaat de input uit een reeks van inputs met hun bijbehorende outputs. Het netwerk zal de gewichten aanpassen zodat elke voorbeeld correct geclassificeerd wordt. Bij unsupervised learning worden de netwerken enkel met inputgegevens getraind en moet het netwerk classificaties afleiden die inherent zijn aan de gegevens.

Het netwerk leert, door het vergelijken van de netwerkoutput voor elk inputpatroon met een originele output voor dat patroon en het berekenen van de fout. Op basis van deze fout worden de sterktes van de connecties van het netwerk iteratief aangepast om convergentie te bereiken. Het netwerk is getraind wanneer het netwerk een correcte output produceert voor elk inputvoorbeeld, eventueel binnen een bepaalde foutmarge of wanneer de gewichten stabiliseren. De informatie, ontdekt door het neurale netwerk, zit dus gecodeerd in de gewichten.

Eťnmaal het netwerk getraind is, worden de gewichten bevroren en kan het netwerk gebruikt worden voor het classificeren van nieuwe gevallen. Het trainingsproces is traditioneel traag maar het classificeren van nieuwe gevallen kan enorm snel gebeuren.

5.4.1.5. De input

Neurale netwerken kunnen werken met datasets met duizenden records en 2 tot 200 attributen. Om efficiŽnt te werken moeten de inputgegevens wel zo ruisvrij mogelijk en numeriek zijn.

5.4.1.6. Incrementele ontwikkeling

Het bouwen van een neuraal netwerk vereist altijd enkele pogingen. Wanneer de resultaten van de eerste poging tegenvallen kan de gebruiker de volgende verfijningen aanbrengen:

5.4.1.7. Voordelen van neurale netwerken

5.4.1.8. Nadelen van neurale netwerken

5.4.1.9. Voorbeelden van applicaties

In (48) worden neurale netwerken gesuggereerd als oplossing voor het ‘travelling-salesman’ probleem, het berekenen van de kortste route door een bepaald netwerk vertrekkend van een bepaalde stad. Gelijkaardig problemen zijn het vinden van de beste route doorheen een telecommunicatiesysteem en het minimaliseren van de leveringstijd van een pakje.

Tabel 26 Illustratie van de complexiteit van het 'travelling-salesman' probleem

Aantal steden aantal routes tijd ANS op microcomputer tijd conventioneel zoekalgoritme op een mainframe

10 181.440 < 0.1 seconde

30 4.4 x 1030 < 0.1 seconde 1 uur

31 < 0.1 seconde 30 uur

32 < 0.1 seconde 330 uur

Andere voorbeelden van bestaande applicaties op basis van neurale netwerken zijn:

JARGON is een adaptief neuraal netwerk dat gebruikt wordt om kennis te ontdekken in natural language databases. In (13) wordt de toepassing van JARGON op een database met 45 teksten over de techniek van het injecteren van medicijnen in spieren beschreven. De samenvattingen geproduceerd door het systeem waren goed gestructureerd wanneer de beperking van de semantiek groot is (vb. expertdatabases en gespecialiseerde databases). Ze worden waziger wanneer de semantische beperking afneemt (vb. interviews).


5.5. Numerieke leersystemen

De meeste supervised learning algoritmes construeren kennisstructuren die objecten classificeren in een eindig aantal klassen. Voor sommige applicaties willen we de exacte waarde van een attribuut voorspellen. Dit geeft echter problemen wanneer het domein van dit attribuut continue is (bv. bij numerieke attributen).

Eťn oplossing is het discretiseren van de mogelijke attribuutwaarden.

Nadeel hiervan : een verlies aan informatie

Daarom willen we als resultaat van het data mining proces een kennisstructuur hebben die numerieke variabelen voorspelt, d.w.z. een functie die resulteert in numerieke waarden.

Vb.

BACON is een systeem dat enkele empirische wetten in chemie en andere domeinen ontdekt.

5.5.1. KEDS (1 & 9)

Vele real-life engineering fenomenen zijn multidimensioneel en niet homogeen, KEDS biedt hiervoor een oplossing in de vorm van een ‘divide-and-conquer strategie’.

Het opsplitsen van het probleemdomein in kleinere delen (partitioneren) heeft volgende voordelen:

5.5.1.1. Input

De input bestaat uit:

De door de gebruiker gedefinieerde set van modelfuncties stelt de domeinkennis voor.

5.5.1.2. Representatieformalisme

Als representatieformalisme gebruiken we region-equationparen:

R1ř y = f1(x) + m(0,s)

R = region

f = equation

Een region-equationpaar voorspelt de waarde van een onafhankelijke variabele y voor alle data punten in een gebied R

Region-equationparen zijn een krachtiger kennis representatie-formalisme dan pure numerieke functies. De modellen geconstrueerd door dit systeem zijn begrijpelijk voor mensen.

5.5.1.3. Het KEDS algoritme

1e fase: ontdekken

KEDS kiest een modelfunctie en selecteert random enkele voorbeelden uit de trainingsset om de onbekende coŽfficiŽnten te berekenen. Daarna wordt berekend voor welk percentage van de trainingsset de resulterende functie geldt. Wanneer dit percentage boven een vooraf bepaalde drempelwaarde ligt wordt de functie geselecteerd.

2e fase: partitioneren

De negatieve en positieve voorbeelden worden gebruikt om het gebied te bepalen waar de functie geldig is. Een functie wordt alleen geselecteerd wanneer ze geldt voor een aaneensluitend gebied.

De ontdekkingsmodule kan dan opgeroepen worden om in elk deelgebied de kandidaat-vergelijking te verfijnen of opnieuw te ontdekken. De verfijnde kandidaat-vergelijking wordt dan doorgegeven aan de partitioneringsmodule om verfijnde deelgebieden te vinden. Deze iteratie kan blijven voortduren tot het region-equationpaar niet meer verbetert.

Figuur 26 Illustratie van de werking van KEDS

5.5.1.4. Evaluatie

Gegenereerde modellen worden geŽvalueerd volgens 2 criteria:

Afhankelijk van de probleemspecificaties kunnen we verschillende modellen creŽren door begrijpelijkheid af te wegen t.o.v. juistheid.

5.5.1.5. Ruis

Om het KEDS-algoritme beter bestand te maken tegen ruis en foute gegevens, kunnen we probablistische covers gebruiken i.p.v. 0/1 covers. Een voorbeeld hiervan is het CAQ-algoritme (1). Het CAQ-algoritme zoekt naar deelgebieden met vooral positieve gevallen i.p.v. naar deelgebieden met enkel positieve gevallen.

Probablistic covering resulteert in betere, kleinere region-equationparen met een grotere cover en dit in minder tijd. Meer details zijn te vinden in (1).

5.5.2. FORTY-NINER (21)

FORTY-NINER is een computersysteem voor data mining dat grote relationele databases kan doorzoeken naar regelmatigheden.

De parameters van FORTY-NINER kunnen aangepast worden om aan allerlei vereisten te voldoen.

Vb.

FORTY-NINER is een uitbreiding op BACON en FAHRENHEIT.

5.5.2.1. Clusteren

Om het zoeken betekenisvol en efficiŽnt te kunnen maken moet FORTY-NINER weten welke attributen onafhankelijk en welke attributen afhankelijk zijn. Het afhankelijk of onafhankelijk zijn van een attribuut is een beslissing die buiten FORTY-NINER staat. Wanneer niet geweten is welke variabelen afhankelijk zijn kunnen alle attribuutparen vergeleken worden in een exhaustieve zoektocht.

5.5.2.2. Representatieformalisme

De statistische patronen die de gegevens in databases kunnen volgen, kunnen een enorm aantal vormen aannemen. Daarom werd beslist de statistische informatie op een visuele manier aan te bieden aan de gebruiker door middel van beslissingsbomen, contingentietabellen en lineaire vergelijkingen.

5.5.2.3. Types van patronen

FORTY-NINER creŽert een lijst van tweedimensionele regelmatigheden. Deze regelmatigheden kunnen 3 vormen aannemen:

Tabel 27 De types patronen waarnaar FORTY-NINER zoekt

Stat-2 een contingentietabel met 4 velden (low-low, low-high, high-low, high,high)

Stat-All een contingentietabel met alle mogelijke combinaties (hierop kan dan nog een soort van aggregatie worden toegepast ter vereenvoudiging)

Lin: (lineair deviation r≤) wordt gevonden door het toepassen van de ‘least squares’ methode, die de beste lineaire fit geeft voor 2 variabelen in een gegeven data set.

Elk van de drie types patronen is geassocieerd met een eigen drempelwaarde. Aangeraden wordt de exploratie te beginnen met een hoge drempelwaarde en deze aan te passen naargelang het aantal ontdekte patronen.

5.5.2.4. Patronen zoeken

Partitioning search

De ‘partitioning search’ wordt gebruikt om subsets van de database te produceren waarin tweedimensionele patronen kunnen worden gezocht.

1) genereer alle mogelijke combinaties van de gegeven onafhankelijke en afhankelijke variabelen

2) beschouw elke partitie van de dataset behalve wanneer deze te weinig elementen bevat

3) zoek in elk blad van de ‘partitioning tree’ naar tweedimensionele patronen

Het partitioneren kan gecontroleerd worden door:

Tabel 28 Illustratie van de complexiteit van FORTY-NINER

N onafhankelijke variabelen (exponentiŽle invloed) 30

M afhankelijke variabelen (lineaire invloed) 5

aantal combinaties die kunnen leiden tot twee-dimensionele patronen: M x N vb. 30 x 5 = 150

aantal combinaties uitgaande van 2 slices per onafhankelijke variabele (binair) 3N-1 = 329

Deze combinatorische explosie kan beperkt worden door:

5.5.2.4.1. Zoeken naar tweedimensionele patronen in de subsets

Nu wordt geprobeerd patronen te ontdekken tussen een afhankelijk attribuut en een onafhankelijk attribuut. Elke voldoende sterke regelmatigheid wordt bewaard.

De complexiteit hangt af van:

5.5.2.4.2. Generaliseren van de tweedimensionele patronen

Tweedimensionele patronen kunnen gegeneraliseerd worden door de waarden van een attribuut te combineren in abstractieklassen.

Een tweede mogelijkheid bestaat erin een attribuut te negeren zodat het aantal dimensies vermindert.

Voordelen van het generaliseren van de tweedimensionele patronen:

5.5.2.5. Output en performantie

Over het algemeen vindt FORTY-NINER een groot aantal statistisch significante patronen. Vele van deze patronen zijn nieuw en interessant maar vele andere zijn daarentegen reeds gekend door de gebruiker.