Dolovanie dát v prostredí hypertextu

Michal Petrov

 

Slovenská technická univerzita, Fakulta informatiky a informačných technológií
Ústav informatiky a softvérového inžinierstva
Ilkovičova 3, 842 16 Bratislava, Slovenská republika
mpetrov at ynet.sk

 

Spracované podľa:Soumen Chakrabarti. Data mining for hypertext: A tutorial survey. Indian Institute of Technology Bombay. Januar 2000.

Abstrakt.
Internet patrí medzi najvýznamnejšie zdroje informácií na svete, pričom väčšina týchto informácia je uložená v podobe hypertextových dokumentov. S narastajúcim počtom webových stránok stúpa aj náročnosť vyhľadania požadovaných informácií. Vyhľadávanie informácií len podľa výskytu zadaného výrazu, je pri takomto veľkom množstve stránok neefektívne a často neprináša uspokojivé výsledky. Tu nachádzajú svoje uplatnenie systematickejšie a komplexnejšie prístupy ako sú dolovanie dát a strojové učenie sa pre hypertext.

Abstract
Internet is one of the most important sources of information of today. Most of the information on internet is stored in hypertext documents. With rapid growth of new web pages the severity of finding right information is raising. Looking for information only by the occurrence of an expression in a document is not enough effective enough and the result are not satisfying. Data mining and machine learning have a significant role to play in this situation.

 

Obsah

 

1 Úvod

Počet webových stránok na Internete už presiahol jeden trilión a neustále narastá. Internet patrí medzi najvýznamnejšie zdroje informácií na svete. Avšak s narastajúcim počtom stránok stúpa aj náročnosť vyhľadania požadovaných informácií. Základným prístupom pri hľadaní informácií na internet je používanie internetových vyhľadávačov a využívanie hypertextových odkazov. Tento prístup je však neefektívny a často neprináša uspokojivé výsledky. Tu nachádzajú uplatnenie systematickejšie a komplexnejšie prístupy ako sú dolovanie dát a strojové učenie sa.

Tento článok popisuje rôzne prístupy k strojovému učeniu a dolovaniu dát v hypertextových dokumentoch, medzi ktoré patria aj webové stránky. V prvej časti sa zameriava na popis modelov, ktoré sa používajú na reprezentáciu znalostí získaných z týchto dokumentov. Následne sú popísané rôzne prístupy k dolovaniu dát ako kontrolované učenie, nekontrolované učenie a čiastočne kontrolované učenie.

Množstvo neštruktúrovaného textu a hypertextu vysoko prevyšuje množstvo štruktúrovaných dát. Hypertextové dokumenty sa používajú už pomerne dlho, avšak až s príchodom internetu a webových stránok došlo k ich masívnemu rozšíreniu. Počet webových stránok je tak vysoký, že aj najväčšie internetové vyhľadávače ako sú google.com alebo yahoo.com indexujú len niekoľko percent z celkové počtu týchto stránok.

Tvorba webových stránok nepodlieha nijakým centrálnym pravidlám, ktoré by presne predpisovali ich štruktúru, tak aby sa v nich dali jednoducho vyhľadávať znalosti. Práve naopak, mnoho autorov zámerne umiestňuje na svoje stránky aj slová, ktoré nemajú s informáciami na stránke nič spoločné, aby tak oklamali internetové vyhľadávače. Ich cieľom je dosiahnuť vysoké hodnotenie svojej stránky pre mnoho vyhľadávacích dotazov. To isté platí aj pre hypertextové odkazy na stránka. Mnohé z nich sú zavádzajúce. To ešte viac komplikuje vyhľadávanie relevantných informácií v hypertextových dokumentoch.

Základ vyhľadávania v hypertextových dokumentoch je podobný ako vyhľadávanie znalosti v textových dokumentoch. Vyhľadávanie v textových dokumentoch sa potyká s problémami ako sú napríklad synonymá alebo slová s viacerými významami. Tieto nedostatky sa ešte viac prejavu pri vyhľadávaní znalostí v hypertexte. Hypertextové dokumenty navyše oproti textovým dokumentom vnášajú do vyhľadávania znalostí ďalší rozmer: hypertextové dokumenty predstavujú čiastočné štruktúrované dáta, ktoré môžeme zobraziť ako orientovaný graf. Jednotlivé stránky sú reprezentované ako uzly grafu a odkazy predstavujú hrany grafu.

2 Základné modely pre reprezentovanie znalostí

V tejto kapitole budú popísané základné modely vhodné na reprezentáciu znalostí pre text, hypertext a čiastočne štruktúrované dáta.

Modely pre text

Najjednoduchším modelom na reprezentovanie znalostí získaných z textových dokumentov je takzvaný vektorový priestorový model [2]. Postup pri tvorbe tohto modelu je nasledovný:

  1. rozdelenie dokumentu na tokeny pomocou oddeľovačov (medzera, bodka, čiarka ...)
  2. konverzia tokenov do kanonickej formy (napr. "mala", "má", "mal", "majú" sa prevedú na "mať")
  3. každý kanonický token potom predstavuje jeden rozmer (os) v euklidovskom priestore.
Dokumenty sú v tomto modely reprezentované ako vektory v takto vytvorenom priestore. Pričom ak sa token t vyskytuje n(d,t) -krát v dokumente d, tak t-tý koordinát dokumentu d má hodnotu n(d,t). Príklad vektorového priestorového modelu je na obrázku 1. Model zobrazuje jednoduchý dokument, ktorý ma len dva typy slov "Dom" a "Auto", pričom slovo "Dom" sa vyskytuje v dokumente dvakrát a slovo "Auto" trikrát. Dokument je reprezentovaný vektorom vyznačeným červenou farbou.

Obrázok 1 : Vektorový priestorový model

Avšak takáto reprezentácia nezohľadňuje skutočnosť, že niektoré slová ako napríklad "algebra" majú väčší význam ako napríklad slová "mať" alebo "byť", ktoré sú pomerne bežné a vyskytujú sa v každom dokumente viackrát. Ak sa token t vyskytuje v Nt dokumentoch z N, tak potom Nt/N určuje jedinečnosť respektíve dôležitosť daného tokenu.

Tento príklad predstavuje jednoduchý model na reprezentáciu znalostí v textovom dokumente, ktorý ale nijako nezohľadňuje gramatiku a sémantické pravidlá použitého jazyka ani vzťahy medzi jednotlivými tokenmi. Aj napriek týmto obmedzenia je tento model postačujúci a spĺňa základné požiadavky na dolovanie znalostí z textových dokumentov.

Modely pre hypertext

Hypertextový dokument obsahuje navyše oproti textovému aj odkazy na ďalšie dokumenty. Tie sa zvyknú modelovať do rôznych úrovni podrobnosti v závislosti od použitia daného modelu. Najjednoduchší model na modelovanie hypertextu je orientovaný graf (D,L), kde D je množina uzlov - dokumentov a L je množina hrán - odkazov. Jednotlivé uzly môžu predstavovať modely pre text. Zložitejšie modely používajú aj algoritmy, na zistenie vzťahov medzi jednotlivý uzlami. Napríklad medzi stránkami o motorizme je navzájom viacej odkazov ako napríklad medzi stránkami o motorizme a maľovaní.

3 Učenie s učiteľom

Učenie s učiteľom (supervised learning) sa nazýva aj klasifikácia. Vstupom pre tento typ učenia je množina dát, ktoré sú označené podľa toho do akej triedy (skupiny) patria. Počet tried je konečný. Vo fáze trénovania sa algoritmus učí na takto označených dát. Po správnom natrénovaní potom algoritmus dokáže správne klasifikovať aj neoznačené dáta.

Pravdepodobnostný model

Majme m tried označených c1...cm. Každej triede je priradená množina označených dokumentov Dc určených na trénovanie. A T je množina všetkých výrazov (slovník), nachádzajúcich sa v trénovacích dokumentoch. Pre výpočet pravdepodobnosti, že dokument d patrí do triedy c potom platí vzťah

kde Φc,t je pravdepodobnosť, že v dokumente z triedy d sa výraz t nachádza aspoň raz. Tento model sa nazýva naivný Bayesov model [3]. Naivný preto, lebo nezohľadňuje vzťahy medzi jednotlivými výrazmi. Jeho nevýhodou je, že znevýhodňuje krátke dokumenty, pretože pre krátke dokumenty je počet slov v dokumente (|t|) výrazne menší ako počet slov v slovníku (|T|).

4 Učenie bez učiteľa

Vstupom pre učenie bez učiteľa v hypertexte je množina hypertextových dokumentov. Cieľom učenia je nájsť hierarchiu v týchto dokumentoch na základne určitých podobnosti a usporiadať dokumenty podľa nájdenej hierarchie. Na nájdenie hierarchie sa používajú klastrovacie algoritmy. Úlohou klastrovacieho algoritmu je zoskupiť podobné dokumenty do akéhosi zhluku. Klastrovanie sa používa na zlepšenie vyhľadávania a prezerania hypertextových dokumentov ako aj na lepšiu vizualizáciu vzťahov medzi jednotlivým hypertextovými dokumentmi. Príkladom klastrovacieho algoritmu je K-means klastrovací algoritmus [4].

K-means klastrovací algoritmus

Klaster je skupina objektov, ktoré sa natoľko podobajú, že ich možno reprezentovať jedným objektom - centrom klastra. Cieľom klastrovacieho algoritmu je nájdenie centier klastrov a priradiť jednotlivé objekty do príslušných klastrov. Je dôležité, aby sa dal každý objekt popísať nejakou metrikou. Rozdiel týchto metrík potom určuje vzdialenosť medzi dvoma objektmi. V našom prípade jednotlivé objekty predstavujú hypertextové dokumenty.

K-Means klastrovací algoritmus je význačný tým, že počet centier je explicitne určený. Jeho cieľom je rozdeliť objekty medzi K klastrov tak, že vzdialenosť medzi všetkými objektmi a ich centrami je minimalizovaná.

K-Means klastrovací algoritmus:

  1. Z priestoru klastrovaných objektov náhodne vyberieme K objektov, tie budú reprezentovať centrá klastrov.
  2. Priradíme každý objekt k tomu klastru, ktorého centrum je k nemu najbližšie.
  3. Prepočítame nové centra klastrov takým spôsobom, že vzdialenosť medzi všetkými objektmi klastra a novým centrom klastra bude minimalizovaná.
  4. Opakujeme kroky 2 a 3 pokiaľ sa centra klastrov menia.

Pre úplnosť je potrebné dodať, že existujú aj klastrovacie algoritmy, ktoré si počet klastrov zistia samé. Medzi takéto algoritmy patrí napríklad hierarchický klastrovací algoritmus [8].

5 Čiastočne učenie s učiteľom

Lepšie výsledky sa väčšinou dajú dosiahnuť pri použití učenia s učiteľom ako bez učiteľa. Na druhej strane vstupom pre učenie s učiteľom je pomerne veľká množina dokumentov, ktoré musia byť už klasifikované alebo nejako označené. Pričom klasifikácia je časovo náročná. V praxi máme zvyčajne k dispozícií relatívne malú skupinu klasifikovaných dokumentov a veľkú skupinu neklasifikovaných dokumentov. Vtedy je vhodné použiť kombináciu oboch prístupov, ktorá sa nazýva čiastočné učenie s učiteľom.

6 Spoločenské siete

Internetová sieť tvorená hypertextovými dokumentmi, ktoré na seba odkazujú má podobné vlastnosti ako majú takzvané spoločenské siete [5]. Tie sa vyznačujú tým, že medzi objektmi, ktoré spolu navzájom súvisia, vznikajú takzvané spoločenstva. Tá istá vlastnosť sa dá pozorovať aj na internete. Napríklad väčšina odkazov stránok zaoberajúcich sa motorizmom sú odkazy opäť na stránky o motorizme.

S využitím teórie spoločenský sieti boli navrhnuté niektoré algoritmy, ktorých cieľom je vybrať stránku, ktorá najlepšie spĺňa požiadavky, ktoré zadal používateľ.

Google - PageRank

Google je internetový vyhľadávač, ktorý ako prvý začal využívať poznatky teórie spoločenských sieti na určenie najvhodnejšej webovej stránky podľa dotazu používateľa.

Nech p je pravdepodobnosť zobrazenia náhodne vybranej webovej stránky a p-1 je pravdepodobnosť zobrazenia ľubovoľnej stránky, na ktorú odkazuje hypertextový odkaz na tejto stránke. Potom rôzne stránky by budú mať rôznu návštevnosť. Populárne webové stránky, na ktoré odkazuje, mnoho ďalších stránok budú mať vyššiu návštevnosť. Táto mierka populárnosti stránky sa nazýva PageRank [6] a pre jej výpočet platí rekurzívny vzťah

kde

u→v znamená, že stránka u obsahuje hypertextový odkaz na stránku v a N je počet všetkých navštívených stránok. Prehľadávací mechanizmus Google týmto spôsobom prechádza jednotlivé stránky a zisťuje ich PageRank, ktorý používa ako metriku na určenie populárnosti stránky. Po tom, ako vyhľadávač nájde stránky, ktoré spĺňajú požiadavky používateľ, sú tieto stránky zoradené tak, že stránky s najvyšším PageRank sa zobrazia ako prvé. Dôležité je, že PageRank nie je závislý od konkrétneho dotazu a teda nemusí sa počítať pri každom dotaze, čím sa predíde spomaleniu vyhľadávania.

Hľadanie témy na základe hypertextových odkazov

Pri tomto postupe sa najprv vytvorí množina stránok, ktoré spĺňajú zadaný dotaz. Do tejto množiny sa potom pridajú aj stránky, na ktoré tieto pôvodne vybrané stránky odkazujú a stránky, ktoré obsahujú odkaz na pôvodne stránky [7]. Každej stránke z tejto množiny sa potom priradia dve metriky hu a au, ktoré sú na začiatku inicializované na hodnotu 1. Následne sa tieto hodnoty pre jednotlivé stránky iteratívne prepočítavajú podľa nasledujúcich pravidiel

pričom obe sumácie sú normalizované na hodnotu 1 po každej iterácií. Čím vyššiu hodnotu má metrika a, tým významnejšia je daná stránka (odkazuje sa na ňu viacej stránok). Čím vyššiu hodnotu má metrika h, tým viac odkazov obsahuje táto stránka (po anglicky sa tieto stránky nazývajú hub). Tento algoritmus je pomalší ako algoritmus PageRange, pretože sa musí prerátavať zvlášť pre každý dotaz.

7 Záver

V článku sú zhrnuté rôzne prístupy k dolovaniu dát z textových a hypertextových dokumentov začínajúce jednoduchými štatistickými modelmi pre textové dokumenty až po modely zohľadňujúce vzťahy medzi jednotlivými hypertextovými dokumentmi. Mnohé z týchto postupov už využívajú komerčné vyhľadávače, ktorých cieľom je, poskytnúť čo najadekvátnejšie odpovede na používateľké dotazy. S narastajúcim množstvom stránok a zvyšujúcou sa dôležitosťou správnych informácií sa budú nároky na vyhľadávacie systémy ešte viac zvyšovať. Preto bude použitie robustných a najmodernejších algoritmov pre dolovanie dát z hypertextových dokumentov v budúcnosti veľmi dôležité.

 

Použitá literatúra

[1] Soumen Chakrabarti. Data mining for hypertext: A tutorial survey. Indian Institute of Technology Bombay. Januar 2000.

[2] W. B. Frakes a R. Baeza-Yates. Information retrieval: Data structures and algorithms. Prentice-Hall, 1992.

[3] S. Chakrabarti, B. Dom, R. Agrawal, a P. Raghavan. Using taxonomy, discriminants, and signatures to navigate in text databases. In VLDB, Athens, Greece, Sept. 1997.

[4] T. Joachims. Making large-scale SVM learning practical. In B. SchSlkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods: Support Vector Learning. MIT Press, 1999.

[5] S. Wasserman and K. Faust. Social Network Analysis. Cambridge University Press, 1994.

[6] S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. In Proceedings of the 7th World-Wide Web Conference (WWWT), 1998.

[7] J. Kleinberg. Authoritative sources in a hyperlinked environment. In ACM-SIAM Symposium on Discrete Algorithms, 1998.

[8] B. T. LUKE: Divisive Clustering

 


Znalostné systémy
Zimný semester 2005/2006