Algorytmy oparte na zbiorach przybliżonych

Algorytmy grupowania oparte na zbiorach przybliżonych wykorzystują dyskretyzację przestrzeni na zbiory elementarne, wewnątrz których elementy są nierozróżnialne [6]. Wynika stąd, iż w procesie grupowania z wykorzystaniem zbiorów przybliżonych pierwszym krokiem jest określenie wielkości zbioru elementarnego. Pierwszym sposobem jest odgórne ustalenie jego wielkości (na przykład jedna jednostka wzdłuż każdej osi układu). Jednak ten sposób jest najgorszym z możliwych, gdyż nie bierze pod uwagę rozkładu elementów przestrzeni wzdłuż poszczególnych osi układu, ani też różnicy w rzędach wielkości miar na każdej osi. Przy stosowaniu tego rodzaju określenia zbioru elementarnego konieczne jest wcześniejsze przeprowadzenie normalizacji całego układu. Kolejnym sposobem ustalenia wielkości zbioru elementarnego jest jego uzależnienie od liczby elementów na przykład jako:

gdzie E_i jest długością zbioru elementarnego wzdłuż osi i, natomiast max_i oraz min_i są odpowiednio największą i najmniejszą wartością współrzędnej i występującą w rozpatrywanym zbiorze danych. Można stąd zauważyć, że wielość zbioru elementarnego zależy od rozmieszczenia elementów wzdłuż każdej osi układu współrzędnych, i może być różna w różnych kierunkach. Wadą tego rozwiązania jest przyjęcie zbyt dużych zbiorów elementarnych przy małej liczbie rozpatrywanych elementów, oraz zbyt małych przy zbyt dużej liczbie elementów.
Trzecim rozwiązaniem jest wprowadzenie dodatkowego parametru, który umożliwiałby uzyskanie pożądanej wielkości zbioru elementarnego. Przykładem takiego rozwiązania jest przekazywanie w postaci parametru liczby zbiorów elementarnych, na które mają zostać podzielone osie układu współrzędnych. Przy zastosowaniu tego sposobu wielkość zbioru elementarnego zależy od rozrzutu elementów wzdłuż każdej osi układu i może być obliczana jako:

gdzie par jest przekazywanym parametrem. W pierwszym z zaproponowanych algorytmów grupowania opartych na zbiorach przybliżonych wielkość zbioru elementarnego, jak również wielkość zbiorów, których elementy są dołączane do rozpatrywanej grupy jest obliczana w zależności od parametru nazwanego stopniem przybliżenia (st_przybl), który może przyjmować wartości z przedziału [0-1], algorytm ten został zapisany w postaci procedury MATLABa prz01.m i prz03.m. Schemat działania tego algorytmu można zapisać następująco:

1. Podział przestrzeni na zbiory elementarne, których wielkość obliczana jest wzorem:
   
   
   
   
2. Zastąpienie współrzędnych wszystkich elementów wskaźnikami do zbiorów elementarnych, do których przynależą.
3. Połączenie w grupy elementów nierozróżnialnych (znajdujących się w tych samych zbiorach elementarnych)
4. Wyznaczenie wielkości zbioru, którego elementy będą przynależały do tej samej grupy, co jego środek. Dołączanie pozostałych elementów do grup.
5. Sprawdzenie liczebności poszczególnych grup. Oznaczenie grup, których liczebność jest mniejsza od założonej jako elementów niesklasyfikowanych.

Algorytm ten działa poprawnie dla wszystkich rodzajów zbiorów, jednak wymaga dokładnego określenia parametru st_przybl, czego można dokonać jedynie przy pomocy metody prób i błędów.
W kolejnym algorytmie opracowanym na potrzeby tej pracy wielkość zbioru elementarnego jest określana poprzez parametr przybl, który informuje program o tym, na ile odcinków elementarnych ma zostać podzielona każda oś układu współrzędnych. Wielkość zbioru elementarnego w każdym kierunku jest obliczana jako iloraz rozrzutu danych w tym kierunku do liczby odcinków, na które ma być podzielony:

Algorytm ten działa podobnie do poprzedniego, z tym, że założoną z góry liczbę grup osiąga poprzez modyfikację wielkości zbioru, którego elementy są dołączane do poszczególnych grup. Algorytm ten został zapisany w postaci procedury prz02.m. Schemat działania algorytmu można przedstawić w kilku punktach:

1. Podział przestrzeni na zadaną liczbę zbiorów elementarnych (dyskretyzacja przestrzeni).
2. Zamiana współrzędnych każdego punktu, na współrzędne określające położenie zbioru elementarnego do którego dane punkty przynależą.
3. Obliczenia początkowe:
   
   1. Połączenie elementów nierozróżnialnych w grupy.
   2. Oznaczenie elementów przynależnych do grup o zbyt małej liczebności jako niesklasyfikowanych.
   3. Wyznaczenie liczby grup na jakie została podzielona przestrzeń i porównanie jej z założoną liczbą grup.
4. Przyłączanie kolejnych punktów do grup:
   
   1. Wyznaczenie nowej wielkości otoczenia punktu.
   2. Przyłączanie do każdej grupy punktów znajdujących się w otoczeniu każdego elementu tej grupy.
5. Oznaczenie elementów przynależnych do grup o zbyt małej liczebności jako niesklasyfikowanych.
6. Wyznaczenie liczby grup na jakie została podzielona przestrzeń oraz liczby elementów niesklasyfikowanych i porównanie jej z założonymi wielkościami:
   
   1. jeżeli któraś z wielkości nie spełnia założeń - powrót do punktu 4.
   2. jeżeli liczba grup przestrzeni jest zgodna z założoną, a ilość elementów niesklasyfikowanych mieści się w normie - przyjęcie podziału jako optymalnego.