Partitioning vs Hierarchical Clustering & Outlier Analysis

Partitioning vs Hierarchical Clustering

Partitioning clustering (e.g., k-Means, k-Medoids) partitions $n$ objects into a fixed number $k$ of clusters such that each object belongs to the cluster whose centroid/medoid is nearest. The clusters are then iteratively refined to improve the squared-error objective (SSE); the output is a single, flat, non-nested set of $k$ clusters.

Hierarchical clustering (AGNES agglomerative / DIANA divisive) produces a nested hierarchy (dendrogram). Agglomerative (bottom-up) methods start with each object in its own cluster and repeatedly merge the most similar pairs; divisive (top-down) methods start with one cluster and repeatedly split.

Aspect	Partitioning	Hierarchical
Number of clusters $k$	must be specified in advance	decided later by cutting the dendrogram
Output form	single flat set of $k$ clusters	nested dendrogram
Similarity	distance to centroid/medoid	inter-cluster distance (single/complete/average link)
Scalability	works well on large datasets ($O(nkt)$ for k-Means)	expensive ($O(n^2)$ to $O(n^3)$), best for small data
Flexibility	iteratively re-partitions; centroids move	merge/split is irreversible (greedy, no backtracking)
Data stored	centroids / medoids only	pairwise distances

Summary: Partitioning is fast and scalable but needs $k$ and is sensitive to initial centroids; hierarchical clustering needs no $k$, gives richer (nested) information via the dendrogram, but is computationally heavier and cannot undo an earlier merge.

Outlier Analysis

Outliers are data observations that deviate considerably from the general behaviour or distribution of the rest of the data. They can arise from noise/errors (measurement or data-entry mistakes) or may be genuinely interesting events (fraud, intrusion, novelty).

Detection approaches:

1. Statistical (distribution-based) — assume the data fits a known distribution; objects that fall in the low-probability tails (e.g., beyond $3\sigma$) are outliers.
2. Distance-based — an object is an outlier if most of its neighbours are farther than a threshold (i.e., it has few neighbours within a radius).
3. Density-based — points lying in low-density regions are outliers (e.g., Local Outlier Factor, LOF).
4. Clustering-based — objects that do not belong to any cluster, or variation far from their cluster centre, are flagged as outliers.

Importance in data mining:

• Outliers can skew the results of clustering, regression, and classification — they heavily influence means, centroids, and learned decision boundaries, degrading accuracy.
• Outlier detection is itself a worthwhile mining task: used for fraud detection (unauthorised credit-card transactions), network intrusion detection, medical anomaly detection, and data-quality cleaning (identify and remove noisy records before modelling).
• Robust statistical techniques/ensembles often must first isolate outliers so that subsequent models are dependable.