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

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KINH TẾ KHOA HỆ THỐNG THÔNG TIN KINH TẾ  KHÓA LUẬN TỐT NGHIỆP 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 SINH VIÊN THỰC HIỆN NGÔ TRẦN HOÀNG LÂM NIÊN KHÓA 2015 – 2019 Tr ườ ng Đ ại họ c K inh tế H uế ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KINH TẾ KHOA HỆ THỐNG THÔNG TIN KINH TẾ  KHÓA LUẬN TỐT NGHIỆP 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 Sinh viên thực hiện Giảng viên hướng dẫn Ngô Trần Hoàng Lâm TS N.

NỘI DUNG

CƠ SỞ LÝ THUYẾT

Mỗi con người được trang bị các giác quan như thị giác, thính giác, và xúc giác để quan sát và nhận thức thế giới xung quanh, từ đó rút ra kinh nghiệm và đánh giá riêng Tương tự, để máy tính có thể nhận thức và xử lý thông tin như con người, cần trang bị cho nó các thiết bị như camera và tai nghe, được xem như giác quan của máy tính Nhờ đó, máy tính có khả năng thực hiện những công việc phức tạp nhanh chóng và chính xác hơn Ví dụ, máy tính có thể lọc ra những người giống nhau trong hai đoạn băng ghi hình dài 12 tiếng hoặc phân tích âm thanh trong một cuộc trò chuyện ở môi trường ồn ào Những công việc này, khi được huấn luyện cho máy tính, được gọi là tác vụ Khi máy tính được trang bị nhiều tác vụ như vậy, nó trở thành AI (Trí tuệ nhân tạo).

AI, viết tắt của Artificial Intelligence, hay trí tuệ nhân tạo, được phân chia thành 4 hướng tiếp cận chính trong quá trình phát triển của nó.

- 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 bối cảnh công nghệ số phát triển nhanh chóng, trí tuệ nhân tạo đang tạo ra những thay đổi sâu sắc trong nhiều lĩnh vực của cuộc sống Nó hỗ trợ tối đa cho các hoạt động của con người, bao gồm kinh doanh, bảo mật và y tế.

Một số hệ thống trí tuệ nhân tạo tiêu biểu bao gồm 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 và Bixby của Samsung, cùng với các nhà thông minh có khả năng học hỏi và ghi nhớ thói quen của người dùng.

Trường Đại học Kinh tế Huế đang áp dụng công nghệ trí tuệ nhân tạo (AI) qua các hệ thống như nhận diện giọng nói, khuôn mặt và gợi ý sản phẩm, mang lại cuộc sống tiện nghi và hiện đại hơn AI không chỉ cải thiện chất lượng sản phẩm mà còn nâng cao năng suất công việc, góp phần tạo ra một xã hội tiến bộ Để máy tính có thể “học tập”, lĩnh vực Học máy (Machine Learning - ML) đóng vai trò quan trọng, cho phép máy tính tự học hỏi từ dữ liệu đã thu thập Học máy sử dụng lượng dữ liệu lớn để giải quyết bài toán, giúp máy tính tự động thực hiện các tác vụ và xử lý tình huống mới với độ chính xác 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) là phương pháp mà máy tính được huấn luyện dựa trên các mẫu đầu vào và đầu ra đã biết trước Sau quá trình huấn luyện, máy tính có khả năng tự động dự đoán kết quả cho đầu ra khi nhận đầu vào mới Học có giám sát được chia thành hai loại chính: hồi quy (Regression) và phân lớp (Classification).

Trường Đại học Kinh tế Huế

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) là phương pháp mà máy tính chỉ nhận dữ liệu đầu vào mà không có đầu ra cụ thể Trong quá trình này, máy tính tự động phân loại các mẫu dữ liệu và nhận diện các mẫu mới Học không giám sát được chia thành hai loại chính: 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:

 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.

Do việc nghiên cứu và ứng dụng học máy tại Việt Nam còn hạn chế, các thuật ngữ tiếng Việt chưa được thống nhất, dẫn đến việc thiếu chuẩn mực chung cho tài liệu Vì vậy, trong khóa luận này, tác giả sẽ sử dụng các thuật ngữ tiếng Anh gốc để đảm bảo giữ nguyên nghĩa của chúng Danh sách các thuật ngữ tiếng Anh được sử dụng trong khóa luận sẽ được trình bày ở trang viii.

1.2 T ổ ng quan v ề h ọ c không giám sát

Trong ngành khoa học dữ liệu, có hai phương pháp chính để sử dụng dữ liệu: học có giám sát và học không giám sát Học có giám sát liên quan đến việc sử dụng dữ liệu để huấn luyện mô hình và tạo ra dự đoán cho dữ liệu mới, trong khi học không giám sát tập trung vào việc tìm kiếm sự tương đồng trong bộ dữ liệu và phân loại các nhóm khác nhau Ưu điểm của học không giám sát là không yêu cầu kết quả đầu ra cho tất cả các bộ dữ liệu, điều này thường xảy ra trong thực tế Khóa luận này sẽ tập trung vào phương pháp phân cụm Kmeans, thuộc về học không giám sát, và sẽ trình bày nội dung này trước, trong khi phần học có giám sát sẽ được đề cập ở phần sau.

Học không giám sát là phương pháp mà máy tính tự học mà không cần hướng dẫn cụ thể hay ví dụ trước, chỉ dựa vào bộ dữ liệu đầu vào Máy tính sẽ tự động phát hiện các điểm tương đồng và khác biệt trong dữ liệu, từ đó nhóm chúng thành các cụm khác nhau Ví dụ, một máy tính chưa từng thấy bức ảnh nào và cũng không được dạy về chó hay mèo sẽ vẫn có khả năng phân loại chúng dựa trên đặc điểm hình ảnh.

Hình 1.1 Hình minh họa cho ví dụcủa phương pháp học không giám sát

Máy tính chưa được đào tạo để phân biệt chó và mèo trong hình ảnh, nhưng nhờ vào học không giám sát, nó có thể phân nhóm hình ảnh dựa trên các đặc điểm tương đồng.

Trường Đại học Kinh tế Huế có khả năng phân tích hình ảnh, cho phép tách biệt các khu vực trong bức tranh thành vùng chứa hình ảnh chó và vùng chứa hình ảnh mèo Điều này được thực hiện dựa trên sự tương đồng giữa các loài động 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:

 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)

 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)

Phân cụm [3], [4] là quá trình chia dân số hoặc dữ liệu thành các nhóm, trong đó các điểm dữ liệu trong cùng một nhóm có sự tương đồng cao, trong khi khác biệt với các nhóm khác Nói một cách đơn giản, phân cụm giúp xác định các tập hợp đối tượng dựa trên các đặc điểm tương đồng và khác biệt giữa chúng.

Các điểm dữ liệu trong biểu đồ dưới đây được phân lớp thành 3 cụm riêng biệt Chúng ta có thể dễ dàng nhận diện các cụm này.

Hình 1.2 Hìnhảnh minh họa cho phương phápphân cụmđã chia dữliệu thành 3 cụm hình cầu

(Nguồn:https://www.geeksforgeeks.org/)

BÀI TOÁN NHẬN DIỆN CHỮ SỐ VIẾT TAY VỚI THUẬT TOÁN PHÂN CỤM KMEANS

Bài toán phân cụm chữ số yêu cầu xây dựng một chương trình để phân chia các hình ảnh 20x20 pixel grayscale của chữ số viết tay thành các cụm khác nhau dựa trên độ tương đồng Mục tiêu là xác định cụm mà một hình ảnh mới thuộc về, từ đó nhận diện chữ số tương ứng.

Chúng tôi sử dụng bộ dữ liệu MNIST, bao gồm 5000 chữ số viết tay từ 250 người, để huấn luyện mô hình phân cụm chữ số Mỗi chữ số từ 0 đến 9 có 500 mẫu, giúp tạo ra sự đa dạng trong dữ liệu MNIST là bộ dữ liệu mở, miễn phí, được cung cấp bởi các tác giả LeCun, Cortes và Burges, phục vụ cho nghiên cứu và thử nghiệm Hình ảnh chữ số được chuẩn hóa kích thước và căn giữa, làm cho bộ dữ liệu này trở thành công cụ hữu ích để đánh giá và thử nghiệm các mô hình học máy mà không cần nhiều công sức làm sạch dữ liệu.

Mỗi chữ số trong tập huấn luyện được biểu diễn bằng một ảnh xám kích thước 20 × 20 pixel, trong đó mỗi pixel có giá trị từ 0 đến 255 Giá trị 0 tương ứng với màu đen, trong khi giá trị 255 đại diện cho màu trắng; các giá trị trung gian phản ánh độ sáng của ảnh, với giá trị càng cao tương ứng với cường độ sáng tăng lên Khi chuyển đổi ảnh kích thước 20 × 20 pixel thành dạng vectơ, chúng ta thu được một vectơ có kích thước 1 × 400.

Trong ví dụ này, mỗi chữ số sẽ được chuyển đổi thành một vectơ dòng 1×400, tạo thành ma trận đầu vào X có kích thước 5000 × 400, trong đó mỗi dòng đại diện cho một hình ảnh chữ số viết tay với 400 thuộc tính Đồng thời, chúng ta cũng có một vectơ 5000×1 chứa nhãn cho tập huấn luyện, với mỗi nhãn tương ứng với giá trị của chữ số.

Trường Đại học Kinh tế Huế tựnhiên thuộc tập các sốtừ 1 đến 10, đại diện cho 10 chữsốtừ 0 đến 9 trong đó nhãn

Trong bài viết này, chúng ta sẽ tìm hiểu về sự tương ứng giữa các nhãn số và chữ số trong các phương pháp học máy Cụ thể, số 10 tương ứng với số 0, trong khi các nhãn từ 1 đến 9 tương ứng với các chữ số từ 1 đến 9 Đối với hồi quy logistic, đây là phương pháp học có giám sát, do đó việc gán nhãn cho dữ liệu là cần thiết để máy tính xác định kết quả đầu ra Ngược lại, phương pháp phân cụm Kmeans là một phương pháp học không giám sát, trong đó việc gán nhãn có thể được xem như là kết quả để chúng ta kiểm tra lại sau khi thuật toán hoàn thành.

Hình 2.1 Cấu trúc của tập dữ liệu chữ số viết tay

Hình 2.2 Ví dụchọn 250 mẫu ngầu nhiên của dữliệu nhận diện chữsốviết tay

2.2 Áp d ụ ng thu ậ t toán phân c ụ m Kmeans vào bài toán nh ậ n di ệ n ch ữ s ố vi ế t tay

Chữ số viết tay bao gồm 10 chữ số từ 0 đến 9, với mỗi chữ số có 500 mẫu khác nhau Phương pháp phân cụm giúp chia các chữ số này thành ít nhất 10 cụm khác nhau, do mỗi chữ số có thể có nhiều cách viết tùy thuộc vào người viết, như số 3, số 4 hay số 7 Việc quy ước này xuất phát từ việc chúng ta biết có 10 dạng chữ số, mặc dù máy tính không tự nhận biết điều đó Khi dữ liệu được đưa vào máy tính, chỉ số sẽ được khởi tạo bằng 10 (K là số cụm), và trong mô hình thử nghiệm, số trọng tâm K sẽ được tăng dần để thu thập kết quả.

Sau khi xác định 10 trọng tâm ban đầu, bước tiếp theo là tính khoảng cách Euclidean của từng phần tử đến tất cả các trọng tâm.

10 trọng tâm), ta có công thức:

Sau khi tính toán khoảng cách từ mỗi phần tử đến tất cả các trọng tâm, phần tử sẽ được gán cho trọng tâm có khoảng cách gần nhất Quá trình này sẽ tạo ra 10 cụm dữ liệu, mỗi cụm chứa một số phần tử nhất định Khoảng cách từ mỗi phần tử đến trọng tâm của nó sẽ gần hơn so với khoảng cách đến các trọng tâm khác trong bộ dữ liệu.

Sau khi phân chia các phần tử thành 10 cụm, chúng ta tiến hành cập nhật trọng tâm cho từng cụm Quá trình này không chỉ điều chỉnh trọng tâm mà còn thay đổi số lượng phần tử gán cho các cụm tương ứng Việc cập nhật trọng tâm được thực hiện bằng cách tính trung bình cộng.

Sau khi cập nhật trung điểm, các phần tử sẽ thay đổi bằng cách tính lại khoảng cách đến tất cả các trọng tâm và được gán cho trọng tâm gần nhất Vấn đề hiện tại là làm sao để máy tính dừng quá trình phân cụm và đưa ra kết quả chính xác.

Trường Đại học Kinh tế Huế thực hiện quá trình lặp lại hai bước chính: tính toán khoảng cách và gán mỗi phần tử đến trọng tâm gần nhất, sau đó cập nhật lại trọng tâm Thuật toán dừng lại khi không còn phần tử nào thay đổi trọng tâm, ngược lại, nếu có sự thay đổi, quá trình cập nhật sẽ tiếp tục.

Thuật toán Kmeans phân cụm các phần tử có độ tương đồng, dẫn đến việc các chữ số cùng loại sẽ được nhóm lại thành một cụm Áp dụng Kmeans vào bài toán, chúng ta sẽ nhận được kết quả là các nhóm dữ liệu được phân loại từ bộ dữ liệu đầu vào.

2.3 Áp d ụ ng Logistic Regressiom vào bài toán nh ậ n di ệ n ch ữ s ố vi ế t tay

Logistic Regression được áp dụng trên bộ dữ liệu MNIST với 10 chữ số từ 0 đến 9, cho phép xây dựng mô hình phân lớp đa lớp thông qua phương pháp Binary Logistic Regression kết hợp với thuật toán one-vs-all Do có 10 chữ số, chúng ta cần thực hiện phân lớp 10 lần, mỗi lần huấn luyện sẽ tạo ra một bộ tham số khác nhau cho từng lớp Thuật toán sẽ phân lớp một lớp cụ thể so với tất cả các lớp còn lại, và để tối ưu hóa quá trình huấn luyện, chúng ta sẽ sử dụng công thức vectơ hóa của Logistic Regression nhằm giảm thiểu số vòng lặp thực thi.

Trong tập dữ liệu các chữ số viết tay, số lượng lớp cần phân loại là K = 10 Tuy nhiên, theo thuật toán của chuyên gia, chương trình có thể hoạt động với mọi giá trị K Cụ thể, bằng cách gọi thuật toán one-vs-all K lần, chương trình sẽ phân lớp cho tất cả các tham số của mỗi lớp với tất cả các lớp còn lại, và lưu trữ trong một ma trận.

Trong bài toán phân loại chữ số từ 0 đến 9, chúng ta sử dụng mô hình Logistic Regression với ma trận ℝ × ( ), trong đó mỗi hàng tương ứng với một vectơ tham số được tìm ra khi phân lớp một chữ số so với các chữ số còn lại, với kích thước 401 Do đây là học có giám sát, chúng ta gán nhãn cho các chữ số từ 0 đến 9, trong đó chữ số 0 được gán nhãn cho số 10, và các chữ số từ 1 đến 9 được gán nhãn tương ứng Chương trình sẽ thực hiện phân lớp cho K = 10 lớp, và nếu chữ số trên hình ảnh thứ j có nhãn k thì y j = 1, ngược lại y j = 0 Qua đó, bài toán phân loại 10 lớp sẽ được chuyển đổi thành 10 bài toán phân loại nhị phân riêng biệt sử dụng mô hình Logistic Regression.

Sau khi huấn luyện xong ta thu được vectơ tham số ( ) ∈ ℝ , thực hiện huấn luyện trên toàn bộ ∈ 1, … , = 10 ta thu về10 vectơ tham số ( ) , ( ) , … , ( ) ∈

ℝ Với bất kỳhìnhảnh của chữsốnào, ta sẽ đưa nó vềdạng 1vectơ gồm 400 đặc trưng Để xác định làvectơ đặc trưng của chữsốnào thì ta lần lượt tính hàm giảthiết

ℎ , ∈ 1, … , = 10 Hàm giảthiết cho giá trịlớn nhấtứng với nào thì ta dự đoán làvectơ đặc trưng của chữsố đó.

THÍ NGHIỆM VÀ KẾT QUẢ

Chương trình thử nghiệm được thực hiện tổng cộng 7 lần với các giá trị khởi tạo trọng tâm K khác nhau: 10, 20, 50, 100, 150, 200, và 250 Các bước thiết lập trong mỗi lần chạy đều giống nhau, do đó, tôi chỉ mô tả chi tiết cách thực hiện thí nghiệm cho lần chạy đầu tiên với K = 10 Các lần chạy tiếp theo sẽ được tóm tắt các bước và trình bày hình ảnh kết quả cuối cùng.

3.1.1 Chương trình thửnghiệm với sốtrọng tâm khởi tạo ban đầu K = 10.

Bước 1 Thiết lập sốtrọng tâm K và sốvòng lặp tối đa.

Trong mã nguồn của chương trình thử nghiệm, chúng ta sẽ truy cập vào phần Kmeans_mnist.m để thiết lập các tham số quan trọng như số trọng tâm K ban đầu và số vòng lặp tối đa (max_iters) Sau nhiều lần kiểm tra, số vòng lặp tối đa được chọn là một giá trị tối ưu để đảm bảo hiệu quả của thuật toán.

Để đảm bảo độ chính xác cao nhất cho kết quả, số vòng lặp của thuật toán không được vượt quá số vòng lặp tối đa đã được xác định trước.

Hình 3.1 Hìnhảnh thiết lập trọng tâm K = 10 và sốvòng lặp tối đa là 100

Khi ta bắt đầu chạy mô hình thử nghiệm thì chương trình sẽ xuất ra hình ảnh của 10 mẫu chữsốviết tay được chọn ngẫu nhiên tương ứng với K = 10.

Hình 3.2 Hìnhảnh minh họa 10 mẫu chữsốviết tayứng với K = 10 Bước 2 Chạy chương trình và ghi nhận kết quảxuất ra.

Trong chương trình thử nghiệm chạy trên cửa sổ lệnh của Octave, tôi đã tích hợp tính năng đếm thời gian Khi chương trình bắt đầu, thời gian hiện tại sẽ được hiển thị ngay lập tức Sau khi đạt điều kiện dừng, chương trình sẽ xuất ra thời gian cập nhật tại thời điểm đó trước khi đưa ra độ chính xác của thuật toán và dự đoán minh họa Nhờ vào tính năng này, người dùng có thể tự tính toán thời gian thực hiện của thuật toán và đánh giá tốc độ hoạt động của nó.

Hình 3.3 minh họa quá trình chạy và kết quả của chương trình thử nghiệm phân cụm Kmeans với K = 10 Mặc dù không thể hiện thời gian bắt đầu thuật toán do giới hạn không gian hình ảnh, tôi sẽ tính toán và cung cấp kết quả thời gian chạy Kết quả cho thấy K = 10 là quá nhỏ so với bộ dữ liệu 5000 chữ số viết tay, dẫn đến độ chính xác chỉ đạt 58.14% Hình ảnh cũng chỉ ra nhãn dán đúng và dự đoán của Kmeans: ans = 1 nếu dự đoán đúng và ans = 0 nếu dự đoán sai.

Hình 3.4 Hìnhảnh nhãn dánđúng và dự đoán của chương trình thửnghiệm phân cụm

3.1.2 Chương trình thửnghiệm với sốtrọng tâm khởi tạo ban đầu K = 20.

Bước 2 Chạy chương trình và ghi nhận kết quảxuất ra.

Hình 3.6 Hìnhảnh quá trình chạy và các kết quảcủa chương trình thửnghiệm phân cụm Kmeans với K = 20

Hình 3.7 Hìnhảnh nhãn dánđúng và dự đoán của chương trình thửnghiệm phân cụm

3.1.3 Chương trình thửnghiệm với trọng tâm khởi tạo ban đầu K= 50.

Bước 2 Chạy chươngtrình và ghi nhận kết quảxuất ra.

Hình 3.10 Hìnhảnh nhãn dánđúng và dự đoán của chươngtrình thửnghiệm phân cụm Kmeans

3.1.4 Chương trình thửnghiệm với trọng tâm khởi tạo ban đầu K = 100.

Hình 3.13 Hìnhảnh nhãn dánđúng và dự đoán của chương trình thửnghiệm phân cụm Kmeans

Thuật toán phân cụm Kmeans được áp dụng trong bài toán nhận dạng chữ số viết tay thông qua hai bước lặp đi lặp lại: đầu tiên là gán dữ liệu vào các cụm, sau đó là cập nhật vị trí trọng tâm của các cụm đó.

Hình 3.23 Hìnhảnh minh họa các bước cập nhật lại trọng tâm của chương trình phân cụm Kmeans

Bảng kết quả cho thấy phương pháp phân cụm Kmeans đạt độ chính xác cao Đặc biệt, khi số trọng tâm K tăng lên, độ chính xác của phân cụm cũng cải thiện đáng kể.

Bảng 3 1 Kết quảmô hình nhận diện chữsốviết tay củaphương pháp phân cụm

Số trọng tâm K Vòng lặp/Vòng lặp tối đa Độ chính xác Thời gian

Số lượng trọng tâm K ảnh hưởng trực tiếp đến độ chính xác của thuật toán phân cụm Kmeans, như thể hiện trong bảng 3.1 Khi tăng số trọng tâm K từ 10 đến 250, độ chính xác tăng từ 58.14% lên 89.50% Tuy nhiên, việc tăng K lên mức quá cao, chẳng hạn như 5000, để đạt độ chính xác 100% là không khả thi và sẽ làm mất đi mục đích phân cụm Trong bộ dữ liệu chữ số viết tay, có 10 loại đối tượng từ 0 đến 9, và các chữ số như 2, 4, 7 có thể có nhiều kiểu viết khác nhau, do đó không cần thiết phải chọn số lượng trọng tâm K quá lớn.

Số lượng trọng tâm K có thể chọn nhiều hơn 10, và nó ảnh hưởng đến thời gian thực hiện của thuật toán Thời gian thực hiện thường tăng khi số trọng tâm K tăng, nhưng vị trí khởi tạo thuận lợi có thể giúp giảm thời gian thực hiện, ngay cả khi số trọng tâm K cao.

Kết quả từ bảng 3.1 cho thấy, dựa vào độ chính xác và thời gian thực hiện, khi trọng tâm K = 200, thời gian thực hiện có sự chênh lệch đáng kể so với các trọng tâm khác.

Trọng tâm K = 250 có thời gian chạy nhanh hi hữu khoảng 11 phút, do vị trí khởi tạo thuận lợi Độ chính xác của trọng tâm K = 200 đạt 88.40%, cao hơn 0.86% so với K = 150 (87.54%) Đối với trọng tâm K = 250, độ chính xác là 88.50%.

Trường Đại học Kinh tế Huế ghi nhận mức tăng 0.1%, tuy không đáng kể nhưng có xu hướng chững lại Với bộ dữ liệu 5000 chữ số, việc chọn trọng tâm K = 200 là một quyết định hợp lý để phân cụm Đối với phương pháp Logistic Regression, do đã sử dụng kết quả từ thuật toán chuyên gia để so sánh, tôi không trình bày chi tiết các bước thiết lập thí nghiệm Độ chính xác của phương pháp này rất cao và có thể đạt mức tối ưu khi số vòng lặp tăng đến một ngưỡng nhất định, trong khi cặp cũng ảnh hưởng đến số vòng lặp và ngược lại.

Bảng 3 2 Kết quảmô hình nhận diện chữsốviết tay của phương pháp Logistic

Regression bằng thuật toán chuyên gia Độchính xác

Kết quả từ bảng 3.2 cho thấy thuật toán chuyên gia với giá trị α = 0.1 đạt độ chính xác 95.00% Tuy nhiên, không có đảm bảo rằng cặp α và giá trị ban đầu sẽ mang lại kết quả tốt nhất Về lý thuyết, cần phải thử nghiệm tất cả các cặp α để tìm ra cặp tối ưu Ví dụ, với 10 giá trị α và 10 giá trị khác, sẽ cần thực hiện 100 lần chạy để xác định cặp tốt nhất, dẫn đến thời gian thực hiện rất lâu Trong khóa luận, chỉ sử dụng kết quả từ thuật toán chuyên gia để so sánh, nên không ghi lại thời gian thực hiện, nhưng rõ ràng là nó lâu hơn nhiều so với phương pháp phân cụm Kmeans.

Phương pháp phân cụm Kmeans thực hiện nhanh hơn nhiều so với Logistic Regression, nhưng độ chính xác của nó không cao bằng Một điểm khác biệt quan trọng là trong Kmeans, số lượng trọng tâm K được chọn ảnh hưởng đến độ chính xác và thời gian thực hiện, trong khi ở Logistic Regression, số vòng lặp và cặp có sự tương tác qua lại để đạt được độ chính xác tối ưu.

Tiêu đề	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
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	Hệ thống thông tin kinh tế
Thể loại	khóa luận tốt nghiệp
Năm xuất bản	2019
Thành phố	Huế

Định dạng
Số trang	71
Dung lượng	1,47 MB

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

NỘI DUNG

CƠ SỞ LÝ THUYẾT

BÀI TOÁN NHẬN DIỆN CHỮ SỐ VIẾT TAY VỚI THUẬT TOÁN PHÂN CỤM KMEANS

THÍ NGHIỆM VÀ KẾT QUẢ

Hướng phát triển của đề tài