_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (1185318), страница 18

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

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

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

Определение 9. Величина называется мерой информативности признака (информационным весом признака) X_i , если N(i) - число логических закономерностей множества P, содержащих признак X_i .

Пусть N(i,j) - число одновременных вхождений признаков X_i, X_j в одну закономерность по множеству P. Величину назовем логической корреляцией признаков X_i и X_j . Данная величина равна нулю, когда во всех закономерностях, куда входит признак X_i, присутствует X_j (и наоборот), т.е. признаки "дополняют друг друга". Корреляция равна единице, если ни в одну закономерность с признаком X_i не входит X_j. Отметим, что при выборе критериев (P_t) согласно /76/ равным признакам будет соответствовать единичная корреляция. В случаях равных или пропорциональных признаков (столбцов таблицы обучения), в силу свойств логических закономерностей N_ij=0 (что непосредственно следует из алгоритма их поиска) и, следовательно, .

Если min(N_i ,N_j)=0, полагаем =0 (данный случай возникает , например, если x_i(S)const).

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

Первое слагаемое показывает насколько близки признаки по отношению к другим признакам, а второе – насколько они «схожи» между собой. Множитель N-2 добавлен для того, чтобы слагаемые были соразмерны и вносили примерно одинаковый вклад в определение близости между признаками.

В качестве алгоритма кластеризации для заданной полуметрики и фиксированного числа кластеров использовалась иерархическая группировка /19/, в которой расстояние между кластерами определялось согласно функции

.

После нахождения n кластеров в сокращенную подсистему признаков включаются наиболее информативные признаки (по одному из каждого кластера).

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

Пусть на некотором шаге k=0,1,2,… получено с помощью кластеризации N-k группировок признаков а из каждой группировки выбран признак с максимальным весом. В результате будет получено признаковое подпространство . Пусть A_N-k - построенный в данном подпространстве алгоритм распознавания. В качестве решения задачи минимизации признакового пространства принимается , соответствующее максимальному k при ограничении .

На Рис.27 приведены графики изменения точности распознавания в модели голосования по системам логических закономерностей при двух подходах к минимизации признакового пространства на примере задачи распознавания состояния ионосферы /83/. Исходное признаковое пространство включало 34 признака, задача распознавания решалась относительно двух классов, обучающая выборка имела длину 181 объектов, контрольная - 170. Черная линия соответствует последовательному отсеву менее информативных признаков, серая - минимизации признакового пространства согласно изложенному выше алгоритму. Видно, что серая линия лежит, как правило, ниже черной. "Волнистость" графиков является естественным следствием набора факторов (неидеальность процедур вычисления предикатов P_t(S), малая длина выборок, "частичная несогласованность" выборок, когда информативность признака на обучающей таблице и контрольной имеет некоторое различие). Из рисунка следуют естественные качественные выводы о данной задаче распознавания. Удаление первой трети малоинформативных признаков мало влияет на точность распознавания и не зависит от используемого метода их сокращения - оставшиеся 20 признаков вполне компенсируют отсутствие остальных 14. При удаление последующих 10 потери при кластеризационной минимизации растут меньше, чем при частотной.

Рис.27. Минимизация признакового пространства на примере задачи распознавания состояния ионосферы

3.13. Алгоритмы кластерного анализа

В настоящем разделе приводятся дополнительный материалы к описаниям реализованных в системе РАСПОЗНАВАНИЕ алгоритмов кластерного анализа, изложенным в главе 2. Коллективное решение задачи кластерного анализа находится согласно подходу, описанному в 2.4.

Алгоритм иерархической группировки реализует стандартную схему иерархической кластеризации на заданное число кластеров. В качестве функций d(T_i, T_j) расстояния между группировками объектов реализованы два «противоположных» подхода:

1.

2. .

При использовании первого подхода ближайшим соседом каждого объекта будет объект из того же кластера. Это главное свойство данного подхода. При выполнении данного свойства, тем не менее, в пределах одного кластера могут быть весьма далекие объекты, менее близкие, чем некоторые объекты из различных кластеров.

Наоборот, при использовании второго подхода центральным условием алгоритма является создание таких кластеров, в которых не будет «очень непохожих» объектов. Здесь близость объектов разных кластеров отходит на второй план, главное – построение кластеров с минимальными диаметрами.

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

Алгоритм k внутригрупповых средних является одним из наиболее известных методов кластеризации. Алгоритм находит такие кластеры, для объектов которых центр «своего кластера» будет ближе центра любого «чужого кластера». Алгоритм состоит из следующих шагов.

Шаг 1. Выбираются k исходных центров кластеров . Этот выбор производиться произвольно, например, первые k результатов выборки из заданного множества объектов.

Шаг l. На l-м шаге итерации заданное множество объектов распределяется по k группировкам по следующему правилу:

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

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

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

, ,

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

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

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

Алгоритмы «итеративная оптимизация» и «метод локальной оптимизации» являются близкими методами нахождения локально-оптимальных разбиений данных на заданное число кластеров в результате минимизации критерия «сумма внутриклассовых дисперсий, или сумма квадратов ошибок» (см. раздел 2.1.).

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

Рассмотрим данный алгоритм с критерием качества «сумма квадратов отклонений» при заданном фиксированном числе кластеров k .

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

b) Затем проводится итеративная оптимизация функционала штрафа — суммы внутриклассовых разбросов , , где y_p — центр p-й группы , к которой отнесен объект . равен среднему квадрату расстояния от объектов, отнесенных в p-ю группировку, до его центра (внутриклассовому разбросу). На каждой итерации выбирается группировка T_p, объект и группировка T_q такие, что при переносе объекта из T_p в T_q функционал J уменьшится на максимальную величину. Процесс завершается, когда никакой последующий перенос не уменьшает функционал (получен локальный минимум) или достигнуто указанное пользователем максимальное число итераций. Полученные группировки объектов T_p , p=1,2,…,k, и считаются искомыми кластерами.

Алгоритм нахождения оптимального числа кластеров в заданном диапазоне от a до b состоит в следующем. Вначале, меняя число кластеров k в цикле от a–1 до b+1 производим кластеризацию и сохраняем полученное значение критерия J^k и соответствующее распределение объектов по k кластерам. Затем строим оценки «качества» данных кластеризаций с учетом числа кластеров. Эти оценки основаны на эвристическом критерии поиска точки, в которой наиболее сильно падает скорость уменьшения функционала J.

Обозначим _i = Jⁱ⁺¹ – Jⁱ. Теперь введем следующие понятия:

«взвешенная левая производная»

,

«взвешенная правая производная»

,

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

Список файлов книги