Hierarchical Clustering and Density-Based Clustering

15.1 Hierarchical Clustering: Two Strategies, No K

15.1.1 Why Build a Tree Instead of Picking K

K-means needs the value of K before it can run, and finding the right K is very hard. The lecture's point is blunt: the number of natural groups is usually not known in advance, and trial-and-error on K is expensive and subjective. Hierarchical clustering sidesteps this problem entirely: you never decide K up front. Instead you build a tree-like structure over the data, and then, based on the question you are trying to answer, you cut that tree at a certain level to get your clusters.

The same tree can serve many questions, because each cut produces a different clustering. Think of a family tree: one diagram records every branching, and whether you ask "who descends from my grandparents?" or "who descends from my great-grandparents?" is just a matter of how high you slice the tree. The tree itself does not change; the cut does. That is the entire payoff of the hierarchical idea: one structure, many clusterings, chosen by where you cut.

15.1.2 Agglomerative and Divisive Strategies

There are two strategies for building the hierarchy, and they are exact mirror images of each other.

In the agglomerative strategy, also called the bottom-up approach, every data point starts out behaving like its own cluster. Then you merge points based on similarity, and keep merging similar clusters until you end up with one big cluster holding everything. Merging is the only operation: nothing ever gets split. Each merge decision is made once, and a cluster, once formed, stays formed.

In the divisive strategy, also called the top-down approach, all the points start inside one big cluster, and you break that cluster into smaller parts based on similarity or dissimilarity, iteratively, until each point is its own cluster. Splitting is the only operation: nothing ever gets merged back.

Both strategies produce nested clusters arranged in a hierarchical tree, which is called a dendrogram — the subject of the next section. The nesting property is what matters: any cluster produced at any level of the tree is a union of clusters from lower levels, so the levels are not independent groupings but a single coherent hierarchy.

15.1.3 Algorithms That Follow the Two Strategies

One well-known algorithm that implements the agglomerative strategy is AGNES (AGglomerative NESting). In AGNES, each point is first treated as a cluster, and merging starts from there: at every step the two closest clusters are combined, and the process is recorded as a tree. AGNES is the reference implementation of the bottom-up idea.

On the divisive side, one algorithm with a primitive divisive hierarchical strategy is DIANA (DIvisive ANAlysis). DIANA begins with all objects in one cluster and repeatedly splits: at each step it finds the object or group that is most dissimilar to the rest and pulls it out into its own cluster, continuing until every object is alone. (The professor's spoken explanation of the name was hard to hear; the standard name in the literature is DIANA.) A second example of a top-down (divisive) algorithm is bisecting k-means, which gets its own treatment below — it takes the "split" idea literally by handing each chosen cluster to k-means with K equals two.

The pair AGNES and DIANA is a classic pairing in the literature precisely because they are symmetric: AGNES shows how merging builds a hierarchy, DIANA shows how splitting tears one down.

15.1.4 Why Hierarchical Clustering Matters in Practice

Real-world: hierarchical clustering is very meaningful because it resembles many taxonomies we follow in real life, for example in biological science. Living things are grouped into nested categories — species inside genera, genera inside families, families inside orders — and that nested structure is exactly the shape a dendrogram produces. Taxonomy is not an arbitrary constraint of the algorithm; it is the natural form of the domain. When your real-world clusters are naturally hierarchical, the tree-based model fits them better than flat K clusters, because a flat model is forced to pretend every group exists at the same level of granularity.

The same nested shape shows up everywhere: file systems are directories inside directories, an organization chart nests teams inside divisions, a phylogenetic tree nests evolutionary branches. Whenever the domain itself is a hierarchy, hierarchical clustering is the honest model.

Recap: hierarchical clustering replaces "guess K" with "build a nested tree, cut where your question needs." Bridge: next we look at the tree itself — the dendrogram — and learn how to read the entire merge history out of its junction heights.

15.2 The Dendrogram

15.2.1 What the Tree Shows

A dendrogram is the tree you get from hierarchical clustering. On the X axis you see all the points, laid out as leaves. On the Y axis you have distance. Each merge in the clustering shows up as a junction, and the height of that junction records the distance at which the two clusters were merged. So the dendrogram is not just a pretty picture: it encodes the entire merge history of the data, and it gives a lot of information.

The two axes play different roles. The X axis only decides the order in which the leaves are drawn — it is a naming axis, not a number axis, so moving a leaf sideways changes nothing about the clustering. The Y axis is the meaningful one: it is measured in distance units (the same units as the pairwise distances), and every vertical line's height is a real number — the distance between the two clusters at the moment they merged.

Visual intuition: imagine a thermometer lying horizontally at the bottom of the page, with the points resting on it. Each junction is a lowercase "V" or "U" reaching upward, and the taller the arch, the farther apart its two subtrees were when they joined. The bottom of the tree is the fine detail (small distances, small clusters); the top is the coarse structure (large distances, one big cluster). Reading the figure bottom-up tells the merge story in time order.

15.2.2 Reading an Example Dendrogram

In the example shown, the leaves are points one, three, two, five, six, and four. Reading the tree bottom-up: point one and point three were merged first, and the junction is low, because the distance between them is small. Then point two and point five were merged. Next, the cluster of two and five was merged with point four. Then the cluster of one and three was merged with that bigger cluster, and finally everything joined into one root.

The height of each junction reflects the distance at the merge: a taller junction means the clusters being joined were farther apart. This is the single most useful rule for reading a dendrogram:

Merge height = distance at which the merge happened. Tall junction → far-apart clusters; low junction → close clusters.

15.2.3 Cutting the Tree at Any Level

Because every merge is stored in the tree, you can cut the dendrogram at any level to get the desired results. A cut near the bottom gives many small clusters; a cut near the top gives a few big ones. This is the payoff of not fixing K: one tree, any number of clusterings, chosen by where you place the cut.

Mechanically, a cut is a horizontal line at a chosen height. Every junction below the line is "accepted," and the leaves that hang together beneath each accepted junction form one cluster; any junction above the line is ignored. In the worked example that follows, this is exactly how the final clusters were read off — a horizontal cut at a chosen height groups everything below each junction into one cluster. Note the cut's height itself has meaning: it is the largest merge distance you are willing to tolerate inside a cluster, so cutting at 0.2 means "no cluster may contain points that were merged at a distance above 0.2."

15.3 Bisecting K-Means (Divisive)

15.3.1 The Algorithm

Purpose: bisecting k-means turns top-down splitting into a repeated call to k-means, so it reuses a cheap, well-understood clustering algorithm as its engine. Instead of inventing a clever split rule, it lets k-means find the two natural halves of whatever cluster it is handed.

Inputs and outputs: the input is the full set of points, plus the number of clusters you eventually want (the stopping condition). The output is a binary tree of splits — each internal node is one k-means run, and the leaves are the final clusters.

Steps:

1. Put all the points into one big cluster.
2. Take the big cluster and pass it to k-means with K equals two, which splits it into two clusters.
3. Choose one of the remaining clusters (the lecture's example works on whichever clusters remain) and pass it to k-means with K equals two.
4. Repeat on whichever clusters remain until you have enough clusters (or until some stopping criterion is met).

The name says it all: you keep bisecting. Each split is one pass of k-means, and the tree of splits records how every cluster was carved out of the original one.

The method is not locked to k-means. Any clustering algorithm can play the role of the splitter — AGNES, or any other strategy you want. The generic idea is: take a big cluster, hand it to a clustering algorithm, and it breaks it into two parts. The K value of two in the example is a choice, not a requirement; you can pass K equals two or any other value you like, based on your requirement. Using K equals two is simply the smallest useful split and the most common default.

15.3.2 Walkthrough on the Example Data

15.3.3 Complexity: Log n Runs of K-Means

The complexity of k-means itself, discussed earlier, is:

$$\text{complexity of k-means}=O(i\cdot k\cdot n\cdot d)$$

where $i$ is the number of iterations, $k$ is the number of clusters, $n$ is the number of points, and $d$ is the dimension of each point. The symbol $i$ is the iteration count — how many times k-means cycles through its two steps before the assignments stop changing. All four factors enter linearly: more iterations, more clusters, more points, or more dimensions each cost proportionally more work.

To get the complexity of bisecting k-means, ask how many times this inner algorithm runs. The number of runs equals the height of the tree you are building. If we assume the tree is balanced and binary, the height of the tree is $\log n$ — a balanced binary tree over $n$ leaves has exactly ${\log }_{2}n$ levels, since each level doubles the number of nodes — so k-means runs about $\log n$ times:

$$\text{complexity of bisecting k-means}\approx O(\log n\cdot i\cdot k\cdot n\cdot d)$$

The reasoning: $\log n$ runs, each costing $O(i\cdot k\cdot n\cdot d)$, multiply together. (Strictly, later runs operate on smaller subsets, so the real total is smaller than the product — but the professor's product form is the standard complexity statement, and it correctly captures the headline: an extra $\log n$ factor.) The tree does not have to be binary — you could have a ternary tree or an n-ary tree based on your requirement — and it might be skewed in one direction; both choices change the number of runs. A balanced tree gives the best case of $\log n$ runs; a badly skewed tree can make the number of runs approach $n$ instead. Either way, the result is costlier than running plain k-means once.

15.3.4 Limitation: The Greedy, Local-Factor Problem

Bisecting k-means follows a greedy strategy: once you have broken a bigger cluster into smaller clusters, you cannot merge two of those smaller clusters back together, even if they turn out to be very similar. The example in the lecture showed why this hurts.

15.4 The Agglomerative Algorithm and the Proximity Matrix

15.4.1 The Overall Procedure

The agglomerative algorithm is one of the most popular hierarchical clustering techniques, and the procedure is simple.

Purpose: turn the data into a nested hierarchy without choosing K, using only pairwise distances.

Inputs and outputs: input is the set of points; output is the complete merge sequence — equivalently, the dendrogram.

Steps:

1. Build a proximity matrix: compute the distance from each cluster to every other cluster, for all the clusters. Initially the clusters are the individual points.
2. Merge the two closest clusters, or the two most similar clusters, whatever your notion of similarity turns out to be.
3. Update the proximity matrix, because two clusters are now one and the distances involving them have changed.
4. Repeat these steps iteratively until only one big cluster remains.

That single cluster is the root of the dendrogram, and every intermediate merge is a junction in it. The whole algorithm is one loop with three moves: build, merge, update — then build again is unnecessary, since updates keep the table current.

The proximity matrix deserves its name: proximity means closeness, so the table stores "how close is every pair of clusters." Its cells are filled with the distance between the corresponding clusters, and the exact meaning of that distance is the only thing that varies between linkage methods. For two clusters $C_i$ and $C_j$ with sizes $m_i$ and $m_j$:

$$M[i][j]=d(p_i,p_j)$$

where $p_i$ is a point in cluster $i$, $p_j$ a point in cluster $j$, and $d(p_i,p_j)$ is the distance between them. Initially, clusters are single points, so the cell for $p_1$ and $p_2$ stores $d(p_1,p_2)$, the ordinary point-to-point distance.

Properties of the matrix (initial state): the matrix is symmetric — $M[i][j]=M[j][i]$, because distance is symmetric — and the diagonal cells are the distance from a point to itself, which is zero. This halves the storage you actually need: only the $\frac{n(n-1)}{2}$ cells above the diagonal hold information.

15.4.2 Worked Example: Nine Points

The example only names three merges, but the pattern is what matters: at every round you scan the table, take the smallest remaining entry, merge its two clusters, and add a junction whose height is exactly that entry's value. A fully numeric illustration of the same procedure (using the reference dataset's coordinates, so you can see real numbers): six points with Euclidean distances such that the smallest entries are $d(3,6)=0.11$ and $d(2,5)=0.14$. The first merge is {3, 6} at height 0.11, the second is {2, 5} at height 0.14, and every later junction sits above them because the remaining entries are all larger. The dendrogram's shape is fully determined by the sorted order of the matrix entries.

15.4.3 Cutting the Example

Once the tree is built, you cut it at any level to decide the final clusters. In the example, a cut at a certain height gives: one cluster holding one and two, another cluster holding three and four (or however the merges fell), five and six together, and so on — each region below the cut line becomes one cluster.

This cut is the direct answer to the question you started with. If the business question asks for three groups, place the cut so that exactly three junctions fall below it; if it asks for seven groups, place the cut lower. The dendrogram's hierarchy is fixed, but the number of clusters is now a free choice made at the end — the whole point of avoiding K up front.

15.4.4 Updating the Proximity Matrix After a Merge

When two clusters merge, only a few cells of the proximity matrix need updating. Suppose C2 and C5 merge first in a diagrammed example. After the merge you have one cluster C2–C5 instead of two, so the cells involving C2 and C5 are updated to reflect the new cluster, while the rest of the matrix stays as it is: the distance between C3 and C4 does not change just because C2 and C5 merged.

The lecture stressed this point with the diagram: most cells are untouched, only the merged cluster's connections change. Concretely: in a matrix over $m$ current clusters, a merge removes two rows and two columns and adds one row and one column for the new cluster — so only $O(m)$ cells are recomputed, out of $O(m^2)$ total. The expensive part of each round is not the update but the search for the minimum entry, which is why the cost analysis in a later section focuses on the scanning.

15.5 Min Linkage

15.5.1 Definition

We keep saying "merge the two most similar clusters," so we need a precise definition of cluster similarity. The first strategy is min. Min says: the similarity between two clusters is defined by the two most similar points, one in each cluster. Concretely, the distance between clusters C1 and C2 is the minimum distance over all pairs of points with one point from C1 and one from C2:

$$d(C_1,C_2)=\underset{p\in C_1,q\in C_2}{\min }d(p,q)$$

where $p$ is any point in cluster $C_1$, $q$ is any point in cluster $C_2$, and $d(p,q)$ is the ordinary distance between those two points. Find the pair of points, one in each cluster, whose distance is smallest; that distance becomes the inter-cluster distance, and that is what min means.

Two ways to picture it. Algebraically: scan every pair $(p,q)$, collect all $d(p,q)$ values, and keep the smallest one. Graphically: treat the points as nodes and each distance as an edge between them; then the min distance between two clusters is the shortest edge with one endpoint in each cluster. This graph view explains the alternative name used in the literature: min linkage is also called single link, because a single close pair is enough to link two clusters together.

Note the subtlety in direction: if your similarity is a distance (smaller = closer), you take the minimum; if you worked with similarities where bigger = closer, you would take the maximum. The names "min" and "max" come from the distance convention, and the lecture's exam questions follow that convention.

15.5.2 Worked Example

15.6 Max Linkage

15.6.1 Definition

The second strategy is max. Max says: the similarity between two clusters is defined by the two least similar points, one in each cluster. Instead of the closest pair, take the most dissimilar pair. The distance between clusters C1 and C2 is the maximum distance over all pairs of points with one point from C1 and one from C2:

$$d(C_1,C_2)=\underset{p\in C_1,q\in C_2}{\max }d(p,q)$$

where again $p$ runs over every point in $C_1$ and $q$ over every point in $C_2$. In the graph view, max linkage takes the longest edge with one endpoint in each cluster — the opposite of min's shortest edge. That is why the literature calls max linkage complete link: two clusters are only "completely linked" when every point in one is close enough to the other — the worst pair, the farthest two points, must also be acceptable. Under complete link, a group of points only becomes a cluster when all its points are pairwise linked — the points must form a clique.

15.6.2 Merging Still Picks the Most Similar Clusters

One point to note here: max only defines the similarity measure. When you merge, you still always merge the two most similar clusters — that is, at every step you pick the cluster pair whose max-distance is smallest. The formula defines how distance between clusters is measured; the merging rule stays the same.

This is a common point of confusion, so the lecture flagged it explicitly:

15.6.3 How the Merge Order Differs from Min

Because the inter-cluster distance is measured differently, the merge order changes. In the example, under min the pairs three and six, then five and two merged early. Under max, the distances between the same points are recomputed as farthest pairs, and the picture shifts: in the lecture's figure, the distance between four and six turns out to be the maximum among the pairs under consideration, which keeps those clusters apart and pushes the merges elsewhere.

Step by step the strategy produces a different hierarchy, and the lecture emphasized that you can see how each strategy grows its own cluster shapes, with different clusters at the end.

Comparison — min vs max:

When to pick which: prefer min when you expect elongated or non-elliptical natural clusters and your data is clean; prefer max when you expect tight, ball-shaped clusters or when your data is noisy. Neither is "correct" — the choice is about the shape you believe the truth has.

15.7 Group Average Linkage

15.7.1 Definition

The third strategy is group average. As the name suggests, you find all pairwise distances between the two clusters and take the average. The distance between C1 and C2 is the average of every distance between a point in C1 and a point in C2:

$$d(C_1,C_2)=\frac{1}{|C_1|\cdot |C_2|}\sum _{p\in C_1}\sum _{q\in C_2}d(p,q)$$

where $|C_1|$ is the number of points in cluster $C_1$ (its cardinality), $|C_2|$ the number of points in $C_2$, and the double sum adds up $d(p,q)$ for every ordered combination of one point $p$ from $C_1$ and one point $q$ from $C_2$. The denominator $|C_1|\cdot |C_2|$ is exactly the number of such pairs, so the formula reads: sum every cross-cluster distance, divide by the number of pairs, and that average is the inter-cluster distance used to decide the next merge.

(The professor's spoken explanation said "find all pair distance and divide by number of points in the cluster"; the standard form divides by the number of point pairs, $|C_1|\times |C_2|$ — with clusters of size 2 and 3, that is 6 pairs, not 5 points. The formula above is the standard one and is what the exam will use.)

So we sum all $d(p,q)$ over every pair, then divide by the number of pairs, and that average is the inter-cluster distance. Because every pair contributes one term to the sum, every point gets one vote — big clusters do not get extra weight per point, and small clusters are not drowned out.

15.7.2 A Middle Ground

Group average sits between the extremes of min and max: instead of letting one closest pair or one farthest pair speak for the whole clusters, it lets every point pair contribute. It is a reasonable, widely used default when you have no reason to prefer the extremes.

In the literature, the standard group-average method is known by its full name UPGMA — Unweighted Pair Group Method using Arithmetic averages. "Unweighted" means each point is weighted equally when the average is computed (a weighted variant, WPGMA, treats each cluster equally instead, which effectively gives fewer points more influence — used only when you have a reason to weight clusters, such as uneven sampling).

15.8 Centroid Linkage

15.8.1 Definition

A fourth way to define inter-cluster distance is to use the centroids. Compute the centroid of each cluster, then take the distance between the centroids:

$$d(C_1,C_2)=\Vert {\mu }_1-{\mu }_2\Vert$$

where ${\mu }_1$ is the centroid (mean point) of cluster $C_1$ and ${\mu }_2$ is the centroid of cluster $C_2$. The centroid of a cluster is its average point: compute the mean of the x-coordinates and the mean of the y-coordinates across all points in the cluster, and that pair of means is $\mu$. The notation $\Vert \cdot \Vert$ means the Euclidean norm — the ordinary straight-line distance between the two center points.

With a third cluster C3 whose centroid sits somewhere else, you compare the centroid distances between all pairs and merge the two clusters whose centroids are closest. It is very easy to visualize: clusters are represented by their center points, and similarity is just center-to-center distance. Instead of comparing every point pair (min, max, group average), centroid linkage compares one pair of numbers per cluster pair — cheap to compute and easy to draw.

15.8.2 The Convexity Assumption

The professor's answer separates two questions. Arbitrary? No — the centroid is a well-defined, reproducible summary (the mean), not a random choice. Safe? Not necessarily — a centroid is only a faithful summary when the cluster is blob-shaped. If the cluster is convex (roughly circular or elliptical), the centroid sits inside the data and the center-to-center distance is a fair measure of how far apart the clusters are. If the cluster is concave — crescent-shaped, ring-shaped, S-shaped — the centroid can fall where no points exist, and two clusters with similar centers can still be entirely separate in space.

Visual intuition: picture two crescent moons facing each other, their tips almost touching. Both centroids lie in the gap between the moons — almost on top of each other — so centroid linkage thinks the two clusters are close, while visually they are two distinct shapes. A distance that uses the closest points (min) would see the tiny gap at the tips; a centroid distance sees only the two empty-air centers.

15.8.3 Worked Example: Min vs Centroid on Four Points

Now contrast what centroid linkage does to the same decision. After {1, 2} merges, its centroid is ${\mu }_{12}=(0.5,0)$. The centroid distance to point 3 is $\Vert (0.5,0)-(2,0.5)\Vert =\sqrt{1.5^2+0.5^2}\approx 1.58$ — noticeably larger than min's 1.12, because the centroid averages the close point 2 and the far point 1. Working the whole dataset through with the centroid ruler is set as homework — you try it yourself and see how the cluster shapes come out differently. The mechanism to watch: whenever the centroid is not the nearest point, the merge order changes; and because the centroid moves after every merge, the history keeps rewiring.

15.8.4 Continuous Clustering (Chaining)

This chain-like growth is not accidental. Min strategy actually supports continuous clustering, also called chaining: each new point attaches to the existing chain through its nearest neighbor, so the cluster stretches out in a line-wise fashion. The lecture revisited this idea with a figure showing distances between two clusters defined by the minimum distance between them, and noted that continuous clustering is exactly the behavior min produces.

Think of it as a railway: the cluster is a line, and every new station connects to the station that is closest to it, wherever that lies on the line — so the line can snake arbitrarily far from where it started. In the four-point walkthrough above, points attach at 1.00, then 1.12, then 1.80 — each attachment through the nearest single point, producing the linear chain 12 → 123 → 1234.

Recap: centroid linkage summarizes each cluster by its mean and measures center-to-center distance — easy to draw, but it assumes convex clusters and can invert the dendrogram. Bridge: Ward's method is the last linkage — and it answers the same "one number per cluster" idea with error instead of a center.

15.9 Ward's Method

15.9.1 SSE as a Cluster Quality Measure

The last method is Ward's method, and its logic is simple. Consider two clusters C1 and C2; each cluster, on its own, has some SSE value. SSE is the sum of squared errors of the cluster:

$$\text{SSE}(C)=\sum _{p\in C}\Vert p-{\mu }_C{\Vert }^2$$

where $p$ is a point in the cluster and ${\mu }_C$ is the centroid of the cluster. The error of one point is its distance from the cluster's centroid, and SSE squares that error and adds it over every point — the same objective function k-means minimizes. (The professor described SSE only in words — "as we start merging clusters the SSE value goes on increasing" — and the sum-of-squared-distances form above is the standard definition used in the reference; it is what you should write on the exam.)

Why squared? Squaring does two things: it makes every error count positively (no cancelling of + and − deviations), and it punishes large errors more than linearly — one point that is very far from the centroid contributes a disproportionately large penalty. That is exactly the behavior we want from a quality measure: a cluster with one stray faraway point is much worse than a cluster where the same total error is spread evenly.

If every point is its own cluster, each cluster has SSE zero, because each point sits exactly at its own centroid. As clusters merge, the SSE value keeps increasing, because points are now measured against a centroid that is not their own. So the lower the SSE, the purer the clusters: SSE is a quality gauge that starts at perfect zero and degrades with every merge.

15.9.2 The Minimum-Increment Rule

Ward's method turns this into a merging rule. When you merge two clusters, the SSE of the combined cluster is bigger than the sum of the two separate SSEs, and the difference is the increment:

$$\Delta \text{SSE}(C_1,C_2)=\text{SSE}(C_1\cup C_2)-\text{SSE}(C_1)-\text{SSE}(C_2)$$

Ward's method says: merge the two clusters where the increment in SSE is minimum. You always merge the pair whose union costs the least extra error. Note the two terms on the right are what we already have (the separate SSEs, known before the merge); the only computation is the SSE of the would-be union. So the increment measures the price of a merge in error units, and Ward always pays the cheapest price available.

There is a closed-form shortcut for the increment that avoids recomputing the union's SSE — it depends only on the sizes and centroids of the two clusters:

$$\Delta \text{SSE}(C_1,C_2)=\frac{|C_1|\cdot |C_2|}{|C_1|+|C_2|}\Vert {\mu }_1-{\mu }_2{\Vert }^2$$

Why the formula takes this shape (derivation): the increment is driven entirely by the separation between the two centroids, scaled by how balanced the two clusters are. The full algebra:

$$\begin{array}{rlr}\text{SSE}(C_1\cup C_2)& =\sum _{p\in C_1\cup C_2}\Vert p{\Vert }^2-|C_1\cup C_2|\Vert \mu {\Vert }^2& \text{(expanding the square and collecting terms)}\\ & =\left(\sum _{p\in C_1}\Vert p{\Vert }^2-|C_1|\Vert {\mu }_1{\Vert }^2\right)+\left(\sum _{p\in C_2}\Vert p{\Vert }^2-|C_2|\Vert {\mu }_2{\Vert }^2\right)-\left(|C_1|\Vert {\mu }_1{\Vert }^2+|C_2|\Vert {\mu }_2{\Vert }^2-(|C_1|+|C_2|)\Vert \mu {\Vert }^2\right)& \text{(rearranging the totals)}\\ & =\text{SSE}(C_1)+\text{SSE}(C_2)+\frac{|C_1||C_2|}{|C_1|+|C_2|}\Vert {\mu }_1-{\mu }_2{\Vert }^2& \text{(weighted-mean identity: the pooled centroid}\mu \text{lies on the segment}{\mu }_1{\mu }_2\text{)}\end{array}$$

Subtracting $\text{SSE}(C_1)+\text{SSE}(C_2)$ from both sides gives the closed form. A sanity check: when both clusters are singletons, $|C_1|=|C_2|=1$, the scale factor is $1/2$, and the increment is $\frac{1}{2}\Vert p_1-p_2{\Vert }^2$ — merging two single points costs half the squared distance between them. The larger either cluster is, the more expensive it is to drag it across a fixed centroid gap, because more points share the new, compromised centroid.

15.9.3 The Temporary-Merge Procedure

To apply the rule, you try merges before committing. With clusters C1, C2, C3, C4 in front of you, temporarily merge C1 and C2 and note down the increment in SSE. Then temporarily merge C1 and C3 and note that increment. Then C2 and C3, and so on, covering the candidate pairs. Whichever pair shows the smallest increment is the one you actually merge, and then you repeat the whole procedure for the next step. So Ward's method defines similarity between two clusters as the increase in squared error when the two clusters are merged, and the algorithm keeps choosing the pair that minimizes that increase.

15.10 Complexity of Agglomerative Clustering

15.10.1 The Cost of the Matrix and Its Updates

What is the complexity of the agglomerative strategy? It comes out to roughly $O(n^3)$ for $n$ points. (The professor's spoken number was garbled — "roughly nq" — and the standard analysis gives $O(n^3)$ for the naive implementation, with an $O(n^2\log n)$ variant; both are stated below and both are fair game for the exam.)

The reasoning in three pieces:

Piece 1 — building the matrix costs $O(n^2)$. The proximity matrix holds the distance between every pair of points. There are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$ pairs, and since the matrix is symmetric you can store just one triangle — either way, the number of distances is proportional to $n^2$. Computing each entry takes constant work (one Euclidean distance in fixed dimension), so filling the matrix is $O(n^2)$.

Piece 2 — each of the $n-1$ merges costs $O(n^2)$ in the worst case. The loop runs $n-1$ times, because each merge reduces the cluster count by one, from $n$ down to 1. Two tasks repeat every round:

• Find the minimum among the inter-cluster distances to pick the next merge. Scanning the current matrix costs $O(m^2)$ when there are $m$ clusters left.
• Update the matrix after the merge. Only the cells touching the new cluster change — $O(m)$ cells out of the $O(m^2)$ total (section 15.4.4).

With $m$ shrinking from $n$ down to 1, the scanning dominates, and summing the round costs gives:

$$\sum _{m=2}^{n}O(m^2)=O(n^3)$$

Piece 3 — smarter bookkeeping gives the $O(n^2\log n)$ variant. If the distances from each cluster to every other cluster are kept in a sorted structure (a heap or sorted list), finding the closest pair drops from $O(m^2)$ to $O(\log m)$ per round, and the total becomes $O(n^2\log n)$. The storage cost is the same in both cases: the matrix itself occupies $O(n^2)$ space.

The bottom line: naive agglomerative clustering is $O(n^3)$ time and $O(n^2)$ space; the heap-based variant reaches $O(n^2\log n)$ time. Either way, the $n^2$ in the space and the extra $n$ in the time are why hierarchical clustering is described as expensive — it is practical for thousands of points, not millions.

15.10.2 Where the Algorithms Land

Putting the complexity numbers together: k-means costs $O(i\cdot k\cdot n\cdot d)$, which is a good complexity — linear in the number of points, the only problem there is that it is a center-based strategy, so you can only get convex clusters. Hierarchical clustering, whether agglomerative or bisecting k-means, is costlier — agglomerative pays $O(n^3)$ or $O(n^2\log n)$, bisecting k-means pays an extra $\log n$ factor over k-means.

If you are looking for non-convex structure, density can be another notion of what a cluster is — which is exactly where the next algorithm comes in. The complexity ledger so far:

15.10.3 Choosing a Linkage Method in Practice

Recap: agglomerative clustering buys its K-free flexibility with $O(n^3)$-style costs. Bridge: since all distance-based methods fail on non-convex shapes, the next unit switches the notion of similarity entirely — from distance to density.

15.11 A Divisive Strategy: Minimum Spanning Tree

15.11.1 Building the MST

Another example of a divisive hierarchical strategy is based on the minimum spanning tree, or MST. The strategy is easy to visualize.

What a spanning tree is: take the points as nodes and draw edges between them, with each edge labeled by its length. A spanning tree is a set of edges that (1) connects every point to every other point (no point is left isolated), (2) uses exactly $n-1$ edges for $n$ points, and (3) contains no cycles — there is exactly one path between any two points. A minimum spanning tree is the spanning tree with the smallest possible total edge length.

Purpose: the MST is a skeleton of the data — the cheapest network that keeps the points connected — and its edges are ranked by length, which gives the divisive algorithm a natural cutting order.

Building it: initially all the points are treated as one big cluster. First you build a minimum spanning tree over the points — the tree that connects all the points with minimum total edge length. Standard algorithms (Kruskal's or Prim's) grow this tree in $O(n\log n)$ time with a heap, or $O(n^2)$ on dense inputs. Once the MST exists, every point is connected to every other point through the tree, so all the points belong to one cluster.

Why the MST, and not the full distance graph? The full graph has $\frac{n(n-1)}{2}$ edges; the MST keeps only the $n-1$ most important ones. It is the same compression that min linkage performs implicitly: the shortest-edge connections alone are enough to encode the cluster structure, which is why the MST hierarchy ends up equivalent to single-link clustering.

15.11.2 Breaking the Largest Edge

Now you break the big cluster into smaller parts. Which edge do you cut? You break the edge with the maximum distance, because that edge contributes most to the dissimilarity of the cluster.

The intuition for "break the largest edge": the tree's edges are the chains of evidence that hold the cluster together. A short edge means "these two points are close — one group"; a long edge means "these two points are barely connected — this is the weakest link." Cutting the weakest link first produces the most defensible split. Note that "largest edge length" is the same thing as "smallest similarity," since distance and similarity are inverse — the professor used both phrasings.

15.11.3 Algorithm Summary

To restate the algorithm:

1. Create a minimum spanning tree over all the points.
2. Repeat: create a new cluster by breaking the link that corresponds to the largest distance (the smallest similarity).
3. Stop when every point is a singleton cluster.

Each break of the largest edge turns one cluster into two, and the sequence of breaks forms the divisive hierarchy.

Complexity and cost: building the MST costs $O(n\log n)$ (heap-based Kruskal or Prim), and breaking the remaining edges is cheap once they are sorted by length — so the whole divisive hierarchy is dramatically cheaper than the $O(n^3)$ agglomerative scan. The tree itself needs $O(n)$ storage.

Equivalence worth knowing: the MST strategy produces exactly the same cluster hierarchy as single-link (min) agglomerative clustering — both are driven by the shortest edges in the graph. The two algorithms look opposite (splitting vs merging) but encode the same structure, which is a good exam-style connection.

15.12 DBSCAN: Why Density?

15.12.1 When Distance Does Not Help

All the strategies so far are distance-based clustering mechanisms: min, max, group average, Ward's method — distance is the main criterion everywhere. But a lot of the time distance does not help you find the natural clusters in the data.

Consider an example: the points on the screen form two natural groups, and if you look closely you can see both of them. Now suppose you use a center-based strategy, say k-means with K equals two. One centroid lands in one region, the other centroid lands in another, and the clusters k-means returns cut right across the natural groups.

Why does this happen? K-means is a center-based model of a cluster: a cluster is "everything near one center," so its boundaries are convex (straight cuts, then circular or elliptical regions). A crescent is not convex — the natural group wraps around empty space — so no single center and no straight boundary can represent it. Distance alone cannot separate these two natural groups, so sometimes you have to come up with a different measure to form natural groups in the data — and one such measure is density.

Visual intuition: think of a night-sky map. Astronomers find star clusters not by measuring how far each star is from every other, but by noticing where stars are packed thickly versus spread thinly. The Milky Way is one giant chain of dense patches connected by fainter ones. "Thickly packed" is a local, spatial statement — it needs no global center and no fixed number of groups — and that is exactly the viewpoint DBSCAN adopts.

15.12.2 Density Needs Two Ingredients

If you want to define density, you need two things. First, you have to define an area: in how much area, in some unit, are we counting points — is it a square, a circle? Second, you have to say how many points should be inside: the minimum number of points that makes a region dense. If there are more points than that minimum, you call the region dense; if fewer, it is less dense. So density always comes with two components: the definition of the area, and the minimum number of points, which we call minPts.

An everyday analogy: "how crowded is a restaurant neighborhood?" Two numbers answer it — how far you are willing to walk (the area) and how many restaurants make a block "busy" (the minimum count). Change the walk distance and the same block flips from busy to empty; change the minimum and the same crowd flips from crowded to not. Density is not an intrinsic property of the data; it is a property of data measured with your chosen area and threshold — which is why both numbers become tunable parameters of the algorithm.

15.12.3 The Full Name

The algorithm built on this notion is DBSCAN, which stands for Density-Based Spatial Clustering of Applications with Noise. It is a density-based clustering algorithm: you define density using minPts and eps, you pass both as tunables when you run it, and it finds clusters by connecting dense regions.

Decompose the name and you get the whole plan:

• Density-Based: similarity is measured by point density, not by distance to a center.
• Spatial: the area component is a circle of radius eps around each point — a spatial neighborhood.
• Applications with Noise: the algorithm has an explicit, first-class category for noise — points that belong to no dense region — instead of forcing every point into some cluster.

Real-world: natural groups in the real world are often non-convex — crescent shapes, rings, elongated blobs — which is exactly when density-based thinking helps and center-based thinking fails. Store customers clustered in walking neighborhoods, crime hotspots on a city map, galaxies in a sky survey — all are spatial density phenomena.

15.13 DBSCAN: Core, Border, and Noise Points

15.13.1 The Two Parameters: Eps and MinPts

DBSCAN takes two tunable parameters: eps, the radius of the neighborhood circle drawn around a point, and minPts, the minimum number of points that must lie in that area for the region to count as dense. Example values from the lecture: eps equals one centimeter, minPts equals five. To check whether a point lies in a dense region, build the circle of radius eps around it and count the points inside. If the count is greater than or equal to minPts, the area is dense.

Formally, the eps-neighborhood of a point $p$ is the set of points within distance eps of $p$:

$$N_{\text{eps}}(p)=\{q:d(p,q)\le \text{eps}\}$$

The inequality $d(p,q)\le \text{eps}$ is inclusive — it admits every point whose distance to $p$ is at most eps, including $p$ itself, because $d(p,p)=0$ satisfies it. (The professor did not state this explicitly; it is the standard convention: the count in the neighborhood includes the point itself.) This convention is what makes the definition well-behaved — with eps = 1 cm and minPts = 5, the point itself is already counted, so a point needs four other points inside its circle to qualify.

Why two parameters? eps fixes the scale of "nearby" (how far you look), minPts fixes the threshold of "crowded" (how many must be there). Both together define a density standard; change either one and the same dataset is read as dense or sparse differently.

15.13.2 Core Points

Every point in the dataset belongs to one of three categories. A core point is a point that satisfies the minPts criterion in the area of radius eps around it. For point p1: draw the circle of radius eps, count the points inside, and if the count is at least minPts, p1 is a core point. So a core point is a point whose eps-neighborhood is dense, and the dense area it sits in is called a dense region:

$$p\text{ is a core point}⟺|N_{\text{eps}}(p)|\ge \text{minPts}$$

The vertical bars $|\cdot |$ mean "size of the set" — the number of points inside the neighborhood. With eps = 1 cm and minPts = 5, p1 is a core point because its circle contains five points (including itself). A core point is the interior of a cluster: it has enough company around it that it can anchor other points. Core points are the load-bearing points of DBSCAN — clusters are built out of them, and no point can be part of a cluster without a chain of core points behind it.

15.13.3 Border Points

A border point is a point that does not satisfy the minPts criterion itself, but can still be reached with the help of a core point. For point p2 in the example: draw the circle around p2 and count — the count is four, which is less than minPts of five, so p2 is not a core point. But p2 becomes a border point if, in its surrounding area, there is at least one point that is a core point. If any point in p2's eps-neighborhood is a core point, p2 counts as a border point, because it hangs off a dense region even though it does not sit inside a dense region of its own.

So border points are the edges of clusters: they are the points that are close enough to the dense interior to belong, but not dense enough to support anyone else. A border point cannot expand a cluster — it only attaches to one. (Note the definition is a one-way street: the core point must lie within eps of the border point, i.e., the border point must lie within eps of the core point — the two conditions are the same distance check.)

15.13.4 Outlier (Noise) Points

The third category is the outlier point, also called the noise point. An outlier satisfies neither condition: in its given area it does not satisfy the minPts criterion, and it cannot be reached with the help of any core point — there is no core point anywhere in its surrounding area. Consider point c: build the area around it, the count falls below minPts, and scanning its neighborhood, no point there is a core point. Then c is a noise point.

Visual intuition for all three: draw eps-circles on a scatter plot and label each point:

• Circle is crowded (≥ minPts points inside) → core — a filled-in area.
• Circle is sparse, but touching a core point's circle → border — the rim of the dense region.
• Circle is sparse and far from any core point → noise — an island in empty space.

15.14 DBSCAN: Building Clusters from Reachability

15.14.1 Direct Density Reachable

With the three point categories in place, DBSCAN defines how points connect. A point A is direct density reachable if it can be reached by traversing through a core point — in plain words, if there is at least one core point in its vicinity. Border points are exactly the points that are direct density reachable from some core point.

The precise statement: A is directly density reachable from a point B when B is a core point and A lies within eps of B — that is, $d(A,B)\le \text{eps}$. The asymmetry is essential and easy to miss: the reachability must start at a core point. A border point cannot reach anything — it lacks the density to vouch for other points — but it can be reached. In the example figure, every blue border point is directly reachable from some green core point, and no border point acts as a source.

Think of it as a reputation chain: only "established residents" (core points) can vouch for newcomers; newcomers can receive a voucher but cannot issue one.

15.14.2 Indirect Density Reachable

Then there is indirect density reachable. Point A and point B are indirect density reachable if you can travel from B to A by traversing through core points in a sequential fashion: B sits next to a core point, that core point sits next to another core point, and so on, until you reach A. The chain of core points is the bridge that connects two dense areas.

Formally: A and B are (indirectly) density reachable when there is a sequence of points $p_1,p_2,\dots ,p_m$ with $p_1=B$, $p_m=A$, where each step $p_i\to p_{i+1}$ is direct density reachability (each $p_i$ for $i<m$ is a core point and $d(p_i,p_{i+1})\le \text{eps}$). The first step may start from a core point, and the final step may land on a border point — the middle of the chain is all core points.

The everyday picture: a bridge built of stepping stones. Each stone (core point) is close enough to the next that you can cross; the chain connects two banks (dense regions) that are never directly adjacent. This is why a cluster can snake across a large area — no single point needs to see the whole cluster, only its neighbor in the chain.

15.14.3 How a Cluster Grows

The growth rule in one sentence: a cluster is everything reachable from a starting core point through chains of core points — including the border points attached at the ends — and nothing else.

The algorithm's five steps (standard form): (1) label every point core, border, or noise; (2) discard the noise points; (3) put an edge between every pair of core points within eps of each other; (4) take each connected component of core points as a cluster; (5) assign each border point to the cluster of one of its associated core points (a tie-breaking rule is needed when a border point touches two clusters). The lecture's narrative — "identify a core point, grow through core neighbors, stop when nothing more is reachable" — is the same procedure viewed from the inside.

15.14.4 The Core-Bridge Picture

The whole idea, restated: we are connecting two dense areas together. We do it by putting core points in the center and connecting core points in a sequential fashion, so that all the dense areas link up into one cluster. What you have to find, in the end, is the set of indirect density reachable points, and from that set the clusters emerge.

Visual intuition: imagine dense blobs of points separated by thin bridges of sparse points. The blobs are the core regions; the bridges are chains of core points (still dense enough to pass the minPts test, just barely); noise floats between them unattached. Each maximal reachable group is one cluster, and the number of clusters is decided by the data's connectivity — not by any K chosen in advance. That is the density answer to the "how many clusters?" question: as many as there are separate reachable regions.

15.15 DBSCAN: Strengths and Failure Mode

15.15.1 Resistance to Noise and Arbitrary Shapes

DBSCAN has a clear advantage: it is resistant to noise. If you use a center-based cluster, noise moves the center around; DBSCAN has a dedicated category of points — outliers — that is focused on finding the noise, so noise gets labeled instead of shifting the cluster. It can handle noise, and it can handle clusters of various sizes and shapes.

The contrast is structural. In k-means, every point is assigned to a cluster, and every point counts in the centroid update — so a few outliers pull the center and distort the whole boundary. In DBSCAN, outliers never join a cluster: they fail both conditions and are dropped from cluster formation entirely, so they influence nothing. Noise is labeled, not absorbed.

Visual intuition: compare the two cluster models on the same amoeba-shaped group. K-means draws a circle around the middle of it — cutting off the tentacles. DBSCAN follows the dense path wherever it leads — the tentacles are part of the cluster because they are dense, not because they are near a center.

Real-world: real data is almost always noisy, so an algorithm with an explicit outlier category is attractive in practice — outliers are labeled, not absorbed. In fraud detection or sensor cleaning, the noise points themselves are often the valuable output: DBSCAN doubles as an outlier detector.

15.15.2 When DBSCAN Does Not Work: Varying Density

DBSCAN does not work properly when density is not uniform — when the density in one cluster is different from the density in another.

The reason is the algorithm's assumption: it assumes one density scale for the whole dataset, so when clusters live at different densities, a single eps and minPts cannot serve all of them. The mechanism in detail: eps and minPts are global numbers, compared against every point's neighborhood. Set them for the dense clusters and the sparse clusters' neighborhoods fall below minPts — their points get labeled noise or get absorbed into whatever dense region is near. Set them for the sparse clusters and the dense clusters' neighborhoods all interconnect — several dense clusters merge into one big blob, exactly the six-to-three collapse above.

This is the same lesson as every clustering method: the model encodes an assumption about cluster shape. K-means assumes convexity, min assumes chains, DBSCAN assumes one density. The fixed eps circle is a single yardstick; a dataset with mixed density needs a ruler per region (which is what algorithms like OPTICS attempt) — beyond this course's scope but worth knowing why it fails.

15.15.3 Choosing Eps and MinPts

How do you decide on the values of eps and minPts? The lecture assigns this as homework: the last slide of the presentation is based on that question, and you are expected to work out the approach for choosing the radius and the minimum point count. Both values are tunables you pass to the algorithm, and the choice drives everything — as the varying-density example shows, the same dataset under different eps and minPts settings gives very different clusterings.

The standard approach, for reference: the k-dist plot. For a chosen $k$ (the intended minPts), compute the distance from every point to its $k$-th nearest neighbor; sort those $n$ values in increasing order and plot them. Points inside real clusters have small k-dist values (their $k$-th neighbor is close); noise points have large ones. The plot is flat for a long stretch and then rises sharply at the knee — the knee's value is a good eps, and $k$ is minPts. The lecture's example dataset (3000 points) yields a clear knee, and eps = 10, minPts = 4 recovers its clusters. Rule of thumb: if $k$ is too small, a few close noise points get mislabeled as clusters; if $k$ is too large, small genuine clusters (smaller than $k$) get labeled as noise.

15.16 The Clustering Landscape: Complexity Recap

15.16.1 K-Means vs Hierarchical vs Density

The clustering unit closes with this contrast. K-means has good complexity, and its only problem is that it is a center-based strategy, so you only get convex clusters. Hierarchical algorithms avoid choosing K but pay a higher cost. And when you are looking for natural, non-convex, noisy clusters, density — in the form of DBSCAN — is another notion altogether, one that does not rely on distance as the main criterion.

Reading the table as a decision ladder:

1. Data is blob-shaped and K is guessable, or speed matters? → K-means, $O(i\cdot k\cdot n\cdot d)$, with the caveat of convex-only clusters and centroid sensitivity to noise.
2. Need a hierarchy (taxonomy, nested groups) and can pay for it? → Agglomerative methods (linkage choice = shape assumption) or bisecting k-means; the dendrogram repays the $O(n^3)$ / $O(\log n\cdot i\cdot k\cdot n\cdot d)$ cost with K-free flexibility.
3. Clusters are arbitrarily shaped, noisy, or of very different sizes? → DBSCAN, trading two tunable parameters (eps, minPts) for the ability to handle crescents, rings, and outliers — with the uniform-density caveat.

Each family answers the same question — "what is a cluster?" — with a different model: near a center, merged by a linkage rule, or connected through dense regions. No method is universally right; each one's assumption is its strength and its failure mode.

15.16.2 What Comes Next

The next topic of the course is an application of data mining techniques: malware detection. That is what the final session of the semester will discuss — a concrete case of the techniques from this and earlier units being turned on a real problem, and a reminder that every method studied so far (clustering included) exists to serve applied detection and decision tasks.

Recap of the whole unit: two ways to build a hierarchy (agglomerative and divisive), one reading tool (the dendrogram), five linkage rules (min, max, group average, centroid, Ward's), two complexity stories (O(n³)-class for agglomerative, log-factor for bisecting k-means), and one density-based alternative (DBSCAN) — each defined by what it assumes about the shape of a cluster.

Exam Guidance Summary

• Comprehensive syllabus: everything covered until the last class is part of the comprehensive syllabus. The clustering material in this unit — hierarchical clustering, the dendrogram, bisecting k-means, the linkage methods (min, max, group average, centroid, Ward's method), the MST-based divisive strategy, and DBSCAN — is examinable.
• DBSCAN homework: the homework on choosing eps and minPts is set for you to work out: make sure you can reason about how the two tunables affect the clustering, including the varying-density failure case (six natural clusters returning three). Recall the standard k-dist approach for the radius, and what happens when k is too small or too large.
• Centroid homework: the homework on the centroid strategy is to run it yourself on the four-point example: work the same dataset you saw with min and compare how the cluster shapes come out. Watch whether the merge order changes and whether the dendrogram stays monotone (inversions).
• Reading a dendrogram: be ready to read one — points on the X axis, distance on the Y axis, merge heights equal to merge distances, and clusters read off by cutting at any level. A horizontal cut at height h means "no cluster may contain points merged above distance h."
• Complexity comparisons: k-means is $O(i\cdot k\cdot n\cdot d)$ and cheap; hierarchical methods are costlier, roughly $O(n^3)$ for agglomerative clustering with $O(n^2\log n)$ variants (heap-based), and bisecting k-means runs k-means $\log n$ times on a balanced binary tree. The proximity matrix alone costs $O(n^2)$ to build and store.
• DBSCAN point categories: the distinction between core, border, and noise — and the notions of direct and indirect density reachability — are core conceptual points to explain precisely. Remember the neighborhood count includes the point itself.
• Vocabulary traps: max linkage defines inter-cluster distance through the two most dissimilar points, but merging always combines the two most similar clusters; and centroid linkage assumes convex clusters (which is why a centroid can sit in empty space for crescent-shaped data). Ward's method is the hierarchical analog of k-means' SSE objective.
• MST connection: the MST divisive strategy produces the same hierarchy as single-link (min) agglomerative clustering — a useful equivalence to be able to state.

Key Industry Applications

• Taxonomies and hierarchies: hierarchical clustering mirrors real-life taxonomies, such as the nested classifications used in biological science — species inside genera, genera inside families — so tree-based clustering is the natural model wherever the domain itself is hierarchical: biological taxonomy, file-system organization, phylogenetic trees, and organizational charts.
• Non-convex natural groups: when clusters in the data are non-convex (crescents, rings, elongated shapes), center-based methods like k-means fail to find the natural groups; density-based clustering like DBSCAN is the practical alternative — customer neighborhoods on city maps, galaxy surveys, and any spatially organized data with arbitrarily shaped regions.
• Noisy real data: real datasets contain noise, and DBSCAN's explicit outlier category labels noise instead of letting it shift cluster centers, which matters whenever data quality is imperfect. In anomaly-oriented fields (fraud detection, sensor fault detection), the labeled noise points are often the most valuable output — DBSCAN doubles as an outlier detector.
• Linkage choice is a judgment call: the choice of linkage method in practice is a judgment call — min, max, group average, centroid, or Ward's method — made according to the requirement and the problem definition, not fixed by any rule: clean elongated data favors min; noisy compact data favors max; balanced defaults use group average; variance-conscious compact clustering uses Ward's.
• Application unit: the course closes the clustering unit by moving to an applied topic, malware detection, as an example of a data mining application built on the techniques from this and earlier units — a reminder that clustering, classification, and evaluation methods exist to serve concrete detection and decision problems.