Folyamatbányászat
Werner Ágnes
[email protected]
Mi is a folyamatbányászat? — —
A folyamatbányászat célja: a folyamati adatokból valódi hasznosítható tudásanyag kinyerése. Felderíthetők és megjeleníthetők azok az összefüggések (pl. az ügyfélcsoportok, régiók, a termékek stb. között), amelyek ◦ a hosszú átfutási időért, ◦ a magas költségekért, ◦ a rossz minőségért felelősek.
—
Felderíthetőek a gyártási folyamatban megjelenő hibák, amelyek ◦ a leállásokért, ◦ a hosszabb gyártási időért felelősek.
Adatok felhasználása —
A folyamatbányászat az adatbányászat egy speciális területének is tekinthető
Kérdések, melyekre a folyamatbányászat választ adhat (pl.): Mennyire felelnek meg az esetek a folyamatmodellnek? Hol vannak a problémák? Milyen gyakori a (nem)megfelelés? Mekkora az események átlagos/min./max. végrehajtási ideje? Mik az üzleti szabályok a folyamatmodellben? Hány ember érintett az egyes eseményeknél?
Hol alkalmazhatjuk a folyamatbányászatot? — — — — — — — — —
Önkormányzatoknál (pl.: Alkmaar, Heusden, Harderwijk) Kormányzati ügynökségeknél (pl.: Rijkswaterstaat, Centraal Justitieel Incasso Bureau, Justice department) Biztosításokhoz kapcsolódó társaságoknál (pl.: UWV) Bankoknál (pl.: ING Bank) Kórházakban (pl.: AMC kórház, Catharina kórház) Multi cégeknél (pl.: DSM, Deloitte) Média vállalatoknál (pl.: Winkwaves) High-tech rendszerek gyártóinál és fogyasztóiknál (pl.: Philips Healthcare, ASML, Thales) stb.
Mivel foglalkozik a folyamatbányászat? — — — — — —
Folyamat felfedezése , feltérképezése (Process discovery): mi történik valójában? Hasonlóság elemzés (Conformance checking): az történik amit elvárunk, amit előre meghatároztunk? Teljesítményelemzés (Performance analysis): hol lehet javítani, változtatni? Folyamat előrejelzés (Process prediction): vajon egy eset be fog következni? Folyamat fejlesztés, tökéletesítés (Process improvement): hogyan alakítsuk át a folyamatot? Stb.
—
Folyamat felfedezése: milyen a valós tanterv?
—
Hasonlóság elemzés: a hallgatók találkoznak-e az előfeltételekkel?
—
Teljesítményelemzés: hol lehet változtatni?
—
Folyamat előrejelzés: be tudja fejezni a hallgató a tanulmányait?
—
Folyamat fejlesztés, tökéletesítés: hogyan lehetne újratervezni a tantervet?
Folyamat —
Olyan cselekvések vagy lépések egymás utáni sorozata, melyek eredményeképpen eljutunk egy bizonyos végpontra.
Három különböző nap tevékenységei
Sematikus folyamatmodell a példánkra
Petri-hálók A Petri-háló struktúra definíciója a következőképpen hangzik: Egy (P, T, Pre, Post) négyest Petri-háló struktúrának nevezzük, ha — P és T nemüres véges halmazok, — Pre, P × T-ből {0,1}-be képező függvény, — Post, T × P-ből {0,1}-be képező függvény. P = {p1, p2, …, pn} és T = {t1, t2, …, tm} halmazokat rendre a helyek és átmenetek halmazának nevezzük. A Pre függvény a bemeneti, a Post függvény pedig a kimeneti függvény. A Petri-hálók állapotukat tokenek segítségével fejezik ki. Egy hely tokenszámát úgy tudjuk jelölni, hogy a helynek megfelelő körbe bizonyos darab pöttyöt rajzolunk.
Folyamatkezelő információs rendszerek — — —
folyamatirányító rendszerek, pl.: WebSphere software, Staffware, Flower, Eastman software, People Soft, Adept web szerverek, pl.: Apache SCM rendszerek (Szoftver Konfiguráció Menedzsment rendszerek), pl.: Subversion, CVS
napló fájlok
Példák:
Az eseménynapló —
—
A folyamatkezelő információs rendszerek széles köre használatos a gyakorlatban az információs rendszerek mindegyike másképpen naplózza az eseményeket a folyamatkezelő információs rendszerek és a folyamatbányászati alkalmazások között meg kell találni a megfelelő kapcsolatot létezik egy meta modell a naplófájlok számára: ebben megadják az alapvető követelményeket, hogy milyen adatoknak kell feltétlenül rögzítve lenniük. A meta modellhez egy, az XML nyelv speciális változatát használják, az úgynevezett Mining XML, MXML formátumot.
Kiindulási pont: esemény napló
esemény logok, ellenőrzési naplók, adatbázisok, üzenet logok stb.
egyértelmű event log (MXML)
A Staffware rendszer saját formátumú naplózásának MXML formátumra való fordításából kapott eseménynapló egy részlete: <Source program="Staffware">
7.0
Esemény log: • folyamatok • folyamat előfordulások
complaints handling
Egy esemény: • művelet neve • (esemény típusa) • (végrehajtó) • (időbélyeg) • (adat)
<WorkflowModelElement>Case start <EventType unkowntype="case_event">unkown <Timestamp>2011-04-16T11:06:00:000+001:00 <WorkflowModelElement>Register complaint <EventType>schedule <Timestamp>2011-04-16T11:16:00:000+001:00 jvluin@staffw
A folyamatbányászat magas szintű modell diagramja
Egy lehetséges implementáció
A folyamatbányászat fontosabb perspektívái Tartalma:
log
A feladatok végrehajtásának körülményei és azok kapcsolatai
Perspektíva: Ellenőrzött folyam (control flow) perspektíva
A végrehajtó személyek / rendszerek
Szervezeti (organizational) perspektíva
További információk (adatmezők értékei) a feladatokról
Eset szerinti (case) perspektíva
Folyamatbányászati segédprogramok
A folyamatbányászat fő lépései
Folyamatbányászati eszközök EMiT (Enhanced Mining Tool) http://prom.win.tue.nl/research/wiki/discont inued/emit — Futura Reflect https://www.futura-reflect.nl — MiMo (Mining Module) http://www.exspect.com —
Folyamatbányászati eszközök: ProM — — —
nyílt forráskódú folyamatbányászati eszköz; jelenleg több mint 280 plugin érhető el az alkalmazáshoz jellemzői:
◦ az eseménynaplót MXML formátumban várja; ◦ naplózás szűrése; ◦ támogatja a legfontosabb folyamatmodelleket is inputként (Petri-háló, EPCs/EPKs (Aris gráf formátum), YAWL stb.; ◦ konvertálási lehetőségek; ◦ feltárás, bányászat; ◦ analizálás; ◦ stb.
A ProM keretrendszer architektúrája
ProM keretrendszer felhasználói felülete
Mit jelent a felfedezés, a bányászat? Folyamat modellek (pl. Petri hálók) — Szervezeti modellek — Szociális hálózatok — Szekvencia diagramok — Üzleti szabályok — Szimulációs modellek — Stb. —
A ProM fontosabb plugin-jai a folyamatbányászat perspektíváinak tükrében Perspektíva
ProM plugin
Ellenőrzött folyam perspektíva
Alpha algorithm Multi-phase Macro plugin Heuristic miner Genetic algorithm plugin
Szervezeti perspektíva
Social Network Miner Organizational Miner Analyze Social Network Originator by Task Matrix
Eset szerinti perspektíva
Performance Sequence Diagram Analysis
Egyéb
Semantic LTL Checker Conformance Checker Performance Analysis with Petri net Decision Point Analysis
MXML log - esetek: 5675 - eseménynapló bejegyzés: 67800
ProM: számos modell felfedező módszer
Analizáló eszközök Kibányászott modell felhasználásával elemzés elvégzése
Conformance checking —
—
Összehasonlítjuk a folyamat modellt és az esemény logot: kiemeljük az eltéréseket és mérjük a hasonlóságot Összehasonlítjuk a korlátozásokat/üzleti szabályokat és az esemény logot
végrehajtásuk nem engedélyezett
a tevékenységek néha nem végrehajthatóak
jó megfelelés
Fitnesz érték figyelése az események végig követésével egy trace-ben
Ha nincs probléma (m=0, r=0):
Egy másik (megvalósíthatatlan) trace
Fitnesz érték számolása
3 példa log összehasonlítása egy modellel:
Diagnosztika
Performance analysis
Események sorrendje az esetek kezdési ideje szerint
Események sorrendje időtartam alapján
„Valós” animáció
Példa log —
—
Minimális információ a logban: eset azonosító és feladat azonosító Szekvenciák: ◦ 1: ABCD ◦ 2: ACBD ◦ 3: ABCD ◦ 4: ACBD ◦ 5: EF
—
3 lehetséges szekvencia: ◦ ABCD ◦ ACBD ◦ EF
>,
, ||, # kapcsolatok
Direkt sorrend: x>y, ha valamely x esetet közvetlenül az y eset követi — Okozati viszony: x y, ha x>y és y>x — Párhuzamosság: x||y, ha x>y és y>x — Választás: x#y, ha nem x>y és nem y>x —
Alap ötletek
Alpha algoritmus
A példa ábrázolása:
Példa az α-algoritmus-ra: Példánk egy cég telefonjavítási folyamatát mutatja be. 1. 2. 3.
4. 5.
6. 7. 8. 9.
Három féle telefontípust képesek helyrehozni (T1, T2, T3). A folyamat azzal indul, hogy regisztrálják a telefonkészüléket, amelyet a megbízó küldött. Miután ez végbement, a telefon a Probléma Detektálási (PD) részlegre kerül. Itt elemzik a hiba okát és az általuk 10 féle javítási kategóriába sorolják. Ha ez megtörtént a készülék a hiba adataival együtt a Javítási (R) részlegre kerül. A Javítási részlegnek két csoportja van. Az egyik, amely az egyszerűbb hibákat javítja, a másik a bonyolultabb meghibásodások javításaiért felelős. Léteznek olyan hibák is, amelyeket mindegyik csapat meg tud javítani. Miután helyrehozták a készüléket a Minőség Ellenőrzés veszi át az irányítást, ahol megbizonyosodnak a hiba tényleges kijavításáról. Ha a telefon újabb javításokra szorul, visszakerül a Javítási részlegre. Ha a készülék immár hibátlan, az ügyet archiválják, és a telefont visszaküldik a megbízónak. Ha bizonyos javítás után sem lehet helyrehozni a telefont, az ügyet akkor is lezárják, és az ügyfél kap egy teljesen új készüléket.
A folyamat eseménynaplójának egy részlete: <WorkflowLog xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:noNamespaceSchemaLocation="http://is.tm.tue.nl/research/processmining/WorkflowLog.xsd" description="CPN Tools simulation log"> <Source program="CPN Tools simulation"/> <WorkflowModelElement>Register <EventType >complete <Timestamp>1970-01-02T12:23:00.000+01:00 System <WorkflowModelElement>Analyze Defect <EventType >start <Timestamp>1970-01-02T12:23:00.000+01:00 Tester3 T2 6 <WorkflowModelElement>Analyze Defect <EventType >complete <Timestamp>1970-01-02T12:30:00.000+01:00 Tester3
A feladat Petri hálója – Alpha algoritmus használata
Az Alpha algoritmus tulajdonságai —
A bányászathoz csak az SWF-nets (Structured Workflow Nets) használható és ennek a hálónak vannak nem implicit helyei, a következő 2 szerkezet nem használható:
Problémás szerkezetek
Megoldás: pl. Genetikus bányászat
A genetikus algoritmus átalakítása Genetikus algoritmus(GA) populáció
log
Fitnesz érték számolása & Szelekció
Mutáció
Keresztezés
Reprezentáció: ok-okozati mátrix
Folyamat modell
Példa egy log fájlra a genetikus algoritmus esetében
Ok-okozati mátrix INPUT
A Petri háló nehezen kezelhető a GA esetében
true
A
B
B
C&D
A
A
EVFVG
A
B
C
D
E
F
G
H
OUTPUT
A
0
1
0
0
0
1
1
0
BVFVG
B
0
0
1
1
0
0
0
0
C&D
C
0
0
0
0
1
0
0
0
E
D
0
0
0
0
1
0
0
0
E
E
0
0
0
0
0
0
0
1
H
F
0
0
0
0
0
0
0
1
H
G
0
0
0
0
0
0
0
1
H
H
0
0
0
0
0
0
0
0
true
Ok-okozati mátrix: egy n*n-es mátrix, ahol n a műveletek száma
A felépített modell ellenőrzése az első esetre a logban
INPUT
true
A
B
B
C&D
A
A
EVFVG
A
B
C
D
E
F
G
H
OUTPUT
A
0
1
0
0
0
1
1
0
BVFVG
B
0
0
1
1
0
0
0
0
C&D
C
0
0
0
0
1
0
0
0
E
D
0
0
0
0
1
0
0
0
E
E
0
0
0
0
0
0
0
1
H
F
0
0
0
0
0
0
0
1
H
G
0
0
0
0
0
0
0
1
H
H
0
0
0
0
0
0
0
0
true
Egy kiindulási populáció kialakítása a függőségi mérték értékén alapul Legyen t1 és t2 két művelet a T log fájlban. Ekkor
follows(t1,t2) = ahányszor „t1t2” megjelenik a logban L1L(t1) = a „t1t1” hányszor fordul elő a logban L2L(t1,t2) = a „t1t2t1” hányszor fordul elő a logban
Az egyedek fitnesz értékének számítása Legyen L egy eseménynapló és PM egy folyamati modell. Ekkor
PM: folyamat modell L: Log fájl numActivitiesLog(L) = a műveletek száma az L log fájlban numTracesLog(L) = a trace-ek száma a log fájlban allParsedActivities(PM,L) = minden trace minden művelete allCompletedLogTraces(PM,L) = sikeresen elemzett trace-ek száma allProperlyCompletedLogTraces(PM,L) = sikeresen elemzett traceek száma, ahol az end segédváltozó értéke 1, míg az összes többi értéke 0
Gyakorlathoz Telefonjavítási folyamat
1.
1.
Alpha algoritmus Garázskapu működésének folyamata
2.
1.
Alpha algoritmus
2.
Conformance checking
3.
Torlódás vizsgálat (Performance analysis)
4.
Animáció Kiszállítási feladat
3.
1.
Alpha algoritmus
2.
Genetikus algoritmus
3.
Trace-ek összehasonlítása (Trace comparison)
4.
Kapcsolati mátrix (Originator by task matrix)
Kiindulási modell – Hibamentes
Kiindulási modell – Hibaészlelés
Kiszállítási probléma vizsgálata System transfers the orders Agent gets targets Agent loads his car Agent starts to deliver Agent reaches the customer Agent gives down the product Agent has technical problem Agent changes the best root Agent can’t reach the customer Agent can’t deliver the product Other agent helps to deliver Other agent reaches the customer
A számítógépes rendszer rögzíti a rendeléseket és továbbítja A futár megkapja a kiszállítási címeket A futár feltölti a telephelyen az autóját A futár megkezdi a kiszállítást A futár eléri az ügyfelet (fizikailag) A futár leadja a terméket A futárnak műszaki problémája lép fel A futár másik útvonalat választ A futár nem éri el az ügyfelet (fizikailag) A futár képtelen kiszállítani a terméket Másik futár segít a kiszállításban Másik ügynök eléri az ügyfelet (fizikailag)
Other agent gives down the product To serve all the customers has been failed Agent finished the delivery Other agent finished the delivery
Másik futár adja le a terméket Nem sikerült az összes ügyfelet kiszolgálni A futár befejezte a kiszállítást (sikeresen) Másik futár befejezi a kiszállítást (sikeresen)
Az eseménynaplóban lévő események azonosítói
Az eseménynapló egy részlete
