Содержание к диссертации
Введение
ГЛАВА 1. Обзор существующих методов классификации многомерных данных и постановка задачи 12
1.1. Статистический метод классификации многомерных данных 13
1.2. Возможность использования нечеткой логики для классификации многомерных данных 17
1.3. Метод классификации многомерных данных, основанный на нейронных технологиях 21
1.3.1.Искусственный нейрон 21
1.3.2.Многослойный персептрон 22
1.3.3.Нейронная сеть Ворда 24
1.3.4.Нейронная сеть Кохонена 24
1.4. Робастный метод классификации многомерных данных 27
1.4.1.Робастная регрессия 28
1.4.2.Знаковая регрессия 29
1.5 Необходимость разработки моделей и алгоритмов классификации состояний биоценозов на примере микробиоценоза желудочно-кишечного тракта человека 30
1.5.1.Дисбиоз желудочно-кишечного тракта 30
1.5.2.Характеристика микрофлоры кишечника людей различного возраста 31
1.5.3.Выбор параметров оценки состояния биоценоза желудочно кишечного тракта человека 33
1.6 Выводы и постановка задачи 39
ГЛАВА 2. Модели представления многомерных данных 41
2.1. Структурно-статистическая модель представления многомерных
данных 41
Метод проекций 43
2.2. Нечеткая модель представления многомерных данных 48
2.2.1.Функции принадлежности 49
2.2.2.Метод вычисления функции принадлежности применительно к задаче классификации многомерных данных 54
2.3. Знаковая модель представления многомерных данных 58
2.4. Выводы 60
ГЛАВА 3. Разработка алгоритмов классификации состояний биоценозов 61
3.1. Алгоритм классификации, основанный на структурно-статистической модели представления многомерных данных 62
3.2. Алгоритм классификации, основанный на нечеткой модели представления многомерных данных 66
3.2.1.«Классический» алгоритм классификации состояний биоценозов 66
3.2.2.Нечеткий алгоритм классификации состояний биоценозов 68
3.3. Алгоритм классификации, основанный на знаковой модели представления многомерных данных 71
3.4. Выводы 74
ГЛАВА 4. Практическая реализация разработанных алгоритмов классификации 75
4.1. Экспериментальное исследование алгоритма классификации, основанного на структурно-статистической модели 75
4.2. Экспериментальное исследование алгоритма классификации, основанного на нечеткой модели 77
4.3. Экспериментальное исследование алгоритма классификации, основанного на знаковой модели 81
4.4. Классификация состояний микробиоценозов желудочно-кишечного тракта человека с использованием нейросетевых технологий 84
4.5. Сравнительный анализ алгоритмов классификации 88
4.6. Описание программной реализации 90
4.7. Выводы 92
Заключение 93
Библиографический список
- Метод классификации многомерных данных, основанный на нейронных технологиях
- Нечеткая модель представления многомерных данных
- Алгоритм классификации, основанный на нечеткой модели представления многомерных данных
- Экспериментальное исследование алгоритма классификации, основанного на знаковой модели
Метод классификации многомерных данных, основанный на нейронных технологиях
Классификация – это отнесение конкретного объекта, представленного значениями его признаков, к одному из фиксированного перечня классов по определенному решающему правилу в соответствии с поставленной целью [1]. При этом под классом понимается классификационная группировка, объединяющая определенное множество объектов по некоторому признаку. Класс какого-либо объекта задается набором его частных проявлений [2].
Наибольший интерес представляет классификация многомерных данных, причем в качестве априорных множеств могут выступать не только количественные, но и качественные признаки объектов. Кроме того, данные могут не подчиняться нормальному закону распределения и не иметь однородной структуры.
Одним из наиболее сложных классификационных задач являются задачи диагностики состояний биоценозов, в частности задачи медицинской диагностики.
На сегодняшний день разработано большое количество систем, основанных на различных методах классификации [3, 4, 5, 6, 7, 8, 9, 10, 11].
В последующих разделах данной главы рассматриваются различные методы классификации многомерных данных. В разделе 1.1. описан статистический метод классификации, в частности метод дискриминантного анализа, в разделе 1.2. приводится описание методов классификации, основанных на нечеткой логике, в разделе 1.3. исследованы возможности нейросетевых технологий, описаны архитектуры нейронных сетей, наиболее часто применяющиеся в задачах диагностики, в разделе 1.4. описаны робастные методы классификации многомерных данных, раздел 1.5. содержит описание предметной области на примере микробиоценоза желудочно-кишечного тракта человека, в разделе 1.6. приведены выводы к данной главе, поставлены цели и задачи исследования.
В математической статистике задачи классификации называются также задачами дискриминантного анализа.
Дискриминантный анализ – метод классификации, основанный на функции расстояния. На качество работы таких классификаторов наибольшее влияние оказывают кластеризационные свойства классов. Можно рассчитывать на получение удовлетворительных практических результатов только в тех случаях, когда классы обнаруживают тенденцию к проявлению кластеризационных свойств в пространстве дискриминантных функций. Существуют классификаторы, использующие критерий максимума расстояния, как случай множественности эталонов, где решения принимаются на основании сравнения объектов не только с математическими ожиданиями, но и с другими «эталонными» объектами множеств, «правило ближайшего соседа» и т. д [12].
В качестве решающих функций в задачах дискриминантного анализа выступают построенные на этапе обучения канонические дискриминантные функции [12-15, 16, 17]: dkm = b0 + b1xkm1 + ...+ bnxkmn, m = 1,…,N, k = 1,…,G (1.1) где dkm – значение дискриминантной функции для m-того объекта в множестве k, xkmi – значение дискриминантной переменной xi для m-того объекта в множестве k, n – количество признаков. Коэффициенты bi , i=1,…,n определяются таким образом, чтобы с помощью дискриминантных функций наилучшим образом, т.е. с наименьшим числом ошибочных решений, произвести разделение объектов на классы. Основной характеристикой различий между классами являются центроиды. Центроид k-го класса – это n-мерный вектор, координатами которого являются средние значения признаков k-го класса. Центроид класса выполняет функцию типичного объекта класса.
Посредством дискриминантного анализа n-мерное пространство признаков преобразуется в q-мерное пространство канонических дискриминантных переменных, где q = n - 1 – число дискриминантных функций. Для данного объекта значение dkm, вычисленное по (1.1), можно интерпретировать как координату в пространстве канонических дискриминантных функций. Для определения коэффициентов bi , i = 1,… ,n дискриминантной функции dkm требуется решить систему из n уравнений с макасимальным числом нетривиальных решений q = n - 1.
R Каждому решению (l,v) соответствует один вектор коэффициентов R v =(v1, v2, …, vn) канонической дискриминантной функции dkm, в качестве которых можно непосредственно использовать vi, i = 1,… ,n. R Компоненты собственного вектора v следует нормировать для того, чтобы начало координат в пространстве канонических дискриминантных функций совпало с главным центроидом – вектором средних значений признаков всех объектов обучающего множества, [18]:
Нечеткая модель представления многомерных данных
Задача классификации решается на основании модели, которая представляет собой совокупность контролируемых параметров, значение которых описывает состояние объекта. Выборка называется одномерной, если каждый принадлежащий ей объект имеет один признак. Если же каждый объект имеет несколько признаков, выборка является многомерной. Если считать каждый признак многомерной выборки случайной величиной, то множество, которое описывает состояние многомерного объекта, можно представить как n-мерный вектор x . Решение задачи обработки многомерных данных, например, задачи классификации, можно упростить, если понизить размерность пространства признаков за счет того, что они, как правило, взаимосвязаны, а, значит, избыточны с точки зрения информации. Понижение размерности - это преобразование исходного n-мерного пространства в пространство меньшей размерности, в котором без существенной потери информации можно выбрать подмножество ненаблюдаемых переменных, число которых зависит от особенностей решаемой задачи классификации.
Дискриминантный анализ – это раздел многомерного статистического анализа, позволяющий изучать различия между множествами одновременно по нескольким переменным.
Опишем состояние множества векторомx=(1, 2,…, n) в n-мерном пространстве, где (1, n) – координаты этого вектора, которые представляют собой значения наблюдаемых параметров. На их основе вырабатывается правило, позволяющее классифицировать объекты.
По единственному состоянию системы обнаружить её структурные свойства невозможно, так как зависимость отражает характер совместного изменения значений компонент. Классифицировать объект можно, только обладая информацией о множестве состояний, каждое из которых представляет собой точку в n-мерном пространстве. Все множество многомерных состояний (многомерные данные) образует скопление точек – «облако», которое может описывать состояние одного объекта в разные моменты времени или состояния разнообразных объектов одного вида. Если группы наблюдаемых объектов различны, они образуют соответствующие им «облака» в некоторых областях пространства, характеристикой положения которых являются средние значения многомерной случайной величины в каждой группе - центроиды. Вероятность перекрывания групп зависит от того, насколько близко скопление точек к соответствующему центроиду. С целью классификации в работе используется дискриминантный анализ. Подробно метод дискриминантного анализа рассмотрен в разделе 1.1.
Основная задача дискриминации – нахождение линейной комбинации компонент, позволяющей оптимально разделить рассматриваемые множества. В данной работе дискриминантный метод сводится к методу проекций [105].
Многомерная случайная величина x=(1, 2,…, n) не всегда является гауссовой, что существенно затрудняет синтез оптимального правила принятия решения. При переходе от многомерной случайной величины к ее проекции х на направление, определяемое вектором a, полученная скалярная случайная величина на основании центральной предельной теоремы хорошо аппроксимируется гауссовым законом распределения (см. раздел 3.1). В качестве критерия в этом случае используется максимум отношения правдоподобия, который обеспечивает минимум средней вероятности ошибки: L=w1(x)/w2(x), (2.2) где w1(x) и w2(x) – плотности распределения вероятностей проекции x для двух априорных множеств 1 и 2. После подобного преобразования даже для небольшого числа достоверных данных полученная случайная величина имеет четко выраженный гауссов закон распределения.
Алгоритм классификации, основанный на нечеткой модели представления многомерных данных
Основным отличием алгоритма классификации, основанного на нечеткой модели представления многомерных данных (ее описание приведено в разделе 2.2), от «классического», является то, что при вычислении среднего расстояния от пациента до множеств «здоровых» и «больных» людей в качестве весовых коэффициентов используются значения характеристической функции принадлежности (2.15), описанной в разделе 2.2 настоящей диссертации [108]. Для описания нечеткого алгоритма классификации введем следующие условные обозначения: X – множество из m «здоровых» людей, состояние каждого из которых описывается вектором xi; Y – множество из u «больных» людей, состояние каждого из которых описывается вектором yi. Алгоритм классификации состояний биоценозов, основанный на нечеткой модели представления многомерных данных (алгоритм 3.2), включает в себя следующие шаги: 1. По (2.13) вычисляются расстояния rij между всеми элементами внутри множеств «здоровых» и «больных» людей; 2. Вычисляются значения характеристических функций m(xi ) , i = 1,m и m(yi ), i = 1,u (2.15); 3. С учетом весовых коэффициентов вычисляется значение среднего расстояния от состояния пациета до множеств «здоровых»(rXcp) и «больных» (rYcp ) людей (2.16); 4. Происходит сравнение rXcp и rYcp ; 5. Принятие решения о принадлежности состояния диагностируемого пациента в пользу наименьшего среднего расстояния (рис. 3.6). Рис. 3.6 – Блок-схема алгоритма 3.2
Сравнительный анализ алгоритмов, описанных в этом разделе, приведен в четвертой главе настоящей диссертации. 3.3. Алгоритм классификации, основанный на знаковой модели представления многомерных данных
Алгоритм классификации (алгоритм 3.3) основан на знаковой модели представления многомерных данных, описанной в разделе 2.3 настоящей диссертации.
Состояние отдельного индивида из множества описывается вектором x=(1, 2,…, n) в n-мерном пространстве, а вектором h=(1, 2, …,n) -состояние диагностируемого пациента. Координатами векторов являются значения количества микроорганизмов данного вида. Расстояние от значения j-го признака пациента до значений i-х признаков индивидов множества вычисляется как отношение количества индивидов, у которых значение i-го признака превысило порог, равный значению j-го признака пациента, к количеству индивидов в множестве [108].
Блок схема разработанного алгоритма представлена на рис. 3.7, при этом приняты следующие обозначения. Множества «здоровых» и «больных» людей обозначены соответственно через X и Y; x – номер выбранного индивида в множестве X, y – номер выбранного индивида в множестве Y. Количество индивидов в множестве X обозначим как mx, количество индивидов во множестве Y обозначим my.
Введем величину I, которая равна количеству признаков у каждого индивида множеств X и Y. Количество признаков у пациента обозначим J. Номер признака индивида из множества обозначим i, номер признака диагностируемого пациента j. Рис. 3.7 – Блок-схема алгоритма 3.3 Отличие разработанного алгоритма заключается в том, что окончательное решение принимается на основании так называемых «частных» решений. Решение о принадлежности пациента одному из множеств принимается в пользу того множества, в пользу которого принято максимальное количество «частных» решений. «Частные» решения принимаются посредством сравнения расстояний между значением 7-го признака пациента и значениями і-го признака индивидов принадлежащих соответственно первому и второму множествам. Все «частные» решения можно записать в виде матрицы, размером (пп) (рис. 3.8).
Поскольку количество значений і-го признака в множестве равно количеству в нем индивидов, то в качестве расстояния выбрана оценка вероятности превышения значениями і-го признака индивидов порога, равного значению 7-го признака пациента.
Данный алгоритм на основании структурных свойств знаковой модели, описанной в разделе 1.4. настоящей диссертации, обладает устойчивостью к изменению закона распределения априорных данных.
Разработан алгоритм классификации состоянии биоценозов, основанный на структурно-статистической модели представления многомерных данных (алгоритм 3.1), который отличается от известных возможностью выбора критерия отношения правдоподобия; 2. Разработан алгоритм классификации состоянии биоценозов, основанный на нечеткой модели представления многомерных данных (алгоритм 3.2), отличие которого заключается в использовании значений характеристической функции принадлежности в качестве весовых коэффициентов; 3. Разработан алгоритм классификации, основанный на знаковой модели представления многомерных данных (алгоритм 3.3), обладающий устойчивостью к изменению закона распределения априорных данных и отличающийся от известных тем, что окончательное решение принимается в пользу того множества, в пользу которого принято максимальное количество «частных» решений
В данной главе проводится экспериментальное исследование алгоритмов, рассмотренных в главе 3. В качестве экспериментальных данных были отобраны и систематизированы результаты бактериологических исследований микрофлоры по 29 видам микроорганизмов (n=29) (см. табл. 1.1).Тестовая выборка включает в себя анализы 250 «здоровых» и 250 «больных» человек. В качестве априорных данных использовалась выборка из 1000 «здоровых» и 1000 «больных» человек (разделы 4.1. – 4.3). Описаны алгоритмы диагностирования состояния микрофлоры ЖКТ человека с использованием нейросетевых технологий (раздел 4.4), в разделе 4.5. проведен сравнительный анализ алгоритмов классификации, раздел 4.6. включает описание программной реализации, в разделе 4.7. приведены выводы по главе.
Экспериментальное исследование алгоритма классификации, основанного на знаковой модели
В первой группе «безусловно положительных» микроорганизмов было выделено 6 категорий, во второй и третьей группе выделено по 5 категорий, в четвертой группе было выделено 2 категории. Также в последней группе не учитывается количество бактерий. Затем производим «оцифровку» ординальных переменных коэффициент1, коэффициент2, коэффициент3 для того, чтобы все примеры несли одинаковую информационную нагрузку. Для этого воспользуемся формулой: Dxk =Pk /P , (4.1) где Pk - число примеров класса k, а P - общее число примеров. Центр каждого такого отрезка будет являться численным значением для соответствующего ординального класса. После преобразований вектор входных параметров имеет следующий вид: X = {группа1; коэффициент1; гр.2; коэф.2; гр.3; коэф.3; коэф.4; коэф.5; коэф.6}. Коэффициенты с первого по третий принимают значения в промежутке [0; 1]. Таким образом, количество параметров входного вектора было сокращено с 31 до 9, удалось избавиться от размерности и произвести нормировку данных. Для конструирования и обучения нейронной сети был выбран готовый нейросетевой пакет Neuro Shell. Среди всех сетей, представленных в пакете Neuro Shell для решения задачи диагностики наиболее эффективными являются сеть Кохонена и сеть Ворда.
Классификация дисбиоза для всех возрастных групп с использованием одной архитектуры нейронной сети невозможна. Эффективность разделения на классы существенно затруднена из-за качественных и количественных различий в составе микрофлоры у людей разных возрастов, поэтому обучение проводилось для некоторых возрастных групп отдельно.
С помощью сети Кохонена не удалось оценить состояние микрофлоры ЖКТ человека для возрастных групп 0-24 часа и 1-6 суток. Сеть Ворда смогла провести корректную диагностику для возрастной группы 1-11 месяцев. Таким образом, с помощью сети Ворда удалось понизить ошибку диагностики до 30%.
Лучше результаты показала нейронная сеть, описанная в [116, 117], построенная по архитектуре трёхслойного персептрона. Обучение сети выполнено на выборке из 100 медико-биологических исследований ЖКТ. Работа обученной нейронной сети проверялась на контрольной выборке из 1000 медико-биологических исследований ЖКТ. Построенная нейронная сеть позволила классифицировать состояние микрофлоры ЖКТ с ошибкой 18%.
Выполнен сравнительный анализ разработанных алгоритмов классификации состояний биоценозов с методом, использующим нейросетевые технологии (см. раздел 4.4.). Используя нейросетевые технологии, не удалось провести классификацию биоценозов для всех возрастных групп, используя одну архитектуру нейронной сети (таблица 4.4).
Плюс в таблице обозначает работоспособность выбранного метода, а минус – невозможность отличить «норму» от «патологии».
Диагностирование с использованием архитектуры трехслойного персептрона, которая показала лучшие результаты среди нейронных сетей, обеспечило 82% правильных решений. Однако, ни одна из описанных выше архитектур не позволила провести классификацию состояний микробиоценоза ЖКТ у всех возрастных групп. Нечеткий алгоритм показал эффективность 80%, модифицированный знаковый алгоритм – 84%, структурно-статистический алгоритм – 95,3% (рис. 4.8). Рис. 4.8 – Сравнительная диаграмма алгоритмов классификации
Следует отметить, что, хотя эффективность структурно-статистического алгоритма является самой высокой, он не обладает устойчивостью, характерной для знакового алгоритма. Если входные параметры будут иметь «тяжелые хвосты» или большие выбросы, эффективность классификации структурно-статистического алгоритма снизится.
В процессе исследований на языке С++ была выполнена программная реализация структурно-статистического [118], нечеткого и знакового [119] алгоритмов классификации состояний биоценозов. Показавшие наибольшую эффективность структурно-статистический и знаковый алгоритмы в качестве модулей включены программу «Автоматизированная система микробиологического мониторинга микробиоценозов желудочно-кишечного тракта (ЖКТ)» [120]. В электронный бланк анализа вносятся результаты бактериологического исследования качественного и количественного состава микрофлоры ЖКТ пациента по 29 признакам. После нажатия кнопки «Применить» результаты работы алгоритмов отображаются в поле «Группа».
Результаты вычислительных экспериментов показывают, что разработанные алгоритмы классификации состояний биоценозов обладают высокой эффективностью.
Эффективность алгоритма классификации, основанного на нечеткой модели представления многомерных данных составляет 80%.
Наиболее высокие результаты показал алгоритм классификации, основанный на структурно-статистической модели представления многомерных данных. Процент правильной классификации составляет 95,3%.
Алгоритм, основанный на знаковой модели представления многомерных данных обладает эффективностью 84%, однако он обладает устойчивостью к «тяжелым хвостам» и большим выбросам закона распределения априорных данных.
Таким образом, настоящая работа обладает большим потенциалом для дальнейшего исследования, как в области классификации состояний биоценозов вне проблемы диагностирования состояния микробиома желудочно-кишечного тракта человека, так и для решения более сложной задачи – диагностирования степени дисбиоза ЖКТ. ЗАКЛЮЧЕНИЕ
Выполнена программная реализация разработанных алгоритмов. 6. Результаты диссертационной работы внедрены в лаборатории микробиома человека и средств его коррекции Федерального бюджетного учреждения науки Нижегородский научно-исследовательский институт эпидемиологии и микробиологии им. академика И.Н. Блохиной Роспотребнадзора и учебный процесс подготовки магистров по направлению «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. Р.Е. Алексеева.