Strona główna

Uniwersytet łÓdzki wydział Ekonomiczno-Socjologiczny Kierunek: Informatyka I Ekonometria


Pobieranie 256.78 Kb.
Strona1/3
Data19.06.2016
Rozmiar256.78 Kb.
  1   2   3
UNIWERSYTET ŁÓDZKI



Wydział Ekonomiczno-Socjologiczny

Kierunek:



Informatyka i Ekonometria

Specjalność:



Komputerowe Metody Badań Operacyjnych

Bartłomiej Frydrych

nr albumu 106752


Metody klasyfikacji obiektów wielocechowych. Program w języku JAVA


Praca magisterska napisana

w Katedrze Badań Operacyjnych

pod kierunkiem

Dr Iwony Konarzewskiej



Łódź 2009
Spis treści

Uniwersytet Łódzki 73

OŚWIADCZENIE 73

Dane studenta 75

Tytuł pracy w języku polskim 75



Tytuł pracy w języku angielskim 75

Wprowadzenie
Celem pracy jest przedstawienie wybranych metod hierarchicznego porządkowania obiektów oraz przykładu praktycznego zastosowania metod do porównania struktury rynku funduszy inwestycyjnych we wrześniu roku 2007 oraz wrześniu roku 2008. Do zaprezentowania części praktycznej zostanie stworzony program komputerowy napisany w języku JAVA, wykorzystujący metody opisane w pracy oraz przedstawiający wyniki.

Wykorzystywane źródła to istniejący materiał teoretyczny zawarty w literaturze dotyczącej poruszanej tematyki. Podstawowym źródłem na którym się oparłem była pozycje1. W części empirycznej nieocenioną pomocą były źródła 2. Źródłem danych jest serwis internetowy www.bankier.pl.

Dyscyplina naukowa zajmująca się metodami klasyfikacji i porządkowania obiektów wielocechowych nosi nazwę wielowymiarowej analizy porównawczej ( WAP ). Metody WAP stosuje się w celu przekształcenia wielowymiarowej przestrzeni zmiennych diagnostycznych na jednowymiarową przestrzeń zmiennej syntetycznej.

W ramach WAP wyróżnia się metody taksonomiczne rozwiązujące następujące problemy:

Badanie podobieństw obiektów w zakresie poziomu zjawiska złożonego

Szeregowanie obiektów pod względem poziomu zjawiska złożonego

W pracy zostaną przedstawione metody z pierwszej grupy3.
Praca składa się z pięciu rozdziałów. W rozdziale pierwszym zostały formalnie przedstawione elementarne pojęcia i definicje takie jak pojęcie porządkowania, klasyfikacji oraz pojęcie danej.

W rozdziale drugim zostały formalnie przedstawione pojęcia oraz metody z które są wykorzystywane w procedurach klasyfikujących. Zostało wyjaśnione pojęcie skupienia, normalizacji zmiennych, odległości między obiektami, odległości między skupieniami oraz zostały przedstawione metody służące do wyznaczania tych wielkości.

Rozdział trzeci zawiera przedstawienie konkretnych procedur klasyfikacyjnych takich jak metodę grupowania, podziału oraz taksonomii wrocławskiej4.

Rozdział czwarty zawiera formalne definicje mierników służących do weryfikacji dokonanego podziału.

W rozdziale piątym zostało przedstawione badanie struktury rynku funduszy inwestycyjnych we wrześniu 2007 oraz wrześniu 2008 przy wykorzystaniu przedstawionych metod oraz aplikacji Klasyfikacja Danych.

Rozdział I
DEFINICJA PODSTAWOWYCH POJĘC


1.1 Pojęcie klasyfikacji
Każdą relację binarną R na zbiorze X definiuje się jako podzbiór iloczynu kartezjańskiego X x X Podzbiór taki można utożsamić z funkcją charakterystyczną:
(1.1) R : X x X → { 0, 1 },
Zdefiniowaną następująco:
(1.2)

gdzie: 1, jeśli x, y są w relacji R,

0, w przeciwnym razie
Klasyfikacja jest czynnością poznawczą, której odpowiadają relacje binarne zwane klasyfikującymi. Relacją klasyfikacji jest każda relacja binarna posiadająca przynajmniej dwie następujące własności: zwrotność i symetrię.

Klasyfikacja jest czynnością podziału zbioru na podzbiory nazywane klasami. Podziałem zbioru X nazywa się każdy zupełny i rozłączny układ podzbiorów tego zbioru, tzn. układ X1, X2, ..., Xn taki, że:


(1.3) dla oraz
Każdy taki podział jest generowany przez odpowiednią relację równoważności i odwrotnie – każda relacja równoważności określa podział zbioru. Relacja równoważności definiowana jako relacja binarna R spełniająca następujące trzy warunki:
Zwrotności, tzn. R(x, x) = 1

Symetrii, tzn R(x, y) = 1 to R(y, x) = 1

Przechodniości, tzn jeśli R(x, y) = 1 oraz R(y, z) = 1, to R(x, z) = 1
Relacja równoważności jest jedną z najbardziej typowych relacji, zwanych relacjami klasyfikującymi. Podstawowe rodzaje relacji klasyfikujących są następujące:
Relacja identyczności

Relacja równoważności

Relacja tolerancji

Relacja podobieństwa


Każda z powyższych relacji dzieli zbiór na rozłączne podzbiory, zwane klasami. Prawdziwe też jest stwierdzenie odwrotne, tzn. każdy zupełny i rozłączny podział danego zbioru wyznacza odpowiadającą mu relację równoważności.

Dzielenie zbioru na klasy nazywa się klasyfikacją, dokonuje się jej zwykle ze względu na jakąś cechę charakteryzującą elementy klasyfikowanego zbioru.


Z pojęciem klasyfikacji związane są dwa inne pojęcia: dyskryminacja i rozpoznawanie obrazów.

Załóżmy, że o pewnej części zbioru elementów wiemy, że należą do jednej klasy, o innej zaś części wiemy, że należą do drugiej klasy. Analizują te dane, chcemy odkryć regułę, według której elementy całego zbioru można podzielić na te dwie klasy. Proces ten nazywamy procesem dyskryminacji zbioru. Jeżeli regułę rozdziału formułuje się w postaci pewnej funkcji, to funkcję tę nazywa się funkcją dyskryminacyjną.

Typowe zagadnienie rozpoznawania obrazów jest następujące. Zakłada się, że dane są typowe wzorce lub przedstawiciele klas i zadanie polega na tym, aby rozpoznać, do której klasy należy zadany dowolny inny element zbioru.

Elementy wzorcowe często nazywa się obrazami. Większość metod rozpoznawania obrazów wykorzystuje pojęcie podobieństwa między elementami. Podobieństwo jest to również relacja binarna, która definiowana jest zwykle w postaci tzw. relacji metrycznej lub ważonej. Oznacza to, że relację taką definiuje się za pomocą uogólnionych funkcji charakterystycznych:


(1.4) R : X x X → [ 0, 1 ]
Wartość R (x, y) interpretuje się wówczas jako wagę związku wiążącego elementy xi i xj. Jeden ze sposobów definiowania takich relacji polega na wykorzystaniu metryki.

Załóżmy, że na zbiorze X określona jest metryka d unormowana na odcinek [ 0, 1 ], wówczas stopień podobieństwa R ( xi, xj ) określa się jako pewną odwrotność odległości d ( xi, xj ). Odwrotność taką można określić za pomocą jednego z następujących wzorów:


(1.5) R ( xi, xj ) = 1 – d ( xi, xj )

(1.6) R ( xi, xj ) = 1 / d (xi, xj )

(1.7) R ( xi, xj ) = 1/ (1 + d ( xi, xj ) )
W przypadku relacji podobieństwa dokonuje się tzw. hierarchicznej klasyfikacji. W pewnym uproszczeniu oznacza to, że dokonuje się nie jednej, lecz wielu klasyfikacji na różnych poziomach stopnia powiązania elementów.

Przyjmując pewien poziom 0 < α < 1, można określić relację


(1.8) Rα ( xi, xj ) =

gdzie: 1, jeśli R ( xi, xj ) ≥ α

0, w przeciwnym razie
i wykorzystać ją do podziału zbioru na klasy. Przyjmując różne wartości α, uzyskuje się różne podziały.

1.2 Pojęcie porządkowania
Porządkowanie zbioru w rozumieniu intuicyjnym oznacza ustawienie jego elementów w kolejności od najmniejszego do największego lub odwrotnie. Z formalnego punktu widzenia oznacza to określenie, który z danych dwóch elementów zbioru jest wcześniejszy, a który późniejszy.

Tak, więc i w tym przypadku określa się relację binarną, nazywaną relacją porządku. Istnieje wiele typów takich relacji. Wszystkie spełniają dwa warunki:


- niesymetryczności

- przechodniości


Warunki te oznaczają, że jeśli A jest mniejsze niż B, to B nie może być mniejsze niż A. Z faktu, że A jest mniejsze od B, a przy tym B jest mniejsze od C, wynika, że A jest mniejsze od C.

1.3 Pojęcie danych
Załóżmy, że dany jest dowolny zbiór obiektów empirycznych E. Przedmioty te są uporządkowane ze względu na nasilenie pewnej cechy X według relacji ρ, która jest relacją porządku. Parę złożoną ze zbioru E oraz relacji ρ, tzn. ( E, ρ ) złożoną ze zbioru liczb rzeczywistych i relacji mniejszości, nazywa się teoretycznym systemem relacyjnym.

Przyporządkowanie liczb elementom zbioru E, jest odwzorowaniem:


(1.9) m: E → R
Jeśli odwzorowanie to jest homomorfizmem, tzn. jeśli spełnia warunki:
(1.10) a ≈ b ↔ m ( a ) = m ( b ),

(1.11) a ρ b ↔ m ( a ) < m ( b )


dla dowolnych , to nazywa się je pomiarem.

Załóżmy, że funkcja m spełniająca te dwa warunki została ustalona. Jeśli okaże się, że dowolnej funkcji rosnącej φ: R → R warunki te będą spełnione również dla nowej funkcji określonej według wzoru:


(1.12) m’ ( a ) = φ ( m (a ) ),
to można powiedzieć, że została ustalona porządkowa skala pomiaru.
Rodzaj skali zależy od tego, jakie przekształcenia są dopuszczalne na uzyskanych liczbach. Jeśli dopuszczalne są przekształcenia określone za pomocą funkcji rosnących, to skalę nazywa się skalą porządkową. Formalnie skalę porządkową definiuje się, więc jakie odwzorowanie:
(1.13) m: E → R,
takie, że
(1.14) a ≈ b ↔ m ( a ) = m ( b ),

(1.15) a ρ b ↔ m ( a ) < m ( b )


oraz takie, że warunki te są spełnione przez odwzorowanie:
(1.16) m’ E → R
określone wzorem:
(1.17) m’ ( a ) = φ ( m ( a ) ), dla każdego φ Φ, gdzie Φ = { φ: R → R | jest φ rosnąca }.
Za pomocą zbioru dopuszczalnych przekształceń Φ definiowane są wszystkie typy skal. Zbiór Φ powinien być grupą ze względu na złożenie funkcji. Istnieje wiele typów skal pomiarowych. Oprócz skali porządkowej najważniejsze to:
Jeśli Φ = { φ: R1 → R1 | φ ( z ) = a * z + b, a > 0 }, to m nazywa się skalą przedziałową

Jeśli Φ = { φ | φ ( z ) = a * z, a > 0 }, to m nazywa się skalą stosunkową

Jeśli Φ = { φ | φ ( z ) = z }, to m nazywa się skalą absolutną.
Załóżmy, że dana jest próbka losowa X1, ..., Xn oraz określona na niej pewna statystyka T = T (X1, ..., Xn ). Przyjmijmy, że wszystkie obserwacje, tzn. wartości x1, x2, ...,xn, są mierzone w tej samej skali dopuszczającej przekształcenia φ z pewnej grupy Φ.

Statystykę T nazywa się statystyką adekwatną względem skali określonej przez grupę Φ, jeśli wielkości T oraz φ ( T ) są statystycznie nierozróżnialne dla wszystkich φ Φ, tzn., jeżeli rozkłady statystyk T oraz φ ( T ) są takie same.

Podana definicja jest równoważna pojęciu Φ – stabilności. Statystyka T nazywa się Φ – stabilna, jeśli zachodzi równość:
(1.18) T (φ ( x1 ), ..., φ ( xn ) ) = φ ( T ( x1, ..., xn ) ),
dla dowolnych ( x1, ..., xn ) Rn oraz φ Φ.

Rozdział II
PRZEDSTAWIENIE METOD I POJĘĆ WYKORZYSTYWANYCH W PROCEDURACH KLASYFIKACYJNYCH


2.1 Odległości między obiektami
Zakładamy, że dana jest realizacja próby n – elementowej pobranej z populacji, w której badana jest p – wymiarowa zmienna losowa ( X1, X2, ...,Xn ). Obserwacje takie wygodnie jest przedstawić w formie macierzy danych X postaci ( ... ), gdzie i – ty ( i = 1, ..., n ) wiersz macierzy X wyznacza wektor wierszowy

xi = [ xi1, xi2, ..., xip ] wartości cech X1, X2, ..., Xp dla obiektu i.



2.1.1 Opisowa definicja odległości
Mała odległość między obiektami oznacza bliskość lub podobieństwo tych obiektów. Znaczna odległość między dwoma obiektami jest synonimem oddalania lub niepodobieństwa rozważanych obiektów.

W wielowymiarowej analizie statystycznej stosuje się wiele różnych miar odległości. Jest to spowodowane tym, że w matematyce odległością między dwoma elementami i oraz j może być dowolna funkcja rzeczywista dij taka, że

1 o dij ≥ 0,2 o dij = 0,3 o dij = dji, 4 o dij ≤ dik + dkj

2.1.2 Procedury normalizacji zmiennych
Warunkiem umożliwiającym wyznaczenie mierników odległości jest normalizacja zmiennych, której celem jest:

Doprowadzenie różnoimiennych cech do wzajemnej porównywalności (postulat addytywności).

Ujednolicenie charakteru zmiennych, przez przekształcenie destymulant w stymulanty lub odwrotnie (postulat jednolitej preferencji).

Wyeliminowanie z obliczeń wartości niedodatnich (postulat dodatniości).

Zastąpienie zróżnicowanych zakresów zmienności poszczególnych cech zakresem stałym (postulat stałości rozstępu lub stałości wartości ekstremalnych).
Procedury normalizacji opierają się na wzorze:

(2.1) (i = 1, …,n)

gdzie: xi, - wyjściowe wartości i – tej realizacji zmiennej;

xi - znormalizowane wartości i – tej realizacji zmiennej;

n – liczba obserwacji;
A, B oraz p to parametry, które w zależności od sposobu normalizacji mogą przyjmować różne wartości.

Wartości tych parametrów dla najczęściej spotykanych procedur normalizacji przedstawia tabela 2.1

Tabela 2.1

Wartości parametrów A, B, p dla wybranych procedur normalizacji zmiennych



Procedura normalizacji

A

B

p

Przekształcenia ilorazowe

0

xmax, xmin



1

Standaryzacja

0,

sx

1, 2, …

Unitaryzacja

0, xmax, xmin

xmax - xmin

½, 1, 2, …

Źródło: [Grabiński T., Wydymus S., Zeliaś A., Metody taksonomii numerycznej w modelowaniu zjawisk społeczno – gospodarczych, PWN, Warszawa, 1989]
Przykład procedury przekształcenia ilorazowego:

(2.2)


Przykład procedury standaryzacji:

(2.3)


Przykład procedury unitaryzacji:

(2.4)


Aby ujednolicić charakter zmiennych należy wykorzystać wartości znormalizowane, stosując wzór:

(2.5) (i = 1, …, n)

gdzie {XS} oraz {XD} to zbiór stymulant i destymulant.

Wyeliminowanie wartości niedodatnich uzyskuje się za pomocą przekształcenia:

(2.6) ( i = 1, …, n; j = 1, …, m )

gdzie n, m to liczba obserwacji i liczba zmiennych.


Stałą δ wyznacza się ze wzoru:

(2.7)

gdzie to wartość minimalna w całej macierzy danych znormalizowanych, natomiast Sx” to odchylenie standardowe wszystkich elementów tej macierzy.

2.1.3 Przedstawienie wybranych miar odległości
Najbardziej ogólną formułą miernika odległości jest formuła Minkowskiego

(2.8) ( i, k = 1, …, n )

gdzie n, m to odpowiednia liczba obiektów i liczba zmiennych, xij, xkj to znormalizowane wartości j – tej zmiennej dla i – tego oraz k – tego obiektu.
Jeśli współczynnik p we wzorze ( 2.8 ) przyjmie wartość 2, otrzymuje się odległość euklidesową

(2.9)


natomiast jeśli współczynnik p przyjmie wartość 1, otrzymuje się odległość miejską

(2.10)


Formuły ( 2.9 ) oraz ( 2.10 ) są najczęściej wykorzystywanymi miernikami odległości. Innymi formułami, często spotykanymi w literaturze przedmiotu są:
Odległość Jeffreysa – Matusita

(2.11)


Odległość Braya – Curtisa

(2.12)


Odległość Canberra

(2.13)


Odległość Clarka

(2.14)


Odległość kątowa

(2.15)


Odległość Machalanobisa

(2.16)

przy czym to wektory znormalizowanych wartości zmiennych dla i – tego oraz k – tego obiektu. jest ogólną macierzą wariancji i kowariancji zmiennych.

Istnieją specjalne miary odległości uwzględniające charakter badanych cech X1, X2, ..., Xp. Przykładem takich miar są miary stosowane w przypadku, gdy każda z cech X1, X2, ..., Xp jest cechą zero – jedynkową. Wówczas elementy

xik ( i = 1, ..., n; k = 1, ..., p ) macierzy danych X mogą być równe 0 lub 1. Dla konstrukcji miary odległości dij pomiędzy i – tym a j – tym obiektem należy rozważyć wiersz i oraz wiersz j macierzy X, czyli wektory wierszowe

xi = [ xi1, xi2, ..., xip ] oraz xj = [ xj1, xj2, ..., xjp ].

Niech a oznacza liczbę tych składowych wektorów xi i xj, które jednocześnie są równe 1. Niech b oznacza liczbę składowych wektora xi równych 1, podczas gdy odpowiednie składowe wektora xj są równe 0; niech c oznacza liczbę składowych wektora xi równych 0, podczas gdy odpowiednie składowe wektora xj są równe 1. Niech d oznacza liczbę tych składowych obu wektorów, które jednocześnie są równe 0.
Przykłady miar odległości dla cech zero – jedynkowych:
Odległość Ochiai

(2.17) dij = 1 – a / [ ( a + b ) ( a + c ) ]0,5


Odległość Dice’a

(2.18) dij = ( b + c ) / ( 2a + b +c )


Odległość Jaccarda

(2.19) dij = ( b + c ) / ( a + b + c )



2.2 Metody porządkowania i klasyfikacji obiektów
2.2.1 Podstawowe pojęcia
Punktem wyjścia w przedstawieniu metod porządkowania i klasyfikacji są następujące zbiory:
zbiór obiektów P będący przedmiotem klasyfikacji, przy czym:

(2.20) P = { P1, P2, ..., Pn }


zbiór cech Φ charakteryzujący przestrzeń klasyfikacji, przy czym:

(2.21) Φ = { X1, X2, ..., Xp }


zbiór jednostek czasu T:

(2.22) T = { 1, 2, ..., t }


Obserwacje poczynione na konkretnych obiektach można zapisać w postaci macierzy obserwacji:

(2.23) X = [ xij ] i = 1, 2, ..., n j = 1, 2, ..., p

gdzie xij oznacza wartość cechy Xj obiektu Pi.
Jeśli obserwacje będą dokonywane w określonych momentach czasu, to macierz obserwacji X będzie miała postać:
(2.24) X = [ xijl ] i = 1, 2, ..., n; j = 1, 2, ..., p; l = 1, 2, ..., t
Stosowanie reprezentacji przestrzennej oznacza, że w przestrzeni p – wymiarowej Rp, mamy zbiór n punktów { x1, x2, ..., xn }. W ten sposób każdy obiekt Pi jest numerycznie opisany za pomocą wektora xi [ 1 × P ] o postaci

xi = [ xi1, xi2, ..., xip ].

Obiekty można porównywać, jeśli zdefiniujemy odpowiednią miarę podobieństwa lub niepodobieństwa między obiektami. Za taką miarę można na przykład przyjąć odległość między obiektami, ustalając, że dwa obiekty Pk, Pr są tym bardziej niepodobne, im większa jest odległość między punktami xk, xr.

Zadaniem dualnym do grupowania obiektów jest grupowanie cech. W takim przypadku przedmiotem grupowania będą cechy numerycznie opisane za pomocą wektora [ n × 1 ] o postaci:


(2.25) Xj = [ x1j, x2j, ..., xnj ] j = 1, 2, ..., p
Oznacza to, że cecha może być geometrycznie interpretowana jako punkt w przestrzeni n – wymiarowej. W takim zadaniu elementy macierzy odległości D wyznacza się zwykle na podstawie współczynników korelacji danych dwóch cech, a zatem elementy macierzy D można wyznaczyć następująco:
(2.26) i, j = 1, 2, ..., p
przy czym:
(2.27) rij = r ( Xi, Xj ) i, j = 1, 2, ..., p

2.2.2 Pojęcie skupienia
Przez skupienie rozumie się zbiór punktów ( obiektów ) podobnych do siebie, przy czym punkty należące do dwóch różnych skupień powinny różnić się między sobą w sposób istotny.

Niech Gi ( i = 1, 2, ..., k ) oznacza zbiór skupień definiowanych jako niepuste, rozłączne i wyczerpujące zbiór P, czyli:


Gi i = 1, 2, ..., k

i ≠ j; i, j = 1, 2, ..., k

Na rysunku 3.1 przedstawiony został przykład podziału zbioru obiektów na skupienia w dwuwymiarowej przestrzeni cech


Rys 2.1

Podział zbioru obiektów na skupienia w dwuwymiarowej przestrzeni cech



  1   2   3


©snauka.pl 2016
wyślij wiadomość