Apakah mungkin untuk menentukan fungsi jarak Anda sendiri menggunakan scikit-learn K-Means Clustering?

172

Apakah mungkin untuk menentukan fungsi jarak Anda sendiri menggunakan scikit-learn K-Means Clustering?

BMSC
sumber
37
Perhatikan bahwa k-means dirancang untuk jarak Euclidean . Ini mungkin berhenti konvergen dengan jarak lain, ketika rerata tidak lagi merupakan estimasi terbaik untuk "pusat" klaster.
Memiliki QUIT - Anony-Mousse
2
mengapa k-means hanya berfungsi dengan jarak Euclidean?
Penasaran
9
@ Anony-Mousse Tidak benar untuk mengatakan bahwa k-means hanya dirancang untuk jarak Euclidean. Itu dapat dimodifikasi untuk bekerja dengan metrik jarak valid apa pun yang ditentukan pada ruang observasi. Sebagai contoh, lihat artikel tentang k-medoid .
ely
5
@Curious: mean meminimalkan perbedaan kuadrat (= kuadrat jarak Euclidean). Jika Anda menginginkan fungsi jarak yang berbeda, Anda perlu mengganti mean dengan estimasi pusat yang sesuai. K-medoid adalah algoritma yang demikian, tetapi menemukan medoidnya jauh lebih mahal.
Memiliki QUIT - Anony-Mousse
4
Agak relevan di sini: saat ini ada permintaan tarik terbuka yang mengimplementasikan Kernel-Kernel. Setelah selesai Anda akan dapat menentukan kernel Anda sendiri untuk perhitungan.
jakevdp

Jawaban:

77

Berikut ini adalah kman kecil yang menggunakan salah satu dari jarak 20-aneh di scipy.spatial.distance , atau fungsi pengguna.
Komentar akan diterima (sejauh ini hanya memiliki satu pengguna, tidak cukup); khususnya, apa metrik N, redup, k, Anda?

#!/usr/bin/env python
# kmeans.py using any of the 20-odd metrics in scipy.spatial.distance
# kmeanssample 2 pass, first sample sqrt(N)

from __future__ import division
import random
import numpy as np
from scipy.spatial.distance import cdist  # $scipy/spatial/distance.py
    # http://docs.scipy.org/doc/scipy/reference/spatial.html
from scipy.sparse import issparse  # $scipy/sparse/csr.py

__date__ = "2011-11-17 Nov denis"
    # X sparse, any cdist metric: real app ?
    # centres get dense rapidly, metrics in high dim hit distance whiteout
    # vs unsupervised / semi-supervised svm

#...............................................................................
def kmeans( X, centres, delta=.001, maxiter=10, metric="euclidean", p=2, verbose=1 ):
    """ centres, Xtocentre, distances = kmeans( X, initial centres ... )
    in:
        X N x dim  may be sparse
        centres k x dim: initial centres, e.g. random.sample( X, k )
        delta: relative error, iterate until the average distance to centres
            is within delta of the previous average distance
        maxiter
        metric: any of the 20-odd in scipy.spatial.distance
            "chebyshev" = max, "cityblock" = L1, "minkowski" with p=
            or a function( Xvec, centrevec ), e.g. Lqmetric below
        p: for minkowski metric -- local mod cdist for 0 < p < 1 too
        verbose: 0 silent, 2 prints running distances
    out:
        centres, k x dim
        Xtocentre: each X -> its nearest centre, ints N -> k
        distances, N
    see also: kmeanssample below, class Kmeans below.
    """
    if not issparse(X):
        X = np.asanyarray(X)  # ?
    centres = centres.todense() if issparse(centres) \
        else centres.copy()
    N, dim = X.shape
    k, cdim = centres.shape
    if dim != cdim:
        raise ValueError( "kmeans: X %s and centres %s must have the same number of columns" % (
            X.shape, centres.shape ))
    if verbose:
        print "kmeans: X %s  centres %s  delta=%.2g  maxiter=%d  metric=%s" % (
            X.shape, centres.shape, delta, maxiter, metric)
    allx = np.arange(N)
    prevdist = 0
    for jiter in range( 1, maxiter+1 ):
        D = cdist_sparse( X, centres, metric=metric, p=p )  # |X| x |centres|
        xtoc = D.argmin(axis=1)  # X -> nearest centre
        distances = D[allx,xtoc]
        avdist = distances.mean()  # median ?
        if verbose >= 2:
            print "kmeans: av |X - nearest centre| = %.4g" % avdist
        if (1 - delta) * prevdist <= avdist <= prevdist \
        or jiter == maxiter:
            break
        prevdist = avdist
        for jc in range(k):  # (1 pass in C)
            c = np.where( xtoc == jc )[0]
            if len(c) > 0:
                centres[jc] = X[c].mean( axis=0 )
    if verbose:
        print "kmeans: %d iterations  cluster sizes:" % jiter, np.bincount(xtoc)
    if verbose >= 2:
        r50 = np.zeros(k)
        r90 = np.zeros(k)
        for j in range(k):
            dist = distances[ xtoc == j ]
            if len(dist) > 0:
                r50[j], r90[j] = np.percentile( dist, (50, 90) )
        print "kmeans: cluster 50 % radius", r50.astype(int)
        print "kmeans: cluster 90 % radius", r90.astype(int)
            # scale L1 / dim, L2 / sqrt(dim) ?
    return centres, xtoc, distances

#...............................................................................
def kmeanssample( X, k, nsample=0, **kwargs ):
    """ 2-pass kmeans, fast for large N:
        1) kmeans a random sample of nsample ~ sqrt(N) from X
        2) full kmeans, starting from those centres
    """
        # merge w kmeans ? mttiw
        # v large N: sample N^1/2, N^1/2 of that
        # seed like sklearn ?
    N, dim = X.shape
    if nsample == 0:
        nsample = max( 2*np.sqrt(N), 10*k )
    Xsample = randomsample( X, int(nsample) )
    pass1centres = randomsample( X, int(k) )
    samplecentres = kmeans( Xsample, pass1centres, **kwargs )[0]
    return kmeans( X, samplecentres, **kwargs )

def cdist_sparse( X, Y, **kwargs ):
    """ -> |X| x |Y| cdist array, any cdist metric
        X or Y may be sparse -- best csr
    """
        # todense row at a time, v slow if both v sparse
    sxy = 2*issparse(X) + issparse(Y)
    if sxy == 0:
        return cdist( X, Y, **kwargs )
    d = np.empty( (X.shape[0], Y.shape[0]), np.float64 )
    if sxy == 2:
        for j, x in enumerate(X):
            d[j] = cdist( x.todense(), Y, **kwargs ) [0]
    elif sxy == 1:
        for k, y in enumerate(Y):
            d[:,k] = cdist( X, y.todense(), **kwargs ) [0]
    else:
        for j, x in enumerate(X):
            for k, y in enumerate(Y):
                d[j,k] = cdist( x.todense(), y.todense(), **kwargs ) [0]
    return d

def randomsample( X, n ):
    """ random.sample of the rows of X
        X may be sparse -- best csr
    """
    sampleix = random.sample( xrange( X.shape[0] ), int(n) )
    return X[sampleix]

def nearestcentres( X, centres, metric="euclidean", p=2 ):
    """ each X -> nearest centre, any metric
            euclidean2 (~ withinss) is more sensitive to outliers,
            cityblock (manhattan, L1) less sensitive
    """
    D = cdist( X, centres, metric=metric, p=p )  # |X| x |centres|
    return D.argmin(axis=1)

def Lqmetric( x, y=None, q=.5 ):
    # yes a metric, may increase weight of near matches; see ...
    return (np.abs(x - y) ** q) .mean() if y is not None \
        else (np.abs(x) ** q) .mean()

#...............................................................................
class Kmeans:
    """ km = Kmeans( X, k= or centres=, ... )
        in: either initial centres= for kmeans
            or k= [nsample=] for kmeanssample
        out: km.centres, km.Xtocentre, km.distances
        iterator:
            for jcentre, J in km:
                clustercentre = centres[jcentre]
                J indexes e.g. X[J], classes[J]
    """
    def __init__( self, X, k=0, centres=None, nsample=0, **kwargs ):
        self.X = X
        if centres is None:
            self.centres, self.Xtocentre, self.distances = kmeanssample(
                X, k=k, nsample=nsample, **kwargs )
        else:
            self.centres, self.Xtocentre, self.distances = kmeans(
                X, centres, **kwargs )

    def __iter__(self):
        for jc in range(len(self.centres)):
            yield jc, (self.Xtocentre == jc)

#...............................................................................
if __name__ == "__main__":
    import random
    import sys
    from time import time

    N = 10000
    dim = 10
    ncluster = 10
    kmsample = 100  # 0: random centres, > 0: kmeanssample
    kmdelta = .001
    kmiter = 10
    metric = "cityblock"  # "chebyshev" = max, "cityblock" L1,  Lqmetric
    seed = 1

    exec( "\n".join( sys.argv[1:] ))  # run this.py N= ...
    np.set_printoptions( 1, threshold=200, edgeitems=5, suppress=True )
    np.random.seed(seed)
    random.seed(seed)

    print "N %d  dim %d  ncluster %d  kmsample %d  metric %s" % (
        N, dim, ncluster, kmsample, metric)
    X = np.random.exponential( size=(N,dim) )
        # cf scikits-learn datasets/
    t0 = time()
    if kmsample > 0:
        centres, xtoc, dist = kmeanssample( X, ncluster, nsample=kmsample,
            delta=kmdelta, maxiter=kmiter, metric=metric, verbose=2 )
    else:
        randomcentres = randomsample( X, ncluster )
        centres, xtoc, dist = kmeans( X, randomcentres,
            delta=kmdelta, maxiter=kmiter, metric=metric, verbose=2 )
    print "%.0f msec" % ((time() - t0) * 1000)

    # also ~/py/np/kmeans/test-kmeans.py

Beberapa catatan menambahkan 26mar 2012:

1) untuk jarak cosinus, pertama-tama normalkan semua vektor data ke | X | = 1; kemudian

cosinedistance( X, Y ) = 1 - X . Y = Euclidean distance |X - Y|^2 / 2

cepat. Untuk vektor bit, jaga norma-norma secara terpisah dari vektor alih-alih meluas ke float (meskipun beberapa program mungkin meluas untuk Anda). Untuk vektor jarang, katakan 1% dari N, X. Y harus mengambil waktu O (2% N), ruang O (N); tapi saya tidak tahu program mana yang melakukan itu.

2) Scikit-learn clustering memberikan gambaran yang sangat baik tentang k-means, mini-batch-k-means ... dengan kode yang berfungsi pada matriks scipy.sparse.

3) Selalu periksa ukuran cluster setelah k-means. Jika Anda mengharapkan cluster berukuran hampir sama, tetapi mereka keluar [44 37 9 5 5] %... (suara menggaruk-garuk kepala).

denis
sumber
1
+1 Pertama-tama, terima kasih telah membagikan implementasi Anda. Saya hanya ingin mengonfirmasi bahwa algoritme berfungsi dengan baik untuk set data 900 vektor dalam ruang 700 dimensi. Saya hanya ingin tahu apakah mungkin untuk mengevaluasi kualitas cluster yang dihasilkan. Dapatkah salah satu nilai dalam kode Anda digunakan kembali untuk menghitung kualitas cluster untuk membantu dalam memilih jumlah cluster optimal?
Legenda
6
Legenda, sama-sama. (Diperbarui kode untuk mencetak cluster 50% / 90% radius). "Kualitas cluster" adalah topik yang umum: berapa banyak cluster yang Anda miliki, apakah Anda memiliki sampel pelatihan dengan cluster yang dikenal, misalnya dari para ahli? Pada jumlah cluster, lihat SO bagaimana-cara-saya-menentukan-k-kapan-menggunakan-k-cara-pengelompokan -ketika-menggunakan-k-cara-pengelompokan
denis
1
Terima kasih sekali lagi. Sebenarnya, saya tidak memiliki sampel pelatihan tetapi saya mencoba memverifikasi cluster secara manual setelah klasifikasi (mencoba memainkan peran pakar domain juga). Saya melakukan klasifikasi tingkat dokumen setelah menerapkan SVD ke beberapa dokumen asli dan mengurangi dimensi mereka. Hasilnya tampak bagus tetapi saya tidak yakin bagaimana memvalidasinya. Untuk tahap awal, sambil menjelajahi berbagai metrik validitas kluster, saya menemukan Dunn's Index, metode Elbow dll. Tidak terlalu yakin yang mana yang akan digunakan jadi saya pikir saya akan memulai dengan metode Elbow.
Legenda
7
Saya tahu ini un-pembumian sesuatu yang sangat tua, tapi saya baru mulai menggunakan kmeans dan menemukan ini. Untuk pembaca yang akan datang tergoda untuk menggunakan kode ini: periksa komentar @ Anony-Mousse pada pertanyaan di atas terlebih dahulu! Implementasi ini, sejauh yang saya bisa lihat, membuat asumsi yang salah bahwa Anda masih bisa menggunakan "mean of points in a cluster" untuk menentukan pusat massa dari cluster tersebut. Ini tidak masuk akal untuk hal lain selain jarak Euclidean (kecuali dalam kasus yang sangat spesifik pada unit sphere, dll ...). Lagi-lagi komentar Anony-Mousse tentang pertanyaan itu benar.
Nevoris
3
@Nevoris, ya saya setuju, kecuali untuk jarak cosinus: lihat di sini untuk alasannya, juga mengapa-tidak-k-berarti-pengelompokan-algoritma-gunakan-hanya-euclidean-jarak-metrik
denis
43

Sayangnya tidak: scikit-pelajari implementasi k-means saat ini hanya menggunakan jarak Euclidean.

Bukan hal sepele untuk memperluas k-means ke jarak lain dan jawaban denis 'di atas bukanlah cara yang benar untuk mengimplementasikan k-means untuk metrik lainnya.

ogrisel
sumber
26

Cukup gunakan nltk sebagai gantinya di mana Anda bisa melakukan ini, mis

from nltk.cluster.kmeans import KMeansClusterer
NUM_CLUSTERS = <choose a value>
data = <sparse matrix that you would normally give to scikit>.toarray()

kclusterer = KMeansClusterer(NUM_CLUSTERS, distance=nltk.cluster.util.cosine_distance, repeats=25)
assigned_clusters = kclusterer.cluster(data, assign_clusters=True)
mdubez
sumber
4
Seberapa efisien implementasi ini? Tampaknya butuh selamanya untuk mengelompokkan sedikitnya 5 poin (dalam dimensi 100).
Nikana Reklawyks
3
Dalam dimensi 100, pengelompokan 1k poin membutuhkan 1 detik per run ( repeats), 1.5k poin membutuhkan 2 menit, dan 2k membutuhkan ... terlalu lama.
Nikana Reklawyks
2
Memang; sesuai komentar @ Anony-Mousse di bawah ini, sepertinya cosine distance mungkin memiliki masalah konvergensi. Bagi saya, ini benar-benar kasus sampah-dalam-sampah: Anda bisa menggunakan fungsi jarak apa pun yang Anda inginkan, tetapi jika fungsi itu melanggar asumsi algoritma, jangan berharap itu menghasilkan hasil yang bermakna!
Chiraz BenAbdelkader
15

Ya, Anda dapat menggunakan fungsi metrik perbedaan; Namun, menurut definisi, algoritma klaster k-means bergantung pada jarak eucldiean dari rata-rata setiap klaster.

Anda bisa menggunakan metrik yang berbeda, jadi meskipun Anda masih menghitung rata-rata, Anda bisa menggunakan sesuatu seperti jarak mahalnobis.

Adam
sumber
25
+1: Saya tekankan bahwa mengambil mean ini hanya sesuai untuk fungsi jarak tertentu, seperti jarak Euclidean . Untuk fungsi jarak lainnya, Anda harus mengganti fungsi estimasi pusat-cluster!
Memiliki QUIT - Anony-Mousse
2
@ Anony-Mousse. Apa yang harus saya ubah ketika saya menggunakan jarak cosinus misalnya?
penasaran
6
Saya tidak tahu Saya belum melihat bukti untuk konvergensi dengan Cosine. Saya percaya ini akan konvergen jika data Anda non-negatif dan dinormalisasi ke unit sphere, karena itu pada dasarnya k-means dalam ruang vektor yang berbeda.
Memiliki QUIT - Anony-Mousse
1
Saya setuju dengan @ Anony-Mousse. Bagi saya, ini hanya kasus sampah-dalam-sampah-keluar: Anda bisa menjalankan K-means dengan fungsi jarak apa pun yang Anda inginkan, tetapi jika fungsi itu melanggar asumsi yang mendasari algoritma, jangan berharap itu menghasilkan makna yang berarti hasil!
Chiraz BenAbdelkader
@ Anony-Mousse tetapi bagaimana menerapkan K-means dengan menggunakan jarak mahalnobis?
Cecilia
7

Ada pyclustering yang merupakan python / C ++ (begitu cepat!) Dan memungkinkan Anda menentukan fungsi metrik khusus

from pyclustering.cluster.kmeans import kmeans
from pyclustering.utils.metric import type_metric, distance_metric

user_function = lambda point1, point2: point1[0] + point2[0] + 2
metric = distance_metric(type_metric.USER_DEFINED, func=user_function)

# create K-Means algorithm with specific distance metric
start_centers = [[4.7, 5.9], [5.7, 6.5]];
kmeans_instance = kmeans(sample, start_centers, metric=metric)

# run cluster analysis and obtain results
kmeans_instance.process()
clusters = kmeans_instance.get_clusters()

Sebenarnya, saya belum menguji kode ini, tetapi menggabungkannya dari kode tiket dan contoh .

CpILL
sumber
perlu Matplotlib diinstal yang membutuhkan "Python sebagai kerangka kerja pada Mac OS X" :(
CpILL
3

Sklearn Kmeans menggunakan jarak Euclidean . Tidak memiliki parameter metrik. Ini mengatakan, jika Anda mengelompokkan time series , Anda dapat menggunakan tslearnpaket python, ketika Anda dapat menentukan metrik ( dtw, softdtw, euclidean).

Tawej
sumber