K-medoids 파이썬 - k-medoids paisseon

This package is a wrapper around the fast Rust k-medoids package, implementing the FasterPAM and FastPAM algorithms along with the baseline k-means-style and PAM algorithms. Furthermore, the (Medoid) Silhouette can be optimized by the FasterMSC, FastMSC, PAMMEDSIL and PAMSIL algorithms.

All algorithms expect a distance matrix and the number of clusters as input. They hence can be used with arbitrary dissimilarity functions.

If you use this code in scientific work, please cite the papers in the References. Thank you.

Installation

Example

import kmedoids c = kmedoids.fasterpam(distmatrix, 5) print("Loss is:", c.loss)

Implemented Algorithms

• FasterPAM (Schubert and Rousseeuw, 2020, 2021)

• FastPAM1 (Schubert and Rousseeuw, 2019, 2021)

• PAM (Kaufman and Rousseeuw, 1987) with BUILD and SWAP

• Alternating (k-means-style approach)

• BUILD (Kaufman and Rousseeuw, 1987)

• Silhouette (Kaufman and Rousseeuw, 1987)

• FasterMSC (Lenssen and Schubert, 2022)

• FastMSC (Lenssen and Schubert, 2022)

• PAMSIL (Van der Laan and Pollard, 2003)

• PAMMEDSIL (Van der Laan and Pollard, 2003)

• Medoid Silhouette (Van der Laan and Pollard, 2003)

Note that the k-means style “alternating” algorithm yields rather poor result quality (see Schubert and Rousseeuw 2021 for an example and explanation).

FasterPAM

FasterPAM k-medoids clustering

This is an accelerated version of PAM clustering, that eagerly performs any swap found, and contains the O(k) improvement to find the best swaps faster.

References:

Erich Schubert, Peter J. Rousseeuw

Fast and Eager k-Medoids Clustering:

O(k) Runtime Improvement of the PAM, CLARA, and CLARANS Algorithms

Information Systems (101), 2021, 101804

Erich Schubert, Peter J. Rousseeuw:

Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms

In: 12th International Conference on Similarity Search and Applications (SISAP 2019), 171-187.

• diss (ndarray) – square numpy array of dissimilarities

• medoids (int or ndarray) – number of clusters to find or existing medoids

• max_iter (int) – maximum number of iterations

• init (str, "random", "first" or "build") – initialization method

• random_state (int, RandomState instance or None) – random seed (also used for shuffling the processing order)

• n_cpu (int) – number of threads to use (-1: automatic)

k-medoids clustering result

KMedoidsResult

FastPAM1

FastPAM1 k-medoids clustering

This is an accelerated version of PAM clustering, that performs the same swaps as the original PAM (given the same starting conditions), but finds the best swap O(k) times faster.

References:

Erich Schubert, Peter J. Rousseeuw

Fast and Eager k-Medoids Clustering:

O(k) Runtime Improvement of the PAM, CLARA, and CLARANS Algorithms

Information Systems (101), 2021, 101804

Erich Schubert, Peter J. Rousseeuw:

Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms

In: 12th International Conference on Similarity Search and Applications (SISAP 2019), 171-187.

• diss (ndarray) – square numpy array of dissimilarities

• medoids (int or ndarray) – number of clusters to find or existing medoids

• max_iter (int) – maximum number of iterations

• init (str, "random", "first" or "build") – initialization method

• random_state (int, RandomState instance or None) – random seed if no medoids are given

k-medoids clustering result

KMedoidsResult

PAM

PAM k-medoids clustering

This is an implementation of the original PAM (Partitioning Around Medoids) clustering algorithm. For improved versions, see the fastpam and fasterpam methods.

References:

Leonard Kaufman, Peter J. Rousseeuw:

Clustering by means of medoids.

In: Dodge Y (ed) Statistical Data Analysis Based on the L 1 Norm and Related Methods, pp 405–416, 1987

Leonard Kaufman, Peter J. Rousseeuw:

Finding Groups in Data: An Introduction to Cluster Analysis.

• diss (ndarray) – square numpy array of dissimilarities

• medoids (int or ndarray) – number of clusters to find or existing medoids

• max_iter (int) – maximum number of iterations

• init (str, "random", "first" or "build") – initialization method

• random_state (int, RandomState instance or None) – random seed if no medoids are given

k-medoids clustering result

KMedoidsResult

Alternating k-medoids (k-means style)

Alternating k-medoids clustering (k-means-style algorithm)

Note: this yields substantially worse results than PAM algorithms on difficult data sets.

• diss (ndarray) – square numpy array of dissimilarities

• medoids (int or ndarray) – number of clusters to find or existing medoids

• max_iter (int) – maximum number of iterations

• init (str, "random", "first" or "build") – initialization method

• random_state (int, RandomState instance or None) – random seed if no medoids are given

k-medoids clustering result

KMedoidsResult

PAM BUILD

PAM k-medoids clustering – BUILD only

This is an implementation of the original PAM (Partitioning Around Medoids) clustering algorithm. For improved versions, see the fastpam and fasterpam methods.

References:

Leonard Kaufman, Peter J. Rousseeuw:

Clustering by means of medoids.

In: Dodge Y (ed) Statistical Data Analysis Based on the L 1 Norm and Related Methods, 405-416, 1987

Leonard Kaufman, Peter J. Rousseeuw:

Finding Groups in Data: An Introduction to Cluster Analysis.

• diss (ndarray) – square numpy array of dissimilarities

• k (int) – number of clusters to find

k-medoids clustering result

KMedoidsResult

FasterMSC

FasterMSC clustering

This is an accelerated version of PAMMEDSIL clustering, that eagerly performs any swap found, and contains the O(k^2) improvement to find the best swaps faster.

References:

Lars Lenssen, Erich Schubert:

Clustering by Direct Optimization of the Medoid Silhouette

In: 15th International Conference on Similarity Search and Applications (SISAP 2022).

• diss (ndarray) – square numpy array of dissimilarities

• medoids (int or ndarray) – number of clusters to find or existing medoids

• max_iter (int) – maximum number of iterations

• init (str, "random", "first" or "build") – initialization method

• random_state (int, RandomState instance or None) – random seed if no medoids are given

k-medoids clustering result

KMedoidsResult

FastMSC

FastMSC clustering

This is an accelerated version of PAMMEDSIL clustering, that performs the same swaps as the original PAMMEDSIL (given the same starting conditions), but finds the best swap O(k^2) times faster.

References:

Lars Lenssen, Erich Schubert:

Clustering by Direct Optimization of the Medoid Silhouette

In: 15th International Conference on Similarity Search and Applications (SISAP 2022).

• diss (ndarray) – square numpy array of dissimilarities

• medoids (int or ndarray) – number of clusters to find or existing medoids

• max_iter (int) – maximum number of iterations

• init (str, "random", "first" or "build") – initialization method

• random_state (int, RandomState instance or None) – random seed if no medoids are given

k-medoids clustering result

KMedoidsResult

PAMSIL

PAMSIL k-medoids clustering

This is an implementation of the original PAMSIL.

References:

Mark Van der Laan, Katherine Pollard, Jennifer Bryan:

A new partitioning around medoids algorithm.

In: Journal of Statistical Computation and Simulation, pp 575-584, 2003

• diss (ndarray) – square numpy array of dissimilarities

• medoids (int or ndarray) – number of clusters to find or existing medoids

• max_iter (int) – maximum number of iterations

• init (str, "random", "first" or "build") – initialization method

• random_state (int, RandomState instance or None) – random seed if no medoids are given

k-medoids clustering result

KMedoidsResult

PAMMEDSIL

PAMMEDSIL clustering

This is an implementation of the original PAMMEDSIL clustering algorithm. For improved versions, see the fastmsc and fastermsc methods.

References:

Mark Van der Laan, Katherine Pollard, Jennifer Bryan:

A new partitioning around medoids algorithm.

In: Journal of Statistical Computation and Simulation, pp 575-584, 2003

• diss (ndarray) – square numpy array of dissimilarities

• medoids (int or ndarray) – number of clusters to find or existing medoids

• max_iter (int) – maximum number of iterations

• init (str, "random", "first" or "build") – initialization method

• random_state (int, RandomState instance or None) – random seed if no medoids are given

k-medoids clustering result

KMedoidsResult

Silhouette

Silhouette index for cluster evaluation.

The Silhouette, proposed by Peter Rousseeuw in 1987, is a popular internal evaluation measure for clusterings. Although it is defined on arbitary metrics, it is most appropriate for evaluating “spherical” clusters, as it expects objects to be closer to all members of its own cluster than to members of other clusters.

References:

Peter J. Rousseeuw:

Silhouettes: A graphical aid to the interpretation and validation of cluster analysis

Journal of Computational and Applied Mathematics, Volume 20, 1987

• diss (ndarray) – square numpy array of dissimilarities

• labels (ndarray of int) – cluster labels (use 0 to k-1, no negative values allowed)

• samples (boolean) – whether to return individual samples or not

• n_cpu (int) – number of threads to use (-1: automatic)

tuple containing the average silhouette and the individual samples

(float, ndarray)

Medoid Silhouette

Medoid Silhouette index for cluster evaluation.

The Medoid Silhouette is an approximation to the Silhouette index, that uses the distance to the cluster medoids instead of the average distance to the other cluster members. If every point is assigned to the nearest medoid, the Medoid Silhouette of a point reduces to 1-a/b where a is the distance to the nearest, and b the distance to the second nearest medoid. If b is 0, the Medoid Silhouette is 1.

This function assumes you already have a distance matrix. It is not necessary to compute a distance matrix to evaluate the medoid silhouette – only the distances between points and medoids are necessary. If you do not have a distance matrix, simply compute the medoid Silhouette directly, by computing (1) the N x k distance matrix to the medoids, (2) finding the two smallest values for each data point, and (3) computing the average of 1-a/b on these (with 0/0 as 0). This can be implemented in a few lines with numpy easily.

• diss (ndarray) – square numpy array of dissimilarities

• meds (ndarray of int) – medoid indexes (k distinct values in 0 to n-1)

• samples (boolean) – whether to return individual samples or not

tuple containing the average Medoid Silhouette and the individual samples

(float, ndarray)

k-Medoids result object

K-medoids clustering result

• loss (float) – Loss of this clustering (sum of deviations)

• labels (ndarray) – Cluster assignment

• medoids (ndarray) – Chosen medoid indexes

• n_iter (int) – Number of iterations

• n_swap (int) – Number of swaps performed

sklearn-compatible API

K-Medoids Clustering using PAM, FasterPAM, and FasterMSC (sklearn-compatible API).

References:

Erich Schubert and Lars Lenssen:

Fast k-medoids Clustering in Rust and Python

Journal of Open Source Software 7(75), 4183

Erich Schubert, Peter J. Rousseeuw:

Fast and Eager k-Medoids Clustering

O(k) Runtime Improvement of the PAM, CLARA, and CLARANS Algorithms

Information Systems (101), 2021, 101804

Erich Schubert, Peter J. Rousseeuw:

Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms

In: 12th International Conference on Similarity Search and Applications (SISAP 2019), 171-187.

Lars Lenssen, Erich Schubert:

Clustering by Direct Optimization of the Medoid Silhouette

In: 15th International Conference on Similarity Search and Applications (SISAP 2022).

Leonard Kaufman, Peter J. Rousseeuw:

Clustering by means of medoids.

In: Dodge Y (ed) Statistical Data Analysis Based on the L 1 Norm and Related Methods, 405-416, 1987

Leonard Kaufman, Peter J. Rousseeuw:

Finding Groups in Data: An Introduction to Cluster Analysis.

Mark Van der Laan, Katherine Pollard, Jennifer Bryan:

A new partitioning around medoids algorithm.

In: Journal of Statistical Computation and Simulation, pp 575-584, 2003

• n_clusters (int) – The number of clusters to form

• metric (string, default: 'precomputed') – It is recommended to use ‘precomputed’, in particular when experimenting with different n_clusters. If you have sklearn installed, you may pass any metric supported by sklearn.metrics.pairwise_distances.

• metric_params (dict, default=None) – Additional keyword arguments for the metric function.

• method (string, "fasterpam" (default), "fastpam1", "pam", "alternate", "fastermsc", "fastmsc", "pamsil" or "pammedsil") – Which algorithm to use

• init (string, "random" (default), "first" or "build") – initialization method

• max_iter (int) – Specify the maximum number of iterations when fitting

• random_state (int, RandomState instance or None) – random seed if no medoids are given

• cluster_centers_ – None for ‘precomputed’

• medoid_indices_ – The indices of the medoid rows in X

• labels_ – Labels of each point

• inertia_ – Sum of distances of samples to their closest cluster center

Fit K-Medoids to the provided data.

• X ({array-like, sparse matrix}, shape = (n_samples, n_samples)) – Dataset to cluster

• y – ignored

self

Predict the closest cluster for each sample in X.

• X (array-like of shape (n_samples, n_features)) – Input data

• y (Ignored) – Not used, present for API consistency by convention

Cluster labels

ndarray of shape (n_samples,)

Fit to data, then transform it.

Fits transformer to X and y with optional parameters fit_params and returns a transformed version of X.

Input samples.

Target values (None for unsupervised transformations).

Additional fit parameters.

Transformed array.

Get parameters for this estimator.

If True, will return the parameters for this estimator and contained subobjects that are estimators.

Parameter names mapped to their values.

Predict the closest cluster for each sample in X.

X ({array-like, sparse matrix}, shape = (n_samples, n_samples)) – New data to predict

Index of the cluster each sample belongs to

array, shape = (n_query,)

Set the parameters of this estimator.

The method works on simple estimators as well as on nested objects (such as Pipeline). The latter have parameters of the form <component>__<parameter> so that it’s possible to update each component of a nested object.

Estimator parameters.

Estimator instance.

Transforms X to cluster-distance space.

X ({array-like}, shape (n_query, n_features), or (n_query, n_indexed) if metric == 'precomputed') – Data to transform

X transformed in the new space of distances to cluster centers

{array-like}, shape=(n_query, n_clusters)

References

This software has been published in the Journal of Open-Source Software:

Erich Schubert and Lars Lenssen:

Fast k-medoids Clustering in Rust and Python

Journal of Open Source Software 7(75), 4183

For further details on the implemented algorithm FasterPAM, see:

Erich Schubert, Peter J. Rousseeuw

Fast and Eager k-Medoids Clustering:

O(k) Runtime Improvement of the PAM, CLARA, and CLARANS Algorithms

Information Systems (101), 2021, 101804

an earlier (slower, and now obsolete) version was published as:

Erich Schubert, Peter J. Rousseeuw:

Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms

In: 12th International Conference on Similarity Search and Applications (SISAP 2019), 171-187.

For further details on medoid Silhouette clustering with FasterMSC, see:

Lars Lenssen, Erich Schubert:

Clustering by Direct Optimization of the Medoid Silhouette

In: 15th International Conference on Similarity Search and Applications (SISAP 2022).

This is a port of the original Java code from ELKI to Rust. The Rust version is then wrapped for use with Python.

If you use this code in scientific work, please cite above papers. Thank you.

License: GPL-3 or later

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <//www.gnu.org/licenses/>.