Блог

Я пытаюсь запустить кластеризацию k-средних для большого набора данных (9106 элементов, 100 измерений). Это делает его очень медленным, поэтому мне было рекомендовано использовать неравенство треугольника, как описано Чарльзом Элканом (http://cseweb.ucsd.edu /~elkan/kmeansicml03.pdf).

Есть ли какая-либо предварительно написанная функция в любом наборе инструментов для этого?

Я использую scikit learn, со своим кодом следующим образом:

 #implement a numpy array to hold the data
data_array = np.empty([9106,100])

#iterate through the data file anad add it to the numpy array
rownum = 0
for row in reader:
    if rownum != 0:
        print "rownum",rownum
        colnum = 0
        for col in row:
            if colnum !=0:
                data_array[rownum-1,colnum-1] = float(col)
                colnum =1
    rownum  = 1

n_samples, n_features = data_array.shape
n_digits = len(data_array)
labels = None #digits.target


#most of the code below was taken from the example on the scikit learn site
sample_size = 200

print "n_digits: %d, t n_samples %d, t n_features %d" % (n_digits,
                                                        n_samples, n_features)
len

print 79 * '_'
print ('% 9s' % 'init'
      '    time  inertia    homo   compl  v-meas     ARI     AMI  silhouette')


def bench_k_means(estimator, name, data):
    t0 = time()
    estimator.fit(data)
    print '% 9s   %.2fs    %i   %.3f   %.3f   %.3f   %.3f   %.3f    %.3f' % (
         name, (time() - t0), estimator.inertia_,
         metrics.homogeneity_score(labels, estimator.labels_),
         metrics.completeness_score(labels, estimator.labels_),
         metrics.v_measure_score(labels, estimator.labels_),
         metrics.adjusted_rand_score(labels, estimator.labels_),
         metrics.adjusted_mutual_info_score(labels,  estimator.labels_),
         metrics.silhouette_score(data, estimator.labels_,
                                  metric='euclidean',
                                  sample_size=sample_size),
         )


bench_k_means(KMeans(init='k-means  ', k=n_digits, n_init=10),
              name="k-means  ", data=data_array)

bench_k_means(KMeans(init='random', k=n_digits, n_init=10),
              name="random", data=data_array)

# in this case the seeding of the centers is deterministic, hence we run the
# kmeans algorithm only once with n_init=1
pca = PCA(n_components=n_digits).fit(data_array)
bench_k_means(KMeans(init=pca.components_, k=n_digits, n_init=1),
              name="PCA-based",
              data=data_array)
print 79 * '_'
 

Есть ли какая-либо предварительно написанная функция в любом наборе инструментов для этого?

Нет. Была попытка использовать этот алгоритм, но он не был объединен в master.

Это делает его очень медленным

Тогда попробуйте MiniBatchKMeans , прежде чем начинать взламывать сложные алгоритмы. Это на порядки быстрее, чем ваниль KMeans , и часто так же хорошо.

Существует такая реализация http://mloss.org/software/view/48 / и он будет обновлен в ближайшее время.