INVERZ FERTŐZÉSI PROBLÉMA Bóta András SZTE, Informatika
Pluhár András SZTE, Informatika
Tartalom • Fertőzési modellek • Domingos-Richardson (kaszkád) modell • Általánosított Kaszkád modell • Inverz fertőzési probléma • „Particle Swarm” optimalizálás • Pénzügyi alkalmazás
Eredet • Epidemiológia • SI, SIR, SIRS, … • Szociológia • Linear Threshold (Granovetter, 1978) • Gazdaságtan • Independent Cascade Model (Domingos-Richardson, 2001) • Generalized Cascade Model (Bóta et al., 2011)
Fertőzési modellek • Input • G(V, E) gráf • Egy e él súlya 𝑤𝑒 • 0 ≤ 𝑤𝑒 ≤ 1 • Kezdetben fertőzöttek 𝐴0 • Output • A t időpontban fertőzöttek 𝐴𝑡 • Iteráció • Állapotok • Susceptible (veszélyeztetett) • Infected (fertőzött) • Recovered (gyógyult)
Független kaszkád (D-S) modell
• Minden iterációban, amíg 𝐴𝑡 ≠ ∅ • Az újonnan aktivált pontok halmaza: 𝐴𝑖 • Minden 𝑣 ∈ 𝐴𝑖 megfertőzi az inaktív 𝑢 pontot 𝑤𝑢,𝑣 valószínűséggel • Ha ez sikeres, az u fertőzött lesz az 𝑖 + 1 iterációban
Általánosított kaszkád modell • Kezdeti fertőzés → A priori eloszlás • Fertőzött pontok → A poszteriori eloszlás • Az eloszlás forrása • Lemorzsolódás (churn) valószínűség • Kredit default valószínűség • gyakoriságok • Fertőzési folyamat • Független kaszkád modell
Ha adott a 𝐺 súlyozott gráf és a 𝑝𝑣 a priori eloszlás minden 𝑣 ∈ 𝑉 (𝐺), a modell megadja a 𝑝𝑣′ a posteriori fertőzési eloszlást minden 𝑣 ∈ 𝑉 (𝐺).
A fertőzési modellek alkalmazása • Fertőzés maximalizálás probléma • Találjunk olyan 𝑘 elemű kezdő halmazt, amely a legnagyobb várható fertőzést okozza (adott 𝑘 -ra) • NP-nehéz (Kempe-Kleinberg-Tardos, 2003) • Fertőzési valószínűségek kiszámítása • Adott kezdeti fertőzés esetén, számoljuk ki egy tetszőleges 𝑣 ∈ 𝑉 𝐺 pont fertőződésének a valószínűségét. • #P-teljes (Chen et al., 2009) • Inverz fertőzési probléma • Honnan vegyük a 𝑤𝑒 értékeket?
Inverz fertőzési probléma Ha adott a G gráf, a 𝑝𝑣 és 𝑝𝑣′ a priori és a poszteriori eloszlások, számoljuk ki az ezt eredményező 𝑤𝑒 él fertőzési valószínűségeket, 𝑒 ∈ 𝐸 𝐺 . • Feltételek (egyszerűsítések) • Az éleknek attribútumai vannak • 𝑤𝑒 az attribútumok függvénye • Csak a függvények paramétereit becsüljük • Attribútum függvények • Polinomok • Normalizálás
Inverz fertőzési probléma • Becslés • A poszteriori eloszlás a referencia halmaz • Véletlen kezdeti paraméterekből indulunk • A GC modellt futtatjuk ismételten • Minimalizáljuk a referencia halmaz és az aktuális fertőzés eltérését • Heurisztikák az IC/GC modellekre • DAG, LDAG (Chen et al., 2011) • CompleteSim, EdgeSim, NBH, ALE (Bóta et al., 2012)
„Particle Swarm” optimalizálás • Hiba felület • A dimenziók száma 1 és 20 között • A heurisztikától függő zaj • Alul determinált probléma: hegyek/völgyek • Fully Informed Particle Swarm (Kennedy-Mendes, 2006) • A részecskéknek van • pozíciója (paraméterek)
• sebessége
• Egymással környezet definícióknak megfelelően hatnak kölcsön • A pozíciók és sebességek szinkronban változnak minden
iterációban
Input • Network • OTP Bank Plc. Corporate (B2B) tranzakciós adatbázis • A tranzakciók (utalások) havi összegzése • Időszak: 2012 április és 2013 március között • Bizonyos összegkorlát felett • Bizonyos gyakoriság felett
• A priori fertőzés • Az ügyfél defaultba került 2013 január és március között
• A poszteriori fertőzés • Az ügyfél defaultba került 2013 április és június között
Attribútumok 1. 2. 3. 4. 5.
6. 7. 8.
9.
Az utalások száma Az átutalt összeg Az ügyfélhez befolyó teljes összeg Közösségi információ: az adott él egy közösség belső éle-e (bináris változó) Relatív forgalom, az él forgalma osztva a pontba befolyó összeggel A cég kora Esetleges sorban állás (követelés) a számlán Hitelkeret túllépés A megrendelő önkormányzat-e vagy sem (bináris)
Tapasztalatok • A becslés leghatékonyabb a „legrosszabb” ügyfelekre 𝑻𝑶𝑷 % 𝒅𝒆𝒇𝒂𝒖𝒍𝒕 𝒓𝒂𝒕𝒆 𝒂𝒗𝒆𝒓𝒂𝒈𝒆 𝒅𝒆𝒇𝒂𝒖𝒍𝒕 𝒓𝒂𝒕𝒆
Constant weights
NBH
ES
CS
TOP 1%
0,79
7,77
7,82
8,09
TOP 3%
2,17
8,51
8,77
8,46
TOP 5%
2,89
7,97
7,97
7,74
TOP 10%
3,16
4,97
4,99
4,92
AUC
65,39%
72,40%
72,49%
71,6%
AUC (lower bound)
62,97%
69,90%
69,99%
69,2%
AUC (upper bound)
67,81%
74,90%
74,98%
74,1%
GINI
7,69%
11,20%
11,24%
10,8%
Other measurements
Tapasztalatok • Irányított vs. irányítatlan • Számít az irányítás • Az élek szűrése javít a viselkedésen • Fertőzési valószínűségek • Folytonos • Bináris • A leghasznosabb változók • Relatív forgalom • Közösségi információ
KÖSZÖNETNYILVÁNÍTÁS Jelen kutatást a futurICT.hu nevű, TÁMOP-4.2.2.C11/1/KONV-2012-0013 azonosítószámú projekt támogatta az Európai Unió és az Európai Szociális Alap társfinanszírozása mellett.
