Luận văn Thạc sĩ Công nghệ thông tin: Khai thác dàn tập phổ biến đóng sử dụng cấu trúc DSBV

Chia sẻ: Bobietbo | Ngày: | Loại File: PDF | Số trang:72

Thêm vào BST

Báo xấu

35
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của luận văn này hướng tới cách giải quyết bài toán: Từ cơ sở dữ liệu có sẵn, làm sao để khai thác toàn bộ các tập phổ biến đóng, quan hệ cha – con giữa các tập này, cải tiến giải thuật khai thác dàn các tập phổ biến đóng để việc khai thác tập luật kết hợp sau này được dễ dàng và hiệu quả hơn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Khai thác dàn tập phổ biến đóng sử dụng cấu trúc DSBV

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC NGOẠI NGỮ TIN HỌC ----------------- LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN TRẦN PHÚ DƯ KHAI THÁC DÀN TẬP PHỔ BIẾN ĐÓNG SỬ DỤNG CẤU TRÚC DSBV Ngành: CÔNG NGHỆ THÔNG TIN Mã số chuyên ngành: 60480201 NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. LÊ HOÀI BẮC Tp. HCM, tháng 6 năm 2019
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC NGOẠI NGỮ TIN HỌC ----------------- LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN TRẦN PHÚ DƯ KHAI THÁC DÀN TẬP PHỔ BIẾN ĐÓNG SỬ DỤNG CẤU TRÚC DSBV Ngành: CÔNG NGHỆ THÔNG TIN Mã số chuyên ngành: 60480201 NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. LÊ HOÀI BẮC Tp. HCM, tháng 6 năm 2019
LỜI CAM ĐOAN Tôi cam đoan: báo cáo luận văn “Khai Thác Dàn Tập Phổ Biến Đóng Sử Dụng Cấu Trúc DSBV” là công trình nghiên cứu của riêng tôi và được sự hướng dẫn khoa học của PGS.TS.Lê Hoài Bắc. Các kết quả nghiên cứu có tính độc lập riêng, không sao chép bất kỳ tài liệu nào và chưa công bố nội dung này ở bất kỳ đâu. Các số liệu trong luận văn được sử dụng trung thực, nguồn trích dẫn có chú thích rõ ràng, có tính kế thừa, phát triển từ các tài liệu, tạp chí, các công trình nghiên cứu khác. Tôi xin hoàn toàn chịu trách nhiệm về lời cam đoan của tôi. TP. HCM, ngày 25 tháng 10 năm 2018 Tác giả Trần Phú Dư
Nhận xét của Thầy hướng dẫn: ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ...........................................................................................................................................
Nhận xét của Thầy phản biện: ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ...........................................................................................................................................
LỜI CẢM ƠN Lời đầu tiên, Tôi xin chân thành bày tỏ lòng biết ơn sự nhiệt tình, và những kiến thức bổ ích mà các thầy cô giảng dạy trong khóa cao học của lớp chúng tôi, đã tận tình chỉ dẫn, truyền đạt khi Tôi học tập tại trường đại học Ngoại Ngữ Tin Học thành phố Hồ Chí Minh. Tôi rất trân trọng ghi nhớ lòng biết ơn sâu sắc và gửi lời cảm ơn chân thành đến thầy PGS.TS Lê Hoài Bắc đã tận tình chỉ dẫn, và hướng dẫn rõ ràng các vấn đề liên quan trong quá trình thực hiện luận văn của tôi từ lúc bắt đầu đến khi hoàn thành. Trong quá trình học tập và làm luận văn, ngoài sự giúp đỡ của thầy cô, Tôi luôn nhận được sự quan tâm, động viên từ ba mẹ, gia đình, và bạn bè. Tôi xin chân thành cảm ơn tất cả người thân yêu đã luôn động viên và giúp đỡ. Lĩnh vực khai thác dữ liệu là hết sức rộng lớn, trong phạm vi của đề tài thực hiện khó tránh khỏi sai sót, rất mong nhận được sự cảm thông và ý kiến đóng góp quý báu của thầy cô, anh chị và bạn bè. Trần Phú Dư
MỤC LỤC LỜI NÓI ĐẦU ................................................................................................................. 1 1. Mở đầu: ........................................................................................................................ 1 2. Bố cục đề tài ................................................................................................................. 3 Chương 1: TỔNG QUAN ................................................................................................... 4 1. Khai thác dữ liệu: ........................................................................................................ 4 2. Ứng dụng của khai thác dữ liệu .................................................................................. 5 3. Khai thác dàn các tập phổ biến đóng .......................................................................... 7 4. Ý nghĩa khoa học và thực tiễn của đề tài .................................................................... 8 5. Phương pháp nghiên cứu và đối tượng nghiên cứu .................................................... 8 6. Khó khăn và Thách thức ............................................................................................. 9 7. Mục tiêu và phạm vi của luận văn .............................................................................. 9 8. Đóng góp của luận văn .............................................................................................. 10 Chương 2: CƠ SỞ LÝ THUYẾT ...................................................................................... 11 1. Khái quát bài toán ..................................................................................................... 11 2. Hướng tiếp cận khai thác tập phổ biến đóng ............................................................. 12 3. Hướng tiếp cận khai thác tập sinh (Minimal Generator) .......................................... 16 4. Hướng tiếp cận khai thác Dàn các tập phổ biến đóng ............................................... 16 5. Đề xuất cấu trúc dữ liệu ............................................................................................ 17 5.1 Superset bit-vector ............................................................................................. 17 5.2 Dynamic superset bit-vector .............................................................................. 18 5.2.1 Tìm FCS từ cấu trúc DSBV ........................................................................ 19 5.2.2 Tìm minimal FCS từ cấu trúc DSBV ......................................................... 20 5.2.3 Giao 2 DSBVs ............................................................................................ 21 5.2.4 Cập nhật 1 DSBV ....................................................................................... 22 Chương 3: ĐỀ XUẤT THUẬT TOÁN KHAI THÁC DÀN CÁC TẬP PHỔ BIẾN ĐÓNG VÀ CẢI TIẾN. ...................................................................................................... 24 1. Phát biểu bài toán khai thác Dàn các tập phổ biến đóng........................................... 24 2. Thuật Toán BVCL ..................................................................................................... 25
2.1 Lưu đồ tổng quát của thuật toán .......................................................................... 30 2.2 Các bước chính của thuật toán ............................................................................. 31 3. Đặc tả và phân tích thuật toán ................................................................................... 36 4. Cải tiến thuật toán gốc ............................................................................................... 43 4.1 Cơ sở lý thuyết ..................................................................................................... 43 4.1.1 Kết nối Galois: ............................................................................................... 43 4.1.2 Định nghĩa toán tử đóng: ................................................................................ 43 4.1.3 Các tính chất của IT-pair ................................................................................ 43 4.1.4 Minimal Generator (mG) ................................................................................ 44 4.1.5 Một số nhận xét về mG ................................................................................... 44 4.2 Thuật toán ............................................................................................................. 44 5. Kết quả thực nghiệm và so sánh................................................................................ 46 5.1 Bộ dữ liệu Chess. ................................................................................................. 47 5.2 Bộ dữ liệu Mushroom. ......................................................................................... 49 5.3 Bộ dữ liệu Pumsb. ................................................................................................ 50 5.4 Bộ dữ liệu Retail. ................................................................................................. 52 5.5 Bộ dữ liệu T10I4D100K ...................................................................................... 54 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN......................................................................... 57 1. Kết luận ................................................................................................................... 57 2. Hướng phát triển ...................................................................................................... 57 TÀI LIỆU THAM KHẢO ................................................................................................. 59
Danh mục các bảng Bảng 2.1: Cơ sở dữ liệu giao dịch book store. .................................................................. 13 Bảng 2.2: Cơ sở dữ liệu giao dịch của bảng 2.1 được mã hóa. ......................................... 13 Bảng 2.3: Cơ sở dữ liệu giao dịch theo chiều dọc dùng bit vector. .................................. 14 Bảng 2.4: Tìm cids của FCS của itemset có DSBV: {1, {12, 129}} ................................ 20 Bảng 2.5: Khai thác minimal FCS từ cấu trúc DSBV ....................................................... 21 Bảng 3.1: Bộ dữ liệu chess ................................................................................................ 47 Bảng 3.2: Kết quả thực nghiệm thu được với bộ dữ liệu Chess ........................................ 47 Bảng 3.3: Bộ dữ liệu Mushroom ....................................................................................... 49 Bảng 3.4: Kết quả thực nghiệm thu được với bộ dữ liệu Mushroom ................................ 49 Bảng 3.5: Bộ dữ liệu Pumsb .............................................................................................. 51 Bảng 3.6: Kết quả thực nghiệm thu được với bộ dữ liệu Pumsb ...................................... 51 Bảng 3.7: Bộ dữ liệu Retail ............................................................................................... 52 Bảng 3.8: Kết quả thực nghiệm thu được với bộ dữ liệu Retail ........................................ 53 Bảng 3.9: Bộ dữ liệu T10I4D100K ................................................................................... 54 Bảng 3.10: Kết quả thực nghiệm thu được với bộ dữ liệu T10I4D100K .......................... 54
Danh mục các hình vẽ, đồ thị Hình 2.1: Dynamic superset bit vector .............................................................................. 18 Hình 2.2: Giao 2 DSBVs ................................................................................................... 22 Hình 2.3: Hội 2 DSBVs ..................................................................................................... 23 Hình 3.1: Lưu đồ thuật toán............................................................................................... 31 Hình 3.2: Cây khai thác FCIs ............................................................................................ 33 Hình 3.3: Khai thác Dàn FCIs ........................................................................................... 36 Hình 3.4: biểu đồ so sánh thời gian thực thi của bộ dữ liệu Chess ................................... 48 Hình 3.5: biểu đồ so sánh bộ nhớ chiếm dụng của bộ dữ liệu Chess ................................ 48 Hình 3.6: Biểu đồ so sánh thời gian thực thi của bộ dữ liệu Mushroom ........................... 50 Hình 3.7: Biểu đồ so sánh bộ nhớ chiếm dụng của bộ dữ liệu Mushroom ....................... 50 Hình 3.8: Biểu đồ so sánh thời gian thực thi của bộ dữ liệu Pumsb ................................. 51 Hình 3.9: Biểu đồ so sánh bộ nhớ chiếm dụng của bộ dữ liệu Pumsb .............................. 52 Hình 3.10: Biểu đồ so sánh thời gian thực thi của bộ dữ liệu Retail ................................. 53 Hình 3.11: Biểu đồ so sánh bộ nhớ chiếm dụng của bộ dữ liệu Retail ............................. 54 Hình 3.11: Biểu đồ so sánh thời gian thực thi của bộ dữ liệu T10I4D100K ..................... 55 Hình 3.12: Biểu đồ so sánh bộ nhớ chiếm dụng của bộ dữ liệu T10I4D100K ................. 55
Danh mục từ viết tắt STT Từ viết tắt Từ viết đầy đủ Ý nghĩa, diễn giải Bit-Vector oriented frequent Closed itemset 1 BVCL Tên thuật toán Lattice 2 CID Closed itemset identifier ID của tập đóng 3 CSDL Cơ sở dữ liệu Tập các giao dịch chứa tập hạng mục 4 DBV Dynamic bit vector Vector bit động. Dynamic superset bit 5 DSBV Vector bit động lưu ID của tập bao nó vector 6 FCS Frequent close supeset Tập bao phổ biến đóng 7 FCI Frequent close itemeset Tập phổ biến đóng 8 MG Minimal generator Tập sinh Non- redundant 9 NARs các luật kết hợp không dư thừa association rules Non-zero least vị trí bit 1 gần nhất trong byte tính từ 10 nsLSB significant bit phải qua 11 nSL Non Subsuming list Danh sách tập không subsume Online Analysis 12 OLAP Phân tích dữ liệu trực tuyến. Processing Online Transaction 13 OLTP Phân tích dữ liệu giao tác trực tuyến. Processing 14 SL Subsuming list Danh sách tập subsume 15 TID Transaction identifiers Mã (định danh) giao dịch, giao tác.
LỜI NÓI ĐẦU 1. Mở đầu Ngày nay, khi khả năng lưu trữ của máy tính tăng cao, cùng với sự gia tăng khủng khiếp lượng dữ liệu trên mạng intenet. Ngày càng xuất hiện nhiều cơ sở dữ liệu với lượng dữ liệu lớn và phức tạp, lượng dữ liệu trong các cơ sở dữ liệu này quá lớn để có thể phân tích, trích xuất theo phương pháp thống kê truyền thống. Điều này đòi hỏi phải có phương pháp, kỹ thuật để khai thác, trích xuất thông tin trong các tập dữ liệu đồ sộ này. Data mining hay khai thác dữ liệu là quá trình khám phá các thông tin, các mối quan hệ có giá trị ẩn chứa bên trong lượng dữ liệu lớn. Quá trình khai thác dữ liệu kết hợp các công cụ từ thống kê và trí tuệ nhân tạo (như mạng nơ ron và học máy) với quản lý cơ sở dữ liệu để phân tích các tập dữ liệu lớn. Khai thác dữ liệu được sử dụng rộng rãi trong kinh doanh (bảo hiểm, ngân hàng, bán lẻ), nghiên cứu khoa học (thiên văn học, y học) và an ninh chính phủ (phát hiện bọn tội phạm và khủng bố). Khai thác dữ liệu được xem là phương pháp mà đơn vị Able Danger của Quân đội Mỹ đã dùng để xác định kẻ đứng đầu cuộc tấn công ngày 11 tháng 9, Mohamed Atta, và ba kẻ tấn công ngày 11 tháng 9 khác là các thành viên bị nghi ngờ thuộc lực lượng al Qaeda hoạt động ở Mỹ hơn một năm trước cuộc tấn công. Tìm những mẫu quan trọng và hữu ích trong 1 tập dữ liệu lớn và phân tích những quan hệ trong các mẫu này là 1 phần trọng yếu của data mining. Tất cả những mẫu này có thể được sử dụng để phát sinh tập luật kết hợp cần thiết. Tập luật kết hợp mô tả sự đồng xuất hiện và mối quan hệ giữa các mẫu. Những luật này có thể rất hữu ích cho nhiều tổ chức thương mại. Các luật kết hợp có thể đóng vai trò quan trọng trong mối liên quan đến việc mua hàng ở siêu thị. Phân tích các đặc điểm của hàng hóa giao dịch, chúng ta có thể dự đoán thói quen về ăn uống của khách hàng, về tình trạng tài chính và nhu cầu tiêu dùng của các sản phẩm. Nó cũng giúp y khoa nghiên cứu tương tác của một số thuốc với nhau. Vì thế, việc 1
phát triển các thuật toán để khai thác các mối quan hệ giữa các mẫu luôn là lĩnh vực nghiên cứu được quan tâm. Những mẫu mà thường xuyên xãy ra giao dịch trong database được gọi là các mẫu phổ biến. Tuy nhiên, những mẫu phổ biến thường rất lớn và chứa nhiều mẫu dư thừa trong tập dữ liệu, chẳng hạng như về sinh học, viễn thông, điều tra dân số. Những tập các mẫu phổ biến đóng là giải pháp để loại bỏ các mẫu dư thừa từ những tập mẫu phổ biến. Một tập phổ biến được gọi là phổ biến đóng nếu như không có tập cha (bao nó) có cùng độ phổ biến. Sự lặp lại giữa các quan hệ Tập Cha – Tập Con trong các tập đóng làm tăng thêm nhiều chi phí trong việc phát sinh các luật kết hợp không dư thừa (NARs). Tuy nhiên cũng thấy rằng, các luật kết hợp không dư thừa có thể được phát sinh hiệu quả hơn từ cấu trúc dàn của các tập đóng so với việc khai thác trực tiếp từ tập đóng [4]. Cấu trúc dàn sắp xếp tất cả các tập đóng theo quan hệ cha – con [18]. Dàn mô tả sự phụ thuộc giữa các tập đóng dẫn đến việc khai thác nhanh các luật kết hợp không dư thừa. Mục tiêu của luận văn này hướng tới cách giải quyết bài toán: Từ cơ sở dữ liệu có sẵn, làm sao để khai thác toàn bộ các tập phổ biến đóng, quan hệ cha – con giữa các tập này, cải tiến giải thuật khai thác dàn các tập phổ biến đóng để việc khai thác tập luật kết hợp sau này được dễ dàng và hiệu quả hơn. Dựa trên một số công trình nghiên cứu về lĩnh vực khai thác tập phổ biến đóng trong những năm gần đây, đặc biệt là dựa trên công trình nghiên cứu năm 2017: “An efficient dynamic superset bit-vector approach for mining frequent closed itemsets and their lattice structure”[1] của Tahrima Hashem và cộng sự. Từ đó luận văn sẽ tập trung nghiên cứu: • Khai thác tập phổ biến đóng: tìm hiểu về tập phổ biến, tập phổ biến đóng, và các ứng dụng của khai thác tập phổ biến đóng và dàn, phát biểu 2
bài toán và các phương pháp khai thác dàn tập phổ biến đóng nỗi bật đã được nghiên cứu trước đó. • Khai thác dàn tập phổ biến đóng: trình bày về dàn các tập phổ biến đóng, cấu trúc DSBV. • Cải tiến thuật toán: đề xuất phương pháp khai thác song song tập sinh và dàn của tập phổ biến đóng. • Kết quả thự nghiệm trên thuật toán BVCL cải tiến, so sánh với thuật toán gốc và các phương pháp trước đây. 2. Bố cục đề tài Luận văn trình bày trong 03 chương: - Chương 1: Giới thiệu tổng quan về khai thác dữ liệu, ý nghĩa của khai thác dữ liệu, ứng dụng của khai thác dữ liệu, khai thác tập phổ biến đóng, nêu rõ phạm vi, mục tiêu, phương pháp nghiên cứu, ý nghĩa khoa học và thực tiễn, các kết quả dự kiến với đóng góp của luận văn là đề xuất một cải thiện khai thác dàn các tập phổ biến đóng của thuật toán BVCL. - Chương 2: Trình bày cơ sở lý thuyết của các khái niệm, kỹ thuật khai thác dàn các tập phổ biến đóng, tập sinh và các giai đoạn tổ chức bài toán. Mô tả và phân tích ưu điểm khuyết điểm của các thuật toán đã có trước đó. Từ đó, hình thành hướng đi mới cho thuật toán cải tiến khai thác dàn tập phổ biến đóng. - Chương 3: Đề xuất thuật toán cải tiến khai thác dàn các tập phổ biến đóng, chỉ rõ các bước cải tiến mới so với thuật toán BVCL, so sánh kết quả thực nghiệm của thuật toán mới với thuật toán gốc cũng như với các thuật toán đã có. - Tiếp theo, là phần Kết luận và Hướng phát triển, nêu tóm gọn về kết quả đạt được cũng như các hướng nghiên cứu, ứng dụng có thể mở rộng và phát triển của luận văn trong tương lai. Cuối cùng, phần Tài liệu tham khảo, liệt kê danh sách các tài liệu tham khảo sử dụng trong luận văn. 3
Chương 1: TỔNG QUAN 1. Khai thác dữ liệu Khối lượng dữ liệu khổng lồ được thu thập trên toàn thế giới, tăng lên hàng terabyte (hoặc petabyte) dữ liệu mỗi ngày từ nhiều nguồn dữ liệu: dữ liệu về kinh tế, khoa học kỹ thuật, y tế, mạng internet, mạng xã hội, các hệ thống truyền dữ liệu tự động và từ các khía cạnh khác trong cuộc sống hàng ngày của con người. Từ những năm đầu thập kỷ 60 đến cuối những năm 1980, công nghệ sưu tập, lưu trữ và xử lý, phân tích dữ liệu đã tiến bộ vượt bậc trước sự phát triển mạnh mẽ của xu hướng tin học hóa trên toàn thế giới. Ban đầu sự thu thập và phát sinh cơ sở dữ liệu, chỉ là truy xuất file thô sơ (đầu những năm 1960). Sau những năm 1970 đến đầu 1980s, phát triển sang hệ thống quản lý CSDL, trong đó đã có công cụ phân tích dữ liệu giao dịch trực tuyến - OLTP. Từ giữa đến cuối những năm 1980, phát triển hệ thống cơ sở dữ liệu nâng cao và hệ thống phân tích CSDL nâng cao, triển khai kèm theo đó là các công cụ nổi bật dành cho phân tích dữ liệu nâng cao. Trong đó có sự ra đời của kiến trúc kho dữ liệu mới đi kèm kỹ thuật OLAP, có khả năng khai thác dữ liệu đa chiều, phân tích dữ liệu sâu, xem thông tin với nhiều góc độ khác nhau. Tuy nhiên khối dữ liệu khổng lồ được thu thập và lưu trữ trong nhiều kho chứa dữ liệu lớn không ngừng tăng nhanh. Việc hiểu hết các thông tin, cũng như rút trích ra các kiến thức ẩn đã nhúng trong khối dữ liệu khổng lồ cực lớn này mà không có công cụ mạnh mẽ hỗ trợ là vượt xa khả năng của con người. Điều này đòi hỏi cần có một công cụ mạnh mẽ, linh hoạt hơn để đáp ứng nhu cầu khám phá các mẫu dữ liệu đặc biệt, quan trọng, nhằm rút trích ra các thông tin, kiến thức có giá trị từ khối dữ liệu khổng lồ. Cuối những năm 1980, khai thác dữ liệu ra đời, đánh dấu sự tiến triển mới của công nghệ thông tin. Các chức năng của khai thác dữ liệu bao gồm: mô tả đặc tính và phân biệt dữ liệu, khai thác các mẫu (chuỗi) phổ biến, sự kết hợp và tương quan, phân lớp và hồi quy, phân tích gom cụm, và nhận dạng ngoại lệ. 4
Trong tương lai, nếu phát sinh thêm nhiều kiểu dữ liệu mới, ứng dụng mới và nhu cầu phân tích dữ liệu mới thì việc xuất hiện thêm các thao tác khai thác dữ liệu mới là điều có thể dự đoán được. 2. Ứng dụng của khai thác dữ liệu Khai phá dữ liệu đã và đang được ứng dụng rộng rãi trong rất nhiều lĩnh vực và hiện nay đã có rất nhiều công cụ thương mại và phi thương mại triển khai các nhiệm vụ của khai phá dữ liệu. Sau đây là một số lĩnh vực mà khai phá dữ liệu đang được ứng dụng rộng rãi: • Phân tích dữ liệu tài chính. • Công nghiệp bán lẻ. • Công nghiệp viễn thông. • Phân tích dữ liệu sinh học. • Phát hiện xâm nhập. • Một số ứng dụng trong khoa học. Phân tích dữ liệu tài chính Dữ liệu tài chính trong ngân hàng và trong ngành tài chính thường đáng tin cậy và có chất lượng cao, tạo điều kiện cho khai phá dữ liệu. Dưới đây là một số ứng dụng điển hình trong khai phá dữ liệu tài chính: • Dự đoán khả năng vay và thanh toán của khách hàng, phân tích chính sách tín dụng đối với khách hàng. • Phân tích hành vi khách hàng (vay, gửi tiền). • Phân loại và phân nhóm khách hàng mục tiêu cho tiếp thị tài chính. • Phát hiện các hoạt động rửa tiền và tội phạm tài chính khác. Công nghiệp bán lẻ Khai phá dữ liệu có vai trò rất quan trọng trong ngành công nghiệp bán lẻ, do dữ liệu thu thập từ lĩnh vực này rất lớn từ doanh số bán hàng, lịch sử mua hàng của khách hàng, vận chuyển hàng hóa, tiêu thụ và dịch vụ. Điều tự nhiên là khối lượng dữ 5
liệu từ ngành công nghiệp này sẽ tiếp tục tăng lên nhanh chóng và dễ dàng thu thập bởi tính sẵn có trên môi trường Web. Ứng dụng khai phá dữ liệu trong ngành công nghiệp bán lẻ nhằm xây dựng mô hình giúp xác định xu hướng mua hàng của khách hàng, giúp doanh nghiệp cải thiện chất lượng sản phẩm dịch vụ nhằm nâng cao sự hài lòng của khách hàng và giữ chân khách hàng tốt. Dưới đây là một số ứng dụng của khai phá dữ liệu trong ngành công nghiệp bán lẻ: • Khai phá dữ liệu trên kho dữ liệu khách hàng. • Phân tích đa chiều trên kho dữ liệu khách hàng về doanh số bán hàng, khách hàng, sản phẩm, thời gian và khu vực. • Phân tích hiệu quả của các chiến dịch bán hàng, Marketing. • Quản trị mối quan hệ khách hàng. • Giới thiệu và tư vấn sản phẩm phù hợp cho khách hàng. Công nghiệp viễn thông Công nghiệp viễn thông là một trong những ngành công nghiệp mới nổi, cung cấp nhiều dịch vụ như trên điện thoại di động, internet, truyền hình ảnh... Do sự phát triển mạnh của công nghệ máy tính và mạng máy tính, viễn thông đang phát triển với tốc độ rất nhanh. Đây là lý do tại sao khai phá dữ liệu trở nên rất quan trọng trong lĩnh vực này. Khai phá dữ liệu trong ngành công nghiệp viễn thông giúp xác định các mô hình viễn thông, phát hiện các hoạt động gian lận trong viễn thông, sử dụng tốt hơn nguồn tài nguyên và cải thiện chất lượng dịch vụ viễn thông. Dưới đây là một số ứng dụng của khai phá dữ liệu trong ngành công nghiệp này: • Phân tích dữ liệu đa chiều viễn thông. • Xây dựng các mô hình phát hiện gian lận. • Phát hiện bất thường trong giao dịch viễn thông. • Phân tích hành vi sử dụng dịch vụ viễn thông của khách hàng. • Sử dụng các công cụ trực quan trong phân tích dữ liệu viễn thông. 6
Phân tích dữ liệu sinh học Khai phá dữ liệu sinh học là một phần rất quan trọng của lĩnh vực Tin - Sinh Học. Sau đây là một số ứng dụng của khai phá dữ liệu ứng dụng trong sinh học: • Lập chỉ mục, tìm kiếm tương tự, bất thường trong cơ sở dữ liệu Gen. • Xây dựng mô hình khai phá các mạng di truyền và cấu trúc của Gen, protein. • Xây dựng các công cụ trực quan trong phân tích dữ liệu di truyền. Phát hiện xâm nhập bất hợp pháp Xâm nhập bất hợp pháp là những hành động đe dọa tính toàn vẹn, bảo mật và tính sẵn sàng của tài nguyên mạng. Trong thế giới của kết nối, bảo mật đã trở thành vấn đề lớn đối với tồn tại của hệ thống. Với sự phát triển của internet và sự sẵn có của các công cụ, thủ thuật trợ giúp cho xâm nhập và tấn công mạng, yêu cầu kiểm soát truy cập bất hợp pháp là yếu tố rất quan trọng đảm bảo cho sự ổn định của hệ thống. Dưới đây là một số ứng dụng của khai phá dữ liệu có thể được áp dụng để phát hiện xâm nhập: - Phát triển các thuật toán khai phá dữ liệu để phát hiện xâm nhập. - Phân tích kết hợp, tương quan và khác biệt để phát hiện xâm nhập. - Phân tích dòng dữ liệu để phát hiện bất thường. 3. Khai thác dàn các tập phổ biến đóng Tìm luật kết hợp từ hàng triệu giao dịch trong nhiều CSDL lớn, hiện tại trở nên khó khăn trong lĩnh vực khai thác dữ liệu. Tập phổ biến và tập phổ biến đóng là chìa khóa quan trọng của việc khai thác các luật kết hợp. Các luật kết hợp có thể được khai thác hiệu quả từ Dàn các tập phổ biến đóng. Không thừa, chính xác, thời gian và chiếm dụng bộ nhớ là các nhân tố cần được xem xét trong khi phát triển thuật toán để tìm các luật kết hợp hữu ích. Xây dựng dàn tập phổ biến đóng là xây dựng quan hệ cha con (trực tiếp) giữa các tập phổ biến đóng với nhau. Do vậy sẽ tiết kiệm được thời gian khi duyệt dàn để sinh luật. 7
4. Ý nghĩa khoa học và thực tiễn của đề tài - Thuật toán BVCL đổi mới hơn so với thuật toán CHARML cũng như các thuật toán duyệt tuần tự tập hạng mục ở những điểm chính sau: o Cấu trúc DSBV lưu thông tin tập cha ở dạng bit nên việc truyền thông tin cho các tập trong dàn khi gọi đệ qui là nhanh chóng. o Cách tổ chức 2 danh sách subsume list và non - subsume list làm cho thuật toán bỏ qua khá nhiều bước khi đệ qui với các tập trong subsume list. - Thuận toán mới cải thiện hiệu suất khai thác dàn các tập phổ biến đóng này góp phần giải quyết vấn đề trong việc khai thác luật kết hợp với nhiều ứng dụng rộng, bao gồm những phân tích về hành vi mua sắm của khách hàng, chuỗi truy xuất web, những thực nghiệm có tính khoa học, điều trị bệnh, ngăn chặn tai họa thiên nhiên và sự hình thành protein… 5. Phương pháp nghiên cứu và đối tượng nghiên cứu • Phương pháp nghiên cứu: - Phương pháp nghiên cứu tài liệu: dựa vào các tài liệu đã công bố của các nhà nghiên cứu về các thuật toán khai thác tập phổ biến, tập phổ biến đóng, và khai thác Dàn: Apriori-Gen, FP-tree, Charm, CharmL, MG-Charm, DCI- Closed, LCM, DBV-Miner, GENCLOSE, NAFCP. Phân tích cách sử dụng cấu trúc dữ liệu DBV, DSBV cách tổ chức CSDL (ngang hay dọc), cách phát sinh mẫu ứng viên mới, các kỹ thuật khai thác Dàn… và xu hướng phát triển của các thuật toán. - Phương pháp thực nghiệm: Tiến hành hiện thực và thực nghiệm các phương pháp được đề xuất trong luận văn để xác định tính đúng đắn, khả thi và phát triển so với các phương pháp đã công bố của các tác giả trong và ngoài nước có liên quan đến luận văn. - Phương pháp thống kê, phân tích dữ liệu: Thống kê, tổng hợp các số liệu trong quá trình thực nghiệm để phân tích, đánh giá từ đó nhận thức, phát hiện, và chọn lọc những ưu điểm để phát huy, tìm cách khắc phục những hạn chế, đồng thời kết hợp những thông tin liên quan đã thu thập được lại thành 8
một nội dung logic đầy đủ để đề xuất thuật toán mới có thời gian khai thác đồng thời Dàn các tập phổ biến đóng và tập sinh của chúng nhanh hơn và tiết kiệm bộ nhớ hơn (có so sánh kết quả thực nghiệm). • Đối tượng nghiên cứu: Thuật toán BVCL khai thác dàn các tập phổ biến đóng, cấu trúc vectơ bit động - DBV, cấu trúc superset vectơ bit động DSBV dùng để lưu và truyền thông tin của các tập superset, các kỹ thuật ánh xạ, chỉ mục để tăng tốc độ tìm kiếm cho thuật toán. 6. Khó khăn và Thách thức Cho trước CSDL D và ngưỡng minSup do người dùng đặt ra, phải tìm đầy đủ các tập phổ biến đóng là một thách thức không nhỏ về thời gian do độ phức tạp trong việc khai thác là hàm mũ. Độ dài của vector bit tăng lên theo số transaction trong CSDL. Làm tốn kém nhiều bộ nhớ. Cấu trúc bit vector động tiết kiệm khá nhiều bộ nhớ đối với CSDL thưa, tuy nhiên, đối với CSDL đặc, việc tiết kiệm không đáng kể. Trên các bộ dữ liệu dùng trong luận văn này, bộ nhớ tiết kiệm hơn 50% so với cấu trúc bit vector tỉnh. 7. Mục tiêu và phạm vi của luận văn Mục đích cuối cùng của quá trình khai thác tập phổ biến là khai thác tập luật kết hợp và ứng dụng các kết quả vào trong thực tế. Theo cách khai thác luật kết hợp truyền thống, việc tìm tất cả các luật kết hợp từ CSDL thõa minSup và minConf gặp nhiều bất lợi khi số tập phổ biến lớn. Do đó cần có một phương pháp thích hợp để khai thác với số lượng luật ít hơn nhưng vẫn đảm bảo tích hợp đầy đủ tất cả các luật của phương pháp khai thác truyền thống. Một trong những cách tiếp cận đó là khai thác luật thiết yếu nhất, chỉ lưu lại các luật có vế trái tối tiểu và vế phải tối đại (theo quan hệ cha – con). Mục tiêu của luận văn là tập trung vào nghiên cứu, phân tích ưu điểm và hạn chế các thuật toán khai thác tập phổ biến đóng, tập phổ biến đóng trên Dàn. Với mong muốn làm giảm thời gian khai thác luật, sử dụng quan hệ cha – con trên Dàn để giảm chi phí xét quan hệ cha – con và vì vậy làm giảm được thời gian khai thác luật. 9