Что делать, если KMeans возвращает меньше, чем K кластеров?

Question

Я реализовал K-Means в Java и немного почесал голову.Я выбираю свои начальные центроиды, выбирая случайное значение в каждом измерении в диапазоне значений точек данных.Я сталкивался со случаями, когда это приводит к тому, что один или несколько из этих центроидов не оказываются скрытыми центроидами любой точки данных.Итак, что мне делать для следующей итерации?Просто оставить его в первоначальном рандомизированном значении?Выбрать новое случайное значение?Вычислить как среднее от других центроидов?Похоже, это не учитывается в исходном алгоритме, но, возможно, я просто что-то упустил.

Answer 1

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

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

Вы также можете попробовать сделать более разумный начальный выбор центроидов кластера, используя kmeans ++ . Этот алгоритм случайным образом выбирает первый центроид и выбирает оставшиеся центроиды K-1, чтобы попытаться максимизировать расстояние между центрами. Выбирая более умных центроидов, вы гораздо реже сталкиваетесь с проблемой центроида, которому назначают нулевые точки данных.

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

Answer 2

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

Answer 3

Как я и использовал, начальные значения были взяты как случайные точки из набора данных, а не случайные точки в охватываемом пространстве. Это означает, что каждый кластер изначально имеет хотя бы одну точку. Вы все еще можете не повезти с выбросами, но, если повезет, вы сможете обнаружить это и перезапустить с другими точками. (При условии, что «K кластеров точек» является адекватным описанием ваших данных)