← Back to branch summary

~paparazzi-uav/paparazzi/v5.0-manual

« back to all changes in this revision

Viewing changes to sw/ext/opencv_bebop/opencv/doc/py_tutorials/py_ml/py_kmeans/py_kmeans_understanding/py_kmeans_understanding.markdown

  • Committer: Paparazzi buildbot
  • Date: 2016-05-18 15:00:29 UTC
  • Revision ID: felix.ruess+docbot@gmail.com-20160518150029-e8lgzi5kvb4p7un9
Manual import commit 4b8bbb730080dac23cf816b98908dacfabe2a8ec from v5.0 branch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
sw/ext/opencv_bebop/opencv/doc/py_tutorials/py_ml/py_kmeans/py_kmeans_understanding/py_kmeans_understanding.markdown
 
1
Understanding K-Means Clustering {#tutorial_py_kmeans_understanding}
 
2
================================
 
3
 
 
4
Goal
 
5
----
 
6
 
 
7
In this chapter, we will understand the concepts of K-Means Clustering, how it works etc.
 
8
 
 
9
Theory
 
10
------
 
11
 
 
12
We will deal this with an example which is commonly used.
 
13
 
 
14
### T-shirt size problem
 
15
 
 
16
Consider a company, which is going to release a new model of T-shirt to market. Obviously they will
 
17
have to manufacture models in different sizes to satisfy people of all sizes. So the company make a
 
18
data of people's height and weight, and plot them on to a graph, as below:
 
19
 
 
20
![image](images/tshirt.jpg)
 
21
 
 
22
Company can't create t-shirts with all the sizes. Instead, they divide people to Small, Medium and
 
23
Large, and manufacture only these 3 models which will fit into all the people. This grouping of
 
24
people into three groups can be done by k-means clustering, and algorithm provides us best 3 sizes,
 
25
which will satisfy all the people. And if it doesn't, company can divide people to more groups, may
 
26
be five, and so on. Check image below :
 
27
 
 
28
![image](images/tshirt_grouped.jpg)
 
29
 
 
30
### How does it work ?
 
31
 
 
32
This algorithm is an iterative process. We will explain it step-by-step with the help of images.
 
33
 
 
34
Consider a set of data as below ( You can consider it as t-shirt problem). We need to cluster this
 
35
data into two groups.
 
36
 
 
37
![image](images/testdata.jpg)
 
38
 
 
39
**Step : 1** - Algorithm randomly chooses two centroids, \f$C1\f$ and \f$C2\f$ (sometimes, any two data are
 
40
taken as the centroids).
 
41
 
 
42
**Step : 2** - It calculates the distance from each point to both centroids. If a test data is more
 
43
closer to \f$C1\f$, then that data is labelled with '0'. If it is closer to \f$C2\f$, then labelled as '1'
 
44
(If more centroids are there, labelled as '2','3' etc).
 
45
 
 
46
In our case, we will color all '0' labelled with red, and '1' labelled with blue. So we get
 
47
following image after above operations.
 
48
 
 
49
![image](images/initial_labelling.jpg)
 
50
 
 
51
**Step : 3** - Next we calculate the average of all blue points and red points separately and that
 
52
will be our new centroids. That is \f$C1\f$ and \f$C2\f$ shift to newly calculated centroids. (Remember, the
 
53
images shown are not true values and not to true scale, it is just for demonstration only).
 
54
 
 
55
And again, perform step 2 with new centroids and label data to '0' and '1'.
 
56
 
 
57
So we get result as below :
 
58
 
 
59
![image](images/update_centroid.jpg)
 
60
 
 
61
Now **Step - 2** and **Step - 3** are iterated until both centroids are converged to fixed points.
 
62
*(Or it may be stopped depending on the criteria we provide, like maximum number of iterations, or a
 
63
specific accuracy is reached etc.)* **These points are such that sum of distances between test data
 
64
and their corresponding centroids are minimum**. Or simply, sum of distances between
 
65
\f$C1 \leftrightarrow Red\_Points\f$ and \f$C2 \leftrightarrow Blue\_Points\f$ is minimum.
 
66
 
 
67
\f[minimize \;\bigg[J = \sum_{All\: Red\_Points}distance(C1,Red\_Point) + \sum_{All\: Blue\_Points}distance(C2,Blue\_Point)\bigg]\f]
 
68
 
 
69
Final result almost looks like below :
 
70
 
 
71
![image](images/final_clusters.jpg)
 
72
 
 
73
So this is just an intuitive understanding of K-Means Clustering. For more details and mathematical
 
74
explanation, please read any standard machine learning textbooks or check links in additional
 
75
resources. It is just a top layer of K-Means clustering. There are a lot of modifications to this
 
76
algorithm like, how to choose the initial centroids, how to speed up the iteration process etc.
 
77
 
 
78
Additional Resources
 
79
--------------------
 
80
 
 
81
-#  [Machine Learning Course](https://www.coursera.org/course/ml), Video lectures by Prof. Andrew Ng
 
82
    (Some of the images are taken from this)
 
83
 
 
84
Exercises
 
85
---------