W ramach Laboratorium badawczego KDD (Knowledge Discovery in Databases) będącego częścią Centrum Otwartej Nauki, ICM UW pracujemy nad metodami przechowywania i analizy treści w dużych kolekcjach dokumentów (publikacji naukowych).

Ja natomiast nazywam się Adam Kawa i jestem developerem Hadoop-a w zespole dr Łukasza Bolikowskiego zajmującego się tymi zagadnieniami. Niniejszy blog będzie miejscem, gdzie chciałbym się dzielić się naszymi doświadczeniami i przemyśleniami, związanymi z wykorzystaniem Hadoop-a w praktycznych i “biznesowych” zastosowaniach.

Dane o dokumentach

Obecnie jesteśmy w posiadaniu około 10M dokumentów w postaci plików PDF i około 17M rekordów opisujących metadane dokumentów w XML-owym formacie BWMeta. Sumuje się to do około 5 TB danych, a orientacyjny przyrost danych to 50 GB (100K dokumentów PDF plus metadane) miesięcznie.

XML-owy format BWMeta (opracowany w ICM) opisujący dokumenty, zawiera informacje takie jak tytuł dokumentu, podtytuł, abstrakt, słowa kluczowe, autorzy, afiliacje autorów w momencie pisania dokumentu, bibliografia, wydawnictwo, nazwy plików zawierające treść dokumentu itd. Więcej o BWMeta można przeczytać tutaj.

Interesuje nas zarówno przechowywanie danych, jak i modelowanie relacji między dokumentami i innymi obiektami (np. autorzy, referencje, wydawnictwa). Dodatkowo każda relacja może mieć zbiór atrybutów ją opisujących (np. rola jaką pełnił współtwórca dokumentu: tłumacz, ilustrator, autor, wydawca). Niektóre relacje wynikają bezpośrednio z metadanych (np. dokument D jest napisany w języku polskim), ale spora część będzie wywnioskowana przez nas za pomocą mniej lub bardziej skomplikowanych algorytmów grafowych/uczenia maszynowego (np. dokument D1 napisany w języku polskim jest plagiatem dokumentu D2 napisanego w języku angielskim).

Zastosowanie Hadoop-a

Dużą cześć zadań związanych z przechowywaniem i analizowaniem dokumentów chcielibyśmy rozwiązać wykorzystując ekosystem Apache Hadoop, w szczególności narzędzia takie jak HBase, MapReduce, Hive/Pig oraz Giraph (być może też Mahout).

HBase wydaje się dla nas interesującym rozwiązaniem jeżeli chodzi o elastyczny sposób przechowywania danych i (relatywnie) szybki dostęp do nich, z kolei MapReduce, Hive/Pig mogą być wykorzystywane do bardziej złożonych obliczeń działających w tle. Implementację algorytmów grafowych być może oprzemy o projekt Apache Giraph (będący jednak wciąż na etapie “inkubacji” w inkubatorze Apache).

Badane zagadnienia

Zbiór wymagań i algorytmów do zaimplementowania jest dość obszerny i ciągle ewoluuje. Jest jednocześnie na tyle różnorodny, że wygląda na to, iż wiele narzędzi z Hadoop-owego ekosystemu faktycznie znajdzie zastosowanie w jego implementacji. Poniżej znajdują się przykłady analiz na dokumentach (przygotowane przez Mateusza Kobosa), które mogą nieco przybliżyć idee naszych obliczeń:

Dodawanie i wyszukiwanie

• Dodawanie nowych obiektów i relacji między obiektami (wraz z atrybutami opisującymi te relacje)
• Wyświetlanie listy wszystkich obiektów i relacji (np. autorów z napisanymi przez nich dokumentami)
• Wyszukiwanie obiektów i relacji (np. dokumentów zawierających w tytule dany napis, autorów o danym nazwisku)

Obliczenia na grafach

• Interpretując dane jako graf gdzie wierzchołkami są osoby, a krawędziami wspólnie napisane dokumenty
• Znalezienie hub-ów, czyli osób, które współpracują z wieloma innymi osobami
• Zakładając, że znamy narodowości osób, znaleźć osoby które współpracują z wieloma osobami z zagranicy
• Znaleźć zespoły naukowe (także międzynarodowe), czyli grupy osoby, które często współpracują ze sobą
• Obliczyć liczbę Erdosa dla danej osoby.

• Interpretując dane jako graf gdzie wierzchołkami są dokumenty, a krawędziami cytaty
• Znaleźć najbardziej “wpływowe” dokumenty (wykorzystując wybraną miarę “wpływu”),  a w konsekwencji znaleźć najbardziej wypływowych autorów.

Uczenie maszynowe

• Klasteryzacja (prawdopodobnie hierarchiczna) dokumentów
• Identyfikacja “gorących” dziedzin (związana z szybkim wzrostem liczby dokumentów w danej dziedzinie)
• Identyfikacja nowo powstałych, tworzących się dziedzin, poddziedzin

Stan prac na dziś i jutro

Na początku kwietnia powinniśmy mieć już klaster z zainstalowanym Hadoop-em. Wprawdzie będą to “tylko” cztery węzły, ale są one na tyle mocne, że powinny zaspokoić nasze (póki co niewygórowane) potrzeby.

Obecnie jesteśmy na etapie modelowania HBase schema dla tabel/tabeli do przechowywania metadanych opisujących dokumenty (rekordy przychodzą do nas w formacie BWMeta), a także zapoznawania się z różnymi metodami przetwarzania danych mających swoje źródło w tabeli HBase (na razie skupiamy się na Java API, MapReduce oraz Hive, później pomyślimy też o webowych klientach). Wdrażamy się również w Apache Giraph, z którym wiążemy duże nadzieje jeżeli chodzi o algorytmy grafowe.

Liczę na to, że jeszcze w kwietniu uda nam się zaimplementować kilka najprostszych algorytmów (w tym przynajmniej jeden grafowy), które wykorzystują kilka narzędzi z Hadoop-owego ekosystemu.

Blogowanie

Ponieważ nasze doświadczenie z niektórymi narzędziami z ekosystemu Hadoop-a nie jest zbyt duże i ciągle uczymy się czegoś nowego, zdajemy sobie sprawę, że wiele naszych przypuszczeń zostanie zweryfikowanych dopiero “w praniu” i setki linii kodu zostanie wyrzucone do kosza. Nie martwimy się tym i chętnie będziemy dzielić się naszymi doświadczeniami i przemyśleniami, na stronach tego bloga.

Wszelkie komentarze i słowa krytyki mile widziane!