Определение критерия качества проекций в КДА и механизма расчета направляющих осей пространства дискриминантных функций.

1. К ритерии качества проекций точек х на оси и соответствующая им матрица отношения дисперсий .

Определим интересующий нас показатель;

1. Если вектор определен как строка матрицы то есть и - к -тый центроид в Х, то матрица разброса (ковариаций) внутри к -того класса

Матрица суммарного внутриклассового расброса

Напомним для дальнейшего, что ранг каждой матрицы образованной как внешнее произведение векторов (типа ВВ^Т)-не более 1. Докажите это.

Пример – = (*) и видим, что если вторую строку умножим на то получим первую строку. Т.о ранг (*) не более 1. и тд

Поскольку ранг каждой из не более единицы, и поскольку только К-1 из них – линейно независимы - (имея центры и к-1 матрицу данных … возможно ввостановить . Покажите это) то ранг матрицы суммарного внутриклассового расброса не более К-1

2. Определим полный вектор средних значений в Х - m и полную матрицу разброса : и Тогда

 

 

Так как известно что полный разброс есть сумма разброса внутри класса и разброса между классами то

Тогда естественно определить второй член в (*) как - матрицу разброса между классами,:

 

 

Как и выше очевидно что ранг матрицы как и тоже не более чем К-1.

Как будет показано немного ниже из этого следует что максимальная размерность пространства проекции из Х^d в У^q будет не более чем К-1

То есть

Проекция из d-мерного пространства в (К- 1)-мерное пространст­во осуществляется с помощью К- 1 разделяющих функций

i =1,..., К- 1 (88)

Если считать составляющими вектора , а векторы весовых функций столбцами матрицы размера d*(К-1), то проекцию можно записать в виде одного матричного уравнения

. (89)

Выборки x₁,..., х_n проецируются на соответствующее множе­ство выборок y₁,..., y_n которые можно описать с помощью их векторов средних значений и матриц разброса. Так, если мы опре­деляем

и

и

то можно непосредственно получить

(**)

Определим теперь интересующий нас показатель разделимости классов как отношение дисперсии межгрупповой к дисперсии в нутригрупповой

(1) - Известно как частное Релея

на интересующих нас новых координатах

Очевидно что это

Хороший показатель

- чем он выше тем лучше

разделяющие свойства данной линии у:

чем>числитель тем дальше центры друг от друга, чем< знаменатель тем более компактны группы.

Уравнения (**) показывают, как матрицы разброса внутри класса и между классами отображаются посредством проекции в простран­ство меньшей размерности.

Мы ищем матрицу отображения , которая максимизирует

отношение разброса между классами к / разбросу внутри класса.

Простым скалярным показателем разброса является определитель матрицы разброса.

Определитель есть произведение собственных значений, а следова­тельно, и произведение «дисперсий» в основных направлениях, измеряющее объем гиперэллипсоида разброса.

Пользуясь этим пока­зателем, получим функцию критерия

(2)

Задача нахождения прямоугольной матрицы , которая мак­симизирует по (1) или (2) – известное как частное Релея, сводится к нахождению обобщенных собственных векторов, соответству­ющим наибольшим собственным значениям в

(**)

Несколько замечаний относительно этого реше­ния.

Во-первых, если — невырожденная матрица, то задачу, как и прежде, можно свести к обычной задаче определения собст­венного значения. То есть образуем из (**) или

То есть можем стандартно искать и как СобствЧисла и СобВек матрицы . Так мы можем решить задачу.

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

,

обобщенная задача определения СЗ, а затем решить

непосредственно для собственных векторов v _i. Как решать далее дело вкуса в том числе можно

применить итерационный алгоритм вращения осей (метод Якоби)

получим как и прежде в ФА диагон. матрицу

собственных значений матрицы и соответстующую ей матрицу преобразований (собственных векторов)

2. Размерность пространства дискриминационных функцийq

 

Можно дать 2 пояснения возможной величине q

А). Первое по-проще – скорее на интуитивном уровне.

Метод КДА образуя новое пространство размерности q задает там некий алгоритм распознавания новых объектов.

Заметим что для определения положения новых координат используются по сути характеристики рассеяния и положения центров классов. Количество центров (точек-центроидов) =количеству классов К.

Отметим что если мы хотим с помощью некоторого количества точек задать положение некоторого пространства, то мерность этого пространства четко связана с минимально необходимым количеством таких точек:

Для задания одномерного пространства – прямой надо 2 точки для двумерного – плоскости – 3 точки и т.д. То есть при наличии К точек (центров классов) мерность пространства которое мы можем задать с их помощью q=К-1.

С поправкой на то что если количество классов К больше чем мерность d исходного пространства Х то тогда q негде набрать независимых координат больше чем d, в таком случае q=d

Т.о. q = минимальному из чисел К-1 и d

Б).Для определения решается . В предположении что - невырожденная, то есть существует далее для определения количества ненулевых нам существенен только ранг .

Поскольку яв­ляется суммой К матриц ранга единица или менее

(убедитесь сами – матрицы - есть внешние произведения векторов ( - ) и поскольку только К-1 из них независимые матрицы, - (матрицу последнего класса можно получить имея всю выборку и К-1 матрицу )

То имеет ранг К-1 или меньше.

Так что не более К-1 собственных значений есть не нули и искомые век­торы весовых функций соответствуют этим ненулевым собственным значениям. Что и дает мерность пространства - К-1 (с той же поправкой что и выше q = минимальному из чисел К-1 и d)