Wysyłanie dobrej pracy do bazy wiedzy jest proste. Skorzystaj z poniższego formularza
Studenci, doktoranci, młodzi naukowcy, którzy wykorzystują bazę wiedzy w swoich studiach i pracy będą Ci bardzo wdzięczni.
Wstęp
1.Historia „analizy skupień”
2. Terminologia
2.1Przedmiot i znak
2.2 Odległość między obiektami (metryczna)
2.3 Gęstość i lokalizacja klastrów
2.4 Odległość między klastrami
3. Metody grupowania
3.1Cechy hierarchicznych metod aglomeracyjnych
3.2Cechy iteracyjnych metod grupowania
4. Grupowanie funkcji
5. Stabilność i jakość klastrowania
Bibliografia
WPROWADZANIE
„Analiza skupień to zestaw metod matematycznych zaprojektowanych w celu utworzenia stosunkowo „odległych” od siebie grup „bliskich” obiektów na podstawie informacji o odległościach lub połączeniach (miarach bliskości) między nimi. klasyfikacja, taksonomia, rozpoznawanie wzorców bez nauczyciela." Taką definicję analizy skupień podano w najnowszym wydaniu Słownika statystycznego. W rzeczywistości „analiza skupień” to uogólniona nazwa dość dużego zestawu algorytmów wykorzystywanych do tworzenia klasyfikacji. Szereg publikacji wykorzystuje również takie synonimy do analizy skupień, jak klasyfikacja i podział. Analiza skupień jest szeroko stosowana w nauce jako środek analizy typologicznej. W każdej działalności naukowej klasyfikacja jest jednym z podstawowych elementów składowych, bez którego niemożliwe jest budowanie i testowanie hipotez i teorii naukowych. Dlatego w swojej pracy uważam za konieczne rozważenie zagadnień analizy skupień (podstawy analizy skupień), jak również rozważenie jej terminologii i podanie kilku przykładów wykorzystania tej metody z przetwarzaniem danych jako głównym celem.
1. HISTORIA „ANALIZY KLASTERÓW”
Analiza publikacji krajowych i zagranicznych pokazuje, że analiza skupień znajduje zastosowanie w wielu różnych dziedzinach nauki: chemii, biologii, medycynie, archeologii, historii, geografii, ekonomii, filologii itp. Książka VV Nalimova „Probabilistyczny model języka” opisuje zastosowanie analizy skupień w badaniu 70 próbek analitycznych. Większość literatury dotyczącej analizy skupień pojawiła się w ciągu ostatnich trzech dekad, chociaż pierwsze prace, w których wspomniano o metodach skupień, pojawiły się dość dawno temu. Polski antropolog K. Chekanowski wysunął ideę „klasyfikacji strukturalnej”, która zawierała główną ideę analizy skupień – alokację zwartych grup obiektów.
W 1925 r. radziecki hydrobiolog P.V. Terentyev opracował tak zwaną „metodę plejad korelacyjnych”, przeznaczoną do grupowania skorelowanych cech. Metoda ta dała impuls do rozwoju metod grupowania za pomocą wykresów. Termin „analiza skupień” został po raz pierwszy zaproponowany przez firmę Trion. Słowo „klaster” jest tłumaczone z angielskiego jako „kiść, pędzel, wiązka, grupa”. Z tego powodu ten rodzaj analizy został pierwotnie nazwany „analizą skupień”. Na początku lat pięćdziesiątych pojawiły się publikacje R. Lewisa, E. Fixa i J. Hodgesa dotyczące hierarchicznych algorytmów analizy skupień. Wyraźny impuls do rozwoju prac nad analizą skupień dała praca R. Rosenblatta nad urządzeniem rozpoznającym (perceptron), która położyła podwaliny pod rozwój teorii „rozpoznawania wzorców bez nauczyciela”.
Impulsem do rozwoju metod grupowania była książka „Principles of Numerical Taxonomy”, opublikowana w 1963 roku. dwóch biologów - Robert Sokal i Peter Sneath. Autorzy tej książki wyszli z tego, że w celu stworzenia skutecznych klasyfikacji biologicznych procedura grupowania powinna zapewniać stosowanie różnych wskaźników charakteryzujących badane organizmy, oceniać stopień podobieństwa między tymi organizmami i zapewniać rozmieszczenie podobnych organizmów w tej samej grupie. W takim przypadku utworzone grupy powinny być wystarczająco „lokalne”, tj. podobieństwo przedmiotów (organizmów) w grupach powinno przewyższać podobieństwo grup między sobą. Późniejsza analiza zidentyfikowanych grup, zdaniem autorów, może wyjaśnić, czy grupy te odpowiadają różnym gatunkom biologicznym. Sokal i Sneath założyli więc, że ujawnienie struktury rozkładu obiektów na grupy pomaga ustalić proces powstawania tych struktur. A różnica i podobieństwo organizmów różnych klastrów (grup) może służyć jako podstawa do zrozumienia trwającego procesu ewolucyjnego i wyjaśnienia jego mechanizmu.
W tych samych latach wiele algorytmów zostało zaproponowanych przez takich autorów jak J. McKean, G. Ball i D. Hall przy użyciu metody k-średnich; G. Lance i W. Williams, N. Jardine i inni – o metodach hierarchicznych. Znaczący wkład w rozwój metod analizy skupień wnieśli krajowi naukowcy - E.M. Braverman, A.A. Dorofeyuk, I.B. Muchnik, LA Rastrigin, Yu.I W szczególności w latach 60-70. Dużą popularnością cieszyły się liczne algorytmy opracowane przez nowosybirskich matematyków N.G. Są to tak znane algorytmy jak FOREL, BIGFOR, KRAB, NTTP, DRET, TRF itp. Na podstawie tych pakietów powstał specjalistyczny pakiet oprogramowania OTEX. Nie mniej interesujące produkty oprogramowania PPSA i Klass-Master zostały stworzone przez moskiewskich matematyków S.A. Aivazyan, I.S. Enyukov i B.G. Mirkin.
W pewnym stopniu metody analizy skupień są dostępne w większości najbardziej znanych krajowych i zagranicznych pakietów statystycznych: SIGAMD, DataScope, STADIA, SOMI, PNP-BIM, COPRA-2, SITO, SAS, SPSS, STATISTICA, BMDP, STATGRAPHICS , GENSTAT, S-PLUS itp. Oczywiście 10 lat po wydaniu tej recenzji sporo się zmieniło, pojawiły się nowe wersje wielu programów statystycznych, pojawiły się zupełnie nowe programy, które wykorzystują zarówno nowe algorytmy, jak i znacznie zwiększoną moc. Informatyka. Jednak większość pakietów statystycznych korzysta z algorytmów zaproponowanych i opracowanych w latach 60-70.
Według przybliżonych szacunków ekspertów, co trzy lata podwaja się liczba publikacji dotyczących analizy skupień i jej zastosowań w różnych dziedzinach wiedzy. Jakie są powody tak burzliwego zainteresowania tego typu analizami? Obiektywnie istnieją trzy główne przyczyny tego zjawiska. Jest to pojawienie się potężnej technologii obliczeniowej, bez której analiza klastrowa rzeczywistych danych jest praktycznie niewykonalna. Drugim powodem jest to, że współczesna nauka w coraz większym stopniu opiera się na klasyfikacji w swoich konstrukcjach. Co więcej, proces ten pogłębia się coraz bardziej, ponieważ równolegle z tym następuje rosnąca specjalizacja wiedzy, co jest niemożliwe bez wystarczająco obiektywnej klasyfikacji.
Trzeci powód - pogłębienie wiedzy specjalnej nieuchronnie prowadzi do wzrostu liczby zmiennych branych pod uwagę w analizie niektórych obiektów i zjawisk. W rezultacie klasyfikacja subiektywna, która wcześniej opierała się na dość niewielkiej liczbie branych pod uwagę cech, często okazuje się zawodna. A obiektywna klasyfikacja, przy stale rosnącym zestawie cech obiektów, wymaga użycia złożonych algorytmów klastrowania, które można zaimplementować tylko na nowoczesnych komputerach. To właśnie te powody doprowadziły do „boomu klastrowego”. Jednak wśród lekarzy i biologów analiza skupień nie stała się jeszcze dość popularną i powszechną metodą badawczą.
2 TERMINOLOGIA
2. 1 PRZEDMIOT I ZNAK
Przedstawmy najpierw takie pojęcia, jak przedmiot i atrybut. Przedmiot – z łac. objectum – podmiot. W odniesieniu do chemii i biologii przez przedmioty będziemy rozumieć konkretne przedmioty badań, które są badane metodami fizycznymi, chemicznymi i innymi. Takimi przedmiotami mogą być np. próbki, rośliny, zwierzęta itp. Pewien zbiór obiektów dostępnych dla badacza do badania nazywany jest próbką lub zbiorem próbek. Liczbę obiektów w takiej populacji nazywa się zwykle wielkością próby. Zazwyczaj wielkość próbki jest oznaczona łacińską literą „n” lub „N”.
Znak (synonimy - właściwość, zmienna, charakterystyka; angielski - zmienna - zmienna.) - jest określoną właściwością obiektu. Te właściwości mogą być wyrażone jako wartości liczbowe lub nieliczbowe. Na przykład ciśnienie krwi (skurczowe lub rozkurczowe) mierzy się w milimetrach słupa rtęci, wagę w kilogramach, wzrost w centymetrach itp. Takie znaki są ilościowe. W przeciwieństwie do tych ciągłych cech liczbowych (skal), wiele cech może mieć wartości dyskretne, nieciągłe. Z kolei takie dyskretne cechy zwykle dzieli się na dwie grupy.
1) Pierwsza grupa to zmienne rangowe lub tak zwane zmienne porządkowe (skale). Takie znaki charakteryzują się właściwością uporządkowania tych wartości. Obejmują one etapy konkretnej choroby, grupy wiekowe, wyniki wiedzy uczniów, 12-punktową skalę trzęsienia ziemi Richtera itp.
2) Druga grupa cech dyskretnych nie ma takiego porządku i nazywana jest nominalnymi (od słowa „nominalny” – próbka) lub cechami klasyfikacyjnymi. Przykładem takich objawów może być stan pacjenta – „zdrowy” lub „chory”, płeć pacjenta, okres obserwacji – „przed leczeniem” i „po leczeniu” itp. W takich przypadkach zwyczajowo mówi się, że takie cechy należą do skali nazw.
Pojęcia dotyczące obiektu i cechy są zwykle nazywane macierzą „Obiekt-właściwość” lub „Obiekt-cecha”. Macierz będzie prostokątną tabelą składającą się z wartości cech opisujących właściwości badanej próbki obserwacji. W tym kontekście jedna obserwacja zostanie zapisana jako osobny wiersz składający się z wartości użytych cech. Oddzielny atrybut w takiej macierzy danych będzie reprezentowany przez kolumnę składającą się z wartości tego atrybutu dla wszystkich obiektów w próbce.
2. 2 ODLEGŁOŚĆ MIĘDZY OBIEKTAMI (METRYCZNE)
Wprowadźmy pojęcie „odległość między obiektami”. Ta koncepcja jest integralną miarą podobieństwa obiektów do siebie. Odległość między obiektami w przestrzeni cech to taka wartość d ij, która spełnia następujące aksjomaty:
1. d ij > 0 (nieujemność odległości)
2. d ij = d ji (symetria)
3. d ij + d jk > d ik (nierówność trójkąta)
4. Jeśli d ij nie jest równe 0, to i nie jest równe j (rozróżnialność obiektów nieidentycznych)
5. Jeśli d ij = 0, to i = j (nierozróżnialność identycznych obiektów)
Wygodnie jest przedstawić miarę bliskości (podobieństwa) obiektów jako odwrotność na odległość między obiektami. Liczne publikacje poświęcone analizie skupień opisują ponad 50 różnych sposobów obliczania odległości między obiektami. Oprócz terminu „odległość” w literaturze często pojawia się inny termin - „metryczny”, który implikuje metodę obliczania określonej odległości. Najbardziej dostępna dla percepcji i zrozumienia w przypadku cech ilościowych jest tak zwana „odległość euklidesowa” lub „metryka euklidesowa”. Wzór na obliczenie tej odległości to:
W tej formule zastosowano następującą notację:
· d ij - odległość między i-tym i j-tym obiektem;
· x ik - wartość liczbowa k-tej zmiennej dla i-tego obiektu;
· x jk - wartość liczbowa k-tej zmiennej dla j-tego obiektu;
· v - liczba zmiennych opisujących obiekty.
Zatem dla przypadku v=2, gdy mamy tylko dwa znaki ilościowe, odległość d ij będzie równa długości przeciwprostokątnej trójkąta prostokątnego, który łączy dwa punkty w prostokątnym układzie współrzędnych. Te dwa punkty będą odpowiadały i-tej i j-tej obserwacji próbki. Często zamiast zwykłej odległości euklidesowej używa się kwadratu d 2 ij. Ponadto w niektórych przypadkach stosuje się „ważoną” odległość euklidesową, przy obliczaniu której współczynniki wagowe są używane dla poszczególnych terminów. Aby zilustrować koncepcję metryki euklidesowej, posłużymy się prostym przykładem uczącym. Macierz danych pokazana w poniższej tabeli składa się z 5 obserwacji i dwóch zmiennych.
Tabela 1
Macierz danych pięciu obserwowanych próbek i dwóch zmiennych.
Korzystając z metryki euklidesowej obliczamy macierz odległości międzyobiektowych, składającą się z wartości d ij - odległości między i-tym i j-tym obiektem. W naszym przypadku i oraz j to numer obiektu, obserwacji. Ponieważ wielkość próbki wynosi 5, odpowiednio i i j mogą przyjmować wartości od 1 do 5. Oczywiste jest również, że liczba wszystkich możliwych odległości w parach będzie wynosić 5*5=25. Rzeczywiście, dla pierwszego obiektu będą to następujące odległości: 1-1; 1-2; 1-3; 1-4; 1-5. Dla obiektu 2 będzie również 5 możliwych odległości: 2-1; 2-2; 2-3; 2-4; 2-5 itd. Jednak liczba różne odległości będzie mniejszy niż 25, ponieważ należy wziąć pod uwagę właściwość nierozróżnialności identycznych obiektów - d ij = 0 dla i = j. Oznacza to, że odległość między obiektem nr 1 a tym samym obiektem nr 1 będzie wynosić zero. We wszystkich pozostałych przypadkach i = j będą takie same odległości zerowe. Ponadto z własności symetrii wynika, że d ij = d ji dla dowolnych i oraz j. Tych. odległość między obiektami #1 i #2 jest równa odległości między obiektami #2 i #1.
Wyrażenie na odległość euklidesową jest bardzo podobne do tak zwanej uogólnionej odległości potęgowej Minkowskiego, w której zamiast dwu potęgowych stosuje się inną wartość. W ogólnym przypadku wartość ta jest oznaczona symbolem „p”.
Dla p = 2 otrzymujemy zwykłą odległość euklidesową. Zatem wyrażenie na uogólnioną metrykę Minkowskiego ma postać:
Wyboru określonej wartości wykładnika „p” dokonuje sam badacz.
Szczególnym przypadkiem odległości Minkowskiego jest tak zwana odległość Manhattan, czyli „odległość między miastami”, odpowiadająca p=1:
Tak więc odległość Manhattanu jest sumą modułów różnic odpowiadających im cech obiektów. Jeśli p ma tendencję do nieskończoności, otrzymujemy metrykę „dominacji” lub metrykę Sup:
co można również przedstawić jako d ij = max| x ik - x jk |.
Metryka Minkowskiego to w rzeczywistości duża rodzina metryk, w tym najpopularniejsze metryki. Istnieją jednak metody obliczania odległości między obiektami, które zasadniczo różnią się od metryk Minkowskiego. Najważniejszym z nich jest tak zwany dystans Mahalanobisa, który ma dość specyficzne właściwości. Wyrażenie dla tej metryki:
Tutaj przez X i oraz X j wskazane są wektory kolumnowe wartości zmiennych dla i-tego i j-tego obiektu. Symbol T w wyrazie (X i - X j ) T oznacza tzw. operację transpozycji wektorowej. Symbol S wskazana jest wspólna wewnątrzgrupowa macierz wariancji-kowariancji. Symbol -1 nad S oznacza, że trzeba odwrócić macierz S . W przeciwieństwie do metryki Minkowskiego i metryki euklidesowej odległość Mahalanobisa przez macierz wariancji-kowariancji S związane z korelacjami zmiennych. Gdy korelacje między zmiennymi wynoszą zero, odległość Mahalanobisa jest równa kwadratowi odległości euklidesowej.
W przypadku wykorzystania dychotomicznych (mających tylko dwie wartości) cech jakościowych szeroko stosowany jest dystans Hamminga
równa liczbie niezgodności wartości odpowiednich cech dla rozważanych i-tego i j-tego obiektów.
2. 3 GĘSTOŚĆ I LOKALIZACJA KLASTRÓW
Głównym celem analizy skupień jest znalezienie w próbie grup obiektów podobnych do siebie. Załóżmy, że niektórymi możliwymi metodami uzyskaliśmy takie grupy - klastry. Należy zwrócić uwagę na ważne właściwości klastrów. Jedną z tych właściwości jest gęstość rozkładu punktów, obserwacji w obrębie klastra. Ta właściwość pozwala nam zdefiniować klaster jako klaster punktów w przestrzeni wielowymiarowej, która jest stosunkowo gęsta w porównaniu z innymi obszarami tej przestrzeni, które albo w ogóle nie zawierają punktów, albo zawierają niewielką liczbę obserwacji. Innymi słowy, jak zwarta jest ta gromada lub odwrotnie, jak rzadka jest. Pomimo wystarczających dowodów na tę właściwość, nie ma jednoznacznego sposobu obliczenia takiego wskaźnika (gęstości). Najbardziej udanym wskaźnikiem charakteryzującym zwartość, gęstość „upakowania” obserwacji wielowymiarowych w danym skupieniu, jest rozproszenie odległości od środka skupienia do poszczególnych punktów skupienia. Im mniejsza dyspersja tej odległości, im bliżej środka gromady znajdują się obserwacje, tym większa gęstość gromady. I odwrotnie, im większe jest rozproszenie odległości, tym rzadsza jest ta gromada, a co za tym idzie, istnieją punkty położone zarówno blisko środka gromady, jak i dość odległe od środka gromady.
Kolejną właściwością klastrów jest ich wielkość. Głównym wskaźnikiem wielkości klastra jest jego „promień”. Ta właściwość najpełniej odzwierciedla rzeczywisty rozmiar gromady, jeśli rozważana gromada jest okrągła i hipersfera w przestrzeni wielowymiarowej. Jeśli jednak gromady mają wydłużone kształty, pojęcie promienia lub średnicy nie odzwierciedla już rzeczywistego rozmiaru gromady.
Kolejną ważną właściwością klastra jest ich lokalność, rozdzielność. Charakteryzuje stopień nakładania się i wzajemnego oddalenia klastrów od siebie w przestrzeni wielowymiarowej. Rozważmy na przykład rozmieszczenie trzech klastrów w przestrzeni nowych, zintegrowanych cech na poniższym rysunku. Osie 1 i 2 uzyskano specjalną metodą z 12 cech odblaskowych właściwości różnych form erytrocytów, badanych za pomocą mikroskopii elektronowej.
Obrazek 1
Widzimy, że klaster 1 ma minimalny rozmiar, podczas gdy klastry 2 i 3 mają w przybliżeniu równe rozmiary. Jednocześnie możemy powiedzieć, że minimalne zagęszczenie, a co za tym idzie maksymalne rozproszenie odległości, jest charakterystyczne dla skupienia 3. Ponadto skupisko 1 jest oddzielone odpowiednio dużymi odcinkami pustej przestrzeni zarówno od skupienia 2, jak i od skupienia 3. 2 i 3 częściowo zachodzą na siebie. Interesujący jest fakt, że skupienie 1 ma znacznie większą różnicę od skupień 2. i 3. wzdłuż osi 1 niż wzdłuż osi 2. Z drugiej strony skupienia 2 i 3 różnią się od siebie w przybliżeniu jednakowo zarówno wzdłuż osi 1, jak i wzdłuż osi 2. Oczywiście do takiej analizy wizualnej konieczne jest rzutowanie wszystkich obserwacji próbki na specjalne osie, w których rzuty elementów klastra będą widoczne jako osobne klastry.
2. 4 ODLEGŁOŚĆ POMIĘDZY KLASTRAMI
W szerszym sensie obiekty mogą być rozumiane nie tylko jako oryginalne przedmioty badań, przedstawione w macierzy „obiekt-właściwość” jako osobna linia, czy jako pojedyncze punkty w wielowymiarowej przestrzeni cech, ale także jako odrębne grupy takich punktów , połączone jednym algorytmem w klaster. W tym przypadku pojawia się pytanie, jak rozumieć odległość między takimi nagromadzeniami punktów (klastrami) i jak ją obliczyć. W tym przypadku różnorodność możliwości jest jeszcze większa niż w przypadku obliczania odległości między dwoma obserwacjami w przestrzeni wielowymiarowej. Procedurę tę komplikuje fakt, że w przeciwieństwie do punktów, klastry zajmują pewną ilość przestrzeni wielowymiarowej i składają się z wielu punktów. W analizie skupień szeroko stosowane są odległości między skupieniami, obliczane na zasadzie najbliższego sąsiada (najbliższego sąsiada), środka ciężkości, najdalszego sąsiada, median. Najczęściej stosowane są cztery metody: pojedynczy link, pełny link, uśredniony link i metoda Warda. W metodzie pojedynczego linku obiekt zostanie dołączony do już istniejącego klastra, jeśli co najmniej jeden z elementów klastra ma ten sam poziom podobieństwa, co dołączany obiekt. W przypadku metody pełnych linków obiekt jest dołączany do klastra tylko wtedy, gdy podobieństwo między kandydatem do włączenia a dowolnym elementem klastra jest nie mniejsze niż określony próg. W przypadku przeciętnego sposobu połączenia istnieje kilka modyfikacji, które są pewnym kompromisem między pojedynczym a pełnym połączeniem. Obliczają średnią wartość podobieństwa kandydata do włączenia do wszystkich obiektów istniejącego klastra. Przywiązanie jest wykonywane, gdy znaleziona średnia wartość podobieństwa osiągnie lub przekroczy określony próg. Najczęściej stosowana jest średnia arytmetyczna podobieństwa między obiektami skupienia a kandydatem do włączenia do skupienia.
Wiele metod grupowania różni się od siebie tym, że ich algorytmy na każdym kroku obliczają różne funkcjonały jakości partycjonowania. Popularna metoda Warda jest skonstruowana w taki sposób, aby zoptymalizować minimalną wariancję odległości wewnątrz klastra. W pierwszym kroku każdy klaster składa się z jednego obiektu, dzięki czemu rozproszenie odległości wewnątrz klastra jest równe 0. Metodą tą łączy się te obiekty, które dają minimalny przyrost rozproszenia, w wyniku czego ta metoda ma tendencję do generować klastry hipersferyczne.
Wielokrotne próby klasyfikacji metod analizy skupień prowadzą do dziesiątek, a nawet setek różnych klas. Taką różnorodność generuje duża liczba możliwych sposobów obliczania odległości między poszczególnymi obserwacjami, nie mniejsza liczba metod obliczania odległości między poszczególnymi skupieniami w procesie grupowania oraz różne szacunki optymalności końcowej struktury skupień.
Najszerzej stosowane w popularnych pakietach statystycznych są dwie grupy algorytmów analizy skupień: hierarchiczne metody aglomeracyjne i iteracyjne metody grupowania.
3. METODY GRUPOWANIA
3. 1 CECHY HIERARCHICZNYCH METOD AGLOMERATYWNYCH
W aglomeracyjnych algorytmach hierarchicznych, które są coraz częściej wykorzystywane w rzeczywistych badaniach biomedycznych, początkowo wszystkie obiekty (obserwacje) traktowane są jako oddzielne, niezależne klastry składające się tylko z jednego elementu. Bez wykorzystania potężnej technologii komputerowej wdrożenie analizy danych klastrowych jest bardzo problematyczne.
Wyboru metryki dokonuje badacz. Po obliczeniu macierzy odległości rozpoczyna się proces aglomeracje (z łac. agglomero - dołączam, gromadzę), przechodząc kolejno krok po kroku. W pierwszym etapie tego procesu dwie początkowe obserwacje (monoklastry) o najmniejszej odległości między nimi są łączone w jedno skupisko, które już składa się z dwóch obiektów (obserwacji). Zatem zamiast dawnych monoklastrów N (składających się z jednego obiektu) po pierwszym kroku pojawią się skupienia N-1, z których jedno skupienie będzie zawierało dwa obiekty (obserwacje), a skupienia N-2 nadal będą składać się z tylko jeden przedmiot. W drugim kroku możliwe są różne metody łączenia klastrów N-2. Dzieje się tak, ponieważ jeden z tych gromad zawiera już dwa obiekty. Z tego powodu pojawiają się dwa główne pytania:
· jak obliczyć współrzędne takiego skupiska dwóch (i dalej więcej niż dwóch) obiektów;
· jak obliczyć odległość do takich „wieloobiektowych” skupisk od „monoklastrów” i pomiędzy „wieloobiektowymi” skupiskami.
Pytania te ostatecznie determinują ostateczną strukturę skupień końcowych (struktura skupień oznacza skład poszczególnych skupień i ich względne położenie w przestrzeni wielowymiarowej). Różne kombinacje metryk i metod obliczania współrzędnych i wzajemnych odległości klastrów powodują zróżnicowanie metod analizy skupień. W drugim kroku, w zależności od wybranych metod obliczania współrzędnych skupienia składającego się z kilku obiektów oraz metody obliczania odległości między skupieniami, możliwe jest albo ponowne połączenie dwóch oddzielnych obserwacji w nowe skupienie, albo połączenie jednego nowego obserwacja do skupiska składającego się z dwóch obiektów. Dla wygody większość programów metod aglomeracyjno-hierarchicznych na końcu pracy może udostępnić dwa główne wykresy do przeglądania. Pierwszy wykres nazywa się dendrogramem (od greckiego dendronu – drzewo), odzwierciedlając proces aglomeracji, scalania poszczególnych obserwacji w jeden końcowy klaster. Podajmy przykład dendrogramu 5 obserwacji w dwóch zmiennych.
Harmonogram1
Oś pionowa takiego wykresu jest osią odległości między skupieniami, a numery obiektów - przypadków użytych w analizie - zaznaczono wzdłuż osi poziomej. Z tego dendrogramu widać, że obiekty nr 1 i nr 2 są najpierw łączone w jedno skupisko, ponieważ odległość między nimi jest najmniejsza i wynosi 1. To połączenie jest pokazane na wykresie za pomocą poziomej linii łączącej pionowe segmenty wychodząc z punktów oznaczonych jako C_1 i C_2. Zwróćmy uwagę na to, że sama linia pozioma przechodzi dokładnie na poziomie odległości między skupieniami równej 1. Dalej, w drugim kroku, obiekt nr 3, oznaczony jako C_3, dołącza do tego skupienia, w skład którego wchodzą już dwa obiekty. Następnym krokiem jest połączenie obiektów #4 i #5, których odległość wynosi 1,41. A w ostatnim kroku skupienie obiektów 1, 2 i 3 łączy się ze skupieniem obiektów 4 i 5. Wykres pokazuje, że odległość między tymi dwoma przedostatnimi skupieniami (ostatnie skupienie obejmuje wszystkie 5 obiektów) jest większa niż 5. , ale mniej niż 6, ponieważ górna pozioma linia łącząca dwa przedostatnie skupiska przebiega na poziomie w przybliżeniu równym 7, a poziom połączenia obiektów 4 i 5 wynosi 1,41.
Poniższy dendrogram został uzyskany poprzez analizę rzeczywistego zbioru danych składającego się z 70 przetworzonych próbki chemiczne, z których każda charakteryzowała się 12 cechami.
Wykres 2
Z wykresu widać, że w ostatnim kroku, kiedy dwa ostatnie klastry łączą się, odległość między nimi wynosi około 200 jednostek. Widać, że gromada pierwsza zawiera znacznie mniej obiektów niż gromada druga, poniżej powiększony fragment dendrogramu, na którym wyraźnie widoczne są liczby obserwacji, oznaczone jako C_65, C_58 itd. (od lewej do prawej): 65, 58, 59, 64, 63, 57, 60, 62, 56, 44, 94 itd.
Wykres 3 Powiększony fragment wykresu #2 powyżej
Widać, że obiekt 44 jest monogromadą, która łączy się z prawą gromadą w przedostatnim kroku, a następnie, w ostatnim kroku, wszystkie obserwacje są łączone w jedną gromadę.
Innym wykresem zbudowanym w takich procedurach jest wykres odległości między skupiskami na każdym etapie łączenia. Poniżej znajduje się podobny wykres dla powyższego dendrogramu.
Wykres 4
W wielu programach możliwe jest wyświetlanie w formie tabelarycznej wyników łączenia obiektów na każdym etapie grupowania. W większości tych tabel, w celu uniknięcia nieporozumień, do oznaczenia początkowych obserwacji stosuje się inną terminologię - monoclusters, oraz rzeczywiste skupienia składające się z dwóch lub więcej obserwacji. W anglojęzycznych pakietach statystycznych obserwacje początkowe (wiersze macierzy danych) oznaczone są jako „przypadek” – przypadek. W celu wykazania zależności struktury klastrów od wyboru metryki i wyboru algorytmu sumy klastrów poniżej przedstawiamy dendrogram odpowiadający algorytmowi pełnego połączenia. I tutaj widzimy, że obiekt #44 jest połączony z resztą zaznaczenia w ostatnim kroku.
Wykres 5
Porównajmy to teraz z innym diagramem uzyskanym metodą pojedynczego łącza na tych samych danych. W przeciwieństwie do metody pełnego połączenia, można zauważyć, że metoda ta generuje długie łańcuchy kolejno dołączanych do siebie obiektów. Jednak we wszystkich trzech przypadkach możemy powiedzieć, że wyróżniają się dwie główne grupy.
Wykres 6
Zwróćmy też uwagę na fakt, że we wszystkich trzech przypadkach obiekt nr 44 łączy się w monoklaster, choć na różnych etapach procesu klastrowania. Wybór takich monoklastrów jest dobrym sposobem wykrywania anomalii, zwanych obserwacjami odstającymi. Usuńmy ten „podejrzany” obiekt nr 44 i ponownie przeprowadźmy grupowanie. Otrzymujemy następujący dendrogram:
Wykres 7
Widać, że zachowany jest efekt „łańcucha”, podobnie jak podział na dwie lokalne grupy obserwacji.
3. 2 CECHY ITERATYWNYCH METOD KLASTROWANIA
Wśród metod iteracyjnych najpopularniejszą metodą jest metoda k-średnich McKeana. W przeciwieństwie do metod hierarchicznych, w większości implementacji tej metody użytkownik musi sam określić żądaną liczbę końcowych klastrów, która jest zwykle oznaczana jako „k”. Podobnie jak w hierarchicznych metodach grupowania, użytkownik może wybrać jeden lub inny rodzaj metryki. Różne algorytmy metody k-średnich różnią się także sposobem doboru początkowych centrów danych skupień. W niektórych wersjach metody użytkownik może (lub musi) sam określić takie punkty początkowe, albo wybierając je z rzeczywistych obserwacji, albo określając współrzędne tych punktów dla każdej ze zmiennych. W innych realizacjach tego sposobu wybór danej liczby k punktów początkowych jest dokonywany losowo, a te punkty początkowe (ziarna klastra) mogą być następnie dopracowywane w kilku etapach. Istnieją 4 główne etapy takich metod:
· wybrać lub przypisać k obserwacji, które będą głównymi centrami klastrów;
· w razie potrzeby klastry pośrednie tworzone są poprzez przyporządkowanie każdej obserwacji do najbliższych określonych centrów klastrów;
· po przypisaniu wszystkich obserwacji do poszczególnych klastrów, pierwotne centra klastrów są zastępowane przez średnie klastrów;
· poprzednia iteracja jest powtarzana, aż zmiany współrzędnych ośrodków klastrowych staną się minimalne.
W niektórych wersjach tej metody użytkownik może ustawić wartość liczbową kryterium, co jest interpretowane jako minimalna odległość wyboru nowych centrów skupień. Obserwacja nie będzie rozpatrywana jako kandydat do nowe centrum klaster, jeśli jego odległość do zastąpionego środka klastra przekracza określoną liczbę. W niektórych programach ten parametr nazywa się „promień”. Oprócz tego parametru możliwe jest również ustalenie maksymalnej liczby iteracji lub osiągnięcie pewnej, zwykle dość małej liczby, z którą porównywana jest zmiana odległości dla wszystkich centrów skupień. To ustawienie jest powszechnie nazywane „zbieżnością”, ponieważ odzwierciedla zbieżność iteracyjnego procesu grupowania. Poniżej przedstawiamy niektóre wyniki, które uzyskano metodą k-średnich McKeana z poprzednimi danymi. Liczbę pożądanych klastrów ustalono początkowo na 3, a następnie na 2. Ich pierwsza część zawiera wyniki jednego czynnika analiza wariancji, w którym numer klastra działa jako czynnik grupujący. Pierwsza kolumna to lista 12 zmiennych, następnie sumy kwadratów (SS) i stopni swobody (df), następnie F-test Fishera, aw ostatniej kolumnie osiągnięty poziom istotności „p”.
Tabela 2 Dane k-średnie McKeana mające zastosowanie do 70 próbek testowych.
|
Zmienne |
|||||||
Jak widać z tej tabeli, hipoteza zerowa o równości średnich w trzech grupach jest odrzucana. Poniżej znajduje się wykres średnich wszystkich zmiennych dla poszczególnych skupień. Te same średnie skupień zmiennych przedstawiono poniżej w formie tabeli.
Tabela 3. Szczegółowy przegląd danych na przykładzie trzech klastrów.
|
Zmienny |
Klaster #1 |
Klaster #2 |
Klaster #3 |
|
Wykres 8
Analiza średnich wartości zmiennych dla każdego skupienia pozwala stwierdzić, że zgodnie z cechą X1 skupienia 1 i 3 mają wartości zbliżone, natomiast skupienie 2 ma średnią wartość znacznie niższą niż w pozostałych dwóch skupieniach. Wręcz przeciwnie, zgodnie z cechą X2 skupienie pierwsze ma najniższą wartość, natomiast skupienia 2 i 3 mają wyższe i zbliżone wartości średnie. Dla cech X3-X12 średnie wartości w skupieniu 1 są istotnie wyższe niż w skupieniach 2 i 3. Poniższa tabela analizy ANOVA wyników skupienia na dwa skupienia wskazuje również na konieczność odrzucenia hipotezy zerowej o równości średnich grupowych dla prawie wszystkich 12 cech, z wyjątkiem zmiennej X4, dla której osiągnięty poziom istotności okazał się powyżej 5%.
Tabela 4. Tabela analizy rozproszenia wyników skupienia na dwa skupienia.
|
Zmienne |
|||||||
Poniżej znajduje się wykres i tabela średnich grupowych dla przypadku grupowania w dwa skupienia.
Tabela 5. Tabela dla przypadku skupienia na dwa skupienia.
|
Zmienne |
Klaster #1 |
Klaster #2 |
|
Wykres 9.
W przypadku, gdy badacz nie jest w stanie z góry określić najbardziej prawdopodobnej liczby skupień, zmuszony jest powtórzyć obliczenia, ustalając inną liczbę, podobnie jak to zrobiono powyżej. A następnie, porównując uzyskane wyniki, zatrzymaj się na jednej z najbardziej akceptowalnych opcji grupowania.
4 . ZESTAWIENIE FUNKCJI
Oprócz grupowania poszczególnych obserwacji istnieją również algorytmy grupowania cech. Jedną z pierwszych takich metod jest metoda plejady korelacji Terentiev P.V. Prymitywne wizerunki takich plejady często można znaleźć w publikacjach biomedycznych w postaci koła usianego strzałkami łączącymi znaki, dla których autorzy znaleźli korelację. Wiele programów do grupowania obiektów i funkcji ma osobne procedury. Np. w pakiecie SAS do grupowania cech stosowana jest procedura VARCLUS (od VARiable - zmienna i CLUSTER - klaster), natomiast analiza skupień obserwacji wykonywana jest innymi procedurami - FASTCLUS i CLUSTER. Konstrukcję dendrogramu w obu przypadkach przeprowadza się za pomocą procedury DRZEWA (drzewa).
W innych pakietach statystycznych dobór elementów do grupowania - obiektów lub cech - dokonywany jest w tym samym module. Jako metrykę dla grupowania cech często stosuje się wyrażenia, które zawierają wartości pewnych współczynników odzwierciedlających siłę związku dla pary cech. W takim przypadku bardzo wygodnie jest, aby znaki o sile połączenia równej jeden (zależność funkcjonalna) przyjmowały odległość między znakami równą zero. Rzeczywiście, przy funkcjonalnym połączeniu, wartość jednej cechy może dokładnie obliczyć wartość innej cechy. Wraz ze spadkiem siły związku między znakami odległość odpowiednio wzrasta. Poniżej znajduje się wykres przedstawiający dendrogram kombinacji 12 cech, które zostały użyte powyżej podczas grupowania 70 próbek analitycznych.
Wykres 10. Dendrogramgrupowanie 12 funkcji.
Jak widać z tego dendrogramu, mamy do czynienia z dwoma lokalnymi grupami cech: X1-X10 i X11-X12.Grupa cech X1-X10 charakteryzuje się dość małą wartością odległości międzyklastrowych, nieprzekraczającą około 100 jednostek. Tutaj również widzimy kilka wewnętrznych sparowanych podgrup: X1 i X2, X3 i X4, X6 i X7. Odległość między cechami tych par, która jest bardzo bliska zeru, wskazuje na ich silny związek par. Natomiast dla pary X11 i X12 wartość odległości między skupiskami jest znacznie większa i wynosi około 300 jednostek. Wreszcie bardzo duża odległość między skupieniami lewym (X1-X10) i prawym (X11-X12), wynosząca około 1150 jednostek, wskazuje, że związek między tymi dwiema grupami cech jest dość minimalny.
5. STABILNOŚĆ I JAKOŚĆ KLASTERINGU
Oczywiście absurdem byłoby postawić pytanie, na ile absolutna jest ta czy inna klasyfikacja uzyskana za pomocą metod analizy skupień. Po zmianie metody grupowania stabilność przejawia się tym, że na dendrogramach dość wyraźnie widoczne są dwa skupienia.
Jako jeden z możliwych sposobów sprawdzenia stabilności wyników analizy skupień można wykorzystać metodę porównywania wyników uzyskanych dla różnych algorytmów klastrowania. Inne sposoby to tak zwana metoda ładowania początkowego zaproponowana przez B. Efrona w 1977 r., metody „scyzoryk” i „sterowanie ślizgowe”. Najprostszym sposobem sprawdzenia stabilności rozwiązania klastrowego może być losowe podzielenie próbki początkowej na dwie w przybliżeniu równe części, zgrupowanie obu części, a następnie porównanie wyników. Bardziej czasochłonny sposób polega na sekwencyjnym wykluczaniu pierwszego obiektu na początku i grupowaniu pozostałych (N-1) obiektów. Ponadto sekwencyjne przeprowadzanie tej procedury z wyjątkiem drugiego, trzeciego itd. obiektów, analizowana jest struktura wszystkich N uzyskanych skupień. Inny algorytm sprawdzania stabilności obejmuje wielokrotne powielanie, powielanie oryginalnej próbki N obiektów, a następnie łączenie wszystkich zduplikowanych próbek w jedną dużą próbkę (populację pseudoogólną) i losowe wyodrębnianie z niej nowej próbki N obiektów. Następnie ta próbka jest grupowana, następnie pobierana jest nowa próbka losowa i ponownie przeprowadzana jest grupowanie itd. Jest też dość pracochłonny.
Nie mniej problemów jest ocena jakości klastrowania. Znanych jest sporo algorytmów optymalizacji rozwiązań klastrowych. Pierwsze prace zawierające sformułowanie kryterium minimalizacji wariancji wewnątrzklastrowej oraz algorytm (typu k-średnich) znajdowania rozwiązania optymalnego pojawiły się w latach 50-tych. W 1963 W artykule J. Warda zaprezentowano również podobny hierarchiczny algorytm optymalizacji. Nie ma uniwersalnego kryterium optymalizacji rozwiązania klastrowego. Wszystko to utrudnia badaczowi wybór optymalnego rozwiązania. W takiej sytuacji w najlepszy możliwy sposób stwierdzenie, że znalezione rozwiązanie skupień jest optymalne na tym etapie badań, jest jedynie zgodnością tego rozwiązania z wnioskami uzyskanymi przy użyciu innych metod statystyki wielowymiarowej.
Na korzyść wniosku o optymalności grupowania przemawiają również pozytywne wyniki sprawdzania momentów predykcyjnych uzyskanego rozwiązania już na innych obiektach badań. Stosując hierarchiczne metody analizy skupień, możemy polecić porównanie kilku wykresów ze sobą przyrostowych zmian odległość między klastrami. W takim przypadku preferowana powinna być opcja, dla której obserwuje się płaską linię takiego przyrostu od pierwszego kroku do kilku przedostatnich kroków z ostrym pionowym wzrostem na tym wykresie w ostatnich 1-2 krokach grupowania.
WNIOSKI
W swojej pracy starałem się pokazać nie tylko złożoność tego typu analiz, ale także optymalne możliwości przetwarzania danych, bo często dla dokładności wyników trzeba użyć od kilkudziesięciu do kilkuset próbek. Ten typ analiza pomaga klasyfikować i przetwarzać wyniki. Nie bez znaczenia uważam również akceptowalność technologii komputerowych w tej analizie, co pozwala na zmniejszenie czasochłonności procesu przetwarzania wyników, a tym samym na zwrócenie większej uwagi na poprawność pobierania próbek do analizy.
W zastosowaniu analizy skupień są takie subtelności i szczegóły, które pojawiają się w poszczególnych konkretnych przypadkach i nie są od razu widoczne. Na przykład rola skali cech może być minimalna, aw niektórych przypadkach może dominować. W takich przypadkach konieczne jest zastosowanie przekształceń zmiennych. Jest to szczególnie skuteczne w przypadku korzystania z metod, które generują nieliniowe przekształcenia cech, które generalnie zwiększają ogólny poziom korelacji między cechami.
Jeszcze większą swoistością jest wykorzystanie analizy skupień w odniesieniu do obiektów, które opisują wyłącznie cechy jakościowe. W tym przypadku całkiem udane są metody wstępnej digitalizacji cech jakościowych i analizy skupień z nowymi cechami. W swojej pracy pokazałem, że analiza skupień dostarcza wielu nowych i oryginalnych informacji zarówno w przypadku jej zastosowania w wystarczająco przebadanych systemach, jak i w badaniu systemów o nieznanej strukturze.
Należy również zauważyć, że analiza skupień stała się niezbędna w badaniach ewolucyjnych, pozwalając na konstruowanie drzew filogenetycznych pokazujących ścieżki ewolucyjne. Metody te są szeroko stosowane w programach badania naukowe w chemii fizycznej i analitycznej.
BIBLIOGRAFIA
1) Aivazyan S.A., Enyukov I.S., Meshalkin L.D. O strukturze i zawartości pakietu oprogramowania do stosowanej analizy statystycznej//Algorytmiczne i oprogramowanie zastosowana analiza statystyczna. — M., 1980.
2) Ayvazyan S. A., Bezhaeva Z. I., Staroverov O. V. Klasyfikacja obserwacji wielowymiarowych.--M .: Statistics, 1974.
3) Becker V. A., Lukatskaya M. L. O analizie struktury macierzy współczynników sprzężenia//Zagadnienia modelowania ekonomicznego i statystycznego oraz prognozowania w przemyśle.-- Nowosybirsk, 1970.
4) Braverman E.M., Muchnik I.B. Metody strukturalne przetwarzanie danych.--M.: Nauka, 1983.
5) Voronin Yu A. Teoria klasyfikacji i jej zastosowania.--Nowosybirsk: Nauka, 1987.
6) Good I.J. Botryology of botryology//Classification and cluster.--M.: Mir, 1980.
7) Dubrovsky S.A. Zastosowana wielowymiarowa analiza statystyczna.--M.: Finanse i statystyka, 1982.
8) Duran N., Odell P. Analiza skupień. — M.: Statistics, 1977.
9) Eliseeva II, Rukavishnikov VS Grupowanie, korelacja, rozpoznawanie wzorców.--M.: Statistics, 1977.
10) Zagoruiko N. G. Metody rozpoznawania i ich zastosowanie.--M .: Radio sowieckie, 1972.
11) Zade L. A. Zbiory rozmyte i ich zastosowanie w rozpoznawaniu wzorców i analizie skupień//Klasyfikacja i skupienia.--M.: Mir, 1980.
12) Kildiszew G.S., Abolentsev Yu.I. Wielowymiarowe ugrupowania.--M.: Statistics, 1978.
13) Raiskaya II, Gostilin NI, Frenkel AA O jednym ze sposobów sprawdzania zasadności podziału w analizie skupień.//Zastosowanie wielowymiarowej analizy statystycznej w ekonomii i ocenie jakości produktu.--Rozdz. P. Tartu, 1977.
14) Shurygin A. M. Dystrybucja odległości i różnic między punktami // Oprogramowanie i wsparcie algorytmiczne dla stosowanej wielowymiarowej analizy statystycznej.--M., 1983.
15) Eeremaa R. Ogólna teoria projektowania systemów klastrowych i algorytmy znajdowania ich reprezentacji liczbowych: Proceedings of the Computing Center of TSU.--Tartu, 1978.
16) Yastremsky BS Selected Works.--M.: Statistics, 1964.
Podobne dokumenty
Cele segmentacji rynku w działania marketingowe. Istota analizy skupień, główne etapy jej realizacji. Wybierz sposób pomiaru odległości lub miary podobieństwa. Hierarchiczne, niehierarchiczne metody grupowania. Ocena niezawodności i niezawodności.
raport, dodany 02.11.2009
Główna charakterystyka kondycja finansowa przedsiębiorstw. Kryzys w przedsiębiorstwie, jego przyczyny, rodzaje i konsekwencje. Nowoczesne metody oraz narzędzia analizy skupień, cechy ich wykorzystania do oceny finansowo-ekonomicznej przedsiębiorstwa.
praca dyplomowa, dodana 10.09.2013
Przeprowadź analizę klastrową przedsiębiorstw za pomocą Statgraphics Plus. Budowa równania regresji liniowej. Obliczanie współczynników sprężystości za pomocą modeli regresji. Ocena istotności statystycznej równania i współczynnika determinacji.
zadanie, dodane 16.03.2014
Konstrukcja regresji typologicznych dla poszczególnych grup obserwacji. Dane przestrzenne i informacje czasowe. Zakres zastosowania analizy skupień. Pojęcie jednorodności obiektów, własności macierzy odległości. Przeprowadzanie regresji typologicznej.
prezentacja, dodano 26.10.2013
Tworzenie połączonych modeli i metod jak nowoczesny sposób prognozowanie. Model oparty na ARIMA do opisu stacjonarnych i niestacjonarnych szeregów czasowych w rozwiązywaniu problemów klastrowania. Autoregresywne modele AR i zastosowanie korelogramów.
prezentacja, dodana 05.01.2015
Charakterystyka różnych rodzajów metryk. Metoda najbliższego sąsiada i jej uogólnienia. Algorytm najbliższego sąsiada. Metoda okna Parzena. Uogólniony klasyfikator metryczny. Problem wyboru metryki. Manhattan i odległość euklidesowa. miara cosinus.
praca semestralna, dodana 03.08.2015
Charakterystyka branży budowlanej Terytorium Krasnodarskiego. Prognoza rozwoju budownictwa mieszkaniowego. Nowoczesne metody i narzędzia analizy skupień. Wielowymiarowe metody statystyczne diagnozowania stanu ekonomicznego przedsiębiorstwa.
praca dyplomowa, dodana 20.07.2015 r.
Charakterystyka kredytów hipotecznych na przykładzie obwodu briańska. Przegląd matematycznych metod podejmowania decyzji: oceny eksperckie, porównania sekwencyjne i parami, analiza hierarchiczna. Opracowanie programu wyszukiwania optymalnego kredytu hipotecznego.
praca semestralna, dodana 29.11.2012
Obszary zastosowania analizy systemowej, jej miejsce, rola, cele i funkcje w nowoczesna nauka. Pojęcie i treść metod analizy systemowej, jej metody nieformalne. Cechy heurystycznych i eksperckich metod badawczych oraz cechy ich zastosowania.
praca semestralna, dodana 20.05.2013
Opracowywanie i badanie metod ekonometrycznych z uwzględnieniem specyfiki danych ekonomicznych i zgodnie z potrzebami Ekonomia i praktyki. Zastosowanie metod i modeli ekonometrycznych do statystycznej analizy danych ekonomicznych.
Uniwersytet: VZFEI
Rok i miasto: Moskwa 2008
1. Wstęp. Pojęcie metody analizy skupień.
2. Opis metodyki zastosowania analizy skupień. Kontrolny przykład rozwiązywania problemów.
4. Lista wykorzystanej literatury
- Wstęp. Pojęcie metody analizy skupień.
Analiza skupień to zestaw metod pozwalających na klasyfikację obserwacji wielowymiarowych, z których każda opisana jest zbiorem cech (parametrów) X1, X2, ..., Xk.
Celem analizy skupień jest tworzenie grup obiektów podobnych do siebie, które potocznie nazywane są skupieniami (klasa, takson, koncentracja).
Analiza skupień jest jednym z obszarów badań statystycznych. Zajmuje szczególnie ważne miejsce w tych dziedzinach nauki, które związane są z badaniem zjawisk i procesów masowych. Konieczność rozwijania metod analizy skupień i ich wykorzystania jest podyktowana tym, że pomagają one budować klasyfikacje oparte na naukach, identyfikować komunikacja wewnętrzna pomiędzy jednostkami obserwowanej populacji. Ponadto metody analizy skupień mogą służyć do kompresji informacji, co jest istotnym czynnikiem w obliczu stałego wzrostu i złożoności przepływów danych statystycznych.
Metody analizy skupień pozwalają na rozwiązanie następujących problemów:
Dokonywanie klasyfikacji obiektów z uwzględnieniem cech, które odzwierciedlają istotę, charakter obiektów. Rozwiązanie takiego problemu prowadzi z reguły do pogłębienia wiedzy o całości klasyfikowanych obiektów;
Sprawdzenie przyjętych założeń o obecności jakiejś struktury w badanym zbiorze obiektów, tj. wyszukaj istniejącą strukturę;
Konstruowanie nowych klasyfikacji dla słabo zbadanych zjawisk, gdy konieczne jest ustalenie obecności powiązań w populacji i próba wprowadzenia do niej struktury (1. s. 85-86).
2. Opis metodyki zastosowania analizy skupień. Kontrolny przykład rozwiązywania problemów.
Analiza skupień pozwala na dokonanie podziału na grupy jednorodne (skupienia) z n obiektów charakteryzujących się k cechami. Jednorodność obiektów określa odległość p(xi xj), gdzie xi = (xi1, …., xik) i xj= (xj1,…,xjk) to wektory składające się z wartości k atrybutów i odpowiednio -ty i j-ty obiekt.
Dla obiektów charakteryzujących się cechami liczbowymi odległość określa się wzorem:
p(xi , xj) = √ ∑(x1m-xjm) 2 (1)*
Obiekty są uważane za jednorodne, jeśli p(xi xj)< p предельного.
Graficzną reprezentację unii można uzyskać za pomocą drzewa unii klastrów - dendrogramu. (2. Rozdział 39).
Przypadek testowy (przykład 92).
|
Wielkość sprzedaży |
|||||
Sklasyfikujmy te obiekty stosując zasadę „bliskiego sąsiada”. Znajdźmy odległości między obiektami za pomocą wzoru (1)* . Wypełnijmy tabelę.
Wyjaśnijmy, w jaki sposób stół jest wypełniony.
Na przecięciu wiersza i i kolumny j wskazana jest odległość p(xi xj) (wynik jest zaokrąglany do dwóch miejsc po przecinku).
Na przykład na przecięciu rzędu 1 i kolumny 3 wskazana jest odległość p(x1, x3) = √(1-6) 2 +(9-8) 2 ≈ 5.10, a na przecięciu rzędu 3 i kolumny 5, odległość p(x3 , x5) = √ (6-12) 2 + (8-7) 2 ≈ 6,08. Ponieważ p(xi, xj) = p(xj,xi), dolna część tabeli nie musi być wypełniona.
Zastosujmy zasadę „bliskiego sąsiada”. W tabeli znajdujemy najmniejszą z odległości (jeśli jest ich kilka, to wybieramy którąkolwiek z nich). To jest p 1,2 ≈ p 4,5 \u003d 2,24. Niech p min = p 4,5 = 2,24. Następnie możemy połączyć obiekty 4 i 5 w jedną grupę, to znaczy, że połączona kolumna 4 i 5 będzie zawierać najmniejszą z odpowiednich liczb kolumn 4 i 5 oryginalnej tabeli odległości. To samo robimy z liniami 4 i 5. Otrzymujemy nową tabelę.
W wynikowej tabeli znajdujemy najmniejszą z odległości (jeśli jest ich kilka, wybierzemy dowolną z nich): р min = р 1,2 = 2,24. Następnie możemy połączyć obiekty 1,2,3 w jedną grupę, to znaczy połączona kolumna 1,2,3 będzie zawierać najmniejszą z odpowiednich liczb kolumn 1 i 2 i 3 z poprzedniej tabeli odległości. To samo robimy z wierszami 1, 2 i 3. Otrzymujemy nową tabelę.
Otrzymaliśmy dwa klastry: (1,2,3) i (4,5).
3. Rozwiązywanie problemów do pracy kontrolnej.
Problem 85.
Semestry: Pięć zakładów produkcyjnych charakteryzuje dwie cechy: wielkość sprzedaży oraz średni roczny koszt środków trwałych.
|
Wielkość sprzedaży |
|||||
|
Średni roczny koszt trwały majątek produkcyjny, |
Rozwiązanie: Znajdźmy odległości między obiektami za pomocą wzoru (1)* (zaokrąglimy do dwóch miejsc po przecinku):
p 1,1 \u003d √ (2-2) 2 + (2-2) 2 \u003d 0
p 1,2 \u003d √ (2-5) 2 + (7-9) 2 ≈ 3,61
p 1,3 \u003d √ (2-7) 2 + (7-10) 2 ≈ 5,83
p 2,2 \u003d √ (5-5) 2 + (9-9) 2 \u003d 0
p 2,3 \u003d √ (5-7) 2 + (9-10) 2 ≈ 2,24
p 3,4 \u003d √ (7-12) 2 + (10-8) 2 ≈5,39
p 3,5 \u003d √ (7-13) 2 + (10-5) 2 ≈ 7,81
p 4,5 \u003d √ (12-13) 2 + (8-5) 2 ≈ 3,16
Na podstawie wyników obliczeń wypełniamy tabelę:
Zastosujmy zasadę najbliższego sąsiada. Aby to zrobić, w tabeli znajdujemy najmniejszą z odległości (jeśli jest ich kilka, wybierz dowolną z nich). To jest p 2,3 = 2,24. Niech p min = p 2,3 = 2,24, wtedy możemy łączyć obiekty kolumn „2” i „3”, a także łączyć wiersze obiektów „2” i „3”. W nowej tabeli wpisujemy najmniejsze wartości z oryginalnej tabeli do połączonych grup.
W nowej tabeli znajdujemy najmniejszą z odległości (jeśli jest ich kilka, to wybieramy którąkolwiek z nich). To jest p 4,5=3,16. Niech p min = p 4,5 = 3,16, wtedy możemy łączyć obiekty kolumn „4” i „5”, a także łączyć wiersze obiektów „4” i „5”. W nowej tabeli wpisujemy najmniejsze wartości z oryginalnej tabeli do połączonych grup.
W nowej tabeli znajdujemy najmniejszą z odległości (jeśli jest ich kilka, to wybieramy którąkolwiek z nich). Są to p 1, 2 i 3=3,61. Niech p min = p 1, 2 i 3 = 3,61, wtedy możemy scalić obiekty kolumn „1” i „2 i 3”, a także scalić wiersze. W nowej tabeli wpisujemy najmniejsze wartości z oryginalnej tabeli do połączonych grup.
Otrzymujemy dwa klastry: (1,2,3) i (4,5).
Dendrogram pokazuje kolejność doboru elementów i odpowiadające im odległości minimalne pmin.
Odpowiadać: W wyniku analizy skupień zgodnie z zasadą „najbliższego sąsiada” powstają 2 podobne do siebie skupienia obiektów: (1,2,3) i (4,5).
Problem 211.
Semestry: Pięć zakładów produkcyjnych charakteryzuje dwie cechy: wielkość sprzedaży oraz średnioroczna wartość środków trwałych.
|
Wielkość sprzedaży |
|||||
|
Średni roczny koszt środków trwałych produkcyjnych |
Klasyfikuj te obiekty, stosując zasadę najbliższego sąsiada.
Rozwiązanie: Aby rozwiązać problem, przedstawiamy dane w oryginalnej tabeli. Określmy odległości między obiektami. Sklasyfikujemy obiekty zgodnie z zasadą „najbliższego sąsiada”. Wyniki przedstawiono w formie dendrogramu.
|
Wielkość sprzedaży |
|||||
|
Średni roczny koszt środków trwałych produkcyjnych |
Korzystając ze wzoru (1)*, obliczamy odległości między obiektami:
p 1,1 = 0, p 1,2 = 6, p 1,3 = 8,60, p 1,4 = 6,32, p 1,5 = 6,71, p 2,2 = 0, p 2,3 = 7,07, p 2,4 = 2, p 2,5 = 3,32, p 3,3 = 0, p 3,4 = 5,10, p 3,5 = 4,12, p 4 ,4=0, p4,5=1, p5,5=0.
Wyniki przedstawiono w tabeli:
Najmniejsza wartość odległości w tabeli to p 4,5=1. Niech p min = p 4,5 = 1, wtedy możemy łączyć obiekty kolumn „4” i „5”, a także łączyć wiersze obiektów „4” i „5”. W nowej tabeli wpisujemy najmniejsze wartości z oryginalnej tabeli do połączonych grup.
Najmniejsza wartość odległości w nowej tabeli to p 2, 4 i 5=2. Niech p min = p 2, 4 i 5=2, to możemy łączyć obiekty kolumn „4 i 5” i „3”, a także łączyć wiersze obiektów „4 i 5” i „3”. W nowej tabeli wpisujemy najmniejsze wartości z tabeli do połączonych grup.
Najmniejsza wartość odległości w nowej tabeli to p 3,4,5=2. Niech p min = p 3,4,5=2, to możemy łączyć obiekty kolumn „3,4,5” i „2”, a także łączyć wiersze obiektów „3,4,5” i „ 2". W nowej tabeli wpisujemy najmniejsze wartości z tabeli do połączonych grup.
| lub zaloguj się do serwisu. |
Zobacz ANALIZA KLASTRA. Antynazi. Encyklopedia Socjologii, 2009 ... Encyklopedia Socjologii
analiza skupień- jest to zestaw metod pozwalających na klasyfikację obserwacji wielowymiarowych, z których każda jest opisana pewnym zestawem zmiennych. Celem analizy skupień jest tworzenie grup obiektów podobnych do siebie, które potocznie nazywane są ... ... Słownik socjologiczny Socium
analiza skupień- matematyczna procedura analizy wielowymiarowej, która pozwala na podstawie zestawu wskaźników charakteryzujących szereg obiektów (np. przedmiotów) pogrupować je w klasy (klastry) tak, aby obiektów zawartych w jednej klasie było więcej. ... ... Wielka Encyklopedia Psychologiczna
Analiza skupień- procedura matematyczna, która pozwala, w oparciu o podobieństwo wartości ilościowych kilku cech charakterystycznych dla każdego obiektu (na przykład podmiotu) dowolnego zestawu, pogrupować te obiekty w określone klasy lub klastry... . ... Słownik psychologiczny
analiza skupień- - [L.G. Sumenko. Angielsko-rosyjski słownik technologii informacyjnych. M.: GP TsNIIS, 2003.] Tematy Technologia informacyjna ogólnie analiza klastrowa EN … Podręcznik tłumacza technicznego
analiza skupień- * analiza skupień * analiza skupień lub grupowanie danych to wielowymiarowa procedura statystyczna, która gromadzi dane zawierające informacje o wybranych obiektach, a następnie układa obiekty w stosunkowo jednorodne grupy skupień (Q ... ... Genetyka. słownik encyklopedyczny
analiza skupień- Czy pożądane jest poprawienie tego artykułu z matematyki?: Wstawianie przypisów, dokładniejsze wskazywanie źródeł. Popraw artykuł zgodnie z zasadami stylistycznymi Wikipedii. Recykling ... Wikipedia
ANALIZA KLASTRA- - matematyczna procedura analizy wielowymiarowej, która pozwala na podstawie zestawu wskaźników charakteryzujących szereg obiektów (np. przedmiotów) grupować je w klasy (zgrupowania), tak aby obiekty zawarte w jednej klasie były jeszcze ... ... Encyklopedyczny słownik psychologii i pedagogiki
ANALIZA KLASTRA - Nazwa zwyczajowa dla różnych matematycznych metod określania głębokiej struktury w złożonych danych. Analiza skupień jest pod wieloma względami podobna do analizy czynnikowej. Obydwa polegają na poszukiwaniu jednolitych elementów (czynników lub klastrów), które... ... Wyjaśniający słownik psychologii
ANALIZA KLASTRA- (analiza skupień) technika stosowana do identyfikacji grup obiektów lub osób, które mogą wykazywać względną różnicę w zestawie danych. Następnie badane są cechy takich osób w każdej grupie. W badaniach rynku ... ... Duży objaśniający słownik socjologiczny
ANALIZA KLASTRA- (ANALIZA KLASTRA) Grupa technik statystycznych wykorzystywanych do określenia wewnętrznej struktury danych w analizie informacji badawczych dotyczących wielu zmiennych. Celem analizy skupień jest identyfikacja grup obiektów ... ... słownik socjologiczny
Książka ta poświęcona jest tylko jednemu z najbardziej obiecujących podejść do analizy wielowymiarowych procesów i zjawisk w tym sensie - analizie skupień.
Analiza skupień to sposób grupowania obiektów wielowymiarowych, polegający na prezentacji wyników poszczególnych obserwacji przez punkty o odpowiedniej przestrzeni geometrycznej, a następnie selekcji grup jako „kęp” tych punktów. Właściwie „klaster” (klaster) w język angielski i oznacza „skrzep”, „kiść (winogrona)”, „grono (gwiazd)” itp. Termin ten niezwykle dobrze pasuje do terminologii naukowej, ponieważ jego pierwsza sylaba odpowiada tradycyjnemu terminowi „klasa”, a druga, niejako wskazuje na jego sztuczne pochodzenie. Nie mamy wątpliwości, że terminologia analizy skupień zastąpi wszystkie konstrukty stosowane wcześniej w tym celu (nienadzorowane rozpoznawanie wzorców, stratyfikacja, taksonomia, automatyczna klasyfikacja itp.). Potencjalne możliwości analizy skupień są oczywiste dla rozwiązania np. problemów identyfikacji grup przedsiębiorstw działających w podobnych warunkach lub z podobnymi wynikami, jednorodnych grup ludności w różnych aspektach życia czy stylu życia w ogóle itp.
Jako kierunek naukowy analiza skupień zadeklarowała się w połowie lat 60. i od tego czasu dynamicznie się rozwija, będąc jedną z gałęzi najintensywniejszego rozwoju nauk statystycznych. Dość powiedzieć, że tylko liczba monografii dotyczących analizy skupień opublikowanych do tej pory w różnych krajach mierzona jest w setkach (podczas gdy powiedzmy, zgodnie z tak „zasłużoną” metodą wielowymiarowej analizy statystycznej, jak Analiza czynników, trudno zliczyć kilkadziesiąt książek). I to jest całkiem zrozumiałe. Przecież tak naprawdę mówimy o modelowaniu operacji grupowania, jednej z najważniejszych nie tylko w statystyce, ale w ogóle - zarówno w poznaniu, jak iw podejmowaniu decyzji.
W naszym kraju ukazało się szereg monografii poświęconych badaniu konkretnych problemów społeczno-gospodarczych z wykorzystaniem analizy skupień (1), metodologii wykorzystania analizy skupień w badaniach społeczno-gospodarczych (2), metodologii analizy skupień jako takiej ( 3) (Podstawy analizy statystycznej)
Proponowana książka I.D. Mandela jest niejako prostopadła do tej klasyfikacji: jej treść wiąże się z każdym z tych trzech obszarów.
Celem książki jest podsumowanie najnowocześniejszy analiza klastrów, analiza możliwości jej wykorzystania i zadań dalszego rozwoju. Ta idea sama w sobie musi budzić szacunek: bezstronna analiza i uogólnianie wymagają dużo pracy, erudycji, odwagi i są oceniane przez społeczność naukową znacznie niżej niż promocja i rozwój własnych projektów. (Książka zawiera jednak również oryginalne opracowania autora dotyczące analizy „intensjonalnej” i dualizmu klasyfikacji.)
Z realizacją tego celu wiążą się zarówno zalety książki, jak i jej wady. Zalety powinny obejmować:
· badanie metodologiczne pojęć jednorodności, grupowania i klasyfikacji z uwzględnieniem wielowymiarowości zjawisk i procesów;
· systematyczny przegląd podejść i metod analizy skupień (w tym do 150 konkretnych algorytmów);
· prezentacja technologii i wyników eksperymentalnego porównania procedur analizy skupień; Książka ta poświęcona jest tylko jednemu z najbardziej obiecujących podejść do analizy wielowymiarowych procesów i zjawisk w tym sensie - analizie skupień.
Analiza skupień to sposób grupowania obiektów wielowymiarowych, polegający na prezentacji wyników poszczególnych obserwacji przez punkty o odpowiedniej przestrzeni geometrycznej, a następnie selekcji grup jako „kęp” tych punktów. W rzeczywistości „cluster” (cluster) w języku angielskim oznacza „skrzep”, „kiść (winogrona)”, „gromada (gwiazd)” itp. Termin ten niezwykle dobrze pasuje do terminologii naukowej, ponieważ jego pierwsza sylaba odpowiada tradycyjnej termin „klasa”, a drugi niejako wskazuje na jego sztuczne pochodzenie. Nie mamy wątpliwości, że terminologia analizy skupień zastąpi wszystkie konstrukty stosowane wcześniej w tym celu (nienadzorowane rozpoznawanie wzorców, stratyfikacja, taksonomia, automatyczna klasyfikacja itp.). Potencjalne możliwości analizy skupień są oczywiste dla rozwiązania np. problemów identyfikacji grup przedsiębiorstw działających w podobnych warunkach lub z podobnymi wynikami, jednorodnych grup ludności w różnych aspektach życia czy stylu życia w ogóle itp.
Jako kierunek naukowy analiza skupień zadeklarowała się w połowie lat 60. i od tego czasu dynamicznie się rozwija, będąc jedną z gałęzi najintensywniejszego rozwoju nauk statystycznych. Dość powiedzieć, że tylko szereg monografii dotyczących analizy skupień, rozwoju schematy ogólne wykorzystanie metod analizy skupień zaimplementowanych w dość obrazowych tabelach; rekomendacyjny charakter prezentacji.
Te zalety decydują o samodzielnym miejscu księgi I.D. Mandela wśród innych publikacji.
Mankamentami książki są niejednoznaczność niektórych rekomendacji oraz brak systematycznej analizy problematyki wykorzystania metod analizy skupień w przedmiotowych zastosowaniach społeczno-gospodarczych. To ostatnie wynika wprawdzie z niedostatecznego wykorzystania analizy skupień w tym obszarze.
Książka stanowi odskocznię, której użycie ułatwia postęp w najtrudniejszym zagadnieniu każdej teorii - praktyczne wykorzystanie narzędzi, które dostarcza.
B. G. Mirkin
Tematyka badań obejmuje zarówno analizę morfologii zmumifikowanych gryzoni w Nowej Gwinei, jak i badanie wyników głosowania senatorów USA, od analizy funkcji behawioralnych zamrożonych karaluchów podczas ich rozmrażania, po badanie rozmieszczenia geograficznego niektórych rodzajów porostów w Saskatchewan.
Ta eksplozja publikacji miała ogromny wpływ na rozwój i zastosowanie analizy skupień. Ale niestety są też strony negatywne. Szybki wzrost publikacji dotyczących analizy skupień doprowadził do powstania ugrupowań użytkowników, a w konsekwencji do powstania żargonu używanego wyłącznie przez ugrupowania, które je stworzyły (Blashfield i Aldenderfer, 1978; Blashfield, 1980).
O tworzeniu żargonu przez specjalistów w tej dziedzinie nauki społeczneświadczy na przykład zróżnicowana terminologia odnosząca się do metody Warda. W literaturze inaczej nazywana jest „metoda Warda”. Znane są co najmniej cztery kolejne jej nazwy: "metoda minimalnej wariancji", "metoda sumy kwadratów błędów", "minimalizacja grupowania hierarchicznego" i "HGROUP". Dwie pierwsze nazwy odnoszą się po prostu do kryterium, którego optimum określa metoda Warda, natomiast trzecia odnosi się do sumy kwadratów błędów, która jest monotonicznym przekształceniem śladowym macierzy W, wewnątrzgrupowej macierzy kowariancji. Wreszcie powszechnie używana nazwa „HGROUP” to nazwa popularnej program komputerowy, który implementuje metodę Warda (Veldman, 1967).
Kształtowanie się żargonu utrudnia rozwój powiązań interdyscyplinarnych, utrudnia skuteczne porównanie metodologia i wyniki zastosowania analizy skupień w różnych dziedzinach nauki prowadzi do niepotrzebnego wysiłku (ponowne wymyślanie tych samych algorytmów) i ostatecznie nie daje nowym użytkownikom głębokiego zrozumienia wybranych przez nich metod (Blashfield i Aldenderfer, 1978). ). Na przykład w jednym badaniu nauk społecznych (Rogers i Linden, 1973) porównano trzy różne metody grupowania przy użyciu tych samych danych. Nazwali te metody następująco: „grupowanie hierarchiczne”, „grupowanie hierarchiczne lub HCG” i „analiza skupień”. I żadna z tych nazw nie była znana metodom grupowania. Początkujący użytkownik programów do analizy skupień będzie zdezorientowany wszystkimi istniejącymi nazwami i nie będzie w stanie powiązać ich z innymi opisami metod grupowania. Doświadczeni użytkownicy znajdą się w trudnej sytuacji, porównując swoje badania z podobną pracą. Możemy posuwać się do skrajności, ale żargon to poważny problem.
W ostatnich latach rozwój analizy skupień nieco spowolnił, sądząc po liczbie publikacji i liczbie dyscyplin, w których ta metoda jest stosowana. Można powiedzieć, że obecnie psychologia, socjologia, biologia, statystyka i niektóre dyscypliny techniczne wejść w fazę konsolidacji w związku z analizą klastrową.
Liczba artykułów chwalących walory analizy skupień sukcesywnie spada. Jednocześnie pojawia się coraz więcej prac, w których na danych kontrolnych porównuje się stosowalność różnych metod grupowania. W literaturze więcej uwagi poświęcono aplikacjom. Wiele badań ma na celu opracowanie praktycznych mierników sprawdzających trafność wyników uzyskanych za pomocą analizy skupień. Wszystko to świadczy o poważnych próbach stworzenia sensownej statystycznej teorii metod grupowania.
