نشر باحثون من Meta FAIR خوارزمية e-means، التي تُقدم كبديل مباشر لخوارزمية k-means الخاصة بـ Lloyd. وفقًا للمؤلفين، تصل الخسارة التي تحققها في 1.4 إلى 2.6 عصرًا إلى نفس مستوى الخسارة التي يحققها k-means الخاص بـ Lloyd في 25 عصرًا. وهي متاحة ضمن FAISS 1.16.0، تحت الوحدة faiss.contrib.e_means.
k-means هي طريقة تجميع تقوم بتقسيم البيانات إلى مجموعات، يمثل كل منها مركز يُسمى centroïde. بالنسبة لمن يبنون فهارس متجهية أو أدوات ترميز أو خطوط تجهيز البيانات، غالبًا ما يكون هذا الحساب هو أبطأ خطوة خارجية، وهذا بالضبط ما تستهدفه e-means.
متوسط متحرك بدلاً من إعادة حساب كاملة
جميع أشكال k-means تحتفظ، لكل مجموعة، بمجموع S وعدد N، حيث يكون centroïde هو حاصل قسمة S على N. وتختلف بشكل رئيسي في كيفية تحديث S وN. تعيد خوارزمية Lloyd حساب هذه القيم من كامل البيانات في كل تكرار. أما MacQueen، في عام 1967، فكان يضيف إحصائيات الدُفعات بشكل مستمر بحيث لا تختفي التخصيصات القديمة أبدًا.
تتبنى e-means مسارًا وسطًا: حيث تخفف الإحصائيات القديمة بمعدل α، وفق الصيغة S ← (1−α)S + αs، ونفس الشيء لـ N. وهكذا تختفي التخصيصات القديمة تدريجيًا، ويتبع centroïdes البيانات الحديثة. حالة Lloyd تعادل دفعة كاملة مع α = 1. على مجموعة بيانات DEEP، تقع هذه الحالة بنسبة 1.8% أعلى من أفضل خسارة تم الحصول عليها.
اختبر المؤلفون أيضًا هبوطًا تقليديًا للتدرج. في أفضل تكوين له، يبقى بنسبة 1.6% أعلى من EMA على DEEP و0.4% على SIFT. ويفترضون أن طريقة EMA تتفوق لأن centroïdes تبقى دائمًا داخل الغلاف المحدب لنقاطها المخصصة.
معاملات محددة بقوانين مقياسية
تحدد قانونان مقياسيان، تم ضبطهما تجريبيًا، حجم الدفعة B والخطوة الابتدائية α0 بناءً على حجم مجموعة البيانات وعدد المجموعات وعدد العصور. على مجموعات بيانات منفصلة، يبلغ الوسيط للندم 0.07% لقانون الخطوة. تتبع الخطوة بعد ذلك جدولًا زمنيًا جيبيًا، من α0 حتى 0.1α0. يكمل النظام آليتان أخريان: إعادة تنشيط المجموعات « الميتة »، أي التي تقل عن حد معين ويتم تنشيطها مجددًا بتقسيم مجموعة كبيرة، وإنهاء الحساب على المتوسط الدقيق للعصر الأخير.
وفقًا للمؤلفين، الأداء المعلن أسرع من Flash-KMeans على GPU بمعدل 10 إلى 45 مرة، وأسرع من Faiss k-means على CPU بمعدل 8 إلى 15 مرة. على معيار VIBE، استغرقت 11 مجموعة بيانات تضم تمثيلات بين 1.6 و2.4 عصرًا. وللتوسع، تم تقسيم مجموعة DINO10B، التي تضم 10 مليارات تمثيل بُعدي 1024، إلى 16.7 مليون مجموعة في 2.5 عصر. تم الحصول على النتائج على GPU من نوع H100. بالنسبة للتكوينات التي تحتوي على 16 مليون centroïde، تصل المجمعات في float32 إلى 64 جيجابايت، مما يستلزم توزيع المجموعات على عدة وحدات GPU.
عرض توضيحي على خيط CPU واحد، نُشر في سلسلة الإعلانات، أعطى 4.39 ثانية لـ Lloyd على 25 عصرًا، مقابل 0.43 ثانية لـ e-means على 2.2 عصر. تُوزع e-means برخصة MIT عبر FAISS.
