これがベトナム大学院の実態だ!

Trường Đại Học Bách Khoa Thành Phố Hồ Chí Minhの大学院修士課程に社会人入学

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.

Nhận dạng mẫu và học máy 中間試験 & 8回目 & mini project

2018年11月3日
以前から予告されていた中間試験。
問題はこちら。
f:id:k4h8:20181107124017j:plainf:id:k4h8:20181107124022j:plain
以前から告知されていた練習問題および2017年度試験と同じ問題もあったが、残念ながら初見も多く、70分あった試験時間が一瞬に感じられた。
なお、この中間試験の成績は35%に相当する。

力を出し尽くし制限時間が終わり、答案用紙が回収された後教室に残ってできなかった問題をやり直していると、なんと授業を行うという。
通常中間試験の日はそれで終わりで、授業をやらないのが通例であるが。
他の学生も疲れが出たのか、Facebookを見たり何やら授業とは関係ない作業をしたり、まともに聞いている人はほとんどいなかった。
ただ、先生のメールアドレスが板書されたので、試験終了後帰らなくてよかった。
このメールアドレスは試験にたいするいちゃもんや得点照会と思ったが念のため確認するとそのどちらでもなく、25%の成績に相当するmini projectの希望を送るためだという。

2日ぐらいたってクラスリーダーの角刈り君から今後の教科書と練習問題、それに件のmini project一覧が送られてきた。
内容は以下の33種類。

1. Study the PCA tool of WEKA and apply it in feature extraction for the following dataset:
(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)
where each pattern is represented by feature 1, feature 2 and the class label.
2. Implement LDA method for the following training data set and apply it in feature extraction:
(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)
where each pattern is represented by feature 1, feature 2 and the class label. (*)
3. Study how to use the X-means algorithm of WEKA and apply it in a clustering problem.
4. Study how to use the EM algorithm of WEKA and apply it in a clustering problem.
5. Study how to use the Bagging and ADABOOST algorithm of WEKA and apply it in a classification problem.
6. Implement ADABOOST algorithm and apply it in a classification problem. (*)
7. Study how to use Decision Tree classifier (J 4.8) of WEKA and apply it in a classification problem.
8. Study how to use SVM of LibSVM and apply it in a classification problem.
9. Study how to use SVM of MATLAB and apply it in a classification problem.
10. Implement back-propagation algorithm to train ANN and apply it in a classification problem. (*)
11. Implement k-NN algorithm and apply it in a classification problem. (*)
12. Implement distance-weighted k-nearest neighbor algorithm and apply it in a classification problem. (*)
13. Implement Naïve Bayes classifier and apply it in a classification problem. (*)
14. Implement logistic regression method and apply it in a classification problem. (*)
15. Study how to use the tools for attribute selection in WEKA and apply it in a benchmark dataset for customer churn prediction problem.
16. Study how to use ANN tool of Spice-Neuro software and apply it in a classification problem.
17. Study how to use ANN tool of MATLAB and apply it in a classification problem.
18. Study how to use RBF network tool of WEKA and apply it in a classification problem.
19. Study how to use RBF network tool of MATLAB and apply it in a classification problem.
20. Implement Squeezer algorithm and apply it in a clustering problem with categorical data. (*)
21. Implement k-means algorithm (with some centroid initialization technique) and apply it in a clustering problem. (*)
22. Implement HAC clustering algorithm and apply it in a clustering problem. (*)
23. Implement Condensed Nearest Neighbors algorithm and apply it in a classification problem. (*)
24. Implement the incremental clustering algorithm Leaders and apply it in a clustering problem. (*)
25. Implement Naïve Rank algorithm for reducing the training set and apply it in a classification using k-Nearest-neighbors. (*)
26. Implement anytime classification algorithm and apply it in a classification problem. (*)
27. Implement the improved k-NN algorithm with branch-and-bound technique. (*)
28. Implement a propotype selection method which is based on clustering and apply it in a classification problem using k-Nearest-neighbors. (*)
29. Implement the improved k-NN algorithm with the support of k-d-tree. (*)
30. Study how to use HMM (hidden Markov model) of MATLAB.
31. Study how to use PCA tool of MATLAB and apply it in the feature extraction for the following dataset:
(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)
where each pattern is represented by feature 1, feature 2 and the class label.
32. Study how to use Decision Tree classifier of RapidMiner and apply it in a classification problem.
33. Study how to use the tools for attribute selection in RapidMiner and apply it in a benchmark dataset for customer churn prediction problem.

この中からどれか1つを選び、先生にメールをする。
ただ、すでに希望者がいるものは選べないので、早い者勝ちとなる。
とりあえずMATLABと書かれているものならやるべきことが具体的なので、

9 SVM of MATLAB.
17 ANN tool of MATLAB.
19 RBF network tool of MATLAB.
30 HMM (hidden Markov model) of MATLAB.
31 PCA tool of MATLAB.

をそれぞれMATLAB上で動かしてみたところHMM (hidden Markov model) が一番簡単そうであったため希望を送ったところ競合がなかったため無事に決定された。
このmini projectの締め切りがいつまでなのかの告知はまだないが、今後の授業を通じて知らされるものと思われる。

Phương pháp nghiên cứu khoa học nâng cao 5回目

2018年11月3日
Part3-14(P165)から
この日は授業中のPC操作が多く、授業中の提出もなかったので実質ほとんどが休憩時間。
レポートの締め切り情報もなかったので来た意味はなかった。
この日はNhの中間試験もあったのでそれであればこっちは休んでも良かったな。

さて、本科目もいよいよ次回で最終回。
60%レポートの仕様説明がされるか。

Nhận dạng mẫu và học máy 7回目

2018年10月27日
中間試験の前の回なので一応来た方がいいかと思って出席したが、特に問題の解説などはなく、配布資料を淡々と進めるだけだった。
出席の意思表示をしに来ただけだ。

Nhận dạng mẫu và học máy 4回目は自主休講で

2018年10月6日
この日はPhương pháp nghiên cứu khoa học nâng caoが1年越しの開講ということでお祭り騒ぎとなっており、かつ、同授業が4時間という長丁場であったこと、さらに体調不良もあり欠席とした。
先生も突然無断欠勤とかあるので、おあいこということで。
一応出席を取る授業なのだが、これまでも出席は取るが平常点に全く加味しないという、何の意味もない出席確認をする授業もあったことから、出席をしたからと言って加点されるわけではない点に気をつけたい。