Метод точной квадратичной регуляризации в задачах кластеризации данных
В работе рассматривается задача кластеризации данных, в которой множество точек в n-мерном пространстве покрывается непересекающимися шарами − кластерами. Эта задача сводится к максимизации нормы вектора на невыпуклом допустимом множестве. Для решения оптимизационной задачи используется метод точ...
Gespeichert in:
| Veröffentlicht in: | Искусственный интеллект |
|---|---|
| Datum: | 2013 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/85146 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Метод точной квадратичной регуляризации в задачах кластеризации данных / А.И. Косолап // Искусственный интеллект. — 2013. — № 1. — С. 158–162. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-85146 |
|---|---|
| record_format |
dspace |
| spelling |
Косолап, А.И. 2015-07-19T19:05:41Z 2015-07-19T19:05:41Z 2013 Метод точной квадратичной регуляризации в задачах кластеризации данных / А.И. Косолап // Искусственный интеллект. — 2013. — № 1. — С. 158–162. — Бібліогр.: 7 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/85146 519.85 В работе рассматривается задача кластеризации данных, в которой множество точек в n-мерном пространстве покрывается непересекающимися шарами − кластерами. Эта задача сводится к максимизации нормы вектора на невыпуклом допустимом множестве. Для решения оптимизационной задачи используется метод точной квадратичной регуляризации, который показал преимущество над генетическими и эволюционными методами при решении многочисленных тестовых задач. В роботі розглядається задача кластеризації даних, в якій множина точок у n-вимірному просторі покривається кулями, що не перетинаються. Ця задача зводиться до максимізації норми вектору на неопуклій допустимій множині. Для розв’язку оптимізаційної задачі використовується метод точної квадратичної регуляризації, який показав перевагу над генетичними та еволюційними методами при розв’язку багатьох тестових задач. In this paper, we consider a problem clustering of data. The set of points cover of spheres in space ndimensional. This problem is reduced to of vector norm maximization on feasible nonconvex set. Then we use a method of an exact quadratic regularization for the solution of an optimizing problem which has shown its superiority over genetic and evolution methods at the solution of numerous test problems. ru Інститут проблем штучного інтелекту МОН України та НАН України Искусственный интеллект Обучающие и экспертные системы Метод точной квадратичной регуляризации в задачах кластеризации данных Метод точної квадратичної регуляризації в задачах кластерізації даних Method of an exact quadratic regularization into clustering problem of data Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Метод точной квадратичной регуляризации в задачах кластеризации данных |
| spellingShingle |
Метод точной квадратичной регуляризации в задачах кластеризации данных Косолап, А.И. Обучающие и экспертные системы |
| title_short |
Метод точной квадратичной регуляризации в задачах кластеризации данных |
| title_full |
Метод точной квадратичной регуляризации в задачах кластеризации данных |
| title_fullStr |
Метод точной квадратичной регуляризации в задачах кластеризации данных |
| title_full_unstemmed |
Метод точной квадратичной регуляризации в задачах кластеризации данных |
| title_sort |
метод точной квадратичной регуляризации в задачах кластеризации данных |
| author |
Косолап, А.И. |
| author_facet |
Косолап, А.И. |
| topic |
Обучающие и экспертные системы |
| topic_facet |
Обучающие и экспертные системы |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Искусственный интеллект |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Метод точної квадратичної регуляризації в задачах кластерізації даних Method of an exact quadratic regularization into clustering problem of data |
| description |
В работе рассматривается задача кластеризации данных, в которой множество точек в n-мерном пространстве
покрывается непересекающимися шарами − кластерами. Эта задача сводится к максимизации нормы
вектора на невыпуклом допустимом множестве. Для решения оптимизационной задачи используется
метод точной квадратичной регуляризации, который показал преимущество над генетическими и
эволюционными методами при решении многочисленных тестовых задач.
В роботі розглядається задача кластеризації даних, в якій множина точок у n-вимірному просторі
покривається кулями, що не перетинаються. Ця задача зводиться до максимізації норми вектору на
неопуклій допустимій множині. Для розв’язку оптимізаційної задачі використовується метод точної
квадратичної регуляризації, який показав перевагу над генетичними та еволюційними методами при
розв’язку багатьох тестових задач.
In this paper, we consider a problem clustering of data. The set of points cover of spheres in space ndimensional.
This problem is reduced to of vector norm maximization on feasible nonconvex set. Then we
use a method of an exact quadratic regularization for the solution of an optimizing problem which has shown
its superiority over genetic and evolution methods at the solution of numerous test problems.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/85146 |
| citation_txt |
Метод точной квадратичной регуляризации в задачах кластеризации данных / А.И. Косолап // Искусственный интеллект. — 2013. — № 1. — С. 158–162. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT kosolapai metodtočnoikvadratičnoiregulârizaciivzadačahklasterizaciidannyh AT kosolapai metodtočnoíkvadratičnoíregulârizacíívzadačahklasterízacíídanih AT kosolapai methodofanexactquadraticregularizationintoclusteringproblemofdata |
| first_indexed |
2025-11-25T20:43:15Z |
| last_indexed |
2025-11-25T20:43:15Z |
| _version_ |
1850530482551259136 |
| fulltext |
ISSN 1561-5359 «Искусственный интеллект» 2013 № 1 158
5К
УДК 519.85
А.И. Косолап
Украинский государственный химико-технологический университет, г. Днепропетровск
Украина, 49005, г. Днепропетровск, пр. Гагарина, 8
Метод точной квадратичной регуляризации
в задачах кластеризации данных
A.I. Kosolap
The Ukrainian State Chemical-Technological University, c. Dnipropetrovsk
Ukraine, 49005, c. Dnipropetrovsk, Gagarina st., 8
Method of an Exact Quadratic Regularization Into
Clustering Problem of Data
А.І. Косолап
Український державний хіміко-технологічний університет, м. Дніпропетровськ
Україна, 49005, м. Дніпропетровськ, пр. Гагаріна, 8
Метод точної квадратичної регуляризації
в задачах кластерізації даних
В работе рассматривается задача кластеризации данных, в которой множество точек в n-мерном пространстве
покрывается непересекающимися шарами − кластерами. Эта задача сводится к максимизации нормы
вектора на невыпуклом допустимом множестве. Для решения оптимизационной задачи используется
метод точной квадратичной регуляризации, который показал преимущество над генетическими и
эволюционными методами при решении многочисленных тестовых задач.
Ключевые слова: кластеризация данных, оптимизация,
метод точной квадратичной регуляризации.
In this paper, we consider a problem clustering of data. The set of points cover of spheres in space n-
dimensional. This problem is reduced to of vector norm maximization on feasible nonconvex set. Then we
use a method of an exact quadratic regularization for the solution of an optimizing problem which has shown
its superiority over genetic and evolution methods at the solution of numerous test problems.
Key words: clustering problem of data, optimization, method of an exact quadratic regularization.
В роботі розглядається задача кластеризації даних, в якій множина точок у n-вимірному просторі
покривається кулями, що не перетинаються. Ця задача зводиться до максимізації норми вектору на
неопуклій допустимій множині. Для розв’язку оптимізаційної задачі використовується метод точної
квадратичної регуляризації, який показав перевагу над генетичними та еволюційними методами при
розв’язку багатьох тестових задач.
Ключові слова: кластеризація даних, оптимізація, метод точної квадратичної регуляризації.
Введение
Одной из основных задач искусственного интеллекта и теории распознавания
образов является разбиение данных на кластеры [1], [2]. Необходимо объединить
данные в группы однотипных объектов – кластеры. Как правило, данные (объекты)
представляются точкой в n-мерном пространстве, которые необходимо разбить на
заданное число подмножеств непересекающимися шарами. Компоненты точек опре-
Метод точной квадратичной регуляризации в задачах кластеризации данных
«Штучний інтелект» 2013 № 1 159
5К
деляют параметры, которые характеризуют объекты. Расстояние между двумя точками
внутри одного кластера всегда меньше расстояния между точками разных кластеров.
В качестве расстояния может выбираться различная метрика пространства. Существуют
эффективные методы разбиения данных на два кластера. Однако разбиение множества
точек на более чем два кластера, представляет собой сложную задачу [1-3]. Это связано
с тем, что оптимальное разбиение точек на кластеры сводится к решению много-
экстремальной задачи, в которой необходимо найти точку глобального экстремума.
В настоящее время для решения таких задач чаще использует генетические или эво-
люционные методы, которые основаны на случайном поиске и позволяют находить
оптимальное решение задач кластеризации только с некоторой вероятностью [4], [5].
Кроме того, эти методы содержат большое количество параметров, от значений ко-
торых зависит их эффективность. В работе использован новый метод точной квадра-
тичной регуляризация для решения многоэкстремальных задач, который показал
лучшие численные результаты в сравнении с генетическими и эволюционными
методами, при решении многих тестовых задач [6].
Целью данной работы является сведение проблемы кластеризации данных к опти-
мизационной задаче и ее решение методом точной квадратичной регуляризации.
Постановка задачи и метод ее решения
Рассмотрим множество m точек },...,{ 1 m
xx в n-мерном евклидовом пространстве.
Необходимо разбить это множество на k сферических кластеров таким образом,
чтобы каждая точка попала только в один кластер и суммарное расстояние между
центрами покрывающих точки шаров было максимальным. Будем покрывать мно-
жество заданных точек n-мерными шарами с радиусом r. Диаметр шара определяет
максимально допустимое расстояние между точками одного кластера. Необходимо
определить центры },...,{ 1 k
zz шаров },|||||{ 22
rzxxB
i
i
≤−= ki ,...,1= так, чтобы
jiBB ji ≠∀Θ= ,I . Это условие равносильно системе неравенств
.,,...1,,4|||| 22 jikjirzz ij
≠=≥− (1)
Каждая точка j
i
Bx ∈ , что равносильно следующим ограничениям, при выполнении
условий (1)
.,...,1,0)||(||
1
22
mjrzx
k
i
ij
=≤−−∏
=
(2)
В качестве критерия оптимальности покрытия множества точек },...,{ 1 m
xx
непересекающимися шарами, выберем максимизацию суммарного расстояния между
центрами шаров. Это равносильно максимизации целевой функции
∑ ∑
= +=
−
k
j
k
ji
ij
zz
1 1
2.|||| (3)
Решение задачи (1 − 3) определит центры шаров, которые разобьют множество то-
чек },...,{ 1 m
xx на k кластеров. Данная постановка задачи кластеризации данных (1 − 3)
проще существующих [6]. Задача (1 − 3) имеет nk искомых переменных },...,{ 1 k
zz и
m+k(k−1)/2 ограничений (1), (2). Целевая функция (3) является выпуклой, а допустимое
множество (1), (2) − невыпуклым, и задача (1 − 3) − многоэкстремальна. Классические
методы ее решения, такие, например, как методы внутренней точки, позволяют
Косолап А.И.
«Искусственный интеллект» 2013 № 1 160
5К
найти только локальное решение, при этом они не всегда могут найти допустимое
решение. Поэтому используем метод точной квадратичной регуляризации [7] для ре-
шения задачи (1 − 3), который предназначен для решения многоэкстремальных задач.
Преобразуем задачу (1 − 3) к виду
},,...,1,,4||||
,,...,1,0)||(||,|||||min{
22
1
22
1 1
2
kjirzz
mjrzxzszzz
ij
k
i
ij
k
j
k
ji
ij
=≥−
=≤−−≤+−− ∏∑ ∑
== += (4)
где z – новая переменная, а параметр s удовлетворяет условию
},,...,{,|||||||| *
1
**2*
1 1
2**
k
k
j
k
ji
ij
zzZZzzs =≥−−∑ ∑
= +=
*
Z − решение задачи (1 − 3). Используем замену ZAy = , где матрица A порядка
)1()1( +×+ knkn равна
+121
...
............
0...10
0...01
kn
yyy
,
а вектор ),( zZZ = , для преобразования задачи (4) к следующей
}.,...,1,,4||||,,...,1
,0)||(||,|||||||||||min{||
22
1
22
1 1
222
kjiryymj
ryxysyyy
ij
k
i
ij
k
j
k
ji
ij
=≥−=
≤−−≤+−− ∏∑ ∑
== += (5)
Зададим такое значение параметра q > 0, при котором ограничения задачи
}||||,,...,1,,4||||||||,,...,1,||||
)||(||,||||)1(|||||||min{||
22222
1
22
1 1
222
dyqkjidryyyqmjdyq
ryxdyqsyyy
ij
k
i
ij
k
j
k
ji
ij
==≤+−−=≤
+−−≤−++−− ∏∑ ∑
== += (6)
будут выпуклыми, за исключением условия dyq =
2|||| . В задаче (6) значение новой
переменной d необходимо определить. Пусть ),(
0
0 dy − решение соответствующей
выпуклой задачи
},||||,,...,1,,4||||||||,,...,1,||||
)||(||,||||)1(|||||min{
22222
1
22
1 1
22
dyqkjidryyyqmjdyq
ryxdyqsyyd
ij
k
i
ij
k
j
k
ji
ij
≤=≤+−−=≤+
+−−≤−++−− ∏∑ ∑
== += (7)
тогда, если условие
0
20 |||| dyq = выполняется, то решение ),(
0
0 dy − определяет опти-
мальное разбиение точек на k сферических кластеров. В противном случае, необходимо
решать задачу
2 2 2 2 2
1 1 1
2 2 2 2
max{|| || | || || ( 1) || || , (|| || )
|| || , 1, ..., , || || || || 4 , , 1, ..., }
kk k
j i j i
j i j i
j i
y y y s q y d x y r
q y d j m q y y y r d i j k
= = + =
− − + + − ≤ − − +
+ ≤ = − − + ≤ =
∑ ∑ ∏ (8)
и найти минимальное значение d
*
, при котором выполняется условие *2* |||| dyq = , где
y
*
− решение задачи (8) при фиксированном значении d
*
. Будем решать задачу (8)
Метод точной квадратичной регуляризации в задачах кластеризации данных
«Штучний інтелект» 2013 № 1 161
5К
следующим образом. Выберем интервал h > 0 изменения переменной hdd +=
0
, где
0
d – решение задачи (7) и, решим для этого значения переменной d задачу (8) моди-
фицированным методом внутренней точки. В этом методе на i-й итерации
максимизация квадрата нормы вектора y на выпуклом допустимом множестве задачи
(8), заменяется максимизацией линейной функции yy
Ti )( 1− , где 1−iy − решение зада-
чи (8) на предыдущей итерации. Таким образом, на каждой итерации модифициро-
ванного метода решается задача выпуклой оптимизации. При увеличении перемен-
ной d значение целевой функции задачи (8) монотонно возрастает [7], пока не вы-
полнится условие *2* |||| dyq = , тогда точка *
y определит оптимальное разбиение точек
на кластеры. Рассмотренная последовательность преобразований задачи (1 − 3) к
эквивалентной задаче (8), при условии dyq =
2|||| , есть метод точной квадратичной
регуляризации (EQR) [7].
Заметим, что увеличение параметра q не меняет решение задачи (8), но при
таком увеличении происходит сглаживание локальных максимумов задачи (8). При
больших значениях q каждое ограничение задачи (8)
mjdyqryx
k
i
ij ,...,1,||||)||(|| 2
1
22
=≤+−−∏
=
будет стремиться к шару, а допустимая область этой задачи – к пересечению шаров.
Рассмотренная задача (1 − 3) решалась при фиксированном количестве кластеров.
Метод EQR позволяет найти минимальное количество кластеров *
k . Для *
kk < допу-
стимое множество задачи (1 − 3) будет пустым. Это означает, что для решения задачи
(8), при больших значениях *
d , будет выполняться условие *2* |||| dyq < . Минимальное
значение k , при котором допустимое множество задачи (8) не пусто, определит мини-
мальное число кластеров.
Пример
На рис. 1 приведен расчет центров шаров кластеров для точек на плоскости
(1,2; 2,3; −1,3; 4,1; 4,−1; 3,−2; 5,0; 1,5; 4,4; 6,3; 5,5; 7,4; 5,−2)
при условии, что r
2
=3 и k =3. Задача (8) решалась при значениях параметров s = 200,
q = 100. Центры шаров кластеров найдены в точках
(4.17082, −072361; 0.367281, 3.578124; 5.591608, 4.683216).
Рисунок 1 – Три кластера
Косолап А.И.
«Искусственный интеллект» 2013 № 1 162
5К
Выводы
В работе приведена новая оптимизационная постановка задачи построения
сферических кластеров в n-мерном евклидовом пространстве. Для решения полученной
многоэкстремальной задачи использовался метод точной квадратичной регуляри-
зации, эффективность которого проверена в многочисленных экспериментах.
Литература
1. Хант Э. Искусственный интеллект / Э. Хант; пер с англ. Д.А. Белова и Ю.И. Крюкова ; под. ред.
В.Л. Стефанюка. – М. : Мир, 1978. – 560 с.
2. Ту Дж. Принципы распознавания образов /Дж. Ту, Р. Гонсалес ; пер. с англ. И.Б. Гуревича ; под.
ред. Ю.И. Журавлева. – М. : Мир, 1978. – 413 с.
3. Мандель И.Д. Кластерный анализ / И.Д. Мандель. – М. : Финансы и статистика. – 1988. – 176 с.
4. Kenneth V.P. Differential Evolution. A Practical Approach to Global Optimization / V.P. Kenneth, R.M. Storn,
J.A. Lampinen. – Berlin Heidelberg: Springer-Verlag, 2005. – 542 p.
5. Сокуренко В.М. Числове дослідження стохастичних методів безперервної глобальної оптимізації /
В.М. Сокуренко, В.С. Неділюк // Наукові вісті НТУУ «КПІ». – 2012. – № 1. – С. 81-87.
6. Sherali H.D. A Global Optimization RLT-based Approach for Solving the Hard Clustering Problem /
H.D. Sherali, D. Jitamitra // Journal of Global Optimization. – 2005. – 32. – P. 281-306.
7. Косолап А.И. Метод квадратичной регуляризации для решения систем нелинейных уравнений /
А.И. Косолап // Журнал обчислювальної та прикладної математики. – 2010. – №4. – С. 44-50.
Literatura
1. Hunt E.B. Artificial Intelligence. Academic Press. Nev York, San Francisco, London, 1975. 468 p.
2. Tou J.T., Gonzalez R.C. Pattern Recognition Principles. Addison-Wesley Publishing Company. London-
Amsterdam-Dom Mills, Ontario-Sydney-Tokyo. 1974. 378 p.
3. Mandel I.D. Cluster Analisys. Finances and Statistica. Moscow. 1988. 176 p. (rus)
4. Kenneth V.P., Storn R.M., Lampinen J.A. Differential Evolution. A Practical Approach to Global
Optimization. Springer-Verlag. Berlin Heidelberg. 2005. 542 p.
5. Sokurenko V.M. Naukovi visti NTUU “KPI”. No. 1. 2012. Pp. 81–87. (rus)
6. Sherali H.D., Jitamitra D. J. Global Optim. No. 32. 2005. Pp. 281–306.
7. Kosolap A.I. J. Comp. & Appl. Math. No. 4. 2010. Pp. 44–50. (rus)
A.I. Kosolap
Method of an Exact Quadratic Regularization Into Clustering Problem of Data
Partition of data into clusters is the most important problem of an artificial intellect and the
theory of pattern classification. Data is represented by points of n-dimensional space. We consider
this problem in n-dimensional space and use the spherical clusters. It is necessary to find the
centers of the spheres which contain all points. Spheres should not intersect and the sum of the
distances between their centers should be maximum. Such a statement concerning this problem for
clustering the data is new and more simple [6].
This type of problem clustering of data is transformed to the maximization of the vector
norm on nonconvex set. This problem is multiextreme. We use the method of exact quadratic
regularization for its solution. This method transforms a multiextreme problem to maximization of
a norm vector on a convex set. This convex set is approximated by the intersection of spheres. We
use a dual method for the solution of this problem. This auxiliary problem is used for searching the
starting point of the method of exact quadratic regularization. We use the modification of an
interior point method for the solution of the problem of a maximum vector norm on convex set.
The method of the exact quadratic regularization has shown its superiority over the genetic
and evolutionary methods at the solution of numerous test problems. The given method can be used
for the data on clusters that was confirmed by numerous experiments.
Статья поступила в редакцию 19.11.2012.
|