🤖 machine learning

Local Cluster Cardinality Estimation for Adaptive Mean Shift

تقدم هذه الورقة خوارزمية "إزاحة المتوسط" (mean shift) متوافقة مع المقياس ومتكيفة كلياً، والتي تحدد تلقائياً عرض النطاق المحلي وعتبات النواة لكل نقطة من خلال تقدير عدد العناصر في العنقود المحلي عبر تحليل توزيع المسافة، محققةً أداء تجميع تنافسي دون الحاجة إلى معرفة مسبقة بعدد العناقيد أو معاملات المقياس العالمية.

المؤلفون الأصليون: Étienne Pepin

نُشر 2026-08-13

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Étienne Pepin

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك في مهرجان موسيقي ضخم وفوضوي. تريد العثور على أصدقائك، لكن الحشد عبارة عن مزيج دوار من آلاف الأشخاص، بعضهم يقف في مجموعات صغيرة متراصة، والبعض الآخر يتجول وحيداً، وهناك تجمعات ضخمة لدرجة أنها تمتد عبر الساحة بأكملها. في عالم علم البيانات، هذه هي مشكلة التجميع (Clustering): محاولة فرز كومة فوضوية من المعلومات إلى مجموعات مرتبة وذات معنى دون وجود خريطة. عادةً، يحتاج الكمبيوتر إلى إنسان يخبره: "مهلاً، هناك بالضبط خمس مجموعات هنا"، أو "استخدم نصف قطر بحث قدره خمسة أمتار". ولكن ماذا لو استطاع الكمبيوتر ببساطة النظر إلى الحشد، وتحديد المجموعات من تلقاء نفسه، وإدراك أن إحدى المجموعات صغيرة ومتراصة بينما الأخرى ضخمة ومنتشرة؟ هذا هو حلم التجميع التكيفي (Adaptive Clustering): وهي طريقة لا تحتاج إلى مسطرة جامدة، بل تستخدم عينيها بدلاً من ذلك لقياس المسافة بين الجيران.

يقدم هذا البحث طريقة ذكية للكمبيوتر للقيام بذلك تماماً. فهو يقترح طريقة تسمى إزاحة المتوسط التكيفية (Adaptive Mean Shift)، وهي تشبه مغناطيساً ذكياً يجذب النقاط معاً لتشكل مجموعاتها الطبيعية. السر يكمن في خدعة جديدة لمعرفة عدد الأشخاص في مجموعة معينة بمجرد النظر إلى مدى تباعدهم عن بعضهم البعض. فبدلاً من التخمين بحجم ثابت لمنطقة البحث، ينظر الخوارزم إلى "توزيع المسافات" — وهو قائمة توضح مدى بعد نقطة واحدة عن الجميع — ويجد "فجوة" أو انخفاضاً طبيعياً في هذه القائمة. هذا الانخفاض يخبر الكمبيوتر: "حسناً، كل من هم أقرب من هذه الفجوة ينتمون إلى مجموعتي؛ وكل من هم أبعد من ذلك هم غرباء". وهذا يسمح للكمبيوتر بتعديل نصف قطر البحث الخاص به آنياً لكل نقطة، مما يجعله غير متأثر بالمقياس (يعمل سواء كانت البيانات تُقاس بالبوصة أو بالسنين الضوئية) ومحلياً (يهتم فقط بالحي المباشر).

قصة المغناطيس ذاتي القياس

تعرف على خوارزمية الإزاحة المتوسطة التكيفية (Adaptive Mean Shift). تخيلها كمجموعة من المتنزهين يحاولون العثور على مركز مخيمهم. في الأيام الخوالي، كان يُقال لكل متنزّه: "انظر إلى كل من يبعد عنك مسافة 10 أقدام وتحرك نحو المتوسط". كان هذا يعمل جيداً إذا كان الجميع يقفون في دائرة مثالية، ولكن ماذا لو كانت إحدى المجموعات متجمعة في دائرة ضيقة وأخرى منتشرة على مساحة ملعب كرة قدم؟ فإن قاعدة الـ 10 أقداء ستؤدي إما إلى تفويت المجموعة المنتشرة أو سحب أشخاص من مخيم آخر بالخطأ.

يقدم هذا البحث متنزهاً أكثر ذكاءً. فبدلاً من إعطائه قاعدة ثابتة قدرها 10 أقدام، يسأل هذا المتنزّه سؤالاً بسيطاً: "كم يبعد جيراني عني؟" يقوم بإنشاء قائمة بالمسافات إلى كل شخص آخر في الحشد. إذا كنت في مجموعة متراصة، فستظهر قائمتك مسافات قصيرة كثيرة، ثم فجأة قفزة كبيرة إلى المجموعة التالية. خدعة البحث هنا هي إيجاد تلك القفزة.

يستخدم المؤلف أداة رياضية خاصة تسمى دالة $\gamma$ (دالة غاما) لمسح قائمة المسافات هذه. تخيل قائمة المسافات كطريق متعرج؛ دالة $\gamma$ هي مثل جهاز قياس زلازل حساس يبحث عن أعمق وادٍ بين تلتين. التلة الأولى تمثل الأشخاص في مجموعتك الخاصة (الجيران القريبين)، والتلة الثانية تمثل الأشخاص في المجموعات الأخرى (الجيران البعيدين). الوادي بينهما هو المكان المثالي لرسم خط.

بمجرد أن يجد الخوارزم هذا الوادي، فإنه يعرف بالضبط عدد الأشخاص في المجموعة المحلية (العدد/Cardinality) ومدى امتداد المجموعة (نصف القطر/Radius). ثم يستخدم هذه المعلومات المحددة لضبط "نصف قطر البحث" و"قوة الجذب" الخاصة به لهذا الموقع تحديداً. إنه يشبه الحرباء التي تغير لونها لتناسب البيئة التي تقف فيها تماماً.

لماذا هذا مهم: لا مزيد من التخمين لعدد المجموعات

أكبر صداع في عملية التجميع هو عادةً معرفة عدد المجموعات الموجودة. معظم الخوارزميات تحتاج منك أن تقول: "جد لي 3 مجموعات" أو "جد لي 10". إذا أخطأت في التخمين، ينهار الأمر برمته. هذه الطريقة الجديدة لا تحتاج إلى ذلك الرقم؛ فهي تحدد المجموعات من خلال البحث عن الفجوات الطبيعية في بيانات المسافات.

اختبر المؤلف هذه الفكرة على "مجموعة بيانات تجريبية" أولاً — عالم مُصطنع يحتوي على أربع مجموعات ذات أحجام وانتشارات مختلفة. نجحت الخوارما في العثور على المجموعات الأربع جميعها، رغم أن إحدى المجموعات كانت صغيرة جداً والأخرى كانت ضخمة. لقد أدركت أن المجموعة الصغيرة تحتاج إلى نصف قطر بحث صغير، بينما تحتاج المجموعة الضخمة إلى نصف قطر كبير، كل ذلك دون إخبارها بعدد المجموعات.

وعندما قارن المؤلف طريقته بالتقنيات الذكية الأخرى للتجميع (تحديداً طريقة WAMS بواسطة Ren وآخرون من عام 2014)، كانت النتائج واعدة. ففي سبع من أصل تسع مجموعات بيانات من العالم الحقيقي (مثل صور الحروف المكتوبة بخط اليد أو البيانات البيولوجية)، وجدت طريقته الجديدة تجمعات أفضل من المنافس. لم تكتفِ بالفوز فحسب، بل فازت غالباً بفارق واضح، حيث حققت "مؤشر راند" (وهو درجة توضح مدى مطابقة المجموعات للحقيقة) قدره 0.9575 على مجموعة بيانات Iris مقارنة بـ 0.9495 للطريقة الأخرى. وفي بعض مجموعات البيانات، كان الفرق صغيراً (أقل من 0.012)، ولكن في مجموعات أخرى، كان الفرق جوهرياً.

قواعد اللعبة

يشير البحث بعناية إلى ما لا تستطيع هذه الطريقة فعله. فهي ليست عصا سحرية تحل كل المشكلات فوراً.

ليست مثالية للمجموعات الضخمة: لدى الخوارزمية قاعدة تقول: "لن نبحث عن مجموعة أكبر من نصف إجمالي البيانات". إذا كانت مجموعة البيانات تحتوي على مجموعة واحدة ضخمة تشكل 60% من كل شيء، فقد يرتبك هذا الأسلوب ويقسم تلك المجموعة الضخمة إلى أجزاء. يعترف المؤلف بأن هذا يمثل قصوراً ويقترح أن قاعدة "الحد الأقصى" تحتاج إلى أن تكون أكثر ذكاءً في المستقبل.
ليست طفرة مثبتة لكل شيء: بينما تفوقت على المنافس في الاختبارات المحددة التي أجرتها، يشير المؤلف إلى أنه قارنها بطريقة تكيفية واحدة فقط. ويقترح الحاجة إلى مزيد من الاختبارات ضد الأساليب الأحدث.
هي نموذج أولي: يصف المؤلف هذا بأنه "نموذج أولي وظيفي أول". ويرى مجالاً للتحسين، مثل استخدام طرق مختلفة للعثور على "الوادي" في قائمة المسافات أو اختبار كيفية تعاملها مع البيانات عالية الأبعاد (البيانات التي تحتوي على مئات الميزات).

الخلاصة

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

ملخص تقني: تقدير عدد العناصر في العنقود المحلي من أجل إزاحة المتوسط التكيفية

بيان المشكلة

تتناول الورقة البحثية تحدي اختيار المعلمات في خوارزمية إزاحة المتوسط التكيفية (Adaptive Mean Shift - AMS). تعتمد خوارزميات AMS التقليدية على معامل عرض النطاق (bandwidth) لتحديد الجوار المحلي لحساب المتوسطات الموزونة. وبينما تستخدم نسخ AMS الأساسية عرض نطاق عالمي ثابت، تحاول النسخ التكيفية تعديل هذا المعامل محلياً، وغالباً ما تعتمد على تقدير الكثافة المحلية (مثل تقدير كثافة النواة - KDE).

حدد المؤلف مشكلتين رئيسيتين في النهج الحالي:

الاعتماد على المقياس (Scale Dependence): تتطلب العديد من الطرق ثابتاً طولياً (عرض النطاق) يتم اختياره لمجموعة البيانات ككل، مما يجعلها حساسة لمقياس البيانات.
المحلية والضجيج: يقيس تقدير كثافة النواة (KDE) القياسي الكثافة في جوار ثابت الحجم. إذا كان هذا الجوار كبيراً جداً، فإنه سيشمل نقاطاً من عناقيد بعيدة، مما يؤدي إلى تشويه التقدير المحلي. وإذا كان صغيراً جداً، فقد يفتقر إلى بنية العنقود. علاوة على ذلك، يتطلب KDE معامل عرض نطاق ليس من السهل اختياره، خاصة بالنسبة للعناقيد الصغيرة أو البيانات عالية الأبعاد حيث يمكن أن يحدث التنعيم المفرط (oversmoothing).

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

المنهجية

تعمل الخوارزمية المقترحة في ثلاث مراحل رئيسية: تقدير عدد عناصر العنقود، إزاحة المتوسط التكيفية، وتصنيف القيم المتطرفة.

1. تقدير عدد عناصر العنقود المحلي

الابتكار الجوهري هو تقدير عدد عناصر العنقود المحلي ( $\hat{n}$ ) باستخدام توزيع المسافة لنقطة $x_i$ إلى جميع النقاط الأخرى.

توزيع المسافة: لكل نقطة، يتم ترتيب المسافات إلى جميع النقاط الأخرى. يفترض المؤلف أنه في مجموعة بيانات متعددة الأنماط، يكون هذا التوزيع ثنائي المنوال: يمثل النمط الأول المسافات إلى النقاط داخل نفس العنقود المحلي، ويمثل النمط الثاني المسافات إلى النقاط في العناقيد الأخرى.
دالة $\gamma$ : لتحديد الحدود بين هذين النمطين (الوادي ذو الكثافة الدنيا)، تقدم الورقة دالة $\gamma$ :
$\gamma(y^{(k)}) = \frac{s^2}{(\bar{y} - y^{(k)})^2}$
حيث $y^{(k)}$ هو المسافة المرتبة رقم $k$ ، و $\bar{y}$ هو متوسط أول $k$ مسافة، و $s^2$ هو تباين هذه المسافات.
منطق التقدير: تبحث الخوارزمية عن الرتبة $k$ التي تقلل $\gamma$ ضمن نافذة بحث محددة ($minBoundary $إلى$ maxBoundary $). يمثل هذا الحد الأدنى عدد عناصر العنقود المحلي المقدر$ \hat{n}_i$.
الخصائص الرئيسية:
- الاستقلال عن المقياس (Scale Invariance): دالة $\gamma$ هي نسبة التباين إلى مربع المسافة. ضرب البيانات في ثابت موجب يترك $\gamma$ دون تغيير، مما يعني عدم الحاجة إلى ثابت طول مقياسي.
- المحلية (Locality): قيمة $\gamma$ عند الرتبة $k$ تعتمد فقط على أقرب $k$ مسافة. النقاط الأبعد لا تؤثر على تقدير حدود العنقود المحلي.

2. إزاحة المتوسط التكيفية

بمجرد تقدير $\hat{n}_i$ لكل نقطة، تقوم هذه القيم بقيادة عملية إزاحة المتوسط:

تعريف النواة: تُستخدم نواة غاوسية مبتورة $K(x; h, \omega)$ $K (x; h, ω)$ .
- عرض النطاق ( $h$ ): يُحسب كالانحراف المعياري لتوزيع المسافة المحلي المقتصر على عدد العناصر المقدر $\hat{n}_i$ .
- العتبة ( $\omega$ ): تُضبط عند المسافة المرتبة رقم $\hat{n}_i$ ، مما يؤدي فعلياً إلى بتر النواة عند نصف قطر العنقود المقدر. النقاط التي تتجاوز هذا النصف قطر تتلقى وزناً صفرياً.
التكيف عالي الأبعاد: تم اقتراح نواة معدلة (المعادلة 6) للأبعاد العالية لتعويض المسافات، وذلك لمنع المسافة الذاتية (الصفر) من الهيمنة على الوزن وتجنب عدم الاستقرار العددي.
زيادة المساحة التدريجية: للتخفيف من التحيز الإيجابي في تقديرات عدد العناصر للنقاط القريبة من حدود العنقود، تزيد الخوارزمية تدريجياً من عدد النقاط التي يتم النظر فيها ( $n_k^*$ ) خلال خطوات إزاحة المتوسط التكرارية، مما يسمح للمتوسط الموزون بالتقارب نحو النمط الحقيقي.

3. التعامل مع التقديرات "السيئة"

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

المساهمات الرئيسية

البارامترية القائمة على عدد العناصر: تقدم الورقة طريقة لاشتقاق عرض النطاق ونصف قطر النواة لـ AMS مباشرة من عدد عناصر العنقود المحلي المقدر، مما يلغي الحاجة إلى معامل عرض نطاق عالمي.
دالة $\gamma$ : دالة مبتكرة، مستقلة عن المقياس، ومحلية للكشف عن الحد الأدنى للكثافة بين نمطين في توزيع المسافة، مما يتجنب مشكلات اختيار عرض النطاق المتأصلة في KDE.
الاستقلال عن المقياس والعنقود: لا تتطلب الخوارزمية معرفة عدد العناقيد كمدخل، وهي مستقلة عن مقياس البيانات.
استراتيجية النواة المبتورة: من خلال بتر النواة عند نصف قطر العنقود المقدر، تضمن الطريقة عدم تلوث المتوسط الموزون المحلي بنقاط بعيدة (من عناقيد أخرى).

النتائج التجريبية

قيم المؤلف الخوارزمية على مجموعتين من المعايسات:

المقارنة مع WAMS لـ Ren et al. (2014):
- تم الاختبار على 9 مجموعات بيانات (Iris, Yeast, Steel, USPS, CTG, Letter, Image, Pen, Wave).
- حققت الطريقة المقترحة مؤشر راند (Rand Index) أعلى من خوارزمية Weighted Adaptive Mean Shift (WAMS) في 7 من أصل 9 مجموعات بيانات.
- تفوقت على جميع النماذج المرجعية المنشورة (WAMS, k-means, EM, Single-linkage) في هذه المجموعات السبع.
- كانت النتائج تنافسية في المجموعتين المتبقيتين (USPS, Image)، رغم أن المؤلف يشير إلى عدم قدرته على الوصول إلى تفاصيل التنفيذ المحددة لتلك النماذح للتحقيق الكامل في التباين.
المقارنة مع معيار Gagolewski (2022):
- تم الاختبار على 8 مجموعات بيانات من UCI (Ecoli, Glass, Ionosphere, Sonar, Statlog, WDBC, Wine, Yeast).
- أدت الخوارزمية أداءً تنافسياً مقابل الطرق الراسخة (GIc, EM, k-means, Spectral, Birch) في مجموعات البيانات التي أظهر فيها مؤشر راند فصلاً واضحاً بين الطرق.
- قصور: تواجه الخوارما خوارزمية صعوبة عندما يحتوي أكبر عنقود على أكثر من 50% من البيانات (الـ maxBoundary الافتراضي هو $0.5n$ ). في مثل هذه الحالات (مثل Ionosphere, Sonar, WDBC)، تفشل الخوارزمية في تمثيل الفئة الأكبر كعنقود واحد، مما يؤدي إلى انخفاض مؤشرات راند. يشير المؤلف إلى أن ضبط معامل maxBoundary يمكن أن يحسن النتائج في هذه المجموعات المحددة، ولكنه يتطلب معرفة بتوزيع البيانات.

الأهمية والادعاءات

تدعي الورقة أن الخوارزمية المقترحة تنافسية ضمن عائلة إزاحة المتوسط التكيفية وتوفر ميزة متميزة بـ عدم اشتراط معرفة عدد العناقيد كمدخل.

التواضع: يقر المؤلف بأن مُقدر عدد العناصر هو "نموذج أولي وظيفي أول" و"عمل قيد التطوير". كما يعترف بأن المقارنة ضد خوارزمية WAMS تغطي عضواً واحداً فقط من عائلة إزاحة المتوسط التكيفية، وأن مقارنات أوسع لا تزال مطلوبة.
الاستقلال عن المقياس: يؤكد المؤلف أن استقلال المُقدر عن المقياس يمثل تحسيناً نظرياً كبيراً، لأنه يزيل الحاجة إلى اختيار ثابت طول لبيانات المقياس.
المحلية: يتم تسليط الضوء على محلية الطريقة الصارمة، مما يضمن عدم تشويه تقدير العنقود المحلي بواسطة نقاط البيانات البعيدة.
العمل المستقبلي: تشير الورقة إلى أن مهمة تقدير عدد العناصر نفسها هي أمر جديد ويستحق مزيداً من البحث. قد تشمل التحسينات المستقبلية استبدال الحدود الثابتة بالبحث عن النمط الخوارزمي (مثل إزاحة المتوسط أحادي البعد) وتحسين التعامل مع معامل maxBoundary لجعله يعتمد كلياً على البيانات.

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