4. Potyczki Informatyczne Nowej Generacji

Zadanie eliminacyjne w konkursie WIPING4 organizowanym przez
Wydział Informatyki Zachodniopomorskiego Uniwersytetu Technologicznego w Szczecinie

Klasteryzator

Klasteryzacja to (w dużym uproszczeniu) proces grupowania elementów w klasy. Klasteryzacja jest jedną z podstawowych metod stosowanych w zagadnieniach sztucznej inteligencji, eksploracji danych i uczenia maszynowego.

Twoim zadaniem będzie napisanie prostego (naprawdę!) klasteryzatora używającego algorytmu k-środków.

Algorytm k-środków pozwala na przypisanie posiadanych danych (próbek) do pewnej liczby grup. Każdą taką grupę reprezentuje pewien punkt w przestrzeni n-wymiarowej (punkt taki nazywamy centrum). Kolejne próbki przypisywane są do najbliższej z grup na podstawie odległości od ich centrum. W konsekwencji po każdej każdej iteracji centrum grupy przemieszcza się, a jego nowa pozycja jest średnią arytmetyczna współrzędnych przypisanych do niego próbek. Na potrzeby zadania zakładamy, że początkowe pozycje centrum są takie same, jak próbek o wskazanych indeksach. Posiadając zbiór danych, liczbę grup, początkowe pozycje centrów oraz typ odległości wyznacz, które z próbek należą do której z grup po zakończeniu pierwszej iteracji algorytmu.

W naszym zadaniu stosować będziemy trzy różne sposoby pomiaru odległości pomiędzy punktami - są to metryki:

• euklidesowa - nie wymagająca szczegółowych objaśnień, jako że jest to - naszym zdaniem - najbardziej intuicyjna z metryk, sprowadzająca się do wyznaczenia długości odcinka łączącego dwa punkty przestrzeni
• Manhattan - to suma wartości bezwzględnych różnic ich współrzędnych (dokładniejszy opis ten metryki znajdziesz np. tutaj)
• PING - specjalna metryka skonstruowana na potrzeby naszego zadania; działa ona w przestrzeni polarnej (biegunowej) i aby ją wyznaczyć, należy przekształcić współrzędne centrów oraz próbek z systemu kartezjańskiego na polarny (biegunowy); następnie można obliczyć odległość zgodnie ze wzorem:  
  
  
  
  odległość ta będzie używana wyłącznie dla danych 2D (tzn. takich, w których współrzędne wszystkich punktów podane są parami liczb)

Wejś›cie

Nieznana z góry liczba wierszy, zawierających kolejno:

• liczba grup (k)
  
• n (0 < n <= k) rozdzielonych spacjami liczb całkowitych, będących indeksami (liczonymi od zera) tych próbek, które są kolejnymi centrami grup
  
• jedno z poniższych słów, określające zastosowaną metrykę:
  
  • euk
  • man
  • pin
• m wierszy, każdy zawierający taką samą liczbę liczb rzeczywistych rozdzielonych przecinkami, określającymi współrzędne próbek
  

Wyjś›cie

• m wierszy, każdy zawierający parę liczb całkowitych rodzielonych spacją, oznaczających kolejno 
  • numer grupy
    
  • numer próbki przypisanej do tej grupy
    
  wiersze ułożone są rosnąco według klucza skonstruowanego z numeru grupy i numeru próbki
  

Przykł‚ad

Wejś›cie: 

3
0 1 4
euk
1.0,1.0
1.0,2.0
4.0,3.0
4.0,4.0
5.0,8.0
5.0,9.0

Wyjście: 

0 0
0 1
1 2
1 3
2 4
2 5

Rozbudowaną interpretację przykładu zawiera dokument dostępny tutaj.

Informacje dodatkowe

• program zostanie uruchomiony 10 razy dla różnych zestawów danych
  

• każde poprawne rozwią…zanie daje 10% punktacji zadania
• zadanie ma wartość‡ punktową… 7,0
• spośród danych wejściowych 4 używają miary 'pin', 3 miary 'euk' i 3 miary 'man'