logo
стоэи

37. Метод «кластеризации».

Кластеризация – это автоматическое разбиение элементов некоторого множества на группы (кластеры) по принципу схожести.

Много практических применений в информатике и других областях:

-анализ данных (DataMining);

-группировка и распознавание объектов;

-извлечение и поиск информации.

Общая схема кластеризации:

1. выделение характеристик.

-выбор свойств, характеризующих объекты:

А) количественные характеристики (координаты, интервалы…);

Б) качественные характеристики (цвет, статус, воинское звание….).

- уменьшение размерности пространства, нормализация характеристик.

-представление объектов в виде характеристических векторов.

2. определение метрики.

-метрика выбирается в зависимости от:

А) пространства, где расположены объекты;

Б) неявных характеристик кластеров.

3. разбиение объектов на группы.

4. представление результатов.

Обычно используется один из следующих способов:

-представление кластеров центроидами;

-представление кластеров набором характерных точек;

--представление кластеров их ограничениями.

Общая схема кластеризации одна, но существуем много различных реализаций этой схемы.

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

-иерархические алгоритмы;

-минимальное покрывающее дерево;

-k-Meansалгоритм (алгоритмk-средних);

-метод ближайшего соседа;

-алгоритмы нечеткой кластеризации;

-применение нейронных сетей;

-генетические алгоритмы;

-метод закалки.

Какой алгоритм выбрать?

-генетические алгоритмы и искусственные нейронные сети хорошо распараллеливаются.

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

-генетические алгоритмы хорошо работают только для одно- (двух-) мерных объектов, зато не требуется непрерывность координат.

-k-meansбыстро работает и прост в реализации, но создает только кластеры, похожие на гиперсферы.

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

-на практике лучше всего зарекомендовали себя гибридные походы, где шлифовка кластеров выполняется методом k-Means, а первоначальное разбиение – одним из более сильных методов.