Zaawansowane metody analizy i eksploracji danych | I2N | semestr zimowy 2025/2026

Laboratorium 2

1. Zaimplementuj algorytm k-means w dwóch wersjach:

   • bez użycia bibliotek numerycznych (czysty Python),
   • z wykorzystaniem biblioteki numpy.

   Początkowy wybór centroidów ma być losowy z (dyskretnym) rozkładem jednostajnym. Następnie:

   • Porównaj czas działania obu wersji dla 1000, 5000, 20000 i 100000 losowych punktów oraz 3, 5 i 10 klastrów,
   • Stwórz funkcję prezentującą obliczone klastry w formie graficznej (matplotlib z wykresem typu scatter, każdy klaster innego koloru).
   • (Dla chętnych) Przedstaw animację (wystarczy gif), prezentującą zmiany w klastrach w kolejnych krokach algorytmu.

2. Dla algorytmu z zadania 1 zmień sposób wybierania początkowych centroidów. Pierwszy wybierz losowo, a każdy następny wybierz z jeszcze niewybranych punktów z prawdopodobieństwem proporcjonalnym do kwadratu odległości między tym punktem a najbliższym centroidem.

3. Zaimplementuj aglomeracyjny algorytm hierarchiczny w trzech wersjach odmienności:

   • najbliższego sąsiada (single linkage),
   • najdalszego sąsiada (complete linkage),
   • średniej (average linkage).

   Następnie:

   • Dla losowego zbioru punktów przedstaw graficznie (jak w zadaniu 1) obliczone klastry. Dla dużych zbiorów punktów ustaw sensowne ograniczenia liczby klastrów.
   • Porównaj dla losowych danych i różnych funkcji odmienności różnicę w wyglądzie klastrów dla algorytmów k-means i hierarchicznego.
   • (Dla chętnych) Przedstaw graficznie klastry w formie dendrogramu.

4. Zaimplementuj algorytm DBSCAN i porównaj go z algorytmami z zadania 1 i 3.