эвристические соображения, либо основываться на минимизации (или максимизации) какого-нибудь показателя качества.
При эвристическом подходе решающую роль играют интуиция и опыт. Он предусматривает задание набора правил, которые обеспечивают использование выбранной меры сходства для отнесения образов к одному из кластеров.
Подход к кластеризации, предусматривающий использование показателя качества, связан с разработкой процедур, которые обеспечат минимизацию или максимизацию выбранного показателя качества. Одним из наиболее популярных показателей является сумма квадратов ошибки:
|
(4-1) |
|
l=OxeSi |
где L — число |
кластеров, S, — множество образов (векторов признаков), |
относящихся к |
1-му кластеру, а M i =Е —V х - вектор выборочных |
средних значений для множества образов Sy величина ф характеризует количество образов, входящих во множество Sy Как видно, показатель качества (1) определяет общую сумму квадратов отклонений характеристик всех образов, входящих в некоторый кластер, от соответствующих средних значений по этому кластеру. Алгоритм, основанный на этом показателе качества, рассматривается ниже. Естественно, существует масса показателей качества, помимо рассмотренного. Нередко применяются алгоритмы отыскания кластеров, основанные на совместном использовании эвристического подхода и показателя качества. Примером является алгоритм ISODATA [8].
Ниже рассмотрены три наиболее известные алгоритма [8], которые являются примерами как эвристического подхода, так и подхода, использующего показатель качества.
4.1.4 Простой алгоритм выделения кластеров
Пусть задано множество N образов {хд, x j,..., % _i} . Пусть также центр первого кластера Mg совпадает с любым из заданных образов и определена произвольная неотрицательная пороговая величина 4; для удобства можно считать, что Мд= хд . После этого вычисляется расстояние d{MQ,xY между
55
существующим центром кластера |
Mg |
и образом |
x j. Если это расстояние |
||||||||||||
больше значения пороговой величины Т |
(у(Мд,х^)> г ) , |
то |
учреждается |
||||||||||||
новый кластер с центром |
= x j . В противном случае образ xj |
включается |
|||||||||||||
в кластер, центром |
которого |
является Mg . Пусть |
условие |
<i(Mg,Xi)>7’ |
|||||||||||
выполнено, и |
Mj - центр нового кластера. |
|
|
|
|
|
|
|
|||||||
|
На следующем шаге вычисляются расстояния cI{Mq,xY) |
и cI{Mi,xY) |
до |
||||||||||||
образа Х2 |
от |
центров кластеров |
Mg |
и |
M j . Если |
оба |
расстояния |
||||||||
оказываются |
больше порога |
Т |
(у(Мд,Х2 )> Г |
и |
ё { м 1 ,Х2 ) > т ) , |
то |
|||||||||
учреждается новый кластер с центром |
М 2 = Х2 . В противном случае образ |
||||||||||||||
Х2 |
зачисляется в тот кластер / (/ = 0,l), чей центр М/ к нему ближе. |
|
|||||||||||||
|
Подобным |
же |
образом |
|
расстояния |
от |
каждого |
нового образа |
|||||||
Ху |
(/■ = 1,7V - 1) |
до |
каждого |
известного |
центра |
кластера |
М; (/ = О,Z - 1) |
||||||||
вычисляются и сравниваются с пороговой величиной. Если все эти
расстояния превосходят значение порога Т |
(v / = 0 ,Z - l |
у(М ;,Х у)>г), то |
учреждается новый кластер с центром |
M i = X j (и |
число кластеров |
увеличивается на единицу). В противном случае образ зачисляется в кластер с самым близким к нему центром.
Результаты описанной процедуры определяются выбором первого центра кластера, порядком просмотра образов, значением пороговой величины Т и, конечно, геометрическими характеристиками данных.
4.1.5 Алгоритм максиминного расстояния
Алгоритм, основанный на принципе максиминного (максимально минимального) расстояния, представляет собой еще одну простую эвристическую процедуру, использующую евклидово расстояние. Этот алгоритм в принципе аналогичен схеме из п. 1.4, за исключением того обстоятельства, что в первую очередь он выявляет наиболее удаленные кластеры.
Алгоритм состоит из нескольких шагов.
Шаг 1. Произвольным образом выбирается центр первого кластера Mg . Удобно выбирать в качестве центра кластера Mg тот вектор признаков
56
X е J , который обладает некоторыми «экстремальными» свойствами.
Например, удобным является тот вектор, удаление которого от среднего всех векторов из выборки максимально:
,, N -1
Mo = arg max, а '' х - Т щ
1=0
Шаг 2. Выбирается центр второго кластера Mj . В качестве центра используется тот вектор х е f?"?*, который наиболее удален от первого центра кластера:
Шаг 4 (4 >2). Выбирается центр кластера . Для этого
вычисляются все расстояния между оставшимися образами (векторами
признаков) |
X е |
\ |
и уже существующими центрами кластеров |
|
|
1 _ 2 |
. Для каждого оставшегося образа х |
находится тот центр |
|
кластера /, |
расстояние до |
которого минимально: |
/ = arg min d\Mi х) |
|
|
|
|
|
l=0,L-2 |
(вектора распределяются по кластерам по критерию близости к их центру). В
качестве претендента на новый центр кластера |
Mp_i |
берется |
тот вектор |
|||||
признаков X , у которого это минимальное расстояние (расстояние до центра |
||||||||
«своего» кластера) максимально: |
|
|
|
|
||||
|
M^^_i=arg |
шах |
min diMi.x). |
|
|
|||
|
|
|
|
x e Y jl:Y = 0 ,L - 2 |
|
|
|
|
Полученное |
для |
|
выбранного |
вектора |
расстояние |
|||
timin = min |
dWi.MT^ |
J |
от |
него до |
ближайшего кластера сравнивается с |
|||
1=0,L-2 ' |
' |
|
|
|
|
|
|
|
некоторым |
«типичным» |
расстоянием djypj^^i |
между |
кластерами. Если |
||||
полученное расстояние больше «типичного», то этот вектор становится новым центром кластера:
57
^m in > dtypical |
= M p _ i . |
В противном случае - процесс вьщеления кластеров останавливается.
Выбор типичного расстояния может быть осуществлен различными способами. Один из наиболее типичных способов - это задание типичного расстояния равного некоторой части ц от среднего расстояния между уже существующими кластерами:
\Ь - 2 L -2
typical ~ Б
Величина ц выбирается из условия О < ц < 1. Типичное значение: Т = ~ •
4.1.6Алгоритм К внутригрупповых средних
Алгоритмы, рассмотренные в пп. 4.1.4 - 4.1.5, являются, в сущности, эвристическими процедурами. Алгоритм, представленный ниже, минимизирует показатель качества, заданный как сумма квадратов расстояний всех точек, входящих в кластерную область, до центра кластера. Эта процедура, которую часто назьшают алгоритмом, основанным на вычислении К внутригрупповых средних, состоит из следующих шагов.
Описание алгоритма Шаг 1. Выбираются К исходных центров кластеров на первой итерации
(r = l): M o(r),M j(r),...,M j^_j(r). Этот выбор производится произвольно, и
обычно в качестве исходных центров используются первые К образов из
заданного множества Vj>j=0 |
iN > K ): |
|
Mo(l)=Xo, M i(l)= A , |
...M ^ _ i(l)= x^_ i . |
|
Номер итерации увеличивается: г := г +1. |
||
Шаг 2. На г-й итерации |
(г = 2,3...) |
исходное множество образов |
распределяется по К кластерам по правилу близости. То есть некоторый образ
X е относят в кластер (г) {к = 0 , К - \ ) с центром М р (г- 1),
рассчитанным на предыдущем шаге, если этот центр - ближайший:
58
xeSi^{r), k = arg min ti(x .M .(r-l)) .
J = 0 , K - 1
Таким образом, S]^{r) - множество образов, входящих в кластер с номером к на г-й итерации алгоритма. В случае равенства расстояний от некоторого образа до нескольких центров кластеров решение об отнесении этого образа к одному из них принимается произвольным образом.
Шаг 3. На основе результатов шага 2 определяются новые центры кластеров Mo(r),Mi(r),...Myy_i(r) на г-й итерации алгоритма. Они определяются из условия, чтобы сумма квадратов расстояний между всеми образами, принадлежащими кластеру S^. (г), и новым центром кластера
Мр(г) должна быть минимальной. Другими словами, новые центры кластеров выбираются таким образом, чтобы минимизировать частные показатели
Jk(r)= |
, к = 0,\,...,К -1 |
хеХ(г)
И, следовательно, интегральный показатель качества кластеризации на г-м шаге:
к=0 |
к=0 xeSi^{r) |
Для случая евклидового расстояния новый центр кластера М^.(г), обеспечивающий минимизацию соответствующего частного показателя
Jk {г) , является, в сущности, выборочным средним, определенным по множеству образов в кластере Sk (г):
xeS^r)
где Nj^ = (г)| - число образов, входящих в кластер Sj^(г) на г-м шаге. Как
видно, название алгоритма «К внутригрупповых средних» определяется способом, принятым для последовательной коррекции назначения центров
кластеров. |
|
|
|
|
|
|
Шаг 4. |
Равенство |
центров |
кластеров |
на |
соседних |
шагах |
|
|
|
|
|
|
59 |