Czym jest problem grupowania?

Problem grupowania należy do kategorii problemów posiadających bardzo dużą przestrzeń rozwiązań. Jego istotą jest pogrupowanie danych przekazanych na wejściu względem pewnych wspólnych cech.

Problem ten można łatwo przedstawić w formie punktów w dwuwymiarowym układzie współrzędnych. Na wejście programu podajemy współrzędne każdego z punktów, a następnie algorytm powinien wskazać ich skupiska. Przy czym każdy punkt musi należeć do jakiegoś skupiska.

R1SICIR6GMico

Ilustracja przedstawia oś XY, na której umieszczono cztery grupy punktów w różnych kolorach.
Na osi X umieszczono skale liczbową od 0 do 45.
Na osi Y umieszczono skalę liczbową od 0 do 30.
Punkty jasnoniebieskie znajdują się w przedziale wartości 5 i 10 osi X oraz 3 i 7 osi Y.
Punkty żółte znajdują się w przedziale wartości 27 i 34 osi X oraz 3 i 8 osi Y.
Punkty ciemnoniebieskie znajdują się w przedziale wartości 25 i 37 osi X oraz 14 i 24 osi Y.
Punkty czerwone znajdują się w przedziale wartości 2 i 13 osi X oraz 16 i 27 osi Y.

Standardowe algorytmy do zagadnień grupowania wymagają od użytkownika informacji wstępnej, takiej jak:

• liczba grup,

• promienie grup,

• gęstość punktów w grupach.

Czasami ciężko jednak jest podać taką informację. Dodatkowo tradycyjne algorytmy mają tendencję do wpadania w ekstrema lokalne. Tych wad pozbawione są algorytmy genetyczne. Można je dodatkowo ulepszyć poprzez wybór bardzo dobrej populacji początkowej jednym z tradycyjnych algorytmów.

Algorytm k‑średnich

Algorytm k‑średnich jest tradycyjnym algorytmem wykorzystywanym do rozwiązywania problemów grupowania. Swoje działanie opiera on na centroidachcentroidcentroidach utworzonych na podstawie średniej współrzędnych punktów w grupie.

Jest to algorytm iteracyjno‑optymalizacyjny. W kolejnych iteracjach przenosi on obiekty pomiędzy skupieniami, dążąc do zwiększenia podobieństw między obiektami w danej grupie.

Wadą tego algorytmu jest to, że na samym początku wymaga informacji o liczbie grup w analizowanym zbiorze danych. Dodatkowo jest on wrażliwy na odstające elementy oraz szumszum informacyjnyszum.

Zastosowanie algorytmu genetycznego

Nasz algorytm genetyczny będzie zajmował się wyszukiwaniem środków każdego ze skupisk punktów. Genem będzie para liczb rzeczywistych, które reprezentują współrzędne punktu na płaszczyźnie. Chromosom zatem będzie zbiorem potencjalnych środków skupisk.

R2l6eInRewkLa

Ilustracja przedstawia pole, podzielone na trzy komórki, wypełnione wartościami liczbowymi.
Komórka pierwsza: 1;8, komórka druga: 2;4, komórka trzecia: 7;3.

Pierwszą populację możemy wybrać zupełnie losowo albo spośród podanych na wejściu punktów. Wadą takiego podejścia jest to, że dojście do optymalnego rozwiązania może zająć dużą ilość czasu.

Dobrym pomysłem jest na samym początku wykorzystanie tradycyjnego algorytmu znajdowania grup. Dzięki temu uzyskamy w miarę przybliżone rozwiązanie, które następnie możemy zoptymalizować naszym algorytmem genetycznym.

Operacja krzyżowania

Operacja krzyżowania w naszym algorytmie genetycznym będzie dosyć standardowa. Możemy tutaj stosować zarówno krzyżowanie jednopunktowe, jak i wielopunktowe. Nie ma to aż tak dużego wpływu na jego funkcjonowanie.

R1BzjPDVdG2cT

Ilustracja przedstawia cztery pola.
Każda z nich podzielona jest na trzy komórki wypełnione wartościami liczbowymi.
Pole pierwsze, komórka pierwsza: 1;8, komórka druga: 2;4, komórka trzecia: 7;3.
Pole drugie komórka pierwsza: 6;4, komórka druga: 8;2, komórka trzecia: 1;1.
Pole pierwsze i drugie ustawione są jedna pod drugim.
Po prawej stronie wychodzi od nich strzałka wskazująca na pole trzecie i czwarte.
Pole trzecie, komórka pierwsza: 1;8, komórka druga: 2;4, komórka: 1;1.
Pole czwarte, komórka pierwsza: 6;4, komórka druga: 8;2, komórka trzecia: 7;3.

Operacja mutacji

Tak samo jak w przypadku algorytmów genetycznych projektujących obwody elektryczne, będziemy tutaj wykorzystywać trzy rodzaje mutacji. Pierwsza z nich będzie polegała na dodawaniu kolejnego genu do danego chromosomu, a zatem kolejnego potencjalnego środka skupiska.

Drugi rodzaj mutacji jest przeciwieństwem pierwszego i będzie on polegał na usunięciu losowego punktu skupiska z danego chromosomu. Natomiast ostatni rodzaj polega na losowej zmianie wartości współrzędnych zawartych w danym genie.

Technika równoległych populacji

Aby ulepszyć działanie naszego algorytmu genetycznego, możemy wprowadzić pewną modyfikację jego działania. Zamiast pracować na jednej, możemy równolegle ewoluować kilka niezwiązanych ze sobą populacji. Następnie co parę iteracji naszego algorytmu tworzymy nowe populacje poprzez krzyżowanie najlepszych osobników ze wszystkich grup między sobą. Pozwala to na lepsze i szybsze przeszukiwanie przestrzeni rozwiązań.

Użycie wniosków wyciągniętych ze startowej populacji

Jeżeli zdecydujemy się na użycie tradycyjnego algorytmu do wyznaczenia początkowej populacji, to możemy wyciągnąć z niej parę przydatnych wniosków, które usprawnią dalszy proces ewolucyjny.

Przykładowo, dzięki punktom wyznaczonym przez tradycyjny algorytm jesteśmy w stanie określić minimalną oraz maksymalną ilość skupisk w naszych danych wejściowych. Możemy tę informację uwzględnić w trakcie przeprowadzania mutacji i utrzymywać liczbę genów w chromosomach w danych granicach.

Przykładowe problemy grupowania

Z problemem grupowania można się często spotkać w branży marketingowej. Często grupuje się klientów o podobnych zachowaniach oraz zainteresowaniach. Dzięki temu można wyświetlać dla nich odpowiednie reklamy, modyfikować ceny w sklepach internetowych oraz proponować im promocje na produkty, które mogą ich zainteresować.

Jeżeli prowadzimy własny serwis internetowy, to bardzo często zbieramy dużą ilość danych na temat naszych odwiedzających. Ich klasyfikacja pozwala znaleźć przydatne zależności, które mogą nam pomóc w dostosowaniu treści znajdujących się na naszej stronie.

Grupowanie jest również wykorzystywane do podziału obrazu na regiony pod względem własności, takich jak kolor, tekstura, czy intensywność. Taki uproszczony obraz jest prostszy do analizy przez algorytmy rozpoznawania obrazu. Jest ono również wykorzystywane do klasyfikacji dokumentów tekstowych w wyszukiwarkach internetowych.

Słownik