Собственные числа и векторы в поиске закономерностей. Метод главных компонент

Задачи распознавания изображений обладают интересным свойством. Вот смотришь на картинку и видишь прямую, которая образована разбросанными точками. Как только пытаешься получить эту прямую по данным точек в программе — сразу возникают алгоритмические трудности.

Что поделаешь, это еще одно напоминание о том, что человеческий глаз — это совершенное средство обработки данных.

В этом примере прямая — это некоторая закономерность, которую нужно найти в потоке данных. Где может пригодиться такой алгоритм? Например, в распознавании маркеров взлетно — посадочной полосы оптической системы посадки БПЛА. Или хотя бы определить направление, в котором дедушка Ляо идет из кабачка домой.

Principal Component Analysis, eigenvalue, eigenvector, собственные числа, собственные векторы, БПЛА, распознавание маркеров ВПП

Следы оставленные дедушкой Ляо по дороге из кабачка домой

Понаблюдаем же за дедушкой Ляо. Хорошо посидев с друзьями своей юности в кабачке, он спешит к домашнему очагу. Как видно из карты перемещений, у дедушки Ляо не очень уверенная походка. Тем не менее, очевидно что он стойко идет к своей цели. Очевидно для нас, потому что мы пользуемся совершенными инструментами — собственными глазами. А что делать компьютеру? Как ему выявить закономерность на основе данных десяти точек?

Для этого можно использовать понятие собственных чисел и собственных векторов матрицы. Поскольку теорию мало кто любит и тем более мало кто запоминает, рассмотрим эти понятия на простом примере и затем вернемся к дедушке Ляо во всеоружии.

Матрицы линейного преобразования: портим фигуру

По старой доброй традиции, воспользуемся богатыми математическими возможностями Питона. Не мудрствуя лукаво, нарисуем следующую фигурку — двойной ромбик:

Для наглядности можно вывести значение этой матрицы на экран:

Матрица определяет фигурку из 12 точек, первая строка — x координаты точек, вторая строка — y координаты. Выглядит фигурка так:

Собственные числа, собственные векторы, линейное преобразование, метод главных компонент, Principal Component Analysis

Фигурка, соответствующая исходной матрице

На этом с исходными данными все. Теперь начинается самое интересное: мы будем портить нашу фигурку. Для этого матрицу фигурки умножаем на матрицу линейного преобразования A, которая может растягивать фигурку по горизонтали:

Или сжимать также по горизонтали:

Растягивать по вертикали:

Перекос:

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

Или вообще вместе со сжатием и растяжением еще перекосить ее так, что сразу и не узнаешь:

Воспользуемся последним преобразованием и скособочим нашу фигурку:

Собственные числа, собственные векторы, линейное преобразование, метод главных компонент, Principal Component Analysis

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

Матрица линейного преобразования A перевела 12 наших исходных векторов на другие позиции, то есть поменяла их координаты: на то оно и преобразование.

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

Вскрытие собственников

Найдем собственные числа и собственные векторы нашей матрицы преобразования A. На Питоне это делается одной строчкой:

Я придерживаюсь обозначений, которые показаны в примерах модуля numpy Питона: w — это собственное число, v — собственный вектор. Неудобно, что слова vector и value начинаются на одну и ту же букву, и поскольку вектор главнее, собственное число получило наименование w.

Посмотрим что получилось:

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

Первая парочка:

Наступил момент истины. Подвергнем вектор линейному преобразованию:

Так оно и есть: собственный вектор «не чувствует» родную матрицу A и остается таким же, как и был, точнее — умноженным на собственное число.

Проверка второй парочки:

Тоже самое: какого-либо желания трансформироваться не обнаружено напрочь.

Principal Component Analysis (PCA), или  Метод главных компонент в поисках закономерностей

Теперь мы хорошо подготовлены к тому, чтобы переварить идею метода PCA, вынесенного в заголовок. Метод основан на поиске осей максимальных изменений входных данных; эти оси называются компонентами, что и послужило основой для названия метода. Подробное и самое главное — понятное описание метода для химических приложений изложено здесь (вспоминая замечательный журнал Химия и жизнь).

На самом деле, кроме поиска закономерностей, метод выполняет еще одну задачу: отделяет существенные данные от несущественных; и кроме этого обладает еще одним важным свойством, о котором я скажу в конце. Применив этот метод, мы наконец узнаем, каков на самом деле был кратчайший маршрут дедушки Ляо и что считать его действительным направлением движения, а что — отклонениями (эх, дедушка Ляо, если бы ты меньше просиживал в кабачке то не пришлось бы связываться с отклонениями!).

Мы неспроста тренировались на собственных векторах и числах, поскольку они являются основой для реализации метода PCA (есть и другие реализации). Если мы поняли это, то до понимания реализации метода остался только один шаг. Этот шаг — использование матрицы линейного преобразования как ковариационной матрицы выходных данных.

Итак, начнем с выборки следов дедушки Ляо, которую для солидности будем именовать треком из 10 точек:

Уберем из трека постоянную составляющую и найдем ковариационную матрицу трека:

Сделаем передышку и осмыслим сделанное (физический смысл — основа любого метода). О чем говорит ковариацонная матрица? Одинаковые значения 0.615 говорят о степени связи (корреляции) переменных x[0..9] и y[0..9], которые являются соответствующими координатами трека (простите, в Питоне индексы начинаются с нуля). Элементы главной диагонали 0.717 и 0.617 говорят о корреляции этих переменных с собой же, то есть это практически значения мощности, если переменные интерпретировать как сигналы.

Поэкспериментируем с ковариационной матрицей на более простых данных. Будем брать значение ковариации слегка зашумленных отрезков из трех точек.

Диагональный отрезок под 45°:

Диагональный отрезок под -45°:

Вертикальный отрезок:

Горизонтальный отрезок:

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

Если мы еще раз нырнем в теорию, то обнаружим, что искомые векторы на самом деле являются собственными векторами ковариационной матрицы.

Итак, за работу!

Осталось запечатлеть результат работы на картинке. Красным цветом представлены собственные векторы ковариационной матрицы, которые и есть главные компоненты, или оси максимальной изменчивости данных.

Principal Component Analysis, eigenvalue, eigenvector, собственные числа, собственные векторы, БПЛА, распознавание маркеров ВПП

Главные компоненты метода PCA. Справа — трек в новой системе координат (rotated_track)

На картинке справа — тот же самый трек в новой системе координат, или проще говоря повернутый на угол одной из осей главных компонент (еще одна причина того, для чего ее нужно было искать). Такое преобразование выполняет последняя строка фрагмента программы:

Кажется, подошло время к тому, чтобы сделать кое-какие выводы.

Тайное становится явным

«Человек, у которого только одни часы, точно знает который час. Обладатель двух часов ни в чем не уверен»

До сих пор все шло прекрасно. Ведь согласитесь, что мы в глубине души ожидали, что метод главных компонент подтвердит нашу не очень глубокую догадку о том, что трек дедушки Ляо проходит по оси юго-запад — северо восток. Так оно и есть. Но есть и вторая компонента, которая упрямо доказывает нам, что дедушка Ляо вполне мог двигать и по оси северо-запад — юго восток. И действительно, если ассортимент кабачка оказался забористым, герой нашего рассказа продвигался очень медленно, зато качало его из стороны в сторону будь здоров. Конечно, коротенький второй вектор говорит о том, что это направление как-бы не главное, но оно есть.

Теперь дальше. Мы действительно выделили закономерность во входном треке.  Можем даже предположить, что главная компонента это и есть трек, искаженный шумом. Таким образом, мы разделили существенные и несущественные данные. И самое интересное, мы переместили трек в новую систему координат, вследствие чего он стал одномерным (говоря по научному, мы выполнили ортогонализацию). Понижение размерности входных данных — это большое достижение, например, для этого предназначены такие сложные итерационные методы, как преобразование Грама — Шмидта.

И в конце вишенка на торте. Посчитаем ковариационную матрицу повернутого трека:

Если считать очень-очень маленькие числа (в степени -17) нулями, то ковариационная матрица нового трека

стала диагональной! А это значит, что корреляция, а именно взаимозависимость между координатами x и y исчезла. Более того, малое значение корреляции для координаты y говорит о том, что мы имеем дело с шумом малой мощности. Сказанное влечет за собой важное следствие: теперь мы можем анализировать трек только по одной новой координате x, не обращая внимания на другую: она в силу ортогональности системы не оказывает никакого влияния.

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

Всем большой привет от дедушки Ляо!

7 комментариев Собственные числа и векторы в поиске закономерностей. Метод главных компонент

  • Евгений

    «Остановившиеся часы дважды в сутки показывают сверхточное время».

    Спасибо за интересную идею — мне может пригодится для расчета вектора направления по РЛИ-данным, я так думал просто разные «средние» использовать.

  • Lao

    Да, это пригодится.

    В РЛ (или в КСА точно) может быть своя трекинговая обработка, которая строит траекторию и предсказывает будущее направление движения цели.

  • Евгений

    В документации по КСА не найдешь описаний используемых алгоритмов, не ясно как они даже переводят азимут/дальность в гео-местоположение на плоскости — может и Пифагором простым.

  • Lao

    Там обычная геометрия, единственное в GPS и Глонасс используются разные модели поверхности Земли, необходимо делать перерасчет. По крайней мере раньше так было, точно не знаю как сейчас. Проекция цели на поверхность и координаты есть.

    Дальше для экстраполяции используют фильтр Калмана. Построение трека проблем не представляет, поскольку основные источники наблюдения содержат информацию о борте. Вот с первичными локаторами выделение трека это искусство.

    Можно присоседиться на поток данных с локатора и поиграться со своим трекером. Глядишь, там и новая КСА УВД появится )

  • Евгений

    Там геометрия сильно разная бывает, точно знаю два типа перевода азимута-дальности в гео. координаты. Какая модель использована для размещения сферы зоны на 20 монитора вообще непонятно. Темный лес — разработчик ничего не будет раскрывать. У нас так после ТО на локаторе в конфигурационный файл КСА попало значение оборота локатора в 5 сек., все самолеты вполне себе далеко за сверхзвук выходили, т.е. текущее значение оборота антенны даже не использовалось, тупо бралось то, что было в конфигурационном файле.
    P.S. Пробую треки строить — но сильно лютая мат.статистика для меня ;-). Может быть пока.

  • Lao

    Вот как развертку сделать на плоский экран монитора — эта мысль мне вообще не приходила в голову, а ведь на самом деле там должна быть правильная проекция )

    Получается в локаторе отметки времени шли не в зависимости от датчика поворота антенны, а по таймеру… это косяк разработчика

    С треками хорошо будет работать в связке Python + numpy. Вся нужная математика и простая работа с массивами, плюс простое отображение данных.

    Есть модуль фильтра Калмана, вся программа будет 3 — 4 строчки.

  • Евгений

    Думается на небольших расстояниях там разница небольшая — «сова на глобус» вполне натянется. Но сам факт скрытия алгоритмов обработки разработчиком несколько напрягает.

Ответить

Вы можете использовать эти HTML теги

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">