source: orange/Orange/doc/widgets/Unsupervised/k-MeansClustering.htm @ 9671:a7b056375472

Revision 9671:a7b056375472, 5.1 KB checked in by anze <anze.staric@…>, 2 years ago (diff)

Moved orange to Orange (part 2)

Line 
1<html>
2<head>
3<title>K-Means Clustering</title>
4<link rel=stylesheet href="../../../style.css" type="text/css" media=screen>
5<link rel=stylesheet href="../../../style-print.css" type="text/css" media=print></link>
6</head>
7
8<body>
9
10<h1>K-Means Clustering</h1>
11
12<img class="screenshot" src="../icons/K-MeansClustering.png">
13<p>Groups the examples using the K-Means clustering algorithm.</p>
14
15<h2>Channels</h2>
16
17<h3>Inputs</h3>
18
19<DL class=attributes>
20<DT>Examples</DT>
21<DD>A list of examples</DD>
22</dl>
23
24<h3>Outputs</h3>
25<DL class="attributes">
26<DT>Examples</DT>
27<DD>A list of examples with the cluster index as the class attribute</DD>
28</dl>
29
30<h2>Description</h2>
31
32<p>The widget applies the K-means clustering algorithm to the data from the input and outputs a new data set in which the cluster index is used for the class attribute. The original class attribute, if it existed, is moved to meta attributes. The basic information on the clustering results is also shown in the widget.</p>
33
34<img class="leftscreenshot" src="K-MeansClustering.png" border=0>
35
36<P>Clustering has two parameters that can be set by the user, the number of clusters and the type of distance metrics, <span class="option">Euclidean distance</span> or <span class="option">Manhattan</span>. Any changes must be confirmed by pushing <span class="option">Apply</span>.</P>
37
38<p>The table on the right hand side shows the results of clustering. For each cluster it gives the number of examples, its fitness and BIC.</p>
39
40<p>Fitness measures how well the cluster is defined. Let <em>d<sub>i,C</sub></em> be the average distance between point <em>i</em> and the points in cluster <em>C</em>. Now, let <em>a<sub>i</sub></em> equal <em>d<sub>i,C'</sub></em>, where <em>C'</em> is the cluster <em>i</em> belongs to, and let <em>b<sub>i</sub></em>=min <em>d<sub>i,C</sub></em> over all other clusters <em>C</em>. Fitness is then defined as the average silhouette of the cluster <em>C</em>, that is avg( (<em>b<sub>i</sub></em>-<em>a<sub>i</sub></em>)/max(<em>b<sub>i</sub></em>, <em>a<sub>i</sub></em>) ).</p>
41
42<p>To make it simple, fitness close to 1 signifies a well-defined cluster.</p>
43
44<P>BIC is short for Bayesian Information Criteria and is computed as ln <em>L</em>-<em>k</em>(<em>d</em>+1)/2 ln <em>n</em>, where <em>k</em> is the number of clusters, <em>d</em> is dimension of data (the number of attributes) and <em>n</em> is the number of examples (data instances). <em>L</em> is the likelihood of the model, assuming the spherical Gaussian distributions around the centroid(s) of the cluster(s).</P>
45
46
47<h2>Examples</h2>
48
49<P>We are going to explore the widget with the following schema.</P>
50
51<img class="screenshot" src="K-MeansClustering-Schema.png"/>
52
53<p>The beginning is nothing special: we load the iris data, divide it into three clusters, show it in a table, where we can observe which example went into which cluster. The interesting part are the Scatter plot and Select data.</p>
54
55<p>Since K-means added the cluster index as the class attribute, the scatter plot will color the points according to the clusters they are in. Indeed, what we get looks like this.</p>
56<img class="screenshot" src="K-MeansClustering-Scatterplot.png" />
57
58<p>The thing we might be really interested in is how well the clusters induced by the (unsupervised) clustering algorithm match the actual classes appearing in the data. We thus take the Select data widget in which we can select individual classes and get the corresponding points in the scatter plot marked. The match is perfect setosa, and pretty good for the other two classes.</p>
59
60<img class="screenshot" src="K-MeansClustering-Example.png" />
61
62<p>You may have noticed that we left the <span class="option">Remove unused values/attributes</span> and <span class="option">Remove unused classes</span> in Select Data unchecked. This is important: if the widget modifies the attributes, it outputs a list of modified examples and the scatter plot cannot compare them to the original examples.</p>
63
64<p>Another, perhaps simpler way to test the match between clusters and the original classes is to use the widget <a href="../Visualize/Distributions.htm">Distributions</a>. The only (minor) problem here is that this widget only visualizes the normal attributes and not the meta attributes. We solve this by using <a href="../Data/SelectAttributes.htm">Select Attributes</a> with which we move the original class to normal attributes.</p>
65
66<img class="screenshot" src="K-MeansClustering-Schema.png"/>
67
68<p>The match is perfect for setosa: all instances of setosa are in the first cluster (blue). 47 versicolors are in the third cluster (green), while three ended up in the second. For virginicae, 49 are in the second cluster and one in the third.</p>
69
70<img class="screenshot" src="K-MeansClustering-Example2.png" />
71
72<p>To observe the possibly more interesting reverse relation, we need to rearrange the attributes in the Select Attributes: we reinstate the original class Iris as the class and put the cluster index among the attributes.</p>
73
74<img class="screenshot" src="K-MeansClustering-Example2a.png" />
75
76<p>The first cluster is exclusively setosae, the second has mostly virginicae and the third has mostly versicolors.</p>
77
78</body>
79</html>
Note: See TracBrowser for help on using the repository browser.