Кластерний аналіз для багатовимірних об’єктів в умовах нечітких даних
This article presents many different areas of practical applications of multivariate cluster analysis under conditions of fuzzy initial data that are described in the literature. New algorithms and formula expressions are proposed for combining various multi-dimensional objects, the parameters of wh...
Збережено в:
| Дата: | 2021 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2021
|
| Теми: | |
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/239829 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1867334415991963648 |
|---|---|
| author | Zack, Yuriy |
| author_facet | Zack, Yuriy |
| author_institution_txt_mv | [
{
"author": "Yuriy Zack",
"institution": null
}
] |
| author_sort | Zack, Yuriy |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2021-09-16T11:48:22Z |
| description | This article presents many different areas of practical applications of multivariate cluster analysis under conditions of fuzzy initial data that are described in the literature. New algorithms and formula expressions are proposed for combining various multi-dimensional objects, the parameters of which are given by fuzzy-sets, into clusters along with calculating the coordinates of the centroids of their membership functions. Various types of clustering criteria are formulated in the form of minimizing the weighted average and the sum of distances between the centroids of objects and clusters presented in different metrics, as well as maximizing the distances between the centroids of different clusters. The formulations and mathematical models of three different NP-hard problems of multidimensional clustering in fuzzy-data conditions are proposed; while solving them any of the considered optimality criteria can be used. Heuristic algorithms for the approximate solution of two formulated problems have been developed. The algorithm for solving the 1st problem is illustrated with a numerical example. The obtained results can serve as a direction for further research and have wide practical applications. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2021.2.02 |
| first_indexed | 2025-07-17T10:27:23Z |
| format | Article |
| fulltext |
Ю.А. Зак, 2021
18 ISSN 1681–6048 System Research & Information Technologies, 2021, № 2
УДК 519.87
DOI: 10.20535/SRIT.2308-8893.2021.2.02
КЛАСТЕРНЫЙ АНАЛИЗ ДЛЯ МНОГОМЕРНЫХ ОБЪЕКТОВ
В УСЛОВИЯХ НЕЧЕТКИХ ДАННЫХ
Ю.А. ЗАК
Аннотация. Приведены описанные в литературе множества различных облас-
тей практических приложений многофакторного кластерного анализа в усло-
виях нечетких исходных данных. Предложены новые алгоритмы и формуль-
ные выражения объединения различных многомерных объектов, параметры
которых заданы fuzzy-множествами, в кластеры и вычисления координат цен-
троидов их функций принадлежности. Сформулированы различные виды кри-
териев кластеризации в виде минимизации средневзвешенной и представлен-
ной в различной метрике суммы расстояний между центроидами объектов и
кластеров, а также максимизации расстояний между центроидами различных
кластеров. Предложены постановки и математические модели трех различных
NP-сложных задач многомерной кластеризации в условиях fuzzy-данных, при
решении которых может быть использован любой из рассмотренных критери-
ев оптимальности. Разработаны эвристические алгоритмы приближенного ре-
шения двух сформулированных задач. Алгоритм решения первой задачи про-
иллюстрирован на числовом примере. Полученные результаты могут
послужить направлением дальнейших исследований и найти широкое практи-
ческое применение.
Ключевые слова: кластерный анализ, многомерные функции принадлежно-
сти, центроиды fuzzy-множеств объектов и кластеров, центры тяжести и сере-
дины сечений нечетких множеств, критерии оптимальности и алгоритмы кла-
стеризации.
ВВЕДЕНИЕ
Кластерный анализ — это разбиение заданного множества, состоящего из N
многомерных объектов ),,1( Ni , на некоторое количество подмножеств
(групп), называемых кластерами. При этом каждый кластер должен вклю-
чать близкие по свойствам, характеристикам или своим значениям объекты,
а объекты разных кластеров существенно отличались друг от друга [1–4; 12].
Количество таких кластеров kO равно K , ),,1 ( Kk где NK . Коли-
чество кластеров может быть задано или определяться в процессе реализа-
ции алгоритма при возможных заданных граничных значениях на количест-
ва кластеров. Каждый из объектов может определяться одним параметром,
представленным числовым или качественным значением, либо некоторым
вектором параметров в m-мерном пространстве ,j
ix .,,1, ,,1 Nimj
Тогда каждый кластер также представлен некоторым множеством точек в
этом m-мерном векторном пространстве. Так как разные параметры (свойст-
ва) объектов могут быть представлены в различных единицах и различных
диапазонах изменения, что может исказить или даже дать неправильный
результат, необходимо привести эти данные к одним и тем же единицам из-
мерения. Это достигается применением коэффициентов масштабирования
Кластерный анализ для многомерных объектов в условиях нечетких данных
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 19
значений отдельных свойств. Степень важности различных свойств учиты-
вается введением соответствующих весовых коэффициентов.
Выборка таких объектов должна быть однородной, т.е. не содержать не
характерных для данного класса задач «выбросов».
Степень сходства между данными из одного кластера должна быть как
можно более высокой, а между данными из разных кластеров — как можно
меньшей, в связи с чем концепция подобия имеет здесь решающее значение.
В качестве степени сходства между данными из одного кластера могут быть
использованы эвклидово расстояние, а также суммарное квадратичное от-
клонение объектов кластера от их центров (центроидов). Квадратичное евк-
лидово расстояние способствует увеличению контрастности кластеров. Рас-
стояния между центроидами данных различных кластеров, которые должны
быть максимизированы, могут также определяться суммарными средне-
взвешенными квадратичными или линейными значениями. Каждый объект
iA и каждый кластер kO являются нечеткими множествами. Алгоритм кла-
стеризации — это определение функции или некоторого решающего прави-
ла, на основе которого каждому объекту ставится в соответствие номер кла-
стера, к которому этот объект принадлежит.
Область применений кластерного анализа очень широка. Эти методы
используются в медицине, технической диагностике, психологии, биологии,
археологии, маркетинге и во многих других дисциплинах [9–19].
В медицине пациенты со схожими характеристиками и симптомами по
результатам иерархического кластерного анализа могут быть сгруппирова-
ны таким образом, чтобы можно было определить наличие и степень неко-
торого заболевания и начать соответствующие лечебные меры в соответст-
вии с установленным диагнозом (см., например, [10, 16, 17, 19]. Примеры
использования кластерного анализа в экономике для классификации ситуа-
ций приведены в работе [9]. В системе государственного управления клас-
терный анализ позволяет распределить налогоплательщиков по категориям
внимания, к которым будут применяться соответствующие комплексы ме-
роприятий [13]. В маркетинге можно определить сегменты клиентов с ана-
логичными моделями покупательского поведения, а также перечни продук-
тов, пользующихся наибольшим спросом среди каждой из групп
покупателей. Это даст возможность координации и повышения эффектив-
ности маркетинговой деятельности конкретно с определенными сегментами
покупателей, что, в свою очередь, приведет к увеличению объема продаж. В
проблемах защиты окружающей среды по результатам мониторинга могут
быть определены зоны в воздухе с определенными степенями загрязнения,
что даст возможность принять любые необходимые мероприятия по улуч-
шению ситуации. В биологии с помощью кластерного анализа анализирую-
тся сложные сети взаимодействующих генов, состоящие порой из сотен или
даже тысяч элементов. В информатике кластерный анализ используется для
«интеллектуальной» группировки результатов, распознавания изображений
[11] при поиске файлов и веб-сайтов, а также других информационных объ-
ектов, предоставляя пользователю возможность быстрой навигации для
ускорения поиска необходимой ему информации.
Большое количество практических приложений основаны на том, что
решения принимаются, опираясь на нечеткие данные. Разные параметры
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 20
или свойства объектов могут быть представлены нечеткими подмножества-
ми с функциями принадлежности вида (см., например, [7, 8, 14, 15]):
)]}([,{ xx x ; )]([)]([)( ixi
Cx
kiCY xCY
i
k
ki
,
где i — весовые коэффициенты, которые в частном случае могут быть
равны 1.
Если при так называемой четкой или жесткой кластеризации каждый
объект может принадлежать только одному кластеру, то при нечеткой кла-
стеризации каждый объект с различными значениями функции принадлеж-
ности может одновременно принадлежать сразу нескольким кластерам. Од-
ним из наиболее широко используемых алгоритмов нечеткой кластеризации
является алгоритм (FCM) [1, 7, 12]). Любой объект ix имеет некоторый на-
бор данных, определяющих его принадлежность к некоторому кластеру.
В алгоритме нечетких С-средних центроид кластера kO kC является сред-
ним значением всех точек в многомерном пространстве, взвешенных по
степени их принадлежности к данному кластеру:
r
xGx
r
xCx
k
x
xxx
C
ki
ki
],[
]),([
.
Здесь r — показатель степени, с увеличением которого растет показа-
тель нечеткости кластера.
Алгоритм FCM минимизирует функционал вида
)(]),([min 2
11
ki
r
x
C
i
K
k
zxxxF
k
.
Этот алгоритм осуществляет распределение N объектов, заданных не-
четкими множествами, по K определяемыми нечеткими множествами кла-
стерам в соответствии с выбранным критерием оптимальности. Эффектив-
ность получения результата повышается при реализации алгоритма не с заранее
заданным, а с автоматическим определяемым количеством кластеров.
ПАРАМЕТРЫ КЛАСТЕРОВ, ВКЛЮЧАЮЩИЕ ОБЪЕКТЫ,
ПРЕДСТАВЕННЫЕ НЕЧЕТКИМИ МНОЖЕСТВАМИ
Рассматриваются объекты, параметры или свойства которых, а также пара-
метры кластеров представлены нечеткими подмножествами с функциями
принадлежности вида
}|)(, { iiiAii XxxxA
i
, ]1,0[)( iA x
i
,
где
NixiA
X
X
i
i
i
,,1, 1)(
max
min
; (1)
}|)(, { kkkOkk ZzzzO
k
,
Кластерный анализ для многомерных объектов в условиях нечетких данных
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 21
где 1)(
max
min
kZ
Z
Z
z
k
k
k
, .,,1 Kk (2)
Здесь Ni ,,1 — индексы, N — количество рассматриваемых объек-
тов; Kk ,,1 , — индексы и количество априори рассматриваемых кластеров.
Пусть нечеткое множество кластера , kO включающего некоторое под-
множетво объектов , ki OA определяется согласно выражению
)( kO z
k
}|)({max iiA
OA
Xxx
i
ki
, .,,1 Kk
Образование функции принадлежности такого кластера (ABCDEFHG),
включающего два объекта иллюстрирует рис. 1.
Каждый объект может определяться некоторым множеством свойств
(параметров) j
ix , количество которых равно m, значение каждого из кото-
рых определяется функцией принадлежности )( j
iA
xj
i
) j
i
j
i Xx , . Кластеры
в этом случае также являются многомерными и выражены вектором функ-
ций принадлежности той же размерности m . Обобщенная функция принад-
лежности этого объекта и кластера kO могут быть вычислены, например, по
формулам:
}|)(, { iiiAi Xxxx
i
) (,{
1
j
iA
j
i
j
m
j
xx j
i
}| j
i
j
i Xx , 1, , ;i N (3)
}|)(, { kkkZk Zzzz
k
)(,{
1
j
kZ
j
i
j
m
j
zz j
k
) }| j
k
j
k Zz , .,,1 Kk (4)
Здесь j — весовые коэффициенты, определяющие значимость каждо-
го из этих свойств, величины которых удовлетворяют соотношениям
10 j , 1, ,j m , 1
1
j
m
j
.
В качестве основной характеристики как отдельных объектов, так и
каждого из кластеров выберем координату абсцисс центра тяжести соот-
ветствующего fuzzy-множества, которые рассчитываются по формулам
(см., например, [5, 6]):
Рис. 1. Функция принадлежности нечетких множеств двух объектов и кластера
B C E F
2-й объект
1-й объект
кластер
A G
y
x
1,0
H
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 22
j
i
j
i
j
i
j
i
x
x
j
iA
j
iA
j
ij
i
x
xx
g
max
min
)(
)(
, ;,,1 mi
i
i i
i
X
X iA
iAi
i
x
xx
g
max
min )(
)(
, 1, , ;i N (5)
)(
)(
max
min
j
kZ
j
kZ
j
k
Z
Z
j
k
z
zz
G
j
k
j
k
j
k
j
k
, 1, ,j m ,
)(
)(
max
min kZ
kZk
Z
Z
k z
zz
G
k
k
k
k
, 1, , .k K (6)
Ограничимся рассмотрением нечетких множеств объектов с функцией
принадлежности треугольного или трапецеидального вида (рис. 2):
),,()( iiiiA bcax
i
, ), ,,()( 21 iiiiiA bccax
i
,
),,()( kkkkA bcaz
k
, )( kA z
k
),, ,,( 21 kkkk bcca
)](, )(, )( ,)([ 11
2
1
1
11 p
k
p
k
p
k
p
k
p
k ZbZcZcZaZ ,
)](,[min)( 1 p
ki
p
k ZaaZa , i
p
k bZb [max)( 1 , )]( p
kZb , (7)
)( 1
1
p
kZc = ic1[ min , )](1
p
ki Zc , )( 1
2
p
kZc = ic2[ max , )](2
p
ki Zc , (8)
)( 1
1
p
kZc = min[ ic , )](1
p
ki Zc , )( 1
2
p
kZc = max[ ic , )](2
p
ki Zc . (9)
Формулы для вычисления значения функции принадлежности для этих
fuzzy-множеств приведены, например, в работе [5]. Координаты оси абсцисс
центра тяжести для треугольных fuzzy-множеств могут вычислены по про-
стым формулам [5, 6]:
)]()()([
3
1
)(1 iiii AbAcAaAG , )]()()([
3
1
)(2 kkkk AbAcAaAG . (10)
Для трапециевидных fuzzy-множеств в качестве координаты )(1 kOG
может быть принято значение, вычисленное по следующему алгоритму.
Вычислим площади соответствующих частей fuzzy-множества: двух
треугольников, которые обозначим )(1 kOS и )(3 kOS и прямоугольника,
которую обозначим как ), (2 kOS а также координаты оси абсцисс центров
Рис. 2. Функции принадлежности fuzzy-множеств треугольного и трапециевидного
типа
y
1,0
a c b x
y
1,0
a c1 c2 b x
Кластерный анализ для многомерных объектов в условиях нечетких данных
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 23
тяжести этих частей, которые соответственно равны , )]([ 1 kOSG )]([ 3 kOSG
и )] ([ 2 kOSG .
Определим весовые коэффициенты
)()()(
)(
321
1
1
kkk
k
OSOSOS
OS
;
)()()(
)(
321
2
2
kkk
k
OSOSOS
OS
;
)()()(
)(
321
3
3
kkk
k
OSOSOS
OS
,
где 1321 .
Тогда координаты оси абсцисс центра тяжести трапеции равна
)]([)]([)]([)( 332211 kkkk OSGOSGOSGOG . (11)
Если объект iA с треугольной функцией принадлежности включается в
кластер kO с трапецеидальной функцией принадлежности, то параметры
функции принадлежности кластера изменяются в соответствии со следую-
щими выражениями:
;)()( if, )(
, )()( if), (
)(
iki
ikk
k AaOaAa
AaOaOa
Oa
; )()( if, )(
, )()( if), (
iki
ikk
k AbObAb
AbObOb
Ob
; )()( if, )(
, )()( if), (
)(
1
11
1
iki
ikk
k AcOcAa
AcOcOc
Oc
. )()( if, )(
, )()( if), (
)(
2
22
2
iki
ikk
k AcOcAc
AcOcOc
Oc
Если первые два объекта iA и vA с треугольными функциями принад-
лежности объединяются в один кластер, то параметры этого кластера опре-
деляются по формулам:
; )()( if, )(
, )()( if, )(
)(
ii
i
k AaAaAa
AaAaAa
Oa
);()( if), (
),()( if), (
)(
ii
i
k AbAbAb
AbAbAb
Ob
);()( if), (
),()( if, )(
)(1
ii
i
k AcAсAa
AcAсAс
Oc
).()( if), (
),()( if, )(
)(2
ii
i
k AcAсAc
AcAсAс
Oc
В качестве другой характеристики каждого fuzzy-множества в задачах
кластерного анализа может быть принята средневзвешенная координат оси
абсцисс середин сечений этих множеств при различных значениях ординаты
функции принадлежности (рис. 3), т.е. точек на прямой 21 ZZ .
Обозначим координаты оси абсцисс середины соответствующих сечений
)( x . Здесь — значение координаты y в этом сечении. Как правило,
0
0 0,1
21
Qq
.
Тогда ), ()(
0
qq
Q
q
xZx
(12)
где 0 0,1 q — весовые коэффициенты, причем .0,1
0
q
Q
q
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 24
В частном случае 0,1 q ; .,,1, 0 Qq
КРИТЕРИИ ОПТИМАЛЬНОСТИ
В качестве критериев оптимальности при отнесении множества, включаю-
щего N объектов к одному из K кластеров, могут быть приняты параметры
расстояний в различных метриках между центрами тяжести объектов и кла-
стеров, а также между центроидами кластеров kG и lG .
;min|)|
1
1
1
1
ikki
OAk
K
k
gG
N
F
ki
(13)
;min)(
1 22
1
2
ikki
OAk
K
k
gG
N
F
ki
(14)
minmax 3
1
3
ikki
OA
K
k
gGF
ki
; (15)
max1
11
4
lkkl
K
kl
K
k
GGF ; (16)
max)( 22
11
5
lkkl
K
kl
K
k
GGF ; (17)
.max max 3
),(11
6
lkkl
lk
K
kl
K
k
GGF (18)
В выражениях (13)–(18) и в дальнейшем kG и ig — соответственно
координаты центров тяжести оси абсцисс центроидов k-го кластера и i-го
объекта, а также между центроидами кластеров kG и lG .. Здесь p
ki ,
10 p
ki 3,2,1p — весовые коэффициенты, сумма которых в каждом
из этих выражений равна .,,1, 1 Kkp
ki
OA ki
Весовые коэффициенты
10 p
kl , 1,,1, 3,2,1 Kkp , Kl ,,2 , 1
1
p
kl
K
kl
; kN — коли-
чество объектов, включенных в кластер kO .
Рис. 3. Горизонтальные сечения функций принадлежности fuzzy-множеств
y
s6=1,0
a c Z2 b x
s5
s4
s3
s2
s1
s0
Z1
y
s6=1,0
a c1 c2 Z2 b x
s5
s4
s3
s2
s1
s0
Z1
Кластерный анализ для многомерных объектов в условиях нечетких данных
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 25
Kроме того, могут использоваться многокритериальные подходы при-
нятия решений с использованием минимизации аддитивной свертки крите-
риев, как, например,
42111 )1(
11
F
KK
F
K
; 54232 )1(
11
F
KK
F
K
; (19)
66353 )1(
1
1
F
KK
F
K
, (20)
а также
68174 )1(
11
F
KK
F
K
; 410395 )1(
11
F
KK
F
K
; (21)
4122116 )1(
11
F
KK
F
K
; 5133127 )1(
11
F
KK
F
K
; (22)
6152148 )1(
11
F
KK
F
K
; 6171169 )1(
11
F
KK
F
K
. (23)
Здесь p , 0< . 1 p 1,2, ,17p — весовые коэффициенты, сумма
которых в каждом из этих выражений равна 1.
Если каждый объект представлен некоторым вектором параметров
в m-мерном пространстве ,j
ix ,,,1 ,,,1 Nimj то в критерии опти-
мальности кластеризации могут быть представлены в виде:
j
i
j
k
j
m
jOXk
xz
N
E
ki
1
1
1
1
min , ,)(
1
min 2
2
1
2
j
i
j
k
j
m
jOXk
xz
N
E
ki
j
i
j
k
j
mjOXk
xz
N
E
ki
3
1
3 max
1
min ; (23)
j
l
j
k
j
m
j
K
kl
K
k
zz
KK 1
111
1 )1(
1
max ,
m
j
j
l
j
k
j
K
kl
K
k
zz
KK 1
2
2
11
2 )(
)1(
1
max ,
m
j
j
l
j
k
j
mj
K
kl
K
k
j
l
j
k
zz
zzK 1
3
111
3 max
1
max . (24)
Здесь j
p , . 10 j
p ;3,2,1p и j
r , . 10 j
r 1,2,3; r — весовые
коэффициенты, сумма которых в каждом из этих выражений равна 1.
Отметим, что в выше приведенных выражениях, так и в других крите-
риях и алгоритмах принятия решений задач кластеризации в условиях не-
четких данных, вместо значений координаты абсцисс центра тяжести нечет-
ких множеств могут использоваться так и середины соответствующих
сечений этих fuzzy-множеств.
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 26
ПОСТАНОВКИ ЗАДАЧ КЛАСТЕРИЗАЦИИ
Приведенные ниже постановки задач предусматривают работу с многомер-
ными объектами и кластерами, параметры которых представлены нечеткими
множествами. Рассмотрим три различные постановки задачи в условиях не-
четких данных.
Задача 1. Определены функции принадлежности всех характеристик
(признаков) каждого из K кластеров, }|)(, { kkkOkk ZzzzO
k
, ) ( kO z
k
],1,0[ k=1,…, K, а также известны функции принадлежности всех характери-
стик N многомерных объектов }|)(, { iiiAii XxxxA
i
, ]1,0[) ( iA x
i
,
1, ,i N . Необходимо в соответствии с одним из выше приведенных
критериев оптимальности распределить это множество объектов среди
этих K кластеров.
Такая постановка задача очень характерна для медицинской диагности-
ки, когда определены различные факторы отсутствия наличия и степени се-
рьезности различных диагнозов и заболеваний, для технической диагности-
ки, когда установлены признаки различного вида неисправностей, а также в
задачах определения и классификации аварийных ситуаций причин и по-
следствий экологических катастроф.
Задача 2. Известны функции принадлежности всех характеристик (при-
знаков) N многомерных объектов }|)(, { iiiAii XxxxA
i
, ]1,0[ )( iA x
i
,
Ni ,,1 . Установлено только количество кластеров K. Необходимо в про-
цессе решения задачи определить функции принадлежности всех характери-
стик (признаков) каждого из K кластеров, }|)(, { kkkOkk ZzzzO
k
,
, ]1,0[) ( kO z
k
Kk ,,1 , и отнести каждый из объектов iA , ,,,1 Ni
только к одному из этих кластеров в соответствии с одним из выше приве-
денных критериев оптимальности (19)–(24).
Задача 3. Известны только функции принадлежности всех характерис-
тик (признаков) N многомерных объектов iA , 1, ,i N . Количество вы-
деляемых кластеров заранее не определено и может быть только ограничено
некоторым числом B. Необходимо определить количество кластеров
, 1 BK а также функции принадлежности всех характеристик (призна-
ков) каждого из этих K, отнести каждый из объектов iA , ,,,1 Ni только
к одному из этих кластеров в соответствии с одним из выше приведенных
комплексных критериев оптимальности (19)–(24).
Отметим, что задачи 2 и 3 являются задачами NP -сложности и для
решения этих задач в условиях большой размерности могут быть предложе-
ны только эвристические алгоритмы приближенного решения
АЛГОРИТМ КЛАСТЕРНОГО АНАЛИЗА
Рассмотрим алгоритмы решения двух различных выше сформулированных
задач. В двух описанных алгоритмах A.1 и A.2 решения задачи 1 использу-
ется один из критериев оптимальности 61 FF , приведенных в формулах
(13)–(18).
Кластерный анализ для многомерных объектов в условиях нечетких данных
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 27
В начале работы алгоритмов приведем единицы и диапазоны измене-
ния значений всех параметров объектов и кластеров (координат оси абсцисс
этих параметров) к одним и тем же безразмерным единицам измерения:
]min; min[min
11
min
j
k
Kik
j
i
Ni
j xxX
, ]max; max[max
11
max
j
k
Kik
j
i
Ni
j xxX
,
)( minmax
jjj XXX .
Обозначим: jj XX min , jj XX min . Тогда
j
j
ijj
i
X
x
Xx , ;,,1 Ni
j
j
kjj
k
X
x
Xx , .,,1 Kk
Алгоритм А.1.
1. Вычислим координаты абсцисс центров тяжести или средневзве-
шенную координату середин оси абсцисс выбранных сечений функций при-
надлежности нечетких множеств для каждого из признаков всех объектов и
центров кластеров в соответствии с формулами (5)–(10) или (12).
2. Вычислим значения:
j
i
j
k
j
ki gGw , KkNimj ,..,1 ,,,1, ,,1 ;
j
ki
j
m
j
ki wW
1
, .,..,1 ,,,1 KkNi
Объект iA относится к кластеру kO , для которого значение kiW мини-
мально, т.е. ki
Kk
i WAk
1
minarg)( .
Другой алгоритм решения задачи 1 отличается от описанного выше
тем, что в процессе решения производится пересчет координаты абсцисс
центроидов вновь преобразованных кластеров.
Алгоритм А.2.
1. Выполняем пункты 1 и 2 алгоритма А.1.
2. Дальнейшие вычисления предусматривают выполнение N шагов.
После выполнения каждого i-го шага отнесения объекта NiAi ,,1, к ка-
кому-либо кластеру , ,,1, KkOk рассчитываем значение координаты
абсцисс центроидов вновь преобразованного кластера по формулам (5)–(10)
или (12). Координаты оси абсцисс центроидов всех вновь преобразованных
кластеров )( nk AO обозначим как )( j
n
j
k AG , ,,,1 mj Nn ,,1 ,
Kk ,,1 . Переходим к п. 3.
3. Рассчитываем значения
, |)(| j
n
j
n
j
k
j
kn gAGw ,,,1 mj Nn ,,1 , Kk ,,1 .
j
kn
j
m
j
kn wW
1
, 1,.., .k K
Объект nA относится к кластеру kO , для которого значение knW ми-
нимально, т.е. kn
Kk
n WAk
1
maxarg)( . Переходим к шагу 4.
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 28
4. Если количество распределенных по кластерам объектов меньше N,
то переходим к выполнению пункта 1. В противном случае алгоритм А.2
завершает свою работу.
Алгоритм В.
Для решения задачи 2 может быть использован любой из приведенных
выше критериев оптимальности и предусматривается выполнение
)1( KN шагов, что заключается в следующем.
1. Выполняем вычисления пункта 1 алгоритмов А.1 и А.2. Перехо-
дим к п. 2.
2. Вычисляем значения
m
j
j
ii gv
1
, .,,1 Ni
Упорядочим все объекты в последовательность в порядке возрастания
значений iv :
}|)(,),(),((),({
~
11,),21 nnNnn vvvAvAvAvAvAU .
Здесь ) ( nvA — объект, для которого координата оси абсцисс циклоида
равна nv . Переходим к п. 3.
3. Вычисления п. 3 предусматривают выполнение N шагов, связанных
с построением кратчайшей связывающей сети системы объектов.
На каждом из этих шагов в цепь включается объект nA , стоящий на по-
следнем n-м месте в последовательности U
~
. Обозначим кратчайшую связы-
вающую сеть на этом этапе решения )( nAC . Рассматривая преобразованную
связывающую сеть как некоторый кластер, рассчитываем значение оси абс-
цисс центроида этого кластера по формулам (5)–(10) или (12). Если включе-
ны все N объектов в строящеюся цепь, то переходим к выполнению пункта
4. В противном случае продолжаем включение следующих, стоящих в по-
следовательности, объектов.
4. На данном этапе вычислений выполняется )1( K шагов, связанных
с разрывом участков связывающей сети в некотором выбранном )1( K -м
месте. При этом может быть использован любой из приведенных в разделе 3
критериев оптимальности.
Пусть на некотором p-м малом шаге итерации, где )1(,,2,1 Np ,
образовано )1( p кластеров, в которые включены все N рассматриваемых
объектов. Отметим, что на первом шаге цепь разбивается на два кластера.
Выполняем следующие вычисления:
1. На 1-м шаге итерации выбираем объект nA , где
2
N
n — целая
часть от деления этих величин. Образуем второй кластер. В первый кластер
1O включаем объекты iA , ni ,,2,1 , а во второй кластер 2O — объекты
Nnn AAA ,,, 21 . Рассчитываем координаты оси абсцисс центроидов обоих
кластеров )( 1OZx и )( 2OZ x по выше приведенным формулам.
Кластерный анализ для многомерных объектов в условиях нечетких данных
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 29
2. Пусть на некотором p -м шаге, где )2(,,2 Np второй итерации
построено p кластеров pOOO ,,, 21 . В каждом из этих кластеров содер-
жатся подмножества объектов khkk AAA ,,, 21 , которые упорядочены в по-
следовательности убывания значений координаты оси абсцисс центроидов
обоих кластеров:
)}1(,,2,1 ),()(|,{
~
1,,21 hkOZOZAAAU kxkxkhkkk .
3. В каждом из кластеров kO выбираем соответственно два объекта
kqA и ,1, qkA где
2
h
q . Кластер kO разбиваем на четыре кластера 1
kO ,
2
kO , 3 4 . k kO иO Каждый из этих кластеров включает следующие объекты:
),,,( 21
1
kqkkk AAAO , ),,,( 2,1,
2
khqkqkk AAAO ;
),,,, ( 1,,21
3
qkqkkkk AAAAO ), ),,,, ( 2,1,
4
khqkqkkqk AAAAO .
Рассчитываем значения координаты оси абсцисс центроидов обоих
кластеров )( 1
kx OZ , )( 2
kx OZ и )( 3
kx OZ , )( 4
kx OZ . Координаты оси абсцисс
центроидов всех остальных кластеров )( lx OZ , l =1,…(k-1),(k+1),…,p (кроме
выбранного k-го кластера) остаются без изменения.
4. Вычисляем по приведенным формулам значения одного из выбран-
ных критериев оптимальности для каждого из вновь образованных 4-х кла-
стеров — )( 1
kO , )( 2
kO и )( 3
kO , )( 4
kO . Рассматриваем также и осталь-
ные оставшиеся без изменения кластеры pkk OOOOO ,,,,,, 1121 . Для
каждого разделяемого кластера kO находим минимальное среди четырех
возможных значений, которое обозначим как )( v
kO . Здесь v — номер вы-
бранного кластера t , для которого достигается это минимальное значение.
Определяем индекс кластера, разбиение которого на два кластера обес-
печивает минимальное значение одного из критериев оптимальности (23).
)(min
1
v
k
pk
v
q O
.
В зависимости от полученного решения количество кластеров увеличи-
ваем на 1 следующим образом:
11
21
121 ,,, , ,,,, pqqqq OOOOOOO
или 11
43
121 ,,, , ,,,, pqqqq OOOOOOO .
Если Kp )1( , то алгоритм завершает свою работу. В противном
случае производим переиндексацию всех преобразованных кластеров и пе-
реходим к выполнению п. 4.
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 30
ИЛЛЮСТРАТИВНЫЙ ПРИМЕР
Параметры треугольных функций принадлежности 2 признаков 12 объектов
и 2 признаков 2 кластеров приведены в табл. 1. Значения признаков всех
объектов и кластеров приведены к одним и тем же единицам измерения.
Таблица 1 . Параметры функций принадлежности 12 объектов и
2-х кластеров
Параметры функций принадлежности объектов и кластеров
Параметры объектов Параметры кластеров
1-й признак 2-й признак 1-й признак 2-й признак
Н
ом
ер
об
ъ
ек
та
1
ia 1
ic 1
ib )( 1
iAx 2
ia 2
ic 2
ib )( 2
iAx 1
ka 1
kc 1
kb )( 1
kOx 2
ka 1
kc 1
kb )( 2
kOx
1 1 4 6 3,67 5 8 10 9,67 4 5 6 5,0 8 10 11 10,0
2 5 7 9 7,0 6 7 8 7,0 8 10 12 9,67 3 4 6 4,33
3 10 11 12 11,0 2 4 5 3,67
4 3 8 9 6,67 9 10 12 10,33
5 10 12 15 12,33 4 6 9 6,33
6 7 8 10 11,67 2 3 4 3,0
7 8 10 11 9,67 4 5 7 5,33
8 3 6 9 6,0 5 8 10 7,67
9 10 13 16 13,0 7 8 10 8,33
10 7 10 11 9,33 1 5 6 4,0
11 12 13 15 13,33 4 7 8 6,33
12 6 8 10 8,0 6 7 11 7,33
В табл. 2 приведены результаты решения иллюстративного примера ал-
горитмом 1 на основе применения критерия оптимальности (13).
Т а б л и ц а 2 . Результаты решения задачи алгоритмом 1
Расчетные данные отнесения рассматриваемых объектов
к одному из 2-х кластеров
Обобщенные расстояния
к кластеру 1
Обобщенные расстояния
к кластеру 2 Н
ом
ер
об
ъе
кт
а
1
1iH 2
1iH 2
1
1
1 ii HH 1
2iH 2
2iH 2
2
1
2 ii HH
Кластер
1 1,33 0,33 1,66 4,33 5,34 9,67 О1
2 2,0 3,0 5,0 2,67 2,67 5,34 О1
3 6,0 6,33 12,33 1,33 0,66 1,99 О2
4 1,67 0,33 2,0 3,0 6,0 9,0 О1
5 7,33 3,67 11,0 2,66 2,0 4,66 О2
6 6,67 7,0 13,67 2,0 1,33 3,33 О2
7 4,67 4,67 9,34 0 1,0 1,0 О2
8 1,0 2,33 3,33 3,67 3,34 7,01 О1
9 8,0 1,67 9,67 3,33 4,0 7,33 О2
10 4,33 6,0 10,33 0,34 0,33 0,67 О2
11 8,33 3,67 12,0 3,66 2,0 5,66 О2
12 3,0 2,67 5,67 1,67 3,0 4,67 О2
Кластерный анализ для многомерных объектов в условиях нечетких данных
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 31
Следовательно, },,, { 84211 AAAAO , ,,, ,,,, { 1110976532 AAAAAAAO
}12A . Трапецеидальные параметры функций принадлежности 2-х объектов
нечетких множеств вновь образованных кластеров имеют вид:
)9,8,4,1()( 1
11
1
O
O
, )12,10,7,5()( 2
12
1
O
O
;
)16,13,8,6()( 1
21
2
O
O
, )11,8,3,1()( 2
22
2
O
O
,
а координаты абсцисс центров тяжести функций принадлежности 2-х объек-
тов этих нечетких множеств соответственно равны:
068,5)]([ 1
11
1
OZ
Ox , 5,8)]([ 2
12
1
OZ
Ox ;
, 788,10)]([ 1
21
2
OZ
Ox 268,7)]([ 2
22
2
OZ
Ox .
Следует отметить, что при выборе второго критерия оптимальности ре-
зультаты решения этой задачи могут оказаться другими.
ЗАКЛЮЧЕНИЕ
Кластерный анализ в условиях представления многомерных объектов и кла-
стеров нечеткими множествами имеет много практических приложений: в
биологии, медицинской и технической диагностике; в проблемах охраны
окружающей среды; в экономике и маркетинге, а также в системе государ-
ственного управления для классификации производителей, потребителей и
ситуаций; в информатике для быстрой навигации и поиска информации в
больших массивах данных и многих других областях.
Предложены алгоритмы и формульные выражения (для функций при-
надлежности треугольного и трапецеидального вида) объединения различ-
ных многомерных объектов, параметры которых заданы fuzzy-множествами,
в кластеры, вычисления координат центроидов функций принадлежности, а
также расстояний между центроидами таких объектов и кластеров.
Сформулированы различные критерии оптимальности в виде миними-
зации средневзвешенной суммы представленной в различной метрике расс-
тояний между центроидами объектов и кластеров, а также максимизации
расстояний между центроидами различных кластеров. Рассматриваются
многокритериальные подходы, основанные на аддитивной свертке различ-
ных критериев.
Рассмотрены постановки и математические формулировки, каждая из
которых может использовать любой из приведенных выше критериев опти-
мальности. Сформулированные задачи 2 и 3 являются задачами экспонен-
циальной сложности в условиях большой размерности и могут быть решены
только приближенными методам. Предложены полиномиальные алгоритмы
получения приближенного решения двух из трех сформулированных задач.
Один из алгоритмов решения задачи 1 проиллюстрирован на числовом при-
мере. Алгоритмы решения других задач будут рассмотрены в других рабо-
тах автора.
Полученные в работе результаты могут быть развиты в работах других
авторов и найти применение в целом ряде практических приложений.
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 32
ЛИТЕРАТУРА
1. J. Bacher , A. Pöge , und K. Wenzig, Clusteranalyse – Anwendungsorientierte Ein-
führung in Klassifikationsverfahren. 3. Auflage. Oldenbourg, München, 2010, 538 s.
2. С.А. Айвазян, В.М. Бухштабер, И.С. Енюков, и Л.Д.Мешалкин, Прикладная
статистика: Классификация и снижение размерности. Москва: Финансы и
статистика, 1989, 607 с.
3. И.Д. Мандель, Кластерный анализ. Москва: Финансы и статистика, 1988, 176 с.
4. М. Жамбю, Иерархический кластер-анализ и соответствия. Москва: Финансы
и статистика, 1988, 345 с.
5. Ю.А. Зак, Принятие решений в условиях размытых и нечетких данных.
Москва: URSS, 2013, 352 с.
6. Ю.А. Зак, Принятие эффективных решений в экономике и менеджменте в ус-
ловиях наличия нечисловой информации и размытых данных. Москва:
Экономика, 2018, 245 с.
7. Д.А. Вятченин, Нечёткие методы автоматической классификации. Минск:
Технопринт, 2004, 219 с.
8. Д.А. Вятченин, “Применение нечетких чисел для обоснования кластеров в ме-
тодах нечеткой кластеризации”, Искусственный интеллект, № 3, c. 523–533,
2008.
9. Ю.П. Зайченко и М.А. Гончар, “Нечеткие методы кластерного анализа в
задачах автоматической классификации в экономике”, Вісник Національного
технічного університету України “КПІ”. Іформатика, управління та
обчислювальна техніка, вип. 47, с. 198–206, 2007.
10. Н.А. Гудилина, Э.С. Иванова, А.В. Сибиряков, Н.В. Мехоношина, Н.Б. Росто-
ва, и Р.А. Файзрахманов, “Использование кластерного анализа при разработке
подходов по выбору и назначению схем лечения ВИЧ-инфицированным паци-
ентам”, Бюллетень сибирской медицины, № 16 (3), c. 52–60, 2017.
11. F. Höppner, F. Klawonn, R. Kruse, and T. Runkler, Fuzzy Cluster Analysis: Methods
for Classification, Data Analysis and Image Recognition. Chichester: Wiley
Intersciences, 1999, 289 p.
12. J.C. Bezdek, J.M. Keller, R. Krishnapuram, and N.R. Pal, Fuzzy Models and
Algorithms for Pattern Recognition and Image Processing. New York: Springer
Science, 2005, 776 p.
13. В.С. Заболотникова и О.Н. Ромашкова, “Анализ методов кластеризации для
эффективного управления процессами налоговой службы”, Фундаментальные
исследования, № 9, с. 303–330, 2017.
14. E. El-Khamy, R.A. Sadek, and M.A. El-Khoreby, “An efficient brain mass detection
with adaptive clustered based fuzzy C-mean and thresholding”, IEEE International
Conference on Signal and Image Processing Applications, pp. 429–433, 2015.
15. T.Banerjee, “Day or Night Activity Recognition From Video Using Fuzzy Clustering
Techniques”, IEEE Transactions on Fuzzy Systems, 22 (3), pp. 483–493, 2014.
16. S. Sridevi and S. Nirmala, “ANFIS based decision support system for prenatal detec-
tion of Truncus Arteriosus congenital heart defect”, Applied Soft Computing, no. 46,
pp. 577–587, 2016.
17. M.A.M. Abushariah, A.A.M. Alqudah, O.Y. Adwan, and R.M.M. Yousef,
“Automatic Heart Disease Diagnosis System Based on Artificial Neural Network
(ANN) and Adaptive Neuro-Fuzzy Inference Systems (ANFIS) Approaches”,
Journal of Software Engineering and Applications, no. 07(12), pp. 1055–1064, 2014.
18. S. Sridevi and S. Nirmala, “ANFIS based decision support system for prenatal detec-
tion of Truncus Arteriosus congenital heart defect”, Applied Soft Computing, 46,
pp. 577–587, 2016.
19. Н.А. Кореновский, “Использование нечеткой логики принятия решений для
медицинских экспертных систем”, Медицинская техника, № 1, c. 33–35, 2015.
Поступила 01.05.2021
Кластерный анализ для многомерных объектов в условиях нечетких данных
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 33
INFORMATION ON THE ARTICLE
Yuriy A. Zack, Dr. Tech. Sc., scientific expert, Deutschland, e-mail: yuriy_zack@
hotmail.com
КЛАСТЕРНИЙ АНАЛІЗ ДЛЯ БАГАТОВИМІРНИХ ОБ’ЄКТІВ В УМОВАХ
НЕЧІТКИХ ДАНИХ / Ю.О. Зак
Анотація. Наведено описані в літературі безлічі різних галузей практичних за-
стосувань багатофакторного кластерного аналізу в умовах нечітких вихідних
даних. Запропоновано нові алгоритми і формульні вирази об’єднання різних
багатовимірних об’єктів, параметри яких задано fuzzy-множинами, у кластери
і обчислення координат центроїдів їх функцій належності. Сформульовано
різні види критеріїв кластеризації у вигляді мінімізації середньозваженої і по-
даної в різній метриці суми відстаней між центроїдами об’єктів і кластерів, а
також максимізації відстаней між центроїдами різних кластерів. Запропонова-
но постановки і математичні моделі трьох різних NP-складних задач багато-
вимірної кластеризації в умовах fuzzy-даних, для розв’язання яких може бути
використаний будь-який з розглянутих критеріїв оптимальності. Розроблено
евристичні алгоритми наближеного розв’язку двох сформульованих задач. Ал-
горитм розв’язання першої задачі проілюстровано на числовому прикладі.
Отримані результати можуть стати напрямом подальших досліджень і знайти
широке практичне застосування.
Ключові слова: кластерний аналіз, багатовимірні функції належності, центро-
їди fuzzy-множин об’єктів і кластерів, центри ваги і середини перетинів нечіт-
ких множин, критерії оптимальності та алгоритми кластеризації.
CLUSTER ANALYSIS FOR MULTIDIMENSIONAL OBJECTS IN FUZZY DATA
CONDITIONS / Yu.A. Zack
Abstract. This article presents many different areas of practical applications of mul-
tivariate cluster analysis under conditions of fuzzy initial data that are described in
the literature. New algorithms and formula expressions are proposed for combining
various multi-dimensional objects, the parameters of which are given by fuzzy-sets,
into clusters along with calculating the coordinates of the centroids of their member-
ship functions. Various types of clustering criteria are formulated in the form of
minimizing the weighted average and the sum of distances between the centroids of
objects and clusters presented in different metrics, as well as maximizing the dis-
tances between the centroids of different clusters. The formulations and mathemati-
cal models of three different NP-hard problems of multidimensional clustering in
fuzzy-data conditions are proposed; while solving them any of the considered opti-
mality criteria can be used. Heuristic algorithms for the approximate solution of two
formulated problems have been developed. The algorithm for solving the 1st prob-
lem is illustrated with a numerical example. The obtained results can serve as a di-
rection for further research and have wide practical applications.
Keywords: cluster analysis, multidimensional membership functions, centroids of
fuzzy-sets of objects and clusters, centers of gravity and mid-sections of fuzzy sets,
optimality criteria and clustering algorithms.
REFERENCES
1. J. Bacher, A. Pöge, K.Wenzig, Clusteranalyse – Anwendungsorientierte Einführung
in Klassifikationsverfahren. 3. Auflage. Oldenbourg, München, 2010, 538 s.
2. S.A. Ajvazjan, V.M. Buchshtaber, I.S. Enyukov, and L.D. Meshalkin, Applied Statis-
tics: Classification and Dimension Reduction. Moscow: Finansi & Statistika, 1989,
607 p.
3. I.D. Mandel, Cluster Analysis. Moscow: Finansi & Statistika, 1988, 176 p.
4. M.Zhambyu, Hierarchical Cluster Analysis and Compliance. Moscow: Finansi &
Statistika, 1988, 345 p.
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2021, № 2 34
5. Yu.A. Zack, Making decisions in the face of blurry and fuzzy data. Moscow: URSS,
2013, 352 p.
6. Yu.A. Zack, Making effective decisions in economics and management in the
presence of non-numerical information and blurry data. Moscow: Ekonomika, 2018,
245 p.
7. D.A. Vyatchenin, Fuzzy automatic classification methods. Minsk: Technoprint,
2004, 219 p.
8. D.A. Vyatchenin, “The use of fuzzy numbers to substantiate clusters in fuzzy
clustering methods”, Iskusstvenij intellect, no. 3, pp. 523–533, 2008.
9. Yu.P. Zaychenko and M.A. Gonchar, “Fuzzy methods of cluster analysis in prob-
lems of automatic classification in economics”, Bulletin of the National Technical
University of Ukraine “KPI ”. Informatics, control and computer engineering, vol.
47, pp. 198–206, 2007.
10. N.A. Grudinina, E.S. Ivanova, A.V. Sibiryakov, N.V. Maüjnjshina, N.B. Rostova,
R.A. Fajsrachmanov, “The use of cluster analysis in the development of approaches
to the selection and prescription of treatment regimens for HIV-infected patients”,
Bulletin of Siberian Medicine, no. 16 (3), pp. 52–60, 2017.
11. F. Höppner, F. Klawonn, R. Kruse, and T. Runkler, Fuzzy Cluster Analysis: Methods
for Classification, Data Analysis and Image Recognition. Chichester: Wiley
Intersciences,1999, 289 p.
12. J.C. Bezdek, J.M. Keller, R. Krishnapuram, and N.R. Pal, Fuzzy Models and Algo-
rithms for Pattern Recognition and Image Processing. New York: Springer Science,
2005, 776 p.
13. V.S. Zabolotnikova and O.N. Romashkova, “Analysis of clustering methods for ef-
fective management of tax service processes”, Fundamental Research, no. 9,
pp. 303–330, 2017.
14. E. El-Khamy, R.A. Sadek, M.A. El-Khoreby, “An efficient brain mass detection
with adaptive clustered based fuzzy C-mean and thresholding”, IEEE International
Conference on Signal and Image Processing Applications, pp. 429–433, 2015.
15. T. Banerjee, “Day or Night Activity Recognition From Video Using Fuzzy Clustering
Techniques”, IEEE Transactions on Fuzzy Systems, 22 (3), pp. 483–493, 2014.
16. S. Sridevi and S. Nirmala, “ANFIS based decision support system for prenatal detec-
tion of Truncus Arteriosus congenital heart defect”, Applied Soft Computing, no. 46,
pp. 577–587, 2016.
17. M.A.M. Abushariah, A.A.M. Alqudah, O.Y. Adwan, and R.M.M. Yousef,
“Automatic Heart Disease Diagnosis System Based on Artificial Neural Network
(ANN) and Adaptive Neuro-Fuzzy Inference Systems (ANFIS) Approaches”,
Journal of Software Engineering and Applications, no. 07(12), pp. 1055–1064, 2014.
18. S. Sridevi and S. Nirmala, “ANFIS based decision support system for prenatal detec-
tion of Truncus Arteriosus congenital heart defect”, Applied Soft Computing, 46,
pp. 577–587, 2016.
19. N.A. Korenovsky, “The use of fuzzy decision-making logic for medical expert
systems”, Medical equipment, no. 1, pp. 33–35, 2015.
|
| id | journaliasakpiua-article-239829 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:27:23Z |
| publishDate | 2021 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/d5/3a1eb9271b2afd3d5f353fac1978eed5.pdf |
| spelling | journaliasakpiua-article-2398292021-09-16T11:48:22Z Cluster analysis for multidimensional objects in fuzzy data conditions Кластерный анализ для многомерных объектов в условиях нечетких данных Кластерний аналіз для багатовимірних об’єктів в умовах нечітких даних Zack, Yuriy кластерний аналіз багатовимірні функції належності центроїди fuzzy-множин об’єктів і кластерів центри ваги і середини перетинів нечітких множин критерії оптимальності та алгоритми кластеризації кластерный анализ многомерные функции принадлежности центроиды fuzzy-множеств объектов и кластеров центры тяжести и середины сечений нечетких множеств критерии оптимальности и алгоритмы кластеризации cluster analysis multidimensional membership functions centroids of fuzzy-sets of objects and clusters centers of gravity and mid-sections of fuzzy sets optimality criteria and clustering algorithms This article presents many different areas of practical applications of multivariate cluster analysis under conditions of fuzzy initial data that are described in the literature. New algorithms and formula expressions are proposed for combining various multi-dimensional objects, the parameters of which are given by fuzzy-sets, into clusters along with calculating the coordinates of the centroids of their membership functions. Various types of clustering criteria are formulated in the form of minimizing the weighted average and the sum of distances between the centroids of objects and clusters presented in different metrics, as well as maximizing the distances between the centroids of different clusters. The formulations and mathematical models of three different NP-hard problems of multidimensional clustering in fuzzy-data conditions are proposed; while solving them any of the considered optimality criteria can be used. Heuristic algorithms for the approximate solution of two formulated problems have been developed. The algorithm for solving the 1st problem is illustrated with a numerical example. The obtained results can serve as a direction for further research and have wide practical applications. Приведены описанные в литературе множества различных областей практических приложений многофакторного кластерного анализа в условиях нечетких исходных данных. Предложены новые алгоритмы и формульные выражения объединения различных многомерных объектов, параметры которых заданы fuzzy-множествами, в кластеры и вычисления координат центроидов их функций принадлежности. Сформулированы различные виды критериев кластеризации в виде минимизации средневзвешенной и представленной в различной метрике суммы расстояний между центроидами объектов и кластеров, а также максимизации расстояний между центроидами различных кластеров. Предложены постановки и математические модели трех различных NP-сложных задач многомерной кластеризации в условиях fuzzy-данных, при решении которых может быть использован любой из рассмотренных критериев оптимальности. Разработаны эвристические алгоритмы приближенного решения двух сформулированных задач. Алгоритм решения первой задачи проиллюстрирован на числовом примере. Полученные результаты могут послужить направлением дальнейших исследований и найти широкое практическое применение. Наведено описані в літературі безлічі різних галузей практичних застосувань багатофакторного кластерного аналізу в умовах нечітких вихідних даних. Запропоновано нові алгоритми і формульні вирази об’єднання різних багатовимірних об’єктів, параметри яких задано fuzzy-множинами, у кластери і обчислення координат центроїдів їх функцій належності. Сформульовано різні види критеріїв кластеризації у вигляді мінімізації середньозваженої і поданої в різній метриці суми відстаней між центроїдами об’єктів і кластерів, а також максимізації відстаней між центроїдами різних кластерів. Запропоновано постановки і математичні моделі трьох різних NP-складних задач багатовимірної кластеризації в умовах fuzzy-даних, для розв’язання яких може бути використаний будь-який з розглянутих критеріїв оптимальності. Розроблено евристичні алгоритми наближеного розв’язку двох сформульованих задач. Алгоритм розв’язання першої задачі проілюстровано на числовому прикладі. Отримані результати можуть стати напрямом подальших досліджень і знайти широке практичне застосування. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2021-09-14 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/239829 10.20535/SRIT.2308-8893.2021.2.02 System research and information technologies; No. 2 (2021); 18-34 Системные исследования и информационные технологии; № 2 (2021); 18-34 Системні дослідження та інформаційні технології; № 2 (2021); 18-34 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/239829/238231 |
| spellingShingle | кластерний аналіз багатовимірні функції належності центроїди fuzzy-множин об’єктів і кластерів центри ваги і середини перетинів нечітких множин критерії оптимальності та алгоритми кластеризації Zack, Yuriy Кластерний аналіз для багатовимірних об’єктів в умовах нечітких даних |
| title | Кластерний аналіз для багатовимірних об’єктів в умовах нечітких даних |
| title_alt | Cluster analysis for multidimensional objects in fuzzy data conditions Кластерный анализ для многомерных объектов в условиях нечетких данных |
| title_full | Кластерний аналіз для багатовимірних об’єктів в умовах нечітких даних |
| title_fullStr | Кластерний аналіз для багатовимірних об’єктів в умовах нечітких даних |
| title_full_unstemmed | Кластерний аналіз для багатовимірних об’єктів в умовах нечітких даних |
| title_short | Кластерний аналіз для багатовимірних об’єктів в умовах нечітких даних |
| title_sort | кластерний аналіз для багатовимірних об’єктів в умовах нечітких даних |
| topic | кластерний аналіз багатовимірні функції належності центроїди fuzzy-множин об’єктів і кластерів центри ваги і середини перетинів нечітких множин критерії оптимальності та алгоритми кластеризації |
| topic_facet | кластерний аналіз багатовимірні функції належності центроїди fuzzy-множин об’єктів і кластерів центри ваги і середини перетинів нечітких множин критерії оптимальності та алгоритми кластеризації кластерный анализ многомерные функции принадлежности центроиды fuzzy-множеств объектов и кластеров центры тяжести и середины сечений нечетких множеств критерии оптимальности и алгоритмы кластеризации cluster analysis multidimensional membership functions centroids of fuzzy-sets of objects and clusters centers of gravity and mid-sections of fuzzy sets optimality criteria and clustering algorithms |
| url | https://journal.iasa.kpi.ua/article/view/239829 |
| work_keys_str_mv | AT zackyuriy clusteranalysisformultidimensionalobjectsinfuzzydataconditions AT zackyuriy klasternyjanalizdlâmnogomernyhobʺektovvusloviâhnečetkihdannyh AT zackyuriy klasternijanalízdlâbagatovimírnihobêktívvumovahnečítkihdanih |