Bemenet modellezése II

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


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.


Kiszolgálási id®k vs. meggyelés sorszáma

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, ...


Minta autokorrelációs függvény

5


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


7

Hisztogramm


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.


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.


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


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


12

Az illesztett Weibull eloszlás


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


14

P-P (probability-probability) Plot


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.


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


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


18

Kumulatív intenzitásfüggvény


É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


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


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


22

Empirikus és illesztett kumulatív intenzitásfüggvény


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


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.


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.


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)


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.


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).


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.


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


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


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.


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.

Bemenet modellezése II

Recommend Documents