proj_z.pdf

Studia niestacjonarne.

Narz¦dzia sztucznej inteligencji, sem. VIII, 2010/2011

1 Projekt 1. Grupowanie danych

Napisa¢ program implementuj¡cy algorytm k -±rednich opisany pseudoko-

dem 1.

Algorithm 1 Iteracyjny algorytm analizy skupie«

1: Dane WY: zbiór obiektów X = { x 1 ,...,x m } , k – liczba klas.

2: Dane WY:

(a) podział obiektów na k rozł¡cznych klas reprezentowany przez ta-

blic¦ przydziałów U = [ u ij ] m × k

(b) ±rodki ci¦»ko±ci klas µ j , j = 1 ,...,k .

3: Inicjalizacja . Wyznacz ±rodki skupie« { µ 1 ,...,µ k } .

4: Aktualizacja przydziałów: dla ka»dego obiektu wyznacz jego przynale»-

no±¢ do skupienia stosuj¡c reguł¦ zwyci¦zca bierze wszystko , tzn.

1 je»eli d ( x i ,µ j ) = min

1 ¬ l ¬ k d ( x j ,µ l )

u ij =

i = 1 ,...,m,j = 1 ,...,k

0 w p.p.

(1)

gdzie d ( x i ,µ j ) to odległo±¢ euklidesowa mi¦dzy obiektem x i 2 X a ±rod-

kiem ci¦»ko±ci µ j .

5: Aktualizacja ±rodków ci¦»ko±ci skupie«:

µ j =

P i =1 u ij x i

P i =1 u ij

(2)

6: Powtarzaj kroki 4 i 5 do chwili spełnienia warunku zatrzymania, którym

jest zazwyczaj niezmienno±¢ przypisa« obiektów do skupie«.

Przeprowadzi¢ eksperymenty dla wybranych zbiorów X i ró»nych strate-

gii inicjowania ±rodków ci¦»ko±ci, tzn:

(a) Ze strony http://www.isical.ac.in/~sanghami/data.html pobra¢

np. nast¦puj¡ce dane: data 3 2 , data 6 2 , data 4 3 . Wykona¢ stosow-

ne wykresy reprezentuj¡ce ka»dy zbiór danych.

(b) Sprawdzi¢ skuteczno±¢ nast¦puj¡cych metod inicjalizacji:

(i) Losowy wybór k obiektów ze zbioru X .

(ii) Wybór k najbardziej odległych od siebie obiektów z X , tzn. rozpo-

czynamy od wyboru losowego obiektu z X . Stanowi on pierwszy

±rodek µ 1 . W zbiorze X poszukujemy obiektu najbardziej odle-

głego od µ 1 . Obiekt ten stanowi drugi ±rodek µ 2 . Niech M =

{ µ 1 ,...,µ j } , j = 2 ,...k − 1. Najbardziej odległy obiekt od zbioru

M wybieramy nast¦puj¡co. Dla ka»dego obiektu z X obliczamy je-

go odległo±¢ od elementów ze zbioru M i przyjmujemy d ( x,M ) =

min l =1 ,...,j d ( x,µ l ). jako µ j +1 przyjmujemy obiekt najbardziej od-

legły od M , tzn. taki obiekt x , »e d ( x ,M ) = max x 2 X d ( x,M ).

J =

d 2 ( x i ,c ( x i ))

(3)

i =1

gdzie c ( x i ) oznacza ±rodek ci¦»ko±ci klasy, do której przypisano obiekt

x i , czyli ±rodek najbli»szy temu obiektowi. Poda¢ liczb¦ iteracji (po-

wtórze« kroków 4 i 5) wykonanych przez algorytm.

(d) Dla danego zbioru X i ka»dego wariantu inicjalizacyjnego uruchomi¢

30 razy algorytm 1. Obliczy¢ warto±¢ ±redni¡ i odchylenie standardowe

wska¹nika J . Podobnie policzy¢ warto±¢ ±redni¡ i odchylenie standar-

dowe liczby iteracji wymaganych przy ka»dym typie inicjalizacji. Czy

oba typy inicjalizacji ró»ni¡ si¦? czy mo»na zaproponowa¢ bardziej efek-

tywna metod¦ inicjalizacji?

2 Projekt 2 – tbd

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: