[МУЗЫКА] [МУЗЫКА] На данный момент существует множество алгоритмов для разных приложений и разных наборов данных. Чтобы сравнивать результаты кластеризации различных алгоритмов необходимо разработать некоторые критерии достоверности. Кроме того, если число кластеров не задано в алгоритмах кластеризации, то весьма нетривиальной задачей найти оптимальное количество кластеров для определенного набора данных. Для этого нам нужны некоторые методы валидации кластеров. Выбор оптимального решения будем основывать на понятии качества. Поскольку идеальное решение задачи кластеризации неизвестно, то оценить качество можно двумя путями, а именно формальным и экспертным. Экспертный выбор наилучшего решения задачи заключается в оценке решения специалистами в данной предметной области. Но экспертная оценка зачастую объективно невозможна из-за большого объема и сложности данных, поэтому важную роль играют формальные критерии оценки качества. Для оценки качества кластеризации и выбора оптимальной схемы кластеризации, как правило, используют два основных критерия, а именно компактность и разделение. Суть компактности заключается в том, что объекты внутри кластера должны быть расположены как можно ближе друг к другу. Общей мерой компактности является дисперсия. Если обратиться к формуле в квадратных скобках, член означает следующее: если yi = yj, то он равен 1, иначе он равен 0. Знаменатель же показывает количество пар таких объектов. В результате мы стараемся минимизировать расстояния внутри кластеров и таким образом получаем некую характеристику качества нашей кластеризации. Такая характеристика, как разделение, заключается в том, что сами кластеры должны быть между собой широко разделены. Если алгоритм кластеризации вычисляет центры кластеров, то можно построить другие функционалы, аналогичные данным. Однако нельзя сказать, что данные функционалы подходят для всех задач, поскольку в данном случае, к примеру, если использовать характеристику компактности, можно придумать следующий случай: если мы возьмем такое условие, что каждый объект у нас будет соответствовать ровно одному кластеру, то данный функционал будет, естественно, минимальным, он будет равен 0, что не является на самом деле решением той или иной задачи. Поэтому выбор критериев качества является очень важным и не всегда тривиальным для решения той или иной задачи. Оценка результатов на основе внешних критериев заключается в сравнении результатов кластеризации с предопределенной структурой, которая накладывается на набор данных. Поскольку мы заранее знаем истинную структуру, этот подход, в основном, используется для выбора правильного алгоритма кластеризации, для конкретного набора данных или же для сравнения производительности различных методов кластеризации. Главным недостатком внешней оценки является то, что если у нас уже есть истинные метки, нам не нужно разбивать данные на кластеры, и в практических приложениях у нас обычно нет такой информации. В свою очередь, эти метки отражают только одно возможное разбиение набора данных, что не означает, что не существует другого, возможно, даже лучшего способа сгруппировать те или иные наборы данных. Также весьма нетривиальным бывает вопрос назначения того или иного наблюдения тому или иному кластеру, поэтому истинные метки кластеров еще не означают решения исходной задачи. Второй подход, основанный на внутренних критериях, в этом случае результаты оцениваются с точки зрения их геометрических свойств кластеров, таких как компактность, разделение или связность, без ссылки на какую-либо внешнюю информацию. И как правило, такие критерии применяются при оценке эффективности, когда в качестве тестового множества используется какое-либо множество данных с известной структурой классов. Основой относительных критериев оценки качества кластеризации является сравнение различных схем. Один из нескольких алгоритмов кластеризации выполняется несколько раз с различными входными параметрами на одном наборе данных. И целью относительных критериев является выбор наилучшей схемы кластеризации из разных результатов. Подходы внешних критериев и внутренних, как правило, основаны на статистических тестах, что в свою очередь является недостатком с точки зрения вычислительной сложности и стоимости этих подходов. С другой стороны, относительный критерий помогает найти нам наилучшую схему кластеризации, в которой алгоритм может определить при определении предположения и параметров. Это деление нельзя назвать однозначным, поскольку внешние критерии применяются для разных структур и могут быть рассмотрены как относительные. В свою очередь, относительные критерии, основанные на сравнении показателей, могут быть использованы как внешние.
