Aplikované matematické vedy - vsb.cz

transcript

motivace

Aplikované matematické vědy

motivace

S={ slunečno, zataženo }Čas: t0 = dnes, t1 = zítra, . . .Náhodná veličina: xt . . . Jaké bude počasí v čase t.

Pro zjednodužení budeme předpokládat, že to, jaké bude počasízítra, záleží jen na tom, jaké počasí je dnes.

Motivace

P(xt+1 = slunečno|xt = slunečno) = 0.9

P(xt+1 = zataženo|xt = slunečno) = 0.1

P(xt+1 = slunečno|xt = zataženo) = 0.5

P(xt+1 = zataženo|xt = zataženo) = 0.5

Motivace

P(x1 = slunečno) = P(x1 = slunečno|x0 = slunečno) · P(x0 = slunečno)+ P(x1 = slunečno|x0 = zataženo) · P(x0 = zataženo)

P(x1 = zataženo) = P(x1 = zataženo|x0 = slunečno) · P(x0 = slunečno)+ P(x1 = zataženo|x0 = zataženo) · P(x0 = zataženo)

Označme:

πt =(

P(xt = slunečno)P(xt = zataženo)

)Potom

πt+1 = Λπt ,

kde Λ je matice podmíněných pravděpodobností.

Předpokládejme, že dnes je slunečno. Jaká je pravděpodobnost, že zítrabude slunečno/zataženo?

π0 =(

)π0 =

π1 = Λπ0 =(

0.9 0.50.1 0.5

)︸︷︷︸můžeme odhadnoutna základě dřívějších

měření

0.90.1

Jak nalezneme přechodovou matici?

Data za posledních 100 dní:

SZZSSSSSSSSSSZZZZZSSSSSSSSSZZSSSSSSSSSSSSSSZZSSSZZSSZSSSSZZZSSSSSSSSZSZZZSSSSSSSSSSSSZZSSSSSSSSSSSZ

Λi,j = ni,jm∑

i=1ni,j

Data za posledních 100 dní:

SZZSSSSSSSSSSZZZZZSSSSSSSSSZZSSSSSSSSSSSSSSZZSSSZZSSZSSSSZZZSSSSSSSSZSZZZSSSSSSSSSSSSZZSSSSSSSSSSSZ

počet přechodů slunečno → slunečno = 65počet přechodů slunečno → zataženo = 11počet přechodů zataženo → slunečno = 10počet přechodů zataženo → zataženo = 13

————————–celkem 99 přechodů

Λ̃ =( 65

761023

0.8553 0.43480.1447 0.5652

Co je „slunečno“? Co je „zataženo“?

„slunečno“ a „zataženo“ jsou dva vzájemně se vylučující stavykategoriální proměnné,každou kategorii lze charakterizovat hodnotou pozorovatelné (měřitelné)typicky spojité proměnné (teplota, tlak, vlhkost, vítr, . . . ).

teplota

Diskretizace

teplota

DiskretizaceDimenze dat počet kategorií

1 102 1003 1 0004 10 0005 100 000...

...n 10n

teplota

Diskretizace

Předpoklad: sníh a vysokáteplota nejsou možné

teplota

Diskretizace

Předpoklad: sníh a vysokáteplota současně nejsou možné

teplota

⇒ Shlukování

Shluková analýza (cluster analysis)

Shluková analýza je souhrnným názvem pro celou řadu výpočetníchalgoritmou, jejichž cílem je rozklad daného souboru dat na několikrelativně homogenních podmnožin, shluků.

Rozklad množiny dat by měl být proveden takovým zpousobem,aby si objekty uvnitř jednotlivých shlukou byly co nejvíce podobné.

Objekty patřící do různých shlukou by si naopak měly být podobnéco nejméně.

Proces shlukování může přinášet různá výsledná rozdělení objektůdo shluků v závislosti na použitých metodách a různýchspecifikacích ⇒ hodnocení výsledků.

PraxeÚloh a situací, kdy je potřeba objekty shlukovat do skupin, je nepřebernémnožství. Příklady praktického využití:

Shlukování genů s podobnými vlastnostmi exprese.

Tvorba skupin studentů se stejnými vlastnostmi.

Shlukování otázek v dotazníku, na které respondenti odpovídajípodobně.

Shlukování chemických prvků, které se chovají v nějaké situacipodobně.

Shlukování oblastí například podle spáchaných trestných činů.

Shluková analýza je často využívaná v marketingu. Napříkladshlukování zákazníků do skupin na základě dat z dotazníkovýchšetření.

Shlukování uživatelů sociálních sítí může odhalit komunity lidí.

Shlukování produktů podle jejich vlastností.

Pojem shluk

Jednou z definic, která pojem shluk vymezuje je Van Rijsbergenovadefinice. Lze ji vyslovit následovně:Je-li dána množina objektů X = {x1, x2, . . . , xn} a libovolnýkoeficient D nepodobnosti objektů, pak shlukem nazveme takovoupodmnožinu A množiny objektou X , pro niž platí:

max D(xi , xj) < min D(xk , xl ),

kde objekty xi , xj , xl ∈ A a objekt xk 6∈ A.

Metrika neboli jak měříme vzdálenosti mezi objekty

Při shlukové analýze je důležité zvolit vhodnou metriku, protože právě taovlivňuje tvar vytvořených shluků. V různých metrikách si mohou býtněkteré objekty blíže a v jiných dále.

Metrický prostorMetrickým prostorem nazýváme dvojici (X , d), kde X je libovolnáneprázdná množina a zobrazení d : X × X → R+ splňuje pro každéx , y , z ∈ X následující tři axiomy:

d(x , y) = 0 právě když x = y (identita)

d(x , y) = d(y , x) (symetrie)

d(x , y) + d(y , z) ≥ d(x , z) (trojúhelníková nerovnost).

Zobrazení d nazýváme metrikou na X , prvky množiny X obvyklenazýváme body prostoru (X , d), číslo d(x , y) nazýváme vzdálenostíobjektů x , y v prostoru (X , d).

Euklidovská metrika

Vzdálenost objektů Xi a Xj v Euklidovské metrice je definovánavztahem

d(Xi ,Xj) =

√√√√ p∑k=1

(xik − xjk)2,

kde xik je hodnota k-té proměnné u i-tého objektu,xjk je hodnota k-té proměnné u j-tého objektu.

Výhoda: výpočetní jednoduchost.

Nedostatky: předpokládá nekorelovanost proměnných =⇒ v praktickýchpodmínkách obtížně splnitelný. Dále je značně závislá na měřítkuproměnných, takže je vhodné pracovat s proměnnými v normovanémtvaru, tj. takovými, které mají nulový průměr a jednotkový rozptyl - jsoutedy bezrozměrnými čísly.

Hammingova metrika (Manhattanská vzdálenost,vzdálenost městských bloků (city-block distance))

Hammingova vzdálenost objektů Xi a Xj je definována vztahem

d(Xi ,Xj) =p∑

k=1|xik − xjk | .

Používá se k popisu rozdílů například mezi dvěma řetězci stejné délky.Vzdálenost se pak rovná počtu znaků, ve kterých se dané řetězce liší.Jinak řečeno, je to počet symbolů, které by bylo nutné změnit, aby bylyoba srovnávané řetězce shodné.Poed užitím této vzdálenosti se musíme ujistit, že znaky spolu nekorelují.Když tato podmínka není splnina, shluky jsou nesprávné.

Manhattan, rok 2020: chci se dostat z rohu 33. ulice a Pakr Avenue na roh ulic28. a 7. Avenue. Jakou vzdálenost musím urazit?

Minkovského metrika a Čebyševova metrika

Minkovského metrika zobecňuje Euklidovu i Hammingovu metriku.

• Místo druhé mocniny, resp. odmocniny, je použita obecná mocnina iodmocnina. To znamená, že zvyšuje váhu vlivu členů s větším rozdílem dílčíchsouřadnic. Čím větší mocnina, tím větší důraz na větší rozdíly mezisouřadnicemi.

d(Xi ,Xj ) = z

√√√√ p∑k=1

|xik − xjk |z

Pro z = 1 . . . Hammingova metrika,z = 2 . . . Euklidova metrika,

...Co se stane, pokud z →∞?

limx→∞

√√√√ p∑k=1

|xik − xjk |z = max∀k{|xik − xjk |}

=⇒ Čebyševova metrika

Minkovského metrika zobecňuje Euklidovu i Hammingovu metriku.• Místo druhé mocniny, resp. odmocniny, je použita obecná mocnina iodmocnina. To znamená, že zvyšuje váhu vlivu členů s větším rozdílem dílčíchsouřadnic. Čím větší mocnina, tím větší důraz na větší rozdíly mezisouřadnicemi.

d(Xi ,Xj ) = z

√√√√ p∑k=1

|xik − xjk |z

limx→∞

√√√√ p∑k=1

d(Xi ,Xj ) = z

√√√√ p∑k=1

|xik − xjk |z

Co se stane, pokud z →∞?

limx→∞

√√√√ p∑k=1

d(Xi ,Xj ) = z

√√√√ p∑k=1

|xik − xjk |z

limx→∞

√√√√ p∑k=1

d(Xi ,Xj ) = z

√√√√ p∑k=1

|xik − xjk |z

limx→∞

√√√√ p∑k=1

d(Xi ,Xj ) = z

√√√√ p∑k=1

|xik − xjk |z

limx→∞

√√√√ p∑k=1

Jednotkové okolí bodu ve vybraných metrikách

Euklidova metrika

Hammingova metrika

Čebyševova metrika

Euklidova metrika

Hammingova metrika

Euklidova metrika

Hammingova metrika

Euklidova metrika

Hammingova metrika

Mahalanobisova metrika

Všechny dosud uvedené metriky neuvažují závislost mezi objekty.

Mahalanobisova vzdálenost objektů Xi a Xj je definovánavztahem

d(Xi ,Xj) =√

(xi − xj)T C−1(xi − xj),

kde xi a xj jsou p-členné vektory proměnných u i-tého a j-téhoobjektu, C je kovarianční matice.

Tato míra vzdálenosti přihlíží k vzájemným interkorelacímproměnných. Pokud jsou proměnné nekorelovány (párové korelačníkoeficienty jsou nulové), je Mahalanobisova vzdálenost rovnačtverci euklidovské vzdálenosti.

d(Xi ,Xj) =√

Metody shlukování

Hierarchické metodyAglomerativní - postupné „připojování“ objektůDivizní - postupné „odpojování“ objektů

Nehierarchické metodyNapř. metody „k-shlukování“

Vybrané metody hierarchického shlukování

Metoda nejbližšího sousedaMetoda nejvzdálenějšího sousedaCentroidní metodaMetoda průměrné vazbyWardova metoda

Metoda nejbližšího souseda (Single linkage)

Jedná se o aglomerativní hierarchickou metodu

Postup je založen na minimální vzdálenosti.

1 Nejprve se spojí dva objekty, které mají nejkratší vzdálenost⇒ shluk.

2 Postupuje se do situace, kdy všechny objekty tvoří 1 shluk.3 Problém s řetězením: spojují se dva shluky, kde vzdálenost

mezi dvěma objekty je nejmenší, ale nemusí se jednat onejbližší shluky.

Metoda nejvzdálenějšího souseda

Postup je založen na maximální vzdálenosti.

Nejdelší vzdálenost mezi objekty ve shluku představujenejmenší kouli, která obklopuje všechny objekty v oboushlucích.Problém s řetězením: není.

Centroidní metoda

Postup je založen na analýze vzdáleností mezi těžišti(centroidy = vektory průměrů) jednotlivých shluků.

Výhoda: menší náchylnost k ovlivnění výsledných shlukůextrémními či odlehlými objekty.

Metoda průměrné vazby

Postup je založen na průměrné vzdálenosti objektů v jednomshluku ke všem objektům ve druhém shluku.

Výhoda: kritérium je zaleženo na všech objektech.

Wardova metoda

Postup není založen na optimalizaci vzdáleností mezi shluky.

Jeho základem je čtverec Euklidovské vzdálenosti.

Řeší se minimalizace heterogenity shluků podle přírůstku vnitroshlukového součtu čtverců odchylek objektů od těžiště (centroidů).

Dendrogram

Graf ukazuje kompletní historii spojování do shluků od jednotlivýchobjektů (vlevo) až to jednoho shluku se všemi objekty (vpravo). Naose x je vzdálenost, při které se shluky spojily.

Algoritmus k-means

počet shluků se zpravidla označuje písmenem k

průměrná hodnotamnožné číslo

Algoritmus k-means

průměrná hodnota

množné číslo

Algoritmus k-means

Princip k-means algoritmu

Algoritmus metody k-means lze obecně popsat čtyřmi kroky:

1 Vyber počet shluků k, náhodně vygeneruj nebo zadej těžištěshluků.

2 Pro každý objekt vyber shluk, jehož těžiště je nejblíže. Pokudse vybraný shluk nerovná původnímu shluku, přemísti do nějobjekt.

3 Přepočítej těžiště nově vzniklých shluků.4 Jestliže nedošlo ke změně žádnéhoshluku, skonči, jinak

pokračuj bodem 2.

Děkuji za pozornost !!!

Aplikované matematické vedy - vsb.cz

Documents