Лекция 11 (2012 Лекции МОТП (Сенько))

МАТЕМАТИЧЕСКИЕОСНОВЫ ТЕОРИИПРОГНОЗИРОВАНИЯЛекторСенько Олег ВалентиновичЛекция 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Матрицу, полученную в результате применения сумматора кнекоторому набору информационных матриц, будем называтьматрицей оценок.