Opdracht 1: Bayesiaanse Spam Filter Het doel van deze opdracht is het ontwerpen van een eenvoudige spam filter op basis van een Bayesiaans Netwerk. Je zal het model implementeren in Netica en het toepassen op twee voorbeelden. Om te bepalen of een binnenkomende mail als ’spam’ of ’niet spam’ geklasseerd moet worden, zal je spam filter rekening houden met
het voorkomen van bepaalde woorden in de body van de mail, de header van de mail, het programma waarin de mail geschreven werd, de achtergrondkleur, of de mail al dan niet naar een mailinglijst gestuurd werd. Hieronder krijg je stap voor stap de informatie die je nodig hebt om de structuur van het Bayesiaanse Netwerk vast te leggen en de kansentabellen bij elke knoop in het netwerk in te vullen. Lees deze informatie zeer aandachtig. De eigenlijke opdracht volgt daaronder. 1. Kritieke woorden in de body van de mail Bij de aanvang van deze stap zou je de mails in je mailbox in principe moeten verdelen in twee mappen: een map met alle mails die je (persoonlijk) als ’spam’ beschouwt, en een tweede map voor je ’niet spam’ mails. Voor deze opdracht vereenvoudigen we deze stap. In de directory I:/GT/Export/roroe/2TI/SN - Operationele analyse/Les 5/ vind je verdeeld over de mapjes ’spam’ en ’nonspam’ 20 tekstbestanden (.txt): 10 tekstbestanden van de vorm spam*.txt en 10 tekstbestanden van de vorm nonspam*.txt. We beschouwen de 10 spam*.txt bestanden als de body’s van de spam mails in je mailbox en de 10 nonspam*.txt bestanden als de body’s van de niet spam mails in je mailbox. Als bijkomende vereenvoudiging wordt er in deze mails een woordenschat met slechts 10 woorden gebruikt: ’offer’, ’account’, ’free’, ’movie’, ’mailing’, ’student’, ’sex’, ’school’, ’lessons’, ’university’. (a) Het is de bedoeling dat je voor beide klasse van mails (’spam’ en ’niet spam’) de frequentie van elk van die 10 woorden bepaalt. Je kan daarbij volgend hulpmiddeltje gebruiken: http://home.wxs.nl/˜hklein/zipf/zipf.htm Voor de mails uit de klasse ’spam’: open de 10 spam*.txt bestanden, kopieer de tekst uit elk bestand en breng ze samen in het venstertje op bovenstaande webpagina. Als je het tooltje compileert, krijg je een frequentietabel voor de 10 woorden en het totaal aantal woorden in de 10 spam*.txt bestanden. Met deze gegeven kan je de kans (in procenten) bepalen waarmee elk van die 10 woorden opduikt in een spam mail. Herhaal dit voor de mails uit de klasse ’niet spam’. Op het einde van deze stap heb je dus twee frequentietabellen. Voeg deze toe aan je oplossingen. (b) Bij het ontwerpen van je Bayesiaans netwerk zal elk van de 10 woorden overeenkomen met 1 knoop. Al deze knopen hangen rechtstreeks af van de knoop ’spam of niet’. Om de kansentabellen van deze 10 knopen in te vullen, kan je gebruik maken van de twee frequentietabellen. (Gebruik 2 cijfers na de komma.) Operationele analyse - Les 5 - Opdrachten
19/4/2010
Opmerking: omdat een Bayesiaans spam filter vertrekt van een persoonlijke lijst met spam mails en niet spam mails, zal een Bayesiaanse spam filter doorheen de tijd een filter worden die voor de persoon in kwestie steeds betert filtert tussen spam mails en niet spam mails. Nieuwe inkomende mails zullen op basis van de filter geklasseerd worden als spam of niet spam. De frequenties van de woorden in deze nieuwe mails worden steeds toegevoegd aan de bestaande lijst. De spam filter leert dus voortdurend bij en wordt dus persoonlijker telkens wanneer er een nieuwe mail arriveert. 2. De header van de mail De header van een mail vertelt ons vaak veel over de kans dat een mail spam is of niet. Omdat we in deze opdracht een eenvoudige spam filter bouwen zullen we in dit geval alleen (laten) nagaan of de header van de mail ’xxx’ bevat of niet. Veronderstel dat 80% van de spam mails ’xxx’ bevat in de header, terwijl dit voor niet spam mail 5% bedraagt. 3. Het programma waarin de mail geschreven werd Ter vereenvoudiging brengen we alleen in rekening of een mail geschreven is in Outlook Express of niet. Veronderstel dat 70% van de binnenkomende mails in Outlook Express geschreven is. 4. De achtergrondkleur We beschouwen (slechts) vijf mogelijke achtergrondkleuren: rood, groen, zwart, wit en blauw. Veronderstel dat de achtergrondkleur van een mail afhangt van drie mail eigenschappen: de mail is spam of niet, de header bevat ’xxx’ of niet, de mail is geschreven in Outlook Express of niet.
Gebruik de volgende kansentabel bij het construeren van je Bayesiaans Netwerk: spam waar waar waar waar vals vals vals vals
’xxx’ in header waar waar vals vals waar waar vals vals
Outlook Express waar vals waar vals waar vals waar vals
rood
groen
zwart
wit
0.4 0.4 0.35 0.3 0.75 0.75 0.4 0.05
0.3 0.3 0.28 0.3 0.10 0.05 0.25 0.05
0.05 0.05 0.01 0.05 0 0.05 0.05 0.10
0.05 0.1 0.01 0.05 0.05 0.05 0.10 0.75
5. De mailing werd al dan niet naar een mailinglijst verstuurd Spam mails worden vaak niet naar 1 persoon, maar naar een volledige mailinglijst gestuurd. Veronderstel dat 40% van de binnenkomende mails naar een mailinglijst worden verstuurd en 60% niet. 6. Veronderstel tenslotte dat de kans dat een mail een spam mail is rechtstreeks afhangt (en alleen afhangt) van het feit dat de mail naar een mailinglijst werd verstuurd of niet. Veronderstel dat 70% van de mails op een mailinglijst spam mails zijn, terwijl dit voor de andere mails (niet verstuurd naar een mailinglijst) 40% bedraagt.
Operationele analyse - Les 5 - Opdrachten
19/4/2010
Gebruik deze informatie nu om de volgende opdrachten uit te voeren. 1. Opdracht 1.1 (a) Construeer een Baysiaans netwerk in Netica dat model staat voor een eevoudige spam filter. Hoeveel knopen heb je nodig? Hoe zijn de knopen onderlingen verbonden? Vul de kansentabel bij elke knoop in. (b) Houd het Netica bestand (.dne) goed bij. (c) Testen van je netwerk: veronderstel dat er een nieuwe mail binnenkomt die geschreven is in Outlook Express, met groene achtergrond, geen ’xxx’ in de header en met de woorden ’offer’ en ’account’ in de body. Gebaseerd op deze gegevens, wat is de kans dat deze mail spam is? (Als je netwerk correct is opgebouwd, zou je een kans van 71.4% moeten vinden.) 2. Opdracht 1.2 (a) In hetzelfde mapje als de omschrijving van deze opdracht vind je ook het bestand ’mail1.txt’. Veronderstel dat deze tekst de body is van een binnenkomende mail. Gebruik opnieuw het tooltje op http://home.wxs.nl/˜hklein/zipf/zipf.htm om de frequenties van de woorden in ’mail1.txt’ te bepalen. Welk zijn de drie woorden met de grootste frequentie? Zet de toestand van deze woorden in je Bayesiaans Netwerk op ’WAAR’ en laat de andere zeven ’woordknopen’ onaangeroerd. Veronderstel dat de achtegrondkleur rood is. (b) Wait is de kans dat mail1 spam is? Zouden we deze mail best als spam klasseren? (c) Veronderstel nu bovendien dat de mail niet in Outlook Express geschreven is. Verandert dit iets aan de kans dat deze mail spam is? Kan je dit verklaren? (d) Voeg je conclusies en bevindingen toe aan je oplossingen. 3. Opdracht 1.3 (a) Veronderstel dat het tekstbestand ’mail2.txt’ de body bevat van een tweede binnenkomende mail. Veronderstel dat we ook volgende bijkomende eigenschappen van mail2 kennen: de achtergrondkleur is rood, de mail is geschreven in Outlook Express en werd verzonden naar een mailinglijst. Zet opnieuw de toestand van de drie woorden met de grootste frequentie op ’TRUE’ en laat de zeven andere ’woordknopen’ onaangeroerd. (b) Wat is de kans dat mail2 spam is of niet? Zouden we deze mail best als spam klasseren? (c) Voeg je conclusies en bevindingen toe aan je oplossingen. 4. Opdracht 1.4 (a) Omdat onze spam filter berekend heeft dat mail1 vermoedelijk een spam mail is, kunnen we de woorden uit mail1 gebruiken om de lijst met frequenties van woorden in spam mails te updaten. (b) Voeg dus de woorden van mail1 toe aan de lijst van de 10 spam*.txt bestanden en gebruik opnieuw de internettool om de kans (in procent) te bepalen dat ´e´en van de 10 woorden opduikt in een spam mail. Deze keer zijn deze percentages dus niet alleen gebaseerd op de 10 spam*.txt bestanden maar ook op het mail1.txt bestand.
Operationele analyse - Les 5 - Opdrachten
19/4/2010
(c) Gebruik deze nieuwe lijst om de kansentabellen in de 10 ’woordknopen’ van je Bayesiaans Netwerk te updaten. Geef dit nieuwe model ook een nieuwe naam en houd ook dit Netica bestand (.dne)goed bij. (d) Gebruik dit nieuwe model om op nieuw de kans te bepalen dat mail2 spam is. Zouden we deze mail nu best als spam klasseren of niet? (e) Verklaar dat dit betekent dat onze Bayesiaans spam filter bijgeleerd heeft en persoonlijk wordt. (f) Voeg je conclusies en bevindingen toe aan je oplossingen. 5. Opdracht 1.5 Doe een paar suggesties voor eigenschappen (knopen) die je zou kunnen toevoegen aan je Bayesiaanse spam filter? Hoe zijn deze knopen verbonden met de andere knopen? Voeg je suggesties toe aan je oplossingen. 6. Opdracht 1.6 Uiteraard proberen spammers ook Bayesiaanse spam filters te omzeilen. Een gekende techniek heet ’Bayesian poisoning’. Leg kort uit wat men hieronder verstaat.
Operationele analyse - Les 5 - Opdrachten
19/4/2010
Opdracht 2: Troubleshooter met ’repair actions’ en ’questions’ In deze opdracht bereken je de te verwachten kost voor een aantal strategie¨en om een probleem te verhelpen. Naast het uitvoeren van acties (’repair actions’), kunnen er nu ook vragen (’questions’) gesteld worden. 1. Open het Netica bestand I:/GT/Export/roroe/2 TI/SN -Operationele analyse/Les 5/Netica/Netica 1.12/Oef/Lichte print3.dne 2. Dit bestand bevat een Bayesiaans netwerk dat model staat voor een printprobleem waarbij de tekst te licht wordt afgedrukt. Dit model voldoet aan de volgende vrij algemene voorwaarden: er is 1 ’probleemknoop’ met de verschillende mogelijke oorzaken (fi ) van het probleem er zijn ’repair actions’ aj verbonden met de probleemknoop, kost caj er zijn vragen qk (’questions’) verbonden met de probleemknoop, kost cqk er is een ’repair action’ acs die elke oorzaak herstelt met kost ccs (’call service’)
3. Veronderstel dat in dit voorbeeld: ca1 = 2, ca2 = 1, ca3 = 5, ca4 = 10, ca5 = 2, ca6 = 1, ccs = 50, cq1 = 3, cq2 = 1, cq3 = 2. 4. Bereken de te verwachten kost EC(S1 ) voor onderstaande strategie S1 .
A3 = ‘ja’
A4 = ‘ja’
A3
Acs
A4
Q1 = ‘nee’
A3 = ‘nee’
A4 = ‘nee’
Q1 Q1 = ‘ja’
A5 = ‘nee’
A5
A6
A5 = ‘ja’
A6 = ‘nee’
Acs
A6 = ‘ja’
w
.d
o c u -tr a c k
om
ww
D EM O
VE
R
SI
O
N
5. Bekijk ook eens de volgende strategie S2F:-Xeerst CHAN wordt vraag q2 gesteld. Als het antwoord GE D ’nee’ is, dan wordt vraag q3 gesteld. AlsP het antwoord op vraag q3 ’nee’ is, dan wordt actie a4 uitgevoerd. Indien het antwoord op vraag q3 ’ja’ is, dan wordt actie a5 uitgevoerd. Als het antwoord op vraag q2 ’ja’ is, dan wordt actie a5 uitgevoerd. Indien het probleem niet opgelost geraakt, wordt er eventueel een ’service call’ naar de helpdesk gedaan. .c
(a) Stel een schema op van de strategie S2 .
(b) Bereken de te verwachten kost EC(S2 ) voor de strategie S2 .
Operationele analyse - Les 5 - Opdrachten
19/4/2010
Opmerking In de praktijk zijn er in een troubleshooter vaak veel meer mogelijke oorzaken, acties en vragen. De structuur van het onderliggende Bayesiaans netwerk is dan ook veel ingewikkelder. Bekijk bijvoorbeeld eens het netwerk I:/GT/Export/roroe/2 TI/SN - Operationele analyse/Les 5/printer troubleshooting.jpg Indien geen extra voorwaarden worden opgelegd, bestaat er geen algoritme meer om de optimale strategie expliciet te berekenen. Er bestaan wel methodes om een strategie te vinden die de optimale strategie vrij goed benaderd. Een voorbeeld van een dergelijke commerci¨ele troubleshooter kan je vinden op http://demo.dezide.com/staff/util/switchLanguage.do?lang=english Probeer bij wijze van voorbeeld eens de ’Internet Connection Troubleshooter’ of de ’Bad Coffee’ troubleshooter. In de versie ’normal’ krijg je alleen vragen en acties voorgeschoteld met de bedoeling om het probleem op een effici¨ente manier op te lossen. In de versie ’expert’ krijg je ook de vragen te zien gerangschikt volgens toenemende kost. Je krijgt ook op elk moment de mogelijke oorzaken en oplossingen te zien gerangschikt volgens dalende kansen en effici¨entie. In dergelijke commerci¨ele troubleshooters krijg je als gebruiker zelden het onderliggende Bayesiaanse netwerk te zien. Maar het is er wel en het vorm zelfs de kern van de troubleshooter!
Operationele analyse - Les 5 - Opdrachten
19/4/2010
