Материал: Мясников В.В. Основы статистической
то в соответствии с общей схемой получаем следующий алгоритм настройки
коэффициентов линейной дискриминантной функции:
W{k + \) = W {к)+ aj^x{k)sgnic(y{k))- W ^ ik )x{k^ .
Алгоритм можно переписать также в более наглядном виде:
W{k + i)= -W{k)+ai^x{k\ r{x{k))>W^(k)x{k),
W{k)-ai^x{k), r{x{k))<W^(k)x{k).
Очевидно, полученный алгоритм корректирует текущую оценку вектора
коэффициентов на каждом шаге.
Вслучае линейной разделимости классов АКП-алгоритм сходится к точному решению, то есть получающийся в результате классификатор все векторы признаков обучающей выборки классифицирует верно. В случае, когда классы линейно разделимыми не являются, в пределе получается решение, оптимальное в смысле минимизации абсолютной величины его расхождения с переменной правильной классификации.
Ал г о р и т м наименьшей СКО (НСКО-алгоритм)
ВНСКО-алгоритме критерий качества классификатора имеет вид
J(W ) = 0 . 5 - M ( r ( X ) - W ^ x f .
Поскольку производная критерия
2 Ш = - м Ц ( х , - ¥ х ).
дИ' ' '
ТО в этом случае имеется следующий алгоритм настройки коэффициентов линейного классификатора:
¥ ( k + l) = fv (к)+а;,х(к)(с(х(к))-¥^ (к)х(к)}.
Аналогично АКП-алгоритму, в НСКО-алгоритме коррекции также производятся на каждом шаге. Отличие заключается только в величине этих коррекций. Для линейно неразделимых классов алгоритм сходится в смысле минимизации величины СКО между решением и переменной правильной классификации.
50
Проблемы алгоритмов и способы их разрешения
Одной из основных проблем алгоритмов построения линейных классификаторов на основе метода стохастической аппроксимации является очень медленная скорость сходимости. Основные приемы, используемые для
ускорения сходимости, следующие: |
|
|
• выбор медленно убывающей последовательности {а^, |
, |
|
изменение значения |
, если только величина |
|
на соседних итерациях изменила знак, использование «перцептронного приема», при котором коррекция
вектора коэффициентов производится только в случае неверной классификации поступившего вектора признаков.
3.2 |
Порядок выполнения лабораторной работы |
|
3.2.1 Исходные данные |
Два |
файла данных, полученных в процессе выполнения первой |
лабораторной работы (см. раздел 1 настоящего пособия) и содержащих наборы двумерных нормально распределенных векторов признаков для ситуации равных корреляционных матриц; параметры этих законов распределения; параметры байесовского классификатора для ситуации равных корреляционных матриц (см. раздел 2 настоящего пособия).
Два файла данных, полученных в процессе выполнения первой
лабораторной работы (см. раздел 1 настоящего пособия) и содержащих наборы двумерных нормально распределенных векторов признаков для ситуации неравных корреляционных матриц; параметры этих законов распределения; параметры байесовского классификатора для ситуации неравных корреляционных матриц (см. раздел 2 настоящего пособия).
3.2.2 Общий план выполнения работы
Построить линейный классификатор, максимизирующий критерий Фишера, для классов Qg ^ двумерных нормально распределенных
51
векторов признаков для случаев равных и неравных корреляционных матриц. Сравнить качество полученного классификатора с байесовским классификатором.
Построить линейный классификатор, минимизирующий среднеквадратичную ошибку, для классов Qg и Qj двумерных нормально распределенных векторов признаков для случаев равных и неравных корреляционных матриц. Сравнить качество полученного классификатора с классификатором Байеса и классификатором Фишера.
Построить линейный классификатор, основанный на процедуре Роббинса-Монро, для классов Qg и Qj двумерных нормально распределенных векторов признаков для случаев равных и неравных корреляционных матриц. Исследовать зависимость скорости сходимости итерационного процесса и качества классификации от выбора начальных условий и выбора последовательности корректирующих коэффициентов. Сравнить качество полученного классификатора с байесовским классификатором.
3.2.3Содержание отчета
Отчет по работе должен содержать:
Аналитические вьфажения для классификаторов, полученных в результате выполнения пп. 1-2 плана, и графическое изображение соответствующих им решающих границ вместе с элементами обучающих выборок.
Параметры классификатора, полученного в результате выполнения п.З плана, и его графическое изображение.
Вероятности ошибочной классификации построенных в пп. 1-3 плана классификаторов, найденные экспериментально. Результаты сравнения построенных классификаторов с байесовским классификатором.
Графическая иллюстрация работы итерационного процесса построения классификатора с помощью процедуры Роббинса-Монро; результаты исследования скорости сходимости этого процесса и качества классификации в зависимости от начальных условий и последовательности корректирующих коэффициентов.
52
4 АВТОМАТИЧЕСКАЯ КЛАССИФИКАЦИЯ
Цель работы - изучение теоретических основ и экспериментальное исследование методов автоматической классификации.
В лабораторной работе изучаются методы автоматической классификации в распознавании образов. Рассматривается постановка задачи автоматической классификации, используемая при автоматической классификации меры сходства, критерии кластеризации. Рассматриваются три известных алгоритма: простой алгоритм вьщеления кластеров, максиминный и К внутригрупповых средних.
4Л Теоретические основы лабораторной работы
4.1.1 Постановка задачи автоматической классификации
Пусть классификации подлежат N обьектов, каждый из которых характеризуется w-мерным вектором признаков х , то есть дано множество
векторов {х, |
. Эти вектора рассматриваются как фиксированные. Каждый |
|
обьект должен быть отнесен к одному из L классов: |
где |
|
число классов L может быть известно заранее или может быть не известно. Таким образом, основной вопрос задачи автоматической классификации (АК), так же как и в других задачах классификации, это вопрос об определении класса'.
Один из возможных подходов к определению класса состоит в его понимании как кластера (таксона), то есть компактной в некотором смысле области в признаковом пространстве. В этом случае задача АК является задачей кластер-анализа и представляет собой задачу идентификации групп схожих образов в анализируемом множестве данных (или задачу вьщеления кластеров).
Процесс вьщеления кластеров является искусством весьма "эмпирическим", так как работа конкретного алгоритма зависит не только от характера анализируемых данных, но в значительной степени и от выбранной меры подобия образов и метода, используемого для идентификации кластеров, и даже от последовательности просмотра образов.
' Речь идет не о задании самого класса, а о задании областей признакового пространства, которые "соответствуют" классам.
53
