Adattarhazak, adatbanyaszati technologiak
Tartalom 1. Az adatbányászat, tudásfeltárás feladata, a tudásfeltárása folyamata, példákkal magyarázva.. ....... 4 1.1 Az adatbányászat ........................................................................................................................... 4 1.2 Tudásfeltárás feladata, folyamata ................................................................................................. 4 1.2.1 Mi nem adatbányászat? ......................................................................................................... 4 1.2.2 Miből áll a web-adatokon végzett tudásfeltárás? .................................................................. 5 1.2.3 Minden kibányászott minta érdekes? .................................................................................... 5 1.2.4 Próbáljuk mérni a tudás érdekességét → és csak érdekes tudást bányásszunk ki az adatokból ......................................................................................................................................................... 5 2. Az adattárházak építése, architektúrák, példákkal magyarázva. ........................................................ 6 2.1 Adattárházak építése..................................................................................................................... 6 2.1.1 Tervezési folyamat.................................................................................................................. 6 2.1.2 Az adattárház tervezési folyamatának tipikus lépései ........................................................... 7 2.1.3 Adattárház építő segédeszközök ............................................................................................ 7 2.2 Adattárház architektúrák .............................................................................................................. 8 3. Az adatkockák szerepe, műveletei, példákkal magyarázva. ................................................................ 9 3.1 Adatkockák szerepe ....................................................................................................................... 9 3.2 Adatkocka .................................................................................................................................... 10 3.3 Adatkockák műveletei ................................................................................................................. 11 4. Az asszociációs szabályok előállítása, példákkal magyarázva ........................................................... 14 4.1 Feladat leírása ............................................................................................................................. 14 4.2 Példa: ........................................................................................................................................... 14 4.3 Az apriori eljárás: ......................................................................................................................... 14 4.4 FP-Tree......................................................................................................................................... 16 5. Az osztályozás feladata, a döntési fák előállítása, példákkal magyarázva. ....................................... 17 5.1 Osztályozás feladata .................................................................................................................... 17 5.2 Döntési fa előállítása ................................................................................................................... 17 6. A klaszterezés feladata, két klaszterező algoritmus, példákkal magyarázva. ................................... 19 6.1 Klaszterezés feladata ................................................................................................................... 19 6.2 Két klaszterező algoritmus .......................................................................................................... 20 6.2.1 A k-közép klaszterezés .......................................................................................................... 20 6.2.2 Összevonó klaszterezési algoritmus ..................................................................................... 21 7. Szövegbányászati módszerek. ........................................................................................................... 25 2
7.1 Látens szemantikai indexelés ...................................................................................................... 25 7.2 Kulcsszó alapú asszociációs analízis (keyword based association analysis) ................................ 27 7.3 Szöveg klasszifikálása .................................................................................................................. 27 7.4 Dokumentumok klaszterezése .................................................................................................... 27 7.5 Vektortér modell ......................................................................................................................... 28 8. Entity resolution ................................................................................................................................ 30 8.1 Record Linkage model (1969) – Hogyan kötjük össze a halmazokat........................................... 30 8.2 Comparison vector – összehasonlítás mi alapján történjen ....................................................... 30 8.3 Duplicate Record Detection – mit kezdjünk a duplikátumokkal ................................................. 30 8.4 String matching / field similarity – mely mezők egyeznek meg? ................................................ 31 8.5 Generic Entity Resolution ............................................................................................................ 31 8.6 Relational Clustering ................................................................................................................... 32 8.7 Ügyfeles példa ............................................................................................................................. 32 8.8 További példák: ........................................................................................................................... 32 8.9 Trendek, nyitott kérdések ........................................................................................................... 33
3
1. Az adatbányászat, tudásfeltárás feladata, a tudásfeltárása folyamata, példákkal magyarázva.. forrás: http://people.inf.elte.hu/kiss/13dwhdm/01H.ppt
1.1 Az adatbányászat Miért kell adatbányászat? Adatrobbanás zajlik: terabájtokról áttérünk a petabájtokra. Nagy adatgyűjtemények keletkeznek és érhetők el. Nagy mennyiségű nyers adat keletkezik a következő területeken:
automatikus adatgyűjtő mérőeszközök, adatbázisrendszerek, Web, közösségi hálók, számítógépes ügyfélszolgálatok Üzleti élet: Web, e-kereskedelem, pénzügyi tranzakciók, tőzsde Tudomány: távérzékelő berendezések, bioinformatika, tudományos szimulációk Közösségi és mindennapos élet: Facebook, hírek, digitális kamerák, YouTube
Ellep bennünket a rengeteg adat, bár mi valójában inkább tudásra vágyunk! A szükség szüli az új technológiát: az adatbányászat a nagy mennyiségű adatok automatikus elemzése. 1950-ig csak elméleti tudomány. Az 1950-es évektől kezdve sok tudományág számítógépes részterületet kifejlesztett. 1990-től már rengeteg szimuláció és tudományos eszköz generál nagy mennyiségű feldolgozandó adatot. Manapság már több petabájtnyi adatot tudunk olcsón tárolni és kezelni. Az Internet és a Grid rendszerek révén ezeket az adathalmazokat könnyen el lehet érni. A tudományos információkezelési, információgyűjtési, szervezési, lekérdezési, megjelenítési feladatok száma az adatmennyiség arányában növekszik. (Minél több az adat, annál többféle feldolgozásra vagyunk kíváncsiak.) Az adatbányászat napjaink egyik fő kihívása!
1.2 Tudásfeltárás feladata, folyamata Az adatbányászat (tudás kinyerése az adatokból): érdekes (nem triviális, implicit, eddig nem ismert és potenciálisan hasznos) mintákat (azaz tudást) akarunk kinyerni a nagyon nagy adathalmazokból lehetőleg automatikusan, és minél hatékonyabban. 1.2.1 Mi nem adatbányászat?
Egyszerű keresések, lekérdezések végrehajtása (Deduktív) szakértői rendszerek
4
A tudásfeltárás folyamata 1.2.2 Miből áll a web-adatokon végzett tudásfeltárás?
Adattisztítás Több forrásból származó adatok integrációja Az adatokból adattárház építése Adatkockák készítése Az adatbányászathoz szükséges adatok kiválasztása Adatbányászat elvégzése Az eredményekből jelentések készítése, megjelenítése A talált minták, összefüggések (tudás) tárolása a tudásbázisban
1.2.3 Minden kibányászott minta érdekes?
Kimerítő kereséssel túl sok mintát kaphatunk Van, ami csak bizonyos helyre, időre, dimenzióra jellemző, vagyis nem elég általános Van, ami csak múló összefüggés, az aktuális adatokra véletlenül teljesül
1.2.4 Próbáljuk mérni a tudás érdekességét → és csak érdekes tudást bányásszunk ki az adatokból
milyen tudás kell: leíró vagy előrejelző milyen eseteket fed le, lehetőleg minél többet mennyire tipikus vagy újszerű a minta (esőben viszünk ernyőt: érdektelen, esőben levisszük a vízilovat sétálni: érdekes) mennyire pontos az összefüggés a lefedett esetekben mennyire időszerű (mindenki vízilovat tart otthon) 5
2. Az adattárházak építése, architektúrák, példákkal magyarázva. forrás: http://people.inf.elte.hu/kiss/13dwhdm/03H.ppt
Mi az adattárház? Sokféleképpen definiálják, nincs egyértelmű meghatározás. Olyan döntéstámogató adatbázis, amelyet a szervezet működéséhez szükséges adatbázisától elkülönítve üzemeltetnek. Egyesített, történeti (időtől függő) adatok elemzését, információ feldolgozását támogató platform. “Az adattárház olyan témaspecifikus, integrált, időfüggő, fizikailag is tárolt adatgyűjtemény, amely a menedzsment döntéshozó folyamataihoz szükséges lehet.”—W. H. Inmon Témaspecifikus: Nem a napi működéshez szükséges folyamatokkal, tranzakciós folyamatokkal foglalkozunk, hanem a modellezéssel, a döntéshozók számára hasznos adatelemzésekkel. Egy speciális témakörhöz szükséges adathalmaz egyszerű, tömör reprezentálása. Kihagyjuk azokat az adatokat, amelyek nem kellenek a döntéshozáshoz. Integráltság: Többféle, heterogén adatforrás adataiból készítjük el az adattárházat. Integrációs technikákat és adattisztítást kell alkalmaznunk. Időfüggés: Általában hosszabb időtartamra (akár évekre visszamenőleg) vizsgáljuk az adatokat. Az adattárház kulcsai (azonosítói) mindig tartalmaznak időpontot, explicit vagy implicit formában, a működési adatbázisban nincs mindig időpont megadva.
2.1 Adattárházak építése Négyféle szempont az adattárház tervezéséhez 1. Fentről-le az adattárházhoz szükséges lényeges információ kiválasztása (mire van és mire lehet majd szükség) 2. Adatforrás mit tárolunk a működési rendszereinkben 3. Adattárház milyen tény és dimenziótáblákat tárolunk az adattárházban 4. Üzlet a végfelhasználó milyen célra használhatja majd az adatokat 2.1.1 Tervezési folyamat
Fentről le, vagy lentről fel, vagy kombinálva:
Fentről le (Top-down): Gondosan, fokozatosan részletezve mindent megtervezünk (időigényes) Lentről fel (Bottom-up): Próbálgatunk, prototípusokat adunk (gyors)
6
Szoftvertervezési szempontból
Vízesés modell (Waterfall): strukturált, szisztematikus elemzés, mielőtt a következő lépést megtesszük Spirális modell (Spiral): gyorsan, egyre több funkcionalitást teszünk a készülő rendszerbe
2.1.2 Az adattárház tervezési folyamatának tipikus lépései
Határozzuk meg az üzleti folyamatokat, amelyekben modellezzünk például a rendeléseket, számlákat Határozzuk meg az üzleti folyamatok atomi adatszintjét Határozzuk meg a tényrekordokhoz tartozó dimenziókat Határozzuk meg a rekordokban szereplő mértékeket
2.1.3 Adattárház építő segédeszközök
Adatgyűjtéshez több, heterogén, akár külső adatforrásból összegyűjti, kiválasztja a szükséges adatokat
Adattisztításhoz adathibákat kijelzi, ha lehet ki is javítja
Adattranszformációhoz az örökölt adatbázisokból az adatokat az adattárház formátumára transzformálja
Betöltéshez rendez, összesít, egyesít, nézeteket készít, ellenőrzi az integritási feltételeket, indexeket készít, particionál
Frissítéshez időközönként az új adatokat, változásokat betölti az adattárházba
7
2.2 Adattárház architektúrák Három típusa van: 1. Vállalati adattárház (Enterprise warehouse) a teljes szervezet összes fontos információját tartalmazza, amely bármilyen témájú elemzéshez valaha is kellhet 2. Adatpiac (Data Mart) egy adott témához (például marketing) szükséges adatok gyűjteménye külön is megépíthetjük, de lehet része a vállalati adattárháznak is 3. Virtuális adattárház (Virtual warehouse) A működési adatbázisra építünk nézeteket Egyes összesítő nézeteket materializálunk
Adattárházak építésének diagramja
8
3. Az adatkockák szerepe, műveletei, példákkal magyarázva. forrás: http://people.inf.elte.hu/kiss/13dwhdm/03H.ppt
3.1 Adatkockák szerepe Az adattárház többdimenziós adatmodellt valósít meg, tipikusan adatkockákat használ. Egy adatkocka, mint például az eladások, esetén az adatokat több dimenzióban nézhetjük, modellezhetjük:
Dimenziótáblákat használunk: cikk(cikk_név, márka, típus), vagy idő(nap, hét, hónap, negyedév, év) A ténytábla tartalmazza az értékeket, mértékeket (például eladott_mennyiség_dollárban) és kulcsokat a megfelelő dimenziótáblákhoz, amely alapján a dimenzió részleteit tudjuk a tényekhez hozzákapcsolni
Az n-dimenziós (n-D) alapkockát alapkuboidnak (alaptéglának) hívjuk. Ez a legrészletezettebb nézete a tényeknek. A legfelső szintű 0-D kuboid a teljes összesítést tartalmazza, (függetlenül helytől, időtől, egyéb dimenzióktól). Ez az apex kuboid. A kuboidok hálóját hívjuk adatkockának.
Kuboidok hálója
9
3.2 Adatkocka Adattárházak modelljei: dimenziók és mértékek Csillagséma: Középen áll a ténytábla, ami dimenziótáblákkal van összekapcsolva.
Csillagséma Hópehelyséma: A csillagséma finomítása, a dimenziótáblákat dekomponáljuk normálformájú kisebb dimenziótáblákra.
Hópehely
10
Csillagkép vagy galaxisséma: Több ténytábla közös dimenziótáblákat használ.
Galaxisséma
3.3 Adatkockák műveletei 1. Felgörgetés - Roll up (drill-up): összesítjük (pl. összegezzük) az adatokat a hierarchián feljebb lépve vagy a dimenziót elhagyva
11
2. Lefúrás - Drill down (roll down): kirészletezünk adatokat (a felgörgetés fordítottja) alacsonyabb szintű összesítést veszünk, részletezzük az adatokat, vagy bevezetünk egy új dimenziót
3. Szeletelés és kockázás - Slice and dice: vetítés és kiválasztás
Szeletelés
12
4. Forgatás (pivotálás) - Pivot (rotate): elforgatjuk a kockát, vagy a vizualizációját, a 3D-t alkotó 2D-s síkszeletek sorozatát átrendezzük
5. Egyéb műveletek a. Keresztülfúrás - drill across: egynél több ténytáblában fúrunk le b. Átfúrás -drill through: a lefúrást SQL utasításokkal a kockában a legrészletezettebb adatokig, azaz az alap relációs táblákig folytatjuk
13
4. Az asszociációs szabályok előállítása, példákkal magyarázva forrás: http://people.inf.elte.hu/kiss/13dwhdm/05(1).ppt 49.dia
4.1 Feladat leírása Feladatunk az adathalmazban előforduló gyakori minták felderítése. Az ilyen eljárások használhatóak például vásárlói kosarak vizsgáltál, ahol az együtt gyakran megvásárolt termékeket keressük. Ez az adatok feldolgozásának szempontjából is érdekes, hiszen egy adathalmazhoz tartozó gyakori minták sokat elmondanak annak tulajdonságairól. Legyenek 𝑋 = {𝑥1 , … , 𝑥𝑘 } és 𝑌 = {𝑦1 , … , 𝑦𝑘 } „cikkek” halmaza. A feladat keresni olyan 𝑋 → 𝑌 szabályokat, melyek megfelelnek bizonyos support és confidence követelményeknek.
Support=S annak a valószínűsége, hogy egy kosár tartalmazza 𝑋 ∪ 𝑌-t Confidence=C feltételes valószínűsége annak, hogy ha egy kosár tartalmazza X-et akkor Y-t is
4.2 Példa:
n cikk esetén 2𝑛 darab részhalmazt kéne megvizsgálni, ami sok. Bemutatjuk az apriori eljárást ami downward closure tulajdonságot tételezi fel az adathalmazról. Ez alapján a gyakori kosarak részkosarai is gyakoriak. Tehát pl. ha sör és pelenka együtt gyakran előfordul a kosarakban, akkor sör is gyakran előfordul. Ebből kifolyólag az apriori alapötlete az, hogy ha egy X „cikk” halmaz nem gyakori, akkor már nem kell vizsgálni az olyan „cikk” halmazokat melyek tartalmazzák X-et. Ezt hívjuk apriori pruning principle-nek.
4.3 Az apriori eljárás: 1. Fussunk végig az adathalmazon és keressük meg a gyakori egy elemű részhalmazokat. (tehát a gyakori cikkeket) k:=1. 2. Generáljunk k+1 hosszú részhalmazokat a gyakori k hosszú részhalmazokból. k:=k+1 3. Nézzük meg hogy az előző pontban generált részhalmazok mennyire gyakoriak. Ha nem gyakoriak hagyjuk el őket. 4. Ha már egy generált részhalmaz sem gyakori, akkor leállunk, egyébként vissza a 2-es pontra.
14
Hogyan generáljunk minden körben lehetséges gyakori halmaz jelölteket?
Első lépés: self-joining az 𝐿𝑘 -ban. 𝐿𝑘 az eddigi gyakori k cikket tartalmazó halmazok! fontos , hogy ez rendezve van. ((lexikografikusan, a példánál érthetőbb)) Második lépés: pruning (vágás). Eltüntetjük azokat a generált halmazokat, melyek tartalmaznak olyan k méretű részhalmazt, ami nem szerepel 𝐿𝑘 -ban.
Példa:
Hogyan számoljuk ki a jelöltek Supportját? (05-16,17.old)
15
Általános problémák a gyakori minták keresésénél:
Az adathalmazon többször végig kell menni (erre megoldás a DIC (23.old)) Egy körben rengeteg jelölt generálódik (erre megoldás a DHP eljárás (21.old)) Support körönkénti kiszámolása költséges
4.4 FP-Tree A diákban szó van egy olyan eljárásról, ami FP-Tree-ket épít
16
5. Az osztályozás feladata, a döntési fák előállítása, példákkal magyarázva. forrás: http://people.inf.elte.hu/kiss/13dwhdm/06(1).ppt
5.1 Osztályozás feladata Klasszifikáláskor meg akarjuk jósolni, hogy az egyes rekordok milyen osztályba tartoznak. A modellt egy tanuló adathalmaz alapján állítjuk be, majd ezt tipikusan egy másik tesztelő adathalmazzal értékeljük ki. Az ilyen eljárások sok területen felhasználhatók, pl hiteligénylés kiértékelésére, előzetes orvosi diagnózis esetén, célzott marketing esetén. A modell konstrukciója. Modellt csak egy már kész, és pontos adathalmazon tudjuk megkonstruálni. Jellemzően a tanítóhalmaz rekordjainak egy oszlopában van a rekordhoz rendelt osztály. A modellt magát reprezentálhatjuk szabályok sorozatával, döntési fával, vagy valamilyen matematikai formulával. A modell alkalmazása. A kész modellt érdemes először egy (a tanuló adathalmaztól független) teszt adathalmazon vizsgálni. Persze a tesztadathalmaz rekordjainak osztályait is pontosan kell ismernünk az eredmény kiértékeléséhez. Ha elég pontos válaszokat ad a modell, akkor ráengedhetjük más adatokra is. Adat tisztítás: A tanító adathalmazon, célszerű tisztítást végezni a modell konstrukciója előtt. Ide tartozik az üres értékek kezelése, valamint a zajcsökkentés, a redundáns/irreleváns attribútumok törlése, valamint az egyes értékek normalizálása.
5.2 Döntési fa előállítása A fa konstrukciója: (felülről lefelé, rekurzív oszd meg és uralkodj)
Kezdetben a tanulóhalmaz minden értéke a gyökérben van. Minden lépésben az egyes csomópontokat kettéválasztjuk bizonyos attribútumok alapján. Az attribútum választás alapja általában valamilyen heurisztika vagy statisztikai mérték(az informacion gain lesz később) A fa építésével leállunk, ha az egyes csomópontokhoz tartozó rekordok már egy osztályba esnek, vagy ha már nincs attribútum, ami alapján vághatnánk, vagy nincs a csomóponthoz érték rendelve. (*Persze gondolom gyakorlatban már egy adott szint után, vagy egy minimális gain alatt leállunk). Végül megnézzük, hogy az egyes levelek milyen osztályhoz tartozó rekordokból tartalmaznak a legtöbbet ( és az lesz a levélhez tartozó osztály).
Attribútum választás information gain alapján:
Azzal az attribútummal vágunk, mellyel a legnagyobb az information gain Legyen pi annak a valószínűsége, hogy egy D rekordhalmazhoz tartozó rekord Ci osztályba m tartozik, és ezt becsüljük így: |Ci, D|/|D| Info ( D ) p i log2 (p i ) Ekkor a várható információ(entrópia): v |D | i 1 j Info A (D) I( D j ) Szükséges információ, hogy A attribútummal vágjunk D-t v részre: j1 | D | Nyert információ az A-alapján történt vágással:
Gain(A) Info(D) Info A (D)
17
Példa (azt keressük, hogy vesz-e pc-t): A példában a kor szerint vágunk, mert arra lesz a legnagyobb a gain.
Mi van ha A attr. folytonos? Keressük a legjobb vágási pontot. Rendezzük az A-ban előforduló értékeket növekvő sorrendben (*Gondolom a csomóban előforduló értékeket). A vágási pont tipikusan két a,b érték között lesz (a+b)/2. Azt a split-point-ot vegyük, mellyel elvágva az adathalmazt annak várható információja minimális lesz. 06-18.old
A Gain(A) érték használatával, az eljárás hajlamos azokat az attribútumokat előnyben részesíteni, melyeknek sok értéke van. Erre a C4.5 kínál megoldást, ami normalizálja a Gain-t. Vagyis legyen v
| Dj |
j1
|D|
SplitInfo A (D)
log2 (
| Dj | |D|
)
és így GainRatio(A)=Gain(A)/SplitInfo(A). Mit az előző esethez hasonlóan, azt az A-t választjuk melyre legnagyobb a GainRatio(A). Overfitting: a modell hajlamos túltanulni a tanuló adathalmazt. Sok zajra, kiugró értékre utalhat az, ha a fa túlzottan szerteágazik. Megoldás, ha csak egy adott jóság (gain) fölött bontjuk a csomópontokat, de ezt nehéz előre belőni. Másik ötlet, ha felépítjük a (túlságosan nagy) fát, és ezt lenyessük. Az ilyen „vágott” fák hatékonyságát célszerű nem a tanuló adathalmazon megmérni.
18
6. A klaszterezés feladata, két klaszterező algoritmus, példákkal magyarázva. forrás: http://people.inf.elte.hu/kiss/12dwhdm/07(1).ppt fordítások: http://people.inf.elte.hu/kiss/13dwhdm/8fej_klaszterezes_alapok.pdf http://people.inf.elte.hu/kiss/13dwhdm/9fej_klaszterezes_halado.pdf
6.1 Klaszterezés feladata Mi a klaszterezés? Objektumok halmazában keresünk olyan csoportokat, melynek tagjai egymáshoz hasonlóak, ugyanakkor más csoportokban lévő tagok különböznek Klaszterezés alkalmazásai: nagy adatállományok csökkentése, az adathalmaz jobb megértése, például a böngészésnél kapott kapcsolódó dokumentumok csoportjai, hasonló funkcionalitással bíró gének és fehérjék csoportjai, hasonló ármozgású részvények csoportjai. Hasonlóság metrikája: az objektumok attribútumaik közti hasonlóságra általában valamilyen d(i,j) metrikát adunk meg. Ezek különböző típusú változókra nagyon különbözhet (boolean,number,categorical). A klaszterek „jóságát” tipikusan máshogy mérjük, és egy ilyen mérték megfogalmazása nehéz. Az adatok típusa lehet:
Interval-valued variables: klaszterezés előtt az ilyen jó normalizálni/standardizálni (vagyis az egyes értékekből kivonjuk a mintaátlagot, majd ezt osztjuk a szórással (most nem a szórásnégyzet gyökével, hanem a mean absolute deviation-nel)). Ezekre sokféle távolságot ráhúzhatunk, pl Euklideszi távolság, MInkowski távolság, Manhattan távolság (07 prezi, 14. oldal) Binary variables: a változónak két állapota lehet. egy lehetséges távolság, ha a nem egyező változók számát elosztjuk az összes változó számával. Nominal values: előzőhöz hasonló, de 2-nél több állapota lehet. Egy lehetséges távolság, ha a nem egyező változók számát oszjuk az összesel. Ordinal value: lehet diszkrét vagy folytonos, de az értékekre van rendezés(rank). Az internal valued variables típushoz tartozó hasonlóságok használhatók, ha a változókat rank szerint a [0,1] intervallumba képezzük. Ratio scaled variable: nemlineáris skálán vett értékek, távolság az előzőhöz hasonlóan visszavezethető az interval-valued variables típusra, de előtte az érték logaritmusát kell venni. (07-dia 20.oldal) Ha az adatbázisban több féle változó van, akkor a különböző típusok súlyozott kombinációját vesszük a hasonlóság kiszámításakor. Vector objects:
19
6.2 Két klaszterező algoritmus A klaszterezés két típusa:
Felosztó klaszterezés: Az objektumok felosztása nem átfedő részhalmazokra (klaszterekre) úgy, hogy minden objektum pontosan egy részhalmazban szerepelhet. Hierarchikus klaszterezés: Egymásba ágyazott klaszterek egy hierarchikus fába szervezett halmaza.
6.2.1 A k-közép klaszterezés k-közép klaszterezés: Ez egy felosztó klaszterezés. Minden klasztert annak középpontja (centroidja) reprezentál. A pontokat ahhoz a klaszterhez rendeljük, melynek középpontjához a legközelebb van. Előre meg kell adni, hogy hány k darab klaszterre szeretnénk bontani a halmazt. Az eljárás:
Válasszunk ki k darab pontot (általában random) Hozzunk létre k klasztert a pontoknak a legközelebbi középpontokhoz való hozzárendelésével. Számoljuk újra a középpontot minden klaszternél. Ha a középpontok megváltoztak vissza 2-esre
20
Megjegyzések:
a középpont általában a klaszterbeli pontok átlaga Az adatokat futtatás előtt célszerű normalizálni A K-közép módszer konvergál a fenti általános hasonlósági mértékekre. A konvergencia legnagyobb része az első néhány iterációban megtörténik. Komplexitás: O( n * K * I * d ) n = pontok száma, K = klaszterek száma, I = iterációk száma, d = attribútumok száma
Problémák a k-közép módszerrel:
Kiugró értékekre érzékeny (k-medoid orvosolja, 07-35.old) Kezdeti középpontok problémája (Ha adott K ,,igazi” klaszter, akkor annak esélye, hogy minden klaszterből választunk középpontot kicsi. Megoldására vannak módszerek) Az alap k-közép üres klasztereket is adhat Előre meg kell adni a klaszterek számát
6.2.2 Összevonó klaszterezési algoritmus Összevonó klaszterezési algoritmus: Hierarchikus klaszterezés, Egymásba ágyazott klaszterek egy hierarchikus fába szervezett halmazát állítja elő (ábrázolására dendrogramot használunk. a függőleges tengely adja meg hogy mi volt a két összevont klaszter távolsága).
21
Hasonlósági vagy távolság mátrixot használ. 1. 2. 3. 4. 5.
Számoljuk ki a közelségi mátrixot. Legyen minden egyes pont egy önálló klaszter. Vonjuk össze a két legközelebbi klasztert. Frissítsük a közelségi mátrixot. Ismételjük a 3.-tól amíg csak egy klaszter nem marad.
Megjegyzések:
A klaszterek közötti távolság definíciójának különböző megközelítései más-más algoritmusokhoz vezetnek. A hasonlóság mérése lehet pl: MIN, MAX, Csoport-átlag, Középpontok közötti távolságok Nem kell feltételezni semmilyen konkrét klaszter-számot előre. Tárigény: O(N2) tárigény mivel a közelségi mátrixot használja. Időigény: O(N3) időigény az esetek többségében (N lépést kell végrehajtani és minden egyes lépésben egy N2 méretű közelségi mátrixot kell frissíteni és kell benne keresni.)
Problémák:
Ha egyszer döntést hozunk arról, hogy két klasztert összevonunk, akkor azt már nem lehet meg nem történtté tenni. Nincs célfüggvény, melyet közvetlenül minimalizálunk. Érzékenység a hibára és a kiugró adatokra Hajlam nagy klaszterek szétvágására
6.2.3 DBSCAN: egy sűrűség alapú algoritmus Sűrűség = egy rögzített sugáron (Eps) belüli pontok száma Egy pont belső pont ha egy előírtnál (MinPts) több pont van Eps sugarú környezetében. (Ezek lesznek egy klaszter belsejének pontjai.) A határ pontnak az Eps sugarú környezetben MinPts-nél kevesebb pontja van, azonban van belső pont ebben a környezetben. A zajos pont az összes olyan pont, amelyik nem belső illetve határ pont. 22
23
Máshogy leírva (először töröljük a zajokat majd):
Előnyök:
ellenálló zajjal szemben Különböző méretű és alakú klasztereket egyaránt tud kezelni
Hátrányok:
Változó sűrűségű halmazoknál gondok Magas dimenziójú adatoknál gondok
(OPTICS) Ez a módszer segít egy jó eps, és Minpts eltalálására.
24
7. Szövegbányászati módszerek. Wiki alapján a szövegbányászat:
„A szövegbányászat (angolul text mining) a strukturálatlan vagy kis mértékben strukturált szöveges állományokból történő ismeret kinyerésének tudománya; olyan különböző dokumentumforrásokból származó szöveges ismeretek és információk gépi intelligenciával történő kigyűjtése és reprezentációja, amely a feldolgozás előtt rejtve és feltáratlanul maradt az elemző előtt. Az egyszerű keresésnél jóval többet hivatott nyújtani a szövegbányászat. Míg szöveges keresés esetében meglévő információkra kívánunk kis időbefektetéssel rátalálni (nagy relevanciájú találati eredmények által), addig a szövegbányászat során olyan tudásra, ismeretekre is szert kívánunk tenni, ami explicite nem volt benne a rendelkezésre álló dokumentumállományban (korpuszban), csak indirekt módon, rejtve, látensen. Bár a teljes szövegű keresés is a szövegbányászat része, a szövegbányászat a keresésnél jóval többet jelent, hasonlóan, ahogy az adatbányászat is jóval többet jelent az egyszerű adatkeresésnél. A szövegbányászat nagy mértékben épít az adatbányászat eredményeire, ahol elsősorban számszerű adatok feldolgozása történik intelligens gépi módszerekkel. Az adatbányászat azon eredményeit, amelyek minták felismerésére, adatreprezentációra, előrejelzésre, statisztikai összefüggések kimutatására vonatkoznak, a szövegbányászat is nagymértékben hasznosítja. A különbség abban mutatkozik, hogy míg adatbányászat esetében jól strukturált számszerű adatokkal dolgozunk, addig a szövegbányászatban strukturálatlan szöveges állományok képezik a kiindulási alapot.” Dokumentumokat akarunk feldolgozni, osztályozni.
7.1 Látens szemantikai indexelés Forrás: http://seo-hungary.com/2009/04/latent-semantic-indexing/ Látens szemantikai Indexelés – ütőkártya vagy hisztéria – a Latent Semantic Indexing (LSI) alatt olyan technológiát értünk, amelyet vezető keresőmotor üzemeltetők – köztük a Google – vezettek be és amelyek segítségével a keresőmotorok képesek a szövegtartalmakat szemantikailag felismerni és értelmezni. Az LSI lehetővé teszi, hogy lokalizálják egy kulcsszó szinonimáit és rokon fogalmait, és az olyan szövegeket, amelyekben ilyenek előfordulnak, relevánsnak soroljanak be – még akkor is, ha maga a keresőfogalom nem fordul elő a szövegben. A Latent Semantic Indexing-gel kapcsolatban egy ideje számos híresztelés terjeng, bár ezek részben hisztériák. Vegyük szemügyre a Latent Semantic Indexing fejlődését az ismertté válása óta … Míg a keresőmotorok korábban csak a meglévő kulcsszavakat elemezték, a szemantikai technológia tovább megy egy lépéssel. Itt még egy megfelelő dokumentum környezetét is analizálják, azaz a keresőmotorok az adott szöveget összehasonlítják olyan dokumentumokkal, amelyek azonos vagy hasonló szavakat és szócsoportokat tartalmaznak. Ennek során a 25
technológia azokat a szövegeket sorolja be szemantikailag rokonnak, amelyek sok hasonló szót és szósort használnak. Ha csak kevés szó egyezik, akkor a szöveg szemantikailag távoli besorolást kap, következésképp az adott keresőfogalom szempontjából nem releváns. A gyakorlatban ez a következőt jelenti: ha egy keresőmotor Latent Semantic Indexing-et használ, akkor például a Saddam Hussein keresőfogalomra egyrészt olyan keresési eredményeket ad, amelyek összefüggésben állnak Saddam Hussein-nel és az Öböl-háborúval, az iraki háborúval vagy Kuvaittal. Másrészt azonban olyan tartalmakat is megjelenít, amelyeknél az adott keresőfogalom sehol sem fordul elő a szövegben. A keresőmotor a szöveges tartalmak alapján tudja, hogy mely eredmények lehetnek mégis relevánsak. Míg ennek alapján nagyon is van értelme rokon fogalmakat integrálni webes szövegekbe, egy weboldal üzemeltetőjének e technológia tekintetében mégis legfőképp a bejövő linkek illetve a megfelelő linkszövegek használatára kell ügyelnie. Ma már nem titok, hogy a bejövő linkek szövege nagymértékben befolyásolja a honlap helyezését. Ebből a szempontból tehát kerülni kellene a mindig azonos linkszövegek használatát. Különben gyorsan kelthetjük azt a benyomást, hogy az oldal túloptimalizált. Az ilyesmit a keresőmotorok nagyon nem szeretik. Ennek következménye lehet például úgynevezett over-optimization-penalties, ami a szembetűnően túltupírozott honlapok büntetése. A siker kulcsa itt a lehetőleg természetesnek ható linkszövegekben van. Nincs ugyan kész recept, vizsgálatok azonban azt mutatták, hogy sok top-helyezésű oldal esetében a kulcsszavaik körülbelül a beérkező linkek 30-40%-ában fordulnak elő. A linkszövegekben szinonimák és rokon fogalmak használatával tovább növelhető a beérkező linkek relevanciája, anélkül, hogy természetellenesnek hatnának. A keresőmotorok megértik ezeket az alternatív fogalmakat és az Ön oldala ennek megfelelő helyezést kap az adott keresőfogalmak szerint. Annak kiderítésére, mely fogalmakat tekinti a Google szinonimának, használhatjuk a szinonima-keresőparancsot (~ / Alt Gr + ). Ha például az autó fogalmára keres szinonimákat, egyszerűen a következő keresőfogalmat adja be a Google-ban: ~autó Így megkapja azokat az oldalakat, amelyek a keresőfogalommal rokon kulcsszavakat tartalmaznak, például autós-hírek, lízing, cars A rokon kifejezések használatával megerősítheti a főfogalmait, ami jobb helyezést eredményez – gyakori ismételgetések és az ezekhez kapcsolódó büntetés veszélye nélkül. Kérem, ügyeljen arra: amíg igyekszik lehetőleg természetesen írni, és a keresőmotorok helyett mindig az olvasóira van inkább tekintettel, minden valószínűség szerint úgyis számtalan LSI kulcsszót használ. Így ennek a témának nem kell különösebb plusz figyelmet szentelnie. Összegzés a Latent Semantic Indexing tekintetében: használjon különféle kulcsszavakat, beleértve a szinonimákat és rokon fogalmakat, különösen a linkszövegekben. Ezáltal az oldala természetesebbnek hat. Ez pedig segíti abban, hogy helyezést kapjon a rokon fogalmak szerint is – még akkor is, ha azok épp nem fordulnak elő az oldalán. Ráadásul ezáltal javíthatja a főfogalmai szerinti helyezését is.
26
7.2 Kulcsszó alapú asszociációs analízis (keyword based association analysis) A cél megtalálni olyan kulcsszavakat/kifejezéseket, melyek gyakran fordulnak elő együtt, majd megtalálni az asszociációs illetve korrelációs kapcsolatot közöttük. Az asszociációs analízis szakaszai:
A szöveg elő feldolgozása (parsing, stemming(pl drug=drugs=drugged), removing stop words(pl. a, the of , always, with), etc.) Már bevált asszociációs szabályokat kereső eljárások használata. Kezeljük a dokumentumokat kosarakként. A „cikkek” pedig legyenek a kulcsszavak, amiket tartalmazhatnak a kosarak. ?term level association mining: ? nem kell embernek felügyelni, csökken az értelmetlen eredmények száma és gyorsabb is lesz
7.3 Szöveg klasszifikálása Motiváció: nagyon sok online dokumentumot szeretnénk automatikusan klasszifikálni/osztályozni. (weblapok, email) A folyamat pontokba szedve:
Adatok elő feldolgozása Tanuló és teszt adatok előállítása A klasszifikációs modell elkészítése (pl. valamilyen tanult módon) A modell kiértékelése A modellt ráengedjük új szövegekre
Nehézséget jelent, hogy a szöveg nem olyan jól strukturált mint egy relációs adatbázis
7.4 Dokumentumok klaszterezése Motiváció: A szövegek automatikus csoportosítása tartalmuk alapján, futásidő alatt, tanuló adathalmaz nélkül. A folyamat:
Adat elő feldolgozás (remove stop words, stem, feature extraction, lexical analysis, etc.) Hierarchikus klaszterezés/Modell based klaszterezés
27
7.5 Vektortér modell A dokumentumot egy term vektorral reprezentáljuk. A term lehet szó vagy kifejezés. Minden term egy dimenziót definiál, így n term kifeszít egy n dimenziós vektorteret. A vektorokat súlyozzuk aszerint, hogy az egyes termek mennyire fontosak. A dokumentumot az azt reprezentáló vektora alapján soroljuk be, vektorhasonlóság alapján. Hogyan súlyozzunk? TF súlyozás: minél gyakrabban fordul elő a t term annál közelebb van a témához. TF=f(t,d) megadja, hogy hányszor fordul elő a t term a d dokumentumban. Mivel a dokumentum hossza torzítja az
eredményt érdemes normalizálni. IDF súlyozás: minél ritkábban szerepel a dokumentumok összeségében, annál diszkriminatív.
TF-IDF súlyozás: a felső kettő kombinációja weight(t,d)=TF(t,d)*IDF(t) Hogyan mérjük a hasonlóságot?
28
A lényeg hogy a fentiekkel van egy vektorterünk, amire a szokásos megoldásokat rá lehet engedni (pl k-közép, döntési fa,neuronhálók,svm)
29
8. Entity resolution forrás: Sidló Csaba: http://people.inf.elte.hu/kiss/13dwhdm/ER-elte-11-03-22.pdf A feladat: rejtett, való világbeli entitásokhoz köthető megfigyelések csoportosítása az entitások köré. entity resolution = azonosságfeloldás Reprezentálható:
rekordok halmazával XML fa gráf
A csoportosítás módszerei:
match-merge = összevonás reprezentatív elemmel klaszterezés közelítés/egzakt megoldások felügyelt/nem felügyelt tanulás
8.1 Record Linkage model (1969) – Hogyan kötjük össze a halmazokat Legyen két halmazunk, A és B. Legyen 𝐴 𝑋 𝐵 = { (𝑎, 𝑏): 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵 } Ezeket az (a,b) párokat akarjuk besorolni M (matched) vagy U (unmatched) halmazokba. Cél: olyan A1, A2, A3 halmazokat képezni, melyre
A1 („positive link”): (a, b) ∈ M vagy A2 („positive non-link”): (a, b) ∈ U esetleg A3 („possible link”): nem tudjuk eldönteni
Gyakorlatban A és B két (többnyire különböző forrásból származó) rekordhalmaz.
8.2 Comparison vector – összehasonlítás mi alapján történjen
𝛾[𝛼(𝑎), 𝛽(𝑏)] = {𝛾1 [𝛼(𝑎), 𝛽(𝑏)], … , 𝛾 𝐾 [𝛼(𝑎), 𝛽(𝑏)] } azaz a rekordra rekordra meghatározunk (α,β) jellemzőket, pl: „a neve ugyanaz”, „a név egyik rekordnál hiányzik” comparison space: miden lehetséges realizáció halmaza
8.3 Duplicate Record Detection – mit kezdjünk a duplikátumokkal
hasonló alaphelyzet: A és B, két halmaz közti párokra (𝛼, 𝛽) ∈ 𝑀 vagy (𝛼, 𝛽) ∈ 𝑈 lexikális heterogenitás feloldása a cél adatelőkészítés: parsing, data transformation, standardization (→ 'ETL') megoldások: vagy megtanulják a megoldást, vagy szakértői tudás kell ha van tanulóadat: M és U egy részhalmaza adott o pl.: Naív Bayes hasonlóságokat figyel meg a két halmaz között
30
o Ellenőrzott tanulás: CART, SVM, regresszió active learning: emberi közreműködés, jól választott döntések meghozatala o többféle klasszifikátor egyidejűleg, majd a bizonytalan elemekre kérdezni o pl.: ALIAS rendszer ha nincs tanulóadat: o statisztikai módszerek (EM) o rekord szintű hasonlósági függvények: távolság alapú módszerek távolság függvény + threshold-ok speciálisan: szabály alapon; szakértők → szabályok → szabály alapú egyezések o unsupervised learning: klaszterező algoritmusok speciális: sok, jellemzően kicsi klaszter
Gyorsítási lehetőség: rekord párok számának csökkentésével, vagy rekord-rekord összehasonlítás gyorsításával.
8.4 String matching / field similarity – mely mezők egyeznek meg?
karakter alapú hasonlóság metrikák token-alapú hasonlóság metrikák o pl. prefixek egyezése fonetikus hasonlóság
8.5 Generic Entity Resolution
páronkénti döntés: rekord-párok összehasonlítása egzakt megoldás (nincs közelítés) nincsenek kapcsolatok: a rekord minden információt tartalmaz feature-ök: attribútum kombinációk fix séma (adott attribútumok) merge lezárt: legkisebb új elemmel bővíthetetlen 'domination': rekordok rendezése – melyik 'jobb' leíró entity resolution (ER): legkisebb olyan lezárt, ami nem tartalmaz dominált elemeket
Lezártak képzése
31
8.6 Relational Clustering
relációs = kapcsolati; cél: reference graph → resolved entity graph hipergráf; hiperélek: kapcsolatok “naïve relational”
8.7 Ügyfeles példa
A példában szereplő csoportosítás „nehéz”, O(n2) a párok vizsgálata miatt! A gyakorlatban sok a probléma a csoportosítással:
heterogén adatforrások: redundáns, örökölt, átfedő stb. rendszerek heterogén formátum: különböző sémák, szabványok, szokások (pl. postai címek) adatminőség, lexikális heterogenitás: adatbeviteli hibák, hiányzó, kitöltetlen attribútumok, szabályok megkerülése (pl. default értékek, 11111-es azonosítók vagy 1970.01.01 dátum) stb.
8.8 További példák:
klasszikus feladat: publikációs adatbázisok o kevés attribútum: írók nevei, esetleg munkahely o kapcsolatok entitások közt: közösen írt cikkek ügyfelek: o jellemzően sok attribútum: természetes + generált (id) o heterogén forrásrendszerek (különböző portfóliók, örökölt rendszerek, o összeolvadások stb.); hány ügyfelünk van igazából? kerestük már ajánlattal? o szerződtünk már vele valaha? o pl: Yahoo közel-keleti felvásárlás: mennyi az új felhasználók száma valójában – o mennyit érdemes költeni? web: o weboldalak ('mirror detection'), termék-keresők termékei, entitások weboldalakon: o személyek, dátumok, helyek stb.; hány Facebook / IWIW felhasználó van igazából o stb…
32
8.9 Trendek, nyitott kérdések
egyre szélesebb körű igények osztott rendszerek, jól skálázódó megoldások: hogyan? egyéb gyorsítási módszerek: blocking, iterative blocking, … ? duplikátum-azonosítás mint keresési probléma: indexelés viselkedés alapú azonosság-feloldás: tranzakciós logok időben változó adatok, időben változó szabályok, időben változó entitások felügyelt tanulás, „active learning”: hibák iránya fontos valószínűségi modellek vs. egzakt eredmények eredmény minősége: hogyan mérjük? entitások hierarchikus egymásra épülése kapcsolat alapú azonosság-feloldás, gráf-klaszterezés keretrendszerek, dobozos termékek: mennyire használhatóak? → iparági tudás beépítése
33
