2.3 Выделение однородных типологических групп объектов
Одной из важной задачей при донозологической оценки функционального состояния человека является выделение и в последующем различения однородных типологических состояний организма, формирующихся под воздействием факторов жизнедеятельности, которые являются отражением свойств неоднородности медико-биологической информации.
В математической формулировки выделение классов однородных типологических состояний является задачей кластеризации(обучение без учителя), целью которой является получение в пространстве интегральных показателей непересекающихся или слабо пересекающихся групп(кластеров), характеристики которых отражают типичные состояния функциональных систем организма.
В общей (нестрогой) постановке проблемы кластеризации объектов заключается в том, чтобы всю анализируемую совокупность объектов, представленную в виде матрицы объектов-признаков, разбить на сравнительно небольшое число однородных, в определенном смысле, групп или классов.
Для формализации этой проблемы удобно интерпретировать анализируемые объекты в качестве точек в соответствующем признаковом пространстве. Если исходные данные представлены в форме матрицы объекты-признаки (), то эти точки являются непосредственным геометрическим изображением многомерных наблюдений, в -мерном пространстве с координатными осями. Естественно предположить, что геометрическая близость двух или нескольких точек в этом пространстве означает близость «физических» состояний соответствующих объектов, их однородность. Тогда проблема кластеризации состоит в разбиении анализируемой совокупности точек — наблюдений на сравнительно небольшое число (заранее известное или нет) классов таким образом, чтобы объекты, принадлежащие одному классу, находились бы на сравнительно небольших расстояниях друг от друга.
В зависимости от объема совокупности наблюдений задача кластеризации подразделяется на два основных типа:
- к первому типу относятся задачи кластеризации сравнительно небольших по объему совокупностей наблюдений, состоящих, как правило, не более чем из нескольких десятков наблюдений.
- к второму типу относятся задачи кластеризации достаточно больших массивов многомерных наблюдений ( - порядка нескольких сотен и тысяч;). Подобное разделение задач кластеризации на два типа хотя и условно но весьма необходимо, и в первую очередь с точки зрения принципиального различия идей и методов, на основании которых конструируются методы кластеризации в том и в другом случае.
С точки зрения априорной информации об окончательном числе классов, на которое требуется разбить исследуемую совокупность объектов, задачу кластеризации можно подразделить на три основных типа:
1) число классов априори задано;
2) число классов неизвестно и подлежит определению (оценке);
3) число классов неизвестно, но его определение и не входит в условие задачи; требуется построить так называемое иерархическое дерево исследуемой совокупности, или дендрограмму.
В соответствии с подразделением задачи кластеризации на типы можно выделить следующие три основных типа методов кластеризации:
- иерархические (агломеративные и дивизимные). Предназначены в основном для решения задач типа для которых неизвестно количество классов. Что касается объема классифицируемой совокупности, то формально иерархические процедуры применимы и для задач небольших по объему совокупностей наблюдений так и для задач больших массивов многомерных наблюдений.
- параллельные. Предназначены для решения задач, для которых известно количество классов. Они реализуются с помощью итерационных алгоритмов, на каждом шаге которых одновременно (параллельно) используются все имеющиеся наблюдений;
- последовательные. Предназначены в основном для решения задач первого и второго типа. Они реализуются с помощью итерационных алгоритмов, на каждом шаге которых используется лишь небольшая часть, например одно из исходных наблюдений, а так же результат разбиения на предыдущем шаге.
Поскольку априорно указать число кластеров не представляется возможным, для поставленной задачи выделения однородных типологических состояний организма наиболее целесообразным является использование иерархической агломеративной кластеризации, позволяющей выявлять естественное расслоение исходных наблюдений на четко выраженные кластеры, сгустки, лежащие друг от друга на некотором расстоянии, но не разбивающиеся на столь же удаленные части. Привлекательной стороной подобных методов является и возможность наглядной интерпретации проведенного анализа.
На первом шаге алгоритма каждое наблюдение рассматривается как отдельный кластер. Далее на каждом шаге работы алгоритма происходит объединение двух самых близких кластеров и соответственно пересчитывается матрица расстояний, размерность которой, естественно, снижается на единицу. Работа алгоритма заканчивается, когда все исходные наблюдения сгруппированы в один кластер, используя некоторую меру сходства или расстояние между объектами. Существует много различных способов вычисления расстояния между целыми группами объектов, каждое из которых порождает специфический иерархический алгоритм кластеризации. Пусть - i-я группа(класс, кластер) объектов, - число объектов, образующих группу, вектор - среднее арифметическое векторных наблюдений, входящих в (другими словами, - «центр тяжести» i-й группы), - мера близости, а - расстояние между группами и На практике используются следующие способы вычисления расстояний между кластерами:
- расстояние, измеряемое по принципу «ближайшего соседа»(рисунок 7) когда расстоянием между кластерами считается минимальное из расстояний между парами объектов, один из которых входит в первый кластер, а другой — во второй;
Рисунок 7 - Метод ближайшего соседа
- расстояние, измеряемое по принципу «дальнего соседа» (рисунок 8) когда расстоянием между кластерами считается максимальное из расстояний между парами объектов, один из которых входит в первый кластер, а другой — во второй;
Рисунок 8 - Метод дальнего соседа
- расстояние, измеряемое по принципу «средней связи»(рисунок 9) расстояние между кластерами рассчитывается как средняя связь, т.е. как среднее арифметическое расстояний между парами объектов, один из которых входит в первый кластер, а другой — во второй;
Рисунок 9 - Метод средней связи
- расстояние, измеряемое по «центрам тяжести» групп(рисунок 10) расстояние между двумя кластерами определяется как расстояние между их центрами тяжести;
Рисунок 10 - Центроидный метод
- расстояние, измеряемое методом Уорда. Этот метод отличается от всех других методов, поскольку он использует методы дисперсионного анализа для оценки расстояний между кластерами. Метод минимизирует сумму квадратов (SS) для любых двух (гипотетических) кластеров, которые могут быть сформированы на каждом шаге.
Для анализа медико-биологическая данных наиболее адекватным является метод Уорда, имеющий тенденцию к нахождению (созданию) кластеров приблизительно равных размеров и имеющих гиперсферическую форму, что дает, как правило, наилучшие результаты.
В качестве меры близости между объектами используется самые различные метрики, которые можно объединить в три большие группы в зависимости от шкалы измерения обрабатываемых переменных:
- меры расстояния для количественных шкал(линейное расстояние, Евклидово, Манхеттенское, Махаланобиса, обобщенное степенное расстояние Минковского и др. );
- меры сходства для номинальных шкал (коэффициенты Рао, Хемминга, Жаккара и др.);
- меры расстояния для произвольных шкал(меры близости Журавлева, Воронина, Миркина и др.).
Для количественных данных Евклидово расстояние является самой популярной метрикой в кластерном анализе: оно отвечает интуитивным представлениям о близости и, кроме того, геометрически лучше всего объединяет объекты в шарообразных скоплениях, которые весьма типичны для данных медико-биологического профиля.
Евклидово расстояние задается формулой
где - значение -го признака у -го объекта.
Это обычный способ его вычисления, который имеет определенные преимущества (например, расстояние между двумя объектами не изменяется при введении в анализ нового объекта, который может оказаться выбросом).
В результате кластеризации формируется классов типологических состояний, каждое из которых характеризуется определенным соотношением интегральных показателей оценки функционального состояния таких, что пересечение между указанными классами является минимальным.
2.4 Построение композиции алгоритмов на основе деревьев решений
Наиболее существенным для поставленных задач является идентификации соответствия оцениваемого состояния к одному из типологических классов(состояний). С математической позиции решение данной задачи состоит в построение решающих правил, позволяющих по величине критерия нормирования оценить принадлежность текущего состояния объекта к одному из классов типологических состояний.
Для решение данной задачи используются алгоритмы классификации интеллектуального анализа данных, позволяющего на основе интегральных показателей оценки функциональных состояний построить решающие правила, наилучшим образом разделяющие все выделенные типологические состояния.
К настоящему времени разработано несколько основных направлений, объединяющих сотни конкретных алгоритмов и методов. В качестве таковых следует отметить перцептронные модели, метод потенциальных функций, статистические модели распознавания, ансамблевые модели(композиция алгоритмов), модели распознавания, основанные на построении кусочно-линейных (или более сложных) разделяющих поверхностей в признаковом пространстве, алгоритмы, основанные на построении решающих деревьев, структурные (лингвистические) методы, модели частичной прецедентности, алгебраический подход Ю.И.Журавлева, нейросетевые алгоритмы, методы, основанные на теории нечетких множеств и др. Основанные на различных идеях, гипотезах и принципах, а также их сочетаниях, эти подходы имеют свои достоинства и недостатки, различные требования к исходным данным, ограничения на области применения. Однако все они сводятся к поиску полезной информации в пространстве возможных объектов и ее корректному обобщению.
Для решение задачи оценки функционального состояния целесообразно использовать композицию алгоритмов классификации, относящиеся к методам классификации с «учителем». Применение композиции алгоритмов классификации требует априорных знаний, к какому из классов относится каждый объект наблюдения, что достигается на предыдущем этапе выделение типологических состояний методом иерархической агломеративной кластеризации.
Необходимость использования композиции классификаторов с последующим объединением их решений для донозологической оценки функционального состояния обусловлено тем, что:
- использование композиции классификаторов приводит к более высокой точности распознавания и лучшим показателям вычислительной эффективности;
- пространство признаков содержит весьма разнообразные типы признаков (булевы, целочисленные, непрерывные и т.п.);
- задача обладает большой размерностью пространства признаков и необходимо бороться с вычислительной сложностью.
Композиция в целом может рассматриваться как сложная, составная модель (multiple model), состоящая из отдельных (базовых) моделей. Здесь возможны два случая:
- композиция состоит из базовых моделей одного типа, например только из деревьев решений, только из нейронных сетей и т. д. (рисунок 11).
- композиция состоит из моделей различного типа — нейронных сетей, деревьев решений, регрессионных моделей и т. д. (рисунок 12).
Рисунок 11 - Однородная композиция
Рисунок 12 - Композиция, состоящая из моделей различного типа
При построении композиции существуют два подхода использования обучающего множества:
- перевыборка (resampling), из исходного обучающего множества извлекается несколько подвыборок, каждая из которых используется для обучения одной из моделей композиции. Данный подход представлен на рисунке 13;
Рисунок 13 - Перевыборка
- использование одного обучающего множества для обучения всех моделей композиции. Данный подход представлен на рисунке 14;
Рисунок 14 - Использование одной обучающей выборки для всех моделей композиции
Для комбинирования результатов, выделенных отдельными моделями обычно используют следующие способы:
- простое голосование (simple voting);
- взвешенное голосование(weighted voting).
Обобщенная схема композиции моделей представлена на рисунке 15
Рисунок 15 - Схема композиции на основе деревьев решений
Таким образом, построение композиции включает следующие шаги:
1) Из обучающего множества длины извлекается заданное количество выборок одинакового размера с помощью процедуры бутстреппинга (bootstrapping) - случайного отбора с возвращениями. Поскольку отбор производится случайно, набор примеров в этих выборках будет различным: одни объекты могут быть отобраны по нескольку раз, а другие - ни разу.
2) На основе каждой выборки строится отдельная (базовая) модель. В качестве базовой модели используется алгоритм дерева решений С4.5.
В основе работы дерева решений лежит процесс рекурсивного разбиения исходного множества наблюдений или объектов на подмножества, ассоциированные с классами. Разбиение производится с помощью решающих правил, в которых осуществляется проверка значений атрибутов по заданному условию. Процесс рекурсивного разбиения подмножеств в узлах дерева решений получил название «разделяй и властвуй» (divide and conquer). В его основе лежит следующий принцип.
Множество содержит примеры, относящиеся к различным классам. Задача заключается в разделении на подмножества, ассоциированные с классами. Выбирается один из входных атрибутов, принимающий два отличных друг от друга значения или более, после чего разбивается на подмножества, где каждое подмножество, содержит все примеры из исходного множества, в которых выбранный атрибут принимает значение (рисунок 15). Данная процедура будет рекурсивно повторяться до тех пор, пока подмножества не будут содержать примеры только одного класса.
Рисунок 16 - Разбиение по атрибуту
Наиболее проблемным этапом алгоритма является выбор атрибута, по которому будет производиться разбиение в каждом узле. Для выбора атрибута разбиения C4.5 использует модифицированный критерий прироста информации
Данная мера представляет собой прирост количества информации, полученный в результате разделения множества на подмножества с помощью разбиения. В качестве наилучшего атрибута для использования в разбиении выбирается тот атрибут, который обеспечивает наибольший прирост информации. Этот атрибут будет являться проверкой в текущем узле дерева, а затем по этому атрибуту производится дальнейшее построение дерева, то есть в узле будет проверяться значение по этому атрибуту и дальнейшее движение по дереву будет производиться в зависимости от полученного ответа. Такие же рассуждения можно применить к полученным подмножествам и продолжить рекурсивно процесс построения дерева, до тех пор, пока в узле не окажутся примеры из одного класса.
Так как деревья решений относят к моделям, которые в процессе обучения адаптируют свое состояние в соответствии с обучающим множеством: даже небольшие изменения в обучающем множестве (замена или удаление одного объекта) могут привести к существенным изменениям в состоянии модели (структуре дерева решений). Иными словами, внося даже незначительные изменения в обучающие данные, всегда будем получать другую модель. Но исходная и измененная модели будут функционировать примерно одинаково и со сравнимой точностью: незначительные изменения в обучающих данных не приведут к изменению основных закономерностей, которые должны быть обнаружены моделью.
3) Определяется общий результат путем взвешенного голосования.
Для получения оптимальной однородной композиции использовалось несколько принципиально разных внешних критериев:
1) критерий среднеквадратичной ошибки;
2) критерий скользящего контроля.
Критерий скользящего контроля - процедура заключающаяся в разбиений исходной выборки на две подвыборки: обучающую и контрольную. Для каждого разбиения выполняется настройка алгоритма по обучающей подвыборке, затем оценивается его средняя ошибка на объектах контрольной подвыборки.
Процедура скользящего контроля заключается в том что выборка разбивается различными способами на две непересекающиеся подвыборки, где - обучающая подвыборка длины, контрольная подвыборка длины, — номер разбиения.
Для каждого разбиения строится дерево решений и вычисляется значение функционала качества .Среднее арифметическое значений по всем разбиениям называется оценкой скользящего контроля:
Критерий скользящего контроля отбирает несколько лучших деревьев решений, качество которых не отличается в пределах дисперсии критерия.
Критерий среднеквадратичной ошибки определяется как среднеквадратическая разность ответов двух алгоритмов, построенных по двум случайным непересекающимся подвыборкам одинаковой или практически одинаковой длины, .
где - модель на обучающей выборки, - модель на контрольной выборки. Чем меньше нормализованное значение критерия среднеквадратичной ошибки, тем больше вес дерева решений .
Таким образом, анализ основных особенностей медико-биологической информации позволил предложить общий методологический подход идентификации функциональных состояний человека. Он включает три этапа.
1) Формирование показателей оценки изучаемых функций организма, имеющих характер функциональных шкал. Он позволят проводить оценку функциональных состояний человека не по всем признакам, а по информативным, адекватно характеризующих функциональное состояние человека, что повышает устойчивость и надежность оценки. Реализация данного этапа осуществляется методом направленного отбора.
2) Формирование пространства альтернатив выбора. Осуществляется в пространстве интегральных показателей с использованием кластерного анализа и состоит в выделении типологических состояний человека.
3) Построение алгоритма принятия решений с учетом «размытости» границ между альтернативными состояниями по показателям характеризующим функциональное состояние человека. Данный этап реализуется с использование однородной композиции моделей(алгоритмов).