Well, hello, my dear friends, thanks for coming back.
As I'm sure you remember from our previous lessons, we talked about supervised learning methods.
So because we wrap that in this lesson, we're going to try to understand unsupervised machine learning
methods.
So let's start.
All right, so what is unsupervised learning then?
Well, in some pattern recognition problems, the training data consists of a set of input vectors X
without any corresponding target values.
The goal in such unsupervised learning problems may be to discover groups of similar examples within
the data.
That's going to be called clustering or to determine how the data is distributed in space that's known
as density estimation.
So maybe to put it in simpler terms for an end sampled space x one to X in true class labels are not
provided for each sample.
That's known as learning without a teacher.
So there are some issues with unsupervised learning.
Unsupervised learning is harder when it's compared to supervised learning tasks.
How do we know if the results are meaningful, since no answer labels are available?
It also has to let an expert look at the results.
Which calls for an external evaluation.
Define an objective function on clustering or internal evaluation.
So why unsupervised learning, why do we need it in spite of these issues?
Well.
Annotating large data sets is very costly, and hence we can label only a few examples manually.
For example, speech recognition.
Now, there may be cases where we don't know how many or what classes the data is divided into.
For example, data mining.
And we may want to use clustering to gain some insight into the structure of the data before designing
a classifier.
So unsupervised learning can be further classified, I believe in the two separate categories parametric,
unsupervised learning, non-parametric unsupervised learning.
So in this case, we assume a parametric distribution of data.
So it assumes that sample data comes from a population that follows a probability distribution based
on a fixed set of parameters.
Theoretically, in a normal family of distributions, all members have the same shape and our parameter
raised by mean and standard deviation.
So that means if you if you know, the mean and standard deviation and the distribution is normal.
You'll know the probability of any future observation.
Parametric, unsupervised learning involves construction of Gaussian mixture models and using expectation
maximization algorithms to predict the class of the sample in question.
So this case is much harder than the standard supervised learning because there are no entry labels
available and hence there is no correct measure of accuracy available to check the result.
So in non parameter rise versions of unsupervised learning.
The data is grouped into clusters where each cluster hopefully says something about categories and classes
present in the data.
So this method is commonly used to model and analyze data with small sample sizes.
Unlike parametric models, non-parametric models do not require the modeler to make any assumptions
about the distribution of the population and so are sometimes referred to as distribution free methods.
Now we can categorize unsupervised learning algorithms into two categories themselves Clustering Association.
In this course, we're just examining the clustering.
So what is clustering that?
Clustering can be considered the most important unsupervised learning problem.
So as every other problem of this kind, it deals with finding a structure and a collection of unlabeled
data.
A loose definition of clustering could be the process of organizing objects into groups whose members
are similar in some way.
A cluster is there for a collection of objects which are similar between them and dissimilar to the
objects belonging to other clusters.
All right, so given a set of points with a notion of distance between points, grouping the points
into some number of clusters such that internal or within the cluster distances should be small.
That is, members of clusters are close or similar to each other.
External or intra cluster distances should be large.
That is, members of different clusters are dissimilar.
Well, the goal of clustering is to determine the internal grouping and a set of unlabeled data.
But how do you decide what constitutes a good clustering?
It can be shown that there is no absolute best criterion, which would be independent of the final aim
of the clustering.
So consequently, it is think that it are you the user who should supply this criteria in such a way
that the result of the clustering will suit your needs.
So here, if you look at this image, how do we know what is the best clustering solution?
Good thing you're here in this course, because I'll tell you to find a particular clustering solution
will need to define the similarity measures for the clusters.
Start with proximity measures.
For clustering, we need to define a proximity measure for two data points.
Proximity here means how similar dissimilar the samples are with respect to each other.
A good proximity measure is very application dependent.
The clusters should be invariant under the transformations natural to the problem.
Also, while clustering, it is not advised to normalize data that are drawn from multiple distributions.
All right, so we can classify clustering algorithms as listed like this.
Exclusive clustering.
Overlapping clustering.
Hierarchical clustering.
Probabilistic clustering.
And the first case data are grouped in an exclusive way so that if a certain data point belongs to a
definite cluster, then it could not be included in another cluster.
A simple example of that is shown in this figure, where the separation of points is achieved by a straight
line on a bi dimensional plane.
No, on the contrary, the second time the overlapping clustering uses fuzzy sets to cluster data so
that each point may belong to one or more clusters or two or more clusters with with different degrees
of membership.
So this case data will be associated to an appropriate membership value.
A hierarchical clustering algorithm is based on the union between the two nearest clusters.
The beginning condition is realized by setting every data point as a cluster.
Then, after a few iterations, it reaches the final clusters wanted.
And finally, the last kind of clustering uses a completely probabilistic approach.
And here we're going to run down four of the most used clustering algorithms.
K means.
Fuzzy K means.
Hierarchical clustering.
Mixture of Gaussians.
So each of these algorithms belongs to one of the clustering types listed here.
While K Means is an exclusive clustering algorithm, fuzzy case means is an overlapping clustering algorithm,
hierarchical clustering is obvious.
And lastly, mixture of Gazans is a probabilistic clustering algorithm.
All right, let's have a look at the first one.
K means clustering.
Cummins is one of the simplest unsupervised learning algorithms that solves a well known clustering
problem.
The procedure follows a simple and easy way to classify a given data set through a certain number of
clusters some clusters.
Fixed a priori.
The main idea is to define key centers, one for each cluster.
These centroid should be placed in a smart way because of different location causes different results,
so the better choice is to place them.
As far away as possible from each other.
And the next step is to take each point belonging to a given dataset and associate it to the nearest
centroid.
When no point is pending, the first step is completed and an early group edge is done.
And at this point, we'll need to recalculate K New Centuries as Barry centers of the clusters resulting
from the previous step.
And after we have these new centroid, a new binding has to be done between the same data set points
and the nearest new centroid.
So a loop has been generated as a result of this loop.
We may notice that the case androids change your location step by step until no more changes can be
done.
So, in other words, Centroid do not move anymore.
And then finally, this algorithm aims at minimizing an objective function in this case, a squared
error of function.
So you see, K means is a simple algorithm that has been adapted to many problem domains.
As we're going to see, it's a good candidate for extension to work with fuzzy feature vectors.
McKay means procedure can be viewed as a greedy algorithm for partitioning the end samples into clusters
so as to minimize this some of the squared distances to the cluster centres.
And it does have some weaknesses.
The way to initialize the means was not specified.
One popular way to start is to randomly choose Kay of the samples.
It can happen that a set of samples closest to MRI is empty so that I cannot be updated.
So this is a problem which needs to be handled during the implementation, but it's generally ignored.
The results depend on the value of K, and there's no optimal way to describe a best K.
Now, this last problem, Matt, particularly troublesome since we often have no way of knowing how
many clusters exist.
So in the example shown here, the same algorithm applied to the same data produces the following three
means clustering.
So does that mean it's better or worse than the two means clustering?
Well, unfortunately, there is no general theoretical solution to find the optimal number of clusters
for any given dataset.
A simple approach is to compare the results of multiple runs with different classes and then choose
the best one according to a given criteria.
But we do need to be careful because increasing can result in smaller error function values by definition.
It also increases the risk of overfishing.
So the next one.
Is Fuzzy K means clustering.
And fuzzy clustering, each point has a probability of belonging to each cluster rather than completely
belonging to just one cluster.
This is the case in traditional K means.
Fuzzy came in specifically try to deal with the problem where points are somewhat in-between centers
or otherwise ambiguous by replacing distance with probability, which of course could be some function
of distance, such as having probability relative to the inverse of the distance.
Fuzzy K means use a weighted centroid based on those probabilities.
So processes of initialization, iteration and termination are the same as the ones used in K means.
The resulting clusters are best analyzed is probabilistic distributions rather than a hard assignment
of labels.
Once you realize, oh, that k- means is a special case of fuzzy K means when the probability function
used is simply one, if the data point is closest to a century and zero otherwise.
So let's have a look at the fuzzy Cayman's algorithm, looks like this.
Assume a fixed number of clusters, K.
Initialization randomly initialize the K means.
Associated with the clusters and then compute the probability that each data point.
Is a member of a given cluster iteration, recalculate the centroid of the cluster as the weighted centroid,
given the probabilities of membership of all data points termination.
Iterate until convergence or until the user specified number of iterations has been reached.
The duration may be trapped at some local maximum or minimum.
For better understanding, we may consider this simple, mono dimensional example, given a certain
data set.
Suppose we represented as distributed on an axis.
Now, looking at the picture, we may identify two clusters in proximity of the two dead concentrations.
It will refer to them using a and B and the first approach shown in this tutorial, the Carmine's algorithm.
We associated each data point to a specific centroid, and therefore this membership function looks
like this.
In the fuzzy Cayman's approach.
Instead, the same given data point does not belong to exclusively well-defined cluster.
But he can be placed in a in between somewhere.
So in this case, the membership function follows a smoother line to indicate that every data point
may belong to several clusters with different extent of membership.
So in this figure.
The data point shown as a red marked spot belongs more to the B cluster rather than the V cluster.
The value of point two of em indicates the degree of membership to a for such data point.
And the next one is hierarchical clustering algorithms.
Given a set of end items to be clustered and and end times and distance or similarity matrix.
The basic process of hierarchical clustering is this.
Start by signing each item to a cluster so that if you have any items you now have and clusters, each
containing just one item.
And let the distances similarities between the clusters.
The same as the distance similarities between the items that they contain.
Find the closest or most similar pair of clusters and merge them into a single cluster, so now you
have one cluster less.
Compute distances, similarities between the new cluster and each of the old clusters.
Then repeat steps two and three until all items are clustered into a single cluster of size in.
Next one is clustering as a mixture of Gaussians.
Now, there's another way to deal with clustering problems.
That's a model based approach, which consists in using certain models for clusters and attempting to
optimize the fit between the data and the model.
In practice, each cluster can be mathematically represented by a parametric distribution like a Gaussian.
Entire data set is therefore modelled by a mixture of these distributions.
So a mixture model with high likelihood tends to have these traits.
Component distributions have high peaks.
The mixture model covers the data well.
And the main advantages of model based clustering, well-studied statistical inference techniques are
available.
Flexibility in choosing the component distribution.
Obtain a density estimation for each cluster.
A soft classification is also available.
So the last one.
Is a mixture of Gaussians.
The most widely used clustering method of this kind is based on learning a mixture of Gaussians.
A mixture model is a mixture of component distributions that collectively make a mixture distribution
f x.
The Alpha K represents the contribution of the K component in constructing f x.
In practice, parametric distribution, for example, Caucasians.
Are often used since a lot of work has been done to understand the behavior.
So if you understand it's f k x for a gauzy and well, you get what is known as a gauzy and mixture
models or GM.
Now, I do want to let you know about one more thing here.
The EM algorithm.
Expectation maximization.
Now this assumes that your data is composed of multiple multivariate normal distributions.
Note, please.
This is a very strong assumption, especially when you fix a number of clusters.
To put it another way, E.M. is an algorithm for maximizing a likelihood function when some of the variables
in your model are unobserved.
That is when you have latent variables.
So you might fairly ask if we're just trying to maximize a function.
Why don't we just use the existing machinery for maximizing a function?
Well, my friends.
If you try to maximize this by taking derivatives and setting them to zero, you find that in many cases,
the first order conditions don't have a solution.
It becomes a problem of the chicken and the egg in that in order to solve for your model parameters,
you need to know the distribution of your unobserved data.
But of course, the distribution of your unobserved data is a function of your model parameters.
Expectation maximization tries to get around this by iteratively getting a distribution for the unobserved
data, then estimating the model parameters by maximizing something that is a lower bound on the actual
likelihood function and repeating until convergence.
All right, very cool.
So what problems associated with clustering are we going to be facing?
I'll tell you, there's going to be a number of problems of clustering and detail a few.
Dealing with large numbers of dimensions and large numbers of data items can be problematic just because
of time complexity.
The effectiveness of the method depends on the definition of distance for distance based clustering,
obviously, if an obvious distance measure doesn't exist, we must define it, which is not always easy,
especially in multidimensional spaces.
The result of the clustering algorithm that in many cases can actually be arbitrary is ill can be interpreted
in different ways.
All right, so what are the possible applications of clustering algorithms then?
Clustering algorithms can be applied in many fields.
For instance, marketing finding groups of customers with similar behavior, given a large database
of customer data containing their properties and pass buying records.
Biology.
Classification of plants and animals given their features.
Insurance identifying groups of motor insurance policyholders with a high average claim cost.
Identifying frauds.
Earthquake studies, clustering, observed earthquake epicenters to identify danger zones.
Worldwide Web document classification clustering weblog data to discover groups of similar access patterns.
All right, so for now, that's it.
To recap in this lesson, we talked about the clustering algorithms and unsupervised learning.
So I want to see in the next session, because we've got a lot more to do until we catch up.
Have a nice day.