ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММНЫХ СРЕДСТВ СОКРАЩЕНИЯ РАЗМЕРНОСТИ МНОГОМЕРНЫХ ДАННЫХ

Покидышева Л.И.¹, Мадаминова М.О.², Ладнюк В.В.³

¹Кандидат технических наук, доцент, ²магистрант, ³аспирант, Сибирский федеральный университет

ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММНЫХ СРЕДСТВ СОКРАЩЕНИЯ РАЗМЕРНОСТИ МНОГОМЕРНЫХ ДАННЫХ

Аннотация

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

Ключевые слова: метод главных компонент, ядерный метод главных компонент, метод многомерного шкалирования.

Pokidysheva L.I.¹, Madaminova М.О.², Ladnyuk V.V.³

¹PhD in Engineering, associate professor, ²undergraduate student, ³postgraduate student, Siberian Federal University

RESEARCH AND DEVELOPMENT OF ALGORITHMS AND SOFTWARE FOR REDUCTION OF THE DIMENSIONALITY OF MULTIDIMENSIONAL DATA

Abstract

At processing large amounts of information, there is often a problem of reducing the dimensionality of data and keep its informative value. The paper presents the effective algorithms for reducing the dimensionality of data, describes their operating principles: the principal component method, the kernel method of principal components, the multidimensional scaling method, the local-linear embedding method, the isometric mapping method, and the flexible maps method. The software implementing the above mentioned algorithms is developed, this application was used to analyze medical data.

Keywords: principal components method, nuclear method of principal components, multidimensional scaling method.

В статистике, биологии, физике и других науках часто необходимо анализировать большие объемы данных. Такие данные сложно интерпретировать и визуализировать. Возникает проблема уменьшения размерности данных с максимальным сохранением их информативности. Это делает актуальным создание методов и алгоритмов программного обеспечения для анализа данных, с помощью которых исследователь сможет обработать данные методами многомерного анализа, а также интерпретировать результаты.

Метод главных компонент

Пусть на вход метода поступает матрица D размера , где n — количество объектов (строк), а m — количество признаков (столбцов). Соответственно каждая ячейка представляет собой количественное значение признака объекта. В результате работы методов главных компонент (МГК) создается матрица , размера , где k < m. Таким образом, количество признаков уменьшается. Главная задача различных МГК заключается в отображении каждого объекта таким образом, чтобы информационная структура исходного множества изменилась минимально. Наша задача – реализовать различные МГК и сравнить их по эффективности сохранения и отображения информации при переходе к пространству меньшей размерности.

Таким образом, в работе будут реализованы и сравнены следующие методы для сокращения размерности данных: метод главных компонент, ядерный метод главных компонент, метод многомерного шкалирования, метод локально-линейного встраивания, метод изометрического отображения, метод упругих карт. Первые три метода широко представлены в публикациях [1,2]. Остановимся подробно на оставшихся [3-5].

Метод  локально-линейного встраивания

Метод локально линейного встраивания является одним из самых современных методов уменьшения размерности данных. Суть этого алгоритма заключается в предположении, что данные в n-мерном пространстве лежат на сглаженном нелинейном многообразии меньшей размерности. Этот метод находит глобальную нелинейную структуру с помощью локально-линейного соответствия. Алгоритм этого метода состоит из трех шагов.

Шаг 1. Найти соседей для каждого вектора D:

– найти расстояния между каждой парой точек;

– для каждого вектора , найти  таких векторов , (), расстояние, до которых наименьшее.

Шаг 2. Создать матрицу , используя следующий алгоритм для каждого :

– создать матрицу , состоящую из соседей вектора ;

– вычесть вектор  из каждого столбца матрицы ;

– рассчитать матрицу по формуле

  (1)

– решить систему линейных уравнений = 1 для вектора w; – присвоить = 0 если i не является соседом j; – для всех остальных элементов i-ой строки матрицы W присвоить  Шаг 3. Найти новую матрицу  меньшей размерности:

– создать матрицу

  (2)

– найти  самых последних (c наименьшим собственным значением) собственных векторов матрицы M;

– присвоить i-ую строку матрицы   собственный вектор снизу (т.е. отбросить самый последний собственный вектор с собственным значением 0).

Метод изометрического отображения

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

Шаг 1. Построить граф соседей

   (3)-(6)

где  d — Евклидово расстояние между двумя векторами;

Шаг 2. Построить матрицу кратчайших расстояний  с помощью алгоритма Дейкстры или Флойда.

Шаг 3. Найти матрицу Грама

  (7)-(8)

где I — единичная матрица; 1 — вектор единиц размера 1. Шаг 4. Разложить матрицу G по МГК (т.е. принять матрицу Грамма G за матрицу ковариации C).

Метод упругих карт

Введем следующие обозначения:

g – количество осей упругой карты (равно количеству координат исходных векторов); w – количество точек на каждой оси; s – количество итераций в алгоритме; len – расстояние между точками на оси; f – коэффициент жесткости карты.

Шаг 1.Создание упругой карты (все узлы упругой карты хранятся в списке h_points).  Каждый узел располагается на одной из осей упругой карты и его координаты рассчитываются следующим образом:

 (9)

Между узлами присутствуют связи. Они хранятся в матрице H.   (10)  (11)   (12)

Шаг 2. Аппроксимация данных – выполняется s раз. В этом цикле:  – упругая карта, на предпредыдущем шаге,  – упругая карта на предыдущем шаге. Релаксация данных – для каждой связи в карте находятся узлы i и j, которые она связывает и расстояние dist между ними. Затем вычисляется величина r сдвига координат по формуле:

  (13) где , а t – это величина связи. Затем соответствующие координаты сдвигаются:    (14)

Шаг 3. Вычисление новых координат – в цикле по всем узлам упругой карты вычисляется вектор влияния исходных данных на этот узел. Для i-го узла упругой карты, если input – массив входных данных, а dist – массив расстояний от входных векторов до текущего узла упругой карты, то вектор влияния равен:

  (15)

Отсюда новые координаты узла карты равны:   (16)

Шаг 4. Проекция на упругую карту – для каждого входного вектора ищется ближайший к нему узел упругой карты. Вектор помещается в него. Затем для этих точек происходит уменьшение размерности. В этом алгоритме оно совершается через метод главных компонент. В итоге получена искомая матрица.

На основе представленных выше алгоритмов разработано программное обеспечение, которое может быть использовано для анализа биомедицинских, экономических и других многомерных данных. Разработана структуры, код программного модуля и реализация его на языке С++ в среде Windows Form.

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

Рис. 1 – Структурная схема системы

 

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

Рис. 2 – Регистрация и вход в систему

 

Методы реализованы с использованием математической библиотеки Eigen: для умножения и нахождения собственных чисел и векторов используются ее высокопроизводительные алгоритмы. Библиотека примечательна тем, что для хранения любых матриц, векторов и блоков используются шаблонизированные алгоритмы с нулевыми затратами на абстракции. В реализации методов используется класс динамической матрицы MatrixXd, который позволяет хранить любое количество строк и столбцов. График рисуется с помощью библиотеки создания графиков gnuplot. При использовании любого метода автоматически строится координатная плоскость, показывающая расположение объекта по двум наиболее главным компонентам. Чтобы отделить значения разных групп объектов на графике, используются цвета: цвет каждого объекта должен подаваться вместе с его признаками.

На вход подается матрица n*m (из n объектов, имеющих m признаков каждый). Наша задача сократить число размерностей с m до k < m так, чтобы терялось бы как можно меньшее количество информации.

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

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

Рис.3 – Главное окно программы

 

В данной работе приведены алгоритмы уменьшения размерности входных данных: рассмотрены самые эффективные существующие методы многомерного анализа, приведены их алгоритмы работы, а также особенности выполнения, варианты реализации; рассмотрен процесс создания программного обеспечения; разработана структуры и код программного модуля, и реализация его на языке С++ в среде Windows Form; Программа  протестирована  на медицинских данных.

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

1. Smith, Lindsay I. A tutorial on Principal Components Analysis [Electronic resource]. – New York : Institute of Technology, 2002. – Access mode: https://goo.gl/dNYm6S
2. Bernhard Scholkopf, Alexander Smola, Klaus-Robert Muller, Kernel Principal Component Analysis, Advances in Kernel Methods-Support Vector Learning, 1999 - [Electronic resource]: [Access mode]: http://pca.narod.ru/scholkopf_kernel.pdf
3. Многомерное шкалирование [Электронный ресурс] : Режим доступа: http://www.statsoft.ru/home/textbook/modules/stmulsca.html
4. Изометрическое Отображение [Электронный ресурс] : Режим доступа: http://www.worklib.ru/dic/изометрическое-отображение/
5. N. Gorban, A. Y. Zinovyev. Principal Graphs and Manifolds/ Chapter 2 in: Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods, and Techniques, Emilio Soria Olivas et al. (eds), IGI Global, Hershey, PA, USA, 2009, pp. 28-59.

Список литературы на английском языке / References in English

1. Smith, Lindsay I. A tutorial on Principal Components Analysis [Jelektronnyj resurs] [Electronic resource]. – New York : Institute of Technology, 2002. – Rezhim dostupa [Access mode] [in English] https://goo.gl/dNYm6S
2. Bernhard Scholkopf, Alexander Smola, Klaus-Robert Muller, Kernel Principal Component Analysis, Advances in Kernel Methods-Support Vector Learning, 1999 - [Electronic resource]: [Access mode]: http://pca.narod.ru/scholkopf_kernel.pdf [in English]
3. Mnogomernoe shkalirovanie [Multidimensional scaling] [Jelektronnyj resurs] [Electronic resource]: : Rezhim dostupa [Access mode]: http://www.statsoft.ru/home/textbook/modules/stmulsca.html [in Russian]
4. Izometricheskoe otobrazchenie[Isometric Display] [Jelektronnyj resurs] [Electronic resource]: Rezhim dostupa [Access mode]: http://www.worklib.ru/dic/изометрическое-отображение/ [in Russian]
5. Zinov'ev, A. Ju. Vizualizacija mnogomernyh dannyh [Visualization of multidimensional data] / A. Ju. Zinov'ev. – Krasnojarsk [Krasnoyarsk]: KGTU, 2000. – 180 s.