Kvantitativní analýza
internetového provozu (4)
Ladislav Lhotka
lhotka@cesnet.cz
Osnova přednášky
* Práce se vzorky datových toků (spojení)
* Analýza mnohorozměrných dat, data mining
* Principal Component Analysis
* Cluster Analysis
* Interaktivní průzkum dat, vizualizace
2
Vzorky datových toků
Toky představují střední úroveň agregace, na vysokorychlostních linkách
ale i tak generují velký objem dat.
Časové parametry sběru toků:
* inactive timeout ­ ukončení toku
* active timeout ­ průběžná data (vhodné pro dlouhotrvající toky)
Pětiminutový vzorek dat z mezinárodní linky do GÉANT2 ­ záznamy o
paketech získané pomoci 10 GE karty DAG (Endace).
* 578944960 bajtů
* 6163012 paketů
* 152010 toků (inact. timeout = 10 s)
* 45284 různých párů IP adres
3
Záznam o paketu
print 6163011: file offset 0x2281ff60
ts=0x4603e58b95f3efc0 2007-03-23 14:34:51.5857534 UTC
type: ERF Ethernet
dserror=0 rxerror=0 trunc=0 vlen=1 iface=0 rlen=96 lctr=0 wlen=1438
dst=00:90:69:f5:dd:7a src=00:0e:38:a4:c4:40
etype=0x0800
ip: version=4 headerwords=5 tos=0 length=1420
ip: id=38972 flags=0x2 fragmentoffset=0
ip: ttl=62 protocol=6 checksum=0xa4da
ip: sourceaddress=195.113.232.82
ip: destinaddress=61.14.17.131
tcp: sourceport=80 destinport=41262
tcp: sequence=0xf460818c
tcp: acknowledgement=0x36ac4dd9
tcp: offset=5 control=16 window=8576
tcp: checksum=0x5483 urgent=0
4
Zastoupené IP adresy
5
Počty bajtů
Celkový počet bajtů pro konkrétní pár IP adres:
6
"Čára" poblíž nuly
7
Vícerozměrná experimentální data
Měříme p parametrů:
X = (X1, X2, . . . , Xp)
Střední hodnota Xi je i pro i = 1, 2, . . . , p
Vzorek n pozorování:
X =




X11 X12 . . . X1p
X21 X22 . . . X2p
... ... ... ...
Xn1 Xn2 . . . Xnp




8
Principal Component Analysis
Cíl: Nálezt vhodnou ortogonální transformaci souřadnic, v níž bude charakter
dat co nejzřetelnější, vyniknou "ulétlá" měření (outliers) atd.
První hlavní komponenta: lineární kombinace původních proměnných
Y1 = 11X1 + 21X2 +    + p1Xp
Chceme nalézt takové koeficienty, aby Y1 měla maximální rozptyl.
a1 =




11
21
...
p1




9
Rozptyl lineární kombinace
1 = E(Y1) = 111 + 212 +    + p1p
D(Y1) = E((Y1 - 1)2
) = E((a1(X - ))2
)
= E(a1(X - )(X - ) a1) = a1Ca1,
kde C je kovarianční matice:
Cij = C(Xi, Xj).
V praxi používáme odhad kovarianční matice ze vzorku a a1Ca1 je pak
odhad rozptylu Y1.
10
Optimalizační úloha
D(Y1) = a1Ca1 - max
s normalizační podmínkou a1a1 = 1.
Jde tedy o nalezení vázaného extrému, který se řeší metodou Lagrangeových
multiplikátorů. Výsledek:
Ca1 = 1a1. (1)
Lagrangeův multiplikátor 1 je tedy vlastním číslem matice C a a1 je
příslušný vlastní vektor.
Z rovnice (1) plyne D(Y1) = a1Ca1 = 1, takže za 1 volíme největší vlastní
číslo.
11
Další hlavní komponenty
Druhá hlavní komponenta
Y2 = 12X1 + 22X2 +    + p2Xp
D(Y2) = a2Ca2 - max
za podmínek a2a2 = 1 a a2a1 = 0 (ortogonalita).
Vyjde Ca2 = 2a2, kde 2 volíme jako druhé největší vlastní číslo a a2 je
pak příslušný vlastní vektor.
12
Souřadná soustava hlavních komponent
A =




11 12 . . . 1p
21 22 . . . 2p
... ... ... ...
p1 p2 . . . pp




Transformace souřadnic:
Y = A X
Navíc platí
A CA = ,
kde  = diag(1, 2, . . . , p).
Podíl i-té hlavní komponenty na rozptylu: i/tr(C).
13
Redukce dimenze
Zvolíme jen několik hlavních komponent, což odpovídá projekci do vektorového
podprostoru generovaného příslušnou podmnožinou vlastních
vektorů.
^A =




11 12 . . . 1q
21 22 . . . 2q
... ... ... ...
p1 p2 . . . pq



 ,
kde q < p. X pak transformujeme na kratší vektor:
^Y = ^A X.
14
Cluster analysis
Cluster (shluk) je založen na pojmu blízkosti nebo podobnosti určité skupiny
objektů (měření), který je kvantifikován koeficientem nepodobnosti
(dissimilarity).
Vlastnosti:
1. X : d(X, X) = 0
2. X, Y : d(X, Y) = d(Y, X)  0
Speciálním případy je metrika, která musí navíc splňovat
X, Y, Z : d(X, Y)  d(X, Z) + d(Z, Y)
nebo ultrametrika, pro niž navíc platí:
X, Y, Z : d(X, Y)  max(d(X, Z), d(Z, Y)).
15
Vzdálenost mezi clustery
1. single linkage
s(X, Y) = min{d(x, y)|x  X, y  Y}
2. complete linkage
c(X, Y) = max{d(x, y)|x  X, y  Y}
3. average linkage
a(X, Y) =
1
|X||Y|

xX
yY
d(x, y)
16
Vlastnosti shlukovacích algoritmů
Podle způsobu vytváření shluků se dělí na aglomerativní a divizivní.
Podle uspořádání shluků různé velikosti se dělí na hierarchické a nehie-
rarchické.
Shluky jsou obvykle disjunktní, jinak jde o tzv. fuzzy clustering.
Metody shlukování se dělí na sekvenční a simultánní.
Nejběžnějšími metodami jsou aglomerativní hierarchické ­ výstuoem je
tzv. dendrogram.
17
Algoritmus (naivní)
1. Na začátku tvoří každý objekt svůj vlastní cluster. Vypočítá se matice
vzdáleností mezi těmito jednoprvkovými clustery. Položíme L = 0
(level).
2. V matici vzdáleností se najde minimální hodnota, odpovídající clusterům
Ci a Cj. Položíme L = (Ci, Cj).
3. Z matice se vyjmou i-tý a j-tý řádek i sloupec a doplní se nový řádek
a sloupec pro nový cluster Cij = Ci  Cj.
4. Je-li matice vzdáleností jednoprvková, pak skonči, jinak jdi na 2.
18
Interaktivní průzkum dat
Program GGobi: http://www.ggobi.org
Funguje samostatně nebo ve spojení s R.
19