Bemenet modellezése II. Vidács Attila 2005. november 3.
Hálózati szimulációs technikák, 2005/11/3
Kiszolgálási id®k modellezése • Feladat: Egy bemeneti modell felállítása egy egy kiszolgálós sorbanállási rendszer kiszolgálási idejének leírására DES-ben. • rendelkezésre álló mérések: n = 23 mért érték a kiszolgálás id®tartamáról:
105.84, 28.92, 98.64, 55.56, 128.04, 45.60, 67.80, 105.12, 48.48, 51.84, 173.40, 51.96, 54.12, 68.64, 93.12, 68.88, 84.12, 68.64, 41.52, 127.92, 42.12, 17.88, 33.00.
• Els® lépés: Annak eldöntése, hogy a meggyelések függetlenek és
azonos eloszlásúak-e (iid) vagy nem. Fontos, hogy az adatok a mérés sorrendjében álljanak rendelkezésünkre! Példák, amikor a függetlenség feltételezése nem helytálló: ∗ Egy új munkatárs els® 23 ügyfelének kiszolgálási ideje. (Várhatóan csökken a kiszolgálási id® ahogyan az illet® belejön a munkába.) ∗ Egy nehéz zikai munka utolsó 23 munkadarabjának elkészítési ideje a munkaid® végéhez közeledve.
1
Hálózati szimulációs technikák, 2005/11/3
2
Kiszolgálási id®k modellezése • Tegyük fel, hogy okunk van feltételezni, hogy a kiszolgálási id® az id®vel csökken. • Lineáris modell: Y = β0 + β1 X + ², ahol X a meggyelés sorszáma, Y a kiszolgálási id®, β0 a tengelymetszet, β1 a meredekség, ² pedig a hibatag.
• Hipotézis teszt: H0 : β1 = 0, H1 : β1 < 0.
Hálózati szimulációs technikák, 2005/11/3
Kiszolgálási id®k vs. meggyelés sorszáma
3
Hálózati szimulációs technikák, 2005/11/3
4
Kiszolgálási id®k modellezése • A hipotézis-teszthez tartozó p-érték a konkrét esetben 0.14, ami nem elég bizonyíték arra, hogy statisztikailag szignikáns lineáris trend van a mérésben. • Több más grakus és statisztikai módszer is létezik a függetlenség vizsgálatára, pl:
A minta autokorrelációs függvényének vizsgálata. scatter plot a szomszédos meggyelésekre, ...
Hálózati szimulációs technikák, 2005/11/3
Minta autokorrelációs függvény
5
Hálózati szimulációs technikák, 2005/11/3
6
Kiszolgálási id®k modellezése • Következ® lépés: Hisztogramm rajzolása és statisztikák számítása. • Hisztogramm
(ld. köv. fólia) Az adathalmaz kicsi ugyan, de egy ferde (skewed) harangforma azért meggyelhet®.
A legnagyobb meggyelés nagyon a jobb szélen helyezkedik el. • Minta statisztikák
Mintaátlag x = 72.22 Tapasztalati szórás: s = 37.49 Variációs együttható: s/x = 0.52 n
1X Ferdeség (skewness): n i=1
µ
xi − x s
¶3 = 0.88
Hálózati szimulációs technikák, 2005/11/3
7
Hisztogramm
Hálózati szimulációs technikák, 2005/11/3
8
Kiszolgálási id®k modellezése • Példák a minta statisztikák értelmezésére:
Ha az s/x variációs együttható 1-hez közeli, aza hisztogramm alakját is gyelembe véveaz exponenciális eloszlást mint lehetséges választást mutatja.
Ha a minta ferdeség 0-hoz közeli, az szimmetrikus eloszlást jelez (pl. normális vagy egyenletes eloszlás).
• A következ® lépés: Parametrikus vagy nemparametrikus modellt
válasszunk? Pl. Egy nemparaméteres lehetséges modell az, ha a mért értékekb®l választunk egyet véletlenszer¶en 1/23-ad valószín¶séggel.
Az adathalmaz kis mérete, a 68.64 érték kétszeres el®fordulása, valamint a kiugró 173.40 másodperces minta inkább paraméteres modell választását sugallja.
Hálózati szimulációs technikák, 2005/11/3
9
Paraméteres modellezés • Az adatok alapján id®független, egyváltozós, folytonos modellt választunk. • A hisztogramm alapján szóba jöhet® eloszlások: gamma, inverz-normális, log-normális, Weibull.
Weibull eloszlás illesztése κ
• A Weibull eloszlás s¶r¶ségfüggvénye: f (x) = λκ κxκ−1 e−(λx) , x ≥ 0 ahol λ az ún. skála (scale) paraméter, κ pedig az alak (shape) paraméter. • Az eloszlás paramétereinek becslésére szolgáló módszerek:
Legkisebb négyzetek (least squares) módszere, momentum módszer, maximum likelihood módszer.
Hálózati szimulációs technikák, 2005/11/3
10
Maximum likelihood módszer • Legyenek x1 , x2 , . . . , xn a mintapontok. • A maximum likelihood függvény: L(λ, κ) =
n Y
" f (xi ) = λ
nκ n
κ
i=1
n Y
#κ−1 e−
xi
Pn i=1
(λxi )κ
i=1
• A log-likelihood függvény: log L(λ, κ) = n log κ + κn log λ + (κ + 1)
n X
log xi − λκ
i=1
n X
xκi .
i=1
• A log-likelihood függvény parciális deriváltjai: n X κn ∂ log L(λ, κ) xκi , = − κλκ−1 ∂λ λ i=1 n n X X ∂ log L(λ, κ) n = + n log λ + log xi − (λxi )κ log λxi . ∂κ κ i=1 i=1
Hálózati szimulációs technikák, 2005/11/3
11
Maximum likelihood módszer (folyt.) • A parciális deriváltakat 0-val egyenl®vé téve a paraméterek megkaphatók. ˆ és κ • Az adott esetben nincs zárt alakú megoldás a λ ˆ MLE becsl®kre. A becsl®k iteratív módon számolhatók. • ... • A kapott paraméter értékek: ˆ = 0.0122, λ
κ ˆ = 2.1
• Standard errors: σ ˆλˆ = 0.00128,
σ ˆκˆ = 0.329
.
• Az aszimptotikus 95% -os kondencia-intervallum κ-ra: 2.10 − 1.96 · 0.329 < κ < 2.10 + 1.96 · 0.329 1.46 < κ < 2.74
Hálózati szimulációs technikák, 2005/11/3
12
Az illesztett Weibull eloszlás
Hálózati szimulációs technikák, 2005/11/3
Kiszolgálási id®k modellezése A következ® feladat: A modell érvényesítése
• Illeszkedésvizsgálati (goodness-of-t tests) módszerek
Chi-square teszt, Kolmogorov-Smirnov teszt, Anderson-Darlling teszt, Vizuális tesztek (pl. Q-Q plot), ...
• A Kolmogorov-Smirnov teszt: Maximális vertikális eltérés az illesztett és az empirikus (tapasztalati) eloszlásfüggvény között.
Az adott példában a 0.15-ös p-érték a Weibull eloszlás jó illeszkedését mutatja.
• Q-Q plot (vagy P-P plot)
13
Hálózati szimulációs technikák, 2005/11/3
14
P-P (probability-probability) Plot
Hálózati szimulációs technikák, 2005/11/3
15
Érkezési folyamat modellezése Példa: Vendégek érkezése egy menzán.
• Mérés: Három napon rögzítettük az érkezéseket 11:00-t®l 15:30-ig.
Összesen n = 150 érkezést gyeltünk meg: n1 = 56, n2 = 42 és n3 = 52 a k = 3 napon.
Deniálva a (0, 4.5] id®intervallumot (órákban mérve) a folyamat három realizációja:
∗ 0.2152 0.3494 0.3943 ∗ 0.3927 0.6211 0.7504 ∗ 0.4499 0.5495 0.6921
... ... ...
4.175 4.248, 4.044 4.374, 3.643 4.357.
• Els® kérdés: A három realizáció egyazon sokaságból származik?
A küls® hatásoknak (pl. id®járás, a hét melyik napja, hirdetések, ...) azonosnak kell lenniük.
A meggyeléseinket úgy tekintjük, mint reprezentáns független mintákat.
Hálózati szimulációs technikák, 2005/11/3
16
Érkezési folyamat modellezése • Következ® feladat: A megfelel® modelltípus kiválasztása
A választás: folytonos idej¶, diszkrét állapotú sztochasztikus folyamat. • Következ® kérdés: Tekinthet®-e a folyamat stacionáriusnak?
Ha az érkezési folyamat nemstacionáriusnak mutatkozik, egy inhomogén Poisson folyamat megfelel® választás lehet.
A választás: Modellezzük a folyamatot egy inhomogén Poisson folyamattal, és vizsgáljuk meg az intenzitás-paraméter id®függését.
• Következ® lépés: Modellillesztés
Inhomogén Poisson folyamat intenzitásfüggvénye: λ(t) (Pl. λ(2) = 10 esetén az beérkezési intenzitás 10 vendég óránként t = 2 id®ben.)
A kumulatív intenzitásfüggvény
Z
t
Λ(t) =
λ(τ ) dτ 0
Hálózati szimulációs technikák, 2005/11/3
17
Érkezési folyamat modellezése • Feladat: A Λ(t) kumulatív intenzitásfüggvény becslése k realizációból, nemparametrikus eljárással. • Legyen:
(0, S] a becsléshez használt id®intervallum, ni , i = 1, 2, . . . , k az i-edik realizációban meggyelt érkezések száma, Pk n = i=1 ni , t(1) , t(2) , . . . , t(n) a k realizáció szuperpozíciójának rendezett mintája (azaz t(i) ≤ t(i+1) ), t(0) = 0, t(n+1) = S ,
• A kumulatív intenzitásfüggvény szakaszonként lineáris becsl®je az érkezési id®pontok között: ˆ Λ(t) =
n(t − t(i) ) in + , (n + 1)k (n + 1)k(t(i+1) − t(i) )
t(i) < t ≤ t(i+1) , i = 0, 1, 2, . . . , n
Hálózati szimulációs technikák, 2005/11/3
18
Kumulatív intenzitásfüggvény
Hálózati szimulációs technikák, 2005/11/3
Érkezési folyamat modellezése ˆ • Ha Λ(t) lineáris, akkor a stacionárius modell megfelel®. • A vizsgált példában a függvény nemlineáris (12:00 és 13:00 között nagyobb intenzitással érkeznek a vendégek), azaz az inhomogén Poisson folyamat a megfelel® modell. • A következ® kérdés: Paraméteres vagy nemparaméteres modellt
használjunk? Az ábra szerint a λ(t) intenzitásfüggvény kezdetben növekszik, aztán nagyjából konstans marad egy-másfél óráig, majd csökken. Ezt a viselkedést nehéz lenne paraméteres modellel leírni. ˆ A példában a nemparaméteres modell (Λ(t) használatával) t¶nik a legalkalmasabbnak.
Ha mégis paraméteres modellel próbálkozunk: Több lehetséges paraméteres modell létezik nemstacionárius érkezési folyamatokra. Pl: hatvány (power law) folyamatok.
19
Hálózati szimulációs technikák, 2005/11/3
20
Hatványfüggvény folyamat illesztése • Feladat: Hatványfüggvény (power law) folyamat illesztése az érkezési folyamatra. • Az intezitásfüggvény: λ(t) = λκ κtκ−1 ,
t>0
• A likelihood-függvény k realizáció esetén: n nκ n −k(λS)κ
L(λ, κ) = k λ
κ e
n Y
tκ−1 . i
i=1
• A log-likelihood függvény: log L(λ, κ) = n log(kκ) − nκ log λ − k(λS)κ + (κ − 1)
n X
log ti .
i=1
Hálózati szimulációs technikák, 2005/11/3
21
Hatványfüggvény folyamat illesztése • A log-likelihood függvény parciális deriváltjai: ∂ log L(λ, κ) κn = − kS κ κλκ−1 , ∂λ λ n
∂ log L(λ, κ) n X = n log λ + + log ti − k(λS)κ log(λS). ∂κ κ i=1 • a parciális deriváltakat nullával egyenl®vé téve a kapott ML becsl®k: ³ ´1/κ n ˆ= 1 n Pn . κ ˆ= , λ S k n log S − i=1 log ti ˆ = 4.86, κ • a konkrét példánkban: λ ˆ = 1.27. • A kumulatív intenzitásfüggvény: Λ(t) = (λt)κ ,
t>0
Hálózati szimulációs technikák, 2005/11/3
22
Empirikus és illesztett kumulatív intenzitásfüggvény
Hálózati szimulációs technikák, 2005/11/3
23
Érkezési folyamat modellezése • Példák egyéb lehetséges paraméteres nemstacionárius modellekre:
Log-logistic process (Lawless 1982): λ(t) =
λκ(λt)κ−1 , 1 + (λt)κ
t>0
EPTM exponential-polynomial-trigonometric function with multiple periodicies model (Crawford 1991): "m # p X X i λ(t) = exp αi t + γk sin(ωk t + φk ) , i=0
k=1
t>0
Hálózati szimulációs technikák, 2005/11/3
24
Modellválasztás • A modellezés kedvez® esetben leegyszer¶södik a megfelel® eloszlás kiválasztásának feladatára. • A helyzet kedvez®, ha az alábbi egyszer¶sít® feltevéseink helytállóak:
A vizsgált folyamat független, azonos (közös) eloszlású (iid) valószín¶ségi változók sorozata.
A közös eloszlás a szokásos eloszláscsaládok egyike, amelyek elérhet®k szinte minden szimulációs programcsomagban: pl. béta, Erlang, exponenciális, gamma, lognormális, normális, Poisson, egyenletes, Weibull.
Rendelkezésünkre állnak mérési eredmények, amelyre illeszthetjük az eloszlást valamilyen módszerrel, mint például: maximmum likelihood vagy momentum módszer.
A választott eloszlás jól illeszkedik az adatokra, amit valamely vizuális vizsgálattal vagy illeszkedésvizsgálattal ellen®rizhetünk.
Hálózati szimulációs technikák, 2005/11/3
25
Modellválasztás • A helyzet néha nem kedvez® az alábbi okok miatt:
A szokásos eloszláscsaládok nem eléggé rugalmasak ahhoz, hogy a meggyelt adatok sajátos jellegét leírják.
A folyamat elemei nem függetlenek. (Vagy az id®sor elemei valahogyan összefügg®ek, vagy a folyamat korrelált a rendszer más bemenetével.)
A folyamat paraméterei az id®ben változnak (nemstacionaritás). Nem áll rendelkezésünkre mérés, amire az illesztést elvégezhetnénk. • A továbbiakban néhány példát és megoldást adunk a fenti esetekre.
Hálózati szimulációs technikák, 2005/11/3
26
Egyváltozós modellek • Feladat: Olyan modellezési esetekben, amikor a változósorozat
független, azonos eloszlású (iid), amikor az eloszlásnak valamilyen szokványostól eltér® jellege van (pl. egynél több módus),
vagy nincs mért adat amire illeszteni szeretnénk, hanem az eloszlás bizonyos jellemz®it adjuk meg (pl. momentumok, percentilis).
• Modellek
Johnson eloszláscsalád Inverz eloszlás polinomiális sz¶r®vel (Bézier eloszlások)
Hálózati szimulációs technikák, 2005/11/3
27
Johnson eloszláscsalád • Az eloszlások egy rugalmasabb családja el®állítható a következ® (Johnson) transzformációval: F (x) = Φ {γ + δg[(x − ξ)/λ]} ,
−∞ < x < ∞,
ahol Φ a standard normális eloszlásfüggvény, γ és δ az alak (shape) paraméterek, ξ a helyzet (location) paraméter, λ a skála (scale) paraméter, g pedig a következ® transzformációk egyike: log(x) a lognormális családnál, sinh−1 (x) a nem korlátos családnál, g(x) = log[x/(1 − x)] a korlátos családnál, x a normális családnál.
• A megfelel® transzformáció kiválasztható egy véletlen minta ferdeségének és lapultságának becslésével, és ezek illesztésével.
Hálózati szimulációs technikák, 2005/11/3
28
Johnson eloszláscsalád (2) • A véletlen változók generálása egy Z standard normális eloszlású v.v. transzformációjával: X = ξ + λg −1 [(Z − γ)/δ], ahol
ea (ea − e−a )/2 g −1 (a) = 1/(1 + e−a ) a
a lognormális családnál, a nem korlátos családnál, a korlátos családnál, a normális családnál.
• Megjegyzés: Ha nem állnak rendelkezésre mért adatok, az eloszlás szubjektív információkra is illeszthet® (DeBrota et al., 1989).
Hálózati szimulációs technikák, 2005/11/3
29
Inverz eloszlás polinomiális sz¶r®vel • Inverse Distribution with Polinomial Filter (IDPF) • Ha a választott referencia-eloszlás illesztése után kiderül, hogy az illeszkedés nem kielégít®, akkor használható az IDPF módszer. • Ismeretlen, folytonos eloszlású v.v.-k generálásához gyakran használjuk az illesztett FX tapasztalati eloszlásfüggvény inverzét: −1 X = FX (U ),
ahol U ∼ U (0, 1) .
• Ötlet: Az illeszkedést javíthatjuk a következ® módosított transzformációval: −1 X = FX (q(U )),
ahol q az U egy polinomja.
Hálózati szimulációs technikák, 2005/11/3
30
Inverz eloszlás polinomiális sz¶r®vel (2) • Legyen q(U ) egy r-edrend¶ polinom: q(U ) = b1 U + b2 U 2 + · · · + br U r . −1 • A {bi ; i = 1, 2, . . . , r} együtthatókat úgy kell megválasztanunk, hogy FX (q(U )) legitim inverz-eloszlásfüggvény maradjon, azaz
q(U ) szigorúan növekv® U -n, q(0) = 0 és q(1) = 1. • A bi együtthatók becslése a legkisebb négyzetek módszerével megoldható: ¶¸¾2 · µ n ½ X i − 0.5 −1 2 . eˆ = min X(i) − FX q b1 ,...,br n i=1
Hálózati szimulációs technikák, 2005/11/3
31
Többváltozós modellek • Ha több véletlen változóról van szó, ezek lehetnek összefügg®ek (vektorok vagy id®sorok). • Általánosan használt modellek:
Többváltozós normál eloszlás véletlen vektorokhoz, p-edrend¶ Gauss-i autoregresszív (AR(p)) modellek id®sorokhoz. • (Id®sorok modellezését ld. kés®bb.) • Adott eloszlású véletlen vektorok el®állításához használatos módszerek:
(Johnson eloszláscsalád többváltozós kiterjesztése) (Kétváltozós Bézier eloszlások) NORTA NORmal To anything
Hálózati szimulációs technikák, 2005/11/3
32
NORTA • NORTA NORmal To Anything (Normálist bármivé) • Ötlet: Transzformáljunk egy standard (többváltozós) normális
eloszlású véletlen vektort a kívánt eloszlásúra.
• Egy Z (k × 1) véletlen vektor standard normális várható érték vektorral és 1 ρ12 · · · 1 ··· ρ21 Σ= .. .. .. . . . ρk1 ρk2 · · ·
eloszlású µ = (0, 0, . . . , 0)0
ρ1k ρ2k .. .
1
korrelációs mátrixszal, ahol az i-edik Zi elem N (0, 1) eloszlású, és ρij = Corr{Zi , Zj }.
• A Σ és µ paraméterek egyértelm¶en meghatározzák az eloszlást.
Hálózati szimulációs technikák, 2005/11/3
33
NORTA (2) • Legyen
−1 FX [Φ(Z1 )] 1
−1 FX2 [Φ(Z2 )] X= .. . −1 FXk [Φ(Zk )]
,
ahol Z = (Z1 , Z2 , . . . , Zk )0 egy standard normális eloszlású vektor Σ korrelációs mátrixszal, és FX1 , FX2 , . . . , FXk a kívánt határeloszlások.
• A feladat: Megtalálni azt a Σ mátrixot, ami X kívánt korrelációs mátrixszát eredményezi.
Ez nem túl bonyolult numerikus probléma (Cairo és Nelson, 1997). Habár az illesztés id®igényes lehet, ezt modellenként csak egyszer kell végrehajtani.