Spis treści

Lista ważniejszych oznaczeń . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Przedmowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1. Analiza skupień . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.1. Formalizacja problemu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.2. Miary podobieństwa/odmienności . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.2.1. Porównywanie obiektów o cechach ilościowych . . . . . . . . . . . . . . . . 24

1.2.1.1. Odległość Minkowskiego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.2.1.2. Odległość Mahalanobisa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.2.1.3. Dywergencja Bregmana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.2.1.4. Odległość kosinusowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.2.1.5. Odległość potęgowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

1.2.2. Porównywanie obiektów o cechach jakościowych . . . . . . . . . . . . . . 31

1.3. Hierarchiczne metody analizy skupień . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.4. Metody kombinatoryczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

1.4.1. Kryteria grupowania oparte na odmienności . . . . . . . . . . . . . . . . . . 39
1.4.2. Zadanie analizy skupień w przestrzeni euklidesowej . . . . . . . . . . . 41

1.4.2.1. Minimalizacja śladu macierzy kowariancji

wewnątrzgrupowych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

1.4.2.2. Aproksymacja macierzy danych . . . . . . . . . . . . . . . . . . . . . . 47
1.4.2.3. Iteracyjny algorytm znajdowania skupień . . . . . . . . . . . . 48

1.4.3. Grupowanie według objętości skupień . . . . . . . . . . . . . . . . . . . . . . . . 51
1.4.4. Uogólnienia zadania grupowania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

1.5. Inne metody analizy skupień . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

1.5.1. Metody relacyjne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.5.2. Metody grafowe i spektralne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.5.3. Metody gęstościowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.5.4. Metody funkcji potencjalnych (jądrowych) . . . . . . . . . . . . . . . . . . . 60
1.5.5. Rodziny grupowań . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6

Spis treści

1.6. Grupowanie jako zadanie optymalizacji submodularnej . . . . . . . . . . . . . . 73

1.6.1. Podział na dwie grupy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

1.6.1.1. Metoda pojedynczego wiązania . . . . . . . . . . . . . . . . . . . . . . 75
1.6.1.2. Grupowanie z użyciem informacji wzajemnej . . . . . . . . . 77

1.6.2. Przypadek większej liczby grup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
1.6.3. Wyznacznikowe procesy punktowe (DPP) . . . . . . . . . . . . . . . . . . . . 79

1.6.3.1. Podstawowe pojęcia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.6.3.2. Grupowanie na podstawie DPP . . . . . . . . . . . . . . . . . . . . . . 82

1.7. Czy i kiedy grupowanie jest trudne? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

2. Algorytmy kombinatorycznej analizy skupień . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

2.1. Algorytm k-średnich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

2.1.1. Klasyczny (wsadowy) wariant algorytmu k-średnich . . . . . . . . . . 92
2.1.2. Iteracyjny wariant algorytmu k-średnich . . . . . . . . . . . . . . . . . . . . . 92
2.1.3. Metody inicjowania algorytmu k-średnich . . . . . . . . . . . . . . . . . . . . 94

2.1.3.1. Algorytm k-średnich++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
2.1.3.2. Algorytm k-średnich D++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

2.1.4. Usprawnienia algorytmu k-średnich . . . . . . . . . . . . . . . . . . . . . . . . . . 99
2.1.5. Warianty algorytmu k-średnich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

2.1.5.1. Wariant on line algorytmu k-średnich . . . . . . . . . . . . . . 101
2.1.5.2. Bisekcyjny wariant algorytmu k-średnich . . . . . . . . . . . 103
2.1.5.3. Sferyczny algorytm k-średnich . . . . . . . . . . . . . . . . . . . . . . 104
2.1.5.4. KHM: algorytm k-średnich harmonicznych . . . . . . . . . . 107
2.1.5.5. Jądrowy algorytm k-średnich . . . . . . . . . . . . . . . . . . . . . . . 109
2.1.5.6. Algorytm k-medoid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
2.1.5.7. Algorytm k-mod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

2.2. Algorytm EM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
2.3. FCM: algorytm k-średnich rozmytych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

2.3.1. Podstawowe sformułowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
2.3.2. Podstawowy algorytm FCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
2.3.3. Miary jakości rozmytego podziału . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
2.3.4. Sformułowanie alternatywne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
2.3.5. Modyfikacje algorytmu FCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

2.3.5.1. Algorytm FCM z metryką Minkowskiego . . . . . . . . . . . 139
2.3.5.2. Algorytm Gustafsona–Kessela (GK) . . . . . . . . . . . . . . . . 141
2.3.5.3. Algorytm FCV: Fuzzy c-varietes . . . . . . . . . . . . . . . . . . . . 143
2.3.5.4. Algorytm FCS: Fuzzy c-shells . . . . . . . . . . . . . . . . . . . . . . 145
2.3.5.5. SFCM: Sferyczny algorytm FCM . . . . . . . . . . . . . . . . . . . 146
2.3.5.6. Jądrowe warianty algorytmu FCM . . . . . . . . . . . . . . . . . . 147

Algorytm KFCM-X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
Algorytm KFCM-F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

2.3.5.7. PCM: possibilistyczny algorytm grupowania . . . . . . . . 151
2.3.5.8. Relacyjny wariant algorytmu FCM . . . . . . . . . . . . . . . . . 155

2.4. Grupowanie na podstawie funkcji alokacji prawdopodobieństwa . . . . 157

2.4.1. Podziały fiducjarne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

Spis treści

7

2.4.2. Od podziałów fiducjarnych do ostrych . . . . . . . . . . . . . . . . . . . . . . . 161

2.5. Propagacja powinowactwa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

3. Ocena jakości skupień i stosowalności algorytmów . . . . . . . . . . . . . . . . . . . . 166

3.1. Przygotowanie danych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
3.2. Wybór liczby skupień . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

3.2.1. Proste heurystyki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
3.2.2. Metody wykorzystujące kryteria informacyjne . . . . . . . . . . . . . . . 170
3.2.3. Klastergramy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

3.3. Miary jakości podziału . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
3.4. Porównywanie podziałów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

3.4.1. Proste metody porównywania podziałów . . . . . . . . . . . . . . . . . . . . 176
3.4.2. Metody pomiaru części wspólnych podziałów . . . . . . . . . . . . . . . . 177
3.4.3. Metody wykorzystujące wzajemną informację . . . . . . . . . . . . . . . 179

3.5. Miary jakości pokrycia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
3.6. Analiza dużych zbiorów danych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

3.6.1. Proste usprawnienia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

3.6.1.1. FFCM: szybki algorytm FCM . . . . . . . . . . . . . . . . . . . . . . 183

PFCM: równoległy algorytm FCM . . . . . . . . . . . . . . . . . . 184
WFCM: ważony algorytm FCM . . . . . . . . . . . . . . . . . . . . 184
mrFCM: algorytm FCM z wieloetapowym
próbkowaniem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

4. Metody spektralne w analizie i redukcji danych . . . . . . . . . . . . . . . . . . . . . . . 187

4.1. Notacja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.2. Spektralna analiza danych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

4.2.1. Optymalizacja spektralna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

4.2.1.1. Przypadek dwóch klas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
4.2.1.2. Dalsze zastosowania wektora Fiedlera . . . . . . . . . . . . . . . 202
4.2.1.3. Przypadek wielu klas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

4.2.2. Alternatywne funkcje kryterialne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
4.2.3. Zadanie rozcinania grafu jako uogólniony problem własny . . . 210
4.2.4. Metody rozwiązywania uogólnionego problemu własnego . . . . 215
4.2.5. Spektralne algorytmy grupowania danych . . . . . . . . . . . . . . . . . . . 220

4.2.5.1. Algorytm normalizowanych cięć Shi i Malika (SM) . . 223
4.2.5.2. Algorytm normalizowanych cięć Vermy i Meili (VM) 224
4.2.5.3. Spektralne odwzorowanie Ng, Jordana

i Weissa (NJW) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225

4.2.5.4. Algorytm DaSpec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

4.2.6. Maksymalizacja spójności grup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
4.2.7. Przykłady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
4.2.8. Dostrajanie algorytmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

4.2.8.1. Wybór parametru ω . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
4.2.8.2. Wzmacnianie struktury blokowej . . . . . . . . . . . . . . . . . . . 240

8

Spis treści

4.3. Błądzenie losowe w grafach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

4.3.1. Błądzenie losowe w grafach nieskierowanych . . . . . . . . . . . . . . . . . 243

4.3.1.1. Proste interpretacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
4.3.1.2. Grupowanie węzłów według ich potencjału . . . . . . . . . . 247
4.3.1.3. Odległość rezystancyjna . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
4.3.1.4. Grupowanie węzłów według czasu pochłonięcia . . . . . 251

4.3.2. Zastosowanie idei błądzenia po grafie: algorytm MCL . . . . . . . 254

4.3.2.1. Podstawowa wersja algorytmu . . . . . . . . . . . . . . . . . . . . . . 254
4.3.2.2. Problemy z algorytmem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

4.4. Metody lokalne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

4.4.1. Algorytm Nibble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
4.4.2. Algorytm PageRank-Nibble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

4.5. Uczenie częściowo nadzorowane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
4.6. Usprawnienia i inne metody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

4.6.1. Grupowanie z wykorzystaniem p-laplasjanu . . . . . . . . . . . . . . . . . 271
4.6.2. Grupowanie stochastyczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
4.6.3. Zastosowanie algorytmu SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
4.6.4. Algorytm PIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
4.6.5. Algorytm PRC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

4.7. Metody redukcji wymiarowości . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282

5. Zbiory danych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

Dodatek A. Uzasadnienie algorytmu FCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

Dodatek B. Rachunek macierzowy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290

B.1. Wektory i ich własności . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
B.2. Macierze i ich własności . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
B.3. Wartości i wektory własne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294

B.3.1. Podstawowe fakty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
B.3.2. Lewo- i prawostronne wektory własne . . . . . . . . . . . . . . . . . . . . . . 299
B.3.3. Wyznaczanie wartości i wektorów własnych . . . . . . . . . . . . . . . . 301

B.3.3.1. Metoda potęgowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
B.3.3.2. Wyznaczanie par własnych laplasjanu . . . . . . . . . . . . . 303

B.4. Normy wektorów i macierzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

Dodatek C. Teoria grafów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

C.1. Podstawowe definicje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

C.1.1. Grafy nieskierowane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
C.1.2. Grafy skierowane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

C.2. Macierze grafów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

C.2.1. Macierz sąsiedztwa/podobieństwa . . . . . . . . . . . . . . . . . . . . . . . . . . 310
C.2.2. Laplasjan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

C.2.2.1. Laplasjan grafu nieskierowanego . . . . . . . . . . . . . . . . . . . 312

Spis treści

9

C.2.2.2. Pseudoodwrotność laplasjanu . . . . . . . . . . . . . . . . . . . . . . 315
C.2.2.3. Laplasjan grafu skierowanego . . . . . . . . . . . . . . . . . . . . . . 316

Dodatek D. Błądzenie losowe w grafie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318

D.1. Błądzenie losowe w grafach nieskierowanych . . . . . . . . . . . . . . . . . . . . . . . 318

D.1.1. Podstawowe fakty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
D.1.2. Charakterystyki błądzenia losowego . . . . . . . . . . . . . . . . . . . . . . . . 322

D.1.2.1. Średni czas dostępu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
D.1.2.2. Czas komutacji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
D.1.2.3. Czas pokrycia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
D.1.2.4. Czas mieszania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324

D.2. Błądzenie losowe w grafach skierowanych . . . . . . . . . . . . . . . . . . . . . . . . . . 324

Dodatek E. Personalizowany wektor PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . 326

E.1. Podstawowe określenia i zależności . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
E.2. Przybliżony algorytm wyznaczania personalizowanego

wektora PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330

Dodatek F. Entropia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

F.1. Podstawowe definicje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
F.2. Entropia gaussowskiego wektora losowego . . . . . . . . . . . . . . . . . . . . . . . . . . 336

Dodatek G. Teoria Dempstera–Shafera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338

G.1. Funkcje charakteryzujące sądy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
G.2. Reguła Dempstera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
G.3. Sprowadzanie przekonań do prawdopodobieństw . . . . . . . . . . . . . . . . . . . 342

Dodatek H. Optymalizacja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

H.1. Submodularne funkcje zbioru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
H.2. Uczenie funkcji submodularnych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
H.3. Optymalizacja submodularnych funkcji zbioru . . . . . . . . . . . . . . . . . . . . . 348

H.3.1. Minimalizacja funkcji submodularnych . . . . . . . . . . . . . . . . . . . . . 348

H.3.1.1. Podstawowe narzędzia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

Drzewo maksymalnych przepływów . . . . . . . . . . . . . . . . 351
Dobre pary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354

H.3.1.2. Algorytm Queyranne’a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356

H.3.2. Maksymalizacja submodularnych funkcji . . . . . . . . . . . . . . . . . . . 359

Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361

Wykaz algorytmów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389

Skorowidz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391