Алгоритм Python k-средних
-
20-09-2019 - |
Вопрос
Я ищу реализацию алгоритма k-средних на Python с примерами для кластеризации и кэширования моей базы данных координат.
Решение
Кластеризация Scipy реализации работают хорошо и включают в себя k-средство выполнение.
Есть также scipy-кластер, который выполняет агломеративную кластеризацию;Преимущество этого метода заключается в том, что вам не нужно заранее определять количество кластеров.
Другие советы
SciPy's кмсредство2() имеет некоторые численные проблемы:у других есть сообщил сообщения об ошибках, такие как «Матрица не является положительно определенной - разложение Холецкого невозможно вычислить» в версии 0.6.0, и я только что столкнулся с тем же самым в версии 0.7.1.
На данный момент я бы рекомендовал использовать PyCluster вместо.Пример использования:
>>> import numpy
>>> import Pycluster
>>> points = numpy.vstack([numpy.random.multivariate_normal(mean,
0.03 * numpy.diag([1,1]),
20)
for mean in [(1, 1), (2, 4), (3, 2)]])
>>> labels, error, nfound = Pycluster.kcluster(points, 3)
>>> labels # Cluster number for each point
array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], dtype=int32)
>>> error # The within-cluster sum of distances for the solution
1.7721661785401261
>>> nfound # Number of times this solution was found
1
Для непрерывных данных использовать k-средние очень просто.
Вам нужен список ваших средних значений, и для каждой точки данных найдите ближайшее к ней среднее значение и усредните новую точку данных.ваши средние значения будут представлять собой недавние существенные группы точек во входных данных.
Я выполняю усреднение постоянно, поэтому для получения нового среднего значения нет необходимости иметь старые данные.Учитывая старое среднее значение k
, следующая точка данных x
, и константа n
которое представляет собой количество прошлых точек данных, для которых нужно сохранить среднее значение, новое среднее значение равно
k*(1-(1/n)) + n*(1/n)
Вот полный код на Python
from __future__ import division
from random import random
# init means and data to random values
# use real data in your code
means = [random() for i in range(10)]
data = [random() for i in range(1000)]
param = 0.01 # bigger numbers make the means change faster
# must be between 0 and 1
for x in data:
closest_k = 0;
smallest_error = 9999; # this should really be positive infinity
for k in enumerate(means):
error = abs(x-k[1])
if error < smallest_error:
smallest_error = error
closest_k = k[0]
means[closest_k] = means[closest_k]*(1-param) + x*(param)
вы можете просто распечатать средства, когда все данные пройдут, но гораздо интереснее наблюдать, как они меняются в реальном времени.Я использовал это на огибающих частот звуковых фрагментов длительностью 20 мс, и после разговора с ним в течение минуты или двух он имел последовательные категории для короткой гласной «а», долгой гласной «о» и согласной «s».странно!
От Википедия, вы можете использовать scipy, K-означает кластеризацию векторного квантования
Или вы можете использовать оболочку Python для OpenCV, ctypes-opencv.
Или ты мог бы Новый интерфейс Python OpenCV, и их кмсредство выполнение.
(Годы спустя) этот kmeans.py под возможно ли указать свою собственную функцию расстояния с помощью scikits-learn-k-средств является простым и достаточно быстрым;он использует любую из 20 с лишним метрик в scipy.spatial.distance.
Вы также можете использовать GDAL, который имеет множество функций для работы с пространственными данными.
SciKit Learn's KMeans() — это самый простой способ применить кластеризацию k-средних в Python.Установка кластеров проста:kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
.
В этом фрагменте кода показано, как хранить координаты центроида и прогнозировать кластеры для массива координат.
>>> from sklearn.cluster import KMeans
>>> import numpy as np
>>> X = np.array([[1, 2], [1, 4], [1, 0],
... [4, 2], [4, 4], [4, 0]])
>>> kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
>>> kmeans.labels_
array([0, 0, 0, 1, 1, 1], dtype=int32)
>>> kmeans.predict([[0, 0], [4, 4]])
array([0, 1], dtype=int32)
>>> kmeans.cluster_centers_
array([[ 1., 2.],
[ 4., 2.]])
(любезно предоставлено документацией SciKit Learn, ссылка на которую приведена выше)
Python Pycluster и pyplot можно использовать для кластеризации k-средних и для визуализации 2D-данных.Недавняя запись в блоге Анализ цены/объема акций с использованием Python и PyCluster приводит пример кластеризации с использованием PyCluster на стандартных данных.