ISSN 2225-7551

УДК 519.85

 

А.И. Косолап, д-р физ.-мат. наук

А.А. Довгополая, аспирант

Украинский государственный химико-технологический университет, г. Днепропетровск, Украина

СФЕРИЧЕСКАЯ КЛАСТЕРИЗАЦИЯ ДАННЫХ

А.І. Косолап, д-р фіз.-мат. наук

А.О. Довгопола, аспірант

Український державний хіміко-технологічний університет, м. Дніпропетровськ, Україна

СФЕРИЧНА КЛАСТЕРИЗАЦІЯ ДАНИХ

Аnatoliy Kosolap, Doctor of Phisical and Mathematical Sciences

Alena Dovgopolaya, PhD student

Ukrainian State University of Chemical Technology, Dnepropetrovsk, Ukraine

SPHERICAL CLUSTERING OF DATA

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

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

Розглянуто задачу розбиття даних на сферичні кластери. Наведено нову оптимізаційну постановку задачі, яка є багатоекстремальною. Запропоновано метод точної квадратичної регуляризації для розв'язання оптимізаційної задачі. Цей метод порівнюється з методом найближчого сусіда для вирішення задач кластеризації даних. Численні приклади показують більш високу ефективність методу точної квадратичної регуляризації.

Ключові слова: метод точної квадратичної регуляризації, метод найближчого сусіда, сферична кластерізація даних, кластер, багатоекстремальні задачі.

In paper we consider a problem of dividing of data on spherical clusters. New optimising statement of a problem which is multiextreme is resulted. We offer a method exact quadratic regularization for the solution of this optimising problem. This method is compared to a method of the nearest neighbour for the solution of problems clustering of data. Many computational examples are provided to show the effectiveness of the proposed method.

Key words: exact quadratic regularization methods, nearest neighbour a method, spherical clustering of data, cluster, multiextremal problems.

Введение. Одной из основных задач в искусственном интеллекте и теории распознавания образов является разбиение данных на кластеры [12]. Как правило, данные (объекты) представляются точкой в n-мерном пространстве. Характеристикам объектов, которые необходимо разбить на кластеры, соответствуют компоненты n-мерной точки. Если расстояние между двумя точками мало, то эти точки входят в один кластер. В качестве расстояния может выбираться различная метрика пространства. Существуют эффективные методы разбиения данных на два кластера. Однако эффективное разбиение множества точек на более, чем два кластера, представляет сложную задачу [12]. Это связано с тем, что оптимальное разбиение точек на кластеры является многоэкстремальной задачей. В настоящее время для решения таких задач чаще используют генетические или эволюционные методы, которые основаны на случайном поиске и позволяют находить оптимальное решение задач кластеризации только с некоторой вероятностью [3]. В работе использован новый метод точной квадратичной регуляризация для решения многоэкстремальных задач, который показал лучшие результаты, в сравнении с генетическими и эволюционными методами, при решении многих тестовых задач [4].

Постановка задачи и метод ее решения. Будем рассматривать множество m точек в n-мерном евклидовом пространстве. Необходимо разбить это множество на k кластеров таким образом, чтобы каждая точка попала только в один кластер и точки с близкими расстояниями образовывали кластер. Будем покрывать множество заданных точек n-мерными шарами с разными радиусами ri. Необходимо определить центры Наукова бібліотека ЧНТУ © 2012