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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

31
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ân lớp có tính đa lớp, phục vụ cho giai trong khai thác dữ liệu là khai thác luật kết đoạn dự đoán lớp cho các dòng ở tập dữ hợp và phân lớp; thuật toán CBA cũng liệu kiểm thử. Với việc thực hiện các bước được đề xuất trong công trình này. Thuật ở giai đoạn 2, thuật toán MMAC đã cải toán bao gồm hai giai đoạn chính: giai thiện được độ chính xác với các trường hợp đoạn sinh luật (áp dụng thuật toán CBA- dự đoán các luật đa nhãn lớp so với các RG) và giai đoạn xây dựng bộ phân lớp (áp thuật toán trước đó. Vào năm 2005, chính dụng thuật toán CBA-CB) đã chứng minh nhóm tác giả trên lại đề xuất một thuật toán được sự cải thiện về độ chính xác so với mới gọi là phân lớp luật kết hợp đa lớp các thuật toán phân lớp dựa trên luật trước (Multi-class Classification based on như cây quyết định [5], ILA [6] v.v. Vào Association Rule - MCAR) [9] áp dụng kỹ năm 2001, W. Li và các cộng sự đã đề xuất thuật tìm tập phổ biến hiệu quả để tạo tập thuật toán phân lớp dựa trên đa luật luật CARs và hướng tiếp cận đánh giá luật (Classification based on Multiple mới để tạo bộ phân lớp có độ tin cậy và độ Association Rules - CMAR) [7], sử dụng chính xác cao, phục vụ cho quá trình dự cây FP (Frequent Pattern Tree) để nén dữ đoán lớp chưa biết nhãn. liệu và dùng phép chiếu trên cây để tìm ra Một trong số những điểm còn hạn chế luật phân lớp. Ở giai đoạn dự đoán luật của các thuật toán khai thác luật phân lớp 27
SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY No. 77 (06/2021) kết hợp kể trên là phụ thuộc chủ yếu vào huấn luyện sẽ được chọn để dự đoán. việc chọn ngưỡng hỗ trợ, ngưỡng tin cậy 2. Nội dung nghiên cứu tối thiểu. Một ngưỡng quá cao sẽ dẫn đến 2.1. Sơ bộ về khai thác luật phân lớp các lớp chứa ít mẫu sẽ không phổ biến và kết hợp (Class association rule mining) vì vậy không luật nào của lớp này được Khai thác luật phân lớp kết hợp là bài nằm trong bộ phân lớp; trong khi một toán tìm ra một tập con của các luật kết ngưỡng quá thấp sẽ dẫn đến việc bộ phân hợp có trong cơ sở dữ liệu mà mỗi luật kết lớp sẽ chứa số lượng lớn luật đa lớp và cả hợp trong tập con này chứa vế phải là giá hai đều ảnh hưởng đến quá trình dự đoán trị của thuộc tính lớp. Bài toán được phát lớp. Vào năm 2017, nhóm tác giả Song và biểu như sau: Lee đề xuất một thuật toán đưa ra một tiêu chí mới gọi là tỷ lệ dự đoán (predictive rate Cho tập dữ liệu huấn luyện T với m - pr), ưu tiên hơn độ tin cậy, độ hỗ trợ… để thuộc tính A1, A2,…, Am và 𝐶 là danh sách đánh giá luật, xây dựng bộ phân lớp dự thuộc tính lớp. |𝑇| là lực lượng của T. đoán chính xác hơn các hướng tiếp cận Định nghĩa 1: AttributeValueSet là tập trước, đó chính là thuật toán PCAR các thuộc tính và giá trị của nó, ký hiệu < (Predictability-based Collective Class (𝐴𝑖1 , 𝑎𝑖1 ), … , (𝐴𝑖𝑚 , 𝑎𝑖𝑚 ) >. Association Rule mining) [10]. Định nghĩa 2: Một luật phân lớp kết Tuy nhiên, ở giai đoạn dự đoán luật, hợp r là một phép kéo theo có dạng Song và Lee [10] chọn tỷ lệ dự đoán làm 𝐴𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒𝑉𝑎𝑙𝑢𝑒𝑆𝑒𝑡 → 𝑐 trong đó, 𝑐 ∈ 𝐶 tiêu chí ưu tiên hàng đầu dẫn đến nhiều là một nhãn lớp. trường hợp bị dự đoán sai khi các luật có tỷ Định nghĩa 3: Số lần xuất hiện của một lệ dự đoán thấp hơn lại có thuộc tính lớp luật r trong T, ký hiệu 𝑎𝑐𝑡𝑜𝑐𝑐𝑟𝑇 (𝑟), là số đúng với mẫu trong tập dữ liệu kiểm thử, đặc biệt đối với trường hợp tập dữ liệu bị dòng trong T chứa AttributeValueSet của r. mất cân bằng về lớp. Do vậy, bài viết này Định nghĩa 4: Số hỗ trợ của một luật r đề xuất một hướng cải tiến để khắc phục trong T, ký hiệu 𝑠𝑢𝑝𝑝𝑐𝑜𝑢𝑛𝑡𝑇 (𝑟), là số nhược điểm trên. Giải pháp của bài viết dòng trong T chứa AttributeValueSet của r này tập trung ở giai đoạn dự đoán, khi một và thuộc tính lớp của C giống với thuộc mẫu mới chưa biết trước lớp của tập kiểm tính 𝑐 của r. thử được đưa vào dự đoán, thuật toán sẽ Định nghĩa 5: Một luật r vượt qua chọn theo thứ tự lớp của nhóm có số lượng ngưỡng hỗ trợ tối thiểu (minsupp) khi luật phủ được mẫu kiểm thử nhiều nhất 𝑠𝑢𝑝𝑝𝑐𝑜𝑢𝑛𝑡𝑇 (𝑟) |𝑇| ≥ 𝑚𝑖𝑛𝑠𝑢𝑝𝑝. (Dominant Class - DC), nhóm có giá trị trung bình cộng của trung bình điều hòa Định nghĩa 6: Một luật r vượt qua HM (Average Harmonic Mean - AHM) ngưỡng tin cậy tối thiểu (minconf) khi giữa tỷ lệ dự đoán và độ tin cậy cao nhất, 𝑠𝑢𝑝𝑝𝑐𝑜𝑢𝑛𝑡𝑇 (𝑟) ≥ 𝑚𝑖𝑛𝑐𝑜𝑛𝑓. nhóm có giá trị trung bình độ hỗ trợ 𝑎𝑐𝑡𝑜𝑐𝑐𝑟𝑇 (𝑟) (Average Support - AS) cao nhất để dự Ví dụ 1: Cho T là cơ sở dữ liệu giao đoán. Trường hợp không có luật nào phủ dịch như Bảng 1 với 6 dòng dữ liệu |𝑇|=6, được mẫu, lớp mặc định (default class) – là các thuộc tính {X, Y, Z}, thuộc tính lớp là lớp xuất hiện nhiều nhất trong tập dữ liệu thuộc tính quyết định Lớp = {Yes, No}. 28
NGUYỄN ANH TÚ TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GÒN Bảng 1. Dữ liệu giao dịch T ví dụ 1 hai tập con: inner training set (TR i ) và OID X Y Z Lớp inner testing set (TEi ) theo tỷ lệ tương ứng 1 x1 y1 z1 Yes (k-1):1. Ở mỗi lần chạy, thuật toán tính tỷ lệ dự đoán của mỗi luật trong RS theo công 2 x1 y2 z1 No thức: 3 x2 y2 z1 No 𝑠𝑢𝑝𝑝𝑐𝑜𝑢𝑛𝑡𝑇𝐸𝑖 (𝑟𝑗 ) 𝑝̂ (𝑗|𝑖 ) = |𝑇𝐸𝑖 | (1) 4 x3 y1 z2 No Trong đó, i là lần chạy vòng lặp trong 5 x3 y3 z1 No k và j là lần duyệt từng luật trong RS. Sau 6 x1 y2 z2 Yes đó, RS sẽ được xếp hạng theo thứ tự ưu Xét luật r: (𝑋, 𝑥1 ) → 𝑌𝑒𝑠 với A = tiên như Hình 1 để sử dụng cho giai đoạn (𝑋, 𝑥1 ) và c = Yes, ta có: cắt tỉa luật, xây dựng bộ phân lớp RSi ở lần 𝑎𝑐𝑡𝑜𝑐𝑐𝑟𝑇 (𝑟) = 3; 𝑠𝑢𝑝𝑝𝑐𝑜𝑢𝑛𝑡𝑇 (𝑟) = 2; chạy thứ i. 𝑠𝑢𝑝𝑝 (𝑟) 2 𝑐𝑜𝑛𝑓𝑇 (𝑟) = 𝑎𝑐𝑡𝑜𝑐𝑐𝑟𝑇 = 3. Sau k lần chạy, các RSi sẽ được hợp 𝑇 (𝑟) nhất lại thành bộ phân lớp chung URS, 2.2. Thuật toán khai thác luật phân trong quá trình hợp nhất, nếu một luật xuất lớp kết hợp dựa trên tập dự đoán PCAR hiện nhiều lần ở các bộ phân lớp RSi, thuật Phương pháp đề xuất của bài viết này là một phiên bản cải tiến của thuật toán toán sẽ tính trung bình cộng của tỷ lệ dự đoán cho luật đó theo công thức: PCAR, vì vậy, giai đoạn sinh luật và đánh 1 giá luật để xây dựng bộ phân lớp hầu như 𝑝̂𝑗 = ∑𝑘𝑖=1 𝑝̂ (𝑗|𝑖 ) (2) 𝑘 tương đồng với thuật toán ban đầu. Sau cùng, URS đã được xếp hạng được Trong nghiên cứu của mình, Song và dùng để dự đoán luật của tập dữ liệu kiểm Lee [10] áp dụng thuật toán Eclat [2] (với thử. Với một mẫu t trong tập dữ liệu kiểm minsupp = 0.05 và minconf = 0.4) để khai thử chưa biết lớp, thuật toán sẽ tìm ra luật thác các luật kết hợp rồi từ đó chọn ra các đầu tiên trong tập URS có thể phủ được t và CARs tạo thành tập luật (RuleSet - RS). chọn lớp của luật đó để dự đoán cho mẫu t. Sau đó, thuật toán áp dụng kỹ thuật đánh Nếu không có luật nào trong URS phủ được giá chéo (cross-validation) chạy k vòng lặp, t, lớp mặc định sẽ được chọn để dự đoán cho mỗi lần chia tập dữ liệu huấn luyện thành mẫu t. Hình 1. Thứ tự xếp hạng luật của thuật toán PCAR 29
SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY No. 77 (06/2021) 3. Đề xuất thuật toán DPCAR cải thường gặp phải vấn đề giới hạn ngưỡng tiến giai đoạn dự đoán luật minsupp và minconf. Thông thường, ở giai 3.1. Ý tưởng chính đoạn sinh luật hoặc cắt tỉa luật dư thừa, các thuật toán này chỉ chọn những luật có giá Như đã trình bày ở trên, nhóm tác giả trị 𝑠𝑢𝑝𝑝 ≥ 𝑚𝑖𝑛𝑠𝑢𝑝𝑝 và 𝑐𝑜𝑛𝑓 ≥ Song và Lee [10] dựa vào tỷ lệ dự đoán 𝑚𝑖𝑛𝑐𝑜𝑛𝑓 dẫn đến nhiều luật có ích bị loại làm tiêu chí ưu tiên hàng đầu trong giai bỏ. Lấy ví dụ, với minsupp = 0.2 và đoạn dự đoán luật dẫn đến nhiều trường minconf = 0.6 thì một luật với supp = 0.6 hợp bị dự đoán sai. Do đó, bài viết này đề và conf = 0.5 sẽ không được sinh ra trong xuất thuật toán DPCAR để khắc phục giai đoạn sinh luật hoặc giữ lại ở giai đoạn nhược điểm trên. tỉa luật. Bằng việc áp dụng cách tính trung Với mỗi mẫu t cần dự đoán lớp trong bình điều hòa giữa độ tin cậy và độ phổ dữ liệu kiểm thử, thuật toán sẽ đếm số biến, vấn đề trên sẽ được giải quyết. Tương lượng các luật phủ được t trong tập URS tự như trên, bài viết này áp dụng cách tính khai thác được từ thuật toán PCAR rồi chia trung bình điều hòa giữa tỷ lệ dự đoán và nhóm các luật đó theo lớp, sau đó lớp ở độ phổ biến để khắc phục vấn đề mà thuật nhóm có số lượng luật cao nhất gọi là toán PCAR gặp phải đó là chỉ chọn các luật dominant class sẽ được chọn để dự đoán trong URS với tỷ lệ dự đoán từ cao xuống lớp cho t. Phương pháp này giúp khắc phục thấp để dự đoán trước rồi mới xét đến độ được việc các luật được xếp hạng cao hơn phổ biến khi các luật có cùng tỷ lệ dự đoán. nhưng dự đoán sai mẫu thử, đặc biệt là các Xét ví dụ: luật r1: a  c1 có pr = 0.8, conf luật mà vế trái có ít thuộc tính thường có tỷ = 0.5 và luật r2: a  c2 có pr = 0.6, conf = lệ dự đoán, độ tin cậy, độ hỗ trợ… cao hơn 0.65 trong URS; mẫu t cần dự đoán có vế nên được xếp trên các luật khác ở bước xếp trái là a (thuộc tính lớp đúng là c2). Vì luật hạng luật. r2 có giá trị HM là 0.624 lớn hơn giá trị Trong trường hợp có hai nhóm HM của luật r1 là 0.615 nên ta chọn lớp c2 dominant class trở lên, thuật toán sẽ tính để dự đoán cho mẫu t (nếu áp dụng trung giá trị trung bình điều hòa (HM) của từng bình cộng giữa pr và conf trong trường hợp luật ở mỗi nhóm theo công thức (3) rồi này thì sẽ chọn lớp của luật r1 dẫn đến dự chọn lớp ở nhóm có trung bình cộng HM đoán sai). (AHM) cao nhất để dự đoán. Nếu giá trị AHM của các nhóm tiếp tục 2∗𝑝𝑟∗𝑐𝑜𝑛𝑓 𝐻𝑀 = (3) bằng nhau, thuật toán sẽ tính AS là trung 𝑝𝑟+𝑐𝑜𝑛𝑓 bình cộng độ hỗ trợ của mỗi nhóm rồi chọn Trong đó, HM là trung bình điều hòa lớp của nhóm có giá trị AS cao nhất để dự giữa tỷ lệ dự đoán và độ tin cậy. Về mặt lý đoán, trường hợp còn lại thì chọn lớp của thuyết, trung bình điều hòa thường được nhóm ngẫu nhiên để dự đoán. Nếu không dùng để tính giá trị trung bình của các biến có luật nào của URS phủ được mẫu t, lớp được biểu diễn dưới dạng tỷ lệ hoặc giá trị mặc định sẽ được chọn để dự đoán cho t. biến có trọng số thay vì sử dụng các giá trị 3.2. Thuật toán trung bình khác. Nhiều thuật toán về AC  Đầu vào: Bộ phân lớp chung (URS), 30
NGUYỄN ANH TÚ TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GÒN Tập dữ liệu kiểm thử (TS) lớp (B, R, L) và chia ngẫu nhiên thành tập  Đầu ra: lớp dự đoán dữ liệu huấn luyện (gồm 562 giao dịch) và  Chi tiết thuật toán: tập dữ liệu kiểm thử (63 giao dịch) (bảng 1 prs = ∅ ; // tập chứa các luật phủ 2). Sau khi chạy thuật toán PCAR [13] trên được mẫu của TS tập dữ liệu huấn luyện (k = 5, minsupp = 2 for each i in TS 0.05, minconf = 0.4) thu được URS gồm 20 3 for each r in URS luật như bảng 3. 4 if r phủ i  Xét trường hợp dữ liệu kiểm thử 5 prs = prs + r; TID 1: 2 4 3 4 => R. 6 end if Thuật toán PCAR sử dụng luật UID 7 end for 11: NA 4 NA NA => L trong URS (với NA là giá trị rỗng ở cột thuộc tính, luật UID 11 8 if prs ≠ ∅ Chia prs thành các nhóm lớp; là luật đầu tiên tìm được trong tập URS phủ 9 Đếm số lượng luật mỗi nhóm; được TID 1) để dự đoán dẫn đến dự đoán 10 sai. 11 Tính HM mỗi luật theo (3); Thuật toán DPCAR xác định được các 12 Tính trung bình cộng HM: 𝐴𝐻𝑀 = 𝐻𝑀1 +⋯+𝐻𝑀𝑛 luật UID 11 (lớp L), UID 13 (lớp R), UID 15 ; 𝑛 (lớp R) có thể dự đoán được; nhóm lớp R có 13 if prs chỉ có một nhóm lớp số lượng là 2 trong khi nhóm lớp L có số 14 Chọn lớp nhóm này dự đoán; lượng là 1 nên chọn nhóm lớp R để dự đoán, 15 else suy ra dự đoán đúng. 16 if nhóm có AHM lớn nhất = 1  Xét trường hợp dữ liệu kiểm thử 17 Chọn lớp nhóm này dự đoán; TID 13: 1 5 4 1 => L. 18 else Thuật toán PCAR sử dụng luật UID 3: 19 if nhóm có AS lớn nhất = 1 NA NA NA => R để dự đoán dẫn đến 20 Chọn lớp nhóm này dự đoán; dự đoán sai. 21 else Thuật toán DPCAR xác định được các 22 Chọn lớp ngẫu nhiên giữa các luật UID 3 (lớp R), UID 4 (lớp L), UID 6 nhóm để dự đoán; (lớp L), UID 9 (lớp R) có thể dự đoán 23 end if được; xét số lượng thì cả hai nhóm đều có 24 end if hai luật nên ta tính HM của hai nhóm này: 25 end if Nhóm R: 26 else /*không có r nào phủ i*/ Luật UID 3: 27 Chọn lớp mặc định dự đoán; (2×0.7741×0.7838) 𝐻𝑀 = (0.7741+0.7838) = 0.77892 28 end if Luật UID 9: 29 end for (2×0.4985×0.6207) 𝐻𝑀 = (0.4985+0.6207) = 0.55293 3.3. Ví dụ minh họa Chọn tập dữ liệu Balance được lấy từ Nhóm L: bộ dữ liệu chuẩn UCI, gồm 625 giao dịch, Luật UID 4: (2×0.7424×0.7477) 4 thuộc tính (Left Weight, Left Distance, 𝐻𝑀 = (0.7424+0.7477) = 0.745 Right Weight, Right Distance) phân vào 3 31
SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY No. 77 (06/2021) Luật UID 6: 24 4 4 3 1 L (2×0.7014×0.7043) 25 5 1 2 4 R 𝐻𝑀 = (0.7014+0.7043) = 0.7028 26 1 4 2 1 L Vì AHM (L) = 0.7239 > AHM(R) = 27 2 4 2 1 L 0.6659 nên chọn lớp L để dự đoán, suy ra 28 1 3 1 5 R dự đoán đúng. 29 1 5 1 1 L Tương tự như hai trường hợp trên, 30 3 1 3 3 R trong khi thuật toán PCAR dự đoán đúng 31 5 1 3 1 L được 49/63 (77.78%) mẫu thì thuật toán 32 3 5 1 2 L DPCAR dự đoán đúng tổng cộng 60/63 33 5 3 2 1 L (95.23%) mẫu bao gồm 37 mẫu đúng 34 2 4 4 4 R dùng Dominant Class, 14 mẫu đúng dùng 35 1 1 1 2 R Average Harmonic Mean và 9 mẫu đúng 36 3 5 2 1 L dùng luật đầu tiên tìm được, tăng 17.45% 37 1 5 5 2 R so với thuật toán PCAR. 38 2 5 5 5 R Bảng 2. Dữ liệu kiểm thử từ Balance 39 4 1 4 4 R 40 2 4 5 1 L TID LW LD RW RD Lớp 41 5 4 3 2 L 1 2 4 3 4 R 42 1 2 4 4 R 2 5 2 4 1 L 43 4 4 5 1 L 3 3 3 2 5 R 44 4 4 5 2 L 4 5 2 1 3 L 45 2 4 1 1 L 5 2 4 5 3 R 46 5 5 5 4 L 6 5 2 2 3 L 47 4 4 5 3 L 7 3 1 2 2 R 48 5 4 3 4 L 8 1 2 1 3 R 49 4 3 1 3 L 9 4 3 2 2 L 50 1 1 5 5 R 10 2 2 4 3 R 51 3 1 2 1 L 11 1 2 1 4 R 52 1 3 5 3 R 12 1 2 5 2 R 53 4 2 4 1 L 13 1 5 4 1 L 54 3 4 5 4 R 14 2 3 2 4 R 55 4 5 5 5 R 15 2 2 1 3 L 56 5 1 4 4 R 16 2 4 3 1 L 57 1 2 3 3 R 17 3 2 1 1 L 58 2 4 5 2 R 18 4 3 1 4 L 59 2 1 3 2 R 19 2 1 1 4 R 60 3 5 1 4 L 20 3 2 2 2 L 61 4 5 4 3 L 21 4 2 1 3 L 62 5 3 5 2 L 22 3 4 5 1 L 63 1 2 2 4 R 23 3 4 3 1 L 32
NGUYỄN ANH TÚ TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GÒN Bảng 3. Tập URS khai thác bằng PCAR, k = 5, minsupp = 0.05, minconf = 0.4 Số phần Tần suất xuất UID LW LD RW RD Lớp PR Conf Supp tử vế trái hiện lớp 1 NA NA 1 NA L 0.8033 0.8 0.1566 1 50 2 NA 1 NA NA R 0.7825 0.7807 0.1584 1 50 3 1 NA NA NA R 0.7741 0.7838 0.1548 1 50 4 NA NA NA 1 L 0.7424 0.7477 0.1423 1 50 5 NA NA 5 NA R 0.7163 0.7248 0.1406 1 50 6 NA 5 NA NA L 0.7014 0.7043 0.1441 1 50 7 NA NA NA 5 R 0.6856 0.6917 0.1477 1 50 8 5 NA NA NA L 0.5432 0.693 0.1406 1 50 9 NA NA 4 NA R 0.4985 0.6207 0.1281 1 50 10 NA NA NA 2 L 0.413 0.5752 0.1157 1 46 11 NA 4 NA NA L 0.4092 0.5981 0.1139 1 50 12 4 NA NA NA L 0.3884 0.5929 0.1192 1 50 13 NA NA NA 4 R 0.3802 0.6 0.1174 1 56 14 NA 2 NA NA R 0.3721 0.5818 0.1139 1 50 15 2 NA NA NA R 0.2526 0.5586 0.1103 1 55 16 NA NA 2 NA L 0.2414 0.5625 0.1121 1 48 17 NA 3 NA NA L 0.1625 0.5 0.1032 1 50 18 3 NA NA NA L 0.13 0.4867 0.0979 1 48 19 NA NA NA 3 L 0.1154 0.4107 0.0819 1 50 20 NA NA NA 3 R 0.1077 0.5089 0.1014 1 47 4. Cài đặt thực nghiệm và kết quả này còn chạy thử nghiệm trên cùng các tập 4.1. Môi trường và dữ liệu thực nghiệm dữ liệu bằng các thuật toán C4.5 [5], Nghiên cứu này cài đặt thực nghiệm RIPPER [12], CBA [4], MCAR [9] để so trên 14 tập dữ liệu chuẩn UCI [11] như sánh. Các thuật toán C4.5, RIPPER, CBA bảng 4. Các thí nghiệm được tiến hành trên được chạy bằng phần mềm WEKA [13]; máy tính cá nhân hệ điều hành Windows MCAR, PCAR, PCAR2 (là một phiên bản 10 (64-bit), cấu hình @Intel CPU core i7 của PCAR nhưng ở giai đoạn tính tỷ lệ dự 2.60 GHz và RAM 8GB. Bên cạnh việc so đoán và xếp hạng, nhóm tác giả chỉ sử sánh với thuật toán PCAR [10] để chứng dụng inner testing set thay vì sử dụng thêm minh sự cải thiện độ chính xác, nghiên cứu inner training set như PCAR) chạy bằng 33
SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY No. 77 (06/2021) ngôn ngữ R do nhóm tác giả Song và Lee trong mô hình (ví dụ: ID, tên v.v.) sẽ bị lọc [10] cung cấp và thuật toán đề xuất bỏ, các thuộc tính có giá trị liên tục sẽ DPCAR chạy trên Java. Bài viết này vẫn được rời rạc hóa; ở giai đoạn sinh luật bảo đảm thiết lập các cài đặt giống như các vẫn chọn minsupp = 0.05, minconf = 0.4 hướng tiếp cận trước, ở giai đoạn tiền xử lý và k = 5 ở giai đoạn tính tỷ lệ dự đoán và dữ liệu, những thuộc tính không có ý nghĩa đánh giá luật. Bảng 4. 14 tập dữ liệu mẫu UCI trong thực nghiệm Tập dữ liệu Số giao dịch Số thuộc tính Số lớp Phân bố lớp (%) Balance 625 4 3 (7.84, 46.08, 46.08) Balloon 20 4 2 (60, 40) Breast Cancer Coimbra 116 10 2 (44.83, 55.17) (19.81, 14.15, 16.98, Breast Tissue 106 9 6 15.09, 13.21, 20.76) Crx 690 9 2 (44.49, 55.51) Cryotherapy 90 7 2 (46.47, 53.33) (32.71, 35.52, 7.94, 6.07, Glass 214 10 7 4.21, 13.55) Iris 150 4 3 (33.33, 33.33, 33.33) (10.15, 10.41, 9.96, 8.44, Led7 3200 7 10 10.5, 10.47, 10.66, 9.5, 10.22, 9.69) Lenses 24 4 3 (16.67, 20.83, 62.5) Pima 768 8 2 (65.1, 34.9) Seeds 210 7 3 (33.33, 33.33, 33.33) Thyroid-new 215 5 3 (69.77, 16.28, 13.95) Wine 178 13 3 (33.14, 39.89, 26.97) 4.2. Kết quả độ chính xác so với các thuật toán được so Kết quả thực nghiệm ở bảng 5 thể sánh. Tỷ lệ thắng - thua - hòa (won – loss hiện độ chính xác khi chạy các thuật toán - tied) của DPCAR so với C4.5, RIPPER, sử dụng kỹ thuật kiểm tra chéo (k-fold CBA, MCAR và PCAR lần lượt là 9-4-1, Cross Validation) với k = 10 trên 14 tập 10-3-1, 8-4-2, 8-4-2, và 8-3-3; của dữ liệu mẫu, các giá trị in đậm thể hiện độ DPCAR2 so với C4.5, RIPPER, CBA, chính xác cao nhất của thuật toán tương MCAR và PCAR2 là 9-4-1, 12-1-1, 8-4-2, ứng cho từng tập dữ liệu. Nhìn chung, 8-3-3, và 9-2-3. Xét trên 14 tập dữ liệu, độ thuật toán đề xuất của bài viết vượt trội về chính xác trung bình của thuật toán 34
NGUYỄN ANH TÚ TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GÒN DPCAR và DPCAR2 đã cải thiện khoảng các tập dữ liệu có sự chênh lệch trong 1.31% và 1.93% tương ứng so với thuật phân bố lớp như Balance, Glass, Lenses, toán PCAR và PCAR2, đặc biệt đối với Pima, Thydroid-new, Wine. Bảng 5. Độ chính xác (%) của C4.5, RIPPER, CBA, MCAR, PCAR, PCAR2, DPCAR, DPCAR2 áp dụng kỹ thuật 10-fold cross validation Tập dữ liệu C4.5 RIPPER CBA MCAR PCAR DPCAR PCAR2 DPCAR2 Balance 76.64 80.32 71.52 76.31 77.28 87.52 77.91 87.66 Balloon 100 100 100 100 100 100 100 100 Breast Tissue 69.81 63.21 69.81 64.27 68.91 73.55 72.64 69.91 Breast Cancer Coimbra 68.10 70.69 72.41 71.67 72.50 73.41 65.46 73.03 Crx 86.09 85.36 85.80 85.07 85.22 83.19 84.93 85.65 Cryotherapy 85.56 83.33 91.11 91.11 91.11 91.11 90.00 91.11 Glass 66.82 66.82 68.22 68.18 64.31 68.03 65.45 67.27 Iris 96.00 94.67 94.00 92.67 94.00 93.33 92.67 92.67 Led7 73.18 69.35 71.78 71.78 73.50 72.97 72.91 72.41 Lenses 83.33 75.00 66.67 68.33 70.00 70.00 71.67 76.67 Pima 73.83 75.13 77.47 77.74 75.39 75.40 73.94 76.69 Seed 90.48 91.43 92.38 90.95 92.38 92.86 93.33 93.33 Thyroid-new 92.09 92.56 93.02 95.37 94.00 94.94 92.99 93.94 Wine 93.82 94.94 96.07 97.75 97.22 97.78 97.78 98.33 Trung bình 82.55 81.63 82.16 82.23 82.56 83.86 82.26 84.19 Bên cạnh độ chính xác, một số thông dụng rộng rãi trong máy học (machine số tác động đến hiệu suất của mô hình dự learning), phân lớp nhị phân (Binary đoán như độ nhạy (sensitivity), độ đặc hiệu classification), được tính theo công thức (specificity), khả năng xác định (precision), (4), công thức (5), công thức (6) và công F1 (trung bình điều hòa giữa precision và thức (7) dựa trên ma trận chéo phân phối sensitivity) và diện tích dưới AUC (area tần số 2 chiều như bảng 6. under the curve) của đường biểu diễn ROC 𝑇𝑃 𝑆𝑒𝑛𝑠𝑖𝑡𝑖𝑣𝑖𝑡𝑦 = 𝑅𝑒𝑐𝑎𝑙𝑙 = 𝑇𝑃+𝐹𝑁 (4) (Receiver operating characteristic) trên 3 𝑇𝑁 tập dữ liệu về y khoa là Breast Cancer 𝑆𝑝𝑒𝑐𝑖𝑓𝑖𝑐𝑖𝑡𝑦 = 𝑇𝑁+𝐹𝑃 (5) 𝑇𝑃 Coimbra, Cryotherapy và Pima cũng được 𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 = 𝑇𝑃+𝐹𝑃 (6) nghiên cứu. 2∗𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛∗𝑅𝑒𝑐𝑎𝑙𝑙 𝐹1 = (7) Các chỉ số trên thường được ứng 𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛+𝑅𝑒𝑐𝑎𝑙𝑙 35
SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY No. 77 (06/2021) Bảng 6. Confusion Matrix Bảng 7, bảng 8, bảng 9 thể hiện sự cải Lớp Dự đoán thiện về hiệu suất và hình 2, hình 3, hình 4, Lớp thực tế Lớp khác hình 5, hình 6, hình 7 lần lượt là đường biểu diễn ROC khi so sánh giữa thuật toán (Possitive) (Negative) DPCAR với PCAR, DPCAR2 với PCAR2 Thực tế TP FN trên 3 tập dữ liệu tương ứng Breast Cancer FP TN Coimbra, Cryotherapy và Pima. Bảng 7. So sánh hiệu suất (%) của PCAR, DPCAR, PCAR2, DPCAR2 trên tập dữ liệu Breast Cancer Coimbra PCAR DPCAR PCAR2 DPCAR2 Sensitivity 58.21 71.5 50.1 72.24 Specificity 83.12 72.67 81.69 71.67 Precision 72.67 84.12 66.26 82.15 F1 63.43 75.33 51.11 76.17 AUC 70.67 72.09 65.9 71.96 Bảng 8. So sánh hiệu suất (%) của PCAR, DPCAR, PCAR2, DPCAR2 trên tập dữ liệu Cryotherapy PCAR DPCAR PCAR2 DPCAR2 Sensitivity 93 92.62 93.24 89.67 Specificity 88.17 95.14 89.07 92.74 Precision 92.62 93 87.67 93.24 F1 91.15 91.15 88.79 89.9 AUC 90.59 93.88 91.16 91.21 Bảng 9. So sánh hiệu suất (%) của PCAR, DPCAR, PCAR2, DPCAR2 trên tập dữ liệu Pima PCAR DPCAR PCAR2 DPCAR2 Sensitivity 49.04 63.72 41.56 66.61 Specificity 89.95 81.96 91.23 81.59 Precision 72.52 66.91 73 65.31 F1 57.47 64.82 51 65.54 AUC 69.5 72.79 66.4 74.1 36
NGUYỄN ANH TÚ TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GÒN Hình 2. Đường biểu diễn ROC của PCAR Hình 5. Đường biểu diễn ROC của PCAR2 và DPCAR trên tập dữ liệu Breast Cancer và DPCAR2 trên tập dữ liệu Cryotherapy Coimbra Hình 3. Đường biểu diễn ROC của PCAR2 Hình 6. Đường biểu diễn ROC của PCAR và DPCAR2 trên tập dữ liệu Breast Cancer và DPCAR trên tập dữ liệu Pima Coimbra Hình 4. Đường biểu diễn ROC của PCAR Hình 7. Đường biểu diễn ROC của PCAR2 và DPCAR trên tập dữ liệu Cryotherapy và DPCAR2 trên tập dữ liệu Pima 37
SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY No. 77 (06/2021) 5. Kết luận cân bằng về lớp. Do phương pháp đề xuất Nghiên cứu này giới thiệu một thuật mang lại hiệu quả cao về độ chính xác so toán đưa ra độ đo mới là tỷ lệ dự đoán và đề với các phương pháp giải quyết bài toán ra xuất một phương pháp cải tiến ở giai đoạn quyết định trước đây nên nó cũng có thể áp dự đoán luật của thuật toán trên để tăng dụng tốt cho các bài toán khác như phân hiệu quả dự đoán của bộ phân lớp khai thác lớp, nhận diện mẫu trong dữ liệu chuỗi tuần được. Bằng phương pháp kết hợp việc chọn tự và dữ liệu chuỗi thời gian v.v. lớp có số lượng cao nhất, trung bình cộng Trong tương lai, nghiên cứu này có thể của trung bình điều hòa giữa tỷ lệ dự đoán tiếp tục mở rộng cải tiến xây dựng bộ phân và độ tin cậy, trung bình cộng của độ hỗ trợ lớp có tính đa lớp cho dự đoán các tập dữ của các luật trong bộ phân lớp phủ được liệu đa lớp – là tập dữ liệu chứa các luật mà mẫu trong tập dữ liệu kiểm thử đã hạn chế một luật có thể thuộc về nhiều lớp. Ngoài được việc lạm dụng chọn các luật có tỷ lệ ra, việc áp dụng các kỹ thuật song song dự đoán cao hay các luật mặc định nhưng làm tăng tốc độ khai thác đối với những tập dự đoán sai, giúp cải thiện được độ chính dữ liệu có số lượng thuộc tính cao cũng xác, đặc biệt đối với tập dữ liệu thực bị mất được quan tâm. TÀI LIỆU THAM KHẢO [1] Agrawal, R., & Srikant, R., "Fast algorithms for mining association rules in large databases", Proceedings of the 20th International Conference on Very Large Databases, 1994. [2] Zaki, M., "Scalable algorithms for association mining", IEEE Transactions on Knowledge and Data Engineering, vol. 12(3), pp. 372-390, 2000. [3] Han, J., Pei, J., Yin, Y., & Mao, R., "Mining frequent patterns without candidate generation: A frequent-pattern tree approach", Data mining and knowledge discovery, 2004. [4] Liu, B., Hsu, W., Ma, Y., "Integrating classification and association rule mining", Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, pp. (80-86), 1998. [5] Quinlan, J. R., "C4.5: Programs for Machine Learning", San Mateo: Morgan Kaufmann, 1993. [6] Tolun, M.R., Abu-Soud, S.M., "ILA: An Inductive Learning Algorithm for Rule Extraction", Expert Systems with Applications, vol. 14(3), pp. 361-370, 1998. [7] Li, W., Han, J., & Pei, J., "CMAR: Accurate and efficient classification based on multiple-class association rule", Proceedings of the 1st IEEE International Conference on Data Mining, pp. 369-376, 2001. [8] Thabtah, F., Cowling, P., & Peng, Y., "MMAC: A new multi-class, multi-label associative classification approach", Proceedings of the 4th IEEE International Conference on Data Mining , 2004. 38
NGUYỄN ANH TÚ TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GÒN [9] Thabtah, F., Cowling, P., & Peng, Y., "MCAR: multi-class classification based on association rule", Proceedings of the 3rd ACS/IEEE International Conference on Computer Systems and Applications, 2005. [10] Song, K., Lee, K., "Predictability-based collective class association rule mining", Expert Syst. Appl., vol. 79, pp. 1-7, 2017. [11] Dua, D., & Graff, C., "UCI Machine Learning Repository", 2019. [12] Cohen, W. W., "Fast effective rule induction", Proceedings of the twelfth international conference on machine learning, pp. 115-123, 1995. [13] Hall, M., Franks, E., Holmes, G., Pfaringer, B., Reutemann, P., & Witten, I. H., "The WEKA datamining software: an update", ACM SIGKDD explorations newsletter, 2009. [14] Al-Tapan, A.A., Al-Maqaleh, B.M., "An effective mining of exception class association rules from medical datasets", Int. J. Comput. Sci. Eng., vol. 7, pp. 191- 198, 2017. [15] Alwidian, J., Hammo, H.B., & Obeid, N., "WCBA: Weighted classification based on association rules algorithm for breast cancer disease", Appl. Soft Comput., vol. 62, pp. 536-549, 2018. [16] Nguyen, L.T.T., Nguyen, N.T., "An improved algorithm for mining class association rules using the difference of Obidsets", Expert Syst, Appl, vol. 42(9), pp. 4361-4369, 2015. [17] Nguyen L.T.T., Vo B., Mai T., Nguyen TL., "A Weighted Approach for Class Association Rules", Sieminski A., Kozierkiewicz A., Nunez M., Ha Q. (eds) Modern Approaches for Intelligent Information and Database Systems. Studies in Computational Intelligence, Springer, Cham, vol. 769, pp. 213-222, 2018. [18] Thabtah, Hadi, W., Abdelhamid, N., & Issa, A., "Prediction phase in associative classification mining", International Journal of Software Engineering and Knowledge Engineering, vol. 21, pp. 855-876, 2011. Ngày nhận bài: 13/2/2020 Biên tập xong: 15/6/2021 Duyệt đăng: 20/6/2021 39