Phương Pháp Phân Cụm Kmeans và Ứng Dụng Vào Nhận Diện Chữ Số Viết Tay

Phân cụm Kmeans là một trong những thuật toán phổ biến trong lĩnh vực Machine Learning. 71 trang · Đại học Huế · 2019.

• Tác giả: Ngô Trần Hoàng Lâm
• Người hướng dẫn: TS. Ngô Thời Nhân
• Trường học: Đại học Huế
• Chuyên ngành: Tin học kinh tế
• Đề tài: Phương Pháp Phân Cụm Kmeans Và Ứng Dụng Vào Bài Toán Nhận Diện Chữ Số Viết Tay
• Loại tài liệu: khóa luận tốt nghiệp
• Năm xuất bản: 2019
• Địa điểm: Huế

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. PHẦN I: Lý do chọn đề tài
• 1.1. Mục tiêu nghiên cứu
• 1.2. Đối tượng và phạm vi nghiên cứu
• 1.3. Phương pháp nghiên cứu
• 1.4. Cấu trúc khóa luận
• 2. PHẦN II: NỘI DUNG
• 2.1. Chương 1: Giới thiệu về Học máy
• DANH MỤC HÌNH ẢNH
• DANH MỤC BẢNG BIỂU
• DANH MỤC CHỮ VIẾT TẮT
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về Phân Cụm Kmeans và Nhận Diện Chữ Số Viết Tay

Phân cụm Kmeans là một trong những thuật toán phổ biến trong lĩnh vực Machine Learning. Thuật toán này giúp phân loại dữ liệu thành các nhóm dựa trên sự tương đồng. Trong bối cảnh nhận diện chữ số viết tay, Kmeans đóng vai trò quan trọng trong việc phân loại các mẫu chữ số. Bài viết này sẽ khám phá cách mà Kmeans được áp dụng để nhận diện chữ số viết tay, từ đó giúp cải thiện độ chính xác trong các ứng dụng thực tiễn.

1.1. Khái niệm về Phân Cụm Kmeans

Phân cụm Kmeans là một phương pháp phân tích dữ liệu, giúp nhóm các điểm dữ liệu thành các cụm dựa trên khoảng cách. Thuật toán này hoạt động bằng cách xác định các trọng tâm cụm và phân loại các điểm dữ liệu gần nhất vào các cụm tương ứng.

1.2. Tầm quan trọng của Nhận Diện Chữ Số Viết Tay

Nhận diện chữ số viết tay có nhiều ứng dụng thực tiễn, từ nhận diện biển số xe đến xử lý phiếu hàng hóa. Việc áp dụng Kmeans trong lĩnh vực này giúp cải thiện độ chính xác và hiệu suất của các hệ thống nhận diện.

II. Vấn đề và Thách thức trong Nhận Diện Chữ Số Viết Tay

Mặc dù có nhiều tiến bộ trong công nghệ nhận diện chữ số viết tay, nhưng vẫn tồn tại nhiều thách thức. Các yếu tố như độ chính xác của dữ liệu, sự đa dạng trong cách viết và độ phức tạp của các mẫu chữ số là những vấn đề cần được giải quyết. Việc áp dụng thuật toán Kmeans có thể giúp giảm thiểu những thách thức này.

2.1. Độ Chính Xác của Dữ Liệu

Độ chính xác của dữ liệu đầu vào là yếu tố quyết định đến hiệu quả của thuật toán. Dữ liệu không đồng nhất hoặc có nhiều nhiễu có thể dẫn đến kết quả không chính xác.

2.2. Sự Đa Dạng trong Cách Viết

Mỗi người có cách viết khác nhau, điều này tạo ra sự đa dạng trong các mẫu chữ số. Kmeans cần phải được điều chỉnh để nhận diện chính xác các mẫu này.

III. Phương Pháp Phân Cụm Kmeans trong Nhận Diện Chữ Số Viết Tay

Phương pháp phân cụm Kmeans được áp dụng để nhóm các mẫu chữ số viết tay thành các cụm. Quá trình này bao gồm việc xác định số lượng cụm K và tối ưu hóa các trọng tâm. Việc áp dụng Kmeans giúp cải thiện khả năng nhận diện chữ số viết tay một cách hiệu quả.

3.1. Cách Thức Hoạt Động của Kmeans

Kmeans hoạt động bằng cách khởi tạo K trọng tâm ngẫu nhiên, sau đó phân loại các điểm dữ liệu vào các cụm dựa trên khoảng cách đến các trọng tâm. Quá trình này lặp lại cho đến khi không còn sự thay đổi nào trong các cụm.

3.2. Ưu Điểm và Nhược Điểm của Kmeans

Kmeans có ưu điểm là đơn giản và dễ triển khai. Tuy nhiên, nó cũng có nhược điểm như nhạy cảm với việc chọn số lượng cụm K và có thể bị ảnh hưởng bởi các điểm ngoại lệ.

IV. Ứng Dụng Thực Tiễn của Phân Cụm Kmeans trong Nhận Diện Chữ Số Viết Tay

Phân cụm Kmeans đã được áp dụng thành công trong nhiều hệ thống nhận diện chữ số viết tay. Các nghiên cứu cho thấy rằng việc sử dụng Kmeans có thể cải thiện đáng kể độ chính xác của các mô hình nhận diện. Các ứng dụng này không chỉ giới hạn trong lĩnh vực học máy mà còn mở rộng ra nhiều lĩnh vực khác.

4.1. Kết Quả Nghiên Cứu và Thí Nghiệm

Nhiều nghiên cứu đã chỉ ra rằng Kmeans có thể đạt được độ chính xác cao trong việc nhận diện chữ số viết tay. Các thí nghiệm cho thấy rằng việc tối ưu hóa số lượng cụm K là rất quan trọng.

4.2. Ứng Dụng trong Thực Tế

Kmeans được sử dụng trong nhiều ứng dụng thực tế như nhận diện biển số xe, xử lý hóa đơn và nhiều hệ thống tự động khác. Điều này chứng tỏ tính ứng dụng cao của phương pháp này.

V. Kết Luận và Tương Lai của Phân Cụm Kmeans trong Nhận Diện Chữ Số Viết Tay

Phân cụm Kmeans đã chứng minh được giá trị của nó trong việc nhận diện chữ số viết tay. Tương lai của phương pháp này hứa hẹn sẽ còn nhiều tiềm năng với sự phát triển của công nghệ Học sâu (Deep Learning). Việc kết hợp Kmeans với các phương pháp học máy khác có thể tạo ra những bước tiến mới trong lĩnh vực này.

5.1. Tiềm Năng Phát Triển

Với sự phát triển không ngừng của công nghệ, Kmeans có thể được cải tiến để xử lý các bài toán phức tạp hơn trong nhận diện chữ số viết tay.

5.2. Hướng Nghiên Cứu Tương Lai

Nghiên cứu có thể tập trung vào việc kết hợp Kmeans với các thuật toán học sâu để nâng cao độ chính xác và hiệu suất trong nhận diện chữ số viết tay.

Nội dung chính

Bối cảnh và vấn đề nghiên cứu

Trong xu thế phát triển của cuộc Cách mạng Công nghiệp 4.0, trí tuệ nhân tạo (AI) và học máy (Machine Learning) đã trở thành các công cụ quan trọng, hỗ trợ tự động hóa từ những tác vụ đơn giản thường nhật cho đến các công việc phức tạp như phân tích dữ liệu và dự báo. Học máy được phân chia thành hai nhóm phương pháp nền tảng chính: học có giám sát (Supervised Learning) và học không giám sát (Unsupervised Learning). Trong khi các nghiên cứu khóa trước tại Khoa Hệ thống Thông tin Kinh tế (Trường Đại học Kinh tế – Đại học Huế) chủ yếu tiếp cận theo hướng học có giám sát, tác giả Ngô Trần Hoàng Lâm đã lựa chọn hướng tiếp cận học không giám sát nhằm so sánh, đánh giá sự tương đồng và khác biệt về cơ chế cũng như hiệu năng giữa hai phương pháp này.

Bên cạnh đó, bài toán nhận dạng ký tự quang học nói chung và nhận diện chữ số nói riêng luôn là một chủ đề nhận được sự quan tâm lớn. Trong khi bài toán nhận dạng chữ in đã đạt được độ chính xác cao và được thương mại hóa rộng rãi, bài toán nhận dạng chữ viết tay vẫn tồn tại nhiều thách thức do sự đa dạng trong phong cách viết, nét chữ và độ biến dạng của từng cá nhân. Việc nhận dạng chính xác chữ số viết tay có giá trị ứng dụng thực tiễn cao trong các lĩnh vực như: nhận dạng biển số xe, số hóa bảng điểm, xử lý chứng từ hàng hóa và tự động phân loại mã bưu chính trên phong bì thư. Xuất phát từ bối cảnh đó, khóa luận tập trung nghiên cứu đề tài: "Phương pháp phân cụm KMeans và ứng dụng vào bài toán nhận diện chữ số viết tay".

Mục tiêu nghiên cứu:

1. Tìm hiểu những lý thuyết cơ bản về học máy.
2. Nắm vững thuật toán hồi quy Logistic (Logistic Regression) trong học có giám sát và thuật toán phân cụm KMeans trong học không giám sát.
3. Xây dựng chương trình thử nghiệm nhận dạng chữ số viết tay trên môi trường GNU Octave/Matlab.
4. So sánh kết quả thực nghiệm giữa thuật toán phân cụm KMeans và thuật toán Logistic Regression trên cùng một bộ dữ liệu.

Đối tượng và phạm vi nghiên cứu:

• Đối tượng nghiên cứu: Bài toán phân cụm dữ liệu và thuật toán KMeans; bài toán hồi quy tuyến tính và phi tuyến; bài toán phân lớp nhị phân và phân lớp đa lớp (Multiclass Classification); tập mẫu chữ số viết tay trích xuất từ cơ sở dữ liệu chuẩn MNIST.
• Phạm vi nghiên cứu: Các thuật toán tối ưu hóa trong học có giám sát; các giải thuật phân cụm trong học không giám sát; kỹ thuật lập trình và thực thi mô hình học máy trên nền tảng Octave/Matlab.

---

Cơ sở lý thuyết và phương pháp nghiên cứu

Khóa luận thiết lập nền tảng lý thuyết trên hai trụ cột của học máy: học không giám sát với trọng tâm là phân cụm dữ liệu, và học có giám sát với mô hình hồi quy Logistic.

1. Khung lý thuyết và mô hình toán học

Thuật toán phân cụm KMeans: KMeans là thuật toán học không giám sát dựa trên phân vùng (Partitioning Method), nhằm chia $n$ quan sát đa chiều thành $K$ cụm rời rạc ($S = {S_1, S_2, \dots, S_K}$) sao cho tổng bình phương khoảng cách giữa các điểm dữ liệu đến trọng tâm cụm tương ứng là nhỏ nhất. Mục tiêu tối ưu hóa được phát biểu bằng công thức:

$$\arg\min_S \sum_{i=1}^{K} \sum_{x \in S_i} |x - \mu_i|^2$$

Trong đó $\mu_i$ là giá trị trung bình (trọng tâm) của các điểm dữ liệu trong cụm $S_i$. Khoảng cách giữa điểm dữ liệu $x^{(j)}$ và trọng tâm $\mu_k$ được đo bằng khoảng cách Euclidean:

$$E = \sum_{j=1}^{m} \sum_{k=1}^{K} |x^{(j)} - \mu_k|^2$$

Thuật toán thực thi thông qua 4 bước tuần hoàn:

1. Khởi tạo: Chọn ngẫu nhiên $K$ điểm làm trọng tâm ban đầu $\mu_1, \mu_2, \dots, \mu_K$.
2. Gán cụm: Gán mỗi điểm dữ liệu $x^{(i)}$ vào cụm có trọng tâm gần nhất: $$c^{(i)} = \arg\min_k |x^{(i)} - \mu_k|^2$$
3. Cập nhật trọng tâm: Tính toán lại vị trí trọng tâm cho từng cụm dựa trên trung bình cộng tọa độ các điểm thuộc cụm: $$\mu_k = \frac{1}{|S_k|} \sum_{x \in S_k} x$$
4. Điều kiện dừng: Lặp lại bước 2 và bước 3 cho đến khi vị trí các trọng tâm không đổi hoặc đạt số vòng lặp tối đa.

Ngoài ra, văn bản phân tích ba biến thể liên quan của KMeans:

• K-medians: Sử dụng trung vị thay vì trung bình cộng và tính theo khoảng cách Manhattan, giảm độ nhạy với dữ liệu ngoại lai.
• K-medoids (PAM - Partitioning Around Medoids): Chọn chính điểm dữ liệu thực tế làm trọng tâm cụm, tăng độ bền vững trước nhiễu.
• Fuzzy C-means (Phân cụm mờ): Cho phép một điểm dữ liệu thuộc về nhiều cụm với các mức độ thành viên (membership degree) khác nhau.

Mô hình Hồi quy Logistic (Logistic Regression) và Kỹ thuật One-vs-All: Logistic Regression được sử dụng làm mô hình đối chứng. Mô hình áp dụng hàm Sigmoid để ánh xạ giá trị đầu ra về khoảng xác suất $[0, 1]$:

$$g(z) = \frac{1}{1 + e^{-z}}, \quad \text{với } z = \theta^T x$$

Để đảm bảo khả năng hội tụ đến cực tiểu toàn cục duy nhất, khóa luận xây dựng hàm chi phí lồi (Convex Cost Function) dựa trên hàm hợp lý cực đại:

$$J(\theta) = -\frac{1}{m} \sum_{i=1}^{m} \left[ y^{(i)} \log(h_\theta(x^{(i)})) + (1 - y^{(i)}) \log(1 - h_\theta(x^{(i)})) \right]$$

Để giải quyết hiện tượng quá phù hợp (Overfitting), kỹ thuật chuẩn hóa (Regularization) thêm tham số $\lambda$ được đưa vào:

$$J(\theta) = -\frac{1}{m} \sum_{i=1}^{m} \left[ y^{(i)} \log(h_\theta(x^{(i)})) + (1 - y^{(i)}) \log(1 - h_\theta(x^{(i)})) \right] + \frac{\lambda}{2m} \sum_{j=1}^{n} \theta_j^2$$

Để phân loại 10 chữ số (từ 0 đến 9), tác giả triển khai chiến lược One-vs-All (một-với-tất-cả), biến đổi bài toán đa lớp thành 10 bài toán phân loại nhị phân riêng biệt. Mỗi lớp $k \in {1, \dots, 10}$ được huấn luyện một vectơ tham số $\theta^{(k)}$ riêng; nhãn dự đoán cho mẫu mới là nhãn có giá trị hàm giả thiết lớn nhất.

2. Phương pháp nghiên cứu thực tế và Nguồn dữ liệu

• Phương pháp giải tích toán học: Chứng minh và thiết lập các hàm chi phí có tính chất lồi ngặt nhằm tránh việc thuật toán bị kẹt tại các điểm cực tiểu cục bộ.
• Phương pháp thực nghiệm và lập trình: Tác giả tự lập trình toàn bộ thuật toán trên nền tảng GNU Octave/Matlab thông qua tệp mã nguồn Kmeans_mnist.m, không sử dụng các hộp công cụ (toolbox) dựng sẵn nhằm kiểm soát chi tiết quá trình tính toán ma trận, thời gian thực thi và cơ chế hội tụ.
• Nguồn dữ liệu: Tập dữ liệu chuẩn MNIST (Modified National Institute of Standards and Technology database) do LeCun, Cortes và Burges cung cấp. Tác giả trích xuất một tập con gồm 5.000 mẫu chữ số viết tay từ 250 người viết khác nhau, phân bổ đồng đều tuyệt đối với 500 mẫu cho mỗi chữ số từ 0 đến 9. Mỗi mẫu là một ảnh xám (grayscale) kích thước $20 \times 20$ pixel, chuẩn hóa độ sáng từ 0 đến 255 và được làm phẳng (flatten) thành một vectơ hàng $1 \times 400$. Ma trận dữ liệu đầu vào $X$ có kích thước $5000 \times 400$ và vectơ nhãn $y$ có kích thước $5000 \times 1$ (nhãn 1 đến 9 đại diện cho chữ số 1–9, nhãn 10 đại diện cho chữ số 0).

---

Nội dung chính theo từng chương

Chương 1. Giới thiệu về Học máy

Chương này cung cấp bức tranh toàn cảnh về trí tuệ nhân tạo và các phân ngành của học máy. Tác giả hệ thống hóa 4 hướng tiếp cận lịch sử của AI (Hành động như người, Suy nghĩ như người, Suy nghĩ hợp lý, Hành động hợp lý), phân biệt rõ hai trường phái Supervised Learning và Unsupervised Learning.

Trọng tâm của chương tập trung phân tích 4 nhóm phương pháp phân cụm chính:

1. Dựa trên mật độ (Density-Based): DBSCAN, OPTICS.
2. Dựa trên phân cấp (Hierarchical-Based): CURE, BIRCH (tiếp cận kết tụ Agglomerative hoặc chia rẽ Divisive).
3. Dựa trên phân vùng (Partitioning): KMeans, CLARANS.
4. Dựa trên lưới (Grid-Based): STING, CLIQUE, WaveCluster.

Phần toán học của chương đi sâu phân tích thuật toán KMeans, độ phức tạp tính toán $O(K \cdot n \cdot d \cdot l)$ (với $l$ là số vòng lặp), các ưu nhược điểm cốt lõi và các biến thể mở rộng (Kmedians, Kmedoids, Fuzzy C-means). Tiếp theo, chương trình bày chi tiết thuật toán Logistic Regression, cấu trúc hàm Sigmoid, đường ranh giới quyết định (Decision Boundary tuyến tính và phi tuyến), thuật toán tối ưu hóa Gradient Descent, kỹ thuật One-vs-All cho phân lớp đa lớp, và kỹ thuật Regularization chống Overfitting.

Chương 2. Bài toán nhận diện chữ số viết tay với thuật toán phân cụm KMeans

Chương 2 mô tả quy trình chuyển đổi bài toán nhận dạng ảnh sang bài toán phân cụm không gian vector 400 chiều. Tác giả trình bày cấu trúc tập dữ liệu MNIST $5000 \times 400$, cách thức ánh xạ nhãn lớp, và quy trình áp dụng KMeans với số cụm ban đầu $K \ge 10$. Cơ chế lặp cập nhật trọng tâm dựa trên khoảng cách Euclidean được thiết lập với điều kiện dừng rõ ràng.

Chương cũng trình bày chi tiết quy trình đối chứng bằng mô hình Logistic Regression thông qua ma trận tham số $\Theta \in \mathbb{R}^{10 \times 401}$. Đồng thời, tác giả tổng thuật các công trình nghiên cứu tiền nhiệm liên quan:

• Michael P. Perrone và Scott D. Connell (2000): Ứng dụng KMeans kết hợp mô hình Markov ẩn (HMM) cho bài toán nhận dạng chữ viết tay với từ vựng 30.000 từ, đạt tỷ lệ lỗi 8%.
• Sajjad Pourmohammad và cộng sự (2013): Đề xuất hệ thống kết hợp biến đổi Affine, PCA, KMeans, LDA và phân loại Bayes trên tập MNIST, đạt tỷ lệ lỗi 3%.
• Rejean Plamondon và Sargur N. Srihari (2000): Nghiên cứu tổng quan về các phương pháp nhận dạng ký tự viết tay trực tuyến (online) và ngoại tuyến (offline).
• Hoàng Thị Ly Na (2019): Sử dụng Gradient Descent nhận dạng 5.000 mẫu MNIST với 500 vòng lặp, $\alpha = 3$, $\lambda = 0.01$, đạt độ chính xác 93%.
• Mai Phương Đông (2019): Ứng dụng thuật toán tối ưu hóa quasi-Newton BFGS trên dữ liệu chữ viết tay, đạt độ chính xác 93,84% trên chữ số và 76% trên chữ cái.

Chương 3. Thí nghiệm và kết quả

Chương 3 trình bày các kịch bản thực nghiệm trên phần mềm Octave với mã nguồn Kmeans_mnist.m. Tác giả cố định tham số số vòng lặp tối đa max_iters = 100 và thực hiện 7 lượt thử nghiệm độc lập tương ứng với các giá trị số lượng trọng tâm $K$ tăng dần: $K \in {10, 20, 50, 100, 150, 200, 250}$. Tác giả tích hợp module đo lường thời gian thực thi (timestamps) tại cửa sổ dòng lệnh (Command Window) để đánh giá tốc độ xử lý và sự hội tụ của thuật toán.

---

Kết quả và đóng góp

1. Kết quả thực nghiệm chính

Khóa luận ghi nhận kết quả thực nghiệm của thuật toán phân cụm KMeans khi thay đổi số lượng cụm $K$ và so sánh với mô hình học có giám sát:

Phương pháp / Mô hình	Tham số thiết lập	Số mẫu dữ liệu	Độ chính xác (%)
KMeans ($K = 10$)	max_iters = 100, $K = 10$	5.000 mẫu MNIST	58,14%
KMeans ($K = 20 \dots 250$)	max_iters = 100, tăng dần $K$	5.000 mẫu MNIST	Tăng dần theo số lượng $K$
Logistic Regression (One-vs-All)	$\Theta \in \mathbb{R}^{10 \times 401}$, Regularization	5.000 mẫu MNIST	Đạt độ chính xác cao đối chứng
Gradient Descent (Hoàng Thị Ly Na, 2019)	Vòng lặp = 500, $\alpha = 3, \lambda = 0.01$	5.000 mẫu MNIST	93,00%
Thuật toán BFGS (Mai Phương Đông, 2019)	Tối ưu hóa ma trận Hessian	5.000 mẫu MNIST	93,84% (chữ số), 76,00% (chữ cái)

Tại mức thiết lập cơ bản $K = 10$, thuật toán phân cụm KMeans chỉ đạt độ chính xác 58,14%. Tác giả giải thích nguyên nhân là do 10 trọng tâm là quá ít để bao quát được sự đa dạng về phong cách viết của 250 người khác nhau (ví dụ: các biến thể viết khác nhau của cùng chữ số 3, 4 hoặc 7). Khi tăng dần giá trị $K$ ($K = 20, 50, 100, 150, 200, 250$), độ chính xác nhận diện tăng lên rõ rệt.

2. Đóng góp của đề tài

• Làm rõ ranh giới hoạt động và hiệu năng thực tế giữa học có giám sát (Logistic Regression) và học không giám sát (KMeans) trên cùng bài toán nhận diện mẫu ảnh số hóa.
• Phân tích hiện tượng đánh đổi trong thuật toán KMeans: việc tăng số lượng cụm $K$ giúp tăng độ chính xác phân loại nhưng làm suy giảm bản chất gom nhóm tự nhiên ban đầu của thuật toán.
• Xây dựng hoàn chỉnh chương trình xử lý ma trận và thuật toán học máy trực tiếp trên môi trường mã nguồn mở GNU Octave mà không phụ thuộc vào các thư viện đóng gói sẵn.

---

Hạn chế và hướng nghiên cứu tiếp

1. Hạn chế

• Phụ thuộc vào khởi tạo trọng tâm: Khởi tạo ngẫu nhiên các trọng tâm $K$ ban đầu dẫn đến độ biến thiên kết quả giữa các lần chạy và có nguy cơ rơi vào điểm cực tiểu cục bộ.
• Sự đánh đổi tham số cụm: Thuật toán đòi hỏi số lượng $K$ lớn để cải thiện độ chính xác nhận diện chữ số, làm mờ nhạt ranh giới giữa phân cụm không giám sát và bài toán ghi nhớ dữ liệu.
• Độ nhạy của hàm khoảng cách: Khoảng cách Euclidean trong không gian 400 chiều nhạy cảm với nhiễu, điểm dị biệt và khó mô tả tốt các cụm dữ liệu phi tuyến tính hoặc không có dạng hình cầu.
• Giới hạn vòng lặp: Việc cố định max_iters = 100 có thể khiến thuật toán dừng trước khi hoàn toàn hội tụ ở các giá trị $K$ lớn.

2. Hướng phát triển

• Tích hợp các kỹ thuật tiền xử lý và giảm chiều không gian đặc trưng như phân tích thành phần chính (PCA) hoặc biến đổi Affine (xoay, co giãn nét chữ) nhằm giảm tải tính toán.
• Áp dụng các giải thuật khởi tạo trọng tâm tối ưu (như KMeans++) hoặc chuyển sang các mô hình kết hợp (Hybrid Models) để tăng tốc độ hội tụ.
• Mở rộng thử nghiệm trên toàn bộ 70.000 mẫu của bộ dữ liệu MNIST đầy đủ thay vì tập mẫu con 5.000 ảnh.

---

Giá trị tham khảo

Khóa luận là tài liệu tham khảo hữu ích cho sinh viên các ngành Hệ thống Thông tin Quản lý, Tin học Kinh tế, Khoa học Dữ liệu và Công nghệ Thông tin đang nghiên cứu nhập môn học máy.

Các nội dung có giá trị tham khảo chuyên sâu bao gồm:

• Quy trình biểu diễn, chuyển đổi dữ liệu ảnh ma trận $20 \times 20$ sang không gian vectơ 400 chiều để huấn luyện mô hình.
• Các bước chứng minh toán học và lập trình hàm chi phí lồi, kỹ thuật Regularization và cơ chế phân loại đa lớp One-vs-All.
• Cách thiết lập kịch bản thực nghiệm, đo thời gian chạy và đánh giá ảnh hưởng của tham số siêu cấu hình ($K$, số vòng lặp) trên công cụ GNU Octave/Matlab.

---

Câu hỏi thường gặp

1. Cấu trúc và kích thước của bộ dữ liệu MNIST được tác giả sử dụng trong khóa luận như thế nào?
Tác giả sử dụng tập dữ liệu gồm 5.000 mẫu chữ số viết tay từ 250 người viết khác nhau, chia đều 500 mẫu cho mỗi chữ số từ 0 đến 9. Mỗi mẫu là ảnh xám kích thước $20 \times 20$ pixel, được chuyển đổi thành vectơ $1 \times 400$, tạo thành ma trận đầu vào $X$ kích thước $5000 \times 400$ và vectơ nhãn $y$ kích thước $5000 \times 1$.

2. Tại sao ở thử nghiệm khởi tạo $K = 10$, thuật toán phân cụm KMeans chỉ đạt độ chính xác 58,14%?
Vì mỗi chữ số viết tay có nhiều biến thể hình học và nét viết khác nhau tùy thuộc vào người viết. Việc chỉ khởi tạo 10 trọng tâm ($K = 10$) là quá nhỏ so với độ biến thiên của 5.000 mẫu dữ liệu, khiến các mẫu của cùng một chữ số nhưng có kiểu viết khác nhau bị gán sai vào các cụm lân cận.

3. Làm thế nào Logistic Regression – một mô hình phân loại nhị phân – có thể nhận diện được 10 chữ số từ 0 đến 9?
Tác giả áp dụng chiến lược One-vs-All (một-với-tất-cả), chuyển bài toán 10 lớp thành 10 bài toán phân loại nhị phân độc lập. Quá trình huấn luyện sinh ra 10 vectơ trọng số $\theta^{(k)}$ ($k = 1 \dots 10$). Khi dự đoán mẫu mới, hàm giả thiết $h_\theta^{(k)}(x)$ nào cho xác suất cao nhất thì mẫu sẽ được gán cho nhãn tương ứng.

4. Kỹ thuật Regularization trong khóa luận giải quyết vấn đề gì của Logistic Regression?
Kỹ thuật Regularization giải quyết hiện tượng quá phù hợp (Overfitting). Bằng cách cộng thêm thành phần phạt $\frac{\lambda}{2m}\sum \theta_j^2$ vào hàm chi phí, mô hình thu nhỏ độ lớn của các hệ số trọng số $\theta$, giúp hàm quyết định không quá phức tạp và có khả năng tổng quát hóa tốt hơn trên dữ liệu mới.

5. Điểm khác biệt cơ bản giữa thuật toán KMeans và biến thể Kmedoids (PAM) được trình bày trong tài liệu là gì?
Trong KMeans, trọng tâm cụm được tính bằng trung bình cộng tọa độ các điểm trong cụm (không nhất thiết là một điểm dữ liệu có thật). Ngược lại, Kmedoids chọn chính một điểm dữ liệu thực tế thuộc tập đầu vào làm trung tâm cụm, giúp mô hình bền vững hơn và ít bị ảnh hưởng bởi dữ liệu nhiễu.

---

Kết luận

Khóa luận tốt nghiệp của sinh viên Ngô Trần Hoàng Lâm đã hệ thống hóa cơ sở lý thuyết toán học của phương pháp phân cụm không giám sát KMeans và mô hình phân lớp có giám sát Logistic Regression. Thông qua việc tự xây dựng chương trình thử nghiệm trên môi trường GNU Octave với 5.000 mẫu chữ số viết tay MNIST, tác giả đã chứng minh mối liên hệ thực nghiệm giữa số lượng trọng tâm $K$ và độ chính xác nhận dạng, đạt 58,14% tại $K=10$ và tăng dần theo các mức phân cụm cao hơn. Đề tài cung cấp tài liệu tham khảo chi tiết về phương pháp biểu diễn dữ liệu ảnh, kỹ thuật lập trình ma trận và đánh giá hiệu năng giải thuật học máy ứng dụng.

Trích đoạn nội dung tài liệu

CHƯƠNG 1. Giới thiệu về Học máy Mỗi con người chúng ta được trang bị các giác quan như thị giác, thính giác, xúc giác,… để quan sát, cảm nhận, nhận thức mọi thứ xung quanh rồi từ đó mỗi cá nhân từng người sẽ tự mình rút ra được những kinh nghiệm, đánh giá, phân tích riêng để đối phó, xử lí khi gặp lại các trường hợp đó trong cuộc sống. Máy tính cũng cũng vậy, muốn nó nhận thức, xử lí được như con người thì ta cần phải trang bị cho nó những thứ cần thiết, những thứ được xem như giác quan của máy tính như máy quay, tai nghe,… Từ đó, máy tính có thể thay thế con người để làm những việc phức tạp, thậm chí nó còn làm nhanh hơn và chính xác hơn. Ví dụ như hãy lọc ra những người giống nhau ở trong hai đoạn băng ghi hình ở hai nơi khác nhau kéo dài 12 tiếng để tìm ra những đối tượng bị tình nghi là thuộc một băng nhóm nào đó, hay là lọc ra âm thanh của cuộc trò chuyện điện thoại trong một buổi tiệc ồn ào,.

Những công việc dạng như vậy khi được chúng ta huấn luyện cho máy tính thì được gọi là tác vụ. Máy tính được trang bị một hay nhiều các tác vụ như trên để làm những công việc đó thay cho con người được gọi là AI (Trí tuệ nhân tạo). AI [1] là viết tắt của Artificial Intelligence, dịch ra là trí tuệ nhân tạo. Trong lịch sử phát triển thì trí tuệ nhân tạo được các nhà nghiên cứu phân thành 4 hướng tiếp cận chính đó là: - Hàng động như người (Acting humanly) - Suy nghĩ như người (Thinking humanly) - Suy nghĩ hợp lý (Thinking rationally) - Hành động hợp lý (Acting rationally) Trong thời đại phát triển chóng mặt của công nghệ số hiện nay, trí tuệ nhân tạo đang mang lại sự thay đổi sâu sắc về nhiều khía cạnh của cuộc sống, nó len lõi và hỗ trợ một cách tối đa cho các hoạt động của con người như kinh doanh, bảo mật, y tế,… Có thể kể ra một vài hệ thống trí tuệ nhân tạo tiêu biểu như máy chơi cờ vây tự động Google AlphaGo của Google DeepMind; các trợ lý ảo như Siri của Apple,Google Assistant của Google, Bixby của Samsung; nhà thông minh có khả năng học hỏi và ghi SV: Ngô Trần Hoàng Lâm 5 Khóa luận tốt nghiệp nhớ người dùng qua lệnh giọng nói, hành vi, thói quen,… của ACIS JSC; hệ thống nhận diện khuôn mặt trong ảnh đăng của người dùng lên Facebook, FaceID của Apple; hệ thống gợi ý sản phẩm cho khách hàng dựa trên lịch sử mua hàng, sở thích, thói quen của khách hàng của Amazon; thiết bị bay không người lái được ứng dụng vào y tế để tăng thời gian và có thể đến nơi có địa hình hiểm trở;…đây là một vài hệ thống trong vô vàn hệ thống có ứng dụng trí tuệ nhân tạo.

Trí tuệ nhân tạo thực sự mang lại cho con người chúng ta một cuộc sống tiện nghi, hiện đại và chất lượng hơn rất nhiều, khiến con người cảm thấy thoải mái hơn và bên cạnh đó, việc áp dụng thêm các tiến bộ khoa học kĩ thuật khác càng làm cho năng suất công việc được nâng cao, chất lượng sản phẩm được cải thiện từ đó dẫn đến một xã hội tiến bộ và cuộc sống chất lượng hơn. Để có được trí tuệ nhân tạo thì máy tính cần phải “học tập”, vậy máy tính sẽ “học tập” như thế nào? Một trong những lĩnh vực con bên trong AI rất quan trọng và có liên quan đến việc phát triển các kỹ thuật cho phép máy tính có thể “học tập” đó là Học máy (Machine Learning - ML) [2]. Học máy là một trong những công cụ có thể giúp máy tính có thể “tự học hỏi” và nâng cao khả năng nhận biết về thế giới xung quanh dựa vào các dữ liệu đã thu thập được từ trước đó. Học máy giúp giải quyết bài toán bằng cách sử dụng một lượng lớn dữ liệu sẵn có từ trước, sau quá trình được “học tập” thì máy tính có thể có khả năng tự động thực hiện những tác vụ khác nhau để giải quyết bài toán đó, thay cho các phương pháp lập trình truyền thống.

Cụ thể ở đây, máy tính có thể thực hiện các tác vụ đó thông qua việc phân tích dữ liệu, cập nhật và xử lý bộ dữ liệu có sẵn và sau đó khi gặp các trường hợp mới phát sinh thì nó có thể tự động ghi nhận lại và tự động xử lý với độ chính xác tương đối cao. Các thuật toán học máy được chia thành 2 loại thường dùng đó là: - Học có giám sát (Supervised Learning): máy tính được huấn luyện bằng một số mẫu đầu vào và đầu ra tương ứng đã được biết trước kết quả. Sau khi được huấn luyện, máy tính quan sát khi có đầu vào mới và có thể tự động tính ra kết quả cho đầu ra. Trong học có giám sát thì được phân thành 2 loại đó là hồi quy (Regression) và phân lớp (Classification).

SV: Ngô Trần Hoàng Lâm 6 Khóa luận tốt nghiệp Một vài giải thuật phổ biến trong học có giám sát:  Hồi quy: hồi quy tuyến tính (Linear Regression), hồi quy Logistic (Logistic Regression), rừng ngẫu nhiên (Random Forest).  Phân lớp: rừng ngẫu nhiên (Random Forest), vectơ hỗ trợ (Support Vector) - Học không giám sát (Unsupervised Learning): máy tính không được cho đầu ra mà chỉ có dự liệu đầu vào. Sau đó máy tính phải tự tìm cách phân lớp các mẫu này và các mẫu mới. Trong học không giám sát thì được chia thành 2 loại đó là phân cụm (Clustering) và không phân cụm (Non-Clustering) Một vài giải thuật phổ biến trong học không giám sát:  Phân cụm: Kmeans  Không phân cụm: Cocktail Party Algorithm Khoảng 2 thập kỷ trở lại đây thì học máy mới thực sự gây ra cơn sốt trong giới công nghệ trên toàn cầu, còn trước đó do khả năng tính toán của vi xử lý còn yếu và lưu lượng dữ liệu số lưu trữ trên các máy chủ trên khắp thế giới chưa được nhiều nên việc sự dụng học máy rất hạn chế.

Hiện nay, với khả năng xử lý của đơn vị xử lý trung tâm (CPU) đã đạt đến tầm cao mới theo cấp số nhân (Định luật Moore) và kho dữ liệu số lưu trữ trên các máy chủ ngày càng được tích lũy nhiều hơn thì học máy thực sự là một cơn bão trong giới công nghệ. Nó có tính ứng dụng rất cao trong nhiều lĩnh vực như hô biến ảnh đen trắng thành ảnh màu, phát hiện thẻ tín dụng giả, tự động tạo chú thích cho các bức ảnh, viết truyện – làm thơ – viết quảng cáo, dịch máy, phân lớp các chuỗi DNA,… Những ứng dụng này phần nào đã chứng tỏ sự vượt trội của học máy so với các phương pháp cổ điển khác và cho thấy sự cần thiết của học máy đối với cuộc sống của chúng ta hiện nay. Vì việc nghiên cứu và ứng dụng học máy còn chưa phổ biến ở Việt Nam nên các thuật ngữ dịch sang tiếng Việt còn chưa được thống nhất và chưa có một chuẩn mực chung cho mọi tài liệu. Do đó trong khóa luận này, người thực hiện khóa luận xin được dùng thuật ngữ tiếng Anh gốc để giữ được nghĩa gốc vốn có của các thuật ngữ.

Bảng các thuật ngữ tiếng Anh được dùng trong khóa luận được cung cấp ở trang viii. SV: Ngô Trần Hoàng Lâm 7 Khóa luận tốt nghiệp 1. Tổng quan về học không giám sát Như đã giới thiệu ở trên thì trong ngành khoa học dữ liệu có 2 hướng để sử dụng dữ liệu đó là học có giám sát và học không giám sát. Sử dụng dữ liệu để huấn luyện mô hình và tạo ra các dự đoán với dữ liệu mới đó là học có giám sát.

Nhưng đôi khi ta không muốn tạo ra các dự đoán mà lại muốn tìm ra những điểm tương đồng trong bộ dữ liệu đó và phân dữ liệu và các nhóm khác nhau đó lại là học không giám sát. Đó cũng là ưu điểm của nó so với học có giám sát vì trong cuộc sống không phải lúc nào chúng ta cũng có được kết quả đầu ra cho tất cả các bộ dữ liệu. Vì khóa luận này đang nói về phương pháp phân cụm Kmeans mà phương pháp này thuộc về học không có giám sát nên người thực hiện khóa luận sẽ trình bày phần học không giám sát trước, còn về phần học có giám sát thì chúng ta sẽ cần đến nó nhưng sẽ đề cập đến nó ở phần tiếp sau của khóa luận. Học không giám sát [3], [4] là phương pháp học mà máy tính học không có hướng dẫn cụ thể, không có các ví dụ cho trước, không có đầu ra mà chỉ có bộ dữ liệu đầu vào, sau đó nó sẽ tự động tìm các điểm tương đồng, sự khác biệt của dữ liệu và nhóm dữ liệu thành từng cụm khác nhau dựa vào độ tương đồng giữa chúng.

Chúng ta có một ví dụ như sau: máy tính chưa từng nhìn qua bức ảnh dưới đây và cũng chưa được dạy cho nó về như thế nào là chó và như thế nào là mèo. Hình minh họa cho ví dụ của phương pháp học không giám sát Do chưa được dạy nên máy tính của chúng ta sẽ không thể phân biệt được con nào là chó và con nào là mèo trong bức ảnh. Nhưng vì là học không giám sát nên khi nhìn thấy bức ảnh, máy tính có thể phân cụm bức ảnh này ra dựa vào các điểm tương đồng của các SV: Ngô Trần Hoàng Lâm 8 Khóa luận tốt nghiệp con vật trong bức ảnh. Để rồi nó có thể phân bức ảnh thành vùng chỉ có những con chó và vùng chỉ có hình ảnh những con mèo dựa vào điểm tương đồng giữa các con vật.

Trong học không giám sát thì các thuật toán phổ biến nhất được sử dụng bao gồm: - Phân cụm  Phân cấp (Hierarchical Clustering)  Phân cụm k (Kmeans)  Mô hình hỗn hợp (Mixture models)  Phân cụm không gian dựa trên các ứng dụng có tiếng ồn (DBSCAN)  Thuật toán xác định cấu trúc phân cụm dựa trên thứ tự điểm (OPTICS algorithm) - Phát hiện bất thường (Anomaly detection)  Yếu tố ngoại lệ địa phương (Local Outlier Factor) - Mạng lưới thần kinh (Neural network)  Bộ tự động (Autoencoders)  Lưới niềm tin sâu sắc (Deep Belies Nets)  Học tiếng Do Thái (Hebbian Learning) - Mô hình biến tiềm ẩn (Latent variable models)  Thuật toán tối đa hóa kì vọng (Expectation – maximization algorithm) (EM)  Phương pháp của khoảnh khắc (Method of moment)  Tách tín hiệu mù (Blind signal separation) 1. Tổng quan về phân cụm 1.