POLECAMY
Wydawca:
Format:
ibuk
Publikacja Wydawnictwa WNT, dodruk Wydawnictwo Naukowe PWN
Książka przeznaczona jest dla studentów i doktorantów zainteresowanych technikami odkrywania wiedzy z danych oraz modelowania komputerowego, a także dla praktyków - informatyków opracowujących programy do analizy dużych zbiorów danych.
Rok wydania | 2017 |
---|---|
Liczba stron | 396 |
Kategoria | Algorytmika |
Wydawca | Wydawnictwo Naukowe PWN |
ISBN-13 | 978-83-01-19178-8 |
Numer wydania | 1 |
Język publikacji | polski |
Informacja o sprzedawcy | ePWN sp. z o.o. |
POLECAMY
Ciekawe propozycje
Algorytmy genetyczne. Kompendium, t. 1
do koszyka
Algorytmy genetyczne. Kompendium, t. 2
do koszyka
Algorytmy diagnostyczne i lecznicze w...
do koszyka
Algorytmy i struktury danych
do koszyka
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 |
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 |
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 |
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 |
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 |