Tài liệu Khai phá song song luật kết hợp mờ

ĐẠI HỌC ỌƯÓC GIA HÀ NỘI KHOA CÔNG NGHỆ PHAN XUÂN HIÉƯ KHAI PHÁ SONG SONG LUẬT KẾT HỌP MỜ Chuyên ngành: C ô n g nghệ thông tin Mà số: 1.01.10 LUẬN VẢN THẠC s ĩ NGƯỜI HƯỚNG DÀN KHOA HỌC TS. HÀ QUANG THỤY €>Ại M Ọ C C U ;Ố C G I A H À N Ộ I TRỦNGTẲMTH&líĩmTHƯVIẼN HoV-tO Hà Nội - 2003 )M o 1 M ụ c lục I ) a n h m ụ c h ì n h v ẽ ................................................................................................................................ ..3 I ) ; m h m ụ c b ả n g b i ể u ......................................................................................................................... ..4 K ý h i ệ u v à t ừ v i ê l t ã t ......................................................................................................................... ..5 1 .(Vi c a m o n .................................................................................................................................................. ..6 M o ' t i à t i ............................................................................................................................................................. ..7 1. T Ô I I O q u a n v è k h a i p h á d ữ l i ệ u .................................................................. .. 9 I . I K h a i p h á c l ữ l i ệ u .................................................................................................................... .. 9 1 . 1 .1 M ụ c l i ê u c u a k h a i p h á d ữ l i ệ u ..................................................................... .9 1 . 1 . 2 Đ ị n h n e l ì ĩ a k h a i p h á d ừ l i ệ u .......................................................................... 10 1 . 1.3. C á c b ư ớ c c h í n h t r o n g k h á m p h á t r i I h ử c ( K D D ) .................... 1I 1.2 I l i r ớ n ụ l i ô p c ậ n v à k ỹ t h u ậ t á p d ụ n ạ t r o n c K h a i p h á d ữ l i ệ u . . 12 C hirơ im I I ư ớ n g tiế p c ậ n v à k ỹ th u ậ t c h í n h t r o n g k h a i p h á d ừ liệu 12 1 . 2 . 2 C á c d ạ n g d ữ l i ệ u c ó t h ể k h a i p h á ............................................................ 13 1 . 3 I ỉ n g đ ụ n ” c u a K h a i p h á d ữ l i ệ u ............................................................................ 13 1.2.1 d ụ n í i c ủ a k h a i p h á d ữ l i ệ u .................................................................. 13 1 . 3 . 2 [ ’ h â n l o ạ i c á c h ệ l l ì ô n ụ k h a i p h á d ừ l i ệ u .......................................... 14 1 . 4 N h ừ n a v ấ n d ề d ư ợ c c h ú I r ọ n g t r ô n a , K h a i p h á d ữ l i ệ u ................. 14 C l i ư ơ n í i 2 . 1 . u ậ l k è t h ọ p ................................................................................................................. 16 1. 3 . 1 { J’n u Y i m h ĩ a c ù a l u ậ t k é t h ọ p .............................................................................................. 16 2 . 2 P h á i h i ê n h à i t o á n k h í i i p h á l u ậ t k è t h ợ p ...................................................... 17 2 . 3 N l ũ m u h ư ứ i i R t i ế p c ậ n c h í n h t r o n g k h a i p h á l u ậ t k ê l h ợ p ........ 19 2.1 m ò ' ............................................................................... 22 ì . I I , u ậ t k ê t h ợ p c ó t l u i ộ c l í n h s ô .................................................................................. 22 C h ư ơ n a 3. K h a i p h á l u ậ t kêl họp 3 . 1 . 1 I , u ậ l k ế t h ợ p c ó t h u ộ c t í n h s ố ....................................................................... 22 2 3 . 1.2 Các phươne, pháp rời rạc h ó a ............................................................... 23 3.2 Luật kết hợp m ờ ............................................................................................. 26 3.2.1 Rời rạc hóa thuộc tính dựa vào tập m ờ ............................................... 26 3.2.2 Luật kết hợp m ờ .......................................................................................28 3.2.3 Thuật toán khai phá luật kết hợp m ờ ...................................................32 3.2.4 Chuyển luật kết hợp mờ về luật kết hợp với thuộc tính s ố ..............36 3.2.5 Thử nehiệm và kết l u ậ n ......................................................................... 37 Chương 4. Khai phá song song luật kết hợp m ờ................................................... 42 4 . 1 Một sô thuật toán song song khai phá luật kết h ợ p .................................. 43 4.2 Thuật toán song song cho luật kết hợp m ờ ................................................50 4.2. ỉ I lướng tiếp cận ......................................................................................... 50 4.2.2 Thuật toán soné sone, cho luật kết họp m ờ ......................................... 54 4.2.2 Tính đúng dãn và độ phức tạp thời gian của thuật toán....................55 4.3 Thứ nụhĩệm và kết l u ậ n ..................................................................................58 Kết luận........................................................................................................................ 60 Nliữne vân dê đã được giải quyết trong luậnvăn n à y ...................................60 Cône việc nehiên cứu trong tương l a i .............................................................. 61 T à i liệu th a m k h ả o ....................................................................................................................................................... 6 2 Phụ lụ c ................................................................................................................66 3 Danh m ụ c hình vẽ ■ Hình I - Lượng dừ liệu được tích lũy tăng mạnh theo thời gian ................................... 9 Hình 2 - Các hước trong quớ trình khám phá tr i thức (KDD) ........................................... / 2 Hình 3 - Minh họa về luật kết hợp .................................................................................... 16 Hình 4 - Ví dụ về vân đề "Điểm biên ĩỊÕy " khi tiến hành rờ i rạc hóa dữ liệ u .......... 25 Hình 5 - Đồ thị hàm thuộc cùa các tập mờ "T u o ijrè ", "T u o ijru n g niên", và "Tìlôi g ià " ............................................................................................................................ 26 Hình 6 - Đồ thị hàm thuộc của hai tập mờ "Cholesterol thấp" và "Cholesterol c a o " ............................................................................................................... 2 7 Hình 7 - Thời gian xử lý tăng mạnh khi giảm giá trị fm insup ..................................... 37 Hình 8 - Sô l trợng tập phô biến và luật tăng mạnh khi giám dan fminsup ................38 Hình 9 - So ỉượng độ tin cậv tâng mạnh khi giảm dần fminconf. ............................... 39 Hình 10 - Thời gian xử lý tăng mạnh khi tăng nhẹ số lượng thuộc tín h ................... 39 Hình ì I - Thời gian xử lý tăng tuyến tính với số lượng bàn g h i ................................ 40 Hình 12- So lượng tập phổ hiến và luật tin cậy biến đổi theo toán tử T-norm .......40 Hình 13 - Két quá khai phá phàn ảnh sự thay đổi của ngưỡng được gắn với các tập m ờ ..................................................................................................................................... 4 1 Hình 14- Thuật toán phân phổi độ hỗ trợ trên hệ 3 B X L ............................................ 44 Hình 15 - Thuật toán phân phổi dữ liệu trên 3 B X L ..................................................... 45 Hình ỉ 6 - Thời ẹian sinh luật giảm mạnh khi tăng dần độ tin cậy tối thiểu ............ 49 Hình 1 7 - Sô luật tin cậv giàm mạnh khi tăng dần độ tin cậy toi thiêu minconf. .. 49 Hình 18 - Hình minh họa thuật toán phân chia .............................................................. 56 Hình 19- Thỏi gian xử lý giảm đáng kế khi tăng dân sỏ tiến trình song song ........ 58 Hình 20 - Thời gian xử lý phụ thuộc vào tỷ lệ sổ tiến trình loẹic và so CPU vật lý .................................................................................................................................................59 Hình 21 - Cừo sôgiao diện chính của FuzzyA R M ........................................................ 66 Hình 22 - Cứa sd dùng để tạo và sửa đổi tập mờ ...........................................................67 Hình 23 - Cứa sổ hiển thị kết quả khơi phá luật kết hợp mờ ........................................67 4 Danh m ụ c b ản g biểu ỉì(inc / - Vi dụ về một CSDL dọng < 2 ,iao d ịc h ...............................................................17 Bỉnự 2 - Các tập phô biến trong CSDL ở bảng ì với độ hô trợ tôi thiêu là 50%.. 17 Bang 3 - Luật kết hợp sinh từ tập phổ biển ACW .......................................................... 18 Bám: -t - CSDL khám và chân đoán bệnh tim mạch cùa 17 bệnh nhân .................. 22 Ba in: 5 - Rỏi rạc hóa thuộc tỉnh sổ rờ i rạc hữu hạn hoặc thuộc tinh họng mục.... 24 Bant 6 - Rời rọc hóa thuộc tính so "Lượng cholesterol trong m á u " ........................ 24 Bàn ĩ. 7 - Rời rạc hóa thuộc tỉnh só “ Tuỏi tác " ............................................................. 24 Bán ininsup [36]. Bàns. sau đây sẽ liệt kc lat cá những tập mục phổ biến (íYcqiicnt-itcmsct)trong CSDI. chi) ở bane 1 với aiá trị minsup băna 50%. C iíc tập mục phô hiền Đ ộ hỗ trọ tu ong iriij» c 10 0% ( 6 ) w, cw 8 3 % (5 ) A , D. T , A C , A w , C D , C T , A C W 6 7 % (4) A r, D W , T W . A C T , A T W . C D W , C T W , A C T W 5 0 % (3 ) lỉ;ÍMị> 2 - Các lập phô biến trong CSDL ỏ bảng I vói độ hỗ trọ tối thiêu là 50% [ Ho \I- IQ !Ậ C ) C ị 18 I nạt kèt hợp cỏ dạn ạ -V—1—->) . troné, dó X và Y là các tập mục thoa mãn dieu kiện X n V = 0 , còn c là độ tin cậy (confidence) của luật, c - ,v(XuY) / ,v(X). Vè mặl xác suât, clộ tin cậy c của một luật là xác suất (có điều kiện) xày ra Y với diêu kiện dã xây ra X. Một luật được xem là tin cậy nêu độ tin cậy c của nỏ lớn hơn hoặc băn 2 , một imưỡim m inconf nào dó do người dùng xác định: c > m incnnf |36|. Hài toán khai phá luật kết hợp (ở dạng đơn giản nhất) đặt ra như sau: Clìo một CSDL D. độ hỗ trợ tối thiểu minsnp, độ tin cậy tối thiểu minconf. Nãy tìm kiếm tất cà các luật kết hợp có dạnẹ X -» Y thỏa mãn độ hỗ trợ \ ( X u Y ) > iniii.sn/) và độ tin cậy cua luật c( X —>}') = í ( X u Y ) / s(X) > m in co nf. I lâu liêt các thuật toán dược dê xuất để khai phá luật kết hợp thường chia hài toán này ihành hai pha | 4 | [ 5 ] [ 2 0 ] |24Ị [34] [35]: Pha 1 : Tim tắt cà các tập mục phổ biển từ CSDI, tức là tìm tất cả các tập mục X thoa màn .v(X) > minsup. Dâv là pha tốn khá nhiều thời gian của CPU (CPIJbouiKỈ) và thời gian vào ra ô đĩa (I/O-bound). Pha 2 : Sinh các luậl tin cậy từ các tập phổ bien đã tìm thấy ở pha thứ nhất. Pha này moni! dối don giản và tốn kém ít thời gian so vói pha trên. Neu X là một tập phò hicn thì luật kêt hop dược sinh lừ X có dạng X '— —>.v\ X ', với X’ là tập con khác rồng cua X. X \ X ’ là hiệu cua hai tập hợp. và c là dộ tin cậy CIU1 luật thỏa mãn (' > minconf. Ví dụ. với tập pho bien ACW có độ tin cậy 67% ở hảng 2 và m in c o n f- 70% thì chúiiíi ta có thê sinh các luật kêl hợp sau đây: Thỏa mãn tninconf> 70%? L u ậ t kết họp Á "...> c w c ul°" -> A I V Có Không 117 - —-" -> A C Có AC - IV Có , i i r - - w" ~ > c Có (' Có " > A IV Báng 3 - L u ậ t kết h ọ p sinh tù tập phố biến A C VV 19 2.3 Những hu’ó'ng tiếp cận chính trong khai phá luật kết họp K.C l ừ khi d ư ợ c R. A e r a w a l đ ề x u ấ t v à o n ă m 1 9 9 3 [ 3 6 J, l ĩ n h v ự c k h a i p h á l u ậ t k ết h ợ p (lêu n a y d ã d ư ợ c n g h i ê n c ứ u v à p h á t tr iể n t h e o n h i ề u h ư ớ n g k h á c n h a u , c ỏ nhữ níi k iếm đỏ xuất nhầm vào cải liến tốc đ ộ th u ậ t to án , c ó những đề xuất nhầm lìm l u ậ t c ó ý n e li ĩa h ơ n . v .v . S a u d à y là m ộ t s ổ h ư ớ n g c h í n h . I .uột kết h ợ p n h ị p h â n (b in a ry a s s o c ia tio n ru le h o ặ c b o o le a n a s s o c ia tio n rule): là l u i ó ' i m nchiên c ứ u d ầ u tiên c ủ a luật kết h ợ p . M ầu h ế t c á c n g h iê n c ứ u ỏ’ thờ i kỳ d ầ u vê lu ậ t k ế t h ợ p đ ề u liê n q u a n đ ế n l u ậ t k ế t h ợ p n h ị p h â n [20] [35] [36]. T ro n g đạn« tâm luật kết hợp xuất hiện này, các m ục (thuộc tro n g g iao dịch cùa C S D L tính) chỉ đ ư ợ c là c ó hay không t â m v ề “ m ứ c đ ộ ” x u ấ t hiện. chứ không quan C ó n g h ĩ a lá v i ệ c m u a 2 0 c h a i b i a v à quan ] ch ai bia đ ư ợ c x e m là g i ố n g n h a u T h u ậ t to án lieu b ie n n h ắ t k h a i p h á d ạ n e l u ậ t n à y là t h u ậ t t o á n A p r i o r i v à c á c b ien t h e c u a n ó Ị 3 5 1. D â v l à (.l ana, l u ậ t d o n e i à n v à n h ư s a u n à y t a h i ê t c á c d ạ n g l u ậ t k h á c c ũ n g c ó thê c h u y ê n về dạnu luật n à y b ă n ẹ m ộ t s ố p h ư ơ n g p h á p .v.v. M ộ t v í d ụ v ề d ạ n g Dì lia sữa I liât kết categorical (lạng (n h ị hiện luật hợp có thuộc association phân - kct họp lính các thuật ‘yes = số và thuộc tính hạng binary, số - qu an titativ e, h ạ n g m ụ c vói các th u ộ c toán đã có tính N D mua đtrờnẹ= [ves ’ v ớ i đ ộ h ỗ tr ợ 2 0 % v à đ ộ tin c ậ y 8 0 % " rule): c á c th u ộ c tính c ủ a các C S D L plnroníĩ. p h á p rời rạ c h ó a n h ầ m ilụna "M ua bánh mì - 'yes ■ A luật n ày : ‘ye: V’ AND mua bơ = n h ư rời rạc h ó a , m ờ h ó a, này, các nhà m ục (quantitative th ự c tế c ó kiêu and rât d a c a t e g o r i c a l , .V .V .). D e p h á t nghiên cửu dã dề xuãl một so c h u y ề n d ạ n g luật n à y v ề d ạ n g nhị p h â n đ ố c ó th ế á p [34] [39]. M ột ví dụ về clạng luật này: "G iớ i linh z ‘Ntìin ’ AND Tuổi e '50..65 ’ AND Cân nặng e '60..80 ’ AND Lirợng đtrờnẹ IroníỊ mán - I20i)iơ/d/ - > Huye! áp = 'Cao v ớ i đ ộ h ỗ trợ 3 0 % , tlộ tin c ậ y 6 5 % " . l.uộl kết Imp mờ (fuzzy association rule): với những hạn chê còn gặp phải tron« C]ịiia trình rời rạc hóa các thuộc tính so (quantitative attributes), các nhà naliicn cửu dã đề xuất luật kết hợp mờ nhằm kliăc phục những hạn chê chuyên luật kết hợp về một dạne tự nhiên trên và hơn, gần gũi hơn với người sứ (lụnlì Ị4 Ị Ị9 1. MỘI ví dụ vè dạng luật nàv: "~Ho khan = ‘y es' AND sốt cao AND đan cơ 'ves ’ AND khó thớ - ‘yes ' => BỊ nhiễm SARS = 'yes với độ hỗ trợ 4% và dộ tin cậy 85%". Trong luật trên, dieu kiện soi cao ờ vế trái của luật là một thuộc tính đã dược 111 ờ hỏa.