Đề tài 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

% 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 toán Apriori: Hiện nay, Apriori [4] là thuật toá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 toà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 toán Apriori: ý tưởng, cài đặt và một số hạn chế còn tồn tại của thuật toán. Ý tưởng chính của thuật toá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 toá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 toá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 toán Apriori : Bảng 2. Bảng kí hiệu cho thuật toá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 toá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 toá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 toá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 toán Apriori dừng ở đây. Kết luận: 18 Apriori là một thuật toá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. Ngoài ra, đây còn là một thuật toán dễ cài đặt. Tuy nhiên, vẫn còn 2 hạn chế trong thuật toá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 toá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 toán Apriori. Hiện nay, có khá nhiều thuật toá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 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 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 toán Apriori dựa trên hai tiền đề quan trọng. Áp dụng thuật toán Apriori vào bài toá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 toán tóm tắt đánh giá sản phẩm nói chung và bài toá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 toán chính của khoá 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 toá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 toá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 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, về các nhu cầu thực tế, ứng dụng cũng như ý nghĩa của bài toán. Chương này sẽ trình bày việc giải quyết bài toá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 toá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 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ư đã 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 toán tóm tắt đánh giá sản phẩm ra đời, trong đó bài toá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 toá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 toá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 toá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 toá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). Ngoà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 toá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 toá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 toá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 toá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 toán Apriori ở bước sau. Bước hai, áp dụng thuật toá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 toá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 toá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 toá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 toán Apriori, f={w1, w2, …,wn}. Nếu tồn tại một câu s chứa toà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 ngoà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ợ hoàn toà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 hoà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ư Naïve Bayesian, Spy EM, phương pháp Rocchio, SVM dựa trên Rocchio, Biased-SVM. 30 • Ngoà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 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. 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ở hoà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. Ngoà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, ngoà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] . [Ngoà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 toá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 toán. + Ngoà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 toá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ụ hoà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 hoà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 hoà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ư, hoà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 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”. Các vấn đề của bài toá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 toá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 toá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 hoà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 hoà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