من الجحيم إلى النعيم: كيف أنقذتنا خوارزمية LSH من “لعنة الأبعاد” في نظام التوصيات؟

يا أهلاً وسهلاً فيكم، معكم أبو عمر.

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

أتذكر مدير المشروع دخل علينا المكتب ومعالم وجهه لا تبشر بالخير أبداً، وقال بنبرة جادة: “يا جماعة، شو القصة؟ التوصيات بطيئة جداً، والزبائن بشتكوا إنها مش دقيقة بالمرة! الموقع صاير بطيء كأنه ماشي على رجل واحدة”.

كانت ضربة في الصميم. كنا نستخدم خوارزمية الجار الأقرب (k-NN) التقليدية. الفكرة بسيطة: عشان نلاقي منتجات شبيهة بمنتج معين، كنا نحسب “مسافة التشابه” بين هذا المنتج وكل منتج آخر في قاعدة البيانات اللي كان فيها مئات الآلاف من المنتجات. كل منتج ممثّل بـ “متّجه” (vector) طويل فيه مئات الخصائص (الأبعاد): السعر، اللون، الفئة، كلمات من الوصف، إلخ. الحسبة هاي كانت بتاخد ثوانٍ طويلة، وهذا في عالم الإنترنت يعني الأبدية. كنا حرفيًا في جحيم “لعنة الأبعاد”، وما كنا عارفين المخرج.

ما هي “لعنة الأبعاد” ولماذا كانت كابوسنا؟

خليني أبسّط لكم الموضوع. تخيل إنك تبحث عن صديقك في شارع مستقيم (بعد واحد). الأمر سهل. الآن تخيل أنك تبحث عنه في ساحة كبيرة (بعدين). أصعب شوي، صح؟ طيب، تخيل أنك تبحث عنه في مبنى ضخم متعدد الطوابق (ثلاثة أبعاد). أصعب بكثير.

“لعنة الأبعاد” (Curse of Dimensionality) هي اللي بصير لما توصل لمئات أو آلاف الأبعاد. في هاي الفضاءات عالية الأبعاد، كل شيء بصير بعيد عن كل شيء آخر. المسافات بين النقاط (المنتجات في حالتنا) بتصير شبه متساوية، ومفهوم “الجار الأقرب” بفقد معناه. كأنك بتبحث عن صديقك في مجرة كاملة، كل النجوم بعيدة عنك بنفس القدر تقريبًا!

تقنيًا، كانت المشكلة إن عملية المقارنة بين منتج وكل المنتجات الأخرى (تعقيد زمني O(N*D) حيث N عدد المنتجات و D عدد الأبعاد) مستحيلة في الوقت الفعلي. النظام كان يختنق، والمستخدمون كانوا يهربون، ونحن كفريق كنا محبطين لأبعد حد.

الفارس الذي أنقذ الموقف: خوارزمية التجزئة الحساسة للمكان (LSH)

وسط هذا الإحباط، وبعد ليالٍ طويلة من البحث والقهوة، لمع في بالي حل كنا قد درسناه في الجامعة بشكل نظري: التجزئة الحساسة للمكان (Locality-Sensitive Hashing – LSH).

فكرة LSH عبقرية في بساطتها. هي عكس التجزئة (Hashing) التقليدية اللي بنعرفها. في التجزئة التقليدية (مثل SHA-256)، أي تغيير بسيط في المدخلات يؤدي إلى تغيير هائل في المخرجات. أما LSH، فتقوم على مبدأ معاكس تمامًا: النقاط القريبة من بعضها في الفضاء متعدد الأبعاد، يجب أن تقع في نفس “الدلو” (Bucket) بعد عملية التجزئة باحتمالية عالية.

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

كيف تعمل LSH من الداخل؟ (مثال مع تشابه جيب التمام)

واحدة من أشهر عائلات LSH هي التي تعتمد على “الإسقاط العشوائي” (Random Projection) وهي مناسبة جدًا لحساب تشابه جيب التمام (Cosine Similarity)، وهو ما كنا نستخدمه. إليكم الفكرة خطوة بخطوة:

1. إنشاء مستويات فائقة عشوائية: في الفضاء ثنائي الأبعاد، يمكننا رسم خط عشوائي يقسم الفضاء إلى نصفين. في الفضاء ثلاثي الأبعاد، نرسم مستوى (plane) عشوائي. في الفضاء عالي الأبعاد، هذا يسمى “مستوى فائق” (hyperplane). نقوم بإنشاء عدة مستويات من هذا النوع بشكل عشوائي.
2. توليد البصمة (Hash): لكل منتج (متّجه)، نرى على أي جانب من كل مستوى فائق يقع. إذا كان على جانب معين نعطيه “1”، وعلى الجانب الآخر نعطيه “0”.
3. تكوين الدلو: إذا استخدمنا 4 مستويات فائقة عشوائية، فسيحصل كل منتج على بصمة مكونة من 4 أرقام (مثلاً: 1011). جميع المنتجات التي لها نفس البصمة “1011” توضع في نفس الدلو.

الجميل في الأمر أن المنتجات المتشابهة جدًا (الزاوية بين المتجهات الخاصة بها صغيرة) ستقع على الأرجح في نفس الجانب من معظم المستويات الفائقة العشوائية، وبالتالي ستحصل على نفس البصمة وتقع في نفس الدلو!

من النظرية إلى التطبيق: مثال بالكود

للتوضيح، دعونا نرى كيف يمكننا تطبيق الفكرة الأساسية باستخدام Python و `numpy`. هذا الكود ليس مكتبة LSH جاهزة، ولكنه يوضح المبدأ الأساسي.

import numpy as np

def get_lsh_hash(vector, planes):
    """
    يحسب بصمة LSH لمتجه واحد بناءً على مجموعة من المستويات.
    """
    # np.dot(planes, vector) > 0  يعطينا True/False لكل مستوى
    # .astype(int) تحول True/False إلى 1/0
    hash_code = (np.dot(planes, vector) > 0).astype(int)
    # نحول سلسلة الأرقام إلى سلسلة نصية لتكون مفتاحًا للدلو
    return "".join(map(str, hash_code))

# --- الإعداد ---
num_dimensions = 128  # عدد أبعاد المتجهات (خصائص المنتجات)
num_hashes = 8        # عدد المستويات الفائقة (طول البصمة)
num_items = 1000      # عدد المنتجات في قاعدة البيانات

# إنشاء بيانات عشوائية (1000 منتج، كل منها 128 بُعدًا)
np.random.seed(42)
items = np.random.randn(num_items, num_dimensions)

# إنشاء المستويات الفائقة العشوائية
# كل مستوى هو متجه عشوائي بنفس عدد الأبعاد
random_planes = np.random.randn(num_hashes, num_dimensions)

# --- بناء الدلاء (Buckets) ---
buckets = {}
for i, item_vector in enumerate(items):
    h = get_lsh_hash(item_vector, random_planes)
    if h not in buckets:
        buckets[h] = []
    buckets[h].append(i) # نخزن فهرس المنتج

# --- الاختبار ---
# لنأخذ منتجًا عشوائيًا كاستعلام (query)
query_index = 0
query_vector = items[query_index]

# 1. البحث بالطريقة البطيئة (Brute-force)
# حساب التشابه مع كل المنتجات الأخرى
similarities = np.dot(items, query_vector) / (np.linalg.norm(items, axis=1) * np.linalg.norm(query_vector))
# الحصول على ثاني أعلى تشابه (الأول هو المنتج نفسه)
top_brute_force_neighbor = np.argsort(similarities)[-2]
print(f"الجار الأقرب بالطريقة البطيئة: المنتج رقم {top_brute_force_neighbor}")

# 2. البحث باستخدام LSH (الطريقة السريعة)
query_hash = get_lsh_hash(query_vector, random_planes)
candidate_indices = buckets.get(query_hash, [])
print(f"وجدنا {len(candidate_indices)} مرشحًا في نفس الدلو.")

if candidate_indices:
    # الآن نحسب التشابه فقط مع المرشحين
    candidate_vectors = items[candidate_indices]
    candidate_similarities = np.dot(candidate_vectors, query_vector) / (np.linalg.norm(candidate_vectors, axis=1) * np.linalg.norm(query_vector))
    
    # استبعاد المنتج نفسه إذا كان في القائمة
    # ثم نجد أفضل مرشح
    best_candidate_local_index = np.argsort(candidate_similarities)[-1] # قد يكون هو نفسه
    if candidate_indices[best_candidate_local_index] == query_index and len(candidate_similarities) > 1:
        best_candidate_local_index = np.argsort(candidate_similarities)[-2]
    
    top_lsh_neighbor = candidate_indices[best_candidate_local_index]
    print(f"الجار الأقرب بطريقة LSH: المنتج رقم {top_lsh_neighbor}")

هذا المثال يبسط الفكرة، لكنه يوضح كيف انتقلنا من مقارنة 1000 منتج إلى مقارنة عدد قليل جدًا من “المرشحين” الموجودين في نفس الدلو.

إعادة بناء نظام التوصيات باستخدام LSH

بمجرد أن فهمنا قوة LSH، تغيرت استراتيجيتنا بالكامل. أصبح سير العمل الجديد كالتالي:

1. المرحلة غير المتصلة (Offline Indexing): مرة كل ليلة، نقوم بتشغيل عملية تأخذ جميع متجهات المنتجات لدينا، وتمررها عبر خوارزمية LSH، وتخزنها في “دلاء” (Hash Buckets). هذه العملية تستغرق وقتًا، لكنها لا تؤثر على المستخدمين لأنها تحدث في الخلفية.
2. المرحلة المتصلة (Online Querying): عندما يزور مستخدم صفحة منتج ما، يحدث التالي في أجزاء من الثانية:
   • نأخذ متجه المنتج الحالي (الاستعلام).
   • نحسب بصمة LSH الخاصة به بسرعة فائقة.
   • بدلاً من مقارنته بمئات الآلاف من المنتجات، نبحث فقط في الدلو الذي يحمل نفس البصمة. قد يحتوي هذا الدلو على 100 أو 200 منتج بدلاً من 500,000!
   • الآن فقط، نقوم بحساب التشابه الدقيق (Cosine Similarity) على هذه المجموعة الصغيرة من “المرشحين”.
   • نعرض أفضل 5 أو 10 نتائج للمستخدم.

النتيجة؟ زمن الاستجابة انخفض من 3-4 ثوانٍ إلى أقل من 50 ميلي ثانية. كانت نقلة نوعية. صحيح أن LSH خوارزمية تقريبية (Approximate)، مما يعني أننا قد نفوت بعض الجيران الأقرب أحيانًا، لكن في المقابل حصلنا على سرعة هائلة، وكانت النتائج جيدة بما يكفي بنسبة 99% لدرجة أن المستخدمين لم يلاحظوا أي فرق سوى السرعة والتحسن العام في جودة التوصيات.

نصائح من “أبو عمر” لتطبيق LSH بنجاح

من خلال تجربتي، تعلمت بعض الدروس التي أود مشاركتها معكم:

وازن بهاراتك جيدًا!

أهم شيء في LSH هو ضبط المتغيرات، خصوصًا عدد جداول التجزئة (L) وعدد دوال التجزئة لكل جدول (k). زيادة عدد الجداول (L) تزيد من فرصة العثور على الجيران (Recall)، بينما زيادة عدد الدوال (k) تجعل البحث أكثر دقة وتقلل عدد المرشحين (Precision). الأمر أشبه بطبخة المقلوبة، بدك توازن البهارات صح عشان تطلع الطبخة ممتازة.

اختر عائلة LSH المناسبة

ما شرحته هو LSH لتشابه جيب التمام. لكن هناك عائلات أخرى من LSH. مثلاً، إذا كنت تقارن بين مجموعات من الكلمات (مثل تشابه المقالات)، فإن MinHash مع مسافة Jaccard هو الخيار الأفضل. اعرف بياناتك ومقياس التشابه الذي تحتاجه أولاً.

لا تعيد اختراع العجلة

الكود الذي كتبته كان للتوضيح فقط. في العالم الحقيقي، استخدم مكتبات جاهزة ومحسّنة لأبعد الحدود. من أشهرها:

• Faiss: مكتبة من فيسبوك، قوية جدًا وسريعة بشكل لا يصدق، ومكتوبة بـ C++ مع واجهات Python.
• Annoy: مكتبة من سبوتيفاي، سهلة الاستخدام وممتازة للعديد من التطبيقات.
• ScaNN: مكتبة من جوجل، تقدم أداءً متطورًا جدًا في هذا المجال.

LSH للترشيح، وليس للترتيب النهائي

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

الخلاصة: من لعنة الأبعاد إلى نعمة التقريب 💡

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

إذا كنت تواجه مشاكل في البحث عن التشابه، أو توصية المنتجات، أو إزالة البيانات المكررة على نطاق واسع، فأنصحك بشدة أن تنظر إلى LSH. قد تكون هي الفارس الذي سينقذك من جحيم لعنة الأبعاد.

تذكر دائمًا، ما في مشكلة ما إلها حل، بس بدها شوية صبر وفنجان قهوة… وفهم للخوارزميات الصح. بالتوفيق يا جماعة! 🚀