Khai thác mẫu tương đồng phổ biến trên dữ liệu phân cấp

Tóm tắt

Khai phá mẫu phổ biến là một nhiệm vụ nền tảng trong lĩnh vực khai phá dữ liệu, tuy nhiên các thuật toán truyền thống thường sinh ra một số lượng mẫu kết quả sớ lượng lớn, trong đó chứa nhiều mẫu dư thừa và không mang lại giá trị thông tin cao. Để giải quyết vấn đề này, bài báo đề xuất một phương pháp tiếp cận nhiều giai đoạn lọc bỏ dư thừa để khai phá một tập hợp mẫu phổ biến cô đọng và ý nghĩa trên cơ sở dữ liệu (CSDL) phân cấp.

Trong nghiên cứu này đầu tiên chúng tôi trình bày thuật toán GFCP (Generalized Frequent Closed Pattern miner) để khai thác toàn bộ tập hợp các mẫu đóng phổ biến, giúp loại bỏ sự dư thừa về mặt cấu trúc. Sau đó, một giai đoạn lọc dựa trên độ tương đồng được áp dụng để loại bỏ các mẫu có nội dung tương tự nhau nhưng độ hỗ trợ thấp hơn. Đồng thời trong quá trình thực hiện chúng tôi cũng loại bỏ sự dư thừa về mặt ngữ nghĩa trong dữ liệu có hệ thống phân cấp, đảm bảo các mẫu con không cung cấp thông tin mới so với các mẫu cha tổng quát hơn sẽ bị loại bỏ. Nghiên cứu tiến hành khảo sát và so sánh hiệu quả của hai độ đo tương đồng phổ biến là Jaccard và Kulczynski và thử nghiệm trên hai cấu trúc dữ liệu Bitset và Set.

Các thực nghiệm trên nhiều bộ dữ liệu chuẩn đã chứng minh tính hiệu quả của phương pháp đề xuất trong việc giảm đáng kể số lượng mẫu đầu ra. Kết quả cũng cho thấy việc triển khai thuật toán sử dụng cấu trúc dữ liệu BitSet mang lại hiệu suất vượt trội về thời gian thực thi so với Set. Đồng thời, bài báo cũng cung cấp những phân tích sâu sắc về sự ảnh hưởng của việc lựa chọn độ đo tương đồng và các tham số đầu vào là độ phổ biến tối thiểu và độ tương đồng tối thiểu đến tập kết quả cuối cùng, qua đó khẳng định tính linh hoạt và hiệu quả của phương pháp trong việc khám phá các tri thức hữu ích từ dữ liệu.