Artykuły na temat Eksploracji danych, czyli Data Miningu

+ Reguły indukcyjne
+ Zapis i interpretacja reguł
+ Interpretacja zbioru reguł

Reguły indukcyjne

Reguła indukcyjna jest najbardziej naturalnym sposobem reprezentowania wiedzy. Poprzez regułę rozumiemy zwykłą logiczną implikację postaci: jeżeli przesłanki to konkluzja lub jeżeli warunki to decyzja, np. jeżeli Jasio z Olsztyna kupił motor i Stasio z Olsztyna kupił motor, to prawdopodobnie Kazio z Olsztyna również kupi motor.

Można wykorzystać reguły do zapisu wiedzy dotyczącej klasyfikacji, czyli indukcyjnego uczenia się pojęć. Część przesłankowa (warunkująca) opisuje wówczas warunki dotyczące atrybutów klasyfikowanego pojęcia, natomiast konkluzją (część warunkowa) będzie odpowiednia kategoria, do której dodamy klasyfikowany przykład. My natomiast skupimy się bardziej na wykorzystaniu reguł do reprezentacji wiedzy dotyczącej asocjacji, czyli uczenia się, jakie atrybuty najczęściej występują razem. Część przesłankowa opisuje tutaj warunki dotyczące wartości atrybutów sprawdzanego rekordu, natomiast wnioskiem będzie wartość atrybutu, który najprawdopodobniej wystąpi wraz z badanymi. Przy pomocy takich reguł możemy sprawdzić poprawność zbioru wartości atrybutów, uzupełnić lub przewidzieć przyszłe wartości atrybutów. Właśnie mechanizm przewidywania przyszłych wartości atrybutów zastosowałem w swojej aplikacji, która na podstawie zgromadzonej wiedzy stara się przewidzieć, które towary klient wrzuci do koszyka.

Zapis i interpretacja reguł

W większości przypadków możemy dopuszczać zapis reguł, jako dowolnych formuł logicznych, zbudowanych z formuł atomowych, mających postać równości, nierówności lub przynależności dla wartości jednego atrybutu. W praktyce, ze względu na efektywność i szybkość generowania reguł oraz wnioskowania dedukcyjnego na ich podstawie, dopuszcza się budowanie formuł logicznych, których część przesłankowa zbudowana jest prawie wyłącznie z koniunkcji warunków atomowych.

Wspomniane warunki elementarne dotyczące wartości pojedynczego atrybutu nazywane są selektorami, a ich koniunkcje – kompleksami. Przyjmuje się tu ograniczenie, że jeden kompleks zawiera tylko pojedyncze selektory dotyczące każdego atrybutu. Regułę składającą się z kompleksu X i decyzji Y możemy przedstawić jako implikację X → Y.

Interpretacja zbioru reguł

Aby umożliwić interpretację dowolnej hipotezy dla danego zestawu atrybutów nie możemy wprowadzić ograniczenia co do ilości reguł opisujących daną hipotezę. Weryfikacja danego przykładu pod kątem utworzonej hipotezy polega na znalezieniu w tej hipotezie reguły pokrywającej, to znaczy takiej, której kompleks będzie identyczny jak zestaw atrybutów w badanym przykładzie. W przypadku, gdy znajdzie się dokładnie jedna reguła pokrywająca dany przykład, jej część decyzyjna Y będzie wartością przypisaną danemu przykładowi przez hipotezę zawierającą regułę pokrywającą. W praktyce jednak taka sytuacja, że dokładnie jedna reguła pokrywa nam weryfikowany przykład zdarza się rzadko. Częściej mamy do czynienia z sytuacją, ze jeden przykład jest pokrywany przez wiele reguł, które posiadają różne części decyzyjne Y, albo przykład nie jest pokrywany przez żadną regułę. W takich przypadkach wszystko zależy od tego, czy zbiór reguł traktujemy jako uporządkowany, czy nieuporządkowany.

Nieuporządkowany zbiór reguł rzeczywiście możemy w dokładnym tego słowa znaczeniu nazwać zbiorem. Zawarte w nim reguły nie są w żaden sposób uporządkowane i każda z nich jest traktowana dokładnie tak samo. Do rozstrzygnięcia sytuacji, w których jeden przykład jest pokrywany przez kilka reguł jednocześnie albo nie jest pokrywany przez żadną regułę należy użyć specjalnej strategii:

• losowy wybór jednej z reguł pokrywających klasyfikowany przykład,

• wybór najbardziej szczegółowej reguły pokrywającej klasyfikowany przykład,

• wybór reguły o najmniejszej liczbie selektorów,

• losowy wybór decyzji według rozkładu prawdopodobieństwa wyznaczonego przez rozkład częstości decyzji wśród reguł pokrywających klasyfikowany przykład,

• związanie z każdą z reguł liczby pokrywanej przez nią przykładów i wybranie reguły posiadających największą ilość pokrywanych przez nią przykładów.

Mimo prostoty, strategie te dają bardzo dobre efekty, a wspomniana prostota obliczeń przekłada się na efektywność i szybkość generowania i interpretacji reguł, co ma bardzo duże znaczenie w praktycznym ich zastosowaniu.

Komplikacji związanych ze stosowaniem nieuporządkowanych zbiorów reguł możemy uniknąć używając algorytmów odkrywania wiedzy, które zbudują nam zbiór reguł uporządkowanych według określonej wartości i ze z góry ustaloną kolejnością ich stosowania. Jeżeli w takim zbiorze zdarzy się, że dany przykład jest pokrywany przez więcej niż jedną regułę, zostaje mu przyporządkowana decyzja z reguły będącej pierwszą z kolei wśród reguł pokrywających dany przykład. Niekiedy taki zbiór uporządkowanych reguł nazywamy listą decyzyjną. Jest to taka lista reguł, gdzie po każdej z nich zostaje dopisana fraza w przeciwnym wypadku i w razie nie spełnienia warunków danej reguły, brana jest pod uwagę kolejna reguła znajdująca się na liście. W ten sposób eliminowany jest problem w sytuacji, gdy jeden przykład jest pokrywany przez więcej niż jedną regułę.