Pages Navigation Menu

ISSN 2227-6017 (ONLINE), ISSN 2303-9868 (PRINT), DOI: 10.18454/IRJ.2227-6017
ПИ № ФС 77 - 51217, 16+

DOI: https://doi.org/10.23670/IRJ.2017.59.078

Скачать PDF ( ) Страницы: 94-97 Выпуск: № 05 (59) Часть 3 () Искать в Google Scholar
Цитировать

Цитировать

Электронная ссылка | Печатная ссылка

Скопируйте отформатированную библиографическую ссылку через буфер обмена или перейдите по одной из ссылок для импорта в Менеджер библиографий.
Покидышева Л. И. ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММНЫХ СРЕДСТВ СОКРАЩЕНИЯ РАЗМЕРНОСТИ МНОГОМЕРНЫХ ДАННЫХ / Л. И. Покидышева, М. О. Мадаминова, В. В. Ладнюк // Международный научно-исследовательский журнал. — 2017. — № 05 (59) Часть 3. — С. 94—97. — URL: https://research-journal.org/technical/issledovanie-i-razrabotka-algoritmov-i-programmnyx-sredstv-sokrashheniya-razmernosti-mnogomernyx-dannyx/ (дата обращения: 22.08.2019. ). doi: 10.23670/IRJ.2017.59.078
Покидышева Л. И. ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММНЫХ СРЕДСТВ СОКРАЩЕНИЯ РАЗМЕРНОСТИ МНОГОМЕРНЫХ ДАННЫХ / Л. И. Покидышева, М. О. Мадаминова, В. В. Ладнюк // Международный научно-исследовательский журнал. — 2017. — № 05 (59) Часть 3. — С. 94—97. doi: 10.23670/IRJ.2017.59.078

Импортировать


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

Покидышева Л.И.1, Мадаминова М.О.2, Ладнюк В.В.3

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

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

Аннотация

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

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

Pokidysheva L.I.1, Madaminova М.О.2, Ladnyuk V.V.3

1PhD in Engineering, associate professor, 2undergraduate student, 3postgraduate 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 размера image004, где n — количество объектов (строк), а m — количество признаков (столбцов). Соответственно каждая ячейка представляет собой количественное значение признака объекта. В результате работы методов главных компонент (МГК) создается матрица image009, размера image012, где < m. Таким образом, количество признаков уменьшается. Главная задача различных МГК заключается в отображении каждого объекта таким образом, чтобы информационная структура исходного множества изменилась минимально. Наша задача – реализовать различные МГК и сравнить их по эффективности сохранения и отображения информации при переходе к пространству меньшей размерности.

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

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

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

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

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

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

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

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

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

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

05-06-2017 11-03-50  (1)

решить систему линейных уравнений image034= 1 для вектора w;

присвоить image038= 0 если i не является соседом j;

для всех остальных элементов i-ой строки матрицы W присвоить image044

Шаг 3. Найти новую матрицу image046 меньшей размерности:

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

05-06-2017 11-08-47  (2)

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

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

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

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

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

05-06-2017 11-10-42   (3)-(6)

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

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

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

05-06-2017 11-11-49  (7)-(8)

где I — единичная матрица; 1 — вектор единиц размера image0721.

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

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

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

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

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

05-06-2017 11-13-58 (9)

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

05-06-2017 11-15-03  (10)

05-06-2017 11-15-19 (11)

05-06-2017 11-15-39  (12)

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

image090  (13)

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

image094 image096   (14)

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

image098  (15)

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

image100  (16)

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

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

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

image101

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

 

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

image102

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

 

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

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

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

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

image105

Рис.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.

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Лимит времени истёк. Пожалуйста, перезагрузите CAPTCHA.