التعلم الآلي “تقويم المجيء” اليوم العاشر: DBSCAN في Excel
نحن هنا في اليوم العاشر من “تقويم المجيء” للتعلم الآلي. أود أن أشكركم على دعمكم.
لقد قمت بإنشاء ملفات جداول بيانات Google هذه لسنوات. تطوروا شيئا فشيئا. ولكن عندما يحين وقت نشرها، أحتاج دائمًا إلى ساعات لإعادة تنظيم كل شيء، وتنظيف التخطيط، وجعلها ممتعة للقراءة.
واليوم ننتقل إلى DBSCAN.
لا يتعلم DBSCAN نموذجًا حدوديًا
تمامًا مثل LOF، فإن DBSCAN كذلك لا نموذج بارامترى. لا توجد صيغة لتخزينها، ولا قواعد، ولا نقط مركزية، ولا يوجد شيء مضغوط لإعادة استخدامه لاحقًا.
يجب علينا أن نحافظ على مجموعة البيانات بأكملها لأن بنية الكثافة تعتمد على جميع النقاط.
اسمها الكامل هو التجميع المكاني القائم على الكثافة للتطبيقات مع الضوضاء.
لكن كن حذرًا: هذه “الكثافة” ليست كثافة غوسية.
إنه أ على أساس العد فكرة الكثافة. فقط “كم عدد الجيران الذين يعيشون بالقرب مني”.
لماذا يعد DBSCAN مميزًا
كما يشير اسمه، يقوم DBSCAN بذلك شيئين في نفس الوقت:
- يجد مجموعات
- تشير إلى حالات شاذة (النقاط التي لا تنتمي إلى أي مجموعة)
وهذا هو بالضبط سبب تقديمي للخوارزميات بهذا الترتيب:
- ك-وسائل و غم نكون نماذج التجميع. إنهم ينتجون كائنًا مضغوطًا: النقط الوسطى للوسائل k والوسائل والتباينات لـ GMM.
- غابة العزلة و LOF نكون نماذج الكشف عن الشذوذ النقي. هدفهم الوحيد هو العثور على نقاط غير عادية.
- DBSCAN يجلس بينهما. يفعل كلا الأمرين التجمع والكشف عن الشذوذ، بناءً فقط على فكرة كثافة الحي.
مجموعة بيانات صغيرة لإبقاء الأمور بديهية
نبقى مع نفس مجموعة البيانات الصغيرة التي استخدمناها في LOF: 1، 2، 3، 7، 8، 12
إذا نظرت إلى هذه الأرقام، ترى بالفعل مجموعتين مدمجتين:
واحد حولها 1-2-3، آخر حولها 7-8، و 12 العيش وحيدا.
يلتقط DBSCAN هذا الحدس بالضبط.
ملخص في 3 خطوات
يسأل DBSCAN ثلاثة أسئلة بسيطة لكل نقطة:
- كم عدد الجيران لديك داخل دائرة نصف قطرها صغير (eps)؟
- هل لديك ما يكفي من الجيران لتصبح نقطة أساسية (minPts)؟
- بمجرد أن نعرف النقاط الأساسية، إلى أي مجموعة متصلة تنتمي؟
فيما يلي ملخص لخوارزمية DBSCAN في 3 خطوات:
دعونا نبدأ خطوة بخطوة.
DBSCAN في 3 خطوات
الآن بعد أن فهمنا فكرة الكثافة والأحياء، أصبح من السهل جدًا وصف DBSCAN.
كل ما تفعله الخوارزمية يناسبه ثلاث خطوات بسيطة.
الخطوة 1 – عد الجيران
الهدف هو التحقق من عدد الجيران في كل نقطة.
نحن نأخذ دائرة نصف قطرها صغيرة تسمى eps.
لكل نقطة، ننظر إلى جميع النقاط الأخرى ونضع علامة على تلك النقاط التي تكون المسافة بينها أقل من eps.
هذه هي الجيران.
وهذا يعطينا الفكرة الأولى للكثافة:
نقطة مع العديد من الجيران تقع في منطقة كثيفة،
نقطة مع عدد قليل من الجيران تعيش في منطقة متناثرة.
بالنسبة لمثال لعبة ذات بعد واحد مثل مثالنا، فإن الاختيار الشائع هو:
العائد على السهم = 2
نرسم مسافة صغيرة نصف قطرها 2 حول كل نقطة.
لماذا يطلق عليه eps؟
الاسم eps يأتي من الحرف اليوناني ε (ابسيلون)، والذي يستخدم تقليديا في الرياضيات لتمثيل أ كمية صغيرة أو أ نصف قطر صغير حول نقطة.
لذلك في DBSCAN، eps هو حرفيا “نصف قطر الحي الصغير”.
ويجيب على السؤال:
إلى أي مدى ننظر حول كل نقطة؟
لذلك في Excel، الخطوة الأولى هي حساب مصفوفة المسافة الزوجية، ثم قم بحساب عدد الجيران الموجودين في كل نقطة ضمن eps.
الخطوة 2 – النقاط الأساسية واتصال الكثافة
والآن بعد أن عرفنا الجيران من الخطوة 1، نقوم بالتقديم minPts لتحديد النقاط التي هي جوهر.
minPts تعني هنا الحد الأدنى لعدد النقاط.
إنه أصغر عدد من الجيران الذي يجب أن تمتلكه النقطة (داخل نصف قطر eps) حتى يتم اعتبارها نقطة جوهر نقطة.
النقطة هي الأساسية إذا كان لديها على الأقل minPts الجيران في الداخل eps.
وإلا فإنه قد يصبح حدود أو ضوضاء.
مع العائد على السهم = 2 و الحد الأدنى = 2، لدينا 12 ليست أساسية.
بمجرد معرفة النقاط الأساسية، فإننا ببساطة نتحقق من النقاط الموجودة كثافة يمكن الوصول إليها منهم. إذا كان من الممكن الوصول إلى نقطة ما عن طريق الانتقال من نقطة أساسية إلى أخرى خلال eps، فإنها تنتمي إلى نفس المجموعة.
في Excel، يمكننا تمثيل ذلك كجدول اتصال بسيط يوضح النقاط المرتبطة من خلال الجيران الأساسيين.
هذا الاتصال هو ما يستخدمه DBSCAN لتشكيل مجموعات في الخطوة 3.
الخطوة 3 – تعيين تسميات المجموعة
الهدف هو تحويل الاتصال إلى مجموعات فعلية.
بمجرد أن تصبح مصفوفة الاتصال جاهزة، تظهر المجموعات بشكل طبيعي.
يقوم DBSCAN ببساطة بتجميع كافة النقاط المتصلة معًا.
لإعطاء كل مجموعة اسمًا بسيطًا وقابلاً للتكرار، نستخدم قاعدة بديهية جدًا:
تسمية الكتلة هي أصغر نقطة في المجموعة المتصلة.
على سبيل المثال:
- تصبح المجموعة {1، 2، 3} مجموعة 1
- تصبح المجموعة {7، 8} المجموعة 7
- نقطة مثل 12 مع عدم وجود جيران الأساسية يصبح ضوضاء
هذا هو بالضبط ما سنعرضه في برنامج Excel باستخدام الصيغ.
الأفكار النهائية
يعد DBSCAN مثاليًا لتعليم فكرة الكثافة المحلية.
لا يوجد احتمال، ولا صيغة غاوسية، ولا خطوة تقدير.
فقط مسافات وجيران ونصف قطر صغير.
لكن هذه البساطة تحد من ذلك أيضًا.
نظرًا لأن DBSCAN يستخدم نصف قطر ثابتًا واحدًا للجميع، فلا يمكنه التكيف عندما تحتوي مجموعة البيانات على مجموعات بمقاييس مختلفة.
HDBSCAN يحافظ على نفس الحدس، ولكن ينظر إليه الجميع نصف القطر ويحافظ على ما يبقى مستقرا.
إنها أقوى بكثير، وأقرب كثيرًا إلى الطريقة التي يرى بها البشر المجموعات بشكل طبيعي.
مع DBSCAN، وصلنا إلى لحظة طبيعية للتراجع وتلخيص النماذج غير الخاضعة للرقابة التي استكشفناها حتى الآن، بالإضافة إلى عدد قليل من النماذج الأخرى التي لم نغطيها.
إنها فرصة جيدة لرسم خريطة صغيرة تربط هذه الخوارزميات ببعضها البعض وتبين موقع كل منها في المشهد الأوسع.
- النماذج المعتمدة على المسافة
تعمل وسائل K وMedoids والتجمع الهرمي (HAC) من خلال مقارنة المسافات بين النقاط أو بين المجموعات. - النماذج المعتمدة على الكثافة
يقوم متوسط التحول ونماذج الخليط الغوسي (GMM) بتقدير الكثافة الناعمة واستخراج المجموعات من بنيتها. - النماذج القائمة على الحي
تحدد DBSCAN وOPTICS وHDBSCAN وLOF المجموعات والحالات الشاذة من الاتصال المحلي بدلاً من المسافة العالمية. - النماذج القائمة على الرسم البياني
يعتمد التجميع الطيفي ولوفان وليدن على البنية داخل الرسوم البيانية للتشابه.
تعكس كل مجموعة فلسفة مختلفة لماهية “المجموعة”.
غالبًا ما يعتمد اختيارك للخوارزمية بشكل أقل على النظرية وأكثر على شكل البيانات وحجم كثافتها وأنواع الهياكل التي تتوقع العثور عليها.
إليك كيفية ربط هذه الطرق ببعضها البعض:
- يتم تعميم وسائل K على GMM عندما تستبدل المهام الصعبة بالكثافات الاحتمالية.
- يتم تعميم DBSCAN على OPTICS عند إزالة الحاجة إلى قيمة eps واحدة.
- تؤدي OPTICS بشكل طبيعي إلى HDBSCAN، الذي يحول اتصال الكثافة إلى تسلسل هرمي مستقر.
- تقوم كل من HAC وSpectral ببناء مجموعات من مسافات زوجية، لكن Spectral يضيف عرضًا قائمًا على الرسم البياني.
- يستخدم LOF نفس الأحياء التي يستخدمها DBSCAN، ولكن فقط للكشف عن الحالات الشاذة.
هناك العديد من النماذج، ولكن هذا يعطي فكرة عن المشهد والمكان الذي يناسبه DBSCAN بداخله.
غدًا، سنواصل تقويم Advent بنماذج أكثر “كلاسيكية” وتستخدم على نطاق واسع في التعلم الآلي اليومي.
شكرًا لك على متابعة الرحلة حتى الآن، ونراكم غدًا.