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

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

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

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

Различные методы логической коррекции алгоритмов распознавания описаны в работах /32, 36, 60/.

1.4.4. Выпуклый стабилизатор.

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

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

Пусть имеется задача распознавания с l классами. Каждый объект представлен вектором в n-мерном действительном пространстве. Обозначим оценку апостериорной вероятности принадлежности j-го объекта к k-му классу, полученную с помощью i-го исходного алгоритма распознавания. Тогда приняв за неустойчивость алгоритма на данном объекте величину

,

(B – распознающий оператор, соответствующий алгоритму A) получим выражение для неустойчивости данного алгоритма на контрольной выборке

.

Будем искать коллективное решение в виде выпуклой комбинации исходных алгоритмов

, k=1…l , ,

где - некоторая функция, определяющая номер распознающего оператора для каждого объекта контрольной выборки; а - весовые функции, обладающие следующими свойствами:

при ,

при .

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

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

Глава2. Математические методы кластерного анализа (классификации без учителя).

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

Методы кластерного анализа позволяют решать задачи минимизации числа эталонов, поиска эталонных описаний, выявления структурных свойств классов и многие другие вопросы анализа данных. Принципы, согласно которым объекты объединяются в один кластер, являются обычно “внутренним делом” конкретного алгоритма кластеризации. Пользователь, зная данные принципы, может в определенных пределах интерпретировать результаты каждого конкретного метода. В отличие от задач распознавания, различные методы кластеризации могут приводить к решениям, имеющим весьма существенные различия. Таким образом, кроме набора разнообразных методов кластеризации, практический интерес представляет наличие средств автоматической обработки результатов, полученных независимо различными алгоритмами /51, 52/. В настоящей главе будут описаны некоторые подходы для решения задачи кластерного анализа, а также метод комитетного синтеза оптимальных коллективных решений. Конкретные методы кластеризации, реализованные в системе РАСПОЗНАВАНИЕ, описаны дополнительно в разделе 3.13.

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

Далее основная задача кластеризации будет рассматриваться прежде всего как задача поиска разбиений выборки признаковых описаний I(S₁),I(S₂),...,I(S_m), I(S) = (x₁(S),x₂(S),...,x_n(S)), заданной числовой таблицей T_nm. В «нестрогой» постановке данная задача формулируется как поиск разбиения выборки на группировки (классы, кластеры, таксоны) близких объектов, причем само искомое разбиение находится как решение некоторой оптимизационной задачи, как результат сходимости некоторой итерационной процедуры, как результат применения некоторой детерминированной процедуры, и т.п.

2.1. Кластеризация, как задача поиска оптимального разбиения.

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

Приведем примеры подобных критериев /19/.

1. Сумма внутриклассовых дисперсий, или сумма квадратов ошибок.

, где , число объектов в группе .

Решением задачи кластерного анализа при данном критерии считается такое разбиение , которое доставляет минимум функционалу .

1. Критерии на базе матриц рассеяния.

Матрица рассеяния для группы определяется как , а матрица внутригруппового рассеяния как (здесь символ t означает символ транспонирования).

Известно несколько определений критериев кластеризации на базе матриц внутригруппового рассеяния. Например, выбор в качестве критерия определителя матрицы внутригруппового рассеяния . Здесь решение задачи кластерного анализа при данном критерии также находится в результате дискретной минимизации. Поскольку число всевозможных разбиений на l групп оценивается как (например, при весьма «скромных» параметрах выборки m=100 , l=5, /19/), полный перебор разбиений здесь заведомо исключен. Поэтому обычно применяют методы частичного перебора с использованием случайного выбора начальных разбиений и последующей локальной оптимизацией. В методах локальной оптимизации (для определенности, минимизации) строится последовательность разбиений , для которой а разбиение вычисляется непосредственно по путем его «локального» изменения. Пусть , , тогда . Некоторый элемент переносится в какую-то другую группу, если это приводит к уменьшению значения функционала на новом разбиении. Конечность данной процедуры локальной (итеративной) оптимизации очевидна. Более подробное описание метода для критерия суммы внутриклассовых дисперсий приведено в разделе 3.16.

Широко известен метод «k- внутригрупповых средних». В данном методе строится последовательность разбиений , как результат выполнения следующих однотипных итераций. Пусть разбиение выбрано случайно. Для группы находится ее центр . Далее в группу зачисляются все элементы выборки, которые ближе к чем к аналогично полученным . Группа строится аналогично, но относительно множества объектов , и т.д. После вычисления их центры пересчитываются и вычислительный процесс повторяется (см. раздел 3.13).

Метод Форель является также представителем подходов, в котором кластеры находятся не в результате оптимизации некоторого критерия, а с помощью итерационных процедур – движения гипершаров фиксированного радиуса в сторону мест «сгущения» объектов /30, 31/.

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

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