POLECAMY
Koszyk
Algorytmy analizy skupień
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. |
Ciekawe propozycje
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 |
Wypożyczaj w abonamencie!
Już od 2,66 zł za ebooka
