3. Het data miningalgoritme: het kernmechanisme van data mining


In (20) pogen Kloesgen en Zytkow te komen tot eenvormigheid in de definities van een aantal termen die relevant zijn voor machine discovery.

Knowledge discovery process

A knowledge discovery process aims at finding out new knowledge about an application domain. Typically a discovery process consists of many discovery steps, each attempting at the completion of a particular discovery task, and accomplished by the application of a discovery method. A discovery process emerges iteratively and depends on the dynamic, result dependent discovery goals. The process iterates many times through the same domain, typically based on search in various hypotheses spaces. New knowledge is inferred from data often with the use of old knowledge. Domain exploration and discovery focusing are discovery processes applied in new domains, where old knowledge is not available (20).

Discovery step

A discovery step is a part of a discovery process. Discovery steps, methods, and tasks are interrelated: step is an application of a method,; method accomplishes a task; task rationalizes a method. The main discovery steps include data collection, pattern extraction from data, inductive generalizations of data, knowledge verification, knowledge transformation. A knowledge discovery process may use steps which do not directly lead to new knowledge, but enable further discoveries, such as knowledge presentation, management of data, management of domain knowledge, and selection of new goals (20).

In dit hoofdstuk zal ik het vooral hebben over de ontdekkingsstappen die direct leiden tot het ontdekken van nieuwe kennis: het clusteren van de database, het evalueren van de ontdekte patronen en het onttrekken van patronen.

Over de stappen die niet direct tot nieuwe kennis leiden maar die het ontdekken van patronen mogelijk maken (vb. kiezen en beoordelen van toepassingen, verzamelen van de gegevens, ...) heb ik het in hoofdstuk 6.


3.1. Input

De drie soorten input in een data miningsysteem zijn gegevens, domeinkennis en gebruikerscommando’s. De ruwe gegevens vormen de grondstof en de domeinkennis moet ervoor zorgen dat de bekomen resultaten begrijpelijk en nuttig zijn en dat het algoritme efficiŽnt kan werken. De gebruikerscommando’s zijn ingrepen van de gebruiker op het ontdekkingsproces.

3.1.1. Ruwe gegevens

De meeste ontdekkingssystemen gaan uit van een universele relatie, ťťn enkele logische tabel die alle relevante velden combineert.

Wanneer het data miningsysteem gebruik moet maken van relationele databases, wanneer dus de te verwerken gegevens niet als een logisch bestand aan het data miningsysteem worden gepresenteerd, moet het systeem beschikken over:

De gegevens vormen de belangrijkste grondstof voor data mining, de kwantiteit en de kwaliteit van de gegevens zijn van doorslaggevend belang voor het succes van data mining.

Kwantiteit

De databasegegevens worden door de gebruiker opgesplitst in een trainingsset en een testset. De trainingsset wordt gebruikt om patronen te ontdekken en met behulp van de testset kan men controleren of de ontdekte patronen ook gelden voor nieuwe gevallen.

De trainingsset is best zo groot mogelijk en hiervoor zijn 2 redenen. Ten eerste leidt een grotere trainingsset tot lagere foutmarges. Dit wordt bevestigd door het experiment van Gaines en Compton(62). Hun experiment bestond erin een data miningsysteem te trainen met telkens 500 extra voorbeelden. Wanneer ze de gegevens van een periode van 3 jaar gebruikten behaalde het systeem een foutmarge van 2,7 %. Voor de gegevens van een periode van 7 jaar gegevens daalde de foutmarge tot 1,4%. Een tweede reden is het feit dat we de bekomen patronen wensen te veralgemenen naar de buitenwereld, naar gevallen die niet in de database zitten. We moeten dus over voldoende voorbeelden beschikken om tot statistisch aanvaardbare resultaten te komen. Het nadeel van grote trainingssets is dat de complexiteit van het zoekprobleem lineair is t.o.v. het aantal voorbeelden. Dit betekent dat wanneer de training set tweemaal zo groot is, het algoritme er ongeveer 2 keer zo lang over zal doen om tot aanvaardbare resultaten te komen. EfficiŽntie moet dus afgewogen worden t.o.v. betrouwbaarheid. Jammer genoeg bestaan er geen algemene normen of richtlijnen voor het bepalen van de optimale hoeveelheid trainingsvoorbeelden.

Experimenten met de grootte van de testset wijzen erop dat de hoeveelheid voorbeelden hier minder van belang is. Belangrijker hier is de kwaliteit van de testset.

Kwaliteit

Het resultaat van data mining is sterk afhankelijk van de kwaliteit van de gegevens waarop de afgeleide patronen gebaseerd zijn. De analist moet er dus voor zorgen dat de gegevens zo goed mogelijk zijn en dat er zoveel mogelijk informatie in de data items zit. De kwaliteit van de trainingsset omvat de volgende factoren:

Volledigheid

Gegevensvervuiling

Overtollige informatie

Vrij van vooroordelen

Een bijkomende vereiste is de begrijpelijkheid van de trainingsset. De gebruiker moet de datatypes, statistische eigenschappen en betekenis van alle attributen kennen. Dergelijke informatie is onontbeerlijk bij het fijnstellen van de parameters van het ontdekkingssysteem.

Voor een meer gedetailleerde behandeling van de invloed van en oplossingen voor gegevenskwaliteits-problemen verwijs ik naar hoofdstuk 4. Kort samengevat zijn er een aantal mogelijke oplossingen. De eerste oplossing is het vermijden van problemen door het toepassen van strenge integriteitsbeperkingen en regelmatig onderhoud aangevuld met pre-processing van de gegevens vooraleer ze gebruikt worden voor data mining. Ten tweede kunnen we de algoritmes robuuster maken door ze uit te breiden met statistische mogelijkheden en tenslotte kunnen we data mining zelf gebruiken voor kwaliteitsbewaking. In dit laatste geval werken we met een data miningsysteem dat automatisch zoekt naar afwijkingen van globale patronen. Wanneer een regel geldt voor 99 van de 100 gevallen dan zal dat ene geval dat niet voldoet aan de regel ofwel een geldige uitzondering zijn ofwel het gevolg van een fout in de gegevens zijn.

3.1.2. Domeinkennis

Domeinkennis is het geheel van kennis, definities, ervaring en vuistregels, beschikbaar over een bepaald probleemdomein. Dergelijke domeinkennis kan verschillende vormen aannemen.

Lijsten met relevante velden

Domeinexperts hebben vaak een vrij goed idee van welke factoren een invloed hebben op een beslissing of een classificatie. Wanneer men bij het opbouwen van een data miningsysteem over een lijst beschikt die de beschikbare attributen naar belangrijkheid schikt kunnen de irrelevante of weinig relevante gegevens verwijderd worden. Het verwijderen van irrelevante gegevens zal een drastische impact hebben op de prestatie van het systeem omdat de complexiteit van het zoekprobleem exponentieel toeneemt met het aantal attributen.

Bovendien kunnen de gebruikers op basis van deze lijst kengetallen toewijzen aan de gegevens zodat het algoritme geleid kan worden bij de attribuutselectie. Attributen met een klein kengetal zullen het laatst gebruikt worden voor specialisatie en het eerst voor generalisatie. Attributen met een hoog kengetal daarentegen zullen het eerst gebruikt worden voor specialisatie en het laatst voor generalisatie.

Definities van nieuwe velden

Bij het opmaken van de dataset kan de domeinexpert of de eindgebruiker beslissen extra velden te definiŽren. Deze nieuwe velden, ook wel composietattributen genoemd, zijn veelal combinaties van beschikbare gegevens of procesgegevens die bij normalisatie verwijderd werden.

Vb.

Voordelen van composietattributen:

Vb.

Functionele of causale verbanden

Functionele of causale verbanden zijn afhankelijkheden tussen 2 of meer variabelen waarbij de waarde van het eerste attribuut bepaald of beperkt wordt door de waarde(n) van de andere attributen.

Vb.

Sommige onderzoekers stellen dat data miningsystemen informatie over functionele verbanden ter beschikking moeten hebben om, binnen een aanvaardbare tijdspanne, tot relevante en nuttige ontdekkingen te komen. Zij stellen dat het systeem beter op zoek gaat naar nieuwe patronen.

De aanhangers van de ‘boot-strapping approach’ houden er een andere mening op na. Zij argumenteren dat het opnieuw kunnen ontdekken van functionele afhankelijkheden een essentiŽle eigenschap is van een data miningsysteem en dat dergelijke ontdekkingen het vertrouwen in het systeem kunnen doen toenemen.

Domeinconcepten

Een domeinconcept is een combinatie van attribuutwaarden die voor de gebruiker of in het probleemdomein een bijzondere betekenis heeft.

Tabel 18 Een data dictionary of vocabularium met domeinconcepten

Views for Relation CUSTOMER

yuppie(name) ::= age < 35 and income > 80000 or card_type = ‘Gold’ Wall_street_yuppie(name) ::= yuppie(name) and profession = ‘Investment Banking’ Madison_Av_yuppie(name) ::= yuppie(name) and profession = ‘Advertising’ senior_citizen(name) ::= age > 65 student(name) ::= profession = ‘student’ customer_type(name) ::= CUSTOMER(name,addr,income,profes,age,card_type,mar_stat)

Views for Relations TRANSACTION

merchant(type) ::= TRANSACTION(name,merchant,type,amount,date) department_store(type) ::= type = ‘department_store’ restaurant(type) ::= type = ‘restaurant’ expensive_restaurant(merchant) ::= restaurant(type) and amount > 150 moderate_restaurant(merchant) ::= restaurant(type) and 40 < amount and amount < 150 inexpensive_restaurant(merchant) ::= restaurant(type) and amount < 40 eco_condition(date) ::= TRANSACTION(name,merchant,type,amount,date) yearly_purchase(date) ::= sum(amount) grouped by year(date) recession(date) ::= yearly_purchase(date) < yearly_purchase(date - 1yr) and yearly_purchase(date - 1yr) < yearly_purchase(date - 2yr) boom(date) ::= yearly_purchase(date) > yearly_purchase(date - 1yr) and yearly_purchase(date - 1yr) > yearly_purchase(date - 2yr)

Zoals blijkt uit bovenstaande tabel worden domeinconcepten gedefinieerd als view op de originele dataset.

Domeinconcepten kunnen gebruikt worden om het zoekproces te leiden en om de resultaten begrijpelijker te maken.

Vb.

In veel bedrijven wordt gewerkt met beschrijvingen zoals hoog, gemiddeld en laag. Deze beschrijvingen slaan dan bijvoorbeeld op intervallen

Op basis van dergelijke informatie kunnen de generalisatie en specialisatie operaties sneller en gerichter gebeuren. Bovendien zullen patronen opgebouwd met domeinconcepten zinvoller en begrijpelijker zijn voor de gebruiker.

Vb.

Het patroon ‘Yuppies bezoeken vooral dure restaurants’ is begrijpelijker dan het patroon ‘Personen jonger dan 35 jaar en met een inkomen hoger dan 80.000 of met een kredietkaart van het type ‘Gold’ bezoeken vooral handelaren van het type ‘restaurant’ met een bedrag groter dan 150’.

ConcepthiŽrarchieŽn

ConcepthiŽrarchieŽn zijn hiŽrarchische verbanden tussen domeinconcepten. Een concepthiŽrarchie is vaak verbonden aan een specifieke attribuut en is gedeeltelijk geordend van algemeen naar specifiek. Het meest algemeen is de null-beschrijving (ANY) en de meest specifieke punten komen overeen met de verschillende waarden die het attribuut kan aannemen.

Figuur 8 Een voorbeeld van een concepthiŽrarchie

ConcepthiŽrarchieŽn kunnen dienen als leidraad bij het generalisatie- en specialisatieproces en bieden dezelfde voordelen als concepten. Ze hebben een positieve invloed op de snelheid van het systeem en hun gebruik resulteert in meer begrijpelijke en nuttige patronen.

Patroon templates of patroonmodellen (82)

De gebruiker kan ook specificeren welke vorm de patronen moeten hebben.

Vb.

Enkel patronen weerhouden die het attribuut ‘geslacht’ in hun conditionele gedeelte hebben.

Een dergelijke beperking kan gebruikt worden voor het evalueren, generaliseren en specialiseren van patronen. Patronen die voldoen aan het model zullen een hogere kwaliteitsscore krijgen en operaties die het patroon specialiseren met behulp van het attribuut ‘geslacht’ zullen voorrang krijgen.

3.1.2.1. Bronnen van domeinkennis

De data dictionary

Een data dictionary bevat meta-informatie over de inhoud van een database. Het data miningalgoritme of KD-algoritme moet over deze meta-informatie kunnen beschikken.

Vb.

Informatie over het datatype is bijvoorbeeld belangrijk voor de selectie van de toepasbare vergelijkingsoperatoren. In het geval van geordende attribuutdomeinen kunnen de verschillende attribuutwaarden vergeleken worden met behulp van <, >, =, £, , Ļ

Vb.

Bij niet geordende attribuutdomeinen hebben alle attribuutwaarden eenzelfde significantie en kunnen ze enkel vergeleken worden bet behulp van =, Ļ.

Vb.

Dit betekent dat we bij numerieke attributen moeten werken met afstandsmaten en bij symbolische attributen met operatoren die testen naar de gelijkheid van waarden.

De gebruiker

De gebruiker en de domeinexpert kunnen putten uit een jarenlange ervaring en beschikken vaak over lijsten met relevante factoren, vuistregels en heuristieken. Het nadeel van zulke kennis is echter dat ze vaak onnauwkeurig, slecht gespecificeerd, onzeker, onvolledig en ontoegankelijk is. Een bijkomend probleem is dat de expertise voor het oplossen van een probleem vaak gedistribueerd is over verschillende individuen. Jammer genoeg zijn domeinexperts bovendien vaak de bron van allerminst eenvoudige domeinkennis. Het onttrekken van dergelijke kennis is een groot probleem. Gelukkig kunnen er bepaalde vormen van domeinkennis ontdekt worden.

Vb.

Functionele afhankelijkheden

De Knowledge Base (KB)

In de knowledge base worden reeds gekende regels, hiŽrarchieŽn, beslissingsbomen en vergelijkingen geldend voor het specifieke probleemgebied, opgeslagen.

Specificaties en handleidingen

Bijkomende informatie over de gegevensstructuur en afhankelijkheden tussen velden bestaat buiten de database in:

3.1.3. Gebruikerscommando’s

De gebruiker of domeinexpert moet instaan voor het parametriseren van het kennisontdekkingssysteem. Hiervoor baseert hij zich op de doelstellingen en resultaten van vorige pogingen. Bij het fijnstellen van het systeem laat de gebruiker zich bovendien leiden door de eigen vooroordelen en door hetgeen hijzelf interessant of merkwaardig vindt.

De gebruiker kan op verschillende niveaus ingrijpen in het zoekproces:


3.2. Clusteren

3.2.1. Wat is clusteren ?

Clusteren is het groeperen van records in betekenisvolle subklassen die gebruikt kunnen worden in een supervised learningsysteem (82). M.a.w., clusteren is het opsplitsen van de trainingsset op basis van een bepaald attribuut of een set van attributen en kan op drie manieren gebeuren:

Door het clusteren van een dataset bepalen we welke eigenschap(pen) we willen karakteriseren en/of voorspellen.

Vb.

Wanneer we het verschil wensen te kennen tussen onze vrouwelijke en onze mannelijke klanten kunnen we de dataset clusteren op basis van het attribuut ‘geslacht’. Deze clustering resulteert in 2 clusters of klassen: {man} en {vrouw}

De attributen die de klasse van een voorbeeld bepalen noemen we de afhankelijke attributen terwijl de overblijvende attributen de onafhankelijke attributen zijn.

De gekozen clustering beÔnvloedt de patronen die gevonden kunnen worden.

Vb.

Wanneer we een klantendatabase verdelen in 2 klassen nl. mannen en vrouwen zullen we waarschijnlijk geen patronen ontdekken die verklaren waarom de ene klant op tijd betaalt en de andere niet.

Daarom moet de gekozen clustering zinvol en nuttig zijn. Een zinvolle en nuttige clustering is een clustering die een reŽle kans biedt op het ontdekken van nuttige patronen. Nuttige patronen zijn patronen die bruikbaar zijn binnen het specifieke probleemdomein.

Vb.

Wanneer we beschikken over een database met patiŽntgegevens kunnen we deze clusteren op basis van het attribuut ‘voornaam’. Een dergelijk clustering is echter zinvol noch nuttig omdat de kans dat de voornaam van een persoon voorspeld kan worden a.d.h.v. de andere beschikbare attributen klein zoniet onbestaande is en omdat indien we toch significante patronen zouden vinden, deze niet nuttig zouden zijn. Een hospitaal is niet gebaat bij het voorspellen van een voornaam.

Een goede clustering zou de clustering op basis van ‘diagnose’ kunnen zijn. In dit geval is er een reŽle kans dat er een verband bestaat tussen de patiŽntengegevens, waaronder symptomen, en de ziekte. Bovendien zou een patroon dat kan voorspellen welke ziekte iemand heeft wel degelijk interessant en nuttig zijn.

3.2.2. Redenen om te clusteren

Doelstelling van de gebruiker

Vaak is men niet geÔnteresseerd in de ganse database maar is men geÔnteresseerd in:

In dit geval is het dus zinvol de database op te splitsen in deze zinvolle groepen of klassen om te kunnen onderzoeken:

Niet homogene relaties

Patronen in een bedrijfsomgeving of in de werkelijke wereld zijn bovendien vaak niet homogeen, dit betekent dat ze slechts voor een gedeelte van de dataset of van het probleemdomein gelden. Traditionele methoden (vb. statistiek) schieten in dit geval tekort. Soms is het misschien wel mogelijk om een homogene formule te vinden maar deze formule zal dan te gecompliceerd en onbegrijpelijk zijn.

Vb.

Het kan zijn dat we geen duidelijk karakteristieke beschrijving vinden voor onze klanten maar dat we een dergelijke beschrijving wel vinden voor onze vrouwelijke klanten.

Het opsplitsen van het probleemdomein in onderscheiden klassen biedt dus het voordeel dat het gemakkelijker is om modellen te ontdekken in de deelgebieden en dat het model in elk deelgebied begrijpelijker zal zijn. Het kan immers misschien wel mogelijk zijn een beschrijving te vinden van al onze klanten, maar die beschrijving zal waarschijnlijk enorm complex zijn.

Vereist door het patroonextractie-algoritme

De meeste patroonextractie-algoritmes werken volgens supervised learning. Dit betekent dat ze moeten beschikken over een set van trainingsvoorbeelden met bekende klasselabels om een set van vooraf gedefinieerde concepten te leren. Een voorbeeld hiervan zijn beslissingsboomalgoritmes zoals ID3.

3.2.3. Drie manieren om een trainingsset te clusteren

3.2.3.1. Clusteren door de gebruiker: supervised learning

Figuur 9 Supervised learning

Supervised learning houdt in dat de gebruiker expliciet vertelt welke voorbeelden of records in welke cluster (klasse) moeten komen. Deze keuze kan bijvoorbeeld gebaseerd zijn op de domeinkennis van de gebruiker.

De gebruiker zal niet manueel aan elk voorbeeld een klasse toewijzen, maar zal een regel definiŽren aan de hand waarvan de klasse van een voorbeeld bepaald kan worden. Deze regel is afhankelijk van de informatie of patronen die de gebruiker hoopt te ontdekken.

Clusteren op attribuutwaarden

Vb.

Clusteren volgens de bron van de gegevens

Vb.

Wanneer men beschikt over een database met klanten van de vestiging in Brussel en een database met de klanten in Antwerpen kan men verschillen opzoeken tussen beide klantengroepen. Dergelijke verschillen kunnen interessant zijn voor beter gerichte marketingcampagnes.

Clusteren op basis van een tijdscode of volgnummer

Vb.

Wanneer we wensen te zoeken naar trends of globale veranderingen in databases kunnen we gebruik maken van snapshots. Snapshots zijn kopieŽn van de operationele database die in een data warehouse worden bijgehouden. Op die manier kunnen we de trends ontdekken en kunnen we volgen hoe de patronen zelf evolueren in de tijd.

Het is echter niet voldoende te bepalen op basis van welke attributen de dataset opgesplitst moet worden. De gebruiker moet ook vastleggen welke attribuutwaarden tot welke klassen aanleiding geven. Dit is vooral belangrijk in het geval van continue attributen. Er moeten dus grenzen gedefinieerd worden voor de klassen.

 

Een eerste mogelijke begrenzing van klassen is binair:

Vb.

klasse 1: attribuut A = a

klasse 2: attribuut A Ļ a

Er kan ook een klasse gedefinieerd worden voor elke mogelijke waarde. Dit is enkel mogelijk wanneer het aantal mogelijke attribuutwaarden niet te groot is.

Vb.

De set van mogelijke waarden = {a1, a2, a3}

De klassen kunnen dan als volgt gedefinieerd worden:

klasse 1: attribuut A = a1

klasse 2: attribuut A = a2

klasse 3: attribuut A = a3

Wanneer er teveel mogelijke attribuutwaarden mogelijk zijn of wanneer het voorspelde attribuut continue is, kunnen meerdere waarden gecombineerd worden in waardesets of intervallen. In dit geval wordt vaak gebruik gemaakt van domeinkennis. Vaak worden voor continue variabelen in de praktijk drempelwaarden of alarmniveaus gebruikt. Wanneer we dergelijke drempelwaarden of alarmniveaus hanteren als grens tussen de klassen verhogen we de kans op relevante ontdekkingen. Ook voor discrete attributen die veel verschillende waarden kunnen aannemen, kunnen we ons beroepen op domeinkennis. Het gebeurt immers niet zelden dat in dergelijke gevallen concepten en concepthiŽrarchieŽn gedefinieerd zijn.

Vb.

Het klasseattribuut kan alle waarden tussen 0 en 1 aannemen.

klasse 1: 0 £ attribuut A < 0,5

klasse 2: 0,5 £ attribuut A £ 1

Vb.

Het klasse attribuut kan 100 verschillende waarden aannemen.

klasse 1: attribuut A ő {a1, a2, ..., a50}

klasse 2: attribuut A ő {a51, ..., a100}

3.2.3.2. Clusteren door clusteralgoritmes: unsupervised learning

Figuur 10 Unsupervised learning

Unsupervised learning houdt in dat het cognitieve systeem zelf de klassen moet ontdekken, de gebruiker definieert geen klassen. Het clusteren gebeurt dan met behulp van een automatisch clusteralgoritme.

Vb.

Traditionele methoden

De traditionele statistische methoden maximaliseren de gelijkenis binnen klassen en minimaliseren de gelijkenissen tussen klassen. Dergelijke methoden werken goed voor numerieke gegevens maar kunnen geen gebruik maken van domeinkennis en achtergrondinformatie.

Numeriek clusteren

Bij numeriek clusteren worden de gegevens opgesplitst op basis van hun afstand in een n-dimensionele ruimte.

Conceptueel clusteren

Conceptuele clustermethoden bepalen clusters op basis van gelijkenis maar maken daarbij ook gebruik van concepten en concepthiŽrarchieŽn gedefinieerd in de domeinkennis. Dergelijke methoden kunnen overweg met nominale en gestructureerd gegevens.

Vb.

3.2.3.3. Interactief clusteren

Alhoewel automatische clusteralgoritmes nuttig kunnen zijn, zijn ze niet altijd in staat nuttige of bruikbare clusters te ontdekken. Vooral wanneer er niet teveel attributen beschikbaar zijn en wanneer visualisatie mogelijk is, is de mens beter in het definiŽren van klassen. Dit heeft aanleiding gegeven tot het ontwikkelen van interactieve clusteralgoritmes die de computer gebruikt voor het berekenen, selecteren en visualiseren van interessante clusters. De gebruiker selecteert dan op basis van domeinkennis de clustering die hem het nuttigst lijkt.

Figuur 11 Visuele voorstelling van clusters

Het grote voordeel van een dergelijke aanpak is dat ook clusters of classificaties waar de domeinexpert of gebruiker anders nooit zou aan gedacht hebben voorgesteld worden. Het ontdekkingsproces is dan niet langer beperkt tot de vermoedens en onmiddellijke doelstellingen van de gebruiker.

3.2.4. Voordelen van domeinkennis en gebruikersinteractie

Wanneer de gebruiker geen klassen definieert, dus in het geval van unsupervised learning, moet het algoritme zelf op zoek naar de meest zinvolle of significante clusteringen. In principe kan voor elke attribuut-waardepaar, attribuut-waardesetpaar en attribuut-waardeintervalpaar een klasse gedefinieerd worden. Zelfs na selectie op basis van significantie kan dit aanleiding geven tot een enorme lijst van mogelijke clusteringen. Deze selectie garandeert echter niet dat een clustering interessant is. Wanneer we daarenboven in beschouwing nemen dat in elke geselecteerde clustering naar mogelijke patronen moet worden gezocht, wordt de complexiteit van unsupervised learning duidelijk.

Vb.

Wanneer men in een medische database met behulp van unsupervised learning op zoek gaat naar symptomen die aanduidingen kunnen zijn voor bepaalde ziektes kan het resultaat patronen bevatten in aard van ‘als voornaam = Geert dan aantal zussen = 2, in 90% van de gevallen’.

Wanneer geclusterd wordt met behulp van concepten en concepthiŽrarchieŽn of wanneer het clusteren gebeurt door of in interactie met de gebruiker zal de performantie van het gehele ontdekkingssysteem hiermee gebaat zijn.

3.2.5. Nadelen van gebruikerstussenkomst

Het is duidelijk dat, wanneer het clusteren volledig overgelaten wordt aan de gebruiker of wanneer het clusteren volledig gebeurt op basis van domeinkennis, er heel wat mogelijk interessante clusteringen genegeerd zullen worden. Domeinkennis en gebruikerstussenkomst kunnen leiden tot een tť beperkte zoekruimte waardoor er potentieel interessante relaties en verbanden kunnen verloren gaan.


3.3. Evaluatie van patronen

Voor elke (onvolledige) groep gegevens is een onbeperkt aantal patronen te construeren. Deze verzameling van alle mogelijke patronen noemen we de zoekruimte. Veel van deze patronen zijn echter niet interessant. We moeten dus op zoek naar dat patroon in de zoekruimte dat de cluster het best beschrijft. Hiervoor hebben we een kwaliteitsfunctie nodig. De kwaliteitsfunctie kan dan samen met een door de gebruiker gedefinieerde drempelwaarde als een soort filter bovenop het data mining systeem geplaatst worden.

3.3.1. Statistische evaluatie

Een beschrijving moet zo goed mogelijk classificeren. Een eerste maatstaf is de mate waarin de beschrijving de training set juist classificeert, dit noemen we de correctheid (correctness). Een beschrijving moet echter niet alleen bekende gevallen correct classificeren, ook onbekende gevallen moeten juist verwerkt worden. De mate waarin onbekende gevallen, de testset, juist geclassificeerd worden, noemen we de geldigheid van een regel (validity) .

3.3.1.1. Voorbeeld

Figuur 12 Voorbeeld van een probleemdomein (de getallen tussen haakjes wijzen op het aantal gevallen)

Tabel 19 Voorbeeld statistische evaluatie

ziekte beschrijving 1 beschrijving 2 totaal coverage

AIDS 9 2 11 9/11 = 0.82

X 1 8 9 8/9 = 0.89

totaal 10 10

accuracy 9/10 = 0.9 8/10 = 0.8

sD(S) = de subset van subset van S die voldoet aan de voorwaarde van D

C = de subset van S die behoort tot klasse C

3.3.1.2. Correctness (9)

Een beschrijving D voor een klasse C is correct wanneer ze geldt voor alle positieve gevallen en niet geldt voor negatieve gevallen.

Sommige symbolische algoritmen zoeken enkel naar volledig correcte regels en beschouwen correctheid als een Booleaans begrip. Het nadeel van een dergelijke aanpak is dat bijna correcte beschrijvingen of regels, die niettemin interessant en nuttig kunnen zijn, niet gevonden worden.

Om de meest veelbelovende beschrijvingen uit een set van incorrecte beschrijvingen te kunnen halen moeten we de notie van correctheid uitbreiden tot een continuŁm van waarden. Deze aanpak levert meer interessante en nuttige maar bijna correcte patronen op. Een dergelijke aanpak is typisch voor statistische algoritmes.

Juistheid van classificatie: classification accuracy

De juistheid van classificatie is de waarschijnlijkheid dat een regel correct classificeert. Het is dus de waarschijnlijkheid dat een patiŽnt die voldoet aan de beschrijving 1 aan AIDS lijdt.

= 9/10 = 0.9

Bereik: coverage

Het bereik van een regel is de waarschijnlijkheid dat een willekeurige patiŽnt met AIDS voldoet aan beschrijving 1.

= 9/11 = 0.82

Gebaseerd op deze waarden kunnen we de volgende types van regels onderscheiden:

Tabel 20 Soorten regels

complete regels bereik = 1 voor elk object behorende tot de klasse geldt de beschrijving van die klasse

consistente regels juistheid van classificatie = 1 de regel classificeert altijd correct

correcte regels bereik = 1 ťn juistheid van classificatie = 1

Correctheid: correctness (fc)

De eenvoudigste functie die juistheid van classificatie en bereik verenigt is

= 9 - (10 x 11)/10 = 9 - 110/20 = 9 - 5,5 = 3,5

Deze functie kan intuÔtief begrepen worden als het verschil tussen het eigenlijke aantal voorbeelden waarvoor de regel correct classificeert en het aantal dat verwacht zou worden indien C onafhankelijk zou zijn van D.

3.3.1.3. Geldigheid of ‘validity’ - fv

Een beschrijving moet ‘geldig’ zijn, d.w.z. ze moet elk nog niet gezien voorbeeld correct classificeren.

De validiteit van een regel kan nooit bewezen worden omdat de regel niet kan worden getest voor alle mogelijke situaties. Daarom hebben we een indicatie nodig van de voorspellende kracht van een beschrijving. De eenvoud van een patroon is ťťn maatstaf die kan gehanteerd worden door het KD-algoritme tijdens de uitvoering. Het valideren t.o.v. de testset gebeurt nadat het systeem reeds getraind is.

Ockham’s razor

De meeste data miningsystemen maken gebruik van Ockham’s razor als een maatstaf voor geldigheid. Deze methode stelt dat ‘hoe eenvoudiger een beschrijving, hoe waarschijnlijker dat het een werkelijk bestaande relatie in de database beschrijft’. De complexiteit van een beschrijving kan gemeten worden a.d.h.v. de lengte van een beschrijving.

Valideren van de regel t.o.v. de testset

De geldigheid van een regel kan ook getest worden d.m.v. een testset. Hierbij wordt gebruik gemaakt van dezelfde formules als bij correctheid, maar wordt de generaliserende kracht van de patronen gemeten; de mate waarin de patronen gelden voor nieuwe gevallen.

Wanneer er te weinig testgegevens beschikbaar zijn kunnen we gebruik maken van ‘ten-fold cross-validation’. De dataset wordt tienmaal verdeeld in een trainingsset en een testset die telkens respectievelijk 90 % en 10 % van de trainingsvoorbeelden bevatten. Het systeem wordt telkens getraind en getest en het gemiddelde van de 10 tests geeft aan hoe goed het systeem werkt.

Wanneer er een significant verschil optreedt tussen de correctheid en de geldigheid van een patroon kan dit te wijten zijn aan:

In het geval er sprake is van traag veranderende patronen is het van belang het systeem op regelmatige tijdstippen opnieuw te trainen. Een aanwijzing van dergelijke veranderingen is wanneer het systeem consistent beter scoort, wanneer het met recente gegevens getraind is.

Vergelijkingspunten voor de prestatie van een systeem

Natuurlijk wordt van een data miningsysteem niet geŽist dat het 100% juiste patronen zou genereren dus moeten we een vergelijkingspunt hebben. Data miningsystemen moeten geŽvalueerd worden ten opzichte van de beste beschikbare techniek. Deze beste beschikbare techniek kan de null hypothese, een expert, een panel van experts, een expertsysteem of een vroeger resultaat van data mining zijn.

Bovendien moet er niet alleen rekening gehouden worden met het aantal juiste voorspellingen of classificaties, maar ook met het aantal bijna juiste voorspellingen, gevallen waarbij het werkelijke klasse als tweede of derde mogelijkheid werd voorspeld.

Tabel 21 Diagnose van sojaboonziektes (68)

correct near-correct

AQ11 97,6 % 100 %

expert 71,8 96,9 %

3.3.1.4. De informatie-inhoud van een regel: j-measure en J-measure (29 & 14)

De hierna beschreven evaluatiemethode vergelijkt het a priori geloof van een regel met het a posteriori geloof. Dit betekent dat men de mate van vertrouwen waarmee men een klasse kan toewijzen aan een voorbeeld zonder te beschikken over de geŽvalueerde regel vergelijkt met de mate van vertrouwen in classificatie wanneer men wel over die regel beschikt.

j-measure

De gemiddelde gemeenschappelijke informatie van de gebeurtenissen xi en y in functie van de a posteriori waarschijnlijkheidsdistributie van X. De j-measure is altijd positief en is een goede maat van hoe verschillend het a priori en a posteriori geloof in X is. Bruikbare regels hebben een hoge graad van ongelijkheid.

J-measure

De J-measure is de gemiddelde informatie-inhoud van een regel en symboliseert het afwegen van juistheid en eenvoudigheid.

3.3.1.5. t-weight en d-weight (9)

t-weight:

d-weight:

3.3.1.6. Confusion matrix en chi-square test van Massy

Een confusion matrix is een samenvatting van het aantal correcte en incorrecte classificaties (53).

Tabel 22 Confusion matrix

Actual classification

A B

Predicted A n11 n12

classification B n21 n22

Een andere veel gebruikte methode voor het testen van de significantie van de resultaten data miningsysteem is de chi-square test:

N= aantal voorbeelden

O = geobserveerde frequentie

E = verwachtte frequentie

Een hoge waarde voor c≤ duidt op een grote afwijking van de null hypothese en dus op een statistisch significante classificatie

3.3.2. Andere facetten van patroonevaluatie

Nieuwheid of ‘novelty’

Ontdekken is het vinden van iets wat voorheen onbekend was. Een KD-systeem is dus een systeem dat kennis vindt die voorheen niet beschikbaar was, d.w.z. kennis die niet impliciet aanwezig was in zijn algoritmes of expliciet aanwezig was in de representatie van domeinkennis. We spreken dus over nieuwe informatie wanneer er een voldoende afwijking bestaat vergeleken met bestaande classificatiemethoden. Deze bestaande classificatiemethoden kunnen gebaseerd zijn op:

Voor het testen van de afwijking ten opzichte van de null hypothese kunnen we werken met de statistische evaluatiemethoden. Het vergelijken van ontdekte patronen met bestaande kennis kan op twee manieren gebeuren:

Bij het automatisch vergelijken met de knowledge base moeten de ontdekte patronen in een geschikte representatievorm staan. Bovendien moet de gebruiker specificeren wat er moet gebeuren wanneer de ontdekte kennis reeds bestaat in de knowledge base, wanneer de ontdekte kennis nieuw is en wanneer de ontdekte kennis ingaat tegen regels in de knowledge base.

Wanneer de gebruiker de ontdekte patronen manueel evalueert, moet ervoor gezorgd worden dat de drempelwaarden voor statistische significantie voldoende hoog zijn, anders zal de gebruiker zowel significante als niet significante patronen moeten evalueren. Voordeel is wel dat de gebruiker in dit geval ook andere, moeilijk te kwantificeren criteria kan hanteren.

Nut

De ontdekte patronen moeten niet alleen significant en nieuw zijn maar ook bruikbaar. Ze moeten geŽvalueerd worden op basis van de doelstellingen van de gebruiker.

Impact

Voor het bepalen van de mate waarin een patroon interessant is in een gegeven situatie is het eveneens nodig de impact van een patroon of regel in overweging te nemen.

Vb.

Stel nu dat het bedrijf waarvoor dit patroon geldt, 99% van zijn omzet realiseert in Vlaanderen kan het toch interessanter zijn verder te onderzoeken wat tot die toename met 5% geleid heeft i.p.v. te onderzoeken wat die toename met 50% in WalloniŽ teweeg heeft gebracht.

De impact van een patroon beÔnvloedt dus het relatief belang van een patroon. De factoren die de impact van een patroon beÔnvloeden variŽren van probleem tot probleem. Het beoordelen van de impact van een regel vergt dus domeinkennis en is een taak van de gebruiker of domeinexpert.

Een kostfunctie (53)

Kostfuncties kunnen een bijkomende verfijning vormen van de classificatie. De kost (opbrengst) van misclassificatie (juiste classificatie) kan berekend worden en dan kan de classificatie gebeuren volgens een principe dat de totale kost minimaliseert of de totale opbrengst maximaliseert.

Nadeel: in de praktijk is de kost van misclassificatie soms moeilijk te berekenen.

Beoordelen van voorwaarden in het patroon

We kunnen kengetallen associŽren met de verschillende beschikbare attributen. Een eerste mogelijkheid is dat dit kengetal het relatief belang van een attribuut weergeeft. Dergelijke kengetallen moeten door de gebruiker op voorhand vastgelegd worden.

Vb.

Wanneer een direct mailing bedrijf vooral geÔnteresseerd is in de invloed van leeftijd op het al dan niet antwoorden op een bepaald aanbod en minder op de invloed van de woonplaats dan kan aan ‘leeftijd’ een waarde 1 toegewezen worden en aan attribuut ‘woonplaats’ de waarde 0. De evaluatiecomponent zal dan patronen die gebruik maken van condities op attribuut ‘leeftijd’ een hogere score toedienen.

Het kengetal kan ook gebruikt worden om risico’s of kosten die gepaard gaan met een bepalen van een waarde voor een attribuut weer te geven. Een waarde 1 zou dan wijzen op een hoge kostprijs.

Vb.

Het kan zijn dat in een medische toepassing een sterke correlatie ontdekt wordt tussen de uitkomst van een bepaalde test en een bepaalde ziekte. Dit patroon zou heel nuttig kunnen zijn voor het stellen van diagnoses. Nu kan het echter zijn dat de test waarvan sprake is ofwel enorm duur is ofwel het risico inhoudt dat de patiŽnt overlijdt. Alhoewel dit patroon wel interessant en significant is, is het niet erg bruikbaar.

Wanneer we werken met kengetallen die slaan op risico of kostprijs dan zullen patronen die gebruik maken van attributen met een hoge waarde voor dit kengetal een lage beoordeling krijgen.

Kwaliteitsfunctie

De kwaliteitsfunctie kent een gewicht of belang toe aan alle kwaliteitscriteria voor patronen en combineert deze om de algemene kwaliteit van een patroon te berekenen. In de kwaliteitsfunctie moeten dus zoveel mogelijk criteria in overweging genomen worden, zowel statistisch als niet statistische.

De algemene kwaliteit van een patroon is in dit geval de gewogen som van alle criteria. Het vinden van de juiste samenstelling van criteria en gewichten is dan een vorm van afstellen van het systeem.

We kunnen ook een volgorde definiŽren van de criteria en voor elk criterium een drempelwaarde definiŽren. Enkel de patronen die voldoen aan de drempelwaarde van het eerste criterium worden weerhouden en geŽvalueerd op basis van het tweede criterium. Na evaluatie van het laatste criterium houden we de beste beschrijvingen over. Hier bestaat het fijnstellen van het systeem uit het bepalen van de volgorde en de drempelwaarden.


3.4. Ontdekken van patronen

Gebaseerd op de trainingsset en (eventueel door de gebruiker gedefinieerde) klassen kan een data miningsysteem vele beschrijvingen construeren. Sommige van deze beschrijvingen zijn meer correct dan andere, d.w.z. sommige beschrijvingen zullen meer succesvol zijn in het classificeren van nog niet geziene voorbeelden (en dus in het vastleggen van de - onbekende - relaties die in de gegevens zitten).

Wanneer we een maatstaf voor de kwaliteit van een beschrijving gedefinieerd hebben, is de constructie van een beschrijving niets meer dan een zoekprobleem: het vinden van de beste beschrijving in de set van alle mogelijke beschrijvingen. Deze set is over het algemeen te groot om op een exhaustieve manier te werk te gaan. Daarom hebben we een efficiŽnter algoritme nodig.

De meeste machine learning- en data miningsystemen kiezen een initiŽle beschrijving die ze op een iteratieve manier aanpassen om de kwaliteit te verbeteren. Deze aanpassingen zijn operaties op een beschrijving. De set van beschrijvingen, samen met deze operaties, en de kwaliteitsfunctie noemen we de zoekruimte.

3.4.1. De zoekruimte

3.4.1.1. descriptieruimte

De descriptieruimte of beschrijvingsruimte D is de set van alle mogelijke omschrijvingen in een bepaalde representatie. Met elke beschrijving Di in D komt een subset sD(S) uit de training set S overeen. De grootte van de descriptieruimte is afhankelijk van het gekozen representatieformalisme en van de kenmerken van de domeinen van de attributen.

Het representatieformalisme

In het geval van een propositional-like representatie is voor elke clustering de descriptieruimte gedefinieerd als het cartesiaans product van de domeinen van de andere attributen. M.a.w., de descriptieruimte is de verzameling van alle mogelijke combinaties van de waarden van de onafhankelijke attributen. Voor krachtiger representatieformalismen die onder andere ook verbanden tussen attributen kunnen modelleren is de descriptieruimte groter.

Het domein van de attributen

Het aantal beschrijvingen dat een systeem kan vinden hangt in grote mate af van het type, de grootte en de structuur van het domein van de attributen.

Het domein van nominale of categorische attributen bestaat uit onafhankelijke symbolen of namen waarvan de waarden niet geordend zijn. Hoe meer verschillende waarden het attribuut kan aannemen, hoe meer descripties er geconstrueerd en dus onderzocht kunnen worden. Het attribuut ‘voornaam’ zal dus aanleiding geven tot een grotere descriptieruimte dan het attribuut ‘bloedsoort’.

De invloed van continue attributen op de grootte van de descriptieruimte hangt af van de precisie waarmee dergelijke attributen worden verzameld. De descriptieruimte voor een set van attributen waarvan een attribuut de waarden {high, medium, low} kan aannemen zal kleiner zijn dan de descriptieruimte voor dezelfde set van attributen waarbij dat attribuut de lichaamstemperatuur tot op 0.1įC nauwkeurig voorstelt.

Informatie over de structuur van het domein, domeinconcepten en concepthiŽrarchieŽn, wordt gebruikt voor de generalisatie- en specialisatieoperaties.

Voordelen van domeinconcepten:

Nadelen: het a priori beperken van de descriptieruimte maakt het ontdekken van mogelijk interessante patronen, die niet binnen de huidige structuren of domeinkennis passen, onmogelijk.

3.4.1.2. Operations

Er zijn 2 grote types van operaties op beschrijvingen: generaliserende en specialiserende operaties. Generaliserende operaties verwijderen van een conditie of het vervangen van een concept door een concept van een hoger niveau, verzwakken de beschrijving en vergroten het bereik. Specialiserende operaties maken de beschrijving strenger en verkleinen het bereik.

3.4.1.3. Kwaliteitsfunctie

De kwaliteitsfunctie beperkt het aantal mogelijke patronen tot deze die voldoen aan de door de gebruiker gedefinieerde kwaliteitscriteria (zie evaluatie van patronen).

3.4.2. De zoekstrategie

Het doel is zo snel mogelijk het patroon met de hoogste top - de hoogste waarde voor de kwaliteitsfunctie - te vinden. Hiertoe definiŽren we operaties die een patroon omzetten in een nabijgelegen patroon. De gekozen zoekstrategie moet in zo weinig mogelijk stappen het globale maximum vinden.

Het basisidee is te starten met een initiŽle beschrijving D1 en deze iteratief aan te passen totdat de kwaliteitsfunctie een bepaalde door de gebruiker gedefinieerde drempelwaarde overschrijdt.

1. eerst wordt een hypothese geformuleerd

2. deze hypothese wordt geverifieerd aan de hand van een kwaliteitsfunctie

3. de hypothese wordt aanvaard, geweigerd of verbeterd totdat een correcte hypothese gevonden wordt

3.4.2.1. InitiŽle beschrijving

Een eerste onderscheid tussen zoekalgoritmes is de keuze van de initiŽle beschrijving.

Bottom-up of data-driven: incrementele generalisatie van gespecialiseerde hypotheses

De initiŽle beschrijving is simpelweg de set, gevormd door alle voorbeelden van de doelklasse. Deze beschrijving is correct maar te complex. Om de complexiteit te verminderen wordt de beschrijving herhaaldelijk gegeneraliseerd. Dit resulteert in ťťn enkele regel die de voorbeelden (voldoende) correct classificeert.

Figuur 13 Een bottom-up leerproces

De leertaak bestaat erin een simpele beschrijving te vinden die alle positieve en geen van de negatieve voorbeelden omvat.

(a) de cover van de initiŽle descriptie zijn de 4 positieve voorbeelden

(b) de tweede beschrijving is meer algemeen

(c) de uiteindelijke beschrijving heeft als cover alle positieve gevallen en geen van de negatieve

Vb.

Top-down of model-driven: specialisatie van algemene hypothese

We kiezen een initiŽle, eenvoudige beschrijving die geldt voor de gehele trainingsset.

Deze beschrijving wordt geleidelijk aan verfijnd door middel van een sequentie van generalisatie en specialisatie-operaties, totdat de kwaliteit een bepaalde drempelwaarde overschrijdt.

De initiŽle relatie omvat 2 positieve en 1 negatief voorbeeld (a), dit verbetert langzaam aan (b) totdat de relatie gevonden wordt die alle positieve en geen negatieve voorbeelden omvat (c).

Figuur 14 Een top-down leerproces

Vb.

3.4.2.2. De zoekgrafiek - ‘search graph’

Op de initiŽle beschrijving kunnen we een aantal operaties toepassen en elk van deze operaties resulteert in een nieuwe beschrijving. Door herhaaldelijk dergelijke operaties toe te passen kunnen we een zoek-grafiek opbouwen, waar de beschrijvingen de knopen vormen en de operaties de pijlen.

Figuur 15 Voorbeeld van een zoekgrafiek

Er moet zo snel mogelijk een beschrijving van voldoende kwaliteit gevonden worden (bijvoorbeeld ťťn van de gemarkeerde doelknooppunten). De constructie van een regel kan dus gekarakteriseerd worden als een zoekproces, waarbij operaties geprobeerd worden totdat een bepaalde sequentie van operaties gevonden wordt die resulteert in een regel van voldoende kwaliteit. De volgorde waarin en de manier waarop deze sequenties gecontroleerd worden wordt de zoekstrategie genoemd (9).

Onherroepelijk zoeken: irrevocable search

Een operatie wordt geselecteerd en toegepast zonder de mogelijkheid tot herziening. Dit betekent dat de keuze en volgorde van operaties bepaalt welk deel van de zoekruimte doorzocht wordt.

Zoeken met de herzieningsmogelijkheid: tentative search

Een toe te passen operatie wordt gekozen en toegepast maar herziening is mogelijk zodat je kan terugkeren tot een bepaald punt in de berekening om een andere operatie te kiezen.

3.4.2.3. Operaties

Met operaties bedoelen we bewerkingen die worden uitgevoerd op een beschrijving om een nieuwe beschrijving met een hogere kwaliteit te genereren. Over het algemeen worden positieve voorbeelden bottom-up gebruikt, d.w.z. ze geven aanleiding tot veralgemening, en worden negatieve voorbeelden top-down gebruikt, d.w.z. ze geven aanleiding tot een specialisatie van de regel.

GENERALISATIE

Generalisatie is het combineren van meerdere gevallen in ťťn algemener geval.

Kenmerken van generalisatie:

Verwijderen van condities: dropping conditions

Een belangrijke vorm van generalisatie is de identificatie en het verwijderen van overbodige en irrelevante condities zonder informatieverlies of met een minimaal informatieverlies. We zoeken met andere woorden naar de ‘minimale set van attributen’ (31). Wanneer een gelijkaardige regel gedefinieerd is voor alle gevallen van een klasse dan kunnen al die regels vervangen worden door ťťn algemene regel voor die klasse door het verwijderen van een conditie.

Vb.

Stel dat we de volgende set van regels ontdekken voor alle provincies in BelgiŽ:

Het attribuut provincie is duidelijk niet relevant. Door het verwijderen van de conditie ‘provincie = ‘ kan de set van regels vereenvoudigd worden tot:

Generaliseren op basis van concepten en concepthiŽrarchieŽn

Wanneer we beschikken over door de gebruiker gedefinieerde concepten en concepthiŽrarchieŽn kunnen we attribuutwaarden of concepten van een lager niveau vervangen door een concept van een hoger niveau. Dit is de techniek die gehanteerd wordt bij ‘climbing generalization tree’ methoden.

Bovendien worden in de praktijk vaak drempelwaarden gehanteerd die gebruikt worden bij dagelijkse transacties of die gedefinieerd zijn in leidraden en reglementeringen. Ook dergelijke drempelwaarden kunnen gebruikt worden voor generalisatie.

Concepten en concepthiŽrarchieŽn laten toe kandidaatregels te beperken tot deze met een bepaalde woordenschat hetgeen de eenvoud en begrijpelijkheid van de ontdekte regels ten goede komt. Bovendien zullen regels die gebaseerd zijn op een vocabularium, gedefinieerd door de gebruiker, ook zinvoller zijn voor de gebruiker.

Discretiseren van continue attributen

Discretiseren van continue attributen komt overeen met het verminderen van de graad van precisie in de representatie van objecten.

Vb.

Numerieke metingen van temperaturen vervangen door kwalitatieve bereiken zoals Hoog, Laag en Normaal

Het voordeel is dat regelmatigheden in gegevens zichtbaarder worden en gemakkelijker te vatten zijn in regels. Bovendien kunnen vele bestaande systemen niet overweg met continue waarden.

Het nadeel van deze techniek is dat het kan leiden tot ongewenst informatieverlies waardoor interessante patronen verloren kunnen gaan, bijvoorbeeld door het discretiseren in binaire categorieŽn (vb. ID3).

We moeten dus zoeken naar de optimale opsplitsing van het continue domein. Hiervoor bestaan een aantal technieken:

Het bereik in gelijke intervallen splitsen kan, net zoals bij het binair splitsen, leiden tot informatieverlies. Een minimaal verlies aan informatie wordt bereikt met het maximaliseren van de entropie.

Hierarchical Maximum Entropy Discretization (27)

Deze methode voor het discretiseren van continue waarden is gebaseerd op ‘maximum entropy’ en leidt tot een minimum aan informatieverlies. Bij ‘hierarchical maximum entropy discretization’ wordt het bereik van een attribuut iteratief gepartitioneerd zodat de intervallen een gelijke waarschijnlijkheid hebben.

Het kn discretiseringsproces is een proces dat een set van k punten vindt op elke as van de n-dimensionele ruimte. Deze n sets van punten zullen de n-dimensionele ruimte partitioneren in kn cellen, die voldoen aan de maximalisatie van de Shannon entropie.

De Shannon entropy (H) wordt als volgt berekend.

Om fijnere intervallen te verkrijgen kan het ‘maximum entropy discretization process’ opnieuw worden toegepast op elk interval. Een dergelijke aanpak komt overeen met het automatisch opbouwen van een concepthiŽrarchie.

SPECIALISATIE

Specialisatie is het toevoegen van voorwaarden aan een bestaande regel om het bereik, het aantal gevallen waarvoor de regel geldt, te verminderen en de juistheid van classificatie te verhogen. Een voorbeeld van specialisatie is de constructie van beslissingsbomen.

Ook bij specialisatie kan gebruik gemaakt worden van domeinconcepten, bijvoorbeeld om te bepalen op welke basis een tak van een beslissingsboom gesplitst moet worden. Dit splitsen kan op de volgende manieren gebeuren:

3.4.2.4. Stopcriterium

Generalisatie

Generalisatie van een regel wordt stopgezet wanneer:

Specialisatie

Symbolische algoritmes (vb. ID3) proberen het opsplitsingsproces totdat alle voorbeelden in een tak tot dezelfde klasse behoren. In veel praktijkapplicaties is dit niet altijd mogelijk omdat niet alle relevante attributen geÔdentificeerd zijn en omdat niet alle gegevens even betrouwbaar zijn. Om overweg te kunnen met ruis moeten er aanpassingen gebeuren aan het stopcriterium.

Vb.:

Invloed van drempelwaarden (32)

Een kleine drempelwaarde leidt tot een eenvoudige regel maar kan resulteren in te sterke generalisatie en het verlies van belangrijke informatie. Een hoge drempelwaarde kan leiden tot een relatief complexe regel en onvoldoende gegeneraliseerde resultaten. De gebruiker moet dus de gewenste eenvoud van de ontdekte patronen afwegen ten opzicht van de juistheid.

3.4.2.5. Uitputtende zoekstrategieŽn

Uitputtende zoekstrategieŽn of niet geÔnformeerde zoekstrategieŽn gebruiken geen heuristieke informatie om de zoektocht te leiden, de operaties worden arbitrair gekozen. In het geval van ‘irrevocable search’ zal dus niet noodzakelijk het beste deel van de zoekruimte doorzocht worden en voor ‘tentative search’ betekent het negeren van heuristieke informatie of domeinkennis dat het langer zal duren om een aanvaardbare oplossing te vinden.

Wanneer we een uitputtende zoekstrategie gebruiken voor supervised learning moet uit alle mogelijke beschrijvingen, die beschrijving geselecteerd worden die de klasse het best beschrijft. In het geval van unsupervised learning moet voor elke clustering alle beschrijvingen geprobeerd worden.

Een belangrijk nadeel van uitputtende zoekstrategieŽn is dus de inefficiŽntie en de enorme complexiteit. Het grote aantal mogelijke patronen en clusteringen resulteert in een immens grote zoekruimte. Wanneer we er daarenboven ook mee rekening houden dat al deze patronen en clusteringen getest en gevalideerd moeten worden is het duidelijk dat dit, zelfs voor niet al te grote databases, enorm duur en tijdrovend is. Daarom moeten er manieren gevonden worden om de keuze van operaties op een optimale manier te laten gebeuren.

 

3.4.2.6. Heuristieke zoekstrategieŽn

Een oplossing voor de grootte van de zoekruimte is het gebruik van ‘strategic common sense’ of strategisch gezond verstand (12). Strategisch gezond verstand is gelijkaardig aan de set van heuristieken die, soms onbewust, door experts gebruikt wordt om te beslissen wat het beste alternatief is. Het idee achter ‘heuristic search’ is het verminderen van de ‘search effort’ en het versnellen van het zoekproces, door zorgvuldige selectie van operaties, zodat er zo snel mogelijk een beschrijving gevonden wordt. Het systeem heeft dus heuristieke informatie of domeinkennis nodig om de knooppunten te selecteren die op het kortste pad liggen naar de doelknooppunt.

Hill Climber strategy

De ‘hill climber strategy’ kiest altijd die operatie die resulteert in de grootste kwaliteitswinst. Daarom moet het systeem de kwaliteit berekenen (of schatten wanneer berekenen te duur uitvalt) van alle mogelijke operaties.

Vb.

De information theoretic measurement van ID3

Gebaseerd op informatie in the trainingsset wordt de waarschijnlijkheid geschat dat de toepassing van een bepaalde operatie zal resulteren in een simpele maar correcte structuur.

Beperkingen op de operaties

Irrelevante attributen

Niet alle attributen zijn relevant.

Vb.

Het attribuut ‘voornaam’ is niet relevant voor het stellen van een medische diagnose.

Soms hangt de relevantie van een attribuut ook af van de waarde van andere attributen. Dergelijke attributen kunnen in bepaalde gevallen genegeerd worden.

Vb.

Het attribuut ‘zwanger?’ is enkel betekenisvol wanneer het geslacht van de persoon ‘vrouwelijk’ is.

De gebruiker zou voor elk attribuut kunnen bepalen hoe relevant het is. Dergelijke domeinkennis kan dan gebruikt worden in de kwaliteitsfunctie zodat deze een hoge waarde geeft aan operaties die een conditie op irrelevante attributen verwijderen en een lage waarde geeft voor operaties die een conditie op irrelevante attributen toevoegen.

Verbanden tussen attributen

Voor sommige applicaties kunnen er verbanden bestaan tussen attributen die hun set van mogelijke waarden beperken. De kwaliteit van een beschrijving zal dus niet verbeteren wanneer een conditie toegevoegd wordt die al geÔmpliceerd wordt door de condities in de beschrijving. De verwachtingsscore van dergelijke operaties zal dus laag zijn.

Vb.

De lengte van een object kan gedefinieerd worden als altijd groter of gelijk aan zijn breedte.

Sturing door de gebruiker

Een andere bron van heuristieke kennis is de gebruiker, een expert in het domein. Het systeem presenteert meerdere beschrijvingen, eventueel samen met hun verwachte of geschatte kwaliteit en de gebruiker selecteert hieruit ťťn of meerdere beschrijvingen die het systeem dan verder moet specialiseren of generaliseren.

Reeds ontdekte klassen en regels

Ook vroeger ontdekte regels kunnen het zoekproces leiden. Dit is vooral belangrijk wanneer de set van voorbeelden regelmatig aangevuld wordt en de voorheen gegenereerde beschrijvingen verfijnd moeten worden om consistent te blijven met de nieuwe set van voorbeelden (incrementeel leren).

Voor- en nadelen

Het gebruik van domeinkennis en de interactie met de gebruiker kan de efficiŽntie van een zoekalgoritme sterk verbeteren. Nadelig is echter dat hierdoor onverwachte maar daarom niet minder bruikbare patronen reeds op voorhand uitgesloten worden. Bovendien presteren dergelijke systemen slecht wanneer de heuristieken van een mindere kwaliteit zijn en kunnen ze niet altijd ontsnappen aan lokale minima.

 

3.4.2.7. Alternatieve zoekstrategieŽn

Genetische algoritmes

John Holland: ontwikkelde en analyseerde genetische algoritmes in het begin van de jaren ‘70.

Een genetisch algoritme is een zoekprocedure gemodelleerd naar de mechanismen van natuurlijke selectie. Het basisidee is het gebruik van een initiŽle set van kandidaatsbeschrijvingen, de populatie. Elk lid van die eerste generatie wordt geŽvalueerd waarbij aan goede kandidaten een hoge score wordt toegewezen. Kandidaatsbeschrijvingen die een goede score behalen kunnen meerdere keren worden geselecteerd voor de tweede generatie, deze met een lage score worden verwijderd. De vrijgekomen plaatsen worden dan ingenomen door combinaties en mutaties van goede beschrijvingen. Combinatie of crossover houdt in dat delen van twee goede originele beschrijvingen gecombineerd worden. Bij mutatie worden ťťn of meerdere delen van een goede beschrijving gewijzigd. Het resultaat is een tweede generatie van kandidaat-beschrijvingen die opnieuw geŽvalueerd, gemuteerd en gecombineerd worden.

Figuur 16 De werking van een genetisch algoritme

Theoretische analyses hebben aangetoond dat genetische algoritmes de kennis die opgebouwd wordt gedurende het zoeken, op een zodanige manier gebruiken dat er:

Simulated annealing

Bij simulated annealing worden de operaties met een zekere willekeur gekozen zodat het zoekproces kan ontsnappen aan lokale maxima. Naar het einde toe neemt de willekeur af zodat het zoekproces zich in het globale maximum kan stabiliseren.

3.4.3. Domeinkennis en gebruikersinteractie

3.4.3.1. Domeinkennis: trade-off tussen efficiŽntie en volledigheid

De ontdekte kennis is niet altijd nuttig bijvoorbeeld omdat ze niet binnen de interessesfeer van de gebruiker past, overbodig is of inconsistent is met reeds bestaande kennis.

Het ontdekken van patronen is een dure aangelegenheid, vooral qua computertijd. Daarom gebruiken we extra kennis over de vorm en de inhoud van en beperkingen op de gegevens, het domein van de database, de context van de ontdekkingstaak en het doel dat wordt nagestreefd om de zoektocht naar interessante kennis te sturen. Deze vorm van kennis noemen we domeinkennis of achtergrondkennis en wordt bijgehouden in een data dictionary, de rest bestaat in handleidingen of in het geheugen van domeinexperts.

Het doel van het gebruik van domeinkennis in data miningsystemen is het verkleinen van de zoekruimte door het algoritme in de richting van interessante patronen te sturen (‘bias’). Dit kan gebeuren door:

Het sturen van het leerproces noemt men ook wel constructief leren en heeft als voordeel dat het algoritme efficiŽnter wordt en dat de ontdekte kennis begrijpelijker, nuttiger en relevanter is. Om deze redenen stellen vele onderzoekers dat KD-algoritmes om significante ontdekkingen te kunnen doen, gebruik moeten maken van domeinkennis.

Het grote nadeel van domeinkennis is het van het algoritme bevooroordeeld wordt. D.w.z. dat een algoritme dat sterk steunt op domeinkennis niet langer objectief is en potentieel bruikbare patronen a priori uitsluit. Het systeem weet immers wat het zoekt en waar het ernaar moet zoeken. Bovendien zullen ontdekte patronen die ingaan tegen hetgeen algemeen gangbaar is, of die niet passen binnen bestaande denkwijzen evenmin ontdekt worden. Een bijkomend nadeel is dat, zoals blijkt uit de ervaring met expertsystemen, het onttrekken en efficiŽnt representeren van domeinkennis geen eenvoudige zaak is.

3.4.3.2. Gebruikersinteractie: trade-off tussen autonomie en veelzijdigheid

Eťn van de streefdoelen van data mining of knowledge discovery is autonomie, het systeem doorzoekt de gegevens autonoom en presenteert de resultaten van deze zoektocht aan de gebruiker. Wanneer we echter de algoritmes bekijken die gebruikt worden in bestaande KDD applicaties vinden we weinig algoritmes die autonoom zijn. In bijna alle systemen is een grote mate van sturing door de gebruiker vereist. De goede werking van het data miningsysteem is immers afhankelijk van de het fijnstellen van drempelwaarden, het definiŽren van klassen, concepten en hiŽrarchieŽn.

Een mogelijkheid om algoritmes autonomer te maken is het inbouwen van specifieke domeinkennis. In dit geval spreken we van verticale integratie, algoritmes die ontworpen zijn voor ťťn bepaalde probleemdomein. Het autonomer maken van algoritmes gaat dus gepaard met een afgenomen veelzijdigheid, een beperktere inzetbaarheid en een kleinere variŽteit aan mogelijke ontdekkingen. De meer veelzijdige algoritmes daarentegen, beschikken over een groot arsenaal aan discoverytechnieken en kunnen dus in veel verschillende probleemdomeinen ingezet worden maar zijn dan weer sterk afhankelijk van gebruikersinteractie.

3.4.3.3. Conclusie

Omwille van de grootte van de zoekruimte moet een data miningsysteem gebruik maken van domeinkennis en moet de gebruiker het systeem eventueel bijsturen. De nadelen hiervan zijn, zoals hiervoor reeds vermeld, dat het data miningsysteem sterk in een bepaalde richting geduwd zal worden. Enkel patronen die gebruik maken van domeinconcepten en concepthiŽrarchieŽn of die passen binnen de vermoedens en hypothesen van de gebruiker zullen ontdekt kunnen worden.

Toch zijn er een aantal stappen die ondernomen kunnen worden om de afhankelijkheid van domeinkennis en gebruikersinteractie te verminderen.

Bootstrapping approach

De ‘bootstrapping approach’ houdt in dat in een eerste fase de domeinkennis (her)ontdekt wordt. Dit is mogelijk omdat de exacte regels of patronen die een algoritme ontdekt meestal het resultaat zijn van beperkingen in het probleemdomein, concepten of hiŽrarchieŽn.

Opslaan en hergebruiken van kennis

Een data miningsysteem zal de eigen ontdekkingen moeten kunnen opslaan en hergebruiken zodat de bootstrappingfase ťťnmalig is.

EfficiŽntere algoritmes

Een efficiŽnter algoritme kan de tijd nodig om het systeem te trainen verminderen zodat de overlast van de ‘bootstrapping approach’ geminimaliseerd wordt.

Vb.

Beter gebruik maken van parallelle technieken en grote geheugens

Snellere hardware

Snellere hardware zorgt ervoor dat op dezelfde of zelfs op een kleinere tijdspanne, een groter deel van de zoekruimte doorzocht kan worden. De belangrijkste reden voor gebruik van domeinkennis, de complexiteit van het zoekprobleem, valt dan grotendeels weg.


3.5. Output

De output van een data miningsysteem wordt in de eerste plaats gebruikt om het systeem zelf fijn te stellen. De gebruiker of domeinexpert moet op basis van de output kunnen beslissen welke drempelwaarden verhoogd of verlaagd moeten worden, welke aanpassingen er nodig zijn aan de kwaliteitsfunctie, of er behoefte is aan extra gegevens of dat er juist irrelevante gegevens verwijderd moeten worden. Dit betekent dat de output begrijpelijk moet zijn en dat de outputcomponent flexibel en krachtig genoeg moet zijn om de ontdekte kennis op de gepaste manier voor te kunnen stellen.

Wanneer de output van het data miningsysteem een aanvaardbare niveau heeft bereikt is het de bedoeling de ontdekte kennis’ effectief te gebruiken, in te schakelen in bedrijfsprocessen. Dit betekent dat de output geschikt moet zijn met het oog op een bepaald doel. Afhankelijk van wie of wat de ontdekte kennis moet gebruiken zal de gewenste vorm van die kennis anders zijn.

De ontdekte patronen moeten eenvoudig zijn

De ontdekte patronen en regels moeten door een mens geÔnterpreteerd, aanvaard en gebruikt worden. Daarom mogen deze patronen niet te complex zijn. Bovendien wijzen complexe patronen in de meeste gevallen op fouten en uitzonderingen in de gegevens.

Eťn mogelijkheid om patronen eenvoudig te houden, is het definiŽren van een drempelwaarde voor het aantal voorwaarden in het conditionele gedeelte. Op deze manier zal het algoritme verder veralgemenen of stoppen met specialiseren totdat aan de drempelwaarde voldaan is. Het nadeel hiervan is wel dat dit aanleiding kan geven tot te sterk veralgemeende patronen.

Verder kan de output van een data mining systeem ook vereenvoudigd worden met behulp van de volgende technieken:

De ontdekte patronen moeten begrijpelijk zijn

De ontdekte patronen moeten in begrijpelijke vorm aan de gebruiker gepresenteerd worden.

Vb.

Als leeftijd < 25 en Rijlessen = nee

Dan in_fout_bij_ongeluk = ja

Met waarschijnlijkheid = 0,2 tot 0,3

Neurale netwerken worden vaak niet als echte data miningsystemen beschouwd omdat ze geen verklaring kunnen bieden voor de manier waarop ze een bepaalde beslissing nemen. Deze kritiek is tegenwoordig echter minder gegrond aangezien men technieken ontwikkeld heeft om de patronen in neurale netwerken te visualiseren en te formaliseren.

Flexibiliteit

Data miningsystemen moeten patronen met variabele precisie en begrijpelijkheid kunnen genereren afhankelijk van de probleemspecifieke doeleinden. Bovendien is het heel belangrijk dat de eindgebruiker over de middelen beschikt om de ontdekte kennis op verschillende manieren voor te stellen. Zelfs voor dezelfde kennis kunnen verschillende mensen immers een verschillende representatievorm prefereren. Vooral uitgebreide visualisatiemogelijkheden zijn in dit opzicht onontbeerlijk.

Consistentie

De ontdekte patronen moeten consistent zijn met bestaande domeinkennis. Dit betekent dat ofwel de bestaande domeinkennis aangepast moet worden aan de nieuw verworven inzichten of dat de nieuw ontdekte kennis herzien moet worden.

De vorm van de output moet aangepast kunnen worden aan hetgeen waarvoor men de ontdekte kennis wil gebruiken

De output van een data miningsysteem kan op verschillende manieren gebruikt worden:

Afhankelijk van de gekozen bestemming van de ontdekte kennis zal men ook opteren voor een andere representatievorm. Natural language is bijvoorbeeld geschikt wanneer de ontdekte kennis direct door de eindgebruiker moet gebruikt worden, maar is niet geschikt voor verdere manipulatie in expertsystemen.

De gebruiker

Wanneer het de bedoeling is dat de gebruiker onmiddellijk met de ontdekte patronen aan de slag kan moeten deze voorgesteld worden in een vorm geschikt voor die eindgebruiker.

Vb.

Bovendien zal vanuit het standpunt van een eindgebruiker de uitleg van een patroon vaak interessanter zijn dan het patroon zelf, dus het resultaat moet een verdere analyse vergemakkelijken.

Tenslotte zullen patronen bruikbaarder en begrijpelijker zijn wanneer ze uitgedrukt worden in een door de gebruiker gedefinieerde terminologie.

Knowledge base

Ontdekte patronen kunnen in een knowledge base gedeponeerd worden als aanvulling bij de reeds bestaande domeinkennis. In dit geval moeten domeinkennis en ontdekte kennis dezelfde representatievorm hebben of tenminste eenvoudig converteerbaar zijn.

DBMS

Eťnmaal de kennis ontdekt en voorgesteld is, moet ze geÔntegreerd worden met de database. De knowledge base kan dan dienen als een front-end voor het opvragen van informatie die in de database zit. Een KB die is opgebouwd op basis van een database kan gezien worden als een hoog niveau samenvatting of structuur bovenop de ongestructureerde database.

Vb.

Search engines voor grote tekstuele databases.

De ontdekte regels kunnen ook gebruikt worden om de kwaliteit van de database te bewaken en te verbeteren.

Vb.

Opzoeken van foute gegevens of opvullen van gaten in de database


3.6. Conclusie

Data mining is grotendeels gebaseerd op machine learningtechnieken. Zo wordt de dataset opgesplitst in klassen of clusters en worden daarna, op een bottom-up of top-down manier, initiŽle beschrijvingen gegeneraliseerd en/of gespecialiseerd, om tot beschrijvingen te komen die voldoen aan bepaalde kwaliteitscriteria.

Het grote verschil tussen data mining en machine learning, is het feit dat data mining sterk afhankelijk is van domeinkennis. Het aantal trainingsvoorbeelden, het aantal attributen en de grootte van de attribuutdomeinen liggen doorgaans een flink stuk hoger dan bij machine learning. Dit resulteert in een zoekruimte die niet langer exhaustief doorzocht kan worden. Daarom heeft het algoritme bij het clusteren van de dataset, het zoeken naar patronen en het evalueren van de ontdekte patronen, hulp nodig in de vorm van domeinkennis of gebruikersinteractie. Het grote nadeel hiervan, zo bleek in dit hoofdstuk, is dat het data miningalgoritme tť sterk in een bepaalde richting geduwd wordt zodat een groot aantal interessante patronen verborgen blijft.

Eťn van de grootste uitdagingen van data mining is ongetwijfeld het verminderen van de afhankelijkheid van domeinkennis zijn, zonder daarbij de efficiŽntie van het systeem in het gedrang te brengen.