Подтвердить что ты не робот

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

Есть ли онлайн-версия алгоритма k-Means clustering?

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

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

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

Ответ 1

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

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

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

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

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

Ответ 2

Вы можете найти больше о онлайн-k-средствах в "Введение в машинное обучение" Этем Алпайдин в главе 12. Локальные модели