Труды КНЦ вып.9 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ) вып. 9/2019(10)

Различные методы кластеризации используют различные метрики и различные критерии. Не существует метода кластеризации, одинаково хорошо работающего для всех типов данных Классификация методов кластеризации Общепринятой классификации методов кластеризации не существует. Приведем следующие группы методов: 1. Вероятностные методы. К ним относятся методы ^-средних ( к-means, к-median, k-medoid). 2. Методы на основе искусственного интеллекта. В частности, методы в рамках нейросетевого подхода. 3. Теоретико-графовые методы. Например, метод ^-средних с критерием диаметра. 4. Логические методы. В частности, деревья решений на основе представления задачи в виде КНФ (BooleanSATisfability). 5. Иерархические методы. 6. Все другие методы, не вошедшие в классификацию. Чаще методы кластеризации делят на иерархические и неиерархические. Неиерархические (упорядоченные - partitioning) отличаются тем, что заранее известно количество кластеров. В иерархических ( hierarchical ) количество кластеров заранее неизвестно и является частью решения. Часто иерархическая кластеризация предшествует неиерархической. Результатом иерархической кластеризации является дендрограмма - древовидная диаграмма. Для остановки кластеризации существует определенный критерий. Например, когда внутри кластерное расстояние становится больше, чем межкластерное. Иерархические методы делятся на дивизимные (сверху вниз по дереву) и агломеративные (снизу вверх по дереву). Примеры: метод ближайшего соседа, метод наиболее удаленного соседа. Также методы кластеризации делят на точные и приближенные. Точные и приближенные методы кластеризации В искусственном интеллекте задачи комбинаторного поиска решаются двумя группами методов. 1. Методы систематического (конструктивного) поиска — позволяет найти глобальный экстремум. 2. Методы локального поиска. Локальный поиск не обладает свойством полноты. Систематический поиск обладает свойством полноты, но позволяет исследовать существенно меньшие пространства поиска. Точные методы обеспечивают поиск глобального оптимума. Глобальный оптимум - это точное решение задачи оптимизации, которое удовлетворяет критерию оптимизации. Приближенные (эвристические) методы, также называются «жадные алгоритмы», в качестве решения могут вернуть локальный оптимум. Алгоритмы локального поиска, которые опираются на понятие соседнего состояния, обладают малым количеством памяти для фиксации 119