PRZYKŁAD:
zbiór Ω zawiera 8 elementów (np. przedsiębiorstwo) o postaci:
obiekty są opisane 2 cechami (np. zatrudnienie w zakł. K w tys. i zatrudnienie w zakł. M w tys.):
ωi
|
xi1 |
xi2 |
zi1 |
zi2 |
1 2 3 4 5 6 7 8 |
2 2 4 5 8 7 8 8 |
3 2 3 4 2 7 7 8 |
-1,429 -1,429 -0,612 -0,204 1,020 0,612 1,020 1,020 |
-0,655 -1,092 -0,655 -0,109 -1,092 1,092 1,092 1,528 |
1. Dokonujemy standaryzacji cech:
Obliczamy macierz odległości Euklidesa:
GEOMETRYCZNA PREZENTACJA ZBIORU Ω
METODY PORZĄDKOWANIA LINIOWEGO (m. Czekanowskiego, m. rang, m. standaryzowanych sum wartości, m. Szczotki, m. gradientowe).
Porządkowanie liniowe polega na rzutowaniu przestrzeni wielowymiarowej na prostą.
Liniowe uporządkowanie obiektów zbioru Ω:
każdy obiekt ma co najmniej jednego sąsida oraz co najwyżej dwóch sąsiadów;
z tego, że obiekt i-ty jest sąsiadem obiektu k-tego, wynika, że obiekt k-ty jest sąsiadem obiketu i-tego;
istnieją co najwyżej dwa obiekty mające tylko jednego sąsiada.
METODY PORZĄDKOWANIA NIELINIOWEGO
uporządkowanie dendrytowe (taksonomia wrocławska, dendryt Prima)
uporządkowanie drzewkowe (m. najbliższego sąsiedztwa, m. najdalszego sąsiedztwa, m. środka ciężkości, m. mediany)
Porządkowanie nieliniowe polega na rzutowaniu punktów przestrzeni wielowymiarowej na płaszczyznę. Charakteryzuje się brakiem wyraźnej hierarchii.
Uporządkowanie dendrytowe
Dendryt - linia łamana rozgłęziająca się, lecz nie zawierająca łamanych zamkniętych, łącząca wszystkie punkty zbioru .
Graficzna prezentacja rozwiązania
obiekty przedstawiane są w postaci kółek zwanych wierzchołkami
obiekty łączymy odcinkami zwanymi łukami (wiązadłami)
METODA CZEKANOWSKIEGO
1. Mierniki odległości występujące w macierzy D dzielimy na kilka klas, a następnie przyporządkowujemy poszczególnym klasom odpowiednie symbole graficzne, które odzwierciedlają różne poziomy wielkości mierników:
+ |
|
X |
|
|
|
|
|
do 2,5 2,5-4,5 4,5-7,5 pow. 7,5
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
+ |
+ |
+ |
X |
|
|
|
|
2 |
+ |
+ |
+ |
X |
|
|
|
|
3 |
+ |
+ |
+ |
+ |
X |
|
|
|
4 |
X |
X |
+ |
+ |
X |
X |
X |
|
5 |
|
|
X |
X |
+ |
|
|
|
6 |
|
|
|
X |
|
+ |
+ |
+ |
7 |
|
|
|
X |
|
+ |
+ |
+ |
8 |
|
|
|
|
|
+ |
+ |
+ |
2. Porządkujemy diagram:
przestawiamy wiersze i kolumny, tak aby wzdłuż przekątnej znajdowały się elementy możliwie jak najmniejsze, a wraz z oddalaniem się od przekątnej wartości mierników odległości były coraz większe:
|
1 |
5 |
4 |
2 |
3 |
6 |
7 |
8 |
1 |
+ |
+ |
+ |
X |
|
|
|
|
5 |
|
|
X |
X |
+ |
|
|
|
4 |
X |
X |
+ |
+ |
X |
X |
X |
|
2 |
+ |
+ |
+ |
X |
|
|
|
|
3 |
+ |
+ |
+ |
+ |
X |
|
|
|
6 |
|
|
|
X |
|
+ |
+ |
+ |
7 |
|
|
|
X |
|
+ |
+ |
+ |
8 |
|
|
|
|
|
+ |
+ |
+ |
TAKSONOMIA WROCŁAWSKA
1. Łączymy każdą badaną jednostkę z jednostkami najbliższymi (wyszukujemy najmniejszą liczbę w każdym wierszu macierzy D):
1,00 1,00 1,41 1,41
1 |
|
2 |
|
2 |
|
1 |
|
3 |
|
4 |
|
4 |
|
3 |
3,61 1,00 1,00 1,00
5 |
|
4 |
|
6 |
|
7 |
|
7 |
|
6 |
|
8 |
|
7 |
1,00
7 |
|
8 |
2. Eliminujemy jedno z każdych podwójnych połączeń.
3. Sprawdzamy czy graf jest spójny (czy każde dwa wierzchołki są połączone nieprzerwanym ciągiem wiązadeł):
a) TAK - koniec procedury,
b) NIE - kontynuujemy procedurę (pkt 4).
4. Łączymy ze sobą poszczególne składowe w miejscu wyznaczym przez minimalną odległość między obiektami (wierzchołkami) należącymi do łączonych składowych:
1,00 1,00 1,00 1,41 3,61
1 |
|
2 |
|
6 |
|
7 |
|
8 |
|
3 |
|
4 |
|
6 |
5. Sprawdzamy, czy uzyskany graf jest spójny:
a) TAK - koniec procedury,
b) NIE - kontynuujemy procedurę (pkt 6).
6. Łączymy poszczególne tzw. skupienia ze sobą w miejscu wyznaczonym przez minimalną odległość między obiektami (wierzchołkami) należącymi do poszczególnych skupień:
5 |
|
|||||||||||||||||||
|
3,61
3,41 |
|
1,00 |
1,00 |
|
|
|
|
||||||||||||
4 |
|
6 |
|
7 |
|
8 |
||||||||||||||
|
1,41 |
|
|
|
|
|
||||||||||||||
3 |
|
|
|
|
|
|
||||||||||||||
|
2,00
1,00 |
|
|
|
|
|
||||||||||||||
1 |
|
2 |
|
|
|
|
7. Sprawdzamy, czy uzyskany graf jest spójny.
itd.
DENDRYT PRIMA
a) tworzymy zbiór A0, w którym znajdują się elementy jeszcze nie przyłączone do dendrytu
wybieramy losowo ze zbioru wyjściowego
jeden punkt, od którego rozpoczynamy budowę dendrytu
b) tworzymy zbiór B zawierający elementy tworzące dendryt
c) tworzymy wektor d1, w którym umieszczamy odległości wybranego punktu (elementu toworzącego dendryt) od pozostałych punktów (elementów nie przyłączonych do dendrytu)
d) wybieramy punkt, który jest najbliżej położony punktu umieszczonego w zbiorze B1 (najmniejszą odległość) i przyłączamy go do zbioru B1
e) tworzymy wektor d2, w którym umieszczamy najmniejsze z odległości punktów ze zbioru B2 od punktów ze zbioru A2
f) wybieramy ze zbioru A2 punkt, który jest najbliżej położony w stosunku do punktów w zbiorze B2 (najmniejszą odległość) i umieszczamy go w zbiorze B2
g) procedurę kontynuujemy, aż wszystkie punkty ze zbioru A zostaną przemieszczone do zbioru B
8 |
|
|||||||||||||||
|
1,00 |
|||||||||||||||
7 |
|
|||||||||||||||
|
1,00 |
|||||||||||||||
|
|
|||||||||||||||
|
3,61
|
|
|
|
|
|
|
|
||||||||
|
|
3 |
|
1 |
|
2 |
||||||||||
|
1,41
3,61 |
2,00 |
1, |
00 |
|
|
||||||||||
|
|
|
|
|
|
|
||||||||||
5 |
|
|
|
|
|
|