ضرب مصفوفة كبيرة الحجم مع pyspark (أو - كيفية مطابقة مجموعتي بيانات كبيرتين من أسماء الشركات)

يتمتع Spark و pyspark بدعم رائع لتوزيع وموازنة موثوقين للبرامج بالإضافة إلى دعم العديد من العمليات الجبرية الأساسية وخوارزميات التعلم الآلي.

في هذا المنشور ، نصف دوافع ووسائل تنفيذ مطابقة الاسم من مجموعتين كبيرتين من أسماء الشركات باستخدام Spark.

الدافع الأول

هدفنا هو مطابقة مجموعتين كبيرتين من أسماء الشركات. نحن نبحث في قائمتين طويلتين من أسماء الشركات ، القائمة A والقائمة B ، ونهدف إلى مطابقة الشركات من A إلى الشركات من B.

عادة سيكون لدينا شيء مثل هذا:

قائمة A | قائمة ب
---------------------
GOOGLE INC. | جوجل
MEDIUM.COM | شركة متوسطة
مختبرات الامازون | الأمازون
جوجل ، وشركة |
Yahoo |
             | مايكروسوفت

في هذا المثال ، يتمثل هدفنا في مطابقة كل من GOOGLE INC. و Google ، inc (من القائمة A) إلى Google (من القائمة B) ؛ وللمطابقة بين MEDIUM.COM و Medium Inc؛ ومختبرات Amazon إلى Amazon ، إلخ ...

بالنظر إلى هذا المثال البسيط ، تبرز بعض الأشياء:

  • من الممكن أن تتطابق أكثر من شركة واحدة من A مع شركة واحدة من B ؛ إنها علاقة متعددة.
  • في معظم الحالات يكون من السهل على البشر مطابقة (مثل مختبرات Amazon إلى Amazon) ولكنها ليست سهلة لمطابقة أجهزة الكمبيوتر (كيف يعرف الكمبيوتر أن "labs" في هذه الحالة غير مهمة وأن "Amazon" هو مجرد اختصار لـ "مختبرات Amazon"؟)
  • ليس كل الشركات من A لها تطابقات في B ، وليس كل الشركات من B مطابقة من A. في مثالنا ، لا تتطابق Yahoo من القائمة A مع أي شركة أخرى على B ولا تتطابق Microsoft من B مع أي شركة على A .
  • يجب أن يكون لأي عنصر من القائمة "أ" تطابق واحد على الأكثر من "ب". والعكس غير صحيح كما هو موضح أعلاه ، ويمكن مطابقة العديد من الشركات من "أ" في شركة واحدة على "ب".

المحاولة الأولى - مباراة تافهة

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

الدقة واستدعاء

هناك نوعان من التدابير ذات الصلة للنظر في: الدقة والاستدعاء. الدقة هي "عدد الأخطاء التي ارتكبناها (لم نرتكبها)" ، أو بعبارة أخرى - بالنظر إلى جميع التطابقات ، كم منها كانت بالفعل مطابقات صحيحة - تطابقات دقيقة. لذا فإن الدقة تدور حول الإيجابيات الخاطئة.

تذكر من ناحية أخرى "كم عدد التطابقات التي كان يجب العثور عليها ، ولكن تم تفويتها". لذلك تذكر حول السلبيات الكاذبة.

كانت أول محاولة تافهة ، كما هو متوقع ، عالية الدقة ولكن منخفضة في الاستدعاء. إذا نظرنا إلى قائمة مختصرة من الشركات على سبيل المثال ، فسوف يتطابق ذلك مع عناصر الصفر من أ إلى ب. وهذا أمر ضعيف للغاية ، ولكن بدقة 100 ٪ ؛-). بالطبع في سيناريو العالم الواقعي ، سيتطابق الأمر قليلاً مع الصفر ، لكن من السهل أن نرى أنه نظرًا لوجود العديد من الاختلافات الصغيرة الممكنة في أسماء الشركات ، ستظل منخفضة.

تحسين بسيط لذلك سيكون إزالة كلمات التوقف.

كلمات التوقف

ما هي كلمات التوقف؟ كلمات الإيقاف هي الكلمات التي تتم إزالتها قبل إجراء العديد من خوارزميات البرمجة اللغوية العصبية NLP لأنها لا تضيف معلومات ، وعادة ما تضيف ضوضاء فقط. في الكلمات الإنجليزية العادية عادةً ما تكون "من" ، "من أجل" إذا "وما إلى ذلك من اللغة ، هذه كلمات شائعة جدًا تستخدم كثيرًا ، ولكن بالنسبة إلى العديد من خوارزميات البرمجة اللغوية العصبية و IR ، فلا تضيف معلومات بعد ذلك. إنهم يصنعون الجمل النحوية الصحيحة ، وفي كثير من الحالات يؤثرون على الدلالات ، ولكن على مستوى العديد من معالجات البرمجة اللغوية العصبية ، التي لا تنظر إلى بناء الجملة الفعلي ، فهي بلا معنى.

في حالتنا ، لا تكون كلمات الإيقاف هي "if" أو "of" أو "for" ، وهي نموذجية باللغة الإنجليزية ، ولكنها "inc" و "llc" من امتداد الشركة. لذا فإن تحسيننا البسيط هو إزالة كل امتدادات الشركة هذه وتجربة معادلة السلسلة البسيطة مرة أخرى.

لقد ساعد هذا بالفعل ، وكما ترون في مثالنا ، ساعد هذا في مطابقة "Google inc." مع "Google" ومع إزالة علامات الترقيم البسيطة والرمز الصحيح ، نطابق أيضًا "Google ، inc" مع "Google". لكن هذا لا يزال لا يتوافق مع "مختبرات أمازون" مع "مختبرات" أمازون "مختبرات" ليست كلمة توقف ، بمعنى أنها ليست امتدادًا مشتركًا للشركة. كما اتضح أن "مختبرات Amazon" ليست مجرد مثال عشوائي ، فإن العديد من أسماء الشركات لديها هذه الاختلافات في أسمائها والتي تظهر في مجموعة بيانات واحدة ولكنها لا تظهر في مجموعات بيانات أخرى. الخلاصة: يتعين علينا إيجاد طريقة "لتجاوز ذلك" ، وتجاهل "المعامل" في "مختبرات Amazon".

دعنا نلتقي بالعلم.

العلم

ما نبحثه هنا هو مشكلة مطابقة مستندات N من مستندات القائمة A إلى M في القائمة B ، في علاقة متعددة. لكن خوارزمية المطابقة لدينا يجب أن تكون "ذكية" ، بمعنى أنها تحتاج إلى أن تكون قادرة على التمييز بين "كلمات مهمة" و "كلمات غير مهمة". نحتاج إلى إيجاد طريقة لإخبار الكمبيوتر بأن "المختبرات" في "مختبرات الأمازون" غير مهمة ولكن "الأمازون" مهمة حقًا. وسنعمل أيضًا على ترميز الأسماء في رموز أصغر عن طريق تقسيم المسافات ، وعلامات الترقيم ، إلخ ، بحيث يتم تقسيم "medium.com" إلى "متوسط" و "com".

العلم لانقاذ!

TF-الجيش الإسرائيلي

تحقيقًا لهذه الغاية ، نستخدم مخططًا مشتركًا في نظرية استرجاع المعلومات تسمى TF-IDF. TF-IDF تعني مصطلح "تردد مقلوب". مصطلح التردد يعني ببساطة "عدد المرات التي تظهر فيها هذه الكلمة في هذا المستند" (مستنداتنا هي مجرد أسماء شركات ، لذا فهي "مستندات" قصيرة جدًا). لذلك في حالة "معامل الأمازون" ، لدينا كلمتين فقط في المستند "الأمازون" و "المعامل" وترددهما ببساطة 1 و 1. (إذا بالمناسبة ، اسم الشركة قد حدث للتو ليكون "مختبرات الأمازون" amazon "إذاً ، كان العدد 2 لـ" amazon "و 1 لـ" labs ".) هذا ما يدور حوله TF ، بسيط للغاية: قم بحساب تواتر المصطلحات في المستند.

تردد المستند المقلوب هو الصفقة الحقيقية. يبحث تردد المستند المقلوب في جميع "المستندات" (ويعرف أيضًا باسم corpus وجميع أسماء الشركة) ويختبر عدد مرات ظهور كلمة "labs" في كل منهم. إذا ظهرت كلمة "amazon" في وثيقة واحدة فقط ، فهذا يعني أن "amazon" هي كلمة مهمة ، ولكن إذا ظهرت كلمة "labs" في العديد من المستندات الأخرى (على سبيل المثال ، تستخدم العديد من الشركات كلمة "labs" كجزء من اسم) ثم هذا يعني أن كلمة "مختبرات" ليست ذات أهمية. الجيش الإسرائيلي هو ذلك بالضبط - كم عدد الوثائق التي تظهر بها الكلمة.

TF-IDF هو TF للمصطلح ، مقسومًا على IDF للمصطلح. يوفر مقياسًا جيدًا لمدى أهمية أو مدى أهمية الكلمات في سياق مستندات محددة.

من السهل حساب مصفوفة TF-IDF لمجموعة من المستندات. هناك مكتبات جاهزة تقوم بذلك ، واستخدمنا تطبيق scikit-Learn لذلك.

مصفوفة TF-IDF هي مصفوفة ثنائية الأبعاد تمثل الصفوف فيها المستندات (في حالتنا - أسماء الشركات) وتمثل الأعمدة رموزًا فريدة (أو كلمات). إذا أردنا إنشاء مصفوفة TF-IDF لإحضارنا الصغير من القائمة "أ" ، فسيبدو الأمر كهذا (بعد إزالة الكلمات المتوقفة وعلامات الترقيم وخفض كل شيء):

           | جوجل | متوسطة | كوم | ياهو | الأمازون | مختبرات
-------------------------------------------------- ---------
GOOGLE INC. | 1 0 0 0 0 0
MEDIUM.COM | 0 .77 .63 0 0 0
مختبرات الامازون | 0 0 0 0 .7 .7
جوجل ، وشركة | 1 0 0 0 0 0
Yahoo | 0 0 0 1 0 0
كوم | 0 0 1 0 0 0

إليك الكود:

من sklearn.feature_extraction.text استيراد TfidfVectorizer
matrix = vectorizer.fit_transform (['GOOGLE'، 'MEDIUM.COM'، 'Amazon labs'، 'Google'، 'Yahoo'، 'com'])

المصفوفة التي تم إنشاؤها هي NxM حيث N = عدد الشركات و M = عدد الرموز المميزة الفريدة.

ستلاحظ أننا أضفنا شركة أخرى (مكونة) باسم "com". لقد فعلنا ذلك لإظهار خاصية مهمة لـ TF-IDF. نحن نستخدم TF-IDF من أجل التمييز بين الرموز المهمة وغير المهمة في الوثائق. الرمز المميز في المستند هو رمز لا يظهر في المستند في كثير من الأحيان فحسب ، ولكن هذا نادر أيضًا نسبيًا في المجموعة بأكملها. إذا ظهر المصطلح عدة مرات في المجموعة ، يصبح هذا أقل أهمية لهذا المستند المحدد. أضفنا الشركة المكونة "com" بحيث يصبح "Medium" ضمن "Medium.com" أكثر أهمية. (ستلاحظ أن الوزن "المتوسط" هو .77 بينما الوزن "com" هو .63 ، ويرجع ذلك إلى ظهور "com" في وثيقة أخرى ومن ثم يكون جيش الدفاع الإسرائيلي أقل).

بالطبع في الوضع الواقعي ، كان لديك عشرات أو مئات من أسماء الشركات التي تحمل الرمز المميز "com" أو "labs" ، لذلك سترى فرقًا كبيرًا بين "Medium" و "com" ضمن اسم Medium.com.

جيب التماثل التشابه

الخطوة التالية بعد حساب مصفوفة TF-IDF لكلا الجانبين (كلا القائمتين A و B للشركات) هي مضاعفة المصفوفات.

توفر ضربات المصفوفات تدبيرًا مثيرًا للاهتمام يسمى تشابه جيب التمام. تشابه جيب التمام هو قياس تشابه بسيط يتراوح بين 0 و 1. تشير القيمة 1 إلى عناصر متطابقة ويشير الشكل 0 إلى عناصر مختلفة تمامًا (تمامًا مثل دالة علم التمام جيب التمام). ضرب المصفوفات يوفر تشابه جيب التمام بين كل عنصر في القائمة أ لكل عنصر في القائمة ب. في واقع الأمر ، نقوم بضرب A ب BT (B.transpose) بحيث تناسب الأبعاد. الشيء المثير للاهتمام حول تشابه جيب التمام بين مصفوفات TF-IDF هو أن النتيجة هي مصفوفة تشابه بين كل عنصر في A لكل عنصر في B ، مع مراعاة أهمية الرموز في الأسماء. عادة ما تكون نتيجة> .8 تعني مطابقة صالحة.

لحسن الحظ ، توفر sklearn package python وظيفة محاكاة جيب التمام البسيطة التي تقبل مصففتين وتؤدي إلى تشابه جيب التمام لهاتين. إليك بعض الرموز التجريبية:

من sklearn.feature_extraction.text استيراد TfidfVectorizer
من sklearn.metrics.pairwise استيراد cosine_similarity
a = vectorizer.fit_transform (['aa'، 'bb'، 'aa bb'، 'aa aa bb'])
b = vectorizer.fit_transform (['aa'، 'bb'])
التماثلات = cosine_similarity (a، b)

والنتيجة هي مصفوفة التشابه بين كل عنصر في A لكل عنصر في b.

           أأ | ب
----------------------
أأ | 1 | 0
bb | 0 | 1
أ ب ب | .7 | 0.7
أأ ب ب | .89 | 0.44

كما هو متوقع ، فإن كلمة "aa" من a تشبه إلى حد بعيد كلمة "aa" من b (لاحظ 1). يمكنك أيضًا أن ترى أن كلمة "aa bb" مشابهة لكلٍ من "aa" و "bb" وهذا أمر منطقي أيضًا. وأخيرًا ستلاحظ أن كلمة "aa aa bb" تمنع تشابهًا أكبر من كلمة "aa" مقارنةً بـ "bb". كل هذا منطقي.

دعونا نلخص العلم هنا. أولاً ، نأخذ قائمتين من المستندات ولكل مجموعة نحسب مصفوفة TF-IDF *. بعد ذلك نقوم بضرب المصفوفات اثنين للوصول إلى تشابه جيب التمام الخاص بهم ، وهي مصفوفة تصف التشابه بين كل وثيقة في A لكل وثيقة في B.

المحاولة الثانية - الضرب مصفوفة سيئة

بعد أن رأينا العلم ، نريد أن نجرب هذا في الممارسة المحاولة التالية هي تحميل جميع الشركات الحقيقية من القائمة "أ" وتحميل جميع الشركات الحقيقية من القائمة "ب" وضربها باستخدام الدالة cosine_similatiry.

القول اسهل من الفعل.

في نطاق صغير هذا يعمل ببساطة ويعمل بشكل جيد للغاية. على سبيل المثال مع بضعة آلاف من الشركات على كل جانب من شأنها أن تعمل. ولكن مع مجموعة البيانات الخاصة بنا ، التي لدينا فيها مئات الآلاف من الأسماء في كل قائمة ، وحتى بضعة ملايين ، يصبح هذا أمرًا صعبًا.

إن مجرد حساب TF-IDF أمر ممكن ، حتى مع وجود مجموعات البيانات الكبيرة هذه ، على مضيف واحد (يعمل الكمبيوتر المحمول بهذه السهولة ، في بضع ثوان). ومع ذلك ، فإن ضرب المصفوفات هو مكان التحدي الحقيقي.

لا يتم الضرب المحلي

دعنا نفترض أن لدينا أسماء 1M (10⁶) في كل قائمة. ستكون كل مصفوفة عندئذٍ حوالي 10⁶ × 10⁶ (نظرًا لأن عدد الرموز المميزة الفريدة مشابه لعدد الشركات بسبب تفرد الأسماء). إنشاء مصفوفة 10 × 10⁶ في الذاكرة يعني تعويم 10¹². يستغرق تعويم الثعبان 16 بايت ، لذلك ينتهي بنا إلى 16 * 10¹ بايت ، والذي يترجم إلى ~ 4PT (أربعة بايت) من ذاكرة الوصول العشوائي. هل يمكننا الاحتفاظ بمصفوفة 4PT في الذاكرة؟ حسنا ، بالطبع لا ، على الأقل ليس على جهاز الكمبيوتر المحمول المتهالك. ولكن - هناك خدعة. ليس لدينا لحفظ كل شيء في الذاكرة. ضع في اعتبارك أنه على الرغم من أن المصفوفة هي 1M على 1M ، إلا أنها في الواقع العملي مليئة بالأصفار. لذلك ، لماذا يجب علينا عناء الحفاظ على كل هذه الأصفار في الذاكرة؟ يمكننا بدلاً من ذلك استخدام تمثيل متفرق للمصفوفة ، حيث بدلاً من الاحتفاظ بالمصفوفة ثنائية الأبعاد في الذاكرة باستخدام صفائف المصفوفات ، يمكننا بدلاً من ذلك فقط تتبع إحداثيات العناصر غير الصفرية ونفترض أن كل الباقي فقط الأصفار. هذا أمر رائع للمحافظة على انخفاض مساحة الذاكرة وكذلك تنفيذ عمليات الضرب السريع للمصفوفة. وفي الحقيقة ، هذا بالضبط ما يفعله sklearn بالفعل. الإبقاء على المصفوفات كما لو كانت Sparse Matrices يعني أنه يتعين علينا فقط تخصيص حوالي 1 مليون عائم (قيم) ، بالإضافة إلى أعداد صحيحة 2M (مؤشرات العناصر غير الصفرية) ، ولكن كل ذلك في حدود 24 ميغابايت ، وهو أمر سهل للغاية.

ولكن - ضرب المصفوفات اثنين ، حتى لو كانت متناثرة ، سيعني على الأقل 10 operations عمليات العمليات (إذا كنا أذكياء مع الأصفار). الآن هذا هو أصعب قليلا. وعلى الرغم من أن numpy (الذي يقع تحت sklearn) جيد جدًا في مثل هذه الرياضيات السريعة ، إلا أن هذا الشيء يمثل تحديًا كبيرًا حتى بالنسبة إلى numpy.

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

المحاولة الثالثة - مضاعفة شرارة الضرب

تعتبر Spark رائعة بالنسبة للحسابات التي تتطلب ذاكرة متوازية للغاية ولها ، لها نوع بيانات BlockMatrix الذي ينفذ عملية مضاعفة. يبدو بالضبط ما كنا نبحث عنه! حسنًا ، لذلك ننشئ مصفوفات TF-IDF ونحولها إلى Spark’s BlockMatrix ونشغل a.multiply (b.transpose ()) وهو ما يفعله cosine_similatiry بشكل أو بآخر.

# الرمز البريدي ...
a_mat = tfidf_vect.fit_transform ([...، ...، ...])
b_mat = tfidf_vect.fit_transform ([...، ...، ...])
a_block_mat = create_block_matrix (a)
b_block_mat_tr = create_block_matrix (b.transpose ())
القيم الصرفية = a_block_mat.multiply (b_block_mat_tr)

هذا يبدو سهلا بما فيه الكفاية ، وهذا هو حقا. ولكن هناك "ولكن" بالطبع ... هذا الشيء ، على الرغم من أنه بسيط ويعمل بشكل صحيح من وجهة نظر الرياضيات - حسنًا ، لا يتغير حجمه ... نحن قادرون على مضاعفة المصفوفات الكبيرة ، ولكن ليست كبيرة كما نود . لقد حاولنا اللعب بأحجام الكتل وما إلى ذلك للأسف ، لقد فشل في مدخلات كبيرة بما فيه الكفاية مع وجود أخطاء خارج الذاكرة أو فترات طويلة لا تنتهي أبدًا (ساعات وساعات).

ما هي المشكلة؟ لا يمكن شرارة النطاق؟

بالطبع يمكن شرارة النطاق. لكن عليك أن تستخدمه بحكمة ، يا غبي ... المشكلة في BlockMatrix هي أنه من أجل تنفيذ عملية الضرب المتعدد ، يحول Spark الكتل المتفرقة للمصفوفة إلى مصفوفات كثيفة (فرعية). وعلى الرغم من أن معظم مصفوفة لدينا هي الأصفار ، إلا أن الشرارة ستحول كل هذه الأصفار إلى تمثيل كثيف ، إما أن تستهلك الكثير من الذاكرة ، أو إذا حافظنا على حجم الكتل صغيرة ، فسيؤدي ذلك إلى الكثير من العمليات ، وإعادة تقسيم الخ. إلى الأبد.

يدعم Spark المصفوفات المتناثرة ، لكن هذه المصفوفات لا تنفذ عملية الضرب (ويعرف أيضًا باسم dot) ، والمصفوفة الموزعة الوحيدة التي تنفذ عملية الضرب اعتبارًا من وقت الكتابة هي BlockMatrix ، والتي تعمل على تحويل التمثيل المتناثر إلى تمثيل كثيف قبل ضربهم. يجب أن نلاحظ أنه كانت هناك مناقشات في مجتمع الشرارة حول طرق تنفيذ ضرب المصفوفة المتناثرة الموزعة ، ولكن كما لوحظ - في وقت كتابة هذا التقرير ، لم يتم تنفيذ هذا بعد.

فشل BlockMatrix.multiply (). ماذا بعد؟

المحاولة الرابعة - والفائز هو ...

كانت محاولتنا الرابعة والأخيرة ناجحة. والفكرة هي أن تخلط وتناسب شرارة مع numpy. تُظهر اختباراتنا أن numpy قادر على ضرب مصفوفة أصغر بمصفوفة أكبر ، لذلك إذا أخذنا جزءًا صغيرًا فقط من المصفوفة A وضربنا في المصفوفة B ، فإن ذلك سوف ينجح ولن ينفجر numpy. وإذا كنت تتذكر دروس الجبر الخاصة بك ، فيمكن إجراء مصفوفات مضاعفة متجهًا تلو الآخر بحيث تكون صحيحة من الناحية الجبرية التي لا تزال صحيحة. تتمثل الفكرة في تقسيم واحد فقط من المصفوفات إلى قطع أصغر ، ثم جعل كل عامل في Spark يدير الضرب على قسمه ، ثم يعيد النتيجة فقط ، على سبيل المثال قد يكون الاستنتاج هو أن الاسم في A [13] يطابق الاسم في B [21] وما إلى ذلك.

البث والتوازي لإنقاذ

لدى سبارك قدرتين مفيدتين: البث والتوازي. يبث البث ببساطة نفس البيانات بالضبط لجميع العمال. نحن نستخدم البث لإرسال المصفوفة B إلى جميع العمال حتى يكون لدى جميع العمال المصفوفة B الكاملة. الموازي قطع البيانات إلى أقسام ويرسل كل قسم إلى عامل مختلف. نستخدم التوازي لإرسال قطع A إلى العمال بحيث يكون لكل عامل كل من B ولكن جزء صغير من A.

إليك المخطط العام:

  1. حساب مصفوفات TF-IDF على السائق.
  2. موازية المصفوفة A ؛ مصفوفة البث B
  3. يقوم كل عامل الآن بمسح جزء العمل الخاص به عن طريق ضرب جزء المصفوفة A بكامل المصفوفة B. لذا إذا كان العامل يعمل على A [0:99] فسوف يضاعف هذه المئات من الصفوف ويعيد النتيجة ، على سبيل المثال A [13] ] يطابق اسم موجود في B [21]. يتم الضرب باستخدام numpy.
  4. سيقوم السائق بجمع جميع النتائج من مختلف العمال ومطابقة المؤشرات (A [13] و B [21]) مع الأسماء الفعلية في مجموعة البيانات الأصلية - وقد انتهينا!

تعمل هذه الطريقة بشكل جيد للغاية ، وفي الواقع عندما كانت تعمل لأول مرة ، كانت مفاجأة رائعة لدرجة أننا اعتقدنا أنها لم تنجح (ولكنها كانت تعمل ...). مقارنة بالطرق السابقة ، والتي إما ركضت لساعات (ولم تنتهِ) أو نفدت أو الذاكرة ، كانت هذه الطريقة قادرة على إكمال حسابها من أجل بضع دقائق فقط. بالطبع ، يعتمد ذلك على حجم البيانات وحجم مجموعة Spark ، ولكن بشكل عام كان أداءها جيدًا.

في الوقت الحالي ، فإن عنق الزجاجة هو برنامج التشغيل الذي يقوم بحساب مصفوفات TF-IDF ، وعلى هذه الجبهة لا يزال لدينا الكثير من مساحة الكوع لأن هذا الحساب لا يزال سهلاً للغاية على sklearn. (ملاحظة جانبية: تنفذ Spark أيضًا حسابات TF-IDF الموزعة ولكن لم يكن علينا استخدامها).

إليك الرمز الكاذب لتوضيح حلنا:

من sklearn.feature_extraction.text استيراد TfidfVectorizer
من sklearn.feature_extraction.text استيراد CountVectorizer
من sklearn.metrics.pairwise استيراد cosine_similarity
# هذه سوف تحصل على قراءة واقعية من الملفات أو قواعد البيانات.
a = ['google inc'، 'medium.com'، ...]
b = ['google' ، 'microsoft' ، ...]
كلمات التوقف = ['ltd'، ...]
vect = CountVectorizer (stop_words = كلمات التوقف)
# يمكن القيام بذلك باستخدام مقدار أقل من الذاكرة باستخدام مولد
المفردات = vect.fit (a + b) .vocabulary_
tfidf_vect = TfidfVectorizer (stop_words = كلمات التوقف ،
                             المفردات = المفردات)
a_mat = tfidf_vect.fit_transform (a)
b_mat = tfidf_vect.fit_transform (b)
a_mat_para = parallelize_matrix (a_mat، rows_per_chunk = 100)
b_mat_dist = broadcast_matrix (a_mat)
a_mat_para.flatMap (
        اللمبة الفرعية:
        find_matches_in_submatrix (csr_matrix (submatrix [1]،
                                             شكل = submatrix [2])،
                                   b_mat_dist،
                                   submatrix [0]))
def find_matches_in_submatrix (المصادر ، الأهداف ، inputs_start_index ،
                              عتبة = 0.8):
    تماثلات = تماثل جيب التمام (المصادر والأهداف)
    بالنسبة لي ، التواطؤ في التعداد (التداخل):
        cosimilarity = cosimilarity.flatten ()
        # ابحث عن أفضل تطابق باستخدام argsort () [- 1]
        target_index = cosimilarity.argsort () [- 1]
        source_index = inputs_start_index + i
        التشابه = التشابه [target_index]
        إذا كان التفضيل [target_index]> = العتبة:
            العائد (source_index ، target_index ، التشابه)
def بث_المصفوفة (حصيرة):
    bcast = sc.broadcast ((mat.data ، mat.indices ، mat.indptr))
    (البيانات ، المؤشرات ، indptr) = bcast.value
    bcast_mat = csr_matrix ((البيانات ، المؤشرات ، indptr) ، الشكل = mat.shape)
    العودة bcast_mat
def parallelize_matrix (scipy_mat، rows_per_chunk = 100):
    [الصفوف ، cols] = scipy_mat.shape
    أنا = 0
    الغواصات = []
    بينما أنا <الصفوف:
        current_chunk_size = min (rows_per_chunk ، الصفوف - i)
        submat = scipy_mat [i: i + current_chunk_size]
        submatrices.append ((i، (submat.data، submat.indices،
                                submat.indptr)،
                            (current_chunk_size ، cols)))
        i + = current_chunk_size
    إرجاع sc.parallelize (الغواصات)

ستلاحظ أنه بعد البث والتوازي ، نعيد تجميع المصفوفة في csr_matrix scipy ، وهو ما نشأت منه. إذن ما نقوم به بشكل أساسي هو - تسلسل المصفوفات عبر السلك ومن ثم إعادة تجميعها على الجانب الآخر ، على العمال. تكون عملية التسلسل فعالة لأننا نحتاج فقط إلى إرسال العناصر غير الصفرية في المصفوفة المتفرق. لذلك بالنسبة لمصفوفة من عناصر 1M ، نرسل فقط حوالي 1M من العوامات ، جنبًا إلى جنب مع 2M intts ، والتي هي بالتأكيد في منطقة الراحة من Spark.

استنتاج

نحن نصف طريقة للعثور على التشابه بين قائمتين من السلاسل A و B تصفان أسماء الشركات. استخدمنا TF-IDF وجيب التماثل كعامل تشابه.

نعرض بعد ذلك العديد من المحاولات للتنفيذ القابل للتوسيع لمضاعفة المصفوفة باستخدام الشرارة ، وطريقة الفوز التي تجمع بين ضرب المصفوفة غير المؤكدة جنبًا إلى جنب مع قدرات الشرارة وموازنتها.

* هناك نقطة واحدة يجب ذكرها: يجب أن تكون مفردات المصفوفتين هي نفسها. بمعنى آخر ، يجب أن يكون عدد الصفوف في كلا المصفوفتين متساوين ويجب أن يكون لهما نفس الترتيب تمامًا ، على سبيل المثال يمثل كل صف مصطلحًا ويجب أن يكون ترتيب الصفوف هو نفسه تمامًا بين المصفوفة A والمصفوفة B. ويتم ذلك بسهولة عن طريق حساب المفردات أولاً ثم حساب TF-IDF فقط كما في المثال التالي:

من sklearn.feature_extraction.text استيراد TfidfVectorizer
من sklearn.feature_extraction.text استيراد CountVectorizer
من sklearn.metrics.pairwise استيراد cosine_similarity
a = ['google inc'، 'medium.com']
b = ['google' ، 'microsoft']
company_name_stopwords = frozenset (['ltd'، 'llc'، 'inc'])
vect = CountVectorizer (stop_words = company_name_stopwords)
المفردات = vect.fit (a + b) .vocabulary_
tfidf_vect = TfidfVectorizer (stop_words = company_name_stopwords ،
                             المفردات = المفردات)
a_mat = tfidf_vect.fit_transform (a)
b_mat = tfidf_vect.fit_transform (b)
التماثلات = cosine_similarity (a_mat، b_mat)