يا أهلاً وسهلاً فيكم يا جماعة. اسمي أبو عمر، مبرمج فلسطيني قضيت سنين عمري بين الأكواد والخوارزميات، وشفت العجب العجاب في عالم الذكاء الاصطناعي. اليوم بدي أحكيلكم قصة صارت معي ومع فريقي قبل كم سنة، قصة فيها معاناة وإحباط، بس نهايتها كانت بصراحة… بتفرّح القلب.
كنا شغالين على نظام توصيات لمتجر إلكتروني كبير. الفكرة كانت بسيطة: لما المستخدم يشوف منتج معين، نعرضله منتجات “شبيهة” إله. “الشبه” هذا كنا بنقيسه بناءً على مجموعة من الخصائص: السعر، اللون، الفئة، تقييمات المشترين، وغيرها. يعني كل منتج هو عبارة عن نقطة في فضاء متعدد الأبعاد (Multi-dimensional space). مهمتنا كانت بسيطة نظرياً: لكل منتج، ابحث عن “أقرب جار” له في هذا الفضاء، يعني أقرب نقطة.
في البداية، استخدمنا الحل “الأهبل” أو الـ Brute-Force. يعني عشان نلاقي أقرب منتج، كنا نمسك المنتج تبعنا ونحسب المسافة بينه وبين كل المنتجات الثانية في قاعدة البيانات، واحد واحد! وبعدين نختار الأصغر. النظام اشتغل، لكن… يا ويلي شو كان بطيء! مع كل مستخدم جديد وكل منتج جديد، النظام يصير أبطأ وأبطأ. صرنا نحس إنه السيرفرات “بتلطم” من كثر الشغل. قعدنا أيام وليالي نحاول نحسّن الأداء، عملنا Caching، حسّنا استعلامات قاعدة البيانات، بس المشكلة الأساسية كانت في الخوارزمية نفسها. كنا زي اللي بحاول يفرّغ البحر بمعلقة. لحد ما في يوم، وإحنا بنبحث عن حلول، واحد من الشباب صاح: “يا جماعة، شو رأيكم بالـ k-d Trees؟”
ما هو “جحيم البحث الخطي” الذي كنا نعيش فيه؟
قبل ما ندخل في تفاصيل شجرة الخلاص هذه، خلوني أشرحلكم المأساة اللي كنا فيها. الطريقة اللي كنا بنستخدمها اسمها البحث بالقوة الغاشمة أو البحث الخطي (Linear Search).
تخيل عندك قاعة فيها ألف شخص، وبدك تلاقي أقرب شخص واقف جنبك. الطريقة الخطية بتجبرك تعمل التالي:
- تقيس المسافة بينك وبين الشخص الأول. تسجلها كـ “أقرب مسافة حتى الآن”.
- تقيس المسافة بينك وبين الشخص الثاني. إذا كانت أقصر من المسافة المسجلة، بتحدّثها.
- تكرر العملية مع الشخص الثالث، والرابع… حتى الشخص رقم ألف.
هذا بالضبط ما كان يفعله نظامنا. لكل عملية بحث، كان يمسح قاعدة البيانات كلها. هذا يعني أن التعقيد الزمني (Time Complexity) للبحث الواحد هو O(N)، حيث N هو عدد النقاط (المنتجات). ولو عندك مليون منتج، يعني مليون عملية حساب مسافة لكل بحث! كارثة بكل المقاييس.
الخلاص في شجرة: مقدمة إلى أشجار كيه-دي (k-d Trees)
شجرة k-d هي هيكل بيانات (Data Structure) مصمم خصيصاً لتنظيم النقاط في فضاء متعدد الأبعاد (k-dimensional space)، وهدفها الأساسي هو تسريع عمليات البحث مثل البحث عن أقرب جار.
الفكرة عبقرية في بساطتها: بدلاً من النظر إلى كل النقاط، الشجرة تقسم الفضاء بشكل متكرر إلى نصفين، مما يسمح لنا بتجاهل أجزاء كبيرة من البيانات بسرعة فائقة. كأنك بدل ما تبحث في القاعة كلها، بتعرف مباشرة أن صديقك في النصف الأيمن من القاعة، فتتجاهل النصف الأيسر بالكامل.
كيف تُبنى شجرة k-d؟
بناء الشجرة يتم بشكل متكرر (Recursively) وهو قلب الموضوع كله. خلينا نفترض إنه عنا مجموعة نقاط في فضاء ثنائي الأبعاد (x, y) عشان نسهّل الشرح:
- اختيار محور للتقسيم: نبدأ بالمحور الأول (مثلاً، محور x).
- إيجاد الوسيط (Median): نرتب كل النقاط بناءً على قيمتها في محور x، ونختار النقطة الوسيطة (اللي في النص تماماً). هذه النقطة ستكون “عقدة” (node) في الشجرة.
- التقسيم: كل النقاط اللي قيمة x تبعتها أصغر من الوسيط بتروح على “الابن الأيسر” (Left Child)، وكل النقاط اللي قيمتها أكبر بتروح على “الابن الأيمن” (Right Child). هيك بنكون قسمنا الفضاء بخط عمودي.
- التكرار وتغيير المحور: الآن نكرر نفس العملية على الابن الأيسر والأيمن، ولكن هذه المرة نستخدم المحور التالي (محور y). يعني في المستوى الثاني من الشجرة، التقسيم سيكون بخطوط أفقية. في المستوى الثالث، نرجع لمحور x، وهكذا، نستمر في تبديل المحاور مع كل مستوى جديد في الشجرة.
بهذه الطريقة، كل عقدة في الشجرة تمثل “مستطيل” أو “صندوق” في الفضاء، وكلما نزلنا أعمق في الشجرة، صغر حجم هذا الصندوق.
البحث عن أقرب جار: السحر الحقيقي لـ k-d Tree
بناء الشجرة جميل، لكن القوة الحقيقية تظهر في عملية البحث. لما تجينا نقطة جديدة (خلينا نسميها نقطة الاستعلام أو Query Point) وبدنا نلاقي أقرب جار إلها، الخوارزمية بتعمل شغلتين رئيسيتين:
1. رحلة الهبوط في أغصان الشجرة
نبدأ من الجذر (root) وننزل في الشجرة. عند كل عقدة، نقارن إحداثيات نقطة الاستعلام مع إحداثيات العقدة على محور التقسيم الحالي. إذا كانت أصغر، نروح يسار، وإذا أكبر، نروح يمين. نستمر في الهبوط حتى نصل إلى “ورقة” (leaf node). هذه الورقة هي أول تخمين لنا لأقرب جار، ونحسب المسافة بينها وبين نقطة الاستعلام ونسجلها كـ “أفضل مسافة حالية”.
2. العودة للوراء والتحقق الذكي (Backtracking)
وهنا يكمن السحر. بعد ما وصلنا للورقة، نبدأ بالصعود في الشجرة مرة أخرى (Backtracking). عند كل عقدة نمر بها أثناء الصعود، نسأل سؤالين:
- هل هذه العقدة أقرب من “أفضل مسافة حالية”؟ إذا نعم، نحدّث أفضل مسافة ونسجل هذه العقدة كأفضل جار جديد.
- السؤال الأهم: هل يمكن أن يوجد جار أقرب في الفرع الآخر (الفرع الذي لم نزره أثناء الهبوط)؟
للإجابة على السؤال الثاني، نرسم دائرة (أو كرة في أبعاد أعلى) حول نقطة الاستعلام نصف قطرها هو “أفضل مسافة حالية”. ثم نتحقق إذا كانت هذه الدائرة تتقاطع مع “مستطيل” الفرع الآخر. إذا لم تتقاطع، فهذا يعني أنه من المستحيل وجود نقطة أقرب في ذلك الفرع بأكمله، وبالتالي نتجاهله بالكامل! وهذا هو سر السرعة. أما إذا كانت الدائرة تتقاطع، فنحن مضطرون للنزول واستكشاف ذلك الفرع أيضاً.
باستخدام هذه الطريقة، نحن نقصّ ونستبعد أجزاء هائلة من فضاء البحث، بدلاً من فحص كل نقطة بغباء.
مثال عملي بالكود (يا مبرمجين، قرّبوا)
كتابة خوارزمية k-d Tree من الصفر ممتعة كتمارين، لكن في الحياة العملية، “لا تعيد اختراع العجلة”. معظم لغات البرمجة توفر مكتبات جاهزة ومُحسّنة للقيام بذلك. في بايثون، مكتبة scipy هي صديقتنا الصدوقة.
شوفوا ما أبسط الموضوع:
import numpy as np
from scipy.spatial import KDTree
# الخطوة 1: إنشاء بعض البيانات العشوائية (تخيلها منتجات في متجرك)
# 1000 نقطة في فضاء ثنائي الأبعاد (مثلاً: السعر، التقييم)
np.random.seed(42) # لضمان نفس النتائج عند كل تشغيل
data_points = np.random.rand(1000, 2)
# الخطوة 2: بناء شجرة k-d من بياناتنا
# هذه الخطوة تتم مرة واحدة (أو كلما تغيرت البيانات بشكل كبير)
print("يتم بناء شجرة k-d...")
kdtree = KDTree(data_points)
print("تم بناء الشجرة بنجاح!")
# الخطوة 3: الآن، لنبحث عن أقرب جار لنقطة جديدة
query_point = np.array([0.5, 0.5])
# k=1 يعني أننا نريد أقرب جار واحد فقط
# يمكن تغيير k للحصول على أقرب 5 جيران مثلاً
distance, index = kdtree.query(query_point, k=1)
# النتائج
print(f"nنقطة البحث: {query_point}")
print(f"أقرب جار لها هو النقطة رقم: {index}")
print(f"إحداثيات أقرب جار: {data_points[index]}")
print(f"المسافة بينهما: {distance}")
# مقارنة مع البحث الخطي (فقط للتوضيح)
# في التطبيق الحقيقي، لن تفعل هذا أبداً مع بيانات كبيرة
# np.linalg.norm(a - b) هي طريقة لحساب المسافة الإقليدية
distances = np.linalg.norm(data_points - query_point, axis=1)
min_distance_linear = np.min(distances)
min_index_linear = np.argmin(distances)
print("n--- مقارنة مع البحث الخطي ---")
print(f"أقرب جار (خطي): {data_points[min_index_linear]}")
print(f"المسافة (خطي): {min_distance_linear}")
الكود أعلاه يوضح كيف أن استدعاء واحد لدالة kdtree.query() يغنينا عن كتابة حلقة for تمر على كل العناصر. الفرق في الأداء بين الطريقتين يصبح فلكياً كلما زاد حجم البيانات.
نصائح من خبرة أبو عمر
- لعنة الأبعاد (Curse of Dimensionality): أشجار k-d رائعة، لكنها ليست الحل السحري لكل شيء. أداؤها يبدأ بالتدهور بشكل كبير كلما زاد عدد الأبعاد (k). القاعدة العامة تقول إنها تعمل بشكل ممتاز حتى 10-20 بعداً. بعد ذلك، حجم الفضاء يصبح هائلاً لدرجة أن الشجرة تضطر لزيارة معظم الفروع، ويصبح أداؤها قريباً من البحث الخطي.
- البدائل في الأبعاد العالية: عندما تتعامل مع مئات الأبعاد (مثلما في نماذج تعلم الآلة الحديثة للغة أو الصور)، ستحتاج إلى حلول أخرى مثل Ball Trees أو خوارزميات البحث عن أقرب جار التقريبية (Approximate Nearest Neighbor – ANN) مثل HNSW أو Annoy من Spotify. هذه الخوارزميات لا تضمن إيجاد الجار الأقرب 100%، لكنها سريعة بشكل لا يصدق وتعطي نتائج دقيقة جداً (مثلاً 99.9% صحيحة).
- متى تعيد بناء الشجرة؟: بناء الشجرة عملية مكلفة نسبياً. إذا كانت بياناتك تتغير باستمرار (مثلاً، إضافة منتجات جديدة كل ثانية)، فقد لا تكون k-d Tree هي الخيار الأمثل، لأنك ستحتاج إلى إعادة بنائها باستمرار. هي تتألق في البيانات شبه الثابتة (Static or semi-static).
الخلاصة: متى تزرع هذه الشجرة في حديقتك؟ 🌱
شجرة k-d هي أداة قوية جداً في صندوق أدوات أي مطور يتعامل مع البيانات المكانية أو عمليات البحث عن التشابه. لقد أنقذت مشروعنا حرفياً، وحولت نظامنا من مصدر إحراج إلى مصدر فخر.
استخدمها عندما:
- تحتاج إلى إجراء عمليات بحث عن “أقرب جار” بشكل متكرر.
- بياناتك ذات أبعاد منخفضة إلى متوسطة (أقل من 20 بُعداً كقاعدة عامة).
- مجموعة البيانات لديك لا تتغير بشكل جنوني كل لحظة.
في المرة القادمة التي تجد فيها نفسك تكتب حلقة for لمسح مجموعة بيانات ضخمة بحثاً عن شيء قريب، تذكر قصة أبو عمر وتذكر هذه الشجرة العبقرية. قد تكون هي الخلاص الذي تبحث عنه. بالتوفيق يا وحوش! 🚀
