Luận án tiến sĩ về khai phá top k mẫu dãy thường xuyên trọng số với khoảng cách thời gian

Luận án tiến sĩ nghiên cứu khai phá top k mẫu dãy thường xuyên trọng số với khoảng cách thời gian, ứng dụng trong phân tích dữ liệu lớn.

• Tác giả: Lê Duy Thảo
• Người hướng dẫn: TS. Nguyễn Việt Anh
• Trường học: Học viện Khoa học và Công nghệ
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Nghiên Cứu Khai Phá Top-K Mẫu Dãy Thường Xuyên Trọng Số Với Khoảng Cách Thời Gian
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN KHAI PHÁ DỮ LIỆU
• 1.1. Định nghĩa luật kết hợp
• 1.2. Độ hỗ trợ tập mục
• 1.3. Độ tin cậy của luật kết hợp
• 1.4. Tập mục thường xuyên
• 1.5. Quá trình tìm kiếm luật kết hợp
• 2. KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG
• 2.1. Bài toán khai phá mẫu dãy thường xuyên và một số khái niệm cơ bản trong khai phá mẫu dãy thường xuyên
• 2.1.1. Cơ sở dữ liệu dãy
• 2.1.2. Dãy con
• 2.1.3. Độ hỗ trợ của một dãy
• 2.1.4. Mẫu dãy thường xuyên
• 2.1.5. Luật dãy trong khai phá dữ liệu
• 2.2. Bài toán khai phá mẫu dãy thường xuyên
• 2.3. Mẫu dãy thường xuyên có trọng số
• 2.4. Mẫu dãy thường xuyên với khoảng cách thời gian
• 3. THUẬT TOÁN APRIORIALL
• 4. THỬ NGHIỆM VÀ NHẬN XÉT
• KẾT LUẬN VÀ KIẾN NGHỊ
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về khai phá dữ liệu

Khai phá dữ liệu là một quá trình quan trọng trong việc khám phá tri thức từ các nguồn dữ liệu lớn. Khai phá dữ liệu không chỉ giúp tìm ra các mẫu có ích mà còn phát hiện mối liên hệ giữa chúng. Một trong những nội dung cốt lõi của khai phá dữ liệu là khai phá luật kết hợp, bao gồm hai bước chính: tìm các tập mục thường xuyên và sinh ra các luật kết hợp từ các tập mục đó. Bài toán khai phá tập mục thường xuyên đã thu hút sự quan tâm của nhiều nhà nghiên cứu, với hàng trăm kết quả nghiên cứu được công bố. Các thuật toán như AprioriAll và PrefixSpan đã được phát triển để giải quyết bài toán này. Tuy nhiên, một trong những hạn chế chính của các phương pháp truyền thống là không thể điều chỉnh số lượng mẫu dãy thường xuyên thông qua phản hồi của người sử dụng. Do đó, việc nghiên cứu các mẫu dãy có trọng số và khoảng cách thời gian trở nên cần thiết.

1.1. Khái niệm về mẫu dãy thường xuyên

Mẫu dãy thường xuyên được định nghĩa là các dãy xuất hiện nhiều lần trong cơ sở dữ liệu dãy. Để xác định một mẫu dãy là thường xuyên, nó cần phải thỏa mãn ngưỡng hỗ trợ tối thiểu. Mẫu dãy thường xuyên có thể được sử dụng trong nhiều lĩnh vực như phân tích thị trường và phát hiện xâm nhập. Việc tìm kiếm các mẫu dãy thường xuyên là một thách thức lớn, đặc biệt khi số lượng mục trong cơ sở dữ liệu tăng lên. Các thuật toán khai phá mẫu dãy thường xuyên như AprioriAll và PrefixSpan đã được phát triển để giải quyết vấn đề này, tuy nhiên, vẫn còn nhiều hạn chế cần khắc phục.

II. Khai phá mẫu dãy thường xuyên có trọng số

Khi nghiên cứu về khai phá mẫu dãy thường xuyên, một yếu tố quan trọng cần xem xét là trọng số của các mẫu. Mỗi mẫu dãy có thể có mức độ quan trọng khác nhau, và việc không tính đến trọng số có thể dẫn đến những kết luận sai lệch. Khai phá mẫu dãy thường xuyên có trọng số yêu cầu xây dựng các thuật toán đảm bảo tính chất phản đơn điệu, cho phép cân bằng giữa độ hỗ trợ và trọng số của dãy. Việc áp dụng trọng số vào các mẫu dãy không chỉ giúp cải thiện độ chính xác của các kết quả mà còn mở rộng khả năng ứng dụng của khai phá dữ liệu trong thực tiễn.

2.1. Thuật toán khai phá mẫu dãy thường xuyên có trọng số

Thuật toán khai phá mẫu dãy thường xuyên có trọng số được thiết kế để tìm ra các mẫu dãy có trọng số cao trong cơ sở dữ liệu. Các thuật toán này thường sử dụng các phương pháp như WPrefixSpan để xác định các mẫu dãy thường xuyên có trọng số. Việc áp dụng trọng số vào các mẫu dãy giúp tăng cường khả năng phân tích và đưa ra quyết định trong các lĩnh vực như phân tích thị trường và dự đoán hành vi người tiêu dùng. Điều này cho thấy tầm quan trọng của việc nghiên cứu và phát triển các thuật toán khai phá mẫu dãy thường xuyên có trọng số.

III. Khai phá top k mẫu dãy thường xuyên trọng số với khoảng cách thời gian

Bài toán khai phá top-k mẫu dãy thường xuyên trọng số với khoảng cách thời gian là một trong những vấn đề phức tạp trong khai phá dữ liệu. Mục tiêu của bài toán này là tìm ra k mẫu dãy thường xuyên có trọng số cao nhất trong một khoảng thời gian nhất định. Việc xác định khoảng cách thời gian giữa các mẫu dãy là rất quan trọng, vì nó ảnh hưởng đến độ quan trọng của các mẫu. Các thuật toán như WIPrefixSpan đã được phát triển để giải quyết bài toán này, cho phép tìm kiếm hiệu quả các mẫu dãy trong các cơ sở dữ liệu lớn.

3.1. Phát biểu bài toán

Bài toán khai phá top-k mẫu dãy thường xuyên trọng số với khoảng cách thời gian có thể được phát biểu như sau: Given a sequence database and a weight threshold, find the top-k frequent weighted sequences that satisfy the time constraints. Việc phát biểu rõ ràng bài toán giúp định hướng cho việc phát triển các thuật toán và phương pháp giải quyết hiệu quả hơn. Điều này không chỉ giúp cải thiện độ chính xác của các kết quả mà còn mở rộng khả năng ứng dụng của khai phá dữ liệu trong thực tiễn.

Nội dung chính

Tổng quan nghiên cứu

Khai phá dữ liệu là một lĩnh vực quan trọng trong công nghệ thông tin, với mục tiêu trích xuất tri thức có ích từ các cơ sở dữ liệu lớn. Theo ước tính, các cơ sở dữ liệu hiện nay có thể chứa hàng triệu giao dịch, đòi hỏi các phương pháp khai phá hiệu quả để phát hiện các mẫu dãy thường xuyên và luật kết hợp có ý nghĩa. Luận văn tập trung nghiên cứu khai phá Top-K mẫu dãy thường xuyên trọng số với khoảng cách thời gian, một bài toán mở rộng của khai phá mẫu dãy thường xuyên truyền thống nhằm phản ánh mức độ quan trọng và tính thời gian của các mục dữ liệu.

Mục tiêu cụ thể của nghiên cứu là: (1) tìm hiểu các kiến thức cơ bản và các biến thể ràng buộc chi tiết về trọng số, thời gian trong khai phá mẫu dãy; (2) cài đặt và thử nghiệm thuật toán khai phá Top-K mẫu dãy thường xuyên trọng số với khoảng cách thời gian. Phạm vi nghiên cứu tập trung vào dữ liệu có trọng số chuẩn hóa và khoảng cách thời gian giữa các mục trong cơ sở dữ liệu dãy, với bộ dữ liệu thử nghiệm lấy từ kho dữ liệu UCI.

Ý nghĩa của nghiên cứu được thể hiện qua việc nâng cao hiệu quả khai phá mẫu dãy thường xuyên trong các ứng dụng thực tế như phân tích thị trường, dự đoán nhu cầu khách hàng, phát hiện xâm nhập mạng, và phân tích mẫu truy cập web. Việc khai phá mẫu dãy có trọng số và khoảng cách thời gian giúp phản ánh chính xác hơn mức độ quan trọng và tính liên tục của các sự kiện trong dữ liệu, từ đó cải thiện chất lượng các luật kết hợp và mẫu dãy được phát hiện.

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 khai phá dữ liệu, đặc biệt là khai phá mẫu dãy thường xuyên và luật kết hợp. Hai thuật toán chủ đạo được nghiên cứu là AprioriAll và PrefixSpan:

• AprioriAll: Thuật toán dựa trên nguyên tắc Apriori, khai phá các mẫu dãy thường xuyên theo chiều rộng, sinh các tập ứng viên dựa trên các mẫu dãy độ dài k-1, sau đó tính độ hỗ trợ để lọc ra các mẫu dãy thường xuyên. Thuật toán này có hạn chế về hiệu suất do phải quét nhiều lần cơ sở dữ liệu.

• PrefixSpan: Thuật toán dựa trên phương pháp phát triển mẫu dãy theo tiền tố, sử dụng kỹ thuật đệ quy và chia để trị để giảm không gian tìm kiếm. Thuật toán không cần sinh tập ứng viên mà khai thác cấu trúc dữ liệu điều kiện theo tiền tố, giúp giảm đáng kể thời gian và bộ nhớ sử dụng.

Các khái niệm chính bao gồm:

• Mẫu dãy thường xuyên: Dãy con xuất hiện với tần suất vượt ngưỡng hỗ trợ tối thiểu trong cơ sở dữ liệu dãy.

• Trọng số chuẩn hóa: Mỗi mục dữ liệu được gán một trọng số thể hiện mức độ quan trọng, trọng số chuẩn hóa của mẫu dãy là trung bình trọng số các mục trong dãy.

• Khoảng cách thời gian: Thời gian giữa các thành phần trong dãy, được ràng buộc bởi các điều kiện tối thiểu và tối đa nhằm phản ánh tính liên tục và quan trọng của mẫu dãy theo thời gian.

• Top-K mẫu dãy thường xuyên: Phương pháp khai phá không dựa trên ngưỡng hỗ trợ cố định mà tìm ra k mẫu dãy có giá trị cao nhất theo trọng số chuẩn hóa và khoảng cách thời gian.

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

Nguồn dữ liệu sử dụng là các bộ dữ liệu dãy thực nghiệm lấy từ kho dữ liệu UCI, có gán trọng số cho từng mục và thông tin khoảng cách thời gian giữa các thành phần. Cỡ mẫu dao động khoảng vài nghìn đến vài chục nghìn bản ghi dãy, đủ để đánh giá hiệu quả thuật toán.

Phương pháp phân tích bao gồm:

• Nghiên cứu lý thuyết: Tổng hợp các định nghĩa, mệnh đề, và thuật toán khai phá mẫu dãy thường xuyên, trọng số và khoảng cách thời gian từ các công trình nghiên cứu đã công bố.

• Nghiên cứu thực nghiệm: Cài đặt các thuật toán AprioriAll, PrefixSpan, WPrefixSpan và WIPrefixSpan để khai phá mẫu dãy thường xuyên trọng số với khoảng cách thời gian. Thử nghiệm trên các bộ dữ liệu thực tế, đo lường thời gian chạy, bộ nhớ sử dụng và số lượng mẫu dãy được khai phá.

Timeline nghiên cứu kéo dài trong khoảng 12 tháng, bao gồm các giai đoạn: tổng quan tài liệu, thiết kế và cài đặt thuật toán, thử nghiệm và đánh giá, viết luận văn và hoàn thiệ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ả thuật toán WIPrefixSpan: Thuật toán khai phá mẫu dãy thường xuyên trọng số với khoảng cách thời gian (WIPrefixSpan) cho thấy thời gian chạy giảm khoảng 30-40% so với thuật toán AprioriAll trên các bộ dữ liệu có kích thước lớn (ví dụ BMSWebView1, Bible). Bộ nhớ sử dụng cũng giảm tương ứng, nhờ kỹ thuật chia nhỏ không gian tìm kiếm theo tiền tố và áp dụng ràng buộc trọng số, thời gian.

2. Ảnh hưởng của trọng số và khoảng cách thời gian: Việc gán trọng số chuẩn hóa và ràng buộc khoảng cách thời gian giúp giảm số lượng mẫu dãy thường xuyên được khai phá khoảng 25-35% so với khai phá mẫu dãy thường xuyên truyền thống, tập trung vào các mẫu có ý nghĩa thực tiễn cao hơn.

3. Top-K mẫu dãy thường xuyên: Phương pháp khai phá Top-K giúp người dùng không cần đặt ngưỡng hỗ trợ tối thiểu, mà vẫn tìm được k mẫu dãy có giá trị nhất. Thử nghiệm với k = 10, 20, 50 cho thấy thuật toán tự động điều chỉnh ngưỡng hỗ trợ, đảm bảo hiệu quả khai phá và giảm thiểu mẫu dãy không cần thiết.

4. So sánh thuật toán PrefixSpan và AprioriAll: PrefixSpan tiết kiệm thời gian chạy trung bình 35% so với AprioriAll do không sinh tập ứng viên và sử dụng cấu trúc dữ liệu điều kiện theo tiền tố. Điều này được minh họa qua biểu đồ thời gian chạy trên các bộ dữ liệu thử nghiệm.

Thảo luận kết quả

Nguyên nhân chính của hiệu quả vượt trội của WIPrefixSpan và WIPrefixSpan là do kỹ thuật đệ quy và chia nhỏ không gian tìm kiếm theo tiền tố, kết hợp với việc áp dụng ràng buộc trọng số và khoảng cách thời gian giúp loại bỏ sớm các mẫu dãy không phù hợp. So với các nghiên cứu trước đây chỉ tập trung vào khai phá mẫu dãy thường xuyên không trọng số, kết quả này cho thấy sự cải tiến rõ rệt về hiệu quả và tính ứng dụng.

Việc áp dụng trọng số chuẩn hóa phản ánh đúng mức độ quan trọng của các mục dữ liệu trong thực tế, ví dụ như trong phân tích thị trường, các mặt hàng có giá trị cao hoặc tần suất mua lớn được ưu tiên khai phá. Ràng buộc khoảng cách thời gian giúp phát hiện các mẫu dãy có tính liên tục và ý nghĩa theo thời gian, phù hợp với các ứng dụng như phân tích hành vi người dùng hoặc phát hiện xâm nhập mạng.

Kết quả cũng cho thấy việc sử dụng thuật toán Top-K giúp giải quyết vấn đề khó khăn trong việc lựa chọn ngưỡng hỗ trợ tối thiểu, một thách thức phổ biến trong khai phá dữ liệu. Thuật toán tự động điều chỉnh ngưỡng dựa trên giá trị k do người dùng cung cấp, giúp khai phá hiệu quả hơn và giảm thiểu mẫu dãy không cần thiết.

Các dữ liệu có thể được trình bày qua biểu đồ so sánh thời gian chạy và bộ nhớ sử dụng giữa các thuật toán, bảng thống kê số lượng mẫu dãy thường xuyên được khai phá theo từng phương pháp và điều kiện trọng số, khoảng cách thời gian.

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

1. Áp dụng thuật toán WIPrefixSpan trong phân tích thị trường: Đề nghị các doanh nghiệp sử dụng thuật toán này để khai phá các mẫu dãy mua hàng có trọng số và khoảng cách thời gian, nhằm phát hiện các xu hướng tiêu dùng liên tục và quan trọng, nâng cao hiệu quả chiến lược marketing. Thời gian triển khai dự kiến 3-6 tháng.

2. Phát triển phần mềm khai phá dữ liệu tích hợp trọng số và thời gian: Khuyến nghị các tổ chức nghiên cứu và phát triển phần mềm tích hợp thuật toán WIPrefixSpan vào các hệ thống khai phá dữ liệu hiện có, giúp người dùng dễ dàng khai thác tri thức có giá trị từ dữ liệu lớn. Thời gian phát triển khoảng 6-9 tháng.

3. Đào tạo và nâng cao nhận thức về khai phá dữ liệu trọng số và thời gian: Các trường đại học và trung tâm đào tạo nên cập nhật nội dung giảng dạy về khai phá mẫu dãy trọng số và khoảng cách thời gian, giúp sinh viên và chuyên gia nắm bắt xu hướng mới trong lĩnh vực khai phá dữ liệu. Thời gian thực hiện 1 năm.

4. Mở rộng nghiên cứu về khai phá mẫu dãy trong các lĩnh vực khác: Đề xuất nghiên cứu áp dụng thuật toán khai phá mẫu dãy trọng số với khoảng cách thời gian trong các lĩnh vực như y tế, an ninh mạng, và phân tích DNA để khai thác tri thức sâu hơn. Thời gian nghiên cứu dự kiến 1-2 năm.

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

1. Nhà nghiên cứu và học giả trong lĩnh vực khai phá dữ liệu và khoa học dữ liệu: Luận văn cung cấp kiến thức chuyên sâu về thuật toán khai phá mẫu dãy thường xuyên trọng số với khoảng cách thời gian, giúp phát triển các nghiên cứu mới và ứng dụng thực tiễn.

2. Chuyên gia phân tích dữ liệu và kỹ sư dữ liệu trong doanh nghiệp: Các chuyên gia có thể áp dụng thuật toán và phương pháp trong luận văn để nâng cao hiệu quả phân tích dữ liệu khách hàng, dự báo xu hướng và tối ưu hóa chiến lược kinh doanh.

3. Sinh viên và học viên cao học ngành công nghệ thông tin, hệ thống thông tin: Luận văn là tài liệu tham khảo quý giá giúp hiểu rõ các thuật toán khai phá dữ liệu nâng cao, phục vụ cho học tập và nghiên cứu khoa học.

4. Nhà phát triển phần mềm và kỹ sư hệ thống khai phá dữ liệu: Các kỹ sư có thể dựa vào các thuật toán và mô hình trong luận văn để phát triển các công cụ khai phá dữ liệu tích hợp trọng số và khoảng cách thời gian, đáp ứng nhu cầu thực tế.

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

1. Top-K mẫu dãy thường xuyên là gì và có ưu điểm gì so với phương pháp truyền thống?
   Top-K mẫu dãy thường xuyên là phương pháp khai phá k mẫu dãy có giá trị cao nhất mà không cần đặt ngưỡng hỗ trợ tối thiểu cố định. Ưu điểm là người dùng không phải đoán ngưỡng phù hợp, tránh khai phá quá nhiều hoặc quá ít mẫu, giúp tập trung vào các mẫu quan trọng nhất.

2. Tại sao cần gán trọng số cho các mục dữ liệu trong khai phá mẫu dãy?
   Trọng số phản ánh mức độ quan trọng hoặc giá trị của từng mục dữ liệu, giúp phân biệt các mẫu dãy có ý nghĩa thực tiễn khác nhau. Ví dụ, trong phân tích mua hàng, mặt hàng có giá trị cao hơn sẽ có trọng số lớn hơn, giúp khai phá các mẫu dãy có giá trị hơn.

3. Khoảng cách thời gian ảnh hưởng thế nào đến khai phá mẫu dãy?
   Khoảng cách thời gian giữa các thành phần trong dãy giúp xác định tính liên tục và mức độ quan trọng của mẫu dãy theo thời gian. Mẫu dãy có khoảng cách thời gian nhỏ thường có ý nghĩa hơn, ví dụ trong phân tích hành vi người dùng hoặc phát hiện xâm nhập.

4. Thuật toán PrefixSpan khác gì so với AprioriAll?
   PrefixSpan sử dụng kỹ thuật phát triển mẫu dãy theo tiền tố và đệ quy, không sinh tập ứng viên như AprioriAll, giúp giảm đáng kể thời gian chạy và bộ nhớ sử dụng, đặc biệt hiệu quả với cơ sở dữ liệu lớn.

5. Làm thế nào để lựa chọn giá trị k trong khai phá Top-K?
   Giá trị k được chọn dựa trên nhu cầu khai phá và khả năng xử lý dữ liệu của người dùng. Thông thường, k được chọn sao cho số lượng mẫu dãy thu được đủ để phân tích mà không quá nhiều gây khó khăn trong xử lý và diễn giải.

Kết luận

• Luận văn đã nghiên cứu và phát triển thuật toán khai phá Top-K mẫu dãy thường xuyên trọng số với khoảng cách thời gian, nâng cao hiệu quả khai phá so với các phương pháp truyền thống.
• Thuật toán WIPrefixSpan kết hợp kỹ thuật đệ quy, chia nhỏ không gian tìm kiếm và áp dụng ràng buộc trọng số, thời gian giúp giảm thời gian chạy và bộ nhớ sử dụng khoảng 30-40%.
• Việc áp dụng trọng số chuẩn hóa và ràng buộc khoảng cách thời gian giúp phát hiện các mẫu dãy có ý nghĩa thực tiễn cao hơn, phù hợp với nhiều ứng dụng như phân tích thị trường, an ninh mạng.
• Phương pháp Top-K giải quyết vấn đề lựa chọn ngưỡng hỗ trợ tối thiểu, giúp người dùng dễ dàng khai phá các mẫu dãy quan trọng nhất.
• Đề xuất các bước tiếp theo bao gồm mở rộng ứng dụng thuật toán trong các lĩnh vực khác, phát triển phần mềm khai phá dữ liệu tích hợp trọng số và thời gian, đồng thời đào tạo nâng cao nhận thức về khai phá dữ liệu nâng cao.

Các nhà nghiên cứu và chuyên gia phân tích dữ liệu nên áp dụng và thử nghiệm thuật toán trong các dự án thực tế để khai thác tri thức giá trị từ dữ liệu lớn, đồng thời đóng góp ý kiến cải tiến cho các phiên bản thuật toán tiếp theo.

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

CHƯƠNG 1. TỔNG QUAN KHAI PHÁ DỮ LIỆU Trong khai phá dữ liệu, tìm hiểu luật kết hợp [1] là một phương pháp nghiên cứu rất hiệu quả và thường xuyên được sử dụng trong việc tìm ra những mối liên kết hữu ích giữa các biến số trong những CSDL lớn. Các luật liên kết chặt chẽ tìm được trong CSDL được ứng dụng trong rất nhiều lĩnh vực khác nhau. Ví dụ như: - Thu thập các loại mặt hàng mà người dùng thường mua cùng với nhau.

- Thu thập các trang web mà người dùng thường truy cập cùng nhau. - Thu thập thông tin mặt hàng sẽ được mua tiếp theo sau khi đã mua mặt hàng nào đó. Tập mục CSDL giao tác D gồm một tập các giao tác D = { t1, t2, … , tN }. Tập I = { i1, i2, … , iM } là tập tất cả các mục (item) xuất hiện trong D.

Mỗi tập con X của I được gọi là một tập mục (itemset). Một tập mục X chứa k mục riêng biệt được gọi là tập mục cỡ k hoặc k-tập mục (k-itemset). Định nghĩa luật kết hợp Tìm kiếm luật kết hợp là tìm ra sự kết hợp hay mối tương quan giữa các tập mục với nhau. Những luật kết hợp này có dạng X → Y với X, Y  I và X ∩ Y = ∅.

Để minh họa cho khái niệm, chúng ta sẽ sử dụng một ví dụ nhỏ trong lĩnh vực mua hàng, tập tất cả các mục là I = { sữa, bánh mỳ, bơ, bia } và CSDL giao tác nhỏ chứa các mục (1 - thể hiện mục xuất hiện trong giao dịch và 0 - thể hiện sự vắng mặt trong giao dịch) được thể hiện trong bảng dưới đây: 6 luan an Bảng 1. Ví dụ về CSDL giao tác với 4 mục và 5 giao tác ID giao dịch Sữa Bánh mỳ Bơ Bia 1 1 1 0 0 2 0 0 1 0 3 0 0 0 1 4 1 1 1 0 5 0 1 0 0 Một ví dụ về luật kết hợp cho CSDL trên sẽ có dạng {bánh mỳ, bơ} →{sữa}, có nghĩa là nếu người dùng mua bánh mỳ và bơ thì họ cũng sẽ mua sữa. Tất nhiên, ví dụ trên là cực kỳ nhỏ. Trong ứng dụng thực tiễn, một luật kết hợp cần có sự nghiên cứu của hàng trăm giao dịch trước khi được coi là có ý nghĩa về mặt thống kê, và tập dữ liệu thường chứa tới hàng ngàn hoặc hàng triệu giao dịch.

Để có thể chọn ra được các luật kết hợp có ý nghĩa từ rất nhiều luật kết hợp có thể có với một CSDL giao tác, người ta thường sử dụng 2 ràng buộc rất phổ biến đó là độ hỗ trợ nhỏ nhất (minimum thresholds support - min_supp) và độ tin cậy nhỏ nhất (minimum thresholds confidence - min_conf). Độ hỗ trợ tập mục Tập mục X  I, số các giao tác chứa tập mục X trong CSDL D gọi là số đếm hỗ trợ (support count - SC) của X, ký hiệu là SC (X). Độ hỗ trợ của một tập mục X - ký hiệu supp (X) – được định nghĩa là tỷ lệ giao dịch trong tập dữ liệu có chứa tập mục X. Công thức tính độ hỗ trợ : SC(X) Supp (X) = P (X) = (1.1) M Trong CSDL ví dụ ở Bảng 1.1, tập mục {sữa, bánh mỳ, bơ} có độ hỗ trợ 7 luan an là 1/5 = 0.2, nghĩa là tập mục X xuất hiện 20% trong toàn bộ tất cả các giao dịch.

Độ tin cậy của luật kết hợp Độ tin cậy của luật kết hợp X→Y - ký hiệu conf (X→Y) - được định nghĩa là xác suất tất cả các giao dịch chứa tập mục Y trong khi đã có tập mục X. Công thức tính độ tin cậy : SC(X∪Y) supp(X∪Y) Conf (X→Y) = P (Y|X) = = (1.2) SC(X) supp(X) Ở đây, supp (X ∪ Y) mang nghĩa độ hỗ trợ với giao dịch xuất hiện cả 2 tập mục X và Y chứ không phải độ hỗ trợ với giao dịch xuất hiện X hoặc Y. Trong CSDL ví dụ ở Bảng 1.1, luật kết hợp {sữa, bánh mỳ}→{bơ} có độ tin cậy là 1/2 = 0.5), có nghĩa là 50% số lần người dùng mua sữa và bánh mỳ, họ sẽ mua luôn cả bơ. Tập mục thường xuyên Các tập mục có độ hỗ trợ lớn hơn độ hỗ trợ tối thiểu gọi là tập mục thường xuyên (frequent itemset).

Tập các k-tập mục (k-itemset) là các tập mục thường xuyên ký hiệu là Lk. Trong CSDL ví dụ ở Bảng 1.1, nếu cho ngưỡng hộ trợ nhỏ nhất là 30%, khi đó tập mục {sữa, bánh mỳ, bơ} có độ hỗ trợ 20% < 30% sẽ không là 1 tập mục thường xuyên, nhưng với tập mục {sữa, bánh mỳ} có độ hỗ trợ là 2/5 = 40% > 30% là một tập mục thường xuyên trong CSDL đã cho. Quá trình tìm kiếm luật kết hợp Một luật kết hợp có ý nghĩa phải được thỏa mãn cả 2 ngưỡng hỗ trợ và tin cậy nhỏ nhất do người dùng đặt ra. Việc tìm kiếm luật kết hợp được chia ra làm 2 bước riêng rẽ: - Bước thứ nhất, ngưỡng độ hỗ trợ nhỏ nhất được sử dụng để tìm ra mọi tập mục thường xuyên có trong CSDL.

- Bước hai, tất cả các tập mục thường xuyên kết hợp với ngưỡng tin cậy nhỏ nhất để hình thành nên luật. 8 luan an Ta có thể thấy rằng bước 2 thực hiện khá đơn giản, và bước một cần chú ý nhiều hơn. Tìm kiếm tất cả các tập mục thường xuyên là rất khó khăn vì nó liên quan tới việc tìm kiếm tất cả các mục kết hợp. Đối với một CSDL giao tác có N mục thì có thể xuất hiện tới 2N-1 tập mục cần xét, trong một CSDL thực tế lại có thể có tới hàng trăm, hàng nghìn mục khác nhau.

Do đó, có thể coi bước tìm tất cả các tập mục thường xuyên là bước quan trọng nhất của bài toán tìm kiếm luật kết hợp. Số lượng tập mục phải xét với 5 mục ban đầu. KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG 1. Bài toán khai phá mẫu dãy thường xuyên và một số khái niệm cơ bản trong khai phá mẫu dãy thường xuyên 1.

Cơ sở dữ liệu dãy Cho I = {i1, i2, …, in} là tập hợp các mục dữ liệu. Một dãy Sm là một danh sách được sắp xếp theo thứ tự của các mục dữ liệu dạng {s1, s2, …, sm} với sj  I là một tập mục được gọi là thành phần của dãy. Khi đó, S = {s1, s2, …, sm} và sj có dạng (i1i2… ik) và it là một mục dữ liệu. Một dãy S bị loại nếu chỉ có duy nhất một mục dữ liệu.

Một mục dữ liệu chỉ xuất hiện 1 lần trong 1 thành phần của một dãy sj, nhưng có thể xuất hiện nhiều lần trong các thành phần khác nhau của một dãy S. Kích thước |S| của một dãy là số lượng của các thành phần trong dãy S. Độ dài l(S) của dãy là tổng số mục dữ liệu trong dãy S. Một cơ sở dữ liệu dãy SDB={S1,S2,…,Sn} là một tập các bộ dữ liệu (sid,Sk) với sid là định danh của một dãy và Sk là một dãy dữ liệu.

Ví dụ về một cơ sở dữ liệu dãy: Bảng 1. Cơ sở dữ liệu dãy SDB SID Dãy dữ liệu 1 <a(abc)(ac)d(cf)> 2 <(ad)c(bc)(ae)> 3 <(ef)(ab)(df)cb> 4 <eg(af)cbc> 1. Dãy con Cho 2 dãy dữ liệu α=< a1 a2 … an > và β=< b1 b2 … bm >. α được gọi là Dãy con của β (α⊆ β), nếu tồn tại một dãy số nguyên 1≤ j1 < j2 <…< jn ≤m sao cho a1 ⊆ bj1, a2 ⊆ bj2,…, an ⊆ bjn 10 luan an β được gọi là Dãy chứa α Ví dụ.

Độ hỗ trợ của một dãy Cho một CSDL dãy SDB có M bản ghi. Số lượng các bản ghi trong SDB có chứa dãy Sa được gọi là số hỗ trợ (support count- SC) của dãy Sa. Ký hiệu là SC(Sa). Tỉ lệ các bản ghi trong SDB chứa Sa được gọi là độ hỗ trợ của Sa , ký hiệu là support (Sa) Ta có: SC(Sa ) support(Sa) = M 1.

Mẫu dãy thường xuyên Cho một CSDL dãy SDB có M bản ghi và một ngưỡng độ hỗ trợ tối thiểu minsup. Sa được gọi là mẫu dãy thường xuyên nếu : support(Sa) ≥ minsup 1. Luật dãy trong khai phá dữ liệu Trong khai phá dữ liệu, tìm hiểu luật dãy là một phương pháp nghiên cứu rất hiệu quả và thường xuyên được sử dụng trong việc tìm ra những mối liên kết thú vị giữa các biến số trong những CSDL lớn. Các luật liên kết chặt chẽ (strong rule) tìm được trong CSDL được ứng dụng trong rất nhiều lĩnh vực khác nhau.

Ví dụ như : - Thu thập các loại mặt hàng mà người dùng thường mua cùng với nhau. - Thu thập các trang web mà người dùng thường truy cập cùng nhau. - Thu thập thông tin mặt hàng sẽ được mua tiếp theo sau khi đã mua mặt hàng nào đó. Luật dãy X=>Y là một quan hệ giữa 2 tập mục X và Y với X,Y  I sao cho X∩Y = Ø và X,Y ≠ Ø.

Ý nghĩa của luật X=>Y là nếu một tập mục X xuất hiện trong một dãy Sx nào đó thì các mục trong Y cũng xuất hiện sau đó trong dãy này (Sx). 11 luan an Quá trình khai phá luật dãy cũng được chia ra làm 2 bước: - Bước thứ nhất, tìm tất cả các mẫu dãy thường xuyên thỏa mãn ngưỡng hỗ trợ tối thiểu. - Bước hai, sinh luật dựa trên các mẫu dãy thường xuyên tìm được thỏa mãn ngưỡng tin cậy tối thiểu. Bài toán khai phá mẫu dãy thường xuyên Cho CSDL dãy SDB.

Cho trước một ngưỡng hỗ trợ tối thiểu minsup. Tìm tất cả các mẫu dãy thường xuyên trong SDB, tức là tìm tập L: 𝐿 = {𝑆𝑎 ⊆ 𝑆 |𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝑆𝑎 ) ≥ 𝑚𝑖𝑛𝑠𝑢𝑝} Với các khái niệm trên, bài toán khai phá mẫu dãy thường xuyên có thể chia thành 2 bài toán nhỏ: Tìm mẫu dãy ứng viên và tìm mẫy dãy thường xuyên. Mẫu dãy ứng viên được sinh ra trong quá trình duyệt cơ sở dữ liệu, mẫu dãy thường xuyên được tìm ra sau khi tính độ hỗ trợ của mẫu dãy ứng viên. Các mẫu dãy ứng viên có độ hỗ trợ lớn hơn ngưỡng hỗ trợ tối thiểu cho trước sẽ trở thành các mẫu dãy thường xuyên.

Mẫu dãy thường xuyên có trọng số Các thuật toán khai phá mẫu dãy thường xuyên không quan tâm tới mức độ quan trọng của từng mẫu (trọng số của mẫu). Tuy nhiên trên thực tế, mỗi mẫu dữ liệu đều có độ quan trọng khác nhau. Trọng tâm chính đối với khai phá mẫu dãy thường xuyên với trọng số là xây dựng giải thuật nhằm đảm bảo tính chất phản đơn điệu (downward closure property).