1 Analiza spójności dokumentów z wykorzystaniem ukrytego kontekstu na przykładzie bazy e-mail'i firmy Enron. Marek Kopel Zakład Systemów Informacyjnych Instytut Informatyki Stosowanej Politechnika Wrocławska

2 Plan wystąpienia ➢ spójność dokumentów ➢ ukryty kontekst ➢ semantyczne informacje o relacjach między autorami dokumentów WWW ➢ siła relacji między autorami ➢ baza e-mail'i Enron ➢ adaptacja metody do Enron'a ➢ inne badania na Enron'ie 2

3 Czego dotyczy analiza spójności? ● głównie dokumentów tekstowych w WWW ● nie wykluczam MM, ale ich wyszukiwanie to wciąż nierozwiązany problem (osobne badania) 3

4 Dokument WWW From Wikipedia, the free encyclopedia ● A web page or webpage is a resource of information that is suitable for the World Wide Web and can be accessed through a web browser. This information is usually in HTML or XHTML format, and may provide navigation to other web pages via hypertext links. ● Web document is a similar concept to web page, except with the following distinctions: – a web page is traditionally transferred using the HTTP or the HTTPS protocol; – a web document may be transferred over any of various Internet communication protocols for use in various kinds of client applications; – a web page is ordinarily restricted to connote HTML, XHTML or another markup language as the primary presentation specficiation; – a web document may consist of any type of document type or MIME Content-Type or file format; – a web document may consist of a compound document, or an attachment to another document or message; and – a web document is a more expansive definition, which includes the traditional definition for 'web page'. 4

5 Spójność dokumentów 3-stopniowa spójności dokumentów: ● podobieństwo treści (content similarity) – znane metody, np. tf-idf ● sąsiedztwo linków, (hyperlink neighbourhood based consistency) – wcześnejsze prace autorskie – Cz. Daniłowicz, M. Kopel: “Analysis Method Of Coherency And Topical Relevancy For Web Document Collections” (ISAT’03) – M. Kopel: “Identyfikacja Spamu Na Podstawie Analizy Spójności Wiadomości” (MiSSI’04) – M. Kopel, Cz. Daniłowicz: “Method of Completing the Consistency Graph of a Hyperlinked Document Collection” (MTAII’04) – M. Kopel, Cz. Daniłowicz: “Measuring The Importance Of Concepts And Relations Between The Concepts In A Hypertext Collection” (ISAT’04) ● ukryty kontekst (semantic based latent context consistency) – obecnie prowadzone badania 5

6 Ukryty kontekst ● kontekst dokumentów wynikający w semantycznej informacji o relacji pomiędzy autorami/czytelnikami dokumentów ● "you write what you read" – intuicyjna teoria, “an old saw” – rozprawa doktorska Maloney, Henry B., English Journal, v74 n5 p28-32 Sep 1985 ● znane (i stosowane) standardy – publikowania relacji między użytkownikami: FOAF, XFN – wiązania dokumentów komentujących z komentowanymi - Linkback 6

7 Spójności dokumentów na podstawie relacji między autorami ● Artykuły np. n/t Baz Danych będą bardziej spójne, jeśli pisane przez naukowców z jednego zakładu niż z 2 uczelni na różnych kontynentach, bo np. dotyczą wspólnego modelu baz, przyjmują podobne założenia, definicje, słownictwo, mają wspólne środowisko do weryfikowania swoich teorii. ● Ale z drugiej strony: osoby o takich samych zainteresowaniach naukowych będą częściej śledziły i komentowały nawzajem swoje blogi, niż ludzi ze swojego otoczenia (fizycznego) zajmujących się innymi rzeczami. 7

8 FOAF ● “Friend of a friend” ● ● FOAF Vocabulary Specification – Namespace Document 27 July 2005 ● FOAF Explorer, foafnaut – human-readable ● FOAFBulletinBoard – spis powrzechny 8

9 XFN ● XHTML Friends Network ● Jan Kowalski ● rubhub – wyszukiwarka relacji między autorami stron domowych (blogów) 9

10 Linkback ● ewolucja: SCI → ACI → Linkback (blogi) ● 3 rodzaje (porównanie):porównanie – Refback – Trackback – Pingback ● powiadamianie autora komentowanego/recenzowanego dokumentu ● odsyłacze do komentarzy (nawet na innych serwerach) dołączane do pierwotnego dokumentu 10

11 Siła relacji (1) Siła relacji między 2 użytkownikami zależy od: ● komunikacji między nimi (e-mail, IM, VoIP,...) ● komentowania/powoływania się na swoje dokumenty (linkback) ● jawnej deklaracji relacji z drugim użytkownikiem przez foaf.rdf i/lub XFN'owy odsyłacz 11

12 Siła relacji (2) ● oznaczenia: – A, B – autorzy – c – miara komunikacji autora A do B – l – miara komentarzy autora A do dokumentów autora B – f – miara typu relacji autora A do B – rs(A→B) - siła relacji autora A do autora B (niesymetryczna) rs(A→B) =f(A, B, c, l, f) (wstępna wersja) 12

13 Dalsze badania ● sformułować szczegółową definicję siły relacji między autorami ● ustalić własności siły relacji – twierdzenia (dowody) ● zaplanować eksperymenty – zbiory danych dla dokumentów WWW (np. dostępny FOAF) 13

14 Enron Email Dataset ● dane zebrane i przygotowane przez CALO Project (A Cognitive Assistant that Learns and Organizes) ● 619,446 e-mail'i w 158 skrzynkach pocztowych pracowników Enron (firma energetyczna w USA, która zbankrutowała w 2001 r.) ● dane opublikowane przez Federal Energy Regulatory Commission podczas śledztwa, później zakupione przez by Leslie Kaelbling @ MIT, poprawiona ich integralność i udostępnione do badań ● plik March 2, 2004 Version of dataset (about 400Mb, tarred and gzipped) spod http://www.cs.cmu.edu/~enron/http://www.cs.cmu.edu/~enron/ 14

15 Przygotowanie zbioru (1) ● enron_mail_030204.tar.gz wielkości 367 MB po rozkompresowaniu i rozpakowaniu - 2,6 GB ● import katalogów z plikami do bazy MySQL (skrypt PHP - MIME parser) ● problem z czasem → czas lokalny + strefa czasowa ● problem z wielo-adresatem → dodatkowe pole o liczbie adresatów ● problem z duplikatami np. w sent_items nadawcy i inbox odbiorcy → import tylko katalogów sent_items (101 876 maili w 12 min.) 15

16 Przygotowanie zbioru (2) ● nadal problem z wielo-adresatem: – nie rozbijać – trudniej identyfikować pojedyncze osoby (adresy) – rozbijać na osobne rekordy – trudniej identyfikować pojedyncze maile → wersja 2 z 2 tabelami: ADR i SENT (import 55 min.) ● po rozbiciu wielo-adresata: – dziwne adresy, typu: [email protected] – problem jak automatycznie powiązać adresy typu: ● [email protected] ● [email protected] ●

17 Wstępne analizy ● Najwięcej wysłanych przez /user: – '[email protected]', 8877, '[email protected]', 7148 ● Najwięcej przysłanych do /user: '[email protected]', 2697 – Vince Kamiński - “Company risk analyst (...), the in-house risk- management genius (...)” ● 232 różnych nadawców (a tylko 150 skrzynek?) ● 15 340 różnych odbiorców (wliczając 6997 kombinacji multi-adresatów - najczęstsza kombinacja do 95 adresatów użyta przez 102 nadawców) ● Analiza czasowa – Najczęściej wysyłane o 8”, najrzadziej o 21” (czasu lokalnego) – Najwięcej w 2001r. i 2000r. – Najwięcej w 16 tygodniu 2001 – Najczęściej we wtorek, najrzadziej w sobotę – Najczęściej w styczniu, najrzadziej w lipcu 17

18 Adaptacja metody dla Enron (1) ● “martwa baza” ● skrzynka e-mail to nie WWW ● na siłę relacji ma wpływ tylko komunikacja między autorami (liczba wysłanych e-mail'i) 18

19 Adaptacja metody dla Enron (2) ● przechodniość siły relacji ● badamy relację A → C, ale A nie wysyłał nic C ● ale wykorzystując teorię FOAF i wiedzę, że rs(A → B) i rs(B → C) są niezerowe może my aproksymować przechodnią siłę relacji: 19

20 Pomysł aplikacji ● maildir wystawiony na WWW i zaindeksowany przez Google (Google Co-op Custom Search Engine) ● Google AJAX Search API (Beta) jako podstawa interfejsu do przeszukiwania maildir'a ● re-ranking wyszukanych e-mail'i na bazie siły relacji między nadawcami – po wybraniu e-mail'a lista kolejnych jest sortowana tak, że najpierw są e-maile tego samego nadawcy i nadawców w najsilniejszej z nim relacji ● filtrowanie wyszukanych e-mail'i uwzględniając ich spójność – długość listy wyszukanych e-mail'i można regulować suwakiem spójności 20

21 Inne badania na bazie Enron ● analiza statystyczna – J. Shetty, J. Adibi, The Enron Email Dataset, Database. Schema and Brief Statistical Report. 2004 http://www.isi.edu/~adibi/Enron/Enron_Dataset_Report.pdf http://www.isi.edu/~adibi/Enron/Enron_Dataset_Report.pdf ● klasyfikacja wiadomości z 7 skrzynek pocztowych do folderów tematycznych na postawie 4 klasyfikatorów: MaxEnt, Naive Bayes, SVM and Winnow – R. Bekkerman, A. McCallum, G. Huang: Automatic Categorization of Email into Folders: Benchmark Experiments on Enron and SRI Corpora. CIIR Technical Report IR-418 2004 ● SNA do wykrycia ról pracowników, MD5 m.in. do identyfikacji duplikatów e-mail'i (250 484 unikatowych z 517 431) – A Corrada-Emmanuel, A McCallum, X Wang: Language Use in a Social Network: The Enron Email Dataset. CNLP Seminars, 2004 – A. Corrada-Emmanuel: Enron Email Dataset Research http://ciir.cs.umass.edu/~corrada/enron/http://ciir.cs.umass.edu/~corrada/enron/ ● klastering i wizualizacja sieci społecznej właścicieli skrzynek pocztowych w enron.com – J. Heer: Exploring Enron. Visual Data Mining of E-mail. UC Berkeley Enron Email Analysis Project. 2004. http://jheer.org/enron/http://jheer.org/enron/ 21

22 Baza Enron w produktach komercyjnych ● Enron Explorer jako reklamówka produktu SONAR platform (Social Networks And Relevance) firmy Trampoline Systems Enron Explorer – wyszukiwarka e-mail'i z mapowaniem do motywów tematycznych (theme) i z java'ową wizualizacją sieci społecznej ● Enron jako przykład InBoxer Anti-Risk Appliance - AJAX'owej aplikacji do wykrywania potencjalnych zagrożeń wynikających z korespondencji firmowej Enron – m.in. możliwości grupowania/filtrowania wiadomości na podstawie semantyki wiadomości, np. wiadomości prywatne, dot. medycyny czy z “niestosowną treścią” (żarty, łańcuszki,...) 22

23 Możliwości wykorzystania bazy Enron ● Analizy dotyczące chronologii (dynamika sieci społecznej) ● Wpływ częstości i regularności komunikacji na siłę relacji ● Uszczegółowienie relacji między pracownikami na podstawie wątków wiadomości (threads) ● Budowa ontologii na podstawie folderów tematycznych ● Identyfikacja spamu na podstawie folderów deleted_items 23

24 Dziękuję pytania? więcej? >> blog naukowy marekopel.wordpress.com 24