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

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

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

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

Ниже будут приведены лишьнекоторые основные способы их выполнения. Подробно данные вопросырассмотрены в [] и в прилагаемой библиографии.2.2.1. Основные определения и этапы алгоритмов вычисления оценок1. Задание системы опорных множеств алгоритма. Первым шагомопределения АВО является задание множества подсистем признаков, по14которым осуществляется сравнение объектов. Пусть Ω A - некоторая системаподмножеств множества {1,2,…,n}, называемая системой опорных множествалгоритмаA.ЭлементыΩ= {i1 , i2 ,..., ik } ∈Ω Aназываютсяопорнымимножествами алгоритма. Они определяют номера признаков, по которымсравниваются части эталонных и распознаваемых объектов. Каждомуподмножеству Ω= {i1 , i2 ,..., ik } можно поставить во взаимно однозначноесоответствиебулевскийвекторω = {ω1 , ω 2 ,...,ω n } ,вкоторомω j = 1, j = i1 , i2 ,..., in , а остальные компоненты равны нулю.Геометрически, множество всехопределяетдискретныйединичный2nn-мерных булевских векторовкубE n = {ω : ω = (ω1 , ω 2 ,..., ωn )} ,ωi ∈{0,1}, i = 1,2,..., n .Теоретическиеисследованиясвойствтупиковыхтестовдляслучайных бинарных таблиц показали, что характеристические векторы«почти всех тупиковых тестов» имеют асимптотически (при неограниченномвозрастании размерности таблицы обучения) приблизительно одну и ту жедлину.

Это явилось одним из обоснований выбора в качестве множества Ω Aвсевозможных подмножеств {1,2,…,n} длины k. Значение k находится изрешения задачи обучения (оптимизации модели) или задается экспертом. Витоге, широко распространенными подходами к выбору Ω A являются(наряду с тупиковыми тестами) следующие два:а) Ω A = {Ω : Ω = k} ;b) Ω A = {Ω}, Ω ⊆ {1,2,..., n}, Ω ≠ ∅.Второй способ выбора системы опорных множеств, как всевозможныхподсистем{1,2,…,n}, является «усреднением» первого и не требуетнахождения неизвестных параметров.2. Задание функции близости.Пусть фиксировано некоторое опорноемножество Ω и соответствующий ему характеристический вектор ω.15Фрагмент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, ω ↔ Ω,а) BΩ ( Sν , S µ ) = иначе.0,Здесь (ε1, ε 2 ,... , ε n ) - неотрицательные параметры, именуемые «точностиизмерения признаков».1,b) BΩ ( Sν , S µ ) = 0,n∑i =1| xi ( Sν ) − xi ( S µ ) |≤ ε ,иначе.Здесь ε также некоторый неотрицательный параметр алгоритма.3.

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

p n - веса (информативность) признаков.4. Оценка объекта S за класс K j для заданной ω-части.Ωa) Γ j ( S ) =1∑ ΓΩ (S i , S ) .(m j − m j −1 ) Si ∈K j165. Оценка объекта S за класс K j .Γ jΩ ( S ) .a) Γ j ( S ) = Ω∑∈ΩAΓj (S ) = v jb)∑ΓΩ∈Ω AΩj( S ) , гдеv j - «вес» класса K j . Например, встатистической теории распознавания аналогами параметровv j являютсяаприорные вероятности классов, которые характеризуют, насколько частовстречаются объекты различных классов .6. Решающее правило.Решающее правило – правило (алгоритм, оператор), относящееобъект по вектору оценок за классы в один из классов, или вырабатывающеедля объекта «отказ от распознавания». Отказ возникает обычно в случаях,когда оценки объекта малы за все классы (объект является принципиальноновым, аналоги которого отсутствуют в обучающей выборке), или он имеетдве или более близкие максимальные оценки за различные классы (объектлежит на границе классов).

Таким образом, решающее правило r вычисляетдляраспознаваемогообъектаSбулевскийвекторr ( S ) = (α1 ( S ),α 2 ( S ),..., α l ( S )),α i ( S ) ∈ {0,1, ∆} , где α i ( S ) = 1 означаетотнесение объекта в класс K i , α i ( S ) = 0 - принятие решения: «объект S непринадлежит классу K i », α i (S ) = ∆ соответствует отказу от распознаванияобъекта относительно класса K i . Приведем примеры решающих правил.a) Простейшее решающее правило – отнесение объекта в класс, закоторый он имеет максимальную оценку, и отказ от распознавания вслучае двух и более максимальных оценок.Γj ( S ) > Γi ( S ), i = 1,2,..., l , i ≠ j , 1,α j ( S ) =  0, Γj ( S ) < max{Γi ( S ), i = 1,2,..., l , i ≠ j},∆ ,иначе17b)Γj ( S ) > Γi ( S ) + δ1 , i = 1,2,..., l , i ≠ j ,1,lα j (S ) = , гдеΓj ( S ) > δ 2 ∑ Γi ( S ),i =10,иначе.δ1 , δ 2-неотрицательные параметры решающего правила. 1,c) α i ( S ) =  0,∆ ,Здесьl∑δijΓ j ( S ) ≥ δ li+1 ,∑δijΓ j ( S ) ≤ δ li+ 2 ,j =1lj =1, гдеδ li+1 > δ li+ 2 .(5)иначе.δ 1 , δ 2 , δ ij - параметры алгоритма.

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

Эффективные формулы вычисления оценокПосле последовательной подстановки выражений на этапах 2-5могут быть получены различные общие формулы для вычисления оценокΓ j (S ) . Например, выбирая первые примеры реализации различных этапов18будет получена следующая общая формула для вычисления оценок объекта Sза классы K j , j=1,2,…,l.mj1Γj (S ) =∑ ∑ BΩ (Sν , S ) .(m j − m j −1 ) ν =m j −1 +1Ω∈Ω A(6)При выборе системы опорных множеств согласно вариантам a) илиb) прямое вычисление оценок (6) представляется весьма трудоемким.kДействительно, при вычислении оценок (6) согласно a) требуется mCnвычислений значений функции близости.

В действительности необходимостьвыполнения всех данных вычислений отсутствует, поскольку существуютэффективные комбинаторные формулы вычисления оценок при многихвариантах реализации этапов 2-5 и различных системах опорных множеств.Теорема 1. Пусть в модели вычисления оценок используютсяварианты a) выполнения этапов, тогда справедлива формулаΓj ( S ) =1Cdk ( S ,Si )∑, где(m j − m j −1 ) Si∈K jd ( S , S i ) = {ν : xν ( S i ) − xν ( S ) ≤ εν ,ν = 1,2,..., n} .Доказательство.Для доказательства достаточно показать, что∑BΩ∈Ω AΩ( Sν , S ) = С dk ( S ,Si ) .Действительно, данная сумма является общим числом «совпадений»фрагментов Sν и S длины k. Но данное число и равноСdk ( S , S i ) .Следствие.

Пусть в модели вычисления оценок используются варианты a)выполнения этапов 2-5 и b) - первого, тогда справедлива формула19Γj ( S ) =1(2 d ( S ,Si ) − 1)∑, где(m j − m j −1 ) Si∈K jd ( S , S i ) = {ν : xν ( S i ) − xν ( S ) ≤ εν ,ν = 1,2,..., n} .mj1Действительно, Γ j ( S ) =∑ ∑ BΩ (Sν , S ) =(m j − m j −1 ) ν =m j −1 +1Ω∈Ω Ad ( S , Si )n11kC d ( S , Si ) =Cdk ( S ,Si ) =∑∑∑∑(m j − m j −1 ) Si∈K j k =1(m j − m j −1 ) Si∈K j k =11(2 d ( S ,Si ) − 1)∑.(m j − m j −1 ) Si∈K jТеорема 2. Пусть в модели вычисления оценок используютсяварианты a) выполнения этапов 1,2,4,5, и c) этапа 3 (т.е.ΓΩ ( Si , S ) =γ i ( ∑ pi ) BΩ ( Si , S ) ), тогда справедлива формулаi:ωi =1Γj ( S ) =1γ i ( ∑ pt )Cdk (−S1 ,Si )−1∑, где(m j − m j −1 ) Si∈K j t∈J ( S ,Si )J ( S , Si ) = {ν : xν ( Si ) − xν ( S ) ≤ εν ,ν = 1,2,..., n} , d ( S , S i ) = J ( S , S i ) .Доказательство.mj1По определению, Γ j ( S ) =∑ γ ν ∑ (∑ pi ) BΩ (Sν , S )(m j − m j −1 ) ν =m j −1 +1 Ω∈Ω A i∈Ωmj1=∑ γ ν ( ∑ pi )ϕ ( S , Sν ) .

Действительно, из определения(m j − m j −1 ) ν =m j −1+1 i∈J ( S ,Sν )20функции близости следует, что в сумму могут войти лишь те веса признаков,по которым объекты не различимы с точностью до соответствующего порога.Коэффициенты при данных pi для фиксированного Sν будут равны в силусимметрии. Но тогдаϕ ( S , Sν )будет равно числу способов выбора изk −1оставшихся d ( S , Sν ) -1 признаков по k-1 признаку, т.е. С d ( S ,Sν )−1 . Теоремадоказана.В теории алгоритмов вычисления оценок существуют и другие эффективныеформулы вычисления оценок для более сложно определенных способов ихвычисления.2.3. Алгоритмы голосования по представительным наборамДругими алгоритмами данного вида являются алгоритмы типа “Кора” /16,12/,в которых опорные множества связаны со значениями признаков конкретныхобъектов.ПустьSν ∈ K j .представительнымдлялюбогоНаборε−u = {xi1 ( Sν ), xi1 ( Sν ),..., xi1 ( Sν ),}называетсянабором (или просто набором) для класса K j , еслиS µ ∈ T nml ,⋅S µ ∉ Kxt ( Sν ) − xt ( S µ ) ≤ ε t , t = i1 , i2 ,..., ikjнесовместна.системанеравенствПредставительныйнаборназывается тупиковым, если любой его собственный поднабор не являетсяпредставительным набором, т.е.

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

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