Luận án Nghiên cứu phát triển phương pháp khai phá luật kết hợp mờ biểu thị bằng thông tin ngôn ngữ, ứng dụng

[0, 100], giá trị của thuộc tính A trong miền [0, 1] như sau: {0.34, 0.41, 0.45}. Đối với thuộc tính B: Dom(A) = [0, 100], giá trị của thuộc tính A trong miền [0, 1] như sau: {0.4, 0.48, 0.32}. 41 Bảng 2.1: Cơ sở dữ liệu ví dụ TID A B 𝑇1 30 40 𝑇2 41 48 𝑇3 45 32 Với giá trị A = 0.3: Do giá trị v(Very Low) <0.3< v(Least Low), ta chỉ cần tính khoảng cách giữa 0.3 với hai miền mờ tương ứng là Very Low và Least Low, còn các miền mờ Least Height, Very Height có giá trị bằng 0. Khoảng cách giữa 0.3 và miền mờ Very Low: 1-abs(0.3 - 0.125) = 0.825. Khoảng cách giữa 0.3 và miền mờ Least Low: 1-abs(0.3 - 0.375) = 0.925. Với giá trị A = 0.41: Do giá trị v(Least Low) <0.41< v(Least Height), ta chỉ cần tính khoảng cách giữa 0.41 với hai miền mờ tương ứng là Very Low và Least Low, còn các miền mờ Least Height, Very Height có giá trị bằng 0. Khoảng cách giữa 0.41 và miền mờ Least Low: 1-abs(0.41 - 0.375) = 0. 965. Khoảng cách giữa 0.4 và miền mờ Least Height: 1-abs(0.41 - 0.625) = 0. 785. Với cách tính tương tự chúng ta có các giá trị được mờ hóa như trong Bảng 2.2. Ký hiệu: A1, B1: Very Low; A2, B2: Least Low; A3, B3: Least Heigh, A4, B4: Very Heigh; Bảng 2.2: Mờ hóa dữ liệu trong Bảng 2.1 TID A B A1 A2 A3 A4 B1 B2 B3 B4 𝑇1 0.825 0.925 0 0 0 0.975 0.775 0 𝑇2 0 0.965 0.785 0 0 0.895 0.855 0 𝑇3 0 0.925 0.825 0 0.805 0.945 0 0 2.2.2. Quan hệ khoảng cách giao dịch Jia-Yu Dai và công sự [18] đã đề xuất phương pháp tính khoảng cách giữa các giao dịch trong CSDL nhị phân. Dựa vào khoảng cách giữa các giao dịch, có thể gộp các giao dịch có khoảng cách gần nhau để tạo ra nhóm giao dịch, kết quả là thu được CSDL mới có kích thước nhỏ hơn. Quan hệ giao dịch và quan hệ khoảng cách giao dịch cho các giao dịch trong CSDL mờ được định nghĩa như sau: 42 a) Quan hệ giao dịch: Hai giao dịch 𝑇1, 𝑇2 được gọi là có quan hệ với nhau nếu 𝑇1 hoặc là tập con của 𝑇2 hoặc 𝑇1là tập cha của 𝑇2. b) Quan hệ khoảng cách giao dịch: Khoảng cách giữa hai giao dịch là số các mục (item) khác nhau. Trong bảng Bảng 2.2 khoảng cách giữa giao dịch 𝑇1 và 𝑇2 là 𝐷𝑇1−𝑇2 = 2, khoảng cách giữa hai giao dịch 𝑇2 và 𝑇3 là 𝐷𝑇1−𝑇3 = 4. 2.2.3. Xây dựng bảng định lượng Để giảm số lượng tập ứng cử được tạo ra, cần phải có thêm thông tin để loại bớt các tập không phải là tập phổ biến. Bảng định lượng được xây dựng để lưu các thông tin này khi mỗi giao dịch được xử lý. Các mục xuất hiện trong giao dịch cần sắp xếp theo thứ tự từ điển. Bắt đầu từ các mục bên trái và gọi đó là tiền tố của mục. Sau đó tính chiều dài của giao dịch đầu vào là n, ghi số lượng các mục xuất hiện trong giao dịch vào các mục tùy theo độ dài của giao dịch: L𝑛, Ln−1, . . . , L1. Bảng định lượng bao gồm những mục trong đó mỗi Li chứa một tiền tố mục và giá trị hỗ trợ của mục đó. Ví dụ 2.2: Xây dựng bảng định lượng cho CSDl giao dịch trong Bảng 2.2. Với giao dịch TID = T1 có giá trị là {A1 = 0.825; A2 = 0.925; B2 = 0.975; B3 = 0.775}, không tính các mục có giá trị bằng 0. Giao dịch T1 có chiều dài n = 4, với tiền tố A1, giá trị từ L1 đến L4 tăng lên 0.825 (khởi tạo là 0), vì vậy A1 = 0.825 xuất hiện trong mỗi Li, với i = 1,..,4. Với tiền tố A2, giá trị từ L1 đến L3 tăng lên 0.925 (khởi tạo là 0), Vì vậy A2 = 0.925 xuất hiện trong mỗi TLi, với i = 1,,3. Với tiền tố B2, giá trị từ L1,L2 tăng lên B2 = 0.975 (khởi tạo là 0). Với tiền tố B3, giá trị L1 tăng lên B3 = 0.775. Với giao dịch TID = T2 có giá trị là {A2 = 0.965; A3 = 0.785; B2 = 0.895; B3 = 0.855}, giá trị A2 trong L1, L2, L3 tăng lên là A2 = 1.89 (0.925 + 0.965), giá trị A2 trong L4 là A2 = 0.965. Với tiền tố A3 = 0.785 trong L1, L2, L3. Với tiền tố B2 = 0.895 trong L1, L2. Với tiền tố B3 = 0.855 trong L1. Với giao dịch TID = T3 {A2 = 0.925; A3 = 0.825; B1 = 0.805; B2 = 0.945; }. Với tiền tốt A2, giá trị L4 tăng lên A2 = 1.89, trong L1, L2, L3 giá trị A2 = 2.815; Với tiền tố A3: trong L1, L2, L3 giá trị của A3 = 1.61; Với tiền tố B1, trong L1, L2 giá trị B1 = 0.805; Với tiền tố B2, trong L1 giá trị B2 = 2.815. 43 Bảng 2.3 là bảng định lượng được xây dựng từ CSDL trong Bảng 2.2. Với bảng định lượng, chúng ta có thể dễ dàng loại bớt các tập ứng cử viên có độ hỗ trợ nhỏ hơn so với sự hỗ trợ tối thiểu. Bảng 2.3: Bảng định lượng của cơ sở dữ liệu Bảng 2.2 L4 L3 L2 L1 A1 = 0.825 A1 = 0.825 A1 = 0.825 A1 = 0.825 A2 = 1.89 A2 = 2.815 A2 = 2.815 A2 = 2.815 A3 = 1.61 A3 = 1.61 A3 = 1.61 B1 = 0.805 B1 = 0.805 B2 = 1.87 B2 = 2.815 B3 = 1.63 2.3. Nén cơ sở dữ liệu giao dịch Với d là khoảng cách quan hệ được khởi tạo bằng 1. Dựa vào khoảng cách giữa các giao dịch, chúng ta gộp các giao dịch có khoảng cách nhỏ hơn hoặc bằng d để tạo thành nhóm giao dịch mới và đưa vào khối gồm các giao dịch được trộn với nhau. Hình 2.2: Tổng quan về thuật toán nén CSDL giao dịch CSDL T iền x ử lý d ữ liệu Mờ hóa CSDL giao dịch Gộp các giao dịch K h ai p h á d ữ liệu Thuật toán Khai phá luật kết hợp mờ từ CSDL nén Tập luật kết hợp mờ 44 Trong Hình 2.2: CSDL gồm các thuộc tính định lượng, phần Tiền xử lý dữ liệu: Thực hiện chuẩn hoá dữ liệu về đoạn [0,1], độ thuộc của giá trị của các thuộc tính được tính toán như trình trình bày trong mục 2.2, sau đó từ CSDL mờ thu được chúng ta gộp các giao dịch gần nhau vào với nhau tạo ra CSDL mới gọi là CSDL nén. Chi tiết thuật toán nén được trình bày chi tiết trong Thuật toán 1. Để tìm ra các luật kết hợp từ CSDL nén luận án đề xuất cải tiến thuật toán Apriori mờ và chi tiết như Thuật toán 2. Thuật toán 1: Thuật toán nén giao dịch Đầu vào: Cơ sở dữ liệu giao dịch mờ D Đầu ra: Cơ sở dữ liệu nén Ký hiệu các tham số của thuật toán như sau: 𝑀𝐿 = {𝑀𝐿𝑘}: 𝑀𝐿𝑘 các nhóm giao dịch có độ dài bằng k (độ dài của giao dịch là số mục trong giao dịch) 𝐿 = {𝐿𝑘}: 𝐿𝑘 các giao dịch có độ dài k 𝑇𝑖: Giao dịch thứ i trong CSDL mờ | 𝑇 𝑖 |: Độ dài của giao dịch 𝑇𝑖 Nội dung thuật toán: Bước 1: Mỗi lần đọc một giao dịch 𝑇𝑖 từ CSDL mờ Bước 2: Tính độ dài của giao dịch 𝑇𝑖: n Bước 3: Dựa vào giao dịch đầu vào để xây dựng bảng định lượng. Bước 4: Tính toán khoảng cách giữa giao dịch Ti với các nhóm giao dịch trong khối MLn−1, MLn, MLn+1. Nếu tồn tại một nhóm giao dịch trong các khối MLn−1, MLn, MLn+1 có khoảng cách với giao dịch Ti nhỏ hơn hoặc bằng d. Chúng ta tiến hành gộp giao dịch Ti với nhóm giao dịch trong khối tương ứng, ta thu được nhóm giao dịch mới và đưa vào khối có độ dài tương ứng, và xóa nhóm giao dịch cũ trong khối. Ví dụ 2.3: Cho d = 1 và hai giao dịch {B = 0.23; C = 0.55; D = 0.75} và {C = 0.82; D = 0.94}. Do khoảng cách giữa hai giao dịch này bằng 1, chúng được gộp thành một nhóm giao dịch {B = 0.23; C = 1.37; D = 1.69}. Nhóm giao dịch này có độ dài bằng 3, vì vậy đưa nhóm giao dịch này vào khối 𝑀𝐿3. Dấu “ = ” được sử dụng để chỉ tổng độ thuộc của các mục trong nhóm giao dịch. Với giao dịch {B = 0.4; C = 0.5}, khoảng cách giữa {B = 0.23; C = 1.37; D = 1.69} và 45 {B = 0.4; C = 0.5} là 1. Vì vậy giao dịch {B = 0.4; C = 0.5} được gộp với nhóm giao dịch {B = 0.23; C = 1.37; G = 1.69} tạo thành nhóm giao dịch mới. Cuối cùng, nhóm giao dịch trở thành {B = 0.63; C = 1.87; G = 1.69}. Xóa nhóm giao dịch {B = 0.23; C = 1.37; G = 1.69} trong khối 𝑀𝐿3 và thêm nhóm giao dịch {B = 0.63; C = 1.87; G = 1.69} vào khối 𝑀𝐿3. Bước 5: Nếu giao dịch 𝑇𝑖 không được gộp với các nhóm giao dịch trong khối MLn−1, MLn, MLn+1. Tính toán khoảng cách giữa giao dịch 𝑇𝑖 và các giao dịch trong khối 𝐿𝑛−1, 𝐿𝑛, 𝐿𝑛+1. Nếu tồn tại giao dịch 𝑇𝑗 sao cho 𝐷𝑇𝑖−𝑇𝑗 ≤ 𝑑, gộp giao dịch 𝑇𝑖 với giao dịch 𝑇𝑗 để tạo thành nhóm giao dịch và thêm nhóm giao dịch này vào khối tương ứng (tùy thuộc vào độ dài của nhóm giao dịch được tạo ra), và xóa giao dịch 𝑇𝑗 trong khối: 𝐿𝑛−1, 𝐿𝑛, 𝐿𝑛+1. Nếu không tìm được giao dịch thỏa mãn khoảng cách d, thêm giao dịch 𝑇𝑖 vào khối 𝐿𝑛. Bước 6: Lặp lại 5 bước trên cho đến khi giao dịch cuối cùng trong CSDL giao dịch được xử lý. Bước 7: Mỗi lần đọc một giao dịch 𝑇𝑖 trong khối 𝐿 = {𝐿𝑘} Bước 8: Tính độ dài của giao dịch 𝑇𝑖: n Bước 9: Tính toán khoảng cách giữa giao dịch 𝑇𝑖 với các nhóm giao dịch trong các khối MLn−1, MLn, MLn+1. Nếu tồn tại một nhóm giao dịch có khoảng cách nhỏ hơn hoặc bằng d, tiến hành gộp giao dịch 𝑇𝑖 với nhóm giao dịch tìm được để tạo thành nhóm giao dịch mới. Tùy thuộc vào độ dài của nhóm giao dịch mới, sẽ thêm nhóm giao dịch mới này vào khối tương ứng: MLn−1, MLn, MLn+1, xóa nhóm giao dịch cũ trong khối: MLn−1, MLn, MLn+1, và xóa giao dịch 𝑇𝑖 trong khối 𝐿𝑛. Bước 10: Lặp lại bước 7, bước 8, bước 9 cho đến khi giao dịch cuối cùng trong 𝐿 = {𝐿𝑘 } được xử lý. Kết quả thu được CSDL nén gồm các giao dịch trong các khối 𝐿 = {𝐿𝑘 }, 𝑀𝐿 = {𝑀𝐿𝑘 }, và bảng định lượng. Bước tiếp theo sau khi đã nén CSDL, có thể dùng một thuật toán khai phá luật kết hợp mờ nào đó để khai phá các luật kết hợp mờ của CSDL đã nén. Ở đây, luận án sử dụng thuật toán khai phá luật kết hợp mờ theo hướng tiếp cận của ĐSGT. Điểm khác biệt ở đây là sử dụng lý thuyết ĐSGT để xây dựng độ thuộc của một giá trị thuộc tính. 46 2.4. Thuật toán trích xuất luật kết hợp mờ Thuật toán 2: Khai phá dữ liệu mờ theo hướng tiếp cận ĐSGT Ký hiệu các tham số của thuật toán khai phá luật kết hợp mờ theo hướng tiếp cận ĐSGT N: Tổng số giao dịch trong CSDL M: Tổng số thuộc tính 𝐴𝑗: Thuộc tính thứ j, 1 ≤ 𝑗 ≤ 𝑚 (thuộc tính định lượng hoặc thuộc tính hạng mục) |𝐴𝑗|: Số nhãn gia tử của thuộc tính Aj 𝑅𝑗𝑘: Nhãn gia tử j của thuộc tính Aj, 1 ≤ 𝑘 ≤ |Aj| 𝐷(𝑖): Dữ liệu giao dịch thứ i, 1 ≤ 𝑖 ≤ 𝑁 𝑣𝑗 (𝑘) : Giá trị phần tử thứ k của Aj trong D (i) 𝑓 𝑗𝑘 (𝑖) : Giá trị độ thuộc của 𝑣j (k) với nhãn gia tử Rjk, 0 ≤ 𝑓𝑗𝑘 (𝑖) ≤ 1 𝑆𝑢𝑝(𝑅𝑗𝑘): Độ hỗ trợ của Rjk Sup: Giá trị hỗ trợ của mỗi tập mục phổ biến Conf: Độ tin cậy của mỗi tập mục phổ biến Min_sup: Độ hỗ trợ tối thiểu cho trước Min_conf: Độ tin tin cậy cho trước 𝐶𝑟: Tập các tập mục có khả năng với r thuộc tính (tập mục), 1 ≤ 𝑟 ≤ 𝑚 𝐿𝑟: Tập các tập mục phổ biến thỏa mãn với r nhãn gia tử (tập mục) 1 ≤ 𝑟 ≤ 𝑚. Thuật toán khai phá dữ liệu dựa trên ĐSGT cho các giá trị định lượng được thực hiện như sau: Input: - CSDL giao tác D - Các ĐSGT cho các thuộc tính mờ - Độ hỗ trợ 𝑀𝑖𝑛_𝑠𝑢𝑝 và độ tin cậy 𝑀𝑖𝑛_𝑐𝑜𝑛𝑓 Output: Luật kết hợp mờ Bước 1: Chuyển các giá trị định lượng 𝑣𝑗 (𝑘) của giao dịch 𝐴𝑗 trong 𝐷 (𝑖), với i từ 1 tới N. Với 𝑣𝑗 (𝑘) , nếu 𝑣𝑗 (𝑘) nằm ở ngoài 1 trong 2 đầu mút (2 nhãn gia tử cực đại 47 và cực tiểu) thì 𝑣𝑗 (𝑘) chỉ có 1 nhãn gia tử ứng với đầu mút đó. Ngược lại 𝑣𝑗 (𝑘) được biểu diễn bởi 2 nhãn gia tử liên tiếp có đoạn giá trị nhỏ nhất trên trường giá trị của 𝑣𝑗 (𝑘) , mỗi nhãn ứng với 1 giá trị biểu diễn độ thuộc 𝑓𝑗𝑘 (𝑖) (j = 1, 2) của 𝑣𝑗 (𝑘) với nhãn gia tử đó. Độ thuộc này được tính là khoảng cách của 𝑣𝑗 (𝑘) tới giá trị biểu diễn cho nhãn gia tử tương ứng. Bước 2: Thực hiện thuật toán nén giao dịch (Thuật toán 1) với CSDL được mờ hóa ở Bước 1. Kết thúc bước này, chúng ta thu được CSDL giao dịch nén và bảng định lượng. Chúng ta sử dụng thuật toán giống như Apriori với CSDL nén để sinh ra các tập phổ biến. Bước 3: Dựa vào giá trị trong TL1 của bảng định lượng, giá trị trong TL1 là độ hỗ trợ của các 𝑅𝑗𝑘. Nếu 𝑆𝑢𝑝(𝑅𝑗𝑘) ≥ min_𝑠𝑢𝑝 thì đưa Rjk vào L1. Bước 4: Nếu L1 ≠ ∅, tiếp tục bước sau, nếu L1 = ∅ thì kết thúc thuật toán. Bước 5: Thuật toán xây dựng tập mục phổ biến mức r từ các tập mục phổ biến mức r - 1 bằng cách chọn 2 tập mục phổ biến mức r - 1 chỉ khác nhau duy nhất một mục, hợp 2 tập mục này ta được tập mục ứng viên 𝐶𝑟. Trước khi sử dụng CSDL nén để tính độ hỗ trợ của các tập mục trong 𝐶𝑟, dựa vào giá trị của TLr trong bảng định lượng chúng ta có thể loại bớt một số ứng cử viên mà không cần phải duyệt CSDL nén. Bước 6: Duyệt CSDL nén, tính độ hỗ trợ của mỗi tập mục trong 𝐶𝑟. Nếu tập mục nào có độ hỗ trợ thỏa mãn độ hỗ trợ tối thiểu thì đưa vào 𝐿𝑟. Bước 7: Thực hiện theo các bước con sau đây lặp lại cho các tập mục phổ biến mức lớn hơn được sinh ra tiếp theo dạng (r+1) tập mục phổ biến S với mục (𝑠1, 𝑠2, , 𝑠𝑡 , , 𝑠𝑟+1) trong 𝐶𝑟+1, 1 ≤ 𝑡 ≤ 𝑟 + 1. (a) Tính giá trị hỗ trợ sup(S) của S trong giao dịch (b) Nếu 𝑆𝑢𝑝(𝑆) ≥ 𝑀𝑖𝑛_𝑠𝑢𝑝, thì đưa S vào 𝐿𝑟+1 Bước 8: Nếu Lr+1 là rỗng, thì thực hiện bước tiếp theo, ngược lại, đặt 𝑟 = 𝑟 + 1, thực hiện lại bước 6 và 7. Bước 9: Đưa ra các luật kết hợp từ các tập mục phổ biến vừa thu được. 48 2.5. Kết quả thử nghiệm Kết quả thử nghiệm được thực hiện với hai thuật toán: thuật toán đề xuất và thuật toán trong [31] bằng ngôn ngữ lập trình C# và chạy thử nghiệm trên máy tính có cấu hình như sau: Intel(R) Core i5 CPU, RAM 8GB. Trong chương này, luận án sử dụng hai CSDL để thử nghiệm: FAM95 và STULONG: - Dữ liệu thử nghiệm STULONG gồm 5 thuộc tính có giá trị là các số nguyên A1, A2, A3, A4, A5. Miền giá trị tương ứng của các thuộc tính là: [-1, 199], [-1, 133], [90, 225], [50, 145], [-1, 530]. CSDL này gồm 1417 bản ghi. - Dữ liệu thử nghiệm FAM95 là số liệu điều tra dân số Mỹ năm 1995. Luận án lựa chọn 5 thuộc tính để thử nghiệm gồm: Age, Hours, IncFam, IncHead, Sex. Với Age là tuổi của người dân, Hours là số giờ làm việc trong tuần, IncFam: thu nhập của gia đình, IncHead là thu nhập của người đứng đầu gia đình, Sex giới tính của chủ gia đình. Các thuộc tính: Age, Hours, IncFam, IncHead là các thuộc tính mờ, thuộc tính Sex nhận các giá trị 0 (nữ) hoặc 1 (nam). CSDL FAM95 gồm 63565 bản ghi. 2.5.1. Thử nghiệm với CSDL FAM95 Trong Bảng 2.4 thống kê số lượng luật kết hợp thu được của ba phương pháp: phương pháp sử dụng: CSDL không nén, CSDL nén, và CSDL nén và Bảng định lượng. Với độ hỗ trợ 20%, 30% số lượng luật kết hợp của phương pháp luận án đề xuất có khác so với phương pháp sử dụng thuật toán Apriori, với độ hỗ trợ tử 40% đến 70% thì số lượng luật kết hợp thu được của ba phương pháp là giống nhau. Bảng 2.4: Số lượng luật kết hợp thu được với độ tin cậy 80% Độ hỗ trợ (%) CSDL không nén CSDL nén CSDL nén, và Bảng định lượng 20 238 255 255 30 98 94 94 40 34 34 34 50 18 18 18 60 6 6 2 70 2 2 2 49 Bảng 2.5: Luật kết hợp thu được với độ hỗ trợ 60% và độ tin cậy 80% STT Luật kết hợp Đỗ hỗ trợ Độ tin cậy CSDL không nén 1 { VL_INCHEAD } ==> { VL_INCFAM } 92% 97% 2 { VL_INCFAM } ==> { VL_INCHEAD } 92% 98% 3 { LY_AGE } ==> { VL_INCHEAD } 69% 98% 4 { LY_AGE } ==> { VL_INCFAM } 70% 99% 5 { VL_INCHEAD, LY_AGE } ==> { VL_INCFAM } 69% 99% 6 { VL_INCFAM, LY_AGE } ==> { VL_INCHEAD } 69% 99% CSDL giao dịch nén, không Bảng định lượng 1 { VL_INCHEAD } ==> { VL_INCFAM } 91% 98% 2 { VL_INCFAM } ==> { VL_INCHEAD } 91% 99% 3 { LY_AGE } ==> { VL_INCHEAD } 69% 99% 4 { LY_AGE } ==> { VL_INCFAM } 69% 100% 5 { VL_INCHEAD, LY_AGE } ==> { VL_INCFAM } 69% 100% 6 { VL_INCFAM, LY_AGE } ==> { VL_INCHEAD } 69% 99% CSDL giao dịch nén, và Bảng định lượng 1 { VL_INCHEAD } ==> { VL_INCFAM } 91% 98% 2 { VL_INCFAM } ==> { VL_INCHEAD } 91% 99% 3 { LY_AGE } ==> { VL_INCHEAD } 69% 99% 4 { LY_AGE } ==> { VL_INCFAM } 69% 100% 5 { LY_AGE, VL_INCHEAD } ==> { VL_INCFAM } 69% 100% 6 { LY_AGE, VL_INCFAM } ==> { VL_INCHEAD } 69% 99% Bảng 2.6: Luật kết hợp thu được với độ hỗ trợ 70% và độ tin cậy 80% STT Luật kết hợp Đỗ hỗ trợ Độ tin cậy CSDL không nén 1 { VL_INCHEAD } ==> { VL_INCFAM } 92% 97% 2 { VL_INCFAM } ==> { VL_INCHEAD } 92% 98% CSDL giao dịch nén, không Bảng định lượng 1 { VL_INCHEAD } ==> { VL_INCFAM } 91% 98% 2 { VL_INCFAM } ==> { VL_INCHEAD } 91% 99% CSDL giao dịch nén, và Bảng định lượng 1 { VL_INCHEAD } ==> { VL_INCFAM } 91% 98% 2 { VL_INCFAM } ==> { VL_INCHEAD } 91% 99% 50 Trong Bảng 2.5, Bảng 2.6 cho thấy số lượng luật kết hợp thu được của ba thử nghiệm (với CSDL không nén, CSDL nén không sử dụng bảng định lượng, CSDL nén sử dụng bảng định lượng) có số lượng giống nhau. Trong Bảng 2.5 so sánh tương ứng từng luật của ba phương pháp cho thấy độ hỗ trợ và độ tin cậy của mỗi luật có khác nhau nhưng không đáng kể. Hình 2.3: Thời gian thực hiện với CSDL nén và CSDL không nén Hình 2.4: Thời gian thực hiện với CSDL nén 0 200 400 600 800 1000 1200 1400 1600 10% 20% 30% 40% 50% 60% 70% 80% T IM E ( S E C O N D ) MINIMUM SUPPORT CSDL không nén CSDL nén 0 50 100 150 200 250 300 4% 5% 10% 15% 20% 25% 30% T IM E ( S E C O N D ) MINIMUM SUPPORT Không sử dụng bảng định lượng Sử dụng bảng định lượng 51 Trong Hình 2.3 so sánh thời gian thực thuật toán Apriori mờ với CSDL không nén và thời gian thực hiện với CSDL nén nhưng không sử dụng bảng định lượng. Trong Hình 2.4 so sánh thời gian thực hiện thuật toán cùng với CSDL nén có sử dụng bảng định lượng và CSDL nén không sử dụng bảng định lượng. Thời gian dùng để nén CSDL trên là 135 giây, số giao dịch thu được sau khi nén là 2402 giao dịch. Kết quả thử nghiệm với độ tin cậy là 60%, luận án thử nghiệm với hai thuật toán: Luật kết hợp theo cách tiếp cận của ĐSGT [2] và thuật toán luận án đề xuất là nén CSDL mờ theo hướng tiếp cận ĐSGT. Kết quả thử nghiệm cho thấy phương pháp đề xuất nén CSDL cho kết quả nhanh hơn với phương pháp đề xuất trong [2] và giá trị của các tập phổ biến tìm được giống với khi chúng ta sử dụng CSDL không nén. 2.5.2. Thử nghiệm với CSDL STULONG Trong Bảng 2.7 thống kê số lượng luật kết hợp thu được của ba phương pháp: phương pháp sử dụng: CSDL không nén, CSDL nén, và CSDL nén và Bảng định lượng. Bảng 2.7: Số lượng luật kết hợp thu được với độ tin cậy 80% Độ hỗ trợ (%) CSDL không nén CSDL nén CSDL nén, và Bảng định lượng 5% 7822 8188 8185 10% 5076 5532 5527 20% 2149 2528 2528 30% 1096 1348 1318 40% 587 599 599 50% 248 287 287 60% 107 155 155 70% 75 75 75 80% 23 35 35 Nhận xét: số lượng luật kết hợp thu được của phương pháp luận án đề xuất sử dụng CSDL nén có sử dụng bảng định lương và không sử dụng bảng định lượng cơ bản là giống nhau. 52 Bảng 2.8: So sánh thời gian thực hiện khai phá luật kết hợp với độ tin cậy 80% Độ hỗ trợ (%) CSDL không nén CSDL nén CSDL nén, và Bảng định lượng 5% 669 41.4 41.4 10% 580 26.4 26.3 20% 187 8.3 8.3 30% 72 3.6 3.5 40% 26 1.1 1.1 50% 8 0.4 0.4 60% 3 0.2 0.2 70% 1 0.1 0.1 Trong Bảng 2.9, Bảng 2.10 cho thấy số lượng luật kết hợp thu được của ba thử nghiệm (với CSDL không nén, CSDL nén không sử dụng bảng định lượng, CSDL nén sử dụng bảng định lượng) có số lượng luật kết hợp giống nhau. Trong Bảng 2.9, Bảng 2.10 so sánh tương ứng từng luật của ba phương pháp cho thấy độ hỗ trợ và độ tin cậy của mỗi luật có khác nhau nhưng không đáng kể. Bảng 2.9: Luật kết hợp thu được với độ hỗ trợ 85% và độ tin cậy 80% STT Luật kết hợp Đỗ hỗ trợ Độ tin cậy CSDL không nén 1 { LL_A5 } ==> { LH_A2 } 86 % 97 % 2 { LH_A2 } ==> { LL_A5 } 86 % 93 % 3 { LL_A5 } ==> { VH_A1 } 88 % 99 % 4 { VH_A1 } ==> { LL_A5 } 88 % 91 % 5 { LH_A2 } ==> { VH_A1 } 92 % 99 % 6 { VH_A1 } ==> { LH_A2 } 92 % 95 % 7 { LL_A5, VH_A1 } ==> { LH_A2 } 85 % 97 % 8 { LH_A2, VH_A1 } ==> { LL_A5 } 85 % 93 % 9 { LH_A2, LL_A5 } ==> { VH_A1 } 85 % 100 % CSDL giao dịch nén, không Bảng định lượng 1 { LL_A5 } ==> { LH_A2 } 88 % 99 % 2 { LH_A2 } ==> { LL_A5 } 88 % 95 % 3 { LL_A5 } ==> { VH_A1 } 88 % 100 % 53 4 { VH_A1 } ==> { LL_A5 } 88 % 91 % 5 { LH_A2 } ==> { VH_A1 } 92 % 100 % 6 { VH_A1 } ==> { LH_A2 } 92 % 95 % 7 { LL_A5, VH_A1 } ==> { LH_A2 } 87 % 99 % 8 { LH_A2, VH_A1 } ==> { LL_A5 } 87 % 95 % 9 { LH_A2, LL_A5 } ==> { VH_A1 } 87 % 100 % CSDL giao dịch nén, và Bảng định lượng 1 { B3 } ==> { A4 } 92 % 100 % 2 { A4 } ==> { B3 } 92 % 95 % 3 { E2 } ==> { A4 } 88 % 100 % 4 { A4 } ==> { E2 } 88 % 91 % 5 { E2 } ==> { B3 } 88 % 99 % 6 { B3 } ==> { E2 } 88 % 95 % 7 { B3, E2 } ==> { A4 } 87 % 100 % 8 { A4, E2 } ==> { B3 } 87 % 99 % 9 { A4, B3 } ==> { E2 } 87 % 95 % Bảng 2.10: Luật kết hợp thu được với độ hỗ trợ 90% và độ tin cậy 80% STT Luật kết hợp Đỗ hỗ trợ Độ tin cậy CSDL không nén 1 { LH_A2 } ==> { VH_A1 } 92 % 99 % 2 { VH_A1 } ==> { LH_A2 } 92 % 95 % CSDL giao dịch nén, không Bảng định lượng 1 { LH_A2 } ==> { VH_A1 } 92 % 100 % 2 { VH_A1 } ==> { LH_A2 } 92 % 95 % CSDL giao dịch nén, và Bảng định lượng 1 { B3 } ==> { A4 } 92 % 100 % 2 { A4 } ==> { B3 } 92 % 95 % 54 Trong Hình 2.3 so sánh thời gian thực thuật toán Apriori mờ với CSDL không nén và thời gian thực hiện với CSDL nén nhưng không sử dụng bảng định lượng. Hình 2.5: Thời gian thực hiện với CSDL nén và CSDL không nén Trong Hình 2.5 so sánh thời gian thực hiện thuật toán cùng với CSDL nén có sử dụng bảng định lượng và CSDL nén không sử dụng bảng định lượng. Kết quả thử nghiệm với độ tin cậy là 80%, luận án thử nghiệm với hai thuật toán: Luật kết hợp theo cách tiếp cận của ĐSGT [2] và thuật toán luận án đề xuất là nén CSDL mờ theo hướng tiếp cận ĐSGT. Kết quả thử nghiệm cho thấy phương pháp đề xuất nén CSDL cho kết quả nhanh hơn với phương pháp đề xuất trong [2] và giá trị của các tập phổ biến tìm được giống với khi chúng ta sử dụng CSDL không nén. 2.6. Kết luận chương 2 Trong chương này luận án nghiên cứu ĐSGT và phát triển thuật toán nén CSDL giao dịch sử dụng cho bài toán khai phá luật kết hợp mờ. Với cách tiếp cận này, các giao dịch gần nhau được gộp lại để tạo thành giao dịch mới, làm giảm kích thước của CSDL đầu vào. Thuật toán nén CSDL giao dịch được thử nghiệm trên CSDL: FAM95 và STULONG. Kết quả thử nghiệm với 2 CSDL cho thấy phương pháp đề xuất nén CSDL cho kết quả nhanh hơn với phương pháp đề xuất trong [2] và giá trị của các tập phổ biến tìm được giống với khi chúng ta sử dụng CSDL không nén. Nội dung của chương này được công bố trong các công trình [i, ii]. 0 100 200 300 400 500 600 700 800 5% 10% 20% 30% 40% 50% 60% 70% 80% T IM E ( S E C O N D ) MINIMUM SUPPORT CSDL không nén CSDL nén không sử dụng bảng định lượng 55 Trong chương này, luận án sử dụng ĐSGT với các biểu diễn đơn thể hạt cho các thuộc tính với tham số giống nhau. Để nâng cao hiệu quả khai phá luật kết hợp và để tìm ra các luật có ý nghĩa hơn, trong chương 3 luận án nghiên cứu và đề xuất phương pháp tối ưu các tham số mờ cho phù hợp với từng thuộc tính với biểu diễn đơn thể hạt và đa thể hạt. 56 CHƯƠNG 3. PHÂN HOẠCH MỜ CHO THUỘC TÍNH DỰA TRÊN BIỂU DIỄN THỂ HẠT CỦA ĐSGT Mục tiêu chính của khai phá luật kết hợp là tìm ra các mối liên hệ giữa các tập mục trong CSDL. Trong bài toán khai phá luật kết hợp mờ sử dụng lý thuyết tập mờ cho các thuộc tính định lượng. Việc thiết kế phân hoạch mờ trên miền thuộc tính cho bài toán khai phá luật kết hợp có vài trò hết sức quan trọng đối kết quả của các luật kết hợp mờ thu được. Trong chương này, luận án trình bày một số cách phân chia miền mờ và đề xuất phương pháp phân chia miền mờ bằng cách sử dụng lý thuyết ĐSGT dựa trên biểu diễn đơn thể hạt và đa thể hạt. ĐSGT cho phép mô hình hoá và thiết kế các từ ngôn ngữ cùng với ngữ nghĩa dựa trên tập mờ. Luận án đề xuất thuật toán tối ưu các hàm thuộc được xây dựng dựa trên lý thuyết ĐSGT cho bài toán khai phá luật kết hợp mờ. Các kết quả thử nghiệm cho thấy kết quả của các phương pháp đề xuất có một số ưu việt hơn một số phương pháp đã đề xuất trước đây. 3.1. Phân hoạch cho miền giá trị của thuộc tính 3.1.1. Đặt vấn đề Bài toán phân chia miền xác định các thuộc tính định lượng của một tập dữ liệu đầu vào như sau: Cho miền xác định của một thuộc tính (ở đây chỉ xét thuộc tính định lượng). Mỗi thuộc tính định lượng có một miền xác định (hoặc miền giá trị) là miền trên trục số thực bao gồm các giá trị mà thuộc tính định lượng đó có thể nhận. Thí dụ tuổi có thể nhận các giá trị từ 0 đến 120. Yêu cầu là phải phân chia miền thuộc tính ra thành các hạt và mỗi hạt có nhãn ngôn ngữ biểu thị bằng tập mờ. Việc phân chia này là cần thiết vì sử dụng tập mờ với nhãn ngôn ngữ phù hợp với cách con người sử dụng ngôn ngữ và để tương tác với người dùng. Việc phân chia có thể là rời rạc nhưng xu hướng chung là phân chia thành các miền có giao nhau rõ hay mờ vì nó mang tính hợp lý hơn. Chẳng hạn, với thuộc tính “khoảng cách”, việc phân chia rời rạc có thể là [0 km, 50 km] là “gần”; [51km, 100 km] là “trung bình”; [100 km, 200 km] là “xa”, nhưng như vậy thì khoảng cách 50km và 51 km rất gần nhau nhưng lại thuộc hai nhãn khoảng cách khác nhau không thật hợp lý. Với phân 57 chia mờ, ta coi các nhãn “gần”, “trung bình”, “xa” là các tập mờ, khi đó một