marcin.mazurek@wat.edu.pl 2006
Analiza skupień
marcin.mazurek@wat.edu.pl 2006
Analiza skupień
Sformułowanie problemu
Analiza, której celem jest ułożenie obiektów w grupy w taki sposób, aby stopień powiązania
obiektów z obiektami należącymi do tej samej grupy był jak największy, a z obiektami z
pozostałych grup jak najmniejszy.
Analiza skupień jedynie wykrywa struktury w danych bez wyjaśniania dlaczego one
występują.
Podstawą grupowania w większosci algorytmów jest podobieństwo pomiędzy elementami -
wyrażone przy pomocy funkcji podobieństwa.
Przykłady zastosowań
Amerykańska armia wydawała zbyt dużo na utrzymanie pełnej „rozmiarówki” mundurów
dla kobiet. Postanowiono przeprowadzić badania, które wskazałyby czy nie ma grup
„rozmiarowych” wśród kobiet, tak że w magazynie można będzie przechowywać wyłącznie
mundury o rozmiarze charakterystycznym dla każdej z grup.
(Berry, Linoff, 1997)
podział wszystkich gwiazd na białe karły, czerwone giganty oraz główną grupę
segmentacja klientów w banku na podstawie sposobu użycia kart kredytowych – według
rodzaju dokonywanych zakupów, ilości wydawanych pieniędzy, częstości używania karty,
miejsca zamieszkania.
zidentyfikowane grupy mogą być przydatne dla celów marketingowych- odpowiednie
materiały reklamowe.
Metryki (miara odległości)
Odległość pomiędzy dwoma punktami x,y w n-wymiarowej
przestrzeni:
- miara Euklidesowa
∑
=
−
=
n
i
j
i
x
x
y
x
d
1
2
2
)
(
)
,
(
- miara w przestrzeni ulicznej
∑
=
−
=
n
i
j
i
x
x
y
x
d
1
1
)
,
(
- miara Minkovskego
(
)
p
p
n
i
j
i
p
x
x
y
x
d
1
1
)
,
(
−
=
∑
=
Dla p=2 miara Minkovskego jest metryką Euklidesową, dla
p=1 uliczną
Miara podobieństwa wektorów binarnych
Niech dane będą dwa n-wymiarowe binarne wektory x o raz y.
x
i
∈
{0,1} i=1.n
y
i
∈
{0,1} i=1.n
x
1
0
1
a
b
y
0
c
d
a – liczba atrybutów, dla których x
i
=1 oraz y
i
=1
b – liczba atrybutów, dla których x
i
=0 oraz y
i
=1
c – liczba atrybutów, dla których x
i
=1 oraz y
i
=0
d – liczba atrybutów, dla których x
i
=0 oraz y
i
=0
Miary podobieństwa pomiędzy dwoma punktami opisanymi w n-wymiarowej przestrzeni cechami binarnymi.
- Simple Matching Coefiicient (SMC)
d
c
b
a
d
a
x
x
S
j
i
SMC
+
+
+
+
=
)
,
(
- Jacard Coefficient
c
b
a
a
x
x
S
j
i
je
+
+
=
)
,
(
- Rao’s Cofficient
d
c
b
a
a
x
x
S
j
i
rc
+
+
+
=
)
,
(
Miara podobieństwa wektorów binarnych
Przykład:
Niech będą dane dwa wektory w 8 wymiarowej przestrzeni:
x=[0,0,1,1,0,1,0,1];
y=[0,1,1,0,0,1,0,0]
Elementy macierzy koincydencji wynoszą odpowiednio:
a = 2
(gdyż wektory są zgodne na 2 pozycjach: dla i=3 oraz i=6)
b = 1
( tylko na pozycji i=2 y przyjmuje wartość 1 a x 0)
c = 2
(dla i=4 oraz i=8)
d = 3
(dla i=1, 5, oraz 7 zarówno x jak i y mają składowe równe 0).
S
SMC
= 5 / 8
S
je
= 2 / 5
S
rc
= 2 / 8
Inne miary
Mutual Neighbor Distance (MND)
MND (x,y) = NN(x,y) + NN(y,x).
NN(x,y) – kolejność sąsiedztwa x w odniesieniu do y. Jeżeli x jest jest najbliższym sąsiadem y, NN(x,y)=1,
jeżeli drugim w kolejności NN(x,y)=2, itd...
Przykład:
MND(A,B) = NN(B,A) + NN(A,B)
NN(A, B) = 1
NN(B,A) = 1
MND (A,B) = 2
MND(B,C) = NN(B,C) + NN(C,B)
NN(B,C) = 1
NN(C,B) = 2
MND(B,C) = 3
MND(A,C) = NN(A,C) + NN(C,A)
NN(A,C) = 2
NN(C,A) = 2
MND(A,C) = 4
A
B
C
Algorytmy wyznaczania skupień
Algorytmy hierarchiczne
grupowania, aglomeracyjne (
agglomerative
)
Każdy punkt wyznacza oddzielne skupienie, w kolejnych krokach łączymy
najbliższe skupienia.
podziału, rozdzielające (
divisible
)
Wszystkie punkty należą do tego samego skupienia, w kolejnych krokach
dokonujemy podziału na mniejsze skupienia. Algorytm powtarzamy dla
każdego z otrzymanych po podziale skupień.
Metody rozdzielające są bardziej wymagające obliczeniowo i są stosowane
w węższym zakresie niż metody aglomeracyjne.
Algorytmy niehierarchiczne
algorytm k-średnich
Odległości skupień
Funkcje oceny
T – suma kwadratów odległości
między parami punktów próby.
WC – suma kwadratów odległości
pomiędzy parami punktów
należących do tego samego
skupienia
BC – suma kwadratów odległości
pomiędzy parami punktów
należących do różnych skupień.
T = const , (W →min) (B → max)
m – środki skupień (średnie
wektorowe)
Bezpośrednie rozwiązania zadania
optymalizacji jest niemożliwe ze
względu na złożoność obliczeniową!
Liczba możliwych podziałów zbioru k
elementów na K grup:
Zadanie pochodne – minimalizacja
sumy W
RMSSTD (root-mean-square standard
deviation)
(
)
(
)
(
)
(
)
(
)
(
)
2
1
1
2
1
2
1
2
1
2
1
1
1
,
2
1
,
2
1
,
2
,
,
,
,
k
k
k
k
k
k
k
k
n
n
i
j
i
j
K
i
j
k
i C
j C
K
i
j
k
i C
j C
i
K
i C
i
k
k
k
k
i C
k
k
i
k
i C
K
K
i
k
k
k
i C
k
T
d
T
WC
BC
WC
d
BC
d
WC
d
n
n
W
d
W
d
W
=
=
=
∈
∈
=
∈
∉
∈
=
∈
∈
=
∈
=
=
=
+
=
=
=
⋅
=
=
=
=
∑∑
∑ ∑ ∑
∑ ∑ ∑
∑
∑ ∑
∑
∑ ∑
∑
x x
x x
x x
x
x m
m
x m
x m
( )
1
1
1
!
K
K k
n
k
K
k
k
K
−
=
−
∑
(
)
1
K
K
W
RMSSTD
N
=
−
Hierarchiczne grupowanie
Mając daną macierz odległości pomiędzy skupieniami
wyznacza się parę skupień najmniej odległych od siebie.
Znalezione skupienia łączy się w jedno.
Wyznacza się odległości wszystkich pozostałych skupień do
nowo utworzonego skupienia.
Powyższe operacje powtarza się aż do chwili, kiedy wszystkie
obiekty utworzą jedno skupienie.
Modyfikacja macierzy odległości
P,Q łączone skupienia –
P powiększane jest o wszystkie elementy z Q
J – skupienie dla którego wyznaczmy zmodyfikowaną odległość
n
p
– liczba elementów należących do skupienia P
n
q
– liczba elementów należących do skupienia Q
n
j
– liczba elementów należących do skupienia J
Reguła aktualizacji odległości Lance-Williams:
qj
pj
pq
qj
q
pj
p
pj
d
d
c
bd
d
a
d
a
d
−
+
+
+
=
2
2
2
2
2
2
qj
pj
pq
qj
q
pj
p
pj
d
d
c
bd
d
a
d
a
d
−
+
+
+
=
Wyznaczanie odległości skupień
Odmienność najbliższego sąsiada (single linkage) -> efekt
łańcuchowy
Odmienność najdalszego sąsiada (complete linkage)-> skupienia
kuliste
Average
Median, centroid, Ward
wymagają istnienia tabeli z danymi, a nie tylko macierzy odległości
skupienia mogą być reprezentowane przez ich środek.
Wyznaczanie odległości skupień
Metoda
Opis
a
p
a
q
b
c
najdalsze
sąsiedztwo
complete linkage
Największa odległość spośród wszystkich
odległości między punktami należącymi do
różnych skupień
0,5
0,5
0
0,5
max{d
pj
,d
qj
}
najbliższe
sąsiedztwo
single linkage
Najmniejsza odległość spośród wszystkich
odległości między punktami należącymi do
różnych skupień
0,5
0,5
0
-0,5
min{d
pj
,d
qj
}
mediana
median linkage
odległość środkowa ze wszystkich odległości
pomiędzy punktami należącymi do różnych
skupień.
0,5
0,5
-0,25
0
0,5d
pj
+0,5d
qj
-
0,25d
pq
ś
rednia
grupowa
Weighted
average linkage
ś
rednia arytmetyczna wyznaczona ze
wszystkich odległości elementów tworzących
te skupienia
q
p
p
n
n
n
+
q
p
q
n
n
n
+
0
0
q
p
pj
p
qj
q
n
n
d
n
d
n
+
⋅
+
⋅
ś
rodek
cieżkości
centroid linkage
różnica odległości środków ciężkości
q
p
p
n
n
n
+
q
p
q
n
n
n
+
(
)
2
q
p
q
p
n
n
n
n
+
⋅
−
0
Ward
Minimalizacja wariancji wewnątrz skupień
i
q
p
i
p
n
n
n
n
n
+
+
+
i
q
p
i
q
n
n
n
n
n
+
+
+
i
q
p
i
n
n
n
n
+
+
−
0
Przykład
Założenie:
- metryka Euklidesowa
- metoda najbliższe sąsiedztwa
Skupienie
Q1
Q2
Q3
Q4
Q5
Q1 {X1}
-
Q2 {X2}
2
-
Q3 {X3}
1
2,23
-
Q4 {X4}
5
5,39
4
-
Q5 {X5}
5,39
5
4,47
2
-
Skupienie
Q1
Q2
Q4
Q5
Q1 {X1,X3}
-
Q2 {X2}
2
-
Q4 {X4}
4
5,39
-
Q5 {X5}
4,47
5
2
-
Skupienie
Q1
Q4
Q5
Q1 {X1,X2,X3}
-
Q4 {X4}
4
-
Q5 {X5}
4,47
2
-
Skupienie
Q1
Q4
Q1 {X1,X2,X3}
-
Q4 {X4. X5}
4
-
Dendrogram :
Q1
Q3
Q2
Q4
Q5
1
2
4
Hierarchiczny podział
Wybór skupienia do podziału:
każde skupienie jest dzielone (pełne drzewo binarne)
dzielone jest skupienie o największej liczbie elementów
dzielone jest skupienie o największym rozrzucie elementów
Dla każdego istniejącego obiektu wyznacza się parę
najbardziej odległych od siebie obiektów, a następnie pośród
par wybiera się tę, dla której odległość jest największa.
Skupienie dzieli się na dwa, tak by obiekty z wyznaczonej
pary trafiły od różnych skupień
Rozdziela się pozostałe z obiektów ze skupienia do jednego z
dwóch powstałych skupień.
Operacje powyższe powtarza się aż do momentu otrzymania
liczby skupień równej liczbie obiektów.
Metody rozdziału (divisive algorithms)
Należy przydzielić punkt X do jednego ze
skupień C1, C2.. CN
W każdym utworzonym skupieniu
wyszukujemy punkt najbardziej oddalony
od punktu X. Punkt X zostaje przydzielony
do tego skupienia, w którym odległość do
znalezionego punktu jest najmniejsza.
W każdym istniejącym skupieniu
wyszukujemy punkty leżące najbliżej X.
Punkt X zostaje przydzielony od tego
skupienia, w którym odległość jest
najmniejsza.
Niehierarchiczne algorytmy
Algorytm k-średnich (k-means), [Forgy 1965]
1.
Inicjalny (losowy) podział całej próbki na K podzbiorów.
2.
Generacja nowego podziału w oparciu o przyporządkowanie każdego
punktu do „najbliższego” skupienia
3.
Wyliczenie środków nowych skupień
4.
Iteracyjne powtórzenie kroków 2 i 3 aż do momentu, kiedy
osiągniemy ekstremum funkcji kryterium bądź nie będzie zmian w
przyporządkowaniu elementów do skupień.
Przykład
K = 2 - liczba skupień
Początkowy przydział punktów do skupień (wygenerowany losowo):
C
1
= { X1, X3, X5}
C
2
= { X2, X4}
Ś
rodki ciężkości skupień:
+
+
+
+
=
3
3
1
1
,
3
6
2
1
1
M
=
3
5
,
3
1
M
+
+
=
2
1
3
,
2
6
1
2
M
=
2
,
2
1
3
2
M
Wariancje wewnątrz skupień:
2
2
2
1
1
1
3
1
5
1
(
,
)
(
,
)
(
,
)
W
d X M
d X M
d X M
=
+
+
(
)
(
)
2
2
2
2
2
2
1
5
5
5
(1 3)
1
2 3
1
6 3
3
16, 67
3
3
3
W
=
−
+
−
+
−
+
−
+
−
+
−
=
2
2
2
2
2
4
2
(
,
)
(
,
)
W
d X M
d X M
=
+
(
)
(
)
2
2
2
2
2
1
1
(1 3 )
3 2
1 3
6 2
14,5
2
2
W
=
−
+
−
+
−
+
−
=
Całkowita wariancja wewnątrzskupieniowa:
1
2
31,17
W
W
W
=
+
=
Zmiana przydziału obiektów od skupień na podstawie ich odległości od środków ciężkości skupień:
(3 , 5/3 )
(3.5 , 2 )
(1,1)
d(X
1
, M
1
)=2,1
d(X
1
, M
2
)=2,69
X
1
∈
C
1
(1,3)
d(X
2
, M
1
)=2,4
d(X
2
, M
2
)=2,69
X
2
∈
C
1
(2,1)
d(X
3
, M
1
)=1,2
d(X
3
, M
2
)=1,80
X
3
∈
C
1
(6,1)
d(X
4
, M
1
)=3,07
d(X
4
, M
2
)=2,69
X
4
∈
C
2
(6,3)
d(X
5
, M
1
)=3,28
d(X
5
, M
2
)=2,69
X
5
∈
C
2
Kolejna iteracja:
Przydział punktów do skupień
C
1
= { X1, X2, X3 }
C
2
= { X4, X5}
Ś
rodki ciężkości skupień:
+
+
+
+
=
3
1
3
1
,
3
2
1
1
1
M
=
3
5
,
3
4
1
M
+
+
=
2
3
1
,
2
6
6
2
M
(
)
2
,
6
2
=
M
Wariancje wewnątrz skupień:
2
2
2
1
1
1
2
1
3
1
(
,
)
(
,
)
(
,
)
3,33
W
d X M
d X M
d X M
=
+
+
=
2
2
2
4
2
5
2
(
,
)
(
,
)
2
W
d X M
d X M
=
+
=
Całkowita wariancja wewnątrzskupieniowa:
1
2
5,33
W
W
W
=
+
=
Zmiana przydziału obiektów od skupień na podstawie ich odległości od środków ciężkości skupień:
(4/3 , 5/3 )
(6, 2 )
(1,1)
d(X
1
, M
1
)=0,74
d(X
1
, M
2
)=5,10
X
1
∈
C
1
(1,3)
d(X
2
, M
1
)=1,37
d(X
2
, M
2
)=5,10
X
2
∈
C
1
(2,1)
d(X
3
, M
1
)=0,94
d(X
3
, M
2
)=4,12
X
3
∈
C
1
(6,1)
d(X
4
, M
1
)=4,71
d(X
4
, M
2
)=1
X
4
∈
C
2
(6,3)
d(X
5
, M
1
)=4,84
d(X
5
, M
2
)=1
X
5
∈
C
2
Zadanie 1
Mając dany zbiór obserwacji:
X1 = {1, 0},
X2 = {0, 1},
X3 = {2, 1},
X4 = {3, 3},
zgrupowanych inicjalnie w dwa skupienia:
C1 = {X1, X3}
C2 = {X2, X4}.
Wykonaj pierwszą iterację algorytmu K-means. Wyznacz nowe środki
skupień?
O ile zmieniła się wariancja wewnątrz skupień W ?
Wykonaj drugą iterację algorytmu.
Literatura
Hand David, Mannila Heikki, Smyth Padhraic „Eksploracja
danych”, WNT 2005
Mehmed Kantardzic „Data Mining: Concepts, Models,
Methods, and Algorithm” Wiley & Sons 2003
Jacek Koronacki, Jan Ćwik „Statystyczne systemy uczące
się”, WNT 2005