K-Means على نطاق واسع: لماذا تنهار وما البديل؟

K-means هي الخوارزمية التي يتعلمها الجميع في مقرر تعلم الآلة التمهيدي، ثم يستخدمونها بشكل خاطئ طوال بقية مسيرتهم المهنية. بساطتها خادعة: اختر K مركزًا للعناقيد، ثم أسند كل نقطة إلى أقرب مركز، وحرّك المراكز إلى متوسط النقاط المسندة إليها، وكرر. ثلاثة أسطر من الشيفرة الزائفة. المشكلة أن هذه البساطة تُخفي سلسلة من الألغام التي تنفجر عند تطبيقها على بيانات حقيقية وبحجم كبير.

عند 10,000 نقطة، تنتهي K-means خلال أجزاء من الثانية، ولا يقلق أحد بشأن تفاصيل التنفيذ. عند 10 ملايين نقطة، يمكن أن يغيّر اختيار طريقة التهيئة زمن التشغيل بمقدار 100 ضعف. وعند مليار نقطة، لا تتسع الخوارزمية القياسية في الذاكرة، فتحتاج إلى مقاربات مختلفة جوهريًا. تتناول ورقة بحثية حديثة عن Flash-KMeans هذه المشكلة تحديدًا، وتحقق نتائج K-means الدقيقة مع استهلاك أقل بكثير للذاكرة وتقارب أسرع. دعنا نتعمق في ما يجعل K-means صعبة على نطاق واسع، وكيف تحل المتغيرات الحديثة هذه المشكلة.

ماذا تفعل K-means القياسية فعلًا

خوارزمية Lloyd، وهي ما يقصده الناس عندما يقولون 'k-means'، لها خطوتان في كل تكرار. خطوة الإسناد: لكل نقطة بيانات، تحسب المسافة إلى جميع المراكز الـK وتُسندها إلى الأقرب. خطوة التحديث: تعيد حساب كل مركز بوصفه متوسط جميع النقاط المسندة إليه.

import numpy as np
def kmeans_lloyd(X, K, max_iter=100):
n, d = X.shape
# Random initialization (bad, but we'll fix this later)
centroids = X[np.random.choice(n, K, replace=False)]
for _ in range(max_iter):
# Assignment: O(n * K * d) — this is the bottleneck
distances = np.linalg.norm(X[:, None] - centroids[None, :], axis=2)
labels = np.argmin(distances, axis=1)
# Update: O(n * d)
new_centroids = np.array([
X[labels == k].mean(axis=0) for k in range(K)
])
if np.allclose(centroids, new_centroids):
break
centroids = new_centroids
return labels, centroids

تكلف خطوة الإسناد O(n × K × d) في كل تكرار، حيث n عدد النقاط وK عدد العناقيد وd عدد الأبعاد. بالنسبة إلى n = 1 مليار و K = 1000 و d = 128 (وهو سيناريو واقعي لتجميع التضمينات)، فهذا يعني 128 تريليون عملية فاصلة عائمة في كل تكرار. حتى بقدرة حوسبة تبلغ تيرافلوب واحدًا، يستغرق ذلك 128 ثانية لكل تكرار، وعادةً تحتاج K-means إلى 10 إلى 50 تكرارًا للتقارب.

مشكلة التهيئة

قبل أن تنفذ K-means أي تكرار، عليها أن تختار مواضع المراكز الأولية. هذا الاختيار أهم بكثير مما يدركه معظم الناس، فالتهيئة السيئة قد تقود إلى حل يتقارب نحوه الخوارزمية وهو أسوأ من الأمثل بهامش كبير وغير محدود.

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

K-means++ (Arthur و Vassilvitskii، 2007) هو الحل القياسي لهذه المشكلة. تختار المركز الأول عشوائيًا، ثم تختار كل مركز لاحق باحتمال يتناسب مع مربع مسافته عن أقرب مركز موجود. النقاط البعيدة عن أي مركز قائم تكون أكثر عرضة للاختيار، فتنتشر المراكز الأولية على البيانات. يوفر هذا ضمانة تقريب بمقدار O(log K)، أي أن الحل مضمون ضمن عامل O(log K) من الأمثل.

def kmeans_plus_plus_init(X, K):
n, d = X.shape
centroids = [X[np.random.randint(n)]]
for _ in range(1, K):
# Distance from each point to nearest existing centroid
dists = np.min([
np.sum((X - c) ** 2, axis=1) for c in centroids
], axis=0)
# Sample proportional to distance squared
probs = dists / dists.sum()
next_idx = np.random.choice(n, p=probs)
centroids.append(X[next_idx])
return np.array(centroids)

لكن هناك مشكلة: تهيئة K-means++ نفسها تكلف O(n × K × d)، إذ تحتاج إلى K مرور عبر مجموعة البيانات بأكملها. مع قيم كبيرة لـK وn، قد تستغرق التهيئة وقتًا أطول من عدة تكرارات من خوارزمية Lloyd. تقلل النسخ القابلة للتوسع مثل k-means|| (Bahmani وآخرون، 2012) عدد المرورات، عبر أخذ عينات زائدة من المرشحين بالتوازي، ثم دمجهم في K مركزًا.

جدار الذاكرة

تحتاج K-means القياسية إلى أن تكون مجموعة البيانات كلها في الذاكرة في آنٍ واحد. في خطوة الإسناد، يجب الوصول إلى كل نقطة بيانات ومقارنتها بكل مركز. مع مليار متجه بأبعاد 128 من نوع float32، تحتاج البيانات وحدها إلى 512 غيغابايت، وهي سعة تفوق ما تملكه معظم الأجهزة المفردة.

الحل الساذج هو mini-batch k-means: تأخذ عينة عشوائية من النقاط في كل تكرار، وتحدّث المراكز بناءً على هذه العينة. هذا الأسلوب يعمل، لكنه يتقارب ببطء أكبر، وإلى حل مختلف قليلًا (وغالبًا أسوأ قليلًا) عن K-means الدقيقة. بالنسبة إلى كثير من التطبيقات، يكون فقدان الجودة مقبولًا. أما في حالات أخرى، مثل كتب الشيفرات الخاصة بالتكميم في البحث المتجهي، فإن الفرق في الجودة مهم.

يتبع Flash-KMeans نهجًا مختلفًا. بدلًا من معالجة مجموعة البيانات كاملة في الذاكرة، يستخدم مرورًا متدفقًا مع تخزين مؤقت ذكي. الفكرة الأساسية: معظم النقاط لا تغير عناقيدها بين التكرارات. إذا كانت نقطة ما في العنقود 7 بثبات (أي أقرب بكثير إلى المركز 7 من أي مركز آخر)، فإن فحص جميع المسافات الـK يكون عملًا مهدورًا. من خلال الحفاظ على حدود للمسافات، يستطيع Flash-KMeans تخطي حساب المسافة الكامل لمعظم النقاط في معظم التكرارات.

تحسينات متباينة المثلث

تستخدم خوارزمية Elkan (2003) متباينة المثلث لتخطي حسابات المسافات غير الضرورية. تقول المتباينة: المسافة من النقطة P إلى المركز A لا تتجاوز مجموع المسافة من P إلى المركز B والمسافة من B إلى A. إذا كنت تعرف أن P مسندة حاليًا إلى المركز B، وتعرف المسافة بين المركزين A وB، فيمكنك أحيانًا أن تثبت أن A بعيد جدًا عن P دون حساب المسافة الفعلية.

عمليًا، يلغي هذا ما بين 80% و95% من حسابات المسافات بعد التكرارات القليلة الأولى، حين تكون معظم النقاط قريبة بالفعل من مركزها الصحيح. أما حسابات المسافات المتبقية فتخص النقاط القريبة من حدود العناقيد، وهي وحدها التي قد تغير إسنادها فعلًا.

المقايضة هنا أن خوارزمية Elkan تحتاج إلى O(n × K) من الذاكرة الإضافية لتخزين حدود المسافات (حدود دنيا من كل نقطة إلى كل مركز، وحدود عليا إلى المركز المسند). مع قيم كبيرة لـK، قد تكون تكلفة الذاكرة هذه كبيرة. تخفض خوارزمية Hamerly هذه التكلفة إلى O(n) بالاحتفاظ بحد أدنى واحد فقط لكل نقطة، لكن بعدد أقل من الحسابات المتخطاة.

تسريع وحدات معالجة الرسوميات

K-means محرجة التوازي في خطوة الإسناد: حساب المسافة لكل نقطة مستقل عن غيره. هذا يجعلها مناسبة بشكل طبيعي لتسريع وحدات معالجة الرسوميات. تتضمن مكتبة cuML من NVIDIA ومكتبة FAISS من Facebook تنفيذات K-means تعمل على GPU، وتحقق تسريعًا يتراوح بين 10 و50 ضعفًا مقارنة بالتنفيذات على المعالج للمجموعات الكبيرة من البيانات.

المشكلة أن ذاكرة GPU محدودة. يملك A100 ذاكرة بسعة 80 غيغابايت، وهي تكفي لنحو 150 مليون متجه بأبعاد 128. أما مجموعات البيانات الأكبر فتتطلب إما تقسيمًا على عدة وحدات GPU، أو نهجًا متدفقًا يُحمَّل فيه جزء من البيانات، ويُعالَج على GPU، ثم تُجمع النتائج على المعالج.

# Using FAISS for GPU-accelerated k-means
import faiss
import numpy as np
# 10 million 128-dimensional vectors
n, d, K = 10_000_000, 128, 1000
X = np.random.randn(n, d).astype('float32')
# CPU k-means (for comparison)
kmeans_cpu = faiss.Kmeans(d, K, niter=20, verbose=True)
kmeans_cpu.train(X)  # ~120 seconds
# GPU k-means (single GPU)
kmeans_gpu = faiss.Kmeans(d, K, niter=20, verbose=True, gpu=True)
kmeans_gpu.train(X)  # ~8 seconds — 15x faster

متى تكون K-means الخيار الخاطئ

قبل تحسين تنفيذ K-means لديك، فكّر فيما إذا كانت هذه الخوارزمية هي الصحيحة أصلًا. فهي تفترض افتراضات قوية لا تنطبق على كثير من مجموعات البيانات الحقيقية.

• عناقيد كروية. تفترض K-means أن العناقيد كروية تقريبًا ومتساوية الحجم. إذا كانت عناقيدك مستطيلة، أو ذات أشكال غير منتظمة، أو متفاوتة الأحجام بشكل كبير، فستقسم K-means العناقيد الكبيرة وتدمج الصغيرة. تتعامل نماذج الخليط الغاوسي (GMMs) مع العناقيد الإهليلجية، بينما تتعامل DBSCAN مع الأشكال الاعتباطية.
• معرفة قيمة K مسبقًا. يجب تحديد عدد العناقيد مسبقًا. إذا لم تكن تعرف K، فستحتاج إلى تشغيل K-means عدة مرات بقيم مختلفة، واستخدام مقياس مثل معامل Silhouette أو طريقة الكوع لاختيار الأفضل. هذا يضاعف إجمالي الحوسبة بعدد قيم K التي تجربها.
• مسافة إقليدية. تستخدم K-means مسافة إقليدية افتراضيًا. بالنسبة إلى تضمينات النصوص، يكون التشابه الجيبي (cosine similarity) أنسب عادةً. يمكنك تجاوز ذلك بتطبيع المتجهات وفق معيار L2، مما يجعل المسافة الإقليدية مكافئة لمسافة الجيب، لكن من السهل نسيان ذلك.
• الحساسية للقيم الشاذة. نقطة شاذة واحدة بعيدة عن أي عنقود ستسحب المركز المسند إليها نحوها. الخوارزميات المتينة مثل k-medoids (التي تستخدم الوسيط بدلًا من المتوسط) تتعامل مع القيم الشاذة بشكل أفضل، لكنها أغلى حسابيًا.

نصائح عملية

بعد استخدام K-means على مجموعات بيانات تتراوح من آلاف النقاط إلى مليارات، إليك ما أراه الأهم:

1. استخدم دائمًا تهيئة K-means++. التهيئة العشوائية لا تستحق المخاطرة أبدًا. الفرق في جودة العناقيد النهائية يبلغ غالبًا من 10% إلى 30%، وK-means++ تضيف عبئًا ضئيلًا لقيم K الصغيرة والمتوسطة.
2. شغّل الخوارزمية عدة مرات. تجد K-means حلًا أمثل محليًا، لا عامًا. شغّلها من 5 إلى 10 مرات ببذور عشوائية مختلفة، وخذ أفضل نتيجة (أقل مجموع للمسافات داخل العناقيد). هذا تأمين رخيص ضد التشغيلات السيئة.
3. طبّع خصائصك. إذا كانت إحدى الخصائص تتراوح بين 0 و1000000 وأخرى بين 0 و1، فإن الخاصية ذات المدى الكبير ستهيمن على حساب المسافة. قم بالتوحيد المعياري (طرح المتوسط والقسمة على الانحراف المعياري)، أو التطبيع بين الحد الأدنى والأقصى قبل التجميع.
4. استخدم FAISS للتجميع واسع النطاق. إذا كان لديك أكثر من مليون نقطة، فستكون K-means في scikit-learn بطيئة. تنفيذ FAISS محسّن بشكل كبير، ويدعم تسريع GPU مباشرة دون إعدادات إضافية.
5. فكّر في الطرق التقريبية للاستكشاف. mini-batch k-means أسرع بعشر مرات من K-means الدقيقة، وتعطي نتائج جيدة غالبًا بما يكفي للاستكشاف. استخدم K-means الدقيقة للتجميع الإنتاجي حيث تهم الجودة.

K-means من تلك الخوارزميات السهلة في الاستخدام، والصعبة في الاستخدام الجيد، والتي تستحق الفهم العميق. الفجوة بين تنفيذ ساذج وآخر محسّن، سواء من حيث السرعة أو جودة النتائج، هائلة. على نطاق صغير لا يهم أي من هذا. أما في النطاق الذي يهم فيه، فإن فهم التهيئة وإدارة الذاكرة وتقليم المسافات وتسريع GPU هو الفرق بين تجميع يستغرق ساعات وتجميع يستغرق دقائق.