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

ВВЕДЕНИЕ.

ГЛАВА 1. КЛАСТЕРНЫЙ АНАЛИЗ В ЗАДАЧАХ

КОГНИТИВНОГО АНАЛИЗА ДАННЫХ.

1.1. Задача кластерного анализа.

1.2. Примеры решения задач извлечения знаний на основе кластерного анализа.

1.3. Алгоритмы кластеризации.

1.3.1. Вариационный подход.

1.3.2. Алгоритмы прямой классификации.

ГЛАВА 2. ТЕСТИРОВАНИЕ КЛАСТЕРНЫХ АЛГОРИТМОВ НА ИНВАРИАНТНОСТЬ ОТНОСИТЕЛЬНО НУМЕРАЦИИ ОБЪЕКТОВ.

2.1. Задача тестирования.

2.2. Методы тестирования на симметричных данных.

2.2.1. Первый метод тестирования.

2.2.2. Второй метод тестирования.

2.3. Примеры симметричных тестов.

2.4. Генерация тестов.

ГЛАВА 3. РАЗРАБОТКА ИНВАРИАНТНЫХ КЛАСТЕРНЫХ

АЛГОРИТМОВ.

3.1. Решетка взвешенных отношений сходства.

3.2. Задача аппроксимации взвешенных отношений сходства транзитивными взвешенными отношениями сходства.

3.3. Операции агрегирования.

3.4. Нечеткие реляционные алгоритмы кластеризации.

Актуальность темы. В настоящее время во всем мире идет активная разработка методов построения интеллектуальных систем. Эти системы основываются на знаниях, которые приобретаются как непосредственно от эксперта или из литературных источников, так и в результате их извлечения из данных. При этом широко используются методы кластерного анализа, которые позволяют формировать классы сходных объектов на основе анализа сходства между объектами или описания объектов в некотором пространстве признаков. Эти методы используются в задачах когнитивного анализа данных: для анализа структуры семантических пространств, формирования понятийной структуры множества объектов, выявления скрытых факторов, лежащих в основе анализируемых явлений, выявления семантической общности исследуемых объектов, обобщения информации [2, 3, 7, 14, 18, 22, 23,25-27].

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

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

Основные задачи работы.

1. Исследование свойств инвариантных алгоритмов кластеризации.

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

3. Разработка инвариантных кластерных алгоритмов и их программная реализация.

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

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

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

• Осуществлена постановка задачи тестирования кластерных алгоритмов на инвариантность относительно нумерации объектов.

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

• Предложены методы генерации симметричных тестов.

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

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

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

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

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

Апробация работы. Результаты, полученные в ходе проведения диссертационных исследований, докладывались и обсуждались на международном семинаре "ДИАЛОГ'95: компьютерная лингвистика и ее приложения" (Казань, 1995), региональном научно-практическом семинаре "Новые технологии в культуре и искусстве" (Казань, 1995), II международной конференции по приложению нечетких систем и мягких вычислений (Германия, Зиген, 1996), международном семинаре "Мягкие вычисления-96" (Казань, 1996), Европейском конгрессе по нечетким интеллектуальным технологиям и мягким вычислениям (Германия, Ахен, 1997), международной конференции "Новые направления в искусственном интеллекте и нейронных сетях" (Турция, Анкара, 1997), 2-ой международной научно-технической конференции "Интерактивные системы: проблемы человеко-компьютерного взаимодействия" (Ульяновск, 1997), региональной конференции молодых ученых (Казань, 1997).

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

В первой главе приводится общая постановка задачи кластерного анализа.

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

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

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

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

К настоящему времени разработан ряд кластерных алгоритмов, основанных на интуитивных соображениях выделения изолированных групп объектов в множестве X и не имеющих эквивалентной формальной постановки задачи. Такие алгоритмы называются эвристическими или алгоритмами прямой классификации [12, 21]. Другой, вариационный подход к решению задачи кластеризации, основанный на применении оптимизационных алгоритмов, подразумевает формализацию интуитивных представлений о разделении компактных групп объектов. Формализация постановки задачи в этом случае сводится к введению в рассмотрение некоторого функционала, зависящего от разделения объектов на классы, экстремум которого как раз и достигается на "хороших" в интуитивном смысле разбиениях.

При решении задач когнитивного кластерного анализа предпочтение отдается, как правило, эвристическим алгоритмам кластеризации [21]. Основные преимущества этих алгоритмов перед оптимизационными процедурами заключаются в следующем:

•относительная простота алгоритмов, их содержательная ясность, что валено для "заказчика", - процесс классификации происходит как бы у него на глазах;

•допустимость контролируемого вмешательства в работу алгоритма - изменение параметров, смысл которых понятен;

•возможность визуализации данных и принятия непосредственных решений;

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

•высокая содержательная ясность результатов классификации и практические удобства в ее осуществлении.

При использовании кластерных алгоритмов в задачах извлечения знаний, когда основной целью кластеризации выступает интерпретация построенных кластеров, на первый план выходит вопрос о зависимости результатов работы алгоритма, а, значит, и их интерпретации от порядка просмотра объектов. Результаты работы большинства кластерных алгоритмов не являются инвариантными относительно нумерации объектов, а если даже алгоритм инвариантен, то он, как правило, имеет различные ограничения на применение [12, 13,29].

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

В разделе 2.1 приводится постановка задачи тестирования кластерных алгоритмов на инвариантность относительно нумерации объектов [6, 30, 33, 35, 36]. В рамках этой задачи формализуется понятие инвариантности алгоритма относительно нумерации объектов, описывается традиционный подход к тестированию кластерного алгоритма на такого рода инвариантность.

ОПРЕДЕЛЕНИЕ 1. Пусть Ь - некоторое множество, | Ь \ =п, п> 1. Функцией близости на Ь называется функция где 1Н множество вещественных чисел, удовлетворяющая на Ь условию симметричности:

ОПРЕДЕЛЕНИЕ 2. Пусть Ь - некоторое множество, | Ь \ =п, п> 1. Нумерацией множества Ь называется биекция <з:Ь—>К, где £={1,2,.„я}.

Пусть Ь - некоторое множество, | Ь | =п, п> 1, К={\,2,.,п}. Функция близости ^ на Ь и нумерация а множества £ порождают на множестве номеров К функцию близости 8к:КхК—>9?, где 5^(7/)= ^(О, а !(/)).

Легко убедиться, что на Ь выполняется следующее соотношение: а(х), ст(у)).

ОПРЕДЕЛЕНИЕ 3. Пусть Ь - некоторое множество, | Ь | =п, п> 1. Р(Ь) - множество всех подмножеств множества Ь. Покрытием множества Ь называется множество С{Ь)={2]}оР{П), объединение элементов которого совпадает с Ь\ \jZj- =Ь. Множества из С{Ь) называются кластерами в Ь. Покрытие С(Ь) называется разбиением множества Ь, если 2гп27=0 для всех 2^С(Ь) таких, что щ.

ОПРЕДЕЛЕНИЕ 4. Пусть Ь={\,2,.,п) (п - любое число, большее 0), - функция близости на Ь. Алгоритм кластеризации <2 - это правило, которое каждой функции близости ^ на X ставит в соответствие некоторое единственное покрытие С(Ь) множества!/.

Обычно от С(Ь) требуют, чтобы оно было разбиением множества Ь.

Предполагается, что функция Я1 представляется в виде матрицы сходства (расстояния) 1,где .у,/= ^(/у) для любых ту'=1,.,и.

Через X п> 1) обозначим множество объектов кластеризации, черезМ- множество натуральных чисел {1,2

Пусть - функция близости на X, <зХ—>М - нумерация множества X, 5м - функция близости, порождаемая 8х и ст, С(М) -покрытие множества М, построенное кластерным алгоритмом <2 на основе

Предположим, что ЫеС(М) - кластер в М. ст (Ы) обозначает образ кластера N в множестве объектов X, определяемый отображением <5Л'М->Х. Обозначим ст1(С(М)) множество всех в

X, определяемых кластерами N из С(М). Очевидно, что &\С{М)) является покрытием множества X и будет разбиением X, если С(М) -разбиение М.

Нетрудно заметить, что для данных X и изменение нумерации <71 на с>2 может привести к тому, что алгоритм <2 построит покрытие С2(Х)= <32~1(С,2(М)) множества X, не совпадающее с С\ (X) = аЛсту

ОПРЕДЕЛЕНИЕ 5. Алгоритм <2 называется инвариантным относительно нумерации объектов, если для любых X, и нумераций <71 и с>2 множества X выполняется <5\1{С\(М))= СТ21(С2(М)), где С\{М) и Сг(М) - покрытия множества М, построенные алгоритмом <2 на основе функции близости и нумераций а] и

ОПРЕДЕЛЕНИЕ 6. Тестом <Х, будем называть конечное множество объектов X совместно с заданной на нем функцией близости

Пусть задано некоторое конечное непустое множество тестов {<X. >}{=!,.,т- Будем считать, что каждое из множеств Хи /=1,.,т, содержит, по крайней мере, два объекта. Тогда из определения 5 вытекает следующий метод тестирования кластерного алгоритма на основе анализа результатов его работы.

1. Выбирается первый тест (/=1).

2. Выбирается первая (у=1) нумерация множества Х{. с/. Х1-^М1.

3. Вычисляются в соответствии с сть ХГ^>М1 и функцией близости

Л/ значения функции близости на множестве номеров.

Найденное множество значений представляется в виде матрицы сходства (расстояния).

4. На основе полученной матрицы с помощью тестируемого алгоритма строится покрытие (разбиение) С\(Мг).

5. В соответствии с нумерацией сть и полученной классификацией множества номеров осуществляется построение классификации С\{Х^) множества объектов.

6. Выбирается следующая (/=/'+1) нумерация су/ множества

Хг.

7. Вычисляются в соответствии с <зу: и функцией близости значения функции близости на множестве номеров.

Найденное множество значений представляется в виде матрицы сходства (расстояния).

8. На основе полученной матрицы с помощью тестируемого алгоритма строится покрытие (разбиение) С/Мг).

9. В соответствии с нумерацией оу: Х^М, и полученной классификацией множества номеров осуществляется построение классификации множества объектов.

10. Полученная классификация С^Х,) сравнивается с С\(Х,). Если С^Х^фС^Хг), что доказывает неинвариантность тестируемого алгоритма, то процедура тестирования завершается. В противном случае осуществляется переход к пункту 11.

11. Проверяется, не исчерпано ли множество всех нумераций множества Х(. Если не все нумерации рассмотрены, то осуществляется переход к пункту 6, а иначе - переход к пункту 12.

12. Анализируется множество {<Х,,15'^>}г=1. „г. Если все тесты этого множества рассмотрены, то процедура тестирования завершается. В противном случае / увеличивается на единицу и осуществляется переход к пункту 2.

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

В разделе 2.2 описывается новый подход к проверке кластерных алгоритмов на инвариантность относительно нумерации объектов, в основе которого лежит идея тестирования алгоритма на симметричных данных [6, 30, 35, 36]. В рамках этого подхода предлагается несколько способов тестирования кластерных алгоритмов, вытекающих из особенностей работы инвариантных алгоритмов на симметричных данных.

ОПРЕДЕЛЕНИЕ 7. Множество X называется симметричным относительно функции близости если существует отличная от тождественной биекция такая, что 8х{х,у)= для всех х, у из X. / будет называться симметрией на <Х,

ОПРЕДЕЛЕНИЕ 8. Пусть Х - конечное множество объектов, 5й -функция близости на X и {/¿¡¿^.„к, (к > 1), - множество попарно различных симметрии: на <Х, Тройка Т = будет называться симметричным тестом.

ТЕОРЕМА 1. Пусть на <Х, задана совокупность попарно различных симметрий \.к, к> 1, и ст0 - любая нумерация множества X Тогда существует набор различных нумераций множествах {а/}г=о,.,а, ^г^о^/Г1, которые порождают вместе с множество функций близости Бо4,.^^1, совпадающих друг с другом.

Пусть Т = <Х,8х,{/',}г-:\.р- - симметричный тест. Рассмотрим множество нумераций {аг}г=о.к множества X, где ао - произвольная нумерация, а,=ао° /¡~\ 1=1,.к. В соответствии с теоремой функции близости 5) , 1=0,.к, определяемые и аг, совпадут. Следовательно, покрытия Сг{М), 1=0,.,к, множества М, построенные одним алгоритмом кластеризации <2 на основе соответствующих равных между собой функций также совпадут:

Со{Щ=С\{Щ=.=С]£М)=С{М). Однако, этого в общем случае нельзя сказать про покрытия С1(Х)=ъ1л{С{А4)), ¡=0,.,к, множества X, определенные нумерациями стг множества X и полученным покрытием С(М). Очевидно, покрытия Сг(Х) заведомо совпадут, если алгоритм () обладает свойством инвариантности относительно нумерации объектов. Однако, если кластерный алгоритм <2 не инвариантен, то эти покрытия С,(Х) могут отличаться друг от друга.

В связи с вышеизложенным практическая реализация процедуры тестирования алгоритма на некотором симметричном тесте <Х,8х,{^}г=\,.,к> может включать в себя следующие шаги.

1. Выбирается (произвольно) начальная нумерация сто множества

X.

2. На основе соотношения ^(/у)— ¿^(сто /у— находится множество значений функции близости которое затем представляется в виде матрицы сходства (расстояния).

3. На основе полученной матрицы с помощью тестируемого алгоритма (2 строится покрытие (разбиение) С(М).

4. В соответствии с нумерацией сто: Х-^М и полученной классификацией множества номеров С(М) осуществляется построение классификации Со(Х) множества объектов.

5. Из множества {/¿}г=1 выбирается первая (/=1) симметрия.

6. В соответствии с симметрией £ и первоначальной нумерацией сто объекты перенумеровываются: стг(л:)=сто(/?"1(х)) для любого хеХ.

7. Согласно нумерации стг и полученной классификации множества номеров осуществляется построение классификации С{Х)=<5[\С{М)) множества объектов.

8. Полученная классификация С^Х) сравнивается с Со(Х). Если Сг(Х)*Со(Х), что доказывает неинвариантность тестируемого алгоритма, то процедура тестирования завершается. В противном случае осуществляется переход к пункту 9.

9. Проверяется, не исчерпано ли множество симметрий {/¿}г=1.к

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

ТЕОРЕМА 2. Если / - симметрия на <Х, 8!х>, <2 - инвариантный алгоритм, С(Х) - построенное им разбиение множества X на основе 8х, тогда для каждого кластера А из С(Х) существует кластер в С(Х), совпадающий с образом множества А при отображении/

Согласно теореме 2 метод проверки кластерного алгоритма на основе некоторого симметричного теста может заключаться в следующем.

1. Выбирается произвольно нумерация сто множества X.

2. На основе соотношения $х{<5оЛ{г),<3()Л{])) г,/=1,.,и находится множество значений функции близости 5м, которое затем представляется в виде матрицы сходства (расстояния).

3. На основе полученной матрицы с помощью тестируемого алгоритма <2 строится разбиение С(М).

4. В соответствии с нумерацией Сто: Х->М и полученной классификацией множества номеров С(М) осуществляется построение классификации С{Х) множества объектов.

5. Оценивается наличие в разбиении С(Х) для всех его классов А\, А2,.Ат (т>1) образов последних при отображениях

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

Первый способ.

5.1. Из множества {/¡}¡=\,.,к выбирается первая (/=1) симметрия.

5.2. Осуществляется поиск в С(Х) для каждого его класса А^ ]=!,.,т, образа /¡(А^. В случае доказывающего неинвариантность алгоритма отсутствия в С(Х) хотя бы одного из искомых образов процедура тестирования завершается.

5.3. Проверяется, не исчерпано ли множество симметрий

Шг=1.к- Если ¿Фк, то выбирается следующая (/=/+1) симметрия и осуществляется переход к пункту 5.2. Если рассмотрены все симметрии, то процедура тестирования на данном симметричном тесте завершается.

Второй способ.

5.1. Из С(Х) выбирается первый (/=1) класс.

5.2. Осуществляется поиск в С(Х) для класса А] классов, совпадающих с /г(Л;), /=1 В случае доказывающего неинвариантность алгоритма отсутствия в С(Х) хотя бы одного из искомых образов процедура тестирования завершается.

5.3. Проверяется, не рассмотрены ли все классы разбиения С(Х). Если ¿Фт, то выбирается следующий О^'+У) класс и осуществляется переход к пункту 5.2. В противном случае процедура тестирования на данном симметричном тесте <Д5ЙГ,{//}7-=1>.д> завершается.

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

В последних разделах настоящей главы приводятся примеры симметричных тестов, описываются некоторые способы генерации симметричных тестов [33].

ТЕОРЕМА 4. Предположим Тх = .к> симметричный тест, У есть такое подмножество X, что существует множество Щ) взаимно различных функций И/.У-^У (/=1,.,/, 1 </< к), совпадающих на У с некоторыми функциями из {//},•=!„,.,к

Предположим также, что есть ограничение функции на

7x7. Тогда тройка Т2 = <Y,Sy,{hj}j=\.t> будет симметричным тестом.

Для тестов Т\ и Т2, рассмотренных в Теореме 4, будем записывать Т2 с Т\ и будем говорить, что Т2 есть симметричный подтест Т\ и Т\ есть база для Т2.

Пусть х - некоторый элемент множества X и / - некоторая симметрия на

ХУ>. Обозначим f°(x)= х и f\x) = /(/''ч(х)) =fl(fi+\x))

00 для всех i = ±1, ±2,. Множество Gf (х) = j^J/' (х) будет называться z'=-со множеством элементов, генерируемых х и f. Ранг х относительно / определяется как г/(х)= \ G/x) \.

ПРЕДЛОЖЕНИЕ 1. Для любой симметрии / на <X,SK> и для любого хеХ выполняется

Gf(x)= {/%х%.,Г\х)}, (1) где г = min{ j>0: f(x) = х }.

Отношение (1) можно записать как

G/(x)=\J f{x). i=о

Предположим, что Т = <Х, Sx, {fi}i=\.i> - это симметричный тест, V - непустое подмножество {/',},=i.fk - некоторая симметрия на <Х, Sx>. Обозначим Gf (V)= (J G/ (x). Множество V будет xeF называться термом для множества 7= G/(V) относительно симметрии

ТЕОРЕМА 5. Предположим Гг = <Х, Sx есть симметричный тест, V - непустое подмножество X, /е {fi}, ),.^ некоторая симметрия на <Х, Предположим У = О/У), есть ограничение функции на множество 7x7 и /г - функция, совпадающая с/на С/У), тогда Т2 = <7, {/?}> будет симметричным подтестом теста Т\.

ТЕОРЕМА 6. Предположим У, = 5х ,{/■},■ симметричный тест, V - непустое подмножество X, некоторая симметрия на <Х, Бх>. Предположим 2 = ХО/ V) Ф0, 51 -ограничение функции ^ на 2у2 и функция, совпадающая с / на 2, тогда = <2, Б2, (я}> будет симметричным подтестом теста 1\.

В третьей главе описываются новые нечеткие реляционные кластерные алгоритмы. Эти иерархические алгоритмы носят параметрический характер и обладают свойством инвариантности относительно нумерации объектов [34].

Задача иерархического кластерного анализа заключается в построении иерархии разбиений множества X, исходя из заданной матрицы сходства. Матрицу сходства можно интерпретировать как множество значений взвешенного отношения сходства. Любое взвешенное отношение эквивалентности определяет иерархию вложенных друг в друга разбиений множества X на классы эквивалентности [8]. Таким образом, задача иерархической кластеризации будет решена в процессе преобразования заданного взвешенного отношения сходства в некоторое взвешенное отношение эквивалентности, а кластерный алгоритм может представлять из себя процедуру одноименного преобразования.

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

В основе нечетких реляционных кластерных алгоритмов лежит описанная процедура транзитивного преобразования: где F означает процедуру коррекции отношения S, ТС - процедуру транзитивного замыкания. В качестве процедуры транзитивного замыкания используется алгоритм "ближайший сосед". Процедура коррекции отношения S имеет вид: f S(x,y) ifh.>c (i = 1,2,3) Fk(x,y) else, (к = 1,2,3),

Ых,у)\-2 $Лх>у) -1 h2 = к пип <\Уу(х)\-2,\Ух(у)\-2У

1-2 тж(\Уу{х)\-2,\Ух{у)\-2У А \К(х,у)\-2 3 \У{х,у) |-2'

Уу(х)={2еХ\Ь-8(х,у)<8(2,х)}, К(у)={геХ\ Ь-8(х,у)<8(2,у)}, У(х,у)={хеХ| Ь-8(х,у)<тж(8(х,2\8(у,2))} = Уу(х)иУх(у), У1(х,у)={2еХ\ = Уу(х)пУх(у), с, Ье [0,1]

1<\(х,у), Р2(х,у) и ^з(х,у) равны, соответственно, минимальному, среднему арифметическому и максимальному значению из всех 8(х,г), 8(у,г), (ге У), значение которых меньше 8(х,у).

Согласно описанной схеме коррекции связь S(x,y) между объектами х, у сохраняется, если hi>c, иначе связь ослабляется. В случае, например, когда /=3, значение отношения сходства 5*(Ху) остается неизменным, если число ( | V\(x,y) | -2) объектов, "близких" и с х и с у, превышает долю с числа (| V(x,y) | -2) объектов, "близких" хотя бы с одним из объектов х или у. Понятие "близости" некоторого объекта с объектом х (объектом у) определяется тем, попадает ли этот объект в "окрестность" Vy(x) точки х (Ух(у) точки у), причем размеры окрестности могут варьироваться за счет изменения параметра Ь. Таким образом, схема коррекции учитывает влияние "близких соседей": связь между х и у сохраняется, если х и у "ведут себя примерно одинаково" по отношению к своим "близким соседям", в противном случае связь ослабляется.

Множество реляционных кластерных алгоритмов, определяемых описанной схемой преобразования взвешенного отношения сходства во взвешенное отношение эквивалентности, включает в себя некоторые хорошо известные алгоритмы. При с=О реляционные алгоритмы совпадают с алгоритмом "ближайший сосед", при b,k= 1 и /=3 - алгоритмом Few [7].

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

Нечеткие реляционные кластерные алгоритмы реализованы на языке Турбо Паскаль для персональных компьютеров семейства ШМ.

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

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

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

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

2. Исследованы свойства инвариантных кластерных алгоритмов.

ЗАКЛЮЧЕНИЕ

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

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

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

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

Ill

1. Аверкин А.Н., Батыршин И.З., Блишун А.Ф., Силов В .Б., Тарасов В.Б. Нечеткие множества в моделях управления и искусственного интеллекта. - М.: Наука, 1986,- 312 с.

2. Апресян Ю.Д. Алгоритм построения классов по матрице расстояний//Машинный перевод и прикладная лингвистика, вып. 9. -1966.-С. 72-79.

3. Батыршин И.З., Панова A.M., Хабибулин Р.Ф. Алгоритмы кластеризации в анализе объектов искусства и культуры//Новые технологии в культуре и искусстве/Тезисы докладов регионального научно-практического семинара. Казань: НИИ "Прометей", 1995, 40 - 43.

4. Батыршин И.З., Хабибулин Р.Ф. Атрибуция псевдонимных произведений на основе инвариантных реляционных алгоритмов кластеризации. В кн.: Труды Международного семинара по компьютерной лингвистике и ее приложениям: ДИАЛОГ'95, Казань, 1995, с. 43-53.

5. Батыршин И.З. О задаче аппроксимации в частично упорядоченном множестве//Математические методы оптимизации и управления в системах. Калинин: КГУ, 1985,- С. 50-56.

6. Батыршин И.З., Хабибулин Р.Ф. Тестирование кластерных алгоритмов на инвариантность относительно нумерации объектов. -Известия академии наук. Теория и системы управления. 1997, 2, 165 -168.

7. Батыршин И.З., Шустер В.А. Структура семантического пространства словесных оценок поступков/ЯТринципиальные вопросытеории знаний/Труды по искусственному интеллекту. Ученые записки Тартусского гос. ун-та. Вып. 688- Тарту, 1984.- С. 20-38.

8. Биркгоф Г., Барти Т. Современная прикладная алгебра. М.: Мир, 1976,-400 с.

9. Браверман Э.М., Дорофеюк A.A., Лумельский В.Я., Мучник И.Б. Диагонализация матрицы связи и выявление скрытых факторов/ЛТроблемы расширения возможностей автоматов. Вып.1,-М.: ИПУ АН СССР, 1971. с. 42 - 79.

10. Гретцер Г. Общая теория решеток: Пер. с англ./ Под редакцией Д. М. Смирнова. М.: Мир, 1981. - 456 с.

11. Дорофеюк A.A. Алгоритмы обучения машины распознаванию образов без учителя, основанные на методе потенциальных функций. "Автоматика и телемеханика", 1966, №10.

12. Дорофеюк A.A. Алгоритмы автоматической классификации (обзор литературы)//Проблемы расширения возможностей автоматов. Вып.1,- М.: ИПУ АН СССР, 1971. с. 5 - 41.

13. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.-511 с.

14. Дэйвисон М. Многомерное шкалирование. М.: Финансы и статистика, 1988. - 254 с.

15. Дюран Б., Оделл П. Кластерный анализ. М.: Статистика, 1977,- 128с.

16. Елисеева И.И., Рукавишников В.О. Группировка, корреляция, распознавание образов (Статистические методы классификации и измерения связей).-М.: Статистика, 1977. 143 с.

17. Елкина В.Н., Загоруйко Н.Г. Количественные критерии качества таксономии и их использование в процессе принятиярешений. "Вычислительные системы", вып. 36, Новосибирск, изд-во "Наука", 1969.

18. Жамбю М. Иерархический кластер-анализ и соответствия. -М: Финансы и статистика, 1988. 342 с.

19. Заморзаев A.M., Палистрант А.Ф. Теория дискретных групп симметрии: Лекции по спец-курсу. Кишинев: КГУ, 1977. 101с.

20. Кофман А. Введение в теорию нечетких множеств. М.: Радио и связь, 1982.- 432 с.

21. Манд ель И. Д. Кластерный анализ. М.: Финансы и статистика, 1988. - 176 с.

22. Марусенко М.А. Атрибуция анонимных и псевдонимных литературных произведений методами распознавания образов. Л.: Изд-во Ленинградского университета, 1990. - 168 с.

23. Налимов В.В. Вероятностная модель языка. М.: Наука, 1979. - 303 с.

24. Нильсон Н. Обучающиеся машины. М., изд-во "Мир", 1967.

25. Олдендерфер М.С., Блэшфилд Р.К. Кластерный анализ. В кн.: Факторный, дискриминантный и кластерный анализ. М.: Финансы и статистика, 1989. - С. 139 - 214.

26. Петренко В.Ф. Психосемантика сознания. М.:МГУ, 1988,208 с.

27. Рубанов Л.И. Метод классификации словаря для помехоустойчивой системы машинного понимания естественного языка. Известия РАН. Техническая кибернетика, 5, 1991. - С. 84 - 93.

28. Торговицкий И.Ш. Распознавание образов при отсутствии процесса обучения. Сб. "Вопросы бионики", М., изд-во "Наука", 1967.

29. Факторный, дискриминантный и кластерный анализ: Пер. с англ./Дж.-О. Ким, Ч. У. Мьюллер, У. Р. Клекка и др.; Под ред. И. С. Енюкова. М.: Финансы и статистика, 1989. - 215 с.

30. Хабибулин Р.Ф. Новые методы тестирования кластерных алгоритмов на инвариантность относительно нумерации объектов. -Труды международного семинара "Мягкие вычисления 96"/ Под ред. И.З. Батыршина, Д.А. Поспелова, Казань, 1996, 209 - 213.

31. Шлезингер М.И. О самопроизвольном различении образов. В сб. "Читающие автоматы". Киев, изд-во "Наукова думка", 1965.

32. Batyrshin I., Kaynak O., Khabibulin R. Test generation for clustering algorithms, in: New Trends in Artificial Intelligence and Neural Networks (Ed. by T. Ciftcibasi, M. Karaman, V. Atalay), EMO Scientific Books, Ankara, 1997, 195 199.

33. Batyrshin I., Khabibulin R. On construction of invariant relational clustering algorithms, in: Interactive Systems: The Problems of HumanComputer Interaction, (Ed. by P. Sosnin), Uljanovsk, 1997, v.2, 3-5.

34. Batyrshin I., Khabibulin R. On invariance of clustering algorithms. Journal of Fuzzy Mathematics. (Submitted).

35. Batyrshin I., Khabibulin R. Testing of Clustering Algorithms on Invariance EUFIT'97, Aachen, Germany, 1997, pp. 1847-1851.

36. Bonner R.E. A "logical pattern" recognition program. "IBM Journ. Res. and Develop.", 1962, vol. 6, N 3.

37. Dunn J.C. A graph-theoretic analysis of pattern classification via Tamura's fuzzy relation , IEEE Trans, on Systems, Man and Cybernetics SMC-4 (1974), 310-313.

38. Fodor J., Roubens M. Fuzzy Preference Modelling and Multicriteria Decision Support. Dordrecht: Kluwer Academic Publishers, 1994.

39. Friedman H., Rubin J. On some invariant criteria for grouping data. "Journ. Amer. Statist. Assoc.", 1968, 62, N 320.

40. Hirsch G., Lamotte M., Mas M.T., Vigneron M.J. Phonemic classification using a fuzzy dissimilitude relation. Fuzzy Sets and Systems, 5, 267-275, 1981.

41. Kullback S. Information theory and statistics. New York, 1959.

42. Rose M. Classification of a set of elements. "Computer Journ.", 1964, vol. 7, N 3.

43. Rubin J. Optimal classification into group an approach for solving the taxonomy problem. "J. Theor. Biol.", 1967,15, N 1.

44. Sebestyen G. Pattern recognition by an adaptive process of sample set construction. "Trans. IRE", 1962, IT-8, N 5.

45. Tamura S., Higuchi S., Tanaka K. Pattern classification based on fuzzy relations.- IEEE Trans, on Systems, Man and Cybernetics SMC-1 (1971), 61-66.

46. Windham M. R. Numerical classification of proximity data with assignment measures//J. of Classification. 1985, - v. 2. - p. 157 - 172.

47. Yager R.R. Constrained OWA aggregation. Fuzzy Sets and Systems, 81, 1996, 89-101.

48. Zadeh L.A. Similarity relations and fuzzy orderings.- Inform. Sciences.- 1971,-V.3.-P. 177-200.

49. Результаты экспериментов на физиологическом материале

50. Идеальное" Метод Первый Второйразбиение корреляционных алгоритм алгоритмплеяд экстремальной экстремальнойгруппировки группировки1. 1-7 I. 1-7 I. 1-4,6 I. 1-71.. 8-11 II. 8,9 II. 5, 7, 10, 11 II. 8-11

51. I. 12-25 III. 10, 11 III. 8, 9, 26, 27 III. 12-17,24,1.. 26 IV. 12-21,24 IV. 12 -17, 24, 251. V. 27 V. 22 25 IV. 18-23

52. VI. 28, 29 VI. 23 V. 18-23 V. 28, 29

53. VII. 30,31 VII. 25 VI. 28, 29 VI. 27,30,31

54. VIII. 32, 33 VIII. 26 VII. 30-33 VII. 26, 32, 331.. 27 1. X. 28, 29 1. XI. 30,31 1. XII. 32, 33

55. Идеальное" Реляционные кластерные алгоритмыразбиение ъ =0.5; Ъ= 1 с=0.2 с =0.5 с=0.81. 1-7 I. 1-7 I. 1-7 I. 1-71.. 8-11 II. 8,9 II. 8,9 II. 8,9

56. I. 10, И III. 10, 11 III. 10,11

57. I. 12-25 IV. 12-25 IV. 12-25 IV. 12-251.. 26 V. 26 V. 26 V. 26

58. V. 27 VI. 27 VI. 27 VI. 27

59. VI. 28, 29 VII. 28, 29 VII. 28, 29 VII. 28,29

60. VII. 30,31 VIII. 30,31 VIII. 30,31 VIII. 30,31

61. VIII. 32, 33 IX. 32,33 IX. 32, 33 IX. 32,33

62. Идеальное" Реляционные кластерные алгоритмыразбиение ъ-- =1.0; к= 1с=0.2 с=0.5 с=0.81. 1-7 I. 1-7 I. 1-7 I. 1-71.. 8-11 II. 8,9 II. 8,9 II. 8,9

63. I. 10, 11 III. 10, 11 III. 10,11

64. I. 12-25 IV. 12-25 IV. 12-25 IV. 12-24 V. 251.. 26 V. 26 V. 26 VI. 26

65. V. 27 VI. 27 VI. 27 VII. 27

66. VI. 28, 29 VII. 28, 29 VII. 28, 29 VIII. 28,29

67. VII. 30,31 VIII. 30,31 VIII. 30,31 IX. 30,31

68. VIII. 32, 33 IX. 32, 33 IX. 32, 33 X. 32,33

69. Идеальное" Реляционные кластерные алгоритмыразбиение Ь = 0.5, 1.0; к = 2, 3с=0.2 с=0.5 с=0.81. 1-7 I. 1-7 I. 1-7 I. 1-71.. 8-11 II. 8,9 II. 8,9 II. 8,9

70. I. 10, 11 III. 10, 11 III. 10,11

71. I. 12-25 IV. 12-25 IV. 12-25 IV. 12-251.. 26 V. 26 V. 26 V. 26

72. V. 27 VI. 27 VI. 27 VI. 271. ТАТАРСТАН ФЭННЭР1. АКАДЕМИЯ СЕтабигать системалары экологиясе институты420089, Казан, Даурия ур., 28 тел. 35-90-07на № от

73. АКТ ВНЕДРЕНИЯ реляционных алгоритмов кластеризации

74. Реляционные алгоритмы кластеризации разработаны аспирантом Казанского государственного технологического университета Хабибулиным Р.Ф. и его научным руководителем зав. кафедрой информатики и прикладной математики КГТУ д.ф.-м.н., проф. Батыршиным И.З.

75. Зав. лаб., к.б.н. Н.с., к.б.н. Н.с.1. АКАДЕМИЯ НАУК ТАТАРСТАНАинститут экологии природных систем420089, Казань, ул. Даурская, 28 тел. 35-90-071. УТВЕРЖДАЮора по научной1. Бойко В.А.4< {5" » ок&я'ар? 1997 г. " * 7 т

76. Зайнулгабидинов Э. Р. Шафигуллина С. М. Фаткуллина Р. Р.

77. ТАТАРСТАН РЕСПУБЛИКАСЫ ПРЕЗИДЕНТЫ КАРШЫНДАГЫ ,ЭУЛЭТ ХЕЗМЭТКЭРЛЭРЕ ЭШЛЭРЕ ДЕПАРТАМЕНТЫНЫН ДЭУЛЭТ ХЕЗМЭТКЭРЛЭРЕНЕН БЕЛЕМЕН АРТТЫРУ ЬЭМ КВАЛИФИКАЦИЯСЕН KYT9PY

78. РЕСПУБЛИКА УЗЭГЕ 420111, Казан, Кремль ур. , 6/20 тел./факс: (8432) 38-96-29республиканский центр

79. ПЕРЕПОДГОТОВКИ И ПОВЫШЕНИЯ

80. КВАЛИФИКАЦИИ ГОСУДАРСТВЕННЫХ СЛУЖАЩИХ ПРИ ДЕПАРТАМЕНТЕ ПО ДЕЛАМ ГОСУДАРСТВЕННЫХ СЛУЖАЩИХ ПРИ ПРЕЗИДЕНТЕ РЕСПУБЛИКИ ТАТАРСТАН420111, Казань, ул. Кремлевская, 6/20 тел./факс: (8432) 38-96-29о Z /ОJ "УТВЕРЖДАЮ"-^ярел-?- Директор Республиканского

81. Центра переподготовки и повышения квалификации

82. Горударственны^елужащих А.Н.Ершов/? Ui * 1999 г.1. АКТ О ВНЕДРЕНИИ

83. Зав. учебно-методическим отделом

84. И.о. декана факультета переподготовки государственных служащих

85. Зав. кафедрой информационных технологий управления, доцент\

86. Коршун E.H. Тазетдинова H.A.