Методы и алгоритмы анализа структуры многомерных данных


Содержание

Big Data: проблемы, методы анализа, алгоритмы Текст научной статьи по специальности « Автоматика. Вычислительная техника»

Аннотация научной статьи по автоматике и вычислительной технике, автор научной работы — Магеррамов Закир Тулуевич, Абдуллаев Вугар Гаджимахмудович, Магеррамова Айнур Закировна

Проводится обзор развития, характеристики и приме-нения технологий Big Data, показывается взаимосвязь технологии Big Data с промышленными предприяти-ями на примере металлургического производства . Описываются принципы обработки Big Data на основе модели Apache Hadoop и компании Oracle, а также ме-тоды анализа массивов данных. Некоторые методы анализа данных сопровождаются алгоритмами класте-ризации и в них применяется функция конкурентного сходства (FRiS-функция).

Похожие темы научных работ по автоматике и вычислительной технике , автор научной работы — Магеррамов Закир Тулуевич, Абдуллаев Вугар Гаджимахмудович, Магеррамова Айнур Закировна,

Текст научной работы на тему «Big Data: проблемы, методы анализа, алгоритмы»

BIG DATA: ПРОБЛЕМЫ, МЕТОДЫ АНАЛИЗА, АЛГОРИТМЫ

МАГЕРРАМОВ З.Т., АБДУЛЛАЕВ В.Г.,

Проводится обзор развития, характеристики и применения технологий Big Data, показывается взаимосвязь технологии Big Data с промышленными предприятиями на примере металлургического производства. Описываются принципы обработки Big Data на основе модели Apache Hadoop и компании Oracle, а также методы анализа массивов данных. Некоторые методы анализа данных сопровождаются алгоритмами кластеризации и в них применяется функция конкурентного сходства (FRiS-функция).

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

Термин Big Data относится к наборам данных, размер которых превосходит возможности типичных баз данных по хранению, управлению и анализу информации. Сами по себе алгоритмы Big Data возникли при внедрении первых высокопроизводительных серверов (мэйнфреймов), обладающих достаточными ресурсами для оперативной обработки информации и пригодных для компьютерных вычислений и дальнейшего анализа. Предпринимателей и ученых волнуют вопросы качественной интерпретации данных, разработки инструментов для работы с ними и развития технологий хранения. Этому способствует внедрение и активное использование облачных моделей хранения и вычислений.

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

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

литики рынка информационных технологий посвящают концепции выделенные исследования. Если обратить внимание на динамику роста данных, то обнаружим рост вычислительных средств, приложений и пользователей — от миллионов в эпоху мэйнфреймов до сотен миллионов в эпоху ПК и миллиардов пользователей в эпоху мобильных устройств, мобильного Интернета, социальных сетей, «облачных» технологий и построения всевозможных решений «умной» экономики. Отдельная тема — Интернет и мобильные технологии. Потоки информации генерируются всё новыми интернет-сервисами, социальными сетями, приложениями электронной торговли, приложениями о местонахождении абонентов сетей. Количество e-mail, отправляемых каждую секунду в мире — 2,9 млн, объем видео, закачиваемого на YouTube каждую минуту — 20 часов. Объем данных, обрабатываемых Google за день -24 петабайт. Количество сообщений на Твиттере в день — 50 млн. Количество минут, проведенных в Facebook в месяц — около 700 млрд. Объем данных, переданных/полученных на мобильные устройства — 1,3 экзабайт. Количество продуктов, заказываемых в Amazon в секунду — 72,9 [2].

2. Постановка задачи

Методику и инструменты работы со структурированными данными ИТ-индустрия создала давно -это реляционная модель данных и системы управления БД. Но современной тенденцией является потребность обработки большого объема неструктурированных данных, и это та область, где прежние подходы работают плохо или вообще не работают. Именно эта потребность требует новой методики обращения с данными, и сейчас все более популярной становится модель работы с Big Data. Занимаясь проблемами Big Data, перед разработчиками и учеными стоит задача — найти программное и техническое решение, способное легко интегрироваться в существующую инфраструктуру ЦОД и обеспечить все три этапа обработки информации: сбор, ее организацию и анализ.

3. Этапы и методы решения

3.1. Характеристики технологии Big Data. В качестве характеристик для больших данных Forrester определяет понятие Big Data как технологию в области аппаратного и программного обеспечения, которая объединяет, организует, управляет и анализирует данные, характеризующиеся «четырьмя V»: объемом (Volume), разнообразием (Variety), изменчивостью (Variability) и скоростью (Velocity) [2].

Эти характеристики являются существенными проблемами технологии Big Data. Рассмотрим каждую из этих составляющих.

Объем накопленных данных в корпорациях из разных сфер деятельности (источник: McKinsey)

Объем данных (Volume). Во введении мы описали лавинообразный рост объема данных в научных и персональных приложениях. Дополним картину информацией о том, какие объемы данных накопили корпорации. Только в США это более 100 Тбайт данных. При этом в разных вертикальных индустриях объем данных существенно различается, следовательно, актуальность применения технологии Big Data в них различна (рисунок) [2]. Разнообразие форматов данных (Variety). Способность приложения обрабатывать большие массивы данных, поступающих из разных источников в различных форматах, является главным критерием отнесения его к технологии Big Data. Многие бизнес-задачи и научные эксперименты требуют совместной обработки данных различных форматов — это могут быть табличные данные в СУБД, иерархические данные, текстовые документы, видео, изображения, аудиофайлы. Пример подобного рода задачи из области медицины: как найти оптимальный курс лечения для конкретного пациента, базируясь на огромном количестве историй болезней пациентов (которые постоянно меняются), а также на базе данных медицинских исследований и геномных данных? Другой пример — из области оптимизации бизнес-процессов: как провести анализ структурированных данных из ERP (Enterprise Resource Planning) — приложения, а также слабоструктурированных данных в виде логфайлов и неструктурированного текста из отзывов покупателей? Третий пример — из сферы прогнозирования погоды: как выполнить анализ климата на базе многолетних метеорологических данных и данных, поступающих со спутника в реальном времени?

Скорость поступления и обработки информации (velocity). В области Big Data выделяют ещё одну проблему: недостаточно высокая скорость обработки данных. В ряде задач эта скорость должна быть очень высокой. Например, биржевым игрокам иногда нужно мгновенно принять решение, основываясь на большом количестве данных о состоянии рынка — за пару секунд ситуация уже может измениться. Очень большая скорость поступления данных характерна для многих научных задач. Например, только один экспериментальный синхротрон Advanced Photon Source (APS) в Аргоннской лаборатории, используемый в числе прочего для томографической съемки объектов на субмикронных разрешениях, может ежедневно генерировать 150 Тбайт информации. Ценность для бизнеса (Value). Компания IDC тоже выделяет «четыре V», характеризующие данные, однако параметр Variety (изменчивость), который применяет компания Forrester, она заменяет на параметр Value (ценность). IDC подчеркивает, что параметр Value — один из основных, позволяющих выделить Big Data как новое явление. Он относится к экономическому эффекту, который технология Big Data обеспечивает пользователям. Информация — это главный аспект успешного прогнозирования роста и составления маркетинговой стратегии в умелых руках маркетолога. Big Data является точнейшим инструментом маркетолога для предсказания будущего компании.

Применение технологии Big Data могжет быть полезно для решения следующих задач:

— лучше узнавать своих потребителей, привлекать аналогичную аудиторию в Интернете;

— оценивать уровень удовлетворенности клиентов;

— находить и внедрять новые способы, увеличивающие доверие клиентов;

— создавать проекты, пользующиеся спросом по прогнозированию рыночной ситуации;

— маркетинг и оптимизация продаж;

— эффективно сегментировать клиентов;

— совершенствовать качество товаров и услуг;

— принимать более обоснованные управленческие решения на основе анализа Big Data;

— оптимизировать портфель инвестиций;

— повышать производительности труда.

3.2. Big Data и промышленные предприятия. Сфера использования технологий Big Data обширна. Известно, что основной поток информации генерируют не люди. Источником служат роботы, находящиеся в постоянном взаимодействии друг с другом. Это приборы для мониторинга,

сенсоры, системы наблюдения, операционные системы персональных устройств, смартфоны, интеллектуальные системы, датчики и прочее. Все они задают бешеный темп роста объема данных, что приводит к появлению потребности наращивать количество рабочих серверов (и реальных, и виртуальных) — как следствие, расширять и внедрять новые data-центры. На промышленных предприятиях объем информации неуклонно растет за счет данных, полученных с датчиков, измерительных и «умных» устройств. Самыми перспективными устройствами считаются датчики, которые могут передавать данные в режиме реального времени. Все устройства на предприятии с помощью таких датчиков могут быть объединены в сеть, а технологии Big Data позволят обрабатывать информацию, поступающую с них, и проводить необходимые мероприятия в автоматическом режиме. Например, предприятия могут с помощью датчиков получать ежеминутные данные о состоянии своего оборудования и на основе этих данных предсказывать оптимальное время для замены и обслуживания. Слишком ранняя замена приведет к дополнительным расходам, а поздняя

— к потере прибыли вследствие простоя оборудования.

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

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

— шахты и карьеры по добыче руд и каменных углей;

— горно-обогатительные комбинаты для подготовки руды к плавке;

— коксохимические заводы или цеха для подготовки углей к коксованию и извлечению полезных химических продуктов;

— энергетические цеха для получения сжатого воздуха, кислорода, а также очистки газов металлургических производств;

— доменные цеха для выплавки чугуна и ферросплавов;

— заводы для производства ферросплавов;

— сталеплавильные цеха (конвертерные, мартеновские, электросталеплавильные) для производства стали;

— прокатные цеха для получения сортового проката (листы, балки, рельсы, прутки, проволока)

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

— технологических (АСУ ТП);

— логистических (АСУ транспортной логистики);

— управления (MES — Manufacturing execution system и ERP — Enterprise Resource Planning системы).

Системы АСУ ТП собирают данные с датчиков агрегатов о состоянии и режимах технологических процессов. С систем контроля качества могут поступать видеоизображения полос прокатки и дефектов на полосе, карты ультразвукового контроля. АСУ транспортной логистики содержат данные о перемещении материалов. ERP и МЕS владеют информацией о заказах, планировании, оперативном управлении обработкой материалов, о состоянии запасов на складах. Например, только цепочка производства от выплавки металла до выпуска автолиста может включать в себя от 7000 до 15000 источников разнородных неструктурированных данных, поступающих в реальном масштабе времени. Высокая степень автоматизации производства порождает у персонала предприятий «иллюзию доступности данных» [5].

Оснащение производства современными системами автоматизации приводит к оцифровке всех получаемых данных, и это создает у персонала предприятия иллюзию их доступности. Но «оцифровано» — не значит «доступно». Данные о технологических процессах есть в АСУ ТП агрегатов, данные о производстве — в MES системах, данные о заказах — в ERP. Перечисленные выше характеристики Big Data («четыре V») хорошо подходят для структурированных и неструктурированных данных металлургического производства:

— множество сигналов с датчиков контроля технологических процессов,

— карты ультразвукового контроля,

— изображения полос прокатки, содержащих дефекты на полосе,

— данные о перемещении продукции и материалов,

— данные о заказах и поставщиках. Технология Big Data позволит свести данные из АСУ ТП, АСУ транспортной логистики и систем класса ERP и MES воедино, тратя на это в разы меньшее количество времени, по сравнению с

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

3.3. Обработка и методы анализа Big Data. С точки зрения обработки в основу технологий Big Data положены два основных принципа:

1) распределенного хранения данных;

2) распределенной обработки, с учетом локальности данных.

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

Распределенная обработка с учетом локальности данных означает, что программа обработки доставляется на вычислитель, находящийся как можно ближе к обрабатываемым данным. Это принципиально отличается от традиционного подхода, когда вычислительные мощности и подсистема хранения разделены и данные должны быть доставлены на вычислитель. Таким образом, технологии Big Data опираются на вычислительные кластеры из множества вычислителей, снабженных локальной подсистемой хранения. Доступ к данным и их обработка осуществляются специальным программным обеспечением. Наиболее известным и интенсивно развивающимся проектом в области Big Data является Apache Hadoop [6,7]. В настоящее время на рынке информационных систем и программного обеспечения синонимом Big Data является технология Hadoop, которая представляет собой программный фреймворк, позволяющий хранить и обрабатывать данные с помощью компьютерных кластеров, используя парадигму MapReduce. Основными составляющими платформы Hadoop являются:

— отказоустойчивая распределенная файловая система Hadoop Distributed File System (HDFS), при помощи которой осуществляется хранение;

— программный интерфейс Map Reduce, который является основой для написания приложений, обрабатывающих большие объемы структурированных и неструктурированных данных параллельно на кластере, состоящем из тысяч машин;

— Apache Hadoop YARN, выполняющий функцию управления данными.

В соответствии с подходом MapReduce обработка данных состоит из двух шагов: Map и Reduce. На шаге Map выполняется предварительная обработка данных, которая осуществляется параллельно на различных узлах кластера. На шаге Reduce происходит сведение предварительно обработанных данных в единый результат. В основе модели работы Apache Hadoop лежат три основных принципа. Во-первых, данные равномерно распределяются на внутренних дисках множества серверов, объединенных HDFS. Во-вторых, не данные передаются программе обработки, а программа — к данным. Третий принцип — данные обрабатываются параллельно, причем эта возможность заложена архитектурно в программном интерфейсе Map Reduce. Таким образом, вместо привычной концепции «база дан-ных+сервер» у нас имеется кластер из множества недорогих узлов, каждый из которых является и хранилищем, и обработчиком данных, а само понятие «база данных» отсутствует. Платформа Hadoop позволяет сократить время на обработку и подготовку данных, расширяет возможности по анализу, позволяет оперировать новой информацией и неструктурированными данными. Компания Oracle разбивает жизненный цикл обработки информации на три этапа и использует для каждого из них собственное решение:

1) Сбор, обработка и структурирование данных. В качестве решения применяется Oracle Big Data Appliance — это предустановленный Hadoop-кла-стер, Oracle NoSQL Database и средства интеграции с другими хранилищами данных. Задача Oracle Big Data Appliance состоит в хранении и первичной обработке неструктурированной или частично структурированной информации, т.е. как раз в том, что у систем на базе Hadoop получается лучше всего.

2) Агрегация и анализ данных. Для работы со структурированными данными используется комплекс Oracle Exadata. Модули интеграции Oracle Big Data Appliance позволяют оперативно загружать данные в Oracle Exadata, а также получать доступ к данным «на лету» из Oracle Exadata.

3) Аналитика данных в реальном времени. Для максимально оперативного анализа полученных данных используется Oracle Exalytics Database Machine, которая позволяет решать аналитические задачи фактически в режиме «online». Существует множество разнообразных методов анализа массивов данных, в основе которых лежит примерно одинаковый набор инструментов анализа данных [3] : многомерный анализ (OLAP), регрессия, классификация, кластеризация и поиск закономерностей. Некоторые из перечисленных методик вовсе не обязательно применимы исключительно к большим данным и могут с успехом

использоваться для меньших по объему массивов (например, A/B-тестирование, регрессионный анализ).

Многомерный анализ — суть метода заключается в построении многомерного куба и получении его различных срезов. Результатом анализа, как правило, является таблица, в ячейках которой содержатся агрегированные показатели (количество, среднее, минимальное или максимальное значение и так далее). В зависимости от реализации, существуют три типа системы многомерного анализа (OLAP): многомерная OLAP (Multidimensional OLAP — MOLAP); реляционная OLAP (Relational OLAP — ROLAP); гибридная OLAP (Hybrid OLAP — HOLAP). Среди них ROLAP-системы являются наиболее прозрачными и изученными, поскольку основываются на широко распространенных реляционных СУБД, в то время как внутреннее устройство MOLAP и HOLAP обычно более закрыто и относится к области «ноу-хау» конкретных коммерческих продуктов.

MOLAP представляет информацию в виде «честной» многомерной модели, но внутри используются те же подходы, что и в ROLAP: схемы «звезда» и «снежинка». С точки зрения СУБД база данных ROLAP — это обыкновенная реляционная база, и для нее необходимо поддерживать весь перечень операций. Однако это не позволяет, во-первых, жестко контролировать этапы ввода данных. Во-вторых, собирать статистику и подбирать оптимальные структуры для хранения индексов. В-третьих, оптимизировать размещение данных на диске для обеспечения высокой скорости ввода/вывода. В-четвертых, при выполнении аналитических запросов из-за высоких требований к быстродействию нет возможности произвести глубокий статистический анализ и выработать оптимальный план выполнения. В ROLAP используются «родные» реляционные оптимизаторы запроса, которые никак не учитывают «многомерность» базы данных. Технологии MOLAP лишены перечисленных недостатков и благодаря этому позволяют добиться большей скорости анализа.

Выбор технологии MOLAP/ROLAP/HOLAP при анализе Big Data зависит от частоты обновления базы данных. С точки зрения распараллеливания обработки, на первый взгляд, все просто — любой многомерный куб может быть «разрезан» по делениям одного из измерений и распределен между несколькими серверами. Например, можно разделить куб на временные периоды (по годам и месяцам), по территориальному признаку (каждый сервер отвечает за свой регион) и так далее. Критерием для разделения куба является следующий принцип: выполнение многомерного запроса

должно ложиться не на один сервер, а на несколько, после чего полученные результаты собираются в единое целое. Например, если пользователь запрашивает статистику продаж по стране за указанный промежуток времени, а данные распределены по нескольким региональным ОЬЛР-серверам, то каждый сервер возвращает свой собственный ответ, которые затем собираются воедино. Если же данные будут распределены по временному критерию, то при выполнении рассматриваемого примера запроса вся нагрузка ляжет на один сервер.

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

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

Регрессия — под регрессией понимают построение параметрической функции, описывающей изменение указанной числовой величины в указанный промежуток времени. Эта функция строится на основе известных данных, а затем используется для предсказания дальнейших значений этой же величины. На вход метода поступает последовательность пар вида «время — значение», описывающая поведение этой величины при заданных условиях, например, количество продаж конкретного вида товара в конкретном регионе. На выходе — параметры функции, описывающей поведение исследуемой величины. Независимо от вида используемой параметрической функции подбор значений ее параметров осуществляется одним и тем же способом. Вычисляется суммарная разница между наблюдаемыми значениями и значениями, которые дает функция при текущих значениях ее параметров. Затем определяется, как следует подкорректировать значения параметров для того, чтобы уменьшить текущую суммарную разницу. Эти операции повторяются до тех пор, пока суммарная разница не достигнет необходимого минимума или ее дальнейшее уменьшение станет невозможным. С точки зрения обработки данных при регрессионном анализе ключевыми операциями являются вычисление текущей суммарной разницы и корректировка значений параметров. Если первая операция распараллеливается очевидным образом (сумма вычисляется по частям на отдельных серверах, а затем суммируется на центральном

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

Если регрессионный анализ сводится к вычислению взвешенных сумм, то он обладает примерно той же степенью применимости и при работе с Big Data, что и многомерный анализ. Таким образом, системы регрессионного анализа волне могут масштабироваться и работать в условиях распределенного сбора информации. Классификация — ее задача отчасти похожа на задачу регрессии и заключается в попытке построения и использования зависимости одной переменной от нескольких других. Например, имея базу данных о цене объектов недвижимости, можно построить систему правил, позволяющую на основе параметров нового объекта предсказать его примерную цену. Отличие классификации от регрессии состоит в том, что анализируется не временной ряд — подаваемые на вход значения никак не могут быть упорядочены. На текущий момент разработано множество методов классификации (функции Байеса, нейронные сети, машины поддерживающих векторов, деревья решений и т. д.), каждый из которых имеет под собой хорошо проработанную научную теорию. Вместе с тем все методы классификации строятся по одной и той же схеме. Сначала производится обучение алгоритма на сравнительно небольшой выборке, а затем — применение полученных правил к остальной выборке. На первом этапе возможно копирование массива данных на один сервер для запуска «классического» алгоритма обучения без распараллеливания работы. Однако на втором этапе данные могут обрабатываться независимо — система правил, полученная по итогам самообучения, копируется на каждый сервер, и через нее прогоняется весь массив данных, хранящийся на этом сервере. Полученные результаты могут либо сохраняться там же на сервере, либо отправляться для дальнейшей обработки. Таким образом, на этапе обучения классификаторов о работе с Big Data пока речи не идет — не существует выборок такого объема, подготовленных для обучения систем, а на этапе классификации отдельные порции данных обрабатываются

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

Проблема кластеризации Big Data состоит в том, что имеющиеся алгоритмы предполагают возможность непосредственного обращения к любой информационной сущности в исходных данных (заранее невозможно предугадать, какие именно сущности понадобятся алгоритму). В свою очередь, исходные данные могут быть распределены по разным серверам, и при этом не гарантируется, что каждый кластер хранится строго на одном сервере. Если распределение данных по серверам делать прозрачным для алгоритма кластеризации, то это неизбежно приведет к копированию больших объемов с одного сервера на другой. Решение проблемы может быть следующим. На каждом сервере запускается свой алгоритм, который оперирует только данными этого сервера, а на выходе дает параметры найденных кластеров и их веса, оцениваемые исходя из количества элементов внутри кластера. Затем полученная информация собирается на центральном сервере и производится метакластеризация — выделение групп близко расположенных кластеров с учетом их весов. Этот метод универсален, хорошо распараллеливается и может использовать любые другие алгоритмы кластеризации, однако он требует проведения серьезных научных исследований, тестирования на реальных данных и сравнения полученных результатов с другими «локальными» методами.


Таким образом, для анализа Big Data подавляющая часть методов кластеризации неприменима в чистом виде и необходимы дополнительные исследования.

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

на покупки, а признаками — купленные товары. Задача поиска закономерностей сводится к выявлению правил вида «если присутствуют признаки Ai,A2 . An , то присутствуют и признаки Б1; B2. Bm, при этом каждое правило характеризуется двумя параметрами: вероятностью срабатывания и поддержкой. Первый параметр показывает, как часто выполняется данное правило, а второй — как часто применимо данное правило, т.е. как часто встречается сочетание признаков A1, A2. An.

A/B тестирование — методика, в которой контрольная выборка поочередно сравнивается с другими. Тем самым удается выявить оптимальную комбинацию показателей для достижения, например, наилучшей ответной реакции потребителей на маркетинговое предложение. Большие данные позволяют провести огромное количество итераций и таким образом получить статистически достоверный результат.

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

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

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

Генетические алгоритмы — в этой методике возможные решения представляют в виде «хромосом», которые могут комбинироваться и мутировать. Как и в процессе естественной эволюции, выживает наиболее приспособленная особь. Оптимизация — набор численных методов для ре-дизайна сложных систем и процессов для улучшения одного или нескольких показателей. Помогает в принятии стратегических решений, например, состава выводимой на рынок продуктовой линейки, проведении инвестиционного анализа. Визуализация аналитических данных — методы для представления информации в виде рисунков, графиков, схем и диаграмм с использованием интерактивных возможностей и анимации как для результатов, так и для использования в качестве исходных данных.

3.4. Алгоритмы кластеризации Big Data. При выполнении кластеризации основной проблемой является определение числа кластеров. Число методов разбиения множества на кластеры довольно велико. Все их можно подразделить на иерархические и неиерархические.

В неиерархических алгоритмах характер их работы и условие остановки необходимо заранее регламентировать часто довольно большим числом параметров, что иногда затруднительно, особенно на начальном этапе изучения материала. Но в таких алгоритмах достигается большая гибкость в варьировании кластеризации и обычно определяется число кластеров. С другой стороны, когда объекты характеризуются большим числом признаков (параметров), то приобретает большое значение задача группировки признаков. В иерархических алгоритмах фактически отказываются от определения числа кластеров, строя полное дерево вложенных кластеров (дендро-грамму). Их число определяется из предположений, не относящихся к работе алгоритмов, например, по динамике изменения порога расщепления (слияния) кластеров. Трудности таких алгоритмов хорошо изучены: выбор мер близости кластеров, проблема инверсий индексации в дендро-граммах, негибкость иерархических классификаций, которая иногда весьма нежелательна. Тем не менее, представление кластеризации в виде денд-рограммы позволяет получить наиболее полное представление о структуре кластеров. 3.4.1. Алгоритм к-средних (к-тват). Алгоритм к-тват строит к кластеров, расположенных на возможно больших расстояниях друг от друга. Основной тип задач, которые решает алгоритм к-средних, — наличие предположений (гипотез) относительно числа кластеров, при этом они должны быть различны настолько, насколько это возможно. Общая идея алгоритма: заданное фиксированное число к кластеров наблюдения сопоставляется кластерам так, что средние в кластере максимально возможно отличаются друг от друга. Описание алгоритма [8]: Этап 1. Первоначальное распределение объектов по кластерам. Выбирается число к, и на первом шаге эти точки считаются «центрами» кластеров. Каждому кластеру соответствует один центр. Выбор начальных центроидов может осуществляться следующим образом: выбор к-наблюдений для максимизации начального расстояния; случайный выбор к-наблюдений; выбор первых к-наблюде-ний. В результате каждый объект назначен определенному кластеру.

Этап 2. Вычисляются центры кластеров, которыми далее считаются покоординатные средние кластеров. Объекты опять перераспределяются. Процесс вычисления центров и перераспределения объектов продолжается до тех пор, пока не выполнено одно из условий: кластерные центры стабилизировались, т.е. все наблюдения принадлежат кластеру, которому принадлежали до текущей итерации; число итераций равно максимуму.

Выбор числа кластеров является сложным вопросом. Если нет предположений относительно этого числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и более, сравнивая полученные результаты. Достоинства метода: простота использования; быстрота использования; понятность и прозрачность алгоритма.

Недостатки метода: алгоритм слишком чувствителен к выбросам, которые могут искажать среднее; медленная работа на больших базах данных; необходимо задавать количество кластеров. 3.4.2. Алгоритм HCM (Hard C — Means). Метод Hard C — Means применяется, в основном, для кластеризации больших наборов числовых данных. Описание алгоритма [9]: Шаг 1. Инициализация кластерных центров Ci (i = 1,2. c). Это можно сделать, выбрав случайным образом c — векторов из входного набора. Шаг 2. Вычисление рядовой матрицы M. Она состоит из элементов m^:

Cjll , для всех i ^ j,

i = 1,2, . c,k = 1,2. K, .0, остальное

где К — количество элементов во входном наборе данных. Матрица М обладает следующими свойствами:

Z mij = 1, Z mij = i = 1 j = 1

где ци — степень принадлежности объекта к к кластеру 1; с — количество кластеров; М — количество элементов. При этом:

0 i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Этап 1. Установить параметры алгоритма: с — количество кластеров; т — экспоненциальный вес, определяющий нечеткость, размазаность кластеров (те [1, да)); е — параметр останова алгоритма. Этап 2. Генерация случайным образом матрицы нечеткого разбиения с учетом условий (1). Этап 3. Расчет центров кластеров: ^=1 НЙ-1Х1 ^

Этап 4. Расчет расстояния между объектами Х и центрами кластеров:

Ои = 7НХк-VIу2 ,к = ТТМ; 1=1″»» .

Этап 5. Пересчет элементов матрицы разбиения с

учетом следующих условий:

Шаг 3. Расчет объектной функции: c c /

J = Z Ji = Z( Z l|Uk — Cil

Шаг 4. Пересчет кластерных центров уравнением:

Ci = id ^k,ukeCi uk , где |Ci | — количество элементов в i-м кластере. Шаг 5. Переход на шаг 2.

Достоинствами метода являются: легкость реализации, вычислительная простота, а недостатками — задание количества кластеров, отсутствие гарантии в нахождении оптимального решения. 3.4.3. Алгоритм нечеткой кластеризации Fuzzy C-means.

Метод нечеткой кластеризации Fuzzy C-means так же применяется, в основном, для кластеризации больших наборов числовых данных. Описание алгоритма [10]:

Пусть нечеткие кластеры задаются матрицей разбиения:

F= KJ , hd ^[0,1], k = 1JM ; i = 1ccc ,

если Dk = hk = [J ,j = i , j = 1,c .

Этап 6. Проверить условие ||F — F*|| i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Шаг 3. Каждый объект а, за исключением 81, пробуется на роль второго столпа, столпом 81 назначается объект, для которого значение функции Р* <(а, б^>оказывается максимальным. Шаг 4. Все объекты исходной выборки распределяются между столпами б1, б2 , образуя кластеры А1, А2, соответственно. Объект а относится к кластеру А1, если расстояние от а до з1 меньше, чем для любого Б>.

Шаг 5. После добавления кластера А2, эталонный объект для кластера А1 выбирается снова, но уже среди объектов кластера А1Столпом б12 назначается объект, на котором достигает своего максимума функция F*<(a, Б2)>, описанная ниже. Аналогично, находится столп Б22 для второго кластера. Полученная кластеризация представляет собой решение задачи для к=2:

Р(5)= ¿ЕаеЛ F(a, 8) . Шаг 6. Далее для каждого нового столпа повторяются те же операции, что и при добавлении объекта два. Шаг 5 выполняется для всех кластеров текущей кластеризации.

Данный алгоритм имеет высокую трудоёмкость -0(п3), а также алгоритму требуется более ячеек п2 памяти, что обусловлено необходимостью хранения матрицы парных расстояний. 3.4.5. Алгоритм FRiS-Stolp.

Другим применением РШ8-функции является один из алгоритмов отбора эталонных образцов

(столпов) для метрического классификатора, именуемый FRiS-Stolp. Выбор эталонов делается с помощью алгоритма FRiS-Stolp. Его идея состоит в том, что все объекты первого образа по очереди назначаются эталонами. Он нацелен на выбор минимального числа столпов, которые защищают не только самих себя, но обеспечивают заданную надежность защиты всех остальных объектов обучающей выборки. Первыми выбираются столпы, защищающие максимально возможное количество объектов с заданной надежностью. По этой причине при нормальных распределениях в первую очередь будут выбраны столпы, расположенные в точках математического ожидания [12]. Алгоритм FRiS-Stolp:

Шаг 1. Проверим вариант, при котором первый случайно выбранный объект aj является единственным столпом образа S1; а все другие образы в качестве столпов имеют свои объекты. Для всех объектов aj ^ aj первого образа находим расстояние r1j до своего столпа aj и расстояние r2j до ближайшего объекта чужого образа. По этим расстояниям вычисляется значение FRiS-функции для каждого объекта aj первого образа. Находим те mj объектов первого образа, значение функций принадлежности F которых выше заданного порога F*, например, F*=0. По этим т^ объектам вычисляем суммарное значение FRiS-функции Fj, которое характеризует пригодность объекта ßj на роль столпа.

Шаг 2. Аналогичную процедуру повторяем, назначая в качестве столпа все М объектов первого образа по очереди.

Шаг 3. Находим объект aj с максимальным значением Fj и объявляем его первым столпом A11 первого кластера C11 первого образа S1. Шаг 4. Исключаем из первого образа mj объектов, входящих в первый кластер. Шаг 5. Для остальных объектов первого образа находим следующий столп повторением шагов 14.

Шаг 6. Процесс останавливается, если все объекты первого образа оказались включенными в свои кластеры.

Шаг 7. Восстанавливаем все объекты образа S1 и

для образа S2 выполняем шаги 1-6.

Шаг 8. Повторяем шаги 1-7 для всех остальных

На этом шаге заканчивается первый этап поиска столпов. Каждый столп Aj защищает подмножество объектов mj своего кластера Cj. 4. Выводы

Эпоха Big Data уже наступила — объемы данных, генерируемых в науке, бизнесе, индустрии и управлении ИТ, растут экспоненциально. Однако существующие приложения обработки Big Data

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

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

В данный момент можно прогнозировать высокоскоростную доставку данных из распределенных источников, оптимизацию переноса данных можно осуществить, например, с помощью развивающихся сейчас методов управления ресурсами с соблюдением гарантий качества обслуживания (QoS). В промышленной сфере можно прогнозировать аппаратные средства со специализированными датчиками для точного снятия показателей данных, а также развитие приложений, которые будут эти данные собирать, обрабатывать и структурировать, передавать в центры обработки, визуализировать для легкого восприятия, что, в свою очередь, облегчит принятие правильного решения. В [13] разработана параллельная реализация алгоритма FRiS для кластеризации научных статей на основе технологии параллельных вычислений Message Passing Interface (MPI). В качестве меры близости при кластеризации принята мера конкурентного сходства. Для настройки весовых коэффициентов при вычислении меры сходства используется генетический алгоритм.

Литература: 1. Gantz John, Reinsel David. http://www.emc.com/collateral/analyst-reports/idc-the-

digital-universe-in-2020.pdf. 2. Найдич А. www.com-press.ru. 3. Селезнев К. Проблемы анализа Больших Данных // Открытые системы. СУБД №07, 2012 с.25-30. 4. Бабич В.К. и др. Основы металлургического производства. М.: Металлургия, 1988. 272 с. 5. Федин М.В. Перспективы использования систем обработки больших данных (bigdata) в металлургической промышленности // Economics. 2015, № 8(9). C. 52-54. 6. Проект Apache Hadoop. https://hadoop.apache.org/. 7. Артемов С. Big Data: новые возможности для растущего бизнеса.

http://www.pcweek.ru/upload/iblock/d05/iet-big-data.pdf. 8. Daniel Fasulo «An Analysis of Recent Work on Clustering Algorithms». Электронное издание. 9. Паклин Н. Алгоритмы кластеризации на службе Data Mining.

http://www.basegroup.ru/clusterization/ datamining.htm. 10. Jan Jantzen «Neurofuzzy Modelling». Электронное издание. 11. Борисова И.А.,Загоруйко Н.Г. Труды Всероссийской Конференции «Знания-Онтологии-Теории». Новосибирск, 2007. Том II. С. 67-76. 12. Борисова И.А. и др. Труды Всероссийской конференции «Знания — Онтология — Теория», Новосибирск, 2007. Том I. С.37-44. 13. Мансурова М.Е. и др. Parallel computational technologies (PCT) 2020. http://ceur-ws.org/Vol-1576/128.pdf. Transliterated bibliography:

1. Gantz John, Reinsel David. http://www.emc.com/collat-eral/analyst-reports/idc-the-digital-universe-in-2020.pdf.

2. Andrey Naydich. www.compress.ru.

3. Konstantin Seleznev. Problemyi analiza Bolshih Dannyih // Otkryityie sistemyi. SUBD #07, 2012 s.25-30.

4. Babich V.K. i dr. Osnovyi metallurgicheskogo proiz-vodstva. M: Metallurgiya, 1988. 272 s.

5. Fedin M.V. Perspektivy ispol’zovanija sistem obrabotki bol’shih dannyh (bigdata) v metallurgicheskoj promyshlennosti // Economics. 2015, № 8(9). C. 52-54. 6. Project Apache Hadoop. https://hadoop.apache.org/.

Илон Маск рекомендует:  Что такое код oracle

7. Artemov S. Big Data: novyie vozmozhnosti dlya rastuschego biznesa.

8. Daniel Fasulo «An Analysis of Recent Work on Clustering Algorithms». Elektronnoe izdanie.

9. Paklin N. Algoritmyi klasterizatsii na sluzhbe Data Mining.

10. Jan Jantzen «Neurofuzzy Modelling». Elektronnoe izdanie.

11. Borisova I.A.,Zagoruyko N.G. Trudyi Vserossiy-skoy Konferentsii «Znaniya-Ontologii-Teorii»,Novo—sibir-sk, 2007, Tom II, s. 67-76.

12. Borisova I.A. i dr. Trudyi Vserossiyskoy konfe-rentsii «Znaniya-Ontologiya-Teoriya», Novosibirsk, 2007. Tom I. S.37-44.

13. Mansurova M.E. i dr. Parallel computational technologies (PCT) 2020. http://ceur-ws.org/Vol-1576/128.pdf.

Поступила в редколлегию 12.04.2020 Рецензент: д-р техн. наук, проф. Кривуля Г.Ф.

Магеррамов Закир Тулуевич, канд. техн. наук, доцент кафедры «Прикладная информатика» Азербайджанского Технического Университета. Научные интересы: численные методы, моделирование и оптимальное управленияе, информационные технологии, объектно-ориентированное

Конспект лекций по курсу «основы проектирования систем искусственного интеллекта»

Название Конспект лекций по курсу «основы проектирования систем искусственного интеллекта»
страница 15/18
Дата конвертации 05.06.2015
Размер 1.29 Mb.
Тип Конспект
источник
1. /gl1-4.doc
2. /gl5.doc
3. /gl6.doc
Конспект лекций по курсу «основы проектирования систем искусственного интеллекта»
Экспертные системы Базовые понятия. Методика построения. Статистический подход (пример)
Лекции 14-16. Машинная эволюция

Методы и алгоритмы анализа структуры многомерных данных

Кластерный анализ

Кластерный анализ предназначен для разбиения множест­ва объектов на заданное или неизвестное число классов на основании некоторого математического критерия качества классификации (cluster (англ.) — гроздь, пучок, скопление, группа элементов, характеризуемых каким-либо общим свой­ством). Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования:

а) внутри групп объекты должны быть тесно связаны между собой;

б) объекты разных групп должны быть далеки друг от друга;

в) при прочих равных условиях распределения объектов по группам должны быть равномерными.

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


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

Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть wi — i-я группа (класс, кластер) объектов, Ni — число объектов, образующих группу wi, вектор i — среднее арифме­тическое объектов, входящих в wi (другими словами [i — «центр тяжести» i-й группы), a q ( wl, wm ) — расстояние меж­ду группами wl и wm

Рис. 11. Различные способы определения расстояния между кластерами wl и wm: 1 — по центрам тяжести, 2 — по ближайшим объектам, 3 — по самым далеким объектам

Расстояние ближайшего соседа есть расстояние между бли­жайшими объектами кластеров:

Расстояние дальнего соседа — расстояние между самыми дальними объектами кластеров:

Расстояние центров тяжести равно расстоянию между центральными точками кластеров:

Обобщенное (по Колмогорову) расстояние между классами, или обобщенное K-расстояние, вычисляется по формуле

В частности, при    и при   - имеем

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

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

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

Многообразие алгоритмов кластерного анализа обусловле­но также множеством различных критериев, выражающих те или иные аспекты качества автоматического группирования. Простейший критерий качества непосредственно базируется на величине расстояния между кластерами. Однако такой критерий не учитывает «населенность» кластеров — относи­тельную плотность распределения объектов внутри выделяе­мых группировок. Поэтому другие критерии основываются на вычислении средних расстояний между объектами внутри кла­стеров. Но наиболее часто применяются критерии в виде от­ношений показателей «населенности» кластеров к расстоянию между ними. Это, например, может быть отношение суммы межклассовых расстояний к сумме внутриклассовых (между объектами) расстояний или отношение общей дисперсии дан­ных к сумме внутриклассовых дисперсий и дисперсии центров кластеров.

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

Иерархическое группирование

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

Классификационные процедуры иерархического типа предназначены для получения наглядного представления о стратификационной структуре всей исследуемой совокупности объектов. Эти процедуры основаны на последовательном объе­динении кластеров (агломеративные процедуры) и на последо­вательном разбиении (дивизимные процедуры). Наибольшее распространение получили агломеративные процедуры. Рас­смотрим последовательность операций в таких процедурах.

На первом шаге все объекты считаются отдельными кла­стерами. Затем на каждом последующем шаге два ближайших кластера объединяются в один. Каждое объединение уменьшает число кластеров на один так, что в конце концов все объекты объединяются в один кластер. Наиболее подходящее разбиение выбирает чаще всего сам исследователь, которому предостав­ляется дендрограмма, отображающая результаты группирования объектов на всех шагах алгоритма (Рис. 12). Могут од­новременно также использоваться и математические критерии качества группирования.

Различные варианты определения расстояния между кла­стерами дают различные варианты иерархических агломеративных процедур. Учитывая специфику подобных процедур, для задания расстояния между классами оказывается достаточным указать порядок пересчета расстояний между классом wl и классом w(m, n) являющимся объединением двух других классов wm и wn по расстояниям qmn = q(wm, wn) и qln = q(wl, wn) между этими классами. В литературе предлагается следующая общая формула для вычисления расстояния между некоторым классом wl и классом w(m, n):

где , ,  и  — числовые коэффициенты, определяющие на­целенность агломеративной процедуры на решение той или иной экстремальной задачи. В частности, полагая  =  = - = ½ и  = 0, приходим к расстоянию, измеряемому по принципу ближайшего соседа. Если положить  =  =  = ½ и  = 0, то расстояние между двумя классами определится как расстояние между двумя самыми далекими объектами этих классов, то есть это будет расстояние дальнего соседа. И, наконец, выбор коэффициентов соотношения по формулам

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

Использование следующей модификации формулы

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

Лекция 1-2: Базовые понятия ии

Назва Лекция 1-2: Базовые понятия ии
Сторінка 15/18
Дата 14.07.2012
Розмір 1.56 Mb.
Тип Лекция
1. /LECT_P1.rtf Лекция 1-2: Базовые понятия ии

Методы и алгоритмы анализа структуры многомерных данных

Кластерный анализ

Кластерный анализ предназначен для разбиения множест­ва объектов на заданное или неизвестное число классов на основании некоторого математического критерия качества классификации (cluster (англ.) — гроздь, пучок, скопление, группа элементов, характеризуемых каким-либо общим свой­ством). Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования:

а) внутри групп объекты должны быть тесно связаны между собой;

б) объекты разных групп должны быть далеки друг от друга;

в) при прочих равных условиях распределения объектов по группам должны быть равномерными.

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

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

Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть wi — i-я группа (класс, кластер) объектов, Ni — число объектов, образующих группу wi, вектор i — среднее арифме­тическое объектов, входящих в wi (другими словами [i — «центр тяжести» i-й группы), a q ( wl, wm ) — расстояние меж­ду группами wl и wm

Рис. . Различные способы определения расстояния между кластерами wl и wm: 1 — по центрам тяжести, 2 — по ближайшим объектам, 3 — по самым далеким объектам

Расстояние ближайшего соседа есть расстояние между бли­жайшими объектами кластеров:

Расстояние дальнего соседа — расстояние между самыми дальними объектами кластеров:

Расстояние центров тяжести равно расстоянию между центральными точками кластеров:

Обобщенное (по Колмогорову) расстояние между классами, или обобщенное K-расстояние, вычисляется по формуле

В частности, при и при — имеем

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

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

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

Многообразие алгоритмов кластерного анализа обусловле­но также множеством различных критериев, выражающих те или иные аспекты качества автоматического группирования. Простейший критерий качества непосредственно базируется на величине расстояния между кластерами. Однако такой критерий не учитывает «населенность» кластеров — относи­тельную плотность распределения объектов внутри выделяе­мых группировок. Поэтому другие критерии основываются на вычислении средних расстояний между объектами внутри кла­стеров. Но наиболее часто применяются критерии в виде от­ношений показателей «населенности» кластеров к расстоянию между ними. Это, например, может быть отношение суммы межклассовых расстояний к сумме внутриклассовых (между объектами) расстояний или отношение общей дисперсии дан­ных к сумме внутриклассовых дисперсий и дисперсии центров кластеров.

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

Иерархическое группирование

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

Классификационные процедуры иерархического типа предназначены для получения наглядного представления о стратификационной структуре всей исследуемой совокупности объектов. Эти процедуры основаны на последовательном объе­динении кластеров (агломеративные процедуры) и на последо­вательном разбиении (дивизимные процедуры). Наибольшее распространение получили агломеративные процедуры. Рас­смотрим последовательность операций в таких процедурах.

На первом шаге все объекты считаются отдельными кла­стерами. Затем на каждом последующем шаге два ближайших кластера объединяются в один. Каждое объединение уменьшает число кластеров на один так, что в конце концов все объекты объединяются в один кластер. Наиболее подходящее разбиение выбирает чаще всего сам исследователь, которому предостав­ляется дендрограмма, отображающая результаты группирования объектов на всех шагах алгоритма (Рис. ). Могут од­новременно также использоваться и математические критерии качества группирования.

Различные варианты определения расстояния между кла­стерами дают различные варианты иерархических агломеративных процедур. Учитывая специфику подобных процедур, для задания расстояния между классами оказывается достаточным указать порядок пересчета расстояний между классом wl и классом w(m, n) являющимся объединением двух других классов wm и wn по расстояниям qmn = q(wm, wn) и qln = q(wl, wn) между этими классами. В литературе предлагается следующая общая формула для вычисления расстояния между некоторым классом wl и классом w(m, n):

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

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

Использование следующей модификации формулы

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

1. Введение

Одной из основных современных задач практически во всех областях человеческой деятельности на сегодняшний день является анализ многомерных данных. Многомерные данные являются результатами численных исследований, технических показателей, обобщением экономической и финансовой информации и т.д. Необходимость обработки, анализа и адекватной трактовки этих данных породила такую интенсивно развивающуюся научную дисциплину, как анализ многомерных данных (Data Analysis). Одной из важнейших составляющих это направление дисциплин является кластерный анализ [1,2], рассматривающий различные способы группировки объектов внутри облака многомерных данных. Методов и алгоритмов кластерного анализа на современном этапе существует очень много, они постоянно развиваются и отличаются большим разнообразием. Это могут быть, например, алгоритмы, реализующие полный перебор сочетаний объектов или осуществляющие случайные разбиения множества объектов. Многообразие алгоритмов кластерного анализа обусловлено также множеством различных критериев, выражающих те или иные аспекты качества автоматического группирования. Надо заметить, что ряд источников [2,3] указывает на ряд специфических особенностей методов, алгоритмов и подходов кластерного анализа, которые исследователь должен учитывать в обязательном порядке:

А) Многие методы кластерного анализа — довольно простые процедуры, которые, как правило, не имеют достаточного статистического обоснования. Они — не более чем правдоподобные алгоритмы, используемые для создания кластеров объектов.

Б) Методы кластерного анализа разрабатывались для многих научных дисциплин, а потому несут на себе отпечатки специфики этих дисциплин. Это важно отметить, потому что каждая дисциплина предъявляет свои требования к отбору данных, к форме их представления, к предполагаемой структуре классификации. Так как кластерные методы порой не более чем правила для создания групп, то пользователь должен знать особенности области происхождения облака данных [2].

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

Г) Цель кластерного анализа заключается в поиске существующих структур. В то же время его действие состоит в привнесении структуры в анализируемые данные. Хотя цель кластеризации и заключается в нахождении структуры, на деле кластерный метод привносит структуру в данные и эта структура может не совпадать с искомой, «реальной». Кластерный метод всегда размещает объекты по группам, которые могут радикально различаться по составу, если применяются различные методы кластеризации. Ключом к использованию кластерного анализа является умение отличать «реальные» группировки от навязанных методом кластеризации данных.

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

Положительный ответ на этот вопрос дают алгоритмы понижения размерности и визуального представления многомерных данных во вложенных в исходный объем многообразиях меньшей размерности.

К числу таких семейств алгоритмов можно отнести метод главных компонент и отображение исходного многомерного объема в главных компонентах (PCA) [2,5], построение самоорганизующихся карт (SOM) [4], построение упругих карт (Elastic Maps) [5,6] с разными свойствами упругости или эластичности и отображение исходного многомерного объема в этих картах.

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

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

— размерность данного многообразия меньше либо равна трем, что дает возможность визуального представления на уровне человеческого восприятия;

— наличие устойчивых связей основных координатных направлений многообразия со всеми координатными направлениями в изучаемом многомерном объеме;

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

Отметим, что общей идеей всех вышеперечисленных подходов является отображение многомерных данных в представимую человеком размерность, например, на плоскость так, чтобы точки данных, близкие на плоскости (на карте), были близки и в исходном пространстве. С помощью визуализации мы можем получать большое количество информации о данных сразу, без какой-либо обработки. Становятся видимыми области группировки данных и разреженные области. Упрощается решение задач классификации. Видно количество кластеров, их форма, взаимное расположение и т.д. Обратим внимание, что это естественная классификация данных, не требующая каких-либо специальных действий над исходными данными. Следует отметить, что подобная постановка задачи может оказаться весьма полезной при обработке, анализе и визуализации многомерных решений задач вычислительной газовой динамики, имеющих небольшую размерность [7-12].

2. Используемые методы

Данный раздел рассматривает общие основные подходы, применяемые для визуального выделения кластеров в многомерном объеме данных. К этим основным подходам относятся: построение самоорганизующихся карт (SOM), построение визуального представления многомерного облака данных в пространстве главных компонент (PCA), построение упругих карт (Elastic Maps).

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

Одним из первых и наиболее известных подходов подобного рода стал алгоритм построения самоорганизующихся карт SOM (Self-Organised Maps), предложенный Кохоненом [4]. В современном представлении карты SOM трактуются как двумерные сетки узлов, размещенные в изучаемом многомерном пространстве.

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

Метод главных компонент (PCA) [2,5] позволяет уменьшить размерность исследуемого многомерного объема данных с наименьшей потерей информации. Главные компоненты представляют собой ортогональную систему координат, в которой дисперсии компонент характеризуют их статистические свойства.

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

Другим важным подходом к нелинейному сокращению размерности данных является построение упругих карт (Elastic Map). Идеология и алгоритмы реализации этого подхода подробно представлены в работах [5,6]. По построению, она представляет собой систему упругих пружин, вложенную в многомерное пространство данных. Данный подход основывается на аналогии с механикой: главное многообразие, проходящее через «середину» данных, может быть представлено как упругая мембрана или пластинка. В отличие от карт SOM, метод упругих карт изначально формулируется как оптимизационная задача, предполагающая оптимизацию заданного функционала от взаимного расположения карты и данных. При создании критерия оптимальности авторы включили в него среднее расстояние от точки данных до ближайшего узла карты. Варьирование параметров упругости (процедура отжига) заключается в построении упругих карт с последовательным уменьшением коэффициентов упругости, в силу чего карта становится более мягкой и гибкой, наиболее оптимальным образом подстраиваясь к точкам исходного многомерного объема данных. После построения упругую карту можно развернуть в плоскость для наблюдения кластерной структуры в изучаемом объеме данных. Построение упругих карт на сегодняшний день является широко распространенным методом анализа данных. Применение упругих карт позволяет более точно и четко определять кластерную структуру изучаемых многомерных объемов данных.

3. Построение технологической цепочки алгоритмов обработки многомерного объема данных

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

Рис. 1. Схема технологической цепочки обработки многомерного массива с целью исследования кластерной структуры.


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

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

Далее при необходимости обеспечить более глубокий уровень детализации и анализа, построенную плоскость двух первых главных компонент надо сделать гибкой, чтобы она могла наилучшим образом подстраиваться к исходному многомерному облаку данных. Для этого плоскость надо преобразовать в упругую карту. После построения упругой карты проводится ее развертка. Это обеспечивает более четкое (менее размытое) визуальное разделение кластеров. Далее следует вспомнить о том, что в отличие от предыдущих подходов, построение упругой карты является оптимизационной задачей, имеющей два внешних параметра – коэффициенты упругости карты λ и μ. Для того чтобы увеличить «резкость» изображения и обеспечить тем самым еще более четкое разделение кластеров, необходимо уменьшать коэффициенты упругости карты λ и μ. При этом карта становится более гибкой, лучше подстраивается к исходным многомерным данным, и при развертке обеспечивает максимально четкое разделение кластеров в рассматриваемой кластерной структуре.

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

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

4. Пример реализации

Покажем, как работает технологическая цепочка на примере конкретной задачи. В качестве тестовой задачи возьмем широко известный тестовый объем многомерных данных IRIS [5]. Данный объем представляет собой набор данных, основанных на измерениях характеристик растений – цветков ириса. Набор данных описывает три сорта ирисов и состоит из 150 точек в четырехмерном пространстве признаков.

Согласно описанию технологической цепочки, приведенному в предыдущем разделе, на предварительном этапе строится самоорганизующаяся карта SOM для рассматриваемого исходного набора данных. Это должно позволить получить следующую информацию – есть ли кластерная структура, как таковая, и сколько классов она в себе содержит. На рисунке 2 представлены результаты построения самоорганизующейся карты SOM для рассматриваемого набора данных. Кластерная структура в объеме данных есть, и она содержит три класса.

Рис. 2. Результат построения карт SOM.

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

На рисунке 3 представлены результаты отображения исходного объема данных в исходных координатах для трехмерного случая. Различные классы выделены цветами – красным, синим и зеленым. На рисунке видно, что точки всех трех классов смешаны, хотя красные точки в своем большинстве лежат отдельно.

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

Рис. 3. Трехмерное представление исследуемого объема данных в исходных координатах.

Рис. 4. Трехмерное представление исследуемого объема данных в пространстве главных компонент.

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

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

С этой целью начнем построение упругих карт и проецирование точек исследуемого объема на поверхности этих карт. (Для построения изображений упругих карт далее использована программа V >

Рис. 5. Построение «жесткой» упругой карты при λ=5, μ=5 в исходных координатах.

Рис. 6. Построение «жесткой» упругой карты при λ=5, μ=5 в исходных координатах с раскраской по плотности данных.

Однако для того, чтобы упругая карта наилучшим образом была ориентирована в многомерном пространстве, ее следует отображать в пространстве главных компонент, как рекомендуется в работах [5,6]. Переход в пространство главных компонент отражен на рисунках 7 – 9. Рисунок 7 представляет ту же самую «жесткую» упругую карту в пространстве главных компонент.

Рис. 7. Построение «жесткой» упругой карты при λ=5, μ=5 в пространстве главных компонент.

На рисунке 8 представлена упругая карта в пространстве главных компонент с раскраской по значению плотности данных. Видно, как плоскость главных компонент изгибается, стараясь наилучшим образом подстроиться к многомерному объему данных. На рисунке 9 представлена развертка упругой карты без раскраски. Разделение синих и зеленых точек улучшилось, впрочем, как и разделение на классы в целом. Картина разделения как бы «проявляется», становясь все более четкой.

Рис. 8. Построение «жесткой» упругой карты при λ=5, μ=5 в пространстве главных компонент, с раскраской по плотности данных.

Рис. 9. Развертка «жесткой» упругой карты при λ=5, μ=5 в пространстве главных компонент.

Продолжая следовать технологической цепочке алгоритмов и методов, представленной в разделе 2, для дальнейшего улучшения четкости разделения на кластеры в исследуемом многомерном объеме данных применим так называемую процедуру отжига. Для этой цели будем уменьшать коэффициенты упругости λ и μ, делая карту более «мягкой». Это обеспечивает нам улучшенную адаптацию упругой карты к данным рассматриваемого многомерного объема.

На рисунках 10 – 12 представлены результаты построения упругой карты при значениях коэффициентов упругости λ=1, μ=1. Рисунок 10 представляет поверхность упругой карты для данных значений коэффициентов упругости. Рисунок 11 представляет ту же карту, раскрашенную в соответствии с плотностью данных. На рисунке 12 представлена развертка упругой карты в плоскость. Можно проследить некоторое улучшение разделения на классы.

Рис. 10. Построение упругой карты при λ=1, μ=1 в пространстве главных компонент.

Рис. 11. Построение упругой карты при λ=1, μ=1 в пространстве главных компонент. с раскраской по плотности данных.

Рис. 12. Развертка упругой карты при λ=1, μ=1 в пространстве главных компонент.

Для дальнейшего улучшения качества разделения продолжим процесс отжига, то есть уменьшения коэффициентов упругости λ и μ. Зададим для дальнейшего построения их значения равными λ=0.01, μ=0.01. Визуальные представления упругой карты для этих параметров представлены на рисунках 13-15, представляющих поверхность упругой карты (Рис.13), поверхность упругой карты, раскрашенную в соответствии с плотностью данных (Рис.14), и развертку упругой карты в плоскость (Рис.15). Разделение на классы стало еще более четким и заметным (зеленые и синие точки на рисунке 15).

Рис. 13. Построение упругой карты при λ=0.01, μ=0.01 в пространстве главных компонент.

Рис. 14. Построение упругой карты при λ=0.01, μ=0.01 в пространстве главных компонент. с раскраской по плотности данных.

Рис. 15. Развертка упругой карты при λ=0.01, μ=0.01 в пространстве главных компонент.

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

5. Обсуждение

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

6. Заключение

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

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

Благодарности

Данная работа выполнена при частичной поддержке грантов РФФИ (проекты 13-0100367а и 14-01-00769а).

Литература

1. Мандель И.Д. Кластерный анализ. М.: Финансы и статистика, 1988. 176 с.

2. Ким Дж., Мюллер Ч. и др. Факторный, дискриминантный и кластерный анализ. М.: Финансы и статистика, 1989. 216 с.

3. Дюран Б., Оделл П. Кластерный анализ. М.: Статистика, 1977. 128 с.

4. Kohonen T. Self-Organizing Maps. Springer: Berlin – Heidelberg, 1997.

5. Зиновьев А. Ю., Визуализация многомерных данных, Красноярск, Изд. КГТУ, 2000. 180 с.

6. A. Gorban, B. Kegl, D. Wunsch, A. Zinovyev (Eds.), Principal Manifolds for Data Visualisation and Dimension Reduction, LNCSE 58, Springer, Berlin – Heidelberg – New York, 2007.

7. Bondarev A.E, Galaktionov V.A. Parametric Optimizing Analysis of Unsteady Structures and Visualization of Multidimensional Data. International Journal of Modeling, Simulation and Scientific Computing, 2013, V.04, N supp01, 13 p., DOI 10.1142/S1793962313410043. http://dx.doi.org/10.1142/S1793962313410043.

8. Bondarev A.E., Galaktionov V.A. State-of-the-Art in Data Visualization for CFD Problems. Scientific Visualization, 2013 vol.5, no. 4, pp. 18-30.

9. Bondarev A.E., Galaktionov V.A. Current Visualization Trends in CFD Problems. Applied Mathematical Sciences, 2014, vol. 8, no. 28, pp. 1357 — 1368,

10. Bondarev A.E. Multidimensional Data Analysis in CFD Problems. Scientific Visualization, 2014, vol. 6, no. 5, pp. 59-66.

11. Bondarev A.E., Galaktionov V.A. Analysis of Space-Time Structures Appearance for Non-Stationary CFD Problems. Proceedings of 15-th International Conference On Computational Science ICCS 2015 Rejkjavik, Iceland, June 01-03 2015, Procedia Computer Science, Volume 51, 2015, Pages 1801–1810.

12. Bondarev A.E., Galaktionov V.A. Multidimensional data analysis and visualization for time-dependent CFD problems. Programming and Computer Software, 2015, vol. 41, no. 5, pp. 247–252, DOI: 10.1134/S0361768815050023.

METHODS DESIGN FOR VISUAL ANALYSIS OF CLUSTERS IN MULTIDIMENSIONAL DATA VOLUMES

A.E. Bondarev, V.A. Galaktionov

Keldysh Institute of Applied Mathematics RAS

The paper considers design of algorithms intended for visual analysis of cluster structures in multidimensional data volumes. The paper is aimed to design of a set of visualization and visual analytics methods for cluster structure studies without applying of clusterization methods influencing at original data. To analyze clusters in original data volume we propose to use the methods of original data points mapping to enclosed manifolds having less dimensionality. The proposed approach is based on self-organized maps (SOM) design, principal components analysis (PCA) and application of elastic maps with further varying of elasticity parameters for the last ones. To provide complete processing of original data volume all mentioned above methods and approaches should be organized in a form of pipeline. The applying of such pipeline allows one to get insight of cluster structures at the different levels of details for multidimensional data volume in question.

Keywords: multidimensional data, cluster structures, visual analysis

References

1. Mandel’ I.D. Klasternyj analiz [Cluster analysis]. Finance and Statistics, 1988. 176 pp. [In Russian]

2. Kim j., Mjuller Ch. et al. Faktornyj, diskriminantnyj i klasternyj analiz [Factorial, discriminant and cluster analysis]. Finance and Statistics, 1989. 216 pp. [In Russian]

Илон Маск рекомендует:  Asp файл browscap ini

3. Djuran B., Odell P. Klasternyj analiz [Cluster analysis]. M .: Statistics, 1977. 128 pp. [In Russian]

4. Kohonen T. Self-Organizing Maps. Springer: Berlin – Heidelberg, 1997.

5. Zinov’ev A. Yu., Vizualizacija mnogomernyh dannyh [visualization of multidimensional data], Krasnoyarsk, Ed. KSTU, 2000. 180 pp. [In Russian]

6. A. Gorban, B. Kegl, D. Wunsch, A. Zinovyev (Eds.), Principal Manifolds for Data Visualisation and Dimension Reduction, LNCSE 58, Springer, Berlin – Heidelberg – New York, 2007.

Лекция 1-2: Базовые понятия ии

Название Лекция 1-2: Базовые понятия ии
страница 15/18
Дата конвертации 21.05.2012
Размер 1.29 Mb.
Тип Лекция
1. /LECT_P1.DOC Лекция 1-2: Базовые понятия ии

Методы и алгоритмы анализа структуры многомерных данных

Кластерный анализ

Кластерный анализ предназначен для разбиения множест­ва объектов на заданное или неизвестное число классов на основании некоторого математического критерия качества классификации (cluster (англ.) — гроздь, пучок, скопление, группа элементов, характеризуемых каким-либо общим свой­ством). Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования:

а) внутри групп объекты должны быть тесно связаны между собой;

б) объекты разных групп должны быть далеки друг от друга;

в) при прочих равных условиях распределения объектов по группам должны быть равномерными.

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

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

Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть wi — i-я группа (класс, кластер) объектов, Ni — число объектов, образующих группу wi, вектор i — среднее арифме­тическое объектов, входящих в wi (другими словами [i — «центр тяжести» i-й группы), a q ( wl, wm ) — расстояние меж­ду группами wl и wm

Рис. 11. Различные способы определения расстояния между кластерами wl и wm: 1 — по центрам тяжести, 2 — по ближайшим объектам, 3 — по самым далеким объектам

Расстояние ближайшего соседа есть расстояние между бли­жайшими объектами кластеров:

Расстояние дальнего соседа — расстояние между самыми дальними объектами кластеров:


gif» name=»object68″ align=absm >

Расстояние центров тяжести равно расстоянию между центральными точками кластеров:

Обобщенное (по Колмогорову) расстояние между классами, или обобщенное K-расстояние, вычисляется по формуле

В частности, при    и при   - имеем

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

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

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

Многообразие алгоритмов кластерного анализа обусловле­но также множеством различных критериев, выражающих те или иные аспекты качества автоматического группирования. Простейший критерий качества непосредственно базируется на величине расстояния между кластерами. Однако такой критерий не учитывает «населенность» кластеров — относи­тельную плотность распределения объектов внутри выделяе­мых группировок. Поэтому другие критерии основываются на вычислении средних расстояний между объектами внутри кла­стеров. Но наиболее часто применяются критерии в виде от­ношений показателей «населенности» кластеров к расстоянию между ними. Это, например, может быть отношение суммы межклассовых расстояний к сумме внутриклассовых (между объектами) расстояний или отношение общей дисперсии дан­ных к сумме внутриклассовых дисперсий и дисперсии центров кластеров.

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

Иерархическое группирование

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

Классификационные процедуры иерархического типа предназначены для получения наглядного представления о стратификационной структуре всей исследуемой совокупности объектов. Эти процедуры основаны на последовательном объе­динении кластеров (агломеративные процедуры) и на последо­вательном разбиении (дивизимные процедуры). Наибольшее распространение получили агломеративные процедуры. Рас­смотрим последовательность операций в таких процедурах.

На первом шаге все объекты считаются отдельными кла­стерами. Затем на каждом последующем шаге два ближайших кластера объединяются в один. Каждое объединение уменьшает число кластеров на один так, что в конце концов все объекты объединяются в один кластер. Наиболее подходящее разбиение выбирает чаще всего сам исследователь, которому предостав­ляется дендрограмма, отображающая результаты группирования объектов на всех шагах алгоритма (Рис. 12). Могут од­новременно также использоваться и математические критерии качества группирования.

Различные варианты определения расстояния между кла­стерами дают различные варианты иерархических агломеративных процедур. Учитывая специфику подобных процедур, для задания расстояния между классами оказывается достаточным указать порядок пересчета расстояний между классом wl и классом w(m, n) являющимся объединением двух других классов wm и wn по расстояниям qmn = q(wm, wn) и qln = q(wl, wn) между этими классами. В литературе предлагается следующая общая формула для вычисления расстояния между некоторым классом wl и классом w(m, n):

где , ,  и  — числовые коэффициенты, определяющие на­целенность агломеративной процедуры на решение той или иной экстремальной задачи. В частности, полагая  =  = - = Ѕ и  = 0, приходим к расстоянию, измеряемому по принципу ближайшего соседа. Если положить  =  =  = Ѕ и  = 0, то расстояние между двумя классами определится как расстояние между двумя самыми далекими объектами этих классов, то есть это будет расстояние дальнего соседа. И, наконец, выбор коэффициентов соотношения по формулам

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

Использование следующей модификации формулы

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

Алгоритмы и программный комплекс анализа многомерных данных о природных объектах с применением статистического и нечеткого моделирования

Разработка методики проведения комплексного анализа многомерных неполных данных с применением нечеткого и статистического моделирования. Идентификация структуры — определение характеристик нечеткой модели. Анализ архитектуры программного комплекса.

Рубрика Программирование, компьютеры и кибернетика
Вид автореферат
Язык русский
Дата добавления 02.09.2020
Размер файла 457,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

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

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

Важным моментом, решаемым в процессе построения НС, является идентификация ее параметров. Актуальной является задача повышения точности вывода НС на реальных данных. Для настройки параметров НС используются различные методы оптимизации, наряду с методами, основанными на производных, применяются генетические алгоритмы, эволюционные стратегии и нейронные сети. Эволюционные стратегии совместно с эволюционным программированием и генетический алгоритм представляют три главных направления развития эволюционного моделирования. Несмотря на то, что каждый из методов возник независимо от других, они характеризуются рядом общих свойств. Для любого из них формируется исходная популяция, которая подвергается селекции и воздействию различных генетических операторов, что позволяет находить лучшие решения. Построение алгоритмов на основе метода эволюционной стратегии основываются на трудах Ingo Rechenberg, Hans-Paul Schwefel, H.-G. Beyer, J, Klockgether, S, Kern, A.Auger, Д. Рутковской, S.L. Luke, N. Hansen, A. Ostermeir, а алгоритмы нечеткого моделирования на работах А.Н. Аверкина, И.А. Ходашинского, И.З. Батыршина, Л.С. Берштейна, Л.Г. Комарцовой, А.В. Язенина, Н.Г., Ярушкиной, P.H. Ishibuchi,n, R.R. Yager, T.Yasukawa, L.-X. Wang, L. Zadeh, H. Bahrami, M. Abdechiri, M.R. Meybodi, Y. Zhang, X. Wu, Z. Xing, W. Hu.

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

При исследовании природных объектов, таких как нефть, для повышения наглядности результатов и помощи в их интерпретации требуют включения в анализ пространственных свойств объектов исследования — географические координаты, глубина залегания и др. Для учета и анализа пространственных данных применяются геоинформационные системы (ГИС), позволяющие визуализировать большие объемы информации с пространственными свойствами, включая связанную с ними количественную информацию об объектах.

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

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

Объект исследования — природные пространственно-распределенные объекты, например нефти, для описания свойств которых используются многомерные массивы данных.

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

Цель работы — разработка алгоритмов и комплекса программ анализа многомерных данных о различных свойствах природных объектов, основанных на сочетании методов нечеткого моделирования, многомерного статистического анализа и методов пространственного анализа с применением геоинформационных систем.

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

2. Разработка методики проведения комплексного анализа многомерных неполных данных с применением нечеткого и статистического моделирования.

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

4. Проведение исследований разработанных алгоритмов на типовых контрольных примерах и тестовых выборках.

5. Проектирование и разработка программного комплекса.

6. Применение и внедрение программного комплекса анализа многомерных неполных данных.

Методы исследований: методы нечеткого моделирования, нечетких множеств, математической статистики, линейной алгебры, метод факторного анализа, численные методы, метод кластеризации, методы пространственного анализа средствами ГИС, методы объектно-ориентированного программирования.

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

Научная новизна. В диссертационной работе получены следующие новые научные результаты:

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

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

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

Созданный программный комплекс внедрен в ИХН СО РАН и применялся при выполнении Бюджетного проекта V.39.3.1. Исследование физико-химических свойств гетерогенных нефтесодержащих систем и их структурной организации на микро- и наноуровне с целью развития научных основ экологически безопасных технологий извлечения вязких парафинистых нефтей по теме «Разработка методических вопросов восстановления пропущенных значений в выборочном массиве из базы данных по свойствам вязких парафинистых нефтей с использованием методов вероятностного моделирования и кластерного анализа данных» и проекта РФФИ 11-05-98023 «Исследование влияния химического состава и условий залегания нефтей на численность, распространение и активность пластовой микрофлоры для повышения нефтеотдачи».

Разработанный программный комплекс внедрен в Федеральном государственном бюджетном учреждении науки Институте мониторинга климатических и экологических систем Сибирского отделения Российской академии наук (ИМКЭС СО РАН) и используется в рамках выполнения работ по программе интеграционного проекта № 70 Сибирского отделения РАН «Анализ и прогноз проявлений вынуждающего воздействия в ритмике метеорологических полей Северного полушария Земли» для анализа разнородной междисциплинарной информации о состоянии и изменениях климатообразующих параметров исследуемых территорий.

Разработанные алгоритмы и программный комплекс используются при выполнении научно-исследовательских работ (задание № 2014/225) в рамках базовой части государственного задания Минобрнауки России для проведения комплексного анализа многомерных характеристик, описывающих процесс принятия решений в производственно-экономических и социальных системах, для решения задач определения границ объектов территориального устройства на основе многомерных данных об инфраструктурной среде и социально-экономических характеристиках в условиях нормативных ограничений.

Алгоритмы блока «Анализ данных» программного комплекса используются в учебном процессе при проведении лабораторных работ по дисциплине «Качество программных систем» на кафедре АОИ ТУСУР, являясь инструментом анализа показателей качества программных систем.

Апробация работы. Основные положения работы докладывались на научных конференциях различного уровня. На VII и VIII международных конференциях «Химии нефти и газа» г. Томск, 2009, 2012 г.; на VII всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии», г. Томск, 2009 г.; на IV Всероссийской конференции молодых ученых «Материаловедение, технологии и экология в 3-м тысячелетии», г. Томск, 2009 г.; на IX всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии», г. Томск, 2011 г.; на XVIII Международной научно-практической конференции студентов, аспирантов и молодых ученых «Современные техника и технологии», г. Томск, 2012 г.; на III Всероссийской молодежной научной конференции «Современные проблемы математики и механики», г. Томск, 2012 г.; на Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР», г. Томск, 2010, 2011, 2012 г, так же опубликованы работы в сборнике «Доклады ТУСУР» (г. Томск, 2013 г.), в журнале «Информационные технологии» (г. Москва, 2013-2014 г.).

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

Соответствуют пункту 5 паспорта специальности: Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента.

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

3. Алгоритм восстановления пропущенных значений на основе модифицированного алгоритма идентификации НС с заданной структурой позволяет увеличить точность восстановления пропущенных значений по сравнению с алгоритмами, предлагаемыми другими авторами как минимум в 1,5 раза на тестовых данных.

Соответствуют пункту 1 и 3 паспорта специальности: 1)Разработка новых математических методов моделирования объектов и явлений. 3)Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий.

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

Соответствует пункту 4 паспорта специальности: Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента.

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

Публикации. Основные положения диссертации отражены в 19 опубликованных работах. В том числе 5 статей напечатаны в ведущих рецензируемых научных журналах и изданиях РФ, в которых ВАК рекомендует публикацию основных результатов диссертационных работ, и получено 1 свидетельство об официальной регистрации программы для ЭВМ (свидетельство № 2013619931 от 21.10.2013 г.).

1. Обзор проблемы исследования

Описываются основные понятия и методы анализа неполных многомерных данных, их классификация и модели. Приведены основные понятия и методы нечеткого моделирования многомерных данных с пропусками, методы анализа и классификации многомерных данных. Рассмотрен пространственный анализ данных с применением ГИС и приведен обзор существующих программных пакетов статистического и нечеткого моделирования. В работе проанализированы основные особенности изучаемых объектов, которые затрудняют проведение анализа данных, такие как многомерность данных, пропущенные значения в данных (неполнота описания объектов), разнородность данных (различные единицы измерения характеристик), наличие пространственных свойств и статистический характер информации об объектах.

Проведенный обзор литературы выявил, что для восстановления пропущенных значений в многомерных данных применяются методы и статистического, и нечеткого моделирования. Однако у статистических методов существуют ограничения к структуре данных: данные должны быть однородны и нормально распределены, такие условия при исследовании природных объектов соблюдаются редко. В связи с чем для выбора метода восстановления был проведен ряд экспериментов на тестовой (полной) выборке, состоящей из 141 записи о физико-химических свойствах нефти. В имеющуюся выборку вводились пропуски, согласно методу скользящего экзамена, затем пропуски восстанавливались, и рассчитывалась точность, с которой пропуски были восстановлены. Результаты эксперимента показали, что на тестовой выборке статистические методы (метод безусловных средних, метод главных компонент, z-метод) обладают низкой точностью восстановления, а модель восстановления на основе нечеткой системы работает с высокой точностью, так как в ней снимается требования нормального распределения и однородности данных. Рассмотрим нечеткие системы.

Нечеткое моделирование включает в себя два основных этапа: идентификацию структуры и настройку параметров нечеткой модели. Идентификация структуры — это определение основных характеристик нечеткой модели (число нечетких правил, количество лингвистических термов для входных и выходных переменных). Настройка же параметров НС — это определение неизвестных параметров антецедентов (условная часть) и консеквентов (заключительной части) нечетких правил путем оптимизации работы нечеткой модели по заданному критерию.

Правила нечеткой модели типа синглтон имеют следующий вид:

правило i: ЕСЛИ x1 = А1i И x2 = А2i И … И xm = Аmi ТО y = ri ,

где Aji — лингвистический терм, которым оценивается переменная xj , а выход y оценивается действительным числом ri.

Модель осуществляет отображение , заменяя оператор нечеткой конъюнкции произведением, а оператор агрегации нечетких правил — сложением. Отображение F для модели типа синглтон определяется формулой:

где — значение i-го входа; — функция принадлежности лингвистического терма Aij; rj — значение консеквента в j-м правиле.

Нечеткая система может быть представлена как y = f(x, и), где и = ||и1,…, иN|| — вектор параметров, N = сумма термов по каждому исследуемому параметру, y — скалярный выход системы.

При n входных переменных, определённых на t термах с треугольными функциями принадлежности, описываемыми тройкой параметров в модели типа синглтон, вектор параметров будет выглядеть следующим образом:

где aij, cij, bij — параметры треугольной функции принадлежности формулы, i-й лингвистической переменной, j-го терма. Параметры, входящие в данный вектор, влияют на адекватность модели.

Задача параметрической идентификации — определить неизвестные параметры антецедентов и консеквентов нечетких правил путем оптимизации работы нечеткой системы по заданному критерию.

Параметрическая идентификация рассматривается как процесс оптимизации нечеткой модели, который сводится к нахождению таких параметров нечеткой системы, чтобы ошибка вывода была минимальной. При этом оценивается качество нечеткого вывода по значениям ошибки вывода, разницы между значениями выходной переменной из таблицы наблюдений f(x) и значениями F(x), полученными нечеткой системой. Исследуются три типа ошибки вывода:

1) среднеквадратичная ошибка (СКО): ;

2) средняя абсолютная ошибка (САО): ;

3) максимальная ошибка (МО): .

Для настройки параметров нечетких моделей используются две группы методов. Первая группа — классические методы оптимизации, основанные на производных (метод наименьших квадратов, градиентный метод, фильтр Калмана). Эти методы обладают высокой скоростью сходимости. Однако трудности применения классических методов оптимизации, связанные с проблемами локального экстремума и «проклятие размерности», заставляют обратиться ко второй группе методов. Метаэвристические алгоритмы (муравьиной колонии, роящихся частиц, имитации отжига, генетические алгоритмы (ГА), эволюционная стратегия (ЭС)) обладают грубой настройкой, которая требует больших временных ресурсов из-за итеративности вычислений. К тому же применение метаэвристик не гарантирует нахождения оптимального решения из-за прямой связи с эмпирической настройкой параметров используемых алгоритмов. Поэтому следует обратиться к объединению методов первой и второй группы.

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


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

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

Настройка нечетких моделей разработанным алгоритмом и аналогами для аппроксимации первой тестовой функции производилась по таблице наблюдений, состоящей из 400 строк. В табл. 1 представлены результаты работы нечеткой системы, основанной на эволюционной стратегии и методе наименьших квадратов (ЭС+МНК), и алгоритмов представленных в литературе.

Таблица 1 — Результат работы алгоритмов на первой тестовой функции

Алгоритм раздела входного пространства на несколько характерных областей (Rojas, Pomares, Ortega, Prieto)

Полезные статьи → Статистические методы анализа данных для решения практических задач (часть вторая)

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

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

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

Можно выделить два класса процедур анализа данных:

  • одномерные (дескриптивные) и
  • многомерные.

Многомерные типы анализа данных

Многомерный анализ данных позволяет одновременно исследовать взаимоотношения двух и более переменных и проверять гипотезы о причинных связях между ними.

Техники многомерного анализа разнообразны. Мы рассмотрим следующие:

  1. Факторный анализ
  2. Кластерный анализ

Факторный анализ

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

Применение факторного анализа преследует две цели:

  • сокращение числа переменных;
  • классификация данных.

Факторный анализ довольно полезен на практике. Приведем несколько примеров.

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

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

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

— надежность сделок (включающий такие параметры, как сохранность средств, возможность беспрепятственного их перевода);

— обслуживание клиентов (профессионализм сотрудников, их благожелательность) и

— качество обслуживания (точность выполнение операций, отсутствие ошибок) и др.

Кластерный анализ

Кластерный анализ (от англ. сluster – сгусток, пучок, гроздь) – это один из способов классификации объектов. Он позволяет рассматривать достаточно большой объем информации, сжимая его и делая компактными и наглядными.

Термин «кластерный анализ» был введен в 1939 году английским ученым Р. Трионом, предложившим соответствующий метод, который сводился к поиску групп с тесно коррелирующим признаком в каждой из них.

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

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

  1. формируем выборку и проводим опрос клиентов,
  2. определяем переменные (характеристики), по которым будем оценивать респондентов в выборке,
  3. вычисляем значения меры сходства и различия между ответами респондентов,
  4. выбираем метод кластеризации (т.е. правила объединения респондентов в группы),
  5. определяем оптимальное число кластеров (групп).

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

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

Кластерный анализ хорошо зарекомендовал себя, и на сегодняшний день применяется в различных прикладных областях:

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

Рассмотренные методики относятся к анализу данных, полученных в ходе проведения количественных исследований.

По вопросам расчета индексов:

Телефон: +7 (383) 203-49-99

Начало (часть первая) и продолжение (часть третья) статьи «Статистические методы анализа данных для решения практических задач».

Полезные статьи → Статистические методы анализа данных для решения практических задач (часть вторая)

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

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

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

Можно выделить два класса процедур анализа данных:

  • одномерные (дескриптивные) и
  • многомерные.

Многомерные типы анализа данных

Многомерный анализ данных позволяет одновременно исследовать взаимоотношения двух и более переменных и проверять гипотезы о причинных связях между ними.

Техники многомерного анализа разнообразны. Мы рассмотрим следующие:

  1. Факторный анализ
  2. Кластерный анализ

Факторный анализ

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

Применение факторного анализа преследует две цели:

  • сокращение числа переменных;
  • классификация данных.

Факторный анализ довольно полезен на практике. Приведем несколько примеров.

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

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

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

— надежность сделок (включающий такие параметры, как сохранность средств, возможность беспрепятственного их перевода);

— обслуживание клиентов (профессионализм сотрудников, их благожелательность) и

— качество обслуживания (точность выполнение операций, отсутствие ошибок) и др.

Кластерный анализ

Кластерный анализ (от англ. сluster – сгусток, пучок, гроздь) – это один из способов классификации объектов. Он позволяет рассматривать достаточно большой объем информации, сжимая его и делая компактными и наглядными.

Термин «кластерный анализ» был введен в 1939 году английским ученым Р. Трионом, предложившим соответствующий метод, который сводился к поиску групп с тесно коррелирующим признаком в каждой из них.

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

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

  1. формируем выборку и проводим опрос клиентов,
  2. определяем переменные (характеристики), по которым будем оценивать респондентов в выборке,
  3. вычисляем значения меры сходства и различия между ответами респондентов,
  4. выбираем метод кластеризации (т.е. правила объединения респондентов в группы),
  5. определяем оптимальное число кластеров (групп).

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

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

Кластерный анализ хорошо зарекомендовал себя, и на сегодняшний день применяется в различных прикладных областях:

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


Рассмотренные методики относятся к анализу данных, полученных в ходе проведения количественных исследований.

По вопросам расчета индексов:

Телефон: +7 (383) 203-49-99

Начало (часть первая) и продолжение (часть третья) статьи «Статистические методы анализа данных для решения практических задач».

«МОДЕЛИ И АЛГОРИТМЫ КЛАССИФИКАЦИИ СОСТОЯНИЙ БИОЦЕНОЗОВ НА ОСНОВЕ СТРУКТУРНЫХ СВОЙСТВ МНОГОМЕРНЫХ ДАННЫХ . »

Нижегородский государственный технический университет

им. Р.Е. Алексеева

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

ПОЖИДАЕВА Анастасия Сергеевна

МОДЕЛИ И АЛГОРИТМЫ КЛАССИФИКАЦИИ СОСТОЯНИЙ

БИОЦЕНОЗОВ НА ОСНОВЕ СТРУКТУРНЫХ СВОЙСТВ

МНОГОМЕРНЫХ ДАННЫХ

Специальность 05.13.01. – «Системный анализ, управление и обработка

информации (в наук

е и промышленности)» (технические науки)

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

Научный руководитель:

д.т.н., профессор Ломакина Л.С.

Нижний Новгород – 2015

СОДЕРЖАНИЕ

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ КЛАССИФИКАЦИИ

МНОГОМЕРНЫХ ДАННЫХ И ПОСТАНОВКА ЗАДАЧИ

1.1. Статистический метод классификации многомерных данных. 13

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

1.3. Метод классификации многомерных данных, основанный на нейронных технологиях

1.3.1. Искусственный нейрон

1.3.2. Многослойный персептрон

1.3.3. Нейронная сеть Ворда

1.3.4. Нейронная сеть Кохонена

1.4. Робастный метод классификации многомерных данных

1.4.1. Робастная регрессия

1.4.2. Знаковая регрессия

1.5 Необходимость разработки моделей и алгоритмов классификации состояний биоценозов на примере микробиоценоза желудочно-кишечного тракта человека

1.5.1. Дисбиоз желудочно-кишечного тракта

1.5.2. Характеристика микрофлоры кишечника людей различного возраста

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

1.6 Выводы и постановка задачи

ГЛАВА 2. МОДЕЛИ ПРЕДСТАВЛЕНИЯ МНОГОМЕРНЫХ ДАННЫХ.

2.1. Структурно-статистическая модель представления многомерных данных

2.2. Нечеткая модель представления многомерных данных

2.2.1. Функции принадлежности

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

2.3. Знаковая модель представления многомерных данных

ГЛАВА РАЗРАБОТКА АЛГОРИТМОВ КЛАССИФИКАЦИИ

3.1. Алгоритм классификации, основанный на структурно-статистической модели представления многомерных данных

ГЛАВА ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ

4.2. Экспериментальное исследование алгоритма классификации, основанного на нечеткой модели

4.3. Экспериментальное исследование алгоритма классификации, основанного на знаковой модели

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

4.5. Сравнительный анализ алгоритмов классификации

4.6. Описание программной реализации

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ВВЕДЕНИЕ

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

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

Большой вклад в решение проблемы классификации многомерных объектов, к которым относятся биоценозы, внесли как отечественные, так и зарубежные ученые: С.А. Айвазян, А.А. Большаков, Р.Н. Каримов, М. Дж. Кендалл, К. Танака, T. Kohonen и другие. Их работы широко используются как в научных исследованиях многомерных данных, так и в задачах прикладного характера. Тем не менее, остается много нерешенных проблем, связанных с внедрением информационных технологий в практику медицинского обслуживания и повышения его эффективности.

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

Цель работы. Разработка и исследование моделей представления многомерных данных и построенных на их основе алгоритмов классификации состояний биоценозов.

Задачи. Для достижения поставленной цели требуется решение следующих задач:

анализ научных публикаций по теме исследования;

разработка и исследование моделей представления многомерных данных;

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

программная реализация разработанных алгоритмов классификации;

применение полученных научных результатов на практике.

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

Научная новизна.

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

структурно-статистическая модель представления многомерных данных;

нечеткая модель представления многомерных данных;

знаковая модель представления многомерных данных.

2. Разработаны новые алгоритмы классификации состояний биоценозов, а именно:

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

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

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

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

Практическая значимость и внедрение. Практические результаты, полученные в ходе выполнения диссертационной работы, используются в лаборатории микробиома человека и средств его коррекции Федерального бюджетного учреждения науки Нижегородский научно-исследовательский институт эпидемиологии и микробиологии им. академика И.Н. Блохиной Роспотребнадзора и в учебном процессе при подготовке магистров по направлению «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. Р.Е.Алексеева, что подтверждается актами о внедрении. Получены свидетельства о государственной регистрации программы для ЭВМ №2013612601 от 6 марта 2013 г. и №2015611346 от 28 января 2015г.

Результаты работы использованы в госбюджетной НИР (Отчет по НИР «Диагностирование биологических объектов с использованием современных информационных технологий», Интернет-номер И131208225518 от 8.12.13 – Н.Новгород: НГТУ, выполненный в рамках НИОКР «Диагностические и информационно-поисковые системы» (Номер государственной регистрации Интернет-номер И111112195013, руководитель работы 01201252337, Ломакина Л.С.).

Публикация результатов. По теме диссертации опубликовано 15 работ, в том числе 3 работы в рецензируемых научных изданиях, рекомендуемых ВАК, 1 учебное пособие, 2 свидетельства о государственной регистрации программы для ЭВМ.

Международной молодежной конференции «Будущее технической науки» г. Н.Новгород, 2010 г., 2012 г., 2014 г.

Международных научно-технических конференциях «Информационные системы и технологии» г.Н. Новгород, 2011 г., 2012 г., 2013 г., 2014 г.


Нижегородской сессии молодых ученых (технические науки) г. Арзамас, 2012 г., 2013г.

XVIII-th International Open Science Conference “Modern informatization problems in simulation and social technologies”, Lorman, MS, USA, 2013y.

VI Всероссийской научно-технической конференции «Нейроинформатика — 2013», г. Москва, 2013 г.

XVII Международной научно-практической конференции «Системный анализ в проектировании и управлении», г. Санкт-Петербург, 2013г.

II Международной научной Интернет-конференции «Математическое и компьютерное моделирование в биологии и химии. Перспективы развития», г. Казань, 2013г.

На региональном конкурсе научных работ среди аспирантов в 2013 году автор стал лауреатом стипендии имени академика Г.А. Разуваева.

Личный вклад автора. Личный вклад автора заключается в следующем:

участие в постановке целей и задач исследования;

построение моделей представления многомерных данных;

разработка алгоритмов решения поставленных задач;

участие в программной реализации алгоритмов;

участие во внедрении созданного программного обеспечения.

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

1.1 Модели представления многомерных данных;

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

1.3 Алгоритмы классификации состояний биоценозов и их программная реализация;

1.4 Результаты экспериментальных исследований.

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

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

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

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

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

Приложение содержит:

Акт о внедрении результатов диссертационной работы в работу лаборатории микробиома человека и средств его коррекции ФБУН «Нижегородский научно-исследовательский институт эпидемиологии и микробиологии им. академика И.Н. Блохиной» Роспотребнадзора;

Свидетельства о государственной регистрации программы для ЭВМ и баз данных.

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ

КЛАССИФИКАЦИИ МНОГОМЕРНЫХ ДАННЫХ И

ПОСТАНОВКА ЗАДАЧИ

Классификация – это отнесение конкретного объекта, представленного значениями его признаков, к одному из фиксированного перечня классов по определенному решающему правилу в соответствии с поставленной целью [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]:

где d km – значение дискриминантной функции для m-того объекта в множестве k, xkmi – значение дискриминантной переменной xi для m-того объекта в множестве k, n – количество признаков. Коэффициенты i, i=1,…,n определяются таким образом, чтобы с помощью дискриминантных функций наилучшим образом, т.е. с наименьшим числом ошибочных решений, произвести разделение объектов на классы. Основной характеристикой различий между классами являются центроиды. Центроид k-го класса – это n-мерный вектор, координатами которого являются средние значения признаков k-го класса. Центроид класса выполняет функцию типичного объекта класса.

интерпретировать как координату в пространстве канонических дискриминантных функций. Для определения коэффициентов i, i = 1,…,n дискриминантной функции d km требуется решить систему из n уравнений с макасимальным числом нетривиальных решений q = n — 1.

которых можно непосредственно использовать vi, i = 1,…,n.

r Компоненты собственного вектора v следует нормировать для того, чтобы начало координат в пространстве канонических дискриминантных функций совпало с главным центроидом – вектором средних значений признаков всех объектов обучающего множества, [18]:

Коэффициенты в (1.2) получены по нестандартизированным исходным данным, поэтому они называются нестандартизированными. [19]. В теории дискриминантного анализа принято считать, что исходные данные приведены к стандартной форме, если векторы объектов имеют нулевое математическое ожидание и единичную дисперсию [12].

Разделяющая мощность j-ой дискриминантной функции тем выше, чем больше соответствующее ей собственное значение j [20].

Степень зависимости между классами и дискриминантной функцией

номер соответствующей дискриминантной функции. Максимальному относительному процентному содержанию не всегда соответствует большое значение коэффициента канонической корреляции, то есть у самой значимой функции может быть слабая связь с классами. Если классы плохо различимы по данным переменным, все коэффициенты корреляции будут иметь малые значения. Для выбора дискриминантных функций на практике s j и j используются совместно [12].

При использовании метода дискриминантного анализа существует ряд ограничений [21]:

требуется линейная независимость признаков;

ковариационные матрицы классов должны быть одинаковы;

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

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

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

Дискриминантный анализ позволяет решать задачи трех типов.

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

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

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

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

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

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

1.2. Возможность использования нечеткой логики для классификации многомерных данных Понятие нечетких множеств как обобщение обычных (четких) множеств было введено Л. Заде в 1965 г., что явилось толчком к новой математической теории [23-41]. Основная идея классификации заключается в использовании нечетких решающих правил и механизма нечеткого логического вывода [42Это означает, что решение о принадлежности параметра классу нельзя принимать по принципу «да/нет». Основой нечеткого подхода является функция принадлежности параметров определенному классу, принимающая значения в интервале [0,1] [46]. В теории нечетких множеств, кроме переменных цифрового типа, существуют так называемые лингвистические переменные. Системы нечеткой логики могут оперировать с неточной качественной информацией [47]. Это их свойство широко используется в различных областях, как, например, конструирование, контроль

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

Согласно этой теории элементы нечеткого множества А представляются характеристическими функциями на универсальном множестве Х. Элемент может полностью принадлежит множеству ( µ A ( x) = 1), не принадлежать

Конкретное значение функции принадлежности называется степенью или коэффициентом принадлежности к множеству А.

Степень принадлежности к множеству А может быть задана аналитически в виде функциональных зависимостей или числовых значений. [48].

Для нечетких множеств определены операции равенства, объединения, пересечения, дополнения, нечеткого включения, нечеткого бинарного отношения и т.д. [49, 50].

принимается условная вероятность наблюдения события А при наблюдении Х. При таком определении надо говорить о субъективности вероятности [53].

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

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

Задача существенно упрощается в том случае, если каждый признак рассматривать как носитель некоторой функции принадлежности, которая является частью более сложного «надежно работающего» нечеткого решающего правила. Тогда задачу синтеза «общего» решающего правила можно разбить на два этапа [48].

На первом этапе определяются частные функции принадлежностей µ A (1 ). µ A ( n ), которые соответствуют информативным признакам, и задаются их параметры.

На втором этапе частные функции принадлежности объединяются в нечеткие решающие правила, которые обеспечивают требуемое качество классификации.

К основным недостаткам нечетких систем можно отнести [59]:

отсутствует стандартная методика проектирования нечетких систем;

невозможно провести математический анализ нечетких систем существующими методами;

по сравнению с вероятностным подходом нечеткий подход не приводит к повышению точности вычислений;

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

Методы, основанные на нечеткой логике, применяются для решения многих задач медицинской диагностики: выбор схемы антибактериальной терапии, в стоматологии, психиатрии, фармакологии и т.д. [60-66, 45, 12].

1.3. Метод классификации многомерных данных, основанный на нейронных технологиях Методы классификации, основанные на аппарате искусственных нейронных сетей, используются с конца 50-х годов XX века. Вначале данные методы были реализованы простейшими системами типа персептрона [67, 68, 55], а в настоящее время для решения задач классификации используются более сложные архитектуры нейронных сетей, такие как многослойные персептроны, карты Кохонена, сети Ворда и т.п. [69].

Область применения систем, построенных на нейросетевых технологиях очень разнообразна [69,55]: распознавание образов, прогнозирование, аппроксимация непрерывных функций, сжатие данных, принятие решений и управление, кластеризация, классификация и т.п.


Далее будут рассмотрены несколько основных архитектур нейронных сетей, наиболее успешно применяемых для решения задачи классификации многомерных данных [70].

Простейшей классификатором на искусственных основе нейронных является одиночный нейрон, который преобразует входной вектор признаков в скалярный выход, зависящий от линейной комбинации входных переменных [71-74].

Скалярный выход нейрона можно использовать в качестве дискриминантной функции, а сам нейрон – в качестве линейного дискриминатора. В тривиальном случае, когда классы четко разделимы, линейный дискриминатор является лучшим нейросетевым методом классификации многомерных данных [70].

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

Такие архитектуры носят название многослойного персептрона [71, 73-75].

Такая предобработка носит название «обучение» нейронной сети.

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

сети, обучающиеся на примерах (обучение с учителем), и самообучающиеся сети (обучение без учителя).

При обучении с учителем для выделения конкретных объектов xi X различных классов K j используется априорная информация [76].

Процесс обучения заключается в том, что на входы искусственной нейронной сети многократно поступают последовательности вида (1.4). В результате формируется функция разделения F(x) (веса), которая определяет логику классификации [76].

Процесс обучения с учителем состоит из двух этапов. На первом этапе происходит непосредственное обучение в соответствии с вышеописанной схемой. На втором этапе осуществляется проверка качества обучения. На входы нейронной сети подается контрольная выборка объектов и оценивается ошибка классификации. Затем происходит корректировка обучения сети (настройка весов). Обучение проводится до тех пор, пока не будет достигнут желаемый уровень ошибки [77].

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

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

Задачей сетей подобной архитектуры является построение отображения набора входных векторов высокой размерности на карту кластеров меньшей размерности. Причем близким кластерам на карте в исходном пространстве должны отвечать близкие друг к другу входные векторы [70].

Карты Кохонена являются удобным инструментом для наглядного представления структуры данных в многомерном пространстве априорных данных.

Несмотря на широкий спектр возможностей нейронных технологий, они обладают рядом существенных недостатков [78]:

проектирования нейронных сетей большинство основано на эвристических подходах, что часто не дает однозначных решений;

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

существенные временные затраты на обучение не позволяют применять нейронные технологии в системах реального времени;

обучение сети может привести к тупиковым ситуациям;

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

при изменении обучающей выборки требуется проводить переобучение нейронной сети;

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

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

В медицинской диагностике нейронные технологии используется, например, для классификации опухолей молочной железы [79], для идентификации человеческих хромосом [80], при диагностике вирусного гепатита [81-84], заболеваний печени [85, 86] и желчного пузыря [87], в психиатрии [88].

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

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

наблюдения в выборке независимы;

случайные величины имеют одинаковые средние и постоянные дисперсии;

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

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

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

Термин «робастность» ввел в 1953 г. Дж. Бокс. Робастность означает нечувствительность к малым отклонениям от предположений, в частности закона распределения [89].

Устойчивой называют такую статистическую процедуру, на значение оценки которой не оказывают влияния малые изменения в основной выборке (то есть, большие изменения нескольких или малые изменения всех значений) [90].

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

Изучению робастных статистических методов посвящен ряд работ отечественных и зарубежных ученых [91-97].

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

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

Как говорилось выше, для использования робастных методов необходимо знать закон распределения остатков, к тому же, они неустойчивы к большим выбросам данных [19].

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

Достоинством знаковых методов [100, 101] является то, что они не зависят от распределения исходных данных. Это позволяет получать точечные и интервальные оценки параметров регрессии в тех случаях, когда закон распределения остатков неизвестен. Знаковая регрессия устойчива к распределениям остатков с «тяжелыми хвостами», также ее можно использовать в случае разнораспространенных остатков [19].

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

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

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

1.5.1. Дисбиоз желудочно-кишечного тракта

Согласно отраслевому стандарту «Протокол ведения больных.

Дисбактериоз кишечника», под дисбактериозом кишечника следует понимать клинико-лабораторный синдром, связанный с изменением качественного и/или количественного состава микрофлоры кишечника с последующим развитием метаболических и иммунологических нарушений с возможным развитием желудочно-кишечных расстройств [103].

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

Выделяют следующие возрастные группы людей [104]:

1 месяц- 11мес, 29 дней;

1 год – 6г, 11 мес, 29 дней;

7 лет – 17 лет 11 мес, 29 дней;

18 лет – 59 лет 11 мес, 29 дней;

60 лет и старше.

Экспериментальные группы здоровых и больных людей различных возрастных групп за были сформированы по следующим критериям включения «Здоровые» и «Больные».

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

Критерий «здоровые» был определен для каждой возрастной группы отдельно» [104].

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

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

Рис. 1.3а – Частота выделения представителей облигатной кишечной микрофлоры и УПМ из кишечника «здоровых» людей разных возрастных групп (по И.В. Соловьевой, 2013) Рис. 1.3б – Частота выделения представителей облигатной кишечной микрофлоры и УПМ из кишечника «больных» людей разных возрастных групп (по И.В. Соловьевой, 2013) 1.5.3. Выбор параметров оценки состояния биоценоза желудочнокишечного тракта человека На основании углублённого анализа литературных данных, использования опыта работы ФБУН ННИИЭМ им. академика И.Н.Блохиной Роспотребнадзора методом экспертных оценок был отобран ряд клинически значимых признаков, определяющих качественный и количественный состав микроорганизмов в субстрата, характеризующих состояние 1г микробиоценоза ЖКТ человека (таблица 1.1).

Родовой и видовой и состав микроорганизмов, учитывающихся при характеристике качественного и количественного состава микрофлоры ЖКТ человека (по Соловьевой И.В., 2013)

Количество E.coli лактозопозитивных Количество E.coli лактозодефективных со сниженной ферментативной активностью Количество E.coli лактозонегативных со сниженной ферментативной активностью Количество E.coli гемолитических (способность к гемолизу как

Признаки №1, 2, 3 — виды микроорганизмов, встречающиеся в норме у всех возрастных групп «здоровых» людей, представители резидентной микрофлоры кишечника человека.

Признак №4 – Fusobacterium spp., Peptococcus spp., Peptostreptococcus spp., Eubacterium spp., Clostridium spp. – значение и роль их в микробиоценозе неоднозначна. Одни авторы регламентируют их количество в норме, другие относят их к условно-патогенным микроорганизмам (УПМ).

Признак №5 – роль бактероидов до конца не выяснена, но установлено, что они принимают участие в пищеварении, расщепляют желчные кислоты, участвуют в процессе липидного обмена. Отмечено, что заселение кишечника бактероидами происходит после первого полугодия жизни ребенка. Среднее количество в микрофлоре – 1*108КОЕ/мл.

Признаки № 6, 7, 8, 9, 10 – в большинстве случаев представителем резидентной микрофлоры является Escherihia сoli. Но так как ее штаммы обладают различной ферментативной активностью и, соответственно, в разной степени влияют на бактерий – симбионтов и на физиологические процессы в толстой кишке, нам представляется важным подразделение на: лактозопозитивные, лактозодефективные, сoli Escherihia лактозонегативные и гемолитические. Также целесообразно учитывать и общее количество Escherihia сoli.

Признаки №11,12 — В 48% случаев у «здоровых» людей и в 28% — у «больных» — в составе микрофлоры ЖКТ обнаруживается Enterococcus spp.

Ряд авторов относит его к резидентной микрофлоре просвета кишечника.

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

Признаки №13,14 — важную роль в развитии патологических процессов у человека играет представители рода Staphylococcus: группа S.epidermidis spp.

и S.aureus. S.epidermidis spp. часто относят к представителям нормофлоры просвета кишечника, в случае если его выделяют в количествах не более 105 КОЕ/г. 105 в количествах КОЕ/г и более является S.aureus этиологическим фактором возникновения патологических процессов.

Признаки №15, 16, 17, 18, 19, 20, 21, 22 — представителей семейства Enterobacteriaceae относят к группе условно-патогенных микроорганизмов, в количестве более 105 КОЕ/г могут вызывать патологические процессы в организме человека, выступать как в роли этиологического фактора заболеваний, так и отягощать течение основного заболевания.

Признак 21 – редко встречающиеся виды семейства Enterobacteriaceae:

Budvicia spp., Buttiauxella spp., Cedecea spp., Edwardsiella spp., Ewingella spp., Kluyvera spp., Leclercia spp., Leminorella spp., Moellerella spp., Obesumbacterium spp., Plesiomonas spp., Pragia spp., Providencia spp., Rahnella spp., Raoultella spp., Tatumella spp., Yokenella spp.

Признак №23 — Pseudomonas aeruginosa хоть и входит в группу неферментирующих грамотрицательных микроорганизмов, но мы сочли необходимым выделить её в отдельный признак, так как она часть является возбудителем внутрибольничных инфекций.

Признак №24 – микроорганизмы, входящие в группу неферментирующих грамотрицательных микроорганизмов (НГОБ), могут быть транзиторными, но при иммунодефицитных состояниях макроорганизма могут выступать этиологическим фактором того или иного заболевания или отягощать течение основного заболевания.

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

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

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

Дисбактериоз кишечника» представлены унифицированные критерии оценки состояния микробиоценозов, большую роль при диагностике нарушений микрофлоры по-прежнему играет фактор субъективности.


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

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

Решению этой задачи посвящена данная диссертационная работа.

1.6 Выводы и постановка задачи

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

Статистический метод – метод дискриминантного анализа, Метод, основанный на применении нечеткой логики;

Метод, основанный на применении нейросетевых технологий;

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

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

К недостаткам нейросетевых технологий относятся следующие:

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

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

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

Статистические, нечеткие и нейросетевые методы применяются для решения задач классификации состояний биоценозов, в частности в задачах медицинской диагностики. Однако они обладают рядом ограничений и недостатков.

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

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

На основании всего вышесказанного сформулируем цель и задачи настоящей работы:

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

Для достижения поставленной цели требуется решение следующих задач:

1. разработка и исследование моделей представления многомерных данных;

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

3. программная реализация разработанных алгоритмов классификации;

4. применение полученных научных результатов на практике.

ГЛАВА 2. МОДЕЛИ ПРЕДСТАВЛЕНИЯ МНОГОМЕРНЫХ ДАННЫХ

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

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

2.1. Структурно-статистическая модель представления многомерных данных Задача классификации решается на основании модели, которая представляет собой совокупность контролируемых параметров, значение которых описывает состояние объекта. Выборка называется одномерной, если каждый принадлежащий ей объект имеет один признак. Если же каждый объект имеет несколько признаков, выборка является многомерной.

Если считать каждый признак многомерной выборки случайной величиной, то множество, которое описывает состояние многомерного объекта, можно r представить как n-мерный вектор. Решение задачи обработки многомерных данных, например, задачи классификации, можно упростить, если понизить размерность пространства признаков за счет того, что они, как правило, взаимосвязаны, а, значит, избыточны с точки зрения информации.

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

Дискриминантный анализ – это раздел многомерного статистического анализа, позволяющий изучать различия между множествами одновременно по нескольким переменным.

r Опишем состояние множества вектором =(1, 2,…, n) в n-мерном пространстве, где (1, 2,…, n) – координаты этого вектора, которые представляют собой значения наблюдаемых параметров. На их основе вырабатывается правило, позволяющее классифицировать объекты.

По единственному состоянию системы обнаружить её структурные свойства невозможно, так как зависимость отражает характер совместного изменения значений компонент. Классифицировать объект можно, только обладая информацией о множестве состояний, каждое из которых представляет собой точку в n-мерном пространстве. Все множество многомерных состояний (многомерные данные) образует скопление точек – «облако», которое может описывать состояние одного объекта в разные моменты времени или состояния разнообразных объектов одного вида. Если группы наблюдаемых объектов различны, они образуют соответствующие им «облака» в некоторых областях пространства, характеристикой положения которых являются средние значения многомерной случайной величины в каждой группе — центроиды. Вероятность перекрывания групп зависит от того, насколько близко скопление точек к соответствующему центроиду.

С целью классификации в работе используется дискриминантный анализ.

Подробно метод дискриминантного анализа рассмотрен в разделе 1.1.

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

Метод перебора конъюнкций в проблеме структурного анализа многомерных данных (на примере решения медицинских задач)

МЕТОД ПЕРЕБОРА КОНЪЮНКЦИЙ

В ПРОБЛЕМЕ СТРУКТУРНОГО АНАЛИЗА МНОГОМЕРНЫХ ДАННЫХ

(НА ПРИМЕРЕ РЕШЕНИЯ МЕДИЦИНСКИХ ЗАДАЧ)1

Рассматривается метод перебора конъюнкций (МПК) в проблеме анализа структуры данных. Формулируется постановка задачи выявления логических связей в заданных группах объектов на заданном множестве признаков. Описан алгоритм (ALOST), реализующий решение задачи. Приведены результаты использования алгоритма на реальных медицинских данных.

В настоящее время в арсенале методов анализа данных широко используются различные программные продукты: статистические пакеты, нейросети, так называемые эволюционные методы, алгоритмы поиска логических закономерностей и др. [Дюк, 2001]. Такие компьютерные разработки представляют собой «инструмент» для анализа данных. Основная их задача – обеспечить корректность анализа, учитывая особенности медицинских данных (многообразие проявления заболевания, наличие большого количества пропущенных данных, их зашумленность и т. д.).

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

В настоящей работе рассматривается один из методов структурного анализа данных, основанный на методе перебора конъюнкций (МПК).

Рассмотрим некоторую упрощенную, но реальную клиническую ситуацию, на примере которой можно будет продемонстрировать необходимость исследования логических связей признаков в различных группах пациентов. (Признаки – перечень свойств, общих для всех объектов в группе исследования. Объект может принимать одно (или несколько) значений из предусмотренных для каждого признака. Каждое значение признака принято называть симптомом.)

Пусть имеется две группы больных с одним и тем же установленным диагнозом, состоящие из N1 и N2 объектов соответственно. Больным в первой группе (N1) назначался метод лечения T1, а в другой (N2) — метод T2. Требуется дать оценку эффективности каждого из этих методов лечения для данной категории больных.

Что понимать под эффективностью лечения — процент ли выздоровевших, доля ли больных, у которых наступило улучшение, пяти-, десятилетнюю выживаемость, или какой-либо другой критерий «хорошего исхода», в данном случае, не столь уж важно. Желательно только, чтобы оценка эффективности была, по возможности, объективной.

После введения критерия «хорошего исхода» группы больных разделяются на тех, для которых метод T1 хорош (Т1+), и на тех, для которых он плох (Т1-); и аналогично метод лечения T2 – для некоторых больных хорош (Т2+), а для некоторых – плох (Т2-). На рис.1 представлена схема возможного распределения состава групп больных и их количеств в группах, получивших сравниваемые методы лечения.

лечение Т1 или Т2)

Т1+ Т1+ Т2+ Т1- Т2- Т2+ Т1+ Т2+ Т1- Т2- Т1- Т2- Т2+ Т1+ Т2+ Т1- Т2- Т2- Т1- Т2- Т1- Т1- Т2- Т1- Т1- Т1- Т1- Т1+ Т2+

Т2+ Т1+ Т2+ Т1- Т2+ Т2+ Т1+ Т2+ Т1- Т1

(после введения критерия фективности)

Групп по эффект-ти

Рис. 1. Распределение объектов по группам сравнения

D – объединенный состав больных , т. е. получивших один из методов лечения (Т1 или Т2) и имеющих либо хороший исход (DТ1+ или DТ2+), либо плохой (DТ1- или DТ2-);

DТ1 – состав больных, получивших Т1;

DТ2 – состав больных, получивших Т2;

DТ1+ – состав больных из группы Т1, имеющих «хороший исход»;

DТ1- – состав больных из группы Т1, имеющих «плохой исход»;

DТ2+ – состав больных, из группы Т2, имеющих «хороший исход»;

DТ2- – состав больных из группы Т2, имеющих «плохой исход»;

N — общее количество больных, участвующих в исследовании,

т. е., N = NТ1 + NТ2;

NТ1 – количество больных, получивших метод лечения Т1;

NТ2 – количество больных, получивших метод лечения Т2;

NТ1+ — количество больных в группе DТ1+ ;

NТ1- — количество больных в группе DТ1-;

NТ2+ — количество больных в группе DТ2+ ;

NТ2- — количество больных в группе DТ1- .

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

Важно выяснить также существуют ли закономерности, общие для хорошего (или плохого) исходов и при T1, и при T2. В этом случае, обнаруженные закономерности могут определить хороший и плохой прогноз вне зависимости от выбранного метода лечения. Выделение таких групп очень важная задача, так как очевидно, что оценивать эффективность применения какого-либо метода лечения (или препарата) в группе с плохим прогнозом нельзя по тем же критериям, что и в группе с хорошим прогнозом. Так, в рассматриваемом примере представляет интерес рассмотреть и сопоставить связи признаков (симптомов) в следующих парах групп: (DТ1+ Ụ DТ2+) и (DТ1- Ụ DТ2-); (DТ1+) и (DТ1- ); (DТ2+) и (DТ2-); а также (DТ1) и (DТ2).

Если обнаружатся сочетания симптомов, характерные для больных с плохим исходом (DТ1- Ụ DТ2-), отличные от группы с хорошим исходом (DТ1+ Ụ DТ2+), то тем самым, могут определиться факторы плохого прогноза, вне зависимости от предлагаемых методов лечения. Если удастся выявить закономерности, различающие гр. (DТ1+) и гр. (DТ1-), то можно будет сформулировать показания и противопоказания к применению метода T1. Аналогично, при сравнении гр. (DТ2+) и гр. (DТ2-), выявленные устойчивые связи симптомов позволят ориентироваться в показаниях и противопоказаниях к использованию метода T2. Сопоставление частоты (или доли) выявленных сочетаний симптомов в группах (DТ1) или (DТ2), позволят сделать суждение о распространенности обнаруженных связей, иными словами, о границах их применимости.

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

Рассматриваемый пример является типичным в круге задач, стоящих перед врачом-исследователем, особенно в проблеме выбора наиболее эффективной тактики лечения кон­кретного больного. Следует заметить, что аналогичные задачи в практике проведения предварительных исследований возникают достаточно часто и в других областях [например, Губерман, 1987].

2. Алгоритм структурного анализа данных

Целью разработки предлагаемого подхода явилась необходимость обеспечить иссле­дователя информацией о распределении сочетаний симптомов в конкрет­ных, заданных им группах объектов. Особенность этого круга задач состоит в том, что пользователю (врачу-исследователю) должна быть предоставлена возможность задавать для исследования произвольные, возможно даже, пересекающиеся группы, (в отличие от классов для диагностики, где классы должны быть строго непересекающимися).

2.1. Метод перебора конъюнкций в структурном анализе данных. Естественно было предположить, что искомые связи (закономерности) в группах следует искать в виде различных логических функций симптомов исходного описания, и в первую очередь, в виде конъюнкций этих симптомов. Такой подход, предложенный в 1964 г. [Бонгард, 1967], получил название «метод перебора конъюнкций» (МПК). В публикациях [Карп, 2005, Чернавский и др., 2004] подробно описаны процедуры перебора конъюнкций и принципы их отбора в решающие правила диагностики. МПК хорошо зарекомендовал себя в построении различных диагностических алгоритмов (и в медицинских, и в не медицинских задачах). Основные преимущества МПК состоят в том, что при его использовании отпадает необходимость задания всех координат объектов, что позволяет использовать объекты с неполной информацией; обнаруженные закономерности сформированы в виде конъюнкций (из симптомов, предложенных самим врачом-исследователем), которые легко интерпретируются, что существенно при содержательном анализе выявленных закономерностей.

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

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

2.2. Задание групп объектов. В ALOST каждая группа может быть задана либо перечислением объектов, либо логическим условием, которому должны удовлетворять все входящие в нее объекты. В общем случае, группа задается именем и «маской». Маска группы – логическая функция компонент. Компоненты задаются: перечислением номеров объектов или симптомов; интервалом номеров объектов или симптомов. Каждой группе присваиваются «имена», отражающие, по возможности, их смысловое содержание. Если какая-либо группа (Gi) уже сформирована, то предусмотрен также вариант задать новую группу, например (Gj), так: «все, которые не вошли в данную группу (Gi)» или «все, которые попали одновременно и в группу с именем Gj, и в группу с именем Gk», и т. д.

2.3. Задание симптомов для перебора. Все симптомы исходного описания перенумерованы от 1 до Y. В таблице 1 приведен фрагмент описания больных острым инфарктом миокарда (ОИМ) для решения задачи сравнительной оценки эффективности применения различных лекарственных средств (Т1 и Т2) к этой категории больных.

Фрагмент карты описания больных острым инфарктом миокарда

Илон Маск рекомендует:  Что такое код log10
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL