[e-mail] 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