Rk III

Rozdział III

METODY GRUPOWANIA OBIEKTÓW

3.1. Założenia grupowania obiektów

Zasadniczym celem grupowania obiektów jest utworzenie jak najbardziej jednorodnych grup obiektów (skupień) ze względu na podobieństwo w zakresie wewnętrznej struktury charakteryzujących je zmiennych. Sprowadza się to do takiego grupowania obiektów, aby spełniało ono dwa podstawowe warunki:

homogeniczności: obiekty należące do tej samej grupy powinny być do siebie jak najbardziej podobne,
heterogeniczności: obiekty należące do różnych grup powinny być do siebie jak najmniej podobne.

Od strony formalnej zbiór obiektów O={O₁,O₂,...,O_n} należy podzielić na podzbiory (grupy obiektów)
spełniające następujące warunki:

zupełności:

, (3.1)

rozłączności:

, r,r'=1,2,...,z, r≠r', (3.2)

niepustości:

∅, r=1,2,...,z. (3.3)

Metody grupowania obiektów mogą być klasyfikowane według różnych kryteriów. Najczęściej pod uwagę brane są kryteria zaproponowane przez P. H. A. Sneatha i R. R. Sokala (1973) i omówione w pracach M. Sobczyka (1995) oraz A. Młodaka (2006).

W niniejszym opracowaniu metody grupowania obiektów zostały sklasyfikowane w grupy metod, w sposób najczęściej występujący w literaturze przedmiotu, w których poszczególne kryteria klasyfikacji nie są rozłączne.

3.2. Metody grupowania obiektów uporządkowanych liniowo

Punktem wyjścia omawianych metod grupowania obiektów jest ich liniowe uporządkowanie. Uporządkowanie to można uzyskać za pomocą dowolnej z metod porządkowania liniowego przedstawionych w rozdz. II. W opracowaniu koncentrujemy się na wybranych metodach grupowania uporządkowanych liniowo obiektów.

3.2.1. Metody diagramowe

Grupowanie obiektów uporządkowanych za pomocą metody Czekanowskiego za pomocą tzw. miernika poprawności grupowania zaproponowała B. Podolec (Podolec i Zając, 1978). Miernik ten konstruowany jest przy założeniu, że w optymalnym grupowaniu poszczególne grupy powinny składać się z obiektów, pomiędzy którymi występują wyłącznie tzw. bliskie powiązania, a poza grupami tylko tzw. powiązania dalekie. Przez powiązania bliskie rozumiane są powiązania pomiędzy obiektami, którym odpowiadają w diagramie symbole graficzne reprezentujące najniższe klasy odległości obiektów (np. dwie najniższe klasy). Pozostałe powiązania między obiektami należy traktować jako dalekie. Wskaźnik poprawności podziału przyjmuje wtedy następującą postać:

, (3.4)

gdzie:

n^w, n^z - liczba powiązań odpowiednio wewnątrz i na zewnątrz wyodrębnionych grup obiektów.

n^pb, n^pd - liczba powiązań odpowiednio bliskich, wewnątrz grup obiektów i dalekich, na zewnątrz grup obiektów.

Do podziału obiektów, uporządkowanych metodą Czekanowskiego na grupy, można wykorzystać także metodę Spätha-Szczotki, przedstawioną w dalszej części rozdziału. Należy jednak w tej sytuacji wykorzystać wyjściową macierz odległości między obiektami, sprzed jej transformacji w diagram.

Przykład 3.1

Punktem wyjścia grupowania województw, w grupy województw o podobnym poziomie życia w 2005 r., za pomocą metod diagramowych było ich uporządkowanie uzyskane za pomocą metody Czekanowskiego (Przykład 2.1).

Za powiązania bliskie uznano powiązania odpowiadające odległościom między województwami mniejszymi od 2,4 (puste kwadraty). Dla każdej możliwego do uzyskania grupowania województw obliczono wskaźnik poprawności podziału (3.4). W kolejnych tablicach przedstawiono cztery najlepsze grupowania województw (począwszy od optymalnego), ze względu na przyjętą funkcję kryterium dobroci grupowania, przedstawiając je na uporządkowanym diagramie Czekanowskiego, podając jednocześnie wartości funkcji dobroci grupowania. W diagramach zaznaczono kwadraty odpowiadające wyodrębnionym grupom województw.

Tab. 3.1. Optymalne grupy województw.

O₈

O₁₅

O₄

O₁₀

O₁₄

O₁

O₂

O₁₆

O₆

O₁₁

O₇

O₁₃

O₅

O₃

O₉

O₁₂

O₈

•

O₁₅

•

O₄

•

O₁₀

•

O₁₄

•

O₁

•

O₂

•

O₁₆

•

O₆

•

O₁₁

•

O₇

•

O₁₃

•

O₅

•

O₃

•

O₉

•

O₁₂

•

Q₁=0,931034

Tab. 3.2. Grupy województw.

O₈

O₁₅

O₄

O₁₀

O₁₄

O₁

O₂

O₁₆

O₆

O₁₁

O₇

O₁₃

O₅

O₃

O₉

O₁₂

O₈

•

O₁₅

•

O₄

•

O₁₀

•

O₁₄

•

O₁

•

O₂

•

O₁₆

•

O₆

•

O₁₁

•

O₇

•

O₁₃

•

O₅

•

O₃

•

O₉

•

O₁₂

•

Q₁=0,915254

Tab. 3.3. Grupy województw.

O₈

O₁₅

O₄

O₁₀

O₁₄

O₁

O₂

O₁₆

O₆

O₁₁

O₇

O₁₃

O₅

O₃

O₉

O₁₂

O₈

•

O₁₅

•

O₄

•

O₁₀

•

O₁₄

•

O₁

•

O₂

•

O₁₆

•

O₆

•

O₁₁

•

O₇

•

O₁₃

•

O₅

•

O₃

•

O₉

•

O₁₂

•

Q₁=0,915254

Tab. 3.4. Grupy województw.

O₈

O₁₅

O₄

O₁₀

O₁₄

O₁

O₂

O₁₆

O₆

O₁₁

O₇

O₁₃

O₅

O₃

O₉

O₁₂

O₈

•

O₁₅

•

O₄

•

O₁₀

•

O₁₄

•

O₁

•

O₂

•

O₁₆

•

O₆

•

O₁₁

•

O₇

•

O₁₃

•

O₅

•

O₃

•

O₉

•

O₁₂

•

Q₁=0,907563

3.2.2. Metoda Spätha-Szczotki

Grupowania uporządkowanych liniowo obiektów dokonujemy w oparciu o macierz odległości między badanymi obiektami. Na podstawie analizy jej elementów szukamy takiego grupowania obiektów na z grup aby funkcja kryterium dobroci grupowania osiągnęła minimum (Grabiński i in., 1989; Szczotka, 1971; Späth, 1973 i 1982).

Warunek ten, gdy dążymy do otrzymania grup obiektów o zbliżonych liczebnościach, można zapisać jako:

0x01 graphic
, (3.5)

gdzie:

d_ii' - odległość między i-tym i i'-tym obiektem należącymi do r-tej grupy obiektów.

Kolejna funkcja kryterium dobroci grupowania minimalizuje sumę średnich odległości w grupach. W sposób formalny warunek ten możemy przedstawić następująco:

0x01 graphic
. (3.6)

Ostatnia z funkcji kryterium dobroci grupowania minimalizuje zróżnicowanie obiektów wewnątrz grup, ze względu na charakteryzujące je zmienne, co możemy sformułować następująco:

0x01 graphic
, (3.7)

gdzie:

- odległość między środkiem ciężkości r-tej grupy i i-tym obiektem należącym do tej grupy.

Szukanie optymalnego grupowania może być realizowane poprzez poszukiwanie absolutnych minimów funkcji dobroci grupowania (3.5), (3.6) lub (3.7). Możemy także szukać rozwiązania qusi-optymalnego.

W punkcie wyjścia tej procedury wszystkie obiekty stanowią oddzielne grupy. W kolejnych iteracjach łączymy dwie sąsiadujące ze sobą grupy obiektów, dla których dana funkcja kryterium dobroci grupowania przyjmuje najmniejszą wartość. Procedurę kończymy w momencie gdy wszystkie obiekty tworzą jedną grupę.

Wyznaczenie ostatecznej konfiguracji grup obiektów wymaga wskazania iteracji, w której następuje przerwanie tworzenia kolejnych, coraz bardziej licznych i jednocześnie coraz mniej jednorodnych grup województw.

Iterację tą możemy zidentyfikować stosując następującą procedurę. Na wstępie tworzymy ciąg ilorazów wartości funkcji dobroci grupowania w kolejnych iteracjach.

, t=2,...,n-1. (3.8)

Następnie szukamy pary sąsiednich ilorazów, dla której po raz pierwszy zachodzi relacja:

, t=2,...,n-1. (3.9)

Grupowanie obiektów należy przerwać w iteracji t-1 wskazanej w relacji (3.9).

Przykład 3.2

W grupowaniu województw, ze względu na podobieństwo poziomu życia w 2005 r. za pomocą metody Spätha-Szczotki, wykorzystano macierz odległości między województwami (tab. 2.1) oraz uporządkowanie liniowe województw uzyskane za pomocą metody Szczotki (Przykład 2.23). W punkcie wyjścia procedury grupowania województw każde z województw stanowi oddzielną grupę. W kolejnych krokach łączymy dwie sąsiadujące ze sobą grupy województw, dla których funkcja dobroci grupowania (3.5) przyjmuje najmniejszą wartość. Etapy tworzenia grup województw wraz z odpowiadającymi im minimalnymi wartościami funkcji dobroci grupowania zawiera tablica 3.5.

Wyznaczenie ostatecznej konfiguracji grup województw wymaga wskazania iteracji, w której następuje przerwanie tworzenia kolejnych, coraz bardziej licznych i jednocześnie coraz mniej jednorodnych grup województw.

Procedurę rozpoczynamy od obliczenia ilorazów wartości funkcji dobroci grupowania w kolejnych iteracjach (3.7):

i₁=2,107; i₂=1,690; i₃=1,421; i₄=1,316; i₅=1,247; i₆=1,202; i₇=1,204; i₈=1,189; i₉=1,163; i₁₀=1,172; i₁₁=1,162; i₁₂=1,185; i₁₃=1,172; i₁₄=1,150.

W kolejnym kroku sprawdzamy dla każdej pary sąsiednich ilorazów czy zachodzi relacja (3.8). Relacja ta spełniona jest po raz pierwszy dla pary sąsiednich ilorazów dla:

i₇> i₆.

Oznacza to, że grupowanie województw należy zakończyć w iteracji t=6. Tym samym za ostateczne uznajemy następujące grupowanie województw:

G₁={O₁,O₅}

G₂={O₇,O₁₃,O₁₅}

G₃={O₉,O₁₂,O₁₄}

G₄={O₃,O₆}

G₅={O₂}

G₆={O₄}

G₇={O₈}

G₈={O₁₀}

G₉={O₁₁}

G₁₀={O₁₆}

Tab. 3.5. Przebieg grupowania województw metodą Spätha-Szczotki.

Kroki	Łączne grupy	Wartości funkcji dobroci grupow.
1	{O₁},{O₅}	1,514
2	{O₁₂},{O₁₄}	3,191
3	{O₁₃},{O₁₅}	5,393
4	{O₃},{O₆}	7,666
5	{O₇},{O₁₃, O₁₅}	10,085
6	{O₉},{O₁₂, O₁₄}	12,573
7	{O₈},{O₁₀}	15,111
8	{O₂},{O₈, O₁₀}	18,187
9	{O₁₁},{O₁₆}	21,617
10	{O₁, O₅},{O₉, O₁₂,O₁₄}	25,140
11	{O₄},{O₃, O₆}	29,468
12	{O₂, O₈, O₁₀},{O₇, O₁₃,O₁₅}	34,231
13	{O₃, O₄, O₆},{O₁₁,O₁₆}	40,556
14	{O₂, O₇, O₈, O₁₀,O₁₃, O₁₅},{O₃, O₄, O₆, O₁₁,O₁₆}	47,541
15	{O₂, O₃, O₄, O₆,O₇, O₈, O₁₀, O₁₁, O₁₃ O₁₅ O₁₆},{O₁, O₅, O₉, O₁₂,O₁₄}	54,691

3.2.3. Metoda maksymalnego gradientu

Podział liniowo uporządkowanych obiektów na grupy według metody maksymalnego gradientu przebiega w oparciu o wartości syntetycznych miar odległości w badanych obiektach(Kolenda, 2006, s. 101-102). Na wstępie ustalamy liczbę grup obiektów (z), którą chcielibyśmy otrzymać w wyniku grupowania. Dla uporządkowanego liniowo ciągu obiektów, ze względu na niemalejące wartości miar syntetycznych, liczymy różnice pomiędzy tymi wartościami dla kolejnych par obiektów:

, i=1,...,n-1. (3.10)

Ciąg obiektów dzielimy na ustaloną grupę podciągów (grup obiektów) przerywając go w z-1 miejscach odpowiadających z-1 najwyższym wartościom bezwzględnym miary (3.10).

Przykład 3.3

Dla grupowania województw, ze względu na podobieństwo poziomu życia w 2005 r., za pomocą metody maksymalnego gradientu wykorzystano wartości miary syntetycznej (s_i) uzyskanej w wyniku zastosowania miary rozwoju (Przykład 2.4). Na wstępie założyliśmy podział województw na z=4 grupy. Dla uporządkowanego ciągu województw, ze względu na rosnące wartości zmiennej syntetycznej, obliczono różnice pomiędzy tymi wartościami dla kolejnych par województw (tab. 3.6).

Aby uzyskać grupy województw nasz uporządkowany ciąg województw powinniśmy przerwać w z-1=3 miejscach, ze względu na największe wartości różnic pomiędzy zmiennymi syntetycznymi dla sąsiednich województw (s_i+1-s_i). W kroku 1 uzyskano największą różnicę pomiędzy zmiennymi syntetycznymi dla województw O₈ i O₁₅ równą 0,059. Tym samym dokonujemy podziału województw na 2 grupy:

0x01 graphic

Następnie usunięto z ciągu różnic wartość maksymalną i ponownie wyznaczono wartość maksymalną różnic zmiennych syntetycznych (krok 2). Była to wartość 0,047 między województwami O₉ i O₃.

W efekcie grupa województw G₂ rozpadła się na dwie podgrupy:

0x01 graphic

Po usunięciu z ciągu różnic pomiędzy wartościami zmiennej syntetycznej wartości maksymalnej, w kroku 3 wyznaczono kolejną wartość maksymalną. Wartość ta odnosiła się do województw O₁₄ i O₁₃i wynosiła 0,045. Powoduje to podział grupy województw G₂ na dwie nowe podgrupy i uzyskanie następujących, ostatecznych grup województw o podobnym poziomie życia w 2005 r.:

Tab. 3.6. Przebieg grupowania województw według metody maksymalnego gradientu.

Województwo

Wartości zmiennej syntetycznej

Bezwzględne wartości różnic

krok 1

krok 2

krok 3

Mazowieckie

Opolskie

Wielkopolskie

Małopolskie

Dolnośląskie

Podlaskie

Pomorskie

Zachodniopomorskie

Lubuskie

Kujawsko-Pomorskie

Łódzkie

Warmińsko-Mazurskie

Świętokrzyskie

Śląskie

Podkarpackie

Lubelskie

0,617

0,614

0,555

0,528

0,496

0,459

0,452

0,431

0,392

0,381

0,348

0,304

0,259

0,242

0,219

0,172

0,003

0,059

0,026

0,032

0,037

0,007

0,021

0,034

0,017

0,033

0,044

0,045

0,018

0,023

0,047

0,003

0,026

0,032

0,037

0,007

0,021

0,034

0,017

0,033

0,044

0,045

0,018

0,023

0,047

0,003

0,026

0,032

0,037

0,007

0,021

0,034

0,017

0,033

0,044

0,045

0,018

0,023

3.2.4. Metoda odchyleń standardowych

W metodzie tej, przy grupowaniu obiektów uporządkowanych liniowo, dzielimy obiekty na grupy w oparciu o badanie odchyleń wartości zmiennej syntetycznej obiektów od średniej wartości tej zmiennej syntetycznej o wartości odchyleń standardowych (Nowak, 1990, s. 93). Zbiór badanych obiektów jest dzielony na cztery grupy, zawierające obiekty o wartościach zmiennej syntetycznej należącej do następujących czterech przedziałów klasowych:

(3.11)

gdzie:

- odpowiednio wartość średniej arytmetycznej i odchylenia standardowego zmiennej syntetycznej.

Przykład 3.4

Na podstawie wartości miary syntetycznej dla województw (s_i), uzyskanej w wyniku zastosowania miary rozwoju (Przykład 2.4), dokonano grupowania województw ze względu na osiągnięty poziom życia w 2005 r., za pomocą metody odchyleń standardowych. Wartości średniej arytmetycznej oraz odchylenia standardowego zmiennej syntetycznej wyniosły:

W oparciu o powyższe wartości uzyskano następujące podziały zmienności zmiennej syntetycznej dla grup województw:

0x01 graphic

Ostatecznie otrzymano następujące cztery grupy województw o podobnym poziomie życia w 2005 r., od poziomu najwyższego do poziomu najniższego:

0x08 graphic

3.3. Metody aglomeracyjne

3.3.1. Metody podziału dendrytu

Metody dendrytowe prowadzą do nieliniowego uporządkowania obiektów w postaci dendrytu i podobnie jak metody podziału dendrogramu tworzą niechierachiczny system grup obiektów. Grupowanie obiektów w oparciu o dendryt polega na jego podziale na części, zawierające homogeniczne grupy obiektów. Podział ten jest przeprowadzany poprzez usuwanie kolejnych, najdłuższych krawędzi dendrytu. Liczba grup, na które dzielimy badane obiekty, może zostać ustalona z góry lub też oparta o wykorzystanie wartości pewnych wskaźników, pozwalających na identyfikację krawędzi, które należy przerwać w dendrycie.

W pierwszym wariancie metody podziału (Florek i in., 1951) ustalamy liczbę grup z, na które dzielimy badane obiekty, co jest tożsame z podziałem dendrytu na z części. Następnie usuwamy z dendrytu z-1 najdłuższych wiązadeł uzyskując założoną liczbę grup obiektów. Autorzy taksonomii wrocławskiej zaproponowali dwie metody podziału dendrytu w sytuacji gdy nie ustalamy z góry liczby grup obiektów.

W pierwszej z metod, prowadzącej do tzw. naturalnego podziału dendrytu, na wstępie porządkujemy nierosnąco wiązadła dendrytu:

gdzie:

d₁,d₂,...,d_n-1 - uporządkowane długości wiązadeł.

Następnie obliczamy ilorazy długości sąsiednich wiązadeł:

, k=1,2,...,n-1, (3.12)

gdzie:

d_k - długość k-tego wiązadła w uporządkowanym nierosnąco szeregu długości wiązadeł.

W kolejnym kroku dla każdej pary sąsiednich ilorazów sprawdzamy czy zachodzi relacja:

, k=1,2,...,n-1. (3.13)

Jeżeli relacja (3.13) spełniona jest tylko dla jednej pary sąsiednich wiązadeł to zbiór obiektów należy podzielić na z=k grup, usuwając z grafu k-1 najdłuższych wiązadeł. Natomiast w sytuacji gdy kryterium (3.13) spełnione jest więcej niż jeden raz wprowadzamy dodatkowe kryterium, pozwalające wybrać lepszy spośród dwóch podziałów dendrytu, o postaci:

, k,k'=1,2,...,n-1; k≠k'. (3.14)

Lepszym podziałem dendrytu jest, według powyższego kryterium, podział na z=k grup niż podział na z'=k' grup. Oznacza to, że dla ustalenia liczby wiązadeł, które uzuwamy z dendrytu bierzemy pod uwagę najmniejszy iloraz sąsiednich wiązadeł z ilorazów spełniających warunek (3.12). Uzyskany podział na grupy obiektów nazywany jest podziałem naturalnym, gdyż dendryt rozpada się w sposób niejako naturalny.

W drugim z wariantów grupowania obiektów stosujemy tzw. podział mocny dendrytu. W pierwszym kroku obliczamy wartości różnic pomiędzy długościami sąsiednich wiązadeł, w ciągu uporządkowanych nierosnąco długości wiązadeł, na podstawie rekurencyjnego wzoru o postaci:

, k=1,2,...,n-1, (3.15)

przy czym:

Następnie obliczane są wskaźniki mocy podziału wskazujące na zmianę jakości grupowania obiektów, przy przejściu od grupowania na z=k części do grupowania na z+1=k+1 części, o postaci:

k=1,2,...,n-2. (3.16)

Podział dendrytu na z=k części nazywamy mocnym gdy zachodzi następująca relacja:

. (3.17)

Kolejna metoda grupowania obiektów oparta na podziale dendrytu została zaproponowana przez Z. Helliwiga (1968). Polega ona na usuwaniu z dendrytu tych krawędzi, których długość jest większa od pewnej wartości krytycznej d^*. Wartość krytyczna jest obliczana w oparciu o następującą formułę:

, (3.18)

gdzie:

0x01 graphic
.

Przykład 3.5

W oparciu o dendryt uzyskany w wyniku porządkowania województw za pomocą metod dendrytowych (rys. 2.5) przeprowadzono grupowanie województw Polski ze względu na podobieństwo poziomu życia osiągniętego z 2005 r. Założono podział województw na 4 grupy. Następnie usunięto z dendrytu 3 najdłuższe wiązadła (rys. 3.1) uzyskując w efekcie następujące grupy województw o podobnym poziomie życia:

G₁={O₁₂},

G₂={O₉},

G₃={O₅},

G₄={O₁, O₂, O₃, O₄, O₆,O₇, O₈, O₁₀, O₁₁,O₁₃,O₁₄ O₁₅, O₁₆}.

Rys. 3.1. Podział dendrytu na cztery składowe.

0x01 graphic

Źródło: Opracowanie własne.

Przykład 3.6

Dendryt będący ilustracją porządkowania województw Polski za pomocą metod dendrytowych (rys. 2.5) stanowił punkt wyjścia do grupowania województw ze względu na podobieństwo poziomu życia w 2005 r., bez zakładania z góry liczby grup.

W pierwszej z metod grupowania, dającej w efekcie tzw. naturalny podział dendrytu, porządkujemy nierosnąco wiązadła dendrytu:

d_5,12=3,43; d_6,9=3,19; d_1,5=2,87; d_2,13=2,86; d_2,10=2,71; d_8,10=2,54; d_6,7=2,35; d_4,16=2,34; d_6,15=2,28; d_3,13=2,27; d_6,10=2,26; d_6,11=2,20; d_4,14=2,01; d_2,14=1,68; d_1,16=1,51.

Następnie tworzymy ilorazy sąsiednich wiązadeł:

0x01 graphic

W kolejnym kroku dla każdej pary sąsiednich ilorazów wiązadeł sprawdzamy czy zachodzi relacja (3.14). Relacja ta jest spełniona dla następujących par sąsiednich wiązadeł:

i₁<i₂; i₃<i₄; i₄<i₅; i₅<i₆; i₇<i₈; i₉<i₁₀; i₁₀<i₁₁; i₁₁<i₁₂; i₁₂<i_13.

Tym samym dla ustalenia jaką liczbę najdłuższych wiązadeł należy usunąć z dendrytu bierzemy pod uwagę następujące ilorazy wiązadeł:

i₁; i₃; i₄; i₅; i₆; i₇; i₉; i₁₀; i₁₁; i_12.

Spośród powyższych ilorazów wiązadeł wybieramy, stosując kryterium dodatkowe (3.15), najmniejszy iloraz, tzn. i₃. Oznacza to, że z dendrytu należy usunąć k-1=2 najdłuższe wiązadła (rys. 3.2).

Rys. 3.2. Podział naturalny na 4 składowe.

0x01 graphic

Źródło: Opracowanie własne.

Ostatecznie uzyskujemy następujące grupy województw, o podobnym poziomie życia w 2005r.:

G₁={O₁₂},

G₂={O₉},

G₃={O₁, O₂, O₃, O₄, O₅, O₆, O₇, O₈, O₁₀, O₁₁,O₁₃, O₁₄, O₁₅, O₁₆}.

W tzw. podziale mocnym dendrytu punktem wyjścia jest, tak jak w poprzedniej metodzie podziału dendrytu, uporządkowany nierosnąco ciąg wiązadeł. W pierwszym kroku zostały obliczone wartości różnic między sąsiednimi wiązadłami na podstawie wzoru rekurencyjnego (3.16):

u₁=36,5; u₂=33,07; u₃=29,88; u₄=27,01; u₅=24,15; u₆=21,44; u₇=18,9; u₈=16,55; u₉=14,21; u₁₀=11,93; u₁₁=9,66; u₁₂=7,4; u₁₃=5,2; u₁₄=3,19; u₁₅=1,68.

Następnie zostały wyznaczone wskaźników mocy podziału w oparciu o formułę (3.17):

m₁=1,083; m₂=1,107; m₃=1,106; m₄=1,118; m₅=1,126; m₆=1,134; m₇=1,142; m₈=1,165; m₉=1,191; m₁₀=1,235; m₁₁=1,305; m₁₂=1,423; m₁₃=1,630; m₁₄=1,899.

Relacja (3.18) jest spełniona dla wskaźnika mocy podziału m₂. Oznacza to, że z dendrytu należy usunąć k=2 najdłuższe wiązadła (rys. 3.2). W efekcie uzyskujemy identyczny podział województw na grupy jak przy naturalnym podziale dendrytu.

W kolejnym wariancie metody podziału dendrytu zastosowano metodę zaproponowaną przez Z. Hellwiga. Uzyskano następującą krytyczną wartość długości wiązadła:

d*=2,433+2⋅0,519=3,741.

W rozpatrywanym dendrycie wszystkie wiązadła mają mniejszą długość od wartości krytycznej. Tym samym wszystkie analizowane województwa tworzą jedną grupę.

3.3.2. Metody podziału drzewka połączeń

W wyniku porządkowania nieliniowego w oparciu o metody drzewkowe uzyskujemy hierarchiczny system grup obiektów, w postaci drzewka połączeń (dendrogramu), rozłączny na każdym z jego poziomów. Innymi słowy poszczególne grupy obiektów nie mają wspólnych elementów (obiektów), lecz zawierają się w sobie w sposób hierarchiczny. W celu wyodrębnienia grup obiektów jak najbardziej do siebie podobnych, ze względu na opisujące je zmienne, musimy dokonać podziału drzewka.

W tym celu szukamy krytycznej wartości odległości (d*) przy której przecinamy gałęzie drzewka tworząc w ten sposób grupy obiektów. Decyzja co do ustalenia wartości krytycznej jest decyzją o charakterze subiektywnym. Wartość ta powinna być większa od najmniejszej odległości, na której spotykają się obiekty na drzewku połączeń (w przeciwnym przypadku otrzymamy same grupy jednoelementowe) oraz mniejsza od największej z odległości na drzewku połączeń przy jakiej wszystkie obiekty tworzą jedną grupę. Dla wyznaczenia krytycznej wartości odległości możemy korzystać z pewnych technik wspomagających (Stanisz, 2007, s. 142-143).

Pierwsza technika polega na analizie dendrogramu pod względem różnic odległości między kolejnymi etapami grupowania obiektów (odległości między kolejnymi węzłami, gdzie uformowała się kolejna grupa obiektów).

Duża różnica tych odległości wskazuje, że łączymy ze sobą grupy obiektów relatywnie mało podobnych. Podziału drzewka (przecięcia jego gałęzi) powinniśmy dokonywać właśnie w takich miejscach. Tym samym krytyczna wartość odległości powinna zawierać się w przedziale pomiędzy długościami gałęzi tworzonych przez łączone, relatywnie niepodobne do siebie grupy obiektów. Wzór na obliczanie krytycznej wartości odległości, przy której powinno nastąpić „ścięcie” gałęzi drzewka, możemy przedstawić następująco:

, h=2,3,...,n-1, (3.19)

gdzie:

d_h - długość h-tej gałęzi drzewka,

- wartość krytyczna odległości odpowiadająca h-1 długości gałęzi drzewka.

Dla wyznaczenia wartości krytycznej odległości możemy korzystać z wykresu przebiegu porządkowania nieliniowego obiektów w postaci drzewka. Na wykresie tym przedstawione są odległości połączeń (wiązań) grup obiektów w kolejnych etapach tworzenia drzewka. Gdy na wykresie pojawia się wyraźne spłaszczenie, za którym następuje dłuższa linia pionowa, oznacza to że po etapach łączenia grup obiektów relatywnie silnie do siebie podobnych nastąpiło połączenie grup obiektów relatywnie do siebie mało podobnych. Odległość ta powinna być uznana za odległość krytyczną, wyznaczającą miejsce „cięcia” gałęzi drzewka. Postępowanie powyższe stanowi graficzny odpowiednik reguły (3.19).

Podobną regułę wyznaczania krytycznej wartości odległości zaproponował T. Grabiński (1992). Jej postać można przedstawić od strony formalnej następująco:

0x01 graphic
, h=2,3,..,n-1. (3.20)

Kolejną regułę wyznaczania krytycznej wartości odległości przedstawił R. Mojena (1997). Wartość ta powinna spełniać następującą nierówność:

, (3.21)

gdzie:

- odpowiednio średnia arytmetyczna i odchylenie standardowe długości gałęzi drzewka,

k - parametr, którego wartości według R. Mojeny powinny zawierać się w przedziale <2;5;350>. W innych pracach sugerowana jest optymalna wartość parametru równa 1,25 (Stanisz, 2007, s. 142).

Przykład 3.7

W oparciu o dendrogram (rys. 2.18) oraz opis i wykres przebiegu grupowania (aglomeracji) województw (rys. 2.17) przeprowadzimy podział województw na grupy o podobnym poziomie życia w 2005 r. Krytyczna wartość odległości, przy której przecinamy gałęzie drzewka, została ustalona wariantowo według formuł (3.20), (3.21) oraz (3.22).

Według formuły różnicowej (3.20) wartość krytyczna odległości wynosi (tab. 3.7):

d*>4,512.

Przecięcie gałęzi drzewka przy powyższym warunku prowadzi do utworzenia trzech, następujących grup województw:

0x01 graphic

Obliczona według formuły ilorazowej (3.21) wartość krytyczna odległości spełnia nierówność (tab. 3.7):

d*>1,677.

Przyjęcie wartości krytycznej odległości spełniającej powyższą nierówność powoduje utworzenie następujących grup województw:

Tabela 3.7. Wyznaczanie krytycznej wartości odległości.

Kroki aglomeracji

1,514

1,677

2,202

2,273

2,383

2,435

2,538

3,048

3,337

3,430

3,971

4,067

4,512

5,194

5,573

0,163

0,525

0,071

0,110

0,052

0,103

0,510

0,289

0,093

0,541

0,096

0,445

0,682

0,379

1,108

1,317

1,032

1,048

1,022

1,042

1,201

1,095

1,028

1,158

1,024

1,109

1,151

1,073

Wreszcie wartość krytyczna odległości oszacowana w oparciu o regułę Mojeny (3.22), przyjmując wartość parametru k=1,25, spełnia warunek:

d*>3,210+1,25⋅1,239=4,759.

Prowadzi to ostatecznie do utworzenia identycznego grupowania województw jak przy szacunku wartości krytycznej odległości za pomocą formuły różnicowej.

3.4. Metody deglomeracyjne

Metody deglomeracyjne prowadzą, podobnie jak metody aglomeracyjne do hierarchicznego systemu grup obiektów. Przedstawicielem tej grupy metod są procedury zaproponowane przez L. Huberta (1973). Ogólny algorytm tych metod można przedstawić następująco (Gabiński i in., 1989, s. 66-67). Na wstępie zakłada się, że wszystkie obiekty tworzą jedną grupę (G). Następnie wyznaczamy parę obiektów najbardziej od siebie odległych (O_i'i O_i”), dla których spełniony jest warunek:

, i',i”=1,2,...,n; i'≠i”. (3.22)

Grupę obiektów G dzielimy na dwie podgrupy (G_r',G_r”). Obiekt O_i' przydziela się do grupy G_r' a obiekt O_i” do grupy G_r”. Jednocześnie obiekty O_i' i O_i” usuwamy z grupy G. W kolejnym kroku przyporządkowujemy pozostałe obiekty z grupy G do grupy G_r',G_r”. Następnie zastępujemy grupę obiektów G dwoma nowopowstałymi grupami G_r'i G_r”, zwiększając tym samym początkową liczbę grup obiektów o jeden. Procedurę podziału grup obiektów kontynuujemy, w analogiczny sposób, do momentu gdy każdy obiekt stanowi odrębną, jednoelementową grupę. W zależności od sposobu przyporządkowania obiektów należących do grupy na wyższym szczeblu agregacji (np. grupy G) do grup obiektów na bezpośrednio niższym szczeblu agregacji (np. grup G_r'i G_r”) wyróżniane są trzy warianty metody.

W wyniku zastosowania metod deglomeracyjnych uzyskujemy hierarchiczny system grup obiektów. W celu wyodrębnienia grup obiektów najbardziej do siebie podobnych, ze względu na opisujące je zmienne musimy wskazać, w którym momencie należy przerwać proces deglomeracji. Pewne sugestie w tym zakresie zostały przedstawione w Przykładzie 3.8.

3.4.1. Metoda najbliższej grupy

Wśród obiektów pozostałych w grupie na danym szczeblu (np. w grupie G) szukamy obiektu najbardziej odległego od wszystkich obiektów już przyporządkowanych do dwóch grup na bezpośrednio niższym szczeblu agregacji (np. w grupach G_r'i G_r”). Jeżeli obiekt ten jest najbardziej odległy od obiektu w pierwszej z grup (np. z grupy G_r') to przydzielamy go do drugiej z grup (np. do grupy G_r”) i usuwamy z grupy na danym szczeblu agregacji (np. z grupy G). W sytuacji gdy obiekt jest najbardziej odległy od obiektu z drugiej grupy (np. z grupy G_r”) to przydzielamy go do pierwszej z grup (np. do grupy G_r') i usuwamy go z grupy na danym szczeblu agregacji (np. z grupy G).

3.4.2. Metoda najbliższego obiektu

Wśród obiektów pozostałych w grupie obiektów na danym szczeblu agregacji (np. z grupy G) szukamy obiektu najmniej odległego od wszystkich obiektów już przydzielonych do grup obiektów na bezpośrednio niższych szczeblach agregacji (np. w grupach G_r'i G_r”). Obiekt ten przydzielamy do tej grupy obiektów na bezpośrednio niższym szczeblu agregacji, od której jest najmniej odległy i usuwamy go z grupy obiektów na danym szczeblu agregacji (np. z grupy G).

3.4.3. Metoda dalszego z najbliższych obiektów

Wśród obiektów pozostałych w grupie na danym szczeblu agregacji (np. w grupie G) szukamy obiektu, dla którego najmniejsza z odległości od wszystkich już przyporządkowanych do grup obiektów na bezpośrednio niższym szczeblu agregacji (np. grup G_r'i G_r”) jest większa. Obiekt ten przydzielamy do grupy, od której jest on bardziej oddalony i usuwamy go z grupy obiektów na danym szczeblu agregacji (np. z grupy G).

Przykład 3.8

Na podstawie macierzy odległości pomiędzy województwami (tab. 2.1) przeprowadzono grupowanie województw, ze względu na podobieństwo poziomu życia w 2005 r., za pomocą metody najbliższego obiektu należącej do grupy metod deglomeracyjnych. Punktem wyjścia metody jest poszukiwanie pary województw najbardziej o siebie oddalonych. Parą województw najbardziej od siebie oddalonych wśród badanych województw w grupie G, którą tworzą wszystkie badane województwa, są województwa O₅ i O₉ (d_5,9=5,573). Zbiór województw G dzielimy na dwie grupy G₁ i G₂. Województwo O₅ przydzielamy do grupy G₁(O₅ ∈ G₁), a województwo O₉do grupy G₂(O₉ ∈ O₂). Oba województwa, O₅ i O₉, usuwamy z grupy G. W kolejnym kroku przyporządkowujemy województwa pozostające w grupie G do nowoutworzonych grup G₁ i G₂. Do przyporządkowania województw do tych grup stosujemy metodę najbliższego obiektu. W wierszach 5-tym i 9-tym macierzy odległości poszukujemy elementu, o najmniejszej wartości (poszukujemy najmniejszej odległości). Wskazuje on województwo, które należy najpierw przyłączyć do nowoutworzonych grup obiektów G₁ i G₂oraz grupę, do której przyłączamy to województwo. Najmniejszą odległością jest odległość d_1,5=2,873. Tym samym województwo O₁ przyłączamy do grupy G₁. W podobny sposób kwalifikujemy do grup G₁ i G₂pozostałe województwa, za każdym razem przyłączając województwo do tej grupy od której dowolnego elementu (województwa) leży ono najbliżej. Tym samym w odpowiednich wierszach macierzy odległości (tab. 2.1), odpowiadających województwom należącym w danym momencie do grup G₁ albo G₂, poszukujemy najmniejszych elementów wskazujących, które z województw i do której z grup kolejno przyłączamy.

W efekcie powyższego postępowania skład grup G₁ i G₂ przedstawia się następująco (kolejność województw w ramach grupy, wskazuje na kolejność ich włączania do tej grupy):

G₁={O₅, O₁, O₁₆, O₄, O₁₄, O₂, O₁₀, O₆, O₁₅, O₇, O_8, O₁₃, O₁₂, O₁₃, O₃},

G₂={O₉}.

W następnym kroku procedury dzielimy województwa należące do grupy G₁ na dwie grupy G₁₁ i G₁₂. W tym celu szukamy w grupie G₁najbardziej oddalonych od siebie województw. Są nimi województwa O₈ i O₁₂(d_8,12=5,5488). Województwo O₈przydzielamy do grupy G₁₁, a województwo O₁₂do grupy G₁₂. Następnie przydzielamy do grup G₁₁ i G₁₂pozostałe województwa z grupy G₁. W tym celu w odpowiednich wierszach macierzy odległości (tab. 2.1) odpowiadających województwom należącym w danym momencie do grup G₁₁ albo G₁₂, poszukujemy najmniejszych elementów wskazujących, do której z grup przyłączamy dane województwo.

Ostatecznie grupy G₁₁ i G₁₂składają się z następujących województw:

G₁₁={O₈, O₁₀, O₆, O₁₁, O₁₅, O₇, O₂, O₁₄, O₄, O₁₆, O_1, O₁₃, O₃, O₅},

G₁₂={O₁₂}.

W dalszym kroku dokonujemy podziału grupy G₁₁na dwie podgrupy G₁₁₁ i G₁₁₂. Najbardziej oddalonymi województwami w grupie G₁₁, stanowiącymi jednocześnie pierwsze elementy podgrup G₁₁₁ i G₁₁₂, są województwa O₃ i O₈(d_3,8=5,1936). Do grup G₁₁₁ i G₁₁₂zostały ostatecznie przyporządkowane następujące województwa:

G₁₁₁={O_3, O₁₃},

G₁₁₂={O₈, O₁₀, O₆, O₁₁, O₁₅, O₇, O₂, O₁₄, O₄, O₁₆, O_1, O₅}.

Grupa G₁₁₁rozpada się na dwie jednoelementowe podgrupy:

G₁₁₁={O₃},

G₁₁₂={O₁₃}.

Natomiast w grupie G₁₁₂najbardziej oddalonymi od siebie województwami są województwa O₄ i O₇(d_4,7=4,5115), które są pierwszymi elementami podgrup województw tworzących w wyniku podziału grupy G₁₁₂. W wyniku tego podziału zostały utworzone dwie następujące grupy województw:

G₁₁₂₁={O₄, O₁₄, O₂, O₁₆, O_1, O₅},

G₁₁₂₂={O₇, O₆, O₁₁, O₁₀, O₁₅, O₈}.

W następnym etapie przeprowadzamy podział grupy G₁₁₂₁₁na podgrupy G₁₁₂₁₁oraz G₁₁₂₁₂. Najbardziej oddalonymi województwami są województwa O₅ i O₁₄(d_5,14=3,8793). Stanowią one pierwsze elementy podgrup województw G₁₁₂₁₁oraz G₁₁₂₁₂. Ostateczny skład tych podgrup województw przedstawia się następująco:

G₁₂₁₁={O₅},

G₁₁₂₁₂={O₁₄, O₂, O₄, O₁₆, O₁}.

W ramach grupy województw G₁₁₂₁₂najbardziej oddalonymi od siebie województwami są województwa O₁ i O₁₄(d_1,14=3,0476).

Tworzą one pierwsze elementy podgrup G₁₁₂₁₂₁i G₁₁₂₁₂₂, których ostateczny skład jest następujący:

G₁₁₂₁₂₁={O_1, O₁₆},

G₁₁₂₁₂₂={O₁₄, O₂, O₄}.

Grupy rozpada się na dwie jednoelementowe podgrupy:

G_1121211={O₁},

G_1121212={O₁₆}.

Natomiast w ramach grupy G₁₁₂₁₂₂najbardziej oddalonymi od siebie województwami są województwa O₂ i O₄(d_2,4=2,5642). Województwo O₄stanowi jednoelementową grupę G_1121221={O₄}. Natomiast województwo O₂oraz z województwem O₁₄stanowią grupę dwuelementową G_1121222={O₂, O₁₄}. Ostatecznie grupa G_1121222rozpada się na dwie grupy jednoelementowe:

G₁₁₂₁₂₂₂₁={O₂},

G_11212222={O₁₄}.

Podział na dwie podgrupy grupy województw G₁₁₂₂przebiegał następująco. W grupie tej najbardziej oddalonymi od siebie województwami były województwa O₇ i O₁₀(d_7,10=4,0670). Stanowią one początkowe elementy podgrup G₁₁₂₂₁oraz G₁₁₂₂₂. W wyniku podziału grupy G₁₁₂₂otrzymano następujące składowe tych podgrup:

G₁₁₂₂₁={O₇},

G₁₁₂₂₂={O₁₀, O₆, O₁₁, O₁₅, O₈}.

Kolejnym etapem procedury jest podział grupy województw G₁₁₂₂₂na dwie podgrupy. Województwami najbardziej od siebie oddalonymi w tej grupie są województwa O₈ i O₁₁(d_8,11=2,2021). Są one początkowymi elementami podgrup województw G₁₁₂₂₂₁i G₁₁₂₂₂₂, które ostatecznie składają się z następujących województw:

G₁₁₂₂₂₁={O₈},

G₁₁₂₂₂₂={O₁₁, O₆, O₁₀, O₁₅}.

W następnym kroku przeprowadzamy podział grupy województw G₁₁₂₂₂₂na dwie podgrupy. W grupie tej najbardziej oddalone od siebie są województwa O₁₁ i O₁₅(d_11,15=3,7693), które stają się początkowymi elementami podgrup G_1122221i G_1122222. Po przeprowadzeniu procedury podziału, grupy te zawierają następujące województwa:

G_1122221={O₁₁, O₆, O₁₀},

G_1122222={O₁₅}.

W kolejnym kroku dokonujemy podziału grupy G_1122221. Województwami najbardziej odległymi od siebie w tej grupie są województwa O₁₀ i O₁₁(d_10,11=3,4631). Stanowią one początkowe elementy dwóch podgrup G_11222211i G_11222212, o następującym, ostatecznym składzie:

G_11222211={O₁₀},

G_11222212={O₁₁, O₆}.

W ostatnim kroku grupa G_11222212ulega podziałowi na dwie jednoelementowe podgrupy:

G_112222121={O₁₁},

G_112222122={O₆}.

W efekcie zaprezentowanej procedury otrzymaliśmy w ostatnim etapie 16 jednoelementowych grup województw.

Schemat deglomeracji zbioru województw, prowadzący do hierarchicznego systemu ich grup, przedstawiono na rysunku 3.3. W celu wyznaczenia ostatecznej konfiguracji grup obiektów możemy skorzystać z przedstawionej na podstawie tego schematu w tablicy 3.8 konfiguracji grup na kolejnych poziomach deglomeracji. Na danym poziomie deglomeracji występują grupy województw będące wynikiem podziału grup województw wieloelementowych występujących na poziomie bezpośrednio niższym oraz grupy województw na poziomie bezpośrednio niższym nie podlegające dalszej dezagregacji (grupy jednoelementowe). W zasadzie powinniśmy przyjąć jako rozwiązanie ostateczne konfigurację grup województw na jednym z poziomów.

Rys. 3.3. Schemat przebiegu deglomeracji.

0x01 graphic

Źródło: Opracowanie własne.

Tabl. 3.8. Grupy województw na kolejnych poziomach deglomeracji.

Poziom deglomeracji	Grupy województw
0	G={O₁, O₂, O₃, O₄, O₅, O₆, O₇, O₈, O₉, O₁₀, O_11, O₁₂, O₁₃, O₁₄, O₁₅, O₁₆}
1	G₁={O₅, O₁, O₁₆, O₄, O₁₄, O₂, O₁₀, O₆, O₁₅, O₇, O_8, O₁₃, O₁₂, O₁₃, O₃}; G₂={O₉}
2	G₁₁={O₈, O₁₀, O₆, O₁₁, O₁₅, O₇, O₂, O₁₄, O₄, O₁₆, O_1, O₁₃, O₃, O₅}; G₁₂={O₁₂}; G₂={O₉}
3	G₁₁₁={O₃, O₁₃}; G₁₁₂={O₁₂}; G₁₂={O₁₂}; G₂={O₉}
4	G₁₁₁₁={O₃}; G₁₁₁₂={O₁₃}; G₁₁₂₁={O₄, O₁₄, O₂, O₁₆, O_1, O₅}; G₁₁₂₂={O₇, O₆, O₁₁, O₁₀, O₁₅, O₈}; G₁₂={O₁₂}; G₂={O₉}
5	G₁₁₁₁={O₃}; G₁₁₁₂={O₁₃}; G₁₁₂₁₁={O₅}; G₁₁₂₁₂={O₁₄, O₂, O₄, O₁₆, O₁}; G₁₁₂₂₁={O₇}; G₁₁₂₂₂={O₁₀, O₆, O₁₁, O₁₅, O₈}; G₁₂={O₁₂}; G₂={O₉}
6	G₁₁₁₁={O₃}; G₁₁₁₂={O₁₃}; G₁₁₂₁₁={O₅}; G₁₁₂₁₂₁={O₁, O₁₆}; G₁₁₂₁₂₂={O₁₄, O₂, O₄}; G₁₁₂₂₁={O₇}; G₁₁₂₂₂₁={O₈}; G₁₁₂₂₂₂={O₁₁, O₆, O₁₀, O₁₅}; G₁₂={O₁₂}; G₂={O₉}
7	G₁₁₁₁={O₃}; G₁₁₁₂={O₁₃}; G₁₁₂₁₁={O₅}; G_1121211={O₁}; G_1121212={O₁₆}; G_1121221={O₄}; G_1121222={O₁₄, O₂}; G₁₁₂₂₁={O₇}; G₁₁₂₂₂₁={O₈}; G_1122221={O₁₁, O₆, O₁₀}; G_1122222={O₁₅}; G₁₂={O₁₂}; G₂={O₉}
8	G₁₁₁₁={O₃}; G₁₁₁₂={O₁₃}; G₁₁₂₁₁={O₅}; G_1121211={O₁}; G_1121212={O₁₆}; G_1121221={O₄}; G_11212221={O₁₄}; G_11212222={O₂}; G₁₁₂₂₁={O₇}; G₁₁₂₂₂₁={O₈}; G_11222211={O₁₀}; G_11222212={O₁₁, O₆}; G₁₁₂₂₂₂={O₁₅}; G₁₂={O₁₂}; G₂={O₉}
9	G₁₁₁₁={O₃}; G₁₁₁₂={O₁₃}; G₁₁₂₁₁={O₅}; G_1121211={O₁}; G_1121212={O₁₆}; G_1121221={O₄}; G_11212221={O₁₄}; G_11212222={O₂}; G₁₁₂₂₁={O₇}; G₁₁₂₂₂₁={O₈}; G_11222211={O₁₀}; G_112222121={O₁₁}; G_112222122={O₆}; G₁₁₂₂₂₂={O₁₅}; G₁₂={O₁₂}; G₂={O₉}

3.5. Metody optymalizacji danego grupowania obiektów

Punktem wyjścia metod optymalizacyjnych jest ustalenie pożądanej liczby grup obiektów, które chcemy utworzyć. Następnie ustalamy wstępny skład poszczególnych grup. Skład tych grup może być ustalany m. in. w sposób następujący (Grabiński i in., 1989, s. 77-78):

w sposób losowy,
korzystając z ocen ekspertów,
poprzez wykorzystanie arbitralnie wybranej zmiennej,
przyjmując jako wstępne grupowanie, grupowanie otrzymane za pomocą dowolnej metody taksonomicznej,
porządkując obiekty według ich odległości od środka ciężkości poszczególnych grup obiektów. Środkami ciężkości grup obiektów stają się obiekty o numerach określonych za pomocą wzoru:
, gdzie r jest kolejnym numerem grupy.

Metody optymalizacyjne dążą do poprawienia dobroci wstępnego grupowania obiektów poprzez optymalizację grupowania polegającą na przesuwaniu obiektów między grupami. Optymalizacja grupowania dokonywana jest z punktu widzenia zdefiniowanego kryterium dobroci grupowania.

Poszczególne metody optymalizacyjne różnią się między sobą ze względu na różnie definiowane kryteria optymalizacyjne oraz różne procedury postępowania.

3.5.1. Metoda k-średnich

Rolę funkcji kryterium dobroci grupowania obiektów w metodzie k-średnich pełnią tzw. błędy grupowania (podziału). Za twórcę tej metody najczęściej uważany jest J. B. Mac Queen (1967).

Metoda k-średnich posiada szereg wariantów (Grabiński i in., 1989, s. 78) różniących się między sobą przede wszystkim właśnie sposobem zdefiniowania funkcji kryterium dobroci grupowania oraz reguł ustalania środków ciężkości początkowej konfiguracji grup, przesuwania obiektów między grupami w procesie optymalizacji grupowania, ustalania wstępnego grupowania obiektów i zatrzymywania procesu poprawiania dobroci grupowania.

Za klasyczny wariant metody k-średnich uważany jest wariant zaproponowany przez J. A. Hartigana (1975). Na wstępie ustalamy liczbę grup, do których klasyfikujemy obiekty oraz maksymalną liczbę iteracji poprawiania dobroci grupowania. Potem ustalamy środki ciężkości wstępnych grup obiektów:

0x01 graphic
, r=1,2,...,z, (3.23)

gdzie:

- wartość j-tej zmiennej dla i^c-tego środka ciężkości danej grupy obiektów.

Następnie do poszczególnych grup przyporządkowujemy obiekty. Dany obiekt przyporządkowujemy do tej grupy, dla której odległość tego obiektu od środka ciężkości jest najmniejsza.

W kolejnym kroku wyznaczamy wartość wyjściowego błędu grupowania obiektów w oparciu o formułę:

, (3.24)

gdzie:

- odległość euklidesowa między i-tym obiektem, a najbliższym i^c-tym środkiem ciężkości,

- środek ciężkości najbliższy i-temu obiektowi,

przy czym:

, r=1,2,...,z. (3.25)

Następnie w sposób iteracyjny, przemieszczając obiekty pomiędzy grupami, optymalizujemy wstępną konfigurację grup obiektów dążąc do minimalizacji błędów grupowania. W tym celu obliczamy dla pierwszego obiektu zmianę błędu grupowania wynikającą z przyporządkowania go do wszystkich kolejnych grup innych niż grupa, w której aktualnie się on znajduje:

0x01 graphic
, O₁∈G_r; r,r'=1,2,...,z; r≠r'. (3.26)

Jeżeli wartość miary (3.26) jest nieujemna dla wszystkich kolejnych przyporządkowań danego obiektu to pozostawiamy go w grupie, w której znajdował się we wstępnym grupowaniu. W przeciwnej sytuacji przemieszczany obiekt do tej grupy, dla której miernik (3.26) przyjmuje najmniejszą wartość ujemną. Następnie obliczamy ponownie środki ciężkości grup obiektów, po uwzględnieniu przemieszczenia pierwszego obiektu do innej grupy oraz wyznaczamy nową wartość błędu grupowania (3.24). W podobny sposób, jak dla pierwszego obiektu, sprawdzamy możliwość poprawy dobroci grupowania poprzez przemieszczanie każdego następnego obiektu do innej grupy niż znajdował się on we wstępnej fazie grupowania, kończąc w ten sposób pierwszą iterację procedury. Jeżeli w trakcie tej iteracji nie nastąpiło żadne przemieszczenie obiektów między grupami oznacza to, że uzyskaliśmy optymalny podział na grupy obiektów. W przeciwnym razie przeprowadzamy kolejne iteracje, aż do momentu gdy w danej iteracji nie nastąpiło żadne przemieszczenie obiektów między grupami lub do momentu gdy osiągnięto założoną liczby iteracji.

Inną wersję metody k-średnich stanowi metoda środków ciężkości. W metodzie tej szukamy optymalnego grupowania obiektów, przesuwając je między grupami, minimalizując ich odległości od środków ciężkości grup (Sparks, 1973), zamiast maksymalizować spadek wartości błędu grupowania. W punkcie wyjścia procedury zakładamy liczbę grup, którą chcemy otrzymać, liczbę iteracji oraz ustalamy wstępny podział obiektów na grupy. Dla każdej z grup obliczamy jej środek ciężkości. Następnie każdy obiekt przypisywany jest do tej grupy, dla której odległość obiektu od środka ciężkości jest najmniejsza i obliczamy środki ciężkości nowych grup. Jeżeli podział na grupy nie uległ zmianie uznajemy go za optymalny. W przeciwnej sytuacji kontynuujemy procedurę aż do momentu gdy w danej iteracji nie nastąpiły zmiany składu grup lub też osiągnięto założoną liczbę iteracji.

W kolejnej wersji metody k-średnich funkcja kryterium dobroci grupowania opiera się na maksymalizacji stosunku zmienności międzygrupowej do zmienności wewnątrzgrupowej (Stanisz, 2007, s. 128), zamiast maksymalizacji spadku wartości błędu klasyfikacji. Punkt wyjścia tej wersji metody jest taki sam jak w dwóch przedstawionych wcześniej jej wersjach. Na wstępie ustalamy podział obiektów na grupy oraz liczbę iteracji, w których dążymy do optymalizacji grupowania. Następnie obliczamy wartość funkcji kryterium dobroci grupowania, którą stanowi stosunek zróżnicowania międzygrupowego do zróżnicowania wewnątrzgrupowego. Miara zróżnicowania międzygrupowego najczęściej jest definiowana jako suma odległości środków ciężkości grup obiektów od środka ciężkości wszystkich badanych obiektów. Natomiast ocenę zróżnicowania wewnątrzgrupowego stanowi wtedy suma odległości wewnątrzgrupowych obiektów od środków ciężkości grup, do którego zostały one sklasyfikowane. Wartość funkcji kryterium może mieć także postać statystyki F stosowanej w analizie wariancji (Podgórski i Jóźwiak, 2005).

W kolejnym kroku obliczamy środki ciężkości dla poszczególnych grup i klasyfikujemy obiekty do grup na podstawie minimalizacji ich odległości od środków grup. Następnie sprawdzamy czy wartość funkcji kryterium nie zwiększyła się. Gdy zmiana taka nie nastąpiła kończymy procedurę przyjmując, że dane grupowanie jest optymalne. W sytuacji przeciwnej przechodzimy do kolejnej iteracji, sprawdzając czy przesunięcia obiektów między grupami nie powodują wzrostu wartości funkcji kryterium dobroci grupowania. Procedurę kontynuujemy do momentu gdy wartość funkcji kryterium dobroci grupowania nie zwiększa się albo gdy osiągnęliśmy założoną liczbę iteracji.

Przykład 3.9

Grupowanie województw, ze względu na poziom życia osiągnięty przez nie w 2005 r., przeprowadzono metodą k-średnich. Wystandaryzowane wartości zmiennych diagnostycznych charakteryzujących poziom życia przedstawiono na rysunku 3.4.

Rys. 3.4. Tablica z danymi do przykładu 3.9.

0x01 graphic

Do grupowania województw wykorzystano pakiet STATISTICA. W tym celu wybieramy z menu Statystyka opcję Wielowymiarowe techniki eksploracyjne/Analiza skupień (rys. 3.5).

Rys. 3.5. Opcje modułu Wielowymiarowe techniki eksploracyjne.

0x01 graphic

Na ekranie otrzymujemy okno Metody grupowania (rys. 3.6).

Rys. 3.6. Okno Metoda grupowania.

0x01 graphic

W oknie Metody grupowania wybieramy opcję Grupowanie metodą k-średnich. Na ekranie otwiera się okno Analiza skupień: Grupowanie metodą k-średnich (rys. 3.7).

Rys. 3.7. Okno ustalania założeń grupowania metodą k-średnich.

0x01 graphic

W ramach powyższego okna wybieramy kartę Więcej klikając odpowiedni klawisz. Otrzymana karta umożliwia określenie założeń grupowania. Na wstępie klikamy klawisz Zmienne co powoduje otwarcie okna Wybierz zmienne do analizy (rys. 3.8).

Rys. 3.8. Okno Wybierz zmienne do analizy.

0x01 graphic

Naszymi zmiennymi są zmienne diagnostyczne charakteryzujące poziom życia województw w 2005 r. Klikamy klawisz Wszystkie i akceptujemy wybór klawiszem OK. Następnie rozwijamy listę Grupuj wybierając opcję Przypadki (wiersze). Tym samym przedmiotem grupowania są województwa w przestrzeni zamiennych. W kolejnym kroku określamy liczbę grup, na które dzielimy zbiór województw. W tym celu w polu Liczba skupień, korzystając z suwaka, wybieramy liczbę 4 decydując się na utworzenie czterech grup województw. W kolejnym polu Liczba iteracji ustalamy liczbę iteracji, w ramach których województwa są przesuwane między grupami. Pozostawiamy domyślne ustawienie 10 iteracji. Gdyby okazało się, że ta liczba iteracji jest zbyt mała możemy po wykonaniu analizy wykonać ją ponownie zwiększając liczbę iteracji.

W dolnej części ekranu znajduje się grupa opcji Wstępne centra skupień, pozwalająca na określenie sposobu wyznaczania wstępnych centrów grup wojewódzkich. Wyniki grupowania województw mogą zależeć od wstępnej konfiguracji grup województw, a tym samym sposobu wyznaczania wstępnych centrów tych grup. Mamy do wyboru jedną z trzech opcji:

Wybierz obserwacje tak, by zmaksymalizować odległości skupień. W ramach tej opcji wstępne centra grup województw są wyznaczane zgodnie z zasadami maksymalizacji odległości między tymi centrami. W pierwszym kroku procedury zostanie wybranych pierwsze z województw (w naszym przykładzie z=4 województwa). Następne województwa zastępują poprzednie centra grup (województwa), gdy najmniejsza z ich odległości od dowolnego z centrów grup jest większa od najmniejszej z odległości między dotychczasowymi centrami grup.

Sortuj odległości i weź przypadki przy stałym interwale. Po wyborze tej opcji wszystkie odległości pomiędzy województwami zostaną posortowane. Następnie na wstępne centra grup zostaną wybrane województwa przy stałym interwale.
Wybierz pierwszych N (liczba skupień) obserwacji. W ramach tej opcji na wstępne centra grup zostałyby wybrane w naszym przykładzie 4 pierwsze województwa.

W naszym przykładzie wybieramy drugą z powyższych opcji. Wybrane założenia grupowania (rys. 3.9) akceptujemy klawiszem OK.

Rys. 3.9. Okno z ustalonymi założeniami grupowania metodą k-średnich.

0x01 graphic

Powoduje to otwarcie okna Wyniki grupowania metodą k-średnich (rys. 3.10).

Rys. 3.10. Okno Wyniki grupowania metodą k-średnich.

0x01 graphic

W górnej części okna znajduje się ogólne podsumowanie wstępnych wyników analizy. Należy zwrócić uwagę, że optymalne grupowanie zostało znalezione już po 3 iteracjach. W dolnej części okna znajdują się klawisze otwierające tablice wynikowe grupowania. Klikając klawisz Elementy każdego skupienia i odległości otwiera się kaskada tablic zawierających składy kolejnych grup województw oraz odległości poszczególnych województw od środków grup, do których należą (rys. 3.11).

Rys. 3.11. Tablice z elementami każdej grupy województw oraz odległościami od środka ciężkości.

0x01 graphic

Uzyskane, w wyniku zastosowania metody k-średnich, grupy województw są następujące:

G₁={O₁, O₂, O₄, O₁₄, O₁₆},

G₂={O₆, O₇, O₈, O₁₀, O₁₁, O₁₅},

G₃={O₃, O₉, O₁₃},

G₄={O₅, O₁₂}.

Używając klawisza Statystyki opisowe każdego skupienia otwieramy okno zawierające tablice z wartościami średnich arytmetycznych, odchyleń standardowych i wariancji zmiennych diagnostycznych dla każdej z grup województw (rys. 3.12).

Rys. 3.12. Tablice ze statystykami opisowymi wystandaryzowanych wartości zmiennych diagnostycznych dla grup województw.

0x01 graphic

Klikając klawisz Podsumowanie: średnie skupień i odległości euklidesowe Otrzymujemy okno zawierające dwie tablice wynikowe. W pierwszej z tablic znajdują się wartości średnich arytmetycznych zmiennych dla utworzonych grup województw (rys. 3.13).

Rys. 3.13. Tablice ze średnimi arytmetycznymi wystandaryzowanych zmiennych diagnostycznych dla grup województw.

0x01 graphic

Druga z tablic zawiera odległości euklidesowe między centrami grup województw (rys. 3.14).

Rys. 3.14. Tablica odległości euklidesowych między centrami grup województw.

0x01 graphic

Klikając klawisz Analiza wariancji uzyskujemy okno zawierające wyniki analizy wariancji (rys. 3.15).

Rys. 3.15. Okno Analiza wariancji.

0x01 graphic

W otrzymanej tablicy znajdują się miary zróżnicowania międzygrupowego i zróżnicowania wewnątrzgrupowego kolejnych zmiennych diagnostycznych wraz z odpowiadającymi im stopniami swobody. Uzyskane, jako stosunek zróżnicowania międzygrupowego do zróżnicowania wewnątrzgrupowego, wartości statystyki F pozwalają na ustalenie hierarchii zmiennych ze względu na ich moc dyskryminacyjną. Podstawowe znaczenie dla ostatecznych wyników grupowania miała zmienna X₈₃.

Używając klawisza Wykres średnich otrzymujemy wykres średnich wartości zmiennych dla każdej z grup województw. Na jego podstawie możemy dokonać analizy porównawczej otrzymanych grup województw ze względu na charakteryzujące je zmienne diagnostyczne. Przykładowo, cechami charakterystycznymi pierwszej z grup województw (rys. 3.16) są relatywnie najniższe, w stosunku do innych grup województw, przeciętne wartości zmiennych X₁₁ oraz X₅₁oraz X₇₁.

Rys. 3.16. Wykres średnich wartości zmiennych dla grup województw.

0x01 graphic

3.5.2. Metoda Forgy-Jancey'a

Kolejną metodą optymalizacyjną jest metoda sformułowana przez E. W. Forgy i R. C. Jancey'a (Forgy 1965; Jancey, 1965). Algorytm metody Forgy-Jancey'a można przedstawić następująco (Grabiński i in., 1989, s. 82; Kucharczyk, 1982). Na wstępie ustalamy liczbę grup obiektów, którą chcemy uzyskać, dokonujemy wstępnej klasyfikacji obiektów do tych grup oraz określamy liczbę iteracji przemieszczania obiektów między grupami. Następnie obliczane są współrzędne środków ciężkości grup, traktowane jednocześnie jako wstępne jądra grup. W kolejnym kroku przemieszczamy każdy obiekt do tej grupy, dla której odległość między tym obiektem, a jądrem grupy jest najmniejsza. Kolejny etap procedury polega na wyznaczeniu jąder nowej grupy w oparciu o wzór:

r=1,2,...,z. (3.27)

gdzie:

- jądro odpowiednio nowej i starej grupy obiektów,

- środek ciężkości starej grupy obiektów,

α - parametr, przyjmujący w zależności od wersji metody, wartości 1, 2 i 1,5.

Kolejne iteracje procedury powtarzamy do momentu aż nie stwierdzimy żadnej zmiany w konfiguracji grup w danej iteracji lub osiągniemy zakładaną liczbę iteracji.

Przykład 3.10

W oparciu o wystymulowane i wystandaryzowane wartości zmiennych diagnostycznych dokonano podziału województw Polski, ze względu na podobieństwo osiągniętego poziomu życia w 2005 r., metodą Forgy-Jancey'a. Na wstępie założono, że województwa zostaną podzielone na 4 grupy. Przyjęto jednocześnie następującą wstępną klasyfikację województw do tych grup:

0x01 graphic

Założono także, że optymalne grupowanie uzyskamy po co najwyżej 20 iteracjach. Szukając optymalnego grupowania województw przyjęto w formule (3.28) wartość parametru α=1. W rozwiązaniu tym za jądra nowych grup uważane są środki ciężkości dotychczasowych grup. Dla każdej z grup województw obliczono jej środek ciężkości, traktowany we wstępnym etapie procedury jako jądro grupy, otrzymując:

0x01 graphic

Następnie każde z województw zostało przyporządkowane do tej grupy, dla której odległość między tym województwem, a jądrem grupy jest najmniejsza. W efekcie uzyskano poniższą klasyfikację grup:

0x01 graphic

Dla każdej grupy obliczono nowe jądro:

0x01 graphic

W kolejnym etapie przeprowadzono nowe przyporządkowanie województw do grup, stosując regułę minimalizacji ich odległości od jąder grup, otrzymując:

0x01 graphic

Współrzędne jąder tych nowych grup przyjęły następujące wartości:

0x01 graphic

Przyporządkowanie województw do grup, uwzględniając ich nowe jądra, nie zmieniło się w stosunku do przyporządkowania uzyskanego w poprzedniej iteracji. Tym samym uzyskaną w wyniku drugiej iteracji klasyfikację województw uważamy za ostateczną.

3.5.3. Metoda Wisharta

W punkcie wyjścia metody Wisharta (Wishart, 1969; Kucharczyk, 1982; Kolenda, 2006, s. 106) ustalamy liczbę grup na które dzielimy badane obiekty (z), minimalną liczbę obiektów w grupach
, odległość progową (d*) wyznaczającą maksymalną dopuszczalną odległość euklidesową obiektu od środka ciężkości grupy oraz maksymalną liczbę iteracji. Ponieważ suma minimalnych liczebności obiektów w grupach może przekroczyć liczbę grupowanych obiektów, ostateczna liczba grup obiektów może być mniejsza od wstępnie ustalonej liczby grup.

Po ustaleniu założeń dokonujemy wstępnego podziału obiektów na ustaloną liczbę grup i wyznaczamy środki ciężkości tych grup. Grupowane obiekty dzielimy na dwie grupy: tzw. grupę nieresztową oraz grupę resztową. Do grupy nieresztowej należą obiekty, których odległości od najbliższych im środków ciężkości są mniejsze od odległości progowej. Obiekty te zostają przyłączone do grup, których środki ciężkości są im najbliższe. Natomiast do grupy resztowej wchodzą obiekty, których odległości od środków ciężkości grup są większe od przyjętej wartości krytycznej.

Następnie sprawdzamy czy liczebności grup obiektów po przesunięciach nie są mniejsze od założonej liczebności minimalnej grup. Obiekty z grup, których liczebności są mniejsze od założonej liczebności minimalnej zostają dołączone do grupy resztowej.

Jeżeli okaże się, że nie zaobserwowano zmian w liczbie i składzie grup obiektów, kończymy grupowanie. Jeżeli natomiast nastąpiły zmiany w dotychczasowym grupowaniu obiektów przestępujemy do drugiej iteracji procedury zaczynając od wyznaczenia środków ciężkości nowych grup obiektów. Postępowanie kończymy gdy w danej iteracji nie wystąpiły zmiany w grupach obiektów lub gdy osiągnięto założoną liczbę iteracji.

Przykład 3.11

W oparciu o wystymulowane i wystandaryzowane wartości zmiennych diagnostycznych (tab. 2.8) przeprowadzono grupowanie województw Polski, ze względu na podobieństwo poziomu życia w tych województwach w 2005 r., za pomocą metody Wisharta.

Na wstępie przyjęto założenie podziału województw na 4 grupy. Ustalono także minimalną liczebność grup
i odległość progową (wyznaczającą maksymalną dopuszczalną odległość województwa od środka ciężkości grupy) d*=3 oraz założono maksymalną liczbę iteracji równą 20. Następnie ustalono następującą wyjściową klasyfikację województw do grup:

0x01 graphic

Dla każdej z grup województw obliczono jej środek ciężkości otrzymując:

0x01 graphic

W kolejnym kroku wyznaczono odległości każdego z województw od środków ciężkości grup:

0x01 graphic

Ponieważ odległości każdego z województw od najbliższych im środków ciężkości grup są mniejsze od przyjętej wartości progowej, wszystkie województwa należą do grupy nieresztowej, a grupa resztowa jest pusta.

Następnie województwa przyporządkowano do tych grup, od których środków ciężkości leżały najbliżej otrzymując:

0x01 graphic

Konfiguracja otrzymanych grup województw uległa zmianie w stosunku do ich wyjściowej konfiguracji. Tym samym przystępujemy do kolejnej iteracji, zaczynając od wyznaczenia środków ciężkości aktualnych grup województw. W efekcie otrzymano następujące środki ciężkości grup województw:

0x01 graphic

Odległości kolejnych województw od środków ciężkości grup zestawiono w macierzy:

0x01 graphic

Ponownie grupa nieresztowa składa się ze wszystkich województw, a grupa resztowa jest pusta. Po przyporządkowaniu województw do grup, od których środków ciężkości ich odległości były najmniejsze otrzymujemy następującą konfigurację tych grup:

0x01 graphic

Konfiguracja grup województw uległa zmianie w stosunku do poprzedniej iteracji. W związku z powyższym obliczamy ponownie środki ciężkości grup województw:

0x01 graphic

Następnie wyznaczamy odległości poszczególnych województw od środków ciężkości grup:

0x01 graphic

Odległości województwa O₁₂ od wszystkich środków ciężkości grup są większe od odległości progowej, a tym samym województwo to wchodzi do grupy resztowej. Pozostałe województwa wchodzą do grupy nieresztowej tworząc jednocześnie następującą konfigurację 4 grup województw:

0x01 graphic

Konfiguracja grup województw uległa zmianie w stosunku do ich konfiguracji w poprzedniej iteracji. Przystępujemy do wyznaczenia środków ciężkości nowych grup otrzymując:

0x01 graphic

Następnie wyznaczamy macierz odległości poszczególnych województw od środków ciężkości grup:

0x01 graphic

Ponownie województwo O₁₂znalazło się w grupie resztowej, a pozostałe województwa tworzą grupę nieresztową. W oparciu o analizę wartości elementów macierzy odległości otrzymujemy następującą konfigurację grup województw:

0x01 graphic

Skład poszczególnych grup województw różni się od ich składu w poprzedniej iteracji. Środki ciężkości tych grup mają następujące współrzędne:

0x01 graphic

Natomiast macierz odległości województw od środków ciężkości aktualnych grup ma postać:

0x01 graphic

Do grupy resztowej należy zaliczyć województwa O₃ oraz O₁₂. Pozostałe województwa tworzą grupę nieresztową.

Grupy województw, utworzone w oparciu o analizę wartości elementów macierzy odległości, są następujące:

0x01 graphic

Skład nowych grup województw uległ zmianie. Ich środki ciężkości mają następujące współrzędne:

0x01 graphic

Natomiast macierz odległości województw od środków ciężkości grup przyjmuje postać:

0x01 graphic

Skład grup województw nie uległ zmianie w stosunku do ostatniej iteracji. Tym samym grupowanie województw z tej iteracji należy uznać za ostateczne. Województwa należące do grupy resztowej tworzą dwie dodatkowe, jednoelementowe grupy.

3.6. Metody obszarowe

W metodach obszarowych przestrzeń wielowymiarową, w której znajdują się punkty reprezentujące obiekty, dzieli się na rozłączne podobszary (Grabiński i in., 1989, s. 71 i dalsze). Podobszary mogą stanowić rozłączne hiperkule lub hiperkostki. Obiekty znajdujące się w poszczególnych podobszarach tworzą grupy obiektów. Promień hiperkul lub liczbę kostek ustala się w sposób arbitralny. Metody obszarowe mogą być zarówno metodami hierarchicznymi jak i metodami niechierarchicznymi.

Wyniki grupowania w niektórych z metod obszarowych zależą od wyjściowego grupowania obiektów, co niewątpliwie stanowi ich wadę.

Promień hiperkul najczęściej wyznacza się w oparciu o jedną z następujących formuł:

(3.28)

lub

, i,i'=1,2,...,n, (3.29)

przy czym:

0x01 graphic
,

, i,i'≠1,2,...,n, (3.30)

gdzie:

c - parametr, którego wartość jest ustalana metodą empirycznych poszukiwań.

W opracowaniu przedstawiamy wybrane metody obszarowe.

3.6.1. Metoda wrocławska

Metoda wrocławska, zwana także taksonomią hiperkul, została zaproponowana przez zespół statystyków z Wrocławia (Bukietyński i in., 1969). W metodzie wykorzystujemy elementy macierzy odległości między obiektami. Punktem wyjścia metody jest ustalenie promienia hiperkul d_o. Następnie tworzone są hiperkule o ustalonym promieniu, których środkami są poszczególne grupowane obiekty (współrzędne środka danej hiperkuli stanowią współrzędne tworzącego ją obiektu). Następnie dla każdej z hiperkul oblicza się liczbę należących do niej obiektów. Obiekty należące do najliczniejszej hiperkuli tworzą grupę obiektów i wyłączane są z dalszej procedury grupowania. Gdy wystąpi więcej niż jedna hiperkula o maksymalnej liczbie obiektów, to pierwszą wyodrębnioną grupę obiektów tworzą obiekty należące do hiperkuli, której środek leży najbliżej początku układu współrzędnych. Procedurę powtarzamy w stosunku do obiektów nie należących do już wyodrębnionych grup obiektów aż do momentu gdy uzyskamy rozłączne i wyczerpujące grupy obiektów (każdy z grupowanych obiektów znajduje się w jednej z grup).

Przykład 3.12

Do podziału województw Polski na grupy województw podobnych ze względu na osiągnięty poziom życia w 2005 r. zastosowano metodę wrocławską, należącą do grupy metod obszarowych.

Na wstępie, w oparciu o macierz odległości między województwami (2.1), obliczono promień hiperkul na podstawie formuły (3.30). Promień ten wyniósł 3,4303. Następnie tworzone są hiperkule o powyższym promieniu, których środkami są kolejne województwa oraz identyfikowane należące do nich województwa. Województwa klasyfikowane do kolejnych hiperkul odpowiadają wyróżnionym odległościom w kolejnych wierszach macierzy odległości (tab. 3.9).

Tab. 3.9. Skład hiperkul w pierwszym kroku procedury.

	O₁	O₂	O₃	O₄	O₅	O₆	O₇	O₈	O₉	O₁₀	O₁₁	O₁₂	O₁₃	O₁₄	O₁₅	O₁₆
O₁	0.000	2.518	3.959	2.435	2.873	3.018	2.974	3.274	4.183	3.251	3.281	3.673	4.186	3.048	3.110	1.514
O₂	2.518	0.000	3.316	2.564	3.700	2.981	3.637	4.197	4.047	2.712	2.863	3.913	2.855	1.677	2.796	2.387
O₃	3.959	3.316	0.000	4.650	4.061	4.130	4.714	5.194	3.658	4.102	4.022	4.370	2.273	3.475	4.783	3.940
O₄	2.435	2.564	4.650	0.000	3.687	3.996	4.512	3.512	5.021	3.124	3.796	5.348	4.291	2.006	4.018	2.342
O₅	2.873	3.700	4.061	3.687	0.000	3.926	3.555	3.968	5.573	4.479	3.979	3.430	3.835	3.879	4.177	3.389
O₆	3.018	2.981	4.130	3.996	3.926	0.000	2.347	2.957	3.188	2.257	2.202	4.060	3.187	3.506	2.278	3.480
O₇	2.974	3.637	4.714	4.512	3.555	2.347	0.000	3.704	4.900	4.067	2.383	4.037	4.155	4.393	3.094	3.203
O₈	3.274	4.197	5.194	3.512	3.968	2.957	3.704	0.000	4.827	2.538	4.052	5.549	4.458	4.239	3.337	4.108
O₉	4.183	4.047	3.658	5.021	5.573	3.188	4.900	4.827	0.000	3.309	3.975	5.129	3.971	4.106	4.520	4.418
O₁₀	3.251	2.712	4.102	3.124	4.479	2.257	4.067	2.538	3.309	0.000	3.463	5.019	3.218	2.880	2.546	3.790
O₁₁	3.281	2.863	4.022	3.796	3.979	2.202	2.383	4.052	3.975	3.463	0.000	4.853	3.087	2.886	3.769	2.728
O₁₂	3.673	3.913	4.370	5.348	3.430	4.060	4.037	5.549	5.129	5.019	4.853	0.000	4.591	5.033	3.621	4.461
O₁₃	4.186	2.855	2.273	4.291	3.835	3.187	4.155	4.458	3.971	3.218	3.087	4.591	0.000	2.859	3.993	4.141
O₁₄	3.048	1.677	3.475	2.006	3.879	3.506	4.393	4.239	4.106	2.880	2.886	5.033	2.859	0.000	4.019	2.512
O₁₅	3.110	2.796	4.783	4.018	4.177	2.278	3.094	3.337	4.520	2.546	3.769	3.621	3.993	4.019	0.000	3.972
O₁₆	1.514	2.387	3.940	2.342	3.389	3.480	3.203	4.108	4.418	3.790	2.728	4.461	4.141	2.512	3.972	0.000

Najliczniejszą hiperkulę stanowi hiperkula, której środkiem jest województwo O₁. Należy do niej 12 następujących województw, tworząc pierwszą grupę województw o podobnym poziomie życia w 2005 r.:

W następnym kroku identyfikujemy województwa należące do hiperkul, których środkami są województwa należące do kolejnych hiperkul, odpowiadającym wyróżnionym odległościom w wierszach macierzy odległości (tab. 3.10).

Tab. 3.10. Skład hiperkul w drugim kroku procedury.

	O₁	O₂	O₃	O₄	O₅	O₆	O₇	O₈	O₉	O₁₀	O₁₁	O₁₂	O₁₃	O₁₄	O₁₅	O₁₆
O₁	0.000	2.518	3.959	2.435	2.873	3.018	2.974	3.274	4.183	3.251	3.281	3.673	4.186	3.048	3.110	1.514
O₂	2.518	0.000	3.316	2.564	3.700	2.981	3.637	4.197	4.047	2.712	2.863	3.913	2.855	1.677	2.796	2.387
O₃	3.959	3.316	0.000	4.650	4.061	4.130	4.714	5.194	3.658	4.102	4.022	4.370	2.273	3.475	4.783	3.940
O₄	2.435	2.564	4.650	0.000	3.687	3.996	4.512	3.512	5.021	3.124	3.796	5.348	4.291	2.006	4.018	2.342
O₅	2.873	3.700	4.061	3.687	0.000	3.926	3.555	3.968	5.573	4.479	3.979	3.430	3.835	3.879	4.177	3.389
O₆	3.018	2.981	4.130	3.996	3.926	0.000	2.347	2.957	3.188	2.257	2.202	4.060	3.187	3.506	2.278	3.480
O₇	2.974	3.637	4.714	4.512	3.555	2.347	0.000	3.704	4.900	4.067	2.383	4.037	4.155	4.393	3.094	3.203
O₈	3.274	4.197	5.194	3.512	3.968	2.957	3.704	0.000	4.827	2.538	4.052	5.549	4.458	4.239	3.337	4.108
O₉	4.183	4.047	3.658	5.021	5.573	3.188	4.900	4.827	0.000	3.309	3.975	5.129	3.971	4.106	4.520	4.418
O₁₀	3.251	2.712	4.102	3.124	4.479	2.257	4.067	2.538	3.309	0.000	3.463	5.019	3.218	2.880	2.546	3.790
O₁₁	3.281	2.863	4.022	3.796	3.979	2.202	2.383	4.052	3.975	3.463	0.000	4.853	3.087	2.886	3.769	2.728
O₁₂	3.673	3.913	4.370	5.348	3.430	4.060	4.037	5.549	5.129	5.019	4.853	0.000	4.591	5.033	3.621	4.461
O₁₃	4.186	2.855	2.273	4.291	3.835	3.187	4.155	4.458	3.971	3.218	3.087	4.591	0.000	2.859	3.993	4.141
O₁₄	3.048	1.677	3.475	2.006	3.879	3.506	4.393	4.239	4.106	2.880	2.886	5.033	2.859	0.000	4.019	2.512
O₁₅	3.110	2.796	4.783	4.018	4.177	2.278	3.094	3.337	4.520	2.546	3.769	3.621	3.993	4.019	0.000	3.972
O₁₆	1.514	2.387	3.940	2.342	3.389	3.480	3.203	4.108	4.418	3.790	2.728	4.461	4.141	2.512	3.972	0.000

Występują dwie hiperkule o maksymalnej liczbie województw, tzn. są to hiperkule, których środkami są województwa O₃ i O₁₃. Bliżej początku układu współrzędnych leży województwo O₁₃, (d(O_13,O₀)=2,55 wobec (d(O_3,O₀)=3,03, gdzie O₀oznacza punkt leżący w środku układu współrzędnych. Województwo to wraz z województwem O₃tworzą drugą grupę województw:

Dwa pozostałe województwa stanowią środki ciężkości jednoelementowych hiperkul (tab. 3.10), a tym samym tworzą jednoelementowe grupy województw:

3.6.2. Metoda katowicka

Metoda katowicka, zwana metodą hiperkostek, została opracowana przez zespół statystyków z Katowic (Kolonko i in., 1970). Metoda ta nie wymaga wyznaczania elementów macierzy odległości między obiektami. Jej podstawą jest macierz danych wejściowych.

Na wstępie zakres zmienności każdej ze zmiennych dzieli się na k z góry ustalonych, równych części (klas). Jest to tożsame z podziałem na części zakresu zmienności wartości zmiennych na każdej z półosi współrzędnych, wyznaczających przestrzeń klasyfikacji obiektów. Wielowymiarowa przestrzeń klasyfikacji dzielona jest w ten sposób na k^m hiperkostek, gdzie m jest liczbą zmiennych charakteryzujących obiekty, wyznaczających wymiar tej przestrzeni.

Każdy z obiektów otrzymuje swój numer identyfikacyjny składający się z m-elementowego ciągu liczb, którego j-ty element odpowiada numerowi klasy j-tej zmiennej (j-tej osi współrzędnych przestrzeni klasyfikacji). Poszczególne elementy ciągu liczb, stanowiących numer identyfikacyjny obiektów, przyjmują wartości z przedziału <1; k>.

W każdej z hiperkostek może znajdować się zero, jeden lub więcej niż jeden obiekt. Każdy obiekt otrzymuje numer identyfikacyjny hiperkostki, do której należy.

Grupowanie obiektów polega na szukaniu pojedynczych albo połączonych ze sobą hiperkostek otoczonych hiperkostkami pustymi (nie zawierającymi żadnych obiektów). W tym celu porównujemy ze sobą elementy składowe numerów identyfikacyjnych obiektów. Im więcej występuje różnic między numerami identyfikacyjnymi pary obiektów (różnych elementów w ich numerach identyfikacyjnych) tym podobieństwo tych obiektów jest mniejsze. Przyjmujemy, że dwa obiekty należą do tych samych lub sąsiednich kostek gdy ich numery identyfikacyjne są identyczne lub różnią się co najwyżej jednym elementem.

Ostateczny wynik grupowania obiektów zależy od liczby klas, na które dzielone są zakresy zmienności zmiennych oraz liczby jednostkowych różnic numerów identyfikacyjnych obiektów, która określa progowy stopień sąsiedztwa hiperkostek.

Przykład 3.13

Stosując metodę katowicką, należącą do grupy metod hiperkostek, przeprowadzono grupowanie województw Polski ze względu na osiągnięty poziom życia w 2005 r. Na wstępie zakres zmienności każdej ze zmiennych podzielono na 4 przedziały klasowe o równej długości przyporządkowując kolejnym przedziałom, kolejne numery porządkowe, (tab. 3.11). Tym samym dokonujemy podziału siedmiowymiarowej przestrzeni klasyfikacji na 4⁷=16 384 hiperkostek.

Następnie każdemu województwu przyporządkowano numer identyfikacyjny składający się z 7 elementowego ciągu liczb, którego kolejne elementy odpowiadają numerom przedziałów klasowych kolejnych zmiennych (tab. 3.12). Numery te wskazują jednocześnie, do której hiperkostki należy dane województwo.

Grupy województw, o podobnym poziomie życia, są tworzone z województw których numery identyfikacyjne są identyczne lub różnią się co najwyżej jednym elementem. Warunek ten prowadzi do utworzenia następujących grup województw:

G₁={O₁},

G₂={O₂, O₁₄},

G₃={O₃, O₁₁, O₁₃},

G₄={O₄, O₈},

G₅={O₅},

G₆={O₆, O₁₅},

G₇={O₇},

G₈={O₉, O₁₀},

G₉={O₁₂},

G₁₀={O₁₆}.

Tabl. 3.11. Numery identyfikacyjne województw ze względu na numery klas zmiennych.

Województwa	Numery identyfikacyjne województw
	X₁₁	X₁₅	X₃₅	X₅₁	X₆₄	X₇₁	X₈₃
Dolnośląskie	1	3	3	4	2	4	4
Kujawsko-pomorskie	1	2	1	1	1	4	4
Lubelskie	1	1	1	1	1	1	4
Lubuskie	4	4	1	4	1	4	4
Łódzkie	4	1	1	4	1	4	1
Małopolskie	4	4	4	1	4	1	1
Mazowieckie	4	1	4	4	4	4	1
Opolskie	4	4	4	4	1	4	4
Podkarpackie	1	4	4	1	1	1	4
Podlaskie	4	4	4	1	1	1	4
Pomorskie	4	1	1	1	4	1	4
Śląskie	1	1	4	1	4	4	1
Świętokrzyskie	4	1	1	1	1	1	4
Warmińsko-mazurskie	1	4	1	1	1	4	4
Wielkopolskie	4	4	4	1	4	4	1
Zachodniopomorskie	1	4	1	4	4	4	4

Tabl. 3.12. Granice przedziałów klasowych zmiennych.

Zmienne	Granice przedziałów klasowych zmiennych
	1	2	3	4
X₁₁	-1,55 - -0,66	-0,66 - 0,23	0,23 - 1,12	1,12 - 2,00
X₁₅	-2,15 - -1,27	-1,27 - -0,40	-0,40 - 0,47	0,47 - 1,35
X₃₅	-1,70 - -0,94	-0,94 - -0,18	-0,18 - 0,58	0,58 - 1,34
X₅₁	-1,65 - -0,81	-0,81 - 0,02	0,02 - 0,86	0,86 - 1,70
X₆₄	-1,13 - -0,23	-0,23 - 0,66	0,66 - 1,55	1,55 - 2,44
X₇₁	-2,66 - -1,72	-1,72 - -0,79	-0,79 - 0,15	0,15 - 1,08
X₈₃	-2,81 - -1,91	-1,91 - -1,00	-1,00 - -0,09	-0,09 - 0,82

3.7. Metody taksonomii struktur

Metody te wykorzystywane są do grupowania obiektów charakteryzowanych zbiorem zmiennych strukturalnych. Przykład takiej metody stanowi procedura eliminacji wektorów zaproponowana przez S. Chomotowskiego i A. Sokołowskiego (1978).

Zasadą grupowania obiektów w metodzie eliminacji wektorów jest dążenie do takiego grupowania aby w poszczególnych grupach znajdowały się obiekty o strukturach podobnych parami. Za parę obiektów podobnych uważa się obiekty, dla których miara odległości struktur (1.76) jest mniejsza od ustalonej wartości progowej d*.

Punktem wyjścia metody eliminacji wektorów jest przekształcenie macierzy odległości D w macierz binarną podobieństwa obiektów, przy przyjęciu wartości progowej odległości d*, o postaci:

, i,i'=1,2,...,n, (3.31)

przy czym:

0x01 graphic
, (3.32)

gdzie:

p_ii' - miara podobieństwa i-tego i i'-tego obiektu.

Następnie wyznaczamy wektor eliminacji p zdefiniowany jako:

, (3.33)

gdzie:

1 - wektor (n x 1) składający się z jedynek.

Maksymalna wartość w wektorze eliminacji wskazuje obiekt, który przy danej wartości progowej d* jest niepodobny do największej liczby pozostałych obiektów. Obiekt ten zostaje wyeliminowany ze zbioru obiektów. W sytuacji gdy więcej niż jedna składowa wektora eliminacji jest równa wartości maksymalnej należy zastosować dodatkowe kryterium eliminacji. Autorzy metody sugerują aby eliminować ostatecznie z obiektów o maksymalnych wartościach składowej wektora eliminacji, obiekt któremu odpowiada maksymalna wartość lub suma wartości w odpowiadających mu wierszu macierzy odległości.

Po eliminacji obiektu ze zbioru obiektów tworzymy zredukowaną macierz binarną P₁ wykreślając z macierzy P wiersz i kolumnę odpowiadające wyeliminowanemu obiektowi. Następnie wyznaczamy wektor eliminacji p₁. Procedurę kontynuujemy aż wszystkie składowe wektora eliminacji będą zerami. Obiekty, które nie zostały wyeliminowane tworzą pierwszą grupę obiektów. Przedstawioną procedurę powtarzamy do grupowania obiektów nie należących do już wyodrębnionej grupy obiektów, uzyskując kolejne grupy obiektów o podobnej strukturze.

Przykład 3.14

Metoda taksonomii struktur została wykorzystana do podziału województw Polski na grupy województw o podobnej strukturze ludności według wieku w 2005 r. Na podstawie danych z Rocznika Statystycznego Województw (GUS, 2006) ustalono strukturę ludności według wieku w tych województwach (tab. 3.13).

Tab. 3.13. Wartości zmiennych opisujących strukturę ludności w województwach Polski według wieku w 2005 r.

Województwo	Udział ludności w danym wieku w ludności ogółem w procentach
Województwo		0-2 (X₁)	3-6 (X₂)	7-12 (X₃)	13-15 (X₄)	16-18 (X₅)	19-24 (X₆)	25-34 (X₇)	35-44 (X₈)	45-54 (X₉)	55-64 (X₁₀)	Pow. 65 (X₁₁)
Dolnośląskie	2,56	3,50	6,29	3,81	4,21	10,45	15,65	12,19	17,07	10,79	13,47
Kujawsko-Pomorskie	2,90	4,00	7,16	4,31	4,55	10,51	15,28	12,74	15,74	10,49	12,32
Lubelskie	2,86	3,96	7,19	4,47	4,74	10,56	14,42	12,47	14,92	10,14	14,27
Lubuskie	2,87	3,89	7,02	4,24	4,66	10,84	15,54	12,40	16,61	10,27	11,67
Łódzkie	2,57	3,50	6,30	3,83	4,06	9,58	14,91	12,42	16,37	11,58	14,88
Małopolskie	2,95	4,21	7,29	4,37	4,58	10,50	15,62	13,09	14,31	9,71	13,36
Mazowieckie	2,82	3,81	6,53	3,85	4,09	9,69	15,90	12,50	15,76	10,50	14,55
Opolskie	2,37	3,54	6,53	4,13	4,60	10,26	15,08	14,17	15,59	10,06	13,65
Podkarpackie	2,91	4,27	7,72	4,82	5,09	10,60	15,14	13,10	14,24	9,21	12,91
Podlaskie	2,68	3,88	7,31	4,55	4,90	10,50	14,35	13,35	14,60	9,41	14,46
Pomorskie	3,12	4,20	7,14	4,30	4,58	10,40	15,81	12,77	15,54	10,22	11,92
Śląskie	2,55	3,48	6,18	3,84	4,31	10,06	15,28	13,35	16,51	11,17	13,25
Świętokrzyskie	2,63	3,72	6,93	4,28	4,54	10,05	14,41	12,33	15,77	10,48	14,86
Warmińsko-Mazurskie	3,03	4,16	7,48	4,61	4,94	11,11	14,83	13,04	15,86	9,38	11,56
Wielkopolskie	3,02	4,09	7,12	4,33	4,64	10,61	16,01	12,69	15,28	10,33	11,89
Zachodnio pomorskie	2,79	3,82	6,85	4,10	4,42	10,53	15,37	12,41	17,01	10,61	12,09

Następnie stosując miarę odległości struktur (1.76) zbudowano macierz odległości między województwami (tab. 3.14).

Tab. 3.14. Macierz odległości struktur między województwami.

	O₁	0.000	0.031	0.040	0.029	0.025	0.040	0.025	0.031	0.055	0.051	0.037	0.017	0.032	0.053	0.038	0.019
	O₂	0.031	0.000	0.024	0.016	0.043	0.022	0.029	0.028	0.029	0.035	0.010	0.030	0.026	0.023	0.011	0.015
	O₃	0.040	0.024	0.000	0.032	0.040	0.023	0.030	0.030	0.030	0.014	0.029	0.044	0.018	0.035	0.027	0.035
	O₄	0.029	0.016	0.032	0.000	0.045	0.033	0.036	0.038	0.041	0.046	0.016	0.034	0.034	0.025	0.016	0.012
	O₅	0.025	0.043	0.040	0.045	0.000	0.054	0.020	0.037	0.065	0.049	0.052	0.022	0.023	0.061	0.053	0.038
	O₆	0.040	0.022	0.023	0.033	0.054	0.000	0.037	0.030	0.016	0.022	0.021	0.039	0.037	0.030	0.022	0.036
	O₇	0.025	0.029	0.030	0.036	0.020	0.037	0.000	0.030	0.052	0.040	0.032	0.029	0.020	0.052	0.033	0.031
D =	O₈	0.031	0.028	0.030	0.038	0.037	0.030	0.030	0.000	0.040	0.032	0.032	0.024	0.028	0.042	0.036	0.035
	O₉	0.055	0.029	0.030	0.041	0.065	0.016	0.052	0.040	0.000	0.024	0.032	0.050	0.048	0.024	0.032	0.044
	O₁₀	0.051	0.035	0.014	0.046	0.049	0.022	0.040	0.032	0.024	0.000	0.040	0.046	0.027	0.032	0.039	0.048
	O₁₁	0.037	0.010	0.029	0.016	0.052	0.021	0.032	0.032	0.032	0.040	0.000	0.038	0.034	0.023	0.006	0.022
	O₁₂	0.017	0.030	0.044	0.034	0.022	0.039	0.029	0.024	0.050	0.046	0.038	0.000	0.033	0.049	0.041	0.027
	O₁₃	0.032	0.026	0.018	0.034	0.023	0.037	0.020	0.028	0.048	0.027	0.034	0.033	0.000	0.044	0.036	0.032
	O₁₄	0.053	0.023	0.035	0.025	0.061	0.030	0.052	0.042	0.024	0.032	0.023	0.049	0.044	0.000	0.025	0.034
	O₁₅	0.038	0.011	0.027	0.016	0.053	0.022	0.033	0.036	0.032	0.039	0.006	0.041	0.036	0.025	0.000	0.022
	O₁₆	0.019	0.015	0.035	0.012	0.038	0.036	0.031	0.035	0.044	0.048	0.022	0.027	0.032	0.034	0.022	0.000

W kolejnym kroku wyznaczono wartość krytyczną odległości między województwami w oparciu o formułę:
; i,i'=1,2,...,n.

Wartość krytyczna odległości wyniosła d*=0,0416.

Macierz odległości (3.14) przekształcono w macierz binarną podobieństwa województw P (tabl. 3.15), stosując formułę transformacji o postaci (3.33).

Tab. 3.15. Binarna macierz podobieństwa województw.

	O₁	0	0	0	0	0	0	0	1	1	0	0	0	1	0	0
	O₂	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
	O₃	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
	O₄	0	0	0	0	1	0	0	0	1	0	0	0	0	0	0
	O₅	0	1	0	1	0	1	0	1	1	1	0	0	1	1	0
	O₆	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
	O₇	0	0	0	0	0	0	0	1	0	0	0	0	1	0	0
P =	O₈	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
	O₉	1	0	0	0	1	0	1	0	0	0	1	1	0	0	1
	O₁₀	1	0	0	1	1	0	0	0	0	0	1	0	0	0	1
	O₁₁	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
	O₁₂	0	0	1	0	0	0	0	1	1	0	0	0	1	0	0
	O₁₃	0	0	0	0	0	0	0	1	0	0	0	0	1	0	0
	O₁₄	1	0	0	0	1	0	1	0	0	0	1	1	0	0	0
	O₁₅	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
	O₁₆	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0

Otrzymana macierz binarna stanowi punkt wyjścia do grupowania województw. Na podstawie tej macierzy konstruujemy wektor eliminacji, którego elementami są sumy wartości kolejnych wierszy macierzy binarnej:

[3, 1, 1, 2, 8, 1, 2, 0, 6, 5, 1, 4, 2, 5, 1, 2].

W pierwszym kroku procedury w macierzy P eliminujemy wiersz i kolumnę nr 5, które wskazuje element o maksymalnej wartości w wektorze eliminacji p₀, uzyskując macierz zredukowaną P:

Tab. 3.16. Zredukowana macierz binarna odległości między województwami.

	O₁	0	0	0	0	1	1	0	0	1	0
	O₂	0	0	0	0	0	0	0	0	0	0
	O₃	0	0	0	0	0	0	1	0	0	0
	O₄	0	0	0	0	0	1	0	0	0	0
	O₆	0	0	0	0	0	0	0	0	0	0
	O₇	0	0	0	0	1	0	0	0	1	0
P₁=	O₈	0	0	0	0	0	0	0	0	0	0
	O₉	1	0	0	1	0	0	1	1	0	1
	O₁₀	1	0	1	0	0	0	1	0	0	1
	O₁₁	0	0	0	0	0	0	0	0	0	0
	O₁₂	0	1	0	0	1	1	0	0	1	0
	O₁₃	0	0	0	0	1	0	0	0	1	0
	O₁₄	1	0	0	1	0	0	1	1	0	0
	O₁₅	0	0	0	0	0	0	0	0	0	0
	O₁₆	0	0	0	0	1	1	0	0	0	0

Następnie w oparciu o macierz P₁ konstruujemy wektor eliminacji p₁:

[3, 0, 1, 1, 0, 2, 0, 5, 4, 0, 4, 2, 4, 0, 2].

Sprawdzamy, czy wszystkie elementy składowe wektora eliminacji są zerami. Ponieważ warunek ten nie jest spełniony, wyznaczamy element wektora eliminacji o maksymalnej wartości i przystępujemy do kolejnego kroku procedury. Powtarzamy powyższą procedurę, aż do momentu gdy wszystkie składowe wektora eliminacji są zerami. Uzyskiwane w kolejnych krokach wektory eliminacji mają następującą postać:

Krok 2:

[2, 0, 1, 1, 0, 1, 0, 4, 0, 3, 1, 4, 0, 1]

W wektorze eliminacji występują dwie wartości maksymalne, ostatecznie eliminujemy z macierzy P₂ wiersz i kolumnę odpowiadającą województwu O₉. Województwu temu odpowiada większa maksymalna wartość w macierzy odległości (3.14) niż województwu O₁₄.

Krok 3:

[1, 0, 1, 0, 0, 1, 0, 0, 2, 1, 4, 0, 0]

Krok 4:

[0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]

W kroku tym otrzymaliśmy wektor eliminacji, w którym występują dwie wartości maksymalne. Ostatecznie eliminujemy z macierzy P₄ wiersz i kolumnę odpowiadające województwu O₁₂. Województwu temu odpowiada większa maksymalna wartość w macierzy odległości (3.14) niż województwu O₃.

Krok 5:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Wszystkie składowe wektora p₅ są zerami. Województwa, które nie zostały wyeliminowane tworzą pierwszą grupę województw:

G₁ = {O₁, O₂, O₃, O₄, O₆, O₇, O₈, O₁₁, O_13, O_15, O₁₆}

W oparciu o postać wyjściową macierzy binarnej P, w szóstym kroku procedury, budujemy macierz P₆, eliminując w macierzy wyjściowej wiersze i kolumny odpowiadające województwom należącym do pierwszej grupy obiektów (tab. 3.16).

Tab. 3.16. Binarna macierz podobieństwa województw nie należących do grupy G₁.

0x01 graphic

Następnie (w kroku 6) konstruujemy wektor eliminacji:

[3, 2, 2, 3, 2]

W wektorze eliminacji występują dwie maksymalne wartości. Z macierzy P₆ eliminujemy wiersz i kolumnę odpowiadające województwu O₅. Województwu temu odpowiada większa maksymalna wartość w zredukowanej macierzy odległości (wyjściowej macierzy odległości po eliminacji wektorów i wierszy opowiadających województwom należącym do grupy G₁).

Powtarzamy powyższą procedurę do momentu gdy wszystkie składowe wektora eliminacji są zerami. W kolejnych krokach otrzymujemy następujące wektory eliminacji:

Krok 7:

[1, 1, 3, 1]

Krok 8:

[0, 0, 0]

Wszystkie składowe wektora p₈ są zerami. Województwa, które nie zostały wyeliminowane tworzą drugą grupę województw:

G₁ = {O_9, O_12, O₁₄}

Na podstawie wyjściowej macierzy liniowej P w dziewiątym kroku procedury budujemy macierz P₉, eliminując z macierzy wyjściowej wiersze i kolumny odpowiadające województwom należącym do grup G₁i G₂ (tab. 3.17).

Tab. 3.17. Binarna macierz podobieństwa województw nie należących do grup G₁i G₂.

0x01 graphic

Następnie konstruujemy wektor eliminacji:

0x01 graphic

Bez względu na to, który wiersz i kolumnę wyeliminujemy z macierzy P₉otrzymamy dwie jednoelementowe grupy województw:

G₃ = {O₅},

G₄ = {O₁₀},

co kończy procedurę grupowania województw.

3.8. Mierniki oceny poprawności grupowania obiektów

Metody grupowania zmierzają do takiej klasyfikacji obiektów w grupy, aby obiekty należące do tej samej grupy były jak najbardziej do siebie podobne (jak najwyższa homogeniczność grup obiektów), a należące do różnych grup były do siebie jak najbardziej niepodobne (heterogeniczne). Ze względu na różne założenia przyjmowane w tych metodach wyniki grupowań często się różnią, a tym samym pożądana jest ocena poprawności grupowania obiektów uzyskiwanych za pomocą różnych metod. Ocena poprawności stosowanych metod grupowania polega na sprawdzeniu czy spełniają one określone kryteria. Stworzenie listy takich kryteriów stanowi podstawowy problem w analizie jakości metod grupowania. W opracowaniu skoncentrujemy się na miernikach poprawności grupowania, opierając się na miarach homogeniczności oraz heterogeniczności grup obiektów.

3.8.1. Miary homogeniczności grup obiektów

Miary homogeniczności grup obiektów określają stopień ich jednorodności. Im mniejsza wartość tych miar tym większa jednorodność grup obiektów, tzn. tym większe podobieństwo obiektów w danej grupie ze względu na charakteryzujące je zmienne.

Miary homogeniczności (jednorodności) zróżnicowania wewnątrzgrupowego grup obiektów można podzielić na mierniki cząstkowe oraz mierniki sumaryczne. Mierniki cząstkowe charakteryzują podobieństwo obiektów wewnątrz pojedynczych grup. Mierniki cząstkowe najczęściej bazują na pomiarze średnich odległości między obiektami w danej grupie, wzajemnych odległości między obiektami w grupie lub pomiarze odległości obiektów od środka ciężkości grupy. Mierniki te przyjmują przy tym postać średniej arytmetycznej, maksymalnej odległości lub mediany (Grabiński i in., 1989, s. 150-151; Młodak, 2006, s. 78-79).

Formuły mierników cząstkowych, opierających się na pomiarze średnich odległości między obiektami w grupie, przyjmują odpowiednio postać:

dla średniej arytmetycznej:

0x01 graphic
, r=1,2,...,z, (3.34)

dla maksymalnej odległości:

i,i'=1,2,...,n_r; r=1,2,...,z, (3.35)

dla mediany:

, i,i'=1,2,...,n_r; r=1,2,...,z. (3.36)

Mierniki cząstkowe bazujące na pomiarze odległości obiektów od środka ciężkości grupy można przedstawić na pomocą następujących formuł:

dla średniej arytmetycznej:

0x01 graphic
, r=1,2,...,z, (3.37)

dla maksymalnej odległości:

i=1,2,...,n_r; r=1,2,...,z, (3.38)

dla mediany:

, i=1,2,...,n_r; r=1,2,...,z. (3.39)

Wzory mierników cząstkowych bazujących na wzajemnych odległościach między obiektami w grupie można przedstawić następująco:

dla średniej arytmetycznej:

0x01 graphic
, i,i'=1,2,...,n_r; r=1,2,...,z, (3.40)

dla maksymalnej odległości:

i,i'=1,2,...,n_r; r=1,2,...,z, (3.41)

dla mediany:

, i,i'=1,2,...,n_r; r=1,2,...,z. (3.42)

Im mniejsze wartości mierników cząstkowych tym większa jednorodność charakteryzująca obiekty w danej grupie.

Mierniki sumaryczne podobieństwa są funkcjami mierników cząstkowych. Stanowią one oceny poprawności grupowania obiektów, ze względu na jednorodność grup obiektów, dla wszystkich grup łącznie. Analogicznie jak w przypadku mierników cząstkowych bazują one na pomiarze średnich odległości obiektów w grupie, odległości pomiędzy obiektami wewnątrz poszczególnych grup lub pomiarze odległości obiektów od środków ciężkości grup, w których te obiekty się znajdują. Formuły mierników sumarycznych, podobnie jak mierników cząstkowych, przyjmują odpowiednio postać średniej arytmetycznej, maksymalnej odległości lub mediany.

Sumaryczne mierniki, oparte na pomiarze średnich odległości między obiektami wewnątrz grup obiektów, są dane wzorami:

dla średniej arytmetycznej:

, (3.43)

gdzie d_r obliczane są w oparciu o formułę (3.34),

dla maksymalnej odległości:

, r=1,2,...,z, (3.44)

gdzie d_r obliczane są w oparciu o formułę (3.35),

dla mediany:

, r=1,2,...,z, (3.45)

gdzie d_r obliczane są w oparciu o formułę (3.36).

Formuły mierników sumarycznych, bazujące na pomiarze odległości obiektów od innych obiektów tej samej grupy, można zapisać następująco:

dla średniej arytmetycznej:

0x01 graphic
, (3.46)

gdzie d_i^r obliczane są w oparciu o formułę (3.40),

dla maksymalnej odległości:

, r=1,2,...,z, (3.47)

gdzie d_i^r obliczane są w oparciu o formułę (3.41),

dla mediany:

, r=1,2,...,z, (3.48)

gdzie d_i^r obliczane są w oparciu o formułę (3.42).

Ostatnia grupa mierników sumarycznych, bazująca na pomiarze odległości obiektów od środków ciężkości grup, obliczana jest w oparciu o następujące formuły:

dla średniej arytmetycznej:

, (3.49)

gdzie d_r obliczane są w oparciu o formułę (3.37),

dla maksymalnej odległości:

, r=1,2,...,z, (3.50)

gdzie d_r obliczane są w oparciu o formułę (3.38),

dla mediany:

, r=1,2,...,z, (3.51)

gdzie d_r obliczane są w oparciu o formułę (3.39).

3.8.2. Miary heterogeniczności grup obiektów

Miary heterogeniczności określają poziom odrębności utworzonych grup obiektów. Im wyższa ich wartość tym większa odrębność utworzonych grup obiektów. Podobnie jak w przypadku miar homogeniczności wyróżniamy wśród nich mierniki cząstkowe oraz mierniki sumaryczne. Mierniki cząstkowe charakteryzują stopień niepodobieństwa danej grupy obiektów od innych grup obiektów. Najczęściej opierają się na pomiarze odległości obiektów z danej grupy obiektów od obiektów spoza tej grupy lub odległości między środkiem ciężkości danej grupy od środków ciężkości pozostałych grup. Mierniki te przyjmują postać średniej arytmetycznej, minimalnej odległości lub mediany.

Formuły mierników cząstkowych opierające się na pomiarze odległości danej grupy obiektów od obiektów nienależących do tej grupy przyjmują odpowiednio postać:

dla średniej arytmetycznej:

0x01 graphic
, r=1,2,...,z, (3.52)

dla minimalnej odległości:

, i=1,2,...,n_r; i'=1,2,...,n_r'; r=1,2,...,z, (3.53)

dla mediany:

, i=1,2,...,n_r; i'=1,2,...,n_r'; r=1,2,...,z. (3.54)

Mierniki cząstkowe bazujące na pomiarze odległości między środkami ciężkości danej grupy od środków ciężkości pozostałych grup można opisać za pomocą następujących formuł:

dla średniej arytmetycznej:

0x01 graphic
, r=1,2,...,z, (3.55)

dla minimalnej odległości:

, r,r'=1,2,...,z; r≠r', (3.56)

dla mediany:

, r,r'=1,2,...,z; r≠r'. (3.57)

Mierniki sumaryczne niepodobieństwa grup obiektów są funkcjami mierników cząstkowych. Stanowią one miary poprawności grupowania obiektów, ze względu na odrębność grup obiektów, dla wszystkich grup obiektów łącznie. Mogą one bazować, analogicznie jak mierniki cząstkowe, na pomiarze odległości obiektów z danej grupy obiektów od obiektów spoza tej grupy lub odległości między środkami ciężkości tych grup. Formuły mierników sumarycznych przyjmują odpowiednio postać średniej arytmetycznej, minimalnej odległości lub mediany.

Sumaryczne mierniki niepodobieństwa grup obiektów, oparte na pomiarze odległości obiektów danej grupy od obiektów spoza tej grupy, są opisane za pomocą formuł:

dla średniej arytmetycznej:

, r=1,2,...,z, (3.58)

gdzie d_r obliczane są w oparciu o formułę (3.52),

dla minimalnej odległości:

, r=1,2,...,z, (3.59)

gdzie d_r obliczane są w oparciu o formułę (3.53),

dla mediany:

, r=1,2,...,z, (3.60)

gdzie d_r obliczane są w oparciu o formułę (3.54).

Wzory na mierniki sumaryczne, bazujące na pomiarze odległości pomiędzy środkami ciężkości grup obiektów możemy przedstawić następująco:

dla średniej arytmetycznej:

, r=1,2,...,z, (3.61)

gdzie d_r obliczane są w oparciu o formułę (3.55),

dla minimalnej odległości:

, r=1,2,...,z, (3.62)

gdzie d_r obliczane są w oparciu o formułę (3.56),

dla mediany:

, r=1,2,...,z, (3.63)

gdzie d_r obliczane jest na podstawie wzoru (3.57).

3.8.3. Mierniki poprawności grupowania

Mierniki poprawności grupowania definiowane są jako iloraz dowolnego miernika homegeniczności grup obiektów oraz dowolnego miernika heterogeniczności grup obiektów. Jednakże pożądane jest aby licznik i mianownik miernika stanowiły mierniki konstruowane na tych samych zasadach, co zapewni spójność pomiaru. W mianowniku mierników poprawności grup obiektów mogą występować zamiast mierników heterogeniczności także inne miary, a mianowicie (Grabiński i in., 1989, s. 154-155):

średnia taksonomiczna zbioru badanych obiektów:

, i,i'=1,2,...,n_, (3.64)

średnia arytmetyczna ze wszystkich mierników odległości:

0x01 graphic
. (3.65)

Im mierniki poprawności grupowania obiektów przyjmują mniejsze wartości, tym większa poprawność grupowania obiektów.

Obiekty traktujemy tutaj w sposób węższy jako obiekty przestrzenne. W ujęciu szerszym mogą to być obiekty dowolnej natury.

Por. także rys. 3.3, na którym przedstawiono schemat przebiegu deglomeracji.

Analizą empiryczną rozkładów błędów grupowania zajmowali się L. Engelman i J. W. Hartigan (1969).

Por. rozdz. 1.6.2.

Kierunki badań nad jakością metod grupowania zostały przedstawione np. w pracy Grabiński i in. (1989, s. 138 i dalsze).

111

0x01 graphic

Wyszukiwarka

Podobne podstrony:
RK T1, III semestr bezpieczeństwo narodowe, system reagowania kryzysowego
3 tydzień Wielkanocy, III piątek
Jezus III
TBL WYKŁAD III Freud
RK mgr W1sn
plsql III
Zaj III Karta statystyczna NOT st
TT Sem III 14 03
Metamorfizm Plutonizm III (migmatyty)
Cz III Ubezpieczenia osobowe i majątkowe
III WWL DIAGN LAB CHORÓB NEREK i DRÓG MOCZ
download Finanse międzynarodowe FINANSE MIĘDZYNARODOWE WSZiM ROK III SPEC ZF
w 13 III rok VI sem
wykład III Ubezpieczenia na życie2011
III BB
wykład III pns psychopatologia

więcej podobnych podstron