Luận Văn Thạc Sĩ: Khai Thác Dàn Tập Phổ Biến Đóng Sử Dụng Cấu Trúc DSBV

Luận văn thạc sĩ nghiên cứu khai thác dàn tập phổ biến đóng sử dụng cấu trúc dsbv, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh vự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: Tp. HCM

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• LỜI NÓI ĐẦU
• Bố cục đề tài
• Danh mục các bảng
• Danh mục các hình vẽ, đồ thị
• Danh mục từ viết tắt
• 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.5.2.1. Tìm FCS từ cấu trúc DSBV
• 2.5.2.2. Tìm minimal FCS từ cấu trúc DSBV
• 2.5.2.4. 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
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Khai Thác Dàn Tập Phổ Biến Đóng

Khai thác dàn tập phổ biến đóng là một lĩnh vực quan trọng trong khai thác dữ liệu, giúp phát hiện các mẫu và mối quan hệ trong dữ liệu lớn. Với sự gia tăng khối lượng dữ liệu, việc áp dụng các phương pháp khai thác hiệu quả trở nên cần thiết. Khai thác dàn tập phổ biến đóng không chỉ giúp tiết kiệm thời gian mà còn nâng cao độ chính xác trong việc phát hiện các luật kết hợp. Nghiên cứu này sẽ tập trung vào cấu trúc DSBV và các ứng dụng của nó trong khai thác dữ liệu.

1.1. Khái Niệm Về Khai Thác Dữ Liệu

Khai thác dữ liệu là quá trình tìm kiếm thông tin có giá trị từ các tập dữ liệu lớn. Nó kết hợp các công cụ từ thống kê và trí tuệ nhân tạo để phân tích và rút trích thông tin. Việc khai thác dữ liệu giúp phát hiện các mẫu và mối quan hệ ẩn trong dữ liệu, từ đó hỗ trợ ra quyết định trong nhiều lĩnh vực.

1.2. Ứng Dụng Của Khai Thác Dữ Liệu

Khai thác dữ liệu được ứng dụng rộng rãi trong nhiều lĩnh vực như tài chính, bán lẻ, viễn thông và y học. Các ứng dụng này giúp phân tích hành vi khách hàng, phát hiện gian lận và tối ưu hóa quy trình kinh doanh. Việc áp dụng khai thác dữ liệu mang lại lợi ích lớn cho các tổ chức trong việc ra quyết định và cải thiện hiệu suất.

II. Vấn Đề Và Thách Thức Trong Khai Thác Dàn Tập Phổ Biến Đóng

Mặc dù khai thác dàn tập phổ biến đóng mang lại nhiều lợi ích, nhưng cũng gặp phải nhiều thách thức. Một trong những vấn đề chính là khối lượng dữ liệu lớn và phức tạp, điều này đòi hỏi các thuật toán khai thác phải hiệu quả và nhanh chóng. Ngoài ra, việc phát hiện các mẫu dư thừa cũng là một thách thức lớn trong quá trình khai thác.

2.1. Khó Khăn Trong Việc Phát Hiện Mẫu

Việc phát hiện các mẫu trong dữ liệu lớn là một thách thức lớn. Các mẫu phổ biến thường chứa nhiều mẫu dư thừa, làm tăng chi phí tính toán. Do đó, cần có các phương pháp hiệu quả để loại bỏ các mẫu không cần thiết và chỉ giữ lại những mẫu có giá trị.

2.2. Thách Thức Về Hiệu Suất Thuật Toán

Hiệu suất của các thuật toán khai thác dàn tập phổ biến đóng là một yếu tố quan trọng. Các thuật toán cần phải được tối ưu hóa để xử lý dữ liệu lớn một cách nhanh chóng và hiệu quả. Việc cải tiến thuật toán là cần thiết để đáp ứng nhu cầu ngày càng cao trong khai thác dữ liệu.

III. Phương Pháp Khai Thác Dàn Tập Phổ Biến Đóng Hiệu Quả

Để khai thác dàn tập phổ biến đóng hiệu quả, cần áp dụng các phương pháp và kỹ thuật tiên tiến. Các phương pháp này bao gồm việc sử dụng cấu trúc DSBV để lưu trữ thông tin và tối ưu hóa quy trình khai thác. Việc áp dụng các thuật toán cải tiến sẽ giúp nâng cao hiệu suất và độ chính xác trong việc phát hiện các luật kết hợp.

3.1. Cấu Trúc DSBV Trong Khai Thác Dữ Liệu

Cấu trúc DSBV (Dynamic Superset Bit-Vector) là một phương pháp hiệu quả để lưu trữ thông tin về các tập phổ biến đóng. Cấu trúc này cho phép truy xuất nhanh chóng và tiết kiệm bộ nhớ, từ đó nâng cao hiệu suất khai thác dữ liệu.

3.2. Thuật Toán Cải Tiến BVCL

Thuật toán BVCL (Bit-Vector oriented Frequent Closed Itemset) là một trong những thuật toán tiên tiến trong khai thác dàn tập phổ biến đóng. Thuật toán này cải thiện hiệu suất khai thác bằng cách tổ chức dữ liệu một cách hợp lý, giúp giảm thiểu thời gian tính toán và tăng độ chính xác.

IV. Ứng Dụng Thực Tiễn Của Khai Thác Dàn Tập Phổ Biến Đóng

Khai thác dàn tập phổ biến đóng có nhiều ứng dụng thực tiễn trong các lĩnh vực khác nhau. Từ phân tích hành vi khách hàng đến phát hiện gian lận, các ứng dụng này giúp các tổ chức tối ưu hóa quy trình và nâng cao hiệu suất. Việc áp dụng các phương pháp khai thác hiệu quả sẽ mang lại giá trị lớn cho doanh nghiệp.

4.1. Phân Tích Hành Vi Khách Hàng

Khai thác dàn tập phổ biến đóng giúp phân tích hành vi mua sắm của khách hàng, từ đó đưa ra các chiến lược tiếp thị hiệu quả. Việc hiểu rõ thói quen và nhu cầu của khách hàng sẽ giúp doanh nghiệp cải thiện dịch vụ và tăng cường sự hài lòng của khách hàng.

4.2. Phát Hiện Gian Lận Trong Ngành Tài Chính

Trong ngành tài chính, khai thác dàn tập phổ biến đóng được sử dụng để phát hiện các hoạt động gian lận. Việc áp dụng các thuật toán khai thác hiệu quả giúp phát hiện sớm các hành vi bất thường, từ đó bảo vệ tài sản và giảm thiểu rủi ro cho doanh nghiệp.

V. Kết Luận Và Hướng Phát Triển Tương Lai

Khai thác dàn tập phổ biến đóng là một lĩnh vực quan trọng trong khai thác dữ liệu, với nhiều ứng dụng thực tiễn và tiềm năng phát triển. Việc cải tiến các thuật toán và phương pháp khai thác sẽ giúp nâng cao hiệu suất và độ chính xác trong việc phát hiện các luật kết hợp. Tương lai của lĩnh vực này hứa hẹn sẽ có nhiều tiến bộ và ứng dụng mới.

5.1. Tiềm Năng Phát Triển Của Khai Thác Dữ Liệu

Với sự gia tăng không ngừng của dữ liệu, tiềm năng phát triển của khai thác dữ liệu là rất lớn. Các công nghệ mới như trí tuệ nhân tạo và học máy sẽ tiếp tục được áp dụng để cải thiện quy trình khai thác và phân tích dữ liệu.

5.2. Hướng Nghiên Cứu Mới Trong Khai Thác Dữ Liệu

Các nghiên cứu mới trong lĩnh vực khai thác dữ liệu sẽ tập trung vào việc phát triển các thuật toán hiệu quả hơn, tối ưu hóa quy trình khai thác và mở rộng ứng dụng trong nhiều lĩnh vực khác nhau. Việc nghiên cứu và phát triển sẽ giúp khai thác dữ liệu trở thành một công cụ mạnh mẽ hơn trong tương lai.

Nội dung chính

Tổng quan nghiên cứu

Sự bùng nổ của kỷ nguyên số đang tạo ra khối lượng dữ liệu khổng lồ lên tới hàng triệu gigabyte mỗi ngày từ các hệ thống giao dịch, viễn thông và mạng xã hội. Phân tích các tập dữ liệu đồ sộ này bằng phương pháp thống kê truyền thống thường gặp bế tắc trước bài toán bùng nổ không gian tìm kiếm dạng hàm mũ. Trong lĩnh vực khai phá dữ liệu, việc trích xuất các tập phổ biến thường tạo ra hàng triệu mẫu dư thừa, làm gia tăng chi phí tính toán khi sinh tập luật kết hợp không dư thừa. Cấu trúc dàn của các tập phổ biến đóng là giải pháp tối ưu nhằm loại bỏ hoàn toàn các mẫu trùng lặp và duy trì tường minh quan hệ cha - con giữa các phần tử.

Luận văn thạc sĩ chuyên ngành Công nghệ thông tin của tác giả Trần Phú Dư, dưới sự hướng dẫn khoa học của Phó Giáo sư Tiến sĩ Lê Hoài Bắc tại Trường Đại học Ngoại ngữ - Tin học Thành phố Hồ Chí Minh, tập trung giải quyết bài toán khai thác dàn tập phổ biến đóng và tập sinh tối tiểu. Mục tiêu trọng tâm của nghiên cứu là xây dựng và hoàn thiện thuật toán cải tiến dựa trên thuật toán gốc BVCL, khai thác đồng thời dàn tập phổ biến đóng và tập sinh nhằm tối ưu hóa hiệu năng sinh luật kết hợp.

Nghiên cứu được triển khai thực nghiệm từ tháng 10 năm 2018 đến tháng 06 năm 2019, sử dụng 5 bộ dữ liệu chuẩn quốc tế bao gồm cả dạng dày đặc và dạng thưa. Đề tài mang lại giá trị khoa học vượt bậc khi giảm trên 50% dung lượng bộ nhớ tiêu thụ so với các cấu trúc vector bit tĩnh, đồng thời loại bỏ chi phí kiểm tra tập con bậc $O(C^2)$ trong không gian mẫu.

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

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng lý thuyết khai phá dữ liệu và khai thác tập phổ biến đóng, kết hợp chặt chẽ với lý thuyết dàn khái niệm và kết nối Galois. Các mô hình và khái niệm cốt lõi được vận dụng bao gồm:

• Tập phổ biến đóng (Frequent Closed Itemset - FCI): Một tập mục được xác định là đóng nếu không tồn tại bất kỳ tập cha nào bao nó có cùng độ hỗ trợ trong cơ sở dữ liệu giao dịch. Khái niệm này giúp thu gọn không gian biểu diễn dữ liệu mà không làm mất thông tin.
• Dàn tập phổ biến đóng (Frequent Closed Itemset Lattice - FCIL): Cấu trúc phân cấp sắp xếp các tập phổ biến đóng theo quan hệ cha - con trực tiếp từ dưới lên, cho phép trích xuất nhanh các luật kết hợp không dư thừa.
• Cấu trúc Dynamic Bit-Vector (DBV) và Dynamic Superset Bit-Vector (DSBV): Vector bit động DBV lưu trữ định danh giao dịch theo chiều dọc và lược bỏ các byte 0 đầu/cuối. Cấu trúc DSBV đại diện cho thông tin các tập bao đóng phổ biến bằng cách đánh dấu mã định danh tập đóng trên từng vị trí bit cụ thể.
• Tập sinh tối tiểu (Minimal Generator - mG): Tập con nhỏ nhất của một tập đóng có cùng độ hỗ trợ, đóng vai trò bản lề trong việc sinh các luật kết hợp thiết yếu nhất.

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

Nghiên cứu sử dụng 5 bộ dữ liệu thử nghiệm chuẩn từ kho dữ liệu FIMI: bộ dữ liệu Chess gồm 3.196 giao dịch và 75 thuộc tính, Mushroom gồm 8.124 giao dịch và 119 thuộc tính, Pumsb gồm 49.046 giao dịch, Retail gồm 88.162 giao dịch và T10I4D100K gồm 100.000 giao dịch tổng hợp. Phương pháp chọn mẫu có chủ đích bao phủ toàn diện cả cơ sở dữ liệu dày đặc có độ tương quan cao lẫn cơ sở dữ liệu thưa có quy mô giao dịch lớn.

Phương pháp phân tích tập trung vào mô hình hóa dữ liệu theo chiều dọc, áp dụng các phép toán logic trên bit (AND, OR) liên tiếp kết hợp với bảng tra cứu 8-bit nhằm tính toán nhanh độ hỗ trợ. Lý do lựa chọn hướng tiếp cận này là khả năng thao tác trực tiếp ở mức nhị phân giúp chương trình tận dụng tối đa băng thông thanh ghi CPU, đồng thời cơ chế phân tách danh sách Subsuming và Non-subsuming giúp loại bỏ hoàn toàn các bước duyệt lặp không cần thiết. Quá trình kiểm nghiệm và tối ưu mã nguồn được thực hiện liên tục trong khung thời gian 8 tháng nghiên cứu.

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

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

Quá trình thực nghiệm đối sánh giữa thuật toán đề xuất và các phương pháp kinh điển đã ghi nhận 4 phát hiện quan trọng:

• Tiết kiệm tài nguyên bộ nhớ vượt bậc: Cấu trúc DSBV giúp giảm từ 50% đến hơn 65% dung lượng RAM chiếm dụng so với cấu trúc vector bit tĩnh truyền thống, đặc biệt hiệu quả trên các cơ sở dữ liệu thưa quy mô 100.000 giao dịch như T10I4D100K.
• Triệt tiêu chi phí kiểm tra tập con dư thừa: Việc duy trì 2 danh sách phân tách Subsuming List và Non-Subsuming List giúp thuật toán mở rộng nhánh theo chiều sâu mà không cần thực hiện phép kiểm tra tập con lặp lại, tiết kiệm 100% chi phí duyệt thừa tại các nhánh đã bị hấp thụ.
• Khai thác đồng thời dàn FCIL và tập sinh mG: Thay vì phải chạy 2 giai đoạn tách biệt như các phương pháp CharmL hay MG-Charm, thuật toán tích hợp xử lý song song cả hai cấu trúc, rút ngắn tổng thời gian sinh luật kết hợp không dư thừa từ 30% đến 45% khi ngưỡng độ hỗ trợ giảm sâu.
• Tính toán bao đóng tối tiểu chính xác tuyệt đối: Thuật toán định vị nhanh vị trí bit 1 gần nhất thông qua hàm nzLSB, trích xuất chính xác 100% các liên kết cha - con trong dàn dữ liệu mà không phát sinh bất kỳ tập đóng giả mạo nào.

Thảo luận kết quả

Hiệu năng vượt trội của thuật toán bắt nguồn từ cơ chế truyền ngược thông tin DSBV trong cây đệ quy duyệt theo chiều sâu. Khi một nhánh kết thúc, thông tin bao đóng được tổng hợp ngay lập tức bằng phép hội bit OR, giúp các nút cha kế thừa toàn bộ cấu trúc tập con mà không cần quét lại dữ liệu.

Các kết quả thực nghiệm được biểu diễn trực quan thông qua đồ thị đường biểu diễn thời gian thực thi theo từng ngưỡng minSup (từ 0.1% đến 90%) và đồ thị cột so sánh mức tiêu thụ bộ nhớ RAM tính bằng megabyte. Khi ngưỡng minSup trên bộ dữ liệu Chess giảm từ 80% xuống 50%, thời gian thực thi của các phương pháp truyền thống tăng vọt theo đường tiệm cận đứng, trong khi thuật toán cải tiến vẫn duy trì tốc độ xử lý ổn định nhờ loại bỏ sớm các tập ứng viên không đóng.

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

Dựa trên kết quả đạt được, nghiên cứu đưa ra 4 khuyến nghị và giải pháp kỹ thuật cụ thể:

• Tối ưu hóa thuật toán trên nền tảng phần cứng đa luồng: Nhóm nghiên cứu và các kỹ sư phần mềm cần chuyển đổi các phép toán bitwise AND/OR trên cấu trúc DSBV sang xử lý song song bằng tập lệnh SIMD hoặc vi xử lý đồ họa GPU. Mục tiêu kỹ thuật là tăng tốc độ xử lý thêm 40% đến 60% đối với các cơ sở dữ liệu trên 10 triệu bản ghi, thực hiện trong lộ trình 6 đến 12 tháng.
• Tích hợp vào hệ thống gợi ý thương mại điện tử: Các doanh nghiệp bán lẻ trực tuyến cần ứng dụng mô hình khai thác dàn tập phổ biến đóng để tự động sinh các luật kết hợp không dư thừa theo thời gian thực. Giải pháp này giúp nâng cao độ chính xác của hệ thống đề xuất sản phẩm, hướng tới mục tiêu tăng 15% đến 20% tỷ lệ chuyển đổi đơn hàng trong vòng 3 đến 6 tháng triển khai.
• Mở rộng sang phân tích dữ liệu Tin - Sinh học: Các viện nghiên cứu y sinh học nên ứng dụng cấu trúc DSBV vào việc lập chỉ mục và phân tích biểu hiện chuỗi gen, protein với quy mô trên 1.000.000 mẫu chuỗi ADN, triển khai trong khung thời gian 12 đến 18 tháng.
• Xây dựng module mã nguồn mở cho hệ sinh thái Big Data: Cộng đồng phát triển công nghệ cần đóng gói thuật toán BVCL cải tiến thành các thư viện tương thích với Apache Spark hoặc Hadoop, hỗ trợ khai phá dữ liệu phân tán trong giai đoạn 6 tháng tiếp theo.

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

Nội dung và kết quả của luận văn mang lại giá trị thiết thực cho 4 nhóm đối tượng:

• Học viên cao học và nghiên cứu sinh ngành Khoa học máy tính: Tài liệu cung cấp hệ thống chứng minh toán học chặt chẽ về lý thuyết dàn Galois, kỹ thuật tối ưu hóa không gian tìm kiếm và phương pháp biểu diễn dữ liệu nhị phân chuyên sâu.
• Kỹ sư dữ liệu và chuyên gia Machine Learning: Cung cấp giải pháp thực tế để xử lý các bài toán phân tích giỏ hàng, giảm tải áp lực bộ nhớ RAM cho các luồng xử lý dữ liệu lớn (Big Data Pipelines).
• Nhà phát triển hệ thống gợi ý (Recommendation Systems): Hỗ trợ xây dựng các mô hình trích xuất luật kết hợp ngắn gọn, tốc độ cao, loại bỏ hoàn toàn các đề xuất dư thừa làm phiền người dùng.
• Chuyên gia an ninh mạng và phân tích lưu lượng: Vận dụng cấu trúc dàn để phân tích log giao dịch mạng, phát hiện các mẫu tấn công xâm nhập bất thường xuất hiện đồng thời trong hàng triệu gói tin.

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

• Cấu trúc Dynamic Superset Bit-Vector (DSBV) khác biệt gì so với Bit-Vector truyền thống? Cấu trúc DSBV không lưu trữ trực tiếp mã giao dịch mà lưu trữ định danh của các tập bao đóng phổ biến. Bằng cách lược bỏ toàn bộ các byte 0 ở hai đầu và chỉ giữ lại dải byte chứa bit 1, DSBV giúp tiết kiệm hơn 50% bộ nhớ so với vector bit tĩnh.

• Tại sao việc khai thác Dàn tập phổ biến đóng lại hiệu quả hơn khai thác tập phổ biến thông thường? Khai thác tập phổ biến thông thường tạo ra số lượng mẫu khổng lồ bị trùng lặp độ hỗ trợ. Dàn tập phổ biến đóng chỉ giữ lại các tập cực đại không bị bao bởi tập có cùng tần suất, giúp giảm hàng nghìn lần số lượng mẫu cần lưu trữ và duyệt luật.

• Cơ chế nào giúp thuật toán BVCL tránh được phép kiểm tra tập con lặp lại? Thuật toán chia tập mục thành 2 danh sách phân tách gồm Subsuming List và Non-Subsuming List. Khi một tập mục được xác định bị hấp thụ, nó sẽ được hợp nhất ngay lập tức, loại bỏ hoàn toàn nhu cầu so khớp tập con bậc hai $O(C^2)$.

• Đóng góp cải tiến lớn nhất của luận văn so với thuật toán BVCL gốc là gì? Thuật toán gốc chỉ tập trung vào việc dựng dàn tập phổ biến đóng. Luận văn đã tích hợp thành công cơ chế khai thác song song tập sinh tối tiểu trực tiếp trong quá trình duyệt đệ quy, giúp rút ngắn thời gian sinh luật kết hợp từ 30% đến 45%.

• Luận văn đã kiểm nghiệm thuật toán trên những loại dữ liệu nào? Nghiên cứu đã thử nghiệm toàn diện trên 5 bộ dữ liệu benchmark quốc tế gồm Chess, Mushroom, Pumsb, Retail và T10I4D100K với quy mô từ 3.196 đến 100.000 giao dịch, kiểm chứng độ ổn định trên cả dạng dữ liệu dày đặc lẫn dữ liệu thưa.

Kết luận

• Đóng góp lý thuyết: Hệ thống hóa và hoàn thiện các định lý, bổ đề toán học về kiểm tra tính đóng và kế thừa bao đóng trong không gian bit.
• Sáng tạo thuật toán: Đề xuất giải pháp khai thác đồng thời cấu trúc Dàn tập phổ biến đóng và tập sinh tối tiểu mG trên nền tảng vector bit động.
• Đột phá hiệu năng: Cắt giảm trên 50% dung lượng bộ nhớ RAM và tối ưu hóa thời gian thực thi khi chạy trên các cơ sở dữ liệu lớn.
• Giá trị thực tiễn: Tạo tiền đề vững chắc cho các ứng dụng phân tích hành vi tiêu dùng, tin - sinh học và phát hiện xâm nhập mạng.
• Đảm bảo tính hoàn chỉnh: Chứng minh toán học khẳng định thuật toán không bỏ sót bất kỳ tập đóng và mối quan hệ cha - con nào trong dữ liệu.

Các nhóm nghiên cứu và doanh nghiệp công nghệ quan tâm đến bài toán tối ưu hóa khai phá dữ liệu lớn có thể áp dụng ngay mô hình thuật toán và cấu trúc DSBV trong luận văn để nâng cao hiệu suất xử lý dữ liệu. Kế hoạch mở rộng thuật toán sang mô hình tính toán phân tán trên GPU dự kiến sẽ được tiếp tục hoàn thiện trong khung thời gian 6 đến 12 tháng tới.

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