Đề tài Khai phá dữ liệu sử dụng luật kết hợp mờ

lớn. Vì vậy các tập ứng cử viên có k mục có thể được sinh ra bằng cách kết nối các tập mục lớn có k-1 mục và xoá các tập ứng cử viên nếu nó chứa bất kỳ một tập con nào mà không phải là lớn. Thủ tục này nói chung dẫn đến một số nhỏ hơn nhiều các tập ứng cử viên, nói cách khác nó là khá hiệu quả trong việc “tỉa gọn” không gian tìm kiếm. Thuật toán AprioriTid có thêm tính chất bổ sung là CSDL không được sử dụng toàn bộ để tính hỗ trợ của các tập ứng cử viên sau lần duyệt đầu tiên. Hơn nữa, việc mã hoá của các tập ứng cử viên được sử dụng ở lần duyệt trước được dùng với mục đích này (việc mã hoá này cho ta biết những ứng cử viên nào có mặt trong những thao tác vụ nào). Ở các lần duyệt sau đó, kích cỡ của việc mã hoá này sẽ có thể nhỏ hơn rất nhiều so với CSDL, vì vậy việc đọc được tiết kiệm rất nhiều. Ký hiệu: Ta quy ước sử dụng bảng chữ cái theo thứ tự từ điển để đặt tên cho các mục trong các tác vụ và các tập mục, ta gọi số các mục trong một tập mục là kích thước của tập mục này, gọi một tập mục có kích thước k là k-tập mục. Ta sử dụng các ký hiệu c[1].c[2]c[k] để biểu diễn k-tập mục c gồm các mục c[1], c[2], , c[k] ở đây c[1] < c[2] < < c[k]. Mỗi một tập mục được gắn với một trường tính toán để lưu độ hỗ trợ đối với tập mục này. k-tập mục một tập mục có k mục Lk Tập của các k-tập mục lớn (với độ hỗ trợ cực tiểu). Mỗi một phần tử của tập này có 2 trường: i) tập mục và ii) tính độ hỗ trợ. Ck Tập của các k-tập mục ứng cử viên (tiềm năng là tập mục lớn). Mỗi phần tử của tập này có 2 trường: i) tập mục và ii) tính độ hỗ trợ. k Tập của các k-tập mục ứng cử viên khi các TID của các tác vụ sinh ra được liên kết với các ứng cử viên. Thuật toán Apriori và AprioriTid: * Ý tưởng tiếp cận: Giải thuật này sử dụng đặc tính bất cứ tập con nào của một tập mục lớn cũng phải là một tập mục lớn. Do vậy, giả thiết rằng các mục trong một tập mục được sắp xếp thứ tự. Giải thuật Apriori sẽ sản sinh ra các itemset ứng cử viên bằng cách kết hợp các itemset lớn của bước trước và xoá những tập con nào là nhỏ của bước trước mà không cần quan tâm tới các giao dịch trong cơ sở dữ liệu. Bằng việc chỉ xem xét những tập mục lớn ở bước trước, số lượng các itemset ứng cử viên được giảm đi đáng kể. * Giải thuật: Hình dưới đây đưa ra giải thuật Apriori. Bước đầu tiên của giải thuật là tính toán ra các 1-itemset lớn. Các bước tiếp theo, gọi là bước lặp k bao gồm 2 pha. Pha 1, các tập mục lớn Lk-1 trong bước thứ k-1 được dùng để sinh ra các tập mục ứng cử viên Ck, sử dụng hàm apriori-gen được miêu tả trong phần sau. Pha 2, quét cơ sở dữ liệu và tính toán độ support của các ứng cử viên trong Ck. L1 = {1-tập mục lớn} For (k = 2; Lk-1 ¹ Æ; k++) do begin Ck = Apriori-gen(Lk-1); // các ứng cử viên mới For tất cả các tác vụ t Î D do begin Ct = Subset(Ck, t); // ứng cử viên được chứa trong t For tất cả các ứng cử viên c Î Ct do c.tính++ end Lk = {c Î Ck|c.tính ³ minSup} end Kết quả = ÈLk Giải thích: Lần duyệt đầu tiên của thuật toán sẽ tính số lần xuất hiện của mỗi mục để xác định các 1-tập mục lớn. Lần duyệt thứ k (k ³ 2) sẽ bao gồm 2 giai đoạn: Giai đoạn 1: tập mục lớn Lk-1 đã được tìm thấy ở lần duyệt thứ k-1 được sử dụng để sinh ra các tập ứng cử viên Ck bằng việc sử dụng hàm Apriori-gen sẽ được giải thích ở dưới. Giai đoạn 2: Dựa vào CSDL, tính độ hỗ trợ của các ứng cử viên trong Ck. Các ứng cử viên trong Ck mà được chứa trong tác vụ t có thể được xác định một cách hiệu quả bằng việc sử dụng Cây băm cũng sẽ được mô tả ngay dưới đây. Sinh ra ứng cử viên Apriori: Hàm Apriori-gen lấy Lk-1 là tập tất cả (k-1)-tập mục lớn làm đối số, nó cho kết quả là tập tất cả k-tập mục lớn. Trong giai đoạn 1 (giai đoạn kết nối): người ta kết nối Lk-1 với Lk-1 để nhận được tập các ứng cử viên Ck. Hợp pÈq của các tập mục p, q Î Lk-1 được chèn vào trong Ck nếu chúng có chung (k-2) mục đầu tiên: insert into Ck select p[1], p[2],, p[k-1], q[k-1] from Lk-1p, Lk-1q where p[1] = q[1], p[2] = q[2],, p[k-2] = q[k-2], p[k-1] < q[k-1]; Trong giai đoạn 2 (giai đoạn sửa, tỉa): xoá bỏ tất cả các tập mục c Î Ck sao cho một vài (k-1)-tập con của c không nằm trong Lk-1. Thủ tục sinh này là đầy đủ bởi đối với bất kỳ tập mục nào trong Lk với độ hỗ trợ tối tiểu thì các tập con kích cỡ (k-1) cũng có độ hỗ trợ tối tiểu, do đó nếu ta mở rộng một tập mục trong Lk-1 với tất cả các mục có thể và sau đó xoá tất cả các tập mà (k-1)-tập con của nó không nằm trong Lk-1, ta sẽ nhận được tập các tập mục trong Lk. Việc kết nối là tương đương với việc mở rộng Lk-1 với mỗi mục nằm trong CSDL và sau đó xoá bỏ các tập mục này mà đối với nó (k-1)-tập mục nhận được bằng việc xoá đi mục thứ (k-1) không nằm trong Lk-1. Vì vậy tại giai đoạn này Ck Ê Lk. Với lập luận như vậy giai đoạn tỉa, là giai đoạn người ta xoá khỏi Ck tất cả các tập mục mà các (k-1) tập mục con của nó không nằm trong Lk-1, cũng không xoá bất kỳ một tập mục nào có thể nằm trong Lk. Hàm Subset: Các tập ứng cử viên Ck được lưu trữ trong một cây băm. Một nút của cây này hoặc là chứa một danh sách của các tập mục (nút lá) hoặc một bảng băm (một nút trong). Trong mỗi một nút trong, mỗi bucket của bảng băm chỉ đến một nút khác. Gốc của cây băm được xem ở độ sâu là 1. Một nút trong ở độ sâu d sẽ dẫn đến nút ở độ sâu d+1. Các tập mục được lưu trữ trong các lá. Khi ta bổ sung thêm một tập mục c, ta bắt từ nút gốc và đi xuống cây cho đến khi ta trạm vào một lá. Tại băm đối với mục thứ d của tập mục đó và theo con trỏ trong bucket tương ứng. Tất cả các nút ban đầu được tạo ra như là nút lá. Khi số các tập mục trong một nút lá vượt quá ngưỡng được chọn, nút là này được chuyển thành một nút trong. Bắt đầu từ nút gốc, hàm Subset tìm tất cả các ứng cử viên được chứa trong tác vụ t như sau: Nếu ta bắt đầu tại một lá, ta tìm những tập mục trong nút lá này được chứa trong tác vụ t và bổ sung các mối quan hệ với chúng đối với tập kết quả mong muốn. Nếu ta đang ở một nút trong và ta đến được nó bằng việc băm mục i, ta băm trên mỗi mục đi sau i trong t và áp dụng một cách đệ qui thủ tục đó đối với nút này trong bucket tương ứng. Đối với nút gốc, ta băm theo mỗi mục trong t. Để thấy được tại sao hàm Subset trả lại tập các tham khảo mong muốn, hãy để ý đến những gì sẽ xảy ra tại nút gốc. Đối với bất kỳ tập mục c nào được chứa trong tác vụ t, mục đầu tiên của c cần phải có trong t. Tại nút gốc, việc băm mọi mục trong t đảm bảo được rằng ta chỉ không biết các tập mục mà nó bắt đầu với một mục không nằm trong t. Những lý luận tương tự áp dụng cho các mức sâu hơn. Vì các mục trong bất kỳ tập mục nào cũng được sắp thứ tự, nếu ta đến được một nút hiện tại bằng việc băm mục i, ta chỉ cần quan tâm đến những mục trong t nó xuất hiện sau i. Thuật toán AprioriTid: * Ý tưởng tiếp cận: Một đặc điểm cần chú ý của giải thuật đó là cơ sở dữ liệu D không được sử dụng để tính toán độ support sau bước lặp đầu tiên. Thay vào đó, tập k được sử dụng cho mục đích này. Mỗi phần tử trong k có dạng (TID, {Xk}), với mỗi Xk là một k-itemset có khả năng là lớn trong giao dịch với định danh là TID. Với k=1, 1 tương ứng với cơ sở dữ liệu D, tuy nhiên mỗi mục i được thay thế bởi tập mục {i}. Với k>1, k được tạo ra bởi giải thuật(bước 10). Mỗi phần tử thuộc k tương ứng với giao dịch t là (t.TID, {c Ck | c được chứa trong t}). Nếu một giao dịch không chứa bất kỳ một k-itemset ứng cử viên nào thì k sẽ không có một phần tử đầu vào nào với giao dịch đó. Do vậy, kích cỡ của k sẽ nhỏ hơn số lượng giao dịch trong cơ sở dữ liệu, đặc biệt với giá trị số k rất lớn. Ngoài ra, với giá trị số k rất lớn, mỗi đầu vào sẽ nhỏ hơn giao dịch tương ứng, bởi vì rất ít các ứng cử viên có thể có trong giao dịch. * Thuật toán: Giải thuật AprioriTid được chỉ ra ở hình dưới đây, giải thuật này cũng sử dụng hàm apriori-gen(Hàm này đã được miêu tả trong phần trên) để xác định ra các tập mục ứng cử viên trước khi một bước lặp bắt đầu. Trước tiên, toàn bộ cơ sở dữ liệu được quét và tìm ra . Điều này có nghĩa là mỗi thành phần trong đều gắn liền với một TID. Tập mục lớn L1 được xác định thông qua việc tính toán số lượng thành phần trong . Sau đó, dùng hàm apriori_gen() để sinh ra C2. xác định được tương ứng với một giao dịch T khi xem xét các thành phần của C2 xuất hiện trong T. Để thực hiện điều này, sẽ được quét thay cho cơ sở dữ liệu. Sau đó thì L2 sẽ được xác định thông qua việc tính toán độ support trong . Quá trình này tiếp tục cho tới khi không còn tập mục ứng cử viên nào được tìm ra. L1 = {1-tập mục lớn} 1 = CSDL D For (k = 2; Lk-1 ¹ Æ; k++) do begin Ck = Apriori-gen(Lk-1); // các ứng cử viên mới. k = Æ For tất cả t Î Ôk-1 do begin // xác định các ứng cử viên được chứa trong tác vụ t.TID Ct = {c Î Ck | (c[1].c[2].c[3]c[k-1]) Î t.tập của các mục Ù (c[1].c[2].c[3]c[k-1].c[k]) Î t.tập của các tập mục}; For tất cả các ứng cử viên c Î Cơ sở tri thức do c.tính++ if (Ct ¹ Æ) then Ôk: = ; end Lk = {c Î Ck | c.tính ³ minSup} end Kết quả = È Lk Cái mới của thuật toán này ở chỗ: CSDL D không được sử dụng để hỗ trợ tính đếm sau lần duyệt đầu tiên. Hơn nữa k được sử dụng đối với mục đích này. Mỗi phần tử của tập k có dạng , ở đây Xk là k-tập mục lớn tiềm năng có mặt trong tác vụ được nhận biết bởi TID. Đối với k = 1, 1 ứng với tác vụ t là . Nếu tác vụ không chứa bất kỳ k-tập ứng cử viên nào, k sẽ không có một mục đưa vào đối với tác vụ này. Vì vậy số các mục đưa vào trong k có thể nhỏ hơn số các tác vụ trong CSDL, đặc biệt khi k là lớn. Tuy nhiên đối với các giá trị k nhỏ số cá mục đưa vào có thể lớn hơn tác vụ tương ứng do các mục đưa vào trong Ck bao gồm tất cả k-tập mục ứng cử viên được chứa trong tác vụ này. Sinh ra các luật: Với mỗi tập mục lớn l, ta sinh ra tất cả các luật dạng a Þ (1-a) ở đây a là tập con của l sao cho support(l)/support(a) ³ minSup. Do support (a*) ³ support (a) với bất kỳ a* Ì a, vì vậy độ tin tưởng của luật a* Þ (1-a*) không thể lớn hơn độ tin tưởng của luật a Þ (1-a), do đó nếu luật a Þ (1-a) không được chấp nhận thì luật a* Þ (1-a*) cũng vậy. Điều này cũng dẫn đến kết luận là nếu luật (1-a) Þ a được chấp nhận thì luật (1-a*) Þ a* cũng được chấp nhận với bất kỳ a* Ì a. Vì thế từ một tập mục lớn l, trước hết ta sinh ra tất cả các luật có 01 mục ở vế phải, sau đó ta sử dụng các vế phải của các luật này và hàm Apriori-gen để sinh ra tất cả các vế phải có thể được bao gồm 2 mục, 3 mục Thuật toán dưới đây mô tả ý tưởng này. 1. For tất cả các k-tập mục lớn lk do begin 2. H1 = {các vế phải của các luật từ lk có 01 mục ở vế phải} 3. Gọi thủ tục Ap-genluat(lk, Hl) 4. end 5. Procedure Ap-genluat (lk: k-tập mục lớn, Hm: tập các vế phải gồm m mục) 6. If (k>m+1) then begin 7. Hm+1 = Apriori-gen(Hm); 8. For tất cả hm+1 Î Hm+1 do begin 9. Conf = support(lk)/support(lk – hm+1) 10. ifConf ³ minSup then 11. Chấp nhận luật lk – hm+1 với độ tin tưởng là Conf, độ hỗ trợ là Support(lk); 12. else 13. Delete hm+1 khỏi Hm+1; 14. end 15. Gọi thủ tục Ap-genluat(lk, Hm+1); 16. end Ví dụ minh hoạ CSDL 1 L1 TID Các mục TID Tập các tập mục Tập mục Hỗ trợ 100 200 300 400 1 3 4 2 3 5 1 2 3 5 2 5 100 200 300 400 {{1}, {3}, {4}} {{2}, {3}, {5}} {{1}, {2}, {3}, {5}} {{2}, {5}} {1} {2} {3} {5} 2 3 3 3 C2 2 L2 Tập mục Hỗ trợ TID Tập các tập mục Tập mục Hỗ trợ {1 2} {1 3} {1 5} {2 3} {2 5} {3 5} 1 2 1 2 3 2 100 200 300 400 {{1 3}} {{2 3}, {2 5}, {3 5}} {{1 2}, {1 3}, {1 5}, {2 3}, {2 5}, {3 5}} {{2 5}} {1 3} {2 3} {2 5} {3 5} 2 3 3 2 C3 3 L3 Tập mục Hỗ trợ TID Tập các tập mục Tập mục Hỗ trợ {2 3 5} 2 200 300 {{2 3 5}} {{2 3 5}} {2 3 5} 2 Giải thích: Xét CSDL đã cho vào thừa nhận là độ hỗ trợ cực tiểu minSup = 2. Việc gọi hàm Apriori-gen với L1 ở bước 4 cho các tập mục ứng cử viên C2. Trong các bước từ 6 đến 10 ta tính độ hỗ trợ của ứng cử viên trong C2 bằng cách lặp trên các mục đưa vào trong 1 và sinh ra 2. Các mục đưa vào đầu tiên trong 1 là {{1}, {3}, {4}} tương ứng với tác vụ 100. Ct tại bước 7 ứng với mục đưa vào này là {{1 3}} bởi vì {1 3} là phần tử của C2 và ({1 3}-{1}) và ({1 3}-{3}) là các phần tử của t. Việc gọi Apriori-gen với L2 cho C3. Thực hiện lần duyệt trên dữ liệu với 2 và C3 sinh ra Ô3. Lưu ý là không có các mục nào trong 3 đối với các tác vụ với TID là 100 và 400 vì chúng không chứa bất kỳ một tập mục nào trong C3. Tập ứng cử viên {2 3 5} trong C3 là lớn và là phần tử của L3. Khi ta sinh ra C4 bằng sử dụng L3 nó trả lại tập rỗng và ta kết thúc. Luật kết hợp mờ Tập mờ (Fuzzy Set) Trong phần này chúng ta bắt đầu tìm hiểu những khái niệm cơ bản nhất: định nghĩa mờ của L.Zadeh (1965), các phép toán đại số, nguyên lý suy rộng, số mờ và sau đó là khái niệm biến ngôn ngữ, các phép toán bước đầu của logic mờ, suy diễn mờ và hệ mờ trên cơ sở các luật mờ. Một số dạng phát triển ứng dụng quan trọng cũng sẽ được lướt nhanh để tạo điều kiện cho các bạn mới học lần đầu có cái nhìn tổng quan về hệ mờ và ứng dụng. Định nghĩa mờ Xét tập X Æ. Ta sẽ gọi X là không gian nền. Chẳng hạn: X = tập sinh viên Đại học Bách khoa Hà Nội khóa 41. A1 = tập sinh viên Khoa Công nghệ thông tin khóa 41. Khi đó A1 là một tập con rõ của X. Gọi: A2 = tập sinh viên giỏi Tin, khoá 41 của Khoa Cơ khí. Khi đó A2 là một tập mờ trên X. Một minh họa khác về tập mờ về vết vân tay của tội phạm để lại trên hiện tượng. Định nghĩa 1 : A là tập mờ trên không gian nền X nếu A được xác định bởi hàm mA: X ® [0,1] X mA(1) = 1 x mA(2) = 0.7 mA là hàm thuộc (membership function) còn mA() là độ thuộc của vào tập mờ A. x Ví dụ 1 về tập mờ Hình 2 Nhiều tài liệu vẫn quen ký hiệu mA(mA(). Tuy nhiên, để gọn đôi khi cần ta sẽ ký hiệu A() thay cho mA(). Chúng ta cũng sẽ kí hiệu: Ví dụ 2: A0 = một vài (quả cam) = {(0/0), (0/1), (0.6/2), (1/3), (1/4), (0.8/5), (0.2/6)} Ví dụ 3: A = “số thực gần 10” có hàm thuộc . Ta sẽ kí hiệu: F(X) = {A tập mờ trên X} Định nghĩa 2: Giá của tập mờ A, S(A) là tập các điểm nào có nào có mA() >0. Với mỗi 0£a£1 tập mức Aa cho bởi: Để ý Aa là tập con rõ của X. Mệnh đề 1: Cho A là tập mờ. Khi đó: với nếu (Ở đây sup – là cận trên đúng của một trên đường thẳng số thực. Bạn nào chưa quen có thể thay bằng max, hoặc hỏi thêm thầy dạy Toán). Chứng minh: Cho 0 < a £ 1 cố định. Với có mA() = 0. Do Aa, nên mAa() = 0. Vậy: =0 = mA(). Với có mA() = a > 0. Ta xét 3 trường hợp: - Nếu a < a’, mA() = 1, nên min (amAa()) = a < a’ - Nếu a = a’, mA() = 1, nên min (amAa()) = a = a’ - Nếu a > a’, mA() = 1, nên min (amAa()) = 0. Vậy = a’ = mA(). Các phét toán đại số trên tập mờ Định nghĩa 3: Cho A, B là hai tập mờ trên không gian nền X, có các hàm thuộc mA, mB. Khi đó phép hợp AÈB, phép giao AÇB và phần bù AC là các tập mờ trên X với các hàm thuộc cho bởi: Định nghĩa 4: Cho A, B ÎF(X). Ta nói: AÍB, nếuvới mọi x ÎX AÊB, nếuvới mọi x ÎX Do đó: A = B, nếu với mọi x ÎX Dễ dàng kiểm tra mệnh đề sau: Mệnh đề 2: Cho A, B Î F(X). Khi đó: (AÈB)a = Aa ÈBa và (AÇB)a = AaÇBa. Ta sẽ coi Æ là tập mờ với mÆ (x) =0 với mọi x. X là tập mờ với mX(x) = 1, với mọi x. Với các tập mờ nhiều tính chất của tập rõ còn đúng. Mệnh đề sau sẽ minh hoạ điều đó. Mệnh đề 3: Cho A, B, C Î F(X). Ta có các tính chất: a) Giao hoán: AÈB = BÈA, AÇB = BÇA b) Kết hợp: AÈ (BÈC) = AÈ (BÈC) AÇ (BÇC) = AÇ (BÇC) c) Luỹ đẳng: AÈA = A, AÇA = A d) Phân phối: AÈ(BÇC) = (AÈB) Ç (AÈC) AÇ(BÈC) = (AÇB) È(AÇC) e) AÇÆ = Æ và A ÈX = X f) Đồng nhất: A ÈÆ = A và AÇX = A g) Hấp thu AÈ(AÇB) = A và AÇ(AÈB) = A h) Luật De Morgan (AÈB)C = AC ÇBC và (AÇB)C = AC ÈBC i) Cuộn: (AC)C = A j) Dạng tương đương: (ACÈB) Ç (AÈBC) = (ACÇBC) È (AÇB) k) Hiệu đối xứng: (ACÇB) È (AÇBC) = (ACÈBC) Ç (AÈB) Số mờ Chúng ta sẽ dùng các số mờ theo định nghĩa sau: Định nghĩa 6: Tập mờ M trên đường thẳng số thực R1 là một số mờ, nếu M chuẩn hoá, tức là có điểm x’ sao cho mM(x’) = 1. Ứng với mỗi a ÎR1, tập mức {x:mM(x) ³a} là đoạn đóng trên R1. mM(x) là hàm liên tục Người ta có thường dùng các số mờ dạng tam giác, hình thang và dạng hàm Gauss. Số mờ tam giác được xác định bởi 3 tham số. Khi đó hàm thuộc của số mờ tam giác M(a,b,c) cho bởi : mM(z) = 0 nếu z £ a z-a/b-a nếu a £ z £ b 1 nếu z=b z-b/c-b nếu b £ z £ c 0 nếu c £ z Còn số mờ hình thang M(a,b,c,d) được xác định bởi 4 tham số có hàm thuộc dạng sau: mM(z) = 0 nếu z £ a z-a/b-a nếu a £ z £ b 1 nếu b£ z £ c z-c/d-c nếu c £ z £ d 0 nếu d £ z Còn hàm thuộc của số mờ dạng hàm Gauss (dạng hình chuông) cho bởi: nếu nếu da là số dương được chọn thích hợp Định lý 1 (Doubois, Prade 1980): Nếu M, N là 2 số mờ thì phép cộng suy rộng M Å N có hàm thuộc cho bởi. mMÅN(z) = max (min (mM(x), mN(y)): x +y = z), với mọi z, cũng là số mờ. Khi M, N là 2 số mờ hình thang M (am, bm, cm, dm), N (an, bn, cn, dn) thì: MÅN (am + an, bm + bn, cm + cn, dm + dn). Định nghĩa tập mờ đối: Nếu A là tập mờ trên R1 với hàm thuộc mA(z) thì tập đối – A cũng là tập mờ trên R1 có hàm thuộc cho bởi m-A(z) = mA(-z). Nhận xét nếu M là số mờ thì –M cũng là số mờ. Hơn nữa M là số mờ hình thang thì –M cũng là số mờ hình thang. Định nghĩa phép trừ suy rộng: Cho M, N là 2 số thì ta có thể định nghĩa. M-N = M Å (-N). Logic mờ Bất kỳ một người nào có ít nhiều tri thức đều hiểu rằng ngay trong những suy luận đời thường cũng như trong các suy luận khoa học chặt chẽ, logic toán học đã đóng vai trò rất quan trọng. Nhưng đáng tiếc, chiếc áo logic toán học cổ điển đã quá chật đối với những ai mong muốn tìm kiếm những cơ sở vững chắc cho những suy luận phù hợp với những bài toán nảy sinh từ nghiên cứu và thiết kế những hệ thống phức tạp, đặc biệt là những cố gắng đưa những suy luận giống như cách con người vẫn thường sử dụng vào các lĩnh vực trí tuệ sáng tạo (chẳng hạn, trong các hệ chuyên gia, các hệ hỗ trợ quyết định, các bộ phần mềm lớn, v.v...) hay vào trong công việc thiết kế và điều khiển, vận hành các hệ thống lớn, phức tạp sao cho kịp thời và hiệu quả. Trong sự phát triển đa dạng của các hệ mờ, dựa trên cách tiếp cận mới của lý thuyết tập mờ, logic mờ giữ một vai trò rất cơ bản. Trong chương trình này chúng em sẽ hiểu logic mờ theo nghĩa đủ “hẹp’ – đó là phần trực tiếp suy rộng logic mệnh đề cổ điển thông qua việc trình bày một số công cụ chủ chốt của lôgic mờ: các liên kết logic cơ bản. Một số phép toán cơ bản của logic mờ Phép phủ định Bây giờ chúng ta cho dạng toán học của phép toán này. Định nghĩa 7 : Hàm n: [0,1] ® [0,1] không tăng thỏa mãn các điều kiện n(0) = 1, n(1) = 0, gọi là hàm phủ định (negation – hay là phép phủ định). Chúng ta có thể xét thêm vài tiên đề khác. Định nghĩa 8 : i, Hàm phủ định n là chặt nếu nó là hàm liên tục và giảm chặt ii, Hàm phủ định n là mạnh nếu nó là chặt và thỏa mãn n (n(x)) = x " [0,1]. Ta hãy cho vài ví dụ và tính chất. Hàm phủ định thường dùng n(x) = 1- x (Zadeh [2]). Hàm n (x) = 1 – x2 Họ phủ định (Sugeno) Nl(x) = (1-x) / (1 + lx), với l > - 1 Rõ ràng (1-x) là phủ định mạnh, còn (1-x)2 là một phủ định chặt, nhưng không mạnh. Còn với họ Sugeno ta có mệnh đề sau: Mệnh đề 4: Với l - 1, Nl(x) là hàm phủ định mạnh. Định nghĩa 9: Cho n là hàm phủ định, phần bù AC của tập mờ A là một tập mờ với hàm thuộc cho bởi AC(a) = n(A(a)), với mỗi aÎW. Rõ ràng định nghĩa phần bù cho trong phần 1.1 là trường hợp riêng khi n(x) là hàm phủ định thường dùng. Phép hội Phép hội (vẫn quen gọi là phép AND – conjunction) là một trong mấy phép toán logic cơ bản nhất. Thông thường người ta xét các tiên đề sau: tđ1. v(P1 AND P2) chỉ phụ thuộc vào v(P1), v(P2) tđ2. Nếu v(P1) = 1 thì v(P1 AND P2) = v(P2), với mọi mệnh đề P2. tđ3. Giao hoán: v(P1 AND P2) = v(P2 AND P1) tđ4. Nếu v(P1) £ v(P2), thì v(P1 AND P3) £ v(P2 AND P3), với mọi mệnh đề P3 tđ5. Kết hợp: v(P1 AND (P2 AND P3) = v(P1 AND P2) AND P3) Khi diễn đạt phép hội mờ như một hàm số T: [0,1]2 ® [-0,1], chúng ta cần tới định nghĩa sau: Định nghĩa 10: Hàm T: [0,1]2 ® [-0,1] là một t – chuẩn (chuẩn tam giác hay t – norm) nếu thỏa mãn các điều kiện sau: T(1,x) = x, với mọi 0 £ x £ 1 T có tính giao hoán, tức là T(x,y) = T(y,x), với mọi 0£x,y£1, T không giảm theo nghĩa T(x,y)£ T(u,v), với mọi x £ u,y£v, T có tính kết hợp : T(x,T(y,z)) = T(T(x,y,z) với mọi 0 £x,y,z£ 1 Từ những tiên đề trên chúng ta suy ra ngay T(0,x). Hơn nữa tiên đề d) đảm bảo tính thác triển duy nhất cho hàm nhiều biến. Mệnh đề 5: Với t – chuẩn T thì: T5(x,y) £ T(x,y) £T1(x,y) = min(x,y) với mọi 0£x,y£1 Chứng minh : Thật vậy Nếu max(x,y) = 1 Khi x = 1, T(1,y) = y = min (x,y) hay T5(x,y) = T(x,y) = T1(x,y). Tương tự nếu y = 1. Nếu max(x,y)<1, T5(x,y) = 0 <T(x,y) Giả sử y = min(x,y), khi đó T(x,y) £T(1,y) = y =T1(x,y). Tương tự nếu x = min (x,y). Định nghĩa 11 : a. Một t – chuẩn T gọi là tiên tục nếu T là hàm liên tục trên [0,1]2. b. Hàm T gọi là Archimed nếu T(x,y)<x với mọi 0<x<1. c. Hàm T gọi là chặt nếu T tăng chặt trên (0,1)2 Định lý 2 : Cho T là một t-chuẩn, ta xác định Tf :[0,1] ´ [0,1] ® [0,1] bằng định nghĩa : Tf(x,y)=f-1(T(f(x),f(y))), với mọi 0 £x,y£1. Khi đó Tf là một t-chuẩn. Nếu T là Archimed thì Tf là Archimed. Định nghĩa 12: Ứng với t-chuẩn T, tập giao của hai tập mờ A,B là tập mờ (AÇTB) trên X với hàm cho bởi : (AÇTB)(x) = T(A(x),B(x)), "xÎX Việc lựa choạn phép giao tương ứng với t-chuẩn T nào tùy thuộc vào bài toán được quan tâm. Phép tuyển Giống như phép hội, phép tuyển hay toán tử logíc OR(disjunction) thông thường cần thỏa mãn các tiên đề sau : Định nghĩa 13 : Hàm S : [0,1]2 ® [0,1] gọi là phép tuyển (OR suy rộng) hay là t-đối chuẩn (t-conorm) nếu thỏa mãn các tiên đề sau : S(0,x) = x với mọi x Î[0,1] S có tính giao hoán: S(x,y) = S(x,y) với mọi 0 £ x,y £ 1 S không giảm:S(x,y) £ S(u,v) với mọi 0 £ x£u £ 1 và 0 £ y£v £ 1 S có tính kết hợp: S(x,S(y,z)) = S(S(x,y),z) với mọi 0£x,y,z£1 Từ định nghĩa ta thấy: S(0,1)£S(x,1) Û 1£S(x,1)£1 => S(x,1) = 1 Định lý 3: Với S là một t-đối chuẩn bất kỳ thì bất đẳng thức sau luôn đúng với x,yÎ[0,1]: S0(x,y) £ S(x,y) £S4(x,y) b) S0 £ S1 £ S2 £ S4 Mệnh đề 6: Nếu S là t-đối chuẩn thì: max(x,y) £ S(x,y) £ Z’(x,y) với mọi 0 £ x,y £ 1. Định nghĩa 14: Cho S là t-đối chuẩn. Khi ấy : S gọi là liên tục nếu S là hàm liên tục trên [0,1]2 Hàm S gọi là Archimed nếu S(x,x) > x với mọi 0 < x < 1 S gọi là chặt nếu S tăng chặt trên (0,1)2 Định lý 4: Cho S là một t-đối chuẩn, ta xác định: Sf: [0,1] ´ [0,1] ® [0,1] Sf(x,y)= f-1(S(f(x), f(y))). Khi đó Sf là một t-đối chuẩn. Nếu S là Archimed thì Sf là Archimed. Định nghĩa 15: Cho A và B là 2 tập mờ trên không gian nền X, với hàm thuộc A(x), B(x) tương ứng. Cho S là một t-đối chuẩn. Phép hợp (AÈSB) là một tập mờ trên X với hàm thuộc cho bởi biểu thức: (AÈSB)(x) = S(A(x), B(x), "xÎX. Việc lựa chọn phép hợp, tương ứng với t-đối chuẩn S nào tùy thuộc vào bài toán ta quan tâm. Định nghĩa 16 : Cho T là t-chuẩn, S là t-đối, n là phép phủ định mạnh. Chúng ta nói bộ ba (T,S,n) là một bộ ba De Morgan nếu thỏa mãn một trong 2 đẳng thức sau : S(x,y) = n(T(n(x),n(y))) hay T(x,y) = n(S(n(x),n(y))) Khi ấy ta nói T và S đối ngẫu với nhau. Quan hệ đối ngẫu giữa t-chuẩn và t-đối chuẩn có thể thấy qua định lý sau. Định lý 5: Cho n là phép phủ định mạnh a) S(x,y) là một t-đối chuẩn và T(x,y) cho bởi : T(x,y) = nT(S(n(x),n(y) với mọi 0£x,y£1 Khi đó T(x,y) là một t-chuẩn. b) Đối ngẫu, cho T(x,y) là t-chuẩn và S(x,y)cho bởi S(x,y) = nT(T(n(x),n(y)) với mọi 0£x,y£1 Khi đó S (x,y) là một t-chuẩn Phép kéo theo Phép kéo theo là công đoạn chủ chốt nhất của quá trình suy diễn trong mọi lập luận xấp xỉ, bao gồm cả lập luận mờ. Phép kéo theo (Implication) được xét như một mối quan hệ, một toán tử logíc. Khi mô hình hóa có thể xét tới các tiên đề sau cho hàm v(P1ÞP2): tđ0: v(P1ÞP2) chỉ phụ thuộc vào giá trị v(P1), v(P2) tđ1: Nếu v(P1) £ v(P2) thì v(P1ÞP2) ³ v(P3ÞP2) với mọi mệnh đề P2 tđ2: Nếu v(P1) £ v(P3) thì v(P1ÞP2) £ v(P1ÞP3) với mệnh đề P1 tđ3: Nếu v(P1) = 0 thì v(P1ÞP) = 1 với mỗi mệnh đề P tđ4: Nếu v(P1) = 1 thì v(PÞP1)=1 với mỗi mệnh đề P tđ5: Nếu v(P1) =1 và v(P2) = 0 thì v(P1ÞP2) = 0 Tính hợp lí của các tiên đề này chủ yếu dựa vào lôgic cổ điển và những tư duy trực tiếp về phép suy diễn. Từ tiên đề I0 ta khẳng định sự tồn tại của hàm I(x,y) xác định trên [0,1]2, với giá trị chân lí qua biểu thức sau: v(P1ÞP2) = I (v(P1), v(P2)) Định nghĩa 17: Phép kéo theo (implication) là một hàm số I: [0,1]2 ® [0,1] thỏa mãn các điều kiện sau: Nếu x £ z thì I(x,y) ³ I (z,y) với mọi y Î [0,1] Nếu y £ u thì I(x,y) £ I (x,u) với mọi x Î [0,1] I (0,x) = 1 với mọi x Î [0,1] I (x,1) = 1 với mọi x Î [0,1] I (1,0) = 0 Một số dạng hàm kéo theo cụ thể: Định nghĩa 18: Dạng kéo theo thứ nhất. Cho S(x,y) là một t-đối chuẩn, n(x) là một phủ định mạnh. Hàm IS(x,y) xác định trên [0,1]2 bằng biểu thức: IS(x,y) = S(n(x),y), " 0£x,y£1 Rõ ràng ẩn ý sau định nghĩa này là công thức từ logic cổ điển PÞQ Û (ØPÚQ) Định lý 6: Với bất kỳ t-chuẩn T, t- đối chuẩn S và phép phủ định mạnh n nào, IS được định nghĩa như trên là một phép kéo theo. Định nghĩa 19: Dạng kéo theo thứ hai. Cho T là một t-chuẩn, hàm IT(x,y) xác định trên [0,1]2 bằng biểu thức : IT(x,y) = sup{u:T(x,u) £y, " 0£x,y£1} Định lý 7: Với bất kỳ t-chuẩn T nào, IT được định nghĩa như trên là một phép kéo theo. Định nghĩa 20: Dạng kéo theo thứ ba. Cho (T, S,n) là bộ ba De Morgan với n là phép phủ định mạnh, phép kéo theo thứ ba IS(x,y) = S(T(x,y), n(x), " 0 £ x,y £1. Quan hệ mờ Quan hệ mờ và phép hợp thành Định nghĩa 19: Cho X, Y là hai không gian nền. R gọi là một quan hệ mờ trên X x Y nếu R là một tập mờ trên X x Y, tức là có một hàm thuộc mR: X x Y ® [0,1]. Ở đây mR(x,y) = R(x,y) là độ thuộc (membership degree) của (x,y) vào quan hệ R. Định nghĩa 20: Cho R1 và R2 là hai quan hệ mờ trên X x Y, ta có định nghĩa a. Quan hệ R1 È R2 với mR1 È R2(x,y) = max {x,y}, mR2(x,y), " (x,y) Î XxY b. Quan hệ R1 Ç R2 với mR1 Ç R2(x,y) = max {x,y}, mR2(x,y), " (x,y) Î XxY Định nghĩa 21: Quan hệ mờ trên những tập mờ. Cho tập mờ A với mA(x) trên X, tập mờ B với mR(x) trên Y. Quan hệ mờ trên các tập mờ A và B là quan hệ mờ R trên XxY thỏa mãn điều kiện: mB(x,y) £ mA(x). " y Î Y và mR(x,y) £ mB(x), " x Î X. Định nghĩa 22: Cho quan hệ mờ R trên XxY Phép chiếu của R lên X là: projXR = {(x, maxymR(x,y): xÎX)} Phép chiếu của R lên Y là: projYR = {(y, maxxmR(x,y): yÎY)} Định nghĩa 23: Cho quan hệ mờ R trên XxY. Thác triển R lên không gian tích XxYxZ là: extXYZR = {(x,y,z), mext(x,y,z) = mR(x,y), "z ÎZ} Phép hợp thành Định nghĩa 24: Cho R1 là quan hệ mờ trên XxY và R2 là quan hệ mờ trên YxZ. Hợp thành R1 ° R2 của R1, R2 là quan hệ mờ trên XxZ. a. Hợp thành max-min (max-min composition) được xác định bởi mR1°R2(x,z) = maxy{min(mR1(x,y),mR2(y,z)}, "(x,z) Î XxZ. b. Hợp thành max-prod cho bởi mR1°R2(x,z) = maxy{mR1(x,y),mR2(y,z)}, "(x,z) Î XxZ. c. Hợp thành max -* được xác định bởi toán tử *: [0,1]2 ® [0,1] mR1°R2(x,z) = maxy{mR1(x,y)*mR2(y,z)}, "(x,z) Î XxZ. Giả thiết (T, S, n) là bộ ba De Morgan, trong đó T là t-chuẩn, S là t-đối chuẩn, n là phép phủ định. Định nghĩa 25: Cho R1, R2 là quan hệ mờ trên XxY, phép T- tích hợp thành cho một quan hệ R1°TR2 trên XxY xác định bởi R1°TR2(x,z) = supyÎXT(R1(x,y), R2(y,z)) Định lý 8: Cho R1, R2, R3 là những quan hệ mờ trên XxX, khi đó: a. R1°T(R2R3) = (R1°TR2)°TR3 b. Nếu R1 Í R2 thì R1°TR3 Í R2°TR3 và R3°TR1 Í R3°TR2 Tính chuyển tiếp Định nghĩa 26: Quan hệ mờ R trên XxX gọi là: a. min –chuyển tiếp nếu min{R(x,y), R(y,z)} £ R(x,z) "x,y,z ÎX. b. chuyển tiếp yếu nếu "x, y, z Î X có R(x,y) > R(y,x) và R(y,z) > R(z,y) thì R(x,z) > R(z,x) c. chuyển tiếp tham số nếu có một số 0q>R(y,x) và R(y,z)>q>R(z,y) thì R(x,z)>q>R(z,x) "x,y,z Î X. Định lý 9: a. Nếu R là quan hệ mờ có tính chất min-chuyển tiếp thì R là quan hệ mờ có tính chất chuyển tiếp tham số với mọi 0<q<1. b. Nếu R là quan hệ mờ có tính chất chuyển tiếp tham số thì R là quan hệ mờ có tính chất chuyển tiếp yếu. Điều khiển mờ Như đã trình bày, những ứng dụng thực tiễn thành công nhất là điều khiển mở. Do vậy, thật tự nhiên chúng sẽ trình bày khá chi tiết về lĩnh vực hấp dẫn này. Cấu trúc cơ bản Tư tưởng cơ bản của điều khiển dựa vào logic mờ là đưa các kinh nghiệm chuyên gia của những người vận hành giỏi hệ thống vào trong thiết kế các bộ điều khiển các quá trình trong đó quan hệ vào – ra (input – output) được cho bởi một tập các luật điều khiển mờ (dạng luật if then) Cấu trúc cơ bản (Basic architecture) Cấu trúc cơ bản của một bộ điều khiển dựa vào logic mờ (fuzzy logic control FLC) gồm bốn thành phần chính (hình 1): khâu mờ hóa (a fuzzifier), một cơ sở các luật mờ (a fuzzy rule base). Một môtơ suy diễn (an infernce engine) và khâu giải mờ (a defuzzifier). Nếu đầu ra sau công đoạn giải mờ không phải là một tín hiệu điều khiển (thường gọi là tín hiệu điều chỉnh) thì chúng ta có một hệ quyết định trên cơ sở logic mờ. Mờ hóa Mô tơ suy diễn Cơ sở luật mờ Giải mờ Đối tượng m(x) m(y) y Hình 3 – Mô tơ suy diễn Không gian input-output Vì mục tiêu của bộ điều khiển mờ là tính toán các giá trị của các biến điều khiển từ quan sát và đo lường các biến trạng thái của quá trình được điều khiển sao cho hệ thống vận hành như mong muốn. Như vậy, việc chọn các biến trạng thái và các biến điều khiển phải đặc trưng cho các phép toán (theo operator) của bộ điều khiển mờ và có tác động cơ bản lên sự quá trình thực hiện bộ FLC. Kinh nghiệm của các chuyên gia và các tri thức về công nghệ đóng vai trò rất quan trọng trong việc lựa chọn các biến. Ví dụ các biến vào thường là trạng thái (state) sai lầm trạng thái (state error, state error derivate, state error intergral, ). Khi sử dụng biến ngôn ngữ, biến ngôn ngữ đầu vào x sẽ gồm các biến ngôn ngữ input xi xác định trên không gian nền Ui và tương tự với biến đầu ra y trên không gian nền Uj. Khi đó: x = {(x1,Ui,{Axi(1), Axi(ki)}. {mxi(ki)}: i = 1,2, n} y = {(y1,Vi,{Ayi(1), Ayi(ki)}. {myi(ki)}: i = 1,2, m} ở đây xi là biến ngôn ngữ xác định trên không gian nền Ui, nhận từ - giá trị Axi với hàm thuộc mxi(k) với k = 1, 2, , ki. Tương tự cho các biến output yj. Ví dụ x1 là biến tốc độ trên không gian nền là miền giá trị vật lý U1 = [0,200km/h]. Biến ngôn ngữ tốc độ có thể có các từ giá trị {rất chậm, chậm, trung bình, nhanh, rất nhanh} Mỗi giá trị ngôn ngữ của biến này được xác định bằng một tập mờ trên U với các hàm thuộc mchậm(u), , mtrung bình(u). Khâu mờ hóa Vì nhiều luật cho dưới dạng dùng các biến ngôn ngữ với các từ thông thường. Như vậy với những giá trị (rõ) quan sát được, đo được cụ thể, để có thể tham gai vào quá trình điều khiển khi cần thiết phải mờ hóa. Có thể định nghĩa, mờ hóa là một ánh xạ (mapping) từ không gian các giá trị quan sát được (rõ) vào không gian của các từ - tập mờ trên không gian của các biến ngôn ngữ input. Ví dụ ứng với biến ngôn ngữ tốc độ, ta cho phép mờ hóa bằng ánh xạ. - Tốc độ một xe tải đo được: u = 75km/h - Từ đó có: (mrất chậm(75), mchậm(75),mtrung bình(75),mnhanh(75), mrất nhanh(75)). Cơ sở các luật mờ Dạng tổng quát của các luật điều khiển mờ là bộ các quy tắc mờ dạng IF THEN, trong đó các điều kiện đầu vào và cả các biến ra (hệ quả sử dụng các biến ngôn ngữ. Viết ở dạng tổng quát, cơ sở các luật mờ trong các hệ thống nhiều biến vào (ouput) và một biến ra (output)(tức là với các hệ MISO) cho dưới dạng sau: Cho x1, x2, , xm là các biến vào của hệ thống, y là biến ra (thường là các biến ngôn ngữ). Các tập Aij, Bj, với i =1, , m; j = 1, ,n là các tập mờ trong các không gian nền tương ứng của các biến vào và biến ra đang sử dụng của hệ thống. Các Rj là các suy diễn mờ (các luật mờ) dạng “Nếu thì” (dạng if then). R1 Nếu x1 là A11 và và xm là Am1 thì y là B1 R2 Nếu x1 là A12 và và xm là Am2 thì y là B2 Rn Nếu x1 là A1n và và xm là Amn thì y là Bn Cho: Nếu x1 là A1* và và xm là Am* Tính: y là B* ở đây A1*, , Am* là các giá trị đầu vào hay sự kiện (có thể mờ hoặc giá trị rõ). Một dạng tường minh các luật mờ thường cho dưới dạng Rj: Nếu x1 là A1j và và xm là Amj thì y = fj (x1, x2, , xm), j = 1, , n. Ở đây fi(x1, x2, , xm) là một hàm của các biến trạng thái. Mô tơ suy diễn Đây là phần cốt lõi nhất của FLC trong quá trình mô hình hoá các bài toán điều khiển và chọn quyết định của con ngường trong khuôn khổ vận dụng logic mờ và lập luận xấp xỉ. Do các hệ thống được xét dưới dạng hệ vào – ra nên luật suy diễn modus ponens suy rộng đóng một vai trò rất quan trọng. Như đã trình bày trong phần trước. Suy luận xấp xỉ, phép hợp thành và phép kéo theo của logic mờ sẽ quyết định trong công việc chính trong quá trình tính toán cũng như trong quá trình rút ra kết luận. Bảng sau đây giới thiệu một số phép kéo theo mờ (fuzzy implications) thường được sử dụng trong diễn đạt các luật mờ. Phép kéo theo Công thức Toán tử min [Mamdani] a =>b = min (a,b) Toán tử tích [Larsen] a =>b = a.b Tích bị chặn a =>b = max(0, a+b-1) Quy tắc số học [Zadeh] a => b= min (1, 1-a+b) Quy tắc max=min [Zadeh] a => b = max (1-a, min (a,b)) Suy diễn bình thường a=>b = 1 nếu a£ b 0 nếu a>b Logic Boole a => b = max (1-a, b) Logic Godel a => b = 1 nếu a £ b b nếu a > b Phép kéo theo Goguen a =>b = 1 nếu a £ b b b Khâu giả mờ Đây là khâu thực hiện quá trình xác định một giá trị rõ có thể chấp nhận được làm đầu ra từ hàm thuộc của giá trị mờ đầu ra. Có hai phương pháp giải mờ chính: Phương pháp cực đại và phương pháp trọng điểm. Tính toán theo các phương pháp phức tạp. Giới thiệu chung về luật kết hợp mờ Ngày nay, với bộ nhớ rất lớn của máy tính, một số lượng lớn các dữ liệu giao dịch sẽ được tập hợp và đsược lưu trữ trong máy tính. Ví dụ như các dữ liệu giao dịch hàng hoá, các bản ghi thông tin sinh viên, các bản ghi hồ sơ bệnh nhân v.v Tuy nhiên, cơ sở dữ liệu giao dịch thuộc loại cơ sở dữ liệu định lượng - quantitative type, và như vậy chúng ta sẽ mất mát rất nhiều thông tin nếu chúng ta chuyển đổi cơ sở dữ liệu định lượng này thành kiểu nhị phân. Trong trường hợp này, một phương pháp mới được đề xuất để giải quyết vấn đề này. Những vấn đề liên quan thì cũng đã được trình bày trong các phần trên. Một trong những hướng giải quyết được đề xuất ở đây là luật liên kết định lượng, luật này sẽ ánh xạ những thuộc tính định lượng thành kiểu mờ. Ngoài ra, còn có một hướng giải quyết do Ramakrishnan Srikant và Rakesh Agrawal đề xuất. Ý tưởng chính của phương pháp này là ánh xạ những thuộc tính định lượng thành kiểu nhị phân. Với mỗi thuộc tính định lượng và phân loại, chúng ta sẽ ánh xạ các giá trị tới một tập các số tự nhiên liên tiếp nhau. Với mỗi giá trị của thuộc tính, độ support và độ tin cậy có thể được tìm thấy khi tạo ra các luật liên kết nhị phân. Giải thuật sẽ liên kết các giá trị số liền kề nhau của thuộc tính cho tới khi độ support là nhỏ hơn độ support do người dùng lựa chọn. Tuy nhiên, Kuok đã chỉ ra vấn đề về ranh giới cứng - sharp boundary problem, đồng ý rằng, vấn đề phân chia cứng của các thuộc tính số không phù hợp với những tri thức trực quan của dữ liệu. Ví dụ, giả sử rằng một thuộc tính là độ tuổi của con người, chúng ta mong muốn lấy ra được các luật liên quan tới lứa tuổi cao niên, trung niên và thanh thiếu niên. Nếu các khoảng tuổi được phân chia cứng, thì chúng ta sẽ có thể gặp phải một tình huống là 59 tuổi được coi là trung niên nhưng 60 tuổi thì lại được coi là cao niên, mặc dù chúng ta có thể hiểu rằng nó không có sự khác biệt lớn đến như vậy. Trong tài liệu của Kuok, thuộc tính tuổi được xác định bởi các tập tuổi mờ của cao niên, trung niên và thanh thiếu niên. Một tập mờ được biểu diễn bởi một hàm thuộc, hàm thuộc này sẽ gắn mỗi giá trị của thuộc tính vào một giá trị nằm trong khoảng (0,1). Ví dụ hàm thuộc của tuổi cao niên được gán giá trị 1.0 cho tuổi 80, 0.8 cho tuổi 50 và 0 cho tuổi 3; trong khi đó hàm thuộc của tuổi trung niên gán giá trị 0 cho tuổi 60, 1 cho tuổi 40, 0.5 cho tuổi 30 và 0 cho tuổi 3. Hình 4 - Hàm thuộc cho các tập mờ Già(Old) và Trẻ(Young) Cũng trong tài liệu của Kuok, luật liên kết mờ có dạng như sau: X A Y B Trong đó: X,Y là các tập mục, A, B là các tập mờ với các thuộc tính tương ứng. Luật trên có thể diễn giải ra rằng nếu X thuộc vào tập mờ A thì Y sẽ thuộc về tập mờ B, với một số lượng bản ghi đủ nhiều để support cho luật này. Một giải thuật mới được đề nghị để tìm ra các luật liên kết mờ có trọng số. Điều này sẽ giúp cải thiện tính ứng dụng thực tế của việc tìm kiếm luật liên kết. Các khái niệm mờ gắn liền với các thuộc tính định lượng và các trọng số được sử dụng để phản ánh tính quan trọng của các khái niệm mờ của mỗi thuộc tính định lượng. Giải thuật này cho phép chúng ta tìm ra các luật tin cậy được với tốc độ tương đối nhanh. Luật kết hợp mờ Mô tả bài toán Thuộc tính và cơ sở dữ liệu: Cho I là tập các thuộc tính I={I1,.In}, trong đó dom(Iv) là miền giá trị của thuộc tính Iv (ví dụ trong cơ sở dữ liệu quản lý về các tính năng kỹ thuật của xe gắn máy, thông số về lượng xăng tiêu thụ trung bình trên 100km là một thuộc tính, với dom=[0,100].Ta có một cơ sở dữ liệu D trên I là tập các bản ghi d. Với mọi bản ghi d thuộc D, ta có d[Iv] xác định giá trị iv thuộc dom(Iv) của thuộc tính Iv của d. Từ Xét I={I1,I2,,In} là tập các thuộc tính, giả sử mỗi một thuộc tính Iv có thể được mô tả bằng một tập các từ Lv={L,L,L}. Lấy ví dụ, thông số về lượng xăng tiêu thụ trung bình trên 100km có thể được mô tả bằng tập từ {thấp, trun bình, cao}. Các từ mô tả các thuộc tính khác nhau là khác nhau, mặc dù chúng có thể cùng nhãn, ví dụ như: “Thấp”, “Trung bình”, “Cao”. Xét L là một từ mô tả thuộc tính Iv của cơ sở dữ liệu, khi đó L được biểu diễn bằng một hàm thuộc: dom(Iv)à[0,1] biểu diễn mức độ đúng của việc sử dụng L để mô tả giá trị iv thuộc dom(Iv). Ký hiệu: - Mv là tập tất cả các hàm thuộc biểu diễn các từ mô tả thuộc tính Iv. - LI là tập tất cả các tập từ mô tả các thuộc tính của I, LI được gọi là mô tả của I. - MI là tập tất cả các hàm thuộc biểu diễn các từ trong mô tả LI của I, MI được gọi là biểu diễn của I ứng với LI. Mệnh đề Cho trước 1 cơ sở dữ liệu D trên tập thuộc tính I và các tập từ cũng như các hàm thuộc gắn với các thuộc tính này. Từ cơ sở dữ liệu này, bài toán tìm luật kết hợp mờ tìm cách rút ra các luật dạng : "Nếu X là A thì Y là B". Trước hết chúng ta có khái niệm mệnh đề. Định nghĩa a.3.1: Cho I là tập thuộc tính, X={ I,I,I} I là tập các thuộc tính, cho A là tập các từ mô tả các thuộc tính trong X, nghĩa là A={ L,L,L}, A được gọi là mô tả của X, khi đó một mệnh đề trên tập thuộc tính I và tập từ LI (hay gọi tắt mệnh đề)"X là A" ký hiệu hình thức . Chú ý rằng có tương ứng một một giữa A và X, theo nghĩa từ L trong A là một mô tả của thuộc tính I trong X. Chúng ta chỉ quan tâm đến luật kết hợp "có ý nghĩa đối", chúng ta sẽ tìm hiểu về một số tiêu chuẩn đánh giá 1 luật kết hợp mờ. Định nghĩa a.3.2: Cho cơ sở dữ liệu D trên tập các thuộc tính I, là một mệnh đề trên I và tập từ LI, MI là biểu diễn của của I ứng với LI. Xét d thuộc D là một bản ghi. Khi đó độ ủng hộ của d cho ứng với MI được cho bởi công thức sau: vote(d,X,A,MI)= (d[Ix1]).(d[Ix2])(d[Ixp]) Ý nghĩa của biểu thức trên biểu diễn giá trị đúng đắn của mệnh đề "Ix1 là L và Ix2là L và Ixp là L . Định nghĩa a.3.3: Độ hỗ trợ của trong D ứng với MI: Supp(X,A,D,MI)= vote(d,X,A,MI) Bên cạnh khái niệm hỗ trợ chúng ta có thể sử dụng khái niệm độ quan trọng. Định nghĩa a.3.4: Độ quan trọng của trong D ứng với MI : Sign(X,A,D,MI)= Trong bài toán tìm luật kết hợp mờ, chúng ta chỉ quan tâm tới các mệnh đề có độ quan trọng (độ hỗ trợ) đử lớn, nghĩa là vượt 1 ngưỡng cho trước nào đó. Nói cách khác đó là những vấn đề có supp(X,A,D,MI) abs hay sign(X,A,D,MI) rel với abs và rel là các ngưỡng cho trước nào đó. Nếu một mệnh đề có độ quan trọng đủ lớn ta gọi mệnh đề đó là đáng kể. Định nghĩa a.3.5: tập các mệnh đề đáng kể trên D ứng với ngưỡng và MI được cho bởi: S(D, , MI)={| supp(X,A) } Luật kết hợp Định nghĩa b.1: Cho trước 1 tập thuộc tính I, LI là tập các từu mô tả I, MI là tập các hàm thuộc biểu diễn I ứng với LI, D là một cơ sở dữ liệu trên I. Mục tiêu của chúng ta là tìm các luật dạng "Nếu X là A thì Y là B" có biểu diễn hình thức à , trong đó X,Y I là tập các thuộc tính, XY={} A,B là các tập từ mô tả X,Y tương ứng. Phần được gọi là phần thân (hay tiền tố) của luật, được gọi là phần đầu (hay hệ quả) của luật. Ý nghĩa của luật này nói lên việc nếu "X là A" được thỏa mãn thì "Y là B" cũng được thỏa mãn. Định nghĩa b.2: Cho trước một tập thuộc tính I, tập tù LI mô tả I, MI là tập các hàm thuộc biểu diễn I ứng với LI . D là một cơ sở dữ liệu trên I. trong đó X,Y I là tập các thuộc tính, XY={} A,B là các tập từ mô tả X,Y tương ứng. - Độ hỗ trợ và độ quan trọng của luật à trên D ứng với MI được cho bởi: supp(à,D,MI)=supp(XY,AB, D,MI) sign(à,D,MI)=sign(XY,AB, D,MI) - Độ tin cậy của luật trên D ứng với MI được cho bởi: Conf((à,D,MI)= Conf((à,D,MI)= Luật được gọi là tin chắc nếu độ chắc chắn của nó vượt một ngưỡng độ chắc chắn tối thiểu cho trước nào đó. Vậy một luật được gọi là quan tâm nếu nó đáng kể và tin chắc. Định nghĩa b.3: Tập các luật quan tâm được ký hiệu: R(D,,,MI)={à|X,YI,XY={},S(D,, MI), Conf((à)} Thuật toán khai thác luật kết hợp mờ Thuật toán khai thác luật kết hợp mờ dựa trên thuật toán Apriori, và mục 3.3.5. Thuật toán chia làm 3 pha chính sau: Pha1: Mô hình hóa bài toán: chuyển dữ liệu ban đầu thông qua hàm thuộc của các tập mờ tương ứng với từng thuộc tính. Pha2 : Tìm tất cả các tập thuộc tính mờ phổ biến dạng có độ hỗ trợ lớn hơn độ hỗ trợ cực tiểu của người dùng nhập vào : fs()fminsupp Pha3 : Sinh các luật mờ tin cậy từ các tập phổ biến đã tìm thấy ở pha thứ nhất. Nếu là tập thuộc tính mờ phổ biến thì luật kết hợp mờ được sinh từ X có dạng X’ is A’ X\X’ is A\A’. Trong đó: X’ là tập con khác rỗng của X, X\X’ là hiệu của 2 tập hợp X và X’. fc là độ tin cậy của luật thỏa mãn fc fminconf (do người dùng xác định). A’ là tập con khác rỗng của A và là tập các tập mờ tương ứng với các thuộc tính trong X’. A\A’ là hiệu của 2 tập A và A’. Đầu vào của thuật toán: Cơ sở dữ liệu D với tập các thuộc tính I và các bản ghi T, ngưỡng hàm thuộc Wf , độ hỗ trợ tối thiểu fminsupp , độ tin cậy tối thiểu fminconf và toán tử Tnorm . Đầu ra của thuật toán: Tất cả các luật kết hợp mờ tin cậy. Ký hiệu sử dụng trong thuật toán khai phá luật kết hợp mờ: Ký hiệu Ý nghĩa D Cơ sở dữ liệu ban đầu. I Tập các thuộc tính trong D. T Tập các bản ghi trong D. Df Cơ sở dữ liệu mờ được tính toán từ cơ sở dữ liệu ban đầu thông qua hàm thuộc của các tập mờ tương ứng với từng thuộc tính. If Tập các thuộc tính trong Df, mối thuộc tính đểu được gắn với 1 tập mờ. Mỗi tập mờ f có 1 ngưỡng wf . Tf Tập các bản ghi trong Df , các thuộc tính trong mỗi bản ghi đã được chuyển sang một giá trị trong khoảng [0,1] nhờ hàm thuộc của các tập mờ tương ứng với từng thuộc tính. Fminsupp Độ hỗ trợ tối thiểu Fminconf Độ tin cậy tối thiểu Ck Tập các thuộc tính có kích thước k Fk Tập các thuộc tính phổ biến có kích thước bằng k F Tập tất cả các thuộc tính phổ biến FC Tập tất cả các luật mờ sinh ra từ Fk Bảng 1 – Ký hiệu sử dụng trong thuật toán Thuật toán khai thác luật kết hợp mờ: Begin (Df,Tf,If)=Mờ_Hóa(D,I,T); F1=Tạo_F1(Df,If,Tf,fminsupp); F=Φ,Cf=Φ; K=2; While (Fk-1Φ) {Ck=Tạo_F_k(Fk-1); Fk=Tính_SP_k(Ck,Df,fminsupp); CFk=Tìm_Luật(F,Fk,fminconf); F=FFk; CF=CFCFk; K=k+1;} END Thuật toán sử dụng một số chương trình con sau: Chương trình con Mờ_Hóa(D,I,T): Hàm này thực hiện nhiệm vụ chuyển đổi từ cơ sở dữ liệu gốc D ban đầu sang cơ sở dữ liệu mờ Df . Các thuộc tính của D được gắn thêm các tập mờ và giá trị của các thuộc tính ở bản ghi T trong D được ánh xạ thành một giá trị thuộc khoảng [0,1] thông qua các hàm thuộc. Chương trình con F1=Tạo_F1(Df,If,fminsupp,wf) Hàm này sinh ra F1 là tập tất cả các tập phổ biển có 1 phần tử. Các tập phổ biến này phải có độ hỗ trợ lớn hơn hoặc bằng fminsupp. Thuật toán tạo F1: F1=Tạo_F1(Df,If,fminsupp,wf) F1=Φ; For each I If If (fs({i},wf) fminsupp) then F1=F1{i}; End if Endfor Return F1 Chương trình con Ck=Tạo_F_k(Fk-1): Hàm này thực hiện kết nối các cặp thuộc tính mờ từ tập các thuộc tính mờ phổ biến Fk-1 có k-1 phần tử để sinh ra tập các thuộc tính mờ Ck có k phần tử. Thuật giải tạo Fk từ Fk-1: Insert into Ck Select P.item_1,P.item_2,,P.itemk-1,Q.itemk-1 From Lk-1P,Lk-1Q Where (P.item_1 = Q.item_1) AND. . . AND (P.item_k-2 = Q.item_k-2) AND (P.item_k-1 < Q.item_k-1) Trong đó: P.item_j,Q.item_j là thuộc tính mờ thứ j trong Lk-1 P.item_o_j,Q.item_o_j là thuộc tính gốc của các thuộc tính mờ thứ j trong Lk-1. Với điều kiện P.itemk-1< Q.itemk-1 nhằm không phát sinh các bộ không trùng nhau. Tuy nhiên thuật giải trên sẽ phát sinh các tập k thuộc tính mờ khác nhau nhưng có cùng thuộc tính gốc và các luật sinh ra từ các tập thuộc tính mờ có cùng thuộc tính gốc là vô nghĩa.Nên cần thay đổi điều kiện của thuật giải như sau: Where (P.item_1 = Q.item_1) AND. . . AND (P.item_k-2 = Q.item_k-2) AND (P.item_k-1 < Q.item_k-1) AND (P.item_o_k-1 Q.item_o_k-1) Điều kiện (P.item_o_k-1 Q.item_o_k-1) sẽ đảm bảo không phát sinh các bộ thuộc tính mờ có cùng thuộc tính gốc. Chương trình con Fk=Tính_SP_k(Ck,Df,fminsupp,wf): Hàm này duyệt qua cơ sở dữ liệu Df, chọn ngưỡng wf và Tnormđể cập nhật độ hỗ trợ cho các thuộc tính trong Ck. Sau khi duyệt xong Tính_SP_k chỉ chọn những tập phổ biến có độ hỗ trợ lớn hơn hoặc bằng fminsupp để đưa vào trong Fk. Thuật giải: Fk=Φ; For(each X Fk-1) do For(each Y Fk-1 and XY) do Begin S=XY; If (|S| ==k and fs(|S|)fminsupp) then Fk=Fk{S}; Endif End Endfor Endfor Chương trình con CFk=Tìm_luật(Fk,fminconf) chương trình con này sinh luật kết hợp mờ tin cậy từ các tập phổ biến Fk . CÀI ĐẶT Bài toán tìm luật Cho trước I là tập thuộc tính, LI là tập các từ mô tả I, MI là tập các hàm thuộc biểu diễn I ứng với LI. D là cơ sở dữ liệu trên I, , tương ứng là các ngưỡng độ hỗ trợ và độ chắc chắn tối thiểu. Hãy tìm R(D, ,,MI)? Bài toán thực tế Ta có cơ sở dữ liệu(D) thông tin giao dịch chứng khoán (tập các thuộc tính I), LI là các từ mô tả các thuộc tính của I (“Tăng nhẹ”,”Tăng khá”,”Tăng mạnh”; “Khối lượng giao dịch thấp”,”Khối lượng giao dịch TB”,”Khối lượng giao dịch lớn”; “Nước ngoài mua ít”, “Nươc ngoài mua TB”, “Nước ngoài mua nhiều”). MI tập hàm thuộc biểu diễn I ứng với LI. Cho trước 2 giá trị là ngưỡng độ hỗ trợ, là ngưỡng độ tin cậy(độ chắc chắn) tối thiểu. Tìm R(D,,,MI) có nghĩa chúng ta đi tìm các luật và các ngưỡng hỗ trợ và ngưỡng tin cậy tương ứng, từ đó dựa vào % ngưỡng hộ trợ và % ngưỡng tin cậy để chúng ta đưa ra nhận định. Ví dụ dữ liệu giao dịch chứng khoán theo ngày: Ngày VNI tăng VNI giảm GTGD(tỉ) NNMUA(triệu CP) Y/Tố tâm lý VNI 12/10/2007 5.3 1323 1800000 1 1 11/10/2007 5.36 1095 2000000 1 0 10/10/2007 7.14 1156 2300000 1 1 09/10/2007 12.49 1314 1400000 1 1 08/10/2007 3.24 1269 1500000 1 1 05/10/2007 6.13 1494 2300000 1 0 04/10/2007 18.84 1683 2100000 1 0 03/10/2007 7.12 1575 1900000 1 1 02/10/2007 15 1750 2800000 1 1 01/10/2007 37.53 1723 1900000 1 1 28/09/2007 32.77 1395 2600000 1 1 27/09/2007 1.82 1084 2100000 1 0 26/09/2007 6.03 1311 1600000 1 1 Bảng 2 – Ví dụ về dữ liệu giao dịch chứng khoán Ta qui đinh khoảng của các LI như sau: VNIndex: VNI tăng >15 điểm à tăng mạnh 5< VNI tăng <15 điểm à tăng trung bình VNI tăng <5 điểm à tăng nhẹ Giá trị giao dịch: Gía trị giao dịch <600 tỉ à Giá trị giao dịch thấp Gía trị giao dịch >1000 tỉ à Giá trị giao dịch cao 600 tỉ <Gía trị giao dịch <1000 tỉ à Giá trị giao dịch trung bình Giao dịch của nước ngoài: Khối lượng nước ngoài mua < 500 nghìn cổ phiếu à Mua ít Khối lượng nước ngoài mua > 1 triệu cổ phiếu à Mua nhiều 500 nghìn<Khối lượng nước ngoài mua < 1 triệu cổ phiếu à Mua trung binh. Yếu tố tâm lý: 1: Yếu tố tâm lý thị trường tốt. 0: Yếu tố tâm lý thị trường không tốt. Sử dụng hàm Mờ_Hóa (3.3.6) để chuyển sang dữ liệu mờ, hàm này được xây dựng dựa trên: L là một từ mô tả thuộc tính Iv của cơ sở dữ liệu D, khi đó L được biểu diễn bằng một hàm thuộc: dom(Iv)à[0,1] biểu diễn mức độ đúng của việc sử dụng L để mô tả giá trị iv thuộc dom(Iv). Kết hợp hàm thuộc theo dạng tam giác theo nên ta có được dữ liệu sau: VNI tăng mạnh VNI tăng TB VNI tăng nhẹ VNI giảm mạnh VNI giamr TB VNI giảm nhẹ GTGD lớn GTGD TB GTGD thấp NN mua nhiều NN mua TB NN mua ít VNI up/down 0 0 0.67 0 0 0 0 0.76 0 0 0.78 0 1 0 0 0 0 0 0.6 0 0.55 0 0.8 0 0 0 0 0 0.6 0 0 0 0 0.6 0 0.85 0 0 1 0 0.57 0 0 0 0 0 0.71 0 0 0.56 0 1 0 0 0.5 0 0 0 0 0.68 0 0 0.59 0 1 Bảng 3 – Dữ liệu giao dịch chứng khoán chuyển sang dạng mờ a, Dùng chương trình con Tạo_F1 (3.3.6) tập tất cả các tập phổ biến có 1 phần tử, các tập thuộc tính phổ biến này có độ hỗ trợ lớn hơn hoặc bằng . b, Chương trình con Tạo_F_k (3.3.6) thực hiện kết nối cặp các thuộc tính mờ từ tập các thuộc tính phổ biến Fk-1 để sinh ra tập các thuộc tính mờ ứng cử viên. c, Chương trình con Tìm_Luật (3.3.6) sinh ra luật kết hợp mờ tin cậy từ các tập phổ biến trong b. KẾT LUẬT Vấn đề tìm kiếm luật kết hợp trong khai phá dữ liệu thực sự rất hữu ích trong các lĩnh vực khai phá tri thức. Trong luận văn này, chúng ta đã giới thiệu phương pháp để tiếp cận với vấn đề luật kết hợp mờ. Bài toán tìm kiếm luật kết hợp mờ được ứng dụng cho nhiều lĩnh vực khác nhau. Cụ thể trong luận văn này em đã cài đặt một thuật toán tìm luật kết hợp mờ cho bài toán dự đoán chỉ số VNIndex. Chương trình đã đưa ra được % độ hỗ trợ và % độ tin cậy. Ngoài ra, chúng ta còn xem xét các giải thuật, kiểm nghiệm thực tế để giải quyết bài toán đặt ra và giới thiệu một số bài toán nâng cao. Tài liệu tham khảo [1] Bùi Công Cường, Nguyễn Doãn Phước - Hệ mờ mạng nơtron và ứng dụng. [2] Nguyễn Thanh Thủy - Khai phá dữ liệu, Kỹ thuật và ứng dụng. [3] Lê Bá Long, Đỗ Văn Thành, Trần Đình Khang - Trường thu hệ mờ và ứng dụng. [4] Bùi Công Cường, Lê Chí Ngọc - Báo cáo tại hội nghị khoa học FAIR 2005. [1] David Hand, Heikki Mannina, Padhraic Smyth - Principles of Data Mining. [2] Hồ Tú Bảo - Knowledge discovery and data mining techniques and practice.