Oplossingen Datamining
2II15
Juni 2008
1. (Associatieregels) (a) Zijn de volgende beweringen juist of fout? Geef een korte verklaring voor alle juiste beweringen en een tegenvoorbeeld voor alle foute be-weringen: i. In elke database is de confidence van de associatieregel {a, b} → {c} groter dan de confidence van {a} → {c}. ii. Elke maximale frequente itemset is een closed itemset. (b) Geef alle associatieregels met een support van minimaal 40% en een confidence van minimaal 70% in de volgende transactiedatabase. TID Items 1 a, b, c 2 b, c, d, e 3 c, d 4 a, b, d 5 a, b, c Geef aan welk algoritme je hiervoor gebruikt en beschrijf de verschillende tussenstappen in jouw berekeningen. Oplossing: (a)
i. Deze uitspraak is onwaar. Neem de database uit (b); conf (bc → d) =
1 1 < conf (b → d) = 3 2
ii. Deze uitspraak is waar. Als I een maximaal frequente itemset is, dan wil dit zeggen dat I frequent is en dat een enkele van zijn echte supersets frequent is. Dus is het onmogelijk dat een van zijn echte supersets dezelfde frequentie als I heeft, en dus is I closed. (b) We zoeken eerst alle frequente itemsets met een minimale support van 40%. Hiervoor maken we gebruik van het Apriori-algoritme. We tellen eerst de frequentie van de singleton sets C1 = {a, b, c, d, e}. Dit levert volgende absolute frequenties op: a b c d e 3 4 4 3 1 Alle singleton sets behalve e zijn frequent. We hebben dus F1 = {a, b, c, d}. Dit levert volgende kandidaten van lengte 2 op: C2 = {ab, ac, ad, bc, bd, cd}. We tellen de absolute frequenties van de paren: ab ac ad bc bd cd 3 2 1 3 2 2 1
De frequente sets van lengte 2 zijn dus: F2 = {ab, ac, bc, bd, cd}. Voor lengte 3 hebben we slechts 2 kandidaten: C3 = {abc, bcd}. Alle andere sets van lengte 3 hebben minstens 1 infrequente subset; abd bijvoorbeeld heeft ad als infrequente subset. De absolute frequenties: abc bcd 2 1 De frequente sets van lengte 3 zijn dus: F3 = {abc}. Er kunnen geen kandidaten van lengte 4 gegenereerd worden. De verzameling frequente itemsets is dus: F = {a, b, c, d, ab, ac, bc, bd, cd, abc} De associatieregels kunnen nu gevormd worden door de frequente itemsets op te splitsen in linker- en rechterkant van een associatieregel. We testen volgende combinaties: a → b 3/3 b → a 3/4 a → c 2/3 c → a 2/4 b → c 3/4 c → b 3/4 b → d 2/4 d → b 2/3 c → d 2/4 d → c 2/3 ab → c 2/3 ac → b 2/2 bc → a 2/3 Merk op dat we a → bc, b → ac en c → ab niet hoeven te testen aangezien ab → c en bc → a onvoldoende confidence hebben. De regels met voldoende support en confidence zijn dus: a → b,
b → a,
b → c,
2
c → b,
ac → b
2. (Hubs en Authorities) Rangschik de nodes volgens hun hub-score. Doe dit ook voor autoriteit. Beschrijf hoe je deze rangschikking bepaalt. 1 2
3 4 5 6
Oplossing: De hub- en autoriteit-scores bepalen we met behulp van het HITS algoritme. Laat voor i = 1 . . . 6, ai de autoriteit-score van node i zijn, en hi de hub-score van deze node. a en h zijn de kolomvectoren met ai (resp. hi ), i = 1 . . . 6 als componenten. Met behulp van de volgende matrix A drukken we het verband tussen hub- en autoriteit-scores van de nodes uit: 0 0 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 A = 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 We beginnen met a = [ 1 1 1 1 1 1 ]T en h = [ 1 1 1 1 1 1 ]T . De hub- en autoriteit-rangschikking kunnen we bereken door iteratief de scores als volgt te updaten tot we de trend zien: h := Aa a := AT h In elke stap normaliseren we de scores zodat zowel de hub-waarden als de autoriteitwaarden maximaal 1 zijn. Een andere, eveneens correcte mogelijkheid is het gebruik van volgende formules: h := (AAT )h a := (AT A)a eveneens met normalisatie in elke stap. Voordeel van deze formule is dat ze sneller convergeert, nadeel is dat je twee matrix vermenigvuldigingen moet uitvoeren voor de berekening van AAT en AT A. Daarom hebben we hier in deze oplossing voor de eerste optie gekozen.
3
Dit geeft de opeenvolgende hub- en autoriteit-scores: a1 a2 a3 a4 a5 a6 h1 h2 h3 h4 h5 h6
1 1 1 1 1 1 1 1 1 1 1 1
1/3 0 0 2/3 1 2/3 1/2 1 1/4 1/4 0 0
4/7 0 0 6/7 1 5/7 5/8 1 1/4 3/8 0 0
1/2 0 0 13/16 1 5/8 13/22 1 5/22 7/22 0 0
... ... ... ... ... ... ... ... ... ... ... ...
We zien nu een duidelijke trend; qua autoriteit-scores krijgen we de volgorde: a5 > a4 > a6 > a1 > a2 = a3 = 0 en voor de hub-scores: h2 > h1 > h4 > h3 > h5 = h6 = 0 Voor de ge¨ınteresseerden: de hub- en autoriteit-scores convergeren naar:
h =
0.61803398875 1.0 0.209056926535 0.338261212718 0.0 0.0
a =
4
0.511170297433 0.0 0.0 0.827090915285 1.0 0.61803398875
3. Classificatie Beschouw de volgende dataset. outlook overcast overcast overcast overcast rainy sunny sunny rainy rainy sunny sunny rainy sunny rainy
temperature 83 64 72 81 65 69 75 68 75 85 80 71 72 70
humidity 86 65 90 75 70 70 70 80 80 85 90 91 95 96
windy FALSE TRUE TRUE FALSE TRUE FALSE TRUE FALSE FALSE FALSE TRUE TRUE FALSE FALSE
play yes yes yes yes no yes yes yes yes no no no no yes
(a) Kan outlook als een ordinaal attribuut beschouwd worden? Leg kort uit. (b) Veronderstel dat je Gini als maat gebruikt om de beste split te kiezen bij de constructie van een beslissingsboom voor het attribuut play. Welke van de volgende splits is dan de beste? Toon de berekening. i. 3-way split outlook=overcast/outlook=sunny/outlook=rainy ii. binaire split temperature≤75 /temperature>75 (c) Kan de evaluatiemethode 10-fold cross-validation gebruikt worden om de kwaliteit van een beslissingsboom te meten? Leg uit.
Oplossing: (a) Dit hangt ervan af of je de waarden die outlook kan aannemen op een logische manier kan ordenen. Als je aanneemt dat dat kan, zoals met de drie waarden die in het voorbeeld voorkomen het geval is, dan kan het, bijvoorbeeld door te stellen dat: rainy < overcast < sunny Indien je aanneemt dat er nog andere weer-types die niet te vergelijken zijn, bijvoorbeeld snowy, hail (is snowy beter dan hail ?), dan kan je het niet als een nominaal attribuut beschouwen. Beide antwoorden werden goed gerekend zolang ze maar voldoende gemotiveerd waren. (b) Voor de berekening van de kwaliteit van de splits moeten we de dataset onderverdelen volgens de split en de Gini index berekenen in elk van deze delen afzonderlijk met betrekking tot het doel-attribuut play. De score voor de split is dan het gewogen gemiddelde van de GINI-index in de afzonderlijke takken van de split. Dit levert de volgende waarden op:
5
1. 3-way split outlook=overcast/outlook=sunny/outlook=rainy: outlook
overcast yes 4 no 0 Gini o = 0
sunny yes 2 no 3 Gini s = 1 − 12 = 25
rainy yes 3 no 2
2 2 5
+
2 3 5
Gini SPLIT = 0 +
Gini r = 1 − = 12 25
5 12 14 25
+
5 12 14 25
=
2 3 5
+
2 2 5
12 35
2. binaire split temperature≤75 /temperature>75 temperature
≤ 75 yes 7 no 3 Gini ≥ = 1 − = 21 50
7 10
≤ 75 yes 2 no 2 2
+
3 10
2
Gini SPLIT =
Gini > = 1 − = 12 10 21 14 50
+
4 1 14 2
=
2 2 4
+
2 2 4
31 70
Aangezien de Gini-score van de split (a) kleiner is dan de Gini-score van split (b), levert split (a) de grootste winst (gain). Daarom kiezen we dus (a). (c) 10-fold cross-validation is een evaluatie-methode voor algoritmes, niet voor bomen of andere modellen. 10-fold cross-validation splitst de data op in 10 delen, en voor elk deel wordt nagegaan wat de performantie is van het model dat het algoritme leert op de andere 9 delen. Door de performantie-score uit te middelen over de 10 tests krijg je een goed beeld van de kwaliteit van de modellen die het algoritme aflevert. Om de kwaliteit van 1 model te evalueren echter is 10-fold cross-validation niet geschikt. (Behalve dan misschien door de kwaliteit van de te evalueren boom te vergelijken met de kwaliteit van de 10 modellen gegenereerd door de cross-validation.)
6
4. (Toepassing) Veronderstel dat je beschikt over een database die informatie over wetenschappelijke publicaties bevat. Voor elke publicatie bevat deze database de titel, de naam van het tijdschrift, het volumenummer, de auteurs, een korte abstract, een kort lijstje keywords en de lijst met referenties. De tijdschriften zijn ingedeeld in categorie¨en. Je kan er van uitgaan dat de gegevens in de database correct en ruisvrij zijn. Geef aan welke technieken uit de cursus je op deze database kan toepassen om volgende problemen op te lossen. Beschrijf duidelijk welke data je gebruikt en op welke manier. (a) Automatisch beslissen, gebaseerd op de titel, de lijst van auteurs, de lijst van keywords en de abstract van een paper, in welke van de tien categorie¨en tijdschriften dit paper het best past. (b) Welke groepjes auteurs hebben veel gemeenschappelijke publicaties? (c) Vind goede overzichtspapers (surveys) in een bepaald domein. Dit domein wordt omschreven door een aantal keywords ingegeven door de gebruiker.
Oplossing: (a) Dit is duidelijk een classificatie-probleem. Als features nemen we de woorden uit de abstracts en titel, de namen van alle auteurs en de lijst van keywords. Dit worden binaire attributen in onze dataset; als een woord w voorkomt in de titel van een paper, is het overeenkomstige attribuut 1, anders is het 0. Op deze dataset kunnen we vervolgens een classifier trainen. Merk op dat er een extra complicatie is omdat er meer dan twee klassen zijn. Een andere optie: defini¨eer een afstandsmaat tussen papers gebaseerd op het aantal gemeenschappelijke woorden in de abstract, het aantal auteurs, etc. en pas dan het nearest neighbor algoritme toe om nieuwe papers te classificeren. (b) Hiervoor is frequent itemset mining geschikt. De transactie-database bestaat uit 1 transactie per paper, namelijk de verzameling auteurs van dat paper. De frequente itemsets zijn dan setjes van auteurs die vaak samen publiceren. Een minder geschikte methode is clustering van de auteurs. Omdat het aantal samenwerkende auteurs typisch veel kleiner is dan het totale aantal auteurs en omdat een auteur tijdens zijn of haar loopbaan vaak met verschillende groepen samenwerkt, krijgen we hier typisch erg veel kleine clustertjes die daarbij nog vaak overlappen. (c) HITS kan hier worden toegepast. De overzichtspapers zijn de hubs van de citatiegraaf. Een extra complicatie hier is de beperking van het domein door middel van opgegeven keywords. Hier kan op twee manieren mee omgegaan worden: ofwel zoeken we eerst de hubs en gebruiken we daarna de keywords om ons te beperken tot het opgegeven domein, of we gebruiken de keywords om eerst relevante papers te identificeren als core, breiden die core uit met alles op afstand 1 en passen HITS toe. Om papers te vinden die overeenstemmen qua keywords kunnen we een afstandsmaat tussen sets van keywords gebruiken, bijvoorbeeld de cosine-measure na omzetting tot binaire vectoren.
7
