Đặt vấn đề Trong vài thập kỷ gần đây, cùng với sự phát triển của xã hội, khoa học kĩ thuật, sự phát triển của công nghệ thông tin, việc sinh và lưu trữ dữ liệu cũng có nhiều kĩ thuật tiễn bộ. Tuy nhiên lượng dữ liệu ngày càng nhiều nên việc lưu trữ trở nên khó khăn hơn và đòi hỏi phương pháp lưu trữ với hiệu quả tốt nhất. Thay vì việc phải lưu trữ một lượng nhiều dữ liệu bao gồm cả dit liệu có thé không cần thiết, người ta thực hiện quá trình biến đôi dữ liệu thành thông tin có ích hay còn gọi là quá trình khai phá dữ liệu (data mining) dé biến dữ liệu thành thông tin hay tri thức phục vụ cho các ứng dụng và loại bỏ được bớt các dữ liệu không cần thiết. Tùy theo loại dữ liệu, loại tri thức muốn thu được từ dữ liệu mà ta sử dụng các phương pháp khai phá phù hợp.
Bên cạnh đó, khai phá dữ liệu còn giúp quá trình tìm thông kiếm thông tin tốt hơn với người dùng hay việc chăm sóc khách hàng, bán hàng tốt hơn đối với các doanh nghiệp. Chúng ta rất quen thuộc với việc tìm kiếm trên google, chúng ta đã thử đặt câu hỏi tại sao google có thể tìm kiếm một cách nhanh và thông minh đến vậy và dữ liệu vô cùng phong phú trên tât cả các mặt các lĩnh vực của đời sông xã hội? Hay việc mua bán sách trực tuyến trên trang nồi tiếng amazon.com, ban để ý rang mỗi khi bạn xem thông tin chỉ tiết về một quyền sách nào đó trên site thì bao giờ cũng kèm theo 1 danh sách các quyên sách gợi ý mua kèm theo quyền ban đang xem, một thống kê cho thấy có tới trên 70% đầu sách được người dùng mua thêm thông qua hình thức gợi ý này. Vậy điều gì làm cho việc bán sách hiệu quả đến như vậy? Tất cả những điều đạt được như vậy là nhờ công nghệ khai phá dữ liệu (data mining). Công nghệ này bao gồm việc tìm tòi và phân tích các khối dit liệu lớn dé chat lọc ra được những mẫu hình và xu hướng có ý nghĩa.
Nó được sử dụng trong nhiều mục đích khác nhau như tiếp thị theo cơ sở dữ liệu, quản trị rủi ro tín dụng, phòng chống gian lận, loc mail rác, hoặc đơn giản là dé tìm hiểu tâm lí và ý kiến của người dùng. Đó cũng chính là một trong những mục tiêu phô biến nhất hiện nay. Hiện nay, có rất nhiều những tác vụ khai phá dữ liệu, nhưng được sử dụng nhiều va phổ biến trong thương mại điện tử không thé không ké đến Association rule — một phương pháp khai phá dữ liệu nhăm đưa ra các tập luật phô biến cho các sản phẩm thường được mua cùng nhau. Những tập luật này góp phần hỗ trợ cho các chiến dịch marketing cũng như đóng góp không nhỏ trong quá trình đưa ra quyết định của các cấp lập chiến lược (tạo chương trình khuyến mãi, chạy quảng cáo).
Các thuật toán nổi tiếng có thể kế đến đối với phương pháp khai phá này là thuật toán Apriori, thuật toán FP Growth, thuật toán Eclat. Tuy nhiên, do thuật toán Apriori đã phát triên từ rất lâu nên có nhiều khuyết điểm như tốc độ xử lý, duyệt cơ sở dữ liệu quá nhiều lần. Do đó, trong phạm vi Khoá luận tốt nghiệp lần này, nhóm em sẽ tìm hiểu và thực hiện cài đặt 2 thuật toán cải tiễn cùng với đó là so sánh 2 thuật toán co bản Apriori, FP Growth và trực quan hoá các tap luật trích xuất được. Mục tiêu Khóa luận được thực hiện với bảy mục tiêu chính: Thứ nhất, tìm hiểu về luật kết hợp và các thuật toán tìm luật kết hợp tiêu biểu, gồm: - Apriori - FP-Growth - EClaT Thứ hai, khóa luận cũng tim hiểu phương pháp đánh giá các thuật toán bao gồm các chỉ số đánh giá, cách tính các chỉ số và phương pháp phân chia dữ liệu.
Thứ ba, thực hiện xây dựng cai đặt các thuật toán tiêu biểu và thực nghiệm trên một số bộ dữ liệu khác nhau. Thứ tư, trực quan hoá tập luật thu được từ thực nghiêm hai thuật toán tiêu biểu Apriori va FP Growth trên thành các dạng biéu dé: - Heatmap - Graph Thứ năm, dựa trên thực nghiệm với một số bộ dữ liệu khác và các chỉ số được tông hợp từ việc cài đặt thuật toán dé đưa ra so sánh giữa hai thuật toán tiêu biểu dựa trên các tiêu chí như thời gian, số lượng tập luật được sinh ra, hiệu năng (dung lượng bộ nhớ). Thứ sáu, đề xuất hai thuật toán cải tiến dựa trên thuật toán Apriori cơ bản, một là thuật toán cải tiễn dựa trên việc giảm số lần duyệt cơ sở dữ liệu, đã được đề cập bởi K. Hai là thuật toán cải tiến giảm số giao dịch cần phải duyệt khi tính support của tập ứng viên, đã được đề cập bởi Mohammed Al-Maolegi.
Thứ bảy, xây dựng chương trình minh hoạ dựa trên thư viện Python để trực quan hoá kết quả cho thuật toán tìm luật kết hợp tiêu biểu và xây dựng chương trình cài đặt hai thuật toán cải tiến. Ý nghĩa đề tài Ý nghĩa thực tế: -_ Việc áp dụng Khai phá dit liệu mà cụ thé là luật kết hợp giúp các doanh nghiệp có cái nhìn khác về dữ liệu rằng chúng không chỉ để xuất ra báo cáo doanh thu hàng tháng, năm mà còn có thê đưa ra một số gợi ý nhằm cài thiện tình hình kinh doanh mà cụ thê trong phạm vi đề tài lần này là ở một cửa hàng cụ thể, không phải trường hợp nhiều chi nhánh. - Goi ý đó trong phạm vi dé tài này chính là các sản phẩm thường được mua cùng với nhau. Từ đó, bộ phận kinh doanh có thê xem xét và điêu chỉnh các chiến lược ví dụ như: cách bố trí sản pham tai quay hàng, danh sách sản phẩm đề xuất khi khách hàng mua hàng online, chương trình khuyến mãi [1] [2],.
Ngoài những lợi ích về phía chủ doanh nghiệp, khách hàng cũng được hưởng các lợi ích như: rút ngăn thời gian trong quá trình di chuyển mua hàng, có những chương trình khuyến mãi hấp dẫn và phù hợp với nhu cầu [2] [3]. Tạo tiền đề dé phát triển các ứng dụng khác. Ý nghĩa nghiên cứu khoa học: Đề tài về Khai phá luật kết hợp có lẽ tuy đã khá phố biến nhưng những ứng dụng của nó vẫn rất hữu ích. Do đó, các nhà khoa học không ngừng tìm hiểu thêm những thuật toán mới cũng như cải tiễn thuật toán cũ và trong đề tài này nhóm em thực hiện dựa trên một bài báo khoa học vào năm 2012 và một bài báo vào năm 2014.
Đối tượng, phương pháp và phạm vi nghiên cứu Đối tượng nghiên cứu Kỹ thuật khai phá dữ liệu. Thuật toán cải tiến. Luật kết hợp, chức năng, vấn đề tồn tại và các kỹ thuật giải quyết. Phương pháp đánh giá thuật toán.
Phạm vi nghiên cứu Tìm hiểu phương pháp phân tích dữ liệu, thực nghiệm và cài đặt lại thuật toán Apriori va FP Growth dựa vào thư viện mlxtend trên Python. Bộ dữ liệu được lấy từ nguồn Kaggle — Online Retail Data v3 (2017) bao gồm Bill (Mã giao dịch), MerchandiseID (Mã sản phẩm), Product (Tên sản phẩm), Quota (Số lượng), BillDate (Ngày giao dịch), Amount (Giá/sản phẩm), CustomerID (Mã khách hàng), Country (Quốc gia). Xây dựng chương trình cài đặt hai thuật toán cải tiến và so sánh với thuật toán Apriori. Bộ dữ liệu của cửa hàng tạp hoá thực phẩm xanh tại Việt Nam.
Phương pháp nghiên cứu Tìm hiểu phương pháp phân tích thuật toán: Association Rule Mining (Apriori Algorithm) Association Rule Mining (FP-Growth) Association Rule Mining (EClaT) Cai đặt thuật toán Apriori va FP Growth. So sánh các thuật toán. Cải tiến thuật toán. Tìm hiểu các kỹ thuật trực quan hóa dữ liệu.
Xây dựng tool bằng ngôn ngữ Python nhăm trực quan hóa các số liệu phân tích và các luật được sinh ra. Phân tích, nhận xét kết quả thực nghiệm Xây dựng chương trình cài đặt hai thuật toán cải tiễn và so sánh với thuật toán Apriori cơ bản. Nội dung nghiên cứu Khảo sát nghiên cứu các vấn đề về luật kết hợp, các phương pháp, giải thuật giải quyết và so sánh ưu nhược điểm của từng phương pháp. Phân tích dữ liệu thực tế từ một cửa hàng quà tặng online ở Châu Âu (2017), cửa hàng tạp hoá thực pham xanh tai Viét Nam.
Đề xuất cải thiện thuật toán. Thực nghiệm, đánh giá các thuật toán, đưa ra so sánh và báo cáo kêt quả. Kết quả dự kiến Các kêt quả dự kiên của khóa luận như sau: So sánh ưu nhược điểm của 2 thuật toán cơ bản: Apiori, FP Growth. Truc quan hoá các tập luật kết hợp.
Dé xuât thuật toán cải tiên. - Phan tích, nhận xét kết quả thực nghiệm. Bố cục báo cáo Báo cáo được chia thành năm chương, phần còn lại được bố cục như sau: Chương 2 — Luật kết hợp Nội dung chương sẽ khái quát hóa những van dé về luật kết hợp bao gồm định nghĩa luật kết hợp, các chức năng, van đề và kỹ thuật tiếp cận của luật kết hợp. Apiori, FP Growth và Eclat sẽ là các thuật toán co bản được dé cập trong chương này.
Chương 3 — Thuật toán cải tiễn Hiện nay, có rât nhiêu thuật toán mới ra đời nhăm giải quyêt những hạn chê của các thuật toán cơ bản. Tuy nhiên, vẫn còn một hướng nghiên cứu khác đó chính là cải tiên những thuật toán cũ. Chương này sẽ nói về một thuật toán cải tiên và cơ sở lý thuyết của phương pháp này. Chương 4— Đánh gia Đề kiểm chứng tính hiệu quả của các thuật toán đã được trình bày trong chương 2 va 3, các thuật toán phải được thực nghiệm thực tế thông qua các bộ dữ liệu khác nhau và dựa trên các chỉ số đánh giá khác nhau.
Nội dung của chương sẽ trình bày phương pháp thực hiện thực nghiệm, sau đó so sánh các kết quả thực nghiệm thực tế dé có thể phân tích những ưu, nhược điểm của từng thuật toán. Chương 5 — Kết luận và hướng phát triển Nội dung trình bày tổng quan những nội dung được thực hiện trong khóa luận, những thành quả cũng như những hạn chế khóa luận gặp phải. Bên cạnh đó đưa ra những hướng phát triển của đề tài trong tương lai. KHAI PHA DU LIEU - LUAT KET HỢP Khai pha dữ liệu là một bước trong quá trình khám phá tri thức, bao gồm các thuật toán chuyên dụng đáp ứng một số yêu cầu về hiệu quả tính toán dé tim ra các mẫu hoặc các mô hình tồn tại bên trong cơ sở dữ liệu đang bị che khuất.