De implementatie van gabmap

Het ontwerp voor de web-applicatie zag er in het begin zo uit: Elke gebruiker kon een aantal projecten aanmaken. Elk project bestond uit een kaart en een of meer data-sets. Voor elke data-set kon de gebruiker een of meer metingen laten uitvoeren. Voor elke meting konden een of meer dendrogrammen gemaakt worden, een of meer clusterkaarten, een mds-kaart en een fuzzy clusterkaart. Een hiërarchische opzet dus, waarin de gebruiker stap voor stap een volgend niveau kon uitvoeren.

Dit plan heb ik al snel laten varen, omdat ik zag dat het erg complex zou worden. Complex om te implementeren, maar ook complex voor de gebruiker om te navigeren. Ik heb toen van een project een platte structuur gemaakt, met één kaart, één data-set, en één meting. En op basis van die ene meting een groot aantal verschillende soorten analyses. Zie hier voor flowcharts van enkele onderdelen.

Het nadeel van deze platte structuur is dat er veel analyses worden gedaan die de gebruiker misschien niet bekijkt. En voor elke nieuwe meting op dezelfde data-set moet een heel nieuw project begonnen worden. Het voordeel is dat er heel voor voor de gebruiker gedaan wordt waar hij aanvankelijk niets voor hoeft te doen, en dit wordt allemaal zo snel mogelijk gedaan nadat hij z’n project (kaart en data) heeft ge-upload. Bij de aanvankelijke opzet zou de gebruiker elke stap apart moeten initialiseren, en dus bij elke stap opnieuw moeten wachten tot de verwerking is uitgevoerd.

Een ander voordeel van de huidige opzet is dat het veel eenvoudiger is een onderdeel toe te voegen. Daardoor is het geheel aan onderdelen ook een stuk breder geworden. Was het oorspronkelijke idee nog om een gebruiksvriendelijke interface te maken voor de RuG/L04-software, uiteindelijk biedt de web-applicatie veel meer dan dat, en biedt het functionaliteit die niet direct aanwezig is in de oorspronkelijke software, maar het resultaat is van de toepassing van die software voor complexere taken. In een web-interface is het mogelijk veel gebruik te maken van scripts, en andere programma’s zoals R, om functionaliteit te creëren die in de oorspronkelijke software niet aanwezig is, en ook niet is aan te bieden in de huidige distributie van RuG/L04 omdat het te veel afhangt van software van derden en van de configuratie van de machine waarop het draait. Daardoor is gabmap geen interface voor RuG/L04, maar een nieuw platform dat voortbouwt op RuG/L04.

De web-applicatie maakt geen gebruik van een database. Alle programma’s achter de applicatie werken op bestanden, dus is alle data opgeslagen in een directory-structuur met bestanden. Voor elke gebruiker is er een directory, daarin zitten bestanden met algemene info zoals e-mailadres, loginnaam, en per project een subdirectory. Een subdirectory van een project bevat bestanden met algemene gegevens over dat project, en voor elk onderdeel in het project weer een subdirectory. Daarin worden alle data, resultaten, en info over huidige opties bewaard. Zie hier voor een overzicht.

De berekeningen die moeten worden uitgevoerd voor een project zijn vaak tijdrovend. Wanneer een gebruiker een project aanmaakt kan de server niet blijven wachten tot alle berekeningen zijn uitgevoerd, maar moet direct een pagina aan de gebruiker terugzenden. Daarom wordt er gebruik gemaakt van een rij (queue) met taken, en taken uit die rij worden in de achtergrond uitgevoerd, terwijl de gebruiker de web-applicatie kan blijven gebruiken voor andere zaken.

Wanneer een gebruiker een project aanmaakt, dan worden er een stuk of tien taken in de rij gezet. Onderdelen die op interactie van de gebruiker reageren zetten voor langdurige berekeningen vaak één taak in de wachtrij. De opzet van de rij is simpel: first in, first out. Dit heeft een nadeel wanneer meerdere gebruikers actief zijn. Wanneer twee gebruikers vlak achter elkaar een project aanmaken, dan moeten de taken van de tweede gebruiker wachten tot de eerste tien taken van de eerste gebruiker allemaal zijn afgerond. Ik heb er over gedacht dit te veranderen, zodat taken van verschillende gebruikers afgewisseld tussen de gebruikers worden uitgevoerd, maar dat is complex. Momenteel hebben weinig gebruikers hier last van, alleen bij practica met meerdere deelnemers.

Taken moeten uitgevoerd worden via een wachtrij omdat sommige taken veel geheugen nodig hebben, en je niet meerdere van zulke taken tegelijk kunt draaien zonder in geheugenproblemen te komen. Bovendien moeten taken wachten op resultaten van andere taken voor ze kunnen beginnen.

Mijn plan was in het begin om de web-applicatie te implementeren in Pylons, een webframework geschreven in Python. Ik heb daar al snel van afgezien, omdat werken met Pylons een grote investering vraagt om te doorgronden, en omdat de voordelen niet duidelijk waren. Alles is nu dus geïmplementeerd als een reeks cgi-scripts die functioneren in de Apache web-server. Dat zijn scripts in Python 3.1, met een korte wrapper in sh voor de initialisatie van de environment. Er is één script dat functioneert als een ‘dispatcher’ voor de verschillende onderdelen binnen een project. Alle andere interacties met de applicatie, zoals afhandeling van een form, gebeuren grotendeels door een apart script per interactie. Al die scripts maken wel gebruik van dezelfde library met hulpfuncties in Python.

Behalve Python 3.1 worden de volgende programmeertalen gebruikt:

  • Python 2.6, voor hulpscripts die Python-library’s gebruiken die nog niet voor Python 3 beschikbaar zijn.
  • Externe Python-library’s: pyproj (voor 3.1), numpy (voor 2.6 en 3.1), colormath (voor 2.6)
  • De RuG/L04 software, geschreven in C en Flex (lexical analyser)
  • Perl, voor een oud script dat nog steeds functioneert
  • R
  • Make, voor de uitvoering van taken in de wachtrij
  • sh
  • PostScript, niet alleen voor weergave van afbeeldingen, maar ook voor berekeningen aan coördinaten voor de “mouse-over maps”.

De grafische uitvoer is in PostScript, met conversies naar PDF en PNG. Bij veel afbeeldingen is er de optie een alternatieve versie te downloaden die geschikt is voor printen in zwart-wit. In dat geval wordt bijvoorbeeld een grijze achtergrond (voor gebieden zonder data) vervangen door een blokstructuur, om het te onderscheiden van de andere kleuren die worden afgedrukt als grijswaarden.

Daarnaast is er uitvoer van data in diverse formaten. Berekende afstanden als tabel, of in L04-formaat. Een feature-definitie die gebruikt wordt voor de tokenizer. Meer zit in de planning.

Voor de data-formaten voor invoer, zie hier en hier.

Als extraatje is er een onderdeel ‘tools’. Daarin zitten nu twee onderdelen:

Confidence interval voor Local Incoherence?

Twee metingen op dezelfde dataset, local incoherence (linc) van 0.705176 (blauw, verticale lijn) en 0.721365 (zwart, verticale lijn).
De curves zijn van tests met verschillende ruisniveaus, hoe lichter de lijn, hoe meer ruis. De krommen voor het vierde en vijfde ruisniveau liggen duidelijk rechts van de linc zonder ruis, dus die krommen vallen af. De eerste drie krommen liggen duidelijk rond, of zelfs lager dan de linc zonder ruis, dus die geven reële waardes. De eerste drie blauwe krommen liggen duidelijk een stuk links van de eerste drie zwarte krommen, dus is het verschil tussen de beide metingen significant.
Is er een methode om die significantie numeriek uit te drukken, in een p-waarde of zo?
Of valt er een betrouwbaarheidsinterval te geven voor een linc-waarde?

Wel of geen normalisatie?

Wel of geen normalisatie gebruiken? Ik heb het getest met vier datasets: Lowman, NL oude data, NL nieuwe data, Duitsland. In alle gevallen is het resultaat met normalisatie beter dan het resultaat zonder normalisatie, voor zowel Cronbach Alfa als Local incoherence.

               | Cronbach Alfa         || Local incoherence
               | met      |  zonder    || met      |  zonder   | verschil
Lowman         | 0.974195 |  0.974037  || 1.41545  |  1.59314  | + 12.6%
NL oude data   | 0.975436 |  0.974408  || 0.704684 |  0.723996 | +  2.7%
NL nieuwe data | 0.992445 |  0.991864  || 1.5747   |  1.60918  | +  2.2%
Duitsland      | 0.961504 |  0.955868  || 0.961621 |  1.02836  | +  6.9%

Vooral bij Lowman is het verschil aanzienlijk. Dit komt omdat dit een dataset is met veel gaten en met grote variatie in lengtes.

Tests met segmenten

Twee meetmethodes met elkaar vergeleken

  1. gedifferentieerd: verschil tussen ‘n’ en ‘l’ is 1, verschil tussen ‘n’ and ‘ñ’ is 0,2.
  2. binair: verschil tussen ‘n’, ‘l’ en ‘ñ’ is allemaal 1.

Beste resultaten zijn gemarkeerd met een asterisk.

           gedifferentieerd        binair
           ca          linc        ca          linc
NL oud    *0.975443   *0.688422    0.974959    0.769789
NL nieuw  *0.991192   *1.60175     0.991123    1.63559
Lowman     0.972952    1.42377    *0.976905   *1.37052
DE        *0.958644   *0.979435    0.95606     1.07387

Bantu heeft geen diacrieten

ca = cronbach alpha : hogere waardes zijn beter
linc = local incoherence : lagere waardes zijn beter

Test van verschillende verwerkingsmethodes

Ik heb verschillende methodes van string edit distance getest op vijf datasets, zo’n beetje alle data die ik heb.

Ik heb drie methodes met elkaar vergeleken:

  1. plain: verwerking van strings zoals ze worden aangeboden
  2. tokenized, free alignment: accenten samengevoegd met hun basisklanken
  3. tokenized, forced alignment: als vorige, met gedwongen alignments van VV en CC

De verschillen zijn niet zo groot.

Volgens local incoherence is methode 1 in twee gevallen de beste. Methode 2 ook in twee gevallen. En methode 3 in één geval. (Zie asterisk in onderstaande tabel)

Cronbach alpha is het beste bij methode 1 in drie gevallen, bij methode 2 in geen geval, en bij methode 3 in twee gevallen.

           plain                   tokenized               tokenized
           free alignment          free alignment          forced alignment
           ca          linc        ca          linc        ca          linc
NL oud    *0.977462    0.721365    0.975443   *0.688422    0.974789    0.692911
NL nieuw   0.991113    1.63198     0.991192    1.60175    *0.992445   *1.5747
Lowman    *0.977773   *1.40152     0.972952    1.42377     0.973726    1.412
DE        *0.962121   *0.935982    0.958644    0.979435    0.960539    0.968748
Bantu      0.977317    1.65525     0.980031   *1.64498    *0.980939    1.70772

ca = cronbach alpha : hogere waardes zijn beter
linc = local incoherence : lagere waardes zijn beter

Volgens de tests is er geen methode beter dan de andere.

Ik denk dat methode 3 als default gebruikt kan worden omdat het alignments laat zien die er het begrijpelijkst uitzien. Maar het argument dat deze methode de beste meetresultaten geeft kunnen we niet gebruiken, niet als we afgaan op deze testresultaten.

Shift map

standard map

shift map

Vervorming van een kaart d.m.v. MDS

Een andere methode om MDS (in twee dimensies) op de kaart in beeld te brengen?

Methodes van edit distance

Op dit moment zijn onderstaande keuzes mogelijk voor manier van afstandmeting dmv string edit distance:

Methode plain

Normalisatie functie nummer 1: delen door som van lengtes van beide strings.

gewicht indel: 1

gewicht substitutie: 2

Als je indel en substitutie aan elkaar gelijk maakt krijg je rare alignments te zien.

Methode vowel/consonant alignments

Normalisatie functie nummer 1: delen door som van lengtes van beide strings.

Tekens ingedeeld volgens deze tabel:

http://www.let.rug.nl/~kleiweg/L04/webapp/bin/charset.sh

Alignments toegestaan:

  • vowel – vowel
  • vowel – semivowel
  • consonant – consonant
  • consonant – semivowel
  • stress – stress
  • puctuation – punctuation
  • unknown – unknown

Haakjes moeten balanceren en worden geïnterpreteerd als niet nader benoemde features, evenals diacrieten. Haakjes (van dezelfde soort) mogen niet nesten. Haakjes: () [] {}

Diacrieten en haakjes worden gecombineerd met vowel, semivowel, consonant of unknown. Andere combinaties zijn niet toegestaan, zoals stress gevolgd door diacriet. Na een sluithaak zijn ook geen diacrieten meer toegestaan.

Gewicht substitutie:

  • twee verschillende basisklanken: 1
  • per verschillend feature wordt het gewicht van substitutie met 0.2 verhoogd.
  • het gewicht voor een substitutie die niet mag is 4 (plus 0.2 voor elk diacrietverschil)

gewicht indel: 1

Methode vowel/consonant alignments — strict IPA

Als de vorige, maar elke string waarin een teken voorkomt dat niet ipa is wordt overgeslagen (en geeft foutmelding in de lijst met fouten), zie tekens gemarkeerd ‘ipa’ in tabel op bovenstaande link.

Data mining in LAMSAS

Ik heb pas een boek gelezen over de geschiedenis van Nederlandse kolonisten in de VS. Ik zag op een clusterkaart een cluster langs de oostgrens van New York, en ik vroeg me af, zou dit een restant van die Nederlandse geschiedenis zijn?

New York, Pennsylvania en New Jersey, ingedeeld in zes clusters

Met de techniek van Martijn en John, die meet hoe belangrijk een bepaald item is voor een dialectgebied, en die ik heb ingebouwd in de webapplicatie, ben ik dit cluster eens gaan onderzoeken.

Een van de woorden met de hoogste scores was Tennessee. Een distributiekaart van de varianten die belangrijk zijn voor het cluster in het oosten van New York ziet er zo uit:

Distributie kaart voor betekenisvolle varianten van "Tennessee"

Distributiekaart voor de betekenisvolle varianten van "Tennessee"

Alle betekenisvolle varianten bleken te beginnen met t{h}. Is dit bepalend voor dit cluster? Dat blijkt zo te zijn:

Spreidingskaart voor varianten van "Tennessee" die beginnen met "t{h}"

Een ander woord dat hoog scoort voor dit cluster is porch. Een spreidingskaart van betekenisvolle varianten ziet er zo uit:

Distributiekaart voor de betekenisvolle varianten van "porch"

Nu lijkt het om de varianten te gaan die beginnen met p{h}. Een spreidingskaart voor dit patroon ziet er zo uit:

Spreidingskaart voor varianten van "porch" die beginnen met "p{h}"

Nou weet ik niet of deze uitspraak t{h} en p{h} typisch voor Nederlandse nazaten is. Wat boeiend is is dat je met dit in de web-applicatie een instrument hebt waarmee je dit soort kenmerken kunt opsporen. Data mining dus.


Toevoeging 18 juli:

Hoe zit het met k{h}? Het woord kitchen scoort heel laag. De methode vind een set varianten waarvan er veel buiten het gezochte cluster liggen, en daarbij zijn ook varianten die niet met k{h} beginnen:

Distributiekaart voor de betekenisvolle varianten van "kitchen"

Maar als je alleen naar k{h} kijkt lijkt het er meer op, al valt de spreiding minder goed samen met het cluster dan eerder t{h} en p{h}:

Spreidingskaart voor varianten van "kitchen" die beginnen met "k{h}"

Boektip: Complex Adaptive Systems

John H. Miller & Scott E. Page
Complex Adaptive Systems
An Introduction to Computational Models of Social Life