Nghiên Cứu Khai Phá Dữ Liệu: Phương Pháp và Ứng Dụng

Khám phá tập mục thường xuyên có trọng số trong cơ sở dữ liệu giao tác, tối ưu hóa quy trình phân tích và khai thác dữ liệu 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 Thái Nguyên
• Đề tài: Khai Phá Dữ Liệu: Phương Pháp và Ứng Dụng
• Loại tài liệu: luận văn

Mục lục chi tiết

• LỜI CAM ĐOAN
• Danh mục các ký hiệu, các chữ viết tắt
• Danh mục các bảng
• Danh mục các hình
• MỞ ĐẦU
• 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.1.1. Cơ sở dữ liệu giao tác
• 1.1.2. Tập mục thường xuyên và luật kết hợp
• 1.1.3. Bài toán khai phá luật kết hợp
• 1.2. Một số thuật toán cơ bản khai phá tập mục thường xuyên
• 1.2.1. Cách tiếp cận khai phá tập mục thường xuyên
• 1.2.2. Thuật toán Apriori
• 1.2.3. Thuật toán FP-growth
• 1.3. Một số hướng mở rộng bài toán khai phá tập mục thường xuyên
• 1.4. 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. Thuật toán khai phá tập mục thường xuyên có trọng số MINWAL
• 2.1.1. Các khái niệm cơ bản
• 2.1.2. Thuật toán MINWAL khai phá tập mục thường xuyên có trọng số dựa trên thuật toán Apriori
• 2.1.3. Ví dụ minh họa thuật toán MINWAL
• 2.2. Thuật toán khai phá tập mục thường xuyên có trọng số WFIM
• 2.2.1. Các khái niệm cơ bản
• 2.2.2. Thuật toán WFIM dựa trên thuật toán Apriori
• 2.2.3. Thuật toán WFIM dựa trên thuật toán FP-Growth
• 2.2.4. Ví dụ thuật toán WFIM
• 2.3. 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.1.1. Kiểm tra tập dữ liệu và môi trường thí nghiệm
• 3.1.2. So sánh WFIM với các thuật toán khác
• 3.1.3. Kiểm tra khả năng phát triển
• 3.2. Ứng dụng chương trình
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về Nghiên cứu Khai phá Dữ liệu Khái niệm và Ý nghĩa

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, giúp phát hiện thông tin ẩn trong dữ liệu lớn. Khai phá dữ liệu không chỉ đơn thuần là phân tích dữ liệu mà còn là quá trình tìm kiếm tri thức từ dữ liệu. Các ứng dụng của nó rất đa dạng, từ thương mại điện tử đến y tế, tài chính và nhiều lĩnh vực khác. Việc hiểu rõ về khai phá dữ liệu sẽ giúp các nhà nghiên cứu và doanh nghiệp tối ưu hóa quy trình ra quyết định.

1.1. Khai thác dữ liệu Định nghĩa và các khái niệm cơ bản

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. Các khái niệm cơ bản bao gồm tập mục thường xuyên, luật kết hợp và độ hỗ trợ. Những khái niệm này là nền tảng cho việc phát triển các thuật toán khai phá dữ liệu.

1.2. Tầm quan trọng của khai phá dữ liệu trong doanh nghiệp

Khai phá dữ liệu giúp doanh nghiệp hiểu rõ hơn về hành vi của khách hàng, từ đó đưa ra các chiến lược kinh doanh hiệu quả. Việc phân tích dữ liệu giúp tối ưu hóa quy trình tiếp thị và nâng cao trải nghiệm khách hàng.

II. Những thách thức trong Nghiên cứu Khai phá Dữ liệu hiện nay

Mặc dù khai phá dữ liệu mang lại nhiều lợi ích, nhưng cũng đối mặt với nhiều thách thức. Các vấn đề như chất lượng dữ liệu, tính bảo mật và quyền riêng tư của người dùng là những yếu tố cần được xem xét kỹ lưỡng. Ngoài ra, việc lựa chọn thuật toán phù hợp cũng là một thách thức lớn trong quá trình khai thác dữ liệu.

2.1. Chất lượng dữ liệu và ảnh hưởng đến kết quả khai thác

Chất lượng dữ liệu là yếu tố quyết định đến độ chính xác của các kết quả khai thác. Dữ liệu không chính xác hoặc thiếu sót có thể dẫn đến những quyết định sai lầm trong kinh doanh.

2.2. Bảo mật và quyền riêng tư trong khai phá dữ liệu

Bảo mật dữ liệu và quyền riêng tư của người dùng là vấn đề quan trọng trong khai phá dữ liệu. Các doanh nghiệp cần đảm bảo rằng dữ liệu của khách hàng được bảo vệ và sử dụng một cách hợp pháp.

III. Phương pháp Khai phá Dữ liệu Các thuật toán chính

Có nhiều phương pháp và thuật toán khác nhau trong khai phá dữ liệu, mỗi phương pháp có những ưu điểm và nhược điểm riêng. Các thuật toán phổ biến như Apriori, FP-Growth và Eclat được sử dụng rộng rãi trong việc khai thác tập mục thường xuyên.

3.1. Thuật toán Apriori Nguyên lý và ứng dụng

Thuật toán Apriori là một trong những thuật toán khai phá dữ liệu phổ biến nhất. Nó sử dụng nguyên lý tỉa để loại bỏ các tập mục không thường xuyên, giúp giảm thiểu khối lượng tính toán.

3.2. Thuật toán FP Growth Ưu điểm và cách thức hoạt động

FP-Growth là một thuật toán khai phá dữ liệu hiệu quả hơn so với Apriori, vì nó không cần sinh ra tập mục ứng viên. Thay vào đó, nó xây dựng một cấu trúc cây để khai thác dữ liệu một cách nhanh chóng.

IV. Ứng dụng thực tiễn của Khai phá Dữ liệu trong các lĩnh vực

Khai phá dữ liệu đã được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau, từ thương mại điện tử đến y tế và tài chính. Những ứng dụng này không chỉ giúp cải thiện hiệu quả kinh doanh mà còn nâng cao chất lượng dịch vụ.

4.1. Ứng dụng trong thương mại điện tử Tối ưu hóa trải nghiệm khách hàng

Trong thương mại điện tử, khai phá dữ liệu giúp phân tích hành vi mua sắm của khách hàng, từ đó đưa ra các gợi ý sản phẩm phù hợp và cải thiện trải nghiệm mua sắm.

4.2. Ứng dụng trong y tế Phân tích dữ liệu bệnh nhân

Khai phá dữ liệu trong y tế giúp phân tích dữ liệu bệnh nhân để phát hiện các xu hướng và mô hình, từ đó cải thiện chất lượng chăm sóc sức khỏe.

V. Kết luận Tương lai của Nghiên cứu Khai phá Dữ liệu

Nghiên cứu khai phá dữ liệu đang ngày càng phát triển và mở rộng. Với sự gia tăng của dữ liệu lớn và công nghệ mới, tương lai của khai phá dữ liệu hứa hẹn sẽ mang lại nhiều cơ hội và thách thức mới. Việc áp dụng các công nghệ như trí tuệ nhân tạo và học máy sẽ giúp nâng cao hiệu quả của quá trình khai thác dữ liệu.

5.1. Xu hướng phát triển của khai phá dữ liệu trong tương lai

Các xu hướng như trí tuệ nhân tạo và học máy sẽ tiếp tục định hình tương lai của khai phá dữ liệu, giúp phát hiện thông tin ẩn trong dữ liệu một cách hiệu quả hơn.

5.2. Thách thức và cơ hội trong nghiên cứu khai phá dữ liệu

Mặc dù có nhiều cơ hội, nhưng cũng cần phải đối mặt với các thách thức như bảo mật dữ liệu và chất lượng dữ liệu. Việc giải quyết những vấn đề này sẽ quyết định sự thành công của khai phá dữ liệu trong tương lai.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh bùng nổ dữ liệu số hiện nay, khối lượng giao dịch bán lẻ và thương mại điện tử toàn cầu đang ghi nhận mức tăng trưởng hơn 35% mỗi năm. Theo ước tính từ các báo cáo công nghệ thông tin, hơn 80% các hệ thống bán lẻ hiện đại dựa vào kỹ thuật khai phá luật kết hợp để phân tích giỏ hàng và bố trí không gian trưng bày sản phẩm. Tuy nhiên, các thuật toán khai phá truyền thống thường xem xét mọi mặt hàng có vai trò và giá trị hoàn toàn bình đẳng, dẫn đến hiện tượng sinh ra hàng nghìn luật kết hợp rác nhưng lại bỏ sót những tổ hợp sản phẩm có giá trị kinh tế cốt lõi.

Vấn đề nghiên cứu then chốt mà đề tài giải quyết là khắc phục nhược điểm của các thuật toán khai phá tập mục thường xuyên không trọng số bằng cách gán trọng số phản ánh đúng giá trị và mức độ quan trọng thực tế của từng sản phẩm. Mục tiêu cụ thể của luận văn là nghiên cứu, thiết kế và cài đặt thực nghiệm thuật toán khai phá tập mục thường xuyên có trọng số chuẩn hóa mang tên WFIM dựa trên cấu trúc cây FP-Tree. Nghiên cứu được thực hiện tại Trường Đại học Công nghệ Thông tin và Truyền thông Thái Nguyên trong giai đoạn 2021-2023, tập trung thử nghiệm trên các cơ sở dữ liệu giao tác chuẩn từ kho lưu trữ UCI như Connect, Mushroom và dữ liệu tổng hợp T10I4DxK. Kết quả nghiên cứu mang lại ý nghĩa to lớn khi giúp giảm thiểu từ 45% đến 60% thời gian xử lý tính toán, loại bỏ hơn 50% số lượng ứng viên dư thừa và gia tăng độ chuẩn xác trong việc hỗ trợ ra quyết định kinh doanh lên 25%.

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 dựa trên hai nền tảng lý thuyết cốt lõi trong khoa học máy tính: lý thuyết khai phá luật kết hợp nhị phân do Rakesh Agrawal đề xuất năm 1993 và lý thuyết cấu trúc cây tiền tố nén FP-Tree do J. Mao và Han phát triển năm 2000. Mô hình nghiên cứu của luận văn tập trung vào bài toán mở rộng: Khai phá tập mục thường xuyên có trọng số chuẩn hóa trên cơ sở dữ liệu giao tác.

Khung lý thuyết vận dụng hệ thống 5 khái niệm chuyên ngành nền tảng:

1. Cơ sở dữ liệu giao tác: Tập hợp các bản ghi giao dịch được đánh dấu bằng định danh giao tác duy nhất (TID), biểu diễn dưới dạng ngang, dọc hoặc ma trận nhị phân 0 và 1.
2. Trọng số chuẩn hóa: Tỷ lệ trung bình cộng trọng số của các mục trong một tập mục, phản ánh mức độ ưu tiên kinh tế hoặc ngữ nghĩa của tập dữ liệu.
3. Độ hỗ trợ có trọng số chuẩn hóa: Tích giữa trọng số chuẩn hóa và tần suất xuất hiện thực tế của tập mục trên tổng số giao dịch.
4. Cận k-hỗ trợ: Giá trị chặn dưới ước lượng toán học giúp xác định nhanh khả năng một tập con có thể hình thành tập mục thường xuyên có trọng số bậc cao hơn.
5. Ràng buộc phân khoảng trọng số: Khung giới hạn từ giá trị nhỏ nhất đến giá trị lớn nhất, kết hợp cùng ngưỡng trọng số tối thiểu để kiểm soát chặt chẽ quá trình cắt tỉa không gian tìm kiếm.

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

Luận văn kết hợp chặt chẽ giữa phương pháp nghiên cứu lý thuyết hình thức và phương pháp thực nghiệm thuật toán trên máy tính:

• Nguồn dữ liệu và cỡ mẫu: Thực nghiệm sử dụng 3 bộ dữ liệu chuẩn quốc tế từ kho lưu trữ UCI và IBM Synthetic Dataset. Bộ dữ liệu Mushroom gồm 8.124 giao tác với 119 mục đại diện cho cơ sở dữ liệu dày đặc; bộ dữ liệu Connect gồm 67.557 giao tác với 129 mục; và bộ dữ liệu tổng hợp T10I4DxK với quy mô biến thiên từ 10.000 đến 100.000 giao tác đại diện cho cơ sở dữ liệu giao dịch bán lẻ thưa thớt quy mô lớn. Phương pháp chọn mẫu phân tầng có chủ đích được áp dụng nhằm kiểm tra tính thích ứng của thuật toán trên nhiều dạng phân bố dữ liệu khác nhau.
• Phương pháp phân tích và lý do lựa chọn: Tác giả xây dựng mã nguồn cài đặt các thuật toán Apriori, FP-Growth, MINWAL và WFIM để tiến hành đo lường định lượng các chỉ số hiệu năng gồm: thời gian thực thi (tính bằng giây và mili-giây), mức tiêu hao bộ nhớ chính và số lượng tập mục sinh ra dưới các ngưỡng độ hỗ trợ tối thiểu (từ 0,1% đến 5,0%) cùng 4 khoảng trọng số khác nhau (từ 0,2 đến 1,5). Lý do lựa chọn tiếp cận cấu trúc cây FP-Tree trong thuật toán WFIM là bởi giải pháp này chỉ quét cơ sở dữ liệu đúng 2 lần, nén hoàn toàn dữ liệu vào cây nhớ mà không cần sinh tập ứng viên Ck, giúp giải quyết triệt để bài toán bùng nổ tổ hợp của phương pháp tiếp cận Apriori.
• Timeline nghiên cứu: Toàn bộ quá trình nghiên cứu, thiết kế toán học, lập trình kiểm thử và đánh giá hiệu năng được tiến hành trong chu kỳ 24 tháng liên tục.

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

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

Quá trình phân tích thực nghiệm trên các bộ dữ liệu chuẩn đã ghi nhận 4 phát hiện khoa học quan trọng:

Thứ nhất, thuật toán WFIM thể hiện khả năng cắt tỉa không gian tìm kiếm vượt trội. Trên tập dữ liệu Connect, việc tích hợp điều kiện tỉa kép dựa trên ngưỡng trọng số nhỏ nhất và trọng số lớn nhất giúp giảm từ 52% đến 68% số lượng tập mục ứng viên dư thừa so với thuật toán MINWAL truyền thống.

Thứ hai, thời gian thực thi của thuật toán WFIM đạt hiệu suất cao hơn đáng kể. Khi kiểm thử trên tập dữ liệu Mushroom với ngưỡng hỗ trợ tối thiểu hạ thấp xuống mức 0,1%, WFIM chạy nhanh hơn gấp 3,8 đến 5,2 lần so với thuật toán MINWAL và rút ngắn 43,8% thời gian so với thuật toán FP-Growth không trọng số nhờ việc loại bỏ sớm các nhánh cây chứa mục không thường xuyên có trọng số.

Thứ ba, kiểm tra khả năng phát triển trên tập dữ liệu T10I4DxK cho thấy khi quy mô giao dịch tăng gấp 10 lần từ 10.000 lên 100.000 bản ghi, thời gian xử lý của WFIM chỉ tăng tuyến tính khoảng 2,8 lần, trong khi thuật toán dạng Apriori tăng theo hàm số mũ vượt quá 12 lần và nhanh chóng cạn kiệt tài nguyên bộ nhớ.

Thứ tư, việc thiết lập các khoảng trọng số khác nhau (từ khoảng 1,0-1,5 đến khoảng 0,2-0,7) mang lại tính linh hoạt cao trong việc lọc dữ liệu. Khoảng trọng số thấp giúp loại bỏ ngay từ vòng duyệt đầu tiên hơn 30% các mục rác có độ hỗ trợ thấp và giá trị thấp, giúp tập trung tài nguyên vào các mẫu có giá trị cao.

Thảo luận kết quả

Nguyên nhân căn bản giúp thuật toán WFIM đạt được hiệu năng ấn tượng nằm ở kỹ thuật sắp xếp các mục theo thứ tự trọng số tăng dần trên cây FP-Tree và khai phá theo phương thức từ dưới lên. Khác với độ hỗ trợ luôn giảm dần khi kích thước tập mục tăng, trọng số không có tính chất đơn điệu giảm. Do đó, việc kết hợp ngưỡng trọng số nhỏ nhất cùng hai điều kiện tỉa chặt chẽ đã bảo toàn được tính chặn dưới đóng mà không làm sót bất kỳ tập mục thường xuyên có trọng số nào.

Khi so sánh với các công bố của Rakesh Agrawal (1993) và J. Mao (2000), nghiên cứu này đã khắc phục hoàn toàn sự khiên cưỡng của mô hình đếm tần suất đơn thuần. Đồng thời, so với thuật toán MINWAL vốn phụ thuộc vào việc quét cơ sở dữ liệu nhiều lần, WFIM chỉ duyệt cơ sở dữ liệu đúng 2 lần và xử lý hoàn toàn trên bộ nhớ đệm cây nén.

Về mặt trực quan hóa, toàn bộ dữ liệu thực nghiệm có thể được trình bày rõ nét qua biểu đồ đường biểu diễn thời gian thực thi tương ứng với từng bước biến thiên của ngưỡng hỗ trợ từ 0,1% đến 2,0%, kết hợp cùng bảng đối sánh ma trận giao tác thể hiện số lượng nút cây nén được rút gọn. Ý nghĩa thực tiễn của phát hiện này là cung cấp cho các nhà quản trị một công cụ phân tích sắc bén, giúp nhận diện chính xác các nhóm hàng mang lại biên lợi nhuận cao nhất thay vì chỉ nhìn vào doanh số bán lẻ bề nổi.

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

Dựa trên các kết quả lý thuyết và thực nghiệm đã đạt được, luận văn đưa ra 4 khuyến nghị hành động thiết thực:

1. Triển khai tích hợp thuật toán WFIM vào hệ sinh thái quản trị chuỗi bán lẻ: Các tập đoàn thương mại điện tử và chuỗi siêu thị cần tiến hành nâng cấp hệ thống phân tích giỏ hàng trong vòng 6 tháng tới, tích hợp module khai phá có trọng số vào phần mềm quản trị quan hệ khách hàng (CRM) để nâng cao doanh số bán chéo lên ít nhất 18% đến 22%. Chủ thể thực hiện là bộ phận phân tích dữ liệu và phòng công nghệ thông tin của doanh nghiệp.

2. Xây dựng ma trận trọng số linh hoạt theo biên lợi nhuận danh mục: Bộ phận quản trị kinh doanh và tiếp thị cần phối hợp với phòng tài chính để thiết lập bảng trọng số chuẩn hóa cho toàn bộ danh mục sản phẩm (từ 0,1 đến 2,0) dựa trên biên lợi nhuận ròng, hạn sử dụng và chi phí lưu kho. Kế hoạch này cần hoàn tất trong quý 1 năm tài chính, với mục tiêu cắt giảm 35% lượng hàng tồn kho đối với các mặt hàng cao cấp.

3. Ứng dụng giải thuật vào nền tảng xử lý dữ liệu lớn phân tán: Đội ngũ kỹ sư dữ liệu cần tiến hành chuyển đổi mã nguồn WFIM sang chạy trên các nền tảng tính toán song song như Apache Spark hoặc Hadoop trong lộ trình từ 9 đến 12 tháng. Mục tiêu là xử lý ổn định luồng dữ liệu lớn với quy mô trên 500.000 giao dịch phát sinh mỗi phút, duy trì độ trễ dưới 2 giây.

4. Mở rộng thử nghiệm mô hình trong lĩnh vực y tế và an ninh không gian mạng: Các viện nghiên cứu tin sinh học và trung tâm an toàn thông tin quốc gia nên ứng dụng thuật toán WFIM trong giai đoạn 12 đến 18 tháng tới để phân tích cấu trúc chuỗi gen đột biến hoặc truy vết các mẫu tấn công xâm nhập mạng nguy hiểm, hướng tới nâng tỷ lệ phát hiện sớm các mối đe dọa lên trên 95%.

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

Công trình nghiên cứu mang lại giá trị tham khảo chuyên sâu và tính ứng dụng cao cho 4 nhóm đối tượng cụ thể:

1. Giảng viên, học viên cao học và nghiên cứu sinh ngành Công nghệ thông tin: Tài liệu cung cấp hệ thống chứng minh định lý toán học chặt chẽ, các bước tối ưu hóa cấu trúc dữ liệu cây FP-Tree và phương pháp luận nghiên cứu thực nghiệm chuẩn mực để phát triển các đề tài khai phá tri thức nâng cao.

2. Kỹ sư phân tích dữ liệu và chuyên gia phát triển hệ thống kinh doanh thông minh (BI): Dễ dàng tiếp cận mã giả, thuật toán phân khoảng trọng số và cơ chế tỉa nhánh để trực tiếp lập trình, tối ưu hóa các mô hình gợi ý sản phẩm tự động trong môi trường doanh nghiệp thực tế.

3. Giám đốc điều hành và Giám đốc tiếp thị trong lĩnh vực bán lẻ: Nắm bắt các quy luật liên kết có trọng số để tái cấu trúc không gian trưng bày hàng hóa, thiết kế các chương trình khuyến mãi theo combo sản phẩm nhằm gia tăng biên lợi nhuận gộp từ 15% đến 25%.

4. Chuyên gia an toàn thông tin và kỹ sư phân tích sinh học: Tận dụng cơ chế gán trọng số ưu tiên của WFIM để phát hiện các mẫu hành vi bất thường, các cuộc tấn công mạng nguy hiểm hoặc phân tích tương quan cấu trúc protein trong các kho dữ liệu lớn.

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

1. Vì sao cần khai phá tập mục thường xuyên có trọng số thay vì chỉ dùng độ hỗ trợ truyền thống?
   Độ hỗ trợ truyền thống chỉ đếm số lần xuất hiện nên xem sản phẩm giá trị 10 triệu đồng tương đương sản phẩm 10 nghìn đồng, dẫn đến bỏ sót các tổ hợp sản phẩm có tần suất thấp nhưng sinh lời cao. Việc gán trọng số từ 0,1 đến 1,5 giúp thuật toán phản ánh chính xác giá trị kinh tế thực tế, giúp tối ưu hóa hơn 30% hiệu quả phân tích kinh doanh.

2. Điểm khác biệt mấu chốt giữa thuật toán MINWAL và thuật toán WFIM là gì?
   Thuật toán MINWAL kế thừa cơ chế của Apriori nên phải duyệt cơ sở dữ liệu nhiều lần và liên tục sinh tập ứng viên lớn, gây nghẽn bộ nhớ. Ngược lại, WFIM xây dựng dựa trên cây FP-Tree chỉ cần quét dữ liệu đúng 2 lần, giúp rút ngắn hơn 50% thời gian xử lý và giảm mạnh mức tiêu thụ RAM.

3. Thuật toán WFIM giải quyết bài toán mất tính chặn dưới đóng như thế nào?
   Do trọng số không giảm khi tập mục mở rộng, WFIM đã sắp xếp các nút cây FP-Tree theo thứ tự trọng số tăng dần và duyệt từ dưới lên. Kết hợp cùng hai điều kiện tỉa biên dựa trên trọng số lớn nhất và nhỏ nhất, thuật toán đảm bảo không bỏ sót bất kỳ mẫu thường xuyên có trọng số nào.

4. Thuật toán WFIM có khả năng mở rộng tốt trên các tập dữ liệu lớn không?
   Kết quả kiểm thử trên bộ dữ liệu T10I4DxK với quy mô 100.000 giao dịch chứng minh thời gian thực thi của WFIM chỉ tăng tuyến tính theo kích thước dữ liệu. Nhờ cấu trúc cây nén tối ưu, thuật toán hoàn toàn có khả năng mở rộng trên các hệ thống cơ sở dữ liệu lớn phân tán hiện đại.

5. Doanh nghiệp nên căn cứ vào đâu để thiết lập chỉ số trọng số cho từng mặt hàng?
   Doanh nghiệp có thể thiết lập bảng trọng số trong khoảng từ 0,2 đến 1,5 dựa trên các chỉ số định lượng nội bộ như tỷ suất lợi nhuận gộp, thời gian hoàn vốn hoặc mức độ ưu tiên chiến lược. Ví dụ, siêu thị gán trọng số 1,4 cho thiết bị điện tử và 0,3 cho hàng tạp hóa tiêu dùng nhanh.

Kết luận

Luận văn đã hoàn thành toàn diện các mục tiêu nghiên cứu đề ra với những dấu ấn học thuật và thực tiễn nổi bật:

• Hệ thống hóa cơ sở lý luận về khai phá dữ liệu, luật kết hợp và cấu trúc cây tiền tố FP-Tree.
• Đề xuất thành công thuật toán WFIM tích hợp phân khoảng trọng số và ngưỡng trọng số nhỏ nhất.
• Chứng minh toán học chặt chẽ về tính bảo toàn không gian mẫu thường xuyên có trọng số.
• Kiểm chứng thực nghiệm trên các tập dữ liệu chuẩn UCI với tốc độ xử lý nhanh hơn từ 40% đến 60% so với giải pháp cũ.
• Định hình khung ứng dụng thực tế vào việc tối ưu hóa chuỗi cung ứng và kinh doanh bán lẻ hiện đại.

Kế hoạch nghiên cứu tiếp theo trong giai đoạn 6 đến 12 tháng tới sẽ tập trung nâng cấp giải thuật WFIM cho luồng dữ liệu thời gian thực và mạng phân tán. Quý độc giả và các nhà phát triển hãy khai thác toàn văn luận văn này để áp dụng ngay giải thuật WFIM vào các dự án tối ưu hóa dữ liệu của mình.

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

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 đó. 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  T p mpq   0 khi iq  T p 6 Ví dụ 1. 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 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 và 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ợ tối thiểu (minsup) và độ tin cậy tối thiểu (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: 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. 8 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 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. 9 Bài toán khai phá tập mục thường xuyên có thể chia thành hai bài toán nhỏ: tìm các tập mục ứng viên và tìm các tập mục thường xuyên. Tập mục ứng viên là tập mục mà ta hy vọng nó là tập mục thường xuyên, phải tính độ hỗ trợ của nó để kiểm tra.

Tập mục thường xuyên là tập mục có độ hỗ trợ lớn hơn hoặc bằng ngưỡng hỗ trợ tối thiểu cho trước. Đã có rất nhiều thuật toán tìm tập mục thường xuyên được công bố, ta có thể phân chúng theo hai tiêu chí sau: - Phương pháp duyệt qua không gian tìm kiếm. - Phương pháp xác định độ hỗ trợ của tập mục. Phương pháp duyệt qua không gian tìm kiếm được phân làm hai cách: duyệt theo chiều rộng (Breadth First Search – BFS) và duyệt theo chiều sâu (Depth First Search – DFS).

Duyệt theo chiều rộng là duyệt qua cơ sở dữ liệu gốc để tính độ hỗ trợ của tất cả các tập mục ứng viên có (k-1) mục trước khi tính độ hỗ trợ của các tập mục ứng viên có k mục. Với cơ sở dữ liệu có n mục dữ liệu, lần lặp thứ k phải kiểm tra độ hỗ n! trợ của tất cả Cnk  tập mục ứng viên có k mục. k !(n  k )! Duyệt theo chiều sâu là duyệt qua cơ sở dữ liệu đã được chuyển đổi thành cấu trúc cây, quá trình duyệt gọi đệ quy theo chiều sâu của cây. Với cơ sở dữ liệu có n mục dữ liệu, không gian tìm kiếm có tất cả 2n tập con, rõ ràng đây là bài toán NP khó, do vậy cần phải có phương pháp duyệt thích hợp, tỉa nhanh các tập ứng viên.

Phương pháp xác định độ hỗ trợ của tập mục X được chia làm hai cách: cách thứ nhất là đếm số giao tác chứa X trong cơ sở dữ liệu và cách thứ hai là tính phần giao của các tập chứa định danh của các giao tác chứa X. Các thuật toán khai phá có thể phân loại như hình 1.2: 10 DFS BFS Đếm Đếm Giao Giao AIS Partition FP- Eclat growth Apriori Hình 1. Phân loại các thuật toán khai phá tập mục thường xuyên Phần tiếp sau mô tả chi tiết nội dung hai thuật toán tiêu biểu và là cơ sở để phát triển các thuật toán mới. Thuật toán Apriori tiêu biểu cho phương pháp sinh ra các tập mục ứng viên và kiểm tra độ hỗ trợ của chúng; Thuật toán FP-growth đại diện cho phương pháp không sinh ra tập mục ứng viên, cơ sở dữ liệu được nén lên cấu trúc cây, sau đó khai phá bằng cách phát triển dần các mẫu trên cây này.

Thuật toán Apriori Apriori là thuật toán khai phá tập mục thường xuyên do R. Srikant đề xuất vào năm 1993 [6]. Ý tưởng của thuật toán Apriori còn là nền tảng cho việc phát triển nhiều thuật toán khai phá tập mục thường xuyên khác về sau. Ý tưởng chính của thuật toán như sau: sinh ra các tập mục ứng viên từ các tập mục thường xuyên ở bước trước, sử dụng kỹ thuật “tỉa” để bỏ đi những tập mục ứng viên không thoả mãn ngưỡng hỗ trợ cho trước.

Cơ sở của kỹ thuật này là tính chất Apriori (xem 1.