Tietokoneharjoitus #5

Aloitus

Demot

Pääaiheet:

Taustoja:


Demo #1, T5/1

Käydään läpi, mitä ovat kattavat joukot ja miten ne saadaan tasoittaisella algoritmilla. Kirjoitetaan datatiedosto softaa (apriori) varten ja kokeillaan, löytääkö se samat kattavat joukot.

Paperilaskarikierroksilta tehtävä H5/1: etsi kattavat joukot kynnysarvolla N=4. Ajatellaan matriisia, jossa neljä riviä a, b, c ja d ja kymmenen havaintoa

------------------------------------
| a (ind==1) | 0 1 1 1 1 0 0 1 1 1 |  "omena"
| b (ind==2) | 1 1 0 1 0 1 1 0 0 1 |  "leipä"
| c (ind==3) | 0 0 0 1 1 1 1 1 1 1 |  "maito"
| d (ind==4) | 1 1 0 1 1 1 1 0 0 1 |  "limu"
------------------------------------
joka ajatellaan vaikkapa kymmenen henkilön (10 saraketta) kauppakasseina. Neljä artikkelia (muuttujat, rivit) ovat vaikkapa omena, leipä, maito ja limu. Jos tuote (tai monta samaa tuotetta) on kassissa, merkataan kyseiselle henkilölle muuttujan kohdalle ykkönen, jos ei ole lainkaan, niin nolla. Ensimmäinen havainto annetussa matriisissa on (0 1 0 1)' eli kauppakassista löytyvät leipä (leipiä) ja limu (limuja).

Kattavia joukkoja ovat niiden artikkeleiden joukot, jotka löytyvät vähintään kynnysarvon ilmoittamasta määrästä kasseja.

Oikeassa tapauksessa sekä havaintoja että artikkeleita on paljon.

Tasoittainen algoritmi: perusteet ja algoritmin pääperiaate. Datasta tietoon, luku 8. ( ... Kattavan joukon jokainen alijoukko tulee olla kattava ... )

Kuinka 0-1-matriisi esitetään kyseisiä apriori-ohjelmia varten? Halutaan jokainen havainto (kassi) omalle riville. Tuotteet indeksoidaan juoksevalla numerolla a=="omena"==1, b=="leipä"==2, c=="maito"==3, d=="limu"==4. Kunkin havainnon eli kassin tuotteet luetellaan käyttäen näitä indeksejä välilyönnin erottamina. Tässä esimerkkitapauksessa saadaan siis kymmenen havaintoa eli riviä ja indeksinumero 1, 2, 3, 4. Matriisin ensimmäinen sarake (0 1 0 1)' tuottaa ensimmäiseksi datatiedoston riviksi siis "2 4" ja matriisin viimeinen sarake (1 1 1 1)' taasen datatiedoston viimeiseksi riviksi "1 2 3 4":

2 4 
[... 8 muuta riviä ...]
1 2 3 4

Miten apriori-ohjelmaa käytetään? Ensimmäinen argumentti on yllä luotu datatiedosto. Kynnysarvo "4" (N=4) annetaan apriori-ohjelmalle toisena argumenttina. (Kolmantena mainittuun tiedostoon ohjelma kirjoittaa kaikki kattavat joukot.) C-ohjelmalla: ./apriori datatiedostosi.dat 4 kattavat_joukot.txt tai vastaavasti python-ohjelmalla: python apriori.py datatiedostosi.dat 4 >kattavat_joukot.txt Kun luet tiedoston "kattavat_joukot.txt" sieltä pitäisi löytyä paperilaskareissakin lasketut joukot eli {tyhjä joukko, a, b, c, d, ac, ad, bc, bd, cd, bcd}, joissa (a==1, b==2, c==3, d==4). Merkinnät ovat lyhenteitä normaalille joukkomerkinnälle, esimerkiksi ab ~= {A, B} ~= {"omena", "leipä"}.


Demo #2, T5/2

Tutkitaan teekkareiden omia "kauppakasseja".

Kirjoita ainakin yksi oma ruokakaupan kauppakuitti kuittitiedostoksi (katso esimerkkejä) ja lähetä se sähköpostilla "parvi () tkk.fi". Käytä omaasi ja Data-hakemiston muita kuitteina aineistona luomaan kattavia joukkoja. Tutki, millaisia kattavia joukkoja saat eri kynnysarvoilla (N >= 2, aloita isoista N:n arvoista kohti pienempiä) ja miten niiden lukumäärä muuttuu kynnysarvon funktiona.

Voit käyttää skriptiä "kuitit_dataksi.sh" luomaan datatiedoston "data.txt" apriori-ohjelmaa varten:

cd Data
cp ../Skriptit/kuitit_dataksi.sh .
./kuitit_dataksi.sh 
Tällöin kuittien tiedostonimet tulee olla muotoa "kuitti_xxxx.txt", jossa kokonaisluku x >= 0001. Kussakin kuittitiedostossa tuotteet on yksisanaisia ja omilla riveillään (muista viimeisen rivin loppuun myös rivinvaihto!)
leipä
juusto
makkara
olut
tulitikkuaski
Ohjelma tuottaa väliaikaistiedostoja "data_x.txt" ja tiedoston "data.txt", joka annetaan apriori-ohjelmalle. Tiedostosta "tuotteet.idx" näet numeroiden ja artikkeleiden yhteyden.

Voit tehdä kuvaajan "kattavien joukkojen lukumäärä kynnysarvon funktiona" Octavea käyttäen. Muokkaa skriptiä "Matlab_skriptit/DT_T5_d2.m" ja aja se. Aloita kynnysarvo "suuresta" luvusta, äläkä pienennä liian pieneksi - jos kynnyksenä N=1, niin 1. tasolla kaikki kattavia, mistä generoituu paljon 2. tason ehdokkaista, joista paljon kattavia, joista generoituu hyvin paljon... (kuinka paljon, jos 0/1-matriisi oli täynnä ykkösiä?)


Demo #3, T5/3

Tutkitaan yli 50 tekstidokumenttia ja niiden sisältämiä sanoja. Katso hakemistoja Dokkarit/Aihe1 ja Dokkarit/Aihe2. Käytä laadittuja "bag of words" -tiedostoa. Dokumenteissa on yhteensä noin 5000 eri "sanaa". Yhdessä dokumentissa on noin 100 - 1000 sanaa, keskimäärin muutamia satoja sanoja.

Piirrä 0/1-matriisi (DT_T5_d3.m) - mitä kaikkea voit tulkita sen mukaan, kun riveillä dokumentit ja sanat sarakkeina ja musta piste (juova) tulee kohtaan, jossa kyseinen sana (sarake) esiintyy kyseisessä dokumentissa (rivi).

Mieti, kuinka tehokas esitystapa 0/1-matriisi (sana esiintyy / ei esiinny) on? Milloin se toimii, milloin ei? Laske nollien määrä matriisissa ja ykkösten määrä matriisissa.

Kokeile apriori-ohjelmaa (aloita N > 30) ja katso millaisia ovat suurikokoisimmat kattavat joukot. Ovatko tulokset järkeenkäypiä, ovatko ne hyödyllisiä? Miten parantaisit tekstidokumenttien esikäsittelyä, jotta hyödyllisyys paranisi?

Datasta tietoon, luku 8. Havainto: dokumentti, Muuttuja: (perusmuodossa oleva) sana. Data D(s,d)=1: esiintyykö sana s ainakin kerran dokumentissa d? Tästä saadaan siis 0/1-matriisi, jonka koko on dokumenttien määrä x sanojen määrä.

Kokeillaan hieman käytännössä. Käytetään dokumentteina PDF-muotoista suomenkielistä harjoitustyön dokumenttia eräältä TKK:n kurssilta. PDF:t muutettu tekstiksi komennolla "pdftotext" ja muutamia intimiteettiä varjelevia sananmuunnoksia tehty ohjelmalla "sed".

0/1-matriisi, jossa rivit dokumentteja ja sarakkeet sanoja, on saatu aikaan "BOW-toolkitillä", jossa "libbow"-kirjaston päällä "rainbow"-ohjelma. (HUOM! Et tarvitse ladata ohjelmaa!!!) Binäärimatriisi löytyy tiedostosta "Data/matriisi_10.dat". Apriori-ohjelman ymmärtämässä muodossa matriisi on esitetty tiedostossa "Data/dataset.dat". Sanat löytyvät tiedostosta "Data/sanat.idx", esim. indeksi 42 vastaava sana löytyy 42. riviltä vaikkapa komennolla

egrep "^42:" Data/sanat.idx
Dokumenttitiedostojen (kaksi eri harjoitustyötä) järjestyksen voi lukea tiedostosta "Data/tiedostot.idx", vaikkapa matriisin rivit 5 ja 12 viittaavat dokumentteihi, jotka löytyvät komennolla
egrep "^5:" Data/tiedostot.idx
egrep "^12:" Data/tiedostot.idx
Voit lukea tiedostostoja Dokkarit/Aihe1/data<täydennä>.txt

Dokumenttien samankaltaisuutta voi testata aiemmilla kierroksilla käytetyin menetelmin tai katso esim. Bingham, Mannila: Random projection.


Demo #4, T5/4

Kokeile "Hubs and authorities" -algoritmia, katso luku 9. Koodi DT_T5_d4.m, jossa valmiina kaksi demoverkkoa M1 ja M2 sekä pohja M3.

M1 löytyy luentokalvojen esimerkkinä. M2 on 30 sivun verkko, jossa näkee, että pelkkä linkkien lukumäärä ei anna parasta relevanssia.

Syötä läsnäolopaperin verkko (M3 koodissa) ja tulkitse.



UNIX-työkalut määrämuotoisen tekstitiedoston pyörittämiseen

Tekstinkäsittelyä varten voi käytää esimerkiksi emacsia, komentorivillä "emacs &" (et-merkki vapauttaa kehotteen). Komentojen tarkat manuaalisivut "man komento" ja "info komento". Netistä löytää paljon ohjeita. Komentoja voi putkittaa (|), syöttöä ohjata <, >, >>, ... Säännöllisiä lausekkeita (regular expressions) tarvitaan usein.

Komentoja: fgrep, egrep, wc, cut, paste, sort, tr, diff, head, tail, colrm, ...

Isompia ohjelmia vaativampaan pyörittelyyn awk, gawk, sed, ...

Harri Haanpään esimerkki sed-ohjelman käytöstä:

lynx -dump www.angelfire.com/id/ismoalanko/hkone.html | sed s/Hassisen/Turingin/g
Eli luetaan www-sivu (myös "wget") putkitetaan sed-ohjelmalle, joka kaikki (g) esiintymät "Hassisen" -> "Turingin".

Esimerkkejä pyörittelyyn

echo Testi
echo Testi\n
echo "Testi\n"
echo 'Testi\n'
echo "$#"
echo '$#'
echo "Nämä omille riveilleen" > roska1.txt
cat roska1.txt | tr " " "\n" > roska2.txt
cat roska2.txt | tr "\n" ":" 
echo "3 4 5 9 12" > roska5.txt
echo "8 4 2 1 9" >> roska5.txt
echo "2 1 0 5 4 7 9" >> roska5.txt
cat roska5.txt | cut -d" " -f3
fgrep "2 1" roska5.txt
egrep "^2 1" roska5.txt
egrep "4 [5-7]" roska5.txt

Shell-ohjelmointi

Esimerkki skriptitiedostosta "maalima.sh"
#!/bin/sh

# tulostetaan näytölle:
echo "Terve, maalima!"
Tiedostolle pitää asettaa suoritusoikeus, esimerkiksi "chmod 744 maalima.sh" (-rwxr--r--). Ajetaan komentoriviltä "./maalima.sh".

Octave batch-ajona

Octave on GNU-lisenssinen ilmainen "Matlab-klooni". Hyvin moni Matlab-skripti toimii myös Octavessa ja päinvastoin.

Octavea voit ajaa myös eräajona avaamatta sen käyttöliittymää. Ensimmäiselle riville tulee tällöin "#!polku/octave -qf", jossa oikea "polku" löytyy komennolla "which octave". Muista laittaa "execute-bitti" päälle (chmod 744 skriptisi.oct).