1 (okres realizacji XI.2003- XI.2005projekt KBN 4 T11C (okres realizacji XI XI.2005 Mapy i inteligentna nawigacja w sieci WWW z wykorzystaniem sieci bayesowskich i systemów immunologicznych Kierownik: dr hab. inż.Mieczyslaw A. Klopotek Wykonawcy: prof. dr hab. inż. Slawomir T. Wierzchon , mgr inż. Krzysztof Ciesielski mgr inż. Michal Draminski, Instytut Podstaw Informatyki PAN, Warszawa mgr Mariusz Kujawiak Instytut Informatyki Akademii Podlaskiej , Siedlce dr inż. Marcin Sydow Polsko-Japońska Wyższa Szkoła Technik Komputerowych, Warszawa Research partially supported by the KBN research project 4 T11C "Maps and intelligent navigation in WWW using Bayesian networks and artificial immune systems"
2 Agenda Cel projektu Pojęcie mapy dokumentu Proces tworzenia mapyArchitektura systemu Problematyka klasteryzacji w mapach dokumentów Wyniki niektórych eksperymentów Co przed nami .... 2nd International Conference on Telemedicine and Multimedia Communication,
3 Cel projektu Celem projektu jest stworzenie narzędzi do wspomagania zadania eksploracji pełnotekstowych baz dokumentów poprzez stworzenie nawigacyjnej mapy dokumentów, na której bliskość geometryczna na mapie odzwierciedlałaby bliskość koncepcyjną dokumentów, a trzeci wymiar byłby wykorzystywany do odzwierciedlenia gęstości dokumentów
4 Koncepcja mapy dokumentówWizualizacja zbioru dokumentów na płaszczyźnie Wiele podejść (inxight, internet cartographer, WEbSOM i warianty) Idea WebSOM bliskość na mapie = bliskość w przestrzeni dokumentów Obszary mapy etykietowane informatywnie Trzeci wymiar – odmienność w stosunku do otoczenia Nasze podejście bazuje na idei WebSOM Trzeci wymiar – gęstość dokumentów
5 Interfejs systemu BEATCA dostęp z http://www. ipipan. wawInterfejs systemu BEATCA dostęp z /mak/current_research/KBN2003/KBN2003Translation.htm Zapytanie Wyntrana mapa Lista map Dokumenty z „komórek”
6 Trójwymiarowe wizualizacje map (BEATCA)
7 W planach: hypergeometryczne reprezentacje (Fish-Eye Effect)
8 Proces tworzenia mapy (bez etykietowania)Zbiór dokumentów Mapa doklumentów Grupy w przestrzeni dokumentów Punkty w przestrzeni dokumentów
9 WebSOM – model przestrzeni dokumentówMy dog likes this food dog W tzw. Modelu wektorowym dokument jest punktem w przestrzeni rozpiętej przez termy – o współrzędnych odpowiadających częstosci tych termów food When walking, I take some food walk
10 Przestrzeń dokumentów a zapytania w wyszukiwarcedog Relewantność dokumentu do kwerendy mierzy się kosinusem kąta między kwerendą a dokumentem food Query: walk walk
11 WebSOM – specyficzna klasteryzacja dokumentówKażda komórka mapy ma swój wektore ferencyjny r x m Mocna zmiana położenia (gruba strzałka) Document space 2D map Important difference to general clustering: not only clusters with similar documents, but also neighboring clusters similar
12 Wady WebSOM Wysoka złożoność obliczeniowaNiestabilność (mapy różnią się dla tych samych dokumentów)
13 Nasza modyfikacja Reprezentacja w postaci kompaktowych wektorów referencyjnych Inicjalizacja ogólnymi tematami Łączona metoda szukania zwycięzcy Mapy wielopozuiomowe Wielofazowa klasteryzacja Początkowa klasteryzacja – identyfikacja głównych tematów Wstępne grupowanie dokumentów WEBSOM dla grup dokumentów Rozmyte grupowanie komórek WebSOM i etykietowanie
14 Reprezentacja w postaci kompaktowych wektorów referencyjnychWektory referencyjne komórek mapy są rzadkie Podczas uczenia stają się jeszcze rzadsze Reprezenntowane przez zrównoważone drzewa „red-black tree” Zadano próg tolerancji Termy (wymiary) poniżej progu są usuwane Zdecydowanie zmniejszono złozoność bez pogorszenia jakości
15 Inicjalizacja tematyczna wektorów referencyjnychZamiast WebSOMowej losowej Identyfikacja K głównych tematów (i ich opisów) Użycie LSI, lub Naiwnej sieci bayesowskiej lub PLSA – niestety nie rekomendujemy Wybór K punktów na mapie jako tyzw. „punktów fiksowych poszczególnych tematów Inicjalizacja punktów fiksowych tematami głównymi Pozostałe komórki inicjalizujemy wektorami „pośrednimi”
16 Klasteryzacja wstępna dokumentówMetoda gazu neuronowego lub gazu neuronowego z funkcją użyteczności lub sieci immunologicznej (przyszłe badania) sieci bayesowskiej (przyszłe badania)
17 Łączone poszukiwanie zwycięzcy na mapie typu WebSOMGlobalne poszukiwanie – dokładne, lecz wolne Lokalne przeszukiwanie – szybsze, lecz może być niedokładne dla szybkich zmian rozkładu Start – jedna faza poszukiwań globalnych Ruchy dokumentów coraz płynniejsze – lokalne poszukiwanie wystarcza Nawrót globalnego przeszukiwania w wypadku nagłych przemieszczeń (outliery, zmnmiejszenie promienia otoczenia)
18 Mapy hierarchiczne Bottom-up approachFeasible (with joint winner search method) Start with most detailed map Compute weighted centroids of map areas Use them as seeds for coarser map Top-down approach is possible but requires fixpoints
19 Klasteryzacja grup dokumentów (komórek do obszarów)Tradycyjne metody zawodne: Skrajnie rozmyta struktura tematyczna SOM Podobieństwo w oryginalnej przestrzeni i na mapie koniecznie zachowane Problemy outrlierów Brak estymacji liczby grup apriori Zastosowano Fuzzy C-MEANS na kracie komórek Połączenie rozmytego grupowania z podejściem grafowym (MST gęstości i odległości) Sjklastrowane dokumenty etykietowane ważonymi centroidami wektorów referencyjnych komórek skalowanymi entropią międzygrupową
20 Architektura systemu
21 Eksperymenty ze zbieżnością mapBadano zbieżność do stabilnego stanu mapy w zależności od Typu funkcji alpha (tempo redukcji promienia poszukiwań) Typu metody szukankia zwycięzcy
22 Zbieżność – funkcje alpha (liniowa kontra odwrotnie proporcjonalna)
23 Zbieżność – poszukiwanie zwycięzcy (łączne kontra lokalne)
24 Eksperymenty z czasem wykonaniaCzynniki badane Rozmiar mapy (całkowita liczba komórek) Metoda optymalizacji słownika dictionary optimization reference vector representation
25 Execution time - map size
26 Execution time - optimizations
27 Dalsze badania Implementacja kolejnych metod klasteryzacjiImplementacja koncepcji przyrostowego konstruowania map Budowa efektywnego pająka Badania porównawcze szybkości i jakości generowanych na różnych ścieżkach
28 Dziękuję. Czy są pytania?