Файл: Учебнометодическое пособие по лабораторному практикуму. Спб ниу итмо, 2013. 35 с. В учебнометодическом пособии предлагаются лабораторные работы, охватывающие основные понятия теории искусственного интеллекта.pdf

25 обучающей выборке
, исходя из условий
:
0
>
′
i
x
w
, если
1
a
A
i
=
и
0
<
′
i
x
w
, если
2
a
A
i
=
Разделяющая поверхность
, задаваемая уравнением
0
=
′
i
x
w
, в
данном случае будет гиперплоскостью
Чтобы представить эти условия единообразно
, обычно пользуются следующим приемом
Пусть
1
=
i
z
, если
1
a
A
i
=
, и
1
−
=
i
z
, если
2
a
A
i
=
, тогда ограничения на вектор параметров будут следующие
:
( )
0
>
′
∀
i
i
z
i
x
w
(13)
В
зависимости от критерия качества и
метода поиска параметров
, максимизирующих этот критерий
, могут быть построены различные процедуры нахождения линейных решающих функций
Одной из идей здесь является применение классического метода наименьших квадратов
(
МНК
).
Необходимо
, чтобы решающая функция правильно классифицировала образы обучающей выборки
Это можно выразить в
виде следующего условия
:
i
i
z
=
κ
)
,
(
w
x
Тогда задача распознавания сводится к
задаче аппроксимации
, для которой в
рамках
МНК
можно записать следующую целевую функцию
:
(
)
∑
=
−
κ
=
M
i
i
i
z
M
L
1 2
)
,
(
1
w
x
(14)
Удобство линейных решающих функций в
том
, что для их нахождения используется линейный
МНК
, имеющий эффективное решение
Для определения значений параметров
, при которых достигается минимум критерия
(14), продифференцируем его и
получим систему линейных уравнений
:
0 2
1 1
1
,
=








−
=
∂
∂
∑ ∑
=
+
=
M
i
k
i
N
j
j
i
j
k
x
z
x
w
M
w
L
,
(15) которую не представляет сложности решить.
Не любые два набора точек в
N
R
разделяются гиперплоскостью, задаваемой линейной решающей функцией, а значит, не все образы в таких наборах могут быть корректно классифицированы с помощью линейной решающей функции. Это является платой за простоту и вычислительную эффективность линейных методов. Нелинейные методы сложны и вычислительно трудоемки. К счастью, существует стандартный прием, позволяющий расширять процедуры построения линейных решающих функций на нелинейные функции. Этот прием заключается в том, что вводятся обобщенные решающие функции вида
R
R
f
f
w
f
w
f
w
N
i
n
n
→
+
+
+
=
κ
:
),
(
)
(
)
(
)
,
(
2 2
1 1
x
x
x
w
x
(16)
В частности, несложно получить линейные решающие функции, используя
1
+
=
N
n
и
i
i
x
f
′
=
)
(
x

26
Функции
)
(
x
i
f
предполагаются известными заранее, то есть имеется возможность однозначно получить их значения для любого вектора x .
Тогда решающие функции вида (16) оказываются линейными по неизвестным параметрам
i
w , и несложно убедиться, что любой метод, предназначенный для нахождения параметров линейных решающих функций, также будет работать и для обобщенных решающих функций.
Один из стандартных способов задания обобщенных решающих функций – это представление их в виде многочленов (при этом, обычно используются ортонормированные системы функций, например, многочлены Лежандра или Эрмита). При этом, однако, количество параметров в обобщенной решающей функции перестает быть фиксированным.
На практике при полуавтоматическом распознавании образов варианты обобщенной решающей функции можно задавать вручную, подбирая наиболее подходящие дополнительные признаки
)
(
x
i
f
Экспериментальная
часть
В данной работе проводят анализ метода обобщенных решающих функций при задании дополнительных признаков вручную. При этом основной характеристикой является вероятность распознавания в зависимости от параметров обучающей выборки: ее размеров, наличия в ней выбросов, формы областей, занимаемых классами, – и в зависимости от привлекаемых дополнительных признаков. Для этого необходимо выполнить следующую последовательность действий.
1. Выполнить реализацию метода обобщенных решающих функций.
2. Сформировать выборку образов, которую разделить на обучающую и тестовую часть. Образы из тестовой выборки не участвуют в обучении, а используются затем для определения процента правильных ответов, даваемых при тех или иных дополнительных признаках. Разделение на обучающую и тестовую выборку желательно производить случайным образом. Размер тестовой выборки должен быть достаточно большим (по крайней мере, несколько десятков элементов).
3. Варьируя обучающую выборку, определить проценты правильного распознавания для различных дополнительных признаков (рекомендуется использовать линейные и квадратичные решающие функции). Обучающую выборку следует изменять следующим образом: добавлять и исключать из нее элементы, чтобы менялся размер выборки, вносить в обучающую выборку ошибки (для нескольких элементов указывать неправильный класс).
4. Для нелинейно разделимых классов образов осуществить перебор дополнительных признаков и найти минимальное количество признаков,

27 при которых корректное разделение находится методом обобщенных решающих функций.
5. Проанализировать полученные результаты. Определить, как влияют ошибки в обучающей выборке на метод обобщенных решающих функций, при каких размерах обучающей выборки и при каких дополнительных признаках больше процент правильного распознавания (и при какой форме областей, занимаемых классами). Сделать выводы по работе.
Литература
1.
Потапов
,
А
.
С
.
Распознавание
образов
и
машинное
восприятие
:
общий
подход
на
основе
принципа
минимальной
длины
описания /
А.С. Потапов. – СПб.: Политехника, 2007. – С. 144-152.
2.
Ту
,
Дж
.
Принципы
распознавания
образов / Дж. Ту, Р. Гонсалес –
М.: Мир, 1978. – С. 53-87.
Вопросы
для
самопроверки
:
1.
В чем заключается основная идея метода решающих функций?
2.
В каком смысле метод обобщенных решающих функций можно назвать линейным, а в каком – нелинейным? Почему для этого метода верны обе эти характеристики?
3.
Какая проблема возникает в методе обобщенных решающих функций, когда количество дополнительных признаков может быть произвольным? Как эта проблема может решаться?
4.
Любой ли формы разделяющие поверхности могут быть построены в методе обобщенных решающих функций?
5.
Как влияют выбросы в обучающей выборке на качество строящейся решающей функции? Можно ли модифицировать метод решающих функций так, чтобы он был менее чувствителен к выбросам?
4.
Изучение
методов
анализа
пространства
признаков
Цель работы – ознакомиться с методами анализа пространства признаков в рамках задач кластеризации и выбора признаков, а также освоить их применение в различных условиях, определяемых характером распределения образов обучающей выборки. Данная работа имеет два варианта выполнения.
Вариант
1
Задание
по
работе
:

28 1.
Изучить теоретическую часть работы.
2.
Реализовать метод k внутригрупповых средних.
3.
Путем варьирования взаимного расположения и формы кластеров, образуемых образами обучающей выборки, определить ограничения метода кластеризации.
Теоретическая
часть
Постановка задачи выделения кластеров в пространстве признаков
В задаче распознавания без учителя машинной системе предоставляется лишь совокупность образов
Χ
∈
i
x
,
i=1,…,M. При этом на основе этих образов система должна сформировать некое множество классов
{
}
N
a
a
a
,...,
,
2 1
=
Α
и построить решающее правило
Α
→
Χ
ϕ
:
Поскольку решающее правило относит каждый образ из обучающей выборки к одному из классов, то задача, по сути, сводится к тому, чтобы объединить образы обучающей выборки в группы (на основе которых и формируются классы). Такое объединение называется группированием.
Здесь возникает вопрос: на каком основании какие-то образы следует относить к одной группе, а какие-то – к другой?
Один из интуитивно очевидных ответов на этот вопрос заключается в том, что объединяться должны похожие друг на друга образы. Степень сходства определяется расстоянием в пространстве признаков. Выбор метрики, однако, во многом произволен, хотя чаще всего используют евклидово расстояние. Если в классы объединяются наиболее близко расположенные друг к другу образы, то задача группирования превращается в задачу кластеризации, то есть в задачу поиска кластеров
(областей, содержащих компактно расположенные группы образов).
Алгоритм k внутригрупповых средних
Алгоритм k внутригрупповых средних (или кратко алгоритм k средних) требует задания числа кластеров, исторически обозначаемых через k. Здесь для обозначения числа классов будет использоваться переменная d, а через
{
}
d
a
a
,...,
1
=
Α
будет обозначаться множество классов. Алгоритм состоит из следующих шагов:
1.
Каждому из d кластеров произвольным образом назначаются их центры (или эталонные образы)
i
,
0
x
. Часто в качестве этих центров выступают первые d образов обучающей выборки
d
i
i
i
,...,
1
,
,
0
=
=
x
x
2.
Каждый образ выборки относится к тому классу, расстояние до центра которого минимально:
(
)
M
i
s
A
j
i
a
i
j
,...,
1
,
)
,
(
min arg
,
0
=
=
Α
∈
x
x
,
(17)

29 где
)
,
(
x
x
′
s
– функция расстояния, в качестве которой может использоваться как евклидово расстояние, так и другие метрики, например, полезным может быть нормированное евклидово расстояние:
j
j
i
j
i
r
s
,
0
,
0
)
,
(
x
x
x
x
−
=
,
(18) где r
j
– размер j-го кластера. Этот размер вычисляется как внутриклассовое расстояние (среднеквадратичное расстояние от образов класса до его центра).
3.
Центры кластеров пересчитываются, исходя из того, какие образы к каждому из них были отнесены:
∑
=
∀
=
j
i
a
A
i
i
j
j
M
)
(
,
0 1
x
x
, где
j
M – количество образов
, попавших в
класс
j
a .
После пересчитываются радиусы кластеров
:
∑
=
∀
−
=
j
i
a
A
i
j
i
j
j
M
r
)
(
2
,
0 2
1
x
x
4.
Шаги
2 и
3 повторяются
, пока не будет достигнута сходимость
, то есть пока классы не перестанут изменяться
Экспериментальная

часть
В
данной работе проводят анализ метода
k внутригрупповых средних
, используемого для распознавания без учителя
(
кластеризации
).
При этом требуется установить влияние формы и
взаимного расположения кластеров на возможность их обнаружения данным методом
, а
также устойчивость результатов метода при выборе различных начальных центров кластеров
Для этого необходимо выполнить следующую последовательность действий
1.
Выполнить реализацию метода
k внутригрупповых средних
2.
Сформировать различные обучающие выборки образов
, варьирующиеся по форме кластеров
(
круглые
, сильно вытянутые
, неправильной формы типа
«
Г
»), их относительным размерам
(
одинаковые или разные размеры кластеров
) и
близости расположения кластеров
3.
Для нескольких обучающих выборок определить различия в
конечных результатах при использовании разных способов задания начальных центров кластеров
: начальные центры формируются из близко расположенных образов
, случайно выбранных образов
, наиболее удаленно расположенных образов
Оценить количество итераций
, требуемых методу для схождения
, при разных способах задания начальных центров

30 4.
Установить различия в
результатах кластеризации для нескольких обучающих выборов в
зависимости от того
, используется ли евклидово расстояние
, или оно нормируется на размеры кластеров
5.
Определить характер формируемых кластеров в
случаях
, когда заданное значение
k отличается
(
как в
большую
, так и
в меньшую сторону
) от действительного числа кластеров в
обучающей выборке
6.
Проанализировать полученные результаты
Определить ограничения метода
k средних
Сделать выводы по работе
Литература
1.
Потапов
,
А
.
С
.
Распознавание
образов
и
машинное
восприятие
:
общий
подход
на
основе
принципа
минимальной
длины
описания
/
А
С
Потапов
. –
СПб
.:
Политехника
, 2007. –
С
. 185-191.
2.
Ту
,
Дж
.
Принципы
распознавания
образов
/
Дж
Ту
,
Р
Гонсалес
–
М
.:
Мир
, 1978. –
С
. 101-112.
Вопросы
для
самопроверки
:
1.
К
какому типу методов распознавания относится метод
k внутригрупповых средних
?
2.
Какое ограничение данного метода мешает утверждать
, что метод является полностью автоматическим
?
3.
Классы какой формы строятся методом
k внутригрупповых средних
?
4.
Какой способ задания начальных центров кластеров в
данном методе предпочтительнее
?
5.
В
чем различие метода
k средних при нормировании евклидового расстояния на размеры кластеров и
без нормирования
?
6.
Какие эффекты возникают
, когда заданное значение
k больше или меньше действительного числа кластеров
?
Вариант
2
Задание
по
работе
:
1.
Изучить теоретическую часть работы
2.
Реализовать метод оценивания плотности вероятностей на основе смесей
3.
Путем варьирования компонент смеси и
их количества
, определить ограничения метода на основе смесей
Теоретическая
часть