ТУЛГУ, Лабораторные методы анализа данных. лабораторные работы (номера: 2, 3, 6, 7
лабораторные работы (номера: 2, 3, 6, 7) по дисциплине "методы анализа данных"
_
ПОЛНОЕ ЗАДАНИЕ В ДЕМО ФАЙЛЕ,
ЧАСТЬ ДЛЯ ПОИСКА ДУБЛИРУЮ НИЖЕ
МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное
образовательное учреждение высшего образования
«Тульский государственный университет»
Институт прикладной математики и компьютерных наук
Кафедра информационной безопасности
Утверждено на заседании кафедры
«Информационная безопасность»
«__» _______ 2021 г., протокол № __
Заведующий кафедрой
_________________________А.А. Сычугов
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
по выполнению лабораторных работ
по дисциплине (модулю)
«Методы анализа данных»
основной профессиональной образовательной программы
высшего образования – программы магистратуры
по направлению подготовки
09.04.01 «Информатика и вычислительная техника»
с профилем
« Компьютерный анализ и интерпретация данных»
Форма обучения: очная
Идентификационный номер образовательной программы: 090401-01-21
Тула 2021 год
Разработчик(и) методических указаний
Двоенко С.Д., профессор, д. ф.- м.н., доцент _______________
(ФИО, должность, ученая степень, ученое звание) (подпись)
_____________________________________________ _______________
(ФИО, должность, ученая степень, ученое звание) (подпись)
Лабораторная работа №1
СТАНДАРТИЗАЦИЯ И ПРЕОБРАЗОВАНИЕ ДАННЫХ
Цель и задача работы
Приведение экспериментальных данных к стандартизованному виду. Преобразования
матрицы данных.
Теоретические положения
Матрица данных. Рассмотрим традиционный вид представления результатов эксперимента
- матрицу данных. Пусть исследователь располагает совокупностью из N наблюдений над
состоянием исследуемого явления. Пусть при этом явление описано набором из n
характеристик, значения которых тем или иным способом измерены в ходе эксперимента.
Данные характеристики носят название признаков, показателей или параметров. Такая
информация представляется в виде двухмерной таблицы чисел X размерности N n или в
виде матрицы XN n :
X X X 1 j n ... ...
x
x
x
1
.
.
i
N
x x x
x x x
x x x
j n
i ij in
N Nj Nn
11 1 1
1
1
... ...
. ... . ... .
... ...
. ... . ... .
... ... .
Строки матрицы X соответствуют наблюдениям или, другими словами, объе к-
там наблюдения. В качестве объектов наблюдения выступают, например, в социол о-
гии - респонденты (анкетируемые люди), в экономике - предприятия, виды продук-
ции и т.д. Столбцы матрицы X соответствуют признакам, характеризующим изуча е-
мое явление. Как правило, это наиболее легко измеряемые характеристики объектов.
Например, предприятие характеризуется численностью, стоимостью основных фо н-
дов, видом выпускаемой продукции и т.д. Очевидно, что элемент xij представляет
собой значение признака j, измеренное на объекте i.
Часто матрица данных приводится к стандартной форме преобразов анием
x x x i j i j j j , x
N
x j i j
i
N
1
1
, j i j j
i
N
N
x x 2 2
1
1
, i 1,...N; j 1,... n,
где x j j , 2 среднее и дисперсия по столбцу j, после которого стандартная матрица X об-
ладает свойствами
x
N
x j i j
i
N 1
0
1
,
j i j
i
N
N
x 2 2
1
1
1, i 1,...N; j 1,... n.
В дальнейшем будем использовать для матрицы данных обозначение X, пола-
гая, что это стандартизованная матрица, без дополнительного упоминания. Для п о-
яснения заметим, что часто признаки, описывающие некоторый объект, имеют сущ е-
ственно различный физический смысл. Это приводит к тому, что величины в разли ч-
ных столбцах исходной матрицы трудно сопоставлять между собой, например, кг и
м. Поэтому получение стандартизованной матрицы можно понимать как приведение
всех признаков к некоторой единой условной физической величине, измеренной в
одних и тех же условных единицах.
Гипотезы компактности и скрытых факторов. Рассмотрим n-мерное пространство, где
оси координат соответствуют отдельным признакам матрицы данных X. Тогда каждую
строку матрицы данных можно представить как вектор в этом пространстве. Следовательно,
каждый из N объектов наблюдения представлен своей изображающей точкой в n-мерном
пространстве признаков (Рис. 1.1).
X1
xi
X3
X2
Рис. 1.1. Пространство признаков.
Отметим, что в основе различных методов анализа матрицы данных лежит н е-
формальное предположение, условно названное ―гипотезой компактности‖. Предп о-
лагается, что объекты наблюдения в различной степени ―похожи‖ друг на друга.
Предполагается, что все множество большого числа объектов представимо в виде н е-
большого числа достаточно сильно различающихся подмножеств, внутри которых
объекты наблюдения ―сильно похожи‖. Например, сильно различающиеся подмнож е-
ства характеризуют типы различных состояний изучаемого явления, а похожие об ъ-
екты внутри них являются зафиксированными состояниями я вления, где разброс зна-
чений объясняется ошибками измерения, изменением условий эксперимента и т.д.
Такие компактные множества называются классами, кластерами, таксонами.
При справедливости такой гипотезы задача обработки в наиболее общей формул и-
ровке неформально ставится как задача разбиения исходного множества объектов в
признаковом пространстве на конечное число классов. Не вдаваясь глубоко в суть
различных постановок задачи классификации, отметим следующие важные моменты.
Во-первых, при известном числе классов, как правило, требуется получить на и-
более удаленные друг от друга в пространстве признаков ко мпактные классы.
Во-вторых, часто число классов заранее неизвестно, поэтому нужно его опред е-
лить, исходя из априорных соображений, или, пробуя разные вариа нты разбиения на
классы.
В-третьих, важно, чтобы результат разбиения был устойчивым. Например, м е-
тоды, используемые в одном из направлений обработки данных - кластер-анализе -
могут порождать различные разбиения для небольших изменений матрицы данных.
Так, если в исходную матрицу добавить новые объекты, то результат кластеризации
изменится. Если он изменится незначительно по составу кластеров, удаленности кл а-
стеров друг от друга, их размеру в пространстве, то результат можно считать усто й-
чивым.
В-четвертых, другие методы классификации, например, в распознавании обр а-
зов, направлены не на получение таксономии (перечисление принадлежности объе к-
тов каждому из классов), а на получение способа определять класс каждого доба в-
ляемого к матрице данных объекта. Данный метод реализуется в виде так называемо-
го решающего правила. Оно представляет собой функцию gx , принимающую зна-
чения на конечном множестве из m классов 1,... m . Тогда при предъявлении
объекта x i , решающая функция примет значение g i x .
Заметим, что разбиение объектов наблюдения на классы означает разделение
матрицы данных на горизонтальные полосы, т.е. перегруппировку строк матрицы
так, что внутри каждой из групп строк объекты принадлежат одному классу и не
принадлежат другим классам.
С другой стороны, можно рассмотреть N-мерное пространство, оси которого со-
ответствуют отдельным объектам. Тогда каждый столбец X j матрицы X представля-
ет собой вектор в данном пространстве, а вся матрица - совокупность n векторов
(Рис. 1.2).
x1
X 1
12 X 2
X n
xN
xi X j
Рис. 1.2. Пространство объектов.
Такое пространство называется пространством объектов. В нем все векторы Xj
одинаковы по длине, вычисляемой как евклидова норма
X x N N j i j
i
N
j
2
1
2 .
Тогда характеристикой близости признаков Xi и Xj в таком пространстве служит
близость направлений их векторов, измеряемая cosi j , где i j - угол между ними. В
этом смысле векторы близки, если угол между ними близок к нулю или к 180 0, и,
следовательно, косинус угла близок по модулю к единице. Равенство cosi j по мо-
дулю единице означает совпадение векторов и линейную связь, так как в стандарт и-
зованной матрице данных значения по одному признаку в точности соответствует
значениям по другому признаку, или совпадение векторов с точностью до наоборот,
то есть противоположные направления, и, следовательно, также линейную связь. Т о-
гда перпендикулярные векторы и нулевое значени е косинуса угла между ними соот-
ветствуют наиболее далеким признакам. В этом случае можно предположить прот и-
воположную ситуацию, когда признаки наименее зав исимы друг от друга - линейно
независимы.
Из теории вероятностей и математической статистики известно , что линейная
связь между двумя переменными характеризуется коэффициентом корреляции. Сл у-
чаю двух переменных, где значения каждой из них представлены в виде ряда набл ю-
дений, соответствует выбор двух столбцов и X x x j j Nj
T
1 ,... в матрице данных. Ко-
эффициент корреляции есть просто скалярное произведение двух векторов признаков
в пространстве объектов, нормированное к их длине, то есть просто косинус угла
между стандартизованными векторами:
r
N
x x
N
X X
N
X X i j ki
k
N
kj i
T
j i j i j i j
1 1 1
1
cos cos .
В статистическом смысле корреляционная связь означает, что значения одного
признака имеют тенденцию изменяться синхронно значениям другого признака. О т-
сутствие связи означает, что изменение значений одного признака никак не сказыв а-
ется на изменении значений другого пр изнака. Такие признаки считаются статист и-
чески независимыми и, в частности, при отсутствии корреляционной связи, линейно
независимыми.
Отметим, что в основе понятия о взаимосвязи между признаками лежит нефо р-
мальное предположение, условно названное ―гипотез ой скрытых факторов‖. А имен-
но, предполагается, что состояние некоторого изучаемого явления определяется
―скрытым‖, ―существенным‖ фактором, который нельзя измерить непосредственно.
Можно лишь измерить набор некоторых других признаков, косвенно отражающих
состояние скрытого фактора. Предполагается также, что множество скрытых факт о-
ров невелико и значительно меньше набора измеряемых признаков. Тогда группа
признаков, испытывающая преимущественное влияние некоторого из факторов, б у-
дет более или менее синхронно изменять свои значения при изменении состояния
этого скрытого фактора. Чем сильнее влияние скрытого фактора, тем синхроннее м е-
няют свои значения признаки, тем сильнее связь.
В пространстве объектов это означает, что векторы признаков образуют дост а-
точно компактную группу, в которой пучок направлений векторов можно охватить
некоторым выпуклым конусом с острой вершиной в начале координат.
При справедливости гипотезы о факторах задача обработки в наиболее общей
формулировке неформально ставится как задача в ыделения конечного числа групп
наиболее сильно связанных между собой признаков и построения для каждой из них
(либо выбора среди них) одного, наиболее сильно связанного с ними (наиболее бли з-
кого к ним) признака, который считается фактором данной группы. Ус пешное реше-
ние такой задачи означает, что в основе сложных взаимосвязей между внешними
признаками лежит относительно более простая скрытая структура, отражающая на и-
более характерные и часто повторяющиеся взаимосвязи.
Отметим следующие важные моменты.
Во-первых, различные методы выделения скрытых факторов объединены в
группу методов - факторный анализ. Сюда же многие исследователи относят и метод
главных компонент.
Во-вторых, существенным в этих методах является то, что число найденных
факторов k должно быть много меньше числа признаков n, а найденные факторы
должны быть как можно более ортогональны друг другу.
В-третьих, как правило, система факторов должна быть ориентирована так, чт о-
бы факторы были упорядочены по масштабу разброса значений объектов на их ос ях.
В статистических терминах это означает, что факторы должны быть упорядочены по
дисперсии объектов на их осях. Необходимость получения именно такой конфигур а-
ции объясняется следующим обстоятельством. Возьмем в пространстве факторов
главный фактор - фактор с наибольшей дисперсией объектов по его оси. Очевидно,
что чем больше дисперсия значений объектов по его оси, тем легче выделить локал ь-
ные сгущения значений и интерпретировать их как группы похожих объектов, то
есть классифицировать их. Такое же предпол ожение применимо и к оставшимся фак-
торам. Если система факторов ортогональна или близка к ней, то факторы считаются
независимыми. Тогда разброс значений по оси каждого из факторов можно объя с-
нить влиянием только этого фактора.
Пусть, например, ряды наблюдений двух случайных величин X x x i i Ni
T
1 ,... и
X x x j j Nj
T
1 ,... являются выборками из генеральной совокупности с нормальным
законом распределения. Изобразим простра нство двух признаков в виде плоскости с
осями координат Xi и Xj (Рис. 1.3). Плотность вероятности нормального распредел е-
ния по оси каждого признака есть
f x 1 2 x x 2 1 2 x 2
2 2 2 / exp / / exp / при x 0, 1.
+ 3 IV X i + 3 I
P1
P 2
0.4 0 -3 + 3
X j
-3 -3
0.4
I I I I I
-3 0 + 3
Рис. 1.3. Распределение наблюдений на плоскости.
Согласно хорошо известному правилу ―трех сигм‖, 99.73% наблюдений но р-
мально распределенной случайной величины попадет в интервал значений по оси а р-
гумента от -3 до +3 или при 1 от -3 до +3. Следовательно, на плоскости в ко-
ординатах Xi и Xj все 99.73% наблюдений будут сосредоточены внутри окружн ости
радиуса 3. При наличии корреляционной связи между признаками набл юдения будут
сосредоточены внутри эллипса рассеивания. Чем сильнее окажется связь, тем уже
будет эллипс рассеивания. В случае положительной связи, изображенной на р исунке,
большие значения одного признака имеют тенденцию соответствовать большим зн а-
чениям другого признака и наоборот. Поэтому, в большинстве случаев с овместные
наблюдения значений этих признаков более часто попадают в I и III квадранты пло с-
кости и реже - во II и IV. Кривые равных вероятностей имеют форму вложенных э л-
липсов с двумя осями P1 и P2. Из рисунка легко заметить, что проекции изобража ю-
щих точек на горизонтальную ось Xj в среднем расположены более плотно, чем пр о-
екции тех же точек на ось P1. Математически доказан факт, что проекции точек на
главную ось P1 эллипса рассеивания расположены наименее плотно по сравнению с
другими возможными положениями оси. Если кластеры предс тавляют собой локаль-
ные сгущения в эллипсе рассеивания, то переход к системе коо рдинат P1 и P2 дает
наилучшую возможность для их выделения. При достаточно сильной корреляции и с-
ходных признаков новый признак P1 может быть выбран в качестве их фактора.
Заметим, что разбиение признаков на группы означает разбиение матрицы да н-
ных на вертикальные полосы, то есть перегруппировку столбцов матрицы так, что
внутри одной группы признаки сильно связаны между собой и слабо связаны с л ю-
бым признаком из другой группы.
Матрица объект-объект и признак-признак. Расстояние и близость. Пусть имеется
матрица данных XN n . Если рассматривать строки данной матрицы как N векторов xi в
пространстве n признаков, то естественно рассмотреть расстояние между двумя некоторыми
векторами. Расстояния между всевозможными парами векторов дают матрицу RN N
расстояний типа объект - объект.
Расстоянием между векторами в пространстве признаков называется некоторая
положительная величина d, удовлетворяющая следующим трем аксиомам метрики:
1. dx x 1 2 , 0, dx x 1 1 , 0;
2. dx x dx x 1 2 2 1 , , ;
3. dx x dx x dx x 1 2 2 3 1 3 , , , (неравенство треугольника).
Таким образом, матрица расстояний является симметричной с нулевой глав ной
диагональю. Существуют различные метрики, но наиболее известной вообще и на и-
более применяемой в обработке данных, в частности, является евклидова метрика
d x x i i
i
n
x x 1 2 1 2
2
1
,
.
Часто используется линейная метрика вида d x x i i
i
n
x x 1 2 1 2
1
,
.
Применение линейной метрики оправдано, когда расстояние определяется как
расстояние между домами в городе по кварталам, а не напрямик. Возможны и другие
виды расстояний.
Часто рассматривается величина, обратная в некотором смысле расстоянию -
близость. На практике часто используют функции близости вида
x x x x 1 2
2
1 2 , exp d , или
x x
x x
1 2
1 2
1
1
,
,
d
,
где определяет крутизну функции близости. Очевидно, что матрица близостей
также является симметричной с единичной главной диагональю, так как x x 1 1 , 1.
Если рассмотреть признаки как n векторов в N-мерном пространстве объектов,
то получим другое преобразование матрицы данных в матрицу Rn n типа признак
- признак. Элементом ri j такой матрицы является значение расстояния или близости
между признаками Xi и Xj. Наиболее распространено представление в виде матрицы
близостей между признаками, где под близостью понимается, например, корреляция
соответствующих признаков.
Легко заметить, что содержательные задачи на матрице данных XN n интер-
претируются на квадратных матрицах RN N и Rn n как выделение блочно -
диагональной структуры путем одновременной п ерегруппировки строк и столбцов.
Тогда в каждом диагональном блоке группируются элементы, близкие в соответс т-
вующем пространстве и далекие от элементов других блоков. Такая задача групп и-
ровки известна как задача диагонализации матрицы связей (Рис. 1.8). Задача о диаг о-
нализации матрицы связей является наиболее общей для матриц связей произвольной
природы. Особенно интересным является случай, когда матрица связей является ко р-
реляционной матрицей. Именно для этого случая разработаны и широко применяю т-
ся на практике специальные алгоритмы, известные как алгоритмы экстремальной
группировки признаков (параметров).
X X1 n . . . . . x x 1 N
x
x
1
N
1
2
3
X
X n
1
.
.
.
.
.
G
G
G
1
2
3
Рис. 1.8. Диагонализация матрицы связей.
Задание на работу
1. Выбрать матрицу данных в одном из публичных репозиториев данных:
- http://polygon.machinelearning.ru - репозиторий данных и алгоритмов «Полигон» ВЦ РАН
- http://archive.ics.uci.edu/ml/– репозиторий данных Центра машинного обучения и интеллек-
туальных систем (университет Калифорнии, Ирвайн)
2. Рассмотреть содержательную задачу обработки выбранных данных, изучить описание
данных
3. Составить матрицу количественных данных вида объект-признак
4. Привести матрицу данных к стандартизированному виду
Содержание отчета
Номер и название лабораторной работы, цель лабораторной работы, выводы.
Контрольные вопросы
1. Как вычислить коэффициент корреляции
2. Что характеризует коэффициент корреляции
3. Для чего выполняется стандартизация данных
4. В чем заключаются свойства расстояния
Лабораторная работа №2
ПОСТРОЕНИЕ ГЛАВНЫХ КОМПОНЕНТ
Цель и задача работы
Изучение основных методов поиска собственных векторов и собственных чисел корре-
ляционной матрицы
Теоретические положения
Корреляционная матрица и ее свойства. При анализе связей важное значение имеет
структура взаимосвязей между признаками. Как известно, измерителем линейной связи
между признаками служит коэффициент корреляции или, в более общем случае,
коэффициент ковариации. С другой стороны, вектор средних и матрица ковариаций
являются исчерпывающими характеристиками нормального закона распределения. Поэтому
остановимся более подробно на свойствах корреляционной матрицы.
Корреляционная матрица Rn n является симметричной, с единичной главной
диагональю, положительно полуопределенной матрицей. Напомним из линейной алгебры,
что квадратная матрица, не обязательно симметричная, называется положительно
полуопределенной, если для любого вектора y y y n
T
1,... квадратичная форма y Ry T 0 не
отрицательна. Квадратная матрица R положительно определена, если для любых y
квадратичная форма y Ry T 0 строго положительна.
Заметим, что при ненулевом векторе y квадратичная форма y Ry T может обратиться в
нуль, только если признаки X x x i n i i Ni
T
1 ,... , 1,... линейно зависимы между собой.
Действительно, пусть все признаки Xi линейно зависимы между собой. Тогда матрица
R=(rij = 1), i =1,... n, j = 1,... n состоит из единиц, если линейная связь, например,
положительна. Тогда для некоторого вектора y получим
y Ry T
n
n
i
i
n
i
i
n
n
i
i
n
j
j
n
i j
j
n
i
n
y y
y
y
y y
y
y
y y y y
1
1
1 1
1
1 1 1 1
1 1
1 1
,... ,... 0
.
Очевидно, что данное число представляет собой сумму всевозможных комбинаций
попарных произведений координат вектора y. Все попарные произведения координат
данного вектора можно представить в виде квадратной матрицы размером n n:
y y y y y
y y y y y
y y y y y
n
n
n n n
T
1
2
1 2 1
2 1 2
2
2
1 2
2
yy .
Матрица yyT является симметричной, а сумма ее диагональных элементов
представляет собой квадрат длины вектора y и всегда положительна для ненулевого y.
Следовательно, равенство y Ry T 0 выполняется только, когда сумма диагональных
элементов равна по модулю и противоположна по знаку сумме недиагональных элементов
y y y i
i
n
i j
j i
n
i
n
2
1 1 1
1
2 0
.
Для случая n = 2 получим: y y y y 1
2
2
2
1 2 2 0. Решив данное квадратное уравнение
относительно y1, получим, что y Ry T 0 при y y 1 2 .
Собственные векторы и числа корреляционной матрицы. Собственным вектором
корреляционной матрицы R, соответствующим собственному числу , называется
ненулевой вектор x x x n
T
1,... , удовлетворяющий уравнению Rx x .
Как известно из линейной алгебры, матрица R рассматривается в данном случае как
матрица линейного преобразования вектора x в вектор x. Это означает, что для данного
линейного преобразования R в n-мерном пространстве существует такое направление, что
преобразование R только растягивает вектор x в раз, сохраняя его ориентацию.
Векторное уравнение можно переписать в виде однородного уравнения относительно
x: R Ex 0. Данное уравнение имеет ненулевое (нетривиальное) решение только
тогда, когда определитель detR E равен нулю. Данный определитель представляет
собой уравнение относительно и является полиномом n степени вида
1 1 0
1
1
n n n n 1
n p ... p . Данный полином называется характеристическим
полиномом (многочленом), а уравнение detR E 0 - характеристическим уравнением.
Характеристическое уравнение имеет n, вообще говоря, различных корней. При этом его
корни i являются собственными числами преобразования R. В качестве собственных
векторов xi , i 1,... n линейного преобразования R, соответствующих собственным числам
i , i 1,... n, берутся векторы единичной длины x i n i j
j
n
2
1
1 1
; ,... , каждый из которых
удовлетворяет соответствующему характеристическому уравнению detR E i 0 .
Рассмотрим случай n=2. Тогда получим
R R E
1
R E
1
1
1
1 1
1 0 12
21
2 2 r
r
r
r
r
r
; ; det r
.
Решением квадратного уравнения 2 2 2 1 r 0 относительно являются
корни 1 1 r и 2 1 r . Отметим следующие свойства собственных чисел.
1) 1 2 0. Так как корреляционная матрица R практически положительно
определена, то при произвольном n все ее собственные числа являются действительными и
строго положительными 1 2 ... 0 n .
2) 1 2 2. Вычислим след матрицы R как сумму ее диагональных элементов
trR r r 11 22 1 1 2. Следовательно, trR 1 2 , то есть сумма собственных чисел
корреляционной матрицы равна ее следу. При произвольном n получим i
i
n
trR
1
.
3) 1 2
2 1 r . Определитель корреляционной матрицы равен det R 1 2 r .
Следовательно, det R 1 2 . При произвольном n получим i
n
i
n
1
1
det R det R.
Следовательно, произведение собственных чисел равно определителю корреляционной
матрицы, взятому со знаком плюс, так как все собственные числа положительны.
Найдем собственные векторы x1 и x2, соответствующие собственным числам 1 и 2.
Из характеристического уравнения следует, что первый вектор найдется из уравнения
1
1
0
0
1
1
11
12
11
12
r
r
x
x
r r
r r
x
x
.
Согласно определению x x 11
2
12
2 1. Тогда получим систему уравнений
rx rx
rx rx
x x
11 12
11 12
11
2
12
2
0
0
1.
Из решения данной системы следует, что x x 11 12 2 / 2 0.707. Два решения ука-
зывают на противоположные направления вдоль диагонали первог о и третьего квад-
рантов плоскости координат:
x
x
x
x
11
12
11
12
0 707
0 707
0 707
0 707
.
.
.
. .
Второй вектор найдется из уравнения 2 21 21
2 22 22
1 0
1 0
r x r r x
r x r r x
.
В результате получим два решения, указывающие на противоположные напра в-
ления вдоль диагонали второго и четвертого квадрантов плоскости координат
21 21
22 22
0.707 0.707
0.707 0.707 .
x x
x x
Как сразу нетрудно заметить, собственные векторы матрицы R, то есть вещес т-
венной симметричной матрицы, соответствующие различным собстве нным числам,
ортогональны между собой. Покажем это для произвольного n. Раccмотрим уравне-
ния Rx x 1 1 1 и Rx x 2 2 2 , где 1 2 . Домножим каждое из уравнений на собст-
венный вектор другого уравнения и получим x Rx x x x Rx x x 2 1 1 2 1 1 2 2 1 2
T T T T и . Так
как x Rx x x R x R x x Rx 2 1 1 2 1 2 1 2
T T T T T T T ( ) , то, вычтя одно уравнение из другого, полу-
чим 0 1 2 1 2 1 2 1 2 1 2 2 1 1 2 2 1 x x x x x x x x x x T T T T T .
Отсюда следует, что x x 2 1 0 T . Следовательно, собственные векторы линейного
преобразования R образуют ортонормированный базис в n-мерном пространстве. Та-
кие векторы называются главными компонентами корреляционной матрицы.
Главные компоненты корреляционной матрицы обладают весьма важными
свойствами, которые имеют содержательный смысл в обработке данных и поэтому
широко используются. Ниже мы покажем геометрический смысл гла вных компонент
на плоскости.
Диагональная форма. Преобразование корреляционной матрицы к диагональной форме
основано на следующем свойстве вещественной (действительной) симметричной матрицы.
Пусть R - невырожденная корреляционная матрица и имеет n различных собственных чисел
i , i 1,... n . Пусть ai , i 1,... n - соответствующие собственные векторы, выбранные из пар
собственных векторов, соответствующих каждому собственному числу, составляющие
ортонормированный базис в n-мерном пространстве. Пусть A a a 1,... n - матрица,
столбцами которой являются собственные векторы ai. Рассмотрим матрицу
A A
a
a
a a
a a a a
a a a a
E T
T
n
T
n
T T
n
n
T
n
T
n
1
1
1 1 1
1
1 0
0 1
...
...
...
...
...
,
где E - единичная матрица. Следовательно, матрица A является ортогональной.
Напомним, что некоторая матрица A ортогональна, если A A A A E 1 T . По
уравнению Ra a получим RA a a 1 1 ... n n , где столбцами матрицы в правой части
являются векторы i i a . Учитывая, что векторы ai ортогональны, получим
A RA
a
a
a a
a a a a
a a a a
T
T
n
T
n n
T
n
T
n
n
T
n n
T
n n
1
1 1
1 1 1 1
1 1
1 0
0
...
...
...
...
.
Матрица A RA T диагональна, и ее диагональные элементы являются собстве н-
ными числами. Из условия A RA T следует AA RAA A A T T T и R AAT , так
как AA A A E T T . Следовательно, невырожденная корреляционная матрица R мо-
жет быть приведена к диагональной форме путем ортогонального преобразов ания
A RA T .
Пусть x x x n
T
1,... - некоторый вектор, заданный своими проекциями на осях
координат X i n i, 1,... . Рассмотрим вектор y y y n
T
1,... , где y A x T , а строками матрицы
AT являются собственные векторы ai
T линейного преобразования R. Тогда
y
a x
a x
y
y
a x
n a x
T
n
T
j j
j
n
nj j
j
n
1 1
1
1
1
.
Следовательно, компонента yi вектора y - это скалярное произведение собственного
вектора ai и вектора x. С другой стороны, скалярное произведение - это произведение
модулей векторов ai и x на косинус угла между ними. Так как ai 1, то это есть
произведение x на косинус угла между ai и x - проекция вектора x на ai. Поэтому вектор y
представлен своими проекциями на ортонормированный базис собственных векторов
корреляционной матрицы R. Можно считать, что новый базис ai , i 1,... n образует новое n-
мерное пространство признаков Y y y i n i N
T
1 ,... , 1,... , принимающих свои значения на N
объектах.
Значения n признаков Yi, как бы измеренных на N объектах, образуют новую матрицу
данных Y XA, полученную из матрицы X ортогональным преобразованием A:
Y
y
y
x a x a
x a x a
x
x
a a XA
1 1 1 1
1
1
1
T
N
T
T T
n
N
T
N
T
n
T
N
T
n
.
Корреляционная матрица R, вычисленная по матрице X, представляет собой
матрицу
R X X
1 1 1
1 1 1
1
1
1 N
X X X X
X X X X
N
X
X
X X
N
T T
n
n
T
n
T
n
T
n
T
n
T
.
Вычислим среднее признака Yj
y
N N
x a
N
a x a x j i
T
j
i
N
ik kj
k
n
i
N
kj ik
i
N
k
n
kj k
k
n
1 1 1
0
1 1 1 1 1 1
x a ,
так как матрица X стандартизована. Вычислим величину
1 1 1
0
0
1
N N N
T T T T T
n
Y Y XA XA A X XA A RA
.
Тогда матрица является ковариационной матрицей, вычисленной по матр ице
Y. Диагональная структура матрицы показывает, как и следовало ожидать, незав и-
симость признаков Y i n i, 1,... . Собственные числа i являются дисперсиями этих
признаков, то есть i i 2 . Если разделить значения компонент каждого пр изнака Yi
на величину i i , то матрица Y будет приведена к стандартизованному виду.
Тогда преобразование Y XA 1/2 даст стандартизованную матрицу данных Y с еди-
ничной корреляционной матрицей:
1 1 1 2 1 2 1 1 2 1 2
1 2 1 2 1 2 1 2 1 2 1 2
N N N
T
T
T T
T
Y Y XA XA A X XA
A RA E
/ / / /
/ / / / / / .
Собственные векторы и собственные числа. В задачах обработки часто возникает
необходимость в определении собственных векторов корреляционной матрицы,
соответствующих тем или иным собственным числам. Как было показано, для нахождения
собственных чисел и векторов следует найти корни характеристического полинома порядка
n относительно . Затем для каждого i , i 1,... n следует найти свой собственный вектор,
который мы обозначим как a i i ni
T
a a 1 ,... , как решение однородной системы линейных
уравнений относительно этого собственного вектора при ограничении на его длину
ai j i
j
n
a
2
1
1.
Известно, что точные методы поиска корней полинома и корней системы линейных
уравнений представляют собой громоздкие процедуры при больших n, практически начиная
с n 3. Поэтому данная задача часто решается итерационными методами вычислительной
математики. Итерационные методы для одновременного поиска всех собственных чисел и
векторов представляют собой методы преобразования симметричной матрицы в
диагональную форму. Часто требуется вычислить только максимальное собственное число и
соответствующий ему собственный вектор. Рассмотрим известный итерационный метод
приближенного вычисления максимального собственного числа и соответствующего
собственного вектора.
Пусть все собственные числа различны и упорядочены 1 2 ... 0 n . Пусть
x x x n
T
1,... - некоторый вектор. Совокупность собственных векторов ai , i 1,... n
корреляционной матрицы R образует ортонормированный базис, в пространстве которого
вектор x преобразуется в вектор y A x T . Т.к. матрица А ортогональна, то y A x 1 и
x Ay , где вектор х представлен своим разложением по базису собственных векторов:
1
1 1 1
1
,... ...
n
n n n i i
i
n
y
y y y
y
x a a a a a .
Тогда
1 1 1
n n n
i i i i i i i
i i i
y y y
Rx R a Ra a . Выделим первое слагаемое
1 1 1 1 1 1
2 2 1
n n
i
i i i i i
i i
y y y y
Rx a a a a .
Умножим это равенство еще раз слева на R:
2
1 1 1
2 1
n
i
i i
i
y y
RRx R x R a a 1 1 1
2 1
n
i
i i
i
y y
Ra Ra
2
2
2
1 1 1 1 1 1 1
2 1 2 1
n n
i i
i i i i
i i
y y y y
a a a a .
Тогда для некоторого s получим
1 1 1
2 1
s
n
s s i
i i
i
y y
R x a a .
Так как 1 2 ... 0 n и 0 1
1
i , то
1
lim 0
s
i
s
и 1 1 1 lim s s
s
y
R x a .
Тогда при 1 y 0 первый собственный вектор определяется достаточно далеким
членом последовательности 2 , , , ... , ... s x Rx R x R x . Но при 1 1 получим, что 1 1 1 lim s
s
y
a ,
а при 1 1 получим, что 1 1 1 lim 0 s
s
y
a . Следовательно, вектор R x s стремится по
направлению к вектору a1, но его длина значительно отличается от единичной.
Поэтому строят две другие последовательности 0 1 , ,... , ... s x x x и z z 1, ... , ... s , где
1, / || || s s s s s z Rx x z z , начиная с некоторого вектора x0 единичной длины. Следовательно,
|| || 1 s x при любом s, а предел последовательности s x стремится по направлению к
вектору a1. Следовательно, 1 lim s
s
x a . Тогда s 1 s 1 1 z Rx a и
z a s i
i
n
a
1 1 1 1 1
2
1
1 .
Задание на работу
Ознакомиться с теоретической справкой к данной лабораторной работе. Найти собст-
венные векторы и собственный числа корреляционной матрицы.
Содержание отчета
Номер и название лабораторной работы, цель лабораторной работы, выводы.
Контрольные вопросы
1. Основные свойства корреляционной матрицы
2. Собственные векторы и собственный числа квадратной матрицы
3. Интерпретация главных компонент на плоскости
4. Алгоритм приближенного вычисления максимального собственного числа
Лабораторная работа №3
ВИЗУАЛИЗАЦИЯ ДАННЫХ В ПРОСТРАНСТВЕ ГЛАВНЫХ КОМПОНЕНТ
Цель и задача работы
2D и 3D представление данных в пространстве первых главных компонент
Теоретические положения
Главные компоненты на плоскости. Пусть в соответствии со статистической гипотезой
порождения матрицы данных X в n-мерном пространстве признаков существует
многомерное нормальное распределение с плотностью вероятности f x / , . Для
стандартизованной матрицы X мы полагаем, что
f
n
T x 0 R
R
/ , x R x
det
exp
1
2
1
2
1
.
Проведем ортогональное преобразование матрицы данных X в новую матрицу данных
Y XA, где A - матрица, столбцами которой являются собственные векторы
корреляционной матрицы R. Тем самым мы перешли в новое признаковое пространство,
образованное ортонормированным базисом линейного преобразования R. Очевидно, что в
новом признаковом пространстве задано нормальное распределение с плотностью
вероятности
f
n
T y / 0, y y
det
exp
1
2
1
2
1
.
Так как A RA T , то
1
1
1 1
1
1 A RA A R A A R A T T T ,
det det
1
1
0
0
n
i
i
n
;
1
1
1
0
0
1
n
.
Тогда f
y
n
i
i
n
i
i i
n
y / 0,
( )
exp
1
2
1
2
1
2
1
.
Пусть n = 2, тогда двухмерное нормальное распределение имеет вид
f
y y
y / 0, exp
1
2
1
2 1 2
1
2
1
2
2
2
.
Рассмотрим уравнение
y y
p p 1
2
1
2
2
2
0
, . Из курса аналитической геометрии
известно, что это уравнение линии второго порядка. При заданном p и найденных
1 и 2 данная линия является линией постоянного значения плотности вероятн о-
сти
1
2
2
1 2
e
p/
. Преобразуем данное уравнение линии второго порядка к кан о-
ническому виду
y
p
y
p
1
2
1
2
2
2
1
. Так как 1 2 0, то данное уравнение является ка-
ноническим уравнением эллипса в системе координат, образованной собственными
векторами, которые соответствуют собственным числам 1 и 2 .
Если r > 0, то 1 1 r и 1 r 2 и система главных компонент y10y2 повернута на
450 относительно исходной системы координат x10x2. Если r < 0, то 1 1 r и 1 r 2 и
система главных компонент y10y2 повернута на 1350 относительно x10x2. Если r=0, то
1 2 1. Тогда уравнение эллипса представляет собой уравнение окружности y y p 1
2
2
2
радиуса p . В этом случае система главных компонент y10y2 может быть ориентирована в
любом направлении, то есть любое направление является главным для такого линейного
преобразования R. Если r=1, то 1 2 2, 0. Тогда уравнение эллипса для линии
постоянного значения плотности вероятности вырождается в уравнение для двух точек,
расположенных на оси 0y1, вида y p r p y 1 2 1 2 , 0 (Рис. 2.1).
y2
x 2
p 1 r
y 1
p 1 r
x 1
Рис.2.1. Главные компоненты
Определим уравнение максимального эллипса в соответствии с правилом ―трех сигм‖,
согласно которому 99.73% всех наблюдений сосредоточено внутри него. Согласно свойствам
канонического уравнения эллипса его главная ось совпадает с направлением первой главной
компоненты 0y1. Длина главной полуоси составляет величину p 1 . В то же время
максимальное положительное случайное отклонение величины y1 на оси 0y1 от центра
координат с вероятностью 0.9973 не превышает величины 3 3 1 1 . Следовательно,
p 1 1 3 , откуда p=9. Проведя те же рассуждения для второй оси максимального
эллипса, получим, что уравнение имеет вид
y y 1
2
1
2
2
2 9 9
1
и описывает линию постоянного
значения плотности вероятности на уровне
f p e
p
r
e
r
1
2
2 1
6 28 1
4 5 0 004
1 2 1
2 2
/
.
. .
.
Т.к. как длина главной полуоси равна p p r 1 1 , то при увеличении r длина
главной полуоси увеличивается. В это время длина второй полуоси эллипса p p r 2 1
уменьшается при увеличении r. Следовательно, чем сильнее связаны признаки X1 и X2
корреляционной зависимостью, тем больше дисперсия 1
2
1 признака Y1 и меньше
дисперсия 2
2
2 признака Y2 при неизменной суммарной дисперсии 1
2
2
2
1 2 2 .
Модель лавных компонент. Пусть новая матрица данных получена путем ортогонального
преобразования Y XA 1/2 . Такая матрица является стандартизованной, то есть
1
N
T Y Y E . Тогда преобразование некоторого вектора x к вектору y выполняется как
y x A T T 1/2 или y A x 1/2 T . Выполним обратное преобразование X Y A 1/2 T . Тем
самым мы выразили матрицу исходных данных через матрицу Y.
Согласно гипотезе скрытых факторов, значение каждого исходного признака,
измеренного на некотором объекте, зависит от влияния некоторых ―скрытых‖ неизмеряемых
факторов и определяется совокупностью их вкладов, пропорциональных силе влияния.
Тогда матрицу Y будем считать матрицей n скрытых факторов, а матрицу U A T T 1/2 -
матрицей факторных нагрузок. Тогда каждая компонента некоторого вектора x, измеренного
на некотором объекте, представляется как совокупность значений факторов на этом объекте
x y A T T T 1/2 или x A y Uy 1/2 :
x
x
y
y
y
a y
n a y
n n
n
i i i
i
n
i i i
i
n
i ni i
i
n
1
1 1
1
1
1
1
1
a a a .
Тогда корреляционная матрица имеет вид
R X X Y A Y A A Y Y A
1 1 1 1 2 1 2 1 2 1 2
N N N
T T T T T T / / / /
=A A UU AA 1/2 1/2 T T T .
Рассмотрим взаимные корреляции между признаками из X и факторами из мат-
рицы Y: 1 1 1 2 1 1 2 1 2
N N N
T T
T
T X Y Y A Y A Y Y A U / / / .
Следовательно, матрица U факторных нагрузок является матрицей взаимных
корреляций между исходными признаками и скрытыми факторами, где элемент u a ij ij i
равен величине взаимной корреляции между признаком Xi и фактором Yj. Рассмотрим
структуру корреляционной матрицы
R UU
T
i
i
n
i i i ni
i
n
i ni i i
i
n
ni
i
n
a a a
a a a
1
1
2
1
1
1
1
2
1
.
Дисперсия k kk i ki ki
i
n
i
n
r a u 2 2 2
1 1
1
некоторого признака Xk есть величина,
состоящая из вкладов соответствующих главных компонент. Полный вклад всех
главных компонент в дисперсии всех признаков соста вляет величину
k
k
n
i ki
i
n
k
n
T a n 2
1
2
1 1
trUU trR tr = .
При преобразовании к главным компонентам вместо n исходных признаков по-
лучается такое же число факторов. Но вклад довольно большой части главных ко м-
понент в суммарную дисперсию признаков является небольшим. Поэтому часто ц е-
лесообразно исключить те главные компоне нты, вклад которых невелик. При этом
оказывается, что при помощи m первых наиболее весомых главных компонент, где
m<n, можно объяснить основную долю суммарной ди сперсии признаков. Эта доля
называется объясняемой долей дисперсии h n i i
i
m
i
m
2 2
1 1
, где обычно
h n 2 / 0.8.
Задание на работу
Ознакомиться с теоретической справкой к данной лабораторной работе. Найти собст-
венные векторы и собственные числа корреляционной матрицы. Выполнить проекцию объ-
ектов на первые два и первые три собственных вектора, отобразить полученные векторы на
плоскости (2D) и в ортогональной проекции трех координат (3D).
Содержание отчета
Номер и название лабораторной работы, цель лабораторной работы, вычисления и графики,
выводы.
Контрольные вопросы
1. Основные свойства корреляционной матрицы
2. Собственные векторы и собственный числа квадратной матрицы
3. Интерпретация главных компонент на плоскости
4. Алгоритм приближенного вычисления максимального собственного числа
5. Методы визуализации данных
6. Задача Карунена-Лоэва
Лабораторная работа №4
ВИЗУАЛИЗАЦИЯ ПРИЗНАКОВ В ПРОСТРАНСТВЕ ГЛАВНЫХ КОМПОНЕНТ
Цель и задача работы
2D и 3D представление признаков в пространстве первых главных компонент
Теоретические положения
Визуализация признаков. Как было показано, дискретное преобразование Карунена-Лоэва
является формальной основой для визуализации объектов в ортогональном пространстве
первых трех главных компонент.
Очевидно, что это можно сделать в пространстве объектов. В нем каждый признак j X
представлен вектором длины N , а все признаки X j , j 1..., n расположены на гиперсфере
этого радиуса в гиперпространстве объектов размерности N .
Поэтому можно было бы взять три любые оси. Но какие? В общем случае возникает за-
дача выбора таких осей, чтобы в их пространстве конфигурация элементов множества (т.е.
признаков) была бы искажена наименьшим образом. Очевидно, что для этого надо решить
задачу дискретного преобразования Карунена-Лоэва для матрицы взвешенных скалярных
произведений
1
( , ) T N N
n
S XX с элементами
1
( ) ij i j s
n
x x , i 1,... N , j 1,... N , где
1 ( , ) ( ,... ) n X N n X X , 1 ( , ) ( ,... ) T T T T
n X n N X X .
Тем не менее, применение в данном случае объектов как осей координат не совсем
удобно, т.к. объекты не являются вариационными рядами.
С другой стороны, конфигурация признаков уже задана нам матрицей взвешенных ска-
лярных произведений
1
( , ) T n n
N
R X X . Напомним, что взвешенные скалярные произведения
1 T
ij i j r X X
N
характеризуют угол между нормированными признаками в пространстве объ-
ектов. Нам нужно показать эти углы в ортогональном пространстве главных компонент.
Рассмотрим матрицу R(n,n) как матрицу данных, где n строк представляют элементы
множества (исходные признаки) в пространстве размерности n своими корреляциями (ска-
лярными произведениями) с другими признаками, оси которых образованы столбцами.
Рассмотрим систему ортогональных координат, заданных матрицей 1 ( , ) ( ,... ) n A n n a a ,
состоящей из собственных векторов 1 ( ,... )T
i i ni a a a , i 1,... n , матрицы R(n,n) в простран-
стве исходных признаков. Найдем проекции векторов-строк из R(n,n) на векторы из
1 ( ,... ) n A a a и получим ненормированную матрицу вычисленных признаков Γ(n,n) RA с
элементами ( ) ij i j r a , где 1 ( ,... ) i i in r r r .
Тогда подматрица Γ(n,3) даст визуальное представление исходных признаков в орто-
гональном пространстве первых трех главных компонент. Длины построенных векторов при-
знаков также необходимо нормировать к единичной длине.
Задание на работу
Ознакомиться с теоретической справкой к данной лабораторной работе. Найти собст-
венные векторы и собственные числа корреляционной матрицы. Выполнить проекцию при-
знаков на первые два и первые три собственных вектора, отобразить полученные векторы на
плоскости (2D) и в ортогональной проекции трех координат (3D).
Содержание отчета
Номер и название лабораторной работы, цель лабораторной работы, вычисления и графики,
выводы.
Контрольные вопросы
1. Основные свойства корреляционной матрицы
2. Собственные векторы и собственный числа квадратной матрицы
3. Интерпретация главных компонент на плоскости
4. Алгоритм приближенного вычисления максимального собственного числа
5. Методы визуализации признаков
6. Задача Карунена-Лоэва
Лабораторная работа №5
ИЗУЧЕНИЕ АЛГОРИТМА К-MEANS
Цель и задача работы
Изучение основных методов построения алгоритмов кластер-анализа. Изучение принципа
работы алгоритма.
Теоретические положения
Алгоритмы кластер-анализа. Решение задачи кластер-анализа также направлено на выявле-
ние локальных сгущений объектов в признаковом пространстве. Так как решение задачи кла-
стер-анализа направлено на получение непосредственной классификации перечислением клас-
сов объектов, то при ее решении отсутствует этап обучения и не строится решающее правило.
Тогда решение задачи кластер-анализа заключается в следующем:
1. выбрать меру близости (расстояния) в пространстве;
2. конструктивно определить понятие локального сгущения;
3. решить проблему классов.
Заметим, что каждая из указанных проблем достаточно нетривиальна сама по себе, и при
их решении существует масса тонкостей, как теоретических, так и эмпирических. В то же время
интуитивный смысл каждой проблемы достаточно прозрачен. Поэтому далее рассмотрим наи-
более очевидные примеры решения данных проблем.
Некоторые наиболее типичные меры близости и расстояния уже были рассмотрены нами
ранее. Заметим, что при конструировании таких мер открывается широкое поле деятельности
для учета всех особенностей данных, отражающих по мнению исследователя суть задачи обра-
ботки.
Конструктивное определение понятия локального сгущения означает, что задается неко-
торая эвристическая процедура выделения классов, либо задается некоторый критерий и, как
правило, итерационная процедура его экстремизации. Например, одним из распространенных
показателей качества кластеризации является среднее дисперсий классов, взвешенных по объе-
мам классов, которое нужно минимизировать:
J
N K i
i
K
i
z z x z
x
1
2
1
1
,...
, z x
x
i
i N
i
1
,
где K- заранее заданное число классов i , zi- среднее по классу (центр класса), Ni- число
объектов в классе i , N- всего объектов.
Рассмотрим типичный алгоритм минимизации критерия J для заданного числа классов
K. Различные модификации данного алгоритма известны как алгоритм K- внутригрупповых
средних, алгоритм K - средних, алгоритм Мак-Куина, алгоритм Хартигана.
Шаг 0: Для заданного числа K классов выбираются K исходных центров
zi i K 0 , 1,... , например, как K самых удаленных друг от друга объектов.
Шаг s: 1. Все множество объектов xl , l 1,...N распределяется по K классам по правилу
x i
s , если x z x z i
s
j
s , j 1,...K, j i .
2. Пересчитываются центры классов z x
x
i
s
i
s N
i
S
1 1
, i 1,...K .
3. Если выполнено z z i
s
i
s i K 1 , 1,... , то стоп,
иначе переход к шагу s s1.
Для применения алгоритмов кластеризации требуется, как правило, заранее определить
из априорных соображений число классов K. Выбор числа классов может сильно повлиять на
результат кластеризации, так как неудачный выбор не позволит выделить компактные классы.
Поэтому в общем случае возникает необходимость оптимизировать результат кластеризации по
числу классов. Заметим, что рассмотренный критерий качества кластеризации не оптимизиру-
ется по числу классов, так как имеет максимальное значение (дисперсия исходных данных) при
K=1 и минимальное нулевое значение при K=N.
Задача определения оптимального числа классов является весьма сложной теоретиче-
ской задачей, поэтому часто процедуры кластеризации строятся как алгоритмы, реализующие
некоторый способ перебора числа классов. Перебор по числу классов осуществляется, напри-
мер, так называемыми агломеративными (объединяющими) или дивизимными (разделяющими)
процедурами.
Например, в агломеративной иерархической процедуре в самом начале предполагается
K N , где N - число объектов, то есть каждый объект является классом. Затем число классов
изменяется на K N 1 за счет объединения двух ближайших классов и т.д., вплоть до K 1,
когда все объекты находятся в одном классе. Затем выбирается оптимальное число классов
K .
Для объединения классов требуется уточнить понятие двух ближайших классов. Рас-
стояние между двумя классами можно определить различными способами, например:
1. ближайший сосед d i j
i j
1
, min
,
x x
x x ;
2. дальний сосед d i j
i j
2
, max
,
x x
x x ;
3. среднее расстояние d
N N i j
i j i j
3
1
,
x x
x x
;
4. расстояние по центрам d
N N
N N i j
i j
i j
4 i j ,
z z .
Отметим, что, если классы недостаточно компактны, то результаты могут сильно разли-
чаться при использовании различных мер расстояния между классами.
Оптимальное число классов K в иерархической процедуре можно оценить по порогу,
который задается межклассовыми расстояниями. Предполагается, что ниже оптимального по-
рога происходит частое (естественное) укрупнение классов и быстрое падение их числа при
небольших приращениях порога межклассовых расстояний. Выше оптимального порога укруп-
нение классов возобновляется (вынужденно) лишь при относительно большом приращении по-
рога межклассовых расстояний.
Процесс объединения можно изобразить в виде дендрограммы, отложив по горизонтали
номера объектов, по вертикали - значения расстояний между объединяемыми классами, прово-
дя соединения между ними на соответствующем уровне (Рис. 4.11).
Здесь видно, что оптимальное значение порога 0.6 дает оптимальное число классов
K =3, до которого происходит естественное укрупнение классов.
0 1 2 3 4 x1
x1
x2
3
2
1
1
2
8
3
4 5
6
7
9
1
2
0.3
0.6
1.4
1.6
8 2 1 3 4 5 6 7 9
объекты
d1 d1
1 2 3 4 5 6 7 8 9 К
К*
а) б) в)
Рис. 4.11. Результат агломеративной иерархической кластеризации
а) граф ближайшего соседства,
б) дендрограмма,
в) изменение порога межклассовых расстояний.
Очевидно, что в дивизимной иерархической процедуре процесс выделения классов вы-
полняется в противоположном направлении. Особенность иерархических группировок состоит
в том, что классы разных уровней образуют вложенные подмножества. Такая информация часто
важна, так как позволяет исследователю последовательно проследить процесс объединения
объектов и уточнить результат объединения. Тем не менее, иерархические алгоритмы вычисли-
тельно достаточно трудоемки и требовательны к ресурсам.
Иерархические процедуры группировки реализуют один из способов перебора по числу
классов. Альтернативой ему является использование неиерархических алгоритмов, например
алгоритма Хартигана. Но тогда при переборе по числу классов придется выполнять кластериза-
цию заново для каждого значения числа классов K. Алгоритмы такого типа весьма чувстви-
тельны к начальному решению. Хорошее начальное решение (исходные центры близки к сред-
ним по классам) резко сократит число шагов алгоритма, а плохое (исходные центры являются
самыми близкими объектами) может просто привести к неудовлетворительному результату.
Так как средние по классам еще только будут найдены, то имеет смысл в качестве исходных
центров принять самые далекие объекты. Это оправдано, так как смысл критерия J состоит в
том, чтобы сделать классы наиболее компактными, а их центры разнести как можно дальше.
Поиск двух самых далеких объектов весьма прост - это максимальный элемент в матрице рас-
стояний. Но поиск K>2 самых далеких объектов по матрице расстояний уже является более
сложной операцией, трудоемкость которой возрастает с ростом K. Поэтому хотелось бы при
переборе по числу классов среди исходных центров для данной кластеризации использовать
центры предыдущей кластеризации. Предполагается, что центры классов двух последователь-
ных кластеризаций мало отличаются при больших K. Построим здесь дивизимную неиерархи-
ческую процедуру кластеризации.
На каждом шаге, начиная с K 1, найдем класс с наибольшей дисперсией, и пусть его
номер равен k. Примем в качестве центров два самых далеких объекта в классе k и разобьем его
на два класса k и K+1 алгоритмом Хартигана. Для K+1 классов примем в качестве исходных K-1
ранее полученных центров и два новых центра и найдем K+1 классов алгоритмом Хартигана.
Перейдем к шагу K K 1. Процедура останавливается при K N .
Оптимальное число классов K можно выбрать как границу, до которой среднее дис-
персий классов быстро убывает при увеличении K, а после которой уменьшение среднего дис-
персий классов резко замедляется. Например, на Рис. 4.12 показано изменение среднего дис-
персий классов для данных на Рис. 4.11 а). В данном случае также K =3.
1 2 3 4 5 6 7 8 9
2
1
1.15
0.5
0.14
K*
J
K
Рис. 4.12. Среднее дисперсий классов.
Если проследить работу данной дивизимной неиерархической процедуры по шагам, то
окажется, что последовательность разбиений на классы объектов на Рис. 4.11 а) образует ие-
рархию и отображается дендрограммой Рис. 4.11 б), с той разницей, что дендрограмма строится
в противоположном направлении. В общем случае последовательные классификации, получен-
ные данной процедурой, не образуют иерархию. Тем не менее, построенная здесь процедура
обладает одним интересным свойством.
Назовем классификацию на K шаге дивизимной неиерархической процедуры устойчи-
вой, если классификация на K+1 шаге иерархически вложена в нее. В противном случае клас-
сификацию на K шаге назовем неустойчивой и будем говорить, что на шаге K+1 были наруше-
ния иерархии. Смысл устойчивости классификации ясно следует из свойств процедуры. Дейст-
вительно, иерархическая вложенность классификации на K+1 класс в классификацию на K
классов означает, что класс k был разбит на два, а остальные классы не изменились. Следова-
тельно, две независимые классификации на K шаге процедуры, полученные при разбиении
класса k с максимальной дисперсией на два и при разбиении всего множества на K+1 класс,
совпали. Это позволяет нам говорить об устойчивости разбиения на K классов и предположить,
что были получены компактные классы.
В общем случае в последовательности классификаций можно выделить подпоследова-
тельности иерархически вложенных классификаций, в которых все классификации, кроме по-
следних, являются устойчивыми. Отметим, что классификации на K 1 и на K N классов
устойчивы по определению. Каждая подпоследовательность устойчивых классификаций опре-
деляет свой масштаб соотношения между между средней дисперсией классов и дисперсией
центров. Очевидно, что оптимальное число классов K определяется одной из устойчивых
классификаций. При выборе оптимального числа классов следует ограничить последователь-
ность устойчивых классификаций справа, отбросив все разбиения с большим числом малона-
полненных классов, согласно условию K N * . Также следует ограничить последовательность
устойчивых классификаций слева, отбросив все разбиения, для которых средняя дисперсия
классов превышает дисперсию центров. Выполнение данных условий обеспечит получение
компактных классов, соответствующих общепринятому в литературе эвристическому опреде-
лению кластера или сгущения.
Задание на работу
Ознакомиться с теоретической справкой к данной лабораторной работе. Построить алго-
ритм кластер-анализа. Обработать данные.
Содержание отчета
Номер и название лабораторной работы, цель лабораторной работы, Пояснительная записка,
выводы.
Контрольные вопросы
1. Что такое локальное сгущение?
2. Что такое кластер?
3. Опишите различные типы кластеров.
4. Опишите алгоритм k-средних.
5. Опишите модификации алгоритма k-средних (Мак-Куина, Хартигана).
Лабораторная работа №6
ИЗУЧЕНИЕ АЛГОРИТМА ISODADA
Цель и задача работы
Изучить работу алгоритма. Изучить способ решения проблемы выбора числа кластеров.
Теоретические положения
Алгоритм кластеризации ISODATA(ИСОМАД). Предназначен для разделения задан-ного множества образов (в данном случае точек двумерного пространства) на подмножества (кластеры), связанные определенным свойством, например основанное на близости точек по геометрическому расстоянию. Алгоритм эвристический, т.е. результат работы во многом зави-сит от заданных начальных параметров.
При работе с набором {x1, x2, ..., xN}, составленным из N элементов, алгоритм ИСОМАД выполняет следующие основные шаги.
Шаг 1. Задаются параметры, определяющие процесс кластеризации:
К—необходимое число кластеров;
QN —параметр, с которым сравнивается количество выборочных образов, вошедших в кластер;
Qs— параметр, характеризующий среднеквадратичное отклонение;
Qc—параметр, характеризующий компактность;
L— максимальное количество пар центров кластеров, которые можно объединить;
I — допустимое число циклов итерации.
Шаг 2. Заданные N образов распределяются по кластерам, соответствующим выбранным исходным центрам, по правилу
xÎ Sj, если ||х – zj|| < ||х – zi||, i=1,2, ..., Nc; i¹ j,
применяемому ко всем образам х, вошедшим в выборку; через Sj обозначено подмножест-во образов выборки, включенных в кластер с центром zj.
Шаг 3. Ликвидируются подмножества образов, в состав которых входит менее QN элемен-тов, т. е. если для некоторого j выполняется условие Nj < QN, то подмножество Sj исключается из рассмотрения и значение Nc уменьшается на 1.
Шаг 4. Каждый центр кластера zj, j=1, 2, ..., Nc, локализуется и корректируется посредст-вом приравнивания его выборочному среднему, найденному по соответствующему подмноже-ству Sj, т. е.
где Nj —число объектов, вошедших в подмножество Nj.
Шаг 5. Вычисляется среднее расстояние Dj между объектами, входящими в подмножество Sj, и соответствующим центром кластера по формуле
Шаг 6. Вычисляется обобщенное среднее расстояние между объектами, находящимися в отдельных кластерах, и соответствующими центрами кластеров по формуле
Шаг 7. (а) Если текущий цикл итерации—последний, то задается Qc=0; переход к шагу 11. (б) Если условие Nc<=К/2 выполняется, то переход к шагу 8. (в) Если текущий цикл итерации
имеет четный порядковый номер или выполняется условие Nc>=K/2, то переход к шагу 11; в противном случае процесс итерации продолжается.
Шаг 8. Для каждого подмножества выборочных образов с помощью соотношения
вычисляется вектор среднеквадратичного отклонения s j = (s 1j, s 2j, ..., s nj)', где п есть раз-мерность образа, xik, есть i-я компонента k-ro объекта в подмножестве Sj, zij есть i-я компонента вектора, представляющего центр кластера zj, и Nj —количество выборочных образов, включен-ных в подмножество Sc. Каждая компонента вектора среднеквадратичного отклонения s j харак-теризует среднеквадратичное отклонение образа, входящего в подмножество Sj, по одной из главных осей координат.
Шаг 9. В каждом векторе среднеквадратичного отклонения s j, j=1, 2, ..., Nc, отыскивается максимальная компонента s jmax.
Шаг 10. Если для любого s jmax, j=1, 2, ..., Nc, выполняются условия s jmax > Qs и
а)
или
б) Nj < К/2,
то кластер с центром zj расщепляется на два новых кластера с центрами zj+ и zj- соответст-венно, кластер с центром zj ликвидируется, а значение Nc увеличивается на 1. Для определения центра кластера zj+ к компоненте вектора zj, соответствующей максимальной компоненте век-тора s j, прибавляется заданная величина g j; центр кластера zj- определяется вычитанием этой же величины g j из той же самой компоненты вектора zj. В качестве величины g j можно выбрать некоторую долю значения максимальной среднеквадратичной компоненты s jmax, т. е. поло-жить g j = ks jmax, где 0 < k <= 1. При выборе g j следует руководствоваться в основном тем, чтобы ее величина была достаточно большой для различения разницы в расстояниях от произ-вольного образа до новых двух центров кластеров, но достаточно малой, чтобы общая структу-ра кластеризации существенно не изменилась.
Если расщепление происходит на этом шаге, надо перейти к шагу 2, в противном случае продолжать выполнение алгоритма.
Шаг 11. Вычисляются расстояния Dij между всеми парами центров кластеров:
Dij =|| zi - zj ||, i=1, 2, ..., Nc-1; j=i+1, 2, ..., Nc.
Шаг 12. Расстояния Dij сравниваются с параметром Qc. Те L расстояний, которые оказа-лись меньше Qc, ранжируются в порядке возрастания:
[Di1j1, Di2j2, ..., DiLjL,]
причем Di1j1 < Di2j2 < ... < DiLjL,. a L—максимальное число пар центров кластеров, которые можно объединить. Следующий шаг осуществляет процесс слияния кластеров.
Шаг 13. Каждое расстояние Diljl вычислено для определенной пары кластеров с центрами zil и zjl. К этим парам в последовательности, соответствующей увеличению расстояния между центрами, применяется процедура слияния, осуществляемая на основе следующего правила.
Кластеры с центрами zil и zjl, i=1, 2, ..., L, объединяются (при условии, что в текущем цик-ле итерации процедура слияния не применялась ни к тому, ни к другому кластеру), причем но-вый центр кластера определяется по формуле
Центры кластеров zil и zjl ликвидируются и значение Nc уменьшается на 1.
Отметим, что допускается только попарное слияние кластеров и центр полученного в ре-зультате кластера рассчитывается, исходя из позиций, занимаемых центрами объединяемых кластеров и взятых с весами, определяемыми количеством выборочных образов в соответст-вующем кластере. Опыт свидетельствует о том, что использование более сложных процедур объединения кластеров может привести к получению неудовлетворительныхрезультатов. Опи-санная процедура обеспечивает выбор в качестве центра объединенного кластера точки, пред-
ставляющей истинное среднее сливаемых подмножеств образов. Важно также иметь в виду, что, поскольку к каждому центру кластера процедуру слияния можно применить только один раз, реализация данного шага ни при каких обстоятельствах не может привести к получению L объединенных кластеров.
Шаг 14. Если текущий цикл итерации—последний, то выполнение алгоритма прекраща-ется. В противном случае следует возвратиться либо к шагу 1, если по предписанию пользова-теля меняется какой-либо из параметров, определяющих процесс кластеризации, либо к шагу 2, если в очередном цикле итерации параметры процесса должны остаться неизменными. Завер-шением цикла итерации считается каждый переход к шагам I или 2.
Пример.
Выборка образов, использованная для иллюстрации работы алгоритма ИСОМАД.
Хотя алгоритм ИСОМАД не очень подходит для ручных вычислений, принцип его работы можно проиллюстрировать на простом примере. Рассмотрим выборку, образы которой разме-щены так, как это изображено на рис. 3.11.
В данном случае N ==8 и п = 2. В качестве начальных условий задаем Nc=1, z1 = (0,0)' и следующие значения параметров процесса кластеризации:
Шаг 1.
К=2, QN=1, Qs=1, Qc=4, L=0, I=4.
Если всякая априорная информация об анализируемых данных отсутствует, эти парамет-ры выбираются произвольным образом и затем корректируются от итерации к итерации.
Шаг 2. Так как задан только один центр кластера, то
S1 ={x1, x2, ..., x8} и N1 = 8.
Шаг 3. Поскольку N1 > QN, ни одно подмножество не ликвидируется.
Шаг 4. Корректируется положение центра кластера:
Шаг 5. Вычисляется расстояние Dj:
Шаг 6. Вычисляется расстояние D:
D = D1 = 2,26.
Шаг 7. Поскольку данный цикл итерации—не последний и Nc = К/2, осуществляется пере-ход к шагу 8.
Шаг 8. Для подмножества S1 вычисляется вектор среднеквадратичного отклонения:
Шаг 9. Максимальная компонента вектора s 1 равна 1,99, следовательно, s 1max = 1,99.
Шаг 10. Поскольку s 1max > Qs, и Nc = К/2, кластер с центром z1 расщепляется на два но-вых кластера. Следуя процедуре, предусмотренной шагом 10, выбираем g j = 0,5s jmax = 1,0.
Для удобства записи будем называть центры этих кластеров z1 и z2 соответственно. Значе-ние Nc увеличивается на 1; переход к шагу 2.
Шаг 2. Подмножества образов имеют теперь следующий вид:
S1 ={x4, x5, ..., x8}, S2 ={x1, x2, x3} и N1 = 5, N2 = 3.
Шаг 3. Поскольку обе величины—и N1, и N2—больше QN, ни одно подмножество не лик-видируется.
Шаг 4. Корректируется положение центров кластеров:
Шаг 5. Вычисляется расстояние Dj, j=1,2:
Шаг 6. Вычисляется расстояние D:
Шаг 7. Поскольку данная итерация имеет четный порядковый номер, условие (в) шага 7 выполняется. Поэтому следует перейти к шагу 11.
Шаг 11. Вычисление расстояний между парами центров кластеров:
Шаг 12. Величина расстояния D12 сопоставляется с параметром Qc. В данном случае D12 > Qc.
Шаг 13. Результаты шага 12 показывают, что объединение кластеров невозможно.
Шаг 14. Поскольку данный цикл итерации—не последний, необходимо принять решение: вносить или не вносить изменения в параметры процесса кластеризации. Так как в данном (простом) случае 1) число выделенных кластеров соответствует заданному, 2) расстояние меж-ду ними больше среднего разброса, характеризуемого среднеквадратичными отклонениями, и 3) каждый кластер содержит существенную часть общего количества выборочных образов, то делается вывод о том, что локализация центров кластеров правильно отражает специфику ана-лизируемых данных. Следовательно, переходим к шагу 2.
Шаги 2—6 дают те же результаты, что и в предыдущем^ цикле итерации.
Шаг 7. Ни одно из условий, проверяемых при реализации данного шага, не выполняется. Поэтому переходим к шагу 8.
Шаг 8. Для множеств S1 ={x4, x5, ..., x8}, S2 ={x1, x2, x3}
Шаг 9. В данном случае s 1max = 0,75 и s 2max = 0,82.
Шаг 10. Условия расщепления кластеров не выполняются. Следовательно, переходим к шагу 11.
Шаг 11. Полученный результат идентичен результату последнего цикла итерации
Шаг 12. Полученный результат идентичен результату последнего цикла итерации.
Шаг 13. Полученный результат идентичен результату последнего цикла итерации.
Шаг 14. На данном цикле итерации не были получены новые-результаты, за исключением изменения векторов среднеквадратичного отклонения. Поэтому переходим к шагу 2.
Шаги 2—6 дают те же результаты, что и в предыдущем;
цикле итерации.
Шаг 7. Поскольку данный цикл итерации—последний, задаем Qc = 0 и переходим к шагу 11.
Шаг 11. Как и раньше,
Шаг 12. Полученный результат идентичен результату последнего цикла итерации.
Шаг 13. Результаты шага 12 показывают, что объединение кластеров невозможно.
Шаг 14. Поскольку данный цикл итерации—последний, выполнение алгоритма заканчи-вается.
Даже из этого простого примера должно быть ясно, что применение алгоритма ИСОМАД к набору данных умеренной сложности в принципе позволяет получить интересные результаты только после проведения обширных экспериментов. Выявление структуры данных может быть, однако, существенно ускорено благодаря эффективному использованию информации, получае-мой после каждого цикла итерационного процесса. Эту информацию, как будет показано ниже, можно использовать для коррекции параметров процесса кластеризации непосредственно при реализации алгоритма.
Задание на работу
Ознакомиться с теоретической справкой к данной лабораторной работе. Реализовать алго-ритм. Определить оптимальное число кластеров.
Содержание отчета
Номер и название лабораторной работы;
Цель лабораторной работы;
Пояснительная записка к проекту;
Выводы.
Контрольные вопросы
1. Что такое локальное сгущение?
2. Что такое кластер?
3. Опишите различные типы кластеров.
4. Опишите алгоритм k-средних.
5. Опишите модификации алгоритма k-средних (Мак-Куина, Хартигана).
6. В чем суть проблемы выбора числа классов?
7. Что такое дендрограмма?
8. Постройте дивизимный алгоритм классификации.
9. Постройте агломеративный алгоритм классификации.
10. Опишите дивизимный неиерархический алгоритм классификации.
13. Опишите алгоритм ISODATA.
Лабораторная работа №7
ИЗУЧЕНИЕ АЛГОРИТМА FOREL
Цель и задача работы
Изучить работу алгоритма. Изучить способ решения проблемы выбора числа кластеров.
Теоретические положения
Алгоритм Форель является примером эвристического дивизимного алгоритма клас-сификации. В основе работы алгоритма Форель лежит использование гипотезы компактности: близким в содержательном смысле объектам в геометрическом пространстве признаков соот-ветствуют обособленные множества точек, так называемые «сгустки». Если расстояние между центром -го таксона и точкой этого таксона обозначить , то сумма расстояний между центром и всеми точками этого таксона будет равна:
где: – расстояние между центром -го таксона и всеми точками этого таксона; – расстояние между центром -го таксона и точкой этого таксона.
Сумма таких внутренних расстояний для всех таксонов равна:
Целью работы алгоритма Форель является найти такое разбиение множества объектов на таксонов, чтобы величина была минимальной.
Работа алгоритма заключается в перемещении гиперсферы определенного радиуса в гео-метрическом пространстве до получения устойчивого центра тяжести наблюдений, попавших в эту гиперсферу. До начала работы алгоритма признаки объектов нормируются так, чтобы их значения находились между нулем и единицей
Пример работы алгоритма.
Допустим, было дано некоторое множество классифицируемых объектов. Пусть каждый объект обладает только двумя свойствами, - это позволит отобразить исходные данные на гео-метрической плоскости:
Шаг 1. Построить гиперсферу радиуса , охватывающую все множество точек:
Шаг 2. Установить радиус гиперсферы и перенести центр сферы в любую из внутренних точек (расстояние до которых меньше радиуса):
Шаг 3. Вычислить новый центр тяжести и перенести в него центр сферы:
Шаг 4. Если новый центр тяжести отличается от предыдущего, то необходимо вернуться к шагу 2 и повторить цикл. Цикл будет повторяться до тех пор, пока центр тяжести не переста-нет смещаться. Таким образом, центр сферы перемещается в область локального сгущения то-чек. В предложенном примере центр сферы , поэтому необходимо установить новый радиус сферы и перенести центр сферы в произвольную внутреннюю точку:
Шаг 5. Вычислить новый центр тяжести и перенести в него центр сферы. Новый центр тяжести , поэтому внутренние точки текущей сферы объединяются в таксон:
Шаг 6. Точки, принадлежащие новому таксону, исключаются из анализа, и работа алго-ритма повторяется с шага №1. И так до тех пор, пока все точки не будут исключены из анализа:
Процедура алгоритма Форель является сходящейся за конечное число шагов в евклидо-вом пространстве любой размерности при произвольном расположении точек и любом выборе гиперсферы.
Если начальную точку, в которую переносится центр сферы, на шаге №2 менять случай-ным образом, может получиться несколько вариантов таксономии, из которых выбирается тот, на котором достигается .
Алгоритм Форель 2 является модификацией исходного алгоритма и применяется в тех случаях, когда необходимо получить изначально заданное количество кластеров (таксонов). Ра-диус сферы по мере надобности может изменяться на заданную величину, которая от итерации к итерации будет уменьшаться.
Наилучшему варианту таксономии отвечает при числе таксонов равном задан-ному.
Задание на работу
Ознакомиться с теоретической справкой к данной лабораторной работе. Построить алго-ритм кластер-анализа. Обработать данные.
Содержание отчета
Номер и название лабораторной работы;
Цель лабораторной работы;
Пояснительная записка к проекту;
Выводы.
Контрольные вопросы
1. Что такое локальное сгущение?
2. Что такое кластер?
3. Опишите различные типы кластеров.
4. Опишите варианты алгоритма Forel.
Лабораторная работа №8
ИЗУЧЕНИЕ АЛГОРИТМОВ SKAT, KOLAPS
Цель и задача работы
Изучить работу алгоритмов. Изучить способ решения проблемы выбора числа кластеров.
Теоретические положения
Алгоритм SKAT. Если при многократном случайном выборе начальной точки получа-ется большое число неодинаковых таксономий или если таксоны сильно отличаются друг от друга по количеству своих точек, то это может означать, что наш материал наряду с нескольки-ми локальными сгустками точек содержит еще и одиночные точки или небольшие их скопле-ния, случайно разбросанные в пространстве между сгустками. Создается ощущение того, что имеется несколько «самостоятельных» таксонов и ряд случайно образовавшихся, «несамостоя-тельных» таксонов, которые было бы целесообразно присоединить к ближайшим самостоя-тельным.
Каждый очередной таксон находился нами в условиях, когда точки, попавшие в преды-дущие таксоны, исключались из рассмотрения. А что происходит, если таксоны формируются в присутствии всех точек? Может случиться, что некоторые из более поздних таксонов вклю-чат в свой состав точки, ранее вошедшие в другие таксоны, и не останутся на месте, а станут скатываться в сторону соседнего сгустка точек и сольются с одним из своих предшественников. Такая ситуация изображена на рис. 6: таксон 2 начнет смещаться и сольется с таксоном 1. Дру-гие же таксоны останутся на прежнем месте и с прежним составом своих внутренних точек. Бу-дем считать таксоны 1, 3 и 4 устойчивыми, самостоятельными, а таксон 2 — неустойчивым, случайным. Случайные таксоны могут появляться из-за помех в данных или из-за неудачного выбора радиуса сфер.
Проверку на устойчивость таксономии можно было бы делать строгими статистическими методами. Однако они разработаны для случаев, когда речь идет о простых распределениях (обычно нормальных) в пространстве малой размерности. Анализ данных же часто имеет дело с относительно небольшим числом объектов (прецедентов) в пространстве большой размерности, и говорить о каком бы то ни было распределении не возможно. Поэтому приходится применять единственно возможные в такой ситуации и, как кажется, достаточно разумные эвристические приемы.
Один из таких приемов реализован в алгоритме SKAT. На вход программы подается мно-жество объектов и результаты его таксономии с помощью алгоритма FOREL при радиусе сферы, равном . Процедуры таксономии повторяются с таким же радиусом сфер, но теперь в качестве начальных точек выбираются центры, полученные в таксономии , и формирование каждого нового таксона делается с участием всех точек. В результате обнаруживаются неус-тойчивые таксоны, которые скатываются к таксонам-предшественникам.
Решение выдается в виде перечня устойчивых таксонов и указания тех неустойчивых, ко-торые к ним тяготеют. Если мы хотим ограничиться только устойчивыми таксонами, тогда мы должны стремиться к такому варианту таксономии, при котором количество точек в устойчи-вых таксонах было бы максимальным, т. е. максимизировать функционал , где
Алгоритм KOLAPS. Взглянув на рис., можно отметить следующие его особенности: здесь выделяются три разных по диаметру сгустка точек на равномерном сером фоне. Хотелось бы, чтобы алгоритм таксономии мог выделить эти три сгустка, каждый со своим диаметром, отделив их от точек фона, т. е. мог бы решать задачу выделения ярких созвездий на звездном небе. Для решения таких задач предназначен один из алгоритмов семейства FOREL — алго-ритм KOLAPS. Его можно разделить на два этапа.
На первом этапе ищутся потенциальные центры будущих таксонов, а на втором — делает-ся проверка, действительно ли выбранная точка является центром устойчивого таксона.
В начале первого этапа сфера достаточно большого радиуса помещается в любую точку множества и смещается, как и в алгоритме FOREL, в центр локального сгустка точек. Ко-личество внутренних точек полученного таксона служит мерой локальной плотности точек в данном месте признакового пространства. Если больше некоторого порога , то центр такого мощного таксона заносится в список претендентов на роль центра таксона-созвездия, а попавшие в него внутренние точки из дальнейшего рассмотрения исключаются. Если меньше , то список претендентов не меняется, но внутренние точки этого таксона также га-сятся. Затем центр сферы помещается в любую из оставшихся точек и процесс выделения сле-дующих таксонов продолжается до исчерпания всех точек.
После этого восстанавливается все множество точек и выделяется в списке претенден-тов таксон с наибольшим значением локальной плотности . В центр этого таксона помеща-ется сфера, и ее радиус начинает сжиматься от величины до величины . На каждом -м шаге сжатия определяется число точек, оставшихся внутренними. Если начальный радиус был слишком большим для данного таксона (т. е. если он захватывал много разреженного простран-ства), то в начале процесса сжатия скорость убывания числа внутренних точек будет неболь-шой. По мере вхождения сферы в более плотную часть таксона количество теряемых точек начнет увеличиваться, что служит сигналом к остановке сжатия. В результате находится наибо-лее естественный для данного таксона радиус сферы и фиксируется число его внутренних точек . Та же процедура постепенного сжатия повторяется и для других таксонов из списка пре-тендентов, упорядоченных по характеристике локальной плотности. В результате выбирается таких таксонов, в состав которых после сжатия попадает наибольшее количество точек. Это
условие равнозначно максимизации функционала .
Задание на работу
Ознакомиться с теоретической справкой к данной лабораторной работе. Построить алгоритмs кластер-анализа. Обработать данные.
Содержание отчета
Номер и название лабораторной работы;
Цель лабораторной работы;
Пояснительная записка к проекту;
Выводы.
Контрольные вопросы
1. Что такое локальное сгущение?
2. Что такое кластер?
3. Опишите различные типы кластеров.
4. Опишите алгоритмы Skat, Kolaps.
