Tài liệu Khai phá phụ thuộc hàm xấp xỉ sử dụng luật kết hợp và ứng dụng

TRƯỜNG Đ H ĐẠI HỌC THÁI NGUYÊN Ệ THÔNG TIN & TRUYỀN THÔNG Thái Nguyên 9 - 2015 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ TRƯỜ ĐẠI HỌC THÁI NGUYÊN Ệ THÔNG TIN & TRUYỀN THÔNG Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 Người hướng dẫn khoa học TS. Nguyễn Huy Đức Thái Nguyên 9 - 2015 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ i LỜI CAM ĐOAN Tôi xin cam đoan luận văn này của tự bản thân tôi tìm hiểu, nghiên cứu dưới sự hướng dẫn của TS. Nguyễn Huy Đức. Các chương trình thực nghiệm do chính bản thân tôi lập trình, các kết quả là hoàn toàn trung thực. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ. TÁC GIẢ LUẬN VĂN Phạm Thị Thanh Nga Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ ii em em tr . ập thể các nhà khoa học, – trong – Nguyên. Với vốn kiến thức được tiếp thu trong quãng thời gian học tập trên giảng đường không chỉ là nền tảng cho quá trình nghiên cứu luận văn mà còn là hành trang quý báu để em bướ ột cách vững chắc và tự tin. Trong quá trình viết luận văn, bản thân em đã hết sức cố gắng nhưng do khả năng, vốn kinh nghiệm nghiên cứu và thời gian có hạn nên luận văn không tránh khỏi những thiếu sót. Vì vậy, em rất mong nhận được sự chỉ bảo, góp ý của các nhà khoa học, các thầy, cô để . ! , Số hóa bởi Trung tâm Học liệu - ĐHTN 08 năm 2015 http://www.lrc-tnu.edu.vn/ iii MỤC LỤC LỜI CAM ĐOAN .............................................................................................. i ................................................................................................... ii MỤC LỤC ........................................................................................................ iii N VĂN .... v DANH MỤC VIẾT TẮ DANH MỤ ẢNG BIỂU .................................................................... vi DANH MỤ Ẽ ........................................................................ vii MỞ ĐẦU ........................................................................................................... 1 Chương 1. TỔNG QUAN VỀ PHỤ THUỘC HÀM, PHỤ THUỘC HÀM XẤP XỈ VÀ LUẬT KẾT HỢP ......................................................................... 4 1.1. Quan hệ và phụ thuộc hàm ......................................................................... 4 1.2. Phụ thuộc hàm xấp xỉ ................................................................................. 6 1.2.1. Định nghĩa ............................................................................................... 6 1.2.2. Một số độ đo cơ bản ................................................................................ 7 1.3. Luật kết hợp................................................................................................ 9 ............................................................................................... 9 ......................................................... 13 1.3.3. Khai phá luật kết hợ Kế .......................................... 13 1 ........................................................................................... 24 Chương 2. BIỂU DIỄN PHỤ THUỘC HÀM XẤP XỈ QUA LUẬT KẾT HỢP.. 25 2.1. Định nghĩa PTH xấp xỉ qua LKH ............................................................ 25 ........................... 28 2.1.2. Về một độ đo độ chính xác ................................................................... 29 ............ 31 ............................................................................................... 33 .............................................................................................. 34 ..................................................................................... 35 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ iv ....................... 36 ....................................... 40 2 ........................................................................................... 42 Chương 3. T . 43 ........................................................................................... 43 ................................................................................. 44 ............................................................................ 46 .............................................................................. 48 Kết luận chương 3 ........................................................................................... 54 ...................................................... 55 ............................................................................... 57 PHỤ LỤC ........................................................................................................ 59 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ v DANH MỤC VIẾT TẮT Ký hiệu Diễn giải RU U U A1, ..., Am . U S = (U, F) s X Y c X Y s X Y c X Y cf I X ,F U X X Y Y X Y X IY IX Y IY LĐQH CSDL Cơ sở dữ liệu PTH LKH Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ vi DANH MỤC BẢNG BIỂU ............................................................................... 5 Bảng 1.2. Bảng quan hệ ví dụ về PTH xấp xỉ ................................................... 7 .................................................................. 10 ........................ 11 Bảng 1.5. Cơ sở dữ liệ D ................................................................. 14 Bảng 1.6. Độ hỗ trợ của các mục .................................................................... 15 Bảng 1.7. Độ hỗ trợ của các tập mục .............................................................. 15 Bảng 1.8. Độ tin cậy của các luật .................................................................... 16 Bả D cho thuật toán Apriori ........................................ 20 ực hiệ ......................................... 21 ................... 24 R ................................................................................. 27 TD R .............................................................. 27 2.3. Một số LKH trong TD tương ứng với PTH xấp xỉ trong R ............ 28 ............................................................ 45 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ vii DANH MỤ HÌNH VẼ Hình 1.1. Phân loại các thuật toán khai phá tập mục phổ biến ....................... 17 ................................................... 44 ....................................... 46 ................................................................... 47 ................................. 48 ...................................................... 49 .......................................... 49 Hình 3.7. Giao diện kết quả khai phá PHT xấp xỉ .......................................... 51 Hình 3.8. Giao diện kết quả khai phá PTH xấp xỉ .......................................... 52 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 1 MỞ ĐẦU 1. Tính cấp thiết của đề tài Sự phát triển nhanh chóng của công nghệ thông tin (CNTT) đã tác động đến mọi mặt của xã hộ ững thành tựu của công nghệ lưu trữ đã cho phép tạo ra những nguồn dữ liệu khổng lồ. Việc khai thác các nguồn dữ liệu này, đang ngày càng cấp thiết đặt ra những thử thách lớn cho ngành CNTT đặc biệt là lĩnh vực khai phá dữ liệu. Như chúng ta đã biết, phụ thuộc hàm đóng một vai trò rất quan trọng trong lý thuyết thiết kế cơ sở dữ liệu. Nó đảm bảo tính chính xác cũng như tính nhất quán của cơ sở dữ liệu. Nhờ có các phụ thuộc hàm, các hệ quản trị cơ sở dữ liệu mới quản lý tốt chất lượng của dữ liệu. Tuy vậy, trong thực tế có một số giá trị dữ liệu không chính xác, hoặc một số ngoại lệ nào đó làm cho các phụ thuộc hàm không thỏa mãn. Sự phụ thuộc hàm “tuyệt đối” này có vẻ quá nghiêm ngặt khi chúng ta hình dung một quan hệ có hàng nghìn bộ, trong khi đó chỉ có khoảng vài bộ vi phạm phụ thuộc hàm. Điều này làm mất tính chất “phụ thuộc” vốn có giữa các thuộc tính. Vì vậy, các nhà nghiên cứu cơ sở dữ liệu đã mở rộng phụ thuộc hàm thành khái niệm phụ thuộc hàm xấp xỉ. Các phụ thuộc hàm này cho phép có một số lượng lỗi nhất định của các bộ dữ liệu đối với phụ thuộc hàm. Suy diễn các phụ thuộc hàm xấp xỉ ấn đề thời sự, được các nhà ợ khoa học tập trung nghiên cứ ệ thông tin. Khai phá phụ thuộc hàm xấp xỉ sử dụng luật kết hợp là một hướng nghiên cứu mới được đề xuất trong thời gian gầ , tôi chọn đề tài: “Khai phá phụ thuộc hàm xấp xỉ sử dụng luật kết hợp và ứng dụng” làm đề tài luận văn tốt nghiệp của mình. 2. Đối tượng và phạm vi nghiên cứu Tìm hiểu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ và các tính chất, độ đo lỗi của nó, khái niệm luật kết hợp, các tính chất và thuật toán điển hình khai phá luật kết hợp. 2 Luận văn đi sâu vào khai phá phụ thuộc hàm xấp xỉ sử dụng luật kết hợp và các vấn đề liên quan thuộc lĩnh vực phát hiện tri thức từ dữ liệu. Xây dựng một ứng dụng thực nghiệm phát hiện phụ thuộc hàm xấp xỉ trong cơ sở dữ liệu bán hàng của siêu thị. 3. Hướng nghiên cứu của đề tài - Nghiên cứu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ và các độ đo lỗi của nó. - Nghiên cứu về khai phá luật kết hợp: Bài toán xuất phát, các khái niệm tập mục phổ biến, luật kết hợp cùng các khái niệm độ hỗ trợ, độ tin cậy… Thuật toán điển hình tìm tập phổ biến và luật kết hợp. - Biểu diễn phụ thuộc hàm xấp xỉ trên quan hệ thông qua luật kết hợp và các độ đo của chúng. Thuật toán xác định phụ thuộc hàm xấp xỉ dựa trên luật kết hợp. 4. Phương pháp nghiên cứu Phương pháp nghiên cứ ứu lý thuyết kết hợp với đánh giá thực nghiệm cụ thể: Phân tích, tổng hợp các kết quả nghiên cứu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ, luật kết hợp… T ố trên các bài báo khoa học, hội thảo chuyên ngành trong và ngoài nước. Từ đó, trình bày làm rõ vấn đề khai phá phụ thuộc hàm xấp xỉ sử dụng luật kết hợp. 5. Ý nghĩa khoa học và thực tiễn Phụ thuộc hàm đóng vai trò rất quan trọng trong lý thuyết CSDL quan hệ. Nó rất hữu ích trong thiết kế CSDL quan hệ như: Xác định khóa, xác định các dạng chuẩn, xác định vấn đề nhất quán dữ liệu…Tuy nhiên, trong thực tế do có một số giá trị dữ liệu không chính xác hoặc một số ngoại lệ nào đó, làm cho các phụ thuộc hàm không thỏa mãn. Sự phụ thuộc tuyệt đối này dường như quá nghiêm ngặt khi ta hình dung một quan hệ có hàng nghìn bộ, trong khi đó chỉ có vài bộ vi phạm phụ thuộc hàm. Điều này, làm mất tính chất phụ thuộc vốn có giữa các thuộc tính. Vì vậy, mở rộng khái niệm phụ thuộc hàm 3 thành phụ thuộc hàm xấp xỉ, cho phép có một số lỗi nhất định của các bộ dữ liệu là rất cần thiết có ý nghĩa cả về mặt lý thuyết cũng như thực tiễn. Các phụ thuộc hàm xấp xỉ không những giúp chúng ta thấy được mối quan hệ tiềm ẩn giữa các thuộc tính mà còn giúp ta thuận tiện hơn trong việc phân tích dữ liệu đánh giá thông tin. Phát hiện phụ thuộc hàm xấp xỉ trong CSDL là một vấn đề nghiên cứu hấp dẫn và cũng là một trong những mục tiêu của phát hiện tri thức. Tiếp cận phụ thuộc hàm xấp xỉ thông qua luật kết hợp của khai phá dữ liệu là một hướng đi thú vị, hứa hẹn nhiều kết quả lý thuyết cũng như ứng dụng hiệu quả trong thực tiễn. Do vậy, đề tài luận văn tìm hiểu về phụ thuộc hàm xấp xỉ, luật kết hợp, đi sâu tìm hiểu khai phá phụ thuộc hàm xấp xỉ sử dụng luật kết hợp có ý nghĩa khoa học và thực tiễn. 6. Cấu trúc luận văn Cấu trúc luận tài liệu tham khảo. bao gồm phần mở đầu, , kết 3 chương Chương 1: Giới thiệu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ và luật kết hợp. Chương 2: . Chương 3: . 4 Chương 1 TỔNG QUAN VỀ PHỤ THUỘC HÀM, PHỤ THUỘC HÀM XẤP XỈ VÀ LUẬT KẾT HỢP Chương này trình bày tổng quan về phụ thuộc hàm, phụ thuộc hàm xấp xỉ và luật kết hợp. Các khái niệm và kết quả trong chương này có thể tìm thấy trong [1], [2], [3], [4], [6], [8], [11], [12]. 1.1. Quan hệ và phụ thuộc hàm U A1, ..., Am Dom Ai , 1 Ai trên U R (U i m R Descartes Dom A1 Dom A2 ... Dom Am . : RU Dom A1 Dom A2 ... Dom Am R . (PTH X → Y (trong X, Y ⊆ U) R (U X→Y t, s R | t X Khi PTH X → Y X→Y s X R. N R t Y : sY R R (X → Y). 1.1. bảng 1.1 như sau: R U = {T, A, B, C} cho trên 5 1.1. V R= :C T A B C 1 a1 b1 c1 2 a2 b2 c2 3 a2 b2 c3 {T} → {A, B, C}, {C} → {T, A, B}, R {A} → {B {B} → {C}, … . S = (U, F) U U F (LĐQH). R PTH X → Y ∈ F F R (X → Y). F trên U F PTH X → Y sao cho R (F R (X → Y). X→Y U F = X → Y. N F+. L F trên U trên U R (F). N (A1) – (A3) như sau: F Với ∀ X, Y, Z ⊆ U: (A1) Y⊆X X → Y ∈ F+ ia tăng (A2) X → Y ∈ F+ X ⋃ Z → Y ⋃ Z ∈ F+ X → Y ∈ F+ Y → Z ∈ F+ (A3) F+ U . X → Z ∈ F+ R (U) 6 – hệ Armstrong hay . 1.2. Phụ thuộc hàm xấp xỉ 1.2.1. Định nghĩa Định nghĩa 1.1. [11] Cho quan hệ R (U) và X → Y là một PTH trên U. Gọi S ⊆ R là quan hệ sao cho có số bộ ít nhất cần loại bỏ khỏi R để R\S thỏa mãn PTH (X → Y). Khi đó tỷ số của |S| và |R| được gọi là độ đo lỗi của PTH X → Y trên R, ký hiệu g3 (X → Y, R). Như vậy g3 X Y, R min{| S || S R, ( R \ S ) ( X | R| Y )} Một cách tương đương g3 X Y, R 1 max{|S || S R, S ( X |R| Y )} Độ đo lỗi trên còn được gọi là độ đo lỗi g3 . Có thể thấy nếu X → Y là một PTH đúng trên R thì độ đo lỗi g3 X Y, R 0. Cho ngưỡng lỗi với 0 1 . Người ta nói PTH X → Y là một PTH xấp xỉ trên R ứng với ngưỡng lỗi . Nếu g3 X Y, R . Khi đó người ta còn nói PTH xấp xỉ X → Y đúng trên R ứng với ngưỡng lỗi . Ví dụ 1.2. Xét quan hệ R trên tập thuộc tính U = {A, B, C, D} cho trên bảng 1.2 như sau: 7 Bảng 1.2. Bảng quan hệ ví dụ về PTH xấp xỉ R= Bộ A B C D t1 0 0 1 1 t2 0 1 1 1 t3 0 2 1 2 t4 1 2 0 0 t5 2 0 0 0 t6 2 0 2 0 t7 1 1 2 1 Xét PTH AB → C trên R (U). Rõ ràng bỏ bộ 6 (hoặc bộ 5) thì PTH AB → C sẽ đúng trên quan hệ R. Tức số bộ ít nhất cần loại khỏi quan hệ R để PTH AB → C đúng trên các bộ còn lại là 1. Suy ra: g3 AB 1 7 C, R Ví dụ 1.3. Xét quan hệ R ở ví dụ 1.2 trên và ngưỡng lỗi = 0,5. Theo ví dụ trên, ta có: g3 AB C, R 1 7 0, 5 . Do đó PTH AB → C là một PTH xấp xỉ trên R ứng với = 0,5. :K R (U) U R hay không. 1.2.2. Một số độ đo cơ bản Khi nghiên cứu phát hiện các PTH xấp xỉ thì vấn đề xác định độ đo cho các PTH xấp xỉ đóng vai trò cực kì quan trọng. Đã có nhiều tác giả đưa ra 8 nhiều độ đo dựa vào nhiều cách khác nhau. Ở đây luận văn tìm hiểu một số độ đo cơ bản. Trong định nghĩa về PTH xấp xỉ khi có một bộ làm cho PTH không đúng. Người ta gọi bộ này là một trường hợp ngoại lệ. Như vậy, PTH xấp xỉ chính là PTH với các trường hợp ngoại lệ. Các độ đo của PTH xấp xỉ dựa trên số lượng các trường hợp ngoại lệ, . U R (U X, Y ⊆ U. a. Độ đo lỗi g2 của Kivinen và Mannila (1995) Để đo lỗi của một PTH X → Y, ngoài độ đo g3 Kivinen và Mannila [11] còn đưa ra độ đo lỗi g2 như sau: Tỷ số giữa các bộ ngoại lệ của X → Y với các bộ trong quan hệ R được gọi là độ đo lỗi g2 của X → Y trên R, ký hiệu g2 (X → Y, R). Như vậy g2 X t Y, R R| s R, t X s X vµ t Y sY R 1.4. Xét quan hệ R ở ví dụ 1.2 trên. Ta có: g2 A 4 7 C, R : Đ [0, g2 g2 X Y, R 0 g2 X Y, R 1 Y Y hàm X .C X. Độ đo lỗi g3 Kivinen và Mannila (1995) Độ đo này đã được giới thiệu trong mục 1.2.1 ở trên. Ở đây chúng ta có thể định nghĩa lạ : 9 g3 X min Re | Re Y, R R và R \ Re X Y R Hay tương đương g3 X Y, R max S | S 1 R, S X Y R : g3 . ờng hợp ngoại lệ các cặp bộ b. Độ đo lỗi g1 của Kivinen và Mannila (1995) [11] Tỷ số giữa các cặp bộ ngoại lệ của X → Y với bình phương các bộ trong quan hệ R được gọi là độ đo lỗi g1 của PTH X → Y trên R, ký hiệu g1( X Y, R) . Một cách hình thức: g1 X t, s | t, s Y, R R, t X s X vµ t Y R sY 2 Ví dụ 1.5. Xét quan hệ R ở ví dụ 1.2 trên. Ta có: g1( A 4 49 C, R) Nhận xét: Độ đo lỗi g1 có giá trị trong khoảng [0, 1]. Khi g1( X nghĩa sự phụ thuộc của Y vào X là PTH Y, R) 0 có , ngược lại Y X. 1.3. Luật kết hợp 1.3.1 m giao dữ liệu . I I1, I 2 , ..., I m T⊆I 10 D . dữ liệu k- k . 1.6. Cho D trên tập các mục I = {A, H, L, E, F}. CSDL giao tác D như sau : D = {{A, F, L, E}; {F, H, E}; {A, F, L, E}; {A, F, H, E}; {A, F, H, L, E}; {F, H, L}} 1.3. V giao 1 {A, F, L, E} 2 {F, H, E} 3 {A, F, L, E} 4 {A, F, H, E} 5 {A, F, H, L, E} 6 {F, H, L} X⊆I T T ⊆ X. X. N supp(X). L X với số của D supp X : T D| X T D : 0 ≤ supp (X) ≤ 1 X supp (X) ≥ minsupp. T giữa số các X. (hay minsupp ∈ [0, . : 11 1.1. [7] ⊆ Y. ,Y ) supp (X) ≥ supp (Y). (1) ( (2) . (3) N . là tập . 1.7. minsupp = 50%. 1.4. V {F} 100% (6/6) {E}, {F, E} 83% (5/6) {A}{H}{D}{A, F}{A, E}{F, H}{F, L}{A, F, E} 67% (4/6) {A,L}{H,E}{L,E}{A,F,L}{A,L,E}{F,H,E}{F,L,E} 50% (3/6) (LKH) đó X, Y Y , trong X I thỏa mãn điều kiện X . Tập X gọi là tiền đề, tập Y gọi Y là kết luận của luật. quan trọng là độ hỗ trợ và độ tin cậy: Y , ký hiệu là s X X X trong D :s X T Y D| X Y. Y T P X Y D . s X Y Y supp X Y