⌂ Lectures
← →/space · tap / swipe to advance · F fullscreen
CSE2525 · Data Mining · 2026–27

Distances & Similarity

Choosing a distance is choosing which patterns an algorithm can see — worked through two case studies.
A. Anand · study deck
In this lecture

Distances & similarity — the roadmap

Almost every mining task — classify, cluster, flag outliers, search — reduces to one question: what is close to what? This lecture is about the decision hiding behind it: the distance.
Part I

Why distance underlies data mining

Before any formula: what does a distance actually let us do?
The one idea to hold onto

Choosing a distance is choosing what’s similar

Every task today — classify, cluster, flag outliers, search — reduces to one question: what is close to what? Change the distance and the answer changes, though no data point moved.
ranked by price ★ query dress running ranked by purpose ★ query running dress
The query ★ is a running shoe; the candidates are a dress shoe and another running shoe. Its nearest neighbour flips: dress by price, running by purpose.
“Similar” has no default meaning — it depends what you measure:
  • Similar in price? — a running shoe lands next to a dress shoe.
  • Similar in purpose? — it lands next to other running shoes.
  • Similar in description text? — grouped by words, not by use.
  • Similar in who buys it? — you get complements, not substitutes.
Same two candidates, same query — the nearest neighbour flips with the distance. The task decides which sense you want; the distance is how you encode it.
Distance is a shared building block

One dataset — four questions

new object? far out
Mining taskThe question, expressed through distance
ClassificationWhich labelled examples are closest to this new object?
ClusteringWhich objects are close enough to form groups?
Anomaly detectionWhich objects are far from the usual observations?
Similarity searchWhich existing objects are closest to this query?
Your turn · 2 min with your neighbour

Design decision: the “more like this” button

Scenario

A music app wants a “more like this” button on every song. You decide what powers it.

There’s no correct answer — only a design decision you can defend. We’ll compare a few.
Part II

Task → representation → distance

The choice of distance is the model — so make the choice deliberately.
From intuition to vocabulary

Features, and what we mean by a “model”

Feature

  • A measurable property of an object — its price, its category, the words in its description, who buys it.

Representation

  • The features you choose to describe an object — its encoding. We formalise this as a representation space next.

Model (here)

  • Representation + distance + decision rule. Choosing the features and the distance is choosing the model.
Different features give different neighbours — so the modelling decision begins by choosing features, which we assemble into a representation space next.
Before the distance comes the encoding

What is a representation space?

Definition A representation encodes each object as an element of a chosen space ℛ — a vector, a set, a sequence, a node in a graph. Every later step sees only what ℛ records, so two objects identical in ℛ are indistinguishable to the distance. Choosing ℛ is the first modelling decision.

Vector · ℝⁿ

object → a point of numeric features
Euclidean · cosine

Set

object → a set of elements (words, shingles)
Jaccard
1 0 1 1 0

Sequence

object → an ordered string of symbols
edit · Hamming

Graph / tree

object → a node in a graph
shortest path
Your turn · match the data to the space

What is a representation space?

Question You’ve met four spaces — vector, set, sequence, graph. For each, name a kind of data that fits it best. Then the twist: could the same object live in more than one?

Vector · ℝⁿ

numeric data — sensor readings, pixels

Set

the words in a document
1 0 1 1 0

Sequence

a time series · text characters

Graph / tree

a social network · the web
The catch: the same text is a set of words, a sequence of characters — or a dense vector (embeddings, next lecture). The representation is a choice, not a given.
Vector space · the straight-line distance

Euclidean distance

x y Δx = 3 Δy = 4 d = 5
The distance is the hypotenuse: √(3² + 4²) = 5.
d(x, y) = √( Σi (xi − yi)² )
Worked example x = (1, 2),   y = (4, 6).
d = √((4 − 1)² + (6 − 2)²) = √(9 + 16) = √25 = 5.
Cosine is its sibling for text — it compares direction, not magnitude. We’ll meet both again: where they’re used, and whether they’re metrics.
Set · the overlap of two sets

Jaccard distance

A B a b c d e
∩ = {c, d} = 2  ·  ∪ = 5  →  J = 0.4, d = 0.6.
J(A, B) = |A ∩ B| / |A ∪ B|     dJ = 1 − J(A, B)
Worked example A = {a, b, c, d},   B = {c, d, e}.
A ∩ B = {c, d} → 2,   A ∪ B = {a, b, c, d, e} → 5.   J = 2/5 = 0.4,   dJ = 0.6.
Natural for documents seen as sets of words or shingles. We’ll meet it again — in near-duplicate detection — and ask whether it’s a metric.
Sequence · how many edits apart

Edit (Levenshtein) distance

x y b o o k b a c k 2 letters change
book → back: two substitutions → 2 edits.
d(x, y) = fewest insertions, deletions & substitutions turning x into y
Worked example book → back:   b·b ✓,   o → a,   o → c,   k·k ✓  →  2 substitutions.
Equal length, substitutions only → this coincides with the Hamming distance. Insertions & deletions let it compare different lengths: book → books = 1.
We’ll meet Hamming again in Part III — where we prove it is a metric — and in the video case study.
Graph · the fewest steps between nodes

Shortest-path (geodesic) distance

A B C 1 1 5
Direct A–C = 5, but A–B–C = 1 + 1 = 2 wins.
d(u, v) = min over paths u → v of  Σ weight(edges)
Worked example Edges: A–B = 1,   B–C = 1,   and a direct A–C = 5.
Paths A → C:   direct = 5,   via B = 1 + 1 = 2.   So d(A, C) = 2 — the shortest path wins.
Unweighted graphs → just count edges. We’ll work this out in full in Part III, and again in graph mining.
Four decisions, in order

Task → representation → distance → decision

ChoiceWhat it determines
TaskWhat “similar” should mean
RepresentationWhat information is available for comparison
DistanceWhich differences matter, and how much
Decision ruleWhat we do with the resulting distances (e.g. top-k)
And you don’t always need a vector first — trees, strings and sets have distances directly.
Your turn · walk the sequence

Design decision: spot duplicate news articles

Scenario

A news aggregator scrapes the same story from dozens of sites, each with small edits. You must group the duplicates — fill in the four decisions.

DecisionYour call for this task
TaskWhat should “similar” mean — near-identical wording?
RepresentationA set of words/k-grams? a vector of the text? or the whole string (a sequence)?
DistanceEach representation brings its own: Jaccard (set) · cosine (vector) · edit distance (string).
Decision ruleGroup two articles when the distance is below which threshold?
Notice the dependency: the representation you pick decides which distances are even available to you.
Part III

Metrics as useful guarantees

What properties make a distance predictable — and fast?
Definition

When is a distance a metric?

Metric space A function d : X × X → ℝ is a metric on a set X if, for every x, y, z ∈ X, it satisfies the four axioms below. The pair (X, d) is then called a metric space.
AxiomFormal statement
Non-negativityd(x, y) ≥ 0
Identity of indiscerniblesd(x, y) = 0  ⟺  x = y
Symmetryd(x, y) = d(y, x)
Triangle inequalityd(x, z) ≤ d(x, y) + d(y, z)
xyz d(x,y) d(y,z) d(x,z)
Triangle inequality: the detour x→y→z is never shorter than going direct.
Why these axioms are worth demanding

The axioms are guarantees an algorithm can exploit

rcq 10 2 ≥ 8 within 3
c is ≥ 8 from q, but we only want neighbours within 3 — so c is skipped, unmeasured.
  • Identity and symmetry make “the nearest object” well-defined and independent of comparison order.
  • The triangle inequality lets known distances bound unknown ones, so candidates can be ruled out without measuring them.
Pruning with the triangle inequality q is at distance 10 from a reference r; a candidate c is at distance 2 from r. The triangle inequality forces a lower bound: d(q, c) ≥ |10 − 2| = 8. Since 8 > 3, c cannot be within 3 of q — discard it without ever computing d(q, c).
This powers metric indexes — ball trees, VP-trees — that avoid the full O(n²) comparisons.
Exercise · check the axioms

Is the Hamming distance a metric?

x y 1 0 1 1 0 1 1 1 0 0 2 positions differ, so the distance = 2
Candidate distance For strings x, y of equal length n, let dH(x, y) be the number of positions at which they differ.
  • Work through each of the four axioms for dH — does it hold?
  • For the ones that hold, give the reason; for any that fails, a counterexample.
Decide for yourself: is dH a metric? We’ll work it through together on the next slide.
Metric axioms to check:  non-negativity d(x,y) ≥ 0  ·  identity d(x,y)=0 ⇔ x=y  ·  symmetry d(x,y)=d(y,x)  ·  triangle d(x,z) ≤ d(x,y)+d(y,z)
Solution

Yes — the Hamming distance is a metric

xi yi zi a a b = ≠
At one position: xᵢ=yᵢ but yᵢ≠zᵢ, so xᵢ≠zᵢ — at least one pair always differs.
Proof — verify each axiom

Non-negativity. dH is a count of positions, hence dH(x, y) ≥ 0.

Identity. dH(x, y) = 0 ⟺ no position differs ⟺ x = y.

Symmetry. “position i differs” is the same statement for (x, y) and (y, x), so dH(x, y) = dH(y, x).

Triangle inequality. Fix a position i. If xi ≠ zi, then xi and zi cannot both equal yi, so xi ≠ yi or yi ≠ zi. Hence at each position [xi≠zi] ≤ [xi≠yi] + [yi≠zi]. Summing over all n positions gives dH(x, z) ≤ dH(x, y) + dH(y, z).  ∎

At each index the distance is at most 1 (0 if equal, 1 if different), and [xi≠zi] ≤ [xi≠yi] + [yi≠zi] holds index by index — so summing over all indices, the total d(x,z) ≤ d(x,y) + d(y,z).
Exercise · find the broken axiom

Is squared Euclidean distance a metric?

Candidate distance On ℝⁿ, define dsq(x, y) = ‖x − y‖² = Σi (xi − yi)² — the squared Euclidean distance (the quantity k-means minimises).
Work on it first — the next slide gives a hint, and the one after that the full solution.
Metric axioms to check:  non-negativity d(x,y) ≥ 0  ·  identity d(x,y)=0 ⇔ x=y  ·  symmetry d(x,y)=d(y,x)  ·  triangle d(x,z) ≤ d(x,y)+d(y,z)
Hint

Try three points on a line

012 xyz
Compare the direct jump x→z against the two-step path x→y→z.
Hint

Put three points x = 0, y = 1, z = 2 on the real line.

Work out the direct squared distance dsq(x, z) and the two-step sum dsq(x, y) + dsq(y, z) — then compare them.

Which of the four axioms does that comparison test?
Metric axioms to check:  non-negativity d(x,y) ≥ 0  ·  identity d(x,y)=0 ⇔ x=y  ·  symmetry d(x,y)=d(y,x)  ·  triangle d(x,z) ≤ d(x,y)+d(y,z)
Solution

No — the triangle inequality fails

4 2 > direct 1 + 1 d(x,z)² sum
Direct (4) > detour sum (2) — so d(x,z) ≤ d(x,y)+d(y,z) is broken.
Counterexample on the real line Take x = 0,   y = 1,   z = 2. Then
dsq(x, z) = (2 − 0)² = 4,   while   dsq(x, y) + dsq(y, z) = 1² + 1² = 2.
So 4 > 2 — the triangle inequality is violated.
Takeaway

Non-negativity, identity and symmetry all hold, yet dsq is not a metric. Squaring breaks the triangle inequality — which is why the Euclidean distance (its square root) is used wherever metric structure is required.

A metric on objects that are not vectors

Worked example: shortest-path distance on a graph

A B C D E
Definition In a connected graph, d(u, v) is the number of edges on a shortest path between u and v (the geodesic distance; for weighted graphs, the smallest total edge weight).
  • BFS from A reads the distance straight off the layer number:
  • layer 0 = {A},  1 = {B, E},  2 = {C},  3 = {D}.
  • So d(A,D) = 3, along A–B–C–D or A–E–C–D.
  • Triangle check: d(A,D) = 3 ≤ d(A,C) + d(C,D) = 2 + 1. ✓
It is a metric: any path through a third node w is itself a valid u→v path, so the shortest cannot be longer — the triangle inequality holds by construction.
Keep these separate

Valid metric ≠ useful distance

useful,not a metric metric &useful ✓ neither metric, butwrong features valid metric → captures task →
The two questions are independent — every box can be occupied.
Ask both, independently

1 · Is it a mathematically valid metric?   2 · Does it capture the similarity our task needs?

Neither answer settles the other. A valid metric can be useless for a task; a genuinely useful dissimilarity need not satisfy every axiom. We’ll see both in the case studies.

Your turn · do you need a metric?

Design decision: 10 million face photos

≈
Among millions of photos, find the near-duplicate pairs.
Scenario

You must find near-duplicate faces in a 10-million-photo archive — far too many to compare every pair.

  • To prune candidates without computing every distance, which axiom must your distance obey — and why?
  • Your score gives d(A,B) ≠ d(B,A). Which axiom breaks, and does it actually matter here?
  • Keep two questions apart: is your score a valid metric, and does it capture “same person”?
Metric axioms to check:  non-negativity d(x,y) ≥ 0  ·  identity d(x,y)=0 ⇔ x=y  ·  symmetry d(x,y)=d(y,x)  ·  triangle d(x,z) ≤ d(x,y)+d(y,z)
Answers · do you need a metric?

10 million face photos — the calls

QuestionThe call
Prune without measuring every pair?Needs the triangle inequality — known distances bound unknown ones, so far-away candidates are skipped unmeasured.
d(A,B) ≠ d(B,A)?Symmetry breaks. “A is a duplicate of B” should equal the reverse — so symmetrise the score (e.g. average the two).
Valid metric vs. captures “same person”?Two separate questions. A metric buys speed (indexing); only a task-fitted score buys correctness. You want both.
The point of this part: metric properties aren’t pedantry — the triangle inequality is what makes the search feasible at all.
Part IV · Case study 1

Products: which differences matter

Designing a similarity, as a sequence of decisions.
“I want to suggest similar items”

First decide what relevance means

Amazon 'products related to this item' carousel
What makes a product a useful recommendation for another — shared category? co-purchase? “related items” / clicks vs. purchases define the target before any distance is chosen.
What information is available

Four representations of a product

Category

  • Where it sits in the catalogue tree

Text

  • Title & description terms

Price

  • A single numeric feature

Reviews

  • Ratings & their distribution
Each representation needs its own distance — and each will disagree about who the neighbours are.
Category → a tree

Taxonomy distance = shortest path

Product category taxonomy tree
Distance = path length up to a common ancestor and back down. A tree is a graph, so this is exactly the shortest-path distance from Part III — and it is a metric on category nodes. But distinct products in the same category have distance 0, so the representation, not the metric, is the limit.
Text → direction of a term vector

Cosine: similar wording, any length

cos(θ) = (a · b) / (‖a‖ ‖b‖)    dcos = 1 − cos(θ)
θ = 90° → cos = 0 doc A: “car” doc B: “automobile”
Same meaning, different words → no shared terms → the vectors are orthogonal, cosine similarity 0.
Read it carefully

Only the direction of the term vectors matters, never their length — good for descriptions of different sizes.

Blind to synonyms: “car” and “automobile” share no terms, so cosine sees them as unrelated even though the docs mean the same thing. Dense embeddings (next lecture) fix this.

Also: distance 0 means same direction, not identical; and 1 − cos θ is not a true metric.

Price → Euclidean, but beware units

Standardize — then don’t over-trust it

Feature distributions with different scales
Raw price dominates small-scale features, so standardize: z = (x − μ)/σ. But equal scale ≠ equal relevance, and it does not remove outlier sensitivity — scaling is not a priority decision.
Reviews → sparse & cold-start

What about products with no history?

Histogram of review counts / ratings
Most products have few reviews; brand-new ones have none (cold start). The distance must degrade gracefully when a representation is missing or thin.
Reviews → a distribution over ratings

A distance over customer reviews

item A item B 1★2★3★4★5★
Each item → its rating distribution; the distance compares the two histograms.
Representation + distance Encode each item by its rating distribution p = (p₁, …, p₅) — the fraction of reviews at each star level. Then d(A, B) is a distance between the two histograms.
  • Average rating alone is too lossy — very different distributions can share a mean.
  • L1 / Euclidean on the histograms is simple, but treats every star as equally far apart.
  • Earth Mover’s (Wasserstein) respects order — 4★ vs 5★ is closer than 1★ vs 5★.
Two items have “similar reviews” when their distributions match — and few-review (cold-start) items need smoothing toward a prior.
Question
Your query is a running shoe. Ranked by price, the single closest product is a formal dress shoe. Is that a good recommendation — and what decides the answer?
Same three candidates, three different distances.
Think — then → for the answer.
See the choice change the answer

One query, three candidates, three rankings

Query a running shoe · €120 · Footwear › Running · “lightweight breathable running shoe”.
CandidateBy priceBy categoryBy text
A · trail running shoe (€130)near (Δ10)nearest — same “Running”near — “running shoe”
B · running socks (€15)far (Δ105)far — Apparel › Socksnear — “breathable lightweight running”
C · formal dress shoe (€125)nearest (Δ5)mid — shares “Footwear”far — only “shoe”
Price crowns a dress shoe; text pulls in socks; only the right representation ranks the other running shoe first. The distance is the model.
From objective to algorithm

Combine distances — weights are priorities

d(x,y) = wc·dcategory + wt·dtext + wp·dprice
Two cautions, linked

The terms must be on comparable scales before you add them — exactly the standardization point again.

The weights w encode priorities; they are the model’s hyperparameters. Standardization does not choose them for you — you decide what should matter. Then rank the top-k neighbours and evaluate against real clicks/purchases.

Part V · Case study 2

Videos: which differences to ignore

Invariance, thresholds, and a system that scales.
YouTube: near-duplicates of an upload

Equivalent for our task, different in the bytes

A query video and several near-duplicates
What should be ignored: re-encoding, modest colour changes, logos/overlays, small crops. The job is the opposite of case 1 — choosing differences to discard.
Byte equality is the wrong tool

Exact ≠ near

The failure Byte equality and cryptographic hashes (MD5, SHA) are designed so one changed pixel flips the whole digest. They detect identical files, never perceptually similar ones.
We need a representation where small perceptual changes → small distance.
Construct the right representation

Perceptual hashing (pHash)

a frame perceptual hash ? black box — don’t open it 1 0 1 1 0 0 fingerprint
Each frame becomes a short fingerprint. We take the hash on faith — how it is computed is a black box here; all we need to trust is that similar frames give similar fingerprints.
The fingerprint survives re-encoding, small crops and overlays — so near-duplicate frames land on near-identical codes. We compare those codes next.
Compare → Hamming distance

Count the differing bits

a = 10110010   b = 10111010  →  dHamming = 1
Back to Part III

Hamming distance is a proper metric on fingerprints — we verified all four axioms in Part III.

Yet distinct videos can share a fingerprint. A metric in the representation space does not guarantee the originals are distinguishable — the same lesson as taxonomy-distance on products.

Make a decision, accept errors

Pick a threshold — trade off the two mistakes

Decision rule call it a near-duplicate when Hamming distance ≤ τ.
Make it scale

Fast filter → slow check

cheap candidate generation  →  expensive exact verification
A recurring pattern — fast filter, slow check

Generate a small candidate set cheaply (fingerprint buckets / LSH), then verify the few survivors with the expensive comparison. Never materialise all n² distances.

The same shape powers web search, retrieval and question answering — a recurring pattern this year.

Synthesis

Change the distance, change the patterns

Why this one choice ripples through every task.
Back to the four tasks

Changing the distance changes the answer

CaseMain lesson
ProductsChoosing which differences matter
VideosChoosing which differences to ignore
Take away · and a transfer exercise

Choosing a distance is choosing what you can see

The message

Task → representation → distance → decision. Metrics buy predictability and speed; but a valid metric and a task-useful distance are two separate questions.

Choosing a distance is choosing which patterns an algorithm can see.

Transfer: for detecting duplicate news articles — what representation would you choose, which changes should be ignored, and how would you evaluate the result?