Algorytmy

Ogólnie algorytmy grupowania możemy podzielić na trzy grupy [3]:

Pierwszą z nich stanowią algorytmy poszukiwania ogólnego ekstremum funkcji kryterialnej. Algorytmy te polegają na wyznaczeniu wszystkich możliwych podziałów elementów przestrzeni na zadaną ilość grup. Kolejnym krokiem jest określenie wartości przyjętej funkcji kryterialnej dla każdego z tak wyznaczonych podziałów. Za optymalny uznaje się ten, dla którego wartość funkcji kryterialnej osiągnęła ekstremum. Algorytm ten jest bardzo prosty w realizacji. Niestety z uwagi na potrzebę wykonania bardzo dużej liczby działań, która jest konieczna do wyznaczenia wszystkich możliwych podziałów elementów przestrzeni, nie jest on w praktyce stosowany.

Kolejną grupą algorytmów grupowania są algorytmy hierarchicznego podziału i grupowania. W pierwszej kolejności zajmiemy się algorytmami podziału. Ich istotą jest poszukiwanie takiego podziału elementów przestrzeni na dwa rozłączne podzbiory, aby przyjęta funkcja kryterialna osiągnęła dla niego ekstremum. Po wyznaczeniu optymalnego podziału na dwie grupy, algorytm ma za zadanie wybrać spośród wszystkich grup, tę o najmniejszej spójności, i podzielić ją na dwie grupy, aby osiągnąć ekstremum przyjętej funkcji kryterialnej. Powyższe kroki powtarza się aż do momentu osiągnięcia zadanej ilości grup. Natomiast jeśli chodzi o algorytmy hierarchicznego grupowania postępowanie w nich przyjęte sprowadza się do łączenia w grupy elementów o największym podobieństwie. Polega to na tym, iż w pierwszym kroku każdy element przestrzeni stanowi oddzielną jednoelementową grupę. Następnie kolejno w każdym kroku następuje łączenie w grupy elementów, których wzajemne podobieństwo jest największe. Postępowanie takie kończymy w momencie osiągnięcia żądanej liczby grup, na jakie mieliśmy podzielić przestrzeń. Wśród autorów publikacji panuje zgoda, co do braku istotnych różnic w zaletach algorytmów grupowania i podziału. Wojciech Cholewa w swojej pracy stwierdza, "że za wystarczająco skuteczne dla uzyskania optymalnego podziału przestrzeni V na l zbiorów elementów podobnych należy uznać postępowanie polegające na hierarchicznym podziale przestrzeni V na około 2 l podzbiorów, a następnie hierarchiczne grupowanie (łączenie) tak otrzymanych zbiorów w celu wyznaczenia wymaganych l zbiorów." [3]

Ostatnią z przedstawionych grup algorytmów grupowania są algorytmy iteracyjne. Ich działanie najlepiej jest przedstawić na podstawie prostego algorytmu. W pierwszym kroku należy wybrać elementy, które można uznać za początkowe przybliżenie reprezentantów q(V1),...,q(Vl). Następnie przeprowadza się dla tak wybranych reprezentantów klasyfikację elementów, polegającą na takim przyporządkowaniu każdego elementu do grupy wyznaczonej przez reprezentanta, dla którego funkcja podobieństwa osiąga ekstremum. W trzecim kroku dla nowo wyznaczonych grup należy określić nowe położenie reprezentantów. Następnie, jeżeli nowo wyznaczeni reprezentanci grup różnią się od reprezentantów z poprzedniego kroku iteracji, należy powrócić do kroku drugiego uwzględniając nowych reprezentantów grup. Natomiast w przypadku, gdy nowo wyznaczeni reprezentanci są identyczni z tymi z poprzedniego kroku iteracji, wówczas uzyskany podział uważa się za optymalny. Największą niedogodnością tego typu algorytmów jest konieczność wykonywania dużej liczby działań, a także uzależnienie końcowego rezultatu od przyjętych w pierwszym kroku reprezentantów.