Kursus ‘Pengantar Julia untuk Ilmu Data’ di MIT – Beragampengetahuan

Oleh: Blog Bogumił Kamiński

Repost dari:

Dari 17 hingga 20 Januari 2023, Anda dan saya akan mengalami kekurangan
Kursus Pengantar Julia untuk Ilmuwan Data di MIT.
Kursus ini terbuka sehingga semua orang diundang untuk bergabung dengan kami. Kamu dapat menemukan
Detail jadwal dan informasi lokasi di sini.

Kami bermaksud untuk mencakup berbagai bidang alat dan teknik ilmu data termasuk
model prediksi, optimisasi dan simulasi. Salah satu modul di
Kursus ini mencakup jaringan penambangan yang kompleks. Sangat menarik bahwa beberapa teknik
digunakan ada yang mirip dengan metode yang saya bahas minggu lalu
Sirkus kutu untuk salam Tahun Baru.

Jadi hari ini saya berpikir untuk menyajikan contoh terkait materi yang sedang kita kerjakan
perencanaan pelajaran dalam kursus termasuk analisis Markov
model.

Posting itu ditulis di bawah Julia 1.8. Seperti minggu lalu, saya ingin melakukan semuanya
analisis hanya menggunakan fungsionalitas yang tersedia di Base Julia.

Pertanyaan yang ingin saya jawab hari ini adalah sebagai berikut.

Misalkan kita memiliki grafik tidak berarah dan ada agen berjalan di atasnya. kami berasumsi
bahwa grafik terhubung, yaitu setiap node dapat diakses dari setiap node lainnya
simpul. Ketika agen berada di beberapa node, ia berpindah ke salah satu node yang terhubung
oleh tepi dengan tombol power. Jika sebuah simpul adalah titik akhir dari banyak sisi, maka a
diantaranya dipilih secara acak.

Sekarang kami siap membuat pertanyaan:

Dalam jangka panjang, seberapa sering setiap node dalam grafik yang dianalisis akan
dikunjungi?

Kami akan mencoba menyelesaikan masalah ini secara numerik.

Untuk fokus pada beberapa bagan tertentu, mari kita analisis jejaring sosial GitHub
diagram jaringan, deskripsi dapat ditemukan di sini.

Unduhan pertama musae_git_edges.csv ke direktori kerja Anda.

Mulailah dengan memeriksa isinya:

julia> raw = collect(eachline("musae_git_edges.csv"))
289004-element Vector{String}:
 "id_1,id_2"
 "0,23977"
 "1,34526"
 "1,2370"
 "1,14683"
 "1,29982"
 "1,21142"
 ⋮
 "37519,37678"
 "19093,2347"
 "37527,37596"
 "37529,37601"
 "37644,2347"
 "25879,2347"
 "25616,2347"

Kami menemukan bahwa setiap baris, kecuali yang pertama, berisi informasi tentang akhir dari
tepi dalam grafik kami. Mari kita pecahkan menjadi angka terlebih dahulu:

julia> edges = [parse.(Int, line) for line in split.(raw[2:end], ',')]
289003-element Vector{Vector{Int64}}:
 [0, 23977]
 [1, 34526]
 [1, 2370]
 [1, 14683]
 [1, 29982]
 [1, 21142]
 [1, 20363]
 ⋮
 [37519, 37678]
 [19093, 2347]
 [37527, 37596]
 [37529, 37601]
 [37644, 2347]
 [25879, 2347]
 [25616, 2347]

Selanjutnya, kami memeriksa jumlah tepi minimum dan maksimum dalam data:

julia> extrema(Iterators.flatten(edges))
(0, 37699)

Kami melihat bahwa kami memiliki 37700 node yang diberi nomor menggunakan indeks berbasis 0.

Sekarang mari kita buat matriks adjacency am dari grafik kami.
kami akan menempatkan 1 di dalam sel am[i, j] jika ada tepi antara node i dan j.
Kalau tidak kita akan pergi am[i, j] Oke 0.
Dalam proses pembuatan am matriks, kami akan memperbaiki nomor node untuk memulai
dengan 1:

julia> using SparseArrays

julia> from, to = getindex.(edges, 1) .+ 1, getindex.(edges, 2) .+ 1;

julia> am = sparse([from; to], [to; from], fill(1.0, 2 * length(edges)));

Mari kita periksa apakah grafik terhubung menggunakan pencarian luas pertama
(fungsi ini agak lambat, dalam proses belajar di MIT Anda akan melihat seperti ini
proses dapat diimplementasikan lebih cepat menggunakan Graphs.jl):

julia> function allconnected(am)
           seen = falses(size(am, 1))
           to_visit = [1]
           seen[1] = true
           while !isempty(to_visit)
               i = popfirst!(to_visit)
               new_neighbors = [j for j in findnz(am[i, :])[1] if !seen[j]]
               seen[new_neighbors] .= true
               append!(to_visit, new_neighbors)
           end
           return all(seen)
       end
allconnected (generic function with 1 method)

julia> allconnected(am)
true

Memang, grafiknya terhubung.

Menggunakan am matriks mudah untuk menghitung matriks transisi bagi kita
proses. Biarkan item tm[i, j] dalam tm matriks adalah probabilitas bahwa
agen bergerak dari node i ke tombol j dalam satu langkah. Jelas probabilitas ini
Menjadi 1 / deg[i] di mana deg[i] adalah derajat simpul i (itu jumlahnya
tetangga.

Mari kita menghitung tm matriks:

julia> deg = sum(am, dims=2);

julia> invdeg = 1 ./ deg;

julia> tm = am .* invdeg;

Mari kita periksa apakah sebenarnya probabilitas di baris tm matriks menambahkan hingga 1:

julia> sum(tm, dims=2)
37700×1 Matrix{Float64}:
 1.0
 1.0
 1.0
 1.0
 1.0
 1.0
 0.9999999999999999
 1.0
 1.0
 0.9999999999999998
 ⋮
 0.9999999999999974
 1.0
 1.0000000000000007
 1.0
 1.0000000000000002
 1.0
 1.0
 1.0
 1.0
 1.0

Kami hampir selesai menghitung probabilitas jangka panjang untuk mengunjungi setiap node
grafik yang dianalisa.

Kita bisa mulai dengan distribusi probabilitas dari node yang berkunjung. Anggapan,
misalnya seragam:

julia> p = fill(1 / 37700, 1, 37700)
1×37700 Matrix{Float64}:
 2.65252e-5  2.65252e-5  2.65252e-5  …  2.65252e-5  2.65252e-5

Dari teori matriks acak, kita tahu itu p * tm adalah distribusi dari
lokasi agen setelah satu langkah:

julia> p * tm
1×37700 Matrix{Float64}:
 8.28912e-7  2.8377e-5  4.65354e-7  …  1.54045e-5  7.46794e-7

Sekarang mari ulangi proses ini beberapa kali hingga vektor p stabil:

julia> function stationary(tm; eps=sqrt(eps()))
           p = fill(1 / 37700, 1, 37700)
           while true
               newp = p * tm
               if sum(abs(o - n) for (o, n) in zip(p, newp)) < eps
                   return newp
               end
               p = newp
           end
       end
stationary (generic function with 1 method)

julia> p = stationary(tm)
1×37700 Matrix{Float64}:
 1.73009e-6  1.38407e-5  1.73009e-6  …  5.19026e-6  6.92034e-6

Kami mengetahui distribusi tetap dari kemungkinan mengunjungi setiap node.
Namun, akan menarik untuk memahaminya. Seperti yang akan kita lihat
sebanding dengan derajat simpul. Mari kita mengujinya:

julia> extrema(vec(p) .- deg ./ sum(deg))
(-3.7003669919877247e-10, 9.529364854058532e-9)

Memang, penyimpangan dari p dari distribusi yang diberikan oleh tingkat node adalah
rendah seperti yang dijanjikan.

Kami telah mempelajari bahwa dalam jangka panjang seberapa sering setiap node akan melakukannya
kontra dengan probabilitas sebanding dengan derajatnya. Properti ini bisa
diverifikasi secara analitik untuk menjaga grafik terhubung yang tidak diarahkan. saya merekomendasi
Anda untuk melakukan perhitungan yang diperlukan.

Saya harap Anda menemukan contohnya menarik. Dalam kursus singkat ini di MIT
dan masih banyak lagi contoh yang akan dijelaskan secara detail dan akan kita bahas
Paket Julia dapat digunakan untuk analisis data dengan nyaman. Namun, saya ingin
untuk menyoroti, bahwa fitur Julia yang sangat menarik berkaitan dengan kenyataan
Seberapa jauh seseorang dapat menggunakan fungsi standarnya tanpa harus melakukannya
menginstal paket apapun.

Terkait