Iti0210lab91

"Naiivne" Bayesi klassifikaator

Sissejuhatus

Klassifitseerimise ülesandes on vaja objekti tunnuste järgi otsustada, millisesse klassi mingi objekt kuulub. Näiteks tuntud iiriste klassifitseerimise ülesandes saab taime teatud osade mõõtude järgi otsustada, millisesse iirise alamliiki ta kuulub. Klassifitseerimiseks saab kasutada ka Naiivse Bayesi (lühidalt NB) tõenäosusmudelit, mis põhineb eeldusel, et kui meil on peidetud põhjus, siis selle nähtavad tagajärjed on kõik üksteisest sõltumatud. See eeldus võimaldab tagajärgede alusel põhjuse tõenäosust leida üsna lihtsa valemi järgi.

Kui meil on teada klassifitseeritava objekti mingid tunnused x₁, ..., x_n ning mingid võimalikud klassid c₁, c₂, ..., siis tõenäosus, et objekti klass on c_i on proportsionaalne järgmise valemiga:

Täpset tõenäosust see valem ei anna, küll aga annab ta seda suurema numbri, mida suurem on tõenäosus. Seega tuleb see valem arvutada välja iga võimaliku klassi c_i kohta ja siis saadud tulemusi võrrelda, et leida kõige tõenäolisem klass. Vaja on iga klassifitseeringu esinemise tõenäosust P(c_i) ning iga tunnuse tinglikku tõenäosusjaotust iga klassi kohta P(X_j|c_i).

NB mudeli üks esimesi ja tuntumaid rakendusi on rämpsposti klassifitseerimine. Idee on lihtne - rämpspostis esinevad rohkem ühesugused sõnad (buy Go1d watches CHE4P!!), päris kirjades teistsugused. Sõnad on tunnusteks, nende esinemise peidetud põhjus on aga see, kas kiri on rämpspost või tavaline.

Kirjuta programm, mis:

1. etteantud treeningnäidetest, kus on antud nii tunnused kui ka klass, ehitab vajalikud tõenäosustabelid;
2. leiab ainult tunnuste alusel objekti klassi

Treeni oma mudel kasutades väikest rämpsmeilide korpust [1]. Allpool leiad juhised selle alla laadimiseks ja kasutamiseks. Seejärel proovi, kas õnnestub kahte toodud kirja klassifitseerida.

Taustainfo: lühidalt, detailsemalt saad lugeda loengukava alt viidatud materjalidest.

Ettevalmistus

Laadi siit treeningandmed ja paki lahti. Võid kasutada ka muid andmeid, aga ära kasuta enron1 osa samast korpusest, kuna sealt pärinevad testandmed.

Teisendame tekstifailid sõnade listideks, edaspidi viitame nendele listidele kui dokumentidele. Selle juures on kasulik ka sõnu filtreerida, jättes välja näiteks sidesõnad. Esialgu teeme lihtsamalt ja filtreerime lihtsalt sõnad, mis on lühemad kui 4 tähemärki.

def stopword(wstr):
    w = wstr.strip()
    if len(w) < 4:
        return True
    return False

Ja siin on laadimise funktsioon ise:

import os

def read_dir(dirn):
    cont_l = []
    for fn in os.listdir(dirn):
        with open(os.path.join(dirn, fn), encoding="latin-1") as f:
            words = [w.strip()
                for w in f.read().replace("\n", " ").split(" ")
                    if not stopword(w)
            ]
            cont_l.append(words)
    return cont_l

Kasutada saad seda nii:

ham_l = read_dir("enron6\\ham")
spam_l = read_dir("enron6\\spam")

print(len(ham_l), "ham messages")  # meaning, these are not spam
print(len(spam_l), "spam messages")

Treenimine

Rämpsposti mudeli tegemiseks võtame uuesti teooria kokku ja kohandame selle meie ülesande jaoks.

Meil on kiri, mis sisaldab sõnu w₁, w₂, ...,. Nende sõnade põhjal tuleb hinnata, kumb tõenäosus on suurem: rämpspost P(spam|w₁, ..., w_n) või tavaline kiri P(ham|w₁, ..., w_n). Selleks arvutame hinnangud:

H_spam = P(spam) * P(w₁|spam) * P(w₂|spam) *... * P(w_n|spam)

H_ham = P(ham) * P(w₁|ham) * ... * P(w_n|ham).

Kõik väärtused valemites saab leida dokumentide pealt statistikat tehes. P(spam) ja P(ham) on eeltõenäosused. Kui meil on treenimiseks 1000 kirja, millest 900 on rämpspost, võime öelda, et P(spam) = 0.9. See tähendab, et meil on mingi eelneval kogemusel põhinev eelarvamus selle kohta, kas klassifitseeritav kiri on rämps või mitte.

w_i tähistab sõna dokumendis positsioonil i. Nüüd teeme kaks eeldust, mis ei ole loomuliku keele puhul kumbki korrektne, aga lihtsustab meie elu tunduvalt:

• sõna esinemise tõenäosus dokumendis ei sõltu täpselt kohast (i)
• sõna esinemise tõenäosus ei sõltu teistest sõnadest - see on NB mudeli põhieeldus.

Oletame, et sõna "Tere" esineb suvalisel kohal tavalises kirjas tõenäosusega 0.001. Kui meil on tavalistes kirjades (ham) kokku 200000 sõna, siis nendest umbes 200 on järelikult "Tere". Sõna esinemise tõenäosust P(w|c), kus c on tähistab klassi - kas spam või ham - hindame järgmise valemiga:

• N_w,c - sõna w esinemiste kord c tüüpi kirjades
• N_c - palju sõnu c tüüpi kirjades kokku on
• |V| - unikaalsete sõnade arv

Näiteks, kui meil esineb sõna "online" rämpsposti hulgas 11 korda, kogu rämpsposti sõnade arv kokku on 500000 ja unikaalseid sõnu on 10000, siis arvutame P("online"|spam) = (11 + 1) / 500000 + 10000. [2]

Kokkuvõte

1. leia dokumentide koguarv ja kui palju neist on rämps/mitte rämps (eeltõenäosused)
2. loenda sõnade esinemised eraldi rämpspostis ja tavalistes kirjades
3. loenda, palju sõnu üldse on rämpspostis/mitte rämpsus
4. loenda mitu unikaalset sõna on (|V|)

Kiire viis unikaalsete sõnade leidmiseks:

V = set(all_spam_words)  # all_spam_words: spam docs joined together
V.update(all_ham_words)
print(len(V), "unique words")