🗊Презентация Кластерный анализ

Тема лекции: Кластерный анализ

ПОНЯТИЕ КЛАСТЕРИЗАЦИИ Во многих прикладных задачах измерять степень сходства объектов существенно проще, чем формировать признаковые описания. Например, гораздо легче сравнить две фотографии и сказать, что они принадлежат одному человеку, чем понять, на основании каких признаков они схожи. Задача классификации объектов на основе их сходства друг с другом, когда принадлежность обучающих объектов каким-либо классам не задаётся, называется задачей кластеризации. Кластеризация – это процесс автоматического разбиения некоторого множества элементов на группы на основе степени их схожести (кластеры). Кластерный анализ (cluster analysis) — многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы. Задача кластеризации относится к статистической обработке, а также к широкому классу задач обучения без учителя.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кластеризация медианным сечением O(n)