generators = {
"circle_A"  : (pg.generate_points_circle,  None),
"circle_B"  : (pg.generate_points_mises,   None),
"circle_C"  : (pg.generate_points_normal,  None),
"ring"      : (pg.generate_points_ring,    None),
# "shape_A"   : (pg.generate_points_in_shape, "drawn_figure_A.txt"),
# "shape_B"   : (pg.generate_points_in_shape, "drawn_figure_B.txt"),
# "shape_C"   : (pg.generate_points_in_shape, "drawn_figure_C.txt"),}

Klasyczne klastrowanie aglomeracyjne zaczyna od traktowania każdego punktu jako osobnego klastra i iteracyjne łączy najbliższe pary klastrów, aż do osiągnięcia żądanej liczby klastrów. W badaniu zastosowano dwa warianty: Single Linkage (minimalny dystans między klastrami) i Complete Linkage (maksymalny dystans między klastrami).

    function AGGLOMERATIVE(data, target_k):
        initialize clusters ← {x} for x in data 
        compute D[i,j] ← distance between clusters i and j
        while |clusters| > target_k:
            (i, j) ← argmin_{p,q} linkage_distance(clusters[p], clusters[q])
            merge clusters[i] and clusters[j]
            update distances D for new cluster
        return clusters
            

DBSCAN identyfikuje obszary o wysokiej gęstości punktów. Dwa kluczowe parametry to ε – promień sąsiedztwa oraz MinPts – minimalna liczba punktów w otoczeniu. Algorytm oznacza punkty rdzeniowe, brzegowe i szum, tworząc klastry bez potrzeby określania ich liczby z góry.

function DBSCAN(D, eps, MinPts):
    C ← 0
    for each point p in D:
        if p not visited:
            mark p visited
            N ← regionQuery(p, eps)
            if |N| < MinPts:
                label p as noise
            else:
                C ← C + 1
                expandCluster(p, N, C, eps, MinPts)
    return cluster labels

function expandCluster(p, N, C, eps, MinPts):
    add p to cluster C
    for each point q in N:
        if q not visited:
            mark q visited
            N' ← regionQuery(q, eps)
            if |N'| ≥ MinPts:
                N ← N ∪ N'
        if q not yet member of any cluster:
            add q to cluster C

function regionQuery(p, eps):
    return {q in D | distance(p, q) ≤ eps}
            

Algorytm k najbliższych sąsiadów (KNN) w kontekście tego badania służył do oceny średnich odległości między punktami w klastrze. Wyznaczone wartości dₖ stanowią jedną z miar jakości klasteryzacji.

function KNN_distance(data, k):
    distances_list ← []
    for each point x in data:
        D_x ← sort([distance(x, y) for y ≠ x])
        d_x ← average(D_x[1..k])
        distances_list.append(d_x)
    return mean(distances_list)
            

Dla klastrowania aglomeracyjnego decydującym parametrem była liczba klastrów (target_k = 2). Na podstawie dendrogramu określono próg cięcia tak, aby utworzyć dwa klastry, a następnie oceniono jakość za pomocą miar P1–P3,k, traktując mniejszy klaster jako szum.

Do dobrania ε oraz MinPts zaimplementowano funkcję dbscanLoop, która przeszukuje ε z zakresu [2, 20] co 0.2 oraz MinPts z zakresu [20, 150] co 1. Dla każdej pary parametrów obliczane są miary jakości klasteryzacji, a najlepszy zestaw wybierany jest na podstawie maksymalnej wartości kryteriów P1–P3,k.

W ramach analizy granularnego grupowania opracowano zestaw 15 miar oceny jakości skupienia, które łączą ze sobą informacje o liczbie punktów w największym klastrze oraz miary odległości między tymi punktami. Podstawowe trzy miary (P1, P2, P3) opierają się na średniej odległości między wszystkimi punktami w klastrze (d̄):

• P1 = liczba punktów × (1 / d̄)
• P2 = liczba punktów × (1 / d̄)²
• P3 = √(liczba punktów) × (1 / d̄)²

Kolejne 12 miar to rozszerzenia powyższych z wykorzystaniem odległości do k najbliższych sąsiadów (d_k) dla k = 3, 5, 7, 9. Dla każdego k obliczane są trzy warianty:

• P1_k = liczba punktów × (1 / d_k)
• P2_k = liczba punktów × (1 / d_k)²
• P3_k = √(liczba punktów) × (1 / d_k)²

Miary te różnią się poziomem agresywności względem wartości odległości — metryki z kwadratem (P2, P3) są bardziej czułe na zmiany rozproszenia, co pozwala lepiej wykrywać spójność dużych i zwartych skupień. Dzięki ujęciu w formie odwrotności, wartości miar rosną w kierunku bardziej jednorodnych klastrów.

# TO DO: Obrazki kształtów zbiorów danych

Single Linkage: we wszystkich analizowanych zbiorach (koło jednorodne, von Mises, normalne, pierścień, półksiężyc, „X”, grzyb) algorytm utrzymuje wysoką dokładność (>80 %) przy poziomach szumu do 60 %. Najbardziej stabilne wyniki (powyżej 88 %) uzyskano dla koła i pierścienia, natomiast najtrudniejszym przypadkiem był półksiężyc – dokładność spadała do 54 % przy 60 % szumu. W każdym zestawie gwałtowny spadek poniżej 35 % obserwujemy przy 70 % szumu, co pokazuje granicę tolerancji Single Linkage.

DBSCAN: również radzi sobie dobrze do 60 % szumu, często osiągając bardzo wysoką dokładność (np. 90 % dla koła, 92 % dla pierścienia, 90 % dla grzyba). Interesującym wyjątkiem jest rozkład von Mises, gdzie dokładność wzrasta z 50 % przy 40 % szumu do 80 % przy 70 % szumu, co wynika z premiowania gęstych, zwartch klastrów. Podobnie jak Single Linkage, DBSCAN traci skuteczność przy 70 % szumu (dokładność spada do ok. 30–37 % w większości przypadków).

Complete Linkage: nie wykazuje istotnej wrażliwości na szum (zawsze wybiera ten sam próg przerwania i uzyskuje jednolite, niskie wyniki), dlatego jego prezentacja została pominięta.