Tổng quan nghiên cứu

Trong kỷ nguyên số hóa, sự bùng nổ của các hệ thống cơ sở dữ liệu quy mô lớn đã tạo ra những kho lưu trữ khổng lồ chứa hàng triệu bản ghi, nhưng đi kèm với đó là tỷ lệ dữ liệu nhiễu và bất thường chiếm từ 15% đến 30% trong thực tế. Các ràng buộc toàn vẹn truyền thống, tiêu biểu là phụ thuộc hàm cổ điển theo hệ tiên đề Armstrong năm 1974, đòi hỏi sự chính xác tuyệt đối trên 100% dữ liệu. Chỉ cần một vài bản ghi sai lệch cũng có thể vô hiệu hóa toàn bộ các phụ thuộc hàm quan trọng, gây trở ngại lớn cho quá trình phát hiện tri thức. Trước thực trạng đó, bài toán đặt ra là cần xây dựng các mô hình nới lỏng điều kiện nhằm khai phá tri thức tiềm ẩn từ dữ liệu không hoàn hảo.

Luận văn thạc sĩ chuyên ngành Hệ thống thông tin của tác giả Nguyễn Minh Huy, dưới sự hướng dẫn khoa học của Giáo sư Tiến sĩ Vũ Đức Thi tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội năm 2011, tập trung giải quyết bài toán phát hiện phụ thuộc hàm xấp xỉ và ứng dụng trong khai phá dữ liệu. Mục tiêu cụ thể của nghiên cứu bao gồm: hệ thống hóa lý thuyết phụ thuộc hàm xấp xỉ loại 1 và loại 2; phát triển thuật toán cải tiến AFDMCEC dựa trên phủ tối thiểu và lớp tương đương để khắc phục nhược điểm của thuật toán TANE; đồng thời ứng dụng phụ thuộc hàm xấp xỉ vào việc rút gọn thuộc tính trong bảng quyết định và tối ưu hóa cây quyết định phân lớp.

Nghiên cứu được tiến hành trên các tập dữ liệu chuẩn từ kho lưu trữ máy học quốc tế UCI và dữ liệu kiểm toán tài chính gồm 5 tháng hoạt động với tổng ngân sách trên 1,5 tỷ đồng. Kết quả nghiên cứu có ý nghĩa phương pháp luận sâu sắc, giúp tối ưu hóa không gian tìm kiếm từ độ phức tạp hàm mũ thành các bước duyệt lớp tương đương hiệu quả, giảm thiểu từ 25% đến 40% thời gian xử lý và loại bỏ tới 66,7% các thuộc tính dư thừa trong bảng quyết định thực nghiệm.

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

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng lý thuyết mô hình dữ liệu quan hệ được Codd đề xuất năm 1970 và Hệ tiên đề Armstrong năm 1974 gồm ba luật suy dẫn căn bản: tính phản xạ, tính tăng trưởng và tính bắc cầu. Bên cạnh đó, luận văn tích hợp Lý thuyết tập thô của Pawlak để mô hình hóa hệ thống thông tin thông qua khái niệm bảng quyết định, quan hệ không phân biệt được, miền xấp xỉ trên, miền xấp xỉ dưới và miền khẳng định.

Mô hình nghiên cứu tuân thủ quy trình phát hiện tri thức trong cơ sở dữ liệu gồm 4 giai đoạn chuẩn: tìm hiểu lĩnh vực ứng dụng, tiền xử lý dữ liệu thô (chiếm từ 60% đến 70% tổng thời gian quy trình), khai phá mẫu tiềm ẩn và diễn giải tri thức. Trong đó, hai mô hình phụ thuộc hàm xấp xỉ cốt lõi được áp dụng gồm:

  1. Phụ thuộc hàm xấp xỉ loại 1: Sử dụng độ đo sai số g3 đo lường tỷ lệ các bộ dữ liệu vi phạm phụ thuộc hàm trên tổng số bản ghi, cho phép xác định quan hệ xấp xỉ khi sai số nhỏ hơn ngưỡng epsilon quy định từ 0 đến 1.
  2. Phụ thuộc hàm xấp xỉ loại 2: Áp dụng hàm khoảng cách chuẩn hóa rho giữa các bộ giá trị trên tập thuộc tính liên tục với ngưỡng sai lệch epsilon nhỏ hơn 1.

Các khái niệm chính được định nghĩa chặt chẽ bao gồm: phân hoạch dữ liệu Pi, lớp tương đương, bao đóng xấp xỉ, khóa xấp xỉ tối thiểu và các dạng chuẩn xấp xỉ 2NF, 3NF, BCNF.

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

Nguồn dữ liệu của luận văn được tổng hợp từ hai nguồn chính: các bộ dữ liệu thực nghiệm chuẩn từ kho lưu trữ UCI Machine Learning Repository với số lượng thuộc tính dao động từ 5 đến 30 thuộc tính; bảng dữ liệu điều tra hành vi tiêu dùng gồm 14 đối tượng khách hàng với 7 thuộc tính; và bộ dữ liệu kiểm toán tài chính doanh nghiệp 5 tháng với các chỉ số chi phí nguyên vật liệu, tiền lương và thuế VAT từ 41 triệu đến 680 triệu đồng.

Cỡ mẫu nghiên cứu được thiết kế linh hoạt từ 14 bản ghi mô phỏng đến các tập dữ liệu mở rộng với quy mô lên tới 100.000 bản ghi nhằm kiểm định giới hạn tính toán của thuật toán. Phương pháp chọn mẫu là chọn mẫu phân tầng kết hợp lấy mẫu ngẫu nhiên có kiểm soát, đảm bảo phản ánh đầy đủ cả biến định danh lẫn biến số liên tục.

Phương pháp phân tích trọng tâm là thuật toán cải tiến AFDMCEC (Approximate Functional Dependency using Minimal Cover and Equivalent Classes) phát triển từ thuật toán TANE. Lý do lựa chọn phương pháp phân tích này là vì thuật toán TANE gốc phải duyệt toàn bộ không gian tổ hợp với độ phức tạp O(2 mũ số thuộc tính), trong khi AFDMCEC tận dụng lớp tương đương và phủ tối thiểu để cắt tỉa sớm các nhánh dư thừa. Toàn bộ quá trình thu thập, lập trình thực nghiệm bằng ngôn ngữ C# và đánh giá hiệu năng được hoàn thành trong khung thời gian 12 tháng tại Đại học Quốc gia Hà Nội.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm và kiểm thử trên các tập dữ liệu đã mang lại 4 phát hiện quan trọng có giá trị khoa học cao:

Thứ nhất, thuật toán AFDMCEC thể hiện hiệu năng vượt trội so với thuật toán TANE gốc. Trên cùng các bộ dữ liệu chuẩn UCI, việc sử dụng lớp tương đương để lọc sớm các phụ thuộc hàm đã giúp AFDMCEC rút ngắn thời gian xử lý thực tế từ 25% đến 35% đối với các bảng dữ liệu có từ 15 đến 25 thuộc tính.

Thứ hai, trong bài toán kiểm toán thực tế gồm 5 tháng tài chính, việc áp dụng phụ thuộc hàm xấp xỉ loại 2 với ngưỡng sai lệch epsilon bằng 0,01 (tương đương 1%) đã phát hiện chính xác dấu hiệu bất thường trong tháng thứ 5. Trong khi tổng chi phí giữa tháng 4 (1,510 tỷ đồng) và tháng 5 (1,515 tỷ đồng) chỉ chênh lệch khoảng 0,33%, thì chi phí nguyên vật liệu lại tăng đột biến từ 604,39 triệu đồng lên 680,43 triệu đồng (tăng 12,58%) và thuế VAT tăng từ 42,70 triệu đồng lên 48,03 triệu đồng (tăng 12,48%). Sự sai lệch vượt ngưỡng 5% này là bằng chứng rõ ràng chỉ ra nguy cơ sai sót hoặc gian lận kê khai.

Thứ ba, trong ứng dụng rút gọn bảng quyết định chẩn đoán bệnh cúm gồm 6 bản ghi với 3 thuộc tính điều kiện (Đau đầu, Đau cơ, Thân nhiệt), thuật toán đã xác định Thân nhiệt là thuộc tính lõi duy nhất. Hai thuộc tính còn lại được rút gọn thành công, giúp cắt giảm 66,7% số lượng thuộc tính đầu vào mà vẫn duy trì độ chính xác phân loại 100%.

Thứ tư, khi xây dựng cây quyết định trên tập dữ liệu 14 khách hàng mua ô tô, việc tính toán lượng thông tin nhận được (Information Gain) cho thấy thuộc tính Phụ cấp tại điểm phân tách 83 đạt giá trị Gain tối đa là 0,3032 trên tổng lượng thông tin toàn cây S bằng 0,940. Con số này vượt trội hơn hẳn so với thuộc tính Công việc (Gain bằng 0,246) và Thành phần gia đình (Gain bằng 0,048), chứng minh rằng việc loại bỏ các biến phụ thuộc hàm xấp xỉ giúp cây quyết định có số tầng phân nhánh ít nhất nhưng đạt độ chính xác dự báo cao nhất.

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự bứt phá về tốc độ của AFDMCEC là cơ chế cắt tỉa thông minh. Thuật toán TANE cũ bị nghẽn cổ chai khi số lượng thuộc tính tăng lên do phải sinh toàn bộ các mức tổ hợp thuộc tính. AFDMCEC khắc phục triệt để bằng cách quét dữ liệu một lần để xác định các lớp tương đương, sau đó loại bỏ ngay các tập thuộc tính tương đương khi hàm lỗi g3 nhỏ hơn ngưỡng sai số cho phép.

Dữ liệu so sánh hiệu năng có thể được mô tả trực quan thông qua biểu đồ đường biểu diễn trục hoành là số lượng thuộc tính (từ 5 đến 30 thuộc tính) và trục tung là thời gian chạy (tính bằng giây). Đường biểu diễn của AFDMCEC luôn duy trì độ dốc thấp hơn rõ rệt so với TANE khi số chiều dữ liệu tăng cao. Đồng thời, bảng ma trận phân hoạch và bảng so sánh độ phức tạp thời gian T(n) minh chứng rõ nét cho khả năng mở rộng của thuật toán trên các quan hệ chứa hàng trăm ngàn bộ dữ liệu.

So với các nghiên cứu phụ thuộc hàm cổ điển vốn thất bại khi gặp dữ liệu thực tế do chỉ một vài dòng nhiễu làm phá vỡ toàn bộ cấu trúc ràng buộc, phương pháp tiếp cận xấp xỉ của luận văn mang lại tính linh hoạt cao. Nghiên cứu khẳng định rằng việc tích hợp phụ thuộc hàm xấp xỉ vào bước tiền xử lý giúp giảm thiểu hiện tượng quá khớp (overfitting) trong các thuật toán học quy nạp như ID3 hay C4.5, tạo ra bước tiến quan trọng trong tối ưu hóa mô hình hộp trắng.

Đề xuất và khuyến nghị

Dựa trên các kết quả lý thuyết và thực nghiệm đạt được, luận văn đưa ra 4 nhóm giải pháp và khuyến nghị hành động cụ thể:

  1. Tích hợp thuật toán AFDMCEC vào hệ thống kiểm toán tự động: Kiểm toán Nhà nước và các tổ chức kiểm toán độc lập cần ứng dụng mô hình phụ thuộc hàm xấp xỉ loại 2 để tự động rà soát các bảng cân đối kế toán, hướng tới mục tiêu phát hiện sớm trên 90% các giao dịch bất thường hoặc gian lận chi phí trong vòng 6 tháng triển khai bởi nhóm chuyên gia công nghệ và kiểm toán viên.
  2. Chuẩn hóa quy trình tiền xử lý và rút gọn thuộc tính trong khai phá dữ liệu: Các bộ phận phân tích dữ liệu doanh nghiệp cần áp dụng kỹ thuật tìm tập lõi và bao đóng xấp xỉ để giảm từ 30% đến 50% số chiều dữ liệu đầu vào trước khi huấn luyện các mô hình cây quyết định, hoàn thành áp dụng trong quý I bởi các kỹ sư dữ liệu.
  3. Thiết lập khung ngưỡng sai số epsilon linh hoạt theo từng ngành: Các viện nghiên cứu và hiệp hội chuyên ngành cần xây dựng bộ tiêu chuẩn tham chiếu cho ngưỡng sai số epsilon, quy định mức 0,01 đối với dữ liệu tài chính - y tế và mức từ 0,05 đến 0,1 đối với dữ liệu thương mại điện tử, ban hành hướng dẫn trong vòng 9 tháng bởi hội đồng khoa học kỹ thuật.
  4. Mở rộng thuật toán trên nền tảng tính toán phân tán: Đội ngũ phát triển phần mềm cần tiến hành nâng cấp mã nguồn thuật toán AFDMCEC sang các nền tảng xử lý dữ liệu lớn như Apache Spark hoặc Hadoop, đặt mục tiêu xử lý các tập dữ liệu trên 10 triệu bản ghi trong lộ trình từ 12 đến 18 tháng do các trung tâm R&D công nghệ thông tin chủ trì.

Đối tượng nên tham khảo luận văn

Nội dung và kết quả của luận văn mang lại giá trị thiết thực cho 4 nhóm đối tượng chính:

  1. Học viên cao học và nghiên cứu sinh ngành Công nghệ thông tin: Tài liệu cung cấp hệ thống chứng minh toán học chặt chẽ về bao đóng xấp xỉ, khóa xấp xỉ và các dạng chuẩn 2NF, 3NF, BCNF, đóng vai trò là tài liệu tham khảo nền tảng để phát triển các đề tài nghiên cứu chuyên sâu về tối ưu hóa cơ sở dữ liệu.
  2. Chuyên gia phân tích dữ liệu và kỹ sư học máy: Hưởng lợi từ phương pháp luận tính toán Information Gain kết hợp loại trừ thuộc tính phụ thuộc hàm để tối ưu hóa cấu trúc cây quyết định ID3/C4.5, giúp tinh gọn mô hình phân lớp trong các bài toán dự đoán hành vi khách hàng.
  3. Kiểm toán viên và chuyên viên thanh tra tài chính: Có thể vận dụng trực tiếp thuật toán phụ thuộc hàm xấp xỉ loại 2 làm công cụ hỗ trợ kiểm tra tính nhất quán giữa tổng chi phí, đơn giá nguyên vật liệu và thuế VAT, giúp phát hiện tự động các điểm bất thường trong hàng vạn chứng từ kế toán.
  4. Quản trị viên cơ sở dữ liệu và kiến trúc sư hệ thống: Tiếp cận phương pháp phân tích lược đồ quan hệ theo các dạng chuẩn xấp xỉ, hỗ trợ thiết kế và tái cấu trúc các kho dữ liệu lớn có tỷ lệ nhiễu cao nhằm duy trì hiệu năng truy vấn tối ưu.

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

  1. Phụ thuộc hàm xấp xỉ khác gì so với phụ thuộc hàm cổ điển trong cơ sở dữ liệu? Phụ thuộc hàm cổ điển yêu cầu ràng buộc giữa các thuộc tính phải đúng tuyệt đối trên 100% bản ghi. Trong khi đó, phụ thuộc hàm xấp xỉ cho phép một tỷ lệ lỗi nhỏ trong phạm vi ngưỡng sai số epsilon từ 1% đến 5%, giúp nhận diện chính xác các quy luật tiềm ẩn ngay cả khi cơ sở dữ liệu chứa nhiễu hoặc dữ liệu khuyết thiếu.

  2. Ngưỡng sai lệch epsilon được xác định dựa trên cơ sở nào trong bài toán thực tế? Việc lựa chọn ngưỡng epsilon phụ thuộc vào yêu cầu nghiệp vụ và ý kiến chuyên gia. Trong các lĩnh vực đòi hỏi độ chính xác cao như kiểm toán tài chính hoặc chẩn đoán y tế, epsilon thường được thiết lập nghiêm ngặt ở mức 0,01 (1%), trong khi các bài toán phân tích xu hướng thị trường có thể chấp nhận mức 0,05 đến 0,10.

  3. Vì sao thuật toán AFDMCEC lại đạt tốc độ xử lý nhanh hơn thuật toán TANE? Thuật toán TANE phải duyệt toàn bộ không gian tổ hợp với độ phức tạp hàm mũ O(2 mũ số thuộc tính). AFDMCEC cải tiến bằng cách kết hợp phủ tối thiểu và phân hoạch lớp tương đương, giúp cắt tỉa ngay các tập thuộc tính tương đương và loại bỏ từ 25% đến 35% các phép toán không cần thiết trong quá trình sinh mức.

  4. Việc loại bỏ thuộc tính phụ thuộc hàm xấp xỉ có tác động thế nào đến cây quyết định? Khi thuộc tính X1 xác định xấp xỉ thuộc tính X2, lượng thông tin Gain của X1 luôn lớn hơn hoặc bằng X2. Loại bỏ X2 giúp cây quyết định không phân tách trên các nút dư thừa, giảm chiều sâu của cây từ 1 đến 2 tầng và nâng cao khả năng tổng quát hóa dữ liệu dự báo.

  5. Thuật toán trong luận văn có khả năng xử lý đồng thời dữ liệu số và dữ liệu định danh không? Nghiên cứu giải quyết toàn diện cả hai loại dữ liệu: phụ thuộc hàm xấp xỉ loại 1 xử lý dữ liệu định danh thông qua phép phân hoạch lớp tương đương, trong khi loại 2 sử dụng hàm khoảng cách chuẩn hóa rho để xử lý dữ liệu số liên tục, đảm bảo tính ứng dụng rộng rãi.

Kết luận

Luận văn thạc sĩ của tác giả Nguyễn Minh Huy đã giải quyết thành công bài toán khai phá tri thức từ dữ liệu không hoàn hảo với 5 đóng góp nổi bật:

  • Hệ thống hóa toàn diện cơ sở toán học của phụ thuộc hàm xấp xỉ loại 1 và loại 2, thiết lập các định nghĩa về bao đóng và khóa xấp xỉ tối thiểu.
  • Đề xuất thành công thuật toán AFDMCEC, cải thiện tốc độ xử lý từ 25% đến 40% so với thuật toán TANE tiêu chuẩn trên các tập dữ liệu thử nghiệm.
  • Ứng dụng xuất sắc vào kiểm toán tài chính thực tế, phát hiện chính xác sai lệch chi phí trên 12% tại tháng thứ 5 với ngưỡng sai số 1%.
  • Tối ưu hóa quy trình xây dựng cây quyết định, giảm thiểu 66,7% thuộc tính dư thừa trong bảng quyết định và nâng cao độ chính xác phân lớp.
  • Đặt nền móng vững chắc cho việc tích hợp các mô hình xấp xỉ hóa vào hệ quản trị cơ sở dữ liệu quan hệ và hệ thống khai phá dữ liệu hiện đại.

Trong giai đoạn 12 đến 18 tháng tới, hướng phát triển kế tiếp cần tập trung vào việc song song hóa thuật toán trên nền tảng dữ liệu lớn phân tán. Các nhà nghiên cứu, kỹ sư dữ liệu và kiểm toán viên có thể tham khảo, ứng dụng ngay các phương pháp luận của luận văn để nâng cao năng lực khai thác tri thức tự động cho tổ chức.