Artykuły na temat Eksploracji danych, czyli Data Miningu

Reprezentowanie danych i hipotez.

1. Opis przykładów

Załóżmy, że chodzi nam o odkrywanie asocjacji wśród wartości pewnych atrybutów, występujących w rekordach bazy danych, zwanych w terminologii maszynowego uczenia się przykładami. W przypadku mojej aplikacji (sklep internetowy) dużo wygodniej jest nie zajmować się samymi atrybutami, ale konkretnie ich wartościami. W takim rodzaju danych dopuszcza się występowanie w każdym z przykładów mogą wystąpić różne zestawy atrybutów, bądź pojedyncze atrybuty mogą przyjmować nie pojedyncze wartości, ale całe zbiory wartości. Tak dzieje sie w przypadku analizowania zakupów poszczególnych klientów w sklepie. Każdy klient może kupić dowolną ilość towarów w ramach jednej transakcji. Podczas analizy należy traktować pojedynczą transakcję jako całość, niezależnie od ilości zakupionych w ramach niej towarów.

Pomijając sposób organizacji takich danych w relacyjnej bazie danych, możemy przyjąć, że każdy przykład p jest opisany przez pewien zbiór atrybutów Zp (zbiór wartości), nie interesując się tym, ile tych atrybutów w istocie jest, ani również ile każdy z nich może mieć wartości. Jako Z oznaczmy zbiór wszystkich wartości, jakie mogą wystąpić w ramach rozważanej dziedziny w opisach przykładów. Jak wcześniej wspomniałem, będziemy rozważać przykłady nie jako zbiór atrybutów i wartości, ale tylko jako zbiór wartości, eliminując w ten sposób konieczność zakładania ilości atrybutów oraz ile każdy z nich może mieć wartości w danym przykładzie.

2. Reguły asocjacyjne

 

Wiedzę o asocjacjach w zbiorze danych zapisujemy za pomocą reguł asocjacyjnych. Jak wspomniałem w poprzednich podrozdziałach tej pracy, reguły przedstawiamy w najbardziej naturalny sposób – za pomocą logicznej implikacji. Każda reguła asocjacyjna składa się z dwóch części – dwóch zbiorów wartości: warunkujących i warunkowych. Regułę o części warunkującej X ⊂ Z i części warunkowej Y  Z zapiszemy więc w sposób następujący:

X ⇒ Y

i będziemy ją interpretować jako stwierdzenie, że wartości atrybutów ze zbioru X często pociągają za sobą wartości atrybutów ze zbioru Y. Inaczej – w wielu przykładach, w których występują wszystkie wartości zbioru X występują również wszystkie wartości ze zbioru Y.

Określenie “często” nie jest zbyt precyzyjnym określeniem ilości powtórzeń wystąpień zbiorów X i Y wśród analizowanego zbioru trenującego. W celu sprecyzowania interpretacji reguł asocjacyjnych określa się dla nich wsparcie i zaufanie. Wsparcie jest stosunkiem ilości wystąpień przykładów P, które zawierają w całości opisy X oraz Y do ilości wszystkich przykładów P, gdzie P jest dowolnym podzbiorem zawierającym tylko i wyłącznie przykłady Z:

Wsparcie(X ⇒ Y) = |PX∪Y| / |P|

Każda reguła może być więc wspierana, albo naruszana przez przykład. Natomiast zaufanie reguły w zbiorze P definiuje się następująco:

Zaufanie(X ⇒ Y) = |PX∪Y| / |PX|

czyli jako stosunek liczby przykładów ze zbioru P, w których opisach występują zarówno opisy X jak i Y do liczby przykładów, w których opisach występują tylko elementy zbioru X, czyli zbioru wartości warunkujących. Poniższy przykład ilustruje wsparcie i zaufanie wybranych reguł w transakcjach sprzedaży sklepu:

transakcja	produkty
1	chleb, masło
2	chleb, masło, mleko, jabłka
3	chleb, mleko, jabłka
4	chleb, masło, mleko, jabłka

reguła	wspierana	naruszana
chleb AND mleko --> jabłka	2, 3, 4
chleb --> masło	1, 2, 4	3

Zgodnie z definicją wsparcia i zaufania dla reguł otrzymujemy następujące wyniki dla analizowanych reguł:

• chleb AND mleko --> jabłka wsparcie=75% zaufanie=100%

• chleb --> masło wsparcie=75% zaufanie=75%

Podsumowując, wsparcie mówi, jak często w badanym zbiorze występuje sytuacja opisana przez regułę, natomiast zaufanie mówi, jak często sytuacja opisana przez zbiór wartości warunkowych występuje pod warunkiem wystąpienia sytuacji opisanej przez zbiór wartości warunkujących.

3. Struktury danych dla przechowywania zbiorów

Każdy element należy do jakiegoś zbioru – w naszym przypadku każda wartość atrybutu należy do danego zbioru wartości. W celu zilustrowania posłużę się przykładem z poprzednich podrozdziałów:

transakcja	produkty
1	chleb, masło
2	chleb, masło, mleko, jabłka
3	chleb, mleko, jabłka
4	chleb, masło, mleko, jabłka

Mamy tu do czynienia z modelem logicznym danych. W polu produkty mami zbiory produktów, które zostały zakupione w ramach transakcji zapisanych w polu transakcje, czyli w transakcji numer 2, klient kupił chleb, masło, mleko, jabłka. Taki model danych służy jednak tylko do teoretycznych rozważań i nie nadaje się do analizy. W praktyce dane o sprzedaży (jak i wszelkie inne) zwykle zapisuje się w relacyjnych bazach danych. Przekształcenie modelu logicznego na model relacyjny przedstawia się następująco:

transakcja	produkt
1	chleb
1	masło
2	chleb
2	masło
2	mleko
2	jabłka
3	chleb
3	mleko
3	jabłka
4	chleb
4	masło
4	mleko
4	jabłka

Widzimy więc istotną różnicę, gdyż w modelu relacyjnym jeden zbiór wartości zapisany jest w kilku rekordach (tylu, ile elementów liczy dany zbiór), natomiast w modelu logicznym do zapisania jednego zbioru wartości wystarczał jeden rekord.

4. Struktury danych dla przechowywania reguł

Podobnie jak zbiory wartości, również reguły asocjacyjne musimy zapisać w modelu relacyjnym. Poniższy przykład ilustruje sposób zapisu reguł w logicznym i relacyjnym modelu danych.

Model logiczny:

• chleb AND mleko --> jabłka wsparcie=75% zaufanie=100%

• chleb --> masło wsparcie=75% zaufanie=75%

Model relacyjny:

Przykładowe dane w modelu relacyjnym dla przechowywania reguł:

tabela reguły

id_reguła	wsparcie	zaufanie
1	0.75	1
2	0.75	0.75

tabela elementy_reguł

id_element	id_reguła	wartość	typ
1	1	chleb	body
2	1	mleko	body
3	1	jabłka	head
4	2	chleb	body
5	2	masło	head