_учебник_ Журавлёв Ю.И. Математические основы теории пронозирования (2008) (1185334)
Текст из файла
Московский государственный университетимени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиМатематические основытеории прогнозирования(курс лекций)лектор — академик РАН Ю. И. Журавлев2008Оглавление1Стандартная задача распознавания . . . . . . . . . . . . . . . .
. . . . . . . .Алгоритм “Кора” (Вайнцвайг, Бонгарт) . . . . . . . . . . . . . . . . . . . . . .Тестовый алгоритм (Ю. И. Журавлев) . . . . . . . . . . . . . . . . . . . . . .33462.1Логические алгоритмы распознавания . . . . . . . . . . . . . . . . . . . . . .993.13.216Алгоритмы вычисления оценок . . .
. . . . . . . . . . . . . . . . . . . . . . . 16Эффективные формулы вычисления оценок . . . . . . . . . . . . . . . . . . . 204.14.224Вычисление характеристик, определяющих алгоритм вычисления оценок . . 24Алгебры над алгоритмами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261.11.21.32345285.1Построение алгоритмов распознавания, корректных для заданной контрольной выборки . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281Курс лекций, прочитанный для 3 потока IV курса факультета ВМиК, набран в системеLATEX студентами:1 лекция — П. Клеменков2 лекция — А. Гудков3 лекция — К. Симонян4 и 5 лекции — А. Фокин2Лекция 11.1Стандартная задача распознаванияПусть дано множество M , являющееся суммой подмножеств K1 , . .
. , Kl , называемыхобычно классами.l[M=Kjj=1Различают случаи а) Ku ∩Kv = ∅, б) Ku ∩Kv , вообще говоря, не пусто. В случае а) говорято задаче с пересекающимися, в случае б) — непересекающимися классами (множестваKj , j = 1 . . . l принято называть классами).В дальнейшем рассматриваются только M специального вида: элементы M являются наборами длины n: ã ∈ M, ã = (a1 , a2 , . . .
, ai , . . . , an ). При этом для каждого номераi, i = i . . . n, определено множество допустимых значений Mi , являющееся метрическимпространством с метрикой ρi , т.е. выполнены аксиомы: ρi (c, d) ≥ 0, ρi (c, c) = 0, ρi (c, d) == ρi (d, c), ρi (c, e) + ρi (e, d) ≥ ρi (c, d), c, d, e ∈ Mi .
В некоторых случаях выполнения последней аксиомы (аксиомы треугольника) не требуют. Тогда говорят, что в Mi введенаполуметрика.В качестве исходной информации задаются некоторые сведения о множестве M и классах K1 , . . . , Kl .В дальнейшем в качестве исходной информации рассматривается так называемая стандартная обучающая информация I: выделяется конечное множество S1 , . . . , Sm элементовиз M : Si = (ai1 , ai2 , . . . , ait , . . . , ain ), i = 1 . . .
m, ait ∈ Mt , для которых известно, в какиеиз K1 , . . . , Kl они входят. Последнее оформляется заданием информационного вектораα̃(Si ) = (αi1 , αi2 , . . . , αij , . . . , αin ), (αij = 1) → Si ∈ Kj , (αij = 0) → Si ∈/ Kj , i = 1 . . . m,j = 1 . . . l.Для удобства данные об элементах Si и их информационных векторах представляютв виде таблиц:12... t... nS1 a11 a12 . . . a1t . .
. a1nS2 a21 a22 . . . a2t . . . a2n... ... ... ... ... ... ...Si ai1 ai2 . . . ait . . . ain... ... ... ... ... ... ...Sm am1 am2 . . . amt . . . amn|{z}T13K1α11α21...αi1...αm1|K2α12α22...αi2...αm2.....................Kjα1jα2j...αij...αmj{z.....................Klα1lα2l...αil...αmlT2α̃(S1 )α̃(S2 )...α̃(Si )...α̃(Sm )}Совокупность таблиц T1 , T2 называется стандартной обучающей информацией I, таблица T2 называется информационной матрицей.Стандартная задача распознавания: пусть задан элемент S ∈ M, S ∈/ {S1 , S2 , . . . , Si ,. . . , Sm }. Найти алгоритм A, который, используя только I и представление S строит информационный вектор α̃(S) = (α˜1 (S), .
. . , α̃j (S), . . . , α̃l (S)).A(I, S) = α̃(S).В задачах распознавания часто обучающая информация I оказывается недостаточнойдля построения “правильного” вектора α̃(S). Поэтому допускаются и широко используются эвристические алгоритмы, допускающие ошибки и отказы при вычислении координатинформационных векторов.Такие алгоритмы Ã(I, S) строят квази-информационные векторы β̃(S) = (β1 (S), . .
. ,βj (S), . . . , βl (S)). При этом возможно, что: βj (S) 6= α̃j (S) (ошибка в распознавании),βj (S) = ∆ — так кодируется отказ от вычисления j-й координаты информационного вектора.В литературе описано значительное число таких эвристических алгоритмов, допускающих небольшое (допустимое при практическом применении) число ошибок и отказовпри решении достаточно узких классов реальных прикладных задач. Мы опишем два таких алгоритма, получивших большое распространение при прогнозировании в геологии,медицине, технике и т.п.В дальнейшем координаты 1, 2, .
. . , n, задающие n-мерные объекты в M , будем называть признаками.1.2Алгоритм “Кора” (Вайнцвайг, Бонгарт)Применяется для M , элементами которых являются бинарные признаки: Mi = {0, 1},i = i . . . n, в основном для задач с двумя непересекающимися классами: M = K1 ∪ K2 ,K1 ∩ K2 = .В таблице kaij km×n , задающей объекты с известной классовой принадлежностью, пустьS1 , . . . , Sq принадлежат K1 , Sq+1 , .
. . , Sm принадлежатK2 . Просматриваем все тройки признаков r, u, v (число таких троек, очевидно, равно n3 ) и анализируем часть таблицы T1 ,4составленной только из столбцов r, u, v:a1ra1ua1va2ra2ua2v·········airaiuaiv·········aqraquaqvaq+1r aq+1u aq+1vaq+2r aq+2u aq+2v·········ajrajuajv·········amramu amvСреди первых q строк выделяем и фиксируем все тройки, не совпадающие ни с одной из троек в строках q + 1, . . . , m.
Формируем множество таких троек {(air , aiu , aiv )}.Аналогично выделяем все тройки (ajr , aju , ajv ), не совпадающие ни с одной из первых qтроек. Множества {(air , aiu , aiv )}, {(ajr , aju , ajv )} назовем, соответственно, характеристиками классов K1 , K2 . Такие характеристики формируем для всех троек (r, u, v).Пусть задан для распознавания объект S = (b1 . . . br . . . bu .
. . bv . . . bn ). Сравниваем всехарактеристики всех троек для K1 с соответствующими тройками в распознаваемом объекте S. Число совпадений (air , aiu , aiv ) = (br , bu , bv ) обозначаем Γ(S, K1 ) — число голосов,поданных для S за класс K1 . Аналогично формируем величину Γ(S, K2 ): число совпадений(ajr , aju , ajv ) = (br , bu , bv ). Вводим пороговый параметр ν.Если Γ(S, K1 ) − ν > Γ(S, K2 ), относим S классу K1 , при Γ(S, K2 ) − ν > Γ(S, K1 ) — вкласс K2 .
В остальных случаях алгоритм отказывается от классификации. На практикечасто полагают ν = 0.Пример 1Дана таблица T1S1S2S3S4S5S611001102010001310100040101005001011Имеем 53 = 10 троек признаков. Перечислим характеристики для K1 и K2 .Характеристики для K1 :1.(1, 2, 3) : (101), (001)3.(1, 2, 5) : (010), (001)5.(1, 3, 5) : (100), (000), (011)7.(2, 3, 4) : (010), (101)9.(2, 4, 5) : (000), (110)2.(1, 2, 4) : (011), (000)4.(1, 3, 4) : (110), (001), (010)6.(1, 4, 5) : (100), (010)8.(2, 3, 5) : (010), (100), (011)10.(3, 4, 5) : (100), (101)5Характеристики для K21.(1, 2, 3) : (100)3.(1, 2, 5) : (101), (011)5.(1, 3, 5) : (100), (101), (001)7.(2, 3, 4) : (001), (000), (100)9.(2, 4, 5) : (010), (101)2.(1, 2, 4) : (101), (010)4.(1, 3, 4) : (101), (100), (000)6.(1, 4, 5) : (110), (101)8.(2, 3, 5) : (000), (001), (101)10.(3, 4, 5) : (011)Очевидно, что с увеличением n (числа признаков) число троек в характеристиках растет весьма быстро.
Поэтому при реальных решениях обязательно использование компьютеров.Заметим, что для объекта S = (00000) : Γ(S, K1 ) = Γ(S, K2 ) = 3. Поэтому алгоритм неклассифицирует этот объект.При распознавании объекта S = (10101) имеют место совпадения с элементами характеристики K1 : (1, 2, 3), (101); (1, 3, 4), (110); (2, 3, 4), (010); (2, 3, 5), (011); (3, 4, 5), (101). Следовательно, Γ(S, K1 ) = 5. Легко проверить, что Γ(S, K2 ) = 2. Алгоритм “Кора” заносит Sв класс K1 .1.3Тестовый алгоритм (Ю. И.
Журавлев)Пусть задана бинарная таблица kaij km×n , строки которой S1 , . . . , Sm разделены на двакласса, причем S1 , . . . , Sq — строки первого класса K1 , Sq+1 , . . . , Sm — строки второгокласса K2 .Набор столбцов с номерами k1 , . . . , kl образует тест, если после удаления из таблицывсех столбцов за исключением вышеозначенных, ни одна из строк из K1 не совпадет нис одной из строк класса K2 . Тест называется тупиковым, если при удалении из него хотябы одного столбца, хотя бы одна из строк K1 совпадет хотя бы с одной из строк K2 .Предположим, что построены все тупиковые тесты T1 , .
. . , Tr бинарной таблицы,Ti = {ni1 , . . . , nip(i) }, i = 1 . . . r, nuv — номера столбцов, входящих в тест.Распознаваемый объект S = (a1 . . . an ) последовательно совмещается с тупиковымитестами. При работе с тестом Ti набор ani1 , . . . , anip(i) сравнивается по столбцам теста совсеми строками таблицы kaij km×n . При этом возможно совпадение со строкой не более чемв одном из классов K1 , K2 (это следует из определения теста). Число совпадений суммируется отдельно для классов K1 , K2 . Полученные суммы Γ(S, K1 ), Γ(S, K2 ) используютсядля классификации объекта S так же, как в алгоритме “Кора”.Понятия “тест” и “тупиковый тест” нетрудно распространить для таблиц, составленных из элементов произвольной природы.
Необходимо только, чтобы элементы каждогостолбца содержались в метрическом пространстве. Обозначим метрику этого пространства через ρt . Два элемента ait , ajt назовем различимыми, если ρt (ait , ajt ) > t ; в противномслучае ait , ajt неразличимы. В определении теста достаточно заменить слова “равны” и“не равны” на “неразличимы” и “различимы”. Значение t задается из “содержательных”соображений или определяется при решении другой задачи.Построение совокупности тупиковых тестов связано с решением системы базовых уравнений.Пусть дана системаfi (x1 .
. . xn ) = 1, i = 1 . . . k.(1.1)Система (1.1) эквивалентна одному уравнениюkYfi (x1 . . . xn ) = 1.i=16(1.2)Представим fi в виде дизъюнктивной нормальной формы (д.н.ф.)_f i = Di =Kit(i) ,iσгде Kit(i) — элементарные конъюнкции, т.е. произведения вида xσj11 · . . .
· xjpp , xσ = x приσ = 1, x̄ при σ = 0.Выполним в (1.2) операции логического умножения и получим финальную д.н.ф.r_δQi = xδi11 · . . . · xipp .Qi = 1.i=1Последовательно решаем уравнения Qi = 1; xi1 = δ1 , . . . , xip = δp , остальные xj = 0, 1.Совокупность всех решений и есть совокупность всех решений системы (1.1).Выведем систему уравнений для построения всех тупиковых тестов таблицы kaij km×n ,в которой строки S1 , . .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
