Fakulta Dopravní Ústav aplikované matematiky. v dopravní problematice

ˇ Cesk´ e vysok´ e uˇ cen´ı technick´ e Fakulta Dopravn´ı ´ Ustav aplikovan´ e matematiky Czech Technical University in Prague Faculty of Transportation Sciences Department of Applied Matematics

Vyuˇ zit´ı shlukov´ e anal´ yzy v dopravn´ı problematice The usage of cluster analysis in transport problems

Bakal´ aˇ rsk´ a pr´ ace

ˇ Skolitel: doc. Ing. Ivan Nagy, CSc. Studijn´ı program: 3710 Technika a technologie v dopravˇe a spoj´ıch Studijn´ı obor: 2612R004 Automatizace a informatika

Prague, 2011

Tereza Mlyn´aˇrov´a

Podˇ ekov´ an´ı Na tomto m´ıstˇe bych r´ ada podˇekovala vˇsem, kteˇr´ı mi poskytli podklady pro vypracov´ an´ı t´eto pr´ ace. Zvl´aˇstˇe pak dˇekuji doc. Ing. Ivanu Nagymu, CSc. za odborn´e veden´ı a konzultov´ an´ı bakal´aˇrsk´e pr´ace a za rady, kter´e mi poskytoval po celou dobu m´eho studia. ´ D´ ale bych chtˇela podˇekovat pracovn´ık˚ um UTIA za umoˇznˇen´ı pˇr´ıstupu k mnoha d˚ uleˇzit´ ym informac´ım a materi´al˚ um. V neposledn´ı ˇradˇe je mou milou povinnost´ı podˇekovat sv´e rodinˇe, pˇr´ıteli a bl´ızk´ ym za mor´aln´ı a materi´aln´ı podporu, kter´e se mi dost´ avalo po celou dobu studia.

Prohl´ aˇ sen´ı Pˇredkl´ ad´ am t´ımto k obhajobˇe bakal´aˇrskou pr´aci, zpracovanou na z´avˇer baˇ kal´ aˇrsk´eho studia na CVUT v Praze na Fakultˇe dopravn´ı. Prohlaˇsuji, ˇze jsem svou bakal´aˇrskou pr´aci vypracovala samostatnˇe a pouˇzila jsem pouze podklady uveden´e v seznamu pouˇzit´e literatury. Nem´am z´avaˇzn´ y d˚ uvod proti uˇzit´ı tohoto d´ıla ve smyslu § 60 Z´akona ˇc.121/2000 Sb., o pr´avu autorsk´em, o pr´ avech souvisej´ıc´ıch s pr´avem autorsk´ ym a o zmˇenˇe nˇekter´ ych z´ akon˚ u (autorsk´ y z´ akon).

..................................................... podpis Praha, ˇcerven 2011

2

Abstrakt Pˇredmˇetem bakal´ aˇrsk´e pr´ ace “Vyuˇzit´ı shlukov´e anal´ yzy v dopravn´ı problematice” je porovn´ an´ı z´ akladn´ıch metod shlukov´e anal´ yzy, uveden´ı jejich vlastnost´ı, resp. siln´ ych a slab´ ych str´ anek, coˇz je prakticky uk´az´ano na experimentech. Shlukov´e algoritmy jsou aplikov´any nejprve na simulovan´a data a pak na data re´ aln´ a, kter´ a byla z´ısk´ ana z dopravn´ıho mˇeˇren´ı. Shlukov´an´ı lze povaˇzovat za ned´ılnou souˇc´ ast dopravn´ıch anal´ yz.

Abstract The topic of the work “The usage of cluster analysis in transport problems” is to compare basic methods of cluster analysis, to mention their properties, or strong and weak points, which is practically demonstrated on experiments. Firstly, cluster algorithms are applied on simulated data and then on real data that was obtained by a traffic measurement. It is possible to consider clustering as the entire part of every traffic analysis.

3

Obsah ´ 1 Uvod 1.1 Motivace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Formulace u ´lohy . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Definice a pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Vybran´ e metody shlukov´ e anal´ yzy 2.1 Algoritmus Kmeans . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Z´ akladn´ı algoritmus Kmeans . . . . . . . . . . . . . . 2.1.2 Dodatky algoritmu Kmeans . . . . . . . . . . . . . . . 2.1.3 P˚ ulic´ı Kmeans . . . . . . . . . . . . . . . . . . . . . . 2.1.4 Kmeans a r˚ uzn´e typy shluk˚ u . . . . . . . . . . . . . . 2.1.5 Siln´e a slab´e str´anky . . . . . . . . . . . . . . . . . . . 2.2 Hierarchick´e shlukov´an´ı . . . . . . . . . . . . . . . . . . . . . 2.2.1 Z´ akladn´ı aglomerativn´ı hierarchick´ y algoritmus . . . . 2.2.2 Uk´ azka metod na pˇr´ıkladˇe . . . . . . . . . . . . . . . . 2.2.3 Lanc˚ uv-Williams˚ uv vztah pro sousedstv´ı (L-W vztah) 2.2.4 Probl´emy hierarchick´eho shlukov´an´ı . . . . . . . . . . 2.3 DBSCAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Z´ akladn´ı idea DBSCANu . . . . . . . . . . . . . . . . 2.3.2 Algoritmus DBSCAN . . . . . . . . . . . . . . . . . . 2.3.3 Siln´e a slab´e str´anky DBSCANu . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

5 5 8 8 10 10 10 16 18 19 20 21 22 25 29 30 31 31 33 36

3 Testov´ an´ı 3.1 Simulovan´ a data . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Testov´ an´ı Kmeans na simulovan´ ych datech . . . . . . . . 3.1.2 Testov´ an´ı hierarchick´eho algoritmu na simulovan´ ych datech 3.1.3 Testov´ an´ı DBSCANu na simulovan´ ych datech . . . . . . . 3.2 Re´ aln´ a data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37 37 37 38 40 42

4 Z´ avˇ er

46

5 Pˇ r´ıloha 5.1 Co je shlukov´ a anal´ yza (cluster analysis)? 5.2 Souˇc´ asti u ´lohy shlukov´an´ı . . . . . . . . . 5.3 R˚ uzn´e druhy shluk˚ u . . . . . . . . . . . . 5.4 Mˇeˇren´ı podobnosti . . . . . . . . . . . . . 5.5 R˚ uzn´e druhy shlukov´an´ı . . . . . . . . . .

48 48 50 52 54 59

4

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

1 1.1

´ Uvod Motivace

Pokud si kdekoli do vyhled´ avaˇce zad´ate “Definuj dopravu,”, vˇetˇsinou se uk´aˇze definice : “Doprava je zp˚ usob pohybov´an´ı se objekt˚ u z m´ısta na m´ısto. Jde o pˇremist’ov´ an´ı...”. Je vˇsak doopravdy pod pojmem Doprava schov´ano pouh´e pˇremist’ov´ an´ı? Ano, dˇr´ıve doprava znamenala pouh´ y pˇresun z m´ısta na m´ısto. Jsou vˇsak pryˇc doby, kdy jsme mohli spoˇc´ıtat auta na kˇriˇzovatk´ach na prstech jedn´e ruky, kdy bylo ropy takˇrka na rozd´ av´ an´ı, kdy jsme mohli v´est nov´e pozemn´ı komunikace kdekoli a nezaj´ımala n´ as ot´ azka z´aboru p˚ udy, kdy hluk a zplodiny byly pouh´e pojmy ve slovn´ıku,... Ve v´ yˇctu vˇec´ı, kter´e jsou jiˇz minulost´ı, bychom mohli pokraˇcovat smˇele d´ ale. Pˇr´ıtomnost s sebou nyn´ı pˇrin´aˇs´ı u ´plnˇe jin´ y n´ahled na dopravu. Nov´ y n´ahled. Sloˇzit´e pˇrepravn´ı vztahy, nar˚ ustaj´ıc´ı intenzity, automobilizace, d´elky kolon, doch´azej´ıc´ı ropa a hled´ an´ı alternativn´ıch paliv, hluk pˇrevyˇsuj´ıc´ı dovolen´e limity, nar˚ ustaj´ıc´ı u ´roveˇ n nehodovosti... Na druhou stranu n´am nyn´ı doprava umoˇzn ˇuje to, co bylo pˇred nˇekolika des´ıtky let v pouh´ ych pˇredstav´ach a snech lid´ı. Cestov´an´ı aˇz na druhou stranu zemˇekoule za p´ar hodin, schopnost pˇrepravit t´emˇeˇr libovoln´e mnoˇzstv´ı materi´ al˚ u a zboˇz´ı, integrace mˇestsk´e hromadn´e dopravy, inovace dopravn´ıch prostˇredk˚ u,... Nab´ız´ı se ot´ azka - “Jde dneˇsn´ı v´ yvoj dopravn´ı techniky a dopravn´ıch technologi´ı spr´ avn´ ym smˇerem?” Samozˇrejmˇe nelze na tuto ot´azku jednoduˇse odpovˇedˇet. Vˇse m´ a sv´e pozitivn´ı a negativn´ı str´anky. Naˇs´ım u ´kolem vˇsak je eliminovat ˇ sen´ı probl´em˚ d˚ usledky negativn´ıch vliv˚ u a zamˇeˇrit se na samotn´a pozitiva. Reˇ u se ub´ır´ a tˇremi smˇery. Jinak ˇreˇceno zamˇeˇrujeme se na zm´ınˇen´e probl´emy ze tˇrech hledisek. Chceme, aby n´ aklady spojen´e s dopravou byly co nejmenˇs´ı, aby dopad na ˇzivotn´ı prostˇred´ı byl co nejm´enˇe ˇskodliv´ y a hlavnˇe poˇzadujeme, aby pro n´as doprava byla prostˇredkem, ve kter´em se budeme c´ıtit bezpeˇcnˇe a kter´ y pro n´as bude bezpeˇcn´ y. Nahl´ıˇz´ıme tedy na vˇec z hledisek ekonomick´ ych, ekologick´ ych a bezpeˇcnostn´ıch. Situaci je moˇzno mˇeˇren´ım r˚ uzn´ ych veliˇcin analyzovat pomoc´ı dat, kter´e sebereme na n´ ami sledovan´ ych objektech. D´ıky sebran´ ym dat˚ um se pohybujeme v nˇekolika-dimenzion´ aln´ıch prostorech. Mˇeˇren´ı v jednom ˇcasov´em okamˇziku pˇredstavuj´ı pr´ avˇe jeden bod v prostoru (pokud uvaˇzujeme dvˇe veliˇciny, pak hovoˇr´ıme o rovinˇe). Vypov´ıdac´ı schopnost dat m˚ uˇzeme demonstrovat na obr´azku 1 jako bezpeˇcnou a nebezpeˇcnou oblast dat. Existuj´ı r˚ uzn´e metody, jak eliminovat probl´emy spojen´e s dopravou. M˚ uˇzeme z´ akonem navrhnout nˇejak´ a nov´a opatˇren´ı, ˇci opravit st´avaj´ıc´ı, zv´ yˇsit policejn´ı dohled na pozemn´ıch komunikac´ıch, uˇcinit stavebn´ı u ´pravy ˇci zlepˇsit techniku v dopravn´ıch prostˇredc´ıch. Posledn´ı z´aleˇzitost´ı se budu zab´ yvat bl´ıˇze. Zaujala mˇe myˇslenka vylepˇsen´ı technick´eho prostˇred´ı uvnitˇr automobil˚ u pomoc´ı nov´eho zaˇr´ızen´ı - jak´esi “krabiˇcky”. Tato krabiˇcka bude dodateˇcn´ ym vybaven´ım, 5

Obr´ azek 1: Bezpeˇcn´a vs. nebezpeˇcn´a oblast dat Jsou zde zobrazena data z re´aln´e j´ızdy. Graf vyjadˇruje z´avislost mezi natoˇcen´ım volantu a rychlost´ı, tud´ıˇz se pohybujeme ve dvourozmˇern´em prostoru (resp. v rovinˇe). Pokud budeme na obr´ azek nahl´ıˇzet z bezpeˇcnostn´ıho hlediska, tak namˇeˇren´ a data zobrazuj´ı vesmˇes j´ızdu bezpeˇcnou. Pokud se tedy nˇejak´e body objev´ı v horn´ı ˇca ´sti obr´ azku a nav´ıc smˇerem do stran, jedn´ a se o j´ızdu nebezpeˇcnou jedeme tedy rychle a jeˇstˇe k tomu do zat´ aˇcky.

jako je napˇr´ıklad navigace, v´ ystraˇzn´e zaˇr´ızen´ı ˇci parkovac´ı ˇcidla. Tyto krabiˇcky budou obsahovat programy, kter´e budou hodnotit naˇsi j´ızdu, resp. styl naˇseho ˇr´ızen´ı z v´ yˇse zm´ınˇen´ ych tˇr´ı hledisek. Bude tedy potˇreba mˇeˇrit data jak na autˇe, tak na samotn´em ˇridiˇci, n´ aslednˇe tato data analyzovat a na z´akladˇe anal´ yzy dat podat rady ˇridiˇci ke zlepˇsen´ı jeho ˇr´ızen´ı, ˇci ho varovat pˇred nebezpeˇcnou j´ızdou. Pokud bychom se tedy v pˇr´ıpadˇe zobrazen´em na obr´azku 1 pohybovali v nebezpeˇcn´e oblasti dat - jeli bychom tedy pˇr´ıliˇs rychle do prudk´e zat´aˇcky, krabiˇcka by n´ as upozornila a naˇse kroky by vedly prvnˇe ke sn´ıˇzen´ı rychlosti a v pˇr´ıpadˇe, ˇze jsme jiˇz za zat´aˇckou, ke srovn´an´ı volantu. T´ım bychom se dostali do bezpeˇcnˇejˇs´ıho m´ odu. Jako matematick´ y n´ astroj pouˇziji klastrov´an´ı a klasifikaci. D´ıky klastrov´an´ı vytvoˇr´ıme model, klasifikac´ı ho pot´e reprezentujeme. V praxi na ˇridiˇce p˚ usob´ı des´ıtky (mnohdy aˇz stovky) vliv˚ u, kter´e je pˇri ˇr´ızen´ı pˇr´ımo, ˇci nepˇr´ımo ovlivˇ nuj´ı. V´ ysledkem tˇechto vliv˚ u pak je, ˇze se automobil i s ˇridiˇcem pohybuje v urˇcit´ ych oblastech (pracovn´ıch m´ odech).

6

Pro lepˇs´ı n´ azornost, jak vypad´a sloˇzitˇejˇs´ı soustava pracovn´ıch m´od˚ u, resp. shluku dat na re´ alnˇe mˇeˇren´ ych datech, m˚ uˇzeme uv´est j´ızdu automobilem, pˇri kter´e mˇeˇr´ıme pˇrid´ av´ an´ı plynu a rychlost. Tato data jsou vykreslena na obr´azku 2.

Obr´ azek 2: Uk´azka pracovn´ıch m´od˚ u (shluk˚ u) Na obr´ azku jsou zobrazena re´ aln´ a data v dvourozmˇern´em prostoru. Na ose x je zobrazen plyn [%]. Na ose y rychlost [km/h].

Jiˇz pouh´ ym okem a bez jak´ekoli pˇredchoz´ı informace jsme schopni analyzovat ˇ danou situaci. Reknˇ eme, ˇze jsou zde rozpoznateln´e ˇctyˇri shluky, kter´e pˇredstavuj´ı rozj´ıˇzdˇen´ı (n´ızk´e rychlosti a r˚ uznˇe velk´ y plyn), j´ızdu mˇestem (hodnoty kolem rychlosti 50 km/h s opˇet r˚ uznˇe velk´ ym plynem), j´ızdu mimo mˇesto (rychlosti kolem 90 km/h s podobn´ ymi hodnotami plynu jako v pˇredchoz´ım pˇr´ıpadˇe) a nakonec j´ızdu na d´ alnici (rychlost kolem 130 km/h s vyˇsˇs´ı hodnotou plynu oproti ostatn´ım pˇr´ıpad˚ um). Jak vˇsak striktnˇe urˇcit pˇr´ısluˇsnosti jednotliv´ ych bod˚ u k dan´ ym skupin´ am? To je pr´avˇe u ´kol shlukov´e anal´ yzy - nalezen´ı m´od˚ u bezpeˇcnosti, resp. nebezpeˇcnosti. O pracovn´ıch m´ odech tedy vypov´ıdaj´ı data mˇeˇren´a jak na autˇe, tak na ˇridiˇci. Mˇeˇren´ a data hraj´ı v tomto pˇr´ıpadˇe kl´ıˇcovou roli, a tak mus´ıme db´at o jejich peˇcliv´ y v´ ybˇer. Daty mˇeˇren´ ymi na automobilu mohou b´ yt veliˇciny jako poloha automobilu, ˇci volantu, plyn, brzda, rotace, pˇr´ıˇcn´e zrychlen´ı, rychlosti jednotliv´ ych kol, ot´ aˇcky motoru, moment motoru, apod. Daty mˇeˇren´ ymi na ˇridiˇci jsou napˇr. pohyby v´ıˇcek, v´ yraz tv´aˇre, EEG, teplotn´ı mapa obliˇceje, u ´nava, reakˇcn´ı doba atd. Jak je jiˇz vidˇet, budeme se pohybovat v n - dimenzion´aln´ım prostoru (n ud´av´a poˇcet mˇeˇren´ ych veliˇcin). Data budou mˇeˇrena v diskr´etn´ım ˇcase, kdy v kaˇzd´em

7

ˇcase dostaneme datov´ y vektor (vektor namˇeˇren´ ych hodnot). Tento vektor pˇredstavuje bod v datov´em prostoru. Uspoˇr´ad´ame-li datov´e vektory od poˇc´atku mˇeˇren´ı aˇz do aktu´ aln´ıho ˇcasu pod sebe, dostaneme datovou matici. V datov´e matici m˚ uˇzeme nal´ezt ˇr´ adky se stejn´ ymi (podobn´ ymi) hodnotami, coˇz jsou m´ody syst´emu, neboli shluky. Jin´ ymi slovy ˇreˇceno - pokud se tedy nˇekter´e situace (tj. datov´e vektory) opakuj´ı jen s mal´ ymi odchylkami, vytv´aˇr´ı se skupiny bod˚ u (shluky), kter´e reprezentuj´ı pr´ avˇe konkr´etn´ı pracovn´ı m´ody, at’ uˇz ˇspatn´e (neˇz´adouc´ı), nebo dobr´e (ˇz´ adouc´ı). Konstrukce syst´emu ˇridiˇc - automobil v sobˇe ukr´ yv´a dvˇe f´aze - f´azi uˇcen´ı a klasifikace. ˆ Ve f´ azi uˇcen´ı doch´ az´ı ke klastrov´an´ı, tedy k detekci shluk˚ u v datech z uˇc´ıc´ı (tr´enovac´ı) mnoˇziny. ˆ Pˇri klasifikaci se zmˇeˇren´ y datov´ y vektor se pˇriˇrad´ı do urˇcit´eho shluku a t´ım se detekuje aktu´ aln´ı pracovn´ı m´od a jeho ohodnocen´ı - v naˇsem pˇr´ıpadˇe je to ˇspatn´e, ˇci dobr´e ˇr´ızen´ı.

Existuje nˇekolik metod klastrov´an´ı (shlukov´an´ı). Jakou metodu zvol´ıme, z´aleˇz´ı zejm´ena na typu vstupn´ıch dat, kter´e chceme analyzovat. Na v´ ybˇer pˇritom m´ame z ˇsirok´e ˇsk´ aly metod hierarchick´ ych a nehierarchick´ ych. D´ ale jsou zde metody Bayesovsk´e statistiky, kter´e vytv´aˇr´ı modely smˇesi hustot pravdˇepodobnost´ı (hustoty se naz´ yvaj´ı komponenty). Tato technika mˇe velmi zaujala, a tak bych se j´ı chtˇela delˇs´ı dobu vˇenovat. Zamˇeˇr´ım se vˇsak nyn´ı na metody klasick´e shlukov´e anal´ yzy, kdy se jedn´a zejm´ena o statickou anal´ yzu dat. D˚ uvodem je, abych byla pot´e schopna hledat klady a z´apory metody Bayesovstv´ı, tedy klasifikace dynamick´e v ˇcase.

1.2

Formulace u ´ lohy

C´ılem t´eto pr´ ace je vytvoˇren´ı pˇrehledu o metod´ach shlukov´e anal´ yzy, jejich zhodnocen´ı a vz´ ajemn´e porovn´an´ı. Hlavn´ım bodem bude pˇrehled o existuj´ıc´ıch shlukov´ ych algoritmech. Tyto algoritmy budu nejprve teoreticky charakterizovat a n´ aslednˇe na nich bude ovˇeˇreno vyuˇzit´ı pro naˇse moˇznosti, tedy moˇznosti klastrov´ an´ı dopravn´ıch dat. Na jednotliv´ ych algoritmech budou provedeny experimenty. Na z´ akladˇe v´ ysledk˚ u budu ilustrovat vhodnost jejich pouˇzit´ı pro r˚ uzn´e formy dat.

1.3

Definice a pojmy

ˆ vzorek – je nez´ avisl´ y druh dat, se kter´ ym se pracuje u shlukov´ ych algoritm˚ u. Typick´e je, ˇze se skl´ad´a z datov´eho vektoru – vektoru mˇeˇren´ ych veliˇcin v ˇcase t. ˆ atribut – veliˇcina z datov´eho vektoru.

8

ˆ dimenze datov´ eho vektoru – poˇcet veliˇcin datov´eho vektoru. ˆ b´ aze – mnoˇzina line´ arnˇe nez´avisl´ ych datov´ ych vektor˚ u. ˆ tˇ r´ıda, skupina – mnoˇzina realizac´ı datov´eho vektoru, kter´a patˇr´ı do stejn´eho klastru. ˆ realizace datov´ eho vektoru – je vektor hodnot namˇeˇren´ ych veliˇcin (bod v datov´em prostoru). ˆ datov´ a matice - je v´ ysledkem vˇsech realizac´ı (vznikne poskl´ad´an´ım realizac´ı datov´eho vektoru do matice) ˆ ˇ sum – je n´ ahodn´ a sloˇzka mˇeˇren´eho vzorku, kter´a umoˇzn ˇuje vzniknout vzhledem k n´ ahodnosti sledovan´eho procesu nebo jako chyba mˇeˇren´ı. ˆ outlier – je vzorek dat, kter´ y je velmi vzd´alen´ y od zbytku dat, a tak necharakterizuje jejich pˇrirozenou strukturu. Vˇetˇsinou se jedn´a o ˇsum. ˆ matice sousednosti - je ˇctvercov´ a (pro neorientovan´e grafy i symetrick´a) matice grafu G, pro kterou plat´ı vztah (1).

AG

=

(aij )ni,j=1 definovan´a pˇredpisem :

aij

=

1 pro {vi, vj } ∈ E , kde v1 , ..., vn oznaˇcuj´ı vrcholy dan´eho grafu Ga Eje mnoˇzina hran a ,

=

0 pro ostatn´ı pˇr´ıpady - tedy pokud neexistuje hrana mezi dan´ ymi vrcholy.

9

(1)

2

Vybran´ e metody shlukov´ e anal´ yzy

Na shlukov´ an´ı, resp. shlukovou anal´ yzu je moˇzn´e nahl´ıˇzet z nˇekolika r˚ uzn´ ych pohled˚ u. Pokud ˇreˇs´ıme ot´ azku, zda chceme m´ıt shluky hierarchicky uspoˇr´adan´e, jin´ ymi slovy chceme, aby mezi nimi platil vztah nadˇrazenosti a podˇrazenosti, vol´ıme mezi hierarchick´ ym a nehierarchick´ ym shlukov´an´ım. U hierarchick´eho shlukov´ an´ı jeˇstˇe rozliˇsujeme aglomerativn´ı a divizivn´ı pˇr´ıstup (viz Pˇr´ıloha 5.5). D´ ale m˚ uˇzeme ˇreˇsit, zda jeden prvek lze pˇriˇradit pouze do jednoho shluku, pak se jedn´ a o shlukov´ an´ı v´ yluˇcn´e, nebo do v´ıce shluk˚ u z´aroveˇ n, pak hovoˇr´ıme o pˇrekr´ yvaj´ıc´ım se shlukov´ an´ı. Zvl´aˇstn´ım pˇr´ıpadem pˇr´ısluˇsnosti vzork˚ u je fuzzy shlukov´ an´ı charakterizov´ ano funkc´ı pˇr´ısluˇsnosti. Zda dan´ y shlukov´ y algoritmus uvaˇzuje ˇsum ˇci outliery, zodpov´ı ot´azka u ´pln´eho a ˇc´asteˇcn´eho shlukov´an´ı. Dalˇs´ı dˇelen´ı shlukov´ an´ı je na deterministick´e a stochastick´e. Nicm´enˇe doprava je sama o sobˇe stochastick´ y syst´em, takˇze determinismus v tomto pˇr´ıpadˇe nebude v˚ ubec uvaˇzov´ an. Zm´ınˇen´e dˇelen´ı a bliˇzˇs´ı popis jednotliv´ ych technik je pˇredstaven v Pˇr´ıloze 5.5. V t´eto ˇc´ asti budou po teoretick´e str´ance pˇredstaveny vybran´e algoritmy shlukov´ an´ı, na kter´ ych bude v ˇca´sti testov´an´ı provedeno nˇekolik experiment˚ u jak na simulovan´ ych, tak na re´ aln´ ych datech.

2.1

Algoritmus Kmeans

Techniky shlukov´ an´ı zaloˇzen´e na modelu rozdˇeluj´ı jedno´ urovˇ novˇe (nehierarchicky) datov´e prvky. Existuje nˇekolik takov´ ych technik, z nichˇz jsou dvˇe nejd˚ uleˇzitˇejˇs´ı, a to Kmeans a Kmedoid. Budu se zde zab´ yvat pouze algoritmem Kmeans. Kmeans definuje model ve formˇe tˇeˇziˇstˇe, coˇz je obvykle pr˚ umˇer z cel´e skupiny prvk˚ u. Model je zpravidla aplikov´ an na data ve spojit´em n - dimenzion´aln´ım prostoru, proto je Kmeans jedn´ım z nejstarˇs´ıch a nejrozˇs´ıˇrenˇejˇs´ıch shlukov´ ych algoritm˚ u. 2.1.1

Z´ akladn´ı algoritmus Kmeans

Technika shlukov´ an´ı Kmeans je povaˇzov´ana za jednoduchou. Nejprve vybereme K z´ akladn´ıch tˇeˇziˇst’, kde K je parametrem definovan´ ym uˇzivatelem (konkr´etnˇe poˇcet poˇzadovan´ ych shluk˚ u). Kaˇzd´ y bod je oznaˇcen a pˇrid´an nejbliˇzˇs´ımu tˇeˇziˇsti a kaˇzd´e seskupen´ı bod˚ u pˇriˇrazen´e jednomu tˇeˇziˇsti je povaˇzov´ano za shluk. Tˇeˇziˇstˇe kaˇzd´eho shluku je pot´e aktualizov´ano vzhledem k prvk˚ um pˇriˇrazen´ ym do dan´eho klastru. Tento krok je neust´ ale opakov´an, dokud se mˇen´ı sloˇzen´ı prvk˚ u ve shluc´ıch, resp. dokud tˇeˇziˇstˇe nez˚ ust´ avaj´ı na jednom m´ıstˇe. Jednotliv´ e kroky algoritmu Kmeans 1. Vyber K bod˚ u jako poˇc´ateˇcn´ı tˇeˇziˇstˇe. 2. Opakuj (zaˇc´ atek cyklu).

10

3. Vytvoˇr K klastr˚ u pˇriˇrazen´ım kaˇzd´eho prvku nejbliˇzˇs´ımu tˇeˇziˇsti. 4. Vypoˇcti tˇeˇziˇstˇe novˇe vznikl´ ych shluk˚ u a pˇresuˇ n do nich vybran´e body. 5. Konec za podm´ınky, ˇze se tˇeˇziˇstˇe jiˇz nepohybuj´ı Obr´ azek 3 ukazuje iterace algoritmu Kmeans.

Obr´ azek 3: Pouˇzit´ı Kmeans algoritmu k nalezen´ı tˇr´ı shluk˚ u Zaˇc´ın´ a se tˇremi n´ ahodnˇe zvolen´ ymi tˇeˇziˇsti a koneˇcn´ a tˇeˇziˇstˇe jsou nalezena po ˇctyˇrech iterac´ıch. U obr´ azk˚ u zobrazuj´ıc´ıch Kmeans shlukov´ an´ı je na kaˇzd´em podobr´ azku (iteraci) uk´ az´ ano tˇeˇziˇstˇe na zaˇca ´tku iterace. Tˇeˇziˇstˇe jsou oznaˇcena pomoc´ı symbolu plus “+” a vˇsechny body v jednom shluku maj´ı stejnou znaˇcku. V prvn´ı iteraci jsou body pˇriˇrazeny k poˇca ´teˇcnˇe zvolen´ ym tˇeˇziˇst´ım, kter´e se vˇsechny nach´ az´ı ve velk´e skupinˇe bod˚ u. Jako tˇeˇziˇstˇe napˇr. pouˇzijeme pr˚ umˇer z bod˚ u v jednom shluku, a tedy aktualizujeme novou polohu tˇeˇziˇstˇe. V dalˇs´ım kroce jsou prvky pˇriˇrazeny k novˇe vypoˇcten´ ym poloh´ am tˇeˇziˇst’ a opˇet se provede aktualizace polohy tˇeˇziˇst’. V iterac´ıch 2, 3 a 4 si lze vˇsimnout, jak se dvˇe tˇeˇziˇstˇe pohybuj´ı smˇerem ke dvˇema menˇs´ım skupin´ am um´ıstˇen´ ym n´ıˇze. Pˇri ukonˇcen´ı tohoto algoritmu maj´ı vypoˇcten´ a tˇeˇziˇstˇe spr´ avnou polohu.

Pˇ riˇ razen´ı prvk˚ u k nejbliˇ zˇ s´ımu tˇ eˇ ziˇ sti Pro pˇriˇrazen´ı prvku k nejbliˇzˇs´ımu tˇeˇziˇsti potˇrebujeme definovat, jak se bude mˇeˇrit podobnost, resp. vzd´alenost, kter´ a urˇc´ı, co je to vlastnˇe nejbliˇzˇs´ı tˇeˇziˇstˇe (vzhledem ke druhu dat). M˚ uˇze existovat nˇekolik variant mˇeˇren´ı vzd´alenosti, kter´e je vhodn´e pro dan´ y typ dat. Napˇr´ıklad v dopravˇe ˇcasto pouˇz´ıvan´a metrika Manhattan, nebo velmi pouˇz´ıvan´a Eukleidovsk´ a vzd´ alenost pro datov´e prvky v Eukleidovsk´em prostoru (viz Pˇr´ıloha 5.4). Mˇeˇren´ı podobnosti pouˇzit´e pro Kmeans je obvykle relativnˇe jednoduch´e. D˚ uvody jsou dva - doch´ az´ı opakovanˇe k poˇc´ıt´an´ı podobnosti mezi kaˇzd´ ym bodem a kaˇzd´ ym tˇeˇziˇstˇem, tud´ıˇz se zde nepoˇc´ıtaj´ı podobnosti mezi prvky navz´ajem, a tak pouˇzit´ a podobnost, resp. vzd´alenost, nen´ı v´ ypoˇcetnˇe n´aroˇcn´a. Tˇ eˇ ziˇ stˇ eau ´ˇ celov´ a funkce C´ıl shlukov´an´ı je typicky vyj´adˇren u ´ˇcelovou funkc´ı, kter´ a z´ avis´ı na vz´ ajemn´ ych vzd´alenostech mezi body, nebo na tˇeˇziˇst´ıch klastr˚ u (napˇr. minimalizuj kvadr´ at vzd´alenosti kaˇzd´eho bodu ke sv´emu nejbliˇzˇs´ımu 11

tˇeˇziˇsti). Pokud m´ ame specifikovan´ y typ metriky a u ´ˇcelovou funkci, tˇeˇziˇstˇe, kter´e m´ ame na poˇc´ atku vybrat, m˚ uˇze b´ yt urˇceno matematicky. Symbol x Ci ci c mi m K

Popis Datov´ y vzorek ´I-t´ y shluk Tˇeˇziˇstˇe shluku Ci Tˇeˇziˇstˇe vˇsech bod˚ u Poˇcet prvk˚ u v ´ı-t´em shluku Poˇcet prvk˚ u v datov´e mnoˇzinˇe Poˇcet shluk˚ u

Tabulka 1: Tabulka uˇzit´ ych symbol˚ u a jejich v´ yznam˚ u

ˆ Data v Eukleidovsk´ em prostoru

Uvaˇzujme data, u nichˇz jsme zvolili Eukleidovskou metriku. Pro naˇsi u ´ˇcelovou funkci, kter´ a urˇcuje kvalitu shlukov´an´ı, pouˇzijeme kvadratick´e krit´erium. Jin´ ymi slovy vypoˇcteme chybu kaˇzd´eho datov´eho prvku, resp. jeho Eukleidovskou vzd´alenost k nejbliˇzˇs´ımu tˇeˇziˇsti, a pak udˇel´ame sumu ˇctverc˚ u chyb. Pokud jsou dod´any dvˇe r˚ uzn´e mnoˇziny shluk˚ u, kter´e jsou vyprodukov´any bˇehem dvou rozd´ıln´ ych chod˚ u Kmeans, preferujeme tu s menˇs´ı hodnotou kvadratick´eho krit´eria, protoˇze to znamen´ a, ˇze modely (tˇeˇziˇstˇe) shlukov´an´ı maj´ı lepˇs´ı reprezentaci ve sv´ ych klastrech. Kvadratick´e krit´erium je form´alnˇe zaps´ano pomoc´ı (2), kde V vyjadˇruje vzd´ alenost. K X X V (ci , x)2 (2) LS = i=1 x∈Ci

Uvˇedomme si, ˇze se pod t´ım skr´ yv´a pr˚ umˇer. Tˇeˇziˇstˇe (pr˚ umˇer) ´ı-t´eho shluku je definov´ ano v rovnici (3). 1 X ci = x (3) mi x∈Ci

Kroky 3 a 4 Kmeans algoritmu pˇresnˇe smˇeˇruj´ı k minimalizaci u ´ˇcelov´e funkce. Krok 3 tvoˇr´ı shluky oznaˇcen´ım bod˚ u ke sv´ ym nejbliˇzˇs´ım tˇeˇziˇst´ım, coˇz minimalizuje kvadratickou vzd´ alenost pro danou mnoˇzinu tˇeˇziˇst’. Krok 4 pˇrepoˇcte tˇeˇziˇstˇe tak, aby bylo moˇzn´e n´ asledovnˇe opˇet minimalizovat krit´erium. Nicm´enˇe kroky 3 a 4 pouze zaruˇcuj´ı nalezen´ı lok´aln´ıho minima, protoˇze je cel´a optimalizace zaloˇzena na poˇc´ ateˇcn´ı volbˇe tˇeˇziˇst’ a poˇctu klastr˚ u. ˆ Obecn´ y pˇ r´ıpad

12

Funkce podobnosti (vzd´ alenosti) ˇ Ctverec Eukleidovsk´e metriky(L2 )

Tˇeˇziˇstˇe

´ celov´a funkce Uˇ

pr˚ umˇer

Minimalizovat souˇcet ˇctverc˚ u L2 vzd´alenost´ı mezi prvky a jejich tˇeˇziˇsti

Tabulka 2: Vztah funkce vzd´alenosti, tˇeˇziˇstˇe a u ´ˇcelov´e funkce Jak jiˇz bylo nast´ınˇeno, existuje nˇekolik moˇznost´ı v´ ybˇeru funkce vzd´alenosti, tˇeˇziˇst’ a u ´ˇcelov´e funkce, kter´e mohou b´ yt pouˇzity v z´akladn´ım Kmeans algoritmu. Tabulka 2 ukazuje vztah mezi funkc´ı vzd´alenosti, tˇeˇziˇstˇem a u ´ˇcelovou funkc´ı. Do konce t´eto ˇc´ asti o algoritmu Kmeans budeme pouˇz´ıvat dvou-dimenzion´aln´ı data, protoˇze je na nich jednoduch´e Kmeans a jeho vlastnosti vysvˇetlit. Je vˇsak nutn´e si uvˇedomit, ˇze Kmeans je velmi obecn´ y koncept postupu shlukov´an´ı, a tak m˚ uˇze b´ yt pouˇzit pro ˇsirokou ˇsk´alu datov´ ych typ˚ u (napˇr. i pro dokumenty ˇci ˇcasov´e s´erie). Volba poˇ c´ ateˇ cn´ıch tˇ eˇ ziˇ st’ Pokud je pouˇzito n´ahodn´e poˇc´ateˇcn´ı rozm´ıstˇen´ı tˇeˇziˇst’, pak je typick´e, ˇze Kmeans pro rozd´ıln´e polohy d´a r˚ uzn´e v´ ysledky kvadratick´eho krit´eria. Situace je ilustrov´ana na obr´azku 4

Tri suboptimalni shluky (lokalni minimum kvadratickeho kriteria)

Tri optimalni shluky (globalni minimum kvadratickeho kriteria)

Obr´ azek 4: Tˇri optim´aln´ı a suboptim´aln´ı shluky M˚ uˇzeme porovnat dva v´ ysledky shlukov´e anal´ yzy, pˇriˇcemˇz na prvn´ım z nich doˇslo k nalezen´ı glob´ aln´ıho minima kvadratick´eho krit´eria pro tˇri shluky a na druh´em k pouh´emu nalezen´ı suboptima, tedy lok´ aln´ıho minima. Rozd´ıln´e v´ ysledky byly dosaˇzeny d´ıky r˚ uzn´ ym poˇca ´teˇcn´ım poloh´ am tˇeˇziˇst’.

V´ ybˇer spr´ avn´ ych poˇc´ ateˇcn´ıch poloh tˇeˇziˇst’ je kl´ıˇcov´ ym krokem z´akladn´ıho algoritmu Kmeans. Bˇeˇzn´ y postup vˇsak pˇresto pouˇz´ıv´a jejich n´ahodn´e um´ıstˇen´ı, avˇsak v´ ysledn´e klastry nemus´ı b´ yt hustˇe zaplnˇen´e. 13

ˆ Uk´ azka v´ ysledku rozd´ıln´ eho um´ıstˇ en´ı poˇ c´ ateˇ cn´ıch tˇ eˇ ziˇ st’

N´ ahodnˇe zvolen´e poˇc´ ateˇcn´ı polohy tˇeˇziˇst’ nemus´ı b´ yt hustˇe obklopen´e datov´ ymi vzorky. Dok´ aˇzeme to pˇr´ıkladem se stejnou datovou mnoˇzinou, jak´a byla pouˇzita v obr´ azku 3 a 4. Na obr´ azc´ıch 5 a 6 je zobrazen v´ ysledek, kter´eho jsme dos´ahli dvˇema r˚ uzn´ ymi p˚ uvodn´ımi polohami tˇeˇziˇst’. I kdyˇz jsou na obr´azku 5 poˇc´ateˇcn´ı tˇeˇziˇstˇe vˇsechna z jednoho pˇrirozen´eho shluku, je nalezeno glob´aln´ı minimum kvadratick´eho krit´eria. Oproti tomu na obr´azku 6, na kter´em se m˚ uˇze zd´at volba poˇc´ ateˇcn´ıch tˇeˇziˇst’ smysluplnˇejˇs´ı, dos´ahneme pouze suboptim´aln´ıho shlukov´an´ı s vˇetˇs´ı chybou kvadratick´eho krit´eria.

Pocatecni rozmisteni datovych vzorku

Iterace 1

Iterace 3

Iterace 2

Obr´ azek 5: Dva p´ ary shluk˚ u s poˇc´ateˇcnˇe zvolen´ ymi dvˇema p´ary tˇeˇziˇst’ uvnitˇr jednoho p´ aru

14

Iterace 1

Iterace 2

Iterace 4

Iterace 3

Obr´ azek 6: Dva p´ ary shluk˚ u s jinak poˇc´ateˇcnˇe zvolen´ ymi tˇeˇziˇsti ˆ Limity n´ ahodn´ e inicializace

Jednou z technik, kter´ a se bˇeˇznˇe pouˇz´ıv´a k vyˇreˇsen´ı n´ahodn´e volby poˇc´ateˇcn´ıch poloh tˇeˇziˇst’, je nechat bˇeˇzet nˇekolik Kmeans algoritm˚ u kaˇzd´ y s r˚ uznˇe zvolenou soustavou poˇc´ ateˇcn´ıch tˇeˇziˇst’ a pak vybrat tu soustavu s nejmenˇs´ı hodnotou krit´eria. Tento postup je velmi jednoduch´ y, avˇsak ne vˇzdy u ´ˇcinn´ y. Z´aleˇz´ı totiˇz na samotn´e datov´e mnoˇzinˇe a na poˇzadovan´em poˇctu shluk˚ u K. Data se skl´ adaj´ı ze dvou p´ ar˚ u shluk˚ u, kde shluky v kaˇzd´em p´aru (nahoˇre a dole) ˇ ast obr´azku 5 - iterace si jsou vz´ ajemnˇe bl´ıˇze neˇz se shluky z druh´eho p´aru. C´ 1 a 2 ukazuje, ˇze pokud zaˇcneme se dvˇema poˇc´ateˇcn´ımi tˇeˇziˇsti v jednom p´aru shluk˚ u, pak budou tˇeˇziˇstˇe i pˇresto, ˇze poˇc´ateˇcn´ı dvˇe tˇeˇziˇstˇe v jednom shluku t´emˇeˇr spl´ yvaj´ı, rozdˇelena a budou nalezeny pˇrirozen´e shluky. Na obr´azku 6 lze vidˇet, ˇze i kdyˇz m´ a jeden p´ ar shluk˚ u pouze jedno p˚ uvodn´ı tˇeˇziˇstˇe a dalˇs´ı zbyl´e tˇri, pak budou dva ze tˇr´ı pˇrirozen´ ych shluk˚ u spojeny a jeden bude rozdˇelen. Vˇsimnˇeme si, ˇze optim´ aln´ıho shlukov´an´ı dos´ahneme pr´avˇe tehdy, kdyˇz se dvˇe poˇc´ ateˇcn´ı tˇeˇziˇstˇe nach´ az´ı kdekoli v jednom p´aru shluk˚ u, protoˇze dojde k jejich n´ asledn´emu rozdˇelen´ı (kaˇzd´e tˇeˇziˇstˇe do jednoho pˇrirozen´eho shluku). Bohuˇzel je vˇsak velmi pravdˇepodobn´e, ˇze se zvyˇsuj´ıc´ım se poˇctem shluk˚ u bude m´ıt aspoˇ n jeden p´ ar shluk˚ u pouze jedno poˇc´ateˇcn´ı tˇeˇziˇstˇe. V tomto pˇr´ıpadˇe dojde k tomu, ˇze p´ ar s jedn´ım tˇeˇziˇstˇem nebude algoritmem Kmeans rozdˇelen, protoˇze datov´e vzorky v p´ aru shluk˚ u jsou si bl´ıˇze samy sobˇe navz´ajem neˇz s ostatn´ımi shluky z jin´ ych p´ ar˚ u. Z tohoto d˚ uvodu je vˇetˇsinou dosaˇzeno pouze lok´aln´ıho optima.

15

Kv˚ uli probl´em˚ um s n´ ahodnˇe zvolen´ ymi poˇc´ateˇcn´ımi tˇeˇziˇsti, kter´e mnohokr´at nelze pˇreklenout ani opakovan´ ym bˇehem, se pouˇz´ıvaj´ı jin´e techniky pro inicializaci. Jeden z efektivn´ıch pˇr´ıstup˚ u je vz´ıt datov´e vzorky a udˇelat z nich shluky za pouˇzit´ı nˇejak´e hierarchick´e shlukov´e techniky. Pak je nalezeno K klastr˚ u na urˇcit´e u ´rovni a tˇeˇziˇstˇe tˇechto shluk˚ u jsou pouˇzita jako poˇc´ateˇcn´ı tˇeˇziˇstˇe pro Kmeans. Tento postup ˇcasto pracuje velmi dobˇre, ale je praktick´ y pouze v pˇr´ıpadˇe, kdy je datov´ a mnoˇzina relativnˇe mal´a (stovky aˇz tis´ıce vzork˚ u) a kdy je ˇc´ıslo K ve srovn´ an´ı s poˇctem vzork˚ u pomˇernˇe mal´e. Dalˇs´ı procedura pro volbu poˇc´ateˇcn´ıch tˇeˇziˇst’, je n´asleduj´ıc´ı - zvol´ı se prvn´ı bod n´ ahodnˇe, nebo se vezme tˇeˇziˇstˇe vˇsech bod˚ u. Pak se vybere bod, kter´ y je nejd´ ale od tohoto jiˇz zvolen´eho tˇeˇziˇstˇe. Takto se pokraˇcuje n´avaznˇe d´ale, aˇz dostaneme poˇzadovan´ y poˇcet K poˇc´ateˇcn´ıch tˇeˇziˇst’, kter´a nejsou n´ahodnˇe rozhozena. Probl´emem tohoto pˇr´ıstupu je vˇsak to, ˇze m˚ uˇze doj´ıt k volbˇe outlieru jako poˇc´ ateˇcn´ıho tˇeˇziˇstˇe nam´ısto bodu s velkou hustotou bod˚ u. Takt´eˇz je n´aroˇcn´e vypoˇc´ıtat nejvzd´ alenˇejˇs´ı bod od mnoˇziny poˇc´ateˇcn´ıch tˇeˇziˇst’ v urˇcit´em ˇcase. Jinou moˇznost´ı je pouˇzit´ı r˚ uzn´ ych alternativ Kmeans (napˇr. p˚ ulic´ı Kmeans, viz 2.1.3), kter´e nejsou tak n´ achyln´e k p˚ uvodn´ı volbˇe tˇeˇziˇst’ nebo pouˇzit´ı urˇcit´ ych proces˚ u po shlukov´ an´ı k vylepˇsen´ı vznikl´ ych shluk˚ u. Poˇ zadavky na ˇ cas a pamˇ et’ Poˇzadavky na velikost pamˇet’ov´eho prostoru pro Kmeans jsou nen´ aroˇcn´e, protoˇze jsou zaznamen´av´any pouze datov´e body a tˇeˇziˇstˇe. Konkr´etnˇe je poˇzadovan´e uloˇzen´ı o velikosti (m + K) × n pamˇet’ov´ ych bunˇek, kde m je poˇcet bod˚ u a n je poˇcet atribut˚ u. Poˇzadavky na v´ ypoˇcetn´ı ˇcas jsou takt´eˇz nen´aroˇcn´e, protoˇze jsou line´arn´ı v˚ uˇci poˇctu datov´ ych vzork˚ u. Poˇzadovan´ y ˇcas je I × K × m × n, kde I je poˇcet iterac´ı potˇrebn´ ych ke konvergenci. Jak jiˇz bylo zm´ınˇeno, je I ˇcasto mal´e ˇc´ıslo, protoˇze se vˇetˇsina zmˇen dˇeje v prvn´ıch nˇekolika iterac´ıch. To je d˚ uvodem toho, proˇc je Kmeans line´ arn´ı v m, ˇcili v mnoˇzstv´ı bod˚ u, a proˇc je ˇc´ıslo K, tedy poˇcet vytvoˇren´ ych shluk˚ u, v´ yraznˇe menˇs´ı neˇz m. 2.1.2

Dodatky algoritmu Kmeans

Pr´ azdn´ e shluky Jeden z probl´em˚ u Kmeans algoritmu je moˇznost vytvoˇren´ı pr´ azdn´ ych shluk˚ u, jestliˇze nejsou ˇz´adn´e body pˇriˇrazeny ke klastru, resp. k tˇeˇziˇsti bˇehem pˇriˇrazov´ an´ı. Pokud se toto stane, pak je nutn´e pˇrem´ıstit tˇeˇziˇstˇe, protoˇze jinak bude chyba krit´eria vˇetˇs´ı, neˇz je nutno. Existuje nˇekolik moˇznost´ı, jak probl´em pr´azdn´ ych shluk˚ u vyˇreˇsit. Jednou z moˇznost´ı je vybrat jako poˇca´teˇcn´ı bod nejvzd´alenˇejˇs´ı bod od nˇejak´eho nynˇejˇs´ıho tˇeˇziˇstˇe. Tento krok je vhodn´ y, protoˇze z´aroveˇ n pom˚ uˇze eliminovat bod, kter´ y pr´ avˇe nejv´ıce pˇrisp´ıv´ a k celkov´e chybˇe kvadratick´eho krit´eria. Dalˇs´ım moˇzn´ ym ˇreˇsen´ım je vybrat nov´e tˇeˇziˇstˇe ze shluku, kter´ y nejv´ıce pˇrisp´ıv´a do chyby kvadratick´eho krit´eria. Toto typicky rozdˇel´ı klastr a redukuje celkovou chybu krit´eria. Pokud existuje nˇekolik pr´azdn´ ych shluk˚ u, pak m˚ uˇze b´ yt tento proces opakov´ an nˇekolikr´ at. 16

Outlier Pokud je pouˇzito kvadratick´e krit´erium, mohou outlieˇri velkou m´ırou ovlivnit shluky, kter´e byly nalezeny. Konkr´etnˇeji - pokud jsou outlieˇri pˇr´ıtomn´ı, v´ ysledn´ a tˇeˇziˇstˇe shluk˚ u (modely) nemus´ı b´ yt tak reprezentativn´ı, jak by mohla b´ yt, s ˇc´ımˇz souvis´ı i vyˇsˇs´ı hodnota kvadratick´eho krit´eria. Z tohoto d˚ uvodu je nˇekdy velmi uˇziteˇcn´e pˇredem nal´ezt outliery a eliminovat je. Je vˇsak d˚ uleˇzit´e si uvˇedomit, ˇze existuj´ı i takov´e aplikace shlukov´an´ı, ve kter´ ych by outlieˇri nemˇely b´ yt eliminov´ any. Pokud je shlukov´an´ı pouˇzito pro kompresi dat, mus´ı b´ yt souˇc´ ast´ı shlukov´ an´ı kaˇzd´ y bod. Zˇrejm´ ym probl´emem je, jak se jiˇz samo nab´ız´ı, identifikace outlier˚ u. Pokud se pouˇzij´ı postupy, kter´e odstran´ı outliery pˇred samotn´ ym shlukov´an´ım, vyhneme se t´ım bod˚ um, kter´e shlukov´an´ı zhorˇsuj´ı. Jako dalˇs´ı alternativa je identifikace outlier˚ u aˇz po procesu shlukov´an´ı. Napˇr. m˚ uˇzeme udrˇzovat z´aznam o kvadratick´em krit´eriu, resp. o pˇrispˇen´ı kaˇzd´eho bodu do celkov´e hodnoty krit´eria, a pak eliminovat ty body, jejichˇz pˇr´ıspˇevek je vyˇsˇs´ı v porovn´an´ı s ostatn´ımi body. Takt´eˇz m˚ uˇze b´ yt naˇs´ım c´ılem eliminovat shluky o mal´em poˇctu vzork˚ u, protoˇze vˇetˇsinou reprezentuj´ı pr´ avˇe skupiny outlier˚ u. Redukce hodnoty kvadratick´ eho krit´ eria v “post” procesu Zˇrejm´ ym zp˚ usobem jak redukovat kvadratick´e krit´erium je naj´ıt v´ıce shluk˚ u, resp. pouˇz´ıt vetˇs´ı K. V nˇekter´ ych pˇr´ıpadech vˇsak chceme zmenˇsit velikost krit´eria pˇri zanech´ an´ı stejn´eho poˇctu klastr˚ u, coˇz je obvykle moˇzn´e, protoˇze Kmeans konverguje vˇzdy alespoˇ n k lok´ aln´ımu minimu. Pouˇz´ıv´a se mnoho technik pro zlepˇsen´ı v´ ysledn´ ych shluk˚ u, tedy pro shlukov´an´ı s niˇzˇs´ım kvadratick´ ym krit´eriem. Strategi´ı je se zamˇeˇrit na jednotliv´e shluky, protoˇze celkov´a hodnota kvadratick´eho krit´eria je vlastnˇe souˇctem krit´eri´ı od kaˇzd´eho shluku. M˚ uˇzeme zmˇenit celkovou hodnotu krit´eria proveden´ım nˇekolika operac´ı na klastrech. Velmi bˇeˇzn´ ym postupem je pouˇz´ıt dvˇe f´aze, a to f´azi rozdˇelov´an´ı a f´azi spojov´ an´ı. T´ımto zp˚ usobem se vyhneme lok´aln´ımu minimu kvadratick´eho krit´eria a nalezneme ˇreˇsen´ı shlukov´ an´ı s poˇzadovan´ ym poˇctem shluk˚ u. Zde jsou zm´ınˇen´e pˇr´ıklady technik, kter´e se pouˇz´ıvaj´ı pro tyto zm´ınˇen´e f´aze. Strategie, kter´e sniˇzuj´ı celkovou hodnotu kvadratick´eho krit´eria za souˇcasn´eho zv´ yˇsen´ı poˇctu shluk˚ u: ˆ Rozdˇ elen´ı klastru - pro rozdˇelen´ı je vybr´an shluk s nejvˇetˇs´ım kvadratick´ ym krit´eriem, ale takt´eˇz m˚ uˇze b´ yt rozdˇelen shluk s nejvˇetˇs´ı smˇerodatnou odchylkou pro jeden konkr´etn´ı atribut. ˆ Pˇ rid´ an´ı nov´ eho tˇ eˇ ziˇ stˇ e, resp. nov´ eho shluku - pro tuto strategii je vybr´ an bod, kter´ y je nejd´ale od libovoln´eho centra shluku. Tento bod jsme schopni jednoduˇse naj´ıt, pokud si nech´av´ame z´aznam o pˇrispˇen´ı k celkov´e hodnotˇe kvadratick´eho krit´eria od kaˇzd´eho bodu. Jinou moˇznost´ı je vybrat n´ ahodnˇe ze vˇsech bod˚ u nebo z bod˚ u s nejvyˇsˇs´ım kvadratick´ ym krit´eriem.

Strategie, kter´e sniˇzuj´ı poˇcet shluk˚ u, pˇriˇcemˇz se z´aroveˇ n snaˇz´ı minimalizovat n´ ar˚ ust celkov´eho kvadratick´eho krit´eria :

17

ˆ Odstranˇ en´ı shluku - pro odstranˇen´ı shluku se nejprve odstran´ı samotn´e tˇeˇziˇstˇe vybran´eho klastru a body, kter´e z odstranˇen´eho shluku zbyly, se pˇreˇrad´ı jin´ ym klastr˚ um. Ide´alnˇe by mˇel b´ yt odstranˇen´ ym shlukem ten, kter´ y zvyˇsuje nejm´enˇe celkov´e kvadratick´e krit´erium. ˆ Spojen´ı dvou shluk˚ u - pro spojen´ı jsou typicky vybr´any shluky, jejichˇz tˇeˇziˇstˇe jsou si nejbl´ıˇze, nebo ty shluky, kter´e nejm´enˇe pˇrisp´ıvaj´ı k n´ar˚ ustu celkov´eho krit´eria. Tato strategie spojen´ı je tat´aˇz, kter´a se pouˇz´ıv´a v technik´ ach hierarchick´eho shlukov´an´ı (zn´am´a jako tˇeˇziˇst’ov´a metoda).

Aktualizace tˇ eˇ ziˇ st’ po kroc´ıch Nam´ısto aktualizace tˇeˇziˇst’ shluk˚ u po tom, co byly pˇriˇrazeny vˇsechny body ke shluk˚ um, mohou b´ yt tˇeˇziˇstˇe aktualizov´ana v jednotliv´ ych kroc´ıch shlukov´ an´ı - po pˇriˇrazen´ı kaˇzd´eho bodu ke shluku. Vˇsimnˇeme si, ˇze toto vyˇzaduje bud’ ˇz´ adnou nebo dvˇe aktualizace tˇeˇziˇst’ v kaˇzd´em kroce, protoˇze se bod bud’ pˇresune k nov´emu klastru (dvˇe aktualizace), nebo z˚ ustane v souˇcasn´em shluku (ˇz´ adn´ a aktualizace). Tento postup zaruˇcuje, ˇze nejsou vytv´aˇreny pr´ azdn´e klastry, protoˇze zaˇc´ınaj´ı vˇsechny shluky s jedn´ım bodem a jestli m´a m´ıt nˇejak´ y shluk pouze jeden bod, bude tento bod pokaˇzd´e pˇriˇrazen tomu sam´emu shluku. Nev´ yhodou t´eto aktualizace je z´avislost na volbˇe poˇrad´ı. Jinak ˇreˇceno - vznikl´e shluky m˚ uˇzou z´ aviset na poˇrad´ı, v jak´em byly pˇriˇrazov´any jednotliv´e body. I kdyˇz to m˚ uˇze b´ yt vyˇreˇseno n´ahodn´ ym poˇrad´ım, v jak´em jsou body pˇriˇrazov´any, z´ akladn´ı pˇr´ıstup aktualizace tˇeˇziˇst’ (po pˇriˇrazen´ı vˇsech bod˚ u) nez´avis´ı na ˇz´adn´em poˇrad´ı. Aktualizace po jednotliv´ ych kroc´ıch je n´aroˇcnˇejˇs´ı. Nicm´enˇe Kmeans konverguje pomˇernˇe rychle, takˇze mnoˇzstv´ı bod˚ u mˇen´ıc´ıch shluky se relativnˇe rychle zmenˇsuje. 2.1.3

P˚ ulic´ı Kmeans

P˚ ulic´ı Kmeans algoritmus je pouh´ ym rozˇs´ıˇren´ım z´akladn´ıho Kmeans. Vˇse je zaloˇzeno na z´ akladn´ı myˇslence - k z´ısk´an´ı K klastr˚ u se rozdˇeluje p˚ uvodn´ı mnoˇzina vˇsech vzork˚ u do dvou shluk˚ u, vybere se jeden z tˇechto novˇe vznikl´ ych shluk˚ u, kter´ y se opˇet rozdˇel´ı na dva podshluky. Tento postup se opakuje, aˇz se dos´ahne K klastr˚ u. Jednotliv´ e kroky p˚ ulic´ıho algoritmu Kmeans 1. Vytvoˇr seznam shluk˚ u. Na zaˇc´atku obsahuje jeden shluk vˇsechny vzorky. Pot´e doch´ az´ı v kaˇzd´em cyklu k aktualizaci. 2. Opakuj (poˇc´ atek cyklu). 3. Vyber a odstraˇ n jeden shluk ze seznamu. 4. Proved’ zadan´ y poˇcet (externˇe stanoven´ y) p˚ ulen´ı vybran´eho nerozeznan´eho shluku za pouˇzit´ı z´ akladn´ıho Kmeans. 18

5. Vyber dva shluky s nejniˇzˇs´ı hodnotou kvadratick´eho krit´eria. 6. Pˇridej tyto dva shluky do seznamu shluk˚ u. 7. Konec za podm´ınky, ˇze seznam shluk˚ u obsahuje K shluk˚ u. Existuje nˇekolik moˇznost´ı, jak vybrat shluk, kter´ y m´a b´ yt rozp˚ ulen. M˚ uˇze se vybrat shluk nejrozs´ ahlejˇs´ı, s nejvyˇsˇs´ım kvadratick´ ym krit´eriem, nebo kombinace obou tˇechto podm´ınek. Samozˇrejmost´ı je, ˇze r˚ uzn´e volby vy´ ust´ı v r˚ uzn´e klastry. ˇ Casto pouˇzijeme tˇeˇziˇstˇe v´ ysledn´ ych shluk˚ u p˚ ulic´ıho Kmeans algoritmu jako poˇc´ ateˇcn´ı tˇeˇziˇstˇe pro z´ akladn´ı algoritmus Kmeans. I kdyˇz Kmeans zaruˇcuje nalezen´ı shlukov´ an´ı reprezentuj´ıc´ı alespoˇ n lok´aln´ı minimum s ohledem na kvadratick´e krit´erium, v p˚ ulic´ım Kmeans se pouˇz´ıv´a Kmeans lok´alnˇe, tj. k rozp˚ ulen´ı jednotliv´ ych shluk˚ u, proto v´ ysledek nereprezentuje kompletn´ı koneˇcnou mnoˇzinu shlukov´ an´ı. Pˇ r´ıklad p˚ ulic´ıho Kmeans a inicializace V´ yhodou p˚ ulic´ıho Kmeans je zejm´ena jeho mal´ a citlivost v˚ uˇci poˇc´ateˇcn´ımu nastaven´ı. K ilustraci tohoto tvrzen´ı si ukaˇzme na obr´ azku 7, jak p˚ ulic´ı Kmeans nalezne ˇctyˇri shluky v datov´e mnoˇzinˇe z obr´ azku 5.

Iterace 1

Iterace 2

Iterace 3

Obr´ azek 7: P˚ ulic´ı Kmeans na pˇr´ıkladu se ˇctyˇrmi shluky V prvn´ı iteraci jsou nalezeny dva shluky, ve druh´e je rozdˇelen shluk napravo a ve tˇret´ı nalevo. p˚ ulic´ı Kmeans m´a m´enˇe probl´em˚ u s inicializac´ı, protoˇze prov´ ad´ı nˇekolik zkuˇsebn´ıch p˚ ulen´ı a vybere tu s nejmenˇs´ı hodnotou kvadratick´eho krit´eria.

2.1.4

Kmeans a r˚ uzn´ e typy shluk˚ u

Kmeans a jeho varianty maj´ı nˇekolik omezen´ı zejm´ena t´ ykaj´ıc´ıch se nalezen´ı r˚ uzn´ ych druh˚ u klastr˚ u. Obzvl´aˇstˇe m´a Kmeans probl´em detekovat “pˇrirozen´e” shluky, kdyˇz maj´ı nekulov´ y tvar, rozd´ıln´e velikosti nebo r˚ uzn´e hustoty. N´azorn´a uk´ azka je na obr´ azku 8. Na prvn´ım podobr´ azku nem˚ uˇze Kmeans nal´ezt tˇri pˇrirozen´e shluky, protoˇze je jeden z nich mnohokr´ at vˇetˇs´ı neˇz dalˇs´ı dva. Z toho d˚ uvodu je vˇetˇs´ı z nich rozdˇelen na dva a jsou k nˇemu pˇridˇeleny vzorky z jednoho menˇs´ıho. Na druh´e ˇc´ asti lze vidˇet, ˇze Kmeans nedok´aˇze naj´ıt tˇri pˇrirozen´e shluky, protoˇze dva menˇs´ı 19

Puvodni datove vzorky

Shluky vytvorene K−means algoritmem

Shluky ruzne velikosti

Shluky ruzne hustoty

Shluky nekulovitého tvaru

Obr´ azek 8: R˚ uzn´e typy shluk˚ u a Kmeans maj´ı vyˇsˇs´ı hustotu neˇz zbyl´e vˇetˇs´ı. Na posledn´ı uk´azce nalezl Kmeans dva shluky, kter´e obsahuj´ı vzorky z obou shluk˚ u pˇrirozen´ ych. Ty totiˇz nejsou kulov´eho tvaru. Obt´ıˇznosti v tˇechto tˇrech situac´ıch vznikaj´ı, protoˇze u ´ˇcelov´a funkce Kmeans tvoˇr´ı neshody pro typy shluk˚ u, kter´e jsme se snaˇzili naj´ıt, protoˇze je minimalizov´ana kulovit´ ymi shluky stejn´ ych velikost´ı a stejn´e hustoty, nebo shluky, kter´e jsou ostˇre rozdˇelen´e. Nicm´enˇe tato omezen´ı mohou b´ yt sv´ ym zp˚ usobem pˇrekon´ana, pokud je uˇzivatel ochotn´ y pˇrijmout shlukov´an´ı, jehoˇz v´ ysledkem jsou pˇrirozen´e shluky, avˇsak rozdˇelen´e na nˇekolik podshluk˚ u. Obr´azek 9 ukazuje, co se stane, pokud zv´ yˇs´ıme ˇc´ıslo K = 6 nam´ısto p˚ uvodn´ıch 2 a 3. Kaˇzd´ y menˇs´ı shluk je u ´pln´ y v tom smyslu, ˇze obsahuje pouze body z jednoho pˇrirozen´eho shluku. 2.1.5

Siln´ e a slab´ e str´ anky

Kmeans je velmi jednoduch´ y algoritmus, kter´ y m˚ uˇze b´ yt pouˇzit pro ˇsirokou ˇsk´ alu datov´ ych typ˚ u. Je i pomˇernˇe u ´ˇcinn´ y, i kdyˇz se ˇcasto mus´ı prov´adˇet opakovanˇe. Nˇekter´e varianty (zde zm´ınˇen´eho p˚ ulic´ıho) Kmeans jsou dokonce jeˇstˇe u ´ˇcinnˇejˇs´ı a m´enˇe citliv´e v˚ uˇci poˇc´ateˇcn´ımu nastaven´ı neˇz z´akladn´ı. Kmeans nen´ı 20

Ruzne velikosti

Ruzne hustoty

Nekulovite tvary

Obr´ azek 9: Nalezen´ı pˇrirozen´ ych shluk˚ u skl´adaj´ıc´ıch se ze subshluk˚ u vhodn´ y pro vytvoˇren´ı r˚ uzn´ ych typ˚ u shluk˚ u. Neum´ı udˇelat nekulovit´e shluky nebo shluky r˚ uzn´ ych velikost´ı a hustot, aˇckoli m˚ uˇze nal´ezt podshluky tvoˇr´ıc´ı pˇrirozen´e shluky, kdyˇz je povoleno vˇetˇs´ı K. Kmeans m´ a takt´eˇz probl´emy s daty obsahuj´ıc´ımi outliery, ty vˇsak mohou b´ yt rozpozn´ any a vymaz´ any, coˇz v´ yraznˇe zlepˇs´ı kvalitu shlukov´an´ı pomoc´ı Kmeans. Nakonec je nutn´e zm´ınit, ˇze Kmeans je specifick´ y pro data, kter´a mohou vytv´ aˇret shluky pomoc´ı tˇeˇziˇst’.

2.2

Hierarchick´ e shlukov´ an´ı

Hierarchick´e shlukov´e techniky jsou dalˇs´ı d˚ uleˇzitou kategori´ı ve shlukov´an´ı. Tak jako Kmeans patˇr´ı k pomˇernˇe star´ ym technik´am, kter´a vˇsak nach´az´ı ˇsirok´e uplatnˇen´ı i na poli dneˇsn´ıch aplikac´ı. Rozliˇsujeme dva pˇr´ıstupy - aglomerativn´ı

21

a divizivn´ı (viz Pˇr´ıloha 5.5). Aglomerativn´ı pˇr´ıstupy jsou jedny z nejbˇeˇznˇejˇs´ıch, a tak o nich bude pojedn´ ano bl´ıˇze. Hierarchick´e shlukov´ an´ı je ˇcasto zobrazov´ano pomoc´ı grafu - stromu, kter´ y se v tomto pˇr´ıpadˇe naz´ yv´ a dendrogram. Ten zobrazuje vztahy shluk - subshluk a zachycuje poˇrad´ı, v jak´em byly shluky vytvoˇreny. Pro mnoˇziny z dvoudimenzion´ aln´ıho prostoru m˚ uˇze b´ yt hierarchick´e shlukov´an´ı reprezentov´ano za pouˇzit´ı diagramu vkl´ adan´ ych shluk˚ u. Obr´azek 10 ukazuje tyto dva typy zobrazen´ı pro ˇctyˇri mnoˇziny bod˚ u (shluky byly vytvoˇreny za pouˇzit´ı metody nejbliˇzˇs´ıho souseda).

Dendrogram

Diagram vkladanych shluku

Obr´ azek 10: R˚ uzn´e zobrazen´ı hierarchick´eho shlukov´an´ı

2.2.1

Z´ akladn´ı aglomerativn´ı hierarchick´ y algoritmus

Existuje nˇekolik metod, jak tvoˇrit shluky, resp. jak pˇristupovat k jednotliv´ ym prvk˚ um shluk˚ u. Bl´ıˇze bude pojedn´ano o metodˇe nejbliˇzˇs´ıho, nejvzd´alenˇejˇs´ıho souseda a o centroidn´ı metodˇe. Postup vˇsech metod m´ a stejnou z´akladn´ı myˇslenku. Na zaˇc´atku se vezme kaˇzd´ y vzorek jako jednotliv´ y shluk a n´aslednˇe se vytvoˇr´ı seznam vzd´alenost´ı mezi shluky pro vˇsechny r˚ uzn´e neuspoˇr´adan´e dvojice. N´aslednˇe se seˇrad´ı tyto vzd´alenosti vzestupnˇe. Dojde k vytvoˇren´ı grafu, ve kter´em jsou vytvoˇreny dle r˚ uzn´ ych metod uzly z dvojic vzork˚ u (viz Definov´an´ı sousedstv´ı mezi shluky). Jestliˇze jsou vˇsechny vzorky ˇcleny jednoho shluku, pak je konec, jinak se neust´ale tento krok opakuje. V´ ysledkem algoritmu je s´ıt’ov´a hierarchie, kter´a m˚ uˇze b´ yt rozˇclenˇena na poˇzadovan´e u ´rovni nepodobnosti (vzd´alenosti), na kter´e se nach´az´ı urˇcit´ y poˇcet shluk˚ u. ˆ Algoritmus pro metodu nejbliˇ zˇ s´ıho souseda

1. Vytvoˇr seznam vzd´ alenost´ı pro vˇsechny neuspoˇr´adan´e dvojice shluk˚ u. 2. Seˇrad’ vzestupnˇe vzd´ alenosti.

22

3. Opakuj (zaˇc´ atek cyklu). 4. Sluˇc dva shluky (dle vybran´e metody). 5. Aktualizuj seznam vzd´alenost´ı s nov´ ym shlukem. 6. Konec za podm´ınky, ˇze zb´ yv´a pouze jeden shluk. Ukaˇzme si n´ azornˇe rozd´ıln´ y v´ ysledek za pouˇzit´ı metody nejbliˇzˇs´ıho a nejvzd´alenˇejˇs´ıho souseda. Na obr´ azku 11 jsou dva shluky rozdˇelen´e mostem ze ˇsumu.

Metoda nejvzdalenejsiho souseda

Metoda nejblizsiho souseda

Obr´ azek 11: Uk´ azka rozd´ılu pouˇzit´ı metody nejbliˇzˇs´ıho a nejvzd´alenˇejˇs´ıho souseda Klastry vytvoˇren´e metodou nejbliˇzˇs´ıho souseda (lev´ a ˇca ´st obr´ azku) jsou v´ıce kompaktn´ı (ucelen´e) neˇz ty poˇr´ızen´e metodou nejvzd´ alenˇejˇs´ıho souseda (prav´ a ˇca ´st). Vˇetˇs´ı shluk je v druh´em pˇr´ıpadˇe podlouhl´ y kv˚ uli ˇretˇezci ˇsumov´ ych vzork˚ u oznaˇcen´ ych *, coˇz je d˚ ukazem toho, ˇze metoda nejbliˇzˇs´ıho souseda je pˇrizp˚ usobivˇejˇs´ı a promˇenlivˇejˇs´ı v˚ uˇci dat˚ um neˇz metoda nejvzd´ alenˇejˇs´ıho souseda. Nicm´enˇe se uk´ azalo, ˇze z pragmatick´eho hlediska pˇrin´ aˇs´ı metoda nejvzd´ alenˇejˇs´ıho souseda uˇziteˇcnˇejˇs´ı hierarchie v mnoha aplikac´ıch neˇz metoda nejbliˇzˇs´ıho souseda.

Definov´ an´ı sousedstv´ı mezi shluky Kl´ıˇcovou z´aleˇzitost´ı je v´ ypoˇcet bl´ızkosti mezi dvˇema shluky (resp. urˇcen´ı vz´ajemn´eho sousedstv´ı dvou shluk˚ u), coˇz lze prov´ezt nˇekolika zp˚ usoby. Bl´ızkost shluk˚ u je typicky definovan´a spolu s urˇcit´ ym typem klastr˚ u. Mnoho, jiˇz zm´ınˇen´ ych, aglomerativn´ıch metod jako MIN, MAX ˇci pr˚ umˇer skupiny poch´ az´ı ze shluk˚ u zaloˇzen´ ych na grafech (viz Pˇr´ıloha 5.3) . ˆ MIN definuje sousedstv´ı shluk˚ u jako vzd´alenost mezi dvˇema nejbliˇzˇs´ımi vzorky z r˚ uzn´ ych shluk˚ u (v terminologii graf˚ u hovoˇr´ıme o nejkratˇs´ı hranˇe mezi dvˇema uzly v r˚ uzn´ ych podmnoˇzin´ach uzl˚ u). Touto metodou m˚ uˇzeme vytvoˇrit souvisl´e shluky. ˆ Alternativou je metoda MAX, kter´ a bere jako sousedstv´ı dvou shluk˚ u vzd´ alenost mezi dvˇema nejvzd´alenˇejˇs´ımi vzorky v r˚ uzn´ ych klastrech (nejdelˇs´ı hrana mezi dvˇema uzly v r˚ uzn´ ych podmnoˇzin´ach uzl˚ u).

23

Metoda nejblizsiho souseda (MIN)

Metoda nejvzdalenejsiho souseda (MAX)

Prumer skupiny

Obr´ azek 12: Techniky urˇcen´ı sousedstv´ı ˆ Posledn´ım pˇr´ıstupem k tomuto probl´emu je pr˚ umˇ er cel´e skupiny, coˇz znamen´ a, ˇze se jako sousedstv´ı dvou rozd´ıln´ ych shluk˚ u bere pr˚ umˇer ze vˇsech vzork˚ u v jednotliv´em shluku.

Na obr´ azku 12 jsou tyto tˇri pˇr´ıpady ilustrov´any. Dalˇs´ı moˇznosti definice vzd´alenost´ı existuj´ı pro shluky reprezentovan´e sv´ ym tˇeˇziˇstˇem. Zde je sousedstv´ı bˇeˇznˇe definov´ano jako vzd´alenost mezi jejich tˇeˇziˇsti. Alternativn´ı technika - Wardova metoda mˇeˇr´ı sousedstv´ı mezi dvˇema shluky v r´ amci n´ ar˚ ustu kvadratick´eho krit´eria, kter´ y je v´ ysledkem spojen´ı dvou shluk˚ u. Jako Kmeans se snaˇz´ı Wardova metoda minimalizovat sumu kvadratick´ ych vzd´alenost´ı vzork˚ u a jejich tˇeˇziˇst’. Poˇ zadavky na ˇ cas a pamˇ et’ V´ yˇse zm´ınˇen´e aglomerativn´ı pˇr´ıstupy pouˇz´ıvaj´ı matici sousednosti, coˇz vyˇzaduje uloˇzen´ı 21 m2 vzd´alenost´ı (pokud se tedy pˇredpokl´ad´a, ˇze je matice sousednosti symetrick´a), kde m je poˇcet datov´ ych vzork˚ u. Pamˇet’ potˇrebn´ a pro sledov´ an´ı tvorby shluk˚ u je u ´mˇern´a poˇctu shluk˚ u, coˇz je m − 1 vyjma shluk˚ u s jedn´ım prvkem. Proto jsou poˇzadavky na pamˇet’ m2 . Anal´ yzu z´ akladn´ıch aglomerativn´ıch algoritm˚ u mus´ıme uvaˇzovat i vzhledem k v´ ypoˇcetn´ı n´ aroˇcnosti. K v´ ypoˇctu matice sousednosti je poˇzadov´ano m2 ˇcasov´ ych jednotek. Po tomto kroce je m − 1 iterac´ı, kter´e zahrnuj´ı pouze kroky 3 a 4, protoˇze je na zaˇc´ atku m klastr˚ u a bˇehem kaˇzd´e iterace jsou spojeny dva shluky. Pokud je provedeno line´ arn´ı prohled´av´an´ı matice sousednosti, pak pro ´ı-tou iteraci poˇzaduje krok 3 (m − i + 1)2 ˇcasov´ ych jednotek. Krok 4 vyˇzaduje jiˇz pouze m − i + 1 ˇcasov´ ych jednotek k aktualizaci matice sousednosti po slouˇcen´ı ˇ dvou shluk˚ u. Casov´ a n´ aroˇcnost takov´eto u ´lohy by tedy zabrala m3 ˇcasov´ ych jednotek. Pokud jsou vzd´ alenosti od kaˇzd´eho shluku ke vˇsem ostatn´ım ukl´ad´any jako uspoˇr´ adan´ y seznam, je moˇzn´e redukovat u ´sil´ı k nalezen´ı dvou nejbliˇzˇs´ıch shluk˚ u na m − i + 1 ˇcasov´ ych jednotek. Nicm´enˇe kv˚ uli obt´ıˇznostem s udrˇzen´ım dat ve srovnan´em seznamu je celkov´ y ˇcas potˇrebn´ y pro v´ yˇse zm´ınˇen´ y algoritmus 24

m2 × log (m) jednotek. ˇ Casov´ e a pamˇet’ov´e poˇzadavky pro hierarchick´e shlukov´an´ı striktnˇe omezuje velikost datov´e mnoˇziny, se kterou m´a b´ yt pracov´ano. 2.2.2

Uk´ azka metod na pˇ r´ıkladˇ e

Vzorek dat Pro lepˇs´ı pˇredstaven´ı chov´an´ı r˚ uzn´ ych hierarchick´ ych algoritm˚ u pouˇzijeme vzorek dat, kter´ y se skl´ad´a z 6 dvou-dimenzion´aln´ıch bod˚ u, kter´e jsou uk´ az´ any na obr´ azku 13. Souˇradnice x a y a Eukleidovsk´e vzd´alenosti mezi body jsou zaznamen´ any v tabulk´ ach 3 a 4.

Obr´ azek 13: Mnoˇzina 6 datov´ ych vzork˚ u

Bod 1 2 3 4 5 6

Souˇradnice x 0.40 0.22 0.35 0.26 0.08 0.45

Souˇradnice y 0.53 0.38 0.32 0.19 0.41 0.30

Tabulka 3: Souˇradnice datov´ ych vzork˚ u

Metoda nejbliˇ zˇ s´ıho souseda (MIN) Pro metodu nejbliˇzˇs´ıho souseda, resp. pro MIN verzi hierarchick´eho shlukov´an´ı je sousedstv´ı dvou shluk˚ u definov´ano jako minim´ aln´ı vzd´ alenost, resp. maxim´aln´ı podobnost, mezi dvˇema body ve dvou r˚ uzn´ ych shluc´ıch. Pokud tedy zaˇcneme se vˇsemi body jako se shluky o jednom prvku a vytvoˇr´ıme spojen´ı mezi body (uzly) poˇc´ınaje spojen´ım o nejmenˇs´ı velikosti, pak se tato spojen´ı (hrany) prot´ınaj´ı v uzlech, kter´e jsou reprezentac´ı shluk˚ u. Tato technika je vhodn´a pro neeliptick´e tvary. Je vˇsak velmi citliv´a v˚ uˇci ˇsumu a outlier˚ um. 25

body 1 2 3 4 5 6

1 0.00 0.24 0.22 0.37 0.34 0.23

2 0.24 0.00 0.15 0.20 0.14 0.25

3 0.22 0.15 0.00 0.15 0.28 0.11

4 0.37 0.20 0.15 0.00 0.29 0.22

5 0.34 0.14 0.28 0.29 0.00 0.39

6 0.23 0.25 0.11 0.22 0.39 0.00

Tabulka 4: Matice vzd´alenost´ı (Eukleidovsk´e) ˆ Pˇ r´ıklad pouˇ zit´ı metody nejbliˇ zˇ s´ıho souseda

Obr´ azek 14 ukazuje v´ ysledek pouˇzit´ı metody nejbliˇzˇs´ıho souseda na naˇsem vzorku dat.

Dendrogram

Metoda nejblizsiho souseda pomoci vkladani

Obr´ azek 14: Uk´ azka metody nejbliˇzˇs´ıho souseda (resp. MIN) Na lev´e ˇca ´sti obr´ azku jsou k vidˇen´ı vloˇzen´e shluky jako posloupnost vloˇzen´ ych elips, kde ˇc´ısla u elips zn´ azorˇ nuj´ı ˇr´ ad shlukov´ an´ı. Prav´ a ˇca ´st zobrazuje tu samou situaci, ale ve formˇe dendrogramu. V´ yˇsku, ve kter´e jsou slouˇceny dva shluky v dendrogramu, znamen´ a vzd´ alenost mezi dvˇema shluky.

Z tabulky 4 vid´ıme, ˇze vzd´ alenost mezi body 3 a 6 je 0.11, coˇz je vlastnˇe v´ yˇska, ve kter´e jsou tyto dva body spojeny do jednoho shluku v dendrogramu. Jako dalˇs´ı pˇr´ıklad uved’me vzd´ alenost (oznaˇcovanou jako V ) mezi shluky {3,6} a {2,5} : V ({3, 6}, {2, 5})

= min V [(3, 2), (6, 2), (3, 5), (6, 5)] = min(0.15, 0.25, 0.28, 0.39) =

0.15

26

Metoda nejvzd´ alenˇ ejˇ s´ıho souseda (MAX) Pro metodu nejvzd´alenˇejˇs´ıho souseda, resp. pro MAX verzi hierarchick´eho shlukov´an´ı je sousedstv´ı dvou shluk˚ u definov´ ano jako maxim´aln´ı vzd´alenost, resp. minim´aln´ı podobnost, mezi dvˇema body ve dvou r˚ uzn´ ych shluc´ıch. I v tomto pˇr´ıpadˇe se vytv´aˇr´ı spojen´ı (hrany) mezi body (uzly). Zaˇc´ın´a se jako v pˇredchoz´ım pˇr´ıpadˇe nejkratˇs´ım spojen´ım. D´ ale se pak opˇet sluˇcuj´ı shluky, kter´e maj´ı k sobˇe nejbl´ıˇze (podm´ınka hierarchick´eho shlukov´ an´ı). Neporovn´avaj´ı se vˇsak vzd´alenosti nejbliˇzˇs´ıch prvk˚ u ve shluku, n´ ybrˇz nejvzd´ alenˇejˇs´ıch. Tato metoda je m´enˇe n´achyln´a v˚ uˇci ˇsumu a outlier˚ um, ale m˚ uˇze rozb´ıt velk´e shluky a z´aroveˇ n favorizuje kulovit´e tvary shluk˚ u. ˆ Pˇ r´ıklad pouˇ zit´ı metody nejvzd´ alenˇ ejˇ s´ıho souseda

Obr´ azek 15 ukazuje v´ ysledek pouˇzit´ı MAX varianty shlukov´an´ı na naˇsem vzorku dat z 6 bod˚ u. Tak jako v pˇr´ıpadˇe nejbliˇzˇs´ıho souseda jsou body 3 a 6 slouˇceny jako prvn´ı, pak body 2 a 5. D´ale je vˇsak shlukov´an´ı rozd´ıln´e - body 3 a 6 jsou slouˇceny se 4 nam´ısto s 2 a 5 nebo 1, protoˇze shluk {3, 6} je bl´ıˇze shluku 4. D˚ uvodem je uvaˇzov´ an´ı nejvzd´alenˇejˇs´ıch prvk˚ u ve shluku do v´ ypoˇctu vzd´alenosti. V ({3, 6}, {4})

= max V [(3, 4), (6, 4)] = max(0.15, 0.22) =

V ({3, 6}, {2, 5})

0.22

= max V [(3, 2), (6, 2), (3, 5), (6, 5)] = max(0.15, 0.25, 0.28, 0.39) =

V ({3, 6}, {1})

0.39

= max V [(3, 1), (6, 1)] = max(0.22, 0.23) =

0.23

Pr˚ umˇ er skupiny Posledn´ı varianta je vz´ıt jako hlavn´ı krit´erium pro sousedstv´ı dvou shluk˚ u pr˚ umˇer vzd´alenost´ı mezi vˇsemi p´ary vzork˚ u v jednotliv´ ych shluc´ıch. Toto je jak´ ysi kompromis mezi metodami nejbliˇzˇs´ıho a nejvzd´alenˇejˇs´ıho souseda. Pro pr˚ umˇer skupiny je vyj´adˇreno sousedstv´ı dvou shluk˚ u (Ci , Cj ), kter´e maj´ı velikosti mi , resp. mj n´asledovnˇe: P V (x, y) , kde ˇcitatel je sumou vzd´alenost´ı mezi prvky mezi shluky. p(Ci , Cj ) = mi mj (4) ˆ Pˇ r´ıklad pouˇ zit´ı pr˚ umˇ eru skupiny

Obr´ azek 16 ukazuje v´ ysledek pouˇzit´ı pr˚ umˇeru skupiny na naˇsem vzorku dat z 6 bod˚ u. Pro ilustraci fungov´an´ı skupinov´eho pr˚ umˇeru, vypoˇcteme vzd´alenosti 27

Dendrogram

Metoda nejvzdalenejsiho souseda pomoci vkladani

Obr´ azek 15: Uk´ azka metody nejvzd´alenˇejˇs´ıho souseda (resp. MAX) mezi nˇejak´ ymi shluky. V ({3, 6, 4}, {1}) V ({2, 5}, {1})

=

(0.22 + 0.37 + 0.23)/(3 ∗ 1)

=

0.28

=

(0.2357 + 0.3421)/(2 ∗ 1)

= 0.2889 V ({3, 6, 4}, {2, 5}) = (0.15 + 0.28 + 0.25 + 0.39 + 0.20 + 0.29)/(6 ∗ 2) =

0.26

Protoˇze je V ({3, 6, 4}, {2, 5}) menˇs´ı neˇz V ({3, 6, 4}, {1}) a V ({2, 5}, {1}), jsou shluky {3, 6, 4} a {2, 5} slouˇceny na ˇctvrt´em stupni hierarchie. Wardova metoda a tˇ eˇ ziˇ st’ov´ a metoda Ve Wardovˇe metodˇe se sousedstv´ı mezi dvˇema shluky definuje pr´avˇe tehdy, kdyˇz vzroste hodnota kvadratick´eho krit´eria, kter´ a vznikne spojen´ım dvou shluk˚ u. Tato metoda pouˇz´ıv´a stejnou u ´ˇcelovou funkci jako algoritmus Kmeans. M˚ uˇze se zd´at, ˇze tato metoda je sv´ ym zp˚ usobem rozd´ıln´ a od jin´ ych hierarchick´ ych technik, ale lze matematicky dok´ azat, ˇze je velmi podobn´a s pˇredchoz´ı metodou pr˚ umˇeru skupiny. Tˇeˇziˇst’ov´ a metoda urˇcuje sousedstv´ı mezi dvˇema shluky vypoˇcten´ım vzd´alenosti mezi tˇeˇziˇsti shluk˚ u. Opˇet se jev´ı jako velmi podobn´a algoritmu Kmeans. ’ Metoda tˇeˇziˇst m´ a vlastnost, kter´a je vˇetˇsinou povaˇzov´ana jako negativum a kterou nelze naj´ıt v jin´ ych hierarchick´ ych postupech, a to moˇznost inverze. Konkr´etnˇeji - shluk 1 si m˚ uˇze b´ yt bl´ıˇze shluku 2, kter´ y je vˇsak jiˇz souˇc´ast´ı jin´eho shluku (vytvoˇren´eho v pˇredchoz´ım kroce se shlukem 3), a tak je jiˇz souˇc´ast´ı pˇrepoˇctu tˇeˇziˇstˇe nov´eho shluku (tvoˇren´eho ze shluk˚ u 2 a 3). Pro dalˇs´ı metody

28

Shlukovani za pomoci prumeru skupiny a vkladani

Dendrogram

Obr´ azek 16: Uk´azka pouˇzit´ı pr˚ umˇeru skupiny se vzd´ alenost mezi slouˇcen´ ymi shluky zvˇetˇsuje, protoˇze postupujeme od shluku o jednom prvku k jednomu shluku obsahuj´ıc´ı vˇsechny prvky. 2.2.3

Lanc˚ uv-Williams˚ uv vztah pro sousedstv´ı (L-W vztah)

Na mnoh´e ze zm´ınˇen´ ych v´ ypoˇct˚ u sousednosti m˚ uˇzeme nahl´ıˇzet jako na L-W vztah (5) s r˚ uzn´ ymi parametry.

p(R, Q) = αA p(A, Q) + αB p(B, Q) + βp(A, B) + γ|p(A, Q) − p(B, Q)|

(5)

Shluky A a B - sluˇcovan´e shluky. Shluk R - vytvoˇren slouˇcen´ım shluk˚ u A a B. Shluk Q - novˇe uvaˇzovan´ y shluk. p(., .) - funkce sousedstv´ı. Pokud tedy spoj´ıme shluky A a B a vytvoˇr´ıme t´ım shluk R, sousedstv´ı nov´eho shluku R v˚ uˇci jiˇz existuj´ıc´ımu shluku Q je line´arn´ı funkce sousedstv´ı shluku Q vzhledem ke shluk˚ um A a B. Tabulka 5 zobrazuje hodnoty tˇechto koeficient˚ u pro zm´ınˇen´e techniky. Nˇekter´e hierarchick´e algoritmy, kter´e mohou b´ yt vyj´adˇreny L-W vztahem, neukl´ adaj´ı p˚ uvodn´ı datov´e vzorky. Nam´ısto toho je matice sousednosti aktualizov´ ana bˇehem shlukov´ an´ı. M˚ uˇze se zd´at jednoduˇsˇs´ı pouˇz´ıt obecn´ y vztah L-W, ale zejm´ena pro implementaci je v´ yhodnˇejˇs´ı k porozumˇen´ı a k nalezen´ı rozd´ıl˚ u mezi jednotliv´ ymi hierarchick´ ymi metodami pouˇz´ıvat pˇr´ımo definice sousedstv´ı pro jednotliv´e metody.

29

Metoda shlukov´ an´ı Nejbliˇzˇs´ıho souseda Nejvzd´ alenˇejˇs´ıho souseda Pr˚ umˇer skupiny Tˇeˇziˇst’ov´ a metoda Wardova metoda

αA 1/2 1/2

αB 1/2 1/2

mA mA +mB mA mA +mB mA +mQ mA +mB +mQ

mB mA +mB mB mA +mB mB +mQ mA +mB +mQ

β 0 0 0 −mA mB (mA +mB )2 −mQ mA +mB +mQ

γ −1/2 1/2 0 0 0

Tabulka 5: Parametry L - W vztahu pro klasick´e hierarchick´e algoritmy 2.2.4

Probl´ emy hierarchick´ eho shlukov´ an´ı

Absence glob´ aln´ı u ´ˇ celov´ e funkce Jedn´ım z probl´em˚ u je, ˇze aglomerativn´ı hierarchick´e shlukov´ an´ı neum´ı glob´alnˇe optimalizovat u ´ˇcelovou funkci. Nam´ısto toho pouˇz´ıv´ a r˚ uzn´ a krit´eria pro lok´aln´ı rozhodnut´ı v kaˇzd´em kroce, kter´a se pouˇz´ıvaj´ı pro volbu shluk˚ u, kter´e maj´ı b´ yt spojeny. Tento pohled na shlukov´an´ı pˇrin´ aˇs´ı shlukov´e algoritmy, kter´e se vyh´ ybaj´ı obt´ıˇznostem v podobˇe kombinatorick´ ych optimalizaˇcn´ıch probl´em˚ u. Tyto pˇr´ıstupy nemaj´ı probl´emy s nalezen´ım lok´ aln´ıch minim nebo s v´ ybˇerem poˇc´ateˇcn´ıch vzork˚ u. Na druhou stranu odrazuje od pouˇzit´ı tˇechto technik ˇcasov´a a pamˇet’ov´a n´aroˇcnost. Schopnost vytvoˇ rit r˚ uzn´ e velikosti shluk˚ u Jedna vˇec zde jeˇstˇe nebyla zm´ınˇen´ a, a to jak zach´ azet s relativn´ımi velikostmi slouˇcen´ ych shluk˚ u. Existuj´ı dvˇe varianty - v´ aˇzen´ a, kter´a bere v u ´vahu poˇcet vzork˚ u v kaˇzd´em shluku a nev´ aˇzen´ a, kter´ a bere vˇsechny shluky stejnou mˇerou. Vˇsimnˇeme si, ˇze term´ıny v´ aˇzen´ y a nev´ aˇzen´ y se t´ yk´ a datov´ ych vzork˚ u a ne samotn´ ych shluk˚ u. Jin´ ymi slovy ˇreˇceno - shluky nestejn´ ych velikost´ı d´avaj´ı rovnomˇernˇe r˚ uzn´e v´ahy bod˚ um v r˚ uzn´ ych shluc´ıch, zat´ımco pokud bereme v u ´vahu velikosti shluk˚ u, pak je bod˚ um v r˚ uzn´ ych shluc´ıch d´av´ana v´aha stejn´a. Rozhodnut´ı o spojen´ı dvou shluk˚ u jsou koneˇ cn´ a Aglomerativn´ı postupy pˇrin´ aˇs´ı dobr´ a lok´ aln´ı rozhodnut´ı, co se t´ yˇce kombinov´an´ı dvou shluk˚ u, protoˇze mohou pouˇz´ıt informaci o podobnostech mezi p´ary ze vˇsech bod˚ u. Nicm´enˇe pokud jiˇz jednou spoj´ıme dva shluky, nen´ı moˇzn´e toto spojen´ı pozdˇeji zruˇsit, coˇz je hlavn´ı pˇr´ıˇcinou toho, ˇze se z lok´aln´ıho optimalizaˇcn´ıho krit´eria nestane glob´ aln´ı. D˚ usledkem je pak to, ˇze nejsou shluky stabiln´ı, resp. bod v nˇejak´em shluku m˚ uˇze b´ yt bl´ıˇze k tˇeˇziˇsti shluku jin´eho neˇz k tomu, ke kter´emu nyn´ı pˇr´ısluˇs´ı. Existuj´ı techniky, kter´e se snaˇz´ı pˇrej´ıt pˇres zm´ınˇen´e limity. Jedna z moˇznost´ı je pohybovat vˇetvemi stromu, abychom vylepˇsili glob´aln´ı u ´ˇcelovou funkci. Dalˇs´ı moˇznost pouˇz´ıv´ a nehierarchick´e techniky shlukov´an´ı (napˇr. Kmeans) k vytvoˇren´ı mnoha mal´ ych shluk˚ u, kter´e pak bere jako poˇc´ateˇcn´ı body pro hierarchick´e shlukov´ an´ı.

30

Siln´ e a slab´ e str´ anky Siln´e a slab´e str´anky jednotliv´ ych technik aglomerativn´ıho hierarchick´eho shlukov´an´ı jiˇz byly prodiskutov´any. Obecnˇe se vˇsak takov´e algoritmy ˇcasto pouˇz´ıvaj´ı, protoˇze mnoho systematick´ ych aplikac´ı vyˇzaduje hierarchii. Existuj´ı studie tvrd´ıc´ı, ˇze tyto algoritmy mohou produkovat kvalitnˇejˇs´ı shluky. Nicm´enˇe aglomerativn´ı pˇr´ıstupy jsou n´aroˇcn´e, co se t´ yˇce doby v´ ypoˇctu a poˇzadavk˚ u na pamˇet’. Skuteˇcnost, ˇze vˇsechna spojen´ı jsou koneˇcn´a, m˚ uˇze takt´eˇz ˇcinit probl´emy zejm´ena pˇri pr´aci se ˇsumem a s vysoce-dimenzion´aln´ımi daty. Postupnˇe mohou b´ yt tyto dvˇe z´aleˇzitosti vyˇreˇseny pomoc´ı jin´ ych nehierarchick´ ych technik, napˇr. pomoc´ı Kmeans.

2.3

DBSCAN

DBSCAN je metoda zaloˇzen´a na hustotˇe bod˚ u. Shlukov´an´ı zaloˇzen´e na hustotˇe hled´ a oblasti o vysok´e hustotˇe bod˚ u, kter´e jsou oddˇelen´e oblastmi s hustotou n´ızkou. 2.3.1

Z´ akladn´ı idea DBSCANu

Centr´ aln´ı hustota, neboli hustota zaloˇzen´a na centru, patˇr´ı mezi nejˇcastˇeji pouˇz´ıvan´e typy hustot. V tomto pˇr´ıstupu je hustota odhadov´ana pro urˇcit´e specifick´e body v mnoˇzinˇe dat, kdy je poˇc´ıt´ano mnoˇzstv´ı bod˚ u v urˇcen´em okruhu kolem centra. Centrum je samozˇrejmˇe zapoˇc´ıt´ano tak´e jako souˇc´ast shluku. Tato technika je zobrazena na obr´ azku 17, kdy body ve stanoven´em okruhu kolem bodu A reprezentuj´ı centr´ aln´ı hustotu.

A Eps

Obr´azek 17: Centr´aln´ı hustota ˇ Reknˇ eme, ˇze bod q leˇz´ı v okol´ı bodu p, jestliˇze se nenach´az´ı ve vzd´alenosti vˇetˇs´ı neˇz je urˇcen´ a vzd´ alenost ε (tj. ˇze bod q je souˇc´ast´ı ε-sousedstv´ı bodu p). Pokud je bod p obklopen dostateˇcnˇe mnoho body, pak mohou b´ yt p a q souˇc´ast´ı jednoho ˇ shluku, i kdyˇz q neleˇz´ı v okol´ı bodu p. Reknˇ eme, ˇze bod q je dosaˇziteln´ y z p, pokud existuje posloupnost bod˚ u p1, p2 , ...pn takov´a, ˇze p1 = p a pn = q , a kde je kaˇzd´ y pi+1 v okol´ı od pi . Tento vztah t´ ykaj´ıc´ı se shluk˚ u zaloˇzen´ ych na hustotˇe nen´ı symetrick´ y (q m˚ uˇze leˇzet na hranˇe shluku, kdy nem´a dostateˇcnˇe mnoˇzstv´ı soused˚ u, aby byl povaˇzov´an za skuteˇcn´ y element klastru), a tak je

31

spojen´ı pomoc´ı hustoty n´ asledovn´e: body p a q jsou spojen´e pr´avˇe tehdy, kdyˇz existuje bod o takov´ y, ˇze o a p (takt´eˇz jako o a q) jsou hustotnˇe dosaˇziteln´e. Tato metoda je jednoduch´ a na implementaci, ale velkou roli zde hraje velikost definovan´eho okruhu kolem centra dan´e vzd´alenosti ε. Napˇr´ıklad, pokud je okruh (resp. jeho polomˇer) dost velk´ y, pak budou m´ıt vˇsechny body hustotu m (poˇcet bod˚ u v datov´e mnoˇzinˇe). Podobn´e plat´ı i naopak - pokud bude polomˇer pˇr´ıliˇs mal´ y, pak budou m´ıt vˇsechny body hustotu 1. Shluk, kter´ y je podmnoˇzinou vzork˚ u v mnoˇzinˇe, splˇ nuje tyto dva postul´aty : 1. Vˇsechny body v klastru jsou navz´ajem dosaˇziteln´e na z´akladˇe hustoty. 2. Pokud je bod dosaˇziteln´ y na z´akladˇe hustoty s kaˇzd´ ym bodem ve shluku, je rovnˇeˇz souˇc´ ast´ı dan´eho shluku. Klasifikace bod˚ u vzhledem k centr´ aln´ı hustotˇ e Centr´aln´ı hustota umoˇzn ˇuje klasifikovat n´ asleduj´ıc´ı body : ˆ j´ adrov´y bod - nach´ az´ı se uvnitˇr shluku. Bod je j´adrov´ ym, pokud poˇcet bod˚ u uvnitˇr dan´eho sousedstv´ı okolo bodu urˇcen´eho funkc´ı vzd´alenosti a parametrem vzd´ alenosti dan´eho uˇzivatelem dosahuje nˇejak´e hranice, coˇz je dalˇs´ı parametr, kter´ y si urˇcuje s´am uˇzivatel. ˆ hraniˇcn´ı bod - nen´ı j´ adrov´ y, ale je zaˇrazen do sousedstv´ı kolem bodu j´ adrov´eho. Hraniˇcn´ı bod m˚ uˇze spadat pod nˇekolik j´adrov´ ych. ˆ ˇsumy a body pozad´ı - body n´ ahodnˇe rozpt´ ylen´e, nach´azej´ıc´ı se v ˇr´ıdce obsazen´e oblasti. Nen´ı ani j´adrov´ y, ani hraniˇcn´ı. Sumove body

B C Eps A Jadrove body

Hranicni bod

Obr´ azek 18: J´ adro oblasti, hranice oblasti a ˇsum ve dvourozmˇern´em prostoru

32

2.3.2

Algoritmus DBSCAN

Po urˇcen´ı obou z parametr˚ u - ε a minim´aln´ıho poˇctu bod˚ u potˇrebn´ ych k vytvoˇren´ı klastru - zaˇc´ın´ a DBSCAN s libovolnˇe zvolen´ ym bodem. Dojde k urˇcen´ı jeho okol´ı ve vzd´ alenosti ε. Jestliˇze toto okol´ı obsahuje dostateˇcn´e mnoˇzstv´ı bod˚ u (zadan´e jako druh´ y parametr), je vytvoˇren shluk. Jinak je bod prozat´ım oznaˇcen jako ˇsum. Toto oznaˇcen´ı ˇsumu nemus´ı b´ yt koneˇcn´e. V dalˇs´ıch iterac´ıch m˚ uˇze b´ yt totiˇz tento bod souˇc´ast´ı okol´ı jin´eho bodu, a tak b´ yt souˇc´ast´ı jin´eho shluku. Pokud je bod oznaˇcen jako souˇc´ast klastru, jeho ε-okol´ı je tak´e souˇc´ast´ı klastru. Z tohoto d˚ uvodu vˇsechny body, kter´e se nach´az´ı v okol´ı ve vzd´alenosti ε vˇsech j´ adrov´ ych bod˚ u, jsou pˇrid´ any spolu s jejich vlastn´ım ε- okol´ım. Tento postup pokraˇcuje, dokud jiˇz neexistuje bod, kter´ y by mohl b´ yt pˇrid´an do uvaˇzovan´eho shluku. Pokud poˇcet pˇrid´ avan´ ych bod˚ u pˇrevyˇsuje minim´aln´ı poˇcet bod˚ u pro vytvoˇren´ı klastru, vznikne shluk. Pot´e je nov´ y, dosud v˚ ubec neuvaˇzovan´ y, bod br´ an jako poˇc´ ateˇcn´ı a cel´ y proces je opakov´an. Nakonec mus´ı b´ yt pˇriˇrazeny hraniˇcn´ı body pouze do jednoho shluku (pokud nen´ı ˇ povoleno, ˇze mohou b´ yt souˇca´st´ı v´ıce shluk˚ u). Sumov´ e body jsou vyˇrazeny. Tento algoritmus je optimalizov´ an z hlediska jednoduchosti a ne z hlediska efektivity. Z´ akladn´ı algoritmus DBSCANu 1. Poˇc´ atek cyklu - vezmi libovoln´ y (dosud neuvaˇzovan´ y) bod. 2. Oznaˇc jako j´ adrov´e body, kter´e se nach´az´ı v jeho ε- okol´ı. 3. Pˇridej body nach´ azej´ıc´ı se v ε- okol´ı vˇsech j´adrov´ ych bod˚ u. 4. Jiˇz nelze pˇridat dalˇs´ı bod. Pokud poˇcet bod˚ u ve shluku je vˇetˇs´ı neˇz minim´ aln´ı poˇzadovan´ y poˇcet bod˚ u pro vytvoˇren´ı shluku, vznikne shluk. 5. Nen´ı splnˇena podm´ınka minim´aln´ıho poˇctu bod˚ u pro vytvoˇren´ı shluku. P˚ uvodn´ı bod je oznaˇcen jako ˇsum. 6. Konec cyklu, pokud jsou proˇsetˇreny vˇsechny body. 7. Pˇriˇrazen´ı hraniˇcn´ıch bod˚ u do jednoho shluku. Odstranˇen´ı ˇsumov´ ych bod˚ u. Volba parametr˚ u DBSCANu Jednou ze z´asadn´ıch z´aleˇzitost´ı je volba parametr˚ u ε a minim´ aln´ıho poˇctu bod˚ u potˇrebn´ ych k vytvoˇren´ı shluku (M inP ts). Tyto parametry jsou ve vˇetˇsinˇe pˇr´ıpad˚ u urˇceny samotn´ ym uˇzivatelem, protoˇze r˚ uzn´e datov´e mnoˇziny a oblasti aplikace algoritmu poˇzaduj´ı rozd´ıln´e parametry. Jednou z moˇznost´ı, jak urˇcit poˇc´ateˇcn´ı hodnotu parametr˚ u, je pomoc´ı tzv. k-vzd´ alenosti. Z´ akladem je urˇcit samotn´e k, pak se pod´ıvat na vzd´alenost z kaˇzd´eho bodu k jeho k-t´emu nejbliˇzˇs´ımu sousedovi. Tato vzd´alenost se naz´ yv´a k-vzd´ alenost. Napˇr. uvaˇzujme k = 5, pak od kaˇzd´eho bodu urˇc´ıme k-vzd´alenost jako vzd´ alenost k 5. nejbliˇzˇs´ımu bodu. 33

Pro body patˇr´ıc´ı do shluku, bude k-vzd´alenost mal´a, pokud nebude k vˇetˇs´ı neˇz velikost klastru. Existuje urˇcit´ y rozptyl hodnot k, kter´ y z´avis´ı na hustotˇe jednotliv´ ych shluk˚ u. Pokud nejsou hustoty pˇrirozen´ ych shluk˚ u radik´alnˇe rozd´ıln´e, nebude rozptyl hodnoty k-vzd´ alenosti velk´ y. Pro ˇsumov´e body bude k-vzd´alenost velk´ a. Pokud spoˇcteme k-vzd´ alenost pro vˇsechny datov´e vzorky, seˇrad´ıme je vzestupnˇe a zakresl´ıme, uvid´ıme ostrou zmˇenu v hodnot´ach k-vzd´alenosti, jak si lze vˇsimnout na prav´e ˇc´ asti obr´ azku 19. Hodnota pod ostrou zmˇenou je vhodnou velikost´ı pro volbu parametru ε. Jako minim´aln´ı poˇcet bod˚ u pro vytvoˇren´ı shluku je moˇzn´e vz´ıt samotn´e k (v naˇsem pˇr´ıpadˇe je M inP ts = 5).

Vzorek dat

K−vzdalenost pro dany vzorek dat

Obr´ azek 19: Vzorek dat a k-vzd´alenost Na lev´e ˇca ´sti obr´ azku 19 je zobrazena mnoˇzina vzork˚ u dat. Na prav´e ˇc´ asti je vykreslen graf s odpov´ıdaj´ıc´ımi k-vzd´ alenostmi

Hodnota polomˇeru z´ aleˇz´ı na k a s n´ım se tak´e mˇen´ı. Kdyˇz je hodnota k pˇr´ıliˇs mal´ a, pak i mal´e mnoˇzstv´ı bod˚ u um´ıstˇen´ ych bl´ızko sebe, kter´e pˇredstavuj´ı ˇsum nebo outlier, je nekorektnˇe oznaˇceno jako klastr. Pokud je vˇsak hodnota k pˇr´ıliˇs velk´ a, pak budou pravdˇepodobnˇe mal´e klastry (velikosti menˇs´ı neˇz k) oznaˇceny jako ˇsum. P˚ uvodn´ı DBSCAN pouˇz´ıv´a hodnotu k = 4, kter´a se jev´ı jako vhodn´a pro vˇetˇsinu dvou-rozmˇern´ ych mnoˇzin dat. Shluky s mˇ en´ıc´ı se hustotou U DBSCANu se mohou vyskytnout probl´emy s hustotou, pokud se hustota shluk˚ u mˇen´ı. V lev´e ˇc´asti obr´azku 19 jsou zobrazeny 4 shluky vˇcetnˇe ˇsumu. Hustota shluk˚ u a oblast´ı ˇsumu je vykreslena jin´ ym ˇ odst´ınem. Sum kolem obou shluk˚ u A a B m´a stejnou hustotu jako samotn´e shluky C a D. Pokud je velikost polomˇeru dostateˇcnˇe mal´a tak, ˇze DBSCAN povaˇzuje C a D za klastry, pak A a B a body je obklopuj´ıc´ı vytvoˇr´ı jedin´ y klastr. Pokud je polomˇer dost velk´ y, pak DBSCAN urˇc´ı A a B jako jednotliv´e oddˇelen´e shluky a body kolem oznaˇc´ı jako ˇsum a n´aslednˇe budou C a D a body kolem povaˇzov´ any takt´eˇz za ˇsum. Na lev´e ˇc´ asti obr´ azku 19 jsou vykresleny shluky, kter´e jsou nalezeny v pomˇernˇe sloˇzit´e dvou-rozmˇern´e mnoˇzinˇe dat. Tato mnoˇzina je vytvoˇrena z 3000 vzork˚ u. 34

Velikost polomˇeru pro tato data byla urˇcena na z´akladˇe vykreslen´ı vybran´ ych vzd´ alenost´ı ˇctvrt´eho nejbliˇzˇs´ıho souseda od kaˇzd´eho bodu a takt´eˇz na z´akladˇe urˇcen´ı hodnoty, pˇri kter´e doch´az´ı k ostr´emu vzestupu. Byl vybr´an polomˇer ε = 10, kter´ y odpov´ıd´ a kolenu u vzestupu vykreslen´ ych k-vzd´alenost´ı. Shluky nalezen´e DBSCANem za pouˇzit´ı n´asleduj´ıc´ıch parametr˚ u : ε = 10 , min (P ts) = 4 jsou zobrazeny na horn´ı ˇc´ asti obr´azku 20. J´adrov´e, hraniˇcn´ı body a ˇsum jsou uk´ az´ any v ˇc´ asti spodn´ı.

Nalezene shluky DBSCANem

Jadrove, hranicni a sumove body

Obr´ azek 20: Uk´azka DBSCAN shlukov´an´ı Na spodn´ı ˇc´ asti obr´ azku jsou j´ adrov´e body oznaˇceny koleˇckem, hraniˇcn´ı plusem a ˇsum kˇr´ıˇzkem.

Poˇ zadavky na ˇ cas a pamˇ et’ Z´akladn´ı ˇcasov´a sloˇzitost algoritmu DBSCAN je m kr´ at ˇcas potˇrebn´ y k nalezen´ı bod˚ u v sousedstv´ı, kde m je poˇcet bod˚ u. V nejhorˇs´ım pˇr´ıpadˇe m˚ uˇze b´ yt ˇcasov´a n´aroˇcnost m2 ˇcasov´ ych jednotek. Nicm´enˇe v n´ızko-dimenzion´ aln´ıch prostorech jsou datov´e struktury, kter´e umoˇzn ˇuj´ı efektivn´ı nalezen´ı vˇsech bod˚ u uvnitˇr dan´e vzd´alenosti, a tak mohou b´ yt poˇzadavky na ˇcas niˇzˇs´ı neˇz m × log (m) ˇcasov´ ych jednotek. 35

Poˇzadavek na pamˇet’ i pro vysoko-dimenzion´aln´ı data je m, protoˇze je nutn´e udrˇzovat pouze mal´e mnoˇzstv´ı dat pro kaˇzd´ y bod (napˇr. znaˇcku shluku k identifikaci kaˇzd´eho bodu jako j´ adro, hranice nebo ˇsum). 2.3.3

Siln´ e a slab´ e str´ anky DBSCANu

Jeho klady jsou: ˆ Nepoˇzaduje apriornˇe zadanou informaci t´ ykaj´ıc´ı se poˇctu shluk˚ u. ˆ Um´ı naj´ıt shluky libovoln´ ych tvar˚ u. Dok´aˇze dokonce urˇcit i shluky, kter´e se dokonale obklopuj´ı (nesm´ı vˇsak b´ yt propojeny). ˆ Bere v u ´vahu ˇsum. ˆ Poˇzaduje pouze dva parametry a je vˇetˇsinou necitliv´ y v˚ uˇci poˇrad´ı bod˚ u v datab´ azi (pouze body nach´azej´ıc´ı se na hranici dvou r˚ uzn´ ych klastr˚ u si moˇzn´ a vymˇen´ı pˇr´ısluˇsnost k urˇcit´emu klastru, pokud se zmˇen´ı jejich poˇrad´ı v datab´ azi).

Jeho z´ apory jsou: ˆ Nejbˇeˇznˇejˇs´ı pouˇz´ıvanou metrikou je Eukleidovsk´ a vzd´alenost, avˇsak pro vysoko-dimenzion´ aln´ı data je volba t´eto metriky neefektivn´ı. ˆ Neoperuje dobˇre s datov´ ymi mnoˇzinami s mˇen´ıc´ı se hustotou (hierarchick´e datov´e mnoˇziny). ˆ Nehod´ı se pro vysoko-dimenzion´ aln´ı data kv˚ uli obt´ıˇzn´emu definov´an´ı hustoty. ˆ Je velmi n´ aroˇcn´ y pro vysoko-dimenzion´aln´ı data, pokud poˇc´ıt´an´ı nejbliˇzˇs´ıch soused˚ u vyˇzaduje v´ ypoˇcet mezi kaˇzd´ ymi dvˇema sousedy.

ˇ ˆ Casov´ a n´ aroˇcnost v´ ypoˇctu je mnohem vyˇsˇs´ı neˇz v pˇredchoz´ıch dvou pˇr´ıpadech algoritm˚ u Kmeans a hierarchick´ ych metod. Ponˇevadˇz DBSCAN operuje se shluky zaloˇzen´ ymi na hustotˇe, je pomˇernˇe odoln´ y v˚ uˇci ˇsumu a um´ı pracovat se shluky libovoln´ ych tvar˚ u a velikost´ı, proto um´ı nal´ezt mnohdy klastry, kter´e nemohou b´ yt zobrazeny jin´ ymi algoritmy, jak´ ymi je napˇr. Kmeans. To je tak´e d˚ uvodem jeho ˇcast´eho pouˇzit´ı.

36

3

Testov´ an´ı

V n´ asleduj´ıc´ı ˇc´ asti budou provedeny experimenty probran´ ych shlukov´ ych algoritm˚ u - Kmeans, hierarchick´eho shlukov´an´ı a DBSCANu. Nejprve budou testov´ any na simulovan´ ych datech a pot´e na datech re´aln´ ych dopravn´ıch.

3.1

Simulovan´ a data

Prvn´ı zm´ınˇen´ a data (simulovan´a) byla vytvoˇrena ve tˇrech form´ach. V kaˇzd´e formˇe dat je moˇzn´e nal´ezt mnoˇzinu model˚ u, kter´e reprezentuj´ı shluky. Tato mnoˇzina se bˇeˇznˇe naz´ yv´ a smˇes, jednotliv´e modely komponenty. Pro simulaci byla pouˇzita smˇes pˇeti statick´ ych komponent s norm´aln´ım rozdˇelen´ım ˇsumu. Prvn´ı data byla simulov´ ana tak, ˇze je moˇzn´e urˇcit shluky pouh´ ym okem, ve druh´em kroce byla testov´ ana data podobn´e struktury, ve kter´e maj´ı shluky zachov´ any polohy sv´ ych tˇeˇziˇst’ a kter´e jsou vˇsak lehce zaˇsumˇen´a. U prvn´ıch dvou forem dat je moˇzn´e urˇcit shluky pouh´ ym okem. Posledn´ı struktura dat jiˇz obsahuje velk´e mnoˇzstv´ı ˇsumu, a tak nen´ı moˇzn´e urˇcit shluky pouh´ ym okem. 3.1.1

Testov´ an´ı Kmeans na simulovan´ ych datech

Nejprve byla data testov´ ana s algoritmem Kmeans. Kmeans je algoritmus vyˇzaduj´ıc´ı urˇcen´ı parametru - poˇcet shluk˚ u (K). Je vˇsak moˇzn´e urˇcit pouze interval poˇctu shluk˚ u - < minim´ aln´ı poˇ cet shluk˚ u, maxim´ aln´ı poˇ cet shluk˚ u >.

Kmeans pro pocet shluku 5

Kmeans pro pocet shluku <2, 10>

Obr´ azek 21: Uk´ azka pouˇzit´ı algoritmu Kmeans na nezaˇsumˇen´ ych datech

37

Na lev´e ˇca ´sti obr´ azku byl zvolen interval poˇctu shluk˚ u < 2 shluky, 10 shluk˚ u > a byly nalezeny 4 shluky, pˇriˇcemˇz pˇrirozen´ a struktura dat pˇredstavuje shluk˚ u 5. D˚ uvodem, proˇc byly dva shluky spojeny, je vzd´ alenost, resp. bl´ızkost, tˇeˇziˇst’ spojen´ ych shluk˚ u. Shluky se nach´ az´ı relativnˇe bl´ızko sebe ve srovn´ an´ı s ostatn´ımi klastry a nav´ıc hustota datov´ ych vzork˚ u jim pˇr´ısluˇsej´ıc´ı je n´ızk´ a. Shlukov´ an´ı lze v pˇr´ıpadˇe volby 5 klastr˚ u povaˇzovat za kvalitn´ı. V´ ysledek shlukov´ an´ı o 5 klastrech je zobrazen na prav´e ˇca ´sti obr´ azku 21.

Dalˇs´ım kladn´ ym rysem pouˇzit´ı tohoto algoritmu je jeho v´ ypoˇcetn´ı nen´aroˇcnost shluky byly nalezeny jiˇz po 3 iterac´ıch (resp. po tˇrech iterac´ıch se pˇrestala h´ ybat tˇeˇziˇstˇe nalezen´ ych klastr˚ u). Na druhou stranu je Kmeans u ´pln´ y (viz Pˇr´ıloha 5.5) shlukov´ y algoritmus, takˇze nebyl uvaˇzov´an ˇz´adn´ y ˇsum ˇci outlieˇri a vˇsechny vzorky byly zaˇrazeny do klastr˚ u. Jak jiˇz bylo ˇreˇceno na zaˇc´ atku, algoritmus Kmeans byl otestov´an i na dalˇs´ıch dvou form´ ach zaˇsumˇen´ ych dat. Na obr´azku 22 m˚ uˇzeme vidˇet v´ ysledek shlukov´ an´ı pˇri urˇcen´ı poˇctu shluk˚ u 5. Lze si vˇsimnout zejm´ena na prav´e ˇc´asti obr´ azku, kde Kmeans tvoˇr´ı shluky kulovit´eho tvaru. I kdyˇz byla p˚ uvodn´ı data hodnˇe zaˇsumˇen´ a, byly vytvoˇreny pomˇernˇe kvalitn´ı shluky (kulovit´e).

Lehce zasumena data

Velmi zasumena data

Obr´ azek 22: Uk´ azka pouˇzit´ı algoritmu Kmeans na zaˇsumˇen´ ych datech Na lev´e ˇca ´sti obr´ azku byla pouˇzita data lehce zaˇsumˇen´ a, u kter´ ych je jeˇstˇe moˇzn´e urˇcit shluky pouh´ ym okem. Na prav´e ˇca ´sti obr´ azku jsou data ve 3. formˇe - velmi zaˇsumˇen´ a. V obou pˇr´ıpadech doˇslo k vytvoˇren´ı kvalitn´ıch kulovit´ ych shluk˚ u po probˇehnut´ı Kmeans algoritmu s urˇcen´ ym poˇctem shluk˚ u 5.

3.1.2

Testov´ an´ı hierarchick´ eho algoritmu na simulovan´ ych datech

V pˇr´ıpadˇe testov´ an´ı prvn´ıho typu dat (nezaˇsumˇen´ ych) pomoc´ı hierarchick´eho algoritmu nebylo dosaˇzeno tak kvalitn´ıho v´ ysledku jako v pˇr´ıpadˇe algoritmu Kmeans. V´ ysledek je zobrazen na obr´azku 23. 38

Obr´ azek 23: Uk´ azka pouˇzit´ı hierarchick´eho algoritmu na nezaˇsumˇen´ ych datech V´ ysledkem shlukov´ an´ı byly 4 shluky, kter´e vˇsak nevystihuj´ı pˇrirozenou strukturu dat. D˚ uvodem m˚ uˇze b´ yt koneˇcn´e pˇriˇrazen´ı prvk˚ u do shluk˚ u, a tedy nalezen´ı lok´ aln´ıho minima (viz 2.2.4).

Na tomto algoritmu byla testov´ana i dalˇs´ı simulovan´a (zaˇsumˇen´a) data, ale nebylo dosaˇzeno zaj´ımav´ ych v´ ysledk˚ u. Na obr´ azku 24 jsou vykresleny dendrogramy pro zaˇsumˇen´a data.

Dendrogram pro lehce zasumena data

Dendrogram pro velmi zasumena data

Obr´ azek 24: Dendrogramy pro zaˇsumˇen´a data

39

Na lev´e ˇca ´sti obr´ azku (jedn´ a se o dendrogram m´enˇe zaˇsumˇen´ ych dat) je posledn´ı shluk vzd´ alen od ostatn´ıch, resp. je velk´ a vzd´ alenost na ose y v dendrogramu od naposledy vytvoˇren´eho shluku, coˇz je zˇrejmˇe d´ ano v´ yskytem nˇejak´eho outlieru. Oproti tomu je na prav´e ˇca ´sti obr´ azku vykreslen dendrogram pro nejv´ıce zaˇsumˇen´ a data, kter´ y je komplexnˇejˇs´ı, protoˇze jsou zde data rozm´ıstˇena rovnomˇernˇeji po cel´e ploˇse (nevytv´ aˇr´ı tedy pˇrirozen´e shluky), a tak nen´ı moˇzn´e naj´ıt prvek, kter´ y by byl tak extr´emnˇe vzd´ alen od ostatn´ıch jako v pˇredchoz´ım pˇr´ıpadˇe.

3.1.3

Testov´ an´ı DBSCANu na simulovan´ ych datech

Na z´ avˇer byla simulovan´ a data zpracov´ana i algoritmem DBSCAN. Jak jiˇz bylo zm´ınˇeno v 2.3.3, je DBSCAN velmi citliv´ y v˚ uˇci nastaven´ı jeho z´akladn´ıch parametr˚ u, a to ε (polomˇer okol´ı uvaˇzovan´eho vzorku) a M inP ts (minim´aln´ı poˇcet vzork˚ u kolem uvaˇzovan´eho vzorku). Dalˇs´ım charakteristick´ ym znakem je, ˇze DBSCAN prov´ ad´ı shlukov´ an´ı ˇca´steˇcn´e (viz Pˇr´ıloha 5.5), proto uvaˇzuje ˇsum. M˚ uˇze tedy doj´ıt k tomu, ˇze nˇekter´e prvky nebudou zaˇrazeny do ˇz´adn´eho shluku. Ponˇevadˇz nepoˇzaduje apriornˇe zadan´ y poˇcet shluk˚ u, byly urˇceny parametry u prvn´ı formy dat (nezaˇsumˇen´ ych) tak, aby bylo nalezeno 5 pˇrirozen´ ych shluk˚ u a aby byl co nejmenˇs´ı poˇcet nezaˇrazen´ ych prvk˚ u, coˇz se povedlo s hodnotou parametr˚ u Eps = 0.05 a M inP ts = 10. V´ ysledek m˚ uˇzeme vidˇet na obr´azku 25. Vˇsimnˇeme si, ˇze nezaˇrazen´e prvky lze uvaˇzovat jako ˇsum. Bylo dosaˇzeno kvalitn´ıho shlukov´ an´ı zejm´ena proto, ˇze shluky nejsou propojen´e a ˇze hustota shluk˚ u je pomˇernˇe stejn´ a.

Obr´ azek 25: Uk´ azka pouˇzit´ı algoritmu DBSCAN na nezaˇsumˇen´ ych datech a pˇri optim´ aln´ı volbˇe parametr˚ u

40

Na obr´ azku 26 je demonstrov´an v´ ysledek shlukov´an´ı, pokud byly mˇenˇeny parametry ε a M inP ts.

Obr´ azek 26: Srovn´ an´ı v´ ysledku shlukov´an´ı pomoc´ı algoritmu DBSCAN pˇri r˚ uzn´e volbˇe parametr˚ u Na lev´e ˇca ´sti obr´ azku bylo zmˇenˇeno M inP ts = 10 na M inP ts = 30, a tak prvky mus´ı b´ yt obklopeny vˇetˇs´ım poˇctem prvk˚ u. Bylo nalezeno takt´eˇz 5 shluk˚ u, ale nebylo zaˇrazeno t´emˇeˇr 181 prvk˚ u, resp. 181 prvk˚ u bylo oznaˇceno jako ˇsum (na obr´ azku jsou zobrazeny pomoc´ı p´ısmene M ). Napravo byl zmˇenˇen parametr Eps z Eps = 0.05 na Eps = 0.10, tud´ıˇz se uvaˇzuje vˇetˇs´ı polomˇer okolo poˇc´ıtan´eho prvku. D˚ usledkem toho je, ˇze dva shluky si navz´ ajem bl´ızk´e byly slouˇceny do jednoho a nebyl nalezen ˇza ´dn´ y ˇsum.

Zmˇenu parametru M inP ts tedy lze vyuˇz´ıt, pokud jsme si vˇedomi, ˇze se v datech nach´ az´ı velk´e mnoˇzstv´ı ˇsumu. Pˇri zvˇetˇsen´ı M inP ts dojde k vˇetˇs´ımu poˇctu nezaˇrazen´ ych vzork˚ u (ˇsumu). V pˇr´ıpadˇe zaˇsumˇen´ ych dat nepˇrinesl algoritmus DBSCAN kvalitn´ı v´ ysledky. V druh´em pˇr´ıpadˇe m´ırnˇe zaˇsumˇen´ ych dat pˇri vhodnˇe zvolen´ ych parametrech z pˇredchoz´ıho pˇr´ıpadu pˇrinesl pouze jeden shluk, pˇri hled´an´ı lepˇs´ıho nastaven´ı byl st´ ale v´ ysledkem jeden shluk. Pokud byl poˇcet shluk˚ u vˇetˇs´ı, doch´azelo k oznaˇcen´ı velk´eho mnoˇzstv´ı prvk˚ u za ˇsumov´e (37 %). Ve tˇret´ı formˇe simulovan´ ych dat byl nalezen jeden shluk, a to i pˇri r˚ uzn´ ych volb´ach parametr˚ u. Rozd´ıl byl pouze v r˚ uzn´em poˇctu nezaˇrazen´ ych, tedy ˇsumov´ ych, prvk˚ u. V tabulce 6 jsou zobrazeny v´ ysledky shlukov´an´ı v z´avislosti na r˚ uzn´e formˇe dat a na r˚ uzn´e volbˇe parametr˚ u. Lze si vˇsimnout, ˇze nejkvalitnˇejˇs´ı v´ ysledek, co se t´ yˇce poˇctu shluk˚ u a mnoˇzstv´ı ˇsumu, je doopravdy u dat 1 (nezaˇsumˇen´ ych) pˇri volbˇe Eps = 0.05 a M inP ts = 10.

41

typy Eps = 0.05, M inP ts = 10 dat / parametry data 1 5 shluk˚ u (3 % ˇsum)

Eps = 0.05, M inP ts = 30

5 shluk˚ u (18 % ˇsum)

data 2

1 shluk (4 % ˇsum)

5 shluk˚ u (37 % ˇsum)

data 3

1 shluk (8 % ˇsum)

1 shluk (26 % ˇsum)

Eps = 0.10,M inP ts = 10 3 shluky (0 % ˇsum) 1 shluk (0 % ˇsum) 1 shluk (1 % ˇsum)

Tabulka 6: V´ ysledky shlukov´an´ı pomoc´ı algoritmu DBSCAN u r˚ uzn´ ych typ˚ u dat a pˇri r˚ uzn´ ych parametrech

3.2

Re´ aln´ a data

Pro testov´ an´ı re´ aln´ ych dat byla pouˇzita data z´ıskan´a z j´ızd testovac´ıho vozu ˇ Skoda, ve kter´em jsou zakomponov´any pˇr´ıstroje mˇeˇr´ıc´ı r˚ uzn´e veliˇciny. Pro testov´ an´ı byly vybr´ any veliˇciny plyn a rychlost. J´ızdy automobilu prob´ıhaly jak v intravil´ anu, tak v extravil´ anu. P˚ uvodn´ı strukturu dat je moˇzn´e si prohl´ednout na obr´ azku 27. Tato data byla opˇet podrobena testov´an´ı pomoc´ı tˇr´ı jiˇz zmiˇ novan´ ych algoritm˚ u.

Obr´azek 27: Re´aln´a data Osa x zobrazuje rychlost [km/h]. Na ose y je vyj´ adˇren plyn [%]. Lze si jiˇz pomoc´ı pouh´eho oka vˇsimnout r˚ uzn´ ych skupin dat. Nutn´e je vˇsak je striktnˇe rozdˇelit.

Velmi kvalitn´ıho v´ ysledku bylo dosaˇzeno pomoc´ı algoritmu Kmeans, coˇz je zobrazeno na obr´ azku 28. 42

Obr´ azek 28: Pouˇzit´ı Kmeans na re´aln´ ych datech Kmeans nalezl 5 shluk˚ u, resp. 5 pracovn´ıch m´ od˚ u, kop´ıruj´ıc´ıch pˇrirozenou strukturu sebran´ ych dat. I kdyˇz jsou pro Kmeans charakteristick´e kulovit´e shluky, byly nalezeny ostr´ a rozhran´ı mezi shluky. Pˇr´ıˇcinou m˚ uˇze b´ yt vˇetˇs´ı hustota dat ve smˇeru osy z.

Jak jiˇz bylo nast´ınˇeno v 1.1, byly pomoc´ı shlukov´an´ı nalezeny pracovn´ı m´ody. Jednotliv´e shluky odpov´ıdaj´ı r˚ uzn´ ym typ˚ um j´ızdy - napˇr. modr´ y shluk zˇrejmˇe odpov´ıd´ a j´ızdˇe ve mˇestˇe, protoˇze je charakterizov´an n´ızkou rychlost´ı a malou hodnotou plynu. Naopak r˚ uˇzov´ y shluk je typick´ y pro j´ızdu na d´alnici o vyˇsˇs´ı rychlosti s vyˇsˇs´ım plynem. Takt´eˇz velmi dobr´ y v´ ysledek byl nalezen pomoc´ı hierarchick´eho shlukov´an´ı, jak lze vidˇet na obr´ azku 29. Hierarchick´ y algoritmus byl vˇsak v´ ypoˇcetnˇe n´aroˇcnˇejˇs´ı.

43

Obr´ azek 29: Pouˇzit´ı hierarchick´eho shlukov´an´ı na re´aln´ ych datech Za pomoc´ı hierarchick´eho shlukov´ an´ı bylo nalezeno opˇet 5 shluk˚ u. Lze si vˇsimnout, ˇze jsou shluky znovu rozdˇeleny ostr´ ym rozhran´ım.

Nejhorˇs´ı v´ ysledek byl doc´ılen za pouˇzit´ı DBSCANu. Nejenˇze byl algoritmus v´ ypoˇcetnˇe n´ aroˇcn´ y na ˇcas, ale pˇri r˚ uzn´em nastavov´an´ı parametr˚ u Eps a MinPts bylo dosaˇzeno ˇspatn´ ych v´ ysledk˚ u - bud’ byl nalezen jeden shluk a velk´e mnoˇzstv´ı ˇsumov´ ych vzork˚ u (obr´ azek 30), nebo bylo nalezeno velk´e mnoˇzstv´ı klastr˚ u (obr´azek 31) opˇet vˇcetnˇe velk´eho mnoˇzstv´ı ˇsumu.

Obr´ azek 30: Nalezen´ı jednoho shluku za pouˇzit´ı DBSCANu na re´aln´ ych datech V tomto pˇr´ıpadˇe byly vytvoˇreny pouze dva shluky, pˇriˇcemˇz vˇetˇs´ı z nich obsahuje t´emˇeˇr 98 % ze vˇsech vzork˚ u. Takt´eˇz byly nˇekter´e vzorky oznaˇcen´e jako ˇsum. Shlukov´ an´ı v tomto pˇr´ıpadˇe lze povaˇzovat za nekvalitn´ı.

44

Obr´ azek 31: Nalezen´ı v´ıce shluk˚ u za pouˇzit´ı DBSCANu na re´aln´ ych datech Bylo nalezeno velk´e mnoˇzstv´ı shluk˚ u, coˇz je v naˇsem pˇr´ıpadˇe nepoˇzaduj´ıc´ı. Vzorky oznaˇcen´e p´ısmenem M jsou nezaˇrazen´e, tedy ˇsumov´e, kter´ ych bylo oznaˇceno 45 %. V´ ysledek shlukov´ an´ı je opˇet velmi nekvalitn´ı.

45

4

Z´ avˇ er

C´ılem pr´ ace bylo nal´ezt algoritmy, kter´e se pouˇz´ıvaj´ı pro klastrov´an´ı dat. V naˇsem pˇr´ıpadˇe jsem se zamˇeˇrila na oblast dopravy, konkr´etnˇe na anal´ yzu dat na jedouc´ım autˇe. V pr´ aci byly vytypov´any tˇri algoritmy - Kmeans, hierarchick´ y algoritmus a DBSCAN, kter´e byly podrobeny teoretick´emu rozboru a n´aslednˇe byly testov´ any na simulovan´ ych a re´aln´ ych dopravn´ıch datech. Je vˇsak nutn´e podotknout, ˇze existuje velk´a propast mezi simulac´ı a re´aln´ ymi daty. Simulovan´ a data byla pouˇzita, protoˇze v jejich pˇr´ıpadˇe je moˇzn´e je nastavit parametry, a tak prakticky demonstrovat vlastnosti algoritm˚ u popsan´e v teoretick´e ˇc´ asti. Na simulovan´ ych datech je moˇzn´e v´ ysledky klastrov´an´ı dobˇre porovnat. Nejlepˇs´ıho v´ ysledku v tomto pˇr´ıpadˇe bylo dosaˇzeno pomoc´ı algoritmu Kmeans. D˚ uvodem je, ˇze byly pro simulaci pouˇzit´e kulovit´e shluky, coˇz je vhodn´e pr´avˇe pro tento algoritmus. Jako nejm´enˇe vhodn´ y zejm´ena pro zaˇsumˇen´a data se jevil algoritmus DBSCAN kv˚ uli velk´emu mnoˇzstv´ı ˇsumu a nevhodn´emu, at’ uˇz vysok´emu, ˇci n´ızk´emu, poˇctu shluk˚ u. Shlukov´e algoritmy byly aplikov´any i na data re´aln´a, protoˇze ta se objevuj´ı v norm´ aln´ım ˇzivotˇe. Tento typ dat je pˇredmˇetem zkoum´an´ı v dopravn´ım v´ yzkumu. I zde bylo dosaˇzeno dobr´eho v´ ysledku pomoc´ı Kmeans. Velmi kvalitn´ı v´ ysledek podal algoritmus hierarchick´ y. DBSCAN lze opˇet oznaˇcit za velmi nekvalitn´ı. Pro dalˇs´ı v´ yzkum tedy doporuˇcuji hierarchick´e shlukov´an´ı, a to nejen kv˚ uli tomu, ˇze ukazuje dobr´e vlastnosti v pokryt´ı klastr˚ u, ale kv˚ uli moˇznosti volby libovoln´eho poˇctu klastr˚ u (dle volby rozliˇsovac´ı u ´rovnˇe).

46

Reference [1] Pang-Ning Tan, Michael Steinbach, Vipin Kumar : Introduction to Data mining : Pearson, Addison Wesley : ISBN 0-321-32136-7, 2006 ˇ [2] Alena Lukasov´ a, Jana Sarmanov´ a : Metody shlukov´e anal´ yzy : SNTL - Nakladatelstv´ı technick´e literatury, Praha 1985 [3] A.K.Jain, M.N.Murty, P.J.Flynn : Datat clustering- A Review : http://eprints.iisc.ernet.in/273/1/p264-jain.pdf [4] V. Kumar : Cluster analysis : Basic concepts and Algorithms : http://wwwusers.cs.umn.edu/˜kumar/dmbook/ch8.pdf

47

5

Pˇ r´ıloha

5.1

Co je shlukov´ a anal´ yza (cluster analysis)?

Shlukov´ a anal´ yza je technika rozdˇeluj´ıc´ı do skupin vzorky, kter´e jsou datov´eho charakteru a kter´e popisuj´ı urˇcit´e pˇredmˇety. C´ılem je, aby si vzorky ve shluku byly navz´ ajem podobn´e (pˇr´ıbuzn´e) a naopak odliˇsn´e s vzorky, kter´e patˇr´ı shluk˚ um ˇ ım jsou vzorky ve shluku pˇr´ıbuznˇejˇs´ı, tedy homogennˇejˇs´ı, a ˇc´ım jsou jin´ ym. C´ rozd´ıly mezi skupinami vˇetˇs´ı - heterogenˇejˇs´ı, t´ım je shlukov´an´ı kvalitnˇejˇs´ı a pˇresnˇejˇs´ı. ˆ Uved’me pˇr´ıklad z dopravy. Jsou sebr´ ana data ve formˇe intenzity z pozemn´ı ´ komunikace. Ukolem shlukov´e anal´ yzy m˚ uˇze b´ yt urˇcit dobu ve dne, kdy je intenzita n´ızk´ a, stˇredn´ı a vysok´a, tedy udˇelat skupiny (shluky) v namˇeˇren´e intenzitˇe, pˇriˇcemˇz z´ akladn´ım atributem je zde poˇcet detekovan´ ych aut.

V mnoha situac´ıch nen´ı samotn´ y pojem shluk (anglicky cluster, pozdˇeji pouˇz´ıv´an homonymn´ı pojem klastr) spr´avnˇe definov´an, resp. definovateln´ y. K lepˇs´ımu porozumˇen´ı obt´ıˇznosti v rozhodov´an´ı, co se skr´ yv´a pod pojmem shluk, uvaˇzujme obr´ azek 32, kter´ y ukazuje 20 bod˚ u a 3 rozd´ıln´e zp˚ usoby rozdˇelen´ı jej do shluk˚ u. Tvary znaˇcek ukazuj´ı pˇr´ısluˇsnost ke shluk˚ um.

a) Puvodni data

b) 2 shluky

c) 4 shluky

d) 6 shluku

Obr´ azek 32: R˚ uzn´e zp˚ usoby rozdˇelen´ı vzork˚ u do shluk˚ u Na obr´ azku b), c) a d) jsou dan´ a data rozdˇelen´ a do dvou, ˇctyˇr a ˇsesti shluk˚ u. Nicm´enˇe je jiˇz na prvn´ı pohled viditeln´e, ˇze lze oba shluky z b) rozdˇelit do tˇr´ı podshluk˚ u, a to i na z´ akladˇe pouh´eho lidsk´eho zraku, kter´ y nevyˇzaduje ˇza ´dnou teoretickou pˇr´ıpravu. Narozd´ıl od ˇca ´sti obr´ azku c), kde jsou vytvoˇreny shluky 4 na z´ akladˇe nˇejak´e informace nav´ıc. Tento obr´ azek ilustruje, ˇze definice shluku nen´ı pˇresn´ a a ˇze nejlepˇs´ı definice z´ aleˇz´ı na pˇrirozenosti a p˚ uvodu dat a na poˇzadovan´ ych v´ ysledc´ıch.

Segmentace a extrakce Term´ıny segmentace a rozdˇelov´an´ı jsou nˇekdy povaˇzov´any za synonyma. Ve shlukov´ an´ı jsou vˇsak pouˇz´ıv´ any pro r˚ uzn´e typy dat. Pojem rozdˇelov´an´ı je vˇetˇsinou 48

pouˇz´ıv´ an ve spojen´ı s technikami, kter´e rozdˇeluj´ı grafy na podgrafy a tedy hovoˇr´ıme sp´ıˇse o pˇr´ıpadu hierarchick´eho shlukov´an´ı. Kdeˇzto segmentace ˇcasto referuje o rozdˇelov´ an´ı dat do skupin, pˇriˇcemˇz pouˇz´ıv´a jednoduch´e techniky (zobrazen´ı m˚ uˇze b´ yt rozˇclenˇeno do segment˚ u zaloˇzen´ ych pouze na rozliˇsen´ı pixel˚ u a barev, nebo mohou b´ yt lid´e rozdˇeleni do skupin dle jejich pˇr´ıjm˚ u). Pojem segmentace tedy m˚ uˇzeme sp´ıˇse vyuˇz´ıt v nehierarchick´em shlukov´an´ı. Nˇekter´e shlukov´e algoritmy tedy pracuj´ı s rozdˇelen´ ymi grafy a jin´e s obr´azky r˚ uzn´ ych typ˚ u. Klasifikace vs. shlukov´ an´ı V t´eto pr´ aci se budu zab´ yvat zejm´ena statickou anal´ yzou dat, tedy klasifikac´ı jiˇz namˇeˇren´ ych dat. Shlukov´a anal´ yza je spojena s dalˇs´ımi technikami, kter´e se pouˇz´ıvaj´ı k rozdˇelov´ an´ı vzork˚ u do skupin. Shlukov´an´ı je nˇekdy povaˇzov´ano za druh, ˇci souˇc´ ast klasifikace, ve kter´em je oznaˇcen´ı vzork˚ u tvoˇreno urˇcitou znaˇckou shluku. L´epe ˇreˇceno - shlukov´a anal´ yza m´a slouˇzit jako prostˇredek k z´ısk´ an´ı klasifikace. V dopravn´ı oblasti napˇr. potˇrebujeme klasifikovat druh auta, kter´ y projel nad urˇcit´ ym detektorem, typ komunikace podle jej´ıho sloˇzen´ı ˇci v naˇsem pˇr´ıpadˇe jednotliv´e pracovn´ı m´ody. ˆ Klasifikace m˚ uˇze b´ yt povaˇzov´ana za kontrolovatelnou (anglicky - supervised), nˇekdy oznaˇcovanou jako uˇcen´ı s uˇcitelem – neoznaˇckovan´e vzorky jsou pˇridˇeleny tˇr´ıdˇe znaˇcek pouˇz´ıvaj´ıc´ı model, kter´ y se vyvinul ze vzork˚ u se zn´ amou tˇr´ıdou znaˇcek. Jinak ˇreˇceno m´ame informaci o tom, jak dan´ y model m´ a vypadat a jak se m´a chovat. Obecnˇe lze ˇr´ıci, ˇze se jedn´a o zaˇrazov´ an´ı dat do klastr˚ u. ˆ Shlukov´ a anal´ yza je vˇsak uvaˇzov´ana za uˇcen´ı bez uˇcitele (anglicky - unsupervised learning), a tud´ıˇz tato technika vˇetˇsinou nem´a informaci o tom, jak se m´ a dan´ y model chovat, a tak se jeho chov´an´ı vyv´ıj´ı v pr˚ ubˇehu shlukov´ an´ı. Obecnˇe vzato se zde jedn´a o vytv´aˇren´ı samotn´ ych klastr˚ u.

Objekty shlukov´ an´ı Je vhodn´e se tak´e zm´ınit o objektech shlukov´an´ı, tedy objektech urˇcen´ ych ke klasifikaci, a jejich znac´ıch. Prov´ad´ıme-li klasifikaci jedn´ım z algoritm˚ u shlukov´e anal´ yzy, mus´ı b´ yt splnˇeny urˇcit´e podm´ınky. Kaˇzd´ y konkr´etn´ı objekt mus´ı b´ yt pops´ an p-tic´ı stav˚ u pˇredem stanoven´ ych p znak˚ u. Je-li napˇr. mnoˇzinou objekt˚ u mnoˇzina urˇcit´ ych druh˚ u aut, stanov´ıme soubor znak˚ u, jako jsou d´elka, v´ yˇska, hmotnost, atd. Pot´e pro kaˇzd´ y detekovan´ y objekt zaznamen´ame va dan´em poˇrad´ı stavy, ve kter´ ych se jednotliv´e znaky nach´azej´ı. Je bˇeˇzn´e pˇriˇrazovat stav˚ um znak˚ u jejich ˇc´ıseln´e k´ody, kter´e pˇredstavuj´ı hodnoty znak˚ u. Objektem pro shlukov´ an´ı je tedy p-tice hodnot vybran´ ych znak˚ u (p-rozmˇern´ y vektor ˇc´ısel), kter´ a je identifik´ atorem dan´eho objektu. Poskl´ad´an´ım vektor˚ u pod sebe pak z´ısk´ ame matici dat, kde ˇr´ adky jsou tvoˇreny objekty a sloupce znaky.

49

Znaky mohou nab´ yvat r˚ uzn´ ych hodnot stav˚ u. Mnoˇzinu stav˚ u mohou tvoˇrit n´ asleduj´ıc´ı moˇznosti (uv´ adˇeny jsou pˇr´ıklady pro objekt - auto). ˆ interval re´ aln´e osy - napˇr. d´elka auta, hmotnost auta, v´ yˇska auta, atd. ˆ koneˇcn´ a (spoˇcetn´ a) mnoˇzina ˇc´ısel - napˇr. poˇcet kol, dveˇr´ı, v´alc˚ u, atd. ˆ dvojice logick´ ych hodnot (vˇetˇsinou pravdiv´ y/nepravdiv´ y v´ yrok) - tyto znaky jsou bˇeˇznˇe naz´ yv´any dichotomick´e. Jsou vˇetˇsinou k´odov´any pomoc´ı jedniˇcek (pravda) a nul (nepravda). Pˇr´ıkladem pro druh auta je benz´ınov´ y motor - ano / ne, ESP - ano / ne, apod. ˆ koneˇcn´ a mnoˇzina popisuj´ıc´ıch term´ın˚ u - z´aleˇz´ı jenom na n´as, jak´e popisuj´ıc´ı term´ıny si sami zvol´ıme, resp. z jak´ ych stav˚ u znak˚ u budeme vyb´ırat. Napˇr. spotˇreba auta - n´ızk´a, stˇredn´ı, vysok´a.

5.2

Souˇ c´ asti u ´ lohy shlukov´ an´ı

Obecn´ e kroky shlukov´ an´ı 1. Reprezentace dat (m˚ uˇze zahrnovat i extrakci a/nebo selekci), filtrace dat. 2. Definice mˇeˇren´ı bl´ızkosti vzork˚ u, kter´e je vhodn´e pro danou oblast dat (urˇcen´ı typu metriky). 3. Shlukov´ an´ı (klastrov´ an´ı). 4. Modelov´ an´ı dat. 5. Zhodnocen´ı v´ ystupu. V naˇsem pˇr´ıpadˇe syst´emu ˇridiˇc - automobil se jednotliv´e kroky budou vztahovat v pˇr´ıpadˇe reprezentace dat na filtraci namˇeˇren´ ych dat na syst´emu od outlier˚ u a ˇsumu, kteˇr´ı by naˇsi anal´ yzu mohly znehodnotit. V´ yskyt outlier˚ u a ˇsumu m˚ uˇze b´ yt d˚ usledkem nekvalitn´ıch mˇeˇric´ıch pˇr´ıstroj˚ u ˇci v´ yskytem extr´emn´ıch ˇridiˇc˚ u (j´ızda po mˇestˇe 100 km/h, ˇci j´ızda po d´alnici 30 km/h). Bl´ızkost vzork˚ u bude stanovov´ ana pomoc´ı Eukleidovsk´e metriky. V dalˇs´ıch kapitol´ach budou probr´ any algoritmy zab´ yvaj´ıc´ı se statickou anal´ yzou dat, nicm´enˇe pro praxi je samozˇrejmˇe vhodnˇejˇs´ı dynamick´e hodnocen´ı pracovn´ıch m´od˚ u, tedy dynamick´e tvoˇren´ı klastr˚ u, pro kter´e se zamˇeˇr´ıme na Bayesovsk´e metody v n´asleduj´ıc´ım obdob´ı. V modelov´ an´ı dat budou vytvoˇrena centra jednotliv´ ych pracovn´ıch m´od˚ u. Zhodnocen´ı v´ ystupu jiˇz pˇrin´aˇs´ı samotnou interakci mezi ˇridiˇcem a automobilem, kdy bude ˇridiˇci sdˇelen typ j´ızdy, resp. bude ˇridiˇc varov´an, pokud se bude nach´ azet v nebezpeˇcn´em m´ odu. Reprezentace dat se t´ yk´ a ot´azky poˇctu tˇr´ıd, mnoˇzstv´ı vzork˚ u a poˇctu, typu a v´ ahy atribut˚ u vhodn´ ych dan´emu shlukov´emu algoritmu. Nˇekter´e z tˇechto informac´ı nemus´ı b´ yt ovlivniteln´e. Selekce atribut˚ u je proces identifikov´an´ı nejefektivnˇejˇs´ı podmnoˇziny z p˚ uvodn´ıch atribut˚ u za u ´ˇcelem jej´ıho n´asledn´eho pouˇzit´ı 50

datové vzorky

selekce/extrakce

reprezentace

atributu

dat

vypocet podobnosti

shlukování

klastry

(vzdalenosti)

zpetnovazebni smycka

Obr´azek 33: F´aze shlukov´an´ı Obr´ azek 33 zobrazuje typick´ y sled prvn´ıch tˇr´ı krok˚ u zahrnuj´ıc´ı i zpˇetnovazebn´ı smyˇcku, kde v´ ystup z procesu shlukov´ an´ı (klastrov´ an´ı) m˚ uˇze zpˇetnˇe ovlivnit jak ˇca ´st extrakce a selekce atribut˚ u, tak i v´ ypoˇcet podobnosti, resp. vzd´ alenosti.

ve shlukov´ an´ı. Extrakce atribut˚ u je pouˇzit´ı jedn´e nebo v´ıce transformac´ı ze vstupn´ıch vlastnost´ı, aby byly vytvoˇreny nov´e charakteristick´e, v´ yznaˇcn´e atributy. Jedna nebo obˇe z tˇechto technik mohou b´ yt pouˇzity k obstar´an´ı vhodn´e mnoˇziny atribut˚ u, kter´e jsou pak pouˇzity ve shlukov´an´ı. Podobnost vzork˚ u je obvykle vn´ım´ana jako opak vzd´alenosti, kter´a je definov´ana pro p´ ary vzork˚ u. Jednoduch´e mˇeˇren´ı vzd´alenosti, jakou je zejm´ena Eukleidovsk´a vzd´ alenost, m˚ uˇze b´ yt ˇcasto pouˇzito ke zobrazen´ı nepodobnosti mezi dvˇema vzorky, zat´ımco jin´ a mˇeˇren´ı jsou pouˇz´ıv´ana k charakterizov´an´ı podobnosti mezi vzorky. ˇ ast klastrov´ C´ an´ı m˚ uˇze b´ yt vykon´ana r˚ uzn´ ymi zp˚ usoby. Shlukov´an´ı m˚ uˇze b´ yt pevn´e (rozdˇelen´ı dat do skupin) nebo fuzzy, hierarchick´e nebo nehierarchick´e. Modelov´ an´ı dat je proces vyb´ır´an´ı jednoduch´e a srozumiteln´e reprezentace mnoˇziny dat. Ve shlukov´ an´ı je modelov´an´ı dat kompaktn´ı popis kaˇzd´eho shluku, obvykle pomoc´ı popis˚ u model˚ u nebo reprezentativn´ıch vzork˚ u, kter´ ymi m˚ uˇzou b´ yt napˇr. stˇredy (centra) shluk˚ u. Ohodnocen´ı v´ ystupu shlukov´ an´ı Zhodnocen´ı v´ ystupu jednotliv´ ych technik shlukov´an´ı m´a nˇekolik str´anek. Jedna je vlastn´ı zhodnocen´ı oblasti dat sp´ıˇse neˇz samotn´ ych algoritm˚ u. Narozd´ıl od toho je anal´ yza spr´avnosti shluk˚ u zejm´ena o zhodnocen´ı v´ ystupu ˇ jednotliv´ ych procedur. Casto tato anal´ yza pouˇz´ıv´a specifick´e mˇeˇr´ıtko optimality, i kdyˇz jsou tato krit´eria znaˇcnˇe subjektivn´ı. Zhodnocen´ı spr´avnosti je objektivn´ı a slouˇz´ı k rozhodnut´ı, zda je v´ ystup smyslupln´ y. V´ ysledek shlukov´an´ı je spr´ avn´ y, platn´ y, kdyˇz se nem˚ uˇze vyskytovat n´ahodnˇe nebo v z´avislosti na nˇejak´em konkr´etn´ım shlukov´em algoritmu. Pro statistick´e postupy existuj´ı tˇri typy validaˇcn´ıch metod: ˆ Extern´ı zhodnocen´ı spr´ avnosti porovn´av´a vzniklou strukturu s poˇzadavky. ˆ Intern´ı zkouˇska spr´ avnosti se snaˇz´ı rozhodnout, zda je struktura skuteˇcnˇe vhodn´ a pro dan´ a data.

51

ˆ Relativn´ı test porovn´ av´a dvˇe struktury a mˇeˇr´ı jejich relativn´ı hodnotu.

5.3

R˚ uzn´ e druhy shluk˚ u

Shlukov´ an´ı se zamˇeˇruje na nalezen´ı uˇziteˇcn´ ych skupin vzork˚ u - shluk˚ u, kdy je uˇziteˇcnost definov´ ana c´ıly datov´e anal´ yzy. Existuje nˇekolik rozd´ıln´ ych pojm˚ u pro shluky ukazuj´ıc´ı se uˇziteˇcn´e v praxi. Aby mohly b´ yt vizu´alnˇe ilustrov´any rozd´ıly mezi r˚ uzn´ ymi druhy shluk˚ u, pouˇz´ıv´ame dvourozmˇern´e soustavy, napˇr. na obr´ azku 34. Nicm´enˇe je d˚ uleˇzit´e zd˚ uraznit, ˇze druhy a vlastnosti shluk˚ u, kter´e jsou zde pops´ any, jsou stejnˇe tak platn´e i pro jin´e druhy dat.

b) Zalozene na modelu

a) Presne vymezene shluky

11 00 00 11 c) Zalozene na blizkosti

11 00 00 11

d) Zalozene na hustote

111111 000000 000000 111111 000000 111111 000000 111111

11 00 0000000 1111111 00 11 0000000 1111111 00 11 0000000 1111111 00 11 0000000 1111111

e) Konceptualni shluky

Obr´ azek 34: R˚ uzn´e typy shluk˚ u ilustrovan´e pomoc´ı dvourozmˇern´eho prostoru Existuje nˇekolik moˇzn´ ych pohled˚ u, jak shluky rozdˇelit. Pro naˇse u ´ˇcely, tedy pro dopravn´ı problematiku, jsou z´akladem shluky zaloˇzen´e na modelu. Shlukem je zde mnoˇzina bod˚ u generovan´ ych stejn´ ym modelem. Pˇ resnˇ e vymezen´ e shluky Shluk je skupina vzork˚ u, ve kter´e jsou si vzorky vz´ajemnˇe v´ıce podobn´e (m´enˇe vzd´ alen´e) neˇz s vzorky jin´ ych shluk˚ u. Shluky jsou ohraniˇceny a nˇekdy je zvykem specifikovat hranici tak, ˇze vˇsechny vzorky ve shluku si mus´ı b´ yt dostateˇcnˇe podobn´e (bl´ızk´e) navz´ ajem. Tato “idealistick´a” definice shluku je uspokojuj´ıc´ı pouze tehdy, kdyˇz data obsahuj´ı pˇrirozen´e, p˚ uvodn´ı shluky, kter´e jsou dosti vzd´ alen´e od sebe navz´ ajem. V ˇc´ asti a) obr´ azku 34 je pˇr´ıklad pˇresnˇe vymezen´ ych shluk˚ u, kter´e se skl´adaj´ı ze dvou skupin bod˚ u ve dvourozmˇern´em prostoru. Vzd´alenost mezi kaˇzd´ ymi 52

dvˇema body v r˚ uzn´ ych skupin´ach je vˇetˇs´ı neˇz vzd´alenost mezi dvˇema body ve skupinˇe. Pˇresnˇe vymezen´e shluky nemus´ı b´ yt kulovit´e, ale mohou m´ıt jak´ ykoliv tvar. Shluky zaloˇ zen´ e na modelu Shluk je soustava vzork˚ u, ve kter´e jsou vzorky generov´any sp´ıˇse jedn´ım modelem neˇz ostatn´ımi. Pro data se spojit´ ym pr˚ ubˇehem je ˇcasto modelem shluku jeho tˇeˇziˇstˇe (pr˚ umˇer vˇsech bod˚ u ve shluku). Kdyˇz nelze tˇeˇziˇstˇe smysluplnˇe vypoˇc´ıtat, napˇr. jsou-li data kategorick´a, je ˇcasto modelem medoid, coˇz je nejreprezentativnˇejˇs´ı prvek shluku. Pro mnoho druh˚ u dat m˚ uˇze b´ yt model definov´an nejv´ıce stˇredov´ ym prvkem. V takov´ ych pˇr´ıpadech hovoˇr´ıme o shluc´ıch zaloˇzen´ ych na centru. Takov´e shluky maj´ı sklon b´ yt kulovit´e. Obr´azek 34 b) ukazuje pˇr´ıklad pr´ avˇe takov´ ychto centr´ aln´ıch shluk˚ u. Shluky zaloˇ zen´ e na grafech Pokud jsou data reprezentov´ana pomoc´ı grafu, kde jsou uzly na nejniˇzˇs´ı u ´rovni vzorky a hrany reprezentuj´ı spojen´ı mezi vzorky, pak m˚ uˇze b´ yt shluk definov´an jako spojuj´ıc´ı sloˇzka - skupina vzork˚ u, kter´e jsou spojen´e mezi sebou navz´ajem a kde nen´ı ˇz´ adn´e spojen´ı s vzorky mimo skupinu. D˚ uleˇzit´ y pˇr´ıklad shluk˚ u zaloˇzen´ ych na grafech jsou bl´ızk´e (souvisl´e) shluky – dva vzorky jsou spojen´e pouze tehdy, kdyˇz se nach´azej´ı do specifikovan´e vzd´alenosti mezi sebou. Kaˇzd´ y vzorek v bl´ızk´em shluku je bl´ıˇze k dalˇs´ım vzork˚ um ve shluku neˇz k jak´emukoli vzorku v klastru jin´em. Obr´azek 34 c) ukazuje pˇr´ıklad takov´ ychto shluk˚ u pro dvourozmˇern´ y prostor. Tato definice shluku je uˇziteˇcn´a, kdyˇz jsou shluky nerovnomˇern´e nebo propleten´e, pˇriˇcemˇz mohou nastat probl´emy, kdyˇz je pˇr´ıtomen ˇsum (jako v naˇsem pˇr´ıpadˇe) – mal´ y most prvk˚ u m˚ uˇze splynout do dvou rozd´ıln´ ych shluk˚ u. Jin´e typy shluk˚ u, kter´e jsou zaloˇzen´e na grafech, jsou tak´e moˇzn´e. Jeden takov´ y pˇr´ıstup definuje shluk jako z´ajmovou skupinu – soustava vrchol˚ u v grafu, kter´e jsou u ´plnˇe propojeny navz´ ajem. Pokud pˇrid´ame spojen´ı mezi vzorky v poˇrad´ı dle jejich vzd´ alenosti mezi sebou sam´ ymi, je shluk vytvoˇren, kdyˇz soustava dat vytv´ aˇr´ı z´ ajmovou skupinu. Tyto shluky tak´e inklinuj´ı k tomu m´ıt kulov´ y tvar. Shluky zaloˇ zen´ e na hustotˇ e ˇ ast Shluk je hust´ a oblast vzork˚ u, kter´a je obklopena oblast´ı s hustotou niˇzˇs´ı. C´ obr´ azku 34 d) ukazuje takov´eto shluky pro data z c), do kter´ ych jsou pˇrid´any sloˇzky ˇsumu. Tyto dva kruhovit´e shluky nespl´ yvaj´ı jako v podobr´azku c), protoˇze se most mezi nimi zvolna mˇen´ı v ˇsum. Podobnˇe ohyb na podobr´azku c) se zvolna st´ av´ a ˇsumem a netvoˇr´ı shluk na podobr´azku d). Definice shluku pomoc´ı hustoty se vˇetˇsinou pouˇz´ıv´a, kdyˇz jsou shluky nepravideln´e, propleten´e nebo pokud je pˇr´ıtomen ˇsum a outlieˇri.

53

Konceptu´ aln´ı shluky Obecnˇe m˚ uˇzeme shluk pojmout jako skupinu vzork˚ u, kter´e sd´ılej´ı nˇejakou oblast. Tato definice vesmˇes zahrnuje vˇsechny definice pˇredeˇsl´e – napˇr. vzorky ve shluku definovan´em dle modelu sd´ılej´ı oblast, kter´a je kolem tˇeˇziˇstˇe. Nicm´enˇe tato definice obsahuje tak´e nov´e typy shluk˚ u – uvaˇzujme shluky na podobr´azku 34 e). Troj´ uheln´ıkov´ a oblast – shluk je sousedn´ı oblast´ı obd´eln´ıkov´eho tvaru a d´ ale je tam oblast kruhov´eho tvaru. V obou pˇr´ıpadech by shlukov´e algoritmy potˇrebovaly velmi specifick´ y koncept shluku, aby doˇslo k u ´spˇeˇsn´emu urˇcen´ı tˇechto shluk˚ u.

5.4

Mˇ eˇ ren´ı podobnosti

Ponˇevadˇz je podobnost z´ asadn´ım pojmem jak v samotn´e shlukov´e anal´ yze, tak v definici shluku, jej´ı mˇeˇren´ı mezi dvˇema vzorky ze stejn´eho v´ ychoz´ıho prostoru je d˚ uleˇzit´e pro vˇetˇsinu shlukov´ ych algoritm˚ u. Kv˚ uli velk´e rozmanitosti z´akladn´ıch typ˚ u a mˇer, mus´ı b´ yt mˇeˇren´ı vzd´alenosti zvoleno velmi opatrnˇe. Nejbˇeˇznˇejˇs´ım zp˚ usobem pro v´ ypoˇcet m´ıry podobnosti mezi vzorky, nebo sp´ıˇse pro mˇeˇren´ı nepodobnosti - resp. vzd´ alenosti, je pouˇzit´ı metriky. V matematice je metrika (neboli funkce vzd´alenosti) funkce, kter´a definuje vzd´ alenost mezi elementy urˇcit´e mnoˇziny. Tato funkce vzd´alenosti se ˇcasto v matematice oznaˇcuje ρ. Mnoˇzina s metrikou se naz´ yv´a metrick´ y prostor. Metrika vytv´ aˇr´ı urˇcitou topologii na mnoˇzinˇe, coˇz vˇsak neplat´ı i v opaˇcn´em pˇr´ıpadˇe – ne vˇsechny topologie mohou b´ yt vytvoˇreny metrikou. Pokud m´a topologick´ y prostor topologii, kter´ a je pops´ana pomoc´ı metriky, je dan´ y prostor metrizovateln´ y. V geometrii je slovo metrika takt´eˇz pouˇz´ıv´ano jako struktura definov´ana jen ve vektorov´em prostoru, kter´ y je spr´avnˇeji oznaˇcen jako metrick´ y tenzor. Pro metriku jako funkci vzd´alenosti plat´ı n´asleduj´ıc´ı axiomy: ˆ axiom nez´ apornosti :

ρ(x, y) ≥ 0 ˆ axiom totoˇznosti (jedn´ a – li se o funkci vzd´alenosti spojuj´ıc´ı prvek se sebou sam´ ym) : ρ(x, y) = 0 ⇔ x = y ˆ axiom symetrie :

ρ(x, y) = ρ(y, x) ˆ troj´ uheln´ıkov´ a nerovnost :

ρ(x, z) ≤ ρ(x, y) + ρ(y, z)

54

Existuje nˇekolik zp˚ usob˚ u jak vyj´adˇrit axiomy metrik a jak d´at vzniknout r˚ uzn´ ym pojm˚ um obecn´ ych metrick´ ych prostor˚ u. Tato zobecnˇen´ı mohou b´ yt kombinov´ana. Terminologie pouˇzit´ a pro jejich popis nen´ı kompletnˇe standardizov´ana. Zejm´ena ve funkcion´ aln´ı anal´ yze ˇcasto pseudometrika poch´az´ı z norm´aln´ıho vektorov´eho prostoru. Rozˇ s´ıˇ ren´ a vs. koneˇ cn´ a metrika Nˇekteˇr´ı autoˇri povoluj´ı, aby vzd´alenost dosahovala hodnoty nekoneˇcna, to znamen´ a, ˇze vzd´ alenosti jsou nez´aporn´a ˇc´ısla na rozˇs´ıˇren´e ˇc´ıseln´e ose. Takov´a funkce se naz´ yv´ a rozˇs´ıˇren´ a metrika. V dopravˇe se sp´ıˇse setk´ av´ ame s metrikou koneˇcnou - napˇr. d´elka kolony, resp. poˇcet aut v n´ı, je koneˇcn´e ˇc´ıslo, d´ale pak charakteristiky jako intenzita, ˇci hustota. Minkowsk´ eho (Eukleidovsk´ a) metrika Nejzn´ amˇejˇs´ı metrika pro spojit´a data je Eukleidovsk´a vzd´alenost, kter´a je speci´aln´ım pˇr´ıpadem Minkowsk´eho metriky. Eukleidovsk´a vzd´alenost se bˇeˇznˇe pouˇz´ıv´a pro zhodnocen´ı bl´ızkosti vzork˚ u ve dvou – nebo tˇr´ı-rozmˇern´em prostoru. Nev´ yhodou pˇr´ım´eho pouˇzit´ı Minkowsk´eho metriky je tendence vˇetˇs´ıch vzork˚ u dominovat ˇ sen´ı tohoto probl´emu zahrnuje normalizaci spojit´ ostatn´ım. Reˇ ych pr˚ ubˇeh˚ u. Minkovsk´eho metriku lze obecnˇe vyj´adˇrit pomoc´ı vztahu (6). d X

1

|xi,k − xj,k |p ) p

(6)

v u d uX d2 (xi , xj ) = t (xi,k − xj,k )2

(7)

dp (xi , xj ) = (

k=1

k=1

Pokud za p dosad´ıme ˇc´ıslo 1, v´ ysledkem bude metrika Manhattan, kter´a se v dopravn´ı problematice vyskytuje pomˇernˇe ˇcasto. Pouˇzijeme ji napˇr´ıklad, pokud chceme urˇcit vzd´ alenost mezi dvˇema m´ısty ve mˇestˇe za podm´ınky, ˇze se mus´ıme pohybovat pouze v na sobˇe kolm´ ych bloc´ıch. Situace je zobrazena na obr´azku 35. Na tomto obr´ azku je vzd´alenost mezi body A a B rovna 22. Vˇsimnˇeme si, ˇze vzd´ alenost je stejn´ a pro vˇsechny zvolen´e trasy - ˇcerven´a, ˇzlut´a i modr´a. Je tedy jedno, kudy cestu vol´ıme, coˇz je v´ yhoda metriky Manhattan. Pokud za p dosad´ıme ˇc´ıslo 2, v´ ysledkem bude Eukleidovsk´a (viz vztah (7)), kter´ a se pouˇz´ıv´ a nejen v dopravˇe nejv´ıce. Lze ji pouˇz´ıt napˇr´ıklad opˇet v pˇr´ıpadˇe urˇcov´ an´ı vzd´ alenosti mezi dvˇema m´ısty ve mˇestˇe, pokud vˇsak cesty ve mˇestˇe nejsou uspoˇr´ ad´ any do pravideln´e mˇr´ıˇzky na sebe kolm´ ych ulic. Na obr´azku 36 lze vidˇet velikost Eukleidovsk´e vzd´alenosti. Pro lepˇs´ı srovn´an´ı tˇechto dvou metrik byla zachov´ ana p˚ uvodn´ı mˇr´ıˇzka ulic.

55

B

A Obr´ azek 35: Uk´azka pouˇzit´ı metriky Manhattan

B

A Obr´ azek 36: Uk´azka pouˇzit´ı Eukleidovsk´e metriky Mahalanobisova metrika Line´ arn´ı korelace m˚ uˇze zdeformovat mˇeˇren´ı vzd´alenosti – tato deformace m˚ uˇze b´ yt zavedena pouˇzit´ım ˇctvercov´e Mahalanobisovy vzd´alenosti. Mahalanobisovu vzd´ alenost lze vyj´ adˇrit pomoc´ı vztahu (8). dM (xi , xj ) = (xi − xj )C −1 (xi, xj )(xi − xj )T , kde

(8)

xi|j - pˇredstavuj´ı ˇr´ adkov´e vektory C - je kovarianˇcn´ı matice vzork˚ u dM - oznaˇcuje r˚ uzn´e v´ ahy pro rozd´ıln´e atributy, kter´e jsou zaloˇzen´e na sv´ ych odchylk´ ach a na line´ arn´ıch korelac´ıch. Implicitnˇe se pˇredpokl´ ad´ a, ˇze hustoty maj´ı Gaussovo rozloˇzen´ı pravdˇepodobnosti. Nˇekter´e shlukov´e algoritmy pracuj´ı s maticemi vzd´alenost´ı nam´ısto s p˚ uvodn´ı mnoˇzinou vzork˚ u. Je uˇziteˇcn´e v takov´ ychto situac´ıch pˇrepoˇc´ıtat vˇsechny n(n − 1)/2 hodnoty vzd´ alenost´ı pro n vzork˚ u a uloˇzit jej do symetrick´e matice. V´ ypoˇcet vzd´ alenost´ı mezi vzorky s nˇejak´ ymi nebo vˇsemi atributy, kter´e nejsou spojit´e, je problematick´e, protoˇze r˚ uzn´e typy atribut˚ u nemus´ı b´ yt porovnateln´e. 56

Mˇ eˇ ren´ı vzd´ alenosti na z´ akladˇ e kontextu (MND) Existuje nˇekolik metod mˇeˇren´ı vzd´alenosti, kter´e berou v u ´vahu i vliv okoln´ıch sousedn´ıch bod˚ u. Tyto body se naz´ yvaj´ı kontext. Podobnost mezi dvˇema body xi a xj dan´e kontextem je pops´ano vztahem (9), kde ξ je zm´ınˇen´ ym kontextem (soustava okoln´ıch bod˚ u). s(xi , xj ) = f (xi , xj , ξ)

(9)

Jednou z metrik pouˇz´ıvaj´ıc´ıch kontext je vzd´alenost spoleˇcn´eho sousedstv´ı, kter´a je bˇeˇznˇe oznaˇcov´ ana jako MND (mutual neighbor distance) a kter´a je dan´a vztahem (10), kde N N (xi , xj ) je ˇc´ıslo souseda xj vzhledem k xi . M N D(xi , xj ) = N N (xi , xj ) + N N (xj , xi ) y

(10)

y C

C

B

B

A

D

A

E F

x Podobnost vzorku A a B vetsi nez B a C

x Po zmene kontextu je podobnost B a C vetsi nez B a A

Obr´azek 37: Vzd´alenost MND V lev´e ˇca ´sti jsou si vzorky A a B v´ıce podobn´e (m´enˇe vzd´ alen´e) neˇz vzorky A a C, kdeˇzto v prav´e ˇca ´sti po zmˇenˇe kontextu jsou si v´ıce podobn´e vzorky B a C neˇz B a A.

Obr´ azek 37 je n´ azorn´ ym pˇr´ıkladem. V lev´e ˇc´ asti je nejbliˇzˇs´ım sousedem A vzorek B, coˇz plat´ı i obr´acenˇe, tedy nejbliˇzˇs´ım sousedem B je A, takˇze plat´ı : N N (A, B) = N N (B, A) = 1 a M N D mezi A a B je 2. D´ ale plat´ı : N N (B, C) = 1, ale N N (C, B) = 2, z ˇcehoˇz plyne M N D(B, C) = 3. Prav´a ˇc´ast je poˇr´ızena z lev´e pˇrid´ an´ım 3 nov´ ych bod˚ u D, E a F. Nyn´ı plat´ı M N D(B, C) = 3 a M N D(A, B) = 5. Vzd´ alenost mezi A a B vzrostla d´ıky pˇrid´an´ı dodateˇcn´ ych bod˚ u, i kdyˇz samotn´e body A a B z˚ ustaly na m´ıstˇe. MND vzd´ alenost nen´ı metrick´a, protoˇze nesplˇ nuje z´akladn´ı axiom, a to troj´ uheln´ıkovou nerovnost. Nehledˇe na to byla MND u ´spˇeˇsnˇe uplatnˇena v nˇekolika shlukov´ ych aplikac´ıch. Tento fakt podporuje hledisko, ˇze nepodobnosti (vzd´alenosti) nemus´ı b´ yt striktnˇe metrick´e. 57

ˆ Watanab˚ uv teor´em o oˇskliv´em kaˇc´atku : Pokud pouˇzijeme koneˇcnou mnoˇzinu ” atribut˚ u, kter´e jsou schopn´e rozliˇsit kaˇzd´e dva uvaˇzovan´e vzorky, poˇcet atribut˚ u, kter´e sd´ılej´ı pr´ avˇe ony dva vzorky, je konstantn´ı a nez´ avisl´y na v´ybˇeru vzork˚ u.“

Z tohoto teor´emu vypl´ yv´ a, ˇze je moˇzn´e vytvoˇrit libovoln´e dva stejnˇe podobn´e vzorky d´ıky zak´ odov´ an´ı jich pomoc´ı dostateˇcnˇe velk´eho poˇctu atribut˚ u. V d˚ usledku toho jsou dva libovoln´e vzorky stejn´e (pokud tedy nepouˇzijeme dodateˇcnou informaci o oblasti). Metrika zaloˇ zen´ a na konceptu´ aln´ıch shluc´ıch V pˇr´ıpadˇe konceptu´ aln´ıho shlukov´an´ı je definov´ana podobnost mezi xi a xj n´ asledovnˇe : s(xi , xj ) = f (xi , xj , ϕ, ξ), (11) kde φ je mnoˇzina pˇredem definovan´ ych koncept˚ u. Situace je ilustrov´ana pomoc´ı obr´ azku 38. x x

x x

x

x

C

x x x

x x

y

x

B

x x x x x x x x x x

x

x

x x

A x x x x x x x x x x x x x

Obr´ azek 38: Konceptu´aln´ı podobnost mezi vzorky Zde je Eukleidovsk´ a vzd´ alenost mezi A a B menˇs´ı neˇz mezi body B a C. Nicm´enˇe na body B a C m˚ uˇze b´ yt nahl´ıˇzeno jako na sobˇe si podobnˇejˇs´ı neˇz A a B, protoˇze B a C patˇr´ı do stejn´e ˇc´asti konceptu (elipsy) a A je souˇc´ast´ı jin´eho - obd´eln´ıku. Konceptu´ aln´ı mˇeˇren´ı podobnosti patˇr´ı mezi nejobecnˇejˇs´ı zp˚ usob mˇeˇren´ı podobnosti. Divergence Kullback-Leibler V teorii pravdˇepodobnosti a v informaˇcn´ı teorii se vyuˇz´ıv´a zejm´ena divergence Kullback-Leibler (oznaˇcov´ ana KL). Nejedn´a se pˇr´ımo o metriku, protoˇze nesplˇ nuje jeden ze z´ akladn´ıch axiom˚ u platn´ ych pro metriky, a to axiom symetrie. Obecnˇe je to nesymetrick´e mˇeˇren´ı rozd´ılnosti mezi dvˇema pravdˇepodobnostn´ımi rozdˇelen´ımi P a Q. P vˇetˇsinou reprezentuje re´alnou distribuci dat, mˇeˇren´ı nebo

58

vypoˇctenou teoretickou distribuci - tedy zn´amou funkci f . Naopak Q charakteristicky pˇredstavuje nˇejakou teorii, model, popis, nebo aproximaci rozdˇelen´ı P - ˇcili hledanou funkci f˜. KL divergence je zvl´ aˇstn´ı pˇr´ıpad ˇsirˇs´ı skupiny odchylek, kter´e se naz´ yvaj´ı f - odchylky. P˚ uvodnˇe byly pˇredstaveny Solomen Kullbackem a Richardem Leiblerem v 1951 jako usmˇernˇen´e odchylky mezi dvˇema distribucemi. ˆ Definice : Pro pravdˇepodobnostn´ı rozdˇelen´ı f a f˜ diskr´etn´ı, ˇci spojit´e n´ ahodn´e veliˇciny se spoleˇcn´ ym suportem je KL vzd´alenost definov´ana n´ asledovnˇe :

ˆR

f (x) dx f˜(x) i (12) Pozn. : KL vzd´ alenost je definov´ana jen tehdy, pokud je f > 0 a f˜ > 0 pro vˇsechny hodnoty i a pokud f a f˜ daj´ı po sumaci 1. DKL (f || f˜) =

X

f (i) , resp. DKL (f || f˜) = f (i)log f˜(i)

f (x)log

ˆ Vztah k metrice : Kullback-Leibler vztahy jsou takt´eˇz ˇrazeny do metrick´ ych vzd´ alenost´ı v oblasti pravdˇepodobnostn´ıch rozdˇelen´ı, ale toto tvrzen´ı nen´ı u ´plnˇe korektn´ı, protoˇze KL odchylka nen´ı symetrick´a. D˚ ukazem je nesplnˇen´ı troj´ uheln´ıkov´e nerovnosti a neplatnost vˇety o symetriˇcnosti, protoˇze vzd´ alenost KL z f dof˜ nemus´ı b´ yt stejnˇe velk´a jako KL z f˜ do f .

DKL (f || f˜) 6= DKL (f˜ || f ) I navzdory tˇemto fakt˚ um generuje KL topologii v oblasti obecn´ ych pravdˇepodobnostn´ıch rozdˇelen´ı. Konkr´etnˇeji ˇreˇceno – jestliˇze m´ame posloupnost rozdˇelen´ı f1 , ..., fn takovou, ˇze plat´ı limn→∞ DKL (fn ||f˜) = 0 , pak fn → f˜.

5.5

R˚ uzn´ e druhy shlukov´ an´ı

Jak´ekoliv seskupen´ı vzork˚ u je bˇeˇznˇe naz´ yv´ano jako shlukov´an´ı a v t´eto ˇc´asti budeme rozliˇsovat jeho r˚ uzn´e druhy. Hierarchick´ e a nehierarchick´ e shlukov´ an´ı Z´ akladn´ım rozdˇelen´ım shlukov´ ych technik je hierarchick´e a nehierarchick´e. Nehierarchick´e shlukov´ an´ı je jednoduˇse rozdˇelen´ı mnoˇziny vzork˚ u do nepˇrekr´ yvaj´ıc´ıch se disjunktn´ıch podmnoˇzin – shluk˚ u tak, ˇze kaˇzd´ y vzorek n´aleˇz´ı pr´avˇe jedn´e podmnoˇzinˇe. Pokud pˇripust´ıme fakt, ˇze shluky mohou m´ıt podshluky a ˇze existuje vztah nadˇrazenosti a podˇrazenosti, hovoˇr´ıme o hierarchick´em shlukov´an´ı. Jedn´a se o mnoˇzinu vkl´ adan´ ych shluk˚ u, kter´e jsou organizov´any jako strom. Kaˇzd´ y uzel (shluk) stromu (kromˇe koncov´ ych uzl˚ u) je sjednocen´ı podˇrazen´ ych podmnoˇzin, 59

a tud´ıˇz je koˇren stromu shluk obsahuj´ıc´ı vˇsechny vzorky. Velmi ˇcasto jsou listy mnoˇziny s jedin´ ym prvkem, tedy samotn´e vzorky. Hierarchick´e shlukov´ an´ı se d´ ale m˚ uˇze dˇelit na aglomerativn´ı a divizivn´ı. Dˇelen´ı z tohoto hlediska souvis´ı s algoritmickou strukturou. Aglomerativn´ı pˇr´ıstup zaˇc´ın´a s kaˇzd´ ym vzorkem jako se samostatn´ ym shlukem a postupnˇe spojuje vzorky (shluky) dohromady do t´e doby, neˇz je splnˇeno pˇredem stanoven´e krit´erium (napˇr. to m˚ uˇze b´ yt poˇzadovan´ y poˇcet shluk˚ u). Narozd´ıl od tohoto postupu zaˇc´ın´ a divizivn´ı shlukov´ an´ı s jedn´ım shlukem, kter´ y obsahuje veˇsker´e vzorky v dan´e mnoˇzinˇe a postupnˇe jej rozˇcleˇ nuje do menˇs´ıch podmnoˇzin, aˇz je opˇet naplnˇeno pˇredem dan´e krit´erium. Vyluˇ cuj´ıc´ı, pˇ rekr´ yvaj´ıc´ı a fuzzy shlukov´ an´ı Shlukov´ an´ı demonstrov´ ana na obr´azku 32 jsou vˇsechna vyluˇcuj´ıc´ı, protoˇze pˇriˇrazuj´ı kaˇzd´ y vzorek do jedin´eho shluku. Existuje mnoho situac´ı, v nichˇz m˚ uˇze b´ yt vzorek pˇrijatelnˇe um´ıstˇen do v´ıce neˇz jednoho shluku. Tyto situace jsou pˇripisov´any tzv. pˇrekr´ yvaj´ıc´ımu se (nev´ yluˇcn´emu) shlukov´ an´ı. V nejobecnˇejˇs´ım slova smyslu pˇrekr´ yvaj´ıc´ı se shlukov´an´ı je pouˇz´ıv´ano k vyj´ adˇren´ı skuteˇcnosti, ˇze vzorek m˚ uˇze souˇcasnˇe patˇrit do v´ıce neˇz jedn´e skupiny. Pˇr´ıkladem m˚ uˇze b´ yt student na vysok´e ˇskole, kter´ y je zde veden jako student a z´ aroveˇ n je tak´e zamˇestnancem ˇskoly. Pˇrekr´ yvaj´ıc´ı shlukov´an´ı je tedy zˇrejmˇe ˇcasto pouˇz´ıv´ ano, pokud je vzorek mezi dvˇema nebo v´ıce skupinami a pokud nem˚ uˇze b´ yt striktnˇe pˇriˇrazen pr´avˇe do jednoho shluku. Pokud se bl´ıˇze pod´ıv´ ame na bod nach´azej´ıc´ı se na obr´azku 32 pˇr´ımo mezi dvˇema shluky, uvid´ıme, ˇze sp´ıˇse neˇz libovoln´e pˇriˇrazen´ı vzorku do jedin´eho shluku, je bod pˇriˇrazen do vˇsech shluk˚ u pˇrich´azej´ıc´ıch stejnou mˇerou v u ´vahu. Ve fuzzy shlukov´ an´ı obsahuje kaˇzd´ y vzorek funkci pˇr´ısluˇsnosti, kter´a ˇr´ık´a, jakou mˇerou patˇr´ı dan´ y vzorek do jednotliv´eho klastru. Funkce pˇr´ısluˇsnosti nab´ yv´a hodnot < 0; 1 >, 0 - nepatˇr´ı a 1 - absolutnˇe patˇr´ı. ´ Upln´ eaˇ c´ asteˇ cn´ e shlukov´ an´ı ´ Upln´ e shlukov´ an´ı pˇriˇrazuje kaˇzd´ y vzorek do shluku, pˇriˇcemˇz ˇc´asteˇcn´e nikoliv. V ˇc´ asteˇcn´em shlukov´ an´ı nˇekter´e vzorky z mnoˇziny dat nemus´ı patˇrit do pˇresnˇe stanoven´ ych skupin. Mnohdy reprezentuj´ı takov´eto vzorky z mnoˇziny dat ˇsum, outliery nebo pozad´ı, kter´e nen´ı d˚ uleˇzit´e, proto je v´ yhodn´e takov´eto vzorky v˚ ubec neuvaˇzovat. Monot´ etick´ e a polyt´ etick´ e shlukov´ an´ı Tento u ´hel pohledu bere v u ´vahu uˇzit´ı atribut˚ u v procesu shlukov´an´ı bud’ jako n´ asledn´e (postupn´e) nebo soubˇeˇzn´e. Vˇetˇsina algoritm˚ u je polyt´etick´a, coˇz znamen´ a, ˇze vˇsechny atributy vstupuj´ı do v´ ypoˇctu podobnosti (resp. vzd´alenost´ı) mezi vzorky a n´ asledn´e z´ avˇery jsou dˇel´any na z´akladˇe tˇechto podobnost´ı (resp.vzd´alenost´ı).

60

V

x2

2 2

2

2 2 2 2 2

2

2

2

3 3

H1 1 1

1 1 1 1 1 1 1 1 1 1 1

3

3 3 3

3 3

3 3

3

4 1 4

1

4 4 4 4 4 4 4

H2 4

x1

Obr´ azek 39: Monot´etick´e shlukov´an´ı Monot´etick´e shlukov´ an´ı uvaˇzuje kaˇzd´ y atribut zvl´aˇst’ pˇri rozdˇelov´an´ı cel´e mnoˇziny vzork˚ u. Na obr´ azku 39 je uk´az´ano monot´etick´e shlukov´an´ı, kdy je soubor dat rozdˇelen do dvou skupin na z´akladˇe vlastnosti x1. Vertik´aln´ı lomen´a ˇc´ara V je rozdˇeluj´ıc´ı ˇcarou v˚ uˇci atributu x1. Kaˇzd´ y z tˇechto shluk˚ u je d´ale samostatnˇe rozdˇelen za pouˇzit´ı vlastnosti x2, jak je vyobrazeno pomoc´ı lomen´ ych ˇcar H1 a H2. Hlavn´ım probl´emem tohoto postupu je, ˇze generuje 2d shluk˚ u, kde d je dimenze datov´eho vektoru. Pro velk´e hodnoty d (d > 100) je poˇcet shluk˚ u vygenerovan´ ych t´ımto algoritmem tak velik´ y, ˇze mnoˇzina dat mus´ı b´ yt rozdˇelena do nezaj´ımavˇe mal´ ych shluk˚ u. Deterministick´ e a stochastick´ e shlukov´ an´ı Toto dˇelen´ı je vˇetˇsinou v´ yznamn´e pro nehierarchick´e pˇr´ıstupy, kter´e jsou navrˇzen´e pro optimalizaci kvadratick´e chybov´e funkce. Tato optimalizace m˚ uˇze b´ yt provedena za pouˇzit´ı tradiˇcn´ıch technik nebo pomoc´ı n´ahodn´eho hled´an´ı ve stavov´em prostoru skl´ adaj´ıc´ım se ze vˇsech moˇzn´ ych znaˇcek. Deterministick´ y algoritmus je algoritmus, kter´ y na stejn´ y vstup (resp. na stejn´e v´ ychoz´ı podm´ınky) reaguje vˇzdy stejnˇe (tedy pˇredv´ıdatelnˇe) a v kaˇzd´em jeho kroku je vˇzdy jednoznaˇcnˇe definov´an i krok n´asleduj´ıc´ı. U stochastick´eho algoritmu nelze pˇredv´ıdat hodnotu v´ ystupu, protoˇze reakce syst´emu jsou n´ ahodn´e, resp. v jak´emkoli kroce nejsme schopni jednoznaˇcnˇe definovat n´ asleduj´ıc´ı krok. Shlukov´ an´ı po kroc´ıch Toto hledisko pˇripad´ avu ´vahu, pokud je datov´a mnoˇzina, kter´a m´a b´ yt rozdˇelena do shluk˚ u, velk´ a a pokud jsou poˇzadavky na proveden´ı shlukov´e anal´ yzy ohlednˇe ˇcasu a pamˇeti procesu omezeny. Shlukov´a anal´ yza nenab´ız´ı k nahl´ednut´ı mnoho algoritm˚ u shlukov´ an´ı, kter´e byly navrˇzeny pro pr´aci s velkou mnoˇzinou dat, ale v´ yvoj pr´ ace s daty podporuje v´ yvoj shlukov´ ych algoritm˚ u, kter´e minimalizuj´ı 61

poˇcet prohled´ avan´ ych vzork˚ u mnoˇziny, redukuj´ı poˇcet vzork˚ u prozkoum´avan´ ych bˇehem v´ ypoˇct˚ u nebo sniˇzuj´ı velikost datov´ ych struktur, kter´e jsou pouˇz´ıv´any ve shlukov´ ych algoritmech. shlukovani

nehierarchicke

hierarchicke

uplne

castecne

chyba ctvercu (SSE)

grafova reprezentace

smesi

Obr´ azek 40: Rozdˇelen´ı metod shlukov´an´ı

62

analyzy modu

Seznam obr´ azk˚ u 1

Bezpeˇcn´ a vs. nebezpeˇcn´a oblast dat . . . . . . . . . . . . . . . .

6

2

Uk´ azka pracovn´ıch m´od˚ u (shluk˚ u) . . . . . . . . . . . . . . . . .

7

3

Pouˇzit´ı Kmeans algoritmu k nalezen´ı tˇr´ı shluk˚ u . . . . . . . . . .

11

4

Tˇri optim´ aln´ı a suboptim´aln´ı shluky . . . . . . . . . . . . . . . . Dva p´ ary shluk˚ u s poˇc´ateˇcnˇe zvolen´ ymi dvˇema p´ary tˇeˇziˇst’ uvnitˇr jednoho p´ aru . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

6

Dva p´ ary shluk˚ u s jinak poˇc´ateˇcnˇe zvolen´ ymi tˇeˇziˇsti . . . . . . .

15

7

P˚ ulic´ı Kmeans na pˇr´ıkladu se ˇctyˇrmi shluky . . . . . . . . . . . .

19

8

R˚ uzn´e typy shluk˚ u a Kmeans . . . . . . . . . . . . . . . . . . . .

20

9

Nalezen´ı pˇrirozen´ ych shluk˚ u skl´adaj´ıc´ıch se ze subshluk˚ u . . . . .

21

10

R˚ uzn´e zobrazen´ı hierarchick´eho shlukov´an´ı . . . . . . . . . . . . .

22

11

Uk´ azka rozd´ılu pouˇzit´ı metody nejbliˇzˇs´ıho a nejvzd´alenˇejˇs´ıho souseda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

12

Techniky urˇcen´ı sousedstv´ı . . . . . . . . . . . . . . . . . . . . . .

24

13

Mnoˇzina 6 datov´ ych vzork˚ u . . . . . . . . . . . . . . . . . . . . .

25

14

Uk´ azka metody nejbliˇzˇs´ıho souseda (resp. MIN) . . . . . . . . . .

26

15

Uk´ azka metody nejvzd´alenˇejˇs´ıho souseda (resp. MAX) . . . . . .

28

16

Uk´ azka pouˇzit´ı pr˚ umˇeru skupiny . . . . . . . . . . . . . . . . . .

29

17

Centr´ aln´ı hustota . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

18

J´ adro oblasti, hranice oblasti a ˇsum ve dvourozmˇern´em prostoru

32

19

Vzorek dat a k-vzd´ alenost . . . . . . . . . . . . . . . . . . . . . .

34

20

Uk´ azka DBSCAN shlukov´an´ı . . . . . . . . . . . . . . . . . . . .

35

21

Uk´ azka pouˇzit´ı algoritmu Kmeans na nezaˇsumˇen´ ych datech . . .

37

22

Uk´ azka pouˇzit´ı algoritmu Kmeans na zaˇsumˇen´ ych datech . . . .

38

23

Uk´ azka pouˇzit´ı hierarchick´eho algoritmu na nezaˇsumˇen´ ych datech 39

24

Dendrogramy pro zaˇsumˇen´a data . . . . . . . . . . . . . . . . . .

39

25

Uk´ azka pouˇzit´ı algoritmu DBSCAN na nezaˇsumˇen´ ych datech a pˇri optim´ aln´ı volbˇe parametr˚ u. . . . . . . . . . . . . . . . . . . .

40

26

Srovn´ an´ı v´ ysledku shlukov´an´ı pomoc´ı algoritmu DBSCAN pˇri r˚ uzn´e volbˇe parametr˚ u . . . . . . . . . . . . . . . . . . . . . . . .

41

27

Re´ aln´ a data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

28

Pouˇzit´ı Kmeans na re´aln´ ych datech . . . . . . . . . . . . . . . . .

43

29

Pouˇzit´ı hierarchick´eho shlukov´an´ı na re´aln´ ych datech . . . . . . .

44

30

Nalezen´ı jednoho shluku za pouˇzit´ı DBSCANu na re´aln´ ych datech 44

31

Nalezen´ı v´ıce shluk˚ u za pouˇzit´ı DBSCANu na re´aln´ ych datech . .

45

32

R˚ uzn´e zp˚ usoby rozdˇelen´ı vzork˚ u do shluk˚ u. . . . . . . . . . . . .

48

5

63

14

33

F´ aze shlukov´ an´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

34

R˚ uzn´e typy shluk˚ u ilustrovan´e pomoc´ı dvourozmˇern´eho prostoru

52

35

Uk´ azka pouˇzit´ı metriky Manhattan . . . . . . . . . . . . . . . . .

56

36

Uk´ azka pouˇzit´ı Eukleidovsk´e metriky . . . . . . . . . . . . . . . .

56

37 38

Vzd´ alenost MND . . . . . . . . . . . . . . . . . . . . . . . . . . . Konceptu´ aln´ı podobnost mezi vzorky . . . . . . . . . . . . . . . .

57 58

39

Monot´etick´e shlukov´an´ı . . . . . . . . . . . . . . . . . . . . . . .

61

40

Rozdˇelen´ı metod shlukov´an´ı . . . . . . . . . . . . . . . . . . . . .

62

64

Seznam tabulek 1

Tabulka uˇzit´ ych symbol˚ u a jejich v´ yznam˚ u. . . . . . . . . . . . .

12

2

Vztah funkce vzd´ alenosti, tˇeˇziˇstˇe a u ´ˇcelov´e funkce . . . . . . . . .

13

3

Souˇradnice datov´ ych vzork˚ u . . . . . . . . . . . . . . . . . . . . .

25

4

Matice vzd´ alenost´ı (Eukleidovsk´e) . . . . . . . . . . . . . . . . .

26

5

Parametry L - W vztahu pro klasick´e hierarchick´e algoritmy . . .

30

6

V´ ysledky shlukov´ an´ı pomoc´ı algoritmu DBSCAN u r˚ uzn´ ych typ˚ u dat a pˇri r˚ uzn´ ych parametrech . . . . . . . . . . . . . . . . . . .

42

65