DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Wykład 5
Rozpoznawanie wzorców
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Wykład 5
Rozpoznawanie wzorców
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
2
Struktura wykładu:
• Metody grupowania
• Analiza skupień
• Analiza asocjacji i sekwencji
• Statystyka opisowa
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
3
Metody grupowania
Grupowanie pod nadzorem
Grupowanie bez nadzoru
Dana jest jednoznacznie określona
zmienna celu.
Nie istnieje jednoznacznie
określona zmienna celu.
Algorytm eksploracji danych
poszukuje wzorców i struktur
wśród wszystkich zmiennych.
• Drzewa decyzyjne
• Regresja logistyczna
• Metoda k-najbliższych sąsiadów
• Metoda k-śrenich
• Metoda SOM – Kohonena
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Metody grupowania – inny podział
1.
Metody hierarchiczne:
•
Skupienia tworzą drzewa binarne i w ten sposób uzyskiwana jest hierarchia
tj. jedne skupienia są zawarte w drugich.
•
Uwzględniając kryterium rozpoczęcia procesu grupowania wyróżniamy:
metody aglomeracyjne i metody podziałowe.
•
Ze względu na sposób wyznaczania odległości między skupieniami
najczęściej spotykane metody aglomeracyjne to: najbliższego sąsiedztwa,
najdalszego sąsiedztwa, mediany, środka ciężkości, średniej odległości
wewnątrz skupień, średniej odległości między skupieniami, minimalnej
wariancji Warda.
2.
Metody optymalizacyjno-iteracyjne:
•
Wymagają wstępnego podziału zbioru obiektów na określona liczbę
podzbiorów. Wybrany sposób podziału jest iteracyjnie modyfikowany.
Np. metoda k-średnich.
3.
Metody obszarowe:
•
Przestrzeń grupowania jest dzielona na rozłączne obszary a obiekty
znajdujące się w otrzymanych obszarach tworzą grupy.
4.
Inne metody
4
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
5
Grupowanie – analiza skupień
Grupa, skupienie (cluster) – zbiór obiektów, które są podobne
do siebie nawzajem i niepodobne do obiektów z innych grup.
Grupowanie (clustering) – oznacza grupowanie obserwacji (rekordów)
w klasy (grupy) podobnych obiektów.
Zmienność pomiędzy grupami (between-cluster variation, BCV)
Zmienność wewnątrz grupy (within-cluster variation, WCV)
Analiza skupień (cluster analysis) – grupowanie bez nadzoru, ma za
cel wykrycie w zbiorze obserwacji skupień, czyli grup.
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Liczba grup (skupień)
Dwa skupienia
Dwa lub cztery skupienia
6
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Algorytm k-średnich
1.
Określamy na ile grup (k) zbiór danych ma zostać podzielony.
2.
Losowo wybieramy k rekordów (obserwacji) jako początkowe
ś
rodki grup.
3.
Dla każdego rekordu znajdujemy najbliższy środek grupy,
wyznaczając w ten sposób podział zbioru na k grup.
4.
Dla każdej z k grup wyznaczamy centroid grupy i aktualizujemy
położenie każdego środka grupy jako nową wartość centroidu.
5.
Powtarzamy punkty od 3 do 5 aż do osiągnięcia określonego
warunku stopu.
7
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Algorytm k-średnich – warunek stopu
•
Algorytm k-średnich kończy działanie, gdy centroidy już się nie
zmieniają.
•
Algorytm może skończyć działanie, gdy zostanie spełnione pewne
kryterium zbieżności, np. brak istotnego zmniejszania
sumarycznego błędu kwadratowego:
–
grupy
–
centroid i-tej grupy
–
punkt danych z i-tej grupy
(
)
∑
∑
∈
=
=
i
C
p
i
k
i
m
p
d
2
1
,
SSE
i
C
i
m
i
C
p
∈
8
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
9
Metoda k-średnich - przykład
•
Przypuścimy, że mamy
zbiór punktów danych
w dwuwymiarowej
przestrzeni.
•
Jesteśmy zainteresowani
odkryciem np. trzech grup.
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
10
Metoda k-średnich - przykład
•
Wybieramy k=3 elementów, które
traktujemy jako potencjalne
ś
rednie (środki) skupień.
•
Wszystkie pozostałe elementy
są przydzielane do skupienia,
którego środek jest mu
najbliższy.
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
11
Metoda k-średnich - przykład
•
W każdym ze skupień na nowo
wyznaczany jest centroid
(średnia, środek) i powtarzany
jest ostatni krok.
•
Algorytm kończy swoje działanie,
jeśli w danym kroku nie zostanie
zmienione przypisanie żadnego
z punktów.
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Charakterystyka obiektów
•
Badane obiekty tworzą skończony zbiór (populacja lub próba wylosowana
z populacji).
•
Każdy obiekt opisany jest przez pewien zestaw zmiennych przyjmujących
wartości liczbowe.
•
Obiekt opisany przez zmienne przedstawiamy jako punkt
z n-wymiarowej przestrzeni.
•
Zbiór punktów jest reprezentowany w przestrzeni wielowymiarowej
zwanej przestrzenią grupowania.
UWAGA: Metody wykorzystywane w analizie skupień dają możliwość uwzględnienia
dużej ilości zmiennych, ale nie dostarczają żadnych wskazówek, które zmienne
należy wybrać.
n
X
X
X
,
,
,
2
1
K
(
)
n
x
x
x
x
,
,
,
2
1
K
=
12
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
13
Wyznaczanie odległości
Dla większego wymiaru:
Metryka euklidesowa
Metryka taksówkowa
(
)
2
1
, y
y
y
=
(
)
2
1
, x
x
x
=
(
)
(
)
(
)
2
2
2
2
1
1
,
y
x
y
x
y
x
d
e
−
+
−
=
(
)
2
2
1
1
,
y
x
y
x
y
x
d
t
−
+
−
=
(
)
2
1
, y
y
y
=
(
)
2
1
, x
x
x
=
(
)
(
)
∑
−
=
i
i
i
e
y
x
y
x
d
2
,
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
14
Pułapka wymuszonego grupowania przykład
•
W metodzie k-średnich istnieje ryzyko złego doboru liczby skupień.
Przykład 1
Analizie poddano zakupy mydła przez klientów: wyróżniono dwie zmienne:
cena za sztukę i liczba sztuk.
Podział na 2 grupy (k-średnich)
Faktyczna liczba grup klientów = 3
cena
L
ic
z
b
a
s
z
tu
k
cena
L
ic
z
b
a
s
z
tu
k
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Metoda SOM – sieci Kohonena
Sieci samoorganizujące (Self Organization Maps, SOM) stanowią
klasę sieci neuronowych bez warstwy ukrytej.
Szczególnym przypadkiem sieci samoorganizujących są
sieci
Kohonena.
Sieci samoorganizujące:
•
Przekształcają złożone, wielowymiarowe sygnały wejściowe
w prostsze, mniej wymiarowe odwzorowania.
•
Neurony położone bliżej siebie są bardziej podobne do siebie
niż do innych neuronów znajdujących się dalej.
15
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Procesy sieci samoorganizujących
1.
Rywalizacja: neurony wyjściowe rywalizują ze sobą, by uzyskać
najlepszą wartość odległości np. euklidesowej. Węzeł wyjściowy
z najmniejszą odległością euklidesową pomiędzy danymi
wejściowymi a wagami zostaje zwycięzcą.
2.
Współdziałanie: pobudzany jest neuron wygrywający oraz inne
neurony z nim sąsiadujące.
3.
Adaptacja: wszystkie neurony z sąsiedztwa neuronu
wygrywającego uczestniczą w adaptacji czyli uczeniu. Wagi ich są
tak dopasowywane, aby neurony te miały większe szanse
na ponowne wygranie rywalizacji w przypadku podobnego rekordu.
16
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Sieci Kohonena - przykład
Przykład 2
•
Rozważmy zbiór danych, w którym każdy rekord (obserwacja) jest opisany przez
10 zmiennych, zatem mamy dziesięciowymiarowy wektor wejściowy.
•
Załóżmy, że chcemy użyć sieci Kohonena o rozmiarze 5 x 5.
•
Każdy neuron jest również opisany przez dziesięciowymiarowy wektor wag.
•
W procesie uczenia sieci wagi są modyfikowane.
i-ty rekord
sieć
1
i
x
2
i
x
10
i
x
M
17
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Sieci Kohonena
•
Z wykorzystaniem odpowiedniego odwzorowania każda obserwacja
otrzymuje swoją reprezentację w siatce neuronów (punktów).
•
Ponieważ każda kratka w siatce odpowiada jednemu skupieniu,
zatem liczba obserwacji (rekordów) musi być większa niż liczba
zadeklarowanych węzłów w siatce.
sąsiad
najbliższy
sąsiad
sąsiad
sąsiad
Reprezentacja
obserwacji na siatce
18
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Sieci Kohonena
•
Każdy neuron jest zdefiniowany przez wektor wag i lokalizację w siatce.
•
W procesie budowy sieci wagi neuronów są modyfikowane.
•
Wektory wag podążają w stronę punktów centralnych skupień danych.
•
Obszar utworzony przez neurony, w którym znajduje się dana
obserwacja jest następnie zacieśniany.
•
Proces jest kontynuowany dla wszystkich pozostałych obserwacji.
19
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Sieci Kohonena
•
Ostatecznie otrzymujemy siatkę z neuronami odzwierciedlającymi
skupienia.
•
Sąsiadujące neurony reprezentują grupy rekordów o zbliżonych
cechach.
•
Na rysunku większe natężenie koloru odpowiada większej liczności
danego skupienia.
20
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Metoda k-średnich i metoda SOM – Kohonena
Przed wykorzystaniem obu metod grupowania bez nadzoru należy
dokonać normalizacji/standaryzacji danych.
( )
( )
( )
( )
( )
X
X
X
X
X
X
X
X
min
max
min
zakres
min
*
−
−
=
−
=
21
( )
( )
X
X
X
X
σ
ś
rednia
*
−
=
Normalizacja:
Standaryzacja:
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
22
Analiza asocjacji
•
Analiza asocjacji zajmuje się badaniem związków między
zachodzeniem pewnych wydarzeń lub istnieniem cech
•
Analiza asocjacji kryje się również pod nazwą „analiza koszykowa
(koszyka sklepowego)” (market basket analysis), daje ona możliwość
znajdowania odpowiedzi m.in. na pytanie:
„Czy jeśli klient kupi produkt A, to czy kupi również produkt B? ”
A
B
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Reguły asocjacyjne
Regułą asocjacyjną nazwiemy każdą implikację: A
B
„ Jeśli poprzednik, to następnik”.
•
Odpowiednie miary wyznaczają jakość takiej reguły asocjacyjnej.
•
Liczba możliwych reguł asocjacyjnych rośnie wykładniczo wraz
ze wzrostem liczby atrybutów. Dla k atrybutów binarnych liczba
możliwych reguł asocjacyjnych wynosi: , dla 10 rodzajów
różnych usług (artykułów) mamy
•
Do odkrywania reguł asocjacyjnych wykorzystywany jest
algorytm
a priori, który daje możliwość zredukowania przedstawionego
problemu do mniejszego wymiaru.
⇒
1
2
−
⋅
k
k
5120
2
10
9
=
⋅
23
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Prezentacja danych w analizie koszykowej
Transakcja
Artykuł
1
1
1
1
2
2
2
A
B
D
E
A
B
C
24
Transakcja
A
B
C
D
E
1
2
3
4
5
6
7
8
1
1
1
1
0
0
1
1
1
1
0
1
1
0
0
1
0
1
1
1
1
1
0
1
1
0
0
0
1
1
0
0
1
0
1
0
1
0
1
1
M
M
Transakcyjny format danych
Macierzowy format danych
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
25
Reguły asocjacyjne (A B)
Podstawowe miary w analizie asocjacji:
•
Wsparcie (Support)
(suma transakcji zawierających produkt A i B)
(suma wszystkich transakcji )
•
Zaufanie (Confidence)
(suma transakcji zawierających produkt A i B)
(suma transakcji zawierających produkt A)
•
Oczekiwane zaufanie (Expected Confidence)
(suma transakcji zawierających produkt B)
(suma wszystkich transakcji )
•
Korelacja asocjacyjna (Lift)
Zaufanie
Oczekiwane zaufanie
⇒
(
)
=
∩ B
A
P
(
)
(
)
( )
=
∩
=
A
P
B
A
P
A
B
P
|
( )
=
B
P
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
26
Reguły asocjacyjne – przykład
Przykład 3
Zbadamy na podstawie poniższych danych, czy istniej reguła asocjacyjna
łącząca dwie usługi ubezpieczeń samochodowych:
ubezpieczenie NW i AC.
AC → NW
Support = 50%
Confidence = 75%
Expected Confidence = 77,8%
Lift = 0,75/0,778 = 0.96 < 1 brak zależności
500 2500
1500 4500
NW
Tak
AC
Nie
Tak
Nie
3000
6000
9000
2000
7000
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
27
Reguły asocjacyjne – przykład
Przykład 4
Zbadamy na podstawie poniższych danych, czy istniej reguła asocjacyjna
łącząca dwie usługi ubezpieczeń: samochodowe ubezpieczenie AC
i ubezpieczenie domu.
AC → Dom
Support = 50%
Confidence = 64%
Expected Confidence = 57%
Lift = 0,64/0,57 = 1,12>1 badana reguła jest prawdziwa
1000 500
2000 3500
Dom
Tak
AC
Nie
Tak
Nie
1500
5500
7000
3000
4000
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
28
Prawdziwa reguła asocjacyjna
Przykład 4 c.d.
Proponowane działania marketingowe maksymalizujące zysk ze
sprzedaży obu usług: ubezpieczenia AC i ubezpieczenia domu:
•
zakwalifikować każdy z produktów do różnych pakietów
•
nie reklamować jednocześnie obu produktów
•
do sprzedaży obu tych produktów dołączyć inny słabo sprzedawany
produkt
•
podnieść cenę jednego produktu obniżyć cenę drugiego
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Odkrywanie reguł asocjacyjnych
Częstość zbioru zdarzeń – liczba transakcji zawierająca dany zbiór
zdarzeń.
Zbiór częsty – zbiór zdarzeń, który występuje przynajmniej pewną
minimalna liczbę razy, czyli z określoną częstością
Odkrywanie reguł asocjacyjnych:
1. Należy znaleźć wszystkie zbiory częste.
2. Na podstawie zbiorów częstych należy wyznaczyć reguły
asocjacyjne, spełniające warunek minimalnego wsparcia i zaufania.
Własność a priori w analizie asocjacji – jeśli zbiór zdarzeń nie jest
częsty, to dodanie dowolnego artykułu
A do tego zbioru nie
spowoduje tego, że zbiór ten będzie zbiorem częstym.
29
φ
≥
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Tworzenie reguł asocjacyjnych
Tworzenie reguł asocjacyjnych za pomocą częstych zbiorów zdarzeń:
1. Utworzyć niepuste podzbiory częstego zbioru zdarzeń.
2. Przeanalizować regułę asocjacyjną:
niepusty podzbiór częstego zbioru zdarzeń
częsty zbiór zdarzeń bez uwzględnionego podzbioru
3. Rozważ wszystkie reguły asocjacyjne dla wszystkich podzbiorów
częstego zbioru zdarzeń.
Przykład 5
Przyjmijmy następujący zbiór częsty trzyelementowy: {A, B, C}.
Właściwe podzbiory: {A}, {B}, {C}, {A, B}, {A, C}, {B, C}.
Reguły asocjacyjne:
{A} {B, C}
{B} {A, C}
{C} {A, B}
{A, B} {C}
{A, C} {B}
{B, C} {A}
30
⇒
⇒
⇒
⇒
⇒
⇒
⇒
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
31
Schemat analizy asocjacji w SAS Enterprise Miner
Diagram gwiaździsty
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
32
Analiza sekwencji
Analiza sekwencji – analiza asocjacji uwzględniająca wymiar czasowy
Analizujemy dane zawierające informacje o zdarzeniach, które wystąpiły
w określonym przedziale w czasie.
Analiza sekwencji daje ona możliwość znajdowania odpowiedzi m.in.
Na pytanie:
„Czy jeśli klient kupił produkt A w ubiegłym miesiącu, to czy kupi
również produkt B w tym miesiącu? ”
• Wymaga uwzględnienia w modelu dodatkowej zmiennej czasowej.
DATA MINING – nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
33
Dziękuję za uwagę !