1. Cel ćwiczenia

Celem ćwiczenia jest zapoznanie się z najważniejszymi zagadnieniami związanymi z metodami

przeznaczonymi do grupowania i klasyfikacji danych.

2. Wprowadzenie teoretyczne

Większość materiałów znajdujących się w tej instrukcji została zaczerpnięta ze strony inter-

netowej projektu GRUPOWANIE-KLASYFIKACJA-SELEKCJA dostępnej pod adresem [1]:

http://ipkm.polsl.pl/PROJEKTY/Klas.

Grupowanie i klasyfikacja to zagadnienia związane z rozpoznawaniem wzorców (ang. pattern

recognition). Dotyczą one podziału zbioru elementów na podzbiory zwane grupami (ang. clu-

sters). Intuicyjnie mówiąc, podzbiory te mają tę właściwość, że elementy w tym samym pod

zbiorze są do siebie podobne. Rozpoznawanie wzorców jest obszarem badań, który zajmuje

się działaniem i projektowaniem systemów rozpoznających wzorce w danych. Zawiera takie

poddziedziny jak analiza dyskryminacyjna, selekcja cech, estymacja błędów, analiza grup

(razem nazywane czasem statystycznym rozpoznawaniem wzorców), wnioskowanie grama-

tyczne (czasem nazywane syntaktycznym rozpoznawaniem wzorców). Ważnymi obszarami

zastosowań są: analiza obrazów, rozpoznawanie pisma, analiza mowy, diagnozowanie ludzi i

maszyn, identyfikacja osób oraz badania przemysłowe.

Generalnie algorytmy klasyfikacji i grupowania ze względu na wykorzystywaną miarę

dzieli się na algorytmy wykorzystujące miary odległości i algorytmy wykorzystujące miary

podobieństwa.

2.1. Miary odległości

Odległość elementów x, y ∈ V jest wartością funkcji d(x, y) nazywanej funkcją odległości,

takiej że:

d : V × V → {r ∈ R

: r ≥ 0}

(1)

spełniająca warunki:

∀

x,y∈V

[d (x, x) ≤ d (x, y)]

(2)

∀

x,y∈V

[d (x, y) = d (y, x)]

(3)

∀

x,y,z∈V

[d (x, z) ≤ d (x, y) + d (y, z)]

(4)

gdzie: R

- zbiór liczb rzeczywistych.

Gliwice 2013-02-05

- 2/14 -

Najczęściej stosowaną funkcją odległości jest odległość euklidesowa:

2
1

(x, y) = (x − y) (x − y)

, ∀x, y ∈ V

(5)

Przyjęcie odległości euklidesowej związane jest z niedogodnościami wynikającymi z dużego

wpływu zmian skal współrzędnych na wyniki grupowania elementów przestrzeni cech. W celu

uniknięcia tych niedogodności zaleca się normalizować przestrzeń wartości cech tak, aby

zbiory wartości kolejnych współrzędnych posiadały zerową wartość średnią i jednostkowe

odchylenie standardowe. Ponadto dla uniezależnienia wyników porównania od wyboru układu

współrzędnych można dokonać obrotu układu współrzędnych, ustalając takie jego położenie,

które pokrywać się będzie z kierunkami osi głównych dla rozpatrywanego zbioru elementów

przestrzeni V . Kierunki te odpowiadać będą kierunkom wektorów własnych macierzy ko-

wariancji współrzędnych elementów v. Otrzymana w ten sposób przestrzeń nazywana jest

przestrzenią wartości cech głównych i oznaczana G

= π(V

Dla zróżnicowania wpływu poszczególnych współrzędnych na odległość elementów przestrzeni

można wprowadzić wagi współrzędnych. W przestrzeni wartości cech wagi współrzędnych

są wagami kolejnych cech. Prowadzi to do odległości Sebestyena:

2
2

(x, y) = (x − y) W (x − y)

, ∀x, y ∈ V

(6)

gdzie: W jest diagonalną macierzą wag:

W =








...

... w








(7)

Jeżeli przyjmuje się celowość zmiany układu współrzędnych przestrzeni V i przeprowadza się

jego obrót do położenia wyznaczonego przez osie główne, a następnie normalizację współ-

rzędnych w tak obróconym układzie, to dla wyznaczenia odległości euklidesowej w tej nowej

przestrzeni G można wykorzystać bezpośrednio współrzędne przestrzeni V i na ich podstawie

wyznaczyć tzw. odległość uogólnioną (Mahalanobisa):

2
3

(x, y) = (x − y) C

−1

(x − y)

, ∀x, y ∈ V

(8)

gdzie: C

−1

- odwrotna macierz kowariancji:

C =

j=1

− ¯

v) , v

∈ V

(9)

gdzie: n - liczba elementów rozpatrywanego zbioru w przestrzeni V ,

v - średni element rozpatrywanego zbioru:

v =

j=1

(10)

Gliwice 2013-02-05

- 3/14 -

Odległość uogólniona uwzględnia korelację współrzędnych. Opisane odległości d

, d

i d

po-

siadają niedogodność polegającą na dużej liczbie działań niezbędnych do ich wyznaczania, co

wpływa na czas wykonywania obliczeń podczas realizacji algorytmów grupowania wykorzystu-

jących te miary odległości. Dla zmniejszenia czasu obliczeń zaleca się stosowanie uśrednionej

odległości Hamminga (odległość Manhattan):

2
4

(x, y) =

i=1

|x [i] − y [i]|, ∀x, y ∈ V

(11)

Odmianą odległości Hamminga jest odległość Canbera:

2
5

(x, y) =

i=1

|x [i] − y [i]|

x [i] + y [i]

, ∀x, y ∈ V

(12)

2.2. Miary podobieństwa

Podobieństwo elementów x, y ∈ V jest wartością funkcji h(x, y) nazywanej funkcją podobień-

stwa, takiej że:

h : V × V → {r ∈ R

: 0 ≥ r ≥ 1}

(13)

spełniająca warunki:

∀

x,y∈V

[h (x, x) ≤ h (x, y)]

(14)

∀

x,y∈V

[h (x, y) = h (y, x)]

(15)

W większości przypadków zakłada się, że:

∀

x∈V

[h (x, x) = 1]

(16)

Funkcja podobieństwa może być określana bezpośrednio lub do jej określenia można wykorzy-

stać funkcję odległości, tzn. można definiować h(d) gdzie d jest wartością funkcji odległości

elementów przestrzeni wartości cech. Tak definiowana funkcja podobieństwa powinna spełniać

warunki:

h (0) = 1

(17)

∀

< d

⇒ h (d

) < h (d

)]

(18)

Z porównania różnych postaci funkcji odległości wynika, że w większości przypadków wartości

tych funkcji rosną ze wzrostem liczby wymiarów m przestrzeni V

, w której te odległości są

wyznaczane. Dla zmniejszenia wpływu liczby wymiarów przestrzeni wartości cech na wartość

funkcji podobieństwa elementów przeprowadza się skalowanie funkcji odległości przed wyko-

rzystaniem jej do określania funkcji podobieństwa:

• dla d

, d

i d

d (x, y) :=

d (x, y)

√

(19)

Gliwice 2013-02-05

- 4/14 -

• dla d

d (x, y) :=

d (x, y)

(20)

• dla d

d (x, y) := d (x, y)

(21)

Przykładami funkcji podobieństwa mogą być zależności:

(x, y) =

1 + αd (x, y)

(22)

(x, y) = 1 −





d (x, y)

max

(x,y)∈V ×V

(d (x, y))





(23)

(x, y) = exp (−αd (x, y))

(24)

gdzie: α, β - stałe warunkujące własności funkcji h.

Niezależnie od wprowadzonych wcześniej funkcji odległości d

do d

można wyznaczyć

funkcję podobieństwa elementów x, y bezpośrednio w postaci cosinusa kąta między

wektorami x, y w przestrzeni V :

(x, y) =

(25)

Powyższa funkcja podobieństwa jest niezależna od obrotu układu współrzędnych i jego skalo-

wania, lecz zależy od ewentualnych przesunięć tego układu.

2.3. Kryteria grupowania elementów

Grupowanie to podział skończonego zbioru V elementów v na L podzbiorów V

elementów

podobnych. Podział ten można zapisać w postaci rodziny Q(V ) podzbiorów V

zbioru V :

Q (V ) = {V

⊂ V : k ∈ [1 : L]}

(26)

Zbiór wszystkich możliwych (lub wszystkich dopuszczalnych) podziałów Q(V ) zbioru V na

L podzbiorów oznaczany jest Q

(V ). Podział Q będzie uznany za podział optymalny Q

opt

jeżeli funkcja kryterialna e(Q) wynikająca z przyjętego kryterium osiąga dla tego podziału

ekstremum, na przykład wartości minimalne:

Q = Q

opt

⇔ e (Q) = min

∈Q

(e (Q

))

(27)

Najprostsza funkcja kryterialna bazuje na funkcji odległości i ma następującą postać:

e (Q) =

1
¯

k=1

(28)

Gliwice 2013-02-05

- 5/14 -

gdzie:

Q - rodzina podzbiorów V

- średnia odległość elementów k-tego podzbioru V

od reprezentanta tego podzbioru.

Funkcja

podobieństwa

umożliwia

określenie

kryteriów

maksymalizujących

„spójność”

podzbiorów. Jedną z najprostszych funkcji kryterialnych jest:

e (Q) = −

k=1

(x,y)∈V

×V

h (x, y)

(29)

Szczególną grupę kryteriów stanowią kryteria progowe. Kryteria te mogą być określane przy

pomocy funkcji odległości lub funkcji podobieństwa elementów. Z wielu kryteriów tego typu

wyróżnić można dwa:

• kryterium „najdalszego sąsiada”

∀

∈Q

opt

∀

x,y∈V

[d (x, y) < d

max

]

(30)

• kryterium „najbliższego sąsiada”

∀

∈Q

opt

∀

x∈V

∃

y6=x

y∈V

[d (x, y) ≤ d

max

]

(31)

lub podobnie dla h (x, y) ≥ h

min

Zaletą tych kryteriów jest ich prostota oraz duża zgodność wyników grupowania opty-

malnego z wynikami grupowania realizowanego arbitralnie przez człowieka. Kryterium

„najbliższego sąsiada” uwypukla podobieństwa par elementów. Kryterium „najdalszego

sąsiada” uwypukla wpływ tzw. „izolowanych elementów” przestrzeni V . Stanowi to pewną

niedogodność ze względu na istnienie odchyleń elementów przestrzeni V wynikających z

określenia położenia tych elementów w tej przestrzeni na podstawie wielkości wyznaczanych

doświadczalnie. Dla częściowego uniezależnienia kryterium „najbliższego sąsiada” od tych

lokalnych odchyleń stosuje się kryterium „n najbliższych sąsiadów”:

∀

∈Q

opt

∀

x∈V

∃

(x)⊂V

∀

y∈s

(x)

[d (x, y) ≤ d

max

]

(32)

lub podobnie dla h (x, y) ≥ h

min

gdzie: S

(x) - n-elementowe otoczenie elementu x.

Liczbę uwzględnianych n najbliższych sąsiadów przyjmuje się w zależności od mocy

przestrzeni V oraz w zależności od liczby L poszukiwanych podzbiorów V

. Główną trudnością

związaną z praktycznym wykorzystaniem opisanych kryteriów progowych jest konieczność

przyjmowania wartości progowej h

min

lub d

max

. Przyjęcie tych wartości jest równoważne z

przyjęciem liczby zbiorów, na które dzielona jest przestrzeń V .

Gliwice 2013-02-05

- 6/14 -

2.4. Wybrane metody grupowania

2.4.1. Metoda najbliższego sąsiada (NN)

Na Rys. 1. pokazano przykład ilustrujący ideę metody najbliższego sąsiada (ang. nearest neigh-

bours, NN). Zakłada się, że nieznany element (oznaczony gwiazdką) zostanie zaklasyfikowany

do tego zbioru od którego dzieli go najkrótszy dystans.

Rysunek 1: Metoda najbliższego sąsiada [4]

Dla algorytmu najbliższego sąsiada sposób postępowania jest następujący:

1. Obliczenie odległości każdego elementu do jego najbliższego sąsiada.

2. Określenie sposobu obliczania wartości progowej (np. obliczenie wartości średniej i od-

chylenia standardowego dla wyników otrzymanych w kroku 1.).

3. Połączenie każdej pary elementów, której odległość jest mniejsza od wartości progowej

(np. gdy wartość jest mniejsza od µ + 3σ, Rys. 2.).

Rysunek 2: Przykład użycia metody NN do podziału zbioru z uwzględnieniem kryterium 3σ

Metoda ta daje dobre rezultaty tylko dla zbiorów elementów, w których można wyróżnić dobrze

rozdzielone podzbiory o stałym rozkładzie gęstości. W przeciwdymnym wypadku podział zbioru

będzie przeprowadzony błędnie (Rys. 3).

Gliwice 2013-02-05

- 7/14 -

4. Ponowne obliczenie wartości średniej d

mean

dla powstałego w kroku 3. zbioru.

5. Połączenie każdego elementu z jego najbliższym sąsiadem jeżeli ich odległość ≤ k·d

mean

Jeżeli brak innych zaleceń należy przyjąć k = 2. Przykład ilustrujący metodę MMD pokazano

na Rys. 7.

2.4.4. Algorytm drzewa minimalnego

Drzewo minimalne jest to taki graf połączeń, w którym każdy element jest połączony z innym,

nie występują obwody zamknięte, a suma długości krawędzi jest minimalna. Na Rys. 8. poka-

zano porównanie ważonego grafu liniowego, drzewa połączeń i drzewa minimalnego.

Rysunek 8: Grafy i drzewa. (a) Ważony graf liniowy. (b) Drzewo połączeń. (c) Drzewo mini-
malne.

Sposób postępowania w tej metodzie jest następujący:

1. Utworzenie drzewa minimalnego.

2. Usunięcie „nieodpowiednich” krawędzi według przyjętego kryterium, np. usuwa się kra-

wędzie, które są dwa razy dłuższe od średniej długości najbliższych krawędzi.

2.5. Ocena wyników procesu grupowania

Jakość podziału zbioru danych można określić:

1. Na podstawie ilorazu średniej odległości elementów w grupie i średniej odległości grup:

k=1

mean (d (v

, v

))

mean (d (V

, V

))

(33)

2. Na podstawie ilorazu sumy „momentów bezwładności” grup i „momentu bezwładności”

wszystkich elementów:

k=1

(34)

W przypadku pierwszej oceny wartość powinna wynosić około 0.5, a w przypadku drugiej oceny

około 0.1.

Gliwice 2013-02-05

- 10/14 -

3. Instrukcja obsługi programu PGrp

Program PGrp został pierwotnie napisany w programie Matlab [2], który jest produktem

komercyjnym. Jednak istnieje możliwość uruchomienia tego programu również w darmowym

środowisku GNU Octave [3]. W tym celu należy pobrać odpowiednią wersję tego środowiska

(program PGrp testowano na wersji 3.6.2) dla odpowiedniego systemu operacyjnego. Stan-

dardowo środowisko GNU Octave jest uruchamiane w wierszu poleceń. Nie jest to wygodny

sposób pracy z tym środowiskiem. Żeby poprawić komfort pracy można zainstalować nakładkę

graficzną o nazwie GUI Octave (ostatnia wersja ma numer 1.5.4).

W pakiecie użyto wybranych funkcji biblioteki KLAS (biblioteka procedur grupowania

i klasyfikacji elementów wielowymiarowych przestrzeni metrycznych) dostępnej pod ad-

resem [1]: http://ipkm.polsl.pl/PROJEKTY/Klas. Do tych funkcji należą: drzewo,

ksasiad, mmd, ocenap, pod, porwn oraz sasiad. Opis tych funkcji zamieszczono w ich

plikach źródłowych oraz na wskazanej stronie. Podczas tworzenia programu PGrp dodano

gotowe, opracowano nowe lub zmodyfikowano istniejące funkcje:

• checkSoft - funkcja sprawdza czy środowiskiem uruchomieniowym jest program Matlab

czy Octave.

• main - główna funkcja programu, równocześnie instrukcja uruchamiająca program.

• ostr2mat - funkcja potrzebna podczas uruchamiania programu w środowisku Octave.

• wykres - zmodyfikowana funkcja wykres dostępna w bibliotece KLAS; modyfikacja po-

legała na dodaniu instrukcji warunkowych z wywołaniem funkcji checkSoft umożliwiając

tym samym rozpoznanie środowiska uruchomieniowego.

Dodatkowo do programu dołączono cztery zbiory danych oznaczonych jako: z01.kig,

z04.kig, z05.kig oraz z06.kig.

Dalsza część tego opisu dotyczy środowiska GNU Octave dla systemu MS Windows

uruchomionego w wierszu poleceń. Zakłada się, że program PGrp znajduje się w katalogu

C:\PGrp. W celu uruchomienia programu PGrp należy:

1. Uruchomić program GNU Octave; plik startowy nazywa się octave.exe; pojawi się okno

z wierszem poleceń

2. Wpisać polecenie cd C:\PGrp i potwierdzić przyciskiem Enter; poleceniem ls można

sprawdzić czy program ma dostęp do katalogu

3. Wpisać polecenie main i potwierdzić przyciskiem Enter; w wierszu poleceń pojawi się

tekst pokazany na Wydruku 1.

Gliwice 2013-02-05

- 11/14 -

Wydruk 1: Ekran startowy programu PGrp

∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗

ALGORYTM GRUPOWANIA DANYCH

W y b i e r z dane do g r u p o w a n i a :

1 :

dane n r 1

2 :

dane n r 2

3 :

dane n r 3

4 :

dane n r 4

N a c i s n i j o d p o w i e d n i k l a w i s z ( d o m y s l n i e 1 ) :

Wydruk 2: Wybór metody grupowania

W y b i e r z a l g o r y t m g r u p o w a n i a :

1 :

2 :

k−NN

3 :

MMD

4 :

d r z e w a m i n i m a l n e g o

N a c i s n i j o d p o w i e d n i k l a w i s z ( d o m y s l n i e 1 ) :

Wydruk 3: Kolejne etapy pracy z programem PGrp dla metody k-NN

Wprowadz l i c z b e

n a j b l i z s z y c h s a s i a d o w ( d o m y s l n i e k=3) : 3

W y b i e r z m i a r e o d l e g l o s c i : 1− e u k l i d e s o w a , 2−Hamminga , 3−Canbera ,

4−M a h a l a n o b i s a , 5− p o d o b i e n s t w o " c o s i n u s k a t a m i e d z y w e k t o r a m i x , y " ,

6− p o d o b i e n s t w o na p o d s t a w i e f .

o d l e g l o s c i h=1/(1+a ∗ d^b ) ,

7− p o d o b i e n s t w o na p o d s t a w i e f .

o d l e g l o s c i h=e x p (−a ∗ d )

( d o m y s l n i e r =1) : 1

Ocena p r o c e s u g r u p o w a n i a 1 :

0 . 4 5 7 5 9

Ocena p r o c e s u g r u p o w a n i a 2 :

0 . 1 3 9 5 2

/// KONIEC PROGRAMU ///

Następnie:

1. W oknie pokazanym na Wydruku 1. należy określić zbiór danych, który będzie poddany

procesowi grupowania - należy wybrać z klawiatury odpowiedni numer i potwierdzić

przyciskiem Enter. UWAGA! Otworzy się nowe okno z wykresem dwuwymiarowym ilu-

strującym rozkład wybranych danych.

Gliwice 2013-02-05

- 12/14 -

2. W oknie pokazanym na Wydruku 2. należy wybrać metodę grupowania wprowadzając

odpowiedni numer z klawiatury i potwierdzić wybór przyciskiem Enter.

3. W kolejnym kroku, w zależności od wybranej metody grupowania, należy podać dodat-

kowy parametr:

(a) NN: nie dotyczy,

(b) k-NN: liczbę najbliższych sąsiadów, parametr k (Wydruk 3.),

(d) drzewa minimalnego: liczbę grup, parametr L.

4. Następnie, niezależnie od wybranej metody, należy wybrać miarę odległości lub podo-

bieństwa (Wydruk 3.): (1) odległość euklidesowa, (2) odległość Hamminga, (3) odległość

Canbera, (4) odległość Mahalanobisa, (5) podobieństwo „cosinus kąta między wektorami

x, y”, (6) podobieństwo na podstawie funkcji odległości h =

1+αd

, (7) podobieństwo

na podstawie funkcji odległości h = exp (−αd)

5. Po wprowadzeniu tych danych program wykona następujące czynności (Wydruk 3.):

(a) Przeprowadzi proces grupowania zgodnie z wprowadzonymi danymi.

(b) Zilustruje wynik procesu grupowania w formie wykresu dwuwymiarowego (Rys. 9).

(d) Zakończy swoje działanie

Rysunek 9: Przykładowy wynik procesu grupowania

Gliwice 2013-02-05

- 13/14 -

4. Sposób przeprowadzenia ćwiczenia

Przebieg ćwiczenia jest następujący:

1. Prowadzący wskazuje studentowi dane do grupowania.

2. Prowadzący wskazuje studentowi dwa algorytmy grupowania - metodę 1. i metodę 2.

3. Prowadzący wskazuje studentowi, które parametry należy zmieniać i, o ile jest to możliwe,

w jakim zakresie.

4. Student przeprowadza badania porównawcze polegające na tym, że:

(a) W ramach metody 1. zmieniane są wartości wybranych parametrów. Jako wyniki

odczytywane są wartości ocen jakości grupowania i wykres ilustrujący podział zbioru

wejściowego na grupy. Po przeprowadzeniu testów wyniki są porównywane między

sobą. Rezultaty porównania należy opracować w formie wniosków.

(b) W ramach metody 2. należy wykonać te same operacje jak w metodzie 1.

należy opracować w formie wniosków.

5. Przygotowanie do ćwiczenia

Przygotowanie do ćwiczenia obejmuje zapoznanie się z treścią niniejszej instrukcją oraz pro-

gramem PGrp. Wiadomości z omawianej dziedziny zostaną sprawdzone w ramach kartkowi

sprawdzającej przygotowanie do zajęć.

Literatura

[1] IPKM: Grupowanie-Klasyfikacja-Selekcja. [on-line] http://ipkm.polsl.pl/PROJEKTY/

Klas, ostatni dostęp: luty 2013.

[2] MathWorks: MATLAB. [on-line] http://www.mathworks.com/products/matlab/,

ostatni dostęp: luty 2013.

[3] MathWorks: GNU Octave. [on-line] http://www.gnu.org/software/octave/, ostatni

dostęp: luty 2013.

[4] Tadeusiewicz R., Flasiński M.: Rozpoznawanie obrazów. Wydawnictwo naukowe PWN,

Warszawa, 1991, [on-line] http://winntbg.bg.agh.edu.pl/skrypty/0005/, ostatni

dostęp: luty 2013.

Gliwice 2013-02-05

- 14/14 -

Document Outline