i
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Quách Hiếu Nghĩa TRÍCH CHỌN THUỘC TÍNH SẢN PHẨM TRONG
HỆ THỐNG MUA BÁN TRỰC TUYẾN TIẾP CẬN
KHAI PHÁ LUẬT KẾT HỢP
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin 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
để
đánh giá, nhưng đã chứng minh được tính đúng đắn và hiệu quả của các kĩ thuật sử
dụng. Đây là cơ sở cho các hệ thống tương tự trong tương lai có thể sử dụng lại hoặc cải
tiến hoàn thiện hơn.
ii MỤC LỤC
LỜI CẢM ƠN........................................................................................................................i
TÓM TẮT NỘI DUNG.........................................................................................................i
MỤC LỤC ............................................................................................................................ii
DANH MỤC BẢNG SỐ LIỆU...........................................................................................iv
DANH MỤC HÌNH ẢNH....................................................................................................v
MỞ ĐẦU ..............................................................................................................................1
Chương 1: GIỚI THIỆU.......................................................................................................2
1.1. Đặt vấn đề: ..............................................................................................................2
1.2. Phát biểu bài toán trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực
tuyến tiếp cận khai phá luật kết hợp: ................................................................................4
1.3. Ý nghĩa và ứng dụng:..............................................................................................6
Chương 2: CƠ SỞ LÝ THUYẾT.........................................................................................8
2.1. Khai phá luật k
ết hợp:.............................................................................................8
2.1.1. Định nghĩa:.......................................................................................................8
2.1.2. Các bước trong khai phá luật kết hợp: .............................................................8
2.2. Các khái niệm cơ sở:...............................................................................................9
2.3. Thuật toán Apriori: ...............................................................................................12
2.4. Tổng kết chương: ..................................................................................................18
Chương 3: TRÍCH CHỌN THUỘC TÍNH SẢN PHẨM TRONG HỆ THỐNG MUA
BÁN TRỰC TUYẾN TIẾP CẬN KHAI PHÁ LUẬT KẾT HỢP.....................................19
3.1. Giới thiệu: .............................................................................................................19
KẾT LUẬN ........................................................................................................................43
TÀI LIỆU THAM KHẢO..................................................................................................44
iv
DANH MỤC BẢNG SỐ LIỆU
Bảng 1. Bảng ví dụ về cơ sở dữ liệu chứa các giao dịch bán hàng của một siêu thị..........11
Bảng 2. Bảng kí hiệu cho thuật toán Apriori......................................................................13
Bảng 3. Bảng cơ sở dữ liệu giao tác minh họa cho thuật toán Apriori ..............................15
Bảng 4. Bảng kết quả C
1
, L
1
...............................................................................................16
Bảng 5. Bảng kết quả C
2
, L
2
...............................................................................................16
Bảng 6. Bảng kết quả C
3
, L
3
...............................................................................................17
Bảng 7. Bảng kết quả C
4
, L
4
...............................................................................................17
Bảng 8. Cấu hình hệ thống thử nghiệm..............................................................................31
ương pháp học máy để giải quyết bài toán trích chọn thuộc tính sản
phẩm. Trong khóa luận này, chúng tôi sử dụng kĩ thuật khai phá luật kết hợp để trích chọn
ra các thuộc tính của sản phẩm. Đây là một hướng tiếp cận hiệu quả đã được chứng minh
khi thực hiện trên ngôn ngữ tiếng Anh. Chúng tôi sẽ trình bày các giải pháp thích hợp khi
áp dụng vào tiếng Việt.
Khóa luận gồm bốn chương, nội dung
được mô tả sơ bộ như dưới đây:
• Chương 1: Đặt vấn đề và giới thiệu tổng quan bài toán tóm tắt đánh giá sản
phẩm, từ đó phát biểu bài toán trích chọn thuộc tính sản phẩm trong hệ thống
mua bán trực tuyến.
• Chương 2: Trình bày về lý thuyết khai phá luật kết hợp theo hướng áp dụng
vào giải quyết bài toán trích chọn thuộc tính sản phẩm trong hệ thống mua
bán trực tuyến.
• Chương 3: Phát biểu bài toán trích chọn thuộc tính sản phẩm trong hệ thống
mua bán trực tuyến tiếp cận khai phá luật kết hợp, phân tích các vấn đề cần
giải quyết đối với bài toán và các bước xây dựng mô hình trích chọn trên cơ
sở áp dụng khai phá luật kết hợp.
• Chương 4: Trình bày những kết quả thực nghiệm của khóa luận.
Cuối cùng là phần kết lu
ận, tóm tắt lại những nội dung chính của khóa luận, đồng
thời chỉ ra những điểm cần khắc phục và hướng cải tiến nhằm mục tiêu xây dựng một hệ
thống ứng dụng thực trên môi trường Internet.
2
Chương 1: GIỚI THIỆU
1.1. Đặt vấn đề:
Trên thế giới nói chung và ở Việt Nam nói riêng, thương mại điện tử đã trở nên phổ
biến và ngày càng phát triển. Một phần quan trọng trong thương mại điện tử là bán hàng
trực tuyến. Ta có thể thấy số lượng website mua bán trực tuyến vô cùng lớn, nổi tiếng trên
toàn thế giới có Amazon.com, Cnet.com, eBay…, còn ở Việt Nam có thể kể ra một số
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
Do vậy, đầu vào (input) của bài toán là các nhận xét, đánh giá của người dùng về
một sản phẩm cụ thể trên một hệ thống bán hàng trực tuyến. Ví dụ: sản phẩm điện thoại
Nokia 8800 Arte trên website thegioididong.com.
Đầu ra (output) là một danh sách các đối tượng có thể là thuộc tính, đặc trưng của
sản phẩm được người dùng nhận xét, đề cập đến trong bài đánh giá. Ví dụ: {màn hình,
phím bấm, màu sắc, loa, giá cả
, kích thước, pin, hình dáng, camera, chất lượng ảnh, hệ
điều hành, ứng dụng, kết nối wifi…}
Trong những năm gần đây, trên thế giới đã có khá nhiều công trình nghiên cứu về đề
tài này. Hầu hết các mô hình trích chọn thuộc tính sản phẩm đều đi theo hướng trích chọn
ra các danh từ và cụm danh từ trong dữ liệu và xây dựng các mô hình thuật toán để lọc ra
được các cụm từ có khả năng là thuộc tính của sả
n phẩm. Có nhiều hướng tiếp cận khác
nhau để trích chọn ra được các cụm từ có khả năng là thuộc tính sản phẩm như áp dụng
học không giám sát [17], CRFs, … Tuy vậy, vẫn còn các vấn đề sau phải giải quyết:
• Trích chọn các thuộc tính từ các từ loại khác danh từ (tính từ và động từ cũng
có thể dùng để chỉ thuộc tính của sản phẩm). Một ví dụ đơn giản như khi nói
một sản phẩm “nhẹ” thì ta thường hiểu đó là nói về thuộc tính “trọng lượng”.
Do việc xác định những thuộc tính dạng này đòi hỏi phải phân tích được ngữ
nghĩa của cả câu, nên đây là một vấn đề khó khăn, đòi hỏi phải có những
nghiên cứu sâu về lĩnh vực xử lý ngôn ngữ tự nhiên.
• Một vấn đề nữa là xử lý các từ đồng ngh
ĩa cùng chỉ một thuộc tính. Đây
không phải là những trường hợp hiếm gặp. Để giải quyết vấn đề này, hiện
nay có 4 hướng tiếp cận chính: đó là sử dụng từ điển đơn ngữ, từ điển đồng
nghĩa (thesaurus), WordNet và máy tìm kiếm (search engine). Tuy nhiên, kết
quả đạt được đều còn khá hạn chế.
Còn ở Việt Nam, cho tới thời đi
ểm này, chưa có một công trình nghiên cứu nào về
(4) Xác định thuộc tính của sản ph
ẩm: áp dụng khai phá luật kết hợp trên tập cơ
sở dữ liệu đánh giá và tập thực thể thu được ở bước trên. Kết quả thu được sẽ
được tiến hành “cắt tỉa” để thu được kết quả cuối cùng là tập các thuộc tính
của sản phẩm xuất hiện trong đánh giá của người dùng.
1.3. Ý nghĩa và ứng dụng:
Trích chọn thuộc tính sản phẩm trong hệ thống mua bán trực tuyến tiếp cận khai phá
luật kết hợp là một đề tài có ý nghĩa và mang tính ứng dụng cao. Kết quả của bài toán sẽ
được sử dụng để tạo ra bản tóm tắt các ý kiến đánh giá của người dùng về một sản phẩm
trên hệ thống mua bán trực tuyến dựa theo các thuộc tính của sản phẩm đó. Đối với nh
ững
sản phẩm có số lượng đánh giá trên mạng khá lớn thì bản tóm tắt trên cung cấp cho người
7
dùng một cái nhìn toàn diện và chi tiết về sản phẩm đó, giúp họ tiết kiệm được thời gian
trong việc tham khảo thông tin để đưa ra quyết định mua hàng. Còn nhà sản xuất thông
qua các tóm tắt này cũng dễ dàng thu thập được các phản hồi của khách hàng trên mạng
đối với sản phẩm của mình, để từ đó cải tiến, hoàn thiện sản phẩm cho phù hợp với nhu
cầu của khách hàng. Chúng tôi tin rằng cùng với việ
c ngày càng nhiều người thực hiện
mua sắm và bày tỏ ý kiến của bản thân qua mạng thì ý nghĩa và lợi ích do kết quả trên
mang lại sẽ càng lớn.
8
Chương 2: CƠ SỞ LÝ THUYẾT
Như đã đề cập trong chương một, yêu cầu của bài toán là xác định tất cả thuộc tính
của sản phẩm được người dùng đánh giá, và để giải quyết vấn đề này chúng tôi sử dụng lý
thuyết khai phá luật kết hợp để tìm ra tập các thuộc tính phổ biến. Điều này xuất phát từ
quan sát thực tế sau. Các đánh giá sản phẩm thường có nội dung khác nhau và có thể gồm
khá nhiều th
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à L
k
, L
k
= {I
1
, I
2
, I
3
, …, I
k
}, 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 {I
1
, I
2
, I
3
, …, I
k-1
} → {I
k
}, 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
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).
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 = {T
1
, T
2
, T
3
, T
4
, T
5
}, 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à T
2
, T
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.
3) C
k
= apriori-gen(L
k-1
); // Sinh tập ứng viên mới
4) forall transactions t ∈ D do begin
5) C
t
= subset(C
k
, t); // Tập ứng viên thuộc t
6) forall candidates c ∈ Ct do
7) c.count++;
8) end
9) L
k
= {c ∈ C
k
| c.count ≥ minsupp}
10) end
11) Answer = ;
Hàm apriori-gen: nhận tham số đầu vào là L
k-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ử L
k
. Hàm này thực hiện như sau :
• Bước 1 kết hợp: để tìm L
k
, tập C
[1] l
1
[2] ... l
1
[k-2] l
1
[k-1] l
2
[k-1].
1) insert into C
k
2) select p.item
1
, p.item
2
,..., p.item
k-1
, q.item
k-1
3) from L
k-1
p, L
k-1
q
4) where p.item1 = q.item
1
, . . ., p.item
k-2
delete c from C
k
;
Hàm subset: nhận tham số đầu vào là C
k
và một giao tác t ∈ D, trả lại tất cả phần tử
của C
k
có mặt trong t. Việc này được thực hiện bằng cách:
• Lưu C
k
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
∈
C
k
(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
Duyệt dữ liệu lần 2:
Bảng 5. Bảng kết quả C
2
, L
2
C
2
L
2
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
C
4
L
4itemset X supp(X) itemset X supp(X)
Nối ABC với
AB
D
A, B, C, D 40%
A, B, C 40%
Nối ACD với
AC
E
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:
Copyright: Tài liệu đại học ©