ترجمة: محمد العنزي
تدقيق: فاضل حمود
تعتبر خوارزميات التجميع (Clustering) من أشهر الخوارزميات في مجال تعلم الآلة من النوع الغير موجه (Unsupervised Learning). تتمحور فكرة هذا النوع من الخوارزميات حول تجميع عناصر البيانات في مجموعات متعددة بناء ً على التشابه بين هذه العناصر. تُستخدم هذه الخوارزميات في العديد من المجالات كمشاريع تنقيب البيانات و اكتشاف الأنماط وتحليل الصور والمعلوماتية الطبية وغيرها.
هناك العديد من خوارزميات التجميع تتشابه في أهدافها وتختلف بطرق عملها كخوارزمية الاتصال، والنقطة المركزية، والتوزيع والتجميع المبني على الكثافة وغيرها. في هذا الدرس، سنسلط الضوء على خوارزمية K-means والتي تعتبر من أشهر خوارزميات التجميع القائم على النقطة المركزية ومن ثم سننطلق سويا في تطبيق عملي لهذه الخوارزمية على بيانات شركة أوبر في مدينة نيويورك. تحتوي هذه البيانات على العديد من المعلومات كنقطة انطلاق الركاب والتاريخ والوقت ومدة الرحلة والمعلومات الجغرافية. نهدف في هذا الدرس إلى معرفة الخطوات العملية عند تطبيق هذا النوع من الخوارزميات والتعرف على النتائج المهمة التي من الممكن الحصول عليها.
عند الحديث عن أنواع خوارزميات التجميع فيمكننا تقسيم عمليات التجميع إلى قسمين رئيسيين:
الأول: التجميع الصارم (Hard clustering) والذي يسمح للعنصر بالانتماء إلى مجموعة واحدة على الأكثر. فعلى سبيل المثال في بيانات أوبر التي سنعمل عليها يتم توزيع كل نقطة انطلاق إلى حي واحد فقط من الأحياء الخمسة.
الثاني: التجميع المرن (Soft clustering)، ويعني إمكانية وجود نفس العنصر في أكثر من مجموعة ومثال ذلك في البيانات التي سنعمل عليها أن بعض المواقع قد تقع على الحد بين حيين فتكون منتمية ً إلى آكثر من مجموعة.
خوارزمية ال K-Means:
في هذا الدرس سنطبق خوارزمية K-means على مجموعة ضخمة من بيانات الرحلات من شركة أوبر في مدينة نيويورك والتي تم جمعها خلال ستة أشهر. تحتوي هذه البيانات الخام على معلومات انطلاق الركاب كالتاريخ والوقت ومدة الرحلة ونقطة الانطلاق. تتكون مدينة نيويورك من خمسة أحياء وهي: بروكلين و كوينز و مانهاتن و برونكس و جزيرة ستاتن. خلال هذا الدرس، سنستكشف هذه البيانات بشكل أدق من خلال تطبيق خوارزمية ال K-Means وتجميع نقاط الانطلاق لمعرفة أكثر الأحياء طلبا ً للخدمة. بالإضافة إلى ذلك، يعطينا هذا الدرس تصورا ً حقيقيا ً للخطوات الرئيسية عند العمل على هذا النوع من مشاريع علم البيانات ابتداء ً من تجهيز البيانات ومرورا ً بتنفيذ الخوارزميات وانتهاءً باستعراض النتائج.
فهم المشكلة:
تعتبر البيانات المرورية في المدن من أهم مصادر البيانات التي يفهم من خلالها طبيعة سير الحركة المرورية ومناطق الازدحام في المدينة كالمناطق السكنية والمدارس والطرق السريعة وأماكن العمل. وتكمن أهمية هذا النوع من البيانات في المعلومات التي يمكن الاستناد عليها عند تخطيط المدن وإدارة الحركات المرورية وفرض القواعد واللوائح المناسبة وفقا ً لذلك.
وتتضح أهمية هذا النوع من البيانات من خلال جمعها على فترات زمنية طويلة ومن ثم تحليلها. يساعد هذا النوع من التحليل الجهات المعنية على تحديد أوقات الذروة و الحركة المرورية في مواسم الإجازات وتأثير الطقس على مختلف الأماكن الجغرافية مما يساعد على زيادة كفاءة التخطيط وأخذ التدابير اللازمة لإدارة المرور. إضافة إلى ذلك، يعتبر هذا النوع من البيانات مصدرا ً مهما لتجنب الكوارث المرورية وإعادة توجيه حركة المرور عند وقوع الحوادث. ولكن هدفنا في هذا الدرس هو التعرف على كيفية تطبيق خوارزميةK-Means وتحديد الأحياء الأكثر طلبا ً لخدمة أوبر في مدينة نيويورك.
فهم البيانات:
سنستخدم بيانات الرحلات من شركة أوبر لعام ٢٠١٤ والتي يمكن تحميلها من الرابط المشار إليه في بداية الدرس:
سنستخدم خلال هذا الدرس عدة حزم والتي نستطيع أن نثبتها بسهولة عن طريق استخدام الأمر ( )install.packages
نبدأ الخطوة الأولى من هذا الدرس بتحميل البيانات:
("apr14 <-read.csv("https://raw.githubusercontent.com/fivethirtyeight/uber-tlc-foil-response/master/uber-trip-data/uber-raw-data-apr14.csv
("may14 <- read.csv("https://raw.githubusercontent.com/fivethirtyeight/uber-tlc-foil-response/master/uber-trip-data/uber-raw-data-may14.csv
("jun14 <- read.csv("https://raw.githubusercontent.com/fivethirtyeight/uber-tlc-foil-response/master/uber-trip-data/uber-raw-data-jun14.csv
("jul14 <- read.csv("https://raw.githubusercontent.com/fivethirtyeight/uber-tlc-foil-response/master/uber-trip-data/uber-raw-data-jul14.csv
("aug14 <- read.csv("https://raw.githubusercontent.com/fivethirtyeight/uber-tlc-foil-response/master/uber-trip-data/uber-raw-data-aug14.csv
sep14 <- read.csv("https://raw.githubusercontent.com/fivethirtyeight/uber-tlc-foil-response/master/uber-trip-data/uber-raw-data-sep14.csv")في الخطوة التالية سنقوم بجمع البيانات سويا ً في مكون واحد حتى تسهل معالجتها والتعامل معها عن طريق الدالة ( )bind_rows من مكتبة dplyr.
(library(dplyr
(data14 <- bind_rows(apr14, may14, jun14, jul14, aug14, sep14الآن لنأخذ نظرة على ملخص البيانات عن طريق الأمر التالي:
(summary(data14 Date.Time Lat Lon Base
Length:4534327 Min. :39.66 Min. :-74.93 B02512: 205673
Class :character 1st Qu.:40.72 1st Qu.:-74.00 B02598:1393113
Mode :character Median :40.74 Median :-73.98 B02617:1458853
Mean :40.74 Mean :-73.97 B02682:1212789 ...........
3rd Qu.:40.76 3rd Qu.:-73.97 B02764: 263899 ...................
Max. :42.12 Max. :-72.07... كما نلاحظ من خلال الملخص السابق، تحتوي البيانات على الأعمدة التالية:
Date.Time: ويحتوي على بيانات تاريخ ووقت بداية الرحلة
Lat: ويحتوي على بيانات خطوط العرض لنقطة الانطلاق
Lon: ويحتوي على بيانات خطوط الطول لنقطة الانطلاق
Base: يحتوي على بيانات الرمز الأساسي للشركة TLC
تحضير البيانات
سنعمل في هذه الخطوة على تحضير البيانات وإعادة ترتيبها بحيث يمكننا العمل عليها بسهولة. كما سنتحقق في الخطوة التالية من وجود البيانات المفقودة
(library(VIM # دالة 'aggr' تصور لنا كمية البيانات المفقودة في كل عمود (aggr(data14
كما نلاحظ في الشكل السابق، يظهر لدينا أن البيانات لا تحتوي على أي بيانات مفقودة. ولكن علينا أن نتذكر بأن هذه ليست الحالة الطبيعية في البيانات حيث أن التعامل مع البيانات المفقودة جزء أساسي من عملية تنظيف وتحضير البيانات. هناك العديد من الطرق للتعامل مع البيانات المفقودة من أشهرها حذف الصفوف أو الأعمدة التي تحتوي على بيانات مفقودة أو استبدال البيانات المفقودة بالقيمة المتوسطة (mean). ولكن ينبغي التأكيد على أنه لا توجد طريقة واحدة صحيحة للتعامل مع البيانات المفقودة بما في ذلك الطرق التي تم التطرق لها.
يحتوي العمود الأول Date.Time على بيانات التاريخ والوقت معا ً، ولاستخدام هذه القيم سنحتاج إلى فصل هاتين القيمتين. ولعمل ذلك، سنستخدم مكتبة lubridate . والتي تسهل علينا اختيار الترتيب المرغوب به لعرض التاريخ (سنة، شهر، يوم).
(library(lubridate
(data14$Date.Time <- mdy_hms(data14$Date.Time
(( data14$Year <- factor(year(data14$Date.Time
((data14$Month <- factor(month(data14$Date.Time
((data14$Day <- factor(day(data14$Date.Time
((data14$Weekday <- factor(wday(data14$Date.Time
((data14$Hour <- factor(hour(data14$Date.Time
((data14$Minute <- factor(minute(data14$Date.Time
((data14$Second <- factor(second(data14$Date.Timeالآن دعونا نلقي نظرة على شكل البيانات النهائي من خلال استعراض الصفوف الأولى:
(head(data14, n=10
لقد قمنا بعمل جميع التعديلات اللازمة والتي تساعدنا على فهم البيانات وتجهيزها لتكون مناسبة لتطبيق خوارزمية K-Means
في الخطوة التالية سنقوم بتقسيم البيانات إلى مجموعتين: مجموعة التدريب، ومجموعة الاختبار. وتعتبر هذه الخطوة من الخطوات الأساسية في مشاريع علم البيانات والعمل على خوارزميات تعلم الآلة (تدريب الخوارزمية على مجموعة التدريب ومن ثم اختبارها باستخدام مجموعة الاختبار). ولتتضح الصورة أكثر دعونا نأخذ هذا المثال، عند العمل على خوارزميات التجميع فإن هذا التقسيم مطلوب لتحديد العوامل المهمة مثل K والذي يمثل عدد المجموعات في خوارزمية K-Means. ولكن في هذا الدرس فإننا نعرف مسبقا أن عدد المجموعات يساوي 5، والتي تمثل عدد الأحياء في مدينة نيويورك.
وقبل أن نبدأ بتطبيق خوارزمية ال K-Means دعونا نتعرف على كيفية عمل هذه الخوارزمية. تعتبر خوارزمية K-Means من أشهر خوارزميات التجميع غير الموجه في مجال تعلم الآلة والتي تستخدم لتقسيم البيانات إلى عدد معين من المجموعات يشار له بالحرف K. كما أن K هنا يمثل عدد المجموعات والذي ينبغي تحديدها من قِبل المستخدم قبل تنفيذ الخوارزمية. في هذا الدرس نعرف مسبقا ًعدد المجموعات التي نريدها وعددها 5 والتي تمثل أحياء مدينة نيويورك وهذا يجعل خوارزمية K-Means خيارا ً مناسبا ً لبيانات هذا الدرس.
ملاحظة حول خوارزميات التجميع:
في هذا الدرس نستخدم خوارزمية التجميع لتصنيف نقاط انطلاق رحلات أوبر إلى عدة مجموعات مختلفة (تمثل المجموعات الأحياء الرئيسية في مدينة نيويورك). ولكن ينبغي أن نشير إلى أن خوارزميات التجميع تعتبر أداة من أدوات استكشاف البيانات والتي يمكن من خلالها اختبار هذه البيانات والتعرف عليها وكيفية توزيعها ولكن لا ينصح بالاعتماد الكلي عليها كأداة موثوقة لتصنيف البيانات حيث أنها ليست الطريقة الوحيدة لاستكشاف البيانات.
أما طريقة عمل خوارزمية ال K-Means فتقوم بداية على تحديد عدد المجموعات المرغوب بها ومن ثم يتم توزيع البيانات على هذه المجموعات من خلال تقليل التباين بين عناصر المجموعة الواحدة (ويعرف بالتباين الكلي داخل المجموعة). تُقسَّم البيانات إلى عدد k من المجموعات ويتم تصنيف كل عنصر في البيانات إلى المجموعة ذات النقطة المركزية الأقرب (المتوسط)، حيث تمثل النقطة المركزية الأساس الذي يتم عليه تقسيم البيانات وتصنيفها ولهذا أتت التسمية k-means clustering. وتتم عملية التصنيف باتباع الخطوات التالية:
- بعد اختيار عدد المجموعات المرغوب به يتم تحديد نقطة مركزية K لكل مجموعة (متوسط كل مجموعة).
- إسناد العناصر المراد تصنيفها إلى إحدى هذه المجموعات وذلك بقياس بعد العنصر من وسط كل مجموعة ومن ثم ضمه إلى المجموعة الأقرب.
- بعد إسناد جميع العناصر، يتم إعادة حساب النقطة الوسطى K (متوسط العناصر) لكل مجموعة ومن ثم إعادة الاسناد بناء ً على المتوسط الجديد.
- تكرار الخطوة 2 و 3 حتى تصل الخوارزمية لحالة الثبات وتعني استقرار العناصر في المجموعات من خلال إسنادها إلى المجموعة الأقرب.
والآن بعد أن استعرضنا طريقة عمل خوارزمية ال K-Means نظريا ً، لنبدأ بتطبيقها عمليا ً:
لتنفيذ خوارزمية K-Means في R نستخدم الدالة kmeans() . بداية ً، نقوم بتحديد قيمة k ب 5 (عدد الأحياء). خيار الseeds هنا يسمح بإنشاء نقطة بداية للأرقام التي يتم إنشاؤها عشوائيًا ، بحيث يساعد على الحصول على نفس النتيجة في كل مرة يتم فيها تشغيل الكود.
(set.seed(20
(clusters <- kmeans(data14[,2:3], 5
# في الخطوة التالية نقوم بإضافة عمود Borough لحفظ رقم الجموعة لكل عنصر
(data14$Borough <- as.factor(clusters$cluster# نتعرف على تفاصيل نتائج التجميع من خلال الأمر التالي
(str(clusters
الصور السابقة تمثل نتائج خوارزمية K-Means وأبرز نتائجها ما يلي:
Cluster : متجه من الأعداد الصحيحة (من 1: k) يشير إلى المجموعة التي تم تخصيص كل نقطة لها.
Centers: مصفوفة تحتوي على النقاط المركزية للمجموعات (Cluster centers).
Withinss: متجه يحتوي على sum of squares داخل المجموعة، وهناك مكون واحد لكل مجموعة.
Tot.withniss: مجموع squares sum داخل المجموعة ((sum(withinss).
Size: عدد العناصر في كل مجموعة.
في الخطوة التالية، سنحاول تمثيل هذه النتائج رسوميا ً:
الأحياء (المجموعات) التي تم تشكيلها مطابقة للأحياء الحقيقية. رقم المجموعة يتوافق مع المناطق التالية:
- برونكس
- مانهاتن
- بروكلين
- ستيتن ايلاند
- كوينز
(library(ggmap
(NYCMap <- get_map("New York", zoom = 10
ggmap(NYCMap) + geom_point(aes(x = Lon[], y = Lat[], colour = as.factor(Borough)),data = data14) +
("ggtitle("NYC Boroughs using KMean
كما نرى، فإن النتائج رائعة جدًا. يتضح لدينا هنا نتائج خوارزمية k-mean والتي من خلالها استطعنا تصنيف نقاط انطلاق رحلات أوبر في مدينة نيويورك لمدة ستة أشهر. والآن، مالذي يمكننا معرفته من خلال هذه النتائج؟ على سبيل المثال يمكننا استخدام هذه النتائج لعرض معدل نمو طلبات أوبر داخل الأحياء لكل شهر لمعرفة أكثر الأحياء طلبا ً لخدمة أوبر من خلال الخطوات التالية:
(library(DT
(data14$Month <- as.double(data14$Month
month_borough_14 <- count_(data14, vars = c('Month', 'Borough'), sort = TRUE) %>%
(arrange(Month, Borough
(datatable(month_borough_14
وللاطلاع على نتائج تحليل نمو الطلبات لكل حي بشكل أسهل، دعونا نمثلها على شكل رسم بياني من خلال الأمر التالي:
(library(dplyr
monthly_growth <- month_borough_14 %>%
mutate(Date = paste("04", Month)) %>%
ggplot(aes(Month, n, colour = Borough)) + geom_line() +
(ggtitle("Uber Monthly Growth - 2014"
monthly_growth
من خلال النتائج السابقة، يظهر لدينا بأن حي بروكلين و ستيتن آيلاند هما الأكثر طلبا ً لخدمة أوبر وكذلك الأعلى نموا ً خلال هذه الفترة.
في الختام وكما رأينا في الخطوات السابقة، فإن خوارزمية K-means من الخوارزميات التي تُنَفذ بسهولة وتعطي نتائج رائعة. ولكن، فإن هذه الخوارزمية لا تخلو من بعض السلبيات كما هو الحال في جميع الخوارزميات الأخرى. أول هذه السلبيات هو ضرورة تحديد عدد المجموعات كخطوة أساسية عند تطبيق هذه الخوارزمية. و كما لاحظتم فلم نواجه تحديا ً كبيرا ً عند تحديد عدد المجموعات في هذا الدرس بسبب معرفتنا المسبقة بعدد الأحياء في نيويورك. ولكن هذه ليست الحالية الطبيعية في جميع البيانات لذلك يُشَكل تحديد عدد المجموعات الأمثل تحديا ً إضافيا ً عند العمل على خوارزمية K-means و هناك عدة طرق يمكن من خلالها تحديد العدد الأمثل لعدد المجموعات لعلنا نتطرق لها في الدروس القادمة. من السلبيات أيضا ً أنها تتأثر بالقيم المتطرفة (outliers) مما قد يحدث تغيرا ً بالنتائج عند إعادة ترتيب البيانات.
في نهاية هذه الدرس، ما تم إنجازه يعطينا لمحة سريعة عن عالم التعليم الغير موجه في مجال تعلم الآلة، تعلمنا سويا ً كيفية تطبيق بعض الخوارزميات المستخدمة في مشاريع علم البيانات وأخذنا مثالا ً عمليا ً على تصنيف نقاط انطلاق رحلات أوبر في أحياء نيويورك من خلال استخدام خوارزمية K-means. كما أخدنا مثالا ً على كيفية الاستفادة من مثل هذه النتائج لمعرفة أكثر الأحياء نمواً في طلبات خدمة أوبر. في الدروس القادمة سنتعمق أكثر في هذه المجالات من خلال دروس تطبيقية نستطيع من خلالها اكتساب المهارات اللازمة للعمل على مثل هذه المشاريع.
Reference
Datacamp/tutorials/by: Sejal Jaiswal
