1 dr Dorota Węziak-Białowolska Instytut Statystyki i Demografii Metody klasyfikacji obiektów 1

2 Jeśli obiekty opisywane są przez informację wielowymiarową (kilka zmiennych), powstaje problem, jak rozpoznać prawidłowości występujące w zbiorze obiektów, czyli jak podzielić (poklasyfikować) obiekty na jak najbardziej jednorodne grupy. 2 dr Dorota Węziak-Białowolska, ISiD, SGH

3 Metody klasyfikacji: A. Metody hierarchiczne: 1. 1. Aglomeracyjne – początkowo każdy obiekt jest odrębnym skupieniem, potem stopniowo łączymy podobne do siebie obiekty w nowe skupienia, aż do momentu uzyskania jednego skupienia 2. 2. Podziałowe – wychodząc od jednego skupienia, rozdzielamy obiekty na mniejsze skupienia B. Metody niehierarchiczne 1. 1. Analiza skupień – metoda k-średnich 3 dr Dorota Węziak-Białowolska, ISiD, SGH

4 Punktem wyjścia jest określenie podobieństwa jednostek/obiektów tworzących badaną zbiorowość Podobieństwo między obiektami mierzy się najczęściej obliczając odległości między nimi: Odległości: 1. 1. Euklidesowa 2. 2. Kwadrat euklidesowej 3. 3. Minkowskiego 4. 4. Miejska 5. 5. Mahalanobisa 6. 6. Czebyszewa 7. 7. … 4 dr Dorota Węziak-Białowolska, ISiD, SGH Najczęściej stosowane w praktyce d ij – odległość między jednostkami o numerach i oraz j x ik – wartość k-tej cechy dla i-tej jednostki w zbiorowości Wybór miary odległości ma wpływ na wynik grupowania!

5 Jednostki, w jakich mierzone są zmienne, mają wpływ na wynik pomiaru Jeśli zmienne będące kryteriami klasyfikacji nie są jednomianowe, zalecane jest wystandaryzowanie lub znormalizowanie zmiennych przed przystąpieniem do procedury grupowania dr Dorota Węziak-Białowolska, ISiD, SGH 5

6 Przekształcenia normalizacyjne 1. 1. Standaryzacja 2. 2. Unitaryzacja 6 dr Dorota Węziak-Białowolska, ISiD, SGH

7 Standaryzacja Ma na celu uzyskanie zmiennych o wariancji równej 1 i średniej równej 0 7 dr Dorota Węziak-Białowolska, ISiD, SGH

8 Unitaryzacja Transformacja zmiennych do takiej postaci, aby przedział ich zmienności miał stałą długość 1 8 dr Dorota Węziak-Białowolska, ISiD, SGH

9 Metody hierarchiczne – procedura grupowania: 1. 1.Wyznaczenie macierzy odległości 2. 2.Wybór najmniejszej wartości w macierzy odległości (z wyjątkiem głównej przekątnej) i utworzenie skupienia z jednostek, których ta najmniejsza odległość dotyczy 3. 3.Ponowne wyznaczenie macierzy odległości dla zredukowanego zbioru obiektów. Dla jednostek, których nie połączono, wartości w macierzy odległości nie zmieniają się. Natomiast trzeba określić podobieństwo między nowym skupieniem a pozostałymi jednostkami. Kroki 2 i 3 powtarzamy aż do utworzenia jednego n-elementowego skupienia ALE jak wyznaczyć odległość z punktu 3? 9 dr Dorota Węziak-Białowolska, ISiD, SGH

10 Metody łączenia obiektów – metody określania podobieństwa między po utworzeniu skupienia 1. 1.Metoda najbliższego sąsiedztwa (pojedynczego wiązania, single linkage) 2. 2.Metoda najdalszego sąsiedztwa (pełnego wiązania, complete linkage) 3. 3.Metoda średnich połączeń (average linkage) 4. 4.Metoda Warda 10 dr Dorota Węziak-Białowolska, ISiD, SGH

11 Metoda najbliższego sąsiedztwa – odległość między nowoutworzonym skupieniem i jednostką zewnętrzną ustalana jest jako najmniejsza odległość z odległości między jednostkami w tym skupieniu i jednostką zewnętrzną – odległość między dwoma skupieniami ustalana jest jako najmniejsza odległość z odległości między jednostkami z jednego i drugiego skupienia 11 dr Dorota Węziak-Białowolska, ISiD, SGH

12 Metoda najdalszego sąsiedztwa – odległość między nowoutworzonym skupieniem i jednostką zewnętrzną ustalana jest jako największa odległość z odległości między jednostkami w tym skupieniu i jednostką zewnętrzną – odległość między dwoma skupieniami ustalana jest jako największa odległość z odległości między jednostkami z jednego z drugiego skupienia 12 dr Dorota Węziak-Białowolska, ISiD, SGH

13 Metoda średnich połączeń – odległość między nowoutworzonym skupieniem i jednostką zewnętrzną ustalana jest jako średnia arytmetyczna z odległości między jednostkami w tym skupieniu i jednostką zewnętrzną – odległość między dwoma skupieniami ustalana jest jako średnia arytmetyczna z odległości między jednostkami z jednego z drugiego skupienia 13 dr Dorota Węziak-Białowolska, ISiD, SGH

14 Metoda Warda W metodzie tej odległości między dwoma grupami obiektów nie można przedstawić wprost za pomocą odległości pomiędzy obiektami należącymi do tych grup Dwie grupy obiektów są łączone w jedną grupę tak, aby zminimalizowć sumę kwadratów odchyleń wszystkich obiektów z tych dwóch grup od środka ciężkości nowej grupy, która powstanie w wyniku połączeń tych dwóch grup Na każdym etapie łączenia grup obiektów, ze wszystkich możliwych do łączenia grup obiektów, łączy się w jedną grupę te grupy, które w rezultacie tworzą grupę obiektów o najmniejszym zróżnicowaniu ze względu na opisujące je zmienne dr Dorota Węziak-Białowolska, ISiD, SGH 14

15 Metoda Warda Kryterium grupowania jednostek w kolejne skupienia jest minimum zróżnicowania wartości cech względem wartości średnich skupień tworzonych w kolejnych krokach Miarą zróżnicowania jest błąd sumy kwadratów – ESS (error of sum of squares) k – liczba jednostek w grupie x i – wartość zmiennej stanowiącej kryterium grupowania charakteryzująca i-tą jednostkę w grupie 15 dr Dorota Węziak-Białowolska, ISiD, SGH

16 Przykład Które kraje europejskie są do siebie najbardziej podobne, a które różnią się najbardziej pod względem zaufania do różnego rodzaju instytucji? 16 dr Dorota Węziak-Białowolska, ISiD, SGH

17 Kraje: Czechy, Dania, Hiszpania, Finlandia, Francja, Wielka Brytania, Grecja, Węgry, Holandia, Norwegia, Polska, Portugalia, Słowacja Cechy: Trust in country's parliament (1 – 10) Trust in the legal system (1 – 10) Trust in the police (1 – 10) Trust in politicians (1 – 10) Trust in political parties (1 – 10) Trust in the European Parliament (1 – 10) Trust in the United Nations (1 – 10) Źródło danych: European Social Survey, Round 3 17 dr Dorota Węziak-Białowolska, ISiD, SGH

18 Dane: 18 dr Dorota Węziak-Białowolska, ISiD, SGH

19 Najpierw analiza tylko dla czterech krajów: Polski, Czech, Słowacji i Węgier Odległość: Kwadrat odległości euklidesowej Odległość między i-tym i j-tym obiektem ze względu na p cech Metoda najbliższego sąsiedztwa 19 dr Dorota Węziak-Białowolska, ISiD, SGH

20 Metoda najbliższego sąsiedztwa 20 dr Dorota Węziak-Białowolska, ISiD, SGH

21 Wynik analizy skupień można przedstawiać za pomocą dendrogramu 21 dr Dorota Węziak-Białowolska, ISiD, SGH

22 Problem Należy sprawdzić, które z krajów europejskich są do siebie podobne pod względem poziomu zaufania społecznego. Plik: zaufanie.sav 22 dr Dorota Węziak-Białowolska, ISiD, SGH

23 Odległość: Kwadrat odległości euklidesowej 23 dr Dorota Węziak-Białowolska, ISiD, SGH

24 24 dr Dorota Węziak-Białowolska, ISiD, SGH

25 DEFIGBGR + ES + FRHUNLNOPLPTSK + CZ DE01937101213201022 FI 016204172634563 GB 0415712211323 GR + ES + FR 017718231320 HU 02431646 NL 07382636 NO 0513753 PL 063 PT 04 SK + CZ 0 25 dr Dorota Węziak-Białowolska, ISiD, SGH

26 Wynik analizy skupień można przedstawiać za pomocą dendrogramu Metoda najdalszego sąsiedztwa 26 dr Dorota Węziak-Białowolska, ISiD, SGH

27 Metoda najbliższego sąsiedztwa 27 dr Dorota Węziak-Białowolska, ISiD, SGH

28 Metoda średnich połączeń 28 dr Dorota Węziak-Białowolska, ISiD, SGH

29 Im mniej wyniki grupowania zależą od przyjętej metody wyznaczania odległości między nowym skupieniem a jednostkami poza skupieniem, tym otrzymane rozwiązanie jest bardziej wiarygodne 29 dr Dorota Węziak-Białowolska, ISiD, SGH

30 Metody niehierarchiczne Metoda k – średnich Tworzymy skupienia w taki sposób, aby jednostki w skupieniu były jak najbardziej podobne, ale jednocześnie jednostki z różnych skupień możliwie jak najmocniej różniły się od siebie 1. 1. Określamy a priori liczbę skupień 2. 2. Losowo wybieramy początkowego reprezentanta dla każdego skupienia 3. 3. Algorytm w kolejnych iteracjach przenosi obiekty do różnych skupień, zmierzając do minimalizacji zmienności wewnątrz skupień i maksymalizacji zmienności między skupieniami 4. 4. Kolejne kroki charakteryzowane są przez funkcję błędu; jej postać jest różnie definiowana w różnych pakietach statystycznych – obliczeniowo jest to „odwrotność” analizy wariancji 30 dr Dorota Węziak-Białowolska, ISiD, SGH

31 Zadanie Należy sprawdzić, które z krajów europejskich są do siebie podobne pod względem poziomu zaufania społecznego. Stosujemy metodę k-średnich Plik: zaufanie.sav 31 dr Dorota Węziak-Białowolska, ISiD, SGH