Обратите внимание, что k-means рассчитано на евклидово расстояние . Он может перестать сходиться с другими расстояниями, когда среднее значение больше не является наилучшей оценкой для «центра» кластера.
ВЫЙТИ - Anony-Mousse
2
почему k-means работает только с евклидовым диссансом?
любопытно
9
@ Anony-Mousse Неправильно говорить, что k-means рассчитано только на евклидово расстояние. Его можно изменить для работы с любой допустимой метрикой расстояния, определенной в пространстве наблюдения. Например, взгляните на статью о k-medoids .
Ely
5
@curious: среднее значение минимизирует квадратные различия (= квадрат евклидова расстояния). Если вы хотите использовать другую функцию расстояния, вам нужно заменить среднее значение соответствующей оценкой центра. K-medoids - такой алгоритм, но найти medoid намного дороже.
ВЫЙТИ - Anony-Mousse
4
Несколько уместно здесь: в настоящее время существует открытый запрос на включение, реализующий ядро K-Means. Когда вы закончите, вы сможете указать свое собственное ядро для вычислений.
jakevdp
Ответы:
77
Вот небольшое kmeans, которое использует любое из 20 с лишним расстояний в
scipy.spatial.distance или пользовательскую функцию.
Будут приветствоваться комментарии (пока что у него был только один пользователь, недостаточно); в частности, каковы ваши N, dim, k, метрика?
#!/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 divisionimport randomimport numpy as npfrom scipy.spatial.distance import cdist # $scipy/spatial/distance.py# http://docs.scipy.org/doc/scipy/reference/spatial.htmlfrom 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.
"""ifnot issparse(X):
X = np.asanyarray(X)# ?
centres = centres.todense()if issparse(centres) \else centres.copy()
N, dim = X.shape
k, cdim = centres.shapeif dim != cdim:raiseValueError("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 =0for 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"% avdistif(1- delta)* prevdist <= avdist <= prevdist \or jiter == maxiter:break
prevdist = avdistfor 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.shapeif 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 ddef 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)defLqmetric( x, y=None, q=.5):# yes a metric, may increase weight of near matches; see ...return(np.abs(x - y)** q).mean()if y isnotNone \else(np.abs(x)** q).mean()#...............................................................................classKmeans:""" 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 = Xif centres isNone:
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 randomimport sysfrom 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 =1exec("\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
Некоторые заметки добавлены 26мар 2012:
1) для косинусного расстояния сначала нормализуем все векторы данных к | X | = 1; затем
cosinedistance( X, Y )=1- X . Y =Euclidean distance |X - Y|^2/2
это быстро. Для битовых векторов храните нормы отдельно от векторов, а не расширяйте их до чисел с плавающей запятой (хотя некоторые программы могут расширяться для вас). Для разреженных векторов, скажем, 1% от N, X. Y должно занять время O (2% N), пробел O (N); но я не знаю, какие программы это делают.
2)
Кластеризация Scikit-Learn
дает превосходный обзор k-средних, мини-пакетных k-средних ... с кодом, который работает с матрицами scipy.sparse.
3) Всегда проверяйте размеры кластеров после k-средних. Если вы ожидаете кластеры примерно одинакового размера, но они выходят
[44 37 9 5 5] %... (звук царапин на голове).
+1 Прежде всего, спасибо, что поделились своей реализацией. Я просто хотел подтвердить, что алгоритм отлично работает для моего набора данных из 900 векторов в 700-мерном пространстве. Мне просто интересно, можно ли оценить качество сгенерированных кластеров. Можно ли повторно использовать какие-либо значения в вашем коде для вычисления качества кластера, чтобы помочь в выборе количества оптимальных кластеров?
Легенда
6
Легенда, пожалуйста. (Обновлен код для печати кластера радиусом 50% / 90%). «Качество кластеров» - это большая тема: сколько у вас кластеров, есть ли у вас обучающие образцы с известными кластерами, например, от экспертов? О количестве кластеров см. SO how-do-i-определить-k-когда-используя-k-средства-кластеризацию -when-используя-k-средства-кластеризацию
Денис
1
Спасибо еще раз. На самом деле, у меня нет обучающих образцов, но я пытаюсь проверить кластеры вручную после классификации (пытаясь играть роль эксперта по предметной области). Я выполняю классификацию на уровне документов после применения SVD к некоторым исходным документам и уменьшения их размеров. Результаты кажутся хорошими, но я не был уверен, как их проверить. На начальном этапе, изучая различные метрики валидности кластера, я натолкнулся на индекс Данна, метод Колена и т. Д., На самом деле не был уверен, какой из них использовать, поэтому подумал, что начну с метода Колена.
Легенда
7
Я знаю, что это заземление чего-то действительно старого, но я только начал с использования Kmeans и наткнулся на это. Для будущих читателей, испытывающих желание использовать этот код: сначала ознакомьтесь с комментариями @ Anony-Mousse по вышеуказанному вопросу! Эта реализация, насколько я вижу, делает неверное предположение, что вы все равно можете использовать «среднее значение точек в кластере» для определения центроида этого кластера. Это не имеет смысла ни для чего, кроме евклидова расстояния (за исключением очень специфических случаев в единичной сфере и т. Д.). Снова комментарии Анони-Мусса по этому вопросу прямо на носу.
Просто используйте вместо этого nltk, где вы можете сделать это, например
from nltk.cluster.kmeans importKMeansClusterer
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)
Насколько эффективна эта реализация? Похоже, что на кластеризацию нужно всего 5 тысяч точек (в измерении 100).
Никана Рекламикс
3
В измерении 100 кластеризация 1k точек занимает 1 секунду за цикл ( repeats), 1,5k точек занимает 2 минуты, а 2k занимает ... слишком много.
Никана Рекламикс
2
На самом деле; согласно комментарию @ Anony-Mousse ниже, кажется, что косинусное расстояние может иметь проблемы сходимости. Для меня это действительно случай мусора в мусоре: вы можете использовать любую функцию расстояния, какую захотите, но если эта функция нарушает предположения алгоритма, не ожидайте, что она даст значимые результаты!
Chiraz BenAbdelkader
15
Да, вы можете использовать функцию разницы метрик; однако по определению алгоритм кластеризации k-средних основывается на евклидовом расстоянии от среднего значения каждого кластера.
Вы можете использовать другую метрику, поэтому, хотя вы все еще рассчитываете среднее значение, вы можете использовать что-то вроде расстояния Махалнобиса.
+1: позвольте мне подчеркнуть, что взятие среднего значения подходит только для определенных функций расстояния, таких как евклидово расстояние . Для других функций расстояния вам также необходимо заменить функцию оценки центра кластера!
ВЫЙТИ - Anony-Mousse
2
@ Anony-мусс. Что я должен изменить, например, когда я использую косинусное расстояние?
любопытно
6
Я не знаю. Я не видел доказательств сближения с косинусом. Я полагаю, что они будут сходиться, если ваши данные неотрицательны и нормализованы в единичной сфере, потому что тогда это по существу k-средства в другом векторном пространстве.
ВЫЙТИ - Anony-Mousse
1
Я согласен с @ Anony-Mousse. Для меня это просто случай мусора в мусоре: вы можете запустить K-means с любой функцией расстояния, которую вы хотите, но если эта функция нарушает основные предположения алгоритма, не ожидайте, что он произведет значимое полученные результаты!
Chiraz BenAbdelkader
@ Anony-Mousse, но как реализовать K-средства с помощью расстояния до Махальнобиса?
Сесилия
7
Существует 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()
На самом деле, я не проверял этот код , но мощеный вместе с билетом и примером кода .
Sklearn Kmeans использует евклидово расстояние . У него нет метрического параметра. При этом, если вы кластеризация временных рядов , вы можете использовать tslearnпакет питона, когда вы можете указать метрику ( dtw, softdtw, euclidean).
Ответы:
Вот небольшое kmeans, которое использует любое из 20 с лишним расстояний в scipy.spatial.distance или пользовательскую функцию.
Будут приветствоваться комментарии (пока что у него был только один пользователь, недостаточно); в частности, каковы ваши N, dim, k, метрика?
Некоторые заметки добавлены 26мар 2012:
1) для косинусного расстояния сначала нормализуем все векторы данных к | X | = 1; затем
это быстро. Для битовых векторов храните нормы отдельно от векторов, а не расширяйте их до чисел с плавающей запятой (хотя некоторые программы могут расширяться для вас). Для разреженных векторов, скажем, 1% от N, X. Y должно занять время O (2% N), пробел O (N); но я не знаю, какие программы это делают.
2) Кластеризация Scikit-Learn дает превосходный обзор k-средних, мини-пакетных k-средних ... с кодом, который работает с матрицами scipy.sparse.
3) Всегда проверяйте размеры кластеров после k-средних. Если вы ожидаете кластеры примерно одинакового размера, но они выходят
[44 37 9 5 5] %
... (звук царапин на голове).источник
К сожалению, нет: в текущей реализации k-средних используется только евклидово расстояние.
Нетрудно расширить k-средних на другие расстояния, и ответ Дениса выше не является правильным способом реализации k-средних для других метрик.
источник
Просто используйте вместо этого nltk, где вы можете сделать это, например
источник
repeats
), 1,5k точек занимает 2 минуты, а 2k занимает ... слишком много.Да, вы можете использовать функцию разницы метрик; однако по определению алгоритм кластеризации k-средних основывается на евклидовом расстоянии от среднего значения каждого кластера.
Вы можете использовать другую метрику, поэтому, хотя вы все еще рассчитываете среднее значение, вы можете использовать что-то вроде расстояния Махалнобиса.
источник
Существует pyclustering, который является Python / C ++ (так быстро!) И позволяет вам указать пользовательскую метрическую функцию
На самом деле, я не проверял этот код , но мощеный вместе с билетом и примером кода .
источник
k-средство Spectral Python позволяет использовать расстояние L1 (Манхэттен).
источник
Sklearn Kmeans использует евклидово расстояние . У него нет метрического параметра. При этом, если вы кластеризация временных рядов , вы можете использовать
tslearn
пакет питона, когда вы можете указать метрику (dtw
,softdtw
,euclidean
).источник