Cara menggunakan SPARSE. pada Python

Apa itu Sparse Data?

Sparse Data adalah data yang sebagian besar memiliki elemen yang tidak digunakan (elemen yang tidak membawa informasi apa pun).

Ini bisa berupa array seperti ini:

[1, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 0]

Sparse Data: adalah kumpulan data yang sebagian besar nilai itemnya nol.

Dense Array: kebalikan dari sparse array: data yang sebagian besar nilainya bukan nol.

Dalam komputasi ilmiah, ketika kita akan berurusan dengan turunan parsial dalam aljabar linier, dan akan menemukan sparse data.

Section Artikel

• 0.1 Bagaiaman cara Bekerja Dengan Sparse Data?
• 1 Matriks CSR
• 2 Metode Matriks Sparse

Bagaiaman cara Bekerja Dengan Sparse Data?

SciPy memiliki modul scipy.sparse yang menyediakan fungsi untuk menangani sparse data.

Terutama ada dua jenis matriks sparse yang digunakan:

CSC – Compressed Sparse Column. Untuk aritmatika yang efisien, pemotongan kolom cepat.

CSR – Compressed Sparse Row. Untuk pengirisan baris cepat, product vektor matriks lebih cepat

Kita akan menggunakan matriks CSR dalam tutorial ini.

Matriks CSR

Kita bisa membuat matriks CSR dengan melewatkan array ke dalam function scipy.sparse.csr_matrix().

Contoh:
Buat matriks CSR dari array

import numpy as np
from scipy.sparse import csr_matrix

arr = np.array([0, 0, 0, 0, 0, 1, 1, 0, 2])

print(csr_matrix(arr))

Contoh di atas mengembalikan:

(0, 5) 1
(0, 6) 1
(0, 8) 2

Dari hasil tersebut dapat dilihat bahwa terdapat 3 item yang bernilai.

Item 1. berada di baris 0 posisi 5 dan memiliki nilai 1.

Item 2. berada di baris 0 posisi 6 dan memiliki nilai 1.

Item 3. berada di baris 0 posisi 8 dan memiliki nilai 2.

Metode Matriks Sparse

Melihat data yang disimpan (bukan item nol) dengan properti data.

Contoh:

import numpy as np
from scipy.sparse import csr_matrix

arr = np.array([[0, 0, 0], [0, 0, 1], [1, 0, 2]])

print(csr_matrix(arr).data)

Menghitung nonzeros dengan metode count_nonzero().

Contoh:

import numpy as np
from scipy.sparse import csr_matrix

arr = np.array([[0, 0, 0], [0, 0, 1], [1, 0, 2]])

print(csr_matrix(arr).count_nonzero())

Menghapus zero-entries dari matriks dengan metode elimin_zeros().

Contoh:

import numpy as np
from scipy.sparse import csr_matrix

arr = np.array([[0, 0, 0], [0, 0, 1], [1, 0, 2]])

mat = csr_matrix(arr)
mat.eliminate_zeros()

print(mat)

Menghilangkan entri duplikat dengan metode sum_duplicates().

Contoh:
Menghilangkan duplikat dengan menambahkannya:

import numpy as np
from scipy.sparse import csr_matrix

arr = np.array([[0, 0, 0], [0, 0, 1], [1, 0, 2]])

mat = csr_matrix(arr)
mat.sum_duplicates()

print(mat)

Mengonversi dari csr ke csc dengan metode tocsc().

Contoh:

import numpy as np
from scipy.sparse import csr_matrix

arr = np.array([[0, 0, 0], [0, 0, 1], [1, 0, 2]])

newarr = csr_matrix(arr).tocsc()

print(newarr)

Catatan: Terlepas dari operasi spesifik sparse yang disebutkan, matriks sparse mendukung semua operasi yang didukung matriks normal, mis. membentuk kembali, menjumlahkan, aritmatika, menyiarkan, dll.

Section Artikel

• 0.1 Bekerja dengan Graph
• 1 Matriks Adjacency
• 2 Komponen Terhubung
• 3 Dijkstra
• 4 Floyd Warshall
• 5 Bellman Ford
• 6 Depth First Order
• 7 Breadth First Order

Bekerja dengan Graph

Graph adalah struktur data penting.

SciPy memberi kita modul scipy.sparse.csgraph untuk bekerja dengan struktur data seperti itu.

Matriks Adjacency

Matriks Adjacency adalah matriks nxn dimana n adalah jumlah elemen dalam suatu graph.

Dan nilai-nilai tersebut mewakili hubungan antar elemen.

Contoh:

Untuk graph seperti ini, dengan elemen A, B dan C, hubungannya adalah:

A & B dihubungkan dengan bobot 1.

A & C dihubungkan dengan bobot 2.

C & B tidak terhubung.

Adjency Matrix akan terlihat seperti ini:

A B C
A: [0 1 2]
B: [1 0 0]
C: [2 0 0]

Contoh di bawah ini mengikuti beberapa metode yang paling sering digunakan untuk bekerja dengan matriks adjacency.

Komponen Terhubung

Menemukan semua komponen yang terhubung dengan metode connected_components().
Contoh:

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(connected_components(newarr))

Dijkstra

Gunakan metode dijkstra untuk menemukan jalur terpendek dalam graph dari satu elemen ke elemen lainnya.

Dibutuhkan argumen berikut:

1. return_predecessors: boolean (True untuk mengembalikan seluruh jalur traversal jika tidak False).
2. indices : indeks elemen untuk mengembalikan semua jalur dari elemen itu saja.
3. limit: bobot jalur maks.

Contoh:
Temukan jalur terpendek dari elemen 1 ke 2

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(dijkstra(newarr, return_predecessors=True, indices=0))

Floyd Warshall

Gunakan metode floyd_warshall() untuk menemukan jalur terpendek di antara semua pasangan elemen.

Contoh:
Temukan jalur terpendek di antara semua pasangan elemen

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(floyd_warshall(newarr, return_predecessors=True))

Bellman Ford

Metode bellman_ford() juga bisa menemukan jalur terpendek di antara semua pasangan elemen, dan metode ini juga bisa menangani bobot negatif.

Contoh:
Temukan jalur terpendek dari elemen 1 ke 2 dengan graph yang diberikan dengan bobot negatif

import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

arr = np.array([
  [0, -1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(bellman_ford(newarr, return_predecessors=True, indices=0))

Depth First Order

Metode depth_first_order() mengembalikan traversal kedalaman pertama dari sebuah node.

Fungsi ini mengambil argumen berikut:

1. graph.
2. elemen awal untuk melintasi graph.

Contoh
Trasversal kedalaman graph pertama pada matriks adjacency  yang diberikan

import numpy as np
from scipy.sparse.csgraph import depth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(depth_first_order(newarr, 1))

Breadth First Order

Metode breadth_first_order() mengembalikan traversal luas yang pertama dari sebuah node.

Fungsi ini mengambil argumen berikut:

1. graph.
2. elemen awal untuk melintasi graph.

Contoh
Traversal luas graph pertama pada matriks adjacency yang diberikan

import numpy as np
from scipy.sparse.csgraph import breadth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(breadth_first_order(newarr, 1))