خوارزمية العلاج

خوارزمية CURE (التجميع باستخدام التمثيلات) هي خوارزمية فعالة لتجميع البيانات في قواعد البيانات الكبيرة . بالمقارنة مع خوارزمية K-means، فهي أكثر مقاومة للقيم الشاذة وقادرة على تحديد المجموعات ذات الأشكال غير الكروية وتفاوتات الحجم.

تعمل خوارزمية التجميع K-means الشائعة على تقليل مجموع مربعات الأخطاء وفقًا للمعيار التالي:

${\displaystyle E=\sum _{i=1}^{k}\sum _{p\in C_{i}}(p-m_{i})^{2},}$

نظراً للاختلافات الكبيرة في أحجام أو أشكال المجموعات المختلفة، قد تقوم طريقة الخطأ التربيعي بتقسيم المجموعات الكبيرة لتقليل الخطأ التربيعي، وهو أمر ليس صحيحاً دائماً. كذلك، توجد هذه المشاكل في خوارزميات التجميع الهرمي، حيث لا توجد أي من مقاييس المسافة بين المجموعات (${\displaystyle d_{min},d_{mean}}$تميل هذه الطرق إلى العمل مع أشكال مجموعات مختلفة. كما أن وقت التشغيل يكون طويلاً عندما تكون قيمة n كبيرة.

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

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

مدة التشغيل هي${\displaystyle O(n^{2}\log n)}$مما يجعله مكلفًا إلى حد ما، كما أن تعقيد المساحة${\displaystyle O(n)}$.

لا يمكن تطبيق الخوارزمية مباشرةً على قواعد البيانات الكبيرة نظرًا لتعقيد وقت التشغيل العالي. وتعالج التحسينات هذا الشرط.

• أخذ العينات العشوائي: يدعم أخذ العينات العشوائي مجموعات البيانات الكبيرة. وعادةً ما تتسع العينة العشوائية في الذاكرة الرئيسية . ينطوي أخذ العينات العشوائي على مفاضلة بين الدقة والكفاءة.
• التقسيم: تقوم الفكرة الأساسية على تقسيم فضاء العينة إلى p قسمًا. يحتوي كل قسم على n/p عنصرًا. في المرحلة الأولى، يتم تجميع كل قسم جزئيًا حتى ينخفض ​​عدد المجموعات إلى n/pq ، حيث q ثابت ≥ 1. في المرحلة الثانية، يتم تجميع الأقسام جزئيًا على n/q . في هذه المرحلة، تُخزَّن النقاط التمثيلية فقط، لأن عملية الدمج لا تتطلب سوى النقاط التمثيلية للمجموعات السابقة قبل حساب النقاط التمثيلية للمجموعة المدمجة. يُسهم تقسيم المدخلات في تقليل أوقات التنفيذ.
• تصنيف البيانات على القرص: عند توفر نقاط تمثيلية فقط لمجموعات k ، يتم تخصيص نقاط البيانات المتبقية لهذه المجموعات. ولتحقيق ذلك، يتم اختيار جزء من النقاط التمثيلية المختارة عشوائيًا لكل مجموعة من مجموعات k ، وتُخصص كل نقطة بيانات للمجموعة التي تحتوي على أقرب نقطة تمثيلية إليها.

علاج (عدد النقاط، k )

المدخلات: مجموعة من النقاط S

الناتج: k مجموعة

• لكل مجموعة u (كل نقطة إدخال)، يتم تخزين متوسط ​​النقاط في المجموعة ومجموعة من c نقاط تمثيلية للمجموعة في u.mean و u.rep (مبدئيًا c = 1 لأن كل مجموعة تحتوي على نقطة بيانات واحدة). كما يتم تخزين المجموعة الأقرب إلى u في u.closest.
• يتم إدخال جميع نقاط الإدخال في شجرة kd T
• تعامل مع كل نقطة إدخال على أنها مجموعة منفصلة، ​​واحسب u.closest لكل u ثم أدخل كل مجموعة في الكومة Q. (يتم ترتيب المجموعات بترتيب تصاعدي للمسافات بين u و u.closest).
• طالما أن الحجم (Q) > k
• قم بإزالة العنصر العلوي من Q (على سبيل المثال u) وقم بدمجه مع أقرب مجموعة له u.closest (على سبيل المثال v) واحسب النقاط التمثيلية الجديدة للمجموعة المدمجة w.
• قم بإزالة u و v من T و Q.
• لكل مجموعة x في Q، قم بتحديث x.closest ونقل x
• أدخل w في Q
• يكرر

• تتضمن مكتبة pyclustering مفتوحة المصدر تطبيقًا بلغة بايثون ولغة C++ لخوارزمية CURE.

• التجميع باستخدام خوارزمية k-means
• خوارزمية BFR

• غوها، سوديبتو؛ راستوجي، راجيف؛ شيم، كيوسوك (1998). "CURE: خوارزمية تجميع فعّالة لقواعد البيانات الكبيرة" (ملف PDF) . نظم المعلومات . 26 (1): 35-58 . doi : 10.1016/S0306-4379(01)00008-4 .
• كوجان، جاكوب؛ نيكولاس، تشارلز ك.؛ تيبول، م. (2006). تجميع البيانات متعددة الأبعاد: التطورات الحديثة في التجميع . سبرينغر. ISBN 978-3-540-28348-5.
• ثيودوريديس، سيرجيوس؛ كوترومباس، قسطنطين (2006). التعرف على الأنماط . دار النشر الأكاديمية. الصفحات 572-574 . ISBN  978-0-12-369531-4.