Телефон: +7 (383)-202-16-86

Статья опубликована в рамках: XLV Международной научно-практической конференции «Научное сообщество студентов: МЕЖДИСЦИПЛИНАРНЫЕ ИССЛЕДОВАНИЯ» (Россия, г. Новосибирск, 21 мая 2018 г.)

Наука: Информационные технологии

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Струкова О.В., Мустафин Д.А. ОЦЕНКА МЕТОДОВ УМЕНЬШЕНИЯ РАЗМЕРНОСТИ ДАННЫХ, ПРИМЕНЯЕМЫХ ДЛЯ ПРЕОБРАЗОВАНИЯ ВИДЕОПОТОКА ПРИ ИДЕНТИФИКАЦИИ ЛИЧНОСТИ // Научное сообщество студентов: МЕЖДИСЦИПЛИНАРНЫЕ ИССЛЕДОВАНИЯ: сб. ст. по мат. XLV междунар. студ. науч.-практ. конф. № 10(45). URL: https://sibac.info/archive/meghdis/10(45).pdf (дата обращения: 06.12.2019)
Проголосовать за статью
Конференция завершена
Эта статья набрала 370 голосов
Дипломы участников
Диплом Интернет-голосования

ОЦЕНКА МЕТОДОВ УМЕНЬШЕНИЯ РАЗМЕРНОСТИ ДАННЫХ, ПРИМЕНЯЕМЫХ ДЛЯ ПРЕОБРАЗОВАНИЯ ВИДЕОПОТОКА ПРИ ИДЕНТИФИКАЦИИ ЛИЧНОСТИ

Струкова Ольга Викторовна

студент, кафедра геоинформатики и информационной безопасности, Самарский университет,

РФ, г. Самара

Мустафин Данис Ахметович

студент, кафедра геоинформатики и информационной безопасности, Самарский университет,

РФ, г. Самара

Научный руководитель Тишин Владимир Викторович

доц., кафедра прикладной математики, Самарский университет,

РФ, г. Самара

Цель исследования:

Оценка эффективности методик уменьшения размерности данных для оптимизации их применения на практике распознавания (идентификации).

Задачи исследования:

1. Обзор литературных источников  о существующих методах уменьшения размерности данных.

2. Проведение исследований (экспериментов) для сравнения эффективности применяемых на практике алгоритмов уменьшения размерности данных в задачах классификации

Методы исследования (программные средства):

Язык программирования С++, библиотека OpenCV

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

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

Решение о выборе метода сокращения размерности основывается на  знании об особенностях решаемой задачи и ожидаемых результатах, а также ограниченности временных и вычислительных ресурсов. По данным литературных обзоров к наиболее часто используемым методам снижения размерности относятся Principal Component Analisys (PCA), Independent Component Analisys (ICA) и Singular Value Decomposition (SVD).

Анализ главных компонент (PCA) — самый простой метод уменьшения размерности данных. Он широко применяется для преобразования признаков при уменьшении размерности данных в задачах классификации. Метод основан на проецировании данных на новую координатную систему меньшей размерности, которая определяется собственными векторами и собственными числами матрицы. С точки зрения математики [1] метод главных компонент представляет собой ортогональное линейное преобразование.

Основная идея метода заключается в вычислении собственных чисел и собственных векторов ковариационной матрицы данных с целью минимизации дисперсии. Матрица ковариации используется для определения разброса относительно среднего по отношению друг к другу. Ковариация двух случайных величин (размерностей) – мера их линейной зависимости:

    (1),

где  – математическое ожидание случайной величины X,  – математическое ожидание случайной величины Y. Также мы можем записать формулу (1) в виде:

 

где  – среднее Х, где  – среднее Y, N – размерность данных.

После вычисления собственных векторов и собственных чисел их значения сортируются в порядке убывания. Таким образом, компоненты получаются в порядке уменьшения значимости. Собственный вектор с самым большим собственным числом и есть главная компонента набора данных. Главные компоненты получаются умножением строк из собственных векторов на отсортированные собственные значения. Для нахождения оптимального пространства меньшей размерности используется формула (3), по которой рассчитывают минимальную ошибку между исходным набором данных и полученным по следующему критерию:

где P – размерность нового пространства, N – размерность исходной выборки, – собственные числа, – пороговое значение. В ходе работы алгоритма получаем матрицу с данными MP, линейно преобразованную из MN, после чего PCA находит линейное отображение M, минимизирующее оценочную функцию:

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

Анализ независимых компонент (ICA), в отличие от PCA — достаточно новый, но быстро набирающий популярность метод. В его основе лежит идея линейного преобразования данных в новые компоненты, которые максимально статистически независимы и необязательно ортогональны друг другу. Для исследований в настоящей работе был выбран алгоритм FastICa, подробно описанный в статье [2]. Основными задачами данного метода являются центрирование(вычитание среднего из данных) и «отбеливание»(линейное преобразование вектора x в вектор с некоррелированными координатами, дисперсия которых равна единице).

Критерием независимости в FastICA является негауссовость, которая измеряется с помощью коэффициента эксцесса:

Для гауссовских случайных величин эта величина равна нулю, поэтому FastICA максимизирует её значение. Если  – «отбеленные» данные, то матрица ковариации «отбеленных» данных – единичная матрица.

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

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

   (8)

Эксперименты

Для экспериментального исследования предложенных методов использовались раскадрированные видеопоследовательности из базы данных CASIA GAIT. База содержит последовательности бинарных изображений, соответствующих отдельным кадрам видеопоследовательности, на которых уже выполнено выделение движущихся объектов.

Из всего множества видеопоследовательностей были случайным образом взяты 15 классов, в которых угол съемки составляет 90 градусов, люди изображены в обычной не зимней одежде и без сумок. В каждом классе было 6 последовательностей. Длина каждой последовательности составляла не менее 60 кадров. Классы были разделены на обучающую и тестовую выборки по 3 последовательности каждая.

Полученные в результате методов PCA и ICA признаки использовались для обучения классификатора, в качестве которого в настоящей работе выступала машина опорных векторов (Support Vector Machines, SVM).

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

 

Рисунок 1. а) Метод главных компонент (PCA) б) Метод независимых компонент (ICA)

 

На рисунке 1(а,б) представлена зависимость точности классификации от значения выходной размерности данных после преобразования. Видно, что в PCA точность классификации при увеличении количества компонент изменяется незначительно, а при использовании ICA точность, начиная с некоторого значения, начинает падать.

 

Рисунок 2. Зависимость времени классификации от количества компонент а) PCA, б) ICA

 

На рисунке 2(а,б) представлена зависимость времени классификации от количества компонент PCA и ICA. Рост размерности в обоих случаях сопровождался линейным возрастанием времени обработки. Из графиков видно, что классификатор SVM работал быстрее после снижения размерности с помощью метода главных компонент (PCA).

Методы Principal Component Analisys (PCA), Independent Component Analisys (ICA) работали достаточно быстро и при определенных параметрах были получены высокие результаты в задаче классификации. Но с данными со сложной структурой эти методы не всегда позволяют достичь желаемого результата. Поэтому в последнее время всё  больше уделяется внимания локальным нелинейным методам, которые совершают проекцию данных на некоторое многообразие, позволяющее сохранить структуру данных.

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

 

Список литературы:

  1. Jolliffe, I.T, Principal Component Analysis, Springer, 2002
  2. Hyvärinen and Erkki Oja,  Independent Component Analysis: Algorithms and Applications, Neural Networks, 13, 2000
  3. Josiński, H. Feature Extraction and HMM-Based Classification of Gait Video Sequences for the Purpose of Human Identification/ Springer, 2013 - Vol 481.
Проголосовать за статью
Конференция завершена
Эта статья набрала 370 голосов
Дипломы участников
Диплом Интернет-голосования

Комментарии (3)

# Наталья 28.05.2018 19:40
Очень интересно
# Светлана 31.05.2018 02:47
Умница
# Юлия 31.05.2018 17:29
Раскрыта очень актуальная тема

Оставить комментарий