Analiza Skupień - Grupowanie
Zaawansowana Eksploracja Danych
JERZY STEFANOWSKI
Inst. Informatyki PP
Wersja dla TPD 2009
Email: [e-mail]
Organizacja wykładu
" Wprowadzenie.
" Możliwe zastosowania
" Podstawy (odległości, & ) .
" Przegląd algorytmów:
" k - średnich
" Hierarchiczne
" Rozszerzenia dla analizy danych o większych
rozmiarach.
" Podsumowanie
� Stefanowski 2009
� Stefanowski 2005
Polish aspects in clustering
Polish terminology:
" Cluster Analysis Analiza skupień, Grupowanie.
" Numerical taxonomy Metody taksonomiczne (ekonomia)
" Uwaga: znaczenie taksonomii w biologii może mieć inny
kontest (podział systematyczny oparty o taksony).
" Cluster Skupienie, skupisko, grupa/klasa/pojęcie
" Nigdy nie mów: klaster, klastering, klastrowanie!
History:
� Stefanowski 2009
More on Polish History
" Jan Czekanowski (1882-1965) - wybitny polski antropolog,
etnograf, demograf i statystyk, profesor Uniwersytetu
Lwowskiego (1913  1941) oraz Uniwersytetu Poznańskiego
(1946  1960).
" Nowe odległości i metody przetwarzania macierzy odległości w
algorytmach, & , tzw. metoda Czekanowskiego.
" Kontynuacja Jerzy Fierich (1900-1965) Kraków
" Hugo Steinhaus, (matematycy Lwów i Wrocław)
" Wrocławska szkoła taksonomiczna (metoda dendrytowa)
" Zdzisław Hellwig (Wrocław)
" wielowymiarowa analizą porównawcza, i inne &
" Współczesnie &
"  Sekcja Klasyfikacji i Analizy Danych (SKAD) Polskiego
Towarzystwa Statystycznego
� Stefanowski 2009
Referencje do literatury (przykładowe)
" Koronacki J. Statystyczne systemy uczące się, WNT
2005.
" Pociecha J., Podolec B., Sokołowski A., Zając K.  Metody
taksonomiczne w badaniach społeczno-ekonomicznych .
PWN, Warszawa 1988,
" Stąpor K.  Automatyczna klasyfikacja obiektów
Akademicka Oficyna Wydawnicza EXIT, Warszawa 2005.
" Hand, Mannila, Smyth,  Eksploracja danych , WNT 2005.
" Larose D:  Odkrywania wiedzy z danych , PWN 2006.
" Kucharczyk J.  Algorytmy analizy skupień w języku
ALGOL 60 PWN Warszawa, 1982,
" Materiały szkoleniowe firmy Statsoft.
� Stefanowski 2009
Problem Statement
Given a set of records, organize
the records into clusters (classes)
" Clustering: the process of grouping physical or
abstract objects into classes of similar objects
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
0 0
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10
� Stefanowski 2009
Przykłady zastosowań analizy skupień
" Zastosowania ekonomiczne:
" Identyfikacja grup klientów bankowych (np. właścicieli kart
kredytowych wg. sposobu wykorzystania kart oraz stylu życia,
danych osobowych, demograficznych) cele marketingowe.
" Systemy rekomendacji produktów i usług.
" Rynek usług ubezpieczeniowych (podobne grupy klientów).
" Analiza sieci sprzedaży (np. czy punkty sprzedaży podobne
pod względem społecznego sąsiedztwa liczby personelu, itp.,
przynoszą podobne obroty).
" Poszukiwanie wspólnych rynków dla produktów.
" Planowanie, np. nieruchomości.
" Badania naukowe (biologia, medycyna, nauki społeczne).
" Analiza zachowań użytkowników serwisów WWW.
" Rozpoznawanie obrazów, dz
więku
" Wiele innych
� Stefanowski 2009
Poszukiwanie  zrozumiałych struktur w danych
" Ma ułatwiać odnalezienie pewnych spójnych podobszarów danych
" Lecz nadal wiele możliowości
� Stefanowski 2009
Nadzorowane vs. nienadzorowane problemy
� Stefanowski 2009
Ocena grupowania
" Inna niż w przypadku uczenia nadzorowanego (predykcji
wartości)
" Poprawność grupowania zależna od oceny obserwatora /
analityka
" Różne metody AS są skuteczne przy różnych rodzajach
skupień i założeniach, co do danych:
" Co rozumie się przez skupienie, jaki ma kształt, dobór miary
odległości sferyczne vs. inne
" Dla pewnych metod i zastosowań:
" Miary zmienności wewnątrz i między  skupieniowych
" Idea zbiorów kategorii odniesienia (np.TREC)
� Stefanowski 2009
Oceny poprzez porównanie do zbioru referencyjnego (ground truth)
" Przykład tekstowy
� Stefanowski 2009
Różne sposoby reprezentacji skupień
d
(a) (b)
e
d
e
a c
j
a c
j
h
k b
h
f
k b
f
i
g
i
g
(c) 1 2 3 (d)
a 0.4 0.1 0.5
b 0.1 0.8 0.1
c 0.3 0.3 0.4
d 0.1 0.1 0.8
g a c i e d k b j f h
e 0.4 0.2 0.4
f 0.1 0.4 0.5
g 0.7 0.2 0.1
h 0.5 0.4 0.1
&
� Stefanowski 2009
Main Categories of Clustering Methods
" Partitioning algorithms: Construct various partitions and
then evaluate them by some criterion.
" Hierarchy algorithms: Create a hierarchical decomposition
of the set of data (or objects) using some criterion.
" Density-based: based on connectivity and density functions
" Grid-based: based on a multiple-level granularity structure
" Model-based: A model is hypothesized for each of the
clusters and the idea is to find the best fit of that model to
each other.
� Stefanowski 2009
Jeszcze inny podział
" Za Jain s tutorial
" Ponadto:
" Crisp vs. Fuzzy
" Inceremental vs. batch
� Stefanowski 2009
Partitioning Algorithms: Basic Concept
" Partitioning method: Construct a partition of a database D of n
objects into a set of k clusters
" Given a k, find a partition of k clusters that optimizes the
chosen partitioning criterion.
" Global optimal: exhaustively enumerate all partitions.
" Heuristic methods: k-means and k-medoids algorithms.
" k-means (MacQueen 67): Each cluster is represented by
the center of the cluster
" k-medoids or PAM (Partition around medoids) (Kaufman &
Rousseeuw 87): Each cluster is represented by one of the
objects in the cluster.
� Stefanowski 2009
Algorytmy podziałowo - optymalizacyjne
" Zadanie: Podzielenie zbioru obserwacji na K zbiorów
elementów (skupień C), które są jak najbardziej
jednorodne.
" Jednorodność  funkcja oceny.
" Intuicja zmienność wewnątrzskupieniowa wc(C) i
zmienność międzyskupieniowa bc(C)
" Możliwe są różne sposoby zdefiniowania
1
rk =
"x"Ck x
" Np. wybierzmy środki skupień rk (centroidy)
nk
K
" Wtedy
wc(C) =
""x"Ck d(x,rk )2
k=1
bc(C) =
"1d" j� Stefanowski 2009
Podstawowe algorytmy podziałowe
" Metoda K - średnich minimalizacja wc(C)
" Przeszukiwanie przestrzeni możliwych przypisań bardzo
kosztowne (oszacowanie w ks. Koronackiego)
" Problem optymalizacji kombinatorycznej systematyczne
przeszukiwanie metodą iteracyjnego udoskonalania:
" Rozpocznij od rozwiązania początkowego (losowego).
" Ponownie przypisz punkty do skupień tak, aby otrzymać
największą zmianę w funkcji oceny.
" Przelicz zaktualizowane środki skupień, &
" Postępuj aż do momentu, w którym nie ma już żadnych zmian w
funkcji oceny lub w składzie grup.
" Zachłanne przeszukiwanie proste i prowadzi do co najmniej
lokalnego minimum. Różne modyfikacje, np. rozpoczynania od kilku
rozwiązań startowych
" Złożoność algorytmy K - średnich O(KnI)
� Stefanowski 2009
Simple Clustering: K-means
Basic version works with numeric data only
1) Pick a number (K) of cluster centers - centroids (at
random)
2) Assign every item to its nearest cluster center (e.g. using
Euclidean distance)
3) Move each cluster center to the mean of its assigned
items
4) Repeat steps 2,3 until convergence (change in cluster
assignments less than a threshold)
� Stefanowski 2009
Przykład (z macierzą początkową)
1 1 1 2 3
Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń#
x1 = x2 = x3 = x4 = x5 =
" Zbiór danych:
ó#2Ą# ó#3Ą# ó#4Ą# ó#1Ą# ó#1Ą#
Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś#
3 4 5 5 5
Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń#
x6 = x7 = x8 = x9 = x10 =
ó#3Ą# ó#1Ą# ó#2Ą# ó#3Ą# ó#4Ą#
Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś#
1 0 0 0 1 0 0 0 1 0
Ą# ń#
ó#0
B(0) = 1 0 1 0 1 0 1 0 1Ą#
ó# Ą#
" Początkowy przydział
ó#0 0 1 0 0 0 1 0 0 0Ą#
Ł# Ś#
3 3.2 2.5
Ą# ń#
" Przeliczenie centroidów
R(0) =
ó#2 2.6 2.5Ą#
Ł# Ś#
" Przeliczenie odległości
2 2.24 2.83 1.41 1 1 1.41 2 2.24 2.83
Ą# ń#
ó#2.28 2.24 2.61 2 1.61 0.45 1.79 1.9 1.84 2.28Ą#
D(1) =
ó# Ą#
ó#1.58 1.58 2.12 1.58 1.58 0.71 2.12 2.55 2.55 2.91Ą#
Ł# Ś#
" Ponowny przydział do skupień:
0 0 0 1 1 0 0 0 0 0
Ą# ń#
ó#0
B(1) = 0 0 0 0 1 0 1 1 1Ą#
ó# Ą#
ó#1 1 1 0 0 0 1 0 0 0Ą#
Ł# Ś#
� Stefanowski 2009
Przykład cd.
3 5 1.5
Ą# ń#
R(1) =
ó#1 3 3 Ą#
" Przeliczenie centroidów
Ł# Ś#
0 0 0 1 1 0 0 0 0 0
Ą# ń#
" Ponowny przydział do skupień:
ó#0
B(2) = 0 0 0 0 1 0 1 1 1Ą#
ó# Ą#
ó#1 1 1 0 0 0 1 0 0 0Ą#
Ł# Ś#
" Warunek końcowy: B(2) = B(1)
G1 = {x4, x5, x7} G2 = {x8, x9, x10} G3 = {x1, x2, x3, x6}
� Stefanowski 2009
K-means example, step 1
k1
Y
Pick 3
k2
initial
cluster
centers
(randomly)
k3
X
� Stefanowski 2009
K-means example, step 2
k1
Y
k2
Assign
each point
to the closest
cluster
k3
center
X
� Stefanowski 2009
K-means example, step 3
k1 k1
Y
Move k2
each cluster
k3
center
k2
to the mean
of each cluster
k3
X
� Stefanowski 2009
K-means example, step 4
Reassign
k1
points
Y
closest to a
different new
cluster center
k3
k2
Q: Which
points are
reassigned?
X
� Stefanowski 2009
K-means example, step 4 &
k1
Y
A: three
points with
animation
k3
k2
X
� Stefanowski 2009
K-means example, step 4b
k1
Y
re-compute
cluster
means
k3
k2
X
� Stefanowski 2009
K-means example, step 5
k1
Y
k2
move cluster
k3
centers to
cluster means
X
� Stefanowski 2009
Discussion
" Result can vary significantly depending on initial
choice of seeds
" Can get trapped in local minimum
" Example: initial cluster
centers
instances
" To increase chance of finding global optimum: restart
with different random seeds
� Stefanowski 2009
K-means clustering summary
Advantages Disadvantages
" Simple, understandable " Must pick number of
clusters before hand
" items automatically
assigned to clusters " Often terminates at a
local optimum.
" All items forced into a
cluster
" Too sensitive to outliers
� Stefanowski 2009
The K-Medoids Clustering Method
" Find representative objects, called medoids, in clusters
" To achieve this goal, only the definition of distance from any
two objects is needed.
" PAM (Partitioning Around Medoids, 1987)
" starts from an initial set of medoids and iteratively replaces
one of the medoids by one of the non-medoids if it improves
the total distance of the resulting clustering.
" PAM works effectively for small data sets, but does not
scale well for large data sets.
" CLARA (Kaufmann & Rousseeuw, 1990)
" CLARANS (Ng & Han, 1994): Randomized sampling.
" Focusing + spatial data structure (Ester et al., 1995).
� Stefanowski 2009
*Hierarchical clustering
" Bottom up (aglomerative)
" Start with single-instance clusters
" At each step, join the two closest clusters
" Design decision: distance between clusters
" e.g. two closest instances in clusters
vs. distance between means
" Top down (divisive approach)
" Start with one universal cluster
" Find two clusters
" Proceed recursively on each subset
" Can be very fast
" Both methods produce a
dendrogram
g a c i e d k b j f h
� Stefanowski 2009
Hierarchical Clustering
" Use distance matrix as clustering criteria. This method
does not require the number of clusters k as an input, but
needs a termination condition. The distance between
clusters should also be chosen.
Step 1 Step 2 Step 3 Step 4
Step 0
agglomerative
(AGNES)
a
a b
b
a b c d e
c
c d e
d
d e
e
divisive
Step 3 Step 2 Step 1 Step 0
Step 4
(DIANA)
� Stefanowski 2009
Distance between Clusters
Single linkage
dmin (Ci,Cj ) = min p - p'
p"Ci , p' "C
minimum distance:
j
Complete linkage
dmax (Ci,Cj ) = max p - p'
p"Ci , p' "Cj
maximum distance:
dmean (Ci,Cj ) = mi - mj
mean distance:
dave(Ci,Cj ) = 1/ (ninj ) p - p'
" "
average distance:
p"Ci j
p' "C
ni
mi Ci Ci
is the mean for cluster is the number of points in
� Stefanowski 2009
Problem doboru miary odległości / podobieństwa
" Nietrywialny i silnie wpływa na wynik
" Różne miary odległości
� Stefanowski 2009
Single Link Example
� Stefanowski 2009
Complete Link Example
� Stefanowski 2009
Changing Linkage Methods
Diagram dla 22 przyp.
Pojedyncze wiązanie
Odległości euklidesowe
ACURA
AUDI
MERCEDES
CHRYSLER
DODGE
VW
HONDA
PONTIAC
SAAB
VOLVO
NISSAN
BMW
MITSUB.
BUICK
OLDS
MAZDA
TOYOTA
CORVETTE
FORD
PORSCHE
ISUZU
Diagram dla 22 przyp.
EAGLE
Metoda Warda
0,0 0,5 1,0 1,5 2,0 2,5 3,0 3,5 4,0 4,5
Odległości euklidesowe
Odległość wiąz.
ACURA
OLDS
CHRYSLER
DODGE
VW
HONDA
PONTIAC
NISSAN
MITSUB.
AUDI
MERCEDES
BMW
SAAB
VOLVO
BUICK
MAZDA
TOYOTA
FORD
CORVETTE
PORSCHE
EAGLE
ISUZU
0 1 2 3 4 5 6 7 8
� Stefanowski 2009 Odległość wiąz.
Maning  texts  single linkage
� Stefanowski 2009
Maning  texts / complete linkage
� Stefanowski 2009
Single vs. Complete Linkage
" A.Jain et al.: Data Clustering. A Review.
� Stefanowski 2009
Single vs. complete linkage
� Stefanowski 2009
Pamiętaj o doborze cech
" Za Jain s tutorial
� Stefanowski 2009
Expectation-Maximization (EM)
" Log likelihood with a mixture model
( )
L(Ś | X)= log p xt | Ś
"
t
k
()
= p xt | Gi P(Gi)
"t log"
i=1
" Assume hidden variables z, which when
known, make optimization much simpler
" Complete likelihood, Lc(Ś |X,Z), in terms of x
and z
" Incomplete likelihood, L(Ś |X), in terms of x
� Stefanowski 2009
Jain  zbiorcze porównanie
� Stefanowski 2009
Algorytmy analizy skupień dla baz danych o wielkich
rozmiarach
" Scalability
" Dealing with different types of attributes
" Discovery of clusters with arbitrary shape
" Minimal requirements for domain knowledge to determine
input parameters
" Able to deal with noise and outliers
" Insensitive to order of input records
" High dimensionality
" Interpretability and usability.
� Stefanowski 2009
Algorytm K-Medoids
" Znajdz
medoidy - obiekty reprezentujące skupienia
" Wykorzystuje się odległości par obiektów.
" PAM (Partitioning Around Medoids, 1987)
" Zacznij od początkowego zbioru medoidów i
krokowo zamieniaj jeden z obiektów - medoidów
przez obiekt, nie będący aktulanie medoidem, jeśli
to polepsza całkowitą odległość skupień.
" PAM  efektywny dla małych zbiorów, lecz
nieskalowalny dla dużych zbiorów przykładów.
" CLARA (Kaufmann & Rousseeuw, 1990)
" CLARANS (Ng & Han, 1994):  Randomized sampling .
� Stefanowski 2009
Metody hierarchiczne dla dużych zbiorów danych
" Niektóre z ograniczeń metod aglomeracyjnych:
" słaba skalowalność: złożoność czasowa przynajmniej O(n2), gdzie n jest
liczbą obiektów,
"  krytyczne znaczenie decyzji o wyborze punktu połączenia kolejnych
skupień w trakcie budowania drzewa hierarchii,
" algorytmy nie zmieniają, ani nie poprawiają, wcześniej podjętych decyzji.
" Rozwinięcia algorytmów hierarchicznych oraz ich integracja z metodami
gęstościowymi:
" BIRCH (1996): użycie drzew  CF-tree , uczenie przyrostowe i stopniowa
poprawa jakości pod-skupień.
" CURE (1998): wybór losowy odpowiednio rozproszonych punktów,
wstępne grupowanie z określeniem ich punktów reprezentatywnych,
łączenie grup w nowe skupienia wraz z przesuwaniem punktów
reprezentatywnych w stronę środków tworzonego skupienia zgodnie z
 shrinking factor ą  ; eliminacja wpływu  outliners .
� Stefanowski 2009
BIRCH  ang. Balanced Iterative Reducing and
Clustering using Hierarchies  Zhang et al. (1996)
" Wykorzystuje hierarchiczne drzewo CF (Clustering Feature)
" Działanie algorytmu:
" Faza 1: przyrostowo przeczytaj raz DB w celu zbudowania w
pamięci początkowej struktury drzewa CF (rodzaj wielopoziomowej
kompresji danych zachowującej wewnętrzną strukturę zgrupowań
danych).
" Faza 2: zastosuj wybrany (inny) algorytm skupień dla lepszego
pogrupowania obiektów w liściach drzewa CF.
" Dobra skalowalność: znajduje zadawalające grupowanie po
jednokrotnym przeczytaniu bazy danych i ulepsza je wykorzystując
niedużo dodatkowych operacji odczytu DB.
" Ograniczenia: zaproponowany dla danych liczbowych, wrażliwość
wyników na kolejność prezentacji przykładów.
� Stefanowski 2009
BIRCH - Clustering Feature Vector
Clustering Feature: CF = (N, LS, SS)
N: liczba grupowanych obiektów
LS: "Ni=1=Xi
CF = (5, (16,30),(54,190))
SS: "Ni=1=Xi2
10
(3,4)
9
8
7
(2,6)
6
5
(4,5)
4
3
2
(4,7)
1
0
0 1 2 3 4 5 6 7 8 9 10
(3,8)
� Stefanowski 2009
CF Tree
Root
CF1 CF2 CF3 CF6
B = 7
child1 child2 child3 child6
L = 6
Non-leaf node
CF1 CF2 CF3 CF5
child1 child2 child3 child5
Leaf node Leaf node
prev prev
CF1 CF2 CF6 next CF1 CF2 CF4 next
� Stefanowski 2009
Wstawianie elementów do drzewa CF
" Parametery drzewa CF:
"  Branching factor B  max. liczba potomków w węz
le (non-leaf
node),
"  Threshold T  max. średnica podskupienia skojarzonego z liściem
drzewa.
" Kolejno wczytywany obiekt przydziel do najbliższego podskupienia (leaf
entry)
" zgodnie z wybraną miarą odległości
" Dokonaj modyfikacji liści
" jeśli średnica liścia > T, to dokonaj podziału (być może także inne
liście powinny być podzielone)
" Dokonaj modyfikacji ścieżki do liścia
" Uaktualnij wektory CF w węzłach drzewa. Dokonaj podziału węzłów
jeśli to konieczne.
" Jeżeli rozmiar drzewa CF jest zbyt duży w stosunku do dostępnej
pamięci operacyjnej, dokonuje się modyfikacji parametrów algorytmu.
� Stefanowski 2009
BIRCH: dalsze szczegóły algorytmu
1: Utwórz drzewo CF w pamięci operacyjnej
" przeczytaj przyrostowo DB i buduj początkową strukturę
drzew
2: (Opcjonalnie) Dokonaj kompresji poprzez budowę mniejszego
drzewa CF zmieniając zakres parametrów
" przejrzyj  leaf entries w początkowym drzewie CF w celu
zbudowania mniejszego drzewa.
3: Globalne grupowanie
" grupuj wykorzystując  leaf entries drzewa
4: (opcjonalne,  off line ) Ulepszanie struktury skupień
" Użyj centroidów z etapu 3, rozdzielając obiekty
Complexity: O(N) czy O(N2)?
� Stefanowski 2009
Metody gęstościowe
" Podstawowe metody wykorzystują miary odległości między obiektami
" Inne metody wykorzystują pojęcie gęstości (ang. density)  lokalne
sąsiedztwo punktu/skupienia, a także  gęsto połączonych punktów
" Właściwości metod gęstościowych:
" Wykrywanie skupień o dowolnych kształtach (niesferycznych)
" Odporność na  szum informacyjny
" Jednokrotne przeglądanie DB
" Potrzebna parametryzacja oceny gęstości i warunków zatrzymania
" Interesujące algorytmy:
" DBSCAN: Ester, et al. (KDD 96)
" OPTICS: Ankerst, et al (SIGMOD 99).
" DENCLUE: Hinneburg & D. Keim (KDD 98)
" CLIQUE: Agrawal, et al. (SIGMOD 98)
� Stefanowski 2009
DBSCAN: Algorytm gęstościowy
" DBSCAN: Density Based Spatial Clustering of
Applications with Noise.
" Wykorzystuje pojęcie  density-based cluster : Skupienie
będące maksymalnym zbiorem punktów gęsto połączonych
 density-connected points .
" Poszukuje się zgrupowań odpowiednio gęsto (blisko siebie)
położonych obiektów (dense regions/clusters) odzielonych
od siebie obszarami o niskiej gęstości ( noise )
" Możliwość wykrywania skupień o dowolnym kształcie w
obecności szumu informacyjnego
� Stefanowski 2009
Bardziej nieregularne kształty
� Stefanowski 2009
DBSCAN: Podstawowe pojęcia
Parametry:
" Eps: Maksymalny promień sąsiedztwa
" MinPts: minimalna liczba punktów (obiektów) w
Eps-sąsiedztwie badanego punktu
NEps(p): {punkt q należy do D | dist(p,q) <= Eps}
Directly density-reachable: A point p is directly density-
reachable from a point q wrt. Eps, MinPts if
1) p belongs to NEps(q)
p MinPts = 5
2) core point condition:
q
Eps = 1 cm
|NEps (q)| >= MinPts
� Stefanowski 2009
DBSCAN: Podstawowe pojęcia (II)
Density-reachable:
" A point p is density-reachable
p
from a point q wrt. Eps, MinPts if
there is a chain of points p1, & , p1
q
pn, p1 = q, pn = p such that pi+1 is
directly density-reachable from pi
Density-connected
pq
" A point p is density-connected to
a point q wrt. Eps, MinPts if there
o
is a point o such that both, p and
q are density-reachable from o
wrt. Eps and MinPts.
� Stefanowski 2009
DBSCAN: jak poszukuje skupień?
Outlier
Border
Eps = 1cm
MinPts = 5
Core
� Stefanowski 2009
DBSCAN: Zarys algorytmu
Wybierz punkt startowy p
Odnajdz
wszystkie punkty do gęstościowego osiągnięcia z p
(density-reachable from p wrt Eps and MinPts).
Jeśli p jest rdzeniem (core point), utwórz skupienie.
Jeśli p jest punktem granicznym (border point) i żadne punkty
nie są z niego gęstościowo osiągalne, DBSCAN wybiera
następny punkt z bazy danych
Proces jest konytuowany dopóki żaden nowy punkt nie może
być dodany to dowolnego skupienia.
Złożoność: O(nlog n) w przypadku użycia specjalnego  spatial
index , w przeciwnym razie O(n2).
� Stefanowski 2009
Soft Clustering
" Clustering typically assumes that each instance is given a
 hard assignment to exactly one cluster.
" Does not allow uncertainty in class membership or for an
instance to belong to more than one cluster.
" Soft clustering gives probabilities that an instance belongs
to each of a set of clusters.
" Each instance is assigned a probability distribution across
a set of discovered categories (probabilities of all
categories must sum to 1).
d
e
a c
j
h
k b
f
i
g
� Stefanowski 2009
Expectation Maximization (EM Algorithm)
" Probabilistic method for soft clustering.
" Direct method that assumes k clusters:{c1, c2,& ck}
" Soft version of k-means.
" Assumes a probabilistic model of categories that allows
computing P(ci | E) for each category, ci, for a given
example, E.
" For text, typically assume a na�ve-Bayes category model.
" Parameters � = {P(ci), P(wj | ci): i"{1,& k}, j "{1,& ,|V|}}
� Stefanowski 2009
Model-Based Clustering Methods
" Attempt to optimize the fit between the data and some
mathematical model
" Statistical and AI approach
" Conceptual clustering
" A form of clustering in machine learning
" Produces a classification scheme for a set of unlabeled objects
" Finds characteristic description for each concept (class)
" COBWEB (Fisher 87)
" A popular a simple method of incremental conceptual learning
" Creates a hierarchical clustering in the form of a classification
tree
" Each node refers to a concept and contains a probabilistic
description of that concept
� Stefanowski 2009
COBWEB Clustering Method
A classification tree
� Stefanowski 2009
*Incremental clustering (COBWEB based)
" Heuristic approach (COBWEB/CLASSIT)
" Form a hierarchy of clusters incrementally
" Start:
" tree consists of empty root node
" Then:
" add instances one by one
" update tree appropriately at each stage
" to update, find the right leaf for an instance
" May involve restructuring the tree
" Base update decisions on category utility
� Stefanowski 2009
World countries data
Kraj C1 C2 C3 C4 C5 C6 C7 C8 C9
Afganistan MAPSNNNNNS
Argentyna KAL.U N S WWW N
Armenia OSWSMS S W W W N
Australia POECDS N S W W W N
Austria KOECDU N W W W W N
Azerbejdżan MSWS N W W W W N
Belgia K OCED UWSWWWN
Białoruś OEWU N W W S S N
Boliwia KASM NWSSSS
... ... ... ... ... ... ... ... ... ...
� Stefanowski 2009
COBWB results
K1
Selected classes
K2
" K1: Rosja, Portugalia, Polska, Litwa,
K3
A
otwa, Węgry, Grecja, Gruzja,
K4
Estonia, Czechy, Chorwacja
K5
K6
" K2: USA, Szwajcaria, Hiszpania,
K7
K8
Norwegia, Holandia, Włochy,
K9
Irlandia, Niemcy, Francja, Dania,
K10
Belgia, Austria
K11
K12
" K3: Szwecja, Korea Płd., Nowa
K13
K14
Zelandia, Finlandia, Kanada,
Australia, Islandia
K15
K16
" ...
K17
" K17: Somalia, Gambia, Etiopia,
K18
Kambodża
K19
" K18: Uganda, Tanzania, Ruanda,
Haiti, Burundi
" ...
� Stefanowski 2009
Other Model-Based Clustering Methods
" Neural network approaches
" Represent each cluster as an exemplar, acting as a
 prototype of the cluster
" New objects are distributed to the cluster whose
exemplar is the most similar according to some
dostance measure
" Competitive learning (Kohonen, SOM)
" Involves a hierarchical architecture of several units
(neurons)
" Neurons compete in a  winner-takes-all fashion for
the object currently being presented
� Stefanowski 2009
Self-Organizing Feature Map (SOM)
" SOMs, also called topological ordered maps, or Kohonen Self-
Organizing Feature Map (KSOMs)
" It maps all the points in a high-dimensional source space into a 2 to 3-d
target space, s.t., the distance and proximity relationship (i.e., topology)
are preserved as much as possible
" Similar to k-means: cluster centers tend to lie in a low-dimensional
manifold in the feature space
" Clustering is performed by having several units competing for the
current object
" The unit whose weight vector is closest to the current object wins
" The winner and its neighbors learn by having their weights adjusted
" SOMs are believed to resemble processing that can occur in the brain
" Useful for visualizing high-dimensional data in 2- or 3-D space
� Stefanowski 2009
Self-Organizing Maps - more
Data: vectors XT = (X1, ... Xd) from d-dimensional space.
Grid of nodes, with local processor (called neuron) in each node.
Local processor # j has d adaptive parameters W(j).
Goal: change W(j) parameters to recover data clusters in X space.
� Stefanowski 2009
An example of analysing olive oil in Italy
An example of SOM application:
" 572 samples of olive oil
were collected from 9
Italian provinces.
Content of 8 fats was
determine for each oil.
" SOM 20 x 20 network,
" Maps 8D => 2D.
" Classification accuracy
was around 95-97%.
Note that topographical relations are preserved, region 3 is most diverse.
� Stefanowski 2009
Quality of life data
Quality of life data
Quality of life data
WorldBank data 1992, 39 quality of life indicators.
SOM map and the same colors on the world map.
More examples of business applications from http://www.eudaptics.com/
� Stefanowski 2009
Clustering High-Dimensional Data
" Clustering high-dimensional data
" Many applications: text documents, DNA micro-array data
" Major challenges:
" Many irrelevant dimensions may mask clusters
" Distance measure becomes meaningless due to equi-distance
" Clusters may exist only in some subspaces
" Methods
" Feature transformation: only effective if most dimensions are
relevant
" PCA & SVD useful only when features are highly
correlated/redundant
" Feature selection: wrapper or filter approaches
" useful to find a subspace where the data have nice clusters
" Subspace-clustering: find clusters in all the possible subspaces
" CLIQUE, ProClus, and frequent pattern-based clustering
� Stefanowski 2009
Clustering Evaluation
" Manual inspection
" Benchmarking on existing labels
" Comparing clusters with ground-truth
categories
" Cluster quality measures
" distance measures
" high similarity within a cluster, low across
clusters
� Stefanowski 2009
Could we analyse an objective single measure?
" Some opinions
� Stefanowski 2009
Dopowiedzieć miary zmienności
" Homogenuous clusters.
" Intuition  zmienność wewnątrzskupieniowa
wc(C) i  zmienność międzyskupieniowa bc(C)
" May be defined in many ways
" Take average of clusters rk (centroids)
1
rk =
"x"Ck x
" Then
nk
K
wc(C) =
""x"Ck d(x,rk )2
k=1
bc(C) =
"1d" j� Stefanowski 2009
Measure of Clustering Accuracy
" Accuracy
" Measured by manually labeled data
" We manually assign tuples into clusters according
to their properties (e.g., professors in different
research areas)
" Accuracy of clustering: Percentage of pairs of tuples in the
same cluster that share common label
" This measure favors many small clusters
" We let each approach generate the same number
of clusters
� Stefanowski 2009
Analiza skupień - podsumowanie
Liczne i ważne zastosowanie praktyczne analizy skupień (AS).
AS używana  samodzielnie w zgłębianiu danych, lub jako jedno z narzędzi
podczas wstępnego przetwarzania w procesie KDD.
Jakość skupień i działanie wielu algorytmów związane są określeniem miary
odległości obiektów.
Podstawowe klasy metod:
hierarchiczne,
podziałowo/optymalizacyjne,
gęstościowe,
 grid-based ,
wykorzystujące modele matematyczne (np. probabilistyczne lub neuronowe).
Ważne zagadnienie to także wykrywanie obiektów nietypowych (outliers
discovery).
� Stefanowski 2009
Problemy i wyzwania
Znaczący postęp w zakresie skalowalnych algorytmów:
" Partitioning: k-means, k-medoids, CLARANS
" Hierarchical: BIRCH, CURE
" Density-based: DBSCAN, CLIQUE, OPTICS
" Grid-based: STING, WaveCluster.
" Model-based: Autoclass, Denclue, Cobweb.
Obecne techniki ciągle nie spełniają wystarczająco
dobrze stawianych wymagań.
Otwarte problemy i wyzwania badawcze; zwłaszcza dla
nietypowych i żłożonych danych.
� Stefanowski 2009
Clustering in Data Mining  przegląd
� Stefanowski 2009
Exercise:
Clustering
in Statsoft -Statistica
� Stefanowski 2009
Analiza Skupień  Statistica; więcej na www.statsoft.com. Przykład analizy danych o
parametrach samochodów
� Stefanowski 2009
� Stefanowski 2009
Dendrogram for Single Linkage
Diagram dla 22 przyp.
Pojedyncze wiązanie
Odległości euklidesowe
ACURA
AUDI
MERCEDES
CHRYSLER
DODGE
VW
HONDA
PONTIAC
SAAB
VOLVO
NISSAN
BMW
MITSUB.
BUICK
OLDS
MAZDA
TOYOTA
CORVETTE
FORD
PORSCHE
ISUZU
EAGLE
0,0 0,5 1,0 1,5 2,0 2,5 3,0 3,5 4,0 4,5
Odległość wiąz.
� Stefanowski 2009
� Stefanowski 2009
Analysing Agglomeration Steps
" Figure  find a cut point ( kolanko / knee)
Wykres odległości wiązania względem etapów wiązania
Odległości euklidesowe
5,0
4,5
4,0
3,5
3,0
2,5
2,0
1,5
1,0
0,5
Wiązania
0,0
Odległ.
0 2 4 6 8 10 12 14 16 18 20 22
Etap
� Stefanowski 2009
Odległość wiązan
Analiza Skupień
 optymalizacja k-średnich
� Stefanowski 2009
Profile - visulization
� Stefanowski 2009
Exercise:
Clustering
in WEKA
� Stefanowski 2009
Exercise:
Clustering
in WEKA
� Stefanowski 2009
WEKA Clustering
" Implemented methods
" k-Means
" EM
" Cobweb
" X-means
" FarthestFirst&
" Clusters can be visualized and compared to
 true clusters (if given)
� Stefanowski 2009
Exercise 1. K-means clustering in WEKA
" The exercise illustrates the use of the k-means algorithm.
" The example  sample of customers of the bank
" Bank data (bank-data.cvs -> bank.arff)
" All preprocessing has been performed on cvs
" 600 instances described by 11 attributes
id,age,sex,region,income,married,children,car,save_act,current_act,mortgage,pep
ID12101,48,FEMALE,INNER_CITY,17546.0,NO,1,NO,NO,NO,NO,YES
ID12102,40,MALE,TOWN,30085.1,YES,3,YES,NO,YES,YES,NO
ID12103,51,FEMALE,INNER_CITY,16575.4,YES,0,YES,YES,YES,NO,NO
ID12104,23,FEMALE,TOWN,20375.4,YES,3,NO,NO,YES,NO,NO
ID12105,57,FEMALE,RURAL,50576.3,YES,0,NO,YES,NO,NO,NO
& & & & & & & & & & & & & & & & & & & & & & & & & & & ..
& & & & & & & & & & & & & & & & & & & & & .
" Cluster customers and characterize the resulting customer
segments
� Stefanowski 2009
Loading the file and analysing the data
� Stefanowski 2009
Preprocessing for clustering
" What about non-numerical attributes?
" Remember about Filters
" Should we normalize or standarize attributes?
" How it is handled in WEKA k-means?
� Stefanowski 2009
Choosing Simple k-means
" Tune proper parameters
� Stefanowski 2009
Clustering results
" Analyse the result window
� Stefanowski 2009
Characterizing cluster
" How to describe clusters?
" What about descriptive statistics for centroids?
� Stefanowski 2009
Understanding the cluster characterization through visualization
� Stefanowski 2009
Finally, cluster assignments
� Stefanowski 2009
Różne nietypowe zastosowanie AS
� Stefanowski 2009
Grupowanie opisów stron
" Komercyjne Vivisimo / Clusty
" Otwarte  Carrot D.Weiss (S.Osinski + JS)
� Stefanowski 2009
Projekt  Open source Carrot 2
� Stefanowski 2009
Web Search Result Clustering  Carrot2
� Stefanowski 2009
Specific data mining applications
� Stefanowski 2009
Time-Series Similarities  specific data mining
Given a database of time-series.
Group  similar time-series
time time
Investor Fund A Investor Fund B
� Stefanowski 2009