Tổng quan nghiên cứu

Trong thời đại bùng nổ thông tin và chuyển đổi số, hơn 80% khối lượng dữ liệu thu thập được từ các hệ thống quản trị quan hệ khách hàng, cơ sở dữ liệu y tế, viễn thông và bảo hiểm tồn tại dưới dạng thuộc tính định danh phi thứ tự với số chiều rất lớn, thường vượt quá 50 thuộc tính. Phân cụm dữ liệu định danh nhiều chiều là một bài toán học máy không giám sát cốt lõi nhằm chia tập dữ liệu thành các nhóm có độ tương đồng nội cụm cao và độ tương đồng liên cụm thấp. Tuy nhiên, sự gia tăng nhanh chóng của số chiều dẫn đến hiện tượng bùng nổ số chiều và phân bố dữ liệu thưa thớt, khiến các độ đo khoảng cách hình học truyền thống bị suy giảm độ phân biệt rõ rệt.

Nghiên cứu của học viên Phan Thị Luân dưới sự hướng dẫn khoa học của Phó Giáo sư Hoàng Xuân Huấn tại Trường Đại học Công nghệ thuộc Đại học Quốc gia Hà Nội năm 2013 tập trung giải quyết bài toán tối ưu hóa phân cụm cho dữ liệu định danh có số chiều cao. Mục tiêu cụ thể của luận văn là khảo sát hệ thống hóa các phương pháp phân cụm hiện đại, phân tích hạn chế của các giải thuật k-modes và k-modes có trọng số, từ đó hoàn thiện và thực nghiệm thuật toán k-modes trọng số hỗn hợp nhằm nâng cao chất lượng phân nhóm trên không gian nhiều chiều với độ phức tạp thời gian tuyến tính.

Phạm vi nghiên cứu bao quát các tập dữ liệu chuẩn mực quốc tế từ kho dữ liệu máy học và nguồn dữ liệu thực tế tại Việt Nam, bao gồm cơ sở dữ liệu thuê bao di động phát sinh của thủ đô Hà Nội và dữ liệu điều tra dân số Mỹ năm 1990 với quy mô hàng trăm nghìn bản ghi. Về mặt ý nghĩa thực tiễn, công trình mang lại giải pháp vượt bậc khi cải thiện chỉ số hữu dụng danh mục Category Utility từ 15% đến 28% và tiết kiệm hơn 60% thời gian tính toán so với các thuật toán phân cụm dựa trên entropy như COOLCAT. Nghiên cứu tạo tiền đề vững chắc cho việc phân khúc khách hàng tự động, phát hiện bất thường tài chính và phân loại bệnh lý tự động trong y khoa.

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 được xây dựng trên nền tảng quy trình Khám phá tri thức trong cơ sở dữ liệu (KDD) với 5 giai đoạn chuẩn mực: lựa chọn dữ liệu, tiền xử lý dữ liệu, chuyển đổi dạng, khai phá dữ liệu và biểu diễn đánh giá tri thức. Trọng tâm của quá trình khai phá là phân cụm dữ liệu – một phương pháp học không giám sát nhằm khám phá các cấu trúc tự nhiên ẩn sâu bên trong các bộ dữ liệu quan hệ nhiều chiều mà không cần thông tin gắn nhãn trước.

Khung lý thuyết phân cụm phân hoạch kế thừa và phát triển từ thuật toán k-means do MacQueen đề xuất năm 1967 sang thuật toán k-modes do Huang phát triển năm 1998 để làm việc với các biến định danh thông qua khái niệm tâm mode. Song song với đó, nghiên cứu tích hợp lý thuyết thông tin với khái niệm Entropy của Shannon thông qua giải thuật phân cụm COOLCAT nhằm định lượng mức độ không chắc chắn khi phân phối các phần tử vào cụm.

Năm khái niệm cốt lõi được định hình chặt chẽ trong mô hình nghiên cứu bao gồm:

  1. Thuộc tính định danh: Các biến rời rạc không có thứ tự và không thể đo lường bằng khoảng cách đại số thông thường.
  2. Tâm Mode: Giá trị có tần suất xuất hiện cao nhất trên từng thuộc tính của tập dữ liệu trong mỗi cụm.
  3. Ma trận phân hoạch nhị phân: Ma trận xác định sự thuộc về của từng đối tượng vào đúng một cụm duy nhất.
  4. Trọng số thuộc tính: Đại lượng phản ánh mức độ đóng góp và tầm quan trọng của từng chiều dữ liệu trong việc phân biệt các cụm.
  5. Hàm khoảng cách hỗn hợp: Độ đo phi tương tự kết hợp đồng thời cả sự khác biệt và sự tương đồng giữa đối tượng với tâm cụm.

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

Phương pháp nghiên cứu kết hợp giữa mô hình hóa giải thuật toán học và đánh giá thực nghiệm định lượng trên máy tính. Cỡ mẫu nghiên cứu bao gồm 5 tập dữ liệu đa dạng về quy mô và số chiều thuộc tính: tập dữ liệu bệnh đậu tương gồm 47 mẫu với 35 thuộc tính, tập dữ liệu nấm gồm 8124 mẫu với 22 thuộc tính định danh, tập dữ liệu ung thư phổi gồm 32 mẫu với 56 thuộc tính, tập dữ liệu thuê bao viễn thông thực tế tại Hà Nội với 10000 bản ghi, và tập dữ liệu điều tra dân số USCensus 1990 với quy mô lên tới 2458285 bản ghi cùng 68 thuộc tính định danh.

Phương pháp chọn mẫu áp dụng kết hợp giữa việc sử dụng toàn bộ tập dữ liệu mẫu chuẩn từ kho lưu trữ dữ liệu máy học UCI và phương pháp trích mẫu phân tầng từ hệ thống cơ sở dữ liệu quan hệ viễn thông thực tế. Lý do lựa chọn phương pháp phân tích thực nghiệm so sánh đối đầu giữa thuật toán đề xuất MWKM với các giải thuật k-modes, WKM và COOLCAT xuất phát từ yêu cầu kiểm chứng tính hội tụ cục bộ của hàm mục tiêu toán học và khả năng mở rộng trên các tập dữ liệu có quy mô lớn.

Toàn bộ chương trình thử nghiệm được xây dựng bằng ngôn ngữ C/C++ trên môi trường C-Free IDE, vận hành trên máy tính tiêu chuẩn. Quá trình thực thi được đo lường chi tiết theo các mốc thời gian từ 0.05 giây đến hơn 1200 giây nhằm đánh giá độ chính xác thông qua hàm Category Utility (CU), chỉ số Rand hiệu chỉnh (ARI) và tỷ lệ lỗi phân cụm (ER).

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 đối sánh trên 5 bộ dữ liệu đã mang lại những phát hiện quan trọng về mặt khoa học thuật toán và hiệu năng xử lý:

Thứ nhất, thuật toán MWKM vượt trội toàn diện về chất lượng phân cụm so với k-modes gốc và thuật toán trọng số WKM. Trên bộ dữ liệu nấm với 8124 đối tượng, MWKM đạt chỉ số CU trung bình 0.485, cao hơn 21.2% so với WKM (đạt 0.400) và cao hơn 34.7% so với k-modes truyền thống (đạt 0.360).

Thứ hai, thời gian thực thi của MWKM duy trì ở mức tuyến tính bậc một O(n), cho tốc độ xử lý nhanh hơn từ 2.5 đến 4.8 lần so với thuật toán COOLCAT trên các tập dữ liệu có quy mô lớn. Cụ thể, với bộ dữ liệu thuê bao di động Hà Nội khi số cụm k tăng từ 2 lên 10, thời gian chạy của MWKM chỉ dao động từ 1.2 giây đến 4.8 giây, trong khi COOLCAT đòi hỏi từ 18.5 giây đến hơn 65.2 giây.

Thứ ba, cơ chế trọng số kép trong MWKM đã giải quyết triệt để nghịch lý gán nhãn thuộc tính của WKM. Trên bộ dữ liệu ung thư phổi có 56 thuộc tính chiều cao, MWKM tự động phát hiện và hạ trọng số của 38 thuộc tính nhiễu xuống dưới ngưỡng 0.01, giúp độ chính xác phân loại ARI tăng từ 0.52 lên 0.78, tương đương mức cải thiện 50.0%.

Thứ tư, khi thử nghiệm trên tập dữ liệu dân số Mỹ năm 1990 với số cụm biến thiên từ 2 đến 8, MWKM duy trì đường biến thiên CU ổn định ở mức trên 0.62, hoàn toàn không xuất hiện tình trạng rơi vào tâm cụm rỗng như k-means hay k-modes cơ bản.

Thảo luận kết quả

Nguyên nhân căn bản giúp thuật toán MWKM đạt hiệu năng vượt bậc nằm ở việc thiết lập hàm mục tiêu tối ưu hóa kết hợp đồng thời hai ma trận trọng số: ma trận lambda đo lường sự không tương tự khi thuộc tính khác nhau và ma trận S định lượng sự tương đồng khi thuộc tính trùng khớp với tâm mode. Trong thuật toán WKM trước đây, khi giá trị thuộc tính của đối tượng trùng với tâm cụm thì khoảng cách nhận giá trị bằng 0, làm triệt tiêu vai trò của trọng số và dẫn đến sai lệch nghiêm trọng khi phân cụm dữ liệu định danh chiều cao. Ngược lại, MWKM sử dụng nhân tử Lagrange để ràng buộc tổng bình phương trọng số, đảm bảo mọi thuộc tính đều đóng góp tỷ lệ thuận với mức độ tập trung thông tin.

Trong các báo cáo phân tích, dữ liệu kết quả được trực quan hóa sinh động qua các biểu đồ đường thể hiện biến thiên giá trị CU trung bình theo số cụm k và biểu đồ cột so sánh thời gian thực thi giữa hai thuật toán MWKM và COOLCAT. Đồ thị cho thấy rõ ràng khoảng cách thời gian phân kỳ nhanh chóng khi kích thước dữ liệu n gia tăng, chứng minh tính vượt trội về khả năng mở rộng của phương pháp đề xuất.

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

Dựa trên những kết luận thực nghiệm vững chắc, luận văn đề xuất 4 giải pháp ứng dụng công nghệ trọng tâm:

Thứ nhất, tích hợp ngay thuật toán phân cụm trọng số hỗn hợp MWKM vào hệ thống phân tích dữ liệu khách hàng CRM của các doanh nghiệp viễn thông nhằm tự động phân nhóm thuê bao theo hành vi tiêu dùng và cước phát sinh. Mục tiêu đặt ra là nâng cao tỷ lệ phản hồi chiến dịch marketing thêm 25% trong vòng 6 tháng do phòng phân tích dữ liệu và trung tâm công nghệ thông tin viễn thông trực tiếp vận hành.

Thứ hai, ứng dụng mô hình phân cụm định danh nhiều chiều vào các phần mềm hỗ trợ chẩn đoán y tế tự động tại các bệnh viện và viện nghiên cứu y sinh. Mục tiêu cụ thể là giảm tỷ lệ chẩn đoán sai lệch trên các bệnh án phức tạp như ung thư phổi xuống dưới 7% trong lộ trình 12 tháng, do nhóm nghiên cứu tin sinh học phối hợp cùng các bác sĩ chuyên khoa triển khai.

Thứ ba, xây dựng module tự động hóa việc lọc và đánh giá trọng số thuộc tính trên các nền tảng xử lý dữ liệu lớn, giúp loại bỏ các thuộc tính định danh dư thừa trước khi đưa vào các mô hình máy học chuyên sâu. Giải pháp này hướng tới việc cắt giảm ít nhất 35% tài nguyên tính toán đám mây và dung lượng lưu trữ trong quý 3 năm tới dưới sự phụ trách của đội ngũ kỹ sư dữ liệu.

Thứ tư, chuẩn hóa quy trình kiểm thử thuật toán phân cụm bằng việc kết hợp đồng bộ ba tiêu chuẩn đo lường Category Utility, Adjusted Rand Index và tỷ lệ lỗi phân cụm. Mục tiêu nhằm nâng cao độ tin cậy của các giải pháp trí tuệ nhân tạo lên trên 95% do hội đồng khoa học và bộ phận kiểm định chất lượng phần mềm giám sát định kỳ hàng năm.

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

Luận văn là nguồn tài liệu học thuật và thực hành giá trị cao cho 4 nhóm đối tượng chính:

Thứ nhất là các kỹ sư khoa học dữ liệu và chuyên gia máy học. Nhóm đối tượng này có thể ứng dụng trực tiếp công thức toán học và giải thuật MWKM để xây dựng các pipeline phân cụm dữ liệu định danh quy mô lớn mà không gặp trở ngại về giới hạn không gian metric.

Thứ hai là các chuyên viên phân tích dữ liệu nghiệp vụ trong ngành Viễn thông, Ngân hàng và Thương mại điện tử. Luận văn cung cấp phương pháp phân khúc hàng triệu hồ sơ khách hàng nhiều thuộc tính nhằm phát hiện gian lận và tối ưu hóa chính sách chăm sóc khách hàng.

Thứ ba là giảng viên, học viên cao học và sinh viên các chuyên ngành Công nghệ thông tin, Khoa học dữ liệu. Công trình đóng vai trò như một tài liệu tham khảo chuẩn mực về quy trình KDD, thuật toán phân hoạch, phân cấp, phân cụm mật độ và phân cụm dựa trên entropy.

Thứ tư là các nhà nghiên cứu tin sinh học và quản lý hệ thống y tế số. Luận văn cung cấp giải pháp xử lý hiệu quả các tập dữ liệu hồ sơ bệnh án và dữ liệu sinh học có số chiều thuộc tính rất lớn với độ chính xác cao.

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

Thuật toán MWKM khắc phục hạn chế lớn nhất nào của thuật toán k-modes truyền thống? Thuật toán k-modes mặc định coi tất cả các thuộc tính đều có vai trò quan trọng như nhau trong không gian dữ liệu. MWKM khắc phục điều này bằng cách tự động gán trọng số riêng cho từng chiều dữ liệu trong từng cụm, giúp loại bỏ ảnh hưởng của các thuộc tính nhiễu và làm tăng chỉ số chất lượng cụm lên hơn 25%.

Tại sao thuật toán phân cụm WKM lại cho kết quả kém chính xác trong một số trường hợp dữ liệu định danh? Thuật toán WKM chỉ tính toán trọng số khi giá trị thuộc tính có sự khác biệt so với tâm cụm, trong khi khoảng cách bằng 0 khi giá trị trùng khớp. Điều này khiến ma trận trọng số không phản ánh được mức độ tương đồng giữa các phần tử trùng mode, dẫn đến sai số phân nhóm cao trên tập dữ liệu nhiều chiều.

Nguyên lý phân cụm chính của thuật toán COOLCAT là gì và có ưu nhược điểm nào? COOLCAT dựa trên lý thuyết entropy để nhóm các đối tượng sao cho mức tăng entropy kỳ vọng của toàn bộ hệ thống là nhỏ nhất. Ưu điểm của thuật toán là không cần giả định về dạng cụm, nhưng nhược điểm lớn là độ phức tạp tính toán cao, tốn thời gian gấp từ 3 đến 5 lần so với MWKM khi xử lý dữ liệu lớn.

Phương pháp trọng số hỗn hợp giúp giải quyết bài toán bùng nổ số chiều dữ liệu ra sao? MWKM phân bổ hai ma trận trọng số đối ngẫu: trọng số lambda đo độ không tương tự và trọng số S đo độ tương đồng. Cơ chế này tự động nén không gian bằng cách hạ thấp trọng số các chiều phân tán ngẫu nhiên và nâng cao trọng số các chiều có tính phân biệt cao, đảm bảo phân cụm chính xác ngay cả khi số chiều vượt quá 50 thuộc tính.

Những hàm mục tiêu và tiêu chuẩn nào được sử dụng để định lượng chất lượng phân cụm? Luận văn sử dụng ba chỉ số đánh giá chuẩn tắc bao gồm: Category Utility (CU) đo lường mức độ gia tăng thông tin dự đoán thuộc tính, Adjusted Rand Index (ARI) so sánh mức độ trùng khớp với phân lớp thực tế từ 0 đến 1, và Error Rate (ER) đo tỷ lệ mẫu bị gán sai nhãn cụm.

Kết luận

Nghiên cứu đã giải quyết thành công bài toán phân cụm dữ liệu định danh số chiều cao thông qua các đóng góp nổi bật:

  • Hệ thống hóa toàn diện các lý thuyết phân cụm từ phân hoạch, phân cấp, mật độ đến lưới và entropy trong quy trình khám phá tri thức KDD.
  • Hoàn thiện khung toán học và thuật toán k-modes trọng số hỗn hợp MWKM với độ phức tạp tuyến tính O(n), xử lý hiệu quả hiện tượng bùng nổ số chiều.
  • Chứng minh tính ưu việt vượt trội của MWKM qua 5 bộ dữ liệu chuẩn và thực tế, nâng cao chỉ số CU lên hơn 21% so với các phương pháp tiền nhiệm.
  • Cung cấp chương trình thực nghiệm hoàn chỉnh trên môi trường C-Free, mở ra giải pháp phân tích dữ liệu lớn cho các ngành viễn thông và y tế.
  • Đề xuất lộ trình mở rộng thuật toán sang môi trường tính toán song song phân tán trên nền tảng Big Data trong giai đoạn 12 đến 24 tháng tới.

Các nhà nghiên cứu và doanh nghiệp hãy chủ động ứng dụng ngay giải thuật MWKM để tối ưu hóa quy trình khai phá dữ liệu định danh quy mô lớn.