Wstęp do problemu grupowania

Ten wpis jest wstępem do dość specyficznego problemu, z jakim spotykamy się w uczeniu maszynowym – problemu grupowania obserwacji.

Z tego artykułu dowiesz się:
1. Czym jest problem grupowania?
2. Jak dzielimy algorytmy grupujące?
3. Jakie zastosowania mają algorytmy grupujące?
4. Jak mierzyć jakość grupowania?

Na moim blogu opisywałem już problemy rekomendacji, klasyfikacji i regresji. Najwyższy czas na kolejne typy problemów i algorytmów, które do tej pory nie były poruszane. Niniejszy wpis jest wstępem do cyklu dotyczącego problemu grupowania obserwacji.

Problem grupowania nie cieszy się zbyt wielką popularnością i jest często pomijany zarówno w środowisku akademickim, jak i biznesowym, gdzie prym wiedzie klasyfikacja i regresja. Przy tym jest on bardzo obszerny i szalenie ciekawy. Z tego względu uznałem, że powinienem mu poświęcić należytą uwagę.

Kolejnym argumentem przemawiającym za grupowaniem jest fakt, że często jest ono wykorzystywane w strategicznych dla danej firmy obszarach, np. zbiór klientów podzielonych na charakterystyczne grupy może stanowić istotny wkład do dyskusji nad strategią sprzedaży i marketingu danej firmy na kolejne lata.

Celowo rozbiłem zagadnienie grupowania na cykl wpisów. W tym artykule kilkukrotnie będę wspominać o tym, że „więcej informacji na temat wybranego zagadnienia przedstawię w kolejnych wpisach”. Proszę Cię zatem o wyrozumiałość. Bez tego zabiegu powstałby jeden ogromny wpis, którego nikt nie zdołałby przeczytać od początku do końca. Uznałem, że treść rozbita na kilka części będzie dla Ciebie przystępniejsza drogi czytelniku. 🙂

Problem grupowania – podstawowe definicje

Na początku chciałbym przedstawić kilka definicji związanych z omawianym zagadnieniem, w celu uspójnienia słownika. 🙂

Problemem grupowania w uczeniu maszynowym nazywamy podział próby (zbioru) na grupy obserwacji, które cechują się podobnymi właściwościami. Algorytmy używane w grupowaniu należą do rodziny określanej uczeniem bez nadzoru. W przeciwieństwie do klasyfikacji, czy regresji nie uświadczymy tu zmiennej celu. Podział dokonywany jest zatem na podstawie wszystkich wybranych zmiennych.

Często możemy się spotkać z innymi nazwami tego samego problemu, np. klastrowanie (słowo niewystępujące w słowniku języka polskiego i nawet strona translate.google.pl tłumaczy „clustering” na „grupowanie”), analiza skupień, lub segmentacja. Dla mnie jednak nazwa „grupowanie” wydaje się najtrafniejsza, dlatego będę się nią posługiwać.

Wynikiem działania algorytmów grupujących są grupy obserwacji. Nie wszystkie jednak obserwacje zostają przydzielone do grup. W zależności od wybranej metody grupowania może się zdarzyć, że niektóre obserwacje nie zostanę przypisane do żadnej grupy. Powodem jest fakt, że na płaszczyźnie wielowymiarowej są one odległe od wszystkich pozostałych obserwacji. Nazywamy je wtedy obserwacjami nietypowymi.

Podobieństwem w grupowaniu nazywamy zazwyczaj (w zależności od wybranego podejścia) miarę odległości pomiędzy obserwacjami na przestrzeni wielowymiarowej zdefiniowanej poprzez zmienne objaśniające.

Zastosowania

Grupowanie ma wiele zastosowań. Do najważniejszych można zaliczyć:

• eksploracyjna analiza zbioru danych – począwszy od przypadków medycznych, aż po biznesowe cel jest podobny – uzyskać jednorodne grupy i odkryć wzorce, które je charakteryzują (np. klienci aktywni, bierni i bardzo aktywni),
• przygotowanie zbioru danych – głównym celem jest tu szybsze wyszukiwanie informacji poprzez porządkowanie zgromadzonych danych, m.in. w silnikach wyszukiwania dokumentów (przykładem są zbiory tekstów, książek, czy dokumentów w firmach).

Ankieta + konkurs: zdecyduj o przyszłości bloga

Przypominam, że tylko do 28 lutego można wypełniać ankietę dotyczącą przyszłości bloga. Wszystkie osoby, które wypełnią ankietę i zostawią w niej swój adres e-mail (użyję go tylko do identyfikacji i kontaktu ze zwycięzcą konkursu) mogą wygrać arcyciekawą książkę: "Praca głęboka" Cala Newporta. Więcej informacji o konkursie znajdziesz w tym wpisie. :)

UPDATE: Konkurs zakończony. Gratulacje dla Izy! :)

Cel grupowania

Celem grupowania jest podział zbioru obiektów na grupy podobnych obiektów (o podobnych wartościach atrybutów). Można zatem założyć, że powstałe grupy powinny być jak najbardziej „jednorodne”.

W zależności od tego, na jaką metodę grupowania się zdecydujemy, liczba grup powstałych grup może zostać przez nas określona a priori jako parametr wejściowy, podczas budowania modelu.

Obiekty, które w przestrzeni wielowymiarowej są położone blisko siebie, powinny być przypisane do tej samej grupy (klastra/segmentu). Obiekty, które są położone daleko od siebie w przestrzeni wielowymiarowej, powinny być przypisane do różnych grup (ew. powinny zostać uznane za obserwacje nietypowe).

Możliwość odkrywania obserwacji nietypowych jest świetną właściwością niektórych algorytmów grupujących. Dzięki temu wspomniane algorytmy mają co najmniej dwa dodatkowe zastosowania:

• w problemach detekcji anomalii, w których nie mamy podanej zmiennej celu, np. przy wykrywaniu nietypowych zachowań klientów banku,
• w problemach klasyfikacji, w których mamy do czynienia z rzadkimi zjawiskami i liczebność jednej klasy zdecydowanie przeważa nad licznością klasy drugiej – wtedy można potraktować klasę mniej liczną jako swego rodzaju anomalię, np. przy wykrywaniu oszustw finansowych.

Podział algorytmów grupujących

Najprostszy podział algorytmów grupujących możemy dokonać, uwzględniając przyjętą przez nie metodę grupowania. Do podstawowych metod grupowania zaliczamy:

1. Grupowanie hierarchiczne – metody łączące intuicyjne i łatwo interpretowalne algorytmy grupowania. Możemy ją podzielić ze względu na podejście do budowy grup: wstępujące lub zstępujące (działanie algorytmu jest kończone po napotkaniu kryterium stopu, np. średnicy grupy, lub liczby grup).
2. Grupowanie gęstościowe – metody oparte o zdefiniowany, maksymalny zbiór gęstościowo połączonych punktów. Algorytmy tej grupy są używane również do wykrywania anomalii.
3. Grupowanie iteracyjno-optymalizacyjne – do tej grupy zaliczane są algorytmy, które wstępnie wykonują podział na zadaną liczbę klas, a następnie w sposób iteracyjny poszczególne obserwacje migrują pomiędzy klasami celem zapewnienia możliwie najmniejszej wariancji (a największej jednorodności) wewnątrz danej klasy.

Wszystkie metody wraz z podaniem przykładowych algorytmów i ich implementacji w Python rozwinę w kolejnych wpisach.

Cechy dobrego grupowania

Skoro nie ma zmiennej celu, to być może zastanawiasz się jak poznać, że proces grupowania dał zadowalające rezultaty. Otóż jak już wspomniałem, cechą dobrego grupowania jest wysokie podobieństwo obiektów znajdujących się w tej samej grupie, natomiast niskie podobieństwo obiektów z różnych grup.

By zweryfikować jakość procesu grupowania, można zatem mierzyć podobieństwo (jako miarę odległości) pomiędzy poszczególnymi obserwacjami w danej grupie. Im większe podobieństwo pomiędzy obserwacjami, tym większy finalny wynik.

Do dwóch podstawowych (i moim skromnym zdaniem najbardziej intuicyjnych) miar jakości grupowania można zaliczyć:

• wskaźnik czystości grup (ang. purity score),
• wskaźnik sylwetkowy grup (ang. silhouette index).

Wymienione miary opiszę w kolejnych wpisach, wraz z podaniem konkretnych przykładów.

Podsumowanie

W kolejnych wpisach podzielę poszczególne algorytmy na grupy i opiszę ich zastosowanie. Nie obejdzie się również bez projektu pokazującego praktyczne zastosowanie algorytmów segmentacji.

Jeśli masz jakieś pytania, to proszę podziel się nimi w komentarzu pod wpisem – zapraszam do dyskusji. Jeśli artykuł przypadł Ci do gustu, to proszę, podziel się nim w mediach społecznościowych ze swoimi znajomymi. Będę bardzo wdzięczny. 🙂

photo: Pixabay.com (vvaniasantoss)