Ю.И. Журавлёв - Математические основы теории прогнозирования (курс лекций)

Московский государственный университетимени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиМатематические основытеории прогнозирования(курс лекций)лектор — академик РАН Ю. И. Журавлев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 = 1 . . . 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 неразличимы. В определении теста достаточно заменить слова “равны” и“не равны” на “неразличимы” и “различимы”.