МЕТОД ЭВОЛЮЦИОННОЙ КЛАСТЕРИЗАЦИИ СЛОЖНЫХ ОБЪЕКТОВ И ПРОЦЕССОВ

МЕТОД ЭВОЛЮЦИОННОЙ КЛАСТЕРИЗАЦИИ СЛОЖНЫХ ОБЪЕКТОВ И ПРОЦЕССОВ

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

1. Расстояние Эвклида .
2. Максимальное расстояние по признакам .
3. Расстояние Махалонобиса .
4. Расстояние Хэмминга .

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

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

,                                                                  (1)

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

                        К традиционным методам кластерного анализа относят древовидную кластеризацию, двухвходовое объединение, метод К средних, метод дендритов, метод корреляционных плеяд и метод шаров [3]. Преимуществами указанных методов является их простота, инвариантность их техники относи­тельно характера исходных данных и используемых метрик. К недостаткам относят слабую формализо­ванность, что затрудняет применение вычислительной техники, а также низкую точность, следствием чего является предварительные оценки структуры пространства факторов и их информативности. Еще одним методом решения задачи кластеризации является использование самоорганизованной карты Кохонена [4]. Проблемой использования такой нейронной сети является выбор начальных весовых коэффициентов, непрерывный характер функционирования и эффективность, оценка которой на сего­дняшний день остается проблемой.

            В качестве альтернативного метода предлагаем использовать генетический алгоритм.           

Генетические алгоритмы – неклассический метод решения задачи оптимизации

            Первые варианты генетического алгоритма и рассмотрение аспектов его применения появились в работах [5], [6], [7], [8], [9]. Дальнейшие ис­следования показали его эффективность в решении инженерных, экономических экологических и других проблем. Главной идеей, лежащей в основе построения генетического алгоритма, является использова­ние идей природного отбора, селекции и мутаций. Его канонический вариант содержит такие этапы:

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

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

3.      Для каждого элемента  вычисляем значения фитнесс-функции   

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

5.      С вероятностью  выбираем одну из полученных особей и с вероятностью  осуществляем мута­цию.

6.      Полученную особь помещаем в новую популяцию .

7.      Повторяем шаги 3-6 раз.

8.      Переписываем элементы  в популяцию удаляя старые особи.

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

Формирование фитнесс-функции задачи кластеризации

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

Шаг 1. Значение фитнесс-функции положить равным нулю ()

Шаг 2. Задать количество кластеров и указать значение

Шаг 3. Выполнить инициализацию матрицы принадлежно­сти элементов к кластерам .

Шаг 4. Для всех объектов выполнить следующие шаги. Пусть

Шаг 5. Вычислить расстояние от -го объекта до центров всех кластеров, которые является осо­бями из выборочной популяции.

Шаг 6. Среди всех расстояний выбрать минимальное и отнести -й объект к -му кла­стеру. Внести соответствующую запись в матрицу .

Шаг 7.  

Шаг 8. Если шаги 5-7 выполнены для всех объектов, то получено значение фитнесс-функции , в про­тивном случае перейти на шаг 5.

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

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

Библиография

1. И.Д. Мандель. Кластерный анализ. Москва, Финансы и статистика, 1988.
2. A.N. Gorban, A.Yu. Zinovyev. Method of Elastic Maps and its Applications in Data Visualization and Data Modeling // Int. Journal of Computing Anticipatory Systems, CHAOS. - 2002. - Vol. 12. - P. 353-369.
3. В. Плюта. Сравнительный многомерный анализ в эконометрическом моделировании. – Москва: Фи­нансы и статистика, 1989.
4. T. Kohonen. Self-organization and associative memory. – New-York, 2d. ed., Springer Verlag, 1988.
5. A.S. Fraser. Simulation of genetic systems. J. of Theor. Biol., vol. 2, pp. 329-346, 1962.
6. A.S. Fraser. The evolution of purposive behavior. In Purposive  Systems, H. von Foerster, J.D. White, L.J. Peterson,  and  J.K.  Russel,  Eds.  Washington,  DC:  Spartan Books, pp. 15-23, 1968.
7. H.J. Bremermann, M. Rogson, S. Salaff. Search by Evolution.  In  Biophysics  and Cybernetic Systems. M. Maxfield, A. Callahan, and L. J. Fogel, Eds. Washington DC: Spartan Books, pp. 157-167, 1965.
8. J.H. Holland. Adaptive  plans  optimal  for  payoff-only environments. Proc. of the 2nd Hawaii Int. Conf. on System Sciences, pp. 917-920, 1969.
9. J.H. Holland. Adaptation in Natural and Artificial Systems. Ann Arbor: Univ. of Michigan Press, 1975.         
10. A.N. Skurikhin, A.J. Surkan. Identification of parallelism in neural networks by simulation with language J. Proc. of the Intern. Cohf. on KPL, APL Quote Quad, Vol.24, No.I, pp.230-237, Toronto, Canada, August 1993.