💊 👨‍👨‍👧‍👧 🔨 SciPy, ग्राफ एल्गोरिदम 👩🏼‍🤝‍👨🏾 👎🏾 👨🏿‍🤝‍👨🏽

SciPy (स्पष्ट साई पाई) एक गणितीय अनुप्रयोग पैकेज है जो नम्पी पायथन विस्तार पर आधारित है। यह उपयोगकर्ता को डेटा के प्रबंधन और विज़ुअलाइज़ेशन के लिए उच्च-स्तरीय कमांड और कक्षाएं प्रदान करके पायथन की क्षमताओं का विस्तार करता है। SciPy के साथ, एक इंटरैक्टिव पायथन सत्र MATLAB, IDL, ऑक्टेव, आर-लैब और SciLab जैसी जटिल प्रणालियों के लिए एक ही संपूर्ण डेटा प्रोसेसिंग और प्रोटोटाइपिंग वातावरण में बदल जाता है।

परिचय

SciPy पैकेज को एनाकोंडा के हिस्से के रूप में स्थापित करने की सिफारिश की गई है। अजगर की मूल बातें और हाथ पर Numpy प्रलेखन के साथ परिचित भी उचित है। संक्षिप्तता और आगे की सुविधा के लिए, हम इस बात से सहमत हैं कि मुख्य पैकेज (numpy, scipy और matplotlib) निम्नानुसार आयात किए जाएंगे:

import numpy as np import matplotlib as mpl import matplotlib.pyplot as plt

यह NumPy, SciPy स्रोत कोड और प्रलेखन में उपयोग किया जाने वाला आधिकारिक आयात अनुबंध है। आपके कोड में इन सम्मेलनों का अनुपालन वैकल्पिक है, लेकिन अत्यधिक अनुशंसित है। प्रत्येक पैकेज को निम्नानुसार अलग से आयात करना उचित है:

 from scipy import linalg, optimize

SciPy और NumPy के पास प्रलेखन के पूर्ण संस्करण हैं जो उनके लगभग सभी कार्यों को कवर करते हैं। वे HTML और पीडीएफ प्रारूप में https://docs.scipy.org/ पर उपलब्ध हैं। कुछ हिस्से अधूरे या पुराने हो सकते हैं, जैसे प्रलेखन लगातार विकास के अधीन है। चूंकि SciPy एक स्वयंसेवी संगठन है और समुदाय पर निर्भर करता है, इसलिए प्रलेखन और कोड में सुधार के लिए प्रतिक्रिया प्रदान करने से लेकर आपकी भागीदारी का स्वागत है और सक्रिय रूप से प्रोत्साहित किया जाता है।

विरल ग्राफ़ एल्गोरिदम (scipy.csgraph)

लुईस कैरोल, मेरी क्रिसमस 1877

क्रिसमस दिवस 1877 पर लुईस कैरोल द्वारा बच्चों के खेल " लैडर्स ऑफ वर्ड्स " के उदाहरण के रूप में scipy.csgraph पैकेज के उपयोग पर विचार करें। इस खेल में, आपको एक बार में एक अक्षर की जगह, शब्दों के बीच का रास्ता खोजना होगा। उदाहरण के लिए, आप "बंदर" और "आदमी" शब्दों को जोड़कर एक बंदर से एक व्यक्ति तक का रास्ता खोज सकते हैं:

$\ rm ape \ apt \ ait \ ait \ करने के लिए बिट \ करने के लिए बड़ा \ करने के लिए \ "आदमी \" करने के लिए बै$

कृपया ध्यान दें कि प्रत्येक चरण में शब्द का केवल एक अक्षर बदलना शामिल है। यह एक बंदर से एक आदमी के लिए सिर्फ एक संभव रास्ता है, लेकिन क्या यह सबसे छोटा रास्ता है? इस प्रकार, दो दिए गए शब्दों के बीच सबसे छोटा रास्ता (सीढ़ी) खोजना आवश्यक है। यह समस्या scipy.sparse.csgraph पैकेज का उपयोग करके हल की जा सकती है।

पहले हमें मान्य शब्दों की सूची चाहिए। कई ऑपरेटिंग सिस्टम में ऐसी अंतर्निहित सूची होती है। उदाहरण के लिए, लिनक्स में, शब्दों की एक सूची निम्नलिखित स्थानों में से एक में मिल सकती है:

 /usr/share/dict /var/lib/dict

शब्दों का एक अन्य स्रोत इंटरनेट पर विभिन्न साइटों पर उपलब्ध है (अपने पसंदीदा खोज इंजन में देखें)। सिस्टम शब्द सूची प्रति पंक्ति एक शब्द के साथ एक फ़ाइल है। सिस्टम शब्द सूची का उपयोग करने के लिए, आपको इसे इस प्रकार पढ़ना होगा:

 word_list = open('/usr/share/dict/words').readlines() word_list = map(str.strip, word_list)

क्योंकि हम तीन अक्षरों के शब्दों की तलाश कर रहे हैं, फिर हम सामान्य सूची से केवल आवश्यक शब्दों का चयन करेंगे। हम उन शब्दों को भी छोड़ देते हैं, जो अपरकेस (उचित संज्ञा) से शुरू होते हैं या इसमें गैर-अक्षर वर्ण होते हैं जैसे एपोस्ट्रोफ और हाइफ़न। अंत में, शब्दों की परिणामी सूची के आकार की जांच करें।

 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 तीन-अक्षर शब्दों की एक सूची है (सटीक संख्या विशेष रूप से प्रयुक्त शब्दकोश के आधार पर भिन्न हो सकती है)। इनमें से प्रत्येक शब्द ग्राफ के शीर्ष पर है। किनारों को जोड़ने वाले किनारों को बनाएं (शब्दों के जोड़े) जो केवल एक अक्षर से भिन्न होते हैं।
हम एक काफी कुशल तरीके का उपयोग करते हैं, जिसके लिए संख्यात्मक खांचे के कुछ हेरफेर की आवश्यकता होगी:

 word_list = np.asarray(word_list) word_list.sort() #     word_list.dtype #   -  Unicode  Python

 dtype('<U3')

अब हमारे पास एक सरणी है जिसमें प्रत्येक प्रविष्टि में तीन यूनिकोड वर्ण हैं। हम उन सभी जोड़ियों को खोजना चाहेंगे जिनके पास एक ही चरित्र हो। आइए प्रत्येक शब्द को त्रि-आयामी वेक्टर में परिवर्तित करके शुरू करें:

 word_bytes = np.ndarray((word_list.size, word_list.itemsize), dtype='uint8', buffer=word_list.data) #     - 4 .      #        word_bytes = word_bytes[:, ::word_list.itemsize//3] word_bytes.shape

 (591, 3)

हमें याद है कि हैमिंग दूरी एक ही लंबाई के दो वैक्टर में विभिन्न पात्रों की संख्या है। हमिंग दूरी का उपयोग करते हुए, हम शब्दों के जोड़े को जोड़ने वाले किनारों की लंबाई निर्धारित करते हैं। हर दो शब्द समान दूरी के साथ शब्दों की सीढ़ी से जुड़े होते हैं $\ frac {1} {N}$ जहाँ $एन = 3$ - एक शब्द में अक्षरों की संख्या:

 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))

दूरी की तुलना करते समय, गैर-सख्त समानता का उपयोग किया जाता है, क्योंकि अन्यथा परिणाम अस्थायी बिंदु मानों के लिए अस्थिर हो सकता है। यदि शब्द में दो अक्षर मेल नहीं खाते हैं, तो असमानता वांछित परिणाम देती है। अब जब ग्राफ दिया गया है, तो हम ग्राफ़ पर किसी भी दो शब्दों के बीच सबसे छोटी पथ खोज करेंगे:

 i1 = word_list.searchsorted ('ape') i2 = word_list.searchsorted ('man')

अब आपको ग्राफ़ पर इन दो कोने के बीच सबसे छोटा रास्ता खोजने की आवश्यकता है। ऐसा करने के लिए, हम दिक्जस्ट्रा एल्गोरिथ्म का उपयोग करते हैं, जो आपको निर्दिष्ट शीर्ष के लिए सभी संभव दूरी खोजने की अनुमति देता है:

 from scipy.sparse.csgraph import dijkstra distances, predecessors = dijkstra(graph, indices=i1, return_predecessors=True) print(distances[i2])

5.0

इसलिए, हम देखते हैं कि एक बंदर और आदमी के बीच का सबसे छोटा रास्ता केवल पाँच चरणों में होता है। इस पथ को पुनर्स्थापित करने के लिए हम एल्गोरिथम द्वारा लौटाए गए पूर्ववर्तियों का उपयोग कर सकते हैं:

 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']

प्रारंभिक उदाहरण की तुलना में सीढ़ियों की लंबाई तीन कदम कम है। मॉड्यूल के अन्य उपकरणों का उपयोग करके, आप अन्य सवालों के जवाब पा सकते हैं। उदाहरण के लिए, क्या तीन अक्षर वाले शब्द हैं जो शब्दों की सीढ़ी से जुड़े नहीं हैं? यह एक ग्राफ की कनेक्टिविटी निर्धारित करने का कार्य है:

 from scipy.sparse.csgraph import connected_components N_components, component_list = connected_components(graph) print(N_components)

हमारे उदाहरण में, तीन-अक्षर के शब्दों के लिए, 15 संबंधित घटक हैं: अर्थात, 15 अलग-अलग शब्द जिनके बीच कोई पथ नहीं है। इनमें से प्रत्येक सेट में कितने शब्द हैं? हम घटकों की सूची से पता लगा सकते हैं:

 [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]

हमें एक बड़ा ग्राफ मिला, जिसमें 577 कोने और साथ ही 14 अलग-अलग रेखांकन शामिल हैं। आइए इन शब्दों को देखें:

 [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']]

आप पता लगा सकते हैं कि किन शब्दों के बीच अधिकतम लंबाई की सीढ़ी है। यह आसन्न मैट्रिक्स की गणना करके निर्धारित किया जा सकता है। ध्यान दें कि दो असंबद्ध बिंदुओं के बीच की दूरी को अनंत माना जाता है, इसलिए उन्हें बाहर रखा जाना चाहिए:

 distances, predecessors = dijkstra(graph, return_predecessors=True) max_distance = np.max(distances[~np.isinf(distances)]) print(max_distance)

 13.0

तो, हमारे उदाहरण में शब्दों के ऐसे जोड़े हैं, जिनके बीच सबसे छोटी सीढ़ी में 13 चरण हैं! आइए निर्धारित करें कि ये जोड़े क्या हैं:

 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')]

हमने शब्दों के जोड़े के सभी संभावित संयोजनों को देखा, जिनके बीच की दूरी 13 है (अधिकतम एक दूसरे से अलग)। यदि आप बारीकी से देखते हैं, तो सीढ़ियों के एक तरफ "छोटा" और "अंप" शब्द हैं, जो केवल एक अक्षर के साथ एक दूसरे से भिन्न होते हैं। सीढ़ियों के दूसरी तरफ "ओम" और "ओह्स" शब्द हैं, जो कि केवल एक अक्षर द्वारा प्रतिष्ठित हैं। इन शब्दों के बीच चरणों की सूची लगभग समान होगी। यह उसी तरह से पाया जा सकता है जैसा कि ऊपर बताया गया है:

 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']

स्कैपी में विरल ग्राफ़ पर शब्द सीढ़ियाँ तेज़ एल्गोरिदम के संभावित उपयोगों में से एक हैं। ग्राफ सिद्धांत का उपयोग गणित, डेटा विश्लेषण और मशीन सीखने के कई क्षेत्रों में किया जाता है। कार्यों की एक विस्तृत श्रृंखला को संभालने के लिए स्कैपी विरल ग्राफ उपकरण काफी लचीले होते हैं।
मुझे खुशी होगी यदि आप टिप्पणियों में लिखते हैं कि अगले लेख में डराने के लिए कौन सा खंड पढ़ना दिलचस्प होगा।

SciPy, ग्राफ एल्गोरिदम

परिचय

विरल ग्राफ़ एल्गोरिदम (scipy.csgraph)

More articles: