Knowledge Discovery in de Flickr Database een kijkje in de black interestingness box
30 juni 2006
T.A.W. Molendijk 0045144 Universiteit van Amsterdam
Abstract We doen een allereerste poging op basis van data van online fotodienst Flickr kennis te vinden over de werking van hun algoritme ter bepaling van interestingness van een foto. Op grond van inzichten in de werking van Flickr en vermoedens van factoren die voor interestingness relevant zijn maken we een selectie uit de schier oneindige data van Flickr, representeren we de geselecteerde data in een relationele setting, maken we een keuze voor de structuur van de instanties, trachten we er met behulp van enkele beschikbare methoden een model uit te extraheren en pogen we dit model ten slotte te interpreteren en er kennis over de werking van het algoritme uit te concluderen. Gezien het verkennende karakter van dit onderzoek zijn deze conclusies in onze ogen opvallend overtuigend. Zeer uitgebreide mogelijkheden voor verdiepend en verbredend vervolgonderzoek maken de vooruitzichten voor onze onderzoeksvraag uitsluitend rooskleuriger.
2
Inhoudsopgave 1. Inleiding
4
2. Theoretische context 2.1. Relationele data 2.2. Leermethoden voor relationele data
5 5 6
3. Flickr
6
4. Selectie en preprocessing van de data
7
5. Transformatie van de data ter voorbereiding op data mining
9
6. Data mining 6.1. Experiment 1 6.2. Experiment 2 6.3. Experiment 3
10 11 11 12
7. Interpretatie van het model
13
8. Conclusie
14
9. Toekomstig onderzoek 9.1. Uitbreiding van de dataset 9.2. Rijkere subgraphs 9.3. Probabilistic relational models 9.4. Patroonherkenning of natural language processing
14 15 15 16 16
3
1
Inleiding
Dit onderzoek is voortgekomen uit de geheimzinnigheid die door online fotodienst Flickr1 is gecreëerd rondom de werking van hun algoritme dat bepaalt of een foto interessant is of niet. Om toch iets over de interne werking van dit algoritme te weten te komen hebben we gepoogd deze tot op zekere hoogte te ‘reverse engineeren’ op basis van data die door de dienst over hun content wordt vrijgegeven. Kunnen we factoren vinden waarvan het aannemelijk is dat deze een positieve dan wel negatieve invloed hebben op de waarschijnlijkheid dat een foto door Flickr als interessant wordt aangemerkt? In deze zoektocht experimenteren we met enkele methoden om probabilistische modellen te leren op grond van Flickr data. Het relationele karakter van deze data beïnvloedt onze keuze voor methoden en dwingt ons aandacht te schenken aan specifieke eigenschappen van relationele data en de potentiële problemen die deze tot gevolg kunnen hebben. In de uitgebreide literatuur worden uiteenlopende termen gehanteerd wanneer men het heeft over het destilleren van bruikbare patronen uit data: data mining, knowledge extraction en information discovery zijn slechts enkele hiervan. Om de discussie in dit verslag zo zuiver mogelijk te houden zullen wij vasthouden aan het model en de terminologie van Fayyad et al. uit 1996 [2]. Hierin wordt in onze ogen terecht een onderscheid gemaakt tussen twee niveaus van generaliteit. Enerzijds beschouwen we het algehele proces van het extraheren van abstracte kennis uit ruwe data, met de nadruk op het feit dat kennis het eindproduct is van data-driven onderzoek. Dit proces noemen we knowledge discovery in databases (KDD) en bestaat uit verschillende stappen (zie figuur 1). Eén van deze stappen behelst het extraheren van patronen uit data met behulp van bepaalde algoritmes. Deze stap noemen we data mining en vindt plaats op basis van data die het resultaat is van meerdere voorbereidende bewerkingen van de ruwe data. Op basis van de gevonden patronen kan op zijn beurt de laatste stap richting feitelijke kennis gezet worden. In dit verslag bespreken we het volledige KDD proces van ruwe data tot bruikbare kennis. We zullen dan ook alle stappen van dit proces bespreken in de context van ons onderzoek. Voordat we hiertoe overgaan zullen we in paragraaf 2 eerst wat relevante achterliggende theorie uiteenzetten, waarna in paragraaf 3 wat dieper in wordt gegaan op het domein van ons onderzoek – Flickr. In paragraaf 4 bespreken we de eerste twee stappen; selectie en preprocessing van data. De voorbereidingen van data mining die hier op volgen komen in paragraaf 5 aan bod, waarna paragraaf 6 gewijd is aan de feitelijke data mining. Het model dat we in deze paragraaf abstraheren pogen we in paragraaf 7 te interpreteren dusdanig dat er enkele conclusies uit getrokken kunnen worden. Paragraaf 8 ten slotte behandelt de conclusies die we uit ons werk trekken en paragraaf 9 licht een tipje van de sluier op wat betreft de in onze ogen zeer uitgebreide mogelijkheden voor vervolgonderzoek.
1
http://www.flickr.com/
4
Figuur 1 KDD proces dat we volgen om van Flickr database naar bruikbare kennis te geraken. Plaatje van [2].
2
Theoretische context
Voordat we het KDD proces in de context van ons onderzoek bespreken is het nuttig om wat relevante theoretische achtergrond te schetsen. Allereerst kijken we naar relationele data en waarin deze verschilt met propositionele data. Daarna bespreken we de methoden die we zullen gebruiken om op basis van de relationele data probabilistische modellen te leren.
2.1
Relationele data
Een intuïtieve manier om een beeld te geven van relationele data is door een onderscheid te maken tussen objecten en links. Een relationele dataset bestaat uit objecten van één of uiteenlopend type. Een object kan attributen hebben, gelijk aan attributen in propositionele data. Tussen objecten onderling kunnen relaties bestaan, die tot uitdrukking komen in links tussen deze objecten. Ook links kunnen er zijn in verschillende typen en kunnen attributen met zich meedragen. Figuur 2b visualiseert dit idee in contrast met propositionele data (2a). In het licht van onze plannen om modellen te leren zijn hier twee fundamentele verschillen tussen relationele en propositionele datasets van belang. Ten eerste is relationele data in tegenstelling tot propositionele data heterogeen van aard. Propositionele instanties delen dezelfde structuur – ieder bevat exact dezelfde verzameling attributen. Het is homogene data. De structuur van relationele instanties daarentegen kan sterk variëren binnen een dataset. Iedere instantie deelt de aanwezigheid van een kernobject van hetzelfde type, maar de relaties die er bestaan tussen dit kernobject en andere objecten kunnen per instantie anders zijn. Het tweede belangrijke verschil tussen beide typen data manifesteert zich in de onafhankelijkheid van een instantie. Tussen relationele instanties kunnen in tegenstelling tot tussen propositionele instanties relaties bestaan. Immers objecten in de ene instantie kunnen direct of indirect gelinkt zijn met objecten uit de andere instantie. Zowel de heterogeniteit als de interne afhankelijkheid van relationele data vormen een probleem voor traditionele leermethoden. In de volgende paragraaf kijken we naar enkele methoden die oplossingen voor deze problemen aandragen.
5
Figuur 2 (a) Propositionele data, (b) relationele data en (c) gepropositionaliseerde relationele data met multisets. Plaatje van [5].
2.2
Leermethoden voor relationele data
De twee methoden die wij in ons onderzoek bekijken zijn beide gebaseerd op een traditionele leermethode en breiden deze vervolgens zodanig uit dat ze ook geschikt zijn voor leren op relationele data. Deze uitbreiding behelst onder andere het ‘platslaan’ van attributen uit een relationele structuur naar een propositionele structuur. Bij deze propositionalisatie zien we ons, als gevolg van het feit dat meerdere gerelateerde objecten ieder een eigen waarde voor een attribuut inbrengen, geconfronteerd met multisets. Dit is geïllustreerd in figuur 2c. Met dergelijke multisets wordt door verschillende algoritmes op verschillende manieren omgegaan. Een tweede keuze die door een algoritme gemaakt moet worden is of het aantal relaties tussen het kernobject en gerelateerde objecten van een bepaald type – de degree – als extra attribuut wordt gerepresenteerd. Wanneer dit niet gebeurt verliezen we de expliciete informatie over de hoeveelheid gerelateerde objecten in de instantie. Als eerste van de twee bekijken we de relational Bayesian classifier (RBC) [5], gebaseerd op de naive bayesian classifier. Deze methode slaat multisets niet plat maar trekt ze juist uiteen in meerdere instanties: voor iedere waarde uit de multiset wordt een aparte instantie gecreëerd. Hiermee wordt impliciet enige informatie over de link degree behouden, maar expliciet slaat de RBC geen degree op. Het aantrekkelijke van de RBC, en tegelijk ook de reden dat we hem in ons onderzoek hebben meegenomen, is de oncomplexe werking ervan. Daarmee is de RBC prima geschikt als controle voor de prestaties van de tweede methode; de relational probability tree. Een relational probability tree, of RPT, [4] leert probability trees op basis van relationele data en is zoals de naam al doet vermoeden afgeleid van een traditionele probability tree leerder. Deze methode slaat multisets plat met behulp van een aggregatie functie. Zo kan bijvoorbeeld de som van alle waarden in een multiset worden berekend of kan het aantal waarden worden geteld dat aan een bepaald criterium voldoet. Daarnaast kan link degree als een concreet attribuut gebruikt worden bij constructie van de tree. Het grote voordeel van deze methode in ons onderzoek is de intuïtieve wijze waarop het model wordt gerepresenteerd en dientengevolge het gemak waarmee informatie uit de tree kan worden geïnterpreteerd.
3
Flickr
We richten ons in dit onderzoek op de vraag welke factoren van invloed zouden kunnen zijn op de zogenaamde interestingness van een foto op Flickr. Een korte introductie van Flickr is hier op zijn plaats. Flickr is een online fotodienst die gebruikers in staat stelt hun zelfgemaakte foto’s in hun databases op te slaan en toegankelijk te maken via het web. Dit laatste wordt voor een groot deel georganiseerd door gebruikers zelf. Foto’s zijn gekoppeld
6
aan de gebruiker die ze online heeft gezet (de eigenaar), maar ook aan zogenaamde grouppools en photosets waar de eigenaar zijn foto’s onderdeel van kan laten uitmaken. Vanaf nu zullen we kortweg spreken over foto’s, groepen en sets. Zodra een gebruiker een foto online zet komt deze standaard terecht op zijn profielpagina. De gebruiker kan vervolgens bepalen of de foto door iedereen te bekijken is of slechts door bepaalde medegebruikers. Een groep is een soort fotoalbum dat beheerd wordt door een gebruiker. Een groep richt zich doorgaans op een specifiek onderwerp, bijvoorbeeld Amsterdam, macro fotografie of foto’s met een panoramaformaat. Door lid te worden van de groep kan een eenieder de beheerder verzoeken één of meerdere van zijn eigen foto’s in de groep op te nemen. Ook voor een groep geldt dat deze publiek kan zijn of slechts na toestemming toegankelijk kan zijn. Een set heeft eveneens de functie van fotoalbum, maar dient als middel voor een gebruiker om zijn eigen foto’s op zijn profielpagina te ordenen. In een set zitten derhalve louter en alleen foto’s van de eigenaar (en beheerder) van de set. Naast de ruwe foto’s en de structuur waarbinnen deze zijn gerepresenteerd bevat Flickr nog een derde type informatie, namelijk metadata. Iedere foto, group en set slaat gegevens op die eraan gerelateerd zijn. Zo hebben alle drie een titel en kunnen foto’s door zowel de eigenaar als andere gebruikers becommentarieerd en gelabeld worden. Ook de eigenschap die in ons onderzoek in de schijnwerpers staat – de zogenaamde interestingness – beschouwen we als metadata. Flickr hanteert een algoritme om uit de honderdduizenden foto’s die iedere dag online worden gezet de 500 meest interessante te selecteren. Dit betekent dat een foto alleen als interessant kan worden aangemerkt op de dag dat hij online is gezet. De werking van dit algoritme wordt angstvallig geheim gehouden en of een foto als interessant is aangemerkt en op welke dag is niet direct als metadata beschikbaar. Wel is voor iedere dag een lijst met de 500 geselecteerde foto’s te bezichtigen.
4
Selectie en preprocessing van de data
De eerste stap in het KDD proces behelst het selecteren van interessante elementen uit de volledige ruwe database van Flickr. Hierbij is het van belang een goede afweging te maken tussen de selectie van naar verwachting relevante informatie enerzijds en het bemoeilijken van experimenten als gevolg van een te grote afmeting of complexiteit van de selectie. In het verlengde van data selectie vindt preprocessing plaats. In deze stap wordt een keuze gemaakt voor de manier waarop we informatie uit de selectie in onze experimenteerset willen representeren. Zo kan ieder commentaar op een foto als apart object worden gerepresenteerd, waarbij de link degree ons vertelt hoe vaak op een foto gereageerd is, maar ook kunnen we ervoor kiezen het aantal reacties direct als attribuut van foto op te slaan. Tijdens de preprocessing stap hebben we meerdere vergelijkbare afwegingen moeten maken. Ook hebben we in deze stap onze selectie geverifieerd, in die zin dat data die bij nader inzien geen informatiewaarde bleken te hebben alsnog uit de selectie zijn verwijderd. Zo hadden we in eerste instantie de eigenschap dat een foto dienst doet als voorblad van een set meegenomen. Toen bleek dat dit voor geen van de geselecteerde foto’s op ging hebben we de eigenschap uit de selectie gehaald. In onderstaand overzicht benoemen we alle informatie die we hebben geselecteerd en op welke wijze we ze in de experimenteerset hebben gerepresenteerd.
7
•
•
•
•
Object: photo Representeert: een foto o Attribuut: pixels Representeert: de afmeting van de foto (breedte × hoogte) Waarden: continu o Attribuut: commentsCount Representeert: het aantal reacties op een foto Waarden: continu o Attribuut: tagsCount Representeert: het aantal labels dat aan een foto gehangen is Waarden: continu o Attribuut: notesCount Representeert: het aantal notities2 dat op een foto gemaakt is Waarden: continu o Attribuut: license Representeert: de licentie waaronder de foto is gepubliceerd Waarden: {0, 1, 2, 3, 4, 5, 6} waarin 0 staat voor geen licentie en 1 tot en met 6 voor de zes verschillende Creative Commons licenties3 o Attribuut (target): interesting Representeert: of de foto door Flickr is aangemerkt als interessant Waarden: {True, False} Object: group Representeert: een groep o Attribuut: membersCount Representeert: het aantal gebruikers dat lid is van de groep Waarden: continu Object: set Representeert: een set o Attribuut: photosCount Representeert: het aantal foto’s dat zich in de set bevindt Waarden: continu Link: is-in Representeert: een relatie tussen een foto en een groep of set die aangeeft dat de betreffende foto zich in de betreffende groep of set bevindt
De praktische uitvoering van zowel selectie als preprocessing heeft zich afgespeeld in en rondom een zelfgeschreven tooltje dat als brug fungeerde tussen Flickr enerzijds en Proximity, de software waarin de volgende stappen van het KDD proces zijn uitgevoerd, anderzijds. In de volgende paragraaf zal nader ingegaan worden op Proximity. Ons tooltje haalt met behulp van de Flickr API4 alle ruwe data op die nodig is om de bovenstaande objecten, links en attributen te kunnen samenstellen. Voor het merendeel hiervan zal geen nadere toelichting nodig zijn, maar de afwijkende manier waarop interestingness door Flickr wordt gerepresenteerd maakt dat hier wat meer zorgvuldigheid vereist is. Zoals eerder gezegd is voor iedere dag een lijst van 500 foto’s beschikbaar die 2
Een notitie is commentaar op een foto, maar dan direct op de foto geplaatst als een soort post-it note. Notities kunnen net als commentaar ook door anderen dan de eigenaar van de foto geplaatst worden, alhoewel hiervoor iets meer voorwaarden gelden. 3 http://creativecommons.org/licenses/ 4 De Flickr API biedt de mogelijkheid gestructureerde Flickr data via een achterdeur uit hun database op te vragen.
8
Flickr het predicaat interessant heeft toegekend. Omdat een foto louter als interessant kan gelden op de dag dat hij online is gezet moeten we ervoor zorgdragen dat alle foto’s die we vergaren op dezelfde dag online zijn gezet. Alleen op die manier kunnen we foto’s vinden waarvan we met zekerheid kunnen zeggen dat ze nooit als interessant zijn aangemerkt. Als eerst selecteren we de 500 foto’s uit de interestingness lijst en geven deze in onze dataset het predicaat interesting. Vervolgens nemen we 1000 willekeurige foto’s van dezelfde dag en geven alle foto’s hiervan die niet reeds in onze verzameling van 500 interessante foto’s zit het predicaat niet interesting. Voor alle foto’s (zowel interesting als niet interesting) nemen we alle groepen en sets waarin de foto is opgenomen en voegen deze toe aan onze dataset, uiteraard zodanig dat identieke groepen of sets slechts één keer opgenomen worden. Ten slotte leggen we voor iedere gevonden relatie tussen een foto en een groep of set een is-in link tussen de betreffende photo en group of set. Het resultaat is een relationele dataset van 1498 foto’s, 2380 groepen, 650 sets en 7281 is-in links. Merk op dat niet publiek toegankelijke foto’s, groepen en sets volledig buiten beschouwing zijn gelaten. De vergaarde data is vervolgens in een door Proximity geaccepteerd formaat weggeschreven, hetgeen ons in staat stelt over te gaan op de volgende stap in het KDD proces. Het gehele traject van Flickr API tot Proximity importeerbestand is tamelijk onomslachtig en verloopt dankzij een tooltje als de onze volledig automatisch. Relevant om hier echter bij te vermelden is dat de tijd die benodigd is om grote hoeveelheden data te vergaren, als gevolg van het feit dat meerdere API aanroepen nodig zijn om voor iedere foto alle gewenste informatie te verzamelen, nogal kan oplopen. Een potentieel probleem met de dataselectie die wij gemaakt hebben is het feit dat bepaalde metadata van een foto kan veranderen als gevolg van de speciale positie op de website die Flickr geeft aan interessante foto’s. Zo is het aannemelijk dat het aantal reacties op een foto harder stijgt dan gewoonlijk zodra een foto in de interestingness lijst terecht komt. Hetzelfde geldt vermoedelijk voor het aantal labels en notities van een foto. We zijn op zoek naar aspecten die een rol spelen in het algoritme dat Flickr hanteert ter bepaling van interestingness, en niet zozeer naar aspecten die ons in staat stellen om achteraf te kunnen inschatten of een foto interesting is (geweest). We lopen het gevaar toch laatstgenoemde aspecten te vinden zodra we het aantal reacties, labels en notities meenemen in de dataset op basis waarvan we gaan modelleren. Om dit risico te minimaliseren hebben we ervoor gekozen foto’s te vergaren die de voorgaande dag online zijn gezet, zodat de tijd die verstreken is sinds foto’s in de interestingness lijst verschenen zijn zo klein mogelijk gehouden wordt. Nog beter zou zijn om reacties, labels en notities die na de betreffende dag zijn toegevoegd (en dus sowieso nadat de foto als interesting is aangemerkt) niet mee te tellen. Ook dan nog echter kan ruis als gevolg van het geschetste probleem niet volledig uitgesloten worden, aangezien niet te achterhalen is wanneer precies gedurende de dag een foto in de interestingness lijst is opgenomen.
5
Transformatie van de data ter voorbereiding op data mining
De data die het resultaat is van de vorige twee stappen uit het KDD proces importeren we in Proximity5, een knowledge discovery tool. Hierin zal de data mining plaatsvinden, alsook de transformaties ter voorbereiding hierop. Het grote voordeel dat Proximity ons biedt is dat het ons in staat stelt de transformaties en de data mining snel en effectief uit te voeren, zonder dat veel tijd en energie geïnvesteerd hoeft te worden in het ontwikkelen van eigen implementaties 5
http://kdl.cs.umass.edu/software/
9
van deze handelingen. Tegelijkertijd brengt dit het nadeel met zich mee dat we bij onze experimenten vastzitten aan de functionaliteit die Proximity ons biedt. We doen een tweetal transformaties. Teneinde een model te kunnen leren hebben we instanties nodig. Omdat we te maken hebben met één grote brok gerelateerde objecten moeten we op zoek naar criteria om uit deze brok kleine bruikbare brokjes data te extraheren. Deze kleine bruikbare brokjes worden in Proximity subgraphs genoemd. Een subgraph bevat een kernobject en daarnaast een aantal gerelateerde objecten die voldoen aan opgegeven criteria. Dit kunnen louter direct gerelateerde objecten zijn, maar ook indirect gelinkte objecten zijn mogelijk. Wij zijn op zoek naar een voorspelling voor het attribuut interesting op het object photo. We kiezen dan ook photo als kernobject. Daarbij willen we alle (eventuele) direct gerelateerde group- en setobjecten in beschouwing nemen, omdat we verwachten dat de wijze waarop een foto zich verhoudt tot groepen en sets iets kan zeggen over de interestingness van een foto. Wanneer we deze criteria loslaten op de volledige dataset levert dit een verzameling 1d-star [1] subgraphs op vergelijkbaar met degene die te zien is in figuur 3. Voordat onze data geschikt is voor data mining staat ons nog slechts één transformatie te wachten. Zodra we een model geleerd hebben wensen we hier pas conclusies uit te trekken als er enige zekerheid is over de kwaliteit van het model. Eén relevante manier om deze kwaliteit te meten is door op basis van het model ongeziene instanties te classificeren en hiervan het succes te bepalen. Om deze aanpak mogelijk te maken hebben we minstens twee subverzamelingen van onze verzameling subgraphs nodig; één om te trainen en één om te testen. De laatste transformatie behelst dan ook het willekeurig opdelen van de verzameling subgraphs in twee even grote subverzamelingen. Slechts twee subverzamelingen maakt het onmogelijk om bij de beoordeling van kwaliteit van de modellen kruisvalidatie toe te passen, maar omdat we in dit onderzoek niet geïnteresseerd zijn in de exacte prestaties van een model is kruisvalidatie niet noodzakelijk en voldoet een onderverdeling in een trainingset en een testset.
Figuur 3 Eén van onze subgraphs. Hierin is een rode knoop een photo object, een groene een group object, een blauwe een set object en een vector een is-in link.
6
Data mining
Nu de data er klaar voor is, is het moment aangebroken om de feitelijke leermethoden erop toe te passen. In ieder van de drie experimenten leren we een RPT en classificeren op basis hiervan de testset. Daarnaast passen we op dezelfde wijze de RBC toe, als controle voor de prestaties van de RPT. Voor alle parameters die in Proximity de gelegenheid geven de aanpak van een methode bij te stellen hebben we altijd de standaard (default) waarden gekozen.
10
6.1
Experiment 1
In ons eerste experiment leren we op basis van alle in paragraaf 4 genoemde attributen. Tabel 1 toont van beide methoden de accuratesse en het gebied onder de ROC curve. Het gebied onder de ROC (receiver operating characteristic) curve is beter geschikt om resultaten van verschillende methoden met elkaar te vergelijken [6]. De hoogte van zowel accuratesse als gebied onder ROC curve is opvallend. Ook schept de grote overeenkomst tussen de uitkomsten van RBC en RPT vertrouwen in de bruikbaarheid van de RPT. Figuur 4 maakt inzichtelijk welke aspecten in deze RPT een rol spelen. Hierin valt op dat het aantal reacties op een foto zeer dominant aanwezig is. Zoals in paragraaf 4 uiteengezet kunnen we vraagtekens plaatsen bij de betekenis van correlaties tussen dit attribuut en het target attribuut. Om deze reden doen we een tweede experiment waarin het aantal reacties op een foto niet meegenomen wordt bij het leren van een model. Accuratesse 0.975 0.985
RBC RPT
Gebied onder ROC curve 0.994 0.996
Tabel 1 Classificeerprestaties van de twee methoden op alle attributen in de selectie.
Figuur 4 RPT geleerd op basis van alle attributen in de selectie.
6.2
Experiment 2
Tabel 2 en figuur 5 tonen de resultaten van de toepassing van de twee leermethoden zonder in acht name van het aantal reacties op een foto. Alhoewel de prestaties van de classificaties met zowel RBC als RPT wat lager zijn dan bij experiment 1 zijn deze nog altijd niet slecht te noemen. Bovendien vertonen de prestaties van beide methoden een vergelijkbare tendens, waaruit we kunnen afleiden dat de RPT nog altijd relevant is. Wanneer we kijken naar de aspecten die een rol spelen in deze RPT valt een overeenkomst met figuur 4 op. Ook hier weer heeft een discutabel attribuut de hoofdrol; het aantal labels dat aan een foto hangt.
11
Hoewel de dominantie van dit attribuut dit maal wat minder groot is dan bij experiment 1 besluiten we ook dit keer een nieuw experiment op te zetten met als doel een RPT zonder prominente positie voor dubieuze attributen. Accuratesse 0.887 0.788
RBC RPT
Gebied onder ROC curve 0.956 0.862
Tabel 2 Classificeerprestaties van de twee methoden op alle attributen in de selectie met uitzondering van het aantal reacties op een foto.
Figuur 5 RPT geleerd op basis van alle attributen in de selectie met uitzondering van het aantal reacties op een foto.
6.3
Experiment 3
In een poging iedere schijn te vermijden dat het model op basis waarvan we in de volgende stap kennis zullen trachten af te leiden misleidende correlaties bevat laten we in dit laatste experiment alle attributen die mogelijk vervuild zijn als gevolg van de waarde van het interesting attribuut buiten beschouwing. Dit betekent dat het aantal reacties op een foto, het
12
aantal labels dat aan een foto hangt en het aantal notities dat op een foto gemaakt is door de methoden niet langer gebruikt worden om een model of classificaties op te baseren. De resultaten zijn te zien in tabel 3 en figuur 6. Afgaande op de prestaties van de classificeerders kunnen we stellen dat de kwaliteit van de modellen wederom is afgenomen, maar nog altijd niet zo laag is dat de bruikbaarheid ervan ter discussie staat. De verandering van het gebied onder de ROC curve laat ten opzichte van het vorige experiment wederom voor beide methoden een gelijksoortige tendens zien, hetgeen ons het vertrouwen geeft dat we uit de RPT met recht enkele conclusies mogen trekken. Accuratesse
Gebied onder ROC curve 0.900 0.945 0.729 0.806
RBC RPT
Tabel 3 Classificeerprestaties van de twee methoden op alle attributen in de selectie met uitzondering van het aantal reacties op een foto, het aantal labels dat aan een foto hangt en het aantal notities dat op een foto gemaakt is.
Figuur 6 RPT geleerd op basis van alle attributen in de selectie met uitzondering van het aantal reacties op een foto, het aantal labels dat aan een foto hangt en het aantal notities dat op een foto gemaakt is.
7
Interpretatie van het model
De RPT uit experiment 3 (figuur 6) achten we bruikbaar voor een interpretatie, de laatste stap in het KDD proces. Geen van de attributen die erin voorkomt kan naar onze mening verdacht worden van een onterechte correlatie met het target attribuut. We zullen enkele knopen bespreken die een overduidelijke invloed hebben op de uiteindelijke probability estimation. Hierbij schromen we niet er lustig op los te generaliseren in de hoop op enkele grote lijnen te stuiten.
13
1. Knoop: Degree(set._degree_) >= 2.0 Betekenis: De foto is minimaal in twee sets opgenomen Mogelijke duiding: Wanneer dit criterium opgaat heeft dit een positieve invloed op de waarschijnlijkheid dat de foto interessant bevonden wordt. Het is aannemelijk dat een dergelijk criterium een rol speelt, aangezien het feit dat een foto in meer dan één set zit zou kunnen aangeven dat de eigenaar meer dan gemiddelde energie steekt in het ordenen van zijn foto’s. Deze meer dan gemiddelde energie steekt hij wellicht eveneens in het maken van foto’s, met als gevolg een grotere kans op interessante foto’s. 2. Knoop: CountContinuous(photo.pixels <= 5625.0) >= 1.0 Betekenis: De foto heeft een afmeting van maximaal 5625 pixels Mogelijke duiding: Als een foto heel klein is (kleiner dan ca. 75 × 75 pixels) dan zal het niet snel een interessante foto zijn (of worden). Ook dit is een aannemelijk criterium, aangezien foto’s die te klein zijn snel in mindere mate indrukwekkend zijn. 3. Knoop: Degree(group._degree_) >= 4.0 Betekenis: De foto is minimaal in vier groeps opgenomen Mogelijke duiding: Wanneer naast het eerste criterium ook dit criterium opgaat neemt de waarschijnlijkheid van interestingness juist weer af. Dit verband is intuïtief minder overtuigend, maar ook niet sowieso te verwerpen. 4. Knoop: Count(photo.license = 5) >= 1.0 en Count(photo.license = 6) >= 1.0 Betekenis: De foto is gepubliceerd onder licentie 5 of 6 Mogelijke duiding: Zodra dit criterium opgaat is kans op interestingness groot. Het is aannemelijk dat een dergelijke logica in het algoritme van Flickr is opgenomen, om een zelfde reden als dat we criterium 1 als aannemelijk beschouwen. Experimenten op een grotere dataset zouden moeten uitwijzen of dit verband specifiek geldt voor licentie 5 en 6 of dat, zoals aannemelijker is, het erom gaat dat een gebruiker de moeite heeft genomen überhaupt een licentie met zijn foto te associëren.
8
Conclusie
In dit onderzoek hebben we een allereerste poging gedaan op basis van data van Flickr kennis te vinden over de werking van hun algoritme ter bepaling van interestingness. Gezien het sterke verkennende karakter van het onderzoek is relatief ondiep in zeer beperkte data gegraven. Een begin is gemaakt door met behulp van enkele snel te gebruiken leermethoden een tamelijk ongenuanceerde blik te werpen op kennis die zich aan de oppervlakte van onze kleine dataset bevindt. Het is bemoedigend te kunnen constateren dat zelfs uit onze modellen desalniettemin enkele overtuigende conclusies getrokken lijken te kunnen worden. Bovendien blijkt uit de relatief hoge classificatiescores dat de modellen op zijn minst enkele spijkers op de kop slaan. Gezien de uitgebreide mogelijkheden voor grondiger, genuanceerder en bovenal breder onderzoek (zie de volgende paragraaf) geven onze resultaten goede redenen voor een vervolg van het traject dat door ons in dit onderzoek is ingezet.
9
Toekomstig onderzoek
Zoals gezegd in de vorige paragraaf leent ons domein zich uitstekend voor diverse vervolgonderzoeken. Het relationele karakter van de data maakt onderzoek gemakkelijk schaalbaar. De huidige dataset kan moeiteloos verrijkt worden met een schier oneindige
14
hoeveelheid en verscheidenheid aan objecten en links, zonder dat het overgrote deel van het werk uit ons onderzoek opnieuw of anders gedaan hoeft te worden. Benodigde preparerende werkzaamheden blijven in grote lijnen onveranderd en relationele leermethodes blijven op dezelfde wijze inzetbaar. Wij menen dat vervolgonderzoeken in een aantal richtingen in het bijzonder veel extra waarde kunnen toevoegen.
9.1
Uitbreiding van de dataset
Er liggen vele mogelijkheden tot uitbreiding van de dataset, zowel kwantitatief als kwalitatief. Flickr beschikt over een enorme hoeveelheid data, waarvan in ons onderzoek slechts een hele kleine dwarsdoorsnede bekeken is. Daarbij komt dat deze dwarsdoorsnede nog zeer ver uitgebreid kan worden. In ons onderzoek is slechts een beperkt aantal mogelijk relevante aspecten meegewogen. Niet alleen verstrekt Flickr veel meer metadata dan wij beschouwd hebben, ook de structuur van de site is veel uitgebreider dan het samenspel van foto’s, groepen en sets waar wij ons op hebben gericht. Ten eerste is veel data beschikbaar over datum en tijdstip waarop diverse content is toegevoegd. Het is zeer aannemelijk dat de positie van bepaalde gebeurtenissen in de tijd een zeer belangrijke rol spelen in het interestingness algoritme van Flickr. Dit aspect is in ons onderzoek volledig buiten beschouwing gelaten. De verwachting is dat sterke correlaties gevonden kunnen worden wanneer slim en relevant met deze data wordt omgesprongen. Ten tweede wordt het relationele karakter van de Flickr data in ons onderzoek niet ten volle uitgebuit. Zo hebben de meeste groepen en sets in onze dataset slechts één of enkele gerelateerde foto’s. Dit is enerzijds simpelweg een gevolg van het feit dat we slechts een heel klein hapje uit de gigantische beschikbare brok hebben genomen, anderzijds ook van de wijze waarop we die hap genomen hebben. Wanneer data vergaard wordt gecentreerd rondom groepen of sets in plaats van – zoals wij hebben gedaan – gecentreerd rondom foto’s zal een groot deel van de groepen en sets in de dataset een vollediger pallet aan relaties hebben. Wij verwachten dat een dergelijke verschuiving van het perspectief tot nieuwe verbanden en inzichten kan leiden. Ten slotte hebben we één zeer belangrijk onderdeel van de structuur van de Flickr website volkomen genegeerd. Foto’s zijn eigendom van een gebruiker, zo ook sets. Het toevoegen van gebruikerselementen aan de dataset komt de intergerelateerdheid van de dataset ten goede en dientengevolge naar verwachting eveneens de rijkheid van kennis die eruit gehaald kan worden.
9.2
Rijkere subgraphs
De rijkheid van de instanties die gebruikt worden bij het leren van een model is direct van invloed op de rijkheid van de verbanden die een dergelijk model kan bevatten. Wij hebben in dit onderzoek uitsluitend gebruik gemaakt van 1d-star subgraphs. Gezien de aard van Flickr data is het niet aannemelijk dat correlaties zich beperken tot attributen van objecten die direct gerelateerd zijn. Veel kan daarom verwacht worden van subgraphs die in staat zijn complexere structuur te representeren. Zo zou simpelweg een uitbreiding naar het gebruik van 2d-star subgraphs [1] al veel nieuws kunnen opleveren.
15
9.3
Probabilistic relational models
De twee methoden die wij hebben gehanteerd maken beide gebruik van propositionalisatie teneinde met relationele data overweg te kunnen. Alhoewel dit een effectieve sluiproute is gebleken is het ook zeker interessant om naar methoden te kijken die relationele data niet degraderen tot minder rijke propositionele data maar de structuur ervan juist in hun voordeel laten werken. Probabilistic relational models (PRM) zoals het relational dependency network (RDN) [3] kunnen een diep inzicht verschaffen in de afhankelijkheden die aanwezig zijn binnen een domein. Met behulp van een RPT kan dan wel iets worden gezegd over de invloed van bepaalde attributen of degrees op het target attribuut, maar niet over hoe deze attributen op hun beurt weer beïnvloed worden. Dergelijke inzichten worden voornamelijk interessant zodra meer ‘dynamische’ attributen (attributen die niet keihard worden bepaald door bijvoorbeeld de maker van een foto) in de dataset worden opgenomen.
9.4
Patroonherkenning of natural language processing
Veel Flickr metadata is in tekstvorm. Titels, labels en reacties zijn enkele in het oog springende voorbeelden hiervan. In deze teksten zit veel informatie verborgen over het karakter van een foto en over hoe een foto door anderen ontvangen wordt. Logischerwijs is dit de ideale informatie om de mate van interestingness op te funderen. Voordat we er echter mee uit de voeten kunnen zou een zekere mate van patroonherkenning of natural language processing (NLP) aan het KDD proces toegevoegd moeten worden. Op welke wijze dit de meeste kansen biedt laten wij graag aan de specialisten op dit vakgebied over.
Referenties [1]
H. Blau, N. Immerman, and D. Jensen. A Visual Language for Querying and Updating Graphs. University of Massachusetts Amherst, Computer Science Department Technical Report 2002-037. 2002.
[2]
U.M. Fayyad, G. Piatetsky-Shapiro, and P. Smyth. From Data Mining to Knowledge Discovery: An Overview. Advances in Knowledge Discovery and Data Mining, edited U.M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, AAAI Press/MIT Press. pp. 1-34. 1996.
[3]
J. Neville and D. Jensen. Dependency Networks for Relational Data. Proceedings of the Fourth IEEE International Conference on Data Mining. 2004.
[4]
J. Neville, D. Jensen, L. Friedland, and M. Hay. Learning Relational Probability Trees. Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2003.
[5]
J. Neville, D. Jensen, and B. Gallagher. Simple Estimators for Relational Bayesian Classifiers. Proceedings of The 3rd IEEE International Conference on Data Mining. Available as University of Massachusetts Amherst, Computer Science Technical Report 2003-004. 2003.
16
[6]
F. Provost and T. Fawcett. Analysis and Visualization of Classifier Performance: Comparison under Imprecise Class and Cost Distributions. Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. AAAI Press. pp. 43-48. 1997.
17
