Обтекание при расчете расстояния для k-средних

Question

Я пытаюсь сделать кластеризацию K-некоторого набора данных с помощью sklearn. Проблема в том, что одно из измерений - это час дня: число от 0 до 23, и поэтому алгоритм расстояния считает, что 0 очень далек от 23, потому что в абсолютном выражении это так. В действительности и для моих целей, час 0 очень близок к часу 23. Есть ли способ сделать алгоритм расстояния в какой-то форме обертывания, чтобы он вычислял более «реальную» разницу во времени. я делаю что-то простое, похожее на следующее:

from sklearn.cluster import KMeans 

clusters = KMeans(n_clusters = 2) 
data = vstack(data) 
fit = clusters.fit(data) 
classes = fit.predict(data) 

data элементы выглядит примерно [22, 418, 192], где первый элемент час.

Любые идеи?

Answer 1

Почему к-средство не работает с произвольными расстояниями

K-средства не является алгоритмом основанного на расстоянии.

К-средство минимизирует внутриквартирные суммы квадратов, что является своего рода дисперсией (это примерно средневзвешенная дисперсия всех кластеров, где каждому объекту и размеру присваивается одинаковый вес).

Для того, чтобы алгоритм Lloyds сходиться вам нужно иметь обе шаги оптимизировать ту же функцию:

• шаг переназначение
• центроид обновление шаг

Теперь «означает «функция является оценкой наименьших квадратов. То есть выбор среднего значения на шаге 2 является оптимальным для цели WCSS. Присвоение объектов по методу наименьших квадратов (= квадратичное евклидово расстояние, монотонное до евклидова расстояния) на этапе 1 также дает гарантированную конвергенцию. Среднее - это именно то, где ваша оберточная идея распалась..

Если вы подключаете случайную другую функцию расстояния, как предложено @elyase k-means может больше не сходиться.

Правильные решения

Существуют различные решения для этого:

• Использование K-medoids (PAM). Выбирая медалью вместо среднего, вы получаете гарантированную конвергенцию с произвольными расстояниями. Однако вычисление медоидов довольно дорого.
• Преобразование данных в пространство ядра, где вы довольны минимизацией суммы квадратов. Например, вы можете преобразовать час в sin(hour/12 * pi), cos(hour/12 * pi), что может быть хорошо для SSQ.
• другие, алгоритмы кластеризации на основе расстояния. К-средства старые, и с тех пор было много исследований по кластеризации. Вы можете начать с иерархической кластеризации (которая на самом деле так же стара, как и k-означает), а затем попробовать DBSCAN и ее варианты.

Answer 2

Несмотря на то, что ответ @elyase принят, я думаю, что это не правильный подход.

Да, чтобы использовать такое расстояние, вам необходимо уточнить дистанцию, и поэтому - используйте другую библиотеку. Но что более важно - понятие означает, что, используемый в k-средствах, не уложится в циклическое измерение. Давайте рассмотрим следующий пример:

#current cluster X,, based on centroid position Xc=24 
x1=1 
x2=24 

#current cluster Y, based on centroid position Yc=10 
y1=12 
y2=13 

вычисления простой среднее арифметическое будет размещать centoids в Xc=12.5, Yc=12.5, которые с точки зрения циклического meausre является incorect, она должна быть Xc=0.5, Yc=12.5. Как вы можете видеть, привязка, основанная на циклической дистанции, не является «совместимой» с простой средней работой и приводит к результатам bizzare.

• Простые к-средства приведет к кластерам {x1,y1}, {x2,y2}
• Простой к - средство + расстояние результат измерения в вырожденной суперкластере {x1,x2,y1,y2}
• Правильная кластеризация будет {x1,x2},{y1,y2}

Решение этой проблемы требует проверяя один, если (лучше ли измерять «простое среднее» или представлять одну из точек как x'=x-24). К сожалению, данный n баллов составляет 2^n возможностей.

Это кажется как использование случае kernelized к- средств, где вы на самом деле кластеризаций в абстрактном пространстве признаков (в вашем случае - в «трубе» свернутой вокруг оси времени), индуцированного ядро ​​("Сходство мера ", являющаяся скалярным произведением некоторого векторного пространства).

Подробная информация о ядра к-средства приведены here