[PYTHON] scikit-learn K-Means Clustering을 사용하여 자신의 거리 함수를 지정할 수 있습니까?

scikit-learn K-Means Clustering을 사용하여 자신의 거리 함수를 지정할 수 있습니까?

scikit-learn K-Means Clustering을 사용하여 자신의 거리 함수를 지정할 수 있습니까?

해결법

1. ==============================

   1.여기에있는 20 홀수 거리 중 하나를 사용하는 작은 kmeans가 있습니다. scipy.spatial.distance 또는 사용자 함수. 의견은 환영받을 것입니다 (이것은 지금까지 단 한 명의 사용자 만 보유하고있었습니다). 특히 N, dim, k, metric은 무엇입니까?

   여기에있는 20 홀수 거리 중 하나를 사용하는 작은 kmeans가 있습니다. scipy.spatial.distance 또는 사용자 함수. 의견은 환영받을 것입니다 (이것은 지금까지 단 한 명의 사용자 만 보유하고있었습니다). 특히 N, dim, k, metric은 무엇입니까?

   #!/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
   

   일부 노트 26mar 2012 추가 :

   1) 코사인 거리에 대해, 먼저 모든 데이터 벡터를 | X | = 1; 그때

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

   빠릅니다. 비트 벡터의 경우 벡터와 별도로 표준을 유지하십시오. 부유물로 확장하는 대신 (일부 프로그램은 확장 될 수 있지만). 스파 스 벡터의 경우 N, X의 1 %를 말하십시오. Y는 시간이 걸릴 것입니다 O (2 % N), 공간 O (N); 그러나 나는 어떤 프로그램이 그렇게하는지 모른다.

   2) Scikit-learn 클러스터링 k-means, mini-batch-k-means의 훌륭한 개요를 제공합니다 ... scipy.sparse 행렬에서 작동하는 코드.

   3) k-means 후 클러스터 크기를 항상 확인하십시오. 대략 동등한 규모의 클러스터를 원한다면 [44 37 9 5 5] % ... (머리 긁기 소리).

2. ==============================

   2.불행히도 no : scikit-k-means의 현재 구현은 유클리드 거리만을 사용합니다.

   불행히도 no : scikit-k-means의 현재 구현은 유클리드 거리만을 사용합니다.

3. ==============================

   3.대신에 nltk를 사용하십시오.

   대신에 nltk를 사용하십시오.

   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)
   

4. ==============================

   4.그렇습니다. 차이 메트릭 함수를 사용할 수 있습니다. 그러나 정의상 k- 평균 클러스터링 알고리즘은 각 클러스터의 평균으로부터의 거리에 의존한다.

   그렇습니다. 차이 메트릭 함수를 사용할 수 있습니다. 그러나 정의상 k- 평균 클러스터링 알고리즘은 각 클러스터의 평균으로부터의 거리에 의존한다.

   다른 통계를 사용할 수 있습니다. 따라서 평균을 계산하더라도 마할 노비스 거리와 같은 것을 사용할 수 있습니다.

5. ==============================

   5.Spectral Python의 k-means는 L1 (맨해튼) 거리의 사용을 허용합니다.

   Spectral Python의 k-means는 L1 (맨해튼) 거리의 사용을 허용합니다.

6. ==============================

   6.pyclustering은 python / C ++ (빠른 것!)이며 사용자 정의 메트릭 함수를 지정할 수 있습니다.

   pyclustering은 python / C ++ (빠른 것!)이며 사용자 정의 메트릭 함수를 지정할 수 있습니다.

   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()
   

   사실,이 코드를 테스트하지는 않았지만 티켓과 예제 코드에서 함께 작성했습니다.

from https://stackoverflow.com/questions/5529625/is-it-possible-to-specify-your-own-distance-function-using-scikit-learn-k-means by cc-by-sa and MIT license