Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
25.12.2012 года Правительством РФ была утверждена «Стратегия долгосрочного развития пенсионной системы РФ», где определены перспективы согласованной п...полностью>>
'Документ'
План проведения семинаров и других информационных мероприятий для налогоплательщиков инспекциями Федеральной налоговой службы Новосибирской области в ...полностью>>
'Документ'
При доминировании какой организационной культуры работники в большей степени склонны реагировать на воздействие своих товарищей, чем на инициативы нач...полностью>>
'Основная образовательная программа'
Основная образовательная программа основного общего образования МБОУ «Средняя общеобразовательная школа №46» г.Калуги разработана в соответствии с тре...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

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

Неявное задание критериев качества в алгоритме кластеризации

Как мы уже сказали, главной задачей кластерного анализа является поиск оптимальной классификации. Результат зависит от выбора критерия качества и способа отыскания его экстремума. Существует немало алгоритмов кластеризации, решающих эту задачу. Получая на входе метрическое пространство объектов, эти алгоритмы производят классификацию.

Выделяется как минимум три цели кластеризации [Воронцов 2015]:

  1. описать структуру пространства объектов, разбивая его на классы похожих объектов и исследуя области сгущения (выделить темы),

  2. сократить объем данных, выделяя наиболее типичных представителей каждого кластера,

  3. выделить специфические объекты, не относящиеся ни к одному из кластеров.

В первом случае число кластеров (тем) должно быть невелико, тогда как во втором случае в каждый кластер должны попасть только наиболее близкие объекты – поэтому ясно, что разные задачи требуют специального подхода, и универсального подхода быть не может.

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

Существует немало работ, посвященных описанию алгоритмов кластеризации [Jain A. и др. 1999]. Мы не ставим перед собой задачу повторить эти труды и описать все возможные алгоритмы, но лишь описываем наиболее стандартные и используемые, для того чтобы оправдать выбор методов, предпринятый нами в практической части работы.

Алгоритм выделения связных компонент

Выделение связанных компонент [Лагутин 2003] – один из простейших методов кластеризации. Пространство представляется в виде графа: вершинами являются объекты, а каждому ребру соответствует число – длина пути между соответствующими объектами. Фиксируется некоторый параметр и перекрываются все те ребра, длина которых больше параметра . Граф распадается на компоненты связности (между вершинами различных компонент не может быть пути, проходящего по ребрам графа). Каждая компонента и будет искомым кластером.

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

Алгоритм кратчайшего пути

Модификацией связных компонент является алгоритм кратчайшего пути. На первом шаге строится остовное дерево с минимальной суммарной длиной ребер: вершины-объекты соединяются ребрами так, что получившийся граф не содержит циклов, при этом минимизируется сумма длин ребер полученного дерева.

В этом случае число кластеров задается входным параметром. Из остовного графа удаляется ребро наибольшей длины, оставшийся граф распадается на компонент, которые и будут искомыми кластерами.

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

Алгоритм ФОРЭЛ (Формальный элемент)

Задается некоторая точка (формальный элемент) метрического пространства и параметр . Рассматриваются только те точки-объекты, расстояние от которых до меньше . Затем точка перемещается в центр тяжести выбранных объектов и операция повторяется до стабилизации в центре области сгущения.

Этот алгоритм имеет множество вариаций и модификаций [Загоруйко 1999], которые отличаются способом объединения окрестностей формальных элементов в кластеры, способами изменения параметра , способами выбора начального положения формальных элементов, однако построены на одном и том же принципе. Значительно усложняется процедура кластеризации, если пространство нелинейно. Доказано, что он сходится за конечное число шагов.

Минимизация функционала качества

Мы уже описали, что задача алгоритма кластеризации – минимизировать некоторый критерий (функционал) качества, то есть подобрать оптимальную классификацию. Есть множество функционалов качества, среди которых нельзя назвать один «правильный». Отметим несколько естественных критериев.

Во-первых, среднее внутрикластерное расстояние должно быть как можно меньше:

С другой стороны, среднее межкластерное расстояние должно быть как можно больше:

Чтобы учесть и межклассовые, и внутриклассовые расстояния, в качестве функционала качества используют отношение этих величин: .

Для поиска минимума функционала можно использовать один из оптимизационных алгоритмов, например, EM-алгоритм и др.

Разделение смеси распределений

Один из статистических методов кластеризации – разделение смеси распределений. Предполагается, что каждый кластер – реализация некоторой случайной величины с плотностью , а – неизвестная априорная вероятность появления объектов из кластера . Тогда плотность распределения объектов выборки равна смеси плотностей .

Как правило, предполагается, что каждый кластер описывается гауссовской плотностью, т.е. представляет собой эллипсоид, оси которого параллельны осям координат.

Разделение смеси – стандартная задача, для которой используют разные методы, в частности, EM-алгоритм, корректирующий параметры распределений. На первом этапе по формуле Байеса вычисляются скрытые переменные, значение которых равно вероятности того, что объект принадлежит кластеру . На втором этапе уточняются параметры каждого кластера с учетом скрытых переменных.

Метод k-средних

Один из самых используемых алгоритмов кластеризации [Мандель 1988], метод k-средних, делит пространство объектов на кластеры близкого объема, минимизируя разброс – среднеквадратическое отклонение объектов кластера от соответствующего центра масс. Для его работы требуется задание числа кластеров.

Более формально, если – выборка пространства объектов, подбирается такой классификатор , что если – центры масс кластеров, то величина

достигает минимума.

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

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

  • Во-вторых, среднеквадратический разброс – ненормированная метрика. Известно лишь, что эталонным значением является нуль, а меньшее значение разброса предпочтительнее.

  • Отдельной проблемой представляется работа с пространствами очень больших размерностей, тогда зачастую векторы сильно разрежены. Применение алгоритмов понижения размерностей (например, PCA) существенно сокращает скорость вычисления, зачастую при этом понижая шум.

Принцип поиска оптимального значения функционала качества похож на действие алгоритма Форэл. Рассматриваются приближенные значения центров кластеров. Каждый объект выборки относится к тому кластеру, к центру которого он ближе, затем значения центров пересчитываются.

Остановимся на этом более подробно. Сначала задаются некоторые априорные значения центров масс кластеров (в западной литературе центры масс кластеров называют центроиды): . Затем циклично повторяют следующие действия. На первом шаге каждый элемент выборки относят к некоторому кластеру в соответствии к ближайшим центроидом. На следующем шаге в каждом кластере заново считается центр масс и получается новая система центров . Затем принадлежность каждого элемента определяется заново и т.д. до сходимости – пока перемещение центроидов не станет меньше некоторого фиксированного порога. Доказано, что данный алгоритм сходится за конечное число шагов, хотя возможно – в точке локального, а не глобального минимума функционала качества.

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

Этот метод – один из самых используемых в прикладных задачах, существует немало модификаций, позволяющих учесть тонкие настройки оптимизации или формы кластеров. Он крайне чувствителен к начальным приближениям центров кластеров вплоть до того, что разные стартовые позиции могут привести к разным локальным минимумам функционала качества. С этой проблемой есть разные способы борьбы, один из которых – параллельный запуск нескольких случайных приближений. Иной метод, предназначенный для решения проблемы поиска глобального минимума, называют схемой инициализации k-means++. В качестве априорного приближения выбираются наиболее удаленные друг от друга точки. Доказано, что таким путем получается заведомо лучшая кластеризация, чем при генерации случайных центров.



Похожие документы:

  1. «Компьютерная лингвистика и интеллектуальные технологии» (1)

    Документ
    ... Кафедра математической лингвистики Направление: «Лингвистика» Образовательная программа: «Прикладная и экспериментальная лингвистика» Профиль: «Компьютерная лингвистика и интеллектуальные технологии» Параллельный конкорданс ...
  2. «Компьютерная лингвистика и интеллектуальные технологии» (2)

    Документ
    ...   Кафедра математической лингвистики Направление: «Лингвистика» Образовательная программа: «Прикладная и экспериментальная лингвистика» Профиль: «Компьютерная лингвистика и интеллектуальные технологии» Выявление информации ...
  3. Как единица устной речи: общая характеристика и прагматический потенциал

    Документ
    ... результаты исследования // Компьютерная лингвистика и интеллектуальные технологии: по материалам ежегодной ... . И. Б. Пересказывательность в русском языке // Компьютерная лингвистика и интеллектуальные технологии: материалы Международной конференции «Диалог ...
  4. Сводные данные международных мероприятий в области образования, науки и инноваций на 20 1 3 – 2015 гг

    Документ
    ... . ноябрь 2013 612 Международная конференция «Компьютерная лингвистика и интеллектуальные технологии» – Диалог 2013 Ин-т проблем ... техни-ческий конгресс по интеллектуальным системам и информационным технологиям Таганрогский технологический ин-т Южного ...
  5. Материал из Semantic Future

    Документ
    ... , к увеличению числа пользователей, активно использующих технологии и сервисы Semantic Web, но революции ... доступ к систематизированным знаниям и данным, относящимся к компьютерной лингвистике, т.е. возможность поиска и получения информации в терминах ...

Другие похожие документы..