Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
AntipovSN and MihhaCF
Часть первая, в которой Граф еще не стал Атосом, не встретил Миледи и все у него хорошо
Вступление от авторов:
Добрый день! Сегодня мы начинаем цикл статей, посвященных скорингу и использованию в оном теории графов (Т.Г.). Надеюсь, нам хватит запала, сил и терпения, т.к. тема достаточно объемная и, на наш взгляд, интересная.
Несмотря на шуточное название, мы постараемся затронуть отнюдь не шуточные темы, которые уже сейчас влияют на жизнь многих из нас, а в ближайшем будущем могут коснуться всех, без исключения.
Все шуточные аллегории, вставки и прочее призваны немного разгрузить повествование и не позволить ему свалиться в нудную лекцию. Всем, кому не зайдет наш юмор, заранее приносим извинения
А теперь к делу.
Цель данной статьи: не более, чем за 30 минут, ввести читателя в проблематику исследования, определить уровень рассмотрения проблемы, описать основную концепцию исследования и познакомить с базовыми терминами.
Термины и определения:
- Скоринг – система бальной оценки объекта, основанная на численных статистических методах.
- Граф – способ моделирования связей объектов. Представьте, что Вы с друзьями играете в покер и хотите смоделировать, кто кому сейчас должен. Например, «Д’Артаньян должен Атосу 10 луидоров»
Полный граф может выглядеть следующим образом:
Арамис всегда был хитрож… себе на уме, ему должен даже Атос. Портос, пока не встретил госпожу Кокнар, перевязь не мог себе нормальную купить и умудрился задолжать нищеброду Д’артаньяну, хотя, честно говоря, они всю дорогу что-то мутили вместе…
Графы состоят из узлов и ребер. Узел может быть напрямую соединен с несколькими другими узлами. Эти узлы называются соседями.
- Взвешенный граф – это граф, у которого каждому ребру присвоен вес. Граф без весов называется невзвешенным.
- Ориентированный или направленный граф – это граф, ребрам которого присвоено направление
- Ориентированный ациклический граф – это случай направленного графа, в котором отсутствуют направленные циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине.
- Data Mining — собирательное название, используемое для обозначения совокупности методов обнаружения в данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности
- Алгоритм поиска в ширину (BFS, Breadth-First Search) – отвечает на два вопроса: существует ли путь от узла А к узлу В и как выглядит кратчайший путь от узла А к узлу В. Обход производится по уровням: сначала проверяются узлы первого уровня, их дочерние узлы добавляются в очередь, и так до конца
- Алгоритм поиска в глубину (DFS, Depth-first search) — Стратегия поиска в глубину, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин
- Алгоритм Дейкстры — Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для ациклических графов с взвешенными ребрами, без отрицательного веса.
Ну, вроде, с самыми основными понятиями разобрались, можно перейти ближе к делу.
Скоринг может быть использован для оценки практически чего угодно, что можно выразить в статистических показателях. Это и оценка кредитоспособности физического / юридического лица (скоринг заявителя), и оценка вероятности мошенничества (скоринг от мошенничества), и оценка страхователя (страховой скоринг), оценка поставщика/заказчика (скоринг контрагента), оценка поведения потребителей (поведенческий скоринг), социальная оценка («Китайский» скоринг) и пр.
Теория графов, в свою очередь, также универсальный инструмент, который может быть использован в любой сфере деятельности, в которой необходимо обрабатывать большие, многоуровневые объемы данных.
Эти два инструмента созданы друг для друга, как Д’артаньян и Констанция (надо только за Констанцией нормально следить и не пускать всяких Миледей).
О важности и злободневности скоринга ничего писать не будем, ибо достаточно приглядеться вокруг и сразу станет понятно, что мы уже давно явно или не явно подвергаемся скорингу, дальше будет только веселее.
В цикле статей мы постараемся наглядно продемонстрировать, как работает скоринг с использованием теории графов в банковской сфере. То есть, мы будем определять кредитоспособность юридических лиц (может даже и физиков зацепим), исходя из предоставленных ими данных и связей, которые они имеют с другими организациями — так называемый «скоринг заемщика».
Как следует из официального определения, скоринг заемщика призван упразднить субъективизм принятия решения кредитного инспектора, снизить уровень внутреннего мошенничества и увеличить скорость принятия решения по кредиту. Посмотрим так ли это, развернем, так сказать, конфету и посмотрим из чего она сделана.
Банковская сфера выбрана не случайно — банки обладают обширными источниками информации и занимаются скорингом с применением автоматизации, все более и более активно.
Еще чуть ближе к делу. Помните, как Д’артаньян дрался с господином де Жюссаком? Шажок туда, шажок сюда, потом бегали вокруг да около дерева и только потоооом колоть друг друга начали. Мы так тянуть не будем, но и колоть сразу тоже смысла нет – будет непонятно.
Итак! В боевой системе скоринговый бал будет рассчитываться на основании двух групп показателей:
- Показатели, полученные напрямую от заемщика и гос. органов:
- налоговая отчетность;
- паспортные данные владельцев, ген. директора, гл. бухгалтера;
- выписки ЕГРЮЛ, ЕГРИП;
- правоустанавливающие документы;
- данные по задолженностям;
- данные по судебным делам;
- и пр.
- Показатели, полученные с помощью анализа графов и data mining:
- взаимодействие с гос. органами – подряд/субподряд/поставка;
- взаимодействие с компаниями из топ-100;
- наличие в окружении заемщика компаний банкротов, должников, компаний с низким скоринговым балом;
- участие в благотворительных организациях
- и пр.
На основании перечисленных показателей выстроится модель: вершинами графа будут все организации, с которыми так или иначе взаимодействовал заемщик, ребра графа будут иметь вес. Вес связи будет задаваться в пределах от 1 до 5, характеризуя степень влияния узлов друг на друга.
К примеру:
- Заемщик, который, в данном случае, является поставщиком, связан контрактами с Заказчиком на 1 млн руб. Годовой оборот заемщика – 5 млн. Годовой оборот Заказчика 100 млн руб. Наглядно видно, что Поставщик зависит от Заказчика сильнее, чем Заказчик от поставщика. Таким образом, для Поставщика связь будет равна 5 (к примеру), а для Заказчика 1.
Понятно, что пример чисто умозрительный и в реальной жизни мы будем делать более детальный анализ. Это дело следующих статей и сейчас нет смысла забираться так глубоко.
Степень взаимодействия и сами взаимодействия будут определяться, в том числе, с помощью алгоритмов поиска на графах.
В нашей тестовой системе мы будем использовать всю ту же тему с мушкетерами и их связями. Модель будет максимально приближена к боевой и в достаточной мере демонстрировать нашу идею. К чему мы в конечном итоге придем, как будет выглядеть модель? Не торопитесь говорить: «Каналья!» или «Мне не нужны академии. Любой гасконец с детства академик!». Все будет не так примитивно, как кажется.
Краткое описание: наши мушкетеры решили создать непубличное акционерное общество (НПАО), которое будет заниматься поставками ювелирных изделий и предоставлять охранные услуги, для начала деятельности им нужен кредит. Кредитной организацией выступает ПАО «Король», который и заказал оценку НПАО «Один за всех»
Особенности представленного графа:
- Граф является неориентированным (двунаправленным) и взвешенным.
- Каждое ребро имеет вес – степень взаимодействия. На рисунке мы не стали усложнять и делать свою величину связи в каждом направлении от узла к узлу. Ограничились единой агрегированной оценкой связи. Но в алгоритме расчета это будет учтено.
- Красным отмечены организации, которые противостоят нашей и всячески ей мешают. В реальной жизни это будут конкуренты, компании банкроты, злостные неплательщики, компании, в отношении которых идут судебные разбирательства и т.д.
- Наверно, уже можно догадаться, что потребуется оценка связей по уровням и направлениям, то есть, нужно будет учитывать не только уровень связи, но и направление. Потребуется учитывать взаимное влияние узлов и еще много чего.
У нас впереди много работы. Ну, а в рамках данной статьи, мы закончили. Заявленные цели статьи, как нам кажется, достигнуты. Надеемся нам удалось Вас заинтересовать, и Вы дочитали до конца.
