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

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

Хачумов Михаил Вячеславович

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

ДАННЫХ

05.13.17 - Теоретические основы информатики

Автореферат

2 6 дпр ЇШ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2012

005017978

005017978

Работа выполнена на кафедре информационных технологий Российского университета дружбы народов

Научный руководитель кандидат физико-математических наук,

профессор Толмачев Игорь Леонидович

Официальные оппоненты

Сачков Юрий Леонидович, д.ф.-м.н., доцент, руководитель Центра процессов управления Института программных систем им. А.К. Айламазяна Российской академии наук

Комарова Екатерина Владимировна, к.ф.-м.н., доцент, заведующая кафедрой прикладной математики Российского государственного социального университета

Ведущая организация Вычислительный центр им. A.A. Дородницына

Российской академии наук

Защита диссертации состоится 18 мая 2012 г. в 15 час. 30 мин. на заседании диссертационного совета Д 212.203.28 при Российском университете дружбы народов по адресу г. Москва, ул. Орджоникидзе, дом 3, ауд. 110.

С диссертацией можно ознакомиться в научной библиотеке Российского университета дружбы народов по адресу: 117198, Москва, ул. Миклухо-Маклая, дом 6. (Отзывы на автореферат просьба направлять по указанному адресу)

Автореферат разослан « Д » апреля 2012 г.

Ученый секретарь диссертационного совета

М.Б. Фомин

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

Актуальность темы

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

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

Исследования геометрической кластеризации, в основном, представлены работами зарубежных ученых США: Still S., Bialek W., Bottou L., Sun J., Yao Y., Matousek J., Японии: Imai I., Inaba M., Imai H., Sadakane К. и др. Большой вклад в развитие общей теории кластерного анализа внесли Moore A.W., Gray A.G., Pelleg D., Tryon R.C., Bailey D.E., Jain A.K., Dubes R.C. (алгоритмы и техника кластеризации); Ball G.H., Hall DJ., MacQueen J., Lloyd Stuart P. (методы k-средних); Jordan M.I.; Moore A.W., Trevor H., Tibshirani R., Friedman J. (иерархические методы); Hardin R.H., Sloane N.J.A., Smith W.D., Sokal R.R., Sneath, P.H. (центроидный метод) и др. Заметный вклад в развитие методов кластерного анализа внесли и отечественные ученые: Дорофеюк A.A., Мучник И.Б., Растригин Л.А., Загоруйко Н.Г и др.

Разработанные методы не учитывают возможность одновременной обработки графических и текстовых разделов документов. В то же время существенную поддержку системам поиска могут оказать подходы, использующие анализ графических образов, содержащихся во многих документах. Несмотря на разную природу текстов и изображений, многие методы их анализа являются общими. В частности, это касается моделей геометрического представления кластеров, выбора метрик и методов классификации. Большой вклад в развитие теории распознавания образов внесли зарубежные ученые Duba R., Hart Р., Той J.T., Gonsales R.C., Fukunaga К., Patrick E., Rosenblatt Frank (персептрон) Breiman L., Friedman J.H., Olshen R.A., Stone C.T., Quinlan J.R. (деревья решений) и отечественные ученые: Айвазян С.А., Айзерман М.А., Браверман Э.М. (метод потенциальных функций), Розоноэр Л.И., Вапник В.Н., Червоненкис А.Я. (статистическая теория распознавания). Ю.И.Журавлев (алгебраическая теория

распознавания) и др. Вопросами классификации и кластеризации искусственными нейронными сетями (ИНС) занимались Rosenblatt F., KohonenT.K., Hopfield J.J., VermaB., HaykinS., MahoneyM., Cheng H., Wosserman F., Горбань A.H., Ясницкий JI.H. и другие исследователи. Вопросами одновременной обработки текста, графики и звука в рамках единой модели представления данных занимался отечественный исследователь Харламов А.А.

В настоящее время существует множество методик, осуществляющих кластеризацию документов. Назовем некоторые из них: Custom Search Folders, Latent Semantic Analysis/Indexing (LSA/LSI); Suffix Tree Clustering (STC); Single Link, Complete Link, Group Average; Scatter/Gather, K-means, Concept Indexing (CI); Self-Organizing Maps (SOM).

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

Цель работы

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

1. Теоретическое исследование свойств метрик пространства rp и построение на этой основе методов решения задач кластеризации и классификации;

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

3. Разработка и исследование метода кластерного анализа с расширенным набором метрик и способов начального размещения кластеров;

4. Разработка и исследование метода кластерного анализа на основе варьирования размерности пространства;

Методы исследования

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

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

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

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

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

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

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

Практическая значимость

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

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

Апробация работы

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

1. Четвертая международная научно-техническая конференция «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 02-05 октября, 2007 г.);

2. XVI Международная конференция по вычислительной механике и современным прикладным программным системам (Алушта, ВМСППС'2009, 25-31 мая 2009 г.);

з

3. Третья Всероссийская научная конференция «Нечеткие системы и мягкие вычисления» НСМВ-2009 (Волгоград, 21-24 сентября 2009 г.);

4. II Международная научно-практическая конференция «Наука и современность - 2010» (Новосибирск, 16 апреля 2010 г.);

5. Девятая международная научно-практическая конференция «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 22-23 апреля 2010 г.);

6. Первая всероссийская научная конференция с международным участием (8А8М-2011) «Системный анализ и семиотическое моделирование» (Казань, 24-28 февраля 2011г.);

7. Всероссийская конференция с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологических систем» (Москва, 18-22 апреля 2011 г.);

8. Всероссийская конференция с элементами научной школы для молодежи «Интеграция науки и образования как фактор опережающего развития профессионального образования» (Москва, 20 сентября 2011 года).

Публикации

Основные результаты диссертационной работы изложены в 13 печатных работах, в том числе четыре статьи опубликованы в рецензируемых изданиях, рекомендованных ВАК РФ.

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

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

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

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

Целью кластеризации является объединение объектов в непересекающиеся группы (кластеры, классы, множества) «близких» объектов. Задача геометрической кластеризации формулируется следующим образом: разбить множество точек X а Яр, |Х| = п на к (к> 1) -

подмножеств (кластеров, классов) СиС2,—,Ск, С, nCj =0 \/i,j, і j, X=ÜC,

так, чтобы выполнялось условие

ЫхеС.

(1.1)

где єі?7'— ядро кластера С,-, а сі(апх) — расстояние между ядром Д; и точкой х из множества X. Характеристики кластеров показаны на рис.1.

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

1) разбиение на классы С, при фиксированных значениях ядер;

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

<ф,,х)

Кластер С:

Кластер С. І'

Центр кластера Кластер С3

Рисунок 1 - Геометрические характеристики кластеров

Пусть задано произвольное подмножество X с Rp и точки x,y,z е X. Определение 1.1. (Mahalanobis P.C., 1936). Статистическим расстоянием или расстоянием Махаланобиса (Mahalanobis Distance) между двумя точками и У = (У\,-,Ур) в пространстве Rp называют функцию вида

Ä.............._.........................._..........._............._...................................................._..................._............................................................................................

dM (х, у) = -¡(х-у? S~\x-y)

(1.2)

где dM(x,0)=\\x\\s=ylxrS 'х является нормой х . Здесь S - матрица ковариации.

Пусть г, = (гл,...,21р)т и = (гп,...,2^)т - два вектора размерности р (т.е. г, и 2] єЯр для всех і,у). Матрица ковариации размерности р*р для

N точек пространства Кр определяется как: 5 =-АТА, где:

А =

{Z1X,...,Z1P)T ~{zx,...,ZV)T

(zm,...,ZNp) -(zx,...,zp)

Здесь (zx,...,z р)т— вектор средних значений координат N точек.

Определение 1.2. (Амелькин С.А., 2005). Расстоянием Евклида-Махаланобиса (Euclidean-Mahalanobis Distance) между двумя точками х = (х1,...,хр) и у = (у\,—,ур)в пространстве R" называется функция вида:

dE_M(x,y) = 4{x-y)T{S + E)-\x-y), | (1.3)

где Е - единичная матрица. Метрика (1.3) устраняет недостаток метрики Махаланобиса, поскольку элементы ее главной диагонали всегда больше нуля.

Определение 1.3. (Grudic G., Mulligan J., 2006). Полиномиальным расстоянием Махаланобиса (Polynomial Mahalanobis Distance) между двумя точками х = (х„...,хр) и у = (у1,-,ур) в пространстве R" называется функция вида:

dPU{x,y) = J(N-l)(x-yfU%i[/(x-y), J (1.4)

где N - размерность матрицы А, ААТ = иш^ит - есть результат сингулярного разложения симметрической матрицы ААТ, причем:

Я^г = ¿¿^(щ + 6г,...,сор + 82), где 52 — малое положительное число.

Известно, что расстояние Евклида является метрикой в пространстве Яр. Справедливость выполнения условий метрики для функции (1.2) показана Аккерманом в 2009 году. Некоторые утверждения Аккермана используются в настоящей диссертации.

Лемма 1.1. (Аскегтап М.Л., 2009). Пусть йк,(х,у) есть квадрат

расстояния Махаланобиса с!м (х, у) с положительно определенной матрицей

М е Крхр. Тогда существует несингулярная матрица В е Кр'р такая, что для

каждых х, у, еЯр имеет место Ом(х,у) = \Вх-Ву^.

Лемма 1.2. (Аскегтап М.Я., 2009). Для квадрата расстояния Махаланобиса Вм и для всех х,у,г е Кр имеет место: А, (х,у) < 2ПМ (х, г)+2Д„ (г, у).

Теорема 1.1. (Аскегтап М.Я., 2009). Расстояние Махаланобиса с!м(х,у) является метрикой.

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

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

Измерение расстояний между классами

Покажем, при каких условиях метрика Махаланобиса может быть использована для классификации (т.е. для определения принадлежности точки одному из нескольких классов). Пусть заданы три класса С,, С2, С3 в

метрическом пространстве Яр. Выпишем условия для метрик, ориентированных на измерение межклассовых расстояний:

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

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

Для расчета расстояния между точкой х и классом С, можно

или Евклида-Махаланобиса (1Е_м(х,Сх) . При этом второй точкой служит

1) о?(С],С2)>0

2) ¿/(С„С2) = 0оС, = С2

3) ^(С„С2) = </(С2,С1)

4) ¿(С^^сЦС^ + сЦС^).

1) ¿(С„С2)>0

2)' ¿(с„с2)=о<=с; =с2

3) сЦС^С^Л^С,)

4) ^(С,,С2)<с/(С,,С3)+с/(С3,С2).

воспользоваться расстоянием Махаланобиса

,-t « „ - j=\ центр класса ц, представленный вектором средних значении * = . . , где

|ч|

|С,| - мощность класса, j - элемент класса С,.

Пусть точку х надо отнести к одному из двух классов С,, С2, а также измерить расстояния между классами. Построим матрицы ковариаций 5,1,5,2,53 классов Ci,C2,C3 соответственно. Объединенная матрица ковариаций для классов Сх,Сг может быть задана как сумма Sl 2 =St+S2, (есть и другой

способ объединения матриц ковариаций, например, S12=-!-(S,+S2),

и, + п2 - 2

п, - число элементов класса С, ), а для классов С,,С2,С3 соответственно — =5,1+52 + 5,3. Расстояние dM(Ci ,С\) удовлетворяет, так же, как и расстояние Евклида, условиям: d (С, ,С;) > О, С, = Cj=>d (С;,С;) = 0 и является симметричным.

Теорема 2.1. Расстояния dM(x,Ct), d^C^Cj) (хеС,С = С(uC;) являются квазиметриками.

Для доказательства теоремы достаточно показать, что dM(x,C2) <dM(C2,C1) + dM(Cltx), dM(C„C2) < dM{C„C,)+dM{CyC2). Доказательство осуществляется по аналогии с доказательством Теоремы 1.1.

Таким образом, объединение частных матриц ковариаций обеспечивает выполнение свойств квазиметрики для функций Махаланобиса (а также Евклида-Махаланобиса) в случае измерения межклассовых расстояний. Рассмотрим следующую задачу практически важную для кластеризации. Задача размещения ядер кластеров формулируется следующим образом: как расположить п точек в р -шаре радиуса г , чтобы сумма расстояний между ними была максимальна [4].

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

Теорема 2.2. Пусть m, е Rp (/ = 1,2,..., ri) - точки, лежащие в р -шаре К (г) радиуса г, S -граница шара K(r), dim^mj)- расстояние между точками m, и m j . Тогда существуют точки т[ е S (/ = 1,...,и), такие что S ¿(щ,т;)< 2 dim-,т'Л.

1 <;< j<n i<;< jin

Таким образом, первоначальное распределение центров кластеров можно свести к задаче размещения п точек на поверхности шара. Приведем несколько определений.

Определение 2.1. Распределение mt (г = 1,2,...,и) точек на сфере в Rp называется равномерным, если точки представляют собой вершины правильных многогранников, описанных сферой.

Определение 2.2. Распределение mi (/' = 1,2,...,и) точек на сфере радиуса г в Rp (п > р) называется равномерным, если для любой точки Щ существует р других точек mjp таких, что d(mi,mjp) = const (п,р,г).

Определение 2.3. Распределение mi (i = 1,2,...,«) точек на сфере в Rp называется квазиравномерным, если оно минимизирует потенциальную энергию системы равных зарядов, размещенных в этих точках (по Д.Томсону).

Из определения 2.1 следует, что количество решений задачи ограничено числом правильных многогранников. Определение 2.2. не охватывает случаи, когда (и < р) , а также приводит к трудностям построения алгоритма вычисления координат равномерно расположенных точек. Выдвинем следующую гипотезу о квазиравномерности. Гипотеза. Выражение Z d(ml, m;) принимает наибольшее значение в

Ki<jin

случае, когда точки т, квазиравномерно расположены на границе р -шара -S.

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

1. Покажем, что данная гипотеза справедлива для плоского случая.

Лемма 2.1 (о размещении центров кластеров в круге) [1]. Пусть щ (г = 1,2,...,и) - точки, лежащие на границе ¿круга К(г) радиуса г, dim^ntj) - расстояние между точками т, и т . Выражение Z сЦгп^тЛ принимает

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

2. Рассмотрим случай трехмерной сферы.

Лемма 2.2. Пусть /и, (г = 1,..,4) - точки, лежащие на трехмерной сфере. Выражение £ с1(т^т,) принимает наибольшее значение в случае, когда

1<;< j< 4

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

Леммы 2.1 и 2.2 составляют важные, хотя и частные результаты, которые подтверждают Гипотезу.

Квазиравномерное размещение точек имеет практическое решение только для некоторого количества точек (2,3,4,6,12) на 3-х мерной сфере (задача Томсона).

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

Метод кластерного анализа, основанный на сетевой модели

Для решения задач геометрической кластеризации и классификации предложена вычислительная схема на основе алгоритма модифицированной искусственной нейронной сети (ИНС) Кохонена с набором метрик (Евклида, Махаланобиса, Евклида-Махаланобиса) и возможностью выбора способа начального размещения ядер кластеров, в том числе равномерного. Задача кластеризации ^-теаш с введением набора метрик формулируется в следующем виде [7]: к Т

X £ О,.-//;) 5 (Хі -// )—>тіл

М ь=,єс,.

_ 1 х

где И] - 2-1Х' , к - число кластеров, Сі - _/' -й кластер, и,- - число

пі -х.-с,

элементов і -о кластера,

Е, для метрики Евклида,

5 = <5, для метрики Махаланобиса {Б —матрица ковариаций)

Б + Е, для метрики Евклида-Махаланобиса.

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

Рисунок 2 - Этапы решения задачи коммивояжера Метод бинарной классификации

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

Рассмотрим основные этапы решения задачи.

1. Предварительное преобразование пространства признаков и условий задачи в новую систему координат на основе метода главных компонентов (МГК). Преобразование предполагает выполнение следующих действий:

a) Построение матрицы ковариаций 5 размерности их и по табличным данным обучающей выборки.

b) Определение собственных чисел (Л,,...Дл) матрицы 5.

2. Преобразование условий исходной задачи путем пересчета входных векторов №.=(хц,...,х1„), в вектора = (уп,...,у1„), (/ = 1 ,...,.т) новой системы

признаков У = (у],...,у„). Формирование новой таблицы, содержащей

множество векторов V = ] пространства Я" . Пересчет выполняется

следующим образом: V* = А ■ IV?, (/ = 1,...,.га).

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

бинарной классификации в пространстве Я2.

4. Построение разделяющей гиперплоскости или, при необходимости, комитета гиперплоскостей В = (1\,Ь2,...,Ьр), где Ьк ={Ь^,Ьк1) , к = \,...,р , р -количество членов комитета и решающей функции ^'О®). классифицирующей объект со, сое{<ц,...,а>т} в пространстве Я2:

(3.1)

5. Восстановление разделяющей гиперплоскости или комитета большинства в пространстве К":

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

Для этого предлагается модифицированный метод восстановления табличных данных ZET. Используем в качестве «компетентных» векторов расширенной таблицы пару заполненных векторов-столбцов с номерами О', у')-Пусть включенная строка имеет пустое поле в столбце к и заполненные поля в столбцах 1,] (к у). Находим значения модулей коэффициентов корреляции векторов-столбцов с номерами 1,) со столбцом к, обозначаемых как у{Вк,В^ , у(Вк,В]) . Коэффициент корреляции векторов В[ и В2

(В В )

вычисляют по формуле ¡Л, м- Используя пару компетентных

ргМ

векторов-столбцов с номерами /, у и данный £ -й столбец, содержащий пробел, восстанавливаем значение элемента рк , например, следующим образом:

Г(Вк,В,) + у(В1,В^ '

(3.2)

Процедуру восстановления (3.2) повторим для всех векторов, имеющих незаполненные элементы в дополнительной строке.

Ь) Восстановленную строку в системе координат У отобразим в систему координат X, решая обратную задачу:_

(3.3)

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

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

Общая схема кластерного анализа:

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

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

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

Экспериментальные исследования на серии полутоновых снймков показали преимущество квазиметрики Евклида-Махаланобиса по полноте распознавания графических объектов в сравнении с метрикой Евклида. Эксперименты по кластеризации документов (на выборке 1000 документов, проанализированных экспертом) показали, что метрика Евклида-Махаланобиса дает улучшение качества кластеризации на 15-20% по сравнению с метрикой Евклида.

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

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

Характеристики методов кластерного анализа

Результаты кластерного анализа слабо структурированных

і Метод варьирования 1 размерности | пространства

I 1. Позволяет свести п-| мерную задачу к і двумерной с [ восстановлением I решающей функции в | иегоднойсистеме I координат

І 2. По сравнению с | аналогичным методам | обеспечивается:

I а) детерминированность | перехода (отсутствие | необходимостипопбора Ї коэффициентов)

I б) уіучшешю разбиения Ї на классы благодаря • применению МГК

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

1. По сравнению с известным сетевым методом имеет большие функциональные возможности

2- Обеспечивает следующий преимущества для задачи коммивояжера:

а) модель с равномерным размещением нейронов дает улучшение пути на 5-10%, а по итерациям на 7 % по сравнению со случайным

б) модель с квазкжтригой Махапанэбиса дает улучшение пути до 5%, а гю итерациям да 20% по сравнению с метрикой Евклида

Применение набора метрик обеспечивает сочетание высокой скорости обработки и точно сти классификации

При использовании квазиметрики Евкпида-Меяаланобиса:

а) полнота распознавания в экспериментах над изображениями достигает порядка 70-100%;

б) точность кластеризации (аннотирования) текстовых документов возрастает на 15-20%

ї | Ожидаемые характеристики: і

і і Повышение релевантности по иска ; ¡1 информации за счет одновременной | 11 обработки текста и трафики 1

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

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

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

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

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

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

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

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

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

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

Основные научные результаты диссертации опубликованы в следующих работах:

работы из списка, рекомендованного ВАК РФ:

1. Атаманов В.В., Козачок М.А., Трушков В.В., Хачумов М.В. Выбор первоначального расположения кластеров в нейронной сети Кохонена // Нейрокомпьютеры: разработка и применение - 2009,- №1- С. 73-76.

2. Хачумов М.В. Задача кластеризации текстовых документов // Информационные технологии и вычислительные системы,- 2010- № 2.-С. 42-49.

3. Толмачев И.Л., Хачумов М.В. Бинарная классификация на основе варьирования размерности пространства признаков и выбора эффективной метрики // Искусственный интеллект и принятие решений,- 2010 - № 2,- С 310.

4. Хачумов М.В. Расстояния, метрики и кластерный анализ // Искусственный интеллект и принятие решений,-2012-№ 1.-С. 81-89.

другие работы:

5. Хачумов М.В. Методы совершенствования алгоритмов кластеризации текстов. - Высокие технологии, фундаментальные и прикладные исследования, образование// Сборник трудов Четвертой международной научно-технической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 02-05 октября 2007 года). - СПб: Изд-во Политехнического университета, 2007, Т. 11 — С. 135-136.

6.Талалаев А.А., Тищенко И.П., Хачумов М.В. Выделение и кластеризация текстовых и графических элементов на полутоновых снимках // Искусственный интеллект и принятие решений - 2008 - № 3 - С. 72-84.

7. Хачумов М.В. Нейронная сеть Кохонена с универсальной метрикой // Материалы XVI Международной конференции по вычислительной механике и современным прикладным программным системам (ВМСППС'2009, Алушта, 25-31 мая 2009 года).- М.: Изд-во МАИ - ПРИНТ, 2009 - С 742-745.

8.Фраленко В.П., Хачумов М.В. Классификация на основе аппарата нейронных сетей с применением метода главных компонент и комитета большинства // Сборник статей Третьей Всероссийской научной конференции «Нечеткие системы и мягкие вычисления» НСМВ-2009 (Волгоград, 21-24 сентября 2009 года).- Волгоград: Изд-во Волгоградского государственного технического университета, Т. 2,2009 - С. 70-79.

9.Хачумов М.В. Применение нейронной сети и расстояния Евклида-Махаланобиса в задаче бинарной классификации // Сборник материалов II Международной научно-практической конференции «Наука и современность - 2010» (Новосибирск, 16 апреля 2010 года). - Новосибирск: Изд-во «СИБПРИНТ», Часть 3,2010,- С. 82-86.

10. Хачумов М.В. О проблеме интеграции анализа текстовых данных и графических образов для задач поиска и кластеризации документов // Сборник трудов Девятой международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 22-23 апреля 2010 года).- СПб: Изд-во Политехнического университета, 2010, Т.З.- С. 157-160.

11. Хачумов М.В. О выборе метрики для решения задач классификации и кластеризации // Материалы Первой всероссийской научной конференции с международным участием (8АБМ-2011) «Системный анализ и семиотическое моделирование» (Казань, 24-28 февраля 2011 года).- Казань: Изд-во «Фэн» Академии наук РТ, 2011- С. 255-260.

12. Хачумов М.В. Модели представления данных в задачах распознавания образов и кластеризации // Тезисы докладов Всероссийской конференции с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологических систем» (Москва, 18-22 апреля 2011 года).- М.: Изд-во РУДН, 2011.-С. 146-148.

13. Хачумов М.В., Фраленко В.П. Графическое приложение для решения задач коммивояжера и кластеризации // Тезисы докладов Всероссийской конференции с элементами научной школы для молодежи «Интеграция науки и образования как фактор опережающего развития профессионального образования» (Москва, 20 сентября 2011 года).- М.: Изд-во Московского государственного университета тонких химических технологий имени М.В. Ломоносова, 2011- С. 241-244.

Личный вклад автора в работах, опубликованных в соавторстве, заключается в следующем: в работе [1] соискателю принадлежит постановка задачи начального размещения кластеров в целом и решение задачи коммивояжера, в [3] - постановка задачи и метод решения задачи построения разделяющей функции методом варьирования размерности пространства признаков, в [6] - постановка задачи кластеризации слабоструктурированной информации и метод кластеризации с экспериментом; в [8] - реализация метода комитета большинства; в [13] - сетевой алгоритм решения задачи коммивояжера.

Хачумов Михаил Вячеславович

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

ДАННЫХ

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

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

Доказана лемма о равномерном размещении ядер кластеров в круге.

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

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

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

Khachumov Michael Vjacheslavovich

DEVELOPMENT AND RESEARCH OF METHODS OF SEMI-STRUCTURED DATA CLUSTER ANALYSIS

The theorem that Mahalanobis and Euclidean-Mahalanobis functions are quasi-metrics is proved. The theorem is necessary for classification problems solving.

The theorem of cluster centers placing on p -dimensional sphere (given that maximum of summarized distance criteria is satisfied) is proved. The theorem allows solving problems of initial cluster centers placing.

The lemma of regular cluster placing in a circle is proved.

The network model method of geometric clustering based on application of a Kohonen neural network with a set of metrics and methods of initial cluster centers placing is offered.

The method of binary classification based on a variation of feature space and modified algorithm ZET of restoration of the passed values of the table of signs is developed.

The algorithms and experimental software for cluster analysis of semi-structured information is developed.

Подписано в печать 09.04.2012 г. Формат 60x84/16. Печать офсетная. Бумага офсетная. Гарнитура Тайме.

_Усл. печ. л. 1,25 Тираж 100 экз. Заказ 395_

Российский университет дружбы народов 115419, ГСП-1, г. Москва, ул. Орджоникидзе, д. 3 Типография РУДН 115419, ГСП-1, г. Москва, ул. Орджоникидзе, д. 3, тел. 952-04-41

61 12-1/798

РОССИЙСКИИ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ Факультет физико-математических и естественных наук

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

Хачумов Михаил Вячеславович

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

05.13.17 - Теоретические основы информатики

Диссертация

на соискание ученой степени кандидата физико-математических наук

Научный руководитель кандидат физико-математических наук,

профессор Толмачев Игорь Леонидович

МОСКВА 2012

СОДЕРЖАНИЕ

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

ГЛАВА 1. АНАЛИЗ ПРОБЛЕМНЫХ ВОПРОСОВ КЛАСТЕРИЗАЦИИ И

КЛАССИФИКАЦИИ СЛАБОСТРУКТУРИРОВАННЫХ ДАННЫХ.............................10

1Л. Модели представления слабо структурированной информации............................11

1.1.1. Табличный способ задания исходных данных..................................................11

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

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

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

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

1.2.2. Постановка задачи классификации.................................................................16

1.3. Анализ мер близости и расстояний. Основные понятия и определения...............17

1.4. Методы выбора первоначального числа кластеров...............................................22

1.4.1. Метод последовательного сокращения числа кластеров..............................23

1.4.2. Метод последовательного увеличения числа кластеров................................23

1.4.3. Метод выбора числа кластеров направленным объединением......................24

1.5. Проблема и модели начального расположения кластеров....................................26

1.5.1. Сферическая (пространственная) модель размещения кластеров...............26

1.5.2. Модель линейных зависимостей......................................................................27

1.6. Методы кластерного анализа..................................................................................28

1.6.1. Классификация на основе метода МГУ А........................................................29

1.6.2. Неиерархические методы кластеризации. Алгоритм к-теат.......................31

1.6.3. Иерархические методы кластеризации..........................................................32

1.6.4. Искусственные нейронные сети......................................................................33

1.7. Особенности задачи кластеризации документов...................................................34

1.7.1.Методы кластеризации документов...............................................................34

1.7.2.Постановка задачи классификации текстов на естественном языке..........35

1.7.3.Проблемные вопросы и совершенствование методов кластерного анализа. 36

1.8. Основные выводы по Главе 1.................................................................................37

ГЛАВА 2. АНАЛИЗ МЕТРИК И ПОСТРОЕНИЕ МОДЕЛЕЙ РАЗМЕЩЕНИЯ ТОЧЕК НА СФЕРЕ ДЛЯ РЕШЕНИЯ ЗАДАЧ ГЕОМЕТРИЧЕСКОЙ КЛАСТЕРИЗАЦИИ...............39

2.1. Метрика Махаланобиса. Предварительные исследования....................................39

2.2. Квазиметрика для измерения расстояний между классами...................................42

2.2.1. Принцип объединения матриц ковариаций.....................................................43

2.2.2. Построение квазиметрики для измерения расстояния между классами.......43

2.3. Задача об оптимальном размещении точек на сфере............................................45

2.4. Основные выводы по Главе 2.................................................................................51

ГЛАВА 3. РАЗРАБОТКА МЕТОДОВ КЛАСТЕРНОГО АНАЛИЗА НА ОСНОВЕ СЕТЕВОЙ МОДЕЛИ И ВАРЬИРОВАНИЯ РАЗМЕРНОСТИ ПРИЗНАКОВОГО ПРОСТРАНСТВА..............................................................................................................53

3.1. Метод геометрической кластеризации на основе сетевой модели........................53

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

3.1.2. Общая схема метода........................................................................................55

3.2. Применение сетевой модели для решения задачи коммивояжера........................56

3.2.1. Задача коммивояжера......................................................................................56

3.2.2. Решение задачи при равномерном размещением кчастеров..........................57

3.2.3. Стратегии движения нейронов.......................................................................59

3.2.4. Экспериментачьные исследования сетевой модели.......................................61

3.3. Оценки необходимого числа кластеров.................................................................63

3.3.1. Оценка числа кластеров для задачи о коммивояжере....................................63

3.3.2. Оценка числа кластеров для задачи кластеризации.......................................64

3.4. Бинарная кластеризация на основе контура минимальной длины........................65

3.5. Метод классификации на основе варьирования размерности пространства признаков........................................................................................................................66

3.6. Совместное применение методов кластерного анализа........................................71

3.7. Основные выводы по Главе 3.................................................................................73

ГЛАВА 4. ПРАКТИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧ КЛАССИФИКАЦИИ И КЛАСТЕРИЗАЦИИ СЛАБОСТРУКТУРИРОВАННОЙ ИНФОРМАЦИИ.....................74

4.1. Анализ документов, представленных полутоновыми снимками..........................74

4.1.1.Постановка задачи двухэтапной кластеризации............................................75

4.1.2.Распознавание и кластеризация полутоновых изображений..........................76

4.1.3. Бинарная классификация полутоновых изображений.....................................77

4.2. Особенности выделения букв и слов на полутоновых снимках............................82

4.2.1. Особенности выделения букв...........................................................................82

4.2.2. Особенности выделения ключевых слов..........................................................85

4.2.3. Применение ИНС для кластеризации текстов и изображений.....................87

4.3. Кластеризация текстовых документов на основе набора метрик..........................90

4.31. Извлечение корпуса релевантных текстовых документов.............................90

4.3.2. Образование учебной выборки и предварительный сбор статистики.........91

4.3.3. Векторизация документов...............................................................................91

4.3.4. Алгоритм кластеризации.................................................................................93

4.3.5. Аннотирование кластеров...............................................................................94

4.3.6. Распределение всех документов корпуса по кластерам (классификация).... 95

4.3.7. Анализ качества выполнения кластеризации................................................... 96

Основные выводы по Главе 4........................................................................................97

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

Список литературы..........................................................................................................100

ВВЕДЕНИЕ

Актуальность темы

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

Геометрическая кластеризация (geometric clustering) относится к методам получения минимального или заданного числа компактных групп, реализуемых с помощью матриц расстояний и графов. В задаче геометрической кластеризации представлены точки потенциально высокоразмерного пространства, на котором определена метрика. Существенное значение имеет здесь сокращение размерности данных и визуализация результатов. Исследования геометрической кластеризации, в основном, представлены работами зарубежных ученых США: Still S., Bialek W., Bottou L., Sun J., Yao Y., Matousek J., Японии: Imai I., Inaba M., Imai H., Sadakane К. и др.

Большой вклад в развитие общей теории кластерного анализа внесли Moore A.W., Gray A.G., Pelleg D., Tryon R.C., Bailey D.E., Jain A.K., Dubes R.C. (алгоритмы и техника кластеризации); Ball G.H., Hall D.J., MacQueen J., Lloyd Stuart Р. (методы k-средних); Jordan M.I.; Moore A.W., Trevor H., Tibshirani R., Friedman J. (иерархические методы); Hardin R.H., Sloane N.J.A., Smith W.D., Sokal R.R., Sneath, P.H. (центроидный метод) и др. Заметный вклад в развитие методов кластерного анализа внесли и отечественные ученые: Дорофеюк A.A., Мучник И.Б., Растригин ДА., Загоруйко Н.Г и др.

Разработанные методы не учитывают возможность одновременной обработки графических и текстовых разделов документов. В то же время существенную поддержку системам поиска могут оказать подходы, использующие анализ графических образов, содержащихся во многих документах. Несмотря на разную природу текстов и изображений, многие методы их анализа являются общими. В частности, это касается моделей геометрического представления кластеров, выбора метрик и методов классификации. Большой вклад в развитие теории распознавания образов внесли зарубежные ученые Duba R., Hart Р., Той J.T., Gonsales R.C., Fukunaga К., Patrick E.,

Rosenblatt Frank (персептрон) Breiman L., Friedman J.H., Olshen R.A., Stone C.T., Quinlan J.R. (деревья решений) и отечественные ученые: Айвазян С.А., Айзерман М.А., Браверман Э.М. (метод потенциальных функций), Розоноэр Л.И., Вапник В.Н., Червоненкис А.Я. (статистическая теория распознавания). Ю.И.Журавлев (алгебраическая теория распознавания) и др. Вопросами классификации и кластеризации искусственными нейронными сетями (ИНС) занимались Rosenblatt F., Kohonen Т.К., Hopfield J. J., Verma В., HaykinS., MahoneyM., Cheng H., Wosserman F., Горбань A.H., Ясницкий JI.H. и другие исследователи. Вопросами одновременной обработки текста, графики и звука в рамках единой модели представления данных занимался отечественный исследователь Харламов A.A.

В настоящее время существует множество методик, осуществляющих кластеризацию документов. Назовем некоторые из них: Custom Search Folders, Latent Semantic Analysis/Indexing (LSA/LSI); Suffix Tree Clustering (STC); Single Link, Complete Link, Group Average; Scatter/Gather, K-means, Concept Indexing (CI); Self-Organizing Maps (SOM).

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

Цель работы

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

1 .Теоретическое исследование свойств метрик пространства Rp и построение на этой основе методов решения задач кластеризации и классификации;

2.Выдвижение гипотез и исследование теоретических вопросов первоначального размещения кластеров в многомерном пространстве;

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

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

Методы исследования

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

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

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

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

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

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

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

Практическая значимость

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

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

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

Апробация работы

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

1. Четвертая международная научно-техническая конференция «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 02-05 октября, 2007 г.);

2. XVI Международная конференция по вычислительной механике и современным прикладным программным системам (Алушта, ВМСППС'2009, 25-31 мая 2009 г.);

3. Третья Всероссийская научная конференция «Нечеткие системы и мягкие вычисления» НСМВ-2009 (Волгоград, 21-24 сентября 2009 г.);

4. II Международная научно-практическая конференция «Наука и современность -2010» (Новосибирск, 16 апреля 2010 г.);

5. Девятая международная научно-практическая конференция «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 22-23 апреля 2010 г.);

6. Первая всероссийская научная конференция с международным участием (ЭЛвМ-2011) «Системный анализ и семиотическое моделирование» (Казань, 24-28 февраля 2011г.);

7. Всероссийская конференция с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологических систем» (Москва, 18-22 апреля 2011 г.).

8. Всероссийская конференция с элементами научной школы для молодежи «Интеграция науки и образования как фактор опережающего развития профессионального образования» (Москва, 20 сентября 2011 года).

Публикации

Основные результаты диссертационной работы изложены в 13 печатных работах, в том числе четыре статьи опубликованы в рецензируемых изданиях, рекомендованных ВАК РФ.

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

Основное содержание работы

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

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

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