Adatbányászati módszerek alkalmazása a Robert Bosch számára Készítette: Tóth Zsolt Neptun kód: F23Y80
Témavezet®: Dr. Kovács László
Ipari konzulens: Gróf Richárd
Miskolci Egyetem, 2010
1. fejezet
Bevezetés 1.1. A dolgozat célja A dolgozatban a Robert Bosch cég hatvani üzemében alkalmazott optikai ellen®rz® berendezésekb®l kapott adatok feldolgozására egy olyan módszert dolgozok ki, amelynek célja a gépek esetleges meghibásodásának el®re jelzése. A dolgozatban bemutatom az el®rejelzések készítéséhez alkalmazott módszereket. A dolgozat elején röviden áttekintem az elektronikai eszközök gyártásának folyamatát, az AOI1 szerepét a gyártásban, az AOI-ASC2 -t, valamint az implementált monitor alkalmazást. A problémakör ismertetése után bemutatom az alkalmazni kívánt matematikai módszereket. Részletesen elemzem a felhasznált statisztikai és adatbányászati módszerekkel az adathalmazt. A kapott eredmények megfelel® vizsgálatához a mért adatokon kívül teszt adatok generálása is szükséges. A dolgozatban bemutatom a teszt adatok generálására szolgáló algoritmusokat. A teszt adatok segítségével alátámasztom az egyes algoritmusok helyességét. A dolgozat következ® részében ismertetem a probléma megoldására kidolgozott eljárásokat. Elemzem az egyes módszereket és az elvárt, illetve a kapott eredményeket. A kapott eredmények mellet ismertetem az eredmény zikai jelentését is, bemutatom a levonható következtetéseket. A dolgozat végén összefoglalom az elért eredményeket. Összehasonlítom az elvárásokat és az elért eredményeket. Bemutatom a f® alkalmazásokat, végül ismertetem a továbbfejlesztési lehet®ségeket. 1 2
Automated Optical Inspection AOI Safety Check
2
1.2. A RBHH bemutatása Az RBHH a Bosch csoport tagja. A Bosch csoport a világ 150 országában jelen van. Jelent®s szerepl®k az auto-elektronika, ipari kommunikáció és számos egyéb területen. 1.2.1.
Az RBHH hatvani üzeme
A hatvani üzemet 1998-ban alapították és napjainkra az autó-elektronikai gyártás egyik legnagyobb központjává vált. Jelenleg négy csarnokban folyik a gyártás és a gyárban egyszerre közel 1800 ember dolgozik. A f® termékek: vezérl® elektronikák, ABS, automataváltó-vezérl®, sziréna, m¶szerfal, légzsák-vezérl®, stb. A hatvani Bosch-ban gyártott termékeket a világ minden táján értékesítik és több mint 15 millió gépjárm¶be szerelték már be. Elektronikai gyártás folyamata
A hatvani üzemben f®ként elektronikai eszközök ( autó elektronika: ABS vezérl®, m¶szerfal, váltó ) gyártásával foglalkoznak. Az elektronikai eszközök gyártása során az egyes áramköri elemeket a megfelel® helyen helyezik el a panelen. Egy panel pedig több NYÁK3 -ot is tartalmazhat. A gyártás során a termék számos fázison megy keresztül és számos különböz® ellen®rzési pont van. A gyártás folyamatát röviden a következ® pontokba lehet összefoglalni: 1. Paszta nyomtatás 2. Felület szerelt elemek ( SM4 ) beültetése 3. Újraömlesztéses hegesztés 4. Furat szerelt ( TH5 ) elemek beültetése 5. Végs® ellen®rzések, min®ség ellen®rzés 6. Kész termék csomagolása A gyártás egyes lépései között számos különböz® ellen®rzést alkalmaznak. Ezek közül a jelent®sebbek: 3 4 5
Nyomtatott Áramköri Lap Surface Mounted Through Hole
3
• JTAG: A teszt során már a kész alkatrészt t¶k segítségével tesztelik.
A t¶k az alkatrész egyes pontjain feszültséget ad, más pontokon pedig mér. A mért értéknek az elvárt tartományba kell esnie.
• Funkcionális teszt: A teszt során már a kész alkatrészt egy berendezés
segítségével úgy tesztelik, mintha már a m¶köd® rendszerben lenne, és a bemeneti teszt adatokra a vár eredményt kell kapnia, ha ett®l eltér®t tapasztal akkor a termék selejtes.
• AXI6 : forrasztások ellen®rzésére lehet alkalmazni. • AOI: A pasztázás, a beültetés, és az újraömlesztéses forrasztás után
lehet alkalmazni.
1.3. AOI és AOI-ASC Az elektronikai gyártás során, viszonylag hamar alkalmazott ellen®rz® eszköz az AOI berendezés. Az AOI berendezést a pasztázás után, a beültetés után, valamint az újraümlesztéses hegesztés után szokták alkalmazni. Mivel az AOI a jelen technológiák mellett is igen lassú és gyakran a gyártás sz¶k keresztmetszetét adja ezért el®fordul, hogy csak forrasztás után vagy egyáltalán nem alkalmazzák. 1.3.1.
AOI
Az AOI berendezés egy számítógépet és egy vagy több kamerát tartalmaz, valamint a kamerát mozgató mechanikát. A számítógép vezérli a kamerát, vagy kamerákat és képeket készít. Az egyes képeket algoritmikus úton elemzi és a hibásnak vélt részeket megjeleníti a monitoron. Az operátor eldönti a kép alapján, hogy valós vagy pszeudo hibát jelzett a gép, szükség esetén nagyítóval megvizsgálja a jelzett területet. Az kamera egy fejben helyezkedik el, a fej a kamerát és a hozzá tartozó LED sort tartalmazza. A legjelent®sebb AOI berendezést gyártó cég a Viscom. A dolgozatban az üzemben használt Viscom gépeken végzett adatokat használtam fel. 1.3.2.
AOI-ASC
Az AOI-ASC lényeg, hogy mint minden mér® m¶szer az AOI berendezés is hitelesítést, ellen®rzést igényel. Az AOI-ASC egy olyan program, amit a gép bizonyos id®közönként lefuttat. A program az eredményét egy napló fájlba 6
Automated X-ray Inspection
4
adja meg, minden nap egy napló fájl keletkezik. Ez az állomány tartalmazza, az egyes mérések nevét, a kamerákat és a mért értékeket. Az egyes mérések hat különböz® ellen®rzést hajtanak végre, ezek közül a dolgozatban, csak a szürkeségi vizsgálat eredményeivel foglalkozom ( GVC7 ), a többi ellen®rzés eredménye vagy megfelelt vagy nem megfelelt lehet.
1.4. AOI-ASC Monitoring Nyári gyakorlatom során a fent említett napló fájlokat feldolgozó alkalmazás fejlesztés volt a feladatom. Ennek a munkának az elvégzése során merült fel az igény, az adatbányászati módszerek alkalmazására. Az AOI-ASC Monitoring egy olyan program rendszer melynek segítségével a gépekr®l a napló fájlokat össze lehet gy¶jteni, fel lehet tölteni egy adatbázisba és az adatbázisban tárolt adatokat meg lehet jeleníteni. A program f® célja, hogy gra kusan ábrázolja a mérési eredményeket az id® függvényében. Ezen felül képes arra, hogy táblázatos formában is megjelenítse az adatokat, valamint az egyes gépeken bekövetkezett gyelmeztetéseket is meg lehet tekinteni a segítségével. A GVC mérési eredmények megjelenítése során merült fel az ötlet, hogy a gra kon mellett az adatsor statisztikai jellemz®i is ki legyenek irtva. A statisztikai adatok után merült fel az ötlet, hogy a program el®rejelzéseket készítsen az egyes adatsorokhoz.
1.5. Hiba el®rejelzés A m¶szerek pontosságának ellen®rzése során, a mért értékeknek megadott intervallumba kell esnie. Az intervallumon belül a berendezés megfelel®en m¶ködik. Az intervallumon kívül es® méréseket hibának nevezzük. A dolgozat célja, az intervallumból kilép® értékek által keltett hibák el®re jelzése. A hibákat a kiinduló adatokból, a burkoló görbékb®l és az eltérés függvény értékeib®l számított regressziós egyenesek segítségével jósolja meg a program, ezeket a módszereket részletesen ismertetem a 2. fejezetben. Mivel a regressziós függvény lineáris ezért egyszer¶en meg lehet határozni a hibák bekövetkezésének id®pontját. Minden mérési beállításhoz az alábbi adatok tartoznak: • Errormin : Az az érték ami alatt ha mér az eszköz akkor hibát jelez és
leáll.
7
Gray Value Check
5
• W arningmin : Az az érték ami alatt ha mér az eszköz akkor hiba bej-
egyzés keletkezik.
• W arningmax : Az az érték ami felett ha mér az eszköz akkor hiba
bejegyzés keletkezik.
• Errormax : Az az érték ami felett ha mér az eszköz akkor hibát jelez
és leáll.
Egyszer¶ egyenlet rendezés segítségével megkaptam, hogy a regressziós egyenes az y értéket
y−b m helyen veszi fel. Fontos kikötés hogy n 6= 0, különben nullával való osztás is el®fordulhat. Ha n = 0 akkor az x értékét végtelennek tekinthetjük. Ennek segítségével könnyen meg lehet határozni, azokat az x értékeket x=
ahol regressziós egyenes gyelmeztetést vagy hibát generálna. Az egyes kamerák mérési eredményeire külön-külön végre hajtja az elemzést a program, ezeket táblázatos formában írja ki. A kiírt eredmények közül, csak a jöv®re vonatkozó adatokat írja ki, a múltbéli adatok nem érdekesek a felhasználók szempontjából. A jöv®re vonatkozó adatok közül célszer¶ megkeresni a legkisebbet, a legnagyobbat.
6
2. fejezet
Prognózis el®állítási módszerei A regresszió analízis egy olyan statisztikai folyamat amelynek során az adathalmaz ismeretében keresünk az adatsorhoz legjobban illeszked® regressziós függvényt. A regresszió számítás segítségével két valószín¶ségi változó közötti kapcsolatot lehet meghatározni. A változók közül az egyiket magyarázandó, a többit magyarázó változónak nevezzük. A regresszió számítás a magyarázó függvény szempontjából számos különböz® lehet. A legegyszer¶bb regresszió a lineáris regresszió. A regressziós görbék halmazából a különböz® szempontok alapján lehet kiválasztani az optimálisat. Az optimális regressziós függvény meghatározásához a legelterjedtebb eljárás a legkisebb négyzetek módszere.
2.1. Lineáris regresszió A lineáris regresszió esetén a magyarázandó y változót a magyarázó x változók segítségével az f (x1 , x2 , . . . , xn ) = yˆ = β0 +
n X
(βi xi )
i=1
egyenlet segítségével keressük. A probléma megoldása során csak egyváltozós lineáris regressziót alkalmaztam. Ebben az esetben az alábbi képletet kaptam f (x) = yˆ = mx + b
A regressziós egyenes meghatározása során m és b értékeit úgy válasszuk meg, hogy a regressziós függvény és az y változó eltérése minimális legyen. Az m és b paraméterek meghatározására számos módszer létezik. A legismertebb ilyen módszer a legkisebb négyzetek módszere. 7
2.1.1.
A legkisebb négyzetek módszere
A módszer bevezeti a D = (y − yˆ)2 függvényt. A módszer célja, hogy az eredeti y és a kapott yˆ értékek különbségeinek a négyzetösszegét minimalizálja. A módszer segítségével meg lehet határozni az optimális m és b paramétereket. A paraméterek meghatározásához a D(m, b) függvényt minimalizálni kell. A minimalizálás eredménye az optimális m és b érték, ahol az y és az yˆ eltéréseinek négyzetösszege minimális. D(m, b) =
|y| X
2
(yi − yˆi ) =
i=0
|y| X
(yi − mxi − b)2 → min
i=0
A legjobban illeszked® függvény meghatározásához tehát egy kétváltozós függvényt minimalizálni. A minimalizálás lineáris regresszió esetén az alábbi eredményt adja: P m=
(xi − x)(yi − y) P (xi − x)2
és b = y − mx
Ennek ismeretében könnyen meg lehet határozni a regressziós egyenest. Az egyenes meghatározására az alábbi algoritmus írtam. function linear_regresion($X,$Y){ $avgX = avg($X); $avgY = avg($Y); $szamlalo = 0; $nevezo = 0; for($i = 0; $i < count($X); $i++){ $szamlalo += ($X[$i]-$avgX)*($Y[$i]-$avgY); $nevezo += pow($X[$i]-$avgX,2); } if($nevezo != 0){ $m = $szamlalo/$nevezo; } else{ $m = 0; } $b = $avgY - ($m*$avgX);
8
$result = array(); for($i = 0; $i < count($X); $i++){ $result[$i] = $m*$X[$i]+$b; } return $result; } 2.1.2.
A lineáris regresszió alkalmazása
A regressziós egyenes, valamilyen x értéknél át fogja lépni megadott y értéket, ilyenkor hibát jelez a gép. A 1.5 részben ismertetett módon határozom, meg a hibák bekövetkezési idejét. Így viszonylag egyszer¶en meg lehet határozni a hibák bekövetkezésének idejét. Ennek a megoldásnak el®nye, hogy egyszer¶, de pontatlan mert az adatsornak van valamilyen mérték¶ szórása. Ezért az egyenes helyett egy sávot határozok meg. A sávot a szórás alapján adom meg, a sáv a sorra nézve a sor addigi értékeinek szórásával tér el a regressziós adott pontjától. Ezt az alkalmazási lehet®séget a Scilab segítségével mutatom be. A Scilab-bal generáltam egy 100 elem¶ vektort melynek értékei a [47, 53] intervallumból való egész számok közül kerültek ki (y = round(rand(1,100)*6+47). A vektorhoz létre hoztam az x tengely értékeit is (x = 1:100). A generált adatsorhoz kiszámítottam a regressziós egyenes együtthatóit a regress függvény használatával(coefs = regress(x,y)). A regress függvény az y tengely metszési pontját (coefs(1)) és a meredekséget (coefs(2)) adja vissza. Ezek ismeretében meghatároztam az illeszked® egyenest (line = coefs(2)*x + coefs(1)). Az adatsor ismeretében meg tudtam határozni egy olyan vektort ami az adatsor addigi részének a szórásával egyenl®. Erre az alábbi kódrészletet használtam. for i = (2:1:100) v(i) = variance(y(1:i)); end
Az így kapott szórás segítségével meghatároztam a fels® és az alsó burkoló görbéket amelyek a regressziós egyenest®l a szórással térnek el. Ezen felül meghatároztam azokat a görbéket is amelyek a szórás kétszeresével térnek el. burkoloU = v + line'; burkoloL = line' - v;
9
burkoloU2 = line' + 2*v; burkoloL2 = line' - 2*v;
Az így kapott vektorokat a plot függvény segítségével megjelenítettem. A kapott gra kon eredménye a 2.1 ábrán látható, ahol a kék görbe a generált adatokat, a piros a regressziós egyenest, a zöld görbék az alsó és fels® sávot, ami a szórásból adódik, a fekete görbék pedig a szórás kétszeresével kapott sávot jelölik.
2.1. ábra. A Scilab által kapott regressziós egyenes, és sáv gra konja
2.1.3.
A lineáris regresszió problémája
A lineáris regresszió könnyen és egyszer¶en alkalmazható a problémára. A képlet alapján egyszer¶en meg lehet határozni a regressziós egyenest, aminek 10
ismeretében, meg lehet adni, hogy várhatóan mikor fog hibázni a gép. A lineáris regresszió gyenge pontja, hogy érzékeny a széls®séges ( outlier ) értékekre. Az outlier adatok hatása a regressziós függvényre annál nagyobb minél kisebb mintát veszünk, azaz hosszú adatsor esetén az outlier adatok hatása kevésbé érvényesül. Azaz egy mérési hiba, nagy mértékben befolyásolni tudja a regressziós egyenest. Ennek következtében az el®rejelzés pontatlan lesz. Scilab példa
Ezt a problémát a Scilab segítségével mutatom be[5]. A SciLab regress(x,y) függvénye vissza adja az m és a b értéket. A teszteléshez teszt adatokat generáltam a Scilab segítségével. x = 1:100; y = round(rand(100,1)*6-3)+50;
Az így kapott adathalmazra illesztettem regressziós egyenest. Majd az egyik értéket (50) növeltem rendre 5,25,50,75 értékkel. Az így kapott eredményeket az alábbi táblázat foglalja magába. x 0 5 25 50 75 m 0, 0054845 0, 0054545 0, 0053345 0, 0051845 0, 0050345 b 49, 70303 49, 754545 49, 960606 50, 218182 50, 475758 2.1. táblázat. A Scilab eredmények táblázata Látható, hogy az outlier adatok, jelent®s változást eredményezhetnek az optimális paraméter értékekben. A 2.1 táblázatban foglalt adatok alapján készítettem gra konokat. A gra konok eredményét a
Megoldási javaslat
A probléma megoldására a mérési értékekhez burkoló görbéket fogok bevezetni. A fels® és alsó burkoló görbére külön meghatározom a regressziós egyenest, és ez alapján csinálom az el®rejelzést. Célszer¶ lehet az els® és a fels® burkoló görbe által meghatározott görbéket átlagolva egy új regressziós egyenest meghatározni. Az új regressziós egyenest ebben az esetben az alábbi. ff (x) = mf x + bf
11
2.2. ábra. A regressziós görbe outlier adatok esetén, ahol 1. gra kon az eredeti adatsor 2. gra kon az 5-tel való módosítás eredménye 3. gra kon a 25-tel való módosítás eredménye 4. gra kon az 50-nel való módosítás eredménye 5. gra kon a 75-tel való módosítás eredménye
12
fa (x) = ma x + ba mf + ma ff (x) + fa (x) bf + ba 1 = (mf + ma )x + (bf + ba ) = x+ 2 2 2 2 Az így kapott fe regressziós egyenest®l jobb illeszkedést várok el mint az
fe (x) =
el®z®ekt®l.
2.2. Burkoló görbék A feladat szempontjából fontos, hogy mi módon de niáljuk az adatsorhoz tartozó burkoló görbéket. A feladathoz különböz® burkoló görbéket lehet de niálni. A feladat megoldása során összesen nyolc fajta burkoló görbét de niáltam. Ezeknek a burkoló görbéknek egy része csak annyiban tér el egymástól, hogy alsó vagy fels® burkoló görbe. Az algoritmusokat az alábbi négy csoportba osztottam: 1. Lépcs®s 2. Lépcs®s Lineáris 3. Maximum Kiválasztásos 4. Maximum Kiválasztásos Lineáris Ezeket a burkoló görbéket két csoportba oszthatjuk. Egyrészt lehet lépcs®s vagy maximum kiválasztásos, másrészt az értékeket vagy tartja, vagy lineárisan növeli. A következ®kben részletesen bemutatom ezeket az algoritmusokat. 2.2.1.
Lépcs®s
Ez a legegyszer¶bb algoritmus. A bemen® tömbb®l úgy képet egy új tömböt, hogy sorban végig olvassa az elemeit és ha az új érték nagyobb mint az el®z® akkor azt írja ki, különben az el®z® értéket tartja. Az alábbi kód az fels® burkoló görbét határozza meg. Az alsó burkoló görbét úgy kapjuk meg, hogy a 12) sorban a relációs jelet megfordítjuk. 1) 2) 3) 4) 5)
function lepcsos($input){ $result = array(); $result[0] = $input[0]; $last = $input[0]; for($i=0; $i
13
6) 7) 8) 9) 10) 11) 12)
if($last < $input[$i]){ $last = $input[$i]; } $result[$i] = $last;
}
} return $result;
Az algoritmussal készített burkoló görbék az alábbi ábrán láthatóak.
2.3. ábra. A lepcsos algoritmus eredménye
El®nye
Az algoritmus el®nye, hogy egyszer¶ és gyors. Az algoritmus csak egyszer olvassa végig a tömb elemeit és csak egy segéd változót használ. Hátránya
Az algoritmus hátránya, hogy ha a maximum a sorban el®l áll, akkor torzítani fogja az értékeket. Túlságosan eltér a szigorúan monoton csökken® sorozatok esetén, a kiinduló görbét®l. Ugyanez igaz az alsó burkoló görbe esetén szigorú monoton növekv® sorozatokra. A módszer hátránya, hogy sok törött vonalból állhat. Ez megnehezíti a görbe értelmezését, és a regressziós függvényt is befolyásolhatja. Célszer¶ ezért egy olyan algoritmust bevezetni ami az egyes értékek közötti lineáris átmenetet is megenged. Ez az algoritmus a lepcsosLinearis algoritmus.
14
2.2.2.
Lépcs®s Lineáris
Ez az algoritmus az el®z® algoritmus módosítása. Az algoritmus, két váltás, lépés között lineáris átmenetet valósít meg. Az algoritmussal kapott burkoló görbék láthatóak a 2.4 ábrán. El®nye
Az így kapott görbe, ez el®z® megoldáshoz képest sokkal szemléletesebb. A folytonos átmenetnek köszönhet®en a regressziós egyenes meredekségét pontosabban meg lehet határozni. Hátránya
Továbbra is gondot jelent a szigorúan monoton növekv® és csökken® sorozatok. Ez látható a 2.4 ábra jobb oldali gra konján, ahol az alsó burkoló görbe konstans értéket vesz fel a növekv® szakaszon. A görbe azon a szakaszon rosszul illeszkedik az kiinduló görbére. Ezt a problémát el lehetne kerülni egy másodfokú burkoló görbe alkalmazásával.
2.4. ábra. A lepcsosLinearis algoritmus eredménye
2.2.3.
Maximum Kiválasztásos
A maximumKivalasztas algoritmus egy másodfokú függvényhez hasonló görbét illeszt a kiinduló görbére. Az algoritmus alapelve, hogy megkeresi a legnagyobb értéket és annak a pozíciója mentén két részre bontja a kapott tömböt. Az így kapott két tömbre meghívja a lepcsos algoritmust. Így 15
a két tömb egyike egy monoton növekv® (csökken®) a másik egy monoton csökken® (növekv®) sorozatot alkot majd. Ezeket a tömbök összef¶zve a burkoló görbét adják. Az algoritmust az alábbi módon adtam meg, eredménye a 2.5 ábrán látható. El®nye
Az algoritmus el®nye, hogy az outlier értékekre kevésbé lesz érzékeny. További el®nye, hogy a maximum érték, nem rontja el az egész burkoló görbét, csak lokálisan érvényes. Ez így kapott görbét®l pontosabb becslést várok, mint az el®z®ekt®l. Hátránya
Az algoritmus hátránya, hogy minden pont között lépcs®s átmenetet valósít meg. Ezen felül rosszul illeszkedik, a periodikus függvényekre.
2.5. ábra. A maximumKivalasztas algoritmus eredménye
2.2.4.
Maximum Kiválasztásos Lineáris
Ez az algoritmus az el®z® algoritmus módosítása úgy, hogy az egyek rész burkoló görbék lineáris átmenetet valósítsanak meg. Az algoritmus a széls® érték megkeresése után a két tömbre a lepcsosLinearis függvényeket hívja meg. Az így kapott burkoló görbe a 2.6 ábrán látható.
16
El®nye
Ennek a görbének az el®z® algoritmus által adott görbéhez képest az az el®nye, hogy jobban illeszkedik a görbe. A lineáris átmenetnek köszönhet®en kevesebb az eltérés, ez f®ként a jobb oldali ábrákon látható. Hátránya
Az algoritmus hátránya, hogy továbbra sem ad jó közelítést a periodikus függvényekre.
2.6. ábra. A MaximumKivalasztasLinearis algoritmus eredménye
2.3. Dierencia függvény A burkoló görbék mellett egy másik megoldásként az adatok transzformációja is felmerült. Ebben az esetben a kiinduló adatokból minden lépésben kivonjuk az ®t megel®z® értékét. Így egy olyan adatsorhoz jutunk, ahol az egyes értékek, az el®z® értékt®l való el®jeles eltérés. Ezt a függvényt az alábbi kód valósítja meg. 1) 2) 3) 4) 5) 6) 7) 8)
function differences_cruve($arr){ $result = array(); if((!is_array($arr))||(count($arr) == 0)){ return $result; } $arr = convertKeys($arr); $result[0] = 0; for($i = 1; $i < count($arr); $i++){
17
9) $result[$i] = $arr[$i]-$arr[$i-1]; 10) } 11) return $result; 12) }
Az így kapott adatsorra szintén lineáris függvényt illesztek, és így kapott regressziós görbe alapján, meg lehet mondani, hogy milyen irányba fog elromlani a gép. Ennek az el®nye, az hogy bizonyos periodikus sorokra nulla meredekség¶ egyenest ad.
2.4. Markov-modell alkalmazása A Markov-modellt a mesterséges intelligencia területén számos helyen használják[2][4], f®ként a beszéd felismerés[3] és szövegbányászat területén. A Markov modell, azt állítja hogy a következ® állapot csak a jelenbeli állapottól függ. Azaz a múltbéli állapotok nincsennek hatással a jöv®beli állapotokra. Formálisan megfogalmazva, adott az S állapotok halmaza és t = 0, 1, 2, . . . . Azt mondjuk, hogy az η valószín¶ségi változó Markov láncot alkot ha P (St+1 |St ) = P (St+1 |St , St−1 , . . . , S0 )
Ebb®l kiindulva meg lehet határozni, hogy egy adott állapotból a rá következ® id®pillanatban mely állapotokba mehet át a rendszer. Ezt egy állapot átmeneti gráal lehet szemléltetni, ahol a csomópontok az egyes állapotok, az irányított élek a lehetséges állapot átmenetek, az élek súlya pedig az állapot átmenet valószín¶sége. Egy csomópontból kiinduló élek súlyainak összege 1, azaz minden lépésben történik állapot átmenet. A gráfot mátrixos formában is fel lehet írni, ilyenkor az állapot átviteli mátrixát kapjuk. Azt mondjuk legyen T |S|×|S| = {pij } átviteli mátrix, ahol pij = P (Si |Sj ). 2.4.1.
Az
n-ed
rend¶ Markov modell
Az el®bb ismertettem az els® rend¶ Markov modellt[4]. Ennek a mintájára de niálható az n-ed rend¶ Markov modell, ahol a St+1 nem csak St -t®l hanem St−1 , . . . , St−n+1 állapotoktól is függ. Ebben az esetben az átviteli mérete |S|n + 1. Az n-ed rend¶ Markov modell alkalmazásakor az n hosszúságú sorozatokat vizsgáljuk az adatsorban. Az n hosszúságú sorra számolja ki a következ® elem bekövetkezési valószín¶ségét. Látható, hogy az n-ed rend¶ Markov modell pontosabb becslést ad, de költségesebb mind a tárolása, mind a kezelése. 18
2.5. Minta illesztés A minta illesztés során megvizsgáljuk az utolsó n karaktert és azt vizsgáljuk az adatsorban, hogy van e benne olyan n-es sorozat ami megegyezik, vagy az eltérésük (távolságuk) kicsi, akkor az alapján lehet jósolni a következ® mérési adatokat. A minta illesztéshez a távolság függvényt az alábbi módon de niáltam. n ∆(xvege , xminta ) =
X
|xvege − xminta |
i=0
A távolság függvény ismeretében meg könnyen meg lehet határozni, hogy az adatsornak mely részei milyen jól illeszkednek az adatsor utolsó n elemére. A minta illesztés algoritmus viszonylag egyszer¶, az adatsor végér®l visszafele megnézi az összes n hosszúságú sorozatot és meghatározza az eltérést. function patternMatching_getDistances($arr,$n){ $result = array(); for($i = 0; $i < count($arr)-$n; $i++){ $result[$i] = 0; for($j = 0; $j < $n; $j++){ $result[$i] += abs($arr[$i+$j] - $arr[count($arr)-$n+$j]); } } return $result; }
A távolságok segítségével ki lehet választani, hogy mely elem következhet a legnagyobb valószín¶séggel. Ehhez meg kell határozni, hogy melyik részre illeszkedik a legjobban a mintánk. Az illeszkedés jóságának meghatározásakor gyelembe kell venni a minta hosszát (n), a találat és a minta közötti távolságot az adatsorban, valamint a találat és a minta távolságát. A minta hosszával (n) egyenes arányban n® a jósággal, mivel minél hosszabb sort illesztünk annál pontosabb lesz az el®rejelzés. A távolság és az eltérés pedig fordított arányban van a találat jóságával. Ezek a feltételek alapján a jóságát az alábbi képlettel számoltam. F (xminta , xtalat ) =
n (poz(xminta ) − poz(xtalalat )) + (∆(xminta , xtalalat ))
Így pontos illesztés esetén ( ∆(xminta , xtalalat ) = 0 ) a jóság függvény csak a minta és a találat távolságától függ. F (xminta , xtalat ) =
n (poz(xminta ) − poz(xtalalat ))
19
Így a legnagyobb jóság értéket a legközelebbi minta legjobban illeszked® minta adja. A régebbi pontos illesztések bár jobban illeszkednek, mégis kisebb lesz a jóság értékük. 2.5.1.
Minta illesztés súlyozással
A minta illesztés során a minta és a találat távolság és a pozíciók különbsége azonos súllyal rendelkeztek. Ennek a tesztelés során az lett az eredménye, hogy pár esett®l eltekintve, az újabb minta mindig jobban illeszkedett mint a régebbi. Ezért súlyok bevezetése mellett döntöttem. A súlyokat úgy vezettem be, hogy az összegük 1-et adjon ki, azaz WP oz = 1 − W∆ . Az így kapott jóság függvény pedig. F (xminta , xtalat ) =
n WP oz (poz(xminta ) − poz(xtalalat )) + W∆ (∆(xminta , xtalalat ))
20
3. fejezet
Eredmények A dolgozat ezen részében a dolgozat elkészítése közben elért eredményeket foglalom össze. Ismertetem az egyes módszerek el®nyeit és hátrányait. Végül röviden összefoglalom az elért eredményeket és levonom a következtetéseket.
3.1. A kialakított rendszer A rendszer kialakítása a nyári gyakorlatom feladata volt. A gyakorlat során kialakítottam a kiinduló rendszert, a jóslást megvalósító függvényeket erre a rendszerre alkalmaztam. A rendszert PHP nyelven kellett implementálnom, adatbázisnak pedig MySQL adatbázist használtam. A PHP nyelv jelent®sen meghatározta, hogy a további funkciókat is PHPban kell implementálnom. Az alap funkciókat támogatta a PHP és számos kiegészít® függvény könyvtárat találtam hozzá az Interneten. A kiegészít® könyvtárak közül a pChart könyvtárt használtam a gra konok elkészítéséhez. A rendszer az eredményeket egy egyszer¶ weboldalon jeleníti meg, így egyszer¶en elérhet® az összes felhasználó számára a hálózaton belül. A rendszer kimenete a 3.1 és a 3.2 ábrákon látható.
Sajnos a PHP viszonylag kevés lehet®séget nyújtott a statisztikai függvények terén. Az egyszer¶bb függvényeket támogatta ( átlag, szórás, stb.), de bizonyos függvényeket ( ferdeség, laposság, kovariancia, stb.) már nem voltak implementálva. Ezek a függvények az elemzés szempontjából fontosak voltak. A 3.2 ábrán látható táblázatban szerepelnek ezek a statisztikai adatok is. Ezért saját függvénykönyvtár implementálása mellett döntöttem. 21
3.1. ábra. Az AOI-ASC Monitoring kimenete
3.2. ábra. Az AOI-ASC Monitoring kimenete
3.2. Saját PHP statisztikai függvénykönyvtár A rendszer implementálása során számos statisztikai függvénykönyvtárt[6][7] megnéztem, de sajnos egyik sem nyújtotta a megfelel® funkciókat. A saját függvénykönyvtár implementálása során részletesen dokumentáltam az egyes függvényeket. Az elkészített függvénykönyvtár így jól de niált és kell®en b®séges lett a feladat megoldásához. A könyvtár az alábbi függvényeket tartalmazza: • Átlag • Átlagtól való átlagos eltérés • Szórás
22
• Terjedelem • Ferdeség • Laposság • Kovariancia • Korreláció
A felsorolt statisztikai függvényeket implementáltam és a MatLab-bal ellen®riztem. A ferdeség és a laposság függvények kivételével mind helyes volt. A ferdeség és laposság függvények csak közelít® értéket adnak. A statisztikai elemzés mellett a lineáris regressziós függvényt is implementáltam. A regressziós függvény implementálása után a de niált burkoló görbéket meghatározó függvényeket valósítottam meg.
3.3. Burkoló görbék vizsgálata A burkoló függvényeket a 2.2 részben mutattam be. A burkoló görbéket el® állító algoritmust a regression.php állományban valósítottam meg. Mind a négy fajta burkoló görbéhez két-két függvény tartozik ( alsó és fels® burkoló görbe ). A burkoló görbék meghatározása után meghatároztam a burkológörbékhez húzható regressziós egyeneseket. A regressziós egyenesek segítségével a 1.5 részben leírtak alapján határoztam meg a kitérések id®pontját. A táblázatban bal oldat az egyes kamerák kódja látható (#0,#1,#2,#3). A táblázat fejlécében pedig az egyes burkoló görbék nevei: • Normal - Az adatsor • lepcsosU - A lepcsosalgoritmus által generált fels® burkoló görbe. • lepcsosL - A lepcsosalgoritmus által generált alsó burkoló görbe. • lepcsosLinearisU - A lepcsosLinearisalgoritmus által generált fels®
burkoló görbe.
• lepcsosLinearisL - A lepcsosLinearisalgoritmus által generált alsó
burkoló görbe.
• MaximumU - A maximumKivalasztasalgoritmus által generált fels®
burkoló görbe.
23
• MaximumL - A maximumKivalasztasalgoritmus által generált alsó burkoló
görbe.
• MaximumLinearisU - A maximumKivalasztasLinearisalgoritmus ál-
tal generált fels® burkoló görbe.
• MaximumLinearisL - A maximumKivalasztasLinearisalgoritmus által
generált alsó burkoló görbe.
3.3. ábra. Az el®rejelzések táblázata
A táblázat celláiban két féle adat lehetséges. • N/A - Nem lehet meghatározni az eltérés idejét, ennek oka az lehet,
hogy a regressziós egyenes meredeksége zérus. Az ideális táblázat csak ilyen értékeket tartalmazna, mert az azt jelenti, hogy a gép a jelen adatok szerint soha nem fog hibát jelezni.
• szint => dátum - Megadja a regressziós egyenes által legközelebb
átlépett szintet, majd a "=>" jellel elválasztva az átlépés idejét. Ez az id®pont a becslése annak, hogy a gép mikor fog hibát jelezni.
3.3.1.
Becslési táblázat kiértékelése
A táblázatból könnyen kiolvasható az egyes gépek mérésénél a kamerák meghibásodásának lehetséges id®pontja. A 3.3 ábrán szerepl® táblázatot 2010.november. 03-04 közötti mérések adataiból kaptam. A becslés szerint a gép ezzel a beállítással az év végéig nagy valószín¶séggel jól fog m¶ködni. Továbbá azt is ki lehet olvasni a kiinduló adatsorból, hogy a #1-es kamera más irányba fog eltérni mint a többi kamera ezzel a beállítással. Elvileg 24
a hiba jelzésének id®pontja 2011. augusztusában várható. A korrelációs adatokból kiolvasható, hogy a többi kamerával csak nagyon csekély mértékben korrelál ( rendre: 0, 31; 0, 25; 0, 25. Ez alátámasztja a táblázatból levont következtetés helyességét. Természetesen az el®re jelzés nem feltétlen pontos, mert addig az id®pontig számos módosítás történhet a berendezéssel ( karbantartás, kalibrálás, hiba szintek módosítása, stb.).
3.4. Továbbfejlesztési javaslat Az elkészült rendszer jelenleg nem használja fel a Markov modell nyújtotta lehet®ségeket, valamint a minta illesztést. A rendszerbe implementálni kell majd ezeket a funkciókat is. A rendszer ezen felül számos apróbb esztétikai hibával terhelt. Az el®re jelz® funkciók csak magyar nyelven m¶ködnek megfelel®en. Más nyelveken is a magyar feliratot írja ki a rendszer. Mivel a rendszer multinacionális környezetben kerül felhasználásra, ezért ezeket a funkciókat nagyon sürg®sen implementálni kell. A hibák el®re jelzésénél, be lehetne iktatni egy olyan funkciót ami más színnel jelöli a közeljöv®ben bekövetkez® hibákat. Például pirossal ami egy héten belül bekövetkezik, sárgával ami egy hónapon belül és nem jelölné külön az összes többit. Így a táblázat sokkal könnyebben átlátható lenne. A rendszer a GVC mérések eredményeinek kiértékelésén kívül az egyes gépek meghibásodásának a gyelésére is alkalmas. A becslések jelenleg csak a GVC adatokra m¶ködnek, ezért a közeljöv®ben a gyelmeztetések monitorozásánál is be lehetne vezetni, így az egyes gépekhez egy összesít® értékeket kaphatunk. A rendszert fontos volt a gyakorlat során gyorsan elkészíteni, ezért a forráskód számos helyen elavult, vagy már nem használt funkciókat is tartalmaz. Ezen felül az egyes függvények implementálásakor a gyorsaság volt a f® szempont, ezért a függvények jelent®s részét lehet még optimalizálni. Ezeket a kód refactoring-gal lehetne javítani. Ez csökkenthetné a várakozási id®ket.
25
4. fejezet
Összefoglalás A dolgozat ezen részében röviden összefoglalom az elért eredményeket. Az eredményekb®l levonom a következtetéseimet. A dolgozatban ismertettem a RBHH hatvani üzemében alkalmazott AOIASC eljárást. Röviden bemutattam az ellen®rz® mérések adatait feldolgozó programot és az elemzési funkcióit. A dolgozat f® célja a mérési adatokon végrehajtható prognózis el®állítási eljárások vizsgálata és implementálása volt. A dolgozat 2. fejezetében részletesen ismertettem a felhasznált módszerek elméleti hátterét. Megvizsgáltam az alkalmazási és felhasználási lehet®ségeket. Nagy hangsúlyt fektettem a lineáris regresszió alkalmazására. Ismertettem a lineáris regresszió elméleti hátterét, és a regressziós egyenes el®állítására szolgáló módszereket. Ismertettem az els®fokú lineáris regresszió problémáit, különös tekintettel az outlier adatokra. Az adatok mellé de niáltam négy különböz® burkoló görbét, melyekre szintén meghatároztam a regressziós egyeneseket. A bevezetett burkoló görbéket részletesen bemutattam, elemeztem, ismertettem a generálásukhoz szükséges algoritmusokat. A burkoló görbék mellett ismertettem a regressziós egyeneshez tartozó szórásból adódó sávot. A dolgozat utolsó felében ismertettem az implementált algoritmusokat. Bemutattam az AOI-ASC Monitoring rendszert. A rendszerhez implementált saját statisztikai függvénykönyvtárat, összehasonlítva más PHP-s statisztikai függvénykönyvtárakkal. Majd ismertettem a kiinduló adatokból és a hozzá burkoló görbékb®l kapott kapott el®rejelzéseket összefoglaló táblázatot. A dolgozatban elkészített rendszer jelent®sen csökkenti a felhasználók kötelezettségeit. Az automatikus gyelés segítségével könnyen nyomon lehet követni az egyes gépekhez tartozó beállításokkal mért értékeket, ez nagy mértékben megkönnyíti a munkát. Korábban a felhasználók csak a kimen® 26
napló fájlt tudták manuálisan átvizsgálni, ami igen id®igényes volt és számos összefüggés felderítésére nem volt lehet®ség így.
27
Irodalomjegyzék [1] Dr. Bodon Ferenc: Adatbányászati Algoritmusok [2] Major Klára: Markov modellek alkalmazása a társadalomtudományi kutatásban [3] Vázsonyi Miklós: Nyelvdetektáció rejtett Markov modell alkalmazásával [4] http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html [5] Modelling of data with Scilab http://www.woldata.se/modellingOfData.pdf [6] AJ PHP Statistical library - http://www.ajdesigner.com/php_code_statistics/mean.php [7] www.php.net statisztikia könyvtára
28
Tartalomjegyzék 1. Bevezetés
1.1. A dolgozat célja . . . . . . . . . . 1.2. A RBHH bemutatása . . . . . . . 1.2.1. Az RBHH hatvani üzeme 1.3. AOI és AOI-ASC . . . . . . . . . 1.3.1. AOI . . . . . . . . . . . . 1.3.2. AOI-ASC . . . . . . . . . 1.4. AOI-ASC Monitoring . . . . . . . 1.5. Hiba el®rejelzés . . . . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
2.1. Lineáris regresszió . . . . . . . . . . . . 2.1.1. A legkisebb négyzetek módszere . 2.1.2. A lineáris regresszió alkalmazása 2.1.3. A lineáris regresszió problémája . 2.2. Burkoló görbék . . . . . . . . . . . . . . 2.2.1. Lépcs®s . . . . . . . . . . . . . . 2.2.2. Lépcs®s Lineáris . . . . . . . . . 2.2.3. Maximum Kiválasztásos . . . . . 2.2.4. Maximum Kiválasztásos Lineáris 2.3. Dierencia függvény . . . . . . . . . . . 2.4. Markov-modell alkalmazása . . . . . . . 2.4.1. Az n-ed rend¶ Markov modell . . 2.5. Minta illesztés . . . . . . . . . . . . . . . 2.5.1. Minta illesztés súlyozással . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
2. Prognózis el®állítási módszerei
3. Eredmények
. . . . . . . .
. . . . . . . .
. . . . . . . .
2
2 3 3 4 4 4 5 5
7
7 8 9 10 13 13 15 15 16 17 18 18 19 20 21
3.1. A kialakított rendszer . . . . . . . . . . . . . . . . . . . . . . 21 3.2. Saját PHP statisztikai függvénykönyvtár . . . . . . . . . . . . 22 29
3.3. Burkoló görbék vizsgálata . . . . . . . . . . . . . . . . . . . . 23 3.3.1. Becslési táblázat kiértékelése . . . . . . . . . . . . . . 24 3.4. Továbbfejlesztési javaslat . . . . . . . . . . . . . . . . . . . . . 25 4. Összefoglalás
26
30
