Keyword keresés és a TF-IDF

Ben Fry a Visualizing Data: Exploring and Explaining Data with the Processing Environment című könyvében (amelyről bővebben is szeretnék majd írni a jövőben) felhívja a figyelmet, hogy a jó vizualizáció csak félig szól az az adatok tetszetős formában öntéséről.

A folyamat hét lépésből áll:

1. aquire
2. parse
3. filter
4. mine
5. represent
6. refine
7. interact 

Az első rész az adatok beszerzéséről, használható formába öntéséről, a szemét eltávolításáról és az értelmes összefüggések felkutatásáról szól.

Tegyük fel, hogy szeretnénk kideríteni, hogy egy weboldalon körülbelül miről írnak, aztán ezt gyorsan áttekinthető formában megtekinteni -- egy jól felépített oldal esetében a lap címlapja magáért beszél, esetleg még kulcsszavakat is mellékeltek -- de mi van, ha mégsem? Az index.hu pl. viszonylag értelmes címekkel látja el a cikkeit, de nem biztos, hogy ez elmondható egy pletykalapról vagy egy személyes blogról is.

Jó ötlet lehet minden oldalnál megjeleníteni a legjellemzőbb kulcsszavakat -- a fenti képen ennek egy kezdetleges változata látható. De hogyan szereztük meg ezeket?

Az adatok beszerzésének az első lépése itt az oldalak letöltése lesz -- már itt is számos problémáva ütközhetünk. Ha szerencsénk van, találhatunk RSS feedeket, ha nincs, akkor különféle trükkökkel kell kinyerni a releváns linkeket a HTML lapokból. Ezután a tisztítás következik, ami esetünkben a HTML tagek kidobását, esetleg a reklámok, kommentek, stb. eltávolítását jelenti. A magyar nyelv esetében külön probléma a karakterkódolás is.

A következő lépés a finomabb szűrés -- írásjelek, rövidítések, számok, stb... Hatalmas -- nyelvspecifikus -- probléma, hogy a magyar ragozó nyelv, így egy jellemző kulcsszó külünböző alakjait nem biztos, hogy sikerül felismerni.

Eddig eljutva látszólag használható adataink vannak: egy csomó cikk, tiszta szöveges formában. A kulcsszavak megtalálása látszólag pofonegyszerű: megszámolunk minden szót (pl. az python NLTK eszközeivel), és a leggyakoribbakat kijelöljük kulcsszónak (ez a bag of words technika). Sajnálatos módon azonban minden nyelvben a leggyakoribbak a segédszavak (a, az, van, meg...), így ezzel semmire nem megyünk. Ha ezeket a szavakat ignoráljuk, már valamennyire juthatunk, de még így sem az igazi -- kifinomultabb modellre van szükség.

A Számítógépes Nyelvészet blogon már szóba került a TF-IDF formula, mint a keyword kinyerés elterjedt eszköze (leírás itt és itt). Az eljárás lényege, hogy egy dokumentum jellemző kulcsszavait nem csak a dokumentumhoz képest, hanem más (lehetőleg hasonló) dokumentumokhoz képest is vizsgáljuk: ha az index.hu újságírói szívesen használnak bizonyos kifejezéseket, akkor ezt figyelembe kell vennünk a kulcsszavak keresése közben, és az ilyen "általában gyakori" kifejezéseket "le kell pontoznunk".

Egészen pontosan így működik a formula:

kulcsszó fontossága: TF x IDF

TF: (term frequency): egy kulcsszó előfordulása az adott dokumentumban
IDF: (invers document freqency) egy kulcszó előfordulása a teljes dokumentum-szettban -- majd ennek az értéknek az "inverze", pl. reciproka, logaritmusa, stb.

Így a fontos kulcsszavak azok lesznek, amelyek gyakoriak az adott dokumentumban ÉS ritkák a teljes szettben.

A fenti két linkeken ezt a modellt vektor térben mutatják be. Ez elsősorban akkor jön jól, ha NAGYON SOK adatunk van, mivel így könnyeb lesz számolni (mármint a gépnek;)

Érdekes kérdés, hogy mennyire KEVÉS adatnál kezd el működni a modell. Hiszen, az egyik viszonyítási pontunk a teljes dokumentum-szett, így ha az túl kicsi, akkor nem biztos, hogy a jól méri fel a modell a kulcsszavak valódi fontosságát. A fenti próba azt mutatja, hogy meglepően kevés szöveg is elég -- az index címlapon egyszerre körülbelül 40 cikk szerepel -- ezeken végigfuttatva a modellt már értelmes eredményeket produkál.

Van tehát egy használhatónak tűnő adatszettünk és egy modellünk. A következő lépés az adatok tetszetős megjelenítése és a felhasználóval való interakció lesz.

(folyt. köv)

Mozgás és vektorok

A processing.org-on igazán remek oktató anyagok találhatók (szerintem ezek egy része átfedésben lehet a külön megvásárolható könyvek tartalmával, bár ki tudja...). A vektorokról szóló anyag inspirálta a következő alkotást.

Húzd a lap felé az egeret, majd kattintgass, vagy nyomkodd az ENTER-t!



Az oktató anyag nagyon jól elmagyaráz mindent a vektorokkal és a mozgás modellezésével kapcsolatban. A lényeg tulajdonképpen az, hogy a processing rendelkezik egy beépített PVector osztállyal -- ez az adattípus két- és háromdimenziós vektorok tárolására lett kitalálva, a metódusai pedig az ehhez tartozó matematikai műveletek (összeadás, kivonás, skalárszorzat, vektorszorzat, normalizálás, etc.) elvégzésének a nyűgét veszik le a vállunkról.

A fent látható sketch-ben tulajdonképpen nem történik más, mint hogy a repülő labdákat mindig abba az irányba gyorsítjuk, amelyik irányba az egérkurzor esik tőlük. Szóval, mindig az egér felé akarnak repülni. Az érdekesség ott van a dologban, hogy mivel egészen addig, amíg el nem érik a kurzort, gyorsítjuk őket, mindig túlrepülnek -- hogy aztán megfordulhassanak és ismét gyorsulhassanak, csak immár a másik irányba. És így tovább, a végtelenségig.
 

3D grafika egyszerűen

A processing nem csak két dimenzióban enged firkálni a rajzfelületre, de három dimenziós világokat is elég egyszerű létrehozni. Következzenek az első tapasztalataim.


Húzd az egeret a rózsaszín felület fölé!


A kód, utána pedig a kommentár:


void setup() {
  size(640, 360, P3D);
  background(0);
  frameRate(10);
}
 
void draw() {
  background(#FF66CC);
  lights();
  for (int i=0; i <= 32; i++) {
    for (int c=0; c < 20; c++) {   
      int plusz=0;
      int forgat=0;
      float tav=dist(i,c,int(mouseX/20),int((height-mouseY)/20));
      if (tav < 10) {
        //plusz=int((11-tav)*4);
        forgat=int((11-tav)*3);
      }
      fill(255);
      lemez(i*23,360-plusz,-c*23,forgat);
    }
  }
}
 
void lemez (int x,int y,int z, int forgat) {
  pushMatrix();
  translate(x,y,z);
 
  rotateX(radians(random(forgat)));
  rotateY(radians(random(forgat)));
  rotateZ(radians(random(forgat)));
 
  scale(10);
  beginShape(QUADS);
  vertex(-1,  0,  -1);
  vertex(- 1,  0, 1);
  vertex( 1, 0,  1);
  vertex(1, 0,  - 1);
  endShape();
  popMatrix();
}


A rajzlapot a harmadik dimenzió felé megnyitni a size parancs harmadik paraméterével tudjuk. Az alapvető rajzoló funkciók ugyanúgy működnek, vagyis minden képkockánál törölhetünk (vagy éppen nem), vonalat húzhatunk, stb.

size(640, 360, P3D);

A három dimenziós testek építése egy kicsivel trükkösebb, mint a két dimenziós rajzolás. A kódban ez mind a lemez() függvényben történik. Először minden testet fel kell építenünk egy pufferben, amit a

pushMatrix();

paranccsal hozunk létre, majd a

popMatrix();

rajzoljuk ki a tartalmát a "vászonra".

Közvetlenül a puffer létrehozása után kell megmondanunk azt is, hogy hová akarjuk elhelyezni a testet, illetve mennyit szeretnénk forgatni rajta (radiánban kéri!). A kódban ez így néz ki:

 translate(x,y,z);

rotateX(radians(random(forgat)));

rotateY(radians(random(forgat)));

rotateZ(radians(random(forgat)));

Ezek után nem meglepő, hogy az olyan primitív testek, mint a box() vagy a sphere() csak egy paramétert kérnek: a méretüket. Ha magunk szeretnénk építkezni, megtehetjük:

beginShape(QUADS);

vertex(-1,  0,  -1);

vertex(- 1,  0, 1);

vertex( 1, 0,  1);

vertex(1, 0,  - 1);

endShape();

Ilyen felületekből akármennyit létrehozhatunk. Fontos megjegyezni, hogy ez egy relatív koordináta-rendszer, vagyis ahhoz, hol fog megjelenni a képernyőn, nincsen semmi köze (ezt a translate csinálja). Annál fontosabb a (0,0,0) pont: e körül tudjuk forgatni a testet.

Ennyivel gyakorlatilag már képesek vagyunk egyszerű három dimenziós világokat készíteni. 

További példákért és információért ide érdemes ellátogatni, illetve továbbra is figyelemmel kísérni a Kép és Kód blogot:)

BKV térkép megállókkal

Nagyon megörültem, hogy a teljes BKV menetrend-adatbázis elérhető, és szabadon lehet vele játszadozni -- a GTFS formátum ugyanis ezt erősen megkönnyíti. Az adatok egyszerű plain text-ben, egészen pontosan CSV-ben, vagyis veszőkkel elválasztva érkeznek. Ezt az Excel és társai minden további nélkül tudják olvasni.

Mivel az adatbázis nagyon sok mindent tartalmaz, szükséges egy kis előszűrés -- egyrészt, hogy egyszerűbb legyen az élet, másrészt, mert a processing bizony elég lassú. A nagy adatbázis alatt kb. 200 megabájt szöveges adatot kell érteni, vagyis egy táblázatkezelővel még éppen, egy egyszerű python szkripttel pedig pikk-pakk megbírkózhatunk vele.

Én legalábbis ezt csináltam: csupán az útvonalakat szerettem volna ábrázolni egy minimálisan interaktív térképen. Ehhez teljesen felesleges foglalkozni a járatok indulási idejével, vagy éppen azzal, hogy melyik jármű mikor melyik megállóban áll. Nekem csak annyit kell tudni, hogy melyik járat mely megallókat érinti. Csakhogy, a GTFS külön táblákban tárolja a járatokat, a megállókat és a járatok által érintett pontokat, Ezért szükség volt az adatok előkészítésére, ami python-nal és táblázatkezelővel történt. Természetesen a legelegánsabb megoldás az összes adatot bedobni egy adatbázisba, és táblákon átívelő lekérdezéseket csinálni, de verébre felesleges ágyúval lőni.

Tehát, lássuk a működő programot (mozgatás: az egér húzgálásával, zoom: +/-):




A forrás az alábbi linken érhető el. A kódot viszonylag sűrűn kommentáltam. Talán érdemes kiemelni, hogy processing-ben nagyon kényelmes a saját adat-típusok (objektumok) létrehozása (ilyenben tárolom a megállókat és az útvonalakat). A másik megjegyzés, hogy ebben a programban a folyamatosan újrainduló draw() funkció csak a hosszúsági és szélességi koordináták kiírásáért felel; a térképet a program elején, illetve csak akkor rajzoljuk ki, ha pl. elmozdítottuk (ugyanis elég sokat kell számolni hozzá). A mozgatásra és a zoomolásra a mousePressed() és a keyPressed() funkciók figyelnek (ezek a nyelvbe beépített funkciók).

Magyar földrajzi adatok

A Statisztikai Hivatalnál elérhető a Helységnévtár, amiben megtalálható az összes magyar település földrajzi koordinátája (és még számos egyéb). Remekül el lehet szórakozni például az irányítószámok eloszlásának ábrázolásával:

De ami ennél sokkal felvilanyozóbb: a BKV fél éve publikálta a teljes menetrend-adatbázisát. És nem is akárhogy, hanem a Google Maps által bevezetett GTFS formátumban -- így gyakorlatilag bárki megírhatja a saját menetrend-tervező applikációját. Nekem persze nincsenek ilyen ambícióim, de azért jó tudni, hogy Budapetről is van egy csomó egyszerűen feldolgozható földrajzi adat (nem is olyan rég került fel a netre a Budapest egy napja videó -- szintén ezekből táplálkozik).

Ez Budapest összes viszonylata -- a hiba egyelőre ott van, hogy csaka végpontokat kötjük össze, vagyis pl. a körúti villamosból csak egy vonás marad. A HÉV és a metróvonalak azonban már itt is felismerhetők.