بسم الله الرحمن الرحيم


ملاحظة: استخدم مفتاح المسافة على لوحة المفاتيح للتنقل بين الشرائح
يُفضّل أي متصفح غير فايرفوكس
من متصفح الجوال ترتيب الشرائح من أعلى-اسفل ثم يسار-يمين

مَهَمّة

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

خوارزمية التجميع (أو التصنيف) k-means

تستخدم هذه الخوارزمية كثيراً في مجال تعلم الآلة و علم البيانات لتجميع "تقسيم" نقاط البيانات المتشابهه (المتقاربة) مع بعضها البعض في عدد معين من المجموعات.

كيف تعمل الخوارزمية؟

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

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


بعد تحديد عدد المجموعات المطلوبة $k$ تقوم الخوارزمية بالخطوات التالية:
  • 1) إنشاء مجموعات فارغة بعدد المجموعات المطلوبة
  • 2) إختيار نقاط منتصف أولية (يمكن إختيارها عشوائياً من المدخلات) لكل مجموعة
  • 3) زيارة كل نقطة من نقاط البيانات:
    • 3.1) حساب المسافة بين هذه النقطة و نقاط المنتصف، مع إختيار المسافة الأقرب
    • 3.2) إضافة هذه النقطة إلى المجموعة الأقرب لها
  • 4) بعد إضافة جميع النقاط إلى المجموعات المختلفة، تقوم بحساب نقطة منتصف جديدة لكل مجموعة
  • 5) اذهب للخطوة 3 وكرر نفس العمليات، حتى تصبح نقاط المنتصف الجديدة هي نفسها السابقة. بمعني المجموعات لا تتغير
  • 6) إرجاع المجموعات النهائية

تنويه

في هذا الشرح، ولغرض تبسيط المفهوم:

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

دعنا أولاً نبدأ بفحص البيانات، وهي كما ذكرنا ستكون بيانات الطول و الوزن لعشرة أشخاص، كالتالي:
In [1]:
          #  1    2    3    4    5    6    7    8    9   10     رقم كل شخص 
weights = [ 74,  77,  81,  76,  80,  91,  88,  93,  88,  92] # الوزن بالكيلوغرام
heights = [179, 182, 181, 175, 174, 182, 178, 178, 174, 173] # الطول بالسنتيمتر
لنتصور البيانات بشكل افضل، سنستعرض النقاط العشرة في الرسم البياني الإحداثي التالي:
In [3]:
show_data() # هذه الدالة ليست جزء من الشرح، لاتهتم لها الآن
الآن، المهمة هي معرفة أي هذه النقاط تتشابه من حيث الخصائص. وبالتالي فرزها في مجموعات مستقلة.
فيما يلي سنقوم بكتابة وشرح الخوارزمية لتنفيذ هذه المهمة.
من اجل تسهيل عملية كتابة الكود، سنضع البيانات في متغير واحد. نسميه الأمثلة. بحيث أن كل مثال سيحتوي على بيانات شخص واحد، كما يلي:
In [4]:
samples = [list(point) for point in zip(weights, heights)]
samples
Out[4]:
[[74, 179],
 [77, 182],
 [81, 181],
 [76, 175],
 [80, 174],
 [91, 182],
 [88, 178],
 [93, 178],
 [88, 174],
 [92, 173]]

حساب المسافة بين نقطتين

تحتاج خوارزمية التجميع أن تقوم بحساب المسافات بين نقاط البيانات، (وهي المسافة العادية، أي نفس المسافة الناتجة إذا ماستخدمنا المسطرة لحساب المسافة بين نقطتين). تسمى هذه المسافة بـ "المسافة الإقليدية"، ويتم حسابها بين نقطتين $U=(u_1, u_2, ...,u_n)$ و $V=(v_1, v_2, ..., v_n)$ بحيث ان $n$ هو عدد الأبعاد في كل نقطة كما يلي:
$$ distance(U, V) = \sqrt{\left(u_{1}-v_{1}\right)^{2}+\left(u_{2}-v_{2}\right)^{2}+\cdots+\left(u_{n}-v_{n}\right)^{2}}=\sqrt{\sum_{i=1}^{n}\left(u_{i}-v_{i}\right)^{2}} $$
لذلك سنحتاج إلى كتابة دالة بايثون لحساب هذه المسافة بين نقطتين (مهما كان عدد الأبعاد في النقطتين) كما يلي:
In [5]:
def distance(u, v):
    """
    حساب المسافة الإقليدية بين نقطتين
    المسافة = square_root( (u0 - v0)^2 + (u1 - v1)^2) )
    
    u: [int, int], النقطة الأولى
    v: [int, int], النقطة الثانية
    """
    sum_ = sum( (u[i] - v[i])**2 for i in range(len(u)) ) # ناتج الجمع اللي تحت الجذر
    return sum_**(1/2)                                    # نأخذ الجذر للمجموع

حساب النقطة الأقرب

سنكتب دالة تأخذ نقطة معينة (لنسميها النقطة الهدف) مع مجموعة نقاط أخرى (لنسميهم نقاط المنتصف)، وتُرجِع النقطة (من نقاط المنتصف) الأقرب إلى النقطة الهدف. كما يلي:
In [6]:
def get_closer(target, *args):
    """
    حساب أي النقاط اقرب إلى النقطة الهدف
    
    target:  [float], النقطة الهدف
    *args: [[float]], مجموعة نقاط 
    """
    min_distance = float('inf')      # متغير للمسافة الأقصر، نبدأه بأكبر قيمة  
    for point in args:               # زيارة نقاط المنتصف المدخلة 
        d = distance(point, target)  # حساب المسافة بين الهدف و نقطة المنتصف الحالية
        if d < min_distance:         # إذا كانت المسافة أقصر من المسافة الأقصر السابقة
            min_distance = d         # نحدث متغير المسافة الأقصر للمسافة الحالية
            closer = point           # نحتفط بـ نقطة المنتصف الحالية كالنقطة الأقرب
    return closer                    # بعد مقارنة جميع المسافات، إرجاع النقطة ذات المسافة الأقرب

حساب نقطة المنتصف لمجموعة من النقاط

اخيراً، سنحتاج دالة أخرى لتقوم بحساب النقطة التي تقع في المنتصف بين مجموعة من النقاط. وهي مجموع النقاط مقسوم على عدد النقاط، تتم كتابتها رياضياً كما يلي بحيث $N$ هو عدد النقاط:
$$ center = \frac{\sum_{i=1}^{N}u_{i}}{N} $$
نستطيع كتابتها في بايثون كما يلي:
In [7]:
def get_center(cluster):
    """
    حساب نقطة المنتصف لكل النقاط في المجموعة
    
    cluster: [[float]], قائمة من النقاط
    """
    center = []                             # متغير لتخزين نقطة المنتصف
    n = len(cluster)                        # عدد النقاط في المجموعة
    for i in range(len(cluster[0])):        # عدد الأبعاد في كل نقطة
        c = sum(p[i] for p in cluster) / n  # المجموع لكل بُعد تقسيم عدد النقاط
        center.append(round(c, 1))          # اضف الناتج
    return center                           # إرجاع نقطة المنتصف التي تم حسابها
الآن وبعد أن قمنا بكتابة كل الدوال البرمجية التي تحتاجها خوارزمية التجميع، نقوم بكتابة وتنفيذ الخوارزمية

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

In [8]:
def k_means(data, k=2, *centers, verbose=True):
    """
    خوارزمية التجميع "التصنيف" مع تنفيذ بأسلوب التكرار الذاتي
    
    data: [[float]],    مجموعة النقاط البيانية التي نرغب في تصنيفها في مجموعات
    k: int,             عدد المجموعات التي نرغب بتكوينها
    centers: [[float]], مُدخل إختياري - نقاط المنتصف (المركزية) الإبتدائية لكل مجموعة
    """
    # نحدد نقاط المنتصف المبدئية إذا كانت لم تدخل مع البيانات
    # عشوائياً نختار من النقاط الأولى في البيانات (بعدد المجموعات)  كنقاط منتصف أولية
    centers = list(centers) if centers else [data[i] for i in range(k)]

    clusters = [[] for _ in range(k)] # ننشئ قوائم فارغة لحفظ النقاط التابعة لكل قائمة بها

    # نقوم بزيارة جميع النقاط البيانية 
    # ولكل نقطة، سنحسب المسافة بينها وبين نقاط المنتصف  
    for point in data:
        # حساب أي نقاط المنتصف أقرب إلى النقطة البيانية الحالية
        nearest = get_closer(point, *centers)
        # نسترجع عنوان أو دليل (من بين قائمة نقاط المنتصف) نقطة المنتصف الأقرب للنقطة الحالية
        nearest_cluster_index = centers.index(nearest)
        # نضيف النقطة الحالية إلى قائمة المجموعة التي تتبع لها من بين مجموعة القوائم
        clusters[nearest_cluster_index].append(point)
    # حساب نقاط المنتصف الجديدة
    new_centers = [get_center(cluster) for cluster in clusters]
    # الأمر التالي ليس جزء من الخوارزمية، لمجرد طباعة النتائج المرحلية
    if verbose: print(f"ITER:\tinit cents: {centers}\n\tnew cents: {new_centers}")

    # إذا نقاط المنتصف السابقة هي نفس الجديدة, تتوقف الخوارزمية وترجع الحل
    if centers == new_centers: return clusters, centers

    # وإلا فإنها ستقوم بتكرار العملية مع نقاط المنتصف الجديدة الجديدة
    return k_means(data, k, *new_centers, verbose=verbose)

إنتهينا من إنشاء الخوارزمية، وهي الآن جاهزة للإستخدام

الآن سنقوم باختبار نتيجة الخوارزمية على البيانات السابقة لأمثلة الطول والوزن لعشرة اشخاص:
In [10]:
clusters, centers = k_means(samples, k=2) # نستدعي الخورازمية بإدخال البيانات وعدد المجموعات المطلوب 
report_result(clusters, centers)          # عرض النتيجة
ITER:	init cents: [[74, 179], [77, 182]]
	new cents: [[76.7, 176.0], [87.1, 178.3]]
ITER:	init cents: [[76.7, 176.0], [87.1, 178.3]]
	new cents: [[77.6, 178.2], [90.4, 177.0]]
ITER:	init cents: [[77.6, 178.2], [90.4, 177.0]]
	new cents: [[77.6, 178.2], [90.4, 177.0]]
نلاحظ في الأعلى، أن الخوارزمية قامت بتقسيم البيانات إلى مجموعتين اللون الأخضر على اليمين والأزرق على اليسار. ونلاحظ نقاط المنتصف النهائية تقع في منتصف كل مجموعة.
إختبار آخر، سنختبر الخوارزمية لتصنف البيانات في ثلاث مجموعات بدل المجموعتين:
In [11]:
clusters, centers = k_means(samples, k=3)
report_result(clusters, centers)
ITER:	init cents: [[74, 179], [77, 182], [81, 181]]
	new cents: [[75.0, 177.0], [77.0, 182.0], [87.6, 177.1]]
ITER:	init cents: [[75.0, 177.0], [77.0, 182.0], [87.6, 177.1]]
	new cents: [[76.7, 176.0], [79.0, 181.5], [90.4, 177.0]]
ITER:	init cents: [[76.7, 176.0], [79.0, 181.5], [90.4, 177.0]]
	new cents: [[76.7, 176.0], [79.0, 181.5], [90.4, 177.0]]
بالمثل، نلاحظ في الأعلى ان الخوارزمية قامت بتقسيم البيانات إلى ثلاث مجموعات: اللون الأحمر، الأخضر، والأزرق. وفي المنتصف لكل مجموعة نشاهد نقطة المنتصف التابعة لها.
في المثال السابق أستخدمنا مجموعة بيانات تحتوي على 10 امثلة فقط و كل مثال يحتوي على خاصيتين أو بُعدين.

فيما يلي سنختبر الخوارزمية على مجموعة بيانات أخرى

في هذا المثال سننشأ عينة بيانات تحتوي على 200 مثال وكل مثال ذات بعدين، ونطلب من الخوارزمية تقسيمها في ثلاث مجموعات. كما يلي:
In [13]:
# إنشاء بيانات وهمية أخرى من 200 مثال
samples2 = [random_point(dimension=2) for _ in range(200)]
# نستدعي الخوارزمية مع البيانات الجديدة و نطلب عدد ثلاث مجموعات
clusters, centers = k_means(samples2, k=3, verbose=False)
report_result(clusters, centers)
وأيضاً في حال أردنا تقسيمها إلى 6 مجموعات، كما يلي:
In [14]:
clusters, centers = k_means(samples2, k=6, verbose=False)
report_result(clusters, centers)
أخيراً، سنختبر الخوارزمية مع عينة بيانات تحتوي 700 مثال وكل مثال يحتوي على ثلاثة أبعاد (أي ثلاثية الأبعاد)، ونطلب من الخوارزمية تقسيمها في ثلاث مجموعات. كما يلي:
In [16]:
samples3 = [random_point(dimension=3) for _ in range(700)]
clusters, centers = k_means(samples3, k=3, verbose=False)
report_result_3D(clusters, centers)
أو تقسيمها إلى مجموعتين كما يلي:
In [17]:
clusters, centers = k_means(samples3, k=2, verbose=False)
report_result_3D(clusters, centers)
In [18]:
samples3[:5] # عينة لشكل البيانات الثلاثية الأبعاد المستخدمة في الأعلى
Out[18]:
[[50, 89, 81], [73, 90, 64], [93, 52, 87], [41, 86, 72], [67, 57, 62]]

نهاية الشرح


إعداد وكتابة: عبدالعزيز الطويان
@iamaziz
رابط لـ عرض الشرائح
رابط لـ كامل الكود مع التنفيذ
6/15/2019