Hi.
I am Ciro Donalek and in this module,
I'll be walking you through one
of the most exciting data mining tasks,
clustering.
We'll go over terminology, definition and
we'll see in more details some of
the models, like and self-organizing maps.
As in the previous ones,
this is a really broad subject.
So the purpose of this lectures is to
give you insights on problematics of and
also help you choosing
the right models and
the right parameters to set and
apply in your analysis.
Now, the difference between clustering and
classification may not seem
great at first but let's
remember that classification is a form of
supervised learning while clustering is.
It's the most common unsupervised task.
So the model is not provided with
the correct results during the training.
According to the cluster hypothesis,
objects in the same
cluster behave similarly.
Meaning, that points in the same cluster
are likely to be of the same type,
sharing for example,
some common statistical characteristics.
With the clustering, basically we want
to find natural groupings among objects.
So let's start with some examples,
so supposed this is our data set,
Simpson characters.
How would you divided them in clusters?
And be careful because
the notion of cluster can be
ambiguous as we see shortly.
So, we can divide them by gender,
females and males.
But also we could divide them
by their role in the series.
Like Simpson family members
versus school employees.
So these are two different but
possible clusters for this data set.
Now, let's see another example.
We have this set of points.
How many clusters do you see?
I'm pretty sure most of you would say
just two clusters because there are two
group of points that looks,
that look really well separated.
But some may see four clusters or
even six little clusters,
as shown in the figure.
From these examples, we can derive
that clustering is indeed subjective.
But in a few moments, we will also
see some measures that we can use in
evaluating the quality of clustering.
Now let's first discuss
why we need clustering.
For example, organizing data into clusters
will show the internal structure,
and that's one of the goals
in gene clustering.
Or we can use partition to achieve a goal
like in marketing segmentation where
the goal is to discover distinct groups
in the customer basis and then use
this knowledge to develop a target,
targeted advertisement, for example.
Another task is to find anomalies or
outliers that could be just measurement
errors or cool rare objects.
Outliers can be defined as in the picture
where we can see two distinct clusters and
an object that seem to not
belong to any of the clusters.
Now in clustering of course has
many applications in almost all
scientific fields, like astronomy,
visualization and so on.
Now let's give a more formal definition.
Given a set of features.
Given a set of feature vectors D
a desired number of cluster K,
an objective of function G, we want
to assign each feature vector to one
cluster in order to minimize or maximize
in some cases the objective function.
The objective function is often
defined in terms of similarity or
distances between samples or clusters.
Now we,
now needed to answer some basic questions.
Like what does similar mean?
How we can define a good partition?
How to measure the quality and so on.
So let's start in how
to evaluate clusters.
We can use two criteria,
two types of criteria.
Internal criteria and external ones.
Internal criteria are based on
the distances between points in clusters.
And the distances between the clusters.
And we'll see them in a moment because
there are many ways to compute those.
External criterion can
use direct evaluation and
the gold standard when available.
Direct evaluation means that experts or
users can manually check the clusters and
apply them in the domain of interest.
This is of course the most
direct evaluation.
But it can be also very time consuming or
unfeasible when we deal with
the huge amounts of data.
So it's unfeasible to look one by one.
Now, an alternative is to use
a labeled subset created by experts,
where the class, where the classes are
known and compute some measures on those.
Now let's start with
the internal measures.
They can be divided in two big
classes: intra-cluster distances
that are the distances between the points
belonging to the same class there.
In the intracluster distances
that are the distances between
clusters as shown in the figure.
Now, typical objective
functions in clustering aim to
obtain a low intracluster distance.
And a high inter-cluster similarity.
So we want all the points in
a cluster close together and
the cluster as distant as possible.
Now we see some of these
distances later when we talk
about the hierarchical clustering because
they are also used to match clusters.
Now keep in mind anyway that
good scores on internal
criterion do not necessarily translate
in good effectiveness in an application.
Additionally this evaluation may
be biased towards algorithms
that use the same criteria
to build the clusters.
For example,
[INAUDIBLE] that we see in the next video
naturally optimize object distances,
and the distance-based internal
criteria will likely overrate
the results of this type of clustering.
So internal evaluations are best
suit to get some insights.
But we can not imply that
one algorithm produce more
valid results than another just
based on the internal criteria.
Now, external measures instead
use a subset of labeled samples,
when this is available.
Keep in mind that the learning is
still unsupervised because the results
are evaluated based on this data, that is
not used for the actual class sitting.
And, so
this data is often created by human
expert and
the most used measures are purity,
normalized mutual information, rand index,
F measures, or Jaccard measures.
Let's start with purity.
Purity can be seen as the equivalent
of accuracy in classification.
So we assign each cluster to
the class which is most frequent.
And measure the purity by
counting the number of
the correctly assigned samples per class.
So high purity is easy to achieve
when the number of classes is large.
In particular purity=1 if each
sample gets its own cluster and
that not something we truly want.
For this reason,
we cannot use purity to trade off for
the polage of the class setting
against the number of classes.
To do so, we need other measures.
Now, this is an example
of bipurities computed.
We have 3 different classes,
cross circles and diamonds.
And let's suppose our algorithm will
find three clusters, as in the figure.
So, the first is,
the first one is assigned to cross,
because we find five
crosses in just one circle.
The second is a, assigned a circle,
and the third is assigned to diamonds.
The overall purity is 71%.
And of course the first clu,
the first cluster is the one
that looks more reliable.
So we have a some sort of purity or
so cluster based.
Now the normalized mutual information or
NMI, measures the amount of
information by which our knowledge
about the classes increases,
when we are told what the clusters are.
But this measure has
the problem as purity,
because don't penalize
large cardinalities.
So while we usually want to
follow the rule of the data.
Few clusters are better,
of course other things being equal.
Now let's see other two measures.
The Rand index measures the percentage
of decisions that are correct.
It is defined as the,
as the sum of the true positive plus
the true negative over
the total number of elements.
So in this formula false positives and
false negatives have the same weight but
as we have also seen in classification.
We may wanted to penalize one of the two,
so we can introduce weights and
use the F measure.
So and if you see the formula of the F
measures there is a beta parameters and
the if we want to penalize the false
negative its efficient to
put beta greater than one.
Now, lets now see how we can, how many
different types of classing there are.
We can,
we can say that there are 4 main sets.
And roughly speaking in
a rectangle class setting,
we want to find a successive class
using a previously established ones.
While in partitional, in partitional
clustering, data samples are divided in
a non-overlapping obj, clusters.
Then, in model based clustering, we assume
that the data are generated by a model and
we try to recover the original
model from the data.
The model that we recovered from
data then defines the cluster and,
the assignment of samples to the cluster.
So for example in the left figure,
in the left figure we have three clusters
of points generated with the distribution.
And we can see that the, EM algorithm
works well recovering all three of them.
While in the density bases approach,
like the one on the right,
classes are defined as areas of higher
density than the remainder of the dataset.
Objects in these sparse areas are usually
considered to be noise and border points.
Now, let's talk more about
hierarchical clustering.
In hierarchical clustering,
we tried to find subsequent clusters using
previously established
ones like I said before.
Now, of course, we cannot do
an exhaustive search based on all
possible combinations because it
would be computationally unfeasible.
That's why we need to use some heuristics
and we can further divide the hierarchical
cluster algorithms in agglomerative or
bottom-up and divisive or top-down.
In a bottom-up,
approach we start with each element
in a separate cluster and then merge
them accordingly to a given property.
On the contrary, with a top-down approach,
we start with all the points in just one
cluster, and then start dividing them.
Let's see with two examples how this work.
So, suppose we have six points
distributed as in the left figure,
as, as in the right figure.
So, black numbers are the points and
in red, the clusters created.
In a bottom-up approach,
we start with four clusters.
One in three, two in five and
four in six have their own clusters.
And then we can start combine them.
Now hierarchical clustering of
a course has some pro and some cons.
In we, in hierarchical clustering,
one of the pros that this,
that we don't need to specify,
in advance, the number of clusters.
And we can later decide where to cut,
in order to have the decided
number of clusters.
So, it's also intuitive, because we are
used, we are also used to think this way.
Unfortunately, they,
they're not scaled well.
Like in the, like any realistic
algorithm local optima can be a problem.
Now, so far, we have talked about
distances between clusters and
weight to match them.
Now we can see, detail, some alternatives.
Single link is defined as the smallest
distance between an element in
one cluster and an element in the other.
This is a local measure since we pay
attention only in the area where the two
clusters are close to each other.
So, other more distant parts of
the clusters are not taken into account.
So, we don't really pay attention
to the shape of the cluster when
we use this distance.
Now, complete link clustering takes into
account also the, takes into, into account
the largest distance between an element in
one cluster and an element in the other.
Basically, we measure the similarity
of two classes as the,
is the similarity of their
most dissimilar members.
This criterion is not local,
because the entire structure of the
clustering can influence the decisions.
And so this method works better for
compact clusters with the small
diameters over long clusters.
But its, but
it is also very sensitive to layers.
For example, a sample, just one sample,
far from the center can increase
the diameters of candidate merge clusters.
And completely change
the final clustering.
Another method that probably is the most
commonly used is the average link.
And it's defined as the average distance
between an element in one cluster and
an element in the other.
Basically, the cluster quality is based
on all similarities between samples.
And so we can avoid all the pit
force of the single link and
complete the link criteria.
Which equates the cluster
similarity with the similarity of
a single pair of samples.
Other [INAUDIBLE] involved
is the centroid medoids and
we'll see it when we talk about
now we'll talk about similarity.
And in generally, in general,
similarity measures are function that,
costs are quan, are function that quantify
the similarity between the two objects.
And they are based on distance metrics.
Now, let's see some distance measures and
when we should use them.
Euclidean Distances are probably
the most commonly used and
produce a kind of
a sphere shaped clusters.
They are often used in
optimization problems, and
especially the square Euclidean distance,
even if it's not really a metric,
because it doesn't satisfy
the triangle inequality.
Now, the taxicab geometry is a form
of geometry in which the usual,
the usual Euclidean distance ir,
is replaced by a new metric,
in which the distance between two points.
Is the sum of the absolute differences
of the Cartesian coordinates and
they produce sort of
a diamond shape clusters.
Cosine similarity is another distance
common used in information revival.
Basically, cosine similarity should
narrate a metric that shows how
related that to samples by looking at
the angle instead of the magnitude.
For example, in text mining,
gives a useful
measure of how similar two
documents are likely to be.
In terms of their subject matter, for
example, like in the figure for similar
scores, vectors are in the same direction
forming an angle near to zero degree.
The mahalanobis distance is a measure
of the distance between a point and
the distribution.
And in the previous video, we have
also seen some other distances that
can be used in the form of text or
binary data, like the hemming distance.
Now, we have talked about hierarchical
clustering, let's now briefly introduce
partitional clustering, that we'll see
more details when we speak about k.
In partitional clustering,
we need to specify the number of
the desired clusters k, even giving it
an input because we know what to expect or
trying a multiple ones and
determining the best using a sum measure.
In partitional clustering each distance
is placed the one over the clusters, and
we can have hard and soft clustering.
I hard clustering, each sample is
a member of one cluster exactly.
An alternative definition about cluster,
of hard clustering is that
a sample can be a full member of more
than one cluster, but a full member.
So it's like a sort of crisp
classification 01, belong with a cluster,
not belong to a cluster.
In soft cluster each sample is
instead the degree of membership,
of membership for each clusters.
Some researcher, researchers also
distinguish between exhaustive clustering
that assigns each sample to a cluster and
non-exhaustive clustering.
When we can have some samples that
don't belong on to any of the clusters.
And that can be useful in for
example, for outlier detection.
Now, in summary, in this video we have
talked about the different types of
clustering, how to choose the right model,
metrics and object,
objective function
depending on our problem.
Then we have introduced the hard and
soft clustering that can be
related with the decreased probabilistic
classification for supervised algorithms.
And we have also seen the differences
between the exhaustive and
non-exhaustive classes.
Now, in the next two lectures we'll
see some models in more details