ˇ 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
Transcript
Ceske vysoke ucenı technicke
Fakulta Dopravnı
Ustav aplikovane matematiky
Czech Technical University in Prague
Faculty of Transportation Sciences
Department of Applied Matematics
Vyuzitı shlukove analyzy
v dopravnı problematice
The usage of cluster analysis in transport problems
Bakalarska prace
Skolitel: doc. Ing. Ivan Nagy, CSc.
Studijnı program: 3710 Technika a technologie v doprave a spojıch
Studijnı obor: 2612R004 Automatizace a informatika
Prague, 2011 Tereza Mlynarova
Podekovanı
Na tomto mıste bych rada podekovala vsem, kterı mi poskytli podklady provypracovanı teto prace. Zvlaste pak dekuji doc. Ing. Ivanu Nagymu, CSc. zaodborne vedenı a konzultovanı bakalarske prace a za rady, ktere mi poskytovalpo celou dobu meho studia.
Dale bych chtela podekovat pracovnıkum UTIA za umoznenı prıstupu k mnohadulezitym informacım a materialum. V neposlednı rade je mou milou povinnostıpodekovat sve rodine, prıteli a blızkym za moralnı a materialnı podporu, kterese mi dostavalo po celou dobu studia.
2
Prohlasenı
Predkladam tımto k obhajobe bakalarskou praci, zpracovanou na zaver ba-kalarskeho studia na CVUT v Praze na Fakulte dopravnı.
Prohlasuji, ze jsem predlozenou praci vypracovala samostatne a ze jsem uvedlaveskere pouzite informacnı zdroje v souladu s Metodickym pokynem o etickeprıprave vysokoskolskych zaverecnych pracı.
Nemam zavazny duvod proti uzitı tohoto dıla ve smyslu § 60 Zakona c.121/2000Sb., o pravu autorskem, o pravech souvisejıcıch s pravem autorskym a o zmenenekterych zakonu (autorsky zakon).
Predmetem bakalarske prace “Vyuzitı shlukove analyzy v dopravnı problema-tice” je porovnanı zakladnıch metod shlukove analyzy, uvedenı jejich vlastnostı,resp. silnych a slabych stranek, coz je prakticky ukazano na experimentech.Shlukove algoritmy jsou aplikovany nejprve na simulovana data a pak na datarealna, ktera byla zıskana z dopravnıho merenı. Shlukovanı lze povazovat zanedılnou soucast dopravnıch analyz.
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 datathat was obtained by a traffic measurement. It is possible to consider clusteringas the entire part of every traffic analysis.
Pokud si kdekoli do vyhledavace zadate “Definuj dopravu,”, vetsinou se ukazedefinice : “Doprava je zpusob pohybovanı se objektu z mısta na mısto. Jdeo premist’ovanı...”. Je vsak doopravdy pod pojmem Doprava schovano pouhepremist’ovanı?
Ano, drıve doprava znamenala pouhy presun z mısta na mısto. Jsou vsak prycdoby, kdy jsme mohli spocıtat auta na krizovatkach na prstech jedne ruky, kdybylo ropy takrka na rozdavanı, kdy jsme mohli vest nove pozemnı komunikacekdekoli a nezajımala nas otazka zaboru pudy, kdy hluk a zplodiny byly pouhepojmy ve slovnıku, atd. Ve vyctu vecı, ktere jsou jiz minulostı, bychom mohlipokracovat smele dale.
Prıtomnost s sebou nynı prinası uplne jiny nahled na dopravu. Slozite prepravnıvztahy, narustajıcı intenzity, automobilizace, delky kolon, dochazejıcı ropa ahledanı alternativnıch paliv, hluk prevysujıcı dovolene limity, narustajıcı urovennehodovosti, atd. Na druhou stranu nam nynı doprava umoznuje to, co bylo prednekolika desıtky let v pouhych predstavach a snech lidı. Cestovanı az na druhoustranu zemekoule za par hodin, schopnost prepravit temer libovolne mnozstvımaterialu a zbozı, integrace mestske hromadne dopravy, inovace dopravnıchprostredku, atd.
Nabızı se otazka - “Jde dnesnı vyvoj dopravnı techniky a dopravnıch technologiıspravnym smerem?” Samozrejme nelze na tuto otazku jednoduse odpovedet.Vse ma sve pozitivnı a negativnı stranky. Nasım ukolem vsak je eliminovatdusledky negativnıch vlivu a zamerit se na samotna pozitiva. Resenı problemuse ubıra tremi smery. Jinak receno zamerujeme se na zmınene problemy ze trechhledisek. Chceme, aby naklady spojene s dopravou byly co nejmensı, aby dopadna zivotnı prostredı byl co nejmene skodlivy a hlavne pozadujeme, aby pro nasdoprava byla prostredkem, ktery pro nas bude bezpecny. Nahlızıme tedy na vecz hledisek ekonomickych, ekologickych a bezpecnostnıch.
Situaci je mozno merenım ruznych velicin analyzovat pomocı dat, ktere sebe-reme na nami sledovanych objektech. Dıky sebranym datum se pohybujemev nekolika-dimenzionalnıch prostorech. Merenı v jednom casovem okamzikupredstavujı prave jeden bod v prostoru (pokud uvazujeme dve veliciny, pakhovorıme o rovine). Vypovıdacı schopnost dat muzeme demonstrovat na obrazku1 jako bezpecnou a nebezpecnou oblast dat.
Existujı ruzne metody, jak eliminovat problemy spojene s dopravou. Muzemezakonem navrhnout nejaka nova opatrenı, ci opravit stavajıcı, zvysit policejnıdohled na pozemnıch komunikacıch, ucinit stavebnı upravy ci zlepsit technikuv dopravnıch prostredcıch. V teto praci se poslednı zalezitostı budeme zabyvatblıze.
Zaujala me myslenka vylepsenı technickeho prostredı uvnitr automobilu pomocınoveho zarızenı - jakesi “krabicky”. Tato krabicka bude dodatecnym vybavenım,
6
Obrazek 1: Bezpecna vs. nebezpecna oblast datJsou zde zobrazena data z realne jızdy. Graf vyjadruje zavislost mezinatocenım volantu a rychlostı, tudız se pohybujeme ve dvourozmernem pro-storu (resp. v rovine).
Pokud budeme na obrazek nahlızet z bezpecnostnıho hlediska, tak namerena
data zobrazujı vesmes jızdu bezpecnou. Pokud se tedy nejake body objevı v
hornı casti obrazku a navıc smerem do stran, jedna se o jızdu nebezpecnou -
jedeme tedy rychle a jeste k tomu do zatacky.
jako je naprıklad navigace, vystrazne zarızenı ci parkovacı cidla. Tyto krabickybudou obsahovat programy, ktere budou hodnotit nasi jızdu, resp. styl nasehorızenı z vyse zmınenych trı hledisek. Bude tedy potreba merit data jak na aute,tak na samotnem ridici, nasledne tato data analyzovat a na zaklade analyzydat podat rady ridici ke zlepsenı jeho rızenı, ci ho varovat pred nebezpecnoujızdou. Pokud bychom se tedy v prıpade zobrazenem na obrazku 1 pohybovaliv nebezpecne oblasti dat - jeli bychom tedy prılis rychle do prudke zatacky,krabicka by nas upozornila a nase kroky by vedly prvne ke snızenı rychlosti av prıpade, ze jsme jiz za zatackou, ke srovnanı volantu. Tım bychom se dostalido bezpecnejsıho modu.
Jako matematicky nastroj bude pouzito klastrovanı a klasifikaci. Dıky klastrovanıse vytvorı model, klasifikacı bude pote reprezentovan. V praxi na ridice pusobıdesıtky (mnohdy az stovky) vlivu, ktere je pri rızenı prımo, ci neprımo ovlivnujı.Vysledkem techto vlivu pak je, ze se automobil i s ridicem pohybuje v urcitychoblastech (pracovnıch modech).
7
Pro lepsı nazornost, jak vypada slozitejsı soustava pracovnıch modu, resp. shlukudat na realne merenych datech, muzeme uvest jızdu automobilem, pri kteremerıme pridavanı plynu a rychlost. Tato data jsou vykreslena na obrazku 2.
Obrazek 2: Ukazka pracovnıch modu (shluku)Na obrazku jsou zobrazena realna data v dvourozmernem prostoru. Na ose x
je zobrazen plyn [%]. Na ose y rychlost [km/h].
Jiz pouhym okem a bez jakekoli predchozı informace jsme schopni analyzovatdanou situaci. Rekneme, ze jsou zde rozpoznatelne tri shluky, ktere predstavujırozjızdenı a jızdu mestem (hodnoty od malych rychlostı kolem 10 km/h do 50km/h s ruzne velkym plynem), jızdu mimo mesto (rychlosti kolem 90 km/h svyssımi hodnotami plynu nez v predchozım prıpade) a nakonec jızdu na dalnici(rychlost kolem 130 km/h s vyssı hodnotou plynu oproti predchozım prıpadum).Jak vsak striktne urcit prıslusnosti jednotlivych bodu k danym skupinam? To jeprave ukol shlukove analyzy - nalezenı modu bezpecnosti, resp. nebezpecnosti.
O pracovnıch modech tedy vypovıdajı data merena jak na aute, tak na ridici.Merena data hrajı v tomto prıpade klıcovou roli, a tak musıme dbat o jejichpeclivy vyber. Daty merenymi na automobilu mohou byt veliciny jako polohaautomobilu, ci volantu, plyn, brzda, rotace, prıcne zrychlenı, rychlosti jednot-livych kol, otacky motoru, moment motoru, apod. Daty merenymi na ridici jsounapr. pohyby vıcek, vyraz tvare, EEG, teplotnı mapa obliceje, unava, reakcnıdoba atd.
Jak je jiz videt, budeme se pohybovat v n - dimenzionalnım prostoru (n udavapocet merenych velicin). Data budou merena v diskretnım case, kdy v kazdemcase dostaneme datovy vektor (vektor namerenych hodnot). Tento vektor predsta-
8
vuje bod v datovem prostoru. Usporadame-li datove vektory od pocatku merenıaz do aktualnıho casu pod sebe, dostaneme datovou matici. V datove ma-tici muzeme nalezt radky se stejnymi (podobnymi) hodnotami, coz jsou modysystemu, neboli shluky. Jinymi slovy receno - pokud se tedy nektere situace(tj. datove vektory) opakujı jen s malymi odchylkami, vytvarı se skupiny bodu(shluky), ktere reprezentujı prave konkretnı pracovnı mody, at’ uz spatne (nezadou-cı), nebo dobre (zadoucı).
Konstrukce systemu ridic - automobil se da aplikovat na dve faze - na fazi ucenıa klasifikace.
� Ve fazi ucenı dochazı ke klastrovanı, tedy k detekci shluku v datech z ucıcı(trenovacı) mnoziny.
� Pri klasifikaci se zmereny datovy vektor se priradı do urciteho shluku a tımse detekuje aktualnı pracovnı mod a jeho ohodnocenı - v nasem prıpadeje to spatne, ci dobre rızenı.
Existuje nekolik metod klastrovanı (shlukovanı). Jakou metodu zvolıme, zalezızejmena na typu vstupnıch dat, ktere chceme analyzovat. Na vyber pritom mamez siroke skaly metod hierarchickych a nehierarchickych.
Dale jsou zde metody Bayesovske statistiky, ktere vytvarı modely smesi hustotpravdepodobnostı (hustoty se nazyvajı komponenty). Tato technika me velmizaujala, a tak bych se jı chtela delsı dobu venovat. Zamerım se vsak nynı nametody klasicke shlukove analyzy, kdy se jedna zejmena o statickou analyzudat. Duvodem je, abych byla pote schopna hledat klady a zapory metody Ba-yesovstvı, tedy klasifikace dynamicke v case.
1.2 Formulace ulohy
Cılem teto prace je vytvorenı prehledu o metodach shlukove analyzy, jejichzhodnocenı a vzajemne porovnanı. Hlavnım bodem bude prehled o existujıcıchshlukovych algoritmech. Tyto algoritmy budu nejprve teoreticky charakterizo-vat a nasledne na nich bude overeno vyuzitı pro nase moznosti, tedy moznostiklastrovanı dopravnıch dat. Na jednotlivych algoritmech budou provedeny expe-rimenty. Na zaklade vysledku budu ilustrovat vhodnost jejich pouzitı pro ruzneformy dat.
1.3 Definice a pojmy
� vzorek – je nezavisly druh dat, se kterym se pracuje u shlukovych algo-ritmu. Typicke je, ze se sklada z datoveho vektoru – vektoru merenychvelicin v case t.
� datova matice - je vysledkem vsech realizacı (vznikne poskladanım rea-lizacı datoveho vektoru do matice)
� sum – je nahodna slozka mereneho vzorku, ktera umoznuje vzniknoutvzhledem k nahodnosti sledovaneho procesu nebo jako chyba merenı.
� outlier – je vzorek dat, ktery je velmi vzdaleny od zbytku dat, a taknecharakterizuje jejich prirozenou strukturu. Vetsinou se jedna o sum.
� matice sousednosti - je ctvercova (pro neorientovane grafy i symetricka)matice grafu G, pro kterou platı vztah (1).
AG = (aij)ni,j=1 definovana predpisem : (1)
aij = 1 pro {vi,vj} ∈ E= 0 pro ostatnı prıpady (pokud neexistuje hrana mezi {vi,vj}).
v1, ..., vn oznacujı vrcholy daneho grafu G a E je mnozina hran.
10
2 Vybrane metody shlukove analyzy
Na shlukovanı, resp. shlukovou analyzu je mozne nahlızet z nekolika ruznychpohledu. Pokud resıme otazku, zda chceme mıt shluky hierarchicky usporadane,jinymi slovy chceme, aby mezi nimi platil vztah nadrazenosti a podrazenosti,volıme mezi hierarchickym a nehierarchickym shlukovanım. U hierarchickehoshlukovanı jeste rozlisujeme aglomerativnı a divizivnı prıstup (viz Prıloha 5.5).
Dale muzeme resit, zda jeden prvek lze priradit pouze do jednoho shluku, pakse jedna o shlukovanı vylucne, nebo do vıce shluku zaroven, pak hovorıme oprekryvajıcım se shlukovanı. Zvlastnım prıpadem prıslusnosti vzorku je fuzzyshlukovanı charakterizovano funkcı prıslusnosti. Zda dany shlukovy algoritmusuvazuje sum ci outliery, zodpovı otazka uplneho a castecneho shlukovanı. Dalsıdelenı shlukovanı je na deterministicke a stochasticke. Nicmene doprava je samao sobe stochasticky system, takze determinismus v tomto prıpade nebude vubecuvazovan. Zmınene delenı a blizsı popis jednotlivych technik je predstaven vPrıloze 5.5.
V teto casti budou po teoreticke strance predstaveny vybrane algoritmy shlu-kovanı, na kterych bude v casti testovanı provedeno nekolik experimentu jak nasimulovanych, tak na realnych datech.
2.1 Algoritmus Kmeans
Techniky shlukovanı zalozene na modelu rozdelujı jednourovnove (nehierar-chicky) datove prvky. Existuje nekolik takovych technik, z nichz jsou dve nejdule-zitejsı, a to Kmeans a Kmedoid. Budu se zde zabyvat pouze algoritmem Kmeans.Kmeans definuje model ve forme teziste, coz je obvykle prumer z cele skupinyprvku. Model je zpravidla aplikovan na data ve spojitem n - dimenzionalnımprostoru, proto je Kmeans jednım z nejstarsıch a nejrozsırenejsıch shlukovychalgoritmu.
2.1.1 Zakladnı algoritmus Kmeans
Technika shlukovanı Kmeans je povazovana za jednoduchou. Nejprve vyberemeK zakladnıch tezist’, kde K je parametrem definovanym uzivatelem (konkretnepocet pozadovanych shluku). Kazdy bod je oznacen a pridan nejblizsımu tezisti akazde seskupenı bodu prirazene jednomu tezisti je povazovano za shluk. Tezistekazdeho shluku je pote aktualizovano vzhledem k prvkum prirazenym do danehoklastru. Tento krok je neustale opakovan, dokud se menı slozenı prvku ve shlucıch,resp. dokud teziste nezustavajı na jednom mıste.
Jednotlive kroky algoritmu Kmeans
1. Vyber K bodu jako pocatecnı teziste.
2. Zacatek cyklu.
11
3. Vytvor K klastru prirazenım kazdeho prvku nejblizsımu tezisti.
4. Vypocti teziste nove vzniklych shluku a presun do nich vybrane body.
5. Konec za podmınky, ze se teziste jiz nepohybujı
Obrazek 3 ukazuje iterace algoritmu Kmeans.
Obrazek 3: Pouzitı Kmeans algoritmu k nalezenı trı shlukuZacına se tremi nahodne zvolenymi tezisti a konecna teziste jsou nalezena poctyrech iteracıch. U obrazku zobrazujıcıch Kmeans shlukovanı je na kazdempodobrazku (iteraci) ukazano teziste na zacatku iterace. Teziste jsou oznacenapomocı symbolu plus “+” a vsechny body v jednom shluku majı stejnouznacku.
V prvnı iteraci jsou body prirazeny k pocatecne zvolenym tezistım, ktere se
vsechny nachazı ve velke skupine bodu. Jako teziste napr. pouzijeme prumer
z bodu v jednom shluku, a tedy aktualizujeme novou polohu teziste. V dalsım
kroce jsou prvky prirazeny k nove vypoctenym poloham tezist’ a opet se pro-
vede aktualizace polohy tezist’. V iteracıch 2, 3 a 4 si lze vsimnout, jak se
dve teziste pohybujı smerem ke dvema mensım skupinam umıstenym nıze.
Pri ukoncenı tohoto algoritmu majı vypoctena teziste spravnou polohu.
Prirazenı prvku k nejblizsımu tezisti Pro prirazenı prvku k nejblizsımutezisti potrebujeme definovat, jak se bude merit podobnost, resp. vzdalenost,ktera urcı, co je to vlastne nejblizsı teziste (vzhledem ke druhu dat). Muzeexistovat nekolik variant merenı vzdalenosti, ktere je vhodne pro dany typ dat.Naprıklad v doprave casto pouzıvana metrika Manhattan, nebo velmi pouzıvanaEukleidovska vzdalenost pro datove prvky v Eukleidovskem prostoru (viz Prıloha5.4).
Merenı podobnosti pouzite pro Kmeans je obvykle relativne jednoduche. Duvodyjsou dva - dochazı opakovane k pocıtanı podobnosti mezi kazdym bodem akazdym tezistem, tudız se zde nepocıtajı podobnosti mezi prvky navzajem, atak pouzita podobnost, resp. vzdalenost, nenı vypocetne narocna.
Teziste a ucelova funkce Cıl shlukovanı je typicky vyjadren ucelovou funkcı,ktera zavisı na vzajemnych vzdalenostech mezi body, nebo na tezistıch klastru(napr. minimalizuj kvadrat vzdalenosti kazdeho bodu ke svemu nejblizsımu
12
tezisti). Pokud mame specifikovany typ metriky a ucelovou funkci, teziste, kteremame na pocatku vybrat, muze byt urceno matematicky.
Symbol Popis
x Datovy vzorek
Ci I-ty shlukci Teziste shluku Ci
c Teziste vsech bodumi Pocet prvku v ı-tem shlukum Pocet prvku v datove mnozineK Pocet shluku
Tabulka 1: Tabulka uzitych symbolu a jejich vyznamu
� Data v Eukleidovskem prostoru
Uvazujme data, u nichz jsme zvolili Eukleidovskou metriku. Pro nasi ucelovoufunkci, ktera urcuje kvalitu shlukovanı, pouzijeme kvadraticke kriterium. Jinymislovy vypocteme chybu kazdeho datoveho prvku, resp. jeho Eukleidovskou vzdale-nost k nejblizsımu tezisti, a pak udelame sumu ctvercu chyb. Pokud jsou dodanydve ruzne mnoziny shluku, ktere jsou vyprodukovany behem dvou rozdılnychchodu Kmeans, preferujeme tu s mensı hodnotou kvadratickeho kriteria, protozeto znamena, ze modely (teziste) shlukovanı majı lepsı reprezentaci ve svychklastrech. Kvadraticke kriterium je formalne zapsano pomocı (2), kde V vy-jadruje vzdalenost.
LS =
K∑i=1
∑x∈Ci
V (ci, x)2 (2)
Teziste (prumer) ı-teho shluku je definovano v rovnici (3).
ci =1
mi
∑x∈Ci
x (3)
Kroky 3 a 4 Kmeans algoritmu presne smerujı k minimalizaci ucelove funkce.Krok 3 tvorı shluky oznacenım bodu ke svym nejblizsım tezistım, coz minimali-zuje kvadratickou vzdalenost pro danou mnozinu tezist’. Krok 4 prepocte tezistetak, aby bylo mozne nasledovne opet minimalizovat kriterium. Nicmene kroky3 a 4 pouze zarucujı nalezenı lokalnıho minima, protoze je cela optimalizacezalozena na pocatecnı volbe tezist’ a poctu klastru.
� Obecny prıpad
13
Funkce podobnosti (vzdalenosti) Teziste Ucelova funkce
Ctverec Eukleidovske metriky (L2) prumer Minimalizovat kvadratickekriterium L2 vzdalenostı mezi
prvky a jejich tezisti
Tabulka 2: Vztah funkce vzdalenosti, teziste a ucelove funkce
Jak jiz bylo nastıneno, existuje nekolik moznostı vyberu funkce vzdalenosti,tezist’ a ucelove funkce, ktere mohou byt pouzity v zakladnım Kmeans algoritmu.Tabulka 2 ukazuje vztah mezi funkcı vzdalenosti, tezistem a ucelovou funkcı.
Do konce teto casti o algoritmu Kmeans budeme pouzıvat dvou-dimenzionalnıdata, protoze je na nich jednoduche Kmeans a jeho vlastnosti vysvetlit. Je vsaknutne si uvedomit, ze Kmeans je velmi obecny koncept postupu shlukovanı, atak muze byt pouzit pro sirokou skalu datovych typu (napr. i pro dokumenty cicasove serie).
Volba pocatecnıch tezist’ Pokud je pouzito nahodne pocatecnı rozmıstenıtezist’, pak je typicke, ze Kmeans pro rozdılne polohy da ruzne vysledky kva-dratickeho kriteria. Situace je ilustrovana na obrazku 4
Tri optimalni shluky
(globalni minimum kvadratickeho kriteria)
Tri suboptimalni shluky
(lokalni minimum kvadratickeho kriteria)
Obrazek 4: Tri optimalnı a suboptimalnı shlukyMuzeme porovnat dva vysledky shlukove analyzy, pricemz na prvnım z nich
doslo k nalezenı globalnıho minima kvadratickeho kriteria pro tri shluky a
na druhem k pouhemu nalezenı suboptima, tedy lokalnıho minima. Rozdılne
vysledky byly dosazeny dıky ruznym pocatecnım poloham tezist’.
Vyber spravnych pocatecnıch poloh tezist’ je klıcovym krokem zakladnıho al-goritmu Kmeans. Bezny postup vsak presto pouzıva jejich nahodne umıstenı,avsak vysledne klastry nemusı byt huste zaplnene.
Nahodne zvolene pocatecnı polohy tezist’ nemusı byt huste obklopene datovymivzorky. Dokazeme to prıkladem se stejnou datovou mnozinou, jaka byla pouzitav obrazku 3 a 4. Na obrazcıch 5 a 6 je zobrazen vysledek, ktereho jsme dosahlidvema ruznymi puvodnımi polohami tezist’. I kdyz jsou na obrazku 5 pocatecnıteziste vsechna z jednoho prirozeneho shluku, je nalezeno globalnı minimumkvadratickeho kriteria. Oproti tomu na obrazku 6, na kterem se muze zdat volbapocatecnıch tezist’ smysluplnejsı, dosahneme pouze suboptimalnıho shlukovanıs vetsı chybou kvadratickeho kriteria.
Iterace 1
Iterace 2 Iterace 3
Pocatecni rozmisteni datovych vzorku
Obrazek 5: Dva pary shluku s pocatecne zvolenymi dvema pary tezist’ uvnitrjednoho paru
15
Iterace 1 Iterace 2
Iterace 3 Iterace 4
Obrazek 6: Dva pary shluku s jinak pocatecne zvolenymi tezisti
� Limity nahodne inicializace
Jednou z technik, ktera se bezne pouzıva k vyresenı nahodne volby pocatecnıchpoloh tezist’, je nechat bezet nekolik Kmeans algoritmu kazdy s ruzne zvolenousoustavou pocatecnıch tezist’ a pak vybrat tu soustavu s nejmensı hodnotoukriteria. Tento postup je velmi jednoduchy, avsak ne vzdy ucinny. Zalezı totizna samotne datove mnozine a na pozadovanem poctu shluku K.
Data se skladajı ze dvou paru shluku, kde shluky v kazdem paru (nahore a dole)si jsou vzajemne blıze nez se shluky z druheho paru. Cast obrazku 5 - iterace1 a 2 ukazuje, ze pokud zacneme se dvema pocatecnımi tezisti v jednom parushluku, pak budou teziste i presto, ze pocatecnı dve teziste v jednom shlukutemer splyvajı, rozdelena a budou nalezeny prirozene shluky. Na obrazku 6 lzevidet, ze i kdyz ma jeden par shluku pouze jedno puvodnı teziste a dalsı zbyletri, pak budou dva ze trı prirozenych shluku spojeny a jeden bude rozdelen.
Vsimneme si, ze optimalnıho shlukovanı dosahneme prave tehdy, kdyz se dvepocatecnı teziste nachazı kdekoli v jednom paru shluku, protoze dojde k jejichnaslednemu rozdelenı (kazde teziste do jednoho prirozeneho shluku). Bohuzel jevsak velmi pravdepodobne, ze se zvysujıcım se poctem shluku bude mıt asponjeden par shluku pouze jedno pocatecnı teziste. V tomto prıpade dojde k tomu,ze par s jednım tezistem nebude algoritmem Kmeans rozdelen, protoze datovevzorky v paru shluku jsou si blıze samy sobe navzajem nez s ostatnımi shluky zjinych paru. Z tohoto duvodu je vetsinou dosazeno pouze lokalnıho optima.
16
Kvuli problemum s nahodne zvolenymi pocatecnımi tezisti, ktere mnohokratnelze preklenout ani opakovanym behem, se pouzıvajı jine techniky pro iniciali-zaci. Jeden z efektivnıch prıstupu je vzıt datove vzorky a udelat z nich shlukyza pouzitı nejake hierarchicke shlukove techniky. Pak je nalezeno K klastru naurcite urovni a teziste techto shluku jsou pouzita jako pocatecnı teziste pro Kme-ans. Tento postup casto pracuje velmi dobre, ale je prakticky pouze v prıpade,kdy je datova mnozina relativne mala (stovky az tisıce vzorku) a kdy je cıslo Kve srovnanı s poctem vzorku pomerne male.
Dalsı procedura pro volbu pocatecnıch tezist’, je nasledujıcı - zvolı se prvnıbod nahodne, nebo se vezme teziste vsech bodu. Pak se vybere bod, kteryje nejdale od tohoto jiz zvoleneho teziste. Takto se pokracuje navazne dale,az dostaneme pozadovany pocet K pocatecnıch tezist’, ktera nejsou nahodnerozhozena. Problemem tohoto prıstupu je vsak to, ze muze dojıt k volbe outlierujako pocatecnıho teziste namısto bodu s velkou hustotou bodu. Taktez je narocnevypocıtat nejvzdalenejsı bod od mnoziny pocatecnıch tezist’ v urcitem case.
Jinou moznostı je pouzitı ruznych alternativ Kmeans (napr. pulicı Kmeans, viz2.1.3), ktere nejsou tak nachylne k puvodnı volbe tezist’ nebo pouzitı urcitychprocesu po shlukovanı k vylepsenı vzniklych shluku.
Pozadavky na cas a pamet’ Pozadavky na velikost pamet’oveho prostorupro Kmeans jsou nenarocne, protoze jsou zaznamenavany pouze datove body ateziste. Konkretne je pozadovane ulozenı o velikosti (m + K) × n pamet’ovychbunek, kde m je pocet bodu a n je pocet atributu.
Pozadavky na vypocetnı cas jsou taktez nenarocne, protoze jsou linearnı vucipoctu datovych vzorku. Pozadovany cas je I×K×m×n, kde I je pocet iteracıpotrebnych ke konvergenci. Jak jiz bylo zmıneno, je I casto male cıslo, protozese vetsina zmen deje v prvnıch nekolika iteracıch. To je duvodem toho, procje Kmeans linearnı v m, cili v mnozstvı bodu, a proc je cıslo K, tedy pocetvytvorenych shluku, vyrazne mensı nez m.
2.1.2 Dodatky algoritmu Kmeans
Prazdne shluky Jeden z problemu Kmeans algoritmu je moznost vytvorenıprazdnych shluku, jestlize nejsou zadne body prirazeny ke klastru, resp. k tezistibehem prirazovanı. Pokud se toto stane, pak je nutne premıstit teziste, protozejinak bude chyba kriteria vetsı, nez je nutno.
Existuje nekolik moznostı, jak problem prazdnych shluku vyresit. Jednou zmoznostı je vybrat jako pocatecnı bod nejvzdalenejsı bod od nejakeho nynejsıhoteziste. Tento krok je vhodny, protoze zaroven pomuze eliminovat bod, kteryprave nejvıce prispıva k celkove chybe kvadratickeho kriteria.
Dalsım moznym resenım je vybrat nove teziste ze shluku, ktery nejvıce prispıvado chyby kvadratickeho kriteria. Toto typicky rozdelı klastr a redukuje celkovouchybu kriteria. Pokud existuje nekolik prazdnych shluku, pak muze byt tentoproces opakovan nekolikrat.
17
Outlier Pokud je pouzito kvadraticke kriterium, mohou outlieri velkou mırouovlivnit shluky, ktere byly nalezeny. Konkretneji - pokud jsou outlieri prıtomnı,vysledna teziste shluku (modely) nemusı byt tak reprezentativnı, jak by mohlabyt, s cımz souvisı i vyssı hodnota kvadratickeho kriteria. Z tohoto duvodu jenekdy velmi uzitecne predem nalezt outliery a eliminovat je. Je vsak dulezitesi uvedomit, ze existujı i takove aplikace shlukovanı, ve kterych by outlierinemely byt eliminovany. Pokud je shlukovanı pouzito pro kompresi dat, musıbyt soucastı shlukovanı kazdy bod.
Zrejmym problemem je, jak se jiz samo nabızı, identifikace outlieru. Pokud sepouzijı postupy, ktere odstranı outliery pred samotnym shlukovanım, vyhnemese tım bodum, ktere shlukovanı zhorsujı. Jako dalsı alternativa je identifikaceoutlieru az po procesu shlukovanı. Napr. muzeme udrzovat zaznam o kvadra-tickem kriteriu, resp. o prispenı kazdeho bodu do celkove hodnoty kriteria, apak eliminovat ty body, jejichz prıspevek je vyssı v porovnanı s ostatnımi body.Taktez muze byt nasım cılem eliminovat shluky o malem poctu vzorku, protozevetsinou reprezentujı prave skupiny outlieru.
Redukce hodnoty kvadratickeho kriteria v “post” procesu Zrejmymzpusobem jak redukovat kvadraticke kriterium je najıt vıce shluku, resp. pouzıtvetsı K. V nekterych prıpadech vsak chceme zmensit velikost kriteria pri za-nechanı stejneho poctu klastru, coz je obvykle mozne, protoze Kmeans konver-guje vzdy alespon k lokalnımu minimu. Pouzıva se mnoho technik pro zlepsenıvyslednych shluku, tedy pro shlukovanı s nizsım kvadratickym kriteriem. Stra-tegiı je se zamerit na jednotlive shluky, protoze celkova hodnota kvadratickehokriteria je vlastne souctem kriteriı od kazdeho shluku. Muzeme zmenit celkovouhodnotu kriteria provedenım nekolika operacı na klastrech.
Velmi beznym postupem je pouzıt dve faze, a to fazi rozdelovanı a fazi spo-jovanı. Tımto zpusobem se vyhneme lokalnımu minimu kvadratickeho kriteria analezneme resenı shlukovanı s pozadovanym poctem shluku. Zde jsou zmıneneprıklady technik, ktere se pouzıvajı pro tyto zmınene faze.
Strategie, ktere snizujı celkovou hodnotu kvadratickeho kriteria za soucasnehozvysenı poctu shluku :
� Rozdelenı klastru - pro rozdelenı je vybran shluk s nejvetsım kvadra-tickym kriteriem, ale taktez muze byt rozdelen shluk s nejvetsı smerodatnouodchylkou pro jeden konkretnı atribut.
� Pridanı noveho teziste, resp. noveho shluku - pro tuto strategii jevybran bod, ktery je nejdale od libovolneho centra shluku. Tento bod jsmeschopni jednoduse najıt, pokud si nechavame zaznam o prispenı k celkovehodnote kvadratickeho kriteria od kazdeho bodu. Jinou moznostı je vybratnahodne ze vsech bodu nebo z bodu s nejvyssım kvadratickym kriteriem.
� Odstranenı shluku - pro odstranenı shluku se nejprve odstranı samotneteziste vybraneho klastru a body, ktere z odstraneneho shluku zbyly, sepreradı jinym klastrum. Idealne by mel byt odstranenym shlukem ten,ktery zvysuje nejmene celkove kvadraticke kriterium.
� Spojenı dvou shluku - pro spojenı jsou typicky vybrany shluky, jejichzteziste jsou si nejblıze, nebo ty shluky, ktere nejmene prispıvajı k narustucelkoveho kriteria. Tato strategie spojenı je tataz, ktera se pouzıva v tech-nikach hierarchickeho shlukovanı (znama jako tezist’ova metoda).
Aktualizace tezist’ po krocıch Namısto aktualizace tezist’ shluku po tom, cobyly prirazeny vsechny body ke shlukum, mohou byt teziste aktualizovana v jed-notlivych krocıch shlukovanı - po prirazenı kazdeho bodu ke shluku. Vsimnemesi, ze toto vyzaduje bud’ zadnou nebo dve aktualizace tezist’ v kazdem kroce,protoze se bod bud’ presune k novemu klastru (dve aktualizace), nebo zustane vsoucasnem shluku (zadna aktualizace). Tento postup zarucuje, ze nejsou vytvare-ny prazdne klastry, protoze zacınajı vsechny shluky s jednım bodem a jestlima mıt nejaky shluk pouze jeden bod, bude tento bod pokazde prirazen tomusamemu shluku.
Nevyhodou teto aktualizace je zavislost na volbe poradı. Jinak receno - vznikleshluky muzou zaviset na poradı, v jakem byly prirazovany jednotlive body. Ikdyz to muze byt vyreseno nahodnym poradım, v jakem jsou body prirazovany,zakladnı prıstup aktualizace tezist’ (po prirazenı vsech bodu) nezavisı na zadnemporadı. Aktualizace po jednotlivych krocıch je narocnejsı. Nicmene Kmeans kon-verguje pomerne rychle, takze mnozstvı bodu menıcıch shluky se relativne rychlezmensuje.
2.1.3 Pulicı Kmeans
Pulicı Kmeans algoritmus je pouhym rozsırenım zakladnıho Kmeans. Vse jezalozeno na zakladnı myslence - k zıskanıK klastru se rozdeluje puvodnı mnozinavsech vzorku do dvou shluku, vybere se jeden z techto nove vzniklych shluku,ktery se opet rozdelı na dva podshluky. Tento postup se opakuje, az se dosahneK klastru.
Jednotlive kroky pulicıho algoritmu Kmeans
1. Vytvor seznam shluku. Na zacatku obsahuje jeden shluk vsechny vzorky.Pote dochazı v kazdem cyklu k aktualizaci.
5. Vyber dva shluky s nejnizsı hodnotou kvadratickeho kriteria.
6. Pridej tyto dva shluky do seznamu shluku.
7. Konec za podmınky, ze seznam shluku obsahuje K shluku.
Existuje nekolik moznostı, jak vybrat shluk, ktery ma byt rozpulen. Muze se vy-brat shluk nejrozsahlejsı, s nejvyssım kvadratickym kriteriem, nebo kombinaceobou techto podmınek. Samozrejmostı je, ze ruzne volby vyustı v ruzne klastry.
Casto pouzijeme teziste vyslednych shluku pulicıho Kmeans algoritmu jakopocatecnı teziste pro zakladnı algoritmus Kmeans. I kdyz Kmeans zarucuje na-lezenı shlukovanı reprezentujıcı alespon lokalnı minimum s ohledem na kvadra-ticke kriterium, v pulicım Kmeans se pouzıva Kmeans lokalne, tj. k rozpulenıjednotlivych shluku, proto vysledek nereprezentuje kompletnı konecnou mnozinushlukovanı.
Prıklad pulicıho Kmeans a inicializace Vyhodou pulicıho Kmeans je zejme-na jeho mala citlivost vuci pocatecnımu nastavenı. K ilustraci tohoto tvrzenı siukazme na obrazku 7, jak pulicı Kmeans nalezne ctyri shluky v datove mnozinez obrazku 5.
Iterace 1 Iterace 2 Iterace 3
Obrazek 7: Pulicı Kmeans na prıkladu se ctyrmi shlukyV prvnı iteraci jsou nalezeny dva shluky, ve druhe je rozdelen shluknapravo a ve tretı nalevo. pulicı Kmeans ma mene problemu s iniciali-zacı, protoze provadı nekolik zkusebnıch pulenı a vybere tu s nejmensıhodnotou kvadratickeho kriteria.
2.1.4 Kmeans a ruzne typy shluku
Kmeans a jeho varianty majı nekolik omezenı zejmena tykajıcıch se nalezenıruznych druhu klastru. Obzvlaste ma Kmeans problem detekovat “prirozene”shluky, kdyz majı nekulovy tvar, rozdılne velikosti nebo ruzne hustoty. Nazornaukazka je na obrazku 8.
Na prvnım podobrazku nemuze Kmeans nalezt tri prirozene shluky, protozeje jeden z nich mnohokrat vetsı nez dalsı dva. Z toho duvodu je vetsı z nichrozdelen na dva a jsou k nemu prideleny vzorky z jednoho mensıho. Na druhecasti lze videt, ze Kmeans nedokaze najıt tri prirozene shluky, protoze dva mensı
majı vyssı hustotu nez zbyle vetsı. Na poslednı ukazce nalezl Kmeans dva shluky,ktere obsahujı vzorky z obou shluku prirozenych. Ty totiz nejsou kuloveho tvaru.
Obtıznosti v techto trech situacıch vznikajı, protoze ucelova funkce Kmeans tvorıneshody pro typy shluku, ktere jsme se snazili najıt, protoze je minimalizovanakulovitymi shluky stejnych velikostı a stejne hustoty, nebo shluky, ktere jsouostre rozdelene. Nicmene tato omezenı mohou byt svym zpusobem prekonana,pokud je uzivatel ochotny prijmout shlukovanı, jehoz vysledkem jsou prirozeneshluky, avsak rozdelene na nekolik podshluku. Obrazek 9 ukazuje, co se stane,pokud zvysıme cıslo K = 6 namısto puvodnıch 2 a 3. Kazdy mensı shluk jeuplny v tom smyslu, ze obsahuje pouze body z jednoho prirozeneho shluku.
2.1.5 Silne a slabe stranky
Kmeans je velmi jednoduchy algoritmus, ktery muze byt pouzit pro sirokouskalu datovych typu. Je i pomerne ucinny, i kdyz se casto musı provadet opa-kovane. Nektere varianty (zde zmıneneho pulicıho) Kmeans jsou dokonce jesteucinnejsı a mene citlive vuci pocatecnımu nastavenı nez zakladnı. Kmeans nenı
21
Ruzne velikosti
Ruzne hustoty
Nekulovite tvary
Obrazek 9: Nalezenı prirozenych shluku skladajıcıch se ze subshluku
vhodny pro vytvorenı ruznych typu shluku. Neumı udelat nekulovite shlukynebo shluky ruznych velikostı a hustot, ackoli muze nalezt podshluky tvorıcıprirozene shluky, kdyz je povoleno vetsı K.
Kmeans ma taktez problemy s daty obsahujıcımi outliery, ty vsak mohou bytrozpoznany a vymazany, coz vyrazne zlepsı kvalitu shlukovanı pomocı Kmeans.
2.2 Hierarchicke shlukovanı
Hierarchicke shlukove techniky jsou dalsı dulezitou kategoriı ve shlukovanı. Takjako Kmeans patrı k pomerne starym technikam, ktera vsak nachazı sirokeuplatnenı i na poli dnesnıch aplikacı. Rozlisujeme dva prıstupy - aglomerativnıa divizivnı (viz Prıloha 5.5). Aglomerativnı prıstupy jsou jedny z nejbeznejsıch,a tak o nich bude pojednano blıze.
22
Hierarchicke shlukovanı je casto zobrazovano pomocı grafu - stromu, kteryse v tomto prıpade nazyva dendrogram. Ten zobrazuje vztahy shluk - sub-shluk a zachycuje poradı, v jakem byly shluky vytvoreny. Pro mnoziny z dvou-dimenzionalnıho prostoru muze byt hierarchicke shlukovanı reprezentovano zapouzitı diagramu vkladanych shluku. Obrazek 10 ukazuje tyto dva typy zob-razenı pro ctyri mnoziny bodu (shluky byly vytvoreny za pouzitı metody nej-blizsıho souseda).
Existuje nekolik metod, jak tvorit shluky, resp. jak pristupovat k jednotlivymprvkum shluku. Blıze bude pojednano o metode nejblizsıho, nejvzdalenejsıhosouseda a o centroidnı metode.
Postup vsech metod ma stejnou zakladnı myslenku. Na zacatku se vezme kazdyvzorek jako jednotlivy shluk a nasledne se vytvorı seznam vzdalenostı mezishluky pro vsechny ruzne neusporadane dvojice. Nasledne se seradı tyto vzdalenos-ti vzestupne. Dojde k vytvorenı grafu, ve kterem jsou vytvoreny dle ruznych me-tod uzly z dvojic vzorku (viz Definovanı sousedstvı mezi shluky). Jestlize jsouvsechny vzorky cleny jednoho shluku, pak je konec, jinak se neustale tento krokopakuje. Vysledkem algoritmu je sıt’ova hierarchie, ktera muze byt rozclenenana pozadovane urovni nepodobnosti (vzdalenosti), na ktere se nachazı urcitypocet shluku.
� Algoritmus pro metodu nejblizsıho souseda
1. Vytvor seznam vzdalenostı pro vsechny neusporadane dvojice shluku.
2. Serad’ vzestupne vzdalenosti.
3. Zacatek cyklu.
4. Sluc dva shluky (dle vybrane metody).
23
5. Aktualizuj seznam vzdalenostı s novym shlukem.
6. Konec za podmınky, ze zbyva pouze jeden shluk.
Ukazme si nazorne rozdılny vysledek za pouzitı metody nejblizsıho a nejvzdalenej-sıho souseda. Na obrazku 11 jsou dva shluky rozdelene mostem ze sumu.
Metoda nejblizsiho souseda Metoda nejvzdalenejsiho souseda
Obrazek 11: Ukazka rozdılu pouzitı metody nejblizsıho a nejvzdalenejsıho sou-seda
Klastry vytvorene metodou nejblizsıho souseda (leva cast obrazku) jsou vıce
kompaktnı (ucelene) nez ty porızene metodou nejvzdalenejsıho souseda (prava
cast). Vetsı shluk je v druhem prıpade podlouhly kvuli retezci sumovych
vzorku oznacenych *, coz je dukazem toho, ze metoda nejblizsıho souseda
je prizpusobivejsı a promenlivejsı vuci datum nez metoda nejvzdalenejsıho
souseda. Nicmene se ukazalo, ze z pragmatickeho hlediska prinası metoda nej-
vzdalenejsıho souseda uzitecnejsı hierarchie v mnoha aplikacıch nez metoda
nejblizsıho souseda.
Definovanı sousedstvı mezi shluky Klıcovou zalezitostı je vypocet blızkostimezi dvema shluky (resp. urcenı vzajemneho sousedstvı dvou shluku), coz lzeprovezt nekolika zpusoby. Blızkost shluku je typicky definovana spolu s urcitymtypem klastru. Mnoho, jiz zmınenych, aglomerativnıch metod jako MIN, MAXci prumer skupiny pochazı ze shluku zalozenych na grafech (viz Prıloha 5.3) .
� MIN definuje sousedstvı shluku jako vzdalenost mezi dvema nejblizsımivzorky z ruznych shluku (v terminologii grafu hovorıme o nejkratsı hranemezi dvema uzly v ruznych podmnozinach uzlu). Touto metodou muzemevytvorit souvisle shluky.
� Alternativou je metoda MAX, ktera bere jako sousedstvı dvou shlukuvzdalenost mezi dvema nejvzdalenejsımi vzorky v ruznych klastrech (nejdel-sı hrana mezi dvema uzly v ruznych podmnozinach uzlu).
� Poslednım prıstupem k tomuto problemu je prumer cele skupiny, cozznamena, ze se jako sousedstvı dvou rozdılnych shluku bere prumer zevsech vzorku v jednotlivem shluku.
24
Prumer skupiny
Metoda nejvzdalenejsiho souseda (MAX)Metoda nejblizsiho souseda (MIN)
Obrazek 12: Techniky urcenı sousedstvı
Na obrazku 12 jsou tyto tri prıpady ilustrovany.
Dalsı moznosti definice vzdalenostı existujı pro shluky reprezentovane svymtezistem. Zde je sousedstvı bezne definovano jako vzdalenost mezi jejich tezisti.Alternativnı technika - Wardova metoda merı sousedstvı mezi dvema shluky vramci narustu kvadratickeho kriteria, ktery je vysledkem spojenı dvou shluku.Jako Kmeans se snazı Wardova metoda minimalizovat sumu kvadratickych vzdale-nostı vzorku a jejich tezist’.
Pozadavky na cas a pamet’ Vyse zmınene aglomerativnı prıstupy pouzıvajımatici sousednosti, coz vyzaduje ulozenı 1
2m2 vzdalenostı (pokud se tedy predpo-
klada, ze je matice sousednosti symetricka), kde m je pocet datovych vzorku.Pamet’ potrebna pro sledovanı tvorby shluku je umerna poctu shluku, coz jem− 1 vyjma shluku s jednım prvkem. Proto jsou pozadavky na pamet’ m2.
Analyzu zakladnıch aglomerativnıch algoritmu musıme uvazovat i vzhledem kvypocetnı narocnosti. K vypoctu matice sousednosti je pozadovano m2 casovychjednotek. Po tomto kroce je m − 1 iteracı, ktere zahrnujı pouze kroky 3 a 4,protoze je na zacatku m klastru a behem kazde iterace jsou spojeny dva shluky.Pokud je provedeno linearnı prohledavanı matice sousednosti, pak pro ı-touiteraci pozaduje krok 3 (m − i + 1)2 casovych jednotek. Krok 4 vyzaduje jizpouze m− i+ 1 casovych jednotek k aktualizaci matice sousednosti po sloucenıdvou shluku. Casova narocnost takoveto ulohy by tedy zabrala m3 casovychjednotek. Pokud jsou vzdalenosti od kazdeho shluku ke vsem ostatnım ukladanyjako usporadany seznam, je mozne redukovat usilı k nalezenı dvou nejblizsıchshluku na m− i+ 1 casovych jednotek. Nicmene kvuli obtıznostem s udrzenımdat ve srovnanem seznamu je celkovy cas potrebny pro vyse zmıneny algoritmusm2 × log (m) jednotek.
Casove a pamet’ove pozadavky pro hierarchicke shlukovanı striktne omezujevelikost datove mnoziny, se kterou ma byt pracovano.
25
2.2.2 Ukazka metod na prıklade
Vzorek dat Pro lepsı predstavenı chovanı ruznych hierarchickych algoritmupouzijeme vzorek dat, ktery se sklada z 6 dvou-dimenzionalnıch bodu, ktere jsouukazany na obrazku 13. Souradnice x a y a Eukleidovske vzdalenosti mezi bodyjsou zaznamenany v tabulkach 3 a 4.
Metoda nejblizsıho souseda (MIN) Pro metodu nejblizsıho souseda, resp.pro MIN verzi hierarchickeho shlukovanı je sousedstvı dvou shluku definovano
26
jako minimalnı vzdalenost, resp. maximalnı podobnost, mezi dvema body vedvou ruznych shlucıch. Pokud tedy zacneme se vsemi body jako se shluky o jed-nom prvku a vytvorıme spojenı mezi body (uzly) pocınaje spojenım o nejmensıvelikosti, pak se tato spojenı (hrany) protınajı v uzlech, ktere jsou reprezentacıshluku. Tato technika je vhodna pro neelipticke tvary. Je vsak velmi citliva vucisumu a outlierum.
� Prıklad pouzitı metody nejblizsıho souseda
Obrazek 14 ukazuje vysledek pouzitı metody nejblizsıho souseda na nasemvzorku dat.
DendrogramMetoda nejblizsiho souseda pomoci vkladani
Obrazek 14: Ukazka metody nejblizsıho souseda (resp. MIN)Na leve casti obrazku jsou k videnı vlozene shluky jako posloupnost vlozenych
elips, kde cısla u elips znazornujı rad shlukovanı. Prava cast zobrazuje tu
samou situaci, ale ve forme dendrogramu. Vyska, ve ktere jsou spojeny dva
shluky v dendrogramu (je vytvoren uzel), znamena vzdalenost mezi dvema
shluky.
Z tabulky 4 vidıme, ze vzdalenost mezi body 3 a 6 je 0.11, coz je vlastne vyska, vektere jsou tyto dva body spojeny do jednoho shluku v dendrogramu. Jako dalsıprıklad uved’me vzdalenost (oznacovanou jako V ) mezi shluky {3,6} a {2,5} :
Metoda nejvzdalenejsıho souseda (MAX) Pro metodu nejvzdalenejsıhosouseda, resp. pro MAX verzi hierarchickeho shlukovanı je sousedstvı dvou
27
shluku definovano jako maximalnı vzdalenost, resp. minimalnı podobnost, mezidvema body ve dvou ruznych shlucıch. I v tomto prıpade se vytvarı spojenı(hrany) mezi body (uzly). Zacına se jako v predchozım prıpade nejkratsım spo-jenım. Dale se pak opet slucujı shluky, ktere majı k sobe nejblıze (podmınka hi-erarchickeho shlukovanı). Neporovnavajı se vsak vzdalenosti nejblizsıch prvkuve shluku, nybrz nejvzdalenejsıch. Tato metoda je mene nachylna vuci sumua outlierum, ale muze rozbıt velke shluky a zaroven favorizuje kulovite tvaryshluku.
� Prıklad pouzitı metody nejvzdalenejsıho souseda
Obrazek 15 ukazuje vysledek pouzitı MAX varianty shlukovanı na nasem vzorkudat z 6 bodu. Tak jako v prıpade nejblizsıho souseda jsou body 3 a 6 sloucenyjako prvnı, pak body 2 a 5. Dale je vsak shlukovanı rozdılne - body 3 a 6jsou slouceny se 4 namısto s 2 a 5 nebo 1, protoze shluk {3, 6} je blıze shluku 4.Duvodem je uvazovanı nejvzdalenejsıch prvku ve shluku do vypoctu vzdalenosti.
Prumer skupiny Poslednı varianta je vzıt jako hlavnı kriterium pro sou-sedstvı dvou shluku prumer vzdalenostı mezi vsemi pary vzorku v jednotlivychshlucıch. Toto je jakysi kompromis mezi metodami nejblizsıho a nejvzdalenejsıhosouseda. Pro prumer skupiny je vyjadreno sousedstvı dvou shluku (Ci, Cj), kteremajı velikosti mi, resp. mj nasledovne:
p(Ci, Cj) =
∑V (x, y)
mimj, kde citatel je sumou vzdalenostı mezi prvky mezi shluky.
(4)
� Prıklad pouzitı prumeru skupiny
Obrazek 16 ukazuje vysledek pouzitı prumeru skupiny na nasem vzorku dat z6 bodu. Pro ilustraci fungovanı skupinoveho prumeru, vypocteme vzdalenostimezi nejakymi shluky.
V ({3, 6, 4}, {1}) = (0.22 + 0.37 + 0.23)/(3 ∗ 1)
28
DendrogramMetoda nejvzdalenejsiho souseda pomoci vkladani
Obrazek 15: Ukazka metody nejvzdalenejsıho souseda (resp. MAX)
Protoze je V ({3, 6, 4}, {2, 5}) mensı nez V ({3, 6, 4}, {1}) a V ({2, 5}, {1}), jsoushluky {3, 6, 4} a {2, 5} slouceny na ctvrtem stupni hierarchie.
Shlukovani za pomoci prumeru skupiny a vkladani Dendrogram
Obrazek 16: Ukazka pouzitı prumeru skupiny
29
Wardova metoda a tezist’ova metoda Ve Wardove metode se sousedstvımezi dvema shluky definuje prave tehdy, kdyz vzroste hodnota kvadratickehokriteria, ktera vznikne spojenım dvou shluku. Tato metoda pouzıva stejnouucelovou funkci jako algoritmus Kmeans. Muze se zdat, ze tato metoda jesvym zpusobem rozdılna od jinych hierarchickych technik, ale lze matematickydokazat, ze je velmi podobna s predchozı metodou prumeru skupiny.
Tezist’ova metoda urcuje sousedstvı mezi dvema shluky vypoctenım vzdalenostimezi tezisti shluku. Opet se jevı jako velmi podobna algoritmu Kmeans.
Metoda tezist’ ma vlastnost, ktera je vetsinou povazovana jako negativum akterou nelze najıt v jinych hierarchickych postupech, a to moznost inverze.Konkretneji - shluk 1 si muze byt blıze shluku 2, ktery je vsak jiz soucastı jinehoshluku (vytvoreneho v predchozım kroce se shlukem 3), a tak je jiz soucastıprepoctu teziste noveho shluku (tvoreneho ze shluku 2 a 3). Pro dalsı metodyse vzdalenost mezi sloucenymi shluky zvetsuje, protoze postupujeme od shlukuo jednom prvku k jednomu shluku obsahujıcı vsechny prvky.
2.2.3 Lancuv-Williamsuv vztah pro sousedstvı (L-W vztah)
Na mnohe ze zmınenych vypoctu sousednosti muzeme nahlızet jako na L-Wvztah (5) s ruznymi parametry.
Pokud tedy spojıme shluky A a B a vytvorıme tım shluk R, sousedstvı novehoshluku R vuci jiz existujıcımu shluku Q je linearnı funkce sousedstvı shluku Qvzhledem ke shlukum A a B. Tabulka 5 zobrazuje hodnoty techto koeficientupro zmınene techniky.
Tabulka 5: Parametry L - W vztahu pro klasicke hierarchicke algoritmy
Nektere hierarchicke algoritmy, ktere mohou byt vyjadreny L-W vztahem, ne-ukladajı puvodnı datove vzorky. Namısto toho je matice sousednosti aktuali-zovana behem shlukovanı. Muze se zdat jednodussı pouzıt obecny vztah L-W,
30
ale zejmena pro implementaci je vyhodnejsı k porozumenı a k nalezenı rozdılumezi jednotlivymi hierarchickymi metodami pouzıvat prımo definice sousedstvıpro jednotlive metody.
2.2.4 Problemy hierarchickeho shlukovanı
Absence globalnı ucelove funkce Jednım z problemu je, ze aglomerativnıhierarchicke shlukovanı neumı globalne optimalizovat ucelovou funkci. Namıstotoho pouzıva ruzna kriteria pro lokalnı rozhodnutı v kazdem kroce, ktera sepouzıvajı pro volbu shluku, ktere majı byt spojeny. Tento pohled na shlukovanıprinası shlukove algoritmy, ktere se vyhybajı obtıznostem v podobe kombinato-rickych optimalizacnıch problemu. Tyto prıstupy nemajı problemy s nalezenımlokalnıch minim nebo s vyberem pocatecnıch vzorku. Na druhou stranu odrazujeod pouzitı techto technik casova a pamet’ova narocnost.
Schopnost vytvorit ruzne velikosti shluku Dalsım z problemu je, jakzachazet s relativnımi velikostmi sloucenych shluku. Existujı dve varianty -vazena, ktera bere v uvahu pocet vzorku v kazdem shluku a nevazena, kterabere vsechny shluky stejnou merou. Vsimneme si, ze termıny vazeny a nevazenyse tyka datovych vzorku a ne samotnych shluku. Jinymi slovy receno - shlukynestejnych velikostı davajı rovnomerne ruzne vahy bodum v ruznych shlucıch,zatımco pokud bereme v uvahu velikosti shluku, pak je bodum v ruznych shlucıchdavana vaha stejna.
Rozhodnutı o spojenı dvou shluku jsou konecna Aglomerativnı postupyprinası dobra lokalnı rozhodnutı, co se tyce kombinovanı dvou shluku, protozemohou pouzıt informaci o podobnostech mezi pary ze vsech bodu. Nicmenepokud jiz jednou spojıme dva shluky, nenı mozne toto spojenı pozdeji zrusit,coz je hlavnı prıcinou toho, ze se z lokalnıho optimalizacnıho kriteria nestaneglobalnı. Dusledkem je pak to, ze nejsou shluky stabilnı, resp. bod v nejakemshluku muze byt blıze k tezisti shluku jineho nez k tomu, ke kteremu nynıprıslusı.
Existujı techniky, ktere se snazı prejıt pres zmınene limity. Jedna z moznostıje pohybovat vetvemi stromu, abychom vylepsili globalnı ucelovou funkci. Dalsımoznost pouzıva nehierarchicke techniky shlukovanı (napr. Kmeans) k vytvorenımnoha malych shluku, ktere pak bere jako pocatecnı body pro hierarchicke shlu-kovanı.
Silne a slabe stranky Silne a slabe stranky jednotlivych technik aglomera-tivnıho hierarchickeho shlukovanı jiz byly prodiskutovany. Obecne se vsak ta-kove algoritmy casto pouzıvajı, protoze mnoho systematickych aplikacı vyzadujehierarchii. Existujı studie tvrdıcı, ze tyto algoritmy mohou produkovat kva-litnejsı shluky. Nicmene aglomerativnı prıstupy jsou narocne, co se tyce dobyvypoctu a pozadavku na pamet’. Skutecnost, ze vsechna spojenı jsou konecna,
31
muze taktez cinit problemy zejmena pri praci se sumem a s vysoce-dimenzionalnı-mi daty. Postupne mohou byt tyto dve zalezitosti vyreseny pomocı jinych nehi-erarchickych technik, napr. pomocı Kmeans.
2.3 DBSCAN
DBSCAN je metoda zalozena na hustote bodu. Shlukovanı zalozene na hustotehleda oblasti o vysoke hustote bodu, ktere jsou oddelene oblastmi s hustotounızkou.
2.3.1 Zakladnı idea DBSCANu
Centralnı hustota, neboli hustota zalozena na centru, patrı mezi nejcasteji pouzıva-ne typy hustot. V tomto prıstupu je hustota odhadovana pro urcite specifickebody v mnozine dat, kdy je pocıtano mnozstvı bodu v urcenem okruhu kolemcentra. Centrum je samozrejme zapocıtano take jako soucast shluku. Tato tech-nika je zobrazena na obrazku 17, kdy body ve stanovenem okruhu kolem boduA reprezentujı centralnı hustotu.
A
Eps
Obrazek 17: Centralnı hustota
Rekneme, ze bod q lezı v okolı bodu p, jestlize se nenachazı ve vzdalenosti vetsınez je urcena vzdalenost ε (tj. ze bod q je soucastı ε-sousedstvı bodu p). Pokudje bod p obklopen dostatecne mnoho body, pak mohou byt p a q soucastı jednohoshluku, i kdyz q nelezı v okolı bodu p. Rekneme, ze bod q je dosazitelny z p,pokud existuje posloupnost bodu p1, p2, ...pn takova, ze p1 = p a pn = q , akde je kazdy pi+1 v okolı od pi. Tento vztah tykajıcı se shluku zalozenych nahustote nenı symetricky (q muze lezet na hrane shluku, kdy nema dostatecnemnozstvı sousedu, aby byl povazovan za skutecny element klastru), a tak jespojenı pomocı hustoty nasledovne: body p a q jsou spojene prave tehdy, kdyzexistuje bod o takovy, ze o a p (taktez jako o a q) jsou hustotne dosazitelne.
Tato metoda je jednoducha na implementaci, ale velkou roli zde hraje velikostdefinovaneho okruhu kolem centra dane vzdalenosti ε. Naprıklad, pokud je okruh(resp. jeho polomer) dost velky, pak budou mıt vsechny body hustotu m (pocetbodu v datove mnozine). Podobne platı i naopak - pokud bude polomer prılismaly, pak budou mıt vsechny body hustotu 1.
32
Shluk, ktery je podmnozinou vzorku v mnozine, splnuje tyto dva postulaty :
1. Vsechny body v klastru jsou navzajem dosazitelne na zaklade hustoty.
2. Pokud je bod dosazitelny na zaklade hustoty s kazdym bodem ve shluku,je rovnez soucastı daneho shluku.
Klasifikace bodu vzhledem k centralnı hustote Centralnı hustota umoznu-je klasifikovat nasledujıcı body :
� jadrovy bod - nachazı se uvnitr shluku. Bod je jadrovym, pokud pocetbodu uvnitr daneho sousedstvı okolo bodu urceneho funkcı vzdalenosti aparametrem vzdalenosti daneho uzivatelem dosahuje nejake hranice, cozje dalsı parametr, ktery si urcuje sam uzivatel.
� hranicnı bod - nenı jadrovy, ale je zarazen do sousedstvı kolem bodujadroveho. Hranicnı bod muze spadat pod nekolik jadrovych.
� sumy a body pozadı - body nahodne rozptylene, nachazejıcı se v rıdceobsazene oblasti. Nenı ani jadrovy, ani hranicnı.
C
B
AEps
Sumove body
Jadrove body
Hranicni bod
Obrazek 18: Jadro oblasti, hranice oblasti a sum ve dvourozmernem prostoru
2.3.2 Algoritmus DBSCAN
Po urcenı obou z parametru - ε a minimalnıho poctu bodu potrebnych k vy-tvorenı klastru - zacına DBSCAN s libovolne zvolenym bodem. Dojde k urcenıjeho okolı ve vzdalenosti ε. Jestlize toto okolı obsahuje dostatecne mnozstvıbodu (zadane jako druhy parametr), je vytvoren shluk. Jinak je bod prozatımoznacen jako sum. Toto oznacenı sumu nemusı byt konecne. V dalsıch iteracıch
33
muze byt totiz tento bod soucastı okolı jineho bodu, a tak byt soucastı jinehoshluku.
Pokud je bod oznacen jako soucast klastru, jeho ε-okolı je take soucastı klastru.Z tohoto duvodu vsechny body, ktere se nachazı v okolı ve vzdalenosti ε vsechjadrovych bodu, jsou pridany spolu s jejich vlastnım ε- okolım. Tento postuppokracuje, dokud jiz neexistuje bod, ktery by mohl byt pridan do uvazovanehoshluku. Pokud pocet pridavanych bodu prevysuje minimalnı pocet bodu provytvorenı klastru, vznikne shluk. Pote je novy, dosud vubec neuvazovany, bodbran jako pocatecnı a cely proces je opakovan.
Nakonec musı byt prirazeny hranicnı body pouze do jednoho shluku (pokud nenıpovoleno, ze mohou byt soucastı vıce shluku). Sumove body jsou vyrazeny. Tentoalgoritmus je optimalizovan z hlediska jednoduchosti a ne z hlediska efektivity.
Zakladnı algoritmus DBSCANu
1. Zacatek cyklu - vezmi libovolny (dosud neuvazovany) bod.
2. Oznac jako jadrove body, ktere se nachazı v jeho ε- okolı.
3. Pridej body nachazejıcı se v ε- okolı vsech jadrovych bodu.
4. Jiz nelze pridat dalsı bod. Pokud pocet bodu ve shluku je vetsı nez mi-nimalnı pozadovany pocet bodu pro vytvorenı shluku, vznikne shluk.
5. Nenı splnena podmınka minimalnıho poctu bodu pro vytvorenı shluku.Puvodnı bod je oznacen jako sum.
6. Konec cyklu, pokud jsou prosetreny vsechny body.
7. Prirazenı hranicnıch bodu do jednoho shluku. Odstranenı sumovych bodu.
Volba parametru DBSCANu Jednou ze zasadnıch zalezitostı je volba pa-rametru ε a minimalnıho poctu bodu potrebnych k vytvorenı shluku (v lite-rature casto oznacovano jako MinPts). Tyto parametry jsou ve vetsine prıpaduurceny samotnym uzivatelem, protoze ruzne datove mnoziny a oblasti aplikacealgoritmu pozadujı rozdılne parametry.
Jednou z moznostı, jak urcit pocatecnı hodnotu parametru, je pomocı tzv.k-vzdalenosti. Zakladem je urcit samotne k, pak se podıvat na vzdalenost zkazdeho bodu k jeho k-temu nejblizsımu sousedovi. Tato vzdalenost se nazyvak-vzdalenost. Napr. uvazujme k = 5, pak od kazdeho bodu urcıme k-vzdalenostjako vzdalenost k 5. nejblizsımu bodu.
Pro body patrıcı do shluku, bude k-vzdalenost mala, pokud nebude k vetsı nezvelikost klastru. Existuje urcity rozptyl hodnot k, ktery zavisı na hustote jedno-tlivych shluku. Pokud nejsou hustoty prirozenych shluku radikalne rozdılne, ne-bude rozptyl hodnoty k-vzdalenosti velky. Pro sumove body bude k-vzdalenostvelka.
34
Pokud spocteme k-vzdalenost pro vsechny datove vzorky, seradıme je vzestupnea zakreslıme, uvidıme ostrou zmenu v hodnotach k-vzdalenosti, jak si lze vsimnoutna prave casti obrazku 19. Hodnota pod ostrou zmenou je vhodnou velikostı provolbu parametru ε. Jako minimalnı pocet bodu pro vytvorenı shluku je moznevzıt samotne k (v nasem prıpade je MinPts = 5).
Vzorek dat K−vzdalenost pro dany vzorek dat
Obrazek 19: Vzorek dat a k-vzdalenostNa leve casti obrazku 19 je zobrazena mnozina vzorku dat. Na prave casti je
vykreslen graf s odpovıdajıcımi k-vzdalenostmi
Hodnota polomeru zalezı na k a s nım se take menı. Kdyz je hodnota k prılismala, pak i male mnozstvı bodu umıstenych blızko sebe, ktere predstavujı sumnebo outlier, je nekorektne oznaceno jako klastr. Pokud je vsak hodnota k prılisvelka, pak budou pravdepodobne male klastry (velikosti mensı nez k) oznacenyjako sum. Puvodnı DBSCAN pouzıva hodnotu k = 4, ktera se jevı jako vhodnapro vetsinu dvou-rozmernych mnozin dat.
Shluky s menıcı se hustotou U DBSCANu se mohou vyskytnout problemys hustotou, pokud se hustota shluku menı. V leve casti obrazku 19 jsou zobra-zeny 4 shluky vcetne sumu. Hustota shluku a oblastı sumu je vykreslena jinymodstınem. Sum kolem obou shluku A a B ma stejnou hustotu jako samotneshluky C a D. Pokud je velikost polomeru dostatecne mala tak, ze DBSCANpovazuje C a D za klastry, pak A a B a body je obklopujıcı vytvorı jediny klastr.Pokud je polomer dost velky, pak DBSCAN urcı A a B jako jednotlive oddeleneshluky a body kolem oznacı jako sum a nasledne budou C a D a body kolempovazovany taktez za sum.
Na leve casti obrazku 19 jsou vykresleny shluky, ktere jsou nalezeny v pomerneslozite dvou-rozmerne mnozine dat. Tato mnozina je vytvorena z 3000 vzorku.Velikost polomeru pro tato data byla urcena na zaklade vykreslenı vybranychk-vzdalenostı ctvrteho nejblizsıho souseda od kazdeho bodu a taktez na zakladeurcenı hodnoty, pri ktere dochazı k ostremu vzestupu. Byl vybran polomerε = 10, ktery odpovıda kolenu u vzestupu vykreslenych k-vzdalenostı. Shlukynalezene DBSCANem za pouzitı nasledujıcıch parametru : ε = 10 , MinPts = 4
35
jsou zobrazeny na hornı casti obrazku 20. Jadrove, hranicnı body a sum jsouukazany v casti spodnı.
Nalezene shluky DBSCANem
Jadrove, hranicni a sumove body
Obrazek 20: Ukazka DBSCAN shlukovanıNa spodnı casti obrazku jsou jadrove body oznaceny koleckem, hranicnı plu-
sem a sum krızkem.
Pozadavky na cas a pamet’ Zakladnı casova slozitost algoritmu DBSCANje m krat cas potrebny k nalezenı bodu v sousedstvı, kde m je pocet bodu. Vnejhorsım prıpade muze byt casova narocnost m2 casovych jednotek. Nicmenev nızko-dimenzionalnıch prostorech jsou datove struktury, ktere umoznujı efe-ktivnı nalezenı vsech bodu uvnitr dane vzdalenosti, a tak mohou byt pozadavkyna cas nizsı nez m× log (m) casovych jednotek.
Pozadavek na pamet’ i pro vysoko-dimenzionalnı data je m, protoze je nutneudrzovat pouze male mnozstvı dat pro kazdy bod (napr. znacku shluku k iden-tifikaci kazdeho bodu jako jadro, hranice nebo sum).
36
2.3.3 Silne a slabe stranky DBSCANu
Klady algoritmu jsou:
� Nepozaduje apriorne zadanou informaci tykajıcı se poctu shluku.
� Umı najıt shluky libovolnych tvaru. Dokaze dokonce urcit i shluky, kterese dokonale obklopujı (nesmı vsak byt propojeny).
� Bere v uvahu sum.
� Pozaduje pouze dva parametry a je vetsinou necitlivy vuci poradı boduv databazi (pouze body nachazejıcı se na hranici dvou ruznych klastrusi mozna vymenı prıslusnost k urcitemu klastru, pokud se zmenı jejichporadı v databazi).
Zapory algoritmu jsou:
� Nejbeznejsı pouzıvanou metrikou je Eukleidovska vzdalenost, avsak provysoko-dimenzionalnı data je volba teto metriky neefektivnı.
� Neoperuje dobre s datovymi mnozinami s menıcı se hustotou (hierarchickedatove mnoziny).
� Nehodı se pro vysoko-dimenzionalnı data kvuli obtıznemu definovanı hus-toty.
� Je velmi narocny pro vysoko-dimenzionalnı data, pokud pocıtanı nej-blizsıch sousedu vyzaduje vypocet mezi kazdymi dvema sousedy.
� Casova narocnost vypoctu je mnohem vyssı nez v predchozıch dvou prıpa-dech algoritmu Kmeans a hierarchickych metod.
Ponevadz DBSCAN operuje se shluky zalozenymi na hustote, je pomerne odolnyvuci sumu a umı pracovat se shluky libovolnych tvaru a velikostı, proto umınalezt mnohdy klastry, ktere nemohou byt zobrazeny jinymi algoritmy, jakymije napr. Kmeans. To je take duvodem jeho casteho pouzitı.
37
3 Testovanı
V nasledujıcı casti budou provedeny experimenty probranych shlukovych algo-ritmu - Kmeans, hierarchickeho shlukovanı a DBSCANu. Nejprve budou tes-tovany na simulovanych datech a pote na datech realnych dopravnıch.
3.1 Simulovana data
Prvnı zmınena data (simulovana) byla vytvorena ve trech formach. V kazdeforme dat je mozne nalezt mnozinu modelu, ktere reprezentujı shluky. Tatomnozina se bezne nazyva smes, jednotlive modely komponenty. Pro simulacibyla pouzita smes peti statickych komponent s normalnım rozdelenım sumu.
Prvnı data byla simulovana tak, ze jednotlive shluky jsou kompaktnı a jejichteziste jsou vzhledem k jejich velikosti daleko od sebe, ve druhem kroce bylatestovana data podobne struktury, ve ktere majı shluky zachovany polohy svychtezist’ a ktere jsou vsak lehce zasumena. U prvnıch dvou forem dat je mozne urcitshluky pouhym okem. Poslednı struktura dat jiz obsahuje velke mnozstvı sumu,a tak nelze rozlisit jednotlive shluky bez nejakeho algoritmu.
3.1.1 Testovanı Kmeans na simulovanych datech
Nejprve byla data testovana s algoritmem Kmeans. Kmeans je algoritmus vyzadu-jıcı urcenı parametru - pocet shluku (K). Je vsak mozne urcit pouze intervalpoctu shluku - < minimalnı pocet shluku, maximalnı pocet shluku >.
Kmeans pro pocet shluku <2, 10> Kmeans pro pocet shluku 5
Obrazek 21: Ukazka pouzitı algoritmu Kmeans na nezasumenych datech
38
Na leve casti obrazku byl zvolen interval poctu shluku <
2 shluky, 10 shluku > a byly nalezeny 4 shluky, pricemz prirozena struktura
dat skryva shluku 5. Duvodem, proc byly dva shluky spojeny, je vzdalenost,
resp. blızkost, tezist’ spojenych shluku. Shluky se nachazı relativne blızko
sebe ve srovnanı s ostatnımi klastry a navıc hustota datovych vzorku jim
prıslusejıcı je nızka. Shlukovanı bylo v prıpade volby 5 klastru kvalitnejsı.
Vysledek shlukovanı o 5 klastrech je zobrazen na prave casti obrazku 21.
Dalsım kladnym rysem pouzitı tohoto algoritmu je jeho vypocetnı nenarocnost -shluky byly nalezeny jiz po 3 iteracıch (resp. po trech iteracıch se prestala hybatteziste nalezenych klastru). Na druhou stranu je Kmeans uplny (viz Prıloha5.5) shlukovy algoritmus, takze nebyl uvazovan zadny sum ci outlieri a vsechnyvzorky byly zarazeny do klastru.
Jak jiz bylo receno na zacatku, algoritmus Kmeans byl otestovan i na dalsıchdvou formach zasumenych dat. Na obrazku 22 muzeme videt vysledek shlu-kovanı pri urcenı poctu shluku 5. Lze si vsimnout zejmena na prave castiobrazku, kde Kmeans tvorı shluky kuloviteho tvaru. I kdyz byla puvodnı datahodne zasumena, byly vytvoreny pomerne kvalitnı shluky (kulovite).
Lehce zasumena data Velmi zasumena data
Obrazek 22: Ukazka pouzitı algoritmu Kmeans na zasumenych datechNa leve casti obrazku byla pouzita data lehce zasumena, u kterych je jeste
mozne urcit shluky pouhym okem. Na prave casti obrazku jsou data ve 3.
forme - velmi zasumena. V obou prıpadech doslo k vytvorenı kvalitnıch ku-
lovitych shluku po probehnutı Kmeans algoritmu s urcenym poctem shluku
5.
3.1.2 Testovanı hierarchickeho algoritmu na simulovanych datech
V prıpade testovanı prvnıho typu dat (nezasumenych) pomocı hierarchickehoalgoritmu nebylo dosazeno tak kvalitnıho vysledku jako v prıpade algoritmuKmeans. Vysledek je zobrazen na obrazku 23.
39
Obrazek 23: Ukazka pouzitı hierarchickeho algoritmu na nezasumenych datechVysledkem shlukovanı byly 4 shluky, ktere vsak nevystihujı prirozenou struk-
turu dat. Duvodem muze byt konecne prirazenı prvku do shluku, a tedy na-
lezenı lokalnıho minima (viz 2.2.4).
Na tomto algoritmu byla testovana i dalsı simulovana (zasumena) data, alenebylo dosazeno zajımavych vysledku.
Na obrazku 24 jsou vykresleny dendrogramy pro zasumena data.
Dendrogram pro velmi zasumena dataDendrogram pro lehce zasumena data
Obrazek 24: Dendrogramy pro zasumena data
40
Na leve casti obrazku (jedna se o dendrogram mene zasumenych dat) je po-
slednı shluk vzdalen od ostatnıch, resp. je velka vzdalenost na ose y v den-
drogramu od naposledy vytvoreneho shluku, coz je zrejme dano vyskytem
nejakeho outlieru. Oproti tomu je na prave casti obrazku vykreslen dendro-
gram pro nejvıce zasumena data, ktery je komplexnejsı, protoze jsou zde data
rozmıstena rovnomerneji po cele plose (nevytvarı tedy prirozene shluky), a
tak nenı mozne najıt prvek, ktery by byl tak extremne vzdalen od ostatnıch
jako v predchozım prıpade.
3.1.3 Testovanı DBSCANu na simulovanych datech
Na zaver byla simulovana data zpracovana i algoritmem DBSCAN. Jak jiz bylozmıneno v 2.3.3, je DBSCAN velmi citlivy vuci nastavenı jeho zakladnıch para-metru, a to ε (polomer okolı uvazovaneho vzorku) a MinPts (minimalnı pocetvzorku kolem uvazovaneho vzorku). Dalsım charakteristickym znakem je, ze DB-SCAN provadı shlukovanı castecne (viz Prıloha 5.5), proto uvazuje sum. Muzetedy dojıt k tomu, ze nektere prvky nebudou zarazeny do zadneho shluku.
Ponevadz nepozaduje apriorne zadany pocet shluku, byly urceny parametry uprvnı formy dat (nezasumenych) tak, aby bylo nalezeno 5 prirozenych shlukua aby byl co nejmensı pocet nezarazenych prvku, coz se povedlo s hodnotouparametru Eps = 0.05 a MinPts = 10. Vysledek muzeme videt na obrazku25. Vsimneme si, ze nezarazene prvky lze uvazovat jako sum. Bylo dosazenokvalitnıho shlukovanı zejmena proto, ze shluky nejsou propojene a ze hustotashluku je pomerne stejna.
Obrazek 25: Ukazka pouzitı algoritmu DBSCAN na nezasumenych datech a prioptimalnı volbe parametru
41
Na obrazku 26 je demonstrovan vysledek shlukovanı, pokud byly meneny para-metry ε a MinPts.
Na leve casti obrazku bylo zmeneno MinPts = 10 na MinPts = 30, a
tak prvky musı byt obklopeny vetsım poctem prvku. Bylo nalezeno taktez
5 shluku, ale nebylo zarazeno temer 181 prvku, resp. 181 prvku bylo oznaceno
jako sum (na obrazku jsou zobrazeny pomocı pısmene M). Napravo byl
zmenen parametr Eps z Eps = 0.05 na Eps = 0.10, tudız se uvazuje vetsı po-
lomer okolo pocıtaneho prvku. Dusledkem toho je, ze dva shluky si navzajem
blızke byly slouceny do jednoho a nebyl nalezen zadny sum.
Zmenu parametru MinPts tedy lze vyuzıt, pokud jsme si vedomi, ze se v da-tech nachazı velke mnozstvı sumu. Pri zvetsenı MinPts dojde k vetsımu poctunezarazenych vzorku (sumu).
V prıpade zasumenych dat neprinesl algoritmus DBSCAN kvalitnı vysledky.V druhem prıpade mırne zasumenych dat pri vhodne zvolenych parametrech zpredchozıho prıpadu prinesl pouze jeden shluk, pri hledanı lepsıho nastavenı bylstale vysledkem jeden shluk. Pokud byl pocet shluku vetsı, dochazelo k oznacenıvelkeho mnozstvı prvku za sumove (37 %). Ve tretı forme simulovanych dat bylnalezen jeden shluk, a to i pri ruznych volbach parametru. Rozdıl byl pouze vruznem poctu nezarazenych, tedy sumovych, prvku.
V tabulce 6 jsou zobrazeny vysledky shlukovanı v zavislosti na ruzne forme data na ruzne volbe parametru. Lze si vsimnout, ze nejkvalitnejsı vysledek, co setyce poctu shluku a mnozstvı sumu, je doopravdy u dat 1 (nezasumenych) privolbe Eps = 0.05 a MinPts = 10.
Tabulka 6: Vysledky shlukovanı pomocı algoritmu DBSCAN u ruznych typudat a pri ruznych parametrech
3.2 Realna data
Pro testovanı realnych dat byla pouzita data zıskana z jızd testovacıho vozuSkoda, ve kterem jsou zakomponovany prıstroje merıcı ruzne veliciny. Pro tes-tovanı byly vybrany veliciny plyn a rychlost. Jızdy automobilu probıhaly jak vintravilanu, tak v extravilanu. Puvodnı strukturu dat je mozne si prohlednout naobrazku 27. Tato data byla opet podrobena testovanı pomocı trı jiz zminovanychalgoritmu.
Obrazek 27: Realna dataOsa x zobrazuje rychlost [km/h]. Na ose y je vyjadren plyn [%]. Lze si jiz
pomocı pouheho oka vsimnout ruznych skupin dat. Nutne je vsak je striktne
rozdelit.
Velmi kvalitnıho vysledku bylo dosazeno pomocı algoritmu Kmeans, coz je zob-razeno na obrazku 28.
43
Obrazek 28: Pouzitı Kmeans na realnych datechKmeans nalezl 5 shluku, resp. 5 pracovnıch modu, kopırujıcıch prirozenou
strukturu sebranych dat. I kdyz jsou pro Kmeans charakteristicke kulovite
shluky, byly nalezeny ostra rozhranı mezi shluky. Prıcinou muze byt vetsı
hustota dat ve smeru osy z.
Jak jiz bylo nastıneno v 1.1, byly pomocı shlukovanı nalezeny pracovnı mody.Jednotlive shluky odpovıdajı ruznym typum jızdy - napr. modry shluk zrejmeodpovıda jızde ve meste, protoze je charakterizovan nızkou rychlostı a malouhodnotou plynu. Naopak ruzovy shluk je typicky pro jızdu na dalnici o vyssırychlosti s vyssım plynem.
Taktez velmi dobry vysledek byl nalezen pomocı hierarchickeho shlukovanı, jaklze videt na obrazku 29. Hierarchicky algoritmus byl vsak vypocetne narocnejsı.
44
Obrazek 29: Pouzitı hierarchickeho shlukovanı na realnych datechZa pomocı hierarchickeho shlukovanı bylo nalezeno opet 5 shluku. Lze si
vsimnout, ze jsou shluky znovu rozdeleny ostrym rozhranım.
Nejhorsı vysledek byl docılen za pouzitı DBSCANu. Nejenze byl algoritmusvypocetne narocny na cas, ale pri ruznem nastavovanı parametru Eps a MinPtsbylo dosazeno spatnych vysledku - bud’ byl nalezen jeden shluk a velke mnozstvısumovych vzorku (obrazek 30), nebo bylo nalezeno velke mnozstvı klastru (obrazek31) opet vcetne velkeho mnozstvı sumu.
Obrazek 30: Nalezenı jednoho shluku za pouzitı DBSCANu na realnych datechV tomto prıpade byly vytvoreny pouze dva shluky, pricemz vetsı z nich obsa-
huje temer 98 % ze vsech vzorku. Taktez byly nektere vzorky oznacene jako
sum. Shlukovanı v tomto prıpade lze povazovat za nekvalitnı.
45
Obrazek 31: Nalezenı vıce shluku za pouzitı DBSCANu na realnych datechBylo nalezeno velke mnozstvı shluku, coz je v nasem prıpade nepozadujıcı.
Vzorky oznacene pısmenem M jsou nezarazene, tedy sumove, kterych bylo
oznaceno 45 %. Vysledek shlukovanı je opet velmi nekvalitnı.
46
4 Zaver
Cılem prace bylo nalezt algoritmy, ktere se pouzıvajı pro klastrovanı dat. Zameri-la jsem se na oblast dopravy, konkretne na analyzu dat merenych na jedoucımaute. V praci byly vytypovany tri algoritmy - Kmeans, hierarchicky algoritmus aDBSCAN, ktere byly podrobeny teoretickemu rozboru a nasledne byly testovanyna simulovanych a realnych dopravnıch datech. Je vsak nutne podotknout, zeexistuje velka propast mezi simulacı a realnymi daty.
Simulovana data byla pouzita, protoze v jejich prıpade je mozne je nastavit pa-rametry, a tak prakticky demonstrovat vlastnosti algoritmu popsane v teoretickecasti. Na simulovanych datech je mozne vysledky klastrovanı dobre porovnat.Nejlepsıho vysledku v tomto prıpade bylo dosazeno pomocı algoritmu Kmeans.Duvodem je, ze byly pro simulaci pouzite kulovite shluky, coz je vhodne pravepro tento algoritmus. Jako nejmene vhodny zejmena pro zasumena data se je-vil algoritmus DBSCAN kvuli velkemu mnozstvı sumu a nevhodnemu, at’ uzvysokemu, ci nızkemu, poctu shluku.
Shlukove algoritmy byly aplikovany i na data realna, protoze ta se objevujı vnormalnım zivote. Tento typ dat je predmetem zkoumanı v dopravnım vyzkumu.I zde bylo dosazeno dobreho vysledku pomocı Kmeans. Velmi kvalitnı vysledekpodal algoritmus hierarchicky. DBSCAN lze opet oznacit za velmi nekvalitnı.Pro dalsı vyzkum tedy doporucuji hierarchicke shlukovanı, a to nejen kvulitomu, ze ukazuje dobre vlastnosti v pokrytı klastru, ale kvuli moznosti volbylibovolneho poctu klastru (dle volby rozlisovacı urovne).
47
Reference
[1] Pang-Ning Tan, Michael Steinbach, Vipin Kumar : Introduction to Datamining : Pearson, Addison Wesley : ISBN 0-321-32136-7, 2006
[2] Alena Lukasova, Jana Sarmanova : Metody shlukove analyzy : SNTL - Na-kladatelstvı technicke literatury, Praha 1985
[3] A.K.Jain, M.N.Murty, P.J.Flynn : Data clustering- A Review :http://eprints.iisc.ernet.in/273/1/p264-jain.pdf : September 1999
[4] V. Kumar : Cluster analysis : Basic concepts and Algorithms : http://www-users.cs.umn.edu/˜kumar/dmbook/ch8.pdf :
48
5 Prıloha
5.1 Co je shlukova analyza (cluster analysis)?
Shlukova analyza je technika rozdelujıcı do skupin vzorky, ktere jsou datovehocharakteru a ktere popisujı urcite predmety. Cılem je, aby si vzorky ve shlukubyly navzajem podobne (prıbuzne) a naopak odlisne s vzorky, ktere patrı shlukumjinym. Cım jsou vzorky ve shluku prıbuznejsı, tedy homogennejsı, a cım jsourozdıly mezi skupinami vetsı - heterogenejsı, tım je shlukovanı kvalitnejsı apresnejsı.
� Uved’me prıklad z dopravy. Jsou sebrana data ve forme intenzity z pozemnıkomunikace. Ukolem shlukove analyzy muze byt urcit dobu ve dne, kdy jeintenzita nızka, strednı a vysoka, tedy udelat skupiny (shluky) v namereneintenzite, pricemz zakladnım atributem je zde pocet detekovanych aut.
V mnoha situacıch nenı samotny pojem shluk (anglicky cluster, pozdeji pouzıvanhomonymnı pojem klastr) spravne definovan, resp. definovatelny. K lepsımuporozumenı obtıznosti v rozhodovanı, co se skryva pod pojmem shluk, uvazujmeobrazek 32, ktery ukazuje 20 bodu a 3 rozdılne zpusoby rozdelenı jej do shluku.Tvary znacek ukazujı prıslusnost ke shlukum.
a) b)
c) d)
Puvodni data
4 shluky 6 shluku
2 shluky
Obrazek 32: Ruzne zpusoby rozdelenı vzorku do shlukuNa obrazku b), c) a d) jsou dana data rozdelena do dvou, ctyr a sesti shluku.
Nicmene je jiz na prvnı pohled viditelne, ze lze oba shluky z b) rozdelit do
trı podshluku, a to i na zaklade pouheho lidskeho zraku, ktery nevyzaduje
zadnou teoretickou prıpravu. Narozdıl od casti obrazku c), kde jsou vytvoreny
shluky 4 na zaklade nejake informace navıc. Tento obrazek ilustruje, ze defi-
nice shluku nenı presna a ze nejlepsı definice zalezı na prirozenosti a puvodu
dat a na pozadovanych vysledcıch.
Segmentace a extrakce
Termıny segmentace a rozdelovanı jsou nekdy povazovany za synonyma. Ve shlu-kovanı jsou vsak pouzıvany pro ruzne typy dat. Pojem rozdelovanı je vetsinou
49
pouzıvan ve spojenı s technikami, ktere rozdelujı grafy na podgrafy a tedyhovorıme spıse o prıpadu hierarchickeho shlukovanı. Kdezto segmentace castoreferuje o rozdelovanı dat do skupin, pricemz pouzıva jednoduche techniky (zob-razenı muze byt rozcleneno do segmentu zalozenych pouze na rozlisenı pixelua barev, nebo mohou byt lide rozdeleni do skupin dle jejich prıjmu). Pojemsegmentace tedy muzeme spıse vyuzıt v nehierarchickem shlukovanı. Nektereshlukove algoritmy tedy pracujı s rozdelenymi grafy a jine s obrazky ruznychtypu.
Klasifikace vs. shlukovanı
V teto praci se budu zabyvat zejmena statickou analyzou dat, tedy klasifikacıjiz namerenych dat. Shlukova analyza je spojena s dalsımi technikami, kterese pouzıvajı k rozdelovanı vzorku do skupin. Shlukovanı je nekdy povazovanoza druh, ci soucast klasifikace, ve kterem je oznacenı vzorku tvoreno urcitouznackou shluku. Lepe receno - shlukova analyza ma slouzit jako prostredek kzıskanı klasifikace. V dopravnı oblasti napr. potrebujeme klasifikovat druh auta,ktery projel nad urcitym detektorem, typ komunikace podle jejıho slozenı ci vnasem prıpade jednotlive pracovnı mody.
� Klasifikace muze byt povazovana za kontrolovatelnou (anglicky - super-vised), nekdy oznacovanou jako ucenı s ucitelem – neoznackovane vzorkyjsou prideleny trıde znacek pouzıvajıcı model, ktery se vyvinul ze vzorkuse znamou trıdou znacek. Jinak receno mame informaci o tom, jak danymodel ma vypadat a jak se ma chovat. Obecne lze rıci, ze se jedna ozarazovanı dat do klastru.
� Shlukova analyza je vsak uvazovana za ucenı bez ucitele (anglicky - unsu-pervised learning), a tudız tato technika vetsinou nema informaci o tom,jak se ma dany model chovat, a tak se jeho chovanı vyvıjı v prubehushlukovanı. Obecne vzato se zde jedna o vytvarenı samotnych klastru.
Objekty shlukovanı
Je vhodne se take zmınit o objektech shlukovanı, tedy objektech urcenych keklasifikaci, a jejich znacıch. Provadıme-li klasifikaci jednım z algoritmu shlu-kove analyzy, musı byt splneny urcite podmınky. Na kazdem objektu lze urcit pznaku, a tak je ke kazdemu objektu prirazena p-tice hodnot znaku. Je-li napr.mnozinou objektu mnozina urcitych druhu aut, stanovıme soubor znaku, jakojsou delka, vyska, hmotnost, atd. Pote pro kazdy detekovany objekt zazna-mename va danem poradı stavy, ve kterych se jednotlive znaky nachazejı. Jebezne prirazovat stavum znaku jejich cıselne kody, ktere predstavujı hodnotyznaku. Objektem pro shlukovanı je tedy p-tice hodnot vybranych znaku (p-rozmerny vektor cısel), ktera je identifikatorem daneho objektu. Poskladanımvektoru pod sebe pak zıskame matici dat, kde radky jsou tvoreny objekty asloupce znaky.
50
Znaky mohou nabyvat ruznych hodnot stavu. Mnozinu stavu mohou tvoritnasledujıcı moznosti (uvadeny jsou prıklady pro objekt - auto).
� interval realne osy - napr. delka auta, hmotnost auta, vyska auta, atd.
� konecna (spocetna) mnozina cısel - napr. pocet kol, dverı, valcu, atd.
� dvojice logickych hodnot (vetsinou pravdivy/nepravdivy vyrok) - tytoznaky jsou bezne nazyvany dichotomicke. Jsou vetsinou kodovany po-mocı jednicek (pravda) a nul (nepravda). Prıkladem pro druh auta je -benzınovy motor - ano / ne, ESP - ano / ne, apod.
� konecna mnozina popisujıcıch termınu - zalezı jenom na nas, jake popi-sujıcı termıny si sami zvolıme, resp. z jakych stavu znaku budeme vybırat.Napr. spotreba auta - nızka, strednı, vysoka.
5.2 Soucasti ulohy shlukovanı
Obecne kroky shlukovanı
1. Reprezentace dat (muze zahrnovat i extrakci a/nebo selekci), filtrace dat.
2. Definice merenı blızkosti vzorku, ktere je vhodne pro danou oblast dat(urcenı typu metriky).
3. Shlukovanı (klastrovanı).
4. Modelovanı dat.
5. Zhodnocenı vystupu.
V nasem prıpade systemu ridic - automobil se jednotlive kroky budou vztaho-vat v prıpade reprezentace dat na filtraci namerenych dat na systemu od out-lieru a sumu, kterı by nasi analyzu mohly znehodnotit. Vyskyt outlieru a sumumuze byt dusledkem nekvalitnıch mericıch prıstroju ci vyskytem extremnıchridicu (jızda po meste 100 km/h, ci jızda po dalnici 30 km/h). Blızkost vzorkubude stanovovana pomocı Eukleidovske metriky. V dalsıch kapitolach budouprobrany algoritmy zabyvajıcı se statickou analyzou dat, nicmene pro praxi jesamozrejme vhodnejsı dynamicke hodnocenı pracovnıch modu, tedy dynamicketvorenı klastru, pro ktere se zamerıme na Bayesovske metody v nasledujıcım ob-dobı. V modelovanı dat budou vytvorena centra jednotlivych pracovnıch modu.Zhodnocenı vystupu jiz prinası samotnou interakci mezi ridicem a automobi-lem, kdy bude ridici sdelen typ jızdy, resp. bude ridic varovan, pokud se budenachazet v nebezpecnem modu.
Reprezentace dat se tyka otazky poctu trıd, mnozstvı vzorku a poctu, typu avahy atributu vhodnych danemu shlukovemu algoritmu. Nektere z techto infor-macı nemusı byt ovlivnitelne. Selekce atributu je proces identifikovanı nejefek-tivnejsı podmnoziny z puvodnıch atributu za ucelem jejıho nasledneho pouzitı
smycku, kde vystup z procesu shlukovanı (klastrovanı) muze zpetne ovliv-
nit jak cast extrakce a selekce atributu, tak i vypocet podobnosti, resp.
vzdalenosti.
ve shlukovanı. Extrakce atributu je pouzitı jedne nebo vıce transformacı zevstupnıch vlastnostı, aby byly vytvoreny nove charakteristicke, vyznacne atri-buty. Jedna nebo obe z techto technik mohou byt pouzity k obstaranı vhodnemnoziny atributu, ktere jsou pak pouzity ve shlukovanı.
Podobnost vzorku je obvykle vnımana jako opak vzdalenosti, ktera je definovanapro pary vzorku. Jednoduche merenı vzdalenosti, jakou je zejmena Eukleidovskavzdalenost, muze byt casto pouzito ke zobrazenı nepodobnosti mezi dvemavzorky, zatımco jina merenı jsou pouzıvana k charakterizovanı podobnosti mezivzorky.
Cast klastrovanı muze byt vykonana ruznymi zpusoby. Shlukovanı muze bytpevne (rozdelenı dat do skupin) nebo fuzzy, hierarchicke nebo nehierarchicke.
Modelovanı dat je proces vybıranı jednoduche a srozumitelne reprezentace mnozi-ny dat. Ve shlukovanı je modelovanı dat kompaktnı popis kazdeho shluku, ob-vykle pomocı popisu modelu nebo reprezentativnıch vzorku, kterymi muzou bytnapr. stredy (centra) shluku.
Ohodnocenı vystupu shlukovanı
Zhodnocenı vystupu jednotlivych technik shlukovanı ma nekolik stranek. Jednaje vlastnı zhodnocenı oblasti dat spıse nez samotnych algoritmu.
Narozdıl od toho je analyza spravnosti shluku zejmena o zhodnocenı vystupujednotlivych procedur. Casto tato analyza pouzıva specificke merıtko optima-lity, i kdyz jsou tato kriteria znacne subjektivnı. Zhodnocenı spravnosti je ob-jektivnı a slouzı k rozhodnutı, zda je vystup smysluplny. Vysledek shlukovanıje spravny, platny, kdyz se nemuze vyskytovat nahodne nebo v zavislosti nanejakem konkretnım shlukovem algoritmu.
Pro statisticke postupy existujı tri typy validacnıch metod:
� Externı zhodnocenı spravnosti porovnava vzniklou strukturu s pozadavky.
� Internı zkouska spravnosti se snazı rozhodnout, zda je struktura skutecnevhodna pro dana data.
52
� Relativnı test porovnava dve struktury a merı jejich relativnı hodnotu.
5.3 Ruzne druhy shluku
Shlukovanı se zameruje na nalezenı uzitecnych skupin vzorku - shluku, kdy jeuzitecnost definovana cıly datove analyzy. Existuje nekolik rozdılnych pojmupro shluky ukazujıcı se uzitecne v praxi. Aby mohly byt vizualne ilustrovanyrozdıly mezi ruznymi druhy shluku, pouzıvame dvourozmerne soustavy, napr.na obrazku 34. Nicmene je dulezite zduraznit, ze druhy a vlastnosti shluku,ktere jsou zde popsany, jsou stejne tak platne i pro jine druhy dat.
����������������������������
����������������������������
��������
��������
������������������������
������������������������
�������� ��
������
a) Presne vymezene shluky b) Zalozene na modelu
c) Zalozene na blizkosti d) Zalozene na hustote
e) Konceptualni shluky
Obrazek 34: Ruzne typy shluku ilustrovane pomocı dvourozmerneho prostoru
Existuje nekolik moznych pohledu, jak shluky rozdelit. Pro nase ucely, tedy prodopravnı problematiku, jsou zakladem shluky zalozene na modelu. Shlukem jezde mnozina bodu generovanych stejnym modelem.
Presne vymezene shluky
Shluk je skupina vzorku, ve ktere jsou si vzorky vzajemne vıce podobne (menevzdalene) nez s vzorky jinych shluku. Shluky jsou ohraniceny a nekdy je zvykemspecifikovat hranici tak, ze vsechny vzorky ve shluku si musı byt dostatecnepodobne (blızke) navzajem. Tato “idealisticka” definice shluku je uspokojujıcıpouze tehdy, kdyz data obsahujı prirozene, puvodnı shluky, ktere jsou dostivzdalene od sebe navzajem.
V casti a) obrazku 34 je prıklad presne vymezenych shluku, ktere se skladajıze dvou skupin bodu ve dvourozmernem prostoru. Vzdalenost mezi kazdymi
53
dvema body v ruznych skupinach je vetsı nez vzdalenost mezi dvema body veskupine. Presne vymezene shluky nemusı byt kulovite, ale mohou mıt jakykolivtvar.
Shluky zalozene na modelu
Shluk je soustava vzorku, ve ktere jsou vzorky generovany spıse jednım modelemnez ostatnımi. Pro data se spojitym prubehem je casto modelem shluku jehoteziste (prumer vsech bodu ve shluku). Kdyz nelze teziste smysluplne vypocıtat,napr. jsou-li data kategoricka, je casto modelem medoid, coz je nejreprezenta-tivnejsı prvek shluku. Pro mnoho druhu dat muze byt model definovan nejvıcestredovym prvkem. V takovych prıpadech hovorıme o shlucıch zalozenych nacentru. Takove shluky majı sklon byt kulovite. Obrazek 34 b) ukazuje prıkladprave takovychto centralnıch shluku.
Shluky zalozene na grafech
Pokud jsou data reprezentovana pomocı grafu, kde jsou uzly na nejnizsı urovnivzorky a hrany reprezentujı spojenı mezi vzorky, pak muze byt shluk definovanjako spojujıcı slozka - skupina vzorku, ktere jsou spojene mezi sebou navzajema kde nenı zadne spojenı s vzorky mimo skupinu.
Dulezity prıklad shluku zalozenych na grafech jsou blızke (souvisle) shluky – dvavzorky jsou spojene pouze tehdy, kdyz se nachazejı do specifikovane vzdalenostimezi sebou. Kazdy vzorek v blızkem shluku je blıze k dalsım vzorkum ve shlukunez k jakemukoli vzorku v klastru jinem. Obrazek 34 c) ukazuje prıklad ta-kovychto shluku pro dvourozmerny prostor.
Tato definice shluku je uzitecna, kdyz jsou shluky nerovnomerne nebo prople-tene, pricemz mohou nastat problemy, kdyz je prıtomen sum (jako v nasemprıpade) – maly most prvku muze splynout do dvou rozdılnych shluku.
Jine typy shluku, ktere jsou zalozene na grafech, jsou take mozne. Jeden takovyprıstup definuje shluk jako zajmovou skupinu – soustava vrcholu v grafu, kterejsou uplne propojeny navzajem. Pokud pridame spojenı mezi vzorky v poradıdle jejich vzdalenosti mezi sebou samymi, je shluk vytvoren, kdyz soustava datvytvarı zajmovou skupinu. Tyto shluky take inklinujı k tomu mıt kulovy tvar.
Shluky zalozene na hustote
Shluk je husta oblast vzorku, ktera je obklopena oblastı s hustotou nizsı. Castobrazku 34 d) ukazuje takoveto shluky pro data z c), do kterych jsou pridanyslozky sumu. Tyto dva kruhovite shluky nesplyvajı jako v podobrazku c), protozese most mezi nimi zvolna menı v sum. Podobne ohyb na podobrazku c) se zvolnastava sumem a netvorı shluk na podobrazku d).
Definice shluku pomocı hustoty se vetsinou pouzıva, kdyz jsou shluky nepravi-delne, propletene nebo pokud je prıtomen sum a outlieri.
54
Konceptualnı shluky
Obecne muzeme shluk pojmout jako skupinu vzorku, ktere sdılejı nejakou ob-last. Tato definice vesmes zahrnuje vsechny definice predesle – napr. vzorky veshluku definovanem dle modelu sdılejı oblast, ktera je kolem teziste. Nicmenetato definice obsahuje take nove typy shluku – uvazujme shluky na podobrazku34 e). Trojuhelnıkova oblast – shluk je sousednı oblastı obdelnıkoveho tvarua dale je tam oblast kruhoveho tvaru. V obou prıpadech by shlukove algo-ritmy potrebovaly velmi specificky koncept shluku, aby doslo k uspesnemu urcenıtechto shluku.
5.4 Merenı podobnosti
Ponevadz je podobnost zasadnım pojmem jak v samotne shlukove analyze, tak vdefinici shluku, jejı merenı mezi dvema vzorky ze stejneho vychozıho prostoru jedulezite pro vetsinu shlukovych algoritmu. Kvuli velke rozmanitosti zakladnıchtypu a mer, musı byt merenı vzdalenosti zvoleno velmi opatrne. Nejbeznejsımzpusobem pro vypocet mıry podobnosti mezi vzorky, nebo spıse pro merenınepodobnosti - resp. vzdalenosti, je pouzitı metriky.
V matematice je metrika (neboli funkce vzdalenosti) funkce, ktera definujevzdalenost mezi elementy urcite mnoziny. Tato funkce vzdalenosti se casto vmatematice oznacuje ρ. Mnozina s metrikou se nazyva metricky prostor. Met-rika vytvarı urcitou topologii na mnozine, coz vsak neplatı i v opacnem prıpade– ne vsechny topologie mohou byt vytvoreny metrikou. Pokud ma topologickyprostor topologii, ktera je popsana pomocı metriky, je dany prostor metrizova-telny.
V geometrii je slovo metrika taktez pouzıvano jako struktura definovana jen vevektorovem prostoru, ktery je spravneji oznacen jako metricky tenzor.
Pro metriku jako funkci vzdalenosti platı nasledujıcı axiomy:
� axiom nezapornosti :ρ(x, y) ≥ 0
� axiom totoznosti (jedna – li se o funkci vzdalenosti spojujıcı prvek se sebousamym) :
ρ(x, y) = 0 ⇔ x = y
� axiom symetrie :ρ(x, y) = ρ(y, x)
� trojuhelnıkova nerovnost :
ρ(x, z) ≤ ρ(x, y) + ρ(y, z)
55
Existuje nekolik zpusobu jak vyjadrit axiomy metrik a jak dat vzniknout ruznympojmum obecnych metrickych prostoru. Tato zobecnenı mohou byt kombinovana.Terminologie pouzita pro jejich popis nenı kompletne standardizovana. Zejmenave funkcionalnı analyze casto pseudometrika pochazı z normalnıho vektorovehoprostoru.
Rozsırena vs. konecna metrika
Nekterı autori povolujı, aby vzdalenost dosahovala hodnoty nekonecna, to zna-mena, ze vzdalenosti jsou nezaporna cısla na rozsırene cıselne ose. Takova funkcese nazyva rozsırena metrika.
V doprave se spıse setkavame s metrikou konecnou - napr. delka kolony, resp.pocet aut v nı, je konecne cıslo, dale pak charakteristiky jako intenzita, ci hus-tota.
Minkowskeho (Eukleidovska) metrika
Nejznamejsı metrika pro spojita data je Eukleidovska vzdalenost, ktera je special-nım prıpadem Minkowskeho metriky. Eukleidovska vzdalenost se bezne pouzıvapro zhodnocenı blızkosti vzorku ve dvou – nebo trı-rozmernem prostoru. Nevyho-dou prımeho pouzitı Minkowskeho metriky je tendence vetsıch vzorku domino-vat ostatnım. Resenı tohoto problemu zahrnuje normalizaci spojitych prubehu.
Minkovskeho metriku lze obecne vyjadrit pomocı vztahu (6).
dp(xi, xj) = (
d∑k=1
|xi,k − xj,k|p)1p (6)
d2(xi, xj) =
√√√√ d∑k=1
(xi,k − xj,k)2 (7)
Pokud za p dosadıme cıslo 1, vysledkem bude metrika Manhattan, ktera se vdopravnı problematice vyskytuje pomerne casto. Pouzijeme ji naprıklad, pokudchceme urcit vzdalenost mezi dvema mısty ve meste za podmınky, ze se musımepohybovat pouze v na sobe kolmych blocıch. Situace je zobrazena na obrazku35. Na tomto obrazku je vzdalenost mezi body A a B rovna 22. Vsimneme si,ze vzdalenost je stejna pro vsechny zvolene trasy - cervena, zluta i modra. Jetedy jedno, kudy cestu volıme, coz je vyhoda metriky Manhattan.
Pokud za p dosadıme cıslo 2, vysledkem bude Eukleidovska (viz vztah (7)),ktera se pouzıva nejen v doprave nejvıce. Lze ji pouzıt naprıklad opet v prıpadeurcovanı vzdalenosti mezi dvema mısty ve meste, pokud vsak cesty ve mestenejsou usporadany do pravidelne mrızky na sebe kolmych ulic. Na obrazku 36 lzevidet velikost Eukleidovske vzdalenosti. Pro lepsı srovnanı techto dvou metrikbyla zachovana puvodnı mrızka ulic.
56
A
B
Obrazek 35: Ukazka pouzitı metriky Manhattan
A
B
Obrazek 36: Ukazka pouzitı Eukleidovske metriky
Mahalanobisova metrika
Linearnı korelace muze zdeformovat merenı vzdalenosti – tato deformace muzebyt zavedena pouzitım ctvercove Mahalanobisovy vzdalenosti. Mahalanobisovuvzdalenost lze vyjadrit pomocı vztahu (8).
dM - oznacuje ruzne vahy pro rozdılne atributy, ktere jsou zalozene na svychodchylkach a na linearnıch korelacıch.
Implicitne se predpoklada, ze hustoty majı Gaussovo rozlozenı pravdepodobnosti.
Nektere shlukove algoritmy pracujı s maticemi vzdalenostı namısto s puvodnımnozinou vzorku. Je uzitecne v takovychto situacıch prepocıtat vsechny n(n−1)/2 hodnoty vzdalenostı pro n vzorku a ulozit jej do symetricke matice. Vypocetvzdalenostı mezi vzorky s nejakymi nebo vsemi atributy, ktere nejsou spojite,je problematicke, protoze ruzne typy atributu nemusı byt porovnatelne.
57
Merenı vzdalenosti na zaklade kontextu (MND)
Existuje nekolik metod merenı vzdalenosti, ktere berou v uvahu i vliv okolnıchsousednıch bodu. Tyto body se nazyvajı kontext. Podobnost mezi dvema bodyxi a xj dane kontextem je popsano vztahem (9), kde ξ je zmınenym kontextem(soustava okolnıch bodu).
s(xi, xj) = f(xi, xj , ξ) (9)
Jednou z metrik pouzıvajıcıch kontext je vzdalenost spolecneho sousedstvı, kteraje bezne oznacovana jako MND (mutual neighbor distance) a ktera je danavztahem (10), kde NN(xi, xj) je cıslo souseda xj vzhledem k xi.
MND(xi, xj) = NN(xi, xj) +NN(xj , xi) (10)
y
x
y
x
y
x
y
x
A
B
C
A
B
C
D
E F
Podobnost vzorku A a B vetsi nez B a C Po zmene kontextu je podobnost B a C vetsi nez B a A
Obrazek 37: Vzdalenost MNDV leve casti jsou si vzorky A a B vıce podobne (mene vzdalene) nez vzorky
A a C, kdezto v prave casti po zmene kontextu jsou si vıce podobne vzorky
B a C nez B a A.
Obrazek 37 je nazornym prıkladem.
V leve casti je nejblizsım sousedem A vzorek B, coz platı i obracene, tedy nej-blizsım sousedem B je A, takze platı :
NN(A,B) = NN(B,A) = 1
a MND mezi A a B je 2. Dale platı :
NN(B,C) = 1,
ale NN(C,B) = 2, z cehoz plyne MND(B,C) = 3. Prava cast je porızenaz leve pridanım 3 novych bodu D, E a F. Nynı platı MND(B,C) = 3 aMND(A,B) = 5. Vzdalenost mezi A a B vzrostla dıky pridanı dodatecnychbodu, i kdyz samotne body A a B zustaly na mıste.
MND vzdalenost nenı metricka, protoze nesplnuje zakladnı axiom, a to trojuhel-nıkovou nerovnost. Nehlede na to byla MND uspesne uplatnena v nekolika shlu-kovych aplikacıch. Tento fakt podporuje hledisko, ze nepodobnosti (vzdalenosti)nemusı byt striktne metricke.
58
� Watanabuv teorem o osklivem kacatku :”
Pokud pouzijeme konecnou mnozi-nu atributu, ktere jsou schopne rozlisit kazde dva uvazovane vzorky, pocetatributu, ktere sdılejı prave ony dva vzorky, je konstantnı a nezavisly navyberu vzorku.“
Z tohoto teoremu vyplyva, ze je mozne vytvorit libovolne dva stejne podobnevzorky dıky zakodovanı jich pomocı dostatecne velkeho poctu atributu. V dusled-ku toho jsou dva libovolne vzorky stejne (pokud tedy nepouzijeme dodatecnouinformaci o oblasti).
Metrika zalozena na konceptualnıch shlucıch
V prıpade konceptualnıho shlukovanı je definovana podobnost mezi xi a xjnasledovne :
s(xi, xj) = f(xi, xj , ϕ, ξ), (11)
kde φ je mnozina predem definovanych konceptu. Situace je ilustrovana pomocıobrazku 38.
xx
x
x x x xx
xxxxx x
x x
x x
xx
x
x
x
xx
x
x
xx
x
x
x
xx
x
x
xx
y
x
A
B
C
Obrazek 38: Konceptualnı podobnost mezi vzorky
Zde je Eukleidovska vzdalenost mezi A a B mensı nez mezi body B a C. Nicmenena body B a C muze byt nahlızeno jako na sobe si podobnejsı nez A a B,protoze B a C patrı do stejne casti konceptu (elipsy) a A je soucastı jineho- obdelnıku. Konceptualnı merenı podobnosti patrı mezi nejobecnejsı zpusobmerenı podobnosti.
Divergence Kullback-Leibler
V teorii pravdepodobnosti a v informacnı teorii se vyuzıva zejmena divergenceKullback-Leibler (oznacovana KL). Nejedna se prımo o metriku, protoze ne-splnuje jeden ze zakladnıch axiomu platnych pro metriky, a to axiom symetrie.Obecne je to nesymetricke merenı rozdılnosti mezi dvema pravdepodobnostnımirozdelenımi P a Q. P vetsinou reprezentuje realnou distribuci dat, merenı nebo
59
vypoctenou teoretickou distribuci - tedy znamou funkci f . Naopak Q charakte-risticky predstavuje nejakou teorii, model, popis, nebo aproximaci rozdelenı P- cili hledanou funkci f .
KL divergence je zvlastnı prıpad sirsı skupiny odchylek, ktere se nazyvajı f - od-chylky. Puvodne byly predstaveny Solomen Kullbackem a Richardem Leibleremv 1951 jako usmernene odchylky mezi dvema distribucemi.
� Definice : Pro pravdepodobnostnı rozdelenı f a f diskretnı, ci spojitenahodne veliciny se spolecnym suportem je KL vzdalenost definovananasledovne :
DKL(f || f) =∑i
f(i)logf(i)
f(i), resp. DKL(f || f) =
R
f(x)logf(x)
f(x)dx
(12)Pozn. : KL vzdalenost je definovana jen tehdy, pokud je f > 0 a f > 0pro vsechny hodnoty i a pokud f a f dajı po sumaci 1.
� Vztah k metrice : Kullback-Leibler vztahy jsou taktez razeny do met-rickych vzdalenostı v oblasti pravdepodobnostnıch rozdelenı, ale toto tvr-zenı nenı uplne korektnı, protoze KL odchylka nenı symetricka. Dukazemje nesplnenı trojuhelnıkove nerovnosti a neplatnost vety o symetricnosti,protoze vzdalenost KL z f dof nemusı byt stejne velka jako KL z f do f .
DKL(f || f) 6= DKL(f || f)
I navzdory temto faktum generuje KL topologii v oblasti obecnych pravdepodob-nostnıch rozdelenı. Konkretneji receno – jestlize mame posloupnost rozdelenıf1, ..., fn takovou, ze platı
limn→∞DKL(fn||f) = 0 , pak fn → f .
5.5 Ruzne druhy shlukovanı
Jakekoliv seskupenı vzorku je bezne nazyvano jako shlukovanı a v teto castibudeme rozlisovat jeho ruzne druhy.
Hierarchicke a nehierarchicke shlukovanı
Zakladnım rozdelenım shlukovych technik je hierarchicke a nehierarchicke. Nehi-erarchicke shlukovanı je jednoduse rozdelenı mnoziny vzorku do neprekryvajıcıchse disjunktnıch podmnozin – shluku tak, ze kazdy vzorek nalezı prave jednepodmnozine.
Pokud pripustıme fakt, ze shluky mohou mıt podshluky a ze existuje vztahnadrazenosti a podrazenosti, hovorıme o hierarchickem shlukovanı. Jedna se omnozinu vkladanych shluku, ktere jsou organizovany jako strom. Kazdy uzel
60
(shluk) stromu (krome koncovych uzlu) je sjednocenı podrazenych podmnozin,a tudız je koren stromu shluk obsahujıcı vsechny vzorky. Velmi casto jsou listymnoziny s jedinym prvkem, tedy samotne vzorky.
Hierarchicke shlukovanı se dale muze delit na aglomerativnı a divizivnı. Delenı ztohoto hlediska souvisı s algoritmickou strukturou. Aglomerativnı prıstup zacınas kazdym vzorkem jako se samostatnym shlukem a postupne spojuje vzorky(shluky) dohromady do te doby, nez je splneno predem stanovene kriterium(napr. to muze byt pozadovany pocet shluku). Narozdıl od tohoto postupuzacına divizivnı shlukovanı s jednım shlukem, ktery obsahuje veskere vzorkyv dane mnozine a postupne jej rozclenuje do mensıch podmnozin, az je opetnaplneno predem dane kriterium.
Vylucujıcı, prekryvajıcı a fuzzy shlukovanı
Shlukovanı demonstrovana na obrazku 32 jsou vsechna vylucujıcı, protoze prira-zujı kazdy vzorek do jedineho shluku.
Existuje mnoho situacı, v nichz muze byt vzorek prijatelne umısten do vıce nezjednoho shluku. Tyto situace jsou pripisovany tzv. prekryvajıcımu se (nevylucne-mu) shlukovanı. V nejobecnejsım slova smyslu prekryvajıcı se shlukovanı jepouzıvano k vyjadrenı skutecnosti, ze vzorek muze soucasne patrit do vıce nezjedne skupiny. Prıkladem muze byt student na vysoke skole, ktery je zde ve-den jako student a zaroven je take zamestnancem skoly. Prekryvajıcı shlukovanıje tedy zrejme casto pouzıvano, pokud je vzorek mezi dvema nebo vıce skupi-nami a pokud nemuze byt striktne prirazen prave do jednoho shluku. Pokud seblıze podıvame na bod nachazejıcı se na obrazku 32 prımo mezi dvema shluky,uvidıme, ze spıse nez libovolne prirazenı vzorku do jedineho shluku, je bodprirazen do vsech shluku prichazejıcıch stejnou merou v uvahu.
Ve fuzzy shlukovanı obsahuje kazdy vzorek funkci prıslusnosti, ktera rıka, jakoumerou patrı dany vzorek do jednotliveho klastru. Funkce prıslusnosti nabyvahodnot < 0; 1 >, 0 - nepatrı a 1 - absolutne patrı.
Uplne a castecne shlukovanı
Uplne shlukovanı prirazuje kazdy vzorek do shluku, pricemz castecne nikoliv.V castecnem shlukovanı nektere vzorky z mnoziny dat nemusı patrit do presnestanovenych skupin. Mnohdy reprezentujı takoveto vzorky z mnoziny dat sum,outliery nebo pozadı, ktere nenı dulezite, proto je vyhodne takoveto vzorkyvubec neuvazovat.
Monoteticke a polyteticke shlukovanı
Tento uhel pohledu bere v uvahu uzitı atributu v procesu shlukovanı bud’
jako nasledne (postupne) nebo soubezne. Vetsina algoritmu je polyteticka, coz
61
znamena, ze vsechny atributy vstupujı do vypoctu podobnosti (resp. vzda-lenostı) mezi vzorky a nasledne zavery jsou delany na zaklade techto podobnostı(resp.vzdalenostı).
x2
x1
V
H1
H2
22
2
2
22
22
2
2 2
1
11
1
1
1 1
1
11
1
1
33
3
3
3
3
3 3
3
33
44
44
44
444
4
1
1
1
Obrazek 39: Monoteticke shlukovanı
Monoteticke shlukovanı uvazuje kazdy atribut zvlast’ pri rozdelovanı cele mnozinyvzorku. Na obrazku 39 je ukazano monoteticke shlukovanı, kdy je soubor datrozdelen do dvou skupin na zaklade vlastnosti x1. Vertikalnı lomena cara V jerozdelujıcı carou vuci atributu x1. Kazdy z techto shluku je dale samostatnerozdelen za pouzitı vlastnosti x2, jak je vyobrazeno pomocı lomenych car H1a H2. Hlavnım problemem tohoto postupu je, ze generuje 2d shluku, kde d jedimenze datoveho vektoru. Pro velke hodnoty d (d > 100) je pocet shluku vy-generovanych tımto algoritmem tak veliky, ze mnozina dat musı byt rozdelenado nezajımave malych shluku.
Deterministicke a stochasticke shlukovanı
Toto delenı je vetsinou vyznamne pro nehierarchicke prıstupy, ktere jsou navrzenepro optimalizaci kvadraticke chybove funkce. Tato optimalizace muze byt prove-dena za pouzitı tradicnıch technik nebo pomocı nahodneho hledanı ve stavovemprostoru skladajıcım se ze vsech moznych znacek.
Deterministicky algoritmus je algoritmus, ktery na stejny vstup (resp. na stejnevychozı podmınky) reaguje vzdy stejne (tedy predvıdatelne) a v kazdem jehokroku je vzdy jednoznacne definovan i krok nasledujıcı.
U stochastickeho algoritmu nelze predvıdat hodnotu vystupu, protoze reakcesystemu jsou nahodne, resp. v jakemkoli kroce nejsme schopni jednoznacne de-finovat nasledujıcı krok.
Shlukovanı po krocıch
Toto hledisko pripada v uvahu, pokud je datova mnozina, ktera ma byt rozdelenado shluku, velka a pokud jsou pozadavky na provedenı shlukove analyzy ohledne
62
casu a pameti procesu omezeny. Shlukova analyza nenabızı k nahlednutı mnohoalgoritmu shlukovanı, ktere byly navrzeny pro praci s velkou mnozinou dat, alevyvoj prace s daty podporuje vyvoj shlukovych algoritmu, ktere minimalizujıpocet prohledavanych vzorku mnoziny, redukujı pocet vzorku prozkoumavanychbehem vypoctu nebo snizujı velikost datovych struktur, ktere jsou pouzıvany veshlukovych algoritmech.
(SSE) reprezentacecastecnechyba ctvercu
smesi analyzymodu
shlukovani
grafovauplne
hierarchicke nehierarchicke
Obrazek 40: Rozdelenı metod shlukovanı
63
Seznam obrazku
1 Bezpecna vs. nebezpecna oblast dat . . . . . . . . . . . . . . . . 7
