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ę !