אלגוריתם האשכולות K-Means ב- Java

1. סקירה כללית

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

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

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

2. אלגוריתמים ללא פיקוח

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

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

  • למידה מפוקחת: באלגוריתמים בפיקוח, נתוני האימון צריכים לכלול את הפיתרון בפועל לכל נקודה. לדוגמא, אם אנו עומדים להכשיר את האלגוריתם שלנו לסינון דואר זבל, אנו מזינים את הדוא"ל לדוגמה וגם את התווית שלהם, כלומר ספאם או לא ספאם, לאלגוריתם. מבחינה מתמטית, אנו הולכים להסיק את f (x) ממערכת אימונים הכוללת את שניהם xs ו כ ן.
  • למידה ללא פיקוח: כשאין תוויות בנתוני האימון, האלגוריתם הוא ללא פיקוח. לדוגמא, יש לנו הרבה נתונים על מוזיקאים ואנחנו נגלה קבוצות של מוזיקאים דומים בנתונים.

3. אשכולות

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

3.1. אשכולות K-Means

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

3.2. איך K-Means עובד

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

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

לאחר מכן אנו מקצים כל נקודת נתונים קיימת למרכז התאים הקרוב ביותר שלה:

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

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

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

3.3. ייצוג תכונות

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

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

וקטור התכונות של אמן כמו לינקין פארק הוא [רוק -> 7890, נו-מטאל -> 700, אלטרנטיבי -> 520, פופ -> 3]. אז אם היינו יכולים למצוא דרך לייצג תכונות כערכים מספריים, אז אנחנו יכולים פשוט להשוות בין שני פריטים שונים, למשל. אמנים, על ידי השוואת הערכים הווקטוריים המתאימים שלהם.

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

כיתה ציבורית שיא {פרטי סופית מחרוזת תיאור; תכונות מפת גמר פרטיות; // בונה, גטר, toString, שווה ו- hashcode}

3.4. מציאת פריטים דומים

בכל איטרציה של K-Means, אנו זקוקים לדרך למצוא את ה- centroid הקרוב ביותר לכל פריט במערך הנתונים. אחת הדרכים הפשוטות ביותר לחישוב המרחק בין שני וקטורי תכונות היא שימוש מרחק אוקלידי. המרחק האוקלידי בין שני וקטורים כמו [p1, q1] ו [p2, q2] שווה ל:

בואו נשתמש בפונקציה זו ב- Java. ראשית, ההפשטה:

ממשק ציבורי מרחק {חישוב כפול (מפה f1, מפה f2); }

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

בואו נראה את היישום למרחק אוקלידי:

מחלקה ציבורית מיישמת EuclideanDistance מרחק {@Override פעמיים חישוב ציבורי (מפה f1, מפה f2) {סכום כפול = 0; עבור (מפתח מחרוזת: f1.keySet ()) {v1 כפול = f1.get (מפתח); כפול v2 = f2.get (מפתח); אם (v1! = null && v2! = null) {sum + = Math.pow (v1 - v2, 2); }} להחזיר את Math.sqrt (סכום); }}

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

3.5. ייצוג Centroid

Centroids נמצאים באותו שטח כמו תכונות רגילות, כך שנוכל לייצג אותם בדומה לתכונות:

מחלקה ציבורית Centroid {גמר פרטי קואורדינטות מפה; // בונים, גטר, toString, שווה ו- hashcode}

עכשיו שיש לנו כמה מופשטים הכרחיים, הגיע הזמן לכתוב את היישום K-Means שלנו. הנה מבט מהיר על חתימת השיטה שלנו:

KM ציבורי בכיתה ציבורית {גמר סטטי פרטי פרטי אקראי = אקראי חדש (); מפה סטטית ציבורית התאמה (רשומות רשימה, int k, מרחק מרחק, int maxIterations) {// הושמט}}

בואו נפרק את חתימת השיטה הזו:

  • ה מערך נתונים הוא קבוצה של וקטורי תכונות. מכיוון שכל וקטור תכונות הוא א תקליט, ואז סוג הנתונים הוא רשימה
  • ה k הפרמטר קובע את מספר האשכולות, שעלינו לספק מראש
  • מֶרְחָק מקפל את הדרך בה אנו הולכים לחשב את ההבדל בין שתי תכונות
  • K-Means מסתיים כאשר המטלה מפסיקה להשתנות במשך כמה חזרות רצופות. בנוסף לתנאי סיום זה, אנו יכולים להציב גבול עליון גם למספר האיטרציות. ה maxIterations טיעון קובע את הגבול העליון
  • כאשר K-Means מסתיים, לכל centroid יש כמה תכונות שהוקצו, ולכן אנו משתמשים ב- מַפָּהכסוג ההחזרה. בעיקרון, כל ערך מפה תואם לאשכול

3.6. דור ה- Centroid

הצעד הראשון הוא ליצור k ממוקמים באופן אקראי מרכזים.

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

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

רשימת סטטי פרטית randomCentroids (רשימת רשומות, int k) {רשימת centroids = ArrayList חדש (); מקסימום מפה = HashMap חדש (); דקות מפה = HashMap חדש (); עבור (רשומת רשומה: רשומות) {record.getFeatures (). forEach ((מפתח, ערך) ->); } הגדר תכונות = records.stream () .flatMap (e -> e.getFeatures (). KeySet (). Stream ()) .collect (toSet ()); עבור (int i = 0; i <k; i ++) {קואורדינטות מפה = HashMap חדש (); עבור (תכונה מחרוזת: תכונות) {max max = maxs.get (attribute); כפול דקות = mins.get (תכונה); coordinates.put (attribute, random.nextDouble () * (max - min) + min); } centroids.add (Centroid חדש (קואורדינטות)); } להחזיר מרכזים; }

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

3.7. מְשִׁימָה

ראשית, נתון תקליט, עלינו למצוא את ה- centroid הקרוב אליו:

סטטי פרטי Centroid הקרוב ביותרCentroid (רשומת שיא, רשימת מרכזים, מרחק מרחק) {מינימום כפול מרחק = כפול.MAX_VALUE; Centroid הקרוב ביותר = null; עבור (Centroid centroid: centroids) {Current CurrentDistance = distance.calculate (record.getFeatures (), centroid.getCoordinates ()); אם (currentDistance <minimumDistance) {minimumDistance = currentDistance; הקרוב ביותר = centroid; }} חזור הכי קרוב; }

כל רשומה שייכת לאשכול המרכזי הקרוב ביותר שלה:

פרטי ריק ריק סטטי allocToCluster (מפה אשכולות, רשומת שיא, Centroid centroid) {clusters.compute (centroid, (key, list) -> {if (list == null) {list = ArrayList new ();} list.add (record); list return;} ); }

3.8. רילוקיישן Centroid

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

ממוצע Centroid סטטי פרטי (Centroid centroid, רשומות רשימה) {if (records == null || recordss.isEmpty ()) {return centroid; } ממוצע מפה = centroid.getCoordinates (); records.stream (). flatMap (e -> e.getFeatures (). keySet (). stream ()) .forEach (k -> average.put (k, 0.0)); עבור (רשומת שיא: רשומות) {record.getFeatures (). forEach ((k, v) -> ממוצע.מחשב (k, (k1, currentValue) -> v + currentValue)); } average.forEach ((k, v) -> average.put (k, v / records.size ())); להחזיר Centroid חדש (ממוצע); }

מכיוון שנוכל להעביר מרכזית יחיד, כעת ניתן ליישם את ה- relocateCentroids שיטה:

רשימת סטטי פרטית relocateCentroids (מפה אשכולות) {return clusters.entrySet (). stream (). map (e -> average (e.getKey (), e.getValue ())). collect (toList ()); }

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

3.9. לשים את הכל ביחד

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

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

מפה סטטית ציבורית fit (List records, int k, מרחק המרחק, int maxIterations) {List centroids = randomCentroids (records, k); מַפָּה אשכולות = HashMap חדש (); מַפָּה lastState = HashMap חדש (); // חזור למספר פעמים שהוגדר מראש עבור (int i = 0; i <maxIterations; i ++) {בוליאני isLastIteration = i == maxIterations - 1; // בכל איטרציה עלינו למצוא את המרכזי הקרוב ביותר עבור כל רשומה עבור (רשומת רשומה: רשומות) {Centroid centroid = הקרוב ביותר לסנטרואיד (רשומה, צנטרואידים, מרחק); assignToCluster (אשכולות, שיא, centroid); } // אם המטלות לא משתנות, אז האלגוריתם מסתיים בוליאני צריךTerminate = isLastIteration || clusters.equals (lastState); lastState = אשכולות; if (shouldTerminate) {break; } // בסוף כל איטרציה עלינו להעביר את המרכזים המרכזיים = relocateCentroids (אשכולות); אשכולות = HashMap חדש (); } להחזיר lastState; }

4. דוגמה: גילוי אמנים דומים ב- Last.fm

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

  1. API להשיג אוסף של אמנים מובילים ב- Last.fm.
  2. ממשק API נוסף לאיתור תגים פופולריים. כל משתמש יכול לתייג אמן במשהו, למשל. סלע. אז, Last.fm מתחזק מסד נתונים של התגים הללו והתדרים שלהם.
  3. ו- API לקבלת התגים המובילים עבור אמן, לפי סדר הפופולריות. מכיוון שיש הרבה תגים כאלה, נשמור רק את התגים שנמנים עם התגים הגלובליים המובילים.

4.1. ה- API של Last.fm

כדי להשתמש בממשקי API אלה, עלינו לקבל מפתח API מ- Last.fm ולשלוח אותו בכל בקשת HTTP. אנו נשתמש בשירות החידוש הבא כדי להתקשר לממשקי ה- API האלה:

ממשק ציבורי LastFmService {@GET ("/ 2.0 /? method = chart.gettopartists & format = json & limit = 50") התקשר לדף int topArtists (@Query ("עמוד")); @GET ("/ 2.0 /? Method = artist.gettoptags & format = json & limit = 20 & autocorrect = 1") התקשר topTagsFor (@Query ("אמן") אמן מחרוזות); @GET ("/ 2.0 /? Method = chart.gettoptags & format = json & limit = 100") שיחת topTags (); // כמה DTO ומיירט אחד}

אז בואו למצוא את האמנים הפופולריים ביותר ב- Last.fm:

// הגדרת שירות Retrofit רשימה סטטית פרטית getTop100Artists () זורק IOException {רשימת אמנים = ArrayList חדש (); // אחזור שני העמודים הראשונים, שכל אחד מהם מכיל 50 רשומות. עבור (int i = 1; i <= 2; i ++) {artists.addAll (lastFm.topArtists (i). execute (). body (). all ()); } להחזיר אמנים; }

באופן דומה, אנו יכולים להביא את התגים המובילים:

סט סטטי פרטי getTop100Tags () זורק IOException {להחזיר lastFm.topTags (). execute (). body (). all (); }

לבסוף, אנו יכולים לבנות מערך נתונים של אמנים יחד עם תדרי התג שלהם:

מערך רשימות סטטי פרטיWithTaggedArtists (רשימת אמנים, Set topTags) זורק IOException {List records = new ArrayList (); עבור (אמן מחרוזת: אמנים) {Map tags = lastFm.topTagsFor (artist) .execute (). body (). all (); // שמור רק תגים פופולריים. tags.entrySet (). removeIf (e ->! topTags.contains (e.getKey ())); records.add (רשומה חדשה (אמן, תגים)); } להחזיר רשומות; }

4.2. אשכולות יוצרים יוצרים

כעת אנו יכולים להזין את מערך הנתונים המוכן ליישום K-Means שלנו:

אמני רשימה = getTop100Artists (); הגדר topTags = getTop100Tags (); רישום רשומות = datasetWithTaggedArtists (אמנים, topTags); מַפָּה אשכולות = KMeans.fit (רשומות, 7, EuclideanDistance חדש (), 1000); // הדפסת אשכולות תצורת האשכול. ForEach ((מפתח, ערך) -> {System.out.println ("------------------------- - CLUSTER ---------------------------- "); // מיון הקואורדינטות כדי לראות תחילה את התגים המשמעותיים ביותר. System.out. println (sortedCentroid (key)); Members String = String.join (",", value.stream (). map (Record :: getDescription) .collect (toSet ())); System.out.print (members); System.out.println (); System.out.println ();});

אם נפעיל את הקוד הזה, הוא היה מדמיין את האשכולות כפלט טקסט:

------------------------------ CLUSTER ------------------- ---------------- Centroid {קלאסי רוק = 65.58333333333333, רוק = 64.41666666666667, בריטי = 20.333333333333332, ...} דייוויד בואי, לד זפלין, פינק פלויד, מערכת של מטה, מלכה , blink-182, הרולינג סטונס, מטאליקה, פליטווד מק, הביטלס, אלטון ג'ון, הקלאש ---------------------------- - CLUSTER ----------------------------------- Centroid {היפ הופ = 97.21428571428571, ראפ = 64.85714285714286, היפ הופ = 29.285714285714285, ...} Kanye West, Post Malone, Childish Gambino, Lil Nas X, A $ AP Rocky, Lizzo, xxxtentacion, Travi $ Scott, Tyler, the Creator, Eminem, Frank Ocean, Kendrick Lamar, Nicki Minaj , דרייק ------------------------------ CLUSTER ----------------- ------------------ Centroid {אינדי רוק = 54.0, רוק = 52.0, רוק פסיכדלי = 51.0, פסיכדלי = 47.0, ...} אימפלה מאולפת, המפתחות השחורים - ---------------------------- CLUSTER --------------------- -------------- Centroid {pop = 81.96428571428571, זמרות = 41.2857142 85714285, אינדי = 22.785714285714285, ...} אד שירן, טיילור סוויפט, ריהאנה, מיילי סיירוס, בילי איליש, לורד, אלי גולדינג, ברונו מארס, קייטי פרי, חאליד, אריאנה גרנדה, בון איבר, דואה ליפה, ביונסה, סיה, פ! נק, סם סמית ', שון מנדס, מארק רונסון, מייקל ג'קסון, הלסי, לאנה דל ריי, קרלי ריי ג'פסן, בריטני ספירס, מדונה, אדל, ליידי גאגא, האחים ג'ונאס ------------ ------------------ CLUSTER ------------------------------- ---- Centroid {אינדי = 95.23076923076923, אלטרנטיבה = 70.61538461538461, אינדי רוק = 64.46153846153847, ...} עשרים ואחד טייסים, הסמיתס, פירנצה + המכונה, מועדון קולנוע דו דלתיים, 1975, דמיין דרקונים, הרוצחים, ערפד סוף שבוע, טיפוח העם, שבץ מוחי, כלוב הפיל, אש ארקייד, קופים ארקטיים ------------------------------ CLUSTER - ---------------------------------- Centroid {electronic = 91.6923076923077, House = 39.46153846153846, dance = 38.0, .. .} שרלי XCX, The Weeknd, דאפט פאנק, קלווין האריס, MGMT, מרטין גאריקס, דפש מוד, Chainsmokers, Avicii, Kygo, Marshmello, David Guetta, Major Lazer ------------------------------ CLUSTER ----- ------------------------------ Centroid {rock = 87.38888888888889, alternative = 72.11111111111111, rock alternative = 49.16666666, ...} Weezer , הפסים הלבנים, נירוונה, Foo Fighters, Maroon 5, Oasis, Panic! בדיסקוטק, גורילאז, גרין דיי, קיור, ילד נופל, OneRepublic, Paramore, Coldplay, Radiohead, Linkin Park, Red Hot Chili Peppers, Muse

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

למרות שאשכול זה הגיוני, לרוב זה לא מושלם מכיוון שהנתונים נאספים רק מהתנהגות המשתמשים.

5. ויזואליזציה

לפני כמה רגעים, האלגוריתם שלנו דמיין את אשכול האמנים בצורה ידידותית לטרמינל. אם אנו ממירים את תצורת האשכול שלנו ל- JSON ונזין אותה ל- D3.js, אז עם מספר שורות של JavaScript, יהיה לנו עץ נחמד ידידותי לאדם Radial Tidy-Tree:

עלינו להמיר את שלנו מַפָּה ל- JSON עם סכמה דומה כמו דוגמה זו d3.js.

6. מספר אשכולות

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

  1. ידע בתחום
  2. היוריסטיקה מתמטית

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

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

6.1. שיטת מרפקים

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

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

sse כפול סטטי ציבורי (מפה מקובץ, מרחק מרחק) {סכום כפול = 0; עבור (Map.Entry entry: clustered.entrySet ()) {Centroid centroid = entry.getKey (); עבור (שיא רשומה: entry.getValue ()) {d כפול = distance.calculate (centroid.getCoordinates (), record.getFeatures ()); sum + = Math.pow (d, 2); }} סכום החזר; }

לאחר מכן, אנו יכולים להפעיל את אלגוריתם K-Means לערכים שונים של kוחשב את ה- SSE עבור כל אחד מהם:

רשומות רשימת = // מערך הנתונים; מרחק מרחק = מרחק EuclideanDistance (); רשום sumOfSquaredErrors = ArrayList חדש (); עבור (int k = 2; k <= 16; k ++) {מפה אשכולות = KMeans.fit (רשומות, k, מרחק, 1000); כפול sse = Errors.sse (אשכולות, מרחק); sumOfSquaredErrors.add (sse); }

בסופו של יום, אפשר למצוא מתאים k על ידי תכנון מספר האשכולות נגד ה- SSE:

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

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

7. מסקנה

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

כרגיל, הקוד לדוגמא זמין בפרויקט GitHub שלנו, אז דאגו לבדוק אותו!