praca inzynierska.PDF

1. Imię i nazwisko studenta: Marcin Goławski

Nr albumu: 143224

Studia pierwszego stopnia

Forma studiów: stacjonarne

Kierunek studiów: Informatyka

Specjalność/profil: -

Imię i nazwisko studenta:
WOJCIECH STANISŁAWSKI

Nr albumu: 143351

Studia pierwszego stopnia

Forma studiów: stacjonarne

Kierunek studiów: Informatyka

Specjalność/profil: -

Imię i nazwisko studenta:
KRZYSZTOF ŚWIECZKOWSKI

Nr albumu: 143365

Studia pierwszego stopnia

Forma studiów: stacjonarne

Kierunek studiów: Informatyka

Specjalność/profil: -

Imię i nazwisko studenta: Artur Peplinski

Nr albumu: 137368

Studia pierwszego stopnia

Forma studiów: stacjonarne

Kierunek studiów: Informatyka

Specjalność/profil: -

PROJEKT DYPLOMOWY INŻYNIERSKI

Tytuł projektu w języku polskim: Równoległa kategoryzacja artykułów Wikipedii z użyciem metod
uczenia maszynowego
Tytuł projektu w języku angielskim: Parallel categorization of Wikipedia using machine learning
methods



Potwierdzenie przyjęcia projektu


Opiekun projektu
podpis
Kierownik Katedry/Zakładu
podpis

dr inż. Julian Szymański

Data oddania projektu do dziekanatu:

2. OŚWIADCZENIE
Imię i nazwisko: Marcin Goławski
Data i miejsce urodzenia: 22.12.1992, Gdańsk
Nr albumu: 143224
Wydział: Wydział Elektroniki, Telekomunikacji i Informatyki
Kierunek: informatyka
Poziom studiów: I stopnia - inżynierskie
Forma studiów: stacjonarne

Ja, niżej podpisany(a), wyrażam zgodę/nie wyrażam zgody* na korzystanie z mojego projektu
dyplomowego zatytułowanego: Równoległa kategoryzacja artykułów Wikipedii z użyciem metod
uczenia maszynowego
do celów naukowych lub dydaktycznych.
1


Gdańsk, dnia .................................. .....................................................
podpis studenta

Świadomy(a) odpowiedzialności karnej z tytułu naruszenia przepisów ustawy z dnia 4 lutego
1994 r. o prawie autorskim i prawach pokrewnych (Dz. U. z 2006 r., nr 90, poz. 631)
i konsekwencji dyscyplinarnych określonych w ustawie Prawo o szkolnictwie wyższym (Dz. U. z
2012 r., poz. 572 z późn. zm.),
2
a także odpowiedzialności cywilno-prawnej oświadczam, że
przedkładany projekt dyplomowy został opracowany przeze mnie samodzielnie.

Niniejszy projekt dyplomowy nie był wcześniej podstawą żadnej innej urzędowej procedury
związanej z nadaniem tytułu zawodowego.

Wszystkie informacje umieszczone w ww. projekcie dyplomowym, uzyskane ze źródeł pisanych i
elektronicznych, zostały udokumentowane w wykazie literatury odpowiednimi odnośnikami
zgodnie z art. 34 ustawy o prawie autorskim i prawach pokrewnych.

Potwierdzam zgodność niniejszej wersji projektu dyplomowego z załączoną wersją elektroniczną.


Gdańsk, dnia .................................. .....................................................
podpis studenta

Upoważniam Politechnikę Gdańską do umieszczenia ww. projektu dyplomowego w wersji
elektronicznej w otwartym, cyfrowym repozytorium instytucjonalnym Politechniki Gdańskiej oraz
poddawania jego procesom weryfikacji i ochrony przed przywłaszczaniem jego autorstwa.
Gdańsk, dnia ................................. .....................................................
podpis studenta

*) niepotrzebne skreślić



1
Zarządzenie Rektora Politechniki Gdańskiej nr 34/2009 z 9 listopada 2009 r., załącznik nr 8 do instrukcji
archiwalnej PG.

2
Ustawa z dnia 27 lipca 2005 r. Prawo o szkolnictwie wyższym:

Art. 214 ustęp 4. W razie podejrzenia popełnienia przez studenta czynu podlegającego na przypisaniu sobie autorstwa
istotnego fragmentu lub innych elementów cudzego utworu rektor niezwłocznie poleca przeprowadzenie postępowania
wyjaśniającego.

Art. 214 ustęp 6. Jeżeli w wyniku postępowania wyjaśniającego zebrany materiał potwierdza popełnienie czynu,
o którym mowa w ust. 4, rektor wstrzymuje postępowanie o nadanie tytułu zawodowego do czasu wydania orzeczenia
przez komisję dyscyplinarną oraz składa zawiadomienie o popełnieniu przestępstwa.

3. 3
STRESZCZENIE
Tematem pracy inżynierskiej jest implementacja aplikacji odpowiedzialnej za
klasyfikację danych tekstowych oraz analizę jej wydajności podczas zrównoleglania
poszczególnych operacji. Praca przedstawia wybrane zagadnienia teoretyczne i
implementacyjne z zakresu technik klasyfikacji danych, rozpraszania operacji a także walidacji
uzyskanych wyników. Obecnie istnieje wiele implementacji podobnych zagadnień, natomiast
poniższa praca przedstawia jedną z możliwości uzyskania korzystnej wydajności wraz z
zadowalającymi wynikami klasyfikacji.
W celu uzyskania zadowalających wyników nie tracąc jednocześnie na wydajności,
do klasyfikacji wektorów tekstów, został wykorzystany algorytm k najbliższych sąsiadów.
Natomiast odległość między obiektami jest definiowana poprzez podobieństwo cosinusowe. Do
procesu klasyfikacji zostały wprowadzone autorskie modyfikacje. Zostały one przedstawione
dokładnie w podrozdziale 2.1.3 natomiast analiza ich wyników znajduje się w rozdziale Ocena.
Głównym założeniem projektu jest zbadanie wpływu rozproszenia poszczególnych
procesów na wydajność klasyfikacji. Do implementacji podziału zadań oraz danych między
węzłami klastra zastosowaliśmy bibliotekę o nazwie Apache Hadoop. Procesy które
zdecydowaliśmy się rozproszyć pomiędzy węzły klastra to m.in. normalizacja tekstów do
wektorów danych, obliczenia podobieństw cosinusowych, folding a także kroswalidacja.
W ramach opracowania zagadnienia został przeprowadzony szereg testów
pokrywających tematy jakości i wydajności klasyfikacji. W trakcie testowania zauważono że
optymalną ilością najbliższych sąsiadów jest wartość oscylująca w granicach 1-5% ilości
wszystkich artykułów biorących udział w klasyfikacji. Dodatkowo zaobserwowano wąskie gardło
działania aplikacji znajdujące się na etapie walidacji skrośnej, i to tam należy szukać
usprawnień wydajności działania.
Implementacja aplikacji jest stabilna i w pełni skalowalna. Klasyfikacje można
przeprowadzić na dowolnym klastrze, o dowolnej liczbie węzłów oraz dowolnej wielkości zbioru
trenującego. Jedynym ograniczeniem użytkowym aplikacji jest czas wykonania niektórych
etapów klasyfikacji dla dużych zbiorów danych(>10000 artykułów). Stan aplikacji jest solidną
podstawą do dalszych prac badawczych w kierunku klasyfikacji danych tekstowych, a sama
implementacja jest przystosowana do ewentualnych ulepszeń w kierunku jakości i wydajności.
Praca dyplomowa została zrealizowania przez czterech współautorów. Udział w
tworzeniu poszczególnych rozdziałów wygląda następująco:
● Wojciech Stanisławski - Udział w rozdziałach 2.2.1, 3.1, 3.2.1, 4 oraz indywidualnie
rozdziały 3.3.2, 3.4.2, 3.5
● Marcin Goławski - Udział w rozdziale 4 oraz Indywidualnie rozdział 2.1
● Krzysztof Świeczkowski - Udział w rozdziałach 2.2.1, 3.1, 3.2.1, 4 oraz indywidualnie
rozdziały 2.2.2, 3.2.2, 3.4.1
● Artur Peplinski - Udział w rozdziałach 2.1.4 , 3.1.1 i 4 oraz 2.2.3, 2.2.4, 3.3.1
Słowa kluczowe: Big data, Apache Hadoop, klasyfikacja KNN, Wikipedia

4. 4
ABSTRACT
The topic of this engineering diploma project is the implementation of the application
classifying text data and analysis of its performance during parallelization. This diploma
presents chosen theoretical and implementational issues concerning techniques of data
classification, operation dispersion and validation of gathered results. To this day, many
implementations of similar problems were presented, however this project focuses on one
chosen method, which promises to reach high performance and satisfactory classification
results.
In order to achieve satisfactory results without a big decrease in performance, a k-
nearest neighbors algorithm was used for classification of vectors describing articles. Distance
between objects is defined by cosine similarity. Custom modifications have been introduced to
the classification process. They are described in detail in subsection 2.1.3 and the results are
analyzed in chapter Evaluation.
The main purpose of this thesis is the analysis of influence of distributed computing
on classification performance. Software library called Apache Hadoop was used for task and
data distribution between cluster nodes. Processes that we have decided to distribute are
normalization of texts into data vectors, calculating cosine similarity, folding and cross
validation.
As part of the elaboration on the topic, a series of thorough tests of quality and
efficiency of classification were conducted, during which it was concluded that the optimal
quantity of nearest neighbors is about 1-5% of all the articles taking part in classification. What
is more, a bottleneck was found. Increase in efficiency can probably be achieved by
improvement of the process of folding and cross validation.
Application is stable and fully scalable. Classification can be done on any cluster, with
any number of nodes and any size of the training dataset. The only usage restraint of the
application is execution time of some stages of classification for large data sets (>10000
articles). Current state of the application is a solid base for future research work towards text
data classification, and the implementation is prepared in such a way, that any future quality or
efficiency enhancements will be easy.
Engineering diploma project has been carried out by four co-authors. Contribution in
thesis is as following:
● Wojciech Stanisławski - Contribution in chapters 2.2.1, 3.1, 3.2.1, 4 and individually in
chapters 3.3.2, 3.4.2, 3.5
● Marcin Goławski - Contribution in chapter 4 and individually in chapter 2.1
● Krzysztof Świeczkowski - Contribution in chapters 2.2.1, 3.1, 3.2.1, 4 and individually in
chapters 2.2.2, 3.2.2, 3.4.1
● Artur Peplinski - Contribution in chapters 2.1.4, 4 and individually in chapters 2.2.3,
2.2.4, 3.3.1
Keywords: Big data, Apache Hadoop, KNN classification, Wikipedia

5. 5
SPIS TREŚCI
STRESZCZENIE ........................................................................................................................... 3
ABSTRACT ................................................................................................................................... 4
SPIS TREŚCI ................................................................................................................................ 5
WYKAZ WAŻNIEJSZYCH OZNACZEŃ I SKRÓTÓW .................................................................. 7
1. WSTĘP I CEL PRACY (Marcin Goławski, Artur Peplinski, Wojciech Stanisławski,
Krzysztof Świeczkowski) ............................................................................................................... 9
1.1 Nakreślenie problematyki .................................................................................................... 9
1.2 Cel pracy .............................................................................................................................. 9
1.3 Stan wiedzy obecnej ............................................................................................................ 9
1.4 Przedstawienie zawartości poszczególnych rozdziałów pracy ......................................... 10
2. TEORIA ................................................................................................................................... 11
2.1 Klasyfikator k-Najbliższych Sąsiadów (Marcin Goławski) ................................................ 11
2.1.1 Działanie klasyfikatora ................................................................................................ 11
2.1.2 Podobieństwo cosinusowe ......................................................................................... 12
2.1.3 Ulepszenia i optymalizacje ......................................................................................... 14
2.1.4 Kroswalidacja .............................................................................................................. 15
2.2 Rozproszenie obliczeń przy pomocy MapReduce ............................................................ 15
2.2.1 Struktura klastra (Wojciech Stanisławski, Krzysztof Świeczkowski) ......................... 15
2.2.2 Podział i przechowywanie plików (Krzysztof Świeczkowski) ..................................... 16
2.2.3 Faza mapowania (Artur Peplinski) ............................................................................. 16
2.2.4 Faza redukcji (Artur Peplinski) ................................................................................... 18
3. IMPLEMENTACJA .................................................................................................................. 19
3.1 Wykorzystane technologie (Wojciech Stanisławski, Krzysztof Świeczkowski) ................. 19
3.1.1 Hadoop........................................................................................................................ 19
3.1.2 Scala ........................................................................................................................... 19
3.2 Opis działania projektu ...................................................................................................... 20
3.2.1 Wstęp (Wojciech Stanisławski, Krzysztof Świeczkowski) .......................................... 20
3.2.2 Schemat działania projektu (Krzysztof Świeczkowski) .............................................. 21
3.3 Klasyfikacja artykułów do kategorii .................................................................................... 22
3.3.1 Wstęp (Artur Peplinski) .............................................................................................. 22
3.3.2 Zbiór danych (Wojciech Stanisławski) ....................................................................... 22
3.4 Rozproszenie na klastrze .................................................................................................. 22
3.4.1 Podział zbioru na węzły (Krzysztof Świeczkowski) .................................................... 23
3.4.2 Operacje, które zostały rozproszone (Wojciech Stanisławski) .................................. 23
3.4.2.1 Rozproszenie zliczania słów ................................................................................ 23
3.4.2.2 Rozproszenie kNN ............................................................................................... 24
3.4.2.3 Rozproszenie foldingu .......................................................................................... 25

6. 6
3.4.2.4 Rozproszenie kroswalidacji .................................................................................. 26
3.5 Instrukcja instalacji (Wojciech Stanisławski) .................................................................... 26
3.5.1. Przygotowanie klastra Apache Hadoop ..................................................................... 27
3.5.2. Konfiguracja parametrów programu .......................................................................... 27
3.5.3 Analiza pliku Wikidumps ............................................................................................. 29
3.5.4 Tryby działania klasyfikatora ....................................................................................... 30
4. OCENA (Marcin Goławski, Artur Peplinski, Wojciech Stanisławski, Krzysztof Świeczkowski)
.................................................................................................................................................... 33
4.1 Wydajność ......................................................................................................................... 33
4.1.2 Ocena wydajności algorytmów ................................................................................... 33
4.1.3 Zysk wydajności poprzez rozproszenie ...................................................................... 34
4.2 Poprawność przypisania do kategorii ................................................................................ 35
4.2.1 Porównanie jakości wybranych strategii progowania ................................................. 35
4.2.2 Jakość klasyfikacji przy rosnącej liczbie artykułów ..................................................... 37
5. PODSUMOWANIE (Marcin Goławski, Artur Peplinski, Wojciech Stanisławski,
Krzysztof Świeczkowski) ............................................................................................................ 38
5.1 Uzyskane efekty i osiągnięcia pracy .............................................................................. 38
5.2 Wnioski z przeprowadzonych badań ............................................................................. 39
5.3 Kontynuacja pracy ......................................................................................................... 40
WYKAZ LITERATURY ................................................................................................................ 41
WYKAZ RYSUNKÓW ................................................................................................................. 42
WYKAZ TABEL ........................................................................................................................... 43

7. 7
WYKAZ WAŻNIEJSZYCH OZNACZEŃ I SKRÓTÓW

big data
Określenie stosowane dla dużych zbiorów uporządkowanych, częściowo -
uporządkowanych lub nieuporządkowanych danych, z których można wyciągnąć
pewne zależności. Ich analiza, ze względu na rozmiar, wymaga dużej mocy
obliczeniowej.
lemma
Forma podstawowa wyrazu, używana do jego reprezentacji np. w słowniku.
Wyraz, który posiada wiele odmian, ma tylko jedną lemmę. [1]
węzeł klastra
Jednostka obliczeniowa wchodząca w skład klastra, udostępniająca swoją moc
obliczeniową na jego rzecz. Operacje dla poszczególnych węzłów przydziela
oprogramowanie sterujące klastrem.
repozytorium Zbiór zasobów cyfrowych dostępny w Internecie.
odległość,
metryka, miara
niepodobieństwa
obiektów

Funkcja określająca odległości pomiędzy poszczególnymi punktami
na przestrzeni euklidesowej.
faza uczenia
Moment działania programu, w którym baza danych przypadków trenujących jest
powiększana.
faza testowania
Moment działania programu, w którym przeprowadzana jest klasyfikacja,
wykorzystując do tego bazę danych przypadków trenujących.
klasa, kategoria
Reprezentacja artykułu jako przynależność do grupy przypadków reprezentującej
artykuły poświęcone podobnej tematyce.
wikikod
Zestaw znaczników, używanych do formatowania tekstu, przetwarzanych przez
oprogramowanie MediaWiki. MediaWiki jest wykorzystywane między innymi
w serwisie Wikipedia.
euclidean
distance
Metryka definiującą bezpośrednią odległość pomiędzy dwoma punktami
na płaszczyźnie euklidesowej, za pomocą zwykłej prostej geometrycznej.

8. 8
cosine similarity
Najpopularniejsza miara odległości dla reprezentacji wektorowej dokumentów. Jej
wartość wynosi kosinus kąta pomiędzy dwoma wektorami, które reprezentują
porównywane dokumenty.
majority voting
Technika wyboru najbardziej prawdopodobnego wyniku ze zbioru wszystkich
możliwych wyników. Miano najbardziej prawdopodobnego uzyskuje wynik
z największą liczbą wystąpień w zbiorze.

9. 9
1. WSTĘP I CEL PRACY
1.1 Nakreślenie problematyki
Ilość danych produkowanych przez ludzkość stale wzrasta. W 2014 roku globalny ruch
sieciowy wynosił 16TB na sekundę [2]. Coraz większy nacisk kładzie się na technologie
pozwalające wyciągać pewne zależności między danymi w sposób automatyczny. Jest to
możliwe dzięki zastosowaniu technologii rozproszonych oraz łączeniu komputerów w klastry,
aby uzyskać w ten sposób moc obliczeniową niezbędną do przetworzenia dużej ilości danych.
Aby programy uruchamiane na klastrach były w stanie wykorzystać całkowicie ich potencjał,
istotne jest jak najlepsze zrównoleglenie operacji wykonywanych przez program oraz danych, z
których program korzysta.
Uporanie się z problematyką przetwarzania wielkich zbiorów danych jest w tym
momencie jednym z głównych wyzwań dla branż technologicznych. Prowadzenie badań i
poszerzanie wiedzy w zakresie dziedziny Big Data prowadzi do bezpośrednich zmian i
ulepszeń w większości dziedzin życia, a w aspekcie naukowym prowadzić może do zdobycia
nowej wiedzy.
1.2 Cel pracy
W niniejszej pracy przedstawiono podejście do analizy big data na przykładzie
repozytorium Wikipedii. Repozytorium to, jest dynamicznie rozwijającym się zbiorem danych.
Sam Polski odłam w roku 2014 powiększył swoje zbiory o ponad 64 tysiące artykułów, czyli o
6,34% całości [3].
Zaimplementowano klasyfikator, który przy pomocy uczenia maszynowego, oraz
przetwarzania równoległego, jest w stanie zanalizować nowe artykuły i przypisać je do
istniejących kategorii artykułów Wikipedii. Istotny dla nas jest aspekt wydajnościowy oraz ocena
zysków czasowych podczas przetwarzania danych za pomocą klast ra obliczeniowego
utworzonego z domowych komputerów.
W niniejszym projekcie jakość klasyfikacji schodzi na drugi plan, podczas gdy główne
starania skupione są na polepszaniu wydajności i efektywnym wykorzystaniu klastrów w
skomplikowanych działaniach. Mimo tego aspekt jakości klasyfikacji nie został całkowicie
pominięty. W tym kierunku zostały wykonane konieczne czynności doboru odpowiedniej miary
niepodobieństwa obiektów oraz doboru algorytmu klasyfikacji. Dodatkowo zostały
wprowadzone niestandardowe techniki ulepszenia procesu Majority Voting naszego autorstwa.
Wszystkie aspekty jakości zostały podsumowane odpowiednimi testami weryfikującymi
poprawność zastosowanych technik.
1.3 Stan wiedzy obecnej
[4] Istnieje wiele zastosowań automatycznej klasyfikacji danych, dobrym przykładem
mogą być rozwiązania stosowane w klientach poczty e-mail przydzielające wiadomości do
konkretnych kategorii na podstawie jej treści. Najlepszym rozwiązaniem problemu kategoryzacji

10. 10
dokumentów tekstowych jest zastosowanie uczenia maszynowego. Wybranie odpowiedniej
metody uczenia maszynowego zależy m.in. od wielkości zbioru trenującego oraz od tępa jej
przyrostu. [2] Jednym z najczęściej wykorzystywanych przy kategoryzacji algorytmów jest
klasyfikator k-Najbliższych Sąsiadów.
[6] Na początku lat 2000’ zaczęło pojawiać się coraz większe zapotrzebowanie
na rozproszenie zasobów komputerowych między wiele węzłów. Rozpraszanie zasobów jest
technologią niezbędną do szybkiego zarządzania danymi w dużych i szybko rozwijających się
serwisach jak np. Google czy Facebook, gdzie użytkownicy każdego dnia generują setki
gigabajtów danych. Jednym z najlepszych wymyślonych rozwiązań, jest model o nazwie
MapReduce wykorzystywany w firmie Google i opisany przez dwóch pracowników tej firmy,
Jeffrey’a Dean’a i Sanjay’a Ghemawat’a. Model ten wykorzystywany jest do dziś przez
korporacje na całym świecie do rozpraszania operacji między komputerami. Powstały również
inne modele jak na przykład Bulk Synchronous Parallel, jednak nie są one tak popularne jak
MapReduce.
1.4 Przedstawienie zawartości poszczególnych rozdziałów pracy
W pierwszej kolejności w rozdziale Teoria zostały wyjaśnione podstawy teoretyczne
mechanizmów wykorzystanych w implementacji. Zostały zgłębione szczegóły działania
klasyfikatora, a w szczególności sposoby wyszukiwania podobieństw tekstu, ewentualne
ulepszenia i modyfikacje oraz kroswalidacja. Dodatkowo wyjaśnione zostały podstawy
rozpraszania aplikacji poruszając tematy struktury klastra, przechowywania danych oraz fazy
redukcji i mapowania.
W następnym rozdziale Implementacja zgłębione zostały szczegóły implementacji
wcześniej wymienionych zagadnień teoretycznych i bezpośrednie dostosowanie ich do
rozwiązania poruszonego problemu. Głównym tematem implementacji są sposoby
zrównoleglania technik przygotowania danych, klasyfikacji i kroswalidacji. Duża część rozdziału
została także poświęcona opisowi działania projektu, w którym wyjaśniony jest proces
przygotowania danych oraz przedstawiony został schemat współpracy poszczególnych sekcji
klasyfikatora.
W rozdziale Ocena zostały przedstawione uzyskane wyniki klasyfikacji. W pierwszej
kolejności zostały ukazane korzyści i starty jakościowe w zależności od przyjętych parametrów
wejściowych dotyczących k najbliższych sąsiadów i/lub zastosowanych ulepszeń klasyfikacji. W
głównej części rozdziału zostały zawarte wyniki testów sprawdzających wydajność działania
algorytmu. Szczególny nacisk położony został na aspekt korzyści wynikających ze
zrównoleglania poszczególnych zadań w czasie klasyfikacji. Wszystkie wyniki testów zostały
przedstawione w tabelach, oraz podsumowanie krótkim komentarzem.
W Podsumowaniu zawarto informacje odnośnie uzyskanych efektów i osiągnięć a
także przedstawiono wnioski z wykonanych pomiarów. Na zakończenie zostały poruszone
kwestie ewentualnych ścieżek rozwoju klasyfikatora i zastosowania otrzymanych wyników w
przyszłych projektach.

11. 11
2. TEORIA
2.1 Klasyfikator k-Najbliższych Sąsiadów
Jedną z najprostszych i najistotniejszych metod klasyfikacji jest zastosowanie
algorytmu K-najbliższych sąsiadów (k Nearest Neighbours, kNN). Algorytm ten zdobył swoją
popularność dzięki wysokiej interpretowalności, prostocie implementacji oraz szerokim
zastosowaniu w dziedzinach eksploracji danych i klasyfikacji[10].
2.1.1 Działanie klasyfikatora
Podstawowym założeniem klasyfikatora jest twierdzenie, że podobne problemy można
rozwiązać w podobny sposób. Posiadając wiedzę na temat rozwiązania najbardziej podobnego
problemu, stosujemy ją w celu rozwiązania nowego problemu. W ten sposób uzyskać można
działanie algorytmu 1NN.
W przypadku zastosowania k-NN, algorytm opiera się na podobieństwie problemu do
jego k najbliższych przypadków w zbiorze trenującym oraz wyprowadzeniu rozwiązania z
technik rachunku prawdopodobieństwa.
Klasyfikacja konkretnego problemu (danej będącej wektorem znajdującym się
w wielowymiarowej przestrzeni) polega na wyznaczeniu k przypadków będących najbardziej
podobnych do danych klasyfikowanych pod względem określonej miary podobieństwa.
Przykładowymi miarami(odległościami) stosowanymi w algorytmie k Nearest Neighbours mogą
być[8]:
● Metryka euklidesowa

√







(2.1)
● Metryka Manhattan

∑


|

| (2.2)
● Metryka Czebyszewa



∑


|

|



(2.3)
● Podobieństwo cosinusowe


∑





√∑





√∑





(2.4)
Ostatnim etapem klasyfikacji jest zdefiniowanie do jakiej klasy przynależy problem
wejściowy. W tym celu stosuje się między innymi metody[9]:
● Inverse Distance Voting (Metoda Sheparda) - Obliczana jest suma odwróconych
odległości pomiędzy wybranych k sąsiadów a analizowanym problemem,
● Majority Voting - Klasa problemu jest określana na podstawie największej
przynależności k znalezionych sąsiadów

12. 12
Opis przykładowego algorytmu k Nearest Neighbours[11]:
1. Faza uczenia:
● wykonaj standaryzację/normalizację danych lub pozostaw je nienaruszone,
● zapamiętaj zbiór trenujący w pamięci.
2. Faza testowania:
● wykonaj standaryzację/normalizację danych lub pozostaw je nienaruszone,
● znajdź odległości pomiędzy wektorem testowanym, a wszystkimi elementami
zbioru trenującego,
● sortuj rosnąco odległości między wektorem testowanym, a elementami zbioru
trenującego,
● wybierz k najbliższych wektorów ze zbioru trenującego,
● policz ilość wszystkich występujących klas k najlepszych wektorów ze zbioru
trenującego,
● wybierz najczęściej występującą klasę jako wynik klasyfikacji,
● w przypadku wystąpienia impasu (np. równa ilość głosów na daną klasę)
wybierz klasę losowo.
2.1.2 Podobieństwo cosinusowe
Jedną z najważniejszych decyzji jaką trzeba podjąć podczas projektowania algorytmu
k Nearest Neighbours jest wybór stosowanej miary do sprawdzania odległości pomiędzy
poszczególnymi przypadkami testowymi. W sytuacji, w której tekst reprezentowany jest przez
wektor zawierający informacje o słowach i częstotliwości ich występowania, naturalnym wydaje
się zastosowanie miary cosinusowej. W celu zrozumienia działania procesu szukania odległości
za pomocą cosine similarity należy przedstawić zasadę działania euclidean distance i
zrozumienia jej ograniczeń.
W przypadku liczenia odległości euklidesowej każda miara jest traktowana
równoważnie, co doskonale sprawdza się w przypadku porównywania obiektów opisanych
liczbowo (rozmiary, statystyka). Dla przykładu klasyfikator przyjmujący wymiary pomieszczeń
traktuje równomiernie jego trójwymiarową specyfikę. W tym przypadku pokój długi i wąski nie
jest w niczym podobny do pokoju o równych długościach ścian.
Rozważmy teraz przypadek zastosowania odległości euklidesowej dla tekstu o
tematyce “Uczenie maszynowe”. Pierwszym zestawem trenującym będą artykuły naukowe
traktujące o tematyce “Uczenia maszynowego” bogate w informacje odnośnie szukanej frazy.
Drugim zestawem trenującym będą artykuły o tematyce “ Wpływ edukacji na branżę
maszynową”.

13. 13

2.1 Rozmieszczenie dwóch grup artykułów i artykułu klasyfikowanego na płaszczyźnie euklidesowej
Załóżmy że oś X oznacza częstotliwość występowania słowa “uczenie”, natomiast oś Y
oznacza częstotliwość występowania słowa “maszynowe” wraz z ich wszystkimi odmianami
językowymi. Punkty oznaczone kolorem czerwonym to artykuły pierwszego zestawu
trenującego, natomiast punkty koloru zielonego to artykuły drugiego zestawu trenującego. W
takim przypadku Fraza “uczenie maszynowe” (oznaczona kolorem niebieskim na wykresie
poglądowym) przy pomocy odległości euklidesowej zostanie błędnie sklasyfikowana jako
artykuł o tematyce “Wpływ edukacji na branżę maszynową”. Aby rozwiązać ten problem
znacznie efektywniejsze okazuje się zastosowanie cosine similarity[7].

2.2 Przykład zastosowania cosine similarity
Funkcje odległości cosinusowej określa się następującym wzorem:



|| || || ||

∑





√∑






√∑







(2.5)

14. 14
Gdzie:
A, B - wektory wszystkich słów z artykułu, wraz z ich częstotliwością występowania w danym
artykule,
n - ilość elementów w wektorach.
2.1.3 Ulepszenia i optymalizacje
Powyższa implementacja klasyfikatora kNN, jest podstawową wersją, której jakość
klasyfikacji w wielu przypadkach może odstawać od oczekiwanych wyników. W celu poprawy
jakości klasyfikacji stosuje się różne optymalizacje, lub ulepszenia algorytmu na etapie doboru
najlepszej kategorii z grupy najbliższych sąsiadów.
W niniejszej implementacji klasyfikatora rezygnujemy z implementacji progowania oraz
ulepszeń na etapie liczenia odległości i doboru wielkości k zbioru najbliższych sąsiadów. W
celu polepszenia jakości działania klasyfikatora zostały wprowadzone zmiany na etapie doboru
finalnej kategorii tekstu, który jest implementacją techniki zwanej Majority Voting. Proces został
usprawniony na dwóch płaszczyznach:
● Wprowadzenie progu akceptacji wartościowej kategorii:
Znaczna większość artykułów jest reprezentowana przez grupę kategorii liczącą n
wartości. Rezultatem tego jest twierdzenie, że wynik klasyfikacji może być poprawny tylko
wtedy gdy na wyjściu zostanie podana kolekcja zawierająca kategorie. W tym celu został
wprowadzony próg akceptacji kategorii, określony wartością procentową punktów uzyskanych
przez najwyżej punktowaną kategorię. Wszystkie kategorie wyjściowe mieszczące się w
zakresie progu akceptacji traktowane są jako wartościowe i podawane na wyjściu klasyfikatora
jako element wyniku klasyfikacji.
Proces ten może zostać przedstawiony poniższym algorytmem:
● wyszukaj najwyżej punktowaną kategorię z grupy kategorii wynikowych,
● przyjmij próg akceptacji równy 70% wartości najwyżej punktowanej kategorii,
● znajdź wszystkie kategorie z grupy kategorii wynikowych, których wartości są
wyższe lub równe wartości progu akceptacji kategorii,
● zwróć zbiór kategorii sklasyfikowanych jako wartościowe.
● Ustalenie wartości wag głosowania dla poszczególnych artykułów:
Podczas Majority Voting, głos każdej kategorii jest traktowany z taką samą wagą.
Oznacza to, że w przypadku dużego rozproszenia artykułów ze zbioru trenującego możemy
uzyskać sytuacje, w której dwa artykuły z grupy k najbliższych sąsiadów mogą być w
rzeczywistości odległymi od siebie elementami z diametralnie różną zawartością. Traktowanie
głosów artykułów na równi w takiej sytuacji wprowadza do klasyfikacji przekłamanie, co
bezpośrednio odbija się na jej jakości.
W celu wyeliminowania tego zjawiska wprowadziliśmy wagi dla poszczególnych głosów
kategorii. Wagą danego artykułu jest jego odległość od artykułu klasyfikowanego. Wprowadza
to sytuację, w której najbliższe z k najbliższych artykułów mają największy wpływ na wynik
klasyfikacji.

15. 15
2.1.4 Kroswalidacja
W celu oszacowania jakości działania algorytmu klasyfikacji, w projekcie została
zaimplementowana walidacja krzyżowa. Jest ona zaprojektowana zgodnie z ogólnie przyjętym
modelem k-krotnej walidacji, w której na głównej próbie dokonywany jest folding, czyli podział
na k podzbiorów. Każdy kolejny podzbiór jest definiowany jako zbiór testowy, natomiast
pozostałe jako zbiór uczący. Z tak przygotowanymi danymi przeprowadzamy analizę, która
polega na porównaniu kolejno wszystkich artykułów ze zbioru testowego z artykułami w zbiorze
uczący. Przykładowo (zakładając 10 foldów, liczących po 10 artykułów) artykuły od 1 do 10 ze
zbioru testowego porównywane są z artykułami od 1 do 90 ze zbioru uczącego.
Podstawowym dylematem pojawiającym się przy walidacji działania naszego algorytmu
było określenie kiedy przypadek testowy okazuje się poprawnie sklasyfikowany. W tym celu
skorzystaliśmy ze znanego w statystyce sposobu określania poprawności klasyfikacji na
podstawie precyzji (precision) i czułości (sensitivity). Zaadoptowaliśmy takie pojęcia jak:
● true positive (TP) - liczba artykułów, które zostały wybrane przez algorytm i które były
oczekiwane,
● false positive (FP) - liczba artykułów, które zostały wybrane przez algorytm, ale nie były
oczekiwane,
● false negative (FN) - liczba artykułów, które nie zostały wybrane przez algorytm, ale
były oczekiwane.
● precision - ilość wybranych elementów, które są znaczące
● sensitivity - ilość znaczących elementów, które zostały wybrane
Aby obliczyć precyzję skorzystaliśmy ze wzoru:



(2.6)
Natomiast wzór definiujący czułości to:



(2.7)
Końcowym wynikiem jest średnia harmoniczna wyciągana na podstawie wcześniejszych
wyników nazywana F-measure.



(2.8)
Dopiero wartość f jest podstawą do określenia jakości, dokonanej przez nas, klasyfikacji.
2.2 Rozproszenie obliczeń przy pomocy MapReduce
2.2.1 Struktura klastra
Klaster obliczeniowy składa się z wielu komputerów, zwanych węzłami, tworzących
jedno zintegrowane środowisko. Utworzenie takiego środowiska od podstaw jest trudnym i
czasochłonnym zadaniem, w związku z czym, zdecydowaliśmy się wykorz ystać zestaw
bibliotek i aplikacji o nazwie Apache Hadoop. Struktura klastra w Apache Hadoop jest
określona przez twórców biblioteki, dzięki czemu stworzenie i konfiguracja jest dużo prostsza.

16. 16
Programista nie musi przejmować się równomiernym rozdzielaniem pracy pomiędzy węzły oraz
implementacją mechanizmów zabezpieczających na wypadek awarii węzła.
Komputery w klastrze opartym na Apache Hadoop mają dwie funkcje:
● przechowywanie danych na węzłach klastra. Duże pliki z danymi dzielone są na części
i rozprzestrzeniane między węzłami klastra. Dodatkowo Apache Hadoop oferuje
replikację danych, w przypadku gdyby wystąpiła awaria któregoś z węzłów. Pliki
danych dzielone są na części o określonej w konfiguracji ilości bajtów. W przypadku,
gdy podział pliku nie następuje na końcu linii, następuje automatyczne dopełnienie do
pełnej linii. Jest to bardzo przydatna funkcjonalność, ze względu na to, że w
programach analizujących dane, wczytywane są one zazwyczaj linia po linii,
● wspólne wykonywanie obliczeń. W przypadku awarii węzła klastra, przydzielone mu
dane do obliczenia są rozdysponowywane wśród reszty węzłów.
2.2.2 Podział i przechowywanie plików
[12][13] W Apache Hadoop pliki są przechowywane w rozproszonym systemie plików
HDFS (Hadoop Distributed File System), którego węzły mogą pełnić jedną z dwóch ról:
● NameNode - węzeł zarządzający systemem plików i węzłami podrzędnymi,
● DataNode - węzeł podrzędny, pełniący rolę kontenera danych.
Węzeł, który pełni rolę NameNode do poprawnej pracy musi znać całe drzewo plików
oraz wszystkie węzły podrzędne. Użytkownik manipulujący danymi z HDFS musi komunikować
się z węzłem NameNode, ponieważ to on zarządza plikami, dzieli je między węzłami i łączy.
Dzięki temu, że użytkownik komunikuje się tylko z jednym węzłem, cały rozproszony system
jest dla użytkownika przeźroczysty. W celu eliminacji wąskich gardeł, czyli elementów, które w
przypadku awarii paraliżują cały system, możliwe jest skonfigurowanie tzw. secondary
NameNode, który w wypadku awarii węzła zarządzającego systemem plików przejmuje jego
rolę.
Węzeł, który pełni rolę DataNode jest odpowiedzialny za przechowywanie danych na
swoim dysku oraz za replikację danych znajdujących się na pozostałych węzłach. W domyślnej
konfiguracji dane trzymane są na trzech różnych węzłach w celu z apewnienia stałej
dostępności plików oraz nie dopuszczenia do przerwania pracy w przypadku awarii części
komputerów.
2.2.3 Faza mapowania
[14][15] Sam proces rozproszenia ma swój początek w fazie mapowani a, która
odpowiada za równomierne rozdzielenie pracy pomiędzy węzłami. Mając do dyspozycji
rozproszony system plików HDFS, wczytywany jest, znajdujący się na nim plik z danymi
wejściowymi, które dzielone są na mniejsze części. Wygenerowane rekordy nazywane są
splitami, które następnie przetwarzane są do postaci par klucz-wartość (powszechnym
przykładem jest tekst sczytywany linia po linii). Powstałe w ten sposób grupy par klucz-wartość
rozproszone zostają pomiędzy węzły klastra, gdzie poddawane są funkcji mapowania. Efektem

17. 17
tych operacji jest znaczne zmniejszenie czasu wykonywania tej samej pracy przez jeden węzeł.
Algorytm MapReduce najczęściej używany jest przy czasochłonnych operacjach na dużych
zbiorach danych. Mniejsze znaczeniem ma poziom skomplikowania zadania, w praktyce są to
zazwyczaj łatwe problemy.

2.3 Diagram przedstawiający pierwszy etap fazy mapowania
dane wejściowe - dowolne dane ładowane z pliku
split - pofragmentowane dane wejściowe
KV - zbiory par klucz-wartość dla danego splitu, ulegających mapowaniu w dalszym etapie
Szczegółowy opis kroków przedstawia się następująco:
● InputFormat dzieli dane wejściowe z pliku wejściowego, wynikiem tego działania są
InputSplits, które reprezentują dane do późniejszej analizy,
● RecordReader przygotowuje dane dla następnego kroku w formie grupy par klucz-
wartość,
● Hadoop MapReduce framework dla każdego InputSplit tworzy map task, który
następnie przydzielany jest do węzła,
● każdy map task wykonuje zaimplementowaną i dostarczaną przez aplikację funkcję
map ,
● każdy węzeł może mieć przydzielone więcej niż jeden task, wykonywane one są
równolegle na wszystkich węzłach klastra.
InputSplits - rekordy danych powstałe na etapie dzielenia zbioru danych wejściowych na
mniejsze części,
InputFormat - klasa odpowiedzialna za generowanie InputSplits, dostarcza także
RecordReader oraz opisuje specyfikację wejścia (typy danych dla par klucz-wartość),
RecordReader - generuje zbiór par klucz-wartość z każdego InputSplit, które następnie są
wejściem dla map task,
map task - określenie na zadanie przydzielane węzłom klastra, którego celem jest wykonanie
funkcji mapującej na danych wejściowych.
(2.9)
Powyższy wzór ukazuje bardzo uproszczony schemat tej fazy. Wyjściem jest plik
wynikowy, którego format reprezentowany jest również przez parę klucz-wartość, jednakże typy
danych niekoniecznie muszą pokrywać się z tymi na wejściu.

18. 18
2.2.4 Faza redukcji
[14][15] Faza redukcji rozpoczyna się niezależnie od skończenia fazy mapowania,
oznacza to, że węzłom klastra dla każdego skończonego map task, może zostać przydzielony
reduce task (podobnie jak map task z tą różnicą, że wykonuje funkcję redukującą), nie czekając
aż pozostałe zostaną ukończone. Oczywistą korzyścią z takiego rozwiązania jest wzrost
wydajności. Wejściem dla tego etapu są dane wynikowe fazy mapowania. Wartym
wspomnienia jest również to, że ta faza jest opcjonalna i może zostać pominięta w zależności
od potrzeb aplikacji.
Na proces redukcji składa się::
● wejście, którym jest wynik poprzedniej fazy,
● dla każdego wejścia tworzony jest reduce task i wykonywana jest funkcja redukująca
na dostarczonych danych,
● opcjonalnie, gdy pliki są zbyt rozprzestrzenione w skład procesu może wchodzić proces
kopiowania plików, aby dostępne były lokalnie i późniejsze sortowanie danych,
● interfejs OutputFormat, który (podobnie jak jego odpowiednik w fazie mapowania,
InputFormat) opisuje specyfikację wyjścia - typy danych dla pary klucza-wartość,
● wynikiem każdego reduce task jest plik wynikowy zapisywany w systemie plików HDFS,
pliki te zostają następnie scalone ze sobą, a dane redukowane po raz ostatni.
Uproszczony schemat fazy redukcji można przedstawić w następujący sposób:
(2.10)
Fazę redukcji można dodatkowo przyspieszyć oraz zminimalizować obciążenie sieci,
poprzez zmniejszenie ilości danych przesyłanych między węzłami dzięki zastosowaniu funkcji
łączącej zwanej Combiner function. Funkcja łącząca działa w ten sam sposób co funkcja
redukująca, jednak działa ona tuż po wykonaniu fazy mapowania, przed wysłaniem utworzonej
struktury do węzłów wykonujących fazę redukcji.
Podsumowując, algorytm MapReduce jest powszechnie stosowany na dużych zbiorach
danych, które w tradycyjny oraz sekwencjonalny sposób przetwarzane byłyby zdecydowanie
dłużej. Rozbicie danych na mniejsze fragmenty i dystrybucja na węzły klastra pozwala na
równoległe ich przetwarzanie co wiąże się ze znacznym wzrostem wydajności aplikacji
opierającej się na tym algorytmie. Przykładem wykorzystania może być analiza dużych ilości
tekstu pod kątem zliczania występujących w nim słów. To rozwiązanie najlepiej się sprawdza w
takich przypadkach.

19. 19
3. IMPLEMENTACJA
3.1 Wykorzystane technologie
3.1.1 Hadoop
Przy założeniu, że sieć jest poprawnie skonfigurowana, konfiguracja Apache Hadoop
jest niezwykle prosta. Sprowadza się ona do uzupełnienia kilku plików xml, oraz podania roli
poszczególnych węzłów. Problemami takimi jak zabezpieczenie klastra przed awarią
pojedynczego węzła, czy poprawnym podziałem plików między węzły zajmuje się sam Hadoop.
Apache Hadoop nie jest jedynym w swoim rodzaju rozwiązaniem dostępnym na rynku.
Istnieje kilka alternatyw dla jego zastosowania. Z poważniejszych konkurentów możemy
wymienić Apache Spark, który niejako wywodzi się z Hadoopa i często używany jest w
połączeniu z nim, jednak może również działać samodzielnie. Zaletami Apache Spark, które
odróżniają go od Hadoopa są niezależność od sposobu magazynowania danych (Hadoop -
HDFS) oraz przystosowanie do przetwarzania i analizy danych w czasie rzeczywistym.
Kolejną alternatywą jest Cluster Map Reduce, stworzony przez firmę Chitika na
wewnętrzne potrzeby. Framework ten bazuje na systemie plików Gluster, a kod źródłowy został
udostępniony publicznie na platformie Github wraz z krótkim opisem konfiguracji. Na ten
moment w Internecie dostępnych jest względnie mało informacji na temat tego frameworku, a
szczególnie doskwiera brak szczegółowej dokumentacji. Twórcy reklamują swój produkt jako
szybszy i efektywniejszy w aspekcie manipulacji i przetwarzania plików wewnątrz frameworku
niż rozwiązania proponowane przez Apache.
Do postawienia na Apache Hadoop przekonała nas ogromna popularność i stabilność
tego rozwiązania, prostota w konfiguracji, porządne zabezpieczenia i spory zasób informacji
dostępny w Internecie. Każde z rozwiązań ma swoje wady i zalety, chociaż Hadoop na dzień
dzisiejszy jest rozwiązaniem, po które sięga się statystycznie najczęściej. Nie jest natomiast
pewne, że implementacja algorytmu przy użyciu tego frameworku będzie najbardziej
optymalnym rozwiązaniem z grupy dostępnych opcji.
3.1.2 Scala
Przy rozwoju projektu wykorzystany został język programowania Scala. [16] Jest to
relatywnie młody język, jego pierwsza wersja miała premierę w 2004 roku. Jego składnia jest
zbliżona do składni Javy, jednak pozwala ona na rozszerzanie bibliotek Javy oraz oferuje
dodatkowe mechanizmy składniowe, takie jak na przykład funkcje anonimowe w postaci
wyrażeń lambda. Oferuje on płynną integrację z językami programowania Java i C# poprzez
kompilację na środowiska uruchomieniowe tych dwóch języków. Scalę cechuje połączenie
właściwości języka obiektowego z cechami języka funkcyjnego. Dzięki właściwościom języka
funkcyjnego Scala pozwala na wygodną implementację algorytmów matematycznych oraz na
używanie funkcji anonimowych w postaci wyrażeń lambda przy np. iterowaniu przez kolekcje.

20. 20
3.2 Opis działania projektu
3.2.1 Wstęp
Wczytanie artykułu:
Artykuł do którego przypasowane mają być kategorie zostaje wczytany do pamięci, po
czym za pomocą wyrażeń regularnych wyodrębnione zostają poszczególne słowa, których
wszystkie wielkie litery zostają zamienione na małe.
Zliczenie i sprowadzenie słów do lemm:
Na bazie pliku tekstowego zawierającego w kolejnych liniach słowa występujące w
języku Polskim i ich bazowe formy, utworzona została struktura, będąca wariantem Drzewa
Trie. Jest to drzewo, które jako klucze przechowuje kolejne litery umieszczonego słowa. A jako
wartości formy bazowe, szukanego słowa. Struktura ta po otrzymaniu słowa zwraca jego formę
podstawową.

3.1 Diagram przedstawiający strukturę Trie dla słów wraz z ich formami bazowymi: dwa → dwa, dwu →
dwa, to → to, oczy → oko, oka → oko, oko → oko
Klasyfikacja słów artykułu:
Wyliczenie podobieństwa pomiędzy artykułami, klasyfikowanym i ze zbioru uczącego,
na podstawie zawierania tych samych słów w obu artykułach. Jako zbiór uczący dla programu
użyte zostało repozytorium artykułów polskiej gałęzi Wikipedii z 2015 roku.
Wybranie kategorii:

21. 21
Wybranie n najlepiej pasujących kategorii dla danego artykułu pośród kategorii najlepiej
dopasowanych artykułów ze zbioru uczącego.
3.2.2 Schemat działania projektu

3.2 Schemat działania projektu
Legenda:

- Czynność wykonywana przez program.

- Dane którymi operuje program.

22. 22
Klasyfikowany artykuł - artykuł który wymaga przyporządkowania kategorii, składa się z nazwy
i tekstu.
Słownik słów i odmian - struktura stworzona na bazie pliku tekstowego zawierającego słowa
występujące w języku polskim i ich lemmy.
Zbiór uczący - repozytorium artykułów polskiej gałęzi Wikipedii z 2015 roku
KNN - Algorytm k-Najbliższych Sąsiadów
3.3 Klasyfikacja artykułów do kategorii
3.3.1 Wstęp
Na podstawie wyliczonego podobieństwa cosinusowego, klasyfikator dobiera
najbardziej podobne do siebie artykuły względem analizowanego. Dobór kategorii odbywa się w
końcowym etapie pracy programu, po zebraniu wyników klasyfikacji do jednego pliku.
W celu przypasowania kategorii do artykułu, w pierwszej kolejności tworzony jest
słownik wszystkich kategorii z dopasowanych artykułów. Każda kategoria oznaczona jest
wartością liczbową, która jest sumą wcześniej wyliczonych wartości podobieństwa
cosinusowego (jeśli kategoria X znajduje się w spisie kategorii artykułu A i artykułu B, to jej
wartością jest suma podobieństwa artykułu A i artykułu B do analizowanego). Z powstałego w
ten sposób słownika, wybierana jest najwyższa wartość, której 90% stanowi próg doboru
najlepszych kategorii. Jeśli zależność (2.1) jest spełniona to kategoria zostaje dopisana na listę
najlepiej dopasowanych.
(3.1)
3.3.2 Zbiór danych
Zbiór trenujący to zbiór artykułów w notacji Wikikodu pobranych z Wikipedii, przy
pomocy Wikidumps. Pobrane dane są aktualne, pobrane na dzień 02.10.2015r. Aplikacja
przetwarza dane zebrane w plikach *pages-articles*.xml i na ich podstawie zapisuje do pliku
nazwę artykułu i jego treść w Wikikodzie.
W celu poprawnego wykonania kroswalidacji, zbiór trenujący należy podzielić na n
części. Jedną z tych części algorytm przyjmuje jako zbiór testujący, pozostałe części są
traktowane jako zbiór trenujący. Najlepiej jest zastosować podział niezależny od treści artykułu
czy kategorii, ponieważ zbiory te powinny zawierać artykuły z różnych klas.
Ilość zbiorów oraz parametr częstotliwości przyporządkowania artykułów do danego foldu, są
ustawialne w parametrach programu. Zmiana tych parametrów może znacząco zmienić dane
wyjściowe algorytmu.
3.4 Rozproszenie na klastrze
W celu uzyskania zysku czasowego w wykonaniu programu poprzez wykorzystanie
klastra, istotne jest rozłożenie jak największej ilości operacji na wiele węzłów. Dla dużych
zbiorów danych, wielokrotnie powtarzane operacje okazują się najbardziej kosztowne czasowo,
z tego powodu to właśnie one zostały rozproszone.

23. 23
3.4.1 Podział zbioru na węzły
Dostęp do danych potrzebnych przez każdy z węzłów realizowany jest za pomocą
HDFS, każdy węzeł pobiera dane, które znajdują się na jego dysku. Ponieważ pliki wczytywane
są linia po linii, a między węzłami pliki są rozdystrybuowane w częściach po 128 MB, może
wystąpić konieczność przesyłu końca linijki między węzłami.
3.4.2 Operacje, które zostały rozproszone
Rozkład operacji na węzłach klastra dla klasyfikacji kształtuje się następująco:
Operacje wykonane przed uruchomieniem programu:
● utworzenie struktury danych słownika form podstawowych oraz zserializowanie jej do
pliku.
Operacje przygotowujące, wykonywane na jednym węźle:
● wczytanie zserializowanego słownika bazowych wersji słów,
● wczytanie artykułów z wikidumps i zapisanie ich do pojedynczych plików.
Operacje rozproszone:
● sprowadzenie wszystkich rozpoznanych słów do lemm i ich zliczenie dla artykułów ze
zbioru danych,
● sprowadzenie wszystkich rozpoznanych słów do lemm i ich zliczenie dla artykułu
klasyfikowanego,
● obliczenie podobieństwa artykułu ze zbioru danych do artykułu klasyfikowanego.
Operacje końcowe wykonywane na jednym węźle:
● wybór najbardziej podobnych artykułów pośród danych zwróconych przez klasyfikator,
a następnie na podstawie kategorii tych artykułów przypasowanie kategorii artykułowi
klasyfikowanemu.

Rozkład operacji na węzłach klastra dla kroswalidacji kształtuje się następująco:
Operacje rozproszone:
● sprowadzenie wszystkich rozpoznanych słów do lemm i ich zliczenie dla artykułów ze
zbioru danych,
● folding, czyli podział zbioru danych na n grup,
● wyliczanie odległości cosinusowej między artykułem z danego foldu, a artykułem spoza
tego foldu.
Operacje końcowe wykonywane na jednym węźle:
● zebranie i podsumowanie wyniku, porównanie z oczekiwanymi wynikami.
3.4.2.1 Rozproszenie zliczania słów
Przed przystąpieniem do zliczania słów, należało odpowiednio przygotować klaster do
pracy. Każdy węzeł klastra został skonfigurowany w taki sposób, że posiada lokalną kopię
struktury słownika, który przyjmując na wejście słowo zwraca jego formę bazową. Na początku

24. 24
kroku mapowania wczytanie artykułu, które odbywa się linia po linii. W ten sposób system
buduje w pamięci strukturę potrzebną do sprowadzenia słów do ich podstawowej formy.
Przy pomocy wyrażeń regularnych, z artykułu zostaje usunięty Wikikod, a następnie
wydobywane są wszystkie słowa, które przy pomocy słownika zostają sprowadzone do
podstawowej formy. Dodatkowo, ponieważ każdy artykuł zawiera informację o
przyporządkowanych kategoriach, kategorie te są wydobywane z pliku przy pomocy wyrażeń
regularnych i są dodawane do pliku wyjściowego. Kluczem w kroku mapowania jest słowo, a
przy każdym jego wystąpieniu do zbioru wartości dodajemy liczbę 1. Dla zbioru kategorii
tworzymy osobny klucz, a do jego zbioru wartości dodajemy każdą wyznaczoną kategorię.
Podczas kroku redukcji słowa są zliczane na podstawie otrzymanych rekordów. Jeżeli
klucz zawiera nazwę słowa, jego wartości są sumowane, w ten sposób otrzymujemy liczebność
danego słowa w artykule. Jeżeli klucz rekordu jest specjalnie stworzonym dla kategorii kluczem,
kategorie są wyznaczane ze zbioru wartości. W ten sposób przeanalizowane dane są zapisane
do plików wyjściowych.
Operacja ta jest wykonywana przy klasyfikacji oraz przy kroswalidacji. Operacja ta
może być wykonana tylko raz, natomiast powinna być wykonana ponownie przy każdej zmianie
zbioru wejściowego. Operacja jest złożona czasowo, ze względu na tworzenie struktury i
wybieranie słów przy pomocy wyrażeń regularnych z dużych artykułów, jednak potrzeba jej
wykonania jest jednorazowa, nie powinno to mocno obciążyć klastra użytkownika.

Przebieg podsumowujący rozproszenie algorytmu zliczania słów:
1. dane wejściowe - danymi wejściowymi algorytmu są artykuły w formie tekstu z
Wikikodem,
2. krok mapowania - dane wejściowe są wczytywane linia po linii. Do mapy zapisywane
są wszystkie znalezione słowa, sprowadzone do podstawowej formy dla danego
artykułu jako klucz i liczba jeden przy każdym wystąpieniu słowa. Dodatkowo do mapy
wpisywane są kategorie, jeśli wystąpią,
3. krok redukcji - mapa uzyskana w poprzednim kroku zostaje wczytana i wszystkie
wystąpienia liczby jeden dla danego słowa zostają sumowane. Sumy wraz z
kategoriami uzyskanymi w poprzednim punkcie są zapisywane na wyjście.
3.4.2.2 Rozproszenie kNN
Operacje tworzenia wektorów słów oraz obliczania odległości cosinusowej dla dwóch
wektorów są operacjami bardzo czasochłonnymi, dlatego aby zwiększyć wydajność niezbędne
jest ich rozproszenie.
Rozproszenie tego kroku polega na wczytaniu z wejścia jednego artykułu z policzonymi
słowami i wydzielonymi kategoriami, wyznaczeniu dla niego wektora słów i porównaniu go
z wektorem innego artykułu. Podczas kroku mapowania, wczytywane są wyniki uzyskane przy
zliczaniu słów. Liczebności każdego słowa oraz wszystkie kategorie są zbierane do jednego

25. 25
rekordu, którego kluczem jest nazwa artykułu. Zbiór lub w przypadku kroswalidacji podzbiór
tych rekordów to zbiór trenujący.
W przypadku klasyfikacji, algorytm porównuje klasyfikowany artykuł ze zbiorem
uczącym, natomiast w przypadku kroswalidacji porównywane są artykuły z danego foldu z
artykułami z pozostałych foldów.
Podczas wykonywania kroku redukcji, do pamięci wczytywany jest zbiór testujący,
którym może być klasyfikowany artykuł lub zbiór artykułów po zliczeniu słów. Wczytany artykuł
lub zbiór artykułów, zostaje następnie porównany z rekordem otrzymanym z kroku mapowania.
Do porównania potrzebne jest uprzednie utworzenie dwóch wektorów słów, zawierających
liczebność danego słowa w dwóch wybranych artykułach. Po utworzeniu wektorów zliczane jest
podobieństwo cosinusowe między dwoma wybranymi artykułami a następnie wyniki
zapisywane są do pliku. Jeżeli na początku kroku redukcji zostaje wybranych więcej niż jeden
artykuł, tworzenie wektorów i zliczanie podobieństwa są wykonywane wielokrotnie.
Przebieg podsumowujący rozproszenie algorytmu kNN:
1. dane wejściowe - zbiór artykułów z policzonymi słowami oraz wydzielonymi
kategoriami,
2. krok mapowania - krok mapowania polega na wczytaniu wyjścia z kroku zliczania słów
do mapy,
3. krok redukcji - z wczytanych danych oraz danych znanych z klasyfikowanego artykułu
utworzone zostają dwa wektory reprezentujące liczebność danych słów w obu
artykułach. Po utworzeniu wektorów liczona jest odległość cosinusowa miedzy nimi i
wypisywana jest na wyjscie razem z kategoriami danego artykułu.
3.4.2.3 Rozproszenie foldingu
Operacja foldingu, ze względu na dużą ilość danych do przetworzenia przy tworzeniu
podzbiorów, została rozproszona i będzie wykonywana przed wykonaniem walidacji skrośnej.
Podział zbiorów jest dokonywany na podstawie nazwy artykułu. Ilość zbiorów można ustawić w
parametrach programu. Krok mapowania jest zaimplementowany w podobny sposób jak przy
algorytmie kNN, natomiast podczas kroku redukcji artykuły są dzielone na n zbiorów na
podstawie nazwy artykułu i zapisywane do n plików. Wszelkie informacje uzyskane przy
zliczaniu słów są przepisywane do odrębnych plików.
Przebieg foldingu:
1. dane wejściowe - artykuł z policzonymi słowami oraz wydzielonymi kategoriami,
2. krok mapowania - krok mapowania polega na wczytaniu wyjścia z kroku zliczania słów
do mapy,
3. krok redukcji - krok redukcji polega na wybraniu odpowiedniego foldu dla artykułu
w zależności od nazwy artykułu. Wszystkie informacje uzyskane w przy zliczaniu słów
są przepisywane do pliku o odpowiedniej nazwie, będącego zbiorem artykułów dla
danego foldu.

26. 26
3.4.2.4 Rozproszenie kroswalidacji
Kroswalidacja składa się z trzech operacji, gdzie każda jest rozpraszana między
węzłami klastra, w celu zwiększenia wydajności. Operacje składające się na kroswalidację to:
● liczenie odległości cosinusowej między artykułami z danego foldu, a artykułami z
pozostałych foldów,
● na podstawie odległości wyznaczanie k-Najbliższych Sąsiadów danego artykułu,
wyszukiwanie najlepszych kategorii przy użyciu kryterium progowania SS-cut oraz
wyznaczenie metryki trafności predykcji F-Measure na podstawie otrzymanych
i oczekiwanych kategorii,
● sumowanie i uśrednianie wyników i obliczanie średniej w celu oceny klasyfikatora.
Liczenie odległości cosinusowej jest realizowane tak jak opisano to w rozdziale 3.4.2.2,
z tą różnicą, że zamiast wczytywania jednego artykułu na początku kroku redukcji, wczytywane
są wszystkie artykuły z danego foldu. W procesie analizy danych zapamiętujemy także
kategorie dla artykułów z badanego foldu, w celu ich późniejszego porównania z kategoriami
uzyskanymi przez proces klasyfikacji.
Na podstawie danych uzyskanych w poprzednim kroku, system wyznacza k
najbliższych sąsiadów oraz najlepsze kategorie dla danego artykułu. Na podstawie uzyskanych
kategorii jesteśmy w stanie wyznaczyć proporcje między dobrze, a źle wybranymi kategoriami
przy pomocy true positive, false positive i false negative dla wybranych kategorii, a na ich
podstawie jesteśmy w stanie wyznaczyć miary Precision i Recall potrzebne do wyznaczenia F-
Measure, a także samo F-Measure.
Krok mapowania polega na wczytaniu wyników uzyskanych w poprzednim kroku i
utworzeniu mapy, której klucze są nazwą artykułu, a wartości to wszystkie kategorie dla obu
artykułów oraz podobieństwo cosinusowe.
Krok redukcji polega na wyznaczeniu k najbliższych sąsiadów oraz najlepszych
kategorii dla danego artykułu i porównaniu ich z kategoriami oczekiwanymi, czyli tymi, które
zawierały na wejściu artykuły ze zbioru testującego. Na podstawie tego porównania możemy
wyznaczyć szukane proporcje i miary.
Ostatnią rozproszoną operacją podczas wykonywania kroswalidacji jest operacja
zliczania wyników zbiorczych dla wszystkich foldów. Wskaźniki true postive, false positive oraz
false negative są sumowane, natomiast szukane miary są w tym kroku uśredniane.
Krok mapowania polega na wczytaniu wszystkich wyników uzyskanych w poprzednim
kroku i zapisaniu ich do jednego wspólnego klucza, natomiast krok redukcji polega na
zsumowaniu i uśrednieniu wszystkich wartości.
3.5 Instrukcja instalacji
W tym rozdziale znajdują się informacje odnośnie instalacji i uruchomienia projektu.
Kod źródłowy można skompilować przy pomocy narzędzia o nazwie Apache Maven. Maven
automatycznie pobierze wszystkie wymagane do działania projektu biblioteki oraz skompiluje

27. 27
kod źródłowy to formatu Java Archive (jar). Aby skompilować kod źródłowy należy pobrać
Apache Maven ze strony programu, a następnie będąc w folderze src/ wywołać polecenia
mvn clean install
mvn package
W folderze src/target powinien pojawić się skompilowany program o nazwie kaw-
0.0.1-SNAPSHOT-jar-with-dependencies.jar. Program ten należy skopiować do katalogu
bin/. Program powinniśmy uruchamiać bezpośrednio z katalogu bin/.
3.5.1. Przygotowanie klastra Apache Hadoop
Program podczas działania wykorzystuje pliki, które muszą być umieszczone w
systemie plików klastra Apache Hadoop lub jeżeli klaster jest uruchomiony lokalnie w trybie
symulacji na dysku komputera. Pliki wymagane przez klasyfikator to:
● artykuł klasyfikowany w notacji Wikikod lub jako zwykły tekst,
● zbiór trenujący artykułów w notacji Wikikod, zawierających informacje o kategoriach,
artykuły te można przy pomocy aplikacji wydobyć z pliku pages-articles z Wikidumps,
● słownik w postaci pliku zawierającego słowa oraz ich formy podstawowe. Plik powinien
przyjmować następującą formę:
○ n w każdej linii pliku powinno znajdować się słowo z odmianą oraz jego wersja
bazowa,
○ n słowo oraz jego wersja bazowa powinny być rozdzielone tabulatorem.
3.5.2. Konfiguracja parametrów programu
Przed uruchomieniem programu należy skonfigurować plik znajdujący się w folderze
conf/ o nazwie kaw.properties. Wartości parametrów powinny być ustawione zgodnie z
tabelą 3.1. Parametry biblioteki Apache Hadoop, w których skład wchodzą m.in. ustawienia
dostępu do klastra, należy ustawiać poprzez rozpoczęcie nazwy parametru od przedrostka
hadoop. a następnie dopisaniu nazwy danego parametru zgodnie z dokumentacją Apache
Hadoop.
Tabela 3.1 Wykaz parametrów uruchomienia aplikacji
Nazwa parametru Typ wartosci Opis
pl.gda.pg.eti.kask.kaw.
userName
String Nazwa użytkownika UNIX na serwerze zdalnym. Tej
nazwy będzie używał Apache Hadoop podczas
łączenia się do zdalnego klastra.
pl.gda.pg.eti.kask.kaw.j
arLocation
String Położenie skompilowanej aplikacji w formacie .jar.
pl.gda.pg.eti.kask.kaw.c
lassifyRepetitions
Integer,
Liczba dodatnia
Ilość powtórzeń klasyfikacji, może być używana do
mierzenia wydajności klasyfikatora.
pl.gda.pg.eti.kask.kaw.k Integer Wartość parametru k dla klasyfikatora k-
Najbliższych Sąsiadów.

28. 28
Tabela 3.1 Wykaz parametrów uruchomienia aplikacji
pl.gda.pg.eti.kask.kaw.c
lassifierPrecision
Double,
0 ≤ x ≤ 1
Procentowa wartość progowania SS-cut klasyfikatora
k-Najbliższych Sąsiadów.
pl.gda.pg.eti.kask.kaw.
dictionaryLocation
String Położenie w systemie plików klastra pliku
zawierającego odmiany słów.
pl.gda.pg.eti.kask.kaw.f
olds
Integer Liczba foldów walidacji skrośnej.
pl.gda.pg.eti.kask.kaw.r
andomPerFold
Integer Rozrzut artykułów między foldy.
pl.gda.pg.eti.kask.kaw.l
ocalDumpsInput
String Położenie pliku pages-articles z Wikidumps na dysku
klastra.
pl.gda.pg.eti.kask.kaw.l
ocalDumpsOutput
String Folder wyjściowy, do którego program ma wypisać
zbiór artykułów przy lokalnym trybie symulacji.
pl.gda.pg.eti.kask.kaw.
dumpsOutput
String Folder wyjściowy, do którego program ma wypisać
zbiór artykułów na klastrze.
pl.gda.pg.eti.kask.kaw.
newArticleInput
String Folder wejściowy do algorytmu klasyfikatora,
powinien zawierać artykuł, który chcemy
sklasyfikować.
pl.gda.pg.eti.kask.kaw.
newArticleOutput
String Folder wyjściowy na klastrze, do którego zapisane
zostaną wyniki zliczania słów klasyfikowanego
artykułu.
pl.gda.pg.eti.kask.kaw.
wordCountInput
String Folder wejściowy do algorytmu zliczania słów,
powinien zawierać zbiór trenujący artykułów.
pl.gda.pg.eti.kask.kaw.
wordCountOutput
String Folder wyjściowy algorytmu zliczania słów na
klastrze.
pl.gda.pg.eti.kask.kaw.c
lassifierInput
String Folder wejściowy do klasyfikatora, parametr powinien
wskazywać na folder wyjściowy algorytmu zliczania
słów.
pl.gda.pg.eti.kask.kaw.c
lassifierOutput
String Folder wyjściowy klasyfikatora.
pl.gda.pg.eti.kask.kaw.f
oldingInput
String Folder wejściowy do algorytmu foldingu, parametr
powinien wskazywać na folder wyjściowy algorytmu
zliczania słów.
pl.gda.pg.eti.kask.kaw.f
oldingOutput
String Folder wyjściowy algorytmu foldingu.
pl.gda.pg.eti.kask.kaw.c
rossvalidationInput
String Folder wejściowy algorytmu kroswalidacji, parametr
powinien wskazywać na folder wyjściowy algorytmu
foldingu.

29. 29
Tabela 3.1 Wykaz parametrów uruchomienia aplikacji
3.5.3 Analiza pliku Wikidumps
Program umożliwia przeanalizowanie pliku pages-articles i skopiowaniu do podanego
folderu artykułów w notacji Wikikodu wraz z kategoriami. Artykuły można przeczytać na lokalny
dysk, co może być przydatne w przypadku symulacji klastra, umożliwia to też ręczne wgranie
plików na klaster. Program umożliwia też wczytywanie artykułów bezpośrednio na rozproszony
dysk Apache Hadoop.
Aby wczytać plik Wikidumps w trybie lokalnym należy uruchomić program wraz z parametrami
java -jar kaw.jar dump --local
natomiast, wczytywanie na klaster odbywa się przy wywyłaniu programu z następującym
parametrem:
java -jar kaw.jar dump
Można uruchomić także wczytywanie pliku razem z dodatkowymi parametrami:
DUMP_IN OUT_DIR [--start N [--skip X]] [--max M]
DUMP_IN, OUT_DIR - odpowiedniki parametrów pl.gda.pg.eti.kask.kaw.localDumpsInput,
pl.gda.pg.eti.kask.kaw.localDumpsOutput, jeżeli nie podane to następuje ich wczytanie z
folderu conf/kaw.properties.
Poniższe nieobowiązkowe parametry umożliwiają wczytywanie pliku wikidumps przez
wiele węzłów klastra jednocześnie:
● --start N - dzięki temu parametrowi można kazać programowi pominąć pierwsze
START artykułów,
● --skip X - dzięki temu parametrowi można kazać programowi kopiować co X artykuł,
● --max M - dzięki temu parametrowi można kazać programowi wczytywać artykuły do
M-tego artykułu.
Przykład wczytywania artykułu na trzech węzłach jednocześnie znajduje się w plikach
bin/read_dump.sh oraz bin/read_dump_to_local_folder.sh.
pl.gda.pg.eti.kask.kaw
.crossvalidationOutput
String Folder wyjściowy algorytmu kroswalidacji.
pl.gda.pg.eti.kask.kaw
.crossvalidationScore
sInput
String Folder wejściowy algorytmu zliczania punktów
kroswalidacji, powinien wskazywać na folder
wyjściowy algorytmu kroswalidacji.
pl.gda.pg.eti.kask.kaw
.crossvalidationScore
sOutput
String Folder wyjściowy algorytmu zliczania punktów
kroswalidacji.
pl.gda.pg.eti.kask.kaw
.crossvalidationAvera
geScoreInput
String Folder wejściowy algorytmu zliczania średniej
punktów kroswalidacji, powinien wskazywać na
folder wyjściowy algorytmu zliczania punktów
kroswalidacji.
pl.gda.pg.eti.kask.kaw
.crossvalidationAvera
geScoreOutput
String Folder wyjściowy algorytmu zliczania średniej
punktów kroswalidacji.

30. 30
3.5.4 Tryby działania klasyfikatora
Aplikacja jest uruchamiana z wiersza poleceń, może zostać uruchomiona w wielu
trybach. Korzystając z aplikacji można dokonać klasyfikacji automatycznej lub uruchomić każdą
z operacji ręcznie. Tryb automatyczny jest najłatwiejszy w obsłudze, nie wymaga ręcznego
zarządzania katalogami.
Tryb ręczny umożliwia wykonywanie każdej operacji na klastrze osobno, jednak wymaga
usuwania katalogów wyjściowych algorytmu przed wykonaniem danej operacji. Uruchamiając
poniżej wylistowane polecenia należy pamiętać, że zamiast kaw.jar, należy podać nazwę
archiwum skompilowanego przez Apache Maven, skopiowanego do katalogu bin/.
W trybie automatycznym można wykonać trzy główne operacje:
1. automatycznej klasyfikacji, operacja automatycznie zlicza słowa klasyfikowanego
artykułu oraz artykułów zbioru trenującego, jeśli nie zostały wcześniej zliczone oraz
wykonuje klasyfikację i wypisuje wyniki na ekran. Operacja ta wymaga uzupełnienia
parametrów w pliku parametrów. Tę operacje można wywołać uruchamiając polecenie
java -jar kaw.jar classify --auto
2. automatycznej kroswalidacji. Program automatycznie zlicza słowa, jeśli to konieczne.
Dzieli zbiór na podzbiory i wykonuje klasyfikację dla wszystkich artykułów. Następnie
program zlicza wyniki i je sumuje i uśrednia, a wynik wypisuje na ekran. Operacja ta
wymaga uzupełnienia parametrów w pliku parametrów. Tę operację można wywołać
uruchamiając polecenie
java -jar kaw.jar crossvalidate --auto
3. automatycznego sumowania wyników. Program ponownie wylicza wyniki, sumuje oraz
uśrednia je i wypisuje na ekran. Operacja jest ta przydatna w przypadku badań jakości
klasyfikacji po modyfikacji parametrów k i progowania. Operacja ta wymaga
uzupełnienia parametrów w pliku parametrów. Operację tę można wywołać
uruchamiając polecenie
java -jar kaw.jar cvscores --auto
W trybie ręcznym można wykonać siedem operacji. Operacje nie wymagają podawania
parametrów w pliku parametrów, ale wtedy należy je podać w wierszu poleceń jako kolejne
parametry programu.
Do operacji wykonywanych ręcznie należą:
1. operacja zliczania słów. Operacja może przyjąć parametry:
● IN_DIR - określa katalog wejściowy dla operacji, analogicznie jak w
pl.gda.pg.eti.kask.kaw.wordCountInput
● OUT_DIR - określa katalog wyjściowy operacji, a nalogicznie jak w
pl.gda.pg.eti.kask.kaw.wordCountOutput
Parametry te są nieobowiązkowe. Operację można wywołać uruchamiając polecenie:
java -jar kaw.jar wordcount [IN_DIR OUT_DIR]
2. operacja klasyfikacji pojedynczego artykułu. Operacja może przyjąć parametry:

31. 31
● IN_DIR - określa katalog wejściowy dla operacji, analogicznie jak w
pl.gda.pg.eti.kask.kaw.classifierInput
● OUT_DIR - określa katalog wyjściowy dla operacji, analogicznie jak w
pl.gda.pg.eti.kask.kaw.classifierOutput
Parametry te są nieobowiązkowe. Operację można wywołać uruchamiając polecenie:
java -jar kaw.jar classify [IN_DIR OUT_DIR]
3. operacja znalezienia najlepszych kategorii. Operacja może przyjąć parametry:
● IN_DIR - określa katalog wejściowy dla operacji, który jest katalogiem wyjściowym
klasyfikacji, analogicznie jak w pl.gda.pg.eti.kask.kaw.classifierOutput
● K - określa parametr k dla algorytmu kNN, analogicznie jak w pl.gda.pg.eti.kask.kaw.k
Parametry te są nieobowiązkowe. Operację można wywołać uruchamiając polecenie:
java -jar kaw.jar bestCategories [IN_DIR K]
4. operacja foldingu. Operacja może przyjąć parametry:
● IN_DIR - określa katalog wejściowy dla operacji, analogicznie jak w
pl.gda.pg.eti.kask.kaw.foldingInput
● OUT_DIR - określa katalog wyjściowy dla operacji, analogicznie jak w
pl.gda.pg.eti.kask.kaw.foldingOutput
Parametry te są nieobowiązkowe. Operację można wywołać uruchamiając polecenie:
java -jar kaw.jar fold [IN_DIR OUT_DIR]
5. operacja kroswalidacji. Operacja może przyjąć parametry:
● IN_DIR - określa katalog wejściowy dla operacji, analogiczn ie jak w
pl.gda.pg.eti.kask.kaw.crossvalidationInput
● OUT_DIR - określa katalog wyjściowy dla operacji, analogicznie jak w
pl.gda.pg.eti.kask.kaw.crossvalidationOutput
Parametry te są nieobowiązkowe. Operację można wywołać uruchamiając polecenie:
java -jar kaw.jar crossvalidate [IN_DIR OUT_DIR]
6. operacja zliczania wyników kroswalidacji. Operacja może przyjąć parametry:
● IN_DIR - określa katalog wejściowy dla operacji, analogicznie jak w
pl.gda.pg.eti.kask.kaw.crossvalidationScoresInput
● OUT_DIR - określa katalog wyjściowy dla operacji, analogicznie jak w
pl.gda.pg.eti.kask.kaw.crossvalidationScoresOutput
Parametry te są nieobowiązkowe. Operację można wywołać uruchamiając polecenie:
java -jar kaw.jar cvscores [IN_DIR OUT_DIR]
7. operacja uśredniania wyników kroswalidacji. Operacja może przyjąć parametry:
● IN_DIR - określa katalog wejściowy dla operacji, analogicznie jak w
pl.gda.pg.eti.kask.kaw.crossvalidationAverageScoreInput
● OUT_DIR - określa katalog wyjściowy dla operacji, analogicznie jak w
pl.gda.pg.eti.kask.kaw.crossvalidationAverageScoreOutput
Parametry te są nieobowiązkowe. Operację można wywołać uruchamiając polecenie:
java -jar kaw.jar cvaverage [IN_DIR OUT_DIR]

32. 32
Program zawiera wbudowany manual, który można wyświetlić uruchamiając aplikację bez
żadnych parametrów. W celu wyświetlenia manuala należy uruchomić polecenie:
java -jar kaw.jar

33. 33
4. OCENA
4.1 Wydajność
W rozdziale tym, opiszemy przeprowadzone przez nas testy oraz skomentujemy ich
wyniki. Projekt naszego autorstwa pozwolił nam na zgromadzenie statystyk wydajnościowych
oraz przeanalizowanie poprawności przypisania do kategorii przez klasyfikator kNN oparty na
podobieństwie cosinusowym.
4.1.2 Ocena wydajności algorytmów
Tabela 4.1 Zależność czasu wykonania poszczególnych operacji od ilości artykułów
100 artykułów 250 artykułów 500 artykułów 750 artykułów
Liczenie słów 00:02:44 00:05:21 00:09:35 00:15:22
Kategoryzacja 1
artykułu
00:00:42 00:00:43 00:00:42 00:00:41
Folding,
kroswalidacja
00:08:03 00:17:59 00:57:03 02:50:13
Zbieranie wyników
kroswalidacji
00:00:37 00:00:38 00:00:41 00:00:42
Uśrednianie
wyników
kroswalidacji
00:00:37 00:00:38 00:00:38 00:00:37
Analiza złożoności czasowej algorytmów projektu, pozwala na wyznaczenie operacji,
które są najbardziej czasochłonne. Tabela 4.1 zawiera zgromadzone statystyki wydajnościowe
dla wszystkich przeprowadzanych przez aplikację operacji dla różnej liczby artykułów. Operacje
te zostały uruchomione na środowisku składającym się z klastra o 12 komputerach, gdzie 10 z
nich to były węzły wykonujące pracę obliczeniową, natomiast 2 z nich zostały skonfigurowane
jako węzły zarządzające. Parametr k dla algorytmu kNN ustawiliśmy na wartość równą 50,
natomiast walidacja skrośna została wykonana po podziale na 10 podzbiorów.
Analizując tabelę 4.1. można zauważyć, że najbardziej czasochłonną operacją są
operacje foldingu i walidacji skrośnej. Dzieje się tak, ponieważ walidacja skrośna wykonuje
bardzo dużo porównań między artykułami. Przykładowo przy analizowanym zbiorze,
zawierającym dokładnie 100 artykułów zostanie wykonanych porównań.
Liczba ta wynika z liczebności zbiorów po podziale, jeżeli zbiór 100 artykułów podzielimy na 10
równych zbiorów, to każdy z nich będzie zawierał po 10 artykułów. Każdy artykuł ze zbioru
testującego, czyli zbioru zawierającego 10 artykułów, porównujemy z każdym artykułem zbioru
trenującego, który zawiera 90 artykułów. Taka analiza jest wykonywana 10 razy, przyjmując
kolejno każdy z podzbiorów jako zbiór testujący. Z tego wynika, iż złożoność czasowa tej
procedury będzie rosła w tempie wyznaczonym przez wzór:
(


(


))





(4.1)

34. 34
k - liczba artykułów,
n - liczba podziałów zbioru.
Przykładowo dla 750 artykułów zostanie wykonanych






porównań. Widać więc, że złożoność czasowa po dodaniu 650 artykułów znacząco
wzrosła, stąd też wysokie różnice czasowe dla obu przypadków.
Drugą bardzo złożoną obliczeniowo operacją jest zliczanie słów. Tutaj złożoność
czasowa wynika w głównej mierze z analizy tekstu pod kątem występowania słów oraz
zmienianiem tych słów do ich formy podstawowej. Po uprzednim usunięciu z tekstu Wikikodu,
słowa są wyszukiwane za pomocą wyrażeń regularnych. Średni artykuł z badanego zbioru
zawiera około 13kB. Dodatkowym kosztem jest wczytanie do pamięci pliku zawierającego
odmiany słów, co zajmuje około pół minuty.
Pozostałe operacje są szybkie, nie wymagają zwiększenia wydajności, ich głównym
obciążeniem czasowym było łączenie się z klastrem Apache Hadoop i przygotowywanie
środowiska.
4.1.3 Zysk wydajności poprzez rozproszenie
Tabela 4.2 Zależność czasu wykonania od ilości węzłów klastra, dla 1500 artykułów
Liczenie słów Klasyfikacja 1 artykułu Klasyfikacja 1000
artykułów
4 węzły Slaves 01:14:21 00:00:40 00:07:18
7 węzłów Slaves 00:44:12 00:00:42 00:07:02
10 węzłów Slaves 00:32:46 00:00:40 00:07:06
Tabela 4.3 Zależność czasu wykonania od ilości węzłów klastra, dla 3000 artykułów
Liczenie słów Klasyfikacja 1 artykułu Klasyfikacja 1000
artykułów
4 węzły Slaves 02:28:41 00:00:43 00:08:26
7 węzłów Slaves 01:38:55 00:00:40 00:09:54
10 węzłów Slaves 01:24:19 00:00:52 00:09:01
Wynik wykonanych pomiarów zależności czasu wykonania poszczególnych elementów
programu od ilości węzłów klastra zostały przedstawione w tabelach 4.2 i 4.3. Pomiary
wykonano dla 2 węzłów zarządzających oraz kolejno 4, 7 i 10 węzłów wykonujących pracę
obliczeniową.
Dla operacji liczenia słów można zaobserwować widoczną poprawę czasu wykonania,
natomiast dla klasyfikacji wraz z wzrostem ilości węzłów nie zaobserwowano oczekiwanej
poprawy czasu klasyfikacji artykułów. Dopiero podczas analizy wyników można było
zidentyfikować problem. Prawdopodobnie jest to spowodowane faktem, iż część operacji

35. 35
klasyfikacji wykonywana jest na jednym węźle. Obliczanie odległości cosinusowej zostało
rozproszone, natomiast wybieranie k najlepszych sąsiadów i kategorii wykonywane jest tylko na
jednym węźle.
4.2 Poprawność przypisania do kategorii
Rozdział ten poświęcony jest analizie wykonanych testów pod kątem jakościowym.
Porównane zostaną wyniki klasyfikacji przy różnych wartościach parametrów algorytmu na
zbiorach danych o różnej wielkości.
4.2.1 Porównanie jakości wybranych strategii progowania

4.1 Wykres zależności poprawności klasyfikacji od parametru k, dla 750 artykułów
Tabela 4.4 Zależność poprawności klasyfikacji od wartości parametru k, dla 750 artykułów
Wartość k
Suma true
positive
Suma false
positive
Suma false
negative
Miara
Sensitivity/
Recall
Miara
Precision
F-measure
k = 2 227 1281 1303 0.1792 0.2327 0.1921
k = 3 206 1142 1324 0.1661 0.2462 0.1880
k = 5 195 914 1335 0.1601 0.2461 0.1833
k = 10 175 714 1355 0.1487 0.2361 0.1725
k = 20 148 563 1382 0.1366 0.2197 0.1591
k = 50 126 519 1404 0.1209 0.1965 0.1419
Tabela 4.4 przedstawia wyniki pomiarów poprawności klasyfikacji w zależności od
przyjętego parametru k. Dla ujednolicenia wykonanych testów liczba artykułów jest stała i
równa 750. Artykuły zostały wybrane w sposób losowy. W celu wizualizacji wyników, do tabeli
dołączono graficzną reprezentację wyników w postaci wykresu zależności precyzji, czułości
oraz f-measure od parametru k.

36. 36
Najlepszą jakość otrzymano dla parametru k równego 2. Wraz ze wzrostem parametru
k możemy zaobserwować spadek miary Recall, co oznacza, że zmniejsza się stosunek miedzy
dobrze wybranymi kategoriami, a kategoriami oczekiwanymi.
Spadek jakości spowodowany jest znaczącym wzrostem liczby kategorii wybieranych
przez algorytm. Dla rosnącej liczby sprawdzanych sąsiadów, pula dostępnych kategorii bardzo
szybko wzrasta. Przyjęta strategia progowania wyników dla wyboru najbardziej trafnych (patrz
wzór 3.1) sprawia, że liczba zaklasyfikowanych kategorii jako poprawne wzrasta gdy
zwiększony zostaje parametr k.
Przy zwiększającej się liczbie kategorii, wynik staje się bardziej zaburzony i mniej
precyzyjny. Po analizie tabeli 4.4 można dojść do wniosku, że najlepsze wyniki klasyfikacji
osiągane są dla parametru k mieszczącego się granicach od 2 do 5 najbliższych sąsiadów.

4.2 Wykres zależności poprawności klasyfikacji od wartości progowania parametru t
Tabela 4.5 Zależność poprawności klasyfikacji od wartości progowania parametru t
Progowanie
parametru t
Suma true
positive
Suma false
positive
Suma false
negative
Miara
Sensitivity/
Recall
Miara
Precision
F-measure
90% 133 1537 1397 0.1241 0.1963 0.1432
80% 149 1756 1381 0.1290 0.1942 0.1462
50% 248 4770 1282 0.1739 0.1633 0.1519
30% 323 18840 1207 0.2046 0.1249 0.1347
10% 403 60111 1127 0.2452 0.0420 0.0567

Na powyższym wykresie można zaobserwować, że wraz ze zmniejszeniem wymagań
przypasowania artykułu do najlepszego sklasyfikowanego artykułu wartość czułości rośnie, a
precyzji maleje. Dzieje się tak ponieważ, otrzymujemy więcej kategorii, których oczekiwaliśmy,

37. 37
ale ponieważ ogółem zwiększyła się liczba zwracanych kategorii, to stosunek kategorii
poprawnych do niepoprawnych maleje. Zauważyć należy, że wartość f-measure osiąga wartość
maksymalną przy wartości 50%, a powyżej tej wartości minimalnie maleje.
4.2.2 Jakość klasyfikacji przy rosnącej liczbie artykułów

4.3 Wykres zależności poprawności klasyfikacji od ilości artykułów, dla k = 2
Tabela 4.6 Zależność poprawności klasyfikacji od ilości artykułów, dla k = 2
Liczba
artykułów
Suma true
positive
Suma false
positive
Suma false
negative
Miara
Sensitivity/
Recall
Miara
Precision
Miara
f-Measure
100 38 175 178 0.2619 0.3416 0.2840
250 134 557 551 0.2833 0.3559 0.3030
500 170 831 849 0.1773 0.2341 0.1937
750 227 1281 1303 0.1792 0.2327 0.1922

Tabela 4.6 przedstawia wyniki pomiarów dokonanych dla stałej wartości parametru k
równej 2 i zmiennej liczbie artykułów w puli testowej. Tabela zawiera podsumowanie wyników
walidacji skrośnej dla całego badanego zbioru i zawiera sumy true positive, false positive, false
negative oraz uśrednione wartości miar sensitivity, precision, f-Measure.
Na wykresie można zaobserwować spadek jakości klasyfikacji przy wzroście liczby
artykułów. Należy zwrócić uwagę, iż jakość klasyfikacji dla tego typu klasyfikatora jest niska.
Wynik został również zaniżony faktem, że podczas weryfikacji poprawności kategorii, program
nie uwzględniał hierarchii kategorii występującej w Wikipedii, więc jeżeli klasyfikator zwrócił
kategorię bardzo podobną do szukanej lub podkategorię szukanej kategorii, to taka kategoria
zostaje uznana za błędną. W celu poprawy jakości należałoby wprowadzić ulepszenia do
klasyfikatora opisane szerzej w rozdziale 5.3.

38. 38
5. PODSUMOWANIE
W rozdziale tym znajdują się informacje dotyczące otrzymanych wyników. Obejmuje on
wnioski dotyczące wykonanej pracy oraz analizę najważniejszych osiągnięć. Dodatkowo
poruszona została kwestia ewentualnej kontynuacji pracy pod kątem udoskonaleniem jakości i
wydajności stworzonego algorytmu.
5.1 Uzyskane efekty i osiągnięcia pracy
W ramach pracy został stworzony system odpowiedzialny za klasyfikację danych
tekstowych. W trakcie projektowania zdecydowano się na wykorzystanie technologii opartych o
klastry komputerowe współpracujących bezpośrednio z maszyną wirtualną Javy. Językiem, o
który oparta jest implementacja rozwiązania, jest Scala, natomiast do obsługi logiki
rozproszenia działań zastosowano framework Apache-Hadoop. Zaprojektowany system jest w
pełni samodzielnym narzędziem, odpowiedzialnym za normalizacje danych, liczenie
podobieństw wektorów danych, dobór wyników oraz szacowanie jakości i wydajności działania
aplikacji.
Algorytmem klasyfikacji zastosowanym w projekcie jest algorytm k Najbliższych
Sąsiadów. Dane tekstowe, porównywane w algorytmie, są prezentowane jako wektory
zawierające informacje o występowaniu słów oraz ich liczności w danym tekście. Po wstępnych
testach, zdecydowano się że miarą niepodobieństwa zastosowaną w algorytmie będzie Cosine
Similarity. Z racji swojej złożoności operacje tworzenia wektorów słów oraz obliczania
odległości cosinusowej dla dwóch wektorów
zostały operacjami, na których zastosowano rozproszenie.
Do przetestowania poprawności otrzymanych wyników oraz wydajności działania
algorytmu zaimplementowano proces kroswalidacji. Tutaj także z racji dużej złożoności operacji
zostało zastosowane rozproszenie. Wszystkie operacje składające się na proces kroswalidacji
tj. liczenie podobieństwa cosinusowego, wyszukiwanie k najbliższych sąsiadów oraz
sumowanie wyników i obliczanie średniej zostały zrównoleglone.
Głównym celem pracy jest poruszenie problemu wydajności klasyfikacji, natomiast
jakość wyników została zniesiona na drugi plan. W celu ulepszenia wydajności oraz
umożliwieniu łatwego skalowania całego systemu, postanowiliśmy wykorzystać technologię
MapReduce, która została zaprojektowana z myślą o analizie dużej ilości danych. Zwiększanie
ilości węzłów rozproszonego klastra obliczeniowego przyspieszyło wydajność klasyfikacji, jest
ona zadowalająca na większości etapach działania algorytmu. Największa strata obliczeniowa
generowana jest w trakcie działania kroswalidacji. Powodem straty jest bardzo duża ilość
porównań między artykułami, natomiast problem ten tylko w małym stopniu udało sie zwalczyć
rozproszeniem. W przypadku pozostałych etapów tj. normalizacji danych, działania algorytmu
klasyfikacji czy foldingu zauważalna jest znaczna poprawa wydajności działania procesów
w zależności od ilości wykorzystanych węzłów klastra.
Wyniki jakościowe klasyfikacji nie przekraczają 20% dla poszczególnych zestawów
danych wejściowych, co jasno pokazuje że skala problemu jest znacznie bardziej

39. 39
skomplikowana. Mimo to otrzymane narzędzie stanowi solidną podstawę do dalszego rozwoju
w dziedzinie klasyfikacji danych tekstowych.
Zaprezentowane w powyższej pracy rozwiązanie problemu, testy oraz analiza
otrzymanych wyników ukazują, że zagadnienia związane z pracą zostały sumiennie
opracowane, stawiane wymagania zrealizowane oraz cel pracy osiągnięty.
5.2 Wnioski z przeprowadzonych badań
Podczas prowadzenia badań nad powyższym zagadnieniem natrafiono na wiele
aspektów związanych z rozpraszaniem aplikacji czy klasyfikacją danych. Poniższe wnioski
przedstawiają nabytą wiedzę podczas wykonywania projektu:
● wszelkie technologie oparte o MapReduce dobrze nadają się do implementacji
klasyfikacji opartej o algorytm kNN, ze względu na skuteczne rozdzielanie zadań
w oparciu o zadany klucz. W przypadku klasyfikacji artykułów, kluczem tym może być
nazwa danego artykułu,
● klasyfikacja danych jest procesem bardzo złożonym, wymagającym zastosowania wielu
technik w celu zwiększenia jej efektywności i zmniejszenia złożoności czasowej,
● kluczem do efektywnej klasyfikacji jest dobór odpowiednich charakterystyk danych
wejściowych,
● zastosowanie technologii Apache Hadoop znacznie usprawnia realizację podobnych
projektów, ponieważ pomaga programiście uzyskać pełne rozproszenie danych oraz
przy pomocy MapReduce pomaga rozproszyć obliczenia pomiędzy węzły klastra,
● technologia Apache Hadoop nadaje się również do realizacji wielu innych projektów,
na przykład do realizacji rozproszonej bazy danych.

Przeprowadzane testy wydajnościowe i jakościowe działania algorytmu prowadzą do
następujących konkluzji:
● zastosowana strategia progowania wyników na poziomie 90% nie zawsze korzystnie
wpływa na jakość wyników,
● zastosowany sposób oceny jakości (f-measure) okazał się być dobrym wyznacznikiem
jakości wyników,
● w walidacji skrośnej nie uwzględniono stratyfikacji (podziału na zbioru artykułów na
foldy tak, aby każdy z podzbiorów zawierał podobnej klasy artykuły) co może wpływać
negatywnie na uzyskane wyniki,
● zauważono znaczną poprawę w aspekcie złożoności czasowej dla operacji zliczania
słów wraz ze wzrostem używanych węzłów klastra, natomiast proces klasyfikacji
uzyskał wzrost wydajności znacznie niższy od oczekiwanego,
● optymalną ilością parametru k jest wartość zawierająca się między 2, a 5 najbliższych
sąsiadów,
● najbardziej czasochłonnymi operacjami są folding i walidacja skrośna i to w nich należy
doszukiwać się wąskiego gardła rozproszenia,

40. 40
● mimo zastosowania optymalnej miary niepodobieństwa dla algorytmu kNN (odległość
cosinusowa), jakość otrzymanych wyników jest niższa od oczekiwanej,
5.3 Kontynuacja pracy
Tematyka klasyfikacji jest bardzo rozległym zagadnieniem algorytmiki, a możliwości
rozwoju implementacji jest bardzo dużo. Do istniejącego projektu można dodać np. działanie
uczenia maszynowego lub sieci neuronowych w celu po dniesienia jakości otrzymanych
wyników, lub usprawnić implementacje zrównoleglenia w celu polepszenia wydajności działania
programu.
Interesujące wnioski może dać zbadanie wyników klasyfikacji z uwzględnieniem
hierarchii kategorii Wikipedii. Pomiar ilości zwróconych kategorii, które znajdują się niżej
w hierarchii (są podkategoriami) oczekiwanej kategorii, może wskazywać ile zwróconych
kategorii uznanych jako błędne było tak naprawdę bliskie poprawnej odpowiedzi.
W kwestii jakości oprócz dodania nowych technik aproksymacyjnych, warto zastanowić
się nad ulepszeniem działania algorytmu kNN. Istnieje szereg implementacji zmodyfikowanego
algorytmu kNN. Najpopularniejszym ulepszeniem, które niewątpliwie miało by korzystny wpływ
na działanie naszego algorytmu, jest wprowadzenie ważonego k, gdzie waga jest zależna od
“gęstości” danych trenujących w przestrzeni euklidesowej.
W przypadku ulepszeń wydajności działania algorytmu w pierwszej kolejności należy
przeprowadzić dokładną analizę działania algorytmu w celu odnalezienia “wąskiego gardła”.
Przede wszystkim kroswalidacja jest procesem w którym efektywne zmniejszenie ilości
porównań przyspieszyłoby znacznie działanie aplikacji. Interpretowanie przez program wyników
walidacji skrośnej, też należy poprawić, uwzględniając pełną hierarchię kategorii, nie
odrzucając tym samym kategorii bardzo podobnych do siebie. Dodatkowo należy sprawdzić,
które etapy mają najmniejszy stosunek wpływu na jakość wyników do złożoności czasowej.
W przypadku zdecydowania się na kompromis wyeliminowania najmniej efektywnych
elementów, możemy uzyskać znaczne przyspieszenie działania wraz z niewielkim wpływem na
ostateczne wyniki.

41. 41
WYKAZ LITERATURY
1. Lemma (morphology), https://en.wikipedia.org/wiki/Lemma_%28morphology%29 (data
dostępu: 2015-11-20).
2. The Zettabyte Era—Trends and Analysis,
http://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-
index-vni/VNI_Hyperconnectivity_WP.html (data dostępu: 2015-11-20).
3. Liczba artykułów w polskojęzycznej Wikipedii,
https://pl.wikipedia.org/wiki/Wikipedia:Liczba_artyku%C5%82%C3%B3w_w_polskoj%C
4%99zycznej_Wikipedii (data dostępu: 2015-11-20).
4. Karol Draszawka, Julian Szymański: Thresholding Strategies for Large Scale Multi-
Label Text Classifier, Gdańsk University of Technology, Sopot 2013.
5. Jeffrey Dean, Sanjay Ghemawat: MapReduce: Simplified Data Processing on Large
Clusters, Google Incorporated 2004.
6. Issues in the classification of text documents, http://nlp.stanford.edu/IR-
book/html/htmledition/issues-in-the-classification-of-text-documents-1.html (data
dostępu: 2015-11-20).
7. Cosine similarity, https://en.wikipedia.org/wiki/Cosine_similarity (data dostępu: 2015-11-
20).
8. Przestrzeń metryczna, https://pl.wikipedia.org/wiki/Przestrze%C5%84_metryczna (data
dostępu: 2015-11-20).
9. Metoda Sheparda, https://pl.wikipedia.org/wiki/Metoda_Sheparda (data dostępu: 2015-
11-20).
10. Dawid Strzempa: System internetowy przeznaczony do klasyfikacji danych, Praca
dyplomowa Magisterska, Politechnika Śląska, Katowice 2008,
http://www.ath.bielsko.pl/~mkordos/mgr/ds2008.pdf.
11. Łukasz Dziedzia: Porównanie jakości uogólnienia efektywności działania różnych
metod klasyfikacji z sieciami neuronowymi SONN, Praca dyplomowa magisterska, AGH
Kraków 2009, http://home.agh.edu.pl/~horzyk/pracedyplom/2009lukaszdziedzia-
pracdypl.pdf.
12. Hadoop Wiki - Name Node, https://wiki.apache.org/hadoop/NameNode (data dostępu:
2015-11-20).
13. Hadoop Wiki - Data Node, https://wiki.apache.org/hadoop/DataNode (data dostępu:
2015-11-20).
14. Apache Hadoop MapReduce Concepts,
https://docs.marklogic.com/guide/mapreduce/hadoop (data dostępu: 2015-11-20).
15. MapReduce Tutorial, https://hadoop.apache.org/docs/current/hadoop-mapreduce-
client/hadoop-mapreduce-client-core/MapReduceTutorial.html (data dostępu: 2015-11-
20).
16. Multiple Authors: An Overview of the Scala Programming Language (Second Edition),
2006, http://www.scala-lang.org/docu/files/ScalaOverview.pdf.

42. 42
WYKAZ RYSUNKÓW
2.1 Rozmieszczenie dwóch grup artykułów i artykułu klasyfikowanego na płaszczyźnie
euklidesowej .......................................................................................................................................... 13
2.2 Przykład zastosowania cosine similarity ......................................................................................... 13
2.3 Diagram przedstawiający pierwszy etap fazy mapowania .............................................................. 17
3.1 Diagram przedstawiający strukturę Trie dla słów wraz z ich formami bazowymi: dwa → dwa,
dwu → dwa, to → to, oczy → oko, oka → oko, oko → oko .................................................................. 20
3.2 Schemat działania projektu ............................................................................................................. 21
4.1 Wykres zależności poprawności klasyfikacji od parametru k, dla 750 artykułów ........................... 35
4.2 Wykres zależności poprawności klasyfikacji od wartości progowania parametru t ........................ 36
4.3 Wykres zależności poprawności klasyfikacji od ilości artykułów, dla k = 2 .................................... 37

43. 43
WYKAZ TABEL
Tabela 3.1 Wykaz parametrów uruchomienia aplikacji ............................................................... 27
Tabela 4.1 Zależność czasu wykonania poszczególnych operacji od ilości artykułów .............. 33
Tabela 4.2 Zależność czasu wykonania od ilości węzłów klastra, dla 1500 artykułów .............. 34
Tabela 4.3 Zależność czasu wykonania od ilości węzłów klastra, dla 3000 artykułów .............. 34
Tabela 4.4 Zależność poprawności klasyfikacji od wartości parametru k, dla 750 artykułów .... 35
Tabela 4.5 Zależność poprawności klasyfikacji od wartości progowania parametru t ................ 36
Tabela 4.6 Zależność poprawności klasyfikacji od ilości artykułów, dla k = 2 ............................ 37