Виділення щільних областей у метричних просторах на основі кристалізації
Application of artificial intelligence methods and fuzzy sets theory to the clusterization problem is considered. Data on dense accumulations in finite metric spaces is an object of the research. Calculations based on the fuzzy sets theory and “optical” approach to the metric space analysis are used...
Saved in:
| Date: | 2019 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Online Access: | https://journal.iasa.kpi.ua/article/view/171809 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1866391915893620736 |
|---|---|
| author | Agayan, S. M. Soloviev, A. O. |
| author_facet | Agayan, S. M. Soloviev, A. O. |
| author_sort | Agayan, S. M. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-07-02T15:42:32Z |
| description | Application of artificial intelligence methods and fuzzy sets theory to the clusterization problem is considered. Data on dense accumulations in finite metric spaces is an object of the research. Calculations based on the fuzzy sets theory and “optical” approach to the metric space analysis are used. The result of the research is realization of “Crystal” algorithms in searching for dense areas in multidimensional data arrays. |
| first_indexed | 2025-07-17T10:25:29Z |
| format | Article |
| fulltext |
© С.М. Агаян, А.А. Соловьев, 2004
Системні дослідження та інформаційні технології, 2004, № 2 7
TIДC
НОВІ МЕТОДИ В СИСТЕМНОМУ АНАЛІЗІ,
ІНФОРМАТИЦІ ТА ТЕОРІЇ ПРИЙНЯТТЯ РІШЕНЬ
УДК 519.68:007.5
ВЫДЕЛЕНИЕ ПЛОТНЫХ ОБЛАСТЕЙ В МЕТРИЧЕСКИХ
ПРОСТРАНСТВАХ НА ОСНОВЕ КРИСТАЛЛИЗАЦИИ
С.М. АГАЯН, А.А. СОЛОВЬЕВ
Рассмотрено применение методов искусственного интеллекта и теории нечет-
ких множеств к задаче кластеризации. Объект исследования — данные о плот-
ных скоплениях в конечных метрических пространствах. В работе использован
математический аппарат на базе теории нечетких множеств и «оптический»
подход к анализу метрических пространств. Результат исследования — реали-
зация серии алгоритмов «Кристалл» поиска плотных скоплений в многомер-
ных массивах данных.
ВВЕДЕНИЕ
Статья продолжает цикл работ «Математические методы геоинформатики»
[1–5], посвященных применению в геофизике методов нечеткой теории
множеств и нечеткой логики. Подход с точки зрения нечеткой математики
используется для выделения плотных областей в конечных метрических
пространствах. Работа выполнена при поддержке Российского фонда фун-
даментальных исследований (грант 04-05-65055-а).
Опыт работы с геофизическими массивами данных показывает, что
большое значение имеют области повышенной плотности. В двумерном
массиве X на рис. 1 они выделены специальным образом. Изолированные
сгущения являются предметом кластерного анализа [6]. Нас интересует на-
хождение их в произвольном случае.
В работах [1–3] используется высекание из X слабейших, наименее
плотных точек (алгоритм «Роден»). В настоящей статье предлагается дуаль-
ная стратегия присоединения сильнейших, наиболее плотных точек в X ,
своего рода кристаллизация в X (алгоритм «Кристалл»). Неформальная
суть ее состоит в следующем: в качестве основы кристалла выбираются на-
иболее плотные точки в X (на рис.1 они отмечены звездочками). Возьмем
одну из них и обозначим *x . Затем устроим борьбу между *x и ее дополне-
нием *xX − за право обладания другой точкой *xXy −∈ . Если основа
кристалла *x победила в некоторых точках из дополнения *xX − , то к ней
присоединяется та из них, в которой эта победа была особенно убедитель-
ной. Обозначим ее 1x . Так получается рост кристалла K от его начальной
версии 0K к следующей версии 1K :
С.М. Агаян, А.А. Соловьев
ISSN 1681–6048 System Research & Information Technologies, 2004, № 2 8
},{}{ 101
*
00 xxKxxK =→== .
Далее за свои точки с первой версией кристалла 1K борется уже его
дополнение 1KX − . И опять рост кристалла K произойдет путем присое-
динения к 1K точки 2x , в которой победа 1K над 11 KXK −= будет наибо-
лее убедительной:
},{ 2121 xKKK =→ .
Если дополнение 1K сохранило в борьбе с первой версией 1K кри-
сталла K все свои точки, то рост K считается законченным, и кристалл K
полагается равным :1K 1KK = . Это и будет наиболее плотной в X частью,
содержащей *x . На следующих стадиях действует та же логика: кристалл
K растет в своей n-й версии nK , если в nK существуют точки, в которых
nK побеждает nK , и прекращает свой рост, останавливаясь на nK в про-
тивном случае.
Формализация кристаллизации будет выполнена на основе оптического
подхода [1–3]: введенный в конечном метрическом пространстве X свет
)(yxδ позволит придать точный смысл всем встречавшимся выше поняти-
ям: плотность, борьба и победа.
1. ОПТИЧЕСКИЙ ПОДХОД
Пусть ),( dX — конечное метрическое пространство.
1.1. Свет
Закон распространения света )(⋅xδ от источника в точке Xx∈ является
свободным параметром изложения и имеет различную математическую кон-
струкцию. Функция )(yxδ моделирует близость в X точки y к точке x и
Рис. 1. Пример сгущений в двумерном пространстве
Выделение плотных областей в метрических пространствах на основе кристаллизации
Системні дослідження та інформаційні технології, 2004, № 2 9
может считаться нечеткой мерой принадлежности y к x . Таким образом, в
общем случае )(yxδ не только убывает с ростом расстояния ),( yxd , но и
зависит от топологии X вокруг x .
Приведем несколько примеров.
1.1.1. С каждой убывающей на положительной полуоси ),0[ ∞ неотри-
цательной функцией «потенциального» типа 1)0(: =ϕϕ , )()( 21 tt ϕϕ ≥ ,
21 tt < связан свет )()( yy xx δδ ϕ = .
)),(()( yxdyx ϕδ = , Xy ∈∀ .
1.1.2. Обычная эксклюзивная максимальность: именно такие y X∈ го-
ворят в пользу близости y к x в X .
: ( , ) ( , ) 1
( )=x
y X d x y d x y
y
X
δ
∈ > +
.
Обозначим ( )
1( ) ( )n x
x iiX x U C r== — центрированное представление
X вокруг x , где
def
( ) { : ( , ) }x i iC r y X d x y r= ∈ = — окружности радиусов ir ,
на которых располагаются точки в X относительно x ; =Γ )(x
}...0{ )(1 xnrr <<<= — «группа нормирования» X в x . Перейдем от )(xX к
наиболее его адекватному одномерному выражению, а именно неотрица-
тельному распределению масс на прямой:
( )
1
( ) {( , ( ) ) }
n x
i i x iX x r m C rΓ = = .
Приводимые ниже меры )(yxδ связаны с движением (рис.2) слева на-
право, начиная от нуля, расстояния ),( yxd сквозь распределение )(xXΓ :
)(yxδ — степень непроникновения ),( yxd в )(xXΓ ( 1≡ — степень глуби-
ны ),( yxd в )(xXΓ ). Разное моделирование движения приводит к разным
мерам.
Нам понадобится нечеткое сравнение :n ×+ ]1,0[→+ на неотрица-
тельных числах 0, ≥ba : ),( ban — мера превосходства b над a со свойст-
вами
bbn ∀≡ ,1),0( ,
aan ∀≡ ,0)0,( ,
X(x) ГX(x)∼
X
x
)(21 ),( xnryxdrr …… →→
)(21 xnmmm
0
Рис. 2. Пример мер: движение в ГX(x)
С.М. Агаян, А.А. Соловьев
ISSN 1681–6048 System Research & Information Technologies, 2004, № 2 10
baban <⇔> 2/1),( ,
baban >⇔< 2/1),( ,
baban =⇔= 2/1),( .
В качестве n возьмем
),(max2
),(max),(
ba
baabban +−
= .
1.1.3. Движение в )(xXΓ через моменты )(yM + и )(yM − . Положим
для Xy ∈
( )),(:)),(()( yxdrmryxdyM iii <−Σ=+ ,
( )),(:)),(()( yxdrmyxdryM iii >−Σ=− .
Моменты )(),( yMyM −+ можно считать доводом в пользу максималь-
ности (минимальности) ),( yxd в )(xXΓ . Их нечеткое сравнение даст нуж-
ную меру
( ))(),()( yMyMnyx
+−=δ .
1.1.4. Движение в )(xXΓ через сравнение с радиусами. Положим для
Xy ∈
==
∑
∑
=
=
)(
1
)(
1 )),,((
)( xn
i i
xn
i ii
x
m
ryxdnm
yδ
1
)),(),,((
1
)),,(()(
1
−
=
−
=
∑∑ ≠=
X
yydyxdn
X
ryxdnm xy
xn
i ii .
1.2. Плотность освещения
Для точки Xx∈ и произвольного подмножества XA ⊂ положим
⎩
⎨
⎧
∈−
∉
=
,если,
,если,def
AxxA
AxA
Ax
⎩
⎨
⎧
∈−
∉
==
.если,1||
,если|,|def
AxA
AxA
AA xx
1.2.1. Определение 1. Назовем плотностью освещения )(xPA точки x
подмножеством A средний свет, приходящий в x от источников Ay ∈
x
Ay y
A A
x
xP x∑ ∈=
)(
)(
δ
.
Выделение плотных областей в метрических пространствах на основе кристаллизации
Системні дослідження та інформаційні технології, 2004, № 2 11
Определение 2. Назовем плотностью A и обозначим
)(min)( xPAP AAx∈= .
Результаты исследований подтверждают способность плотности чис-
ленно выражать интегральную сконцентрированность A вокруг x. Продол-
жая аналогию с нечеткой принадлежностью, можно считать )(xPA нечеткой
мерой принадлежности x к A . Оказывается, что не только зависимость
)(xPx A→ плотности по первой компоненте обладает хорошими свойства-
ми, но и вторая зависимость )(xPA A→ . Это имеет фундаментальное значе-
ние [1].
1.2.2. Утверждение. Зависимость )(xPA A→ линейна: если XBA ⊂, и
∅=BA∩ , то
)()()( xP
BA
B
xP
BA
A
xP B
xx
x
A
xx
x
BA +
+
+
=∪ .
В частности, при дополнительном предположении x∈A
)(
1
)(
1
1
)( xP
BA
B
xP
BA
A
xP BABA −+
+
−+
−
=∪ .
Сформулируем предмет нашего поиска в X .
1.2.3. Определение. Подмножество XA ⊂ плотно на фоне X , если
AxxPxP xA ∈∀≥ ),()( .
Искать такие A в X будем глобальным вариантом алгоритма «Кри-
сталл».
2. Глобальный «Кристалл»
Параметры алгоритма: конечное метрическое пространство ),( dX , модель
света )(⋅xδ , параметр роста кристалла α , параметр основы β .
2.1. Блок-схема (рис. 3)
НетДа
Нет
Нет
Да
Да
Рис. 3. Блок-схема алгоритма
С.М. Агаян, А.А. Соловьев
ISSN 1681–6048 System Research & Information Technologies, 2004, № 2 12
2.2. Основа
Задача блока состоит в выборе начальных точек (основ) кристаллизации.
Последние должны быть достаточно плотны в X . В глобальном «Кристал-
ле» множество основ XF ⊂ определяется с помощью глобальной функции
плотности: если )(XPΣ — среднее значение )(⋅xP на X , 1≥β , то
{ })()(:
def
XPxPXxFF x Σ≥∈== ββ .
Самая плотная точка *x в X — начало первого кристалла K(1).
)(maxarg0
*)1(
0 ⋅=== xx PxxK .
Если закончена i-я кристаллизация )(iK и при этом iKKF ∪…∪1⊂ ,
то алгоритм завершает свою работу (переход в блок «Конец») и
)()1( ,, iKK … — его результат. В противном случае iKKF ∪…∪1⊄ проис-
ходит выбор )1(
0
+ix — основы следующей )1( +i -й кристаллизации.
)(maxarg
)(\
)1(
0 1 ⋅=
∪∪
+
xKKF
i Px i…
.
Далее осуществляется переход в блок «Рост I».
2.3. Рост I
Если i
nK — текущая версия i-го кристалла iK , то борьба i
nK с
i
nK в точке
i
nKx∈ формализуется в виде частного
)(
)(
xP
xP
i
n
i
n
K
K , а результат борьбы — в
виде сравнения этого частного с порогом роста α.
Если )()( xPxP i
n
i
n KK
< , то
i
nK сохранило за собой свою точку x . Рост
кристалла iK заканчивается на стадии i
nK , если его дополнение
i
nK сохра-
нило все свои точки. Далее происходит переход к блоку «Основа».
Если )()( xPxP i
n
i
n KK
≥ , то i
nK одержал над
i
nK победу в точке x, но
кристалл iK может перейти из i
nK в следующую стадию i
nK 1+ через x :
},{1 xKK i
n
i
n =+ только при условии сохранения своей плотности на фоне X .
И с этим связана вторая проверка роста кристалла.
2.4. Рост II
Вывод условия на x , гарантирующего сохранение плотности },{1 xKK i
n
i
n =+
на фоне X , содержит два утверждения.
2.4.1 Утверждение 1. n -я версия nK кристалла K плотна на фоне
⇔X )()( xPxP
nn KK ≥ , nKx∈∀ .
Выделение плотных областей в метрических пространствах на основе кристаллизации
Системні дослідження та інформаційні технології, 2004, № 2 13
Доказательство. Из представления nn KKX ∪= и линейности плот-
ности 1.2.2 следует для nKx∈ равенство
)(
1
)(
1
1
)( xP
X
K
xP
X
K
xP
nn K
n
K
n
X −
+
−
−
= .
Поэтому условие плотности 1.2.3 примет вид
)(
1
)(
1
1
)( xP
X
K
xP
X
K
xP
nnn K
n
K
n
K −
+
−
−
≥ .
Принимая во внимание равенство XKK nn =+ , имеем
)(
1
)(
1
1
)( xP
X
KX
xP
X
K
xP
nnn K
n
K
n
K −
−
+
−
−
≥=
или
)()( xPxP
nn KK
≥ nKx∈∀ .
Ч.т.д.
2.4.2. Следствие. Порог роста кристалла 1≥α .
Доказательство. Если кристалл K из стадии nK переходит в стадию
},{ 11 ++ = nnn xKK , то необходимо, согласно 2.4.1, неравенство ≥++
)( 11 nK xP
n
)( 11 ++
≥ nK xP
n
, но )()( 111 ++ =
+ nKnK xPxP
nn
и )()( 111 ++ =
+ nKnK xPxP
nn
, а пото-
му 1≥α .
Ч. т. д.
Итак, если nK победил nK в точке nn Kx ∈+1 , то плотность
},{ 11 ++ = nnn xKK на фоне X в 1+nx имеет место автоматически ( 1≥α ). Ос-
талось проверить условие 2.4.1 для 1+nK в остальных его точках, т. е. для
nKx∈ . Нам потребуется выразить )(
1
xP
nK +
через )(xP
nK и )(
1
x
nx +
δ :
11 ++= nnn xKK ∪ , nKx∈ , следовательно (линейность 1.2.2)
)(1)(
1
)(1)()(
1111
1
x
K
xP
K
K
x
K
xP
K
K
xP
nnnnn x
n
K
n
n
x
n
K
n
n
K ++++
+
−
=+=
+
δδ
и
)(
1
1)(
1
)(
11
x
K
xP
K
K
xP
nnn x
n
K
n
n
K ++ −
−
−
= δ .
Равенства
XKKx
K
xP
K
K
xP nnx
n
K
n
n
K nnn
=++
−
=
++
),(1)(
1
)(
11
δ
и
С.М. Агаян, А.А. Соловьев
ISSN 1681–6048 System Research & Information Technologies, 2004, № 2 14
⇔
−
+
−
−
= )(
1
)(
1
1
)( xP
X
K
xP
X
K
xP
nn K
n
K
n
X
( ) ( ) )(1)(1)( xPKxPXxPK
nn KnXKn −−−=⇔
дают возможность выразить неравенство )()(
11
xPxP
nn KK ++
≥ , nKx∈∀ че-
рез n-ю стадию кристалла
⇔
−
−
−
≥+
−
++
)(
1
1)(
1
)(1)(
1
11
x
K
xP
K
K
x
K
xP
K
K
nnnn x
n
K
n
n
x
n
K
n
n δδ
=
−
−
−
≥
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
−
+⇔
+
)(
1
)(
1
)(
1
11
1
xP
K
K
xP
K
K
x
KK nnn K
n
n
K
n
n
x
nn
δ
( ) ( ) ( ) ( )
−
−
−
=
−
−
−
−−−
= )(
1
1)(1
1
)(1)(1
xP
K
X
K
xPK
K
xPKxPX
X
nn
Kn
n
KnX nn
( ) ( ) −
−
−
≥
−
−
⇔
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
+
−
−−
+
)(
1
1
)(
1
1
)(1
1
11
1
xP
K
X
x
KK
X
xP
KK
K X
n
x
nn
K
nn
n nn
δ
( )( )
( ) ( ) )(1)()()(
1
11
1
xPKxPKxxP
KK
KX
nnn KnXnxK
nn
n −−≥⇔
−
−−
−
+
δ .
Сформулируем утверждение, являющееся сутью блока «Рост II».
2.4.3. Утверждение 2. Рост кристалла 11 ++ =→ nnnn xKKK ∪ через
точку 1+nx описывается неравенствами
)()( 1+≥ nKK xPxP
nn
(*)
и
( ) nKnXnx KxxPKxPKx
nn
∈∀−−≥
+
),(1)()(
1
δ . (**)
Итак, в блоке «Рост II» происходит проверка точек 1+nx (*), которые
nK отрывает от nK , на сохранение плотности с их участием. Если они не
выдерживают условие (**), то текущий кристалл расти перестает и в алго-
ритме происходит переход к блоку «Основа» с целью поиска основы для
следующей кристаллизации. Если таких 1+nx оказывается несколько
),...,( 1
1
1
nm
nn xx ++ , то в качестве продолжения берется та из них, в которой каче-
ство кристалла K на )1( +n -й стадии будет максимальным (1.2.1).
)(maxarg 111
s
nn
m
sn xkPx n
+=+ = ∪ .
Выделение плотных областей в метрических пространствах на основе кристаллизации
Системні дослідження та інформаційні технології, 2004, № 2 15
Далее происходит расчет плотностей )(
1
⋅
+nKP и )(
1
⋅
+nKP на n 1K + для
борьбы между ними за рост кристалла K на следующем )1( +n -м уровне в
блоке «Рост I».
1),(
1
1)(
1
)(
11 +∈∀
+
+
+
=
++ nx
n
K
n
n
K Kxx
K
xP
K
K
xP
nnn
δ ,
1),(
2
1)(
2
1
)(
11
+∈∀
−
−
−
−
=
++
nx
n
K
n
n
K Kxx
K
xP
K
K
xP
nnn
δ .
2.5. Конец
В данном блоке происходит идентификация окончательных версий кристал-
ла IKK ,...,1 , ),( αFII = .
3. ЛОКАЛЬНЫЙ «КРИСТАЛЛ»
Рассмотрим ситуацию, изображенную на рис. 4. Процесс кристаллизации K
начнется где-то в середине A и в общем случае будет непременно происхо-
дить то слева, то справа от 0K . Через какое-то время из-за больших линей-
ных размеров A освещение еще не принадлежащих K справа точек из A
правым краем A и множеством B может стать более плотным, чем освеще-
ние этих точек кристаллом K . В результате кристалл K прекратит свой
рост, не достигнув правого конца A . Хотя из рис. 4 ясно видно, что именно
A должен быть окончательной его версией: AK = .
Выйти из этого по-
ложения можно, освобо-
дившись от большой дли-
ны растущего кристалла с
помощью так называемой
локальной кристаллиза-
ции, рассмотрев борьбу
между K и K в точке x
не во всем пространстве
X , а только в его шаре
определенного радиуса r
с центром в x .
3.1. Локальная плотность
Для ее определения потребуется несколько обозначений: =),( rxD
}),(:{ ryxdXy ≤∈= — шар в X с центром в x и радиусом r . Если A⊂X,
то }),(:{),(),( ryxdAyArxDrxDA ≤∈== ∩ — часть в A , отстоящая от x не
более, чем на r . Заметим, что ),( rxDA может быть пусто и, кроме того,
),( rxDxAx A∉⇒∉ .
K0 A
B
Рис. 4. Пример необходимости применения локаль-
ного «Кристалла»
С.М. Агаян, А.А. Соловьев
ISSN 1681–6048 System Research & Information Technologies, 2004, № 2 16
С заданной моделью света )(⋅xδ на X можно связать не только плот-
ность )(⋅AP , но и целую серию производных от нее так называемых локаль-
ных r -плотностей )()( rPA ⋅ .
3.1.1. Определение 1. Назовем локальной r-плотностью подмножества
A в точке x
⎪
⎪
⎩
⎪⎪
⎨
⎧
=
>
==
∑
≠
∈
.0),(если,0
,0),(если),(
),(
1
)()()( ),(),(
def
xA
xA
rxDy
y
xA
rxDA
rxD
rxDx
rxDxPrxP
xy
A
A
δ
Определение 2. Назовем локальной r -плотностью A и обозначим
)()(min)()( rxPrAP A
Ax∈
= .
Таким образом, r -плотность A в x равна нулю в двух случаях: когда
x лежит в A , но при этом r -изолирован в нем ( xrxDA =),( ), или когда x
r -отделим от A ( ∅=),( rxDA ).
Далее, переход ),( rxDA A→ согласован с дизъюнктным объединением
=∨=∨ )(),(),( BArxDrxD BA ∩
( ) ( ) ).,(),(),(),( rxDrxDBrxDArxD BA ∨=∨= ∩∩
Отсюда следует линейность (1.2.2) локальной плотности
)()(
),(
),(
)()(
),(
),(
)()( rxP
rxD
rxD
rxP
rxD
rxD
rxP B
xBA
xB
A
xBA
xA
BA
∨∨
∨ += .
3.1.2. Определение. Подмножество XA ⊂ r -плотно на фоне X , если
AxrxPrxP XA ∈∀≥ ),()()()( .
Цель локального r -«Кристалла» — поиск r -плотных A в X . Его па-
раметры — пространство ),( dX , модель света )(⋅xδ , радиус r , параметр
роста кристалла α , параметр основы β .
Изложение r -«Кристалла» аналогично изложению глобального «Кри-
сталла» и будет вестись по его модулю.
3.2. Основа
Если )()( rXPΣ — среднее значение плотности )()( rPX ⋅ на X ;
),( rFF β= — множество основ локальной r -кристаллизации, то
{ })()()(:
def
rXPxPXxF X Σ≥∈= β .
Выделение плотных областей в метрических пространствах на основе кристаллизации
Системні дослідження та інформаційні технології, 2004, № 2 17
Самая r -плотная точка *x в X — начало первого r -кристалла 1K .
)()(maxarg0
*1
0 rPxxK XX ⋅=== .
Остальное аналогично 2.2.
3.3. Рост I
Для удобства положим
),(),( rxDrxD
nKn = ,
),(),( rxDrxD
nKn = ,
),(),( rxPrxP
nKn = ,
),(),( rxPrxP
nKn = .
При этом ),(),(),( rxDrxDrxD nn ∨= .
Если nK — текущая версия кристалла K , то ее борьба с nK в точке
nKx∈ происходит в шаре ),( rxD между ),( rxDn и ),( rxDn . Как и в гло-
бальном «Кристалле», результатом борьбы является сравнение частного
)()(
)()(
rxP
rxP
n
n с порогом α . Особенность локального случая состоит в том, что
локальные плотности )()( rxPn и )()( rxPn могут равняться нулю. Рассмот-
рим все случаи.
3.3.1. 0)()( >rxPn и )()()()( rxPrxP nn α< : x остается за nK . Случай
0)()( >rxPn приведен на рис. 5, а 0)()( =rxPn — на рис. 6.
3.3.2. )()()()( rxPrxP nn α≥ : nK отрывает x у nK , но на следующем
этапе в блоке «Рост II» может отвергнуть x в качестве точки роста. Случай
0)()( >rxPn изображен на рис.7, а 0)()( =rxPn — на рис. 8.
x
Kn
Kn
Рис. 5. Cлучай )()()()( rxPrxP nn α< ,
0)()( >rxPn
Kn
x
Kn
Рис. 6. Cлучай )()()()( rxPrxP nn α< ,
0)()( =rxPn
С.М. Агаян, А.А. Соловьев
ISSN 1681–6048 System Research & Information Technologies, 2004, № 2 18
3.3.3. 0)()()()( == rxPrxP nn : точка x абсолютно r -изолирована в X ,
не может служить продолжением для nK и потому остается в nK (рис.9).
3.4. Рост II
По аналогии с глобальным случаем условие на x , гарантирующее сохране-
ние локальной плотности 11 ++ ∨= nnn xKK на фоне X , заключено в двух
утверждениях:
3.4.1. Утверждение 1. n -я версия nK кристалла K локально r-плотна
на фоне )()()()( rxPrxPX nn ≥⇔ , nKx∈∀ .
Доказательство. Из представления ),(),(),( rxDrxDrxD nn ∨= и ло-
кальной линейности )()( rPx ⋅ для x справедливо
)()(
),(
),(
)()(
),(
),(
)()( rxP
rxD
rxD
rxP
rxD
rxD
rxP n
x
xn
n
x
xn
X += .
Но 1),(),(),( −=⇒∈ rxDrxDrxDx nxnn , ),(),( rxDrxD nxn = . Если
0),( =rxDn , то ),(),( rxDrxDn = и )()()()( rxPrxP nX = (рис.10). Если
0),( >xn rxD , то аналогично 2.4.1 )()()()( rxPrxP nn ≥ и 1≥α (рис. 11).
Рис. 7. Cлучай )()()()( rxPrxP nn α≥ ,
0)()( >rxPn
Kn
x
Kn
Kn
x
Kn
Рис. 8. Cлучай )()()()( rxPrxP nn α≥ ,
0)()( =rxPn
Рис. 9. Cлучай 0)()()()( == rxPrxP nn
Kn
x
Kn
Рис. 10. Cлучай ×= )()()()( rxPrxP nX
)0|),((| =× rxDn
Kn
x
Kn
Выделение плотных областей в метрических пространствах на основе кристаллизации
Системні дослідження та інформаційні технології, 2004, № 2 19
Ч. т. д.
Это означает, что, как и в глобальном «Кристалле», плотность кристал-
ла 1+nK в точке 1+nx , поступившей из блока «Рост I», выполнена автомати-
чески. В силу локальности, проверку 3.4.1 в остальных 1+∈ nKx нужно де-
лать только при условии принадлежности ),(),( 11 rxDxrxDx nn ++ ∈⇔∈
(рис. 12).
Заменяя в 2.4.3 X на ),( rxD , nK на ),( rxDn и nK на ),( rxDn , полу-
чаем локальный критерий плотности продолжения для xn+1.
3.4.2. Утверждение 2. Пусть nn Kx ∈+1 и )()()()( 11 rxPrxP nnnn ++ ≥α .
Переход 11 ++ ∨=→ nnnn xKKK с сохранением локальной плотности на фо-
не X возможен только при условии
( ) )()(1),()()(),()(
1
rxPrxDrxPrxDx nnXnxn
−−≥
+
δ , ),( 1 rxDx nn +∈∀ .
Если nm
nn xx 1
1
1 ,..., ++ — возможные продолжения, то выбор среди них осу-
ществляется по качеству (3.1.1).
)()(maxarg 111 rxKPx s
nn
m
sn
n
+=+ += .
Далее происходит расчет плотностей )()(1 rPn ⋅+ и )()(
1
rP
n
⋅
+
на 1+nK
для борьбы между ними за рост кристалла K на следующем )1( +n -м уров-
не в блоке «Рост I»: если 1+∈ nKx и rxxd n >+ ),( 1 , то ее не затронули пре-
дыдущие события и все в ней осталось без изменений.
),(),(),,(),( 11 rxDrxDrxDrxD nnnn == ++ ,
)()()()(),()()()( 11 rxPrxPrxPrxP nnnn == ++ .
Если rxxd n ≤+ ),( 1 , то
1111 ),(),(,),(),( ++++ −=+= nnnnnn xrxDrxDxrxDrxD
Рис. 11. Cлучай ×≥ )()()()( rxPrxP nn
)0|),((| >× rxDn
Kn
x
Kn
Рис. 12. Cлучай ×∈+ ),(1 rxDxn
)),(( 1 rxDx n+∈×
Kn
x
Kn
xn+1
С.М. Агаян, А.А. Соловьев
ISSN 1681–6048 System Research & Information Technologies, 2004, № 2 20
и
)(
1),(
1)()(
1),(
),(
)()(
11 x
rxD
rxP
rxD
rxD
rxP
nx
n
n
n
n
n ++
+
+
=+ δ ,
=+ )()(1 rxPn
⎪
⎩
⎪
⎨
⎧
≤
>
−
−
−
−
= +
.2),(если,0
,2),(если),(
2),(
1)()(
2),(
1),(
1
rxD
rxDx
rxD
rxP
rxD
rxD
n
nx
n
n
n
n
n
δ
Второй случай означает, что после перехода 1+nx из nK в 1+nK точка x
стала в 1+nK r -изолированной.
3.5. Конец
В данном блоке происходит идентификация окончательных версий кристал-
ла IKK ,...,1 , ),,( rFII α= .
Завершая описание «Кристалла», сделаем несколько замечаний.
1. В отличие от «Родена», «Кристалл» сразу имеет дело с плотным на
фоне X множеством.
2. В плотном на фоне X подмножестве A не все точки обязаны быть
сильными и годятся на роль основ из F : кристаллизация дает в отличие от
F более целостную картину уплотнений в X .
3. Параметры α и β отвечают за жесткость «Кристалла»: большим α
и β соответствуют более компактные и сильные уплотнения в X .
4. В блоке «Основа» подмножество F может быть получено с помо-
щью другой плотности, построенной на иных принципах.
Рис. 13. Пример кристаллизации вокруг одной основы, 0,1=γ
Выделение плотных областей в метрических пространствах на основе кристаллизации
Системні дослідження та інформаційні технології, 2004, № 2 21
5. Неспособность nK оторвать у nK точки равносильно неравенству
)()( xPxP
nn KK > , nKx∈∀ . Согласно 2.4.1, это означает повышенную
плотность nK на фоне X . Так в процессе кристаллизации nK мы можем
получить уплотнения с обратной стороны.
6. В локальном «Кристалле» радиусы могут быть переменными и зави-
сеть от x : )(xrr = . Кроме того, мягкими в «Кристалле» могут быть
неравенства, связанные с α и β : в обозначениях 1.1.2 ba
мягко
< , если
2/1),( >ban или 4/3 .
7. Исследования показали, что довольно часто требуется γ -усиление
плотности на общем фоне, а именно γ -аналог 1.2.3 при 1>γ .
Рис. 14. Пример кристаллизации вокруг одной основы, 2,1=γ
Рис. 15. Пример кристаллизации вокруг одной основы, 3,2=γ
С.М. Агаян, А.А. Соловьев
ISSN 1681–6048 System Research & Information Technologies, 2004, № 2 22
AxxPxP XA ∈∀≥ ),()( γ .
Рост в соответствующей γ -версии глобального «Кристалла» описыва-
ется неравенствами
Рост I: )()1,()( 11 ++ +≥ nKnK xPncxP
nn
γ ,
Рост II: ( ) )(1)(
)1,(1
)1()1,(
)(
1
xPKxP
KncK
KXnc
x
nn Knx
nn
n
x −−
++−
−+
≥
+ γ
γ
δ ,
Рис. 16. Результат работы «Кристалла», 2,1;5,2 == βγ
Рис. 17. Результат работы «Кристалла», 2,1;0,4 == βγ
Выделение плотных областей в метрических пространствах на основе кристаллизации
Системні дослідження та інформаційні технології, 2004, № 2 23
где
γ
λ
γ
+−−
=+
+
+
1
1
1
)1,(
n
n
KX
K
nc .
Вывод этих условий аналогичен доказательству утверждения 2.4.3.
8. На рис. 13–15 показана кристаллизация вокруг одной и той же осно-
вы соответственно при 0,1=γ ; 2,1=γ и 3,2=γ . На рис. 16, 17 приведены
примеры работы «Кристалла» при 5,2=γ ; 2,1=β и 0,4=γ ; 2,1=β .
ЛИТЕРАТУРА
1. Гвишиани А.Д., Агаян С.М., Богоутдинов Ш.Р. Математические методы геоин-
форматики. I. Новый подход к кластеризации // Кибернетика и системный
анализ. — 2002. — № 2. — С. 104–122.
2. Алгоритмы искусственного интеллекта для кластеризации магнитных анома-
лий / А Д. Гвишиани, М. Диаман, В О. Михайлов и др. // Физика Земли. —
2002. — № 7. — С. 13–38.
3. Application of artificial intelligence for Euler solution clustering / V.O. Mikhailov,
A. Galdeano, M. Diament et al. // Geophysics. — 2003. — 68, № 1. — P. 168–
180.
4. Gvishiani A., Dubois J.O. Artificial intelligence and dynamic systems for geophysi-
cal applications. — Berlin: Springer, 2002. — 347 p.
5. Математические методы геоинформатики. II. Алгоритмы нечеткой логики в
задачах выделения аномалий на временных рядах / А.Д. Гвишиани,
С.М. Агаян, Ш.Р. Богоутдинов и др. // Кибернетика и системный анализ. —
2003. — № 4. — С. 103–111.
6. Мандель И.Д. Кластерный анализ. — М: Финансы и статистика, 1988. — 176 с.
Поступила 25.03.2004
|
| id | journaliasakpiua-article-171809 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:25:29Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/5b/61d98c17cc5493c606618c7f0662f95b.pdf |
| spelling | journaliasakpiua-article-1718092019-07-02T15:42:32Z Recognition of dense areas in metric spaces basing on crystallization Выделение плотных областей в метрических пространствах на основе кристаллизации Виділення щільних областей у метричних просторах на основі кристалізації Agayan, S. M. Soloviev, A. O. Application of artificial intelligence methods and fuzzy sets theory to the clusterization problem is considered. Data on dense accumulations in finite metric spaces is an object of the research. Calculations based on the fuzzy sets theory and “optical” approach to the metric space analysis are used. The result of the research is realization of “Crystal” algorithms in searching for dense areas in multidimensional data arrays. Рассмотрено применение методов искусственного интеллекта и теории нечетких множеств к задаче кластеризации. Объект исследования — данные о плотных скоплениях в конечных метрических пространствах. В работе использован математический аппарат на базе теории нечетких множеств и “оптический” подход к анализу метрических пространств. Результат исследования — реализация серии алгоритмов “Кристалл” поиска плотных скоплений в многомерных массивах данных. Розглянуто застосування методів штучного інтелекту і теорії нечітких множин до задачі кластеризації. Об’єкт дослідження — дані про щільні скупчення у кінцевих метричних просторах. У роботі використано математичний апарат на базі теорії нечітких множин та “оптичний” підхід до аналізу метричних просторів. Результат дослідження — реалізація серії алгоритмів “Кристал” пошуку щільних скупчень у багатовимірних масивах даних. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-07-02 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/171809 System research and information technologies; No. 2 (2004); 7-23 Системные исследования и информационные технологии; № 2 (2004); 7-23 Системні дослідження та інформаційні технології; № 2 (2004); 7-23 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/171809/171520 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Agayan, S. M. Soloviev, A. O. Виділення щільних областей у метричних просторах на основі кристалізації |
| title | Виділення щільних областей у метричних просторах на основі кристалізації |
| title_alt | Recognition of dense areas in metric spaces basing on crystallization Выделение плотных областей в метрических пространствах на основе кристаллизации |
| title_full | Виділення щільних областей у метричних просторах на основі кристалізації |
| title_fullStr | Виділення щільних областей у метричних просторах на основі кристалізації |
| title_full_unstemmed | Виділення щільних областей у метричних просторах на основі кристалізації |
| title_short | Виділення щільних областей у метричних просторах на основі кристалізації |
| title_sort | виділення щільних областей у метричних просторах на основі кристалізації |
| url | https://journal.iasa.kpi.ua/article/view/171809 |
| work_keys_str_mv | AT agayansm recognitionofdenseareasinmetricspacesbasingoncrystallization AT solovievao recognitionofdenseareasinmetricspacesbasingoncrystallization AT agayansm vydelenieplotnyhoblastejvmetričeskihprostranstvahnaosnovekristallizacii AT solovievao vydelenieplotnyhoblastejvmetričeskihprostranstvahnaosnovekristallizacii AT agayansm vidílennâŝílʹnihoblastejumetričnihprostorahnaosnovíkristalízacíí AT solovievao vidílennâŝílʹnihoblastejumetričnihprostorahnaosnovíkristalízacíí |