Лекция 11 (1185276)

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

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

МАТЕМАТИЧЕСКИЕОСНОВЫ ТЕОРИИПРОГНОЗИРОВАНИЯЛекторСенько Олег ВалентиновичЛекция 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 ) в некоторый кластер*Gl уменьшение функционала F максимально.

Средивсевозможных переносов такого рода.•В результате разбиение Gl 1 отличается от Gl толькосоставом кластеров с номерами  и  . Процесс• завершается, когда никакой последующий перенос неуменьшает функционал или достигнуто указанное пользователеммаксимальное число итерацийМетоды кластерного анализаПустьврезультатепримененияразнообразныхметодовкластеризации получено множество различных решений дляодних и тех же данных. При отсутствии внешнего критерия,выбор одного решения из данного множества кластеризацийможет быть не ясен. Поэтому представляет интерес применениеметодов обработки полученных множеств кластеризаций сцельюпостроенияколлективныхрешений,предпочтительных и обоснованных, чем полученныеотдельными алгоритмами кластеризации.болееРешение задачи кластерногоанализа коллективами алгоритмовКластеризацию выборкиG1 ,Sini  {x1, , xm} , включающую кластеры, Gk можно описать с помощью информационной матрицы||  ji ||mk , где  ji  1 , если x j  Gi и  ji  0 в противномслучае.Наличие нескольких единиц в одной строке соответствуетпринадлежности объекта сразу нескольким кластерам.

Нулеваястрока означает отказ от кластеризации соответствующегообъекта.Решение задачи кластерногоанализа коллективами алгоритмовОпределение 1. Информационные матрицы I ||  ji ||mkI  ||  ji ||mkиназываются эквивалентными, если они равны сточностью до перестановки столбцов.Произвольная информационная матрица I ||  ji ||mk определяеткласс всех эквивалентных ей матрицK (I )Определение 2. Алгоритмом кластеризацииAcалгоритм, переводящий выборкуностиSini.называетсяв класс эквивалент-K ( I ) некотоой информационной матрицы I ..Решение задачи кластерногоанализа коллективами алгоритмовИными словами Ac ( Sini )  K (||  ji ||mk ). Данное определениеотражает факт свободы в обозначении полученныхалгоритмом кластеров.

Пусть существуетвыборки Sini алгоритмамиA1c ,r кластеризаций, Arcна k кластеров.Задача построения оптимальной коллективной кластеризациисостоитв вычислении по множеству изr исходныхкластеризаций, задающих классы эквивалентностиK (||  1ji ||mk ),, K (||  rji ||mk )некоторого нового коллективногорешения K (|| ˆ ji ||mk ) , где ˆ ji {0,1}.Решение задачи кластерногоанализа коллективами алгоритмовОператорΒ( I1,, I r ) || b ji ||mk , b ji {0,, r} , называетсяrсумматором, если b ji   rjit 1Матрицу, полученную в результате применения сумматора кнекоторому набору информационных матриц, будем называтьматрицей оценок.

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

Тип файла PDF

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

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

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