Публикация работ сотрудников

А.С.Таскин

Программа для ЭВМ «Программа  для линейного гибридного  анализа и восстановления данных»

Аннотация

В данной работе рассматриваются некоторые базовые методы анализа данных и  вариации их совместного (комбинированного) использования. Описывается разработанная программа для ЭВМ, реализующая рассматриваемые методы прогнозирования (восстановления регрессии) и процедуры их тестирования.

Задача восстановления данных может считаться одной из наиболее сложных задач в области анализа данных, она требует тщательного исследования исходного набора данных и методов, подходящих для анализа. Следует отметить, что эта задача заведомо некорректна и не может быть решена без дополнительных предположений. Существует множество методов анализа и восстановления данных. Они основаны на различных «технологиях»: деревья регрессии [1, 2], анализ и преобразование (или отбор) входных признаков [3, 4], кластеризация данных [5, 6, 7] и др. Выбор метода для решения конкретной задачи зависит, прежде всего, от характера обрабатываемых данных.

Существует множество реализаций алгоритмов анализа данных, например, Intel Math Kernel Library [8], Microsoft Data Mining Algorithms [9], MCL++ [10]. Особо отметим отечественный проект Alglib [11], предоставляющий реализацию алгоритмов на различных языках программирования.

Для же понадобилось создавать ещё одну библиотеку? Дело в том, что разработанная библиотека не является конкурентом или аналогом существующих. Она расширяет семейство алгоритмов за счет новых модификаций. Эти модификации основаны на базовых линейных методах прогнозирования и кластеризации и являются их комбинацией. Программа для ЭВМ «Программа  для линейного гибридного  анализа и восстановления данных» предназначена для построения математических моделей наборов числовых данных рядом линейных методов прогнозирования. А также для построения прогнозов (аппроксимаций) данных с помощью полученных моделей.

Рассмотрим используемые базовые методы (алгоритмы) анализа данных:

·       Линейная регрессия

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

·       Метод k  ближайших соседей (kNN)

·       Метод k средних (k-means)

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

Метод главных компонент разрабатывался для решения задачи наилучшей аппроксимации конечного множества точек прямыми и плоскостями [13]. Первая главная компонента – это такая нормированно-центрированная линейная комбинация исходных признаков, которая среди всех прочих нормированно-центрированная линейных комбинаций признаков обладает наибольшей дисперсией [14].

kNN (k nearest neighbors, k ближайших соседей) – широко используемый алгоритм классификации. Его идея заключается в том, что целевой объект принадлежит к тому классу, представителей которого больше всего среди k ближайших соседей целевого объекта. 

k-means – итерационный алгоритм кластеризации, основанный на разделении объектов согласно их расположению в пространстве входных признаков. Каждая итерация состоит из двух шагов. На первом производится разделение объектов на кластеры: объект принадлежит тому кластеру, расстояние до ядра которого минимально. На втором шаге производится перерасчет ядер кластеров: ядро рассчитывается как центр масс объектов соответствующего кластера.

В разработанной программе для ЭВМ на основе базовых методов анализа данных реализованы следующие гибридные методы прогнозирования:

·       Двойня линейная регрессия

·       Построение проекций на главных компоненты

·       Линейная регрессия с кластеризацией по значению признака

·       Линейная регрессия с кластеризацией методом k-means

·       Линейная регрессия с кластеризацией методом kNN

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

Построение проекций на главных компоненты. Этот метод имеет смысл применять в случае, когда обучающая выборка имеет пропущенные значения (подробнее о проблеме пропущенные значений можно прочитать, например, в [13]). Суть предлагаемого метода заключается в построении проекций на главные компоненты входных данных для перехода к полной (не содержащей пропусков) таблице, и применении линейной регрессии к построенным проекциям для прогнозирования значения выходного (целевого) признака[15].

Метод обеспечивает разбиение выборки  данных на пересекающиеся кластеры. Выбираются признаки, и по их значениям выборка разделяется на кластеры – в один кластер попадут объекты с одинаковым значением данного признака [16, 17]. После того, как для текущего объекта определены кластеры, в которые он входит, требуется найти «лучший» из них – тот, по которому далее будет проводиться регрессионный анализ. Качество кластера можно определять, например, по результатам скользящего контроля методом линейной регрессии.

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

Линейная регрессия с кластеризацией методом kNN. Алгоритм knn используется для формирования кластера для каждого целевого объекта, для чего в пространстве входных признаков вычисляется расстояние между целевым объектом и всеми объектами обучающей выборки и отбирается k его ближайших объектов-соседей. В связи с требованием превышения числа объектов над числом параметров в данной работе рассматривались k большие M.

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

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

Для эмпирической оценки обобщающей способности метода на заданной конечной выборке применяют скользящий контроль [18]. В данной программе  применяется полный скользящий контроль по отдельным объектам (leave-one-out cross validation). Выборка  раз (  – мощность выборки) разбивается на тестовое и обучающее множество. В тестовое множество попадает один объект из выборки, остальные объекты составляют обучающее множество. Каждый объект ровно один раз участвует в контроле. Мощность обучающего множества всего на единицу меньше мощности полной выборки.

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

Для сравнения результатов тестирования используются следующие оценки:

1.     Ошибка классификации, %

Обозначим множество значений признака: F:{f₁…f_k}; истинное значение целевого признака i-го объекта: a_iÎF; прогнозное значение целевого признака i-го объекта: p_i. Определим ошибку классификации как:

2.     Относительная ошибка прогнозирования, %:

где a_i – истинное значение целевого признака i-го объекта, p_i – прогнозное значение целевого признака i-го объекта.

3.     Площадь под ROC-кривой [19]

Программная реализация.

Разработанная программа для ЭВМ представляет собой библиотеку классов, реализующую следующие функции:

·       Применение описанных методов прогнозирования и кластеризации

·       Тестирования методов

·       Оценивание методов

Библиотека предоставляет программный интерфейс для доступа к перечисленным функциям.

На рис.1. представлена диаграмма классов (упрощенная), отображающая структуру программных объектов:

Рис. 1. UML диаграмма классов

Поясним названия классов:

Все классы (соответствующие методам прогнозирования) имеют общие интерфейсные методы, определенные в родительском классе Method.

Часть методов является абстрактными – каждый дочерний класс имеет их собственную реализацию:

Следующие методы являются общими для дочерних классов, то есть имеют единственную реализацию (в родительском классе):

Библиотека разработана на языке C# и использует Framework 4.0. Ниже представлен пример использования программного интерфейса библиотеки для реализации построения модели данных методом линейной регрессии и оценки точности полученной модели.

// Загрузка тестового и обучающего множества из файлов

Set OM = new Set("om.txt");

Set TM = new Set("tm.txt");

// Инициализация метода прогнозирования

Method m = new LinearRegression();

// Будем считать, что целевой признак - последний

int DepVar = OM.ColumnCount - 1;

// Построение модели данных по обучающему множеству

object model = m.GetModel(OM, DepVar);

// Прогнозирование целевого признака тестового множества

// Результат – множество, отличающееся от тестового

// целевым признаком

Set res = m.OnTestSet(model, TM, DepVar);

// Анализ результатов прогнозирования

// через сравнение исходных и предсказанных значений

// целевого признака

Result result = m.analyse(TM, res, DepVar);

Заключение

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

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

Литература

1. Gey S., Nédélec E. Model selection for CART regression trees. IEEE Trans. Inf. Theory 51, 2005. – pp.658–670.

2. Breiman L., Friedman J., Olshen R., Stone C. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984. – 358 p.

3. Aydln T., Giivenir H.A. Regression by Selecting Appropriate Features. Proceedings of TAINN’2000I, zmir, June 21-23, 2000. – pp.73–82.

4. Bair E., Hasle H., Debashis P., Tibshirani R. Prediction by supervised principal components. J Am Stat Assoc, vol.101(119), 2006. – pp.119–137.

5. Tondel K., Indahl U., Gjuvsland A., Vik J. et al. Hierarchical Cluster-based Partial Least Squares Regression (HC-PLSR) is an efficient tool for metamodelling of nonlinear dynamic models. BMC Systems Biology, vol.5(90), 2011.

6. Camps-Valls G. et al. Cyclosporine concentration prediction using clustering and support vector regression methods. Electronic Letters, vol.38(12), 2002. – pp.568–570.

7. Ari B., Guvenir H.A. Clustered linear regression. Knowledge-Based Systems vol.15(3), 2002. – pp.169–175.

8. Intel Math Kernel Library,

http://software.intel.com/sites/products/collateral/XE/Intel_MKL10 -3_Brief_101011-2.pdf

9. Microsoft Data Mining Algorithms,

http://msdn.microsoft.com/en-us/library/ms175595%28v=sql.90%29.aspx

10. MLC++, http://www.sgi.com/tech/mlc/

11. ALGLIB, http://www.alglib.net/

12. Дрейпер Н.Р., Смит Г. Прикладной регрессионный анализ. М.: Издательский дом "Вильямс", 2007.

13.  Россиев А.А. Итерационное моделирование неполных данных с помощью многообразий малой размерности// Диссертация на соискание степени кандидата физико-математических наук, 2000.

14. Айвазян С.А. Прикладная статистика: Классификации и снижение размерности. М.: Финансы и статистика, 1989. – 607 с.

15. Таскин А.С. Линейная регрессия, построенная по проекциям на главные компоненты //  Нейроинформатика, её приложения и анализ данных: Материалы XIX Всероссийского семинара / Под ред. А.Н. Горбаня, Е.М. Миркема. – Красноярск: Сиб. федер. ун-т, 2011. – С. 154-159.

16. Таскин А.С., Неволина С.С. Применение предварительной кластеризации при заполнении пробелов в таблицах данных // Сборник трудов VIII Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии». Томск, 3 - 5 марта 2010 г., ч.1. Томск: СПБ Графикс – С. 223–224.

17. Таскин А.С., Миркес Е.М. Линейная регрессия с кластеризацией по признаку на данных с действительными величинами. Вестник СибГАУ, 2012.

18. Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов. Математические вопросы кибернетики / К.В. Воронцов // под ред. Лупанова О. Б. – М.: Физматлит, 2004. – T. 13. – С.5-36.

19. Конушин, А.С. Введение в машинное обучение [Электронный ресурс] / А.С. Конушин, О.В. Баринова, В.С. Конушин [и др.]. – Москва, 2008. – Режим доступа: http://courses.graphicon.ru/files/courses/vision/2009/cv_2009_06.pdf. – свободный.