Metody analizy i

odkrywania wiedzy w

niekompletynych zbiorach

danych

Łukasz Ryniewicz 25.04.2007

Plan prezentacji

• Typy niekompletności informacji
• Metody uzupełniania danych

• Statystyczne
• k-najbliższych sąsiadów, drzewa

decyzyjne

• Metody analizy niekompletnych

danych

• Rozmyte reguły asocjacyjne
• Zbiory przybliżone i modyfikacje
• Modyfikacje algorytmów

Etapy eksploracji danych

Analiza problemu

dane

Selekcja i czyszczenie danych

dane wyselekcjonowane

Transformacja danych

•Wybór strategii co do
badania danych

•Konwersja

•Dyskretyzacja

•Zmiana reprezentacji z
relacyjnej na transakcyjną

dane przetworzone

Etapy eksploracji danych

Eksploracja danych

wzorce

Przygotowanie wyników do oceny

dane wygodne
do
analizowania

Analiza wyników

•Wybór
narzędzi

•Wybór
algorytmów

•Zastosowania
ich

Obróbka żeby było miłe dla oka

Zastosowanie uzyskanej wiedzy w praktyce

Typy niepełności danych

• Niepewność – gdy nie wiemy czy dane

są poprawne

• Niedokładność – np. gdy mamy dane

w postaci przedziałów: 100-200, dane
opisowe : dość ciepło

• Niekompletność – nie znamy wartości

atrybutu

• Niespójność – np. jednemu obiektowi

są przypisane różne wartości

• Ignorancja – gdy mamy brak wiedzy

Niekompletność

• Brakujące dane – są możliwe do

uzupełnienia

• chwilowa – nie jest dostępna dana w

momencie jej wstawiania

• niedokładność urządzeń, metod –

możliwe do oszacowania

• Niedostępne dane

• nie są możliwe do uzupełnienia,
• gdy są instancje do których nie mają

zastosowania wartości atrybutów (np.
baza z polami: bramki, strzelcy w
przypadku meczu bezbramkowego)

Model transakcyjny danych

A

B

C

d

1

0

1

1

1

2

*

0

*

1

3

1

*

2

1

4

0

1

2

1

5

1

*

1

0

6

0

1

*

0

A

a



A

a

a

V

V





U – zbiór obiektów

A – zbiór atrybutów

d - atrybut decyzyjny

dziedzina

})

{

,

(

d

A

U

DT







a

V

a

V

a

x

f

a

x

V

A

U

f







)

,

(

)

,

(

:

:



}

,...

2

,

1

:

{

n

j

K

K

j





- zbiór klas decyzyjnych

Metody stosowane podczas
transformacji danych

•

Usuwanie niekompletności danych

• Pomijanie obiektów zawierających braki

danych

• W bazach traznsakcyjnych pomijanie

brakującego atrybutu

• Zastępowanie brakujących wartości

• Użycie stałej – np. nowej nie występującej w

zbiorze wartości danego atrybutu

• Użycie mody, mediany, wartości średniej dla

wartości danego atrybutu

• Użycie metod data mining – np. k-najbliższych

sąsiadów gdzie porównujemy obiekt z
brakującą wartością z obiektami sąsiednimi i na
ich podstawie odtwarzamy brakujący atrybut

Metody statystyczne

• Procedury oparte na kompletnych rekordach – gdy

mało braków

• Procedury ważące – ustawiane są wagi rekordów by

zminimalizować odchylenia związane z brakami

• Procedury oparte o uzupełnianie danych

• Jawne w postaci formalnego modelu

(średnia, mediana, regresja, badanie

korelacji)

• Niejawne ukierunkowane na algorytmy

implikujące modele (uzupełnianie na

podstawie podobieństw, zastępowanie

innymi rekordami, zastępowanie stałymi)

• Procedury oparte o modele – definiuje się model

kompletnych danych i zależności są wyliczane na

podstawie rozkładu prawdopodobieństw

Metody statystyczne -
przykład

1. Podziel zbiór U na klasy decyzyjne

2. Dla każdej klasy wyznacz za

pomocą statystyki S

3. Dla każdego braku uzupełnij według

przynależności do odpowiedniej klasy
decyzyjnej

}

)

(

:

{

di

x

d

U

x

U

di







a

di

V

s 

*})

)

,

(

:

({











a

di

a

di

v

x

a

f

U

x

v

S

s

k-najbliższych sąsiadów

1. Bazę – U dzielimy na 2 podzbiory

• - przynajmniej 1 wartość

atrybutu nie jest znana

• - pozostałe

2. Dla każdego rekordu r należącego do

znajdujemy k najbliższych sąsiadów z
Odległość liczona tylko przy
wykorzystaniu znanych w r atrybutów.
Uzupełnienie braku (np. poprzez
wyznaczenie mody z wartości
atrybutów k sąsiadów i wstawienie jej
do r)

N

DR

N

DR

Z

DR

Z

DR

Drzewa decyzyjne

1. Bazę – U dzielimy na 2 podzbiory

• - przynajmniej 1 wartość atrybutu nie

jest znana

• - pozostałe

2. Wyznaczamy zbiór atrybutów gdzie pojawiła sie wartość

nieznana –

3. Dla każdego atrybutu a należącego do tworzymy

drzewo decyzyjne na podstawie gdzie każda

wartość a tworzy klasę decyzyjną

4. Klasyfikujemy rekord r z z brakującym atrybutem a

do odpowiedniej klasy

5. W przypadku gdy rekord r ma więcej niż jeden brak to:

1. Dla braku a klasyfikacja
2. W r uzupełnienie braku tylko wtedy gdy

osiągnięto liść

3. Powrót do 5.1
4. Gdy nie osiągamy już liści klasyfikujemy na

podstawie najbardziej licznego zbioru

N

DR

Z

DR

N

A

N

A

a

DT

Z

DR

N

DR

Metody stosowane na etapie
odkrywania wiedzy

• Użycie standardowych metod gdy

przeprowadziliśmy już proces
uzupełniania danych

• Użycie zmodyfikowanych metod analizy

pod kątem braków danych

• Użycie metod używających podejście

do danych i klasyfikacji zbiorów
rozmytych i przybliżonych

• Podejście probabilistycznie

•Dla każdego atrybutu jest definiowany zbiór
lingwistycznych termów które określają jakieś
pojęcie z dziedziny, np wysoki

• jest reprezentowany przez zbiór rozmyty na
dziedzinie A, ozn: d(A), o funkcji przynależności

Reguły asocjacyjne oparte na
zbiorach rozmytych

i

tA

L

]

1

,

0

[

)

(

:



A

d

i

tA

L



i

tA

L

•Stopień w jakim term charakteryzuje pewien
rekord r to wartość funkcji przynależności:

•Stopień w jakim zbiór termów
charakteryzuje rekord r to:

•Reprezentacja termów za pomocą zbiorów
rozmytych pozwala obliczyć stopień gdy
potrzebna wartość nie jest znana. Wtedy funkcja
zwraca wartość ½

Reguły asocjacyjne oparte na
zbiorach rozmytych

i

tA

L

)

.

(

)

,

(

i

L

tA

A

r

r

L

St

i

tA

i





m

t

tA

tA

tA

L

L

L

L

Z

,...,

,

:

2

1

)}

.

(

),...,

.

(

),

.

(

min{

)

,

(

2

1

2

1

m

L

L

L

L

A

r

A

r

A

r

r

Z

St

m

tA

tA

tA

t









)

,

(

r

L

St

i

tA

)

.

(

i

L

A

r

i

tA



•Generacja reguł dla różnych atrybutów
i w postaci:

Zamiast wsparcia jest liczona różnica
między prawdopodobieństwami:

Reguły asocjacyjne oparte na
zbiorach rozmytych











U

r

tA

U

r

tA

tA

tA

tA

r

L

St

r

L

L

St

L

L

ki

mj

ki

ki

mj

)

,

(

)

},

,

({

)

,

Pr(

mj

ki

tA

tA

L

L

R



:

k

A

m

A















U

r

tA

tA

Am

s

Ak

p

U

r

tA

tA

r

L

L

St

r

L

St

L

ms

kp

mj

mj

)

},

,

({

)

,

(

)

Pr(

Ai

-liczba termów zdefiniowana dla atrybutów Ai

•Jeżeli różnica ta jest statystycznie istotna,
wtedy jest akceptowana taka reguła i jest
obliczane zaufanie reguły

Reguły asocjacyjne oparte na
zbiorach rozmytych

)

|

Pr(

)

|

Pr(

log

)

,

(



j

p

tA

tA

tA

tA

tA

tA

o

mj

ki

mj

ki

mj

ki

L

L

L

L

L

L

W





•Dane wykluczone Dis(X)
•Obowiązująca baza vdb(X)

Rekord r jest wykluczony dla danego
zbioru X jeśli zawiera przynajmniej jedną
wartość nieznaną dla jednego atrybutu
który znajduje się w zbiorze X. Zbiór tych
rekordów – Dis(X), vdb(X) = U\Dis(X)

Definicje reguł asocjacyjnych
uwzględniające braki danych

)

(

)

(

X

vdb

U

X

wsparcie

X



X

X

XY

U

Y

Dis

U

U

Y

X

zaufanie









)

(

)

(

•Nieznane wartości atrybutu są zastępowane
przez wszystkie znane wartości. Każda wartość
w zastępuje nieznaną daną dla której
prawdopodobieństwo prob(w,a) jest równe
względnej częstości jej występowaniu w
wektorach dla których jest określona wartość
tego atrybutu.

•Wsparcie elementu elem(w,a) o wartości w z
dziedziny atrybutu a dla pojedynczego rekordu
r:

•Wsparcie zbioru
dla pojedynczego rekordu r:

Podejście probabilistyczne I



))

,

(

(

w

a

elem

probWsp

r







k

i

i

i

r

r

a

w

elem

probWsp

X

probWsp

1

))

,

(

(

)

(

{

1 gdy r.a = w

prob(w,a) gdy r.a = ?

0 w p. p.

)}

,

(

),...,

,

(

),

,

(

{

2

2

1

1

k

k

a

w

elem

a

w

elem

a

w

elem

X 

•Normalnie transakcja t wspiera zbiór X
albo nie

•Każdy element występujący w transakcji t
wspieranej przez k-elementowy zbiór Zk
wnosi 1/k do wartości całkowitego
wsparcia zbioru Zk

•Całkowita wartość wsparcia Zk jest sumą
wsparć wnoszone przez poszczególne
elementy

•Znalezienie rozkładu
prawdopodobieństwa na brakującym
atrybucie, i wtedy przemnażamy wartość
wnoszoną przez to prawdopodobieństwo

•Zk={a,b,c} t={a,b,*} p(c)=3/5
=> wsp(Zk)=1/3+1/3+(1/3)*(3/5)

Podejście probabilistyczne
II

Podejścia wykorzystujące
zbiory przybliżone – relacja
nierozróżnialności

A

B

)}

(

)

,

(

:

{

)

(

B

IND

x

y

U

y

x

I

B







)}

,

(

)

,

(

:

)

,

{(

)

(

a

y

f

a

x

f

U

U

y

x

B

IND

B

a













A

B

C

d

1

0

1

1

1

2

1

0

1

1

3

1

1

2

1

4

0

1

2

1

5

1

1

1

0

6

0

1

0

0

}

)

(

:

{

X

x

I

U

x

X

B

B









}

)

(

:

{













X

x

I

U

x

X

B

B

U

X 

X

B

X

B

X

B







)

(



Używana w algorytmach generacji reguł indukcyjnych

Współczynnik aproksymacji:

Przybliżenia zbiorów klas decyzyjnych
służy do utworzenia zbioru reguł
decyzyjnych w postaci:

Gdzie

Relacja nierozróżnialności może być
stosowana jedynie w kompletnych
zbiorach, dlatego istnieją jej modyfikacje

Podejścia wykorzystujące
zbiory przybliżone – relacja
nierozróżnialności

)

)

,

(

(

d

v

x

d

f

P





)

,

:

)

,

(

(

ai

ai

i

ai

i

V

v

A

a

v

x

a

f

P









Podejścia wykorzystujące
zbiory przybliżone - relacja
tolerancji

A

B

*}

)

,

(

*

)

,

(







a

y

f

a

x

f















)

,

(

)

,

(

:

)

,

{(

)

(

a

y

f

a

x

f

U

U

y

x

B

T

B

a

A

B

C

d

1

0

1

1

1

2

1

*

1

1

3

1

1

*

1

4

0

1

2

1

5

*

*

1

0

6

0

1

0

0

}

)

(

:

{

X

x

T

U

x

X

B

B









}

)

(

:

{













X

x

T

U

x

X

B

B

U

X 

X

B

X

B

X

B







)

(



Używana w algorytmach generacji reguł indukcyjnych

Używana przy uzupełnianiu braków

•Elementów podobnych do x

•Elementów do których x jest podobny

Podejścia wykorzystujące
zbiory przybliżone - relacja
podobieństwa

A

B

)

,

(

)

,

(

*

)

,

(

:

y

a

f

x

a

f

y

a

f

x

yS

B

a

B













A

B

C

d

1

0

1

1

1

2

1

*

1

1

3

1

1

*

1

4

0

1

2

1

5

*

*

1

0

6

0

1

0

0

}

:

{

)

(

x

yS

U

y

x

S

B

B





}

)

(

:

{

)

(

1

X

x

S

U

x

X

B

B











Używana w algorytmach generacji reguł indukcyjnych

y podobny do x

Dla każdego x są definiowane 2 klasy:

}

:

{

)

(

1

y

xS

U

y

x

S

B

B









}

:

)

(

{

)

(

X

x

x

S

X

B

B







Podejścia wykorzystujące zbiory
przybliżone – rozmyta relacja
podobieństwa



)

,

( y

x

R

a

a

b

c

D

X1

1

2

3

1

X2

*

2

3

1

X3

*

*

3

2

•Intuicja- x2 jest bardziej podobny do
x1 niż x3 do x1

•Zwykła relacja tolerancji nie
rozróżnia

•Zakładamy że pod brakującymi
wartościami dla ustalonego atrybutu
może występować znana wartość z
jednakowym prawdopodobieństwem

•Podobieństwo obiektów x,y
względem a można zapisać:

*

)

,

(

*

)

,

(

1

*)

)

,

(

*

)

,

(

(

*)

)

,

(

*

)

,

(

(

1

*

)

,

(

*

)

,

(

)

,

(

)

,

(

0

*

)

,

(

)

,

(

1

2



































y

a

f

x

a

f

V

y

a

f

x

a

f

y

a

f

x

a

f

V

y

a

f

x

a

f

y

a

f

x

a

f

y

a

f

x

a

f

a

a







B

a

a

A

y

x

R

y

x

B

R

)

,

(

)

,

)(

(

I możemy zapisać
rozmytą relacje
podobieństwa:

•Metoda polega na klasyfikacji n>2 klas decyzyjnych
•Tworzone są klasyfikatory niezależne Cij których
celem jest stwierdzenie czy nowy obiekt należy do
klasy i-tej czy j-tej (odpowiednio Cij = 1, Cij = 0)

•Do budowy klasyfikatorów są wykorzystywane
powyższe relacje które pozwalają stwierdzić do
której klasy bardziej obiekt klasyfikowany należy

•Do każdego klasyfikatora określa sie współczynnik
wiarygodności w fazie uczenia

•Decyzja klasyfikacyjna:

Metoda kwadratowa

i

ij

i

ij

ncor

nerror

ncor

P













i

j

ij

ij

i

i

x

C

P

S

i

x

d

)}

(

{

max

)

(

Oczekiwana ilość informacji potrzebna do
klasyfikacji:

Maksymalizujemy przyrost informacji
G(U,T) w wyniku podziału testem T:

Żeby uniknąć zbyt wielkiej ilości podziałów
wprowadzamy współczynnik:

Gdzie P(U,T) – wartość informacyjna testu:

Drzewa decyzyjne – C4.5

U

Ki

U

K

U

I

n

i

i

log

)

(

1









)

(

)

(

)

,

(

1

i

k

i

i

U

I

U

U

U

I

T

U

G









)

,

(

)

,

(

)

,

(

T

U

P

T

U

G

T

U

WI



U

U

U

U

T

U

P

i

k

i

i

log

)

,

(

1









Uo – zbiór tych obiektów w których
występuje brak na atrybucie potrzebnym do
testu T
Przyrost informacji

Wartość informacyjna testu

Drzewa decyzyjne – C4.5
modyfikacja

)

,

(

)

,

(

'

0

0

T

U

U

G

U

U

U

T

U

G







U

U

U

U

U

U

U

U

T

U

P

i

k

i

i

o

log

log

)

,

(

1

0











Drzewa decyzyjne – podejście
probabilistyczne

T

L

I 

)

)

(

,...,

)

(

|

)

(

(

...

)

)

(

|

)

(

(

)

)

(

(

)

|

(

1

1

1

1

1

1

2

2

1

1

























m

m

m

m

r

x

t

r

x

t

r

x

t

P

r

x

t

r

x

t

P

r

x

t

P

x

I

P

t1

t2

t3

tm

I

n1

n2

n3

nm

T:

r1

r2

rm

m

n

n ,...,

1

m

t

t ,...,

1

m

m

R

r

R

r



 ,...,

1

1

-liść

-węzły

-testy

-wyniki testów

Dla przykładu x (bez braków
danych) prawdopodobieństwo
osiągnięcia liścia I wynosi:

Gdy wyniki testów są znane (x nie zawiera braków
potrzebnych przy testach) to prawdopodobieństwo
osiągnięcia liścia wynosi 0 lub 1

Drzewa decyzyjne – podejście
probabilistyczne

Jeżeli test tk w węźle nk nie może być ustalony
dokładnie (występuje brak danych) to możemy
przyjąć prawdopodobieństwo z rozkładu Ω
określone następująco:

]

[

,

]

[

,

,

1

1

1

1

)

)

(

,...,

)

(

|

)

(

(

k

k

k

k

k

k

t

n

T

t

r

t

n

T

k

k

k

k

x

U

U

r

x

t

r

x

t

r

x

t

P

















Gdzie podzbiór przykładów dla których wartość testu jest znana

]

[t

U

Metoda podziału

Polega na podzieleniu danych na
mniejsze porcje tak by nie zawierały one
braków i niosły maksymalną ilość
informacji o klasyfikacji. Następnie dla
każdej porcji jest stosowany odrębny
model klasyfikacji, i następuje synteza
wyników

a

b

c

d

1

0

*

1

0

1

*

1

0

1

1

0

1

1

0

1

*

0

1

0

*

1

0

0

a

b

d

1

0

1

0

1

1

0

1

0

1

1

1

b c

d

1 1

0

1 0

1

0 1

0

1 0

0

a

b

c

d

0

1

1

0

1

1

0

1

M1

M2

M3

d

1

1

0

1

0

0

a

b

d

1

0

1

0

1

1

0

1

0

1

1

1

b c

d

1 1

0

1 0

1

0 1

0

1 0

0

a

b

c

d

0

1

1

0

1

1

0

1

Literatura

•Imieliński T., Lipiński W., Incomplete Information in Relational
Databases, Journal of the AEM, tom 31, 1984

•Chan K. C. C., Wai-Ho A., Mining Fuzzy Association Rules,
Proceedings of the Sixth International Conference on Information and
Knowledge Managment, Las Vegas, 1997

•Regel A., Cremilleux B., Treatment of Missing Values for Association
Rules, Proceedings of Research and Development in Knowledge
Discovery and Data Mining, Second Pacific-Asia Conference, PAKDD-
98, Melbourne, 1998

•Protaziuk G., Odkrywanie wiedzy w niekopletnych zbiorach danych,
rozprawa doktorska, Warszawa 2005

•Kryszewicz M., Rybiński H., Incomplete database issues for
representative association rules, Proceedings of Foundations of
Inteligent Systems, 11th International Symposium, Warszawa 1999

•Nayak J. R., Cook D. J., Approximate Association Rule Mining,
Proceedings of the Fourteenth International Articital Inteligence
Research Society Conference, Key West, Floryda, 2001

•Feelders A., Handling missing data in trees: surrogate splits of
statistical ipmutation?, Proceedings of Principles of Data Mining and
Knowledge Discovery Third European Confereance, PKDD ’99, Praga,
1999

Dziękuję za
uwagę