Zespół autorski:	prof. dr hab. inż. Jan J. Mulawka (ISE)
	dr inż. Paweł Cichosz (ISE)

Metody odkrywania wiedzy
(Knowledge Discovery Methods)

Wymiar godzinowy zajęć:

W	C	L	P
2	-	-	1

Klasy tematyczne:

PZ-I

Wymagane przedmioty poprzedzające:

--

Zalecane przedmioty poprzedzające:

Inżynieria wiedzy (IW)

Przedmioty podobne:

Uczenie się maszyn (UM)

Forma zaliczenia:

E

Semestr zalecany:

7-9, studia III stopnia

Słowa kluczowe:

sztuczna inteligencja, systemy uczące się, odkrywanie wiedzy, eksploracja danych, indukcja, statystyczna istotność, drzewa decyzyjne, reguły, grupowanie pojęciowe, dyskretyzacja, konstruktywna indukcja, sieci bayesowskie, metauczenie się, tablice kontyngencji, aproksymacja funkcji

Krótka charakterystyka w języku polskim:

Przedmiot jest przeznaczony przede wszystkim dla studentów studiów magisterskich specjalności informatycznych. Celem przedmiotu jest zapoznanie studentów z najważniejszymi zaawansowanymi technikami stosowanymi do odkrywania wiedzy w danych (knowledge discovery), czyli odkrywania występujących w danych zależności i formułowania ich w postaci umożliwiającej wnioskowanie. Jest to dynamicznie rozwijająca się w ostatnich latach dziedzina badań naukowych i coraz częściej udanych zastosowań praktycznych. Jej znajomość staje się wobec tego istotnym elementem edukacji informatycznej na poziomie zaawansowanym. Zapoznanie się z nią może być zarówno przygotowaniem do późniejszej działalności badawczej w ramach studiów doktoranckich, jak i istotnym atutem na rynku pracy.

Techniki, które będą przedstawiane, wywodzą się z maszynowego uczenia się i statystyki. Wynika stąd częściowe podobieństwo do przedmiotu Uczenie się maszyn (UM), istnieją jednak następujące różnice:

1. tylko niektóre algorytmy omawiane na wykładzie z UM są wykorzystywane do odkrywania wiedzy i będą omawiane na wykładzie z MOW,
2. na wykładzie z MOW będą omawiane dodatkowe algorytmy wykorzystywane do odkrywania wiedzy nie objęte programem UM,
3. poziom prezentacji algorytmów będzie bardziej zaawansowany i uwzględni m.in. problemy efektywności obliczeniowej oraz statystycznej istotności wyników.

Krótka charakterystyka w języku angielskim:

The course is addressed mainly to M.Sc. students of Computer Science. The objective of the course is to intruduce to the students the most important advanced techniques used for knowledge discovery, i.e., discovering meaningful relationships in data and formulating them in a form useful for inference. This is recently a dynamically growing field of scientific research and, more and more often, successful practical applications. Some knowledge of this field becomes therefore an important element of computer science education on an advanced level. Learning about it may be both a form of preparation for future PhD research and a significant asset on the job market.

The techniques that will be presented come from machine learning and statistics. This entails a partial similarity to the Machine Learning course (Uczenie się maszyn), but there are the following differences:

• only some of the learning algorithms covered by the Machine Learning course are used for knowledge discovery and will be covered by the Knowledge Discovery Methods course,
• the Knowledge Discovery Methods course will cover several additional knowledge discovery algorithms not covered by the Machine Learning course,
• the presentation level of the algorithms will be more advanced, including in particular computational efficiency and statistical significance issues.

Treść wykładu:

Wprowadzenie.

Informacje o przedmiocie. Sformułowanie zadania odkrywania wiedzy. Klasyfikacja metod odkrywania wiedzy. Przykładowe zastosowania.

Wprowadzenie do maszynowego uczenia się.

Definicja uczenia się. Rodzaje uczenia się. Klasyfikacja metod uczenia się. Podstawowa terminologia i notacja. Rola uczenia się w odkrywaniu wiedzy.

Narzędzia ze statystyki i teorii informacji.

Przedziały ufności. Miary statystycznej istotności. Procedury statystycznej oceny hipotez. Entropia. Teorioinformacyjne miary niejednorodności rozkładu i złożoności.

Indukcja drzew decyzyjnych.

Reprezentacja hipotez za pomocą drzew decyzyjnych. Zstępujące konstruowanie drzewa. Kryteria wyboru testu. Testy dla atrybutów ciągłych. Przycinanie drzew decyzyjnych. Probabilistyczne drzewa decyzyjne.

Indukcja reguł.

Reprezentacja hipotez za pomocą zbiorów reguł. Strategie roztrzygania konfliktów przy stosowaniu reguł. Schemat sekwencyjnego pokrywania. Algorytmy AQ i CN2. Przycinanie zbiorów reguł. Probabilistyczne zbiory reguł.

Klasyfikacja bayesowska.

Twierdzenie Bayesa. Optymalny klasyfikator bayesowski. Naiwny klasyfikator bayesowski. Zasada minimalnej długości kodu i jej zastosowania do oceny jakości hipotez.

Sieci bayesowskie.

Definicja sieci bayesowskiej. Reprezentacja założeń o warunkowej niezależności w sieci bayesowskiej. Reprezentacja łącznego rozkładu wnioskowania w sieci bayesowskiej. Wnioskowanie w sieciach bayesowskich. Algorytmy uczenia się sieci bayesowskich.

Grupowanie pojęciowe.

Grupowanie za pomocą pokryć (system CLUSTER/2): reprezentacja grup przez kompleksy, zapewnianie rozłączności kompleksów. Grupowanie probabilistyczne (system COBWEB): funkcja oceny jakości grupowania, probabilistyczne drzewo grupowania, operatory modyfikacji drzewa i strategia ich stosowania. Wnioskowanie na podstawie wyników grupowania.

Odkrywanie reguł asocjacyjnych.

Składnia i semantyka reguł asocjacyjnych. Wsparcie i wiarygodność reguł asocjacyjnych. Analiza statystyczna tablic kontyngencji. Algorytm Apriori. Asocjacje temporalne.

Dyskretyzacja atrybutów ciągłych.

Rodzaje dyskretyzacji. Dyskretyzacja wstępująca. Dyskretyzacja zstępująca. Kryteria oceny dyskretyzacji: entropia, statystyka $\chi^2$. Dyskretyzacja bez nadzoru.

Konstruktywna indukcja.

Statystyczne miary istotności atrybutów i zależności między atrybutami. Eliminacja niestotnych atrybutów. Wykrywanie zależności funkcyjnych między atrybutami. Tworzenie nowych atrybutów: metody oparte na analizie danych i na analizie hipotez.

Metauczenie się.

Koncepcja metauczenia się. Metody generowania hipotez bazowych: techniki próbkowania, techniki wielu algorytmów, techniki różnej parametryzacji algorytmów, techniki randomizacji algorytmów. Metody łączenia hipotez: głosowanie, głosowanie ważone dokładnością, łączenie probabilistyczne.

Aproksymacja funkcji i regresja.

Reprezentacja parametryczna. Aproksymator liniowy. Regresja liniowa. Regresja nieliniowa. Metody pamięciowe.

Odkrywanie równań.

Heurystyki odkrywania równań z jedną zmienną zależną: metoda wykrywania trendów, metoda stałych pochodnych, metoda przeszukiwania przestrzeni parametrów . Heurystyki odkrywania równań z wieloma zmiennymi zależnymi: uogólniona metoda wykrywania trendów, metoda dekompozycji.

Dane rzeczywiste.

Techniki wstępnego przetwarzania danych: identyfikacja wartości izolowanych, identyfikacja niespójności, wypełnianie brakujących wartości. Przetwarzanie dużych zbiorów danych: techniki próbkowania i okienkowania, specjalizowane struktury danych.

Zakres projektu:

Projekt polegać będzie na implementacji omawianych na wykładzie algorytmów odkrywania wiedzy, być może z wykorzystaniem istniejących bibliotek, i ich zastosowaniu do wybranych zbiorów danych w celu odkrycia występujących w nich zależności. Typowe zadanie projektowe obejmować będzie następujące elementy:

1. implementację wybranego algorytmu odkrywania wiedzy,
2. implementację komunikacji z bazą danych,
3. przygotowanie bazy danych zawierającej dane do badań doświadczalnych,
4. przeprowadzenie eksperymentów z różnymi ustawieniami paramentrów algorytmu,
5. statystyczną analizę uzyskanych wyników.

Zakres pracy domowej:

W ramach pracy domowej studenci będą przeprowadzać badania doświadczalne z wykorzystaniem udostępnionego im oprogramowania niekomercyjnego implementującego niektóre techniki odkrywania wiedzy. Używana będzie w tym celu m.in. publicznie dostępna biblioteka Weka. Typowe ćwiczenie domowe będzie polegać na przeprowadzeniu porównawczych eksperymentów z kilkoma algorytmami stosowanymi do tych samych zbiorów danych, w celu zdobycia większego praktycznego doświadczenia w zakresie stosowania technik odkrywania wiedzy.

Literatura:

1. Cichosz, P. Systemy uczące się. WNT, 2001.
2. Kubat, M., Bratko, I., Michalski, R. S. Machine Learning and Data Mining: Methods and Applications. John Wiley and Sons, 1998.
3. Mitchell, T. M. Machine Learning. McGraw-Hill, 1997.
4. Witten, I. H., Frank, E. Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations.

Podpis kierownika zespołu autorskiego:

Podpis kierownika zakładu: Podpis dyrektora instytutu:

Decyzja końcowa:

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.2beta6 (1.42)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation mow-konspekt.tex

The translation was initiated by Pawel Cichosz on 2001-06-11