Algorytmy analizy skupień

Mieczysław Kłopotek, Sławomir Wierzchoń

Uzyskaj dostęp

ISBN/ISSN:

978-83-01-19178-8

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2017

Liczba stron:

398

XML:ISBN/ISSN:

ONIX MARC21

Bibliografia:

Kłopotek, Mieczysław; Wierzchoń, Sławomir. Algorytmy analizy skupień. Red. . Warszawa: Wydawnictwo Naukowe PWN, 2017, 398 s. ISBN 978-83-01-19178-8

Bibliografia refWorks:

RT Book, Whole

SR Electronic(1)

A1 Kłopotek, M.

A1 Wierzchoń, S.

T1 Algorytmy analizy skupień

PB Wydawnictwo Naukowe PWN

PP Warszawa

YR 2017

SN 978-83-01-19178-8

Bibliografia BibTex:

@Book{ 194139, author = "Kłopotek, Mieczysław and Wierzchoń, Sławomir", editor = "", title = "Algorytmy analizy skupień", publisher = "Wydawnictwo Naukowe PWN", year = "2017", address = "Warszawa", isbn = "978-83-01-19178-8" }

Bibliografia endNote:

TY - BOOK

AU - Kłopotek, Mieczysław

AU - Wierzchoń, Sławomir

ED -

TI - Algorytmy analizy skupień

PB - Wydawnictwo Naukowe PWN

CY - Warszawa

PY - 2017

SN - 978-83-01-19178-8

ER -

Netografia (standard APA):

Kłopotek, Mieczysław; Wierzchoń, Sławomir. Algorytmy analizy skupień [baza danych online] Warszawa: Wydawnictwo Naukowe PWN, 2017 [dostęp: 03 07 2024]. Dostęp w Ibuk Libra: https://libra.ibuk.pl/reader/algorytmy-analizy-skupien-mieczyslaw-klopotek-slawomir-194139.

algorytmy, optymalizacja, Entropia, Teoria grafów, analiza i redukcja danych, zbiory danych, rachunek macierzowy, błądzenia losowe w grafie, wektor PageRank

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ą...

Więcej

ISBN/ISSN:

978-83-01-19178-8

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2017

Liczba stron:

398

XML:ISBN/ISSN:

ONIX MARC21

Lista ważniejszych oznaczeń12
Przedmowa14
1. Analiza skupień20
1.1. Formalizacja problemu21
1.2. Miary podobieństwa/odmienności24
1.2.1. Porównywanie obiektów o cechach ilościowych25
1.2.1.1. Odległość Minkowskiego26
1.2.1.2. Odległość Mahalanobisa29
1.2.1.3. Dywergencja Bregmana29
1.2.1.4. Odległość kosinusowa31
1.2.1.5. Odległość potęgowa31
1.2.2. Porównywanie obiektów o cechach jakościowych32
1.3. Hierarchiczne metody analizy skupień35
1.4. Metody kombinatoryczne39
1.4.1. Kryteria grupowania oparte na odmienności40
1.4.2. Zadanie analizy skupień w przestrzeni euklidesowej42
1.4.2.1. Minimalizacja śladu macierzy kowariancji wewnątrzgrupowych43
1.4.2.2. Aproksymacja macierzy danych48
1.4.2.3. Iteracyjny algorytm znajdowania skupień49
1.4.3. Grupowanie według objętości skupień52
1.4.4. Uogólnienia zadania grupowania53
1.5. Inne metody analizy skupień54
1.5.1. Metody relacyjne55
1.5.2. Metody grafowe i spektralne55
1.5.3. Metody gęstościowe56
1.5.4. Metody funkcji potencjalnych (jądrowych)61
1.5.5. Rodziny grupowań68
1.6. Grupowanie jako zadanie optymalizacji submodularnej74
1.6.1. Podział na dwie grupy75
1.6.1.1. Metoda pojedynczego wiązania76
1.6.1.2. Grupowanie z użyciem informacji wzajemnej78
1.6.2. Przypadek większej liczby grup79
1.6.3. Wyznacznikowe procesy punktowe (DPP)80
1.6.3.1. Podstawowe pojęcia81
1.6.3.2. Grupowanie na podstawie DPP83
1.7. Czy i kiedy grupowanie jest trudne?85
2.1. Algorytm k-średnich89
2. Algorytmy kombinatorycznej analizy skupień89
2.1.1. Klasyczny (wsadowy) wariant algorytmu k-średnich93
2.1.2. Iteracyjny wariant algorytmu k-średnich93
2.1.3. Metody inicjowania algorytmu k-średnich95
2.1.3.1. Algorytm k-średnich++98
2.1.4. Usprawnienia algorytmu k-średnich100
2.1.3.2. Algorytm k-średnich D++100
2.1.5. Warianty algorytmu k-średnich102
2.1.5.1. Wariant on line algorytmu k-średnich102
2.1.5.2. Bisekcyjny wariant algorytmu k-średnich104
2.1.5.3. Sferyczny algorytm k-średnich105
2.1.5.4. KHM: algorytm k-średnich harmonicznych108
2.1.5.5. Jądrowy algorytm k-średnich110
2.1.5.6. Algorytm k-medoid113
2.1.5.7. Algorytm k-mod116
2.2. Algorytm EM120
2.3. FCM: algorytm k-średnich rozmytych124
2.3.1. Podstawowe sformułowanie124
2.3.2. Podstawowy algorytm FCM128
2.3.3. Miary jakości rozmytego podziału133
2.3.4. Sformułowanie alternatywne137
2.3.5. Modyfikacje algorytmu FCM138
2.3.5.1. Algorytm FCM z metryką Minkowskiego140
2.3.5.2. Algorytm Gustafsona–Kessela (GK)142
2.3.5.3. Algorytm FCV: Fuzzy c-varietes144
2.3.5.4. Algorytm FCS: Fuzzy c-shells146
2.3.5.5. SFCM: Sferyczny algorytm FCM147
2.3.5.6. Jądrowe warianty algorytmu FCM148
Algorytm KFCM-X148
Algorytm KFCM-F150
2.3.5.7. PCM: possibilistyczny algorytm grupowania152
2.3.5.8. Relacyjny wariant algorytmu FCM156
2.4. Grupowanie na podstawie funkcji alokacji prawdopodobieństwa158
2.4.1. Podziały fiducjarne160
2.4.2. Od podziałów fiducjarnych do ostrych162
2.5. Propagacja powinowactwa164
3.1. Przygotowanie danych167
3. Ocena jakości skupień i stosowalności algorytmów167
3.2. Wybór liczby skupień169
3.2.1. Proste heurystyki170
3.2.2. Metody wykorzystujące kryteria informacyjne171
3.3. Miary jakości podziału172
3.2.3. Klastergramy172
3.4. Porównywanie podziałów176
3.4.1. Proste metody porównywania podziałów177
3.4.2. Metody pomiaru części wspólnych podziałów178
3.4.3. Metody wykorzystujące wzajemną informację180
3.5. Miary jakości pokrycia182
3.6. Analiza dużych zbiorów danych183
3.6.1. Proste usprawnienia183
3.6.1.1. FFCM: szybki algorytm FCM184
PFCM: równoległy algorytm FCM185
WFCM: ważony algorytm FCM185
mrFCM: algorytm FCM z wieloetapowym próbkowaniem186
4. Metody spektralne w analizie i redukcji danych188
4.1. Notacja193
4.2. Spektralna analiza danych197
4.2.1. Optymalizacja spektralna197
4.2.1.1. Przypadek dwóch klas197
4.2.1.2. Dalsze zastosowania wektora Fiedlera203
4.2.1.3. Przypadek wielu klas205
4.2.2. Alternatywne funkcje kryterialne208
4.2.3. Zadanie rozcinania grafu jako uogólniony problem własny211
4.2.4. Metody rozwiązywania uogólnionego problemu własnego216
4.2.5. Spektralne algorytmy grupowania danych221
4.2.5.1. Algorytm normalizowanych cięć Shi i Malika (SM)224
4.2.5.2. Algorytm normalizowanych cięć Vermy i Meili (VM)225
4.2.5.3. Spektralne odwzorowanie Ng, Jordana i Weissa (NJW)226
4.2.5.4. Algorytm DaSpec230
4.2.6. Maksymalizacja spójności grup233
4.2.7. Przykłady235
4.2.8. Dostrajanie algorytmu239
4.2.8.1. Wybór parametru ω239
4.2.8.2. Wzmacnianie struktury blokowej241
4.3. Błądzenie losowe w grafach243
4.3.1. Błądzenie losowe w grafach nieskierowanych244
4.3.1.1. Proste interpretacje244
4.3.1.2. Grupowanie węzłów według ich potencjału248
4.3.1.3. Odległość rezystancyjna251
4.3.1.4. Grupowanie węzłów według czasu pochłonięcia252
4.3.2. Zastosowanie idei błądzenia po grafie: algorytm MCL255
4.3.2.1. Podstawowa wersja algorytmu255
4.3.2.2. Problemy z algorytmem257
4.4. Metody lokalne259
4.4.1. Algorytm Nibble261
4.4.2. Algorytm PageRank-Nibble264
4.5. Uczenie częściowo nadzorowane268
4.6. Usprawnienia i inne metody272
4.6.1. Grupowanie z wykorzystaniem p-laplasjanu272
4.6.2. Grupowanie stochastyczne274
4.6.3. Zastosowanie algorytmu SVD279
4.6.4. Algorytm PIC280
4.6.5. Algorytm PRC282
4.7. Metody redukcji wymiarowości283
5. Zbiory danych287
Dodatek A. Uzasadnienie algorytmu FCM289
Dodatek B. Rachunek macierzowy291
B.1. Wektory i ich własności291
B.2. Macierze i ich własności292
B.3. Wartości i wektory własne295
B.3.1. Podstawowe fakty295
B.3.2. Lewo- i prawostronne wektory własne300
B.3.3. Wyznaczanie wartości i wektorów własnych302
B.3.3.1. Metoda potęgowa302
B.3.3.2. Wyznaczanie par własnych laplasjanu304
B.4. Normy wektorów i macierzy306
Dodatek C. Teoria grafów308
C.1. Podstawowe definicje308
C.1.1. Grafy nieskierowane309
C.1.2. Grafy skierowane310
C.2. Macierze grafów311
C.2.1. Macierz sąsiedztwa/podobieństwa311
C.2.2. Laplasjan313
C.2.2.1. Laplasjan grafu nieskierowanego313
C.2.2.2. Pseudoodwrotność laplasjanu316
C.2.2.3. Laplasjan grafu skierowanego317
Dodatek D. Błądzenie losowe w grafie319
D.1. Błądzenie losowe w grafach nieskierowanych319
D.1.1. Podstawowe fakty319
D.1.2. Charakterystyki błądzenia losowego323
D.1.2.1. Średni czas dostępu323
D.1.2.2. Czas komutacji324
D.2. Błądzenie losowe w grafach skierowanych325
D.1.2.3. Czas pokrycia325
D.1.2.4. Czas mieszania325
Dodatek E. Personalizowany wektor PageRank327
E.1. Podstawowe określenia i zależności327
E.2. Przybliżony algorytm wyznaczania personalizowanego wektora PageRank331
Dodatek F. Entropia335
F.1. Podstawowe definicje335
F.2. Entropia gaussowskiego wektora losowego337
Dodatek G. Teoria Dempstera–Shafera339
G.1. Funkcje charakteryzujące sądy339
G.2. Reguła Dempstera342
G.3. Sprowadzanie przekonań do prawdopodobieństw343
Dodatek H. Optymalizacja345
H.1. Submodularne funkcje zbioru345
H.2. Uczenie funkcji submodularnych348
H.3. Optymalizacja submodularnych funkcji zbioru349
H.3.1. Minimalizacja funkcji submodularnych349
Drzewo maksymalnych przepływów352
H.3.1.1. Podstawowe narzędzia352
Dobre pary355
H.3.1.2. Algorytm Queyranne’a357
H.3.2. Maksymalizacja submodularnych funkcji360
Bibliografia362
Wykaz algorytmów390
Skorowidz392

1.2.Miarypodobieństwa/odmienności

Skorowartośćrreprezentujekosinuskątamiędzy(centrowanymi)wek-

toramiXi,Xj,to

dtg(Xi,Xj)=J1−r2(Xi,Xj)

r2(Xi,Xj)

(1.16)

możnapotraktowaćjakoodległośćtangensową.Tangensowamiaraodległo-

ści,dtg,opartajestnazasobieinformacjiwspólnejniesionejprzezanalizo-

wanecechy.Wektoryrównoległe(r=1)iantyrównoległe(r=−1)niosą

takąsamąinformację,awięcichodległośćwynosi0,podobieństwojestnaj-

większeirówne1.Natomiastwektoryortogonalnesąnieskończenieodległe

imajązerowepodobieństwo,gdyżkażdyznichzawieracałkowicieróżnąin-

formację.Wektoryowspółczynnikachkorelacjiróżnychod0i±1zawierają

wczęściinformacjęspecyﬁczną,awczęściinformacjęwspólną.Zawartośćtej

wspólnejinformacjijestmiarąichpodobieństwa.Tangensowamiaraodle-

głościmaobecnieszerokiezastosowaniewanaliziepodobieństwa13.Kolejny,

normalizowany,wariantkorelacyjnejmiarypodobieństwa,to

rn(Xi,Xj)=

2(r(Xi,Xj)+1)

(1.17)

gwarantujący,żer(Xi,Xj)∈[0,1].Wbioinformatycestosujesiętzw.kwa-

dratowąodległośćkorelacyjnądb(Xi,Xj)=1−r2(Xi,rj)doporównywania

proﬁligenetycznych14.Szereginteresującychuwagowłasnościachwspół-

czynnikakorelacjimożnaznaleźćwpracy[311].

KorelacjaPearsonajestmiarodajna,jeżeliporównywanezmiennepod-

legająrozkładowinormalnemu.Wprzypadkuprzeciwnymnależystosować

innemiarypodobieństwa.

Wspomnijmywreszcieoodległościchi-kwadratzdeﬁniowanejnastępu-

jąco

dχ2(X,y)=

il1

(xi−yi)2

xi+yi

(1.18)

awykorzystywanejdoporównywaniahistogramów15.Odległośćtaznajduje

13Por.np.J.Mazerski.Podstawychemometrii,Gdańsk2004.Wydanieelektro-

nicznedostępnepodadresemhttp://www.pg.gda.pl/chem/Katedry/Leki_Biochemia/

dydaktyka/chemometria/podstawy_chemometrii.zip.

14Por.http://www.improvedoutcomes.com/docs/WebSiteDocs/Clustering/

Clustering_Parameters/Pearson_Correlation_and_Pearson_Squared_Distance_

Metric.htm.

15Por.V.Asha,N.U.Bhajantri,P.Nagabhushan:GLCM-basedchi-squarehistogram

distanceforautomaticdetectionofdefectsonpatternedtextures.Int.J.ofComputational

VisionandRobotics,2(4),2011,pp.302–313.

Brak wyników

Algorytmy analizy skupień

Treść książki

Znajdź bibliotekę blisko siebie, i uzyskaj dostęp do ebooka w systemie IBUK Libra