Technische Universiteit Delft Elektrotechniek, Wiskunde en Informatica Secties: Pattern Recognition & Bioinformatics & Multimedia Signal Processing
DATA MINING (TI2730-C) Schriftelijk -
(her)tentomen.
Dinsdag
10 april, 2012, 14:00
-17:00
Geef de a n t w o o r d e n v o o r iedere vraag o p een afzonderliil< blad, w a n t de o p g a v e n w o r d e n v o o r het nakijken gesplitst!
-
V e r g e e t n i e t j e n a a m en s t u d i e n u m m e r t e z e t t e n o p ieder b l a d !
-
Geef, indien mogelijk, niet alleen de u i t k o m s t e n , maar o o k de tussenliggende berekeningen. B e a n t w o o r d i n g van de vragen m a g in het Nederlands of Engels, m a a r h o u h e t w e l k o r t en b o n d i g .
-
Het t o t a a l aantal p u n t e n dat je v o o r de o p g a v e n k u n t behalen is 4 6 p u n t e n
Opgave 1 (14pt) Een dataset bestaat uit 30 o b j e c t e n van t w e e verschillende klassen die elk t w e e k e n m e r k e n ( f l , f 2 ) h e b b e n . Een scatter p l o t van de data ziet er als volgt uit:
a, I p t )
Leg uit w a a r o m het niet zinvol is o m k-means t o e t e passen o p deze data.
b, I p t )
Leg u i t w a a r o m deze data b e t e r geclassificeerd kan w o r d e n m e t de k-
c, I p t )
T e k e n de beslisgrens w a n n e e r de 1-NN regel aan de h a n d van deze
NN classifier dan m e t de Nearest M e a n classifier. d a t a g e l e e r d w o r d t , (maak g e b r u i k van a n t w o o r d v e l 1 , I c ) d, 2pt)
W e l k e o b j e c t e n w o r d e n b e h o u d e n als ' c o n d e n s i n g ' w o r d t t o e g e p a s t ? ( m o t i v e e r het a n t w o o r d )
e, I p t )
W a a r o m zou m e n ' e d i t i n g ' w i l l e n t o e p a s s e n ?
f, 2 p t )
Welke
objecten worden
verwijderd
( m o t i v e e r het a n t w o o r d )
1
als e d i t i n g w o r d t
toegepast?
g, I p t )
W a t zijn de a-priori l
h, 3 p t )
Teken de beslisgrens als de Naive Bayes Classifier aan de hand van deze data geleerd w o r d t , (maak g e b r u i k van a n t w o o r d v e l 2, m o t i v e e r het antwoord)
i, I p t )
Geef aan w a a r o m de c o m p l e x i t e i t van een classificator
verkleind
w o r d t als w e k e n m e r k e n f i l t e r e n of e x t r a h e r e n , j, Ipt)
B e r e d e n e e r o f de t - t e s t v o o r deze dataset een goed c r i t e r i u m is o m te g e b r u i k e n t i j d e n s een f e a t u r e - f i l t e r i n g p r o c e d u r e .
OPGAVE 4 (IZpt) In deze crisistijd zijn b a n k e n voorzichig m e t het v e r s t r e k k e n van l e n i n g e n . Banken p r o b e r e n via risico-analyse in t e schatten of een p o t e n t i ë l e g e l d l e n e r w e l o o i t zijn lening zal t e r u g b e t a l e n . V o o r dit doel g e b r u i k t de bank een database van e e r d e r e k l a n t e n , w a a r b i j gekeken w o r d t naar het h e b b e n van een eigen huis, het i n k o m e n , de huwelijkse staat en of m e n in het v e r l e d e n aan zijn v e r p l i c h t i n g e n h e e f t voldaan (hierna aangeduid als ' b e t r o u w b a a r ' ) . Zie t a b e l 1 . Klant
Eigen huis
Huwelijkse staat
Inkomen
Classicatie: Betrouwbaar
1
Ja
Alleenstaand
125k
Nee
2
Nee
Gehuwd
lOOk
Nee
3
Nee
Alleenstaand
70k
Nee
4
Ja
Gehuwd
120k
Nee
5
Nee
Gescheiden
95k
Ja
6
Nee
Gehuwd
60k
Nee
7
Ja
Gescheiden
220k
Nee
8
Nee
Alleenstaand
85k
Ja
9
Nee
Gehuwd
75k
Nee
10
Nee
Alleenstaand'
90k
Ja
Tabel 1 O m een 'decision t r e e ' t e g e n e r e r e n die v o o r s p e l t of een t o e k o m s t i g e lener aan zijn v e r p l i c h t i n g kan v o l d o e n ( ' b e t r o u w b a a r '
is), kiest de bank v o o r een e e n v o u d i g e
m e t h o d e o m een decision t r e e t e g e n e r e n . Bij elke stap w o r d t die binaire splitsing gekozen die t e n m i n s t e leidt t o t 1 subset m e t records die b e h o r e n t o t
dezelfde
klasse. De eerste splitsing w o r d t g e m a a k t o p basis van eigen huis, de t w e e d e o p basis van h u w e l i j k s e staat en bij de d e r d e stap w o r d t gekeken naar het i n k o m e n . a, 3 p t )
Teken de b o o m v o o r t a b e l 1 en b e a n t w o o r d de v o l g e n d e v r a g e n . Bij de t w e e d e stap zijn er t w e e kandidaat-splitsingen. Geef aan w e l k e je gekozen h e b t en w a a r o m ? Geef o o k aan bij de d e r d e stap w e l k e grens j e h e b t gekozen m e t b e t r e k k i n g t o t i n k o m e n en w a a r o m ?
Om
de
decision
tree
steeds
beter
te
maken
voegt
de
bank
steeds
nieuwe
klantgegevens aan de database t o e . In d i t geval w o r d e n er t w e e records t o e g e v o e g d
2
(zie t a b e l 2). O n g e l u k k i g e r w i j s o n t b r e e k t het i n k o m e n van klant 1 1 . Er zijn drie m o g e l i j k h e d e n : v o e g r e c o r d 1 1 niet aan de database t o e , 2) v o e g r e c o r d 1 1 t o e aan de database en g e n e r e e r de decision t r e e alleen o p basis van eigen huis en huwelijkse staat, en 3) b e r e k e n een geschikte w a a r d e v o o r h e t i n k o m e n . Klant
Eigen huis
Huwelijkse staat
lnl
Classificatie: Betrouwbaar
11
Nee
Gehuwd
?
Ja
12
Ja
Gehuwd
135k
Ja
Tabel 2 b, 2 p t )
A a n w e l k e van de drie m o g e l i j k h e d e n geef j e d e v o o r k e u r . Licht je antwoord toe.
c, 2 p t )
Geef d e o n t b r e k e n d e w a a r d e in geval van m e a n i m p u t a t i o n and h o t deck i m p u t a t i o n .
V o e g record 1 1 ( m e t de r e s u l t a t e n van de h o t deck i m p u t a t i o n ) en record 12 t o e aan de originele database van t a b e l 1 . V o o r het m a k e n van een n i e u w e decision t r e e o p basis van de 12 records g e b r u i k e n w e nu een binaire splitsing o p basis van de Giniindex. W e s t a r t e n m e t een splitsing o p basis van h u w e l i j k s e staat. d, 2 p t )
V o o r de eerste splitsing zijn er 3 k a n d i d a t e n . Geef deze en bereken v o o r elk de Gini-index. Aan w e l k e geef j e de v o o r k e u r ? Licht je antwoord toe.
e, 2 p t )
Als
in
plaats
van
de
Gini-index
de
"misclassification
error"
als
c r i t e r i u m was g e b r u i k t , aan w e l k e splitsing zou j e dan de v o o r k e u r geven? Geef de 'misclassification e r r o r s ' . f, I p t )
Aan w e l k e m e t h o d e geef j e u i t e i n d e l i j k de v o o r k e u r : Gini-index of classificatiefout, of m a a k t het niet uit? Licht j e a n t w o o r d t o e .
O P G A V E 3 (lOpt) /C-anonymity is d e f i n e d as r e d u c i n g t h e g r a n u l a r i t y in such a w a y t h a t a given record c a n n o t be distinguished f r o m at least k-1 o t h e r records. Based o n this d e f i n i t i o n and t h e f o l l o w i n g database t a b l e e n t r i e s , answer t h e f o l l o w i n g q u e s t i o n s . Index
BSN
Name
Gender
Birth date
Transaction
26838
78979879
A
Female
12-11-1987
45
6-4-2012
89890
89779003
B
IVlale
3-4-1986
51
4-4-2012
67989
12123987
C
Female
5-6-1985
51
5-4-2012
98273
57893980
D
Female
11-2-1992
45
4-4-2012
67820
56787922
E
IVlale
12-11-1986
45
6-4-2012
68902
90890892
F
Male
7-3-1985
85
5-4-2012
12489
67899909
G
Male
4-5-1991
85
5-4-2012
Transaction Date
amount (Euros)
a, I p t )
W h a t is t h e value f o r k f o r t h e " b i r t h d a t e " a t t r i b u t e ?
3
b, 2pt)
A n o n y m i z e t h e " t r a n s a c t i o n a m o u n t " a t t r i b u t e such t h a t a record c a n n o t be distinguished f r o m at least 2 o t h e r record (k=3 a n o n y m i t y ) .
c, 2 p t )
Explain a w a y t o fully hide t h e i d e n t i t y o f t h e p e o p l e in t h e t a b l e and e l a b o r a t e if it is practical in real life t o d o so.
Assume t h a t in a n o t h e r t a b l e , w e have t h e f o l l o w i n g entries: Index
Name
Items
Transaction Date
897970
X
Egg chocolates, meat balls, potato
5-4-2012
126789
Y
Hair gel, red bull, gum, deodorant
6-4-2012
d, 3pt)
Try t o i d e n t i f y t h e names X and Y w i t h respect t o n a m e and g e n d e r by using t h e i n f o r m a t i o n in t h e t w o t a b l e s .
e, I p t )
Elaborate o n t h e life styles of t h e s e t w o p e o p l e , f o r e x a m p l e m a r i t a l status, o c c u p a t i o n and so o n .
f, I p t )
W h a t is needed t o d e d u c e m o r e accurate i n f o r m a t i o n o n these t w o people?
OPGAVE 4 (lOpt) Een bank h e e f t de v o l g e n d e g e a n o n i m i s e e r d e gegevens van h u n c l i ë n t e n :
Persoonsnr. Geslacht
Rente perc. huidige lening
Woonomgeving Inkomen
1
7.5
stad
laag
goed slecht
man
Kredietwaardigheid
vrouw
7.5
stad
hoog
3
man
7.5
stad
hoog
slecht
4
vrouw
7.5
stad
hoog
goed
5
vrouw
5
dorp
hoog
goed
6
man
7.5
dorp
laag
goed
7
man
7.5
stad
laag
slecht
8
vrouw
5
stad
hoog
goed
9
vrouw
7.5
stad
hoog
slecht
10
vrouw
5
stad
hoog
goed
2
De bank is geïnteresseerd o m de b e d r i j f s v o e r i n g t e v e r b e t e r e n d o o r
datamining
t e c h n i e k e n t o e te passen o p deze gegevens. De bank is v o o r n a m e l i j k geïnteresseerd in de t o e p a s s i n g van de t e c h n i e k association (a; I p t )
rules.
Geef t w e e v o o r b e e l d e n van hoe de bank m e t b e h u l p van de r e s u l t a t e n van een analyse van deze gegevens m e t association rules de b e d r i j f s v o e r i n g kan v e r a n d e r e n .
4
De b a n k w i l op basis van de eerste 5 gegevens (geslacht; r e n t e p e r c e n t a g e huidige l e n i n g ; w o o n o m g e v i n g ; i n k o m e n ; en k r e d i e t w a a r d i g h e i d ) analyses v e r r i c h t e n . Hierbij h a n t e e r t zij een m i n i m a l e s u p p o r t van 5 en een m i n i m a l e c o n f i d e n c e van 9 0 % . (b; 2pt) (c; 2 p t )
Geef alle f r e q u e n t i t e m s e t s . (Laat zien hoe u hieraan g e k o m e n b e n t ) Geef alle regels die g e v o n d e n w o r d e n . (Laat zien hoe u hieraan gekomen bent)
(d; I p t ) (e; I p t )
W a t is de o priori
eigenschap?
Bespreek hoe t i j d e n s h e t g e n e r e r e n van de regels [rule g e b r u i k g e m a a k t kan w o r d e n van de a priori
(f; I p t )
discovery)
eigenschap.
De bank w i l nu o o k het gegeven " a a n t a l k i n d e r e n " m e e n e m e n in de analyse. Geef aan hoe de bank d i e n t o m t e gaan m e t d i t gegeven o m de association
rule analyse h i e r o p t e k u n n e n t o e p a s s e n .
(g; I p t )
Bereken van een van de g e v o n d e n regels de lift.
(h; I p t )
Schets van deze regel o o k de double
decker plot en geef aan w a t de
doe w a a r d e is. (Geef duidelijk de getallen aan in de d o u b l e decker plot)
5