خوارزميات تعلم الآلة

هي خوارزميه لجمع عدد من البيانات استادا إلى خصائص وسمات هذه البيانات، وتتم عمليه التجميع من خلال تقليل المسافات بين البيانات ومركز التجمع (cluster centroid).

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

1. حساب إحداثيات مراكز التجميع
2. حساب المساقه بين كل البيانات ومراكز التجميع.
3. تجميع البيانات وتنظيمها في مجموعات بناء على اقل المسافات بين المركز ونقاط البيانات.
4. اعاده تنفيذ الخطوات من 1 – 3 حتى الوصول إلى حاله الثبات

يعتمد أداء هذه الخوارزمية على المواقع الأولية لمراكز التجمع (Centroid)، ومن المستحسن تنفيذ هذه الخوارزمية عدة مرات مع اختلاف المراكز في كل مرة عن المرات السابقة.

نفترض لدينا أربعة أنواع من الأدوية، وكل نوع من الأدوية لديه عدد من السمات، في هذا المثال كل نوع له سمتان.

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

1.القيم الابتدائية لمراكز التجمع: نفترض أن الدواء A والدواء B هما مراكز التجمع الأولى. لتكن c1 و c2 تدل على إحداثيات المراكز، حيث أن(c1=(1,1 و(c2=(2,1.

يبين الشكل 1.1 توزيع أنواع الأدوية المعبر عنها بالمعين الأزرق على المستوى الريكاردي، كما يبين مراكز التجمع الابتدائية، مع الأخذ بعين الاعتبار أن هذه المراكز تم افتراضها بشكل عشوائي.

2. المسافات بين النقاط والمراكز: نحسب المسافة بين مركز التجمع وكل نقطة من النقاط في المستوى. فينتج لدينا مصفوفة من المسافات.

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

3. تجميع النقاط: نحيل كل نقطة إلى مركز تجمع بالاعتماد على أقل مسافة. وهكذا، فان الدواء الأول (A) ينتدب إلى المجموعة الأولى، الدواء الثاني (B) إلى المجموعة الثانية، الدواء الثالث (C) إلى المجموعة الثانية، والدواء الرابع (D) يعود للمجموعة الثانية. ينتج لدينا مصفوفة المجموعات G التي تتكون من القيم 1 و 0، ويكون العنصر في مصفوفة المجموعات يساوي 1 فقط إذا كان الدواء مسند إلى تلك المجموعة.

4. التكرار الأول، تحديد مراكز التجمع: بعد معرفة عناصر كل مجموعة، نحسب مركز جديد لكل مجموعة اعتمادا على هذه العضويات الجديدة، كما يظهر في الشكل 1.2. المجموعة الأولى تتكون من عنصر واحد فقط، وتبقى إحداثيات مركز التجمع الأول كما هي دون تغيير(c1=(1,1.أما المجموعة الثانية والتي تتكون من ثلاث عناصر، تتغير إحداثيات مركز التجمع الثاني بالاعتماد على إحداثيات العناصر الثلاثة:

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

6. التكرار الأول، تجميع النقاط: على غرار الخطوة الثالثة، نحيل كل نقطة إلى مركز تجمع بالاعتماد على أقل مسافة. بالعودة إلى مصفوفة المسافات الجديدة، ننقل الدواء الثاني (B) إلى المجموعة الأولى، بينما تبقى باقي الأدوية كما هي. تظهر مصفوفة المجموعات كالتالي

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

8. التكرار الثاني، المسافات بين النقاط والمراكز: نكرر الخطوة الثانية، فينتج لدينا مصفوفة مسافات جديدة كما يلي:

9. التكرار الثاني، تجميع النقاط:، مرة أخرى نحيل كل نقطة إلى مركز تجمع بالاعتماد على أقل مسافة.

ينتج لدينا في النهاية. بمقارنة التجمع بين التكرار الأول والتكرار الثاني، نلاحظ أن المجموعات لم تتغير من حيث عناصرها. هذا يعني أن عملية الحسابات في ال(k-mean clustering) وصلت إلى حالة الثبات، وهذا يعني أن هذه الخوارزمية لم تعد بحاجة إلى المزيد من التكرار، وبالتالي حصلنا على النتيجة النهائية للتجميع.

ال(Fuzzy C-means Clustering) تعتمد على الفكرة الأساسية من ال(k-means Clustering)، مع فارق واحد هو أن في ال(FCM) كل نقطة بيانات تنتمي إلى مجموعة على درجة من عضوية الصف، في حين أن كل نقطة بيانات في ال(KM) اما أن تنتمي المجموعة أو لا تنتمي.

توظف ال(FCM) تقسيم عشوائي(ضبابي)، كما أنه يمكن لنقطة معينة أن تنتمي لعدة مجموعات مع درجة من الانتماء التي يحددها عضوية الصفوف بين 0 و 1.

يسمح لمصفوفة العضوية (U) أن تكون فيها قيم العناصربين 0 و 1. مع ذلك، حاصل جمع درجات انتماء نقطة بيانات لجميع المجموعات دائما يعادل:

كما أن ال(Cost Function) لل(FCM) هو:.

حيث أن uij تكون بين 0 و 1، ci هي عبارة عن مركز التجمع في المجموعة الضبابية i، هي المسافة الاقليدية بين مركز التجمع i ونقطة البيانات j، كما أن هي عبارة عن (weighting exponent).

هنالك شروط ضرورية لايصال ال(Cost Function) للحد الأدنى وهي:

تعمل هذه الخوارزمية بشكل متكررمن خلال الشرطين السابقين إلى أن لا يلاحظ أي تحسن. في عملية (batch mode)، تحدد ال(FCM) مراكز التجمع ci ومصفوفة العضوية U باستخدام الخطوات التالية:

1. وضع قيم ابتدائية عشوائية بين 0 و 1 في عناصر مصفوفة العضوية U
2. حساب مراكز التجمع الضبابي ci، حيث أن i=1,……..,c.
3. حساب ال(Cost Function). ويتم التوقف اما إذا كانت نتيجة ال(Cost Function) ما دون قيمة تحمل معينة، أو أن التحسن في تلك النتيجة من خلال التكرار السابق ما دون حد معين.
4. حساب مصفوفة العضوية الجديدة U باستخدام المعادلة التالية:

كما هو الحال في ال(KM)، يعتمد أداء ال(FCM) على قيم مصفوفة العضوية الابتدائية؛ فمن المستحسن أن تنفذ هذه الخوارزمية عدة مرات، في كل مرة تكون البداية بقيم نقاط بيانات مختلف

(Mountain Clustering)هي طريقة بسيطة لإيجاد مراكز التجمعات بالاعتماد على حساب الكثافة من خلال ما يدعى بال(Mountain Function). كما يمكن استخدام هذه الطريقة لإيجاد مراكز التجمعات بشكل تقريبي، مما يسهل استخدامها كوسيلة ابتدائية قبل الدخول في مراحل تجميع أكثر تعقيدا.

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

المرحلة الثانية، يتم تتابع بناء ال(MF) والذي يمثل قياس كثافة البيانات. ذروة(ارتفاع) ال(MF) عند النقطة v؟V تعادل

حيث أن xi هي نقطة i من البيانات، وs هو ثابت تطبيقي محدد، يتبين من المعادلة السابقة أن قياس كثافة البيانات يتأثر بكل النقاط xi في مجموعة البيانات، وقياس كثافة البيانات يتناسب عكسيا مع المسافة بين نقاط البيانات xiو النقطة الموجودة في الv(MF. الثابت يحدد الذروة والانحدار لل (MF) الناتج.

المرحلة الثالثة تنطوي على اختيار مراكز التجمعات عن طريق هدم ال(MF) بشكل تسلسلي. يحدد مركز التجمع الأول ci من خلال اختيار النقطة التي لها أعلى قياس للكثافة. يتم تحديد مركز التجمع الثاني من خلال القضاء على تأثير التجمع الأول. ويتم ذلك من خلال إعادة تشكيل ال(MF)، ويتم تشكيل ال(MF) الجديد من خلال

القيمة الطروحة في المعادلة السابقة تزيل أثر المجموعة الأولى. من الملاحظ أن بعد عملية الطرح تقل قيمة ال(MF) الجديدة mnew(v) لتصل إلى الصفر عند v=c1.

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

المشكلة في طريقة التجمع السابقة (Mountain Clustering) ، هي أن العمليات الحسابية تزداد طرديا بازدياد أبعاد المشكلة؛ وذلك لأنه _وكما ذكر سابقا_ يتم تقييم ال(Mountain Function) عند كل نقطة تقاطع في الشبكة على مستوى البيانات.

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

خوارزمية ال(Subtractive clustering)، هي عمليه تحديد مراكز المجموعات التي تجمعها صفه مشتركه بين كل الأعضاء دون العلم بعدد المجموعات الموجودة لدينا.

وتعتمد هذه الطريقة على حساب كثافه البيانات عند كل نقطة ضمن مستوى معين، فاذا كانت كل نقطة مرشحة لتكون مركز تجمع، فانه يمكن قياس كثافة البيانات عند النقطة xi من المعادلة التالية:

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

تم اختيار المركز الأول xc1 والذي كانت كثافة البيانات عنده أعلى ما يمكن Dc1 . بعد ذلك يتم حساب قيم الكثافات الجديدة عند كل نقطة xi من خلال

حيث أن rb ثابت موجب يمثل قطر دائرة حول كل نقطة، يتم حساب الكثافة داخل هذه الدائرة، وكلما كبر هذا القطر أصبح لدينا عدد اقل من المجموعات، وكلما قل القطر زاد عدد المجموعات. ودائما تكون قيمة rb أكبر من قيمة ra (غالبا يستخدم rb=1.5ra )، وذلك لتقليل قيم الكثافة عند النقاط المجاورة لنقطة المركز الأولى.

وتقوم خوارزمية ال (Subtractive clustering) بالخطوات التالية:

1. إيجاد نقطه معينه موجوده في المجال تكون عندها الكثافة عاليه_ ويتم حساب الكثافة من المعادلة الأولى_ ومن ثم اختيار نقطه معينه كمركز، وذلك عن طريق وجودها بين عدد كبير من النقاط المجاورة.
2. يتم حذف نقاط البيانات.
3. ثم تبحث الخوارزمية عن مركز جديد، وذلك عن طريق حساب قيم الكثافة للنقاط الأخرى_كما في المعادلة الثانية_، وتستمر هذه العملية حتى الانتهاء من كل النقاط، أو إيجاد عدد كاف(مناسب) من المجموعات.

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

ال(Cross Validation) هو عبارة عن عمليات حسابية واحصائية لتقسيم البيانات والعينات (samples) إلى مجموعات فرعية. ويتم اجراء عملية التحليل في البداية على مجموعة فرعية واحدة، في حين نحتفظ بالمجموعات الفرعية الأخرى لاستخدامها لاحقا للتأكد من صحة التحليل الأولي.

المجموعة الفرعية الأولى يطلق عليها مجموعة التدريب(training set)، والمجموعات الفرعية الأخرى يطلق عليها مجموعات الاختبار والتحقق (testing and validation).

المشكلة في استخدام الطرق السابقة انها لاتعطي مؤشرا عن كيفية تصرف المعلم (Learner)، عندما يطلب منه التنبؤ حول البيانات التي لم تكن جاهزة حتى الآن. لاتقوم بعمليه التعميم لجميع البيانات المستقبلية (not generalized).

يمكن التغلب على هذه المشكلة من خلال عدم استخدام مجموعة البيانات بالكامل في عمليه التدريب، بعض البيانات نقوم بحذفها قبل اجراء عملية التدريب، وبعد اجراء عملية التدريب، البيانات التي تم حذفها يتم استخدامها في عملية الاختبار، وذلك لحساب الأداء (performance)، وهذه هي الفكرة الرئيسية لل(Cross validation).

أنواع ال(Regression)

(linear regression)

سمي بالخطي لان العلاقة بين كل من المتغير x والمتغير y هي خطية، في هذه الحالة يتم محاولة إيجاد خط يصنف حميع نقاط البيانات.

(Quadratic regression)

سمي بذلك لانه متعلق بالمعادلات التربيعية من الدرجة الثانية، ويمثل منحنى يصنف نقاط بيانات معينة، ويحقق نتائج أفضل من ال(Linear regression). (Piecewise linear nonparametric regression)

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

الشكل2.1: أنواع ال(Regression)، (أ) (linear regression)، (ب) (Quadratic regression)، (ج)(Piecewise linear nonparametric regression)

طرق ال(Cross Validation)

هي من ابسط الطرق المستخدمة في ال(Cross Validation)، حيث أن البيانات تقسم إلى مجموعتين، المجموعة الأولى تستخدم للتدريب والثانية للاختبار، وبعد ذلك يتم تحديد ال(Regression) وفقا للبيانات المستخدمة في عملية التدريب، بعد ذلك ينكن تخمين أداء هذه الطريقة وتحديد نسبة الخطأ(error) من خلال البيانات المستخدة للاختبار.

ملاحظه: هناك اختلاف وتباين كبير في تقييم طرق ال(Cross Validation)، ويعتمد ذلك على نوع النقاط التي تم اختيارها في عملية التدريب والاختبار والطريقة التي يتم فيها تقسيم البيانات.

ميزاتها:

1. بسيطة التنفيذ.
2. لا تحتاج إلى وقت كبير في عمليه الحساب.

سيئاتها:

تضيع جزء من بيانات التدريب، حيث يتم الزالة 30% من البيانات واستخدامها في عملية الاختبار.

طريقة عمل الخوارزمية

1. اختيار 30% من البيانات بشكل عشوائي لاستخدامها في عملية الاختبار.
2. استخدام كا تبقى من البيانات في عملية التدريب.
3. اجراء عملية ال(regression).
4. تخمين وحساب الأداء المستقبلي للعمليه بناء على البيانات المستخدمة في عمليه الاختبار.

الخطوة الأولى والثانية:

كما يظهر لدينا في الشكل 2.2 أن النقاط باللون الأحمر تستخدم للاختبار. والنقاط باللون الأزرق تستخدم للتدريب.

الخطوة الثالثة:

اجراء عملية (Regression) على مجموعة البيانات المستخدمة للتدريب، لاحظ وجود خط التصنيف الأخضر في الشكل 2.3.

الخطوة الرابعة:

تخمين أداء هذه الطريقة من خلال النقاط المستخدمة في عملية الاختبار. يمكننا بعد ذلك حساب نسبة الخطأ (Mean Square Error) لمعرفه أي من الطرق أفضل في استخدامها.

من خلال تطبيق الخطوات السابقة على أنواع ال(Regression) الأخرى يتبين لدينا ما يلي:

عند مقارنة نتائج الأنواع الثلاثة يتبين ان الخطأ عند ال(Quadratic regression) اقل شيء وهنا نعتبرها الأفضل.

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

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

طريقة عمل الخوارزمية:

•لكل عينة k في المجموعة R.

•نقوم بحذف إحداثيات النقطة (Xk ،Yk) من المجموعة.

•نقوم بعمليه التدريب على باقي النقاط في المجموعة.

•نقوم بحساب الخطأ (MSE) الناتج من هذه النقطة (Xk ،Yk).

•نقوم بتكرار من 1 – 4 لكل النقاط الموجودة في المجموعة R.

الخطوة الأولى:

كما نرى في الشكل 2.5، النقطة باللون الأحمر تمثل نقطة الاختبار.

الخطوة الثانية:

حذف إحداثيات النقطة (Xk ،Yk) من المجموعة R قبل القيام بعملية التدريب، كما في الشكل 2.6.

الخطوة الثالثة:

نقوم بعملية التدريب على النقاط المتبقية في المجموعة R، كما يظهر في الشكل 2.7.

الخطوة الرابعة:

حساب نسبة الخطأ (MSE) الناتج من النقطة (Xk ،Yk)، لاحظ الشكل 2.8.

الخطوة الخامسة:

•تكرار الخطوات الأربعة (1 – 4) لكل النقاط الموجودة في المجموعة R كما هو في الشكل 2.9.

•حساب الخطأ (MSE) الناتج من جميع النقاط.

تكرار الخطوات على الأنواع لأخرى من ال(Regression)

عند المقارنة بين الطرق الثلاثة تبين ان اقل نسبة خطأ هوعند استخدام ال(LinearRegression)، وهي الأفضل في عمليه التدريب.

ميزات استخدام ال(Leave one out):

•لاتضيع أي جزء من البيانات عند اجراء عمليه التدريب لان نقطه واحده تستخدم في عمليه الاحتبار في كل مرة.

سيائتها:

•عمليه تطبيق هذه الطريقة مكلفه مقارنه بالطرق الأخرى، لأنه يتم تكرار العمليات الحسابية عدة مرات بناء على عدد النقاط.

خلال هذه الطريقة يتم تقسيم البيانات بشكل عشوائي إلى k من المجموعات ومن ثم عملية التدريب لعدد k من المرات باستخدام جميع النقاط الموجودة باستثناء المجموعة k.

خطوات عمل الخوارزمية:

•تقسيم البيانات بشكل عشوائي إلى K من المجموعات.

•لكل مجوعه نقوم بالتدريب باستخدام كل النقاط التي لاتنتمي إلى هذه المجموعة.

•حساب مجموع نسبة الخطأ في هذه المجموعة.

•تكرار الخطوات من 2- 3 حتى ننتهي من جميع المجموعات.

•حساب الوسط(الmean) للمجموع الكلي للخطأ من كل المجموعات.

الخطوة الأولى:

تقسيم البيانات بشكل عشوائي إلى Kمن المجموعات.

في هذا المثال يتم تقسيم البيانات إلى ثلاث مجموعات، كما يظهر في الشكل 2.12.

المجموعة الأولى : اللون الأحمر المجموعة الثانية : اللون الأزرق المجموعة الثالثة : اللون الأخضر

الخطوة الثانية والثالثة:

في هذه المرحلة يتم تدريب جميع النقاط التي لا تنتمي إلى اللون الأحمر، كما هو في الشكل 2.13. حساب نسبة الخطأ في هذه المجموعة.

الخطوة الرابعة:

تكرار الخطوة الثانية والثالثة حتى ننتهي من جميع المجموعات، كما هو في الشكل 2.14.

الخطوة الخامسة:

حساب الوسط للمجموع نسب الخطأ لكل المجموعات.

عند تطبيق هذه الخوارزمية على ال((Piecewise linear nonparametric regression وال((quadratic regression فإن نسب الخطأ تكون كما يلي:

بعد المقارنة بين الطرق الثلاثة تبين ان اقل نسبة خطأ هوعند استخدام ال(Quadratic regression)، وهي الأفضل في عمليه التدريب

ميزات استخدام ال(K-fold cross validation)

•إذا تم اختيار القيمة الصحيحه للمتغير k، فانه يقلل استخدام البيانات في عملية الاختبار مقارنه مع ال(test set method)، ويقلل من التكلفة مقارنه مع ال(leave one out method).

ملاحظة:

لايوجد نظرية ثابتة لاختيار قيمه k، لكن الشائع هو اختيار k=10.

مخطط تنيفذ خوارزمية K-fold cross validation