7. Market Segmentation using Jaccard Similarity
A note before starting: Every prior section (popularity, collaborative filtering, ALS) answered some version of “what rating would this user give this movie?” This section asks a completely different question — “do natural groups of similar-behaving users exist at all, and what do they look like?” It’s not a model comparison, and there’s no RMSE table at the end. If you’re here for the modeling results, feel free to skip this section — it’s exploratory and business-facing rather than predictive.
1. Why Measure Similarity?
Underneath a surprising number of unrelated-sounding problems is the same question: given two things, how much do they overlap?
- Recommender systems — how similar are two users’ viewing histories?
- Search engines — is this webpage a near-duplicate of one already indexed?
- Plagiarism detection — does this essay share large chunks of text with another?
- Fraud detection — does this new account’s behavior overlap suspiciously with a known bad actor’s?
This is a genuinely different flavor of problem than the ones tackled so far in this project. ALS and cosine-based CF are both magnitude-aware — they care about how much someone liked something. This section deals with set similarity — a more foundational tool that only asks whether two things overlap, with no notion of magnitude or learned structure at all. It’s closer to a raw data-structures-and-probability tool than a trained model, which is exactly why it shows up as a building block inside many larger systems rather than standing alone as a full recommender.
Sets vs. vectors vs. user-item matrices. Everything in this project so far represented users as rows in a matrix (ALS) or as rating vectors (cosine CF). This section represents each user as something simpler: a plain set — the collection of movies they’ve interacted with, nothing else. No ratings, no order, no matrix — just “did they watch it, yes or no.”
2. Jaccard Similarity: Measuring Set Overlap
What Jaccard measures. Given two sets, how much of their combined content do they share?
\[J(S_1, S_2) = \frac{|S_1 \cap S_2|}{|S_1 \cup S_2|}\]Why not just count the overlap directly? The naive idea — just count how many movies two users share — fails immediately: a user who’s watched 2,000 movies will share a lot with almost everyone, simply by virtue of watching everything, not because they have similar taste to any one person in particular. Dividing by the union fixes this: it normalizes overlap against each pair’s combined footprint, so a small but concentrated overlap (5 shared movies out of 10 total) scores higher than a large but diluted one (50 shared movies out of 2,000 total).
Manual calculation. Say Alice watched {Titanic, Notebook, Matrix} and Bob watched {Titanic, Avengers, Matrix, Inception}.
- Intersection: {Titanic, Matrix} → size 2
- Union: {Titanic, Notebook, Matrix, Avengers, Inception} → size 5
Strengths. Simple, interpretable, needs no training or optimization, and naturally suited to binary/implicit signals — exactly the kind of data real production systems often have far more of than clean star ratings.
Limitations. Jaccard only knows presence or absence — it has zero concept of how much someone liked something. Two users with wildly opposite taste (one loves everything they watched, the other hates everything they watched) can still score a perfect Jaccard similarity of 1.0 if they happened to watch the exact same movies. This is a real blind spot for anything trying to predict taste — but it’s not a flaw for the specific question this section is asking (shared behavioral footprint, not shared taste), a distinction returned to later.
Why exact Jaccard becomes expensive at scale. Computing this for every pair requires $O(n^2)$ comparisons, and each comparison needs full set intersection/union — fine at 610 users (~186K pairs), but computationally infeasible at the scale real systems operate at (millions of users, or billions of documents in a search-engine context).
3. MinHash: Making Jaccard Scalable
The computational problem. At real scale, two things break: storing full sets for every user/document becomes expensive, and comparing every pair ($O(n^2)$) becomes intractable — a billion documents means a billion-squared comparisons, infeasible no matter how fast the hardware.
The intuition behind MinHash. Instead of comparing full sets directly, compress each set into a small, fixed-size signature, such that comparing signatures approximates the true Jaccard similarity — without ever recomputing a full intersection or union.
Step-by-step:
- Hashing items — apply a random hash function to every element in a set (e.g., every movieId a user watched).
- Taking the minimum hash — keep only the single smallest hashed value from that set. This one number is the set’s “signature” under this particular hash function.
- Building a signature — repeat with many different random hash functions (e.g., 10, 100), producing a short vector of min-hash values per user — dramatically smaller than the original set, regardless of how large that set was.
- Comparing signatures — check what fraction of positions match between two users’ signatures.
Why matching MinHash values estimate Jaccard. This isn’t a heuristic — it’s a provable result: under a uniformly random hash function, the probability that two sets produce the same minimum hash value exactly equals their true Jaccard similarity:
\[P(\text{minhash}(S_1) = \text{minhash}(S_2)) = J(S_1, S_2)\]Averaging this probability across many independent hash functions gives an unbiased estimate of Jaccard similarity — using only a short signature instead of the full sets.
Exact vs. estimated Jaccard. The estimate converges toward the true value as more hash functions are used, but it’s still an approximation — with a small dataset like ours, it’s worth directly comparing the two to see how close they land (done in the segmentation walkthrough below).
Pros and cons. MinHash dramatically reduces the cost of each comparison (short signatures instead of full sets) and, combined with Locality-Sensitive Hashing (LSH) — bucketing similar signatures together so only likely-similar candidates are ever compared — avoids the full $O(n^2)$ comparison entirely. The cost is that results are approximate, not exact, and the approximation quality depends on how many hash functions are used.
4. Beyond Set Similarity: Cosine Similarity
Jaccard’s blind spot — no sense of magnitude — is a real problem the moment the question shifts from “did they watch the same things” to “do they feel the same way about the things they watched.”
Representing users as rating vectors, rather than plain sets, brings magnitude back into the picture. Cosine similarity measures the angle between two rating vectors — capturing whether two users’ rating patterns align, not just whether their watch histories overlap.
This is exactly the tool used in the collaborative filtering section of this project — computed over sparse user-item matrices, where most entries are missing rather than zero (a genuinely different structure than a dense document-term matrix, and one of the reasons that section’s cosine computation was built the way it was).
Why similar users can still behave differently on an individual movie. Even two users with high cosine similarity — genuinely aligned taste on average — can disagree sharply on any single specific movie. Aggregate similarity is a statement about overall pattern, not a guarantee about any one prediction.
5. From Similarity to Recommendation: ALS
The limitation of neighborhood-based similarity (Jaccard, cosine, both): predictions are only ever computed from directly observed overlaps — a specific pair of similar users, or a specific pair of similar items. There’s no shared underlying structure being learned across the whole dataset simultaneously — no compression, no generalization beyond direct comparison.
Latent factors and matrix factorization — the approach covered in the ALS math section — take a different approach: rather than comparing raw rows/columns directly, learn a compressed, shared representation for every user and every movie simultaneously, such that even completely unobserved (user, movie) pairs get a meaningful prediction, purely from that shared latent structure.
Jaccard → MinHash and Cosine → ALS are not the same progression. It’s tempting to read this whole post as one continuous “fix the previous tool’s flaw” chain — but that’s not quite accurate, and worth being precise about. Jaccard → MinHash is a scalability fix — MinHash doesn’t change what is being measured, only how efficiently it’s estimated. Cosine → ALS is a completely different kind of upgrade — cosine similarity and ALS answer genuinely different questions (direct neighbor comparison vs. learned shared structure), not the same question solved more efficiently. These are two separate axes of improvement, not one single narrative arc.
6. MovieLens Market Segmentation: Putting Jaccard + MinHash Into Practice
The objective. Unlike every other section in this project, this isn’t about predicting a rating. It’s about answering: do natural groups of users exist, based purely on shared behavioral footprint — and what do those groups actually watch?
Why segment users, and not movies? Nothing about Jaccard forces a choice here — the exact same formula works symmetrically on movies:
\[J(\text{movie}_1, \text{movie}_2) = \frac{|\text{users who watched both}|}{|\text{users who watched either}|}\]would tell you how similar two movies are, based on shared audience. That’s a legitimate, complementary segmentation — “which movies attract the same crowd” rather than “which people behave alike.” Users were chosen here because the framing is market segmentation — a business question about audiences, not about content. The movie-side version is a natural extension worth acknowledging, but it answers a different question (item clustering) than the one this section sets out to answer (audience clustering).
A clarification worth stating plainly before going further: none of what follows involves the model “understanding” genres, actors, or content in any way. This point matters enough to slow down on, since it’s easy to conflate with how ALS’s latent factors work.
Everything in this section happens in two completely separate phases:
- Phase 1 — pure numbers, no genre knowledge at all. Each user is represented as nothing more than a set of
movieIdintegers. Jaccard and MinHash measure how much these numeric sets overlap between users. The output of this phase is purely structural: “user 7, user 12, and 85 other users all landed in the same connected component because their movieId sets overlapped heavily.” At this point, there is zero information about what those movies are or why the users are similar — just that they are, numerically. - Phase 2 — a separate, after-the-fact lookup, added purely for human interpretation. Once segments exist as groups of userIds, a completely different, simple question is asked: given that we know which users are in Segment 0, what movies did they actually watch, and what genres do those movies belong to? This joins each segment’s users back to
train(to find which movies they watched) and then tomovies.csv— which already contains agenrescolumn, human-labeled metadata bundled with the MovieLens dataset itself. Nothing was learned or classified here; the code simply counts, for each segment, which genre labels appear most often among the movies that segment watched.
This is a different mechanism from ALS’s latent factors, worth contrasting directly: ALS’s \(k\) dimensions are learned and have no inherent label at all — you cannot ask ALS “what does dimension 3 mean” and get “Action” as an answer; any such interpretation would itself require a similar post-hoc inspection step. Jaccard segmentation, by contrast, never learns anything comparable — it groups raw IDs by overlap, full stop, and genre labeling is bolted on afterward using metadata that already existed, not discovered by the clustering process itself.
Step 1 — Convert users into sets. Every user’s row becomes a plain set of movieIds they interacted with, discarding rating values entirely — a deliberate choice, since the question here is about exposure, not taste.
Step 2 — Compute exact Jaccard similarity. At 610 users (~186K pairs), this is completely tractable directly — no approximation needed at this scale.
\[J(\text{user}_1, \text{user}_2) = \frac{|\text{movies watched by both - intersection}|}{|\text{movies watched by either - union}|}\]Step 3 — Build MinHash signatures and estimate Jaccard. Even though exact computation is feasible here, MinHash was applied anyway, specifically to demonstrate the technique and validate it against ground truth — the kind of check that matters immensely at real scale, where exact computation wouldn’t be an option at all.
Step 4 — Compare exact vs. approximate results. The mean absolute error between exact and MinHash-estimated Jaccard similarity, across all compared pairs, quantifies how good the approximation is with the number of hash tables actually used — a genuine sanity check, not just a formality.
A quick note on vocabulary before continuing: this section starts using graph language — nodes and edges — which is worth grounding concretely if it’s unfamiliar. A graph here is just two things: nodes (each user is a node — 610 users, 610 nodes) and edges (a line drawn between two nodes whenever some condition is true). Here, an edge gets drawn between user A and user B whenever their Jaccard similarity exceeds a chosen threshold. This is the same object as an adjacency matrix from linear algebra, just drawn as dots and lines instead of a matrix of 0s and 1s — row i, column j = 1 in the matrix is exactly the same fact as “an edge exists between node \(i\) and node \(j\)” in the graph picture.
“Connected components” means groups of nodes that are all reachable from each other by hopping along edges — and critically, this reachability is transitive. If Alice-Bob have an edge, and Bob-Carol have an edge, Alice and Carol end up in the same component too, even with zero direct edge between them, purely by hopping through Bob. This transitive-chaining behavior is exactly what causes the giant-component problem walked through below.
Step 5 — Identify behavioral segments. Thresholding the exact Jaccard similarity graph and finding connected components.
Where the threshold comes from, and why it’s a genuine choice, not a fixed rule. Drawing an edge requires deciding what counts as “similar enough” — and nothing in the Jaccard formula tells you what that cutoff should be. It’s a free parameter, in the same spirit as \(k\) in ALS or \(C\) in the popularity shrinkage formula: a number you choose, then validate by observing its effect. Worth being explicit that this is a separate step from MinHash entirely — MinHash only estimates the similarity number (a stand-in for exact Jaccard); the threshold decision happens afterward, deciding what to do with that number once you have it. And unlike the
Corrank/regParamsweeps earlier in this project, there’s no RMSE or Precision@K here to say which threshold is objectively “best” — this is a judgment call based on producing interpretable, reasonably-sized groups, not a metric being minimized.
At a threshold of 0.15, connected components produced 7 groups: one with 424 users (70% of the entire dataset) and rest between only 2 to 5 users. (Note - Any user with zero edges at all — meaning their Jaccard similarity with every other user fell at or below the threshold — is completely invisible to this component-counting logic, therefore the total number of users after the threshold segmentation may not add up to 610).
The above not a meaningful segmentation — it’s the giant component problem, a well-known phenomenon in network science, and precisely the transitive-chaining effect just described, playing out at scale.
Diagnosing it properly — a threshold sweep. Rather than accepting or discarding this result outright, the threshold was swept across a range of values to see how the largest component’s size responds:
| Threshold | Edges | Largest component | # components |
|---|---|---|---|
| 0.10 | 17,320 | 535 (88% of users) | 9 |
| 0.15 | 7,211 | 424 (70%) | 7 |
| 0.20 | 3,837 | 317 (52%) | 7 |
| 0.25 | 2,283 | 179 (29%) | 11 |
| 0.30 | 1,501 | 86 (14%) | 10 |
| 0.35 | 852 | 80 (13%) | 6 |
The giant component shrinks steadily and predictably as the threshold tightens — Low thresholds admit enough edges for transitive chaining to fuse nearly everything; tightening the bar progressively fragments the graph into smaller, more distinct, more interpretable pieces.
Why 0.15 looked stricter than it actually was. The percentile distribution of exact Jaccard scores across all ~186,000 pairs explains the failure directly:
| Percentile | 25% | 50% | 75% | 90% | 95% | 99% | max |
|---|---|---|---|---|---|---|---|
| Jaccard | 0.009 | 0.025 | 0.054 | 0.096 | 0.134 | 0.275 | 0.773 |
A threshold of 0.15 sits between the 95th and 99th percentile — only the top 3-4% of all pairs clear it. That sounds strict, but 3-4% of ~186,000 pairs is still over 7,000 edges, more than enough for transitive chaining to fuse most of the graph. Percentile-based intuition about “a strict cutoff” doesn’t reliably predict where a similarity graph actually fragments — an empirical sweep is needed to find that point directly, rather than assuming a high percentile threshold is automatically safe from the giant-component effect.
The usable operating point. Around 0.30–0.35, the graph fragments into comparably-sized, genuinely distinct components (86 and 80 users in the largest component, several more in the 6–10 user range) — a far more interpretable segmentation than the original 424/5 split.
Step 6 — Interpret the segments. Joining each segment back to movies.csv’s genre data reveals what each behavioral cluster actually watches. Even the flawed initial 424-user “mega-segment” and the 5-user outlier segment showed a genuine difference worth noting: the small segment’s genre profile leaned more heavily toward Romance appearing in its top-5 genres, while the giant segment’s top genres (Drama, Comedy, Action, Thriller, Adventure) mostly just reflect the dataset’s overall genre popularity — itself a useful confirmation that an under-fragmented segment tells you little beyond “this is what’s popular overall,” reinforcing why the threshold sweep and a properly fragmented segmentation matter for genuinely useful audience profiles.
The limitation, stated plainly. Behavioral overlap is not identical taste. Two users in the same segment share exposure — they’ve watched similar things — but as established back in Section 2, they could feel completely oppositely about every one of those shared movies. This is precisely why this section is framed as a segmentation/insight exercise rather than a competing prediction model: it answers a genuinely different, complementary question to everything else in this project, not a better answer to the same one.
Appendix: MinHash, Worked From Scratch
MinHash is named for exactly what it does: for each random hash function, keep the minimum hash value produced by the items in a set.
1. Take a set and hash every item
\[A = \{A, B, C, D\}\]Apply a hash function, producing (illustrative) numbers:
\[A \to 73,\quad B \to 12,\quad C \to 91,\quad D \to 45\]Take the minimum:
\[\min(73, 12, 91, 45) = 12\]So
\[\text{MinHash}(A) = 12\]under this hash function.
2. Why the minimum? — the random-ordering connection
Imagine instead randomly shuffling the items into an order, like $D, E, C, A, B$ — the first item, $D$, is what we’d care about. A random hash function does the same job without physically generating a shuffle: since hash values look random, whichever item gets the smallest hash value is equivalent to whichever item would appear first in a random ordering. Taking the minimum hash is a computational shortcut for “find the first item in a random ordering,” without ever generating that ordering explicitly.
3. Why matching minimums estimate Jaccard
\[A = \{A,B,C,D\}, \qquad B = \{B,C,D,E\}\]Apply one shared hash function to every item across both sets:
\[A\to73,\ B\to12,\ C\to91,\ D\to45,\ E\to30\]For set \(A\): hashes are \({73,12,91,45}\), minimum \(=12\).
For set \(B\): hashes are \({12,91,45,30}\), minimum \(=12\).
They match. Why? Because \(B\) (the item, value 12) happens to be the smallest-hashed item across the entire union \({A,B,C,D,E}\), and \(B\) is a member of both sets — so both sets’ minimums land on it.
4. What if the minimum belongs to only one set?
A different hash function might give:
\(A\to10,\ B\to50,\ C\to80,\ D\to60,\ E\to20\).
Set \(A\)’s minimum: 10 (item \(A\), which only belongs to set \(A\)). Set \(B\)’s minimum: 20 (item \(E\), which only belongs to set \(B\)). The minimums don’t match — because the smallest-hashed item in the union this time wasn’t a shared element.
The general rule this reveals: the two minimums match exactly when the smallest-hashed item in the union of both sets happens to be a member of both sets (i.e., in the intersection). Since the hash values are effectively a random ordering, the probability of this happening is precisely :
\[\frac{|\text{intersection}|}{|\text{union}|}\]— which is exactly the Jaccard similarity formula. This is why matching MinHash values, on average, estimate true Jaccard similarity.
5. One hash function isn’t enough — build a signature
A single hash function gives a single yes/no match — too noisy to trust alone. Repeat with many independent hash functions, and record the minimum from each:
| Hash 1 | Hash 2 | Hash 3 | Hash 4 | Hash 5 | |
|---|---|---|---|---|---|
| User A | 12 | 81 | 34 | 7 | 91 |
| User B | 12 | 44 | 34 | 19 | 91 |
This row is the MinHash signature — \(A \to [12, 81, 34, 7, 91]\), \(B \to [12, 44, 34, 19, 91]\) — a short, fixed-length compression of each set, regardless of how large the original set was.
6. Comparing signatures to estimate Jaccard
Compare position by position:
| A | B | Match? | |
|---|---|---|---|
| H1 | 12 | 12 | ✓ |
| H2 | 81 | 44 | ✗ |
| H3 | 34 | 34 | ✓ |
| H4 | 7 | 19 | ✗ |
| H5 | 91 | 91 | ✓ |
3 out of 5 positions match:
\[\hat J(A,B) = \frac{3}{5} = 0.6\]This is the estimate — the more hash functions used, the tighter this estimate converges to the true Jaccard similarity.
The whole story, in one line
Jaccard defines what similarity means → a random-ordering argument gives the mathematical trick for estimating it cheaply → MinHash implements that trick by keeping the minimum hash value per set → matching MinHash values, across many hash functions, estimate Jaccard similarity without ever computing a full intersection or union.