Tài liệu Khai thác tập mục hữu ích cao trên cơ sở dữ liệu tăng trưởng

CHUẨN Y CỦA HỘI ĐỒNG BẢO VỆ LUẬN VĂN --o0o-- Luận văn tựa đề “KHAI THÁC TẬP MỤC HỮU ÍCH CAO TRÊN CƠ SỞ DỮ LIỆU TĂNG TRƯỞNG” được Võ Thiện Khoa thực hiện và nộp nhằm thỏa một trong các yêu cầu tốt nghiệp Thạc sĩ ngành Khoa Học Máy Tính. Ngày bảo vệ luận văn, TPHCM, ngày 05 tháng 12 năm 2015 Chủ tịch Hội đồng GS.TSKH. Hoàng Văn Kiếm Đại học Quốc tế Hồng Bàng Ngày tháng năm 20 Hiệu Trưởng PGS.TS. Thái Bá Cần Ngày tháng năm 20 Người hướng dẫn PGS.TS. Võ Đình Bảy Đại học Công Nghệ - TpHCM Ngày tháng năm 20 Viện Đào Tạo Sau Đại Học GS. TSKH. Hoàng Văn Kiếm Ngày tháng năm 20 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC QUỐC TẾ HỒNG BÀNG Luận văn thạc sĩ: Khai thác tập mục hữu ích cao trên cơ sở dữ liệu tăng trưởng Do học viên: Võ Thiện Khoa - Cao học khóa: 1 – Đợt 2 - Ngành: Khoa học máy tính thực hiện. Người hướng dẫn: PGS. TS. Võ Đình Bảy. Đã bảo vệ trước Hội đồng, ngày: 05/12/2015 theo Quyết định số ……., / ngày / của Hiệu trưởng ĐH Quốc Tế Hồng Bàng. Thành phần Hội đồng đánh giá Luận văn Thạc sĩ gồm: TT Họ và tên Chức danh Hội đồng 1 GS.TSKH. Hoàng Văn Kiếm Chủ tịch 2 PGS.TS. Trần Công Hùng Phản biện 1 3 PGS.TS. Lê Hoàng Thái Phản biện 2 4 TS. Nguyễn Hòa Ủy viên 5 TS. Lê Xuân Trường Ủy viên, Thư ký Chủ tịch Hội đồng đánh giá Luận văn GS.TSKH. Hoàng Văn Kiếm LÝ LỊCH CÁ NHÂN  1. SƠ LƯỢC LÝ LỊCH - Họ tên : Võ Thiện Khoa. - Ngày sinh : 16/10/1983. - Nơi sinh : Thành Phố Hồ Chí Minh. - Tốt nghiệp THPT : Trường THPH Bà Điểm, xã Bà Điểm, huyện Hóc Môn, TP.HCM. 2. QUÁ TRÌNH HỌC TẬP Thời gian Nơi học tâp 2001 - 2003 Học tại trường Trung cấp Giao Thông Vận Tải khu vực 3. 2004 - 2006 Học tại trường Cao đẳng Công Nghiệp 4. 2007 - 2009 Học tại trường Đại học Kỹ Thuật Công Nghệ. 3. QUÁ TRÌNH CÔNG TÁC Thời gian Nơi công tác 2009 - 2010 Làm việc tại Công ty phát triển phần mềm Khoa Việt. 2011 - nay Làm việc tại Bệnh viện Chợ Rẫy. - Địa chỉ liên lạc: 8/5D tổ 4 ấp Bắc Lân, xã Bà Điểm, huyện Hóc Môn, TP. HCM. - Email: [email protected]. - Điện thoại di động: 0908.650.611. i LỜI CAM ĐOAN  Tôi cam đoan rằng luận văn “Khai thác tập mục hữu ích cao trên cơ sở dữ liệu tăng trưởng” là bài nghiên cứu của chính tôi. Ngoại trừ những tài liệu tham khảo được trích dẫn trong luận văn này, tôi cam đoan rằng phần còn lại của luận văn này chưa từng được công bố hay được sử dụng để nhận bằng cấp ở những nơi khác. Không có sản phẩm hay nghiên cứu nào của người khác được sử dụng trong luận văn này mà không được trích dẫn theo đúng quy định. TP. HCM, ngày tháng năm 2015 Tác giả luận văn Võ Thiện Khoa ii LỜI CẢM ƠN  Lời đầu tôi xin chân thành cảm ơn TS. Võ Đình Bảy đã tận tình truyền đạt và hướng dẫn tôi trong suốt thời gian thực hiện luận văn này. Thầy luôn tận tâm giúp đỡ, định hướng cho tôi trong suốt thời gian nghiên cứu khoa học. Thầy đã giúp tôi tiếp cận với khoa học và biết cách sáng tạo trong khoa học, với những điều mới trong xã hội và đạt được thành công trong bài nghiên cứu của mình. Tiếp theo tôi xin bày tỏ lòng biết ơn đến Ban Giam hiệu, quí thầy cô trong Viện đào tạo Sau Đại học trường Đại học Quốc tế Hồng Bàng đã cung cấp những kiến thức quý báu cho tôi trong suốt quá trình học tập và nghiên cứu tại trường. Cuối cùng, chân thành gởi lời cảm ơn đến gia đình, bạn bè và những người thân luôn quan tâm và giúp đỡ tôi trong suốt thời gian học tập và nghiên cứu hoàn thành luận văn này. Vì thời gian có hạn và kiến thức còn hạn chế, nên luận văn khó tránh khỏi những thiếu sót, rất mong nhận được sự đóng góp ý kiến quý báu của quý thầy cô, anh chị và các bạn. iii TÓM TẮT  Khai thác dữ liệu là quá trình khám phá thông tin tìm ẩn và các mối liên hệ lẫn nhau có trong các cơ sở dữ liệu lớn. Khai thác dữ liệu truyền thống là thường dạng tĩnh và xử lý dữ liệu được thực hiện hàng loạt. Nhưng trên thực tế, cơ sở dữ liệu thường xuyên biến động do đó cách này không hiệu quả gây lãng phí khi một lượng nhỏ dữ liệu được thêm vào cơ sở dữ liệu lớn. Do đó, Hong và các đồng sự [11] đã đề xuất ra khái niệm tập gần phổ biến để khai thác tập phổ biến trên cơ sở dữ liệu tăng trưởng. Tác giả đã xử dụng hai ngưỡng phổ biến đó là: ngưỡng phổ biến trên (tương đương với ngưỡng phổ biến tối thiểu, minSup) và ngưỡng phổ biến dưới để giảm số lần duyệt lại cơ sở dữ liệu gốc. Thuật toán Pre-HUI là thuật toán khai thác tập mục hữu ích cáo trên cơ sở dữ liệu tăng trưởng được đề xuất vào năm 2014 [7]. Luận văn đề xuất thuật toán khai thác tập mục hữu ích cao trên cơ sở dữ liệu trưởng dựa trên cấu trúc cây WIT (Weighted Itemset-Tidset tree) bằng cách tỉa những ứng viên có độ hữu ích thấp và cải tiến bước sinh tập ứng viên trước khi sử dụng phương pháp khai thác dữ liệu được đề xuất. Do đó, thuật toán mới này sẽ cải thiện tốt hơn về thời gian và bộ nhớ sử dụng trong quá trình khai thác tập mục hữu ích cao. iv ABSTRACT  Data mining is the process of discovering hidden information and mutual relationships in large databases. Traditional data mining is often static and data is processed in batch mode. But in reality, the database is constantly fluctuating so this approach is inefficient when a small amount of data is added to the database. Therefore, Hong and colleagues [11] have proposed the concept of “Pre-large” to discover nearly frequent itemsets in incremental databases. The authors have used two bounds: upper bound utility and lower bound utility to reduce the number of scans on the original database. Pre-HUI is an algorithm for mining high itemset utility in incremental databases [7]. Thesis proposes a new algorithm for mining high itemset utility in incremental databases based on the WIT tree (Weighted itemset-Tidset tree) by pruning the low utility candidates. Therefore, this new algorithm will improve the time and memory used in the process of mining high itemset utility. v NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN -o0o............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. vi NHẬN XÉT CỦA GIẢNG VIÊN PHẢN BIỆN 1 -o0o............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. vii NHẬN XÉT CỦA GIẢNG VIÊN PHẢN BIỆN 2 -o0o............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. viii NHẬN XÉT CỦA HỘI ĐỒNG PHẢN BIỆN -o0o............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ix MỤC LỤC LÝ LỊCH CÁ NHÂN ................................................................................................ i LỜI CAM ĐOAN ..................................................................................................... ii LỜI CẢM ƠN .......................................................................................................... iii TÓM TẮT ................................................................................................................ iv ABSTRACT ...............................................................................................................v MỤC LỤC ..................................................................................................................x DANH MỤC HÌNH VẼ ......................................................................................... xii DANH MỤC BẢNG .............................................................................................. xiii DANH MỤC CÁC CHỮ VIẾT TẮT.....................................................................xv CHƯƠNG 1: TỔNG QUAN.....................................................................................1 1.1 Lý do chọn đề tài, lĩnh vực nghiên cứu .............................................................1 1.2 Vấn đề nghiên cứu của đề tài ............................................................................2 1.3 Mục tiêu nghiên cứu ..........................................................................................2 1.4 Những nội dung chính yếu cần nghiên cứu ......................................................2 1.5 Cấu trúc luận văn ..............................................................................................2 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT ........................................................................4 2.1 Tổng quan về khai thác dữ liệu .........................................................................4 2.1.1 Khám phá tri thức và khai thác dữ liệu. ....................................................4 2.1.2 Quá trình khám phá tri thức.......................................................................4 2.1.3 Các kỹ thuật khai thác dữ liệu ...................................................................7 2.1.4 Ứng dụng trong khai thác dữ liệu ..............................................................7 2.1.5 Những thách thức trong khai thác dữ liệu .................................................8 2.2 Tổng quan về khai thác luật kết hợp .................................................................8 2.3 Giới thiệu về khai thác tập mục hữu ích cao ...................................................12 2.4 Khai thác tập mục hữu ích cao trên cơ sở dữ liệu tăng trưởng .......................21 2.4.1 Tổng quan.................................................................................................21 x 2.4.2 Một số định nghĩa của bài toán ...............................................................24 2.4.3 Nội dung thuật toán Pre-HUI ..................................................................27 2.4.4 Minh họa thuật toán .................................................................................32 CHƯƠNG 3: THUẬT TOÁN CẢI TIẾN .............................................................39 3.1 Ưu và khuyến điểm của thuật toán Pre-HUI ...................................................39 3.2 Thuật toán cải tiến dựa trên cấu trúc cây WIT ................................................39 3.2.1 Nội dung thuật toán ..................................................................................39 3.2.2 Minh họa thuật toán .................................................................................44 3.2.3 Những điểm mới của thuật toán cải tiến ..................................................51 CHƯƠNG 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ .................................................52 4.1 Môi trường thực nghiệm .................................................................................52 4.2 Giới thiệu cơ sở dữ liệu thực nghiệm ..............................................................52 4.2.1 Tổng quan về CSDL thực nghiệm ............................................................52 4.2.2 So sánh thời gian chạy thực nghiệm ........................................................53 4.3 Thực nghiệm trên CSDL chuẩn ......................................................................56 4.3.1 Thực nghiệm trên CSDL Retail ................................................................56 4.3.2 Thực nghiệm trên CSDL BMS-POS .........................................................59 4.4 Kết quả thực nghiệm .......................................................................................63 CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .....................................64 5.1 Kết luận ...........................................................................................................64 5.2 Hạn chế của đề tài ...........................................................................................64 5.3 Hướng phát triển .............................................................................................65 DANH MỤC TÀI LIỆU THAM KHẢO ...............................................................66 1. Tài liệu tiếng việt ..............................................................................................66 2. Tài liệu tiếng anh ...............................................................................................66 xi DANH MỤC HÌNH VẼ Hình 2.1: Qui trình khám phái tri thức. ........................................................................... 5 Hình 2.2: Xây dựng cây WIT-Tree. .............................................................................. 19 Hình 2.3: Thuật toán TWU-Mining. ............................................................................. 20 Hình 2.4: Kết quả thuật toán TWU-Mining. ................................................................. 21 Hình 2.5: Thuật toán Pre-HUI. ...................................................................................... 29 Hình 3.1: Thuật toán cải tiến. ........................................................................................ 42 Hình 3.2: Biểu diễn cây H_PTWU trên CSDL D. ........................................................ 45 Hình 3.3: Biểu diễn cây H_PTWU khi xóa itemset A .................................................. 47 Hình 3.4: Biểu diễn cây H_PTWU khi cập nhật itemset B ........................................... 47 Hình 3.5: Biểu diễn cây H_PTWU đã cập nhật các 1-itemset ...................................... 48 Hình 3.6: Biểu diễn cây H_PTWU khi xét nút B có 2-itemset . ................................... 49 Hình 3.7: Biểu diễn cây H_PTWU khi xét nút B có 3-itemset từ 2-itemset. ................ 49 Hình 3.8: Biểu diễn cây H_PTWU khi đã hoàn tất thêm giao dịch mới. ...................... 50 Hình 4.1: Thực nghiệm CSDL bán thuốc khi thêm 2.000 giao dịch cho mỗi lần. ........ 53 Hình 4.2: Thực nghiệm CSDL bán thuốc khi thêm 4000 giao dịch cho mỗi lần. ......... 54 Hình 4.3: Thực nghiệm CSDL bán thuốc khi thêm 5.000 giao dịch cho mỗi lần. ....... 55 Hình 4.4: Thực nghiệm CSDL Retail khi thêm 1.000 giao dịch cho mỗi lần. .............. 57 Hình 4.5: Thực nghiệm CSDL Retail khi thêm 2.000 giao dịch cho mỗi lần. .............. 58 Hình 4.6: Thực nghiệm CSDL Retail khi thêm 3.000 giao dịch cho mỗi lần. .............. 59 Hình 4.7: Thực nghiệm CSDL BMS-POS khi thêm 10.000 giao dịch cho mỗi lần. .... 60 Hình 4.8: Thực nghiệm CSDL BMS-POS khi thêm 20.000 giao dịch cho mỗi lần. .... 61 Hình 4.9: Thực nghiệm CSDL BMS-POS khi thêm 30.000 giao dịch cho mỗi lần. .... 62 xii DANH MỤC BẢNG Bảng 2.1: Bảng biểu diễn CSDL giao dịch .................................................................. 13 Bảng 2.2: Bảng lợi nhuận của các item trong CSDL ................................................... 14 Bảng 2.3: Bảng độ hữu ích các giao dịch trong CSDL ................................................ 15 Bảng 2.4: Two-Phase với 1-itemset ............................................................................. 17 Bảng 2.5: Two-Phase với 2-itemset ............................................................................. 17 Bảng 2.6: Two-Phase với 3-itemset ............................................................................. 17 Bảng 2.7: Two-Phase với các itemset có độ hữu ích cao. ............................................ 18 Bảng 2.8: WIT-Tree với từng item đơn........................................................................ 19 Bảng 2.9: Ví dụ 2 giao dịch .......................................................................................... 22 Bảng 2.10: Ví dụ về bảng lợi nhuận ............................................................................. 22 Bảng 2.11: Bảng lợi nhuận ........................................................................................... 24 Bảng 2.12: CSDL ban đầu ............................................................................................ 25 Bảng 2.13: CSDL thêm vào.......................................................................................... 25 Bảng 2.14: Bảng tập itemset có trọng số giao dịch lớn và lợi ích thật sự .................... 32 Bảng 2.15: Bảng tập itemset có trọng số giao dịch gần lớn và lợi ích thật sự ............. 32 Bảng 2.16: Bảng các độ hữu ích của các giao dịch mới ............................................... 33 Bảng 2.17: Bảng twu và au của 1-itemset trong giao dịch mới ................................... 34 Bảng 2.18: Bảng cập nhật 1-itemset trong tập 𝐻𝑇𝑊𝑈1𝐷 .......................................... 34 Bảng 2.19: Bảng cập nhật 1-itemset trong tập 𝐻𝑇𝑊𝑈1𝐷 .......................................... 35 Bảng 2.20: Bảng twu Large và Pre-large 1-itemset với au của chúng ......................... 36 Bảng 2.21: Bảng kết quả cuối cùng thuật toán Pre-HUI .............................................. 37 Bảng 2.22: Bảng tập hữu ích cao trong thuật toán Pre-HUI ........................................ 37 Bảng 3.1: Bảng twu và au của các 1-itemset trong giao dịch mới ............................... 46 xiii Bảng 3.2: Bảng các itemset có độ hữu ích cao trong thuật toán cải tiến ...................... 50 Bảng 4.1: Thời gian thực nghiệm trên CSDL bán thuốc với mỗi lần thêm là 2.000 giao dịch ........................................................................................................................ 53 Bảng 4.2: Thời gian thực nghiệm trên CSDL bán thuốc với mỗi lần thêm là 4.000 giao dịch. ....................................................................................................................... 54 Bảng 4.3: Thời gian thực nghiệm trên CSDL bán thuốc với mỗi lần thêm là 5.000 giao dịch. ....................................................................................................................... 55 Bảng 4.4: Các CSDL thực nghiệm chuẩn .................................................................... 56 Bảng 4.5: Thời gian thực nghiệm trên CSDL Retail với mỗi lần thêm là 1.000 giao dịch. ............................................................................................................................... 56 Bảng 4.6: Thời gian thực nghiệm trên CSDL Retail với mỗi lần thêm là 2.000 giao dịch ................................................................................................................................ 57 Bảng 4.7: Thời gian thực nghiệm trên CSDL Retail với mỗi lần thêm là 2.000 giao dịch. ............................................................................................................................... 58 Bảng 4.8: Thời gian thực nghiệm trên CSDL BMS-POS với mỗi lần thêm là 10.000 giao dịch ............................................................................................................ 60 Bảng 4.9: Thời gian thực nghiệm trên CSDL BMS-POS với mỗi lần thêm là 20.000 giao dịch ............................................................................................................ 61 Bảng 4.10: Thời gian thực nghiệm trên CSDL BMS-POS với mỗi lần thêm là 30.000 giao dịch ............................................................................................................ 62 xiv DANH MỤC CÁC CHỮ VIẾT TẮT Ký hiệu Ý nghĩa tiếng Việt Ý nghĩa tiếng Anh AU Độ hữu ích thực sự Actual utility CSDL Cơ sở dữ liệu Data base H_PTWU Tập các tập mục có trọng Large (high) and Pre-large số độ hữu ích lớn và tiền transaction-weighted utilization lớn của giao dịch HTWU Tập các tập mục có trọng Large (high) số độ hữu ích lớn của giao transaction-weighted dịch utilization HU Tập các tập mục có độ High-utility itemset hữu ích cao Itemset Tập mục KDD Khám phá tri thức trong Knowledge Discovery in cơ sở dữ liệu Databases KTDL Khai thác dữ liệu Pre-HUI Thuật toán Pre-HUI PTWU Tập các tập mục có trọng Pre-large số độ hữu ích tiền lớn của transaction-weighted utilization giao dịch SL Ngưỡng độ hữu ích dưới The lower utility threshold SU Ngưỡng độ hữu ích trên The upper utility threshold TID Mã giao dịch Transaction identification TU Độ hữu ích của giao dịch Transaction utility TWU Trọng số độ hữu ích của Transaction-weighted giao dịch utilization WIT-Tree Cây WIT Itemset Data Mining Weighted Itemset-Tidset tree xv CHƯƠNG 1: TỔNG QUAN 1.1 Lý do chọn đề tài, lĩnh vực nghiên cứu Trong những năm gần đây, cùng với sự phát triển vượt bậc của công nghệ thông tin, truyền thông, khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin không ngừng được nâng cao. Với lượng dữ liệu khổng lồ và luôn gia tăng theo thời gian, rõ ràng các phương pháp phân tích dữ liệu truyền thống sẽ không còn hiệu quả, gây tốn kém và dễ dẫn đến những kết quả sai lệch. Để có thể khai thác hiệu quả các cơ sở dữ liệu lớn, một lĩnh vực khoa học mới đã ra đời: Khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases – KDD). Khai thác dữ liệu (Data Mining) là một công đoạn chính trong quá trình khám phá tri thức, nhằm tìm kiếm, phát hiện các tri thức mới, hữu ích tiềm ẩn trong các cơ sở dữ liệu lớn. Việc khai thác tập phổ biến thường được mô tả là một quá trình lấy thông tin có giá trị từ cơ sở dữ liệu lớn, nó bắt nguồn từ dạng mẫu có sẵn tồn tại trong cơ sở dữ liệu, các mẫu này có khuynh hướng gom nhóm lại với nhau và được định nghĩa như là một mô hình khai thác. Khai thác tập mục hữu ích cao (high-utility itemset) là một mở rộng của bài toán khai thác tập mục phổ biến, đã được nhiều tác giả quan tâm với mục đích đánh giá ý nghĩa của các tập mục trong khai thác luật kết hợp. Để khai thác tập mục hữu ích cao, một giá trị được sử dụng đó là lợi ích của itemset, chẳng hạn tổng lợi nhuận mà doanh nghiệp thu được nếu bán itemset ấy trong tập giao dịch. Khác với khai thác itemset phổ biến, lợi ích của itemset không thỏa tính chất bao đóng giảm (downward closure property) nên độ phức tạp của bài toán cao. Ngoài ra, CSDL thường biến động, các giao dịch thường xuyên được cập nhật chẳng hạn được thêm mới thường xuyên. Việc cập nhật lại các itemset kết quả khi cơ sở dữ liệu thay đổi cũng là một trong những nhu cầu cấp thiết. Chính vì vậy tôi chọn đề tài “Khai thác tập mục hữu ích cao trên cơ sở dữ liệu tăng trưởng” nhằm góp phần rút ngắn thời gian cũng như việc sử dụng bộ nhớ trong quá trình khai thác. Trang 1 1.2 Vấn đề nghiên cứu của đề tài  Làm thế nào để khai thác tập mục trên CSDL lớn và thường xuyên thay đổi?  Có cách nào để cập nhật lại tập mục khi dữ liệu thay đổi?  Làm thế nào để giảm số lần duyệt lại CSDL gốc trong quá trình khai thác dữ liệu?  Bài toán có thể áp dụng trong khai thác dữ liệu bán thuốc tại bệnh viện ở Thành phố Hồ Chí Minh hay không? 1.3 Mục tiêu nghiên cứu Nghiên cứu bài toán khai thác tập phổ biến trên cơ sở dữ liệu tăng trưởng. Nghiên cứu thuật toán Pre-HUI trong việc khai thác tập mục hữu ích cao. Phát triển thuật toán mới cho khai thác tập mục hữu ích cao trên cơ sở dữ liệu tăng trưởng. Áp dụng vào thực tế với CSDL bán thuốc của bệnh viện. 1.4 Những nội dung chính yếu cần nghiên cứu - Tìm hiểu về những xu hướng hiện nay trong khai thác dữ liệu. - Tìm hiểu một số kỹ thuật và thuật toán đang được sử dụng trong khai thác dữ liệu. - Các thuật toán khai thác tập hữu ích cao (high utility itemset – HUI). - Nghiên cứu bài toán khai thác tập mục hữu ích cao trên CSDL tăng trưởng. - Nghiên cứu và đề xuất thuật toán cải tiến nhằm nâng cao hiệu quả về mặt thời gian khai thác. - Thực nghiệm trên các cơ sở dữ liệu chuẩn để minh chứng tính hiệu quả của thuật toán cải tiến. 1.5 Cấu trúc luận văn Luận văn tổ chức thành 5 chương có nội dung như sau: - Chương 1: Giới thiệu tổng quan tới bối cảnh thực tiễn định hình hướng nghiên cứu của luận văn. Trang 2 - Chương 2: Trình bày tổng quan về khai thác dữ liệu (KTDL), khai thác luật kết hợp và phương pháp khai thác tập phổ biến. Giới thiệu về khai thác tập mục hữu cao và thuật toán. Nghiên cứu bài toán khai thác tập mục hữu ích cao từ cơ sở dữ liệu tăng trưởng và thuật toán Pre-HUI. - Chương 3: Nghiên cứu mặt hạn chế của thuật toán Pre-HUI. Nghiên cứu và đề xuất thuật toán cải tiến nhằm nâng cao hiệu quả về mặt thời gian khai thác dựa trên cấu trúc cây WIT(Weighted Itemset-Tidset tree). - Chương 4: Giới thiệu môi trường thực nghiệm, CSDL dùng để thực nghiệm. So sánh về thời gian thực hiện giữa Pre-HUI và thuật toán đề xuất. - Chương 5: Kết luận và hướng phát triển. Trang 3