CCKM: A Modified k-means Clustering using Concentric Circles
تقدم هذه الورقة البحثية خوارزمية CCKM، وهي خوارزمية تجميع k-means حتمية تستخدم استراتيجية تهيئة للمراكز تعتمد على الدوائر المركزية والربعية في فضاء مُخفض عبر تحليل المكونات الرئيسية (PCA)، لتتفوق باستمرار على خوارزمية k-means التقليدية وسابقتها ECKM عبر مجموعات بيانات ومقاييس تقييم متعددة.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
في محيطات البيانات الحديثة الشاسعة والصامتة، حيث تطفو مليارات النقاط من المعلومات دون تسميات أو حدود واضحة، يحتاج العلماء غالباً إلى إيجاد الأنماط. إنهم بحاجة إلى فرز هذه الفوضى إلى مجموعات ذات معنى، وهي مهمة تُعرف باسم "التجميع" (Clustering). تخيل أنك تحاول تنظيم مكتبة ضخمة حيث أُلقيت جميع الكتب على الأرض، مختلطة ببعضها البعض، ولا يوجد أي منها يحمل عنواناً. لكي تفهم المجموعة، يجب عليك أن تقرر أي الكتب تنتمي معاً بناءً على محتواها، وتجميعها في أكوام تشترك في قصص متشابهة. هذا هو التحدي الجوهم في عملية التجميع: أخذ مجموعة بيانات مبعثرة وتقسيمها إلى مجموعات (Clusters) متميزة تكون العناصر داخل كل مجموعة أكثر تشابهاً مع بعضها البعض مما هي عليه مع العناصر في المجموعات الأخرى.
أحد أكثر الأدوات شيوعاً لهذه المهمة هو خوارزمية تُسمى "k-means". تعمل هذه الخوارزمية عن طريق اختيار بضع نقاط بداية، تُسمى "المراكز" (Centroids)، ثم تطلب من كل نقطة بيانات الانضمام إلى أقرب مركز لها. وبمجرد أن تختار النقاط مجموعاتها، تقوم الخوارزمية بإعادة حساب مركز كل مجموعة بناءً على المكان الذي استقرت فيه النقاط فعلياً، ثم تطلب من النقاط الاختيار مرة أخرى. تتكرر هذه الدورة حتى تتوقف المجموعات عن التغير. ومع ذلك، فإن نجاح هذه العملية يعتمد كلياً على مكان وضع نقاط البداية الأولى تلك. فإذا كانت التخمينات الأولية سيئة، يمكن للخوارزمية أن تظل عالقة في ترتيب غير مثالي، مما يؤدي إلى فرز الكتب في أكوام فوضوية وخاطئة تبدو مرتبة ولكنها تروي القصة الخطأ. لسنوات، حاول الباحثون حل هذه المشكلة من خلال إيجاد طرق أفضل لاختيار نقاط البداية هذه، والابتعاد عن التخمينات العشوائية نحو استراتيجيات هندسية أكثر تعمداً.
في دراسة حديثة، اقترح الباحثان بارون كر بول وكينسوك جيري من الهند طريقة جديدة للتعامل مع هذا التخمين الأولي. فقد قدما طريقة تسمى "k-means القائمة على الدوائر المركزية" (Concentric Circles based k-means)، أو CCKM. فبدلاً من التخمين عشوائياً أو استخدام أشكال هندسية معقدة يصعب حسابها، يعتمد نهجهما على فكرة بسيطة وبديهية: رسم دوائر حول مركز البيانات. يقوم الباحثون أولاً بأخذ مجموعة البيانات بأكملها وتقليصها إلى بُعدين، مما يخلق خريطة مسطحة تحافظ على العلاقات بين النقاط. ثم يجدون المركز الدقيق لجميع نقاط البيانات على هذه الخريطة ويعاملونه كنقطة الأصل، أو منتصف لوحة الهدف (Bullseye).
من هذه النقطة المركزية، يرسم الفريق سلسلة من الدوائر التي تشترك في نفس المركز ولكن بأحجام مختلفة، تماماً مثل حلقات الهدف. تقسم هذه الدوائر المساحة إلى نطاقات أو حلقات متميزة بينها. ثم يقوم الباحثون بعدّ عدد نقاط البيانات التي تقع في كل حلقة. وداخل كل حلقة، ينظرون إلى الأرباع الأربعة، أو "القطاعات"، ليروا أي منها هو الأكثر ازدحاماً. يختارون مركز القطاع الأكثر ازدحاماً في كل حلقة ليكون بمثابة نقطة البداية لمجموعة جديدة. ومن خلال القيام بذلك، يضمنون أن تكون نقاط البداية موزعة عبر البيانات وموضوعة في الأماكن التي تتركز فيها البيانات بالفعل، بدلاً من أن تطفو في مساحات فارغة أو تتكتل بالصدفة.
اختبر الفريق هذه الطريقة الجديدة مقابل خوارزمية k-means القياسية وطريقة هندسية سابقة تُسمى "k-means القائمة على الدائرة الفارغة" (Empty Circle based k-means). أجروا تجاربهم على عشر مجموعات بيانات مختلفة، تتراوح من المجموعات البسيطة والمنفصلة بوضوح إلى الأشكال المعقدة والمتعرجة التي يصعب فرزها. أظهرت النتائج أن نهج الدوائر المركزية الجديد كان فعالاً للغاية. وفي غالبية الاختبارات، أنتجت الطريقة الجديدة مجموعات أكثر نظافة ودقة من النهج العشوائي القياسي. والأهم من ذلك، أنها وصلت إلى حل مستقر بشكل أسرع بكثير. في عدة مجموعات بيانات، تطلبت الطة الجديدة خطوات أقل بكثير لإنهاء عملها؛ فعلى سبيل المثال، في إحدى مجموعات البيانات، استغرقت أربع خطوات فقط مقارنة بثماني خطوات للطريقة القياسية، وفي مجموعة أخرى، انتهت في سبع خطوات مقابل أربع عشرة خطوة. هذه السرعة أمر بالغ الأهمية لأنها تعني أن الكمبيوتر يقضي وقتاً أقل في الحساب ووقتاً أطول في تقديم النتائج.
كما سلطت الدراسة الضوء على المواضع التي تتألق فيها هذه الطريقة والمواضع التي تكمن فيها حدودها. فقد حققت أداءً استثنائياً في مجموعات البيانات ذات الأشكال غير الخطية، مثل البيانات المرتبة في مسار أو منحنى يشبه اللهب، حيث تعاني الطرق القياسية غالباً. كما تفوقت عندما يكون عدد المجموعات متوسطاً، حيث تعاملت بنجاح مع سيناريوهات تحتوي على ما يصل إلى خمس عشرة مجموعة متميزة. ومع ذلك، لاحظ الباحثون أنه عندما يصبح عدد المجموعات كبيراً جداً بالنسبة لحجم البيانات، فإن الهيكل الصارم للدوائر المركزية قد يصبح عائقاً. في هذه السيناريوهات المحددة وعالية الكثافة، قد تتطلب الطريقة أحياناً خطوات أكثر لفرز البيانات مقارنة بالطريقة القياسية. ورغم هذه الحدود، تشير النت النتائج الإجمالية إلى أن استخدام الحلقات المركزية البسيطة لتوجيه الوضع الأولي للمجموعات هو وسيلة قوية وفعالة وموثوقة لتنظيم البيانات المعقدة. لقد جعل الباحثون كود البرمجة والبيانات الخاصة بهم متاحة للجمهور، مما يسمح للآخرين بالتحقق من هذه النتائج وتطبيق هذا المنطق الهندسي على تحديات فرز البيانات الخاصة بهم.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.