מה זה K-Means Clustering?

K- mean clustering הוא an למידה ללא פיקוח אלגוריתם, ומתוך כל אלגוריתמי הלמידה הבלתי מפוקחים, K-means clustering עשוי להיות הנפוץ ביותר, הודות לכוחו ולפשטותו. איך עובד K-means clustering בדיוק?

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

הגדרת אשכולות

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

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

• ודא שכל נקודות הנתונים באשכול דומות זו לזו ככל האפשר.
• ודא שכל נקודות הנתונים באשכולות שונים שונות זו מזו ככל האפשר.

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

אשכולות K-Means

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

באופן כללי, ניתן לחלק את צבירת K-means לחמישה שלבים שונים:

• הצב את כל המופעים בקבוצות משנה, כאשר מספר קבוצות המשנה שווה ל-K.
• מצא את הנקודה/מרכז הממוצע של מחיצות האשכול החדשות שנוצרו.
• בהתבסס על הסנטרואידים הללו, הקצה כל נקודה לאשכול ספציפי.
• חשב את המרחקים מכל נקודה למוקדים, והקצה נקודות לאשכולות שבהם המרחק מהמרכז הוא המינימום.
• לאחר שהנקודות הוקצו לאשכולות, מצא את המרכז החדש של האשכולות.

חוזרים על השלבים לעיל עד לסיום תהליך האימון.

בשלב הראשוני, צנטרואידים ממוקמים איפשהו בין נקודות הנתונים.
צילום: Weston.pace באמצעות wikimedia commons, רישיון תיעוד חינם של GNU (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

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

בשלב השני, נעשה שימוש במדד מרחק כמו מרחק אוקלידי כדי לחשב לאיזה מרכז נקודה נתונה הקרובה ביותר, ואז הנקודות מוקצות למחלקה של אותו מרכז. צילום: Weston.pace באמצעות Wikimedia Commons, רישיון מסמך חופשי של GNU (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

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

בשלב השלישי, המרכז מועבר לממוצע של כל נקודות הנתונים. לאחר מכן השיעורים מחולקים מחדש. תמונה: Weston.pace באמצעות Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

בשלב עדכון המרכז, המרכז מחושבים על ידי מציאת המרחק הממוצע בין כל נקודות הנתונים הכלולות כעת בתוך אשכול.

כיצד לבחור את הערך הנכון עבור "K"

בהתחשב בכך ש-K-means clustering הוא אלגוריתם לא מפוקח ומספר המחלקות אינו ידוע מראש, איך מחליטים על מספר המחלקות המתאים/הערך הנכון עבור K?

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

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

מיני-אצווה K-Means Clustering

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

Mini-Batch K-פירושו התקבצות הוא וריאנט על צבירת K-means כאשר גודל מערך הנתונים הנחשב מוגבל. צבירת K-means רגילה פועלת על כל מערך הנתונים/אצווה בבת אחת, בעוד ש-Min-batch K-means clustering מפרק את מערך הנתונים לקבוצות משנה. מיני-אצטות נדגמות באופן אקראי מכל מערך הנתונים ולכל איטרציה חדשה נבחרה מדגם אקראי חדש ומשמשת לעדכון המיקום של המרכזים.

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

תוצאות מחקרים על האפקטיביות של מיני-אצווה K-means clustering מצביעות על כך שהוא יכול להפחית בהצלחה את זמן החישוב עם פשרה קלה באיכות האשכולות.

יישומים של K-Means Clustering

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

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

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