AntipovSN and MihhaCF

UPD Часть вторая здесь

Часть первая, в которой Граф еще не стал Атосом, не встретил Миледи и все у него хорошо

Вступление от авторов:

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

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

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

А теперь к делу.

Цель данной статьи: не более, чем за 30 минут, ввести читателя в проблематику исследования, определить уровень рассмотрения проблемы, описать основную концепцию исследования и познакомить с базовыми терминами.

Термины и определения:

• Скоринг – система бальной оценки объекта, основанная на численных статистических методах.
• Граф – способ моделирования связей объектов. Представьте, что Вы с друзьями играете в покер и хотите смоделировать, кто кому сейчас должен. Например, «Д’Артаньян должен Атосу 10 луидоров»

Полный граф может выглядеть следующим образом:

Арамис всегда был хитрож… себе на уме, ему должен даже Атос. Портос, пока не встретил госпожу Кокнар, перевязь не мог себе нормальную купить и умудрился задолжать нищеброду Д’артаньяну, хотя, честно говоря, они всю дорогу что-то мутили вместе…

Графы состоят из узлов и ребер. Узел может быть напрямую соединен с несколькими другими узлами. Эти узлы называются соседями.

• Взвешенный граф – это граф, у которого каждому ребру присвоен вес. Граф без весов называется невзвешенным.
• Ориентированный или направленный граф – это граф, ребрам которого присвоено направление
• Ориентированный ациклический граф – это случай направленного графа, в котором отсутствуют направленные циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине.
• Data Mining — собирательное название, используемое для обозначения совокупности методов обнаружения в данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности
• Алгоритм поиска в ширину (BFS, Breadth-First Search) – отвечает на два вопроса: существует ли путь от узла А к узлу В и как выглядит кратчайший путь от узла А к узлу В. Обход производится по уровням: сначала проверяются узлы первого уровня, их дочерние узлы добавляются в очередь, и так до конца
• Алгоритм поиска в глубину (DFS, Depth-first search) — Стратегия поиска в глубину, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин
• Алгоритм Дейкстры — Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для ациклических графов с взвешенными ребрами, без отрицательного веса.

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

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

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

Эти два инструмента созданы друг для друга, как Д’артаньян и Констанция (надо только за Констанцией нормально следить и не пускать всяких Миледей).

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

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

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

Банковская сфера выбрана не случайно — банки обладают обширными источниками информации и занимаются скорингом с применением автоматизации, все более и более активно.

Еще чуть ближе к делу. Помните, как Д’артаньян дрался с господином де Жюссаком? Шажок туда, шажок сюда, потом бегали вокруг да около дерева и только потоооом колоть друг друга начали. Мы так тянуть не будем, но и колоть сразу тоже смысла нет – будет непонятно.

Итак! В боевой системе скоринговый бал будет рассчитываться на основании двух групп показателей:

• Показатели, полученные напрямую от заемщика и гос. органов:
  
  • налоговая отчетность;
  • паспортные данные владельцев, ген. директора, гл. бухгалтера;
  • выписки ЕГРЮЛ, ЕГРИП;
  • правоустанавливающие документы;
  • данные по задолженностям;
  • данные по судебным делам;
  • и пр.
• Показатели, полученные с помощью анализа графов и data mining:
  
  • взаимодействие с гос. органами – подряд/субподряд/поставка;
  • взаимодействие с компаниями из топ-100;
  • наличие в окружении заемщика компаний банкротов, должников, компаний с низким скоринговым балом;
  • участие в благотворительных организациях
  • и пр.

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

К примеру:

• Заемщик, который, в данном случае, является поставщиком, связан контрактами с Заказчиком на 1 млн руб. Годовой оборот заемщика – 5 млн. Годовой оборот Заказчика 100 млн руб. Наглядно видно, что Поставщик зависит от Заказчика сильнее, чем Заказчик от поставщика. Таким образом, для Поставщика связь будет равна 5 (к примеру), а для Заказчика 1.
  Понятно, что пример чисто умозрительный и в реальной жизни мы будем делать более детальный анализ. Это дело следующих статей и сейчас нет смысла забираться так глубоко.

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

В нашей тестовой системе мы будем использовать всю ту же тему с мушкетерами и их связями. Модель будет максимально приближена к боевой и в достаточной мере демонстрировать нашу идею. К чему мы в конечном итоге придем, как будет выглядеть модель? Не торопитесь говорить: «Каналья!» или «Мне не нужны академии. Любой гасконец с детства академик!». Все будет не так примитивно, как кажется.

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

Особенности представленного графа:

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

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