1194 lines
58 KiB
TeX
1194 lines
58 KiB
TeX
\chapter{Ekstrakcja godzin rozpoczęcia mszy świętych}
|
||
\section{Ogólny zarys systemu}
|
||
Architektura systemu ekstrakcji godzin rozpoczęcia mszy świętych została
|
||
przedstawiona na rysunku \ref{pic:architektura}. W niniejszym podrozdziale zostanie ona
|
||
krótko opisana. Szczegółowy opis poszczególnych komponentów znajduje się w
|
||
podrozdziałach \ref{sub:zbieranie_informacji} - \ref{sub:klasyfikacja}.
|
||
|
||
System zaczyna działanie od zebrania jak największej ilości danych (nazwa parafii, adres, diecezja
|
||
itd.) o polskich parafiach ze strony \url{deon.pl}. Następnie wysyła zapytania do interfejsu API
|
||
Google w
|
||
celu znalezienia adresów internetowych parafii.
|
||
Dla każdej parafii, dla której udało się znaleźć adres URL, pobierane są wszystkie
|
||
podstrony w odległości\footnote{Zakładamy, że sieć jest grafem, zatem odległość
|
||
definiujemy tak jak w teorii grafów.} co najwyżej 3 od strony startowej.
|
||
|
||
Z dużej liczby stron parafialnych, za pomocą reguł wyodrębnione zostają
|
||
te, na których z dużym prawdopodobieństwem znajdują się godziny mszy świętych.
|
||
Następnie godziny zostają wydobyte ekstraktorem godzin
|
||
o bardzo niskiej precyzji i bardzo wysokiej wartości pokrycia.
|
||
Każda godzina wraz z kontekstem, w jakim się znajduje, trafia do anotatora.
|
||
Tam jest oznaczana jako poprawna lub niepoprawna godzina mszy
|
||
świętej\footnote{\label{hour_note}Przez „niepoprawne
|
||
godziny mszy świętych” rozumiemy godziny, które nie są
|
||
godzinami rozpoczęcia mszy świętych.}.
|
||
Regułowy ekstraktor mszy świętych o bardzo wysokiej precyzji znajduje poprawne
|
||
godziny mszy świętych i dołącza je do zaanotowanych danych.
|
||
Co więcej, w celu wyrównania
|
||
klas z nieodfiltrowanego zbioru stron parafialnych wylosowane zostają niepoprawne godziny mszy świętych.
|
||
Zebrane dane zostają użyte do wytrenowania klasyfikatora godzin opartego na
|
||
płytkich sieciach neuronowych.
|
||
|
||
Klasyfikator używany jest do przyporządkowania godzin
|
||
znalezionych przez ekstraktor godzin do następujących klas:
|
||
\begin{itemize}
|
||
\item poprawne godziny mszy świętych,
|
||
\item niepoprawne godziny mszy świętych.
|
||
\end{itemize}
|
||
|
||
\noindent Docelowe godziny rozpoczęcia mszy świętych otrzymujemy z:
|
||
\begin{itemize}
|
||
\item ekstraktora godzin mszy świętych,
|
||
\item klasyfikatora godzin.
|
||
\end{itemize}
|
||
|
||
\begin{figure}[!htb]
|
||
\center
|
||
\includegraphics[width=1\hsize]{struktura_programu.png}
|
||
\caption{Architektura systemu do ekstrakcji godzin mszy świętych.}
|
||
\label{pic:architektura}
|
||
\end{figure}
|
||
|
||
\clearpage
|
||
|
||
\section{Zbieranie informacji o parafiach}
|
||
\label{sub:zbieranie_informacji}
|
||
|
||
\begin{figure}[htb]
|
||
\center
|
||
\includegraphics[width=0.7\hsize]{crawler_adresow_trans.png}
|
||
\caption{Fragment architektury systemu przedstawiający komponent odpowiedzialny za zbieranie informacji o parafiach.}
|
||
\label{pic:pajak_nazw_parafii}
|
||
\end{figure}
|
||
Na rysunku \ref{pic:pajak_nazw_parafii} został przedstawiony fragment architektury
|
||
systemu z rysunku \ref{pic:architektura}, który zostanie omówiony w niniejszym podrozdziale.
|
||
|
||
Dane zostały zebrane z serwisu internetowego deon.pl, który zawiera 10130 parafii.
|
||
Są to prawie wszystkie polskie parafie, ponieważ według
|
||
danych statystycznych GUS\cite{gus} z 2016 roku w Polsce było
|
||
10255 parafii.
|
||
|
||
Dla każdej parafii zebrano:
|
||
\begin{itemize}
|
||
\item nazwę parafii,
|
||
\item miejscowość, w której się znajduje,
|
||
\item dokładny adres,
|
||
\item nazwę dekanatu, do którego należy,
|
||
\item nazwę diecezji, do której przynależy,
|
||
\item województwo, w którym się znajduje.
|
||
\end{itemize}
|
||
|
||
\noindent Fragment zebranych danych został przedstawiony w tabeli \ref{dane_tab}.
|
||
|
||
\begin{table}[H]
|
||
\centering
|
||
\def\arraystretch{1.1}
|
||
\begin{tabular}{ l l l l l l }
|
||
\textbf{Parafia} & \textbf{Miejscowość} & \textbf{Adres} & \textbf{Diecezja} & \textbf{Dekanat} & \textbf{Województwo} \\
|
||
\hline \\ [-2ex]
|
||
Bożego Ciała & Hel & ul. Gdań... & gdańska & Morski & pomorskie \\
|
||
Ducha Św. & Śrem & ul. Prym... & poznańska & Śrem & wielkopolskie\\
|
||
Św. Trójcy & Paszowice & Paszowic... & legnicka & Jawor & dolnośląskie\\
|
||
\\ [-1.5ex]
|
||
\end{tabular}
|
||
\caption{Fragment danych zebranych przez pająka nazw i adresów parafii.}
|
||
\label{dane_tab}
|
||
\end{table}
|
||
|
||
Do wydobycia danych użyto skryptu w języku Python, który korzystał z parsera
|
||
HTML z biblioteki \textit{Beautiful Soup}\cite{beautiful_soup}. Przy wysyłaniu zapytań do serwisu deon.pl zastosowano
|
||
algorytm \textit{Expotential Backoff}\cite{expotential_backoff}
|
||
(patrz algorytm \ref{alg:backoff}).
|
||
|
||
\begin{algorithm}
|
||
\setstretch{1.2}
|
||
\SetAlgorithmName{Algorytm}{algorithm}{List of Algorithms}
|
||
\caption{\textit{Expotential Backoff}}
|
||
\label{alg:backoff}
|
||
\SetAlgoLined
|
||
\SetKwFunction{Request}{send\_request}
|
||
\SetKwData{MaxWait}{max\_wait\_time}
|
||
\SetKwData{MaxRepeat}{repeat\_limit}
|
||
\SetKwInput{kwInput}{Stałe}
|
||
\SetKwInput{kwAlg}{Algorytm}
|
||
\SetKwInput{kwWhere}{gdzie}
|
||
\kwInput{\\
|
||
\Indp{\makebox[2.8cm][l]{\MaxWait }} $-$ maksymalny czas oczekiwania.\\
|
||
{\makebox[2.8cm][l]{\MaxRepeat }} $-$ limit liczby powtórnych zapytań pod rząd.
|
||
}
|
||
\bigskip
|
||
\kwAlg{
|
||
\begin{enumerate}[rightmargin=5mm]
|
||
\item Wyślij zapytanie do serwisu;
|
||
\item Jeśli zapytanie się nie powiodło, poczekaj 2s i wyślij kolejne zapytanie,
|
||
\item Jeśli zapytanie się nie powiodło, poczekaj 4s i wyślij kolejne zapytanie,
|
||
\item Jeśli zapytanie się nie powiodło, poczekaj 8s i wyślij kolejne zapytanie,
|
||
\item Powtarzaj do czasu aż zapytanie się powiedzie lub liczba ponownych
|
||
zapytań pod rząd wyniesie \MaxRepeat.
|
||
\end{enumerate}
|
||
}
|
||
\kwWhere{
|
||
\begin{itemize}
|
||
\setlength\itemsep{0.3em}
|
||
\item Czas oczekiwania to $2^t$, gdzie $t$ to liczba nieudanych zapytań.
|
||
\item Czas oczekiwania nie może być większy niż \MaxWait.
|
||
\end{itemize}
|
||
}
|
||
\end{algorithm}
|
||
|
||
Algorytm \ref{alg:backoff} uodparnia skrypt na przejściowe problemy z połączeniem i
|
||
zapobiega zbyt częstemu wysyłaniu zapytań do serwisu. Dla przykładu załóżmy,
|
||
że dany serwis jest obciążony i odpowiada na zapytanie z dużym opóźnieniem.
|
||
Wtedy algorytm \textit{Expotential Backoff} przy każdym kolejnym niepowodzeniu
|
||
będzie czekał coraz dłużej, zanim wyśle kolejne zapytanie. W ten sposób nie
|
||
będzie niepotrzebnie obciążał serwisu.
|
||
|
||
\section{Wyszukiwanie adresów URL parafii}
|
||
\begin{figure}[tbh!]
|
||
\center
|
||
\includegraphics[width=0.7\hsize]{crawler_url_trans.png}
|
||
\caption{Fragment architektury systemu przedstawiający komponent odpowiedzialny
|
||
za wyszukiwanie adresów URL parafii.}
|
||
\label{pic:pajak_url}
|
||
\end{figure}
|
||
|
||
Na rysunku \ref{pic:pajak_url} został przedstawiony fragment architektury
|
||
systemu z rysunku \ref{pic:architektura}, który zostanie omówiony w niniejszym podrozdziale.
|
||
|
||
\subsubsection{Pierwsze próby}
|
||
Do wyszukiwania adresów URL parafii próbowano wykorzystać wyszukiwarki takie jak
|
||
Google i DuckDuckGo. Automatycznie wysyłano zapytanie złożone z konkatenacji
|
||
nazwy parafii, jej miejscowości i ulicy, na której się znajduje. Wyszukiwarka Google dawała
|
||
zadowalające wyniki, jednak po kilkunastu zapytaniach blokowała adres IP.
|
||
Ponadto, w warunkach użytkowania serwisu i w pliku \textit{robots.txt} Google zabrania
|
||
korzystania z pająków na ich wyszukiwarce.
|
||
Wyszukiwarka DuckDuckGo nie blokowała adresu IP, ale zabraniała indeksowania w pliku \textit{robots.txt} i słabo radziła sobie z polskimi
|
||
zapytaniami. W obu przypadkach powyższa metoda stwarzała kolejny problem do
|
||
rozwiązania -- z wielu wyników wyszukiwania trzeba było wybrać ten, który zawierał
|
||
adres URL parafii.
|
||
\subsubsection{Rozwiązanie}
|
||
Po wielokrotnych próbach poszukiwań znaleziono klucz do rozwiązania problemu
|
||
wyszukiwania adresów URL, jakim jest
|
||
\textit{Google Places API}\cite{google_api}. Serwis \textit{Text Search}\cite{text_search} pozwala na wyszukanie miejsca
|
||
danego obiektu na
|
||
podstawie jego nazwy. Ponadto, mając już wyszukany dany obiekt i jego
|
||
identyfikator można odpytać serwis \textit{Place Detail}\cite{place_detail}, aby wyciągnąć więcej
|
||
szczegółów o danym miejscu. Między innymi można otrzymać adres URL danego obiektu.
|
||
|
||
Jedynym minusem jest ograniczenie liczby zapytań do 1000 na 24 godziny. W
|
||
dodatku, każde zapytanie do serwisu \textit{Text Search} traktowane jest jak 10
|
||
zapytań. Podając swoją kartę płatniczą, można zwiększyć limit
|
||
zapytań do 150 000 na 24 godziny. Karta płatnicza jest potrzebna Google do
|
||
identyfikacji osoby. Żadna opłata nie jest pobierana za korzystanie z interfejsu
|
||
API.
|
||
|
||
Dla każdej parafii wykonywane jest zapytanie do serwisu \textit{Text Search}.
|
||
Składa się ono z konkatenacji nazwy parafii, jej miejscowości i ulicy, na której
|
||
się znajduje. Jeśli nie zostanie znaleziony żaden obiekt, wysyłane jest powtórne
|
||
zapytanie, lecz tym razem składające się tylko z nazwy parafii i jej
|
||
miejscowości.
|
||
|
||
Zdarza się, że serwis \textit{Text Search} zwraca kilka obiektów. W takim
|
||
przypadku brany jest adres URL pierwszego obiektu z listy wyników.
|
||
Najczęściej jednak oba obiekty należą do tej samej parafii, więc mają taki sam
|
||
adres internetowy. Taki przypadek przedstawia rysunek \ref{pic:text_search}.
|
||
Serwis \textit{Text Search} zwraca dużo danych w formacie JSON, które
|
||
trudno jest przedstawić w przejrzystej postaci.
|
||
Dla
|
||
czytelności na rysunku \ref{pic:text_search} pokazano zrzuty ekranu z wyszukiwarki \textit{Google Maps},
|
||
które odpowiadają rezultatowi, jaki otrzymano, korzystając z serwisu
|
||
\textit{Text Search}.
|
||
|
||
\noindent Powyższą metodą udało się zebrać adresy URL dla ok. 5600 parafii.
|
||
|
||
\begin{figure}[tbh]
|
||
\center
|
||
\includegraphics[width=1\hsize]{amb_text_search.png}
|
||
\caption{Przykład dwóch obiektów zwróconych przez wyszukiwarkę Google, które
|
||
mają ten sam adres internetowy.}
|
||
\label{pic:text_search}
|
||
\end{figure}
|
||
|
||
|
||
\section{Indeksowanie stron parafialnych}
|
||
\enlargethispage{1\baselineskip}
|
||
\begin{figure}[htb!]
|
||
\center
|
||
\includegraphics[width=0.7\hsize]{crawler_parafii_general_trans.png}
|
||
\caption{Fragment architektury systemu przedstawiający komponent odpowiedzialny
|
||
za indeksowanie stron parafialnych.}
|
||
\label{pic:pajak_parafii_general}
|
||
\end{figure}
|
||
|
||
|
||
Na rysunku \ref{pic:pajak_parafii_general} został przedstawiony fragment architektury
|
||
systemu z rysunku \ref{pic:architektura}, który zostanie omówiony w niniejszym podrozdziale.
|
||
|
||
Pająk został napisany przy użyciu biblioteki \textit{Scrapy}\cite{scrapy}.
|
||
Punktem startowym jest pojedynczy adres URL parafii podawany na wejście
|
||
programu. Z początkowego adresu URL wydobywana jest domena, w której obrębie
|
||
porusza się pająk. Oznacza to, że jedna instancja pająka zajmuje się pobieraniem
|
||
tylko jednej parafii. W ramach jednej parafii pająk jest w stanie
|
||
asynchronicznie wysłać wiele zapytań do serwera i odbierać wiele odpowiedzi od serwera.
|
||
|
||
\subsection{Komponenty pająka}
|
||
Pająk składa się z następujących komponentów:
|
||
\begin{description}
|
||
\item [Silnik] -- odpowiada za kontrolę przepływu danych i komunikację między komponentami.
|
||
\item [Dyspozytor] -- otrzymuje żądania od \textit{silnika}, kolejkuje je i na
|
||
prośbę \textit{silnika} odsyła z powrotem.
|
||
\item [Downloader] -- odpowiada za pobieranie stron parafialnych i
|
||
przekazywanie ich \textit{silnikowi}.
|
||
\item [Procesor danych] -- zajmuje się końcową obróbką i zapisem danych.
|
||
\item [Spider]\footnote{Użyto angielskiej nazwy, aby rozróżnić
|
||
\textit{spider'a} (komponent pająka), od pająka (cały program
|
||
odpowiedzialny za indeksowanie stron parafialnych).}
|
||
- definiuje sposób, w jaki pobierać dane, między innymi jak parsować stronę i za jakimi
|
||
linkami podążać.
|
||
\item [Spider middleware] -- programy pośredniczące między \textit{silnikiem}, a
|
||
\textit{spider'em}. Odpowiedzialne są za dodatkowe przetwarzanie danych wyjściowych
|
||
(dane parafialne i żądania) i wejściowych (odpowiedzi) \textit{spider'a}.
|
||
\item [Downloader middleware] -- programy pośredniczące między silnikiem, a
|
||
\textit{downloader'em}. Zajmują się dodatkowym przetwarzaniem danych wejściowych
|
||
(żądań) i wyjściowych (odpowiedzi) \textit{downloader'a}.
|
||
|
||
\end{description}
|
||
\subsection{Przepływ danych}
|
||
|
||
Przepływ danych kontrolowany jest przez
|
||
\textit{silnik} i ma postać przedstawioną na rysunku \ref{pic:scrapy_data_flow}\footnote{Diagram i opis wzorowany jest na
|
||
dokumentacji znajdującej się pod linkiem https://doc.scrapy.org/en/latest/topics/architecture.html.}:
|
||
|
||
\begin{figure}[tbh]
|
||
\center
|
||
\includegraphics[width=0.85\hsize]{scrapy_data_flow.png}
|
||
\caption{Silnik kontrolujący przepływ danych przez komponenty pająka.}
|
||
\label{pic:scrapy_data_flow}
|
||
\end{figure}
|
||
\begin{enumerate}
|
||
\item \textit{Silnik} otrzymuje od \textit{spider'a} żądanie pobrania początkowej strony danej
|
||
parafii (najczęściej jest to strona główna parafii).
|
||
\item \textit{Silnik} oddaje żądania \textit{dyspozytorowi}, który kolejkuje je do dalszego
|
||
przetwarzania oraz pyta \textit{dyspozytor} o żądania gotowe do przekazania \textit{downloader'owi}.
|
||
\item \textit{Dyspozytor} zwraca \textit{silnikowi} następne żądania.
|
||
\item \textit{Silnik} wysyła żądania do \textit{downloader'a}. Zanim żądania dotrą do
|
||
\textit{downloader'a}, przetwarzane są przez \textit{downloader middleware}.
|
||
\item \textit{Downloader} pobiera stronę parafialną i umieszcza ją w odpowiedzi, którą
|
||
przesyła \textit{silnikowi}. Zanim odpowiedź dotrze do \textit{silnika}, przetwarzana jest przez
|
||
\textit{downloader middleware}.
|
||
\item \textit{Silnik} otrzymuje odpowiedź od \textit{downloader'a} i przekazuje ją \textit{spider'owi} do
|
||
dalszego przetwarzania. Zanim odpowiedź trafi, do \textit{spider'a} przetwarzana jest
|
||
przez \textit{spider middleware}.
|
||
\item \textit{Spider} przetwarza odpowiedź i zwraca dane strony parafialnej \textit{silnikowi}. Zanim dane
|
||
trafią do \textit{silnika}, przechodzą przez \textit{spider middleware}. Dodatkowo \textit{spider}
|
||
wysyła żądania z nowymi stronami parafialnymi do pobrania.
|
||
\item \textit{Silnik} wysyła zebrane dane do \textit{procesora danych}, który zapisuje je do
|
||
pliku. Następnie przekazuje nowe żądania do zakolejkowania
|
||
\textit{dyspozytorowi}.
|
||
\end{enumerate}
|
||
% \vspace*{-20mm}
|
||
Cały proces trwa dopóty, dopóki są nowe żądania do przetworzenia.
|
||
|
||
\subsection{Sprawdzanie typu odpowiedzi}
|
||
Podczas indeksowania ważne jest rozpoznawanie typu pobieranych danych. W przypadku
|
||
indeksowania stron parafialnych przedmiotem zainteresowania są wyłącznie dane tekstowe. Należy
|
||
zatem zadbać o to, aby nie pobierać danych binarnych takich jak np. video, audio
|
||
i obrazy.
|
||
|
||
Biblioteka \textit{Scrapy} obsługuje rozpoznawanie typu zawartości odpowiedzi, bazując na
|
||
następujących kryteriach:
|
||
\begin{itemize}
|
||
\item wartości \mintinline{bash}{Content-type}\cite{RFC2045}, \mintinline{bash}{Content-Encoding}\cite{RFC7231} i \mintinline{bash}{Content-Disposition}\cite{RFC6266} w nagłówku odpowiedzi;
|
||
\item nazwie pliku lub adresie URL (jeśli nie udało się rozpoznać po nagłówku);
|
||
\item obecności znaków kontrolnych w pierwszych 5000 bajtów odpowiedzi
|
||
(jeśli nie udało się
|
||
rozpoznać po nazwie pliku lub adresie URL).
|
||
\end{itemize}
|
||
Powyższy schemat postępowania jest skuteczny, jeśli serwisy internetowe zwracają
|
||
poprawne odpowiedzi. Niestety, niektóre strony parafialne zwracają
|
||
odpowiedzi, które nie są zgodne z rozdziałem 3.1 z dokumentu
|
||
RFC7231\cite{RFC7231}\footnote{RFC to zbiór technicznych dokumentów w formie
|
||
memorandum opisujących protokoły związane z Internetem i sieciami komputerowymi.}.
|
||
Dla przykładu strona potrafi zwrócić \mintinline{bash}{Content-Type: text/html}
|
||
w nagłówku, a w ciele -- binarną
|
||
zawartość np. film. Tego rodzaju anomalie są wykrywane i eliminowane.
|
||
\enlargethispage{3\baselineskip}
|
||
Stosując algorytm \ref{alg:binaryornot}, można określić typ zawartości
|
||
ciała odpowiedzi.
|
||
|
||
\begin{algorithm}[tbh!]
|
||
\setstretch{1.2}
|
||
\SetAlgorithmName{Algorytm}{algorithm}{List of Algorithms}
|
||
\caption{Rozpoznawanie plików binarnych}
|
||
\label{alg:binaryornot}
|
||
\SetKwIF{IfM}{ElseIfM}{ElseM}{if~(\endgraf}{\endgraf\nl)~then}{else
|
||
if}{else}{\nl end if}%
|
||
\SetKwIF{If}{ElseIf}{Else}{if}{then}{else if}{else}{\nl end if}%
|
||
\SetAlgoLined
|
||
\SetKwData{File}{bytes}
|
||
\SetKwData{True}{True}
|
||
\SetKwData{False}{False}
|
||
\SetKwInput{kwInput}{Wejście}
|
||
\SetKwInput{kwOutput}{Wyjście}
|
||
\kwInput{\File $\leftarrow$ 1024 pierwsze bajty pliku}
|
||
\kwOutput{\True jeśli plik binarny, \False jeśli plik tekstowy}
|
||
|
||
\SetKwData{ControlCount}{control\_char\_count}
|
||
\SetKwData{ControlRatio}{control\_char\_ratio}
|
||
\SetKwData{AsciiCount}{high\_ascii\_count}
|
||
\SetKwData{AsciiRatio}{high\_ascii\_ratio}
|
||
\SetKwData{Null}{null}
|
||
\nl\uIf{\File puste {\bf or} \File dekodowalne jako unikod}{
|
||
\nl \Return{\False}\;
|
||
}\ElseIf{znak \Null \bf in \File}{
|
||
\nl \Return{\True}\;
|
||
}
|
||
\nl \tcc{Za znaki kontrolne uznajemy znaki o kodach EASCII od 0 do 7, 11, od 14
|
||
do 32 i od 127 do 159.}
|
||
\nl\ControlCount $\leftarrow$ liczba znaków kontrolnych w \File\;
|
||
\nl\AsciiCount $\leftarrow$ liczba znaków EASCII o kodach od 160 do 255 w \File\;
|
||
\nl\ControlRatio $\leftarrow \frac{\ControlCount}{1024}$\;
|
||
\nl\AsciiRatio $\leftarrow \frac{\AsciiCount}{1024}$\;
|
||
\nl \If{$($\ControlRatio $> 0.3$ {\bf or} \AsciiRatio $> 0.7)$}{
|
||
\nl \Return{\True}\;
|
||
}
|
||
\nl \Return{\False}\;
|
||
\end{algorithm}
|
||
|
||
Algorytm \ref{alg:binaryornot} analizuje zawartość ciała odpowiedzi w celu
|
||
stwierdzenia, czy jest ona binarna, czy nie.
|
||
W linii 6 za znaki kontrolne uznano
|
||
wszystkie znaki kontrolne ze zbioru C0\footnote{C0 to znaki kontrolne z kodu
|
||
ASCII o kodach od 0 do 32 i o kodzie 127.} i C1\footnote{C1 to znaki kontrolne
|
||
o kodach od 128 do 159. Zostały zdefiniowane w standardzie ISO/IEC 2022.
|
||
Wiele
|
||
innych systemów kodowań rezerwuje sobie kody od 128 do 159 na znaki kontrolne.} z wyłączeniem
|
||
następujących znaków:
|
||
\begin{itemize}
|
||
\item znak nowej linii (oznaczany przez \mintinline{python}{\n}),
|
||
\item znak powrotu karetki (oznaczany przez \mintinline{python}{\r}),
|
||
\item znak tab (oznaczany przez \mintinline{python}{\t}),
|
||
\item znak backspace (oznaczany przez \mintinline{python}{\b}),
|
||
\item znak nowej linii (oznaczany przez \mintinline{python}{\n}),
|
||
\item znak końca strony (oznaczany przez \mintinline{python}{\f}),
|
||
\end{itemize}
|
||
Powyższe znaki zostały wykluczone, ponieważ często występują w plikach tekstowych.
|
||
|
||
Warto zwrócić uwagę na linię 10. Współczynnik
|
||
\mintinline{python}{control_char_ratio}
|
||
oznacza procent znaków kontrolnych w pierwszych 1024 bajtach pliku.
|
||
Jeśli współczynnik \mintinline{python}{control_char_ratio} jest większy niż
|
||
$0,3$, to plik jest uznawany za binarny. Wartość $0,3$ została przyjęta z
|
||
rozwiązania z
|
||
kodu\footnote{Kod znajduje się pod linkiem \url{https://github.com/Perl/perl5/blob/v5.27.11/pp\_sys.c\#L3605-L3665}. Wartość 0,3 występuje w linii 3661.}
|
||
źródłowego języka Perl, który między innymi zajmuje się rozpoznawaniem plików
|
||
binarnych. Natomiast współczynnik \mintinline{python}{high_ascii_ratio} oznacza
|
||
procent znaków EASCII\footnote{EASCII
|
||
oznacza rozszerzone kodowanie ASCII. Przykładowe rozszerzenia to systemy
|
||
kodowania ISO 8859 lub UTF-8.}
|
||
o kodach od 160 do 255.
|
||
Reprezentacja tych znaków zależy od rozszerzenia ASCII. Najczęściej jednak są to
|
||
znaki drukowalne, które rzadko występują w tekście.
|
||
Jeśli współczynnik \mintinline{python}{high_ascii_ratio} jest większy niż $0,7$,
|
||
to plik jest uznawany za binarny.
|
||
Wartość $0,7$ została dobrana na podstawie następujących obserwacji:
|
||
\begin{enumerate}
|
||
\item Zdarzają się pliki binarne, które mają dużo znaków
|
||
\mintinline{python}{high_ascii}. Przykładem jest plik z katalogu
|
||
\mintinline{text}{data.tar.gz/spec/resources/pixelstream.rgb}
|
||
z archiwum \url{https://rubygems.org/downloads/chunky\_png-1.2.8.gem}. Plik
|
||
zawiera bardzo dużo znaków o kodzie 255 w początkowych bajtach.
|
||
\item Mało prawdopodobne jest, aby plik tekstowy miał w pierwszych 1024 bajtach
|
||
więcej niż 70\% znaków \mintinline{python}{high_ascii}. Nawet jeśli pająk
|
||
natrafiłby na taki plik, to z dużym prawdopodobieństwem nie zawierałby on
|
||
informacji parafialnych.
|
||
\end{enumerate}
|
||
|
||
\subsection{Automatyczna regulacja częstości zapytań}
|
||
Biblioteka \textit{Scrapy} zawiera przydatne rozszerzenie, które potrafi automatycznie
|
||
regulować częstość zapytań w zależności od obciążenia pająka i serwera.
|
||
|
||
Algorytm \ref{alg:throttling} przedstawia sposób postępowania, w jaki pająk
|
||
automatycznie reguluje częstość zapytań. Idea algorytmu jest następująca.
|
||
Załóżmy, że serwer potrzebuje
|
||
\mintinline{python}{latency}\footnote{Zmienna \mintinline{python}{latency}
|
||
została
|
||
zdefiniowana w algorytmie \ref{alg:throttling}.} sekund, aby odpowiedzieć pająkowi. Jeśli pająk chce
|
||
mieć przetworzone równolegle
|
||
\mintinline{python}{target_concurrency}\footnote{Stała
|
||
\mintinline{python}{target_concurrency} została zdefiniowana w algorytmie \ref{alg:throttling}.}zapytań, to powinien
|
||
wysyłać każde zapytanie co \mintinline{python}{latency/target_concurrency}
|
||
sekund.
|
||
|
||
\begin{algorithm}[tbh!]
|
||
\setstretch{1.2}
|
||
\SetAlgorithmName{Algorytm}{algorithm}{List of Algorithms}
|
||
\caption{Algorytm regulacji częstości zapytań}
|
||
\label{alg:throttling}
|
||
\SetAlgoLined
|
||
\SetKwFunction{Request}{send\_request}
|
||
\SetKwData{Delay}{download\_delay}
|
||
\SetKwData{tDelay}{target\_download\_delay}
|
||
\SetKwData{iDelay}{init\_download\_delay}
|
||
\SetKwData{minDelay}{min\_download\_delay}
|
||
\SetKwData{maxDelay}{max\_download\_delay}
|
||
\SetKwData{latency}{latency}
|
||
\SetKwData{targetConcurrency}{target\_concurrency}
|
||
\SetKwInput{kwConst}{Stałe}
|
||
\SetKwInput{kwVar}{Zmienne}
|
||
\SetKwInput{kwWhere}{gdzie}
|
||
\SetKwInput{kwAlg}{Algorytm}
|
||
\kwConst{\\
|
||
\Indp{\makebox[4.1cm][l]{\iDelay}} $-$ początkowe opóźnienie wysłania zapytania. \\
|
||
{\makebox[4.1cm][l]{\minDelay}} $-$ minimalne opóźnienie wysłania zapytania. \\
|
||
{\makebox[4.1cm][l]{\maxDelay}} $-$ maksymalne opóźnienie wysłania zapytania.\\
|
||
{\makebox[4.1cm][l]{\targetConcurrency}} $-$ średnia wartość równoległych
|
||
zapytań do
|
||
\phantom{{\makebox[4.1cm][l]{\targetConcurrency}} $-$} wysłania.
|
||
}
|
||
\kwVar{\\
|
||
\Indp{\makebox[4.1cm][l]{\tDelay}} $-$ docelowe opóźnienie wysyłania zapytania.\\
|
||
{\makebox[4.1cm][l]{\Delay}} $-$ opóźnienie wysłania zapytania. \\
|
||
{\makebox[4.1cm][l]{\latency}} $-$ czas od ustanowienia połączenia do
|
||
\phantom{{\makebox[4.1cm][l]{\latency}} $-$} otrzymania nagłówków odpowiedzi.
|
||
}
|
||
\bigskip
|
||
\kwAlg{
|
||
\begin{enumerate}[rightmargin=5mm]
|
||
\item Wyślij zapytanie do serwisu;
|
||
\item Ustaw $\Delay \leftarrow \iDelay$.
|
||
\item Gdy odebrano odpowiedź, ustaw
|
||
$\tDelay \leftarrow \frac{\latency}{\targetConcurrency}$.
|
||
\item Ustaw $\Delay \leftarrow \frac{\Delay\ +\ \tDelay}{2}$
|
||
\item Czekaj \Delay sekund.
|
||
\item Wyślij kolejne zapytanie do serwisu;
|
||
\item Wróć do kroku nr 3.
|
||
\end{enumerate}
|
||
}
|
||
\kwWhere{
|
||
\begin{itemize}
|
||
\item Opóźnienia liczone są w sekundach.
|
||
\item \Delay nie może być mniejszy niż \minDelay i większy niż \maxDelay.
|
||
\item Czasy oczekiwania na odpowiedzi z kodem http różnym od 2xx nie są brane
|
||
pod uwagę.
|
||
\item Algorytm kończy się, gdy nie ma więcej zapytań do wysłania.
|
||
\end{itemize}
|
||
}
|
||
\end{algorithm}
|
||
|
||
\clearpage
|
||
\noindent W pająku stron parafialnych stałe z algorytmu \ref{alg:throttling} ustawiono następująco:
|
||
|
||
\begin{itemize}
|
||
\item \mintinline{python}{min_download_delay = 0}
|
||
\item \mintinline{python}{max_download_delay = 300}
|
||
\item \mintinline{python}{init_download_delay = 5}
|
||
\item \mintinline{python}{target_concurrency = 1}
|
||
\end{itemize}
|
||
Stałe \mintinline{python}{min_download_delay} i
|
||
\mintinline{python}{max_download_delay} zostały ustawione w taki sposób, aby nie
|
||
ograniczać zbyt mocno
|
||
pająka co do doboru wartości \mintinline{python}{download_delay}. Celem jest
|
||
przecież automatyczna regulacja wartości \mintinline{python}{download_delay}.
|
||
Niska wartość stałej \mintinline{python}{target_concurrency} umotywowana jest
|
||
dużą liczbą równolegle pracujących pająków (patrz podrozdział \ref{subsec:multiprocess}).
|
||
|
||
\subsection{Indeksowanie wieloprocesorowe}
|
||
\label{subsec:multiprocess}
|
||
\begin{figure}[tbh!]
|
||
\center
|
||
\includegraphics[width=0.72\hsize]{crawler.png}
|
||
\caption{100 pająków pracujących jednocześnie.}
|
||
\label{pic:pajaki}
|
||
\end{figure}
|
||
Pająk został zaprojektowany w ten sposób, aby bardzo łatwo można było
|
||
urównoleglić pobieranie stron parafialnych.
|
||
Z pomocą programu \textit{GNU parallel}\cite{parallel} indeksowane jest
|
||
jednocześnie 100 parafii (patrz rys. \ref{pic:pajaki}). Gdy jedna ze stu
|
||
parafii zostanie pobrana, zastępuje ją kolejna parafia. Tym sposobem przez
|
||
prawie cały czas równolegle pracuje 100 pająków. Takie podejście pozwoliło
|
||
maksymalnie wykorzystać łącze internetowe, które było wąskim gardłem w procesie
|
||
indeksowania stron parafialnych.
|
||
|
||
\subsection{Organizacja danych}
|
||
|
||
\enlargethispage{1\baselineskip}
|
||
Dane zbierane przez pająka zapisywane są do pliku w formacie JSONL\cite{jsonline}. Format JSONL charakteryzuje się tym, że w każdej linii pliku
|
||
znajduje się poprawny obiekt JSON.
|
||
Dla
|
||
każdej parafii pobrane dane zapisywane są w oddzielnym pliku. W każdej linii
|
||
pliku znajduje się strona parafialna zapisana w formacie JSON.
|
||
Taki sposób organizacji danych przynosi szereg korzyści takich jak:
|
||
\begin{enumerate}
|
||
\item wygodne przetwarzanie równoległe,
|
||
\item łatwa obróbka danych za pomocą narzędzi Uniksowych,
|
||
\item mniejszy rozmiar pliku w porównaniu do zwykłego formatu JSON.
|
||
\end{enumerate}
|
||
|
||
\noindent Dla każdej strony parafialnej zapisywane są następujące informacje:
|
||
\begin{enumerate}
|
||
\item adres URL strony,
|
||
\item adres URL poprzedniej strony,
|
||
\item adres URL strony początkowej,
|
||
\item domena parafii,
|
||
\item strona parafii w formacie HTML,
|
||
\item tekst z odnośnika (linku), który doprowadził do bieżącej strony.
|
||
\end{enumerate}
|
||
|
||
\section{Konwersja HTML na tekst.}
|
||
\begin{figure}[tbh!]
|
||
\center
|
||
\includegraphics[width=0.53\hsize]{html2text_trans.png}
|
||
\caption{Fragment architektury systemu przedstawiający komponent odpowiedzialny
|
||
za konwersje HTML na tekst.}
|
||
\label{pic:html2text}
|
||
\end{figure}
|
||
|
||
Na rysunku \ref{pic:html2text} został przedstawiony fragment architektury
|
||
systemu z rysunku \ref{pic:architektura}, który zostanie omówiony w niniejszym podrozdziale.
|
||
|
||
Do konwersji z formatu HTML na format tekstowy wykorzystano bibliotekę \mintinline{bash}{html2text}\cite{html2text}
|
||
pierwotnie rozwijaną przez Aarona Schwartza.
|
||
\mintinline{bash}{html2text} konwertuje HTML na czysty, czytelny tekst w
|
||
formacie \textit{Markdown}\cite{markdown}. Biblioteka oferuje wiele opcji do kontroli
|
||
konwersji i jest bardzo łatwa w modyfikacji.
|
||
|
||
\smallskip
|
||
\noindent Zastosowano następujące opcje i modyfikacje przy konwersji:
|
||
\vspace{-2mm}
|
||
\begin{itemize}
|
||
% \setlength{\itemsep}{1pt}
|
||
\item ignorowanie linków, tabel i obrazków,
|
||
\item usuwanie znaków odpowiedzialne za pogrubienie i kursywę tekstu,
|
||
\item usuwanie znaków odpowiedzialne za tworzenie list.
|
||
\end{itemize}
|
||
|
||
\section{Ekstrakcja godzin}
|
||
\begin{figure}[tbh!]
|
||
\center
|
||
\includegraphics[width=0.65\hsize]{general_ekstraktor.png}
|
||
\caption{Fragment architektury systemu przedstawiający komponent odpowiedzialny
|
||
za ekstrakcję godzin ze stron parafialnych.}
|
||
\label{pic:general_ekstraktor}
|
||
\end{figure}
|
||
Na rysunku \ref{pic:html2text} został przedstawiony fragment architektury
|
||
systemu z rysunku \ref{pic:architektura}, który zostanie omówiony w niniejszym podrozdziale.
|
||
|
||
Ekstraktor godzin służy do znajdowania bardzo ogólnych ciągów znaków mogących
|
||
być godzinami rozpoczęcia mszy świętych. Został napisany z myślą, aby miał
|
||
bardzo wysoką wartość pokrycia, ale już niekoniecznie wysoką precyzję.
|
||
Celem jest,
|
||
aby w zbiorze wyekstrahowanych godzin znalazło się jak najwięcej godzin
|
||
rozpoczęcia mszy, bez względu na to, jak duży jest ten zbiór.
|
||
|
||
Do osiągnięcia tego celu zastosowano następujące reguły.
|
||
Ciąg znaków oznaczony jako \mintinline{bash}{hour} zostanie wyekstrahowany, jeśli
|
||
zajdzie każdy z poniższych warunków:
|
||
\begin{enumerate}
|
||
\item \mintinline{bash}{hour} pasuje do wyrażenia regularnego \\ \mintinline{text}{(0?[6-9]|1\d|2[0-2])[:.](oo|[0-5]\d)|6|7|8|9|1\d|2[0-2]};
|
||
\item Znak przed \mintinline{bash}{hour} zawiera się w
|
||
\mintinline{python}{{',', '('}};
|
||
\item Znak po \mintinline{bash}{hour} zawiera się w
|
||
\mintinline{python}{{',', ')', ';'}};
|
||
\item Jeśli znak przed \mintinline{bash}{hour} równa się
|
||
\mintinline{python}{'('}, to znak po \mintinline{bash}{hour} jest różny od \mintinline{bash}{')'}.
|
||
\end{enumerate}
|
||
Ekstraktor wraz
|
||
ze znalezioną godziną zapisuje kontekst, w jakim ta godzina się znalazła.
|
||
|
||
\section{Filtrowanie stron}
|
||
\begin{figure}[tbh!]
|
||
\center
|
||
\includegraphics[width=0.5\hsize]{filtrowanie.png}
|
||
\caption{Fragment architektury systemu przedstawiający komponent odpowiedzialny
|
||
za filtrowanie stron parafialnych.}
|
||
\label{pic:filtrowanie}
|
||
\end{figure}
|
||
Na rysunku \ref{pic:filtrowanie} został przedstawiony fragment architektury
|
||
systemu z rysunku \ref{pic:architektura}, który zostanie omówiony w niniejszym podrozdziale.
|
||
|
||
Filtr stron parafialnych ma za zadanie odnaleźć strony parafialne, na których z
|
||
dużym prawdopodobieństwem znajdują się godziny mszy świętych. Taki zabieg jest
|
||
potrzebny, aby ograniczyć liczbę godzin, które trafią do anotatora. Gdyby nie zastosowano
|
||
filtru stron parafialnych, ekstraktor godzin wśród wszystkich stron parafialnych
|
||
znalazłby ponad 3 miliony godzin. Po zaaplikowaniu filtru stron i przetworzeniu
|
||
ich przez ekstraktor godzin otrzymano 10920 godzin. Później godziny wraz z
|
||
kontekstami poddawane są anotacji. Etap ten będzie dokładniej opisany w
|
||
podrozdziale \ref{sec:anotator}.
|
||
|
||
Reguły zastosowane do zadecydowania czy dana strona zawiera godziny mszy
|
||
świętych, zostały przedstawione w
|
||
algorytmie \ref{alg:has_mass}.
|
||
\begin{algorithm}
|
||
\setstretch{1.2}
|
||
\SetAlgorithmName{Algorytm}{algorithm}{List of Algorithms}
|
||
\caption{Rozpoznawanie stron z godzinami mszy świętych.}
|
||
\label{alg:has_mass}
|
||
\SetKwIF{IfM}{ElseIfM}{ElseM}{if~(\endgraf}{\endgraf\nl)~then}{else
|
||
if}{\nl else}{\nl end if}%
|
||
\SetKwIF{If}{ElseIf}{Else}{if}{then}{else if}{else}{\nl end if}%
|
||
\SetAlgoLined
|
||
\SetKwData{link}{url}
|
||
\SetKwData{bText}{btn\_text}
|
||
\SetKwData{False}{False}
|
||
\SetKwData{True}{True}
|
||
\SetKwInput{kwInput}{Wejście}
|
||
\SetKwInput{kwOutput}{Wyjście}
|
||
\kwInput{\\
|
||
\vspace{-0.5mm}
|
||
\Indp\link $\leftarrow$ adres internetowy analizowanej strony,\\
|
||
\bText $\leftarrow$ tekst na przycisku, który doprowadził do
|
||
analizowanej \phantom{\bText $\leftarrow$} strony.
|
||
}
|
||
|
||
\kwOutput{
|
||
\vspace{-2mm}
|
||
\begin{itemize}[rightmargin=5mm]
|
||
\setlength\itemsep{-1mm}
|
||
\item \True jeśli jest wysokie prawdopodbieństwo, że strona zawiera godziny mszy
|
||
\item \False jeśli jest niskie prawdopodbieństwo, że strona zawiera godziny mszy
|
||
\end{itemize}
|
||
}
|
||
|
||
\SetKwData{suf}{url\_suf}
|
||
\SetKwData{slash}{'/'}
|
||
\SetKwData{goodreg}{ok\_regex}
|
||
\SetKwData{badreg}{bad\_regex}
|
||
|
||
\nl\tcc{Wyrażenia regularne \goodreg i \badreg ignorują wielkość liter.}
|
||
\nl $\goodreg \leftarrow$
|
||
\mintinline[breaklines]{python}{'msze|nabo[żz]e[ńn]stw(a|(?=\W\d)|$)|
|
||
porz[ąa]dek($|\.htm)|porz[aą]dek.(liturgi|mszy)| (rozk[lł]ad|plan|godziny|uk[lł]ad|harmonogram|grafik|rozpiska).mszy'}
|
||
|
||
\medskip \vspace{-1mm}
|
||
\nl $\badreg \leftarrow$
|
||
\mintinline[breaklines]{python}{'nabo[zż]e[nń]stwa.(majowe|wielk|czerwcowe |maryjne|pasyjne|pokutne|fatimskie|do|ro[żz]a|czterdzie|w.wielk)'}
|
||
|
||
\nl$\suf \leftarrow$ ciąg znaków w \link po ostatnim wystąpieniu \slash\;
|
||
|
||
\nl\uIfM{\begin{tabular}{@{\hspace*{-3.8pt}}l@{}}
|
||
\nl \hspace*{1.2em}
|
||
$($ \suf pasuje do $\goodreg$ {\bf and} \suf nie pasuje do \badreg $)$ {\bf or}\\
|
||
\nl \hspace*{1.2em}
|
||
$($ \bText pasuje do $\goodreg$ {\bf and} \bText nie pasuje do \badreg $)$
|
||
\end{tabular}}{
|
||
\nl \Return{\True};\
|
||
}\ElseM{
|
||
\Return{\False};\
|
||
}
|
||
\end{algorithm}
|
||
|
||
W algorytmie \ref{alg:has_mass} warto zwrócić uwagę na wyrażenia regularne
|
||
\mintinline{text}{ok_regex} i \mintinline{text}{bad_regex}. Wyrażenie
|
||
regularne \mintinline{text}{ok_regex} ma za zadanie dopasować się do słów,
|
||
które są powiązane z porządkiem mszy świętych. Stąd też pojawiają się tam
|
||
wyrażenia takie jak „rozkład mszy” lub „porządek liturgii”.
|
||
|
||
Wyrażenie regularne \mintinline{text}{bad_regex} ma za zadanie dopasować się do
|
||
słów, które są powiązane z innymi nabożeństwami niż msze święte. Stąd pojawiają
|
||
się tam wyrażenia takie jak „nabożeństwa czerwcowe” czy „nabożeństwa maryjne”.
|
||
|
||
\section{Anotator danych}
|
||
\label{sec:anotator}
|
||
|
||
|
||
\begin{figure}[tbh!]
|
||
\center
|
||
\includegraphics[width=0.6\hsize]{annotator.png}
|
||
\caption{Fragment architektury systemu przedstawiający komponent odpowiedzialny
|
||
za anotację danych.}
|
||
\label{pic:anotator}
|
||
\end{figure}
|
||
|
||
Na rysunku \ref{pic:anotator} został przedstawiony fragment architektury
|
||
systemu z rysunku \ref{pic:architektura}, który zostanie omówiony w niniejszym podrozdziale.
|
||
|
||
\subsection{Ogólny zarys}
|
||
\label{subsec:anotator}
|
||
\begin{figure}[tbh!]
|
||
\center
|
||
\includegraphics[width=0.4\hsize]{antoator.jpg}
|
||
\caption{Zrzut ekranu pokazujący interfejs anotatora na urządzeniu mobilnym.}
|
||
\label{pic:antoator}
|
||
\end{figure}
|
||
|
||
Anotator danych został stworzony w celu zebrania jak największej ilości
|
||
danych dla klasyfikatora przewidującego czy zaznaczony fragment jest godziną
|
||
rozpoczęcia mszy świętej, czy nie.
|
||
Żeby osiągnąć zamierzony cel, anotator został zaprojektowany w ten sposób, aby:
|
||
\begin{itemize}
|
||
\item był szybki,
|
||
\item był dostępny na urządzeniach mobilnych i stacjonarnych,
|
||
\item był prosty i wygodny w użyciu,
|
||
\item umożliwiał wykrywanie oszustów (osób intencjonalnie źle anotujących).
|
||
\end{itemize}
|
||
|
||
|
||
\noindent Anotator jest dostępny jako aplikacja internetowa pod adresem \url{msze.nsupdate.info}. Aplikacja jest
|
||
responsywna, więc można z niej wygodnie korzystać na każdym urządzeniu
|
||
wyposażonym w co najmniej 4-calowy wyświetlacz. Interfejs jest przejrzysty i
|
||
został pokazany na rysunku \ref{pic:antoator}. Jedyne akcje, jakie może wykonać użytkownik to:
|
||
\begin{itemize}
|
||
\item kliknąć „Tak”, jeśli zaznaczono godzinę rozpoczęcia mszy,
|
||
\item kliknąć „Nie”, jeśli zaznaczono inną godzinę,
|
||
\item cofnąć się do poprzedniej anotacji,
|
||
\item wyświetlić instrukcję obsługi.
|
||
\end{itemize}
|
||
Po naciśnięciu przycisku „Tak” lub „Nie” ekran jest automatycznie przewijany na
|
||
sam dół. Taka operacja zapewnia łatwy dostęp do przycisków odpowiedzialnych za anotację. Dzięki
|
||
temu znajdują się one również zawsze w tym samym miejscu, co ułatwia szybką
|
||
anotację.
|
||
Po naciśnięciu przycisku „Cofnij” ekran nie jest już przewijany na sam dół. W
|
||
ten sposób zapewniono wygodny dostęp do przycisku „Cofnij”. Jest to szczególnie
|
||
istotne w przypadku gdy
|
||
użytkownik zamierza cofać się wiele razy.
|
||
|
||
Aby zapewnić odpowiednią jakość anotacji, przy pierwszym uruchomieniu wyświetlana
|
||
jest instrukcja obsługi. Opisuje ona sposób, w jaki należy anotować godziny oraz
|
||
przedstawia przykłady poprawnie zaanotowanych godzin. Instrukcję można zamknąć
|
||
dopiero po przewinięciu jej na sam dół.
|
||
|
||
Aplikacja nie wymaga logowania. Taka
|
||
decyzja została podjęta ze względu na fakt, że anotatorami są wolontariusze.
|
||
Wymóg rejestracji i logowania spowodowałby zmniejszenie liczby osób chętnych do
|
||
anotacji. Takie podejście wiąże się jednak z problemem identyfikacji
|
||
użytkowników. Identyfikacja jest niezbędna do prawidłowego funkcjonowania
|
||
antotora. Chcielibyśmy wiedzieć, które godziny zostały zaanotowane przez danego
|
||
użytkownika, aby między innymi nie dać mu tych samych godzin do anotacji.
|
||
|
||
\subsection{Identyfikacja urządzeń}
|
||
\enlargethispage{3\baselineskip}
|
||
Skuteczną identyfikację można przeprowadzić, używając ciasteczek oraz pobierając różne informacje o urządzeniu.
|
||
Za pomocą biblioteki \mintinline{text}{fingerprintjs2} można między innymi zebrać następujące
|
||
dane o kliencie\cite{fingerprintjs2}:
|
||
\begin{enumerate}
|
||
\item wersję przeglądarki,
|
||
\item język,
|
||
\item głębię koloru,
|
||
\item rozdzielczość ekranu,
|
||
\item strefę czasową,
|
||
\item obsługę \textit{localStorage}\footnote{Obiekt przechowujący dane w
|
||
przeglądarce bez daty ważności.},
|
||
\item obsługę \textit{sessionStorage}\footnote{Obiekt przechowujący dane w
|
||
przeglądarce tylko na czas sesji (po zamknięciu przeglądarki dane są usuwane).},
|
||
\item wspieranie \textit{indexed DB}\footnote{Niskopoziomy interfejs API dla
|
||
transakcyjnej bazy danych do przechowywania ustrukturyzowanych danych.},
|
||
\item klasę CPU,
|
||
\item system operacyjny,
|
||
\item listę zainstalowanych czcionek,
|
||
\item listę zainstalowanych wtyczek,
|
||
\item \textit{Canvas fingerprint}\footnote{Mechanizm do tworzenia odcisków palca
|
||
przeglądarki na podstawie HTML5 Canvas. HTML5 Canvas to element języka HTML
|
||
służący do renderowania obrazów bitmapowych.},
|
||
\item \textit{WebGL fingerprint}\footnote{Mechanizm do tworzenia odcisków palca
|
||
przeglądarki na podstawie obrazków generowanych przez silnik do rysowania
|
||
grafiki \textit{WebGL}.},
|
||
\item \textit{Audio fingerprint}\footnote{Mechanizm do tworzenia odcisków palca
|
||
przeglądarki za pomocą analizy sygnału audio.},
|
||
\item \textit{Pixel ratio}\footnote{Jest to stosunek rozdzielczości logicznej do
|
||
rozdzielczości fizycznej.},
|
||
\item liczbę procesorów logicznych,
|
||
\item pojemność pamięci RAM.
|
||
\end{enumerate}
|
||
|
||
\noindent Nadawanie identyfikatora nowemu urządzeniu, a potem jego identyfikacja przedstawia się następująco:
|
||
\begin{enumerate}
|
||
\item Klient wysyła żądanie GET w celu załadowania anotatora.
|
||
\item Anotator ładuje się w przeglądarce i oblicza \textit{odcisk
|
||
palca}\footnote{Odcisk palca przeglądarki
|
||
to informacje zebrane w celu jej identyfikacji.}
|
||
przeglądarki za pomocą biblioteki \textit{fingerprintjs2}. Obliczony \textit{odcisk
|
||
palca} będzie dołączany do każdego kolejnego żądania.
|
||
\item Klient wysyła serwerowi nowe żądanie z prośbą wyświetlenia fragmentu z
|
||
godziną do anotacji. Wraz z żądaniem przesyłany jest \textit{odcisk palca} przeglądarki.
|
||
\item Serwer odbiera żądanie od klienta i oblicza unikalny identyfikator dla
|
||
klienta. Serwer zapisuje w bazie danych, że \textit{odciskowi palca} wysłanemu przez
|
||
klienta odpowiada wygenerowany identyfikator.
|
||
\item Serwer wysyła klientowi fragment do anotacji wraz z wcześniej
|
||
wygenerowanym identyfikatorem, który zostaje zapisany w nagłówku \textit{Set-Cookie}.
|
||
\item Klient odbiera fragment do anotacji. Zostaje on wyświetlony na ekranie
|
||
urządzenia. Identyfikator zawarty w nagłówku \textit{Set-Cookie} zostaje
|
||
zapisany w przeglądarce klienta. W tym momencie kończy się ładowanie anotatora.
|
||
\item Przy każdym kolejnym żądaniu ciasteczko z
|
||
identyfikatorem jest wysyłane do serwera. Na jego podstawie serwer
|
||
identyfikuje dane urządzenie. Jeśli użytkownik usunie ciasteczka z
|
||
urządzenia i wyśle kolejne zapytanie, to serwer zidentyfikuje użytkownika po
|
||
\textit{odcisku palca} przeglądarki i w nagłówku \textit{Set-Cookie} prześle
|
||
pierwotny identyfikator przydzielony danemu urządzeniu.
|
||
\end{enumerate}
|
||
|
||
|
||
\enlargethispage{3\baselineskip}
|
||
\subsection{Architektura anotatora}
|
||
|
||
Architektura anotatora została przedstawiona na rysunku \ref{pic:anotator_detailed}.
|
||
Komunikacja między serwerem a klientem przedstawia się następująco:
|
||
\begin{enumerate}
|
||
\item Klient wysyła żądanie do serwera.
|
||
\item Serwer \textit{nginx} odbiera żądanie od klienta i przekazuje je serwerowi
|
||
\textit{Gunicorn}.
|
||
\item Serwer \textit{Gunicorn} przekazuje żądanie wolnemu wątkowi roboczemu.
|
||
Jeśli każdy wątek roboczy jest zajęty, żądanie zostanie przekazane
|
||
pierwszemu wolnemu wątkowi roboczemu.
|
||
\item Aplikacja webowa \textit{Flask} przetwarza żądanie. W zależności od żądania odpowiednio
|
||
modyfikuje dane w bazie \textit{Redis}.
|
||
\item Aplikacja webowa \textit{Flask} zwraca kolejną godzinę do
|
||
anotacji z \textit{listy fragmentów do anotacji} i przekazuje ją w postaci
|
||
odpowiedzi do serwera \textit{Gunicorn}.
|
||
\item Serwer \textit{Gunicorn} odbiera odpowiedź i przekazuje ją serwerowi \textit{nginx}.
|
||
\item Serwer \textit{nginx} wysyła odpowiedź klientowi.
|
||
\end{enumerate}
|
||
|
||
\clearpage
|
||
\begin{figure}[t]
|
||
\centering
|
||
\includegraphics[width=0.65\hsize]{annotator_detailed.png}
|
||
\caption{Architektura anotatora.}
|
||
\label{pic:anotator_detailed}
|
||
\end{figure}
|
||
|
||
\section{Regułowa ekstrakcja godzin mszy}
|
||
\begin{figure}[tbh!]
|
||
\center
|
||
\includegraphics[width=0.6\hsize]{ekstraktor_regulowy.png}
|
||
\caption{Fragment architektury systemu przedstawiający komponent odpowiedzialny
|
||
za ekstrakcję godzin rozpoczęcia mszy świętych.}
|
||
\label{pic:ekstraktor_regulowy}
|
||
\end{figure}
|
||
Na rysunku \ref{pic:ekstraktor_regulowy} został przedstawiony fragment architektury
|
||
systemu z rysunku \ref{pic:architektura}, który zostanie omówiony w niniejszym podrozdziale.
|
||
|
||
Ekstraktor regułowy oparty jest na wyrażeniach regularnych.
|
||
Wyróżniamy pięć kluczowych fragmentów wyszukiwanych przez ekstraktor godzin. Są
|
||
to:
|
||
\begin{description}[labelindent=15pt, style=multiline, leftmargin=5.5cm]
|
||
\item [główny nagłówek] -- nagłówek rozpoczynający spis godzin mszy świętych (np. \say{porządek mszy}) lub \say{msze
|
||
święte}. Jest on ekstrahowany przez wyrażenie regularne\footnote{Zakładamy
|
||
, że wyrażenia regularne ignorują wielkość liter.}\\
|
||
\mintinline[breaklines]{text}{'porządek mszy (świętych|św|św\.)|}\\
|
||
\mintinline[breaklines]{text}{msz[ea][\n]+([śs]wi[eę]t[ea]|św|św\.)'}
|
||
\item [nagłówek niedzielny] -- nagłówek, po którym występują niedzielne i świąteczne
|
||
godziny mszy (np. \say{porządek świąteczny}). Jest on ekstrahowany przez
|
||
wyrażenie regularne\\
|
||
\mintinline[breaklines]{text}{'niedziel[a|e][ \n]+i[ \n]+(dni[ \n]+}\\
|
||
\mintinline[breaklines]{text}{(świąteczne|św|św\.)|święta)|niedziel[ea]|}\\
|
||
\mintinline[breaklines]{text}{porządek świąteczny'}
|
||
\item [niedzielne godziny] -- niedzielne i świąteczne godziny mszy świętych.
|
||
Są one ekstrahowane przez wyrażenie regularne \\\mintinline[breaklines]{text}{'.*[^\d]\d{1,2}[^\d].*?''}
|
||
\item [nagłówek powszedni] -- nagłówek, po którym występują godziny mszy
|
||
świętych dla dni powszednich (np. \say{w tygodniu}). Jest on ekstrahowany
|
||
przez wyrażenie regularne \\\mintinline[breaklines]{text}{'dzień powszedni|dni powszednie|w tygodniu| porządek zwykły|od poniedziałku do soboty'}
|
||
\item [powszednie godziny] -- powszednie godziny mszy świętych. Są one
|
||
ekstrahowane przez wyrażenie regularne \\\mintinline[breaklines]{text}{'(.*?[^\d\n]?\d{1,2}[^\d\n]?.*?\n)+'}.
|
||
|
||
\end{description}
|
||
W dużym uproszczeniu ekstrakcja godzin przedstawia się następująco:
|
||
\begin{enumerate}
|
||
\item Wyszukaj \textit{nagłówek główny}, \textit{nagłówek niedzielny} i
|
||
\textit{nagłówek powszedni} w taki sposób, aby:
|
||
\begin{itemize}
|
||
\item \textit{nagłówek niedzielny} był za \textit{nagłówkiem głównym}, ale
|
||
przed \textit{nagłówkiem powszednim}.
|
||
\item między \textit{nagłówkiem głównym} a \textit{nagłówkiem powszednim}
|
||
nie znajdował się żaden inny \textit{nagłówek} niż
|
||
\textit{nagłówek niedzielny}
|
||
\end{itemize}
|
||
\item Jeśli wyszukiwanie w kroku 2. się nie powiodło, szukaj na kolejnej stronie parafialnej.
|
||
\item Niedzielnymi i świątecznymi godzinami mszy świętych będą godziny między
|
||
\textit{nagłówkiem niedzielnym} a \textit{nagłówkiem powszednim} pasujące
|
||
do wyrażenia regularnego \textit{niedzielnych godzin}. Jeśli wyszukiwanie
|
||
się nie powiedzie, to rozpocznij szukanie od początku na kolejnej stronie parafialnej.
|
||
\item Godzinami powszednimi, będą godziny po \textit{nagłówku powszednim}
|
||
pasujące do wyrażenia regularnego \textit{powszednich godzin}. Jeśli wyszukiwanie
|
||
się nie powiedzie, to rozpocznij szukanie od początku na kolejnej stronie parafialnej.
|
||
|
||
\end{enumerate}
|
||
|
||
\section{Klasyfikacja godzin}
|
||
\label{sub:klasyfikacja}
|
||
|
||
\begin{figure}[tbh!]
|
||
\center
|
||
\includegraphics[width=0.9\hsize]{klasyfikator.png}
|
||
\caption{Fragment architektury systemu przedstawiający komponent odpowiedzialny
|
||
za klasyfikację godzin.}
|
||
\label{pic:klasyfikator}
|
||
\end{figure}
|
||
Na rysunku \ref{pic:klasyfikator} został przedstawiony fragment architektury
|
||
systemu z rysunku \ref{pic:architektura}, który zostanie omówiony w niniejszym podrozdziale.
|
||
|
||
|
||
Klasyfikator opary jest na płytkich sieciach neuronowych optymalizowanych metodą
|
||
stochastycznego spadku wzdłuż gradientu z
|
||
liniowo malejącym współczynnikiem uczenia. Został on wykorzystany do klasyfikacji
|
||
godzin na te będące godzinami mszy świętych i na te nimi niebędące.
|
||
|
||
\subsection{Model teoretyczny}
|
||
\label{subsec:model_teoretyczny}
|
||
|
||
Podrozdział opiera się na artykule \textit{word2vec Parameter Learning
|
||
Explained}\cite{word2vec} i artykule \textit{Bag of Tricks for Efficient Text Classification}\cite{fasttext}.
|
||
\subsubsection{Notacja}
|
||
W podrozdziale \ref{subsec:model_teoretyczny} przyjęto poniższą notację.
|
||
\boldmath %\unboldmath
|
||
\begin{description}[labelindent=25pt, style=multiline, leftmargin=2.5cm]
|
||
|
||
\item[$X_{V\times N}$] -- macierz $X$ o $V$ wierszach i $N$ kolumnach.
|
||
\item [$X_{i,j}$] -- wartość w macierzy $X$ w wierszu $i$ i kolumnie $j$.
|
||
\item [$X_{i,*}$] -- wiersz $i$ w macierzy $X$.
|
||
\item [$X_{*,j}$] -- kolumna $j$ w macierzy $X$.
|
||
\item [$x_i$] -- $x_i$ wartość pod indeksem $i$ w wektorze $x$.
|
||
\item [$w_i$] -- wektor słowa o indeksie $i$.
|
||
\item [$w_{i,j}$] -- wartość pod indeksem $j$ w $i$-tym słowie.
|
||
\end{description}
|
||
|
||
\subsubsection{Architektura sieci}
|
||
|
||
\begin{figure}[tbh!]
|
||
\center
|
||
\includegraphics[width=0.6\hsize]{cbow.png}
|
||
\caption{Architektura sieci neuronowej.}
|
||
\label{pic:cbow}
|
||
\end{figure}
|
||
|
||
Rysunek \ref{pic:cbow}\footnote{Rysunek wzorowany jest na rysunku z artykułu \textit{word2vec Parameter Learning
|
||
Explained}\cite{word2vec}} przedstawia sieć neuronową, która służy do klasyfikacji
|
||
tekstu.
|
||
Wejście do sieci składa się z wektorów słów $w_1, \dots, w_C$, gdzie $w_1,
|
||
\dots, w_C$ to słowa z klasyfikowanego zdania. Wektory słów zakodowane
|
||
zostały za pomocą kodowania \textit{one-hot encoding}\footnote{Sposób kodowania
|
||
zwany jako \say{kod 1 z n}.}.
|
||
Na wejściu mamy $C$ wektorów słów o rozmiarze $V$, gdzie $V$ to rozmiar
|
||
słownika, a $C$ to liczba słów w zdaniu. Każdy wektor słów połączony jest z warstwą
|
||
ukrytą $h$ macierzą wag $W_{V\times N}$ (współdzielą tę samą macierz). Warstwa
|
||
ukryta $h$ jest rozmiaru $N$. Warstwa ukryta $h$ łączy się z warstwą wyjściową
|
||
macierzy $H_{N\times K}$. Warstwa wyjściowa $y$ jest rozmiaru $K$, gdzie $K$
|
||
to liczba klas.
|
||
Sieć klasyfikuje zdania do klas $k_1, \dots, k_K$.
|
||
|
||
\subsubsection{Propagacja w przód}
|
||
|
||
Warstwa ukryta jest wynikiem średniej z wektorów słów $w_1, \dots,
|
||
w_C$\footnote{Zakładamy, że wektory są wektorami wierszowymi.}
|
||
pomnożonych przez macierz $W_{V\times N}$ (patrz równanie \ref{eq:hidden}).
|
||
|
||
\begin{equation}
|
||
\label{eq:hidden}
|
||
h=\frac{1}{c} \sum_{i=1}^{C}{w_i W}=\frac{1}{c} (\sum_{i}^{C}{w_i }) \cdot W
|
||
\end{equation}
|
||
|
||
W warstwie wyjściowej jako funkcja aktywacji została zastosowana funkcja
|
||
\textit{softmax}\cite{softmax}. Wejście o indeksie $j$ do funkcji \textit{softmax} obliczane jest za pomocą równania \ref{eq:softmax_input}.
|
||
\begin{equation}
|
||
\label{eq:softmax_input}
|
||
u_j=h\cdot H_{*,j}
|
||
\end{equation}
|
||
|
||
$y_j$ w warstwie wyjściowej otrzymujemy używając funkcji \textit{softmax} zgodnie z równaniem \ref{eq:output_y}
|
||
\begin{equation}
|
||
\label{eq:output_y}
|
||
y_j = \frac{exp(u_j)}{\sum_{i=1}^{K}{exp(u_i)}}
|
||
\end{equation}
|
||
Funkcja \textit{softmax} normalizuje nam wektor wyjściowy. Dzięki niej na
|
||
wyjściu z sieci otrzymujemy rozkład prawdopobieństwa klas. Możemy zatem zapisać, że
|
||
\begin{equation}
|
||
\label{eq:probyj}
|
||
p(k_j|w_1,w_2, \dots, w_C) = y_j,
|
||
\end{equation}
|
||
gdzie $k_j$ to klasa o indeksie $j$.
|
||
|
||
\subsubsection{Proces uczenia sieci neuronowej}
|
||
Proces uczenia zaczynamy od zainicjalizowania macierzy $W_{V\times N}$ i
|
||
$H_{N\times K}$ losowymi wartościami. Następnie przeprowadzamy propagację w
|
||
przód i obliczamy błąd między aktualnym a oczekiwanym wyjściem. Następnie
|
||
obliczamy gradient funkcji kosztu i poprawiamy wartości macierzy $W$ i $H$ w
|
||
kierunku gradientu.
|
||
|
||
Celem jest maksymalizacja prawdopobieństwa $p(k_{j^*}|w_1, \dots w_C)$ (patrz równania \ref{eq:max_start} - \ref{eq:max_end}), gdzie $k_{j^*}$
|
||
to wyjściowa klasa o indeksie $j^*$.
|
||
\begin{align}
|
||
\label{eq:max_start}
|
||
max(p(k_{j^*}|w_1, \dots w_C)) &= max(\frac{exp(u_{j^*})}{\sum_{i=1}^{K}{exp(u_i)}}) &\text{z \ref{eq:probyj} i \ref{eq:output_y}}\\
|
||
&= max(log(\frac{exp(u_{j^*})}{\sum_{i=1}^{K}{exp(u_i)}}))\\
|
||
\label{eq:max_end}
|
||
&= max(u_{j^*} - log(\sum_{i=1}^{K}{exp(u_i)}))
|
||
\end{align}
|
||
Zatem funkcja kosztu (celem jest jej minimalizacja) będzie przedstawiała się tak
|
||
jak na równaniu \ref{eq:loss}.
|
||
|
||
\begin{align}
|
||
E&=-(u_{j^*} - log(\sum_{i=1}^{K}{exp(u_i)})) &\text{z \ref{eq:max_end}}\\
|
||
\label{eq:loss}
|
||
&=log(\sum_{i=1}^{K}{exp(u_i)}) -u_{j^*}
|
||
\end{align}
|
||
|
||
\subsubsection{Aktualizowanie wag macierzy $H_{N\times K}$}
|
||
Najpierw należy policzyć pochodną cząstkową funkcji kosztu $E$ względem wektora
|
||
$u$ (patrz równania \ref{eq:deu_start} - \ref{eq:deu_end}).
|
||
\begin{align}
|
||
\label{eq:deu_start}
|
||
\frac{\partial E}{\partial u_j} &= \frac{\partial(log(\sum_{i=1}^{K}{exp(u_i)}) -u_{j^*})}{\partial u_j}\\
|
||
&=\frac{\partial(log(\sum_{i=1}^{K}{exp(u_i)}))}{\partial u_j} - \frac{\partial u_{j^*}}{\partial u_{j}}\\
|
||
\shortintertext{Z reguły łańcuchowej otrzymujemy:}
|
||
&=\frac{\partial(\sum_{i=1}^{K}{exp(u_i)})}{\partial u_{j}} \cdot \frac{\partial(log(\sum_{i=1}^{K}{exp(u_i)}))}{\partial(\sum_{i=1}^{K}{exp(u_i)})} - \frac{\partial u_{j^*}}{\partial u_{j}}\\
|
||
&= exp(u_j) \cdot \frac{1}{\sum_{i=1}^{K}{exp(u_i)}} - \frac{\partial u_{j^*}}{\partial u_{j}}\\
|
||
&= y_j - \frac{\partial u_{j^*}}{\partial u_{j}} &\text{z \ref{eq:output_y}}\\ \shortintertext{Za $\frac{\partial u_{j^*}}{\partial u_{j}}$ podstawiamy $t_j$:}
|
||
\label{eq:deu_end}
|
||
&= y_j - t_j \vcentcolon= e_j\\\shortintertext{gdzie $t_j = 1$, gdy $j = j^*$, w przeciwnym wypadku $t_j = 0$.}\nonumber
|
||
\end{align}
|
||
|
||
Pochodna $e_j$ to błąd predykcji warstwy wyjściowej.
|
||
Gradient dla wag z macierzy $H$ otrzymamy, licząc pochodną cząstkową
|
||
funkcji kosztu $E$ względem wag macierzy $H$ (patrz równania \ref{eq:der_start} - \ref{eq:der_end}).
|
||
\begin{align}
|
||
\label{eq:der_start}
|
||
\frac{\partial E}{\partial H_{i,j}}&=\frac{\partial E}{\partial u_j} \cdot \frac{\partial u_j}{\partial H_{i,j}} &\text{z reguły łańcuchowej}\\
|
||
&= e_j \cdot \frac{\partial(h \cdot H_{*,j})}{\partial H_{i,j}} &\text{z \ref{eq:softmax_input}}\\
|
||
&= e_j \cdot \frac{\partial(\sum_{i'=1}^{N}{h_{i'} \cdot H_{i',j}})}{\partial H_{i,j}} &\text{z definicji mnożenia macierzy}\\
|
||
\label{eq:der_end}
|
||
&= e_j \cdot h_i
|
||
\end{align}
|
||
|
||
\noindent Aktualizowanie wag macierzy $H$ zostało przedstawione w równaniu \ref{eq:update_h}.
|
||
\begin{align}
|
||
\label{eq:update_h}
|
||
H_{i,j}^{nowe} = H_{i,j}^{stare} - \eta \cdot e_j \cdot h_i\\ \shortintertext{gdzie $\eta$ to liniowo malejący współczynnik uczenia.}\nonumber
|
||
\end{align}
|
||
\subsubsection{Aktualizowanie wag macierzy $W_{V\times N}$}
|
||
Najpierw należy policzyć pochodną cząstkową funkcji kosztu $E$ względem warstwy
|
||
ukrytej $h$ (patrz równania \ref{eq:sumder_start} - \ref{eq:sumder_end}).
|
||
\begin{align}
|
||
\label{eq:sumder_start}
|
||
\frac{\partial E}{\partial h_i} &= \sum_{j=1}^{K}{\frac{\partial E}{\partial u_j} \cdot \frac{\partial u_j}{\partial h_i}} &\text{z reguły łańcuchowej}\\
|
||
&= \sum_{j=1}^{K}{e_j \cdot \frac{\partial(h \cdot H_{*,j})}{\partial h_i}} &\text{z \ref{eq:softmax_input} i z \ref{eq:deu_start} - \ref{eq:deu_end}}\\
|
||
&= \sum_{j=1}^{K}{e_j \cdot \frac{\partial(\sum_{i'=1}^{N}{h_i' \cdot H_{i',j}})}{\partial h_i}} &\text{z definicji mnożenia macierzy}\\
|
||
\label{eq:sumder_end}
|
||
&= \sum_{j=1}^{K}{e_j \cdot H_{i,j}}
|
||
\end{align}
|
||
W równaniu \ref{eq:sumder_start} mamy do czynienia z sumą ze względu na fakt,
|
||
że neuron $h_i$ połączony jest z $K$ neuronami warstwy wyjściowej. Każdy błąd
|
||
predykcji powinien być uwzględniony.
|
||
|
||
Następnie należy policzyć pochodną cząstkową funkcji $E$ względem wag w macierzy
|
||
$W$ (patrz \ref{eq:last_der_start} - \ref{eq:last_der_end}).
|
||
\begin{align}
|
||
\label{eq:last_der_start}
|
||
\shortintertext{Z reguły łańcuchowej:}
|
||
\frac{\partial E}{\partial W_{k,i}} &= \frac{\partial E}{\partial h_i} \cdot \frac{\partial h_i}{\partial W_{k,i}}&\text{}\\
|
||
\shortintertext{Z \ref{eq:sumder_start} - \ref{eq:sumder_end} i z \ref{eq:hidden}:}
|
||
&= (\sum_{j=1}^{K}{e_j \cdot H_{i,j}}) \cdot \frac{\partial (\frac{1}{C}(\sum_{i'=1}^{C}{w_{i'}})W_{*,i})}{\partial W_{k,i}}\\
|
||
\shortintertext{Z definicji mnożenia macierzy:}
|
||
&=(\sum_{j=1}^{K}{e_j \cdot H_{i,j}}) \cdot \frac{\partial (\frac{1}{C}\sum_{l=1}^{V}((\sum_{i'=1}^{C}{w_{i',l}})W_{l,i}))}{\partial W_{k,i}}\\
|
||
&=(\sum_{j=1}^{K}{e_j \cdot H_{i,j}}) \cdot \frac{1}{C}\sum_{i'=1}^{C}{w_{i',k}}\\
|
||
\intertext{Zauważmy, że $\sum_{i'=1}^{C}{w_{i',k}}=1$, bo wektory słów zakodowane są kodowaniem \textit{one-hot encoding}. Innymi słowy jest tylko jeden wektor słowa, który ma wartość 1 pod indeksem $k$. Reszta wektorów słów ma pod indeksem $k$ wartość 0. Zatem otrzymujemy:}
|
||
&=\frac{1}{C}\sum_{j=1}^{K}{e_j \cdot H_{i,j}}
|
||
\label{eq:last_der_end}
|
||
\end{align}
|
||
|
||
\noindent Aktualizowanie wag macierzy $W$ zostało przedstawione w równaniu \ref{eq:final}.
|
||
\begin{equation}
|
||
\label{eq:final}
|
||
W_{i,j}^{nowe} = W_{i,j}^{stare} - \eta \frac{1}{C} \sum_{j=1}^{K}{e_j \cdot H_{i,j}}
|
||
\end{equation}
|
||
|
||
\subsection{FastText}
|
||
Autorzy biblioteki \textit{fastText} wskazują, że podstawowy model opisany w
|
||
podrozdziale \ref{subsec:model_teoretyczny} można usprawnić. Do modelu można
|
||
dodać dodatkowe cechy w postaci \textit{n-gramów}(w modelu z podrozdziału
|
||
\ref{subsec:model_teoretyczny} zostały zastosowane unigramy). Artykuł
|
||
\textit{Bag of Tricks for Efficient Text Classification}\cite{fasttext} pokazuje,
|
||
że dodanie bigramów poprawia wyniki klasyfikatora.
|
||
Ponadto, aby przyspieszyć trenowanie, można zastosować funkcję \textit{hierarchical
|
||
softmax}\cite{fasttext}, zamiast funkcji \textit{softmax}. Taka operacja jest korzystna w
|
||
przypadku dużej liczby klas \cite{fasttext}. W przypadku klasyfikacji godzin użyto funkcji
|
||
\textit{softmax} ze względu na małą liczbę klas.
|
||
Do klasyfikacji użyto biblioteki \textit{fastText} z domyślnymi parametrami.
|
||
Rezultaty zostały przedstawione w rozdziale \ref{ch:rezultaty}.
|
||
|
||
\chapter{Rezultaty}
|
||
\label{ch:rezultaty}
|
||
W niniejszym rozdziale zebrane zostały wyniki, jakie osiągnął system ekstrakcji
|
||
informacji o godzinach rozpoczęcia mszy świętych.
|
||
|
||
\subsubsection{Dane parafii i ich adresy URL}
|
||
\noindent Udało się zebrać:
|
||
\begin{itemize}
|
||
\item \textbf{10130} nazw i adresów parafii,
|
||
\item \textbf{5600} adresów internetowych stron parafialnych,
|
||
\end{itemize}
|
||
Ręcznie na małej próbce adresów
|
||
URL stwierdzono, że
|
||
w ponad 90\% prowadzą one do poprawnych parafii.
|
||
|
||
Warto zaznaczyć, że w momencie oddania pracy do druku nie znaleziono
|
||
obszerniejszego zbioru adresów URL parafii. Serwisy internetowe zawierające
|
||
adresy URL parafii posiadały nie więcej niż 2500 tysiąca adresów URL parafii.
|
||
Większość z nich to były błędne adresy internetowe.
|
||
|
||
\subsubsection{Pająk}
|
||
Z \textbf{5600} adresów internetowych parafii pająk zaindeksował \textbf{5177} stron parafialnych.
|
||
W kilka dni pobrał około \textbf{3 000 000} stron HTML o łącznym rozmiarze \textbf{152G}. Po
|
||
konwersji stron parafialnych z formatu HTML do formatu tekstowego otrzymano \textbf{22G} tekstu.
|
||
|
||
\subsubsection{Anotator}
|
||
W dwa tygodnie od udostępnienia anotatora udało się:
|
||
\begin{itemize}
|
||
\item zebrać \textbf{10260} anotacji godzin,
|
||
\item zaanotować \textbf{9313}\footnote{Dopuszczane jest by jedna godzina była
|
||
anotowana przez wielu unikalnych użytkowników. Stąd rozbieżność między
|
||
liczbą anotacji a zaanotowanymi godzinami.} z \textbf{10920} godzin.
|
||
\end{itemize}
|
||
Dane anotowano z \textbf{177} unikalnych urządzeń.
|
||
Średni czas anotacji na urządzenie wyniósł \textbf{2,5} sekundy.
|
||
|
||
Liczba urządzeń, z których anotowano godziny mszy świętych świadczy o
|
||
zainteresowaniu społeczności katolickiej projektem automatycznego ekstraktora
|
||
godzin mszy świętych. Entuzjazm udzielał się również w komentarzach na
|
||
Facebook'u (komentarze pod postem z prośbą o anotowanie godzin mszy świętych).
|
||
Średni czas anotacji, jak i liczba zaangażowanych użytkowników potwierdzają cechy anotatora
|
||
wymienione
|
||
w podrozdziale \ref{subsec:anotator} (szybkość, dostępność i wygoda użytkowania).
|
||
\subsubsection{Regułowy ekstraktor danych}
|
||
Regułowy ekstraktor danych był w stanie znaleźć godziny mszy świętych dla około
|
||
\textbf{2600} parafii z \textbf{5177} parafii. Na małej próbce parafii ręcznie stwierdzono bardzo wysoką precyzję
|
||
ekstrahowanych danych.
|
||
|
||
\subsubsection{Klasyfikator godzin}
|
||
Do ewaluacji ekstraktora godzin wykorzystano dane zebrane przez anotator. Z 9313 zaanotowanych
|
||
godzin 80\% użyto do trenowania klasyfikatora, a 20\% do ewaluacji. Nie
|
||
przeprowadzono optymalizacji parametrów.
|
||
|
||
\noindent Otrzymano następujące wyniki:
|
||
\begin{itemize}
|
||
\item \makebox[3.8cm][l]{wartość pokrycia} $= 0,884$
|
||
\item \makebox[3.8cm][l]{precyzja} $= 0,850$
|
||
\item \makebox[3.8cm][l]{F1\footnote{F1 to średnia harmoniczna z wartości pokrycia i precyzji.}} $= 0,884$
|
||
\item \makebox[3.8cm][l]{dokładność} $= 0,858$
|
||
\end{itemize}
|
||
Wyniki są obiecujące i z pewnością można je w przyszłości znacznie poprawić.
|
||
%\textbf{9313} anotacji godzin w \textbf{dwa tygodnie} od udostępnienia anotatora,
|
||
\chapter{Podsumowanie}
|
||
W pracy opisany został zrobiony przeze mnie system do ekstrakcji informacji
|
||
godzin rozpoczęcia mszy świętych. Na początku przedstawiłem komponent
|
||
odpowiedzialny za zbieranie informacji o parafiach. Następnie przybliżyłem
|
||
metodę wyszukiwania adresów internetowych parafii. Potem dokładnie omówiłem
|
||
architekturę pająka do pobierania stron parafialnych.
|
||
W kolejnych rozdziałach krótko opisałem bibliotekę do konwersji tekstu,
|
||
ekstraktor godzin oraz wyszukiwanie stron, na których z dużym prawdopodobieństwem
|
||
znajdują się godziny mszy. Następnie omówiłem anotator służący do zbierania
|
||
danych do uczenia maszynowego. Anotator dostępny jest pod adresem
|
||
\url{msze.nsupdate.info}. Potem krótko opowiedziałem o regułowym ekstraktorze
|
||
danych. W kolejnym rozdziale przedstawiłem model teoretyczny klasyfikatora
|
||
godzin mszy. W szczególności wyprowadziłem równania na aktualizacje wag sieci
|
||
neuronowej.
|
||
Na końcu przedstawiłem informacje o wszystkich zebranych danych oraz wynikach
|
||
anotatora, ekstraktora godzin mszy świętych i klasyfikatora godzin. Otrzymane
|
||
rezultaty świadczą o sensowności projektu i zachęcają do jego dalszego rozwoju.
|
||
|
||
% \subsection{Ewaluacja wewnętrzna} %F1 score
|
||
% \subsection{Ewaluacja zewnętrzna} % w systemie webowym, użytkownicy
|
||
% \chapter{Wnioski}
|
||
%%% Local Variables:
|
||
%%% LaTeX-command: "latex -shell-escape"
|
||
%%% End:
|