Self-podobnost analýzy síťových dat - Self-Similarity of Network Data Analysis

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Březen 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v počítačové sítě, sebepodobnost je funkce dynamiky přenosu dat v síti. Při modelování dynamiky síťových dat se používají tradiční modely časových řad, například autoregresní model klouzavého průměru (ARMA (p, q)), nejsou vhodné. Je to proto, že tyto modely poskytují pouze konečný počet parametrů v modelu a tedy interakci v konečném časovém okně, ale síťová data mají obvykle závislé na velké vzdálenosti časová struktura. Self-podobný proces je jedním ze způsobů modelování dynamiky síťových dat s takovým dlouhým dosahem korelace. Tento článek definuje a popisuje dynamiku přenosu dat v síti v kontextu podobného procesu. Jsou uvedeny vlastnosti procesu a jsou uvedeny metody pro vytváření grafů a odhad parametrů modelování sebepodobnosti síťových dat.

Definice

Předpokládat ${ displaystyle X}$ být slabě stacionární (stacionární) proces 2. řádu s průměrem ${ displaystyle mu}$rozptyl ${ displaystyle sigma ^ {2}}$, a autokorelace funkce ${ displaystyle gamma (t)}$Předpokládejme, že funkce autokorelace ${ displaystyle gamma (t)}$ má formu${ displaystyle gamma (t) pravá šipka t ^ {- beta} L (t)}$ tak jako ${ displaystyle t to infty}$, kde ${ displaystyle 0 < beta <1}$a ${ displaystyle L (t)}$ je pomalu se měnící funkce na nekonečno, to je ${ displaystyle lim _ {t to infty} { frac {L (tx)} {L (t)}} = 1}$ pro všechny ${ displaystyle x> 0}$.Například, ${ displaystyle L (t) = const}$ a ${ displaystyle L (t) = log (t)}$ jsou pomalu se měnící funkce.
Nechat ${ displaystyle X_ {k} ^ {(m)} = { frac {1} {m ^ {H}}} (X_ {km-m + 1} + cdot cdot cdot + X_ {km}) }$,kde ${ displaystyle k = 1,2,3, ldots}$, označuje agregovanou řadu bodů přes nepřekrývající se bloky velikosti ${ displaystyle m}$, pro každého ${ displaystyle m}$ je kladné celé číslo.

Přesně podobný proces

• ${ displaystyle X}$ se nazývá přesně podobný proces, pokud existuje podobný parametr ${ displaystyle H}$ takhle ${ displaystyle X_ {k} ^ {(m)}}$ má stejnou distribuci jako ${ displaystyle X}$. Příklad přesně podobného procesu s ${ displaystyle H}$ je Frakční Gaussův šum (FGN) s ${ displaystyle { frac {1} {2}}$.

Definice: Fractional Gaussian Noise (FGN)

${ displaystyle X (t) = B_ {H} (t + 1) -B_ {H} (t), ~ forall t geq 1}$ se nazývá Fractional Gaussian Noise, kde ${ displaystyle B_ {H} ( cdot)}$ je Frakční Brownův pohyb.^[1]

přesně podobný proces druhého řádu

• ${ displaystyle X}$ se nazývá přesně podobný samoobslužný proces druhého řádu, pokud existuje obdobný parametr ${ displaystyle H}$ takhle ${ displaystyle X_ {k} ^ {(m)}}$ má stejnou odchylku a autokorelaci jako ${ displaystyle X}$.

asymptotický podobný proces druhého řádu

• ${ displaystyle X}$ se nazývá asymptotické sebepodobný proces druhého řádu s obdobným parametrem ${ displaystyle H}$ -li ${ displaystyle gamma ^ {(m)} (t) až { frac {1} {2}} [(t + 1) ^ {2H} -2t ^ {2H} + (t-1) ^ { 2H}]}$ tak jako ${ displaystyle m to infty}$, ${ displaystyle ~ forall t = 1,2,3, ldots}$

Některé relativní situace podobných procesů

Závislost na velké vzdálenosti (LRD)

Předpokládat ${ displaystyle X (t)}$ být slabě stacionární (stacionární 2. řád) proces s průměrem ${ displaystyle mu}$ a rozptyl ${ displaystyle sigma ^ {2}}$. Funkce autokorelace (ACF) se zpožděním ${ displaystyle t}$ darováno ${ displaystyle gamma (t) = { mathrm {cov} (X (h), X (h + t)) nad sigma ^ {2}} = {E [(X (h) - mu) (X (h + t) - mu)] přes sigma ^ {2}}}$

Definice:

Za slabě stacionární proces se považuje „závislost na velké vzdálenosti“, pokud ${ displaystyle sum _ {t = 0} ^ { infty} | gamma (t) | = infty}$

Proces, který uspokojuje ${ displaystyle gamma (t) pravá šipka t ^ {- beta} L (t)}$ tak jako ${ displaystyle t to infty}$ se říká, že má závislost na velké vzdálenosti. The spektrální hustota následuje funkce závislosti na velké vzdálenosti a mocenský zákon blízko původu. Ekvivalentně k ${ displaystyle gamma (t) pravá šipka t ^ {- beta} L (t)}$, ${ displaystyle X}$ má závislost na velké vzdálenosti, pokud je funkce spektrální hustoty autokorelační funkce, ${ displaystyle f_ {t} (w) = součet _ {t = 0} ^ { infty} gamma (t) e ^ {iwt}}$, má podobu ${ displaystyle w ^ {- gamma} L (w)}$ tak jako ${ displaystyle w to 0}$ kde ${ displaystyle 0 < gamma <1}$, ${ displaystyle L}$ se pomalu mění na 0.

také vidět

Pomalu se rozpadající odchylky

${ displaystyle X ^ {(m)} = { frac {1} {m}} (X_ {1} + cdot cdot cdot + X_ {m})}$
Když funkce autokorelace podobného procesu vyhovuje ${ displaystyle gamma (t) pravá šipka t ^ {- beta} L (t)}$ tak jako ${ displaystyle t to infty}$, to znamená, že také uspokojuje ${ displaystyle Var (X ^ {(m)}) na am ^ {- beta}}$ tak jako ${ displaystyle m to infty}$, kde ${ displaystyle a}$ je konečná kladná konstanta nezávislá na m a 0 <β <1.

Odhad parametru vlastní podobnosti "H"

R / S analýza

Předpokládejme, že podkladový proces ${ displaystyle X}$ je Fractional Gaussian Noise. Zvažte sérii ${ displaystyle X _ {(1)}, ldots, X _ {(n)}}$a nechte ${ displaystyle Y _ {(n)} = součet _ {i = 1} ^ {n} X _ {(i)}}$.

Rozptyl vzorku z ${ displaystyle X _ {(i)}}$ je ${ displaystyle S ^ {2} (n) = { frac {1} {n}} součet _ {i = 1} ^ {n} X _ {(i)} ^ {2} - ({ frac { 1} {n}}) ^ {2} Y_ {n} ^ {2}}$

Definice: Statistika R / S

${ displaystyle { frac {R} {S}} (n) = { frac {1} {S (n)}} [ max _ {0 leq t leq n} (Y_ {t} - { frac {t} {n}} Y_ {n}) - min _ {0 leq t leq n} (Y_ {t} - { frac {t} {n}} Y_ {n})]}$

Li ${ displaystyle X _ {(i)}}$ je tedy FGN ${ displaystyle E ({ frac {R} {S}} (n)) na C_ {H} krát n ^ {H}}$
Zvažte použití regresního modelu:${ displaystyle log { frac {R} {S}} (n) = log (C_ {H}) + H log (n) + epsilon _ {n}}$, kde${ displaystyle epsilon _ {n} thicksim N (0, sigma ^ {2})}$
Zejména pro časovou řadu délky ${ displaystyle N}$ rozdělit data časové řady na ${ displaystyle k}$ skupiny každé velikosti ${ displaystyle { frac {N} {k}}}$, vypočítat ${ displaystyle { frac {R} {S}} (n)}$ pro každou skupinu.
Tak pro každé n máme ${ displaystyle k}$ dvojice dat (${ displaystyle log (n), log { frac {R} {S}} (n)}$).Existují ${ displaystyle k}$ body za každého ${ displaystyle n}$, takže se nám vejde a regresní model odhadovat ${ displaystyle H}$ přesněji. Pokud je sklon regresní přímka je mezi 0,5 ~ 1, jedná se o podobný proces.

Časově závislý graf

Rozptyl výběrového průměru je dán vztahem ${ displaystyle Var ({ bar {X}} _ {n}) to cn ^ {2H-2}, ~ forall c> 0}$.
Pro odhad H vypočítat vzorek znamená ${ displaystyle { bar {X}} _ {1}, { bar {X}} _ {2}, cdots, { bar {X}} _ {m_ {k}}}$ pro ${ displaystyle m_ {k}}$ dílčí řada délky ${ displaystyle k}$ .
Celkový průměr může být dán vztahem ${ displaystyle { bar {X}} (k) = { frac {1} {m_ {k}}} součet _ {i = 1} ^ {m_ {k}} { bar {X}} _ {i} (k)}$, rozptyl vzorku ${ displaystyle S ^ {2} (k) = { frac {1} {m_ {k} -1}} součet _ {i = 1} ^ {m_ {k}} ({ bar {X}} _ {i} (k) - { bar {X}} (k)) ^ {2}}$.
Grafy rozptylu a času se získají vynesením ${ displaystyle log S ^ {2} (k)}$ proti${ displaystyle log k}$ a můžeme vložit jednoduchou nejmenší čtvercovou čáru přes výsledné body v rovině ignorující malé hodnoty k.

Pro velké hodnoty ${ displaystyle k}$se očekává, že body v grafu budou rozptýleny kolem přímky se záporným sklonem ${ displaystyle 2H-2}$Pro závislost na krátkém dosahu nebo nezávislost mezi pozorováními je sklon přímky roven -1.
Autopodobnost lze odvodit z hodnot odhadovaného sklonu, který je asymptoticky mezi –1 a 0, a odhad míry sebepodobnosti je dán vztahem ${ displaystyle { hat {H}} = 1 + { frac {1} {2}} (sklon).}$

Analýza založená na periodogramu

Whittleův přibližný odhad maximální pravděpodobnosti (MLE ) se používá k vyřešení parametru Hurst prostřednictvím spektrální hustota z ${ displaystyle X}$. Nejde jen o nástroj pro vizualizaci Hurstova parametru, ale také o metodu statistického odvození parametrů pomocí asymptotických vlastností MLE. Zejména, ${ displaystyle X}$ následuje a Gaussův proces. Nechte spektrální hustotu ${ displaystyle X}$,${ displaystyle f_ {x} (w; theta) = sigma _ { epsilon} ^ {2} f_ {x} (w; (1, eta))}$, kde${ displaystyle theta = ( sigma _ { epsilon} ^ {2}, eta) = ( sigma _ { epsilon} ^ {2}, H, theta _ {3}, ldots, theta _ {k}), H = { frac { gamma +1} {2}}}$, a ${ displaystyle theta _ {3}, ldots, theta _ {k}}$ postavit model autoregrese časových řad krátkého dosahu (AR), to znamená ${ displaystyle X_ {j} = součet _ {i = 1} ^ {k} alpha _ {i} X_ {j-i} + epsilon _ {j}}$,s ${ displaystyle Var ( epsilon _ {j}) = sigma _ { epsilon} ^ {2}}$.

Tedy odhadce Whittle ${ displaystyle { hat { eta}}}$ z ${ displaystyle eta}$ minimalizovat funkci ${ displaystyle Q ( eta) = int _ {- pi} ^ { pi} { frac {I (w)} {f (w; (1, eta))}} dw}$, kde I (w) označuje periodogram X jako ${ displaystyle (2 pi n) ^ {- 1} | součet _ {j = 1} ^ {n} X_ {j} e ^ {iwj} | ^ {2}}$ a ${ displaystyle { hat { sigma}} ^ {2} = int _ {- pi} ^ { pi} { frac {I (w)} {f (w; (1, { hat { eta}}))}} , dw}$. Tyto integrace lze posoudit Riemannovým součtem.

Pak ${ displaystyle n ^ {1/2} ({ hat { theta}} - theta)}$ asymptoticky následuje normální rozdělení, pokud ${ displaystyle X_ {j}}$ lze vyjádřit jako formu modelu nekonečného klouzavého průměru.

Odhadovat ${ displaystyle H}$, nejprve je třeba vypočítat tento periodogram. Od té doby${ displaystyle I_ {n} (w)}$ je odhad spektrální hustoty, série se závislostí na velké vzdálenosti by měla mít periodogram, který je úměrný ${ displaystyle | lambda | ^ {1-2H}}$ blízký původu. Graf periodogramu se získá vynesením${ displaystyle log (I_ {n} (w))}$ proti ${ Displaystyle log (w)}$.
Pak se hodí regresní model ${ displaystyle log (I_ {n} (w))}$ na ${ Displaystyle log (w)}$ by měl dát sklon ${ displaystyle { hat { beta}}}$. Sklon upravené přímky je také odhadem ${ displaystyle 1-2H}$. Tedy odhad ${ displaystyle { hat {H}}}$ je získáno.

Poznámka:
Při použití metody periodogramu existují dva běžné problémy. Za prvé, pokud data nenásledují Gaussovo rozdělení, transformace dat může vyřešit tento druh problémů. Zadruhé, spektrum vzorku, které se odchyluje od předpokládané spektrální hustoty, je další. K řešení tohoto problému se navrhuje metoda agregace. Li ${ displaystyle X}$ je Gaussův proces a funkce spektrální hustoty ${ displaystyle X}$ splňuje ${ displaystyle w ^ {- gamma} L (w)}$ tak jako ${ displaystyle w to infty}$, funkce,${ displaystyle m ^ {- H} L ^ {- { frac {1} {2}}} (m) součet _ {i = (j-1) m + 1} ^ {m} k (X_ { i} -E (| X_ {i} |)), ~ j = 1,2, ldots, [{ tfrac {n} {m}}]}}$, konverguje v distribuci na FGN as ${ displaystyle m to infty}$.

Reference

• P. Whittle, „Odhad a informace ve stacionárních časových řadách“, čl. Rohož. 2, 423-434, 1953.
• K. PARK, W. WILLINGER, Self-Similar Network Traffic and Performance Evaluation, WILEY, 2000.
• W. E. Leland, W. Willinger, M. S. Taqqu, D. V. Wilson, „O sebepodobné povaze ethernetového provozu“, ACM SIGCOMM Computer Communication Review 25,202-213,1995.
• W. Willinger, M. S. Taqqu, W. E. Leland, D. V. Wilson, „Self-Podobnost ve vysokorychlostním paketovém provozu: Analýza a modelování měření ethernetového provozu“, Statistics Science 10,67-85,1995.