ASPARAGUS: System do automatycznej agregacji wyników zapytań SPARQL

- autor: tsissput

Wprowadzenie

Każdy wyszukujący informacje w Internecie spotkał się z sytuacją, w której wyszukiwarka internetowa bądź inna usługa indeksująca strony internetowe proponuje np. 45 milionów wyników. Oczywiście nikt nie przegląda wszystkich, na ogół użytkownicy ograniczają się do pierwszych kilku stron. Co gorsza często okazuje się, że na tych kilku stronach (powiedzmy: wśród pierwszych 30 wyników) pojawiają się tak naprawdę dwa-trzy tematy poruszane na różne sposoby przez różnych autorów. Żeby uniknąć takich sytuacji próbowano zastosować różne rozwiązania. Jednym z nich są katalogi stron internetowych, dostarczających taksonomii pozwalających łatwo nawigować zgodnie z naszymi potrzebami informacyjnymi. Oczywiście, są one zupełnie nieprzystosowane do treści tworzonych dynamicznie przez użytkowników zgodnie z paradygmatem Web 2.0. Innym rozwiązaniem jest wykorzystanie algorytmów uczenia maszynowego i odkrywania skupień w wynikach wyszukiwania do utworzenia użytecznie opisanych grup. Implementacją tego pomysłu jest system Carrot² stworzony na Politechnice Poznańskiej. ASPARAGUS jest systemem wprowadzającym możliwość grupowania wyników wyszukiwania do semantycznych danych Web 3.0. Grupowanie wykonywane jest w oparciu o wiedzę dziedzinową zawartą w ontologii opisującej dane.

Podejście naiwne

W pierwszym odruchu można stwierdzić, że przecież RDF to tylko inne przedstawienie tych samych danych, które zawarte są w bazie danych, wystarczy więc zastosować takie samo podejście jak w bazie danych, czyli przenieść polecenia GROUP BY i HAVING z języka SQL do języka SPARQL. Takie podejście prezentuje W3C w SPARQL 1.1, zgodnie ze swoim konsekwentnym czynieniem ze SPARQL klona SQL. Trzeba jednak zauważyć, że danych RDF generalnie nie rozważa się bez wiedzy dziedzinowej zawartej w ontologii. Wtedy można zaobserwować główną wadę tego rozwiązania: bierze pod uwagę wyłącznie równość wartości wskazanego atrybutu. W konsekwencji: ciężko budować taksonomię (a ontologie w OWL z natury swojej są hierarchiczne), ciężko rozważać atrybuty numeryczne.

Prosty przykład: wyobraźmy sobie system agregujący informacje z różnych źródeł dotyczący miejsc, w których można spędzić urlop. Łatwo wyobrazić sobie powiązanie tych danych z hierarchią umiejscowienia na Ziemi, np. na jednym poziomie podział na kontynenty, na kolejnym na kraje itd. Co więcej, naturalnym wydaje się założenie, że takie dane będą posiadały informacje o położeniu geograficznym. Wyobraźmy sobie teraz użytkownika, których zadaje zapytanie do takiej bazy i prosi o pogrupowanie zgodnie z lokalizacją. Wykorzystanie taksonomii okazuje się niemożliwe, ponieważ GROUP BY sobie z nią nie poradzi i wygeneruje np. płaską strukturę grup, za to zawierającą duplikaty. Próba wykorzystania grupowania po położeniu również nie przyniesie nic dobrego, ponieważ nie powstaną grupy miast położonych blisko siebie (np. Zakopane i Chochołów).

Wniosek: zastosowanie GROUP BY nie poprawia jakości wyników wyszukiwania.

Semantyczne grupowanie

Wydaje się, że najprostszym rozwiązaniem jest rozszerzenie GROUP BY o uwzględnianie taksonomii pojęć, do których należą wyniki. Aby wykonać takie grupowanie, dla każdej zmiennej w wyrażeniu grupującym należy obliczyć najbardziej ogólne pojęcie, wywieść z niego taksonomię, a następnie obliczyć część wspólną tak powstałych hierarchii. Poniżej znajduje się szczegółowe omówienie algorytmu:

  1. Dla każdej zmiennej ?v, dla której ma być wykonywanie grupowanie:
    1. Oblicz iloczyn wszystkich typów do których należą wiązania zmiennej ?v w wynikach wyszukiwania.
    2. Jeżeli tak uzyskany iloczyn jest nienazwany, to zastąp go jego najbliższym, nazwanym przodkiem.
    3. Stwórz drzewo Tv ukorzenione w uzyskanym iloczynie i składające się z jego nazwanych podpojęć, zgodnie z hierarchią zawierania.
  2. Jeżeli potrzebne jest grupowanie po więcej niż jednej zmiennej v1, v2, …, vn, niech T będzie iloczynem drzew Tv1, Tv2, …, Tvn. W przeciwnym razie przyjmij T=Tv1. Przez iloczyn drzew A i B rozumie się drzewo C, w którym: korzeniem drzewa C jest para uporządkowana (korzeń(A), korzeń(B)), natomiast jego poddrzewami są poddrzewa stworzone przez tworzenie iloczynów drzew ze zbioru zdefiniowanego jako produkt kartezjański zbiorów drzew powstałych po usunięciu odpowiednio korzenia z drzewa A oraz korzenia z drzewa B.
  3. Krotki wynikowe należy przypisywać do najniżej położonej w hierarchii grupy, dla której spełnione jest założenie, że obiekty występujące w krotce muszą należeć do klas występujących w grupie.

Ten bardzo prosty algorytm zapewnia budowę hierarchii grup przy stosunkowo niskich nakładach obliczeniowych. Rozwiązuje on pierwszy z postawionych problemów, czyli radzi sobie z hierarchią pojęć. Jego słabą stroną pozostają literały, czyli np. wspominane współrzędne geograficzne.

Wywołanie powyżej opisanego algorytmu w ASPARAGUS-ie dokonuje się za pomocą słowa kluczowego CATEGORIZE BY.

Semantyczna analiza skupień

Alternatywnym podejściem w stosunku do przedstawionej powyżej automatycznej budowy taksonomii na podstawie bazy wiedzy, jest wykorzystanie algorytmów analizy skupień w  celu odkrywania prawidłowości w wynikach. Oczywiście dane RDF/OWL to graf obiektów i pojęć, nie możliwym jest więc zastosowanie klasycznych miar odległości stosowanych w uczeniu maszynowym dla danych numerycznych, reprezentowanych typowo jako punkty w przestrzeniach wielowymiarowych. ASPARAGUS implementuje dwie metryki odległości, reprezentujące dość mocno ówczesny stan, jednak obie nie są pozbawione poważnych wad:

  • jedna z nich, nazwana Common Classes, działa wyłącznie dla danych abstrakcyjnych i uwzględnia wyłącznie taksonomię klas, natomiast zapewnia dobrą wydajność;
  • druga, stworzona na Uniwersytecie Bari, zapewnia dobre wykorzystanie całej semantyki, ale jest niezwykle kłopotliwa obliczeniowo, a przy tym traktuje pojęcia, które są oznaczone jako rozłączne (owl:disjointWith) jako zupełnie niepodobne, co jest niezgodne z intuicją (mężczyzna i kobieta, choć są to zdecydowanie klasy rozłączne, prawdopodobnie jednak mają ze sobą więcej wspólnego niż mężczyzna i stół).

Innym, istotnym problemem, zasadniczo nie poruszanym w literaturze, jest problem stworzenia opisów grup. W typowym uczeniu maszynowym istnieją algorytmy (np. COBWEB), budujące opisy grup będące rozkładem prawdopodobieństwa wartości atrybutu w danej grupie. Nie jest to rozwiązanie nadające się do bezpośredniego przeniesienia na grunt Semantic Web, ponadto można polemizować czy opis w postaci rozkładu prawdopodobieństwa w tym wypadku byłby użyteczny dla odbiorcy. Ostatecznie ASPARAGUS oferuje dwa algorytmy grupowania:

  • algorytm k-Medoids, budujący płaską listę grup o narzuconym przez użytkownika rozmiarze i wykorzystujący medoidy jako opisy tychże grup;
  • algorytm aglomeracyjnego grupowania hierarchicznego, budujący dendrogram i wykorzystujący prostą aproksymację najbardziej specyficznego pojęcia (ang. MSC – most specific concept) do tworzenia opisów grup.

Grupowanie z wykorzystaniem miar podobieństwa dostępne jest w ASPARAGUSie z wykorzystaniem konstrukcji CLUSTER BY:

Implementacja

ASPARAGUS został stworzony jako jądro systemu, dokonujące pobierania wyników i grupowania oraz interfejs użytkownika napisany w Google Web Toolkit. Do wnioskowania wykorzystywany jest Pellet, bibliteka implementująca metodę Tableau. Jej zaletą jest kompletność i pełność wnioskowania, ale bardzo wolne działanie poważną wadą. Zainstalowany ASPARAGUS znajduje się pod adresem http://semantic.cs.put.poznan.pl/Asparagus/.

Podsumowanie

ASPARAGUS z założenia stanowi system prototypowy i jako taki spełnił świetnie swoje zadanie. Pozwolił nam wykryć słabe strony pomysłów, ale także odkryć wady zastosowanych technologii.

Powyższy wpis powstał głównie na podstawie moich doświadczeń z tworzenia ASPARAGUSa, ale także na podstawie artykułów „ASPARAGUS – A System for Automatic SPARQL Query Results Aggregation Using Semantics” (A. Ławrynowicz i inni) oraz „Categorize by: Deductive Aggregation of Semantic Web Query Results” (C. d’Amato i inni).

Jędrzej Potoniec, 84868

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s

%d blogerów lubi to: