Dự thảo tóm tắt luận án tiến sĩ toán học phát triển một số thuật toán hiệu quả k

DAI HOC QUOC GIA HA NOI TRUONG DAI HOC KHOA HOC TU NHIEN NGUYEN DUY HAM PHAT TRIEN MOT SO THUAT TOAN HIEU QUA KHAI THAC TAP MUC TREN CO SO DU LIEU SO LUQNG CO SU PHAN CAP CAC MUC DU THAO LUAN AN TIEN SI TOAN HOC Hà Nội - 2016 DAI HOC QUOC GIA HA NOI TRUONG DAI HOC KHOA HOC TU NHIEN NGUYEN DUY HAM PHAT TRIEN MOT SO THUAT TOAN HIEU QUA KHAI THAC TAP MUC TREN CO SO DU LIEU SO LUOQNG CO SU PHAN CAP CAC MUC Chuyên ngành: CƠ SỞ TOÁN CHO TIN HỌC Mã số: 62.10 DỰ THẢO LUẬN AN TIEN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1.NGUYEN THI HONG MINH 2. VÕ ĐÌNH BẢY Hà Nội - 2016 LỜI CAM ĐOAN Tôi xin cam đoan luận án này là công trình nghiên cứu do tác giả thực hiện dưới sự hướng dẫn của tập thể cán bộ hướng dẫn. Luận án có sử dụng thông tin trích dẫn từ nhiều nguồn tham khảo khác nhau, các thông tin trích dẫn đều được ghi rõ nguồn gốc. Các số liệu thực nghiệm, kết quả nghiên cứu trình bày trong luận án là hoàn toàn trung thực, chưa được công bồ bởi tác giả nào hay trong bất kì công trình nào khác.

Tác giả Nguyễn Duy Hàm LỜI CẢM ƠN Luận án Tiến sĩ này được thực hiện tại trường Đại học Khoa học và Tự nhiên — Đại học Quốc gia Hà Nội với sự hướng dẫn khoa học của TS. Nguyễn Thị Hồng Minh, PGS.Võ Đình Bảy và TS. Lê Quang Minh. Nghiên cứu sinh xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo, cô giáo hướng dẫn đã định hướng khoa học, tận tâm giúp đỡ và chỉ bảo tỉ mỉ trong suốt quá trình nghiên cứu mới có thể hoàn thiện bản luận án này.

Nghiên cứu sinh luôn ghi nhớ công lao dạy dỗ, đìu dắt vào con đường khoa học của có PGS.TS Hoàng Chí Thành — người đã hướng dẫn Nghiên cứu sinh ở giai đoạn đầu làm nghiên cứu khoa học. Nghiên cứu sinh xin chân thành cảm ơn các nhà khoa học, tác giả các công trình nghiên cứu đã được trích dẫn trong luận án vì đây là nguồn tài liệu quý báu để Nghiên cứu sinh phát triển và hoàn thiện các công bố của mình. Nghiên cứu sinh xin chân thành cảm ơn Ban Giám hiệu, lãnh đạo Khoa Toán — Co — Tin học, các thầy cô, giảng viên Bộ môn Tin học — Trường Đại học Khoa học Tự nhiên — Đại học Quốc gia Hà Nội đã tạo những điều kiện thuận lợi nhất để Nghiên cứu sinh hoàn thành chương trình học tập và thực hiện hoàn tất luận án của mình. Nghiên cứu sinh xin chân thành cảm ơn Ban Giám hiệu Trường Đại học An ninh nhân dân, tập thể giáo viên Bộ môn Toán — Tin học Trường Đại học An ninh nhân dân nơi Nghiên cứu sinh công tác và các bạn bè thân thiết đã luôn tạo điều kiện, động viên, khuyến khích và hỗ trợ tối đa để Nghiên cứu sinh hoàn thành bản luận án này.

Cuối cùng, con xin cảm ơn Bố Mẹ, đặc biệt là Mẹ — người đã luôn hy sinh tất cả vì sự nghiệp học tập của các con, rất tiếc mẹ đã không đợi được đến ngày con hoàn thành luận án. Xin cảm ơn gia đình, chị gái và các em đã luôn đồng hành, động viên, chia sẻ giúp duy trì nhiệt huyết và nghị lực để đi đến hoàn thành bản luận án này.Hồ Chí Minh, tháng 04 năm 2016 il MỤC LỤC LỜI CAM ĐOAN.- (2:21 22121 21212212121121211210112121121211 1121 cu H MỤC LỤC _. VI DANH MUC CAC HINH VE, DO THI .cccccccscsccsescssessseeessesesseseees VIII DANH MỤC CÁC KÍ HIỆU VÀ CHỮ VIẾT TÁT.--2- + XI MO DAU rcececsecscsssssssssssssssssssssssssssssssssssscsssusassucsssesussesussesesssseseeaeeees 1 CHƯƠNG1. TỎNG QUAN VẺ KHAI THÁC TẬP MỤC.

Bài toán khai thác tập mục. Bài toán khai thác EÌ.- --- --- c + Sc S1 2113113913911 1 11 15 11 11 1 11g g1 vn ri 14 1. Các phương pháp khai thác FI 1. 5p khảithác FI rênCSDL ngang.

Phương pháp khai thác FI trên CSDL dọc dựa trên FT—tree. Một số phương pháp khai thác F WI và F WUI trên QDB. Khai thác FWI In 4 0 0 00. Khai thác TRREÌL,.

Khai thác FI trên CSDL có sự phân cấp các mục. Tiếp cận bit—vector trong khai thác FI. Kết luận chương CHUONG 2. KHAI THACTAP MUC PHO BIEN TRÊN CƠ SỞ DỮ 81298985009) 9 25.

Thuật toán khai thác tập FW]. HH HH re 34 PANAHagtlaobsr. Thu ttoántính giaoc a haiIWS.-- Làn HH HH HH rên 38 P HN Iuonn ion. 40 PP 6 gìn so còn hố.

C utriic Multi bit s€ðTm€Tn(.--- -- - - 5< S4 121 EE E1 TH TH HT ng rên 5 2. Thu ánxácđ ¡nh giao MBiS. Thuật toán khai thác FWUI dựa trên MBIS—tree. Kết qua thurc nghi@m.

Một số Khai miGM ei. Cấu trúc DTab. Cấu trúc TR-tree. Thuật toán khai thác TRFWUI¿ sử dụng cấu trúc dữ liệu DTab.

Thuật toán khai thác nhanh TREWUIL dựa trên cấu trúc DHeap. Kết quả thực nghiệm.---2-22+2+++2EEEE2EE22211121127111711211271121121E 1E Xe 70 ca na. KHAI THÁC TẬP MỤC PHỎ BIẾN TRÊN CƠ SỞ DỮ LIEU SO LUQNG CÓ SỰ PHÂN CÁP CÁC MỤC. Thuật toán khai thác FWUI trên HQ DB.

Thuật toán xác định weight cho các mục C ha. Thuật toán thêm mục cha vào CS. Một số cải tiến nâng cao hiệu quả khai thác F WUI trên HQDB. Cấu trúc EDBV.

Tính tidset nút cha từ tidsef nÚt COII. Kiém tra mối quan hệ cha con đối với các mục trong tập mục. Thu t toán khai thác nhanh FWUI trên HQDB. Kết quả thực nghiệm.

CSDL th c nh ố. 93 KG (no nh. Kết luận chương.-------222vccv+++rrttttEE2221111112 rrrrrrrrrrrrrrrrrrree 100 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN. _ Các kết quả đạt được.

_ Hướng phát triển.rrrrree 102 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIÁ LIÊN QUAN ĐẾN LUẬN ÁN. (5c S2 2121 2121211212112121121211211121121211 11 1e xe, 103 TAI LIEU THAM KHẢO. 2 5-52S22SSE2ESE2E£EE2EvEEzEeErkererrred 104 Bang 1. DANH MỤC BẢNG Các giao dchc a BDB D.

5c St HH ret 8 Các giao dchc a HDB DB. 5c St, 9 IDc acác m Cc a HBD DB.---- S ScS net 9 Các giao dchc a HDB DBb ng ID. 11 Tr ngs cácm cc aQDB DB.- net 11 Các giao dchc a WDB D.- ác HH HH Hư 12 Tr ngs c acác m cc aWDB DB. 14 BDB DB theo chỉ u d c.

5555 5+5 Street 19 Giátr twc aCSDLDB trong ví d_ I.---- 23 twu các giao dchc a DB trong víd_ I.------ 25 HDB DB trong Ví d 1.2 sau khi thêm m c cha. 35 DBVc a bitLvector trong Vid 2.1 oe ee eeeeeeteeseseeeteeteseeneeees 35 IWSt_ bitLvector trong Vid 2. ee eseeeescseeeeseneeseneseenenees 35 Ch s cácbitlc aIWS(X).SH ST nHn HH HH 44 Môt CSDLth c nghi m. 555 S5 St erereeireg 47 Bit vector v 1 96 ph n(.Ặ 5 SĂS SH eiren 51 MBiSt bitLvector B ng2.

75 Tên m thằng aCác m C. 82 fWu C a Các gØ1aO (Ì CH. - «sgk HH ng nrkt 82 TplI-itemsetph bị n.--cc-c<c+ 86 Bi udi ns nguyénKU id ngb niiin,sm [Liinlàm tword. 93 Các m c trên cây PHAN p.--- ¿55 5 Sky 94 Sosánhb nh vàs L' ng các m C .-------+ 94 Th cnghi m trên CSDL SALEI FACT:SYNC.- 95 So sánh th ¡ gianch y trên CSDL SALELEACTL1997.

DANH MUC CAC HINH VE, DO THI 909. 9 Cây phânc p Tr bí udi n theo ID. 555 <5<c+xscsxsserer 10 Thu ttoán Apriori trong khai tháct pm cph bi n. 16 Thu ttoán FP: Growth d atrênc utrúc EP[ tree.

--- -- 17 Thu ttoán Eclat d atrênc u trúc [Ti tree.---«--«-s«<<+>+ 18 Cây IT tree v ¡ minsup = 0,5 c a CSDL DB.------ 19 Thu ánxácđị nh giao hai [WS.ĂẶĂ Set 39 Thuật toán tính ws của tập mục XX. - - cà snnne re 4I Thuật toán xây dựng cây I[WS-tree. Teen 43 Thuật toán khai thác FWI dựa trên IW S—tree.----c-ccccccc# 43 IWS-tree với nút A(minws = ()¿4).- ----c cty 44 IWS-tree với nútA vàB(minws = 4) .5-5 S2 ccxcccceeeesre 45 IWS-tree với minWS = (¿44.-- --- + 2S v1 v12 1 1 1 cớ 46 So sánh thời gian chạy với CSDL RETAIL. ----- --- 47 So sánh thời gian chạy với CSDL BMS-POS.

47 So sánh thời gian chạy với CSDL SALE-FACT-1997. 48 So sánh thời gian chạy với CSDL SALE-FACT-1997+1998. 48 So sánh thời gian chạy với CSDL SALE-FACT-SYNC. 48 So sánh thời gian chạy với CSDL CONNECT.- 48 So sánh thời gian chạy với CSDL ACCIDENTTS.- 49 So sánh bộ nhớ sử dụng với CSDL RETAIL.

----- --- 49 So sánh bộ nhớ sử dụng với CSDL BMS-—POS.- 49 So sánh bộ nhớ sử dụng với CSDL SALE-FACT-1997. So sánh bộ nhớ sử dụng với CSDL SALE-FACT-1997+1998. 50 So sánh bộ nhớ sử dụng với CSDL SALE-FACT-SYNC. 50 So sánh bộ nhớ sử dụng với CSDL CONNECTT.

-------- 50 So sánh bộ nhớ sử dụng với CSDL ACCTDENT. -- 50 Thuật toán xác định giao hai MBIS.- 55c s+cscsxsersxserrer 53 Thuật toán tính wus dựa trên MBIS.---5-ccScss+sekreereskrrer 54 Thuật toán khai thác FWUI dựa trên MBIS-tree. ---- --«- 56 So sánh thời gian chạy trên CSDL RETAIL.-- ----- -- 57 So sánh thời gian chạy trên CSDL BMS-POS.- 57 So sánh thời gian chạy trên CSDL SALE-EFACT-1997. 57 So sánh thời gian chạy trên CSDL SALE-EFACT-1997+1998.

58 So sánh thời gian chạy trên CSDL SALE-EFACT-SYNC. 58 So sánh thời gian chạy trên CSDL CONNEC TT. ------‹- 58 So sánh thời gian chạy trên CSDL ACCIDENTS.- 58 So sánh bộ nhớ sử dụng trên CSDL RETAIL. --- 58 So sánh bộ nhớ sử dụng trên CSDL BMS—POS.

-«- 59 So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-1997. 59 So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-1997+1998.59 So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-SYNC. 59 So sánh bộ nhớ sử dụng trên CSDL CONNECTT. -- --- -«« 60 So sánh bộ nhớ sử dụng trên CSDL ACCIDENT.

62 Thuật toán tạo TR-tree sử dụng D Tab. -- 55 se ssseesersersred 64 Thuật toán lọc ra TREW UÏ,,.-- -- Sc 2c 3t 9 re 66 DHeap với k= 5 với CSDL trong ví dụ l. Thuật toán chèn một nút mới vào DHeap. --- 5 «+ s++sx>+ 68 Thuật toán tạo TR-tree sử dụng DHeap.

--- 5c c+ssee+ 69 Thuật toán lọc ra TREW UÏ,,.-- G2 1S SH ng re. 70 So sánh thời gian chạy trên CSDL MBS—POS. --- 70 So sánh thời gian chạy trên CSDL RETAIL,.-------++ 71 So sánh thời gian chạy trén CSDL CONNECT. --- --- 71 So sánh thời gian trên CSDL SALE—FACT—1997.----s+s=ss+ 71 So sánh thời gian trên CSDL SALE-FACT—1997+1998.

71 So sánh thời gian trên CSDL SALE-FACT-SYNC.- 72 Tập các cây phân cấp Tr. ee 75 Thuật toán tính weight cho các mục cha. -- --- + sxssxssveseesers 79 Thuật toán thêm mục cha vào CSTDL .--- 55+ 55+ + +++s++ss++s+ 80 Thuật toán khai thác FWUI từ HQDB.--5- 5c csxsessxseseres 81 Cay HIT-tree với CSDL HD và minwus = Ö,6.-- -- + 83 Sử dụng các phép AND và dịch bit đề tách các đoạn hai byte. 87 Thuật toán tính nhanh wus của các tập mục .- ---«--+-+ 89 Thuật toán xác định tidset các mục và tính twu của các giao dịch.90 Thuật toán khai thác nhanh FWUI trên HỌDB.