הבלוג של ניב

כל מה שאתם צריכים לדעת על clustering

פוסט מקיף על נושא clustering ולמידה לא מפוקחת.

Niv Alex
8–12 minutes
, , ,
תמונת פרופיל של Niv Alex

במסגרת קורס "מבוא למדעי נתוני עתק" שלקחתי בשנה ב' של התואר הראשון, התבקשנו להגיש מיני פרויקט קטן שעוסק בנושא של clustering. למי שלא מכיר, קלאסטרינג (clustering) היא טכניקה של למידה לא מפוקחת (unsupervised learning) שבה המטרה העיקרית שלנו היא לחלק נתונים לקבוצות (קלאסטרים) כך שהנתונים בתוך כל קבוצה יהיו דומים זה לזה, אבל שונים מהנתונים שנמצאים בקבוצות אחרות. בפוסט זה אציג לעומק את את נושא הלמידה הלא מפוקחת וה-clustering, אציג את האלגוריתמים הנפוצים הקיימים בתחום ואדגים שימוש בהם תוך כדי ביצוע הפרויקט.

תוכן עיניינים של פוסט זה:

  1. ההבדל בין למידה מפוקחת (supervised) ללמידה לא מפוקחת (unsupervised)
  2. מטריקות מרחק ודמיון

ההבדל בין למידה מפוקחת (supervised) ללמידה לא מפוקחת (unsupervised)

בלמידת מכונה, כאשר אנחנו מדברים על אלגוריתמים מפוקחים, יש לנו בעצם סט אימון של מספר דוגמאות כאשר כל דוגמה בסט שלנו היא מתוייגת (כלומר לכל דוגמה אנחנו יודעים האם היא איקס או עיגול בתמונה שמצורפת למטה). הרעיון המרכזי באלגוריתמים מפוקחים הוא בעצם למצוא איזשהו קלאספייר (classifier) שיפריד לנו בין שתי הקבוצות (במקרה זה עיגולים/איקסים). כפי שניתן לראות, במקרה שלנו הקלאספייר הוא הקו הסגול שמבצע הפרדה די טובה בין האיקסים והעיגולים.

תמונה מספר 1: ההבדל בין ביצוע קלסיפקציה לבין ביצוע קלאסטרינג

אז מה קורה באלגוריתמים לא מפוקחים? באלגוריתמים לא מפוקחים (unsupervised), כל הדוגמאות בסט האימון שלנו הן אותו הדבר (כלומר, הן כולן לא מתוייגות). השאיפה שלנו באלגוריתמים לא מפוקחים היא לחלק את הדוגמאות שלנו לקבוצות על פי המיקומים היחסיים שלהם או לפי הדמיון בין דוגמה לדוגמה, כאשר בסופו של דבר נרצה להגיע למצב שבו דוגמאות דומות יהיו תחת אותה קבוצה.

אז איך בעצם נדע שביצענו קליסטור טוב על סט הדוגמאות שלנו? קליסטור טוב אומר שיש דמיון מאוד גבוה בין פריטים שנמצאים בתוך אותו קלאסטר (קבוצה). מושג זה נקרא בז'רגון המקצועי high intraclass similarity והוא אומר את הדבר הפשוט הבא: ככל שיש דמיון פנימי יותר גבוהה בין פריטים שנמצאים תחת אותו הקלאסטר, כך נוכל להגיד שהקליסטור שביצענו היה טוב יותר.

מטריקות מרחק ודמיון

פעולת הקלאסטרינג שאותה אנחנו נבצע מסתמכת על מטריקות של דמיון/מרחק בין דוגמאות שונות בסט הדוגמאות שלנו. אחת המטריקות הכי שימושיות למדידת מרחק/דמיון היא המרחק האוקלידי שכולנו מכירים מהתיכון. המרחק האוקלידי כאמור הוא המרחק הישר והקצר ביותר בין שתי נקודות במרחב (יש כאלה שקוראים לו גם מרחב גיאומטרי)

$$ d=\sqrt{\sum(x_{i}-y_{i})^{2}} $$

שיטה נפוצה נוספת לחישוב מרחק/דמיון היא המרחק של מנהטן – בשיטה זו אנחנו לא מסתכלים על מרחק אווירי אלא על איך מגיעים מנקודה A לנקודה B בעזרת פניות בזוויות של 90 מעלות בלבד. כלומר התנועה שלנו תעשה רק במקביל לאחד משני הצירים ומעל מנת להגיע מנקודה אחת לאחרת עלינו יהיו לנוע מרחק מסוים ימינה/שמאלה ומרחק מסוים מעלה/מטה. לכן באופן מתמטי ניתן להגיד שמרחק מנהטן בין שתי נקודות (x1,x2) ו-(y1,y2) יהיה: $$|x1−x2|+|y1−y2|$$

ישנן מטריקות נוספות לחישוב מרחק כמו Cosine distance או מרחק המינג, אך לא אכנס אליהן בפוסט זה מאחר והן פחות נפוצות.

אלגוריתם K-Means

אלגוריתם K-Means הוא אולי האלגוריתם הנפוץ והפופולרי ביותר לביצוע קלאסטרינג. מטרתו של האלגוריתם היא לחלק את סט הדוגמאות שלנו ל-K אשכולות (קלאסטרים) לפי מרכזי כובד שנקראים צנטרואידים (centroids). השאיפה היא שבסופו של דבר כל אחת מהדוגמאות שלנו תהיה משויכת לאחד מ"מרכזי הכובד" הללו. על ידי בחירה נכונה של מרכזי הכובד נוכל לבצע קליסטור מיטבי של הקבוצות שלנו.

קלט האלגוריתם: סט דוגמאות

פלט האלגוריתם: חלוקה של אותו סט דוגמאות לקבוצות בעלות משמעות (כאשר אני אומר משמעות, אני מתכוון לכך שבכל קלאסטר יהיה לנו intraclass similarity גבוה ככל הניתן). בשלב זה אציין גם שהאלגוריתם הוא איטריבי מטבעו, כלומר הוא קורה בשלבים (איטרציות) בדומה לעוד כמה אלגוריתמי למידת מכונה כמו Gradient descent.

איך האלגוריתם עובד?

נגיד וקיבלנו את סט הדוגמאות הבא ואנחנו שואפים לחלק אותו ל-K=2 קבוצות.

  • בשלב הראשון: נבחר באופן רנדומלי לחלוטין K צנטרואידים במרחב (צנטרואידים במרחב הם בעצם מיקומים במרחב ובמקרה שלנו מדובר על שתי נקודות במישור האוקלידי). בדוגמה שלנו K=2 לכן נבחר 2 צנטרואידים (הם מסומנים באיקס אפור ואיקס אדום באיור).
  • בשלב השני: נבצע "צביעה" של כל הנקודות (הדוגמאות) במרחב שלנו. כל נקודה בסט הדוגמאות שלנו נצבעת לפי הצנטרואיד שהכי קרוב אליה. בעצם אפשר לחשוב על זה כך, כל נקודה כחולה תשאל את עצמה "האם אני קרובה יותר לצנטרואיד האפור או לצנטרואיד האדום" ואז היא תיצבע בהתאם.
  • בשלב השלישי: נבצע הזזה של כל צנטרואיד (כל איקס באיור) לממוצע של הנקודות שנצבעו בצבע שלו, כפי שניתן לראות באיור למטה, האיקס האדום זז לכיוון מרכז הקבוצה האדומה וגם האיקס האפור מתחיל להתקרב לכיוון מרכז הקבוצה השחורה.
  • בשלב הרביעי: נחזור שוב ושוב על שלבים 2-3 של צביעה והזזה עד שהדוגמאות שלנו (הנקודות באיור) מפסיקות לשנות צבע וכשזה יקרה יהיה ניתן להגיד שהגענו לקליסטור טוב.

ניתן בעצם להגיד שכלל העצירה שלנו באלגוריתם K-means הוא מצב בו הנקודות (הדוגמאות) לא משנות את הצבע שלהן או מצב בו הצנטרואידים עצמם לא משנים את המיקום שלהם יותר (מצב בו הם כבר האופטימלי שלהם).

בתמונה למטה ניתן לראות איטרציות של אלגוריתם ה-K-Means והתכנסות שלו לאחר 14 איטרציות.

פסאדו קוד של אלגוריתם K-Means:

Python
function kmeans(k, points) is
    // Initialize centroids
    centroids ← list of k starting centroids
    converged ← false

    while converged == false do
        // Create empty clusters
        clusters ← list of k empty lists

        // Assign each point to the nearest centroid
        for i ← 0 to length(points) - 1 do
            point ← points[i]
            closestIndex ← 0
            minDistance ← distance(point, centroids[0])
            for j ← 1 to k - 1 do
                d ← distance(point, centroids[j])
                if d < minDistance THEN
                    minDistance ← d
                    closestIndex ← j
            clusters[closestIndex].append(point)

        // Recalculate centroids as the mean of each cluster
        newCentroids ← empty list
        for i ← 0 to k - 1 do
            newCentroid ← calculateCentroid(clusters[i])
            newCentroids.append(newCentroid)

        // Check for convergence
        if newCentroids == centroids THEN
            converged ← true
        else
            centroids ← newCentroids

    return clusters

אתגרים עיקריים באלגוריתם ה-K-Means

  1. צנטרואידים שלא שובצה להם אף דוגמה (נקרא לעיתים צנטרואידים יתומים)
  2. קלאסטרים שלא ניתנים להפרדה
  3. בעיית ה-Local optima
  4. אתגר בחירת ה-K

צנטרואידים שלא שובצה להם אף דוגמה

צנטרואידים יתומים הם צנטרואידים שלא שובצה להם אף דוגמה מסט הדוגמאות שלנו. מקרה כזה יכול להתרחש כאשר אחד הצנטרואידים שנבחר באופן אקראי רחוק באופן משמעותי מכל הדוגמאות שנמצאות בסט שלנו, במקרה כזה הצנטרואיד עלול להישאר יתום (ללא אף דוגמה שמשויכת אליו) לאורך כל התהליך. למשל בדוגמה שלמטה, ניתן לראות כי האיקס האדום קרוב באופן משמעותי לשאר הדוגמאות ואילו האיקס השחור נמצא רחוק מכולן.

מה אפשר לעשות במצב כזה:

  • לאתחל את האלגוריתם: בגלל שהאלגוריתם שלנו הוא רנדומי ויוביל בכל הרצה לתוצאות שונות, ניתן פשוט להריץ אותו מחדש ולקוות שהפעם הוא יגריל צנטרואידים שאינם יתומים.
  • פתרון אפשרי נוסף הוא למחוק את הצנטרואיד היתום ולהשתמש ב-K-1 קלאסטרים במקום ב-K קלאסטרים, אך פתרון זה עלול להיות טיפה בעייתי כאשר יש לנו רק K=2 קבוצות.

אבל נשים לב כי אפשר להימנע בכלל מכל העניין והבעיה של הצנטרואידים היתומים בעזרת אתחול נכון ונבון של אלגוריתם ה-K-Means. במקום לבצע אתחול רנדומי לחלוטין של הצנטרואידים כפי שבציענו עד כה, נבצע אתחול של הצנטרואידים ע"י נקודות רנדומיות מתוך סט האימון. נגריל K דוגמאות מתוך סט האימון והן ישמשו אותו כצנטרואידים, ובכך נימנע לחלוטין ממצב של צנטרואיד יתום.

ועכשיו לחלק הפרקטי

כדי להמחיש את התיאוריה שהסברתי בפירוט רב בפוסט, אציג כעת את הפתרון שלי למיני פרויקט שניתן לנו במסגרת הקורס. במסגרת ההנחיות אנחנו נתפקד כעובדי מחלקת הדאטה בחברת e-commerce מובילה בתחום הפרסומות. כחלק ממטלה שקיבלנו מסמנכ"לית השיווק והמכירות של החברה עלינו לבצע סגמנטציה של לקוחות החברה כדי לטרגט להם פרסומות מותאמות באופן אישי.

הפרויקט נתן יד חופשית לביצוע והוא הגדיר רק קווים ושלבים כלליים כפי שקיימים בכל פרויקט דאטה טוב: שלב ניתוח הנתונים, שלב הנדסת הנתונים, שלב הסגמנטציה של הלקוחות, שלב הפעלת האלגוריתם וניתוח המדדים, ושלב הויזואליזציה.

ניתוח הנתונים

ראשית, נייבא את כל הספריות איתן נעבוד לאורך כל התרגיל

Python
import pandas as pd
import numpy as np

import matplotlib.pyplot as plt
import seaborn as sns

import warnings
warnings.filterwarnings('ignore')

from sklearn.model_selection import GridSearchCV

import datetime as dt

בשלב הבא נייבא את הדאטה שאיתו נעבוד במהלך התרגיל ונתחיל לחקור אותו:

Python

online = pd.read_csv('OnlineRetail.csv', encoding='unicode_escape')
online.head()

כפי שניתן לראות הדאטה סט של OnlineRetail מכיל נתוני עסקאות מחנות מקוונת (ככל הנראה חנות בבריטניה). זה נראה שכל שורה בדאטה סט מייצגת מוצר שנרכש כחלק מהזמנה של לקוח. כשמנתחים את הדאטה סט אפשר להבחין שיש לנו 8 עמודות:

  • InvoiceNo – מזהה ייחודי לכל עסקה
  • StockCode – כנראה קוד של מוצר (גם נראה קוד ייחודי)
  • Description – תיאור מילולי של המוצר
  • Quantity – מספר הפריטים שנרכשו מאותו סוג של מוצר
  • InvoiceDate – תאריך ושעת ביצוע העסקה
  • UnitPrice – מחיר יחידה מאותו מוצר
  • CustomerID – מזהה לקוח (גם נראה שמדובר בקוד ייחודי)
  • Country – ככל הנראה מדינת הלקוח או המדינה שממנה בוצעה העסקה

נבדוק כעת כמה רשומות הדאטה סט שלנו מכיל:

Python
print(online.shape)

(541909, 8)

כפלט קיבלתי (541909,8), כלומר הדאטה סט בנוי מ-8 עמודות וכמעט 542 אלף שורות. בשלב הבא בואו נקבל קצת אינפורמציה על טיפוסי הנתונים בדאטה שלנו:

Python
online.info()


output:
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 541909 entries, 0 to 541908
Data columns (total 8 columns):
 #   Column       Non-Null Count   Dtype  
---  ------       --------------   -----  
 0   InvoiceNo    541909 non-null  object 
 1   StockCode    541909 non-null  object 
 2   Description  540455 non-null  object 
 3   Quantity     541909 non-null  int64  
 4   InvoiceDate  541909 non-null  object 
 5   UnitPrice    541909 non-null  float64
 6   CustomerID   406829 non-null  float64
 7   Country      541909 non-null  object 
dtypes: float64(2), int64(1), object(5)
memory usage: 33.1+ MB

כפי שניתן לראות יש לנו יחסית הרבה עמודות מסוג object, עוד 2 עמודות מסוג float ועוד עמודה אחת מסוג int.

בשלב הבא, נרצה לוודא שהדאטה סט שלנו לא מכיל ערכי null, נבדוק כמה אחוזים מכל עמודה הם ערכי null:

Python
online.isnull().sum()/(len(online))*100

output:
InvoiceNo       0.000000
StockCode       0.000000
Description     0.268311
Quantity        0.000000
InvoiceDate     0.000000
UnitPrice       0.000000
CustomerID     24.926694
Country         0.000000
dtype: float64

Feature Engineering

נעיף מהדאטה סט שלנו את כל ערכי ה-null בעזרת פקודת dropna:

Python
online = online.dropna()

כעת נבדוק שוב עם כמה רשומות נשארנו בדאטה סט שלנו:

Python
online.shape

output:
(406829, 8)

יפה, הצלחנו להעיף כמעט מאה אלף שורות שהיו שם סתם. עכשיו נחזור להסתכל על הפיצ'רים שלנו. כפי שראינו למעלה יש לנו 5 פיצ'רים מסוג object, עוד 2 פיצ'רים מסוג float ועוד פיצ'ר אחד מסוג int. נשים לב שהפיצ'ר customer id היה משום מה מסוג float64, נהפוך אותו ל-string type למען הנוחות:

Python
online['CustomerID'] = online['CustomerID'].astype(str)

גם הפורמט של InvoiceDate היה טיפה מוזר (פורמט של object), נעדיף לעבוד עם פורמט של datetime type ולכן נהפוך גם את ה-type של הפיצ'ר הזה:

Python
online['InvoiceDate'] = pd.to_datetime(online['InvoiceDate'], 
format='%d-%m-%Y %H:%M')

כעת נסתכל על הפיצ'רים: quantity ו-unit price. מאחר ואנחנו נבצע סגמנטציה של לקוחות, בסופו של דבר נהיה מעוניינים לדעת מה היה המחיר הכולל של כל עסקה עבור כל לקוח. לא באמת מעניין אותנו מה היה ה-quantity מכל פריט ומה היה ה-unit price. לכן, נוכל לבצע Feature Engineering וליצור פיצ'ר חדש שנקרא Total_Amount_Spent שייצג את המחיר הכולל ששילם הלקוח עבור אותה עסקה. Total_Amount_Spent יחושב כמכפלה בין הכמות (quantity) שאותה רכש הלקוח והמחיר (unit price) של כל יחידה מהמוצר.

Python
online['Total_Amount_Spent']= online['Quantity'] * online['UnitPrice']

כעת הדאטה שלנו ייראה כך:

כעת נרצה לייצר data frame חדש שיכיל שתי עמודות בלבד: עמודה ראשונה של CustomerID (מזהה לקוח) ועמודה שנייה של Total_Amount_Spent (כמות ההוצאות של אותו לקוח)

Python

# total amount
total_amount = online['Total_Amount_Spent'].groupby(online['CustomerID']).sum()
total_amount = pd.DataFrame(total_amount).reset_index()
total_amount.head()

ניצור עוד data frame יחסית פשוט בשם transactions שיכיל את מספר ההזמנות שביצע כל לקוח:

Python
# total transactions
transactions = online['InvoiceNo'].groupby(online['CustomerID']).count()
transaction = pd.DataFrame(transactions).reset_index()
transaction.head()

המשך יבוא…

השאירו תגובה

קריאה נוספת

לגלות עוד מהאתר הבלוג של ניב

כדי להמשיך לקרוא ולקבל גישה לארכיון המלא יש להירשם עכשיו.

להמשיך לקרוא