
Contents
Kmeans

If your experience problems
with the applet start (it is possible because changes
starting with Java 7 Update 51),
you can download the applet here (kmeans.zip), save it on disk, unzip it
and start it by clicking on batfile.
Please cite as: E.M. Mirkes, Kmeans and Kmedoids applet. University of Leicester,
2011
The most common algorithm uses an iterative refinement technique. Due to its ubiquity it is often called the kmeans algorithm; it is also referred to as Lloyd's algorithm, particularly in the computer science community.
Given an initial set of k means (centroids) m_{1}^{(1)},…,m_{ k}^{(1)} (see below), the algorithm proceeds by alternating between two steps:
Assignment step : Assign each observation to the cluster with the closest mean
(i.e. partition the observations according to the Voronoi
diagram generated by the means).
Update step : Calculate the new means to be the centroid of the observations
in the cluster.
The algorithm is deemed to have converged when the assignments no longer change.
Kmeans is a classical partitioning technique of clustering that clusters the data set of n objects into k clusters with k known a priori. A useful tool for determining k is the silhouette.
The kmedoids algorithm is a clustering algorithm related to the kmeans algorithm and the medoidshift algorithm. Both the kmeans and kmedoids algorithms are partitional (breaking the dataset up into groups) and both attempt to minimize squared error, the distance between points labeled to be in a cluster and a point designated as the center of that cluster. In contrast to the kmeans algorithm, kmedoids chooses datapoints as centers ( medoids or exemplars).
Kmedoids is also a partitioning technique of clustering that clusters the data set of n objects into k clusters with k known a priori. A useful tool for determining k is the silhouette.
It could be more robust to noise and outliers as compared to kmeans because it minimizes a sum of general pairwise dissimilarities instead of a sum of squared Euclidean distances. The possible choice of the dissimilarity function is very rich but in our applet we used the squared Euclidean distance.
A medoid of a finite dataset is a data point from this set, whose average dissimilarity to all the data points is minimal i.e. it is the most centrally located point in the set.
The most common realisation of kmedoid clustering is the Partitioning Around Medoids (PAM) algorithm and is as follows:
Repeat
alternating steps 2 and 3 until there is no change in the assignments.
The applet contains three menu panels (top left), University of Leicester label (top right), work desk (center) and the label of the Attribution 3.0 Creative Commons publication license (bottom).
To wisit the website of the University of Leicester click on the University of Leicester logo.
To read the Creative Commons publication license click on the bottom license panel.

The
first menu panel allows you to create and edit the data set. Every data point
is displayed as a small circle on the work desk.
The first part of the Data set panel contains one big coloured rectangle and a palette built from six small differently coloured rectangles. To select one of the six colors click on a small rectangle. The big coloured rectangle displays the currently selected color.
The third part of the Data set panel contains six buttons. The first three buttons change the type of cursor brush.
The button "One point" switches the brush to add single points. Every mouse click on the work desk will add a point to the data set.
The button "Scatter" allows you to add several points by one mouse click. You can choose the number of added points in the "Number of points" spinner in the middle part of the menu panel. Points are scattered randomly in a circle whose radius is determined by the slider "Caliber" in the middle part of the menu panel.
The button "Erase" switches the mouse cursor in the eraser. When you click the eraser mouse cursor on the work desk, all points, whose centres are covered by the cursor, are removed from the work desk.
The button "Select" is not used
When you press the "Random" button several points are added on the work desk. The number of points is defined by the "Number of points" spinner. The locations of new points are generated randomly on whole work desk.
The button "Erase all" fully clears the work desk. It removes all kinds of object: data points, centroids, test results, maps and so on.
The second menu panel "Execution", is desined to
initiate centroids and to learn models.
The leftmost part indicates the colour for for next added centroid. The user can not select centroid color.
The next part of the menu panel indicates the number of centroids, which can be added to the work desk.

There are two kinds of centroids: kmeans centroids are fourray stars and kmedoids centroids are nineray stars.
You can add centroids by the "Random centroid" button, or by clicking on a data point. Both centroids (kmeans and kmedoids) are initialised simultaneously at the same data point.
The "Erase centroids" button allows you to remove ALL centroids.
Before you can see the results, you should press the "Learn" button.
After learning you can observe the results. If you want to edit centroids or the data set you should press the button "Unlearn".
The
third menu panel "View learning history" is needed to view the
learning results. In the left top corner of the panel the number of steps is
indicated that was needed to learn both models, and the number of the step
showed in the work desk.

The leftmost button shows the first step. The second button moves to the previous step. The third button starts the slide show with one second delay between steps. It goes always from the first step to the last one. The fourth button moves to the next step. The rightmost button shows the last step.
The right part of menu panel are used to choose what is displayed on the work desk.
Kmeans only  the data set is coloured in accordance with kmeans results. Kmedoids centroids are not displayed.
Kmeans (show kmedoids centroids)  the data set is coloured in accordance with kmeans results. Both groups of centroids are displayed.
Kmedoids only  the data set is coloured in accordance with kmedoids results. Kmeans centroids are not displayed.
Kmedoids (show kmeans centroids)  the data set is coloured in accordance with kmedoids results. Both groups of centroids are displayed.