2010 Лекции МОТП. Записки (1185265), страница 11

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

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

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

Отметим, что вмодели с представительными наборами (как и для тестового алгоритма) возможны идругие способы вычисления оценок (181). Например, другие нормировки или весовыекоэффициенты – множители перед B ( S , u ) , равные числу эталонов класса K j , в которыхвстречается u .Для нахождения тупиковых представительных наборов, содержащихся в некоторомэталоне S j , формируются матрицы сравнения S j со всеми эталонами других классов.Тупиковыепокрытияданныхматрицсравненияиопределяюттупиковыепредставительные наборы. Однако, если для поиска тупиковых тестов таблицы T nmlтребуется решать задачу на покрытия для матрицы изN=∑ (m − mi> ji −1i)(m j − m j −1 )i , j =1, 2 ,...,lстрок и n столбцов, то для поиска тупиковых представительных наборов объекта Si ∈ K jзадача на покрытия решается для матрицы из (m − m j ) строк и n столбцов.

Такимобразом, нахождение множества всех тупиковых представительных наборов таблицы T nmlтребует решения m задач на покрытия но «малой » размерности /Дюкова/.Вопрос обобщения алгоритмов распознавания с представительными наборами на случаиk- значной и вещественнозначной информации информации решается аналогичнотестовому алгоритму. Множество допустимых значений некоторого признака делится наконечное число интервалов, каждому из которых приписывается целое число 0, 1, 2,…,или k. Таблице T nml и распознаваемым объектам ставятся в соответствие строки новыхцелочисленных значений признаков.

Далее процесс определения тупиковыхпредставительных наборов и распознавания полностью идентичен бинарному случаю.Другое распространение на вещественнозначные признаки связано с введениемпороговых параметров ε 1 , ε 2 ,..., ε n и следующей модификацией понятияпредставительного набора: наборu = {xi1 ( Sν ), xi2 ( Sν ),..., xik ( Sν ), }называетсяпредставительным набором для класса K j , если для любого S µ ∈ T nml ,⋅S µ ∉ Kбы одно из неравенствjхотяxt ( Sν ) − xt ( S µ ) ≤ ε t , t = i1 , i2 ,..., ik будет невыполненным.64Заметим, что дискретизация признаков или введение пороговых параметров ε 1 , ε 2 ,..., ε nздесь могут быть индивидуальны для каждого эталона.

Главным требованием их выбораявляется отделимость рассматриваемого объекта Si ∈ K j относительно эталонов из СK j .Отметим, что , в отличие от тестового алгоритма, описанная модель с представительныминаборами допускает пересечение классов. В последнем случае оказываются«бесполезными» объекты, по которым классы пересекаются, поскольку данные объектыне содержат представительных наборов. Впрочем, существуют модификации понятияпредставительного набора, допускающие и пересечение классов.Можно провести аналогию тестов и представительных наборов с линейными и кусочнолинейными разделяющими поверхностями. Тестовый алгоритм как и модели сразделяющими гиперплоскостями требуют отделимость классов, и в них особое значениеимеют «граничные» эталоны классов. Модель с представительными наборами и кусочнолинейные модели являются «менее требовательными» к обучающей информации.

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

Алгоритмы данных моделей определяются заданием шестипоследовательных этапов, для которых могут быть использованы различные конкретныеспособыопределенияиливыполнения.Тестовыйалгоритмиалгоритмыспредставительными наборами могут быть представлены как частные случаи более общейконструкции. Ниже будут приведены лишь некоторые основные способы их выполнения.Подробно данные вопросы рассмотрены в /…/.1. Задание системы опорных множеств алгоритма.

Первым шагом определения АВОявляется задание множества подсистем признаков, по которым осуществляется сравнениеобъектов. Пусть Ω A - некоторая система подмножеств множества {1,2,…,n}, называемаясистемой опорных множеств алгоритма A. Элементы Ω= {i1 , i2 ,..., ik } ∈Ω A называютсяопорными множествами алгоритма.

Они определяют номера признаков, по которымсравниваются части эталонных и распознаваемых объектов. Примером выбора системы65опорных множеств Ω A является множество тупиковых тестов. Каждому подмножеству Ω={i1 , i2 ,..., ik } можно поставить во взаимно однозначное соответствие характеристическийбулевский векторω = {ω1 , ω 2 ,...,ω n } , в котором ω j = 1, j = i1 , i2 ,..., ik , а остальныекомпоненты равны нулю. В силу данного соответствия Ω ↔ ω , использование данныхвеличин будет для нас равнозначным.Множество всех n-мерных булевских векторов определяет дискретный единичныйnкуб E = {ω : ω = (ω1 , ω 2 ,..., ω n )} , ωi ∈{0,1}, i = 1,2,..., n . Число элементов куба равно2n .Теоретические исследования свойств тупиковых тестов для случайных бинарныхтаблиц показали, что характеристические векторы «почти всех тупиковых тестов» имеютасимптотически (при неограниченном возрастании размерности таблицы обучения)приблизительно одну и ту же длину.

Это явилось одним из обоснований выбора вкачестве множества Ω A всевозможных подмножеств {1,2,…,n} длины k. Значение kнаходится из решения задачи обучения (оптимизации модели) или задается экспертом. Витоге, широко распространенными подходами к выбору Ω A являются(наряду ступиковыми тестами) следующие два:а) Ω = {Ω : Ω = k} ;Ab) Ω A = {Ω}, Ω ⊆ {1,2,..., n}, Ω ≠ ∅.Второй способ выбора системы опорных множеств, как всевозможных подсистем {1,2,…,n}, является «усреднением» первого и не требует нахождения подходящего значенияпараметра k.2.

Задание функции близости. Пусть фиксировано некоторое опорное множество Ω исоответствующий ему характеристический вектор ω. Фрагментобъектаxi1 ( S ), xi2 ( S ),...xik ( S )S = ( x1 ( S ), x2 ( S ),...xn ( S ) , соответствующий всем единичным компонентамвектора ω, называется ω-частью объекта, и обозначается ωS. Под функцией близостиBΩ ( S i , S j ) будет пониматься функция от соответствующих ω-частей сравниваемыхобъектов, принимающая значение 1 («объекты близки») или 0 («объекты далеки»).Приведем примеры подобных функций.1, | xi ( Sν ) − xi ( S µ ) |≤ ε i , ∀i : ωi = 1, ω ↔ Ω,иначе.0,а) BΩ ( Sν , S µ ) = 66Здесь(ε1, ε 2 ,... , ε n )- неотрицательные параметры, именуемые «точности измеренияпризнаков».1,b) BΩ ( Sν , S µ ) = 0,n∑| xi ( Sν ) − xi ( S µ ) |≤ ε ,i =1иначе.Здесь ε также некоторый неотрицательный параметр алгоритма.3.

Оценка близости объекта S к эталонному объектуSiдля заданной ω-части.Данная числовая величина формируется на основе функции близости и, возможно,дополнительных параметров.a)ΓΩ ( S i , S ) = BΩ ( Si , S ) .b)ΓΩ ( Si , S ) = wΩ BΩ ( Si , S ) , где wΩc)- «вес» опорного множества.ΓΩ ( Si , S ) = γ i ( ∑ pi ) BΩ ( S i , S ) .i:ωi =1степень важности объектаSiЗдесьγi- параметры, характеризующие(информативность объекта), аp1 , p 2 ,... p n- веса(информативность) признаков.4.

Оценка объекта S за классΓ jΩ ( S ) =а) ФункцияKjдля заданной ω-части.1∑ ΓΩ (S i , S ) является примером естественной(m j − m j −1 ) Si ∈K jоценки близости объекта к классу для заданного подмножества признаков.5. Оценка объекта S за классKj .Данная функция задает суммарную степень близости распознаваемого объекта S к классуK j . Приведем обычно используемые выражения для ее вычисления.a) Γ j ( S ) =∑ΓΩ∈Ω Ab) Γ j ( S ) = v jΩj(S ) .∑ΓΩ∈Ω AΩj( S ) , гдеvj- «вес» классараспознавания аналогами параметровvjK j .

Например, в статистической теорииявляютсяаприорные вероятности классов,которые характеризуют, насколько часто встречаются объекты различных классов .676. Решающее правило.Решающее правило есть правило (алгоритм, оператор), относящее объект повектору оценок за классы в один из классов, или вырабатывающее для объекта «отказ отраспознавания». Отказ является более предпочтительным вариантом решения в случаях,когда оценки объекта малы за все классы (объект является принципиально новым, аналогикоторого отсутствуют в обучающей выборке), или он имеет две или более близкиемаксимальные оценки за различные классы (объект лежит на границе классов).В формальной постановке, решающее правило r вычисляет для распознаваемогообъектаSповекторуоценокΓ ( S ) = (Γ1 ( S ), Γ2 ( S ),..., Γl ( S ))булевскийвекторr ( Γ ( S )) = (α1A ( S ), α 2A ( S ),...,α lA ( S )),α i ( S ) ∈ {0,1, ∆}, i = 1,2,..., l.

Интерпретация обозначенийприведена ранее в (898).а) Пример простейшего решающего правила – отнесение объекта в единственный класс,за который он имеет максимальную оценку.1, Γ j ( S ) > Γi ( S ), i = 1,2,..., l , i ≠ j ,α jA ( S ) = иначе.0,b) Для «осторожного» принятия решения относительно принципиально новых объектов,или находящихся на границе двух и более классов, обычно достаточно введение врешающееправилодвухпороговыхпараметровΓ j ( S ) > Γi ( S ) + δ1 , i = 1,2,..., l , i ≠ j ,1,lAα i (S ) = Γ j ( S ) > δ 2 ∑ Γi ( S ),i =10,иначе.lδ ij Γ j ( S ) ≥ c1i , 1,∑j =1lAiiic) α i ( S ) = ∆ , c1 > ∑ δ j Γ j ( S ) > c2 ,j =1lδ ij Γ j ( S ) ≤ c2i ,∑ 0,j =1(5)68Здесьδ1 , δ 2 , δ ij , c1i , c2i- параметры алгоритма.

В последнем случае (5) наличие двухили более единиц интерпретируется как «объект принадлежит нескольким классам».Когда бинарный вектор состоит из одних нулей говорят, что данный объект – выброс, онне похож ни на один из классов, близких его аналогов ранее не наблюдалось.Использование решающего правила означает фактически переход из признаковогопространства в пространство оценок, в котором в качестве разделяющих классы функцийиспользуются гиперплоскости, проходящие через начало координат симметричноотносительно новых координатных осей (случай a), пары гиперплоскостей (случай b), инаборы из l-1 гиперплоскостей.Варьируя в моделях вычисления оценок правила определения этапов 1-6 (часть примерових определения приведена выше), можно получить различные модели распознающихалгоритмов типа вычисления оценок.Если конкретные правила этапов (1-5) определены, то после последовательнойподстановки выражений на этапах 2-5 могут быть получены различные общие формулыдля вычисления оценок Γ j (S ) .

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

Список файлов лекций