Онлайн-кластеризация k-средних

Question

Существует ли онлайн-версия алгоритма k-Means для кластеризации?

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

Я написал один с хорошими результатами, но я действительно предпочел бы иметь что-то «стандартизированное» для ссылки, так как это должно использоваться в моеммагистерская работа.

Кроме того, кто-нибудь есть советы для других алгоритмов онлайн-кластеризации?(lmgtfy не удалось;))

Answer 1

Да, есть.Google не удалось найти его, потому что он более известен как «последовательные k-средние значения».

Вы можете найти две реализации псевдокода последовательных K-средних в этом разделе некоторых заметок класса Princeton CS Ричард Дуда .Я воспроизвел одну из двух реализаций ниже:

Make initial guesses for the means m1, m2, ..., mk
Set the counts n1, n2, ..., nk to zero
Until interrupted
    Acquire the next example, x
    If mi is closest to x
        Increment ni
        Replace mi by mi + (1/ni)*( x - mi)
    end_if
end_until

Прекрасно, что вам нужно запомнить только среднее значение каждого кластера и количество точек данных, назначенных кластеру.,Обновив эти две переменные, вы можете выбросить точку данных.

Я не уверен, где вы сможете найти цитату для нее.Я бы начал искать в классическом тексте Дуды Классификация образцов и анализ сцен или более новое издание Классификация образцов .Если его там нет, вы можете попробовать новейшую книгу Криса Бишопа или недавний текст Дафны Коллер и Нира Фридмана.