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

Luty 22, 2013

Semantyczny rejestr usług sieciowych

- autor: tsissput

Cel projektu

Pomysł na semantyczny opis i wyszukiwanie usług sieciowych nie jest nowy, ale jak dotąd nie powstało rozwiązanie, które spotkałoby się z powszechną akceptacją.  Powodów takiego stanu rzeczy należy upatrywać przede wszystkim w skomplikowanym i trudnym w opisie modelu Big Web Services opartym na protokole SOAP. Sprowadza się on w zasadzie do zdalnego wywoływania metod za pośrednictwem rozbuchanego, nadmiarowego i pod wieloma względami dublującego funkcjonalność protokołów transportowych (np. HTTP) formatu XML, co wiąże się z nieograniczoną dowolnością wykonywanych operacji.  Każda próba wzbogacenia takich usług o informację semantyczną wymaga zarówno dodatkowego powiększenia i tak już „ciężkiej” koperty SOAPowej, jak też bardzo indywidualnego podejścia do semantycznego opisu każdej usługi z osobna.

W związku z powyższym, zdecydowaliśmy się ograniczyć zakres projektu do usług zgodnych z paradygmatem REST. Pozwala to na wprowadzenie swojego rodzaju „wspólnego mianownika” dla opisywanych usług, który wynika ze ściśle określonego związku architektury usług z wykorzystanym protokołem transportowym (praktycznie zawsze HTTP lub HTTPS). Ogromnym ułatwieniem jest tu porzucenie potencjalnie nieskończonej (w przypadku usług typu Big Web Services) przestrzeni możliwych operacji, na rzecz tej, którą tworzą metody protokołu HTTP. Ponadto, w przypadku usług RESTowych, mamy pewność, że zakres operacji jest jasno określony przez adres URL zasobu. Nie jest konieczne wnikanie w ciało żądania by określić na jakich danych wykonujemy jakąś czynność.

Należy wspomnieć, że sam paradygmat REST jest pojęciem o bardzo wysokim poziomie abstrakcji i sam w sobie nie definiuje żadnych szczegółów implementacji usług. W projekcie zakładamy zgodność usług z jego konkretną interpretacją opartą na protokole HTTP, a mianowicie z architekturą zorientowaną na zasoby (ang. Resource Oriented Architecture – ROA). Termin ten został zaproponowany przez Leonarda Richardsona i Sama Ruby’ego w książce Semantic Web Services (wyd. O’Reilly).

verbs

Kolejną rzeczą, na którą należy zwrócić uwagę jest fakt, że koncepcja globalnych rejestrów usług nie zyskała powszechnej aprobaty. Samo skłonienie setek niezależnych podmiotów do utrzymywania takich rejestrów jest zadaniem trudnym. Opracowując nasze rozwiązanie nie kierowaliśmy się ambicjami stworzenia takiego rejestru. Nasza aplikacja jest przeznaczona do użytku w zastosowaniach lokalnych, na skalę pojedynczych przedsiębiorstw czy systemów informatycznych

Semantyka

Ograniczenie się do opisu usług RESTowych pozwoliło na opracowanie stosunkowo nieskomplikowanej ontologii opisującej architekturę zorientowaną na zasoby. Do opisu każdej usługi potrzeba w ogólności trzech elementów:

  • Ontologii REST-HTTP opisującej pojęcia związane z ROA, takie jak: zasób, adres URL, nagłówek HTTP, ciało odpowiedzi, operacja tworzenia zasobu, metoda GET, etc.
  • Ontologii dziedzinowej opisującej biznesową interpretację zasobów. Pojęcia w niej zawarte to na przykład: pacjent, kolejka na badanie, wpis w karcie, grupa krwi, etc. Należy tu wspomnieć, że w ogólności każda usługa może być opisana przy pomocy dowolnej liczby ontologii dziedzinowych, które mogą być łączone w celu poszerzenia opisu semantycznego.
  • Ontologii opisującej konkretną usługę zawierającej przede wszystkim instancje klas zdefiniowanych w pozostałych ontologiach.

Pozwala to na elastyczne mapowanie udostępnianych przez usługi zasobów w kontekście ROA na abstrakcyjne zasoby opisane w ontologiach.

Zakłada się ponadto, że każdy złożony zasób (na przykład Lekarz) interpretowany jako instancja pewnej klasy z ontologii, składa się z pewnej liczby podzasobów atomowych o typach prostych reprezentowanych przy pomocy typowanych literałów.  Zarówno zasoby złożone, jak i atomowe, są wiązane w stosunku 1:1 z pojęciami z ontologii dziedzinowej.

Oto kilka przykładów zapytań w języku naturalnym, które można wyrazić przy pomocy opisanego powyżej zestawu ontologii:

  • Znajdź usługę, która umożliwia pobranie kolekcji pacjentów leczonych na zapalenie płuc bez podawania dodatkowych parametrów
  • Znajdź usługę, która pozwoli na utworzenie nowego zasobu oznaczającego pojęcie pacjent w kontekście kolejki na badanie rentgenowskie, przy założeniu że znam PESEL, imię i nazwisko pacjenta.
  • Dysponuję numerem książeczki ubezpieczeniowej pacjenta. Jakich jeszcze parametrów potrzebuję by wykonać zapytanie tworzące zasób reprezentujący tego pacjenta przy pomocy usługi X?

Implementacja rejestru

Oczywiście sama ontologia to za mało by wykorzystać takie zapytania w praktyce. Dokonaliśmy implementacji usługi RESTowej pozwalającej na wgrywanie ontologii i udostępniającej końcówkę SPARQL  wykorzystywaną do wykonywania zapytań do ontologii.

Wykorzystaliśmy w tym celu bibliotekę Apache Jena udostępniającą interfejsy do manipulacji danych semantycznych i ich przechowywania w bazie danych oraz silnik SPARQL. Interfejst REST usługi oparto na bibliotece Jersey implementującej standard JAX-RS. Widoki stworzono w technologii JSP.

semreg2

Plany na przyszłość

Opracowana aplikacja stwarza szereg interesujących możliwości. Dzięki semantycznemu opisowi publikowanych usług możliwe jest tworzenie klientów aplikacyjnych, które zamiast jawnie wywoływać konkretne usługi posiadać będą jedynie zdefiniowaną w sposób deklaratywny informację o tym jaką operację należy wykonać i na jakim zasobie. Dzięki wykorzystaniu rejestru, potrzebna będzie jedynie informacja o tym, na jakie pojęcie w dziedzinie biznesowej przekłada się dany zasób.

Łatwo sobie wyobrazić sytuację, w której klient pobiera listę dostępnych usług oraz wymaganych przez nie parametrów, a następnie odpytuje rejestr w celu znalezienia usług udostępniających dane, które są potrzebne jako parametry żądania. Jeszcze prostszym zadaniem jest kompozycja formularzy HTML pozwalających na wprowadzenie wymaganych przez usługi danych przez użytkownika. Potencjalnym klientem rejestru jest rozwijany na Politechnice Poznańskiej silnik procesów biznesowych ROsWeL (ang. Resource Oriented Workflow Language).

roswelLogoWidePlainBlack50pxhi

Korzystanie z rejestru zostałoby znacznie ułatwione gdyby opis usług w językach RDF i OWL był generowany w pewnym stopniu automatycznie. Można to zrealizować przy pomocy biblioteki opartej o mechanizm adnotacji w języku Java, w sposób podobny do tego, w jaki na podstawie adnotacji JAX-RS lub JAX-WS generowane są dokumenty WADL i WSDL. W gestii programisty usług pozostałoby wtedy tylko umieszczenie odpowiednich adnotacji semantycznych obok adnotacji JAX-RS definiujących parametry i typy obiektów zwracanych przez usługi.

Powyższe założenia zamierzamy zrealizować w ramach pracy magisterskiej.

Tomasz Niedźwiedź i Paweł Pawłowski

Luty 21, 2013

SignedNetworkGenerator

- autor: tsissput
  • Przemysław Wróblewski 89846
  • Marcin Wojdowski 89843

Program ma za zadanie generowanie sieci z wiązaniami ujemnymi i dodatnimi.

Program realizuje następujący scenariusz:

  1. Załadowanie danych konfiguracyjnych
  2. Pobranie z fabryki NetworkFactory2 głównego algorytmu przetwarzania, impl w pakiecie org.tsiss.sng.network.creators
  3. W zależności od głównego algorytmu przetwarzania klass wspierajacych przetwarzanie. Przykładowe wartości z pliku ApplicationContext:
    1.  ac.getProbability(); – zwraca model prawdopodobienstwa dla procesu tworzenia krawedzi wewnątrz grupy i na zewnątrz(osobne).
    2. ac.getGroupChooser(); – zwraca model wyboru grupy do przydziałów nowych elementów.
    3. ac.getExtNegativeEdge(); – zwraca model wyboru docelowego wierzchołka dla negatywnej zewnętrznej krawedzi
    4. ac.getExtPositiveEdge();- zwraca model wyboru docelowej grupy dla negatywnej zewnętrznej krawedzi
    5. ac.getNodeChooser();- zwraca model wyboru docelowego wierzchołka dla wybranej grupy
    6. ac.getAgeFunction();- zwraca funkcje postarzająca krawędzie.

Głównym plikiem konfiguracyjnym projektu jest plik sng.properties.

W środku znajdziemy następujące przykładowe parametry:

  • nodes=40 ­– ilośc węzłów
  • iterations=40000 – ilośc iteracji algorytmu
  • edges=220 – max ilość krawędzi
  • negative-edge=1 – możliwość tworzenia negatywnych krawedzi
  • bidirected=true – czy sieć jest skierowana
  • minimum-edge-weight=-5.0
  • maximum-edge-weight=5.0
  • output-file=d:\\sng\\sng.gdf – plik wyjsciowy
  • output-type=GDFFile – format wyjsciowy
  • groups=5 – ilość dostępnych grup
  • AgeFunction=LinearFunction – nazwa klasy użytej jako funkcja postarzania(pakiet: org.tsiss.sng.edge.age)
  • probability  = ParametrizedProbability – nazwa klasy użytej jako funkcji określającej możliwość powstania krawędzi (pakiet: org.tsiss.sng.probability.create.edge)
  1. — parametry specyficzne dla danej klasy
  2. ParametrizedProbability.createInternalEdgeProb=0.8
  3. ParametrizedProbability.createExternalEdgeProb=0.6
  4. ParametrizedProbability.isNegativeEdgeProb=0.5
  •  groupChooser=PopularPreference – nazwa klasy użytej jako funkcji wybierającej docelową grupę dla nowego obiektu (pakiet: org.tsiss.sng.probability.choose.group)
  •  nodeChooser  = NodeDegreePreference – nazwa klasy użytej jako funkcji wybierającej wierzchołek z podanego zbioru, np. Wybranej grupy (pakiet: org.tsiss.sng.probability.choose.node)
  1.  — parametry specyficzne dla danej klasy
  2. NodeDegreePreference.handicap = 2
  3. NodeDegreePreference.degreeWeight =1.5
  • externalNegativeEdge = GroupNegativePreferenceWithPositiveInfluence – nazwa klasy użytej jako funkcji wybierającej docelową grupę dla nowej negatywnej krawedzi (pakiet: org.tsiss.sng.probability.choose.group)
  1. — parametry specyficzne dla danej klasy
  2. GroupNegativePreference.handicap = 1
  • externalPositiveEdge = GroupPositivePreference – nazwa klasy użytej jako funkcji wybierającej docelową grupę dla nowej pozytywnej krawedzi (pakiet: org.tsiss.sng.probability.choose.group)
  1. — parametry specyficzne dla danej klasy
  2. GroupPositivePreference.handicap = 2

Jak widzimy po skompilowaniu projektu możemy zmieniać mechanizm działania aplikacji bez potrzeby ponownej przebudowy projektu.
Możliwości aplikacji możemy rozszerzać dodając nowe implementacje klas.
Należy jednak pamiętać,że wszystkie klasy utworzone w pakiecie org.tsiss.sng.probability.* i org.tsiss.sng.edge.age należy zarejestrować w odpowiedniej enumeracji w pakiecie org.tsiss.sng.enum.

Sytuacja jest podobna z formatami wyjściowymi utworzonej sieci (pakiet: org.tsiss.sng.outputs).
Niestety format UCINet wymaga poprawek.

Specyficzne parametry dla danych klas:

Jeżeli zaszłaby potrzeba pobrania z pliku konf. Specyficznego nowego parametru, zapisujemy go wg. schematu:

„NazwaKlasy.nazwaParametru=Wartość”

Po dodaniu parametru należy go zarejestrować w enumeracji org.tsiss.sng.enum.ApplicationOption.java, np:

AGE_FUNCTION(„ageFun”, „AgeFunction”,true,”Name algorithm used to determine age function”,”NoFunction”),

PARAM_NAME(„shortName”, „LongName”,true,”Description”,”DefaultValue”),

Jeżeli mamy już zarejstrowany parameter w klasie ApplicationContext dodajemy:

  1. pole przechowujace wartość naszego paramteru
  2. w metodzie setApplicationValue, dodajemy warunek case i metode konwersji naszego paramteru z klasy String
  3. utworzenie gettera dla pola z pkt 1.

To wszystko.

Jeżeli z jakiś względów użytkownik, nie może zarejestrować, dodać wpisu, może wykorzystać metode ApplicationContext.getProperty(String key, String defaultValue), by pobrać wartośc parametru prosto z pliku sng.properties. Jednak należy pamiętać, że powyższe rozwiązanie nie jest zalecane.

Źródła projektu dostępne pod adresem: http://sirius.cs.put.poznan.pl/~inf89843/tpd2/tsiss/sng.zip

Przykładowo wygenerowane sieci: http://sirius.cs.put.poznan.pl/~inf89843/tpd2/tsiss/sng_net.rar

Uruchamanie:

“java –jar SignedNetworkGenerator.jar plik_konf.properties”

Jako jedyny parametr funkcja przyjmuje relatywną ścieżkę do pliku konfiguracyjnego. Jeżeli użytkownik pominie parametr, aplikacja spróbuje załadować plik sng.properties z katalogu aplikacji.

Miłego korzystania:)

Luty 20, 2013

System Rekomendacji Gier Planszowych

- autor: tsissput

Cel projektu:

Celem projektu było stworzenie systemu będącego w stanie polecać gry planszowe na podstawie wybranej gry planszowej lub preferencji mechanik sterujących grami planszowymi.

Realizacja projektu:

W celu ustalenia jakie gry można polecić, w zależności od wybranego przez użytkownika tytułu, należało stworzyć graf podobieństw pomiędzy grami planszowymi. Do ustalenia podobieństwa pomiędzy nimi zostały wykorzystane ich mechaniki. Wyróżnia się ponad 40 różnych mechanik sterujących grami planszowymi, każda gra wykorzystuje dowolną liczbę tych mechanik w swoim działaniu. Fakt ten został wykorzystany do ustalania podobieństwa między poszczególnymi tytułami- dla każdej pary gier planszowych sprawdzana jest liczba mechanik, z których oba tytuły korzystają oraz liczba różnych mechanik, które te gry wykorzystują. Iloraz tych dwóch wartości daje nam miarę podobieństwa jednej gry planszowej do drugiej. Wartości tej miary stanowią krawędzie w grafie podobieństw pomiędzy grami planszowymi. Ponieważ miara ta jest wartością symetryczną, krawędzie w grafie są nieskierowane. Aby zniwelować dużą ilość krawędzi, szczególnie wychodzących od wierzchołków reprezentujących gry z dużą ilością wykorzystanych mechanik, zastosowano próg odcięcia na poziomie 0,3. Gdy użytkownik szuka gry podobnej do wymienionego tytułu, system zwraca wszystkie wierzchołki, które posiadają krawędź prowadzącą do wierzchołka reprezentującego wybraną grę. Wszystkie tytuły są wyświetlane wg miary podobieństwa w kolejności malejącej wraz z najważniejszymi informacjami o danych tytułach. System udostępnia także alternatywną metodę rekomendacji gier. Pozwala on na wybranie kilku mechanik gier planszowych, po czym dodawany jest tymczasowy wierzchołek grafu i tworzone są krawędzie wychodzące z niego zgodnie z zasadami wymienionymi powyżej. Następnie zwracane są wszystkie tytuły które zostały połączone krawędzią z tymczasowym wierzchołkiem. Po dokonaniu rekomendacji tymczasowy wierzchołek zostaje usunięty z grafu.

Wykorzystane technologie:

– Java
– Play Framework
– Twitter bootstrap

Wizualizacja sieci oraz działania systemu:

Graf podobieństw gier planszowychstronaGłówna wynikigry

Kody źródłowe:

http://sirius.cs.put.poznan.pl/~inf89752/iswd/tsiss.zip

 

Autorzy:

Jakub Jaróżek
Dawid Neumann

Luty 19, 2013

Semantic WoW

- autor: tsissput

Cel projektu

Celem projektu było stworzenie i wizualizacja grafu powiązań pomiędzy graczami World of Warcraft – jednej z najpopularniejszych gier MMORPG w sieci. Niezbędne dane pobrano korzystając z WoW API do bazy danych, przetworzono i uzyskano graf w formacie Netdraw VNA. Wizualizacji dokonano z użyciem programu Gephi.

Zastosowane technologie

Informacje z WoW API pobrano z użyciem aplikacji konsolowej napisanej w języku Java. Dane przechowywano w bazie MongoDB, zaś przetwarzanie odbywało się przy pomocy wspomnianej aplikacji oraz skryptów JavaScript. Dalszych operacji na grafie oraz wizualizacji dokonano w programie Gephi.

Zaimplementowana aplikacja

Jak wspomniano aplikacja jest konsolowa, umożliwia następujące operacje:

  • wczytanie pliku z nazwami gildii,
  • pobieranie nie ściągniętych gildii (na podstawie wczytanej listy nazw),
  • pobieranie nie ściągniętych postaci (na podstawie listy nazw członków gildii),
  • oba powyższe,
  • usunięcie zawartości bazy danych,
  • wygenerowanie pliku z grafem na podstawie pobranych danych przetworzonych za pomocą skryptów JS.

cmd

Architektura aplikacji

Ze względu na sposób udostępniania danych przez WoW Api, aplikacja wymaga nazw gildii, których ma dotyczyć analiza (względnie nazw wszystkich gildii na serwerze). Informację tę uzyzkano z serwisu WoW Progress i wczytywano z plików.
arch

Model ORM

Do mapowania obiektowo relacyjnego wykrorzystano bibliotekę Morphia współpracującą ze biblioteką Java sterowników bazy MongoDB.
orm

Uzyskane dane

Pobrano informację o graczach serwera Arathor-EU należących do gildii uzyskanych z WoW Progress. Dane pobierano na przestrzeni 5 dni w pierwszej połowie stycznia 2013. Po zapisie do bazy danych jej rozmiar wynosił ponad 35GB.

Pobrano informacje o 302 gildiach oraz 38 629 postaciach. Ze względu na rozmiary danych i przyjęty sposób analizy połączeń zdecydowano się przetworzyć jedynie postaci z 5 najlepszych (pod względem liczby punktów osiągnięć):

  • Alliance of Destiny
  • Maligned
  • Velvet Glove
  • Retired
  • Blacksail Pirates

Do tych gildii należy 1760 postaci powiązanych łącznie z 650 kontami graczy.

Graf uzyskany na podstawie top 5 gildii

Postaci są opisane takimi atrybutami jak: średni poziom przedmiotów, klasa, rasa, płeć, poziom postaci, oraz informacją czy jest to główna postać gracza. Wiele postaci gracza udało się identyfikować na podstawie identycznej listy osiągnięć zdobywanych w tym samym momencie. Za główną uznawano tę o najwyższym poziomie w danej gildii (tak więc gracz mógł mieć więcej niż jedną główną postać). Krawędź przechowuje również informację o tym, czy łączy dwie główne postaci, oraz o minimalnej rozbieżności czasowej w zdobyciu osiągnięcia przez obie postaci.

Jako że WoW API nie udostępnia bezpośrednio informacji o tym jak gracze dobierają się w drużyny, dwie postaci połączono krawędzie jeżeli zdobyli osiągnięcie w podobnym czasie (założono, że zdobywali go wspólnie), lub są w tej samej drużynie pvp. Wagą krawędzi ustanowiono liczbę osiągnięć, które zostały zdobyte w podobnym (w odstępie pięciu minut) czasie.

W rezultacie otrzymano:

  • 48792 Krawędzi
  • 36859 krawędzi między głównymi postaciami
  • 153 krawędzie pvp

W pierwszym pliku  krawędzie poprowadzono jedynie pomiędzy głównymi postaciami, oraz pomiędzy wszystkimi postaciami danego gracza. W drugim  umieszczono wszystkie krawędzie.

Wizualizacja

Poniższe rysunki przedstawiają grafy, w którym krawędzie poprowadzono jedynie między głównymi postaciami. Pierwsze dwie ilustrują wspólne zdobywanie osiągnięć, podczas gdy w trzecim zawarto informacje o grze arenowej. Na dwóch początkowych obrazkach pozostawiono jedynie krawędzie między postaciami, które przynajmniej jedno osiągnięcie zdobyły w tym samym momencie, i to tylko te, których waga przekraczała 40. Wielkość wierzchołka odpowiada jego wartości pagerank, zaś kolor wskazuje przynależność do gildii (na pierwszym), poziom posiadanego ekwipunku (na drugim).

guilds_circle_2guilds_circlepvp

Luty 18, 2013

Co słychać w mediach społecznościowych?

- autor: tsissput

Założenia projektu

Celem projektu było stworzenie prototypu aplikacji umożliwiającej analizę wiadomości gazetowych pod kątem popularności, którą uzyskały w serwisach społecznościowych.

Wynik realizacji projektu

Utworzone zostały dwa moduły. Pierwszy z nich odpowiedzialny jest za ciągłą akwizycję wpisów z kanałów RSS wylistowanych w pliku tekstowym. Informacje o kanałach RSS i ich wpisach zapisywane są w bazie danych.

Drugi moduł zajmuje się pobieraniem informacji o zainteresowaniu, jakie wzbudziły wiadomości w serwisach społecznościowych. Prototypowa aplikacja zbiera informacje o liczbie tweetów na serwisie Twitter zawierających link do badanego artykułu oraz liczbę udostępnień artykułu na portalu Facebook. Pobrane dane zapisywane są w bazie danych. Moduł ten generuje również pliki csv z zestawieniem najpopularniejszych artykułów ogółem oraz najpopularniejszych w każdym z kanałów RSS. 

Rozwój projektu

Kolejnymi krokami rozwoju aplikacji mogą być:

– rozszerzenie modułu zbierającego informacje o zainteresowaniu o kolejne serwisy społecznościowe

– opracowanie funkcji oceny zainteresowania na podstawie informacji ze wszystkich serwisów

– stworzenie modułu analizującego artykuły pod kątem cech wspólnych, próba klastrowania wiadomości, w celu odnalezienia zależności między treścią i tematyką artykułu a wzbudzonym zainteresowaniem

– dodanie interfejsu graficznego

Wykorzystane technologie

– Java

– PostgresSQL

– biblioteka do obsługi kanałów RSS: ROME http://rometools.org/

– lekka i bardzo wygodna biblioteka odpowiedzialna za integrację z bazą danych, ORM: jOOQ http://www.jooq.org/

– Twiiter API

– Facebook API

Kod źródłowy + przykładowe wyniki działania aplikacji

https://github.com/k-cz/tsiss

 

 

Autor

Kacper Skory

 

Tagi:
Luty 13, 2013

Event Finder czyli wszystkie interesujące wydarzenia w jednym miejscu

- autor: tsissput

Celem projektu było stworzenie aplikacji, która ułatwi użytkownikom dostęp do informacji na temat zbliżających się wydarzeń. Dzięki wybraniu interesujących nas kategorii oraz miast otrzymujemy dostosowaną grupę wydarzeń. Dzięki temu nie trzeba przekopywać się przez treści zupełnie nas nie interesujące. Wydarzenia oraz kategorie są dodawane przez użytkowników i to oni dbają o dostarczenie jak najciekawszej treści.
MainPage
Na zaprezentowanym obrazku widać dwa wydarzenia, są to koncerty z kategorii muzyki rockowej. Wydarzenia wybierane są na podstawie ustawień użytkownika, tak więc w systemie widnieją innego typu wydarzenia, natomiast użytkownik widzi dobrane dla niego. Ma oczywiście możliwość przejrzenia wszystkich wydarzeń, jednak jest w tym celu zrealizowany inny widok. Wydarzenia na które użytkownik planuje się wybrać są oznaczana na niebiesko.
Oczywiście jak na portal społecznościowy przystało nie może obyć się bez interakcji między użytkownikami. Możliwe jest śledzenie wybranych osób dzięki czemu dostajemy spis wydarzeń na jakie się wybierają. Dodatkowo każde wydarzenie może zostać skomentowane przez użytkowników.
Inwigiluj

Do stworzenia aplikacji wykorzystaliśmy technologię .Net, język C#, logika biznesowa została zrealizowana z wykorzystaniem technologii WCF dzięki czemu istnieje możliwość stworzenia dodatkowych interface’ów użytkownika. Domyślny interface został zrealizowany z wykorzystaniem technologii MVC oraz styli CSS Twitter Bootstrap.

Autorzy
Tomasz Bartoszewski
Marcin Wolicki