Uczenie się maszyn: wykład 9
Odkrywanie zależności w danych

Paweł Cichosz


Date: Semestr zimowy 1997/98

Termin data mining

Termin data mining ostatnio pojawia się coraz częściej nie tylko w publikacjach naukowych, lecz także w marketingowych materiałach różnych firm oferujących oprogramowanie i usługi w dziedzinie analizy danych. W praktyce dokładne znaczenie wiązane z tym terminem bywa różne, ponieważ wyraźnie opłaca się go używać, nawet jeśli jest to tylko w niewielkim stopniu uzasadnione. Funkcjonuje również inny termin, knowledge discovery in databases. Niektórzy rozróżniają znaczenie tych dwóch terminów, a zwłaszcza ich zakresy znaczeniowe: jeden z nich jest szerszy, chociaż trudno bez dokładnych studiów powiedzieć który. My przyjmiemy tutaj, że w obu przypadkach mowa jest o odkrywaniu zależności występujących w dużych zbiorach danych, zazwyczaj przechowywanych w bazach danych (obecnie najczęściej relacyjnych).

W przypadku relacyjnych baz danych można przyjąć, że zależności poszukuje się w tabeli zawierającej wiele rekordów, z których każdy stanowi zestaw wartości pewnej liczby atrybutów o różnych typach. Zależności można uznać za interesujące, jeśli dotyczą atrybutów ważnych dla posiadacza danych. Są one natomiast użyteczne, jeśli charakteryzują się:

Uczenie się maszyn a odkrycia

Odkrywanie wiedzy w bazach danych pozostaje w bardzo bliskim związku z uczeniem się maszyn. Ogólnie można przyjąć, że metody data mining są oparte przede wszystkim na statystycznych metodach analizy danych oraz na metodach uczenia się na podstawie przykładów. Te ostatnie zresztą, jak kilkakrotnie widzieliśmy, same odwołują się czasem do narzędzi ze statystyki.

Ograniczenia metod statystycznych

Statystyczne metody analizy danych są w większości znane od wielu lat i stosowane z powodzeniem do rozwiązywania wielu praktycznych problemów w różnych obszarach zastosowań, lecz używane w tradycyjny sposób napotykają na pewne ograniczenia. W uproszczeniu, pozwalają one na wykrywanie korelacji między różnymi zjawiskami (np. wartościami różnych atrybutów w bazie danych), wykrywanie występujących trendów, dopasowywanie równania do zbioru punktów pomiarowych, wykrywanie skupień itd., ale nie generują wyjaśnień tych zależności i ich opisów w abstrakcyjnej, symbolicznej postaci, użytecznej do wyciągania wniosków. Aby odkrywane za pomocą analizy statystycznej zależności były w pełni użyteczne, konieczny jest najczęściej daleko idący udział doświadczonego użytkownika przy ich stosowaniu i interpretacji. Można natomiast powiedzieć, że większość metod uczenia się ma na celu odkrycie (nauczenie się) zależności w sposób maksymalnie zautomatyzowany i utworzenie ich opisu, który jest łatwy do interpretacji i pozwala na wnioskowanie.

Stosowanie algorytmów uczenia się

O omawianych przez nas dotychczas algorytmach indukcyjnego uczenia się na podstawie przykładów (np. ID3, AQ, CN2, COBWEB itd.) można powiedzieć nie popełniając żadnego nadużycia, że są metodami odkrywania zależności w bazach danych. Jednak stosując którykolwiek z tych algorytmów do odkrywania wiedzy w bazach danych zakładamy natychmiast, że zbiór trenujący jest bardzo duży: liczba rekordów liczona jest na ogół w tysiącach albo milionach. O ile algorytmy te nie mogą uczyć się użytecznej wiedzy przy zbyt małej ilości danych, duża ilość danych stwarza inne problemy.

Koszt obliczeniowy wszystkich metod zależy oczywiście od ilości danych, na których operują, i w niektórych przypadkach może okazać się trudny do akceptacji. Wówczas można wziąć pod uwagę przeprowadzenie redukcji rozmiaru dostępnego zbioru danych. Należy to oczywiście uczynić w sposób, który z dużym prawdopodobieństwem pozostawi w zredukowanych danych interesujące i użyteczne zależności występujące w oryginalnym zbiorze danych. Redukcja taka może mieć postać

Inny problem wiąże się z tym, że w przypadku bardzo dużej ilości przykładów może być niemożliwe znalezienie hipotezy, która przy dostatecznie dużej dokładności byłaby na tyle prosta, aby jej interpretacja przez człowieka prowadziła do interesujących wniosków. Lepszym pomysłem może być poszukiwanie hipotez o ograniczonym zakresie -- zachodzących dla wyznaczonych w systematyczny sposób fragmentów bazy danych.

Z całą pewnością algorytmy stosowane do odkrywania wiedzy w bazach danych muszą sobie radzić z ich zaszumieniem i niekompletością. W pierwszym przypadku oznacza to stosowanie różnych technik zapobiegających nadmiernemu dopasowaniu do przypadkowych (nieistotnych) danych, a w drugim np. wypełnianie w odpowiedni sposób nieznanych wartości atrybutów.

Przy uwzględnieniu wszystkich tych praktycznie istotnych problemów do odkrywania zależności w bazach danych mogą być i są rzeczywiście stosowane metody uczenia się już przez nas poznane. W ramach tego wykładu krótko omówimy dwie inne metody dokonywania odkryć:

Odkrycia za pomocą tablic kontyngencji

Tablice kontyngencji są znaną ze statystyki metodą prezentacji zależności występujących pomiędzy wartościami dwóch (w podstawowym przypadku) zmiennych losowych, którymi przy dokonywaniu odkryć są atrybuty. W przypadku dwóch atrybutów $ a_1$ i $ a_2$ o niewielkiej liczbie wartości dyskretnych tablica kontyngencji ma wiersze odpowiadające wszystkim wartościom atrybutu $ a_1$ (ze zbioru $ A_1$) i kolumny odpowiadające wszystkim wartościom atrybutu $ a_2$ (ze zbioru $ A_2$). Element tablicy na przecięciu wiersza odpowiadającego wartości $ v_1\in A_1$ i kolumny odpowiadającej wartości $ v_2\in A_2$ jest liczbą przykładów (rekordów w rozpatrywanej tabeli), dla których $ a_1$ ma wartość $ v_1$ i $ a_2$ ma wartość $ v_2$.

W przypadku atrybutów ciągłych ich wartości są dyskretyzowane. W najprostszym przypadku, gdy dla obu atrybutów dyskretyzacja dzieli zakres wartości na dwa przedziały (małe i duże wartości), tablica kontyngencji jest czteroelementową tablicą $ 2\times 2$. Dla atrybutów dyskretnych o dużej liczbie wartości wstępnie przeprowadza się na ogół agregację tych wartości (rodzaj konstruktywnej indukcji).

Znanym systemem odkrywania zależności w danych wykorzystującym tablice kontyngencji jest FortyNiner (49er) Żytkowa i Zembowicza, na którym luźno oparta jest poniższa dyskusja.

Wzorce w tablicach kontyngencji

O występowaniu wzorców w tablicach kontyngencji mówi się, jeśli obserwowany w niej rozkład wartości atrybutów wskazuje na występującą między nimi zależność. Siła wzorca jest tym większa, im mniej rozkład ten przypomina przypadkowy. Do weryfikowania istnienia zależności i mierzenia ich siły mogą być wykorzystane różne testy statystyczne, w najprostszym przypadku statystyka $ \chi^2$.

Niech w tablicy kontyngencji dla atrybutów $ a_1$ i $ a_2$ symbol $ n_{v_1v_2}$ oznacza liczbę na pozycji odpowiadającej wartości $ v_1$ atrybutu $ a_1$ i wartości $ v_2$ atrybutu $ a_2$. Z kolei przez $ e_{v_1v_2}$ oznaczymy oczekiwaną liczbę przykładów (rekordów) o wartości $ v_1$ atrybutu $ a_1$ i wartości $ v_2$ atrybutu $ a_2$ przy założeniu niezależności tych dwóch atrybutów. Można oszacować:

$\displaystyle e_{v_1v_2} = \frac{n_{a_1,v_1}\cdot n_{a_2,v_2}}{n}, $

gdzie, przyjmując, że wiersze i kolumny tablicy odpowiadają wartościom obu atrybutów ze zbiorów $ A_1$ i $ A_2$,

$\displaystyle n_{a_1,v_1} ={}$ $\displaystyle \sum_{v\in A_2}n_{v_1v},$    
$\displaystyle n_{a_2,v_2} ={}$ $\displaystyle \sum_{v\in A_1}n_{vv_2},$    
$\displaystyle n ={}$ $\displaystyle \sum_{v_1\in A_1}\sum_{v_2\in A_2} n_{v_1v_2}.$    

Wówczas wartość statystyki $ \chi^2$ oblicza się według wzoru:

$\displaystyle \chi^2 = \sum_{v_1\in A_1}\sum_{v_2\in A_2} \frac{(n_{v_1v_2}-e_{v_1v_2})^2}{e_{v_1v_2}}. $

Statystyka ta ma w przybliżeniu rozkład $ \chi^2$ o $ (\vert A_1\vert-1)\cdot(\vert A_2\vert-1)$ stopniach swobody. Korzystając z tablic statystycznych dla znanej wartości $ \chi^2$ i liczby stopni swobody można określić prawdopodobieństwo tego, że tablica kontyngencji reprezentuje tylko przypadkowy rozkład wartości atrybutów. Dla żądanego poziomu istotności i danej liczby stopniu swobody można z kolei znaleźć progową wartość statystyki, której przekroczenie oznacza statystycznie istotną zależność.

Na podstawie istotnych statystycznie wzorców w tablicach kontyngencji można prowadzić wnioskowanie, a więc tablica taka jest formą reprezentaci użytecznej wiedzy. W szczególności, na podstawie znajomości wartości jednego atrybutu można oszacować rozkład prawdopodobieństwa wartości drugiego atrybutu. W niektórych przypadkach bardzo silnych wzorców tablice można przekształcać do postaci reguł.

Strategia poszukiwania wzorców

Trudno na ogół oczekiwać, aby istotne zależności zachodziły dla całej, często bardzo dużej bazy danych. W związku z tym metody odkrywania zależności tego typu łączą analizę statystyczną tablic kontyngencji z pewnymi strategiami wybierania dekompozycji bazy danych na fragmenty, w których mogą występować istotne wzorce. Dekompozycja taka polegać może na:

Selekcja może być poprzedzona agregacją wartości atrybutów, według których ma być dokonywana (rodzaj konstruktywnej indukcji). Rozpoczynając od pełnej tabeli w każdym kroku, o ile nie zostaną znalezione odpowiedniej jakości wzorce, dokonuje się dekompozycji i ponawia próbę.

Naszkicowany proces ma charakter przeszukiwania przestrzeni możliwych tablic kontyngencji dla danego początkowo zbioru rekordów i atrybutów w poszukiwaniu takich, dla których występują dostatecznie istotne wzorce. W przypadku systemu 49er jest to wyczerpujące przeszukiwanie w głąb, które w można opisać jak w tablicy 1. Jest to przybliżona i silnie uproszczona rekonstrukcja algorytmu zaproponowanego przez twórców systemu, którzy opisali go w sposób dość umiarkowanie precyzyjny. Przedstawiony tu algorytm zakłada, że wstępnie za pomocą jakiejś formy konstruktywnej indukcji dokonano dyskretyzacji lub agregacji wartości atrybutów tam, gdzie było to konieczne.


Tablica: Uproszczony algorytm poszukiwania wzorców w tablicach kontyngencji przez system 49er.
$ \textit{szukaj\_wzorców}(P,F,R)$:
  1. jeśli $ \vert F\vert<2$ to
    powrót;
  2. dla każdej pary atrybutów $ a_1,a_2\in F$ dla których dotychczas nie znaleziono wzorca wykonaj
    1. skonstruuj tablicę kontyngencji $ t$ dla $ a_1$ i $ a_2$ na podstawie danych z $ P$;
    2. jeśli tablica $ t$ zawiera statystycznie istotny wzorzec to zachowaj $ \langle t,a_1,a_2,R\rangle$;
  3. dla każdego $ a\in F$ wykonaj
    dla każdego $ v\in A$ wykonaj
    $ \textit{szukaj\_wzorców}(P_{av}, F-\{a\},R\cup\{a=v\})$.


Argumentem procedury $ \textit{szukaj\_wzorców}$ jest zbiór przykładów (rekordów) $ P$ oraz zbiór atrybutów $ F$, które są uwzględniane. Jest on podzbiorem całego zbioru atrybutów  $ \mathbb{A}$, za pomocą których opisywane są rekordy w danej początkowo tabeli. Trzecim argumentem jest zbiór warunków (zakresów) dla wartości atrybutów ze zbioru $ \mathbb{A}-F$. Przyjmujemy, że z danej początkowo tabeli wybierane są tylko rekordy spełniające wszystkie warunki z $ R$ i następnie rzutowane na zbiór atrybutów $ F$ (tzn. pomijane są wartości pozostałych atrybutów), co daje w wyniku zbiór $ P$, dla którego tworzona jest tablica kontyngencji. Przyjmujemy też, że dla atrybutu $ a\in F$ i pewnej jego wartości $ v\in A$ zbiór $ P_{av}$ jest wynikiem zastosowania do $ P$ selekcji (z warunkiem $ a=v$) i następnie rzutowania na $ F-\{a\}$. Przy znalezieniu na dowolnym poziomie przeszukiwania zadowalającego wzorca jest on zapamiętywany wraz z atrybutami, których dotyczy, oraz warunkami (zakresami) dla wartości pozostałych atrybutów. Przy pierwszym wywołaniu procedury mamy oczywiście $ P=T$ (cały zbiór rekordów w tabeli) i $ F=\mathbb{A}$ (zbiór wszystkich atrybutów) oraz $ R=\emptyset$.

W praktyce proces poszukiwania wzorców jest często wspomagany przez użytkownika, który może określić interesujące go atrybuty, dla których mają być znalezione wzorce, lub atrybuty, według których ma następować podział zbioru danych na podzbiory przy schodzeniu w głąb drzewa przeszukiwania.

Odkrywanie równań

W przypadku atrybutów o wartościach ciągłych można podjąć próbę opisania zależności między nimi za pomocą równania. Tego typu zależność, o ile uda się ją znaleźć, jest na ogół bardzo interesująca i przydatna. Równania o odpowiednio dużym zakresie stosowalności i dużej dokładności mają znakomitą wartość predykcyjną i są stosunkowo łatwe do interpretacji. Ten rodzaj odkryć określa się niekiedy jako odkrycia naukowe (scientific discovery), traktując równania jako poszukiwane prawa opisujące dane empiryczne.

Podobnie jak w przypadku wzorców w tablicach kontyngencji, często użyteczne równania zachodzą tylko dla fragmentów bazy danych. Omawiane dalej metody odkrywania równań stosowane są więc często w ramach ogólnego schematu kolejnych dekompozycji zbioru danych podobnego do przedstawionego wcześniej algorytmu poszukiwania wzorców. Uruchomienie jednej z tych metod poprzedzane jest testem statystycznym mającym określić, czy prawdopodobne jest istnienie zależności funkcyjnej.

Mówiąc o równaniach odchodzimy od naszej zwyczajowej notacji i terminologii i nazywamy atrybuty zmiennymi oraz oznaczamy je przez litery $ x$, $ y$, itd. Poniżej przedstawiamy kilka metod odkrywania równań wykorzystywanych w różnych wersjach znanego systemu odkryć naukowych BACON.

Odkrywanie prostych praw numerycznych

Najprostszy rodzaj praw, jakich odkrywanie moglibyśmy chcieć zautomatyzować, to funkcyjna zależność dwóch numerycznych zmiennych. Mając zbiór pochodzących z obserwacji (pomiarów) par wartości $ \langle x_i,y_i\rangle$, chcemy znaleźć funkcję $ f$ taką, że $ y=f(x)$ opisuje te dane maksymalnie dokładnie. Istniejące metody analityczne rozwiązywania tego problemu (regresja) zakładają pewne szczególne proste postaci funkcji $ f$ (np. funkcja liniowa). Poniżej omawiamy kilka heurystyk, które mogą być wykorzystane do znajdowania tego typu prostych zależności dla szerszego spektrum funkcji $ f$.

Wykrywanie trendów i stałych

Jedną z najprostszych heurystyk jest wykrywanie trendów i stałych. Jest to właściwie zestaw czterech następujących heurystycznych reguł:

  1. jeśli zmienna $ y$ ma wartość $ v$ w pewnej liczbie przypadków, przyjmij, że $ y$ ma zawsze wartość $ v$,
  2. jeśli zmienne $ x$ i $ y$ są liniowo zależne z pochyleniem $ a$ i przesunięciem $ b$ ($ y=ax+b$) w pewnej liczbie przypadków, to przyjmij, że ten związek zachodzi zawsze,
  3. jeśli $ y$ zmniejsza się przy zwiększaniu się $ x$ oraz $ x$ i $ y$ nie są zależne liniowo, utwórz nową zmienną $ t=xy$,
  4. jeśli $ y$ zwiększa się przy zwiększaniu $ x$ oraz $ x$ i $ y$ nie są zależne liniowo, utwórz nową zmienną $ t=x/y$.
Pierwsze dwie z powyższych reguł służą do wykrywania stałych wartości zmiennych oraz zależności liniowych. Obie z nich bezpośrednio prowadzą do sformułowania prawa. Jak długo żadna z nich nie daje się zastosować, tworzone są za pomocą pozostałych dwóch reguł nowe zmienne, do których ponawia się rekurencyjnie próbę zastosowania którejś z reguł. Dwie ostatnie reguły w podanej postaci stosują się tylko do zmiennych o jednakowych znakach. Modyfikacja dla zmiennych o przeciwnych znakach jest oczywista.

Przedstawione heurystyki są niezwykle proste, chociaż pozwalają na odkrycie w efektywny sposób nietrywialnych praw (np. trzeciego prawa Kepplera). Ich ograniczeniem jest to, że nie pozwalają na odkrycie związków wielomianowych stopnia $ 2$ lub wyższych (np. tak prostego związku jak $ y=ax^2+b$). Nie przewidują one również mechanizmów działania przy zaszumionych danych.

Znajdowanie stałych pochodnych

Bardziej zaawansowaną heurystyką jest znajdowanie stałych pochodnych. Technika ta umożliwia znajdowanie dowolnych wielomianowych zależności pomiędzy parą zmiennych przeszukując w pewien sposób przestrzeń funkcji wielomianowych. Przeszukiwanie to rozpoczyna się od rozważenia możliwych składników o najwyższym stopniu, przez kolejno sprawdzanie składników stałych, liniowych, kwadratowych itd. Obliczane są (metodą różnicową) kolejno odpowiadające im pochodne (zerowego, pierwszego, drugiego rzędu itd.) dopóki nie uzyska się w wyniku stałej wartości pochodnej na dostępnym zbiorze danych. Rząd tej stałej pochodnej i jej wartość dają informację odpowiednio o stopniu i współczynniku najwyższego stopniem wyrazu wielomianu. Wówczas, wprowadzając nową zmienną zależną, ponawia się cały proces w poszukiwaniu wyrazu o niższym stopniu, itd. Ściślej mówiąc, zamiast pochodnej stopnia $ n$ oblicza się jej wartość podzieloną przez $ n!$. Dokładniej opisuje to algorytm podany w tablicy 2. Jego pierwsze dwa argumenty to odpowiednio zmienna zależna i niezależna. Trzeci argument to zbiór danych (wartości zmiennych), w którym odbywa się poszukiwanie. Przyjmujemy, że zbiór ten zawiera początkowo pewną liczbę wartości $ x_i$ zmiennej niezależnej $ x$ i odpowiadających im wartości $ y_i$ zmiennej zależnej $ y$.


Tablica: Algorytm odkrywania równań metodą stałych pochodnych.
$ \textit{znajdź\_równanie}(y,x,P)$
  1. $ y^{(0)}:=y$; $ n:=0$;
  2. jak długo wartości $ y^{(n)}$ nie są stałe w zbiorze $ P$ powtarzaj
    1. $ n:=n+1$;
    2. dla każdego $ i=0,1,\dots$ wykonaj
      $ y^{(n)}_i:=\frac{y^{(n-1)}_{i+1}-y^{(n-1)}_i}{x_{i+n}-x_i}$;
  3. zachowaj w $ w$ stałą wartość $ y^{(n)}$;
  4. jeśli $ n=0$
    zwróć $ w$;
    w przeciwnym przypadku
    1. utwórz zmienną $ t=y-wx^n$;
    2. dodaj do $ P$ wartości $ t_i$ dla $ i=0,1,\dots$;
    3. zwróć $ wx^n+\textit{znajdź\_równanie}(t,x,P)$.


Prosta modyfikacja opisanej metody pozwala na znaczne rozszerzenie klasy funkcji branych pod uwagę przez system. Oprócz analizowania możliwych wielomianowych związków pomiędzy $ x$ i $ y$, system może poszukiwać takich związków między $ x$ i $ y^2$, $ x$ i $ y^3$ itd., a także np. $ x$ i $ \log y$ lub $ x$ i $ \sin y$.

Przedstawiona technika może zostać też zmodyfikowana w celu dopuszczenia zaszumionych danych przez rozluźnienie wymagania, aby pochodne były stałe (zastąpienie go wymaganiem, aby były prawie stałe), np. przez wprowadzenie wielkości maksymalnego błędu względnego i bezwzględnego danych jako parametrów systemu.

Przykład: $ y=3x^2+2x+1$.

Rozważmy zależność $ y=3x^2+2x+1$. Tablica 3 przedstawia przykładowe dane zgodne z tym prawem wraz z wartościami pierwszej i drugiej pochodnej $ y$ (obliczonymi metodą różnicową).


Tablica: Przykładowe dane dla metody stałych pochodnych.
$ x$ $ y$ $ y'$ $ \frac{1}{2}y''$
$ 1$ $ 6$ $ (34-6)/(3-1)=14$ $ (29-14)/(6-1)=3$
$ 3$ $ 34$ $ (121-34)/(6-3)=29$ $ (50-29)/(10-3)=3$
$ 6$ $ 121$ $ (321-121)/(10-6)=50$ $ (77-50)/(15-6)=3$
$ 10$ $ 321$ $ (706-321)/(15-10)=77$  
$ 15$ $ 706$    


Jak widać, (połowy) wartości drugiej pochodnej są stałe i równe $ 3$, co pozwala systemowi wywnioskować, że funkcja wiążąca $ x$ i $ y$ zawiera składnik $ x^2$ ze współczynnikiem $ 3$. Wiedząc to, system może powtórzyć powyższą procedurę zastępując $ y$ przez nową zmienną równą $ y-3x^2$, itd.

Zachłanne przeszukiwanie przestrzeni parametrów

W poprzednich podejściach system dokonujący odkryć stara się określić wyrażenia opisujące związki pomiędzy obserwowanymi zmiennymi wyłącznie na podstawie dostępnych danych. Jeśli dane te są obarczone nawet niewielkim błędem, może to doprowadzić do poważnych problemów. Alternatywne podejście polega na dostarczeniu systemowi przez użytkownika szablonów praw, które należy wziąć pod uwagę. Przykładowo, system może otrzymać wskazówkę, aby poszukiwać związków postaci $ y=ax^2+bx+c$ oraz $ \sin y=ax+b$.

W oparciu o dostarczone mu szablony (standardowy zestaw szablonów może być wbudowany do systemu) system rozpoczyna poszukiwanie wartości parametrów tych szablonów, dla których uzyskuje się związki najlepiej opisujące dane. Poszukiwanie to rozpoczyna się od skonkretyzowania szablonów przez przypisanie ich parametrom różnych kombinacji wartości $ -1$, 0 i $ 1$. W ten sposób generuje się pewną liczbę stanów początkowych, z których każdy odpowiada pewnej konkretyzacji szablonu. Proces przeszukiwania opisuje szkicowy algorytm podany w tabeli 4.


Tablica: Uproszczony algorytm przeszukiwania przestrzeni parametrów przy dopasowywaniu danych do szablonów równań.
  1. wygeneruj zbiór wyrażeń początkowych dla parametrów ze zbioru $ \{-1,0,1\}$;
  2. $ \delta:=0.5$;
  3. powtarzaj
    1. oceń jakość każdego wyrażenia obliczając korelację danych wartości zmiennej zależnej $ y$ i jej wartości obliczonych za pomocą tego wyrażenia;
    2. pozostaw co najwyżej $ m$ najlepszych wyrażeń (o najwyższej korelacji);
    3. dla każdego wyrażenia utwórz nowe wyrażenia uzyskane przez dodanie/odjęcie do/od jednego lub więcej jego parametrów $ \delta$;
    4. $ \delta:=0.5\delta$;
    jak długo $ \delta>\epsilon$.


Metoda ta jest stosunkowo odporna na błędy danych, ponieważ używa ich do testowania hipotez, a nie do ich generowania.

Odkrywanie złożonych praw numerycznych

Dotychczas omawiane były metody znajdowanania praw opisujących związki zachodzące pomiędzy wartościami dwóch zmienych. Związki łączące większą liczbę zmiennych powodują szereg dodatkowych komplikacji i w związku z tym wymagają innych metod.

Przy odkrywaniu zależności wielu zmiennych możemy mieć do czynienia z dwoma zasadniczo róznymi sytuacjami. Albo system może prowadzić aktywne eksperymenty, co pozwala mu stosować technikę zmieniania jednej zmiennej niezależnej na raz (przy określonych stałych wartościach innych zmiennych), albo jest wyłącznie zdany na obserwowanie danych pochodzących z pomiarów, na których przebieg nie ma wpływu i techniki tej nie może zastosować. Omówimy przykładowe heurystyki pomocne przy odkrywaniu związków w obu tych sytuacjach.

Rekursja na wyższe poziomy opisu

W przypadku, gdy system ma eksperymentalną kontrolę nad zmiennymi, pomiędzy którymi poszukuje związków, można zastosować technikę poszukiwania regularności na różnych poziomach opisu. Na początku wszystkie zmienne niezależne oprócz jednej otrzymują stałe wartości i poszukuje się pewnego prawa dla tej sytuacji. Można w tym celu wykorzystać metody omawiane poprzednio dla zależności dwóch zmiennych. Odnalezione prawo, opisujące zależność zmiennej zależnej od wybranej zmiennej niezależnej, przy ustalonych wartościach pozostałych zmiennych niezależnych, można traktować jako ukonkretnienie pewnego szablonu wyrażenia przez podstawienie pewnych stałych za jego parametry. Stałe te zapamiętywane są wraz z ustalonymi wartościami zmiennych niezależnych, dla których zostały znalezione. Następnie system zmienia jedną z ustalonych wartości zmiennych niezależnych i ponawia tę procedurę, znajdując inne stałe parametry. Po zgromadzeniu w ten sposób dostatecznie dużej ilości danych, system przechodzi na wyższy poziom opisu, na którym traktuje te stałe jako nowe zmienne zależne i próbuje znaleźć opisujące je związki stosując rekurencyjnie tę samą metodę.

Jeśli, przykładowo, system poszukuje zależności pomiędzy zmienną zależną $ y$ i zmiennymi niezależnymi $ t$, $ w$ i $ x$, jego pierwszy krok może polegać na ustaleniu pewnych wartości dla $ t$ i $ w$, dla których znajdowane jest pewne prawo opisujące zależność $ y$ od $ x$. Załóżmy, że znalezione prawo jest postaci $ y=a_1x^2+b_1$ dla pewnych konkretnych wartości $ a_1$ i $ b_1$. Wówczas system zmienia jedną z ustalonych zmiennych, np. $ w$, i ponownie znajduje zależność $ y$ od $ x$, postaci $ y=a_2x^2+b_2$. Powtarzając to wielokrotnie, system uzyskuje dla różnych $ w$ różne pary wartości $ a_i$ i $ b_i$. Kiedy jest ich dostatecznie dużo, można potraktować $ a$ i $ b$ jako nowe zmienne zależne i poszukiwać ich zależności od $ w$ dla różnych $ t$ w ten sam sposób -- to właśnie jest rekurencyjne przejście na wyższy poziom.

Powyższy opis jest streszczeniem tego, co na temat omawianej techniki piszą jej twórcy. Jednak bardziej precyzyjny i dający lepsze wybrażenie o możliwej implementacji opis można sformułować w postaci algorytmu rekurencyjnego, w którym wspomniane przejście na wyższy poziom opisu jest powrotem z rekurencyjnego wywołania. Algorytm taki, który jest prawdopodobnie nie całkiem wierną, ale za to jasno i w miarę zgrabnie sformułowaną interpretacją oryginalnej heurystyki systemu BACON, przedstawia tablica 5.


Tablica: Algorytm odkrywania równań metodą rekursji na wyższy poziom opisu.
$ \textit{znajdź\_równanie}(y,X,P)$:
  1. jeśli $ X=\emptyset$
    zwróć stałą wartość $ y$ ze zbioru $ P$;
  2. wybierz $ x\in X$;
  3. $ E:=\emptyset$;
  4. dla różnych wartości $ v$ zmiennej $ x$ wykonaj
    1. $ e:=\textit{znajdź\_równanie}(y,X-\{x\},P_{xv})$;
    2. $ E:=E\cup\{e\}$;
  5. znajdź wspólny szablon $ \mathbf{e}$ dla równań ze zbioru $ E$ oraz zbiór parametrów tego szablonu $ \Phi$ i ich wartości $ S$ dla różnych wartości $ x$;
  6. dla każdego $ \phi\in\Phi$ wykonaj
    1. $ e:=\textit{znajdź\_równanie1}(\phi,x,S)$;
    2. zastąp parametr $ \phi$ w szablonie $ \mathbf{e}$ równaniem $ e$;
  7. zwróć $ \mathbf{e}$.


Argumenty przedstawionej procedury to zmienna zależna $ y$, zbiór zmiennych niezależnych $ X$ oraz zbiór danych $ P$. Będziemy zakładać dla wygody, że $ P$ zawiera wszystkie potrzebne dane w dostatecznej ilości (w praktyce oczywiście mogą być one generowane za pomocą eksperymentów podczas poszukiwania równania). Przez $ P_{xv}$ oznaczamy zbiór tych rekordów danych ze zbioru $ P$, dla których zmienna $ x$ ma ustaloną wartość $ v$. Wykorzystywana jest procedura $ \textit{znajdź\_równanie1}$, która oznacza dowolną metodę znajdowania prostych równań (dla dwóch zmiennych).

Znajdowanie praw przez obserwację

Powyższe podejście nie może być zastosowane w przypadku, gdy system nie ma eksperymentalnej kontroli nad wartościami zmiennych i musi pozostać biernym obserwatorem dostarczanych mu danych. Okazuje się na szczęście, że użyteczna może być w tym przypadku nieco zmodyfikowana najprostsza z omawianych heurystyk dla znajdowania prostych praw (dla dwóch zmiennych): technika wykrywania stałych i trendów. Modyfikacja polega na tym, że obecnie zamiast wykrywać monotoniczne trendy (jeśli wartość jednej zmiennej się zwiększa, to wartość drugiej też się zwiększa albo zmniejsza się) staramy się wykrywać zachodzące pomiędzy wartościami zmiennych korelacje. Jeśli okaże się, że wartości $ x$ i $ y$ są pozytywnie skorelowane, tworzona jest nowa zmienna $ t=x/y$, zaś jeśli $ x$ i $ y$ są skorelowane negatywnie, tworzona jest nowa zmienna $ t=xy$.

Korelacje o różnym stopniu mogą oczywiście występować pomiędzy wieloma parami zmiennych, co powoduje potrzebę wyboru najbardziej obiecujących. W przypadku systemu BACON branych jest pod uwagę $ m$ najsilniej skorelowanych par zmiennych, na podstawie których tworzy się nowe zmienne, ponownie oblicza korelacje pomiędzy wszystkimi parami zmiennych, itd. W miarę, jak tworzone są zmienne odpowiadające coraz bardziej złożonym wyrażeniom, najlepsze korelacje zbliżają się do $ 1$ lub $ -1$, prowadząc ostatecznie do odkrycia liniowej zależności i utworzenia prawa. System działa do momentu wykorzystania wszystkich zmiennych w pewnym prawie lub przekroczenia przez wyrażenia odpowiadające zmiennym pewnego progu złożoności.

Literatura do wykładu

Wprowadzenie do zagadnień data mining stanowi raport Holsheimera i Siebesa, chociaż większość z omawianych tam zagadnień koncentruje się wokół znanych nam już algorytmów indukcyjnego uczenia się na podstawie przykładów. System 49er opisują w swoim artykule Żytkow i Zembowicz. Przedstawione metody odkrywania równań zaczerpnięto z repertuaru metod zaimplementowanych w różnych wersjach systemu BACON i opisanych w artykule Langleya i innych.

  1. Holsheimer, M., Siebes, A. Data mining: A search for knowledge in databases. Technical report CS-R9406, Center for Mathematics and Computer Science, The Netherlands, 1994. Dla zainteresowanych plik w postscripcie dostępny u mnie.
  2. Żytkow, J. M., Zembowicz, R. Database exploration in search for regularities. Journal of Intelligent Information Systems, 2:39-81, 1993.
  3. Langley, P., Simon, H. A., Bradshaw, G. L. Heuristics for empirical discovery. W: Bolc, L. (ed.), Computational Models of Learning, Springer-Verlag, 1987. Przedruk w Shavlik, J., Dietterich, T. G. (eds.), Readings in Machine Learning, Morgan Kaufmann, 1990.

About this document ...

Uczenie się maszyn: wykład 9
Odkrywanie zależności w danych

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation wyklad9.tex

The translation was initiated by Pawel Cichosz on 2004-03-01

Pawel Cichosz 2004-03-01