NARZĘDZIA SZTUCZNEJ INTELIGENCJI

PROJEKT 2011

GRUPOWANIE DANYCH

PJWSTK W GDAŃSKU

Kod

• W Języku ActionScript 3.0 zaimplementowałem algorytm k-średnich, zgodnie z zadanym pseudokodem

• Program pobiera dane z plików tekstowych i wyświetla je w formie graficznej

• Program umożliwia także wygenerowanie losowego zestawu danych o zadanej liczbie obiektów w zakresie od 20 do 1000

• Istnieje możliwość wyboru ilości środków skupień w zakresie od 2 do 10

• Program umożliwia wybranie sposobu generowania początkowych środków skupień:

  • Losowy wybór środków

  • Losowy wybór 1-go środka, a następnie wyliczenie następnego najbardziej od niego odległego punktu, po czym wybranie następnego najbardziej odległego od nich punktu itd.

• Program wypisuje wyliczone dane w tabeli wyświetlanej w oknie głównym

• Fragment kodu odpowiedzialny za wyliczanie środków i liczenie odległości między punktami i środkami:

public function stworzSrodki(num:int):void

{

_mPoints = [];

for (var i:int = 0; i < num; i++) 

{

var distances:Array = [];

for (var j:int = 0; j < _points.length; j++) 

{

distances.push( { distance:checkDistance(_points[j]), id:j });

}

distances.sortOn("distance", Array.NUMERIC | Array.DESCENDING);

var id:int = i == 0 ?  Math.random() * _points.length : distances[0].id;

var dot:Dot = _points[id];

var mPoint:MidPoint = new MidPoint(dot.getCords().x, dot.getCords().y, i);

_mPoints.push(mPoint);

addChild(mPoint);

}

}

public function sprawdzOdleglosc(dot:Dot):Number

{

var result:Number = 0;

for (var i:int = 0; i < _mPoints.length; i++) 

{

result += Point.distance(_mPoints[i].getCords(), dot.getCords());

}

return result;

}

Obliczenia

• Przygotowałem 3 zestawy danych wejściowych do programu, które zgodnie z sugestią pobrane zostały ze strony http://www.isical.ac.in/~sanghami/data.html

• Dla każdego zestawu danych przeprowadziłem w programie po 30 symulacji dla środków skupień wybranych losowo i dla środków najbardziej odległych

• Do pomiaru jakości klasyfikacji przyjąłem funkcje kosztu daną wzorem:

• Obliczyłem wartość średnią i odchylenie standardowe wskaźnika J

• Obliczyłem wartość średnią i odchylenie standardowe ilości iteracji wymaganych przy każdym typie inicjalizacji

1. Dane

   1. Zestaw 3_2

Dane wejściowe z pierwszego zestawu w formie graficznej prezentują się następująco:

Przykładowy losowy sposób generacji 3 środków skupień:

Przykładowo wygenerowane 3 środki najbardziej odległe:

Dwie końcowe wersje otrzymanych skupień dla 3 środków:

Zestaw 6_2

Dane wejściowe z drugiego zestawu w formie graficznej prezentują się następująco:

Przykładowy losowy sposób generacji 6 środków skupień:

Przykładowo wygenerowane 6 środków najbardziej odległych:

Kilka końcowych wersji otrzymanych skupień dla 6 środków:

Dwa przykłady zagłodzenia jednego ze środków:

Zestaw 4_3 (zmodyfikowany do 2 wymiarów)

Dane wejściowe z trzeciego zestawu w formie graficznej prezentują się następująco:

Przykładowy losowy sposób generacji 4 środków skupień:

Przykładowo wygenerowane 4 środki najbardziej odległe:

Jedyna końcowa wersja otrzymanych skupień dla 4 środków:

Wyniki

Otrzymane wyniki przedstawiam poniżej w formie tabeli:

dane 3_2 losowo
iter - średnie
iter - odchylenie
dane 3_2 najdalsze
iter - średnie
iter - odchylenie
dane 6_2 losowo
iter - średnie
iter - odchylenie
dane 6_2 najdalsze
iter - średnie
iter - odchylenie
dane 4_3 losowo
iter - średnie
iter - odchylenie
dane 4_3 najdalsze
iter - średnie
iter - odchylenie

Wnioski

Jak widać w załączonej tabeli liczba iteracji i odchylenie standardowe dla metody losowej jest większa niż dla metody z wyliczonymi środkami najbardziej odległymi. Także funkcja kosztu obliczona jako wskaźnik J oraz odchylenie standardowe dla wskaźnika J są wyraźnie większe dla metody losowej. W trzecim przypadku końcowy efekt grupowania skupień był za każdym razem identyczny bez względu na wybraną metodę, jednak metoda najbardziej odległych środków osiągała cel w dużo mniejszej liczbie iteracji – w tym wypadku średnio ok. 4,5 iteracji przy 7,5 iteracji przy wyborze losowych środków.

Wynika z tego, że przy tym samym algorytmie liczącym metoda wyboru środków skupień jako najbardziej odległych od siebie obiektów jest dużo skuteczniejsza od metody losowego wyboru tych środków.

Testowaliśmy tylko dwie metody wyboru środków, ale studiując literaturę natknąłem się na jeszcze inne metody (algorytm logiki rozmytej, euklidesowa, miejska), jednak trudno mi ocenić ich skuteczność bez fizycznego przetestowania.