Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Хачумов Михаил Вячеславович
РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ КЛАСТЕРНОГО АНАЛИЗА СЛАБОСТРУКТУРИРОВАННЫХ ДАННЫХ
05.13.17 - Теоретические основы информатики
Автореферат диссертации на соискание ученой степени кандидата физико-математических наук
Москва - 2012
Работа выполнена на кафедре информационных технологий Российского университета дружбы народов Научный руководитель кандидат физико-математических наук, профессор Толмачев Игорь Леонидович Официальные оппоненты Сачков Юрий Леонидович, д.ф.-м.н., доцент, руководитель Центра процессов управления Института программных систем им. А.К. Айламазяна Российской академии наук Комарова Екатерина Владимировна, к.ф.-м.н., доцент, заведующая кафедрой прикладной математики Российского государственного социального университета Ведущая организация Вычислительный центр им. А.А. Дородницына Российской академии наук
Защита диссертации состоится 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 K. и др. Большой вклад в развитие общей теории кластерного анализа внесли 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 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. (центроидный метод) и др. Заметный вклад в развитие методов кластерного анализа внесли и отечественные ученые: Дорофеюк А.А., Мучник И.Б., Растригин Л.А., Загоруйко Н.Г и др.
Разработанные методы не учитывают возможность одновременной обработки графических и текстовых разделов документов. В то же время существенную поддержку системам поиска могут оказать подходы, использующие анализ графических образов, содержащихся во многих документах. Несмотря на разную природу текстов и изображений, многие методы их анализа являются общими. В частности, это касается моделей геометрического представления кластеров, выбора метрик и методов классификации. Большой вклад в развитие теории распознавания образов внесли зарубежные ученые Duba R., Hart Р., Tou J.T., Gonsales R.C., Fukunaga K., Patrick E., Rosenblatt Frank (персептрон) Breiman L., Friedman J.H., Olshen R.A., Stone C.T., Quinlan J.R. (деревья решений) и отечественные ученые: Айвазян С.А., Айзерман М.А., Браверман Э.М. (метод потенциальных функций), Розоноэр Л.И., Вапник В.Н., Червоненкис А.Я.
(статистическая теория распознавания). Ю.И.Журавлев (алгебраическая теория распознавания) и др. Вопросами классификации и кластеризации искусственными нейронными сетями (ИНС) занимались Rosenblatt F., Kohonen T.K., Hopfield J.J., Verma B., Haykin S., Mahoney M., Cheng H., Wosserman F., Горбань А.Н., Ясницкий Л.Н. и другие исследователи.
Вопросами одновременной обработки текста, графики и звука в рамках единой модели представления данных занимался отечественный исследователь Харламов А.А.
В настоящее время существует множество методик, осуществляющих кластеризацию документов. Назовем некоторые из них: 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).
Несмотря на очевидный прогресс в этой области, до сих пор далеки от окончательного решения следующие проблемные теоретические вопросы:
выбор первоначального расположения ядер кластеров, обоснование выбора метрик; создание метода унифицированной обработки текстов и графики;
управление размерностью данных; ускорение процессов и повышение точности кластеризации. Это определяет актуальность темы исследования направленной на создание универсальных методов анализа слабоструктурированной информации.
Цель работы Целью работы является развитие методов кластерного анализа слабоструктурированных данных на основе совершенствования математических моделей, метрик и алгоритмов. Цель достигается решением следующих задач:
p 1. Теоретическое исследование свойств метрик пространства R и построение на этой основе методов решения задач кластеризации и классификации;
2. Исследование теоретических вопросов первоначального размещения кластеров в многомерном пространстве.
3. Разработка и исследование метода кластерного анализа с расширенным набором метрик и способов начального размещения кластеров;
4. Разработка и исследование метода кластерного анализа на основе варьирования размерности пространства;
Методы исследования В диссертационной работе использованы методы теории множеств, теории алгоритмов, методы обработки изображений. Исследования базируются на теории искусственных нейронных сетей, методах алгебраической теории распознавания изображений и моделирования многообъектных структур на ЭВМ.
Научная новизна Научная новизна заключается в построении новых методов и алгоритмов, обеспечивающих решение задач кластерного анализа текстов и изображений:
1. Доказаны утверждения о том, что функции Махаланобиса и ЕвклидаМахаланобиса являются квазиметриками, что позволяет решать задачи измерения расстояний как внутри, так и между классами, а также между произвольной точкой и классами.
2. Доказана теорема о размещении точек в p -мерном шаре при выполнении критерия максимального суммарного расстояния между точками. Выдвинута гипотеза о квазиравномерности размещения точек при том же критерии, которая частично подтверждена теоремами о равномерном размещении точек в круге и четырех точек в трехмерной сфере, что позволяет решать проблему первоначального размещения ядер кластеров, в том числе для задачи коммивояжера.
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. Первая всероссийская научная конференция с международным участием (SASM-2011) Системный анализ и семиотическое моделирование (Казань, 24-28 февраля 2011г.);
7. Всероссийская конференция с международным участием Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологических систем (Москва, 18-22 апреля 2011 г.);
8. Всероссийская конференция с элементами научной школы для молодежи Интеграция науки и образования как фактор опережающего развития профессионального образования (Москва, 20 сентября 2011 года).
Публикации Основные результаты диссертационной работы изложены в 13 печатных работах, в том числе четыре статьи опубликованы в рецензируемых изданиях, рекомендованных ВАК РФ.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего наименований. Основная часть изложена на 106 страницах машинописного текста, иллюстрируется 25 рисунком и 19 таблицами.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертации, сформулированы цели и задачи работы, раскрыты научная новизна и практическая ценность результатов работы, приведены данные об апробации результатов, их внедрении и о структуре работы.
В первой главе приведены необходимые определения и приведен аналитический обзор проблемных актуальных вопросов геометрической кластеризации и классификации слабоструктурированной информации.
Существенное внимание уделено геомерическим моделям размещения кластеров и обоснованию метрик. Приведены основные теоремы, которые открывают путь к решению задач кластеризации.
Целью кластеризации является объединение объектов в непересекающиеся группы (кластеры, классы, множества) близких объектов. Задача геометрической кластеризации формулируется X n следующим образом: разбить множество точек X Rp, на k (k 1) - подмножеств (кластеров, классов) С1,С2,...,Сk, Сi С 0 i, j, i j, j k X Сi так, чтобы выполнялось условие i k H dai, x min, (1.1) i1xСi p ai R dai, x ai где ядро кластера Сi, а расстояние между ядром и точкой x из множества X. Характеристики кластеров показаны на рис.1.
Один из известных методов решения задачи метод динамических ядер использует в качестве меры расстояние Евклида. Сначала задаются начальные значения ядер. Затем выполняют итерационно следующие шаги:
1) разбиение на классы Сi при фиксированных значениях ядер;
2) оптимизация значений ядер при фиксированном разбиении на классы.
Процедура останавливается, если после очередного выполнения разбиения на классы не изменился состав ни одного класса.
Рисунок 1 - Геометрические характеристики кластеров p Пусть задано произвольное подмножество X R и точки x, y, z X.
Определение 1.1. (Mahalanobis P.C., 1936). Статистическим расстоянием или расстоянием Махаланобиса (Mahalanobis Distance) между двумя x (x1,..., xp ) y ( y1,..., y ) точками и в пространстве Rp называют функцию p вида (1.2):
(1.2) dM (x, y) (x y)T S1(x y) dM (x,0) x xT S x где является нормой x. Здесь S - матрица S ковариации.
Пусть zi (zi1,...,zip)T z (z,..., z )T два вектора размерности (т.е.
и p j j1 jp p z Rp p p zi R и для всех i, j ). Матрица ковариации размерности для j p S AT A N точек пространства R определяется как:, где:
N (z11,..., z1p )T (z1,..., z )T p (z21,..., z2 p )T (z1,..., z )T p A ...
(zN1,..., zNp )T (z1,..., z p )T (z1,..., z )T Здесь вектор средних значений координат N точек.
p Определение 1.2. (Амелькин С.А., 2005). Расстоянием ЕвклидаМахаланобиса (Euclidean-Mahalanobis Distance) между двумя точками p x (x1,..., xp ) y ( y1,..., yp ) в пространстве называется функция вида:
и R (1.3) dE M (x, y) (x y)T (S E)1(x y), где E - единичная матрица. Метрика (1.3) устраняет недостаток метрики Махаланобиса, поскольку элементы ее главной диагонали всегда больше нуля.
Определение 1.3. (Grudic G., Mulligan J., 2006). Полиномиальным расстоянием Махаланобиса (Polynomial Mahalanobis Distance) между двумя p точками x (x1,...,xp ) и y ( y1,..., yp ) в пространстве R называется функция вида:
dPM (x, y) (N 1)(x y)TUTW1U (x y), (1.4) T A, AAT UW1U - есть результат сингулярного где N - размерность матрицы разложения симметрической матрицы AAT, причем:
2 2 W diag(1 ,...,p ), где Ч малое положительное число.
Известно, что расстояние Евклида является метрикой в пространстве Rp Справедливость выполнения условий метрики для функции (1.2).
показана Аккерманом в 2009 году. Некоторые утверждения Аккермана используются в настоящей диссертации.
Лемма 1.1. (Ackerman M.R., 2009). Пусть DM (x, y) есть квадрат dM (x, y) расстояния Махаланобиса с положительно определенной матрицей p p M Rp p. Тогда существует несингулярная матрица B R такая, что для p x, y, R каждых имеет место DM (x, y) Bx By.
Лемма 1.2. (Ackerman M.R., 2009). Для квадрата расстояния p Махаланобиса DM и для всех x, y, z R имеет место:
DM (x, y) 2DM (x, z) 2DM (z, y).
Теорема 1.1. (Ackerman M.R., 2009). Расстояние Махаланобиса dM (x, y) является метрикой.
Основными задачами
кластерного анализа, решаемыми в диссертационной работе, являются: выбор числа кластеров, первоначальное размещение ядер, обоснование выбора метрик и методов, сокращение пространства признаков. Практическая часть работы направлена на создание технологии кластеризации слабоструктурированной информации. В заключении Первой главы даны предложения по усовершенствованию процедуры кластеризации и сформулированы задачи диссертационной работы.
Во второй главе дано обоснование математического аппарата, необходимого для решения проблемных вопросов классификации и кластеризации. Доказаны необходимые теоремы о метриках, сформулирована и доказана теорема о начальном расположении кластеров.
Выдвинута гипотеза о равномерности размещения ядер кластеров и рассмотрены некоторые геометрические случаи, когда точки кластера равномерно расположены в выпуклой оболочке на круге и сфере.
Измерение расстояний между классами Покажем, при каких условиях метрика Махаланобиса может быть использована для классификации (т.е. для определения принадлежности точки одному из нескольких классов). Пусть заданы три класса C1,C2,C3 в p метрическом пространстве R. Выпишем условия для метрик, ориентированных на измерение межклассовых расстояний:
1) d(С1,С2) 2) d(С1,С2) 0 С1 С 3) d(С1,С2) d(С2,С1) 4) d(С1,С2) d(С1,С3) d(С3,С2).
Примером функции, отвечающей указанным требованиям, является расстояние Хаусдорфа. На практике используют и другие метрики, которые наилучшим образом учитывают специфику конкретной прикладной области.
Так как в задачах, решаемых в диссертационной работе, импликация 2), вообще говоря, не выполняется, вводится понятие квазиметрики, для которой выполняются следующие условия:
1) d(С1,С2) / 2) d(С1,С2) 0 С1 С 3) d(С1,С2) d(С2,С1) 4) d(С1,С2) d(С1,С3) d(С3,С2).
Для расчета расстояния между точкой x и классом C1 можно воспользоваться расстоянием Махаланобиса dM (x,С1) (x x)T S11(x x) или Евклида-Махаланобиса dE M (x,С1). При этом второй точкой служит Cx1 j jx Cцентр класса, представленный вектором средних значений, где Cx1 j C1 - мощность класса, - элемент класса C1.
Пусть точку x надо отнести к одному из двух классов C1,C2, а также измерить расстояния между классами. Построим матрицы ковариаций S1,S2,S3 классов C1,C2,C3 соответственно. Объединенная матрица ковариаций для классов C1,C2 может быть задана как сумма S1,2 S1 S2, (есть и другой способ объединения матриц ковариаций, например, ni S1,2 (S1 S2), - число элементов класса Ci ), а для классов n1 n2 C1,C2,C3 соответственно S1,2,3 S1 S2 S3. Расстояние dM (Ci,C ) j удовлетворяет, так же, как и расстояние Евклида, условиям: d (Ci,Cj ) 0, Ci Cj d (Ci,Cj ) и является симметричным.
Теорема 2.1. Расстояния dM (x,Ci ), dM (Ci,Cj ) (xC,C Ci Cj ) являются квазиметриками.
Для доказательства теоремы достаточно показать, что dM (x,C2 ) dM (C2,C1) dM (C1, x), dM (C1,C2) dM (C1,C3) dM (C3,C2).
Доказательство осуществляется по аналогии с доказательством Теоремы 1.1.
Таким образом, объединение частных матриц ковариаций обеспечивает выполнение свойств квазиметрики для функций Махаланобиса (а также Евклида-Махаланобиса) в случае измерения межклассовых расстояний.
Рассмотрим следующую задачу практически важную для кластеризации.
Задача размещения ядер кластеров формулируется следующим образом:
p как расположить n точек в -шаре радиуса r, чтобы сумма расстояний между ними была максимальна [4].
Решение задачи является предметом актуальных исследований и лежит в основе предагаемого в диссертации геометрического размещения кластеров.
Теорема 2.2. Пусть mi Rp (i 1,2,...,n) - точки, лежащие в p -шаре K(r) r S K(r) d(mi, mj) - расстояние между точками mi и радиуса, -граница шара, mi/ S (i 1,...,n), mj. Тогда существуют точки такие что d(mi, mj ) d(mi/, m/ ).
j 1i jn 1i jn Таким образом, первоначальное распределение центров кластеров можно свести к задаче размещения n точек на поверхности шара.
Приведем несколько определений.
p mi (i 1,2,...,n) Определение 2.1. Распределение точек на сфере в R называется равномерным, если точки представляют собой вершины правильных многогранников, описанных сферой.
Определение 2.2. Распределение mi (i 1,2,...,n) точек на сфере радиуса Rp mi r в (n p) называется равномерным, если для любой точки p mjp d(mi,mjp ) const n, p,r существует других точек таких, что.
p R Определение 2.3. Распределение mi (i 1,2,...,n) точек на сфере в называется квазиравномерным, если оно минимизирует потенциальную энергию системы равных зарядов, размещенных в этих точках (по Д.Томсону).
Из определения 2.1 следует, что количество решений задачи ограничено числом правильных многогранников. Определение 2.2. не охватывает случаи, когда (n p), а также приводит к трудностям построения алгоритма вычисления координат равномерно расположенных точек.
Выдвинем следующую гипотезу о квазиравномерности.
d(mi, m ) Гипотеза. Выражение принимает наибольшее значение в j 1i jn p случае, когда точки mi квазиравномерно расположены на границе -шара - S.
p К сожалению, доказательство Гипотезы для -шара, вызывает затруднения, поэтому предлагается рассмотреть некоторые частные случаи, решение которых имеет самостоятельное и важное прикладное значение.
1. Покажем, что данная гипотеза справедлива для плоского случая.
Лемма 2.1 (о размещении центров кластеров в круге) [1]. Пусть mi (i 1,2,...,n) - точки, лежащие на границе L круга K(r) радиуса r, mi mj. d(mi,m ) d(mi,mj ) - расстояние между точками и Выражение j 1i jn mi принимает наибольшее значение в случае, когда точки L квазиравномерно расположены на границе круга.
2. Рассмотрим случай трехмерной сферы.
mi (i 1,..,4) Лемма 2.2. Пусть - точки, лежащие на трехмерной сфере.
d(mi, mj) Выражение принимает наибольшее значение в случае, когда 1i jmi точки соответствуют вершинам правильного тетраэдра.
Леммы 2.1 и 2.2 составляют важные, хотя и частные результаты, которые подтверждают Гипотезу.
Квазиравномерное размещение точек имеет практическое решение только для некоторого количества точек (2,3,4,6,12) на 3-х мерной сфере (задача Томсона).
Третья глава посвящена вопросам построения методов кластерного анализа. Модельная задача коммивояжера на основе сети Кохонена рассматривается как первый этап задачи кластеризации, вторым этапом которой является разбиение на классы. Разработан метод решения задачи бинарной классификации на основе алгоритма варьирования размерности признакового пространства.
Метод кластерного анализа, основанный на сетевой модели Для решения задач геометрической кластеризации и классификации предложена вычислительная схема на основе алгоритма модифицированной искусственной нейронной сети (ИНС) Кохонена с набором метрик (Евклида, Махаланобиса, Евклида-Махаланобиса) и возможностью выбора способа начального размещения ядер кластеров, в том числе равномерного. Задача кластеризации k-means с введением набора метрик формулируется в следующем виде [7]:
k (xi )T S (xi ) min j j, j1 i:xiС j C nj где j xi - nj i:xiC, k число кластеров, j - j -й кластер, - число j элементов j -о кластера, E, для метрики Евклида, S, S для метрики Махаланобиса (S матрица ковариаций) S E, для метрики Евклида Махаланобиса.
Работа ИНС состоит из алгоритма формирования кластеров (обучения) и алгоритма распознавания. В качестве полигона для проверки качества сетевой модели выбрана задача о коммивояжере, которая с учетом выбранной схемы равномерного размещения кластеров служит этапом решения задачи геометрической кластеризации. На рис.2 приведена визуализация результатов некоторых итераций решения задачи коммивояжера.
Рисунок 2 - Этапы решения задачи коммивояжера Метод бинарной классификации Задача бинарной классификации в пространстве Rn может быть сведена к двумерной геометрической задаче (пространство R2 ) на основе понижения степени пространства признаков. Разработан специальный метод, основанный на снижении размерности n -мерного пространства признаков до двумерного, построении разделяющей гиперплоскости и ее обратном отображении в n -мерное пространство, что обеспечивает удобство решения задачи классификации непосредственно в системе исходных признаков.
Рассмотрим основные этапы решения задачи.
1. Предварительное преобразование пространства признаков и условий задачи в новую систему координат на основе метода главных компонентов (МГК). Преобразование предполагает выполнение следующих действий:
а) Построение матрицы ковариаций S размерности n n по табличным данным обучающей выборки.
b) Определение собственных чисел (1,...,n) матрицы S.
2. Преобразование условий исходной задачи путем пересчета входных векторов Wi (xi1,..., xin ), в вектора Vi (yi1,..., yin), (i 1,...,.m) новой системы Y ( y1,..., yn ).
признаков Формирование новой таблицы, содержащей множество векторов V V,...,V пространства Rn. Пересчет выполняется 1 m следующим образом: ViT A WiT, (i 1,...,.m).
(xi, xj ) 3. Выбор из таблицы двух признаков, соответствующих двум (i,j ) наибольшим собственным числам и построение неравенств задачи Rбинарной классификации в пространстве.
4. Построение разделяющей гиперплоскости или, при необходимости, k B (b1,b2,...,bp) комитета гиперплоскостей, где bk (b1k,b2 ), k 1,..., p, p / количество членов комитета и решающей функции F (), классифицирующей объект , 1,...,m R в пространстве :
p / F () (3.1) sign(V (),bi) i5. Восстановление разделяющей гиперплоскости или комитета Rn большинства в пространстве :
а) включим дополнительно двухкомпонентный вектор (i. ), j определяющий коэффициенты разделяющей гиперплоскости или гиперплоскости из комитета, увеличив тем самым количество строк таблицы до m 1, и восстановим его недостающие элементы в Rn.
Для этого предлагается модифицированный метод восстановления табличных данных ZET. Используем в качестве компетентных векторов расширенной таблицы пару заполненных векторов-столбцов с номерами (i, j). Пусть включенная строка имеет пустое поле в столбце k и i, j заполненные поля в столбцах ( k i, j ). Находим значения модулей i, j коэффициентов корреляции векторов-столбцов с номерами со столбцом k, обозначаемых как (Bk, Bi ), (Bk, Bj ). Коэффициент корреляции векторов (B1, B2) B1 и B2 вычисляют по формуле (B1, B2) . Используя пару B1 Bкомпетентных векторов-столбцов с номерами i, j и данный k -й столбец, содержащий пробел, восстанавливаем значение элемента k, например, следующим образом:
i k (Bk, Bi) kj (Bk, Bj ) k . (3.2) (Bk, Bi) (Bk, Bj ) Процедуру восстановления (3.2) повторим для всех векторов, имеющих незаполненные элементы в дополнительной строке.
b) Восстановленную строку в системе координат Y отобразим в систему координат X, решая обратную задачу:
T xi A1biT (3.3) Предложенный подход позволяет проводить целенаправленные действия (3.1)-(3.3), обеспечивая отсутствие неопределенности в выборе параметров преобразования.
В четвертой главе представлены экспериментальные исследования качества алгоритмов и методов кластерного анализа слабоструктурированных данных на основе полученных теоретических результатов и разработанных программных инструментальных средств.
Рассмотрены алгоритмы решения задач раздельной и совместной кластеризации и классификации текстовой и графической информации.
Разработано программное обеспечение для выполнения кластерного анализа изображений и текстов.
Общая схема кластерного анализа:
выделение информативных параметров: извлечение индекса текста и дескрипторов изображений (интегральных параметров); поиск локальных объектов (букв, лиц, самолетов и т.д.). Фильтрации с целью уменьшения числа объектов типа шум;
геометрическая кластеризация с использованием моделей и инструментов первоначального размещения ядер кластеров;
раскладка потока текстовых документов и изображений на основе созданных кластеров и методов классификации.
Экспериментальные исследования на серии полутоновых снимков показали преимущество квазиметрики Евклида-Махаланобиса по полноте распознавания графических объектов в сравнении с метрикой Евклида.
Эксперименты по кластеризации документов (на выборке 1000 документов, проанализированных экспертом) показали, что метрика ЕвклидаМахаланобиса дает улучшение качества кластеризации на 15-20% по сравнению с метрикой Евклида.
Результаты бинарной классификации изображений кристаллизованных капель биологической жидкости показали, что применение квазиметрики Махаланобиса позволяет практически безошибочно выявлять факт наличия заболевания. Эксперименты по одновременному обнаружению слов и изображений на скан-копии документа показали достаточно надежное выделение и распознавание целевых объектов. При этом часть классификаторов настраивается на анализ текстовой части, а другая на графические элементы. Разработанные инструментальные средства могут быть применены для решения широкого класса задач (кластеризация текстов, распознавание графических образов, поиск целевых регионов на картах и др.). Сводные количественные и качественные результаты, полученные на основе проведенных исследований, представлены на рис. 3.
Рисунок 3 - Результаты экспериментальных исследований Заключение содержит основные результаты и выводы по диссертационной работе.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ 1.Доказаны утверждения о том, что функции Махаланобиса и ЕвклидаМахаланобиса являются квазиметриками. Использование набора метрик в задачах геометрической кластеризации и классификации позволяет решать задачи измерения расстояний как внутри, так и между классами, а также между произвольной точкой и классами.
2. Выдвинута гипотеза о квазиравномерности размещения точек на границе p -шара при выполнении критерия максимального суммарного расстояния между точками, которая частично подтверждена теоремами о равномерном размещении точек в круге и четырех точек на трехмерной сфере (условию равномерности соответствует правильный тетраэдр). Это позволяет решать проблему первоначального размещения ядер кластеров, в том числе для задачи коммивояжера.
3. Доказана теорема о размещении ядер кластеров в p -мерном шаре при выполнении критерия максимального суммарного расстояния между ядрами.
4. Разработан метод кластерного анализа, основанный на применении модифицированной нейронной сети Кохонена с набором метрик и способов начального размещения ядер кластеров, что позволяет увеличить точность эвристического решения задачи коммивояжера, а также классификации изображений и аннотирования текстов.
5. Разработан метод кластерного анализа, рассчитанный на бинарную классификацию, основанный на варьировании пространства признаков и процедуре восстановления неизвестных значений таблицы признаков.
6. Разработаны алгоритмы и экспериментальное программное обеспечение для кластерного анализа слабоструктурированной информации.
Основные научные результаты диссертации опубликованы в следующих работах:
работы из списка, рекомендованного ВАК РФ:
1. Атаманов В.В., Козачок М.А., Трушков В.В., Хачумов М.В. Выбор первоначального расположения кластеров в нейронной сети Кохонена // Нейрокомпьютеры: разработка и применение. - 2009. - №1. - С. 73-76.
2. Хачумов М.В. Задача кластеризации текстовых документов // Информационные технологии и вычислительные системы. - 2010. - № 2. - С. 42-49.
3. Толмачев И.Л., Хачумов М.В. Бинарная классификация на основе варьирования размерности пространства признаков и выбора эффективной метрики // Искусственный интеллект и принятие решений. - 2010. - № 2. - С 3-10.
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. Фраленко В.П., Хачумов М.В. Классификация на основе аппарата нейронных сетей с применением метода главных компонент и комитета большинства // Сборник статей Третьей Всероссийской научной конференции Нечеткие системы и мягкие вычисления НСМВ-20(Волгоград, 21-24 сентября 2009 года). - Волгоград: Изд-во Волгоградского государственного технического университета, Т. 2, 2009. - С. 70-79.
9. Хачумов М.В. Применение нейронной сети и расстояния ЕвклидаМахаланобиса в задаче бинарной классификации // Сборник материалов II Международной научно-практической конференции Наука и современность - 2010 (Новосибирск, 16 апреля 2010 года). - Новосибирск:
Изд-во СИБПРИНТ, Часть 3, 2010. - С. 82-86.
10. Хачумов М.В. О проблеме интеграции анализа текстовых данных и графических образов для задач поиска и кластеризации документов // Сборник трудов Девятой международной научно-практической конференции Исследование, разработка и применение высоких технологий в промышленности (Санкт-Петербург, 22-23 апреля 2010 года). - СПб: Издво Политехнического университета, 2010, Т.3. - С. 157-160.
11. Хачумов М.В. О выборе метрики для решения задач классификации и кластеризации // Материалы Первой всероссийской научной конференции с международным участием (SASM-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] - сетевой алгоритм решения задачи коммивояжера.
Хачумов Михаил Вячеславович РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ КЛАСТЕРНОГО АНАЛИЗА СЛАБОСТРУКТУРИРОВАННЫХ ДАННЫХ Доказана теорема о том что функции Махаланобиса и Евклида- Махаланобиса являются квазиметриками, что может быть использовано для решения задач классификации.
Доказана теорема о размещении ядер кластеров на p -мерной сфере при выполнении критерия максимального суммарного расстояния между ядрами.
Теорема позволяет решать задачи первоначального размещения ядер кластеров.
Доказана лемма о равномерном размещении ядер кластеров в круге.
Предложен метод геометрической кластеризации, основанный на применении модифицированной нейронной сети Кохонена с набором метрик и способов начального размещения ядер кластеров.
Разработан метод бинарной классификации, основанный на варьировании пространства признаков и модифицированном алгоритме 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>
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>
The algorithms and experimental software for cluster analysis of semistructured information is developed.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям