التجميع باستخدام خوارزمية k -medians

تُعدّ تقنية التجميع باستخدام الوسيط K أسلوبًا لتقسيم البيانات يُستخدم في تحليل التجميع. ^{[ 1 ]} تقوم هذه التقنية بتجميع البيانات في k مجموعة عن طريق تقليل مجموع المسافات - عادةً باستخدام مسافة مانهاتن (L1) - بين نقاط البيانات ووسيط مجموعاتها المُخصصة. تتميز هذه الطريقة بمقاومتها العالية للقيم الشاذة، وهي مناسبة تمامًا للبيانات المنفصلة أو الفئوية. وهي تعميم لخوارزمية الوسيط الهندسي أو الوسيط 1، المُعرّفة لمجموعة واحدة. يُعدّ الوسيط K نوعًا مُعدّلًا من خوارزمية التجميع k -means، حيث يتم حساب الوسيط بدلًا من حساب المتوسط ​​لكل مجموعة لتحديد مركزها . يُؤدي هذا إلى تقليل الخطأ في جميع المجموعات فيما يتعلق بمقياس المسافة ذي المعيار 1 ، بدلًا من مقياس المسافة ذي المعيار 2 التربيعي (الذي تستخدمه خوارزمية k -means).

يرتبط هذا مباشرةً بمسألة الوسيط k : بالنظر إلى فضاء متري${\displaystyle (V,d)}$وعدد صحيح${\displaystyle k}$، تطلب المسألة إيجاد مجموعة من المراكز k${\displaystyle C\subseteq V}$وذلك لتقليل مجموع المسافات من كل عنصر في${\displaystyle V}$إلى أقرب مركز، أي أننا نريد تقليل

${\displaystyle \sum _{u\in V}\min _{v\in C}d(u,v)}$

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

تستخدم الخوارزمية المقترحة تكرارًا على نمط لويد، يتناوب بين خطوة التوقع (E) وخطوة التعظيم (M)، مما يجعلها خوارزمية توقع-تعظيم . في خطوة التوقع، تُسند جميع العناصر إلى أقرب وسيط لها. وفي خطوة التعظيم، يُعاد حساب الوسائط باستخدام الوسيط في كل بُعد على حدة.

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

كثيرًا ما يُخلط بين هذه الخوارزمية وخوارزمية k -medoids . مع ذلك، يجب أن يكون الوسيط (medoid) عنصرًا فعليًا من مجموعة البيانات، بينما في خوارزمية وسيط مسافة مانهاتن متعددة المتغيرات، ينطبق هذا فقط على قيم السمة المفردة. وبالتالي، يمكن أن يكون الوسيط الفعلي مزيجًا من عدة عناصر. على سبيل المثال، إذا كانت لدينا المتجهات (0,1) و(1,0) و(2,2)، فإن وسيط مسافة مانهاتن هو (1,1)، وهو غير موجود في البيانات الأصلية، وبالتالي لا يمكن أن يكون وسيطًا.

تُعدّ خوارزمية التجميع k-medians وثيقة الصلة بتقنيات التجميع التقسيمي الأخرى، مثل k-means و k-medoids ، حيث يكمن الاختلاف الرئيسي بينها في كيفية تحديد مراكز المجموعات ونوع مقياس المسافة المستخدم. وتؤدي هذه الاختلافات إلى سلوكيات متباينة فيما يتعلق بالمتانة والتكلفة الحسابية وقابلية التطبيق على توزيعات البيانات المختلفة. تعمل خوارزمية k-means على تقليل مجموع مربعات المسافات الإقليدية بين نقاط البيانات ومتوسط ​​المجموعة (مركزها). وتستخدم المتوسط ​​الحسابي كممثل للمجموعة، مما يجعلها حساسة للقيم الشاذة والضوضاء، لأن المتوسط ​​يتأثر بشدة بالقيم المتطرفة. في المقابل، تعمل خوارزمية k-medians على تقليل مجموع الفروق المطلقة (عادةً باستخدام مسافة مانهاتن/L1)، مع اختيار الوسيط على طول كل بُعد كمركز للمجموعة. ولأن الوسيط مقاوم للقيم المتطرفة، فإن خوارزمية k-medians تكون عمومًا أكثر متانة في وجود القيم الشاذة. تُركز خوارزمية k-medoids أيضًا على المتانة، ولكن بدلًا من استخدام الوسائط أو المتوسطات المحسوبة، فإنها تختار نقاط البيانات الفعلية (الميدويدات) كمراكز للمجموعات. ^{[ 2 ]} وهذا ما يجعل k-medoids مناسبة بشكل خاص للبيانات غير الإقليدية أو الفئوية. مع ذلك، ولأنها تتضمن تقييم أوجه الاختلاف بين الأزواج والبحث المتكرر عن النقاط التمثيلية، فإنها تميل إلى أن تكون أكثر استهلاكًا للموارد الحاسوبية من كلٍ من k-means و k-medians، خاصةً مع مجموعات البيانات الكبيرة.

• يتضمن ELKI العديد من متغيرات k-means، بما في ذلك k-medians.
• فورتران kmedians
• يتضمن برنامج GNU R خوارزمية k-medians في حزمة "flexclust".
• وسائط ستاتا

• تحليل التجميع
• خوارزمية k -means
• ميدويد
• خيال