So imagine for a second that you are blindfolded,
right? And you're just dropped out of a helicopter
into some completely unknown area of the city.
That is quite the start to a Tuesday. Right.
But bear with me. You have absolutely no idea
where you are. And to figure out if you've landed
in, say, a commercial district or a residential
neighborhood, Well, you don't sit there and try
to construct some complex mental map of urban
zoning laws. No, of course not. You just reach
out. Exactly. You just reach out, walk around
slightly, and identify the five closest buildings
to you. Makes sense. And if you feel around and
find three houses and two office buildings, you
logically deduce, hey, I must be in a residential
area. Yeah. You rely entirely on your immediate
surroundings. Yeah. And today, we're going straight
to the core of how computers use this exact this
very primitive human instinct to drive modern
artificial intelligence. It's honestly a phenomenal
starting point, because when we strip away all
the intimidating jargon surrounding machine learning,
the actual mechanics of how software makes decisions,
they often resemble the most basic, intuitive
ways we humans make sense of our environment.
Like, we assume algorithms require some hyper
-futuristic logic, but the foundations are just
highly practical. And that is exactly our mission
for you today. We're doing a deep dive into the
source material on the K -Nearest Neighbor's
algorithm, or KNN, as it's usually called. KNN,
yes. It is one of the absolute oldest classification
methods out there, which I found crazy, like
dating back to 1951. And we really want to cut
through the dense technical concepts here to
understand not just what this algorithm does,
but why it matters when we rely on computers
to categorize literally everything from Text
documents to live video streams. Absolutely.
OK, let's unpack this. I just used that blindfold
analogy to describe reaching out to five buildings.
In the literature we're looking at, this seems
to map directly onto the core function of the
algorithm, right? Oh, it maps perfectly. I mean,
the documentation formally calls this a plurality
vote. Plurality vote, OK. Yeah. So in your scenario,
the five closest buildings represent what the
algorithm calls the K nearest training examples.
That K is really just a positive integer. Usually
a pretty small number, right? Right, usually
small. So the algorithm looks at an unknown object,
which is you, standing there blindfolded, finds
its closest neighbors, and simply assigns it
to the class that is most common among those
neighbors. So if k equals 1. If k is 1, it just
takes the exact identity of the single closest
building. No voting needed. That is, well, the
history here is fascinating too, because like
I mentioned, this isn't some modern Silicon Valley
invention. Not at all. The sources know the fundamental
was actually developed by statisticians, Evelyn
Fix and Joseph Hodges, back in 1951. Yes, and
it was later expanded upon by Thomas Cover. Right.
But looking at how it actually functions today,
the categorical voting makes total sense, like
three houses beat two offices, easy. But I'm
trying to picture what happens if we aren't sorting
things into rigid categories. Okay, what do you
mean? Well, say I want the algorithm to predict
a specific continuous number, like... estimating
the property value of a new house based on its
neighbors. A house can't be, you know, category
$500 ,000 and just vote on it. The logic seems
like it would just hit a wall. You'd think so,
yeah. But what's fascinating here is that the
algorithm adapts to continuous variables through
a process called KNN regression. Regression.
Yeah, it's sometimes referred to as nearest neighbor
smoothing. So instead of taking a plurality vote
of categories, the algorithm just shifts its
math. It calculates the actual average value
of those k nearest neighbors. Oh, wow. So it's
not actually predicting a new value from thin
air. It's just finding a localized compromise
of what already exists right around it. Precisely.
So if you want to know the property value of
a new house, and you set your K to five, the
algorithm finds the five most physically similar
houses in your historical data. Right. It takes
their known property values, averages them out,
and assigns that average to the new house. The
neighborhood logic remains identical. It just
outputs a mean rather than a majority. OK, but
wait. That raises a massive logistical problem,
though. How so? You just said it finds the five
most physically similar houses. How does a computer
actually measure similarity or nearness? I mean,
if you're measuring a house, you have square
footage, which is in the thousands, and then
you have the number of bedrooms, which is usually
less than 10. I see where you're going with this.
Or even worse. If the algorithm is analyzing
countries, it might look at life expectancy in
years versus GDP in trillions of dollars. If
a computer is just crunching raw numbers, that
GDP figure is going to completely swallow the
life expectancy figure, right? Just because trillions
are mathematically way larger than double digits.
You've zeroed in on one of the most critical
vulnerabilities of K &N. The computer does not
know. what a dollar or a year is. Right. It's
just numbers. Exactly. It just sees a massive
number versus a tiny number. So if the features
represent different physical units or they just
come in vastly different scales, the accuracy
of the algorithm severely degrades. The distance
calculation just gets completely warped by whichever
feature has the largest absolute numbers. So
we have to somehow force all these different
measurements to speak the same numerical language
before the algorithm even looks at them. Exactly.
The data has to undergo what we call feature
-wise normalizing. Normalizing, got it. Yeah,
we scale the features down so they carry the
appropriate weight. Often that means compressing
everything into a proportional range, like between
0 and 1. Oh, OK. So a trillion dollars becomes
like 0 .8, and 80 years of life expectancy becomes
0 .8 as well. Right. And researchers put massive
effort into this pre -processing stage. The text
actually mentions they frequently use evolutionary
algorithms to optimize how features are scaled,
or they scale them based on the mutual information
they share with the training classes. OK. So
assuming we've scaled everything properly so
the GDP doesn't crush the life expectancy. What
kind of ruler is the algorithm actually using
to measure this distance? Well, for continuous
variables like height, weight, or distance, it
typically uses the standard straight line measurement
we all learned in high school geometry, Euclidean
distance. Ah, good old Euclidean distance. Lies.
But the algorithm is highly adaptable, depending
on the data. If you are working with discrete
variables, like, say, classifying text documents,
it uses an overlap metric, also known as Hamming
distance. Hamming distance. Okay, I'm picturing
that like grading a multiple -choice test. You
aren't measuring a physical line between two
essays. You're just counting exactly how many
specific positions match up and how many don't.
That is a highly accurate way to visualize it.
It measures the minimum number of substitutions
required to change one string of data into the
other. That makes a lot of sense. And it goes
even deeper. In bioinformatics, specifically
with highly complex gene expression microarray
data, researchers use correlation coefficients
as their distance metric. Like what kind of coefficients?
Things like Pearson and Spearman correlation.
As long as you give it the appropriate mathematical
measuring stick, the algorithm can find a neighborhood
in almost any data set. You know, there's a behavioral
quirk of this algorithm mentioned in the sources
that I found just incredibly relatable. Oh, yeah.
It calls KNN a lazy algorithm because it defers
all computation until the absolute last second.
It essentially just memorizes the training data
without doing anything with it. It's very true.
It totally reminds me of a college student who
refuses to study all semester, brings an enormous
stack of textbooks to an open book final exam,
and then frantically tries to look up the closest
matching answers in real time while the clock
is ticking. The lazy learning categorization
is completely accurate. I mean, unlike other
machine learning methods, there is no explicit
training phase where the algorithm builds some
complex internal model or decision tree beforehand.
It just sits there. It just stores the feature
vectors and class labels. That's it. The actual
mathematical function is only approximated locally
when a query is actually made. But because it's
doing this open book frantic search at the very
last second, relying entirely on a local vote,
here's where it gets really interesting. Doesn't
that expose a huge flaw if the historical data
is skewed? How do you mean? Let's say we have
a data set that is flooded with blue squares,
just thousands of them, and it only has a tiny
handful of red triangles. If I drop a new point
right next to a red triangle, but there are 100
blue squares nearby just because they are everywhere
in the system, those blue squares are gonna win
the vote by sheer volume. The nuance of that
smaller group gets totally drowned out by the
tyranny of the majority. That skewed class distribution
is a very real problem. The majority class will
dominate the predictions simply because they
show up more often in that k -nearest neighborhood.
So how do we fix it? Well, the mathematical solution
to this is quite elegant. We use a weighted nearest
neighbor classifier. OK, so we stop treating
every neighbor's vote as equal. How do we decide
whose vote matters more? We assign weights based
on proximity. Instead of every one of the neighbors
getting an equal vote, which would be a weight
of one over K, we multiply their vote by a weight
proportional to the inverse of their distance.
Inverse distance. OK, meaning the closer you
are to the query point, the louder your voice
gets in the vote. Exactly. So a red triangle
sitting right next to me gets a massive megaphone,
while the 50 blue squares sitting further away
get their volume turned way down, even if they're
technically inside my neighborhood. Exactly.
It prevents distant crowds from shouting down
the immediate local reality. And the sources
also mentioned another fascinating abstraction
to solve this, called a self -organizing map,
or SOM. SOM. How does an SOM physically change
the data to fix the skew? Think of it as creating
regional representatives. Instead of looking
at every single individual point, which gives
the advantage to the most crowded demographic,
the sum creates nodes. Node, okay. Yeah, and
each node acts as a single representative center
for a cluster of similar points, regardless of
how densely packed that original cluster was.
Oh, wow. It essentially levels the playing field
by condensing the data into evenly weighted prototypes
before the K &N vote is even applied. That makes
the voting process infinitely fair. But that
brings us to the actual size of the neighborhood.
How do we pick the magic number K? That is the
good question. Right. Because if I ask three
people, I get a very specific local answer. But
if my K is 300, my immediate neighborhood gets
completely diluted by the broader city. You've
hit on the core tension of tuning the algorithm.
Larger values of kin definitely reduce the effect
of random noise because you're taking a broader
consensus. But you are absolutely right that
it makes the boundaries between different categories
a lot blurrier. So is there a rule of thumb?
Well, if you are dealing with a binary classification
problem, meaning there are only two possible
categories to choose from, you must choose an
odd number for K. Oh, to prevent a tied vote.
Exactly! Because if K is 4, you could end up
with a 2 to 2 split and the algorithm just gets
stuck. Precisely. And to find the empirically
optimal k, researchers often utilize what's called
the bootstrap method. They repeatedly resample
the data, estimating the accuracy of different
k values, until they find the mathematical sweet
spot that balances noise reduction with distinct
boundaries. OK, I want to circle back to the
lazy learning concept for a second, because I
just can't shake the logistical nightmare of
it. the open book test problem. Yes. If the algorithm
doesn't build a streamlined model in advance,
and it just calculates the distance to every
single stored example at the very last minute,
what happens when the data set is massive? Yeah,
that's a problem. I mean, if I have a million
data points, and each point has dozens of features,
searching through all of that in real time seems
like it would just crash a computer. Oh, it absolutely
would. And this introduces one of the most dramatically
named concepts in all of data science, the curse
of dimensionality. The curse of dimensionality.
Honestly, it sounds like an Indiana Jones artifact,
but I'm guessing it's a mathematical trap. This
raises an important question, right? Because
it is a severe trap. When you start adding too
many dimensions to your data, usually once you
get past 10 dimensions or features, the very
concept of Euclidean distance begins to physically
break down. Wait, I'm starting to picture how
distance just breaks down. A foot is a foot.
Regardless of how many things you're measuring,
right? Not in high dimensional space. Imagine
a standard 3D room. OK. There's a clear center
and there are corners. But as you add dimension,
say you stretch it into a 100 dimensional room,
the mathematical volume of that space expands
exponentially. The geometry works out such that
almost all the data points get pushed to the
outer crust of that space. The crust. Yes, the
center becomes virtually empty. Oh, wow. So if
my query point is in the middle of this 100 -dimensional
room, practically all the historical data points
are pushed out to the walls, meaning they're
almost exactly the same distance away from me.
Exactly. When every point is roughly equidistant
from the search query, the concept of a nearest
neighbor becomes mathematically meaningless.
Because everyone is equally far away. Right.
The algorithm gets paralyzed because nothing
stands out as being closer than anything else.
So if the data has too many features, the algorithm
essentially goes blind. So how do we break the
curse? We have to aggressively simplify the data
using dimension reduction. Before we ever apply
the KNN algorithm, we transform the data to extract
only the most critical information, creating
a low dimensional embedding. The sources cite
techniques like principal component analysis
or PCA and linear discriminant analysis. I hear
terms like principal component analysis a lot
in AI discussions. What is that physically doing
to the data to solve this dimensionality problem?
Think of it like taking a 3D shadow of a complex
object. If you have a highly complex multidimensional
shape, PCA essentially shines a mathematical
light on it to cast a flattened shadow. OK, I
can picture that. It squashes the data down so
you only keep the most distinct important outlines,
the principal components, and it throws away
all the useless depth and noise that's just confusing
the algorithm. The text gives a great real -world
example of this in a computer vision pipeline
for face recognition. Like how facial recognition
unlocks a smartphone. Yes. run KNN on millions
of raw high -definition pixels. That's way too
many dimensions. Right. So the pipeline starts
with a hair face detection algorithm just to
locate the face, uses mean shift tracking to
follow it, and then crucially uses a PCA projection.
It compresses that incredibly complex visual
data down into a manageable feature space. Oh.
So only after the face is flattened into its
core mathematical shadow is the KNN classification
applied to identify who it actually is. Exactly.
problem by squashing the features. But what about
the sheer volume of the data? Like, squashing
the features helps, but if I still have a billion
individual records, the last -minute open book
search still takes way too long. Do we just,
I don't know, randomly delete half the historical
data and hope for the best? Not randomly, no.
We use data reduction techniques to systematically
eliminate stored examples. A classic method mentioned
in the text is the condensed nearest neighbor
rule, or CNN, also known as the Hart algorithm.
OK, so how does the Hart algorithm decide what
gets kept and what gets thrown in the trash without
ruining the accuracy? It looks for what we call
prototypes. Essentially, if a data point is sitting
completely surrounded by other points of its
exact same class, it's considered an absorbed
point. Absorbed. Yeah. It doesn't offer any new
information for drawing the boundary lines between
categories. It's redundant. It's safe and obvious.
So the algorithm deletes it. It prioritizes keeping
points that have a high border ratio. Border
ratio. Meaning we want to keep the data points
that sit. right on the turbulent messy edge between
two different classes. Precisely. Those boundary
cases are the most informative for making future
decisions. The safe echo chambers in the middle
of a cluster are just noise. By tossing them
out, this algorithm can sometimes reduce a data
set to just 15 or 20 percent of its original
size while maintaining full accuracy. Keep the
edge cases, throw away the echo chamber. I absolutely
love that. That's a re -efficient. Now, we've
spent this entire time talking about how K and
N use a similarity to find its neighbors. But
the source material mentioned a variant that
flips this entirely on its head, and I found
it fascinating. The furthest neighbor variant.
Instead of finding what's closest, the algorithm
actively seeks out maximal dissimilarity. It
looks for the total opposites. Why would we ever
want an algorithm to actively seek out things
that don't belong? It has a highly creative application
and recommender systems. It's used to build what's
called an inverted neighborhood model. So instead
of a streaming platform doing the standard, you
know... People who like this movie also like
these exact same movies. What is the furthest
neighbor doing? It identifies the users who are
the absolute most dissimilar to you. And it uses
their preferences inversely to generate your
recommendations. That's wild. Now, historically,
furthest neighbor methods achieve lower predictive
accuracy. They aren't going to perfectly guess
your next favorite movie. But what they do achieve
is a massive increase in novelty and diversity.
Oh, to break you out of the echo chain. Exactly.
They are designed to break you out of your algorithmic
filter bubble by recommending things that the
traditional nearest neighbor method would just
completely ignore for being too weird or unpopular.
An algorithm mathematically designed to give
you a surprise. That's great. Are there other
ways we use this to find the weirdos in the data?
Yes, actually. KNN is also highly effective for
anomaly detection. The mechanism is incredibly
simple. If we measure the distance to your cave,
nearest neighbor, and that distance is massively
large, it tells us that your local density is
very low. You are sitting out there... entirely
by yourself. You're a statistical outlier. Exactly.
Despite being such a simple foundational model,
using K &N for finding anomalies and outliers
works remarkably well. It even holds its own
against much more complex modern data mining
methods. So what does this all mean? Let's tie
all of this together. We've gone from blindfolded
people feeling houses to flattening faces into
mathematical shadows. We have covered a lot of
ground. At its core, KNN is this brilliantly
simple concept from the 1950s, the idea that
you are who you hang out with, mathematically
brought to life. We've explored how it uses plurality
voting, how it survives skewed data by turning
up the volume on the closest neighbors, and how
it survives the absolute nightmare that is the
curse of dimensionality by squashing data down
to its most useful prototypes. And if we connect
this to the bigger picture... understanding these
mechanisms, how algorithms handle noisy data,
skewed populations and border cases, it's vital.
It isn't just an academic exercise. It gives
you a framework to think critically about how
software is categorizing your own digital footprint
every single day and why it might be making the
assumptions it makes. Absolutely. And as we wrap,
I want to leave you with one final thought to
mull over. and this builds directly on something
kind of hidden in the source material regarding
the one nearest neighbor classifier. Oh, the
simplest version. Right. This is the absolute
simplest version, where k equals exactly 1. You
only look at the single closest point. Ah, you
were referring to the Bayes error rate property.
It is one of the most profound mathematical proofs
in classification logic. It really is. Because
the math shows that as your historical data set
grows and approaches infinity, simply using the
one nearest neighbor rule guarantees an error
rate that is no worse than twice the Bayes error
rate. Which is huge. Right. For context, the
Bayes error is the theoretical minimum possible
error you can ever mathematically achieve. Think
about the philosophical weight of that for a
second. We constantly assume that making the
best decision requires a complex consensus. Yeah,
a committee. Exactly. We assume we need a weighted
average of hundreds of different opinions or
a massive convoluted decision tree. But this
mathematical proof says that's not necessarily
true. It challenges our entire assumption about
what constitutes intelligence in decision -making.
Right. With enough historical experience, with
a massive enough memory of past data, simply
looking at the single closest past example gets
you incredibly close to the absolute best possible
decision you could ever mathematically make.
It's pretty mind -blowing. Does that mean having
a massive, perfectly preserved memory of past
experiences is actually more effective than having
a highly complex reasoning process? If you're
blindfolded in the city, maybe you don't need
to feel five buildings to know where you are.
If you've been to enough places, maybe you only
need to touch one wall. Thank you so much for
joining us on this deep dive. Keep questioning
the algorithms, keep exploring the data, and
we'll catch you next time.