scikit-learn · znd4 · Jul 31, 2015 · Jul 31, 2015 · Aug 1, 2015 · Aug 2, 2015
diff --git a/.gitignore b/.gitignore
@@ -39,6 +39,7 @@ doc/samples
 *.prof
 .tox/
 .coverage
+.vscode
 
 lfw_preprocessed/
 nips2010_pdf/
@@ -54,6 +55,7 @@ benchmarks/bench_covertype_data/
 *.prefs
 .pydevproject
 .idea
+*.iml
 
 *.c
 *.cpp

diff --git a/doc/modules/classes.rst b/doc/modules/classes.rst
@@ -100,6 +100,7 @@ Classes
    cluster.DBSCAN
    cluster.FeatureAgglomeration
    cluster.KMeans
+   cluster.KMedoids
    cluster.MiniBatchKMeans
    cluster.MeanShift
    cluster.SpectralClustering

diff --git a/doc/modules/clustering.rst b/doc/modules/clustering.rst
@@ -54,6 +54,13 @@ Overview of clustering methods
      - General-purpose, even cluster size, flat geometry, not too many clusters
      - Distances between points
 
+   * - :ref:`K-Medoids <k_medoids>`
+     - number of clusters
+     - Moderate ``n_samples``, medium ``n_clusters``
+     - General-purpose, uneven cluster size, flat geometry, 
+       not too many clusters
+     - Any pairwise distance
+
    * - :ref:`Affinity propagation <affinity_propagation>`
      - damping, sample preference
      - Not scalable with n_samples
@@ -278,6 +285,64 @@ small, as shown in the example and cited reference.
    D. Sculley, *Proceedings of the 19th international conference on World
    wide web* (2010)
 
+.. _k_medoids:
+
+K-Medoids
+=========
+
+:class:`KMedoids` is related to the :class:`KMeans` algorithm. While
+:class:`KMeans` tries to minimize the within cluster sum-of-squares,
+:class:`KMedoids` tries to minimize the sum of distances between each point and
+the medoid of its cluster. The medoid is a data point (unlike the centroid)
+which has least total distance to the other members of its cluster. The use of
+a data point to represent each cluster's center allows the use of any distance
+metric for clustering.
+
+:class:`KMedoids` can be more robust to noise and outliers than :class:`KMeans`
+as it will choose one of the cluster members as the medoid while
+:class:`KMeans` will move the center of the cluster towards the outlier which
+might in turn move other points away from the cluster centre.
+
+:class:`KMedoids` is also different from K-Medians, which is analogous to :class:`KMeans`
+except that the Manhattan Median is used for each cluster center instead of
+the centroid. K-Medians is robust to outliers, but it is limited to the
+Manhattan Distance metric and, similar to :class:`KMeans`, it does not guarantee
+that the center of each cluster will be a member of the original dataset.
+
+The complexity of K-Medoids is :math:`O(N^2 K T)` where :math:`N` is the number
+of samples, :math:`T` is the number of iterations and :math:`K` is the number of
+clusters. This makes it more suitable for smaller datasets in comparison to
+:class:`KMeans` which is :math:`O(N K T)`.
+
+.. topic:: Examples:
+
+ * :ref:`sphx_glr_auto_examples_cluster_plot_kmedoids_digits.py`: Applying K-Medoids on digits
+   with various distance metrics.
+
+
+**Algorithm description:**
+There are several algorithms to compute K-Medoids, though :class:`KMedoids`
+currently only supports Partitioning Around Medoids (PAM). The PAM algorithm
+uses a greedy search, which may fail to find the global optimum. It consists of
+two alternating steps commonly called the
+Assignment and Update steps (BUILD and SWAP in Kaufmann and Rousseeuw, 1987).
+
+PAM works as follows:
+
+* Initialize: Select ``n_clusters`` from the dataset as the medoids using
+  a heuristic, random, or k-medoids++ approach (configurable using the ``init`` parameter).
+* Assignment step: assign each element from the dataset to the closest medoid.
+* Update step: Identify the new medoid of each cluster.
+* Repeat the assignment and update step while the medoids keep changing or
+  maximum number of iterations ``max_iter`` is reached.
+
+.. topic:: References:
+
+ * "Clustering by Means of Medoids'"
+   Kaufman, L. and Rousseeuw, P.J.,
+   Statistical Data Analysis Based on the L1–Norm and Related Methods, edited
+   by Y. Dodge, North-Holland, 405–416. 1987
+
 .. _affinity_propagation:
 
 Affinity Propagation

diff --git a/examples/cluster/plot_cluster_comparison.py b/examples/cluster/plot_cluster_comparison.py
@@ -109,6 +109,10 @@
     # ============
     ms = cluster.MeanShift(bandwidth=bandwidth, bin_seeding=True)
     two_means = cluster.MiniBatchKMeans(n_clusters=params['n_clusters'])
+    kmedoids = cluster.KMedoids(
+        n_clusters=params['n_clusters'],
+        init='k-medoids++',
+        metric='euclidean')
     ward = cluster.AgglomerativeClustering(
         n_clusters=params['n_clusters'], linkage='ward',
         connectivity=connectivity)
@@ -127,6 +131,7 @@
 
     clustering_algorithms = (
         ('MiniBatchKMeans', two_means),
+        ('KMedoids', kmedoids),
         ('AffinityPropagation', affinity_propagation),
         ('MeanShift', ms),
         ('SpectralClustering', spectral),

diff --git a/examples/cluster/plot_kmedoids_digits.py b/examples/cluster/plot_kmedoids_digits.py
@@ -0,0 +1,98 @@
+# -*- coding: utf-8 -*-
+"""
+=============================================================
+A demo of K-Medoids clustering on the handwritten digits data
+=============================================================
+
+In this example we compare different pairwise distance
+metrics for K-Medoids.
+
+"""
+import numpy as np
+import matplotlib.pyplot as plt
+
+from collections import namedtuple
+from sklearn.cluster import KMedoids, KMeans
+from sklearn.datasets import load_digits
+from sklearn.decomposition import PCA
+from sklearn.preprocessing import scale
+
+print(__doc__)
+
+# Authors: Timo Erkkilä <timo.erkkila@gmail.com>
+#          Antti Lehmussola <antti.lehmussola@gmail.com>
+#          Kornel Kiełczewski <kornel.mail@gmail.com>
+# License: BSD 3 clause
+
+np.random.seed(42)
+
+digits = load_digits()
+data = scale(digits.data)
+n_digits = len(np.unique(digits.target))
+
+reduced_data = PCA(n_components=2).fit_transform(data)
+
+# Step size of the mesh. Decrease to increase the quality of the VQ.
+h = .02     # point in the mesh [x_min, m_max]x[y_min, y_max].
+
+# Plot the decision boundary. For that, we will assign a color to each
+x_min, x_max = reduced_data[:, 0].min() - 1, reduced_data[:, 0].max() + 1
+y_min, y_max = reduced_data[:, 1].min() - 1, reduced_data[:, 1].max() + 1
+xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
+
+plt.figure()
+plt.clf()
+
+plt.suptitle("Comparing multiple K-Medoids metrics to K-Means and each other",
+             fontsize=14)
+
+Algorithm = namedtuple('ClusterAlgorithm', ['model', 'description'])
+
+selected_models = [
+    Algorithm(KMedoids(metric='manhattan',
+                       n_clusters=n_digits),
+              'KMedoids (manhattan)'),
+    Algorithm(KMedoids(metric='euclidean',
+                       n_clusters=n_digits),
+              'KMedoids (euclidean)'),
+    Algorithm(KMedoids(metric='cosine',
+                       n_clusters=n_digits),
+              'KMedoids (cosine)'),
+    Algorithm(KMeans(n_clusters=n_digits),
+              'KMeans')
+    ]
+
+plot_rows = int(np.ceil(len(selected_models) / 2.0))
+plot_cols = 2
+
+for i, (model, description) in enumerate(selected_models):
+
+    # Obtain labels for each point in mesh. Use last trained model.
+    model.fit(reduced_data)
+    Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
+
+    # Put the result into a color plot
+    Z = Z.reshape(xx.shape)
+    plt.subplot(plot_cols, plot_rows, i + 1)
+    plt.imshow(Z, interpolation='nearest',
+               extent=(xx.min(), xx.max(), yy.min(), yy.max()),
+               cmap=plt.cm.Paired,
+               aspect='auto', origin='lower')
+
+    plt.plot(reduced_data[:, 0],
+             reduced_data[:, 1],
+             'k.', markersize=2,
+             alpha=0.3,
+             )
+    # Plot the centroids as a white X
+    centroids = model.cluster_centers_
+    plt.scatter(centroids[:, 0], centroids[:, 1],
+                marker='x', s=169, linewidths=3,
+                color='w', zorder=10)
+    plt.title(description)
+    plt.xlim(x_min, x_max)
+    plt.ylim(y_min, y_max)
+    plt.xticks(())
+    plt.yticks(())
+
+plt.show()
diff --git a/sklearn/cluster/__init__.py b/sklearn/cluster/__init__.py
@@ -10,6 +10,7 @@
 from .hierarchical import (ward_tree, AgglomerativeClustering, linkage_tree,
                            FeatureAgglomeration)
 from .k_means_ import k_means, KMeans, MiniBatchKMeans
+from .k_medoids_ import KMedoids
 from .dbscan_ import dbscan, DBSCAN
 from .bicluster import SpectralBiclustering, SpectralCoclustering
 from .birch import Birch
@@ -19,6 +20,7 @@
            'Birch',
            'DBSCAN',
            'KMeans',
+           'KMedoids',
            'FeatureAgglomeration',
            'MeanShift',
            'MiniBatchKMeans',

diff --git a/sklearn/cluster/k_means_.py b/sklearn/cluster/k_means_.py
@@ -837,6 +837,13 @@ class KMeans(BaseEstimator, ClusterMixin, TransformerMixin):
         For large scale learning (say n_samples > 10k) MiniBatchKMeans is
         probably much faster than the default batch implementation.
 
+
+    KMedoids
+        KMedoids tries to minimize the sum of distances between each point and
+        the medoid of its cluster. Unlike in KMeans the medoid is a data point.
+        The use of a data point to represent each cluster's center allows the
+        use of any distance metric for clustering.
+
     Notes
     ------
     The k-means problem is solved using Lloyd's algorithm.
-Original file line number
+Diff line change
@@ Expand Up / @@ -39,6 +39,7 @@ doc/samples @@
     *.prof
     .tox/
     .coverage
+    .vscode
     lfw_preprocessed/
     nips2010_pdf/
@@ Expand All / @@ -54,6 +55,7 @@ benchmarks/bench_covertype_data/ @@
     *.prefs
     .pydevproject
     .idea
+    *.iml
     *.c
     *.cpp
@@ Expand Down @@