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

На правах рукописи

Цурко Варвара Владимировна

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

данным

Специальность 05.13.18 — «Математическое моделирование, численные методы и комплексы программ»

2 5 MAP 2015

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва — 2015 3

005561053

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте проблем управления им. В.А.Трапезникова Российской академии наук

Научный руководитель: Михальский Анатолий Иванович,

доктор биологических наук, кандидат технических наук, старший научный сотрудник, ведущий научный сотрудник ИПУ РАН Официальные оппоненты: Ромаиюха Алексей Алексеевич,

доктор физико-математических наук, профессор, ведущий научный сотрудник, заместитель директора ИВМ РАН

Куликов Сергей Михайлович,

кандидат технических наук,

зав. информационно-аналитическим

отделом ФГБУ ГНЦ МЗ РФ

Ведущая организация: Федеральное государственное бюджетное

образовательное учреждение высшего образования «Московский государственный университет имени М. В. Ломоносова»

Защита состоится 27 апреля 2015 г. в 14 часов на заседании Диссертационного совета Д 002.226.01 при Федеральном государственном бюджетном учреждении науки Институте проблем управления им. В.А.Трапезникова РАН, расположенном по адресу: 117997, Москва, ул. Профсоюзная, д. 65.

С диссертацией можно ознакомиться в библиотеке ИПУ РАН и на официальном сайте http: //www. ipu. ru/.

Автореферат разослан «_»_2015 г.

Ученый секретарь диссертационного совета ^

кандидат технических наук Кочетков С. А.

Общая характеристика работы

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

Среди многих задач автоматизированной обработки многомерных эмпирических данных актуальна проблема выделения наиболее значимых, существенных для решаемой задачи признаков1. Эта проблема важна при анализе популяционных данных с целью выявления закономерностей заболеваемости и смертности, при поиске параметров, существенных для классификации состояний производственного процесса, а также в различных задачах медицинской диагностики, анализа изображений и текстов. Исходные данные, возникающие в таких задачах, обычно характеризуются высокой размерностью. Количество признаков, например, в задачах распознавания текстов может достигать порядка 101 — 107, причем значимыми является лишь небольшая часть из них2. Данные, получаемые в биологических экспериментах на микрочипах, характеризуются экспрессией десятков тысяч генов, а число доступных для анализа объектов исчисляется сотнями.

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

'Ulum Д., Langley P. Selection of relevant features and examples in machine learning // Al. 1997. V. 97(1-2). P. 245 - 271.

-Lewis O. D. Feature selection and feature extraction for text cauterization // Proceedings of Speech and Natural Language Workshop. Morgan Kaufmann Publishers, 1992. P. 212 217.

решая задачу по сложности сопоставимую с исходной, что сильно снижает статистическую достоверность результата.

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

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

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

■"'Литиям С. Л., Кухштапср В.М., Пнюкпн U.C., Мсшалкин J1.Л. Прикладная статистика: классификация и снижение ргпмсрностм. М: Финансы и статистика, 1989.

JKuIlback S., Lciblcr R. Л. On information and sufficiency // The Annals of Mathematical Statistics. 1951. V. 22. No. 1. Р. 79-K6.

5Novovicova J., Pudil P.. Kittler J. Divergence based feature selection for multimodal class densities .'/' IliHIi Transactions on Pattern Analysis and Machine Intelligence. 1996. V. 18(2). P. 218223.

C'oct/ce К M. Correcting Kullback-Leibler Distance for Feature Selection // Pattern Recognition Letters. 2005. V. 26. No. II. P. ¡675 5683.

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

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

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

Данная цель определила основные задачи работы:

1) сформулировать задачу отбора признаков в терминах оптимизации функционала среднего риска;

2) разработать метод оптимизации предложенного функционала среднего риска по эмпирическим данным;

3) реализовать метод оптимизации функционала среднего риска по эмпирическим данным в виде вычислительного алгоритма;

4) применить разработанный алгоритм для решения практических задач.

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

6Вашшк В. II.. Чсрнонепкнс Л. Я. Теория распознавания обраюв. М.: Паука, 1474.

7K.oItchinskii V., Panclienko D. llademacher processes and bounding ihe risk of function learning, lligli Dimensional Probability, 11 / J-d. by D. I:. Gine, J.Wellner. Uirkhauser, 1999. P. 443 457.

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

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

Основные положения, выносимые на защиту:

1) постановка задачи выбора признаков как задачи максимизации среднего риска;

2) адаптация оценок равномерного уклонения среднего и эмпирического рисков, основанных на теории Вапника-Червонснкиса, и оценок, основанных на Радемахсровской сложности, для решения поставленной задачи;

3) теорема о величине Радемахсровской сложности в классе байесовских оценок гистограмм;

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

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

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

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

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

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

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

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

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

Метод контрастирования распределений, разработанный в диссертации, успешно внедрен в практику работы компании ООО «Ай Эм Эс Хэле». Внедрение метода позволило сократить количество признаков, необходимое для достоверного разделения аптек на классы по объемам продаж. Результаты внедрения подтверждены соответствующим актом.

Достоверность и обоснованность результатов. Достоверность результатов обеспечивается математическими доказательствами теорем и утверждений.

Обоснованность выводов анализа данных о заболеваемости и смертности проводилась путем сопоставления результатов с опубликованными медицинскими данными. Результаты были доложены на специализированных конференциях и опубликованы в профильных изданиях [1,2,10].

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

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на III Международной конференции «Математическая биология и биоинформатика» (Пущино, 2010); XV, XVI Международной научно-практической конференции «Пожилой больной. Качество жизни» (Москва, 2010, 2011); Международной конференции "14th Applied Stochastic Models and Data Analysis International Conference (ASMDA2011)" (Италия, Рим, 2011); Международной научной школе «Моделирование и анализ безопасности и риска в сложных системах» (Санкт-Петербург, 2011); Международном симпозиуме "Applied Mcthods of Statistical Analysis. Simulations and Statistical Inferencc (AMSA)" (Новосибирск, 2011); Международной конференции "Statistical Models and Methods for Reliability and Survival Analysis and Thcir Validation" (Франция, Бордо, 2012); научном ce-

минаре «Математическое моделирование и системная биология» под руководством д.т.н. В. Н. Новосельцева и д.ф.-м.н. А. А. Романючи (ИПУ РАН и ИВМ РАН, Москва, 28 ноября 2012); VII Международной конференции «Управление развитием крупномасштабных систем» (Москва, 2013); ХП Всероссийском совещании по проблемам управления (Москва, 2014); XVI Международной конференции "Artificial Intelligence: Methodology, Systems, Applications" (Болгария, Варна, 2014).

Публикации. Основные результаты диссертационной работы опубликованы в 10 работах [1-10], одна из которых является публикацией в издании из списка Scopus [3], а две являются статьями в ведущих рецензируемых научных журналах и изданиях, рекомендованных ВАК РФ [1,2].

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

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

Основное содержание работы

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

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

В разделе 1.1 представлен обзор задач восстановления зависимостей по эмпирическим данным. Задачи классификации, регрессионного анализа, восстановления плотностей распределений сформулированы в общем виде

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

В разделе 1.2 рассмотрена проблема отбора признаков. Приведены различные определения понятия «значимый признак», дан обзор и классификация существующих методов.

В разделе 1.3 описана задача оценки качества обучения, дан обзор оценок обобщающей способности, начиная с равномерных по классу решающих функций оценок, полученных В.Н. Вапником и А. Я. Червоненкисом в 70-х годах XX века и положивших начало развитию этой теории, и заканчивая недавними работами, в которых получены оценки, адаптированные к данным.

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

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

Пусть X € Ш" — множество объектов, У = {0,1} — множество классов, Р — неизвестное вероятностное распределение на X х У, (х, у) — случайная пара из распределения Р. Объект х = (.т(1),..., х(п)) — «-мерный вектор, координаты которого имеют смысл признаков.

Пусть область значения координаты х(з) разделена на т;- интервалов, тогда к - П"=1 Т1 — число интервалов п-мерной гистограммы, <п,..., о* — п-мерные интервалы деления области значений х. Если априорное распределение вероятностей равномерно на ¿-мерном симплексе, то (р'у(х) — байесовская оценка п-мерной гистограммы распределения в классе у

;=1 + К

где у = 0,1,1{.т е <т, } — индикатор, значение которого равно 1, если х принадлежит интервалу (Т-1, и равно 0 иначе, 1У — размер независимой выборки

из класса у, п'{ — количество элементов выборки из класса //, попавших в интервал (71 гистограммы.

Класс F — класс байесовских оценок гистограмм, построенных для всевозможных подмножеств множества признаков.

В диссертации мера различия гистограмм вводится через средний риск, для этого определяется функция штрафа

= -//Ь^оО'О - (1 - у)1нУ,'(.т)

и ее математическое ожидание — функционал среднего риска

9\) = -Е,„ [г/ 1п(х) + (1 - у) 1и ^(х)'] . (1)

Средний риск (1) имеет смысл взвешенной по априорному распределению у энтропии плотностей ^'¿(х) и р'{(х) относительно распределения случайной величины х в классах 1 и 0. В диссертации показано, что задача максимизации среднего риска по ¡^'/(х-) е F соответствует поиску в

заданном классе Г двух оценок, таких что найденная оценка -¿иО'') должна максимально отличаться в смысле информационного расстояния Кульбака-Лсйблера от истинной плотности х в классе 1, а найденная ^{(х) должна максимально отличаться от истинной плотности распределения х в классе 0. Максимизируя средний риск (1) по классу гистограмм, построенных на разном числе признаков, получим набор признаков, для которого байесовские оценки максимально отличаются в смысле смешанной энтропии.

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

Введем понятие функционала эмпирического риска.

Пусть х\----— выборка из класса у, у = 0,1. Тогда байесовские

оценки вероятности попадания в ?'-ый интервал для каждого класса имеют вид

71? + 1

+ к '

где у = 0,1, пУ = Ч*1! е <7/}.

Выполнены ограничения

О <с< ¿ = 1Л с-

к + тах(/(), /1)'

¿=1

Функционал эмпирического риска равен среднему по выборке значению функции штрафа

VI) = -г4г Е +"" • (2)

I о + '1

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

В Утверждении 1 оценена функция роста рассматриваемой системы множеств.

Утверждение 1. Пусть /г(х) — гистограмма, построенная для к фиксированных интервалов, Н — множество таких гистограмм. Для функции роста системы множеств Б = {ж: 1г{х) > с,Н £ Н} справедлива оценка ть'(21) < (20А:.

В Утверждении 2 приведена нижняя оценка функционала среднего риска для поставленной задачи.

Утверждение 2. В классе байесовских оценок гистограмм Г с вероятностью не менее 1 — г/ справедлива нижняя оценка для функционала среднего риска

- 21п(А; + тах(/о,/х))у-/0 + ¿1 - 1--'

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

Пусть й"]1, ■.., ¿J,..., ¿¡i — последовательность независимых одинаково распределенных случайных величин, принимающих значения + 1 и -1 с вероятностью 1/2 и независимых от выборки (.г",..., ,: с},..., х}^. Тогда штраф Радемахсра8 (Радемахеровская сложность) имеет вид

vli-viei'l'» + «1

гас АУ = Z/Li Щх] € a,}, i = 17к, у = 0,1.

Пусть Д!/ - (А'(,..., Af'j. Чтобы найти величину штрафа Радсмахера, в диссертационной работе сформулированы и доказаны Лемма 1 и Теорема 1.

Лемма 1. В классе байесовских оценок гистограмм F величина Q(RA») = шах]Гд>^(,)

равна

1. если 3t: А", < 0 и АУ < 0. г = 17к. то

к

Q{F. А1') = А:> In (1 - с(к - 1)) +

где j = arg max* A'/

2. если А» < 0, г = М и Д? > 0. г = s + 1. к

U Q(F1Д») = ¿Д}'luc+ £

' = 1 i = S+l =.s+l A j

"Kollchinskii V. Rademacher penalties and structural risk minimization // I1:HI: Transactions 011 Information Theory. 2001. V. 47. No. 5. P. 1902 1914.

Теорема 1. В классе байесовских оценок гистограмм Р штраф Радемахера вычисляется по формуле

щР) = щах Д1) + Д°), -Д1) + -Д")) • «о + «1

В Утверждении 3 приводится нижняя оценка рассматриваемого функционала среднего риска, использующая штраф Радемахера.

Утверждение 3. В классе байесовских оценок гистограмм Г с вероятностью не менее 1 - ч справедлива нижняя оценка для функционала среднего риска

¿1) > <УП - 2Я(Р) - ----- (4)

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

Пусть объект х = (,7:(1),... ,.т(п)) описывается п признаками (координатами), С„ = {1,...,»} - множество всех признаков, вектор тгС,ЛХ) состоит из подмножества С,„ С Сп координат вектора х.

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

На первом шаге происходит перебор всех признаков по одному, выбирается признак г, максимизирующий эмпирический риск (2):

г = агй^таХ([Ме (у>?,(*-{./}(:Г))>У^Ш(*)))•

Выбранный признак г включается в первое построенное подмножество признаков С\ = {¿}.

На втором шаге перебираются всевозможные пары признаков, в которых один признак фиксирован на предыдущем шаге, а второй признак не равен первому. Выбирается пара признаков {г,.?'}, доставляющая максимум эмпирическому риску. Строится подмножество признаков = {г,;}}.

На последующих шагах процесс повторяется и останавливается, когда все признаки исчерпаны и построена последовательность подмножеств множества признаков С\ С С?, С • • • С С,,.

На втором этапе алгоритма выбора контрастирующих признаков для каждого подмножества С; из построенной последовательности вычисляется эмпирический риск (2) и оценка среднего риска. Для оценки среднего риска может использоваться оценка (3), следующая из теории Вапника-Чсрвоненкиса, или оценка (4), основанная на Радсмахсровской сложности. Выбирается подмножество признаков С;, доставляющее максимум оценке среднего риска.

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

В разделе 3.1 обоснована актуальность задачи и приведено подробное описание данных. Исследовались индивидуальные, нспсрсонифициро-ванные данные о сочетанной заболеваемости и смертности на территории США за 1980 год9. Объектами выборки являлись случаи смерти, для каждого случая указаны возраст смерти, дата смерти, причина смерти и список сопутствующих заболеваний. Анализ проводился для старшей возрастной группы: люди, умершие после 65 лет (включительно). Размер выборки составлял более 1,1 млн. человек. Выборка делилась на две группы: в «раковую» группу входили люди, у которых был рак определенной локализации, в «нераковую» группу входили люди, у которых рак диагностирован не был. Сопутствующие заболевания, которые человек имел в конце жизни, группировались в блоки согласно МКБ-9 классификации и составляли признаковое описание задачи. Всего в данных присутствовало 92 возможных блока сопутствующих заболеваний.

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

'Mortality Data, Multiple Cause-of-Dealh Public-Use Data Files. URL: http://www.cdc. gov/nchs/data_access/VitalStatsOnline,htm#Mortality_Multiple

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

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

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

Максимум как оценки среднего риска (3), так и оценки (4) достигается на первых тринадцати блоках сопутствующих заболеваний из таблицы 1. В список заболеваний, попали заболевания, имеющие высокую летальность: ишемическая болезнь сердца, гипертония, цсрсброваскулярныс заболевания, болезни артерий, артериол, капилляров, ВИЧ. Эти заболевании больше распространены среди людей, у которых не диагностирован рак. и являются конкурирующими причинами смерти. Среди сопутствующих заболеваний также были выделены «другие болезни пищеварительной системы», являющиеся факторами риска возникновения рака.

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

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

Таблица 1. Выбор блоков сопутствующих заболеваний

Название блока сопутствующих заболеваний Оценка Оценка |

(3) (4)

Нет «других форм болезни сердца» 0,6070 0,6448

Нет «ВИЧ, полиомиелит и других вирусных 0,9123 0,9745

заболеваний центральной нервной

системы, не передаваемых членистоногими»

Нет «ишсмичсской болезни сердца 1,1426 1,2255

и болезней легочного кровообращения»

Нет «нсспецифичсских патологических 1,2919 1,3943

проявлений»

Нет «болезней артерий, артсриол и капилляров» 1,458 1,5775

Нет «других болезней пищеварительной 1,5089 1.6442

системы»

Нет «церсброваскулярных болезней» 1,5899 1,7394

Нет «симптомов и плохо определенных условий» 1,6441 1,7998

Нет «вирусных заболеваний. 1,6906 1,8546

сопровождающихся сыпью»

Нет «риккстсиозов и других болезней, 1,7454 1,9197

передаваемых членистоногими»

Нет «гипертонической болезни» 1,7848 1,9606

Нет «заболеваний других эндокринных желез» 1,8079 1,9831

Есть «другие бактериальные заболевания» 1,8292 2,0115

Нет «других болезней кишечника и брюшины» 1,8193 2,0074

Нет «других болезней мочевыделитсльной 1,8096 2,0006

системы»

Есть «другие и неуточненные эффекты воздействия 1,7989 1,9919

внешних причин, осложнения хирургических и

терапевтических вмешательств»

Нет «открытых ран головы, шеи и туловища» 1,7875 1,9823

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

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

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

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

В разделе 4.2 обсуждаются особенности применения алгоритма выбора контрастирующих признаков к данным, продемонстрировано преимущество оценки, основанной на Радсмахсровской сложности, по сравнению с оценкой среднего риска Вапника-Чсрвонснкиса в силу сильной завышенное™ последней.

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

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

Таблица 2. Результаты применения алгоритма выбора контрастирующих

признаков

Подмножества признаков Эмпирический риск Оценка среднего риска (4)

1 10 4,799 2,1275

2 10, 1 6,884 2,9038

3 10, 1, 4 10,1013 1,9058

4 Ю, 1,4, 5 13,4695 0.6662

5 Ю, 1,4, 5, 2 16,8365 -0.4554

6 10, 1,4, 5, 2,7 20,2038 -1,5773

7 10, 1,4, 5, 2, 7,3 23,5711 -2,6551

8 10, 1, 4, 5, 2, 7, 3, 6 26,9384 -3,738

9 10, 1,4, 5, 2, 7,3,6,8 30,3057 ^,8208

10 10, 1,4, 5, 2, 7,3,6, 8,9 33,673 -5,9037

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

На рисунке 1 представлены ошибки классификации на различных наборах параметров, построенных в результате работы алгоритма выбора контрастирующих признаков. По горизонтальной оси отложены наборы параметров, на которых строился классификатор, по вертикальной — значение доли ошибочно классифицированных объектов наивным байесовским классификатором. Минимум ошибки на обучении (6,4%) достигается на паре параметров с номерами 10 и 1, что совпадает с результатом, полученным с помощью алгоритма выбора контрастирующих признаков. Ошибка клас-

12,5 %-

10,0 %-

7,5 % -

5,0 %-

2,5 %-

0,0

Ошибка на обучении ] Ошибка на контроле

о ю CN СО «э СО

о" ю" см" со" со"

о" Т-Г 1ГЗ Cvi со"

т— о" Л— in см" к

о" Ю CN

т— о" х— о" 1— ю"

СП

coco со

CN LO -чГ

Рисунок 1. Ошибки классификации на различных наборах признаков

сификации контрольной выборки в этом случае составляет 8%. На других наборах параметров ошибка классификации выше как на обучении, так и на контроле.

Результаты, полученные с помошыо алгоритма выбора контрастирующих признаков, сравнивались с результатами, полученными с использованием других популярных алгоритмов отбора признаков. Результаты сравнения приведены в таблице 3. К данным задачи были применены алгоритм RELIEF10, два метода отбора признаков на основе корреляции: CFS11 и ме-

"!Kira К., Rendcll L. The feature selection problem: Traditional methods and a new algorithm // In Tenth National Conference on Artificial Intelligence. MIT Press, 1992. P. ¡29 134.

'11 iall M. A. Correlation-based feature selection for discrete and numeric class machine learning // In Proceedings of Seventeenth international Conference on Machine Learning (ICML-00). Morgan Kaufmann Publishers, 2000. P. 359-366.

Таблица 3. Сравнение алгоритмов отбора (преобразования) признаков

Алгоритм отбора признаков Подмножества признаков Доля правильно классифицированных объектов

Выбор контраструюших признаков 10, 1 0,92561

RELIEF 10, 2, 7, 3, 5, 1, 8, 6 0,910976

Отбор признаков на основе корреляции CFS 4,5,6, 10 0,910976

Отбор признаков на основе корреляции IBM 3,7 0,730488

Скоректированное расстояние Кульбака-Лсйблера 10, 1,4, 5, 2,7 0,893902

Принцип главных компонент 3 компоненты 0,895122

Метод независимых компонент 10 компонент 0,876829

тод отбора признаков IBM SPSS Modeler12, отбор признаков, основанный на вычислении скорректированного расстояния Кульбака-Лсйблсра между

l2IBM SPSS Modeler 14.2 Algorithms Guide. URL: ftp://public.dhe.ibm.сои/ software/analytics/spss/documeiitation/modeler/

распределениями13. Также к признаковому описанию применялись принцип главных компонент14 и метод независимых компонент1-"1.

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

Сравнение результатов работы алгоритмов отбора признаков показывает, что с помощью алгоритма, предложенного в диссертации, было выбрано меньшее количество признаков и были достигнуты наиболее точные результаты классификации, что демонстрирует его преимущества над другими рассмотренными методами отбора признаков.

Заключение

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

1. Задача выбора признаков формализована как задача максимизации среднего риска на основании эмпирических данных.

2. Проведена адаптация оценок равномерного уклонения эмпирического риска от среднего, основанных на теории Вапника-Чсрвонснкиса, и оценок, основанных на Радсмахсровской сложности, для максимизации среднего риска путем максимизации эмпирического риска.

'Ч'оег/ее K.M. Correcting Kullback-Leibler Distance for Feature Selection // Pattern Recognition Leiters. 2(105. V. 26. No. 11. P. 1675-16X3.

l4.lollill'e I T. Principal component analysis. New York: Springer-Verlag, I486.

'•Ч'ошоп P. Independent component analysis. Л new concept // Signal Processing. 1994. V. 36. P. 2X7 314.

3. Доказана теорема о величине Радсмахсровской сложности в классе байесовских опенок гистограмм.

4. Предложен метод выбора контрастирующих признаков. Разработан программный комплекс, реализующий предложенный алгоритм.

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

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

Публикации автора по теме диссертации

Публикации из списка ВАК

1. Михальский А. И., Цурко В. В. Возрастные особенности причин смерти и сопутствующих болезней //Клиническая геронтология. 2014. N0. 1-2. С. 35-40.

2. Цурко В. В., Михальский А. И. Статистический анализ связи рака и сопутствующих заболеваний // Успехи Геронтологии. 2013. Т. 26. N0. 4. С. 766-774.

Публикация в издании из списка Scopus

3. Tsurko V., Michalski A. Feature Selection by Distributions Contrasting // Artificial Inlclligcncc: Methodology, Systems and Applications, G. Agre, P. Hitzcr, A. A. Krisnadhi, S. O. Kuznctsov (eds.), LNA1 8722. SpringerVerlag, 2014. P. 139-149.

Прочие публикации

4. Цурко В. В., Михальскии А. И. Исследование влияния сопутствующих заболеваний на возникновение злокачественных новообразований // XII Всероссийского совещания по проблемам управления (ВСПУ 2014). Москва, 16-19 июня 2014 г.: Труды. [Электронный ресурс] М.: ИПУ РАН, 2014. С. 6800-6810.

5. Цурко В. В., Михальскии А. И. Математическое моделирование смертности по причинам при сочстанной заболеваемости // Доклады III Международной конференции Математическая биология и биоинформатика. г. Пущино, 10-15 октября 2010 г.: Сборник докладов. М.: МАКС Пресс, 2010. С. 260-261.

6. Tsurko V.V., Michalski A.I. Comorbidity in Cancer Mortality Analysis // Proceedings of the 14th Applied Stochastic Models and Data Analysis International Conference - ASMDA2011, Rome, Italy, 6-10 June 2011. 2011. P. 1373.

7. Tsurko V. V, Mikhalsky A. I. Investigation Of Canccr Death Risk In The Comorbidity Case // Международная Научная Школа Моделирование и Анализ Безопасности и Риска в Сложных Системах (МАБР-2011), Санкт-Пегсрбург, 28 июня - 2 июля 2011 г. 2011. С. 399-404.

8. Tsurko V., Michalski A. Investigation of canccr mortality on the basis of historical comorbidity data // Proceedings of the International Conference on Statistical Models and Methods for Reliability and Survival Analysis and Their Validation - S2MRSA, Bordeaux, France, 4-6 July 2012. 2012. P. 236-239.

9. Tsurko V., Michalski A. Statistical analysis of mortality-eomorbidity links // Proceedings of the International Workshop "Applied Methods of Statistical

Analysis. Simulations and Statistical Inference" - AMSA'2011, Novosibirsk, Russia, 20-22 September, 2011. Novosibirsk: Publishing house of NSTU, 2011. P. 63-70.

10. Tsurko V. V., Michalski A. I. Statistical analysis of the relationship between cancer and associated diseases // Advances in Gerontology. Springer-Verlag, 2014. V. 4. No 3. P. 205-212.

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

В работах [1,5] автором проанализированы данные медицинской статистики, показаны сопутствующие заболевания, наиболее часто связанные с различными причинами смерти в различных возрастных группах. В работах [2,4,8,10] автором адаптированы под решаемую задачу оценки среднего риска, основанные на теории Вапника-Чсрвонснкиса. В работах [6,7,9] автором получены основные неравенства и предложен алгоритм выбора контрастирующих признаков. В работе [3] автором доказана теорема о величине штрафа Радсмахсра, сформулированы и доказаны основные результаты.

Научное издание

Цурко Варвара Владимировна Разработка численных методов выбора контрастирующих признаков по эмпирическим данным

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 24.02.2015. Формат 60x90/16. Усл. псч. л. 1,69. .Уч.-изд. л. 1,0. Тираж 100 экз. Заказ №. 18

Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова Российской академии наук 117997, ул. Профсоюзная, д. 65 Россия, Москва E-mail: snv@ipu.iTi http://www.ipu.ru