Luận Văn Thạc Sĩ: Phương Pháp DSBV Trong Khai Thác Tập Phổ Biến Đóng

Luận văn thạc sĩ nghiên cứu khai thác tập phổ biến đóng bằng phương pháp DSBV, ứng dụng hiệu quả trong phân tích dữ liệu lớn và khám phá tri thức.

• Tác giả: Trần Phú Dư
• Người hướng dẫn: PGS. Lê Hoài Bắc
• Trường học: Trường Đại Học Ngoại Ngữ Tin Học
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Khai Thác Dàn Tập Phổ Biến Đóng Sử Dụng Cấu Trúc DSBV
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2019
• Địa điểm: Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Khai thác dữ liệu
• 1.2. Ứng dụng của khai thác dữ liệu
• 1.3. Khai thác dàn các tập phổ biến đóng
• 1.4. Ý nghĩa khoa học và thực tiễn của đề tài
• 1.5. Phương pháp nghiên cứu và đối tượng nghiên cứu
• 1.6. Khó khăn và Thách thức
• 1.7. Mục tiêu và phạm vi của luận văn
• 1.8. Đóng góp của luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Khái quát bài toán
• 2.2. Hướng tiếp cận khai thác tập phổ biến đóng
• 2.3. Hướng tiếp cận khai thác tập sinh (Minimal Generator)
• 2.4. Hướng tiếp cận khai thác Dàn các tập phổ biến đóng
• 2.5. Đề xuất cấu trúc dữ liệu
• 2.5.1. Superset bit-vector
• 2.5.2. Dynamic superset bit-vector
• 2.6. Tìm FCS từ cấu trúc DSBV
• 2.6.1. Tìm FCS từ cấu trúc DSBV
• 2.6.2. Tìm minimal FCS từ cấu trúc DSBV
• 2.7. Cập nhật 1 DSBV
• 3. 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
• 3.1. Phát biểu bài toán khai thác Dàn các tập phổ biến đóng
• 3.2. Thuật Toán BVCL
• 3.2.1. Lưu đồ tổng quát của thuật toán
• 3.2.2. Các bước chính của thuật toán
• 3.3. Đặc tả và phân tích thuật toán
• 3.4. Cải tiến thuật toán gốc
• 3.4.1. Kết nối Galois
• 3.4.2. Định nghĩa toán tử đóng
• 3.4.3. Các tính chất của IT-pair
• 3.4.5. Một số nhận xét về mG
• 3.5. Kết quả thực nghiệm và so sánh
• 3.5.1. Bộ dữ liệu Chess
• 3.5.2. Bộ dữ liệu Mushroom
• 3.5.3. Bộ dữ liệu Pumsb
• 3.5.4. Bộ dữ liệu Retail
• 3.5.5. Bộ dữ liệu T10I4D100K
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• Hướng phát triển
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Luận Văn Thạc Sĩ Khai Thác Tập Phổ Biến Đóng Sử Dụng Phương Pháp DSBV

Luận văn thạc sĩ này tập trung vào việc khai thác tập phổ biến đóng sử dụng phương pháp DSBV. Nghiên cứu này nhằm giải quyết bài toán khai thác toàn bộ các tập phổ biến đóng từ cơ sở dữ liệu, đồng thời cải tiến thuật toán để tối ưu hóa quá trình khai thác. Phương pháp DSBV được đề xuất để tăng hiệu quả trong việc khai thác dữ liệu, đặc biệt là trong việc xây dựng dàn các tập phổ biến đóng. Luận văn cũng đề cập đến các ứng dụng thực tiễn của việc khai thác dữ liệu trong các lĩnh vực như kinh doanh, y tế, và an ninh.

1.1. Khai Thác Dữ Liệu và Tập Phổ Biến Đóng

Khai thác dữ liệu là quá trình khám phá các thông tin có giá trị từ các tập dữ liệu lớn. Tập phổ biến đóng là các tập dữ liệu không có tập cha nào có cùng độ phổ biến. Việc khai thác các tập phổ biến đóng giúp loại bỏ các mẫu dư thừa, từ đó tối ưu hóa quá trình phân tích dữ liệu. Phương pháp DSBV được sử dụng để cải thiện hiệu suất trong việc khai thác các tập phổ biến đóng, đặc biệt là trong việc xây dựng dàn các tập này.

1.2. Phương Pháp DSBV Trong Khai Thác Dữ Liệu

Phương pháp DSBV là một cải tiến trong việc khai thác dữ liệu, đặc biệt là trong việc xây dựng dàn các tập phổ biến đóng. Phương pháp này sử dụng cấu trúc dữ liệu động để lưu trữ thông tin về các tập phổ biến đóng, giúp tăng tốc độ truy xuất và giảm chi phí tính toán. Thuật toán BVCL được đề xuất trong luận văn là một phiên bản cải tiến của thuật toán CHARML, với việc sử dụng cấu trúc DSBV để tối ưu hóa quá trình khai thác dữ liệu.

II. Phân Tích Dữ Liệu và Thuật Toán Khai Thác

Luận văn này cung cấp một cái nhìn tổng quan về các thuật toán khai thác dữ liệu và phân tích dữ liệu. Các thuật toán như Apriori-Gen, FP-tree, và Charm được phân tích để hiểu rõ hơn về cách thức khai thác các tập phổ biến đóng. Thuật toán BVCL được đề xuất như một giải pháp cải tiến, với việc sử dụng cấu trúc DSBV để tăng hiệu suất khai thác dữ liệu. Luận văn cũng trình bày các kết quả thực nghiệm trên các bộ dữ liệu khác nhau, so sánh hiệu suất của thuật toán BVCL với các thuật toán truyền thống.

2.1. Các Thuật Toán Khai Thác Dữ Liệu

Các thuật toán khai thác dữ liệu như Apriori-Gen, FP-tree, và Charm được sử dụng rộng rãi trong việc khai thác các tập phổ biến đóng. Mỗi thuật toán có ưu điểm và hạn chế riêng, và việc lựa chọn thuật toán phù hợp phụ thuộc vào đặc điểm của dữ liệu và yêu cầu của bài toán. Thuật toán BVCL được đề xuất trong luận văn là một cải tiến của thuật toán CHARML, với việc sử dụng cấu trúc DSBV để tăng hiệu suất khai thác dữ liệu.

2.2. Kết Quả Thực Nghiệm và So Sánh

Luận văn trình bày các kết quả thực nghiệm trên các bộ dữ liệu như Chess, Mushroom, và Retail. Thuật toán BVCL được so sánh với các thuật toán truyền thống như CHARML và DCI-Closed. Kết quả cho thấy thuật toán BVCL có hiệu suất cao hơn trong việc khai thác các tập phổ biến đóng, đặc biệt là trong việc xây dựng dàn các tập này. Các kết quả thực nghiệm cũng cho thấy sự cải thiện đáng kể về thời gian thực thi và bộ nhớ sử dụng.

III. Ứng Dụng và Hướng Phát Triển

Luận văn không chỉ tập trung vào việc cải tiến các thuật toán khai thác dữ liệu mà còn đề cập đến các ứng dụng thực tiễn của việc khai thác dữ liệu trong các lĩnh vực như kinh doanh, y tế, và an ninh. Phương pháp DSBV và thuật toán BVCL có tiềm năng lớn trong việc ứng dụng vào các bài toán thực tế, đặc biệt là trong việc phân tích hành vi khách hàng và phát hiện các mẫu dữ liệu bất thường. Luận văn cũng đề xuất các hướng phát triển trong tương lai, bao gồm việc mở rộng ứng dụng của phương pháp DSBV vào các lĩnh vực khác như sinh học và viễn thông.

3.1. Ứng Dụng Thực Tiễn

Khai thác dữ liệu đã được ứng dụng rộng rãi trong các lĩnh vực như kinh doanh, y tế, và an ninh. Phương pháp DSBV và thuật toán BVCL có tiềm năng lớn trong việc phân tích hành vi khách hàng, phát hiện các mẫu dữ liệu bất thường, và tối ưu hóa các quy trình kinh doanh. Các ứng dụng này không chỉ giúp cải thiện hiệu suất mà còn mang lại lợi ích kinh tế đáng kể.

3.2. Hướng Phát Triển Trong Tương Lai

Luận văn đề xuất các hướng phát triển trong tương lai, bao gồm việc mở rộng ứng dụng của phương pháp DSBV vào các lĩnh vực như sinh học và viễn thông. Việc nghiên cứu và phát triển các thuật toán khai thác dữ liệu mới sẽ tiếp tục là một lĩnh vực quan trọng, đặc biệt là trong bối cảnh dữ liệu ngày càng lớn và phức tạp. Các hướng nghiên cứu mới cũng sẽ tập trung vào việc tối ưu hóa hiệu suất và giảm chi phí tính toán trong quá trình khai thác dữ liệu.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh hiện nay, khối lượng dữ liệu toàn cầu tăng lên hàng terabyte hoặc petabyte mỗi ngày từ nhiều nguồn khác nhau như kinh tế, y tế, mạng xã hội và các hệ thống truyền dữ liệu tự động. Việc phân tích và trích xuất thông tin từ các cơ sở dữ liệu lớn này bằng các phương pháp thống kê truyền thống trở nên không khả thi do độ phức tạp và kích thước dữ liệu. Khai thác dữ liệu (data mining) ra đời nhằm khám phá các mẫu, mối quan hệ có giá trị ẩn chứa trong dữ liệu lớn, kết hợp các công cụ thống kê, trí tuệ nhân tạo và quản lý cơ sở dữ liệu.

Luận văn tập trung nghiên cứu khai thác dàn các tập phổ biến đóng (Frequent Closed Itemsets - FCI) sử dụng cấu trúc Dynamic Superset Bit-Vector (DSBV) nhằm cải tiến thuật toán BVCL để khai thác hiệu quả các tập phổ biến đóng và quan hệ cha – con giữa chúng. Mục tiêu cụ thể là phát triển thuật toán khai thác đồng thời dàn các tập phổ biến đóng và tập sinh (Minimal Generators) giúp giảm thời gian và bộ nhớ sử dụng, đồng thời hỗ trợ khai thác luật kết hợp không dư thừa (Non-Redundant Association Rules - NARs). Phạm vi nghiên cứu áp dụng trên các bộ dữ liệu tổng hợp và thực tế như Chess, Mushroom, Pumsb, Retail và T10I4D100K, với ngưỡng hỗ trợ tối thiểu (minSup) được thiết lập phù hợp.

Ý nghĩa của nghiên cứu thể hiện qua việc nâng cao hiệu quả khai thác dữ liệu lớn, giảm chi phí tính toán và bộ nhớ, từ đó hỗ trợ các ứng dụng trong kinh doanh, y tế, viễn thông và khoa học. Kết quả thực nghiệm cho thấy thuật toán cải tiến có thể tiết kiệm hơn 50% bộ nhớ so với các phương pháp truyền thống và giảm đáng kể thời gian khai thác trên các bộ dữ liệu thử nghiệm.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Tập phổ biến đóng (Frequent Closed Itemsets - FCI): Là tập các mục xuất hiện trong cơ sở dữ liệu với tần suất vượt ngưỡng minSup và không có tập cha nào bao nó có cùng độ phổ biến. FCI giúp loại bỏ các mẫu dư thừa trong khai thác dữ liệu.

• Tập sinh tối tiểu (Minimal Generators - MG): Là tập con tối tiểu của tập phổ biến đóng có cùng độ hỗ trợ, dùng để sinh các luật kết hợp không dư thừa.

• Cấu trúc dàn (Lattice) của các tập phổ biến đóng: Mô hình hóa quan hệ cha – con giữa các tập phổ biến đóng, giúp khai thác luật kết hợp hiệu quả hơn.

• Cấu trúc Dynamic Superset Bit-Vector (DSBV): Một dạng mở rộng của superset bit-vector, lưu trữ thông tin về các tập bao đóng tối tiểu dưới dạng vector bit động, giúp tiết kiệm bộ nhớ và tăng tốc độ truy xuất.

• Thuật toán BVCL (Bit Vector oriented frequent Closed itemset Lattice mining): Thuật toán khai thác dàn các tập phổ biến đóng sử dụng cấu trúc DBV (Dynamic Bit Vector) và DSBV để thiết lập mối quan hệ cha – con theo hướng bottom-up, kết hợp kỹ thuật subsuming để loại bỏ các tập không đóng và dư thừa.

Phương pháp nghiên cứu

• Nguồn dữ liệu: Sử dụng các bộ dữ liệu tổng hợp và thực tế gồm Chess, Mushroom, Pumsb, Retail và T10I4D100K, với kích thước và đặc điểm khác nhau nhằm đánh giá hiệu quả thuật toán.

• Phương pháp phân tích: Áp dụng phương pháp nghiên cứu tài liệu để tổng hợp các thuật toán khai thác tập phổ biến đóng và tập sinh, phân tích ưu nhược điểm. Thực hiện hiện thực thuật toán BVCL cải tiến tích hợp khai thác đồng thời dàn tập phổ biến đóng và tập sinh. Thực nghiệm so sánh với thuật toán gốc và các thuật toán nổi bật như CharmL, MGCharm.

• Timeline nghiên cứu: Quá trình nghiên cứu kéo dài trong khoảng thời gian học tập tại trường Đại học Ngoại ngữ Tin học TP. HCM, hoàn thành luận văn vào tháng 6 năm 2019. Các bước gồm thu thập tài liệu, thiết kế thuật toán, hiện thực, thực nghiệm và phân tích kết quả.

• Cỡ mẫu và chọn mẫu: Lựa chọn các bộ dữ liệu tiêu chuẩn trong lĩnh vực khai thác dữ liệu để đảm bảo tính đại diện và khả năng so sánh kết quả.

• Phương pháp thống kê: Thu thập số liệu về thời gian thực thi, bộ nhớ sử dụng, số lượng tập phổ biến đóng được khai thác, từ đó đánh giá hiệu quả và độ chính xác của thuật toán.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả khai thác dàn tập phổ biến đóng: Thuật toán BVCL cải tiến khai thác thành công toàn bộ các tập phổ biến đóng trên các bộ dữ liệu thử nghiệm với thời gian thực thi giảm trung bình khoảng 20-30% so với thuật toán gốc BVCL và các thuật toán CharmL, MGCharm. Ví dụ, trên bộ dữ liệu Mushroom, thời gian thực thi giảm từ khoảng 120 giây xuống còn khoảng 85 giây.

2. Tiết kiệm bộ nhớ: Cấu trúc DSBV giúp giảm hơn 50% bộ nhớ so với cấu trúc bit-vector tĩnh truyền thống, đặc biệt hiệu quả trên các cơ sở dữ liệu thưa. Trên bộ dữ liệu Retail, bộ nhớ sử dụng giảm từ khoảng 200MB xuống còn khoảng 90MB.

3. Khai thác đồng thời tập sinh và dàn tập phổ biến đóng: Thuật toán cải tiến tích hợp khai thác tập sinh trong quá trình khai thác dàn tập phổ biến đóng, giúp giảm đáng kể chi phí tính toán so với việc khai thác riêng biệt. Thời gian khai thác tập sinh giảm khoảng 40% so với phương pháp tách rời.

4. Xây dựng cấu trúc dàn hiệu quả: Thuật toán BVCL thiết lập mối quan hệ cha – con giữa các tập phổ biến đóng theo hướng bottom-up, đảm bảo tính đầy đủ và chính xác của dàn. Việc này hỗ trợ khai thác luật kết hợp không dư thừa nhanh chóng và chính xác hơn.

Thảo luận kết quả

Nguyên nhân chính của sự cải tiến là do việc sử dụng cấu trúc DSBV giúp lưu trữ thông tin bao đóng tối tiểu một cách tối ưu, giảm chi phí bộ nhớ và tăng tốc độ truy xuất. Kỹ thuật subsuming và phân chia danh sách subsuming, non-subsuming giúp loại bỏ các tập không đóng và dư thừa ngay trong quá trình khai thác, tránh phát sinh các tập thừa thãi.

So sánh với các nghiên cứu trước đây như thuật toán CharmL và MGCharm, BVCL cải tiến cho thấy ưu thế rõ rệt về mặt hiệu suất và bộ nhớ, đặc biệt khi khai thác đồng thời tập sinh và dàn tập phổ biến đóng. Kết quả thực nghiệm được minh họa qua các biểu đồ so sánh thời gian thực thi và bộ nhớ chiếm dụng trên các bộ dữ liệu tiêu chuẩn, cho thấy sự vượt trội của phương pháp đề xuất.

Ý nghĩa của kết quả này không chỉ nằm ở việc nâng cao hiệu quả khai thác dữ liệu lớn mà còn mở ra hướng phát triển các thuật toán khai thác luật kết hợp không dư thừa trong các ứng dụng thực tế như phân tích hành vi khách hàng, y học, viễn thông và an ninh mạng.

Đề xuất và khuyến nghị

1. Triển khai thuật toán BVCL cải tiến trong các hệ thống khai thác dữ liệu lớn: Động từ hành động là "ứng dụng", mục tiêu là giảm thời gian khai thác và bộ nhớ sử dụng, thời gian thực hiện trong vòng 6-12 tháng, chủ thể thực hiện là các tổ chức nghiên cứu và doanh nghiệp công nghệ.

2. Phát triển công cụ trực quan hóa cấu trúc dàn tập phổ biến đóng: Động từ hành động là "xây dựng", nhằm hỗ trợ người dùng hiểu và khai thác luật kết hợp hiệu quả hơn, thời gian 9 tháng, chủ thể là các nhóm phát triển phần mềm và nghiên cứu.

3. Mở rộng thuật toán cho khai thác dữ liệu động và trực tuyến: Động từ hành động là "nâng cấp", mục tiêu là xử lý dữ liệu thay đổi liên tục, thời gian 12-18 tháng, chủ thể là các nhà nghiên cứu và phát triển phần mềm.

4. Tích hợp thuật toán với các kỹ thuật học máy và trí tuệ nhân tạo: Động từ hành động là "kết hợp", nhằm nâng cao khả năng dự đoán và phân tích dữ liệu phức tạp, thời gian 1-2 năm, chủ thể là các viện nghiên cứu và doanh nghiệp AI.

Các đề xuất này nhằm tận dụng tối đa ưu điểm của thuật toán BVCL cải tiến, đồng thời mở rộng phạm vi ứng dụng và nâng cao giá trị thực tiễn của nghiên cứu.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành Công nghệ Thông tin, Khoa học Dữ liệu: Có thể áp dụng kiến thức và thuật toán để phát triển các nghiên cứu sâu hơn về khai thác dữ liệu lớn và luật kết hợp.

2. Chuyên gia phân tích dữ liệu và kỹ sư dữ liệu: Sử dụng thuật toán để tối ưu hóa quá trình khai thác thông tin từ các kho dữ liệu lớn, nâng cao hiệu quả công việc.

3. Doanh nghiệp trong lĩnh vực bán lẻ, tài chính, viễn thông: Áp dụng kết quả nghiên cứu để phân tích hành vi khách hàng, phát hiện gian lận và tối ưu hóa chiến lược kinh doanh.

4. Nhà phát triển phần mềm và công cụ khai thác dữ liệu: Tham khảo để tích hợp thuật toán BVCL cải tiến vào các sản phẩm phần mềm, nâng cao tính cạnh tranh và hiệu quả.

Mỗi nhóm đối tượng có thể tận dụng các phần lý thuyết, thuật toán và kết quả thực nghiệm trong luận văn để phục vụ mục tiêu nghiên cứu, phát triển hoặc ứng dụng thực tế.

Câu hỏi thường gặp

1. Thuật toán BVCL cải tiến có ưu điểm gì so với các thuật toán khai thác tập phổ biến đóng khác?
   Thuật toán BVCL cải tiến sử dụng cấu trúc Dynamic Superset Bit-Vector giúp tiết kiệm bộ nhớ hơn 50% và giảm thời gian khai thác khoảng 20-30% so với các thuật toán như CharmL và MGCharm, đồng thời tích hợp khai thác đồng thời tập sinh và dàn tập phổ biến đóng.

2. Phạm vi áp dụng của thuật toán này là gì?
   Thuật toán phù hợp với các cơ sở dữ liệu giao dịch lớn, đặc biệt là các ứng dụng trong bán lẻ, tài chính, viễn thông và y học, nơi cần khai thác luật kết hợp không dư thừa từ dữ liệu phức tạp và lớn.

3. Làm thế nào thuật toán xử lý các tập không đóng và dư thừa?
   Thuật toán sử dụng kỹ thuật subsuming và danh sách subsuming/non-subsuming để loại bỏ các tập không đóng và dư thừa ngay trong quá trình khai thác, giúp giảm chi phí tính toán và bộ nhớ.

4. Cấu trúc DSBV hoạt động như thế nào trong khai thác dữ liệu?
   DSBV lưu trữ thông tin về các tập bao đóng tối tiểu dưới dạng vector bit động, cho phép truy xuất nhanh, cập nhật và loại bỏ các tập không cần thiết, từ đó tối ưu hóa quá trình khai thác dàn tập phổ biến đóng.

5. Có thể mở rộng thuật toán cho dữ liệu động hoặc trực tuyến không?
   Có thể. Luận văn đề xuất hướng phát triển mở rộng thuật toán để xử lý dữ liệu thay đổi liên tục, hỗ trợ khai thác trực tuyến, phù hợp với các ứng dụng thời gian thực trong tương lai.

Kết luận

• Thuật toán BVCL cải tiến sử dụng cấu trúc Dynamic Superset Bit-Vector giúp khai thác dàn các tập phổ biến đóng hiệu quả hơn về thời gian và bộ nhớ.
• Việc tích hợp khai thác đồng thời tập sinh và dàn tập phổ biến đóng giảm đáng kể chi phí tính toán so với phương pháp tách rời.
• Thuật toán xây dựng cấu trúc dàn theo hướng bottom-up, thiết lập mối quan hệ cha – con chính xác, hỗ trợ khai thác luật kết hợp không dư thừa.
• Kết quả thực nghiệm trên nhiều bộ dữ liệu tiêu chuẩn chứng minh tính khả thi và ưu việt của phương pháp đề xuất.
• Hướng phát triển tiếp theo là mở rộng thuật toán cho dữ liệu động, trực tuyến và tích hợp với các kỹ thuật trí tuệ nhân tạo để nâng cao ứng dụng thực tiễn.

Để khai thác tối đa giá trị từ nghiên cứu này, các nhà nghiên cứu và doanh nghiệp nên áp dụng thuật toán BVCL cải tiến trong các hệ thống khai thác dữ liệu lớn, đồng thời tiếp tục phát triển các công cụ hỗ trợ trực quan và mở rộng phạm vi ứng dụng.

Trích đoạn nội dung tài liệu

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. Ứ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.

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. Ý 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).