18.3.2010
Seminář ústavu Dopravní systémy Fakulta dopravní Dopravní systémy
Matematické postupy (až kam jsme došli)
S přispěním: Mgr. M. Pavelka, PhD Ing. O. Přibyl, PhD Ing. M. Škodáček Ing. J. Wosyka
Březen 2010
1
18.3.2010
Motivace Předmět úvahy dopravní systémy – silnice zpracování dat modelování dopravy
Dopravní systémy (K612) x Matematika
(K611)
obrovské zdroje informací – matematické metody apriorní znalosti – dopravně-inženýrský pohled
Neformální vazby → formalizovat pracovní semináře → vědecké semináře propojení projektů rozpravy k doktorským pracím zjistit konkurenční výhody 2
2
18.3.2010
Rozpracované metody Mnohočetné regrese odhadování doby jízdy odhadování škodlivin
Rozhodovací stromy segmentace dat (klasifikace dopravy) pravděpodobnostní stromy (analýza rizik)
Redukce dimenze proměnných metoda PCA nehierarchické shlukové analýzy stavový prostor/stavový vektor
Hledání nestacionarit v dopravním proudu spektrální transformace dopravní modely založené na FC
Znalostní systémy Analytické vs. systémové metody 3
3
18.3.2010
Odhadování parametrů založené na rozhodovacích stromech a regresních modelech Data Mining
Určení cíle modelování (= čeho má být dosaženo) ⇒ cílová proměnná (prediktivní, deskriptivní) Předzpracování dat (sběr, vzorkování a vizualizace dat/chybějící a duplicitní údaje atd.) Transformace proměnných Rozdělení na trénovací, validační a testovací data. Vlastní modelování – použití a porovnání výkonnosti jednotlivých modelů. Ohodnocení modelů na out-of-sample datech
Mnohočetná regrese k
Omezení
y j = α + β1 x1 j + β 2 x2 j + K + β k xkj + ε j = α + ∑ βi xij + ε j i =1
požadavek na lineární závislost mezi regresory a cílovou proměnnou (většinou neplatí) multikolinearita je výhodou pro predikční a nevýhodou pro explanativní modely
Postup výběru regresorů dopředná regrese (nejprve nejvýznamnější) zpětná regrese (všechny a odstraňovány nevýznamné)
4
4
18.3.2010
Odhady dob jízdy
5
5
18.3.2010
Odhady dob jízdy významné zvýšení přesnosti: FCD
6
6
18.3.2010
Rozhodovací stromy
Obecné binární rozhodovací stromy OBCT (Ordinary Ordinary Binary Classification Trees) Trees acyklický graf, jehož vrcholy mají výstupní stupeň vždy buď 0 (listy) nebo 2 (vnitřní vrcholy). rozdělují prostor do mnohoúhelníků, které mají strany rovnoběžné s osami, posloupnost rozhodování je aplikována na jednotlivé příznaky, rozhodování probíhá podle dotazů ve tvaru „je příznak ?“
Pravděpodobnostní stromy FTA, ETA
7
7
18.3.2010
Odhadování škodlivin z dopravních dat
Náhrada extrémně drahých senzorů Nepřesnost bodového měření Odstranění stochasticity měření Prediktivní model
Ventilační schéma s vyznačenými proměnnými -Mrázovka
8
8
18.3.2010
Odhadování množství škodlivin
Odhadování a predikce +30 min: z dopravních dat
Metoda: rozhodovací stromy
koncentrace_CO_vtt_1240 4.5 koncentrace_CO_vtt_1240 historicky model hybridni model
4
Hybridní model
3.5 3 2.5
Měřená koncentrace … modře Historický model … zeleně Hybridní model … červeně
2 1.5 1 0.5 0 00:00
02:24
04:48
07:12
09:36
12:00 cas
14:24
16:48
19:12
21:36
00:00
9
9
18.3.2010
Pravděpodobnostní stromy – analýza rizik
základ kvantitativního hodnocení rizik tunelů
četnost scénáře je dána součinem pravděpodobností uzlů
omezení:
447 tunelů/5 let 7 požárů
10
10
18.3.2010
Redukce dimenze proměnných v obecně orientované dopravní síti Doprava: časo-prostorový více-dimenzionální vektor Model dopravy: dopravy redukce v dimenzi i prostoru
{q }→{q } S raf
⊗
i red
Redukce dimenzionality
{q , v }→{∆ } i
Mobilita lidstva a dopravní telematika
i
⊕
i
11
11
18.3.2010
108 profilových detektorů 28 úsekových
12
12
18.3.2010
Metoda hlavních komponent
Uplatnění, kdy jsou redundantní proměnné (≈ lineární) Postup:
načtení dat (N pozorování/řádky matice a j proměnných/sloupce matice) odečtení průměrů ⇒ průměrná hodnota sloupce je 0 výpočet kovarianční matice C (symetrická, prvky na diagonále – variace proměnné) výpočet vlastních čísel λ a vlastních vektorů z matice C (C.z = λ. z) sestupné seřazení vlastních vektorů (první – největší λ) nová data: vynásobení původních dat s vlastním vektorem kovarianční matice první s výsledných proměnných, které představují lineární kombinaci původních proměnných, má největší rozsah a postihuje největší část variability původních proměnných
13
13
18.3.2010
PCA redukce 30 proměnných (q, κ) – Jižní spojka
První tři komponenty po transformaci proměnných metodou PCA. Zelené body představují polohu dopravních situací dne 10. května 2007. Červený bod představuje dopravní situaci daného dne v konkrétním čase 8 hodin 35 minut. V tomto případě byly vybrány všechny proměnné pro daný směr, tedy jak intenzita tak obsazenost.
redukce 15 proměnných (q) – Jižní spojka
Metoda hlavních komponent. Zelené body představují zobrazení dopravní situace dne 10. května 2007 V tomto případě byly vybrány pouze intenzity dopravy dr. Pavelka
14
14
18.3.2010
PCA
Co nás na první pohled zaujme:
Situace ve vybraném dni tvoří shluk, nejsou rozptýleny po prostoru. To znamená že v daný den se vyskytuje jakási podmnožina dopravních situací, ne všechny situace jsou v daný den přítomny. Je velký rozdíl mezi zobrazeními, pokud byly použity jen hodnoty intenzit dopravy, a pokud byly použity jen hodnoty obsazenosti. Zatímco zobrazení vzniklé transformací intenzit dopravy tvoří spojitý útvar, zobrazení vzniklé transformací obsazeností má zvláštní strukturu.
Analýza ukázala
Chování řidičů při jízdě z centra a do centra se může lišit. Dopravní zácpy ve směru z centra a do centra mají jinou dynamiku.
Vidíme, že pokud použijeme jen obsazenosti (vynecháme intenzity), vznikne docela zajímavý útvar
15
15
18.3.2010
PCA
ing. Škodáček
16
16
18.3.2010
Metody shlukové analýzy
Nehierarchické shlukování
objekty rozděluje do podmnožin dle specifických kritérií
Metoda nejbližšího souseda /Simple linkage/ Metoda nejvzdálenějšího souseda /Complete linking/ Centroidní metoda /Weighted group method/ Metoda průměrné vazby /Average linkage/ Mediánová metoda /Unweighted group average/ Wardova - Wishartova metoda /Ward's error sum of squares method/ Metoda k-průměrů /k-means clustering/ Metoda PAM /Partition around medoid/
Metoda k-průměrů
Počet nutných výpočtů je značný -algoritmy založené na postupném zlepšování rozkladu přesouváním objektů Jednoduchá Nejvyužívanějším kritériem kvality rozkladu je hodnota stopy matice vnitroskupinové variability Prvky se mohou přeskupovat mezi shluky k nh Lze ji použít pouze pro metrická data T W = x hi − x h x hi − x h Konverguje v konečném počtu kroků k nějakému řešení h =1 i =1 Může existovat více řešení v závislosti na počátečních podmínkách
∑∑ (
)(
)
k představuje celkový počet shluků, nh počet objektů v h-tém shluku, xhi je i-tý objekt v i-tém shlkuku a xh s pruhem je vektor průměrů h-tého shlkuku
17
17
18.3.2010
Aplikace metod shlukové analýzy Klasifikace dopravních situací rozdělení dopravních situací na přirozené skupiny, ve kterých budou dopravní situace co nejvíce vzájemně podobné optimálně přirozená kritéria (hrušky/jablka) objekty tvoří kontinuum – arbitrární třídění volíme a definujeme třídy
zde netřídíme, ale hledáme třídy: klasifikační algoritmus (shlukování diskretizací) 10 detektorů (3 pruhy, 2 parametry) % zastoupeni - Zapad AAAAAAAAAA AAAAAAAABA
Redukce počtu detektorů
ABAAAAAAAA ABABAAAAAA AAABAAAAAA
neidentifikované
AABAAAAABA
noc
ABAAAAAABA AACCAAAAAA AABCAAAAAA AABAAAAAAA AABAAAAACA AAAAAAAABB Zbytek
18
18
18.3.2010
Využití shlukové analýzy pro redukci dat
Metoda: k-medoids shlukování pro 18 detektorů Určení podobnosti 11
2
výpočet koeficientů korelace grafická interpretace v tabulce
1 10
3
8
4
12
5
13
6 7
14 18
15
17
16
9
5 shluků
výpočet tzv. „Silhouette coeficient“ si =
bi − ai max(ai , bi )
a i udává průměrnou vzdálenost objektu i vůči
ostatním objektům v tomtéž shluku bi, udává průměrnou vzdálenost objektu i vůči všem objektům v dalším nejbližším shluku (další nejlepší kandidát pro umístění objektu i)
dr. O. Přibyl
19
19
18.3.2010
Využití shlukové analýzy pro redukci dat
11
2
S3
1
10
3
S1 8
4
12
5
13
S 26
14 18
15
S5 S416 17
7
9 Shluk 1: Shluk 2: Shluk 3: Shluk 4: Shluk 5:
detektor 1, 2, 3, 4 detektor 5, 6 ,7, 8, 9, 12, 13, 14 detektor 10, 11 detektor 15, 16 detektor 17, 17 18
poměr redukce 18 : 5 = 3,6 krát
20
20
18.3.2010
Metoda pro spojité modelování dopravní sítě s využitím plovoucích vozidel
Ing. J. Wosyka
21
21
18.3.2010
Metoda pro spojité modelování dopravní sítě Penetrace FC
Hybridní model
Demonstrace dopravních problémů u Modletic, kde 5 km od první nehody vznikla nová
22
22
18.3.2010
Znalostní systémy Problematika šíření standardů do praxe
„Informační“ vers. „Znalostní“ společnost
Rok 1996 2003 2005 2008
Počet standardů 58 92 164 217
23
23
18.3.2010
Znalostní systémy Strukturované vyhledávání
Znalostní systém
Aristotelés (348 př.n.l.-322př.n.l.) se snažil rozpoznat základní vlastnosti a rozčlenit veškeré skutečnosti
Zavedení systematiky do třídění standardů: koncept vycházející z tzv. Aristotelova čtverce, tvořeného logickým čtvercem
soud obecný kladný soud obecný záporný soud částečný kladný soud částečný záporný
…SaP …SeP …SiP …SoP
Vyšší dipolarity 1. Uživatel a norma
2. Doprava a data
3. Rozhraní a spojení
Celkem:
(1646-1716) pojem substance – duchovní povaha, nedělitelná, základem všeho – term?
Kategorie (prvky, póly)
Základní dipolarity 1.1. Uživatel normy 1.2 Zavedení normy do ČSN
4 4
1.3 Druh normy
4
1.4 Užití normy v ITS 2.1 Data
4 4
2.2 Místo (pozemní komunikace)
4
2.3 Druh dopravy
4
2.4 Výměna dat 3.1 Druh spojení
4 4
3.2 Člověk – Stroj
4
3.3 Vozidlo – Infrastruktura 3.4 Vysílání do/z vozidla
4 4
3
12
48
Ing. Večerka
24
24
18.3.2010
Znalostní systémy vyhledávání znalostí
Nový obor bez teoretického základu Vymezit oblast vytvořit ontologii
Ontologie: konceptualizace znalostí ve formě hierarchické sémantické struktury. Pomáhá specifikovat strukturu a vytvořit co možná nejlepší navigaci znalostmi v této struktuře uloženými.
objektově orientovaný přístup model standardu
Značkování, makro data Vyhledávací mechanizmus
25
25
18.3.2010
Analytické vs. systémové řešení problematika doktorských prací
Popis obecné problematiky Analytické řešení problém může být popsán v „uzavřené“ podobě (jako funkce, množina, pravděpodobnost události, geometrické znázornění apod.)
Systémový inženýrský model vymezení systému, hranice, holistický pohled
„SSADM- Structured System Analysis and Design Metodology“
Analytická část
Strukturovaná metodologie analýzy a návrhu systému
analýza současného stavu a procesů (technické, provozní, ekonomické), analýza technických a technologických možností pro inovaci procesů, analýza požadavků managementu na kvalitnější řízení procesů.
Syntetická část
návrh struktury systému, výběr prvků, návrh procesů na zvolené architektuře, návrh postupu implementace a řízení projektu.
26
26
18.3.2010
Analytické vs. systémové řešení problematika doktorských prací
Abstraktní model reality: nástroje Blokové diagramy funkcí Diagramy datových toků UML diagramy USL funkční mapy
27
27
18.3.2010
UML popis Kontextový diagram
Diagram případů užití
Diagram aktivit
28
28
18.3.2010
Závěr Ve všech oblastech zájmu rozvinout a „standardizovat“ matematické a systémové postupy pasportizace znalostí
Transformovat projekty na skutečná týmová řešení propojit horizontálně projekty báze pro komunikaci společná publikační činnost
Výzkum nestacionarit v dopravním proudu Metody (ne)spektrálních transformací Entropie v návrhu systémů a řada dalších témat
29
29
