Tutorial Data Science Dengan Pyhton : Cara Membuat Data Grafik di Python

CSGraph adalah singkatan dari Compressed Sparse Graph , yang berfokus pada algoritma grafik Cepat berdasarkan representasi matriks renggang .

Representasi Grafik

Untuk memulainya, mari kita pahami apa itu grafik renggang dan bagaimana grafik itu membantu dalam representasi grafik.

Apa sebenarnya grafik renggang itu?

Grafik hanyalah kumpulan node, yang memiliki hubungan di antara mereka. Grafik dapat mewakili hampir semua hal - koneksi jaringan sosial, di mana setiap node adalah orang dan terhubung ke kenalan; gambar, di mana setiap node adalah piksel dan terhubung ke piksel tetangga; poin dalam distribusi dimensi tinggi, di mana setiap node terhubung ke tetangga terdekatnya dan praktis apa pun yang dapat Anda bayangkan.

Salah satu cara yang sangat efisien untuk merepresentasikan data grafik adalah dalam matriks renggang: sebut saja G. Matriks G berukuran N x N, dan G [i, j] memberikan nilai hubungan antara node 'i' dan node 'j'. Grafik renggang sebagian besar berisi nol - yaitu, sebagian besar node hanya memiliki sedikit koneksi. Properti ini ternyata benar dalam banyak kasus yang menarik.

Pembuatan submodul grafik renggang dimotivasi oleh beberapa algoritme yang digunakan dalam scikit-learn yang mencakup berikut ini -

• Isomap - Algoritma pembelajaran berjenis, yang membutuhkan pencarian jalur terpendek dalam grafik.

• Pengelompokan hierarki - Algoritme pengelompokan berdasarkan pohon rentang minimum.

• Dekomposisi Spektral - Algoritme proyeksi berdasarkan grafik laplacia jarang.

Sebagai contoh konkret, bayangkan kita ingin merepresentasikan graf tak berarah berikut -

Grafik ini memiliki tiga node, di mana node 0 dan 1 dihubungkan oleh edge of weight 2, dan node 0 dan 2 dihubungkan oleh edge of weight 1. Kita dapat membuat representasi padat, bertopeng, dan jarang seperti yang ditunjukkan pada contoh berikut , perlu diingat bahwa grafik yang tidak berarah direpresentasikan oleh matriks simetris.

G_dense = np.array([ [0, 2, 1],
                     [2, 0, 0],
                     [1, 0, 0] ])
                     
G_masked = np.ma.masked_values(G_dense, 0)
from scipy.sparse import csr_matrix

G_sparse = csr_matrix(G_dense)
print G_sparse.data

Program di atas akan menghasilkan keluaran sebagai berikut.

array([2, 1, 2, 1])

Ini identik dengan grafik sebelumnya, kecuali node 0 dan 2 dihubungkan oleh tepi tanpa bobot. Dalam hal ini, representasi padat di atas mengarah pada ambiguitas - bagaimana non-edge dapat direpresentasikan, jika nol adalah nilai yang berarti. Dalam kasus ini, representasi bertopeng atau jarang harus digunakan untuk menghilangkan ambiguitas.

Mari kita perhatikan contoh berikut.

from scipy.sparse.csgraph import csgraph_from_dense
G2_data = np.array
([
   [np.inf, 2, 0 ],
   [2, np.inf, np.inf],
   [0, np.inf, np.inf]
])
G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
print G2_sparse.data

Program di atas akan menghasilkan keluaran sebagai berikut.

array([ 2., 0., 2., 0.])

Share :