Ёволюционный подход к выделению информативных признаков в задачах анализа медицинских данных

√лавна€ ї ѕубликации ї Ёволюционный подход к выделению информативных признаков в задачах анализа медицинских данных

”ƒ  004.8 »скусственный интеллект. 2008. є3. —.105-112.

Ќовоселова Ќ.ј.1, ћастыкин ј.—.2, “ом ».Ё1.

1ќбъединенный институт проблем информатики ЌјЌ Ѕеларуси, ћинск, Ѕеларусь

2Ѕелорусский государственный медицинский университет, ћинск, Ѕеларусь

novosel@newman.bas-net.by

 

Ёволюционный подход к выделению информативных признаков в задачах анализа медицинских данных

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

 

 

¬ведение

ќдним из важнейших этапов процесса извлечени€ знаний из большого объема накопленных медицинских данных €вл€етс€ этап предобработки исходных данных, включающий выделение информативных признаков. Ѕлагодар€ широкому распространению компьютерных технологий, в базах данных медицинских учреждени€х накапливаетс€ большое количество разнородной медицинской информации, больша€ часть которой напр€мую не св€зана с решением какой-либо конкретной задачи, как например задачи классификации или прогноза. ¬ этом случае исключение из рассмотрени€ избыточных и несущественных признаков позвол€ет не только повысить точность решени€ задачи и сократить врем€ на поиск решени€, но и получить более простой и пон€тный результат [1].

¬ данной работе рассматриваетс€ применение эволюционного подхода к выделению признаков дл€ дифференциальной диагностики подтипов транзиторных ишемических атак (“»ј). »сходными данными в этом случае €вл€етс€ набор клинических и персональных признаков, характеризующих пациента, который в свою очередь относитс€ к одному из четырех классов [2]. ѕараллельно с процессом выделени€ признаков решаетс€ задача классификации, целью которой €вл€етс€ предсказание класса дл€ конкретного объекта данных, основыва€сь на значени€х предсказывающих признаков. «адача выделени€ признаков рассматриваетс€ как оптимизационна€ задача с двум€ оптимизируемыми критери€ми: минимизаци€ ошибки классификации и количества отобранных предсказывающих признаков. ƒл€ решени€ этой задачи предлагаетс€ использовать специально разработанный генетический алгоритм (√ј) дл€ многокритериальной оптимизации [3]. ќсновное преимущество применени€ этого алгоритма дл€ выделени€ признаков состоит в возможности получени€ множества оптимальных решений с учетом двух критериев, так называемых недоминируемых решений многокритериальной оптимизационной задачи. “акой подход позвол€ет избежать изначального жесткого определени€ весовых коэффициентов дл€ отдельных критериев. ¬ыбор окончательного множества предсказывающих признаков из различных недоминируемых комбинаций может осуществл€тьс€ либо экспертом согласно его знани€м и опыту, либо автоматически с использованием тестового набора данных.

 

1. «адача многокритериальной оптимизации

Ѕольшинство решаемых практических задач предполагают поиск решени€, €вл€ющегос€ оптимальным согласно нескольким критери€м. ќднако, большинство методов, используемых дл€ решени€ этих задач, использует единый, составной оптимизируемый критерий. ¬ этом случае задача многокритериальной оптимизации сводитс€ к одной или нескольким задачам однокритериальной оптимизации. —уществует огромна€ разница между двум€ этими задачами. ѕри однокритериальной оптимизации осуществл€етс€ поиск единственного оптимального решени€. ѕри многокритериальной оптимизации осуществл€етс€ поиск нескольких оптимальных решений, что позвол€ет равным образом учитывать все оптимизируемые критерии [3]. ѕосле завершени€ оптимизации пользователь имеет возможность выбрать наилучшее с его точки зрени€ решение, представл€ющее собой компромисс между несколькими противоречивыми критери€ми.

ѕоиск множества решений при многокритериальной оптимизации основываетс€ на концепции ѕарето-оптимальности. ќсновна€ ее иде€ заключаетс€ в определении пон€ти€ недоминируемости дл€ отдельных решений оптимизационной задачи. –ешение x1 доминирует другое решение x2, если одновременно выполн€ютс€ два следующих услови€:

1. –ешение x1 не хуже решени€ x2 по любому из рассматриваемых в задаче критериев

2. –ешение x1 строго лучше решени€ x2 по крайней мере по одному из критериев.

≈сли не существует ни одного решени€, удовлетвор€ющего вышеперечисленным услови€м, то x2 €вл€етс€ недоминируемым или ѕарето-оптимальным решением многокритериальной задачи.

—огласно предложенному в статье подходу, выделение информативных признаков дл€ решени€ задачи распознавани€ подтипов “»ј представл€етс€ как задача многокритериальной оптимизации.

ѕусть – множество различных подмножеств признаков, характеризующих объект данных.  аждое подмножество представл€ет собой некоторую комбинацию входных признаков из максимально возможного количества комбинаций 2n, где n – количество входных признаков. “ребуетс€ выделить подмножество признаков , которое €вл€етс€ решением двухкритериальной задачи оптимизации с двум€ следующими критери€м:

 

max f1(S), min f2(S), (1)

где f1(S) – количество правильно классифицированных объектов с использованием подмножества признаков S, f2(S) – количество элементов подмножества признаков S.

¬ предлагаемом подходе дл€ выделени€ признаков использован генетический алгоритм, который имеет модифицированную схему реализации применительно к задаче многокритериальной оптимизации. —огласно алгоритму не требуетс€ изначальное определение весовых коэффициентов, соответствующих отдельным целевым критери€м [3]. –ешение задачи оптимизации в этом случае можно получить в виде нескольких недоминируемых подмножеств признаков.

ƒл€ расчета точности классификации с использованием подмножества признаков используетс€ алгоритм k-ближайших соседей [4]. —огласно этому алгоритму дл€ каждого объекта определ€етс€ k-ближайших соседей в пространстве признаков. ¬ыбор соседей обычно выполн€етс€ на основании значений евклидовых рассто€ний, хот€ можно использовать другие метрики (например, рассто€ние ћахаланобиса). ¬ качестве класса объекта выбираетс€ класс, к которому относ€тс€ большинство из k-ближайших соседей.

 

2. ќписание эволюционного подхода

—реди различных категорий алгоритмов выделени€ признаков генетические алгоритмы стали примен€тьс€ относительно недавно. √енетические алгоритмы представл€ют собой стохастические методы решени€ оптимизационных задач, в основе которых лежит моделирование процессов биологической эволюции [5]. √енетические алгоритмы можно отнести к наиболее эффективному методу глобального поиска в многомерном пространстве признаков, позвол€ющему получить оптимальное или близкое к нему решение поставленной задачи и учесть возможные взаимозависимости между признаками. ћногие авторы примен€ли генетические алгоритмы дл€ отбора признаков, где в качестве значени€ оценочной или оптимизируемой функции выступала точность классификации с использованием дерева решений и классификаторов, основанных на принципе ближайших соседей [6,7].

¬ работе [6] описан один из первых подходов к использованию генетического алгоритма дл€ отбора признаков. ¬ [6] √ј используетс€ дл€ поиска оптимального бинарного вектора, где каждый бит соответствует отдельному признаку (рис. 1). ≈сли i-ый бит вектора равен единице, то соответствующий ему признак участвует в классификации; если бит равен нулю, тогда соответствующий признак исключаетс€ из дальнейшего анализа.

 

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

 

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

¬ общем случае √ј может осуществл€ть поиск наилучшей диагональной матрицы W или вектора ее диагональных элементов , который представл€ет собой «наилучшее» преобразование исходного признакового пространства с целью максимизации/минимизации оптимизируемого критери€. ƒл€ расчета значени€ оптимизируемого критери€ каждый входной объект данных преобразуетс€ с использованием генетически сгенерированной матрицы W с целью получени€ нового вектора признаков :

,

где ,

 

  1. если , то в качестве элементов вектора используютс€ только бинарные значени€. ¬ этом случае если i-ый компонент вектора равен единице, то i-ый признак сохран€етс€ в отбираемом подмножестве, в противном случае признак исключаетс€ из подмножества. ¬ этом случае осуществл€етс€ отбор признаков и сокращаетс€ размерность исходного признакового пространства;

  2. если например , то осуществл€етс€ выделение признаков, т. е. происходит поиск относительных весов признаков, которые обеспечивают наилучшее значение оптимизируемого критери€. «начени€ весов признаков определ€ют их полезность дл€ решени€ соответствующей оптимизационной задачи. ¬есовые коэффициенты со значени€ми близкими к нулю указывают на низкую информативность признака. ¬ этом случае эти признаки могут быть исключены из рассмотрени€;

  3. если в особи √ј закодировать как вектор с бинарными значени€ми так и вектор весовых коэффициентов, то возможно одновременно решить задачу линейного масштабировани€ (взвешивани€) и отбора признаков, что позвол€ет определить не только состав отобранных информативных признаков, но и степень их информативности дл€ конкретной задачи.

“аким образом, предложенный в насто€щей работе эволюционный подход включает два способа выделени€ информативных признаков:

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

2) взвешивание признаков с одновременным отбором.

ƒл€ каждого из перечисленных способов используетс€ различное кодирование особей генетического алгоритма и соответственно различные операции рекомбинации и мутации.

¬ св€зи с тем, что выделение признаков рассматриваетс€ как задача многокритериальной оптимизации, то приспособленность каждой особи генетического алгоритма определ€етс€ двум€ численными значени€ми: точностью классификации набора данных с использованием алгоритма k-ближайших соседей и количеством выделенных признаков. ќсновные генетические операции используемого √ј описаны в работе [3].

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

 

3. ќписание исследуемого набора данных и результатов вычислений

»сходный исследуемый набор данных состоит из 101 наблюдени€ клинически выверенных случаев пациентов с атеротромботическим этиопатогенезом эпизодов “»ј (—уб“»ј1) – 22 наблюдени€, кардиоэмболическим (—уб“»ј2) – 23 наблюдени€ и гипертензивным (—уб“»ј3) – 22 наблюдени€.  онтрольна€ группа Ќќ–ћј включала 34 наблюдени€.  аждое наблюдение характеризуетс€ измерени€ми по 25 клиническим и персональным признакам.

 

3.1 –езультаты работы √ј в случае отбора признаков

–ассмотрим результаты работы √ј в случае решени€ задачи отбора признаков дл€ распознавани€ подтипов “»ј. »спользуемые в этом случае значени€ параметров √ј приведены в табл. 1.  ажда€ особь √ј представл€ет собой частное решение задачи отбора признаков и состоит из n ген, где n – количество всех рассматриваемых признаков (n=25).  аждый ген может принимать значение 0 или 1, что указывает на исключение/включение соответствующего признака в состав подмножества отбираемых признаков.

“аблица 1 – «начени€ параметров √ј

ѕараметр

«начение

–азмерность попул€ции √ј

200

 оличество генераций

100

¬еро€тность рекомбинации

0.8

¬еро€тность мутации

0.1

Ќа рис. 1 представлены значени€ ошибки классификации, с использованием подмножеств признаков различной размерности, полученных в ходе работы √ј.

–исунок 1 – Ёволюци€ попул€ций √ј в двухмерном пространстве оптимизационных критериев

ѕолученные в процессе работы √ј недоминируемые решени€ – ѕарето-оптимальный фронт - многокритериальной оптимизационной задачи отбора признаков представлены на рис.2.

–исунок 2 – Ќедоминируемые подмножества признаков: горизонтальна€ ось определ€ет количество признаков, вертикальна€ – ошибку классификации (распознавани€) подтипов “»ј

—огласно рис. 2 подмножество признаков, обеспечивающее минимальную ошибку классификации ( 30%) с использованием алгоритма k-ближайших соседей состоит из 8 признаков.

 

3.2 –езультаты работы √ј в случае взвешивани€ признаков с одновременным отбором

–ассмотрим результаты работы √ј в случае решени€ задачи взвешивани€ признаков с одновременным отбором дл€ распознавани€ подтипов “»ј. »спользуемые в этом случае параметры √ј идентичны приведенным в таблице 1.  ажда€ особь √ј представл€ет собой частное решение задачи взвешивани€ и отбора признаков и состоит из 2*n ген, где n – количество всех рассматриваемых признаков (n=25). ѕервые n ген могут принимать действительное значение в интервале [0,10], обеспечивающее независимое линейное масштабирование отдельных признаков, последующие n ген могут принимать бинарные значени€ и предназначены дл€ отбора признаков. “аким образом, результатом работы √ј €вл€ютс€ недоминируемые подмножества признаков с весовыми коэффициентами (рис. 3).

–исунок 3 – Ёволюци€ попул€ций √ј в двухмерном пространстве оптимизационных критериев

ѕолученные в процессе работы √ј недоминируемые решени€ – ѕарето-оптимальный фронт - многокритериальной оптимизационной задачи взвешивани€ и отбора признаков представлены на рис.4.

–исунок 4 – Ќедоминируемые подмножества признаков: горизонтальна€ ось определ€ет количество признаков, вертикальна€ – ошибку классификации (распознавани€) подтипов “»ј

 

¬есовые коэффициенты недоминируемого подмножества, обеспечивающего минимальную ошибку классификации 25,7 %, представлены в табл. 2.

 

“аблица 2 – ¬есовые коэффициенты отобранных признаков*

ѕризнак

PROFESSN

HERED_CV

HYPERTEN

CORCARSC

¬ес

3.7

3.3

5.4

6.5

ѕризнак

BRONCHRO

HEADACHE

VERTIGO

 

¬ес

9.6

4.2

9.4

 

*ѕредставлены коды признаков: професси€ (PROFESSN), наследственность по ÷¬« (HERED_CV), артериальна€ гипертензи€ (HYPERTEN), коронарокардиосклероз (CORCARSC), хронический бронхит (BRONCHRO), головные боли (HEADACH), головокружение (VERTIGO).

«аключение

¬ насто€щей работе описаны два способа выделени€ признаков, которые позвол€ют сократить сложность и повысить точность классификации путем получени€ недоминируемых подмножеств признаков с использованием генетического алгоритма, предназначенного дл€ решени€ многокритериальных задач. ѕреимуществом использовани€ √ј в этом случае €вл€етс€ получение нескольких решений с последующей возможностью привлечени€ знаний и опыта экспертов с целью выбора окончательного подмножества предсказывающих признаков. ѕрименение предложенного эволюционного подхода к дифференциальной диагностике подтипов транзиторных ишемических атак позвол€ет сконцентрировать внимание на небольшом количестве признаков, €вл€ющихс€ в этом случае наиболее информативными и получить классификационное решение, которое не уступает по точности классификации с решением, полученным с учетом 25 исходных признаков.

ƒальнейшим направлением исследований €вл€етс€ использованием √ј дл€ параллельного отбора признаков и наблюдений из набора данных, что позволит сократить количество прототипов, используемых при проведении классификации методом k-ближайших соседей. ƒл€ больших наборов данных такой отбор позволит уменьшить временные и вычислительные затраты на осуществление классификации объектов данных. »нтерес представл€ет также использование результатов применени€ эволюционного подхода к отбору признаков дл€ построени€ ансамблей классификаторов и применение различных комбинационных методов дл€ получени€ более высокой точности классификации [8].

 

Ћитература

  1. Dash, M. Feature selection for classification / M. Dash, H. Liu // Intelligent Data Analysis. – 1997. – Vol. 1, є 3. – P. 131–156.

  2. ƒривотинов, Ѕ.¬. јдаптивна€ нейро-нечетка€ модель дл€ дифференциальной диагностики подтипов транзиторных ишемических атак Ѕ.¬. ƒривотинов, ≈.Ќ. јпанель, Ќ.ј. Ќовоселова, ј.—. ћастыкин, ј.—. ‘едулов // ¬оенна€ медицина. – є 4. – 2007. – —. 101–106.

  3. Deb, K. Multi-Objective Optimization using Evolutionary Algorithms / K. Deb // John Wiley & Sons, England. – 2001.

  4. Cover, T.M. Nearest neighbor pattern classification / T.M. Cover, P.E. Hart // IEEE Transactions on Information Theory. – 1967. – Vol. 13, є 1. – P.21–27.

  5. Goldberg, D. Genetic algorithms in search, optimization and machine learning / D. Goldberg. – Reading (MA): Addison-Wesley, 1989. – 432 p

  6. Siedlecki, W. A note on genetic algorithms for large scale feature selection / W. Siedlecki, J. Sklansky // Pattern Recognition Letters. – 1989. – Vol. 10, є 5. – P. 335–347.

  7. Dimensionality reduction using genetic algorithms / Raymer M.L. [et al.] // IEEE Transactions on Evolutionary Computation. – 2000. – Vol. 4, є 2. – P. 164–171.

  8. Multiple Classifier Systems (Kittler J & Roli F (editors)) // Proc. of 2nd International Workshop, MCS2001, Cambridge, UK, 2-4 July 2001, Lecture Notes in Computer Science, vol. 2096, Springer-Verlag, Berlin.

 

¬резка1



03.12.2022

Ќавигаци€

Ќовости

01.05.2016

„итать далее...

29.01.2016

„итать далее...

  • ¬се новости (20)
  • –еклама

    —четчики


    яндекс.ћетрика
    яндекс цитировани€
    дл€ спамеров
    –Ш–≥—А–∞—В—М –≤ —Б–∞–Љ—Л–µ –њ–Њ–њ—Г–ї—П—А–љ—Л–µ –Њ–љ–ї–∞–є–љ –Є–≥—А—Л–Ъ—Г–њ–Є—В—М —Б—Г–њ–µ—А —Б–Є–∞–ї–Є—Б –≤ –њ–µ—А–Љ–Є Vin –Ї–Њ–і –µ–≤—А–Њ–њ–∞–Ъ—А–Є–Ј–Є—Б —З–∞—Б—В—М 3 –Є–≥—А–∞—Б—В—Г–і–Є—П Diamond –§–µ–і–µ—А–∞—Ж–Є—П Pole Dance–Ю–Љ—Б–Ї —А–µ–Љ–Њ–љ—В —В—А—Г–±–Ю–љ–ї–∞–є–љ –Є–≥—А–∞ Diablo 4–Ц–µ–љ—Б–Ї–∞—П –≤–Є–∞–≥—А–∞ –Ї—Г–њ–Є—В—М –≤ –Ь—Л—В–Є—Й–∞—Е—Б—В–Њ–ї –љ–∞ –Ј–∞–Ї–∞–Ј –Њ–Љ—Б–Ї–і–ґ–µ–љ–µ—А–Є–Ї –≤–Є–∞–≥—А–∞ —Б–Њ—Д—В –Ї—Г–њ–Є—В—М–Є–≥—А–∞–µ–Љ —В—Г—В–≥–∞–і–∞–љ–Є–µ —В–∞—А–Њ –Њ–љ–ї–∞–є–љ–°–Є–Љ—Б 4 –Є–≥—А–∞—В—М –Њ–љ–ї–∞–є–љdocument.write('');