SciPy (diucapkan sai pie) adalah paket aplikasi matematika berdasarkan ekstensi Numpy Python. Ini sangat memperluas kemampuan Python dengan menyediakan pengguna dengan perintah dan kelas tingkat tinggi untuk mengelola dan memvisualisasikan data. Dengan SciPy, sesi Python interaktif berubah menjadi lingkungan pemrosesan data dan prototipe lengkap yang sama untuk sistem yang kompleks seperti MATLAB, IDL, Octave, R-Lab dan SciLab.
Pendahuluan
Paket SciPy direkomendasikan untuk diinstal sebagai bagian dari Anaconda. Keakraban dengan dasar-dasar Python dan memiliki dokumentasi Numpy di tangan juga disarankan. Untuk singkatnya dan kenyamanan lebih lanjut, kami setuju bahwa paket utama (numpy, scipy dan matplotlib) akan diimpor sebagai berikut:
import numpy as np import matplotlib as mpl import matplotlib.pyplot as plt
Ini adalah perjanjian impor resmi yang digunakan dalam NumPy, kode sumber SciPy dan dalam dokumentasi. Kepatuhan terhadap konvensi ini dalam kode Anda adalah opsional, tetapi sangat dianjurkan. Dianjurkan untuk mengimpor masing-masing paket secara terpisah sebagai berikut:
from scipy import linalg, optimize
SciPy dan NumPy memiliki versi lengkap dari dokumentasi yang mencakup hampir semua fungsinya. Mereka tersedia di https://docs.scipy.org/ dalam format HTML dan PDF. Beberapa bagian mungkin tidak lengkap atau ketinggalan zaman, seperti dokumentasi terus dikembangkan. Karena SciPy adalah organisasi sukarela dan tergantung pada komunitas, partisipasi Anda dari memberikan umpan balik hingga meningkatkan dokumentasi dan kode disambut dan didorong secara aktif.
Algoritma Grafik Jarang (scipy.csgraph)
Lewis Carroll, Selamat Natal 1877
Pertimbangkan penggunaan paket scipy.csgraph sebagai contoh permainan anak-anak " Ladders of Words " yang diciptakan oleh Lewis Carroll pada Hari Natal 1877. Dalam gim ini, Anda harus menemukan jalur di antara kata-kata itu, mengganti satu huruf sekaligus. Misalnya, Anda dapat melacak jalur dari monyet ke seseorang dengan menghubungkan kata "kera" dan "manusia" sebagai berikut:
Harap dicatat bahwa setiap langkah melibatkan perubahan hanya satu huruf kata. Ini hanya satu jalan yang mungkin dari monyet ke manusia, tetapi apakah ini jalan terpendek? Dengan demikian, perlu untuk menemukan jalan terpendek (tangga) antara dua kata yang diberikan. Masalah ini dapat diselesaikan dengan menggunakan paket scipy.sparse.csgraph.
Pertama kita perlu daftar kata-kata yang valid. Banyak sistem operasi memiliki daftar bawaan seperti itu. Sebagai contoh, di linux, daftar kata dapat ditemukan di salah satu tempat berikut:
/usr/share/dict /var/lib/dict
Sumber kata lain adalah kamus yang tersedia di berbagai situs di Internet (lihat di mesin pencari favorit Anda). Daftar kata sistem adalah file dengan satu kata per baris. Untuk menggunakan daftar kata sistem, Anda harus membacanya sebagai berikut:
word_list = open('/usr/share/dict/words').readlines() word_list = map(str.strip, word_list)
Karena kami mencari kata-kata dari tiga huruf, maka kami hanya akan memilih kata-kata yang diperlukan dari daftar umum. Kami juga mengecualikan kata-kata yang dimulai dengan huruf besar (kata benda yang tepat) atau berisi karakter non-alfabet, seperti apostrof dan tanda hubung. Pada akhirnya, periksa ukuran daftar kata yang dihasilkan.
word_list = [word for word in word_list if len(word) == 3] word_list = [word for word in word_list if word[0].islower()] word_list = [word for word in word_list if word.isalpha()] word_list = list (map (str.lower, word_list)) len (word_list)
591
Sekarang kami memiliki daftar 591 kata tiga huruf (angka pastinya dapat bervariasi tergantung pada kamus tertentu yang digunakan). Setiap kata ini adalah bagian atas grafik. Buat tepi yang menghubungkan simpul (pasangan kata) yang berbeda hanya dengan satu huruf.
Kami menggunakan cara yang cukup efisien, yang akan membutuhkan manipulasi array numpy:
word_list = np.asarray(word_list) word_list.sort()
dtype('<U3')
Sekarang kita memiliki sebuah array di mana setiap entri berisi tiga karakter Unicode. Kami ingin menemukan semua pasangan yang memiliki tepat satu karakter. Mari kita mulai dengan mengubah setiap kata menjadi vektor tiga dimensi:
word_bytes = np.ndarray((word_list.size, word_list.itemsize), dtype='uint8', buffer=word_list.data)
(591, 3)
Kita ingat bahwa jarak Hamming adalah jumlah karakter yang berbeda dalam dua vektor dengan panjang yang sama. Menggunakan jarak Hamming, kami menentukan panjang tepi yang menghubungkan pasangan kata. Setiap dua kata terhubung ke tangga kata dengan jarak yang sama dengan dimana - jumlah huruf dalam satu kata:
from scipy.spatial.distance import pdist, squareform from scipy.sparse import csr_matrix hamming_dist = pdist (word_bytes, metric = 'hamming') graph = csr_matrix (squareform (hamming_dist < 1.5 / 3))
Ketika membandingkan jarak, persamaan yang tidak ketat digunakan, karena jika tidak hasilnya mungkin tidak stabil untuk nilai floating point. Ketimpangan memberikan hasil yang diinginkan jika dua karakter dalam kata tidak cocok. Sekarang setelah grafik diberikan, kami akan melakukan pencarian jalur terpendek antara dua kata pada grafik:
i1 = word_list.searchsorted ('ape') i2 = word_list.searchsorted ('man')
Sekarang Anda perlu menemukan jalur terpendek antara dua simpul ini pada grafik. Untuk melakukan ini, kami menggunakan algoritme Dijkstra, yang memungkinkan Anda menemukan semua jarak yang memungkinkan untuk titik tertentu:
from scipy.sparse.csgraph import dijkstra distances, predecessors = dijkstra(graph, indices=i1, return_predecessors=True) print(distances[i2])
5.0
Jadi, kita melihat bahwa jalan terpendek antara monyet dan manusia hanya berisi lima langkah. Kita dapat menggunakan pendahulu yang dikembalikan oleh algoritma untuk memulihkan jalur ini:
path = [] i = i2 while i != i1: path.append(word_list[i]) i = predecessors[i] path.append(word_list[i1]) print(path[::-1])
['ape', 'apt', 'opt', 'oat', 'mat', 'man']
Panjang tangga adalah tiga langkah lebih sedikit dari pada contoh awal. Dengan menggunakan alat lain dari modul, Anda dapat menemukan jawaban untuk pertanyaan lain. Misalnya, apakah ada kata-kata dengan tiga huruf yang tidak terhubung di tangga kata? Ini adalah tugas untuk menentukan konektivitas grafik:
from scipy.sparse.csgraph import connected_components N_components, component_list = connected_components(graph) print(N_components)
15
Dalam contoh kami, untuk kata tiga huruf, ada 15 komponen terkait: yaitu, 15 set kata yang berbeda tanpa jalur di antara mereka. Berapa banyak kata dalam setiap set ini? Kita dapat mengetahui dari daftar komponen:
[np.sum(component_list == i) for i in range(N_components)]
[577, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Kami mendapat satu grafik besar, yang mencakup 577 simpul, serta 14 grafik terisolasi. Mari kita lihat kata-kata ini:
[list(word_list[np.where(component_list == i)]) for i in range(1, N_components)]
[['aha'], ['chi'], ['ebb'], ['gnu'], ['ism'], ['khz'], ['nth'], ['nÊe'], ['ova'], ['qua'], ['ugh'], ['ups'], ['urn'], ['use']]
Anda dapat menemukan di antara kata-kata yang mana ada tangga dengan panjang maksimum. Ini dapat ditentukan dengan menghitung matriks adjacency. Perhatikan bahwa jarak antara dua titik yang tidak terhubung dianggap tak terbatas, oleh karena itu mereka harus dikecualikan:
distances, predecessors = dijkstra(graph, return_predecessors=True) max_distance = np.max(distances[~np.isinf(distances)]) print(max_distance)
13.0
Jadi, dalam contoh kita ada pasangan kata seperti itu, di antaranya tangga terpendek berisi 13 langkah! Mari kita tentukan pasangan apa ini:
i1, i2 = np.where(distances == max_distance) list(zip(word_list[i1], word_list[i2]))
[('imp', 'ohm'), ('imp', 'ohs'), ('ohm', 'imp'), ('ohm', 'ump'), ('ohs', 'imp'), ('ohs', 'ump'), ('ump', 'ohm'), ('ump', 'ohs')]
Kami melihat semua kombinasi yang mungkin dari pasangan kata, jarak di antaranya adalah 13 (secara terpisah terpisah satu sama lain). Jika Anda perhatikan dengan seksama, di satu sisi tangga ada kata "imp" dan "ump", yang berbeda satu sama lain hanya dengan satu huruf. Di sisi lain tangga adalah kata "ohm" dan "ohs," yang juga dibedakan hanya dengan satu huruf. Daftar langkah-langkah di antara kata-kata ini akan hampir sama. Itu dapat ditemukan dengan cara yang sama seperti ditunjukkan di atas:
path = [] i = i2[0] while i != i1[0]: path.append(word_list[i]) i = predecessors[i1[0], i] path.append(word_list[i1[0]]) print(path[::-1])
['imp', 'amp', 'asp', 'ass', 'ads', 'ids', 'ins', 'inn', 'ion', 'won', 'woo', 'who', 'oho', 'ohm']
Tangga kata hanyalah salah satu dari kemungkinan penggunaan algoritma cepat pada grafik yang jarang dalam scipy. Teori grafik digunakan di banyak bidang matematika, analisis data, dan pembelajaran mesin. Alat grafik scipy sparse cukup fleksibel untuk menangani berbagai tugas.
Saya akan senang jika Anda menulis di bagian komentar mana yang akan menarik untuk dibaca di artikel selanjutnya.