Základy vytěžování dat

Základy vytěžování dat předmět A7Bb36vyd – Vytěžování dat Filip Železný, Miroslav Čepek, Radomír Černoch, Jan Hrdlička katedra kybernetiky a katedra počítačů ČVUT v Praze, FEL

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Shluková analýza a analýza hlavních komponent Odkaz na výukové materiály: https://cw.felk.cvut.cz/doku.php/courses/a7b36vyd/moduly/start (oddíl 3)

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Vytěžování dat, přednáška 4: Shluková analýza Miroslav Čepek

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Fakulta elektrotechnická, ČVUT

1 / 35

Shluková analýza

Co to je shluková analýza

I

Je jednou ze základních úloh vytěžování dat.

I

Jde o seskupení objektů do skupin podle jejich vlastností. Tak aby si objekty ve skupinách byly ”nějak” podobné.

I

A zároveň nebyly podobné objektů v jiných skupinách.

2 / 35

Shluková analýza

3 / 35

Shluková analýza

Co to je shluková analýza (II)

I I

V principu jde o optimalizační problém. Co se musí optimalizovat? I I

Počet shluků (skupin) Přiřazení instancí do shluků

4 / 35

Shluková analýza

Jak zjistit, že jsou si dva vzory podobné?

I

To je obecně velmi složitá otázka.

I

Protože shlukovou analýzu budou provádět hlavně počítače, musí být výsledkem nějaké číslo.

I

Z matematické analýzy známe pojem metrika – což je jiné označení vzdálenosti. Metrika musí splňovat několik základních podmínek, aby ji bylo možné použít.

I

I I I I

d(x, y) ≥ 0 d(x, y) = d(y, x) d(x, y) = 0 ⇔ x = y d(x, y) + d(y, z) ≥ d(x, y)

5 / 35

Shluková analýza

Metriky

I

Jaké znáte metriky?

I

Eukleidovská metrika

I

Manhattanská metrika

I

Kosinová metrika Příklady dalších metrik

I

I

I

I

Editační vzdálenost (vzdálesnost dvou slov = počet změn, kterými můžu změnit jedno slovo na druhé) Grafová metrika (počet hran, které musím v grafu projít, abych se dostal do z jednoho uzlu do druhého) http://en.wikipedia.org/wiki/Metric_space

6 / 35

Shluková analýza

Eukleidovská metrika

I

Nejpřirozenější metrika, protože se s ní běžně setkáváme.

I

Jak změříme vzdálenost dvou bodů na tabuli?

I

Pravítkem :)!

I

A když známe souřadnice, můžeme ji spočítat. Jak?

7 / 35

Shluková analýza

Eukleidovská metrika (II)

√

a2 + b2

I

Pythagorova věta! c =

I

A Pythagorovu větu můžeme zobecnit pro
i=1

8 / 35

Shluková analýza

Manhattanská metrika (City-block distance)

I

Základní myšlenka: Kolik bloků ve městě musím obejít, abych se dostal z jednoho místa na druhé?

I

Nebo také – kolik tahů králem musím udělat abych se dostal z jednoho místa šachovnice na druhé?

9 / 35

Shluková analýza

Manhattanská metrika (City-block distance) (II)

I

Pokud znám souřadnice, vzdálenost spočítam takto: dist(~x,~y) = |x1 − y1 | + |x2 − y2 | + . . . + |xn − yn |

10 / 35

Shluková analýza

Kosinová vzdálenost

I

Vzdálenost dvou vektorů je úhel, který svírají. ∑n similarity(~x,~y) = √∑ n

i=1 (xi

2 i=1 (xi )

∗

∗ yi ) ∑n

2 i=1 (yi )

I

Výsledky této funkce jsou v rozmezí -1 . . . +1. -1 znamená úplný opak, 0 nezávyslost a +1 naprostou shodu.

I

Aby výsledky vyhovovali definici metriky je potřeba podobnost odečíst od jedné. dist(~x,~y) = 1 − similarity(~x,~y)

11 / 35

Shluková analýza

Shlukování pomocí KMeans

I

Jednostlivé shluky budou zastoupeny jedním reprezentantem, který ponese vlastnosti typické pro danou skupinu/shluk.

I

Každá instance (vzor) v datech bude reprezentována reprezentantem, který je jí nejpodobnější .

I

Jinými slovy – který ji bude nejblíž (v dané metrice).

12 / 35

Shluková analýza

13 / 35

Shluková analýza

Shlukování pomocí KMeans

I

Jak určit, kde je správné místo pro reprezentanty?

I

Chceme, aby vzdálenost mezi reprezentanty a instancemi byla co nejmenší.

I

Snažíme se vlastně minimalizovat součet všech vzdáleností mezi instancemi a jejich reprezentanty ⇒ jde o optimalizační problém.

I

Taková optimalizace se dá řešit mnoha způsoby, ale jeden z nejjednodušších je iterační.

14 / 35

Shluková analýza

Algoritmus KMeans – značení

I

Máme množinu n vstupních vzorů/instancí (vektorů) xk . Jednotlivé složky vektoru budeme označovat xk (s).

I

A máme množinu K reprezentantů. meansti je i-tý reprezentant v kroku t.

15 / 35

Shluková analýza

Algoritmus KMeans

1. Nastav reprezentanty means0i do náhodných počátečních bodů. 2. Najdi a přiřaď každé instanci jeho nejbližšího reprezentanta. I I

∀x najdi j tak, aby dist(x, meanstj ) ≤ dist(x, meansti )∀i a pro každého reprezentanta meansti vytvoř množinu nearestti instancí, ke kterým je nejblíž.

3. Přesuň reprezentanta tak aby ležel ”uprostřed” své množiny nejbližších instancí. I

meanst+1 (s) = i

1 knearestti k

∑

xk ∈nearestti

xk (s)

4. Pokud se změnila poloha alespoň jednoho preprezentanta, vrať se na bod 2. Jinak skonči.

16 / 35

Shluková analýza

Ilustrace KMeans

17 / 35

Shluková analýza

Ilustrace KMeans (II)

18 / 35

Shluková analýza

Ilustrace KMeans (III)

19 / 35

Shluková analýza

Ilustrace KMeans (IV)

20 / 35

Shluková analýza

Ilustrace KMeans (V)

21 / 35

Shluková analýza

Pohádka o Algoritmu KMeans :)

I

Once there was a land with N houses.

I

One day K kings arrived to this land.

I

Each house was taken by the nearest king.

I

But the community wanted their king to be at the center of the village, so the throne was moved there

I

Then the kings realized that some houses were closer to them now, so they took those houses, but they lost some. This went on and on... (2-3-4)

I

Until one day they couldn’t move anymore, so they settled down and lived happily ever after in their village...

22 / 35

Shluková analýza

Problémy a stabilita shlukování pomocí KMeans

I

Dopadne shlukování pomocí KMeans pokaždé stejně?

I

Jak určit správný počet středů (shluků)?

I

Jak vyhodnotit jestli shlukování dopadlo dobře a jestli jsme zvolili přiměřené K?

23 / 35

Shluková analýza

Vyhodnocení shluků vytvořených KMeans algoritmem I

Jednou z možných metod je tzv. silueta.

I

Silueta pro každou vstupní instanci spočítá jistotu zařazení instance do daného shluku. b(xk ) − a(xk ) s(xk ) = max(a(xk ), b(xk ))

I

a(xk ) je průměrná vzdálenost xk od ostatních instancí shluku, ke kterému je přiřazena.

I

b(xk ) je průměrná vzdálenost xk od instancí v nejbližším dalším shluku.

I

Výsledné hodnoty jsou mezi -1 (xk do shluku úplně nepatří) a +1 (úplně patří)

I

ftp: //ftp.win.ua.ac.be/pub/preprints/87/Silgra87.pdf 24 / 35

Shluková analýza

Vyhodnocení shluků vytvořených KMeans algoritmem (II)

I

Pokud vypočítáte siletu pro všechny instance a vykreslíte ji do grafu, můžete si udělat představu, jak shlukování dopadlo.

25 / 35

Shluková analýza

Ukázka Siluety – shluky Kosatců

26 / 35

Shluková analýza

I

Které shlukování dopadlo lépe?

I

Co třeba průměrná silueta přes všechny instance (ideálně přes testovací data)?

27 / 35

Shluková analýza

Stabilita shluků

I

Jak zkusit, že shluky opravdu v datech jsou a výsledné shluky nejsou náhoda?

I

Náhodným smazáním např. 10% různých instancí vygenerovat M podmnožin dat a spustit shlukování na každé podmnožině.

I

Existuje několik ukázkových apletů/aplikací, kde si můžete zkusit, jak algoritmus funguje.

I

http://home.dei.polimi.it/matteucc/Clustering/ tutorial_html/AppletKM.html

28 / 35

Shluková analýza

Hierarchické shlukování – úvod

I

KMeans, jak jsme viděli, má některé mouchy. I I

Kolik je v datech shluků? Závislost výsledků na počátečních podmínkách.

I

Šlo by shlukování dělat i jinak?

I

Šlo :). Jednou z možností je Hierarchické shlukování.

I

Základní myslenka je, že vytvoříme hierarchii shluků. Vždy spojíme dva nejpodobnější shluky do jednoho většího.

I

A takto budeme pokračovat, dokud nevytvoříme jeden mega-shluk.

29 / 35

Shluková analýza

Hierarchické shlukování

1. Začne ze stavu, kdy každá instance je jedním shlukem. 2. Najdi dva nejbližší shluky. 3. Spoj je do jednoho. 4. Zůstávají nějaké shluky, které lze spojit? Pokud ano, vrať se na bod 2.

30 / 35

Shluková analýza

Nejbližší shluky

I

Jak zjistím vzdálenost dvou shluků?

I

Dokud shluky obsahují jen jednu instanci, je spočítání vzdálenosti jednoduché. Ale pak? Vzdálenost shluků je určena

I

I I

I I

Nejbližší sousedé – vzdáleností nejbližších instancí ve shluku. Nejvzdálenější sousedé – vzdáleností nejvzdálenějších instancí ve shluku. Vzdálenost středů – vzdáleností center (středů) shluků. Průměrná vzdálenost – průměrná vzdálenost mezi všemi instancemi v obo shlucích

31 / 35

Shluková analýza

Vzdálenost shluků – ilustrace

Nejkratší vzdálenost

Průměrná vzdálenost

Největší vzdálenost

Vzdálenost mezi reprezentanty

32 / 35

Shluková analýza

Dendrogram I

Když zkusíme vizualizovat postup shlukování – tj. které shluky se spojují, získáme strom – dendrogram.

I

Jak nalezneme počet shluků? Výběrem :), podle toho, kolik shluků potřebujeme nebo kolik vyjde jako nejvhodnější.

33 / 35

Shluková analýza

Vyhodnocení hierarchického shlukování

I

Můžeme opět použít siluetu, stejně jak jsme ji používali v K-Means.

I

Druhou možností je vypočítat CPCC (Cophenetic Correlation Coeffitient).

I

CPCC je normovaná kovariance vzdáleností v původním prostoru a v dendrogramu.

I

Pokud je hodnota CPCC menší než cca 0.8, všechny instance patří do jediného velkého shluku.

I

Obecně platí, že čím vyšší je kofenetický koeficient korelace, tím nižší je ztráta informací, vznikající v procesu slučování objektů do shluků.

34 / 35

Shluková analýza

Další informace a zdroje

I

http://cmp.felk.cvut.cz/cmp/courses/recognition/ zapis_prednasky/zapis_02/13/shlukovani.pdf

I

http://www.fit.vutbr.cz/study/courses/ZZD/public/ seminar0304/hlukovani2.pdf

35 / 35

Shluková analýza

Vytěžování dat, přednáška 5: Self Organizing Map Miroslav Čepek

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Fakulta elektrotechnická, ČVUT

1 / 44

Self Organizing Map

Shlukovací algoritmy a nevýhody

I

Jaké znáte shlukovací algoritmy?

I

KMeans

I

Hierarchické shlukování

I

KMeans – nedopadne pokaždé stejně, musím zkoušet počet centroidů.

I

Hiearachické shlukování – musím spočítat N2 vzdáleností. Což pro větší N není jednoduché.

2 / 44

Self Organizing Map

Další shlukovací algoritmy

I

Existuje spousta dalších algoritmů pro shlukování dat.

I

Ukáži vám ješte jeden – Self Organizing Map (SOM).

3 / 44

Self Organizing Map

Kompetitivní učení

I

Jedinci (reprezentanti, centroidy, neurony, jedinci) spolu soutěží – o něco :).

I

Nepotřebuji žádného arbitra (učitele), který by říkal, kam se mají jedinci přesunout. Každý jedinec to umí zjistit sám.

I

Jedinci se učí z příkladů.

I

Systém (populace jedinců) se v průběhu času samoorgranizuje sám.

I

A teď to zkusíme použít na shlukování.

4 / 44

Self Organizing Map

Kompetitivní učení v pohádce

I

Vzpomínáte si na pohádku o Králích z minulé přednášky?

I

Do země s N domy přijelo K králů a někde se usídlili. A každý král zabral domy, které mu byli nejblíž a z nich vybíral daně. A protože lidé chtěli, aby jim byl král co nejblíž, král se přestěhoval do geometrického středu domů.

I

Tím se ale některé domy ocitly blíže jinému králi a tak z nich daně začal vybírat jiný král. Králové se opět přesunout a tak dále.

I

Nejbližší král tedy získá všechny daně z domů, které jsem mu nejblíž.

5 / 44

Self Organizing Map

Kompetitivní učení v KMeans

I

KMeans také používá kompetitivní učení. Jak?

I

KMeans je trochu skromější.

I

Reprezentanti (centroidy) soutěží o data. A nejbližší reprezentant vyhraje – zabere celou instanci a jiného reprezentant k ní nepustí. ”Bere vše”.

6 / 44

Self Organizing Map

Kvantizační chyba

I

Minule jsem v souvislosti s KMeans mluvil o optimalizaci (minimalizaci) chyby.

I

Této chybě se říká kvantizační chyba. A vyjadřuje průměrnou vzdálenost mezi daty a odpovídajícími reprezentanty.

I

Průměrná vzdálenost mezi krály a jejich poddanými. ∑ 1 počet instancí k

kvantizační chyba =

∑

dist(ri , x)

i=0 x∈nearest(ri )

I

ri je i-tý reprezentant. A nearest(ri ) je množina instancí, které jsou mu nejblíž.

I

x je jedna z instancí.

7 / 44

Self Organizing Map

Vektorová kvantizace

I

A cílem (nejen) KMeans je minimalizovat tuto chybu.

I

Tím že minimalizuji kvantizační chybu tlačím reprezentanty do míst, kde se nachází hodně instancí.

I

Snažím se tím aproximovat hustotu instancí pomocí (menší hustoty) reprezentantů.

I

Do míst, kde je vysoká hustota instancí, se snažím dostat hodně reprezentatnů a naopak – do míst s málo instancemi dávám málo reprezentatnů.

I

Cílem kvantizace vektorů je aproximace hustotu pravděpodobnosti p(x) výskytu instancí x pomocí konečného počtu reprezentantů wi .

8 / 44

Self Organizing Map

Vítěz NEbere vše

I

U KMeans z domu vybírá daně jen nejbližší král. ”Winner takes all”.

I

Co když platí, že část daní může vybírat i jiný blízký král?

I

Pak už neplatí, že vítěz bere vše a něco zbude i na ostatní. Zde je důležité okolí – tj. jak daleko se králi ještě vyplatí jet pro svůj díl daní.

I

I I

Malé okolí – vítěz bere vše - daně vybírá jen jeden král Velké okolí – komunismus - každý král dostane z každého domu kousek.

9 / 44

Self Organizing Map

Neuronový plyn

I

Jiný způsob, jakým lze minimalizovat kvantizační chybu.

I

Na rozdíl od KMeans používám okolí a jinak počítám nové pozice středů.

1. Náhodně rozmísti reprezentanty a zvol velké okolí. 2. Vyber nějakou vstupní instanci xj . 3. Spočítej vzdálenost mezi xj a všemi reprezentanty wi ∀i. 4. Uprav pozice všech středů v závislosti na vzdálenosti od instance a okolí. 5. Zmenši okolí. 6. Pokud ještě chceš pokračovat, pokačuj bodem 2.

10 / 44

Self Organizing Map

Ilustrace iterace Neuronového plynu

11 / 44

Self Organizing Map

Ilustrace iterace Neuronového plynu

12 / 44

Self Organizing Map

Ilustrace iterace Neuronového plynu

13 / 44

Self Organizing Map

Ilustrace iterace Neuronového plynu

14 / 44

Self Organizing Map

Neuronový plyn (II)

I I

V algoritmu je několik stupňů volnosti. ”Vyber nějakou vstupní instanci” I

Procházíme postupně jednotlivé instance postupně v pevném pořadí. I

I

I

Nevhodné protože výstup může záviset na pořadí předkládání instancí.

Projde všechny instance jednou, pak v jiném pořadí podruhé, atd... Vybírá skutečně náhodně. Čili nezaručuje, že počet předložení síti bude pro všechny instance stejný. I

Nepoužívá se, protože není zaručeno, že nepředložím x1 10x, pak x2 12x, atd...

15 / 44

Self Organizing Map

Neuronový plyn (III)

I

”Uprav pozice všech středů v závislosti...”

I

Čím vzdálenější reprezentant, tím se posouvá méně.

I

wt+1 = wti + η t e−k/λ (x − wti ) i

t

I

I I

η t je adaptační krok v kroku t a určuje o kolik se maximálně může reprezentant posunout. (Typicky o dost menší než 1 a s roustoucím t klesá k 0). k pořadí ve vzdálenosti reprezentanta od instance. λt definuje velikost okolí a s rostoucím t klesá.

16 / 44

Self Organizing Map

Neuronový plyn (IV)

I

”Zmenši okolí” I

I

I

Okolí (λt ) se typicky postupně zmenšuje o nějaký násobek. Např. λt+1 = λt ∗ 0.95 Při zmenšování okolí se podobným způsobem zmenšuje i adaptační krok. η t+1 = η t ∗ 0.95.

”Pokud ješte chceš pokračovat...” I

Dopředu určím, že chci pokračovat dokud je λ > 0.05 nebo skonči poté, co předložíš všechny instance 10x.

Kontrolní otázka: Za jakých podmínek se přesune nejbližší reprezentant na pozici právě předložené instance?

17 / 44

Self Organizing Map

Vylepšení Neuronového plynu

I

Jak by se dal neuronový plyn vylepšit dál?

I

Co kdyby se neposouvali všechni reprezentanti blízko instance?

I

Vytvoříme ”přátelské” vztahy mezi reprezentanty. A budou se posouvat jen ”kamarádi” vítězného reprezentanta.

I

Když vizualizujeme ”přátelství” mezi reprezentanty získáme pravidelnou mřížku (síť).

I

Typicky se používá čtvercová nebo hexagonální síť.

18 / 44

Self Organizing Map

Inspirace pro SOM

I

Inspirací nejsou králové, ale oblasti v lidském mozku.

I

Řídící centra jednotlivých končetin spolu souvisí a navzájem se ovlivňují.

19 / 44

Self Organizing Map

SOM

I

Neuronová síť SOM je vynálezem prof. Kohonena z Finska.

I

Původně vznikla jako model motorického cortexu a její první aplikace byl fontetický psací stroj.

I

A protože se prof. Kohonen zabýval umělými neuronovými sítěmi, převzal i SOM jejich terminologii.

20 / 44

Self Organizing Map

SOM - Pozice neuronů

I

Každý reprezentant – v terminologii SOMu neuron – je opět reprezentován jeho souřadnicemi v prostoru.

I

Souřadnice každého neuronu (reprezentanta) se označují jako váhy.

I

Když si zkusím takovou síť vizualizovat, dostaneme například:

21 / 44

Self Organizing Map

SOM - Pozice neuronů (II)

I

WTF? Ještě před chvílí byla ta síť přece pravidelná!

I

To ano, ale to byla idealizovaná projekce, aby bylo názorně vidět vztahy! 22 / 44

Self Organizing Map

SOM - Algoritmus

I

Celý SOM algoritmus vypadá pak takto:

1. Inicializuj váhy všech neuronů (souřadnice všech reprezentantů). 2. Vyber nějakou vstupní instanci xj . 3. Spočítej vzdálenost mezi xj a všemi neurony wi ∀i. 4. Urči nejbližší neuron – BMU (Best Matching Unit). 5. Uprav váhy (pozici) BMU a jeho okolí. 6. Pokud ještě chceš pokračovat, pokačuj bodem 2.

23 / 44

Self Organizing Map

Detaily algoritmu

I

Inicializace vah: I I

I

Rovnoměrné rozprostření pro prostoru. Náhodně.

Výběr instancí: I I

Opět můžeme vybírat instance úplně náhodně. Ale mnohem častější je vybrat všechny instance jednou, pak všechny podruhé (v jiném pořadí), atd... Prochází se permutace vstupní množiny.

24 / 44

Self Organizing Map

Detaily algoritmu (II) I

Výpočet vzdáleností a určení BMU je celkem jednoduchá záležitost.

I

Určím si metriku, kterou budu využívat a tu aplikuji.

I

Mnohem zajímavější je úprava pozice BMU a jeho okolí :).

I

Jak vlastně určím neurony v okolí?

25 / 44

Self Organizing Map

Změna vah graficky

26 / 44

Self Organizing Map

Detaily algoritmu (III)

I

Novou pozici neuronu wi v kroku t + 1 (po předložení vzoru xj ) určím jako:

I

wt+1 = wti + µ(t)(xj − wti ) i

I

Kde µ(t) je sdružený učící koeficient, který v sobě sdružuje jak vzdálenost neuronu od BMU tak i maximální možnou změnu vah (pozice).

I

µ(t) s postupujícím časem klesá k nule.

27 / 44

Self Organizing Map

Detaily algoritmu (IV)

−

µ(t) = α(t)e

dist(wi ,BMU) 2σ 2 (t)

I

α(t) představuje učící krok (tedy jak moc se maximálně mohou změnit váhy neuronu).

I

eblabla určuje, že okolí neuron má tvar gausovky.

I

σ 2 (t) určuje velikost okolí a postupně s časem klesá.

28 / 44

Self Organizing Map

Příklad Máme 3 neurony w1 = (0, 0)w2 = (2, 1)w3 = (0, 3) a ty jsou na lince. w1 je sousedem w2 , w2 je sousedem w3 a w1 , w2 je sousedem w3 . A instanci x = (1, 1) Který neuron je BMU? (Použijeme eukleidovskou metriku) d(w1 , x) =

√

d(w2 , x) = d(w3 , x) =

29 / 44

(0 − 1)2 + (0 − 1)2 = √

√

√ 2 = 1.41...

(2 − 1)2 + (1 − 1)2 =

(0 − 1)2 + (3 − 1)2 =

Self Organizing Map

√ 1=1

√ 5 = 2.23..

Příklad (II) BMU je tedy w2 . Řekněme, že σ(t) = 1 a α(t) = 0.25 A zkusme vypočítat novou pozici BMU (w2 ). dist(wi ,BMU) 2σ 2 (t)

−

µ(t) = α(t)e

= 0.25 ∗ e−

dist(w2 ,w2 ) 2∗12

= 0.25 ∗ e0 = 0.25

wt+1 = wt2 + µ(t)(x − wt2 ) = (2, 1) + 0.25 ∗ ((1, 1) − (2, 1)) = 2 = (2, 1) + 0.25(−1, 0) = (1.75, 1) Pro w1 se posune do pozice: −

µ(t) = α(t)e

dist(w1 ,w2 ) 2σ 2 (t)

= 0.25 ∗ e− 2 = 0.25 ∗ 0.606 = 0.151 1

wt+1 = wt1 + µ(t)(x − wt1 ) = (0, 0) + 0.151 ∗ ((1, 1) − (0, 0)) = 1 = (0, 0) + (0.151, 0.151) = (0.151, 0.151)

30 / 44

Self Organizing Map

Chyba SOM I I

Stejně jako v Hierarchickém shlukování a K-Means potřebujeme nějakou míru ”dobrého shluknutí”. Kvantizační chyba I

I

I

Ale tu už známe! To je přece chyba, o které jsme mluvili na začátku přednášky! Průměrná vzdálenost mezi instancemi a nejbližšími neurony.

Topografická chyba I I

Popisuje kvalitu ”natažení” mřížky sítě na vstupní data. Procento instancí, pro které platí, že jejich BMU a druhý nebližší neuron nejsou sousedy v mřížce sítě.

∑ errtopo = n1 ni=1 u(xi ) u(xi ) = 1 ⇐⇒ BMU a druhý nejbližší neuron pro xi nejsou sousedé v mřížce.

31 / 44

Self Organizing Map

Vizualizace SOM

I

Dokud máme jen 2D data, tak s vizualizací není problém. Ale co když máme více dimenzí? I I I

U-Matice Analýza hlavních komponent Sammonova projekce

32 / 44

Self Organizing Map

U-Matice I

Matice vzdáleností mezi váhovými vektory jednotlivých neuronů, typicky se vizualizuje, vzdáleností vyjádřeny barvou – světlá barva = malá vzdálenost.

I

Zobrazuje strukturu vzdáleností v prostoru dat.

33 / 44

Self Organizing Map

U-Matice I

Barva neuronu je vzdálenost je váhového vektoru od všech ostatních váhových vektorů.

I

Tmavé váhové vektory jsou vzdáleny od ostatních datových vektorů ve vstupním prostoru.

I

Světlé váhové vektory jsou obklopeny cizími vektory ve vstupním prostoru.

34 / 44

Self Organizing Map

U-Matice (III)

I

Jak z U-Matice poznám shluky?

I

Ze vzdáleností mezi neurony.

I

Kopce oddělují clustery (údolí).

35 / 44

Self Organizing Map

Analýza hlavních komponent

I

Jde o statistickou metodu pro redukci dimenzionality.

I

Označuje se jako PCA z anglického Principal Component Analysis.

I

Snaží se najít nové osy, které lépe popisují data s minimální ztrátou informace.

I

První osa vede směrem, který má největší rozptyl hodnot, druhá osa směrem, kde je druhý největší rozptyl, atd...

I

Vždy mi vrátí stejný počet nových os, jako mají původní data dimenzí, ale já se mohu rozhodnout některé nepoužít.

36 / 44

Self Organizing Map

Analýza hlavních komponent (II) I

Pro výpočet nových souřadnic se používá konvariance, vlastní čísla a vlastní vektory.

I

Tím vás nebudu trápit :).

I

http://www.cs.otago.ac.nz/cosc453/student_ tutorials/principal_components.pdf

37 / 44

Self Organizing Map

Využití PCA v SOM I

Nyní můžu provést PCA projekci SOM sítě do 2D a zobrazit si ji.

38 / 44

Self Organizing Map

Využití PCA mimo SOM

I

Samozřejmě využití PCA není nutně limitováno jen na použití v SOM, ale můžu ji použít například pro průzkumu dat.

I

Stejně tak, některé metody vytěžování dat nemají rády příliš mnoho dimenzí a PCA jim můžete pomoci k lepším výsledkům.

I

Nevýhodou je umělost nových os, která znesnadňuje interpretaci získaných výsledků.

I

0.125 ∗ petal_length + 0.578 ∗ petal_width + 0.934 ∗ sepal_length − .0346 ∗ sepal_width

39 / 44

Self Organizing Map

Sammonova projekce

I

Jinou možností je Sammonova projekce.

I

Ta netransformuje osy, ale znovu umísťuje objekty v novém (méně dimenzionálním) prostoru.

I

Při umisťování se snaží zachovat vztahy v datech (data, která byla blízko v původním prostoru, budou blízko i v novém prostoru).

40 / 44

Self Organizing Map

Sammonova projekce (2)

I

Sammonova projekce se snaží minimalizovat následující funkci: ∑ (dist∗ (xi , xj ) − dist(xi , xj ))2 1 E= ∑ ∗ dist∗ (xi , xj ) i<j dist (xi , xj ) i<j

I

dist∗ (xi , xj ) je vzdálenost xi a xj v původním prostoru.

I

dist(xi , xj ) je vzdálenost xi a xj v novém prostoru (v projekci).

I

Pro minimalizaci se používají standardní optimalizační metody – pro tuto úlohu typicky iterační metody.

I

Při minimalizaci se pohybuje body v novém prostoru (v projekci). Tím ovlivníte dist(xi , xj ) a můžete dosáhnout zmenšení E.

41 / 44

Self Organizing Map

Sammonova projekce - ukázka

Ukázka několika iterací Sammonovy projekce na Iris datech.

Počáteční stav

42 / 44

Self Organizing Map

1. iterace

10. iterace

Další vizualizace – Příznakové grafy I

Vychází z U-Matice, ale místo vzdálenosti jednotlivých vektorů se do šestiúhelníčků kreslí hodnoty vybrané proměnné.

43 / 44

Self Organizing Map

Další čtení

I

http://www.cis.hut.fi/somtoolbox/theory/ somalgorithm.shtml

I

http://www.cis.hut.fi/research/som-research/

I

http://www.ai-junkie.com/ann/som/som1.html

I

www.cs.bham.ac.uk/~jxb/NN/l16.pdf

44 / 44

Self Organizing Map

Vytěžování dat, cvičení 5: Shlukování Miroslav Čepek

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Fakulta elektrotechnická, ČVUT

1/5

Shlukování

Zadání domácího úkolu 1. Doimplementujte K-Means algoritmus. Přiložená funkce v Matlabu implementuje část KMeans algoritmu (nalezení nejbližších reprezentantů (centroidů)). Vaším úkolem je doplnit přesun reprezentantů do středu nových shluků a určit, zda je možné ukončit algoritmus nebo má smysl pokračovat další iterací. 2. Centroidy (reprezentanty) inicializujte náhodně a při každém spuštění jinak. 3. Shlukněte přiložená data vaším KMeans algoritmem. Zkuste různé počty reprezentantů (2,3, . . . ,10). Spočítejte průměrnou siluetu pro všechny počty shluků a určete pro který počet reprezentantů vyjde průměrná silueta nejlépe. Pro zajímavé počty reprezentantů zobrazte grafy siluet.

2/5

Shlukování

Zadání domácího úkolu (2)

1. Pro nejlepší počet reprezentantů, který vám vyšel v minulém bodě, (alespoň 5x) spusťte algorimus KMeans s různými náhodnými počátečními pozicemi reprezentantů. 2. Shlukněte data pomocí hierarchického shlukování. Vytvořte stejný počet shluků, který vám vyšel nejlépe v algoritmu KMeans. Do zprávy vložte dendrogram, graf siluety a průměrnou siluetu. Krátce okomentujte rozdíly mezi výsledky hierarchického shlukování a KMeans algoritmu.

3/5

Shlukování

Obsah zprávy 1. Vámi doplňený zdrojový kód. !!A jeho stručný popis!! 2. Průměrné hodnoty siluety pro počty reprezentantů: 2, 3, 4, . . ., 10. 3. Dále přiložte zajímavé grafy siluet. Volitelně, pokud vám přijde zajímavý, může zpráva také obsahovat 2D/3D bodový graf se zvýrazněnými shluky. 4. Hodnoty průměrných siluet a výsledných souřadnic reprezentantů pro různé náhodné počáteční pozice reprezentantů. Pro počet reprezentantů, který vám vyšel nejlepší, v minulém bodě. 5. Dendrogram, který vám vyšel z hierarchického shlukování. A průměrná silueta a graf siluety stejný pro počet shluků, jako vám vyšel nejlepší v algoritmu KMeans.

4/5

Shlukování

Užitečné funkce

I

silhouette

I

kmeans

I

linkage

I

pdist

I

cluster

I

cophenet

I

scatter

5/5

Shlukování

Vytěžování dat 6: Self Organizing Map Miroslav Čepek

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Fakulta elektrotechnická, ČVUT

1 / 15

Slef Organizing Map

SOM Toolbox

I

V dnešním cvičení vám ukážeme SOM Toolbox.

I

Před použitím jej musíte stáhnout a rozbalit.

I

SOM Toolbox se nachází na http://www.cis.hut.fi/somtoolbox/.

2 / 15

Slef Organizing Map

SOM Toolbox (II)

I

Až SOM Toolbox stáhnete, rozbalte jej do ”nějaké” složky (ideálně tam, kde máte ostatní vaše zdrojové soubory). Doporučuji nechat soubory SOM Toolboxu v jednom podadresáři.

I

Tento podadresář musíte přidat do cesty, kde Matlab hledá skripty.

I

Pravým tlačítkem klikněte na adresář se SOM Tooleboxem a vyberte ”Add to Path” ”Selected Folder and Subfolders”.

3 / 15

Slef Organizing Map

SOM Toolbox – demo

I

Společně projdeme demo skripty, které ukazují všechny možnosti SOM Toolboxu.

I

Pokud si někdy nebudete vědět rady, projděte si tato dema znovu a většinou v nich najdete, co potřebujete.

I

Dema spoustíte příkazy som_demo1, som_demo2, som_demo3 a som_demo4.

4 / 15

Slef Organizing Map

Načtení dat

I

Načtěte data pomocí load ionosphere. I

I

This radar data was collected by a system in Goose Bay, Labrador. This system consists of a phased array of 16 high-frequency antennas with a total transmitted power on the order of 6.4 kilowatts. The targets were free electrons in the ionosphere. ”Good” radar returns are those showing evidence of some type of structure in the ionosphere. ”Bad” returns are those that do not; their signals pass through the ionosphere.

Normalizujte data pomocí data = som_normalize(X)

5 / 15

Slef Organizing Map

SOM příklad učení

I

Vytvořte náhodně inicializovanou mapu pomocí som_randinit.

I

Pokud potřebujete vytvořit prázndou mapu, použijte som_map_struct.

I

map = som_randinit(X, 'msize', [10 8], 'lattice','hexa')

I

Pro trénování použijte som_batchtrain(map, data) (druhá možnost je som_seqtrain).

I

Variantou je použití funkce som_make, která vytvoří SOM síť, inicializuje ji a naučí ji.

6 / 15

Slef Organizing Map

PCA vizualizace dat

I

Zobrazení dat pomocí PCA I I

I

Výpočet PCA hodnot: tmp = pcaproj(data, 2) Zobrazení scatter(tmp(:,1), tmp(:,2))

Barevné rozlišení tříd: I I I I

y = cell2mat(Y) scatter(tmp(y == 'k',1), tmp(y == 'k',2), 'ok') hold on scatter(tmp(y == 'g',1), tmp(y == 'g',2), '+r')

7 / 15

Slef Organizing Map

SOM – vizualizace

I

Zobrazte U-Matici som_show.

I

som_show(map, 'umat', 'all').

I

Jak zobrazit, který neuron je reprezentantem pro která data?

I

Musíme použít som_show_add a k U-Matici přidat informace o počtu a typu dat.

I

Nejprve je potřeba zjistit, který neuron je BMU pro které vstupní instance. K tomu slouží som_hits.

I

h1 = som_hits(map, data(y == 'g', :)); h2 = som_hits(map, data(y == 'k', :));

I

som_show_add('hit', h1, 'MarkerColor', [1 0 0]); som_show_add('hit', h2, 'MarkerColor', [0 1 0]);

8 / 15

Slef Organizing Map

Zadání domácího úkolu

I

Pomocí SOM vytvořte shluky dodaných dokumentů.

I

Dokumenty obsahují zprávy z několika diskusních fór. Každé fórum má jeden adresář a každá zpráva v něm je jeden soubor.

I

Ze stránek předmětu (cvičení) stáhněte tato data.

I

Z dokumentů extrahujte důležitá slova a příznakové vektory pomocí rozšíření rapidmineru pro textmining. (bude náplní dalšího cvičení).

I

Takto extrahovaná data uložte do CSV souboru.

9 / 15

Slef Organizing Map

Zadání domácího úkolu (2)

I

Tento CSV soubor načtěte do MATLABu pomocí funkce dlmread (nebo podobné).

I

Pomocí SOM Toolboxu shlukněte načtená data a pomocí různých vizualizací zobrazte výsledky shlukování.

I

Pro počítání vzdáleností použijte Kosínovou metriku.

I

Učiňte závěry, zda se dokumenty v jednotlivých fórech podobají nebo ne.

10 / 15

Slef Organizing Map

Nastavení textminingu

I

Tokeny (slova) jsou odděleny znaky, která nejsou písmena.

I

Doporučuji, abyste vyfiltrovali příliš krátká slova (řekněme kratší než 5 znaků) a často se vyskytující slova (stopwords) – předložky, spojky, ...

I

Pro hledání kořenů slov použijte Porterův algoritmus.

I

Volitelně můžete zkusit zkusit zkontruovat n-gramy (tokeny sestávající se z více slov) – doporučuji maximálně 3 slova.

I

Také doporučuji odstranit slova, která se vyskytují příliš řídce (příliš málo -krát).

11 / 15

Slef Organizing Map

Obsah zprávy

I

Zpráva bude obsahovat:

I

Popis proudu v Rapidmineru, kterým jste vyextrahovali příznaky z dokumentů a jeho screenshot (alespoň důležité části).

I

Popis postupu, jakým jste vytvořili SOM síť a její vizualizace.

I

Vytvořené vizualizace a jejich popis.

I

Závěr o tom, zda se příspěvky v diskusních fórech podobají nebo ne.

12 / 15

Slef Organizing Map

Užitečné příkazy SOM Toolboxu

I

som_demo1, som_demo2, som_demo3, som_demo4

I

som_randinit

I

som_make

I

som_quality

I

som_show

I

Kompletní dokumentaci všech funkcí naleznete na http://www.cis.hut.fi/projects/somtoolbox/ package/docs2/somtoolbox.html

13 / 15

Slef Organizing Map

Užitečné zdroje o Textminingu

I

Pokud se chcete podívat, jak se textmining provádí v Rapidmineru, doporučuji následující sérii videí: I I I I I I

I

http://www.youtube.com/watch?v=hpvda_Rfg3s http://www.youtube.com/watch?v=EjD2M4r4mBM http://www.youtube.com/watch?v=vhMzUi-FMy0 http://www.youtube.com/watch?v=ToxzfYECxOU http://www.youtube.com/watch?v=BRvjWLwSScQ http://www.youtube.com/watch?v=9I0BcMuhPe8

Video přednáška o Textminingu http://videolectures.net/ess07_grobelnik_twdmI/

14 / 15

Slef Organizing Map

Užitečné zdroje o Textminingu (2)

I

http://eprints.pascal-network.org/archive/ 00000017/01/Tutorial_Marko.pdf

I

http://www.cs.sunysb.edu/~cse634/presentations/ TextMining.pdf

15 / 15

Slef Organizing Map

Vytěžování dat, cvičení 7: Textmining Miroslav Čepek

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Fakulta elektrotechnická, ČVUT

1 / 24

Textmining

Základní kroky pro text mining

1. Získání dokumentů a nahrání do Rapidmineru (či jiného SW) 2. Tokenizace (rozklad textu na jednotlivá slova) 3. Odfiltrování častých a nezajímavých slov 4. Převod slov na kořeny slov (stemming) I I I

Převod na jednotná čísla Převod různých časování/způsoby/vidy na infinitivy Převod mezi různými variantami slov (příslovce, přídavná jména ← podstatná jména).

5. Vytvoření ”word vectoru”. (Převod slov na čísla). 6. Tvorba modelu.

2 / 24

Textmining

Instalace rozšíření pro Textmining

I

Standardní instalace Rapidmineru neobsahuje rozšíření pro Textmining.

I

Musíte nainstalovat rozšíření, ale naštěstí je to velmi jednoduché :).

I

Z menu Help vyberte Update RapidMiner. Zde zaklikněte Text Processing a Web Mining.

I

A klikněte na Install.

3 / 24

Textmining

Získání dokumentů a nahrání do Rapidmineru

I

Existuje několik uzlů, pro nahrávání dat do RapidMineru.

I

Pro naše účely, kdy máme dokumenty různých typů v různých složkách, nejlépe vyhovuje uzel Text Processing > Process Documents from Files.

I

Jedná se o super-uzel, který bude obsahovat pod-proud transformující dokumenty na číselné vektory.

4 / 24

Textmining

Extrakce textů z HTML

I

První krok je extrakce textů z HTML (resp. odstranění HTML tagů).

I

Pro to budete potřebovat uzel Extract Content > HTML Processing > Extract Content.

5 / 24

Textmining

Tokenizace

I

Rozklad na jednotlivá slova.

I

Slova se rozdělují typicky podle ”ne”písmenek. Takto získaná slova se označují jako termy.

I

V Rapidmineru existuje uzel ”Tokenize”, který najdete Text Processing > Tokenization > Tokenize.

I

Možnosti rokladu na slova jsou: non-letters, specify-characters, regular expression, linguistic tokens, linguistic token.

6 / 24

Textmining

Tokenizace (2)

I

Zkuste spustit proud nyní.

I

Výsledkem bude word objekt, který si můžete prohlédnout.

I

Uvidíte počty slov podle typů dokumentů. A také celkový počet slov.

I

Každé slovo nakonec bude reprezentovat vstupní proměnnou.

7 / 24

Textmining

Filtrování častých a nezajímavých slov

I

Protože vstupních proměnných bude i tak moc, je vhodné některé z nich eliminovat.

I

První způsob je filtrování obvyklých a nezajímavých slov.

I

V Rapidmineru se to děje uzlem Text Processing > Filtering > Filter Stopwords (English).

I

Tím z dokumentu odstraníte termy (slova), která se v angličtině vyskytují příliš často.

I

Například spojky, běžná slovesa, předložky, apod...

I

Uzel v Rapidmineru obsahuje seznam předdefinovaných slov.

8 / 24

Textmining

Filtrování častých a nezajímavých slov (3)

I

Stejně tak může (ale nemusí) být dobrý nápad vyfiltrovat slova, která jsou příliš dlouhá nebo příliš krátká.

I

K tomu slouží Text Processing > Filtering > Filter Tokens (by Length).

9 / 24

Textmining

Převod slov na kořeny slov – Stemming

I

Exituje několik způsobů, jak najít kořen slova.

I

Například hrubou silou – tj tabulka mapující každé slovo a každý jeho tvar na odpovídající kořen. Jeden z dalších používaných algoritmů (pro Angličtinu) je tzv. Porterův algoritmus.

I

I I

I

I

Iterativně odebírá známé koncovky anglických slov. Má seznam přípon a ty se pokouší postupně odebrat (pokud to lze). Například HOPEFULNESS → HOPEFUL → HOPE.

http://tartarus.org/martin/PorterStemmer/def.txt

10 / 24

Textmining

Převod slov na kořeny slov – Stemming (2)

11 / 24

Textmining

Kombinace slov - N-Grams

I

Někdy se v dokumentech vyskytují zajímavé kombinace (po sobě jdoucích) slov.

I

N-Gram je term, který obsahuje posloupnost term maximální délky N.

I

Uzel Text Processing > Transformation > Generate n-Grams (Terms) vygeneruje vsechny kombinace termů.

12 / 24

Textmining

Kombinace slov

13 / 24

Textmining

Vlastnosti uzlu Process Documents from Files I

Jednak umožňuje zahodit málo (nebo moc) často se vyskytující termy (slova a n-gramy).

I

Jednotlivé možnosti vybíráte combo-boxem Prune method.

I

Další důležitá věc je zaškrtnout Create word vector.

I

A vybrat vhodnou metodu pro Vector creation.

14 / 24

Textmining

Vytvoření ”word vectoru”

I

Nyní máme slova (termy) a jejich počty v jednotlivých dokumentech.

I

Před předložením shlukovací (či jakékoliv jiné) metodě je potřeba tyto počty nějak přetransformovat. V Rapidmineru jsou na výběr následující možnosti:

I

I

I I I

Term Frequency – normalizovaný počet výskytů termu výskytu termu ( počet celkový počet termů ) Term Occurences Binary Term Occurences TF-IDF

15 / 24

Textmining

Term Frequency - Inverse Document Frequency

I

Míra ukazující, jak moc je term specifický pro daný dokument.

I

Zahrnuje v sobě dvě části Term Frequency a Inverse Document Frequency.

I

Term Frequency je definován takto: tf(t) =

16 / 24

Textmining

počet výskytu termu celkový počet termů

Term Frequency - Inverse Document Frequency (2)

I

Inverse Document Frequency ukazuje, jak často se vyskytuje term v ostatních dokumentech. idf(t) = log

kDk k{d : t ∈ d}k

I

kDk – Celkový počet dokumentů.

I

k{d : t ∈ d}k – Počet dokumentů, ve kterých se term t vysktytuje.

17 / 24

Textmining

Term Frequency - Inverse Document Frequency (3)

I

Term Frequency - Inverse Document Frequency nakonec získáme, když tyto dvě míry vynásobíme. td − idf(t, d) = tf(t, d) ∗ idf(t)

18 / 24

Textmining

Export dat do CSV a import do MATLABu

I

V RapidMineru bohužel nejsou žádné vhodné shlukovací metody. Čili použijeme Matlab a SOM toolbox.

I

K exportu z RapidMineru lze použít uzel Export > Data > Write CSV

I

Abychom se nemuseli trápit v Matlabu s načítáním ošklivých hodnot, můžeme využít uzlu Export > Data > Write CSV k odstranění sloupců, které obhashují nečíselná a pomocná data.

I

V mém případě jde o sloupce: Description, Keywords, Language, Robots, Title, label, metadata_date, metadata_file, metadata_path.

I

Pro import použijeme v MATLABu funkci importdata.

19 / 24

Textmining

Shlukování v SOM toolboxu

I

Vytvoření a naučení SOM mapy:

I

map = som_make(x.data);

I

Zobrazení UMatice:

I

som_show(map, 'umat','all')

I

Jak to dopadlo?

20 / 24

Textmining

UMatice se zobrazenými třídami dokumentů

21 / 24

Textmining

Zobrazení mapy a dat pomocí PCA projekce

22 / 24

Textmining

Užitečné zdroje o Textminingu

I

Pokud se chcete podívat, jak se textmining provádí v Rapidmineru, doporučuji následující sérii videí: I I I I I I

I

http://www.youtube.com/watch?v=hpvda_Rfg3s http://www.youtube.com/watch?v=EjD2M4r4mBM http://www.youtube.com/watch?v=vhMzUi-FMy0 http://www.youtube.com/watch?v=ToxzfYECxOU http://www.youtube.com/watch?v=BRvjWLwSScQ http://www.youtube.com/watch?v=9I0BcMuhPe8

Video přednáška o Textminingu http://videolectures.net/ess07_grobelnik_twdmI/

23 / 24

Textmining

Užitečné zdroje o Textminingu (2)

I

http://eprints.pascal-network.org/archive/ 00000017/01/Tutorial_Marko.pdf

I

http://www.cs.sunysb.edu/~cse634/presentations/ TextMining.pdf

24 / 24

Textmining