Ekonometria przestrzenna wykład 4 PDF

Ekonometria przestrzenna wykład 4 Klasyfikacja obiektów na podstawie metod hierarchicznych M. Chrzanowska Ekonometria przestrzenna 1 Metody hierarchiczne należą do najczęściej stosowanych metod klasyfikacji obiektów społeczno- gosp...

Ekonometria przestrzenna wykład 4 Klasyfikacja obiektów na podstawie metod hierarchicznych M. Chrzanowska Ekonometria przestrzenna 1 Metody hierarchiczne należą do najczęściej stosowanych metod klasyfikacji obiektów społeczno- gospodarczych. Zastosowanie metod hierarchicznych umożliwia podział zbioru obiektów na grupy i przedstawienie ich pełnej hierarchii. W hierarchii tej można wyszczególnić grupy nadrzędne, których elementami są inne grupy niższego rzędu. Ekonometria przestrzenna 2 Podział metod hierarchicznych Istnieje wiele metod grupowania obiektów społeczno-gospodarczych na podstawie metod hierarchicznych, które ze względu na sposób grupowania dzielą się na: – metody aglomeracyjne (indukcyjne) – metody podziałowe (dedukcyjne) Ekonometria przestrzenna 3 Metody aglomeracyjne (indukcyjne)  procedura grupowania opiera się na założeniu, że każdy analizowany obiekt jest jednoelementowym skupiskiem. W każdym kolejnym kroku obiekty te łączone są w skupiska wyższego rzędu. Efektem końcowym procedury grupowania przy wykorzystaniu metod aglomeracyjnych jest jedna grupa obiektów zawierająca wszystkie elementy zbioru, Ekonometria przestrzenna 4 Metody podziałowe (dedukcyjne) procedura grupowania jest odwrotnością procedury aglomeracyjnej. Opiera się na założeniu, że zbiór wszystkich elementów tworzą jedno skupisko. Z każdym kolejnym krokiem skupisko to jest dzielone na coraz mniejsze grupy. Efektem końcowym procedury grupowania przy wykorzystaniu metod podziałowych jest zbiór skupisk jednoelementowych Ekonometria przestrzenna 5 Metody aglomeracyjne (indukcyjne) Schemat grupowania dla wszystkich metod aglomeracyjnych opiera się na jednym algorytmie postępowania. Algorytm ten nazywa się centralną procedurą aglomeracyjną. Rozpoczyna się on od budowy macierzy D zawierającej odległości euklidesowe pomiędzy wszystkimi obiektami. Macierz ta opisana jest zgodnie z wzorem Ekonometria przestrzenna 6 Centralna procedura aglomeracyjna  d11 d12... d1n  d d 22 ... d 2 n  D  [d ij ]   21 i  1, 2,..., n j  1, 2,..., m ............    d m1 d m 2... d mn  gdzie dij odległość euklidesowa określona wzorem:  z  z jk  p d ij  2 ik k 1 Ekonometria przestrzenna 7 Centralna procedura aglomeracyjna Następnie w macierzy D wyszukuje się minimalną odległość d pq  min i, j d ij  pomiędzy obiektami, które tworzą jednoelementowe grupy – A p i Aq. Grupy dla których odległość jest najmniejsza wiążą się w jedną (dwuelementową) grupę: Ar Ar  Ap  Aq Ekonometria przestrzenna 8 Centralna procedura aglomeracyjna W kolejnym kroku oblicza się odległości wszystkich grup od utworzonej grupy. Odległość tę wyznacza się zgodnie z przyjętą metodą aglomeracyjną. Tak obliczoną odległość umieszcza się w macierzy D w p-tym wierszu i p-tej kolumnie oraz usuwa jednocześnie q-ty wiersz i q-tą kolumnę. Ekonometria przestrzenna 9 Centralna procedura aglomeracyjna Powyższy algorytm powtarza się aż do momentu utworzenia jednej grupy zawierającej wszystkie obiekty zbioru. Każda iteracja centralnej procedury aglomeracyjnej prowadzi do powstawania coraz mniejszej liczby grup. Macierz odległości D po każdej iteracji jest aktualizowana, co umożliwia określenie jakości podziału. Ekonometria przestrzenna 10 Centralna procedura aglomeracyjna Obliczanie odległości nowoutworzonej grupy od pozostałych grup (w każdej iteracji) jest istotnym etapem centralnej procedury aglomeracyjnej Zgodnie z tą procedurą odległość pomiędzy nowoutworzoną a pozostałymi grupami wyznaczana jest według następującego wzoru: d ir  a p d ip  aq d iq  bd pq  c d ip  d iq 11 Odległość pomiędzy nowoutworzoną grupą a pozostałymi grupami d ir  a p d ip  aq d iq  bd pq  c d ip  d iq gdzie: d iq - odległość pomiędzy grupami Ai i Aq, d ip - odległość pomiędzy grupami Ai i A p, d pq - odległość pomiędzy grupami A p i Aq a p , aq , b, c - parametry charakteryzujące procedurę aglomeracyjną d ir - odległość pomiędzy grupami Ai i Ar , Ekonometria przestrzenna 12 UWAGA Wartości parametrów a p , aq , b, c stanowią główną różnicę pomiędzy poszczególnymi metodami aglomeracyjnymi. Ekonometria przestrzenna 13 Metody hierarchiczne Wśród najczęściej stosowanych wyróżniamy następujące metody (uszeregowane na podstawie malejącej efektywności) – metoda Warda; – metoda najdalszego sąsiedztwa; – metoda średniej grupowej ; – metoda mediany; – metoda środka ciężkości; – metoda najbliższego sąsiedztwa 14  metoda najbliższego sąsiedztwa metoda najdalszego sąsiedztwa metoda mediany metoda średniej grupowej metoda środka ciężkości metoda Warda Metoda Warda jest najefektywniejszą metodą aglomeracyjną. Jej istotnym czynnikiem jest zmienność wewnątrzgrupowa. Skupiska obiektów są łączone w taki sposób, aby w efekcie otrzymać jak najmniejszą całkowitą wariancję wewnątrzgrupową. Ekonometria przestrzenna 16 Metoda Warda Odległość pomiędzy grupami wyznaczana jest na podstawie różnicy pomiędzy sumą kwadratów odległości poszczególnych obiektów od środków grup (do których te obiekty należą). Zastosowanie metody Warda prowadzi najczęściej do utworzenia grup o zbliżonej liczbie obiektów. Grupy te tworzą równomierne drzewa połączeń. Ekonometria przestrzenna 17 Metoda Warda Odległość wyznaczana jest zgodnie z formułą: Ni  N p Ni  Nq Ni d ir  d ip  d iq  d pq Ni  Nr Ni  Nr Ni  Nr Gdzie: N i , N p , N q , N r - liczba obiektów w grupach: Ai , Ap , Aq , Ar Ekonometria przestrzenna 18 Metoda najdalszego sąsiedztwa odległość pomiędzy grupami wyznaczana jest na podstawie odległości pomiędzy obiektami umiejscowionymi najdalej od siebie (należącymi do różnych grup). Odległość wyznaczana jest zgodnie z formułą: d ir  0,5d ip  0,5d iq  0,5 d ip  d iq Ekonometria przestrzenna 19 Metoda średniej grupowej odległością pomiędzy grupami jest to wartość średnia obliczona na podstawie wszystkich odległości pomiędzy obiektami różnych grup. Odległość wyznaczana jest zgodnie z formułą: Np Nq d ir  d ip  d iq Nr Nr Ekonometria przestrzenna 20 Metoda mediany odległość pomiędzy grupami definiowana jest jako mediana trzech różnych odległości. Odległości te odnoszą się do dwóch podgrup początkowych, które są łączone w nową podgrupę. Jako wartość pierwszej odległości przyjmuje się odległość pomiędzy środkami pierwszej i nowoutworzonej podgrupy. Ekonometria przestrzenna 21 Metoda mediany Wartością drugiej odległości jest odległość pomiędzy środkami drugiej i nowoutworzonej podgrupy, natomiast wartością dla trzeciej odległości jest odległością pomiędzy środkami pierwszej i drugiej podgrupy. metodą ważonych środków ciężkości Ekonometria przestrzenna 22 Metoda mediany Odległość d ir wyznaczana jest zgodnie z formułą: d ir  0,5d ip  0,5d iq  0,25d pq Ekonometria przestrzenna 23 Metoda środka ciężkości odległość pomiędzy grupami definiowana jest jako odległość pomiędzy środkami ciężkości tych grup (obliczanych na podstawie średniej arytmetycznej wartości współrzędnych obiektów danej grupy). Ekonometria przestrzenna 24 Metoda środka ciężkości Odległość d ir wyznaczana jest zgodnie z formułą: Np Nq N p Nq d ir  d ip  d iq  2 d pq Nr Nr N r Ekonometria przestrzenna 25 Metoda najbliższego sąsiedztwa odległość pomiędzy grupami wyznaczana jest na podstawie odległości pomiędzy obiektami umiejscowionymi najbliżej od siebie (należącymi do różnych grup). Ekonometria przestrzenna 26 Metoda najbliższego sąsiedztwa Odległość d ir wyznaczana jest zgodnie z formułą: d ir  0,5d ip  0,5d iq  0,5 d ip  d iq Ekonometria przestrzenna 27 Metody hierarchiczne Jedną z głównych zalet stosowania metod hierarchicznych do grupowania obiektów jest możliwość zaprezentowania uzyskanych podziałów grup w formie drzewa połączeń – dendrogramu. Drzewo to obrazuje kolejne połączenia grup uzyskane przy każdej iteracji centralnej procedury aglomeracyjnej. Ekonometria przestrzenna 28 Metody hierarchiczne Dzięki temu istnieje możliwość wyodrębnienia poszczególnych skupisk obiektów, a także dokonania ich oceny. Aby wyszczególnić ostateczny wynik grupowania należy przeprowadzić podział dendrogramu w miejscu najdłuższych gałęzi. Ekonometria przestrzenna 29 Metody niehierarchiczne Grupy powstałe na skutek zastosowania metod niehierarchicznych tworzą nieuporządkowaną konfigurację skupisk. W odróżnieniu od metod hierarchicznych w metodach niehierarchicznych grupy wyższego rzędu nie muszą zawierać skupisk niższego rzędu. Ekonometria przestrzenna 30 UWAGA Zastosowanie metod hierarchicznych najczęściej wymaga podjęcia subiektywnych wyborów, które mają wpływ na wynik klasyfikacj Ekonometria przestrzenna 31 Metoda k-średnich Do najpopularniejszych metod niehierarchicznych należy optymalizacyjno-iteracyjna metoda k- średnich. Podobnie jak inne metody optymalizacyjne, metoda k-średnich rozpoczyna się od wstępnego podziału analizowanych obiektów na k podgrup. Ekonometria przestrzenna 32 Metoda k-średnich Liczbę i strukturę skupień w metodzie k- średnich ustala się w sposób losowy lub w oparciu o ocenę ekspertów. Możną ją również ustalić na podstawie klasyfikacji przy użyciu arbitralnie określonej zmiennej bądź też w oparciu o wyniki klasyfikacji uzyskane przy użyciu innych metod taksonomicznych (np. klasyfikacji na podstawie miernika taksonomicznego). Ekonometria przestrzenna 33 Metoda k-średnich Głównym założeniem metody k-średnich jest stopniowa poprawa wstępnego podziału poprzez przenoszenie obiektów z grupy do grupy w kolejnych iteracjach. Maksymalną liczbę iteracji określa się na początku procedury grupowania na podstawie metody k-średnich. Ekonometria przestrzenna 34 Metoda k-średnich Procedura ta ma na celu minimalizację wariancji wewnątrzgrupowej, a także maksymalizację zmienności między grupami. Optymalność uzyskanego podziału bada się wykorzystując odpowiednie kryterium. Ekonometria przestrzenna 35 Metoda k-średnich Procedura poprawy wstępnego podziału obiektów na grupy odbywa się zgodnie z algorytmem J. A. Hartigana. Zgodnie z tą procedurą po ustaleniu maksymalnej liczby powtórzeń algorytmu oraz określeniu liczby podgrup (zawierających wszystkie obiekty) wyznacza się pierwotną macierz B. Ekonometria przestrzenna 36 Metoda k-średnich Elementami macierzy B są środki ciężkości każdej podgrupy ustalonej w wyniku wstępnego podziału obiektów (np. w sposób losowy, w oparciu o ocenę ekspertów lub w oparciu o wyniki innej zastosowanej metody). Ekonometria przestrzenna 37 Metoda k-średnich Macierz B ma następującą postać: b11 b12... b1m  b b22... b2 m  B  21 ............    bk1 bk 2... bkm  l  1, 2,..., k j  1, 2,..., m Ekonometria przestrzenna 38 Metoda k-średnich  Po wyznaczeniu macierzy B, każdy obiekt przyporządkowuje się do grupy, której środek ciężkości znajduje się najbliżej tego obiektu. W kolejnym kroku określa się wyjściowy błąd podziału zgodnie n z formułą: e   d il2 i 1  gdzie odległość euklidesowa określająca minimalną odległość i-tego obiektu od l-tego środka ciężkości, wyznaczona na podstawie d  x  b  wzoru m  2 2 il ij lj j 1 Ekonometria przestrzenna 39 Metoda k-średnich d   xij  blj  m 2 2 il j 1 Gdzie: xij - wartość cechy j dla i-tego obiektu, blj - współrzędna l-tego środka ciężkości Ekonometria przestrzenna 40 Metoda k-średnich Po wyznaczeniu błędu podziału oblicza się jego zmiany będące następstwem przyporządkowania pierwszego obiektu do wszystkich grup aktualnego podziału. Wartość tych zmian wyznacza się na podstawie wzoru: nl d2 nl1 d12l1 e(1)  1l  nl  1 nl1  1 l Ekonometria przestrzenna 41 Metoda k-średnich nd 2 nl1 d12l1 e(1)   l 1l nl  1 nl1  1 l Gdzie:  nl - liczebność grupy l,  d1l2 - odległość pomiędzy pierwszym obiektem a środkiem ciężkości grupy l,  nl - liczebność grupy do której należy 1 pierwszy obiekt,  1l - odległość pomiędzy pierwszym 2 d 1 obiektem a najbliższym środkiem ciężkości. Ekonometria przestrzenna 42 Metoda k-średnich W przypadku gdy minimalna wielkość zmian błędu el(1) jest ujemna to obiekt pierwszy przyporządkowuje się do skupieni dla którego wartość zmian błędu jest minimalna. Następnie wyznacza się środki ciężkości skupisk zawarte w macierzy B a także nową wartość błędu wynikającego z podziału. Ekonometria przestrzenna 43 Metoda k-średnich Jeżeli wartość zmian błędu jest nieujemna to dokonywanie jakichkolwiek zmian w strukturze grup jest bezpodstawne. a także nową wartość błędu wynikającego z podziału. Wielkość zmian błędu podziału oraz ich wartość minimalną określa się dla każdego badanego obiektu. Ekonometria przestrzenna 44 Metoda k-średnich W przypadku gdy powyższe operacje nie powodują przemieszczeń obiektów pomiędzy grupami należy zakończyć algorytm. W przeciwnym przypadku należy rozpocząć kolejną iterację. Procedurę należy powtarzać dopóki liczba iteracji nie osiągnie maksymalnej ustalonej wartości. Ekonometria przestrzenna 45 Metoda k-średnich Istotnym etapem metody k-średnich jest analiza wariancji zmiennych wykorzystanych w procesie grupowania. Ta analiza pozwala na ustalenie, która ze zmiennych diagnostycznych ma największy, a która najmniejszy wpływ na ostateczny wynik grupowania obiektów. Ekonometria przestrzenna 46 Metoda k-średnich W przeciwieństwie do metody Warda, metoda k-średnich jest oparta na analizie zróżnicowania zarówno międzygrupowego, jak i wewnątrzgrupowego. Wariancja międzygrupowa określa poziom zróżnicowania wartości badanej zmiennej pomiędzy grupami obiektów. Ekonometria przestrzenna 47 Wariancja międzygrupowa Wariancja międzygrupowa określa poziom zróżnicowania wartości badanej zmiennej pomiędzy grupami obiektów. Jest ona wyznaczana na podstawie wzoru SS b MG  vb gdzie: Ekonometria przestrzenna 48 Wariancja międzygrupowa vb liczba stopni swobody obliczana według wzoru vb  b  1 SSB suma kwadratów odchyleń badanej zmiennej pomiędzy grupami, wyznaczane zgodnie z wzorem b SS b   ( xi  x ) 2 ni i 1 Ekonometria przestrzenna 49 Wariancja wewnątrzgrupowa wariancja wewnątrzgrupowa wyznacza poziom zróżnicowania wartości zmiennej dla obiektów należących do tej samej grupy. Ta wariancja jest obliczana zgodnie z wzorem: SS w WG  vw vw  n  bEkonometria przestrzenna 50  Gdzie:  SSw - suma kwadratów odchyleń badanej zmiennej wewnątrz poszczególnych grup, wyznaczane zgodnie z wzorem: b ni SS w   ( xij  xi ) 2 i 1 j 1 vw  n  b  xij - wartość zmiennej Xj dla j-tego obiektu należącego do i-tej grupy. Ekonometria przestrzenna 51 Metoda k-średnich Istotność każdej zmiennej diagnostycznej można zweryfikować przy pomocy testu Fishera-Snedecora (testu F). Weryfikacji poddaje się następującą hipotezę zerową: H0: x1  x 2    x b Ekonometria przestrzenna 52 Metoda k-średnich Zgodnie z tą hipotezą wartości średnie badanej zmiennej w uzyskanych grupach obiektów nie są istotnie zróżnicowane. Hipotezie H0 przeciwstawia się alternatywną hipotezę H1. Ta hipoteza zakłada, że średnie wartości badanej zmiennej są istotnie zróżnicowane co najmniej dla dwóch grup. Ekonometria przestrzenna 53 Metoda k-średnich Zgodnie z tą hipotezą wartości średnie badanej zmiennej w uzyskanych grupach obiektów nie są istotnie zróżnicowane. Hipotezie H0 przeciwstawia się alternatywną hipotezę H1. Ta hipoteza zakłada, że średnie wartości badanej zmiennej są istotnie zróżnicowane co najmniej dla dwóch grup. Ekonometria przestrzenna 54 Metoda k-średnich  Hipoteza zerowa testu F jest weryfikowana na podstawie statystyki, którą wyznacza się według wzoru: MG F WG  gdzie:  MG - wartość zróżnicowania międzygrupowego,  WG - wartość zróżnicowania wewnątrzgrupowego. Ekonometria przestrzenna 55 Metoda k-średnich  Jeżeli wartość statystyki F dla badanej zmiennej jest niższa niż wartość krytyczna oznacza to, że średnie wartości tej zmiennej nie są istotnie zróżnicowane. Z kolei w przeciwnym przypadku należy odrzucić hipotezę zerową.  Wartość krytyczną dla testu F odczytuje się z tablic dla ustalonego poziomu istotności oraz odpowiedniej liczby stopni swobody: ; vb  b  1 v w  n  b Ekonometria przestrzenna 56 INNE METODY AGLOMERACYJNE Ekonometria przestrzenna 57 Inne metody niehierarchiczne Obok najpopularniejszej metody średnich istnieją jeszcze inne (mniej popularne) metody niehierarchiczne. Wśród nich wyróżnić należy – metodę Forgy-Janceya; – metodę Wisharta. Ekonometria przestrzenna 58 Metoda Forgy-Janceya Metoda ta zaproponowana w 1965 roku przez E.W Forgy i R.C. Jancey’a. Algorytm tej meotdy jest następujący: – Ustala się liczbe grup, na które chcemy podzielić badaną zbiorowość. – Wstępnie przypisuje się obiekty do grup; na tym etapie ustala się również liczbę iteracji przemieszczenia obiektów pomiędzy grupami. Ekonometria przestrzenna 59 Metoda Forgy-Janceya Oblicza się współrzędne środków ciężkości grupy w tym przypadku jest to jądro grupy: nr  1 or  nr o i 1 i W kolejnym kroku przypisuje się i-ty obiekt do tej grupy, w której odległość między i-tym obiektem a jądrem grupy jest najmniejsza Ekonometria przestrzenna 60 Metoda Forgy-Janceya W nowych grupach wyznacza się jądra grup wg wzoru: r r  J  J  o - J t t -1 t -1 r t -1 r  – Gdzie  parametr przyjmujący w zależności od wersji metody wartość 1,2 lub 1,5 Ekonometria przestrzenna 61 Metoda Forgy-Janceya Kolejne iteracje powtarza się aż do momentu, gdy nie obserwuje się żadnej zmiany w konfiguracji grup w danej iteracji albo osiągnięta zostanie maksymalna liczba iteracji Ekonometria przestrzenna 62 Metoda Wisharta Procedura tej metody przebiega następująco: Ustala się: – wstępną liczbę grup (z) na które dzieli się badane obiekty – minimalna liczbę obiektów w grupach ( nr )min – Odległość progową (d*),która wyznacza max dopuszczalną odległość euklidesową obiektu od środka ciężkości grupy – maksymalną liczbę iteracji. 63 Metoda Wisharta Przeprowadza się wstępny podział obiektów. Wyznacza się środki ciężkości tych grup. Grupowane obiekty dzieli się na dwie grupy: nieresztową oraz resztową. Do grupy nieresztowej należą obiekty dla których odległości od najbliższych im środków ciężkości są mniejsze od odległości progowej, Ekonometria przestrzenna 64 Metoda Wisharta Obiekty te zostają przyłączone do grup, których odległości od najbliższych im środków ciężkości grup są niższe od założonej wartości krytycznej. Do grupy resztowej klasyfikuje się obiekty, których odległość jest wyższa od założonej wartości maksymalnej. Ekonometria przestrzenna 65 Metoda Wisharta Sprawdza się, czy liczebności grup obiektów (po zmianach) nie sa mniejsze od założonej minimalnej liczby grup. Obiekty z grup, których liczebności nie spełniają tego warunku zostają włączonej do grupy resztowej. Ekonometria przestrzenna 66 Metoda Wisharta Jeśli w danej iteracji nie nastąpiły żadne przesunięcia w strukturach grup to algorytm grupowania jest zakończony Jeśli nastąpiły zmiany w dotychczasowej strukturze przystępuje się do iteraqcji drugiej. Ekonometria przestrzenna 67 UWAGA Przed przystąpieniem do grupowania obiektów na podstawie metod niehierarchicznych należy określić liczbę skupień. Ma to istotny wpływ na uzyskaną klasyfikację. W przypadku określenia za dużej ilości skupień kłopotliwa może być interpretacja wyników. Z kolei określenie za małej ilości skupień skutkuje niską jednorodnością wewnątrzgrupową. Ekonometria przestrzenna 68  Niehierarchiczna metoda grupowania k- średnich umożliwia weryfikację i ocenę jakości klasyfikacji (na podstawie analizy porównawczej wartości średnich w podgrupach). Metoda umożliwia również wskazanie cech wpływających na zróżnicowanie skupisk. Ekonometria przestrzenna 69 Metody niehierarchiczne Metody niehierarchiczne charakteryzują się szybkością obliczeń, co jest również istotną zaletą tych metod. Do negatywnych cech metody k-średnich zaliczyć można brak hierarchii wewnątrz grupy, jak również fakt, że zmiana ilości skupień spowoduje brak zależności pomiędzy nowymi grupami a skupiskami uzyskanymi w poprzednim podziale Ekonometria przestrzenna 70