Математические методы искусственного интеллекта. Броневич А.Г - 10 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

10
2. В качестве второго центра кластера выберем тот элемент
2 j
=cx,
который находится на наибольшем расстоянии от
1
c , т.е.
11
1
max
ji
in≤≤
−= −xc xc.
3.
Предположим, что выбраны k центров кластеров. В качестве оче-
редного (1)k + -го центра кластера выберем тот эле-
мент
s
x
, который находится на наибольшем расстоя-
нии от ближайшего из центров
1
,...,
k
cc (рис.4), т.е.
11
1
min max min
s
jij
jk jk
in
≤≤ ≤≤
≤≤
−= −xc xc
.
Условием остановки алгоритма может быть выпол-
нение неравенства
(1) ()kk
γ
+
∆∆≥, (1)
где
γ
– некоторое пороговое значение, близкое к 1.
Выполнение условия (1) означает, что при появления
нового центра кластера дисперсия меняется незначительно.
4.3. Алгоритм ISODATA
Этот алгоритм является разновидностью алгоритма k -
внутригрупповых средних и отличается от него введением некоторых эври-
стических параметров. С помощью параметров можно объединять два кла-
стера в один, разделять один кластер на два и т.д.
Процедуры изменения числа кластеров можно осуществлять следую-
щим образом:
1.
Удаление кластеров. Если кластер содержит мало элементов
1i
Nq< (
1
q – параметр алгоритма ISODATA), то он удаляется, т.е. его элемен-
ты распределяются по другим кластерам, а центр кластера
i
c
удаляется из
списка центров кластеров.
2.
Разделение кластеров. Если разброс элементов от центра кластера
достаточно большой, или, другими словами, если дисперсия
i -го кластера
2i
D
q>
, то i -й кластер разделяется на два кластера. Для разделения кластера
вычисляются покомпонентные дисперсии:
2
1
ji
im jm im
i
S
Dxc
N
∈
=−
∑
x
, 1,...,mn= .
Далее выбирается та
l -я компонента, для которой
il is
DD>
для всех ls≠ и
осуществляется разделение кластеров по
l -й компоненте. При этом новые
центры кластеров
′
c
и
′′
c
будут вычисляться по формулам
11 1 11 1
( ,..., , , ,..., ), ( ,..., , , ,..., )
i i il il il il in i i il il il il in
ccc Dcc ccc Dcc
γγ
−+ −+
′′′
=+ =−cc
,
где
γ
– параметр алгоритма ISODATA.
Другой, более точный способ деления кластеров состоит в вычислении
«направления» в пространстве
n
R
, вдоль которого дисперсия кластера мак-
симальна. Далее кластер разделяется на два гиперплоскостью, проходящей
через центр кластера и перпендикулярной вычисленному направлению.
Рис.4
2
x
1
0
1
c
2
c
3
c

Страницы