Khai thác luật phân lớp kết hợp theo tập dự đoán

Bài viết giới thiệu các thuật toán khai thác luật phân lớp kết hợp, đặc biệt là thuật toán PCAR đề xuất tỷ lệ dự đoán, được chọn ưu tiên hơn độ tin cậy, độ hỗ trợ để đánh giá luật, tạo ra bộ phân lớp chính xác hơn. Tuy nhiên, việc dự đoán đơn luật ưu tiên chọn tỷ lệ dự đoán dẫn đến việc dự đoán sai ở nhiều tập dữ liệu mất cân bằng về lớp.
Nội dung trích xuất từ tài liệu:
Khai thác luật phân lớp kết hợp theo tập dự đoán TRƯỜNG ĐẠI HỌC SÀI GÒN SAIGON UNIVERSITY TẠP CHÍ KHOA HỌC SCIENTIFIC JOURNAL ĐẠI HỌC SÀI GÒN OF SAIGON UNIVERSITY Số 77 (06/2021) No. 77 (06/2021) Email: tcdhsg@sgu.edu.vn ; Website: http://sj.sgu.edu.vn/ KHAI THÁC LUẬT PHÂN LỚP KẾT HỢP THEO TẬP DỰ ĐOÁN Mining class association rule based on predictive collection ThS. Nguyễn Anh Tú Trường Đại học Ngoại ngữ – Tin học TP.HCM TÓM TẮT Bài viết giới thiệu các thuật toán khai thác luật phân lớp kết hợp, đặc biệt là thuật toán PCAR đề xuất tỷ lệ dự đoán, được chọn ưu tiên hơn độ tin cậy, độ hỗ trợ… để đánh giá luật, tạo ra bộ phân lớp chính xác hơn. Tuy nhiên, việc dự đoán đơn luật ưu tiên chọn tỷ lệ dự đoán dẫn đến việc dự đoán sai ở nhiều tập dữ liệu mất cân bằng về lớp. Do đó, bài viết đề xuất thuật toán DPCAR để cải tiến giai đoạn dự đoán bằng cách ưu tiên chọn nhóm cao nhất về số luật phủ; về trung bình điều hòa của tỷ lệ dự đoán và độ tin cậy; và về độ hỗ trợ của luật trong bộ phân lớp. Kết quả thực nghiệm cho thấy thuật toán đề xuất đã tăng khoảng 1.31% và 1.93% khi so sánh với hai phiên bản của thuật toán PCAR cũng như vượt trội so với các thuật toán trước đó về độ chính xác trên 14 tập dữ liệu trong tập UCI. Từ khóa: phân lớp, luật phân lớp kết hợp, tập dự đoán, khai thác dữ liệu ABSTRACT This paper will present the algorithms for mining the class association rule, especially an algorithm named PCAR that has proposed a novel measure, known as the predictive rate, which has priority over confidence, support, etc., in the rule evaluation, has built the classifier with high accuracy. However, by using single accurate rule prediction, many cases were incorrectly covered by the rule which higher predictive rate, especially in imbalanced real datasets. Therefore, this paper proposes the DPCAR algorithm to improve PCAR algorithm at the prediction phase by selecting the class with priority dominant class groups; the highest harmonic mean ratio between predictive rate and confidence; and the highest support of rule in the classifier. The experimental results show that the proposed algorithm has increased by 1.31% and 1.93% compared to two versions of PCAR algorithm as well as outperformed the previous algorithms over 14 data sets of UCI Repository. Keywords: classification, class association rules, predictive collection, data mining 1. Giới thiệu cho dữ liệu mới vào trong một những lớp Khai thác luật kết hợp và phân lớp là đã được xác định trước trong dữ liệu giao những bài toán quan trọng được nghiên dịch. Từ những định nghĩa trên, các nhà cứu hiện nay trong khai thác dữ liệu. Trong nghiên cứu đã đề xuất phương pháp kết khi khai thác luật kết hợp là quá trình đi hợp hai kỹ thuật đó lại để tạo ra một tìm mối liên kết giữa các hạng mục thì bài phương pháp mới gọi là phân lớp kết hợp. toán phân lớp có nhiệm vụ xây dựng ra bộ Phân lớp kết hợp (Associative phân lớp từ dữ liệu huấn luyện để phân lớp Classification - AC) là một phương pháp Email: tu.na@huflit.edu.vn 26 NGUYỄN ANH TÚ TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GÒN kết hợp việc khai thác luật kết hợp để xây trong tập kiểm thử, CMAR chia các luật có dựng bộ phân lớp hay mô hình phân lớp thể dự đoán được thành từng nhóm theo (classifier) và dự đoán các mẫu chưa biết thuộc tính lớp rồi tính giá trị chi bình trước lớp trong bài toán phân lớp dữ liệu. phương trọng số (Weighted Chi-square - Đầu tiên, các luật kết hợp được tạo ra bằng weighted2) cho mỗi nhóm và chọn thuộc việc sử dụng các thuật toán khai thác tập tính lớp của nhóm có giá trị weighted2 lớn phổ biến để sinh luật, có thể kể đến như nhất để dự đoán cho mẫu kiểm thử. Thuật Apriori [1], Eclat [2], FP-growth [3] v.v. toán CMAR đã đem lại hiệu quả cao trong Sau đó, các luật được sinh ra dưới dạng việc tăng độ chính xác của tập luật CARs luật phân lớp kết hợp (Class Association khai thác được. Tiếp sau đó, Thabtah và Rules - CARs) được giữ lại để đánh giá. các cộng sự đã đề xuất thuật toán MMAC Luật phân lớp kết hợp là một dạng đặt biệt (Multi-class, Multi-label Associative của luật kết hợp mà vế trái (hay tiền đề) là Classification) [8] để khai thác luật phân các hạng mục và vế phải (hay hệ quả) là lớp kết hợp đa lớp, đa nhãn vào năm 2004. thuộc tính lớp. Trong giai đoạn đánh giá, Thuật toán MMAC bao gồm ba giai đoạn: AC sử dụng các độ đo như độ tin cậy đầu tiên, thuật toán sinh tập luật CARs thỏa (confidence - conf), độ hỗ trợ (support - ngưỡng tin cậy tối thiểu (minimum supp), độ dài tiền đề (cardinality) hay tần confidence - minconf) và xếp hạng, cắt tỉa suất xuất hiện từng lớp (frequency)… của để bỏ các luật dư thừa; sau đó, thuật toán luật để xếp hạng, cắt tỉa luật dư thừa rồi dùng đệ quy để khai thác các dòng dữ liệu xây dựng bộ phân lớp phục vụ cho quá còn lại của tập dữ liệu huấn luyện sau khi trình dự đoán. đã qua bước cắt tỉa ở giai đoạn đầu, sinh ra Khai thác luật phân lớp kết hợp được một tập luật mới rồi gộp với tập luật đã đề xuất bởi Liu và các cộng sự vào năm khai thác được ở giai đoạn đầu để tạo ra bộ 1998 [4] bằng việc kết hợp hai kỹ thuật phâ ...