شجرة الكرات

في علم الحاسوب ، ^تُعرف شجرة الكرة ، أو شجرة ^{القياس ،} بأنها بنية بيانات لتقسيم الفضاء تُستخدم لتنظيم النقاط في فضاء متعدد الأبعاد. تقسم شجرة الكرة نقاط البيانات إلى مجموعة متداخلة من الكرات . تتميز بنية البيانات الناتجة بخصائص تجعلها مفيدة في العديد من التطبيقات، وأبرزها البحث عن أقرب جار .

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

تُحدد كل عقدة في الشجرة أصغر كرة تحتوي على جميع نقاط البيانات في شجرتها الفرعية. وهذا يُنتج الخاصية المفيدة التالية: بالنسبة لنقطة اختبار معينة t خارج الكرة، فإن المسافة إلى أي نقطة في كرة B في الشجرة أكبر من أو تساوي المسافة من t إلى سطح الكرة. بالصيغة الرسمية: ^{[ 2 ]}

${\displaystyle D^{B}(t)={\begin{cases}\max(|t-{\textit {B.pivot}}|-{\textit {B.radius}},D^{\textit {B.parent}}),&{\text{if }}B\neq Root\\\max(|t-{\textit {B.pivot}}|-{\textit {B.radius}},0),&{\text{if }}B=Root\\\end{cases}}}$

أين${\displaystyle D^{B}(t)}$هي أقصر مسافة ممكنة من أي نقطة في الكرة B إلى نقطة ما t .

ترتبط أشجار الكرة بشجرة M ، لكنها تدعم فقط الانقسامات الثنائية، بينما في شجرة M ينقسم كل مستوى${\displaystyle m}$ل${\displaystyle 2m}$يؤدي طي الأشجار إلى بنية شجرية أقل عمقًا، وبالتالي يتطلب حسابات مسافة أقل، مما ينتج عنه عادةً استعلامات أسرع. علاوة على ذلك، يمكن تخزين أشجار M بشكل أفضل على القرص ، حيث يتم تنظيمها في صفحات . كما تحتفظ شجرة M بالمسافات من العقدة الأصلية محسوبة مسبقًا لتسريع الاستعلامات.

تتشابه أشجار نقطة المراقبة أيضًا، لكنها تنقسم ثنائيًا إلى كرة واحدة، والبيانات المتبقية، بدلاً من استخدام كرتين.

تتوفر عدة خوارزميات لبناء شجرة الكرة. ^{[ 1 ]} يهدف هذا النوع من الخوارزميات إلى إنتاج شجرة تدعم بكفاءة الاستعلامات من النوع المطلوب (مثل أقرب جار) في الحالة المتوسطة. وتعتمد المعايير المحددة للشجرة المثالية على نوع السؤال المراد الإجابة عليه وتوزيع البيانات الأساسية. ومع ذلك، فإن المقياس العام لكفاءة الشجرة هو تقليل الحجم الإجمالي لعقدها الداخلية. ونظرًا لتنوع توزيعات مجموعات البيانات في العالم الحقيقي، تُعد هذه مهمة صعبة، ولكن توجد عدة طرق استدلالية تُقسّم البيانات بشكل جيد عمليًا. وبشكل عام، هناك مفاضلة بين تكلفة بناء الشجرة والكفاءة التي يحققها هذا المقياس. ^{[ 2 ]}

يصف هذا القسم بإيجاز أبسط هذه الخوارزميات. وقد قدم ستيفن أوموهوندرو مناقشة أكثر تعمقاً لخمس خوارزميات. ^{[ 1 ]}

الدالة construct_balltree تأخذ المدخلات التالية: D ، وهي عبارة عن مصفوفة من نقاط البيانات. وتخرج الدالة: B ، وهو جذر شجرة الكرة التي تم إنشاؤها. إذا بقيت نقطة واحدة، فأنشئ ورقة B تحتوي على تلك النقطة في D، ثم أعد B. وإلا ، فليكن c هو بُعد أكبر انتشار. لنفترض أن p هي النقطة المركزية المختارة مع مراعاة c ليكن L و R مجموعتي النقاط الواقعة على يسار ويمين الوسيط على طول البعد c. أنشئ B مع طفلين: B.pivot := p ، B.child1 := construct_balltree(L)، B.child2 := construct_balltree(R). ليكن B.radius أقصى مسافة من p بين الأبناء، ثم أعد B. نهاية الدالة.

يُعدّ تسريع استعلامات البحث عن أقرب جار أحد أهم تطبيقات أشجار الكرة ، حيث يهدف البحث إلى إيجاد أقرب k نقطة في الشجرة إلى نقطة اختبار معينة باستخدام مقياس مسافة محدد (مثل المسافة الإقليدية ). تستغل خوارزمية بحث بسيطة، تُسمى أحيانًا KNS1، خاصية المسافة في شجرة الكرة. على وجه الخصوص، إذا كانت الخوارزمية تبحث في بنية البيانات باستخدام نقطة اختبار t ، وقد رصدت بالفعل نقطة p الأقرب إلى t من بين النقاط التي صادفتها حتى الآن، فيمكن تجاهل أي شجرة فرعية تكون كرتها أبعد عن t من p في بقية عملية البحث.

دالة البحث عن أقرب جار هي المدخلات التالية: t، النقطة المستهدفة للاستعلام k، عدد أقرب الجيران لـ t الذين سيتم البحث عنهم Q، طابور ذو أولوية قصوى يحتوي على k نقطة على الأكثر ب، عقدة، أو كرة، في الشجرة الناتج: Q، التي تحتوي على أقرب k جار من داخل B إذا كان الفرق بين المسافة (t، B.pivot) ونصف قطر B أكبر من أو يساوي المسافة (t، Q.first) ، فأرجع Q دون تغيير. أما إذا كانت B عقدة طرفية، فلكل نقطة p في B ، إذا كانت المسافة (t، p) أقل من المسافة (t، Q.first) ، أضف p إلى Q إذا كان حجم (Q) أكبر من k ، قم بإزالة أبعد جار من Q نهاية الشرط نهاية الشرط كرر وإلا ليكن child1 هو العقدة الفرعية الأقرب إلى t لنفترض أن child2 هي العقدة الفرعية الأبعد عن t knn_search(t, k, Q, child1) knn_search(t, k, Q, child2) end if return Q end function [ 2 ]