Uniwersytet Warszawski University of Warsaw
Menu
Wyszukiwarka
 W bieżącym katalogu
UNIWERSYTET WARSZAWSKI

Wydział Matematyki, Informatyki i Mechaniki

METODA ANALIZY REGULARNOŚCI I JEJ ZASTOSOWANIA W EKSPLORACJI DANYCH

Tytuł po angielsku:

Regularity Analysis And Its Applications In Data Mining

-------- Autoreferat --------

Autor: Nguyen Thi Sinh Hoa

Promotor:

dr hab. Bogdan S. Chlebus

Warsaw, 1999

 

Automatyczne odkrywanie wiedzy z danych jest jedną z głównych dziedzin sztucznej inteligencji, w szczególności eksploracji danych i odkrywania wiedzy (ang. data mining and knowledge discovery). Głównym celem eksploracji danych jest wyszukiwanie istotnych informacji w oparciu o skończony zbiór przykładów (obiektów) (ang. examples, objects).

Przedmiotem badań w dziedzinie eksploracji danych są różnego typu zależności: funkcyjne lub relacyjne występujące w zbiorze przykładów. Zależności te są zwykle reprezentowane przez wzorce (ang. patterns - patrz [2]) lub reguły decyzyjne (ang. decision rules - patrz [2], [11]).

Wzorce i reguły decyzyjne tworzą zestaw ważnych narzędzi przy rozwiązywaniu dwóch podstawowych problemów, często spotkanych w praktyce: klasyfikacji nowych przykładów (ang. new object classification) oraz opisu pojęć (podzbiorów danych) (ang. concept description). Drugie zadanie jest ogólniejsze, dlatego w rozważaniach jest ono zwykle wysuwane na pierwszy plan.

W praktyce interesujące nas pojęcia są często definiowane jedynie w oparciu o dostępną niepełną informację. Pojęcie zwykle jest syntetyzowane z pojęć pierwotnych (ang. primitive concepts) (patrz [10]), które z kolei są zdefiniowane przez wzorce. Problem opisu pojęć sprowadza się więc do problemu wyszukiwania zbioru wzorców dobrze przybliżających dane pojęcie.

Przy konstrukcji algorytmów odkrywania wiedzy pojawiają się następujące problemy:

  1. Wybór języka do reprezentacji wiedzy. Język do opisywania wiedzy z jednej strony musi być prosty aby zapewnić efektywność procesu wyszukiwania wzorców. Z drugiej strony musi się on charakteryzować wystarczającą ekspresywnością, pozwalającą na wyrażanie złożonych pojęć i struktur danych.

  2. Wyznaczanie kryterium oceny jakości wzorca (lub zbioru wzorców) dla zapewnienia oceny bliskości aproksymowanych pojęć (definiowanych w oparciu o niepełną informację) do docelowych.

  3. Konstrukcja efektywnych algorytmów generowania semi-optymalnego wzorca (lub semi-optymalnego zbioru wzorców).

W literaturze można znaleźć opisy wielu metod rozwiązywania problemu opisu pojęć. Do popularnych należą: metody statystyczne (patrz [5], [6]), algorytmy decyzyjne (patrz [11]), drzewa decyzyjne (patrz [12]) czy sieci neuronowe (patrz [13]). Autorzy poszczególnych metod starają się wykazać ich zalety biorąc pod uwagę różne kryteria. Jednak w literaturze brak było dotąd jednolitego podejścia do zagadnienia optymalnego opisu, trudno więc było scharakteryzować zarówno złożoność obliczeniową problemu jak i jakość algorytmów heurystycznych.

1  GŁÓWNE WYNIKI PRACY

W niniejszej pracy, rozważane są najważniejsze aspekty związane z procesem odkrywania wiedzy: oprócz analizy wspomnianych wyżej trzech problemów dotyczących konstrukcji efektywnych algorytmów odkrywania wzorców, omawiamy również analizę złożoności obliczeniowej szeregu problemów dotyczących zagadnienia opisu pojęć. Uzyskane wyniki można podzielić na cztery grupy:

  • Zagadnienie dotyczące języka reprezentacji wiedzy;
  • Złożoność obliczeniowa problemów aproksymacji pojęć;
  • Metody odkrywania wzorców ze skończonego zbioru danych;
  • Eksperymenty komputerowe i zastosowania w problemach eksploracji danych.

O to ich omówienie.

  1. Język reprezentacji wiedzy

    Wzorzec w standardowym języku jest reprezentowany przez koniunkcję podstawowych wyrażeń typu (atrybut = wartość), zwanych deskryptorami. Język ten jest prosty i w wielu zastosowaniach okazuje się wystarczający do opisu pojęć. Jednak w wielu innych zastosowaniach, gdy dziedziny atrybutów opisujących dane są złożone (np. gdy liczba wartości w dziedzinie jest duża względem liczby przykładów występujących w tablicy danych) wzorce w języku standardowym okazują się niewystarczające a algorytmy decyzyjne stają się nieefektywne. W pracy rozpatruje się dwa kierunki rozszerzenia języka reprezentacji wiedzy.

    • Wzorce uogólnione. W wyrażeniach logicznych używanych do opisu pojęć, zamiast prostych deskryptorów typu (atrybut = wartość), rozpatruje się ogólniejsze deskryptory typu (atrybut Î zbiór_wartości). Uwzględniono dwa przypadki. Jeżeli dziedzina atrybutu składa się z wartości numerycznych, to zbiór_wartości jest zdefiniowany jako przedział liczb rzeczywistych, a gdy dziedzina atrybutu zawiera wartości symboliczne, to zbiór_wartości jest zdefiniowany jako zbiór wartości dyskretnych należących do dziedziny atrybutu. Wzorce będące koniunkcją deskryptorów uogólnionych są nazwane szablonami.

    • Wzorce definiowane za pomocą relacji podobieństwa. Każdy wzorzec w standardowym języku może być zdefiniowany również przez pewną parę (x0, R), gdzie x0 jest obiektem w zbiorze danych, a R jest binarną relacją będącą relacją "nierozróżnialności" określoną na dziedzinach atrybutów (patrz [11]). W celu rozszerzenia języka, zamiast standardowej relacji nierozróżnialności rozpatruje się w pracy pewne klasy relacji zwanych relacjami podobieństwa (ang. similarity relation) (patrz [14], [15]). Wzorce są zatem zdefiniowane przez obiekt i pewną optymalną relację podobieństwa związaną z tym obiektem. Wzorce zdefiniowane przez relację podobieństwa są nazywane wzorcami relacyjnymi.

  2. Złożoność obliczeniowa problemów aproksymacji pojęć

    Jednym z najważniejszych wyników pracy jest określenie złożoności obliczeniowej szeregu problemów związanych z wyszukiwaniem optymalnego opisu pojęć. W pracy otrzymano następujące wyniki:

    • Pierwszy dotyczy problemu wyszukiwania optymalnego standardowego wzorca. Udowodniono, że dla podanej liczby naturalnej k, problem wyszukiwania k deskryptorów postaci (atrybut = wartość) takich, że wzorzec będący koniunkcją tych deskryptorów jest spełniony przez maksymalną liczbę przykładów z tablicy danych jest NP-trudny.

    • Drugi dotyczy problemu wyszukiwania optymalnego zbioru cięć. Cięcie definiuje się jako parę (a, c), gdzie a jest pewnym atrybutem, a c określa wartość cięcia na tym atrybucie. Problem związany jest z minimalizacją zbioru deskryptorów postaci (a Î [v1, v2]) potrzebnych do opisu tablicy danych przy zachowaniu rozróżnialności (patrz [11]). Problem ten był po raz pierwszy rozpatrywany w [7], gdzie udowodniono, że problem wyszukiwania minimalnego niesprzecznego zbioru cięć należy do klasy problemów NP-trudnych, jeżeli liczba atrybutów jest jedną z danych wejściowych. W tej pracy ulepszono ten wynik dowodząc, że wymieniony problem jest NP-trudny, jeśli liczba atrybutów jest dowolną stałą większą od 1.

    • Trzeci dotyczy również problemu wyszukiwania optymalnego zbioru cięć. Rozpatruje się jednak inne kryterium optymalizacji. Zbiór cięć jest optymalny, jeśli jest niesprzeczny z danymi oraz liczba obszarów wyznaczonych przez te cięcia jest najmniejsza. Udowodniono, że przy tak postawionym kryterium problem wyszukiwania optymalnego zbioru cięć jest NP-trudny.

    • Kolejny wynik dotyczy problemu wyszukiwania optymalnej rodziny podziałów, który jest związany z minimalizacją zbioru deskryptorów postaci ( atrybut Î zbiór_wartości) potrzebnych do opisu tablicy danych przy zachowaniu jej rozróżnialności (patrz [11]). Podziałem określonym na pewnym atrybucie jest podział zbioru wartości tego atrybutu na rozłączne podzbiory. Rodzina podziałów określonych na atrybutach zbioru danych jest optymalna jeśli jest niesprzeczna z tymi danymi oraz łączna liczba podzbiorów powstających z tych podziałów jest najmniejsza. Udowodniono, że wymieniony problem należy do klasy problemów NP-trudnych.

    • Ostatni wynik dotyczy problemu wyszukiwania optymalnego podziału binarnego. Binarny podział to taki, który dzieli zbiór wartości atrybutu na dwa rozłączne podzbiory. Binarny podział jest optymalny, jeśli rozróżnia maksymalną liczbę przykładów o różnych decyzjach (należących do różnych klas decyzyjnych). Wykazano, że problem wyszukiwania optymalnego binarnego podziału jest NP-trudny.

  3. Metody odkrywania wzorców

    W pracy przedstawiono szereg nowych metod generowania wzorców. Rozpatrywano dwie ważne klasy wzorców: szablony oraz wzorce relacyjne.

    • Odkrywanie szablonów (ang. templates)

      Rozwijając ideę sekwencyjnej selekcji atrybutów (ang. feature selection) (patrz [4]), przedstawiono nowe podejście do wyszukiwania szablonów. Nowa metoda charakteryzuje się ogólnością. Ten sam schemat obliczenia może być użyty do generowania uogólnionych wzorców o różnych właściwościach, które pasują do różnych zastosowań praktycznych np. do klasyfikacji, opisywania pojęć, generowania reguł asocjacyjnych, itp. Przedstawiono również nową metodę konstrukcji drzewa decyzyjnego. Nowa metoda wykazuje pewną zaletę w porównaniu do znanych metod z literatury ([5], [12]). Jest nią większa ogólność, umożliwia ona generowanie efektywnego drzewa dla różnych typów danych: symbolicznych i numerycznych.

    • Odkrywanie wzorców relacyjnych (ang. relational patterns)

      Wzorce relacyjne są definiowane za pomocą relacji podobieństwa. Opierając się na kryterium maksymalnej jednorodności (obiekty w jednej klasie podobieństwa muszą należeć do jednej klasy decyzyjnej) przedstawiono nowe podejście do wykrywania relacji podobieństwa z danych. Analizując geometryczne struktury relacji podobieństwa, opracowano uniwersalny schemat pozwalający na generowanie optymalnych relacji w różnych klasach podobieństwa.

  4. Wyniki doświadczalne

    Implementacja opracowanych metod wykrywania wzorców oraz przeprowadzone eksperymenty tworzą ważną część pracy. Opracowane algorytmy charakteryzują się efektywnością obliczeniową. Umożliwiają one zatem efektywną pracę przy danych o dużych rozmiarach. Rozpatruje się trzy podstawowe zastosowania wzorców w praktyce: klasyfikacja nowego obiektu, opis pojęć (w szczególności klas decyzyjnych) oraz dekompozycja zbioru danych. Otrzymane wyniki potwierdzają skuteczność nowych podejść zaproponowanych w pracy w tych zastosowaniach.

Literatura

    [1] Chlebus B. S., Nguyen S. Hoa, 1998. On finding optimal discretizations for two attributes. Proc. of First International Conference on Rough Sets and Soft Computing (RSCTC'98). Warszawa, Poland, June 22-27, Springer-Verlag, LNAI 1424, 537-544.

    [2] Fayyad U. M., Piatetsky-Shapiro G., Smyth P., Uthurusamy R., (Eds.) 1996. Advances in Knowledge Discovery and Data Mining. AAAI Press/ The MIT Press.

    [3] Greco S., Matarazzo B., Słowiński R. 1999. On Joint Use of Indicernibility, Similarity and Dominance in Rough Approximation of Decision Classes. Proc. of Fifth International Conference on Integrating Technology and Human Decisions: Global Bridges into the 21th Century. Athens, Greece, July 4-7.

    [4] Liu H., Motoda H., 1998. Feature Selection for Knowledge Discovery and Data Mining. Kluwer Academic Publishers.

    [5] Michie, D., Spiegelhanter, D.J. and Taylor, C.C., (Eds.), 1994. Machine Learning, Neural and Statistical Classification. Ellis Horwood, London.

    [6] Mitchell T. M., 1997. Machine Learning. The McGraw-Hill Companies, Inc., New York.

    [7] Nguyen H. Son, 1997. Discretization of Real Value Attributes: Boolean Reasoning Approach. Warsaw University, Ph.D. Dissertation.

    [8] Nguyen S. Hoa, Nguyen H. Son, 1998. Pattern extraction from data. Fundamenta Informaticae 34, 129-144.

    [9] Nguyen S. Hoa, Skowron A., Synak P., 1998. Discovery of Data Patterns with Applications to Decomposition and Classification Problems. In: Polkowski and Skowron [11], 55-97.

    [10] Pal S. K., Skowron A., (Eds.), 1998. Rough-Fuzzy Hybridization: A New Trend in Decision Making. Springer-Verlag. Singapore.

    [11] Polkowski L., Skowron A., (Eds.), 1998. Rough Sets in Knowledge Discovery: Methodology and Applications. Physica-Verlag, Heidelberg.

    [12] Quinlan J. R., 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo, California.

    [13] Ripley B. D., 1996. Pattern Recognition and Neural Networks. Cambridge University Press, Cambridge.

    [14] Słowiński R., Vanderpooten D., 1997. Similarity Relation as a Basis for Rough Approximations. In: P. Wang (Ed.): Advances in Machine Intelligence and Soft Computing, Bookwrights, Raleigh NC, 17-33.

    [15] Skowron A., Polkowski L., Komorowski J., 1996. Learning Tolerance Relation by Boolean Descriptions: Automatic Feature Extraction from Data Tables. Proc. of The Fourth International Workshop on Rough Sets, Fuzzy Sets and Machine Discovery. Tokyo, Japan, November 6-8, 11-17.

 

File translated from TEX by TTH, version 2.00.
On 25 Mar 2000, 13:24.