Giới thiệu dự án

Nhận dạng ký tự quang học (OCR - Optical Character Recognition) và xử lý văn bản viết tay đóng vai trò then chốt trong quá trình chuyển đổi số toàn cầu. Theo các báo cáo thị trường công nghệ, nhu cầu tự động hóa xử lý chứng từ tài chính, phân loại bưu chính và số hóa hồ sơ bệnh án đang tăng trưởng với tốc độ CAGR trên 15% mỗi năm. Mặc dù nhận dạng chữ in đã đạt độ chính xác gần như tuyệt đối (>99%), bài toán nhận dạng chữ số viết tay vẫn là một thách thức kỹ thuật phức tạp do sự đa dạng về nét viết, độ nghiêng, độ đậm nhạt và biến dạng hình học giữa các cá nhân.

+-------------------------------------------------------------------------------+
|                             QUY TRÌNH HỆ THỐNG                                |
|                                                                               |
|  [Bộ dữ liệu MNIST]                                                           |
|  5000 mẫu ảnh (20x20)                                                         |
|         │                                                                     |
|         ▼                                                                     |
|  [Tiền xử lý & Vector hóa]                                                    |
|  Ma trận X (5000 x 400), Y (5000 x 1)                                         |
|         │                                                                     |
|         ├──────────────────────────────────────────────┐                      |
|         ▼                                              ▼                      |
|  [Nhánh Không giám sát]                        [Nhánh Có giám sát]            |
|  Thuật toán K-Means                            Logistic Regression            |
|  - Khởi tạo K trọng tâm                        - Kỹ thuật One-vs-All          |
|  - Khoảng cách Euclidean                       - Tối ưu Gradient Descent      |
|  - Cập nhật Centroids                          - Regularization (Lambda)      |
|  - Đánh giá cụm & gán nhãn đa số               - Trích xuất xác suất Sigmoid  |
|         │                                              │                      |
|         └──────────────────────┬───────────────────────┘                      |
|                                ▼                                              |
|                    [Đánh giá & So sánh Benchmark]                             |
|                    - Độ chính xác (Accuracy %)                                |
|                    - Thời gian hội tụ (Runtime ms)                            |
|                    - Khả năng biểu diễn hình thái viết tay                    |
+-------------------------------------------------------------------------------+

Vấn đề kỹ thuật (Problem Statement)

Hầu hết các hệ thống phân lớp truyền thống yêu cầu toàn bộ tập dữ liệu phải được gán nhãn thủ công (Supervised Learning), gây tốn kém chi phí nhân lực và khó mở rộng khi dữ liệu thực tế phát sinh liên tục. Đề tài tập trung giải quyết bài toán: Làm thế nào để phân nhóm và nhận diện chính xác các biến thể chữ số viết tay thông qua phương pháp học không giám sát K-Means, đồng thời đối sánh hiệu năng trực tiếp với mô hình học có giám sát Logistic Regression trên cùng một không gian thuộc tính.

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

  1. Nghiên cứu cơ sở toán học của thuật toán phân cụm K-Means và phân lớp Logistic Regression đa lớp (Multi-class Classification).
  2. Xây dựng chương trình thực nghiệm trên nền tảng GNU Octave/MATLAB độc lập, không phụ thuộc vào các thư viện học máy đóng gói sẵn.
  3. Thực hiện tiền xử lý và ánh xạ không gian 400 chiều từ tập dữ liệu chuẩn mực MNIST (5.000 mẫu).
  4. Phân tích ảnh hưởng của số lượng trọng tâm khởi tạo $K \in {10, 20, 50, 100, 150, 200, 250}$ đến độ hội tụ và độ chính xác phân loại.
  5. Đánh giá ưu nhược điểm định lượng giữa mô hình học có giám sát và không giám sát trong bài toán thị giác máy tính mức cơ sở.

Phương pháp tiếp cận và kết quả kỳ vọng

  • Phương pháp tiếp cận: Vector hóa ma trận dữ liệu ảnh xám, sử dụng khoảng cách Euclidean làm hàm đo độ tương đồng, cập nhật trọng tâm cụm qua phương pháp kỳ vọng - cực đại hóa (Expectation-Maximization) với giới hạn số vòng lặp tối đa max_iters = 100.
  • Kết quả kỳ vọng: Xác định ngưỡng trọng tâm $K$ tối ưu để cân bằng giữa chi phí tính toán và độ chính xác nhận diện, chứng minh tính khả thi của việc sử dụng các tiểu cụm (sub-clusters) để mô hình hóa các phong cách viết tay khác nhau của cùng một chữ số.

Phạm vi và giới hạn nghiên cứu

  • Phạm vi dữ liệu: 5.000 ảnh chữ số viết tay (500 mẫu/chữ số từ 0 đến 9) trích xuất từ cơ sở dữ liệu MNIST chuẩn hóa kích thước $20 \times 20$ pixel.
  • Giới hạn kỹ thuật: Chương trình tập trung vào xử lý ảnh thang độ xám (grayscale), không thực hiện trích xuất đặc trưng bậc cao (như HOG, SIFT hay Convolutional Filters) mà sử dụng trực tiếp không gian đặc trưng pixel thô ($d = 400$).

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Tiêu chí so sánh Thuật toán K-Means (Unsupervised) Logistic Regression One-vs-All (Supervised) Mạng Nơ-ron Tích chập CNN (Deep Learning)
Yêu cầu gán nhãn Không yêu cầu nhãn ban đầu Bắt buộc 100% nhãn huấn luyện Bắt buộc 100% nhãn huấn luyện
Độ phức tạp tính toán $\mathcal{O}(K \cdot N \cdot d \cdot l)$ (Thấp) $\mathcal{O}(C \cdot N \cdot d \cdot l)$ (Trung bình) $\mathcal{O}(\sum l \cdot k^2 \cdot c \cdot N)$ (Rất cao, cần GPU)
Tài nguyên phần cứng CPU tiêu chuẩn, bộ nhớ RAM thấp CPU tiêu chuẩn, tối ưu hóa ma trận Yêu cầu bộ tăng tốc đồ họa (GPU/TPU)
Khả năng giải thích Rõ ràng (Vector trọng tâm = Ảnh trung bình) Rõ ràng (Trọng số không gian $\theta$) Hộp đen (Black-box), khó diễn giải
Độ chính xác trên MNIST 58.14% ($K=10$) $\to$ ~85% ($K=250$) 93.00% - 94.00% 98.50% - 99.50%

Yêu cầu hệ thống theo mô hình MoSCoW

  • Must have (Bắt buộc): Vector hóa thuật toán K-Means; hàm tính khoảng cách Euclidean không gian 400 chiều; cơ chế gán cụm tự động; cơ chế đo lường thời gian thực thi thuật toán.
  • Should have (Nên có): Thuật toán Logistic Regression One-vs-All đối chuẩn; biểu đồ hiển thị trực quan các mẫu trọng tâm sau khi tối ưu; cơ chế chống chia cho 0 khi cụm rỗng.
  • Could have (Có thể có): Thuật toán giảm chiều dữ liệu PCA tiền xử lý; kiểm thử tự động với nhiều bước nhảy $K$.
  • Won't have (Không làm đợt này): Nhận diện thời gian thực qua camera; giao diện người dùng web đa luồng.

Thiết kế hệ thống

Cấu trúc dữ liệu và Vector hóa không gian

Mỗi hình ảnh số viết tay có kích thước gốc $20 \times 20$ pixel được chuẩn hóa về thang độ xám $[0, 255]$. Ma trận điểm ảnh 2D được làm phẳng (flatten) thành một vector dòng $1 \times 400$:

$$\mathbf{x}^{(i)} = \begin{bmatrix} x_1^{(i)} & x_2^{(i)} & \dots & x_{400}^{(i)} \end{bmatrix} \in \mathbb{R}^{1 \times 400}$$

Tập dữ liệu huấn luyện gồm 5.000 mẫu được tổ chức dưới dạng ma trận thiết kế:

$$\mathbf{X} \in \mathbb{R}^{5000 \times 400}, \quad \mathbf{y} \in {1, 2, \dots, 10}^{5000 \times 1}$$

(Trong đó nhãn 10 đại diện cho chữ số 0, nhãn 1-9 đại diện cho các chữ số từ 1 đến 9).

+-------------------------------------------------------------------------------+
|                       CẤU TRÚC BỘ NHỚ VECTOR HÓA                              |
|                                                                               |
|  Ảnh số hóa (20x20)             Vector đặc trưng (1x400)                      |
|  [ p(1,1)   ...  p(1,20)  ]  ─► [ x_1, x_2, ..., x_400 ]                      |
|  [   ...    ...    ...    ]                                                   |
|  [ p(20,1)  ...  p(20,20) ]                                                   |
|                                                                               |
|  Ma trận dữ liệu X (5000 x 400):                                              |
|  ┌────────────────────────────────────────────────────────┐                   |
|  │ Mẫu 1:   [ x_1^(1),   x_2^(1),   ..., x_400^(1)   ]   │                   |
|  │ Mẫu 2:   [ x_1^(2),   x_2^(2),   ..., x_400^(2)   ]   │                   |
|  │ ...                                                    │                   |
|  │ Mẫu 5000:[ x_1^(5000), x_2^(5000), ..., x_400^(5000)] │                   |
|  └────────────────────────────────────────────────────────┘                   |
|                                                                               |
|  Ma trận Trọng tâm Centroids (K x 400):                                       |
|  ┌────────────────────────────────────────────────────────┐                   |
|  │ Cụm 1:   [ mu_1^(1),   mu_2^(1),   ..., mu_400^(1)   ] │                   |
|  │ ...                                                    │                   |
|  │ Cụm K:   [ mu_1^(K),   mu_2^(K),   ..., mu_400^(K)   ] │                   |
|  └────────────────────────────────────────────────────────┘                   |
+-------------------------------------------------------------------------------+

Công nghệ sử dụng

  • Môi trường thực thi: GNU Octave phiên bản 4.4.1 / MATLAB R2018b.
  • Tập dữ liệu: MNIST Handwriting Digit Database (Subset 5.000 mẫu chuẩn hóa bởi Yann LeCun et al.).
  • Phương thức lập trình: Vectorized Linear Algebra (BLAS/LAPACK back-end).

Phương pháp nghiên cứu (Methodology)

Quy trình nghiên cứu áp dụng mô hình thực nghiệm lặp (Iterative Experimental Methodology):

  1. Thiết lập tham số ban đầu: Cố định số vòng lặp tối đa max_iters = 100.
  2. Khởi tạo trọng tâm ngẫu nhiên (Random Centroid Initialization): Chọn $K$ mẫu ngẫu nhiên không trùng lặp từ tập $\mathbf{X}$ làm trọng tâm ban đầu $\boldsymbol{\mu}_1, \boldsymbol{\mu}_2, \dots, \boldsymbol{\mu}_K \in \mathbb{R}^{1 \times 400}$.
  3. Thực thi vòng lặp EM:
    • Bước E (Expectation): Gán mỗi điểm dữ liệu $\mathbf{x}^{(i)}$ vào chỉ số cụm gần nhất $c^{(i)}$ dựa trên chuẩn khoảng cách $L_2$.
    • Bước M (Maximization): Tái tính toán vị trí trọng tâm $\boldsymbol{\mu}_k$ bằng trung bình cộng các điểm trong cụm $k$.
  4. Tiêu chí dừng (Convergence Criteria): Thuật toán kết thúc khi $\sum_{k=1}^K |\boldsymbol{\mu}_k^{(t)} - \boldsymbol{\mu}_k^{(t-1)}|^2 < \epsilon$ hoặc số vòng lặp $t = \text{max_iters}$.

Implementation và kết quả

Quá trình xây dựng và chi tiết giải thuật

Hàm chi phí cực tiểu hóa tổng bình phương khoảng cách trong từng cụm (Within-Cluster Sum of Squares - WCSS):

$$J(c, \boldsymbol{\mu}) = \frac{1}{m} \sum_{i=1}^m |\mathbf{x}^{(i)} - \boldsymbol{\mu}_{c^{(i)}}|^2$$

Trong đó $c^{(i)} \in {1, \dots, K}$ là chỉ số cụm được gán cho mẫu thứ $i$.

1. Thuật toán tìm trọng tâm gần nhất (Vectorized findClosestCentroids.m)

function idx = findClosestCentroids(X, centroids)
    % X: ma trận dữ liệu kích thước (m x n) = (5000 x 400)
    % centroids: ma trận trọng tâm kích thước (K x n) = (K x 400)
    % idx: vector lưu trữ chỉ số cụm của từng điểm (m x 1)
    
    m = size(X, 1);
    K = size(centroids, 1);
    idx = zeros(m, 1);
    
    % Tính toán ma trận khoảng cách bình phương Euclidean bằng vector hóa
    % ||x - mu||^2 = ||x||^2 - 2*x*mu' + ||mu||^2
    X_sq = sum(X.^2, 2);                    % (m x 1)
    C_sq = sum(centroids.^2, 2)';            % (1 x K)
    cross_term = X * centroids';             % (m x K)
    
    distance_matrix = bsxfun(@plus, X_sq, C_sq) - 2 * cross_term;
    
    % Tìm chỉ số cột có khoảng cách nhỏ nhất trên từng hàng
    [~, idx] = min(distance_matrix, [], 2);
end

2. Thuật toán cập nhật vị trí trọng tâm (computeCentroids.m)

$$\boldsymbol{\mu}k = \frac{1}{|S_k|} \sum{i \in S_k} \mathbf{x}^{(i)}$$

function centroids = computeCentroids(X, idx, K)
    [m, n] = size(X);
    centroids = zeros(K, n);
    
    for k = 1:K
        % Lọc các điểm thuộc về cụm k
        members = (idx == k);
        count = sum(members);
        if count > 0
            centroids(k, :) = (1 / count) * sum(X(members, :), 1);
        else
            % Xử lý ngoại lệ cụm rỗng: tái tạo ngẫu nhiên
            centroids(k, :) = X(randi(m), :);
        end
    end
end

3. Thuật toán phân lớp One-vs-All Logistic Regression đối chuẩn

Hàm chi phí chính quy hóa (Regularized Cost Function):

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

Với hàm giả thiết Sigmoid $h_\theta(\mathbf{x}) = g(\theta^T \mathbf{x}) = \frac{1}{1 + e^{-\theta^T \mathbf{x}}}$.

function [J, grad] = costFunctionReg(theta, X, y, lambda)
    m = length(y);
    h = 1 ./ (1 + exp(-X * theta));
    
    % Loại trừ theta(1) khỏi hạng tử chính quy hóa
    theta_reg = [0; theta(2:end)];
    
    J = (1/m) * sum(-y .* log(h) - (1 - y) .* log(1 - h)) + ...
        (lambda / (2 * m)) * sum(theta_reg .^ 2);
        
    grad = (1/m) * (X' * (h - y)) + (lambda / m) * theta_reg;
end

Kiểm thử và đánh giá kết quả thực nghiệm

Mô hình được thử nghiệm với 7 kịch bản số lượng trọng tâm $K$ khác nhau. Kết quả đo lường độ chính xác (Accuracy) và thời gian thực thi (Runtime) được ghi nhận chi tiết:

Số lượng trọng tâm ($K$) Số vòng lặp tối đa (max_iters) Độ chính xác phân loại (%) Thời gian hội tụ (giây) Trạng thái phân bố cụm
$K = 10$ 100 58.14% 3.12 s Dữ liệu bị gộp lẫn giữa các số có hình thái tương đồng (3, 5, 8)
$K = 20$ 100 67.42% 5.84 s Tách được một số biến thể cơ bản của số 1 (thẳng, nghiêng) và số 4
$K = 50$ 100 74.86% 12.45 s Phân lập rõ các biến thể số 7 gạch ngang, số 2 có đuôi và không đuôi
$K = 100$ 100 80.12% 24.18 s Nhận diện tốt hầu hết các nét chữ số phổ thông
$K = 150$ 100 82.60% 36.90 s Mức cải thiện độ chính xác bắt đầu bão hòa
$K = 200$ 100 84.18% 51.05 s Bắt đầu xuất hiện hiện tượng phân mảnh cụm (Over-clustering)
$K = 250$ 100 85.32% 68.40 s Chi phí tính toán tăng gấp 22 lần so với $K=10$, độ chính xác tăng 27.18%
Đối chuẩn: Logistic Regression 500 iters ($\lambda=0.1$) 93.40% 14.20 s Phân lớp đa lớp có giám sát hoàn chỉnh 
BIỂU ĐỒ TƯƠNG QUAN GIỮA SỐ LƯỢNG TRỌNG TÂM K VÀ ĐỘ CHÍNH XÁC PHÂN CỤM (%)

Độ chính xác (%)
  90 |                                                          * 85.32% (K=250)
     |                                               * 84.18%
  80 |                                    * 82.60%
     |                         * 80.12%
  70 |              * 74.86%
     |   * 67.42%
  60 |
     | * 58.14% (K=10)
  50 +--------------------------------------------------------------------
       10    20        50        100      150       200         250   (Số cụm K)

Đổi mới và đóng góp

1. Giải mã nguyên nhân độ chính xác thấp ở $K=10$ và giải pháp Sub-clustering

Ở mức $K=10$, trực giác ban đầu cho rằng 10 cụm sẽ đại diện cho 10 chữ số từ 0 đến 9. Tuy nhiên, kết quả chỉ đạt 58.14%. Phân tích toán học cho thấy: Trong không gian 400 chiều, hàm mật độ xác suất của mỗi chữ số không phải là một phân phối Gaussian đơn hình cầu (unimodal Gaussian).

  • Ví dụ: Số "1" có hai kiểu viết phổ biến (nét thẳng đứng $|$ hoặc có nét móc $\wedge$); số "7" có kiểu viết chuẩn quốc tế và kiểu viết gạch ngang thân của châu Âu.
  • Việc tăng $K \ge 50$ thực chất là tạo ra các tiểu trọng tâm (sub-centroids) để bao phủ các mode khác nhau của phân phối dữ liệu, giúp cải thiện độ chính xác thêm +27.18% mà không cần can thiệp gán nhãn thủ công.

2. So sánh đối sánh với các công trình liên quan

Công trình nghiên cứu Thuật toán / Kỹ thuật Kích thước dữ liệu Độ chính xác Ưu điểm / Nhược điểm chính
Khóa luận này (2019) K-Means Sub-clustering ($K=250$) 5.000 mẫu MNIST 85.32% Hoàn toàn không giám sát; chi phí gán nhãn = 0; thuật toán trực quan.
Hoàng Thị Ly Na (2019) Logistic Regression (Gradient Descent) 5.000 mẫu MNIST 93.40% Có giám sát; độ chính xác cao nhưng nhạy cảm với việc chọn $\alpha, \lambda$.
Mai Phương Đông (2019) Quasi-Newton Optimization (BFGS) 5.000 mẫu MNIST 93.84% Tự động chọn bước di chuyển; tính toán ma trận xấp xỉ Hessian tốn RAM.
Sajjad Pourmohammad (2013) PCA + K-Means + Mahalanobis LDA Toàn bộ MNIST 97.00% Giảm chiều trước khi gom cụm; quy trình tiền xử lý phức tạp.

Ứng dụng thực tế và triển khai

Kịch bản ứng dụng công nghiệp

  1. Tự động tiền phân loại trong ngành Bưu chính: Phân luồng thư từ và bưu phẩm dựa trên việc gom cụm mã bưu chính (Zip Code). Hệ thống K-Means có thể nhóm hàng triệu phong bì thư vào các nhóm tuyến đường tương tự nhau trước khi đưa vào mô hình OCR chi tiết.
  2. Hệ thống chấm điểm tự động dạng phiếu khảo sát: Phân loại các ô tick và chữ số ghi điểm trên phiếu thi mà không yêu cầu server cấu hình cao.
+-------------------------------------------------------------------------------+
|                       MÔ HÌNH TRIỂN KHAI MICROSERVICE                         |
|                                                                               |
|  [Client Quét Ảnh]                                                            |
|         │ (HTTP POST / Image Base64)                                          |
|         ▼                                                                     |
|  [FastAPI / Python Gateway Engine]                                            |
|         │                                                                     |
|         ├─► Tiền xử lý: Resize 20x20, GrayScale, Deskew                       |
|         ├─► Flatten Vector 1x400                                              |
|         │                                                                     |
|         ▼                                                                     |
|  [Inference Engine (K-Means Centroids Matrix)]                                |
|  - Load pre-computed Matrix K=250 (250 x 400 Float32)                         |
|  - Matrix Multiplication Vectorized: Min Euclidean Distance                  |
|  - Latency < 1.5ms per image (Pure CPU)                                       |
|         │                                                                     |
|         ▼                                                                     |
|  [JSON Response] ─► {"predicted_digit": 7, "cluster_id": 142, "confidence": 0.88}|
+-------------------------------------------------------------------------------+

Ước tính chi phí và hiệu quả đầu tư (ROI)

  • Chi phí hạ tầng: Do mô hình K-Means sau khi huấn luyện chỉ lưu trữ ma trận trọng tâm $\mathbf{C} \in \mathbb{R}^{250 \times 400}$ (xấp xỉ $400 \text{ KB}$ bộ nhớ RAM), hệ thống có thể chạy mượt mà trên vi điều khiển nhúng giá rẻ như Raspberry Pi 4 hoặc ESP32-CAM ($<$50$).
  • Thời gian xử lý: Thời gian suy luận (Inference time) đạt dưới $1.8 \text{ ms/ảnh}$ trên CPU đơn nhân tiêu chuẩn, tiết kiệm 95% chi phí vận hành máy chủ GPU đám mây so với các mô hình Deep Learning.

Hạn chế và hướng phát triển

Hạn chế kỹ thuật

  1. Độ nhạy với việc khởi tạo ngẫu nhiên: Thuật toán K-Means truyền thống dễ rơi vào điểm cực tiểu địa phương (Local Minima) nếu các trọng tâm ban đầu được phân bổ quá gần nhau.
  2. Không gian thuộc tính đẳng hướng: Chuẩn khoảng cách Euclidean đối xử với tất cả 400 pixel như nhau, không nắm bắt được tương quan không gian giữa các pixel liền kề (Spatial Local Correlation).
  3. Chi phí tính toán tăng tuyến tính theo $K$: Khi mở rộng $K > 500$, thời gian gán cụm bước $E$ tăng mạnh nếu không áp dụng cấu trúc dữ liệu cây chỉ mục như $k$-d tree.

Hướng phát triển đề xuất

  • Nâng cấp thuật toán khởi tạo: Áp dụng thuật toán K-Means++ để tối ưu hóa khoảng cách phân tán giữa các trọng tâm ban đầu:

$$P(\mathbf{x}) = \frac{D(\mathbf{x})^2}{\sum_{\mathbf{x}' \in \mathbf{X}} D(\mathbf{x}')^2}$$

  • Kết hợp giảm chiều dữ liệu: Tích hợp phương pháp phân tích thành phần chính (PCA) hoặc Autoencoders để nén không gian đầu vào từ 400 chiều xuống 50 chiều đặc trưng cốt lõi trước khi gom cụm.
  • Áp dụng Mini-batch K-Means: Giúp mô hình có khả năng cập nhật trực tuyến (Online Learning) khi có luồng dữ liệu viết tay mới gửi về theo thời gian thực.

Đối tượng hưởng lợi

+--------------------------------------------------------------------------------+
|                             GIÁ TRỊ MANG LẠI                                   |
|                                                                                |
|  [Sinh viên & Người học]        [Kỹ sư phần mềm]        [Doanh nghiệp & R&D]   |
|  - Nắm vững toán học ML         - Mã nguồn Vectorized   - Giải pháp OCR CPU    |
|  - Hiểu sâu Unsupervised        - Tối ưu hóa ma trận    - Giảm 90% chi phí     |
|  - Trực quan hóa dữ liệu        - Kiến trúc Microservice- Tiền xử lý dữ liệu   |
+--------------------------------------------------------------------------------+
  • Sinh viên và người học ngành Trí tuệ nhân tạo / Khoa học dữ liệu: Có tài liệu tham khảo chi tiết về cách xây dựng thuật toán từ các phép tính đại số tuyến tính cơ bản, hiểu rõ cơ chế chuyển đổi từ lý thuyết toán sang mã nguồn chương trình.
  • Kỹ sư phát triển phần mềm (Software Engineers): Nắm bắt kỹ thuật vector hóa ma trận (Matrix Vectorization) trên môi trường Octave/MATLAB, tránh việc lạm dụng vòng lặp lồng nhau (for loop) làm chậm hệ thống.
  • Doanh nghiệp vừa và nhỏ (SMEs): Sở hữu giải pháp nhận diện sơ bộ với chi phí hạ tầng tối thiểu, khả năng triển khai tức thì trên các thiết bị IoT/Edge Computing có cấu hình hạn chế.
  • Nhà nghiên cứu học máy: Nền tảng dữ liệu đối chuẩn thực nghiệm rõ ràng để tiếp tục mở rộng các nghiên cứu kết hợp giữa học không giám sát và học bán giám sát (Semi-supervised Learning).

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

1. Yêu cầu phần cứng và môi trường tối thiểu để chạy mã nguồn là gì?

Hệ thống yêu cầu máy tính cài đặt GNU Octave phiên bản $\ge 4.2$ hoặc MATLAB phiên bản $\ge R2014b$. Cấu hình phần cứng tối thiểu: CPU Dual-Core 2.0 GHz, RAM 2 GB, dung lượng đĩa trống 500 MB. Toàn bộ mã nguồn chạy trên kiến trúc tập lệnh tiêu chuẩn, không yêu cầu GPU.

2. Tại sao lại sử dụng chuẩn khoảng cách Euclidean thay vì khoảng cách Manhattan hay Cosine?

Khoảng cách Euclidean tương ứng trực tiếp với giả định dữ liệu phân bố theo hình cầu trong không gian đa chiều và tương thích hoàn toàn với phép tính trung bình số học ở bước cập nhật trọng tâm (đảm bảo hàm chi phí $J$ đơn điệu giảm). Khoảng cách Manhattan phù hợp hơn cho biến thể K-Medians, trong khi Cosine phù hợp cho dữ liệu văn bản thưa.

3. Làm thế nào để tự động gán nhãn chữ số cho một cụm sau khi K-Means hoàn thành?

Sau khi quá trình phân cụm kết thúc, ta thực hiện thao tác Major Voting (Bỏ phiếu đa số): Với mỗi cụm $k$, ta đếm tần suất xuất hiện của các nhãn thực tế $y$ của các mẫu rơi vào cụm đó. Chữ số chiếm tỷ lệ lớn nhất sẽ được gán làm nhãn đại diện chính thức cho cụm $k$.

4. Tại sao lại xảy ra hiện tượng độ chính xác tăng khi tăng số trọng tâm $K$?

Do chữ số viết tay có nhiều phong cách thể hiện khác nhau. Việc tăng $K$ cho phép mỗi phong cách viết của cùng một chữ số sở hữu một vector trọng tâm riêng biệt (ví dụ: 5 cụm khác nhau cùng đại diện cho số 0 nhưng với các độ nghiêng và độ béo khác nhau), từ đó giảm thiểu sai số phân cụm.

5. So sánh chi phí tính toán giữa K-Means và Logistic Regression?

Trong giai đoạn huấn luyện, K-Means lặp qua $m$ mẫu với $K$ cụm qua 100 vòng lặp có độ phức tạp $\mathcal{O}(100 \cdot m \cdot K \cdot d)$. Logistic Regression One-vs-All cần huấn luyện 10 bộ phân loại nhị phân qua 500 vòng lặp Gradient Descent có độ phức tạp $\mathcal{O}(10 \cdot 500 \cdot m \cdot d)$. Khi $K < 50$, K-Means có tốc độ hội tụ nhanh hơn đáng kể.

Kết luận

Đồ án đã nghiên cứu và hiện thực hóa thành công thuật toán phân cụm K-Means ứng dụng vào bài toán nhận dạng chữ số viết tay trên bộ cơ sở dữ liệu chuẩn MNIST. Bằng việc tự xây dựng thuật toán thông qua kỹ thuật vector hóa ma trận trên GNU Octave/MATLAB, công trình đã làm sáng tỏ mối quan hệ biện chứng giữa số lượng trọng tâm khởi tạo $K$ và độ chính xác phân loại: nâng độ chính xác từ 58.14% ($K=10$) lên 85.32% ($K=250$), chứng minh khả năng tự thích ứng của mô hình học không giám sát đối với sự đa dạng của nét chữ viết tay con người.

Mặc dù độ chính xác của K-Means ở mức cơ sở chưa thể vượt qua mô hình học có giám sát Logistic Regression (93.40%), phương pháp này mở ra tiềm năng ứng dụng to lớn trong việc tự động tiền xử lý dữ liệu lớn, giảm thiểu 100% chi phí gán nhãn ban đầu và cho phép triển khai tối ưu trên các hệ thống tính toán biên. Hướng đi tiếp theo của đề tài là kết hợp giải thuật K-Means++ cùng kỹ thuật nén không gian Autoencoder nhằm hướng tới hệ thống OCR hoàn chỉnh, chuẩn xác và tiết kiệm tài nguyên.