Gộp từng bước

Thuộc phần Học không giám sát trong hành trình Machine Learning của Coddy. Bài học 16 trên 51.

Chương này tạo một cây phân cấp cho dữ liệu của bạn, rồi chia cây thành các nhóm. Dưới đây là mười quả bóng thể thao, được sắp xếp theo kích thước và trọng lượng:

Sơ đồ cây về mười quả bóng thể thao. Những quả bóng nhỏ như bóng golf, bóng tennis và bóng chày nối với nhau ở thấp về một phía, những quả bóng lớn như bóng đá và bóng rổ nối với nhau ở phía bên kia, và một đường nét đứt chia cây thành hai nhóm này

Cây phát triển từ dưới lên. Bắt đầu với từng điểm riêng lẻ, gộp hai nhóm gần nhau nhất rồi lặp lại:

Năm chiếc lều dọc theo một con sông ở các vị trí 2, 7, 15, 19 và 33 mét, được vẽ thành năm hàng. Bước 1 gộp 15 và 19, bước 2 gộp 2 và 7, bước 3 gộp hai nhóm đó, bước 4 thêm 33

Khoảng cách giữa hai nhóm là khoảng cách giữa các giá trị trung bình của chúng. Gộp các danh sách như sau:

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # gộp các danh sách
groups.pop(1)  # xóa [7], giờ đã nằm trong nhóm 0
print(groups)

Lệnh này in ra [[2, 7], [15, 19], [33]]. Gộp hết lần này đến lần khác, đó là phân cụm kết tụ (agglomerative clustering).

Thử thách

Trung bình

Các gia đình dựng những chiếc ô bãi biển sát nhau. Gộp 10 chiếc ô trong spots cho đến khi còn lại wanted nhóm. closest_pair(groups) trả về vị trí i, j của hai nhóm gần nhau nhất.

Bắt đầu với mỗi chiếc ô riêng lẻ, trong một danh sách chỉ có một chiếc.
Khi có nhiều nhóm hơn wanted: in ra lần gộp, gộp cặp đó, xóa nhóm thứ hai.
In ra các nhóm còn lại.

Với các chiếc ô khác và wanted bằng 3:

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

Tự làm thử

import numpy as np

# Vị trí của 10 chiếc ô trên bãi biển, tính bằng mét từ tháp cứu hộ
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# Trả về i, j (i < j): vị trí của hai nhóm có giá trị trung bình gần nhau nhất
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())

# Viết code của bạn bên dưới