Лекция 11 (2012 Лекции МОТП (Сенько))
Описание файла
Файл "Лекция 11" внутри архива находится в папке "2012 Лекции МОТП (Сенько)". PDF-файл из архива "2012 Лекции МОТП (Сенько)", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
МАТЕМАТИЧЕСКИЕОСНОВЫ ТЕОРИИПРОГНОЗИРОВАНИЯЛекторСенько Олег ВалентиновичЛекция 11Методы кластерного анализаВажное прикладное значение имеют методы анализа данных,связанные с теорией распознавания. К их числу относятсяметодыкластерногоанализамногомерных данных.иметодывизуализацииЦелью методов кластерного анализаявляется разбиение выборок многомерных данных на группыобъектов близкихвсмысле некоторой заданной мерысходства. Такие компактные группы называются кластерами,классами или таксонами.Методы кластерного анализа называют также методамиобучениябезтаксономииучителя,автоматическойгруппировкиилиМетоды кластерного анализаМетоды кластерного анализа могут использоваться в качествавспомогательных инструментов при решении задачпрогнозирования или распознавания.
Так с помощьюкластеризации могут отбираться эталонные объекты. Однаконередко кластеризация может иметь самостоятельное значение.Можно выделить задачи кластерного анализа, для которых числокластеров задано, а также задачи, в которых число кластеровследует определить в ходе решения кластеризации.Методы кластерного анализаОдним из наиболее известных методов кластеризации являетсяалгоритм k внутригрупповых средних. Предположим, что у насзадана выборка многомерных векторов-объектовSini {x1,, xm} . Алгоритм находит такие кластеры, дляобъектов которых центр «своего кластера» будет ближе централюбого «чужого кластера».На начальном этапе произвольным0G{Gобразом выбирается начальная кластеризация01,0(mс содержанием объектов1,, mk0 ) соответственно., Gk0}Методы кластерного анализаlПредположим, что на (l-1)-ом шаге получены группы Gl {G1 ,На l-ом Для каждой из групп Gil вычисляется центр1x lmili x , i 1,j,kx j GilПусть (x, y) неотрицательная функция близости междувекторами x, yПроизвольный объект x jпереносится в группу Gil , если (x j , xil ) (x j , xil ), i {1, , k} \ i ., Gkl }Методы кластерного анализаВ результате мы получаем группыGl 1 {G1l 1,, Gkl 1} ипереходим к (l+1)-ому шагу .
Процесс останавливается, если накаком-то шаге оказывается, что xil xil 1 , i 1,,kДругим методом кластеризации, основанным на итерационнойпроцедуре является алгоритм Форель, основанный на. движениигипершаров фиксированного радиуса в сторону мест«сгущения»объектов. Пусть фиксировано некоторое положительное число R. Выбирается случайный вектор x j* Sini игипершар радиуса R с центром в z1 x j* : R1 {x : (x, z1 ) R}Методы кластерного анализаПолагаемG1 Sini R1 Вычисляется центр новой сферы1z2 x j и группа G2 Sini R 2 , где R 2 {x : (x, z 2 ) R}| G1 | x j G1Процесс заканчивается на некотором шаге l * при выполненииусловия Gl* 1 Gl* . Полученное множество объектовfобъявляется первым кластером G1 .
Оно исключается извышеописанная процедура повторяется относительнооставшейся части выборки.SiniМетоды кластерного анализаТаким образом последовательно находятся кластерыG1f , G2f ,, Gkf*Процесс кластеризации заканчивается на k * -ой итерацииk*при достижении условияSini \Gi f i 1• Полученное число кластеров зависит от выбора радиуса R,который является параметром алгоритма..Методы кластерного анализаМетод иерархической группировки позволяет не толькоосуществить кластеризацию с заранее выбранным числомклассов и выявить иерархию кластеров.На начальном этапе в качестве кластеров рассматриваютсяотдельные объекты выборки Sini .
Дальнейшая кластеризацияпроизводится с используется функции близости междукластерами, которая задаётся на основе функции близостимежду векторными описаниями объектов.Методы кластерного анализаНа практике используется несколько типов функций близостимежду кластерами Gi и Gi :min (Gi , Gi ) min (x , x )- минимальное расстояние междуx Gi ,x Giобъектами из двух кластеров;max (Gi , Gi ) max (x , x ) - максимальное расстояние междуx Gi ,x Gi объектами из двух кластеров;c (Gi , Gi ) ( xi , xi ) - расстояние между центрами двухкластеров;Методы кластерного анализа|Gi | |Gi |- среднее1 av (Gi , Gi ) (x , x )| Gi | | Gi | 1 1расстояние между объектами двух классов.На втором шаге два ближайших кластера объединяются в один.Процесс объединения повторяется до нахождения l кластеров.Для остановки процесса объединения кластеров могут бытьиспользованы дополнительные условия, задаваемыеэкспертом, и связанные со спецификой конкретной задачи.В этом случае число кластероврешения.устанавливается в ходеМетоды кластерного анализаИспользуются также методы кластеризации, основанные напоиске разбиений Sini , для которых достигают максимумаспециальные функционалы качества.
Так качестворазбиенияG {G1 , , Gk } может быть описано спомощью функционала внутренних дисперсий FVS (G)представляющего собой взвешенную сумму среднихотклонений от центра внутри внутри каждой из группk|Gi | (x j , xi )i 1x j Gi| Gi |FVS (G) {| Gi |[ k|Gi |]} (x j , xi )i 1 x j GiМетоды кластерного анализаНетрудно видеть, что “вес” каждой из групп пропорционаленчислу объектов в ней.Sinik группПоскольку число всевозможныхразбиенийнаkmоценивается какполный перебор разбиений здесьk!заведомо исключен.
Поэтому обычно применяютметоды частичного перебора с использованием случайноговыбора начальных разбиений и последующей локальнойоптимизациейМетоды кластерного анализаВ методах локальной оптимизации (для определенности,минимизации) строится последовательность разбиений• G ,G ,12, Gl ,, для которыхF (G1 ) F (G2 ),, F (Gl ) F (Gl 1 ),а разбиение Gl 1 вычисляется непосредственно поGl {G1l ,, Gkl }путем его «локального» изменения – переносанекоторого объектов из одного кластера в другой.Методы кластерного анализаlИщется такой объектx j* (l ) , при переносе которого из кластера G( содержащего x j (l ) в разбиении Gl ) в некоторый кластер*Gl уменьшение функционала F максимально.
Средивсевозможных переносов такого рода.•В результате разбиение Gl 1 отличается от Gl толькосоставом кластеров с номерами и . Процесс• завершается, когда никакой последующий перенос неуменьшает функционал или достигнуто указанное пользователеммаксимальное число итерацийМетоды кластерного анализаПустьврезультатепримененияразнообразныхметодовкластеризации получено множество различных решений дляодних и тех же данных. При отсутствии внешнего критерия,выбор одного решения из данного множества кластеризацийможет быть не ясен. Поэтому представляет интерес применениеметодов обработки полученных множеств кластеризаций сцельюпостроенияколлективныхрешений,предпочтительных и обоснованных, чем полученныеотдельными алгоритмами кластеризации.болееРешение задачи кластерногоанализа коллективами алгоритмовКластеризацию выборкиG1 ,Sini {x1, , xm} , включающую кластеры, Gk можно описать с помощью информационной матрицы|| ji ||mk , где ji 1 , если x j Gi и ji 0 в противномслучае.Наличие нескольких единиц в одной строке соответствуетпринадлежности объекта сразу нескольким кластерам.
Нулеваястрока означает отказ от кластеризации соответствующегообъекта.Решение задачи кластерногоанализа коллективами алгоритмовОпределение 1. Информационные матрицы I || ji ||mkI || ji ||mkиназываются эквивалентными, если они равны сточностью до перестановки столбцов.Произвольная информационная матрица I || ji ||mk определяеткласс всех эквивалентных ей матрицK (I )Определение 2. Алгоритмом кластеризацииAcалгоритм, переводящий выборкуностиSini.называетсяв класс эквивалент-K ( I ) некотоой информационной матрицы I ..Решение задачи кластерногоанализа коллективами алгоритмовИными словами Ac ( Sini ) K (|| ji ||mk ). Данное определениеотражает факт свободы в обозначении полученныхалгоритмом кластеров.
Пусть существуетвыборки Sini алгоритмамиA1c ,r кластеризаций, Arcна k кластеров.Задача построения оптимальной коллективной кластеризациисостоитв вычислении по множеству изr исходныхкластеризаций, задающих классы эквивалентностиK (|| 1ji ||mk ),, K (|| rji ||mk )некоторого нового коллективногорешения K (|| ˆ ji ||mk ) , где ˆ ji {0,1}.Решение задачи кластерногоанализа коллективами алгоритмовОператорΒ( I1,, I r ) || b ji ||mk , b ji {0,, r} , называетсяrсумматором, если b ji rjit 1Матрицу, полученную в результате применения сумматора кнекоторому набору информационных матриц, будем называтьматрицей оценок.