Machine learning is transforming the world around us. To become successful, you’d better know what kinds of problems can be solved with machine learning, and how they can be solved. Don’t know where to start? The answer is one button away. During this course you will: - Identify practical problems which can be solved with machine learning - Build, tune and apply linear models with Spark MLLib - Understand methods of text processing - Fit decision trees and boost them with ensemble learning - Construct your own recommender system. As a practical assignment, you will - build and apply linear models for classification and regression tasks; - learn how to work with texts; - automatically construct decision trees and improve their performance with ensemble learning; - finally, you will build your own recommender system! With these skills, you will be able to tackle many practical machine learning tasks. We provide the tools, you choose the place of application to make this world of machines more intelligent. Special thanks to: - Prof. Mikhail Roytberg, APT dept., MIPT, who was the initial reviewer of the project, the supervisor and mentor of half of the BigData team. He was the one, who helped to get this show on the road. - Oleg Sukhoroslov (PhD, Senior Researcher at IITP RAS), who has been teaching MapReduce, Hadoop and friends since 2008. Now he is leading the infrastructure team. - Oleg Ivchenko (PhD student APT dept., MIPT), Pavel Akhtyamov (MSc. student at APT dept., MIPT) and Vladimir Kuznetsov (Assistant at P.G. Demidov Yaroslavl State University), superbrains who have developed and now maintain the infrastructure used for practical assignments in this course. - Asya Roitberg, Eugene Baulin, Marina Sudarikova. These people never sleep to babysit this course day and night, to make your learning experience productive, smooth and exciting.
K-means clustering
Loading...
来自 Yandex 的课程
Big Data Applications: Machine Learning at Scale
50 个评分
与讲师见面
Vladimir Lesnichenko
Pavel MezentsevSenior Data Scientist
PulsePoint inc
Emeli Dral
Alexey A. DralFounder and Chief Executive Officer
BigData Team
Ilya TrofimovPrincipal Data Scientist
Yandex
Evgeny FrolovData Scientist, PhD Student @Skoltech
Computational and Data Intensive Science and Engineering
Let's continue talking about unsupervised learning techniques.
Now, we'll focus on a different question,
can we find any clusters in the data?
I think it's the time to discuss what clusters are.
Formally, what we usually understand by clusters is a group of
points which are more similar to each other than to other groups.
Among many definitions of what this similarity might mean,
we'll consider the most useful one.
A group of points is considered to be a cluster,
if the distances among them are much
smaller than the typical distance of points outside of the clusters.
To understand what I mean, look at this picture.
On the left, you can see set of points that
doesn't show any particular clustering structure,
while on the right, set of points clearly consist of two clusters.
Of course, if we could always just take a look at the picture,
there would be no need for any techniques,
but unfortunately, if we are dealing with multidimensional data,
they are absolutely required.
As I've told you previously,
all the unsupervised learning tasks need some formalization.
To formalize a clustering task,
we should first define the metric.
In other words, we need to say,
how we are measuring distances between our points in space.
I suggest to stick with simple Euclidean measure.
For now, though, you of course,
can use all other kinds of metrics.
Another simplification that will do for now,
is supposed that we somehow know the number of clusters in the data.
The parameter k will stand for this number.
Let's associate each cluster with its central point,
Mu with an index i.
To calculate the coordinates of its central points,
we just need to average the coordinates of all the points in the cluster.
On the other hand, a set of central points defines all clusters by a simple rule.
For each point, we find the closest center and assigned it to the corresponding cluster.
Imagine that we have some cluster candidates,
let's define the function that measures how good the clustering is in the following way.
Take for each cluster,
total sum of distances from points to their center,
and add up these values for all clusters.
In case the value of k equals to one,
we don't have any options and just assign all the points to one cluster.
In this case, the value of function V is the sum of length of green segments.
In case the value of k is equal to two,
and the clustering is done properly,
that is we distinguish the left group from the right.
The value of V is a sum of length of red segments.
So, at least in this example,
the function V seems to be much smaller for proper clustering compared to a wrong one.
Now, we are ready to formulate our task in case of a fixed and known k. Our task is
finding such centers of clusters that minimize the energy function V. Turns out,
the task is finding a real global minimum is np-hard.
We kind of have to try
all the possible clustering options which typically are of a large number.
The most reasonable alternative is a simple gradient Lloyd's
algorithm which is guaranteed to converge to a local minimum.
Let's see how it works.
First of all, we fixed the value of k,
and initial centers of k clusters.
The next steps, are we assigning all points to the clusters according to current centers?
Followed by recalculating the centers again.
These two steps are iterated,
until the centers stop changing from iteration to iteration.
Let's see it again on the picture.
First, we assign initial centers,
then assign each point to a cluster,
then recalculate the centers and so on.
Just in a few iterations here,
the cluster center stop changing,
and we found the desired clustering. Nice and easy.
Moreover, this algorithm is easily adapted to distributed settings.
When you start at points on Hadoop cluster, namely,
cluster assignment can be done in parallel on the map step,
while new centers can be calculated on the reduced step.
Let's address some important issues of the algorithm.
The first and the simplest one is scaling.
The recipe is straightforward.
Data should always be standardized before applying kmeans.
Otherwise, the distances are dominated by features with large values,
and the result of a clustering is usually useless.
Another issue is a strong dependence on the initial centers.
It's been shown over time that in many examples,
that a purely random initialization doesn't work well.
Fortunately, there is a good heuristic called kmeans++ that seems to work much better.
The heuristics makes use of the fact that closely selected centers tend to work poorly.
So the idea to make the process iterative,
picking one center at a time,
making sure that the next center is not close to already selected.
To achieve it, every time,
the probability of which point to become a center of a cluster is
proportional to square distance to the closest already chosen center.
So, the further the point,
the more the probability.
To make this process easier to execute in parallel.
There's been proposed the better version of kmeans++ called kmeans parallel.
The idea is to reasonably reduce a set of candidates for becoming a center,
and then to apply kmeans++ on the small set of candidates.
This heuristic is implemented in Spark MLlib.
Well, looks like there is an elephant in the room.
Of course, I completely forgot to tell you how to define the number of clusters.
This is the most tricky question as there is no right answer to it.
I'll tell you the simplest approach that is called,
The Elbow method which is similar to what we've discussed previously.
Remember, that we've been minimizing the V function,
when k equals to one,
it gets its maximum value which we'll call V total.
The idea is to try different values of k and see
how small the value of V function becomes as a fraction of V total.
So, we could build this simple graph showing reduction of V for various values of k,
and look at the so-called elbow point.
Just to remind you, this is the point where the marginal reduction becomes rather small.
In this example, the elbow point is k equal to three,
which indicates that the most reasonable number of clusters is three.
Actually, there are many other ways to answer this question,
and I encourage you to at least get familiar with them.
So, today we've learned about the task of finding clusters in the data.
We discussed formal definition of a cluster along with the formal definition of our task.
Then we talked about kmeans method,
with different heuristics to define initial sentence,
and to define the number of clusters.
