|
GRUPOWANIE |
KLASYFIKACJA |
SELEKCJA |
|
ALGORYTMY GRUPOWANIA OPARTE NA ZBIORACH ROZMYTYCH | ||
|
Metoda górska jest ostatnio powstałym podejściem do grupowania. Ta technika grupowania jest bardzo prostą metodą intuicyjną, która nie wymaga uprzednio określenia liczby grup. Warto podkreślić, że ta metoda grupowania może być łatwo zrealizowana w sposób interakcyjny i jako taka może dostarczyć podstawowego narzędzia, za pomocą którego ludzie i maszyny mogą współzawodniczyć, aby wygenerować reguły modelu systemów rozmytych. Metoda górska jest trzyetapowym procesem na siatce identyfikacji położenia środków grup w zbiorach danych o skłonnościach do grupowania się. W pierwszym etapie dyskretyzujemy przestrzeń obiektu i jednocześnie generujemy potencjalne środki grup. W drugim etapie wykorzystujemy dane obserwacje, obiekty, które podlegają grupowaniu, do skonstruowania funkcji górskiej. W trzecim etapie tworzy się zarodki zgrupowania przez iteracyjną destrukcję funkcji górskiej. Algorytm tej metody został zaczerpnięty z [4]. Pierwszy etap metody górskiej polega na stworzeniu dyskretnej przestrzeni X x Y przez podział X i Y za pomocą odpowiednio r1 i r2 równomiernie oddalonych od siebie linii. Przecięcia tych linii siatkowych, zwane węzłami, tworzą nasz zbiór potencjalnych środków grupowania. Oznaczamy element N przez Nij, (Xi,Yj), aby wskazać węzeł otrzymany przez przecięcie linii siatki przechodzących przez Xi i Yj. Gęsta siatka zwiększa liczbę potencjalnych środków grupowania i zwiększa również wymagany układ równań. Drugim etapem jest konstrukcja funkcji górskiej M, która jest określona na zbiorze potencjalnych środków grupowania N. Funkcja górska M jest zbudowana z danych obserwacji przez dodawanie do każdego węzła w zbiorze N pewnej wielkości, proporcjonalnej do odległości tego węzła od punktu, reprezentującego dane; mogą to być tylko wielkości nie używane. Ujmując to bardziej formalnie, dla każdego punktu Nij, (Xi,Yj) w zbiorze N
![]() przy czym Ok jest k-tym punktem danych (xk,yk), a jest stałą dodatnią i d(Nij,Ok) jest miarą odległości miedzy Nij i Ok najczęściej, ale nie koniecznie tą miarą jest
Trzeci etap metody górskiej polega na wykorzystaniu funkcji górskiej do tworzenia środków grupowania. Niech węzeł N1* będzie punktem siatki o maksymalnej sumie całkowitej, szczytem funkcji górskiej. Jego wygraną będziemy oznaczali M1*=Max[M(Nij)]. Jeżeli jest więcej niż jedno maksimum, to wybieramy losowo jeden z nich. Wyróżniamy ten węzeł jako pierwszy środek grupowania i oznaczamy jego współrzędne N1*=(x1*,y1*). Aby otrzymać następny środek grupowania, musimy wyeliminować wpływ dopiero co zidentyfikowanego środka, ponieważ zazwyczaj ten szczyt jest otoczony przez pewną liczbę punktów siatki, które również mają wysokie wygrane. W tym celu musimy usunąć wpływ szczytu będącego ostatnio zidentyfikowanym środkiem grupowania i skorygować funkcję górską. Dokładniej mówiąc, tworzymy skorygowaną funkcję górską M2, określoną na N, taką że
przy czym M1 jest pierwotną funkcją górską M, b jest stałą dodatnią, N1* i M1* są to położenie i wygrana środka grupowania ostatnio zidentyfikowanego i d=(N1*,Nij) jest miarą odległości. Teraz użyjemy skorygowanej funkcji górskiej M2 do znalezienia następnego środka grupowania, określając jego położenie N2* i wygraną M2* o wartości maksymalnej. N2* staje się nowym drugim środkiem grupowania. Następnie korygujemy naszą funkcję, aby otrzymać M3
Mówiąc ogólnie, startując od skorygowanej funkcji górskiej Mk, którą otrzymujemy w rezultacie znalezienia (k-1)-szego środka grupowania, postępujemy następująco:
4. Jeżeli: Ważną cechą metody funkcji górskiej jest brak wymagania założenia liczby środków grupowania. Metoda ta wyznacza m pierwszych środków, które spełniają kryterium zakończenia obliczeń, począwszy od najważniejszych, które mają maksymalne wartości funkcji górskiej w węzłach N1*,N2*,...,Nm*.
![]()
m - parametr fuzyfikacji, | |||