מיזוג צעד אחר צעד

חלק מהיחידה למידה בלתי מונחית במסלול ה-Machine Learning של Coddy. שיעור 16 מתוך 51.

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

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

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

חמש אוהלים לאורך נהר במרחקים 2, 7, 15, 19 ו-33 מטרים, מוצגים בחמש שורות. בשלב 1 ממזגים את 15 ו-19, בשלב 2 ממזגים את 2 ו-7, בשלב 3 מחברים את שתי הקבוצות האלה, בשלב 4 מוסיפים את 33

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

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # חבר את הרשימות
groups.pop(1)  # הסר את [7], שנמצאת כעת בקבוצה 0
print(groups)

זה מדפיס [[2, 7], [15, 19], [33]]. מיזוג אחר מיזוג — זוהי אשכול היררכי אגלומרטיבי.

אתגר

בינוני

משפחות מציבות את שמשיות החוף שלהן קרוב זו לזו. קבץ את 10 השמשיות שב־spots באמצעות מיזוג, עד שנותרות wanted קבוצות. closest_pair(groups) מחזירה את המיקומים i, j של שתי הקבוצות הקרובות ביותר.

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

עבור שמשיות אחרות ו־wanted 3:

Merge [33] and [35]
Merge [30] and [33, 35]
Merge [3] and [8]
3 groups: [[3, 8], [30, 33, 35], [70]]

נסו בעצמכם

import numpy as np

# המיקומים של 10 שמשיות חוף, במטרים ממגדל המציל
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# מחזירה i, j (i < j): המיקומים של שתי הקבוצות שהממוצעים שלהן הקרובים ביותר זה לזה
def closest_pair(groups):
    best_i, best_j = 0, 1
    best_gap = abs(np.mean(groups[0]) - np.mean(groups[1]))
    for i in range(len(groups)):
        for j in range(i + 1, len(groups)):
            gap = abs(np.mean(groups[i]) - np.mean(groups[j]))
            if gap < best_gap:
                best_i, best_j, best_gap = i, j, gap
    return best_i, best_j


wanted = int(input())

# כתבו את הקוד שלכם למטה