Shluková analýza Jiří Militky Analýza experimentálních dat V Červeně označené slide jsou jen pro doplnění informací a nezkouší se.
Klasifikace objektů
Rozdělení objektů do shluků dle jejich podobnosti a dle vybraných vlastností proměnných.
Objekty se často zařazují do skupin: Periodická tabulka prvků (chemie) Taxonomie rostlin a živočichů (zoologie, botanika) Účelem je:
popis systematiky (taxonomie)
Sumarizace podle jistých kritérií (zjednodušení) Predikce chování Vysvětlení zvláštností (predikce vztahů) Každá klasifikace objektů je závislá na cíli: různé cíle vedou k různým členěním.
Klasifikace vyžaduje definici podobnosti resp. různosti objektů. O užitečnosti klasifikace rozhoduje využitelnost výsledků. Je výhodu , pokud existuje teoretické zdůvodnění klasifikace.
Typy klasifikace
Cíl: zařazení objektů do skupin (tříd) na základě výsledků měření na těchto objektech. Řízená (supervised): třídy jsou předdefinován. Je třeba použít množinu označených objektů (trénovací nebo učící) pro vytvoření klasifikátoru umožňujícího klasifikaci budoucích objektů (diskriminační analýza) Neřízená (unsupervised): třídy jsou neznámé. Je třeba je stanovit na základě informací o objektech. (analýza shluků)
Analýza shluků
K dispozici je n objektů, každý je popsán pomocí m rysů, proměnných resp. charakteristik. Cílem je zařazení objektů do skupin. Často se požaduje dělení objektů. Hledají se souvislosti v datech. Objasňuje se chování dat. Provádí se předpověď chování Provádí se vizualizace dat ve vhodné soustavě ‘Neřízené učení’ Jde většinou o ne stochastické metody.
Shlukovací znaky
Struktura dat x 11 ... Matice dat (dva módy) xi1 ... x n1
... ... ... ... ...
x 1j ... x ij ...
...
x nj
...
... ... ...
x 1n ... x in ... x nn
1) Znaky charakterizující shlukované objekty. 2) Analýza nerozlišuje významné a nevýznamné znaky. 3) Odlišení shluků za použití všech navržených znaků.
0 d(2,1) 4) Na volbě znaků závisí Matice 0 nalezení správných shluků. nepodobnosti d(3,1) d(3,2) 0 (jeden mód) 5)Výběr znaků, které : : : d(n,1) d(n,2) ... ... 0 dostatečně rozlišují mezi objekty.
Kvalita shlukování
Nepodobost/Podobnost : Podobnost je vyjádřena jako funkce vzdálenosti, která je obecně vhodná metrika : d(i, j) Podobnost : Kvalita shluků je popsána speciálními Podle vzdálenosti charakteristikami. 1 a 9 jsou blízké Funkce vzdálenosti se obyčejně silně liší pro 1, 9 a 7 jsou nepodobné různé typy speciálních škál dat jako jsou Podle struktury kardinální, booleovské, kategorizované, 1 a 7 jsou podobné ordinální a nominální znaky. 1, 7 a 9 jsou nepodobné Pro různé znaky lze použít různé typy váhových koeficientů. Vyjádření kvality Je složité vyjádřit “dostatečně podobné” nebo je obyčejně pouze “dostatečně dobré” subjektivní.
Vzdálenost objektů I
Pro hodnocení podobnosti/nepodobnosti se používají různé typy vzdáleností mezi dvojicemi objektů Populární je Minkowského vzdálenost:
d (i, = j)
q
(| x 1 − x 1|q +| x 2 − x 2 |q +...+| x − x |q ) i j i j im jm
kde i = (xi1, xi2, …, xim) a j = (xj1, xj2, …, xjm) jsou dva mrozměrné datové objekty a q je celé kladné číslo
Pokud je q = 1, je d. Manhattanská vzdálenost
d (i, j) = | x − x | + | x − x | +...+ | x − x | i1 j1 i2 j 2 im jm
Vzdálenost objektů II
Pokud je q = 2, je d tzv. Eukleidovská vzdálenost d (i, = j)
(| xi1 − x j1|2 +| xi2 − x j 2 |2 +...+| xi − x j |2 ) m m
d(i,j) ≥ 0
d(i,i) = 0
d(i,j) = d(j,i)
d(i,j) ≤ d(i,k) + d(k,j)
y1
y1
D = (y2-y1)+(x2-x1) y2-y1
y2-y1
D = Iy2-y1I+Ix2-x1I B
B y2
y2
x2-x1 x1
Manhattanovská vzdálenost A
Euklidovská vzdálenost A
Vlastnosti
x2-x1 x2
x1
Je možné použít také vážené vzdálenosti, Pearsonův korelační koeficient a jiné míry nepodobnosti.
x2
Vzdálenost objektů III Tětivová vzdálenost (chord distance)
d (i, j) =
m x x ∑ ik jk k =1 2 1− m m 2 2 ∑ x ik ∑ x jk = k 1 =k 1
Mahalanobisova vzdálenost pro silně korelované znaky xi xj)
d (i, j) =
( xi − x j )
T
C
−1
V případě tří znaků je tětivová vzdálenost přímou vzdáleností dvou bodů na povrchu koule s jednotkovým poloměrem a počátkem v těžišti. Problém všech vzdálenostních měr: při použití nestandardizovaných dat mohou při různých jednotkách měření vyjít značné rozdíly mezi různými typy vzdáleností.
( xi − x j )
C (m x m) kovarianční matice pro m znaků
Vzdálenost objektů IV Korelační míry párové korelační koeficienty rij mezi dvojicí objektů xi a xj pro m znaků
m
∑(x
− xi ) ( x jk − x j )
−x
) ∑ ( x jk − x j ) 2
m
ik i = k 1= k 1
Silná korelace rij → 1 značí vysokou podobnost Slabá korelace rij → 0 značí nízkou podobnost
x3
k =1
ik
2
x2
r (i, j) =
∑(x
x1
m
x1
x2
x3
Podobnost pro binární proměnné (míry asociace) Kontingenční tabulka (odezva typu 0,1)
a ..pozitivní shoda tj. počet znaků, kde
Objekt j
Objekt i
1 0
1
0
a c
b d
suma a + c b + d
suma a +b c+d m
oba objekty mají hodnotu 1. d negativní shoda tj. počet znaků, kde oba objekty mají hodnotu 0.
c. počet znaků, kde objekt i má hodnotu 0. a objekt j hodnotu 1 b počet znaků, kde objekt i má hodnotu 1. a objekt j hodnotu 0
Sokal Michener koeficient shody Hamman Korelační koeficient −bc d (i, j) = a + d −b−c d (i, j) = a +b cad d (i, j) = a + d ( )( + d )( a + c )( b +b ) a +b + c + d a +b + c + d Soerensen Rogers Tanimoto Russel Rao 2a a+d d d (i, j) = d (i, j) = d (i, j) = 2a +b + c a + 2b+ 2c + d a +b + c + d
Podobnost mezi binárními proměnnými - příklad jméno Jack Mary Jim
pohlaví M F M
horečka Y Y Y
kašel N N P
Test-1 P P N
Test-2 N N N
Test-3 N P N
Test-4 N N N
Pohlaví je symetrický atribut Ostatní jsou asymetrické binární atributy Nechť M, Y a P jsou rovny 1, a N, F je rovno 0
Mary Jack
1 0
1 2 1
0 1 3
suma 3 4
suma
3
4
7
Sokalův koeficient d(Jack, Mary) = (2+3)/7 = 0.714 Russel Rao koeficient d(Jack, Mary) = (3)/7 = 0. 428
Podobnost pro nominální proměnné
Jde o zobecnění binárních proměnných pro více stavů např. barvy, značky aut, typ technologie atd. Metoda 1: Jednoduchá shoda
p : počet shod, m : celkový počet znaků (proměnných)
−p d (i, j) = mm
Metoda 2: převedení na binární proměnné
Každý z M nominálních stavů je nová binární proměnná
Ordinální proměnné
Ordinální proměnná je diskrétní nabývající konečného počtu stavů Důležité je uspořádání (pořadí) od nejhoršího k nejlepšímu Lze je zpracovat podobně jako spojité proměnné náhrada hodnoty xij i-tého objektu a j-tého znaku odpovídajícími pořadími pij p ∈{1,..., M } ij
j
mapování rozmezí každého znaku do intervalu [0, 1] náhradou i – tého objektu pro j – tý znak veličinou
pij −1 zij = M j −1
Výpočet míry nepodobnosti pro zij jako pro spojité proměnné
Kardinální proměnné Je možné použít všech typů vzdáleností. Protože jsou jednotlivé znaky v různých jednotkách (rozmezí) je vhodná standardizace dat. Výhodné je použití průměrné absolutní odchylky pro j tý znak:
= saj
Výpočet z skóre
1 n ∑ n i =1
| xij − x j |
xij − x j zij = sa j
Průměrná absolutní odchylka je robustnější než směrodatná odchylka.
Předpoklady analýzy shluků Analýza shluků je objektivní kvantifikace strukturních zvláštností sledovaných objektů. Nejsou zde požadavky na normalitu, linearitu, nebo homoskedasticitu. Dva kritické předpoklady: Reprezentativnost výběru objektů Nalezené shluky mají odpovídat struktuře populace. Odlehlé objekty mohou způsobit vznik „nevhodných“ shluků, které negativně ovlivní odhad struktury objektů. Vliv multikolinearity Multikolineární znaky jsou implicitně váženy intenzivněji. V případě silné multikolinearity je možno snížit počet znaků nebo použít Mahalanobisovu vzdálenost.
Problémy s definicí shluků
Základní přístupy ke shlukování Dělící (nehierarchické) Konstrukce různých skupin objektů (shluků) a výběr nejvhodnější podle zadaného kritéria.
Hierarchické algoritmy: Konstrukce hierarchického rozkladu množiny objektů podle vhodného kritéria
Rozlišovací kritérium: maximalizace rozdílů mezi shluky, Proměnlivost mezi shluky vůči proměnlivosti uvnitř shluků. Test: poměr rozptylu mezi shluky vůči rozptylu uvnitř shluků
Nehierarchické shlukování základy
Dělící postupy: Celkem n objektů se dělí do k shluků nalezených podle zvoleného kritéria . Počet shluků je předem zvolen.
Globální optimalita: hodnocení všech možných kombinací objektů ve shlucích
Heuristické metody: k-means a k-medoids algoritmy
k-means (MacQueen’67): Každý shluk je representován svým středem (těžištěm)
k-medoids resp. PAM (Partition around medoids) (Kaufman & Rousseeuw’87): Každý shluk je representován jedním objektem, který v něm leží.
Nehierarchické shlukování postup
1. Zadání zárodku shluku (= počátečního středu shluku). 2. Objekty ležící uvnitř zadané vzdálenosti jsou do shluku zařazeny. 3. Zadání zárodku dalšího shluku a pokračování krokem 2.
Postupy K-means shlukování (nejbližších středů, těžišť) (a) Sekvenční práh: začíná se volbou jednoho zárodku a zahrnují se všechny objekty uvnitř dané vzdálenosti. Dále je vybrán zárodek druhého shluku, atd. (b) Paralelní práh: vybírá se několik zárodků současně a objekty se zařazuje podle prahové vzdálenosti od nejbližšího zárodku. (c) Optimalizace: je možné znovu zařazení objektů. Když se objekt dostane blíže jinému shluku, než se právě nachází, je přeřazen do bližšího shluku.
10
Metoda shlukování K- Means
9 8 7 6 5 4 3 2 1
Potíže u zašuměných Pro dané k, je k-means dat a vybočujících algoritmus rozdělen do hodnot. Shluky musí těchto fází: mít konvexní tvar. Rozdělení objektů do k neprázdných podmnožin Musí být možné určit průměr. Je nalezeno Výpočet bodů počátku lokální optimum. (zárodků) jako centroidů shluků pro dané rozdělení objektů. Centroid je střed (průměrný bod) shluku. Přiřazení objektu do shluku s nejbližším bodem počátku. Návrat na krok 2, dokud se již nerealizuje další přiřazení. Klíčovým problémem je vhodná volba shlukových zárodků.
0 0
9
10
3 2 1 0 0
1
2
3
4
5
6
7
8
9
10
10 9 8 7 6 5 4 3
3
2
2
1
1
0
0
7
8
4
4
6
7
5
5
5
6
6
6
4
5
7
7
3
4
8
8
2
3
9
9
1
2
10
10
0
1
8
9
10
0
1
2
3
4
5
6
7
8
9
10
Shlukování: nejbližší soused Znak 2
Znak 1
Shlukování: nejbližší soused Znak 2
Znak 1
Shlukování: nejbližší soused Znak 2
Znak 1
Shlukování: nejbližší soused Znak 2
Znak 1
Shlukování: nejbližší soused Znak 2
Znak 1
Shlukování: nejbližší soused Znak 2
Znak 1
Vzdálenost objektu od shluku je definována jako nejmenší vzdálenost mezi tímto bodem a libovolným bodem ve shluku.
Metoda shlukování K-Medoids
Funguje dobře jen pro malé počty objektů
1. Nalezení počáteční skupiny reprezentujících objeků (medoidů) Medoid - střed shluku, je objekt, pro který platí, že průměrná vzdálenost k ostatním objektům v tomto shluku je minimální. 2. Po nalezení medoidů jsou data klasifikována do shluků vždy okolo nejbližšího medoidu. Medoidy a shluky se vytvářejí na základě vzdáleností dij. Algoritmus vyhledává dosud nezařazené objekty a přemísťuje je tak, aby se hodnota D snižovala. Jako účelová funkce se bere celková vzdálenost mezi všemi objekty n ve shluku podle vzorce D
= ∑ ∑ ∑ dij j =1 i ⊂ ck j ⊂ ck
kde k je celkový počet shluků, d je vzdálenost mezi i-tým a j-tým objektem a ck udává všechny objekty ve shluku l.
•
Celková cena za výměnu 10
10
9
9
8
8
t
7 6
j
t
7 6
j h
5 4
i
3
5 4
h i
3
2
2
1
1
0 0
1
2
3
4
5
6
7
8
9
0
10
0
10
10
9
9
3
4
5
6
7
8
9
10
8
h
7
2
Cjih = 0
Cjih = d(j, h) - d(j, i)
8
1
7
j
6
6 5
5
i
4
t
n
h t
3
2
2
1
1
TCih = ∑ C jih
i
4
3
j
j =1
0
0 0
1
2
3
4
5
Pro všechny dvojice nevybraného objektu h a vybraného objektu i, se určí celková cena za výměnu TCih • Pokud je TCih < 0, je objekt i nahrazen objektem h • Pak je každý nevybraný objekt přiřazen k nejpodobnějšímu medoidu •Postup se opakuje až již neproběhne žádná náhrada.
6
7
8
9
Cjih = d(j, t) - d(j, i)
10
0
1
2
3
4
5
6
7
8
9
Cjih = d(j, h) - d(j, t)
10
Hierarchické shlukování I 1 2 3 4 5
C1 C2 C3 C4 C5 C6 ..
Data Kritéria podobnosti
5×5
dij
Matice podobnosti (vzdálenosti)
Kritéria shlukování
Dendrogram
Hierarchické shlukování II
Jako kritérium pro shlukování se využívá matice vzdáleností . Je třeba definovat kritérium pro ukončení. Algoritmy seskupování a rozdělování Krok 0
a
Krok
1
Krok
2
Krok
3
Krok
4
ab
b
abcde
c
cde
d
de
e Krok
seskupování (AGNES)
4
Krok
3
Krok
2
Krok
1
Krok
0
rozdělování (DIANA)
Hierarchické shlukování III Způsob seskupování: 1. Dva objekty, jejichž vzdálenost je nejmenší se spojí do prvního shluku. 2. Vypočte se nová matice vzdáleností, v níž jsou vynechány objekty z prvního shluku, a tento shluk je pak zařazen jako objekt. 3. Celý postup se opakuje tak dlouho, dokud všechny objekty netvoří jeden velký shluk, nebo dokud nezůstane určitý, předem zadaný počet shluků.
Způsob rozdělování: Inverzní postup od jednoho shluku ke shlukům jednoprvkovým
Mezi shlukové vzdálenosti Metoda nejbližšího souseda: minimální vzdálenosti mezi objekty dvou shluků Metoda nejvzdálenějšího souseda: maximální vzdálenost mezi objekty dvou shluků Metoda průměrového linkování: průměrná vzdálenost všech objektů v jednom shluku ke všem objektům ve druhém shluku. Wardova metoda: minimalizace přírůstku vnitro shlukové variability VSS (suma čtverců odchylek od průměrů znaků pro všech m objektů).
Metoda těžiště
Metoda těžiště: vzdálenost těžišť shluků. Těžiště shluku je průměrná hodnota shlukových znaků. k objektů ve shluku
Příklad: metoda nejbližšího souseda Data
Matice eukleidovských vzdáleností E1
Spojí se objekt 1 a 2, protože jejich vzdálenost je v matici E1 nejmenší. Sestavení matice vzdáleností E2, zbylých objektů od shluku (1, 2). d(1,2).3) = min (d1,3 , d2,3) = min (29, 26)= 26, d(1,2),4) = min (d1,4 , d2,4) = 49, d(1,2),5) = min (d1,5 , d2,5) = 50, Matice vzdáleností E3
Matice vzdáleností E2
další shluk (4, 5).
Porovnání mezi shlukových vzdálenosti 1. 2. 3. 4.
Skupinový průměr, Kofenetická korelace: 0.987, Delta(0.5): 0.137; Nejbližší soused, Kofenetická korelace: 0.989, Delta(0.5): 0.474; Nejvzdálenější soused, Kofenetická korelace: 0.989, Delta(0.5): 0.178 ; Wardova metoda, Kofenetická korelace: 0.979, Delta(0.5): 0.549 Nejbližší soused
Průměrná vzdálenost
Nejvzdálenější soused
Wardova metoda
Míry věrohodnosti
1. kritérium těsnosti proložení : kofenetický korelační koeficient
CC - nejlépe odpovídá struktuře objektů a znaků mezi objekty, je to Pearsonův korelační koeficient mezi skutečnou a predikovanou vzdáleností, založenou na dendrogramu. 2. kritérium těsnosti proložení: kritérium delta - měří stupeň přetvoření struktury dat, - je žádoucí, aby hodnoty delta byly blízké nule,
kde A = 0.5 nebo 1, dij je vzdálenost v původní matici vzdáleností a d*ij je vzdálenost získaná z dendrogramu .
Porovnání shlukovacích metod (1) Hierarchické metody: a) Hierarchické metody jsou rychlé. b) Hierarchické metody mohou být ovlivněny odlehlými objekty., c) Hierarchické metody nejsou vhodné pro velké počty objektů. (2) Nehierarchické metody: a) Použití nehierarchických metod závisí na schopnosti uživatele vybrat zárodkové body. b) Výsledky nehierarchických metod jsou méně ovlivněny odlehlými body. (3) Kombinace obou metod, hierarchických a nehierarchických: a) Nejprve se hierarchickou metodou určí: počet shluků, profily shlukovaných center a zřetelně odlehlé body. b) Po odstranění odlehlých bodů: zbývající objekty jsou shlukovány nehierarchicky se zárodky z výsledků hierarchické metody.
Zatím vše !!!
