Taksonomiczne metody
porzÄ…dkowania i grupowania
obiektów
We wszystkich metodach zakładamy, \
e
przedmiotem porzÄ…dkowania lub
grupowania sÄ… obiekty ujmowane w
wielowymiarowej przestrzeni zmiennych.
W większości procedur grupowania
istniejÄ… tak\
e metody dualne, w których
przedmiotem klasyfikacji sÄ… zmienne
traktowane jako zbiór punktów w
wielowymiarowej przestrzeni obiektów.
Procedury taksonomiczne mo\
na
podzielić m.in. na:
" - wzorcowe i bezwzorcowe,
" - obszarowe, oparte na podobieństwie i
czynnikowe,
" - hierarchiczne i niehierarchiczne,
" - aglomeracyjne i podziałowe,
" - liniowe i nieliniowe.
W metodach wzorcowych dokonuje siÄ™
podziału na grupy ze względu na
uprzednio przyjęte wzorce tych grup.
W metodach bezwzorcowych szuka siÄ™
podziału zbioru obiektów na podzbiory
wewnętrznie homogeniczne (jednorodne)
oraz heterogeniczne (niejednorodne)
między sobą, bez ustalonych z góry
wzorców poszczególnych grup.
W metodach obszarowych grupowanie
obiektów odbywa się poprzez podział
wielowymiarowej przestrzeni klasyfikacji
na rozłączne podprzestrzenie, zgodnie z
ustalonymi zadaniami, i zaliczanie
obiektów znajdujących się w
wyodrębnionych podprzestrzeniach do
odrębnych grup.
W metodach opartych na podobieństwie
poszczególnym parom obiektów
przyporzÄ…dkowuje siÄ™ odpowiednio
zdefiniowaną miarę podobieństwa (lub
odległości) i łączy się w grupy obiekty
najbardziej do siebie podobne.
Metody czynnikowe sprowadzajÄ… siÄ™ do
zastąpienie wyjściowego zbioru obiektów
zbiorem ich grup, poprzez przekształcenie
ortogonalne macierzy danych
wyjściowych.
Metody hierarchiczne prowadzą do wyodrębnienia
pełnej hierarchii skupień z monotonicznie
wzrastającym współczynnikiem podobieństwa.
Uzyskiwane tu skupienie wy\
szych rzędów
zawierają rozłączne skupienia poziomów
ni\
szych. Wyró\
nia siÄ™ tu metody aglomeracyjne
i podziałowe.
Metody niehierarchiczne prowadzÄ… do
nieuszeregowanych i zachodzÄ…cych na siebie
konfiguracji skupień, tzn. takich, w których
skupienia ni\
szego rzędu nie muszą być
elementami skupień wy\
szego rzędu.
W metodach aglomeracyjnych (sekwencyjnych,
indukcyjnych) wychodzi się z zało\
enia, \
e
ka\
dy obiekt stanowi początkowo odrębną
grupę, a następnie zmniejsza się sukcesywnie
liczbÄ™ grup przez ich Å‚Ä…czenie w grupy wy\
szego
rzędu.
W metodach podziałowych (globalnych,
dedukcyjnych) analizowany zbiór obiektów
traktuje siÄ™ poczÄ…tkowo jako jednÄ… grupÄ™, a
proces klasyfikacji polega na stopniowym
zwiększaniu liczby grup.
Metody liniowe pozwalajÄ… na
uporządkowanie zbioru obiektów
wielowymiarowych według pewnego
syntetycznego kryterium będącego funkcją
zmiennych wyjściowych. Problem
grupowania schodzi tutaj na plan dalszy,
jakkolwiek mo\
na go tak\
e rozwiązać
posługując się informacjami zawartymi w
realizacji zmiennej syntetycznej.
Metoda Czekanowskiego.
Najstarsza numeryczna procedura taksonomiczna. Umo\
liwia ona
zarówno liniowe uporządkowanie obiektów jak i ich grupowanie.
Punktem wyjścia jest symetryczna, kwadratowa macierz odległości
między klasyfikowanymi obiektami
D = [dij ]
gdzie n jest liczbą obiektów.
Schemat postępowania polega na przestawianiu wierszy i
odpowiadających im kolumn w macierzy D w taki sposób, aby
wzdłu\
jej głównej przekątnej znajdowały się elementy mo\
liwie jak
najmniejsze, a wraz z oddalaniem się od głównej przekątnej wartości
pojawiających się mierników odległości były coraz większe.
Jako obiektywną funkcję kryterium stosuje się następujący
miernik:
n n
F = dij uij
""
i=1 j>i
gdzie dij to elementy macierzy D, natomiast uij to ich wagi
zdefiniowane za pomocą jednego ze wzorów:
|i - j|
uij = ,
n - 1
1
uij = [2n|i - j - 1|+i + j - (i - j)2 ],
n(n - 1)
1
uij = [2n|i - j|+2 - i - j - (i - j)2 ]
n(n - 1)
Dalej numerycznie przestawia siÄ™ kolumny i wiersze tak, aby
wartość F była maksymalna.
Zwrócić uwagę na trudność obliczeniową gdy\
np. dla n obiektów
liczba mo\
liwych uporządkowań wynosi n!/2. Stosuje się tutaj
technikÄ™ uproszczonÄ… polegajÄ…cÄ… na tym, \
e z jakiegoÅ› porzÄ…dku
początkowego startuje się do transpozycji dwóch pierwszych
elementów sprawdza się czy wartość F rośnie; jeśli nie to wraca się
do poczÄ…tku sprawdza to samo dla transpozycji 1 i 3. W przeciwnym
przypadku otrzymaną transpozycję traktuje się jako punkt wyjścia i
itd.
Metody porzÄ…dkowania
liniowego.
" Zbiór obiektów &! uporządkowuje się liniowo, tzn.
tak, aby:
" - ka\
dy obiekt miał co najmniej jednego sąsiada
oraz co najwy\
ej dwóch sąsiadów;
" - z tego, \
e i-ty obiekt jest sÄ…siadem obiektu j-
tego, wynika, \
e obiekt j-ty jest sÄ…siadem obiektu
i-tego;
" - istniejÄ… co najwy\
ej dwa obiekty majÄ…ce tylko
jednego sÄ…siada.
Metoda Szczotki.
Szuka się takiego porządku obiektów, dla
którego wartość funkcji kryterium osiąga
maksimum. Symbol d(ai, ai+j) oznacza
odległość Euklidesa pomiędzy obiektami i
oraz j.
W praktyce ze względu na du\
Ä… liczbÄ™
permutacji postępuje się jak w metodzie
Czekanowskiego.
Metody gradientowe.
Szuka się takiego wektora współrzędnych, który minimalizuje jedną
z następujących funkcji kryteriów:
"(d - ´ij )2
ij
i< j
E1 =
"´
ij
i< j
2
ëÅ‚ - ´ij öÅ‚
dij
E2 =
"ìÅ‚ ´ij ÷Å‚
ìÅ‚ ÷Å‚
i< j íÅ‚ Å‚Å‚
(dij - ´ij )2
1
E3 =
i< j
"´ " ´ij
ij
i< j
gdzie ´ij to odlegÅ‚ość miÄ™dzy i-tym oraz j-tym obiektem w
wyjściowej m-wymiarowej przestrzeni cech, natomiast dij to
odległość między tymi obiektami w jednowymiarowej przestrzeni
określonej przez szukaną zmienną syntetyczną.
Miara odległości jest obojętna pod warunkiem, \
e taka sama dla
odlegÅ‚oÅ›ci dij i ´ij .
Punktem wyjścia jest dowolny wektor współrzędnych (np.
ustalony losowo), który jest przekształcany w trakcie kolejnych
iteracji polegajÄ…cych na szukaniu ekstremum funkcji wielu
zmiennych, tak aby został zapewniony jak największy spadek
wartości funkcji kryterium.
Metody podziału zbiorów liniowo uporządkowanych.
Punktem wyjścia jest liniowe uporządkowanie badanych
obiektów.
M e t o d a S p ä t h a -S z c z o t k i
s z u k a s iÄ™ ta k ie g o p o d z ia Å‚u z b io ru n a k s k u p ie Å„ , a b y f u n k c je k r y te r ia :
n
k
i
1
Q = d ( s , t )
" "
A
n
i = 1 s , t = 1
i
n
k
i
1
Q = d ( s , t )
" "
B
n ( n - 1)
i = 1 s , t = 1
i i
n
k
i
Q = d ( x , c )
" "
C ij i
i = 1 j = 1
o s iÄ… g a Å‚y w a r to Å› c i m in im a ln e .
d ( s ,t) to o d le g ło ś ć m ię d z y o b ie k ta m i s o r a z t n a le \
Ä… c y m i d o i- te j
g r u p y ,
d ( x , c ) - o d lrg ło ś ć m ię d z y ś ro d k ie m c ię \
k o ś c i i- te j g ru p y o b ie k tó w
ij i
a j-ty m o b ie k te m n a le \
Ä… c y m d o te j g ru p y ,
n - lic z e b n o ś ć i- te j g r u p y o b ie k tó w .
i
Metody dendrytowe.
Taksonomia wrocławska.
" Buduje się dendryt w ten sposób, \
e wśród wszystkich
odległości D szuka się najmniejszych wskazujących na
parę elementów najbli\
szych. Otrzymane połączenia
przedstawia siÄ™ w postaci grafu niezorientowanego, w
którym długości krawędzi są proporcjonalne do
odległości między obiektami przyporządkowanymi
poszczególnym wierzchołkom. Sprawdza się czy
otrzymany graf jest spójny. Jeśli nie, to jego
poszczególne składowe spójności łączy się ze sobą w
miejscu wyznaczonym przez minimalną odległość
między obiektami - wierzchołkami - nale\
Ä…cymi do
łączonych składowych.
" Aby otrzymać podział zbioru klasyfikowanego na k klas
nale\
y w dendrycie odrzucić k-1 najdłu\
szych krawędzi.
y
ródło: Mercik&Mazurkiewicz: Power Index with Precoalitions Based on Ideological Distance, Badania Operacyjne i
Decyzje, 1995
Metoda Prima.
" Podobna do metody taksonomi wrocławskiej z
tym, \
e w procesie konstrukcji dendrytu cały
zbiór klasyfikowany dzieli się na dwa podzbiory,
z których pierwszy zawiera obiekty nale\
Ä…ce w
danym momencie do tworzonego dendrytu,
natomiast drugi pozostałe obiekty, jeszcze nie
przyłaczone do dendrytu.
" W kroku 1 zbiór pierwszy jest pusty. Dalej,
bierze siÄ™ dowolny jeden element ze zbioru
drugiego, następnie szuka najbli\
szego do niego
elementu ze zbioru drugiego, itd. A\
do
momentu a\
zbiór drugi będzie pusty.
Metody obszarowe.
Przestrzeń dyskryminacji dzieli się na rozłączne obszary zgodnie z
ustalonymi zasadami oraz traktuje obiekty znajdujÄ…ce siÄ™ w takich
obszarach jako odrębne klasy.
Najczęściej takie podobszary to są hiperkule lub hiperkostki.
Promień takiej hiperkuli lub liczbę hiperkostek ustala się arbitralnie.
Często wg. następującego sposobu:
d0 = d + csD
lub
d0 = max min{dij }
i j
(i,j = 1,& ,n) gdzie d , sD średnia arytmetyczna i odchylenie
standardowe z minimalnych odległości poszczególnych obiektów od
wszystkich pozostałych; c - dowolna liczba rzeczywista ustalona tak,
aby otrzymać nietrywialne podziały (zaczyna się od -2, -1, -0,5, 0,
0,5, 1, 1,5 itd.).
Stosuje siÄ™ tutaj metody:
" - wrocławska,
" - taksonomi stochastycznej,
" - procedurÄ™ Sebastyena,
" - metodÄ™ katowickÄ…,
" - metodÄ™ Thorndike a,
" - metodÄ™ Hartigana
" - itd.
Drzewa klasyfikacyjne
X1<1
nie
tak
x2
R1
R2
R1
R2
1
x1
X1<1
nie
tak
x2
R1
X2<2
tak nie
R3
R4
R4
R1
2
R4
1
x1
X1<1
nie
tak
x2
R1
X2<2
tak nie
R3
R4
X1<2,5
R1 tak
nie
2
R5
R6
R5 R6
1 2,5
x1
Przykład: zbiór kwiatów irisa (Fisher, 1936)
Virginica
Versicor
Kryterium: jak
najmniejsza
wariancja w
obrębie danej
klasy
Setosa
y
ródło: Metody statystycznej analizy wielowymiarowej w badaniach marketingowych,
Wydawnictwo AE Wrocław, 2004.
Segmentacja rynku
Wstępne zało\
enie:
liczebność klasy
przekraczajÄ…ca 10%
badanej zbiorowości
Algorytm !
y
ródło: Metody statystycznej analizy wielowymiarowej w badaniach marketingowych,
Wydawnictwo AE Wrocław, 2004.
Przykład. Ceny giełdowe energii w skali roku (CRO - cena rozliczeniowa odchylenia wolumenu, CROs
-cena rozliczeniowa odchylenia sprzeda\
y, CROz - ceny rozliczeniowa odchylenia zakupu)
y
ródło: Faber, Gładysz, Mercik: DRZEWA REGRESYJNE W ANALIZIE RYZYKA OBCI
śENIA
ELEKTROENERGETYCZNEGO, BOS 2006, Szczecin.
Zasady zakupu/sprzeda\
y energii na giełdzie mo\
na ogólnie scharakteryzować następująco
(Wójcik i Wójcicka, 2004):
" Jeśli zadeklarowane przez uczestnika giełdy zapotrzebowanie na energię ró\
ni siÄ™ co najwy\
ej
o 1% od rzeczywistego, to cenÄ… zakupu/ sprzeda\
y energii jest cena rozliczeniowa odchylenia
CRO.
" Jeśli zadeklarowane przez uczestnika giełdy zapotrzebowanie na energię ró\
ni się o więcej ni\

o 1% od rzeczywistego, to cena sprzeda\
y energii na giełdzie zale\
y zarówno od ceny CRO
oraz jak i ceny rozliczeniowej odchylenia zakupu CROz.
Jeśli zadeklarowane przez uczestnika giełdy zapotrzebowanie na energię ró\
ni siÄ™ o mniej ni\
o -1%
od rzeczywistego, to cena sprzeda\
y energii na giełdzie zale\
y zarówno od ceny CRO oraz jak i ceny
rozliczeniowej odchylenia sprzeda\
y CROs.
Badania oparto na 555 obserwacjach poziomu obciÄ…\
enia systemu elektroenergetycznego o godzinie
12 na przestrzeni czterech lat oraz dane pogodowe i ceny rynku energii. Dane giełdowe wykorzystane
zostaną w dalszej części pracy do wielowymiarowej analizy ryzyka. Do budowy binarnego drzewa
regresyjnego zastosowano pakiet SPSS. Za kryterium podziału przyjęto redukcję wariancji oraz takie
parametry jak minimalna liczba obserwacji w liściu = 10 oraz minimalna liczba obserwacji przed
podziałem = 50. Jako czynniki klasyfikacyjne przyjęto:
" dzień roku,
" dzień miesiąca,
" dzień tygodnia (poniedziałek=1,& , niedziela=7),
" miesiÄ…c,
" temperatura.
Homogeniczność wariancji wolumenu obcią\
enia systemu
elektroenergetycznego.
Klasa 13 26 25 15 18 16 29 14 5 37 7 28 33 35 22 23 34 36 39 38
13 * * *
26 * * * *
25 * * * * *
15 * * * *
18 * * * * * *
16 * * *
29 * * * * * * * *
14 * * * * * * * *
5 * * * * * * *
37 * * * * * * * *
7 * * * * * * * * * * *
28 * * * * * * * * * * * *
33 * * * * * * * * * * * * * *
35 * * * * * * * * * * *
22 * * * * * * * * * *
23 * * * * * * * * * *
34 * * * * * * * * * *
36 * * * * * * * * *
39 * * * * * * * * *
38 * * * * * * * *
Diagram Haasego dla ryzyka giełdowego energii elektrycznej
Diagram Haasego jest jednÄ… z wielu metod stosowanych w analizach wielokryterialnych (np.
Ignasiak, 2001). Diagramem Hassego nazywamy graf zorientowany G(X , R), gdzie X jest zbiorem
porównywanych elementów, R jest relacją częściowego porządku określoną na elementach zbioru X:
xi Rx Ô! xi " jest gorsze od" x (1)
j j
W naszych badaniach elementami zbioru X sÄ… klasy wyznaczone w drzewie regresyjnym
X={K5, K7,& ,K39}. Termin  gorsze rozumiany jest w sensie  większego poziomu ryzyka . A więc
biorąc pod uwagę kryteria fi (x), i=1,2,3,4, dla których wartościami najgorszymi w sensie poziomu
ryzyka są ich wartości maksymalne powiemy, \
e klasa Ki " jest gorsza od"K wtedy i tylko
j
wtedy, gdy istnieje takie r ( r "{1,2,3,4}), \
e:
( ) ( )
fr (Ki ) > fr K i fs (Ki ) e" fs K dla s `" r . (2)
j j
Graf Haasego dla wielokryterialnego ryzyka giełdowego
w
13 26 25 16 37 35 22 34
z
r
o
s
t
r
y
38
29 15 18 28 36 39
z
y
k
a
14
7
33
5 23
Najgorszymi w sensie wielowymiarowego ryzyka giełdowego są klasy K13, K16, K18, K22, K25,
K26, K34, K35, K37, K39. Są to klasy równowa\
ne (najbardziej ryzykowne) w sensie Pareto. Do klas
tych nale\
Ä… takie dni roku, jak:
1, 2 stycznia i 1, 2 lutego,
wszystkie dni tygodnia z wyjÄ…tkiem niedziel
" w pierwszej połowie miesięcy zimowych (grudzień  luty) ) z przyrostem temperatury
średniej w ciągu doby większym ni\
3,60 C przy temperaturze maksymalnej poni\
ej
90C,
" w marcu, listopadzie z temperaturÄ… maksymalnÄ… powy\
ej 80 C
" we wrześniu, paz
dzierniku z temperaturą średnią poni\
ej 100 C,
" w kwietniu z temperaturą średnią powy\
ej 100 C,
" w pierwszej dekadzie maja oraz
okres letni z wyjątkiem  śród, czwartków i sobót ze zmianą temperatury minimalnej w ciągu
doby o mniej ni\
30 C i równocześnie ze zmianą temperatury w ciągu doby mniejszą od 90 C.