Исследование метода декомпозиционного дерева и его модификация для смешанных типов данных Нгуен Нгок Хуи

Введение к работе

Актуальность темы исследования. В настоящее время существует значительное число подходов и методов кластеризации/классификации, ориентированных на различные типы данных. Особого внимания заслуживает случай, когда признаки, характеризующие объекты заданного множества, являются разнородными. Например, в задаче медицинской диагностики, которая может быть поставлена как задача классификации, векторная оценка, характеризующая состояние пациента, может содержать компоненты, относящиеся к следующим типам данных: количественный, интервальный, лингвистический, булевский и др. В рамках data mining (L. Billard, E. Diday, V. Ganti, F. Hoppner, M.S. Yang и др.) предложены специальные функции расстояния для неколичественных типов данных, позволяющие оценить «схожесть» объектов. Однако для приближенной информации в виде нечетких чисел можно использовать альтернативные подходы, основанные на индексах сравнения. В качестве базового метода для кластеризации объектов, характеризуемых разнородными признаками, выбран «метод определения транзитивно-ближайших подмножеств», который в рамках данной работы называется методом декомпозиционного дерева. Его преимущество заключается в том, что он позволяет получить всю совокупность возможных группировок объектов заданного множества. В работах Каплиевой Н.А., Леденевой Т.М. предложена модификация данного метода, что позволяет говорить о схеме метода и возможных его реализациях, которые связаны со способами задания исходной информации и выбором типа транзитивности. Исследована зависимость результатов нечеткой кластеризации от функции расстояния и типа транзитивности. Актуальность диссертационной работы обусловлена недостаточной изученностью ряда вопросов, связанных с некоторыми другими (параметрическими) типами транзитивности, а также возможностью использования иных вариантов формирования исходной информации в виде отношения сходства/несходства. Кроме того, отсутствуют подходы к сравнению декомпозиционных деревьев.

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

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

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

2. Разработка подходов к сравнению декомпозиционных деревьев.

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

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

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

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

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

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

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

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

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

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

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

   Степень достоверности и апробация работы. Теоретические выводы, приведенные в диссертации, обоснованы корректным использованием математического аппарата, подтверждены вычислительным экспериментом, который проводился с использованием разработанного программного комплекса. Научные результаты докладывались и обсуждались на научных конференциях профессорско-преподавательского состава, аспирантов и студентов Воронежского государственного университета, на Международных конференциях «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 2010, 2011, 2012 гг.)

   Публикации. Основные результаты диссертации опубликованы в 7 научных работах, в том числе 4 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, лично соискателю принадлежит: в [1] - теоретический анализ и выводы относительно влияния типа транзитивности на структуру дерева; частично структурные и количественные характеристики декомпозиционного дерева; в [2, 4] - вывод формул и проведение экспериментальных расчетов; в [3, 7] - проведение вычислительного эксперимента и его анализ для смешанных типов данных; в [6] - вариант корректирующей процедуры для отношения сходства.

   Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Основная часть работы изложена на 131 страницах текста и содержит 51 рисунков и 13 таблиц. В Приложение вынесены результаты вычислительного эксперимента.

   Похожие диссертации на Исследование метода декомпозиционного дерева и его модификация для смешанных типов данных

   

   Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типаПолуян, Анна Юрьевна

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

   

   Метаматематические исследования правдоподобных рассуждений типа ДСМВиноградов Дмитрий Вячеславович

   

   Теория LP-структур для построения и исследования моделей знаний продукционного типаМахортов, Сергей Дмитриевич

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

   Исследование и разработка системы диалогового схемтехнического проектирования для ЭВМ типа СМ-1700Тимаев, Андрей Александрович

   

   Разработка и исследование схем детерминированного поиска на основе сортировки с приложением к идентификации оцифрованных объектов различных типовБелоконова Светлана Сергеевна

   

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

   

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

   

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