Geekly articles weekly

Hitung Scoring de la Fer atau studi tentang penilaian kredit sebagai bagian dari memperluas wawasan seseorang. Bagian 3

Bagian ketiga, di mana Athos diendapkan, dan Count de la Fer bijaksana dengan algoritma.


UPD Bagian Satu ada di sini
Bagian kedua UPD di sini


AntipovSN dan MihhaCF


Pengantar dari penulis:


Selamat siang Hari ini kami melanjutkan serangkaian artikel yang ditujukan untuk penilaian dan penggunaan teori grafik di dalamnya. Anda dapat berkenalan dengan artikel pertama dan kedua di sini dan di sini, masing-masing. Kami sangat menyarankan, jika tidak, artikel ini mungkin tampak seperti percobaan tanpa makna dengan algoritma.


Semua alegori komik, sisipan, dll., Dirancang untuk sedikit meringankan narasi dan tidak membiarkannya jatuh ke dalam kuliah yang membosankan. Kami meminta maaf kepada semua orang yang tidak masuk ke humor kami


Tujuan artikel ini: dalam waktu tidak lebih dari 30 menit, jelaskan algoritma pembuatan grafik dan hitung skor skor untuk NPO “One for All”.


Ketentuan dan definisi:


  • Algoritma pencarian kedalaman-pertama (DFS) - Strategi pencarian mendalam, seperti namanya, adalah pergi "lebih dalam" ke dalam grafik sejauh mungkin. Algoritme pencarian dijelaskan secara rekursif: kami memilah-milah semua tepi yang berasal dari titik tersebut. Jika ujung mengarah ke titik yang tidak dipertimbangkan sebelumnya, maka kami menjalankan algoritme dari titik yang tidak diperiksa ini, dan setelah itu kami kembali dan terus menyortir tepi. Pengembalian terjadi jika tidak ada tepi dalam simpul yang dipertimbangkan yang mengarah ke simpul yang tidak diperiksa. Jika, setelah penyelesaian algoritma, tidak semua simpul dipertimbangkan, maka perlu untuk menjalankan algoritma dari salah satu simpul yang tidak diperiksa
  • Rekursi - memanggil fungsi (prosedur) dari itu sendiri, langsung (rekursi sederhana) atau melalui fungsi lain (rekursi kompleks atau tidak langsung)

Pada artikel pertama kami (di sini ), kami menentukan model grafik yang akan kami coba, dan memberikan deskripsi singkat.


Dalam artikel kedua kami (di sini ), kami menggambarkan struktur data dasar yang dapat digunakan untuk menyimpan grafik dan menjelaskan lebih detail model grafik dan cara bekerja dengannya.


Sudah waktunya untuk mengeluarkan pedang dari sarungnya dan mulai menikam semua orang, atau lebih tepatnya, membuat algoritma untuk menghitung skor penilaian untuk NPO "One for All".


Ayo pergi!


Algoritma akan dieksekusi dalam Python . Seperti kata mereka, tarik ular ke pedang!


Grafik akan disimpan dalam kamus, sebagai berikut:


graph = { 'Odin_za_vseh' : {'goody': 10, 'rank': 4, 'fund':4, 'relations':{'Bonasye':3, 'Trevi': 1, 'Gusak':2,'Suchka':5, 'Roshfor':1, 'Cardi':1}}, 'Cardi' : {'goody': -8, 'rank': 9, 'fund':8, 'relations':{'Korol':2,'Odin_za_vseh':3,'Gvardia':5, 'Roshfor':5 }}, 'Roshfor' : {'goody': -7, 'rank': 7, 'fund':5,'relations':{'Cardi':1, 'Suchka': 3,'Odin_za_vseh':2, 'Bonasye':5 }}, 'Suchka' : {'goody': -10, 'rank': 4, 'fund':4, 'relations':{'Odin_za_vseh':5,'Roshfor':3 }}, 'Gvardia' : {'goody': -5, 'rank': 3, 'fund':4, 'relations':{'Cardi':1,'Gusak':1 }}, 'Gusak' : {'goody': -7, 'rank': 4, 'fund':4, 'relations':{'Gvardia':5,'Odin_za_vseh':2 }}, 'Trevi' : {'goody': 7, 'rank': 5, 'fund':5, 'relations':{'Odin_za_vseh':4,'Mushketery':5 }}, 'Bonasye': {'goody': -2, 'rank': 2, 'fund':3, 'relations':{'Odin_za_vseh':1,'Roshfor':1,'Konsta':2 }}, 'Konsta' : {'goody': 10, 'rank': 5, 'fund':3, 'relations':{'Koroleva':2,'Bonasye':1 }}, 'Mushketery' : {'goody': 7, 'rank': 5, 'fund':4, 'relations':{'Korol':1, 'Trevi':1}}, 'Koroleva' : {'goody': 6, 'rank': 8, 'fund':7, 'relations':{'Korol':2,'Konsta':5, 'EnglishMan':3 }}, 'Korol' : {'goody': 5, 'rank': 10, 'fund':10, 'relations':{'Cardi':3, 'Koroleva':5,'Mushketery':5 }}, 'EnglishMan' : {'goody': 5, 'rank': 8, 'fund':10, 'relations':{'Koroleva':2}} }

'goody' - peringkat simpul - baik atau buruk dan tingkat "prioritas" dari node. Misalnya, Kardinal adalah pahlawan negatif film, sehingga peringkatnya negatif. Kardinal adalah salah satu musuh utama para pahlawan kita, tetapi bukan yang paling penting (kami memutuskan demikian)
'peringkat' - skor simpul dalam tabel peringkat
'fund' - kelayakan simpul
'relations' - dengan siapa terhubung dan seberapa besar dapat mempengaruhi simpul yang terhubung dengannya


Sejauh ini, semuanya sederhana, tetapi pembaca yang perhatian sudah bisa melihat beberapa fitur, ya, pertanyaan tentang konten sudah muncul. Mari kita coba memprediksi dan menjawabnya. Hak injeksi pertama adalah milik kita!


  1. Saya pikir tidak ada gunanya menjelaskan apa yang kami gunakan untuk nama kunci kamus tingkat pertama. Namun, Anda sudah dapat menebak dengan benar, beberapa nama telah mengalami perubahan karena persepsi kami terhadap karya tersebut.


  2. Dari mana parameter ini berasal ('goody', 'rank', dll.), Mengapa mereka dan dari mana peringkat mereka berasal?
    Dalam rangka:


    • Dalam kehidupan nyata, parameter ini akan menjadi ciri perusahaan simpul tertentu. Untuk semua orang yang akan melakukan penilaian dan tergantung pada jenis penilaian ini, parameter ini akan berbeda. Sebagai contoh, parameter untuk mengevaluasi penilaian peminjam dapat berupa - omset, jumlah hutang / piutang, surat eksekusi, dll.
    • Mengapa tepatnya mereka - penulis melihatnya dengan cara ini))) parameter ini mencerminkan esensi dari apa yang dijelaskan Count, menurut pendapat kami
    • Penilaian, seperti yang mereka katakan sekarang, adalah pakar. Dalam kehidupan nyata, perkiraan ini akan diperoleh melalui penambangan. Kami akan menulis lebih banyak tentang ini di artikel selanjutnya.

  3. Mengapa beberapa node memiliki tautan timbal balik yang berbeda (misalnya, Odin_za_vseh - Bonasye = 3, dan Bonasye - Odin_za_vseh = 1)? Ini karena Odin_za_vseh memiliki efek yang jauh lebih besar pada Bonasye daripada sebaliknya. Dan ini penting untuk dipahami. Saat mencetak Odin_za_vseh, kita perlu mempertimbangkan efek Bonasye pada Odin_za_vseh.


  4. Apa itu skor obligasi dan bagaimana cara menghitungnya?


    • Penilaian komunikasi adalah ukuran pengaruh satu simpul terhadap simpul lainnya
    • Setiap koneksi dalam Grafik kami adalah dua arah, tetapi pada saat yang sama, penilaian komunikasi dalam arah yang berbeda dapat bervariasi
    • Skor komunikasi adalah nilai dari 1 hingga 5 (dari 1 hingga 5 misalnya saja). Tidak boleh ada koneksi negatif, karena node terhubung ke yang lain, dan kami mengevaluasi seberapa besar hal itu mempengaruhi node ini, atau tidak terhubung. Dalam kasus ini, tentu saja, koneksi dengan simpul yang tidak dapat diandalkan pada akhirnya akan negatif untuk simpul yang kami evaluasi, karena simpul yang tidak dapat diandalkan ini akan memiliki peringkat internal negatif.
    • Penilaian internal suatu simpul adalah nilai agregat yang terdiri dari parameter internal suatu simpul. Dalam contoh kita, ini adalah 'goody', 'rank', 'fund'. Peringkat internal mungkin negatif.

  5. Bagaimana bola skor dipertimbangkan?


    • Setiap perusahaan yang akan menggunakan pendekatan ini dapat meletakkan perhitungan skor skornya berdasarkan persyaratan dan pengalaman bisnisnya.
    • Dalam kasus kami, kami memilih cara yang sederhana dan rumit:
      • Skor skor = Skor internal dari simpul yang kami evaluasi + Jumlah (Penilaian internal untuk simpul anak level 1 yang mengevaluasi dampak simpul ini pada simpul yang dievaluasi) + (Jumlah (Peringkat internal simpul anak level 2 menilai pengaruh simpul ini pada simpul orangtua level 1) / 2)
      • Jika Anda mendapatkan skor skor negatif, maka kami tidak memberikan pinjaman
    • Algoritma yang disajikan di bawah ini adalah dasar dan dapat dengan mudah dimodifikasi agar sesuai dengan teknik perhitungan skor skor apa pun.
    • Semua kesulitan akan berada di penambangan "benar", tetapi itu akan dijelaskan dalam artikel berikutnya


Dan di sini adalah algoritma itu sendiri:


 searched=[] #   def search_outer(name,n): return graph[name]['goody']*graph[name]['rank']*graph[name]['fund']+search(name,n) # search_outer()    ,       #,       search() #name –   ,     #n –   –       def search(name, n, z=1): ball=0 #,      global searched #    if z <= n and name not in searched: #        searched.append(name) for x in graph[name]['relations']: #   ball += graph[x]['goody'] * graph[x]['rank'] * graph[x]['fund'] * graph[x]['relations'][name] / z + search(x,n,z+1) #      #   ,     return ball #, ,     def main(): ball = search_outer ('Odin_za_vseh', 2) print(ball) if __name__ == '__main__': main()

Untuk meringkas:


  • Saya yakin membaca artikel itu tidak lebih dari 30 menit
  • Kami menghitung skor penilaian untuk NPO One untuk Semua. Kami tidak memberikan penghargaan, NPO "One for All" ternyata adalah para petualang dengan sekelompok musuh. Kami dapat memberikan kredit kepada pegawai negeri, misalnya, 'Mushketery'
  • Algoritma itu ternyata sederhana dan cukup efektif.
  • Kompleksitas komputasi adalah O (N ** d +1), di mana d adalah jumlah level. Secara visual, algoritma ditunjukkan pada gambar di bawah ini.

gambar


Terima kasih sobolevn dan artikelnya


Anda dapat beralih ke penambangan data yang paling menarik dan sulit!


PS Mengenai tautan ke artikel lain dengan teori (dalam artikel sebelumnya, kami memberikan komentar):


Source: https://habr.com/ru/post/id465927/

More articles:


All Articles