´ ´ er ˇ Uvod STC Zav
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´ Autor: Jan Hoˇsek ˇ ˇ uˇ Skolitel: RNDr. Radim Reh ˚ rek ´ eˇ inˇzen´yrzka´ Fakulta jaderna´ a fyzikaln ˇ Cesk e´ vysoke´ uˇcen´ı technicke´ v Praze
25. 5. 2009
ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
´ ´ er ˇ Uvod STC Zav
Osnova
1
´ Uvod Motivace ´ Ukazka technologie pro anglicke´ dokumenty
2
STC Suffix Tree Clustering Algoritmus Sloˇzitost
3
´ er ˇ Zav Shrnut´ı Reference
ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
´ ´ er ˇ Uvod STC Zav
´ Motivace Ukazka technologie pro anglicke´ dokumenty
Motivace ´ Problem ´ ce vrac´ı v´ysledky jako dlouh´y seznam seˇrazen´y podle Vyhledavaˇ relevance Uˇzivatele´ cˇ asto kladou pˇr´ıliˇs obecne´ dotazy Prvn´ı subjektivneˇ vyhovuj´ıc´ı dokument muˇ ˚ ze b´yt v seznamu velmi daleko ˇ sen´ı Reˇ ´ v seznamu v´ysledku˚ skupiny podobn´ych dokumentu˚ a Nalezt spojit je do shluku˚ ´ ´ do Uˇzivatel nemus´ı prochazet cel´y seznam, ale je navigovan skupiny dokumentu, ˚ ktera´ ho zaj´ıma ´ Seznam dokumentu˚ lze pˇreskupit (proloˇzit) tak, aby na zaˇcatku ´ byli zastupci ze vˇsech skupin.
ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
´ ´ er ˇ Uvod STC Zav
´ Motivace Ukazka technologie pro anglicke´ dokumenty
´ Ukazka technologie Vivisimo ´ Ukazka technologie Vivisimo
ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
´ ´ er ˇ Uvod STC Zav
´ Motivace Ukazka technologie pro anglicke´ dokumenty
´ Ukazka technologie Vivisimo ´ Ukazka technologie Vivisimo
ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
´ ´ er ˇ Uvod STC Zav
Suffix Tree Clustering Algoritmus Sloˇzitost
Suffix Tree Clustering ´ ı na zaklad ´ ´ ı Shlukovan´ eˇ shodn´ych fraz´ STC - Suffix Tree Clustering ´ ı pomoc´ı suffixoveho ´ Algoritmus shlukovan´ stromu popsal O. Zamir[1] ´ prace ´ je implementovat a otestovat Hlavn´ım ukolem teto ´ tento algoritmus pro cˇ eske´ texty ´ Moˇzna´ uskal´ ı cˇ eskeho jazyka ´ Bohate´ tvaroslov´ı ˇ s´ı slovosled Volnejˇ Psan´ı bez diakritiky
ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
´ ´ er ˇ Uvod STC Zav
Suffix Tree Clustering Algoritmus Sloˇzitost
Postup algoritmu ´ ı textu Pˇredzpracovan´ ˇ ı zvlaˇ ´ stn´ıch znaku, Odstranen´ ˚ pˇrevod na mala´ p´ısmena ˇ ı na vety ˇ a na slova Rozdelen´ ˇ ı pˇredpon, pˇr´ıpon, mnoˇzneho ´ Odstranen´ cˇ ´ısla atd. ´ Nalezen´ı zakladn´ ıch shluku˚ ´ ı suffixtree Vygenerovan´ ´ Nalezen´ı zakladn´ ıch shluku˚ a jejich ohodnocen´ı s(B) = |B| · f (|P|) |B| - poˇcet dokumentu˚ ve shluku B ´ P |P| - poˇcet slov ve frazi ´ vynechame ´ Z hodnocen´ı fraze pˇr´ıliˇs cˇ asta´ a pˇr´ıliˇs ˇr´ıdka´ slova
ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
´ ´ er ˇ Uvod STC Zav
Suffix Tree Clustering Algoritmus Sloˇzitost
Suffixtree cat ate cheese“, mouse ate cheese too“, cat ate mouse too“ ” ” ”
ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
´ ´ er ˇ Uvod STC Zav
Suffix Tree Clustering Algoritmus Sloˇzitost
Postup algoritmu ´ ı textu Pˇredzpracovan´ ˇ ı zvlaˇ ´ stn´ıch znaku, Odstranen´ ˚ pˇrevod na mala´ p´ısmena ˇ ı na vety ˇ a na slova Rozdelen´ ˇ ı pˇredpon, pˇr´ıpon, mnoˇzneho ´ Odstranen´ cˇ ´ısla atd. ´ Nalezen´ı zakladn´ ıch shluku˚ ´ ı suffixtree Vygenerovan´ ´ Nalezen´ı zakladn´ ıch shluku˚ a jejich ohodnocen´ı s(B) = |B| · f (|P|) |B| - poˇcet dokumentu˚ ve shluku B ´ P |P| - poˇcet slov ve frazi ´ vynechame ´ Z hodnocen´ı fraze pˇr´ıliˇs cˇ asta´ a pˇr´ıliˇs ˇr´ıdka´ slova
ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
´ ´ er ˇ Uvod STC Zav
Suffix Tree Clustering Algoritmus Sloˇzitost
Postup algoritmu
´ Kombinace zakladn´ ıch shluku˚ ´ ı Dokumenty maj´ı cˇ asto v´ıce spoleˇcn´ych fraz´ Na mnoˇzineˇ shluku˚ definujeme ekvivalenci: Bn ≡ Bm ⇔ (|Bm ∩ Bn |/|Bm | > 0, 5) ∧ (|Bm ∩ Bn |/|Bn | > 0, 5) ´ ekvivalence jsou v´ysledne´ shluky Tˇr´ıdy teto
ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
´ ´ er ˇ Uvod STC Zav
Suffix Tree Clustering Algoritmus Sloˇzitost
Sloˇzitost STC
´ ame ´ Pˇredpoklad n dokumentu˚ na vstupu Velikost dokumentu je omezena´ ´ Tedy i hloubka suffixoveho stromu je omezena´ ˇ ´ Casova´ sloˇzitost v´ypoˇctu zakladn´ ıch shluku˚ je O(n) ´ ı shluku˚ je teoreticky O(n2 ), ale kdyˇz se Kombinovan´ ´ an´ ´ ı ostatn´ıch shluku˚ vuˇ omez´ıme na porovnav ˚ ci k nejv´ysˇ e hodnocen´ym je sloˇzitost O(n) Celkem O(n)
ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
´ ´ er ˇ Uvod STC Zav
Shrnut´ı Reference
Shrnut´ı
STC ´ ı shluku˚ v posloupnosti O(n) algoritmus pro hledan´ dokumentu˚ Implementace v jazyce Python ´ Upravy pro cˇ eske´ dokumenty ´ Pro v´ypoˇcet cˇ etnosti slov jsem pouˇzil pˇrevod na zakladn´ ı tvar (lemmatizace) ´ je vhodne´ penalizovat zajmena, ´ V hodnt´ıc´ı funkci fraze ´ pˇredloˇzky, spojky, cˇ astice a citoslovce
ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
´ ´ er ˇ Uvod STC Zav
Shrnut´ı Reference
Reference Zamir, O. and Etzioni, O., Web document clustering: a feasibility demonstration Vivisimo, http://clusty.com/
ˇ Dekuji za pozornost ˇ ˇ uˇ Autor: Jan Hoˇsek Skolitel: RNDr. Radim Reh ˚ rek
ˇ ı webov´ych dokumentu˚ v realn ´ em ´ cˇ ase Tˇr´ıden´
