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 KHỐ 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 KHỐ 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 tố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 hồ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 tố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 tố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 tố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 tốn Apriori......................................................................13 Bảng 3. Bảng cơ sở dữ liệu giao tác minh họa cho thuật tố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 tốn tĩm tắt các đánh giá ra đời. Cùng với nĩ là bài tố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 tố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 tốn tĩm tắt đánh giá sản phẩm, từ đĩ phát biểu bài tố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 tố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 tố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 tố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 tồ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 tồ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, hồ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. Ngồ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 tố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 tố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 tố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 tố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 tố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 tố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 tố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 tố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 tố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 tồ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, hồ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 tố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 tố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 tốn học máy hiệu quả được áp dụng trong nhiều bài tố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 cấu trúc nhân quả phù hợp với nhu cầu của người dùng giữa các tập đối tượng trong các cơ sở dữ liệu giao tác, cơ sở dữ liệu quan hệ, và những kho thơng tin khác [1]. Hiện nay, khai phá luật kết hợp được ứng dụng vào trong nhiều lĩnh vực như: mạng viễn thơng, quản lý rủi ro, quản lý thị trường, quản lý kho hàng, phân cụm, phân lớp trong khai phá dữ liệu … 2.1.2. Các bước trong khai phá luật kết hợp: Trong bài tốn khai phá luật kết hợp, để tìm ra các luật kết hợp thỏa mãn 2 giá trị cho trước là độ hỗ trợ cực tiểu (minimum support) và độ tin cậy cực tiểu (minimum confidence) từ một cơ sở dữ liệu cĩ sẵn, cơng việc thực hiện được chia làm hai bước [5]: 9 (1) Tìm tất cả các tập chỉ mục phổ biến: một tập chỉ mục là phổ biến được xác định qua việc tính độ hỗ trợ và thoả mãn độ hỗ trợ cực tiểu. (2) Sinh ra các luật kết hợp mạnh từ các tập chỉ mục phổ biến: các luật phải thoả mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu. Giả sử cĩ tập chỉ mục phổ biến là Lk, Lk = {I1, I2, I3, …, Ik}, các luật kết hợp của tập chỉ mục này được sinh như sau: khởi tạo luật đầu tiên {I1, I2, I3, …, Ik-1} → {Ik}, sau đĩ tiến hành kiểm tra độ tin cậy (confidence) để xác định luật trên cĩ thỏa mãn hay khơng. Thực hiện cắt bỏ phần tử cuối cùng của vế trái, chuyển sang vế phải để tạo thành luật mới, rồi lại kiểm tra độ tin cậy. Quá trình trên được thực hiện cho tới khi vế trái trở thành tập rỗng. Do bước thứ 2 khá đơn giản, khơng cĩ gì phức tạp nên hầu hết các nghiên cứu về khai phá luật kết hợp đều tập trung vào bước một. Đối với bước thứ nhất trong khai phá luật kết hợp, ta lại cĩ thể chia ra làm 2 bước con: sinh tập chỉ mục ứng viên (candidate frequent itemsets) và sinh tập chỉ mục phổ biến (frequent itemsets). Trong đa số trường hợp, số lượng tập chỉ mục phổ biến sinh ra là rất lớn, kéo theo số lượng luật kết hợp tạo ra thường là hàng nghìn, thậm chí hàng triệu luật. Người dùng cuối gần như khơng thể hiểu hoặc đánh giá hết được một lượng lớn luật phức tạp như trên, do đĩ hạn chế phần nào giá trị của kết quả thu được. Hiện nay đã cĩ rất nhiều thuật tốn hiệu quả được đưa ra để giải quyết vấn đề này, bằng cách chỉ sinh luật phù hợp với nhu cầu của người dùng (interest rules), sinh luật “khơng dư thừa” (“non-redundant” rules), hoặc chỉ sinh luật thỏa mãn một tiêu chuẩn cụ thể nào đĩ như coverage, leverage, lift hoặc strength. Phần dưới đây sau khi trình bày các khái niệm cơ sở trong lý thuyết khai phá luật kết hợp, sẽ giới thiệu về một thuật tốn kinh điển dùng để sinh luật kết hợp là Apriori. 2.2. Các khái niệm cơ sở: Cho tập hợp I = {I1, I2, I3, …, In} gồm n phần tử khác nhau, I được gọi là tập chỉ mục (itemset), T là một giao tác (transaction) chứa một tập các phần tử thuộc I (T ⊆ I), D là một cơ sở dữ liệu chứa m giao tác T khác nhau. Một luật kết hợp là một phát biểu cĩ dạng X→Y, trong đĩ X ⊆ I, Y ⊆ I và X∩Y=Ø. Vế phải X được gọi là tiền đề, cịn vế trái Y gọi là kết luận của luật. Cĩ hai độ đo cơ bản cho luật kết hợp, đĩ là độ hỗ trợ (support) và độ tin cậy (confidence). 10 Độ hỗ trợ một tập chỉ mục X trong D, kí kiệu supp(X), được tính bằng phần trăm số giao tác T trong D cĩ chứa X (hay cịn gọi là hỗ trợ X). . Giả sử độ hỗ trợ của một phần tử là 0,1%, điều đĩ cĩ nghĩa là chỉ cĩ 0,1% số giao tác cĩ chứa phần tử đĩ. Độ hỗ trợ của một luật kết hợp r = X→Y, kí hiệu supp(r), biểu thị tần số luật cĩ trong các giao tác. Độ hỗ trợ thể hiện trong bao nhiêu phần trăm dữ liệu thì những điều ở vế trái và vế phải cùng xảy ra. Như vậy, độ hỗ trợ chính là xác xuất P(X∪Y): Độ tin cậy của một luật kết hợp r = X→Y, kí hiệu conf(r), là số phần trăm các giao tác trong D chứa cả X và Y trên số giao tác trong D chứa X. Độ tin cậy chính là xác xuất cĩ điều kiện P(Y|X), nĩ thể hiện nếu vế trái xảy ra thì cĩ bao nhiêu khả năng vế phải cũng xảy ra : Độ tin cậy biểu thị độ mạnh của một luật kết hợp, giả sử độ tin cậy của luật r bằng 80%, cĩ nghĩa là 80% số giao tác cĩ chứa X thì cũng chứa Y. Do cơ sở dữ liệu cĩ kích thước lớn và người dùng thường chỉ quan tâm tới một tập các phần tử nhất định, do vậy người ta đưa ra các ngưỡng giá trị cho độ hỗ trợ và độ tin cậy nhằm loại bỏ các luật khơng phù hợp với yêu cầu của người dùng hoặc các luật vơ dụng. Hai ngưỡng này được gọi là độ hỗ trợ cực tiểu (minimum support) và độ tin cậy cực tiểu (minimum confidence). 11 Tập chỉ mục X cĩ supp(X) ≥ minsupp, với minsupp là độ hỗ trợ cực tiểu, được gọi là tập chỉ mục phổ biến (frequent itemset hay large itemset). Một số tính chất điển hình của tập mục phổ biến: • Nếu A⊆B với A, B là các tập chỉ mục thì supp(A) ≥ supp(B). • Một tập chứa một tập khơng phổ biến thì cũng là tập khơng phổ biến. • Các tập con của tập phổ biến cũng là tập phổ biến. Các luật kết hợp thoả mãn cả hai ngưỡng độ hỗ trợ cực tiểu (minsupp) và độ tin cậy cực tiểu (minconf) được gọi là luật kết hợp mạnh (strong), tức là supp(X→Y) ≥ minsupp và conf(X∪Y) ≥ minconf. Người ta thường viết giá trị các độ hỗ trợ và độ tin cậy này giữa 0% và 100% thay cho 0 tới 1. Nếu độ hỗ trợ cực tiểu minsupp cĩ giá trị cao thì ta sẽ thu được ít tập chỉ mục phổ biến, do vậy sẽ cĩ ít luật hợp lệ phổ biến xuất hiện; cịn ngược lại nếu đặt minsupp thấp thì sẽ xuất hiện nhiều luật hợp lệ hiếm. Cịn đối với độ tin cậy cực tiểu minconf, nếu giá trị minconf cao thì thu được ít luật, nhưng tất cả các luật này "gần như đúng". Cịn nếu minconf cĩ giá trị thấp thì ta thu được rất nhiều luật nhưng phần lớn "rất khơng chắc chắn". Trong thực tế, người ta thường đặt giá trị minsupp trong khoảng 2-10% và minconf trong khoảng 70-90%. Ta đi vào xem xét một ví dụ nhỏ tương tự như bài tốn phân tích bán hàng trong siêu thị do Rakesh Agrawal đưa ra trong [5]. Giả sử cĩ một cơ sở dữ liệu nhỏ chứa các giao tác như sau: 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ị Transaction ID Sữa Bánh mì Bơ Bia Táo Khăn 1 1 1 0 0 1 1 2 0 1 1 0 1 1 3 0 0 0 1 1 0 4 1 1 1 0 1 1 12 5 0 1 1 0 0 0 Mỗi một hàng ứng với một giao tác, mỗi giao tác là một danh sách các mặt hàng được mua trong một lượt mua hàng của khách tại siêu thị. Giá trị 1 cĩ nghĩa là mặt hàng đĩ được mua, cịn 0 cĩ nghĩa là khơng được mua. Tập chỉ mục ở đây là I = {sữa, bánh mì, bơ, bia, táo, khăn}. Cơ sở dữ liệu D = {T1, T2, T3, T4, T5}, gồm 5 giao tác. Xét một luật kết hợp X→Y sau: {bánh mì, bơ}→{khăn} X = {bánh mì, bơ}. Các giao tác hỗ trợ X là T2, T4, T5 ⇒ supp(X) = 3/5 = 0.6 = 60% Y = {khăn}, các giao tác hỗ trợ Y là T1, T2, T4 ⇒ supp(Y) = 3/5 = 0.6 = 60% X∪Y = {bánh mì, bơ, khăn}, các giao tác hỗ trợ X∪Y là T2, T4 ⇒ supp(X∪Y) = 2/5 = 0.4 = 40% supp(X→Y) = supp(X∪Y) = 0.4 = 40% conf(X→Y) = supp(X∪Y)/supp(X) = 0.4/0.6 = 0.66 = 66% Luật kết hợp trên thể hiện "nếu khách hàng mua bánh mì và bơ thì người đĩ sẽ mua khăn trong 66% trường hợp. Bánh mì, bơ và khăn được mua chung trong 40% giao tác". Nếu đặt minsupp = 2% thì tập X = {bánh mì, bơ} là một tập chỉ mục phổ biến. Đặt minconf = 60% thì X→Y là một luật mạnh. 2.3. Thuật tốn Apriori: Hiện nay, Apriori [4] là thuật tốn khai phá luật kết hợp nổi tiếng, sử dụng chiến lược tìm kiếm theo chiều rộng (Breath-first search) để tính độ hỗ trợ của các tập chỉ mục và tận dụng bổ đề downward closure [4] để tìm ra các tập ứng viên. Apriori rất hiệu quả trong quá trình sinh tập ứng viên do áp dụng sử dụng kĩ thuật cắt tỉa để tránh phải đánh giá một số tập chỉ mục nhất định mà vẫn bảo đảm tính tồn vẹn. Phần dưới đây sẽ trình bày về các nội dung chính của thuật tốn Apriori: ý tưởng, cài đặt và một số hạn chế cịn tồn tại của thuật tốn. Ý tưởng chính của thuật tốn Apriori: 13 • Tạo ra các tập chỉ mục phổ biến cĩ 1 phần tử, rồi tiếp đến là 2 phần tử, 3 phần tử... cho đến khi chúng ta tạo ra tập chỉ mục phổ biến của mọi kích thước. • Mỗi tập chỉ mục được tạo ra phải được tính tốn độ hỗ trợ. • Tập chỉ mục phổ biến k phần tử được tạo ra từ tập phổ biến k-1 phần tử. Bằng cách, nối từng đơi một tập chỉ mục phổ biến k-1 phần tử đã cĩ để tạo ra tập ứng viên k phần tử. Sau đĩ, những tập ứng viên nào cĩ chứa một tập con khơng phải là phổ biến sẽ bị loại bỏ. Apriori khác các thuật tốn khác ở quá trình sinh tập ứng viên: chỉ sử dụng các tập chỉ mục đã được thấy là phổ biến trong lần duyệt trước để tìm các tập ứng viên mà khơng cần quan tâm đến các giao tác trong cơ sở dữ liệu. Cơ sở để cho ý tưởng trên dựa vào các tiên đề sau: • Các tập con của tập chỉ mục phổ biến cũng là tập chỉ mục phổ biến [4]. Ví dụ, nếu {AB} là một tập phổ biến thì {A} và {B} cũng là những tập phổ biến. • Một tập chứa một tập khơng phổ biến thì cũng là tập khơng phổ biến (downward closure lemma [4]). Ví dụ, nếu {C} là tập khơng phổ biến thì {AC} cũng là tập khơng phổ biến. Vì vậy, các tập ứng viên k phần tử được sinh ra bằng cách nối các tập phổ biến cĩ k- 1 phần tử lại. Sau đĩ những tập ứng viên nào cĩ chứa một tập con khơng phải là phổ biến sẽ bị loại bỏ. Phương pháp này sinh ra số lượng tập ứng viên nhỏ hơn rất nhiều so với cách duyệt hết dữ liệu, nĩi cách khác nĩ khá hiệu quả trong việc "tỉa gọn" khơng gian tìm kiếm. Cài đặt thuật tốn Apriori : Bảng 2. Bảng kí hiệu cho thuật tốn Apriori k-itemset Tập chỉ mục cĩ k phần tử. Lk (lagre k-itemset) Tập chỉ mục phổ biến cĩ k phần tử. Mỗi phần tử thuộc tập này sẽ cĩ 2 thuộc tính: i. itemset (tập chỉ mục) ii. count (biến đếm để đo độ hỗ trợ) 14 Ck Tập chỉ mục ứng viên cĩ k phần tử. Mỗi phần tử thuộc tập này cũng cĩ 2 thuộc tính: i. itemset (tập chỉ mục) ii. count (biến đếm để đo độ hỗ trợ) Thuật tốn Apriori: Input: Cơ sở dữ liệu D và độ hỗ trợ cực tiểu minsupp. Output: Tập chỉ mục phổ biến trong D. Giả mã [4]: 1) L1 = {large 1-itemsets}; 2) for ( k = 2; Lk-1 ≠ Ø; k++ ) do begin 3) Ck = apriori-gen(Lk-1); // Sinh tập ứng viên mới 4) forall transactions t ∈ D do begin 5) Ct = subset(Ck , t); // Tập ứng viên thuộc t 6) forall candidates c ∈ Ct do 7) c.count++; 8) end 9) Lk = {c ∈ Ck | c.count ≥ minsupp} 10) end 11) Answer = ; Hàm apriori-gen: nhận tham số đầu vào là Lk-1 và trả lại kết quả là một tập chứa tất cả các tập chỉ mục phổ biến cĩ k phần tử Lk. Hàm này thực hiện như sau : • Bước 1 kết hợp: để tìm Lk , tập Ck được sinh ra bởi việc nối Lk-1 với chính nĩ. Thành phần l1 và l2 của Lk-1 được nối nếu: (l1[1] = l2[1]) ∧ (l1[2] = l2[2]) ∧ ...( l1[k-2] = l2[k-2]) ∧ (l1[k-1] < l2[k-1]) Kết quả thu được cĩ dạng: l1[1] l1[2] ... l1[k-2] l1[k-1] l2[k-1]. 1) insert into Ck 2) select p.item1, p.item2,..., p.itemk-1, q.itemk-1 3) from Lk-1 p, Lk-1 q 4) where p.item1 = q.item1, . . ., p.itemk-2 = q.itemk-2, 5) p.itemk-1 < q.itemk-1; 15 • Bước 2 rút gọn: dựa vào tính chất "Những tập kích thước (k-1) khơng phổ biến khơng thể là tập con của tập phổ biến kích thước k " để tiến hành "cắt tỉa", rút gọn kích thước Ck. Nếu một phần tử của Ck cĩ tập con k-1 phần tử khơng thuộc Lk-1 thì phần tử đĩ khơng phải là phổ biến và bị loại khỏi Ck. 6) forall k-itemsets c ∈ Ck do 7) forall (k-1)-subsets s of c do 8) if (s ∉ Lk-1) then 9) delete c from Ck; Hàm subset: nhận tham số đầu vào là Ck và một giao tác t ∈ D, trả lại tất cả phần tử của Ck cĩ mặt trong t. Việc này được thực hiện bằng cách: • Lưu Ck vào một cây băm (hash-tree [15]) trong đĩ, mỗi một node sẽ chứa một danh sách các tập chỉ mục c ∈ Ck (leaf node - lá) hoặc một bảng băm (interior node - nút trong). Ban đầu mọi node đều được khởi tạo là lá, sau khi số tập chỉ mục của một lá đạt đến một ngưỡng xác định nào đĩ thì lá được chuyển thành nút trong. Để thêm một tập c vào cây, ta đi từ gốc xuống lá, sử dụng hàm băm cho các nút trong để xác định hướng đi. • Duyệt cây từ gốc cho tới các lá, lấy mọi phần tử thuộc t tại lá và đưa vào tập kết quả. Ví dụ minh họa: Giả sử cĩ cơ sở dữ liệu giao tác như bên dưới [11], độ hỗ trợ cực tiểu minsupp là 40%, hãy tìm tất cả các tập chỉ mục phổ biến. Bảng 3. Bảng cơ sở dữ liệu giao tác minh họa cho thuật tốn Apriori Transaction ID A B C D E T1 1 1 1 0 0 T2 1 1 1 1 1 T3 1 0 1 1 0 T4 1 0 1 1 1 T5 1 1 1 1 0 Áp dụng thuật tốn Apriori : 16 Duyệt dữ liệu lần 1: Bảng 4. Bảng kết quả C1, L1 C1 L1 itemset X supp(X) itemset X supp(X) A 100% A 100% B 60% B 60% C 100% C 100% D 80% D 80% E 40% E 40% Duyệt dữ liệu lần 2: Bảng 5. Bảng kết quả C2, L2 C2 L2 itemset X supp(X) itemset X supp(X) A, B 60% A, B 60% A, C 100% A, C 100% A, D 80% A, D 80% A, E 40% A, E 40% B, C 60% B, C 60% B, D 40% B, D 40% B, E 20% B, E loại C, D 80% C, D 80% C, E 40% C, E 40% D, E 40% D, E 40% BE bị loại do supp(BE) = 20% < minsupp = 40%. Duyệt dữ liệu lần 3: Để tạo ra C3, chỉ cần tìm xem xét các tập chỉ mục cĩ phần tử đầu tiên giống nhau (với lần duyệt thứ k, cần k-2 phần tử đầu tiên giống nhau) 17 Bảng 6. Bảng kết quả C3, L3 C3 L3 itemset X supp(X) itemset X supp(X) Nối AB với AC A, B, C 60% A, B, C 60% Nối AB với AD A, B, D 40% A, B, D 40% Nối AB với AE A, B, E loại A, B, E loại Nối AC với AD A, C, D 80% A, C, D 80% Nối AC với AE A, C, E 40% A, C, E 40% Nối AD với AE A, D, E 40% A, D, E 40% Nối BC với BD B, C, D 40% B, C, D 40% Nối CD với CE C, D, E 40% C, D, E 40% ABE bị loại do BE khơng phải là tập phổ biến. Duyệt dữ liệu lần 4: Bảng 7. Bảng kết quả C4, L4 C4 L4 itemset X supp(X) itemset X supp(X) Nối ABC với ABD A, B, C, D 40% A, B, C 40% Nối ACD với ACE A, C, D, E 40% A, B, D 40% Duyệt dữ liệu lần 5: Trong lần duyệt này, chúng ta khơng thể tạo ra tập ứng viên nào nữa do khơng cịn 2 tập phổ biến 4 phần tử nào cĩ 3 phần tử đầu tiên giống nhau. Thuật tốn Apriori dừng ở đây. Kết luận: 18 Apriori là một thuật tốn linh hoạt và hiệu quả trong việc tìm các tập chỉ mục phổ biến trong khai phá luật kết hợp. Ngồi ra, đây cịn là một thuật tốn dễ cài đặt. Tuy nhiên, vẫn cịn 2 hạn chế trong thuật tốn này. Một là độ phức tạp của quá trình sinh tập ứng viên gây tốn nhiều thời gian và bộ nhớ. Ví dụ: 104 tập chỉ mục phổ biến 1 phần tử sẽ tạo ra 107 tập ứng viên 2 phần tử. Để phát hiện một tập phổ biến kích thước 100 thì cần tạo ra 2100 ≈1030 tập ứng viên (một con số khổng lồ). Hai là số lần duyệt cơ sở dữ liệu của thuật tốn Apriori phụ thuộc vào độ dài của tập phổ biến dài nhất tìm được. Các vấn đề trên cĩ thể gây ra tình trạng nghẽn cổ chai cho thuật tốn Apriori. Hiện nay, cĩ khá nhiều thuật tốn mới được cải tiến dựa trên Apriori. 2.4. Tổng kết chương: Trong chương này, chúng ta đã xem xét các vấn đề cơ bản của lý thuyết khai phá luật kết hợp theo hướng ứng dụng vào bài tố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 ta đã hiểu được tư tưởng chủ đạo của khai phá luật kết hợp và thấy được khả năng tìm kiếm các tập phổ biến của thuật tốn Apriori dựa trên hai tiền đề quan trọng. Áp dụng thuật tốn Apriori vào bài tốn của khĩa luận, kết hợp một số kĩ thuật xử lý ngơn ngữ tự nhiên, chúng ta sẽ tìm được tập các thuộc tính phổ biến của sản phẩm từ cơ sở dữ liệu các đánh giá của người dùng trên mạng. Chương đầu đã giới thiệu về bài tốn tĩm tắt đánh giá sản phẩm nĩi chung và bài tốn trích chọn thuộc tính sản phẩm trên hệ thống mua bán trực tuyến nĩi riêng. Chương tiếp theo sẽ đề cập đến bài tốn chính của khố luận một cách chi tiết, phân tích những vấn đề sẽ gặp phải với bài tốn trích chọn thuộc tính sản phẩm trên hệ thống mua bán trực tuyến. Và cũng trong chương tới, chúng ta sẽ xem xét việc xây dựng bộ trích chọn thuộc tính sản phẩm áp dụng thuật tốn Apriori. 19 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 3.1. Giới thiệu: Trong chương một, chúng tơi đã giới thiệu một cách tổng quát về bài tốn trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến, về các nhu cầu thực tế, ứng dụng cũng như ý nghĩa của bài tốn. Chương này sẽ trình bày việc giải quyết bài tốn trích chọn thuộc tính sản phẩm, phân tích đầy đủ các thách thức đối với bài tốn và đưa ra các hướng giải quyết cụ thể cho các vấn đề đĩ. Đồng thời, chương này cũng đưa ra mơ hình trích chọn thuộc tính sản phẩm áp dụng khai phá luật kết hợp cùng với một số kĩ thuật xử lý ngơn ngữ tự nhiên. 3.2. Bài tố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ư đã phân tích ở phần trước, nhu cầu tĩm tắt các đá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 sẽ ngày càng gia tăng. Vì vậy bài tốn tĩm tắt đánh giá sản phẩm ra đời, trong đĩ bài tốn trích chọn thuộc tính sản phẩm là một vấn đề khĩ khăn và cần phải giải quyết nhất. Đây là bài tốn liên quan tới lĩnh vực trích chọn từ khĩa (terminology extraction), một lĩnh vực con của trích chọn thơng tin (information extraction). Do vậy chúng ta phải giải quyết những vấn đề chính sau: • Tự động trích chọn các thực thể trong văn bản: ta cần tìm được tập các từ hoặc cụm từ cĩ thể là thuộc tính của sản phẩm trong tất cả các đánh giá của người dùng (tập thực thể này được gọi là tập ứng viên). • Sau đĩ, từ tập ứng viên trên, ta cần xác định được các thuộc tính sản phẩm (chính là các terminology). Vấn đề cốt lõi của bài tốn là tìm ra chiến lược trích chọn thuộc tính tốt nhất. 20 5.2.1. Tự động trích chọn các thực thể trong văn bản: Mỗi một đánh giá về sản phẩm của người dùng là một văn bản mà ta cần xử lý, các thuộc tính sản phẩm xuất hiện trong đĩ sẽ là các thực thể cần được trích chọn. Qua quan sát dữ liệu cho thấy các thuộc tính sản phẩm thường xuất hiện dưới dạng là một danh từ, do đĩ để trích chọn được chúng ta cĩ thể căn cứ vào dấu hiệu đĩ. Để làm được như vậy chúng ta cần một bộ gán nhãn từ loại. Khĩ khăn gặp phải là hiện nay lĩnh vực xử lý tiếng Việt cịn hạn chế cả về mặt số lượng nghiên cứu cũng như kết quả đạt được [2]. Trong khĩa luận này, chúng tơi sử dụng hai chương trình xử lý ngơn ngữ tiếng Việt đã cĩ là JVnSegmenter [7] và VnQTAG [3] để thực hiện việc tách từ và gán nhãn. Chi tiết sẽ được trình bày trong mơ hình hệ thống đề xuất. 5.2.2. Xác định thuộc tính của sản phẩm từ tập ứng viên: Trong bài tốn trích chọn từ khĩa (terminology extraction), về cơ bản cĩ hai loại kĩ thuật chính để xác định các từ khĩa trong tập văn bản: một là các kĩ thuật hình thức dựa trên mơ tả ngữ nghĩa của từ khĩa, thường là các cụm danh từ, hai là các kĩ thuật thống kê, các kĩ thuật loại này dựa trên thực tế là các từ ghép thành một từ khĩa thì thường được tìm thấy cạnh nhau và lặp lại nhiều lần để tiến hành việc trích chọn. Tuy nhiên cả hai phương pháp trên đều cĩ những hạn chế của riêng mình. Trong phương pháp hình thức, việc sử dụng các cụm danh từ để trích chọn thường tạo ra quá nhiều các kết quả khơng phải là từ khĩa cần tìm. Thêm vào đĩ, hiện nay việc xác định các cụm danh từ tiếng Việt cịn rất hạn chế trong kết quả đạt được. Cịn đối với phương pháp thống kê, trích chọn theo các cụm từ cĩ xác suất xuất hiện cao thì hạn chế gặp phải là thường bỏ xĩt quá nhiều các từ khĩa cĩ số lần xuất hiện thấp, các từ khĩa cĩ nhiều cách viết khác nhau và các từ khĩa chỉ gồm một từ. Để khắc phục các hạn chế trên, trong khĩa luận này chúng tơi sử dụng mơ hình áp dụng kĩ thuật khai phá luật kết hợp trong đĩ áp dụng thuật tốn Apriori kết hợp thêm một số kĩ thuật rút gọn, cắt tỉa khác để tìm ra tập các từ khĩa phổ biến (các thuộc tính cĩ xác suất xuất hiện cao). Ngồi ra trong mơ hình này chúng tơi cịn thực hiện việc tìm kiếm các thuộc tính ít phổ biến dựa trên ý kiến đánh giá của người dùng. Phần dưới đây sẽ trình bày về mơ hình trích chọn thuộc tính sản phẩm dựa trên khai phá luật kết hợp. 21 3.3. Mơ hình trích chọn thuộc tính sản phẩm: Đối với bài tốn trích chọn thuộc tính sản phẩm được người mua hàng đánh giá trong hệ thống bán hàng trực tuyến, khĩa luận này sử dụng mơ hình tương tự như trong hệ thống [13]. 3.3.1. Cấu trúc hệ thống trích chọn thuộc tính sản phẩm: 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. Đầu tiên, ta tiến hành thu thập đá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 để đưa vào cơ sở dữ liệu các đánh giá. Việc thu thập dữ liệu cĩ thể tiến hành tự động bằng cách crawl các đánh giá sản phẩm từ một website bán hàng trực tuyến về. Dữ liệu thu được sẽ được xử lý để tách từ, gán nhãn từ loại rồi đưa vào module trích chọn các thuộc tính phổ biến, kết quả thu được là một tập các thuộc tính CSDL các từ thể hiện ý kiến CSDL thuộc tính ít phổ biến Đánh giá sản phẩm CSDL các đánh giá CSDL thuộc tính phổ biến Trích chọn thuộc tính Tách từ Gán nhãn từ loại Trích chọn các thuộc tính phổ biến Trích chọn các thuộc tính ít phổ biến Trích chọn các từ thể hiện ý kiến 22 được nhiều người đánh giá (phổ biến ở đây cĩ nghĩa là xuất hiện nhiều). Dựa vào kết quả trên, trích chọn ra các từ thể hiện ý kiến và cuối cùng là xác định các thuộc tính ít phổ biến (cĩ số lần xuất hiện thấp). Theo mơ hình trên, cơng việc giải quyết bài tốn sẽ được chia làm 5 bước chính sau: • Tách từ. • Gán nhãn từ loại. • Trích chọn các thuộc tính phổ biến của sản phẩm. • Trích chọn các từ thể hiện ý kiến. • Cuối cùng là tìm các thuộc tính ít phổ biến. 3.3.2. Tách từ: Bước đầu tiên trong quá trình trích chọn thuộc tính sản phẩm là tách từ. Đối với tiếng Anh, các từ được phân cách bởi dấu cách hoặc. Tuy nhiên, với tiếng Việt thì khơng đơn giản như vậy, một từ tiếng Việt cĩ thể gồm nhiều hơn một âm tiết. Do đĩ khơng phải lúc nào ta cũng cĩ thể tiến hành tách từ dựa vào dấu cách. Sau khi tìm hiểu một số chương trình tách từ, chúng tơi sử dụng chương trình JVnSegmenter của nhĩm nghiên cứu [7], đây là chương trình tách từ tiếng Việt sử dụng mơ hình CRFs (conditional random fields) cho kết quả cĩ độ chính xác cao. Ví dụ: Câu = “Nokia N81 đời mới gồm 2 phiên bản: N81 8GB và N81 2GB” Sau khi qua cơng đoạn tách từ, ta cĩ các từ tiếng Việt trong cặp ngoặc như sau: [Nokia] [N81] [đời mới] [gồm] [2] [phiên bản]: [N81] [8GB] [và] [N81 2GB] Do chất lượng dữ liệu tiếng Việt cịn chưa cao, người dùng khi bày tỏ ý kiến của mình qua mạng thường vi phạm một trong các lỗi như viết tiếng Việt khơng dấu, cú pháp khơng chuẩn, sai chính tả… vì vậy, trước khi dữ liệu được đưa qua JVnSegmenter, chúng ta cần tiến hành một số bước tiền xử lý như thêm dấu câu, chỉnh sửa các lỗi chính tả, loại bỏ các kí tự khơng cĩ ý nghĩa (ví dụ một số người cĩ thĩi quen sử dụng các kí tự biểu hiện cảm xúc của ngơn ngữ chat vào trong cả cách viết bình thường, đối với bài tốn của chúng ta, các từ này khơng cung cấp thơng tin cần thiết nên sẽ bị loại bỏ). 23 3.3.3. Gán nhãn loại từ: Dữ liệu sau khi được tách từ, sẽ được tiến hành gán nhãn từ loại (phân biệt danh từ, tính từ, động từ, …). Trong khĩa luận này, chúng tơi sử dụng chương trình VnQTAG của nhĩm tác giả [3] để tiến hành cơng việc trên. VnQTAG được nhĩm tác giả trên chỉnh sửa lại thành phiên bản dùng cho tiếng Việt từ phần mếm QTAG của nhĩm tác giả O. Mason, Đại học Bermingham, Anh. QTAG là một bộ gán nhãn xác suất độc lập với ngơn ngữ. Phương pháp xử lý của QTAG cĩ thể mơ tả tổng quát như sau. Dựa vào kho dữ liệu đã được gán nhãn bằng tay, bộ gán nhãn tìm những nhãn cĩ thể được và tần số của nĩ cho từng từ trong kho dữ liệu mới đã được tách từ. Nếu việc tìm kiếm một từ trong danh sách từ vựng đã học thất bại thì tất cả các nhãn sẽ được gán cho từ đĩ. Cuối cùng, bộ gán nhãn thực hiện bước loại bỏ nhập nhằng bằng cách sử dụng thơng tin về xác suất phân bố từ vựng đã được học trước đĩ. Dữ liệu đầu vào của chương trình VnQTAG là văn bản đã được phân tách từ trong từng câu (kết quả của bước tách từ ở phần trên), kết quả đầu ra của chương trình là một từ loại tương ứng sẽ được gán cho từng từ trong văn bản. Hệ thống sử dụng đồng thời từ điển để liệt kê các từ loại cĩ thể cho một từ, và một kho văn bản mẫu để loại bỏ nhập nhằng. Ví dụ về kết quả thu được sau khi đưa dữ liệu qua VnQTAG: hồi lên sáu <w pos=","> , cĩ lần tơi đã nhìn thấy <w pos="Nn"> một bức tranh <w pos="Jd"> tuyệt đẹp Hạn chế cịn tồn tại của VnQTAG chính là chương trình chưa cĩ khả năng nhận diện các cụm danh từ, việc gán nhãn từ loại mới chỉ xác định được các danh từ. Trong khi bài tốn của chúng ta yêu cầu cần xác định cả các cụm danh từ (điều này sẽ được giải thích cụ thể trong phần sau). Đây là một vấn đề khĩ cần được giải quyết; trong hệ thống trích chọn thuộc tính sản phẩm sử dụng khai phá luật kết hợp, chúng tơi mới chỉ cĩ thể xác định được một số cụm danh từ nhất định. 24 3.3.4. Trích chọn thuộc tính phổ biến: Mục tiêu của bước này là xác định được các thuộc tính của sản phẩm được nhiều người dùng nhận xét (chúng tơi gọi là các thuộc tính phổ biến). Tuy nhiên, do độ phức tạp về ý nghĩa của ngơn ngữ tự nhiên nên ở đây chúng tơi chỉ tập trung vào các thuộc tính xuất hiện một cách rõ ràng trong câu. Khái niệm rõ ràng được hiểu như sau: • “Chất lượng ảnh chụp rất tốt” – thuộc tính “chất lượng ảnh” là rõ ràng. • “Mặc dù đắt, nhưng tơi vẫn quyết định mua.” – thuộc tính “giá bán” là khơng rõ ràng, hệ thống khơng xác định được các thuộc tính kiểu này. Do số lượng các thuộc tính khơng rõ ràng trong các đánh giá ít hơn thuộc tính rõ ràng nên việc bỏ qua các thuộc tính kiểu này khơng làm ảnh hưởng nhiều tới kết quả. Để tìm ra các thuộc tính phổ biến, chúng tơi sử dụng kĩ thuật khai phá luật kết hợp trong đĩ tập chỉ mục là tập các thuộc tính sản phẩm, mỗi một câu trong đánh giá là một giao tác, cịn cơ sở dữ liệu giao tác chính là tập các đánh giá đầu vào. Qua việc khảo sát các đánh giá sản phẩm trên các hệ thống mua bán trực tuyến, chúng tơi rút ra kết luận: hầu hết các thuộc tính của sản phẩm xuất hiện trong các đánh giá đều ở dạng danh từ hoặc cụm danh từ. Vì vậy, ở đây chúng tơi chỉ tập trung vào việc khai phá luật kết hợp trên tập các danh từ và cụm danh từ cĩ mặt trong đánh giá sản phẩm. Phương pháp thực hiện sẽ gồm 3 bước như sau. Bước một, sinh tập chỉ mục, hệ thống thực hiện trích chọn ra các danh từ trong tập dữ liệu các đánh giá sản phẩm đã được gán nhãn từ loại ở bước trên. Dựa vào các danh từ này chúng tơi tạo ra một file giao tác. File này cĩ cấu trúc như sau: mỗi dịng trong file là một dãy các kí tự 0, 1 cách nhau bởi dấu cách, cĩ độ dài bằng nhau và bằng số danh từ tìm được ở trên, thể hiện cho một câu trong tập các đánh giá sản phẩm. Mỗi một số trong dãy 0, 1 thể hiện sự xuát hiện của một danh từ trong câu: 0 cĩ nghĩa là danh từ đĩ khơng xuất hiện trong câu, cịn 1 là cĩ xuất hiện. File giao tác này chính là cơ sở dữ liệu giao tác sẽ dùng trong thuật tốn Apriori ở bước sau. Bước hai, áp dụng thuật tốn Apriori trên tập chỉ mục và cơ sở dữ liệu giao tác thu được ở bước trên, ta sẽ thu được các tập chỉ mục phổ biến (frequent itemsets), mỗi đối tượng thuộc các tập này cĩ khả năng là một thuộc tính của sản phẩm. Một tập chỉ mục được coi là phổ biến khi các từ trong tập này xuất hiện ít nhất trong c% số câu của tập dữ liệu (minimum support = c%, c là giá trị do chúng ta định trước). Chú ý ở bước này, 25 chúng ta sẽ khơng chạy thuật tốn Apriori để tìm hết tất cả các tập phổ biến mà chỉ tìm các tập phổ biến cĩ độ dài trong giới hạn xác định, bởi vì các thuộc tính của sản phẩm cũng cĩ giới hạn về số từ (trong khảo sát các đánh giá sản phẩm điện thoại, chúng tơi nhận thấy độ dài tối đa của một thuộc tính là 5 từ - ví dụ như cụm danh từ sau “màn hình tinh cảm ứng”). Vì vậy chúng tơi sẽ đưa ra ngưỡng giới hạn độ dài tối đa của tập chỉ mục phổ biến cần tìm. Nhờ vậy tiết kiệm được thời gian và cơng sức. Sau khi tìm được các tập chỉ mục phổ biến, hệ thống thực hiện bước 3: “cắt tỉa” các đối tượng khơng phải thuộc tính. Việc “cắt tỉa” gồm 2 bước con: • Compactness pruning (cắt tỉa bảo đảm tính chặt chẽ): trong bước này, chúng tơi kiểm tra các thuộc tính cĩ nhiều hơn 2 từ trở lên để loại bỏ những cụm từ vơ nghĩa. Nguyên nhân là do khi thực hiện khai phá luật kết hợp, thuật tốn chỉ quan tâm tới số lần xuất hiện của các từ, tức là độ hỗ trợ của từ, chứ khơng quan tâm tới vị trí xuất hiện của từ trong câu, điều này dẫn tới khả năng trong các tập chỉ mục phổ biến tìm được cĩ chứa nhiều cụm từ vơ nghĩa. Ví dụ: cĩ tập chỉ mục phổ biến 1 phần tử {hệ điều hành, Symbian}. Khi áp dụng thuật tốn Apriori để tìm tập chỉ mục phổ biến 2 phần tử, giả sử ta thu được kết quả là {hệ điều hành Symbian, Symbian hệ điều hành}. Ta thấy ngay chỉ cĩ "hệ điều hành Symbian" mới là thuộc tính cần tìm, cịn "Symbian hệ điều hành" là một cụm từ vơ nghĩa phải loại bỏ. Để loại bỏ được các kết quả vơ nghĩa, chúng tơi đưa ra khái niệm "cụm từ chặt chẽ" như sau: + giả sử f là một cụm từ phổ biến gồm n từ tạo ra từ thuật tốn Apriori, f={w1, w2, …,wn}. Nếu tồn tại một câu s chứa tồn bộ w1, w2, …,wn và khoảng cách giữa wi và wi+1 trong s khơng quá 3 thì f được coi là "chặt" đối với s. + Nếu f xuất hiện trong m câu thuộc tập dữ liệu đánh giá, và f là "chặt" đối với ít nhất 2 trong m câu trên thì f là một cụm từ chặt chẽ. Đối với những cụm từ khơng thỏa mãn điều kiện chặt chẽ trên, hệ thống sẽ tiến hành loại bỏ khỏi tập thuộc tính phổ biến. • Redundancy pruning (cắt tỉa dư thừa): bước này tập trung vào loại bỏ các thuộc tính thừa (những thuộc tính là danh từ đơn). Ví dụ về một thuộc tính dư thừa như sau: trong bản đánh giá về sản phẩm điện thoại X, người tiêu dùng đề cập tới “tuổi thọ pin 26 ngắn”, khi thực hiện tách từ, gán nhãn và sinh tập thuộc tính phổ biến, trong kết quả thu được cĩ 2 thuộc tính “tuổi thọ” và “tuổi thọ pin”. Ta thấy ở đây thuộc tính “tuổi thọ” là dư thừa do nĩ đĩng vai trị khơng quan trọng so với thuộc tính “tuổi thọ pin”. Vì vậy, hệ thống sẽ loại bỏ các thuộc tính thừa này. Tuy nhiên, khơng phải cứ cĩ một thuộc tính khác bao hàm mình thì thuộc tính con sẽ bị loại bỏ, bởi vì cĩ thể thuộc tính con vẫn mang ý nghĩa quan trọng. Ví dụ như ở trường hợp sau, “màn hình”, “màn hình chính”, “màn hình ngồi”, lúc này ta khơng thể loại bỏ thuộc tính “màn hình”. Để xác định một thuộc tính là dư thừa hay khơng, chúng tơi sử dụng độ đo pure support, cĩ thể dịch là độ hỗ trợ hồn tồn (kí hiệu là p-support). Độ đo p-support được định nghĩa như sau: p-support của một thuộc tính f được tính bằng phần trăm số câu trong đĩ chứa thuộc tính f mà khơng chứa các thuộc tính khác là cha của thuộc tính đĩ (f phải xuất hiện dưới dạng danh từ trong các câu này, nguyên nhân là do trong tiếng Việt, các từ khơng cĩ thay đổi dạng khi chuyển từ danh từ sang từ loại khác, vì thế để chắc chắn cụm từ f xuất hiện trong câu đúng là thuộc tính của sản phẩm thì f phải ở dạng danh từ); một thuộc tính được gọi là cha nếu thuộc tính đĩ cĩ bao hàm thuộc tính khác trong mình (ví dụ: "màn hình cảm ứng" là thuộc tính cha của thuộc tính "màn hình"). Chúng ta xem xét ví dụ sau để hiểu rõ hơn về p-support: trong tập dữ liệu đánh giá sản phẩm, thuộc tính “màn hình” cĩ độ hỗ trợ là 9% (xuất hiện trong 9% câu thuộc tập dữ liệu). “Màn hình” lại là tập con của cụm từ “màn hình cảm ứng”. Giả sử độ hỗ trợ của “màn hình cảm ứng” là 5%, thì p-support của thuộc tính “màn hình” sẽ là 4% (9% - 5%). Nếu một thuộc tính cĩ giá trị p-support nhỏ hơn ngưỡng p-support cực tiểu do ta đưa ra và tồn tại một thuộc tính cha của thuộc tính kia thì ta sẽ xếp nĩ vào dạng thuộc tính thừa và loại bỏ. Sau khi thực hiện 2 bước cắt tỉa, ta thu được tập các từ và cụm từ là thuộc tính phổ biến của sản phẩm. 3.3.5. Trích chọn từ thể hiện ý kiến: Từ thể hiện ý kiến là các từ dùng để biểu đạt ý kiến khen hay chê của người viết. Qua quá trình khảo sát các đánh giá sản phẩm trên hệ thống mua bán hàng trực tuyến, chúng tơi rút ra nhận xét là các từ thể hiện ý kiến thường là tính từ hoặc cụm tính từ xuất hiện gần các từ hoặc cụm từ chỉ thuộc tính của sản phẩm. Ví dụ như trong câu “phím bấm rất đẹp”, “đẹp” là tính từ thể hiện ý kiến, “phím bấm” là thuộc tính sản phẩm. Vì thế dựa vào tập các thuộc tính phổ biến tìm được ở bước trên, chúng ta cĩ thể trích xuất ra các từ 27 thể hiện ý kiến trong tập các đánh giá sản phẩm. Mục đích của bước này là để từ các từ thể hiện ý kiến này, chúng ta tìm ra được các thuộc tính ít phổ biến (điều này cũng dựa vào hai nhận xét rút ra từ quan sát thực tế: các từ thể hiện ý kiến và thuộc tính sản phẩm thường xuất hiện cùng nhau trong một câu; và người dùng cĩ xu hướng dùng cùng một tính từ để nhận xét về nhiều đối tượng khác nhau). Việc trích chọn các từ thể hiện ý kiến trong các đánh giá được tiến hành như sau: Đối với mỗi một câu trong cơ sở dữ liệu các đánh giá, nếu chứa bất kì thuộc tính phổ biến nào thì trích chọn ra tính từ ở gần thuộc tính đĩ, và tính từ đĩ được coi là từ thể hiện ý kiến. for mỗi câu trong CSDL các đánh giá if (nĩ chứa thuộc tính phổ biến) { Tìm tính từ gần thuộc tính sản phẩm nhất và lưu vào tập các từ thể hiện ý kiến. } 3.3.6. Trích chọn thuộc tính ít phổ biến: Định nghĩa thuộc tính ít phổ biến: trái với thuộc tính phổ biến là những thuộc tính được người dùng đánh giá nhiều nhất, thuộc tính khơng phổ biến là các thuộc tính chỉ được một số ít người dùng nhắc đến. Tuy nhiên, những thuộc tính này vẫn cĩ thể được một số khách hàng hoặc chính nhà sản xuất quan tâm muốn biết. Do vậy hệ thống vẫn phải trích chọn được những thuộc tính kiểu này. Cũng như đối với thuộc tính phổ biến, ở đây chúng tơi cũng chỉ tập trung vào các thuộc tính rõ ràng (khái niệm rõ ràng xem lại ở mục 3.3.4). Như đã đề cập đến ở phần trước, quan sát đánh giá sản phẩm trên hệ thống mua bán trực tuyến, chúng tơi rút ra hai nhận xét quan trọng sau: • Một là các từ thể hiện ý kiến thường xuất hiện cùng các từ chỉ thuộc tính sản phẩm trong một câu. 28 • Hai là người dùng cĩ thể dùng các tính từ giống nhau khi đánh giá các đối tượng khác nhau. Ví dụ: cùng một tính từ “đẹp” được dùng để nhận xét cho 2 thuộc tính khác nhau: “Nokia N81 cĩ thiết kế đẹp mắt” và “Chất lượng ảnh rất đẹp”. Do vậy, dựa vào các từ thể hiện ý kiến đi cùng các thuộc tính phổ biến, chúng ta cĩ thể tìm ra các thuộc tính ít phổ biến theo nguyên tắc bắc cầu. Việc trích chọn các thuộc tính ít phổ biến được thực hiện như sau, với tập các đánh giá sản phẩm, tập các thuộc tính phổ biến và tập các từ thể hiện ý kiến tìm được ở bước trên, ta thực hiện duyệt tất cả các câu trong tập đánh giá, nếu câu nào khơng chứa các thuộc tính phổ biến, nhưng cĩ các từ thể hiện ý kiến thì thực hiện trích chọn danh từ, cụm danh từ gần từ đĩ nhất và đưa vào tập các thuộc tính ít phổ biến: for mỗi câu trong CSDL các đánh giá if (nĩ khơng chứa thuộc tính phổ biến nhưng chứa từ thể hiện ý kiến) { Tìm danh từ hoặc cụm danh từ gần từ thể hiện ý kiến nhất và lưu kết quả vào tập các thuộc tính ít phổ biến. } Vấn đề gặp phải là việc trích chọn này cĩ thể đưa ra các danh từ hoặc cụm danh từ khơng phải thuộc tính của sản phẩm, nguyên nhân là do người dùng thường sử dụng tính từ để đánh giá mọi thứ, bao gồm cả sản phẩm và những thứ khơng liên quan (các đánh giá cĩ thể chứa cả những câu khơng liên quan tới sản phẩm). Tuy nhiên, đây khơng phải là vấn đề nghiêm trọng, do số lượng thuộc tính ít phổ biến chỉ chiếm một phần nhỏ tổng số thuộc tính trong thực nghiệm. Các thuộc tính ít phổ biến chỉ được sinh ra nhằm đảm bảo tính hồn thiện của hệ thống. 3.3.7. Đánh giá, nhận xét về mơ hình sử dụng: Mơ hình đưa ra trong khĩa luận cĩ nhiều ưu điểm như xác định được cả thuộc tính phổ biến và ít phổ biến một cách hiệu quả, tốc độ nhanh, khơng cần tập dữ liệu training. Tuy nhiên vẫn cịn tồn tại một số hạn chế chưa giải quyết được: 29 • Thứ nhất là việc xác định thuộc tính sản phẩm thực hiện ở mức độ từ, khơng xét đến các thơng tin ngữ nghĩa ở mức độ câu, do vậy hệ thống cĩ thể trích chọn ra các đối tượng khơng phải là thuộc tính của sản phẩm. • Hai là mơ hình mới chỉ tìm ra được các thuộc tính thuộc từ loại danh từ. • Thứ ba là vấn đề về từ đồng nghĩa, trong kết quả trích chọn cĩ thể cĩ các từ đồng nghĩa, do vậy chúng ta phải kết hợp chúng lại làm một nhĩm. Phương pháp giải quyết hiện tại đối với tiếng Anh là sử dụng một bộ từ điển đơn ngữ, sử dụng WordNet [8], sử dụng từ điển đồng nghĩa, và sử dụng máy tìm kiếm [14]. Đối với tiếng Việt, do hạn chế về thời gian, kiến thức cũng như các cơng cụ liên quan mà chúng tơi tạm thời chưa đưa vào giải quyết vấn đề này trong mơ hình trên. • Cuối cùng là chưa giải quyết được vấn đề thuộc tính ẩn (khơng rõ ràng). 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: Hiện nay trên thế giới cĩ khá nhiều cơng trình nghiên cứu về lĩnh vực trích chọn thuộc tính sản phẩm trong các đánh giá của khách hàng với nhiều cách tiếp cận khác nhau. Phần này sẽ điểm qua một số mơ hình trích chọn cĩ cách tiếp cận khác với khĩa luận: • Đầu tiên là OPINE, một hệ thống trích chọn thơng tin khơng giám sát, được xây dựng trên nền tảng hệ thống KnowItAll [6] dùng để trích chọn thuộc tính sản phẩm và ý kiến đánh giá trong các đánh giá sản phẩm trực tuyến. Một đặc điểm nổi trội của OPINE là khả năng trích chọn cả thuộc tính rõ ràng và thuộc tính khơng rõ ràng. • Thứ hai là mơ hình của Heng Ren, Jingye Wang, và Tony Wu [10]. Trong mơ hình này, quá trình trích chọn sẽ đi từ mức độ câu rồi mới xuống đến mức độ từ. Bước đầu tiên là xác định các câu trong đánh giá cĩ khả năng chứa thuộc tính của sản phẩm. Bước 2, dùng luật kết hợp và PMI (Point- wise Mutual Information) để trích chọn ra các thuộc tính trong đĩ. Để xác định câu cĩ chứa thuộc tính hay khơng, nhĩm tác giả áp dụng một vài phương pháp học máy như Nạve Bayesian, Spy EM, phương pháp Rocchio, SVM dựa trên Rocchio, Biased-SVM. 30 • Ngồi ra cịn cĩ mơ hình trích chọn tự động thuộc tính sản phẩm từ các đánh giá sản phẩm trực tuyến sử dụng mơ hình entropy cực đại kết hợp với các đặc trưng cú pháp và từ vựng của nhĩm tác giả Gamgarn Somprasertsri và Pattarachai Lalitrojwong [9]. Phương pháp tiến hành như sau: trích chọn các thuộc tính từ một tập dữ liệu đã gán nhãn, sau đĩ tiến hành huấn luyện mơ hình entropy cực đại, và sử dụng mơ hình đã được huấn luyện để trích chọn ra các thuộc tính của sản phẩm. Cuối cùng áp dụng kĩ thuật xử lý ngơn ngữ tự nhiên để xác định các thuộc tính cịn lại. 3.4. Tổng kết chương: Chương này đã đi vào xem xét các nội dung chính của bài tốn trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến. Trình bày hai thách thức cơ bản và một số phương pháp giải quyết. Đồng thời đưa ra mơ hình trích chọn thuộc tính sản phẩm sử dụng kĩ thuật xử lý ngơn ngữ tự nhiên và khai phá luật kết hợp khá hiệu quả. Chương tiếp theo trình bày các thử nghiệm thực tế trên tập dữ liệu cụ thể được lấy từ các hệ thống mua bán trực tuyến tiếng Việt và đánh giá kết quả thu được. 31 Chương 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ 4.1. Mơi trường thử nghiệm: 4.1.1. Mơi trường phần cứng: Bảng 8. Cấu hình hệ thống thử nghiệm Thành phần Chỉ số CPU Intel Pentum IV 2.4GHz Memory (RAM) 1.00 GB HDD 80 GB System type 32 bit Operating System 4.1.2. Cơng cụ phần mềm: Hiện tại trong lĩnh vực xử lý ngơn ngữ tiếng Việt, số phần mềm nguồn mở hồn thiện cịn khá hạn chế. Để tiến hành thực nghiệm, chúng tơi sử dụng cơng cụ mã nguồn mở JvnSegmenter của nhĩm tác giả Nguyễn Cẩm Tú và Phan Xuân Hiếu. Nguồn: Đây là bộ cơng cụ viết trên Java sử dụng mơ hình CRFs để thực hiện tách từ cho ngơn ngữ tiếng Việt. Ngồi ra, chúng tơi cịn sử dụng bộ cơng cụ gán nhãn từ loại VnQTAG của nhĩm tác giả Nguyễn Thị Minh Huyền, Vũ Xuân Lương, Lê Hồng Phương. Nguồn: Cuối cùng là các thành phần khác trong hệ thống trích chọn thuộc tính sản phẩm do chúng tơi tự xây dựng (cài đặt Apriori, bộ trích chọn thuộc tính). 4.2. Dữ liệu thực nghiệm: Dữ liệu thực nghiệm là các đánh giá sản phẩm sản phẩm điện thoại của người dùng viết bằng ngơn ngữ tiếng Việt lấy trên các trang bán hàng trực tuyến như vatgia.com, 32 thegioididong.com… Các đánh giá cĩ cấu trúc gồm tiêu đề và nội dung ý kiến, ngồi ra cịn cĩ các thơng tin về số điểm (rating), thời gian và người đánh giá. Hình 3. Ví dụ về các đánh giá sản phẩm Nokia E90 trên website thegioididong.com Sau khi được lấy về, dữ liệu được tổ chức dưới dạng file text, mỗi file lưu tất cả đánh giá cho một sản phẩm cụ thể. Cĩ tổng cộng 23 loại điện thoại, với tổng cộng 700 đánh giá được thu thập làm dữ liệu thực nghiệm. Dưới đây, chúng tơi trình bày kết quả đạt được đối với 6 sản phẩm tiêu biểu. Nội dung cần lấy 33 Bảng 9. 6 sản phẩm tiêu biểu trong số các mẫu thực nghiệm STT Tên sản phẩm Số lượng đánh giá Số lượng thuộc tính 1 800 sapphire arte 12 36 2 Nokia 5800 XpressMussic 27 30 3 Nokia N73 Music Edition 60 52 4 Nokia N81 - 8GB 21 47 5 Nokia N95 53 42 6 Samsung F480 17 37 Dữ liệu sau khi lấy về sẽ được tiến hành tiền xử lý: + Thêm dấu câu đối với các đánh giá khơng gõ cĩ dấu. + Sửa các lỗi chính tả. + Loại bỏ các kí tự biểu cảm trong ngơn ngữ chat (emoticons). Nhận xét: Các đánh giá sản phẩm trên ngơn ngữ tiếng Việt trong các hệ thống mua bán trực tuyến nĩi chung cĩ nhiều hạn chế về số lượng cũng như chất lượng. + Về số lượng: rất khĩ để tìm một trang bán hàng trực tuyến nào cĩ số lượng đánh giá tiếng Việt về một sản phẩm lên quá con số một trăm. Vì vậy việc thu thập các đánh giá về cùng một sản phẩm phải tiến hành trên nhiều hệ thống mua bán trực tuyến khác nhau. + Cịn về chất lượng các đánh giá, tồn tại hạn chế chính ở cả mặt hình thức và nội dung. Về hình thức, vấn đề gặp phải ở đây là tồn tại một số lượng khá lớn người dùng cĩ thĩi quen viết tiếng Việt khơng dấu. Hiện nay lại chưa cĩ hệ thống xử lý ngơn ngữ tiếng Việt nào cĩ khả năng bổ sung dấu cho văn bản tiếng Việt khơng dấu. Vì vậy, chúng tơi bắt buộc phải tiến hành chuẩn hĩa bằng tay, thực hiện việc thêm dấu cho các đánh giá viết khơng dấu. Đây là một cơng đoạn tốn nhiều thời gian và cơng sức nhất trong khâu tiền xử lý. Về nội dung, các đánh giá phần lớn cịn khá sơ sài (cá biệt một lượng khơng nhỏ 34 đánh giá chỉ gồm cĩ 1, 2 câu nhận xét với nội dung chung chung). Trong quá trình thu thập dữ liệu, chúng tơi đã cố gắng chọn lọc ra các đánh giá cĩ chất lượng nội dung khá trở lên. 4.3. Kết quả thực nghiệm: Tiến hành thử nghiệm trên tập các dữ liệu tiếng Việt đã qua tiền xử lý như giới thiệu ở trên. Kết quả thu được như sau. 4.3.1. Tách từ và gán nhãn từ loại: • Tách từ: + Đọc dữ liệu từ file văn bản chứa các đánh giá tiếng Việt (mã hĩa UTF-8) thu thập được vào JvnSegmenter để tiến hành tách từ. + Kết quả trả lại cĩ dạng như sau: [Tuyệt vời] , [nhưng] [...] [Mới] [mua] [con] [này] [được] [2] [hơm] . [Dùng] [thấy] [rất] [ổn] , [cĩ] [điều] [pin] [mau] [hết] , [1] [ngày] [là] [hết sạch] . [Tình hình] [này] [phải] [kiếm] [quả] [Pin] [khác] [khủng] [hơn] [mới] [xong] . [Ngồi ra] [thì] [camera] [mặt] [trước] [xấu kinh] , [dùng] [video call] [thì] [tệ] [thật] . [Nhưng] [về cơ bản] [thì] [các] [tính năng] [khác] [rất] [tuyệt] , [đặc biệt] [xem] [phim] [mp4] [trên] [màn hình] [16] [triệu] [màu] , [hehe] , [các] [máy] [khác] [khĩc hận] [Ưu điểm] : [Nhiều] [Nhược điểm] : [Pin] [mau hết] [Đánh giá] : [10 /10] [Nhận xét] [lúc] : [00:44:00] [18/04/2007] [Email] : [my_memory_21_08@yahoo.com] + Lưu kết quả trên ra file cĩ cấu trúc mỗi dịng là một từ trong cặp ngoặc vuơng để làm dữ liệu đầu vào cho bộ gán nhãn VnQTAG. + Đánh giá kết quả tách từ: độ chính xác cao, thời gian thực hiện nhanh. • Gán nhãn từ loại: + Chạy cơng cụ VnQTAG với dữ liệu đầu vào là các file text thu được ở bước trên. 35 + Kết quả trả lại là các file chứa dữ liệu đã được gán nhãn. File này cĩ cấu trúc như sau: Tuyệt vời , nhưng ... . Mới mua con này được 2 hơm . … + Đánh giá kết quả gán nhãn: Do thời gian thực nghiệm cĩ hạn nên chúng tơi chưa thể tiến hành gán nhãn tập dữ liệu bằng tay để tiến hành đánh giá độ chính xác của kêt quả gán nhãn tự động bằng VnQTAG. Tuy nhiên, qua quan sát, chúng tơi nhận thấy kết quả gán nhãn từ loại cĩ độ chính xác chưa cao. 4.3.2. Trích chọn thuộc tính phổ biến: • Sinh các tập chỉ mục phổ biến: + Bước 1: sinh tập chỉ mục, trích chọn ra các từ được gán nhãn danh từ trong kết quả thu được trên. Theo kết quả gán nhãn từ loại, các danh từ được chia làm 8 nhĩm nhỏ. Bảng 10. Các loại danh từ Loại danh từ Kí hiệu nhãn Danh từ riêng Np Danh từ đơn thể Nc Danh từ tổng thể Ng Danh từ loại thể Nt Danh từ chỉ đơn vị Nu Danh từ trừu tượng Na 36 Danh từ số lượng Nn Danh từ vị trí Nl Bảng 11. Số lượng danh từ trong tập đánh giá mỗi sản phẩm STT Tên sản phẩm Số lượng danh từ 1 800 sapphire arte 222 2 Nokia 5800 XpressMussic 353 3 Nokia N73 Music Edition 798 4 Nokia N81 - 8GB 481 5 Nokia N95 809 6 Samsung F480 306 + Bước 2: tạo cơ sở dữ liệu giao tác. Đối với mỗi một sản phẩm, tạo một ma trận m×n, trong đĩ mỗi hàng ứng với một câu trong tập dữ liệu các đánh giá về sản phẩm đĩ, cịn mỗi cột ứng với một danh từ trong tập chỉ mục thu được ở bước trên. 0 0 0 0 0 0 0 0 0 0 0 0 0...0 0 0 0 0 0 1 0 0 0 0 0 0 1...1 0 1 1 0 0 0 0 0 0 0 0 0 0...0 ... 1 1 0 1 1 0 0 0 0 0 0 0 0...0 + Bước 3: chạy thuật tốn Apriori với dữ liệu đầu vào là tập chỉ mục và cơ sở dữ liệu sinh ở bước trên, đầu ra là các tập chỉ mục phổ biến thỏa mãn ngưỡng hỗ trợ cực tiểu minsupp. Mỗi tập chỉ mục phổ biến sẽ tương ứng với một thuộc tính. Ví dụ: giả sử L1 = {A, B, C, D …}, L2={[AB],[AC],…} thì A, B, C, D và AB, AC cĩ thể là thuộc tính của sản phẩm. Trong quá trình thực nghiệm, chúng tơi rút ra các nhận xét sau: + Nếu tạo tập chỉ mục I gồm tất cả các danh từ thu được sau khi gán nhãn từ loại, thì các tập chỉ mục phổ biến Lk sinh ra sẽ chứa rất nhiều các phần tử khơng phải là thuộc tính của sản phẩm. Dựa vào khảo sát các thuộc tính là 37 danh từ đơn và danh từ ghép trong các đánh giá, chúng tơi đưa ra chiến lược chọn lọc danh từ như sau: sử dụng I={Nc, Ng, Na, Np} để tìm L1, và sử dụng I={Nc, Ng, Na, Np, Nu, Nl} để tìm Lk với k > 1. + Hầu hết các thuột tính sản phẩm xuất hiện trong các đánh giá đều cĩ độ dài nhỏ hơn 3 từ (thuộc tính dài nhất được tạo ra bằng cách ghép 3 từ đơn lại với nhau). Vì vậy, chúng tơi chỉ lấy kết quả gồm các tập chỉ mục phổ biến 3 phần tử trở xuống (Lk với k ≤ 3), bỏ qua các Lk cịn lại. Điều này giúp tiết kiệm thời gian và cơng sức cho bước cắt tỉa mà khơng làm ảnh hưởng tới kết quả của bài tốn. + Ngồi ra, để loại bỏ bớt các kết quả khơng phù hợp, chúng tơi sử dụng 2 ngưỡng minsupp khác nhau cho L1 và Lk (1< k ≤ 3). Minsupp cho L1 là 2%, trong khi minsupp cho Lk là 1%. Minsupp cho L1 cao hơn để loại bỏ bớt các danh từ khơng quan trọng. Kết quả thu được như bảng bên dưới: 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 Thuộc tính phổ biến (khai phá luật kết hợp) Tên sản phẩm Số thuộc tính xác định bằng tay Recall Precision 800 sapphire arte 36 0.500 0.008 Nokia 5800 XpressMussic 30 0.500 0.063 Nokia N73 Music Edition 52 0.385 0.177 Nokia N81 - 8GB 47 0.596 0.002 Nokia N95 42 0.404 0.091 Samsung F480 37 0.649 0.006 Trung bình 40 0.506 0.058 • Cắt tỉa kết quả thu được: 38 + Bước 1 - compactness prunning: cắt tỉa nhằm đảm bảo tính chặt chẽ của kết quả. Thực hiện như đã đề cập trong mơ hình ở chương 3. + Bước 2 - redundancy prunning: cắt tỉa loại bỏ thuộc tính thừa. Ở đây chúng tơi đặt ngưỡng p-support = 2. + Kết quả đạt được thể hiện trong bảng dưới đây. 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 Compactness prunning Redundancy prunning Tên sản phẩm Số thuộc tính xác định bằng tay Recall Precision Recall Precision 800 sapphire arte 36 0.306 0.297 0.306 0.333 Nokia 5800 XpressMussic 30 0.500 0.263 0.433 0.255 Nokia N73 Music Edition 52 0.365 0.253 0.365 0.253 Nokia N81 - 8GB 47 0.489 0.2 0.468 0.212 Nokia N95 42 0.405 0.227 0.405 0.243 Samsung F480 37 0.568 0.247 0.568 0.273 Trung bình 40 0.438 0.248 0.424 0.262 4.3.3. Tìm tập các từ thể hiện ý kiến: Phương pháp thực hiện như sau: • Tìm các câu trong đĩ cĩ xuất hiện các thuộc tính sản phẩm. • Lấy ra các tính từ cĩ trong đĩ (dựa vào kết quả gán nhãn từ loại). • Chọn ra các tính từ ở gần thuộc tính nhất để đưa vào tập các từ thể hiện ý kiến. Chúng tơi chọn các tính từ ở gần thuộc tính nhất vì thơng thường đây là các tính từ bổ nghĩa cho danh từ (thuộc tính) mà ta tìm được ở trên. 4.3.4. Trích chọn thuộc tính ít phổ biến: Tiến hành tương tự như trên: • Tìm các câu trong đĩ cĩ xuất hiện các từ thể hiện ý kiến. 39 • Lấy ra các danh từ cĩ trong đĩ (dựa vào kết quả gán nhãn từ loại). • Chọn ra các danh từ ở gần các từ thể hiện ý kiến nhất để đưa vào tập các thuộc tính ít phổ biến. Kết quả trích chọn cuối cùng được thể hiện trong bảng dưới đây: 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. Xác định thuộc tính ít phổ biến Tên sản phẩm Số thuộc tính xác định bằng tay Recall Precision 800 sapphire arte 36 0.324 0.324 Nokia 5800 XpressMussic 30 0.433 0.25 Nokia N73 Music Edition 52 0.365 0.253 Nokia N81 - 8GB 47 0.468 0.212 Nokia N95 42 0.476 0.213 Samsung F480 37 0.568 0.266 Trung bình 40 0.439 0.253 Bảng 15. Độ đo F1 của kết quả sau các bước. Tên sản phẩm Số thuộc tính gán nhãn bằng tay Compactness prunning Redundancy prunning Xác định thuộc tính ít phổ biến 800 sapphire arte 36 0.301 0.319 0.324 Nokia 5800 XpressMussic 30 0.345 0.321 0.317 Nokia N73 Music Edition 52 0.299 0.299 0.299 Nokia N81 - 8GB 47 0.284 0.292 0.291 Nokia N95 42 0.291 0.304 0.294 40 Samsung F480 37 0.344 0.369 0.362 Trung bình 40 0.311 0.317 0.314712 Hình 4. Đồ thị độ đo F1 của kết quả sau các bước trích chọn. 4.4. Đánh giá kết quả thực nghiệm: Để tiến hành đánh giá kết quả thực nghiệm, chúng tơi tiến hành xác định các thuộc tính sản phẩm cĩ trong các đánh giá bằng con người. Số thuộc tính tìm được hầu hết là các thuộc tính rõ ràng (như đã ví dụ ở trên), các thuộc tính khơng rõ ràng chiếm một tỉ lệ rất nhỏ (1-5%). Cột các thuộc tính tìm được bằng tay trong bảng 12, 13 cho ta thấy số lượng thuộc tính tìm được bằng cách này đối với mỗi một sản phẩm. Bảng 12, 13 và 14 cho ta thấy độ chính xác và độ hồi tưởng của tập thuộc tính tìm được ở mỗi bước: • Sau khi áp dụng thuật tốn Apriori là: 5.8% và 50.6% • Sau khi thực hiện cắt tỉa Compactness prunning: 24.8% và 43.8% 41 • Sau khi thực hiện cắt tỉa Redundancy prunning: 26.2% và 42.4% • Sau khi trích chọn các thuộc tính ít phổ biến: 25.3% và 43.9% Trong bảng 12, kết quả sau bước sinh tập thuộc tính phổ biến bằng phương pháp khai phá luật kết hợp cĩ độ chính xác rất thấp. Chứng tỏ các tập chỉ mục phổ biến sinh ra cịn chứa quá nhiều phần tử khơng phải thuộc tính. Bảng 13 cho thấy kết quả sau khi thực hiện hai bước cắt tỉa. Độ chính xác đã được nâng lên đáng kể, độ hồi tưởng chỉ giảm đi vài phần trăm. Điều này chứng tỏ 2 phương pháp cắt tỉa đưa ra là hiệu quả. Trong bảng 14, hai cột cuối cho ta thấy kết quả sau khi trích chọn các thuộc tính ít phổ biến. Ta thấy cĩ sự giảm nhẹ về độ chính xác trung bình, tuy nhiên do các thuộc tính ít phổ biến thường được xếp hạng khá thấp nên các kết quả này hầu như khơng ảnh hưởng tới người dùng. Kết quả trích chọn thuộc tính sản phẩm trên tiếng Việt cịn thấp là do các nguyên nhân chính sau: • Việc gán nhãn từ loại cịn nhiều sai sĩt. • Chưa cĩ một cơng cụ hồn thiện để xác định được các cụm danh từ trong văn bản tiếng Việt. Trong khĩa luận này, chúng tơi chỉ mới tìm ra các cụm danh từ cĩ cấu tạo từ các danh từ đơn bằng cách áp dụng luật kết hợp. Vì vậy, kết quả cịn bỏ sĩt các thuộc tính là cụm danh từ cĩ cấu tạo khác như danh từ + động từ (“nắp trượt”, “chế độ rung”…). • Đây là cơng trình đầu tiên trong lĩnh vực trích chọn thuộc tính sản phẩm trong các đánh giá xử lý trên ngơn ngữ tiếng Việt, thêm vào đĩ là hạn chế về thời gian và kiến thức nên tập dữ liệu để tiến hành thử nghiệm cũng như cơ sở để đánh giá kết quả chưa được hồn thiện. Từ những kết quả và đánh giá trên, chúng ta cĩ thể kết luận rằng mơ hình trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến ứng dụng khai phá luật kết hợp là một mơ hình cĩ nhiều tiềm năng. Để thu được kết quả tốt hơn thì cần phải đầu tư nhiều cơng sức và cĩ quy mơ hơn, từ việc thu thập dữ liệu cho tới hồn thiện các thành phần xử lý ngơn ngữ tiếng Việt của hệ thống. 42 4.5. Tổng kết chương: Trong chương này chúng ta đã xem xét kết quả của quá trình thử nghiệm mơ hình trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến áp dụng khai phá luật kết hợp. Qua phân tích và đánh giá đã cho thấy tính đúng đắn của phương pháp sử dụng trong khĩa luận, nếu được đầu tư, hồn thiện trong tương lai thì đây là một mơ hình cĩ nhiều triển vọng áp dụng vào thực tế. 43 KẾT LUẬN Khĩa luận đã trình bày bài tố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”. Các vấn đề của bài tốn đã được trình bày, phân tích và đưa ra các hướng giải quyết cụ thể. Khĩa luận đã sử dụng tiếp cận khai phá luật kết hợp là một phương pháp học máy linh hoạt, hiệu quả, thích hợp với bài tốn trích chọn thuộc tính sản phẩm. Những kết quả chính mà khĩa luận đạt được: • Phân tích các vấn đề xung quanh bài tốn trích chọn thuộc tính thuộc tính sản phẩm trong hệ thống mua bán trực tuyến. • Xây dựng mơ hình trích chọn thuộc tính sản phẩm trong tiếng Việt Do khuơn khổ cĩ hạn về thời gian cũng như lượng kiến thức cĩ được và gặp khĩ khăn trong quá trình thu thập dữ liệu thử nghiệm nên cịn một số vấn đề mà khĩa luận phải tiếp tục hồn thiện và phát triển trong thời gian tới: • Thử nghiệm trên một dữ liệu lớn hồn chỉnh hơn. • Xây dựng các phương pháp hiệu quả hơn trong việc trích chọn cụm danh từ tiếng Việt. 44 TÀI LIỆU THAM KHẢO Tiếng Việt: [1] Đỗ Phúc. Giáo trình Khai thác Dữ liệu. Trường Đại học Cơng nghệ thơng tin TP. Hồ Chí Minh, Đại học Quốc gia TP. Hồ Chí Minh. 2006. [2] Hồ Tú Bảo, Lương Chi Mai. Về xử lý tiếng Việt trong Cơng nghệ thơng tin. Viện Cơng nghệ Thơng tin, Viện Khoa học và Cơng nghệ Việt Nam, 2006. [3] Nguyễn Thị Minh Huyền, Vũ Xuân Lương, Lê Hồng Phương. Sử dụng bộ gán nhãn từ loại xác suất QTAG cho văn bản tiếng Việt. Kỷ yếu hội thảo ICT.rda'03. Hà Nội. 22-23 tháng 2, 2003 Tiếng Anh: [4] Agrawal, R. and Srikant, R. Fast algorithms for mining association rules. In Proc. 20th Int. Conf. Very Large Data Bases, 487-499. 1994. [5] Agrawal, R., Imielinski, T., and Swami, A. N. Mining association rules between sets of items in large databases. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, 207-216. [6] Ana-Maria Popescu and Oren Etzioni. Extracting Product Features and Opinions from Reviews. In HLT '05: Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing (2005), 339-346. [7] Cam Tu Nguyen and Xuan Hieu Phan. JVnSegmenter: A Java-based Vietnamese Word Segmentation Tool. 2007. [8] Fellbaum, C. (Edit). WordNet, An Electronic Lexical Database. The MIT Press. 2001. [9] Gamgarn Somprasertsri, Pattarachai Lalitrojwong. Automatic product feature extraction from online product reviews using maximum entropy with lexical and syntactic features. Information Reuse and Integration, 2008. IEEE International Conference on Volume , Issue , 13-15 July 2008, 250 - 255 [10] Heng Ren, Jingye Wang, and Tony Wu. Customer review feature extraction. 45 [11] Knowledge Discovery in Databases, Apriori Itemset Generation. In computer science 831. University of Regina. [12] M. Hu and B. Liu. 2004. Mining and Summarizing Customer Reviews. In KDD, pages 168–177, Seattle, WA. 2004 [13] M. Hu and B. Liu. Mining Opinion Features in Customer Reviews. In AAAI’04, 2004. [14] M. Hu and B. Liu. Opinion Extraction and Summarization on the Web. In AAAI’06, 2006 [15] R. C. Merkle. A digital signature based on a conventional encryption function. Crypto '87 [16] S. Blair-Goldensohn, K. Hannan, R. McDonald, T. Neylon, G. A. Reis and J. Reynar. Building a sentiment summarizer for local service reviews. In WWW Workshop on NLP in the Information Explosion Era, 2008. [17] Santosh Raju, Prasad Pingali, and Vasudeva Varma. An Unsupervised Approach to Product Attribute Extraction. Tech report, International Institute of Information Technology, India, 2009