ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM

NGUYỄN HOÀNG NHẬT

KHAI PHÁ TẬP PHỔ BIẾN TRÊN
CƠ SỞ DỮ LIỆU TĂNG TRƯỞNG
TRONG LĨNH VỰC MUA BÁN HÀNG

Chuyên ngành: HỆ THỐNG THÔNG TIN
Mã số: 61.49.01.04

TÓM TẮT
LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN

Đà Nẵng – Năm 2017


Công trình được hoàn thành tại
TRƯỜNG ĐẠI HỌC SƯ PHẠM - ĐHĐN

Người hướng dẫn khoa học: TS. NGUYỄN TRẦN QUỐC VINH

Phản biện 1: TS. Hoàng Thị Thanh Hà
Phản biện 2: TS. Trần ThiênThành

Luận văn được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp thạc sĩ
Hệ thống thông tin họp tại Trường Đại học Sư phạm – ĐHĐN vào ngày
30 tháng 7 năm 2017.

Có thể tìm hiểu luận văn tại:

- Thư viện Trường Đại học Sư phạm Đà Nẵng, Đại học Đà Nẵng.
- Trung tâm thông tin học liệu, Đại học Đà Nẵng.


1
MỞ ĐẦU
1. Lý do chọn đề tài
Khai thác dữ liệu là một khái niệm ra đời vào những năm cuối
của thập kỷ 80, nó là quá trình tìm kiếm, khám phá dưới nhiều góc độ
khác nhau nhằm phát hiện các mối liên hệ, quan hệ giữa các dữ liệu,
đối tượng bên trong CSDL, kết quả của việc khai thác là xác định các
mẫu hay các mô hình tồn tại bên trong nhưng chúng nằm ẩn ở các
CSDL.
Về bản chất nó là giai đoạn duy nhất rút trích và tìm ra được các
mẫu, các mô hình hay thông tin mới, tri thức tiềm ẩn có trong CSDL
chủ yếu phục vụ cho mô tả và dự đoán. Đây là giai đoạn quan trọng
nhất trong quá trình phát hiện tri thức từ CSDL, các tri thức này hỗ trợ
trong việc ra quyết định, điều hành trong khoa học và kinh doanh.
Trong những năm gần đây thì rất nhiều các kỹ thuật trong khai
thác dữ liệu đã được phát triển. Các hướng tiếp cận trong khai thác dữ
liệu có thể phân loại dựa vào cơ sở dữ liệu làm việc như: CSDL giao
dịch, CSDL tạm thời, CSDL quan hệ, CSDL đa phương tiện v..v. Có
nhiều phương pháp trong khai thác dữ liệu đã được đề xuất như: luật
kết hợp (Apriori), phân lớp, gom nhóm (K-mean, K-medoids,..), khai
thác mẫu tuần tự…
Khai phá dữ liệu đã thu hút được sự quan tâm của rất nhiều nhà
nghiên cứu, nhờ có nhiều những ứng dụng trong thực tiễn trong nhiều
lĩnh vực như y tế, kinh doanh, ngân hàng,....
Trong đó, nhu cầu thêm những giao dịch mới vào CSDL hoặc
xóa một số giao dịch trong CSDL hiện tại trong các ứng dụng của thế

giới thực là rất cần thiết. Do đó việc xây dựng và chọn lựa nên một
thuật toán có hiệu suất xử lý tốt nhất để có thể xử trong trường hợp


2
CSDL tăng trưởng là một yêu cầu cấp thiết và hướng nghiên cứu phát
triển các thuật toán khai thác tập phổ biến trên dữ liệu tăng trưởng là
một trong những hướng nghiên cứu được đầu tư và phát triển mạnh.
Đã có rất nhiều thuật toán ra đời, tuy nhiên mỗi thuật toán có ưu,
khuyết điểm khác nhau, việc nghiên cứu chọn ra 1 thuật toán phù hợp
có hiệu suất xử lý cao để xử lý CSDL trong trường hợp phát sinh giao
dịch là cần thiết.
Đó chính là lý do tôi chọn đề tài : “Nghiên cứu một số phương
pháp khai phá tập phổ biến trên cơ sở dữ liệu tăng trưởng trong lĩnh
vực mua bán hàng” để làm đề tài luận văn thạc sĩ của mình.
2. Mục tiêu nghiên cứu
- Tìm hiểu các phương pháp khai phá cơ sở dữ liệu cơ bản.
- Tìm hiểu kỹ thuật khai phá dữ liệu dựa trên khai thác luật kết
hợp trong CSDL giao dịch:
o Nghiên cứu, phân tích, đánh giá 1 số phương pháp khai phá
tập phổ biến trên cơ sở dữ liệu tĩnh: Apriori, cây FP- Tree.
o Nghiên cứu, phân tích, đánh giá 1 phương pháp khai phá tập
phổ biến trên cơ sở dữ liệu tăng trưởng: Thuật toán FUP, Pre – large–
Itemset, Pre- FUFP.
- So sánh hiệu năng của thuật toán Pre- FUT và thuật toán Pre –
large – Itemset.
3. Đối tượng và phạm vi nghiên cứu
3.1. Đối tượng nghiên cứu
- Thuật toán Apriori
- Thuật toán FP- Tree

- Thuật toán FUP
- Thuật toán Pre – large – Itemset
- Thuật toán Pre-FUFP


3
- Thuật toán Pre-FUT
- Các CSDL khi phát sinh thêm các giao dịch, cụ thể ở đây là
các giao dịch khi thực hiện thanh toán mua hàng.
Phạm vi nghiên cứu
- Tập phổ biến khi phát sinh giao dịch mới.
- Kỹ thuật khai phá tập phổ biến dựa trên khai thác luật kết hợp
khi CSDL phát sinh giao dịch mới.
4. Phương pháp nghiên cứu
4.1. Nghiên cứu lý thuyết
- Nghiên cứu tài liệu, ngôn ngữ và các công nghệ có liên quan.
- Kỹ thuật khai phá dữ liệu dựa trên khai thác luật kết hợp
trong CSDL giao dịch.
- Kỹ thuật khai phá tập phổ biến trên cơ sở dữ liệu tĩnh.
- Kỹ thuật khai phá tập phổ biến trên cơ sở dữ liệu tăng
trưởng.
4.2. Nghiên cứu thực nghiệm
- Tiến hành thu thập và tổng hợp các tài liệu có liên quan đến
kỹ thuật khai phá dữ liệu sử dụng luật kết hợp, các thuật toán khai
phá dữ liệu trên CSDL tĩnh và CSDL động.
- So sánh hiệu xuất xử lý các CSDL động của thuật toán PreFUT và Pre- large- Itemset trên CSDL giao dịch mua hàng tại siêu
thị.
5. Dự kiến kết quả
5.1. Kết quả về lý thuyết
- Hiểu thêm được các phương pháp khai phá dữ liệu.

o Kỹ thuật khai phá tập phổ biến dựa trên khai thác luật kết
hợp trong CSDL giao dịch.
o Các phương pháp khai phá tập phổ biến trên cơ sở dữ liệu


4
tĩnh: Apriori, cây FP- Tree.
o Các phương pháp khai phá tập phổ biến trên cơ sở dữ liệu
tăng trưởng: Thuật toán FUP, Pre- FUFP.
- Cải tiến hiệu suất thuật toán FUP nhanh hơn bằng thuật toán
Pre-FUT.
5.2. Kết quả về thực tiễn
Chọn ra được 1 thuật toán phù hợp để cải tiến hiệu suất của kỹ
thuật khai phá tập phổ biến dựa trên luật kết hợp trong trường hợp
CSDL tăng trưởng ,phát sinh thêm các giao dịch mới, giúp quản lý và
các luật đã khai phá được hiệu quả hơn, từ đó có thể tiến hành tiếp quá
trình sinh ra các luật kết hợp hiệu quả hơn.
Có thể áp dụng thuật toán để xử lý CSDL tăng trưởng của nhiều
lĩnh vực khác nhau.
6. Ý nghĩa khoa học và thực tiễn
Áp dụng lý thuyết về khai thác luật kết hợp trong CSDL giao
dịch để nghiên cứu các thuật toán khai phá tập phổ biến trên CSDL
tăng trưởng
Về mặt thực tiễn, việc nghiên cứu giúp chọn ra 1 thuật toán phù
hợp giúp cải thiện thời gian xử lý các CSDL giao dịch tăng trưởng,
giúp quản lý, cập nhật các luật trong kỹ thuật khai thác dữ liệu dựa trên
khai thác luật kết hợp trên CSDL tốt hơn.
7. Bố cục luận văn
Chương 1: Tổng quan về khai thác tập phổ biến trên cơ sở dữ
liệu tăng trưởng

Trong chương này, chúng tôi trình bày cơ sở lý thuyết làm nền
tảng để nghiên cứu, bao gồm: Tổng quan về khai phá dữ liệu, các kỹ
thuật khai phá dữ liệu. Tìm hiểu một số phương pháp, thuật toán khai
phá dữ liệu trên cơ sở dữ liệu tĩnh : Apriori, FP Tree, Apriori-Tid,


5
Apriori Hybrid.
Chương 2: Một số phương pháp khai thác tập phổ biến trên cơ
sở dữ liệu tăng trưởng
Trong chương này, chúng tôi trình bày kiến thức lý thuyết, thuật
toán, ví dụ minh họa về các thuật toán khai phá tập phổ biến trên cơ sở
dữ liệu tăng trường như: FUP, Pre – large – Itemset, Pre- FUFP, Pre –
FUT.
Chương 3: Thực nghiệm
Trong chương này, chúng tôi sẽ xây dựng ứng thuật toán khai
phá tập phổ biến trên CSDL tăng trưởng được đánh giá cao hiện nay
là Pre-FUT và thuật toán Pre – Large – Itemset sử dụng ngôn ngữ C.
Tiến hành so sánh hiệu suất, thời gian xử lý giữa 2 thuật toán để tìm ra
1 thuật toán hiệu quả nhất. CSDL được sử dụng là các giao dịch thanh
toán mua hàng của 1 công ty mua bán sản phẩm trực tuyến từ năm
2010 đến 2011.
Cuối cùng là những đánh giá, kết luận và hướng phát triển của
đề tài.


6
CHƯƠNG 1
TỔNG QUAN VỀ KHAI THÁC TẬP PHỔ BIẾN
1.1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU

1.1.1. Mở đầu
Khai thác dữ liệu là một khái niệm ra đời vào những năm cuối
của thập kỷ 80, nó là quá trình tìm kiếm, khám phá dưới nhiều góc độ
khác nhau nhằm phát hiện các mối liên hệ, quan hệ giữa các dữ liệu,
đối tượng bên trong CSDL, kết quả của việc khai thác là xác định các
mẫu hay các mô hình tồn tại bên trong nhưng chúng nằm ẩn ở các
CSDL.
Trong những năm gần đây thì rất nhiều các kỹ thuật trong khai
thác dữ liệu đã được phát triển. Các hướng tiếp cận trong khai thác dữ
liệu có thể phân loại dựa vào cơ sở dữ liệu làm việc như: CSDL giao
dịch, CSDL tạm thời, CSDL quan hệ, CSDL đa phương tiện v..v. Có
nhiều phương pháp trong khai thác dữ liệu đã được đề xuất như: luật
kết hợp (Apriori), phân lớp, gom nhóm (K-mean, K-medoids,..), khai
thác mẫu tuần tự…
Khai phá dữ liệu được áp dụng trong nhiều lĩnh vực:

Hình 1.1. Một số lĩnh vực liên quan đến khai phá dữ liệu


7
1.1.2. Kiến trúc của một hệ thống khai phá dữ liệu

Hình 1. 1. Khám phá tri thức trong cơ sở dữ liệu điển hình
1.1.3. Các giai đoạn của quá trình khai phá dữ liệu

Hình 1. 2. Các bước của quy trình khai phá dữ liệu
Quá trình xử lý khai phá dữ liệu bắt đầu bằng việc xác định
chính xác vấn đề cần giải quyết. Sau đó sẽ xác định dữ liệu liên quan
dùng để xây dựng giải pháp. Tiếp theo là thu thập dữ liệu có liên quan
và xử lý chúng thành dạng sao cho thuật toán khai phá dữ liệu có thể

hiểu được
1.1.4.

Một số kỹ thuật khai phá dữ liệu

a. Phân lớp dữ liệu
b. Phân nhóm dữ liệu
c. Hồi qui (Regression)


8
d. Tổng hợp (summarization)
e. Mô hình hóa phụ thuộc (dependency modeling)
f. Phát hiện sự thay đổi và độ lệch (change and deviation
dectection):
1.1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu
Dựa vào những kiểu dữ liệu mà kỹ thuật khai phá áp dụng, có
thể chia dữ liệu thành các loại khác nhau:
- Cơ sở dữ liệu quan hệ
- Cơ sở dữ liệu giao tác
- Cơ sở dữ liệu không gian
- Cơ sở dữ liệu có yếu tố thời gian
- Cơ sở dữ liệu đa phương tiện.
1.1.6. Các phương pháp chính trong khai phá dữ liệu
g. Phân lớp và dự đoán (Classification & Prediction)
h. Phân cụm và phân đoạn (Clusterring and Segmentation)
i. Khai phá chuỗi theo thời gian (Sequential temporal
patterns)
j. Mô tả khái niệm và tổng hợp hóa (Summarization)
k. Luật kết hợp (Association rules)

1.2. MỘT SỐ PHƯƠNG PHÁP KHAI THÁC TẬP PHỔ BIẾN
TRÊN CSDL TĨNH
1.2.1. Mở đầu
Hiện nay thì có rất nhiều phương pháp khai thác tập phổ biến
trên CSDL tăng trưởng. Trong số đó thì khai thác luật kết hợp trong
CSDL giao dịch là một trong những kỹ thuật phổ biến nhất trong khai
thác dữ liệu, có thể chia làm 2 hướng chính:
Phương pháp khai thác tập phổ biến mà cần phải phát sinh tập
ứng viên.


9
Phương pháp khai thác tập phổ biến không cần phát sinh tập ứng
viên.
Phương pháp khai thác tập phổ biến mà yêu cầu phát sinh tập
ứng viên còn được gọi là phương pháp tựa Apriori. Thuật toán đầu tiên
được Cheung et al. [6] đề xuất là FUP (Fast-UPdated algorithm). Tuy
nhiên thuật toán vẫn xử lý lại toàn bộ CSDL gốc khi thêm mới giao
dịch vào CSDL. Một số thuật toán khác cũng đã được đề xuất [21].
Phương pháp khai thác tập phổ biến mà không yêu cầu phát sinh
tập ứng viên còn được gọi là phương pháp tựa FP-tree (FrequentPattern tree). Thực tế phương pháp FP-tree vẫn phát sinh ứng viên,
nhưng ứng với mỗi ứng viên phát sinh ra thì sẽ tính nhanh được độ hỗ
trợ, do đó giải quyết được vấn đề bùng nổ tập ứng viên. Bên cạnh đó
thì rất nhiều các thuật toán đã được đề xuất như AFPIM [15], EFPIM
[17].
Bởi vì các thuật toán khai thác tập phổ biến trên CSDL tăng
trưởng đều dựa vào những thuật toán khai thác tập phổ biến trên CSDL
tĩnh, do đó trong các mục tiếp theo của chương này thì luận văn sẽ giới
thiệu một số khái niệm cũng như một số thuật toán khai thác tập phổ
biến tiêu biểu trên CSDL tĩnh và thuật toán khai thác tập phổ biến trên

CSDL động.
1.2.2. Một số kiến thức cơ bản
a. Các khái niệm
b. Khai thác tập phổ biến
1.2.3. Phương pháp Apriori
Apriori [1, 2, 7] là thuật toán khai thác luật kết hợp do Rakesh
Agrawal, Tomasz Imielinski, Anin Sawami đề xuất vào năm 1993, là
nền tảng cho việc phát triển những thuật toán sau này. Thuật toán sinh


10
tập ứng viên từ những tập phổ biến ở bước trước, sử dụng kĩ thuật “tỉa”
để bỏ đi tập ứng viên không thỏa mãn ngưỡng hỗ trợ cho trước.
Các ký hiệu sử dụng trong thuật toán:
Lk = {l1, l2,…, li, …} tập các k-itemset phổ biến.
Ck = {c1, c2,…, ci, …} tập các k-itemset ứng viên, mỗi ci có 2
trường itemset và count dùng để chứa tập thuộc tính và độ phổ biến
của tập thuộc tính đó trong cơ sở dữ liệu.
Thuật toán:
INPUT: Tập các giao dịch D, ngưỡng hỗ trợ minsup
OUTPUT: Tập Answer bao gồm các tập phổ biến trên D
Phương pháp:
L1 = {large 1-itemset};
for (k = 2; Lk-1 ≠ ∅; k++) do begin
Ck = apriori_gen(Lk-1); // sinh tập ứng viên mới Ck;
forall giao dịch t ∈ D do begin
Ct = subset(Ck, t); // các tập ứng viên chứa
trong t;
forall tập mục ứng cử c ∈ Ct do
c.count ++ ;

end;
Lk = {c ∈ Ck | c.count ≥ minsup}
end;
Answer = k Lk ;
1.2.4. Phương pháp FP-Tree
Thuật toán xây dựng cây FP
Function createFPtree()
INPUT: CSDL D chứa các giao dịch, ngưỡng minsup.
OUTPUT: Cây FP-tree


11
Bước 1: Duyệt D và tính độ phổ biến của các item. Sắp xếp các
item theo thứ tự giảm dần của độ phổ biến, ta được tập kết quả L.
Bước 2: Tạo nút gốc cho cây T, ký hiệu là root. Duyệt D lần thứ
2. Ứng với mỗi giao tác trong D thực hiện 2 công việc sau:
• Chọn và sắp xếp những item phổ biến theo thứ tự trong f_list.
• Giao dịch đang xét được lý hiệu như sau [p|r_list] gồm 2
phần, p là phần tử item đầu tiên và P là những item còn lại của giao
dịch (không bao gồm những item không thỏa ngưỡng phổ biến). Gọi
hàm insert_tree( [p|r_list], root ).
1.2.5. Một số thuật toán khai thác tập phổ biến khác
1.2.6. Một số cấu trúc dữ liệu giúp cải thiện thuật toán
Apriori
a. Hash-tree
b. Trie
1.3. KẾT CHƯƠNG
Khai phá dữ liệu ngày càng đóng một vai trò quan trọng trong
việc tìm ra các tri thức thực sự có ích, hiệu quả tiềm ẩn trong các khối
dữ liệu thông tin khổng lồ vẫn hàng ngày đang được thu thập, lưu trữ

để giúp các cá nhân và tổ chức đưa ra được các quyết định chính xác
và nhanh chóng.
Chương 1 đã giới thiệu những kiến thức chung về lĩnh vực khai
phá dữ liêu, tuy đã có rất nhiều các giải pháp và phương pháp được
ứng dụng trong khai phá dữ liệu, trong đó nhưng trên thực tế quá trình
này vẫn gặp không ít khó khăn và thách thức như:
- Kích thước dữ liệu ngày càng lớn, có thể lên đến gigabytes,
terabytes thậm chí lớn hơn.
- Số lượng các luật rút ra từ việc khai thác dữ liệu là rất lớn.
- Các luật rút ra từ việc khai thác dữ liệu chỉ phản ánh được tình


12
trạng của dữ liệu tại một thời điểm nhất định. Để có thể rút ra được
những luật kết hợp có độ tin cậy cao và ổn định thì cần phải thu thập
dữ liệu trong một thời gian đáng kể.
- Vì vậy, có 2 vấn đề được đặt ra trong việc khai thác dữ liệu là:
- Thiết kế một thuật toán hiệu quả cho việc khai thác các luật
hoặc các mẫu phổ biến.
- Thiết kế một thuật toán hiệu quả để cập nhật và quản lý các
luật đã được khai thác.
Vấn đề thứ nhất đã được nghiên cứu từ rất lâu, có nhiều thuật
toán hiệu quả đã được đề xuất như : Apriori, FP-Tree, Apriori- Tid,
Apriori – Hybird.
Vấn đề thứ hai cũng đã được nghiên cứu và phát triển thành nhiều
thuật toán với hiệu quả sử dụng khác nhau, chúng ta sẽ tìm hiểu 1 số
thuật toán tiêu biểu để giải quyết vấn để này trong chương 2
CHƯƠNG 2
MỘT SỐ PHƯƠNG PHÁP KHAI THÁC TẬP PHỔ BIẾN
TRÊN CƠ SỞ DỮ LIỆU TĂNG TRƯỞNG

2.1. THUẬT TOÁN FUP
Thuật toán FUP (Fast-UPdate algorithm) do Cheung et al. đề
xuất năm 1996 [6]. Thuật toán xử lý trường hợp thêm giao dịch mới
vào CSDL.
2.1.1. Một số ký hiệu
Một tập X là tập phổ biến trong CSDL DBdb nếu X.support ≥
s×(D+d)


13

Hình 2.1. 4. trường hợp xảy ra khi thêm mới giao dịch vào CSDL [6]
Như vậy sẽ có 4 trường hợp xảy ra khi thêm các giao dịch mới
vào CSDL.
Trường hợp 1: Một itemset là phổ biến (large) trong CSDL ban
đầu và trong các giao dịch được thêm vào.
Trường hợp 2: Một itemset là phổ biến (large) trong CSDL ban
đầu nhưng là không phổ biến (small) trong các giao dịch được thêm
vào.
Trường hợp 3: Một itemset là không phổ biến (small) trong
CSDL ban đầu nhưng là phổ biến (large) trong các giao dịch được
thêm vào.
Trường hợp 4: Một itemset là không phổ biến (small) trong
CSDL ban đầu và trong các giao dịch được thêm vào.
Nhận xét: Trường hợp 1 thì itemset đó vẫn sẽ phổ biến trong
CSDL sau khi được cập nhật, trường hợp 4 thì itemset đó vẫn sẽ không
phổ biến trong CSDL sau khi được cập nhật, do đó trường hợp 1 và 4
sẽ không ảnh hưởng đến kết quả của tập phổ biến khai thác được.
Trường hợp 2 có thể sẽ loại bỏ đi một số itemset đã tồn tại trong tập
phổ biến của CSDL gốc, còn trường hợp 3 có thể sẽ bổ xung thêm một

số itemset mới vào tập phổ biến đã được khai thác. Một thuật toán quản
lý tốt tập phổ biến đã được khai thác trong trường hợp các giao dịch
mới được thêm vào phải làm được một số công việc sau.


14
- Đánh giá xem các các itemset thuộc tập phổ biến (large itemset)
trong CSDL ban đầu có còn phổ biến (large) trong CSDL sau khi được
cập nhật hay không.
- Tìm các itemset thuộc tập không phổ biến (small itemset)
trong CSDL ban đầu có thể trở thành phổ biến (large) trong CSDL sau
khi được cập nhật.
Tìm những itemset chỉ xuất hiện trong những giao dịch được thêm vào
và xác định xem chúng có phổ biến (large) trong CSDL sau khi được
cập nhật không
2.1.2. Chi tiết thuật toán FUP
Bước 1: Tại mỗi lần lặp, độ hỗ trợ của từng itemset trong tập
large k-itemset trong L sẽ được cập nhật dựa vào db để lọc ra những
itemset nào là không phổ biến (losers còn gọi là small itemset hay
những tập không còn là tập phổ biến trong DBdb). Ta chỉ cần quét
db để tiến hành cập nhật độ hỗ trợ.
Bước 2: Trong khi quét db thì một tập hợp các ứng viên Ck sẽ
được trích xuất ra từ db cùng với độ độ hỗ trợ. Độ hỗ trợ của các phần
tử trong Ck sẽ được cập nhật dựa vào DB để tìm ra tập các tập phổ biến
mới.
Bước 3: Tập Ck sẽ được cắt tỉa dựa vào db trước khi dựa vào DB
Bước 4: Kích thướt của CSDL sau khi được cập nhật trong mỗi
lần lặp sẽ được giảm xuống bằng phép cắt tỉa dựa vào các item trong
db.
Bước 1:

Bổ đề 1: Một 1-itemset

X  L1 là không phổ biến (  L1 )

trong CSDL sau khi được cập nhật DBdb nếu và chỉ nếu X.supportUD
< s × (D+d)
CM: Dựa vào định nghĩa độ hỗ trợ tối thiểu và định nghĩa large


15
1-itemset.
Bổ đề 2: Một 1-itemset

X  L1

có thể trở thành phổ biến

(winner hay large itemset  L1 ) trong CSDL sau khi được cập nhật
DBdb nếu và chỉ nếu X.supportd ≥ s×d
CM: Vì

X  L1

nên X.support < s×D

Nếu X.support < s×d thì X.supportUD = X.supportD +
X.supportd < s×(D+d) nên X  L1 . Vì vậy để X  L1 thì
X.supportd ≥ s×d

Hình 2.2. Tiến trình thực hiện bước 1 trong thụât toán FUP [6]

Mô tả chi tiết bước 1:
- Quét db, ∀X ∈ L1, cập nhật X.supportUD, sau khi quét xong db
thì ∀X ∈ L1 kiểm tra X.supportUD < s × (D+d) nếu X thỏa thì X là loser
và loại X ra khỏi L1
- Trong khi quét db thì có tập C1 dùng để lưu các itemset X  T
với Tdb và X  L1, sau đó dựa vào bổ đề 2 nếu X C1 và X thỏa
X.supportd < s×d thì loại X ra khỏi C1
- Quét DB để cập nhật X.supportUD ∀X ∈ C1, bằng cách kiểm tra
độ hỗ trợ các tập phổ biến trong C1 sẽ được tìm thấy. Ta kết hợp các
tập phổ biến vừa tìm thấy trong C1 với tập L1 ta được tập L1
2.1.3. Ví dụ


16
2.2. KHÁI NIỆM PRE-LARGE-ITEMSET
2.3. THUẬT TOÁN PRE-LARGE-ITEMSET
2.3.1. Các ký hiệu và lý thuyết liên quan
2.3.2. Thuật toán
2.3.3. Ví dụ minh họa
2.4. THUẬT TOÁN PRE-FUFP
2.3.4. Các ký hiệu
2.3.5. Thuật toán
2.3.6. Ví dụ minh hoạ
2.5. THUẬT TOAN PRE-FUT
Thuật toán Pre-FUT sử dụng cấu trúc trie kết hợp với khái niệm
pre-large itemset để giải quyết cho trường hợp thêm mới giao dịch vào
CSDL.
Trie [5] là một cấu trúc được cài đặt hiệu quả trong thuật toán
Apriori [1, 2]. Với cấu trúc Trie thì việc phát sinh tập ứng viên mới và
việc xác định độ hỗ trợ của các tập ứng viên sẽ dễ dàng hơn so với khi

cài đặt thuật toán Apriori bằng cấu trúc cây băm [2]. Cấu trúc Trie sẽ
lưu trữ hết tất cả các tập phổ biến khai thác được. Ta chỉ cần duyệt qua
cấu trúc Trie theo chiều sâu (DFS) hoặc theo chiều rộng (BFS) là ta có
thể có được tập tất cả tập phổ biến.
2.3.7. Các ký hiệu
2.3.8. Thuật toán Pre-FUT
2.3.9. Ví dụ thuật toán Pre-FUT
2.6. KẾT CHƯƠNG
Chương 2 đã trình bày cho chúng ta 1 số thuật toán tiêu biểu để
khai phá tập phổ biến trên CSDL tĩnh: Apriori, FP-Tree, Apriori-Tid,
Apriori- Hybrid. Các thuật toán khai phá tập phổ biến trên CSDL tĩnh :
FUP, Pre-large- Itemset, Pre-FUP, Pre-FUT. Mỗi thuật toán đều có


17
những ưu điểm và hạn chế riêng, trong đó nổi bật thuật toán Pre-FUT
được ra đời sau cùng đã khắc phục được khuyết điểm của các thuật
toán đi trước, cải thiện được hiệu suất xử lý các CSDL lớn khi phát
sinh thêm mới giao dịch. Chúng ta sẽ thực nghiệm điểu này tại chương
sau.
CHƯƠNG 3
THỰC NGHIỆM VỚI DỮ LIỆU THỰC TẾ
3.1. MÔ TẢ DỮ LIỆU
Trong đồ án này sử dụng dữ liệu từ tất cả các giao dịch mua
hàng xảy ra từ ngày 01/12/2010 đến ngày 09/12/2011 của 1 công ty
bán lẻ đồ lưu niệm trực tuyến tại Anh.
Số lượng giao dịch : 540909
Số lượng sản phẩm : 3958
Dữ liệu được cung cấp tại website
/>

Hình 3. 1. Các giao dịch được đưa vào thuật toán


18

Hình 3. 2. Các giao dịch được chuyển đổi sang file .DAT
3.2. MÔ TẢ CHƯƠNG TRÌNH
Luận văn sẽ so sánh hiệu năng của thuật toán Pre-FUT và thuật
toán pre-large-itemset được nêu ở mục 2.3 chương 2.
Thuật toán pre-large-itemset sẽ được cài đặt với cấu trúc cây
băm.
Thuật toán Pre-FUT được cài đặt trên cơ sở thuật toán Apriori
thuần túy, sử dụng cấu truc Trie, và sử dụng khải niệm Pre Large
Itemset để xử lý CSDL động khi phát sinh giao dịch. Kết quả khi chạy
thành công thuật toán sẽ là 1 cấu trúc câu Trie lưu trữ tập pre-large và
large của toàn bộ CSDL, đồng thời cũng lưu trữ tập rescan itemset để
phục vụ cho lần thêm giao dịch mới tiếp theo.

Hình 3.3. Các file sinh ra sau khi thực hiện thành công các thuật toán


19

Hình 3.4. File kết quả tập large được sinh ra khi thực hiện thành
công thuật toán

Hình 3.5. File kết quả tập pre large được sinh ra khi thực hiện thành
công thuật toán



20

Hình 3.6. File report tổng hợp thời gian xử lý của tập phổ biến khi
phát sinh các giao dịch mới
Trong phần thực nghiệm thì thuật toán Pre-FUT và thuật toán
pre-large-itemset sẽ được cài đặt bằng C++ trên máy tính PC với CPU
Intel Core i5, 2.3Ghz, RAM 4GB, Windows 10. CSDL thực nghiệm
lấy từ nguồn như trên.
Chương trình thực hiện: Code Block:


21
Bảng 3.1. CSDL thực nghiệm
Databases
Online retail

#Trans

#Items

531909

3958

3.3. ĐÁNH GIÁ
Thí nghiệm thứ nhất sẽ so sánh hiệu năng của 2 thuật toán khi
hai ngưỡng Sl và Su biến thiên. Các thông số được thể hiện trên Bảng
3.7.
Kết quả thực nghiệm thể hiện trên hình 3.7. Số lượng tập prelarge và large itemset được thể hiện trên Bảng 3.3
Bảng 3. 2. Bảng giá trị thông số của các CSDL thực nghiệm

Databases

D

T

Sl

Su

f

Độ biến thiên
của minsup

Onlie

53190 3958 0.03 0.08 13727

0.002

retail
60
50
40
30
20

10
0

0.08

0.082

0.084

Pre- large- itemset

0.086

0.088

0.01

Pre-FUT

Hình 3. 3: Kết quả so sánh trên CSDL Online retail trong
thí nghiệm thứ nhất


22
Bảng 3. 3. Số lượng tập pre-large và large itemset của CSDL
Sl

0.03

0.032

0.034


0.036

0.038

0.04

Su

0.08

0.082

0.084

0.086

0.088

0.01

439

406

375

351

332


315

52905

19271

7909

4384

2792

1972

Large
Prelarge

Thí nghiệm thứ hai sẽ so sánh hiệu năng của 2 thuật toán khi
thêm liên tiếp hàng loạt giao dịch. Các thông số thể hiện trên Bảng 3.4.
Kết quả thực nghiệm trong lần thứ hai lần lượt thể hiện trên các hình
3.8
Bảng 3. 4. Các thông số trong thứ nghiệm thứ hai
Databases

Sl

Su

D


T

f

Số lần
thêm

Online retail

0.04

0.09

53190

3958

13727

140
120
100
80
60
40

20
0

Pre- large- itemset


Pre-FUT

Hình 3. 4. Kết quả so sánh trên CSDL Online retail trong
thí nghiệm hai

10


23
Nhận xét:
Trong thí nghiệm thứ 2 với CSDL Online retail, ứng với 2 ngưỡng
Sl = 0.04 và Su = 0.09 thì f = 13727 và mỗi lần thí nghiệm 2 sẽ thêm
vào CSDL gốc 1000 giao dịch. Như vậy đến lần thêm thứ 3 thì tổng số
giao dịch thêm vào kể từ lần thêm đầu tiên > f nên bắt buộc thuật toán
sẽ phải xử lý lại toàn bộ CSDL để xử lý những itemset trong tập rescan
itemset, xác định itemset nào thuộc tập pre-large và large itemset để
cập nhật lại cây trie phục vụ cho lần thêm giao dịch kế tiếp. Trên Hình
3.8 có những điểm đồ thị thay đổi đột ngột, đó là những điểm mà tại
đó thuật toán phải xử lý lại toàn bộ CSDL. Do đó thời gian sẽ có sự
chênh lệch rất lớn so với khi chỉ xử lý những giao dịch cần thêm vào.
3.4. KẾT CHƯƠNG
Dựa vào kết quả thực nghiệm, có thể thấy thời gian thực thi của
thuật toán Pre-FUT (sử dụng khái niệm pre-large itemset kết hợp với
cấu trúc Trie) nhanh hơn gấp nhiều lần so với thuật toán FUP (sử dụng
khái niệm pre-large itemset kết hợp với cấu trúc cây băm [2]) ngay cả
trong trường hợp thuật toán phải quét và xử lý lại toàn bộ CSDL gốc.
KẾT LUẬN
1. KẾT QUẢ ĐẠT ĐƯỢC
Như đã trình bày trong các chương trước, mục tiêu của luận văn

đề ra là nghiên cứu các thuật toán khai phá tập phổ biến trên CSDL
tăng trưởng và có thẻ chọn ra 1 thuật toán tối ưu nhất để có thể xử lý
CSDL tăng trưởng hiệu quả nhất, giảm thời gian phải xử lý CSDL khi
có phát sinh thêm giao dịch, để từ đó phát triển các luật khai phá kết
hợp 1 cách hiệu quả hơn.
Thuật toán Pre- FUT được phát triển từ các thuật toán khai phá