1
Đáp án bài tập
chương 5 :
Gom nhóm DL
2
BÀI TẬP
• Thời gian : 15’
• Cho DL sau : {2,3,4,10,11,12,20,25,30} và k =
2
• Với trung tâm các nhóm là (m
1
, m
2
), sử
dụng thuật toán k-means để xác định các
nhóm. Tính độ đo SSE cho từng nhóm ở
vòng lặp đầu tiên và cuối cùng.
• Dưới đây là một đáp án.
2
3
Đáp án : k - MEANS
• Cho tập DL 1 chiều sau và k = 2 :
{2,3,4,10,11,12,20,25,30}
• Bước 1 :
– Giả sử chọn các trung tâm cụm là : m
1
=5, m
2
=10
• Gán các đối tượng vào hai cụm. Thu được :
– K

– Trung tâm cụm mới : m
1
=7, m
2
=25
• Các cụm thu được cuối cùng :
– K
1
={2,3,4,10,11,12}, K
2
={20,30,25}
– SSE = 150
• Thuật toán dừng vì các trung tâm cụm không thay đổi .
3
5
Bài tập : THUẬT TOÁN AGNES
• Thời gian : 20’
• Cho tập DL gồm 6 điểm
trong không gian 2
chiều. Sử dụng thuật
toán AGNES với
Complete link (khoảng
cách xa nhất giữa 2
điểm của 2 nhóm khác
nhau) để gom nhóm.
Điểm Tọa độ x Tọa độ y
P1 0.40 0.53
P2 0.22 0.38
P3 0.353 0.32
P4 0.26 0.19

• Dist({3,6},{1}) =max(dist(3,1),dist(6,1))
=max(0.22, 0.24) = 0.24
(cần liệt kê đầy đủ các khoảng cách giữa các nhóm)
8
Đáp án : THUẬT TOÁN AGNES
Sử dụng Complete Link :
5. dist(2,5) là nhỏ nhất nên gộp P2 và P5. Ta có các nhóm
sau : {1}, {4}, {3,6}, {2,5}
6. Tính khoảng cách giữa các nhóm. Ví dụ :
• dist({3,6},{2,5})
= max(dist(3,2),dist(6,2),dist(3,5),dist(6,5))
= max(0.15, 0.24, 0.28, 0.39) = 0.39
• dist({3,6},{4}) = max(dist(3,4),dist(6,4)) = max(0.16,
0.22) = 0.22
• ........ (cần liệt kê đầy đủ các khoảng cách giữa các nhóm)
• dist({3,6},{4}) nhỏ nhất nên gộp các nhóm {3,6}, {4}
thành một nhóm.
• Ta thu được các nhóm : {1},{2,5},{3,4,6}
5
9
Đáp án : THUẬT TOÁN AGNES
Sử dụng Complete Link :
7.Tiếp tục :
• Tính khoảng cách giữa các nhóm : ….
• Gộp {1} với {2,5} thu được các nhóm {1,2,5},
{3,4,6}
8.dist ({3,4,6},{1,2,5})= 0.39
9.Gộp 2 nhóm này ta thu được nhóm “toàn bộ”
và thuật toán dừng
10