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

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

Бирюков Андрей Сергеевич

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

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

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

Москва 2005

Работа выполнена в Вычислительном Центре им. А.А. Дородницына Российской Академии Наук

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

доктор физико-математических наук В.В. Рязанов

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

доктор технических наук Л.М. Местецкий кандидат физико-математических наук Н.В. Песков

Ведущая организация:

Московский Физико-Технический

Институт (государственный университет)

Защита состоится «_ 2005 г. В часов на заседании

диссертационного совета Д002.017.02 Вычислительного центра им А.А. Дородницына РАН по адресу: 119991, Москва, ул. Вавилова, 40.

С диссертацией можно ознакомится в библиотеке Вычислительного Центра им. А.А. Дородницына РАН

Автореферат разослан «-//» Н 2005 г.

Ученый секретарь диссертационного совета доктор физико-математических наук " В.В. Рязанов

ч-н

г^г

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

Кластерный анализ является важным разделом интеллектуального анализа данных. Значительный вклад в развитие теории кластерного анализа внесли С.А. Айвазян, Р. Гонсалес, Н.Г.Загоруйко, Л.Г. Малиновский, Л.Д. Мешалкин, Ш.Ю. Раудис, Г.С. Себестиана, Дж. Ту. В настоящее время существует несколько основных подходов к решению задачи кластеризации при заданном числе кластеров: основанные на поиске оптимальных разбиений, иерархической группировке, идеях динамических сгущений, восстановлении плотностей компонент по заданной смеси, теории графов, эвристические алгоритмы, и другие. Основные проблемы их практического применения связаны с трудоемкостью и многоэкстремальностью оптимизационных задач, нахождением вырожденных решений, сложностью сравнения и интерпретации решений, полученных различными алгоритмами.

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

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

Цель работы.

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

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

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

А(/т) = К(Ш (Уж)),

где - таблица признаковых описаний объектов, Я - оператор,

переводящий таблицу признаковых описаний в матшщу-_^денок__степени

Р0(..,, -'.ЧхиьнАЯ

"(■ К А Рг

близости объектов к каждому из кластеров, а г - решающее правило. Данная форма представления является аналогом записи стандартных алгоритмов распознавания в алгебраической теории распознавания как произведения распознающего оператора и решающего правила (Ю.И. Журавлев, Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Кибернетика. 1977. N4. С. 5-17.). Получена верхняя оценка вариации функционала качества коллективного решения и разработан эффективный алгоритм комитетного синтеза, основанный на последовательной минимизации данных оценок.

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

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

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

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

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

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

Практическая ценность.

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

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

Реализация результатов.

Результаты исследований в виде алгоритмов и программ получены по планам грантов РФФИ №№ 99-07-90120, 99-07-90390, 00-01-00650, 02-0108007 инно, 02-07-90134, 02-07-90137, 03-01-00580, 04-01-08045 офи, НШ 1721.2003.1, по Программе № 17 фундаментальных исследований Президиума РАН «Параллельные вычисления и многопроцессорные вычислительные системы», в проектах ИНТАС №02-00370, 02-00626.

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

Материалы, изложенные в диссертации, прошли апробацию на:

• 5-ой Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (2000 год, г. Самара);

• 10-ой Всероссийской конференции «Математические методы распознавания образов» (2001 год, г. Звенигород, Московская область);

• 6-ой Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (2002 год, г. Великий Новгород);

• 11-ой Всероссийской конференции «Математические методы распознавания образов» (2003 год, г. Пущино, Московская область);

• 7-ой Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (2004 год, г. Санкт-Петербург);

• The 6th German-Russian Workshop "Pattern Recognition and Image Understanding" (Novosibirsk, 2003)

Структура и объем работы.

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

Результаты, выносимые на защиту.

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

2. Методы синтеза коллектива базисных алгоритмов, основанных на восстановлении компонент смеси по выборке объектов.

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

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

5. Программная система интеллектуального анализа данных, распознавания и прогноза «РАСПОЗНАВАНИЕ» (структура, интерфейс пользователя, ядро программной системы, методы кластерного анализа).

Содержание работы.

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

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

Исследуется выборка Б = {х1,...,хт}, заданная таблицей признаковых описаний Jm(S).

Определение: Информационные матрицы / = Цо^|| / и Г = Ца^| а , а'и е {0,1, А}, называются эквивалентными, если они равны с точностью до перестановки столбцов.

Произвольная матрица ||а,у определяет класс ^ всех

эквивалентных ей матриц. Результат кластеризации £ на / кластеров К1,...,К1 записывается в виде класса к|а!/||тх,) эквивалентных

информационных матриц / = |ау||^, где ау е{0,1,А}, ац =1, если х,еК;> а у =0, если х, £ К], ац = А соответствует отказу от зачисления х1 в один из кластеров.

Рассматривается множество алгоритмов кластеризации, представимых в виде:

ЖУж) = К(гЛ(Уя)). Оператор /?(Ут) вычисляет по Зт числовую матрицу оценок степени близости объектов к каждому из кластеров:

Оператор г называется решающим правилом. Он переводит матрицы оценок в информационные матрицы:

^и-кь-'-

Задача построения оптимального коллективного решения на основе кластеризации выборки 5 алгоритмами А1,..., А" решается в два этапа.

1. Построение отображения Уи на множество классов эквивалентности

Кс = (ф9|и а9 е {0,1,А}, / = 1,...,/», у = 1,...,/.

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

Определение: Оператор В над множеством матриц оценок у = 1,...,п

называется сумматором, если

<к1Ь{)нк1Ь'где ь=~t%> . w.

Определение: Комитетным синтезом информационной матрицы / = на

таблице признаковых описаний выборки объектов Jт называется ее вычисление I = r(B(Jm)) при условиях: В - сумматор, г - решающее правило.

Определение: Числовая матрица ^ называется контрастной, если ßv е{0,1}, i = l,..., т, 7 = 1,...,/.

Далее используется следующая метрика на множестве матриц оценок:

pWM^fj^bl-bl |.

/=1 у-1

Определение: Мерой качества Фа(В) матрицы оценок 5 = называется

величина Фа(В) = p(B,G), где G - множество всех контрастных матриц

размера /их/. Матрица В* называется оптимальной по критерию Фа(В) на

множестве матриц {В}, если ФС(В')= ттФс(В).

Для построения оптимального комитетного решения необходимо для

каждой матрицы \ßl\ t, v = lвыбрать такую нумерацию столбцов,

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

М = {\,2,...,т}

Х) ={i\by = Y) =М\Х}, у=1,...,/.

Пусть Jtv = , v = l,...,«, - некоторая перестановка чисел

я0 ={1,2,...,/}, а ж = {л1,...,л"} - набор перестановок. В соответствии с набором перестановок п матрица оценок будет вычисляться следующим образом:

вЧКЬгде b:j = bij(x) = ±ß;J\ß;; =/г;.

V=I

Теорема 1.2: Для произвольного набора перестановок я = {жх,...,яп} изменение значения функционала качества матрицы оценок В удовлетворяет следующему ограничению:

АФ < £ Д„ , где Д„ = 2£ " 2£ £ /Г .

п

Таким образом, условие <0 является достаточным для

уменьшения функционала качества при переходе от Ьу{ж°) к ^ =Ь'у(ж). Первая сумма в А„ соответствует текущей матрице оценок, для которой вычислены X , , у = 1,...,/, и не зависит от к. Вторая сумма соответствует

новой матрице оценок, задаваемой набором перестановок к. Следовательно, для минимизации Д^ требуется найти:

/

л-" = англах,

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

Далее в главе рассматривается подход к построению коллективного решения задачи кластерного анализа, основанный на повторной кластеризации результатов традиционными методами. Пусть в результате кластеризации выборки 5" набором алгоритмов А1,..., А", получены информационные матрицы а1' , а" е {0,1}, г = 1,...,т, 7 = 1,...,/,

II ) Н/ях/хя ^

У = 1,...,«.

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

II Н/хп

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

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

п ^ 11 тх/

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

Рп - Ри -Ж,

хтР1х - Ры-

Для построения начального приближения переставим столбцы матриц

таким образом, чтобы условие «в каждой строке максимальное

значение Д^ стоит в столбце с номером соответствующего кластера»

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

где с; вычисляются по элементам матрицы /О . В результате решения

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

Во второй главе рассматриваются вопросы построения коллективного решения задачи кластерного анализа, основанного на восстановлении компонент смеси по выборке объектов. Пусть имеется такая совокупность т объектов одной и той же природы 5 = {х,,...,хт}, что каждый ее элемент 1 = 1,.,.,т, можно описать набором из и различных количественных признаков х> = (х,,,..., хм), х1 еЯ", где Я" - и-мерное евклидово пространство. Задача состоит в выделении кластеров в данной выборке -определение их состава и некоторых характеристик. О структуре задачи известно следующие:

1. Выборка объектов состоит из известного числа / кластеров.

2. Вид условных по кластерам плотностей р(х | , ), известен,

3. Априорные вероятности Р{со]) для каждого кластера неизвестны,

4. Значения I параметрических векторов Э1 - неизвестны.

5. Признаки являются попарно независимыми.

Предполагается, что объекты получены выделением состояния природы со] с вероятностью Р(о);) и последующим выделением х в

соответствии с вероятностным законом р(х \ со^6). Таким образом, функция

плотности распределения объектов определяется как:

—>тах

¡-1

1 I

=1, =1,

.=1 у-1

*„2 0,

К* I в) = £ р(х | , в1 )Р{т1), где 0 = (0,,..., 0,). (1)

Задача состоит в нахождении значений неизвестных параметров в = (£?,,и априорных вероятностей кластеров Р(а>;), } = 1,...,/, таких,

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

Можно показать, что если функция плотности распределения выборок р(х\в) является суммой плотностей компонент, подчиняющихся нормальному закону распределения значений признаков объектов (с попарно неравными векторами параметров в] и ненулевыми априорными вероятностями Р(а/)), то такое представление является единственным с

точность до переобозначения кластеров.

В работе рассматривается задача поиска параметров одномерных функций плотности распределения объектов внутри кластеров по заданной смеси объектов из этих кластеров. Область значения проекции выборки на некоторый признак разбивается на N интервалов равной длины: [хо»*»]»^»^]»—»(*Аг-1»*уу]- Далее строится функция рэ(х) - эмпирическая функция плотности распределения смеси I кластеров для данного признака. Данная функция задается в виде конечного набора ее значений на интервалах [х0, х, ], (х15 х2 ],..., , % ], рэ(х) на интервале [хм,х,] равна доле объектов выборки, значения признака которых попали в 1-ый интервал. Требуется

найти ее наилучшее приближение в виде ^Р1р1(х\9,), где р1(х\в1) -

функция плотности распределения объектов внутри кластера /, известная с точностью до значений вектора параметров в,, а Р1 - неизвестная априорная вероятность i -ого кластера.

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

Составим систему из N уравнений, которая является, вообще говоря, несовместной.

Тогда задачу восстановления компонент смеси запишем в следующем виде:

1-1

р, х р, (х[)+...+р1 х />,(*;>=рэ{х\)

х Рх&ы ) + ..- + Р,х ) = Рэ(х'„ )

при ограничениях 0 ^ Р, < 1, У = 1,..., /, ]Г Р1 = 1. Традиционные

1=1

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

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

Теорема 2.1: Пусть дана смесь функций плотностей распределения объектов / кластеров:

/

р(х\в) = £р,Р,(х1а.А)> где

1=1 О ,х<а, 1

РЛх\а„Ь,) =

Ъ,-а,

,а, <х<Ь,, 1 = 1,...,/,

О ,х>Ь1

а, * а &Ьк#Ьп для любых У, _/, к, У = 1,..., 1. о Р

, длялюбыхУ* j, /,у' = 1,...,/.

Ь,-а, Ъ] -а]

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

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

Тогда многомерная плотность кластера а>] имеет вид:

где а" = , и = 1,...,и есть некоторая перестановка чисел (1,...,/).

Если кластеру а>] соответствует набор тогда априорная

вероятность Р{<о]) кластера со] может быть оценена по априорным

вероятностям Ру{(оУ), V = 1,...,и. В качестве подобной оценки будем

>

использовать величину:

P(coSj) = njp4w )..J>4a> ) = П(Pv K; -

* v=!

По формуле Байеса апостериорная вероятность кластера а} оценивается как

p(x\(o 0s )P(cos ) P(a>j\x,0Sj) =-'S'

Согласно байесовскому решающему правилу минимум ошибки классификации достигается при применении решающего правила:

xecOj, если Я(й)у \x,9Sj) = max Р(а>, | х,вй ). (3)

Байесовское решающее правило (3) может быть преобразовано к эквивалентному виду:

п п

х е Wj, если YudL- = "i^IXa- »где 0 - -1' =0, maxd" = 1.

" > ' P.v.r li.v.T

Построенные матрицы оценок могут быть использованы далее

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

В третьей главе описан алгоритм кластеризации, основанный на покрытии выборки гипершарами. Рассматривается задача кластеризации на I кластеров. Имеется выборка признаковых описаний объектов X = {х1,...,хт},

х, =(*,,,дг,2,...,*,„). Пусть заданны I векторов >»,,...,у1 е Л", которые считаются центрами «сгущения» выборки и интерпретируются как центры кластеров.

Вводятся в рассмотрение специальные семейства вложенных гипершаров. Пусть р- некоторая метрика в пространстве Я". Упорядочив по возрастанию значения расстояний от у1 до всех элементов из Х = {х,,...,хт}, получим монотонно возрастающие последовательности гх < г2 <... < гк^

к, <т, / = 1,...,I. Через {Л] = {х:р(х,у1) < гу.},/ = 1,...,к1}, обозначается множество вложенных гипершаров с центрами в у,. Множество данных гипершаров покрывает все объекты выборки. Обозначим пц = |{дг, : х, е }| -

число объектов выборки, принадлежащих гипершару Щ.

Рассматривается следующая задача: «Найти 1 гипершаров покрывающих все объекты из X = {х,,...,хт} и имеющих

1

минимальную величину ^ ».

г=1

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

л

(5)

(6)

г, €{0,1}.

(7)

1, Л, С ,

0, иначе.

(8)

Показано, что для коэффициентов целевой функции (4) и системы ограничений (5) выполнены неравенства п1} < п1 у+1, с' <с'7+|. Из свойств

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

Определение: Множество гипершаров называется полной системой гипершаров для задачи (4-8), если к1 =т для всех г = 1,...,/. Утверждение 3.3: Для полной системы гипершаров всегда существует решение задачи (4-8), для которого /(г*) < га + / -1.

Утверждение 3.4: Оптимальное решение задачи (4-8) на базе полной системы гипершаров всегда содержит не более чем / -1 объектов принадлежащих нескольким гипершарам.

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

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

На прилагаемых графиках (для случая 10 кластеров) по оси «X» откладывались количество признаков, которые имела кластеризуемая выборка, а по оси «У» количество правильно классифицированных элементов в процентах.

задачи (4-8) выполняются равенства: г* = 1, / = 1,2,..., /.

- Метод максимального правдоподобия

- Комигетный синтез

- Метод коллективных к-средних__

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

МО Метод маю имальиого правдоподобия 100 Метод коллвкттных к-средмих

И Г I ! Г П 90 М 70 :

I

!

9« г 0 25 М Зв « 43 96 К 20 25 30 36 40 45 50 55

Разработанные алгоритмы и программы были апробированы на реальных данных из различных предметных областей.__

Название задачи Максимальное правдоподобие Коллективные к-средних Комитетный метод

Задача одобрения кредита 73% 75% 80%

Классификация сортов вина 90% 92% 90%

Задача диагностики рака груди Отказ от кластеризации 95% 86%

В пятой главе рассматривается универсальная программная система интеллектуального анализа данных, распознавания и прогноза РАСПОЗНАВАНИЕ. В основу требований к системе положены идеи универсальности и интеллектуальности. Под универсальностью системы понимается возможность ее применения к максимально широкому кругу задач (по размерностям, по типу, качеству и структуре данных, по вычисляемым величинам). Под интеллектуальностью понимается наличие

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

В рамках системы РАСПОЗНАВАНИЕ разработана библиотека программ, реализующих следующие методы распознавания и кластерного анализа: алгоритм вычисления оценок, линейный дискриминант Фишера, линейная машина, К ближайших соседей, двумерные линейные разделители, алгоритм голосования по логическим закономерностям, метод опорных векторов, статистически взвешенные синдромы, алгоритм голосования по тупиковым тестам, нейросетевой алгоритм, метод локальной оптимизации, итеративная оптимизация, иерархическая группировка, метод к внутригрупповых средних, ЕМ-алгоритм.

Создана библиотека методов построения коллективных решений на базе различных наборов методов распознавания или кластерного анализа: метод Байеса, «области компетенции», комплексный комитетный метод, выпуклый стабилизатор, «шаблоны принятия решений», динамический метод Вудса, комитетный синтез решений задач кластерного анализа, коллективные к-внутригрупповые средние.

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

Публикации по теме диссертации.

1. А.С.Бирюков. "Об одном методе поиска алгебраических корректоров при решении задачи распознавания образов по прецедентам", Труды 5-ой международной конференции "Распознавание образов и анализ изображений: новые информационные технологии", том 1, стр. 13-15, 2000.

2. A. S. Biryukov. "A Method for Finding Algebraic Correctors in Precedent-Based Image Recognition", Pattern Recognition and Image Analysis, Vol. 11,No. 1,2001, pp. 11-12,2001.

3. А.С.Бирюков, А.П.Виноградов, В.В.Рязанов, И.В.Рязанов. "О восстановлении некоторых плотностей кластеров по эмпирическим плотностям смеси", Труды 5-ой международной конференции "Распознавание образов и анализ изображений: новые информационные технологии", том 1, стр. 16-20, 2000.

4. A.S.Biiyukov, A.P.Vinogradov, V.V.Ryazanov, I.V.Ryazanov. "Restoration of some cluster densities by empirical densities of mixtures", Pattern Recognition and Image Analysis, Vol. 11,No. 1,2001,pp. 13-15,2001.

5. A.C. Бирюков. "Решение задачи таксономии, основанное на анализе одномерных признаковых покрытий", Доклады 10-ой Всероссийской конференции "Математические методы распознавания образов", стр. 911,2001.

6. А.С. Бирюков. "Восстановление одномерных плотностей кластеров по эмпирическим плотностям смеси при помощи генетического подхода", Труды 6-ой международной конференции "Распознавание образов и анализ изображений: новые информационные технологии", том 1, стр. 66-70,2002.

7. Yu.I. Zhuravlev, V.V. Ryazanov, O.V. Senko, A.S. Biryukov, D.P. Vetrov, A.A. Dokukin, D.A. Kropotov, N.N. Katerinochkina, A.S. Obukhov, M.Yu. Romanov, I.V. Ryazanov, F.B. Chelnokov. The Program System For Data Analysis "RECOGNITION (LOREG)" // Proc. of the 6th German-Russian Workshop "Pattern Recognition and Image Understanding", Novosibirsk, 2003, pp. 255-258.

8. Ю.И. Журавлев, B.B. Рязанов, O.B. Сенько, А.С. Бирюков, Д.П. Ветров, А.А. Докукин, Д.А. Кропотов, Н.Н. Катериночкина, А.С. Обухов, М.Ю. Романов, И.В. Рязанов, Ф.Б. Челноков. Разработка универсальной программной системы интеллектуального анализа данных, распознавания и прогноза // Труды 11 Всероссийской конференции "Математические методы распознавания образов", Москва, 2003, стр. 311-314.

9. Yu.Zhuravlev, V.Ryazanov, O.Senko, A.Birykov, D.Vetrov, A.Dokukin, N.Katerinochkina, D.Kropotov, A.Obukhov, M.Romanov, LRyazanov, I.Tolstov, F.Chelnokov. Universal Software System for Recognition, Data Mining and Forecasting "Recognition". // Proc. of 7th International Conference "Pattern Recognition and Image Analysis: New Information Technologies", Saint-Peterburg, 2004, pp. 578-581.

10.Yu.I. Zhuravlev, V. V. Ryazanov, О. V. Senko, A. S. Biryukov, D. P. Vetrov, A. A. Dokukin, N. N. Katerinochkina, D. A. Kropotov, A. S. Obukhov, M. Yu. Romanov, I. V. Ryazanov, I. V. Tolstov, and F. B. Chelnokov. "RECOGNITION: A Universal Software System for Recognition, Data Mining, and Forecasting", Pattern Recognition and Image Analysis, Vol. 15, No. 2,2005, p. 476.

11.Yu.I. Zhuravlev, V.V. Ryazanov, O.V. Senko, A.S. Biryukov, D.P. Vetrov, A.A. Dokukin, D.A. Kropotov. The Program System for Intellectual Data Analysis, Recognition and Forecasting. WSEAS Trans, on Information Science and Applications, V.2, N.l, 2005, pp.55-58.

Подписано в печать 27.10.2005 Формат 60x88 1/16. Объем 1 п.л. Тираж 100 экз. Заказ № 133 Отпечатано в ООО «Соцветие красок» 119992 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. 102

РЫБ Русский фонд

2007-4 2275

Получено 3 J — п

Введение

Глава 1. Коллективные решения задачи кластерного анализа

§ 1. Оптимальные комитетные решения, построенные по матрицам оценок

§2. Построение оптимальных комитетных решений задач кластерного анализа

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

§4. Взаимосвязь комитетного синтеза и подхода, основанного на повторной кластеризации

Глава 2. Коллективные решения задачи кластерного анализа на основе восстановления компонент смеси по выборке объектов

§ 1. Постановка задачи, идентифицируемость компонент

§2. Одномерная задача восстановления параметров смеси

§3. Алгоритмы решения задачи восстановления параметров смеси

§4. Оптимальные коллективные решения на множествах одномерных решений

§5. Практическая реализация алгоритмов решения задачи восстановления параметров смеси

Глава 3. Алгоритмы кластеризации, основанные на поиске оптимальных покрытий

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

§2. Свойства задачи построения покрытия

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

Глава 4. Результаты экспериментов

§ 1. Сравнительные эксперименты на модельных задачах

§2. Сравнительные эксперименты на реальных задачах

Глава 5. Универсальная программная система интеллектуального анализа данных, распознавания и прогноза РАСПОЗНАВАНИЕ

§ 1. Возможности системы РАСПОЗНАВАНИЕ

§2. Структура программы

§3. Практическое применение

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

Интенсивные исследования в области кластерного анализа продолжаются с 60-х годов 20-го века в ведущих научных организациях, учреждениях и университетах мира. К настоящему времени сформировалось несколько подходов в кластерном анализе. Один из первых научных коллективов в области кластерного анализа был образован в Новосибирске под руководством Н.Г.Загоруйко [9, 10]. Алгоритм ФОРЕЛЬ позволяет решать задачу кластеризации заданной выборки векторных признаковых описаний объектов с помощью следующей итерационной схемы. Фиксируется положительное число (радиус гипершара), некоторая метрика в пространстве признаковых описаний и произвольный эталон обучающей выборки. Определяется подмножество векторов, принадлежащих гипершару с центром в заданном эталоне, и вычисляется средний вектор по данному множеству векторов. Данный средний вектор принимается за центр нового гипершара. Далее процесс повторяется. Критерием останова является достижение ситуации, когда центры гипершаров на двух последовательных итерациях совпадают. Объекты, принадлежащие «конечному» гипершару принимаются за объекты первого кластера, они исключаются из обучающей выборки и процесс повторяется сначала. Найденные в итоге число кластеров (и сами кластеры) будут зависеть от выбора метрики, начальных эталонов, радиусов гиперсфер. Другая группа методов, разработанная данной научной группой, основана на поиске таких разбиений выборки, которые минимизируют некоторый эвристический функционал качества разбиения. Функционал качества определяется как результат попытки формализации тех принципов, которыми руководствуется неформально человек при кластеризации плоских выборок, имеющих некоторую кластерную структуру. В данном критерии объединяются такие естественные соображения как «метрическая близость объектов одного кластера», «удаленность объектов разных кластеров», «число объектов одного кластера не должно многократно превышать число объектов другого кластера», «близость к граничному объекту объектов других кластеров должна быть существенно меньше чем близость к некоторым соседям из «своего» кластера». Оптимальная кластеризация находится как разбиение, минимизирующее заданный критерий. При этом перебор вариантов возможных разбиений основан на различных разрывах построенного по выборке минимального покрывающего дерева [9,10].

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

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

Иерархические кластеризации строятся на последовательном объединении близких группировок (агломеративные процедуры) или расщеплении множеств объектов на более мелкие (делимые процедуры) [1].

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

В методе динамических сгущений, являющимся далеким обобщением метода к -внутригрупповых средних, «среди всех разбиений на / кластеров следует найти разбиение, относительно каждого кластера которого заданное «ядро» оказалось бы наиболее представительным» [79]. Существуют подходы, основанные на использовании теории графов и различные эвристические подходы (метод к-эталонов, метод взаимного поглощения, и другие) [80].

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

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

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

Теория синтеза коллективных комитетных решений задачи кластерного анализа, впервые была предложена в [2]. Согласно ей, сначала для кластеризации произвольных объектов независимо применяются некоторые алгоритмы А1,.,Ак. Далее результаты их применения специальным образом обрабатываются (решение оптимизационных задач на перестановках) и формулируется окончательное коллективное решение об отнесении объектов к одному из кластеров.

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

A(JJ = K(rR(Jm)), где Jm - таблица признаковых описаний объекта, R - оператор, переводящий таблицу признаковых описаний в матрицу оценок степени близости объектов к каждому из кластеров, а г - решающее правило. Данная форма представления является аналогичной записи алгоритмов распознавания в алгебраической теории распознавания [45, 56, 58]. Для данного общего случая вводятся определения операторов синтеза коллективных комитетных решений и критерии их качества. Получена верхняя оценка вариации функционала качества и разработан эффективный алгоритм комитетного синтеза, основанный на последовательной минимизации данных оценок.

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

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

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

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

Четвертая глава посвящена изложению результатов численных экспериментов. Эксперименты проводились на модельных и реальных практических задачах. В качестве модельных задач рассматривались смеси выборок, порожденные генератором случайных чисел согласно нормальному закону распределения и при гипотезе о статистической независимости признаков. Параметры распределений выбирались такими, чтобы точность решения задачи классификации с учителем на данных выборках была выше 99%. Обоснование применения смесей нормальных распределений для решения реальных задач кластерного анализа содержится в [12-14], где отмечается, что использование таких смесей только в качестве первой аппроксимации неизвестной функции плотности вероятности дает удовлетворительные результаты. Кроме того, известно существование реальных объектов в биологии, медицине, психологии, астрономии и других областях, распределение которых есть смесь нормальных распределений [15,16].

Идея применения конечных смесей нормальных распределений для решения задач распознавания развивалась в работах зарубежных и отечественных исследователей: Г.С. Себестиана, Дж. Ту, Р. Гонсалеса, Д.А. Хартигана, Т.В. Андерсона, Л.Д. Мешалкина, Л.Г. Малиновского, Ш.Ю. Раудиса и других [12,13,16-23].

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

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

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

1. распознавание (диагностика) ситуаций, явлений, объектов или процессов с обоснованием решений;

2. кластерный анализ и исследование структуры данных;

3. выявление существенных признаков и нахождение простейших описаний;

4. нахождение эмпирических закономерностей различного вида;

5. построение аналитических описаний множеств (кластеров) объектов;

6. нахождение нестандартных или критических случаев;

7. формирование эталонных описаний образов.

Разработки программных систем анализа данных активно ведутся в России и ведущих зарубежных странах. Прежде всего, это статистические пакеты обработки данных и визуализации (SPSS, STADIA, STATGRAPHICS, STATISTICA, SYSTAT, Олимп:СтатЭксперт Prof., Forecast Expert, и другие), в основе которых лежат методы различных разделов математической статистики - проверка статистических гипотез, регрессионный анализ, дисперсионный анализ, анализ временных рядов и др. Использование статистических программных продуктов стало стандартным и эффективным инструментом анализа данных, и, прежде всего, начального этапа исследований, когда находятся значения различных усредненных показателей, проверяется статистическая достоверность различных гипотез, находятся регрессионные зависимости. Вместе с тем статистические подходы имеют и существенные недостатки. Они позволяют оценить (при выполнении некоторых условий) статистическую достоверность значения прогнозируемого параметра, гипотезы или зависимости, однако сами методы вычисления прогнозируемых величин, выдвижения гипотез или нахождения зависимостей имеют очевидные ограничения. Прежде всего, находятся усредненные по выборке величины,- что- может- быть- достаточно- грубым представлением- об анализируемых или прогнозируемых параметрах. Любая статистическая модель использует понятия «случайных событий», «функций распределения случайных величин» и т.п., в то время как взаимосвязи между различными параметрами исследуемых объектов, ситуаций или явлений являются детерминированными. Само применение статистических методов подразумевает наличие определенного числа наблюдений для обоснованности конечного результата, в то время как данное число может быть существенно больше имеющегося или возможного. То есть в ситуациях анализа в принципе непредставительных данных, или на этапах начала накопления данных, статистические подходы становятся неэффективными как средство анализа и прогноза.

В последние годы появились узкоспециализированные пакеты интеллектуального анализа данных. Для данных пакетов часто характерна ориентация на узкий круг практических задач, а их алгоритмической основой является какая-либо одна из альтернативных моделей, использующая нейронную сеть, решающие деревья, ограниченный перебор, и т.п. [55]. Ясно, что подобные разработки существенно ограничены при практическом использовании. Во-первых, заложенные в них подходы не является универсальными относительно размерностей задач, типа, сложности и структурированности данных, величины шума, противоречивости данных и т.п. Во-вторых, созданные и «настроенные» на решение определенных задач, они могут оказаться совершенно бесполезными для других. Наконец, множество задач, представляющих интерес практическому пользователю, обычно шире возможностей отдельного подхода. Например, пользователю может быть важно иметь численную характеристику надежности некоторого прогноза, но «решающее дерево» ее не вычисляет. «Нейронная сеть» выступает в роли «черного ящика», предлагающего некоторый прогноз без его обоснования. Логические методы распознавания позволяют выявлять логические закономерности в данных и использовать их при прогнозировании, но при наличии линейных зависимостей между признаками и прогнозируемой величиной точность прогноза, сделанного «линейной машиной», может быть заметно выше.

Таким образом, на настоящем уровне развития методов решения задач анализа данных, представляется предпочтительным путь создания программных средств, включающих основные существующие разнообразные подходы. В данном случае повышаются шансы подбора из имеющихся алгоритмов такого алгоритма, который обеспечит наиболее точное решение интересующих пользователя задач на новых данных. Другим важным атрибутом систем анализа и классификации должно быть наличие средств автоматического решения задач распознавания и классификации коллективами алгоритмов. Действительно, стандартной ситуацией является наличие нескольких альтернативных алгоритмов или решений, равнозначных для пользователя. Для выбора из них одного наиболее предпочтительного не хватает информации. Тогда естественной альтернативой выбору является создание на базе имеющихся алгоритмов или решений новых, более предпочтительных. Теоретические основы практической реализации идеи решения задач анализа данных коллективами алгоритмов были разработаны в ВЦ РАН в рамках алгебраического подхода для решения задач распознавания (логическая и алгебраическая коррекция алгоритмов) в 1976-1980 [45, 56, 57] и комитетного синтеза классификаций для задач кластерного анализа (автоматической классификации) в 19811982 годах [49, 50]. Позднее появились исследования в данной области и в других странах.

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

Заключение

Приведем перечень основных результатов диссертационной работы.

1. Обобщен метод комитетного синтеза для алгоритмов кластерного анализа, представимых в виде:

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

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

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

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

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

6. Разработана структура, интерфейс пользователя и ядро программной системы для решения задач распознавания, кластеризации и прогноза. Разработана программная система РАСПОЗНАВАНИЕ для решения задач анализа данных, распознавания, кластеризации и прогноза.

1. Р.Дуда, П.Харт, «Распознавание образов и анализ сцен», Издательство «Мир», Москва, 1976.

2. В.В. Рязанов «Оптимальные коллективные решения в задачах распознавания и классификации», Диссертация на соискание ученой степени доктора физико-математических наук, Москва, 1994.

3. Федорюк М.В. «Обыкновенные дифференциальные уравнения». М.: Наука. Главная редакция физико-математической литературы, 1980.

4. B.C. Рябенький «Введение в вычислительную математику», Учебное пособие для вузов.

5. Henry Teicher. «Identifiability of mixtures». The Annals of Mathematical Statistics, Vol. 32,244-248,1961.

6. Henry Teicher. «Identifiability of finite mixtures». The Annals of Mathematical Statistics, Vol. 34,1265-1269, 1963.

7. Sidney J. Yakowitz, John D. Spragins. «On the Identifiability of Finite Mixtures». The Annals of Mathematical Statistics, Vol. 39, No. 1,209-214,1968.

8. Д.Б. Юдин, Е.Г. Голыптейн «Линейное программирование». М., Физматтиз, 1963 г.

9. Загоруйко Н.Г. «Методы распознавания и их применение». М.: Сов.радио, 1972. 206с.

10. Загоруйко Н.Г. «Прикладные методы анализа данных и знаний». Новосибирск: Изд-во Института математики, 1999.

11. И.Хэмди А. Таха «Введение в исследование операций», 6-е издание. М.: Издательский дом «Вильяме», 2001.

12. Малиновский Л.Г. «Классификация объектов средствами дискриминантного анализа», «Наука», М., 1979.

13. Благовещенский Ю.Н., Мешалкин Л.Д. «Общие вопросы статистических методов классификации», в сборнике «Статистические методы классификации», вып. I, №6, МГУ, М., 1969.

14. Мешалкин Л.Д., Ребрий В.А. «Классификация наблюдений посредством аппроксимации реальных распределений нормальными в окрестности плоскости деления», в сборнике «Статистические методы классификации», вып. I, №6, МГУ, М., 1969.

15. Robertson, С.A., and Fryer, J.G. «Some Descriptive Properties of Normal Mixtures» Skand. Aktuarietidskr. Parts 3-4,137-14,1969.

16. J.A. Hartigan, «Clustering Algoritms», New York, John Wiley & Sons, 1975.

17. Себестиан Г.С. «Процессы принятия решений при распознавании образов», «Техника», Киев, 1965.

18. Ту Д., Гонсалес Р. «Принципы распознавания образов», «Мир», М., 1978.

19. Раудис LLL, Пикялис В., Юшкавичюс К. «Экспериментальное сравнение тринадцати алгоритмов классификации», в сборнике «Статистические проблемы классификации», Институт физики и математики АН Литовской ССР, Вильнюс, 1975.

20. Андерсон Т. «Введение в многомерный статистический анализ», «Наука», М., 1963.

21. Дородное А.А. «Ортонормированная система Гаусса», «Сборник аспирантских работ. Точные науки», КГУ, Казань, 1969.

22. Волошин Г.Я., Косенкова С.И. «Метод распознавании, основанный на аппроксимации выборок смесью нормальных законов», в сборнике «Вычислительные системы», выпуск 61, Новосибирск, 1975.

23. Раудис Ш., «Алгоритмы построения правила ^слассификации», в сборнике «Статистические проблемы управления», Институт физики и математики АН Литовской ССР, Вильнус, 1975.

24. Исаенко O.K., Урбах В.Ю. «Разделение смесей распределений вероятностей на их составляющие», «Итоги науки и техники. Теория вероятностей. Математическая Статистика. Теоретическая кибернетика», том 13, М., 1976.

25. Апраушева Н.Н. «Об использовании смесей нормальных распределений в распознавании образов», диссертация на соискание ученой степени кандидата физико-математических наук, Москва, 1981.

26. A.S.Biryukov, А.Р.Vinogradov, V.V.Ryazanov, LV.Ryazanov. "Restoration of some cluster densities by empirical densities of mixtures", Pattern Recognition and Image Analysis, Vol. 11, No. 1,2001, pp. 13-15.

27. A.C. Бирюков. "Решение задачи таксономии, основанное на анализе одномерных признаковых покрытий", Доклады 10-ой Всероссийской конференции "Математические методы распознавания образов", стр. 9-11.

28. Neyman J., Pearson E.S. On the problem of the most efficient tests of statistical hypothesis, Phill. Trans. Royal Soc. London, 231,289-337 (1933).

29. Розенблатт Ф. Принципы нейродинамики (перцептрон и теория механизмов мозга). М.: Мир, 1965.-480 с.

30. Айзерман М.А., Браверманн Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970.-384 с.

31. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). М.:Наука, 1974.-415 с.

32. Метод комитетов в распознавании образов. Свердловск: ИММ УНЦ АН СССР, 1974.165 с.

33. Мазуров Вл.Д. Комитеты систем неравенств и задача распознавания // Кибернетика. 1971. №3. С. 140-146.

34. Ивахненко А.Г. Системы эвристической самоорганизации в технической кибернетике. -Киев: Техшка, 1971.-372 с.

35. Лбов Г.С. Методы обработки разнотипных экспериментальных данных// Новосибирск. Наука, 1981.160 с.

36. А.Н.Дмитриев, Ю.И.Журавлев, Ф.П.Кренделев, О математических принципах классификации предметов и явлений. Сб. "Дискретный анализ". Вып. 7. Новосибирск, ИМ СО АН СССР. 1966. С. 3-11.

37. Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. 1971. №3. С. 1-11.

38. Ю.И.Журавлев, Об алгебраическом подходе к решению задач распознавания или классификации. Проблемы кибернетики. М.: Наука, 1978. Вып.ЗЗ. С.5-68.

39. Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз: Матем. методы и их применение. М.: Наука, 1988. Вып.1, С.176-200.

40. Матросов B.JI. Синтез оптимальных алгоритмов в алгебраических замыканиях моделей алгоритмов распознавания// Распознавание, классификация, прогноз: Матем. методы и их применение. М.: Наука, 1988. Вып.1, С.229-279.

41. Рязанов В.В. О построении оптимальных алгоритмов распознавания и таксономии (классификации) при решении прикладных задач // Распознавание, классификация, прогноз: Матем. методы и их применение. М.: Наука, 1988. Вып.1, С.229-279.

42. Рязанов В.В. Комитетный синтез алгоритмов распознавания и классификации // ЖВМ и МФ. 1981. Том 21, №6. С.1533-1543.

43. Рязанов В.В. О синтезе классифицирующих алгоритмов на конечных множествах алгоритмов классификации (таксономии) // ЖВМ и МФ, 1982. Том 22, №2. С.429-440.

44. Дюкова Е.В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания// Проблемы кибернетики. М.: Наука, 1982. Вып. 39. С. 165-199.

45. Дюкова Е.В. Алгоритмы распознавания типа "Кора": сложность реализации и метрические свойства// Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука, 1989. Вып.2. С. 99-125.

46. Сенько О.В. Использование процедуры взвешенного голосования по системе базовых множеств в задачах прогнозирования// М. Наука, Ж. вычисл. матем. и матем. физ. 1995, т. 35, № 10, С. 1552-1563.

47. Aslanyan L., Zhuravlev Yu,.Logic Separation Principle, Computer Science & Information Technologies Conference, Yerevan, September 17-20,2001,151-156.

48. В.Дюк, А.Самойленко, Data Mining: учебный курс СПб: Питер, 2001. - 368 с.

49. Ю.И. Журавлев. Корректные алгебры над множествами не корректных (эвристических) алгоритмов. I. // Кибернетика. 1977. N4. С. 5-17., II. Кибернетика, N4, 1977, III.//Кибернетика. 1978. N2. С. 35-43.

50. Журавлев Ю.И., ИЗБРАННЫЕ НАУЧНЫЕ ТРУДЫ. М.: Издательство Магистр, 1998.-420 с.

51. А.Н.Дмитриев, Ю.И.Журавлев, Ф.П.Кренделев, О математических принципах классификации предметов и явлений. Сб. "Дискретный анализ". Вып. 7. Новосибирск, ИМ СО АН СССР. 1966. С. 3-11.

52. V.V.Ryazanov, Recognition Algorithms Based on Local Optimality Criteria , Pattern Recognition and Image Analysis. 1994. Vol.4, no.2. pp. 98-109.

53. Ryazanov V.V. About some approach for automatic knowledge extraction from precendent data // Proceedings of the 7th international conference "Pattern recognition and image processing", Minsk, May 21-23, 2003, vol. 2, pp. 35-40.

54. V.V.Ryazanov, O.V. Senko, and Yu. I. Zhuravlev. Methods of recognition and prediction based on voting procedures.// Pattern Recognition and Image Analysis, Vol. 9, No. 4, 1999, p.713—718.

55. Кузнецов B.A., Сенько O.B., Кузнецова A.B. и др. // Распознавание нечетких систем по методу статистически взвешенных синдромов и его применение для иммуногематологической нормы и хронической патологии. // Химическая физика, 1996, т.15.№1. С. 81-100.

56. Обухов A.C., Рязанов B.B. Применение релаксационных алгоритмов при оптимизации линейных решающих правил. Доклады 10-й Всероссийскойконференции "Математические методы распознавания образов (ММРО-Ю)", Москва, 2001,102-104.

57. Ф.Уоссермен, Нейрокомпьютерная техника, М.,Мир, 1992.

58. Рязанов В.В., Челноков Ф.Б., О склеивании нейросетевых и комбинаторно-логических подходов в задачах распознавания, Доклады 10-й Всероссийской конференции "Математические методы распознавания образов (ММРО-Ю)", Москва, 2001,115-118.

59. Christopher J.C. Burges. A Tutorial on Support Vector Machines for Pattern Recognition, Appeared in: Data Mining and Knowledge Discovery 2,121-167,1998.

60. Vetrov D.P. On the Stability of the Pattern Recogntion Algorithms. // Pattern Recognition and Image Analysis, Vol.13, No.3,2003, pp.470-475.

61. Журавлев Ю.И., Зенкин А.И. Зенкин А.А., Дюкова E.B., Исаев И.В., Кочетков Д.В., Кольцов П.П., Рязанов В.В. Пакет прикладных программ для решения задач распознавания и классификации (ПАРК). ВЦ АН СССР, Москва, 1981.24 с.

62. Бушманов О.Н., Дюкова Е.В., Журавлев Ю.И., Кочетков Д.В., Рязанов В.В. Система анализа и распознавания образов, Распознавание, классификация, прогноз: Мат. методы и их применение. М.:Наука, 1988. Вып.2. С.250-273.

63. Дюкова Е.В., Журавлев Ю.И., Рязанов В.В. Диалоговая система анализа и распознавания образов. М.: ВЦАН СССР, 1988,40 с.

64. Ryazanov V.V. One approach for classification (taxonomy) problem solution by sets of heuristic algorithms, Proceedings of the 9-th Scandinavian Conference on Image Analysis, Uppsala, Sweden, 6-9 June 1995, Vol.2, P.997-1002.

65. Sigillito, V. G., Wing, S. P., Hutton L. V., Baker К. B. (1989). Classification of radar returns from the ionosphere using neural networks. Johns Hopkins APL Technical Digest, 10,262-266

66. Дж. Роббинс «Отладка приложений», Перевод с английского, Спб.: БХВ-Петербург, 2001.

67. Harrison, D. and Rubinfeld, D.L. Hedonic prices and the demand for clean air, J. Environ. Economics & Management, vol.5,81-102, 1978.

68. Дидэ Э., и др. Методы анализа данных: Подход, основанный на методе динамических сгущений. Перевод с французского. Под редакцией и с предисловием С.А. Айвазяна и В.М. Бухштабера М.: Финансы и статистика, 1985.

69. Айвазян С.А., и др. ПРИКЛАДНАЯ СТАТИСТИКА: Классификация и снижение размерности, М. Финансы и статистика, 1989.

70. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Перевод с английского М.: Мир, 1985.

71. A. S. Biryukov. "A Method for Finding Algebraic Correctors in Precedent-Based Image Recognition", Pattern Recognition and Image Analysis, Vol. 11, No. 1, 2001, pp. 11-12, 2001.