Лекция (4)

Лекция 4:кластеризацияЧто есть кластер?Кластер: группа «похожих» объектов«похожих» между собой в группе (внутриклассовое расстояние) «не похожих» на объекты других групп Определение неформальное, формализация зависит от методаКластерный анализРазбиение множество объектов на группы (кластеры)Тип моделей:«описательный» (descriptive) Data mining => одна из задач - наглядноепредставление кластеров «прогнозный» (predictive) Data mining => разбиение на кластеры, а затем«классификация» новых объектовТип обучения:всегда «без учителя» (unsupervised) => тренировочный набор не размеченЭтапы кластерного анализа:Подготовка данных Применение алгоритма Визуализация и интерпретация результатовПрименение методов кластеризациив задачах анализа данныхКластеризация ради кластеризации:Выявление и описание групп (человек не способен «осознать» более 10объектов в одной задаче, как обработать выборку с миллионами?) «Сжатие» информации (особенно в обработке мультимедиа) Построение различных поисковых индексов (сравниваем не со всеми, аначинаем с прототипов кластеров)Мощнейшее средство предобработки данных:Дискретизация (от чисел к «понятиям») Уменьшение размерности (от больших объемов к «реальным») Обработка пропущенных значений (инициализируем и итерационно«улучшаем» пропуски) Поиск исключений и артефактов (что не в кластере, то под «подозрением»)Предварительный этап перед классификацией:Стратифицированные модели Поиск «кандидатов» классов для классификации «с учителем» Поиск состояний для марковских моделей прогнозирования Поиск шаблонов правил (проекция кластеров)Прикладное применение методовкластеризацииПожалуй, самая «востребованная» задача в Data Mining«Экономика»:Таксономии и обработка результатов экспериментов илиисследованийОбработка мультимедиа:«Сегментация» рынков, клиентов, товаров, услуг«Наука» и медицина:Почему? Потому что получаем «что-то полезное» практически из«ничего»«Сжатие» и «сегментация» изображений, видеоряда, звукаЭлектронные текстовые документы:Рубрикация и индексированиеКачество кластеризацииХороший метод кластеризации находит кластерыc высоким «внутриклассовым» сходством объектови низким «межклассовым» сходством объектовОценка качества кластеризации (нет понятия «точность»)необходима, так как влияет на выбор параметров методаопределяется либо экспертом – субъективная величиналибо «перекрестной» проверкой целевой функции кластеризацииКачество кластеризации зависит:от метода кластеризацииот меры сходства (или расстояния)Требования к методу кластеризацииМасштабируемостьПоддержка различных типов атрибутов и структур данныхВозможность находить кластеры сложной формыОтсутствие обязательных требований к наличию априорных знанийо выборке (например, о распределениях)Устойчивость к «шуму» и выбросамВозможность работы с высокой размерностью и с большойвыборкойВозможность включать пользовательские ограничения изависимостиИнтерпретируемость и наглядность (прототипы, границы, правила,функции принадлежности и т.п.)Интуитивность параметров кластеризацииПодготовка данных длякластеризацииОтбор наблюденийЧто я разбиваю на кластеры? Решаемые задачи: исключить выборсы (узел Filter), уменьшитьвыборку (узел Sample)Отбор и трансформация переменныхКакие характеристики объектов важны? Выбирает эксперт. Переменные коррелируют? (узлы PCA и Variable Clustering) Распределения переменных симметричны? (узел Transform)Стандартизация переменныхСравнимы ли масштабы переменных? Делается автоматически узлом кластеризацииФильтрация данныхЦель – удаление из выборки артефактов и выбросовПравила фильтрации задаются для отдельных переменных:•••Ручные – задаютсядопустимые значенияпеременных (диапазоны длячисловых, список длякатегориальных)Редкие значения длякатегориальныхНетипичные значения длячисловых (задаетсядопустимое отклонение отмат.

ожидания илидопустимое отклонение отмедианы или экстремальныепроцентили и другое).Сокращение обучающей выборки –случайная выборка (Sampling)Цель – выбрать «представительное» подмножество примеров:В идеале с тем же распределением Просто случайная выборка работает плохо – не удается сохранитьхарактеристики всего набораАдаптивные методы случайной выборки:В соответствии с «грубой» моделью, например кластерной Случайная выборка в рамках экспертных «срезов» (условия насрезы формируются аналитиком) Случайная выборка в рамках «срезов», построенных автоматическипо какому-либо классу, высоко селективному атрибуту или ихкомбинации Основная особенность – выборка в рамках среза или кластерапропорциональна размеру среза или кластераСокращение обучающей выборки (SAMPLING) –метод стратификацииЗадается процент исходной выборкиДля выбранной категориальной переменной (переменнаястратификации) строится частотная диаграмма (для числовойнеобходима предварительная дискретизация)Наблюдения случайным образом выбрасываются так, чтобы сохранитьраспределение переменной стратификацииПодготовка данных для кластеризации«Сырые» данныеКластерная/стратифицированнаяслучайная выборкаFilteringClusteringSamplingFilteringИсходные данныеМатрица признаков:ЧисловыеБинарныеНоминальные (категориальные)Упорядоченные шкалыНелинейные шкалы x11 ...x i1 ...x n1Матрица различия (или сходства):  0 «Естественные» расстояния d(2,1)предметной области d(3,1) Экспертные оценки(противоречивы, нетранзитивны,  :недостоверны)d ( n,1)...x1f............xif...............

xnf......0d ( 3,2) 0::d ( n,2) ...x1p ... xip ... xnp ... 0Числовые значения – приведение кблизким шкаламНормализация на абсолютное отклонение более робастно(устойчиво к ошибкам), чем нормализация на стандартноеотклонение:Среднее абсолютное отклонениеs f  1n (| x1 f  m f |  | x2 f  m f | ... | xnf  m f |)гдеz-scorexif  m fzif sfОбычная нормализация:std f 1m f  n  x  x  ... x 1f2fnf.xif  m fyif std f1 ( x  m )2  ( x  m )2  ...  ( x  m )2 n 1  1 ff2ffnff Меры сходства и различия для исходныхданных с числовыми атрибутамиОбычно строится на основе расстояния:d(i,j)  0, d(i,i) = 0, d(i,j) = d(j,i), d(i,j)  d(i,k) + d(k,j)Наиболее популярно расстояние Минковского:d (i, j)  q (| x  x |q  | x  x |q ... | x  x |q )i1 j1i2j2ipjpгде i = (xi1, xi2, …, xip) и j = (xj1, xj2, …, xjp) - два объекта с pчисловыми атрибутами, q - положительное целое числоq = 2 - Евклидово (не фамилия, но имя) расстояние:d (i, j)  (| x  x |2  | x  x |2 ... | x  x |2 )i1j1i2j2ipjpq = 1, d – расстояние «Манхэтен»:d (i, j) | x  x |  | x  x | ... | x  x |i1 j1 i2 j2ip jpБинарные атрибутыРасстояние Хэмминга = сумма единиц после XORТаблица «сопряженных признаков»( M10  M 01 )В ячейках – число совпадающих и несовпадающих значений из pбинарных атрибутов для объектов j и iObject j101Object i 0sumM 11M 10M 01M 00M 11M01M 10MsumM MM M1011100100M 00  M 01  M 10  M 11M 10  M 01 На основе коэффициента совпаденияM 11  M 01  M 10  M 00 для симметричных атрибутов (значения равнозначны)d (i, j ) На основе коэффициента Jaccardd (i , j ) для асимметричных атрибутов (единица важнее)M 10  M 01M 11  M 01  M 10ПримерИмяПолЖарКашель Test-1Test-2Test-3Test-4JackMaryJimMFMYYYNNPNNNNPNNNNPPNпол - симметричный атрибутостальные ассиметричныепусть Y и P соответствует 1, а N соответствует 001d ( jack , mary )  0.332 0111d ( jack , jim )  0.671111 2d ( jim , mary )  0.7511 2Категориальные атрибуты и шкалыКатегориальные атрибуты:много значений, например, цвета: red, yellow, blue, greenПодход 1: простое совпадениеM - число совпадений, p - число переменных (аналог нормированногорасстояния Хэмминга) d (i, j )  p  mpПодход 2: кодирование бинарными векторамиДля каждого значения категориального атрибута создаетсяотдельная бинарная переменная: один категориальный атрибут с Mвозможными значениями => бинарный вектор длины MКатегориальные упорядоченные шкалы:Могут быть и дискретными и непрерывнымиПорядок важен, «разница» - нет = рангиcводятся к числовым: заменить xif на его ранг, отобразить на [0, 1] снормировкой:rif 1zif rif {1,..., M f }Mf1затем использовать стандартные расстоянияПреобразование переменныхПростые преобразования:Функции от исходной (log, exp, …), дискретизации (на бакеты и квантили),объединение редких категориальных значений и т.д.Адаптивные преобразования – перебор простых и выбор лучшего понекоторому криетрию:Нормальность распределения результата, корреляция с откликом,Оптимальная дискретизация и т.д.Основные типы алгоритмовкластеризацииИерархические:На основе группировки (partitioning):Направленный перебор вариантов разбиения исходного множестваобъектов, выбор лучшего по некоторому критериюk-means, k-medoidsНа основе связности:Создается иерархическая декомпозиция исходного множестваобъектов в соответствии с некоторой стратегией «объединения»(восходящая кластеризация) или «разбиения» (нисходящая)Кластеры ищутся в виде связных областей с помощью локальнойоценки числа ближайших соседейМодель-ориентированые (статистические):Выбирается некоторая гипотеза (параметрическая модель) оструктуре кластеров и находятся, параметры, наилучшим образомприближающие эту модельИерархическая кластеризацияStepStepStepStepStep01234abcdeabcdecdedeStepStepStepStepStep43210Параметры:abвосходящаяagglomerativeнисходящаяdivisiveИспользуется только матрица сходства (различия) и не требуетсядополнительных параметров (например, числа кластеров)Процесс:«Пошаговое» объединение ближайших кластеров (восходящая)или разбиение наиболее удаленных (нисходящая)Представление иерархическихкластеров - Дендрограммабинарное дерево,описывающее все шагиразбиенияКорень – общий кластер,листья - элементы«Высота» ветвей (допересечения) – порограсстояния «склейки»(«разделения»)Результаткластеризации – «срез»дендрограммыИерархическая кластеризация - DemoУровни кластеризацииОценка близости кластеровРасчет расстояния на основе попарныхрасстояний между элементами различныхкластеров:Полное связывание: наибольшее попарноерасстояние.