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 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(os.path.join("enron6", "ham"))
spam_l = read_dir(os.path.join("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")

Klassifitseerimine

Teisenda allolevad kirjad dokumentideks samamoodi nagu tegid treeningandmetega. Korduvad sõnad meid enam ei huvita, seega viska kordused välja. Seda saad teha käsitsi või jällegi Pythoni set()-i ära kasutades. Lisaks viska välja sõnad, mida me treenimisel ei kohanud mitte kummagi klassi kirjade juures, kohtleme neid kui "neutraalseid" mis ei suurenda ega vähenda rämpsposti tõenäosust. Kui sõna esines ühes klassis, aga teises ei esinenud, siis tuleb tema esinemiste arvuks teises võtta 0.

Nüüd tuleks arvutada H_spam ja H_ham. Kui H_spam on suurem, on tegu rämpspostiga.

Arvutamine aga ei ole nii lihtne! Tegu on suure hulga väikeste tõenäosuste kokku korrutamisega, mis kipuvad kokku 0-iks minema. Kasutame omadust, et kui a = b * c siis log(a) = log(b) + log(c). Seega valemite lõplik kuju on:

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

ln H_ham = ln P(ham) + ln P(w₁|ham) + ... + ln P(w_n|ham).

Kus w_i on sõna klassifitseeritavast kirjast ja n nende sõnade arv antud kirjas mis leidusid vähemalt ühes kirjade klassis. Kui a > b siis ka log(a) > log(b), nii et logaritmilisel kujul hinnangute pealt saab juba lõpptulemuse välja lugeda.

Kirjad klassifitseerimiseks

Kiri 1

Subject: cleburne issues
daren , with megan gone i just wanted to touch base with you on the status of the enron payments owed to the cleburne plant . the current issues are as follows :
november gas sales $ 600 , 377 . 50
october payment to ena for txu pipeline charges $ 108 , 405 . 00
cleburne receivable from enron $ 708 , 782 . 50
less : november gas agency fees ( $ 54 , 000 . 00 )
net cleburne receivable from enron $ 654 , 782 . 50
per my discussions with megan , she stated that about $ 500 k of the $ 600 k nov gas sales was intercompany ( desk to desk ) sales , with the remainder from txu . are we able to settle any intercompany deals now ? are we able to settle with txu ?
additionally , you ' ll see that i included the oct txu payment in the receivable owed to cleburne also . this is because i always pay megan based upon the pipeline estimates in michael ' s file , even though they are not finalized until the next month . therefore in my november payment to enron , i paid ena for october ' s estimate , of which megan would have paid the final bill on 12 / 26 / 01 when it was finalized . however , i had to pay the october bill directly last month , even though i had already sent the funds to ena in november . therefore , i essentially paid this bill twice ( once to ena in nov & once to txu in dec ) . i deducted the november agency fees from these receivable totals to show the net amount owed to cleburne .
please advise as to the status of these bills . you can reach me at 713 - 853 - 7280 . thanks .

Kiri 2

Subject: immediate contract payment .
immediate contract payment . our ref : cbn / ird / cbx / 021 / 05
attn :
during the auditing and closing of all financial records of the central bank of nigeria ( cbn ) it was discovered from the records of outstanding foreign contractors due for payment with the federal government of nigeria in the year 2005 that your name and company is next on the list of those who will received their fund .
i wish to officially notify you that your payment is being processed and will be released to you as soon as you respond to this letter . also note that from the record in our file , your outstanding contract payment is usd $ 85 , 000 , 000 . 00 ( eighty - five million united states dollars ) .
kindly re - confirm to me if this is inline with what you have in your record and also re - confirm the information below to enable this office proceed and finalize your fund remittance without further delays .
1 ) your full name .
2 ) phone , fax and mobile # .
3 ) company name , position and address .
4 ) profession , age and marital status .
5 ) copy of drivers license i . d .
as soon as the above information are received , your payment will be made available to you via an international certified bank draft , which will be delivered to your doorstep for your confirmation . you should call my direct number as soon as you receive this letter for further discussion and more clarification . also get back to me on this e - mail address ( payment _ info _ 10 @ yahoo . com ) and ensure that you fax me all the details requested to my direct fax number as instructed .
best regards ,
prof . charles c . soludo .
executive governor
central bank of nigeria ( cbn )
tel : 234 - 1 - 476 - 5017
fax : 234 - 1 - 759 - 0130
website : www . cenbank . org
mail sent from webmail service at php - nuke powered site
- http : / / yoursite . com

Lisaülesanne

Järgnevad tegevusi võib proovida, need ei ole kohustuslikud.

• suvaliste kirjade klassifitseerimine - nõuab arvatavasti täiendavat eeltöötlust
• sõnade parem filtreerimine - täienda stopwords funktsiooni.
• arvuta logaritmiliste hinnangute pealt lõplik tõenäosus (vihje - e^a / e^b = e^a-b)