Системы распознавания образов (идентификации)

Структурная схема сети Хопфилда приведена на Рис. 6. Она состоит из единственного слоя нейронов, число которых является одновременно числом входов и выходов сети. Каждый нейрон связан синапсами со всеми остальными нейронами, а также имеет один входной синапс, через который осуществляется ввод сигнала. Выходные сигналы, как обычно, образуются на аксонах.

Рис. 6. Структурная схема сети Хопфилда

Задача, решаемая данной сетью в качестве ассоциативной памяти, как правило, формулируется следующим образом. Известен некоторый набор двоичных сигналов (изображений, звуковых оцифровок, прочих данных, описывающих некие объекты или характеристики процессов), которые считаются образцовыми. Сеть должна уметь из произвольного неидеального сигнала, поданного на ее вход, выделить ("вспомнить" по частичной информации) соответствующий образец (если такой есть) или "дать заключение" о том, что входные данные не соответствуют ни одному из образцов. В общем случае, любой сигнал может быть описан вектором X = { xi: i=0...n-1}, n - число нейронов в сети и размерность входных и выходных векторов. Каждый элемент xi равен либо +1, либо -1. Обозначим вектор, описывающий k-ый образец, через Xk, а его компоненты, соответственно, - xik, k=0...m-1, m - число образцов. Когда сеть распознбет (или "вспомнит") какой-либо образец на основе предъявленных ей данных, ее выходы будут содержать именно его, то есть Y = Xk, где Y - вектор выходных значений сети: Y = { yi: i=0,...n-1}. В противном случае, выходной вектор не совпадет ни с одним образцовым.

Если, например, сигналы представляют собой некие изображения, то, отобразив в графи-ческом виде данные с выхода сети, можно будет увидеть картинку, полностью совпадающую с одной из образцовых (в случае успеха) или же "вольную импровизацию" сети (в случае неудачи).

На стадии инициализации сети весовые коэффициенты синапсов устанавливаются следующим образом:

(1)

Здесь i и j - индексы, соответственно, предсинаптического и постсинаптического нейронов; xik, xjk - i-ый и j-ый элементы вектора k-ого образца.

Алгоритм функционирования сети следующий (p - номер итерации):

1. На входы сети подается неизвестный сигнал. Фактически его ввод осуществляется непо-сред-ственной установкой значений аксонов:

yi(0) = xi , i = 0...n-1, (2)

поэтому обозначение на схеме сети входных синапсов в явном виде носит чисто условный характер. Ноль в скобке справа от yi означает нулевую итерацию в цикле работы сети.

2. Рассчитывается новое состояние нейронов

, j=0...n-1 (3)

и новые значения аксонов

(4)

Рис. 7. Активационные функции

где f - активационная функция в виде скачка, приве-денная на Рис. 7а.

3. Проверка, изменились ли выходные значения аксонов за последнюю итерацию. Если да - переход к пункту 2, иначе (если выходы застабилизировались) - конец. При этом выходной вектор представляет собой образец, наилучшим образом сочетающийся с входными данными.

Как говорилось выше, иногда сеть не может провести распознавание и выдает на выходе несуществующий образ. Это связано с проблемой ограниченности возможностей сети. Для сети Хопфилда число запоминаемых образов m не должно превышать величины, примерно равной 0.15_n. Кроме того, если два образа А и Б сильно похожи, они, возможно, будут вызывать у сети перекрестные ассоциации, то есть предъявление на входы сети вектора А приведет к появлению на ее выходах вектора Б и наоборот.

Рис. 8. Структурная схема сети Хэмминга

Когда нет необходимости, чтобы сеть в явном виде выдавала образец, то есть достаточно, скажем, получать номер образца, ассоциативную память успешно реализует сеть Хэмминга. Данная сеть характеризуется, по сравнению с сетью Хопфилда, меньшими затратами на память и объемом вычислений, что становится очевидным из ее структуры (Рис. 8).

Сеть состоит из двух слоев. Первый и второй слои имеют по m нейронов, где m - число образцов. Нейроны первого слоя имеют по n синапсов, соединенных со входами сети (образующими фиктивный нулевой слой). Нейроны второго слоя связаны между собой ингибиторными (отрицательными обратными) синаптическими связями. Единственный синапс с положительной обратной связью для каждого нейрона соединен с его же аксоном.

Идея работы сети состоит в нахождении расстояния Хэмминга от тестируемого образа до всех образцов. Расстоянием Хэмминга называется число отличающихся битов в двух бинарных векторах. Сеть должна выбрать образец с минимальным расстоянием Хэмминга до неизвестного входного сигнала, в результате чего будет активизирован только один выход сети, соответствующий этому образцу.

На стадии инициализации весовым коэффициентам первого слоя и порогу активационной функции присваиваются следующие значения:

, i=0...n-1, k=0...m-1 (5)

Tk = n / 2, k = 0...m-1 (6)

Здесь xik - i-ый элемент k-ого образца.

Весовые коэффициенты тормозящих синапсов во втором слое берут равными некоторой величине 0 < ? < 1/m. Синапс нейрона, связанный с его же аксоном имеет вес +1.

Алгоритм функционирования сети Хэмминга следующий:

1. На входы сети подается неизвестный вектор X = {xi:i=0...n-1}, исходя из которого рассчитываются состояния нейронов первого слоя (верхний индекс в скобках указывает номер слоя):

образ распознавание хопфилд хэмминг

, j=0...m-1 (7)

После этого полученными значениями инициализируются значения аксонов второго слоя:

yj(2) = yj(1), j = 0...m-1 (8)

2. Вычислить новые состояния нейронов второго слоя:

(9)

и значения их аксонов:

(10)

Активационная функция f имеет вид порога (рис. 2б), причем величина F должна быть достаточно большой, чтобы любые возможные значения аргумента не приводили к насыщению.

3. Проверить, изменились ли выходы нейронов второго слоя за последнюю итерацию. Если да - перейди к шагу 2. Иначе - конец.

Из оценки алгоритма видно, что роль первого слоя весьма условна: воспользовавшись один раз на шаге 1 значениями его весовых коэффициентов, сеть больше не обращается к нему, поэтому первый слой может быть вообще исключен из сети (заменен на матрицу весовых коэффициентов).

Метод потенциальных функций

Предположим, что требуется разделить два непересекающихся образа V1 и V2. Это значит, что в пространстве изображений существует, по крайней мере, одна функция, которая полностью разделяет множества, соответствующие образам V1 и V2. Эта функция должна принимать положительные значения в точках, соответствующих объектам, принадлежащим образу V1, и отрицательные - в точках образа V2. В общем случае таких разделяющих функций может быть много, тем больше, чем компактней разделяемые множества. В процессе обучения требуется построить одну из этих функций, иногда в некотором смысле наилучшую.

Метод потенциальных функций связан со следующей процедурой. В процессе обучения с каждой точкой пространства изображений, соответствующей единичному объекту из обучающей последовательности, связывается функция U(X, Xi), заданная на всем пространстве и зависящая от Xi как от параметра. Такие функции называются потенциальными, так как они напоминают функции потенциала электрического поля вокруг точечного электрического заряда. Изменение потенциала электрического поля по мере удаления от заряда обратно пропорционально квадрату расстояния. Потенциал, таким образом, может служить мерой удаления точки от заряда. Когда поле образовано несколькими зарядами, потенциал в каждой точке этого поля равен сумме потенциалов, создаваемых в этой точке каждым из зарядов. Если заряды, образующие поле, расположены компактной группой, потенциал поля будет иметь наибольшее значение внутри группы зарядов и убывать по мере удаления от нее.

Обучающей последовательности объектов соответствует последовательность векторов X1, X2, :, в пространстве изображений с которыми связана последовательность U(X, X1), U(X, X2), : потенциальных функций, используемых для построения функций f(X1, X2, :). По мере увеличения числа объектов в процессе обучения функция f должна стремиться к одной из разделяющих функций. В результате обучения могут быть построены потенциальные функции для каждого образа:

, , (ф. 3)

В качестве разделяющей функции f(X) можно выбрать функцию вида:

, (ф. 4)

которая положительна для объектов одного образа и отрицательна для объектов другого.

В качестве потенциальной функции рассмотрим функцию вида

,

(ф. 5)

где ?j(X) - линейно независимая система функций; ?j - действительные числа, отличные от нуля для всех j = 1, 2, : ; Xi - точка, соответствующая i-му объекту из обучающей последовательности. Предполагается, что ?j(X) и U(X, Xi) ограничены при X?V1 ? V2; ?j(X)=?j?j(X).

В процессе обучения предъявляется обучающая последовательность и на каждом n-м такте обучения строится приближение fn(X) характеризуется следующей основной рекуррентной процедурой:

, (ф. 6)

Разновидности алгоритмов потенциальных функций отличаются выбором значений qn и rn, которые являются фиксированными функциями номера n. Как правило, qn?1, а rn выбирается в виде:

, (ф. 7)

где S(fn, f) - невозрастающие функции, причем

(ф. 8)

Коэффициенты ?n представляют собой неотрицательную числовую последовательность, зависящую только от номера n. Кроме того,  и  (например, ?n=1/n) или ?n=const.

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

1. Будем считать, что f0(X)?0 (нулевое приближение). Пусть в результате применения алгоритма после n-го шага построена разделяющая функция fn(X), а на (n+1)-м шаге предъявлено изображение Xn+1, для которого известно действительное значение разделяющей функции f(Xn+1). Тогда функция fn+1(X) строится по следующему правилу:

(ф. 9)

2. Во втором алгоритме также принимается, что f0(X)?0. Переход к следующему приближению, т. е. переход от функции fn(X) к fn+1(X), осуществляется в результате следующей рекуррентной процедуры:

(ф. 10)

где ? - произвольная положительная константа, удовлетворяющая условию ?=(1/2)?max(X, Xi).

Если в (ф. 5) принять

,

и предположить, что xv может иметь только два значения 0 и 1, то в этом случае алгоритм потенциальных функций будет совпадать со схемой перцептрона с индивидуальными порогами А-элементов и с коррекцией ошибок. Поэтому многие теоретические положения метода потенциальных функций могут быть успешно применены для анализа некоторых перцептронных схем.

Метод группового учета аргументов МГУА

Метод наименьших квадратов

Перед тем, как начинать рассмотрение МГУА, было бы полезно вспомнить или узнать впервые метод наименьших квадратов - наиболее распространенный метод подстройки линейно зависимых параметров.

Рассмотрим для примера МНК для трех аргументов:

Пусть функция T=T(U, V, W) задана таблицей, то есть из опыта известны числа U-i, Vi, Wi, Ti ( i = 1, : , n). Будем искать зависимость между этими данными в виде:

(ф. 11)

где a, b, c - неизвестные параметры.

Подберем значения этих параметров так, чтобы была наименьшей сумма квадратов уклонений опытных данных Ti и теоретических Ti = aUi + bVi + cWi, то есть сумма:

(ф. 12)

Величина ? является функцией трех переменных a, b, c. Необходимым и достаточным условием существования минимума этой функции является равенство нулю частных производных функции ? по всем переменным, то есть:

(ф. 13)

Так как:

(ф. 14)

то система для нахождения a, b, c будет иметь вид:

(ф. 15)

Данная система решается любым стандартным методом решения систем линейных уравнений (Гаусса, Жордана, Зейделя, Крамера).

Рассмотрим некоторые практические примеры нахождения приближающих функций:

1. y = ?x2 + ?x + ?

Задача подбора коэффициентов ?, ?, ? сводится к решению общей задачи при T=y, U=x2, V=x, W=1, ?=a, ?=b, ?=c.

2. f(x, y) = ?sin(x) + ?cos(y) + ?/x

Задача подбора коэффициентов ?, ?, ? сводится к решению общей задачи при T=f, U=sin(x), V=cos(y), W=1/x, ?=a, ?=b, ?=c.

Если мы распространим МНК на случай с m параметрами,

(ф. 16)

то путем рассуждений, аналогичных приведенным выше, получим следующую систему линейных уравнений:

(ф. 17)

где ,

Общая схема построения алгоритмов метода группового учета аргументов (МГУА).

Рис. 9. Селекция самого черного тюльпана при расширяющемся опытном поле (эквивалент полного перебора), и при постоянном размере поля (эквивалент селекции при сохранении свободы выбора решений F = const)

Заимствование алгоритмов переработки информации у природы является одной из основных идей кибернетики. "Гипотеза селекции" утверждает, что алгоритм массовой селекции растений или животных является оптимальным алгоритмом переработки информации в сложных задачах. При массовой селекции высевается некоторое количество семян. В результате опыления образуются сложные наследственные комбинации. Селекционеры выбирают некоторую часть растений, у которых интересующее их свойство выражено больше всего (эвристический критерий). Семена этих растений собирают и снова высевают для образования новых, еще более сложных комбинаций. Через несколько поколений селекция останавливается и ее результат является оптимальным. Если чрезмерно продолжать селекцию, то наступит <инцухт> - вырождение растений. Существует оптимальное число поколений и оптимальное количество семян, отбираемых в каждом из них.

Алгоритмы МГУА воспроизводят схему массовой селекции [5], показанной на Рис. 9. В них есть генераторы усложняющихся из ряда в ряд комбинаций и пороговые самоотборы лучших из них. Так называемое <полное> описание объекта

? = f(x1,x2,x3,?,xm),

где f - некоторая элементарная функция, например степенной полином, заменяется несколькими рядами "частных" описаний:

1-ряд селекции: y1= f(x1x2), y2= f(x1x3),..., ys= f(xm-1xm),

2-ряд селекции: z1= f(y1y2), z2= f(y1y2),..., zp= f(ys-1ys), где s=c2, p=cs2 и т.д.

Входные аргументы и промежуточные переменные сопрягаются попарно, и сложность комбинаций на каждом ряду обработки информации возрастает (как при массовой селекции), пока не будет получена единственная модель оптимальной сложности.

Каждое частное описание является функцией только двух аргументов. Поэтому его коэффициенты легко определить по данным обучающей последовательности при малом числе узлов интерполяции [4]. Исключая промежуточные переменные (если это удается), можно получить "аналог" полного описания. Математика не запрещает обе эти операции. Например, по десяти узлам интерполяции можно получить в результате оценки коэффициентов полинома сотой степени и т. д.

Из ряда в ряд селекции пропускается только некоторое количество самых регулярных переменных. Степень регулярности оценивается по величине среднеквадратичной ошибки (средней для всех выбираемых в каждом поколении переменных или для одной самой точной переменой) на отдельной проверочной последовательности данных. Иногда в качестве показателя регулярности используется коэффициент корреляции.

Ряды селекции наращиваются до тех пор, пока регулярность повышается. Как только достигнут минимум ошибки, селекцию, во избежание "инцухта", следует остановить. Практически рекомендуется остановить селекцию даже несколько раньше достижения полного минимума, как только ошибка начинает падать слишком медленно. Это приводит к более простым и более достоверным уравнениям.

Алгоритм с ковариациями и с квадратичными описаниями

Рис. 10. МГУА как эквивалент массовой селекции.

В этом алгоритме [5, 6] используются частные описания, представленные в следующих формулах:

yi=a0+a1xi+a2xj+a3xixj;

yk=a0+a1xi+a2xj+a3xixj+a4xi2+a5xj2.

Сложность модели увеличивается от ряда к ряду селекции как по числу учитываемых аргументов, так и по степени. Степень полного описания быстро растет. На первом ряду - квадратичные описания, на втором - четвертой степени, на третьем - восьмой и т. д. В связи с этим минимум критерия селекции находится быстро, но не совсем точно. Кроме того, имеется опасность потери существенного аргумента, особенно на первых рядах селекции (в случае отсутствия протекции). Специальные теоремы теории МГУА определяют условия, при которых результат селекции не отличается от результата полного перебора моделей.

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

Метод предельных упрощений (МПУ)

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

В МПУ предполагается, что разделяющая функция задается заранее в виде линейного (самого простого) полинома, а процесс обучения состоит в конструировании такого пространства минимальной размерности, в котором заранее заданная наиболее простая разделяющая функция безошибочно разделяет обучающую последовательность. МПР назван так потому, что в нем строится самое простое решающее правило в пространстве небольшой размерности, т. е. в простом пространстве.

Пусть на некотором множестве объектов V заданы два подмножества V*1 и V*2, определяющих собой образы на обучающей последовательности V. Рассмотрим i-е свойство объектов, такое, что некоторые объекты обучающей последовательности этим свойством обладают, а другие - нет. Пусть заданным свойством обладают объекты, образующие подмножество V1i, а объекты подмножества V2i этим свойством не обладают (V1i ? V2i = V). Тогда i-е свойство называют признаком первого типа относительно образа V*1, если выполняются соотношения

 и

(ф. 18)

и признаком второго типа, если выполняются

 и (ф. 19)

Если же выполняются соотношения

 и (ф. 20)

то i-е свойство считается признаком первого типа относительно образа V*2, а если выполняются

 и

(ф. 21)

то это же свойство объявляется признаком второго типа относительно образа V*2. Если свойство не обладает ни одной из приведенных особенностей, то оно вообще не относится к признакам и не участвует в формировании пространства.

Одинаковые признаки - это два признака xi и xj, порождающие подмножества V1j, V2j, V1i, V2i, такие, что

V1j= V1i и V2j= V2i. (ф. 22)

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

Метод предельных упрощений состоит в том, что в процессе обучения последовательно проверяются всевозможные свойства объектов и из них выбираются только такие, которые обладают хотя бы одной из особенностей, определяемых соотношениями (ф. 18), (ф. 21). Такой отбор однотипных, но неодинаковых признаков продолжается до тех пор, пока при некотором значении размерности пространства не наступит безошибочное линейное разделение образов на обучающей последовательности. В зависимости от того, из признаков какого типа строится пространство, в качестве разделяющей плоскости выбирается плоскость, описываемая уравнением

(ф. 23)

либо уравнением

(ф. 24)

Каждый объект относится к одному из образов в зависимости от того, по какую сторону относительно плоскости находится соответствующий этому объекту вектор в пространстве признаков размерности n.

Коллективы решающих правил

Давно известны приемы повышения качества принимаемых реше-ний, состоящие в объединении специалистов той или иной области знаний в коллектив, вырабатывающий совместное решение. Идею коллективного решения можно применить и к <коллективу> фор-мальных алгоритмов, что позволит повысить эффективность ре-шения многих задач.

Для рационального использования особенностей различных алгоритмов при решении задач распознавания возможно объединить различные по характеру алгоритмы распозна-вания в коллективы, формирующие классификационное решение на основе правил, принятых в теории коллективных решений. Пусть в некоторой ситуации Х принимается решение S. Тогда S=R(X), где R-алгоритм принятия решения в ситуации X. Предположим, что существует L различных алгоритмов решения задачи, т. е. Sl=Rl(X), l=1, 2, ... , L, где Sl-решение, получен-ное алгоритмом Rl. Будем называть множество алгоритмов {R}={R1, R2, ..., Ri.} коллективом алгоритмов решения задачи (кол-лективом решающих правил), если на множестве решений Sl в любой ситуации Х определено решающее правило F, т. е. S=F(S1, S2, ..., SL, X). Алгоритмы Rl принято называть членами коллектива, Sl - решением l-го члена коллектива, а S - коллек-тивным решением. Функция F определяет способ обобщения ин-дивидуальных решений в решения коллектива S. Поэтому синтез функции F, или способ обобщения, является центральным момен-том в организации коллектива.

Принятие коллективного решения может быть использовано при решении различных задач. Так, в задаче управления под си-туацией понимается ситуация среды и целей управления, а под решением - самоуправление, приводящее объект в целевое состоя-ние. В задачах прогноза Х - исходное, а S - прогнозируемое состояние. В задачах распознавания ситуацией Х является опи-сание объекта X, т. е. его изображение, а решением S - номер образа, к которому принадлежит наблюдаемое изображение. Индивидуальное и коллективное решения в задаче распозна-вания состоят в отнесении некоторого изображения к одному из образов. Наиболее интересными коллективами распознающих ал-горитмов являются такие, в которых существует зависимость веса каждого решающего правила Rl от распознаваемого изображения. Например, вес решающего правила Rl может определяеться соотно-шением

(ф. 25)

 где Bl - область компетентности решающего правила Rl. Веса решающих правил выбираются так, что

(ф. 26)

для всех возможных значений X. Соотношение (ф. 25) означает, что решение коллектива определяется решением того решающего правила Ri, области компетентности которого принадлежит изоб-ражение объекта X. Такой подход представляет собой двухуров-невую процедуру распознавания. На первом уровне определяется принадлежность изображения той или иной области компетент-ности, а уже на втором - вступает в силу решающее правило, компетентность которого максимальна в найденной области. Решение этого правила отождествляется с решением всего кол-лектива. Основным этапом в такой организации коллективного решения является обучение распознаванию областей компетентности. Прак-тически постановкой этой задачи различаются правила органи-зации решения коллектива. Области компетентности можно ис-кать, используя вероятностные свойства правил коллектива, можно применить гипотезу компактности и считать, что одина-ковым правилам должны соответствовать компактные области, которые можно выделить алгоритмами самообучения. В про-цессе обучения сначала выделяются компактные множества и соответствующие им области, а затем в каждой из этих областей восстанавливается свое решающее правило. Решение такого пра-вила, действующего в определенной области, объявляется дикта-торским, т. е. отождествляется с решением всего коллектива.

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

Методы и алгоритмы анализа структуры многомерных данных

Кластерный анализ

Кластерный анализ предназначен для разбиения множест-ва объектов на заданное или неизвестное число классов на основании некоторого математического критерия качества классификации (cluster (англ.) - гроздь, пучок, скопление, группа элементов, характеризуемых каким-либо общим свой-ством). Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования:

а) внутри групп объекты должны быть тесно связаны между собой;

б) объекты разных групп должны быть далеки друг от друга;

в) при прочих равных условиях распределения объектов по группам должны быть равномерными.

Требования а) и б) выражают стандартную концепцию ком-пактности классов разбиения; требование в) состоит в том, чтобы критерий не навязывал объ-единения отдельных групп объектов.

Узловым моментом в кластерном анализе считается выбор метрики (или меры близости объектов), от которого решающим образом зависит окончательный вариант разбиения объектов на группы при заданном алгоритме разбиения. В каждой конкретной задаче этот выбор произво-дится по-своему, с учетом главных целей исследования, физи-ческой и статистической природы используемой информации и т. п. При применении экстенсиональных методов распозна-вания, как было показано в предыдущих разделах, выбор метрики достигается с помощью специальных алгоритмов преобразования исходного пространства признаков.

Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть wi - i-я группа (класс, кластер) объектов, Ni - число объектов, образующих группу wi, вектор ?i - среднее арифме-тическое объектов, входящих в wi (другими словами [?i - <центр тяжести> i-й группы), a q ( wl, wm ) - расстояние меж-ду группами wl и wm

Рис. 11. Различные способы определения расстояния между кластерами wl и wm: 1 - по центрам тяжести, 2 - по ближайшим объектам, 3 - по самым далеким объектам

Расстояние ближайшего соседа есть расстояние между бли-жайшими объектами кластеров:

 Расстояние дальнего соседа - расстояние между самыми дальними объектами кластеров:

 

Расстояние центров тяжести равно расстоянию между центральными точками кластеров:

 

Обобщенное (по Колмогорову) расстояние между классами, или обобщенное K-расстояние, вычисляется по формуле

В частности, при ? ? ? и при ? ? -? имеем

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

Нацеленность алгоритмов кластерного анализа на опре-деленную структуру группировок объектов в пространстве признаков может приводить к неоптимальным или даже неправильным результатам, если гипотеза о типе группировок неверна. В случае отличия реальных распределений от ги-потетических указанные алгоритмы часто <навязывают> дан-ным не присущую им структуру и дезориентируют исследо-вателя. Поэтому экспериментатор, учитывающий данный факт, в условиях априорной неопределенности прибегает к применению батареи алгоритмов кластерного анализа и от-дает предпочтение какому-либо выводу на основании комп-лексной оценки совокупности результатов работы этих ал-горитмов.

Алгоритмы кластерного анализа отличаются большим разнообразием. Это могут быть, например, алгоритмы, реализу-ющие полный перебор сочетаний объектов или осуществляю-щие случайные разбиения множества объектов. В то же время большинство таких алгоритмов состоит из двух этапов. На первом этапе задается начальное (возможно, искусственное или даже произвольное) разбиение множества объектов на классы и определяется некоторый математический критерий качества автоматической классификации. Затем, на втором этапе, объек-ты переносятся из класса в класс до тех пор, пока значение критерия не перестанет улучшаться.

Многообразие алгоритмов кластерного анализа обусловле-но также множеством различных критериев, выражающих те или иные аспекты качества автоматического группирования. Простейший критерий качества непосредственно базируется на величине расстояния между кластерами. Однако такой критерий не учитывает <населенность> кластеров - относи-тельную плотность распределения объектов внутри выделяе-мых группировок. Поэтому другие критерии основываются на вычислении средних расстояний между объектами внутри кла-стеров. Но наиболее часто применяются критерии в виде от-ношений показателей <населенности> кластеров к расстоянию между ними. Это, например, может быть отношение суммы межклассовых расстояний к сумме внутриклассовых (между объектами) расстояний или отношение общей дисперсии дан-ных к сумме внутриклассовых дисперсий и дисперсии центров кластеров.

Функционалы качества и конкретные алгоритмы автомати-ческой классификации достаточно полно и подробно рассмот-рены в специальной литературе. Эти функционалы и ал-горитмы характеризуются различной трудоемкостью и подчас требуют ресурсов высокопроизводительных компьютеров. Раз-нообразные процедуры кластерного анализа входят в состав практически всех современных пакетов прикладных программ для статистической обработки многомерных данных.

Иерархическое группирование

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

Классификационные процедуры иерархического типа предназначены для получения наглядного представления о стратификационной структуре всей исследуемой совокупности объектов. Эти процедуры основаны на последовательном объе-динении кластеров (агломеративные процедуры) и на последо-вательном разбиении (дивизимные процедуры). Наибольшее распространение получили агломеративные процедуры. Рас-смотрим последовательность операций в таких процедурах.

На первом шаге все объекты считаются отдельными кла-стерами. Затем на каждом последующем шаге два ближайших кластера объединяются в один. Каждое объединение уменьшает число кластеров на один так, что в конце концов все объекты объединяются в один кластер. Наиболее подходящее разбиение выбирает чаще всего сам исследователь, которому предостав-ляется дендрограмма, отображающая результаты группирования объектов на всех шагах алгоритма (Рис. 12). Могут од-новременно также использоваться и математические критерии качества группирования.

Различные варианты определения расстояния между кла-стерами дают различные варианты иерархических агломеративных процедур. Учитывая специфику подобных процедур, для задания расстояния между классами оказывается достаточным указать порядок пересчета расстояний между классом wl и классом w(m, n) являющимся объединением двух других классов wm и wn по расстояниям qmn = q(wm, wn) и qln = q(wl, wn) между этими классами. В литературе предлагается следующая общая формула для вычисления расстояния между некоторым классом wl и классом w(m, n):

ql(m, n) = q (wl, w(m, n)) = ?qlm + ?qln + ?qmn + ? | qlm - qln |

где ?, ?, ? и ? - числовые коэффициенты, определяющие на-целенность агломеративной процедуры на решение той или иной экстремальной задачи. В частности, полагая ? = ? = -? = Ѕ и ? = 0, приходим к расстоянию, измеряемому по принципу ближайшего соседа. Если положить ? = ? = ? = Ѕ и ? = 0, то расстояние между двумя классами определится как расстояние между двумя самыми далекими объектами этих классов, то есть это будет расстояние дальнего соседа. И, наконец, выбор коэффициентов соотношения по формулам

приводит к расстоянию qcp между классами, вычисленному как среднее расстояние между всеми парами объектов, один из ко-торых берется из одного класса, а другой из другого.

Использование следующей модификации формулы

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

Размещено на Allbest.ru