81081 P3200141

210 4. Analiza skupień

Naszą uwagę będziemy koncentrowali przede wszystkim na podstawowym celu analizy skupień. Wykrywanie grup, czyli jednorodnych podzbiorów obiektów, napotyka jednak pewne szczególne problemy, a zasadniczym jest brak zadowalającej definicji tego czym jest grupa. Z tego powodu większość technik grupowania nie może być sformalizowana w postaci właściwego modelu, tak jak to ma miejsce w przypadku analizy czynnikowej lub analizy głównych składowych (zob. 0’Miurcheartaigh i Payne, 1977). Zagadnienie definicji jest oczywiście z wielu względów istotne i znalazło swój wyraz w licznych publikacjach¹, choć dla poznania podstawowej idei i technik grupowania można je pomijać i używać terminu grupa lub klasa lub też skupienie w intuicyjnym sensie jako zbioru podobnych obiektów. Podane wcześniej wyjaśnienia niewiele oczywiście mówią,jak przyporządkowywać p-wymiarowe obserwacje do grup. Ogólnie powiada się, że grupy powinno się tworzyć tak, aby były one w pewnym sensie odległe. Można to rozumieć w ten sposób, że różnice między obserwacjami należącymi do tej samej grupy powinny być małe, natomiast różnice między obserwacjami należącymi do różnych grup powinny być duże.

Można by zatem sformułować dwa postulaty pod adresem grup (zob. Gordon, 1981): postulat wewnętrznej spójności (ang. intemal cohesion) i postulat zewnętrznej izolacji (ang. extemal isolation). Cytowany autor ilustruje tę koncepcję geometrycznie. w sposób ukazany na rysunku 4.1.

(a)

(b)

(C)

Rysunek 4.1. Ilustracja koncepcji spójności i izolacji grup

(a) grupy są spójne i izolowane, (b) grupy są izolowane, lecz nie są spójne, (c) grupy spójne są połączone przez punkty pośredniczące Źródło: Gordon, 1981

Johnson i Wichem (1992) twierdzą, że w większości zastosowań analizy skupień badacz dostatecznie dobrze zna problem, aby odróżnić „dobre” grupowanie do grupowania „złego". Dlaczego więc - zadają oni zasadniczo retoryczne pytanie - nie wyliczyć wszystkich możliwych ugrupowań i wybrać najlepsze do dalszych

badań? Negatywna odpowiedź wynika z rozważań kombinatorycznych. Łączna liczba możliwych podziałów jest bardzo duża i jest równa liczbie Slirlinga dru-

giego rodzaju²

(4.

/

gdzienjest liczbą grupowanych obiektów w K niepustych skupieniach, przy czym

A = l, 2,..., n.

Powoduje to, że praktyczna możliwość wyliczenia możliwych do otrzymania grup obiektów jest niewielka. Grupowanie tylko n = 20 obiektów w K= 4

rozłączne grupy daje ponad 4,5-10'° różnych ugrupowań, zaś podwojenie liczby obiektów (n = 40) i liczby grup (K = 8) da już około 1,3- 10^k ugrupowań czyli

około 2,9 • 10²⁷ razy więcej. Pewne techniki grupowania są zatem potrzebne

Liczba technik klasyfikacji wchodzących w zakres analizy skupień jest ogromna. Już samo ich systematyzowanie według przeróżnych kryteriów stano wić może odrębny przedmiot badań naukowych Odsyłamy zatem czytelnika do opracowań, w których ów wątek został obszernie potraktowali\ (np Harligan 1975; Kowalewski, 1994; Pociecha i in„ 1988; Nowak, 1990, Marek i Noworol. 1987; Jajuga, 1993). Tutaj najogólniej scharakteryzujemy dwa podstawowe typy grupowania; podział oraz hierarchię.

Przez podział (ang. partition) P_K = (C, ,C,,C_K] należy rozumieć rozdzielenie zbioru obiektów Q na K podzbiorów, zwanych skupieniami (ang. clusiers), spełniających następujące warunki:

a) C, *0dla£ = l,2.....K,

b) C_g D C_h = 0 dla g, h = 1, 2,..., K oraz g & h,

Oznacza to, że: (a) żadne skupienie nie może być podzbiorem pustyni, (b) skupienia są rozłączne, czyli nic mają wspólnych elementów (ich iloczyn jest zbiorem pustym) oraz (c) podział na skupienia wyczerpuje cały wyjściowy zbiór Q grupowanych obiektów (tzw. warunek adekwatności).

Można wyróżniać także inne typy grupowania o charakterze podziału, w których skupienia nie są rozłączne lub nie w yczerpują całego zbioru obiektów.

Przez hierarchię (ang. hierarchy) będziemy rozumieli zbiór H = (P, ,P₂.....P_u}

u < n podziałów zbioru obiektów Q, przy czym zbiór podziałów jest taki, iż relacje C_f £ P_k,C_h EP, oraz k > l implikują, żeC^ CC,, lubC^ DC* = Odia wszystkich g,h& g, k,l = 1,2,.... n. W zakresie grupowania hierarchicznego wyróżnia się

1

N^rp. R.F Ling (1973), On the Theoryand Construction ofk-clustcrs, Computer Journal. 15. s. 326-332

2

Zob. Anderberg (1973), Johnson i Wichem (1992).