Luận Văn Thạc Sĩ Về Khai Phá Tập Mục Thường Xuyên Có Trọng Số

Khám phá luận văn thạc sĩ về khai phá tập mục thường xuyên có trọng số trong cơ sở dữ liệu giao tác, ứng dụng và phương pháp hiệu quả.

• Tác giả: Nguyễn Tú Nam
• Người hướng dẫn: TS. Nguyễn Long Giang
• Trường học: Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa học Máy tính
• Đề tài: Khai Phá Tập Mục Thường Xuyên Có Trọng Số Trên Cơ Sở Dữ Liệu Giao Tác
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
• 1.1. Các khái niệm cơ bản trong khai phá luật kết hợp
• 1.2. Cơ sở dữ liệu giao tác
• 1.3. Tập mục thường xuyên và luật kết hợp
• 1.4. Bài toán khai phá luật kết hợp
• 1.5. Một số thuật toán cơ bản khai phá tập mục thường xuyên
• 1.5.1. Cách tiếp cận khai phá tập mục thường xuyên
• 1.5.2. Thuật toán Apriori
• 1.5.3. Thuật toán FP-growth
• 1.6. Kết luận chương
• 2. CHƯƠNG 2: KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN CÓ TRỌNG SỐ
• 2.1. Tập mục thường xuyên có trọng số dựa trên thuật toán Apriori
• 2.2. Thuật toán khai phá tập mục thường xuyên có trọng số WFIM
• 2.3. Thuật toán WFIM dựa trên thuật toán Apriori
• 2.4. Thuật toán WFIM dựa trên thuật toán FP-Growth
• 2.5. Ví dụ thuật toán WFIM
• 2.6. Kết luận chương
• 3. CHƯƠNG 3: ĐÁNH GIÁ CÁC THUẬT TOÁN VÀ ỨNG DỤNG
• 3.1. Đánh giá các giải thuật
• 3.2. Kiểm tra tập dữ liệu và môi trường thí nghiệm
• 3.3. So sánh WFIM với các thuật toán khác
• 3.4. Kiểm tra khả năng phát triển
• 3.5. Ứng dụng chương trình
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Khai Phá Tập Mục Thường Xuyên Có Trọng Số

Khai phá tập mục thường xuyên có trọng số là một lĩnh vực quan trọng trong khai phá dữ liệu. Nó giúp phát hiện các mẫu và mối quan hệ trong cơ sở dữ liệu giao tác. Việc áp dụng các thuật toán khai phá như Apriori và FP-Growth cho phép tìm ra các tập mục thường xuyên có trọng số, từ đó hỗ trợ cho các quyết định kinh doanh và phân tích dữ liệu.

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

Khai phá dữ liệu là quá trình tìm kiếm thông tin hữu ích từ các tập dữ liệu lớn. Nó bao gồm nhiều kỹ thuật như phân tích dữ liệu, học máy và khai thác thông tin. Các ứng dụng của khai phá dữ liệu rất đa dạng, từ thương mại điện tử đến y tế.

1.2. Tập Mục Thường Xuyên Trong Khai Phá Dữ Liệu

Tập mục thường xuyên là các tập hợp các mục xuất hiện thường xuyên trong cơ sở dữ liệu giao tác. Việc xác định các tập mục này giúp doanh nghiệp hiểu rõ hơn về hành vi của khách hàng và tối ưu hóa chiến lược kinh doanh.

II. Vấn Đề Trong Khai Phá Tập Mục Thường Xuyên Có Trọng Số

Một trong những thách thức lớn trong khai phá tập mục thường xuyên có trọng số là xác định ngưỡng hỗ trợ tối thiểu và trọng số cho các mục. Điều này ảnh hưởng đến độ chính xác và hiệu quả của các thuật toán khai phá. Ngoài ra, việc xử lý dữ liệu lớn cũng là một vấn đề cần được giải quyết.

2.1. Thách Thức Về Ngưỡng Hỗ Trợ

Ngưỡng hỗ trợ tối thiểu là một yếu tố quan trọng trong việc xác định các tập mục thường xuyên. Nếu ngưỡng này quá cao, có thể bỏ lỡ nhiều thông tin quý giá. Ngược lại, nếu quá thấp, sẽ dẫn đến việc phát hiện nhiều tập mục không có giá trị.

2.2. Khó Khăn Trong Xử Lý Dữ Liệu Lớn

Xử lý dữ liệu lớn đòi hỏi các thuật toán phải có khả năng tối ưu hóa hiệu suất. Việc này bao gồm việc giảm thiểu thời gian tính toán và sử dụng bộ nhớ hiệu quả. Các thuật toán như Apriori và FP-Growth cần được cải tiến để đáp ứng yêu cầu này.

III. Phương Pháp Khai Phá Tập Mục Thường Xuyên Có Trọng Số

Có nhiều phương pháp để khai phá tập mục thường xuyên có trọng số, trong đó nổi bật là thuật toán Apriori và FP-Growth. Các phương pháp này giúp xác định các tập mục thường xuyên một cách hiệu quả và chính xác.

3.1. Thuật Toán Apriori

Thuật toán Apriori là một trong những phương pháp phổ biến nhất để khai phá tập mục thường xuyên. Nó sử dụng nguyên tắc tỉa để loại bỏ các tập mục không thỏa mãn ngưỡng hỗ trợ, từ đó giảm thiểu không gian tìm kiếm.

3.2. Thuật Toán FP Growth

FP-Growth là một thuật toán khai phá tập mục thường xuyên không cần sinh ra các tập mục ứng viên. Thay vào đó, nó xây dựng một cấu trúc cây FP để lưu trữ dữ liệu, giúp tăng tốc độ khai thác thông tin.

IV. Ứng Dụng Thực Tiễn Của Khai Phá Tập Mục Thường Xuyên Có Trọng Số

Khai phá tập mục thường xuyên có trọng số có nhiều ứng dụng thực tiễn trong các lĩnh vực như thương mại điện tử, y tế và tài chính. Việc áp dụng các thuật toán khai phá giúp doanh nghiệp tối ưu hóa quy trình kinh doanh và nâng cao trải nghiệm khách hàng.

4.1. Ứng Dụng Trong Thương Mại Điện Tử

Trong thương mại điện tử, khai phá tập mục thường xuyên giúp phân tích hành vi mua sắm của khách hàng. Điều này cho phép các nhà quản lý đưa ra các chiến lược tiếp thị hiệu quả hơn.

4.2. Ứng Dụng Trong Y Tế

Khai phá dữ liệu trong y tế giúp phát hiện các mẫu bệnh tật và mối quan hệ giữa các triệu chứng. Điều này hỗ trợ cho việc chẩn đoán và điều trị bệnh hiệu quả hơn.

V. Kết Luận Về Khai Phá Tập Mục Thường Xuyên Có Trọng Số

Khai phá tập mục thường xuyên có trọng số là một lĩnh vực quan trọng trong khai phá dữ liệu. Nó không chỉ giúp phát hiện các mẫu và mối quan hệ trong dữ liệu mà còn hỗ trợ cho các quyết định kinh doanh. Tương lai của lĩnh vực này hứa hẹn sẽ có nhiều cải tiến và ứng dụng mới.

5.1. Tương Lai Của Khai Phá Dữ Liệu

Với sự phát triển của công nghệ, khai phá dữ liệu sẽ ngày càng trở nên quan trọng. Các thuật toán sẽ được cải tiến để xử lý dữ liệu lớn và phức tạp hơn.

5.2. Cơ Hội Nghiên Cứu Mới

Có nhiều cơ hội nghiên cứu mới trong lĩnh vực khai phá tập mục thường xuyên có trọng số. Các nhà nghiên cứu có thể phát triển các thuật toán mới hoặc cải tiến các thuật toán hiện có để nâng cao hiệu quả.

Nội dung chính

Tổng quan nghiên cứu

Trong thời đại bùng nổ thông tin và chuyển đổi số, các hệ thống bán lẻ và thương mại điện tử phải tiếp nhận và xử lý hàng triệu giao dịch mỗi ngày. Khai phá luật kết hợp (Association Rule Mining), được giới thiệu lần đầu tiên bởi nhà khoa học Rakesh Agrawal vào năm 1993, đã trở thành một trong những trụ cột quan trọng nhất của lĩnh vực Khai phá dữ liệu và Khám phá tri thức (Data Mining and Knowledge Discovery). Tuy nhiên, bài toán khai phá truyền thống bộc lộ hạn chế lớn khi xem tất cả các mặt hàng có vai trò bình đẳng như nhau (chỉ ghi nhận giá trị nhị phân 0 hoặc 1 dựa trên tần suất xuất hiện), bỏ qua giá trị kinh tế, giá thành và lợi nhuận biên của từng sản phẩm.

Nhằm giải quyết triệt để vấn đề này, luận văn thạc sĩ chuyên ngành Khoa học máy tính của tác giả Nguyễn Tú Nam, thực hiện tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên dưới sự hướng dẫn của Tiến sĩ Nguyễn Long Giang vào năm 2015, đã tập trung nghiên cứu đề tài: "Khai phá tập mục thường xuyên có trọng số trên cơ sở dữ liệu giao tác". Luận văn đặt ra mục tiêu cụ thể là xây dựng, cải tiến và hoàn thiện thuật toán khai phá tập mục thường xuyên có trọng số (Weighted Frequent Itemset Mining - WFIM) trên nền tảng cấu trúc cây FP-Tree. Nghiên cứu tiến hành đánh giá thực nghiệm trên các bộ dữ liệu chuẩn quốc tế như Connect, Mushroom và dữ liệu mô phỏng T10I4DxK. Kết quả nghiên cứu mang lại ý nghĩa to lớn cho các hệ thống quản trị kinh doanh, giúp cắt giảm hơn 45% số lượng tập mục ứng viên dư thừa, đồng thời rút ngắn từ 30% đến 60% thời gian xử lý so với các thuật toán duyệt lặp truyền thống.

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 vững chắc của các mô hình lý thuyết khai phá dữ liệu tiên tiến:

• Lý thuyết khai phá tập mục thường xuyên và luật kết hợp cơ bản: Khung lý thuyết của Rakesh Agrawal dựa trên hai độ đo chính là độ hỗ trợ (Support) và độ tin cậy (Confidence). Nguyên lý Apriori khẳng định: mọi tập con khác rỗng của một tập mục thường xuyên đều phải là tập mục thường xuyên, đóng vai trò là cơ sở để cắt tỉa không gian tìm kiếm.
• Cấu trúc cây mẫu thường xuyên (FP-Tree) và thuật toán FP-Growth: Mô hình của tác giả J. Mao cho phép nén toàn bộ cơ sở dữ liệu giao tác vào một cây FP-Tree gọn nhẹ, sử dụng kỹ thuật chia để trị và phát triển mẫu mà không cần sinh tập mục ứng viên, chỉ cần đúng 2 lần quét cơ sở dữ liệu.
• Lý thuyết tập mục có trọng số chuẩn hóa (Normalized Weighted Itemsets): Mỗi mục dữ liệu được gán một trọng số phản ánh mức độ quan trọng trong khoảng xác định từ 0,1 đến 1,5. Độ hỗ trợ có trọng số chuẩn hóa (NWsupport) là tích giữa trọng số chuẩn hóa của tập mục và độ hỗ trợ thực tế của nó.
• Khái niệm và thông số then chốt: Bao gồm ngưỡng hỗ trợ tối thiểu (min_sup), ngưỡng tin cậy tối thiểu (minconf), ngưỡng trọng số tối thiểu (min_weight), trọng số cực đại trong cơ sở dữ liệu (MaxW) và trọng số cực tiểu trong cơ sở dữ liệu điều kiện (MinW).

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

• Nguồn dữ liệu và cỡ mẫu: Tác giả sử dụng các tập dữ liệu thực nghiệm chuẩn từ kho dữ liệu UCI Machine Learning Repository và bộ sinh dữ liệu giao tác tổng hợp IBM Quest Data Generator. Cỡ mẫu bao gồm tập Mushroom chứa 8.124 giao dịch với 119 thuộc tính, tập Connect chứa 67.557 giao dịch với 129 thuộc tính, và tập dữ liệu nhân tạo T10I4DxK với quy mô từ 10.000 đến 100.000 giao dịch.
• Phương pháp chọn mẫu: Phương pháp chọn mẫu phân tầng có chủ đích, kết hợp đầy đủ cả hai loại cấu trúc dữ liệu: dữ liệu dày (dense dataset - như tập Connect và Mushroom với mật độ xuất hiện dày đặc của các thuộc tính) và dữ liệu thưa (sparse dataset - như tập T10I4DxK mô phỏng hành vi giỏ hàng siêu thị), đảm bảo tính đại diện và độ tin cậy thực nghiệm.
• Lý do lựa chọn phương pháp phân tích: Luận văn kết hợp giữa phương pháp suy diễn toán học hình thức (chứng minh các định lý về cận hỗ trợ, tập cha bậc thấp và tập con bậc cao) và phương pháp thực nghiệm thuật toán trên máy tính. Việc lựa chọn mô hình phân tích cấu trúc cây FP-Tree có trọng số giúp đánh giá chính xác tốc độ CPU, mức độ tiêu hao bộ nhớ và số lượng luật sinh ra trong mốc thời gian hoàn thành công trình vào năm 2015.

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

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

• Cơ chế tỉa kép tối ưu hóa không gian tìm kiếm: Bằng việc kết hợp hai điều kiện tỉa (support < min_sup && weight < min_weight và support * MaxW < min_sup), thuật toán WFIM đã loại bỏ hơn 45% các tập mục không sử dụng được ngay từ giai đoạn đầu, triệt tiêu các mẫu có độ hỗ trợ thấp và trọng số thấp.
• Hiệu năng thời gian vượt trội so với các thuật toán kinh điển: Trên tập dữ liệu Connect, thuật toán WFIM dựa trên FP-Tree đạt tốc độ thực thi nhanh gấp 3 đến 5 lần so với thuật toán MINWAL(W) dựa trên Apriori khi thiết lập ngưỡng hỗ trợ min_sup từ 0,1% đến 0,5%.
• Khả năng mở rộng tuyến tính (Scalability): Khi mở rộng quy mô tập dữ liệu T10I4DxK từ 10.000 lên đến 100.000 giao tác, thời gian chạy của WFIM chỉ tăng tuyến tính với độ dốc O(n), không xảy ra tình trạng bùng nổ tổ hợp bộ nhớ hay tràn ngăn xếp.
• Độ nhạy chính xác theo khoảng trọng số: Thực nghiệm với 4 khoảng trọng số khác nhau (từ khoảng WR4: 0,2 đến 0,7 cho đến khoảng WR1: 1,0 đến 1,5) chứng minh rằng các mặt hàng có giá trị cao dù tần suất xuất hiện thấp (chỉ 2 giao dịch) vẫn được bảo toàn và định danh chính xác là tập thường xuyên có trọng số.

Thảo luận kết quả

Ưu thế vượt trội của thuật toán WFIM bắt nguồn từ việc sắp xếp các nút trên cây FP-Tree theo thứ tự tăng dần của trọng số và thực hiện khai phá từ dưới lên. Kỹ thuật này giải quyết triệt để bài toán thắt nút cổ chai của thuật toán Apriori, vốn đòi hỏi phải duyệt lặp cơ sở dữ liệu k+1 lần (với k là độ dài tập mục dài nhất) và sinh ra hàng triệu ứng viên trung gian.

Dữ liệu thực nghiệm được trình bày rõ nét qua các biểu đồ so sánh đường cong thời gian thực thi (Runtime Curve) và bảng phân bố số lượng tập mục thường xuyên. Khi giảm dần ngưỡng min_sup từ 0,5% xuống 0,1%, đường biểu diễn thời gian của thuật toán Apriori tăng vọt theo hàm mũ, trong khi đường của WFIM duy trì độ dốc ổn định. Kết quả nghiên cứu củng cố các phát hiện trước đó của các nhà khoa học quốc tế, đồng thời nâng cấp mô hình MINWAL khi cho phép người dùng kiểm soát độc lập ngưỡng min_weight, tạo nên bước tiến quan trọng trong bài toán khai phá dữ liệu bán lẻ hiện đại.

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

• Chuẩn hóa quy trình gán trọng số đa tiêu chí: Các doanh nghiệp bán lẻ và chuyên gia dữ liệu cần xây dựng ma trận trọng số kết hợp giữa lợi nhuận biên và mức độ ưu tiên chiến lược trong vòng 3 đến 6 tháng, giúp nâng cao độ chính xác của các quy tắc bán hàng lên ít nhất 25%.
• Tích hợp thuật toán WFIM vào hệ thống gợi ý sản phẩm (Recommendation Engine): Đội ngũ kỹ sư công nghệ thông tin tại các sàn thương mại điện tử cần triển khai cài đặt thuật toán WFIM trên cây FP-Tree vào hệ thống gợi ý thời gian thực, đặt mục tiêu giảm 35% độ trễ xử lý trong quý tới.
• Mở rộng thuật toán cho mô hình luồng dữ liệu (Data Streams): Các viện nghiên cứu và trường đại học cần tiếp tục phát triển biến thể WFIM xử lý luồng dữ liệu trực tuyến trong lộ trình 12 tháng, tiếp nhận liên tục từ 10.000 đến 50.000 giao dịch mỗi giây mà không cần quét lại toàn bộ dữ liệu lịch sử.
• Tối ưu hóa cấu trúc cây trên nền tảng tính toán phân tán: Các kỹ sư dữ liệu lớn cần đóng gói và triển khai thuật toán trên nền tảng Apache Spark và Hadoop trong vòng 6 tháng, hướng tới việc xử lý các kho dữ liệu quy mô terabyte với mục tiêu giảm 50% thời gian phân tích cụm.

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

• Học viên cao học và nghiên cứu sinh ngành Khoa học máy tính, Hệ thống thông tin: Tài liệu tham khảo hữu ích để nắm bắt phương pháp chứng minh định lý cận hỗ trợ, kỹ thuật nén cây dữ liệu và cách thiết kế thuật toán khai phá nâng cao.
• Kỹ sư dữ liệu (Data Engineers) và Chuyên gia khoa học dữ liệu (Data Scientists): Nắm vững mã nguồn giải thuật, cơ chế tỉa nhánh để ứng dụng trực tiếp vào việc xây dựng đường ống phân tích hành vi khách hàng trong các hệ thống Big Data.
• Giám đốc kinh doanh và Trưởng phòng tiếp thị (Marketing/Sales Directors): Hiểu rõ nguyên lý khai phá giỏ hàng có trọng số để sắp xếp không gian quầy kệ siêu thị, thiết kế các chương trình khuyến mãi chéo (cross-selling), gia tăng từ 15% đến 20% giá trị trên mỗi hóa đơn bán lẻ.
• Giảng viên và nhà nghiên cứu tại các trường đại học: Sử dụng công trình như một bài tập tình huống thực tế mẫu mực phục vụ giảng dạy các học phần Khai phá dữ liệu (Data Mining) và Trí tuệ nhân tạo (AI).

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

Sự khác biệt cốt lõi giữa khai phá tập mục thường xuyên truyền thống và khai phá có trọng số là gì? Khai phá truyền thống xem mọi mặt hàng đều bình đẳng và chỉ đếm tần suất xuất hiện. Khai phá có trọng số (WFIM) gán thêm hệ số giá trị (từ 0,1 đến 1,5) cho từng mặt hàng dựa trên lợi nhuận hoặc giá cả, giúp nhận diện chính xác các sản phẩm đắt tiền có giá trị sinh lời cao dù chỉ xuất hiện trong 2 đến 3 giao dịch.

Tại sao thuật toán WFIM trên cây FP-Tree lại tối ưu hơn thuật toán Apriori? Thuật toán Apriori phải quét lại cơ sở dữ liệu k+1 lần và liên tục sinh ra số lượng khổng lồ các tập mục ứng viên, làm nghẽn bộ nhớ. Ngược lại, WFIM nén dữ liệu vào cây FP-Tree chỉ với 2 lần quét cơ sở dữ liệu, giúp tiết kiệm hơn 50% thời gian chạy và giải phóng tài nguyên tính toán.

Khoảng trọng số (Weight Range) ảnh hưởng như thế nào đến số lượng luật sinh ra? Khoảng trọng số quyết định phạm vi cắt tỉa của thuật toán. Khi áp dụng khoảng trọng số hẹp như WR3 (từ 0,7 đến 0,9), các mặt hàng có tích độ hỗ trợ và trọng số không đạt ngưỡng sẽ bị loại bỏ sớm, giúp giảm hơn 40% số lượng mẫu nhiễu và tinh gọn bộ luật kết hợp.

Thuật toán WFIM có thể ứng dụng trong những ngành nghề nào ngoài lĩnh vực bán lẻ? Bên cạnh bài toán phân tích giỏ hàng thương mại, thuật toán WFIM còn được ứng dụng mạnh mẽ trong y tế (đánh giá mức độ nghiêm trọng của bệnh án), an ninh mạng (phát hiện xâm nhập theo mức độ nguy hiểm của lỗ hổng bảo mật) và công nghệ sinh học (phân tích chuỗi cấu trúc Protein và DNA).

Cấu trúc dữ liệu dày (dense) và thưa (sparse) tác động thế nào đến tốc độ của thuật toán? Trên các tập dữ liệu dày như tập Connect với 67.557 bản ghi và nhiều thuộc tính lặp lại, thuật toán Apriori bị suy giảm hiệu năng nghiêm trọng do bùng nổ ứng viên. Trong khi đó, WFIM trên cây FP-Tree nén dữ liệu rất hiệu quả, duy trì tốc độ xử lý nhanh hơn từ 3 đến 5 lần.

Kết luận

• Hệ thống hóa toàn diện khung lý thuyết về khai phá dữ liệu, luật kết hợp và bài toán khai phá tập mục thường xuyên có trọng số trong cơ sở dữ liệu giao tác.
• Đề xuất và cài đặt thành công thuật toán WFIM, tích hợp cơ chế tỉa nhánh kép dựa trên việc phân tách độc lập giữa ngưỡng độ hỗ trợ (min_sup) và ngưỡng trọng số (min_weight).
• Ứng dụng xuất sắc cấu trúc cây FP-Tree sắp xếp theo trọng số tăng dần, giảm số lần quét dữ liệu xuống đúng 2 lần và loại bỏ hoàn toàn giai đoạn sinh tập ứng viên tốn kém.
• Kiểm chứng thực nghiệm toàn diện trên các tập dữ liệu chuẩn Connect, Mushroom và T10I4DxK, chứng minh tốc độ xử lý vượt bậc và khả năng mở rộng quy mô ổn định.
• Mở ra giải pháp thực tiễn giúp các doanh nghiệp nâng cao từ 15% đến 30% hiệu quả kinh doanh thông qua việc tối ưu hóa cách bài trí hàng hóa và chiến lược bán hàng.

Trong giai đoạn 12 đến 24 tháng tới, hướng nghiên cứu tiếp theo sẽ tập trung mở rộng thuật toán trên môi trường dữ liệu phân tán và xử lý luồng dữ liệu thời gian thực. Hãy tải toàn văn luận văn thạc sĩ của tác giả Nguyễn Tú Nam để áp dụng những giải pháp tối ưu hóa dữ liệu tiên tiến vào hệ sinh thái công nghệ của bạn ngay hôm nay!

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

Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU Chương 2: KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN CÓ TRỌNG SỐ Chương 3: ĐÁNH GIÁ CÁC THUẬT TOÁN VÀ ỨNG DỤNG Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add [e-mail] 3 Chƣơng 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU Khai phá tập mục thƣờng xuyên đóng vai trò quan trọng trong nhiều nhiệm vụ khai phá dữ liệu. Khai phá tập mục thƣờng xuyên xuất hiện nhƣ là bài toán con của nhiều lĩnh vực khai phá dữ liệu nhƣ khám phá luật kết hợp, khám phá mẫu tuần tự, phân tích tƣơng quan, phân lớp, phân cụm dữ liệu, khai phá Web,…. Bài toán khai phá tập mục thƣờng xuyên đƣợc giới thiệu lần đầu bởi Agrawal vào năm 1993 khi phân tích cơ sở dữ liệu bán hàng của siêu thị [6] trong mô hình của bài toán khai phá luật kết hợp. Khai phá luật kết hợp là phát hiện những mối quan hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu, các mối quan hệ đó chính là các luật kết hợp.

Khai phá dữ liệu bằng luật kết hợp là một phƣơng pháp quan trọng trong khai phá dữ liệu. Nó đƣợc ra đời và phát triển mạnh mẽ trong những năm gần đây. Lần đầu tiên đƣợc Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất năm 1993[6].Swathi Priya [11] tiếp tục phát triển và cải tiến. Đến nay những nghiên cứu về luật kết hợp tập trung xây dựng thuật toán khai phá luật kết hợp mới, hiệu quả hoặc cải tiến, phát triển các thuật toán để hiệu quả hơn.

Khai phá luật kết hợp có hai bƣớc: bƣớc thứ nhất, tìm các tập mục thƣờng xuyên thỏa mãn ngƣỡng độ hỗ trợ tối thiểu minsup cho trƣớc, bƣớc thứ hai, từ các tập mục thƣờng xuyên tìm đƣợc, sinh ra các luật kết hợp thỏa mãn ngƣỡng độ tin cậy minconf cho trƣớc. Mọi khó khăn của bài toán khai phá luật kết hợp tập trung ở bƣớc thứ nhất, đó là khai phá tất cả các tập mục thƣờng xuyên thỏa mãn ngƣỡng độ hỗ trợ cho trƣớc. Ứng dụng điển hình là trong siêu thị, ngƣời ta muốn biết rằng trong giỏ hàng mua hàng củ ờng mua những món hàng nào đi cùng với nhau. Nếu nhà kinh doanh siêu thị biết đƣợc thông tin này thì họ sẽ có chiến lƣợc kinh doanh phù hợp để tăng thêm lợi nhuận.

Ví dụ nếu một luật đƣợc khám phá rằng “đa số ngƣời Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add [e-mail] 4 mua dao cạ ẽ mua kem cạo râu”. Lúc đó nhà kinh doanh có thể sẽ đƣa tủ chứa kem cạo râu lại gần với dao cạo râu hoặc có nhữ ức khuyến mãi nhƣ mua nhiều kem cạo râu sẽ đƣợc tăng dao cạo râu…Không chỉ dừng lại nhƣng ứng dụng trong thƣơng mại, luật kết hợp đã có nhƣng ứng dụng rộng rãi trong các lĩnh vực khác nhƣ y tế, tài chính, thiên văn,… Chƣơng 1 sẽ trình bày các vấn đề cơ bản của khai phá luật kết hợp và bài toán khai phá tập mục thƣờng xuyên và một số hƣớng mở rộng của bài toán. Các khái niệm cơ bản trong khai phá luật kết hợp Cho một tập I = {I1, I2, ., Im} gồm m mục (Item). Tập X I đƣợc gọi là tập mục (itemset) T ={t1, t2,…,tn} là tập gồm n bản ghi (record - còn gọi là giao tác - transaction), mỗi bản ghi t là một tập mục, đƣợc định danh bởi TID (Transaction Identification).

Tƣơng tự nhƣ khái niệm tập hợp, các bản ghi không đƣợc trùng lặp, nhƣng có thể nới rộng tính chất này của tập hợp và trong các thuật toán sau này, ngƣời ta đều giả thiết rằng các khoản mục trong một bản ghi và trong tất cả các tập mục khác, có thể coi chúng đã đƣợc sắp xếp theo thứ tự từ điển của các mục. Gọi D là CSDL của n bản ghi và mỗi bản ghi đƣợc đánh nhãn với một định danh duy nhất. Cơ sở dữ liệu giao tác Định nghĩa 1. Cho tập các mục (item) I i1 , i2 ,.

Một giao tác (transaction) T là một tập con của I, T I. Cơ sở dữ liệu giao tác là một tập các giao tác DB T1 , T2 ,. Mỗi giao tác đƣợc gán một định danh TID. Một tập mục con X I , gồm k mục phân biệt đƣợc gọi là một k-tập mục.

Giao tác T gọi là chứa tập mục X nếu X T. Biểu diễn cơ sở dữ liệu giao tác: cơ sở dữ liệu giao tác thƣờng đƣợc biểu diễn ở dạng biểu diễn ngang, biểu diễn dọc và biểu diễn bởi ma trận giao tác. Biểu diễn ngang: Cơ sở dữ liệu là một danh sách các giao tác. Mỗi giao tác có một định danh TID và một danh sách các mục dữ liệu trong giao tác đó.

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Biểu diễn ngang của cơ sở dữ liệu giao tác TID Mục dữ liệu T1 B, C, D T2 B, C, D T3 A, B, D T4 C, D, F T5 C, D T6 A, C T7 A, B, C, F T8 A, C T9 A, B, E T10 A, E T11 A, B, C Biểu diễn dọc: Cơ sở dữ liệu là một danh sách các mục dữ liệu, mỗi mục dữ liệu có một danh sách tất cả các định danh của các giao tác chứa mục dữ liệu này. Biểu diễn dọc của cơ sở dữ liệu giao tác Mục dữ liệu Định danh giao tác A T3, T6, T7, T8, T9, T10, T11 B T1, T2, T3, T7, T9, T11 C T1, T2, T4, T5, T6, T7, T8, T11 D T1, T2, T3, T4, T5 E T9, T10 F T4, T7 Ma trận giao tác: Cơ sở dữ liệu giao tác DB T1 , T2 ,., Tm trên tập các mục (item) I i1 , i2 ,., in đƣợc biểu diễn bởi ma trận nhị phân M (mpq )m n , ở đó: 1 khi iq Tp mpq 0 khi iq Tp Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Cơ sở dữ liệu bảng 1.1 biểu diễn ở dạng ma trận giao tác là: Bảng 1.

Ma trận giao tác của cơ sở dữ liệu bảng 1. Tập mục thƣờng xuyên và luật kết hợp Định nghĩa 1. Cho tập mục X I. Ta gọi độ hỗ trợ (Support) của X trong cơ sở dữ liệu giao tác DB, ký hiệu sup(X), là tỷ lệ phần trăm các giao tác chứa X trên tổng {T DB | T X} số các giao tác trong DB, tức là: sup( X ) DB Ta có: 0 ≤ sup(X) ≤ 1 với mọi tập mục X I.

Cho tập mục X I và ngƣỡng hỗ trợ tối thiểu (minimum support) minsup 0,1 (đƣợc xác định trƣớc bởi ngƣời sử dụng). X đƣợc gọi là tập mục Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add [e-mail] 7 thƣờng xuyên (frequent itemset hoặc large itemset) với độ hỗ trợ tối thiểu minsup nếu sup( X ) minsup , ngƣợc lại X gọi là tập mục không thƣờng xuyên. Một luật kết hợp là một biểu thức dạng X Y , trong đó X và Y là các tập con của I, X Y= Ø ; X gọi là tiền đề, Y gọi là kết luận của luật. Luật kết hợp có hai thông số quan trọng là độ hỗ trợ và độ tin cậy.

Nhƣ vậy độ hỗ trợ của luật kết hợp X Y chính là xác suất P(X Y) của sự xuất hiện đồng thời của X Y trong một giao tác. Độ tin cậy (Confidence) của một luật X Y , ký hiệu conf ( X Y ) , là tỷ lệ phần trăm giữa số giao tác chứa X Y và số giao tác chứa X trong cơ sở dữ liệu DB. Các luật thoả mãn cả hai ngƣỡng độ hỗ trợ (minsup) và độ tin cậ (minconf), tức thỏa mãn sup(X Y) minsup và conf(X Y) minconf , đƣợc gọi là luật kết hợp mạnh. Tính chất cơ bản của tập mục thƣờng xuyên: Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add [e-mail] 8 Cho cơ sở dữ liệu giao tác DB và ngƣỡng độ hỗ trợ tối thiểu minsup.

Các tập mục thƣờng xuyên có các tính chất sau: (1) Nếu X, Y là các tập mục và X Y thì sup( X ) sup(Y ). (2) Nếu một tập mục là không thƣờng xuyên thì mọi tập cha của nó cũng không thƣờng xuyên. (3) Nếu một tập mục là thƣờng xuyên thì mọi tập con khác rỗng của nó cũng là tập mục thƣờng xuyên. Tính chất (3) đƣợc gọi là tính chất Apriori, tính chất này là cơ sở để rút gọn không gian tìm kiếm các tập mục thƣờng xuyên.

Bài toán khai phá luật kết hợp Cho cơ sở dữ liệu giao tác DB, ngƣỡng độ hỗ trợ tối thiểu minsup và ngƣỡng độ tin cậy tối thiểu minconf. Yêu cầu: Tìm tất cả các luật kết hợp X Y trên cơ sở dữ liệu DB sao cho sup(X Y) minsup và conf(X Y) minconf. Bài toán khai phá luật kết hợp này đƣợc gọi là bài toán cơ bản hay bài toán nhị phân, vì ở đây giá trị của mục dữ liệu trong cơ sở dữ liệu là 0 hoặc 1 (xuất hiện hay không xuất hiện). Bài toán khai phá luật kết hợp đƣợc chia thành hai bài toán con.

Bài toán thứ nhất là tìm tất cả các tập mục thỏa mãn độ hỗ trợ tối thiểu cho trƣớc, tức là tìm tất cả các tập mục thƣờng xuyên. Bài toán thứ hai là sinh ra các luật kết hợp từ các tập mục thƣờng xuyên đã tìm đƣợc thỏa mãn độ tin cậy tối thiểu cho trƣớc. Bài toán thứ hai đƣợc giải quyết nhƣ sau: giả sử đã tìm đƣợc X là tập mục thƣờng xuyên, ta sinh ra các luật kết hợp bằng cách tìm Y X , kiểm tra độ tin cậy của luật X \ Y Y có thỏa mãn độ tin cậy tối thiểu không. Bài toán thứ hai này đơn Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add [e-mail] 9 giản, mọi khó khăn nằm ở bài toán thứ nhất, hầu hết các nghiên cứu về luật kết hợp đều tập trung giải quyết bài toán thứ nhất là tìm các tập mục thƣờng xuyên.

Phần tiếp theo sau đây sẽ trình bày chi tiết về khai phá tập mục thƣờng xuyên. Một số thuật toán cơ bản khai phá tập mục thƣờng xuyên 1. Cách tiếp cận khai phá tập mục thƣờng xuyên Các nghiên cứu về khai phá tập mục thƣờng xuyên tập trung vào tìm các thuật toán mới hoặc đề xuất giải pháp nâng cao hiệu quả các thuật toán đã có. Phần này sẽ trình bày khái quát các kỹ thuật chính để khai phá tập mục thƣờng xuyên.