SAS EM. Лекция 3. Кластеризация (Лекции 2014)

SAS ENTERPRISE MINERКЛАСТЕРИЗАЦИЯC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .КОНЦЕПЦИЯ SEMMASampleC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .ExploreModifyModelAssessЧТО ЕСТЬ КЛАСТЕР?•Кластер: группа «похожих» объектов••••Кластерный анализ••Разбиение множество объектов на группы (кластеры)Тип моделей:•••«похожих» между собой в группе (внутриклассовое расстояние)«не похожих» на объекты других группОпределение неформальное, формализация зависит от метода«описательный» (descriptive) Data mining => одна из задач наглядное представление кластеров«прогнозный» (predictive) Data mining => разбиение на кластеры,а затем «классификация» новых объектовТип обучения:•всегда «без учителя» (unsupervised) => тренировочный набор неразмеченC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .ПРИМЕНЕНИЕ МЕТОДОВ КЛАСТЕРИЗАЦИИ ВЗАДАЧАХ АНАЛИЗА ДАННЫХ•Кластеризация ради кластеризации:Выявление и описание групп (человек не способен «осознать» более 10объектов в одной задаче, как обработать выборку с миллионами?)• «Сжатие» информации (особенно в обработке мультимедиа)• Построение различных поисковых индексов (сравниваем не со всеми, аначинаем с прототипов кластеров)••Мощнейшее средство предобработки данных:Дискретизация• Уменьшение размера выборки (от больших объемов к «реальным»)• Обработка пропущенных значений (инициализируем и итерационно«улучшаем» пропуски)• Поиск исключений и артефактов (что не в кластере, то под«подозрением»)•C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .КАЧЕСТВО КЛАСТЕРИЗАЦИИ•••Хороший метод кластеризации находит кластеры•c высоким «внутриклассовым» сходством объектов•и низким «межклассовым» сходством объектовОценка качества кластеризации (нет понятия «точность»)•необходима, так как влияет на выбор параметров метода•определяется либо экспертом – субъективная величина•либо «перекрестной» проверкой целевой функции кластеризацииКачество кластеризации зависит:•от метода кластеризации•от меры сходства (или расстояния)C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .ИЕРАРХИЧЕСКАЯ КЛАСТЕРИЗАЦИЯStep0abcdeStep4•Step1Step2Step3Step4восходящаяagglomerativeababcdecdedeStep3Step2Step1Step0нисходящаяdivisiveИспользуется только матрица сходства (различия) и не требуетсядополнительных параметров (например, числа кластеров)• «Пошаговое» объединение ближайших кластеров (восходящая) илиразбиение наиболее удаленных (нисходящая)C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .ПРЕДСТАВЛЕНИЕ ИЕРАРХИЧЕСКИХКЛАСТЕРОВ - ДЕНДРОГРАММА••••C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .бинарное дерево,описывающее все шагиразбиенияКорень – общий кластер,листья - элементы«Высота» ветвей (допересечения) – порограсстояния «склейки»(«разделения»)Результат кластеризации– «срез» дендрограммыИЕРАРХИЧЕСКАЯ КЛАСТЕРИЗАЦИЯ - DEMOC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .УРОВНИ КЛАСТЕРИЗАЦИИC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .ОЦЕНКА БЛИЗОСТИ КЛАСТЕРОВ•Расчет расстояния на основе попарныхрасстояний между элементами различныхкластеров:•••••Полное связывание: наибольшее попарноерасстояние. Дает компактные сферическиекластеры.Среднее связывание: усредненное попарноерасстояние. Редко используется.Единственное связывание: наименьшеепопарное расстояние. Дает «растянутые» кластерысложной формы.Центроидное связывание: расстояние междуцентрами (мат.

ожидание) кластеров.Другие методы (например метод Ward’а –минимизирует внутрикластерные дисперсии илидругую целевую функцию)C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .ПримерA B C D EA 0 1 2 2 3B 1 0 2 4 3C 2 2 0 1 5D 2 4 1 0 3E 3 3 5 3 0C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .ОПРЕДЕЛЕНИЕ ЧИСЛА КЛАСТЕРОВ•SAS Cubic Clustering Criterion (CCC) (Sarle, 1983)•Основная идея: сравнение R2 (для отображения матрицы данныхс помощью индикаторной матрицы в прототипы кластеров) длязаданной модели кластеризации с E(R2) для равномернораспределенного множества прототипов кластеров (как наихудшийвозможный вариант):1  E ( R 2 ) CCC  ln K2  1  Rclust C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .•КЛАСТЕРИЗАЦИЯ НА ОСНОВЕ СТРОГОЙГРУППИРОВКИ (PARTITIONING):Основная задача:•Найти такое разбиение C исходного множества X из N объектовна K непересекающихся подмножеств Ck, покрывающих X, чтобывнутриклассовое расстояние было минимальным:min•Ci C j  , Ci  XТочное решение – перебор с отсечением••iK1 xCi  xCi d ( x, x)метод «ветвей и границ», но число комбинаций неприемлемодаже для 100 объектов:KЭвристические методы:•K N1K i S(N , K ) ( 1)   KK ! i 1iK-means (прототип кластера – мат. ожидание m), K-medoids(прототип кластера – средний элемент)min•ищется локальный минимумC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .Ci C j  , Ci  XiK1 xCi d (mi , x)МЕТОД K-MEANS В ENTERPRISE MINER•Шаг 0. Инициализация:••Шаг 1. Поиск центров:••Для всех K кластеровmi xxCixДля всех N объектовd (mi , x ) и K кластеровxCiДемонстрация на данных censusC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .CiШаг 3. Выбор ближайшего кластера:x  Ci  i  min d (m j , x )j•CiШаг 2. Расчет расстояний до центров:••произвольное разбиение на заданноечисло кластеров K (где значение Kвыбирается по ССС на основеиерархической кластеризации) поЕсли были перестановки, то Шаг 1.SAS ENTERPRISE MINERПРЕДОБРАБОТКА ДАННЫХC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .КОНЦЕПЦИЯ SEMMASampleC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .ExploreModifyModelAssess«ПРОКЛЯТИЕ» РАЗМЕРНОСТИ1–D2–DEp(r)=r1/p• E10(0.01)=0.63• E10(0.1)=0.8•3–DC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .ПРОБЛЕМЫ ВХОДНЫХ ПЕРЕМЕННЫХЗависимостьНе релевантностьx4x20.70Input x2 has the0.60same information asinput x1.0.500.40x1x3Выхода два: либо преобразование либо исключениеC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d ....СОРАЩЕНИЕ РАЗМЕРНОСТИДано: входные переменные {x1,…,xn} и выходная (числовая или бинарная) yЗадача: оставить только значимые и независимые xiРаботает в два этапа:1.Уделяет все xi, где R2(xi)<T1 удаление незначимых2.Forward stepwise регрессия f(xi1,…xik) покаR2(f(xi1,…xik))-R2(f(xi1,…xik-1))>T2удаление зависимыхПреобразования переменных:•Дискретизация непрерывных (на 16 интервалов)•Группировка категориальныхC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .КОНЦЕПЦИЯ SEMMASampleC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .ExploreModifyModelAssessОБЩАЯ ИДЕЯ PCA•Cтроится новый базис (линейное преобразование исходногопространства) такой, что:Центр координат совпадает с мат. ожиданием наблюдений• Первый вектор направлен таким образом, что дисперсия вдоль негобыла максимальнойD U  V• Каждый последующий вектор ортогонален предыдущим и направлен понаправлению максимальной дисперсии• Последние компоненты – не важны!!!•P N•Формально:•Два эквивалентных подхода:SVD разложение матрицы данных• Собственные значения ковариационной матрицы•C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .P PP NN NПОИСК СОБСТВЕННЫХ ЗНАЧЕНИЙ ИСОБСТВЕННЫХ ВЕКТОРОВ КОВАРИАЦИОННОЙМАТРИЦЫ В PCA•Рассчитаем ковариационную матрицу:•••••Ковариация = 0 – независимы cov( x1 , x1 ) cov( x1 , x 2 ) ... cov( x1 , x d ) Ковариация > 0 – вместе растут 21222d cov(x,x)cov(x,x)...cov(x,x)и убываютC............Ковариация < 0 – противофазаПроблема с.зн.:d1d2dd cov( x , x ) cov( x , x ) ... cov( x , x ) С*v=λ*vnX i  X  Yi  Y i 1решение: поиск корнейcov( X , Y ) |С - λ . I|=0n  1матрица положительно определенная – есть вещественные корниРезультат:• λ – дисперсии• с.в. – главные компонентыC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ В PCAD=SUfactorsvariablesVTfactorssig.variablessignificantsamplesC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .samplesnoisesignificantnoisefactorsnoisefactorsSVD РАЗЛОЖЕНИЕ И ОБРАТНАЯ ПРОЕКЦИЯX nm  U nn DnmVmTm•SVD разложение матрицы X:•SVD приближение (метод главных компонент):••отбрасываются с.в., соотв. наименьшим с.з.остается p-я часть главных с.в., которые характеризуют основныезависимости в XTmin X  U p D pV pU p , D p ,V p•с их помощью приближается исходная матрица:X (l 1)  V pV p X (l )TC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .КОНЦЕПЦИЯ SEMMASampleC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .ExploreModifyModelAssessПРОПУЩЕННЫЕ ЗНАЧЕНИЯ•Не все значения атрибутов известны или достоверны••Причины появления пропущенных значений••••••Наиболее важная задача, так как многие к ней сводятся(удаление шума, не консистентностей и т.д.)Ошибки «оборудования» и/или ПО при получении данных отдатчиков и из экспериментовУдаление несогласованных значений атрибутовПросто не введены в систему из-за халатности или ошибкиЧасть данных может быть опциональна с точки зрения бизнеспроцессов организации, но важна для анализаНе хранится правильная история изменений – невозможноправильно определить значение на момент анализаПропущенные данные:••Ведут к неточным результатам анализаДопускаются не всеми алгоритмами анализаC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .