Кластеризации данных в области прикладной информатики и программной инженерии на примере зарубежного опыта и зарубежных публикаций
жүктеу/скачать 177,5 Kb.
|
| Методы кластеризации
Две общие категории кластеризации Рисунок 1. Стандартный алгоритм кластеризации k-means. Первая, также называемая кластеризацией на основе сходства, объединяет похожие экземпляры данных вместе на основе меры близости данных по парам. Кластеризация на основе графовых разделов и односвязная иерархическая агломеративная кластеризация - два широко используемых метода в этой категории. Центральная кластеризация, также называемая кластеризацией на основе центроида или на основе модели, представляет каждый кластер с помощью модели, то есть центроида кластера. К этой категории относятся обычная кластеризация k-means, кластеризация на основе смеси моделей и некоторые более сложные варианты. Алгоритмы кластеризации на основе центроида часто более эффективны, чем алгоритмы кластеризации на основе сходства, поэтому мы решили использовать именно их. Алгоритмы на основе сходства обычно имеют сложность не менее O(N2) (для вычисления мер близости между парами данных), где N - количество экземпляров данных. В отличие от них, алгоритмы на основе центроидов более масштабируемы, их сложность составляет O(NKM), где K - число кластеров, а M - число пакетных итераций. Мы изучаем два метода кластеризации - k-means и Neural- Gas - для группировки немаркированных модулей программной системы с высокой степенью гарантии. k-means На рисунке 1 показан широко используемый стандартный алгоритм k-средних. Объективная функция, которую он минимизирует, задается средней квадратичной ошибкой, Neural-Gas Алгоритм кластеризации Neural-Gas - это метод конкурентного обучения, использующий правило обучения SoftMax. То есть множество центроидов обновляется каждый раз, когда алгоритм посещает экземпляр данных. Количество обновлений зависит от расстояния между экземпляром данных и центроидом кластера. Это противоречит правилу "победитель-всех", используемому в алгоритме k-средств, где при каждом посещении экземпляра обновляется только ближайшая центроид. Алгоритм Neural-Gas тесно связан с самоорганизующейся картой (SOM) и кластеризацией с максимальной энтропией. В обоих алгоритмах в процесс обучения и оптимизации встроен детерминированный механизм отжига, позволяющий избежать множества локально оптимальных решений. Пусть x - вектор данных, y - индекс кластера, а y - центроид (среднее значение) кластера y. Пакетная версия алгоритма Neural-Gas сводится к итерации между следующими двумя шагами: где b - эквивалентный температурный пара-метр, управляющий гладкостью поверхности ошибок, а r (x, y) - ранговая функция, принимающая значение k 1, если y является k-й ближайшей центроидой кластера к вектору данных x. Таким образом, кластеры ранжируются в соответствии с их расстояниями до экземпляра данных x, и вероятность назначения P(y | x) уменьшается по мере снижения ранга кластера y. Алгоритмы k-means и Neural-Gas имеют онлайн версии, в которых центральные точки кластеров обновляются постепенно, по мере поступления каждого вектора данных в алгоритмы. Правила онлайн обновления доступны в виде градиентного спуска. Более ранние работы показали, что онлайн версия алгоритма Neural-Gas сходится быстрее и находит лучшие локальные решения, чем SOM и методы кластеризации с максимальной энтропией для определенных задач. жүктеу/скачать 177,5 Kb. Достарыңызбен бөлісу:
|