Archive for Listopad, 2013

Listopad 24, 2013

Graph Search, czyli semantyczna wyszukiwarka Facebooka.

- autor: tsissput

graph-search_320x197Graph Search – wyszukiwanie w socjogramie jako trzeci filar Facebooka.

Pierwszy filar to nasza nieśmiertelna ściana z wiadomościami (News Feed). Drugi – wprowadzona pod koniec 2011 roku oś czasu (Timeline).

Wyszukiwarka — bo tym właśnie z punktu widzenia użytkownika będzie Graph Search — ma pomóc odkryć coś nowego lub usprawnić poruszanie się na Facebooku.

Graph Search ma mieć mnóstwo zastosowań. Będzie można znaleźć na przykład wszystkie osoby, które mieszkają w jakimś mieście i lubią jakąś aktywność. Dzięki temu można będzie bez odrywania oczu od serwisu odkryć coś nowego, przede wszystkim nowych znajomych, na przykład znajomych naszych znajomych, z którymi mamy szansę się spotkać i mamy coś wspólnego. Ułatwi to też trafienie do popularnej wśród pewnych grup restauracji lub polecanego przez znajomych dentysty.

Facebook rozrasta się – codziennie dochodzą nowi użytkownicy, a starzy dorzucają nowe lajki, zdjęcia, linki i komentarze. Baza informacji rośnie w niesłychanym tempie. Do tej pory jednak nie było zbytniej możliwości przeszukiwania jej przez użytkowników. W efekcie Facebook jest nastawiony bardzo na to, co dzieje się „teraz” – większość osób jest przykuta do swojego strumienia aktualności, nie wychodzi poza niego. Powód jest prosty – znalezienie czegoś na Facebooku starszego niż kilka tygodni, szczególnie jeśli nie dotyczy jednej osoby i nie jest zdjęciem, jest strasznie wkurzające.

Graph Search upraszczając – jest to wyszukiwarka, która pozwala przeszukiwać bazy Facebooka. Ale to uproszczenie, porównanie do zwykłej wyszukiwarki, byłoby (szczególnie zdaniem Marka Zuckerberga) bardzo krzywdzące. Rozbijmy więc nowość na kilka punktów:

1. Uprzedzając wszelkie wątpliwości, Zuckerberg na samym początku powiedział, że użytkownicy mogą przeszukiwać jedynie te rzeczy, które zostały im udostępnione. Do tej pory bowiem wiele rzeczy było zbyt starych, żeby je wygrzebać. Teraz łatwiej będzie je znaleźć.

2. Graph Search nie opiera się o słowa kluczowe, jak robi to np. wyszukiwarka Google’a. Facebook, szczególnie w fazie beta Socjogramu, bardziej polega na elementach w swojej bazie danych – użytkownikach, fanowskich stronach czy wpisanych zainteresowaniach – i ich powiązaniach ze sobą. Dlatego jeśli będziemy szukać znajomych, którzy lubią Grę o tron, Graph Search poinformuje nas przede wszystkim o osobach, które polubiły taką stronę, a nie o tych, które gdzieś tam wspomniały o „tronie” i „grze” w jednym poście. W efekcie co prawda silnik wyszukiwania może pominąć część wartościowych informacji, odsiewa jednak wiele śmieciowych wyników.

3. Całość działa w oparciu o frazy. „Znajomi, którzy lubią…”, „Zdjęcia ze mną i …”, „Restauracje w pobliżu … lubiane przez znajomych z kraju …”, a nawet „singielki mieszkające w … i interesujące się …” – łączy się to z poprzednim punktem. Znowu, tak skonstruowane wyszukiwanie jest nieco ograniczające i może pomijać niektóre informacje, docelowo jednak ma szansę zapewnić znacznie bardziej wartościowe wyniki. Pytanie, czy się to nie zmieni w miarę rozwoju usługi i jej wychodzenia z fazy bety.

4. Całość jest zintegrowana ze stroną główną. Główna belka serwisu została całkowicie zdominowana przez pasek wyszukiwania, podczas gdy ikonki notyfikacji oraz ustawienia zostały zepchnięte do prawej strony. Wpisywane w pole frazy dynamicznie zmieniają stronę. Z punktu widzenia użytkownika to istotna cecha serwisu – upraszcza cały proces.

Graph Search ma umożliwić użytkownikowi przeszukiwanie zapisów aktywności własnej i znajomych. Będzie więc można poprosić o listę zdjęć, które użytkownik polubił, listę zdjęć konkretnych znajomych zrobionych w wybranym mieście 5 lat temu, listę zespołów, których słuchają współpracownicy, listę miast, w których mamy rodzinę i tak dalej. Na razie można zapisać się do zamkniętych testów wyszukiwarki, które prowadzone będą w tylko języku angielskim. Graph Search ma ponadto szanować ustawienia prywatności użytkowników.

Facebook chce, aby dzięki temu wyszukiwaniu życie było łatwiejsze, a świat mniejszy. Możliwe, że jest ot kolejny sposób aby użytkownicy Facebooka nie rezygnowali z serwisu, a chętniej z niego korzystali oraz pojawiali się także nowi internauci. Wall Street Journal przekazał informację, że zmniejsza się zainteresowanie Facebookiem. Analiza dotyczyła Stanów Zjednoczonych, gdzie w grudniu z serwisu przestało korzystać (czyli w ciągu miesiąca wcale go nie odwiedziło) 1,4 miliona użytkowników. W sumie używa go jeszcze ponad 167 milionów Amerykanów, ale strata jest spora i cieszy zwłaszcza w kontekście wiadomości z poniedziałku, kiedy to Guardian powiadomił, że z serwisu Zuckerberga uciekło 600 tysięcy Brytyjczyków z ponad 33 milionów, a w tym miesiącu nie zalogowało się już kolejnych 300 tysięcy. Statystyki można znaleźć na stronie czeskiej firmy SocialBakers.

Według tych samych danych, w Polsce w ciągu ostatniego miesiąca aktywnych użytkowników Facebooka przybyło prawie 400 tysięcy (171 tysięcy w ciągu ostatnich dwóch tygodni). W sumie korzysta z niego lekko ponad 10 milionów Polaków, co daje nam 23 pozycję na Świecie (z 212 monitorowanych państw). W ogólnym rozrachunku liczba użytkowników serwisu nadal rośnie i nieubłaganie zbliża się do symbolicznej granicy miliarda. W niektórych krajach użytkowników Facebook już znudził. Według analityków przytłaczające są reklamy, promowane posty i ciągłe zmiany. Pole do rozwoju nadal jednak jest — głównie w krajach Azji, gdzie z szacowanych 4 miliardów mieszkańców Facebooka używa zaledwie 7%.

Decyzja o masowym przejściu na nowy silnik zapadła w Palo Altro w lipcu 2013, a pierwszymi królikami doświadczalnymi są amerykańscy użytkownicy. Usługa została uruchomiona na kilkuset milionach kont. Zmiana jakościowa będzie ogromna. Jeśli jednak pamiętacie przepychanki ze słynną osią czasu – nie wszystkim przypadnie do gustu, bo nie wszyscy kochają super hiper mega innowacje.

Nowa funkcja jest na razie w Polsce jeszcze nie aktywna. Na tej stronie możemy się zapisać na listę oczekującą – choć część materiałów o Socjogramie (tak będzie się usługa nazywać w Polsce) została zlokalizowana, to wersja beta jest tylko dostępna dla użytkowników serwisu korzystających z amerykańskiej wersji językowej.

Firma zamierza upublicznić wyszukiwarkę w ciągu tygodni/miesięcy. W przyszłości ma się pojawić wsparcie dla aplikacji mobilnych, obsługa wszystkich języków, przeszukiwanie statusów i Open Graph.

Open Graph, czyli połączenie Graph Search z wyszukiwaniem lajków na stronach zewnętrznych. Zaprezentowano go już 3 lata temu:

Open Graph umożliwia indeksowanie stron internetowych pod względem ich „popularności” wśród użytkowników.

Tym samym firma przypomniała niejako, że jej starania o zbudowanie własnej, specyficznej wyszukiwarki trwają już od kilku lat. Zapewne to właśnie Graph Search miał na myśli Zuckerberg we wrześniu zeszłego roku.

Socjogram może okazać się jedną z najważniejszych funkcji Facebooka. Owszem, ktoś powie, że wyszukiwarka technologicznie wcale nie jest bardziej zaawansowana od rozwiązań konkurencji, szczególnie Google’a. Warto jednak pamiętać, że sam algorytm jest tylko jednym elementem całej układanki. Elementem najmniej ważnym, z punktu widzenia użytkownika. Użytkownik bowiem szuka określonych treści, jeśli więc baza danych jest uboga o nie, to nawet najlepszy algorytm nie zatuszuje tego faktu.

Źródła:

http://en.wikipedia.org/wiki/Facebook_Graph_Search

http://www.dobreprogramy.pl/

https://www.facebook.com/about/graphsearch

http://www.gazeta.pl/

http://actualfacebookgraphsearches.tumblr.com/

http://www.komputerswiat.pl

http://www.insidefacebook.com/

 Kamil Pludra, 94470

Reklamy
Listopad 24, 2013

Semantyka stron WWW, czyli co nowego w HTML5?

- autor: tsissput

Od dosyć dawna możemy projektować strony według standardu HTML5, jednakże nie wszystkie przeglądarki wspierają ten standard w równym stopniu. Także przed użyciem którejś z właściwości HTML5 warto sprawdzić, jakie przeglądarki obsługują daną opcję i na jakim poziomie.

Wracając do sedna, czyli do standardu HTML5, daje on wiele nowych możliwości, między innymi wprowadza elementy semantyczne, które nadają znaczenie sekcjom kodu dokumentu HTML, a użyte we właściwy sposób, mogą usprawnić działanie przeglądarek, wyszukiwarek i czytników ekranów dla osób niedowidzących i właśnie tymi elementami będę zajmował się w dalszej części artykułu.

Większość stron internetowych przed standardem HTML5 opierała się na elementach <div>, które nic nie mówią o zawartości znajdującej się wewnątrz elementu. Elementy te są proste w użyciu, a sposób wyświetlania i funkcję jaką pełnią możemy definiować arkuszami styli. Przyglądając się bardziej złożonemu dokumentowi HTML i elementom <div> trudno stwierdzić jaką funkcję one pełnią, tym bardziej, jeżeli nie ma żadnych komentarzy twórcy dokumentu, a klasy czy identyfikatory styli są nazwane w sposób nic nie mówiący człowiekowi. Dlatego aby odpowiedzieć sobie na to pytanie, jaką funkcję dany element <div> spełnia, należy zagłębić się w arkuszach styli, sprawdzając, jakie style są przypisane do danego elementu. Ale czy wiedza gdzie dany element jest umiejscowiony i w jaki sposób jest wyświetlany na stronie definiuję to jaką rolę pełni? Czy <div> umieszczony w dolnej części strony zawsze jest stopką? Albo czy menu zawsze znajduje się po lewej stronie strony? Dlatego HTML5 wprowadza nowe elementy semantyczne, które jednoznacznie mówią jaki element jaką pełni funkcję na stronie i zastępują zbyt ogólne elementy <div>, dzięki temu kod dokumentu jest łatwiejszy do edytowania i utrzymania, i to jest jeden z kilku powodów, aby używać nowe znaczniki. Drugim z powodów jest dostępność.  Strony dostępne to strony po których można nawigować za pomocą czynników ekranów, których używają osoby niedowidzące, dzięki elementom semantycznym łatwiej przychodzi znalezienie interesujących elementów strony. Kolejnym powodem jest optymalizacja pod kątem wyszukiwarek. Roboty przeszukujące sieć biorą pod uwagę elementy semantyczne dokumentu HTML, odpowiednie ich użycie może pomóc Twojej stronie znaleźć się na początku listy wyników wyszukiwania.

Nowe elementy semantyczne wprowadzają nową jakość w strukturze dokumentu, dzięki nim można oddzielić najpopularniejsze sekcje dokumentu a ponadto nadać znaczenie treściom w nich zawartych. Poza tym, nowe znaczniki nic nie zmieniają, nie są nim przypisane żadne style.

Jednym z najbardziej wyspecjalizowanych znaczników jest element <time>, w którym powinna być właściwie sformatowana  godzina bądź data na przykład <time>2013-11-24</time>.

Kolejnym elementem opisującym strukturę dokumentu jest element <header>,  w którym zawieramy nagłówek strony, czy też rozbudowany nagłówek artykułu. Pewnie teraz zastanawiasz się, co w wypadku, gdy na stronie będą występować oba nagłówki. Standard HTML5 nie zabrania kilkukrotnego użycia tego samego elementu semantycznego w obrębie jednej strony, jednakże im jest ich mniej i są bardziej przemyślane i właściwie użyte tym lepiej, ponieważ zbyt pochopne używanie nowych znaczników spowoduje powrót do tej samej sytuacji jak w wypadku ogólnych elementów <div>.

Następnym jest element <footer>, w której zawieramy stopkę dokumentu HTML.  Oczywiście każdy z tych elementów może zawierać inne elementy, także <div>.  Możemy na przykład umieścić informacje o autorze, menu nawigacyjne z poznanym już znacznikiem <nav>. Oczywiście wszystkich elementów nie powinnyśmy zawierać w elemencie <footer>, mogą być zawarte przed lub po tym znaczniku, ale w obrębie tego samego znacznika <div>, w którym jest zawarty element <footer>.

Niestety w HTML5 nie wprowadzono elementu <content>, w którym byłaby zawarta główna treść strony. Za to istnieje element <article> reprezentujący pewien oddzielny fragment treści, może to być wpis blogowy, czy to jakaś wiadomość. Oczywiście, w znaczniku <article> możemy zawrzeć poprzednie elementy takie jak <header> i  <footer>, w ten sposób otrzymamy artykuł z nagłówkiem, w którym będzie tytuł,  a może także podtytuł, notka o autorze.  Następnie zawieramy treść artykułu, w elemencie <div> lub <spam> a na koniec poznany także prędzej element <footer> w którym mogą być zawarte tak zwane copyrighty, czy odnośniki do innych stron. Tylko co w przypadku kiedy artykuł jest podzielony na kilka podstron? W takim przypadku, lepszym rozwiązaniem będzie, gdy każdy z części artykułu umieścimy w oddzielnym elemencie <article>.

Wyżej wspomniałem o artykule, w którego nagłówku występował także nagłówek, HTML5 wyróżnia element <hgroup>,  w którym możemy zawrzeć tytuł w elemencie <h1> a podtytuł w elemencie <h2>, jeżeli chcemy zawrzeć coś więcej, to lepiej zrobić to poza znacznikiem <hgroup>.

Mamy już zdefiniowany cały tekstowy artykuł, ale co jeśli wewnątrz tekstu będziemy chcieli zawrzeć jakiś obraz? Analogicznie jak w książkach, każdy z obrazów powinien być jednoznacznie związany z tekstem, dlatego będziemy go zawierać w elemencie <figure>. Dobrym pomysłem, jest także opis każdego z obrazu, taki opis powinien być umieszczany wewnątrz elementu <figcaption> i może on zastąpić atrybut alt ze znacznika <img>.

HTML5 wyróżnia także element <aside>, można w nim zawierać treść, który w jakiś sposób odnosi się do zawartości znacznika <article>. Może to być rozszerzenie jakiegoś zagadnienia, cytat, czy odnośnik zewnętrzny.

Elementy nawigacyjne powinniśmy zawierać w nowym elemencie <nav>, dlatego w tym znaczniku będziemy umieszczać odnośniki w obrębie danej strony lub do innych zewnętrznych stron.

Kolejnym nowym znacznikiem będzie element <section>, w którym zostają zwarte treści, nie pasujące do pozostałych elementów semantycznych.  Można w nim umieścić skróconą informację o nas, czy zestaw informacji kontaktowych, a także zbór treści na przykład lista newsów, czy też samoistne treści, które nie można nazwać artykułem. Może to być na przykład lista produktów na stronie sklepu.

Podsumowując, HTML5 wprowadza kilka nowych elementów semantycznych, przy pomocy których można zbudować strukturę semantyczną dokumentu, która niesie za sobą jednoznaczne informacje semantyczne, nie tylko dla autorów, ale także użytkowników przeglądających strony przy pomocy czytników ekranów dla osób niedowidzących a także dla robotów wyszukiwarek indeksujących stron, które biorą pod uwagę zwartość elementów semantycznych, gdzie zysk jest obopólny, użytkownicy wyszukiwarek otrzymują lepiej dopasowane wyniki a twórcy stron wyższą pozycję w wynikach wyszukiwania.

Oczywiście, zasób znaczników jest dość ubogi, z jednej strony to wada, ponieważ nie do końca możemy dopasować semantykę do prezentowanej zawartości na stronie, a z drugiej zaleta, ponieważ twórcy stron internetowych nie muszą uczyć się mnóstwa nowych znaczników, które pewnie i tak nie oddadzą całej semantyki jaką można spotkać na stronie internetowej. Reasumując, elementy semantyczne to pierwszy krok, do stworzenia w pełni semantycznych sieci WWW.

Piotr Michalak

Listopad 15, 2013

Filtrowanie społecznościowe

- autor: tsissput

Systemy rekomendacyjne

Z systemami rekomendacyjnymi spotykamy się niemal codziennie. Towarzyszą nam one w wielu dziedzinach życia, czy to kupujemy w sklepie internetowym czy słuchamy muzyki na Youtubie. Jakiś algorytm próbuje ustalić, jakie produkty nam się spodobają. Można się nawet spotkać z opinią że niektóre rekomendacje nie są trafne jedynie po to, abyśmy nie czuli się obserwowani.  Wyobraźmy sobie co by było w przeciwnym przypadku.  Jakkolwiek może wydawać się niepokojące to, jak wiele wiedzą o nas takie systemy, stoją za nimi ciekawe techniki i algorytmy.

W  problemie rekomendacji występują użytkownicy i produkty. To które któremu rekomendujemy jest w gruncie rzeczy obojętne, nieistotne czy rekomendujemy produkty użytkownikom czy użytkowników produktom.  Można sobie to wyobrazić jako macierz użytkownicy na produkty której wartości reprezentują to, na ile użytkownik i produkt do siebie pasują. Jest to często macierz rzadka, a jej puste pola należy interpretować jako nieznane, a nie zerowe, wartości. Celem algorytmów rekomendacji jest przewidzenie które z nieznanych pól będą mieć wysokie wartości, ponieważ wiedza o tych produktach stanowi możliwość zysku właściciela serwisu.

Netflix Prize

W 2006 roku amerykańska wypożyczalnia filmów Netflix ogłosiła konkurs na algorytm osiągający mniejszy średni błąd kwadratowy niż ich obecna metoda. Okazało się to bardzo dobrym sposobem na rozwój– wielu naukowców i zapaleńców kilka lat pracowało nad jak najlepszym algorytmem a nagrodę dostał jedynie zwycięzca. Firma nie musiała obciążać tym swoich pracowników, który mogli być mniej pomysłowi, a także swojego budżetu.

Różne podejścia do rekomendacji

Podczas konkursu okazało się, że najlepsze wyniki osiągały algorytmy oparte o filtrowanie społecznościowe (colaborative filtering). Nie biorą one pod uwagę żadnych jawnie określonych cech filmu czy użytkownika, ale patrzą jedynie na macierz ocen i próbują odkryć podobieństwa i zależności pomiędzy użytkownikami czy produktami  (zależności między wierszami czy kolumnami). Problemem takich systemów jest tak zwany zimny start, czyli brak możliwości rekomendacji czegokolwiek gdy nie ma żadnych znanych ocen. Ciekawy pomysł przedstawił Filmaster, proponujący użytkownikom między innymi cotygodniowe rekomendacje filmów w telewizji i kinach. Zakładając konto w serwisie należy ocenić 20 wybieranych dynamicznie przez serwis filmów.

Ułomności tej nie ma content filtering, oparte na wprowadzonych przez eksperta danych o filmach oraz informacji o użytkownikach. Może ono działać od samego początku ale okazuje się, ze osiąga gorsze rezultaty niż colaborative filtering. Poza tym wymaga od użytkownika jawnego podania danych o sobie co może prowadzić do niechęci korzystania z serwisu.

Obie metody sprowadzają się do opisania użytkowników za pomocą wektora cech, które później są porównywane czy do siebie pasują czy nie. Cechy te są jawnie podawane w filtrowaniu za pomocą treści. Systemy oparte o filtrowanie społecznościowe rozkładają macierz ocen na dwie macierze w których kolumny/wiersze odpowiadają wywiedzionym ze zbioru cechom. Może się okazać, że będą one interpretowane dla człowieka albo będą złożeniem cech na które nie wpadłby ekspert opisujący film.

Odkrywanie cech

Odkrywanie takich cech dokonuje się za pomocą rozkładu SVD macierzy, przedstawienie macierzy w taki sposób oddaje wszystkie zależności pomiędzy wartościami. Udowodnione jest, ze ciąg kolejnych wektorów własnych macierzy wraz z wartościami własnymi jest najlepszym możliwym przybliżeniem wartości macierzy na tej ilości kolumn/wierszy. Rozkład SVD niesie niestety ze sobą pewne problemy. Po pierwsze traktuje puste pola jako pewną wartość (np. zero) a nie wartość nieznaną. Po drugie obliczanie rozkładu macierzy w sposób dokładny jest kosztowne obliczeniowo, co stanowi problem w systemie z setkami tysięcy produktów i użytkowników. Po trzecie należy pamiętać, że uzyskawszy idealne dopasowanie na zbiorze uczącym czyli na znanych ocenach, które zapewnia obliczenie pełnego rozkładu SVD, możemy bardzo źle trafiać z rekomendacjami dla nowych, nieznanych, przypadków.

Zamiast dokładnego rozkładu macierzy używa się dekompozycji metodami uczenia maszynowego.  Tak samo jak przy obliczaniu SVD znajduje się kolejne wektory które wymnożone przez siebie dają przybliżenie macierzy. Nie liczy się tych wartości dokładnie, ale zmienia się wartości w wektorach odpowiadających danej obserwacji w kierunku spadku gradientu błędu tak aby z każdą kolejną obserwacją bardziej wartości dopasować do zbioru znanych obserwacji.

Metoda stochastycznego spadku wzdłuż gradientu

W swojej pracy magisterskiej zajmuję się właśnie przyrostową dekompozycją macierzy za pomocą stochastycznego spadku wzdłuż gradientu.  Jej algorytm polega na uczeniu się kolejnych cech, czyli wektora prezentującego wartość cechy dla każdego użytkownika oraz wektora z wartościami cechy filmów.  Każda cecha jest inicjowana małymi liczbami losowymi. Podczas kilkukrotnego przeglądania zbioru uczącego  odpowiednie wartości wektora cech użytkowników i wektora cech filmów są modyfikowane aby pomniejszyć błąd osiągany dla aktualnej obserwacji ze zbioru uczącego. W momencie gdy błąd na całym zbiorze przestaje się zmieniać rozpoczyna się uczenie następnej cechy. Warunek stopu dla uczenia się cechy będzie uzależniony od zmian błędu na zbiorze uczącym i wydzielonym z niego zbiorze weryfikującym. Powinno to przyczynić się do szybszego zakończenia uczenia, niż przy odgórnie ustalonej liczbie epok uczenia. Może to także polepszyć wyniki dla nieznanych przypadków.

Wydajność i eksperymenty

Zbiór na którym przeprowadzane są eksperymenty uczenia jest na tyle duży, że konieczne było zwrócenie uwagi na wydajność. Tak więc algorytm jest implementowany w c++, dane są wczytywane do tablicy i przeglądane kolejno. Sporym ograniczeniem jest brak łatwego sposobu zrównoleglenia obliczeń,  co bardzo przyspieszyłoby  pracę.

Do tego momentu został zaimplementowany algorytm uczenia wraz z zabiegami mającymi na celu osiągnięcie szybszego zbiegnięcia błędu (tak zwaną regularyzacją). Został on jednak przetestowany  dopiero na jednej szóstej oryginalnego zbioru danych. Wynika to z faktu, że przeprowadzanie eksperymentów jest bardzo czasochłonne, co utrudnia prace.

Warto zauważyć, ze na jednej szóstej danych osiąga on rezultaty podobne do najlepszych z konkursu Netflix Prize. Nie wiadomo jakie rezultaty osiągnie on na pełnych danych i na pełnym zbiorze testowym. Mogą być one znacznie gorsze. Jest tak ponieważ używany wycinek zbioru treningowego jest zbiorem bardzo przychylnym dla algorytmu, zawiera najczęściej występujące filmy i użytkowników. Pojawienie się innych, rzadziej występujących,  z pewnością przyczyni się do zwiększenia średniego błędu predykcji.

Kolejnymi krokami będzie przetestowanie algorytmu na pełnym zbiorze. Jednak z uwagi na rozmiar danych aby uniknąć nieudanych prób uczenia na małym zbiorze, wpierw na podzbiorze zostanie oszacowana dobra konfiguracja algorytmu i ona zostanie zastosowana na dużych danych.

Inne zastosowania SVD

Rozkład według wartości osobliwych znajduje zastosowania w wielu miejscach, nie tylko przy rekomendacji.  Kilkoma z wielu dziedzin gdzie się pojawia są wyszukiwarki tekstowe (uogólnianie słów w pojęcia, upraszczanie modelu), kompresja obrazu czy wizualizacja danych wielowymiarowych.

Źródła

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.178.598&rep=rep1&type=pdf

http://www2.research.att.com/~volinsky/papers/ieeecomputer.pdf

http://www.netflixprize.com/

Kalina Jasinska

Yehuda Koren, Robert Bell, & Chris Volinsky (2009). Matrix Factorization Techniques for Recommender Systems Computer DOI: 10.1109/MC.2009.263

Listopad 11, 2013

Wykorzystanie Dbpedii Spotlight w pracy z danymi publicznymi

- autor: tsissput

Dominik Filipiak, 94419

Jak powszechnie wiadomo, w internecie można znaleźć wszelakie dane na rozmaite tematy. Ich katalogowanie jest obecnie niezwykle popularnym trendem, co generuje serwisy zbierające takie dane, a nawet kompleksowe rozwiązania takie jak CKAN [1]. Wykonano także wiele pracy, aby sklasyfikować takie dane. Przetwarzanie wejściowych danych na postać trójek RDF-owych to jeden z możliwych kierunków. Przyjrzyjmy się teraz jak w nadawaniu znaczeń może przydać nam się niezwykle ciekawy projekt, jakim jest DBpedia Spotlight. Wykorzystamy wcześniej wymienione technologie do transformacji plików CSV na RDF wzbogacanych o własności i ich wartości pobieranych jako zasoby z DBpedii.

DBpedia jest efektem próby usystematyzowania danych zebranych na Wikipedii. Poprzez ekstrakcję strukturalna crawler pobiera dane na temat każdego artykułu. Część informacji na Wikipedii jest usystematyzowana – specjalne pola, tzw. infoboksy da się łatwo mapować na RDF-owe trójki.

Screenshot 2013-11-10 18.25.25

Tak przetworzony artykuł trafia na DBpedię w postaci trójek:

Screenshot 2013-11-10 18.26.31

Projekt DBpedia spotlight dostarcza narzędzie pozwalające wyszukiwać w tekście zasobów znajdujących się na DBpedii. Narzędzie może być wykorzystane również do znajdowania kategorii odpowiadających zadanemu zbiorowi pojęć, co stanowi użyteczne narzędzie w temacie, którym dziś się zajmujemy. Pod adresem http://dbpedia-spotlight.github.io/demo/ znajduje się interaktywne demo możliwości tego systemu. Dla programisty kluczową funkcją jest jednak to, że zostało udostępnione publiczne wygodne REST-owe API służące do operowania na Spotlighcie. Serwisy oparte na wcześniej wspomnianym systemie CKAN służą do gromadzenia dużych zbiorów danych publicznych. Dzięki systemowi grupowania, tagów oraz linkowaniu zasobów w różnych formatach do zbiorów danych możliwe jest szybkie wydobywanie interesujących nas informacji. Programiści z pewnością docenią API, które pozwala w wygodny sposób operować na zgromadzonych zasobach. Część z danych udostępniona jest już w postaci RDF-owych trójek, część jako arkusze XLS, inne natomiast są zamieszczone jako proste pliki CSV.

Spróbujemy użyć projektu Spotlight przy przetwarzaniu plików z CSV. Przy wykorzystaniu API, odpytamy system o wszystkie zbiory związane z danymi w Wielkiej Brytanii:

http://publicdata.eu/api/search/dataset?q=tags:uk&all_fields=1

Otrzymamy listę wszystkich zbiorów związanych z Wielką Brytanią w formacie JSON. To, co nas interesuje to przede wszystkim zawarte tam linki do zasobów. Warto zauważyć, że pole res_format mówi nam o formacie zasobów. Tak więc po przefiltrowaniu odpowiedzi tak, żeby uzyskać tylko zasoby w formacie CSV otrzymamy zbiór linków z plikami do pobrania. Po ściągnięciu tych zbiorów możemy wykorzystać API projektu Spotlight do próby nadania polom znaczeń. Jak wiadomo, plik CSV to nic innego jak zwykły plik tekstowy, gdzie poszczególne rekordy oddzielone są przecinkami, a każdy wiersz wypisany jest w osobnej linii. Dodatkowo, jeżeli rekord zawiera znaki specjalne, to jest on ujęty w cudzysłów. Pierwsza linia zazwyczaj zawiera nagłówki kolumn, a pierwsze rekordy w kolejnych liniach to opcjonalne nagłówki wierszy. Załóżmy, że przy pracy z wybranym plikiem wiersz odpowiedzialny za nagłówki zawiera trzy kolumny: Poland, Great Britain oraz USA. Aby otrzymać linki do zasobów, należy zadać odpowiednie zapytanie:

http://spotlight.dbpedia.org/rest/annotate/?text=Poland+Great+Britain+USA

Spotlight rozpozna w zapytaniu trzy kraje. Teraz, mając wskaźniki na reprezentacje RDF-ową, można spróbować podjąć się klasyfikacji tych pojęć. W odpowiedzi na zapytanie otrzymujemy również zbiór typów przypisanych do wskazanego pojęcia. I tak, dla naszego przykładowego zapytania (dla słowa „Poland”), otrzymamy:

Screenshot 2013-11-10 19.04.32

Jak widać termin został słusznie rozpoznany jako kraj. Analogicznie jest dla pozostałych pojęć. Dzięki temu można np. spróbować oznaczyć kategorię nadrzędną w tabeli jako kraje, lub po prostu użyć tego wyniku przy transformacji tabel na format RDF. Wyszukiwanie zasobów tekście jest jednak niezwykle czasochłonne, co trzeba mieć na uwadze przy pracy z tak dużymi zbiorami jak wcześnie wspomniane publicdata.eu. Dlatego też istotne jest wybranie z wejściowego pliku tylko istotnych dla nas informacji. Człowiekowi łatwo jest ocenić co jest nagłówkiem, a co polem z danymi w pliku CSV. Aby zmaksymalizować szybkość automatycznego przetwarzania tych plików, należy napisać coś na kształt prostej heurystyki.

W artykule [3] podjęto się próby sprowadzenia tabeli w formacie CSV do postaci kanonicznego modelu. Wypunktowano też wiele związanych z tym problemów. Warto jednak zauważyć, że tamtejsze podejście nie zakłada występowania nagłówków wierszy, co generuje dodatkowe problemy. Najbardziej intuicyjną metodą przy wybieraniu pojęć jest odrzucenie pól z danymi – zazwyczaj są to liczby. Dlatego pierwszym krokiem jest określenie „wysokości” nagłówków kolumn oraz „szerokości” pół określających nagłówki wierszy. Niestety nie jest to zadanie proste, gdyż nie można zawsze założyć, że w polu na dane znajdować się będą tylko liczby. Czasem może być to tekst (np. „Not available”), lub też puste pole. Część kolumn może zawierać w sobie inne, co ma graficznie reprezentować relację podrzędności. Oczywiście jest to też aplikowane dla wierszy. Przy liniowym przetwarzaniu plików może to generować problemy związane z rozpoznawaniem wielkości, gdy np. kolumna „Kraj” będzie rozgałęziać się na „Polska” oraz „Anglia” – jak łatwo sobie wyobrazić, „Kraj” będzie miał szerokość równą 2, ale będzie zajmował tylko jedno pole, drugie natomiast będzie puste. Są to jednak problemy na poziomie implementacji rozwiązania programistycznego i jedynym ich odbiciem na całość jest zdecydowane spowolnienie działania. Wykorzystując prosty program do implementacji powyższego rozwiązania, spróbujmy teraz przetworzyć plik z danymi dotyczącymi straży pożarnej mieszczącej się w Londynie.

Screenshot 2013-11-10 19.27.39

Kolumny zostaną zmapowane na:

http://dbpedia.org/resource/Code

http://dbpedia.org/resource/Area

http://dbpedia.org/resource/Emergency

(…)

Natomiast wiersze zostaną zmapowane na:

http://dbpedia.org/resource/City_of_London

http://dbpedia.org/resource/London_Borough_of_Barking_and_Dagenham

http://dbpedia.org/resource/London_Borough_of_Barnet

http://dbpedia.org/resource/London_Borough_of_Bexley

http://dbpedia.org/resource/London_Borough_of_Brent

(…)

Dysponując takimi danymi mapowanie do postaci trójek jest znacznie prostsze i efektywniejsze, gdyż nie musimy tworzyć zasobów reprezentujących dzielnice Londynu, a możemy wykorzystać te już istniejące. Z taką reprezentacją wystarczy tylko odpytać Dbpedię o właściwości danego zasobu (np. poprzez zapytanie w języku SPARQL poprzez framework Apache Jena). Poniżej przykład zasobu w formacie .ttl:

<http:/cs.put.poznan.pl/data/fire_brigade#1>

rdf:type yago:LondonBoroughs ;

dbpprop:shortName „Camden”;

(…)

dbpprop:url „http://www.camden.gov.uk/”.

Spotlight nie jest oczywiście narzędziem doskonałym. Jest znane wiele przypadków, gdzie trudno jednoznacznie nadać znaczenie dla danego słowa. Dla przykładu, termin „Jaguar” można oznaczać znanego producenta samochodów, jak i również zwierze z rodziny kotowatych. Dlatego tak ważne jest rozpoznanie wg kontekstu. Struktura typów zbioru pojęć nie jest niestety drzewiasta, stanowi ona tzw. „siatkę”. Dobór algorytmu próbującego uogólnić taką strukturę jest kluczowy i stanowi obszerny temat na kolejny artykuł. Może zdarzyć się też tak, że program źle wywnioskuje z kontekstu nasze pojęcie. Dla przykładu, kiedy mówimy o krajach, z termem „Germany” związany jest zasób „West Germany”. Intuicyjnie wiemy, że znacznie trafniejszym wyborem byłby link kierujący nas do obecnych Niemiec, jednak dla analizatora nie jest to takie oczywiste. W prezentowanym podejściu zajęliśmy się zasobami w języku angielskim, ponieważ niestety nie jest jeszcze dostępna wersja projektu Spotlight przeznaczona do pracy z polskim językiem. Warto jednak śledzić temat, gdyż w przyszłości może to być niezwykle przydatny oręż w przetwarzaniu polskojęzycznych danych publicznych.

[1] http://ckan.org/

[2] https://github.com/dbpedia-spotlight/dbpedia-spotlight/wiki

[3] http://svn.aksw.org/papers/2013/ISemantics_CSV2RDF/public.pdf

 

Listopad 10, 2013

k-hop reachability – opis problemu i analiza rozwiązania

- autor: tsissput
Opracował: Przemysław Grzędzielski 

1 Wstęp

Celem niniejszego wpisu jest przybliżenie czytelnikom problemu k-hop reachability, mającego duże znaczenie w szeregu dziedzin, które można zamodelować przy pomocy sieci (w szczególności w sieciach społecznościowych) oraz analiza rozwiązania tego problemu, zaproponowanego w artykule „K-Reach: Who is in Your Small World”.

 2 Opis problemu i jego znaczenie

 2.1 Sformułowanie problemu

 Dane wejściowe

Niech s (source) i t (target) oznaczają dwa wierchołki w grafie, modelującym sieć. Niech k jest pewną dodatnią liczbą całkowitą.

 Problem

Czy z wierzchołka s da się dojść do wierzchołka t w co najwyżej k krokach? Innymi słowy, czy istnieje ścieżka w grafie skierowanym od wierzchołka s do wierzchołka t o długości co nawyżej k?

 Dane wyjściowe

Jest to problem decyzyjny, więc wynikiem jest odpowiedź TAK lub NIE na postawione pytanie.

 2.2 Związki z innymi problemami grafowymi

Zauważmy, że klasyczny problem osiągalności wierzchołków, polegający na udzieleniu odpowiedzi na pytanie: czy wierzchołek t jest osiągalny z wierzchołka s (czyli, przykładowo – czy Jaś jest w jakiś sposób powiązany z Małgosią?), jest przypadkiem szczególnym przedstawionego problemu, w którym parametr k wynosi nieskończoność.

 2.3 Znaczenie w kontekście sieci społecznościowych

Nietrudno wyobrazić sobie, że problem ten ma potencjalnie duże znaczenie w kontekście sieci społecznościowych. Nierzadko bowiem nie wystarcza nam wiedza o tym, czy dwie osoby są ze sobią powiązane w ogóle (jak zauważają autorzy artykułu – dowolne dwie osoby najprawdopodobniej są w jakiś sposób ze sobą powiązane, biorąc pod uwagę słynne “twierdzenie” o six degrees of separation). Znacznie bardziej przydatna może okazać się wiedza o tym, czy dane dwie osoby są od siebie oddalone o pewną liczbę k, szczególnie w przypadku małych k.

Przykładowo: chcemy, aby szczegółowość informacji o profilu osoby A w portalu społecznościowym widziana przez osobę B zależała od tego, jak “blisko” w grafie znajdują się te osoby. Np. użytkownik A ustawił widoczność swoich danych teleadresowych w taki sposób, aby mieli do nich dostęp znajomi co najwyżej trzeciego stopnia. Kiedy użytkownik B wyświetla profil użytkownika A, potrzebujmy odpowiedzi na pytanie, czy użytkownik B jest “oddalony” od użytkownika A o nie więcej niż trzy.

 3 Przykładowe podejścia, ich wady i zalety

 3.1 Problem z Lady Gagą

Autorzy artykułu “K-Reach: Who is in Your Small World” dokonują istotnego spostrzeżenia: fakt, że wartość k jest mała (mniejsza od 6, bo takie instancje mają sens w kontekście rzeczonych six degrees) nie czyni problemu łatwiejszym. Wydawać by się mogło, że w takim wypadku sprawdziłoby się rozwiązanie naiwne, polegające na przejściu grafu wszerz (Breadth First Search) i sprawdzeniu, czy docelowa osoba zostanie napotkana w odległości nie większej niż k od wierzchołka początkowego. Problemem, który wskazują autorzy, jest obecność tzw. celebrities, czyli osób bardzo popularnych w całej sieci. Twierdzą oni, że w przypadku większości rzeczywistych zapytań na pewnym etapie przeszukiwania grafu napotkamy na celebrytę (nie przepadam za tym neologizmem…), który “zaprowadzi” nas do tak wielkiej liczby wierzchołków, że dalsze przeszukiwanie sieci stanie się zadaniem karkołomnym (przykład: Lady Gaga, która w chwili powstawania niniejszego wpisu ma 60 411 323 fanów na Facebooku – wyobraźmy sobie tę zajętość pamięciową!).

 3.2 DAG – Dlaczego Acykliczny Graf … ?!

Kolejne przytoczone przez autorów podejście opiera się na założeniu, że graf sieciowy jest acyklicznym grafem skierowanym (ang. Directed Acyclic Graph). W przypadku, kiedy tak nie jest (czyli – w rzeczywistości – praktycznie zawsze) zostaje on zredukowany do DAGa poprzez zastąpienie wszystkich silnie spójnych składowych (ang. strongly connected components) pojedynczymi wierzchołkami. Podejście to redukuje zajętość pamięciową i sprawdza się w przypadku pytania, czy połączenie między dwoma wierzchołkami w ogóle istnieje (wiadomo, że jeśli dojdziemy do wierzchołka zastępującego składową silnie spójną, to dojdziemy także do każdego z rzeczywistych wierzchołków ją tworzących). Zawodzi jednakże w przypadku rozważanego problemu k-reachability, ponieważ – jak nietrudno zauważyć – para wierzchołków “osiągalnych” nie musi być “k-osiągalna” (jeśli mogę pokusić się o spolszczenie nazwy naszego problemu).

Do powyższych spostrzeżeń dorzuciłbym jeszcze jedno, zasadnicze – w praktyce sieć społecznościową rzadko możemy w ogóle zamodelować w postaci grafu skierowanego, najczęściej bowiem “znajomość” między dwoma osobami jest relacją symetryczną, czyż nie?

 3.3 Najkrótsze ścieżki

Innym rozważanym podejściem jest stosowanie indeksów przeznaczonych do przetwarzania zapytań o najkrótsze ścieżki pomiędzy wierzchołkami w grafie. Użycie takiego indeksu, który danego wierzchołka s powie nam szybko (czyt. O(1)), jaka jest jego odległość od wierzchołka t, byłoby trywialne. Problemy, które wskazują autorzy, jest koszt przetwarzania zapytań o odległości między wierzchołkami oraz fakt, że indeksy takie przeważnie są tworzone dla grafów nieskierowanych.

Moim zdaniem, podstawowym mankamentem, który należałoby tutaj podkreślić, jest duża zajętość pamięciowa takiego indeksu oraz złożoność samego procesu tworzenia. Stworzenie macierzy najkrótszych odległości między wierzchołkami wymaga bowiem po prostu przejścia grafu w kolejności BFS (jeśli łuki mają jednakowe wagi, oczywiście). Jeśli natomiast łuki mają różne wagi, najkrótsze odległości między wierzchołkami na niewiele nam się przydadzą.

 4 Algorytm k-Reach

 4.1 Pokrycie wierzchołkowe

Zaproponowany algorytm konstruuje indeks, który pozwala na sprawdzenie, czy dane dwa wierzchołki leżą w odległości co najwyżej k. Do stworzenia indeksu wykorzystywane jest tzw. pokrycie wierzchołkowe grafu:

Pokrycie wierzchołkowe to taki podzbiór wierzchołków grafu G(V,E), że dowolna krawędź w tym grafie jest incydentna z co najmniej jednym wierzchołkiem tego podzbioru

Minimalne pokrycie wierzchołkowe to najmniejszy możliwy podzbiór wierzchołków grafu, który jest jego pokryciem wierzchołkowym

Problem znalezienia minimalnego pokrycia wierzchołkowego grafu jest NP-trudny. Istnieje jednak algorytm, który znajduje jego przybliżenie w czasie wielomianowym: 2-approximate minimum vertex cover.

Jego przebieg jest następujący (E oznacza zbiór krawędzi w grafie G, V zbiór wierzchołków w grafie G, S jest wynikowym zbiorem):

 S = <empty set>()
while (E is not empty){
(u,v) = randomly_select_edge_from_E
// add u and v to result set
S += u
S += v
// remove every edge that is incident to u or v
for every e : (e incident to u or v) {
E -= e
}
// remove u and v from the vertices
V -= u
V-=v
}
// S is the result
return S

Zauważmy, że dla każdej krawędzi (u,v), którą dodajemy do zbioru S, co najmniej jeden z pary wierzchołków musi należeć do minimalnego pokrycia wierzchołkowego (oznaczmy je jako C). W przeciwnym razie C nie spełniałoby definicji pokrycia wierzchołkowego (tzn. krawędź (u,v) nie byłaby incydentna z żadnym z wierzchołków należących do C). O skonstruowanym oszacowaniu możemy więc powiedzieć, że jego liczność jest co najwyżej dwa razy większa od liczności minimalnego pokrycia wierzchołkowego: |S| <=2*|C|.

 4.2 indeks k-Reach

Indeks k-Reach zakłada, że dane są:

• graf G(V,E)

• S – pokrycie wierzchołkowe grafu G

• parametr k

Indeks jest grafem I=(V_i, E_i, w_i) zdefiniowanym następująco:

• V_i = S

• E_i jest zbiorem krawędzi (u,v) należących do S takich, że v jest k-osiągalny z u (isReachable(u,v,k) == true)

• w_i to funkcja wagowa, która każdej krawędzi e=(u,v) ze zbioru E_i przyporządkowuje wagę (zauważmy, że isReachable(u,v,k-2) impikuje, że isReachable(u,v,k-1), co z kolei implikuje isReachable(u,v,k):

 – if (isReachable(u,v,k-2)) { w_i(e) = k-2;}
 – else if (isReachable(u,v,k-1)) { w_i(e) = k-1; }
 – else if (isReachable(u,v,k)) { w_i(e) = k;}

Procedura konstrukcji indeksu k-Reach jest następująca: dla każdego wierzchołka u w pokryciu S wyznaczamy zbiór S_k(u), zawierający wierzchołki znajdujące się w odległości nie większej niż k od niego, wykonując przejście BFS po grafie G). Pseudokod znajduje się poniżej:

S = 2-approximate_vertex_cover(G)
V_i = S
for each u in S {
S_k(u) = BFS(graph=G,upper_bound=k)
for each v in S_k(u) {
E_i += (u,v)
compute weight w_i for (u,v)
}
}
return I=(V_i,E_i,w_i)

 4.3 Przetwarzanie zapytań przy użyciu indeksu k-Reach

Zakładając, że dla danego parametru k skonstruowano indeks k-Reach (a także, uprzednio, pokrycie wierzchołkowe S), odpowiedź na pytanie: czy wierzchołek t jest oddalony od wierzchołka s o co najwyżej k, jest stosunkowo prosta. Istotne jest spostrzeżenie, że możemy tu mieć do czynienia z czterema przypadkami. Logika algorytmu jest prosta:

 Przypadek 1: s i t należą do S

Najprostszy przypadek. Jeśli zarówno s i t należą do pokrycia wierzchołkowego S, to isReachable(u,v,k) zachodzi wtedy i tylko wtedy, gdy krawędź (s,t) znajduje się w zbiorze krawędzi E_i naszego indeksu.

 Przypadek 2: s należy do S, t nie należy do S

Skoro t nie należy do pokrycia wierzchołkowego S, to wiadomo, że wszystkie jego poprzedniki należą do S (wynika to z definicji pokrycia wierzchołkowego). Wiadomo też, że jeden z tych poprzedników (o ile takie w ogóle istnieją) musi być (k-1)-osiągalny z wierzchołka s (wówczas docelowe t będzie k-osiągalne z wierzchołka s).

Przypadek 3: s nie należy do S, t należy do S

Sytuacja analogiczna do powyższej. Skoro s nie należy do pokrycia wierzchołkowego S, to wiadomo, że wszystkie jego następniki muszą należeć do S. Wiadomo też, że z co najmniej jednego z tych następników wierzchołek docelowy t jest (k-1)-osiągalny (wówczas jest on k-osiągalny z początkowego s).

 Przypadek 4: s, t nie należą do S

Rozumowanie podobne jak poprzednio. Wiemy, że wszystkie następniki s oraz wszystkie poprzedniki t należą do S. Sprawdzamy więc, czy istnieje taka para (u,v), że u jest następnikiem s, v jest poprzednikiem t oraz zachodzi isReachable(u,v,k-2). Jeśli taka para istnieje, to wiemy, że t jest osiągalny z s.

 4.4 Analiza złożoności

Warto zwrócić uwagę na złożoności obliczeniowe poszczególnych kroków prezentowanego algorytmu. Muszę przyznać, że wyjaśnienia podane przez autorów (dotyczy to w szczególności kroku nr 2) wydają mi się niekompletne, a co za tym idzie – niezrozumiałe.

 4.4.1 Tworzenie indeksu k-Reach

• Wyznaczanie pokrycia wierzchołkowego S: O(m+n)

• Tworzenie skierowanego, ważonego grafu I=(V_i, E_i, w_i): całkowita liczba wykonywanych kroków jest równa sumie kroków wymaganych do stworzenia zbiorów S_k dla każdego wierzchołka u (czyli zbiorów wierzchołków k-osiągalnych z u) – pamiętajmy, że w tym celu przechodzimy graf w porządku BFS dla każdego wierzchołka u (z maksymalnym zasięgiem k)

 4.4.2 Przetwarzanie zapytania dla danych s,t

Niech inDegree(u,G) i outDegree(u,G) oznaczają, odpowiednio, stopień wejściowy i stopień wyjściowy wierzchołka u w grafie G.

• Sprawdzenie, czy wierzchołek należy do V_i: O( 1 )

• Sprawdzenie, czy krawędź (u,v) należy do E_i i odczytanie jej wagi: O( log outDegree(u,I) ) lub O( log inDegree(v,I) ) przy założeniu, że graf jest przechowywany w formie listy sąsiedztwa (ang. adjacency list)

Na tej podstawie autorzy podają następujące złożoności przetwarzania poszczególnych przypadków zapytań wyróżnionych w algorytmie:

• Przypadek 1: O( log outDegree(s,I) )

• Przypadek 2: O( outDegree(s,I)+inDegree(t,G) )

• Przypadek 3: O( outDegree(s,G)+inDegree(t,I) )

• Przypadek 4: O(  sum_by_u_in_outNeighbours(s,G): (outDegree(u,I)+inDegree(t,G)) )

Uważam, że analizie złośoności obliczeniowej należałoby w artykule poświęcić nieco więcej miejsca. Co o nich sądzicie?

 5 Bibliografia

K-Reach: Who is in Your Small World”, 1 VIII 2012; James Cheng, Zechao Shang, Hong Cheng, Haixun Wang, Jeffrey X. Yu

Listopad 10, 2013

Wprowadzenie do Linked Data

- autor: tsissput

Wstęp

Sieć WWW (World Wide Web) radykalnie zmieniła nasz sposób dzielenia się wiedzą poprzez obniżenie bariery w publikowaniu i dostępie do dokumentów w ramach globalnej przestrzeni informacji. Przeglądarki i linki hipertekstowe pozwalają użytkownikom na przeglądanie tej przestrzeni, a indeksowanie dokumentów i analiza struktur powiązań między nimi na wnioskowanie na temat potencjalnego znaczenia dla zapytania zadanego przez użytkownika. Jest to możliwe przez ogólny, otwarty i elastyczny charakter sieci, który jest postrzegany jako kluczowy element nieograniczonego wzrostu. Tradycyjnie dane publikowane w sieci były dostępne jako surowe wpisy w formatach CSV, XML lub oznaczone jako tabele HTML tracąc wiele z ich struktury oraz znaczenia. Konwencja hipertekstowych powiązań narzuca niejawny charakter relacji między powiązanymi dokumentami. Taki stan rzeczy uniemożliwia połączenie poszczególnych danych z określonego dokumentu z innymi powiązanymi danymi.

W ostatnich latach sieć ewoluowała z globalnej przestrzeni informacji powiązanych dokumentów w przestrzeń gdzie powiązane są zarówno dokumenty jak i dane. U podstaw tej ewolucji znalazł się zestaw najlepszych praktyk, w zakresie publikowania i łączenia danych strukturalnych, nazywany Linked Data. Zaadaptowanie zestawu najlepszych praktyk doprowadziło do rozszerzenia globalnej sieci połączonych danych o różne dziedziny, takie jak społeczeństwo, firmy, książki, publikacje naukowe, filmy, muzyka, programy telewizyjne i radiowe, genetyka, lekarstwa i próby medyczne, społeczności internetowe, statystyka i dane naukowe, opinie.

Ta sieć danych umożliwia powstanie nowego typu aplikacji. Istnieją ogólne przeglądarki powiązanych danych, które umożliwiają ich przeglądanie i nawigowanie pomiędzy źródłami wzdłuż połączeń między danymi. Są to mechanizmy przemierzające sieć powiązanych danych między różnymi źródłami umożliwiając wykonywanie ekspresyjnych zapytań o szerokich możliwościach na zagregowanych danych, podobnie jak dziś odbywa się to w lokalnych bazach danych. Sieć powiązanych danych otwiera też nowe możliwości dla aplikacji specjalizowanych. W przeciwieństwie do rozwiązań typu mashup 2.0 działających na stałym, określonym zbiorze źródeł aplikacje oparte na Linked Data działają na samej górze globalnej przestrzeni danych, co umożliwia dostarczenie wyczerpujących odpowiedzi.

Co to jest Linked Data?

graphSą to najlepsze praktyki na temat tworzenia w sieci powiązań pomiędzy danymi pochodzącymi z różnych źródeł. Dane mogą być tak różne jak bazy danych prowadzonych przez dwie organizacje w różnych lokalizacjach geograficznych lub systemy heterogeniczne w obrębie pewnej firmy, które trudno dopasować aby współpracowały na poziome danych. Technicznie Linked Data odnosi się do danych opublikowanych w sieci w taki sposób, że są one możliwe do odczytywania przez maszyny, a ich znaczenie jest wyraźnie określone, są związane z innym zewnętrznym zbiorem danych, a ten z kolei może być powiązany z kolejnym zewnętrznym źródłem.

Chociaż podstawową jednostką w sieci są dokumenty HTML połączone bez typowymi łączami, Linked Data opiera się na dokumentach zawierających dane w formacie RDF (Resource Description Framework), które przy pomocy wyrażeń łączą dowolne byty na świecie. Wynikiem tego jest nazywana przez nas sieć danych, którą można dokładnie określić jako sieć bytów na świecie opisanych przez dane w sieci.

Berners-Lee w 2006 roku przedstawił zestaw zasad publikowania danych w sieci w taki sposób, że wszystkie publikowane dane stają się częścią jednej globalnej przestrzeni danych:

  • Użyj URI jako nazwa bytu
  • Użyj http URI tak aby ludzie mogli wyszukać nazwy bytu
  • Gdy ktoś wyszukuje URI dostarcz użyteczne informacje przy pomocy standardów (RDF, SPARQL)
  • Zamieszczaj powiązania do innych URI tak aby można było znaleźć więcej informacji

Reguł te stały się znane jako ‚Linked Data principles’ i zapewniają podstawę dla publikowania i łączenia danych wykorzystując strukturę sieci Web zachowując jej architekturę i standardy.

Technologie wykorzystywane w Linked Data

Linked Data opiera się na dwóch technologiach, które są podstawą sieci WWW: URI (Uniform Resource Identifiers) i HTTP (HyperText Transfer Protocol). Chociaż URL (Uniform Resource Locator) stał się znany jako adres dokumentów i innych jednostek, które mogą znajdować się w sieci to URI zapewnia bardziej ogólny sposób rozpoznawania bytów, które istnieją na świecie. URI i HTTP są uzupełniającymi się technologiami i mają kluczowe znaczenie dla sieci danych – RDF. Podczas gdy HTTP zapewnia środki do konstrukcji i powiązania dokumentów w sieci WWW, RDF zapewnia ogólny, grafowy, oparty na danych model do konstrukcji i powiązania bytów opisujących rzeczywistość.

rdf_w3c_icon.128

Dla przykładu trójka RDF może stwierdzać, że dwie osoby A i B, każda identyfikowana przez URI, związane są faktem, że A zna B. Podobnie trójka RDF może wiązać osobę C z artykułem naukowym D w bibliograficznej bazie danych, stwierdzając, że C jest autorem D. Dwa zasoby powiązane w ten sposób można wyciągnąć z dwóch różnych zbiorów danych w sieci, dzięki czemu dane z jednego źródła są powiązane z danymi z innego źródła, tworząc w ten sposób sieć danych. W ten sposób możliwe jest, że trójka RDF łączy dwa różne zbiory danych analogicznie jak link łączy dokumenty w sieci Web.

RDF Vocabulary Definition Language (RDFS) i Web Ontology Language (OWL) stanowią podstawę do tworzenia słowników, które mogą być używane do opisania bytów występujących w rzeczywistości i opisu związków występujących między nimi. Słownictwo jest zbiorem klas i właściwości. Słowniki same są wyrażone za pomocą RDF, używając RDFS i OWL, które zapewniają różne stopnie ekspresyjności w modelowaniu domeny zainteresowania. Każdy może opublikować słownik w sieci danych, które z kolei mogą być powiązane przy mocy trójek RDF w taki sposób, że klasy i własności z jednego słownika są powiązane z innymi, wyrażają w ten sposób mapowania pomiędzy powiązanymi słownikami.

Przez zastosowanie URI do określania zasobów, HTTP jako mechanizmu wyszukiwania i RDF jako reprezentacja opisu zasobów, Linked Data bezpośrednio opiera się na ogólnej architekturze sieci Web. Sieć danych może więc być postrzegana jako dodatkowa warstwa, która ściśle przeplata się z klasyczną siecią dokumentów i ma wiele tych samych właściwości:

  • Sieć danych jest ogólna i może zawierać dane dowolnego typu.
  • Każdy może publikować dane.
  • Wydawcy danych nie są ograniczeni w wyborze słowników do opisu reprezentacji danych.
  • Byty są połączone przez RDF tworząc globalny graf danych, który obejmuje źródła danych i pozwala na odkrywanie nowych źródeł danych.

Z punktu tworzenia aplikacji sieć danych ma następujące cechy:

  • Dane są ściśle oddzielone od formatowania i graficznej reprezentacji.
  • Dane są samo opisujące. Jeśli aplikacja wykorzystująca Linked Data napotka na dane opisane nieznanym słownictwem aplikacja może odwołać się do URI, które identyfikują wykorzystane słownictwo w celu znalezienia ich definicji.
  • Zastosowanie HTTP jako standardowego mechanizmu dostępu do danych i RDF jako standardowego modelu danych upraszcza dostęp do danych w stosunku do sieci Web, która opiera się na różnorodnych modelach danych i interfejsach dostępowych.
  • Sieć danych jest otwarta, co oznacza, że aplikacje nie muszą nie muszą mieć ściśle określonego zestawu źródeł danych ale w czasie wykonywania programu można odkrywać nowe źródła danych za pomocą powiązań RDF.

Podsumowanie

Rozwinięcie globalnej sieci danych opartej na technologiach podstawowych dla obecnej sieci WWW oraz otwartość tego rozwiązania ułatwia wprowadzenie Linked Data w życie. Nowe aplikacje bazujące na tej technologii mogą korzystać z niezliczonej ilości źródeł danych, które to nie muszą być definiowane w trakcje wytwarzania oprogramowania. Zastosowana przez Linked Data reprezentacja danych umożliwia bezpośrednie ich przetwarzanie przez maszyny. Możliwe staje się nawigowanie wzdłuż połączeń między danymi, niezależnie od źródeł ich pochodzenia. Linked Data może okazać się rewolucyjnym rozwiązaniem propagującym Semantic Web i przyspieszającym ewolucję Web 2.0 do Web 3.0.

Christian Bizer, Tom Heath, & Tim Berners-Lee (2009). Linked Data – The story so far International Journal on Semantic Web and Information Systems DOI: 10.4018/jswis.2009081901

Autor: Łukasz Grzybowski