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

ВВЕДЕНИЕ.

ГЛАВА I. ПРОБЛЕМЫ ОБРАБОТКИ И ИТЕРАЦИОННОГО МОДЕЛИРОВАНИЯ НЕПОЛНЫХ ДАННЫХ С ПОМОЩЬЮ МНОГООБРАЗИЙ МАЛОЙ РАЗМЕРНОСТИ.

Введение.

1.1. Методы обработки данных с пропус ками.

1.2. Главные кривые.

1.3. Таблицы эмпирических данных.

Задачи эмпирического предсказания.

Требования к методам обработки таблиц эмпирических данных.

1.4. Итерационное моделирование неполных данных с помощью многообразий малой размерности.

Постановка задачи.

ГЛАВА II. ЛИНЕЙНЫЕ И КВАЗИЛИНЕЙНЫЕ МНОГООБРАЗИЯ МАЛОЙ РАЗМЕРНОСТИ.

Введение.

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

II.2. Геометрическая интерпретация.

И.З. Линейные многообразия малой размерности.

Сингулярное разложение матриц с пропусками.

Метод главных компонент для таблиц с пробелами.

11.4. Восстановление данных с использованием линейных моделей.

11.5. Многомерные линейные многообразия.

Ортогонализация базисной системы векторов.

Двумерные линейные модели.

Трехмерные линейные модели.

11.6. Квазилинейные многообразия малой размерности.

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

11.7. Интерполяция.

Интерполяция полиномом небольшой степени.

Интерполяция кубическими сплайнами.

11.8. Экстраполяция.

Проблема экстраполяции, оптимальное аналитическое продолжение ü формула Карлемана.

Интерполяция и оптимальное сглаживание по формуле Карлемана.

11.9. Использование квазилинейных моделей.

НЛО. Механическая интерпретация.

II. 11. Нейронный конвейер для данных с пропусками.

ГЛАВА III. САМООРГАНИЗУЮЩИЕСЯ МНОГООБРАЗИЯ

МАЛОЙ РАЗМЕРНОСТИ.

Введение.

III. 1. Определение главных кривых.

Алгоритм Hastie-Stuetzle.

111.2. Идея самоорганизующихся кривых.

111.3. SOC.

Алгоритм построения SOC.

111.4. S ОМ.

Квадратная SOM.

Гексагональная SOM.

Алгоритм построения квадратной SOM.

Алгоритм построения гексагональной SOM.

111.5. Проблема локального минимума.

Метод отжига.

Многосеточный метод.

111.6. Сглаживание.

Проблема сглаживания.

Кусочно-линейная проекция на ломаную.

Кусочно-линейная проещия на квадратную и гексагональную сетки.

111.7. Механическая интерпретация.

ГЛАВА IV. ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫ.

IV. 1. Факторный и кластерный анализ административных территорий Красноярского края по показателям здоровья и здравоохранения 87

1У.2. Таблица результатов выборов президентов США.91

1У.З. Верификация связей между двумя динамическими системами . 96

IV.4. Сочетанные поражения проводящей системы сердца.98

ЗАКЛЮЧЕНИЕ.100

ЛИТЕРАТУРА.102

Введение

Актуальность проблемы

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

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

Несмотря на перечисленные трудности, данные нуждаются в обработке. Поэтому явно или неявно возникает необходимость в процедуре заполнения пропусков и ремонта (здесь и далее под "ремонтом" подразумевается поиск и исправление неправдоподобных значений) данных - процедуре предобработки.

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

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

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

В настоящем исследовании описывается новый метод моделирования неполных данных с помощью последовательности кривых, обобщающий метод главных компонент. Он также может быть интерпретирован как процедура сингулярного разложения матриц с пробелами. Обсуждаются три версии метода, которые имеют ясную физическую интерпретацию: а) линейный - с моделированием данных последовательностью линейных многообразий малой размерности; б) квазилинейный - с построением "главных кривых" (или "главных поверхностей"), однозначно проектируемых на линейные главные компоненты; в) существенно нелинейный - основанный на построении "главных кривых" ("главных струн и балок") с использованием вариационного принципа; итерационная реализация этого метода близка методу самоорганизующихся карт Кохонена.

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

Цель работы

Целью работы является разработка и экспериментальная проверка технологии итерационного моделирования неполных данных с помощью многообразий малой размерности.

Для достижения цели исследования необходимо решить следующие задачи:

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

II и ^ заполнения пропусков и ремонта искаженных значении;

- разработка методологии нейронного конвейера, заполняющего пропуски в данных и ремонтирующего искаженные значения;

- разработка программного продукта, реализующего предлагаемые технологии и методы;

- экспериментальная проверка при решении реальных задач заполнения пропусков и "ремонта" неполных данных.

Научная новизна

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

Практическая значимость

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

Разработанные в рамках технологии методы ориентированы на следующее применение:

- построение итерационной модели данных, не накладывающей практически никаких ограничений на количество и расположение пробелов в данных;

- предоставление пользователю инструментов, позволяющих заполнять пробелы в данных, обнаруживать и исправлять искаженные (неправдоподобные) значения.

Реализация результатов

Разработанные в диссертации методы реализованы в программных продуктах FAMaster и ModelAnalyzer. Имеется 9 актов о внедрении программ в пробную эксплуатацию.

Апробация работы

Основные положения работы докладывались и обсуждались на VI, VII и VIII Всероссийских семинарах "Нейроинформатика и ее приложения", (Красноярск, 1998, 1999 и 2000 гг.), Международной научно-технической конференции "Нейронные, реляторные и непрерывнологические сети и модели" (Ульяновск, 1998 г.),' Всероссийских научно-технических конференциях "Нейроинформатика" в рамках научных сессий МИФИ (Москва, 1999 и 2000 гг.), XII Международной конференции по нейрокибернетике (Ростов-на-Дону, 1999 г.), V международной конференции "Математика. Компьютер. Образование" (Дубна, 1998 г.). Работа отмечена дипломом 1-ой степени на XXXVII международной научной студенческой конференции "Студент и научно-технический прогресс": Информационные технологии (1999 г, Новосибирск). Разработанные программные продукты FAMaster и ModelAnalyzer демонстрировались на этих конференциях.

По теме диссертации автором опубликовано 14 печатных работ и 6 тезисов докладов.

Структура диссертации

Диссертация состоит из введения, четырех глав и заключения, а также приложений и списка цитируемой литературы из 86 наименований, содержит 14 рисунков и 4 таблицы. Общий объем диссертации (с учетом иллюстраций) составляет 121 страницу.

Выводы:

1. Кластеризация регионов с учетом главных компонент позволила выделить 5 кластеров, четко различающихся по соотношению затрат, обеспеченности кадрами и здоровья населения. □ Затраты '"" □ Здоровье ■ Кадры Н "1 1 1 к I . л-Ш. 1

Кластер 1 Кластер 2 Кластер 3 Кластер 4 Кластер 5

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

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

4. Использованная в работе технология, включающая комбинацию двух математических методов, может быть применена для анализа систем здравоохранения в крупных регионах России, а также, возможно, для анализа функционирования различных объектов системы здравоохранения (ЛПУ, город).

Заключение

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

Приведенный алгоритм заполнения пробелов не требует их предварительного априорного заполнения - в отличие от многих других алгоритмов, предназначенных для той же цели. Однако он требует предварительной нормировки ("обезразмеривания") данных - перехода в каждом столбце таблицы к "естественной" единице измерения. Важное замечание - в задаче обработки данных с пробелами невозможно перейти к однородной задаче центрированием данных.

Большой интерес вызывает вопрос: сколько слагаемых (главных кривых) следует брать для обработки данных? Существует несколько вариантов ответов, но большинство из них подчиняется эвристической формуле: число слагаемых должно быть минимальным среди тех, что обеспечивают удовлетворительное (терпимое) тестирование метода на известных данных. Такой принцип "минимальной достаточности" характерен для многих нейросетевых приложений [32, 33, 47].

Разработанный метод выступает в форме некоторого "анзатца" -предложения, а не в виде серии теорем. Это не случайно - предлагается технология построения правдоподобных оценок пропущенных данных, а не их неизвестного истинного значения. Практическая ценность методов такого рода должна оцениваться и взвешиваться пользователями технологии. Разработано соответствующее программное обеспечение. Оно хорошо зарекомендовало себя при решении трудных задач с большим числом пропущенных данных, а в более простых (стандартных) случаях приводит к тем же результатам, что и классические методы статистического анализа.

В итоге основными результатами работы можно считать следующие.

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

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

3. Разработаны программные продукты FAMaster и Model Analyzer, реализующие предложенные технологии.

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

1. Россиев А.А. Моделирование данных при помощи кривых для восстановления пробелов в таблицах // Методы нейроинформатики: сборник научных трудов / Под ред. А.Н. Горбаня. - Красноярск: КГТУ, 1998, - 6-22.

2. Россиев А.А. Моделирование данных для восстановления пробелов в таблицах // Материалы конференции молодых ученых Института вычислительного моделирования СО РАН, апрель 1998 г. - Красноярск: Р1ВМ СО РАН, 1998, - с. 46-61.

3. Россиев А.А. FAMaster - программный продукт для моделирования неполных данных и заполнения пробелов в них // Нейроинформатика и ее приложения: Тезисы докладов VI Всероссийского семинара, 2-5 октября 1998 г. - Красноярск: КГТУ, 1998, - с. 155.

4. Gorban' A.N., Rossiev А.А. Neural Network Iterative Method of Principal Curves for Data with Gaps. Journal of Computer and System Sciences International, 1999, Vol. 38, No. 5, P. 825-850.

5. Горбань А.Н., Россиев А.А. Итерационный метод главных кривых для данных с пробелами // Проблемы нейрокибернетики. Материалы XII Международной конференции по нейрокибернетике. - Ростов-на-Дону: Изд-воСКНЦВШ. 1999. 323 с. 198-201.

6. Россиев А.А. Нейросетевой подход к итерационному методу главных кривых для данных с пробелами // Материалы конференции молодых ученых Института вычислительного моделирования СО РАН, март 1999 г. -Красноярск: ИВМ СО РАН, 1999. - с. 92-94.

7. Горбань А.Н., Россиев А.А., D.C. Wunsch II, Самоорганизующиеся кривые и нейросетевое моделирование данных с пробелами // 2-я Всероссийская научно-техническая конференция "Нейроинформатика-2000". Сборник научных трудов. 4.1. М.: МИФИ.- 2000. 40-46.

8. З.Зиновьев А.Ю., Питенко А.А., Россиев А.А. Проектирование многомерных данных на двумерную сетку. // 2-я Всероссийская научно-техническая конференция "Нейроинформатика-2000". Сборник научных трудов. 4.1. М.: МИФИ.-2000. 80-88.

9. Айвазян А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Основы моделирования и первичная обработка данных. М.: Финансы и статистика, 1983.-471с.

10. Айвазян А., Енюков И.С, Мешалкин Л.Д. Прикладная статистика: Исследование зависимостей. М.: Финансы и статистика, 1985. - 488с.

11. Айвазян А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Классификация и снижение размерности. М.: Финансы и статистика, 1989.-607с.

12. Айзенберг Л.А. Формулы Карлемана' в комплексном анализе. Первые приложения. Новосибирск: Наука, 1990. 248 с.

13. Афифи А., Эйзен Статистический анализ. Подход с использованием ЭВМ. - М.: Мир, 1982. - 488с.

14. Вапник В.Н. Восстановление зависимостей по эмпирическом данным. - М.: Наука, 1979.-448с.

15. Горбань А.Н., Миркес Е.М., Свитин А.П. Метод мультиплетных покрытий и его использование для предсказания свойств атомов и молекул // Журнал физической химии. - 1992. - Т.66, №6. - с. 1503-1510.

16. Горбань А.Н., Миркес Е.М., Свитин А.П. Полуэмпирический метод классификации атомов и интерполяции их свойств. Препринт ВЦ СО АН СССР №19, Красноярск, 1989, 29с.

17. Горбань А.Н., Новоходько А.Ю., Царегородцев В.Г. Нейросе1;евая реализация транспонированной задачи линейной регрессии, Нейроинформатика и ее приложения: Тезисы докладов IV Всероссийского семинара. Красноярск, 1996, с.37-39.

18. Горбань А.Н., Россиев Д.А. Нейронные сети на персональном компьютере. Новосибирск: Наука, 1996.

19. Ежов А.А., Шумский А. Нейрокомпьютинг и его приложения в экономике и бизнесе. М.: МИФИ, 1998. - 224 с.

20. Кендалл М., Стьюарт А. Многомерный статистический анализ и временные ряды. - М.: Наука, 1976. - 736 с.

21. Кендалл М., Стьюарт А. Статистические выводы и связи. - М.: Наука, 1973. - 900 с.

22. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. - Новосибирск: Наука, 1981. - 157с.

23. Литл Р.Дж.А., Рубин Д.Б. Статистический анализ данных с пропусками. М.: S Финансы и Статистика, 1991.

24. Макаренко Н.Г. Многообразия, погружения и трансверсальность//сб. Проблемы солнечной активности, Ленинград, 1991, 13-28

25. Матюшин Г.В. Сочетанные поражения проводящей системы сердца (распространенность, клинико-электрокардиографические варианты, клиническое течение, прогноз) // Диссертация на соискание ученой степени доктора медицинских наук, КрасГМА, 2000.

26. Нейроинформатика / А.Н. Горбань, В.Л. Дунин-Барковский, Е.М. Миркес и др. Новосибирск: Наука (Сиб. отделение), 1998.

27. Пфанцагль И. Теория измерений. - М.: Мир, 1976. - 246с.

28. Рао СР. Линейные статистические методы. - М.: Наука, 1968. - 548 с.

29. Растригин Л.А., Пономарев Ю.П. Экстраполяционные методы проектирования и управления. - М.: Машиностроение, 1986. - 120 с.

30. Самарский А.А. Введение в численные методы. М.: Наука. Главная редакция физико-математической литературы, 1982. - 272 с.

31. Справочник по прикладной статистике. В 2-х т., под ред Э.Ллойда, У.Ледермана, Ю.Н.Тюрина-М.: Финансы и статистика, 1989, 1990.

32. Тюрин Ю.Н., Макаров А.А. Статистический анализ данных на компьютере / Под ред. В.Э.Фигурнова- М.: ИНФРА-М, 1998. - 528 с , ил.

33. Факторный, дискриминантный и кластерный анализ. - М.: Финансы и статистика, 1989. -215 с.

34. Afifi А.А., Elashoff R.M. Missing observations in multivariate statistics. - J. Amer. Statist. Assoc, 1966, vol. 61. pp. 595-604.

35. Beale E.M., Little R.J. Missing values in multivariate analysis. - J. Roy. Statist. Soc. В., 1975, vol. 37. pp. 129-145.

36. Buck S.F. A method of estimation of missing values in multivariate data. - J. Roy. Statist. Soc. В., 1960, vol. 22. pp. 202-206.

37. Delicado P., Principal Curves and Principal Oriented Points, Tech. rep. 309, Department d'Economia i Empresa, Universitat Pompeu Fabra, 1998.

38. Dempster A.P., Laird N.M., Rubin D.B. Maximum likelihood from incomplete data via the EM-algorithm. - J. Roy. Statist. Soc. p., 1977, vol. 39. pp. 1-38.

39. Dodge Y. Analysis of experiments with missing data. - New York, Wiley, 1985. 498 p.

40. Engelman L. An efficient algorithm for computing covariance matrices from data with missing values. - Communs Statist. В., 1982, vol. 11. p. 113-121.

41. Frane G.M. Some simple procedures for handling missing values in multivariate analysis. - Psychometrika, 1976, vol. 41. pp. 409-415.

42. Glasser М. Linear regression analysis with missing observations among the independent variables. - J . Amer. Statist. Assoc, 1964, vol. 59. p. 834-844.

43. Gleason T.C., Staelin R. A proposal for handling missing data. - Psychometrika, 1975,vol. 40. pp. 229-252.

44. Gorban A.N., Novokhodko A.Yu. Neural Networks In Transposed Regression Problem, Proc. INNS WCNN '96.

45. Gorban A.N., Waxman C. Neural Networks for Political Forecast. Proceedings of the WCNN'95 (World Congress on NeuralNetworks'95, Washington DC, July 1995), PP.176-178.

46. Hartley H.O., Hocking R.R. The analysis of incomplete data. - Biometrics, 1971, vol. 27. pp. 783-808.

47. Hastie T, and Stueltze, Principal Curves, Journal of the American Statistical Association, vol. 84, no. 406, pp. 502-516, 1989.

48. Hastie T. Principal Curves and Surfaces, PhD thesis, Stanford University, 1984.

49. Hocking R.R., Marx D.L. Estimatiom with incomplete data: an improved computational method and the analysis of nested data. - Communs Statist. A., 1979, vol. 8. pp. 1151-1181.

50. Huseby J.R., Schwertman N.C., Allen D.M. Computation of the mean vector and dispersion matrix for incomplete multivariate data. - Communs Statist. В., 1980, vol. 9. pp. 301-309.

51. Kegl В., Krzyzak A., binder T. and Zeger K. Principal Curves: Learning and convergence, in Proceedings of IEEE International Symposium on Information Theory, p. 387, 1998.

52. Kegl В., Krzyzak A., Linder Т., and Zeger K., Learning and Design of Principal Curves, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999.

53. Kohonen T. Self-Organizing Maps. Springer: Berlin - Heidelberg, 1997.

54. Kramer M.A. Nonlinear principal component analysis using autoassociative neural networks. AIChE Journal. 1991. V.37, No. 2. PP. 233-243.

55. LeBlank M., Tibshorany N. Adaptive principal surfaces. Journal of the American Statistical Association. 1994, Mar. V. 89, No. 425. PP. 53-64.

56. Little R.J., Rubin D.B. Statistical analysis with missing data. - New York, Wiley, 1987.430 р.

57. Little R.J., Schlushter M.D. Maximum likelihood estimation for mixed continuous and categorical data with missing values.- Biometrika, 1985, vol. 72. pp. 497-512.

58. Little R.J., Smith P.J. Editing and imputation for quantitative survey data. - J. Amer Statist. Assoc, 1987, vol. 82. pp. 58-68.

59. Mardia K.V., Kent J.T, and Bibby J.M. Multivariate Analysis. London: Academic Press, 1979.

60. Srivastava M.S. Multivariate data with missing observations. - Communs Statist. Theory and Method, 1985, vol. 14. pp. 775-792.

61. Tibshirani R., Principal Curves revisited, Statistics and Computation, vol. 2, pp. 183-190, 1992.

62. Titterington D.M., Jiang J.M. Recursive estimation procedures for missing data problems. -Biometrika, 1983, vol. 70. pp. 613-624.

63. Walsh J.E, Computer-feasible method for handling incomplete data in regression analysis.-J. of ACM, 1961, vol. 18. pp. 201-211.

64. Wilks S.S. Moments and distributions of estimates of population from fragmentary samples. -Ann. Math. Statist., 1932, vol.3, pp. 163-195.