Tài liệu Nghiên cứu luật kết hợp hiếm và khuyến nghị áp dụng cho bài toán tiếp thị

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- Trần Thu Hà NGHIÊN CỨU LUẬT KẾT HỢP HIẾM VÀ KHUYẾN NGHỊ ÁP DỤNG CHO BÀI TOÁN TIẾP THỊ Chuyên ngành: Hệ thống thông tin Mã số: 60.48.01.04 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2013 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: Tiến sĩ Hà Hải Nam Phản biện 1: …………………………………………………………………………… Phản biện 2: ………………………………………………………………………….. Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 MỞ ĐẦU Phát hiện luật kết hợp là phát hiện các mối quan hệ đó trong phạm vi của một tập dữ liệu đã cho. Trong lĩnh vực khai phá dữ liệu (data mining), luật kết hợp (association rule) được dùng để chỉ mối quan hệ "kéo theo" giữa các tập dữ liệu (ví như sự xuất hiện của mặt hàng này "kéo theo" sự xuất hiện của mặt hàng kia) trong một tập bao gồm nhiều đối tượng dữ liệu. Phát hiện luật kết hợp đang được ứng dụng thành công trong một số lĩnh vực kinh tế xã hội khác nhau như thương mại, , y tế, tài chính,…. Một trong những vấn đề mới mà các nhà nghiên cứu hiện nay quan tâm là vấn đề phát hiện luật kết hợp hiếm( gọi tắt là luật hiếm) và ứng dụng luật hiếm vào các lĩnh vực của cuộc sống. Yếu tố thành công trong mọi hoạt động kinh doanh ngày nay là việc biết sử dụng thông tin một cách có hiệu quả. Có nghĩa là từ các dữ liệu có sẵn phải tìm ra các thông tin tiềm ẩn mà trước đó chưa được phát hiện, tìm ra xu hướng và các yếu tố tác động lên chúng. Trong chiến lược kinh doanh thì Tiếp thị luôn được xem là cốt lõi của vấn đề, bởi muốn thành công trong kinh doanh thì chương trình tiếp thị, quảng bá đến người tiêu dùng luôn là khâu quan trọng nhất. Từ những yêu cầu thực tế trên, em chọn đề tài “Nghiên cứu luật kết hợp hiếm và khuyến nghị áp dụng cho bài toán tiếp thị”. Từ những mục tiêu và yêu cầu của đề tài nghiên cứu, đề tài được xây dựng gồm phần mở đầu, 3 chương nội dung và phần kết luận, cụ thể như sau: Chương 1: Tổng quan về vấn đề phát hiện luật kết hợp. Chương 2: Luật kết hợp hiếm. Chương 3:Khuyến nghị áp dụng luật kết hợp hiếm cho bài toán tiếp thị. Trong quá trình hình thành luận văn học viên đã được sự giúp đỡ tận tình của thầy hướng dẫn TS. Hà Hải Nam, cùng sự giúp đỡ của các thầy cô giáo trong Học viện Bưu chính viễn thông cùng các bạn bè đồng nghiệp. Học viên xin chân thành cảm ơn và mong nhận được sự đóng góp tích cực để bản thân được tự hoàn thiện mình hơn. 2 CHƯƠNG I: TỔNG QUAN VỀ VẤN ĐỀ PHÁT HIỆN LUẬT KẾT HỢP. Trước tiên, chương này sẽ giới thiệu tổng quan về phương pháp chung phát hiện luật kết hợp. Tiếp theo là trình bày quá trình phát hiện luật kết hợp từ CSDL tác vụ và vấn đề phát hiện luật kết hợp từ CSDL định lượng. 1.1 Luật kết hợp và các phương pháp chung phát hiện luật kết hợp. 1.1.1. Bài toán phát hiện luật kết hợp Ngày nay việc phát hiện luật kết hợp đang trở thành một khuynh hướng quan trọng trong khai phá dữ liệu. Luật kết hợp là luật ngầm định một số quan hệ kết hợp giữa một tập các đối tượng, mà các đối tượng này có thể độc lập hoàn toàn với nhau. Khái niệm luật kết hợp (Association Rule) và phát hiện luật kết hợp (Association Rule Mining) được Rakesk Agrawal và các cộng sự đề xuất lần đầu tiên vào năm 1993 nhằm phát hiện các mẫu có giá trị trong CSDL tác vụ (Transaction Database) tại các siêu thị. Mục đích của bài toán phát hiện luật kết hợp là tìm ra mối quan hệ giữa các tập mục dữ liệu trong các CSDL lớn và các mối quan hệ này là có ích trong hỗ trợ quyết định. Trong CSDL dân số, quan hệ “60% số người lao động ở độ tuổi trung niên có thu nhập thấp hơn mức thu nhập bình quân” sẽ rất có ích cho việc điều chỉnh chính sách thu nhập. Trong CSDL siêu thị, việc phát hiện được quan hệ “78% số khách hàng mua sữa và đường cũng mua bơ” sẽ rất có ích cho quyết định kinh doanh, chẳng hạn, quyết định về số lượng nhập các mặt hàng này hoặc bố trí chúng tại các ngăn hàng liền kề nhau. Luật kết hợp (Association rule) được định nghĩa là biểu diễn mối quan hệ giữa hai tập mục dưới dạng X  Y, trong đó X  I, Y  I, X  Y = . X được gọi là phần tiền đề (antecedent) và Y được gọi là phần hệ quả (consenquent) của luật. 1.1.2. Quy trình phát hiện luật kết hợp 3 Theo thống kê của Microsoft [5], đã có 2671 tác giả công bố 1526 công trình khoa học có giá trị (với 10224 lần được chỉ dẫn) về phát hiện luật kết hợp. Mục đích của bài toán phát hiện luật kết hợp trong CSDL tác vụ D là đi tìm tất cả các luật kết hợp mạnh (độ hỗ trợ cực tiểu và độ tin cậy cực tiểu do người sử dụng đưa ra trong quá trình phát hiện luật). Các thuật toán phát hiện luật kết hợp thường chia quá trình giải bài toán này thành hai bước như sau: (1) Bước 1: Tìm tất cả các tập phổ biến trong CSDL D. (2) Bước 2: Với mỗi tập phổ biến I1 tìm được ở bước 1 tất cả các luật mạnh có dạng I2 I1 – I2, I2  I1 Trong đó, ở bước thứ 1 đây là giai đoạn khó khăn, phức tạp và tốn nhiều chi phí. Bước 2 được giải quyết đơn giản hơn khi đã có các tập phổ biến và độ hỗ trợ của chúng. Bài toán tìm tập phổ biến trong không gian các tập con của tập mục I có độ phức tạp tính toán là O(2I). 2.1 Phát hiện luật kết hợp từ CSDL tác vụ. Nghiên cứu phát hiện luật kết hợp trong CSDL tác vụ được khởi đầu từ phát hiện luật kết hợp với một ngưỡng độ hỗ trợ, tới phát hiện luật kết hợp với độ hỗ trợ khác nhau cho các mục dữ liệu. 1.2.1. Phát hiện luật kết hợp với một ngưỡng độ hỗ trợ. Bài toán phát hiện luật kết hợp đưa ra một ngưỡng độ hỗ trợ chung( độ hỗ trợ cực tiểu) do người sử dụng đưa vào. Việc phát hiện luật kết hợp tuân thủ theo quy trình hai bước, tập chung vào bước tìm ra tập các tập phổ biến, với ba hướng giải quyết: - Tìm tất cả các tập phổ biến. - Tìm tất cả các tập phổ biến đóng. - Tìm tất cả các tập phổ biến cực đại. 1.2.1.1. Phát hiện luật kết hợp từ tất cả các tập phổ biến 4 Các phương pháp được sử dụng ở đây là phương pháp duyệt không gian tìm kiếm, các phương pháp xác định trước hỗ trợ. Bỏ qua độ phức tạp vào – ra và tính toán khi duyệt CSDL, các thuật toán này đều thực hiện tìm kiếm trên cây các tập con của tập mục vì vậy độ phức tạp tính toán là O( ). Phương pháp duyệt không gian tìm kiếm được chia thành hai nhóm tương ứng: 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 theo kích thước k của các tập mục ứng viên lần lượt từ kích thước 1, 2, ….Một số thuật toán phổ biến theo cách tiếp cận này là Apriori, Partition, ….,thuật toán Apriori( hình 1.1) được xếp vào tốp 10 thuật toán khai phá dữ liệu điển hình nhất. Thuật toán Apriori thực hiện nhiều lần duyệt dữ liệu, trong lần duyệt thứ nhất, ta tính độ hỗ trợ của tập mục riêng và xác định mục phổ biến trong chúng, nghĩa là thỏa mãn độ hỗ trợ cực tiểu. Trong mỗi lần duyệt sau ta sử dụng các tập phổ biến đã tìm được trong lần duyệt trước để sinh ra tập phổ biến tiềm năng, gọi là tập ứng viên và tính độ hỗ trợ của tập ứng viên này khi duyệt qua dữ liệu, ở cuối mỗi lần duyệt ta xác định được tập item nào là tập phổ biến thực sự trong các tập ứng viên. Quá trình đó thực hiện cho tới khi không còn tập mục phổ biến nào mới được tìm thấy nữa. Bảng 1.1: Bảng kí hiệu sử dụng trong thuật toán Apriori 1 Ký hiệu k-itemset Lk Ck Ý nghĩa Tập có k-mục dữ liệu Tập chứa k= itemset phổ biến. Mỗi phần tử của tập này có hai trường: i) itemset và ii) độ hỗ trợ của itemset đó Tập chứa các k-itemset ứng viên( các tập phổ biến à tiềm năng). Mỗi phần tử của tập này có hai trường: i) itemset và ii) độ hỗ trợ. 5 Đầu vào: CSDL D, độ hỗ trợ cực tiểu minSup Kết quả: Tập các tập phổ biến Thuật toán Apriori tìm các tập phổ biến: 1. L1 = {1-tập mục dữ liệu phổ biến}; 2. for ( k = 2; Lk-1 ; k++ ) do begin 3. Ck = apriori-gen(Lk-1, minsupp); // sinh ra các ứng cử viên Lk-1 4. forall transactions t  D do begin 5. Ct = subset(Ck, t); // ứng cử viên được chứa trong t 6. forall candidates c Ct do 7. c.count++; 8. end 9. Lk = {c  Ck c:count  minSup} 10. end 11. Answer = UkLk Hàm Apriori – Gen sinh ra các ứng cử viên: Procedure apriori-gen(Lk-1) insert into Ck //bước kết nối select p.item1, p.item2,…,p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1 = q.item1,…,p.itemk-2 = q.itemk-2, p.itemk-1 PromotionType= 0 với conf = 0.7 16 Luật này có thể được suy diễn như sau: Khi mua đồ cho trẻ em từ 1-2 tuổi khách hàng có nghề nghiệp văn phòng không mua các sản phẩm khuyến mãi. Luật 2: ( ProductType =1, ProductTypeByAge =1, CareerType =1) => PromotionType=0 với conf = 0.75 Luật này được suy diễn như sau: Khi mua thực cho phẩm trẻ em từ 1-2 tuổi, khách hàng có nghề nghiệp văn phòng không mua các sản phẩm khuyến mãi. Luật 3: (ProductPrice >= 300.000, ProductType =2, CareerType=2) => Month = 1) với conf = 0.8 Luật 4: (ProductPrice >= 300.000, ProductType = 2, CareerType=2) => Month = 2) với conf = 0.76 Luật 3 và 4 được suy diễn như sau: Vào tháng 1 và tháng 2 các khách hàng có nghề nghiệp lao động phổ thông mua đồ chơi trẻ em có giá trị lớn hơn 300.000 VND. Tuy thử nghiệm được tiến hành chỉ đưa ra một số luật hiếm khá đơn giản, thử nghiệm cũng minh chứng được khả năng áp dụng khai phá luật hiếm trong các ứng dụng tiếp thị sản phẩm dịch vụ. Kết luận chương: Trong chương thứ 3, luận văn đã trình bày kết quả ứng dụng khai phá dữ liệu với luật kết hợp hiếm cho bài toán tiếp thị. Việc ứng dụng luật kết hợp hiếm được khuyến nghị áp dụng vào ba phạm vi chính của tiếp thị dựa trên tri thức là: Xây dựng hồ sơ khách hàng, phân tích biến động và phân tích xu hướng. Thử nghiệm được áp dụng với CSDL của một của hàng bán đồ trẻ em cũng đã mang lại kết quả hữu ích mà bài toán tiếp thị cần quan tâm. Đưa ra được một số luật cần thiết áp dụng cho tiếp thị. 17 PHẦN KẾT LUẬN Các kết quả đạt được: Luận văn đã nghiên cứu về lý thuyết và ứng dụng vấn đề phát hiện luật kết hợp, ứng dụng khai phá luật kết hợp với luật kết hợp hiếm vào bài toán tiếp thị. Các nỗ lực hiện tại trong quản lý quan hệ khách hàng được tập trung vào giao diện khách hàng và quản lý các tương tác với khách hàng.