Versie overzicht V17 augustus 2009 Subversion revisie 134 V14 augustus 2009 Subversion revisie 128 V3 augustus 2009 Subversion revisie 112

Voorblad

Versie overzicht V17 augustus 2009 – Subversion revisie 134 Ruw overzicht bestandsgrootte bij % verwijdering van veel voorkomende woorden. Hoofdstuk opdrachtformulering. V14 augustus 2009 – Subversion revisie 128 Oude resultaten, interpretaties en conclusie weg gehaald. Nieuwe resultaten als ‘scratch’ ingevoerd. Hier en daar wat interpretaties geschreven. V3 augustus 2009 – Subversion revisie 112 Opdrachtomschrijving abstracter gemaakt zodat de scoping de rationale kan bevatten voor de keuze in tekst-soort. Aantekeningen van: conclusie en further research als concept geplaatst in de daarvoor bestemde secties. V30 juli 2009 – Subversion revisie 108 Indeling bijgeschaafd. Inleiding bevat nu enkel achtergrond informatie (opdracht/bedrijf/uni), leeswijzer. Hoofdstuk 2 is ingedeeld in delen: Opdrachtformulering, Scoping, Relevantie en Onderzoeksvragen. De overige stukken zijn verplaatst naar H3. Onderzoeksmethode en bevat dus: Methodologie, Aanpak en tot op heden Beschrijving van: corpus, referentiemodel, validatiemethode. Als scratch is toegevoegd een somsgewijze V29 juli 2009 – Subversion revisie 100 Een eerste versienummering voor de tot nu toe opgebouwde basis. Deze basis bevat o.a. een introductie, formulering van de opdracht en onderzoeksvraag, doelstelling, relevantie en wat observaties uit de voorstudie. V0.0 Er is enkel sprake van ongestructureerde aantekeningen die tezamen toevallig een document vormen.

Voorwoord Na veel zweet (maar gelukkig geen bloed en tranen), ligt hier voor u mijn master thesis. Bedanken -> begeleiding: Jan van Eijck, Paol Varekamp Andere mensen van logica: Hans de Vreeze, Edwin Essenius(voor helpen vaststellen opdracht). Collega studenten van working tomorrow Klasgenoten met wie ik leuke studie tijd heb gehad, met name de mensen uit m’n team: Jeroen van lieshout, nickolas heirbout, Menno middel, erik slaghter, paul mooij Bedanken mensen die mee gegeven de referentieset berichten hun eigen relevantie (clustering) hadden aangegeven. Laurence van bilderbeek, Robbert faase, roos de groot, Gerrit Jonker, Ivan Cacic, Sander Wierstra, Jan Wiebe Olijve, Daan mastenbroek.

Contents Voorblad ................................................................................................................................................. 1 Versie overzicht....................................................................................................................................... 2 Samenvatting .......................................................................................................................................... 6 1.

Inleiding........................................................................................................................................... 7 1.1.

1.1.1.

Opdracht .......................................................................................................................... 7

1.1.1.

Logica ............................................................................................................................... 7

1.1.2.

Universiteit van Amsterdam ............................................................................................. 8

1.1. 2.

3.

4.

Achtergrondinformatie ............................................................................................................ 7

Leeswijzer ................................................................................................................................ 8

Opdrachtformulering & Probleemstelling ........................................................................................ 9 2.1.

Opdrachtformulering ............................................................................................................... 9

2.2.

Scoping .................................................................................................................................... 9

2.2.1.

Nieuwsberichten .............................................................................................................. 9

2.2.2.

Clustering by Compression ............................................................................................... 9

2.3.

Relevantie .............................................................................................................................. 10

2.4.

Onderzoeksvragen ................................................................................................................. 10

Onderzoeksmethode ..................................................................................................................... 11 3.1.

Vaststellen referentiemodel. .................................................................................................. 11

3.2.

Proefondervindelijke toetsing eerste hypothese..................................................................... 12

3.3.

Proefondervindelijke toetsing overige hypothesen. ................................................................ 12

3.3.1.

Experiment: Normalisatie in lengte ................................................................................. 12

3.3.2.

Experiment: Verwijdering van veel voorkomende woorden ............................................ 13

3.3.3.

Experiment: Alfabetische sortering van de woorden. ...................................................... 13

3.3.4.

Experiment: combinaties van eerder genoemde experimenten ...................................... 13

3.4.

Beschrijving Corpus ................................................................................................................ 14

3.5.

Beschrijving verificatieset en referentiecluster ....................................................................... 14

3.6.

Beschrijving validiatiemethode............................................................................................... 15

3.6.1.

Meten van clusterfouten of ‘clustering error’ ................................................................. 15

3.6.2.

Incrementele uitbreiding referentiemodel ...................................................................... 16

Achtergrond en Context................................................................................................................. 17 4.1.

Begripvorming........................................................................................................................ 17

5.

4.2.

Eerdere succesvolle implementaties NCD ............................................................................... 18

4.3.

Relevant onderzoek ............................................................................................................... 18

4.4.

Observaties uit voorstudie ..................................................................................................... 20

Onderzoek ..................................................................................................................................... 20 5.1.

Vergelijking standaard implementatie met het referentiecluster ............................................ 20

5.2.

Op zoek naar fouten ............................................................................................................... 21

5.2.1.

Iteratieve uitbreiding van de verificatieset ...................................................................... 21

5.2.2.

Verklaring van de fouten ................................................................................................ 22

5.3.

Opzoek naar verbeteringen .................................................................................................... 23

5.3.1.

Resultaten lengte normalisatie ....................................................................................... 24

5.3.2.

Resultaten verwijdering van vele voorkomende woorden............................................... 25

Bestandsgrootte ............................................................................................................................ 26 5.3.3.

Resultaten alfabetische sortering van de woorden ......................................................... 26

5.3.4.

Resultaten overige experimenten ................................................................................... 27

6.

Resultaten ..................................................................................................................................... 29

7.

Conclusie ....................................................................................................................................... 30

Bibliography .......................................................................................................................................... 31 Bijlage 1.

Overzicht artikelen uit referentiemodel .............................................................................. 32

Bijlage 2.

Grote versie referentiecluster ............................................................................................ 33

Bijlage 3.

Grote versie referentiecluster + P1,P2,P3 ........................................................................... 34

Oude notities en rotzooi ........................................................................................................................ 35

Samenvatting Wat de uva in een samenvatting zou willen zien: Op deze ene bladzijde staat alles wat ik vind dat iemand die niet meer dan vijf minuten leestijd heeft over mijn project moet weten. Hierin wordt de volgende informatie herhaald die elders in je scriptie uitgebreid behandeld wordt: • De relevantie en motivatie voor het onderzoek • De onderzoeksvraag met mogelijk een korte beschrijving van je onderzoeksaanpak • De behaalde resultaten en conclusies (dus de bijdragen van je scriptie) Kortom, dit is een soort poster voor je script. Zie als voorbeeld de abstract van: http://homepages.cwi.nl/~paulk/ thesesMasterSoftwareEngineering/2006/JonathanWitkamp.pdf.

1. Inleiding 1.1.

Achtergrondinformatie

1.1.1. Opdracht Nieuwe opdracht introductie schrijven die beter overeen komt met de ‘abstractere opdrachtformulering’. Deze vormen om de volgende steekwoorden: ongeclassificeerde en gestructureerde teksten, zoeken van relevante teksten, bij elkaar groeperen van relevante teksten. verwijderen: Al sinds het ontstaan van het internet zijn er bedrijven die hun nieuwsberichten tekstueel hetzij online, presenteren aan hun lezers. Deze nieuwsberichten woorden doorgaans opgeslagen als losse objecten in een database. Hoewel de database de mogelijkheid biedt om relaties tussen berichten te specificeren, wordt dit echter bijna niet gedaan omdat het een handmatig proces betreft. Wanneer berichten echter wel automatisch gekoppeld worden, betreft of vaak zeer complexe methoden gebruik makend van pattern-matching en semantische analyses (zie b.v. Automation), of semiautomatische processen zoals het handmatige tagging / classificatie om vervolgens automatisch relaties te leggen. Verwijderen: Nu wil het geval zo zijn, dat er niet lang gelden een methode is ontwikkeld om de gelijkenis tussen twee “objecten” uit te drukken. Omdat deze methode succesvol is ingezet voor diverse classificatie vraagstukken (Zie hoofdstuk) en instaat is de gelijkenis tussen twee objecten uit te drukken volgt automatisch dan ook de vraag of deze methode dan ook niet geschikt is om te gebruiken op nieuwsberichten. Vragen die hierbij horen zijn: Kan de NCD gebruikt worden om nieuwsberichten dusdanig aan elkaar te relateren dat de gerelateerde berichten ook daadwerkelijk aangeboden kunnen worden aan de lezer; en Kan de NCD gebruikt worden om nieuwsberichten automatisch te classificeren. Motivatie / Theorie: aangezien de NCD dus de gelijkenis tussen berichten uitdrukt, zou de NCD dus uitstekend ingezet kunnen worden om lezers van berichten aanbevelingen te doen voor het lezen van andere berichten, zonder ingewikkelde semantische analyses of tagging processen.

1.1.1. Logica Het onderzoek wordt uitgevoerd in opdracht van Logica Rijswijk (afdeling public sector). Logica plc. is op 30 december 2002 ontstaan uit het voormalige Logica plc. (60%) en het voormalige CMG plc. (40%) Beide ICT-dienstverleners zijn van oorsprong Engelse bedrijven, maar CMG was in Nederland veel groter dan de Engelse moeder. Sinds 13 januari 2006 is tevens het Franse Unilog onderdeel van het bedrijf, waarmee het een derde thuismarkt heeft gecreëerd. Logica is een internationale ICT-dienstverlener en heeft wereldwijd momenteel 40.000 werknemers in 39 verschillende landen in dienst. Het behoort, ook qua omzet, tot de internationale top-20 in de ICT-dienstverlening. De omzet uit de traditionele ICTdienstverlening wordt voornamelijk in Europa en Australië (continent) gehaald. Logica levert diensten op tal van terreinen, zoals management- en ICT-consultancy, systeemontwikkeling en –integratie en neemt voor klanten complete bedrijfsprocessen in beheer. Het bedrijf ontwikkelt en implementeert oplossingen voor klanten over de hele wereld. Zij maakt daarbij gebruik van geavanceerde technologieën die direct doorwerken in de bedrijfsresultaten van de klant. Logica is een beursgenoteerde onderneming met noteringen aan de London Stock Exchange en Euronext Amsterdam.

Doelstelling van logica. Logica zal, indien blijkt dat de methode succesvol ingezet kan worden, de kennis willen gebruiken om als eerste te demonstreren bij haar klanten, maar ziet daarnaast ook mogelijkheid om het intern bij een aantal projecten te gebruiken. Hierbij kan gedacht worden om de methode in te zetten als matchfunctie voor vacatures en cv’s.

1.1.2. Universiteit van Amsterdam <Een mooi verhaal over de UvA – wellicht koppeling cwi vermelden> Doelstelling van de UvA.

1.1.

Leeswijzer



2. Opdrachtformulering & Probleemstelling

2.1.

Opdrachtformulering

De oorspronkelijke opdracht zoals geformuleerd door de onderzoeker in samenwerking met Logica en de Universiteit van Amsterdam is als volgt: “Onderzoek de geschiktheid van de methoden NGD en NCD (zoals gepresenteerd in (Cilibrasi & Vitanyi, 2006)) voor het relateren van teksten zoodanig de lezer van de tekst een aanbeveling gedaan kan worden voor het lezen van andere relevante teksten.”

Gegeven in de opdrachtformulering is de doelstelling van deze opdracht te onderzoeken of de NCD ingezet kan worden om de lezer van een bepaalde tekst aanbevelingen te doen voor het lezen van andere relevante berichten.

2.2.

Scoping

Omdat het hier een zeer brede opdrachtformulering betreft is het noodzakelijk om enige vorm van scoping toe te passen. Als eerste zal de Normalized Google Distance volledig buiten beschouwing worden gelaten. Daarnaast wordt de configuratie van de Normalized Compression Distance beperkt tot het gebruik van één enkel clustermethode en wordt het begrip “teksten” uit de opdrachtformulering opnieuw gedefinieerd. 2.2.1. Nieuwsberichten Wanneer we spreken over teksten dan kunnen we verschillende soorten teksten onderscheiden. Denk hierbij bijvoorbeeld aan verhalen, informatieve teksten, directieve teksten of beschouwende teksten. Het begrip tekst is dus erg breed, vandaar ook de keuze om dit begrip in te perken tot één enkel soort. Intuïtief gezien verschillen de tekstsoorten in mate van semantische explicietheid, dit intuïtieve gevoel wordt ook tastbaar gemaakt bij vertaalcomputers die afhankelijk van de tekstsoort beter of slechter functioneren (Russel & Norvig, 1995, p. 692). Om een voorbeeld te noemen zou in een gedicht gesproken kunnen worden over een term of object, zonder de naam ervan daadwerkelijk te noemen. In zekere zin is de semantiek bij deze slecht geëxpliciteerd – of niet expliciet syntactisch aanwezig. Het andere uiterste zullen we vinden in bijvoorbeeld wetenschappelijke artikelen of wetsartikelen waarbij het de doelstelling is om de kennis van de werkelijkheid van de lezer te vergroten en dit op zo een efficiënt mogelijke manier te doen. De keuze van tekstsoort valt dan uiteindelijk ook op nieuwsberichten. Naast de verwachting dat nieuws expliciet beschreven wordt, bieden nieuwsberichten tevens verificatiemogelijkheden vanwege de inherente classificatie die volgt uit de opbouw van dagbladen(binnenland, sport, etc.). Tevens is het gemakkelijk om een goede corpus samen te stellen aangezien nieuws vaak publiekelijk beschikbaar is. 2.2.2. Clustering by Compression Omdat deze opdrachtformulering te breed is bevonden, is er gekozen om de focus te leggen op de NCD methode zoals gepresenteerd in (Cilibrasi & Vitanyi, Clustering by Compression, JANUARY 2005). Er zal in

dit onderzoek niet geprobeerd worden om de NCD te combineren met andere hiërarchische clusteralgoritmen 1zoals de Ward’s Method (SAS Institute, 2009) of classificatie methoden zoals Support Vector Machines of Neural Networks (rudithesis) N.B. Het gebruik van Support Vector Machines vergt de beschikking over geclassificeerde ‘learning data’. Hoewel de testset volledig is geclassificeerd en dus uitermate geschikt zou zijn als learning data, betreft het alledaags wereldnieuws een soort waarbij enorm vaak nieuwe classificaties worden toegevoegd. In zekere zin kunnen we stellen dat men hierdoor altijd achter de feiten aan loopt. Daarnaast zal voor het gebruik van support vectormachines uitgezocht moeten worden hoe een similarity measure gebruikt kan worden voor classificatie middels een Support Vector Machine (een SVM wenst immers features (Hsu, Chang, & Lin, 2003)).

2.3.

Relevantie

Omdat het resultaat van het onderzoek een directe beantwoording is van de vraag of NCD ingezet kan worden voor de automatische relatielegging van nieuwsberichten, zullen nieuwsinstanties, dagbladen en nieuwswebsites groot belang hebben bij het antwoord. Immers zullen deze bij een positief antwoord hun diensten uit kunnen breiden. Ook op wetenschappelijk gebied is er een belang daar het onderzoek meer inzicht zal geven hoe de methode geschikt gemaakt kan worden voor het relateren (vinden van relevante informatie) van teksten en welke vormen van preprocessing het resultaat verbeteren. De beantwoording is met name interessant omdat er in teksten, nog meer dan andere vormen van data – een enorme ruimte is voor interpretatie.

2.4.

Onderzoeksvragen

De onderzoeksvraag die volgt uit de hiervoor gegeven opdrachtformulering en scope is als volgt: “In welke mate is de op „Normalized Compression Distance‟ gebaseerde „Clustering by Compression‟ methode geschikt2 voor het aan elkaar relateren van tekstuele nieuwsberichten?”

1

Voor further research kan op http://www.let.rug.nl/~kleiweg/clustering/ software gevonden worden om de clustering uit te voeren. 2 De ‘Clustering by Compression’ methode wordt hierbij geschikt geacht wanneer voor alle berichten uit een gevormd cluster geldt dat deze ten opzichte van elkaar als relevant worden ervaren voor een toenemend aantal berichten. De methode wordt als ‘voorwaardelijk geschikt’ geacht wanneer enkel door conditionering van de variabelen de methode geschikt blijkt en wordt anderzijds als ongeschikt beschouwd. De mate van ongeschiktheid komt verder overeen met het aantal fouten gemaakt bij de clustering.

Bij deze vraag is het de verwachting dat de methode in de normale vorm niet geschikt is. Deze verwachting is gebaseerd op de resultaten uit de experimentele voorstudie waaruit bleek dat de NCD beïnvloed wordt door de bestandsgrootte (Zie ook paragraaf X), daarnaast is het een bekend dat een verschil in bestandsgrootte per definitie zorgt voor een toenemendere dissimilarity(Bron paper). Tevens blijkt uit de literatuurstudie dat veelvoorkomende woorden een effect hebben op de mate van precisie van de NCD (Zie ook paragraaf X of (Ana Granados, Camacho, & Rodr´ıguez, 2008)). Hier op doorredenerend wordt de verwachting nog sterker dat de methode in zijn neutrale vorm niet geschikt is voor ons doel. Bijbehorende deze vraag worden dan ook de volgende hypothesen gesteld, de rationale achter deze hypothesen wordt gegeven in hoofdstuk X?3 Onderzoeksmethode. Hypothese 1. De Clustering by Compression methode is niet geschikt voor het aan elkaar relateren van tekstuele nieuwsberichten wanneer gebruik wordt gemaakt van de volledige tekst. Hypothese 2. De Clustering by Compression methode behaalt een beter resultaat wanneer de berichten genormaliseerd worden in lengte. Hypothese 3. De Clustering by Compression methode behaalt een beter resultaat wanneer de veel voorkomende woorden uit de tekst verwijderd worden. Hypothese 4. De Clustering by Compression methode behaalt een beter resultaat wanneer de woorden alfabetisch gesorteerd worden. TODO: Beschrijving geven van het geen verstaan wordt onder „veel voorkomende woorden‟ = woorden telling over de gehele corpus.

3. Onderzoeksmethode Het onderzoek zal geschieden volgens de empirische methode waar proefondervindelijk een antwoord op de gestelde vraag gevonden zal worden. Het moet duidelijk zijn dat de volgende stappen tevens deel uitmaken van een groter plan, opgedeeld in fasen volgt in (bijlage verwijzing ‘fasen overzicht’) hiervan een kort overzicht. De hieronder beschreven stappen betreft de invulling van fase 4: de gerichte experimentele fase. De eerder genoemde literatuurstudie en ongerichte experimentele fase maken tevens deel uit van de gefaseerde aanpak3. TODO: Onderkennen dat het moelijk is om überhaupt iets te bewijzen met de empirische methdoe @ bron methdoen en onderzoek boek.

3.1.

Vaststellen referentiemodel.

TODO: referentiemodel hernoemen net als verderop in de tekst al gedaan is.. naar: referentie set, of referentie cluster. Noem het “Vaststellen berichtenset ter verificatie”. Todo: Benadrukken waarom het referentiemodel voldoende gevalideerd is – en waarom i kdat denk.

Als eerste zal er een referentiemodel vastgesteld worden. Het referentiemodel wordt opgebouwd uit berichten waarvan bepaald is wat de optimale groepering is op basis van classificatie en menselijke 3

De hypothesen die ten gronden liggen van de experimenten zijn gebaseerd op bevindingen uit de fasen literatuurstudie en ongerichte experimentele fase (respect. fase 1 en 2).

interpretatie. Het referentiemodel zal in de verdere stappen van het onderzoek ingezet worden als verificatiemiddel waar het wordt vergeleken met de uitkomsten van de methode. De totstandkoming van het model wordt besproken in (verwijzing), de vergelijkingmethode wordt besproken in (verwijzing).

3.2.

Proefondervindelijke toetsing eerste hypothese.

TODO: in feite heb ik twee stappen gedaan: als eerste toetsing software, en verificatie methode. Vervolgens validatie bruikbaarheid van de methode. Dit zou ik eigenlijk nog vast moeten leggen ergens. Als het verificatiemodel eenmaal is vastgesteld, zal de eerste hypothese getoetst kunnen worden. Dit wordt simpelweg gedaan door de methode in te zetten op alle berichten uit het verificatiemodel en de resultaten van de methode te vergelijken met het verificatiemodel op basis van de eerder gerefereerde vergelijkingmethode. Na de vergelijking zijn er twee observaties mogelijk; Foutief en foutloos. Indien het resultaat foutief is, zal de hypothese direct bevestigd kunnen worden. Wanneer de methode echter een foutloos resultaat geeft, is helaas enkel bewezen dat de methode foutloos werkt voor de berichten uit het verificatiemodel. Om het nu wel aannemelijk te kunnen maken zal actief geprobeerd worden het referentiecluster te breken, door telkens niet-relevante berichten toe te voegen. Dit zal uiteindelijk leiden tot een bevestiging van de hypothese, of een falsificatie van de hypothese wanneer geldt dat voor alle nietrelevante berichten uit de corpus geldt dat deze de referentie clusters niet verstoren. Opmerkin van Edwin: Wanneer heb je genoeg getoetst om te kunnen zeggen dat de hypothese onjuist is?Wat zijn de gevolgen dan voor de andere hypothesen?

3.3.

Proefondervindelijke toetsing overige hypothesen.

Enkel indien de eerste hypothese bevestigd wordt, kan overgegaan worden tot het toetsen van de tweede en overige hypothesen. Belangrijk is het inzicht te hebben dat een falsificatie van de eerste hypothese het uitvoeren van de overige niet overbodig maakt. Het bevestigen van deze wordt echter moeilijker, maar het falsificeren kan nog steeds (immers kan geobserveerd worden dat de vorm conditionering er juist voor zorgt dat de methode slechter presteert). Voor de toetsing van deze hypothesen zal wederom een experiment uitgevoerd word. Dit keer zal echter gekeken worden naar het aantal fouten gemaakt in de clustering; we spreken over een betere prestatie wanneer er minder fouten worden gemaakt ten opzichte de neutrale inzet, automatisch geldt het tegenovergestelde wanneer er meer fouten worden gemaakt. In de volgende paragrafen worden de experimenten omschreven. De experimenten zijn gekoppeld aan de eerder genoemde hypothesen. 3.3.1. Experiment: Normalisatie in lengte Verwoorden dat: Bij wijze van serendipiteit is de rationale achter dit experiment gevonden in de experimentele fase. Tijdens deze fase viel het op dat de dissimilarity toeneemt naar mate de bestandsgrootte toeneemt.

Voor hypothese twee zijn er twee soorten normalisatie experimenten bedacht, te weten: normalisatie door inkorting en normalisatie door aanvulling. Bij normalisatie door inkorting worden alle berichten van een berichtenverzameling afgekapt tot de lengte van het kortste bericht uit de verzameling. Hoewel dit aandoet als een naïeve methode, hoeft het effect bij voorbaat zeker niet afgedaan te worden als ‘slecht’, immers wordt door professionele schrijvers zeer concreet geschreven en mogen we bij informatieve berichten als nieuwsberichten verwachten dat een groot deel van de essentie bevat is in de eerste alinea’s van een tekst. Bij normalisatie door aanvulling vullen we alle berichten uit de verzameling aan met zichzelf, tot de lengte van het langste bericht is bereikt. In tegenstelling tot de eerder genoemde methode verliezen we hier geen informatie. Onbekend is echter wat het effect zal zijn op de NCD. Het zou immers goed mogelijk kunnen zijn dat deze actie net zo goed weer ongedaan wordt door de compressor (immers brengen we redundantie aan). Een derde vorm van lengte normalisatie is het bijproduct van het volgend experiment, waarbij door het verwijderen van de Y% meest veel voorkomende woorden het lengte verschil steeds verder gereduceerd zal worden. TODO: Aantonen dat dit zo is. 3.3.2. Experiment: Verwijdering van veel voorkomende woorden TODO: Ook nog ergens beschrijven hoe ze bepaald worden. TODO: Beschrijving van het experiment verijwderen van de % meest voorkomende woorden. Waarbij de meest voorkomende woorden bepaald worden over de gehele corpus. De derde hypothese berust op het idee dat de essentie van het bericht niet bevat is in de meest veel voorkomende woorden. Zoals tevens in (verwijzing) aangetoond wordt speelt tot 80% een minder significante rol in de essentie van het bericht. 3.3.3. Experiment: Alfabetische sortering van de woorden. Met de gedachte dat een standaard compressor de redundantie uit een tekst haalt, maken we door het sorteren van de woorden, het de compressor een stuk gemakkelijker om zijn taak uit te voeren. Daarnaast zal de compressie van twee berichten samen leiden tot een kleinere bestandsgrootte indien twee berichten over hetzelfde gaan, een hogere similarity dus. De gedachte is echter dat we door het sorteren wel de context zullen ‘verwijderen’, maar omdat in (Verwijzing) is aangetoond dat de woordvolgorde niet perse essentieel is voor het begrijpen van een passage, hebben we een uitstekend excuus. Daarnaast is het tenslotte niet noodzakelijk dat de berichten nog uitgepakt hoeven te worden na berekening van de similarity. 3.3.4. Experiment: combinaties van eerder genoemde experimenten Omdat alle experimenten geautomatiseerd worden (er wordt een applicatie geschreven die het experiment kan uitvoeren), kan er vervoglens ook gemakkelijk gecombineerd worden. Omdat we hierdoor relatief snel nieuwe experimenten uit kunnen voeren, zal tevens een aantal combinaties

uitgeprobeerd wordt, waarvan enigsinds verwacht kan worden dat deze resultaat zouden kunnen brengen. Dit zijn de volgende combinaties. NCD run removal of frequent keywords, then sort, then truncate NCD run Order by Frequency, Truncate to minimum Beschrijven: Tevens zal het experiment van uit (Ana Granados, Camacho, & Rodr´ıguez, 2008) herhaald worden waarbij een beter resultaat behaald werd door 80-90% van de meest voorkomende woorden te vervangen door strings bestaande uit het karakter *.

3.4.

Beschrijving Corpus

Het uitvoeren van de genoemde experimenten vergt de beschikking van een testset aan nieuwsberichten. Deze testset, of synchrone corpus is samengesteld door alle volledige nieuwsberichten van de maand Januari 2009 uit de database van het NRC handelsblad te nemen (NRC Handelsblad, 2009). Onder volledig wordt verstaan dat een bericht tenminste beschikt over een titel, introductie en body waardoor berichten als korte headlines buiten beschouwing blijven. De synchrone corpus bevat 1322 berichten met een lengte variërend van 620 karakters tot 29414 karakters met een gemiddelde lengte van 5657. Daarnaast is van alle berichten de sectie aangegeven (sport, binnenland e.d.) en zijn de berichten indien van toepassing geclassificeerd door handmatig tagging toe te passen op een of meerdere van de volgende rubrieken: Trefwoord, Geografie, Persoon, Organisatie (NRC Handelsblad, 2009). De gehele corpus kan niet worden bijgevoegd daar ter verkrijging van de nieuwsberichten een abonnement op het NRC is vereist.

3.5. Beschrijving verificatieset en referentiecluster Todo: herschrijven, checkup. Juist omdat de definitie van ‘gerelateerd zijn’ zo mogelijk aan te geven is, is er bij de totstandkoming van de referentieset extra aandacht besteed om te zorgen dat er zoveel mogelijk verschillende groepjes berichten zijn, waarvoor geldt dat de berichten in de groepjes onderling zoveel mogelijk overeenkomsten in classificatie hebben tegenover geen of zo weinig mogelijk overeenkomsten met berichten uit de andere groepen. Verwijderen?:Om dit te verwezenlijken is gebruik gemaakt van de door het NRC reeds toegepaste classificatie om te zorgen dat berichten binnen hetzelfde cluster ook dezelfde classificatie delen. Daarnaast is deze classifcatie ook gebruikt om er voor te zorgen dat de verschillende clusters onderling daadwerkelijk verschillen in classificering. Tevens is de verificatieset bevestigd door enkele lezers van de berichten, die gegeven de set berichten in willekeurige volgorde de vraag is gesteld deze te groeperen op basis van relevantie (Gebruikerenquetesvalidatiemodel).

Het bleek te zijn dat de door de lezers samengestelde groepen identiek waren aan de groepering op basis van de door het NRC toegepaste classificatie. We kunnen hierdoor stellen dat het referentiemodel betrouwbaar is.

Het uiteindelijke referentiecluster is als volgt (zie ook voor een vergrootte versie): Cluster 1: (6770) Geldnet haalde wietwinst Checkpoint wekelijks op (6804) Skiën op wiet Cluster 2: (5732) Meer geweld en andere scenario's (5733) Niemand staat boven de wet, ook Omar alBashir niet Cluster 3: (6415) Verhoging van AOW-leeftijd is niet eerlijk (6416) Hogere leeftijd onvermijdelijk (4708) Haast met nationaal reddingsplan Cluster 4: (6839) Scepsis India over plan Obama (6842) Obama is niet ambitieus genoeg over Afghanistan Cluster 5: (4431) Duitsers hebben felle kritiek op 'hun' paus (4494) Merkel roept paus ter verantwoording Figure 1. Referentiecluster .

De inhoud van deze artikelen kan aangevraagd worden bij de auteur of online geraadpleegd worden op de website van het NRC (Bijlage 1). Todo: overwegen gehele berichten uit het cluster bij te voegen

3.6.

Beschrijving validiatiemethode

3.6.1. Meten van clusterfouten of ‘clustering error’ Het aantal clusterfouten wordt bepaald door voor alle paren uit een referentiecluster de afstand tussen de berichten te meten en deze bij elkaar op te tellen. De afstand is hierbij gedefinieerd als het aantal nodes (non leaf nodes) tussen de twee berichten. Het aantal clusterfouten, of ‘clustering error’ in Engelstalige literatuur (Ana Granados, Camacho, & Rodr´ıguez, 2008) kan vervolgens worden gebruikt als nulpunt voor een vergelijking met andere gemaakte clusters waarbij een hoger aantal clusterfouten aangeeft dat er clusters zijn gebroken en berichten dus verkeerd geplaatst zijn.

Als voorbeeld heeft de referentieset in (verwijzing) een aantal clusterfouten van 9. De set bestaat uit 5 clusters welke respectievelijk voor 1, 1, 5, 1 en 1 fouten bijdragen aan het totaal. 3.6.2. Incrementele uitbreiding referentiemodel TODO: beschrijven en invullen. Omdat (vooruitlopend op de resultaten in verwijzing) zal blijken dat de methode instaat is om gegeven de referentieset de exacte clustering kan namaken, zal het referentiemodel incrementeel worden uitgebreid tot op het punt er fouten ontstaan, of dat aanmelijk gemaakt is dat de methode zeer stabiel werkt. Doel: Incrementeel opbouw van het referentiemodel door ongerelateerde berichten toe te voegen. Hopende dat er op den duur foute clusters ontstaan. In deze foute clusters kan vervolgens gezocht worden naar verbetering door te gaan spelen met de variabelen. (conditioneren). Nadeel: Het validatiemodel zal iedere keer aangepast moeten worden om goed te kunnen meten of er fouten optreden. Immers kun je theoretisch een node toevoegen aan een cluster zonder de clustering error aan te passen. Het is daarom ook van belang dat alle nodes worden beschouwd bij deze berekening. Het toevoegen van één enkele node is hierdoor ook risicovol.

4. Achtergrond en Context Hierin staat wat je moet weten om mijn probleem te kunnen plaatsen. De informatie in dit hoofdstuk heb ik bijeengesprokkeld tijdens mijn literatuuronderzoek. Ik verwijs hier ook naar allerlei bronnen bij voorbeeld naar boeken die ik tijdens mijn opleiding of tijdens de literatuurstudie voor de stage heb bestudeerd. Hier is een voorbeeld: [?]. Kijk ook eens naar hoofdstuk 2 van deze scriptie: http://homepages.cwi.nl/~paulk/thesesMasterSoftwareEngineering/2006/RichardKettelerij.pdf. 8

4.1.

Begripvorming

Voordat we verder gaan met het onderzoek naar de geschiktheid van de “normalized compression distance” voor het aan elkaar relateren van nieuwsberichten is het van belang om eerst een helder begrip te vormen van de methoden en de achterliggende theorie. Kolmogorov complexity. Essentieel gezien is de (unconditional) Kolmogorov Complexity van een eindige binaire reeks x, de lengte van de ultieme ingepakte versie van x. Formeel is de Kolmogorov Complexity, de lengte van het kortste binaire programma om x vast te stellen middels een universele Turing Machine. De conditional Kolmogorov Complexity , is de lente van het kortste programma welke gegeven y, x kan vaststellen (Li, Chen, Li, Ma, & Vitányi, DECEMBER 2004). Het probleem van de Kolmogorov complexity is echter dat deze niet te berekenen valt, thans niet in de zin van een universele Ruring machine. Wel is er de mogelijkheid om de Kolmogorov complexity te benaderen door gebruik te maken van real-world compressors zoals Gzip of Bzip (Cilibrasi & Vitanyi, Clustering by Compression, JANUARY 2005). Verwijderen: Informally, K(x) measures the information content, degree of redundancy, degree of structure, of x (http://neilconway.org/talks/kolmogorov.pdf) Formally, the information distance is the length E(x,y) of a shortest binary program that computes x from y as wel as computing y from x. (the similarity metric)

Normalized Information De information distance is de lengte van het korste binaire programma, welk x kan transformeren tot y en vice versa. y kan transformeren tot x en is gedefinieerd als . (Li & Vitányi, Theory of Thermodynamics of Computation, Oct. 4-6, 1992) Normalized Information Distance. Gedefinieerd als

drukt de Normalized Information Distance (NID) de

genormaliseerde informatieafstand uit, of wel de lengte van het kortste binaire Universele Prefix Turing Machine programma welke x kan transformeren tot y en vice versa. De NID is een metriek waarin alle afzonderlijke gelijkenissen (similarities) tussen de twee objecten worden vastgelegd en waarbij de overheersende feature bepalend is. (Li, Chen, Li, Ma, & Vitányi, DECEMBER 2004)

Omdat de Normalized Information Distance gebruik maakt van de Kolmogorov Copmlexity, is deze dus wederom niet uit te rekenen. Door nu gebruik te maken van real-world compressors kan dit probleem worden overwonnen en de NID worden benaderd. Normalized Compression Distance. Gegeven een compressor C, waarvoor geldt dat deze normal is (zie (Cilibrasi & Vitanyi, Similarity of Objects and the Meaning of Words, 2006)), wordt voor deze benadering de NID omgeschreven tot:

waarbij en de lengtes zijn van de gecomprimeerde versies van x en y, en de lengte is van de gecomprimeerde versie van x en y samen. Het mag hierbij duidelijk zijn dat de NCD lang niet zo’n zuiver resultaat geeft als de NID in theorie zal geven, maar aangezien de NID niet te berekenen valt is dat iets wat we graag voor lief nemen.

Quartet Method tbv clustering Todo: beschrijven Uit clustering by compression: “Our aim is to analyze data sets for which the number of clusters is not known a priori, and the data are not labeled.” “Hierarchical clustering is among the best known unsupervised methos in this setting, and the most natural way is to represent the relations in the form of a dendrogram, which is customarily a directed binary tree or undirected ternary tree”.

4.2.

Eerdere succesvolle implementaties NCD

Todo: Een aantal cases kort presenteren.

4.3.

Relevant onderzoek

Compressor keuze. Aangezien de NCD methode gebruik maakt van compressors, is het aannemelijk dat we een aantal voorwaarden moeten stellen voor het gebruik van de NCD methode. In (CEBRI´AN, ALFONSECA, & ORTEGA, 2005) hebben de auteurs onderzocht in welke mate van precisie geldt waarbij ze tot de conclusie zijn gekomen dat de NCD methode, afhankelijk van de gekozen compressor beperkt is in objectgrootte. Ze hebben aangetoond dat voor het gebruik binnen de NCD methode er voor de compressiemethoden gzip, bzip2 (fast), bzip2 (best) en ppmz er een maximale objectgrootte geldt van respectievelijk 32, 50, 450 en ∞ kb waarbij met een overschrijding van deze grens de dissimilarity snel toeneemt. Daarnaast laten ze zien dat de methoden bzip2, gzip en ppmz opeenvolgend het beste benaderen voor .

Samenvattend is de ppmz compressor dus het aantrekkelijkst om te gebruiken; geen maximale objectgrootte, de beste compressieratio (CEBRI´AN, ALFONSECA, & ORTEGA, 2005) en het meest nauwkeurig bij NCD(x,y) = 0 voor toenemende bestandsgrootte. Echter, gezien de doorlooptijd van PPMZ4 tot wel 4x langer is gebleken in vergelijking met GZIP5 (Jonker, R01 - Runtime vergelijking GZIP en PPMZ2, 2009) is toch gekozen om GZIP als standaard compressor te nemen (NB. Dat de objectgroten uit de gekozen testset / corpus voor het grootste deel onder de maximale objectgroote van de GZIP methode blijft). De invloed van ruis op de NCD. In het artikel (Ana Granados, Camacho, & Rodr´ıguez, 2008) is de invloed van ruis op de NCD bestudeerd. Met de gedeelde motivatie uit (Verwijzing) dat , introduceerden de auteurs ruis door karakters te substitueren. Hun bevindingen zijn hierbij dat wanneer de substitutie wordt toegepast met willekeurige karakters, de documenten complexer worden in tegenstelling tot substitutie met een constant karakter waarbij de documenten in complexiteit dalen. Tevens laten ze zien dat het substitueren van de minst voorkomende woorden zorgt voor een toenemend aantal clusteringfouten. Bij substitutie van de meest voorkomende woorden blijft het aantal fouten echter stabiel en heeft zelfs een positief effect op de clustering bij een substitutie van de 80% tot 90% van de meest voorkomende woorden. Dit betekent dat we hiermee de non relevante delen van de tekst weghalen en het zo gemakkelijker maken om betrouwbare similarities te vinden. De les die wij hieruit kunnen halen is dat door de veelvoorkomende woorden te verwijderen, tenminste een net zo goed, of zelfs beter resultaat behaald kan worden, dan deze actie uit te voeren.

Bevindingen uit: Woord volgorde maakt niet uit artikel. Hoeveel betekenis kan men uit een passage halen, zonder de oorspronkelijke woordvolgorde te beschouwen? Uit een verkennend onderzoek van (Landauer, Laham, Rehder, & Schreiner, 1997) blijkt dat de woordvolgorde er niet eens zoveel toe doet. Binnen hun onderzoek hebben ze mensen gevraagd korte essays te beoordelen op de kwaliteit en hoeveelheid overgebrachte informatie over een bepaald wetenschappelijk onderwerp. Deze beoordelingen zijn vervolgens vergeleken met de uitkomst van een statistisch model waarbij geen rekening gehouden wordt met de woordvolgorde. Bij hun experimenten laten ze „mensen‟ het werk van studenten beoordelen Natuurlijk mag het duidelijk zijn dat Bevindingen uit: Heuristiek vergelijking keyword extractie. Todo: wellicht kan ik hier nog motiveren waarom ik gekozen heb voor de keyword extractie methode. 4 5

Implementatie op basis van PPMZ2 v0.81 (Bloom, 2004). Implementatie op basis van SharpZipLib v0.85.5 (IC#Code, 2008).

4.4.

Observaties uit voorstudie

Observaties uit de eerste NCD experimenten. De NCD wordt beïnvloed door de objectgrootte. Naar aanleiding van her artikel (CEBRI´AN, ALFONSECA, & ORTEGA, 2005) waarin geconcludeerd werd dat de betrouwbaarheid van de NCD drastisch verminderd na een bepaalde objectgrootte, was het de vraag of we deze vermindering in betrouwbaarheid ook al eerder kunnen waarnemen. Uit een simpel experiment waarbij de functie wordt uitgevoerd op het groter wordende object is dan ook gebleken dat de bestandsgrootte een zekere negatieve invloed heeft op de bestandsgrootte (Jonker, R02 - De invloed van de objectgrootte op de NCD, 2009). Deze observatie samen met het fijt dat een verschil in bestandsgrootte per definitie zorgt voor een toenemende dissimilarity dient als motivatie om extra aandacht te besteden aan de lengte van de berichten. (Verwijzing hypothesen?)

5. Onderzoek

5.1.

Vergelijking standaard implementatie met het referentiecluster

Het uitvoeren van de clusteringmethode op basis van de, resulteert in de onderstaande clustering. De gebruikte compressor is de standaard complearn processor.

Figure 2. Resulterend cluster op basis van de referentieset. (Links: C=Complearn, rechts: C=Gzip)

Zoals op het oog vergeleken kan worden, betreft het hier een identieke clustering t.o.v. het referentiecluster. Dit wordt bevestigd door het aantal clusterfouten met elkaar te vergelijken. Met een

clusterfout aantal van 9 bevestigd dit er inderdaad geen extra fouten gemaakt worden en het cluster dus identiek is.

5.2.

Op zoek naar fouten

Zoals in de onderzoeksmethode werd omschreven, zal in het geval van een foutloze uitkomst getracht worden de clustering gebroken proberen te worden door nieuwe ongerelateerde clusters toe te voegen tot op het moment dat de clustering gebroken wordt (Het resulterende foutenaantal is groter dan het bepaalde foutenaantal). Er is hier gekozen om telkens groepen van 2 gerelateerde berichten toe te voegen. Op deze wijze kan de plaatsing van de toegevoegde berichten meegenomen worden in de fouten telling, waarbij anders (bij de toevoeging van één enkel bericht) niks gezegd kan worden over het effect van het toegevoegde berichte wanneer deze ‘bij’ een ander cluster geplaatst wordt. Voor de toegevoegde clusters geldt verder dat deze geen enkele classificatieovereenkomst hebben ten opzichte van de reeds toegevoegde clusters en dan de berichten onderling zo veel als mogelijk overeenkomsten in classificatie hebben. 5.2.1. Iteratieve uitbreiding van de verificatieset Als eerste worden er twee berichten toegevoegd die beide betrekking hebben op de dubieuze voorzitter Möllenkamp van woningcorporatie Rochdale. Met deze toevoeging komt het berichtenaantal in de verificatieset op 14, vormt het referentiecluster 6 clusters met een Total aantal clusterfouten van 10.

P1

P4426 'Möllenkamp loog over Maserati' P4588 Koning Möllenkamp regelde alles zelf

Aantal clusterfouten Complearn: 10 GZIP: 10 PPMZ: 10

Figure 3. Effect van clustering door toevoeging cluster P1 aan het referentiemodel.

Na toevoeging blijkt de methode wederom instaat het aantal clusterfouten te evenaren t.o.v. het met het cluster P1 verrijkte referentiemodel. Een volgende toevoeging betreft twee berichten betreffende het crèchedrama in Dendermonde en verslaggeving door de media. Met deze toevoeging aan de verificatieset bestaat het referentiecluster uit 7 clusters met een totaal aantal clusterfouten van 11. Aantal clusterfouten P4490 Crèchedrama als mediaspiegel Complearn: 11 P2 P4498 Media sloegen op hol bij babymoordenaar GZIP: 11 PPMZ: 11 Figure 4. Effect van clustering door toevoeging cluster P2 aan het referentiemodel.

Wederom valt te zien dat de methode er perfect in geslaagd is alle berichten te clusteren zoals gewenst is volgens het referentiecluster. Een volgende toevoeging betreft twee berichten met betrekking op de Zweedse overname van de Nuon. Met deze toevoeging aan de verificatieset zal het referentiecluster bestaan uit 7 clusters met een totaal aantal clusterfouten van 12.

P3

p5458 Fijn, daar komen de Zweden aan p6020 Investeer meer in groene infrastructuur

Aantal clusterfouten Complearn: 27 GZIP: 41 PPMZ: 30

Figure 5. Effect van clustering door toevoeging van cluster P3 aan het referentiemodel.

Dit keer wijkt het aantal clusterfouten af van het aantal clusterfouten in het referentiemodel, deze fouten worden in de volgende paragraaf verder bekeken. Artikelen referentiecluster +p1,p2,p3.rar

5.2.2. Verklaring van de fouten Het valt op dat de Complearn compressor beter heeft gepresteerd dan de andere compressors(Tabel verwijzing ), thans de Complearn compressor maakt in 3 clusters fouten tegenover 4 clusters bij de GZIP en PPMZ compressors.

Complearn

GZIP

PPMZ

Ref.6

Cluster 1 Cluster 2 Cluster 3

1 1 15

5 1 19

5 1 11

1 1 5

Cluster 4 Cluster 5 Cluster P1

1 1 1

1 1 4

1 1 4

1 1 1

Cluster P2 Cluster P3 Totaal

1 6 27

1 9 41

1 6 30

1 1 12

Table 1. Aantal clusterfouten verificatieset + {P1,P2,P3}

Results.rar

7

<- alle 3 de plaatjes toevoegen.

Figure 6. Resulterende clustering voor verificatieset + P1,P2,P3; C=GZIP

Wanneer we het resulterende cluster (zie figuur) nog eens goed bekijken en vergelijken met het referentiecluster (verwijzing bijlage ref cluster+123), dan zien we dat in het geval van de GZIP compressie: a. De berichten p6020 en 4708 samen een cluster vormen en daardoor de clusters 3 en P3 verbreken. b. De berichten p4588 en 6804 samen een cluster vormen en daardoor de clusters 1 en P1 verbreken. c. De berichten P5458, 6416, 6770, p4426 en 6415 een cluster vormen en daardoor de clusters 1,3,P1 en P3 verbreken. Opvallend is dat de fout genoemd in a ook gemaakt worden in de overige compressors. Daarnaast wordt de in b genoemde fout gedeeld met de PPMZ variant. En wordt de in c gemaakte fout in mindere mate gemaakt bij gebruik van de PPMZ compressor, waar de berichten 6770, 6416 en p5458 als fout cluster worden.

5.3.

Opzoek naar verbeteringen

Nu gebleken is dat de methode niet foutloos zijn werk doet, zal opzoek gegaan moeten worden naar verbeteringen. Deze verbeteringen worden gezocht in de vorm van preprocessing waar de nieuwsberichten worden aangepast waarna de Normalized Compression Distance wordt toegepast.

6

Het referentiecluster is gegeven in (Bijlage verwijzing.) De clusternummering komt overeen met de nummering zoals gegeven in het referentiecluster(verwijzing) en de nummering van de toegevoegde clusters in (verwijzing). 7

De volgende subparagrafen presenteren de resultaten van de eerder (hoofdstuk verwijzing) genoemde experimenten. Deze experimenten hebben als doel de gemaakte fouten te neutraliseren om zo proefondervindelijk te bewijzen of te falsificeren welke van de methoden bijdragen aan een beter resultaat. 5.3.1. Resultaten lengte normalisatie 5.3.1.1. Origineel

Normalisatie door opvulling Na experiment Complearn

GZIP

PPMZ

Ref.

Cluster 1 Cluster 2 Cluster 3

1 1 15

5 1 19

5 1 11

1 1 5

Cluster 4 Cluster 5 Cluster P1 Cluster P2 Cluster P3 Totaal

1 1 1 1 6 27

1 1 4 1 9 41

1 1 4 1 6 30

1 1 1 1 1 12

Complearn

GZIP

PPMZ

Ref.

Cluster 1 Cluster 2 Cluster 3

5 1 15

5 1 19

5 1 11

1 1 5

Cluster 4 Cluster 5 Cluster P1 Cluster P2 Cluster P3 Totaal

1 1 4 1 7 35

1 1 4 1 9 41

1 1 4 1 6 30

1 1 1 1 1 12

Complearn

GZIP

PPMZ

Ref.

normalisatie door opvulling.rar

5.3.1.2. Origineel

Normalisatie door afkapping Na experiment Complearn

GZIP

PPMZ

Ref.

Cluster 1

1

5

5

1

Cluster 1

1

5

5

1

Cluster 2

1

1

1

1

Cluster 2

1

1

1

1

Cluster 3 Cluster 4

15 1

19 1

11 1

5 1

Cluster 3 Cluster 4

15 1

19 1

11 1

5 1

Cluster 5

1

1

1

1

Cluster 5

1

1

1

1

Cluster P1 Cluster P2

1 1

4 1

4 1

1 1

Cluster P1 Cluster P2

1 1

4 1

4 1

1 1

Cluster P3 Totaal

6 27

9 41

6 30

1 12

Cluster P3 Totaal

6 27

9 41

6 30

1 12

5.3.2. Resultaten verwijdering van vele voorkomende woorden

Aantal juiste clusters

Aantal foutloze clusters 10 8 6 4 2 0

0

5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 99

8

8

8

8

8

8

8

8

8

8

8

8

8

8

8

8

8

8

8

8

8

Complearn 6

6

6

6

6

6

6

6

6

6

6

6

8

8

5

6

4

5

5

3

5

GZIP

5

4

6

6

6

6

6

6

5

5

5

5

8

8

5

6

4

4

4

3

4

PPMZ

4

4

4

5

5

5

5

5

7

6

5

8

8

6

6

6

4

4

5

1

3

Max.

Aantal clusterfouten Aantal fouten

60 50 40 30 20 10 0 Min.

0

5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 99

12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12

Complearn 27 27 21 27 27 27 18 21 21 22 27 19 12 12 23 20 41 24 29 41 34 Gzip

31 35 27 27 27 27 27 27 25 26 31 25 12 12 23 22 41 41 41 47 42

PPMZ

29 29 30 25 25 25 25 25 14 18 25 12 12 20 20 23 33 37 26 53 57

Bestandsgrootte 25000 20000 15000 10000

5000

0% 1% 5% 10% 15% 20% 25% 30% 35% 40% 45% 50% 55% 60% 65% 70% 75% 80% 85% 90% 95% 100%

0

Bijschrijft toevoegen: Bestandsgrootte van alle berichten convergeren naar elkaar. 4500

Bericht grotte (bytes)

4000 3500 3000 2500 2000

1500 1000 500

0% 1% 5% 10% 15% 20% 25% 30% 35% 40% 45% 50% 55% 60% 65% 70% 75% 80% 85% 90% 95% 100%

0

Bijschrift toevoegen: Verschil tussen alle bestanden wordt gemiddeld genomen steeds kleiner.

5.3.3. Resultaten alfabetische sortering van de woorden Origineel NA sortering Cluster 1

Complearn

GZIP

PPMZ

Ref.

1

5

5

1

Cluster 1

Complearn

GZIP

PPMZ

Ref.

7

7

9

1

Cluster 2 Cluster 3 Cluster 4 Cluster 5

1 15 1 1

1 19 1 1

1 11 1 1

1 5 1 1

Cluster 2 Cluster 3 Cluster 4 Cluster 5

1 13 1 1

1 13 1 1

1 17 1 5

1 5 1 1

Cluster P1 Cluster P2 Cluster P3

1 1 6

4 1 9

4 1 6

1 1 1

Cluster P1 Cluster P2 Cluster P3

5 1 5

5 1 9

8 1 7

1 1 1

Totaal

27

41

30

12

Totaal

34

34

49

12

Complearn

GZIP

PPMZ

Ref.

5.3.4. Resultaten overige experimenten 5.3.4.1.

Order by Frequency, truncate Complearn

GZIP

PPMZ

Ref.

Cluster 1 Cluster 2 Cluster 3 Cluster 4

1 1 15 1

5 1 19 1

5 1 11 1

1 1 5 1

Cluster 1 Cluster 2 Cluster 3 Cluster 4

7 1 13 1

5 1 19 1

5 1 11 1

1 1 5 1

Cluster 5 Cluster P1 Cluster P2

1 1 1

1 4 1

1 4 1

1 1 1

Cluster 5 Cluster P1 Cluster P2

1 1 1

1 4 1

1 4 1

1 1 1

Cluster P3 Totaal

6 27

9 41

6 30

1 12

Cluster P3 Totaal

6 33

9 33

6 48

1 12

5.3.4.2.

% removal, Sort, truncate

Remove, Sort and truncate Aantal fouten

30 25 20 15 10 5 0 ref

0 1 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95100

12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12

complearn 16 16 16 14 14 14 12 12 12 12 12 12 12 12 12 17 19 22 20 22 27 26

gzip

16 16 16 14 14 14 12 12 12 12 12 12 12 12 17 12 19 23 20 22 27 27

ppmz

14 14 14 12 12 16 14 14 17 18 14 20 17 17 16 17 20 24 27 26 25 28

5.3.4.3.

Karaktersubstitutie van meest voorkomende woorden door *

Aantal correcte clusters 9 8 7 6 5 4 3 2 1 0 Max.

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 99

8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8

Complearn 5 5 4 5 5 5 5 5 5 5 5 6 6 5 5 5 5 5 5 5 5 GZIP

4 4 4 4 4 5 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5

PPMZ

4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 4 4 4 4 4

Aantal clusterfouten 45 40 35 30 25 20 15 10 5 0 Min.

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 99 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12

Complearn 31 31 36 31 31 28 31 34 31 31 25 18 18 23 25 25 25 25 25 25 25

GZIP

41 41 41 41 41 31 41 41 36 36 31 31 31 25 25 25 25 31 31 31 31

PPMZ

29 29 33 33 38 38 38 38 38 33 33 23 23 23 23 23 30 30 34 38 38

6. Resultaten Onderstaande is allemaal scratch. Interpretaties en semi conclusies Neutrale inzet normalized comprssion distance. De Normalized Compession Distance blijkt een heel eind in de goede richting te komen wanneer we hem proberen in te zetten om de berichten op inhoud te clusteren. Gegeven de referentie set uit (verwijzing) was de methode instaat dezelfde clusters samen te stellen als het geval was in het bijbehorende referentiecluster. Na toevoeging van extra berichten aan de referentieset begon de methode echter fouten te maken. Geconcludeerd mag dan ook worden dat de Normalized Compression Distance in zijn neutrale vorm niet geschikt is om volledig foutloos relevante berichten aan te dragen. Hypothese lengte normalisatie. Aangezien bekend – en geobserveerd was dat de lengte van de berichten de normalized compression distance beïnvloedden zijn er twee experimenten verzonnen om daar wat aan te doen. Hoewel er niet veel van verwacht werd, was het onduidelijk wat het effect zou zijn. Het blijkt dat beide experimenten geen positief invloed hebben gehad op het eindresultaat, sterker nog valt te observeren dat beide methoden het zelfde of net iets slechter presteerden als de neutrale inzet. Bij de normalisatie door opvulling was dit te verwachten, immers brengen we redundantie aan die door een compressor net zo gemakkelijk weer geneutraliseerd wordt (het doel van een compressor is immers het verwijderen van receptiviteit). Bij het afkappen van de berichten is het rsultaat echter stukken verwonderlijker daar gezien de samenstelling van de referentieset ontzettend veel informatie verloren gaat. Dit leert ons dat, klaarblijkelijk de essentie van het bericht bevat is in het eerste deel, tenslotte wordt het resultaat niet beter of slechter waaruit blijkt dat het latere deel van het bericht weinig of niets bijdraagd aan het resultaat. Resultaten verwijderen van veel voorkomende woorden. Bij het verwijderen van de meest veel voorkomende woorden, zien we dat de PPMZ compressor gemiddeld het minste aantal correcte clusters kan reproduceren tegenover de standaard complearn compressor. Te observeren valt dat de prestaties van de compressors tot 50% verwijdering van de meest voorkomende woorden redelijk stabiel blijft, maar daarna kort piekt tot optimale resultaten en na de 65% in resultaat afneemt. Er is dus aangetoond dat, gegeven deze referentieset de methode wel het gewenste optimale resultaat behaald wanneer we 55-65% van de meest voorkomende woorden verwijderen, afhankelijk van de gebruikte compressor. Alfabetische sortering van woorden De alfabetische sortering van woorden, presteert in tegenstelling tot de verwachting slechter dan de oorspronkelijke methode. Op het gebruik van de GZIP compressor na, worden er minder juiste clusters samengesteld en is het aantal clusterfouten hoger. (Wat betekent dit?)

7. Conclusie Conclusie opnieuw schrijven. Interessante passage om miss nog te verwerken in de conclusie: Passage uit “clustering by compression”: “With the natural data sets we use, one may have the preconception (or prejudice) that, say, music by Bach should be clustered together, music by Chopin should be clustered together, and so should music by rock stars. However the preprocessed music files of a piece by Bach and a piece by Chopin, or the Beatles, may resemble one another more than two different pieces by Bach – by accident or indeed by design and copying. Th8us, natural data sets may have ambiguous, conflicting, or counterintuitive outcomes. Ion other words, the experiments on natural data sets have the drawback of not having an objective clear “correct” answer that can function as a benchmark for assessing our experimental outcomes, vbut only intuitive or traditional preconceptions”.

Further research - Andere cluster methoden. o http://www.let.rug.nl/~kleiweg/clustering/clustering.html < voorbeelden - Support Vector Machiens voor supervised learning.

Bibliography Ana Granados, M. C., Camacho, D., & Rodr´ıguez, F. B. (2008). Evaluating the Impact of Information Distortion on Normalized Compression Distance. ICMCTA, LNCS 5228 , 69–79. Bloom, C. (2004, Mei 09). High Compression Markov Predictive Coder . Retrieved Juli 14, 2009, from CBLOOM.COM: http://www.cbloom.com/src/ppmz.html CEBRI´AN, M., ALFONSECA, M., & ORTEGA, A. (2005). COMMON PITFALLS USING THE NORMALIZED COMPRESSION DISTANCE: WHAT TO WATCH OUT FOR IN A COMPRESSOR. COMMUNICATIONS IN INFORMATION AND SYSTEMS , Vol. 5, No. 4, pp. 367-384,. Cilibrasi, R., & Vitanyi, P. (Volume 51). Clustering by Compression. IEEE Transactions on Information Theory , p1523 - 1545. Cilibrasi, R., & Vitanyi, P. (2006). Similarity of Objects and the Meaning of Words. ArXiv Computer Science e-prints . IC#Code. (2008, November 8). .NET Zip Library #ziplib (SharpZipLib). Retrieved Juli 14, 2009, from ic#code: http://www.icsharpcode.net/OpenSource/SharpZipLib/Download.aspx Jonker, I. (2009). R01 - Runtime vergelijking GZIP en PPMZ2. Rijswijk. Jonker, I. (2009). R02 - De invloed van de objectgrootte op de NCD. Rijswijk. Landauer, T. K., Laham, D., Rehder, B., & Schreiner, M. E. (1997). How Well Can Passage Meaning be Derived without Using Word Order? A Comparison of Latent Semantic Analysis and Humans. Boulder: University of Colorado. Li, M., & Vitányi, P. (Oct. 4-6, 1992). Theory of Thermodynamics of Computation. Proc. IEEE Physics of Computation Workshop , p42 - 46. . Li, M., Chen, X., Li, X., Ma, B., & Vitányi, P. M. (VOL. 50, NO. 12, DECEMBER 2004). The Similarity Metric. IEEE TRANSACTIONS ON INFORMATION THEORY , p3250 - 3264. NRC Handelsblad. (2009, Juni 27). Digitaal Krantenarchief. Retrieved Juni 27, 2009, from NRC.nl: http://archief.nrc.nl/?modus=a

Bijlage 1.

Overzicht artikelen uit referentiemodel

Onderstaande tabel betreft een overzicht van alle artikelen gebruikt in het referentiemodel alsmede het webadres waar deze verkregen kan worden. Om de berichten digitaal in te zien, zal men moeten beschikken over een webabonnement bij het NRC.

1

2

3

4

5

P1

P2

P3

6770 Geldnet haalde wietwinst Checkpoint wekelijks op http://archief.nrc.nl/index.php/2009/Maart/28/Voorpagina/01/Geldnet+haalde+wietwinst+Checkpoint+we kelijks+op 6804 Ski?n op wiet http://archief.nrc.nl/index.php/2009/Maart/28/Overig/Z06/Ski%EBn+op+++wiet 5732 Meer geweld en andere scenario?s http://archief.nrc.nl/index.php/2009/Maart/5/Buitenland/05/Meer+geweld+en++andere+scenario%3Fs 5733 Niemand staat boven de wet, ook Omar al-Bashir niet http://archief.nrc.nl/index.php/2009/Maart/5/Buitenland/05/Niemand+staat+boven+de+wet%2C+ook+Om ar+al-Bashir+niet 6415 Verhoging van AOW-leeftijd is niet eerlijk http://archief.nrc.nl/index.php/2009/Maart/20/Overig/07/Verhoging+van+AOW-leeftijd+is+niet+eerlijk 6416 Hogere leeftijd onvermijdelijk http://archief.nrc.nl/index.php/2009/Maart/20/Overig/07/Hogere+leeftijd+onvermijdelijk 4708 Haast met nationaal reddingsplan http://archief.nrc.nl/index.php/2009/Februari/9/Economie/09/Haast+met+nationaal+reddingsplan 6839 Scepsis India over plan Obama http://archief.nrc.nl/index.php/2009/Maart/30/Buitenland/05/Scepsis+India+over+plan+Obama 6842 Obama is niet ambitieus genoeg over Afghanistan http://archief.nrc.nl/index.php/2009/Maart/30/Overig/07/Obama+is+niet+ambitieus+genoeg+over+Afghan istan 4431 Duitsers hebben felle kritiek op ?hun? paus http://archief.nrc.nl/index.php/2009/Februari/3/Buitenland/04/Duitsers+hebben+felle+kritiek+op+%3Fhun %3F+paus 4494 Merkel roept paus ter verantwoording http://archief.nrc.nl/index.php/2009/Februari/4/Buitenland/05/Merkel+roept+paus+ter+verantwoording 4426 'M?llenkamp loog over Maserati' http://archief.nrc.nl/index.php/2009/Februari/3/Binnenland/02/%27M%F6llenkamp+loog+over+Maserati% 27 4588 Koning M?llenkamp regelde alles zelf http://archief.nrc.nl/index.php/2009/Februari/6/Binnenland/03/Koning+M%F6llenkamp+regelde+alles+zelf 4490 Cr?chedrama als mediaspiegel http://archief.nrc.nl/index.php/2009/Februari/4/Buitenland/04/Cr%E8chedrama+als++mediaspiegel 4498 Media sloegen op hol bij babymoordenaar http://archief.nrc.nl/index.php/2009/Februari/4/Overig/07/Media+sloegen+op+hol+bij+babymoordenaar 6020 Investeer meer in groene infrastructuur http://archief.nrc.nl/index.php/2009/Maart/11/Economie/13/Investeer+meer+in+groene+infrastructuur 5458 Fijn, daar komen de Zweden aan http://archief.nrc.nl/index.php/2009/Februari/26/Overig/07/Fijn%2C+daar+komen+de+Zweden+aan

Bijlage 2.

Grote versie referentiecluster

Grote representatie van het referentie cluster. Samengesteld op basis van de door het NRC aangebrachte classificatie en samengesteld na interpretatie van diverse lezers.

De verbindingen tussen de ‘leaf’-nodes geven aan wat het aantal overeenkomsten in classificatie is. De getallen binnen de nodes geven de unieke sleutel aan van de nieuwsberichten.

Bijlage 3.

Grote versie referentiecluster + P1,P2,P3

Onderstaand referentiecluster betreft het referentiecluster gebaseerd op de verificatieset met toevoeging van de berichten uit de sets P1,P2 en P3. De clustering is samengesteld op basis van door het NRC aangebrachte classificatie en de interpretatie van diverse lezers.

De verbindingen tussen de ‘leaf’-nodes geven aan wat het aantal overeenkomsten in classificatie is. De getallen binnen de nodes geven de unieke sleutel aan van de nieuwsberichten. Een p geeft aan dat het een toevoeging betreft ten opzichte van het originele referentiemodel.

Oude notities en rotzooi I.

II.

III.

Literatuur studie o Vraag: Hoe kun je de NCD zelf inzetten? o Bevinding uit ncd literatuur: verschil in bestandsgrootte is van invloed. o Bevinding: NCD is resistant to noise  Substitutie van 80% v/d veel voorkomende woorden door karakters * geeft een beter resultaat.  Cluster error blijft behouden. o Bevinding: Common pitfallszx  NCD(x,x) == 0 voor lengte X > oneindig wordt het best evenaart door de PPMZ compressiemethode.  GZIP haalt hier ook een vergelijkbasre score maar is beperkt tot een objectlengte van 32kbyte, bij NCD(x,y) moet len(x+y)<=32k zijn. Daar in tegen wel makkelijekr te implementeren. Ongericht Experimentele fase o Had als doel zelf een implementatie te maken van de NCD methode, los van de Complearn om te toetsen of ik de methode begrijp. o Bevindingen:  Bestanden worden minder similar naarmate de bestandsgrootte stijgt.  Naar mate bestanden groter worden convergeert het resultaat richting 1. Keuze validatiemethoden o Keuze uit (Journaal 25 mei):  Validatie op basis van een bestaande methode – vergelijken.  Validatie op basis van reeds getagde/classificeerde berichten – vergelijken.  Keuze andere data waarvan classificatie wel bekend is – vergelijken.  Mensen de gelegde relatie laten beoordelen – vergelijken. Hoewel hier initieel mee is begonnen omdat dit oorspronkelijk het plan was, is uiteindelijk gekozen voor een andere methode. Tijdens het maken van een PHP applicatie waarin de gebruiker gevraagd werd verschillende nieuwsberichten met elkaar te vergelijken werd helemaal duidelijk hoe suggestief deze methode was. Daarnaast was de enorme hoeveelheid te leggen relaties eigenlijk onbegonnen werk. o Methode:  Zoals al eerder is toegepast van “NCD is resistant to noise”.  Andere mogelijkheden afhankelijk van de gebruikte clustermethodiek. Support Vector Machiens zijn b.v. uitermategeschikt om te valideren middels crossvalidatie (ref:guide to svm)  Ultieme validatiemethode (als related(x,y) dan geen z waarvoor ncd(x,z) < ncd(x,y) en ncd(x,z)


IV.

V.

VI.

VII. VIII.

Handmatig een referentiecluster vaststellen op basis van reeds geclassificeerde berichten. Dit cluster gevalideerd door mensen zelf een cluster te laten bepalen zonder medewetenschap van de oorspronkelijke classificatie. o Rationale:  In de oorspronkelijke methode werd gebruikgemaakt van suggestieve vraagstelling. Dit maakt het onzeker. Daarnaast vergde de oude methode n²-n beoordelingen van relaties, wat teveel werk is. Andere data zoeken was geen optie, het heeft vele tijd gekost, en nieuwsberichten zijn met name interessant omdat daar het doel is de informatie over te brengen, semantiek zal dan ook zoveel mogelijk syntactisch verwoord zijn.  In plaats daarvan is op basis van classificatie een cluster vastgesteld, welke weer bevestigd is door andere mensen welke dient als validatie. Start stap o Uitvoer NCD methode zonder conditionering. o Meten van de resultaten  Cluster error meten. o Interpretatie resultaten Opzoek naar methoden om het resultaat te verbeteren (hypothesen vormen) o Mogelijkheid:  Gebruik maken van andere classificatie methoden Niet gekozen om de huidige methode zoveel mogelijk ‘uit te putten’. o Op basis van eerdere experimenten en theorie.:  Normaliseren van berichtlengte tbv verbetering resultaat Door te trunceren tot de minimum berichtlengte uit de set o Verlies van informatie. Door aan te vullen tot de maximumberichtlengt uit de set. o Behoud van informatie. o Op basis van literatuur  Verwijderen van % meest voorkomende woorden uit corpus.  Karaktersubstitutie door * van % meest voorkomende woorden uit corpus.  Sorteren van woorden (tbhv vergemakkelijking compressie) backed by: artikel : meaning derrived w/o considering the order of words. o Combinaties van allen. Uitvoeren van de verbeteringmethoden icm clustering ncd o Methode uitvoeren o Resultaat meten. o Conclusie beter/slechter – evt: hoezo/waarom? Hypothesen en vervolgexperimenten verzinnen. Conclusie schrijven.