Реализация k-средних с евклидовым расстоянием против манхэттенского расстояния? - PullRequest
Новая
       51

Реализация k-средних с евклидовым расстоянием против манхэттенского расстояния?

0 голосов
/ 05 декабря 2018

Я реализую алгоритм kmeans с нуля на python и на Spark.На самом деле, это моя домашняя работа.Проблема заключается в реализации kmeans с предопределенными центроидами с различными методами инициализации, один из которых - случайная инициализация (c1), а другой - kmeans ++ (c2).Кроме того, необходимо использовать различные метрики расстояния, евклидово расстояние и расстояние до Манхэттена.Формула для них обоих представлена ​​следующим образом:

enter image description here

Вторая формула в каждом разделе предназначена для соответствующей функции стоимости, которая будет минимизирована,Я реализовал оба из них, но я думаю, что есть проблема.Это график функции стоимости за итерацию kmeans с различными настройками:

enter image description here

enter image description here

Первый график выглядит хорошо, но у второго, похоже, есть проблема, потому что, насколько я понимаю, стоимость kmeans должна уменьшаться после каждой итерации.Так в чем проблема?Это из моего кода или формулы?

А вот мои функции для вычисления расстояний и стоимости: 

def Euclidean_distance(point1, point2):
    return np.sqrt(np.sum((point1 - point2) ** 2))

def Manhattan_distance(point1, point2):
    return np.sum(np.absolute(point1 - point2))

def cost_per_point(point, center, cost_type = 'E'):
    if cost_type =='E':
        return Euclidean_distance(point, center)**2
    else:
        return Manhattan_distance(point, center)

А вот мой полный код на GitHub: https://github.com/mrasoolmirzaei/My-Data-Science-Projects/blob/master/Implementing%20Kmeans%20With%20Spark.ipynb

1 Ответ

0 голосов
/ 06 декабря 2018

K-означает, что не минимизирует расстояния .

Минимизирует сумму квадратов (которая не является метрикой).

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

Минимизация евклидовых расстояний - это проблема Вебера. Среднее значение не является оптимальным.Вам нужна сложная геометрическая медиана, чтобы минимизировать евклидовы расстояния.

Если вы назначаете точки с расстоянием до Манхэттена, неясно, что минимизируется ... У вас есть две конкурирующих цели,Хотя я предполагаю, что он все еще будет сходиться, это может быть сложно доказать.потому что использование среднего значения может увеличить сумму расстояний на Манхэттене.

Я думаю, что я опубликовал контрпример для k-средних, минимизирующих евклидово расстояние, здесь, в SO или stats.SE некоторое время назад.Таким образом, ваш код и анализ могут даже быть в порядке - это ошибочное задание.

...