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
Struktura wykładu:
" Metody grupowania
" Analiza skupień
" Analiza asocjacji i sekwencji
" Statystyka opisowa
2
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Metody grupowania
Grupowanie pod nadzorem Grupowanie bez nadzoru
Dana jest jednoznacznie określona Nie istnieje jednoznacznie
zmienna celu. określona zmienna celu.
Algorytm eksploracji danych
poszukuje wzorców i struktur
wśród wszystkich zmiennych.
" Drzewa decyzyjne " Metoda k-śrenich
" Regresja logistyczna " Metoda SOM  Kohonena
" Metoda k-najbliższych sąsiadów
3
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
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.
5
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:
k
2
SSE =
" "d(p, mi )
i=1 p"Ci
Ci  grupy
mi  centroid i-tej grupy
p "Ci  punkt danych z i-tej grupy
8
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Metoda k-średnich - przykład
" Przypuścimy, że mamy
zbiór punktów danych
w dwuwymiarowej
przestrzeni.
" Jesteśmy zainteresowani
odkryciem np. trzech grup.
9
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
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.
10
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
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.
11
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.
X1, X ,K, X
" Obiekt opisany przez zmienne przedstawiamy jako punkt
2 n
x = (x1, x2,K, xn)
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ć.
12
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Wyznaczanie odległości
Metryka euklidesowa Metryka taksówkowa
x = (x1, x2)
x = (x1, x2)
y = (y1, y2)
y = (y1, y2)
2 2
dt(x, y)= x1 - y1 + x2 - y2
de(x, y)= (x1 - y1) +(x2 - y2)
Dla większego wymiaru:
2
de(x, y)= (xi - yi)
"
i
13
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
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.
Faktyczna liczba grup klientów = 3 Podział na 2 grupy (k-średnich)
14
cena cena
Liczba sztuk
Liczba sztuk
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.
sieć
i-ty rekord
xi1
xi2
M
xi10
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).
najbliższy
sÄ…siad
sÄ…siad
Reprezentacja
obserwacji na siatce
sÄ…siad sÄ…siad
" 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.
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 - min(X ) X - min(X )
Normalizacja:
X* = =
zakres(X ) max(X )- min(X )
X - średnia(X )
Standaryzacja:
X * =
Ã(X )
21
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
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
22
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
k Å" 2k -1
10Å"29 = 5120
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.
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
Transakcyjny format danych Macierzowy format danych
Transakcja
Transakcja Artykuł A B C D E
1 A 1 1 1 0 1 1
1 B 2 1 1 1 0 0
1 D 3 1 0 1 0 1
1 E 4 1 1 1 0 0
2 A 5 0 1 1 1 1
2 B 6 0 0 1 1 0
2 C 7 1 0 0 0 1
M 8 1 1 1 0 1
M
24
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Ò!
Reguły asocjacyjne (A B)
Podstawowe miary w analizie asocjacji:
" Wsparcie (Support)
(suma transakcji zawierajÄ…cych produkt A i B)
P(A)" B)=
(suma wszystkich transakcji )
" Zaufanie (Confidence)
P(A)" B)
(suma transakcji zawierajÄ…cych produkt A i B)
P(B | A)= =
P(A)
(suma transakcji zawierajÄ…cych produkt A)
" Oczekiwane zaufanie (Expected Confidence)
(suma transakcji zawierajÄ…cych produkt B)
P(B)=
(suma wszystkich transakcji )
" Korelacja asocjacyjna (Lift)
Zaufanie
Oczekiwane zaufanie
25
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
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.
NW
Nie Tak
Nie 500 2500
3000
AC
1500 4500
Tak 6000
2000 7000 9000
AC NW
Support = 50%
Confidence = 75%
Expected Confidence = 77,8%
Lift = 0,75/0,778 = 0.96 < 1 brak zależności
26
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
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.
Dom
Nie Tak
Nie 1000 500
1500
AC
2000 3500
Tak 5500
3000 4000 7000
AC Dom
Support = 50%
Confidence = 64%
Expected Confidence = 57%
Lift = 0,64/0,57 = 1,12>1 badana reguła jest prawdziwa
27
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
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
28
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ą
e" Ć
Odkrywanie reguł asocjacyjnych:
1. Należy znalez
ć 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}
30
Ò!
{B, C} {A}
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Schemat analizy asocjacji w SAS Enterprise Miner
Diagram gwiaz
dzisty
31
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
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.
32
DATA MINING  nr przedmiotu 233100-0997
Zakład Analizy Historii Zdarzeń i Analiz Wielopoziomowych ISiD SGH
dr Wioletta Grzenda
Dziękuję za uwagę !
33