Algorytmy analizy skupień
Motorem napędzającym współcześnie rozwój nauki,
techniki i gospodarki jest szeroki dostęp do danych z doświadczeń i obserwacji
procesów zachodzących w przyrodzie, instalacjach przemysłowych oraz w społeczeństwie.
Rozwój technologii umożliwił wprawdzie łatwe i szybkie
pozyskiwanie oraz gromadzenia olbrzymich zbiorów informacji, nadal jednak ich
przetwarzanie i analizowanie jest poważnym wyzwaniem. Aby mu sprostać, opracowano wiele
metod, wśród których ważną rolę odgrywa analiza skupień. Jest ona uniwersalnym
narzędziem do porządkowania i segregowania wielowymiarowych informacji.
Do tradycyjnych obszarów zastosowań analizy skupień
należą: segmentacja obrazów, wyszukiwanie informacji oraz bioinformatyka. Stale jednak
poszerza się zakres jej stosowania, już dziś służy m.in. w medycynie do diagnozowania
pacjentów na podstawie danych klinicznych i laboratoryjnych, w handlu do segmentacji
rynku w celu opracowania efektywnych strategii marketingowych oraz w wielu dziedzinach
nauki do przetwarzania wyników badań.
Autorzy książki, zdając sobie sprawę z rosnącej
popularności metod analizy skupień i konieczności ich ciągłego doskonalenia w celu
lepszego przystosowania do analizy coraz obszerniejszych zbiorów danych o złożonej
topologii, przygotowali publikację, która:
- zawiera przegląd podstawowych algorytmów analizy
skupień wraz z omówieniem ich różnorodnych modyfikacji;
- unaocznia problem oceny i wyboru właściwej liczby
skupień;
- omawia specjalizację wybranych algorytmów do zadań
przetwarzania ogromnych zbiorów danych;
- prezentuje w zwartej formie ujednolicony materiał,
stanowiący podstawę rozwijania nowych algorytmów spektralnej i dyfuzyjnej analizy
danych;
- opisuje wybrane rozwiązania stosowane w uczeniu
częściowo nadzorowanym;
- zawiera bogatą literaturę, która może być punktem
wyjścia różnorodnych samodzielnych poszukiwań wiedzy.
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.
Lista ważniejszych oznaczeń
Przedmowa
1. Analiza skupień
1.1. Formalizacja problemu
1.2. Miary podobieństwa/odmienności
1.2.1. Porównywanie obiektów o cechach ilościowych
1.2.1.1. Odległość Minkowskiego
1.2.1.2. Odległość Mahalanobisa
1.2.1.3. Dywergencja Bregmana
1.2.1.4. Odległość kosinusowa
1.2.1.5. Odległość potęgowa
1.2.2. Porównywanie obiektów o cechach jakościowych
1.3. Hierarchiczne metody analizy skupień
1.4. Metody kombinatoryczne
1.4.1. Kryteria grupowania oparte na odmienności
1.4.2. Zadanie analizy skupień w przestrzeni euklidesowej
1.4.2.1. Minimalizacja śladu macierzy kowariancji wewnątrzgrupowych
1.4.2.2. Aproksymacja macierzy danych
1.4.2.3. Iteracyjny algorytm znajdowania skupień
1.4.3. Grupowanie według objętości skupień
1.4.4. Uogólnienia zadania grupowania
1.5. Inne metody analizy skupień
1.5.1. Metody relacyjne
1.5.2. Metody grafowe i spektralne
1.5.3. Metody gęstościowe
1.5.4. Metody funkcji potencjalnych (jądrowych)
1.5.5. Rodziny grupowań
1.6. Grupowanie jako zadanie optymalizacji submodularnej
1.6.1. Podział na dwie grupy
1.6.1.1. Metoda pojedynczego wiązania
1.6.1.2. Grupowanie z użyciem informacji wzajemnej
1.6.2. Przypadek większej liczby grup
1.6.3. Wyznacznikowe procesy punktowe (DPP)
1.6.3.1. Podstawowe pojęcia
1.6.3.2. Grupowanie na podstawie DPP
1.7. Czy i kiedy grupowanie jest trudne?
2. Algorytmy kombinatorycznej analizy skupień
2.1. Algorytm fc-średnich
2.1.1. Klasyczny (wsadowy) wariant algorytmu fc-średnich
2.1.2. Iteracyjny wariant algorytmu fc-średnich
2.1.3. Metody inicjowania algorytmu fc-średnich
2.1.3.1. Algorytm fc-średnich++
2.1.3.2. Algorytm fc-średnich D++
2.1.4. Usprawnienia algorytmu fc-średnich
2.1.5. Warianty algorytmu fc-średnich
2.1.5.1. Wariant on linę algorytmu fc-średnich
2.1.5.2. Bisekcyjny wariant algorytmu fc-średnich
2.1.5.3. Sferyczny algorytm fc-średnich
2.1.5.4. KHM: algorytm fc-średnich harmonicznych
2.1.5.5. Jądrowy algorytm fc-średnich
2.1.5.6. Algorytm fc-medoid
2.1.5.7. Algorytm fc-mod
2.2. Algorytm EM
2.3. FCM: algorytm fc-średnich rozmytych
2.3.1. Podstawowe sformułowanie
2.3.2. Podstawowy algorytm FCM
2.3.3. Miary jakości rozmytego podziału
2.3.4. Sformułowanie alternatywne
2.3.5. Modyfikacje algorytmu FCM
2.3.5.1. Algorytm FCM z metryką Minkowskiego
2.3.5.2. Algorytm Gustafsona-Kessela (GK)
2.3.5.3. Algorytm FCV: Fuzzy ovarietes
2.3.5.4. Algorytm FCS: Fuzzy c-shells
2.3.5.5. SFCM: Sferyczny algorytm FCM
2.3.5.6. Jądrowe warianty algorytmu FCM
Algorytm KFCM-X
Algorytm KFCM-JF
2.3.5.7. PCM: possibilistyczny algorytm grupowania
2.3.5.8. Relacyjny wariant algorytmu FCM
2.4. Grupowanie na podstawie funkcji alokacji prawdopodobieństwa
2.4.1. Podziały fiducjarne
2.4.2. Od podziałów fiducjarnych do ostrych
2.5. Propagacja powinowactwa
3. Ocena jakości skupień i stosowalności algorytmów
3.1. Przygotowanie danych
3.2. Wybór liczby skupień
3.2.1. Proste heurystyki
3.2.2. Metody wykorzystujące kryteria informacyjne
3.2.3. Klastergramy
3.3. Miary jakości podziału
3.4. Porównywanie podziałów
3.4.1. Proste metody porównywania podziałów
3.4.2. Metody pomiaru części wspólnych podziałów
3.4.3. Metody wykorzystujące wzajemną informację
3.5. Miary jakości pokrycia
3.6. Analiza dużych zbiorów danych
3.6.1. Proste usprawnienia
3.6.1.1. FFCM: szybki algorytm FCM
PFCM: równoległy algorytm FCM
WFCM: ważony algorytm FCM
mrFCM: algorytm FCM z wieloetapowym próbkowaniem
4. Metody spektralne w analizie i redukcji danych
4.1. Notacja
4.2. Spektralna analiza danych
4.2.1. Optymalizacja spektralna
4.2.1.1. Przypadek dwóch klas
4.2.1.2. Dalsze zastosowania wektora Fiedlera
4.2.1.3. Przypadek wielu klas
4.2.2. Alternatywne funkcje kryterialne
4.2.3. Zadanie rozcinania grafu jako uogólniony problem własny
4.2.4. Metody rozwiązywania uogólnionego problemu własnego
4.2.5. Spektralne algorytmy grupowania danych
4.2.5.1. Algorytm normalizowanych cięć Shi i Malika (SM)
4.2.5.2. Algorytm normalizowanych cięć Vermy i Meili (VM)
4.2.5.3. Spektralne odwzorowanie Ng, Jordana i Weissa (NJW)
4.2.5.4. Algorytm DaSpec
4.2.6. Maksymalizacja spójności grup
4.2.7. Przykłady
4.2.8. Dostrajanie algorytmu
4.2.8.1. Wybór parametru ul
4.2.8.2. Wzmacnianie struktury blokowej
4.3. Błądzenie losowe w grafach
4.3.1. Błądzenie losowe w grafach nieskierowanych
4.3.1.1. Proste interpretacje
4.3.1.2. Grupowanie węzłów według ich potencjału
4.3.1.3. Odległość rezystancyjna
4.3.1.4. Grupowanie węzłów według czasu pochłonięcia
4.3.2. Zastosowanie idei błądzenia po grafie: algorytm MCL
4.3.2.1. Podstawowa wersja algorytmu
4.3.2.2. Problemy z algorytmem
4.4. Metody lokalne
4.4.1. Algorytm Nibble
4.4.2. Algorytm PageRank-Nibble
4.5. Uczenie częściowo nadzorowane
4.6. Usprawnienia i inne metody
4.6.1. Grupowanie z wykorzystaniem p-laplasjanu
4.6.2. Grupowanie stochastyczne
4.6.3. Zastosowanie algorytmu SVD
4.6.4. Algorytm PIC
4.6.5. Algorytm PRC
4.7. Metody redukcji wymiarowości
5. Zbiory danych
Dodatek A. Uzasadnienie algorytmu FCM
Dodatek B. Rachunek macierzowy
B.1. Wektory i ich własności
B.2. Macierze i ich własności
B.3. Wartości i wektory własne
B.3.1. Podstawowe fakty
B.3.2. Lewo- i prawostronne wektory własne
B.3.3. Wyznaczanie wartości i wektorów własnych
B.3.3.1. Metoda potęgowa
B.3.3.2. Wyznaczanie par własnych laplasjanu
B.4. Normy wektorów i macierzy
Dodatek C. Teoria grafów
C.1. Podstawowe definicje
C.1.1. Grafy nieskierowane
C.1.2. Grafy skierowane
C.2. Macierze grafów
C.2.1. Macierz sąsiedztwa/podobieństwa
C.2.2. Laplasjan
C.2.2.1. Laplasjan grafu nieskierowanego
C.2.2.2. Pseudoodwrotność laplasjanu
C.2.2.3. Laplasjan grafu skierowanego
Dodatek D. Błądzenie losowe w grafie
D.1. Błądzenie losowe w grafach nieskierowanych
D.1.1. Podstawowe fakty
D.1.2. Charakterystyki błądzenia losowego
D.1.2.1. Średni czas dostępu
D.1.2.2. Czas komutacji
D.1.2.3. Czas pokrycia
D.1.2.4. Czas mieszania
D.2. Błądzenie losowe w grafach skierowanych
Dodatek E. Personalizowany wektor PageRank
E.1. Podstawowe określenia i zależności
E.2. Przybliżony algorytm wyznaczania personalizowanego
wektora PageRank
Dodatek F. Entropia
F.1. Podstawowe definicje
F.2. Entropia gaussowskiego wektora losowego
Dodatek G. Teoria Dempstera-Shafera
G.1. Funkcje charakteryzujące sądy
G.2. Reguła Dempstera
G.3. Sprowadzanie przekonań do prawdopodobieństw
Dodatek H. Optymalizacja
H.1. Submodularne funkcje zbioru
H.2. Uczenie funkcji submodularnych
H.3. Optymalizacja submodularnych funkcji zbioru
H.3.1. Minimalizacja funkcji submodularnych
H.3.1.1. Podstawowe narzędzia
Drzewo maksymalnych przepływów
Dobre pary
H.3.1.2. Algorytm Queyranne‘a
H.3.2. Maksymalizacja submodularnych funkcji
Bibliografia
Wykaz algorytmów
Skorowidz
396 stron, Format: 16.5x24.0cm, oprawa miękka
