2008-10-07

Ogólna charakterystyka web miningu

Web mining

Wykład 1.

Rok akademicki: 2008/2009

Plan wykładu

• Pojęcie i rozwój web miningu

• Podstawowe problemy rozważane na gruncie web miningu

– analiza zawartości serwisów internetowych

– analiza zachowań użytkowników

– analiza struktury połączeń pomiędzy serwisami

• Zastosowania web miningu

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 2

1

2008-10-07

Zaliczenie przedmiotu

• Egzamin pisemny (test)

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 3

Data mining - definicja

The nontrivial extraction of implicit, previously unknown, and potentially useful information from data.

W. Frawley and G. Piatetsky-Shapiro and C. Matheus, Knowledge Discovery in Databases: An Overview. AI Magazine, Fall 1992, pp. 213-228.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 4

2

2008-10-07

Data mining - definicja

The science of extracting useful information from large data sets or databases.

D. Hand, H. Mannila, P. Smyth: Principles of Data Mining. MIT Press, Cambridge, MA, 2001. ISBN 0-262-08290-X

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 5

Data mining - definicja

Data mining, also known as knowledge-discovery in databases (KDD), is the practice of automatically searching large stores of data for patterns. To do this, data mining uses computational techniques from statistics, machine learning and pattern recognition.

http://en.wikipedia.org/wiki/Data_mining

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 6

3

2008-10-07

Data mining

Data mining to określenie grupy metod szeroko rozumianej analizy danych mających na celu identyfikację nieznanych wcześniej prawidłowości występujących w dużych zbiorach danych. Powstałe wyniki mają postać łatwą do interpretacji przez prowadzącego badania.

Eugeniusz Gatnar, 1997

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 7

Zasadniczy cel badań

• Analiza danych, mająca na celu wykrycie wzorców, a przez to wzbogacenie wiedzy człowieka.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 8

4

2008-10-07

Web mining

• Web mining – data mining zawartości serwisów

internetowych oraz zachowań ich użytkowników

• Podstawowe problemy rozważane na gruncie web miningu to:

– analiza zawartości serwisów internetowych,

– analiza zachowań użytkowników,

– analiza struktury połączeń pomiędzy serwisami.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 9

Zakres badań web miningowych

• Podstawowe problemy rozważane na gruncie Web Miningu to:

– analiza zawartości serwisów internetowych,

• podejście text miningowe,

• podejście oparte na ontologiach i sieciach semantycznych,

– analiza zachowań użytkowników,

– analiza struktury serwisów internetowych.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 10

5

2008-10-07

Analiza zawartości serwisów internetowych oparta na podejściu text miningowym

• Text mining – proces mający na celu wydobycie z zasobów tekstowych nieznanych wcześniej informacji (Marti A. Hearst, 1999).

• Serwisy WWW publikują przede wszystkim informacje tekstowe

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 11

Informacje tekstowe

• Wysoki stopień upowszechnienia informacji tekstowych,

• Łatwość przetwarzania tekstów przez człowieka,

• Trudności z automatyzacją przetwarzania spowodowane przez:

– niski stopień strukturyzacji tekstów,

– brak jednoznacznych metod interpretacji

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 12

6

2008-10-07

Korzenie text miningu

• Data mining,

• Uczenie maszynowe,

• Przetwarzanie języka naturalnego,

• Wyszukiwanie informacji,

• Statystyka,

• Matematyka (algebra liniowa),

• Informatyka.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 13

Zastosowania text miningu

• Pozyskiwanie informacji z tekstów,

• Identyfikacja wiadomości zawierających określone treści,

• Generowanie streszczeń,

• Klasyfikacja wzorcowa,

• Klasyfikacja bezwzorcowa,

• Identyfikacja powiązań,

• Wizualizacja,

• Generowanie odpowiedzi na pytania.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 14

7

2008-10-07

Przebieg analizy text miningowej

• Określenie celu, zakresu i kosztów badań,

• Wstępne przetworzenie dokumentów,

• Określenie sposobu reprezentacji informacji zawartych w dokumentach,

• Konstrukcja modelu,

• Realizacja obliczeń,

• Ocena modelu,

• Interpretacja uzyskanych wyników.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 15

Cel, zakres, koszty

• Identyfikacja typu rozpatrywanego problemu:

– klasyfikacja wzorcowa,

– klasyfikacja bezwzorcowa (analiza skupień),

– współwystępowanie zjawisk,

– określenie podobieństwa (np. identyfikacja plagiatów),

– ...

• Sformułowanie celu zadania badawczego,

• Relacje pomiędzy celem, zakresem i budżetem badań.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 16

8

2008-10-07

Wstępne przetworzenie dokumentów

• Transformacja dokumentów do postaci tekstowej,

• Usunięcie znaków formatujących,

• Ujednolicenie sposobu kodowania znaków.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 17

Reprezentacja informacji (1) – macierz częstości

• Zapamiętywany jest fakt lub liczba wystąpień danego słowa w dokumencie

• Pomija informację o kolejności słów

• Prowadzi do utworzenia macierzy częstości.

• Najbardziej rozpowszechniona – prosta i nie stwarzająca problemów obliczeniowych,

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 18

9

2008-10-07

Reprezentacja informacji (2) – reprezentacja listowa

• Poszczególne fragmenty dokumentu przechowywane są w postaci list.

• Zachowuje kolejność słów.

• Stwarza problemy obliczeniowe.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 19

Reprezentacja informacji (3) – drzewa i grafy

• Reprezentacja oparta na strukturach drzewiastych i grafowych

• Pozwala na uwzględnienie zależności hierarchicznych (drzewa)

• Stanowi dogodne narzędzie do reprezentacji struktury gramatycznej

• Pozwala reprezentować związki pomiędzy elementami (graf tworzący sieć semantyczną)

• Stwarza problemy obliczeniowe

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 20

10

2008-10-07

Tworzenie macierzy częstości

• Podział dokumentów na wyrazy

• Usunięcie wyrazów nieistotnych

• Przekształcenie wyrazów do formy podstawowej

• Utworzenie macierzy częstości

• Przekształcenie macierzy częstości

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 21

Wyznaczanie macierzy częstości (1)

• Podział dokumentów na wyrazy

Mowa jest srebrem, lecz milczenie złotem.

↓

mowa

jest

srebrem

lecz

milczenie

złotem

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 22

11

2008-10-07

Wyznaczanie macierzy częstości (2)

• Usunięcie słów nieistotnych (stop-lista)

Mowa jest srebrem, lecz milczenie złotem.

↓

mowa

jest

srebrem

lecz

milczenie

złotem

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 23

Wyznaczanie macierzy częstości (3)

• Przekształcenie wyrazów do formy podstawowej (rdzenia) Mowa jest srebrem, lecz milczenie złotem.

↓

mowa - mowa

jest - być

srebrem - srebro

lecz - lecz

milczenie - milczenie

złotem - złoto

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 24

12

2008-10-07

Wyznaczanie macierzy częstości (4)

• Utworzenie wspólnej listy dla wszystkich dokumentów Milczenie - przyjaciel który, nigdy nie zdradza

Książka to przyjaciel, który nigdy nie zdradzi

książka, który, milczenie, nie, nigdy, przyjaciel, to, zdradzać Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 25

Wyznaczanie macierzy częstości (5)

• Utworzenie macierzy częstości

Dokumenty

x – liczba wystąpień i-tego

ij

wyrazu w j-tym dokumencie

X

X =

Wyrazy

Zwykle uwzględnia się

tylko te wyrazy,

które występują

przynajmniej w dwóch

dokumentach

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 26

13

2008-10-07

Modyfikacje macierzy częstości (1)

• Reprezentacja binarna

2 0 4 ... 4

1 0 1 ... 1

1 0 3 ... 0

bin

1 0 1 ... 0

X

bi

b n

i

X

X =

Xb =

... ... ... ...

... ... ... ...

0 1 2 ... 1

0 1 1 ... 1

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 27

Modyfikacje macierzy częstości (2)

• Reprezentacja logarytmiczna

2 0 .. 4

1,301 0,000 .. 1,602

1 0 .. 0

lo

l g

o

1,000 0.000 .. 0,000

X

X =

Xlog =

.. .. .. ..

.. .. .. ..

0 1 .. 2

0,000 1,000 .. 1,301

x →

ij

1 + log(xij)

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 28

14

2008-10-07

Modyfikacje macierzy częstości (3)

• Ważona reprezentacja logarytmiczna

Reprezentacja logarytmiczna

x →

ij

1 + log(xij)

Ważona reprezentacja logarytmiczna

x →

ij

(1 + log(xij)) * log(N/dfi)

N - liczba wszystkich dokumentów

dfi - liczba dokumentów zawiejących i-ty wyraz Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 29

Modyfikacje macierzy częstości (4)

• Rozkład według wartości osobliwych

X = U S VT

X

=

U

S

VT

macierz U - wyrazy w przestrzeni wyznaczonej przez składowe macierz V - dokumenty w przestrzeni wyznaczonej przez składowe macierz S - macierz diagonalna, znaczenie kolejnych składowych Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 30

15

2008-10-07

Modyfikacje macierzy częstości (5)

• Rozkład według wartości osobliwych

X = U S VT

X

=

U

S

VT

współrzędne wyrazów: UrSr

współrzędne dokumentów: VrSr

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 31

Metody analizy macierzy częstości

• Metody taksonomiczne,

• Drzewa klasyfikacyjne i regresyjne,

• Sieci neuronowe,

• i inne ...

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 32

16

2008-10-07

Aforyzmy i przysłowia (1)

A.

Milczenie bywa wymowniejsze od mowy.

B.

Milczenie – przyjaciel, który nigdy nie zdradza.

C.

Często najmądrzejszą odpowiedzią jest milczenie.

D.

Mowa jest srebrem, lecz milczenie złotem.

E.

Mowa słodsza niż miód.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 33

Aforyzmy i przysłowia (2)

F.

Trucizna prawdy jest lepsza od miodu kłamstwa.

G.

Milsza prawda niż przyjaciel.

H.

Książka jest przyjacielem, który nigdy nie oszukuje.

I.

Książka to przyjaciel, który nigdy nie zdradza.

J.

Kto znalazł przyjaciela, skarb znalazł.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 34

17

2008-10-07

Aforyzmy i przysłowia (3)

K.

Nie ten przyjaciel, co cię chwali, ale ten, co ci prawdę powie.

L.

Pewnego przyjaciela poznaje się w niepewnym położeniu.

M. Pewnego przyjaciela poznaje się w sytuacji niepewnej.

N.

Ten przyjaciel, co prawdę mówi.

O.

Wierny bowiem przyjaciel potężną obroną, kto go znalazł, skarb znalazł.

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 35

Aforyzmy i przysłowia - ważona reprezentacja logarytmiczna, bez redukcji do rdzenia Metoda Warda

Milczenie bywa wymowniejsze od mowy

Często najmądrzejszą odpowiedzią jest milczenie

Milsza prawda niż przyjaciel

Ten przyjaciel, co prawdę mówi

Mowa jest srebrem, lecz milczenie złotem

Mowa słodsza niż miód

Milczenie - przyjaciel, który nigdy nie zdradza

Książka to przyjaciel. który nigdy nie zdradzi

Książka jest przyjacielem, który nigdy nie oszukuje Nie ten przyjaciel, co cię chwali, ale ten, co ci prawdę mówi Trucizna prawdy jest lepsza od miodu kłamstwa

Pewnego przyjaciela poznaj się w niepewnym połozeniu Pewnego przyjaciela poznaje się w sytuacji niepewnej Kto znalazł przyjaciela, skarb znalazł

Wierny bowiem przyjaciel potężną obroną, kto go znalazł, skarb znalazł

3 4 5 6 7 8 9 0 111

Odległość

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 36

wiąz.

18

2008-10-07

Klasyfikacja wybranych utworów literatury polskiej (1)

• Adam Mickiewicz, Dziady III

• Juliusz Słowacki, Kordian

• Stanisław Wyspiański, Noc Listopadowa

• Stanisław Wyspiański, Wesele

• Bolesław Prus, Katarynka

• Henryk Sienkiewicz, Janko Muzykant

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 37

Klasyfikacja wybranych utworów literatury polskiej (2)

• Maria Konopnicka, Nasza Szkapa

• Gabriela Zapolska, Moralność Pani Dulskiej

• Adam Mickiewicz, Pan Tadeusz

• Henryk Sienkiewicz, Krzyżacy (t. I)

• Eliza Orzeszkowa, Nad Niemnem (t. I)

• Władysław Reymont, Chłopi (t. I)

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 38

19

2008-10-07

Klasyfikacja wybranych utworów literatury polskiej ważona reprezentacja logarytmiczna, bez redukcji do rdzenia Metoda Warda

A. Mickiewicz, Dziady III

J. Słowacki, Kordian

S. Wyspiański, Noc Listopadowa

S. Wyspiański, Wesele

B. Prus, Katarynka

H. Sienkiewicz, Janko Muzykant

M. Konopnicka, Nasza szkapa

G. Zapolska, Moralność Pani Dulskiej

A. Mickiewicz, Pan Tadeusz

H. Sienkiewicz, Krzyżacy, t. I

E. Orzeszkowa, Nad Niemnem, t. I

W. Reymont, Chłopi, t. I

0

20

40

60

80

100

120

Paweł Lula, Katedra Systemów Obliczeniowych, Uniwersytet Ekonomiczny w Krakowie 39

Odległość wiąz.

20