podzial.pdf

PODZIAý DANYCH NAKLASY

Definicja

Dana jest macierz danych X. Podziałem P macierzy na k klas (klasyfikacją) nazywamy

przyporządkowanie indeksom wierszy macierzy k rozłącznych zbiorów I 1 , I 2 , ..., I k , takich,

Ŝe 4 j : 1

n j : n

Wiersze macierzy danych moŜna przestawiać. Dla prostoty uporządkujmy je tak, Ŝe

pierwszych n 1 wierszy zajmą elementy naleŜące do pierwszej klasy, kolejnych n 2

wierszy zajmą elementy naleŜące do drugiej klasy, ..., ostatnich n k wierszy zajmą

elementy naleŜące do ktej klasy:

X :

X ¾ 1 ¿

X ¾ 2 ¿

...

X ¾ k ¿

gdzie

X ¾ j ¿

: X n 1 + n 2 + ... + n j ? 1 + 1

, X n 1 + n 2 + ... + n j ? 1 + 2

, ..., X n 1 + n 2 + ... + n j ? 1 + n j

jest podmacierzą wymiaru n j ² p, zawierającą dane, naleŜące do jtej klasy.

Oznaczmy przez g j środek cięŜkości jtej klasy: g j : g ¼ X ¾ j ¿ ½ , oraz przez G P ¼ X ½

macierz środków cięŜkości klas podziału;

G P ¼ X ½ :

À g 1 Á n 1

À g 2 Á n 2

...

À g k Á n k

Lemat 1

g ¼ G P ¼ X ½½ : j : 1

p j g j : g ¼ X ½ d : g,

p j

d :

n j

g ¼ G P ¼ X ½½ : n G P ¼ X ½ T 1 n : n

1 n : n j : 1

À g 1 Á n 1 À g 2 Á n 2

... À g k Á n k

n j g j ,

g : n j : 1

i 5 I j X i : n j : 1

n j g j

I j : À 1, 2, ..., n Á . Wiersz X i naleŜy do jtej klasy, jeśli i 5 I j . Niech n j : # ¼ I j ½ .

Wtedy > j : 1

Twierdzenie 1 [Huygensa dla podziaþu]

J ¼ X ½ : j : 1

p j J ¼ X ¾ j ¿ ½ + J ¼ G P ¼ X ½½ :

d : J W ¼ P ½ + J M ¼ P ½

Funkcje J W ¼ P ½ i J M ¼ P ½ nazywają się bezwładnością wewnątrzklasową (J W ¼ P ½ ) i

bezwładnością międzyklasową ( J M ¼ P ½ ) podziału P.

J ¼ X ½ : n i : 1

m X i ? g m 2 : n j : 1

i 5 I j

m X i ? g m 2 :

: n j : 1

i 5 I j

m X i ? g j m 2 + m g j ? g m 2 + 2 µ X i ? g j , g j ? g ¶

Teza wynika z toŜsamości:

i 5 I j µ X i ? g j , g j ? g ¶ : i 5 I j ¼ X i ? g j ½ , g j ? g : µ 0, g j ? g ¶ : 0,

i 5 I j m X i ? g j m 2 : n j J ¼ X ¾ j ¿ ½ ,

n j : 1

i 5 I j

m g j ? g m 2 : J ¼ G P ¼ X ½½ .

Wniosek 1

J M ¼ P ½ : j : 1

p j m g j ? g m 2

klasyfikacja bez nauczyciela (grupowanie, analiza skupień)

Klasyfikacja z nauczycielem składa się z dwóch faz: uczenia i dyskryminacji. W

fazie uczenia zadany jest podział na k klas (podział wzorcowy). Na jego podstawie

wytwarza się funkcję dyskryminacyjną. Funkcja dyskryminacyjna przypisuje kaŜdemu

nowemu wektorowi numer klasy do której on naleŜy. Dobra funkcja dyskryminacyjna

ustala to przyporządkowanie z moŜliwie najmniejszym błędem.

Przykładem klasyfikacji z nauczycielem jest diagnostyka medyczna. W fazie uczenia

wypracowuje się metody diagnozy na podstawie znanych przypadków róŜnych chorób

(podział wzorcowy). Lekarz stosując swoją wiedzę (funkcję dyskryminacyjną) stara się

postawić dobrą diagnozę (ustala przyporządkowanie objawów do choroby z moŜliwie

najmniejszym błędem)

W klasyfikacji bez nauczyciela nie mamy podziału wzorcowego. W tym przypadku

naleŜy wytworzyć klasy tak, aby elementy naleŜące do jednej klasy były do siebie

podobne, a elementy z róŜnych klas były jak najbardziej do siebie niepodobne.

Przykładem klasyfikacji bez nauczyciela jest klasyfikacja, zaproponowana przez

Linneusza (1707 1778), w której do jednej klasy przypisał zwierzęta o podobnej

Zadaniem naszym będzie dobry podział (klasyfikacja) danych X na k klas. MoŜliwe

są dwa sposoby dokonania takiego podziału:

p klasyfikacja z nauczycielem, zwana dyskryminacją,

budowie zewnętrznej.

Grupowanie

W klasyfikacji bez nauczyciela elementy naleŜące do jednej klasy mają być do siebie

podobne, a elementy z róŜnych klas jak najbardziej do siebie niepodobne.

Miarą podobieństwa w klasie j moŜe być bezwładność tej klasy J ¼ X ¾ j ¿ ½ . Im mniejsza

ta liczba, tym bardziej podobne do siebie są elementy klasy. Podział P jest dobry gdy

średnia bezwładność we wszystkich klasach jest mała, czyli gdy bezwładność

wewnątrzklasowa J W ¼ P ½ jest mała.

Miarą niepodobieństwa (odległości ) między klasami moŜe być bezwładność

międzyklasowa J M ¼ P ½ . Im ona większa tym bardziej odległe są od siebie środki cięŜkości

klas.

Dobre grupowanie to takie, gdzie bezwładność J W ¼ P ½ jest mała a J M ¼ P ½ duŜa. Z

twierdzenia 1 wynika, Ŝe te warunki są równowaŜne.

Przykþad 1

Porównajmy dwa podziały zbioru

X :

1 1

2 2

3 3

3 4

4 3

5 2

Podział P: I 1 : À 1, 2 Á , I 2 : À 3, 4, 5, 6 Á .

2 ¼ 0.5 + 0.5 ½ : 0.5,

g ¼ X ¾ 2 ¿ ½ T : ¾ 3.75, 3.0 ¿ , J ¼ X ¾ 2 ¿ ½ : 1

4 ¼ 0.56 + 1.56 + 0.06 + 2.56 ½ : 1.18,

J W ¼ P ½ : 1

6 ¼ 2 D 0.5 + 4 D 1.18 ½ : 0.95

Podział Q: I 1 : À 5, 6 Á , I 2 : À 1, 2, 3, 4 Á .

2 ¼ 0.5 + 0.5 ½ : 0.5,

g ¼ X ¾ 2 ¿ ½ T : ¾ 2.25, 2.5 ¿ , J ¼ X ¾ 2 ¿ ½ : 1

4 ¼ 3.81 + 0.31 + 0.81 + 2.81 ½ : 1.94,

J W ¼ Q ½ : 1

6 ¼ 2 D 0.5 + 4 D 1.94 ½ : 1.46

Podział P jest lepszy od podziału Q, gdyŜ J W ¼ P ½ 9 J W ¼ Q ½ .

Podziały P i Q moŜna porównać, obliczając bezwładność międzyklasową (jest ona

prostsza do obliczenia):

g ¼ X ½ T : ¾ 3, 2.5 ¿

Dla podziału P

6 m g ¼ X ¾ 1 ¿ ½ ? g ¼ X ½ m 2 + 4

6 m g ¼ X ¾ 2 ¿ ½ ? g ¼ X ½ m 2 : 2

6 ¼ 1.5 2 + 1 2 ½ + 4

6 ¼ 0.75 2 + 0.5 2 ½ : 1.62

Dla podziału Q

g ¼ X ¾ 1 ¿ ½ T : ¾ 1.5, 1.5 ¿ , J ¼ X ¾ 1 ¿ ½ : 1

g ¼ X ¾ 1 ¿ ½ T : ¾ 4.5, 2.5 ¿ , J ¼ X ¾ 1 ¿ ½ : 1

J M ¼ P ½ : 2

J M ¼ P ½ : 2

6 m g ¼ X ¾ 1 ¿ ½ ? g ¼ X ½ m 2 + 4

6 m g ¼ X ¾ 2 ¿ ½ ? g ¼ X ½ m 2 : 2

6 ¼ 1.5 2 + 0 2 ½ + 4

6 ¼ 0.75 2 + 0 2 ½ : 1.12

Podział P jest lepszy od podziału Q, gdyŜ J M ¼ P ½ ; J M ¼ Q ½

Sprawdzając wszystkie 63 moŜliwe podziały na dwie klasy moŜna wyznaczyć

najlepszy podział. n

W ogólnym przypadku wybór najlepszego podziału przez sprawdzanie wszystkich

moŜliwych przypadków wymaga gigantycznej liczby obliczeń. Jeden z moŜliwych

sposobów, pozwalających uzyskać dobry, ale nie zawsze optymalny podział jest algorytm

pochłaniajacy, wykorzystujący podział na komórki Woronoja.

Definicja

Podział danych X na komórki Woronoja o centrach c 1 , c 2 , ..., c k jest rozbiciem X na klasy

I 1 , I 2 , ..., I k :

I j : À i : m X i ? c j m m X i ? c r m , r : 1, 2, ..., k, i 6 I 1 , I 2 , ...I j ? 1 Á

Komórki Woronoja składają się z punktów najbliŜszych centrom. Punkty leŜące w tej

samej odległości od kilku centrów naleŜą do komórki o najniŜszym numerze (umowa).

Twierdzenie 2

Niech P będzie podziałem Woronoja na komórki o centrach c 1 , c 2 , ..., c k . Niech Q

będzie podziałem Woronoja na komórki o centrach g ¼ X ¾ 1 ¿ ½ , g ¼ X ¾ 2 ¿ ½ , ..., g ¼ X ¾ k ¿ ½ . Podział Q

jest nie gorszy od podziału P.

Dowd

Niech P będzie podziałem na klasy I 1 , I 2 , ..., I k , Q podziałem na klasy

L 1 , L 2 , ..., L k , Y ¾ r ¿ podmacierzą X o wierszach, których numery naleŜą do L r .

Oznaczmy

n j : # ¼ X ¾ j ¿ ½ , m r : # ¼ Y ¾ r ¿ ½

Mamy:

J W ¼ P ½ : n j : 1

n j J ¼ X ¾ j ¿ ½ : n j : 1

n j d 2 ¼ X ¾ j ¿ , À g ¼ X ¾ j ¿ ½Á n j ½ :

: n j : 1

i 5 I j

m X i ? g ¼ X ¾ j ¿ ½m 2

Ostatnią sumę, dla ustalonego j, moŜna zapisać:

i 5 I j m X i ? g ¼ X ¾ j ¿ ½m 2

: r : 1

i 5 I j V L r

m X i ? g ¼ X ¾ j ¿ ½ m 2

: >

i 5 I j V L j

m X i ? g ¼ X ¾ j ¿ ½m 2 + r : 1

i 5 I r V Lj

¾ r j ¿m X i ? g ¼ X ¾ j ¿ ½m 2 + r : 1

i 5 I j V L r

¾ r j ¿m X i ? g ¼ X ¾ j ¿ ½m 2

+ r : 1

i 5 I j V L r

¾ r j ¿ m X i ? g ¼ X ¾ j ¿ ½ m 2 ? r : 1

i 5 I r V Lj

¾ r j ¿ m X i ? g ¼ X ¾ j ¿ ½ m 2

: m j d 2 ¼ Y ¾ j ¿ , À g ¼ X ¾ j ¿ ½Á m j ½ + r : 1

¾ r j ¿ >

i 5 I j V L r

m X i ? g ¼ X ¾ j ¿ ½ m 2 ? >

i 5 I r V Lj

m X i ? g ¼ X ¾ j ¿ ½ m 2

Ale z twierdzenia HuygensaPitagorasa

d 2 ¼ Y ¾ j ¿ , À g ¼ Y ¾ j ¿ ½Á m j ½ d 2 ¼ Y ¾ r ¿ , À g ¼ X ¾ j ¿ ½Á m j ½

Stąd

i 5 I j m X i ? g ¼ X ¾ j ¿ ½ m 2 m j d 2 ¼ Y ¾ j ¿ , À g ¼ Y ¾ j ¿ ½Á m j ½ + r : 1

¾ r j ¿ >

i 5 I j V L r

m X i ? g ¼ X ¾ j ¿ ½ m 2 ? >

i 5 I r V Lj

m X i ? g ¼ X ¾ j ¿ ½ m 2

Sumując po wszystkich j otrzymamy

J W ¼ P ½ J W ¼ Q ½ + n j : 1

r : 1

¾ r j ¿ >

i 5 I j V L r

m X i ? g ¼ X ¾ j ¿ ½ m 2 ? >

i 5 I r V Lj

m X i ? g ¼ X ¾ j ¿ ½ m 2

Korzystając z symetrii indeksów j i r moŜna zapisać:

j : 1

r : 1

¾ r j ¿ >

i 5 I j V L r

m X i ? g ¼ X ¾ j ¿ ½m 2 ? >

i 5 I r V Lj

m X i ? g ¼ X ¾ j ¿ ½m 2

: j : 1

r : 1

¾ r j ¿ >

i 5 I j V L r

m X i ? g ¼ X ¾ j ¿ ½m 2 ? >

i 5 I j V Lr

m X i ? g ¼ X ¾ r ¿ ½m 2

: j : 1

r : 1

i 5 I j V L r

¾ r j ¿ m X i ? g ¼ X ¾ j ¿ ½ m 2 ? m X i ? g ¼ X ¾ r ¿ ½ m 2

gdy i 5 I j V L r to wiersz X i zostanie przeniesiony z klasy j w podziale P do klasy r w

podziale Q, co oznacza Ŝe

m X i ? g ¼ X ¾ r ¿ ½ m m X i ? g ¼ X ¾ j ¿ ½ m

Wynika z tego, Ŝe

j : 1

r : 1

i 5 I j V L r

¾ r j ¿ m X i ? g ¼ X ¾ j ¿ ½m 2 ? m X i ? g ¼ X ¾ r ¿ ½m 2

a więc

J W ¼ P ½ J W ¼ Q ½

co kończy dowód. n

lemat 2 tw 3 przykład 2 n

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: