Nhận dạng mẫu và học máy 中間試験模範解答
同科目の模範解答が配布された。
仮に今期で単位が取れなくても来期でとれるので、確実に単位をあげに来ている科目とわかる。
内容は以下の通り。
Ñeà thi giöõa hoïc kyø I (2018)
Moân : Nhận dạng mẫu và Học Máy
Lớp Cao học
Thôøi gian: 70 phuùt
(Sinh viên được phép tham khảo tài liệu)
Đề thi gồm 2 trang
1. (1.25 điểm) Trả lời các câu hỏi sau đây, mỗi câu 0.25 điểm:
1.1 (Đúng/Sai) Giải thuật EM thuộc loại gom cụm mềm (soft clustering).
1.2 (Đúng/Sai) Giải thuật gom cụm k-Means thì phù hợp với dữ liệu rời rạc (categorical data) hơn là dữ liệu liên tục.
1.3 Giải thuật gom cụm EM thuộc loại giải thuật gom cụm nào sau đây
A. gom cụm phân cấp B. Gom cụm phân hoạch
C. Gom cụm dựa vào mô hình D. Gom cụm dựa vào mật độ
1.4 Luật phân lớp có thể được rút trích dễ dàng từ phương pháp phân lớp nào sau đây:
A. k-lân cận gần nhất B. Cây quyết định
C. Naïve Bayes D. các trường hợp trên đều sai
1.5 Phát biểu nào sau đây không đúng
A. Giải thuật k-Means có độ phức tạp gần như tuyến tính
B. Giải thuật gom cụm dựa vào mật độ có thể sinh ra các cụm có hình dạng bất kỳ
C. Giải thuật k-Means thích hợp với việc gom cụm thành những cụm có dạng hình cầu
D. Giải thuật gom cụm phân cấp tách có độ phức tạp tinh toán là hàm mũ.
E. Giải thuật gom cụm phân cấp gộp có độ phức tạp tinh toán là hàm mũ.
Ans
1.1 Đúng
1.2 Sai
1.3 C
1.4 B
1.5 E
2. (0.5 điểm) Cho một tập dữ liệu mẫu có số đặc trưng là n, khi tính ma trận hiệp phương sai cho tập dữ liệu, ta được một ma trận vuông bậc n mà các phần tử trên đường chéo chính khác 0, còn các phần tử còn lại đều bằng 0. Ma trận hiệp phương sai có tính chất như vậy nói lên điều gì về dữ liệu ?
Ans:
Ma trận hiệp phương sai như vậy cho thấy các thuộc tính của dữ liệu độc lập, không hề phụ thuộc vào nhau.
3. (0.75 điểm) Nêu sự khác biệt giữa lựa chọn đặc trưng (feature selection) và trích yếu đặc trưng (feature abstraction). PCA là phương pháp lựa chọn đặc trưng hay trích yếu đặc trưng ?
4. (0.75 điểm) Nêu sự khác biệt giữa lựa chọn prototype (prototype selection) và trích yếu prototype (prototype abstraction). Naïve Rank Reduction là phương pháp lựa chọn prototype hay trích yếu prototype ?
5. (0.75 điểm)
a. Cho các xác xuất: P(A|B) = 2/3, P(A|~B) = 1/3, P(B) = 1/3. Hãy tính xác xuất có điều kiện P(B|A).
Hint : Áp dụng công thức
b. Để có thể áp dụng bộ phân lớp Naive Bayes, chúng ta cần một giả định gì về tính chất dữ liệu.
Ans
a) Ta có : P(A) = P(A|B).P(B) + P(A|~B).P(~B)
= (2/3).(1/3) + (1/3).(2/3) = 4/9
P(B|A) = P(A|B).P(B)/P(A) = (1/3).(3/3)/(4/9) = ½
6. (1 điểm) Giải thích hai phương pháp kiểm tra chéo (cross-validation) sau đây: kiểm tra chéo k-phần (k-fold cross validation) và kiểm tra chéo bỏ ra một phần tử (leave-one-out cross validation).
7. (1 điểm)
Chúng ta dùng bộ phân lớp 5-lân cận gần nhất có trọng số (weighted 5-NN classifier) để phân lớp mẫu thử P. Giả sử khoảng cách giữa P với năm lân cận gần nhất (X1, X2, X3, X4 và X5) lần lượt là d1 = 1, d2 = 3, d3 = 4, d4 = 5 và d5 =8. Nếu X1, X2 thuộc lớp + và X3, X4 , X5 thuộc lớp -. Vậy P sẽ được phân vào lớp nào?
Ans
Vì khoảng cách nhỏ nhât là d1 = 1 và khoảng cách lớn nhất là d5 = 8, các trọng số ứng với các mẫu (X1, X2, X3, X4 và X5) như sau:
wi = (d5-di)/(d5-d1) = (8-di)/(8-1) = (8-di)/7
w1 = (8-1)/7 = 1, w2 = (8-3)/7 = 5/7, w3 = (8-4)/7 = 4/7, w4 = (8-5)/7 = 3/7, w5 = (8-8)/7 = 0
+ = w1 + w2 = 1 + 5/7 và - = w3 + w4 + w5 = 4/7 + 3/7 + 0
Vì + > - nên mẫu thử thuộc về lớp +.
8. (1.5 điểm)
Cho tập mẫu thuộc hai lớp 1 và 2 sau đây:
(1, 1, 1), (1, 2, 1), (1, 3, 1), (2, 1, 1), (2, 2, 1), (2, 3, 1), (2, 3.5, 1),
(2.5, 2, 1), (3.5, 1, 1), (3.5, 2, 1), (3.5, 3, 2), (3.5, 4, 2), (4.5, 1, 2)
(4.5, 2, 2), (4.5, 3, 2), (5, 4, 2), (5, 5, 2), (6, 3, 2), (6, 4, 2), (6, 5, 2)
trong đó mỗi mẫu được biểu diễn bằng thuộc tính 1, thuộc tính 2 và nhãn lớp.
Tính centroid của mỗi lớp. Áp dụng bộ phân lớp minimum-distance classifier để xác định lớp cho mẫu thử P = (3.8, 3.1).
Ans
Centroid của lớp 1 :
1 = ((1+1+1+2+2+2+2 + 2.5+ 3.5+3.5)/10, (1+2+3+1+2+3+3.5+2+1+2)/10)=(2.05, 2.05)
Centroid của lớp 1 :
2 =((3.5 + 3.5 +4.5 + 4.5 + 4.5+5+5+6+6+6)/10, (3+4+1+2+3+4+5+3+4+5)/10)= (4.85, 3.4)
P = (3.8, 3.1)
D(P, 1 ) =sqrt((3.8 – 2.05)2 +(3.1 - 2.05)2) = 2.04
D(P, 2 )= sqrt((3.8-4.85)2 + (3.1 – 3.4)2) = 1.09
D(P, 2 ) < D(P, 1 )
Suy ra : P thuộc lớp 2
9. (1 điểm)
Cho ma trận nhầm lẫn (confusion matrix) của một bộ phân lớp gồm 3 lớp như sau :
Predicted
C1 C2 C3
Actual C1 19 4 1
C2 3 20 4
C3 2 3 21
Tinh độ chính xác (accuracy) của bộ phân lớp này.
Ans:
a) Accuracy = (t_C1 + t_C2 + t_C3)/N
= (19+20+21)/(24 + 27 + 26) = 60/77 = 0.779
10. (1 điểm)
a. Cho hai mẫu (mỗi mẫu gồm 3 thuộc tính) X = (7, 4, 3), Y = (4, 1, 8), hãy tính khoảng cách Manhattan giữa hai mẫu X và Y. (0.5 điểm)
b. Cho hai mẫu (mỗi mẫu gồm 8 thuộc tính nhị phân) X = (1, 0, 1, 1, 1, 0, 1, 1), Y = (0, 1, 1, 0, 0, 1, 0, 0), hãy tính khoảng cách giữa hai mẫu X và Y. (0.5 điểm)
Ans:
a) Khoảng cách Manhattan: d(X, Y) = |7- 4|+ |4 – 1| + |3 – 8| = 11
b) X và Y có 7 thành phần khác biệt nhau
d(X, Y) = 7
11. (0.5 điểm)
Gom cụm gia tăng là gì? Nêu một nhược điểm của giải thuật gom cụm gia tăng Leader.
