SciPy ، خوارزميات الرسم البياني

SciPy (وضوح sai pie) عبارة عن حزمة تطبيق رياضية تستند إلى ملحق Numpy Python. يعمل هذا البرنامج على توسيع قدرات Python بشكل كبير من خلال تزويد المستخدم بأوامر وفصول عالية المستوى لإدارة البيانات وتصورها. باستخدام SciPy ، تتحول جلسة Python التفاعلية إلى نفس بيئة معالجة البيانات والنماذج الأولية الكاملة للأنظمة المعقدة مثل MATLAB و IDL و Octave و R-Lab و SciLab.

مقدمة

يوصى بتثبيت حزمة SciPy كجزء من Anaconda. من المستحسن أيضا الألفة مع أساسيات بيثون وجود وثائق Numpy في متناول اليد. للإيجاز والراحة ، نوافق على استيراد الطرود الرئيسية (رديئة ، سكيبي و matplotlib) على النحو التالي:

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

هذه هي اتفاقية الاستيراد الرسمية المستخدمة في شفرة المصدر NumPy و SciPy وفي الوثائق. الامتثال لهذه الاتفاقيات في التعليمات البرمجية الخاصة بك هو اختياري ، ولكن يوصى بشدة. يُنصح باستيراد كل عبوة بشكل منفصل على النحو التالي:

 from scipy import linalg, optimize 

لدى SciPy و NumPy إصدارات كاملة من الوثائق التي تغطي جميع وظائفها تقريبًا. وهي متوفرة على https://docs.scipy.org/ بتنسيق HTML و PDF. قد تكون بعض الأجزاء غير مكتملة أو قديمة الوثائق قيد التطوير باستمرار. نظرًا لأن SciPy هي منظمة تطوعية وتعتمد على المجتمع ، فإن مشاركتك من تقديم الملاحظات إلى تحسين الوثائق والكود هي موضع ترحيب وتشجيع نشط.

خوارزميات الرسم البياني المتفرقة (scipy.csgraph)

لويس كارول ، عيد ميلاد سعيد 1877

فكر في استخدام حزمة scipy.csgraph كمثال على لعبة الأطفال " سلالم الكلمات " التي ابتكرها لويس كارول يوم عيد الميلاد عام 1877. في هذه اللعبة ، تحتاج إلى العثور على المسار بين الكلمات ، واستبدال حرف واحد في وقت واحد. على سبيل المثال ، يمكنك تتبع المسار من قرد إلى شخص ما عن طريق توصيل الكلمتين "ape" و "man" كما يلي:

$$

$$\ rm ape \ to apt \ to ait \ to bit \ to big \ to bag \ to mag \ to man$$

يرجى ملاحظة أن كل خطوة تنطوي على تغيير حرف واحد فقط من الكلمة. هذا مجرد مسار واحد ممكن من القرد إلى الرجل ، لكن هل هذا أقصر طريق؟ وبالتالي ، من الضروري إيجاد أقصر طريق (سلم) بين كلمتين معينتين. يمكن حل هذه المشكلة باستخدام حزمة scipy.sparse.csgraph.

أولاً نحتاج إلى قائمة بالكلمات الصالحة. العديد من أنظمة التشغيل لديها مثل هذه القائمة المضمنة. على سبيل المثال ، في نظام التشغيل linux ، يمكن العثور على قائمة بالكلمات في أحد الأماكن التالية:

 /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 

لدينا الآن قائمة تضم 591 كلمة تتكون من ثلاثة أحرف (قد يختلف العدد الدقيق بناءً على القاموس المحدد المستخدم). كل هذه الكلمات هي الجزء العلوي من الرسم البياني. قم بإنشاء حواف تربط الرؤوس (أزواج من الكلمات) التي تختلف بحرف واحد فقط.
نحن نستخدم طريقة فعالة إلى حد ما ، والتي سوف تتطلب بعض التلاعب في مجموعة numpy:

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

 dtype('<U3') 

الآن لدينا مجموعة تحتوي كل إدخال فيها على ثلاثة أحرف Unicode. نود أن نجد جميع الأزواج التي لها شخصية واحدة بالضبط. لنبدأ بتحويل كل كلمة إلى متجه ثلاثي الأبعاد:

 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) 

نذكر أن مسافة Hamming هي عدد الأحرف المختلفة في متجهين من نفس الطول. باستخدام مسافة Hamming ، نحدد طول الحواف التي تربط أزواج الكلمات. ترتبط كل كلمتين بسلالم الكلمات بمسافة تساوي $$$\ frac {1} {N}$اين $$$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') 

أنت الآن بحاجة إلى العثور على أقصر مسار بين هذين الرأسين على الرسم البياني. للقيام بذلك ، نستخدم خوارزمية Dijkstra ، التي تسمح لك بالعثور على جميع المسافات الممكنة للرأس المحدد:

 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 مكونًا مرتبطًا: أي ، 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 (مفصولة إلى أقصى حد عن بعضها البعض). إذا نظرت عن كثب ، على جانبي الدرج الكلمات "imp" و "ump" ، والتي تختلف عن بعضها البعض بحرف واحد فقط. على الجانب الآخر من الدرج توجد الكلمات "أوم" و "أوم" ، والتي تتميز أيضًا بحرف واحد فقط. قائمة الخطوات بين هذه الكلمات ستكون هي نفسها تقريبا. يمكن العثور عليها بنفس الطريقة الموضحة أعلاه:

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

سلالم الكلمات هي مجرد واحدة من الاستخدامات الممكنة للخوارزميات السريعة على الرسوم البيانية المتناثرة في السماء. تُستخدم نظرية الرسم البياني في العديد من مجالات الرياضيات وتحليل البيانات والتعلم الآلي. أدوات الرسم البياني المتناثر مرنة بما يكفي للتعامل مع مجموعة واسعة من المهام.
سأكون مسروراً إذا كتبت في التعليقات ، أي قسم من الأقسام سيكون من المثير للاهتمام قراءته في المقال التالي.