Samenvatting
Data mining
Inhoudsopgave
1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Data en de distributie ervan . . . . . . . . . . . . . . . . . . . . . . . . . 2
3 Beslissingsbomen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4 Beslissingsbomen prunnen . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 Classificatie algoritmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6 Evaluatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7 Data mining tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8 Data mining, data science & big data . . . . . . . . . . . . . . . . . . . . 23
9 Subgroup discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
10 Regressie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
11 Maximally Informative k-Itemsets . . . . . . . . . . . . . . . . . . . . . . 33
12 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1 Overview
Data mining is het extraheren van tot op heden onbekende en potentieel bruikbare, in-
teressante kennis uit grote data sets. Het wordt ook wel secundaire statistiek genoemd.
Dit is het analyseren van data die aanvankelijk niet voor analyse verzameld is. Zo verza-
melen veel bedrijven vandaag de dag grote hoeveelheden data, vaak voor administratieve
doeleinden en niet perse voor het toepassen van data mining. Dit creëert echter tegelij-
kertijd een grote hoeveelheid ervaring/kennis. Als deze data gemined wordt kan er van
deze ervaring geleerd wordt. Er zijn verschillende redenen om dit te doen:
• Voor het doen van voorspellingen over bijvoorbeeld toekomstige gebeurtenissen of
keuzes die potentiele klanten maken.
• Voor het analyseren van bepaalde processen en dergelijke.
• Voor het optimaliseren van bijvoorbeeld processen en dergelijke.
Er zijn twee stromingen binnen data mining:
Mining for insight
Het doel hiervan is het beter leren kennen en begrijpen van je domein door ander
andere het vinden van regelmatigheden in variabelen.
Black-box mining
Het doel hiervan is het optimaliseren van bijvoorbeeld een proces door het vinden
van een model dat goed werkt, zonder dat je weet hoe het model werkt. Hoe of
waarom het model werkt interesseert je niet, er onstaat dus niet meer inzicht bij
deze methode.
Pagina 1 van 44
, Samenvatting
Een dataset bestaat uit een verzameling instanties, bijvoorbeeld het weer gemeten op 10
Data mining
verschillende dagen. Een instantie wordt gekarakteriseerd door attributen die verschil-
lende aspecten van een instantie meten. Data mining paradigma’s:
Classification: bij deze methode wordt ervan uit gegaan dat je data hebt die
in verschillende klassen georganiseerd kan worden. Je hebt een (binaire) klasse
variabele en je wilt voor toekomstige gevallen bepalen of ze wel of niet in deze
klasse horen. Dit is het meest gebruikte paradigma.
Clustering: bij deze methode wordt er ook met groepen gewerkt, maar hebben
we bij aanvang nog geen labels voor de groepen. We zoeken naar overeenkomsten
in de gevallen zodat we de dataset op kunnen delen in groepen van vergelijkbare
gevallen.
Regression: deze methode lijkt op classificatie. Er is één target waarde, maar in
plaats te bepalen of een geval wel of niet tot een klasse variabele behoort ben je op
zoek naar een exacte, nummerieke waarde.
Association: in deze situatie heb je een object met vele variabelen waarvan je wilt
weten welke variabelen bij elkaar horen. Oftewel, je bent op zoek naar afhankelijk-
heden tussen deze variabelen.
Classificatie maakt gebruik van decision trees. Het doel hiervan is het voorspellen van
een bepaalde klasse variabele voor een object gebaseerd op voorbeeld gevallen. De boom
zorgt ervoor dat de attribuut afhankelijkheden (hetgeen waar het van afhangt of object
wel of niet tot de klasse variabele behoort) expliciet weergegeven worden. Deze onaf-
hankelijkheden zijn echter vaak fuzzy, omdat er meerdere afhankelijkheden meewegen.
Perfecte voorspellingen zijn dan ook zeldzaam.
Naast de decision tree is er ook nog een grafische representatie van deze decision tree
die gebruikt kan worden. Als alleen gevallen in de dataset uit twee variabelen bestaan,
dan kunnen we de ene variabele tegen de x-as en de andere variabele tegen de y-as afzet-
ten en vervolgens met een + of - in de grafiek voor elk geval aanduiden of het wel of niet
tot de desbetreffende klasse variabele behoort.
2 Data en de distributie ervan
De data die gebruikt wordt voor data mining wordt vaak in een tabel gepresenteerd. Dit
wordt ook wel propositionele data of attribute value genoemd. Een rij in de tabel re-
presenteert instanties uit de data set. Instanties worden ook wel voorbeelden of gevallen
genoemd. De tabel in z’n geheel presenteert een monster of steekproef genomen uit een
grotere populatie. We noemen dit ook wel identically distributed (iid), wat wil zeggen dat
we ergens een distributie van data hebben en daar een monster uit nemen. Het nemen
van een monster doen we willekeurig zodat de geselecteerde instanties onafhankelijk van
elkaar zijn. Dit is echter slechts een aanname die in de praktijk vaak die waargemaakt
wordt. Elke kolom in de tabel representeert een attribuut, ookwel een feature of variabele
genoemd. Daarnaast is er meestal ook sprake van een target attribuut of een kleine groep
attributen die van extra interesse zijn.
Typen data
Er zijn verschillende typen attributen:
Pagina 2 van 44
, Samenvatting
Data mining
Nominaal(ookwel symbolisch of discreet genoemd)
Het enige wat je kunt doen met dit type attribuut is controleren op gelijkheid. We
kunnen geen afstanden tussen nominale attributen berekenen of andere rekenkun-
dige operaties erop uitvoeren.
Nummeriek
Bij dit type variabelen kunnen we vergelijken, oftewel de <, >, ≤, ≥ operaties. Daar-
naast kunnen we er ook rekenkundige operaties op uitvoeren en de afstand er tussen
bekijken.
Ordinaal
Bij dit type attribuut kunnen we wel vergelijken(<, >, ≤, ≥), maar geen rekenkun-
dige operaties of afstandsberekeningen uitvoeren.
Binair
Dit type attribuut is hetzelfde als nominaal, maar heeft slechts twee waarden na-
melijk True en False. Deze waarden spelen een speciale rol.
Data distributie
Er zijn twee soorten data distributie:
Univariate distributie
Bij univariate distributie kijken we slechts naar één attribuut en willen we weten welke
waarden voorkomen voor dat attribuut. Je bent in weze dus enkel aan het tellen. Deze
tellingen geven alle informatie over de data sample. Ook hier geldt dat omdat de data
slechts een sample is van de hele populatie, de tellingen schattingen of probabilities zijn.
De distributie vertelt ons dus wel wat, maar geeft nooit het volledige beeld omdat er
altijd sprake is van ruis in de data.
We gebruiken een entropie om aan te geven hoe informatief een attribuut is. Voor het
berekenen van de entropie van een attribuut gebruiken we een functie die een getal tussen
0 en 1 geeft. Hoe dichter bij 1 hoe informatiever het desbetreffende attribuut.
We bekijken nu de volgende typen univariate distributies:
Distributie van een binair attribuut
Binaire attributen hebben altijd precies twee waarden. Als we de probability P van
een van de attributen weten, dan weten we dus ook de probability van het andere
attribuut namelijk 1 - P. De entropie van een binair attribuut wordt dan gegeven
door de formule H(A) = −p lg(p) − (1 − p)lg(1 − p). De informativiteit van een
attribuut A is maximaal als p = 12 . Dit noemen een uniforme distributie: als alle
waarden van een attribuut even waarschijnlijk zijn.
Distributie van een nominaal attribuut
Een waarden voor een nominaal attribuut hebben dezelfde kenmerken als die van een
binair attribuut, maar een nominaal attribuut kan in tegen stelling tot een binair
attribuut meer dan twee waarden hebben. Stel dat een een nominaal attribuut
m mogelijke waarden heeft, dan zijn er dus ook n probabilities p1 , p2 , ..., pm . De
entropie
Pm van een nominaal attribuut wordt dan gegeven door de formule H(A) =
1
i=1 −p i lg(pi ). In dit geval is H(A) maximaal voor p = m . We kunnen H(A) dan
herschrijven tot Hmax = m × −( m1 ) lg( m1 ) = − lg( m1 ) = lg(m).
Pagina 3 van 44
, Samenvatting
Data mining
Distributie van een nummeriek attribuut
Nummerieke domeinen kunnen oneindig zijn, waardoor het een stuk lastiger wordt
om de waarden van een attribuut te tellen. Als we dat wel zouden doen dan zou
de probability van één specifieke waarde meestal 0 zijn. In plaats daarvan nemen
we bij zulke gevallen de probabilities van intervallen. Als interval gebruiken we
vaak het absolute minimum tot en met een bepaalde waarde x. Als je het interval
dan vergroot door de waarde van x te verschuiven, dan gaat de probability van dat
interval ook steeds een beetje omhoog. Dit resulteert in de cumulative distribution
function CDF FX (x) = P (X ≤ x). Als je de afgeleide van deze functie neemt dan
krijg je de probability density function PDF. Deze functie is een stuk interessanter,
omdat het laat zien in welk punt, oftewel voor welke waarde van de desbetreffende
variabele, CDF het snelste groeit. Dit duidt aan dat er op dat punt veel waarden
binnen dat interval vallen en geeft daarmee de relatieve densiteit aan voor elke
waarde.
We kunnen de densiteit van een distributie van nummerieke attributen inschatten
op twee manieren:
Histogrammen
We gebruiken een histogram om zo de densiteit van waarden op discrete wijze
in te schatten. Voor het maken van een histogram definieer je intervallen en tel
je alle waarden die binnen dat interval vallen. Het bepalen van de snijpunten
voor een interval kan op twee manieren:
∗ Equal width: splits het domein op in k intervallen van gelijke grote.
∗ Equal height: selecteer k snijpunten op dusdanige wijze dat alle interval-
len ongeveer nk waarden bevatten. De histogram die verkregen wordt bij
deze methode is minder interessant, omdat de hoogte overal gelijik is. De
informatie zit hem in waar de snijpunten komen te liggen. De afstand
tussen de snijpunten van een interval geven de densiteit van dat interval
aan.
Kernel density estimation
Deze methode geeft een exactere schatting van de densiteit doordat de data
ge-”smooth” wordt over een nummeriek domein door middel van een kernel
(meestal Gaussian). Deze methode geeft dus een vloeiende grafiek.
Voor het berekenen van de entropie van een nummeriek attribuut R gebruiken we in
plaats van probabilities p de densiteit functies PDF: h(X) = − X f (x) log f (x)dx
met f de PDF. Deze generalisatie is echter enigszins problematisch, bijvoorbeeld:
stel dat we de uniforme distributie [0, a] hebben, dan geldt H(X) = lg(a). Echter,
Pagina 4 van 44
, Samenvatting
Data mining
als a = 12 , dan H(X) = lg( 12 ) = −1. Een entropie kan echter niet negatief zijn. Het
concept entropie is dan ook niet zo goed van toepassing op nummerieke data.
Multivariate distributie
Bij multivariate distributies kijken we naar de relaties tussen attributen onderling. We
maken hiervoor gebruik van joint distributions. Zo’n joint distributie geeft aan hoe vaak
bepaalde combinaties van waarden voorkomen, oftewel we tellen dus combinaties. We
doen dit door middel van een confusion matrix (ookwel contingency table of cross table
genoemd). Als we twee verschillende attributen hebben, dan kunnen we links van de
tabel alle waarden van het ene attribuut plaatsen en bovenaan de tabel alle waarden van
het andere attribuut. Vervolgens kun je aan de hand van deze matrix zo alle combinaties
tellen. Hier is wederom sprake van volledige informatie, alle informatie die je uit de
data kan halen zit hierin. Daarnaast geldt dat wanneer je de joint distributie van twee
variabelen gevonden hebt, je ook direct de univariate distributie van beide variabelen
hebt. Uit deze joint distributies kunnen we verschillende informatie halen:
• Joint entropy: de entropie voor alle gevonden combinaties uit de matrix.
• Mutual information: hoeveel informatie kun je uit het ene attribuut krijgen, dat je
ook uit het andere attribuut kan krijgen.
• Information gain: hoeveel informatie geeft een variabele x over een variabele y.
Er zijn verschillende soorten joint distributies:
• X en Y zijn onafhankelijk van elkaar, oftewel de kans op X én de kans op Y, is de
kans op X keer de kans op Y.
0, 48 = 0, 6 × 0, 8 T F
0, 32 = 0, 4 × 0, 8 T 0,48 0,32 0,8
0, 12 = 0, 6 × 0, 2 F 0,12 0,08 0,2
0, 08 = 0, 4 × 0, 2 0,6 0,4 1,0
• Y is afhankelijk van X, oftewel als je X weet dan heb je een goeie kans op Y te
schatten.
T F
Als X true is, dan is de kans groot dat Y ook true is T 0,42 0,13 0,55
→ F 0,12 0,33 0,45
Als X false is, dan is de kans groot dat Y ook false is 0,54 0,46 1,0
→
• X bepaalt Y volledig, oftewel als je X weet dan weet je Y 100% zeker ook en an-
dersom.
T F
De hoge getallen bevinden zich op T 0,40 0 0,4
een van de twee mogelijke diagona- F 0 0,6 0,6
len. 0,4 0,6 1,0
Tot zover hebben we naar multivariate distributies voor binaire attributen gekeken.
In zulke gevallen is het gemakkelijk om een tabel te maken en de combinaties
Pagina 5 van 44
, Samenvatting
Data mining
van waarden te tellen. Ditzelfde geldt voor nominale attributen. Bij multivariate
distributies voor nummerieke variabelen is dit echter niet het geval:
– 2-dimensies:
In het geval van twee nummerieke variabelen kan er nog gebruik gemaakt
worden van scatterplots, 2D histogrammen en Gaussian KDE. Scatterplots
hebben echter wel als nadeel dat we het niet zien als punten in de grafiek
onder elkaar liggen. Iets wat op een enkele stip lijkt kan in werkelijkheid een
stapel van duizenden stipjes zijn, wat duidt op een hoge densiteit die we dan
dus wellicht over het hoofd zien. Dit gebeurd niet bij 2D histrogrammen en
Gaussian KDE, omdat zulke gebieden dan als rode vlekken aangegeven zullen
worden.
– Hogere dimensies:
Bij hogere dimensie distributies wordt het erg problematisch. Drie variabelen
kan nog, maar daarna worden distributies onbruikbaar. Dit betekent dat we
ons dus moeten focussen op nummerieke multivariate distributies bestaande
uit twee of drie nummerieke variabelen.
Ten slotte moet nog opgemerkt worden dat de joint distributie van een binair at-
tribuut en een nummeriek attribuut een zeer relevante distributie is binnen data
mining. Dit is namelijk meestal het geval bij classification.
3 Beslissingsbomen
In de vorige sectie zagen we dat we aan de hand van entropie aan konden geven hoe
informatief een bepaald attibuut is. Hetzelfde geldt, andersom, voor klasse attributen.
Een klasse attribuut bevat onzekerheid over de mogelijke waarden die het aan kan nemen.
Deze onzekerheid kan weergegeven worden door de entropie H(p) van het target attri-
buut. We kunnen de zekerheid van een klasse toe laten nemen door andere attributen te
overwegen. Dit doen we door te kijken of de ene waarde van een ander attribuut gerela-
teerd is aan de ene waarde van het klasse attribuut en een andere waarde van dit andere
attribuut gerelateerd is aan de andere waarde van het klasse attribuut. Bijvoorbeeld,
stel we hebben een data set met instanties waarin we de de variabelen ’weer’ en ’terras
pakken’ hebben. De variabele ’weer’ kan de waarden ’zon’ of ’regen’ aannemen en de
variabele ’terras pakken’ is of ’ja’ of ’nee’. De variabele ’terras pakken’ is dus het klasse
attribuut/target attribuut. We kunnen nu kijken of er een dusdanige relatie tussen ’weer’
en ’terras pakken’ is, waardoor we meer zekerheid over het klasse attribuut krijgen. Dit
is bijvoorbeeld hier het geval als een instantie met ’weer’ = ’zon’ altijd ’terras pakken’ =
’ja’ geeft en ’weer’ = ’regen’ altijd ’terras pakken’ = ’nee’ geeft. Dit splitsen op informa-
tieve attributen moeten vertakkingen met lagere entropieën produceren. De verandering
in entropie voor en na een splitsing noemen we de information gain. Dit splitsen op
attributen kunnen we grafisch weergeven in een beslissingsboom:
• Elke interne knoop geeft de test op een bepaald attribuut weer.
• Een vertakking in de boom representeert de uitkomst van zo’n test.
• Een blad representeert een klasse label of klasse label distributie.
• In elke knoop wordt één attribuut gekozen om de voorbeelden uit de data set zo
veel mogelijk op te delen in aparte klassen.
Pagina 6 van 44
, Samenvatting
Data mining
• Een nieuw geval wordt geclassificeerd door een pad dat match met dit geval te
volgen tot je uitkomt bij een blad. Het label in dat blad geeft dan de klasse van
dat geval aan.
Er zijn twee manieren voor het bouwen van een beslissingsboom:
Top-down constructie
Bij aanvang bevinden alle trainingsvoorbeelden zich in de wortel van de boom. Ver-
volgens worden de voorbeelden recursief gepartitioneerd door telkens één attribuut
per keer te kiezen.
Bottom-up boom prunning
Verwijder de subbomen en vertakkingen van onder naar boven om zo de geschatte
nauwkeurigheid van nieuwe gevallen te verbeteren.
Kiezen van het splitsende attribuut
Om te bepalen op welk attribuut het best gesplitst kan worden evalueren we in elke knoop
de beschikbare attributen door middel van het scheiden van de klassen in de trainings-
voorbeelden. We maken hiervoor gebruik van een goodness functie. Er zijn allerlei
verschillende goodness functies, zoals information gain(ID3 en C4.5), information
ratio en Gini index. Het beste attribuut is dat attribuut die de kleinste boom produ-
ceert. De heuristiek die we hiervoor gebruiken zegt dat we ’pure’ vertakkingen, bladeren
en knopen willen. Met puur bedoelen we een variabele wiens individuele waarden al-
lemaal positief of negatief classificeren. Als iets puur is heeft het dus geen entropie,
immers als een bepaalde waarde van een attribuut altijd dezelfde classificatie heeft dan
is de probability van die waarde dus p = 1 of p = 0 en dit geeft:
• H(1) = 0
• H(0) = 0
Een knoop waarin dit geldt noemen we een pure knoop en we zeggen dat deze distributie
’skewed’ is. Voor p = 0,5 geldt H(0,5) = 1, dan zeggen we dat we te maken hebben met
een gemixte knoop wiens distributie ’equal’ is.
Information gain
De information gain is de hoeveelheid informatie voor het splitsen minus de hoeveelheid
informatie na het splitsen op een bepaald attribuut. De formule hiervoor is als volgt:
Gain(A) = H(p) − i H(pi ) × nni met:
P
• p de probability van een positieve uitkomst in de huidige set.
Pagina 7 van 44
, Samenvatting
Data mining
• n het aantal voorbeelden in de huidige set.
• pi de probability van een positieve uitkomst in branch i.
• ni het aantal voorbeelden in branch i.
We zien dus dat de information gain afhankelijk is van de entropieën van voor en na
het splitsen. Als de information gain toeneemt, dan neemt de puurheid eveneens toe.
Dit is logisch aangezien we net zagen dat wanneer iets puur is het bijna geen entropie
heeft. Als we dus een attribuut met een hogere puurheid en dus lage entropie vinden, dan
zal de information gain ook hoog zijn aangezien Gain(A) = H(p) − lage entropie(A) >
H(p) − hoge entropie(A). Aangezien we een zo puur mogelijke vertakking willen, kiezen
we het attribuut met de hoogste information gain.
Een voorbeeld
De entropieën voor alle waarden van het attribuut ’Outlook’ zijn dan:
Outlook = ’Sunny’:
H([2, 3]) = H(0.4) = −0.4 lg(0.4) − 0.6 lg(0.6) =
0.971 bit
Outlook = ’Overcast’:
H([4, 0]) = H(1) = −1 lg(1) − 0 lg(0) = 0 bit
Outlook = ’Rainy’:
H([3, 2]) = H(0.6) = −0.6 lg(0.6) − 0.4 lg(0.4) =
0.971 bit
Gemiddelde entropie voor Outlook:
5 4 5
( 14 ) × 0.971 + ( 14 ) × 0 + ( 14 ) × 0.971 = 0.693
De information gain voor outlook is dan:
Gain(outlook) = H([9, 5]) − 0.693 = 0.94 − 0.693 = 0.247 bit.
Op dezelfde wijze berekenen we de information gains voor de andere drie attributen:
• gain(T emperature) = 0.029 bit
• gain(Humidity) = 0.152 bit
• gain(W indy) = 0.048 bit
Outlook heeft dus de hoogste information gain en dus gaat we als eerst op dat attribuut
opsplitsen.
Er moet wel nog opgemerkt worden dat niet alle bladeren puur hoeven te zijn, soms
hebben identieke voorbeelden toch andere klassen. het splitsen stopt wanneer de data
niet verder opgesplits kan worden.
Zeer vertakkende attributen
Pagina 8 van 44
