Data Mining

Answer: (i) Clustering Large Application based on RANdomized Search

CLARANS is a medoid-based clustering algorithm for large datasets. Instead of exhaustively scanning all neighbours of a medoid (as PAM does) or drawing random samples once (as CLARA does), it searches the neighbourhood graph of potential medoid sets using a randomised search, jumping to a random neighbour each time a better one is found. The name is the direct expansion of that idea: CLustering Large Applications based on RANdomized Search.

Options (ii) and (iii) substitute incorrect words — 'Least ... Sorting' and 'Labelled ... Search' — neither of which belongs to the actual acronym. Because a correct expansion is given, 'None of the above' is also wrong.

Answer: (iv) All of the above

K-means requires all three inputs before it can run: (i) a distance metric (usually Euclidean) to decide which centroid a point is closest to and to compute within-cluster error; (ii) the number of clusters k, which must be supplied by the user because the algorithm has no way of discovering it; and (iii) an initial guess of the cluster centroids (seed points), which the algorithm then refines by alternating the assignment and update steps.

Since (i), (ii) and (iii) are each genuinely required, no single one of them is the answer — 'All of the above' is correct.

Answer: (iii) Density based

DENCLUE (DEnsity-based CLUstEring) models the overall density of a dataset as a superposition of kernel density functions ('influence functions') contributed by every data point, and then climbs the gradient of this density surface to reach density attractors. Points sharing an attractor form a cluster, so clusters are simply high-density regions separated by low-density regions — the defining property of density-based clustering.

It is not partitioning (it does not split data into k given groups), not hierarchical (it builds no dendrogram), and not grid-based (it does not quantise the space into grid cells). Hence (iii).

Answer: (i) Group of similar objects that differ significantly from other objects

A cluster is defined by intra-cluster similarity and inter-cluster dissimilarity: its members are alike with respect to the attributes of interest, while being distinctly different from objects belonging to other clusters. This is the standard working definition used in cluster analysis.

Option (ii) describes data preprocessing (transforming or simplifying data before learning), and option (iii) describes a knowledge or idea representation from which information is extracted — neither is a cluster. Since (i) is a correct definition, 'None of the above' is wrong as well.

Answer: (iv) Group data points into clusters with high intra-group similarity and low inter-group similarity

Clustering is an unsupervised task: its objective is to partition the data so that objects inside the same cluster are as similar as possible (high intra-cluster similarity) while objects belonging to different clusters are as dissimilar as possible (low inter-cluster similarity). Option (iv) states exactly this criterion, and it is formalised through similarity/distance measures and minimisation of the within-cluster sum of squares.

'Find hidden patterns in data' (ii) is far too vague — it describes data mining as a whole, not clustering specifically. Classifying data into known categories (i) is classification, and predicting future values (iii) is prediction; both are supervised tasks requiring labelled data, so they are wrong.

Answer: (i) Silhouette coefficient

The silhouette coefficient is the standard internal quality measure for clusters. For a point $i$, $s(i) = \dfrac{b(i) - a(i)}{\max\{a(i),\,b(i)\}}$, where $a(i)$ is the average distance to points in its own cluster and $b(i)$ is the average distance to points in the nearest neighbouring cluster. Values lie between $-1$ and $1$; a value near $1$ means the point is well matched to its own cluster and far from every other cluster. Averaging $s(i)$ over all points — or repeating this for several values of $k$ and choosing the best average — is a common way to assess and tune K-means.

Precision, accuracy and F1 score are label-based classification metrics: they need ground-truth classes to compare against. Clustering is unsupervised and has no ground-truth labels, so (ii), (iii) and (iv) do not apply.

Answer: (i) Outliers can distort the cluster centroids

K-means represents each cluster by its centroid, the arithmetic mean of the points assigned to it. The mean is highly sensitive to extreme values, so a single outlier lying far from the data bulk can pull a centroid toward itself, steal points from a genuine cluster, and inflate the within-cluster sum of squares — producing badly shaped or wrongly positioned clusters. Hence outlier detection (removal, or a robust variant such as K-medoids) is performed before and during clustering.

Outliers do not improve clustering accuracy (ii); they should not automatically be absorbed into clusters (iii); and the claim that they have no effect on clustering (iv) is false, precisely because mean-based centroids are sensitive to them.

Answer: (iii) legitimate and illegitimate data objects

In data mining (per Han, Kamber & Pei), outliers are data objects that deviate considerably from the general behaviour or distribution of the rest of the data — and they can be both legitimate and illegitimate:

• Legitimate outliers — genuine data objects that differ from the majority but are still valid data; they themselves are the main interest in some mining tasks (e.g., fraud detection — an unusual transaction is a valuable event worth investigating, not a mistake).
• Illegitimate outliers — objects that arise from noise or errors (sensor malfunction, human data-entry mistakes, measurement glitches); these are unwanted and are usually cleaned/removed during preprocessing.

Because outlier analysis deals with both cases, option (iii) — "legitimate and illegitimate data objects" — is the correct characterization.

Why the others are wrong:

• (i) legitimate only and (ii) illegitimate only — each captures only one side; outliers can be either.
• (iv) None of the above — incorrect since (iii) is correct.

Answer: Four general characteristics of hierarchical clustering

Hierarchical clustering methods build a nested hierarchy (dendrogram) of clusters. Their general characteristics include:

1. No requirement to specify the number of clusters $k$ in advance — the $k$ is chosen afterwards by "cutting" the dendrogram at a chosen similarity/distance level.

2. Agglomerative (bottom-up) or divisive (top-down) — agglomerative starts with each object in its own cluster and repeatedly merges the two most similar clusters (e.g., AGNES/AGNES), while divisive starts with all objects in one cluster and repeatedly splits (e.g., DIANA).

3. Merge/split decisions are based on inter-cluster proximity (distance or similarity between clusters), using linking criteria such as:

   • single-link — distance between the closest members,
   • complete-link — distance between the farthest members,
   • average-link — average inter-cluster distance.

4. The hierarchy is represented by a dendrogram — a tree diagram that records the sequences of merges/splits and the similarity levels at which they occur.

5. They do not backtrack / are irreversible — once two clusters are merged (agglomerative) they are never separated; once a cluster is split (divisive) it is never re-merged.

6. They are deterministic and non-linear — no centroid optimisation; no iterative refinement (unlike k-means).

7. Complexity: typically $O(n^2)$ or more (no need for $k$) — less noisy/sensitive to initial conditions if stable, but costlier than partitioning.

(At least four of the above are usually quoted — e.g., 1, 2, 3, 4.)

Answer: (i) group of similar objects that differ significantly from other objects

In data mining, a cluster is a collection of data objects that are similar to one another within the same cluster and dissimilar to the objects in other clusters. This is the standard textbook definition (Han & Kamber).

Why the others are wrong:

• (ii) describes data transformation/preprocessing (preparing data for a learning algorithm), not a cluster.
• (iii) describes data/information (a symbolic representation from which information can be extracted), not a cluster.
• (iv) None of the above — incorrect since (i) is the correct definition.

Hence a cluster is a group of similar objects that differ significantly from other objects — option (i).

Answer: k-Medoids (PAM) vs k-Means

Criterion	k-Means	k-Medoids (PAM)
Proposed center	Centroid: mean vector of the cluster (arithmetic mean — not necessarily a point in the data set)	Medoid: an actual data object within the cluster that is the most centrally located (minimises total distance to all other objects in the cluster)
Robust to outliers/noise	No — outliers affect the mean and can distort the centre	Yes — the medoid is a real point, so isolated/outlying points affect it much less
Suitable data type	numerical (mean requires numbers)	any — including categorical data (only distances/ dissimilarities needed)
Complexity	cheaper for low/$| often$O(n^2)$ or worse — it must evaluate all candidate medoid swaps
Output	a hard cluster line through "data point at the boundary"	one of the real existing data objects

When to use k-medoids? When outliers/noise are present, or when the data is not numeric (e.g., some categorical/mixed data), or when the interpretation as an existing prototype is necessary.

Summary: k-Means uses a mean (centroid, often invented point); k-Medoids uses a medoid — an existing representative object — making it robust to outliers and usable with non-numeric dissimilarity matrices.

Solution

Correct Answer: (iii) It requires the number of clusters to be specified in advance

Explanation

K-means needs the user to give k, the number of clusters, before it runs. A wrong k gives poor clusters, and the right k is usually unknown. Other limitations: sensitive to outliers, depends on initial centroids, finds only spherical clusters, works on numeric data.

Why other options are incorrect:

• (i) K-means is designed for numerical data.
• (ii) It does not handle outliers well; they pull centroids away.
• (iv) It relies on a distance measure (usually Euclidean).

Answer: (iii) It requires the number of clusters to be specified in advance

Answer: (iv) k-Means

Partitioning clustering methods partition $n$ data objects into $k$ clusters (where $k$ is given in advance) such that each object belongs to the cluster whose centroid (mean) is nearest to it. k-Means is the classic partitioning algorithm:

1. Choose $k$ initial centroids (one per cluster).
2. Assign each object to the cluster of its nearest centroid.
3. Recompute each cluster's centroid as the mean of its member objects.
4. Repeat steps 2–3 until the centroids stop changing.

Input: k, dataset D
Repeat until centroids converge:
    assign each x ∊ D to cluster of nearest centroid
    recompute each centroid = mean of its cluster

Why the others are wrong:

• (i) Apriori — an association-rule mining algorithm (frequent itemset generation), not a clustering method.
• (ii) ID3 — a decision tree classifier.
• (iii) Naïve Bayes — a probabilistic classifier, not a clustering method.

Hence the partitioning clustering method among the options is k-Means.

Answer: (iv) unsupervised learning

Segmenting customers into distinct groups (clusters) in order to send appropriate subscription offers is a clustering task. Since the segments are not known in advance and the algorithm must discover the natural groupings from the data itself, this is unsupervised learning.

Why the others are wrong:

• (i) supervised learning — that requires pre-labelled classes; here there are no pre-defined customer segment labels.
• (ii) data extraction — a preprocessing/retrieval step, not the grouping task.
• (iii) serration — a typo/nonsense option (no such data-mining category).

Hence customer segmentation for targeted offers is an example of unsupervised learning — option (iv).

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

Definition. DBSCAN is a density-based clustering algorithm that groups together points lying in densely populated regions of the data space and marks points lying in sparse regions as noise. Unlike K-means it does not require the number of clusters, it can discover clusters of arbitrary shape, and it handles outliers explicitly.

Key concepts

The algorithm takes two parameters:

• ε (eps) — the radius of a point's neighbourhood, $N_\varepsilon(p) = \{q \mid d(p,q) \le \varepsilon\}$.
• MinPts — the minimum number of points required inside that neighbourhood.

Every point is then classified as:

1. Core point if $|N_\varepsilon(p)| \ge MinPts$.
2. Border point if it lies within ε of a core point but has fewer than MinPts points in its own neighbourhood.
3. Noise point if it is neither core nor border.

A point is density-reachable from a core point if it falls inside that core point's ε-neighbourhood (directly or through a chain of core points). Two points are density-connected if both are density-reachable from some common core point. A cluster is a maximal set of density-connected points.

Algorithm

1. Label every point as unvisited.
2. Pick an unvisited point p and compute $N_\varepsilon(p)$.
3. If $|N_\varepsilon(p)| < MinPts$, label p as noise (it may be relabelled as a border point of a cluster formed later).
4. Otherwise p is a core point: create a new cluster and grow it — insert every point of $N_\varepsilon(p)$; for each newly added point that is itself a core point, expand its neighbourhood too, continuing through the queue until no more core points are reachable.
5. Mark all points added to a cluster as visited and repeat from step 2 until no unvisited points remain.

repeat until no unvisited point is left:
    pick unvisited p, compute N_eps(p)
    |N_eps(p)| <  MinPts --> label p noise (may become border later)
    |N_eps(p)| >= MinPts --> p is a core point: open a new cluster,
                             absorb N_eps(p), then expand through every
                             density-reachable core point
result: set of clusters + noise points

Properties

• Strengths: no need to pre-specify the number of clusters; finds arbitrarily shaped (non-convex) clusters; outliers are reported as noise instead of being forced into a cluster; with a spatial index the neighbourhood search costs about $O(n \log n)$.
• Limitations: one global (ε, MinPts) pair must suit every cluster, so clusters of strongly differing densities are handled poorly; the result is sensitive to the choice of ε and MinPts; effectiveness drops on high-dimensional data, where distances become less meaningful.

Model-Based Clustering: Importance and Commonly Used Models

Definition. Model-based clustering assumes that the observed data is generated by a finite mixture of underlying probability distributions. It estimates the number of clusters together with the parameters of each component, so clustering becomes a problem of statistical model fitting rather than purely geometric partitioning.

1. Importance of model-based clustering

1. Probabilistic, not just geometric. Every object receives a posterior membership probability $P(z_i = k \mid x_i)$, which quantifies clustering uncertainty — something hard-partition methods such as k-means cannot provide.
2. Flexible cluster shapes. Giving each component its own covariance matrix lets the model represent elliptical, elongated and differently oriented clusters, whereas k-means implicitly assumes spherical clusters of equal size.
3. Automatic choice of K. Criteria such as BIC, AIC or ICL select the number of clusters from the data instead of trial-and-error runs with different values of $k$.
4. Statistical rigour. Parameters are estimated by maximum likelihood (usually the EM algorithm), giving a well-defined objective function, convergence behaviour and a basis for comparing competing models.
5. Extra capabilities. The same framework supports imputation of missing values, soft classification, outlier detection and discriminant analysis.
6. Interpretability. The fitted means, covariances and mixing proportions directly describe every cluster.

2. Commonly used models

Model family	Component distribution	Typical data / use
Gaussian (normal) mixture model	$\mathcal{N}(\mu_k, \Sigma_k)$	Continuous data with elliptical clusters — the most common choice
Multinomial mixture	Multinomial	Text/document clustering over word-count vectors
Bernoulli mixture	Bernoulli	Binary data: market-basket and click indicators
Poisson mixture	Poisson	Count data such as arrivals or call volumes
Student-t mixture	$t$-distribution	Robust clustering when outliers are present
Latent class model	Categorical	Survey responses and categorical attributes
Hidden Markov model	States plus emissions	Temporal data: speech, video, biosequences

3. Fitting the models (EM outline)

1. Initialise means mu_k, covariances Sigma_k and weights pi_k
2. E-step: responsibility r_ik = P(z_i = k | x_i, theta)
3. M-step: update mu_k, Sigma_k, pi_k as weighted averages
4. Repeat until the log-likelihood stops increasing
5. Select K by maximising BIC = 2*logL - p*log(n)

4. Typical applications

Customer segmentation with soft memberships, image segmentation, fraud detection, gene-expression analysis and topic modelling.

Conclusion: model-based clustering turns clustering into a principled statistical inference problem — flexible shapes, honest uncertainty and an objective way to choose the number of clusters.

Applying the K-Means Algorithm to a Small Dataset

Definition. K-means is a partitioning (centroid-based) algorithm that splits $n$ objects into $k$ clusters by minimising the within-cluster sum of squares

$$J = \sum_{c=1}^{k}\sum_{x_i \in C_c} \lVert x_i - \mu_c \rVert^2$$

where $\mu_c$ is the centroid of cluster $C_c$.

1. The dataset

The question leaves the data open, so we take $k = 2$ and these six 2-D points:

Point	Coordinates
P1	(1, 1)
P2	(2, 1)
P3	(1, 2)
P4	(8, 8)
P5	(9, 8)
P6	(8, 9)

2. Algorithm steps

1. Choose the number of clusters $k$ and pick $k$ initial centres.
2. Assign every point to the centre with the smallest Euclidean distance $d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$.
3. Recompute each centre as the mean of the points assigned to it.
4. Repeat steps 2-3 until no point changes its cluster.

3. Initialisation

Initial centres: $C_1 = P1 = (1, 1)$ and $C_2 = P4 = (8, 8)$.

4. Iteration 1 - assignment

Point	$d(\cdot, C_1)$	$d(\cdot, C_2)$	Nearest centre
P1 (1,1)	0.00	9.90	$C_1$
P2 (2,1)	1.00	9.22	$C_1$
P3 (1,2)	1.00	9.22	$C_1$
P4 (8,8)	9.90	0.00	$C_2$
P5 (9,8)	10.63	1.00	$C_2$
P6 (8,9)	10.63	1.00	$C_2$

Check: $d(P2, C_2) = \sqrt{(8-2)^2 + (8-1)^2} = \sqrt{36+49} = \sqrt{85} \approx 9.22$.

Recomputed centres:

$$\mu_1 = \left(\frac{1+2+1}{3},\ \frac{1+1+2}{3}\right) = (1.33,\ 1.33)$$

$$\mu_2 = \left(\frac{8+9+8}{3},\ \frac{8+8+9}{3}\right) = (8.33,\ 8.33)$$

5. Iteration 2 - assignment with the new centres

Point	$d(\cdot, C_1)$	$d(\cdot, C_2)$	Nearest centre
P1 (1,1)	0.47	10.37	$C_1$
P2 (2,1)	0.75	9.69	$C_1$
P3 (1,2)	0.75	9.69	$C_1$
P4 (8,8)	9.43	0.47	$C_2$
P5 (9,8)	10.16	0.75	$C_2$
P6 (8,9)	10.16	0.75	$C_2$

Check: $d(P1, C_1) = \sqrt{(1-1.33)^2 + (1-1.33)^2} = \sqrt{0.109 + 0.109} \approx 0.47$.

Membership is identical to iteration 1, the recomputed centres do not move, so the algorithm converges after 2 iterations.

6. Final result

K-means result (k = 2)
----------------------
Cluster 1 : centre (1.33, 1.33) -> P1(1,1), P2(2,1), P3(1,2)
Cluster 2 : centre (8.33, 8.33) -> P4(8,8), P5(9,8), P6(8,9)
Iterations : 2  (no membership change after iteration 2)

7. Points an examiner rewards

• The result is only a local optimum of $J$; k-means++ initialises centres that are well spread out.
• It produces spherical, similarly sized clusters only — non-convex shapes are not found and outliers get no label.
• Empty clusters must be repaired, e.g. re-seeded from the farthest point.
• Choose $k$ with the elbow method or the silhouette coefficient; cost is $O(n \cdot k \cdot i)$ for $i$ iterations.

Clustering Framework for Customer Segmentation

Goal: group customers with similar behaviour so that marketing, pricing and service can be targeted per segment. Clustering is unsupervised: there are no predefined labels.

Framework overview

Business goal -> Data collection -> Preprocessing -> Feature selection
   -> Choose algorithm -> Choose number of clusters -> Handle outliers
   -> Validate clusters -> Profile segments and act

1. Data and business goal

Define what "similar" means. Typical features: RFM (recency, frequency, monetary value), age, income, location, product categories, web and app activity, tenure.

2. Preprocessing

• Missing values: impute (median/mode) or drop sparse columns.
• Duplicates and inconsistencies: merge and standardize.
• Categorical features: one-hot or label encoding (or use a distance made for mixed data).
• Scaling: min-max or z-score, so large-range attributes (income) do not dominate distance.
• Skewed features: log-transform spending data.

3. Feature selection and dimensionality reduction

In high-dimensional data, distances become less meaningful (curse of dimensionality).

• Remove irrelevant and highly correlated features (correlation filter, variance threshold).
• Use PCA to compress correlated features into fewer components.
• Keep features that are meaningful to the business.

4. Choice of clustering algorithm

Algorithm	Best when	Limitation
K-means	Large data, roughly spherical clusters, numeric features	Needs k; sensitive to outliers
Hierarchical	Smaller data, want a dendrogram	Costly for large data
DBSCAN	Arbitrary shapes, noise present, k unknown	Struggles with varying densities
Gaussian mixture (model-based)	Overlapping segments, soft membership	Assumes distribution form
K-prototypes / K-medoids	Mixed numeric and categorical data	Slower

For a large customer dataset, K-means (or mini-batch K-means) is a good start; DBSCAN or GMM can be used to compare.

5. Selecting the number of clusters

• Elbow method: plot within-cluster sum of squares (WCSS) against k and pick the bend.
• Silhouette score: choose the k with the highest average silhouette.
• Gap statistic, or dendrogram cut for hierarchical clustering.
• Business usefulness: the segments must be few enough to act on (often 3 to 8).

6. Outlier handling

Outliers pull centroids and distort K-means.

• Detect with IQR, z-score, Local Outlier Factor or DBSCAN noise points.
• Decide: remove or cap them if they are errors; keep them as a separate group if they are genuine (very high-value customers or fraud).

7. Cluster validation

Type	Measure
Internal (no labels)	Silhouette coefficient (higher is better), Davies-Bouldin index (lower is better), Calinski-Harabasz index (higher is better)
External (if labels exist)	Adjusted Rand Index, purity
Stability	Re-run with different seeds or samples; clusters should stay similar
Business validation	Segments are distinct, interpretable and actionable

8. Interpretation and use

Profile each cluster by its mean feature values, for example high-value loyal, new customers, discount seekers, at risk of churn, and design offers for each. Monitor and re-cluster periodically as behaviour changes.

Conclusion

A good segmentation framework combines careful preprocessing, sensible feature selection, a suitable algorithm, a justified k, robust outlier handling and validation, ending in segments the business can act on.

Density-Based Clustering with a Focus on DBSCAN

Definition. Density-based clustering groups objects that are connected by regions of high point density, separated by regions of low density. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is the classic algorithm of this family.

1. Key definitions

• $\varepsilon$-neighbourhood: $N_\varepsilon(p) = \{q \mid d(p,q) \le \varepsilon\}$, the set of all points within radius $\varepsilon$ of $p$ (the point $p$ itself is counted).
• Core point: $p$ is a core point if $|N_\varepsilon(p)| \ge \text{minPts}$.
• Border point: $p$ lies inside the $\varepsilon$-neighbourhood of at least one core point but is not itself a core point.
• Noise (outlier): $p$ is neither core nor border, so it is not assigned to any cluster.
• Reachability: $q$ is directly density-reachable from $p$ if $q \in N_\varepsilon(p)$ and $p$ is core; density-reachability is the transitive chain of such steps, and two points are density-connected when both are reachable from a common core point.

2. Parameters

• $\varepsilon$ (eps): the neighbourhood radius. Too small leaves everything as noise; too large merges distinct clusters. It is often chosen from the elbow of a k-distance plot.
• minPts: the minimum number of points required to form a dense region. A common rule of thumb is $\text{minPts} \ge d + 1$ for dimensionality $d$; values of 4 or $2d$ are typical.

3. Algorithm steps

DBSCAN(D, eps, minPts)
  for each point p in D:
    if p is already labelled: continue
    N = region_query(p, eps)            # all points within eps of p
    if |N| < minPts: label p as NOISE
    else:
      create new cluster C; move p from noise into C
      seeds = N minus p
      for each q in seeds:
        if q is labelled NOISE: relabel q as a border point of C
        if q is labelled UNVISITED: label q as a member of C
        Nq = region_query(q, eps)
        if |Nq| >= minPts:              # q is core, grow the cluster
          add Nq to seeds

4. Worked illustration

Points on a line, $\varepsilon = 1.5$, $\text{minPts} = 3$:

Point	Co-ordinate	Neighbourhood size	Type	Final cluster
p1	0	2 (p1, p2)	border	C1
p2	1	3 (p1, p2, p3)	core	C1
p3	2	3 (p2, p3, p4)	core	C1
p4	3	2 (p3, p4)	border	C1
p5	10	2 (p5, p6)	border	C2
p6	11	3 (p5, p6, p7)	core	C2
p7	12	2 (p6, p7)	border	C2
p8	20	1 (p8)	noise	none

Processing: p1 alone is too sparse and is first marked as noise; then p2 is found to be a core point, opens cluster C1 and pulls in p1, p3 and p4 (p1 is relabelled as a border point and p3, being core, brings in its neighbour p4). p5 is likewise first flagged as noise and only absorbed when core point p6 opens C2. p8 has no neighbours within $\varepsilon$ and remains noise.

Result: $C1 = \{p1, p2, p3, p4\}$, $C2 = \{p5, p6, p7\}$, noise $= \{p8\}$.

5. DBSCAN vs k-means

Criterion	DBSCAN	k-means
Cluster shape	Arbitrary, non-convex shapes	Spherical only
Number of clusters	Discovered automatically from density	Must be supplied as $k$
Outliers	Explicitly detected as noise	Forced into some cluster
Varying densities	Fails when cluster densities differ greatly	Copes better with unequal sizes
Parameters	$\varepsilon$, minPts	$k$, initialisation
Complexity	$O(n \log n)$ with a spatial index, $O(n^2)$ naively	$O(nkt)$
Main sensitivity	To $\varepsilon$ and minPts	To the choice of seeds

Extensions: OPTICS produces an ordering that removes the need to fix $\varepsilon$ in advance, and HDBSCAN handles clusters of differing density.

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.

Overview of Clustering Approaches (with Examples)

Clustering groups objects so that objects within a cluster are similar and objects in different clusters are dissimilar. The main approaches are:

1. Partitioning Methods

Partition $n$ objects into a pre-specified number $k$ of clusters by iteratively refining the cluster representatives until a criterion (typically the squared error) is minimised.

• Examples: k-Means (mean-based centroid), k-Medoids / PAM (uses actual data points as medoids — robust to outliers).

2. Hierarchical Methods

Create a nested hierarchy (dendrogram) either:

• agglomeratively (bottom-up) — each object is its own cluster initially; repeatedly merge the two closest clusters (AGNES);
• divisively (top-down) — start with one cluster and split (DIANA).
  No $k$ is required in advance — choose it by cutting the dendrogram.
• Examples: AGNES, DIANA, BIRCH (scalable, uses CF-trees), CURE (multiple representative points, handles arbitrary shapes).

3. Density-Based Methods

Clusters are dense regions of points separated by low-density areas. They can find clusters of arbitrary shape and naturally identify noise.

• Examples: DBSCAN (dense regions via ε-neighbourhood and MinPts: core/border/noise points), OPTICS (handles varying densities), DENCLUE.

4. Grid-Based Methods

Overlay the data space with a grid of cells and do the clustering on the cells, not on individual objects — the cost depends on the number of cells, not on the number of data objects, so clustering is very fast.

• Examples: STING (statistical summaries per cell), CLIQUE (grid + subspace), WaveCluster.

5. Model-Based Methods

Assume the data follow a probabilistic (mixture) model — one probability distribution per cluster — and find the model that best fits the data (highest likelihood). Membership becomes a probability rather than a hard assignment.

• Examples: EM (Expectation–Maximization) for Gaussian mixtures, Self-Organising Maps (Kohonen nets), COBWEB (conceptual clustering).

6. Methods for High-Dimensional Data

In high dimensions distances concentrate and standard clustering degrades (curse of dimensionality). Approaches:

• subspace clustering — find clusters in lower-dimensional subspaces;
• co-clustering / bi-clustering — group rows and columns simultaneously (common in gene-expression analysis);
• dimension-reduction pre-processing, e.g. PCA, before clustering.
• Examples: CLIQUE, PROCLUS (projected clustering), co-clustering / block clustering.

7. Constraint-Based Methods

Perform clustering subject to user or application constraints, e.g. must-link / cannot-link pairs, or spatial obstacles.

• Examples: COD (Clustering with Obstacles), COP-KMEANS (must-link / cannot-link constraints).

Summary Table

Approach	Core idea	Example
Partitioning	split into k clusters, iterate	k-means, PAM
Hierarchical	nested dendrogram; merge/split	AGNES, BIRCH, CURE
Density-based	dense regions separated by sparse areas	DBSCAN, OPTICS
Grid-based	operate on grid cells	STING, CLIQUE
Model-based	fit a probability model	EM / GMM, SOM
High-dimensional	subspace / co-clustering	CLIQUE, PROCLUS
Constraint-based	obey background constraints	COP-KMEANS, COD

Partitioning Methods vs Hierarchical Methods in Cluster Analysis

Definition. Partitioning methods decompose the data set directly into a fixed number of non-overlapping clusters, while hierarchical methods build a nested hierarchy of clusters, usually displayed as a dendrogram, and reach a partition by cutting that tree.

1. Partitioning methods

• Idea: one flat partition of $n$ objects into $k$ clusters, $k$ specified in advance.
• Representative algorithms: k-means (centroid), k-medoids/PAM (representative object), CLARA and CLARANS for large data, k-modes for categorical data.
• Typical criterion: minimise the within-cluster sum of squares $J = \sum_{c=1}^{k}\sum_{x_i \in C_c} \lVert x_i - \mu_c \rVert^2$ by iterative relocation: assign, recompute, repeat until no change.
• Properties: fast ($O(nkt)$ for k-means), simple, but produces only one flat solution, is sensitive to initialisation and to outliers, and tends to find spherical clusters of similar size.

2. Hierarchical methods

• Idea: produce a sequence of nested partitions rather than one; no $k$ needed up front.
• Agglomerative (bottom-up): start with $n$ singletons, repeatedly merge the two closest clusters until one remains.
• Divisive (top-down): start with all data in one cluster and recursively split it.
• Linkage criteria: single (minimum distance between clusters, chaining effect), complete (maximum distance), average (UPGMA), Ward (minimum increase in within-cluster variance).
• Properties: yields a dendrogram, reveals structure at every granularity, is deterministic, but costs $O(n^2 \log n)$ or $O(n^3)$ time and $O(n^2)$ memory, and merges once made are irreversible.

Dendrogram (agglomerative)

|                  +---- P6
|             +----+---- P5
|        +----+----+---- P4
|   +----+----+---- P3
+---+----+----+---- P2
    +----+----+---- P1
    |         |         |\    height -> distance at which clusters merge

3. Comparison

Criterion	Partitioning (k-means)	Hierarchical (agglomerative)
Output	One flat partition	Nested hierarchy / dendrogram
Number of clusters $k$	Must be fixed in advance	Chosen afterwards by cutting the tree
Approach	Iterative relocation of assignments	Greedy merging or splitting
Reversibility	Reassignments allowed, non-monotonic	Merges are permanent and monotonic
Repeatability	Depends on random seeds	Deterministic for a fixed linkage
Scalability	$O(nkt)$, good for large $n$	$O(n^2 \log n)$, poor for very large $n$
Cluster shape	Spherical, similar sizes	Any shape, depends on linkage
Outliers	Absorbed into clusters	Can be isolated early as singleton branches
Interpretability	Centroids only	Full dendrogram of relationships

4. When to use which

Use partitioning when the data is large, $k$ is known (e.g. $k$ customer segments) and a single flat answer is enough. Use hierarchical methods when the nesting itself is the insight — taxonomy building, gene-family trees, or when $k$ is unknown and the analyst will decide by cutting the dendrogram. Bisecting k-means and BIRCH combine the two ideas: BIRCH builds a compact summary tree first and then partitions it.

Main Requirements for Cluster Analysis

Following Han, Kamber & Pei (Data Mining: Concepts and Techniques), the key requirements that a good clustering method should satisfy are:

1. Scalability

The method must work efficiently on large databases — ideally near-linear (or sub-quadratic) in the number of objects $n$. Many classic algorithms degrade badly on millions of tuples.

2. Ability to deal with different types of attributes

Real data contains numerical, categorical (binary/nominal), ordinal, and mixed attributes. The clustering method should handle all these types (often by using an appropriate dissimilarity matrix).

3. Discovery of clusters of arbitrary shape

Clusters are not always spherical/ball-like. A good method should find clusters of arbitrary shape (e.g., elongated, concave, "C"-shaped) — density-based methods (DBSCAN, OPTICS) do this well, whereas k-Means cannot.

4. Minimal requirements for domain knowledge / input parameters

Clustering should require as few user-supplied parameters as possible (e.g., $k$ for k-Means, $\varepsilon$/MinPts for DBSCAN), because guessing them needs domain knowledge and a wrong guess harms the result. Ideally parameters should be easy to determine.

5. Ability to deal with noisy data

Real data contains noise and outliers. The method should be robust so that noise does not seriously distort the discovered clusters, and outliers should be handled (detected or tolerated).

6. Insensitivity to input order / incremental updatability

The same result should be obtained no matter the order in which input records are presented, and the method should support incremental updates when new data arrive (important for data warehouses that get refreshed).

7. High dimensionality

Distances concentrate in high-dimensional spaces ("curse of dimensionality"). A suitable method should either work well in high dimensions or use subspace/feature-selection strategies.

8. Interpretability and usability

The resulting clusters should be interpretable, comprehensible, and usable — the user must be able to understand and act on the discovered grouping.

9. Constraint-based clustering

Real applications often impose constraints (must-link / cannot-link, or spatial/budget constraints); the method should be able to incorporate them to produce domain-appropriate clusters.

---

Summary: a good clustering algorithm must be scalable, robust to noise, general (arbitrary shapes, mixed data types), minimal-parameter, order-insensitive, high-dimensionality-aware, and interpretable.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN is a density-based clustering algorithm that groups points that are closely packed together, marking points in low-density regions as noise. It finds clusters of arbitrary shape and needs no predefined number of clusters $k$.

Key Concepts

• ε-neighbourhood (Eps): for a point $p$, the set of points within distance $\varepsilon$ of $p$.
• MinPts: minimum number of points required to form a dense region.
• A point $p$ is:
  • a core point if its ε-neighbourhood contains at least MinPts points (including itself);
  • a border point if it is within the ε-neighbourhood of a core point but is not itself a core point;
  • a noise point if it is neither core nor border.

Algorithm

DBSCAN(D, Eps, MinPts)
1. Mark all points as unvisited.
2. For each unvisited point p in D:
     a. find all points q within Eps of p (N_eps(p));
     b. if |N_eps(p)| < MinPts → mark p as noise (temporarily);
     c. else make p a new cluster C and expand:
          - for every point q in N_eps(p): if q is unvisited,
            mark q visited, find its neighbourhood,
            if q is a core point add its neighbours to the cluster,
            if q was labelled noise, add q to cluster C.
3. Repeat until all points are processed.

Expansion merges any overlapping dense neighbourhoods: cluster grows by absorbing every point reachable through a chain of core points.

Properties

• Detects clusters of arbitrary shape (e.g., donut/C shapes), unlike k-Means.
• Handles noise/outliers explicitly.
• Needs only two parameters (Eps, MinPts) — no $k$ in advance.
• Sensitivity: results depend strongly on a good choice of Eps and MinPts (often found via a k-distance graph).
• Complexity: O(n log n) with a spatial index (e.g., R-tree); O(n²) without.

    ● ● ●   (dense region = cluster)
  ● ● ● ● ●
    ● ● ●
         ●            ← noise point (isolated)

Here the dense blob forms one cluster and the isolated point is flagged as noise.

Basic Clustering Methods

The fundamental clustering approaches, with their ideas and typical algorithms:

1. Partitioning Methods

Divide the $n$ objects into $k$ clusters (given in advance) by iteratively refining cluster representatives (centroids/medoids) until a criterion such as the squared error is minimised.

$$E = \sum_{i=1}^{k}\sum_{x \in C_i} \|x - \mu_i\|^2$$

• Examples: k-Means (mean centroid), k-Medoids/PAM (actual data object as representative, robust to outliers).

2. Hierarchical Methods

Create a nested hierarchy of clusters (dendrogram):

• agglomerative (bottom-up): start with every object as its own cluster, repeatedly merge the closest two;
• divisive (top-down): start with one cluster, repeatedly split.
  No $k$ is needed upfront — the user "cuts" the dendrogram later.
• Examples: AGNES, DIANA, BIRCH (scalable via CF-trees), CURE (multiple representatives, arbitrary shapes).

3. Density-Based Methods

Clusters are dense regions of points separated by low-density (sparse) regions. Can discover clusters of arbitrary shape and explicitly mark noise.

• Examples: DBSCAN (ε-neighbourhood + MinPts), OPTICS, DENCLUE.

4. Grid-Based Methods

Partition the data space into a grid of cells and cluster on the cells rather than on individual points — cost depends on number of cells, not on data size, so these methods are very fast.

• Examples: STING (statistical summaries per cell), CLIQUE (grid + subspace clustering), WaveCluster.

5. Model-Based Methods

Assume each cluster follows a probability distribution (e.g., Gaussian) and find the model that best fits the data (maximising likelihood). Membership becomes probabilistic rather than hard.

• Examples: EM (Expectation–Maximization / Gaussian mixture), Self-Organising Maps (SOM), COBWEB (conceptual clustering).

---

Comparison table

Method	Key idea	k needed?	Shapes	Complexity (typical)
Partitioning	refine k centroids/medoids	Yes	spherical	O(n·k·iterations)
Hierarchical	merge/split into a dendrogram	No	any (linkage-dependent)	O(n²)–O(n³)
Density-based	dense regions separated by sparse	No	arbitrary	O(n log n) w/ index
Grid-based	cluster on grid cells	No	arbitrary	depends on grid size
Model-based	fit probability distributions	No (AIC/BIC)	distribution-shaped	iterative EM

These five form the basic taxonomy of clustering methods in data mining.

Cluster Analysis and the Major Clustering Methods

1. What is cluster analysis?

Cluster analysis (clustering) is the task of grouping a set of physical or abstract objects into classes (clusters) of similar objects, so that objects within a cluster are highly similar to one another and as dissimilar as possible to objects in other clusters. It is an unsupervised learning task - no class labels are supplied, and the grouping emerges from the data itself. Similarity is usually measured by distance functions such as Euclidean, Manhattan or cosine distance.

Requirements of a good clustering algorithm: scalability to large data sets, ability to deal with different attribute types, minimal dependence on domain knowledge, discovery of clusters of arbitrary shape, robustness to noise and outliers, and interpretable results.

2. Categorisation of major clustering methods

Method	Representative algorithms	Key idea
Partitioning	k-means, k-medoids (PAM), CLARANS	Build k partitions that minimise a cost function; clusters are spherical and described by prototypes (centroids)
Hierarchical	AGNES, DIANA, BIRCH, CURE, CHAMELEON	Create a nested hierarchy (tree / dendrogram) of clusters, either bottom-up (agglomerative) or top-down (divisive)
Density-based	DBSCAN, OPTICS, DenCLUE	A cluster is a continuous region of high point density separated by regions of low density; finds arbitrary shapes and marks noise
Grid-based	STING, CLIQUE, WaveCluster	Quantise the object space into a finite number of cells on a grid and operate on the grid - very fast, resolution-dependent
Model-based	EM (Gaussian mixtures), COBWEB, SOM	Assume a statistical or neural model for each cluster and fit the data to it (e.g. maximise likelihood)

Brief explanation:

1. Partitioning methods - start with a random or sampled set of k representatives and iteratively reassign points to the nearest representative until convergence (e.g. Lloyd's k-means). Fast and simple, but need k in advance and favour convex clusters.
2. Hierarchical methods - produce a dendrogram that the analyst can cut at any level; no need to prespecify k, but merges/splits are irreversible and a naive implementation costs $O(n^3)$ time and $O(n^2)$ memory.
3. Density-based methods - grow clusters from dense seeds, so the number of clusters and the cluster shape are discovered automatically and noise is handled naturally.
4. Grid-based methods - move the computation from individual objects to cells, giving constant-time complexity with respect to the number of data objects.
5. Model-based methods - treat clusters as probability distributions or neural units, giving a principled statistical framework (but assuming a particular model form).

Q8(b) - K-means Clustering of the Eight Points

Data: $A_1(2,10), A_2(2,5), A_3(8,4), B_1(5,8), B_2(7,5), B_3(6,4), C_1(1,2), C_2(4,9)$; $k = 3$; Euclidean distance $d(P,Q)=\sqrt{(x_P-x_Q)^2+(y_P-y_Q)^2}$; initial centres $A_1, B_1, C_1$.

Algorithm: (1) assign every point to the nearest centre, (2) recompute each centre as the mean of its cluster, (3) repeat until no membership changes.

Iteration 1 - centres $A_1(2,10)$, $B_1(5,8)$, $C_1(1,2)$

Point	$d$ to $(2,10)$	$d$ to $(5,8)$	$d$ to $(1,2)$	Nearest
$A_1(2,10)$	0.000	3.606	8.062	A
$A_2(2,5)$	5.000	4.243	3.162	C
$A_3(8,4)$	8.485	5.000	7.280	B
$B_1(5,8)$	3.606	0.000	7.211	B
$B_2(7,5)$	7.071	3.606	6.708	B
$B_3(6,4)$	7.211	4.123	5.385	B
$C_1(1,2)$	8.062	7.211	0.000	C
$C_2(4,9)$	2.236	1.414	7.616	B

Clusters after iteration 1

• Cluster A = $\{A_1\}$, centre $= (2,10)$
• Cluster B = $\{A_3, B_1, B_2, B_3, C_2\}$, centre $= \left(\frac{8+5+7+6+4}{5},\frac{4+8+5+4+9}{5}\right) = (6,6)$
• Cluster C = $\{A_2, C_1\}$, centre $= \left(\frac{2+1}{2},\frac{5+2}{2}\right) = (1.5,3.5)$

Iteration 2 - centres $(2,10)$, $(6,6)$, $(1.5,3.5)$

Point	$d$ to $(2,10)$	$d$ to $(6,6)$	$d$ to $(1.5,3.5)$	Nearest
$A_1(2,10)$	0.000	5.657	6.519	A
$A_2(2,5)$	5.000	4.123	1.581	C
$A_3(8,4)$	8.485	2.828	6.519	B
$B_1(5,8)$	3.606	2.236	5.701	B
$B_2(7,5)$	7.071	1.414	5.701	B
$B_3(6,4)$	7.211	2.000	4.528	B
$C_1(1,2)$	8.062	6.403	1.581	C
$C_2(4,9)$	2.236	3.606	6.042	A

Clusters after iteration 2

• Cluster A = $\{A_1, C_2\}$, centre $= \left(\frac{2+4}{2},\frac{10+9}{2}\right) = (3,9.5)$
• Cluster B = $\{A_3, B_1, B_2, B_3\}$, centre $= \left(\frac{8+5+7+6}{4},\frac{4+8+5+4}{4}\right) = (6.5,5.25)$
• Cluster C = $\{A_2, C_1\}$, centre $= (1.5,3.5)$ (unchanged)

Iteration 3 - centres $(3,9.5)$, $(6.5,5.25)$, $(1.5,3.5)$

Point	$d$ to $(3,9.5)$	$d$ to $(6.5,5.25)$	$d$ to $(1.5,3.5)$	Nearest
$A_1(2,10)$	1.118	6.538	6.519	A
$A_2(2,5)$	4.610	4.507	1.581	C
$A_3(8,4)$	7.433	1.953	6.519	B
$B_1(5,8)$	2.500	3.133	5.701	A
$B_2(7,5)$	6.021	0.559	5.701	B
$B_3(6,4)$	6.265	1.346	4.528	B
$C_1(1,2)$	7.762	6.388	1.581	C
$C_2(4,9)$	1.118	4.507	6.042	A

Note that $B_1$ moves from cluster B to cluster A. New centres:

• Cluster A = $\{A_1, B_1, C_2\}$, centre $= \left(\frac{2+5+4}{3},\frac{10+8+9}{3}\right) = (3.67,9)$
• Cluster B = $\{A_3, B_2, B_3\}$, centre $= \left(\frac{8+7+6}{3},\frac{4+5+4}{3}\right) = (7,4.33)$
• Cluster C = $\{A_2, C_1\}$, centre $= (1.5,3.5)$

Iteration 4 - centres $(3.67,9)$, $(7,4.33)$, $(1.5,3.5)$

Point	$d$ to $(3.67,9)$	$d$ to $(7,4.33)$	$d$ to $(1.5,3.5)$	Nearest
$A_1(2,10)$	1.944	7.557	6.519	A
$A_2(2,5)$	4.333	5.044	1.581	C
$A_3(8,4)$	6.616	1.054	6.519	B
$B_1(5,8)$	1.667	4.177	5.701	A
$B_2(7,5)$	5.207	0.667	5.701	B
$B_3(6,4)$	5.518	1.054	4.528	B
$C_1(1,2)$	7.491	6.438	1.581	C
$C_2(4,9)$	0.333	5.548	6.042	A

The memberships are identical to iteration 3, so no point moves, the centres would not change any further, and the algorithm converges.

Final result

Cluster	Points	Final centre
Cluster 1 (A)	$A_1(2,10),\ C_2(4,9),\ B_1(5,8)$	$(3.67,\ 9)$
Cluster 2 (B)	$A_3(8,4),\ B_2(7,5),\ B_3(6,4)$	$(7,\ 4.33)$
Cluster 3 (C)	$A_2(2,5),\ C_1(1,2)$	$(1.5,\ 3.5)$

The three groups are geometrically sensible: a top-left group around $(3.67,9)$, a right-hand group around $(7,4.33)$, and a bottom-left group around $(1.5,3.5)$.

Curse of Dimensionality in Clustering and How Model-Based Methods Cope

Definition. The curse of dimensionality refers to the phenomena that appear when the number of attributes $d$ becomes large: statistical, geometric and computational techniques that work in low dimensions break down.

1. What goes wrong in high dimensions

1. Distance concentration. For random points, the difference between the nearest and farthest neighbour shrinks relative to the distances themselves. If $d_{max}$ and $d_{min}$ are the farthest and nearest distances from a query point, then the relative contrast $R = (d_{max} - d_{min})/d_{min}$ tends to 0 as $d \to \infty$: all points become almost equidistant, so nearest-neighbour, k-means and density-based rules lose their discriminating power.
2. Sparsity of the space. The volume of a unit hypercube grows as $1^d$ exponentially, while data samples grow only linearly. To keep the same occupancy one would need exponentially many points, so observed data occupies a vanishing fraction of the space — clusters that look dense in 2-D become empty regions in high $d$.
3. Concentration at the boundary. In high dimensions almost all the volume of a hypercube lies in its corners and near its surface, so intuition built from 2-D/3-D pictures no longer applies.
4. Density estimation fails. Histograms and kernel estimates need samples exponential in $d$; DBSCAN's eps neighbourhoods become empty or contain all points at once.
5. Spurious correlations and overfitting. With many attributes, chance patterns look like structure, and models fit noise.
6. Cost. Every distance or similarity computation is $O(d)$, making mining slow as well as unreliable.

2. How model-based clustering helps

Aspect	Effect
Parametric assumption	A mixture of $K$ Gaussians in $d$ dimensions is described by only $O(K d^2)$ parameters, whereas a non-parametric density estimate would need exponentially many samples — the model imposes structure that the data cannot supply
Joint distribution	Covariance matrices model correlations between attributes, so redundant dimensions do not each add independent noise to the comparison
Latent structure	Extensions such as factor analysis and probabilistic PCA assume data lies near a low-dimensional subspace, explicitly reducing the effective dimension before clustering
Regularised estimation	Covariance shrinkage and tied/diagonal covariance options stop the $d(d+1)/2$ covariance terms from being estimated from too little data
Model selection	BIC penalises the parameter count, discouraging over-complex models that would simply memorise noise in high dimensions
Probabilistic output	Membership probabilities degrade gracefully, instead of forcing a meaningless nearest-centre assignment when all distances are nearly equal
Outlier handling	Heavy-tailed components (Student-$t$ mixtures) absorb anomalous points instead of pulling centroids around

3. Limitations to mention

Even mixture models struggle when $d$ is large relative to $n$; in practice they are combined with dimensionality reduction (PCA), feature selection or subspace clustering (e.g. PROCLUS, CLIQUE) before fitting.

Conclusion: dimensionality destroys clustering mainly through distance concentration and exponential sparsity; model-based methods respond by imposing a compact probabilistic form, exploiting attribute correlations and selecting complexity through BIC.

Short Note on Hierarchical Clustering

1. Definition

Hierarchical clustering creates a nested hierarchy (a tree) of clusters in which clusters at one level are merged (or split) to form clusters at the next level. The result is usually displayed as a dendrogram - a tree diagram whose vertical axis shows the distance (or dissimilarity) at which each merge/split occurs. Cutting the dendrogram at any height gives a flat clustering with a chosen number of clusters.

2. Two approaches

1. Agglomerative (bottom-up, the most common): start with each object as a singleton cluster ($n$ clusters) and repeatedly merge the two closest clusters until only one cluster remains. $n-1$ merges are needed.
2. Divisive (top-down): start with one cluster containing all objects and repeatedly split the least homogeneous cluster until every object is a singleton. It is less used because deciding which cluster to split is computationally harder ($2^{n-1}-1$ possible splits for $n$ objects).

3. How "closest" is measured - linkage criteria

• Single linkage (minimum distance): distance between the two nearest members of the two clusters. Fast, can find elongated (non-elliptical) clusters, but suffers from the chaining effect - a few noise points can link two large clusters.
• Complete linkage (maximum distance): distance between the two farthest members. Produces compact, equally sized clusters, but is sensitive to outliers.
• Average linkage (UPGMA): average of all pairwise distances between the members of the two clusters - a compromise between single and complete linkage.
• Ward's method: merges the pair whose merge increases the total within-cluster variance the least; tends to give clusters of similar size.
• Centroid linkage: distance between the centres (means) of the two clusters.

4. Illustration

 distance
    |                    +--------------------+
 4  |                    |
    |              +-----+-----+
 3  |              |           |
    |        +-----+-----+     |
 2  |        |     |     |     |
    |   +----+--+ +--+ +--+    |
 1  |   |    |  | |  | |  |    |
    +---+----+--+ +--+ +--+----+-----------> objects
        o1   o2   o3  o4  o5   o6

Clusters {o1,o2} and {o3,o4} form first, then merge into one cluster at a higher level, and the whole set joins at the top; cutting at height 2 gives, say, three clusters.

5. Merits, demerits and variants

• Merits: no need to prespecify the number of clusters $k$ in advance; the dendrogram is easy to interpret and shows the natural nesting of groups at several abstraction levels.
• Demerits: merge/split decisions are irreversible (an early wrong merge cannot be undone); a naive implementation costs $O(n^3)$ time and $O(n^2)$ memory to maintain the distance matrix, so it does not scale well to very large data sets; sensitive to noise and to the choice of linkage.
• Scalable variants: BIRCH (clustering feature tree, incremental), CURE (uses well-scattered representative points), CHAMELEON (uses a $k$-NN graph and dynamic modelling), and ROCK (for categorical data).

Clustering & Model-Based Clustering

Definition of Clustering

Clustering is the process of grouping a set of data objects into classes (clusters) so that objects within the same cluster are as similar to one another as possible, and objects in different clusters are as dissimilar as possible. It is an unsupervised learning task because no class labels are assumed known in advance. Similarity/dissimilarity is usually measured by a distance (Euclidean, Manhattan, etc.) or by correlation.

Example: grouping customers by purchasing behaviour into clusters such as "low spenders", "regular buyers", "occasional big-ticket buyers", etc.

Clustering is used for data compression, outlier detection, market segmentation, bioinformatics (gene grouping), and as a pre-processing step for other mining tasks.

Model-Based Clustering Techniques

Model-based methods assume that the data fit a probabilistic (statistical mixture) model, and try to find the best fit of the data to the assumed model, usually by maximising the likelihood of the model having generated the observed data. Each cluster is modelled by a probability distribution (e.g., a Gaussian) rather than by a centroid alone.

1. Statistical approach — Expectation–Maximization (EM) for Gaussian mixtures (GMM).
Assume the data come from a mixture of $K$ Gaussian distributions; each cluster is one component distribution with its own mean $\mu_k$ and covariance $\Sigma_k$, mixed with weight $\pi_k$. EM iterates two steps:

• E-step (expectation): compute for every point its probability (responsibility) of belonging to each cluster using Bayes' rule:

$$\text{responsibility}(i,k) = \frac{\pi_k \, p(x_i \mid \mu_k, \Sigma_k)}{\sum_j \pi_j p(x_i \mid \mu_j, \Sigma_j)}$$

• M-step (maximisation): re-estimate the parameters $\pi_k$, $\mu_k$, $\Sigma_k$ by maximising the expected likelihood, using each point's responsibility values as weights.

The two steps are repeated until the likelihood (or the parameters) converges. Each object is assigned to the cluster for which its responsibility is highest.

2. Neural-network/symbolic models (self-organising maps, SOM).
Each cluster corresponds to a node (neuron) with a prototype; competitive learning adjusts the winning neuron and its neighbourhood, producing clusters on a low-dimensional map.

3. Fuzzy / probabilistic clustering (fuzzy c-means).
Instead of a hard assignment, every point receives a degree of membership in every cluster (between 0 and 1), a fuzzy generalisation of model-based membership.

4. Model selection.
The appropriate number of clusters $K$ can be chosen using statistical criteria such as BIC (Bayesian Information Criterion) or AIC, comparing how well models with different $K$ fit the data.

Advantages of model-based clustering:

• Can model clusters of different shapes, sizes and orientations (through each cluster's covariance), unlike k-Means.
• Provides a probabilistic interpretation — each object has posterior membership probabilities.
• Offers a sound statistical basis (likelihood), and $K$ need not be fixed exactly — model-selection criteria guide the choice.

Limitations:

• A parametric form must be assumed; if the assumption is wrong, the results may be poor.
• EM can converge to a local optimum, is sensitive to initial parameters, and is computationally heavier than simple partitioning methods.

      cluster 1                    cluster 2
  (Gaussian: μ1, Σ1)          (Gaussian: μ2, Σ2)
      ~~~~~︿~~~~                 ~~~~~︿~~~~
   EM assigns each point to the most likely bell
   curve (posterior probability) → soft membership

Noise vs Outliers — Differences and Answers

Definitions

• Noise is the random (or nonsystematic) component or distortion in the measured data — e.g., typing errors, random measurement error, or blurred/unclear attributes. It is the random part of a value that obscures the true pattern.
• Outliers are data objects (points, tuples) that behave very differently from the general behaviour or distribution of the rest of the data — they always deviate systematically in some interesting direction.

Aspect	Noise	Outliers
Source	random errors / random fluctuations	occasional exceptional data (can be legitimate interest or genuine anomaly)
Form	adds fuzziness to many points	a few points deviate strongly from the bulk
Data quality	generally removed/cleaned	can be kept (they may BE the target in fraud detection)
Relationship	noise can cause outliers	outliers are not necessarily noise

(i) Is noise ever interesting or desirable? Are outliers?

• Noise is usually not interesting or desirable — it is an undesirable error component; however some randomness/perturbation can be used in simulation or regularisation.
• Outliers ARE often interesting/desirable: in fraud detection, network intrusion, and medical anomaly detection an unusual tuple may be exactly what we are mining for.

(ii) Can noise objects be outliers?

Yes. Since noise is random error, in a small data set a noisy point can easily appear as an outlier — a tuple that deviates strongly from the rest — thereby becoming an outlier (noise-generated outlier).

(iii) Can noise make a typical value unusual or vice-versa?

Noise can easily change a typical attribute value into an unusual one (e.g., the measured age of a person typed 218 instead of 28 → the noisy value looks like an outlier). Conversely, an outlier can't become a "typical" point merely by adding noise; but noise can randomly mask a true-outlier so it appears normal/typical (e.g., extreme transaction value 4500 accidentally recorded as 450 masks it as uninteresting noise). So yes, noise can make a typical value look unusual and noise can also make an unusual value look typical.

  Tuples within same cluster are similar; different clusters are dissimilar.
  Clusters can be of arbitrary shape; outliers/noise are explicitly marked.
                                    |
              ┌─────────┴─────────┐
             ● ● ●        noise point

Summary

• Noise: random measurement error; usually removed/ignored.
• Outliers: genuinely deviant points; can be interesting and kept.
• Overlap: noise can produce outliers; outliers are not always noise; and noise can mask or create apparently "normal"/"unusual" values.

Categorization of Major Clustering Methods

Clustering groups data objects so that objects in the same cluster are similar to each other and different from objects in other clusters. It is unsupervised learning. The major methods are grouped into five categories.

1. Partitioning methods

Divide n objects into k partitions (clusters), each object belonging to one cluster; the user gives k.

• K-means: each cluster is represented by its mean (centroid); objects are repeatedly assigned to the nearest centroid.
• K-medoids (PAM, CLARA, CLARANS): each cluster is represented by an actual object (medoid); less sensitive to outliers.
• Good for spherical clusters of similar size and for large data; needs k.

2. Hierarchical methods

Build a tree of clusters (dendrogram).

• Agglomerative (bottom-up): start with each object as a cluster and merge the closest.
• Divisive (top-down): start with one cluster and split.
• Linkage: single, complete, average. Variants: BIRCH, CURE, Chameleon.
• No k needed in advance, but a merge or split cannot be undone and it is costly for big data.

3. Density-based methods

A cluster is a dense region of objects separated by regions of low density.

• DBSCAN (parameters eps and MinPts), OPTICS, DENCLUE.
• Finds arbitrary-shaped clusters and handles noise; k not needed; struggles with varying densities.

4. Grid-based methods

Quantize the space into a finite number of grid cells and cluster the cells.

• STING, CLIQUE, WaveCluster.
• Very fast: the time depends on the number of cells, not on the number of objects.

5. Model-based methods

Assume a mathematical model for each cluster and fit the data to it.

• EM (Expectation-Maximization) with Gaussian mixtures, COBWEB (conceptual clustering), SOM (self-organizing maps).
• Gives soft (probabilistic) membership; depends on the assumed model.

Summary table

Category	Basic idea	Examples	Strength	Weakness
Partitioning	Split into k groups, iteratively optimize	K-means, K-medoids	Simple, scalable	Needs k, spherical shapes, outliers
Hierarchical	Tree of merges/splits	AGNES, DIANA, BIRCH	Dendrogram, no k	Not scalable, no undo
Density-based	Dense regions	DBSCAN, OPTICS	Arbitrary shapes, noise	Parameter sensitivity
Grid-based	Grid cells	STING, CLIQUE	Fast	Less accurate boundaries
Model-based	Statistical model fit	EM, COBWEB, SOM	Soft clusters	Model assumptions

Some methods combine ideas from several categories (for example high-dimensional and constraint-based clustering).

Conclusion

The right method depends on data size, cluster shape, presence of noise and whether k is known.