Kolejna metoda sztucznej inteligencji - analiza skupień

Jednym z obszarów sztucznej inteligencji, który ostatnio bardzo się rozwija, jest tak zwana analiza skupień. Jest to związane z największym wyzwaniem, przed jakimi stoi współczesna informatyka - tak zwanym problemem "Big Data". Chodzi o analizy ogromnych zasobów informacji, jakie gromadzą współczesne bazy, banki i hurtownie danych. Przypuszcza się, że w tych zasobach ukryta jest wiedza, której odkrycie mogłoby przynieść znaczące korzyści. Nie jest jednak łatwo tę wiedzę pozyskać, gdyż jest ona w zgromadzonych danych ukryta, uwikłana, nie oczywista, nie intuicyjna. Jednak jest ważna, bo tę wiedzę, która była odsłonięta, prosta, oczywista i intuicyjna już dawno odkryto i wykorzystano, więc na jej podstawie nie zdobywa się przewagi konkurencyjnej. Natomiast odkrycie czegoś nowego i nieoczekiwanego może otworzyć skarbnicę nowych korzyści. Dlatego takich właśnie nowych i nieoczekiwanych odkryć poszukujemy w "Big Data" z pomocą metod określanych jako "Data Mining". Trudność tych poszukiwań dodatkowo podnosi fakt, że zwykle nie wiadomo z góry, czego my w tych danych właściwie szukamy?

Gromadzenie danych jest dziś łatwe i tanie. Praktycznie wszystkie czynności, jakie wykonujemy na co dzień w pracy zawodowej i prywatnie są związane z komputerami, pozostawiają w związku z tym cyfrowy ślad. Płacąc w sklepie za zakupy, rozmawiając przez telefon, wysyłając i odbierając email, rejestrując się u lekarza, wyjmując pieniądze z bankomatu, przeglądając strony internetowe - zostawiamy cyfrowe ślady.

W przypadku nacechowanego złą wolą ukierunkowania zainteresowania (zwłaszcza mediów) na konkretnego człowieka - te cyfrowe ślady są jak krople krwi rannego zwierzęcia, niezawodnie prowadzące pozbawionego skrupułów siepacza. Niestety uzasadniona jest coraz powszechniejsza dziś świadomość, że te komputerowe tropy, wszędzie i zawsze gromadzone, mogą stać się dla każdego człowieka źródłem osobistego zagrożenia. Powinniśmy przeciwko temu protestować przy każdej okazji i na każdym miejscu, gdyż niezwykle łatwo jest dziś naruszyć czyjąś prywatność, a - jak się sam przekonałem - przy istniejącym stanie prawnym podsłuchiwany czy podglądany nie może się skutecznie bronić przed efektami tej permanentnej cyfrowej inwigilacji.

Pozostawmy jednak na boku te przykre spostrzeżenia związane z nadużywaniem dostępności danych w celu niszczenia pojedynczych ludzi i skupmy się na pozytywnych stronach problemu Big Data i na metodach przynoszących rzeczywiste korzyści wynikające z wiedzy, którą udaje się czasem pozyskać.

Jedną z takich metod jest tytułowa analiza skupień.

Wykrycie, że jakieś obiekty w jakiejś przestrzeni skupiają się (grupują) w jakimś niewielkim obszarze

pozwala często na wyciąganie bardzo interesujących wniosków. Wnioski te mogą dotyczyć rozważanych obiektów albo obszaru, w którym to grupowanie ma miejsce. Czasem wykrycie faktu takiego spontanicznego grupowania także może posłużyć do tego, by ustalić jakieś niebanalne właściwości przestrzeni, w której to grupowanie zachodzi.

Słowo przestrzeń użyte w poprzednim zdaniu jest tu bardzo ważne. Dostrzeżenie, że obiekty skupiają się w realnym świecie, jak na przywołanym wyżej rysunku, jest stosunkowo łatwe. W informatyce zwykle jednak mówimy o obiektach abstrakcyjnych, opisywanych za pomocą pewnych (rejestrowanych w bazie danych) cech. Na przykład sylwetki ludzi można opisać za pomocą dwóch cech: wzrost oraz waga. Każdy człowiek po określeniu jego wzrostu i wagi może być przedstawiony jako punkt w dwuwymiarowej przestrzeni, której osie opisane są właśnie wartościami tych cech.

Na podstawie użytych cech w zbiorze danych może być dokonana kategoryzacja, gdy dla każdej cechy wprowadzimy jakieś kategorie (dla wzrostu będą to kategorie niski-wysoki a dla wagi szczupły-otyły) oraz ustalimy granice wartości cech, decydujące o przynależności do takiej lub innej kategorii.

Kategoryzacja nie jest jednak najlepszym sposobem opracowania rozważanych danych, bo wprowadza element arbitralny (te granice!) i "na siłę" wszystkie obiekty wpycha do wcześniej przyjętych kategorii. Znacznie doskonalsza jest analiza skupień pozwalająca wykryć i trafnie opisać rzeczywiście występujące wśród danych typowe ich zestawienia, a także pokazująca, że niektóre dane są na tyle nietypowe, że pozostają poza wszystkimi skupieniami.

W dwuwymiarowej przestrzeni (opartej na uwzględnianiu tylko dwóch cech) takie skupienia jest bardzo łatwo wyodrębnić.

W przestrzeni trójwymiarowej też się to da zrobić "ręcznie" poprzez ocenę danych przez człowieka.

Ale co zrobić, jeśli obiekty są charakteryzowane przez kilkanaście, kilkadziesiąt czy kilkaset cech, czyli punkty osadzone są w przestrzeni wielowymiarowej?

Takimi właśnie trudnymi przypadkami zajmuje się analiza skupień, nazywana też klasteryzacją (od angielskiego terminu cluster analysis). Oczywiście szczegółów używanych w tej metodzie technik nie jestem w stanie tu opisać (zwłaszcza, że jest ich dużo i są bardzo zróżnicowane), ale z grubsza biorąc dzielą się one na metody aglomeracyjne i podziałowe. Zilustrujemy poniżej metodę aglomeracyjną, polegającą na tym, że do skupień kolejno dołącza się obiekty aż do uzyskania pożądanego podziału zbioru danych. Metoda podziałowa (nie omawiana tu) polega na tym, że na początku wszystkie obiekty łączy się w jedno wielkie skupisko, a potem się rozcina kolejno najsłabsze powiązania, wyodrębniając kolejne skupienia.

Przebieg działania metody aglomeracyjnej dla prostego przykładu pięciu obiektów w dwuwymiarowej przestrzeni (rysowanych jako punkty na płaszczyźnie) wygląda tak: Najpierw wszystkie obiekty są rozważane traktowane jako oddzielne skupienia. W przykładzie na rysunku poniżej jest ich pięć, ale w rzeczywistych zadaniach bywają ich tysiące!

Potem oblicza się wzajemne odległości wszystkich obiektów (co bywa trudne w wielowymiarowej przestrzeni!) i łączy się ze sobą wszystkie te obiekty, których odległość jest mniejsza od pewnego założonego progu. W ten sposób tworzą się pierwsze wieloelementowe skupienia.

W prezentowanym przykładzie połączyliśmy tylko dwa obiekty (czerwony i zielony), ale w ogólnym przypadku na tym etapie mogą powstać setki małych skupień, często kilkuelementowych. Jeśli tych skupień jest za dużo - przesuwamy w górę próg odległości pozwalający łączyć obiekty, w wyniku czego do istniejących skupień dołączane są kolejne obiekty, a także mogą powstać nowe skupienia, łączące te obiekty, które poprzednio nie kwalifikowały się do połączenia, a teraz (przy przesuniętym progu) mogą być zaakceptowane jako elementy pewnego skupienia.

Tę procedurę można kontynuować, tworząc coraz większe skupienia, aż wreszcie wszystkie dane zostaną połączone w jedno wielkie skupienie, co oczywiście nie ma sensu.

Jak zwykle w podobnych przypadkach cała sztuka polega na tym, żeby wiedzieć, kiedy przerwać dalsze łączenie. Przydatny przy tym bywa rysunek nazywany dendrogramem albo drzewem Warda. Dla prezentowanego wyżej przykładu pięciu obiektów wygląda on tak:

Widać na nim, co z czym było grupowane i jak daleki musiał być zakres wiązania, żeby dane skupienie mogło powstać. Pokazany dendrogram jest jednak mało ciekawy, bo przykład był trywialny - tak wybrany, żeby się dało łatwo narysować poszczególne etapy procesu grupowania, ale nietypowy, bo w kolejnych krokach realizacji algorytmu rozrastało się jedno skupienie, więc nic ciekawego nie dawało się zaobserwować. Przyjrzyjmy się jednak innemu przykładowi. Wyobraźmy sobie, że chcemy pogrupować polskie województwa na podstawie danych dotyczących ilości ludności, powierzchni, dochodów, stopnia rozwoju itp. Każdy punkt reprezentujący konkretne województwo jest więc punktem w wielowymiarowej przestrzeni. Efekt zastosowania aglomeracyjnej analizy skupień dla tego przykładu przedstawia rysunek.

Przykład oparty jest na fikcyjnych danych, a rysunek zaadaptowałem z popularnego źródła, więc nie należy w tych wynikach doszukiwać się merytorycznego sensu, ale obejrzeć obrazek i przemyśleć jego interpretację zdecydowanie warto. Widać, że przy przyjęciu jako kryterium granicznej wartości odległości wynoszącej 2 algorytm wyodrębnił cztery skupienia: pierwsze tworzą najsilniej związane województwa warmińsko-mazurskie i podlaskie, drugie województwa łódzkie i śląskie, trzecie świętokrzyskie i opolskie i czwarte województwa dolnośląskie, mazowieckie i wielkopolskie. Algorytm chwilowo pozostawił "bez przydziału" najsłabiej związane z resztą województwa lubelskie, lubuskie, zachodnio-pomorskie, małopolskie, pomorskie i podkarpackie.

Jeśli zasięg dozwolonego wiązania powiększy się do 9 to całe terytorium Polski podzielone zostanie na trzy skupiska, zgodnie z rysunkiem tu pokazanym:

Jak widać metody analizy skupień działają w dużej mierze "pod dyktando" człowieka decydującego, w którym miejscu przeciąć dendrogram. Nie jest to więc klasyfikacja całkowicie obiektywna, ale dla wielu celów może być ona przydatna. Wymieńmy przykładowo jedną korzyść, jaką można odnieść stosując metodę analiz skupień do danych z kas w supermarkecie:

Z tych rachunków kasowych można poznać, jakie towary klienci kupują razem. Na przykład bułki na śniadanie, masło i wędlinę lub sery. Wiedząc, że tak właśnie klient będzie napełniał koszyk można tak rozmieścić te razem kupowane towary, żeby idąc od jednych do drugich klient musiał przejść możliwie długą drogę między półkami zapełnionymi innymi towarami. A nuż się skusi i kupi coś jeszcze?

Z tym zastosowaniem wiąże się znana anegdota: Otóż stosują analizę skupień wykryto (podobno...) grupę klientów łączących w swoim koszyku dość nieoczekiwane zestawienie produktów: pampersy i piwo. Analiza pokazała, że była to grupa młodych tatusiów, którzy wypędzeni z domu przez żonę ("Dziecka nie nakarmisz i nie przewiniesz - to przynajmniej idź i kup mi pieluszki:) idą posłusznie do sklepu, ale żeby pokazać, że oni się tak całkiem jeszcze nie dali wziąć pod pantofel - kupują sześciopak piwa, żeby pokazać w domu, kto tu jest "panem i władcą" :-) .

Po wykryciu powyższej prawidłowości tak rozmieszczono towary w sklepie, żeby idąc od pieluszek do piwa trzeba było przejść obok stoiska z aparatami fotograficznymi. No i sprzedaż tych aparatów wzrosła, bo przecież każdy tatuś łatwo da się przekonać, że pierwsze tygodnie życia dziecka trzeba dokumentować fotograficznie!

Nie dam głowy, że ta anegdota oparta jest na faktach, ale jestem pewien, że oferty operatorów telekomunikacyjnych albo banków budowane są na podstawie starannie przeprowadzonej analizy skupień danych z bilingów lub z operacji na kontach. Tylko nikt się głośno do tego nie przyznaje ...