AntipovSN et MihhaCF
UPD deuxième partie ici
UPD troisième partie ici
La première partie, dans laquelle le comte n'est pas encore devenu Athos, n'a pas rencontré Milady et tout va bien avec lui
Introduction des auteurs:
Bon après-midi Aujourd'hui, nous commençons une série d'articles consacrés à la notation et à l'utilisation de la théorie des graphes (T.G.). J'espère que nous avons suffisamment de fusible, de force et de patience, car le sujet est assez volumineux et, à notre avis, intéressant.
Malgré le nom de la bande dessinée, nous essaierons de toucher loin de sujets comiques qui affectent déjà la vie de beaucoup d'entre nous, et dans un proche avenir, ils peuvent toucher tout le monde, sans exception.
Toutes les allégories comiques, les encarts, etc. sont conçus pour soulager légèrement le récit et ne pas le laisser tomber dans une conférence fastidieuse. Nous nous excusons auprès de tous ceux qui ne rentrent pas dans notre humour
Maintenant au point.
Le but de cet article: en moins de 30 minutes, initiez le lecteur au problème de recherche, déterminez le niveau de considération du problème, décrivez le concept de base de l'étude et introduisez les termes de base.
Termes et définitions:
- La notation est un système d'évaluation ponctuelle d'un objet basé sur des méthodes statistiques numériques.
- Un graphe est un moyen de modéliser les relations des objets. Imaginez que vous jouez au poker avec vos amis et que vous souhaitez simuler qui doit à qui maintenant. Par exemple, "D'Artagnan doit Athos 10 louis"
Un graphique complet pourrait ressembler à ceci:
Aramis était toujours rusé ... dans son esprit, même Athos lui devait. Porthos, jusqu'à ce qu'il rencontre Mme Koknar, ne pouvait pas se permettre d'acheter une vinaigrette et a réussi à devoir un mendiant à D'artanyan, bien que, franchement, ils aient mutilé quelque chose ensemble ...
Les graphiques sont constitués de nœuds et d'arêtes. Un nœud peut être directement connecté à plusieurs autres nœuds. Ces nœuds sont appelés voisins.
- Un graphique pondéré est un graphique avec un poids attribué à chaque bord. Un graphique sans pondération est appelé non pondéré.
- Un graphique dirigé ou dirigé est un graphique dont les bords sont affectés d'une direction
- Un graphe acyclique dirigé est un cas de graphe dirigé dans lequel il n'y a pas de cycles dirigés, c'est-à-dire des chemins commençant et se terminant au même sommet.
- L'exploration de données est un nom collectif utilisé pour désigner un ensemble de méthodes pour détecter des interprétations auparavant inconnues, non triviales, pratiquement utiles et accessibles des connaissances nécessaires pour prendre des décisions dans divers domaines de l'activité humaine
- L'algorithme de recherche en largeur (BFS, Breadth-First Search) répond à deux questions: le chemin du nœud A au nœud B existe-t-il et quel est le chemin le plus court du nœud A au nœud B. Le contournement est effectué par niveaux: les nœuds de premier niveau sont vérifiés, leurs nœuds enfants sont ajoutés à la file d'attente, et ainsi de suite jusqu'à la fin
- Algorithme de recherche en profondeur d'abord - Stratégie de recherche en profondeur d'abord - La stratégie de recherche en profondeur d'abord consiste à approfondir le graphique autant que possible. L'algorithme de recherche est décrit récursivement: on trie toutes les arêtes provenant du sommet en question. Si l'arête mène à un sommet qui n'a pas été pris en compte précédemment, nous exécutons l'algorithme à partir de ce sommet non examiné, puis nous revenons et continuons de trier les arêtes. Le retour se produit s'il n'y a pas d'arêtes dans le sommet considéré qui conduisent au sommet non examiné. Si, après la fin de l'algorithme, tous les sommets n'ont pas été pris en compte, il est nécessaire d'exécuter l'algorithme à partir de l'un des sommets non examinés
- Algorithme de Dijkstra - Trouve les chemins les plus courts d'un des sommets du graphique à tous les autres. L'algorithme ne fonctionne que pour les graphiques acycliques avec des bords pondérés, sans poids négatif.
Eh bien, en quelque sorte, avec les concepts les plus élémentaires compris, vous pouvez vous rapprocher du point.
La notation peut être utilisée pour évaluer presque n'importe quoi, qui peut être exprimé en indicateurs statistiques. Il s'agit d'une évaluation de la solvabilité d'une personne physique / morale (notation du demandeur), d'une évaluation de la probabilité de fraude (notation de fraude) et d'une évaluation du preneur d'assurance (notation d'assurance), d'une évaluation du fournisseur / client (notation de la contrepartie), d'une évaluation du comportement du consommateur (notation comportementale), d'une évaluation sociale (Notation "chinoise"), etc.
La théorie des graphes, à son tour, est également un outil universel qui peut être utilisé dans n'importe quel domaine d'activité dans lequel il est nécessaire de traiter de grands volumes de données à plusieurs niveaux.
Ces deux outils sont créés l'un pour l'autre, comme D'artanyan et Constance (il vous suffit de suivre Constance normalement et de ne laisser passer aucune Miladya ).
Nous n'écrirons rien sur l'importance et l'actualité de la notation, car il suffit de regarder de plus près et il deviendra immédiatement clair que nous avons explicitement ou non explicitement marqué depuis longtemps, ce ne sera que plus amusant.
Dans la série d'articles, nous allons essayer de montrer clairement comment fonctionne la notation en utilisant la théorie des graphes dans le secteur bancaire. Autrement dit, nous déterminerons la solvabilité des entités juridiques (peut-être même que nous accrocherons les physiciens) en fonction des données qu'elles fournissent et des relations qu'elles entretiennent avec d'autres organisations - ce que l'on appelle le «score des emprunteurs» .
Comme il ressort de la définition officielle, la notation de l'emprunteur vise à éliminer la subjectivité de la décision de l'inspecteur du crédit, à réduire le niveau de fraude interne et à accélérer la prise de décision sur le prêt. Voyons si c'est le cas, élargissons les bonbons, pour ainsi dire, et voyons de quoi ils sont faits.
Le secteur bancaire n'a pas été choisi par hasard - les banques disposent de nombreuses sources d'informations et obtiennent de plus en plus activement des scores grâce à l'automatisation.
Un peu plus près du point. Rappelez-vous comment D'artagnan a combattu avec M. de Jussac? Un pas là-bas, un pas ici, puis nous avons couru autour de l'arbre et seulement alors commencé à nous poignarder. Nous ne tirerons pas comme ça, mais cela n'a pas de sens de poignarder tout de suite - ce ne sera pas clair.
Alors! Dans un système de combat, une balle de score sera calculée sur la base de deux groupes d'indicateurs:
- Indicateurs obtenus directement de l'emprunteur et de l'État. organes:
- déclaration fiscale;
- passeport détails des propriétaires, gène. réalisateurs, ch. comptable;
- Déclarations du Registre d'État unifié des entités juridiques, EGRIP;
- documents de titre;
- données sur la dette;
- données judiciaires;
- et ainsi de suite
- Indicateurs obtenus grâce à l'analyse graphique et à l'exploration de données:
- interaction avec l'état. organismes - consécutifs / sous-traitance / fourniture;
- interaction avec les entreprises du top 100;
- la présence dans l'environnement de l'emprunteur de sociétés en faillite, de débiteurs, d'entreprises à faible score;
- participation à des organisations caritatives
- et ainsi de suite
Sur la base des indicateurs listés, un modèle sera construit: les sommets du graphique seront toutes les organisations avec lesquelles l'emprunteur a interagi d'une manière ou d'une autre, les bords du graphique auront du poids. Le poids de la connexion sera défini dans une plage de 1 à 5, caractérisant le degré d'influence des nœuds les uns sur les autres.
Par exemple:
- L'emprunteur, qui est dans ce cas le fournisseur, est lié par des contrats avec le client pour 1 million de roubles. Le chiffre d'affaires annuel de l'emprunteur est de 5 millions, le chiffre d'affaires annuel du client est de 100 millions de roubles. On voit clairement que le fournisseur dépend davantage du client que du client du fournisseur. Ainsi, pour le Fournisseur, la connexion sera de 5 (par exemple), et pour le Client 1.
Il est clair que l'exemple est purement spéculatif et dans la vie réelle, nous ferons une analyse plus détaillée. C'est une question des articles suivants, et maintenant cela n'a aucun sens d'aller aussi loin.
Le degré d'interaction et les interactions elles-mêmes seront déterminés, entre autres, à l'aide d'algorithmes de recherche de graphes.
Dans notre système de test, nous utiliserons le même sujet avec les mousquetaires et leurs relations. La maquette sera au plus près du combat et démontrera suffisamment notre idée. À quoi en arriverons-nous finalement, à quoi ressemblera le modèle? Prenez votre temps pour dire: "Canalia!" ou "Je n'ai pas besoin d'académies. Tout Gascon d'enfance est académicien! » Tout ne sera pas aussi primitif qu'il n'y paraît.
Brève description: nos mousquetaires ont décidé de créer une société anonyme non publique (NPAO), qui fournira des bijoux et des services de sécurité, ils ont besoin d'un prêt pour démarrer l'activité. L'établissement de crédit est PJSC Korol, qui a commandé l'évaluation de NPO One for All
Caractéristiques du graphique présenté:
- Le graphique est non orienté (bidirectionnel) et pondéré.
- Chaque côte a un poids - le degré d'interaction. Dans la figure, nous n'avons pas compliqué et établi notre valeur de connexion dans chaque direction d'un nœud à l'autre. Nous nous sommes limités à une seule évaluation de communication agrégée. Mais dans l'algorithme de calcul, cela sera pris en compte.
- Les organisations marquées en rouge qui s'opposent à la nôtre et y interfèrent de toutes les manières. Dans la vraie vie, il s'agira de concurrents, d'entreprises en faillite, de défaillants malveillants, d'entreprises contre lesquelles un litige est en cours, etc.
- Probablement, vous pouvez déjà deviner que vous devrez évaluer les relations par niveaux et directions, c'est-à-dire que vous devrez prendre en compte non seulement le niveau de communication, mais aussi la direction. Il faudra prendre en compte l'influence mutuelle des nœuds et bien plus encore.
Nous avons beaucoup de travail devant nous. Eh bien, dans le cadre de cet article, nous avons terminé. Les objectifs déclarés de l'article, comme il nous semble, ont été atteints. Nous espérons avoir réussi à vous intéresser, et vous lisez jusqu'au bout.