Treść pracy
Tytuł:

Metody grupowania i ich implementacja do eksploracji danych
postaci symbolicznej

Geneza pracy

Eksploracja danych czy też pozyskiwanie wiedzy z baz danych stało się istotnym zagadnieniem dotyczącym analizy danych stosowanym w wielu organizacjach. W wyniku szerokiej komputeryzacji wielu dziedzin życia, takich jak: nauka, biznes, administacja publiczna, efektywne i skuteczne wydobywanie istotnych informacji spośród zgromadzonych i stale rosnących zbiorów danych stało się kluczowym zagadnieniem. W niniejszej pracy zaprezentowano eksplorację danych jako proces, na który składa się etap poznania dziedziny, techniki analizy ze szczególnym uwzględnieniem grupowania oraz etap walidacji, będący wstępem do poznania nowej wiedzy o badanej dziedzinie. Obszar badań dotyczy danych symbolicznych, w szczególności danych lingwistycznych, zarówno języka naturalnego jak i o sztucznie ograniczonym zasobie słów i gramatyce. Szczegółowe zbadanie charakterystyki i właściwości danych pozwala na zbudowanie odpowiednich narzędzi ich analizy. Samo zagadnienie grupowania takich danych potraktowane zostało jako metoda czy też technika stosowana w ramach eksploracji danych. W pracy dokonano badania metod i technik umożliwiających eksplorację danych postaci symbolicznej oraz przedstawiono własne propozycje metod i algorytmów grupowania. Szczególnej analizie zostały poddane metody grupowania w kontekście danych symbolicznych i lingwistycznych. W tym celu dokonano przeglądu literatury zawierające treści związane z niniejszą tematyką, dokonano analizy dziedziny grupowania, jaką są dane biznesowe oraz dane lingwistyczne. Przeprowadzono badanie metod grupowania przydatnych do przetwarzania danych wymienionych postaci. Zasadniczym celem pracy było opracowanie metody grupowania opartej o listy decyzyjne. Przedstawiona metoda stanowi alternatywne rozwiązanie dla zagadnienia grupowania danych symbolicznych. W zakresie własnych propozycji metod grupowania autor wprowadził metodę grupowania opartą o listy decyzyjne. W oparciu o tą metodę autor zaproponował i zaimplementował trzy nowe algorytmy grupowania.

Teza pracy

W pracy formułuje się następującą tezę:
Zaproponowana metoda grupowania oparta o listy decyzyjne jest alternatywną metodą grupowania danych symbolicznych, a w niektórych przypadkach lepszą od dotychczas stosowanych metod grupowania.
Tezy szczegółowe:
  1. metody grupowania nie wykorzystujące funkcji odległości, oparte wyłącznie o kryterium jakości grupowania, w niektórych przypadkach lepiej nadają się do grupowania danych symbolicznych,
  2. dzięki wykorzystaniu dodatkowej wiedzy o znaczeniu słów, użytych w nazwach grupowanych obiektów, uzyskuje się lepsze wyniki grupowania (bardziej zgodne z oczekiwaniami ekspertów),
  3. dzięki zastosowaniu listy reguł do prezentacji rezultatów grupowania, metoda grupowania oparta o listy decyzyjne, jest lepsza od metod prezentujących wyniki w postaci macierzy przypisań czy też obiektów wzorcowych, z punktu widzenia percepcji człowieka.

Zakres pracy

W rozprawie dokonał szczegółowej analizy możliwości grupowania zbiorów zawierających dane symboliczne oraz możliwości zastosowania rezultatów grupowania do eksploracji danych. Badania dotyczyły metod i algorytmów grupowania, technik porównywania i weryfikacji uzyskiwanych rezultatów rezultatów. Zakres pracy jest następujący:
  1. Omówionie poszczególnych aspektów eksploracji danych, z uwzględnieniem jej usytuowania jako etapu w procesie pozyskiwania wiedzy oraz formy jej realizacji na przykładzie grupowania danych (rozdział 1).
  2. Krytyczna dyskusja różnych metod analizy danych postaci symbolicznej, szczególnie w kontekście grupowania danych tej postaci ( rozdziały 2 i 3) oraz w zakresie przeprowadzonych badań (rozdziały 5 i 6). Wykazano szereg warunków istotnych w procesie eksploracji danych.
  3. Przedstawiono adaptacje wybranych metod i algorytmów do analizy danych symbolicznych, wraz z przeprowadzeniem badań porównawczych ich skuteczności w zakresie grupowania przykładowych danych.
  4. Wprowadzono oryginalną metodę grupowania danych w oparciu o listy decyzyjne oraz zaproponowano 3 algorytmy w oparciu o tą metodę (rozdział 4). Metoda ta umożliwia grupowanie obiektów opisanych atrybutami symbolicznymi oraz umożliwia prezentację wyników w postaci reguł.
  5. Dokonano adaptacji i implementacji wybranych metod do grupowania danych symbolicznych, oraz porównano ich efektywności w zakresie przetwarzania przygotowanych zbiorów danych (rozdział 5). Wskazano przypadki, dla których metody nie wymagające stosowania funkcji odległości dają lepsze wyniki.
  6. Przedstawiono metodę grupowania dokumentów tekstowych o nietypowej postaci, jakimi są nazwy występujące w katalogu towarów (rozdział 6). Przedstawiono przykład, w którym dzięki wykorzystaniu zewnętrznej wiedzy wyniki grupowania były lepsze.
Zawarte w pracy badania metod grupowania przeprowadzono w oparciu o różne bazy danych, pochodzące ze zbiorów referencyjnych UCI oraz z rzeczywistych baz danych przedsiębiorstw. Celem badań była weryfikacja skuteczności poszczegółnych metod grupowania do grupowania danych postaci symbolicznej. Wykazano wrażliwość poszczególnych metod na rodzaj przetwarzanych danych co nie stanowi o ich dobroci. W toku badań odkryto nową metodę grupowania, dla której w dalszym ciągu przeprowadzono badania porównawcze z uprzednio przebadanymi metodami. Z konstrukcji metody wynika, że nie posiada ona tych wad, którymi obarczone były poprzednie. Potwierdzono w badaniach, gdyż wykazano istnienie przypadków, dla których przedstawiona metoda dała wyniki równe lub lepsze od osiąganych przez pozostałe metody.

Podsumowanie

Proponowane przez autora grupowanie za pośrednictwem atrybutów wnosi szereg zmian jakościowych w zakresie interpretacji i dalszej analizy wyników grupowania. W miejsce długiej tablicy przypisań obiektów (o długości równej ilości obiektów) otrzymuje się stosunkowo krótką listę reguł. Samo zmniejszenie zapisu wyniku ma pozytywny wpływ na możliwość dalszego przyswojenia wyniku przez człowieka. Dodatkowo lista ta jest w określony sposób uporządkowana, co umożliwia nadanie poszczególnym regułom pewnych cech ważności. Właściwość tą można znakomicie wykorzystać do porównywania rezultatów grupowania niewiele się od siebie różniących zbiorów. Przykładem takiego zagadnienia jest porównywanie tego samego zjawiska ale w różnych momentach czasu. Zbiory obiektów reprezentujące dane zjawisko podlegają zmianom i modyfikacjom w miarę upływu czasu. Do zagadnień eksploracji danych należy poznanie i wyjaśnienie istoty tych zmian. Propozycją autora niniejszej pracy jest użycie grupowania opartego o listę decyzyjną do objaśniania zmian, trendów w bazach danych. Wykorzystać do tego celu należy formę prezentacji wyniku grupowania, jakim jest lista decyzyjna. Kolejność ułożenia reguł w takiej liście jest bowiem bardzo czułym wskaźnikiem istotności poszczególnych wartości atrybutów, co szczególnego wymiaru nabiera podczas analizy zmian w bazie danych. Objaśnianie takich zmian poprzez przykłady wzorcowe, które są wynikiem grupowania iteracyjnego, jest utrudnione, gdyż ukryta jest przyczyna i charakter zmian (brak informacji o własnościach obiektów, które zaważyły na zmianie przykładu wzorcowego).
Metody oparte o listy decyzyjne mogą stanowić alternatywę w stosunku do pozostałych metod grupowania. Aby w pełni wydobyć ich możliwości należy skonstruować odpowiednie algorytmy. Autor zaproponował modyfikację trzech rodzajów algorytmów: pełny przegląd, proste wstawianie i genetyczny.
Algorytm pełnego przeglądu jest najbardziej dokładny ale zarazem najbardziej kosztowny, w sensie złożoności obliczeniowej. Drugi algorytm wykorzystuje zaproponowaną strategię heurystyczną. Strategia ta polega na poszukiwaniu położenia danej reguły w liście odrębnie dla każdej reguły. Przeszukiwanie trwa do momentu, aż przestawienie żadnej z reguł nie powoduje polepszenia wyniku. Stosowanie heurystyk okupione jest ryzykiem otrzymania rozwiązania tylko lokalnie optymalnego natomiast znaczącym atutem jest znacznie lepsza złożoność od algorytmu pełnego przeglądu. Trzecia propozycja algorytmu wykorzystuje ideę genomu, w który to przekształcono listę decyzyjną. Z uwagi na nieco inne właściwości listy należało zmodyfikować operatory przeszukiwania. Zrezygnowano z operatora krzyżowania, a operator mutacji realizuje operację zamiany miejscami dwóch losowo wybranych elementów.