Кластеризация это что такое
Кластеризация
Кластерный анализ (англ. Data clustering ) — задача разбиения заданной выборки объектов (ситуаций) на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались.
Задача кластеризации относится к статистической обработке, а также к широкому классу задач обучения без учителя.
Содержание
Типология задач кластеризации
Типы входных данных
Цели кластеризации
В первом случае число кластеров стараются сделать поменьше. Во втором случае важнее обеспечить высокую степень сходства объектов внутри каждого кластера, а кластеров может быть сколько угодно. В третьем случае наибольший интерес представляют отдельные объекты, не вписывающиеся ни в один из кластеров.
Во всех этих случаях может применяться иерархическая кластеризация, когда крупные кластеры дробятся на более мелкие, те в свою очередь дробятся ещё мельче, и т. д. Такие задачи называются задачами таксономии.
Результатом таксономии является древообразная иерархическая структура. При этом каждый объект характеризуется перечислением всех кластеров, которым он принадлежит, обычно от крупного к мелкому.
Классическим примером таксономии на основе сходства является биноминальная номенклатура живых существ, предложенная Карлом Линнеем в середине XVIII века. Аналогичные систематизации строятся во многих областях знания, чтобы упорядочить информацию о большом количестве объектов.
Методы кластеризации
Формальная постановка задачи кластеризации
Пусть — множество объектов, — множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами . Имеется конечная обучающая выборка объектов . Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике , а объекты разных кластеров существенно отличались. При этом каждому объекту приписывается номер кластера .
Алгоритм кластеризации — это функция , которая любому объекту ставит в соответствие номер кластера . Множество в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.
Кластеризация (обучение без учителя) отличается от классификации (обучения с учителем) тем, что метки исходных объектов изначально не заданы, и даже может быть неизвестно само множество .
Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин:
а также ряд алгоритмов, не имеющих чётко выраженного критерия, но осуществляющих достаточно разумную кластеризацию «по построению». Все они могут давать разные результаты.
Применение
В биологии
В социологии
В информатике
См. также
Литература
Внешние ссылки
На русском языке
На английском языке
Полезное
Смотреть что такое «Кластеризация» в других словарях:
кластеризация — — [Интент] Тематики автоматизированные системы EN clustering … Справочник технического переводчика
кластеризация — кластериз ация, и … Русский орфографический словарь
КЛАСТЕРИЗАЦИЯ — выделение различных групп объектов с общими признаками [63, c. 83] … Современный образовательный процесс: основные понятия и термины
кластеризация записей — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN record clustering … Справочник технического переводчика
Кластеризация рекламы — подача новостей или рекламной информации блоками, в которых объединяющую роль играет или общая тема, или общая фирма, рекламирующая свои товары … Реклама и полиграфия
Кластеризация генов — * кластарызацыя генаў * gene clustering задача разбиения заданной выборки генов на подмножества, называемые кластерами (), так, чтобы каждый кластер состоял из схожих генов, а гены разных кластеров существенно отличались. Задача К. г. относится к … Генетика. Энциклопедический словарь
Кластеризация результатов поиска — Кластеризация результатов поиска группировка результатов поиска в поисковой системе по тому или иному признаку с целью сделать результат поиска более удобным. Например, в корпусной лингвистике при поиске по достаточно большому корпусу может … Википедия
кластеризация диполя — dipolio klasterizacija statusas T sritis chemija apibrėžtis Dipolio susiskaidymas į kelis mažesnius dipolius. atitikmenys: angl. dipole clustering rus. кластеризация диполя … Chemijos terminų aiškinamasis žodynas
Кластеризация документов — Для улучшения этой статьи желательно?: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение). Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждаю … Википедия
Иерархическая кластеризация — (также графовые алгоритмы кластеризации) совокупность алгоритмов упорядочивания данных, визуализация которых обеспечивается с помощью графов. Алгоритмы упорядочивания данных указанного типа исходят из того, что некое множество объектов… … Википедия
Кластеризация
Кластеризация — это разбиение множества объектов на подмножества (кластеры) по заданному критерию. Каждый кластер включает максимально схожие между собой объекты. Представим переезд: нужно разложить по коробкам вещи по категориям (кластерам) — например одежда, посуда, декор, канцелярия, книги. Так удобнее перевозить и раскладывать предметы в новом жилье. Процесс сбора вещей по коробкам и будет кластеризацией.
Критерии кластеризации определяет человек, а не алгоритм, — этим она отличается от классификации. Этот метод машинного обучения (Machine Learning) часто применяют в различных неструктурированных данных — например если нужно автоматически разбить коллекцию изображений на мини-группы по цветам.
Кластерный анализ применяют в разных сферах:
Типы входных данных
Признаковое описание объектов
Объект описывается при помощи набора характеристик. Признаки бывают числовые и категориальные. Например, можно кластеризовать группу покупателей на основе их покупок в интернет-магазине. В качестве входных данных будут средний чек, возраст, количество покупок в месяц, любимая категория покупок и другие критерии.
Матрица расстояний между выделенными объектами
Это симметричная таблица, где по строкам и столбцам расположены объекты, а на пересечении — расстояние между ними: например, таблица с расстояниями между отелями в разных городах. Такой способ может помочь выделить кластеры отелей, которые сгруппированы в одной и той же локации.
Освойте самую востребованную технологию искусственного интеллекта. Дополнительная скидка 5% по промокоду BLOG.
Цели кластеризации
Сжатие данных
Кластеризация актуальна, если исходная выборка слишком большая. В результате от каждого кластера остается по одному типичному представителю. Количество кластеров может быть любым — здесь важно обеспечить максимальное сходство объектов внутри каждой группы.
Поиск паттернов внутри данных
Разбиение объектов на кластеры позволяет добавить дополнительный признак каждому объекту. Так, если в результате кластерного анализа выявилось, что определенный покупатель относится к первому кластеру, и мы знаем, что первый кластер — это кластер людей, которые тратят большое количество денег на покупки по средам, то можно сказать, что это покупатель приобретает продукты в основном по средам.
Поиск аномалий
В этом случае выделяют нетипичные объекты, не подходящие ни к одному сформированному кластеру. Интересны отдельные объекты, которые не вписываются ни в одну из сформированных групп.
Методы кластеризации
Общепринятой классификации методов нет, но есть несколько групп подходов.
1. Вероятностный подход. В рамках него предполагается, что каждый из объектов относится к одному из классов.
2. Подходы с учетом систем искусственного интеллекта. Большая условная группа методов, разнится с методической точки зрения.
4. Иерархический подход. Предполагает наличие вложенных групп — кластеров разного порядка. Выделяются агломеративные и дивизионные (объединительные и разделяющие) алгоритмы. В зависимости от количества признаков могут выделяться политетические (используют при сравнении нескольких признаков одновременно) и монотетические (используют при применении одного признака) методы классификации.
Как описать кластеризацию формально?
В кластеризации имеют дело с множеством объектов (X) и множеством номеров кластеров (Y). Задана функция расстояния между объектами ( p). Нужно разбить обучающую выборку на кластеры, так чтобы каждый кластер состоял из объектов, близких по метрике p, а объекты разных кластеров существенно отличались. При этом каждому объекту приписывается номер кластера y(i).
Алгоритм кластеризации — это функция, которая любому объекту X ставит в соответствие номер кластера Y.
Data Science с нуля
Вы получите достаточную математическую подготовку и опыт программирования на Python, чтобы решать задачи машинного обучения.
Что такое кластеризация или кластерный анализ
Примеры кластеризации в маркетинге.
Если у вас есть большой массив данных, то наиболее эффективный способ понять, что с ними делать — рассортировать их в группы для первичного анализа. Группировать можно при помощи — сегментации (вы сами задаете критерии, например, возрастные и ценовые группы) или кластеризации (математический алгоритм сам выявляет “связующий” критерий или признак, который объединяет данные). Ценность data-driven подхода и основное отличие кластеризации заключается в том, что алгоритмы выявляют и объединяют параметры с похожими чертами из первичного массива данных.
Маркетинг и продажи — одно из направлений применения кластерного анализа. В частности для прогнозирования будущего поведения покупателя — персонализации и таргетирования. Кластерный анализ использует математические модели для обнаружения групп схожих клиентов, основываясь на наименьших различиях среди покупателей в каждой группе.
Кластерный анализ (англ. cluster analysis) — многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы.
Боль: кампании, как маркетинговая инвестиция, должны быть направлены на конкретную целевую группу.
Стандартный пул данных в датасете:
Более глубокое понимание клиентских сегментов достигается путем разработки 3D-модели кластеров на основе ключевых бизнес-показателей, таких как размещенные заказы (покупки), частота заказов, заказанные товары или изменение цен. Актуальность результатов кластеризации для бизнеса позволяет лицам, принимающим решения, выявлять проблемные кластеры, которые вынуждают продавца использовать больше ресурсов для достижения целевого результата. Затем можно сосредоточить свои маркетинговые и операционные усилия на правильных кластерах, чтобы обеспечить оптимальное использование ресурсов, включая:
Хотя возможности прогнозирования, предлагаемые кластеризацией, могут трансформировать результаты целевого маркетинга, кластеризация наиболее эффективна при использовании вместе с другими решениями для розничной аналитики. Ценность кластеризации продуктов особенно видна в очень разреженном датасете (наборе данных). В дополнение к повышению рентабельности маркетинговых инвестиций (ROMI) с точки зрения прибыльности клиентов, кластеризация продуктов может помочь ритейлерам таргетировать и активизировать клиентов из категории с невысокой платежеспособностью.
Подробнее о функционале модуля “Кластеризация” смотрите в обучающем видео.
Зачем нужен этот метод
С помощью кластерного анализа выявляются структурные группы для лучшего понимания информации. Кроме того, он позволяет упрощать обработку данных. Использование метода кластеризации актуально и для больших, и для малых объемов информации. Он способствует компактному хранению сведений и поиску атипичных объектов, не вошедших ни в одну группу.
Сферы применения
Алгоритмы кластеризации
Последовательность команд в общем виде выглядит следующим образом:
Алгоритмы кластерного анализа подразделяются на иерархические и неиерархические. При этом данные первого типа в конце генерируют иерархию кластеров. Любой из них может быть использован для интерпретации результатов.
Иерархические алгоритмы
Иерархические алгоритмы бывают:
При работе первых сначала каждый объект является отдельным кластером. Затем они объединяются до размещения всех их в одной группе.
Вторые работают по обратному принципу. Сначала все объекты находятся в одной группе. Затем постепенно разделяются, пока каждый не образует уникальный кластер.
Визуально иерархические алгоритмы представляют с помощью дендрограмм. На таких схемах видна последовательность объединения или разделения объектов.
Объединение кластеров
Когда каждый объект является отдельным кластером, расстояния между ними определяются выбранной мерой. При их объединении возникают затруднения в определении расстояния между ними. Поэтому необходимы правила, определяющие порядок этих действий.
Можно связать два кластера, когда два произвольных объекта из разных групп расположены максимально близко друг к другу. В таком случае расстояние определяют по правилу ближайшего соседа или методом одиночной связи. Так создаются волокнистые кластеры (соединенные только отдельными элементами, случайно расположенными рядом).
Метод полной связи или отдаленных соседей заключается в использовании наиболее удаленных объектов в разных группах.
Если расстояние между кластерами определяется как среднее значение между всеми парами объектов в них, применяется метод невзвешенного попарного среднего.
Ему аналогичен метод взвешенного попарного среднего. Отличие между ними лишь в том, что во втором случае размер кластеров используется в качестве весового коэффициента. По этой причине такой метод используется, если объемы групп различается.
При невзвешенном центроидном расчете берется расстояние между центрами тяжести кластеров.
Взвешенный центроидный метод (медиана) похож на предыдущий. Отличие в том, что при расчетах учитывают вес для определения различий в размерах кластеров. По этой причине при существенной разнице рациональнее использовать именно такой метод.
Метод Варда отличается от прочих, так как использует принципы дисперсионного анализа для определения расстояний между кластерами. Он сводит к минимуму сумму квадратов для любых двух групп, которые могут быть созданы на каждом этапе. Метод Варда эффективен, однако он стремится создавать кластеры небольшого размера.
Неиерархические алгоритмы
Методы иерархической кластеризации неприменимы при большом количестве наблюдений. Поэтому исследователи обращаются к неиерархической кластеризации.
Наиболее популярный алгоритм K-средних. Метод также именуют быстрым кластерным анализом.
Алгоритм K-средних строит группы, находящиеся на значительных расстояниях друг от друга. Они должны максимально отличаться. Выбор числа K обусловлен результатами ранее проведенных исследований, теоретическими соображениями или интуицией. Метод подходит для анализа небольшого объема данных. К достоинствам относятся:
Описание алгоритма K-средних
Таким способом все объекты распределяются по конкретным группам.
Итеративный процесс
Центрами становятся покоординатные средние кластеров. Объекты перераспределяются. Этот процесс длится до стабилизации кластерных центров или до достижения максимального числа итераций.
С позиции вычислений метод K-средних является обратным дисперсионным анализом. Работа начинается с K случайно отобранных кластеров. Далее меняется принадлежность объектов к ним для уменьшения изменчивости внутри групп и возрастания этого показателя между ними. В кластеризации данных методом K-средних перемещаются объекты из одних групп в другие. Это нужно выполнять для получения максимально значимого результата при дисперсионном анализе.
Интерпретация результатов
После получения результатов кластеризации методом быстрого анализа рассчитывают средние для каждой группы по каждому измерению. Это выполняется для оценки отличия кластеров друг от друга. Если анализ выполнен качественно, средние значения для большинства групп будут сильно различаться. Значения F-статистики, вычисленные для каждого измерения, это еще один индикатор качества дискриминации кластеров.
Обзор алгоритмов кластеризации данных
В своей дипломной работе я проводил обзор и сравнительный анализ алгоритмов кластеризации данных. Подумал, что уже собранный и проработанный материал может оказаться кому-то интересен и полезен.
О том, что такое кластеризация, рассказал sashaeve в статье «Кластеризация: алгоритмы k-means и c-means». Я частично повторю слова Александра, частично дополню. Также в конце этой статьи интересующиеся могут почитать материалы по ссылкам в списке литературы.
Так же я постарался привести сухой «дипломный» стиль изложения к более публицистическому.
Понятие кластеризации
Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны. Главное отличие кластеризации от классификации состоит в том, что перечень групп четко не задан и определяется в процессе работы алгоритма.
Меры расстояний
Итак, как же определять «похожесть» объектов? Для начала нужно составить вектор характеристик для каждого объекта — как правило, это набор числовых значений, например, рост-вес человека. Однако существуют также алгоритмы, работающие с качественными (т.н. категорийными) характеристиками.
Классификация алгоритмов
Объединение кластеров
Обзор алгоритмов
Алгоритмы иерархической кластеризации
Среди алгоритмов иерархической кластеризации выделяются два основных типа: восходящие и нисходящие алгоритмы. Нисходящие алгоритмы работают по принципу «сверху-вниз»: в начале все объекты помещаются в один кластер, который затем разбивается на все более мелкие кластеры. Более распространены восходящие алгоритмы, которые в начале работы помещают каждый объект в отдельный кластер, а затем объединяют кластеры во все более крупные, пока все объекты выборки не будут содержаться в одном кластере. Таким образом строится система вложенных разбиений. Результаты таких алгоритмов обычно представляют в виде дерева – дендрограммы. Классический пример такого дерева – классификация животных и растений.
Для вычисления расстояний между кластерами чаще все пользуются двумя расстояниями: одиночной связью или полной связью (см. обзор мер расстояний между кластерами).
К недостатку иерархических алгоритмов можно отнести систему полных разбиений, которая может являться излишней в контексте решаемой задачи.
Алгоритмы квадратичной ошибки
Задачу кластеризации можно рассматривать как построение оптимального разбиения объектов на группы. При этом оптимальность может быть определена как требование минимизации среднеквадратической ошибки разбиения:
где cj — «центр масс» кластера j (точка со средними значениями характеристик для данного кластера).
К недостаткам данного алгоритма можно отнести необходимость задавать количество кластеров для разбиения.
Нечеткие алгоритмы
Алгоритмы, основанные на теории графов
Суть таких алгоритмов заключается в том, что выборка объектов представляется в виде графа G=(V, E), вершинам которого соответствуют объекты, а ребра имеют вес, равный «расстоянию» между объектами. Достоинством графовых алгоритмов кластеризации являются наглядность, относительная простота реализации и возможность вносения различных усовершенствований, основанные на геометрических соображениях. Основными алгоритмам являются алгоритм выделения связных компонент, алгоритм построения минимального покрывающего (остовного) дерева и алгоритм послойной кластеризации.
Алгоритм выделения связных компонент
В алгоритме выделения связных компонент задается входной параметр R и в графе удаляются все ребра, для которых «расстояния» больше R. Соединенными остаются только наиболее близкие пары объектов. Смысл алгоритма заключается в том, чтобы подобрать такое значение R, лежащее в диапазон всех «расстояний», при котором граф «развалится» на несколько связных компонент. Полученные компоненты и есть кластеры.
Для подбора параметра R обычно строится гистограмма распределений попарных расстояний. В задачах с хорошо выраженной кластерной структурой данных на гистограмме будет два пика – один соответствует внутрикластерным расстояниям, второй – межкластерным расстояния. Параметр R подбирается из зоны минимума между этими пиками. При этом управлять количеством кластеров при помощи порога расстояния довольно затруднительно.
Алгоритм минимального покрывающего дерева
Алгоритм минимального покрывающего дерева сначала строит на графе минимальное покрывающее дерево, а затем последовательно удаляет ребра с наибольшим весом. На рисунке изображено минимальное покрывающее дерево, полученное для девяти объектов.
Путём удаления связи, помеченной CD, с длиной равной 6 единицам (ребро с максимальным расстоянием), получаем два кластера: и
Послойная кластеризация
Алгоритм послойной кластеризации основан на выделении связных компонент графа на некотором уровне расстояний между объектами (вершинами). Уровень расстояния задается порогом расстояния c. Например, если расстояние между объектами , то .
Алгоритм послойной кластеризации формирует последовательность подграфов графа G, которые отражают иерархические связи между кластерами:
,