60
правок
Изменения
Major: cluster analysis definition added
'''Кластеризация''' (англ. ''cluster analysis'') {{---}} задача группировки множества объектов на подмножества ('''кластеры''') таким образом,
чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.
Задача кластеризации относится к классу задач обучения без учителя.
== Постановка задачи кластеризации ==
Пусть <tex>X</tex> {{---}} множество объектов, <tex>Y</tex> {{---}} множество идентификаторов (меток) кластеров.
На множестве <tex>X</tex> задана функция расстояния между объектами <tex>\rho(x,x')</tex>.
Дана конечная обучающая выборка объектов <tex>X^m = \{ x_1, \dots, x_m \} \subset X</tex>.
Необходимо разбить выборку на подмножества (кластеры), то есть каждому объекту <tex>x_i \in X^m</tex> сопоставить метку <tex>y_i \in Y</tex>,
таким образом чтобы объекты внутри каждого кластера были близки относительно метрики <tex>\rho</tex>, а объекты из разных кластеров значительно различались.
{{Определение
|definition =
'''Алгоритм кластеризации''' — это функция <tex>a\colon X\to Y</tex>, которая любому объекту <tex>x\in X</tex> ставит в соответствие идентификатор кластера <tex>y\in Y</tex>.
}}
Множество <tex>Y</tex> в некоторых случаях известно заранее, однако чаще ставится задача
определить оптимальное число кластеров, с точки зрения того или иного ''критерия качества'' кластеризации.
Кластеризация (обучение без учителя) отличается от классификации (обучения с учителем) тем,
что метки объектов из обучающей выборки <tex>y_i</tex> изначально не заданы, и даже может быть неизвестно само множество <tex>Y</tex>.
Решение задачи кластеризации объективно неоднозначно по ряду причин:
* не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области.
* число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют ввести этот параметр.
* результат кластеризации существенно зависит от метрики. Однако существует ряд рекомендаций по выбору для определенных классов задач.
== Типология задач кластеризации ==
=== Типы входных данных ===
* Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками (англ. ''features''). Признаки могут быть как числовыми, так и нечисловыми.
* Матрица расстояний между объектами. Каждый объект описывается расстоянием до всех объектов из обучающей выборки.
Вычисление матрицы расстояний по признаковому описанию объектов может быть выполнено бесконечным числом способов в
зависимости от определения метрики между объектами. Выбор метрики зависит от обучающей выборки и поставленной задачи.
=== Цели кластеризации ===
* Классификация объектов. Попытка понять зависимости между объектами путем выявления их кластерной структуры. Разбиение выборки на группы схожих объектов упрощает дальнейшую обработку данных и принятие решений, позволяет применить к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»). В данном случае стремятся уменьшить число кластеров для выявления наиболее общих закономерностей.
* Сжатие данных. Можно сократить размер исходной выборки, взяв один или несколько наиболее типичных представителей каждого кластера. Здесь важно наиболее точно очертить границы каждого кластера, их количество не является важным критерием.
* Обнаружение новизны (обнаружение шума). Выделение объектов, которые не подходят по критериям ни в один кластер. Обнаруженные объекты в дальнейшем обрабатывают отдельно.
=== Методы кластеризации ===
* Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике.
* Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности.
** Алгоритм <tex>k-</tex>средних (англ. ''<tex>k-</tex>means)
** EM-алгоритм
* Иерархические алгоритмы кластеризации. Упорядочивание данных путем создания иерархии вложенных кластеров.
== Источники информации ==
* [https://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7 Википедия {{---}} Кластерный анализ]
* [https://en.wikipedia.org/wiki/Cluster_analysis Wikipedia {{---}} Cluster analysis]
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F MachineLearning {{---}} Кластеризация]
* [https://ru.wikipedia.org/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F Википедия {{---}} Иерархическая кластеризация]
[[Категория: Машинное обучение]]
чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.
Задача кластеризации относится к классу задач обучения без учителя.
== Постановка задачи кластеризации ==
Пусть <tex>X</tex> {{---}} множество объектов, <tex>Y</tex> {{---}} множество идентификаторов (меток) кластеров.
На множестве <tex>X</tex> задана функция расстояния между объектами <tex>\rho(x,x')</tex>.
Дана конечная обучающая выборка объектов <tex>X^m = \{ x_1, \dots, x_m \} \subset X</tex>.
Необходимо разбить выборку на подмножества (кластеры), то есть каждому объекту <tex>x_i \in X^m</tex> сопоставить метку <tex>y_i \in Y</tex>,
таким образом чтобы объекты внутри каждого кластера были близки относительно метрики <tex>\rho</tex>, а объекты из разных кластеров значительно различались.
{{Определение
|definition =
'''Алгоритм кластеризации''' — это функция <tex>a\colon X\to Y</tex>, которая любому объекту <tex>x\in X</tex> ставит в соответствие идентификатор кластера <tex>y\in Y</tex>.
}}
Множество <tex>Y</tex> в некоторых случаях известно заранее, однако чаще ставится задача
определить оптимальное число кластеров, с точки зрения того или иного ''критерия качества'' кластеризации.
Кластеризация (обучение без учителя) отличается от классификации (обучения с учителем) тем,
что метки объектов из обучающей выборки <tex>y_i</tex> изначально не заданы, и даже может быть неизвестно само множество <tex>Y</tex>.
Решение задачи кластеризации объективно неоднозначно по ряду причин:
* не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области.
* число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют ввести этот параметр.
* результат кластеризации существенно зависит от метрики. Однако существует ряд рекомендаций по выбору для определенных классов задач.
== Типология задач кластеризации ==
=== Типы входных данных ===
* Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками (англ. ''features''). Признаки могут быть как числовыми, так и нечисловыми.
* Матрица расстояний между объектами. Каждый объект описывается расстоянием до всех объектов из обучающей выборки.
Вычисление матрицы расстояний по признаковому описанию объектов может быть выполнено бесконечным числом способов в
зависимости от определения метрики между объектами. Выбор метрики зависит от обучающей выборки и поставленной задачи.
=== Цели кластеризации ===
* Классификация объектов. Попытка понять зависимости между объектами путем выявления их кластерной структуры. Разбиение выборки на группы схожих объектов упрощает дальнейшую обработку данных и принятие решений, позволяет применить к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»). В данном случае стремятся уменьшить число кластеров для выявления наиболее общих закономерностей.
* Сжатие данных. Можно сократить размер исходной выборки, взяв один или несколько наиболее типичных представителей каждого кластера. Здесь важно наиболее точно очертить границы каждого кластера, их количество не является важным критерием.
* Обнаружение новизны (обнаружение шума). Выделение объектов, которые не подходят по критериям ни в один кластер. Обнаруженные объекты в дальнейшем обрабатывают отдельно.
=== Методы кластеризации ===
* Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике.
* Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности.
** Алгоритм <tex>k-</tex>средних (англ. ''<tex>k-</tex>means)
** EM-алгоритм
* Иерархические алгоритмы кластеризации. Упорядочивание данных путем создания иерархии вложенных кластеров.
== Источники информации ==
* [https://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7 Википедия {{---}} Кластерный анализ]
* [https://en.wikipedia.org/wiki/Cluster_analysis Wikipedia {{---}} Cluster analysis]
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F MachineLearning {{---}} Кластеризация]
* [https://ru.wikipedia.org/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F Википедия {{---}} Иерархическая кластеризация]
[[Категория: Машинное обучение]]
