Archive for Lipiec, 2012

Lipiec 17, 2012

Analiza behawioralna

- autor: tsissput

W ostatnim czasie, miałem okazję zapoznać się z dwoma artykułami Longbing Cao [1] [2] oraz jednym tego samego autora napisanym razem z Philipem Yu, opisującymi BIA – czyli Behavioral Informatics and Analytics (Informatyka i Analiza Behawioralna). Jest to nowa, zaproponowana przez nich gałąź informatyki, która koncentruje się na analizie wzorców zachowania ludzi, na podstawie zebranych uprzednio danych.

W przeciwieństwie do tradycyjnego podejścia, zaproponowana w artykule metoda bierze pod uwagę nie same dane transakcyjne i demograficzne (czyli wyrwane z szerszego kontekstu pojedyncze zdarzenia – takie jak np. sprzedaż akcji na rynku kapitałowym), ale sekwencje zachowań, ich cel, otoczenie, czas, miejsce, a także osiągnięty efekt. Inaczej mówiąc, autorzy artykułów proponują zebrane dane o zachowaniach ludzi traktować jako sekwencję zdarzeń, w której branych jest pod uwagę wiele czynników jednocześnie. Na przykład analizując dane dotyczące transakcji finansowych, byłyby brane pod uwagę nie tylko dane dotyczące pojedynczych operacji zakupu lub sprzedaży aktywów, ale sekwencje takich zdarzeń, wraz z towarzyszącym im kontekstem (jak choćby cel transakcji). Jedno takie zdarzenie nazywane jest wektorem behawioralnym i może on składać się z takich elementów jak:

  • Podmiot wykonujący aktywność;

  • Obiekt, na którym aktywność jest wykonywana;

  • Kontekst aktywności;

  • Cel;

  • Informacja o wiedzy podmiotu o świecie;

  • Akcja;

  • Plan działania podmiotu;

  • Skutek aktywności;

  • Ograniczenia;

  • Czas wystąpienia aktywności;

  • Miejsce wystąpienia aktywności;

  • Aktualny status aktywności;

  • Powiązane akcje.

Do pełnej analizy zazwyczaj jest potrzebna sekwencja takich wektorów. W celu przygotowania wektora, konieczne jest uprzednie zebranie danych, które posłużą do jego budowy. Dane te mogą być zaczerpnięte z tradycyjnej, transakcyjnej bazy danych i po odpowiednim połączeniu można je wykorzystać do budowy wektorów behawioralnych.

Po przygotowaniu sekwencji wektorów behawioralnych, metoda koncentruje się na wykryciu wzorców zachowań operujących na sekwencjach w/w wektorów. Cały proces można podzielić na następujące kroki:

  1. Modelowanie zachowań – czyli stworzenie właściwego dla rozwiązywanego problemu i oczekiwanych wyników wektora behawioralnego, przy ograniczeniach wynikających z dostępnych danych.

  2. Konwersja danych do modelu behawioralnego.

  3. Analiza wzorców behawioralnych oparta o stworzoną dla danego zbioru danych metodę, która następnie jest zastosowana do stworzonych wektorów w celu wyodrębnienia konkretnych wzorców zachowań.

  4. Stworzenie reguł biznesowych na podstawie opracowanych wzorców zachowań.

Według zapewnień autorów, takie podejście pozwala na osiągnięcie dużo lepszych rezultatów w ocenie przyczyn i skutków badanych zachowań.

Ponieważ samo zagadnienie i metodologia jest szczegółowo opisana w artykule, pozwolę sobie nie podejmować w tej chwili dalszych detali tej metody, ale przejść do moich spostrzeżeń, które nasunęły mi się podczas lektury.

Analiza behawioralna nie jest w bezpośrednim zakresie moich zainteresowań w sensie naukowym, niemniej jednak jest to dziedzina, z którą moim zdaniem każdy styka się w mniejszym lub większym stopniu – dokonując jej często czysto intuicyjnie. Z tego powodu koncepcja BIA sama w sobie nie wydała mi się szczególnie rewolucyjna ani odkrywcza, jest raczej inkrementacyjnym podejściem do dotychczasowych metod analizy.

Nieco zaskoczyło mnie, że proponowana przez autorów artykułu analiza ma opierać się w całości o dotychczas zebrane dane transakcyjne, które jedynie są transformowane do nowej postaci. Takie podejście ma oczywiście tę zaletę, że analizie można poddać wiele opisanych wcześniej zjawisk i porównać wyniki z tradycyjnymi metodami, jednak nie mogłem się oprzeć wrażeniu, że analiza biorąca pod uwagę cele i kontekst działania człowieka, powinna opierać się na bardziej kompletnych przesłankach.

Można posłużyć się tutaj wcześniej wspomnianym przykładem transakcji finansowych. W budowanym przez autorów modelu, biorą oni pod uwagę tylko dane przechowywane przez systemy finansowe, które zapisują jedynie informacje bezpośrednio związane z działaniem giełdy. Na podejmowane decyzje wpływa dużo szerszy wachlarz czynników i choć oczywiście ciężko wziąć pod uwagę je wszystkie, próby stworzenia dokładnego modelu behawioralnego na tak ograniczonym zestawie wejściowym wydają mi się zbyt ograniczone.

Problem ten może jednak być trudny do rozwiązania, ze względu na pojawiający się w tej sytuacji paradoks Boniniego, który mówi że może być niemożliwe zbudowanie dokładnego modelu o stopniu skomplikowania mniejszym niż system, który staramy się symulować.

Mimo wszystko uważam jednak, że nie można uznać tego za wadę proponowanego rozwiązania, gdyż wynika po prostu z założeń przyjętych podczas pracy i metodę można w prosty sposób rozszerzyć o dodatkowe dane wejściowe.

Aspektem, który utrudnia pełną ocenę tej pracy jest jej mocno teoretyczny charakter. Praca koncentruje się na ogólnych założeniach nowej metody, na razie dość pobieżnie tylko opisując sposoby wnioskowania w modelu.

Autor pokusił się o analizę dwóch konkretnych przypadków[1]: zachowań inwestorów na rynku finansowym oraz zachowań związanych z pobieraniem świadczeń socjalnych (a w szczególności kwestie wychwytywania niesłusznie nadpłaconych przez państwo świadczeń na rzecz obywatela).

W pierwszym przypadku brano pod uwagę operacje związane ze sprzedażą i zakupem papierów wartościowych, analizując przy tym zarówno sekwencję takich decyzji podejmowanych przez inwestora oraz szereg dodatkowych czynników takich jak wielkość transakcji czy jej skutek.

Drugi przypadek obejmował takie czynniki jak rejon wypłacanych świadczeń, płeć osoby pobierającej świadczenie, jej sytuację rodzinną, wykształcenie czy pochodzenie.

W każdym przypadku autor artykułu starał się wykryć reguły prowadzące do takich a nie innych zachowań. Reguły te mogłyby być następnie wykorzystane do przeciwdziałania niepożądanym zachowaniom i stymulowania tych pożądanych.

Wyniki eksperymentu zaprezentowane są w artykule jako obiecujące, jednak ich praktyczna użyteczność nie jest udowodniona, ani też nie są one w bezpośredni sposób porównane z alternatywnymi metodami analizy zachowań. Brakuje również kompleksowego przedstawienia wyników eksperymentów i konkretnych przykładów wynikających z nich konkretnych korzyści.

Podsumowując, zaprezentowana metoda sama w sobie wydaje się ciekawym rozszerzeniem istniejących metod analizy, jednak trudno na tym etapie oceniać, na ile wpłynie na dotychczasowe podejście do badań ludzkich zachowań. BIA przypomina w założeniach podejście do analizy, które jest bardziej intuicyjne dla człowieka – czyli branie pod uwagę wielu powiązanych czynników i traktowanie ich jako sekwencje zdarzeń, a nie oderwane od siebie dane statystyczne.

W mojej ocenie, zaprezentowana metoda może borykać się z problemami związanymi z zebraniem odpowiednich danych do analizy, jak również z nadmiernym skomplikowaniem tworzonych wzorców. Z tego powodu może być ona podatna (choć czy jest tak rzeczywiście, nie można ocenić bez dokładniejszych eksperymentów) na efekty związane z przeuczeniem, czyli stworzeniem zbyt specjalistycznych wzorców, które nie będą miały szerszego praktycznego zastosowania.

Ze względu na postępującą informatyzację kolejnych dziedzin życia, analiza behawioralna będzie miała coraz szersze spektrum danych do przetworzenia, a co za tym BIA może zyskać na znaczeniu. Być może okaże się przydatna podczas analizy ogromnej ilości danych zebranych przez portale społecznościowe, które w połączeniu z konkretnymi danymi dotyczącymi działań biznesowych mogą dać ciekawe rezultaty. Okaże się to jednak dopiero, jeśli dyscyplina będzie się dalej rozwijać i będzie stosowana szerzej w praktyce.

Cao, L. (2010). In-depth behavior understanding and use: The behavior informatics approach Information Sciences, 180 (17), 3067-3085 DOI: 10.1016/j.ins.2010.03.025

Longbing Cao (2008). Behavior Informatics and Analytics: Let Behavior Talk IEEE International Conference on Data Mining Workshops

Longbing Cao, & Philip S. Yu (2009). Behavior Informatics: An Informatics Perspective for Behavior Studies IEEE Intelligent Informatics Bulletin

Reklamy
Lipiec 3, 2012

Grafowe bazy danych

- autor: tsissput

Relacyjne bazy danych przyzwyczaiły nas do myślenia o danych, ich reprezentacji i utrwalaniu w bardzo ograniczony sposób. Kluczowe jest określenie sztywnego podziału danych na kategorie oraz określenie ścisłych relacji między nimi. Takie podejście ma szereg zalet, takich jak łatwy sposób reprezentacji ujętych w ten sposób danych w pamięci komputera czy ich późniejsze filtrowanie przy wykonywaniu zapytań. Często jednak taki sposób reprezentacji informacji okazuje się sztuczny, gdyż na poziomie aplikacji wygodniej jest stosować ogólniejsze struktury danych. Grafy na przykład pozwalają łatwo modelować m.in. rekurencję, ścieżki, hierarchie, etc. Za przykład usług wymagających modelowania danych w ten sposób mogą służyć sieci społecznościowe, systemy zarządzania treścią czy choćby systemy stron wiki. Oczywiście możliwe jest reprezentowanie grafów w relacyjnych bazach danych, jednak jak pokazują badania (patrz niżej), takie rozwiązania nie skalują się, są trudne w użyciu oraz uniemożliwiają stosowanie optymalizacji specyficznych dla grafów. Ogromnym wyzwaniem jest przechowywanie grafów dużych rozmiarów, a także ich efektywne przeszukiwanie. Stąd wysiłki naukowców mające na celu zaproponowanie  nowych modeli danych i języków zapytań, które pozwoliłyby na upowszechnienie się tzw grafowych baz danych.

GraphDB [1] stanowi rozszerzenie obiektowych baz danych pozwalające na bezpośrednie modelowanie i operowanie na grafach. W tym celu zdefiniowane są trzy nowe klasy obiektów: klasy proste (simple classes), połączenia (link classes) i ścieżki (path classes). Obiekty klas prostych reprezentują węzły grafu, połączenia odpowiadają łukom grafu i zawierają referencje do dwóch obiektów klas prostych. Natomiast obiekty klasy ścieżek przechowują informację na temat wszystkich węzłów i krawędzi grafu, które dana ścieżka odwiedza.

Z uwagi na to, że opisywane rozwiązanie stanowi rozszerzenie obiektowej bazy danych, możliwe jest określanie hierarchi klas obiektów składowych grafów. Wymaga to dodatkowego, złożonego mechanizmu zapewniającego spójność bazy. Ciekawym pomysłem jest określanie klas ścieżek jako wyrażeń regularnych na zbiorze klas połączeń.

W artykule przedstawiony jest jedynie szkic języka zapytań dla grafowych baz danych. Podstawą języka jest wyrażenie derive (derive statement), które może być używane podobnie jak wyrażenie select … from … where … w relacyjnych bazach danych. Prosty przykład znajdujący tytuły książek napisanych przez Grahama Greene’a w 1943 roku podany jest poniżej:

on person wrote book
where person.name = "Green" and
      book.year = 1943
derive book.title

gdzie person i book są klasami prostymi, wrote natomiast jest klasą połączeń. W powyższym przykładzie wynikiem będzie sekwencja (zawierająca 0, 1 lub więcej) elementów typu String. Wynikiem działania wyrażenia derive mogą być również sekwencje dowolnych typów, w tym obiektów klas prostych, połączeń i innych. Sekwencje nie muszą zawierać wyłącznie obiektów tego samego typu, mogą być sekwencjami heterogenicznymi. Do ich przetwarzania służy wyrażenie rewrite, dzięki któremu możliwe jest zastąpienie obiektów lub podsekwencji przez inne (nowe) obiekty. Autor planuje wprowadzenie do języka zapytań dodatkowych operacji pozwalających na m.in. sortowanie, grupowanie, pozyskiwanie najkrótszej ścieżki, etc.

GraphDB był pierwszym krokiem w kierunku projektowania grafowego modelu danych, który łatwo integrowałby się z obiektowym modelem danych. Przedstawione w artykule idee zostały zaimplementowane jako element platformy SECONDO, która została opisana dopiero 7 lat poźniej, w 2000 roku [1*].

Autorzy [2] wykorzystali model danych zbliżony do tego z [1]. Zdefiniowane zatem są typy węzłów (node types), krawędzi (edge types), ścieżek (path types) i dodatkowo typy grafowe (graph types) zawierające m.in. kolekcje węzłów i ścieżek należących do danego grafu. Odpytywanie grafowej bazy danych odbywa się przy wykorzystaniu zaproponowanego w artykule języka GOQL. Bazuje on na języku OQL [2*], ale dodatkowo definuje nowe operatory, które pozwalają na przetwarzanie ścieżek i sekwencji. Przykładowym nowym operatorem jest connected, przyjmujący jako argumenty dwa węzły (ścieżki) a i b. Wyrażenie a connected b jest prawdziwe, jeśli istnieje ścieżka p między węzłem a (ostatnim węzłem ścieżki a) i węzłem b (pierwszym węzłem ścieżki b). Przykładowe zapytanie w GOQL znajdujące połączenia autobusowe między Oxfordem a Londynem wygląda następująco:

select path(p)
from g in Connections,
     s1, s2 in g.Nodes,
     p in paths(g, s1, s2)
where g.name ="BusConnections",
      s1.name="Oxford",
      s2.name="London",
      p : s1 connected s2

W celu ewaluacji zapytań w GOQL, zapytania tłumaczone są z algebry bazującej na O-Algebrze, wykorzystanej wcześniej do przetwarzania zapytań języka OQL. Oprócz znanych z algebry relacyjnej i obecnych w O-Algebrze operatorów takich jak operator selekcji, produktu kartezjańskiego czy unii, znajdują się nowe, związane z nowymi operatorami zdefiniowanymi w GOQL. Autorzy na szeregu przykładów pokazują jak przy ich pomocy możliwa jest ewaluacja zapytań GOQL.

Jak słusznie zauważają autorzy, przetwarzanie grafów wymaga wykonywania trawersali, które często są bardzo kosztowne. Dlatego proponują optymalizację opartą o tzw nodecode’y, unikalne liczby przyporządkowywane wszystkim węzłom (jeden węzeł może mieć przyporządkowanych wiele nodecode’ów). Przydzielanie nodecode’ów poszczególnym węzłom odbywa się poprzez przeszukanie grafu w głąb. Dysponując zbiorami nodecode’ów dwóch dowolnych węzłów, możliwe jest stwierdzenie czy istnieje ścieżka między nimi. Jeśli taka ścieżka istnieje, wszystkie możliwe ścieżki między tymi węzłami mogą zostać wywiedzione bez wykonywania trawersali. Autorzy przyznają, że ta optymalizacja sprawdzać się będzie jedynie dla małych, rzadkich grafów (liczących do 50 węzłów). Nie mówią jednak co sie dzieje, gdy graf ulega modyfikacji. Wydaje się być to problematyczne z uwagi na algorytm  wykorzystujący przeszukiwanie grafu w głąb.

Artykuł zawiera jedynie wstępne porównanie algorytmów używających i nieużywających systemu nodecode’ów. Autorzy przedstawiaja wyłącznie dyskusje na temat złożoności każdego z nich, zostawiając ewaluację zaimplementowanych rozwiązań na przyszłość. Z pobieżnych poszukiwań wynika jednakże, że próżno jej
szukać w kolejnych artykułach autorów.

Autorzy [3] proponują zupełnie odmienne podejście do grafowych baz danych niż prezentowane w [1] czy [2]. Wychodzą bowiem z założenia, że w grafowej bazie danych podstawową jednostką informacji powinien być graf, a nie jego składowe, takie jak wierzchołek czy krawędź. Rozważany model danych dopuszcza grafy, węzły, krawędzie o dowolnej liczbie atrybutów. Podstawą prezentowanego rozwiązania jest formalny język dla grafów, który służy jako baza dla GraphQL, grafowego języka zapytań. W wypadku gramatyki dla grafów symbolami terminalnymi i nieterminalnymi nie są ciągi znaków, a struktury grafowe zwane motywami grafowymi (graph motifs). Motywem grafowym może być zwykły graf lub też graf zbudowany z innych motywów grafowych poprzez ich łączenie, branie ich alternatywy czy też powtarzanie. Tak jak w zwykłej gramatyce językiem jest zbiór wszystkich ciągów znaków, które można  uzyskać wskutek wykorzystania zdefiniowanej gramatyki i podstawowych symboli nieterminalnych, tu język stanowi zbiór wszystkich grafów, które można wygenerować poprzez wykonywanie operacji łączenia, alternatywy czy powtarzania na motywach grafowych.

Podstawą języka GraphQL są wzorce używane do przeszukiwania grafowej bazy danych. Wzorcem jest motyw grafowy wraz z predykatem na argumentach motywu grafowego. Wynikiem zapytania jest lista grafów pasujących do wzorca, niekoniecznie o tej samej strukturze czy atrybutach. Dopasowanie grafu do wzorca powoduje stworzenie powiązania między grafem a wzorcem, dzięki czemu możliwe jest operowanie na otrzymanej liście grafów w jednolity, zdefiniowany przez wzorzec sposób. GraphQL zawiera dodatkowo operator kompozycji (composition operator) pozwalający na przetwarzanie listy wynikowych grafów, podobnie jak to było w przypadku GraphDB. Poniżej znajduje się przykładowe zapytanie w formie FLWR (for, let, where, return) znanej z XQuery [3*] przeszukujące baze artykułów naukowych o nazwie DBLP generujące graf, w którym dowolna para współautorów artykułu ma wystąpić w postaci krawędzi między węzłami reprezentującymi autorów, jeśli artykuł powstał po roku 2000.

graph P {
   node v1 <author>;
   node v2 <author>;
   node a <year>;
} where a.year > 2000;
C:= graph {};
for P exhaustive in doc("DBLP")
   let C:= graph {
      graph C;
      node P.v1, P.v2;
      edge e1 (P.v1, P.v2);
      unify P.v1, C.v1 where P.v1.name=C.v1.name;
      unify P.v2, C.v2 where P.v2.name=C.v2.name;
   }

Wyrażenie for dopasowuje zdefiniowany wcześniej wzorzec P do grafów w bazie danych, let natomiast przetwarza wyniki dopasowań tworząc nowe grafy zawierające łuk między węzłami reprezentującymi współautorów.

Algebra grafowa, którą wykorzystuje GraphQL, to algebra relacyjna ale zaadoptowana do świata grafów. Zatem znane z algebry relacyjnej operatory takie jak operator selekcji czy iloczynu kartezjańskiego jako argumenty przyjmuje grafy a nie sekwencję krotek. Autorzy dowodzą, że nierekursywna wersja użytej algebry grafowej jest równoważna algebrze relacyjnej.

Problem dopasowywania wzorców w grafach jest problemem NP-zupełnym. Autorzy argumentują, iż brak łamania struktury grafów na poszczególne relacje (węzły, łuki, ścieżki) pozwala na stosowanie szeregu optymalizacji specyficznych dla grafów, np. ograniczających przestrzeń przeszukiwań. Autorzy opisują szczegółowo trzy  optymalizacje i demonstrują wyniki ewaluacji dla dwóch benchmarków: rzeczywistego i syntetycznego. Uzyskane wyniki pokazują, że przyjęte podejście i użyte optymalizacje pozwalają na osiągnięcie wydajności do dwóch rzędów wielkości większej niż w przypadku użycia bazy SQL do modelowania grafów.

Opisane krótko w tej notce rozwiązania, różniące się między sobą co do przyjętego podejścia, rozważanych aspektów, dyskusji strony implementacyjnej, stanowią przyczynek do tworzenia dojrzałych systemów grafowych baz danych. Dobrym dowodem na to, że istnieje zapotrzebowanie na rozwiązania tego typu jest uzyskanie we wrześniu zeszłego roku finansowania w wysokości 10.6 miliona dolarów dla otwartoźródłowego projektu grafowej bazy danych Neo4j [4*].

[1] Ralf Hartmut Guting (1994). GraphDB: Modeling and Querying Graphs in Databases 20th International Conference on Very Large Data Bases

Stefan Dieker, & Ralf Hartmut Guting (2000). Plug and Play with Query Algebras: SECONDO-A Generic DBMS Development Environment 2000 International Symposium on Database Engineering & Applications (IDEAS ’00)

[2] L. Sheng, Z. M. Ozsoyoglu, & G. Ozsoyoglu (1999). A Graph Query Language and Its Query Processing 15th International Conference on Data Engineering (ICDE ’99)

[2*] The Object Data Standard: ODMG 3.0. Edited by R.G.G. Cattell and Douglas K. Barry, with contributions by Mark Berler, Jeff Eastman, David Jordan, Craig L. Russell, Olaf Schadow, Torsten Stanienda, and Fernando Velez. Morgan Kaufmann Publishers, Inc., 2000. ISBN 1-55860-647-5.

[3] Huahai He, & Ambuj K. Singh (2008). Graphs-at-a-time: query language and access methods for graph databases ACM SIGMOD international conference on Management of data (SIGMOD ’08)

[3*] XQuery 1.0: An XML Query Language (Second Edition), http://www.w3.org/TR/2010/REC-xquery-20101214/

[4*] http://www.neotechnology.com/2011/09/neo-technology-closes-10-6-million-series-a
-funding-to-accelerate-adoption-of-nosql-in-the-enterprise/