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

hiê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 toá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 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í