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

Question

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

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

Первый график выглядит хорошо, но у второго, похоже, есть проблема, потому что, насколько я понимаю, стоимость 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

Answer 1

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

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

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

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

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

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