Д.ф.-м.н.  А.К.Керимов,  к.ф.-м.н.  Р.И.Давудова

Азербайджанский Государственный Экономический Университет  adalat_kerim@mail.ru ,

Институт Кибернетики Национальной Академии Наук Азербайджана

                                                  d.rewana@rambler.ru

Эволюционный подход к решению одной

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

 Введение

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

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

Пусть дано множество допустимых однотипных сложных объектов

                                          ,                                                   (2.1)   

состояния  которых описываются набором некоторых числовых признаков

                                                                  (2.2)       

Здесь T-прямоугольная матрица, j-й признак i-го объекта, -ограниченная область изменения го признака. Множество объектов (2.1) считается допустимым, если признаки (2.2) определены областью значений , т.е. для , где .  Однотипными понимаются системы, описание состояний которых дано в одном и том же признаковом пространстве.  Таблицу Т называют признаковой матрицей. Каждый объект  из (2.1) можно определить отображением , где   пространство n-мерных векторов действительных чисел.

Определение 1. Подмножества  набора объектов X, удовлетворяющие  следующим условиям, называются классами:

        1);         2) ;

        3)  Для, где - мера сходства объекта  и класса.

        4)  Для и ,  где - мера сходства объектов  и .

Предполагается, что  количество классов l до классификации является известным [2].

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

    

3. Методы решения

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

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

Кратко изложим суть предложенного алгоритма:

Шаг 0 :

Положить k=0.

Шаг 1:

Генерируется случайная начальная популяция при известном  l.

Шаг 2: 

Вычисляется функция приспособленности (функционал качества классификации).

Шаг 3:

Случайно выбираются  из популяции к_m особей (классов)  и  d_i  битов (объектов)  для многоточечной  мутации.

Шаг 4:

Проводится многоточечная мутация. Полученные  особи  останутся  в популяции (заменяя своих «родителей»).

Шаг 5:

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

Шаг 6:

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

Шаг 7:

Выбираются  максимально далекие особи.

Шаг 8:

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

Шаг 9:

Вычисляется целевая функция.

Шаг10:

Проверить условия для завершения алгоритма. Если условие удовлетворяется, то остановиться; иначе, положить k=k+1 и перейти к шагу 3.

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

Литература:

1.      Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. – М., ФИЗМАТЛИТ, 2003, -432 стр.

2.      Зенкин А.И., Керимов А.К. Задача построения оптимальных классификаций динамических объектов. М.: ВЦ АН СССР, 1985 г., 20 с  Препринт.

3.      Керимов А.К., Давудова Р.И. Применение самоорганизующегося   генетического алгоритма в  одной задаче оптимальной классификации. // Известия НАНА. Сер.физ.-тех. и мат. наук. Т.XXV, №3, 2008. стр.35-40.

4.      Керимoв А.К., Давудова Р.И. Эволюционный алгоритм  для решения задачи автоматической классификации. // Искусственный интеллект и принятие решений. Институт системного анализа РАН. № 4, 2009, с. 74-79.

5.      Керимов А.К., Давудова Р.И. Программная реализация эволюционного алгоритма решения одной задачи автоматической классификации. // Программные   продукты и системы. №1, 2010 стр.15-18.