УДК 51.76, 57.087

Линейный дискриминантный анализ Фишера в задачах классификации многомерных биомедицинских данных

А.П. Немирко
apn-bs@yandex.ru
Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»

Исследовано линейное преобразование пространства на основе критерия Фишера для задач классификации многомерных биомедицинских данных. Приведены выражения для рекуррентного вычисления весовых векторов, которые образуют новые признаки. Показано, что за счет более точного представления данных с помощью найденных признаков они позволяют более эффективно реализовать процедуры классификации.
Ключевые слова: анализ биомедицинских данных, линейный дискриминант Фишера, близость классов.
Linear transformation of space on the basis of Fischer's criterion for problems of multidimensional biomedical data classification is investigated. Expressions for recurrent calculation of weight vectors which form new features are given. It is shown that due to more exact data presentation by means of the found features they allow to realize classification procedures more effectively.
Keywords: biomedical data analysis, liner Fisher’s discriminant, classes proximity.

Классификация многомерных данных широко применяется в биологических и медицинских исследованиях [1, 2]. Для сокращения размерности признакового пространства часто применяется метод главных компонент [3]. Для классификации используется также линейный дискриминант Фишера (ЛДФ) [4], который уменьшает размерность признакового пространства с исходного до одного путем проектирования многомерных данных на прямую. Экспериментальные исследования показывают, что критерий Фишера далеко не всегда оптимален для решения задачи распознавания объектов. Введение дополнительного весового вектора [5−7] может уменьшить пересекаемость классов и привести к более эффективным процедурам линейной классификации на плоскости. Такой подход требует введения других, отличных от критерия Фишера, способов измерения близости классов в многомерном пространстве.
В данной работе предложено несколько способов оценки близости классов и степени их пересекаемости. Все эти способы применены к описанию классов в пространстве двух весовых векторов, найденных по критерию Фишера. Необходимо отметить, что во всех случаях критерий Фишера остается универсальным.
Цель работы – исследование применимости дискриминантного анализа с дополнительными весовыми векторами для повышения качества распознавания многомерных биомедицинских данных.

Трансформация признакового пространства на основе критерия Фишера
Линейный дискриминант Фишера определяется как вектор W, для которого линейный функционал максимален.

критерий Фишера ЛЭТИ CardioQVARK(1)

В этой формуле m1 и m2 − средние значения классов, спроектированных на W; s12 и s22 − выборочные внутриклассовые рассеяния для этих проекций. Для W при условии, что J(W) = max, расстояние между проекциями классов на W максимально.
Приведенный выше функциональный критерий (1) можно переписать в виде

критерий Фишера ЛЭТИ CardioQVARK(2)
где SB = (M1 – M2)(M1 – M2)T − матрица межклассового рассеяния; M1 и M2 − векторы сред-них значений классов; SW = S1 + S2 − матрица внутриклассового рассеяния; S1, S2 − матрицы внутриклассового рассеяния 1- и 2-го классов:

критерий Фишера ЛЭТИ CardioQVARK
Xi(j) i-й входной вектор j-го класса; n1 и n2 число членов каждого класса.
Анализ формулы (2) показывает [4], что максимум J(W) достигается при

критерий Фишера ЛЭТИ CadioQVARK(3)
Для исходного n-мерного признакового пространства выражение (3) можно переписать в виде

критерий Фишера ЛЭТИ CardioQVARK(4)
В работе [5] выведена формула для рекуррентного вычисления других дополнительных ортогональных весовых векторов. Второй дополнительный весовой вектор W2 определяется выражением 

критерий Фишера ЛЭТИ CardioQVARK  (5)

Эксперименты с линейно разделимыми классами
Для экспериментальных исследований выбраны два линейно разделимых многомерных множеств f1 и f2 [5]. Результат вычисления по ним первых двух главных компонент показан на рис. 1. Из него видно, что метод главных компонент не обеспечивает линейную разделимость классов.
Реализация метода ЛДФ с одним добавочным признаком на данных множествах показана на рис. 2.
Из рис. 2 видно, что использование только одного весового вектора W1, найденного по критерию Фишера, линейной разделимости достичь не удается. Добавочный же признак (весовой вектор W2) обеспечивает полную линейную разделимость классов f1 и f2.

анализ множеств по методу главных компонент ЛЭТИ CardioQVARK
Рис. 1. Анализ множеств f1 и f2 по методу главных компонент

анализ множеств методом ЛДФ ЛЭТИ CardioQVARK
Рис. 2. Анализ множеств f1 и f2 методом ЛДФ с одним добавочным признаком. Ось абсцисс – вектор W1 , ось ординат – вектор W2

На рис. 3 изображена область пересечений двух классов ирисов Фишера: виргинского и разноцветного справа. [9] в сокращенном и пространстве, образованном двумя весовыми векторами W1 и W2.
Из рис. 3 видно, что только в двумерном пространстве можно достичь нулевой ошибки классификации виргинских ирисов при малых ошибках классификации разноцветных ирисов. В случае сложных конфигураций распределений классов выигрыш от введения дополнительного весового вектора может оказаться существенным. На рис.4 показаны два класса линейно непересекающихся объектов, представленных в двумерном пространстве признаков x1 и x2. Для данных распределений этих классов использование критерия Фишера дает решающий вектор W1, показанный на рисунке, общей ошибкой 33%. На плоскости же легко найти решающий вектор F который разделяет эти классы безошибочно.

анализ ирисов Фишера ЛЭТИ CardioQVARK
Рис. 3. Анализ ирисов Фишера: виргинского (слева) и разноцветного (справа) в редуцированном пространстве методом ЛДФ с одним добавочным признаком

классификация распределений ЛЭТИ CardioQVARK
Рис. 4. Классификация при сложной конфигурации распрeделений: W1 – оптимальный решающий вектор, найденный по критерию Фишера; F – решающий вектор для безошибочной классификации на 2 класса

Оценка близости классов в многомерном пространстве
Экспериментальные исследования показывают, что критерий Фишера далеко не всегда оптимален для решения задачи распознавания объектов. Для улучшения классификации нужны новые критерии близости классов. Эти критерии не всегда легко применить в исходном пространстве. Однако можно сначала снизить размерность признакового пространства с помощью ЛДФ с добавочными признаками, а затем искать оптимальный весовой вектор уже в сокращенном пространстве, например, в двумерном. Этот подход требует введения других, отличных от критерия Фишера, способов измерения близости классов в двумерном пространстве.
Можно предложить несколько способов оценки близости классов и степени их пересекаемости. Необходимо отметить, что во всех случаях критерий Фишера остается универсальным.
1. Первый способ оценки пересекаемости классов для 2-классовой задачи заключается в измерении размера области пересечения, которую можно получить построив выпуклые оболочки обоих классов и найдя область их пересечения. Степень близости классов (при пересечении степень пересекаемости) может быть оценена как минимальное расстояние между этими выпуклыми оболочками. Существует несколько алгоритмов измерения такого минимального расстояния (например, алгоритм Гилберта − Джонсона − Кёрти [8]). Мы применяем способ, который заключается в передвижении одной из оболочек в направлении вектора, соединяющего центры классов до момента, когда все элементы будут удалены из области пересечения (или до момента, когда 1-й элемент окажется в области пересечений для непересекающихся классов). Расстояние полученного сдвига и будет искомым расстоянием. Алгоритм реализуется в системе MATLAB с применением функций convhull, convhulln.
2. Второй способ оценки пересекаемости классов заключается в подсчете доли элементов каждого класса, попавших в область пересечения, и вычислении среднего по двум классам. Этот параметр меняется от 0 до 1. Конечно, для задачи классификации важно, сколько представителей каждого класса попало в область пересечений. Это влияет на ошибки классификации.
3. С точки зрения классификации наиболее адекватным следует считать третий способ, который измеряет площадь под кривой зависимости доли правильно обнаруженных эле-ментов одного класса от доли ошибочного обнаружения второго класса – аналог кривой рабочей характеристики (ROC-кривой). Методы преобразования пространства признаков можно сравнивать по этому критерию. Чем площадь больше – тем метод лучше.
• Для классификации многомерных биомедицинских данных используется линейный дискриминант Фишера. Экспериментальные исследования показали, что критерий Фишера не всегда оптимален для решения задачи распознавания объектов. Введение дополнительных весовых векторов уменьшает пересекаемость классов и приводит к более эффективным процедурам линейной классификации.

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

Исследование выполнено при поддержке РФФИ в рамках научных проектов №№ 15-07-01790, 16-01-00159 и медицинского проекта CardioQVARK − кардиограмма с помощью телефона www.cardioqvark.ru.

Литература
1. Немирко А.П., Манило Л.А., Калиниченко А.Н. Матема-тические методы анализа биомедицинских данных. СПб: Изд-во СПбГЭТУ «ЛЭТИ». 2013. 175 с.
2. Рангайян Р.М. Анализ биомедицинских сигналов. Практический подход / Пер. с англ. А.Н. Калиниченко / Под ред. А.П. Немирко. М.: Физматлит. 2007. 440 с.
3. Айвазян С.А., Бежаева З.И., Староверов О.В. Класси-фикация многомерных наблюдений. М.: Статистика. 1974. 240 с.
4. Дуда Р., Харт П. Распознавание образов и анализ сцен / Пер. с англ. М.: Мир. 1976. 511 с.
5. Nemirko A.P. Transformation of feature space based on Fisher’s linear discriminant. // Pattern Recognition and Image Analysis. Advances in Mathematical Theory and Applications. 2016. V. 26. № 2. Р. 257−261.
6. Манило Л.А. Упорядочение спектральных признаков по эмпирическим оценкам межгруппового расстояния в задачах классификации биосигналов // Известия вузов России. Радиоэлектроника. 2006. Вып. 3. С. 20-29.
7. Манило Л.А. Линейный дискриминант Фишера в зада-чах распознавания биосигналов по частотным свой-ствам // Сб. докл. 12-й Всерос. конф. «Математические методы распознавания образов» (Москва, 2005). М.: МАКС Пресс. 2005. С. 371–374.
8. Gilbert E.G., Johnson D.W., Keerthi S.S. A fast procedure for computing the distance between complex objects in three-dimensional space // IEEE Journal of Robotics and Automation. April 1988. V. 4. Р. 193–203.
9. Iris Data Set. UCI Machine Learning Repository. https://archive.ics.uci.edu/ml/datasets/Iris, 2016.


Fischer’s linear discriminant analysis in problems of multidimensional biomedical data classification

A.P. Nemirko Dr.Sc. (Eng.),
Professor, Department of Biotechnical Systems, Saint Petersburg Electrotechnical University «LETI»
E-mail: apn-bs@yandex.ru

For reduction of feature space dimension at biomedical data classification the Fischer’s linear discriminant is used. It reduces space dimension from initial to one by projecting the multidimensional data into a straight line. Pilot studies show that Fischer's criterion is not always optimum for the solution of an object recognition problem. Introduction of an additional weight vector can reduce an intersection between classes and lead to more effective procedures of linear classification on the plane. Recurrent expression for consecutive calculation of additional features is derived. When only one additional weight vector is used, procedure of classification is realized on the plane. Such approach demands introduction of other ways of class proximity measurements different from Fischer's criterion. In this work some ways of an assessment of class adjacency and degree of their intersection are offered. All these ways are applied to classification in space of two weight vectors found by Fischer's criterion.

REFERENCES
1. Nemirko A.P., Manilo L.A., Kalinichenko A.N. Matematicheskie metody analiza biomedicinskih dannyh. SPb: Izd-vo SPbGJeTU «LJeTI». 2013. 175 s.
2. Rangajjan R.M. Analiz biomedicinskih signalov. Prakticheskij podhod / Per. s angl. A.N. Kalinichenko / Pod red. A.P. Nemirko. M.: Fizmatlit. 2007. 440 s.
3. Ajvazjan S.A., Bezhaeva Z.I., Staroverov O.V. Klassifikacija mnogomernyh nabljudenij. M.: Statistika. 1974. 240 s.
4. Duda R., Hart P. Raspoznavanie obrazov i analiz scen / Per. s angl. M.: Mir. 1976. 511 s.
5. Nemirko A.P. Transformation of feature space based on Fisher’s linear discriminant. // Pattern Recognition and Image Analysis. Advances in Mathematical Theory and Applications. 2016. V. 26. № 2. Р. 257−261.
6. Manilo L.A. Uporjadochenie spektral'nyh priznakov po jempiricheskim ocenkam mezhgruppovogo rasstojanija v zadachah klassifikacii biosignalov // Izvestija vuzov Rossii. Radiojelektronika. 2006. Vyp. 3. S. 2029.
7. Manilo L.A. Linejnyj diskriminant Fishera v zadachah raspoznavanija biosignalov po chastotnym svojstvam // Sb. dokl. 12-j Vseros. konf. «Matematicheskie metody raspoznavanija obrazov» (Moskva, 2005). M.: MAKS Press. 2005. S. 371–374.
8. Gilbert E.G., Johnson D.W., Keerthi S.S. A fast procedure for computing the distance between complex objects in three-dimensional space // IEEE Journal of Robotics and Automation. April 1988. V. 4. Р. 193–203.
9. https://archive.ics.uci.edu/ml/datasets/Iris, 2016.Iris Data Set. UCI Machine Learning Repository.