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

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

НГУЕН НГОКХУИ

ИССЛЕДОВАНИЕ МЕТОДА ДЕКОМПОЗИЦИОННОГО ДЕРЕВА И ЕГО МОДИФИКАЦИЯ ДЛЯ СМЕШАННЫХ ТИПОВ ДАННЫХ

Специальность 05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 6 МАЙ т

Воронеж - 2013

005058321

Работа выполнена в ФГБОУ ВПО «Воронежский государственный университет»

Научный руководитель Леденева Татьяна Михайловна,

доктор технических наук, профессор, ФГБОУ ВПО «Воронежский государственный университет», заведующий кафедрой вычислительной математики и прикладных информационных технологий

Официальные оппоненты: Буховец Алексей Георгиевич,

доктор технических наук, профессор, ФГБОУ ВПО «Воронежский аграрный государственный университет им. императора Петра I», профессор кафедры прикладной математики и применения математических методов в экономике;

Попова Ольга Борисовна, доктор технических наук, профессор, ФГБОУ ВПО «Воронежский государственный университет инженерных технологий», профессор кафедры информационных технологий моделирования и управления

Ведущая организация: ФГБОУ ВПО «Тамбовский государственный

технический университет»

Защита состоится «£Х» МОЙ/ 2013 г. в 45.00 в аудитории 226 на заседании диссертационного совета Д.212.03 8.24 ФГБОУ ВПО «Воронежский государственный университет» по адресу: 394006, г. Воронеж, Университетская пл., 1.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Воронежский государственный университет».

Автореферат разослан « ? » Ол1р,Ы^2013 г.

Ученый секретарь

диссертационного совета Д.212.037.02

Чеботарев А.С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

4. Разработка программного комплекса, реализующего метод

1 Кофман А. Введение в теорию нечетких множеств / А. Кофман. - М. : Наука, 1986. - 320 с.

декомпозиционного дерева, проведение вычислительного эксперимента и его анализ.

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

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

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

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

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

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

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

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

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

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

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Рисунок 1. Схема метода декомпозиционного дерева

Пусть R,,R2 е F(X у.Х) - нечеткие бинарные отношения, заданные на множестве X; fxRi {х,у), fiR, (х,у) - их функции принадлежности.

(max— t) -композицией нечетких отношений R, и R} называется t

нечеткое отношение R,°R2 с функцией принадлежности

ц , (x,y) = maxtUR (x,z),nRXz,y)\,

где t —>[0,7] - треугольная норма, которая определяет пересечение

нечетких множеств.

Нечеткое бинарное отношение R обладает свойством {max— /)-t

транзитивности, если R°RczR. Если отношение не является транзитивным, то с помощью транзитивного замыкания его можно обеспечить таким свойством.

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

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

Таблица 1

Название (-норм 1.1 Функция принадлежности

Логическая

Алгебраическая /и«,ЛО= ^ (Х'У)

Ограниченная ^,А^яЛх-У) = тах{^к, + {х-}')-'-0)

Относительная /'-,.(*,.*,) (*-У) /ч (Х.у) + Мк! (х.у)-мК1 (х.у)Мк! (х,У)

Драстическая Ми,(Х-У)•если Ми,(х,у) = 1, И Я, (х-у)'есл" Си, (х-У) = 0,иначе

/ -параметрическая X е{0,]) Р,Л*,я!)(х-У) = тах{Ч1-Х){р*1 (х'У) + Ря, {х,у)-1) + кху)

у-параметрическая у>0

Во второй главе представлены результаты исследования метода декомпозиционного дерева. Особое внимание в диссертации было уделено параметрическим типам транзитивности, которые порождаются, в частности, Я-параметрической и /-параметрической нормами. Исследовалось влияние параметров на вид декомпозиционного дерева.

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

Декомпозиционное дерево Т представляет собой иерархическую структуру, каждый ярус которой содержит разбиение объектов заданного множества. Ярусы будем считать одинаковыми, если они соответствуют одному и то же разбиению. Количество ярусов определяется количеством значений уровня а0<а1<...<ап, при этом ярус уровня и„ называется корнем

декомпозиционного дерева.

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

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

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

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

Доказано следующее утверждение: если для нечеткого отношения подобия Я^Ртгу^Х2} существует обычное отношение эквивалентности

Л сX2, такое, что ЛсЛ, то невозможно получить тривиальное разбиение Я, иначе тривиальное разбиение существует.

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

а) существует единственная вершина г, называемая корнем растущего дерева, у которой сГ(г)< 1 и г/~(г)> 1;

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

Верхней вершиной растущего дерева б назовем вершину, которая соответствует минимальному значению уровня, формирующего тривиальное разбиение. Соответствующие значения уровней будем называть уровнем корня аг растущего дерева и уровнем вершины «Л. Промежуток 2аа = [«г,а5] можно рассматривать как зону роста декомпозиционного дерева, которая содержит последовательные значения уровней, таких, что при переходе от уровня к уровню формируются ярусы с новыми классами объектов. Величину 1г = а5 - аг будем называть высотой растущего дерева.

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

Появление циклов в основании декомпозиционного дерева свидетельствует о том, что на некотором ярусе появляются вершины х с <1*(х)> /, т.е. происходит объединение появившихся ранее классов. Соответствующие им значения уровней будем называть критическими. Минимальное а и максимальное а значения уровней, которым соответствуют ярусы, содержащие вершины с с!*[х)>1, назовем соответственно нижней и верхней границами зоны неустойчивой классификации Z = [a,a]. В рамках проведенного исследования оказалось, что зона неустойчивой классификации появляется не всегда.

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

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

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

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

3. Пусть NumKl^^a) - количество классов, содержащихся на ярусе, который соответствует уровню а, при использовании t -нормы данного типа type £ {лог, алг, огр, др}. Зафиксируем некоторое значение а е (0,0.5], тогда

NumKlorp (а ) > NumKlav (а*) > NumKI0,„„ (а)> ЫитК1юг («*).

При ае(0.5,/] все типы /-нормы дают одно и тоже максимальное число классов. Данный вывод позволяет при заданном значении индекса чувствительности а подобрать приемлемое количество классов или варьировать это количество за счет выбора / -нормы.

4. В случае у -параметрической t -нормы высота растущего дерева для всех значений параметров одинаковая, причем аг=0.5 и as=0.5.

5. Пусть у, - некоторое значение параметра у-параметрической t-нормы и Ra (у,) - разбиение, соответствующее уровню а, тогда если такое же разбиение существует для значения параметра у2 > у, и соответствующее ему значение уровня есть а , тогда а <а. Это означает, что с возрастанием параметра у для «распознавания» такого же разбиения будет достаточно меньшее значение индекса чувствительности.

6. Вес и>(х) объекта х - это минимальное значение уровня а, при котором объект х образует тривиальный класс. Тогда с возрастанием параметра у -параметрической нормы вес фиксированного объекта не возрастает. Это означает, что при увеличении параметра у возрастают шансы получения тривиального класса, образованного данным объектом. И, таким образом, параметр у можно интерпретировать как «силу удара», который влечет за собой разбиение множества объектов на отдельные классы. С ростом у уже для малых значений уровней возможно формирование тривиальных классов, причем количество классов на нижних ярусах декомпозиционного дерева очень резко возрастает.

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

Пусть х,y,zeX, S - отношение сходства на множестве X. Будем говорить, что объекты х и у неразличимы относительно объекта z, если max{S(x,z),S(y,z)}<S(x,y), т.е. степень сходства между объектами х и у превышает степени сходства этих объектов с объектом z.

Чем больше объектов из множества X согласуются со степенью сходства Б(х,у), тем в больше степени объекты х и у неразличимы. Если объекты х и у неразличимы по отношению к малой части объектов из множества X, то, следовательно, относительно другой (большей) части они ведут себя разнообразно, что обусловливает необходимость корректировки отношения . В диссертации разработана корректирующей процедура (рис. 2), основанная на количественной оценке «соседей» каждого из объектов.

Рисунок 2. - Схема корректирующей процедуры 10

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

Пусть F(U) - семейство нечетких подмножеств универсального

множества U, A,,A2sF(U) - нечеткие множества, тогда функция подобия задается формулой

S(A

v" 2> \A,va:\ щ+кнл^Г

где \А\ - мощность соответствующего нечеткого множества.

Для треугольных и трапециевидных нечетких чисел определены функции подобия с учетом их расположения на прямой. Пусть Т, ={a1,d,,e],b1) и Т2 = (a2,d2,e2,b2) нечеткие трапециевидные числа, функция принадлежности которых определяется следующим образом (индексы опущены):

Ix~a ^ ^j b-x

-, если а < х< а, -, если с <х<Ь,

d-a b-e

1, если d < х < е, 0, иначе.

В работе рассмотрены все возможные случаи взаимного расположения нечетких чисел на числовой прямой, и для каждого случая построена функция подобия (табл. 2, здесь w0 = b - а, w, = e-d).

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

Известно, что часто используемые в приложениях расстояния Хемминга и Евклида позволяют осуществлять разбиение на классы при значениях а >0.5 для всех типов /-норм. Это означает, что для растущих декомпозиционных деревьев в этом случае для уровня корня имеет место аг>0.5. При использовании функции подобия декомпозиционное дерево растет практически от нулевых значений уровня, при этом для уровня вершины справедливо as=0.5 для всех типов t -норм. Использование функции подобия позволяет уже при малых значениях индекса чувствительности осуществить классификацию объектов. Это означает, что функция подобия позволяет улучшить «распознающие» свойства [max- min) -композиции. Это отражается в том, что зона роста декомпозиционного дерева во всех примерах значительно больше для функции подобия, чем в декомпозиционных деревьях, полученных с использованием функций расстояния.

Таблица 2

№ Условия для параметров Функция подобия

I а, < а2 < Ь2 < , с/1<с/2<е1< е, ¿>, - а, + е, - с/,

11 а,<а2<£2<Ь„ ах<с12<ех<е2 л= ^ /, =е, ~(12,12 = Ь1-а2,1}=(Ь2-Ь^-И г(ТТ) (/.+/2+/з) (ИЬ+ИО-(/,+/2Н)

III а, < а2 < Ьг < 6,, с/, < е, < с12 < е2 А- /I, К+,Ч)-(/1+/2)

IV а, <а2 <6, <Ъ2, с/, < с/2 < е2 < е] /Л, у'^-ьуи {Ь1-ег)-{.Ьх-ех) V 2>у0+/

V а, <а2 <£, <Ь2, с1х < с/, < е, < е2 е2 — а, + Ь2 —

VI а, <а2 <6, ^—, - А!" Ъ,-ех+Ъ2-е2 / V А — °2

VII а2 — а1 <Ъ2, < ¿/2 < е2 < е, А - д Ь2-6, ' (А-^Нй,-^)'"2 (^МА-е,)

XIII <>(?;,г2) = о

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

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

где t{i),t(j) - лингвистические оценки объектов х, и Xj соответственно, представленные термами лингвистической шкалы с функциями принадлежности Мф)(и) н /',(,)(")' Р - настраиваемый параметр.

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

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

где п ,п п - количество числовых, нечетких и лингвистических

кол ' неч, линз 7

компонент; SK01{xj,xJ),Slle4[xi,xj),Sml,^xi,xJ) - нормированные расстояния между соответствующими разнородными компонентами векторных оценок объектов xt и Xj, ; п - общее количество компонент.

В четвертой главе описывается разработанный программный комплекс «FuzzyCluster», структура которого включает следующие основные модули: модуль доступа к базе данных, модуль формирования различных типов матриц и модуль построения декомпозиционного дерева (рис. 4). Приложение реализовано в стиле обычного мастера и содержит самостоятельный Navigation Framework, предоставляющий удобную архитектуру для навигации пользователя между шагами приложения. В диссертации разработана процедура для тестирования основных модулей. Программа использовалась для классификации компьютеров, предлагаемых интернет-магазином с целью формирования предложений для различных сегментов клиентской базы. Для выбранных моделей системных блоков были выбраны характеристики, предполагающие количественные, лингвистические и нечеткие оценки. В рамках исследования были получены различные варианты кластеров. На рис. 5 представлены декомпозиционные деревья, соответствующие различным параметрам.

Механизм доступа к базе данных

Сериал изация/д ее ериализация данных

Интерфейс доступа к данным

Проверка целостности данных

Рисунок 3. - Структура программного комплекса «РиггуС^ег»

МОДУЛЬ Доступ к базе данных

«(1) [ J__Ь 1 1 V _.[._ ..1 ! М<1| [7

ПИИ 10 1 5 II 9Ц7М) , | г | з | 1 4 1 I • II 7 I . I > I

\ ч/

1 < [> II 3 II< 151 II ' 1 • 1 » 1 >{№««) | 1 | 2 | 3 ! 4 1 I « I 7 | . | , |

\/ 4 1 1

7(0666) 1 ' 1 * И 1« « II ' • 1 • 1 Ц9ЯЖ) 1 1 1 2 1 3 ! 4 1 1 « 1 ' 1 » 1 > 1

С (Я (53) 1 - 1 - 1 > 1« 5 1 II ' ■ ы Б(*Б5Э) | 1 | 2 | 3 1 4 1 | • | 7 | . | , |

т \

5(1649) И 1 * 1 з 1« 5 | II ' ■ ы 5 (0 Б49> | 1 | 2 | 3 1 4 1 I . I » I ■ 1 » 1

1

А (»673) 1 . 1 * 1 3 1«1 5 | II ' , \ , 1 | 1 | 2 | 3 ! 4 1 I . I 7 I . I » I

зр.яц 1 • 1 * 1 3 4 * 1 1 ' 1 • 1' 1 ](К.ЯЯ) ] 1 | 2 | 3 | 4 | I . I 7 I . I . I

2 (В 552) 1.1*13 ! « * 1 ' 1 > 1 9 | 2(1557) | 1 | 2 | 3 1 4 1 | • | 7 | . | , |

1

1(0) 1 . 1 > 1 3 1 * 5 1 1 ' 1 . 1,1 Щ | 1 | 2 | 3 1 4 1 I . I . I . I . I

а) б)

Рисунок 4. - Декомпозиционные деревья с разными коэффициентами чувствительности: а)-0.05, б)-0.17

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

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

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

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

(7

у

i }

Список публикаций но теме диссертации

Публикации в изданиях, рекомендованных ВАК РФ

1. Нгуен H. X. О влиянии функции подобия на результаты нечеткой классификации / H. X. Нгуен, Т. М. Леденева // Информационные технологии: научно-технический журнал. - М.: Новые технологии, 2011. -№ 11. - С. 15-23.

2. Нгуен H. X. О вычисление функции подобия для нечетких чисел / H. X. Нгуен, Т. М. Леденева // Научно-теоретический журнал. — Белгород: Вестник БГТУ им. В.Г. Шухова, 2011. -№ 4. - С. 177-182.

3. Нгуен H. X. Алгоритм нечеткой классификации для объектов с оценками в лингвистической шкале / H. X. Нгуен, Т. М. Леденева, К.С. Погосян // Системы управления и информационные технологии. - Москва-Воронеж: Изд-во «Научная книга», 2012. -№ 3(49). - С. 20-23.

4. Нгуен H. X. О представлении информации в задачах классификации / Т.М. Леденева, H. X. Нгуен // Вестник Воронежского государственного технического университета. - Воронеж : 2012 -Т.8, № 7.1 - С. 33-38.

Статьи и материалы конференций

5. Нгуен H. X. О мерах подобия нечетких чисел / H. X. Нгуен // Сб. трудов Междунар. конф. «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 20-22 сентября 2010 г.). - Воронеж : Издательско-полиграфический центр Воронежского государственного университета, 2011. - С. 252-255.

6. Нгуен H. X. Об собственностях формирования корректирующей процедуры при переходе от отношения сходства к отношению подобия / Н.Х. Нгуен, Т.М. Леденева // Сб. трудов Междунар. конф. «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 26-28 сентября

2011 г.). — Воронеж : Издательско-полиграфический центр Воронежского государственного университета, 2011. - С. 242-246.

7. Нгуен H. X. О мерах несходства для смешанных типов данных/ Т.М. Леденева, Н.Х. Нгуен // Сб. трудов Междунар. конф. «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 26-28 ноября

2012 г.), Часть 2. - Воронеж : Издательско-полиграфический центр Воронежского государственного университета, 2012.-С. 180-185.

Подписано в печать 15-04.13. Формат 60 - 84 Усл. псч. л. 0,93. Тираж 100 экз. Заказ 375.

0| печатано с готового оригинал-макета в типо1рафнн Пздатсльско-полшрафического ценфа Воронежскою государственного университета. 394000, Воронеж, ул. Пушкинская, 3

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"

(ФГБОУ ВПО «ВГУ»)

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

НГУЕН НГОК ХУИ

ИССЛЕДОВАНИЕ МЕТОДА ДЕКОМПОЗИЦИОННОГО ДЕРЕВА И ЕГО МОДИФИКАЦИЯ ДЛЯ СМЕШАННЫХ ТИПОВ ДАННЫХ

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.17 - Теоретические основы информатики

Научный руководитель доктор технических наук, профессор Леденева Т. М.

ВОРОНЕЖ 2013 г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ....................................................................................4

Глава 1. АНАЛИЗ ПОДХОДОВ К РЕШЕНИЮ ЗАДАЧИ

КЛАСТЕРИЗАЦИИ..............................................................8

1.1. Постановка задачи кластеризации....................................................8

1.2. Сравнительный анализ подходов к решению задачи кластеризации......14

1.3. Основные понятия нечеткого подхода к кластеризации.....................24

1.4. Цель и задачи исследования........................................................36

Глава 2. НЕЧЕТКАЯ КЛАССИФИКАЦИЯ: ИССЛЕДОВАНИЕ

МЕТОДА ДЕКОМПОЗИЦИОННОГО ДЕРЕВА....................37

2.1. Влияние типа транзитивности на результаты нечеткой классификации..........................................................................37

2.2. Система показателей для сравнения результатов нечеткой классификации.........................................................................48

2.3. Формирование корректирующей процедуры при переходе от отношения сходства к отношению подобия....................................................57

Выводы по второй главе...................................................................63

Глава 3. НЕЧЕТКАЯ КЛАСТЕРИЗАЦИЯ ДЛЯ РАЗНОРОДНЫХ

ТИПОВ ДАННЫХ.............................................................65

3.1. Основные типы данных...............................................................65

3.2. Вычисление функции подобия для нечетких чисел...........................68

3.3. О мерах несходства для разнородных данных...................................79

3.4. Задача кластеризации для объектов с оценками в лингвистической шкале.....................................................................................84

Выводы по третьей главе..................................................................92

Глава 4. ОПИСАНИЕ ПРОГРАММНОГО КОМПЛЕКСА «COMPOUND

FUZZY DISTANCE»..........................................................94

4.1 Структура программного комплекса..........................................94

4.2. Вычислительный эксперимент............................................114

Выводы по четвертой главе..........................................................119

ЗАКЛЮЧЕНИЕ.......................................................................121

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ..........................123

ПРИЛОЖЕНИЕ..........................................................................132

ВВЕДЕНИЕ

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

1 Кофман А. Введение в теорию нечетких множеств / А. Кофман. - М. : Наука, 1986. - 320 с.

4

отношения сходства/несходства. Кроме того, отсутствуют подходы к сравнению декомпозиционных деревьев.

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

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

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

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

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

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

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

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

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

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

4) Для формирования отношений сходства/несходства предложен

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

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

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

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

моделирования.

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

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

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

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

ГЛАВА 1. АНАЛИЗ ПОДХОДОВ К РЕШЕНИЮ ЗАДАЧИ КЛАСТЕРИЗАЦИИ

1.1. Постановка задачи кластеризации

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

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

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

Рассмотрим основные понятия кластерного анализа [11,16,31].

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

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

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

Согласно [11] - «кластеры - это «непрерывные» области некоторого пространства с относительно более высокой плотностью точек, отделенные других таких же областей областями с относительно низкой плотностью точек».

Существуют достаточно нетрадиционные подходы. Например, в [11] каждая точка считается источником света, она освещает другие точки и сама освещается. Вводится конструкция света, с помощью которой проявляется геометрическая структура кластера.

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

Одно из распространенных формализованных определений

представляющих собой точки в евклидовом пространстве размерности с1.

Кластеризация - это разбиение объектов множества X на К кластеров

к

Я!,...,Кк, удовлетворяющих условиям для /^у и

J=|

таких что заданная функция качества / достигает своего экстремального

кластеризации [31]: Пусть задано множество объектов

значения. Типичная функция качества имеет вид

где с] - центр кластера . В этом случае цель кластеризации - найти вектор центроидов с = {с1,...,ск) и соответствующее разбиение ,

минимизирующее функцию (1).

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

Схожесть объектов может определяться не только на основе функции расстояния, но и на основе специальных отношений сходства и подобия [25,42].

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

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

классификации имеется коллекция расклассифицированных (тренировочных) объектов, и задача состоит в отнесении нового элемента данных к одному из существующих классов [47,58].

Этапы решения задачи кластеризации [31] представляют на рис.1.1.

Цикл обратной связи Рис. 1.1. Этапы решения задачи кластеризации

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

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

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

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

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