Raport do projektu z przedmiotu Sztuczna Inteligencja
Marek Szczepaniak
Wrocław, 23 czerwca 2008
Celem projektu było stworzenie aplikacji umożliwiającej rozpoznawanie autora tekstu. Zadaniem polega na przyporządkowaniu do niepodpisanego tekstu jednego z wcześniej zdefiniowanych autorów. Dla każdego z autorów jako dane uczące wykorzystywane są napisane przez niego wiadomości.
Analizie poddane zostały posty z forum studentów informatyki, a więc krótkie wypowiedzi.
Proces przyporządkowywania autora do tekstu można podzielić na trzy główne etapy.
Dane są normalizowane (wielkość liter, białe znaki) oraz usuwane są elementy mogące zakłócić klasyfikację. W przypadku rozpatrywanych danych usunięte zostały tagi formatujące BBCode oraz takie elementy jak cytowania innych postów czy wklejone kody źródłowe. Usunięte zostały również wiadomości krótsze niż 50 znaków.
Dla każdej z wypowiedzi utworzono wektor cech go opisujących. Wśród możliwych do użycia cech tekstu są:
W przypadku słów i n-gramów słów możliwe jest wcześniejsze przeprowadzenie stemmingu czyli sprowadzenie słów do form bazowych (np. Ala ma kota zostanie zastąpione Ala mieć kot).
Aby nadać cechom wagi odpowiednie do ilości informacji, które niosą wykorzystano miarę TF-IDF (Term Frequency - Inverse Document Frequency).
Do klasyfikacji użytko algorytmu k-NN (k-Nearest Neighbor). Jako miara podobieństwa tekstów została użyta odległość kosinusowa czyli kosinus kąta pomiędzy wektorami cech opisującymi dokumenty.
Aplikację zostałą zaimplementowana w języku Java (w wersji SE 6.0). Dane uczące oraz testowe ładowane są z bazy MySQL. Do stemmingu wyrazów wykorzystano bibliotekę morfologik-stemming.
Do testów wybranych zostało losowo 20 autorów. Aby nierównomierny rozkład danych nie zaburzył wyników dla każdego autora losowo wybrano 500 napisanych przez niego postów. 490 z nich posłużyło jako dane uczące, 10 jako testowe. Łącznie dane uczące liczyły 9800 postów, dane testowe 200.
Aplikacja jako wynik zwracała raport ze statystykami ilości poprawnie rozpoznanych tekstów. Poniżej przykładowe wyniki.
| autor | poprawne | skuteczność |
|---|---|---|
| 3 | 2 | 20% |
| 4 | 2 | 20% |
| 5 | 4 | 40% |
| 6 | 9 | 90% |
| 10 | 0 | 0% |
| 16 | 3 | 30% |
| 17 | 2 | 20% |
| 19 | 2 | 20% |
| 25 | 5 | 50% |
| 29 | 3 | 30% |
| 33 | 1 | 10% |
| 34 | 2 | 20% |
| 42 | 2 | 20% |
| 54 | 3 | 30% |
| 62 | 7 | 70% |
| 67 | 0 | 0% |
| 86 | 6 | 60% |
| 276 | 2 | 20% |
| 302 | 8 | 80% |
| 725 | 7 | 70% |
| 70 | 35% |
| autor | poprawne | skuteczność |
|---|---|---|
| 2 | 4 | 40% |
| 3 | 5 | 50% |
| 4 | 2 | 20% |
| 5 | 1 | 10% |
| 6 | 7 | 70% |
| 10 | 1 | 10% |
| 16 | 3 | 30% |
| 17 | 5 | 50% |
| 19 | 3 | 30% |
| 25 | 3 | 30% |
| 29 | 8 | 80% |
| 33 | 1 | 10% |
| 34 | 2 | 20% |
| 42 | 2 | 20% |
| 54 | 4 | 40% |
| 62 | 6 | 60% |
| 67 | 1 | 10% |
| 86 | 4 | 40% |
| 302 | 6 | 60% |
| 725 | 3 | 30% |
| 71 | 35,5% |
| autor | poprawne | skuteczność |
|---|---|---|
| 2 | 1 | 10% |
| 3 | 4 | 40% |
| 5 | 3 | 30% |
| 6 | 6 | 60% |
| 10 | 2 | 20% |
| 16 | 3 | 30% |
| 17 | 2 | 20% |
| 19 | 3 | 30% |
| 25 | 3 | 30% |
| 29 | 4 | 40% |
| 33 | 1 | 10% |
| 34 | 3 | 30% |
| 42 | 0 | 0% |
| 54 | 4 | 40% |
| 62 | 5 | 50% |
| 67 | 1 | 10% |
| 86 | 3 | 30% |
| 276 | 3 | 30% |
| 302 | 6 | 60% |
| 725 | 4 | 40% |
| 61 | 30,5% |
Średnia skuteczność jest w granicach 35%. Jak widać jakość klasyfikacji jest zależna od autora. Wiadomości niektórych łatwo rozpoznawać (np. użytkownicy 6, 302) w przypadku innych rezultaty były bardzo słabe (np. numery 33 i 67).
Kolejna tabelka prezentuje skuteczność w zależności od długości klasyfikowanej wiadomości.
| rozmiar postu (w znakach) | poprawnych | testowanych | skuteczność |
|---|---|---|---|
| 50-99 | 74 | 291 | 25% |
| 100-199 | 115 | 346 | 33% |
| 200-299 | 63 | 144 | 44% |
| 300-399 | 19 | 63 | 30% |
| 400-499 | 24 | 50 | 48% |
| 500-599 | 15 | 29 | 52% |
| 600-699 | 9 | 26 | 35% |
| 700-799 | 4 | 9 | 44% |
| 800-899 | 5 | 13 | 38% |
| 900-999 | 4 | 7 | 57% |
| 1000-1099 | 1 | 3 | 33% |
| 1100-1199 | 3 | 5 | 60% |
Najwięcej postów mieści się w granicy do 300 znaków czyli są to dość krótkie. Wśród dłuższych wiadomości skuteczność jest nieco lepsza od średniej. W przypadku najdłuższych wiadomości (powyżej 700 znaków) wyniki bywają różnie, głównie z powodu małej ilości długich tekstów zarówno w danych testowych jak i uczących.
Skuteczność algorytmu (oscylująca w granicach 35%) wydaje się na pierwszy rzut oka kiepska. W literaturze zagadnienia pojawiają się lepsze wyniki. Trzeba jednak pamiętać o tym, że zazwyczaj przypisywanie autorów jest wykonywane na długich tekstach. W pracach naukowych można znaleźć eksperymenty przeprowadzane na książkach, referatach czy esejach, głównie w języku angielskim. Są to dużo dłuższe teksty niż ok. 200 znakowe posty (czyli niewiele więcej niż zwykły SMS). Dodatkowym problemem jest różnorodność danych, baza zawiera zarówno wskazówki do zadań zapisane formalnym językiem matematycznym jak i luźne pogadanki na temat polityki. Kolejnym czynnikiem utrudniającym zadanie może być okres czasu z jakiego pochodzą dane, najstarsze posty datowane są na 2004 rok. W ciągu 4 lat edukacji na studiach użytkownikowi mógł się nieco zmienić styl czy zasób słownictwa. Zniekształcenia danych moga powodować również takie z pozoru nieistotne rzeczy jak zmiana przeglądarki użytkownika na taką ze sprawdzaniem pisowni.
Wyniki nie są oszałamiające lecz na pewno wyraźne lepsze od losowej klasyfikacji (dającej skuteczność ok. 5%). Niestety brak prac poruszających analogiczne zagadnienie uniemożliwia porównanie wyników.