UUtah F2026 | Data Mining | L6 - Similarities

Overview

The lecture develops similarity as a way to score how alike objects are, then uses Jaccard similarity to compare sets of text shingles. It explains how k-gram choices shape document representations and introduces MinHash, whose key property is that two documents’ hash values collide with probability equal to their Jaccard similarity—a foundation for scaling similarity search with locality-sensitive hashing.

Key takeaways

Jaccard similarity, |A ∩ B| / |A ∪ B|, scores both shared elements and total set size; the lecture’s example sets yield 3/8 = 0.375.
Two-word shingles preserve local order that bag-of-words vectors discard, while representing shingles as sets deliberately discards term counts.
Text shingle design is task-dependent: stop-word removal, punctuation, sentence boundaries, part-of-speech features, and k all change what the similarity score captures.
Jaccard comparison does not need a predefined vocabulary, unlike bag-of-words vectors, making it convenient for evolving or mixed sets of elements.
MinHash is designed so that two sets collide with probability equal to their Jaccard similarity, allowing randomized hashes to estimate set resemblance.
Maintaining the minimum hash over a document’s shingles permits a one-pass signature computation; locality-sensitive hashing builds on this property to find similar documents without exhaustive comparisons.

Chapters

0:00 Project Proposal Requirements and Data Mining Project Scope

Project teams must have 2–3 members; students can connect in class or through the Canvas discussion board.
By Tuesday, each team must submit a 100–200-word proposal as a PDF, with every member uploading the same file.
Projects should focus on discovering structure in data, not primarily optimizing a classifier; a classifier may serve as a black-box evaluation tool.
Projects using personally sourced data—such as research, work, or a hobby dataset—can offer useful domain knowledge for judging results.

9:00 Homework 2: GloVe Embeddings and Approximate Similarity Search

Homework 2 uses 100-dimensional GloVe word embeddings to explore similarity search.
Students are asked to install and use a fast nearest-neighbor search package rather than rely on brute-force search.
A provided Overleaf template is optional; students may use their own format if it remains clear.
The homework also introduces hashing-related similarity methods, with a bonus question for students seeking a harder extension.

12:00 Similarity Scores Reverse the Direction of Distance

A distance is small for nearby inputs, while a similarity score is large for inputs considered alike.
A similarity is generally a bivariate function S(A, B) that returns a scalar score, commonly between 0 and 1.
Identical inputs often have similarity 1, but this is a convention rather than a universal rule.
Unlike distance metrics, similarities are not always constrained by the same mathematical properties.

17:00 Converting Similarities into Distances

A common conversion is D(A, B) = 1 − S(A, B), producing a distance bounded between 0 and 1 when similarity is in that range.
Another conversion is the square root of S(A, A) + S(B, B) − 2S(A, B).
For an ordinary inner product, the second expression becomes Euclidean distance because the self-similarities give squared vector norms.
Depending on the similarity definition, one conversion may yield a metric while the other does not.

23:00 Similarity as a Modeling Choice and the Limits of Approximation

A useful similarity score maps each pair to a comparable scalar, so an algorithm can rank pairs by how alike they are.
Some scores, including an unnormalized dot product, can be negative; cosine similarity also need not follow the usual 0-to-1 convention.
Randomized search methods may estimate distances rather than compute them exactly, and approximation error can sometimes disrupt properties such as the triangle inequality.
The lecture introduces Jaccard similarity as a concrete set-based alternative to vector distance.

27:00 Jaccard Similarity Measures Set Overlap

Jaccard similarity is |A ∩ B| / |A ∪ B|, comparing the overlap of two sets with the total number of distinct elements they contain.
For A = {0, 1, 2, 5, 7} and B = {0, 2, 3, 5, 6, 9}, the intersection has 3 elements and the union has 8, giving 3/8 = 0.375.
The score is between 0 and 1: identical sets score 1, and sets with no overlap score 0.
Jaccard distance, 1 minus Jaccard similarity, is a metric; Jaccard and weighted variants are widely used for set comparisons.

35:00 Bag-of-Words Vectors Count Terms but Ignore Word Order

A bag-of-words representation maps a document to a vector of word counts, using a vocabulary that may contain 10,000 or more terms.
In the Dr. Seuss example, the vector records counts such as five occurrences of “I” and zero occurrences of “zebra.”
Bag-of-words vectors lose word order: “I am Sam” and “am I Sam” can map to the same representation.
BM25 is a more sophisticated weighting approach that adjusts term importance, including downweighting common words.

41:00 K-Grams and Shingles Preserve Local Word Context

A k-gram, also called a shingle, is a sequence of k consecutive words extracted with overlaps.
For k = 2, “I am Sam” produces “I am” and “am Sam”; for k = 5, the example includes overlapping phrases such as “do not like them Sam.”
Representing a document as a set of k-grams preserves local word order and makes unrelated text less likely to collapse to the same representation.
Unlike bag-of-words vectors, k-gram sets typically record whether a phrase occurs, not how many times it occurs.

45:00 Text-Shingle Representations Require Explicit Modeling Choices

Removing stop words is one option for excluding common terms that contribute little individual meaning.
Punctuation can be discarded or retained; an em dash may be useful for an authorship task even if punctuation is irrelevant to topic matching.
Shingles may cross sentence boundaries, as in the example’s “Sam to” sequence, or be restricted to individual sentences.
The representation can also encode parts of speech or word weights, and k must be chosen to balance context length against the chance of overlap.

55:00 Character K-Grams Extend the Method Beyond Word Tokenization

Character-based k-grams can be useful when a text has few distinct symbols, such as DNA sequences built from A, C, G, and T.
Because the character alphabet is smaller than a word vocabulary, character k-grams often use a larger k.
Character-level tokenization can also help with languages or settings where word segmentation and training data are limited.
These alternatives show that choosing words, characters, punctuation, and k is part of the modeling task.

57:00 Comparing Four Dr. Seuss Lines with Jaccard Similarity

The example treats each of four lines as a separate document and represents each as a set of two-word shingles.
Jaccard similarity compares each pair of line-specific shingle sets without requiring a shared vocabulary vector.
The method is intended to capture topical or textual resemblance, such as whether two web pages or articles discuss similar material.
The setup illustrates how a set representation can be used directly with the Jaccard formula.

1:02:00 Worked Jaccard Scores Show Overlap and Set Size Together

Documents 1 and 2 share one shingle, “I am,” and have three distinct shingles in their union, yielding similarity 1/3.
Documents 1 and 3 have no shared shingles, so their Jaccard similarity is 0.
Documents 1 and 4 share “I am”; their union contains eight shingles, giving similarity 1/8.
The full pairwise comparison balances shared shingles against union size, so longer documents do not automatically receive higher similarity.

1:04:00 Jaccard Sets Avoid a Fixed Vocabulary

Jaccard comparison needs only the elements present in the two sets; it does not require defining all English words or possible k-grams in advance.
A bag-of-words model instead needs a specified vocabulary and corresponding vector dimensions.
A set of movie genres can also represent a movie, allowing genre-based comparisons without a fixed vector space.
New set elements can be incorporated without redefining a global list of features.

1:09:00 Scaling Similar-Document Search Beyond Brute Force

For one billion documents represented as k-gram sets, scanning every document for each query is too costly.
Finding all similar document pairs by comparing every pair also scales quadratically.
Search engines can use similarity to retrieve relevant documents and identify duplicate or near-duplicate pages before serving results.
Set representations lack the vector geometry used by some nearest-neighbor methods, motivating MinHash and locality-sensitive hashing.

1:14:00 MinHash Targets Jaccard Similarity Through Collision Probability

MinHash uses a randomly selected hash function from a family; a fixed random salt can make the chosen function deterministic for repeated use.
The desired property is P(H(A) = H(B)) = Jaccard(A, B), with probability taken over the random hash choice.
Identical sets should always collide, while disjoint sets should have zero collision probability in the ideal construction.
More similar documents therefore have a greater chance of landing in the same hash bucket.

1:18:00 The MinHash Minimum Enables One-Pass Document Processing

For a set T of shingles, hash each element and return the smallest hash value: initialize v to infinity, then update v whenever h(xᵢ) < v.
The resulting set-level hash is the minimum of the element-level hash values, rather than a count or ordered list of shingles.
The minimum can be maintained as shingles are generated in a single scan through a document.
The lecture leaves the collision-probability proof and the use of MinHash for scalable retrieval to the next discussion of locality-sensitive hashing.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, UofU Data Science.