79928 P3200023

4.1-2- Charakterystyka obiektów

Zakładamy, że badane obiekty tworzą skończony zbiór (będący populacją lub próbą wylosowaną ¹ 1¹ pulacji) ii— {O,, 0₂,...,0„j. Liczba elementów zbioru £ł wynosi n. Każdy z obiektów jest opisany za pomocą m zmiennych przyjmujących wartości liczbowe'. Oi=|t,i^a- --.-t«.}. i =l,...,n (rozwijana jest teoria symbolicznego grupowania, w którym obiekty są opisane przez cechy jakościowe, jednak te metody wymagają innego podejścia i w tym opracowaniu nie omawiamy ich; problemom tym poświęcona jest m.in. praca (Gatnar, 1998]).

W ten sposób zbiór obiektów jest reprezentowany przez n-elementowy zbiór punktów w przestrzeni m-wymiarowej zwanej przestrzenią grupowania. W przestrzeni grupowania zdefiniowana jest metryka pozwalająca określać odległości między obiektami. Do najbardziej znanych metryk można zaliczyć: odległość euklidesową, kwadrat odległości euklide-sowej, metrykę miejską, metrykę Czebyszewa, metrykę Mahalanobisa.

Matematycznie problem można sprowadzić do zadania podziału n obiektów na k rozłącznych niepustych podzbiorów o liczebności n_un₂,...,n_k (gdzie n,+n₂+...+n_k=n) w ten sposób. aby zminimalizować pewną funkcję kryterium (tym kryterium może być np. wariancja wewnątrzorupowa obiektów). Teoretycznie możemy rozwiązać zadanie obliczając wartości funkcji kryterium dla wszystkich możliwych podziałów i wybierając podział optymalny. Jednak z praktycznego punktu widzenia jest to niemożliwe. Liczba A wszystkich możliwych podziałów n-elementowego zbioru na k rozłącznych i niepustych podzbiorów jest liczbąStirlinga drugiego rodzaju i wynosi:

4.1

Liczba A przyjmuje olbrzymie wartości już dla stosunkowo małych wartości n i k. Przykładowo dla zt=10 i k=2 wynosi ona 511. a dla n=40, k=4 już 5,037«10²~. W tym drugim przypadku nawet przyjmując, że komputer oblicza wartość kryterium dla jednego podziału wciągu 1 mikrosekundy, potrzeba około 1/, miliarda lat na zakończenie obliczeń. Podejmowane były próby znalezienia algorytmu upraszczającego analizę tak. żeby nie trzeba było wyodrębniać wszystkich możliwych podziałów, jednak dotychczasowe rezultaty nie Hzadowalające. Z tego względu stosowane są metody prowadzące do rozwiązań przybliżonych, mimo że nie są one optymalne.