خوارزمية كيه- ميدويدز (K-Medoids)

<![CDATA[

مقدمة عن التجميع (Clustering)

التجميع هو عملية تقسيم مجموعة من البيانات إلى مجموعات أو تجمعات، بحيث تكون العناصر داخل كل مجموعة متشابهة مع بعضها البعض أكثر من تشابهها مع العناصر الموجودة في مجموعات أخرى. يعتبر التجميع من تقنيات التعلم غير الخاضع للإشراف (Unsupervised Learning)، حيث لا يتم توفير علامات أو تصنيفات مسبقة للبيانات. الهدف الرئيسي من التجميع هو اكتشاف الأنماط والتجمعات الطبيعية الموجودة في البيانات.

الفرق بين كيه-مينز وكيه-ميدويدز

أحد أهم الفروق بين كيه-مينز وكيه-ميدويدز هو طريقة اختيار مركز المجموعة (centroid). في خوارزمية كيه-مينز، يتم حساب مركز المجموعة على أنه متوسط نقاط البيانات في المجموعة. وهذا يعني أن مركز المجموعة قد لا يكون بالضرورة نقطة بيانات فعلية من مجموعة البيانات الأصلية. على النقيض من ذلك، في خوارزمية كيه-ميدويدز، يتم اختيار مركز المجموعة ليكون نقطة بيانات فعلية من مجموعة البيانات، وهذا ما يسمى “ميدويد” (medoid). الميدويد هو النقطة التي تكون متوسط المسافة بينها وبين جميع النقاط الأخرى في المجموعة هو الأدنى.

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

خطوات خوارزمية كيه-ميدويدز

تتكون خوارزمية كيه-ميدويدز من الخطوات التالية:

التهيئة (Initialization): يتم اختيار عدد المجموعات (K) بشكل مسبق. يتم تحديد K ميدويدز أولية بشكل عشوائي من بين نقاط البيانات.
التخصيص (Assignment): يتم تعيين كل نقطة بيانات إلى أقرب ميدويد بناءً على مقياس المسافة (مثل المسافة الإقليدية).
التحديث (Update): لكل مجموعة، يتم تحديد ميدويد جديد. يتم اختيار الميدويد الجديد من بين نقاط البيانات داخل المجموعة، وذلك باختيار النقطة التي تقلل من مجموع المسافات بينها وبين جميع النقاط الأخرى في المجموعة.
التكرار (Iteration): تتكرر الخطوات 2 و 3 حتى تتوقف مراكز المجموعات عن التغير (أو تتغير بمقدار ضئيل) أو حتى يتم الوصول إلى عدد محدد مسبقًا من التكرارات.

اختيار قيمة K

يعد اختيار قيمة K (عدد المجموعات) أمرًا بالغ الأهمية. لا توجد طريقة مثالية لتحديد قيمة K، ولكن هناك العديد من التقنيات التي يمكن استخدامها:

طريقة الكوع (Elbow Method): يتم تشغيل الخوارزمية لعدد من قيم K المختلفة، ويتم رسم قيم مؤشر ما (مثل مجموع التربيعات داخل المجموعات – Within-Cluster Sum of Squares (WCSS)) مقابل قيم K. يبحث المرء عن “كوع” في الرسم البياني، وهو النقطة التي يبدأ عندها الانخفاض في WCSS في التباطؤ.
طريقة الظل (Silhouette Method): تحسب هذه الطريقة قيمة معامل الظل لكل نقطة بيانات. يعبر معامل الظل عن مدى تشابه نقطة البيانات مع نقاط البيانات الأخرى داخل مجموعتها ومدى اختلافها عن نقاط البيانات في المجموعات الأخرى. يتم حساب متوسط معاملات الظل لجميع نقاط البيانات للحصول على درجة تقييم للمجموعة. يتم اختيار قيمة K التي تعطي أعلى درجة تقييم.
طرق أخرى: يمكن استخدام طرق أخرى مثل تحليل الفجوة (Gap Statistic) أو استخدام المعرفة المسبقة بالمجال أو المشاكل التي يتم تحليلها.

مقاييس المسافة

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

المسافة الإقليدية (Euclidean Distance): تقيس المسافة المباشرة بين نقطتين في الفضاء.
مسافة مانهاتن (Manhattan Distance): تقيس مجموع الفروق المطلقة بين إحداثيات نقطتين.
مسافة ميكوفسكي (Minkowski Distance): تعميم لمسافة إقليدية ومانهاتن.

يعتمد اختيار مقياس المسافة على طبيعة البيانات والمشكلة التي يتم حلها.

تطبيقات كيه-ميدويدز

تستخدم خوارزمية كيه-ميدويدز في مجموعة متنوعة من المجالات والتطبيقات، بما في ذلك:

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

مزايا كيه-ميدويدز

تتميز خوارزمية كيه-ميدويدز بعدة مزايا:

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

عيوب كيه-ميدويدز

على الرغم من مزاياها، إلا أن كيه-ميدويدز لديها بعض العيوب:

الحساسية للتهيئة الأولية: يمكن أن تتأثر النتائج باختيار الميدويدز الأولية.
التعقيد الحسابي: تتطلب حسابات المسافات المتكررة، مما قد يجعلها أبطأ من كيه-مينز على مجموعات البيانات الكبيرة.
صعوبة التعامل مع البيانات ذات الأبعاد العالية: قد تواجه صعوبة في التعامل مع مجموعات البيانات ذات عدد كبير من الأبعاد.

تحسينات على كيه-ميدويدز

تم اقتراح العديد من التحسينات على خوارزمية كيه-ميدويدز لتحسين أدائها:

PAM (Partitioning Around Medoids): هي النسخة الأصلية من الخوارزمية.
CLARA (Clustering LARge Applications): تم تصميمها للتعامل مع مجموعات البيانات الكبيرة عن طريق أخذ عينات من مجموعة البيانات.
CLARANS (Clustering Large Applications based on RANdomized Search): تحسين على CLARA يجمع بين أساليب العينات و البحث العشوائي.

كود مثال (Python)

يوضح هذا الكود مثالاً بسيطًا لكيفية تطبيق خوارزمية كيه-ميدويدز باستخدام مكتبة scikit-learn في Python:

    
    from sklearn_extra.cluster import KMedoids
    import numpy as np

    # إنشاء بيانات وهمية
    X = np.array([[1, 2], [1.5, 1.8], [5, 8], [8, 8], [1, 0.6], [9, 11]])

    # تطبيق خوارزمية كيه-ميدويدز
    kmedoids = KMedoids(n_clusters=2, random_state=0)
    kmedoids.fit(X)

    # الحصول على مراكز المجموعات
    medoids = kmedoids.medoid_indices_

    # الحصول على التسميات (المجموعات)
    labels = kmedoids.labels_

    print("Medoids:", X[medoids])
    print("Labels:", labels)

في هذا المثال، يتم إنشاء بيانات وهمية ذات بعدين. ثم يتم تطبيق خوارزمية كيه-ميدويدز مع مجموعتين (K=2). بعد ذلك، يتم عرض مراكز المجموعات والتسميات (مجموعات كل نقطة بيانات).

خاتمة

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