Jak działają najpopularniejsze algorytmy dostępne w narzędziu SPSS Modeler?

Start / Blog / Jak działają najpopularniejsze algorytmy dostępne w narzędziu SPSS Modeler?

W związku z tym, że analitycy korzystający z narzędzi powinni wiedzieć, jak działają algorytmy w nich zaimplementowane, postanowiłem w niniejszym wpisie opisać logikę działania 7 najpopularniejszych algorytmów dostępnych w narzędziu IBM SPSS Modeler.

Obraz1

 

1. Drzewa decyzyjne

Obraz2

Drzewa decyzyjne należą do najpopularniejszych klasyfikatorów. Celem klasyfikatorów jest przypisanie obserwacji do jednej ze zdefiniowanych klas (grup), np. kobieta lub mężczyzna. Zmienną, która identyfikuje klasę nazywamy zmienną celu. Aby drzewo decyzyjne zdolne było do rozróżniania, do której klasy należy dana obserwacja podlega ono procesowi uczenia na danych historycznych, tj. na danych najczęściej dotyczących przeszłości.

Drzewa decyzyjne uczone są z nadzorem, co oznacza, że w danych wykorzystywanych do uczenia muszą być zawarte zmienne opisujące daną obserwacje (tzw. zmienne objaśniające) oraz wartości zmiennej celu. Następnie podczas uczenia, algorytm sprawdza, jak wartości zmiennych objaśniających wpływają na fakt przynależności do zadanej klasy. W efekcie otrzymujemy reguły, które determinują przynależność obserwacji do danej grupy. W przypadku drzew decyzyjnych, reguły te można zwizualizować na acyklicznym, skierowanym grafie, zwanym drzewem decyzyjnym.

Obraz3

 

Kolejność zmiennych w drzewie wynika z ‘siły’, z jaką rozdzielają one obserwacje na klasy. Im większa moc dyskryminacyjna zmiennej, tym wyżej znajdzie się ona na grafie. W każdym węźle drzewa widzimy udział jednostek należącej do każdej z klas. Wartość ta wyliczana jest na podstawie danych historycznych i możemy ją interpretować, jako prawdopodobieństwo przynależności do klasy.

Jak długo budujemy drzewo? Do samego dołu lub do osiągnięcia kryterium stopu, które najczęściej definiowane jest przez minimalną liczbę rekordów w węźle lub maksymalną liczbę poziomów drzewa. Często po zbudowaniu pełnego drzewa, jest ono następnie skracane. Proces ten nazywa się przycinaniem drzewa i ma on zapobiec przeuczeniu modelu, czyli zbyt mocnemu dostosowaniu się reguł do konkretnych danych uczących.

W narzędziu IBM SPSS dostępne są 4 różne algorytmy budowy drzew decyzyjnych: C5.0, CHAID, QUEST, C&RT. Różnice między nimi wynikają m.in. z podejścia do braków danych, liczby podziałów w ramach jednej gałęzi oraz obsługi zmiennych ciągłych.  Zainteresowanych odsyłam do poniższej tabeli:

Obraz4

 

Drzewa decyzyjne bardzo dobrze nadają się do rozwiązywania problemów, w których oprócz scoru  (przewidywane prawdopodobieństwo przynależności do klasy) analityk potrzebuje poznać dokładną regułę, która go determinuje. Przykładem takich problemów może być przewidywanie awarii maszyn i urządzeń. Dodatkowo, drzewa decyzyjne mogą być wykorzystywane do objaśniania reguł stworzonych przez inne algorytmy (np. sieci neuronowe) lub jako metoda doboru zmiennych do modelu. Wadę drzew decyzyjnych  stanowi, wynikający z ortogonalności podziałów, brak ciągłości scoru. Drzewa decyzyjne stanowią często pierwszą z metod używanych przy modelowaniu problemów klasyfikacyjnych.

 

2. Metoda wektorów nośnych

Obraz5

Pozostając przy uczonych z nadzorem klasyfikatorach, kolejnym popularnym algorytmem, jest metoda wektorów nośnych. Idea metody sprowadza się do wyznaczenia hiperpłaszczyzny dzielącej przestrzeń obserwacji na dwie części.

Gdyby nasz klient opisany był przez dwie cechy (dwie zmienne objaśniające), np. wzrost i wagę to hiperpłaszczyzna zostałaby sprowadzona do prostej o równaniu y=ax+b, gdzie x i y oznaczają wzrost i wagę. Gdybyśmy przewidywali płeć osoby (zmienna celu), to parametry a i b krzywej zostałyby tak dobrane, aby po jednej stronie krzywej byli głównie mężczyźni, a po drugiej głównie kobiety.

Obraz12

W przypadku gdy granica między klasami nie jest liniowa algorytm dokonuje transformacji, która ma celu przekształcenie problemu do problemu liniowego. Transformacja ta wykonywana jest przy wykorzystaniu funkcji jądrowych.

Metoda wektorów nośnych jest często stosowana do bardziej złożonych problemów klasyfikacyjnych, dla których dokładność predykcji jest ważniejsza od czytelności reguły klasyfikacyjnej. Przykładem takich problemów są modele budowane w CRM-ie analitycznym (x-sell, up-sell, churn).

 

3. Naiwny klasyfikator Bayesa

Obraz6

Klasyfikator, którego nazwa wzięła się brytyjskiego matematyka Thomasa Bayesa, to kolejny przykład algorytmu uczonego z nadzorem. Idea działania algorytmu jest bardzo prosta,  prawdopodobieństwo przynależności obserwacji do danej klasy wyznaczane jest na podstawie wzoru na prawdopodobieństwo warunkowe dla zdarzeń niezależnych.

Zobaczmy, jak działa algorytm w praktyce. Załóżmy zbiór klientów banku. Wśród klientów banku 20% klientów odchodzi, a 80% klientów zostaje. Wśród odchodzących 10% stanowią kobiety, a 8% osoby z obszarów miejskich. Ile wynosi zatem prawdopodobieństwo odejścia dla kobiety z miasta? 10%*8%*20% = 0,16%.

Prawdopodobieństwa a-priori wyznaczane są na podstawie zbioru treningowego. Dlaczego klasyfikator nazywany jest naiwnym? Bo naiwnie zakłada, że zmienne użyte do opisu obserwacji są niezależne.

Klasyfikator Bayesa bardzo dobrze nadaje się do problemów o bardzo dużej liczbie zmiennych wejściowych.

 

4.  Metoda k-najbliższych sąsiadów

Obraz7

Metoda k-najbliższych sąsiadów jest bardzo prostym klasyfikatorem uczonym z nadzorem. W przeciwieństwie jednak do opisywanych powyżej metod jest to tzw. lazy learner, co oznacza, że jedyną czynnością wykonywaną podczas treningu algorytmu jest przechowywanie obserwacji treningowych na potrzeby ich przyszłego użycia.

Jak działa algorytm? Dla każdej nowej obserwacji wyznaczana jest zadana (k) liczba najbliższych sąsiadów. Do wyznaczenia najbliższych sąsiadów wykorzystać możemy różne metryki np. metrykę euklidesową (o której piszę więcej w części poświęconej metodzie k-średnich). Następnie sąsiedzi ‘głosują’, do której klasy powinna zostać zaklasyfikowana nowa obserwacja.

Przykład: Chcemy określić płeć naszej obserwacji korzystając z metody k-najbliższych sąsiadów, gdzie k=5. Jeżeli wśród najbliższych sąsiadów mamy 4 kobiety i 1 mężczyznę, to nasza obserwacja zostanie zaklasyfikowana jako kobieta.

W bardziej zaawansowanym przypadku, głosowanie może być ważone odległością. W przypadku ciągłych zmiennych celu wyznaczana jest po prostu średnia (ważona).

Metoda k-najbliższych sąsiadów idealnie nadaje się do rozwiązywania problemów w oparciu o obserwacje referencyjne. Przykładem takich zagadnień są przede wszystkim systemy rekomendacyjne, w których użytkownik dostaje rekomendacje wynikające z zachowania jednostek do niego podobnych. Przykład bardziej opisowy: jeżeli użytkownik obejrzał filmy Rocky, Rambo i Dynastia, to jego najbliższym sąsiadem będzie użytkownik, który również obejrzał te filmy. Jeśli użytkownik drugi obejrzał dodatkowo Titanica, to ten właśnie film zostanie zarekomendowany użytkownikowi pierwszemu.

 

5. Metoda k-średnich

Obraz8

Metoda k-średnich reprezentuje metody analizy skupień zwane również grupowaniem lub klasteryzacją. W przeciwieństwie do algorytmów opisanych wcześniej algorytmy analizy skupień uczone są bez nadzoru, co sprowadza się do tego, że w procesie uczenia nie jest wykorzystywana zmienna celu.

Metody analizy skupień służą do podziału zbioru obserwacji na podzbiory (segmenty). Podział dokonywany jest w taki sposób, aby obserwacje najbardziej do siebie podobne znajdowały się w jednym segmencie oraz żeby różnice między segmentami było możliwie jak największe.

W metodzie k-średnich użytkownik sam określa liczbę segmentów, które mają być zbudowane przez algorytm. Oczywiście, istnieją różne modyfikacje metody k-średnich w których liczba segmentów jest dobierana automatycznie np. Dwustopniowe Grupowanie. Można też, w celu optymalizacji liczby skupień posłużyć się miarą Silhouette.

Pozostaje zatem ostatnie pytanie, czyli jak nauczyć algorytm nie posiadając zmiennej celu? W tym przypadku z pomocą przychodzi nam metryka euklidesowa i wyznaczana przez nią odległość punktów w przestrzeni.  Gdyby nasze obserwacje opisane były przez dwie cechy, np. wzrost i waga, to odległość między obserwacjami byłaby równa długości przeciwprostokątnej trójkąta, którego przyprostokątne wyznaczane są jako odpowiednio różnica wagi i wzrostu między obserwacjami. W tym przypadku odległość można by  wyliczyć korzystając z twierdzenia pitagorasa.

Jak więc wygląda sam proces uczenia? W pierwszym kroku algorytm losowo wybiera spośród dostępnych obserwacji zadaną liczbę centrów skupień np. 5. W drugim kroku każda pozostała  obserwacja klasyfikowana jest do skupienia, to którego centrum na najbliżej. W trzecim kroku następuje zmiana środków segmentów, na obserwacje centralne w ramach segmentów wyznaczonych w kroku drugim. Następnie podobnie jak w kroku drugim wszystkie obserwacje ponownie klasyfikowane są do skupień, do centrów których mają najbliżej. Kroki 3 i 4 powtarzane są do osiągnięcia stabilności lub do wyczerpania maksymalnej liczby iteracji.

Algorytm k-średnich m.in. ze względu na swoja prostotę jest najpopularniejszym algorytmem wykorzystywanym do budowy modeli segmentacyjnych – segmentacji klientów, segmentacji punktów sprzedaży,  segmentacji odbiorców..

 

6. Algorytm Apriori

Obraz9

Algorytm Apriori wykorzystywany jest do analizy asocjacji zwanej popularnie analizą koszykową. Schemat działania algorytmu jest bardzo prosty, przeszukuje on zbiór obserwacji szukając reguł typu jeżeli poprzednik, to następnik.

W celu zobrazowania metody posłużę się następującym przykładem. Wyobraźmy sobie, że jesteśmy analitykami zatrudnionymi do analizy zakupów klientów w pewnym sklepie spożywczym. Analizujemy paragony i sprawdzamy, ilu klientów, którzy kupili frytki, kupiło też ketchup. Jeżeli z 10 klientów, którzy kupili frytki 4 kupiło ketchup to prawdopodobieństwo warunkowe kupna ketchupu pod warunkiem kupna frytek wynosi 40%, a w języku analizy koszykowej, wyliczona w ten sposób wartość nazywana jest ufnością. Jeżeli standardowo 5% klientów kupuje ketchup to lift (wzrost) naszej reguły wynosi 40% / 5%=8. Zaprezentowana reguła znalazła zastosowanie dla 4 z 200 klientów, czyli jej wsparcie wynosi 2%.

Liczba stworzonych przez algorytmy reguł zależy od ustawionych przez użytkownika na starcie minimalnych poziomów wparcia i ufności.

Analiza koszykowa wykorzystywana jest przede wszystkim w branży handlowej do analizy paragonów lub faktur. Wnioski  tej analizy wykorzystywane są do tworzenia ofert sprzedaży wiązanej (x-sell), zarządzania cenami, a także planowania rozłożenia asortymentu w sklepach. Dodatkowo, algorytmy analizy asocjacji znajdują zastosowanie w mechanizmach rekomendacyjnych.

 

7. Szeregi czasowe – modele ARiMA

Obraz10

Idea szeregów czasowych polega na próbie odwzorowania, jak dane zjawisko np. popyt kształtowało się w przeszłości i na tej podstawie przewidywania, jak kształtować będzie się ono w przyszłości.

W podstawowych modelach szeregów czasowych nie uwzględniamy zmiennych dodatkowych tj. egzogenicznych. Zakładamy, że wartość szeregu czasowego w danym okresie zależy od jego wartości w okresach wcześniejszych. Oczywiście wagi okresów wcześniejszych mogą się zmieniać, np. maleć. Przy budowie szeregu czasowego SPSS w sposób automatyczny uwzględnia sezonowość.

Jak SPSS wybiera najlepszy model? Minimalizując wartość miary MAE – średni błąd prognozy, czyli średnią odległość między szeregiem rzeczywistym, a szeregiem wyznaczonym przez SPSS, który wykorzystywany będzie do prognozowania. Oczywiście miara MAE może być jedynie wyznaczona dla okresu historycznego. Na poniższym rysunku MAE to średnia odległość między linią niebieską i zieloną.

Obraz11

Jak poprawić jakość modelu? Dokładając do zbioru treningowego zmienne binarne (zerojedynkowe), które reprezentować będą zdarzenia nadzwyczajne tj. święta, promocje itp. Ważne, żeby dla każdego typu zjawisk powstała osobna zmienna.

Analiza szeregów czasowych wykorzystywana jest w wielu branżach do prognozowania m.in. popytu i cen.

 

 

Celem powyższego artykułu było przedstawienie logiki działania 7 najpopularniejszych algorytmów z dostępnych w narzędziu IBM SPSS Modeler bez używania wzorów matematycznych. Oczywiście, jest to tylko bardzo mały fragment możliwości analitycznych narzędzia. Czytelników zainteresowanych bardziej szczegółowym wglądem w dostępne algorytmy zachęcam do przeczytania dokumentacji. Na koniec chciałbym jeszcze dodać, że nie ma metody analitycznej, która jest zawsze najlepsza w rozwiązywaniu danej grupy problemów. Dla każdego problemu warto zawsze przetestować kilka dostępnych metod i dopiero na tej podsatwie wybrać najlepszą biorąc pod uwagę skuteczność oraz potencjalne wady i zalety.

 

 

Copyright 1.04.2016 by Jędrzej Traczykowski