Discovering Patterns Without Labels: Unsupervised Techniques

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 7.2 Free with a free account

Discovering Patterns Without Labels: Unsupervised Techniques

Introduction to Artificial Intelligence · Chapter 7: Machine Learning, NLP, and PerceptionSection 7.2 · lesson 50 of 6916 min · free with a free account

← Learning from Labeled Data: Supervised TechniquesNext lesson: Combining Natural Language Processing with Deep Learning →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

How clustering, PCA, association rules and anomaly detection find structure.

  • Trace k-means and compare it with hierarchical clustering and DBSCAN
  • Explain how PCA reduces the number of features while keeping most of the variance
  • Calculate support, confidence and lift for an association rule
  • Detect anomalies with robust scores and evaluate clusterings with the silhouette

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (2,170 words). Read along, or search it.

Opening Question

Plenty of Data, No Answer Key

A supermarket has millions of till receipts. Nobody has labeled them family shopper, or student. A bank has millions of transactions, and almost none are marked as fraud. A biologist measures 64 features for every sample. Plenty of data, and no answer key. So what can a program discover on its own, and how would anyone know it's any good?

Four Tasks

Clustering, Reduction, Associations and Anomalies

Unsupervised learning finds structure without labels. With only inputs, it can't be correct; it can only describe the data usefully. It has four main tasks. Clustering finds groups of similar items, like customers with similar buying habits. Dimensionality reduction describes the data with fewer numbers. Association rules find things that occur together, like bread and butter. And anomaly detection finds the items that don't fit. One warning applies throughout: with no answer key, the algorithm always returns something, even from random data.

Clustering

Grouping by Distance After Standardizing

Clustering divides items into groups, so that items in a group are similar, and items in different groups are different. Similarity is usually distance between feature values: the closer two items are, the more alike they are. So standardize the features first, to average zero and spread one. Otherwise income, in thousands, drowns out the number of children.

k-Means

Assign and Update Until Stable

The most common method is k-means. It splits the data into exactly k groups, each summarized by its centroid, the average of its members. Start by choosing k centroids, for example k random data points. Then assign: give each point to its nearest centroid. Update: move each centroid to the average of the points assigned to it. Repeat those two steps, until the assignments stop changing.

Worked Example

A Poor Start in Round One

Eight points: four near one corner, A to D, and four near the other, E to H. Let k be two. Suppose a poor start: both centroids in the lower-left, on A and on B. Round one, assign. c1 keeps only A and C. Centroid c2 is a little closer to everything else, so it grabs B and D, and all four far points too. Update. c1 moves to one, one and a half. And c2 lands in the middle of nowhere, at about 5.7, 5.5. The total squared distance, from each point to its new centroid, is 91.3.

Worked Example

The Groups Separate in Round Two

Round two. Now c2 is clearly nearer the upper-right group, so the two groups separate cleanly: A to D, and E to H. The centroids move to the centers of the two groups, and the total falls to 4.0. Round three: no point changes group, so the algorithm stops.

Limitations

Starting Points and the Elbow Method

k-means is simple, fast on large data, and always converges. But you must choose k in advance, and the result depends on the start, so it can get stuck in a poor solution. It also suits round clusters of similar size, and outliers drag its centroids. Remedies for the start: run it several times and keep the lowest total, or use k-means++, which spreads the starting centroids apart. To choose k, the elbow method plots the total for each k, and looks for the bend. In one set of 300 points, the total fell from 3,190 at k equals two, to 465 at three, then barely moved. The bend is at three.

Hierarchical Clustering

Dendrograms and Linkage Rules

Hierarchical clustering needs no k. It starts with every item alone, and repeatedly merges the two closest clusters. The merges form a tree, a dendrogram. Cut it at a chosen height to get clusters. But what does closest mean, for two clusters? That rule is the linkage. Single linkage uses their closest pair of members. Complete linkage uses their farthest pair. Average linkage averages over all pairs.

Worked Example

Single Versus Complete Linkage

Take six values: 1, 2, 5, 9, 10, and 15. Every rule first merges 1 with 2, and 9 with 10. Then single linkage joins 5 to the left group at three, and the two groups at four, since 5 is just four from 9. Cut into two clusters, single linkage leaves 15 alone. A chain of near neighbors stretched across the data. Complete linkage compares farthest members, so it splits one, two, five from nine, ten, fifteen: compact groups. Average linkage agrees. A long stretch with no joins suggests where to cut. And since it needs every pairwise distance, the method is slow on huge data.

DBSCAN

Core, Border and Noise Points

DBSCAN defines a cluster as a dense region, separated from other dense regions by sparse space. It needs two settings. eps is the radius of a neighborhood around a point. minPts is how many points, counting the point itself, that neighborhood must hold to count as dense. A core point has at least minPts points within eps. Clusters grow outward from core points. A border point has too few neighbors of its own, but lies within eps of a core point. It sits on a cluster's edge. A noise point is neither. It belongs to no cluster, and is flagged as an outlier. DBSCAN picks an unvisited core point, gathers everything reachable through chains of dense neighborhoods into one cluster, and repeats.

Quick Check

Classifying the Point at 2.8

Quick check. Five points on a line: 1.0, 1.5, 2.0, 2.8, and 6.0. Take eps equals one, and minPts equals three. What kind of point is 2.8? Pause, and decide. Border. Within one of 2.8 lie only 2.0 and itself: two points, short of three, so it isn't core. But 2.0 is core, with four, and 2.8 is within its reach. So 2.8 joins the cluster's edge, instead of being noise. The real noise is 6.0, with nobody near it.

Comparison

DBSCAN Recovers Interlocking Crescents

DBSCAN finds clusters of any shape, needs no k, and identifies noise. Imagine two interlocking crescents, plus twelve stray points. In one example, k-means with k equals two cut straight through the crescents. Its agreement with the true grouping was only 0.21. DBSCAN recovered both crescents exactly, and flagged seven of the twelve strays as noise. Its own difficulty: eps and minPts must be chosen well, and it struggles when clusters have very different densities.

PCA

Principal Components Capture Variance

Next, dimensionality reduction. Many features often move together, like neighboring pixels in a handwritten digit. Principal component analysis, or PCA, finds new axes that are combinations of the original features. The first component points where the data varies most. The second is perpendicular, and captures most of the rest. Take six points that lie close to a rising line. Center them on their mean, compute how the two features vary and co-vary, and find the directions. The first component points along the line. Its variance is 6.73, against only 0.13 across it. So the first component alone holds 98.1 percent of the variance. Each point becomes one number instead of two, and very little is lost.

Worked Example

Compressing Handwritten Digits

Scale it up: 1,797 handwritten digits, each 8 by 8 pixels, so 64 features. The first two components keep 28.5 percent of the variance. Ten keep about 74 percent, and just 21 of the 64 keep 90 percent. Plotted on just two components, images of the same digit land near each other, though PCA never saw a label. The limits: PCA finds only straight-line patterns, its axes can be hard to explain, and it needs standardized features.

Association Rules

Support, Confidence and Lift

Association rules find items that occur together in market baskets, like bread, then butter: baskets with bread tend to have butter. Three measures judge a rule. Support is the share of all baskets that contain the whole set: how common it is. Confidence of A then B is the support of A and B, over the support of A: of the baskets with A, the share that also have B. Lift is the confidence, divided by the support of B: how much more often B shows up with A than it does normally. Lift above one means a positive association; exactly one, unrelated; below one, less often than chance.

Worked Example

Frequent Sets and the Apriori Principle

Here are ten baskets. Choose a minimum support of 0.3: at least three of the ten. Count single items: bread 7, butter 5, milk 5, eggs 4, jam 3, and cola only 2. The Apriori principle saves work: if a set is infrequent, every larger set containing it is too. So nothing with cola needs counting. Only three pairs are frequent: bread with butter, in five baskets, and bread with jam, and bread with milk, in three each.

Worked Example

Confidence Is Not Symmetric, Lift Is

Now form rules from those pairs, and keep the ones with confidence of at least 0.6. Bread then butter has confidence 0.71. Butter then bread has 1.00: every butter basket has bread. Confidence isn't symmetric, but lift is: 1.43 both ways. Now milk then bread. Its confidence is 0.60, so it passes. But its lift is 0.86. Bread is in seventy percent of all baskets, but only sixty percent of milk baskets. And associations aren't causes. Putting butter next to bread may help, but butter doesn't make anyone buy bread.

Quick Check

Eggs Then Milk Has a Lift of One

Quick check, with the same ten baskets. Eggs appear in four of them, milk in five, and both together in two. Is eggs then milk a useful rule? Pause, and decide. No. The support is two tenths. Confidence is 0.2 over 0.4: one half. And milk's own support is also one half, so the lift is exactly one. Egg buyers take milk exactly as often as everyone else. Fifty percent confidence is just the base rate.

Anomaly Detection

Point, Contextual and Collective Anomalies

Anomaly detection finds items that differ markedly from the rest, like an odd card purchase, or a sensor drifting before a failure. Anomalies are rare and varied, so there are few labeled examples, and detection is usually unsupervised. A point anomaly is one value far from the rest. A contextual anomaly is normal in general, but odd for its context: thirty degrees Celsius in January. A collective anomaly is a group that's odd together, though each item is fine alone, like a flat-lining heartbeat trace. Approaches include statistical limits, robust statistics, distance and density, isolation by random splits, and reconstruction error from PCA.

Worked Example

Z-Scores and the Masking Problem

A common rule can fail. Twelve server response times, in milliseconds: all near a hundred, and one at 250. The z-score is a value's distance from the mean, in standard deviations. A common rule flags anything above three. The mean is 112.8, and the standard deviation 43.3. So the spike scores 3.17, and is just flagged. Now let a second spike, 240, replace one normal value. The mean rises to 124.6, and the standard deviation to 56.4. The spikes now score only 2.23 and 2.05. Neither is flagged. The spikes pull up the mean and stretch the spread, hiding themselves. That's masking. With twelve values, no z-score can exceed 3.18.

Robust Scores

Median and MAD Resist Masking

The robust version uses the median, the middle value, and the MAD, the median of the distances from the median. Its score is 0.6745, times the distance from the median, divided by the MAD. Values above 3.5 are commonly flagged. With both spikes, the median is 101.5, and the MAD is 3. The spikes score 33.4 and 31.1, far above the limit, while normal points score at most 1.2. And since anomalies are rare, even a good detector raises mostly false alarms. Treat flags as candidates for review.

Evaluation

The Silhouette Score

Finally, how good is a clustering, with no answer key? The silhouette score asks two things of each point. a is the average distance to the rest of its own cluster. b is the average distance to the nearest other cluster. Its silhouette is b minus a, over the larger of the two: near one, snug; near zero, on a boundary; negative, probably misplaced. Back in the eight-point example, point D has a of 1.14, and b of 7.79, so its silhouette is 0.85. Averaged over all eight points, two clusters score 0.87, but three clusters only 0.52, which correctly says two is better.

Cautions

Measures Reward What They Were Designed For

If a true grouping is known, the adjusted Rand index compares the two: one is perfect agreement, and zero is chance. But internal measures favor round clusters. On the crescents, k-means, which cut them wrongly, scores a silhouette of 0.48, and DBSCAN, which found them, only 0.33. A measure rewards what it was designed to reward. So combine several measures, check stability across reruns, and look at the clusters themselves.

Application

What the Supermarket Can Find

Back to the supermarket's receipts. With no labels, a program can still find a lot. Standardized k-means or DBSCAN finds shopper groups, PCA makes them plottable, rules judged by lift find what's bought together, and robust scores flag odd receipts. And whether it's any good takes checks: silhouette, stability, and a plain meaning someone can act on.

Key Takeaways

Groups, Components, Rules and Outliers

To sum up. Unsupervised learning finds groups, simpler descriptions, associations and anomalies, and it always returns something, so check it. k-means needs k and suits round clusters. Hierarchical builds a dendrogram, and DBSCAN finds any shape and marks noise. PCA keeps the directions of greatest variance. Rules are judged by support, confidence and lift. Robust median scores resist masking, and the silhouette favors round clusters, so look at the results too.

Think About It

A Low Silhouette for Viewer Groups

Here's something to think about. A streaming service clusters its viewers into five groups, and the silhouette is only 0.31. Why might the score be low, even if the groups are useful to the marketing team? And what would you check before trusting them?

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Discovering Patterns Without Labels: Unsupervised Techniques

How does the k-means clustering algorithm work?
k-means splits data into exactly k groups by repeating two steps: assign each point to its nearest centroid, then move each centroid to the average of its assigned points. It stops when the assignments no longer change. Results depend on the starting centroids, so it is common to run it several times or use k-means++, and the elbow method helps choose k.
What is the difference between k-means and DBSCAN?
k-means needs k chosen in advance and suits round clusters of similar size, while DBSCAN defines clusters as dense regions and can find clusters of any shape. DBSCAN uses a radius, eps, and a minimum count, minPts, to label core, border and noise points, so it also flags outliers. Its difficulty is choosing those settings well and handling clusters with very different densities.
What do support, confidence and lift mean in association rules?
Support is the share of all baskets containing the whole item set; confidence of A then B is the support of A and B divided by the support of A; and lift is that confidence divided by the support of B. In ten baskets, if eggs appear in 4, milk in 5 and both in 2, confidence is 0.5 and lift is exactly 1, so the items are unrelated.
Why can z-scores fail to detect outliers?
Z-scores can fail because outliers pull up the mean and stretch the standard deviation, hiding themselves, an effect called masking. With twelve server response times near 100 milliseconds plus spikes at 250 and 240, the spikes score only about 2.2 and 2.1, under the common limit of 3. A robust score based on the median and the MAD flags both easily, at over 30.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →