Bài tập luyện tập Phân lớp

Phiếu luyện tập chủ đề phân lớp, Classification, trình bày các bài tập theo tám nhóm chủ đề và khép lại bằng phần chú thích công thức tham khảo. Phiếu do các giảng viên thực hành soạn thảo và duy trì, với sự đóng góp của Th.S Nguyễn Thị Thu Hằng, Th.S Nguyễn Ngọc Đức và Th.S Lê Nhựt Nam.

Cây quyết định, Decision Tree¶

Bài 1¶

Nêu ngắn gọn các bước chính của quá trình phân lớp bằng cây quyết định. Trong từng bước, hãy giải thích vai trò của nó trong việc xây dựng mô hình.

Bài 2¶

Tại sao kỹ thuật cắt tỉa, pruning, lại cần thiết trong quá trình xây dựng cây quyết định? Hãy nêu một nhược điểm cụ thể khi sử dụng một tập dữ liệu riêng biệt để đánh giá việc cắt tỉa.

Bài 3¶

Cho một cây quyết định đã được xây dựng. Ta có hai lựa chọn:

Chuyển cây thành luật, sau đó cắt tỉa các luật.
Cắt tỉa cây trước, sau đó chuyển sang luật.

Phương án đầu có ưu điểm gì so với phương án sau? Giải thích cụ thể.

Bài 4¶

Phân tích độ phức tạp tính toán trong trường hợp xấu nhất của thuật toán cây quyết định. Cho tập dữ liệu $D$ , $n$ là số thuộc tính và $|D|$ là số mẫu huấn luyện. Biểu diễn kết quả theo $n$ và $|D|$ .

Bài 5¶

Cho một tập dữ liệu 5 GB với 50 thuộc tính, trong đó mỗi thuộc tính có 100 giá trị phân biệt, và bộ nhớ chính 512 MB trên máy tính xách tay. Hãy đề xuất một phương pháp hiệu quả để xây dựng cây quyết định trên tập dữ liệu lớn như vậy. Giải thích bằng ước tính bộ nhớ sử dụng.

Bài 6¶

Cho bảng dữ liệu huấn luyện sau đây lấy từ cơ sở dữ liệu nhân viên. Dữ liệu đã được biểu diễn thu gọn, ví dụ 31...35 biểu diễn khoảng tuổi 31 đến 35. Cột count thể hiện số lượng mẫu có giá trị tương ứng.

department	status	age	salary	count
sales	senior	31...35	46K...50K	30
sales	junior	26...30	26K...30K	40
sales	junior	31...35	31K...35K	40
systems	junior	21...25	46K...50K	20
systems	senior	31...35	66K...70K	5
systems	junior	26...30	46K...50K	3
systems	senior	41...45	66K...70K	3
marketing	senior	36...40	46K...50K	10
marketing	junior	31...35	41K...45K	4
secretary	senior	46...50	36K...40K	4
secretary	junior	26...30	26K...30K	6

Cho biết status là thuộc tính nhãn, class label. Hãy thực hiện:

Sửa đổi thuật toán cây quyết định cơ bản để tính đến giá trị count của từng dòng dữ liệu.
Sử dụng thuật toán để xây dựng cây quyết định từ dữ liệu trên.
Cho một mẫu dữ liệu có giá trị department = systems, age = 26...30, salary = 46K...50K. Phân lớp status của mẫu này bằng phương pháp Naive Bayes.

Bài 7¶

Giải thích sự khác biệt giữa cây quyết định ID3 và C4.5. Tại sao C4.5 được coi là cải tiến so với ID3? Hãy nêu ít nhất hai điểm cải tiến chính.

Bài 8¶

Định nghĩa Gain Ratio, tỷ lệ thu hồi thông tin, được sử dụng trong thuật toán C4.5. Giải thích tại sao tiêu chuẩn này ưu việt hơn Information Gain đơn thuần trong ID3, đặc biệt khi xử lý thuộc tính có nhiều giá trị phân biệt.

Phân lớp Naive Bayes¶

Bài 9¶

Tại sao phương pháp phân lớp Naive Bayes được gọi là naive, tức ngây thơ? Hãy tóm tắt ngắn gọn ý tưởng chính của phương pháp phân lớp Naive Bayes.

Bài 10¶

Một lớp học có 30 sinh viên. Kết quả kiểm tra cuối kỳ cho thấy 18 sinh viên đạt, ký hiệu P, và 12 sinh viên không đạt, ký hiệu F. Trong số sinh viên đạt, 15 người có học lực Giỏi và 3 người có học lực Trung bình. Trong số sinh viên không đạt, 2 người có học lực Giỏi và 10 người có học lực Trung bình.

Tính xác suất tiên nghiệm $P(P)$ và $P(F)$ .
Tính xác suất $P(Giỏi \mid P)$ và $P(Giỏi \mid F)$ .
Cho một sinh viên mới có học lực Giỏi. Sử dụng Naive Bayes để phân lớp sinh viên này.

Bài 11¶

Chứng minh tính tương đương của mô hình Logistic Regression và Naive Bayes dưới các điều kiện sau:

Mỗi thuộc tính $X_i$ được lấy từ phân phối Gaussian $P(X_i \mid Y = k) = N(\mu_{ik}, \sigma_i)$ với $\sigma_{i0} = \sigma_{i1} = \sigma_i$ .
Mỗi thuộc tính $X_i$ được lấy từ phân phối Bernoulli $P(X_i = 1 \mid Y = k) = \theta_{ik}$ .

Bài 12¶

Một vấn đề khi áp dụng Naive Bayes là xác suất bằng không, zero probability. Hãy giải thích khi nào vấn đề này xảy ra và Laplace smoothing giải quyết nó như thế nào. Cho ví dụ cụ thể.

Bài 13¶

Xét bài toán lọc thư rác, spam filtering. Xem xét dữ liệu có 100 e-mail, trong đó 60 là spam và 40 không phải spam. Các từ xuất hiện trong e-mail spam và không spam được thống kê như sau:

Từ	Spam	Không Spam
khuyến mãi	45	5
miễn phí	38	3
xin chào	10	30
báo cáo	5	25

Sử dụng Naive Bayes, phân lớp e-mail có chứa cả hai từ khuyến mãi và miễn phí. Giả sử độc lập có điều kiện giữa các từ.

Phân lớp gần nhất, K-Nearest Neighbor¶

Bài 14¶

So sánh ưu điểm và nhược điểm của phương pháp phân lớp tích cực, eager classification, ví dụ cây quyết định, Bayesian, mạng nơ ron, với phân lớp lười biếng, lazy classification, ví dụ k-nearest neighbor, case-based reasoning. Trong trường hợp nào thì lazy classification có ưu thế vượt trội?

Bài 15¶

Viết thuật toán phân lớp k-nearest neighbor với đầu vào là $k$ , số láng giềng cần tìm, $n$ , số thuộc tính mô tả mỗi mẫu dữ liệu, và tập huấn luyện $D$ . Phân tích độ phức tạp thời gian và không gian của thuật toán.

Bài 16¶

Cho tập dữ liệu sau trong không gian 2 chiều:

STT	x1	x2	Nhãn
1	1	2	A
2	2	3	A
3	3	1	B
4	6	5	B
5	7	7	A
6	8	6	B

Sử dụng k-NN với $k = 3$ và khoảng cách Euclidean, phân lớp điểm mới $x = (5, 4)$ .

Bài 17¶

Nêu ba kỹ thuật đánh chỉ số, indexing, thường được sử dụng để tăng tốc quá trình tìm kiếm láng giềng gần nhất trong k-NN. Mỗi kỹ thuật phù hợp với loại dữ liệu nào?

Phân lớp tuyến tính, Perceptron và Logistic Regression¶

Bài 18¶

Mô hình perceptron $y = f(x) = sign(w^T x + b)$ được dùng để học phân lớp nhị phân từ dữ liệu huấn luyện.

Giả sử có hai mẫu huấn luyện: mẫu dương $x_1 = (2, 1)^T$ , mẫu âm $x_2 = (1, 0)^T$ . Tốc độ học $\eta = 1$ . Bắt đầu từ $w = (1, 1)^T$ và $b = 0$ , giải các tham số của bộ phân lớp.
Giả sử có bốn mẫu huấn luyện. Mẫu dương gồm $x_1 = (1, 1)^T$ và $x_2 = (0, 0)^T$ . Mẫu âm gồm $x_3 = (1, 0)^T$ và $x_4 = (0, 1)^T$ . Có thể phân lớp đúng tất cả các mẫu bằng perceptron không? Tại sao?

Bài 19¶

Giả sử có ba mẫu dương $x_1 = (1, 0, 0)$ , $x_2 = (0, 0, 1)$ , $x_3 = (0, 1, 0)$ và ba mẫu âm $x_4 = (-1, 0, 0)$ , $x_5 = (0, -1, 0)$ , $x_6 = (0, 0, -1)$ . Áp dụng phương pháp gradient ascent chuẩn để huấn luyện bộ phân lớp logistic regression không có tham số hiệu chỉnh. Khởi tạo vector trọng số với hai giá trị khác nhau $w_0 = (0, 0, 0, 0)^T$ và $w_0 = (0, 0, 1, 0)^T$ . Vector trọng số tối ưu $w^*$ có giống nhau không? Hãy giải thích chi tiết.

Bài 20¶

Phân tích sự khác biệt giữa Logistic Regression và mô hình tuyến tính thuần túy, Linear Regression, trong bài toán phân lớp nhị phân. Tại sao hàm sigmoid được chọn làm hàm kích hoạt trong Logistic Regression? Hãy biểu diễn hàm mất mát, loss function, Binary Cross-Entropy và giải thích ý nghĩa của nó.

Đánh giá mô hình phân lớp¶

Bài 21¶

Chứng minh rằng độ chính xác, accuracy, là hàm của độ nhạy, sensitivity, và độ đặc hiệu, specificity, tức là chứng minh rằng:

Accuracy = Sensitivity \cdot P(P) + Specificity \cdot P(N)

(1)

trong đó $P(P)$ và $P(N)$ lần lượt là tỷ lệ mẫu dương và mẫu âm trong tập dữ liệu.

Bài 22¶

Trung bình điều hòa, harmonic mean, của các số thực dương $x_1, x_2, \ldots, x_n$ được định nghĩa là:

H = \frac{n}{\frac{1}{x_1} + \frac{1}{x_2} + \cdots + \frac{1}{x_n}}

(2)

Độ đo F là trung bình điều hòa của Precision và Recall. Hãy sử dụng định nghĩa này để suy ra công thức F. Ngoài ra, hãy viết $F_\beta$ theo số thực dương TP, số âm giả FN và số dương giả FP.

Bài 23¶

Các mẫu dữ liệu trong bảng sau được sắp xếp theo xác suất giảm dần do một bộ phân lớp xác suất trả về:

Số thứ tự	Nhãn thực	Xác suất
1	P	0.95
2	N	0.85
3	P	0.78
4	P	0.66
5	N	0.60
6	P	0.55
7	N	0.53
8	N	0.52
9	N	0.51
10	P	0.40

Với mỗi mẫu, tính các giá trị TP, FP, TN, FN. Tính tỷ lệ dương thật, TPR, và tỷ lệ dương giả, FPR. Vẽ đường cong ROC cho tập dữ liệu trên.

Bài 24¶

Giả sử muốn lựa chọn giữa hai mô hình dự đoán $M_1$ và $M_2$ . Đã thực hiện 10 vòng kiểm chứng chéo 10-fold trên mỗi mô hình, trong đó sử dụng cùng một cách phân chia dữ liệu tại vòng $i$ cho cả hai mô hình. Tỷ lệ lỗi của $M_1$ là 30.5, 32.2, 20.7, 20.6, 31.0, 41.0, 27.7, 26.0, 21.5, 26.0. Tỷ lệ lỗi của $M_2$ là 22.4, 14.5, 22.4, 19.6, 20.7, 20.4, 22.1, 19.4, 16.2, 35.0. Nhận xét xem mô hình nào tốt hơn đáng kể, xét ở mức ý nghĩa 1%.

Bài 25¶

Khó khăn gì xuất hiện khi đánh giá độ chính xác phân lớp trong trường hợp một đối tượng có thể thuộc nhiều lớp đồng thời, multi-label classification? Hãy đề xuất các tiêu chí để so sánh các bộ phân lớp trong trường hợp này.

Phương pháp kết hợp mô hình, Ensemble Methods¶

Bài 26¶

Boosting là gì? Giải thích tại sao nó có thể cải thiện độ chính xác trong cây quyết định. Hãy mô tả quy trình của thuật toán AdaBoost và nêu một điểm khác biệt chính giữa AdaBoost và Gradient Boosting.

Bài 27¶

XGBoost là một hệ thống học máy mở rộng cho cây tăng cường. Hàm mục tiêu có hàm mất mát huấn luyện và thành phần hiệu chỉnh:

L = \sum_i \ell(y_i, \hat{y}_i) + \sum_k \Omega(f_k)

(3)

$\hat{y}_i$ là gì? Tại vòng lặp $t$ , XGBoost cố định $f_1, \ldots, f_{t-1}$ và huấn luyện cây thứ $t$ là $f_t$ . XGBoost xấp xỉ hàm mất mát $\ell(y_i, \hat{y}_i)$ như thế nào?
$\Omega(f_k)$ là gì? Phần nào trong thành phần hiệu chỉnh cần xem xét tại vòng lặp $t$ ?

Bài 28¶

Hãy so sánh ba phương pháp ensemble phổ biến: Bagging, Boosting và Random Forest theo các tiêu chí sau: chiến lược lấy mẫu, cách kết hợp kết quả, xử lý overfitting, và trường hợp sử dụng điển hình.

Vấn đề mất cân bằng lớp, Class Imbalance¶

Bài 29¶

Vấn đề mất cân bằng lớp là gì? Nêu các chiến lược để giải quyết vấn đề này. Giả sử một ngân hàng muốn xây dựng bộ phân lớp phát hiện giao dịch thẻ tín dụng gian lận. Minh họa cách xây dựng bộ phân lớp chất lượng từ một tập dữ liệu lớn gồm nhiều giao dịch hợp lệ và rất ít giao dịch gian lận.

Bài 30¶

Phân biệt kỹ thuật oversampling và undersampling trong xử lý mất cân bằng lớp. Hãy nêu một nhược điểm cụ thể của mỗi kỹ thuật. Khi nào nên dùng SMOTE, Synthetic Minority Oversampling Technique, thay cho oversampling đơn giản?

Bài tập tổng hợp¶

Bài 31¶

Cho tập dữ liệu sau để phân lớp kết quả thi đầu vào, Pass hoặc Fail:

Số giờ học	Số bài tập	Điểm GK, điểm giữa kỳ	Kết quả
10	5	6.0	Pass
5	2	4.5	Fail
8	4	7.0	Pass
3	1	3.5	Fail
12	6	8.0	Pass
6	3	5.0	Fail
9	5	6.5	Pass
4	2	4.0	Fail

Xây dựng cây quyết định bằng tiêu chuẩn Information Gain.
Áp dụng Naive Bayes để phân lớp sinh viên mới có số giờ học 7, số bài tập 3, điểm GK 5.5.
Tính ma trận nhầm lẫn, confusion matrix, Precision, Recall và F1-score bằng phương pháp hold-out với 70% huấn luyện và 30% kiểm thử.

Bài 32¶

Trong bài toán phân lớp cảm xúc giọng nói, voice emotion classification, một hệ thống có các kết quả sau trên tập kiểm tra 200 mẫu với 4 lớp Vui, Buồn, Tức, Bình thường, mỗi lớp 50 mẫu:

Thực so với Dự đoán	Vui	Buồn	Tức	Bình thường
Vui	40	3	4	3
Buồn	2	38	5	5
Tức	3	4	39	4
Bình thường	2	3	3	42

Tính macro-average và weighted-average của Precision và Recall.
Tính độ chính xác tổng thể, overall accuracy.
Nhận xét về hiệu suất của mô hình. Lớp nào được nhận biết tốt nhất và kém nhất?

Bài 33¶

Trong bài toán chẩn đoán bệnh ung thư dương tính hoặc âm tính, một tập kiểm tra gồm 500 mẫu với 450 âm tính và 50 dương tính, được đánh giá bởi ba mô hình:

Mô hình	TP	FP	TN	FN
M1	40	20	430	10
M2	48	60	390	2
M3	35	5	445	15

Tính Accuracy, Precision, Recall và F1-score cho từng mô hình.
Trong bối cảnh y tế, chẩn đoán ung thư, ta nên chọn mô hình nào? Giải thích lý do dựa trên ý nghĩa của FP và FN trong bài toán này.
Vẽ ba đường cong ROC để so sánh, xấp xỉ định tính, và giải thích.

Chú thích và Công thức tham khảo¶

Ký hiệu và định nghĩa:

TP, True Positive: số mẫu dương được dự đoán đúng là dương.
TN, True Negative: số mẫu âm được dự đoán đúng là âm.
FP, False Positive: số mẫu âm bị dự đoán nhầm là dương, tức lỗi loại I.
FN, False Negative: số mẫu dương bị dự đoán nhầm là âm, tức lỗi loại II.

Accuracy = \frac{TP + TN}{TP + TN + FP + FN}

(4)

Precision = \frac{TP}{TP + FP}

(5)

Recall = \frac{TP}{TP + FN}

(6)

F1 = \frac{2 \cdot Precision \cdot Recall}{Precision + Recall}

(7)

F_\beta = (1 + \beta^2) \cdot \frac{Precision \cdot Recall}{\beta^2 \cdot Precision + Recall}

(8)

TPR = Recall,\quad FPR = \frac{FP}{FP + TN}

(9)