ВОПРОСЫ АВТОМАТИЗИРОВАННОЙ МЕДИКО-ТЕХНИЧЕСКОЙ ДИАГНОСТИКИ (1050259), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

Другими словами, новые центры кластеров z_j(k+1) выбираются таким образом, чтобы миними­зировать показатель качества

(2.7)

Центр z_j(k+1), обеспечивающий минимизацию показателя ка­чества, является, в сущности, выборочным средним, определен­ным по множеству S_j(k). Следовательно, новые центры класте­ров определяются как

(2.8)

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

Очевидно, что название алгоритма «К внутригрупповых средних» определяется способом, принятым для последователь­ной коррекции назначения центров кластеров.

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

Качество работы алгоритмов, основанных на вычислении К внутригрупповых средних, зависит от числа выбираемых цент­ров кластеров, от выбора исходных центров кластеров, от после­довательности осмотра образов и, естественно, от геометриче­ских особенностей данных. Хотя для этого алгоритма общее до­казательство сходимости не известно, приемлемые результаты можно ожидать в тех случаях, когда данные обра­зуют характерные гроздья, отстоящие друг от друга достаточно далеко. В большинстве случаев практическое применение этого алгоритма потребует проведения экспериментов, связанных с выбором различных значений параметра К и исходного распо­ложения центров кластеров.

Алгоритм ИСОМАД. Алгоритм ИСОМАД (Итеративный Самоорганизующийся Метод Анализа Данных, английское название Isodata — Iterative Self-Organizing Data Analysis Techniques) в принципе аналогичен процедуре, предусматривающей вычисление К внутригрупповых средних, поскольку и в этом алгоритме центрами кластеров служат выборочные средние определяемые итеративно. Однако в отличие от предыдущего алгоритма ИСОМАД обладает обширным набором вспомогательных эвристических процедур, встроенных в схему итерации. Это определение «эвристические» следует постоянно иметь в виду, поскольку целый ряд описываемых ниже этапов вошел в алгоритм в результате осмысления эмпирического опыта его использования.

До выполнения алгоритма следует задать набор N_c исходных центров кластеров z₁, z₂ ..... z_Nc . Этот набор, число элементов должно быть равно предписанному ко­личеству кластеров, может быть получен выборкой образов из заданного множества данных.

При работе с набором {x₁, х₂, …, x_N}, составленным из N элементов, алгоритм ИСОМАД выполняет следующие основные шаги.

Шаг 1. Задаются параметры, определяющие процесс класте­ризации:

К - необходимое число кластеров;

_N - параметр, с которым сравнивается количество выбо­рочных образов, вошедших в кластер;

_S - параметр, характеризующий среднеквадратичное от­клонение;

_C - параметр, характеризующий компактность;

L - максимальное количество пар центров кластеров, кото­рые можно объединить; I - допустимое число циклов итерации.

Шаг 2. Заданные N образов распределяются по кластерам, соответствующим выбранным исходным центрам, по правилу ,

применяемому ко всем образам х, вошедшим в выборку; через S_j обозначено подмножество образов выборки, включенных в кластер с центром z_j.

Шаг 3. Ликвидируются подмножества образов, в состав ко­торых входит менее _N элементов, т. е. если для некоторого j выполняется условие N_j < _N, то подмножество S_j исключается из рассмотрения и значение N_c уменьшается на 1.

Шаг 4. Каждый центр кластера z_j, j=1, 2 … N_c, лока­лизуется и корректируется посредством приравнивания его вы­борочному среднему, найденному по соответствующему подмно­жеству S_j , т. е.

,

где N_j - число объектов, вошедших в подмножество S_j.

Шаг 5. Вычисляется среднее расстояние D_j между объек­тами, входящими в подмножество S_j, и соответствующим цент­ром кластера по формуле

Шаг 6. Вычисляется обобщенное среднее расстояние между объектами, находящимися в отдельных кластерах, и соответ­ствующими центрами кластеров по формуле

Шаг 7. а) Если текущий цикл итерации — последний, то задается _C = 0, переход к шагу 11. б) Если условие N_c  K/2 выполняется, то переход к шагу 8. в) Если текущий цикл ите­рации имеет четный порядковый номер или выполняется условие N_c  2K, то переход к шагу 11; в противном случае процесс итерации продолжается.

Шаг 8. Для каждого подмножества выборочных образов с помощью соотношения

вычисляется вектор среднеквадратичного отклонения , где n есть размерность образа, x_ik есть i-я компонента k-ro объекта в подмножестве S_j, z_ij есть i-я ком­понента вектора, представляющего центр кластера z_j, и N_j - ко­личество выборочных образов, включенных в подмножество S_j. Каждая компонента вектора среднеквадратичного отклонения _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_C и

a)

или

б) N_c  K/2,

то кластер с центром z_j расщепляется на два новых кластера с центрами z_j⁺ и z_j^- соответственно, кластер с центром z_j ликви­дируется, а значение N_c увеличивается на 1. Для определения центра кластера z_j⁺ к компоненте вектора z_j, соответствующей максимальной компоненте вектора s_j, прибавляется заданная величина _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 между всеми парами центров кластеров:

.

Шаг 12. Расстояния D_ij сравниваются с параметром Q_C. Те L расстояний, которые оказались меньше Q_C , ранжируются в по­рядке возрастания:

,

причем , a L - максимальное число пар центров кластеров, которые можно объединить. Следующий шаг осуществляет процесс слияния кластеров.

Шаг 13. Каждое расстояние вычислено для определен­ной пары кластеров с центрами и . К этим парам в последовательности, соответствующей увеличению расстояния между центрами, применяется процедура слияния, осуществляе­мая на основе следующего правила. Кластеры с центрами и i=1, 2...L, объединяются (при условии, что в текущем цикле итерации процедура слияния не применялась ни к тому, ни к другому кластеру), при­чем новый центр кластера определяется по формуле

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

Следует отметить, что допускается только попарное слияние кластеров. Центр полученного в результате кластера рассчитывается, исходя из позиций, занимаемых центрами объединяемых класте­ров и взятых с весами, определяемыми количеством выборочных образов в соответствующем кластере.

Опыт свидетельствует, что использование более сложных процедур объединения кластеров может привести к получению неудовлетворительных результатов. Описанная процедура обеспечивает выбор в качестве центра объединенного кластера точки, представляющей истинное среднее сливаемых подмножеств образов. Важно также иметь в виду, что, поскольку к каждому центру кластера процедуру слияния можно применить только один раз, реализация данного шага ни при каких обстоятельствах не может привести к получению L объединенных кластеров.

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

Ниже приведены графики (рис. 10, 11), полученные в результате обработки одних и тех же данных с помощью алгоритма К внутригрупповых средних и алгоритма ИСОМАД соответственно.

Характеристики

Список файлов учебной работы