Khóa luận Trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến tiếp cận khai phá luật kết hợp

i ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Quách Hiếu Nghĩa TRÍCH CHỌN THUỘC TÍNH SẢN PHẨM TRONG HỆ THỐNG MUA BÁN TRỰC TUYẾN TIẾP CẬN KHAI PHÁ LUẬT KẾT HỢP KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2009 ii ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Quách Hiếu Nghĩa TRÍCH CHỌN THUỘC TÍNH SẢN PHẨM TRONG HỆ THỐNG MUA BÁN TRỰC TUYẾN TIẾP CẬN KHAI PHÁ LUẬT KẾT HỢP KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: Ths. Nguyễn Việt Cường Cán bộ đồng hướng dẫn: CN. Nguyễn Thị Thùy Linh HÀ NỘI - 2009 LỜI CẢM ƠN Đầu tiên, em xin gửi lời cảm ơn chân thành và sâu sắc tới Thạc sỹ Nguyễn Việt Cường và Cử nhân Nguyễn Thị Thùy Linh, người đã tận tình chỉ bảo và hướng dẫn em trong suốt quá trình thực hiện khóa luận tốt nghiệp này. Tiếp theo, em xin chân thành cảm ơn các thầy cô đã nhiệt tình giảng dạy và giúp đỡ, tạo điều kiện thuận lợi cho em trong suốt quá trình học tập tại trường Đại học Công nghệ. Em cũng xin gửi lời cảm ơn tới thầy cô và các bạn sinh viên thuộc Phòng thí nghiệm Công nghệ tri thức đã ủng hộ và giúp đỡ em rất nhiều trong quá trình nghiên cứu và thực hiện khóa luận này. Cuối cùng, xin gửi lời cảm ơn vô hạn tới gia đình và bạn bè, những người luôn bên cạnh và động viên tôi trong cuộc sống học tập cũng như làm việc. Xin chân thành cảm ơn! Hà Nội, ngày 23 tháng 5 năm 2009 Sinh viên Quách Hiếu Nghĩa i TÓM TẮT NỘI DUNG Ngày nay, thương mại điện tử đã trở nên phổ biến đối với mọi người. Cùng với nó là sự ra đời của các trang web bán hàng trên mạng. Trên các trang web bán hàng trực tuyến thường có mục dành cho khách hàng đưa ra ý kiến, đánh giá của mình về sản phẩm và các dịch vụ liên quan. Với sự phát triển của thương mại điện tử, số lượng đánh giá mà một sản phẩm nhận được cũng ngày càng tăng. Đối với một sản phẩm phổ biến, số lượng đánh giá của khách hàng có thể khá lớn (có thể lên tới con số hàng trăm). Điều này gây ra khó khăn cho những ai muốn tham khảo các đánh giá để đưa ra quyết định có mua sản phẩm hay không. Do vậy, nảy sinh nhu cầu tóm tắt những đánh giá này lại thành một bản tóm tắt dễ đọc. Trong khóa luận này, chúng tôi thực hiện nghiên cứu và triển khai mô hình trích chọn các thuộc tính sản phẩm được nhắc đến trong các đánh giá, một phần quan trọng trong bài toán tóm tắt đánh giá sản phẩm của người dùng trên hệ thống mua bán trực tuyến. Hiện nay trên thế giới đã có nhiều hệ thống trích chọn thuộc tính sản phẩm trong các đánh giá đạt kết quả khả quan, tuy nhiên đó đều là các hệ thống áp dụng cho ngôn ngữ tiếng Anh. Mục tiêu của khóa luận là xây dựng một mô hình xử lý các đánh giá viết trên ngôn ngữ tiếng Việt bằng cách áp dụng một số kĩ thuật xử lý ngôn ngữ tự nhiên và khai phá luật kết hợp. Tuy kết quả đạt được chưa thể đáp ứng được yêu cầu thực tế do tồn tại nhiều khó khăn, hạn chế trong các công cụ xử lý ngôn ngữ tiếng Việt cũng như các cơ sở để đánh giá, nhưng đã chứng minh được tính đúng đắn và hiệu quả của các kĩ thuật sử dụng. Đây là cơ sở cho các hệ thống tương tự trong tương lai có thể sử dụng lại hoặc cải tiến hoàn thiện hơn. ii MỤC LỤC LỜI CẢM ƠN........................................................................................................................i TÓM TẮT NỘI DUNG.........................................................................................................i MỤC LỤC ............................................................................................................................ii DANH MỤC BẢNG SỐ LIỆU...........................................................................................iv DANH MỤC HÌNH ẢNH....................................................................................................v MỞ ĐẦU ..............................................................................................................................1 Chương 1: GIỚI THIỆU.......................................................................................................2 1.1. Đặt vấn đề: ..............................................................................................................2 1.2. Phát biểu bài toán trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến tiếp cận khai phá luật kết hợp: ................................................................................4 1.3. Ý nghĩa và ứng dụng:..............................................................................................6 Chương 2: CƠ SỞ LÝ THUYẾT .........................................................................................8 2.1. Khai phá luật kết hợp:.............................................................................................8 2.1.1. Định nghĩa:.......................................................................................................8 2.1.2. Các bước trong khai phá luật kết hợp: .............................................................8 2.2. Các khái niệm cơ sở:...............................................................................................9 2.3. Thuật toán Apriori: ...............................................................................................12 2.4. Tổng kết chương: ..................................................................................................18 Chương 3: TRÍCH CHỌN THUỘC TÍNH SẢN PHẨM TRONG HỆ THỐNG MUA BÁN TRỰC TUYẾN TIẾP CẬN KHAI PHÁ LUẬT KẾT HỢP.....................................19 3.1. Giới thiệu: .............................................................................................................19 3.2. Bài toán trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến tiếp cận khai phá luật kết hợp: ...............................................................................................19 iii 5.2.1. Tự động trích chọn các thực thể trong văn bản:.............................................20 5.2.2. Xác định thuộc tính của sản phẩm từ tập ứng viên:.......................................20 3.3. Mô hình trích chọn thuộc tính sản phẩm: .............................................................21 3.3.1. Cấu trúc hệ thống trích chọn thuộc tính sản phẩm:........................................21 3.3.2. Tách từ: ..........................................................................................................22 3.3.3. Gán nhãn loại từ: ............................................................................................23 3.3.4. Trích chọn thuộc tính phổ biến: .....................................................................24 3.3.5. Trích chọn từ thể hiện ý kiến: ........................................................................26 3.3.6. Trích chọn thuộc tính ít phổ biến: ..................................................................27 3.3.7. Đánh giá, nhận xét về mô hình sử dụng:........................................................28 3.3.8. Giới thiệu một số mô hình trích chọn thuộc tính sản phẩm khác: .................29 3.4. Tổng kết chương: ..................................................................................................30 Chương 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ ..................................................................31 4.1. Môi trường thử nghiệm:........................................................................................31 4.1.1. Môi trường phần cứng:...................................................................................31 4.1.2. Công cụ phần mềm: .......................................................................................31 4.2. Dữ liệu thực nghiệm: ............................................................................................31 4.3. Kết quả thực nghiệm:............................................................................................34 4.3.1. Tách từ và gán nhãn từ loại:...........................................................................34 4.3.2. Trích chọn thuộc tính phổ biến: .....................................................................35 4.3.3. Tìm tập các từ thể hiện ý kiến:.......................................................................38 4.3.4. Trích chọn thuộc tính ít phổ biến: ..................................................................38 4.4. Đánh giá kết quả thực nghiệm: .............................................................................39 4.5. Tổng kết chương: ..................................................................................................42 KẾT LUẬN ........................................................................................................................43 TÀI LIỆU THAM KHẢO..................................................................................................44 iv DANH MỤC BẢNG SỐ LIỆU Bảng 1. Bảng ví dụ về cơ sở dữ liệu chứa các giao dịch bán hàng của một siêu thị..........11 Bảng 2. Bảng kí hiệu cho thuật toán Apriori......................................................................13 Bảng 3. Bảng cơ sở dữ liệu giao tác minh họa cho thuật toán Apriori ..............................15 Bảng 4. Bảng kết quả C1, L1...............................................................................................16 Bảng 5. Bảng kết quả C2, L2...............................................................................................16 Bảng 6. Bảng kết quả C3, L3...............................................................................................17 Bảng 7. Bảng kết quả C4, L4...............................................................................................17 Bảng 8. Cấu hình hệ thống thử nghiệm..............................................................................31 Bảng 9. 6 sản phẩm tiêu biểu trong số các mẫu thực nghiệm ............................................33 Bảng 10. Các loại danh từ ..................................................................................................35 Bảng 11. Số lượng danh từ trong tập đánh giá mỗi sản phẩm ...........................................36 Bảng 12. Độ hồi tưởng và độ chính xác đối với kết quả thu được nhờ khai phá luật kết hợp ......................................................................................................................................37 Bảng 13. Độ hồi tưởng, độ chính xác của kết quả thu được sau 2 bước cắt tỉa .................38 Bảng 14. Độ hồi tưởng và chính xác của kết quả sau các bước xác định thuộc tính ít phổ biến. ....................................................................................................................................39 Bảng 15. Độ đo F1 của kết quả sau các bước.....................................................................39 v DANH MỤC HÌNH ẢNH Hình 1. Ba bước tóm tắt các đánh giá một sản phẩm trên hệ thống mua bán trực tuyến.....3 Hình 2. Mô hình hệ thống trích chọn thuộc tính sản phẩm trong hệ thống bán hàng trực tuyến ...................................................................................................................................21 Hình 3. Ví dụ về các đánh giá sản phẩm Nokia E90 trên website thegioididong.com ......32 Hình 4. Đồ thị độ đo F1 của kết quả sau các bước trích chọn............................................40 1 MỞ ĐẦU Với sự phát triển của thương mại điện tử, số lượng đánh giá của người dùng về một sản phẩm trên một hệ thống mua bán trực tuyến ngày càng gia tăng. Do vậy bài toán tóm tắt các đánh giá ra đời. Cùng với nó là bài toán con, trích chọn thuộc tính sản phẩm được người dùng đề cập đến trong các đánh giá, cần phải giải quyết. Hiện nay, có khá nhiều hướng tiếp cận theo phương pháp học máy để giải quyết bài toán trích chọn thuộc tính sản phẩm. Trong khóa luận này, chúng tôi sử dụng kĩ thuật khai phá luật kết hợp để trích chọn ra các thuộc tính của sản phẩm. Đây là một hướng tiếp cận hiệu quả đã được chứng minh khi thực hiện trên ngôn ngữ tiếng Anh. Chúng tôi sẽ trình bày các giải pháp thích hợp khi áp dụng vào tiếng Việt. Khóa luận gồm bốn chương, nội dung được mô tả sơ bộ như dưới đây: • Chương 1: Đặt vấn đề và giới thiệu tổng quan bài toán tóm tắt đánh giá sản phẩm, từ đó phát biểu bài toán trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến. • Chương 2: Trình bày về lý thuyết khai phá luật kết hợp theo hướng áp dụng vào giải quyết bài toán trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến. • Chương 3: Phát biểu bài toán trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến tiếp cận khai phá luật kết hợp, phân tích các vấn đề cần giải quyết đối với bài toán và các bước xây dựng mô hình trích chọn trên cơ sở áp dụng khai phá luật kết hợp. • Chương 4: Trình bày những kết quả thực nghiệm của khóa luận. Cuối cùng là phần kết luận, tóm tắt lại những nội dung chính của khóa luận, đồng thời chỉ ra những điểm cần khắc phục và hướng cải tiến nhằm mục tiêu xây dựng một hệ thống ứng dụng thực trên môi trường Internet. 2 Chương 1: GIỚI THIỆU 1.1. Đặt vấn đề: Trên thế giới nói chung và ở Việt Nam nói riêng, thương mại điện tử đã trở nên phổ biến và ngày càng phát triển. Một phần quan trọng trong thương mại điện tử là bán hàng trực tuyến. Ta có thể thấy số lượng website mua bán trực tuyến vô cùng lớn, nổi tiếng trên toàn thế giới có Amazon.com, Cnet.com, eBay…, còn ở Việt Nam có thể kể ra một số trang web như vatgia.com, thegioididong.com... Chủng loại sản phẩm trên các hệ thống bán hàng trực tuyến cũng vô cùng đa dạng, từ sản phẩm phục vụ cuộc sống hàng ngày cho tới ô tô, căn hộ, nhà cửa, bất động sản… Với mỗi một sản phẩm được bán trực tuyến, luôn có mục nhận xét (review) là nơi khách hàng đưa ra ý kiến đánh giá của mình về sản phẩm đã mua cũng như các dịch vụ liên quan. Đây là nguồn thông tin quan trọng, cung cấp cho người mua hàng cái nhìn toàn diện hơn về một sản phẩm mà họ định mua. Còn đối với nhà sản xuất, đánh giá của khách hàng là cơ sở để tiến hành cải tiến, hoàn thiện sản phẩm của mình. Cùng với sự phát triển không ngừng của thương mại điện tử thì số lượng người mua hàng trực tuyến cũng ngày càng tăng, dẫn đến số lượng nhận xét, đánh giá của người dùng về các sản phẩm ngày càng nhiều. Một sản phẩm thông dụng có thể có hàng trăm thậm chí hàng nghìn nhận xét khác nhau. Điều nay gây khó khăn cho cả người mua hàng và nhà sản xuất. Người mua hàng sẽ gặp khó khăn trong việc tổng hợp ý kiến của những người đi trước để đưa ra quyết định mua hay không mua một sản phẩm. Còn nhà sản xuất thì khó theo dõi, nắm bắt được tất cả phản hồi của người tiêu dùng về sản phẩm của mình. Thêm vào đó, các công ty thì không chỉ sản xuất 1 loại sản phẩm. Một công ty thường sản xuất vài loại sản phẩm khác nhau và các sản phẩm này cũng có thể được bán trên nhiều website khác nhau. Từ thực tế trên, nảy sinh nhu cầu cần tóm tắt tất cả nhận xét của khách hàng về một sản phẩm trên hệ thống mua bán trực tuyến. Khác với việc tóm tắt văn bản truyền thống, thường là thuần túy chọn lọc ra một số câu trong văn bản gốc để tạo thành bản tóm tắt hoặc diễn giải lại nội dung văn bản gốc một cách ngắn gọn, súc tích hơn. Ở đây, tóm tắt đánh giá sản phẩm nhằm mục tiêu tạo ra một bản tóm tắt dựa trên các thuộc tính của sản phẩm đó. Tức là ta chỉ khai thác các thuộc tính (đặc trưng, chức năng) của 3 sản phẩm được người tiêu dùng nhận xét và từ đó xác định các ý kiến đánh giá được đưa ra. Việc tóm tắt đánh giá sản phẩm cơ bản được thực hiện như sau: Hình 1. Ba bước tóm tắt các đánh giá một sản phẩm trên hệ thống mua bán trực tuyến Giả sử chúng ta thực hiện tóm tắt các đánh giá đối với một sản phẩm máy ảnh kĩ thuật số, máy_ảnh_1. Kết quả tóm tắt tạo ra sẽ có cấu trúc như sau: Máy_ảnh_1: Thuộc tính: chất lượng ảnh Khen (positive): 253 + “Chất lượng ảnh tuyệt vời” + “Tôi rất thích chất lượng của bức ảnh” ... Chê (negative): 6 + “Chất lượng ảnh không tương ứng với mức giá quá cao” ... Thuộc tính: kích thước Khen (positive): 134 + “Thật đáng kinh ngạc, kích thước nhỏ gọn trong lòng bàn tay” … 4 Trong 3 bước trên, bước cuối cùng khá đơn giản, chỉ sử dụng kết quả của hai bước trước để sinh ra bản tóm tắt. Hai bước đầu mới đóng vai trò quyết định trong việc giải quyết vấn đề. Bước một là xác định những thuộc tính, đặc trưng của sản phẩm được người tiêu dùng quan tâm, nhận xét. Từ đó, bước hai sẽ xác định ra các câu chứa ý kiến đánh giá (về các thuộc tính tìm được ở bước một), rồi phân loại ý kiến thành 2 loại tích cực và tiêu cực. Như vậy, ta có thể thấy, xác định thuộc tính sản phẩm được đánh giá là vấn đề cần phải giải quyết đầu tiên. Một câu hỏi có thể được đặt ra là “tại sao không lấy luôn danh sách các thuộc tính của sản phẩm từ nhà bán lẻ hay nhà sản xuất?” Đây cũng là một hướng tiếp cận. Tuy nhiên, nó gặp phải một số vấn đề sau: (1) Đối với nhà bán lẻ, số lượng chủng loại sản phẩm họ bán có thể rất nhiều, do vậy họ cũng không nắm bắt được hết tất cả các thuộc tính của từng sản phẩm. (2) Từ ngữ mà nhà bán lẻ hoặc nhà sản xuất sử dụng để chỉ thuộc tính của sản phẩm có thể không giống như của khách hàng mặc dù có thể cùng nói về một thuộc tính. Do vậy, khó có thể dựa vào đó để xác định các thuộc tính mà khách hàng nhận xét. Ngoài ra, khách hàng còn có thể nhận xét về các thuộc tính mà sản phẩm còn thiếu. (3) Khách hàng cũng có thể nhận xét về một vài thuộc tính mà nhà sản xuất không nghĩ tới (những thuộc tính của sản phẩm nhưng không có trong danh sách đưa ra). (4) cuối cùng, nhà sản xuất có thể không đưa ra các thuộc tính yếu kém của sản phẩm do lo ngại người dùng biết được. Vì vậy để khắc phục các hạn chế trên, chúng ta cần đi theo hướng trích chọn thuộc tính sản phầm từ các đánh giá của người dùng bằng cách áp dụng phương pháp học máy. Bài toán trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến tiếp cận khai phá luật kết hợp ra đời từ đây. Khóa luận này sẽ tập trung vào giải quyết bài toán trích chọn thuộc tính sản phầm trong hệ thống mua bán trực tuyến tiếp cận khai phá luật kết hợp, xử lý trên ngôn ngữ tiếng Việt. Phần dưới đây sẽ trình bày chi tiết hơn về vấn đề này. 1.2. Phát biểu bài toán trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến tiếp cận khai phá luật kết hợp: Như đã giới thiệu ở trên, bài toán trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến thuộc loại bài toán trích chọn thông tin, nhằm mục tiêu tìm ra tất cả thuộc tính, đặc trưng của sản phẩm đã được người mua hàng đánh giá. 5 Do vậy, đầu vào (input) của bài toán là các nhận xét, đánh giá của người dùng về một sản phẩm cụ thể trên một hệ thống bán hàng trực tuyến. Ví dụ: sản phẩm điện thoại Nokia 8800 Arte trên website thegioididong.com. Đầu ra (output) là một danh sách các đối tượng có thể là thuộc tính, đặc trưng của sản phẩm được người dùng nhận xét, đề cập đến trong bài đánh giá. Ví dụ: {màn hình, phím bấm, màu sắc, loa, giá cả, kích thước, pin, hình dáng, camera, chất lượng ảnh, hệ điều hành, ứng dụng, kết nối wifi…} Trong những năm gần đây, trên thế giới đã có khá nhiều công trình nghiên cứu về đề tài này. Hầu hết các mô hình trích chọn thuộc tính sản phẩm đều đi theo hướng trích chọn ra các danh từ và cụm danh từ trong dữ liệu và xây dựng các mô hình thuật toán để lọc ra được các cụm từ có khả năng là thuộc tính của sản phẩm. Có nhiều hướng tiếp cận khác nhau để trích chọn ra được các cụm từ có khả năng là thuộc tính sản phẩm như áp dụng học không giám sát [17], CRFs, … Tuy vậy, vẫn còn các vấn đề sau phải giải quyết: • Trích chọn các thuộc tính từ các từ loại khác danh từ (tính từ và động từ cũng có thể dùng để chỉ thuộc tính của sản phẩm). Một ví dụ đơn giản như khi nói một sản phẩm “nhẹ” thì ta thường hiểu đó là nói về thuộc tính “trọng lượng”. Do việc xác định những thuộc tính dạng này đòi hỏi phải phân tích được ngữ nghĩa của cả câu, nên đây là một vấn đề khó khăn, đòi hỏi phải có những nghiên cứu sâu về lĩnh vực xử lý ngôn ngữ tự nhiên. • Một vấn đề nữa là xử lý các từ đồng nghĩa cùng chỉ một thuộc tính. Đây không phải là những trường hợp hiếm gặp. Để giải quyết vấn đề này, hiện nay có 4 hướng tiếp cận chính: đó là sử dụng từ điển đơn ngữ, từ điển đồng nghĩa (thesaurus), WordNet và máy tìm kiếm (search engine). Tuy nhiên, kết quả đạt được đều còn khá hạn chế. Còn ở Việt Nam, cho tới thời điểm này, chưa có một công trình nghiên cứu nào về lĩnh vực trích chọn thuộc tính sản phẩm trên các hệ thống mua bán trực tuyến. Trong khóa luận này, chúng tôi mong muốn sử dụng các kĩ thuật đã được nghiên cứu, đề xuất trong những công trình đã có trên thế giới, cùng với việc thay đổi, cải tiến thích hợp để áp dụng vào ngôn ngữ tiếng Việt. Do vậy, bên cạnh hai vấn đề đã chỉ ra ở trên, chúng tôi còn phải đối mặt với các thách thức sau: 6 • Vấn đề thứ nhất là sự nhập nhằng của ngôn ngữ. Tiếng Việt khác với tiếng Anh, là loại hình ngôn ngữ đơn lập, vì vậy việc phân biệt ranh giới từ và xác định từ loại là một vấn đề phức tạp. Do vậy, ta cần xây dựng những bộ xử lý ngôn ngữ tiếng Việt đủ mạnh để đảm bảo kết quả có độ chính xác cao. • Vấn đề thứ hai là lựa chọn chiến lược trích chọn hiệu quả để tìm ra các thuộc tính sản phẩm. Trong khóa luận này, chúng tôi sử dụng kĩ thuật khai phá luật kết hợp kết hợp cùng với một số phương pháp xử lý ngôn ngữ tự nhiên để xây dựng mô hình trích chọn thuộc tính sản phẩm. Khai phá luật kết hợp cho phép tìm ra tập tất cả đối tượng thỏa mãn điều kiện do người dùng đặt ra. Đây là phương pháp được nhiều công trình nghiên cứu tương tự áp dụng hiệu quả [12, 16]. Qua thử nghiệm đã cho thấy kết quả khá khả quan. Độ chính xác đối với tiếng Anh đạt trên 68% (cao nhất là 87%). Các bước giải quyết bài toán trong khóa luận như sau: (1) Thu thập dữ liệu: nếu dữ liệu (là các đánh giá, nhận xét của người dùng vể một sản phẩm) chưa có sẵn trong cơ sở dữ liệu, ta phải tiến hành crawl từ các website bán hàng trực tuyến về; (2) Tiền xử lý: chuẩn hóa văn bản, sửa các lỗi cú pháp, chính tả, loại bỏ các kí hiệu vô nghĩa hoặc không có ý nghĩa quan trọng (như các kí tự thể hiện cảm xúc trong ngôn ngữ chat qua mạng); (3) Trích chọn ra các thực thể có thể là thuộc tính của sản phẩm; (4) Xác định thuộc tính của sản phẩm: áp dụng khai phá luật kết hợp trên tập cơ sở dữ liệu đánh giá và tập thực thể thu được ở bước trên. Kết quả thu được sẽ được tiến hành “cắt tỉa” để thu được kết quả cuối cùng là tập các thuộc tính của sản phẩm xuất hiện trong đánh giá của người dùng. 1.3. Ý nghĩa và ứng dụng: Trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến tiếp cận khai phá luật kết hợp là một đề tài có ý nghĩa và mang tính ứng dụng cao. Kết quả của bài toán sẽ được sử dụng để tạo ra bản tóm tắt các ý kiến đánh giá của người dùng về một sản phẩm trên hệ thống mua bán trực tuyến dựa theo các thuộc tính của sản phẩm đó. Đối với những sản phẩm có số lượng đánh giá trên mạng khá lớn thì bản tóm tắt trên cung cấp cho người 7 dùng một cái nhìn toàn diện và chi tiết về sản phẩm đó, giúp họ tiết kiệm được thời gian trong việc tham khảo thông tin để đưa ra quyết định mua hàng. Còn nhà sản xuất thông qua các tóm tắt này cũng dễ dàng thu thập được các phản hồi của khách hàng trên mạng đối với sản phẩm của mình, để từ đó cải tiến, hoàn thiện sản phẩm cho phù hợp với nhu cầu của khách hàng. Chúng tôi tin rằng cùng với việc ngày càng nhiều người thực hiện mua sắm và bày tỏ ý kiến của bản thân qua mạng thì ý nghĩa và lợi ích do kết quả trên mang lại sẽ càng lớn. 8 Chương 2: CƠ SỞ LÝ THUYẾT Như đã đề cập trong chương một, yêu cầu của bài toán là xác định tất cả thuộc tính của sản phẩm được người dùng đánh giá, và để giải quyết vấn đề này chúng tôi sử dụng lý thuyết khai phá luật kết hợp để tìm ra tập các thuộc tính phổ biến. Điều này xuất phát từ quan sát thực tế sau. Các đánh giá sản phẩm thường có nội dung khác nhau và có thể gồm khá nhiều thứ không liên quan trực tiếp tới sản phẩm, nhưng khi nhận xét về các thuộc tính của sản phẩm, người dùng có xu hướng dùng những từ ngữ giống nhau. Do vậy, việc sử dụng khai phá luật kết hợp để tìm các tập chỉ mục phổ biến (thường là các thuộc tính của sản phẩm) là thích hợp. Chương hai này sẽ trình bày một số vấn đề chính về khai phá luật kết hợp: tổng quan, các khái niệm cơ sở và thuật toán Apriori dùng trong khai phá luật kết hợp. 2.1. Khai phá luật kết hợp: 2.1.1. Định nghĩa: Khai phá luật kết hợp được Rakesh Agrawal giới thiệu lần đầu vào năm 1993 [5], và từ đó tới nay đã được nghiên cứu, phát triển mạnh, trở thành một thuật toán học máy hiệu quả được áp dụng trong nhiều bài toán. Khai phá luật kết hợp có thể được hiểu là công việc đi tìm tần số mẫu, mối kết hợp, sự tương quan, hay các