METODY GRUPOWANIA OBIEKTÓW

Cele grupowania:

utworzenie jak najbardziej jednorodnych grup obiektów (skupień) ze względu na podobieństwo w zakresie wewnętrznej struktury charakteryzujących je zmiennych.

Kryteria grupowania:

• 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.

Warunki grupowania:

zbiór obiektów O={O₁,O₂,...,O_n} dzielimy na podzbiory (grupy obiektów)
spełniają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

• metody grupowania obiektów uporządkowanych liniowo

• metody aglomeracyjne

• metody podziału dendrytu

• metody podziału dendrogramu

• metody deglomeracyjne

• metody optymalizacji danego grupowania

• metody obszarowe

• metody taksonomii struktur

METODY GRUPOWANIA OBIEKTÓW

UPORZĄDKOWANYCH LINIOWO

METODY DIAGRAMOWE

METODA PODOLEC

Założenia:

• 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, poza powiązaniami bliskimi, należy traktować jako dalekie

Wskaźnik poprawności grupowania:

, (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.

METODA SPÄTHA-SZCZOTKI

Funkcje dobroci grupowania:

• Dążymy do otrzymania grup obiektów o zbliżonych liczebnościach:

, (3.5)

gdzie:

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

• Funkcja kryterium dobroci grupowania minimalizuje sumę średnich odległości w grupach:

. (3.6)

• Funkcji kryterium dobroci grupowania minimalizuje zróżnicowanie obiektów wewnątrz grup, ze względu na charakteryzujące je zmienne:

, (3.7)

gdzie:

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

Rozwiązanie quasi-optymalne

• w punkcie wyjścia 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ę

• wskazujemy iterację, w której następuje przerwanie tworzenia kolejnych, coraz bardziej licznych i jednocześnie coraz mniej jednorodnych grup województw

• 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).

METODA MAKSYMALNEGO GRADIENTU

• 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 miary (3.10)

METODA ODCHYLEŃ STANDARDOWYCH

• 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.

METODY AGLOMERACYJNE

METODY PODZIAŁU DENDRYTU

Ogólna charakterystyka:

• 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

NATURALNY PODZIAŁ DENDRYTU

• porządkujemy nierosnąco wiązadła dendrytu:

,

gdzie:

d₁,d₂,...,d_k - uporządkowane odległości wiązadeł.

• 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).

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)

METODA HELLWIGA

• usuwamy z dendrytu krawędzie, 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:

,

.

METODY PODZIAŁU DENDROGRAMU

Ogólna charakterystyka metod

• 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ę

METODY WYZNACZANIA

KRYTYCZNEJ WARTOŚCI ODLEGŁOŚCI

Analiza 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 odległości między węzłami wskazuje, że łączymy ze sobą grupy obiektów relatywnie mało podobnych

• 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.

Analiza wykresu przebiegu porządkowania nieliniowego

obiektów w postaci drzewka

• na wykresie przebiegu porządkowania obiektów 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ści ta powinna być uznana za odległość krytyczną, wyznaczającą miejsce „cięcia” gałęzi drzewka

Analiza dendrogramu pod względem stosunku odległości

między kolejnymi etapami grupowania

• wzór na krytyczną wartość odległości:

, h=2,..,n. (3.20)

Reguła Mojeny

• wzór na krytyczną wartość odległości:

, (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>.

METODY OPTYMALIZACJI

DANEGO GRUPOWANIA OBIEKTÓW

Ogólna charakterystyka

• punktem wyjścia metod optymalizacyjnych jest ustalenie pożądanej liczby grup obiektów, które chcemy utworzyć

• ustalamy wstępny skład poszczególnych grup:

• 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

• następnie poprawiamy dobroć wstępnego grupowania obiektów poprzez optymalizację grupowania polegającą na przesuwaniu obiektów między grupami

METODA k-ŚREDNICH

• 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

• ocenę zróżnicowania wewnątrzgrupowego stanowi 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

• 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

METODA FORGY-JANCEY'A

• na wstępie ustalamy liczbę grup obiektów, którą chcemy uzyskać, dokonując 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 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 nowej 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

METODY OBSZAROWE

Ogólna charakterystyka

• w metodach obszarowych przestrzeń wielowymiarową, w której znajdują się punkty reprezentujące obiekty, dzieli się na rozłączne podobszary

• 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

METODA KATOWICKA

• na wstępie zakres zmienności każdej ze zmiennych dzieli się na k z góry ustalonych, równych części (klas), co 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

• 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)

• 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 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

METODY TAKSONOMII STRUKTUR

METODA ELIMINACJI WEKTORÓW

• przekształcamy 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:

, (3.32)

gdzie:

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

• wyznaczamy wektor eliminacji p_o 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 (eliminujemy 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 wyeliminowaniu 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 wyodrębnionej grupy obiektów, uzyskując kolejne grupy obiektów o podobnej strukturze zmiennych

---