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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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 .

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций