Кластерный анализ

Август 9, 2022

Главная
Математика
Кластерный анализ

Содержание

2. ПОНЯТИЕ КЛАСТЕРИЗАЦИИ Во многих прикладных задачах измерять степень сходства объектов существенно проще, чем формировать признаковые описания.
3. ЗАДАЧИ И УСЛОВИЯ КЛАСТЕРИЗАЦИИ Понять структуру множества объектов, разбив его на группы схожих объектов. Упростить дальнейшую
4. ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ Распознавание образов
5. ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ Распознавание образов
6. ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ Группировка объектов
7. ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ Классификация результатов поиска
9. ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ Сегментация изображений
10. ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ Сегментация изображений
11. ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ Кластеризация результатов поиска — используется для «интеллектуальной» группировки результатов при поиске файлов, веб-сайтов, других
12. ОБЩИЙ АЛГОРИТМ КЛАСТЕРИЗАЦИИ Выбор меры близости; Выбор алгоритма кластеризации; Представление полученных результатов;
13. МЕРЫ БЛИЗОСТИ Коэффициент сходства (также мера сходства, индекс сходства) — безразмерный показатель, применяемый для количественного определения
14. Обобщенный алгоритм Ллойда (Generalized Lloyd) или алгоритм k-средних (k-means) O(k*n*?) Метод k-средних – это метод кластерного
15. Обобщенный алгоритм Ллойда (Generalized Lloyd) или алгоритм k-средних (k-means) O(k*n*?) 2. Относим наблюдения к тем кластерам,
16. Обобщенный алгоритм Ллойда (Generalized Lloyd) или алгоритм k-средних (k-means) O(k*n*?)
17. Кластеризация объединением ближайших соседей (pairwise nearest neighbor) O(n2) Дано: n точек xi в многомерном пространстве, которые
18. Задача – разбить эти точки на два кластера
20. Скачать презентацию

Слайд 2

ПОНЯТИЕ КЛАСТЕРИЗАЦИИ
Во многих прикладных задачах измерять степень сходства объектов существенно проще,

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

Слайд 3

ЗАДАЧИ И УСЛОВИЯ КЛАСТЕРИЗАЦИИ
Понять структуру множества объектов, разбив его на группы

схожих объектов. Упростить дальнейшую обработку данных и принятия решений, работая с каждым кластером по отдельности (стратегия «разделяй и властвуй»)
Сократить объём хранимых данных в случае сверхбольшой выборки, оставив по одному наиболее типичному представителю от каждого кластера
Выделить нетипичные объекты, которые не подходят ни к одному из кластеров. Эту задачу называют одноклассовой классификацией, обнаружением нетипичности или новизны (novelty detection)
Вычисление значений той или иной меры сходства (или различия) между объектами
Во всех этих случаях может применяться иерархическая кластеризация, когда крупные кластеры дробятся на более мелкие, те в свою очередь дробятся ещё мельче, и т. д. Такие задачи называются задачами таксономии (taxonomy). Результатом таксономии является не простое разбиение множества объектов на кластеры, а древообразная иерархическая структура. Вместо номера кластера объект характеризуется перечислением всех кластеров, которым он принадлежит, от крупного к мелкому.

Слайд 4

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Распознавание образов

Слайд 5

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Распознавание образов

Слайд 6

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Группировка объектов

Слайд 7

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Классификация результатов поиска

Слайд 8

Слайд 9

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Сегментация изображений

Слайд 10

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Сегментация изображений

Слайд 11

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Кластеризация результатов поиска — используется для «интеллектуальной» группировки результатов при

поиске файлов, веб-сайтов, других объектов, предоставляя пользователю возможность быстрой навигации, выбора заведомо более релевантного подмножества и исключения заведомо менее релевантного — что может повысить юзабилити интерфейса по сравнению с выводом в виде простого сортированного по релевантности списка.
Сегментация изображений — кластеризация может быть использована для разбиения цифрового изображения на отдельные области с целью обнаружения границ (edge detection) или распознавания объектов.
Интеллектуальный анализ данных (data mining) — кластеризация в Data Mining приобретает ценность тогда, когда она выступает одним из этапов анализа данных, построения законченного аналитического решения. Аналитику часто легче выделить группы схожих объектов, изучить их особенности и построить для каждой группы отдельную модель, чем создавать одну общую модель для всех данных. Таким приемом постоянно пользуются в маркетинге, выделяя группы клиентов, покупателей, товаров и разрабатывая для каждой из них отдельную стратегию.

Слайд 12

ОБЩИЙ АЛГОРИТМ КЛАСТЕРИЗАЦИИ
Выбор меры близости;
Выбор алгоритма кластеризации;
Представление полученных результатов;

Слайд 13

МЕРЫ БЛИЗОСТИ
Коэффициент сходства (также мера сходства, индекс сходства) — безразмерный показатель,

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

Слайд 14

Обобщенный алгоритм Ллойда (Generalized
Lloyd) или алгоритм k-средних (k-means) O(kn?)
Метод k-средних

– это метод кластерного анализа, цель которого является разделение n наблюдений из пространства Rn на k кластеров, при этом каждое наблюдение относится к тому кластеру, к центру (центроиду) которого оно ближе всего.
В качестве меры близости используется Евклидово расстояние.
Метод k-средних разделяет n наблюдений на k групп (или кластеров) (k ≤ m) чтобы минимизировать суммарное квадратичное отклонение точек кластеров от центроидов этих кластеров.
1. На первом этапе центроиды кластеров выбираются случайно или по определенному правилу (например, выбрать центроиды, максимизирующие начальные расстояния между кластерами).

Слайд 15

Обобщенный алгоритм Ллойда (Generalized
Lloyd) или алгоритм k-средних (k-means) O(kn?)
2. Относим

наблюдения к тем кластерам, чье среднее (центроид) к ним ближе всего. Каждое наблюдение принадлежит только к одному кластеру, даже если его можно отнести к двум и более кластерам.
3. Затем центроид каждого i-го кластера перевычисляется по следующему правилу:
Таким образом, алгоритм k-средних заключается в перевычислении на каждом шаге центроида для каждого кластера, полученного на предыдущем шаге.
Алгоритм останавливается, когда значения не меняются:
Неправильный выбор первоначального числа кластеров k может привести к некорректным результатам. Именно поэтому при использовании метода k-средних важно сначала провести проверку подходящего числа кластеров для данного набора данных.

Слайд 16

Обобщенный алгоритм Ллойда (Generalized
Lloyd) или алгоритм k-средних (k-means) O(kn?)

Слайд 17

Кластеризация объединением ближайших соседей (pairwise nearest neighbor) O(n2)
Дано: n точек xi

в многомерном пространстве, которые нужно разбить на k кластеров.
Считаем каждую точку отдельным кластером. Таким образом, алгоритм стартует с n кластеров. Центр каждого из этих кластеров совпадает с координатами точки, его образующей.
Находим два кластера, центры кластеров которых ближе всего друг к другу.
Объединяем эти два кластера в один и вычисляем координаты его центра, усреднением координат всех входящих в кластер точек.
Шаги 2-3 повторяются до тех пор, пока число кластеров не уменьшится до заданного числа k.
Как вариант, целевым может быть не число кластеров k, а расстояние между центрами объединяемых кластеров, которое должно быть не больше некого заданного порога.

Слайд 18

Кластерный анализ

Содержание

ПОНЯТИЕ КЛАСТЕРИЗАЦИИВо многих прикладных задачах измерять степень сходства объектов существенно проще,

ЗАДАЧИ И УСЛОВИЯ КЛАСТЕРИЗАЦИИПонять структуру множества объектов, разбив его на группы

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИРаспознавание образов

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИРаспознавание образов

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИГруппировка объектов

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИКлассификация результатов поиска

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИСегментация изображений

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИСегментация изображений

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИКластеризация результатов поиска — используется для «интеллектуальной» группировки результатов при

ОБЩИЙ АЛГОРИТМ КЛАСТЕРИЗАЦИИВыбор меры близости;Выбор алгоритма кластеризации; Представление полученных результатов;

МЕРЫ БЛИЗОСТИКоэффициент сходства (также мера сходства, индекс сходства) — безразмерный показатель,

Обобщенный алгоритм Ллойда (Generalized Lloyd) или алгоритм k-средних (k-means) O(k*n*?)Метод k-средних

Обобщенный алгоритм Ллойда (Generalized Lloyd) или алгоритм k-средних (k-means) O(k*n*?)2. Относим

Обобщенный алгоритм Ллойда (Generalized Lloyd) или алгоритм k-средних (k-means) O(k*n*?)

Кластеризация объединением ближайших соседей (pairwise nearest neighbor) O(n2)Дано: n точек xi

Задача – разбить эти точки на два кластера

Похожие презентации

ПОНЯТИЕ КЛАСТЕРИЗАЦИИ
Во многих прикладных задачах измерять степень сходства объектов существенно проще,

ЗАДАЧИ И УСЛОВИЯ КЛАСТЕРИЗАЦИИ
Понять структуру множества объектов, разбив его на группы

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Распознавание образов

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Распознавание образов

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Группировка объектов

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Классификация результатов поиска

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Сегментация изображений

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Сегментация изображений

ПРИМЕНЕНИЕ КЛАСТЕРИЗАЦИИ
Кластеризация результатов поиска — используется для «интеллектуальной» группировки результатов при

ОБЩИЙ АЛГОРИТМ КЛАСТЕРИЗАЦИИ
Выбор меры близости;
Выбор алгоритма кластеризации;
Представление полученных результатов;

МЕРЫ БЛИЗОСТИ
Коэффициент сходства (также мера сходства, индекс сходства) — безразмерный показатель,

Обобщенный алгоритм Ллойда (Generalized
Lloyd) или алгоритм k-средних (k-means) O(kn?)
Метод k-средних

Обобщенный алгоритм Ллойда (Generalized
Lloyd) или алгоритм k-средних (k-means) O(kn?)
2. Относим

Обобщенный алгоритм Ллойда (Generalized
Lloyd) или алгоритм k-средних (k-means) O(kn?)

Кластеризация объединением ближайших соседей (pairwise nearest neighbor) O(n2)
Дано: n точек xi