UPORZĄDKOWANIE DRZEWKOWE

Hierarchia drzewkowa zbioru jest definiowana jako uporządkowana dwójka <,V>, gdzie:

V - macierz konfetyczna, której elementami są wartości ultrametryki między elementami 1, 2,...,n

ultrametryka określa poziom, na jakim dwa obiekty spotykają się na drzewku połączeń (dendogramie)

METODA NAJBLIŻSZEGO SĄSIEDZTWA

odległość między dwiema grupami definiuje się jako najkrótszą spośród odległości między dowolnymi obiektami należącymi do tych dwóch grup obiektów

a)

(l=0)

:

1

2

3

4

5

6

7

8

gdzie:l - numer etapu,

b) łączymy parę najbliższych sobie podgrup

(l=1)

:

1, 2

3

4

5

6

7

8

c) wyznaczamy odległości między podgrupą {1, 2} a wszystkimi obiektami wybierając każdorazowo krótszą z dwóch odległości

itd.

d) tworzymy macierz odległości po pierwszym połączeniu

e) łączymy parę najbliższych sobie podgrup

(l=2)

:

1, 2

3

4

5

6, 7

8

f) wyznaczamy odległości między podgrupą {6, 7} a wszystkimi pozostałymi podgrupami wybierając każdorazowo najkrótszą z odległości

g) powtarzamy procedurę aż do uzyskania jednej grupy, w której znajdują się wszystkie elementy badanego zbioru

PRZEBIEG AGLOMERACJI ZBIORU

L.p.	Łączone podgrupy
1		1,00
2		1,00
3		1,00
4		1,41
5		2,00
6		3,61
7		3,61

MACIERZ KONFETYCZNA V

DENDOGRAM UZYSKANY METODĄ

NAJNIŻSZEGO SĄSIEDZTWA

4

3,61

3

2

1,41

1

1 2 3 4 5 6 7 8

METODA ELIMINACJI WEKTORÓW

1. Przekształcamy macierz odległości D w macierz binarną P:

gdy elementy zbioru są podobne 0

gdy elementy zbioru nie są podobne 1

tzn.: przyjmujemy poziom krytyczny podobieństw d*

2. Budujemy wektor eliminacji P0, którego elementy są sumą odpowiednich wierszy macierzy P

eliminujemy wiersz i odpowiadającą mu kolumnę, które wskazuje maksymalny element w wektorze

3. Tworzymy macierz zredukowaną

3. Eliminację kontynuujemy aż do momentu gdy w macierzy P pozostaną same zera

4. Obiekty tworzące macierz, w której pozostały same zera stanowią pierwszą podgrupę:

5. Budujemy macierz P1 po wyeliminowaniu obiektów należących do pierwszej podgrupy:

6. Budujemy wektor eliminacji

7. Po wyeliminowaniu obiektu
w macierzy P1 pozostają same zera

8. Ostateczny podział zbioru :

Metoda k-średnich

funkcja kryterium: ogólna suma odległości wewnętrzgrupowych liczonych od środka grup, których współrzędne wyznaczone są jako średnie arytmetyczne z wartości cech obiektów należących do danej podgrupy

Przykład

1. Przyjmujemy podział wstępny na k=3 podzbiorów

2. Wyznaczamy w sposób losowy podział wyjściowy:

3. Wyznaczamy współrzędne środków grup

4. Szacujemy sumę odległości wewnątrzgrupowych:

5. Próbujemy przemieszczać obiekty do innych grup niż się aktualnie znajdują tak aby spowodować jak największe zmniejszenie wariancji wewnątrzgrupowej (F)

a) przesuwając obiekt 1 do 2-giej podgrupy uzyskujemy: F=23,42, a do 3-ciej podgrupy: F=21,34

6. Przyjmujemy nowy podział na podgrupy:

7. Próbujemy przemieszczać obiekty do innych podgrup:

a) przesuwając obiekt 2 do 1-szej podgrupy uzyskujemy: F=15,37, a do 3-ciej podgrupy: F= 13,25

8. Przyjmujemy nowy podział na podgrupy:

itd.

9. Powtarzamy procedurę przesunięć dla k=3 aż do momentu gdy F=min

10. Po sprawdzeniu alokacji każdego z punktów okazuje się, że najmniejsza wartość F=11,15 odpowiada podziałowi:

METODA CZEKANOWSKIEGO

funkcja kryterium dobroci grupowania

gdzie:

- liczba bliskich powiązań między elementami wewnątrz wyodrębnionych podzbiorów

- liczba dalszych powiązań między elementami na zewnątrz wyodrębnionych podzbiorów

W - liczba wszystkich powiązań wewnątrz podzbiorów

Z - liczba wszystkich powiązań na zewnątrz podzbioru

Przykład:

1. Propozycja podziału na podzbiory rozłączne

a)

b)

2. Obliczamy wartości funkcji kryterium dobroci grupowania

3. Przyjmujemy ostateczny podział zbioru , dla którego funkcja kryterium dobroci grupowania przyjmuje najwyższą wartość

TAKSONOMIA WROCŁAWSKA

(optymalny podział dendrytu)

1. Porządkujemy wiązadła dendrytu wg. malejących wartości ich długości:

2. Tworzymy ilorazy długości sąsiednich wiązadeł:

3. Sprawdzamy dla jakiej wartości "k" spełniona jest relacja:

4. Odrzucamy wiązadła tworzące ilorazy spełniające relację 3.

Metoda Hellwiga (podział dendrytu)

1. Szukamy wartości krytycznej c*, za pomocą której usuwamy wiązadła dendrytu

gdzie:

- najmniejszy element w wierszu (kolumnie) "i"

2. Porządkujemy wiązadła dendrytu wg malejących wielkości

3. Odrzucamy wiązadła o wartościach większych od c*

---