Алгоритм К внутригрупповых средних.

⇐ ПредыдущаяСтр 3 из 5Следующая ⇒

Ш1. Выбираются К исходных центров кластеров Z1(1), …, Zk(1). Этот выбор производится произвольно. Ш2. Заданное множество образов {х} распределяется по K кластерам по следующему правилу:

хÎ S_j(k), если || х – z_j(k) ||< || х - z_i(k) || для всех i= 1, 2, ..., K, i≠ j, где S_j(k)—множество образов, входящих в кластер с центром z_j(k). В случае равенства решение принимается произвольным образом. Ш 3. На основе пред-го шага определяются новые центры кластеров z_j(k+1), j = 1, 2, ..., К, исходя из условия, что сумма квадратов расстояний между всеми образами, принадлежащими множеству Sj(K), и новым центром кластера должна быть минимальной. Т. е. новые центры кластеров z_j(k+1) выбираются таким образом, чтобы минимизировать показатель качества

Новые центры кластеров определяются как

где Nj—число выборочных образов, входящих в множество Sj(k).

Ш 4. Проверяется равенство z_j(k+1) = z_j(k) при j=1, 2, ..., К, которое является условием сходимости алгоритма, и при его достижении выполнение алгоритма заканчивается. В противном случае алгоритм повторяется от шага 2. Качество работы алгоритмов, основанных на вычислении К внутригрупповых средних, зависит от числа выбираемых центров кластеров, от выбора исходных центров кластеров, от последовательности осмотра образов и от геом-х особенностей данных.

Алгоритм ISODATA.

{x₁, x₂, ..., x_N} – исходный набор образов. Ш1: Задаются параметры, определяющие процесс кластеризации:

К—необходимое число кластеров; Q_N —параметр, с которым сравнивается количество выборочных образов, вошедших в кластер; Q_s— параметр, характеризующий среднеквадратичное отклонение; Q_c—параметр, характеризующий компактность; L— максимальное количество пар центров кластеров, которые можно объединить; J — допустимое число циклов итерации. Ш2: заданные N образов распределяются по кластерам, соответствующим выбранным исходным центрам, по правилу

xÎ Sj, если ||х – zj|| < ||х – zi||, i=1, 2, ..., N_c; i¹ j, где

Sj-подмножество образов выборки, включённых в кластер с центром Zj. Ш3: ликвидируются подмножества образов, в состав которых входит менее Q_N элементов, т. е. если для некоторого j выполняется условие N_j < Q_N, то подмножество S_j исключается из рассмотрения и значение N_c уменьшается на 1. Ш4: каждый центр кластера z_j, j=1, 2, ..., N_c, локализуется и корректируется посредством приравнивания его выборочному среднему, найденному по соответствующему подмножеству S_j, т. е.

j=1..Nc, где N_j —число объектов, вошедших в подмножество Sj. Ш5: вычисляется среднее расстояние D_j между объектами, входящими в подмножество S_j, и соответствующим центром кластера по формуле Ш6: вычисляется обобщённое среднее расстояние между объектами, находящимися в отдельных кластерах, и соответствующими центрами кластеров по ф-ле Ш7: а) если текущий цикл итерации – последний, то задается Q_c=0, переход к шагу 11. б) Если условие N_c< =К/2 выполняется, то переход к шагу 8. в) Если текущий цикл итерации имеет четный порядковый номер или выполняется условие N_c> =K/2, то переход к шагу 11; в противном случае процесс итерации продолжается. Ш8: для каждого подмножества выборочных образов с помощью соотношения , i=1..n, j=1..Nc вычисляется вектор среднеквадратичного отклонения σ _j = (σ _1j, σ _2j, ..., σ _nj)', где п есть размерность образа, x_ik, есть i-я компонента k-ro объекта в подмножестве S_j, z_ij есть i-я компонента вектора, представляющего центр кластера z_j, и N_j —количество выборочных образов, включенных в подмножество S_c. Каждая компонента вектора среднеквадратичного отклонения σ _j характеризует среднеквадратичное отклонение образа, входящего в подмножество S_j, по одной из главных осей координат.

Ш9: в каждом векторе среднеквадратичного отклонения s_j, j=1, 2, ..., N_c, отыскивается максимальная компонента s_j_max. Ш10: Если для любого s _j_max, j=1, 2, ..., N_c, выполняются условия s _j_max> Q_s, и а) и

Nj> 2(QN+1), или б) N_j < К/2, то кластер с центром z_j расщепляется на два новых кластера с центрами z_j⁺ и z_j^- соответственно, кластер с центром z_j ликвидируется, а значение N_c увеличивается на 1. Для определения центра кластера z_j+ к компоненте вектора z_j, соот-й макс-й компоненте вектора s _j, прибавляется заданная величина g_j; центр кластера z_j^- опред-я вычитанием этой же величины g_j из той же самой компоненты вектора z_j. В качестве величины g_j можно выбрать некоторую долю значения макс-й среднеквадратичной компоненты s_j_max, т. е. положить g_j = ks _j_max, где 0 < k ≤ 1. При выборе g_j следуег руковод-я в основном тем, чтобы ее величина была достаточно большой для различения разницы в расстояниях от произвольного образа до новых двух центров кластеров, но достаточно малой, чтобы общая структура кластеризации существенно не изменилась. Если расщепление происходит на этом шаге, надо перейти к шагу 2, в противном случае продолжать выполнение алгоритма. Ш11: вычисляются расстояния D_ij между всеми парами центров кластеров:

D_ij =l| z_i - z_j ||, i=1, 2, ..., N_c-1; j=i+1, 2, ..., N_c. Ш12: Расстояния D_ij сравниваются с параметром Q_c. Те L расстояний, которые оказались меньше Q_c, ранжируются в порядке возрастания:

[D_i1j1, D_i2j2,..., D_iLjL,] причем D_i1j1< D_i2j2< ... < D_iLjL,. a L—максимальное число пар центров кластеров, которые можно объединить. Следующий шаг осуществляет процесс слияния кластеров. Ш13: кластеры с центрами z_il и z_jl, i=1, 2, ..., L, объединяются (при усл, что в текущем цикле итерации процедура слияния не прим-ь ни к тому, ни к др-у кластеру), причем новый центр кластера опр-я по формуле

Центры кластеров z_il и z_jl ликвидируются и значение N_c уменьшается на 1.

Ш14: если текущий цикл итерации—послед-й, то выполнение алг-ма прекращ-ся. В противном случае следует возврат-я либо к ш1, если по предписанию польз-ля меняется к-л из параметров, определяющих процесс кластеризации, либо к ш2, если в очередном цикле итерации параметры процесса должны остаться неизменными. Завершением цикла итерации считается каждый переход к ш1 или 2.

⇐ Предыдущая 1 234 5 Следующая ⇒