Лекция 11. Методы кластерного анализа_ метод главных компонент (2014 Лекции (Сенько))

Лекция 11Методы кластерного анализапроектирование данных на плоскость, метод главныхкомпонентЛектор – Сенько Олег ВалентиновичКурс «Математические основы теории прогнозирования»4-й курс, III потокСенько Олег Валентинович ()МОТП, лекция 111 / 30Содержание лекции1Кластерный анализ2Визуализация многомерных данных3Метод главных компонентСенько Олег Валентинович ()МОТП, лекция 112 / 30Важное прикладное значение имеют методы анализа данных,связанные с теорией распознавания. К их числу относятся методыкластерного анализа и методы визуализации многомерных данных.Целью методов кластерного анализа является разбиение выборокмногомерных данных на группы объектов близких в смысле некоторойзаданной меры сходства.

Такие компактные группы называютсякластерами, классами или таксонами. Методы кластерного анализаназывают также методами обучения без учителя, автоматическойгруппировки или таксономии. Методы кластерного анализа могутиспользоваться в качества вспомогательных инструментов прирешении задач прогнозирования или распознавания. Так с помощьюкластеризации могут отбираться эталонные объекты. Однако нередкокластеризация может иметь самостоятельное значение. Можновыделить задачи кластерного анализа, для которых число кластеровзадано, а также задачи, в которых число кластеров следуетопределить в ходе решения кластеризации.Сенько Олег Валентинович ()МОТП, лекция 113 / 30Большинство известных алгоритмов кластеризации предполагаетзадание неотрицательной функцией близости ρ(x, y) междупроизвольными векторами x и y. В качестве функций близости могутвыступать евклидова метрика или метрика Хэмминга.

Одним изнаиболее известных методов кластеризации является алгоритм kвнутригрупповых средних. Предположим, что у нас задана выборкамногомерных векторов-объектов Seini = {x1 , . . . , xm }. Алгоритмнаходит такие кластеры, для объектов которых центр «своегокластера» будет ближе центра любого «чужого кластера».Наначальном этапе произвольным образом выбирается начальнаяe 0 = {G0 , . . . , G0 } с содержанием объектовкластеризация G1k00(m1 . . . .

, mk ) соответственно.l−1Предположим, что на шаге (l − 1) получены группы {Gl−11 , . . . , Gk } cсодержанием объектов (m1l−1 , . . . , ml−1k ) На шаге l для каждой изl−1групп Gi вычисляется центр1 Xxjx̄l−1=imlil−1xj ∈Giпри i = 1, . . .

, k.Сенько Олег Валентинович ()МОТП, лекция 114 / 30Произвольный объект xj 0 из выборки Sei ni переносится в группу Gl−1i00 ,если при произвольном i0 из множества {1, . . . , k} \ i00 выполняетсянеравенствоl−1ρ(xj 0 , x̄il−100 ) < ρ(xj 0 , x̄i0 ).. В результате мы получаем группы {Gl1 , . . . , Glk } и переходим к шагу(l + 1). Процесс останавливается, если на каком-то шаге оказывается,что x̄li = x̄l+1при i = 1, . . . , k.iДругим методом кластеризации, основанным на итерационнойпроцедуре является алгоритм Форель, основанный на. движениигипершаров фиксированного радиуса в сторону мест«сгущения»объектов. Пусть фиксировано некоторое положительноечисло R.

Выбирается случайный вектор xj 0 ∈ Seini и гипершар R1радиуса R с центром в z 1 = xj 0 . То есть R1 = {x | ρ(x, z 1 ) < R}.TПолагаем G1 = Seini R1 и вычисляем центр новой сферы по формулеX1xj .z2 =| G1 |xj ∈G1Сенько Олег Валентинович ()МОТП, лекция 115 / 30Формируем группу G2 из объектов Seini , попавших в сферуR2 = {x | ρ(x, z 2 ) < R}. Процесс заканчивается на некотором шаге l∗при выполнении условия Gl∗ +1 = Gl∗ . . Полученное множествообъектов объявляется первым кластером Gf1 . Оно исключается изSeini , а вышеописанная процедура повторяется относительнооставшейся части выборки, в результе чего формируется непересекающаяся с Gf1 выборка Gf2Процесс кластеризации заканчивается на итерации k ∗ , на которойдостигается условиеSeini \ ∪ki=1 Gfi = ∅.Таким образом формируется набор кластеровGf1 , .

. . , Gfk∗ .Полученное число кластеров зависит от выбора радиуса R, которыйявляется параметром алгоритма.Сенько Олег Валентинович ()МОТП, лекция 116 / 30Метод иерархической группировки позволяет не только осуществитькластеризацию с заранее выбранным числом классов и выявитьиерархию кластеров. На начальном этапе в качестве кластероврассматриваются отдельные объекты выборки Seini . Дальнейшаякластеризация производится с используется функции близости междукластерами, которая задаётся на основе функции близости междувекторными описаниями объектов.

На практике используетсянесколько типов функций близости между кластерами Gi0 и Gi00 :минимальное расстояние между объектами из двух кластеровPmin (Gi0 , Gi00 ) =minxµ ∈Gi0 ,xν ∈Gi00ρ(xµ , xν );максимальное расстояние между объектами из двух кластеровPmax (Gi0 , Gi00 ) =maxxµ ∈Gi0 ,xν ∈Gi00ρ(xµ , xν );расстояние между центрами двух кластеровPc (Gi0 , Gi00 ) = ρ(x̄i0 , x̄i00 );Сенько Олег Валентинович ()МОТП, лекция 117 / 30среднее расстояние между объектами двух классовPav (Gi0 , Gi00 ) =X11|Gi0 | |Gi00 |Xρ(xµ , xν ).xµ ∈Gi0 xµ ∈Gi0На втором шаге два ближайших кластера объединяются в один.Процесс объединения повторяется до выделения заранеефиксированного числа кластеров.

Для остановки процессаобъединения кластеров могут быть использованы дополнительныеусловия, задаваемые экспертом, и связанные со спецификойконкретной задачи. В этом случае число кластеров устанавливается входе решения.Используются также методы кластеризации, основанные на поискеразбиений Seini , для которых достигают максимума специальныефункционалы качества.Сенько Олег Валентинович ()МОТП, лекция 118 / 30e = {G1 , . . . , Gk } можетТак качество разбиения на набор кластеров Geбыть описано с помощью функционала внутренних дисперсий FV S (G)представляющего собой взвешенную сумму средних отклонений отцентра внутри внутри каждой из группe =FV S (G)kXi=1|Gi |kXX ρ(xµ , x̄i ) X=ρ(xµ , x̄i ).|Gi |xµ ∈Gii=1 xµ ∈GiНетрудно видеть, что “вес” каждой из групп пропорционален числуобъектов в ней.

Поскольку число всевозможных разбиений Seini на kmгрупп оценивается как kk! полный перебор разбиений здесь заведомоисключен. Поэтому обычно применяют методы частичного перебора сиспользованием случайного выбора начальных разбиений ипоследующей локальной оптимизациейСенько Олег Валентинович ()МОТП, лекция 119 / 30В методах локальной оптимизации (для определенности,минимизации) строится последовательность разбиенийe1 , Ge2 , .

. . , Gel , . . .G, для которыхe 1 ) > FV S (Ge 2 ), . . . , FV S (Ge l ) > FV S (Ge l+1 ), . . .FV S (Ge l+1 вычисляется непосредственно по предшествующемуа разбиение Geразбиению Gl = {Gl1 , . . . , Glk } путем его «локального» изменения –переноса некоторого объектов из одного кластера в другой. Ищетсятакой объект xJ(l) , при переносе которого из кластера Glµ ,e l , в некоторый кластер Glνсодержащего xJ(l) в разбиении Gуменьшение функционала FV S максимально среди всевозможныхпереносов такого рода. В результате разбиение отличается от толькосоставом кластеров с номерами Glµ и Glν . Процесс завершается, когданикакой последующий перенос не уменьшает функционал илидостигнуто указанное пользователем максимальное число итерацийСенько Олег Валентинович ()МОТП, лекция 1110 / 30Решение задачи кластерного анализа коллективами алгоритмовПусть в результате применения разнообразных методов кластеризацииполучено множество различных решений для одних и тех же данных.При отсутствии внешнего критерия, выбор одного решения из данногомножества кластеризаций может быть не ясен.

Поэтому представляетинтерес применение методов обработки полученных множествкластеризаций с целью построения коллективных решений, болеепредпочтительных и обоснованных, чем полученные отдельнымиалгоритмами кластеризации. Кластеризацию выборки Seini ,включающую кластеры {G1 , . .

. , Gk } можно описать с помощьюинформационной матрицы kαji km×k , где αji = 1, если xj ∈ Gi , иαji = 0 в противном случае. Наличие нескольких единиц в однойстроке соответствует принадлежности объекта сразу несколькимкластерам. Нулевая строка означает отказ от кластеризациисоответствующего объекта.Определение 1. Информационные матрицы I = kαji km×k и0 kI = kαjim×k называются эквивалентными, если они равны сточностью до перестановки столбцов.Сенько Олег Валентинович ()МОТП, лекция 1111 / 30Решение задачи кластерного анализа коллективами алгоритмовТаким образом произвольная информационная матрица I = kαji km×keопределяет класс всех эквивалентных ей матриц K(I).cОпределение 2. Алгоритмом кластеризации A называется алгоритм,eпереводящий выборку в класс эквивалентности K(I)некоторойинформационной матрицы I.eИными словами Ac = K(kαji km×k ).

Данное определение отражаетвозможности произвола в обозначении полученных алгоритмомкластеров. Пусть существует r кластеризаций выборки Seiniалгоритмами Ac1 , . . . , Acr на k кластеров. Задача построенияоптимальной коллективной кластеризации состоит в вычислении помножеству из r исходных кластеризаций, задающих классыэквивалентности1reeK(kαji km×k ), . . . , K(kαji km×k )eнекоторого нового коллективного решения K(kα̂ji km×k ) , гдеα̂ji ∈ [0, 1].Сенько Олег Валентинович ()МОТП, лекция 1112 / 30Решение задачи кластерного анализа коллективами алгоритмовОператор B(I1 , .