[МУЗЫКА] [МУЗЫКА] Поскольку задача кластеризации неоднозначна, существует великое множество методов для ее решения. Каждая методология определяет свой набор правил для определения подобия между объектами. Рассмотрим наиболее популярные концепции для ее решения, а именно: иерархическую кластеризацию, кластеризацию на основе центров тяжести, кластеризацию на основе распределения вероятности, на основе плотности, на основе графов, на основе сетки и на основе подпространств. Модели, основанные на представлении о том, что данные, ближе расположенные в пространстве, имеют большее сходство друг с другом, чем данные, расположенные дальше. Примером таких моделей является иерархический алгоритм кластеризации. Существует два основных подхода в иерархической кластеризации, а именно — агломерационный и дивизивный. Агломерационный подход также еще называют подходом «снизу вверх», суть которого заключается в следующем: на первой итерации каждый объект данных представляет собой отдельный кластер. Дальше, в зависимости от расположения этих кластеров, мы начинаем их объединять. И данную процедуру повторяем, пока у нас не объединятся все, весь набор данных в один кластер. В свою очередь дивизивный подход, который также называют подходом «сверху вниз», заключается в следующем: на начальном этапе у нас весь набор данных представляет собой один единый кластер. А затем мы начинаем делить этот кластер в зависимости от удаленности объектов, находящихся в нем. Существуют некоторые недостатки иерархической кластеризации, а именно: объекты данных, неправильно объединенные на начальных итерациях, не могут быть перераспределены на следующих шагах. Также выбор функции расстояния в этих задачах неоднозначен. И выбор той или иной метрики может приводить к совершенно различным результатам. Однако данные методы имеют и свои плюсы, а именно: они очень легко интерпретируемы и очень показательны с точки зрения визуализации данных. Итеративные алгоритмы кластеризации, в которых понятие сходства определяется близостью точки данных к центру тяжести кластера. Алгоритм кластеризации алгоритм K-means является ярким примером из данной категории. Количество кластеров, требуемых в конце, должно быть задано заранее, что требует иметь некоторое предварительно представление о наборе данных. Данные итеративные алгоритмы имеют свои недостатки, а именно: они склонны сходится к локальным оптимумам, что всегда приводит не к лучшим результатам. Однако данные алгоритмы имеют свои плюсы, а именно: они эффективны в высокоразмерных и больших наборах данных, так они обладают не очень серьезной вычислительной сложностью. Обычно данные алгоритмы основаны на минимизации некоей целевой функции, которая определяет так называемое качество данной кластеризации. Кластеры, найденные по центральным алгоритмам, имеют выпуклые формы, и поэтому использование алгоритмов из данной методики не всегда желательно в задачах, где кластеры могут иметь произвольные формы. Эти модели кластеризации основаны на представлении о том, насколько вероятным является то, что все точки данных принадлежат одному и тому же распределению, например, Гаусса. Данные модели часто страдают от переобучения. Популярным примером этой модели является алгоритм максимизации ожиданий, который использует нормальное многомерное распределение. Метод кластеризации на основе плотности представляет собой методологию, в которой плотные точки данных разделены областями с низкой плотностью. Их общая идея состоит в том, чтобы продолжать выращивать данный кластер, пока плотность либо количество точек в окрестности превышает некоторый порог. Таким образом, для каждой точки данных в данном кластере окрестность заданного радиуса должна содержать минимальное количество точек. Привлекательной особенностью данных алгоритмов является то, что они могут обрабатывать кластеры различных произвольных форм. Кроме того, основанные на плотности подходы могут эффективно обрабатывать «зашумленные» данные и выбросы. Более того, методы на основе плотности могут быть расширены от полного пространства до кластеризации подпространств. Правда, одной из трудностей таких алгоритмов является выбор значения параметров, таких как порог плотности. В алгоритмах кластеризации на основе графов сначала строится граф или гиперграф, вершины которого представляют собой объекты данных и набор ребер, которые являются связями между этими вершинами. Графическая кластеризация — это задача группировки вершин на кластеры таким образом, чтобы как можно больше ребер было внутри кластера и относительно немного между кластерами. Если использовать теорию графов, то это можно сказать выделение клик либо сильно связанных компонентов. Основное различие между кластеризацией графа и традиционной кластеризацией данных заключается в том, что кластеры графов измеряют близость вершин на основе связности, например, количества возможных путей между двумя вершинами, или на основе структурного сходства, например, количества общих соседей из двух вершин. В то время как кластеризация данных в стандартном смысле измеряет расстояние в основном на основе сходства атрибутов, таких как евклидово расстояние между двумя векторными атрибутами. Сложность вычисления большинства алгоритмов кластеризации по крайней мере линейно пропорциональна размеру набора данных. Большим преимуществом кластеризации на основе сетки является значительное сокращение вычислительной сложности, которая не зависит от количества объектов данных и зависит только от количества ячеек в каждом измерении в фантомном пространстве признаков. Подход к кластеризации на основе сетки отличается от обычных алгоритмов кластеризации тем, что он касается не точек данных, а пространства значений. Таким образом, можно сформулировать алгоритм кластеризации на основе сетки следующим образом: на первом шаге мы должны создать структуру сетки, то есть разбить пространство данных на конечное число ячеек. На втором шаге мы рассчитываем плотность клеток для каждой ячейке, далее сортируем эти клетки в соответствии с их плотностями, определяем центры кластеров, обходим соседние ячейки. Другими словами, алгоритмы сначала квантуют исходное пространство данных в конечное число ячеек, а затем выполняют все операции в квантованном пространстве. Основной характеристикой этих алгоритмов кластеризации является их быстрое время обработки. Поскольку аналогичные точки данных попадают в одну и ту же ячейку, и будут рассматриваться как одна точка. Использование этих подходов часто является эффективным во многих задачах анализа данных. Поэтому методы на основе сетки могут быть интегрированы с другими методами кластеризации, такими как метод на основе плотности либо иерархические методы. Правда, одной из трудностей алгоритмов кластеризации на основе сетки является выбор размера данной сетки или порогов плотности, поскольку мелкие размеры сетки приводят к огромному количеству вычислений, в то время как грубые размеры сетки приводят к низкому качеству кластеров. Традиционные алгоритмы кластеризации учитывают все размеры исходного набора данных. Таким образом, в высокоразмерных наборах данных мы сталкиваемся с несколькими проблемами, а именно: в очень больших размерах все объекты в наборе данных являются почти равноудаленными друг от друга, полностью маскируя при этом кластеры. Также кластеры внедряются в подпространство пространства данных, а разные кластеры могут существовать в разных подпространствах. В свою очередь неактуальные измерения могут скрывать кластеры в зашумленных данных. Эти алгоритмы удаляют ненужные и избыточные размеры. В отличие от методов выбора, которые анализируют набор данных в целом, алгоритм кластеризации подпространств локализует их поиск и способен обнаружить кластеры, которые существуют в нескольких возможных перекрывающихся пространствах. Одним из возможных решений является использование метода уменьшения размеров: таких как метод главных компонент, трансформация [НЕРАЗБОРЧИВО] или метод выбора признаков. В подходах с уменьшением размерности сначала снижается размерность исходного набора данных, удаляя менее важные переменные, или преобразуя исходный набор данных в низкоразмерное пространство, а затем применяя обычные алгоритмы кластеризации к новому набору данных. Подбором выбора объектов можно найти размеры, на которые сопоставляются точки данных. Как в подходах к уменьшению размеров, так и при подборе объектов, необходимо отрезать некоторые переменные, что может привести к значительной потере информации. Если мы рассмотрим следующий пример: пусть у нас будет трехмерный набор данных, который имеет три кластера. Один встроенный в плоскость XY, другой пусть будет встроен в плоскость YZ, а третий встроен в плоскость ZX. Для такого набора данных применение уменьшения размера или метода выбора объектов не может восстановить всей структуры кластеризации, поскольку три кластера формируют в разных подпространствах. В общем, алгоритмы кластеризации, основанные на методе уменьшения размеров или выбора объектов, создают кластеры, которые могут не полностью отражать исходную структуру данного набора объектов. Некоторые алгоритмы кластеризации объединяют в себе идеи различных методологий, поэтому иногда алгоритм сложно классифицировать как однозначно принадлежащий к той или другой концепции. Поэтому такую систематизацию нельзя назвать однозначной. В данной таблице приведены наиболее популярные алгоритмы из различных концепций. Также перечислены все основные характеристики данных алгоритмов, с которыми мы посоветуем вам ознакомиться самостоятельно. [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА]
