K-means vs K-medoid:

Aspect	K-means (Lloyd)	K-medoid (PAM)
Center	Centroid = mean $\mu_j=\frac1{|C_j|}\sum x$ (not necessarily data point, continuous)	Medoid = actual data point minimizing sum distance to cluster members
Distance	Euclidean (minimizes SSE)	Any metric (Manhattan, arbitrary dissimilarity)
Robustness	Sensitive to outliers (mean shifts)	Robust (medoid not affected by extreme outlier)
Cost function	$J=\sum\sum||x-\mu||^2$	$E=\sum\sum d(x,m_j)$
Complexity	$O(nkdi)$ fast	$O(k(n-k)^2)$ per iteration (PAM) much slower, $CLARA/CLARANS$ for large data
When to use	Continuous, spherical clusters, fast	Categorical/mixed, need representatives from dataset, noisy data

Density-Based Hierarchical Clustering:

Combines density and hierarchy. Unlike flat K-means, builds tree (dendrogram) where clustering reflects density connectivity at different thresholds.

• Core idea: Clusters are dense regions separated by sparse regions. Define $\epsilon$-neighborhood and $minPts$. Point types: core (≥$minPts$ in $\epsilon$), border, noise. Hierarchical variant (e.g., HDBSCAN, OPTICS, DENCLUE hierarchical) varies $\epsilon$/density threshold to create hierarchy.

• OPTICS: Ordering Points To Identify Clustering Structure — computes reachability distance, produces reachability plot, extracts hierarchy without fixing single $\epsilon$.

• HDBSCAN: Converts DBSCAN to hierarchical, builds minimum spanning tree of mutual reachability, condenses, selects stable clusters via persistence $\lambda=1/distance$.

• Hierarchical density dendrogram: Bottom leaves = core points merge at lowest density threshold as $\epsilon$ increases.

Advantages: Finds arbitrary shapes, handles noise, no need to preset $k$, hierarchy reveals clusters at multiple densities.

Steps generic: Estimate density (kernel), build graph where edges if density > threshold, connected components = clusters, vary threshold → hierarchy, prune unstable branches.