Proposal and study of statistical features for string similarity computation and classification

ملخص تقني: مقترح ودراسة السمات الإحصائية لحساب تشابه النصوص وتصنيفها

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

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

1. السمات الإحصائية المقترحة:

• المعلومات المتبادلة الموزونة (WMI): وهي تكييف للمعلومات المتبادلة القياسية (MI) التي تتضمن عامل وزن ($m > 1$) وتأخذ ترتيب الحروف في الاعتبار. وتتضمن عملية إزاحة (shift) لمراعاة مسافات الإزاحة، مما يميز بين النصوص التي هي مجرد تبديلات لبعضها البعض مقابل النصوص المتطابقة.
• سمات مصفوفة التواجد المشترك (COM): مكيّفة من معالجة الصور، وتقوم هذه المصفوفات بعدّ التواجد المشترك للحروف المتطابقة عند مسافات محددة بين نصين. وتشمل السمات المستمدة منها: احتمالية التواجد المشترك (COP)، ودرجة الاحتمالية (PS)، وإجمالي درجة الاحتمالية (TPS)، وتوزيع التواجد المشترك (CODs).
• سمات مصفوفة طول التشغيل (RLM): تعتمد على ترميز طول التشغيل، وتقوم هذه السمات بعدّ حالات تكرار أطوال تسلسلات محددة من النص الأول ($w_1$) داخل النص الثاني ($w_2$). وتشمل السمات المستمدة منها: مجموع التكرارات (SO)، ومجموع التكرارات الموزون (WSO)، والحد الأقصى للتكرار (MO)، والحد الأقصى لطول التشغيل المتكرر (MORL)، ومتغير الحد الأقصى المتتالي لأطول سلسلة فرعية مشتركة (RLMMCLCS).

2. المقارنات المرجعية:
تتم مقارنة السمات المقترحة مع المقاييس الإحصائية الراسخة، بما في ذلك:

• أطول سلسلة فرعية مشتركة (LCS) و(LCS) المعياري.
• الحد الأقصى المتتالي لأطول سلسلة فرعية مشتركة (MCLCS).
• المعلومات المتبادلة القياسية (MI).
• مسافات التحرير: هامينج (المعدل)، ليفنشتاين، وداميراو-ليفنشتاين.
• معامل دايس (Dice coefficient).

3. الإعداد التجريبي:

• مجموعات البيانات الاصطناعية: تم إجراء مجموعتين من التجارب باستخدام نصوص مولدة.
  • مقارنة الكلمات: نصوص تصل إلى 14 حرفًا مع درجات متفاوتة من العشوائية ($R=0.5, 0.9$).
  • مقارنة الجمل: نصوص تصل إلى 200 حرف مع عشوائية منخفضة ($R=0$) ومتوسطة ($R=0.15$).
  • كانت التصنيفات ثنائية: "متطابق" (نسخة معدلة من النص الأول) أو "مختلف" (مولد عشوائيًا).
• مجموعة بيانات من العالم الحقيقي: تم استخدام مجموعة بيانات ويكيبيديا الخاصة بالانتحال (Clough and Stevenson, 2011) لمشكلة تصنيف متعدد الفئات تتضمن أربعة مستويات: نسخ قريب، تنقيح خفيف، تنقيح ثقيل، وعدم انتحال.
• المصنفات: تم اختبار مجموعة متنوعة من الخوارزميات، بما في ذلك LMT (أشجار النموذج اللوجستي)، والغابة العشوائية (Random Forest)، وأشجار REP، والبيرسيبترون متعدد الطبقات (MLP)، وخوارزمية k-NN، ونايف بايز (Naive Bayes)، باستخدام برنامج Weka.

النتائج الرئيسية

• التجارب الاصطناعية:

  • في 3 من أصل 4 سيناريوهات اصطناعية، تفوقت سمات RLM وCOM المقترحة إحصائيًا على السمات القائمة على المسافة والمتطورة (P-value < 0.001).
  • حققت سمات COM أفضل أداء عندما كانت العشوائية منخفضة إلى متوسطة (مثل $R=0.5$ للنصوص القصيرة)، محققة أعلى دقة فردية (86.78% باستخدام LMT).
  • أظهرت سمات RLM قدرة فائقة على الصمود في سيناريوهات العشوائية العالية والنصوص الطويلة (مثل $R=0.15$ للنصوص بطول 200 حرف)، متفوقة بشكل كبير على مجموعات المسافات.
  • أظهرت المعلومات المتبادلة القياسية (MI) والسمات القائمة على الطول ضعفًا مستمرًا في الأداء.
  • كان LMT هو المصنف الأكثر دقة بشكل عام، رغم أنه يتطلب وقت تدريب كبير. بينما كان k-NN الأسرع في "توليد" النموذج (لأنه مصنف كسول/lazy)، إلا أنه كان الأبطأ في وقت التصنيف.

• كشف الانتحال:

  • باستخدام مجموعة بيانات ويكيبيديا، حققت المنهجية المقترحة دقة بلغت 84.21% باستخدام مصنف التصويت التجميعي (Vote classifier ensemble).
  • تجاوزت هذه النتيجة الأعمال السابقة على نفس مجموعة البيانات (Clough and Stevenson: 66.31% بناءً على مصفوفة الارتباك الخاصة بهم؛ وChong et al.: 70.52%).
  • أشار ترتيب السمات إلى أن السمات المشتقة من RLM (تحديدًا MORL وRLMMCLCS) كانت أكثر المتنبئات قيمة لهذه المهمة.

الأهمية والادعاءات
تدعي الورقة أن تكييف مصفوفات الحوسبة المرئية (COM وRLM) لتمثيل تشابه النصوص يوفر بديلًا قويًا ومستقلاً عن اللغة لمسافات التحرير التقليدية والمقاييس الدلالية.

• الاستقلالية اللغوية: تعتمد السمات المقترحة كليًا على الأنماط الإحصائية، مما يجعلها قابلة للتطبيق على أي لغة دون الحاجة إلى قواميس أو تصنيفات.
• القدرة على الصمود أمام العشوائية: توضح الدراسة أنه بينما تعمل الطرق القائمة على المسافة بشكل جيد للتغييرات الطفيفة، فإن سمات RLM فعالة بشكل خاص للنصوص الطويلة ودرجات العشوائية العالية، مما يحاكي سيناريوهات الانتحال في العالم الحقيقي.
• الكفاءة: بينما يتطلب استخراج السمات لـ COM وRLM بناء مصفوفة، فإن استخراج سمات متعددة من مصفوفة واحدة يعد أمرًا فعالًا حوسبيًا.
• الإمكانات المستقبلية: يشير المؤلفون بتواضع إلى أن الإمكانات الكاملة لـ COM وRLM في تشابه النصوص لم تُستغل بالكامل بعد، مما يشير إلى أن هندسة السمات المستندة إلى هذه المصفوفات تعد اتجاهًا واعدًا للعمل المستقبلي.

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