TDK Dolgozat Készítette: Vágó Tamás II. éves mérnök informatikus Msc hallgató
Konzulens: Dr. Kovács László Általános Informatikai Tanszék
Miskolc 2010.
Előszó
Napjainkban is számos keresőprogram létezik, melyek segítésével hatékonyan tudunk keresni a weben. Ám mindegyik keresőprogramnak a legfőbb előnye egyben a hátránya is, mégpedig hogy csak a keresés során beírt kulcsszavakra szűkíti a találatok listáját. Ez a keresési jól használható, ha céltudatosan tudjuk, hogy mit keresünk. Ám amikor valamilyen témában szeretnénk elmélyíteni a tudásunkat és hasonló témájú oldalakat szeretnénk találni akkor nehézségekbe, ütközünk. Igaz a fejlettebb böngészők már támogatják a tartalmilag hasonló dokumentumokra való keresést, de ekkor is csak egy találati listát kapunk nem pedig egy átfogó képet az adott tématerületen fellelhető dokumentumokról. A dolgozat célja egy olyan keresési alternatíva létrehozása melynek segítségével a felhasználó képes lehet egy átfogó képet kapni a weben található dokumentumokról, illetve arról hogy az adott tématerülethez mely dokumentumok kapcsolódnak szorosan illetve kevésbé. A tartalom alapú web térkép egy olyan keresési eszköz melyen a felhasználó vizuálisan is látja az egyes dokumentumok adott témabeli távolságát. Minél jobban hasonlít, két dokumentum tartalma annál közelebb kerülnek egymáshoz a térképen illetve minél különbözőbbek annál távolabb. A dolgozatban ismertetésre kerülnek a térkép készítése során alkalmazott szövegbányászati technikák illetve azok konkrét alkalmazása. Hogy az esetleges rejtett tartalmi összefüggéseket is fel lehessen deríteni, a web térkép dokumentumain a DBSCAN algoritmus segítségével, a dokumentumok klaszterezésre kerülnek. Így további összetartozó csoportokat tudunk felderíteni és megjeleníteni a térképen. A program fejlesztése során egy további alkalmazási módot is sikerült felderíteni. A program kiválóan alkalmaz az egyes site-ok tartalombeli homogenitásának a vizsgálatára, melynek segítségével vizuálisan is láthatóvá válik, hogy mely oldalak tartoznak tartalmilag leginkább egy oldaloz, és melyek azok az oldalak amelyek kilógnak a sorból.
2
Tartalomjegyzék Előszó ......................................................................................................................................... 2 Súlyozási sémák a vektortér modellben ................................................................................. 4 Szótövezés .................................................................................................................................. 6 STOPWORD .............................................................................................................................. 7 Bitmap index: ......................................................................................................................... 8 Invertált dokumentum index: ................................................................................................. 9 A programban használt adatszerkezetek: ............................................................................. 11 Internetes Keresőprogramok működése ................................................................................... 13 A Google bemutatása ........................................................................................................... 13 Googlebot, Web Crawler .................................................................................................. 13 Google Indexer ................................................................................................................. 14 Querry processor, avagy a Lekérdező komponens ........................................................... 15 PageRank Számítása ........................................................................................................ 15 A keresés folyamata ......................................................................................................... 17 A program felépítése ................................................................................................................ 18 A rendszer felépítése: ........................................................................................................... 18 Dokumentumok begyűjtéséért és feldolgozásáért felelős alrendszer: .............................. 18 Dokumentumok tárolásáért és távolságának meghatározásáért felelős alrendszer .......... 19 Adattároló alrendszer ....................................................................................................... 20 Térkép készítő és megjelenítő alrendszer ......................................................................... 20 Térképkészítő algoritmus ......................................................................................................... 21 Az algoritmus működése: ..................................................................................................... 22 Webes tartalom klaszterezése ................................................................................................... 24 DBSCAN algoritmus bemutatása......................................................................................... 25 DBSCAN paramétereinek dinamikus meghatározása .......................................................... 27 DBSCAN algoritmus általánosítása ..................................................................................... 28 Az iteratív keresés folyamata ........................................................................................... 28 Az elkészült program hatáskörének elemzése .......................................................................... 31 Konkrét példa a webtérkép alkalmazására ............................................................................... 33 Összegzés, kitekintés ................................................................................................................ 35 Függelék ................................................................................................................................... 36 Képek és ábrák jegyzéke .......................................................................................................... 37 Irodalomjegyzék, Hivatkozások ............................................................................................... 38
3
Vektortér modell
Már a 1960-as években felmerült az igény egy hatékony szöveg reprezentációt biztosító modellre. Mely hatékonyan támogatja a keresést. Az első modell System for the Mechanical Analysis and Retrieval of Text azaz a SMARTi volt. Ezen rendszer segítségével hatékonyan lehetett keresni a különböző dokumentumok között, és alapja a vektortér modell volt. A vektortér modell alapvető koncepciója hogy a dokumentumokat vektorként ábrázolja a bennük található szavak alapján, melyek a vektor dimenzióját adják. A dokumentumtér egy mátrixszal reprezentálható, aminek: ●
sorai az egyedi szavak előfordulását
●
oszlopai pedig az adott dokumentumot szimbolizálják
Legyen D egy dokumentum gyűjtemény melynek elemei dokumentum vektorok, az így kapott gyűjtemény egy mátrix segítségével reprezentálható. 𝑑0,0 𝐷=[ ⋮ 𝑑𝑖,0
⋯ ⋱ ⋯
𝑑0,𝑗 ⋮ ] 𝑑𝑖,𝑗
Természetesen a 0 és 1 reprezentáció helyett más megoldásokat is szoktak alkalmazni, mint például 1 helyett az adott szó számosságát tüntetik fel a mátrixban.
Vegyük észre hogy
A vektortér modell sajátosságából fakadóan a szavak a sorrendiségüket elveszítik, az ilyen modelleket BOW reprezentációnak hívják, azaz Bag Of Word, vagyis magyarul szózsák modell.
Súlyozási sémák a vektortér modellben
4
Többféle súlyozás is létezik a vektortér modellii D mátrixának, az elemeinek a meghatározására. Ilyen módszerek: ●
Bináris súlyozás: a legegyszerűbb súlyozási megoldás, hátránya hogy elvész a szavak gyakorisága az adott modellben. Formája:
●
Előfordulási gyakoriság alapú súlyozás: előnye hogy figyelembe veszi a szavak adott dokumentumon belüli gyakoriságát. Hátrányként felróható hogy nem minden szó esetén a gyakoriság határozza meg adott szó relevanciáját, hiszen számos esetben a Zipf törvényiii érvényesül, vagyis egy nyelv leggyakoribb szavai általában csak a mondatszerkezet létrehozását szolgálják, és más jelentőségük nincs. Ezeket a szavakat általában STOPWORDS ként említi a szakirodalom Melyeket sok esetben szűrni szoktak.
●
Logaritmikus súlyozás: Előnye hogy elnyomja a túl gyakori szavakat, amik nagy valószínűséggel STOPWORD-ök ezáltal ha úgy tetszik, normalizálja az adott dokumentum szógyakoriságait. 𝑑𝑖,𝑗 = {
●
o
𝑘𝑖
, , 𝑒𝑔
𝑘𝑖
𝑘
𝑡
Term Frequecy (TF, szó gyakorisága a dokumentumban): Egy adott szó gyakoriságánál azt vizsgálja, hogy a szó mekkora részét képzi a dokumentumnak. Ez a módszer jól működik heterogén dokumentumhalmazok esetén is.
●
Inverse Document Frequecy:(inverz gyakoriság alapú súlyozás): A Tf és logaritmikus súlyozás kombinálása, mely rendelkezik mindkét módszer előnyeivel.
5
Szótövezés Minden szövegbányászati alkalmazásban kulcsfontosságú szerepet játszik a szótövezés, hiszen a különböző ragok, jelek és más nyelvi elemek eltávolítása a hatékonyság és egyértelműség növelése szempontjából kifejezetten előnyös. Mivel tartalom alapú a fejlesztett rendszer ezért nem jár információ veszteséggel a szótövezés, csupán redukálja a problémateret, ahol a tartalmat meghatározó szavak egységes formába kerülnek. A szótövezés után a szavak legkompaktabb formáját kapuk, továbbá szótövezés nélkül az egyes szavak különböző formái a dokumentum vektortér modellben más és más elemként szerepelnek. De a szótövezéssel kiküszöbölhetjük ezt a problémát. A szótövezési technikáknak két fő fajtája van: -
Szabály alapú
-
Adatbázis alapú
A szabály alapú szótövezők a szavak képzési szabályait tartalmazzák, melynek segítségével a szabályokat visszavezetve megkaphatjuk az egyes szavak eredeti szótövét, illetve ellenőrizhetjük, hogy helyes-e az adott szó. Ennek a módszernek az előnye, hogy a szabályok segítségével egy általános megoldást lehet kapni, relatíve kicsi információ tárolásával. A rendszer általánosan használható, ám előfordulhat, hogy nem minden esetben szótövez helyesen. Ilyen szótövező például az angol nyelven kiválóan működő Porter-féle szótövezőiv. Az adatbázis alapú szótövezők a szabályalapúak ellentétei, hiszen szabályok nélkül hatalmas adatbázis segítségével dolgoznak, mely tartalmaz minden egyes ragozott szót, szótövét és más nyelvtani szabályokat. Ezen rendszerek az előnye, hogy gyors és pontos szótövezésre képesek. Hátrányuk viszont hogy nem elég általánosak és relatíve hatalmas adatmennyiségekkel dolgoznak. A program készítése során mégis az adatbázis alapú szótövezést kellett választanom, hiszen a magyar nyelv bonyolultsága miatt a szabályalapú szótövező rendszerekből nincs túl sok a piacon, és amik megtalálhatóak azok csak fizetős formában érhetők el. Szerencsére létezik egy ingyenes és nyílt forrású kezdeményezés is mely a BME-s Szószablya projekt. Ez a 6
projekt egy hatalmas adatbázist hozott létre szótövezésre, ami ingyenesen letölthető és szabadon használható. Mivel tekintélyes méretű ezért a benne szereplő gyakorisági számok alapján csak a leggyakoribb szavak kerültek átemelésre. A hatalmas adatbázis redukálása céljából. Az eredeti adatbázis több mint 2 millió ragozott szót tartalmaz. Amely tárigénye a program hordozhatóságát jelentősen rontaná. Illetve a feldolgozási idők is nagymértékben csökkennének. Ezért egy tervezési döntést kellett bevezetni a program fejlesztése során, mégpedig hogy az adatbázisból a 100 000 leggyakoribb elem került átemelésre.
STOPWORD A STOPWORD vnem más, mint azoknak a szavaknak a halmaza melyeket ki lehet szűrni szövegből jelentősebb információcsökkenés nélkül. Tipikusan ezek a szavak csak a mondat szerkezetének a kialakításához járulnak hozzá, de jelentésbeli funkciójuk nincs. Minden nyelvnek megvannak a maga stopword-jei melyek szűrésével hatékonyságnövekedést lehet elérni. Ezeknek a szavaknak a megtalálása rendkívül egyszerű, hiszen minden nyelvben ezek fordulnak elő a legnagyobb gyakorisággal. A magyar nyelvben ezek a szavakvi a következőek: a
meg
össze
van
én
az
el
vissza
lesz
te
egy
át
de
volt
ő
be
rá
hát
csak
mi
ki
ide
és
nem
ti
le
oda
vagy
igen
ők
fel
szét
hogy
mint
ön
Jól látszik, hogy e szavak jelentős része nem tartalmaz semmilyen extra információt a dokumentumok kiértékelése szempontjából. További előnye a stopword-ök szűrésének mikorosite-oknál illetve kisméretű dokumentumoknál figyelhető, meg amikor is a szűrés után tényleg csak a lényegi információk
7
maradnak meg a feldolgozás után. Ezáltal az oldalak távolságát valóban csak a tartalom befolyásolja.
Szöveg feldolgozást támogató reprezentációs modellek A szöveg reprezentáció mindig is kulcsfontosságú momentum volt a szövegbányászatban, hiszen egy jól megválasztott hatékony adatszerkezet nagyban segíti a feldolgozási és keresési műveletek végrehajtását az adott halmazon. A reprezentációs technikák közül több is kialakult a szövegbányászat múltja során, melyeknek fejődését leginkább a hardver fejlődésével lehet összekapcsolni. A két legelterjedtebb fizikai reprezentáció, a dokumentum vektortér modellhez a következő: -
bitmap index
-
invertált index
Bitmap index: Ez egy mátrix alapú reprezentációvii, melynek sorai az egyes szavakat oszlopai pedig az egyes dokumentumokat tartalmazzák. Természetesen az oszlopok és sorok jelentése az adott tervezői elgondolástól függ. Működése: Mivel bitmap alapú indexelésről van szó, a mátrix elemei 1 illetve 0 ahol az egy azt jelzi, hogy az adott szó szerepel a dokumentumban a 0 pedig hogy nem.
Formája:
i szavaknak, j dokumentumoknak felel meg.
Például:
8
D1 D2 D3 alma
1
0
1
körte
1
1
0
szilva
0
1
0
barack 1
0
1
Lehetséges keresési kérések lehetnek azok a dokumentumok ahol: alma ÉS körte ÉS barack (alma VAGY barack) ÉS körte Előnye: ●
gyors keresést biztosít (bináris műveletekkel tudunk szűrni)
●
alacsony memóriaigény
Hátránya: ●
nagy mennyiségű adatnál kezelhetetlenné válik
●
ritka mátrixok problémája felvetődik (memóriaigény számítási költség)
●
további hátrány még hogy csak azt tárolja, hogy adott dokumentumon belül szerepel-e a keresett szó, tehát további költség hogy át kell vizsgálni a dokumentumot. (O(dokumentum hossza))
●
problémás hatalmas dokumentum halmazok esetén, a nagyméretű mátrixok tárolása
Mikor előnyös: ●
kisméretű dokumentumhalmaz esetén
●
olyan kereséseknél ahol csak a kulcsszó tartalmazása számít
Invertált dokumentum index: Egy átgondoltabb szöveg reprezentációs technikaviii, mely a bitmap reprezentációval szemben láncolt listákat alkalmaz. Így a reprezentációtól függően nem csak azokat a dokumentumokat
9
tartalmazza, ahol szerepel az adott szó, hanem adott dokumentumon belül a szó előfordulásának pozícióit is. Felépítése: Egyszerűbb reprezentáció, mely csak a szavak előfordulását tartalmazza:
1. ábra – szavak előfordulásának tárolása dokumentumbeli pozíció nélkül
Összetettebb reprezentáció, mely a szavak előfordulása mellett a dokumentumbeli pozíciókat is tartalmazza:
2. ábra – szavak előfordulásának tárolása dokumentumbeli pozícióval
Ennél a reprezentációnál már a dokumentumon belüli előfordulások is le vannak tárolva, tehát a keresés még inkább hatékonyabbá válik. (i,j) i: melyik dokumentumban fordul elő a szó, j adott dokumentumon belül hol található. Előnye: ●
A keresés során könnyebb megtalálni egy adott dokumentumon belül a keresett szavakat
●
dinamikus memóriaallokálást tesz ehetővé
●
figyelembe veszi a szavak számosságát is 10
●
nagyméret dokumentumhalmaz esetén is működik
●
A módszer tárigénye csökkenthető minimális számítási költséggel
Hátránya: ●
A keresés sebessége lassabb
●
A pointerek extra memóriát igényelnek
A programban használt adatszerkezetek: A programban működése szempontjából követelmény a gyors működés, ennek következtében az adatok gyors elérése. Ezért a programban számos helyen megjelennek a Hash függvényix alapú módszerek, azaz hasító táblák alkalmazása. Ezen adatszerkezetek nagy előnye az adatok azonnali elérése.
3. ábra - Hash tábla működése
Ennek egy speciális változatát a Dictionaryx generikus típust használja a program mely tetszőleges adattípusból felépíthető és O(1) idő alatt bármely eleme elérhető. Ez egy olyan speciális hash tábla mely kezeli az adatok túlcsordulását. A generikus típusok további előnye hogy tetszőleges mélységben egymásba ágyazhatunk más generikus típusokat is, melyből komplex struktúrákat alakíthatunk ki. Természetesen a faszerűen felépített struktúra leveleiben konkrét típusoknak kell szerepelniük. A Dictionary adatszerkezet egy kulcs-érték párost tartalmaz. A kulcs az adat eléréséhez szükséges, az értékben pedig a letárolandó adatok szerepelnek. Mivel számos esetben, kiváltképpen szavak számlálásánál a gyors elérés és értékmódosítás, továbbá a rendezett könnyen visszakereshető struktúra a cél, ezért ez az adatszerkezet a legmegfelelőbb a szövegbányászati célokra. 11
A program fontosabb területei ahol a Dictionary struktúra megjelenik: Nyers dokumentumok tárolása (URLDokumentum adatai (szöveg,simenő linkek, …) Szavak előfordulási gyakorisága (Szó[Dokumentum sorszáma, szó darabszáma az aktuális dokumentumban]) Dokumentumok távolságának mátrix (URL1URL2Távolság) Virtuális Dokumentumpontok távolságának mátrixa (URL1URL2Távolság)
Dokumentumok távolságának mérése
A dokumentumok hasonlóságát vagy különbözőségét hogy számszerűsíteni tudjuk, valamilyen metrikát kell hozzá rendelnünk. Két dokumentum távolsága, ha nagy, akkor a két dokumentum különbözik, míg ha kicsi a két dokumentum hasonló.
Többféle távolságmetrika, de ezek közül a leggyakoribbak a következőkxi: ●
Euklideszi távolság
●
Négyzetes euklideszi távolság
●
Manhattan távolság
●
Maximum távolság
12
●
Mahalanobis távolság
●
Koszinusz hasonlóság
A gyakorlatban leginkább kedvelt és alkalmazott távolságmetrika az euklideszi távolság illetve a koszinusz távolság (hasonlóság). A programban is az euklideszi távolságmetrika szerepel, mivel az euklideszi távolságot lehet a legáltalánosabban alkalmazni a távolság mérésére.
Internetes Keresőprogramok működése A Google bemutatása Napjainkban szinte már az interneten történő keresés szinonimájává vált a Google keresője, de sokan nem tudják, hogy hogyan is működik ez a rendkívül egyszerűnek kinéző, ám meglehetősen bonyolult rendszer. A konkrét működésrexii, három fő folyamat zajlik le a Google keresőjében, aminek a pontos találati eredményeket köszönhetjük: ●
Google bot, más néven Crawler ami begyűjti az interneten elérhető összes weboldalt
●
Indexer, ez a folyamat bontja szét a weboldalakat szavaikra, majd indexeli azokat egy hatalmas adatbázisban
●
Query Processor, megvizsgálja a beadott keresési kulcsszavakat majd összehasonlítja a belső adatbázisával, és visszaadja a legrelevánsabb találtatokat.
Googlebot, Web Crawler A Crawler dolga a weboldalak begyűjtése a weben, a Google ezen komponense másodpercenként több ezer oldalt tölt le párhuzamosan, majd továbbítja azt az Indexer felé.
13
De ne higgyük azt, hogy a Google minden oldalt megtalál és az egész internetet képes bejárni. A Google az internet bejárását az oldalakon talált hivatkozások segítségével illetve korábbi adatbázisban eltárolt címekkel járja be. Ha példádul egy új weboldalt készítünk a Google azt nem vagy csak hosszabb idő után képes bejárni, hiszen ha nem mutat rá URL más módon kell az oldal címét beszereznie. A Google hogy ezt a hibát kivédje, engedi az oldalak manuális hozzáadását is a keresője számára http://www.google.com/addurl.html). A Google a meglátogatott oldalakon talált hivatkozásokat hozzáadja a bejárandó oldalak listájához, majd ezután a következő oldalra ugrik ebben a listában és azzal is ugyanezt a folyamatot hajtja végre. Vagyis: ●
a bejárandó oldalak soráról egy oldalt kiválasztása
●
oldal letöltése, tárolása majd továbbítása az Indexernek
●
az oldalon talált hivatkozások hozzáadása a bejárandó oldalak sorához
Ezt a folyamatot nevezik deep web-nek elviekben ezzel a folyamattal az egész web bejárható feltéve, ha minden oldalra találunk hivatkozást. De mivel az internet hatalmas és az erőforrások végesek ezért a google se “látja” a teljes webet, hanem annak csak egy szignifikáns részét. Mivel ez a folyamat rendkívül erőforrás igényes a Google csak havonta végzi el az oldalak begyűjtését, és egyben az adatbázisa aktualizálását. Hogy a felesleges erőforrás-pazarlást elkerülje a bejárandó elemek listáján eliminálja a duplikált címeket, illetve hogy felesleges újra indexelés se történjen, a letöltött oldalakat összeveti a korábban letöltött és letárolt változatukkal, és ha nincs eltérés, azaz az oldal nem változott akkor nem kell az aktuális oldalhoz az indexeket újragenerálni. Ahhoz hogy mégis aktuális legyen, a legnépszerűbb oldalakat, mint például hírportálok, tőzsdeárfolyamok...stb. akár napi rendszerességgel vagy gyakrabban is letölti, és indexeli. Ezt a folyamatot fresh crawl-nak az előzőt pedig deep crawl-nak nevezik. E két folyamat megfelelő arányú kombinálásával mindig friss és hatékony keresés biztosít a felhasználói számára.
Google Indexer A korábban bemutatott Crawler a begyűjtött weboldalakat ennek a komponensnek továbbítja. Az oldalakat az index adatbázisa tárolja el, majd indexeli azokat. Tehát tárolódik az oldal, majd ezt az indexelő komponens szavanként kielemzi, és egy közös adatbázisba letárolja az összes szót és azok előfordulási helyét. A szavak alfabetikus rendezés szerint tárolódnak és nem csak az tárolódik le, hogy mely dokumentumban fordul elő, hanem az is hogy az adott dokumentumban mely helyeken szerepel.
14
(Invertált index) Ahhoz hogy tovább tudja, a hatékonyságát növelni a modulnak kihagyja az úgynevezett stop word-öket, ezek olyan szavak melyek egy nyelvben nagyon gyakoriak, de jelentés szempontjából nem jelentősek. Minden nyelvnek egyedi stop word listája van. Angolban például: the, is, on ,or, of, how... . Ezeket a szavakat az indexelő komponens szűri, illetve van még pár technika, amivel további teljesítménynövekedést illetve racionalizálást ér el, mint például: a fölösleges whitespace karakterek eltávolítása, szavak kisbetűssé alakítása, és még számos egyebét technika, ami javít a hatékonyságon.
Querry processor, avagy a Lekérdező komponens A lekérdező modulnak számos része van a felhasználói felülettől a releváns oldalak megjelenítésével bezárólag. Az egyik talán legfontosabb az egyedi algoritmusa, a PageRank, ennek az algoritmusnak köszönheti a Google a sikerét, hiszen ez az algoritmus dönti el egy adott oldalról, hogy az mennyire fontos számunkra. Az algoritmus egyik fő motívuma a tudományos publikációk fontosságának meghatározásán alapszik, tehát minél többen hivatkoznak egy oldalra, annál fontosabb az az oldal. Az algoritmus leglényegesebb motívuma ez, de számos részlete a mai napig üzleti titoknak minősül, és titkos. A PageRank több mint száz kritériumot vesz figyelembe az oldalak rangsorolásánál, beleértve a népszerűséget, az oldal méretét, az aktuális keresési trendeket, és még számos más dolgot.
PageRank Számítása Az oldalak súlyát a Google a PageRankxiii képlettel határozza meg, minél népszerűbb egy oldal annál többen hivatkoznak rá, ezért annál nagyobb a presztízse és a relevanciája is, ha egy találati listában szerepel. Mivel más oldalakra mutató linkek, egyfajta szavazást, emberi döntést képviselnek, ezáltal a Google ezen koncepciója helyesen működik. A hivatkozásokból minden oldal kap egy értéket mely minél nagyobb annál előkelőbb az oldal, viszont az oldal továbbadhatja az értékét, ha hivatkozik más oldalakra, természetesen ilyenkor nem vész el a teljes érték, hanem csak egy részét adja át. De hogy megértsük hogyan is működik ez, nézzük meg azt a két képletet, amit a Google maga is használ a PageRank kiszámításához. Legyen: M(i) az i. oldalra hivatkozó oldalak halmaza PR(i) az i. oldal PageRank értéke L(j) az j. oldalról kimenő hivatkozások száma tegyük fel hogy minden oldal d értéket ad ahol 0 < d < 1 azaz 1 - d marad neki.
15
Van egy másik képlet is, ami a valószínűség számítás oldaláról közelíti meg a kérdést, ilyenkor a PageRank értéke annak a valószínűsége, hogy valaki a linkeket használva közelíti meg az oldalt.
Egyes ajánlások szerint a d paraméter értékét rendszerint 0.85 körüli értékre állítják be. Fontos probléma a képlet számítása során a ,,danglink link’’-ek problémája melyek általában letöltendő fájlokra, és nem oldalakra mutatnak, de befolyásolják a PR értékét, ezért a rendszer szűri ezeket a linkeket. A PageRank számítása egy iteratív folyamat melyben a képletet többször meg kell ismételni, hogy a kívánt eredményt megkapjuk, az iterációk során a képlet egyre pontosabb értéket ad az egyes csomópontokra. Nézzünk meg egy példát a PR érték kiszámítására: Tanulási ráta d=0.85 PR(A)=PR(B)=PR(C)=1
4. ábra - minta a PageRank számításához
16
Iteráció
PR(A)
PR(B)
PR(C) Összeg
0.
1
1
1
3
1.
1
1.85
0.15
3
2.
1.7225
1.1275
0.15
3
3.
1.108375
1.741625
0.15
3
4
1.63038125
1.21961875
0.15
3
...
...
...
...
...
30.
1.39539316985 1.45460683014 0.15
3
Kezdetben a kapott eredmények ingadoznak majd a számos iterációt követően megszületik a helyes eredmény. Minél több iterációt hajtunk végre annál pontosabb eredményt kapunk.
A keresés folyamata Amikor a felhasználó beír pár kulcsszót a Google oldalán akkor nem is gondolja, hogy a háttérben számos feladat hajtódik végre a másodperc tört része alatt, de mi is történik ilyenkor? A Google megnézi a beírt kulcsszavakat és kibővíti a keresési listát a szavak szinonimáját használva. Alapvető esetben a kereséskor a beírt kulcsszavak esetén a Google az ÉS műveletet, vagyis a metszetképzést veszi figyelembe, tehát elsődlegesen olyan találtatokat kínál fel, amelyekben minden kulcsszó szerepel. Természetesen ez nem minden esetben működik tehát a kulcsszavak találatokbeli előfordulása alapján is egy rangsort kell felállítania a keresőnek. A releváns találatok kikeresésének a folyamata: Organikus találati lista: ●
A Google megvizsgálja a lokalizációt, tehát hogy milyen nyelven és milyen országból keresünk, hiszen például a “foci” szó esetében Angliában és Amerikában is egy helyi lakosnak más sport jut az eszébe.
●
Következő lépésben megvizsgálja a személyes beállításokat és azt, hogy az adott IP címről vagy az adott Google fiókkal rendelkező személy a múltban milyen kereséseket futtatott le
●
Ezután a PageRank figyelembevételével előtérbe hozza az “erősebb” oldalakat
●
A keresés túl sok oldalt hoz fel, akkor tovább rangsorolja ezeket úgy hogy a minél frissebb, naprakészebb oldalak nagyobb súlyt kapnak
●
Az ugyanarról a domain névről származó magas találati súlyú oldalakat csoportosítja, ha minden egyes oldal magas súllyal rendelkezik
●
A fent felsorolt szűrők után elkészül a normál találati lista
17
A program felépítése A program felépítését a keresőmotorok logikája és működése ihlette az oldalak begyűjtésénél. A feldolgozás során pedig az szövegbányászati módszerek kerültek az előtérbe.
A rendszer felépítése:
5. ábra - A program felépítése
A programot négy fontosabb részre lehet osztani:
Dokumentumok begyűjtéséért és feldolgozásáért felelős alrendszer
Dokumentumok tárolásáért és távolságának meghatározásáért felelős alrendszer
Adattároló alrendszer
Térkép készítő és megjelenítő alrendszer
Alrendszerek bemutatása: Dokumentumok begyűjtéséért és feldolgozásáért felelős alrendszer:
Két fő osztályból áll Harvester és Refinery ez a két osztály felelős a weben található oldalak felderítéséért letöltéséért és feldolgozásért. Harvester: Az osztály a példányosítás során egy linket kér be, mely egy kiindulási pont. Ezen a kiindulási ponton keresztül egy szélességi kereséssel gyűjti be a weben található linkeket és tartalmukat.
18
A folyamat egy listát használ, mely melynek a végére beilleszti az újonnan talált linkeket, amennyiben a link már szerepel a listában, abban az esetben nem fog bekerülni a struktúrába. A linkek begyűjtésével párhuzamosan egy másik szálon elindul a az oldalak begyűjtése is. Refinery: Ez az osztály felelős a Harvester által begyűjtött linkek tartalmának a letöltésért és konvertálásáért sima egyszerű szöveges, plain text formátumba. Ez a folyamat lényegében egy egyszerű HTML to Text konverzió melyben a HTML tag-ek scriptek és stílusok eltávolításra kerülnek és csak a szöveg marad meg. A szótövező osztály segítségével itt történik meg a szavak egyszerűbb alakra történő hozása, ami után a STOPWORD szűrés következik. Ennek az eredményeként megkapjuk a tiszta és nyers szöveget.
6. ábra - Adatok begyűjtésének a folyamata
Stemmer: Ez az osztály felelős a szavak szótövezésért, körülbelül a leggyakoribb 100 000 szót tartalmazza a szószablya projektből, melyeket szerializálva perzisztens módon tárol. A központi adatszerkezet itt is egy Dictionary mely azonnali elérést biztosít a szótövező számára. Dokumentumok tárolásáért és távolságának meghatározásáért felelős alrendszer
Segédosztályok halmaza mely a dokumentumok fontosabb adatainak eltárolását illetve a köztük lévő távolságok meghatározását segíti. Document: Olyan segédosztály mely adatstruktúraként funkcionál, tárolja az egyes oldalak címét, ami egyedi azonosítóként funkcionál illetve az oldal szövegét, az oldalból kifelé mutató hivatkozások listáját valamint hogy az oldalt sikerült-e letölteni a begyűjtési folyamat során.
19
DocumentDistance: Az Euklideszi távolságmetrikát figyelembe véve kiszámolja az oldalak egymáshoz mért távolságát, és tárolja azokat a Storage osztály dokumentum távolság mátrixában. A távolságmérés a Storage osztály dokumentum mátrixa alapján történik, ahol a számítás a következőképpen zajlik: -
Az távolságszámító algoritmus kigyűjti a közös szavak listáját melyre kiszámolja a távolságmetrikát
-
Ha a két dokumentumban vannak eltérő szavak, akkor azokra a képlet 0-t és az eltérő szavak számosságát tartalmazná. Ez egy fölösleges négyzetre emelést és gyökvonást jelentene ezért a program egyszerűen a különbségek számosságát hozzáadja a távolság metrikához. √
2
2
=√
2
=
Adattároló alrendszer
Ez az alrendszer egyetlen osztály, a Storage osztályt tartalmazza. Az osztály lényege hogy a begyűjtött adatokat perzisztens módon tárolja, és az alkalmazásban ezek az adatok bárhol, és azonnal rendelkezésre álljanak. Storage: Feladata az adatok perzisztens tárolása, mely szerializáció segítségével valósul meg. A program indulásakor a már meg lévő adatok betöltődnek illetve a programból való kilépéskor, ha időközbe bővült az adatbázis, akkor az új adatokkal együtt lementésre kerülnek a már meglévő adatok. Az osztály a következő adatokat tárolja: -
Dokumentumok (URL, Dokumentumok szövege, Oldalból kimutató hivatkozások listája, Sikeresen letöltődött-e az oldal)
-
Bejárandó linkek listája (URL)
-
Dokumentum mátrix (A szavak dokumentumok szerinti előfordulásának számossága, URL illetve szavak szerint indexelve)
-
Dokumentumok távolságának mátrixa (Két oldal címével indexelve a két oldal közötti távolságot adja, Euklideszi távolság metrika szerint)
-
Számított távolság mátrix (A térképen elhelyezett pontok távolságának mátrixa)
-
Dokumentum pontok listája( A térképen megjeleníteni kívánt pontok listája, mely tárolja a pontok (x,y) koordinátáját, és a hozzá kötődő URL-t)
Térkép készítő és megjelenítő alrendszer
20
Ez az alrendszer felelős a térkép elkészítéséért és megjelenítéséért. Két osztályt tartalmaz mely az előbb említett két funkciót valósítja meg. ViewModel: Ez az osztály generálja le a megjelenítésre szánt dokumentum csomópontokat melyek az egyes dokumentumokat, weboldalakat szimbolizálják. Továbbá egy algoritmus a weboldalak távolsága alapján elkészíti a térképet, aminek konkrét működése egy másik fejezet tárgya. Drawing: A megjelenítésért felelős osztály mely kirajzolja, és méretezi a térképet. Ebben az osztály azonosítja a dokumentumokat koordinátájuk alapján mely a megjelenítés szempontjából fontos. DBSCAN: A dolgozatban bemutatásra kerülő általánosított DBSCAN algoritmus végrehajtásáért felelős osztály.
Térképkészítő algoritmus A weboldalak letöltése után a program kiszámolja a weboldalak egymáshoz viszonyított távolságát, ami az Euklideszi távolságmérési metrika alapján történik. Tehát kiindulási állapotként rendelkezésünkre állnak a weboldalak távolságai mátrixos formában: 𝐷1,1 [ ⋮ 𝐷𝑚,1
⋯ ⋱ ⋯
𝐷1,𝑛 ⋮ ] 𝐷𝑚,𝑛
ahol a mátrix oszlopai és sorai az egyes dokumentumok közötti távolságot szimbolizálják. Tehát a Di,j Az i. és a j. dokumentum távolságát szimbolizálja. Mivel a térképek kétdimenziósak szoktak lenni, illetve az emberi agy is kétdimenziós ábrákat preferálja legjobban ezért a készített térkép is síkban készült. Tehát az algoritmusnak készítenie kellett egydimenziós adatsorból egy kétdimenziósat. Így hát át kellett gondolni, hogy hogyan is lehet egy dimenziós adatokból kétdimenziósat csinálni. Ennél a pontnál a fizikából sikerült ötletet meríteni, a következő képen: Adott n darab pont a síkban melyeknek adott távolságokra kell elhelyezkedniük. Kezdetben a pontokat véletlenszerűen helyezzük el a síkba majd a pontok között a távolsággal arányos taszító illetve vonzó erő lép fel. -
Ha a pontok közötti távolság kisebb, mint az aktuális helyzetben akkor taszító erő
-
Ha pedig a pontok közötti távolság nagyobb, mint az aktuális helyzet akkor pedig vonzó erő
21
lép fel. Tehát a pontok közötti távolságokból erőket lehet számítani melyek a rendszer pontjait, elmozgatják. 𝑛
→ = ∑→ 𝐹𝑒
𝑖=0
𝐹𝑖
A pontokra gyakorolt eredő erők elmozdítják a pontot egy olyan helyre ahol az adott pont egyensúlyban van a többivel. De mivel n darab pontunk van ezért ezt minden egyes pontra meg kell ismételni. Mivel a korrekciók során a már beállított pontjaink is elmozdulnak, ezért az algoritmust addig kell ismételni, amíg az elmozdulásuk értéke egy kellően kicsi 𝜀 távolság alá csökken.
7. ábra - Dokumentumpontok árendeződése a kiszámított erők által
Az algoritmus működése: Adott: n darab dokumentum és azok távolságából képzett mátrix. Várt eredmény: n darab dokumentumhoz tartozó (x,y) koordináta a síkban Az algoritmus működéséhez szükségünk van a valós távolságokra, melyet a dokumentumok tartalom szerint meghatározott távolsága ad meg, ez az algoritmus egyik bemenő adata, mely egy mátrix a továbbiakban jelöljük TR-et (azaz a valós távolságok mátrixa). 𝐷1,1 𝑇𝑅 = [ ⋮ 𝐷1,𝑚
⋯ ⋱ ⋯
𝐷1,𝑛 ⋮ ] 𝐷𝑚,𝑛
Di,j Az i. és a j. dokumentum távolságát szimbolizálja. Továbbá szükség van a TS mátrixra is mely a pontok síkban lévő aktuális távolságát mutatja, azt a távolságot az (x,y) koordináták segítségével szintén az Euklideszi távolság metrika alapján számítjuk. 𝑆1,1 𝑇𝑆 = [ ⋮ 𝑆1,𝑚 22
⋯ ⋱ ⋯
𝑆1,𝑛 ⋮ ] 𝑆𝑚,𝑛
Si,j Az i. és a j. Dokumentum távolságát szimbolizálja. Végül szükségünk van az erőhatásokat szimbolizáló TC-re azaz a korrekciós mátrixra mely a TR és a TS közötti távolság arányát, vagyis az egymásra ható erőket mutatja. Kiszámítása: 𝐷1,1 𝑆1,1
𝑇𝑅 =
⋮
𝐷1,𝑚
[ 𝑆1,𝑚
⋯ ⋱ ⋯
𝐷1,𝑛 𝑆1,𝑛
⋮
𝐷𝑚,𝑛
𝑆𝑚,𝑛 ]
𝐶1,1 =[ ⋮ 𝐶1,𝑚
⋯ 𝐶1,𝑛 ⋱ ⋮ ] ⋯ 𝐶𝑚,𝑛
Ci,j Az i. és a j. dokumentum közötti korrekció mértékét szimbolizálja. Ha Ci,j < 1 akkor a jelenlegi távolság túl nagy ezért az algoritmus csökkenti a távolságot. Ha Ci,j>1 akkor a jelenlegi távolság túl kicsi ezért az algoritmus növeli a távolságot. Ha Ci,j = 1 akkor nem kell korrigálni az aktuális távolságot. Az algoritmus működése során a pontok mozgását legjobban a TC mátrix korábbi illetve aktuális elemenkénti összegének különbsége mutatja, ha ez a távolság elér egy küszöbértéket, akkor az algoritmus leáll. Vagyis a Leállási feltétel: ∑ 𝒊 ∑ 𝑗 𝑇𝐶𝑒𝑙ő𝑧ő – ∑ 𝑖 ∑ 𝑗 𝑇𝐶𝑎𝑘𝑡𝑢á𝑙𝑖𝑠 < 𝜀 akkor az algoritmus leáll. Az algoritmus működése: DO { FOR (i: 0 -> n) { TS kiszámítása; FOR (j:0-> n) TC kiszámítása; Pontok korrigálása a TC mátrixszal: HA (i!=j) AKKOR { x[j]=(x[i]-x[j])* TC[i,j]; y[j]=(y[i]-y[j])* TC[i,j]; } } 23
} WHILE (∑ 𝒊 ∑ 𝑗 (𝑇𝐶𝑒𝑙ő𝑧ő ) – ∑ 𝑖 ∑ 𝑗 (𝑇𝐶𝑎𝑘𝑡𝑢á𝑙𝑖𝑠 ) < 𝜀)
Az algoritmus költsége: C = 2n3+n2 Az algoritmus hatékonyságágának növelése: Mivel az algoritmus mátrixokkal dolgozik ezért a számítási költség a legegyszerűbb esetben is négyzetes. Mivel az algoritmushoz felhasznált mátrixok négyzetesek és a főátlóra szimmetrikusak ezért: Az algoritmus hatékonyságának számításköltségének csökkentése érdekében elég csak a főátló feletti elemeket kiszámítani azt algoritmushoz, hiszen a főátló alatti részek ugyanazok. Az algoritmus új költsége: 𝐶 =
2𝑛3 +𝑛2 2
Webes tartalom klaszterezése A TDK dolgozat írása során igényként felmerült az adatok gépi csoportosítása, avagy klaszterezése. Mivel nagy adatmennyiségeknél átláthatatlanná válnak az adatok. Ezért elengedhetetlen az adatok klaszterezése a könnyebb áttekinthetőség végett. Ha a felhasználó egy adott témában keres a dokumentum vektortér modell távolságmetrikájával, és a klaszterezés segítségével könnyen megtalálhatja a számára fontos adatokat, oldalakat. A klaszterezés koncepciója hogy a hasonló dokumentumokat egy csoportba igyekszik gyűjteni. Két dokumentum esetén pedig minél több a közös sző a két dokumentumban annál hasonlóbbak, és annál kisebb a távolságuk az adott dokumentumoknak. Mivel a webes adatok nagyon heterogének ezért olyan klaszterezési eljárást kellett választani, amely képes az egyéni klaszteralakzatok felismerésére illetve a zajok kezelésére is. A választásom a sűrűség alapú klaszterező eljárásokra esett melyek képesek az egyéni klaszteralakzatok felismerésére, és a zajok kezelésére is.
24
Ezen elvű algoritmusok közül a DBSCAN algoritmusra esett a választás a működési hatékonysága és jó klaszterezési képességi miatt.
DBSCAN algoritmus bemutatása Az algoritmust 1996-ban fejlesztették ki nagyméretű zajos adatbázisok klaszterezésérexiv. Ez egy sűrűség alapú eljárás mely a dokumentumok vektortérbeli sűrűségén alapszik, vagyis ahogy a sűrűségük (távolságuk) alapján összefüggő dokumentum csoportokat észlel, azokat egy klaszterbe sorolja.
8. ábra - Egyedi klaszteralakzatok felderítése DBSCAN algoritmus segítségével
Az algoritmus működéséhez elengedhetetlen két fontos paraméter megadása: -
EPS legnagyobb megengedett dokumentumtávolság
-
Minimum Points (MinPtr) magelem minimális szomszédsága
Az algoritmus fontosabb elemei -
Magelem: olyan elem melytől EPS távolságra legalább MinPts számú pont található.
-
Közbenső elem: a magelemből kiinduló egymástól legfeljebb EPS távolságba pontok halmazának egy eleme.
-
Szélső elem: a magelemtől EPS távolságon belőli pontok láncolatán elérhető olyan elem, amelyből már más elemre nem indul hivatkozás.
-
Külső elem: olyan elem, amely az megadott paraméterek alapján nem sorolható semmilyen csoportba, azaz zaj.
Az algoritmus tulajdonságai: Előnyök:
nem használ rácsot a sűrűség meghatározásához
25
gyors, és alacsony számításigény
tetszőleges alakzatok felismerése
zajok hatékony kezelése, szűrése
EPS és MinPts paraméterek körülményes meghatározása
Egyenletes eloszlású minta esetén egy klaszterbe olvaszt, vagy mindent
Hátrányok:
különálló klaszternek (azaz zajnak)
Az algoritmus működése: -
A csoportosítandó elemek átvizsgálása magelemek után kutatva
-
Magelemek ellenőrzése EPS és MinPts alapján
-
Magelemhez tarozó csoportok kiépítése, a magelemből kiindulva, EPS távolságonkénti pontok beolvasztásával
Pszeudo kód: DBSCAN(D, EPS, MinPtr) C=0 //Klaszter sorszáma ForEach (P in D) MagelemekKeresése(P,D,Eps,MinPtr, C) SzomszédokKeresése(P, D, Eps) Gyűjtsük ki P azon szomszédait D-ből melyek kissebbek EPS-től MagelemekKeresése(P,D,Eps,MinPtr, C) N=SzomszédokKeresése(P, D, Eps) Ha Méret(N)>=Minptr akkor C=C+1; megjelölés magelemként (C indexel) a klaszter elemeinek rekurzív kigyűjtése, a magelemből kiindulva
Az algoritmus költsége: 𝑂( ∙ o ( )
26
DBSCAN paramétereinek dinamikus meghatározása A klaszterezés során általános problémaként jelentkezik, hogy az adott dokumentum vektortérben lévő elemeket hány csoportra, klaszterre osszuk fel. Mivel a döntés nem hozható meg abszurd módon ezért számos technika és ötlet született ennek a meghatározására. Az első és legegyszerűbb megoldás a klaszterezési „ököl” szabályxv, azaz egy adott vektortérben a klaszterek száma az alábbi képlettel határozható meg: 𝑘≈ √
2
Ez a képlet viszonylak jó iránymutatás a klaszterek számának meghatározására. Mivel ez az szabály csak egy durva közelítést ad, ezért számos más ötlet is született a megfelelő klaszterszámok meghatározására. Egy másik elterjedt koncepció a „Elbow method”xvi a nevét a klaszterezés során készített diagram alakjáról kapta.
9. ábra - Elbow method szemléltetése
A görbe egy íj húrjára hasonlít ahol az optimális klaszterszámot a görbében bekövetkezett törés adja meg. (Ahol feszítik a „húrt” ott vannak az ideális paraméterek.)
27
DBSCAN algoritmus általánosítása A DBSCAN algoritmus működéséhez két paraméter beállítása kulcsfontosságú. Ezeknek a paramétereknek az értéke határozza meg a klaszterek számát. Ha egy függvényként tekintünk, a két paraméterre az alábbi határértékelet kapjuk
Eps
Minimum Points (Minpts)
Klaszterek száma
Megjegyzés
0
>0
0
Azaz minden pont zaj lesz.
0
=0
n
Azaz minden pontból klaszter lesz
0 ≤ Minpts < n
1
Egy nagy klaszterré olvadnak össze a pontok
A kérdés tehát e határok között hogyan tudjuk megadni az algoritmusnak a lehető legoptimálisabb paramétereket. A legkézenfekvőbb megoldás az optimális klaszterszám eléréséhez az algoritmuskülönböző paraméterekkel történő futtatása. A paramétereket a hatékonyság érdekében a lehető legszűkebb tartományban kell tartani. De mik is ezek a tartományok: Min(Vektortér elemei)<Epsilon<Max(Vektortér elemei) 0<Minimum points
Az iteratív keresés folyamata
Ahhoz hogy ez kétparaméteres algoritmust a paramétereitől függetlenné tudjuk tenni számos iterációt, kell lefuttatni a fent definiált tartományok között. 28
Az iteratív keresés jóval megnöveli a költséget, de cserébe meghatározza a két ismeretlen paramétert az Epsilon-t és a MinPts-t. A keresés költségét leginkább befolyásoló tényező az Epsilon léptékének a meghatározása. Ennek az étéknek a nagysága után lehet felderíteni az egyes klasztereket. A lépték 1000 iteráció esetén már jó közelítést ad az adott problémára. Az iteratív keresés előtt fontos meghatározni néhány elemet melyek segítik a hatékony működést. Ezek az elemek: -
Legkisebb távolság a dokumentum távolságok mátrixában
-
Legnagyobb távolság a dokumentum távolságok mátrixában
-
𝑛 𝑘
ami a klaszterezési ökölszabály alapján kapható meg
A keresés során minden egyes iterációban lefuttatjuk a DBSCAN algoritmus majd kigyűjtjük annak az értékeit. Az iterációk számát a két paraméter szerint futtatjuk: Az Eps paramétert a legkisebb és legnagyobb távolságérték között léptetjük a következő léptékkel: 𝑙 𝑝𝑡 𝑘 =
max(𝐷𝐷𝑀) − min(𝐷𝐷𝑀) 𝐼𝑡𝑒𝑟á𝑐𝑖ó𝑠 𝑓𝑒𝑙 𝑜 𝑡á𝑠
Ahol a DDM: Document Distance Matrix azaz a dokumentumok távolságának mátrixa A MinPts paramétert pedig 1-től a 𝑘 - ig léptetjük Hogy további hatékonyságbeli javulást érjünk el azt algoritmus futtatása során, definiálnunk kell egy fontos feltételt, ami az esetleges zsákutcákat kizárja a keresésből. Ez a probléma a nem megfelelően megválasztott paraméterek esetén az algoritmus egy nagy szuperklaszterbe igyekszik olvasztani a pontokat. Ha ezeket a feltételeket teljesítünk, akkor a keresési algoritmus költsége jelentős mértékben redukálható. Ilyen feltétek mellett a költség közel azonos az iterációk számával. ~ 𝑖𝑡𝑒𝑟á𝑐𝑖ó𝑠 𝑓𝑒𝑙 𝑜 𝑡á𝑠 ∙ 𝑂( ∙ o ( ) 29
Algoritmus: IterativeSearch(resolution) FOR MinPts1..(n/k) lépték:1 FOR EPS Min(DDM)..Max(DDM) Lépték: Max(DDM)-Min(DDM)/Resolution DBSCAN(D, Eps, MinPts) Klaszterezési adatok kigyűjtése Belső ciklus leállási feltételeinek vizsgálata Leggyakoribb klaszterméret megkeresése Visszatérés a leggyakoribb klaszterméret paramétereivel.
A DBSCAN algoritmus használata során a tapasztalatok azt mutatják, hogy azt iteratív keresés során a klaszterek számának az alakulása normál eloszlást követ. Ez az eloszlás függ az elemek számától illetve az iteratív keresés léptékétől.
10 000 kisérlet elvégzése után kapott gyakoriságok eloszlása 3000 2500 2000 1500 1000 500 0 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 10. ábra - klaszterek számának gyakorisági eloszlása
Az ábrán látható diagram X tengelye a klaszterek számát mutatja, míg az Y tengely pedig az egyes klaszterek esetén hány iterációban jött ki az adott klaszterszám. 30
Jelen diagram egy 72 elemű mintahalmazról készül, amelynél jól látszik, hogy a klaszterezési ökölszabály jól közelíti a klaszterek számát. 72 √ =6 2 A különböző minták klaszterezése során arra a következtetésre jutottam hogy minél finomabb léptéket választok Epszilonnak az iteratív keresés során a fent definiált tartományban, annál a kapott statisztika annál jobban közelíti az ökölszabály szerint kapott értéket.
Az elkészült program hatáskörének elemzése Az elkészült program segítségével jól átláthatóvá válnak az egyes oldalak kapcsolati illetve tartalombeli viszonyai. Ezáltal nem csak egy kulcsszavak alapján történő szűrést lehet elvégezni, hanem vizuálisan az oldalak tartalombeli viszonya is jól látszik. Ezáltal kivallóan szemléltetve az egyes oldalak hasonlóságát illetve távolságát. A vizualizáció lévén könnyedén meg lehet határozni a tartalombeli határokat, a térkép segítségével, mely nagyban segíti az adott tématerület iránt érdeklődő felhasználóknak a további témához tartozó oldalak megtekintését, felderítését. A webtérkép szempontjából kétféle hatáskört kell megvizsgálni: -
az egyik a lokális (azaz a site-ok szintjén történő térképkészítés)
-
globális (azaz egy nagy kiterjedésű „internet méretű” térkép készítési )
feldolgozási szintet kell megvizsgálnunk. A lokális szinten történő elemzés tipikusan egy site-ra vonatkozik, azaz egy weboldal aloldalainak viszonyát deríti fel. Ebben az esetben az elemzés világosan megmutatja,
31
11. ábra - szemléltető kép a programból
hogy az adott oldal mennyire homogén illetve milyen tartalomterületekre különöl el, és melyek azok az oldalak, amik nem illenek ezekbe a tartalmakba. Azonban nem csak a nem odaillő oldalakat vizsgálhatjuk meg, hanem például az egyes oldalkategóriák kialakítását is jól támogathatjuk a webtérkép segítségével. Alapesetben egy nagyméretű portálnál mindig is problémát jelent a megfelelő navigációs kategóriák meghatározása illetve azok megfelelő alkalmazása. Ám ha vizuálisan jól elkülöníthető csoportokat látunk a térképen, az egyértelműen jelzi, hogy hol vannak az egyes tartalombeli kategóriák határai. További rejtett összefüggések tárhatók fel ilyen módon a DBSCAN algoritmus használatával, melynek segítségével automatikusan meghatározásra kerülnek az egyes csoportok, vagyis leendő kategóriák. A globális alkalmazási hatáskör igen nagy kihívást jelent, mivel hatalmas mennyiségű adat áll a rendelkezésünkre. Egyetlen megkötés talán az, hogy a tatalom alapú metrika csak egy adott nyelven belül működik megfelelőn. Tehát többnyelvűség esetén az elemzés nem megfelelően fog működni. Mivel akár mennyire is különbözőek két nyelv szavai mimig lesznek olyan alaki átfedések melyeket a rendszer félreértelmez illetve minden nyelvhez másfajta szótövezőt kell alkalmazni. További problémát jelent még hogy egy adott nyelvterületű weboldalak száma hatalmas, ami hihetetlen mértékű tárkapacitást és számítási erőforrást igényel egy webtérkép elkészítéséhez.
32
Csak a magyar nyelvű .hu domain Google által ismert oldalainak a száma közel 100 millió oldalt számlál, amiből egyenesen következik, hogy egy ilyen méretű térkép készítéséhez hihetetlen nagy erőforrásokra van szükség, melyet egy normál teljesítményű asztali gép nem tud kiszolgálni, vagy ha igen akkor hihetetlenül magas számítási idő és tárterület árán, ami pedig elrontja az adatok naprakészségét. Közelítő számítások egy magyar nyelvű webtérkép elkészítéséhez: A .hu domain alatt 98 400 000 oldal találhatóxvii A weben található oldalak átlagos mérete 320KBxviii Ebből következik, hogy egy ilyen térkép tárigénye: 29.32 TB
Konkrét példa a webtérkép alkalmazására A program szemléltetését, a Miskolci Egyetem: Általános informatikai tanszékxix honlapjának feltérképezésével és kielemzésével mutatom be. Ahogyan az ábrákból is jól látszik egy erősen központosított oldalról van szó, melynél a hivatkozások egy oldalba futnak be, ez az oldal pedig a főoldal. Ez egy egyszerű és erős koncepció miszerint a felhasználó mindent el tud érni a főoldalról, ám a nagy hátránya hogy egy oldalon, a rengeteg hivatkozás átláthatatlanná teszi a rendszert.
További megfigyelésként az látszik, hogy az oldal viszonylag egységes, homogén tartalmat mutat az oldalak többségét nézve. Ez az egység a keresőmotorok rangsoroló algoritmusának szempontjából is előnyös, hiszen a keresőmotoroknál nagyban számít az oldal egységes tartalma, ami a találati listán történő előrelépést jelent. A központi tartalmak egy egységben koncentrálódnak, melyből csak az eltérő tartalmú oldalak térnek el. Ezek az oldalak a következőek: Munkatársak: Ez az oldal csak egy képet tartalmaz, melynél az oktatók fejére kattintva el lehet érni az az oktatók oldalait. Az informatikai intézet szolgáltatásai: az informatika intézet szolgáltatásait bemutató aloldal Számítógép terem használati szabályok: a termek használati szabályai. Info klub: ezeknél a tartalmaknál jól látszik, hogy
33
eltérnek a tanszék általános dokumentumaitól, tehát ezeket érdemes egy külön kategóriába kiemelni. Továbbá az oldal az alábbi kulcsszavakra fókuszál, ezek szerepelnek a belső magban: start infoklub wagner kérdés g anyag ősz page általános 5 projektorok sz projekt tavasz miskolci információ 2009 foglaltsága z feladatok geial337b egyetem történet informatikus oktatók mészáros szakdolgoza 2008 gépészmérn alapítvány bsc kutatók m tok 2007 öki hírek gyakorlat oktatók répási komplex tdk kar esemény téma doktorandus salánki feladat kutatási doktori 2010 laborok zok j éves projektek iskola barabás felszereltség rendszergaz gy diplomamun fejlesztési neptun elek szolgáltatás dák tanáraink kák munka iit halász használati demonstráto tóth msc szaktanács mail hadházi szabályzat rok drótos szakmai szervezeti home kocsis in102 baksáné d gyakorlat működés tanszék kovács órarendje e vincze szigorlat ergo munkatárs krizsán in103a p é záróvizsgák bibamus oktatás mileff in103b t képzés felvételi kép kutatás pance in104 ficsór tárgy záróvizsga galériák hallgató smid faq l kiírások műsz oktatási kapcsolat szűcs gyakori kecskeméti letölthető inf cég Ezekre a szavakra mindenképpen kilelhet hegyezni egy estleges keresőoptimalizálást azaz SEOxx-t. A keresőszavakból jól látszik hogy az oldal tartalma teljes mértékben lefedi a a hozzá tartozó tanszéket. Azaz szerepelnek az ott dolgozó munkatársak nevei, a fontosabb feladatok, tárgyak, termek…stb. Vagyis az oldalon lényeges információk találhatóak meg, fölösleges nem odaillő tartalmak pedig nem. Az oldal homogenitás szempontjából is egységes képet mutat, tehát tartalmilag egy jól felépített oldalról van szó. A program támogatja továbbá a kulcsszavakra történő szűrést is.
12. ábra - Kulcsszavakra történő szűrés a program segítségével
Valamint a dokumentumok közös tartalomi metszetének előállítását: 34
13. ábra Tartalmi metszetek kiértékelése
Összegzés, kitekintés A tartalom alapú webtérkép egy jövőbeli kereséséi alternatíváját körvonalazza elénk, egy tisztán tartalom alapján történő összefüggések, és tartalmi távolságok alapján készült webtérkép nagyban megkönnyítené az internetes oldalak közötti navigációt és a web tartalmi áttekintését. Ám mivel az internet méretei túlmutatnak egy normál asztali számítógép kapacitásán, sőt egy fejlettebb szerver feldolgozási képességein is, ezért csak a Google-höz hasonló számítási és tárkapacitási igényekkel rendelkező cégek lesznek csak képesek egy ilyen webtérkép megvalósítására. Addig is a webtérkép alkalmazása csak kisméretű problématerek kezelésére lesz elegendő, mint például oldalak tartalmi összefüggéseinek, homogenitásának vizsgálata. Ez igencsak kis szelete az internetnek, ám mégis sok rejtett összefüggés és következtetést tudunk levonni az egyes oldalak elemzése által. Melyek nagyban megkönnyítik az oldalt szerkesztő személyek munkáját. A webtérkép jelenlegi formájában egyfajta eszközként, toolként szolgálhat a web helyek szerkesztőinek, adminisztrátorainak, hogy oldalukat hogyan tudnák minél jobban egységesíteni és az egyes kategóriákat-szekciókat kialakítani. További használati alternatívaként megemlíteném, hogy a térkép kiválóan alkalmas egy modern oldaltérkép készítésére, mely nemcsak az elérhető oldalakat hanem azok tartalmi viszonyait is ábrázolja. A TDK dolgozat további produktuma a DBSCAN algoritmus automatizálása, mely számos helyen kiválóan alkalmazható, bonyolultan meghatározható klaszterezési paraméterek nélkül. Tökéletes alternatívát jelentve zajos összetett adathalmazokra. 35
Függelék
14. ábra - Képek a programból 1.
15. ábra - Képek a programból 2.
36
Képek és ábrák jegyzéke
1. ábra – szavak előfordulásának tárolása dokumentumbeli pozíció nélkül ............................ 10 2. ábra – szavak előfordulásának tárolása dokumentumbeli pozícióval .................................. 10 3. ábra - Hash tábla működése ................................................................................................. 11 4. ábra - minta a PageRank számításához ................................................................................ 16 5. ábra - A program felépítése .................................................................................................. 18 6. ábra - Adatok begyűjtésének a folyamata ............................................................................ 19 7. ábra - Dokumentumpontok árendeződése a kiszámított erők által....................................... 22 8. ábra - Egyedi klaszteralakzatok felderítése DBSCAN algoritmus segítségével .................. 25 9. ábra - Elbow method szemléltetése ...................................................................................... 27 10. ábra - klaszterek számának gyakorisági eloszlása .............................................................. 30 11. ábra - szemléltető kép a programból ................................................................................. 32 12. ábra - Kulcsszavakra történő szűrés a program segítségével ............................................. 34 13. ábra Tartalmi metszetek kiértékelése.................................................................................. 35 14. ábra - Képek a programból 1. ............................................................................................. 36 15. ábra - Képek a programból 2. ............................................................................................. 36
37
Irodalomjegyzék, Hivatkozások Könyvek:
[ 1.]
Tikk Domonkos: Szövegbányászat
[ 2.]
Trey Nash C# 2008
[ 3.]
SAMS: Joe Mayo C# 3.0 with the .NET Framework 3.5
[ 4.]
Kovács László: Adatelemzési és adatbányászati módszerek jegyzet
[ 5.]
Kovács László: Szövegbányászat és dokumentumkezelés
Internetes források:
[ 1.]
http://www.googleguide.com/google_works.html
[ 2.]
http://ppcblog.com/how-google-works/
[ 3.]
http://www.google.com/howgoogleworks/
[ 4.]
http://www.microsoft.com/net/
[ 5.]
http://dev.mysql.com/doc/
[ 6.]
http://mokk.bme.hu/projektek/szoszablya
[ 7.]
http://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set
[ 8.]
http://en.wikipedia.org/wiki/DBSCAN
38
Hivatkozások: i
http://en.wikipedia.org/wiki/SMART_Information_Retrieval_System
ii
Tikk Domonkos: Szövegbányászat
iii
http://szovegbanyaszat.typotex.hu/content/html/ch2zipf/ch2zipf.html
iv
http://tartarus.org/~martin/PorterStemmer/
v
http://en.wikipedia.org/wiki/Stopword
vi
http://www.ranks.nl/stopwords/hungarian.html
vii
http://en.wikipedia.org/wiki/Bitmap_index
viii
Information Retrieval: Implementing and Evaluating Search Engines. Cambridge
ix
Kovács László: Adatbázisok tervezésének és kezelésének módszertana
x
http://msdn.microsoft.com/en-us/library/xfhwa508.aspx
xi
Tikk Domonkos: Szövegbányászat
xii
http://www.googleguide.com/google_works.html http://ppcblog.com/how-google-works/ http://www.google.com/howgoogleworks/
xiii
http://www.webworkshop.net/pagerank.html
xiv
http://rgm2.lab.nig.ac.jp/RGM2/R_man-2.9.0/library/fpc/man/dbscan.html
xv
Kanti Mardia et al. (1979). Multivariate Analysis. Academic Press
xvi
Kanti Mardia et al. (1979). Multivariate Analysis. Academic Press
xvii
http://www.google.hu/search?sourceid=chrome&ie=UTF-8&q=site:.hu
xviii
http://searchengineland.com/google-web-report-average-page-size-320-kb-46316
xix
http://www.iit.uni-miskolc.hu/iitweb/opencms/department/index.html
xx
http://www.seotools.hu/
39
