Неиерархические (итеративные) методы кластеризации

С возрастанием объёмов данных иерархические методы теряют все свои привлекательные свойства, тогда эффективными могут оказаться неиерархические методы, представляющие из себя итеративные алгоритмы разделения исходной совокупности. То есть весь набор данных делится на определённое количество кластеров или пока не сработает правило остановки. В этой группе методов, используются два подхода, оба отличных от работы дивизимных иерархических принципов. Методы первого подхода определяют границы кластеров по наиболее плотным участкам многомерного пространства исходных данных. То есть происходит процесс поиска «сгущения точек». Методы второго подхода минимизируют меры различия объектов.

К-средних (k-means).

Это наиболее распространённый неиерархический метод, и возможно самый распространённый метод кластеризации в целом в связи с простотой его реализации[36].

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

PAM (k-means + k-medoids).

Метод по своей сути является модификацией К-средних с применением К-медианы[30]. Работа алгоритма аналогична K-means, только объекты в нём распределяются не относительно центра кластера, а релятивно его медианы. Алгоритм лучше своего основоположника противостоит выбросам и шумам, поскольку медиана мене подвержена этим явлениям. К сожалению, алгоритм не преобразовался настолько, чтобы применяться к для больших объёмов данных.

Алгоритм CLARA (Clustering LARge Applications).

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

LargeItem.

Алгортим LargeItem был предложен Вангом в 1990 году. Это оптимизационный алгоритм для кластеризации транзакционных данных, основанных на критериальной функции, оптимизации глобального критерия[35]. Этот глобальный критерий использует параметр поддержки (в терминологии здесь много общего с алгоритмами для выявления ассоциативных правил). В вычисление глобального критерия делает алгоритм кластеризации во много раз быстрее, чем при использовании локального критерия при парном сравнении объектов, поэтому «глобализация» оценочной функции — один из путей получения масштабируемых алгоритмов. Алгоритм включает в себя две фазы: фазу распределения и фазу улучшения. Лучшим решением является то, которое лучше минимизирует целевую функцию. Так как найти абсолютно точное решение не представляется возможным с достаточной долей вероятности, то цель этого алгоритма состоит в нахождении приближенного решения, что является достаточным для практического применения. В отличии от К-means, LargeItem позволяет значению k варьироваться, т. е. алгоритм не обязан знать её заранее. Чтобы избежать сканирования всех транзакций при кластеризации, некоторые кассетные функции, такие как |Large_i|, |U^k_i=1=Small_i| и | U^k_i=1=Large_i|, сохраняются после каждого распределения или перемещения транзакции.

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

CLOPE.

В 2002 году группа китайских учёных представила[35] алгоритм CLOPE (Clustering with sLOPE). Особенностью этого алгоритма является высокая производительность работы по сравнению с другими иерархическими методами. Работа этого алгоритма основана на максимизации глобальной функции стоимости, повышающей близость транзакций в кластерах с помощью увеличения параметра кластерной гистограммы.

С помощью параметра, названного авторами CLOPE коэффициентом отталкивания (repulsion), регулируется уровень сходства транзакций внутри кластера, и, как следствие, финальное количество кластеров. Этот коэффициент подбирается пользователем. Чем больше r, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

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