مرجع
آخر الزيارات

خوارزمية تصنيفية

383 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: الخوارزمية التصنيفية أو التجميع بالمتوسط أو التجمع بالمتوسط (بالانجليزية: k-means clustering) هي طريقة لتكميم المتجهات، في الأصل في علم معالجة الإشارة والتي اشتهر استخدامها في تطبيقات التصنيف (cluster analysis) خلال عملية التنقيب في…. تتناول المقالة 5 أقسام، منها «تصنيف أولي»، «تحديث المراكز» و«الوصف».
المحتويات
  1. تصنيف أولي
  2. تحديث المراكز
  3. الوصف
  4. التاريخ
  5. التطبيق الخوارزمي

على سبيل التعريف، الخوارزمية التصنيفية أو التجميع بالمتوسط أو التجمع بالمتوسط (بالانجليزية: k-means clustering) هي طريقة لتكميم المتجهات، في الأصل في علم معالجة الإشارة والتي اشتهر استخدامها في تطبيقات التصنيف (cluster analysis) خلال عملية التنقيب في البيانات. الهدف من هذه الخوارزمية هو تقسيم عدد من العناصر (بيانات n) إلى عدد k من الأقسام والتي فيها ينضوي كل عنصر إلى القسم ذي النقطة المركزية الأقرب (المتوسط)، حيث تمثل النقطة المركزية الأساس الذي يتم عليه تقسيم البيانات وتصنيفها ولهذا أتت التسمية k-means clustering. نتيجة التصنيف هي القسمة إلى مناطق فورونية. ونتناول فيما يلي مزيدًا من التفاصيل.

ومن جهة أخرى، المشكلة تكمن في صعوبة الحساب، بمعنى صعوبة الوصول إلى نتيجة يتم على أساسها تضمين عنصر ما إلى قسم معين. وبرغم التشابه مع خوارزمية تعظيم التوقع (expectation-maximization algorithm EMA)، إلا أن ال k-means لا تُنتج أشكال مختلفة للبيانات المُجزئة كما تفعل ذلك الأولى (EMA).

تصنيف أولي

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

حيث كل عنصر يتم دمجه إلى منطقة مركزية واحدة بالتحديد.

تحديث المراكز

معرض صور

من جهة ثانية، في هذه الخطوة يتم حساب النقاط المركزية من جديد بحيث تكون المراكز المحدثة للقطع (clusters) الجديدة.

كذلك، حساب النقاط المركزية الجيدية (الأنسب) يعني كذلك تقليل الحساب المتوسطي بين العناصر ومراكزها (WCSS) داخل كل منطقة.

الوصف

حيث μi هي متوسط العناصر في الجزء Si.

وفي السياق ذاته، S = {S1, S2, ..., Sk} بحيث يؤخذ القيمة الدنيا لمجموع التربيع بين كل عنصر وبين النقاط المركزية والتي عددها k (within-cluster sum of squares (WCSS)). العلاقة الرياضية تُعطى كالآتي:

إضافةً إلى ذلك، نأخذ العناصر المعطاة (x1, x2, ..., xn) ، حيث كل عنصر يمثل متجها بُعده d. بعد تطبيق الخوارزمية على العناصر فيتم تقسيمها حسب التشابه بينها إلى عدد (k ≤ n) k من الأجزاء S:

التاريخ

ومن ناحية أخرى، في سنة 1965 نشر E.W.Forgy نفس الطريقة، ولهذا يتم تسمية الخوارزمية أحيانا على إسمه. تطوير اضافي على الخوارزمية تم نشرها من قِبَل هارتيجان ووونج في 1975/1979.

علاوةً على ذلك، أول من استعمل مصطلح ال "k-means" كان جيمس ماكوين في سنة 1967 بيدَ أن الفكرة خلف هذا المصطلح ترجع إلى هوجو شتاين هاوس في سنة 1957. التطبيق الكلاسيكي للخوارزمية تم اقتراحه من قبل ستوارت لويد في سنة 1957 كتقنية تطبيقية للتضمين الرقمي، إلا أن النشر الأول لم يتم حتى عام 1982.

التطبيق الخوارزمي

ومن جهة أخرى، التطبيق الخوازمي لل k-means يستعمل تقنية تكرار التصنيف. ابتداءً من نقاط عشوائية للمراكز m1(1),...,mk(1) يمر التطبيق في الخطوتين التاليتين:

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.