Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ
Посмотреть оригинал

Алгоритм кластеризации

Цель алгоритма кластеризации ^-средними (k-means) — минимизация евклидовой метрики между объектами одного кластера. Показателем, т.е. целевой функцией, в алгоритме является так называемая остаточная сумма квадратов RSS, которая представляет собой сумму квадратов расстояний от объектов кластера до его центра, называемого также центроидом:

где центроид, который определяется как «центр тяжести» кластера:

На первом шаге алгоритма К центроидов выбирается случайным образом из исходного набора точек в выборке. После этого происходит формирование кластеров но следующему принципу: для взятого объекта выбирается центроид, который наиболее близко находится к нему. Затем рассчитывается целевая метрика. Как только инициализация алгоритма завершилась, начинается итерационный процесс. Суть этого процесса состоит в нескольких шагах: оценить новые центроиды как центры масс для имеющихся кластеров, для всех точек подобрать наиболее близкие кластеры и, если целевая метрика (6.3) после этого изменилась несущественно или не изменилась вовсе, закончить работу алгоритма, в противном случае необходимо заново сформировать центроиды и т.д. Представим псевдокод данного алгоритма. [1]

2

Выход:

• Множество центроидов.

Алгоритм:

1. Выбрать К случайных объектов из множества

  • 2. Для всех Д? = 1,2,..., К, пока не выполнится критерий остановки:
  • 2.1. Сформировать пустой кластер со[2] [3].
  • 2.2. Все точки xit удовлетворяющие условию

присвоить кластеру со[3].

2.3. Пересчитать центроид х^.

3. Вернуть

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

  • [1] Вход: • Выборка X = {лГ|, х2, х3,...}. • Метрика d.
  • [2] RSS получило значение ниже порогового. В таком случае,вероятнее всего, достигнуто оптимальное разбиение объектов,однако не всегда выбранный порог действительно это гарантирует. Алгоритм кластеризации ^-средними является простейшими, что немаловажно, наглядным решением задачи разбиения объектов обучающей выборки на непересекающиеся подмножества.Однако же одним из его недостатков является то, что при различных запусках данного алгоритма, в силу используемой в немрандомизации на первом шаге алгоритма, финальное решение
  • [3] После получения множества центроидов легко посчитатьразбиение множества точек исходного набора данных на кластеры — для этого достаточно проитерироваться по всем кластерам и выбрать для кластеров точки, удовлетворяющие условию(х-х^)2 —> min. В общем случае помимо критерия малого изменения значения RSS алгоритм может иметь еще несколько условий останова,а именно: • количество итераций вычисления кластеров превысилонекоторый порог. Данный метод призван ускорить выполнениеалгоритма кластеризации ^-средними, однако очевидно, что далеконе во всех случаях будет достигнут минимум целевой функции; • объекты в течение нескольких итераций не изменяли своикластеры или же центроиды не меняют своих положений. Возможно, в таком случае алгоритм застрял в локальном минимумеи для него можно попробовать выполнить некоторую «встряску» — сдвинуть случайным образом центроиды;
  • [4] После получения множества центроидов легко посчитатьразбиение множества точек исходного набора данных на кластеры — для этого достаточно проитерироваться по всем кластерам и выбрать для кластеров точки, удовлетворяющие условию(х-х^)2 —> min. В общем случае помимо критерия малого изменения значения RSS алгоритм может иметь еще несколько условий останова,а именно: • количество итераций вычисления кластеров превысилонекоторый порог. Данный метод призван ускорить выполнениеалгоритма кластеризации ^-средними, однако очевидно, что далеконе во всех случаях будет достигнут минимум целевой функции; • объекты в течение нескольких итераций не изменяли своикластеры или же центроиды не меняют своих положений. Возможно, в таком случае алгоритм застрял в локальном минимумеи для него можно попробовать выполнить некоторую «встряску» — сдвинуть случайным образом центроиды;
 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы