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

. . , Ir ) = kβji km×k , где βji ∈ {1, . . . , } , называетсясумматором, еслиrXtαji.βji =t=1Матрицу, полученную в результате применения сумматора кнекоторому набору информационных матриц, будем называтьматрицей оценок. Оператор C называется решающим правилом, еслиskm×k ,C(kβji km×k ) = kαjis = 1, если β > β пригде при произвольном j ∈ {1, . . . , m} αjijijts = 0 в противном случае.t = {1, . .

. , k} \ {i}, и αjiОпределение 3. Комитетным синтезом информационной матрицыs kkαjim×k по множеству исходных кластеризаций, задаваемых набороминфориационными матриц Ie = {I1 , . . . , Ir }, называетсяпоследовательное применение к Ie сумматора B и решающего правилаC.Сенько Олег Валентинович ()МОТП, лекция 1113 / 30Решение задачи кластерного анализа коллективами алгоритмовДля оценивания коллективного решения вводится понятиеконтрастных матриц оценок, соответствующих случаям, когда всеисходные решения задач классификации оказались одинаковыми.ckОчевидно, что для произвольной контрастной матрицы kβjim×kc ∈ {0, r}.

Пусть Be c = kβ c km×k - множествовыполняется условие βjijiвсевозможных контрастных матриц . Качеством произвольнойматрицы B = kβji km×k , вычисленной сумматором, определяется какe c.минимальное расстояние до матриц из множества BΦ(B) = minkm XXecBj=1 i=1c|βji − βji|Набор информационных матриц {I10 , . . . , Ir0 } назовём эквивалентным{I1 , . . . , Ir }, еслиe 1 ), . . .

, I 0 = K(Ie r ).I10 = K(IrСенько Олег Валентинович ()МОТП, лекция 1114 / 30Решение задачи кластерного анализа коллективами алгоритмовЗадача оптимального коллективного синтеза сводится поискуэквивалентного {I1 , . . . , Ir } набора {I1m , . . . , Irm }, для которого врезультате применения сумматора получается матрица Bm сминимальным значением Φ среди всевозможных матриц ,вычисляемых сумматором по наборам, эквивалентным {I1 , . . . , Ir }.Сенько Олег Валентинович ()МОТП, лекция 1115 / 30Визуализация многомерных данныхПри решении задач распознавания, классификации и анализа данныхважное значение имеет наличие средств визуализации многомерныхданных, позволяющих наглядно получать представление оконфигурации классов, кластеров и расположении отдельныхобъектов. Предполагаем опять, что у нас задана выборка{x1 , .

. . , xm }, состоящая из элементов пространства Rn . Требуетсянайти отображение этого набора точек на плоскость R2 так, чтобыметрические соотношения между образами точек на плоскостимаксимально соответствовали бы метрическим соотношениям междуними в исходном признаковом пространстве."Близкие"точки в исходном пространстве должны бытьпо-возможности "близкими"на плоскости.Соответственно "удалённые"точки в исходном пространстведолжны быть по-возможности "удалёнными"на плоскости.Сенько Олег Валентинович ()МОТП, лекция 1116 / 30Визуализация многомерных данныхПусть точки {y 1 , . .

. , y m } являются образами точек {x1 , . . . , xm } наплоскости R2 . Пусть δij - расстояние между векторами xi и xj , dij расстояние между векторами y i и y j . Ищется такое отображение, длякоторого сумма различий расстояний между точками будетминимальнаJ(ey) =m XmX(δij − dij )2 → min,i=1 j=1e = {y 1 , . . . , y m } является вектором размерности 2m,где yсодержащим последовательно координаты двумерных образовмногомерных объектов.Минимизация функционала J(ey ) проводится с помощью стандартнойпроцедуры градиентного спуска.Сенько Олег Валентинович ()МОТП, лекция 1117 / 30Визуализация многомерных данныхe l+1 на шаге lНовое значение вектора координат двумерных образов ye l1 ,вычисляется по значению вектора координат двумерных образов yвычисленному на предыдущем шаге, по формулеe l+1 = ye l + κ ? grad[J(eyy l )]e , κ - шаггде grad[J(ey )] - градиент функционала J(ey ) в точке yградиентного спуска.

В качестве начальной конфигурации можетиспользоваться проекция точек {x1 , . . . , xm } на н плоскость,соответствующую некоторой паре признаков. Пример проекции наплоскость из пространства размерности 26, полученной описаннымметодом, приведён на рисунке 1.Сенько Олег Валентинович ()МОТП, лекция 1118 / 30Визуализация многомерных данныхРис.1. Точкам зелёного и синего цвета соответствуют описания двухклассов объектов. Таким образом видно, что точки двух классовявляются достаточно разделёнными.Сенько Олег Валентинович ()МОТП, лекция 1119 / 30Методы преобразования признакового пространства.

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

. Данный метод называетсяМетодом главных компонент (Principal component analysis) , а такжепреобразованием Карунена-Лоэв (Karhunen–Loeve transform) Методглавных компонент основан на переходе от исходного множествавообще говоря коррелированных переменных X1 , . . . , Xn к новомунабору переменных Z1 , . . . , Zn с нулевыми коэффициентамиковариации между ними. То есть cov(Zi , Zj ) = 0 при i 6= j,i = 1, .

. . , n, j = 1, . . . , n. Переход к некоррелированным переменнымможет быть осуществлён с помощью линейного преобразованияnXСенько Олег Валентинович ()20 / 30ZjМОТП,= лекцияwij11Xi .Метод главных компонентДанное преобразование задаваётся матрицей вещественныхкоэффициентов W = kwij kn×n . Предположим, что у нас имеетсяисходная выборка Seini = {x1 , . . .

, xm } , которая может представлена вx11 . . . x1n. . . . . . . . . виде X = xj1 . . . xjn . . Далее будем предполагать,что. . . . . . . . . xm1 . . . xmnPпризнаки в матрице являются центрированными, то есть mj=1 xji = 0при i = 1, . .

. , n.Переход к центрированной выборке может быть всегдалегко осуществлён с помощью простого линейного преобразования.Отметим, что Xt X = (m − 1)Σ, где Σ = kσˆij kn×n - выборочнаяковариационная матрица, элементы которой вычисляются по формулеmσˆij =1 Xxki xkj .m−1k=1Сенько Олег Валентинович ()МОТП, лекция 1121 / 30Метод главных компонентПодобная запись для коэффициентов ковариации возможна из зацентрированности данных.z11 . . . z1n. .

. . . . . . . Предположим, что Z = zj1 . . . zjn . - матрица значения. . . . . . . . . zm1 . . . zmnпризнаков Z1 . . . . , Zn ,полученных с помощью линейного преобразования. Очевидно, чтоZ = XW . Отметим, что матрица Z также является центрированной,поскольку линейное преобразование не приводит к утрате свойствацентрированности. Вследствие требования отсутствия корреляциимежду переменными Z1 , . .

. , Zn матрица Zt Z , являющаясяковариационной матрицей для Z-переменных, является диагональной.При этом Pна диагонали в строке i находится величина (m − 1)δi , гдеm12δi = m−1j=1 zji .Сенько Олег Валентинович ()МОТП, лекция 1122 / 30Метод главных компонентОднакоZt Z = Wt Xt XW = (m − 1)Wt ΣW.Таким образом Wt ΣW является диагональной матрицей. Однако изтеории матриц известно, что диагонализация симметрическойвещественной матрицы Σ может быть осуществлена с помощьюквадратной матрицы E , столбцами которой являютсяортонормированные собственные вектора Σ. Иными словамиcправедливо равенство Et ΣE = V , где V - диагональная матрица, надиагонали которой лежат собственные значения Σ.

Отсюда можносделать вывод, что использование в качестве W матрицы E позволяетосуществлять переход к некоррелированным переменным Z1 , . . . , Zn .При этом дисперсиям переменных Z1 , . . . , Zn будут соответствоватьсобственные значения матрицы Σ .Сенько Олег Валентинович ()МОТП, лекция 1123 / 30Метод главных компонентСтолбцы матрицы E могут быть интерпретированы как новыйортонормированный базис в пространстве исходных переменных.

Приэтом переменные Z1 , . . . , Zn являются проекциями на оси новогобазиса. Отметим, что ось, соответствующая максимальномусобственному значению, является одновременно тем направлением висходном пространстве, для которого дисперсия проекций на неговекторов обучающей выборки максимальна. Следует также отметить,что преобразование, задаваемое матрицей E является унитарнымпреобразованием, не изменяющим длины векторов. Вследствие этогополная выборочная дисперсия остаётся после преобразования Eнеизменной и равной сумме собственных значений ковариационнойматрицы Σ. То есть для полной дисперсии D(Seini ) выборки Seiniсправедливо разложениеD(Seini ) =mmj=1j=11 X1 X(xj − x̄)2 =(z j − z̄)2m−1m−1Сенько Олег Валентинович ()МОТП, лекция 11(1)24 / 30Метод главных компонентОднако из некоррелированности переменных Z1 , .

. . , Zn следует, чтоmnj=1i=1X1 X(z j − z̄)2 =Λim−1где Λ1 , . . . , Λn являются неотрицательными собственнымизначениями1 PmΣ. В формуле (1) используются обозначения x̄ = mxj=1 j ,1 Pmz̄ = m j=1 zj . Принимая во внимание условие центрированностипеременных X, а значит и переменных Z, получаемmnj=1i=1X1 X(zj )2 =Λim−1Полученные в результате преобразования E переменные называютглавными компонентами. Главные компоненты ранжируются взависимости от величин соответствующих собственных значений.Сенько Олег Валентинович ()МОТП, лекция 1125 / 30Метод главных компонентПеременная, соответствующая максимальному собственному значениюΛ1 и задаваемая соответствующим собственному вектором e1называется первой главной компонентой. Она обладает максимальнойдисперсией, равной Λ1 .

Переменная, соответствующая второму повеличине собственному значению Λ2 и задаваемая соответствующимсобственному вектором e2 называется второй главной компонентой ит.д.PkСуммуi=1 Λi принято называть объяснённой дисперсией, а суммуPnΛi=k+1 i - остаточной дисперсией для k первых главных компонент.Покажем справедливость равенстваnXi=k+1Сенько Олег Валентинович ()Λi =mkj=1i=1X1 X[xj −ei (ei , xj )]2 .m−1МОТП, лекция 1126 / 30Метод главных компонентP(ei , xj ). По определению переменных ZДействительно, xj = ni=1 eiPсправедливо равенство xj = ni=1 ei zji .