Информационная система принятия решений (задачи кредитования)

В роли критерия качества решения задачи распознавания, используется обычно функционал, равный числу неверных классификаций некоторой последовательности изображений, называемой контрольной, истинная классификация которых известна.

Очевидно, что чем меньше значение этого функционала, тем лучше решена задача распознавания.

3.4 Гипотеза компактности

При формировании образа (класса) человек, по-видимому, выделяет у предъявляемых ему изображений элементы сходства и различия. Наличие этих элементов и позволяет относить изображения к тому или иному образу (классу). По аналогии будем предполагать, что в пространстве признаков изображения, принадлежащие одному и тому же образу, близки, а изображения, принадлежащие различным образам, хорошо разделимы друг от друга. Это предположение о свойствах изображений в пространстве признаков и составляет сущность гипотезы компактности. Конкретизируя, можно сказать, что содержательно гипотеза компактности предполагает:

1) любые две внутренние точки пространства признаков, принадлежащие одному и тому же классу (образу) можно соединить достаточно гладкой кривой, все точки которой будут принадлежать тому же классу (образу);

2) почти все внутренние точки, принадлежащие тому или иному классу (образу), в достаточно большой окрестности имеют только изображения из своего класса (образа);

3) число граничных точек мало. Гипотеза компактности есть некоторое допущение относительно свойства изображений группироваться в образы в пространстве признаков. Предполагая справедливость гипотезы компактности, мы тем самым обосновываем методически решение задачи распознавания как задачу поиска разбиения пространства изображений с помощью некоторой поверхности. Коль скоро изображения группируются в разделяемые множества (т.е. в образы), то поиск разделяющей поверхности становится оправданным.

3.5 Детерминистские методы распознавания

Постановка задачи. Будем считать, что задано пространство признаков Х размерности n 1. Точками х этого пространства являются изображения х = (x1,…,xn). Пусть известно число L классов (образов) K1,…, KL, к которым могут относиться всевозможные изображения х из Х. Пусть также для некоторых изображений из пространства Х известны классы (образы), к которым они принадлежат: принадлежат K1,принадлежат K2, и т. д., принадлежат KL, причем каждому из L классов принадлежит не менее одного изображения, т. е. ik > 1, k = 1,..., L. Последовательность ,…, будем называть обучающей.

Под детерминистской постановкой задачи распознавания будем подразумевать задачу отыскания разбиения пространства признаков Х на L взаимно непересекающихся областей, каждая из которых соответствует некоторому классу (образу). Построение искомого разбиения, т. е. обучение, будем проводить исходя из собственно обучающей последовательности, не используя те или иные ее стохастические свойства. Таким образом, мы рассматриваем в детерминистской постановке задачу обучения с учителем. Различные методы решения этой задачи составляют детерминистские методы распознавания:

· метод разделяющей функции,

· метод комитетов решения задачи распознавания,

· метод потенциальных функций,

· алгоритмы распознавания, основанные на вычислении оценок (АВО).

3.6 Алгебраический подход к задачам распознавания

Постановка задачи. Пусть в пространстве изображений Х дана обучающая последовательность изображений, принадлежащих L классам K₁,…, K_L. Пусть имеется совокупность алгоритмов распознавания {А}, каждый алгоритм из множества {A} классифицирует произвольное изображение х, основываясь на обучающей последовательности. Если ввести функционал качества как долю нераспознанных изображений на некоторой контрольной последовательности, то, как это было рассмотрено, можно ставить задачу отыскания оптимального по качеству алгоритма распознавания среди алгоритмов {А}. При этом подходе была рассмотрена задача построения на базе совокупности алгоритмов распознавания {A}такого алгоритма, который бы обеспечивал безошибочное распознавание контрольной последовательности изображений.

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

Определение. Совокупность алгоритмов распознавания {A}называется корректной, если для любых обучающей и контрольной последовательностей, в совокупности {А}имеется такой алгоритм, который не ошибается на контрольной последовательности. Нашей задачей будет являться изучение вопроса о корректности той или иной совокупности алгоритмов распознавания.

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

На первом этапе вычисляется близость изображений контрольной последовательности к классам, на которые необходимо их расклассифицировать, а на втором этапе решающее правило по этой близости определяет те классы, к которым относятся изображения контрольной последовательности. Для совокупности таких распознающих алгоритмов можно ввести операции сложения, умножения на скаляр, произведения. Эти алгебраические операции над некоторой совокупностью распознающих алгоритмов {A} позволяют конструировать новые распознающие алгоритмы. Как уже отмечалось одним из основных вопросов алгебраической теории распознавания является выяснение корректности совокупности алгоритмов {А}. Если корректности нет, то введенные операции позволяют пополнить совокупность {A}новыми алгоритмами, получающимися при использовании этих операций над алгоритмами из {А}. Очевидно, что операции сложения, умножения на скаляр, умножения позволяют строить многочлены из алгоритмов. Таким образом, вместо исходной совокупности {A}алгоритмов распознавания можно конструировать совокупность алгоритмов, являющихся полиномами над исходной совокупностью {А}, и уже в этой новой совокупности алгоритмов ставить вопрос о ее корректности. Так, например, доказано, что линейное пополнение (состоящее только из полиномов первой степени) совокупности алгоритмов распознавания определенного типа, основанных на ВО, корректно. Естественно, в рамках алгебраического подхода ставится вопрос не только о конструировании корректного алгоритма, но и о его поведении на произвольных изображениях. Другими словами, вопрос о том, насколько надежен корректный алгоритм, также составляет предмет исследования алгебраической теории распознавания. В настоящее время такие исследования являются одной из интенсивно развивающихся областей алгебраической теории распознавания.

3.7 Статистические подходы к распознаванию

Мы полагали, что любое изображение х на пространстве изображений Х представляет собой набор некоторых признаков: х = (x₁,…,x_n). Признаки эти являлись некоторыми характеристиками изображения, и мы считали, что их значения являются детерминированными в том смысле, что кодирующее устройство, преобразуя реальный объект в его изображение, всегда преобразует один и тот же объект в одно и то же изображение. Очевидно, что такое допущение может быть не всегда справедливым. Так, любое кодирующее устройство вносит свои собственные помехи, кроме того, изображение может быть сильно зашумленным и непосредственно по своей природе. Все это позволяет рассматривать набор признаков x₁,…,x_n как n-мерную случайную величину. Кроме этого, появление изображения того или иного класса может само по себе подчиняться вероятностным законам. Другими словами, можно говорить о вероятности появления изображения, относящегося к тому или иному классу. Очевидно, так как в нашем распоряжении имеется выборка конечной совокупности, то точное построение решающего правила невозможно. Существуют различные методы построения решающих правил:

· байесовское решающее правило;

· основанные на аппроксимации распределения вероятностей;

· решающие правила, зависящие от параметра.

3.8 Структурные подходы в распознавании

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

Подход, используемый для представления иерархической структурной информации, содержащейся в каждом объекте, т. е. для описания объекта при помощи более простых подобъектов, которые, в свою очередь, описываются еще более простыми подобъектами, и т. д., будем называть структурным подходом к распознаванию образов. Этот подход основан на аналогии между структурой объектов и синтаксисом языка. В рамках этого подхода считается, что объекты состоят из соединенных различными способами подобъектов так же, как фразы и предложения строятся путем соединения слов, а слова составляются из букв. Очевидно, что для того, чтобы такой подход был полезен, наипростейшие подобъекты, называемые примитивами, должны распознаваться гораздо проще, чем сами образы. Отметим, что распознавание примитивов должно осуществляться уже обычными, не структурными методами. Язык, который обеспечивает структурное описание объектов в терминах наборов примитивов и операций их объединения, называют языком описания образов. Правила композиции примитивов задаются обычно так называемой грамматикой описания образов. После того как каждый примитив объекта идентифицирован, процесс распознавания завершается выполнением синтаксического анализа, т. е. грамматическим разбором "предложения" из цепочки примитивов, описывающего объект. Эта процедура устанавливает, правильно оно или нет синтаксически относительно заданной грамматики образа, что позволяет отнести "предложение" к одному из классов.

Структурный подход к распознаванию позволяет описывать большую совокупность сложных объектов, используя небольшие наборы простых примитивов и - правил грамматики. Грамматическое правило - в нашем случае это правило подстановки - можно использовать произвольное число раз, и таким образом очень компактно выразить некоторые структурные особенности, вообще говоря, бесконечного множества предложений, составленных из цепочек примитивов. Очевидно, что практическая ценность такого подхода целиком зависит от способности распознавать примитивы и их взаимосвязи. Обычно взаимосвязь между примитивами определяется логическими или арифметическими операциями.

3.9 Задача автоматической классификации

Постановка задачи. Как и раньше, мы будем считать, что задано пространство изображений Х. Пусть даны некоторые изображения x₁,…,x_n, принадлежащие Х. В том случае, когда истинная классификация этих изображений была известна заранее, x₁,…,x_n называли обучающей последовательностью. 3адача распознавания в этом случае ставилась как задача отнесения некоторого изображения x к одному из классов (образов), представленных изображениями из обучающей последовательности. Теперь усложним задачу. Будем считать, что информация об истинной классификации изображений x₁,…,x_m отсутствует. В этом случае под задачей распознавания будем подразумевать задачу разбиения совокупности изображений x₁,…,x_m на классы (образы) по их "схожести". Эта задача называется также задачей таксономии, задачей обучения без учителя, задачей кластер анализа.

Решение этой задачи, т. е. построение классификации изображений x1,…,xm, будет формализовать интуитивное понятие "схожести" изображений. Это понятие может быть употребимо в различных аспектах, и соответственно возможны различные пути его формализации. Обычно в кластерном анализе рассматривают такое понимание "сходства", которое вытекает из геометрических представлений об изображениях как точках в пространстве изображений Х. Отсюда будет вытекать соответствующая формализация этого понятия. Конкретно мы будем считать, что для любых двух изображений х 1 и х 2 определено расстояние между ними с(х 1,х 2). Отметим, что выполнение аксиомы треугольника необязательно. Естественно считать два изображения тем более "схожими", чем ближе они находятся друг к другу в смысле расстояния с. Вводя с, мы тем самым неявно готовимся к формированию искомых классов. Очевидно, что такая интерпретация "схожести" будет эффективна только в том случае, когда введенное расстояние с соответствует содержательной стороне конкретной рассматриваемой задачи кластер-анализа. Выбор расстояния для каждой конкретной задачи кластер-анализа является неформальной процедурой и осуществляется обычно лицом, проектирующим систему, решающую задачу кластер-анализа. Определение "схожести" между изображениями с помощью расстояния между ними в пространстве изображений Х приводит к тому, что "схожими" будут те изображения, которые собраны в компактные группы. Каждая такая группа изображений и образует один класс (т. е. все эти изображения принадлежат одному образу). Это означает также, что рассматриваемая интерпретация "схожести" имеет смысл в предположении о том, что гипотеза компактности изображений имеет место.

Такой подход и определение "схожести" ориентированы на использование информации о классах, содержащейся во взаимном расположении объектов в пространстве изображений Х. В связи с этим алгоритм, реализующий решение задачи кластер-анализа, должен уметь выделять в пространстве области с большой плотностью объектов из последовательности x1,…, xm и игнорировать те области, где эта плотность мала.

Рассмотрим теперь множество S всевозможных различных разбиений последовательности изображений x₁,…,x_m на непересекающие группы, Очевидно, что максимальное число групп, на которое можно разбить последовательность изображений x₁,…,x_m, есть m, т. е. по одному изображению на группу. Минимальное же число групп в разбиении равно единице, т. е. все изображения собраны в одну группу. Очевидно, что S конечно. Если отождествлять группы изображений с классами, на которые необходимо разбить исходную последовательность изображений, то мы получаем, что S есть совокупность всех возможных решений задачи кластер-анализа для последовательности изображений x₁,…,x_n другими словами, S есть совокупность всевозможных классификаций изображений x₁,…,x_n. Однако большая часть таких решений, по-видимому, отнюдь не сводит в один класс "схожие" изображения. Очевидно, что среди всех этих решений мы должны выбрать то, которое в некотором смысле наилучшим образом осуществляет отнесение "схожих" изображений из последовательности x₁,…,x_n по классам. Это означает, что необходимо задать некоторый функционал J, сопоставляющий каждому решению задачи кластер-анализа некоторую числовую оценку, а затем искать такое решение, на котором он достигает экстремума. Выбор такого функционала также является неформальной процедурой, которая осуществляется обычно проектировщиком системы, решающей задачу кластер-анализа на основе априорных данных и собственного опыта. Таким образом, алгоритм, реализующий решение задачи кластер-анализа, можно рассматривать как алгоритм выбора из конечного множества решений S экстремального (в смысле функционала J) решения. Другими словами, под задачей кластер-анализа мы будем подразумевать задачу отыскания экстремального (в смысле функционала J) разбиения заданной последовательности изображений x1,…,xm.

Стоит отметить, что обычно в качестве функционала J берут среднее расстояние между изображениями, относимыми в один и тот же класс, и суммируют его по всем классам. При этом отыскивают такое решение, при котором функционал J минимален. Иногда некоторая априорная информация позволяет сделать вывод о необходимости построения иерархического решения задачи кластер анализа. Отметим также, что поиск наилучшего решения задачи кластер анализа прямым перебором всех решений невозможен, так как

S = 2m - 1,

а m порядка 100. В настоящее время существуют пакеты прикладных программ, реализующие большое число алгоритмов решения задачи кластер анализа. Выбор того или иного алгоритма для решения конкретной задачи является неформальной проблемой и определяется: соответствием реальной группировки объектов критериям качества разбиения объектов по классам, заложенным в алгоритме. В любом случае качество работы алгоритма оценивается экспертом-специалистом.

Метод разделяющей функции. Будем искать L функций D₁(х),…,D_l (х), таких, что для всех x из класса K_i, i = 1,..., L, значение i-й функции D_i на х, т. е. D_i(х), будет больше, чем значение на x всех остальных функций. Такие функции D_i (х) называются разделяющими (дискриминантными). Не задаваясь априори никакими дополнительными свойствами функций D_i, отыскать их будет затруднительно. Поэтому обычно берут не произвольные разделяющие функции, а обладающие некоторыми простыми свойствами. Рассмотрим линейные разделяющие функции D_i(х), т. е. функции вида:

D_i(х) = б x + бx+ …+бx+ б,

где x = (x₁,x₂,…,x _n); б, б, …,б, б - константы.

Если искать разделяющие функции только среди линейных, то граница раздела между классами в пространстве Х окажется плоскостью в n-мерном пространстве. Будем считать, что L = 2. Это предположение, не является стеснительным.

Если предполагать, что такая плоскость существует, то в соответствии с теоремой Новикова за конечное число шагов можно добиться построения разделяющей классы плоскости.

Если же предполагать существование плоскости, разделяющей два класса, то линейная разделяющая функция должна строится так, чтобы число неправильных распознаваний элементов обучающей последовательности было минимально. В том случае, когда L > 2, можно считать, что линейная разделяющая функция строится сначала для отделения изображений первого класса (образа) от всех остальных. Далее процедура построения разделяющей функции повторяется на множестве оставшихся изображений с тем, чтобы выделять второй класс, и т. п. Поскольку аналогичное рассуждение можно проводить для любой задачи распознавания, это означает, что число классов (образов), на которые классифицируются (распознаются) изображения, всегда можно считать равным 2.

В качестве разделяющих функций можно брать и более сложные функции, например, берутся так называемые кусочно-линейные, квадратичные разделяющие функции и т.п.

Отметим, что при построении плоскости, разделяющей два класса, можно ставить вопрос о построении наилучшей в некотором смысле разделяющей плоскости. Такая плоскость будет называться оптимальной.

Метод комитетов решения задачи распознавания. По-прежнему будем рассматривать задачу распознавания в детерминистской постановке, причем будем иметь в виду задачу обучения с учителем. Будем считать, что число классов (образов) равно двум.

Таким образом, обучающая последовательность состоит из двух последовательностей изображений x1, …, x r из класса К 1 и xr+1,…, x r из класса К 2.

Будем считать, что все изображения различны. Откажемся теперь от предположения о линейной разделимости последовательностей x1, …, x r и xr+1,…, x r,т. е. пусть не существует плоскости безошибочно разделяющей объекты обучающей последовательности. Иначе говоря, какая бы плоскость не проводилась, часть объектов из одного класса будет находиться по одну сторону с объектами из второго класса.

Определение. Комитетом совокупности объектов из двух классов называется множество плоскостей в пространстве изображений, обладающих тем свойством, что каждый объект правильно классифицируется более чем половиной из плоскости. Можно доказать, что при некоторых условиях комитет обязательно существует.

Содержательно комитет означает следующее. В том случае, когда обучающая последовательность, вообще говоря, не разделяется плоскостью, образуется набор плоскостей, называемых комитетом и обладающих следующим свойством.

Число ошибочных отнесений каждого изображения обучающей последовательности при разделении пространства признаков плоскостями из комитета меньше половины числа плоскостей. Таким образом, комитет как бы имеет коллективное мнение о том, к какому классу принадлежит объект, причем "большинство" комитета имеет мнение, отвечающее истинной классификации изображения. Комитет строится по обучающей последовательности объектов. После построения комитета объекты, попадающие на распознавание, относятся в тот класс, которому их относит большая часть плоскостей. Естественно, что основной проблемой данного метода является поиск комитета совокупности объектов. В настоящее время существуют пакеты прикладных программ, в которых реализован метод комитетов. Этот метод является в некотором смысле обобщением идеи разделения классов в пространстве признаков наиболее простой поверхностью.

Метод потенциальных функций. По-прежнему будем рассматривать задачу распознавания в детерминистской постановке. Будем считать, что число классов L равно двум. Обозначим их через К ₁ и К ₂. Кроме того, пусть имеется обучающаяся последовательность x₁, …, x _r из класса К ₁ и x_r+1,…, x _r из класса К ₂. Будем считать, что каждая точка Х (т.е. вектор х из Х) из обучающей последовательности создает вокруг себя некоторое поле.

Например, можно считать, что в каждой точке х обучающей последовательности находится единичный заряд. Тогда по аналогии с физикой поле, создаваемое зарядами, можно описать потенциалом, создаваемым системой зарядов во всем пространстве. Отметим, что такая аналогия с физикой сразу требует того, чтобы на пространстве Х векторов х было введено расстояние между векторами. Функцию, определяющую поле, будем называть потенциальной. Выбор потенциальной функции определяется неформально в зависимости от специфики задачи. Однако, как бы мы не выбирали эту функцию, естественно требовать от нее выполнения ряда свойств, с тем чтобы потенциал, создаваемый обучающей последовательностью, был неотрицателен, монотонно убывал по мере увеличения расстояния от точки х, в которой расположен заряд, создающий потенциал, и т. д.

Рассмотрим теперь потенциал, создаваемый в пространстве признаков Х точками из классов К ₁ и К ₂, полагая суммарный потенциал суммой потенциалов от каждого заряда. Получаем две функции К^*(х) и К^**(х), где К^* (х) - потенциал от точек класса К ₁, а К^**(х) от точек класса К ₂. Будем теперь предъявляемую к распознаванию произвольную точку х ₀ из Х относить к классу К ₁, если К^* (х ₀) > К^** (х ₀). Если К^* (х ₀) < К^** (х ₀), то отнесем х ₀ к классу К ₂. Если классы К ₁ и К ₂ удовлетворяют гипотезе компактности, то можно ожидать, что К^* (х) и К^**(х) будут иметь на изображениях из своего класса большие значения, чем на изображениях из чужого класса. Таким образом, в силу симметрии потенциальной функции, по существу, предполагается "простота" границ между классами. Очевидно, что граница между классами К ₁ и К ₂ определяется условием К^*(х) - К^**(х) =0. Если определить функцию:

Ф(х) = К^*(х) - К^**(х),

то очевидно, что Ф (х) есть разделяющая (дискриминантная) функция. Вот ее и надо отыскивать по обучающей последовательности.

Для отыскания разделяющей функции существует так называемая общая рекуррентная процедура. Эта процедура выстраивает разделяющую функцию на (п + 1)-м шаге исходя из значения разделяющей функции, полученной к n-му шагу, причем используется информация об истинной принадлежности классам изображений из обучающей последовательности. Будем считать, что обучающая последовательность образована случайно появившимися изображениями, другими словами, обучающая последовательность есть выборка конечного объема из пространства изображений Х. Тогда можно считать, что последовательность разделяющих функций {Фn(х)}, выстраиваемая общей рекуррентной процедурой к n-му шагу, есть последовательность случайных функций. Поэтому, говоря о сходимости последовательности функций {Фn(х)} к истинной разделяющей функции Ф(х), будем иметь в виду сходимость в вероятностном смысле, т. е. либо по вероятности, либо с вероятностью 1, либо в среднем.

Можно доказать, что общая рекуррентная процедура с вероятностью 1 за конечное число шагов строит разделяющую функцию.

3.10 Алгоритмы распознавания, основанные на ВО (АВО)

Будем рассматривать задачу распознавания в детерминистской постановке, причем для случая, когда проводится обучение с учителем.

Пусть задана обучающая последовательность изображений x₁, …, x _r, x_r+1,…, x_r, x_r+1,…, x_r принадлежащих l непересекающимся классам К ₁, К ₂, …, К_l, причем первые r₁ изображений - из класса К ₁, следующие r₂ - r₁ изображений - из К ₂ и т.д.

Пусть пространство изображений Х - n-мерно. Это означает, что любое изображение х есть набор п характеристик (признаков), описывающих объект. Обозначим признаки, характеризующие изображение xj так:

xj = (бj, бj,…, бj).

Будем говорить, что обучающая последовательность изображений x1, …, xr, xr+1,…, xr,…, xr+1,…, xr образует таблицу обучения Tn, r.

Каждой строке этой таблицы отвечает одно из изображений обучающей последовательности.

Поскольку все изображения на обучающей последовательности относятся к тому или иному классу, можно считать, что таблица Tn, r разбита на l групп непересекающихся строк.

Сформулируем основную задачу. Пусть задана таблица обучения T_n,r и некоторое изображение х на Х. Требуется указать класс K_j, j = 1, 2,…, l, к которому принадлежит изображение х.

Перейдем теперь к описанию класса алгоритмов, решающих основную задачу. Будем называть этот класс классом алгоритмов, основанных на ВО, а каждый конкретный алгоритм - алгоритмом ВО. Класс алгоритмов, основанных на ВО, задается посредством описания шести элементов, его определяющих:

1. Система опорных множеств,

2. Функция близости,

3. ВО по строкам фиксированного опорного множества,

4. ВО для класса по опорному множеству,

5. Оценка для класса по системе опорных множеств,

6. Решающее правило. Любой алгоритм распознавания, задание которого складывается из шести элементов, и будет алгоритмом ВО, представляющих собой совокупность всевозможных алгоритмов распознавания, задаваемых рассматриваемыми шестью элементами.

Задание алгоритма ВО.

· Система опорных множеств. Под опорным множеством будем подразумевать некоторый набор номеров столбцов таблицы обучения T _{n, r.} Под системой опорных множеств будем подразумевать совокупность опорных множеств, задаваемых из содержательных соображений при определении алгоритма, основанного на ВО. Например, система может состоять из одного набора, включающего все столбцы, т. е. столбцы с номерами 1, 2,..., n.

· Функция близости. Пусть x_i и x_p - некоторые изображения. Пусть задана функция r, которая описывает степень похожести изображений x_i и x_p на основе анализа только по одному из опорных множеств. Ее и будем называть функцией близости. Пример 1. r = 1, если x_i и x_p совпадают на столбцах, входящих в некоторое опорное множество, и r = 0 - в противном случае. Строки считаются похожими, если эти части совпадают.

Очевидно, что для каждого опорного множества можно вычислить функцию близости. Выбор той или иной функции близости определяется содержательными соображениями.

· ВО по строкам фиксированного опорного множества.

Рассматриваемый пункт (элемент) класса алгоритмов распознавания, основанных на ВО, означает учет степени важности, представительности изображений, входящих в обучающую последовательность. Другими словами, пусть априорно задаются числовые коэффициенты г₁, …, г_r, характеризующие важность изображений x₁,…, x_r.

Тогда определяем оценку по строкам фиксированного опорного множества как некоторую заданную функцию от функции близости и коэффициентов г₁,…, г_r.

Например, = г_i r, если функция близости вычисляется между изображениями x_i и x_p по некоторому опорному множеству. Таким образом, - это близость по опорному множеству с учетом важности.

· ВО для класса по опорному множеству. Оценка Г* для класса по опорному множеству означает вычисление близости между всеми изображениями из одного класса и некоторым изображением, относительно которого эта близость вычисляется. Эта близость вычисляется с учетом важности изображений по фиксированному опорному множеству. Например, если опорное множество представляет собой набор столбцов i₁,…,i_k, а к классу K_m относятся изображения x_r+1, …,x_r, то оценку Г* для класса K_m по опорному множеству i₁,…, i_k для произвольного изображения x_p можно вычислить так:

Г* = г _r+1 r(x_r+1, x_p)+…+г_rr(x_r, x_p).

· Оценка для класса K_m по системе опорных множеств.

Оценки Г_m для класса K_m по системе опорных множеств означает близость произвольного изображения x_p к изображениям из класса K_m по всем опорным множествам из системы опорных множеств. Например, в качестве оценки Г_т можно взять сумму всех оценок Г*, полученных для каждого опорного множества.

Е. Решающее правило. Пусть по системе опорных множеств к изображению xp вычислены оценки Г 1,......, Гl. Под решающим правилом будем подразумевать правило, которое по оценкам Г 1,......, Гl выносит суждение о принадлежности xp классам K1, …, Кl. Например, xp относится к классу Kj, если Гj - наибольшая оценка из Г 1,..., Гl.На этом описание алгоритмов распознавания, основанных на ВО, завершается.

Таким образом, можно сказать, что, выбирая конкретную систему опорных множеств, определяя функцию близости, задавая правила ВО по строкам фиксированного опорного множества, для класса по опорному множеству и по системе опорных множеств, а также назначая решающее правило, мы получаем некоторый конкретный алгоритм ВО. Класс же алгоритмов распознавания, основанных на ВО, включает в себя всевозможные алгоритмы, которые могут быть построены из рассмотренных шести элементов.

Качество работы алгоритма распознавания, основанного на ВО. Пусть для таблицы обучения Tn,r задан алгоритм распознавания, основанный на ВО. Будем считать, что помимо обучающей последовательности изображений, имеется еще одна последовательность изображений y₁,…, y_m, которую будем называть контрольной. Для каждого из изображений контрольной последовательности известен класс (образ), к которому оно принадлежит. Качество работы алгоритма распознавания будет оцениваться по его работе на контрольной последовательности. В частности, контрольная последовательность может совпадать с обучающей последовательностью. В таком случае говорят о скользящем контроле. Пусть алгоритм распознавания из предъявленных m изображений m₁ распознал неправильно, а m₂ - алгоритм отказался распознавать. Рассмотрим в качестве функционала ц, описывающего качество работы алгоритма распознавания следующую величину:

ц = (m₁ - m₂)/m.

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

Поиск экстремального алгоритма для числа объектов обучения порядка 100 и при числе характеристик, описывающих объект порядка 100 возможен только на современных высокопроизводительных ЭВМ. При этом по заданной таблице обучения и контрольной последовательности находится экстремальный по качеству алгоритм. Очевидно, что отыскание экстремума в многомерной области практически невозможно осуществить прямым перебором.

4. Постановка задачи

Предлагается формализованный подход, позволяющий реализовать процесс принятия решения о целесообразности выдачи кредита физическому лицу, с использованием методов распознавания образов. Задача оценки финансового состояния сводится к классификации физических лиц на основе достаточно слабых требований к исходным данным. Клиенты, отнесенные к одному классу образов, будут обладать общими свойствами, т.е. находиться примерно на одном уровне финансовой устойчивости, кредитоспособности, являться равноправными.

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

Содержательная постановка задачи заключается в следующем. Определяются классы состояний, каждый из которых содержит клиентов с одинаковой оценкой банкротства. Каждый клиент описывается набором признаков, характеризующих его. Требуется отнести распознаваемого клиента к одному из классов состояний.

На языке математической теории распознавания образов эта задача определяется следующим образом.

Формальная постановка задачи. Входной информацией является множество векторов:

,

Здесь - число векторов; - число признаков; -й вектор (- е наблюдение).

Задача обучения с учителем. Пусть неизвестны классов объектов , которые в заданном множестве (обучающее множество) представлены конечными подмножествами:

,

.

Необходимо построить правило, с помощью которого можно с достаточной степенью надежности классифицировать объекты, принадлежащие классам , но не содержащиеся в обучающем множестве . Критерием качества искомого решающего правила служит процент правильно распознанных с его помощью объектов с априори известной классификацией, но не участвовавших в обучении. Совокупность таких объектов называется проверочной или контрольной выборкой. Формирование проверочной выборки из множества всех представленных на обучение объектов представляет собой также весьма важную задачу.

Распознавание объекта основывается на заранее проведенном обучении - этапе, который предшествует этапу распознавания. Целью обучения является подбор таких порогов, при которых получается минимальное число ошибок на обучающем наборе объектов с известной принадлежностью классам (обучение). Следующим этапом после обучения является этап контроля обучения. Он заключается в контроле обучения, вычислении ошибки распознавания объектов, которые принадлежат известным классам (экзамен). И последний этап - распознавание неизвестного объекта.

В настоящее время разработано множество алгоритмов распознавания объектов и накоплен большой опыт решения прикладных задач в различных областях науки и техники. Наиболее развитой и известной моделью распознавания является модель алгоритмов вычисления оценок. Многопараметрические алгоритмы этой модели и были положены в основу системы поддержки принятия решений по определению класса и размеров кредита. Класс алгоритмов, основанных на вычислении оценок, задается посредством описания шести элементов его определяющих: система опорных множеств, функция близости, вычисление оценок по строкам фиксированного опорного множества, вычисление оценки для класса по опорному множеству, оценка для класса по системе опорных множеств, решающее правило.

Любой алгоритм распознавания, задание которого складывается из шести элементов, и будет алгоритмом вычисления оценок, представляющих собой совокупность всевозможных алгоритмов распознавания, которые могут быть заданы рассматриваемыми шестью элементами.

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

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

На основании предложенной модели мной разработана экспериментальная вычислительная система распознавания кредитоспособности физических лиц по его признакам "Информационная система решения задачи кредитования", на вход которой подаются описания клиентов, представленные векторами-описаниями и разбитые экспертом по кредитам на классы.

Предложенная система позволяет определять класс финансового состояния распознаваемого клиента. Использование такого подхода позволяет получить более точный и объективный результат, что помогает снизить риск убытков и получить прибыль, а также аргументировать принимаемые решения при работе с кредиторами и партнерами.

Литература

1. Churchill G.A., Nevin J.R., Watson R.R. //The role of credit scoring in the loan decision. Credit World. March/1977.

2. Myers J.H., Forgy E.W. The development of numerical credit evaluation systems//Journal of American Statistical Association. September/1963.

2. Нортон М. Нервный бизнес//Банковские технологии. 1995. № 3. С. 73.

3. В. Степанова, А. Заяца "Анализ состояния банка" (Банковские технологии. 1996. № 8. С. 58).

Размещено на Allbest.ru