THUẬT TOÁN KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN
TRONG CƠ SỞ DỮ LIỆU LỚN THÔNG QUA MẪU ĐẠI DIỆN
Nguyễn Hưng Long
Khoa Hệ thống thông tin kinh tế và Thương mại điện tử, Đại học Thương mại
Nguyễn Minh Hồng
Khoa Tốn - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
Tóm tắt
Bài viết đề xuất thuật toán RSFPGrowth khai phá tập mục thường xuyên trong
cơ sở dữ liệu lớn thơng qua mẫu đại diện. Thuật tốn RSFPGrowth cho phép thay vì tìm
tập tất cả các tập mục thường xuyên trong cơ sở dữ liệu lớn bằng cách tìm tập chứa hầu
hết các tập tập mục thường xuyên từ tập mẫu đại diện các giao tác. Bởi vì khi cỡ mẫu n
cần lấy cho tập mẫu sẽ tăng chậm so với cỡ tổng thể nên độ hiệu quả của việc khai phá
tập tập mục thường xuyên thông qua lấy mẫu đại diện các giao tác sẽ càng cao khi kích
thước của cơ sở dữ liệu ban đầu càng lớn.
Từ khóa: Khai phá dữ liệu, tập mục thường xuyên, cơ sở dữ liệu, mẫu đại diện, FPGrowth
1. Mở đầu
Trong những năm gần đây, khai phá dữ liệu (KPDL) đã trở thành đề tài thu hút
sự quan tâm của nhiều nhà nghiên cứu và đã được ứng dụng thành công trong mọi mặt
của đời sống - xã hội. Khai phá dữ liệu được định nghĩa là q trình trích lọc khơng tầm
thường những thơng tin hữu ích chưa biết từ các cơ sở dữ liệu (CSDL) lớn (có chứa đến
hàng vạn, triệu các giao tác).
Khai phá tập mục thường xuyên (TMTX) được biết đến như là bài toán con của
bài toán khai phá dữ liệu và đã được giới thiệu lần đầu tiên vào năm 1993 bởi Agrawal
R. và Srikant R. [5, 6], thuộc Trung tâm nghiên cứu Almaden của IBM (Mỹ), nhằm phân
tích CSDL bán hàng tại siêu thị. Qua q trình phân tích sẽ giúp cho nhà phân tích lựa
chọn các phương án tốt nhất trong hoạt động kinh doanh của siêu thị. Để giải quyết bài
toán này, các tác giả đề xuất thuật toán Apriori. Tại hội nghị quốc tế về khai phá dữ liệu
vào tháng 12 năm 2006 đã đánh giá thuật toán Apriori đứng trong top 10 thuật toán khai
phá dữ liệu [9]. Hiện đã có nhiều nghiên cứu, xây dựng các thuật tốn khai phá TMTX
được dựa trên thuật toán Apriori (gọi là các thuật toán kiểu Apriori). Thuật toán Apriori
và các thuật tốn kiểu Apriori có hai nhược điểm lớn: Phải sinh ra khối lượng khổng lồ

các tập ứng viên và duyệt CSDL giao tác nhiều lần.
TMTX là công cụ hiệu quả để khai phá các luật kết hợp (association rule), tập
mục đóng (closed itemset), tập mục tuần tự (sequential itemset), các phụ thuộc hàm
(functional dependencies), ...
Để khắc phục hạn chế của thuật toán Apriori, Han J. và cộng sự [7, 8] tại Trường
Đại học Simon Fraser (Canada) đã đề xuất thuật toán FP-growth. Thuật toán FP-growth
khai phá TMTX được xây dựng dựa trên những kĩ thuật cơ bản sau: (1) Nén toàn bộ
CSDL giao tác lên một cấu trúc cây, gọi là cây FP-tree, nhờ đó giảm chi phí cho số lần
duyệt CSDL giao tác trong quá trình khai phá. (2) Dùng phương pháp chia để trị (devide285


and-conquer), bằng cách trong quá trình xây dựng và khai phá dữ liệu được chia làm
thành các bài toán nhỏ hơn, theo nghĩa xây dựng các cây FP-tree có điều kiện và khai
phá các TMTX trên các cây FP-tree có điều kiện đã được tạo ra. Do vậy, quá trình khai
phá cây được phát triển dần các mẫu mà không sinh ra nhiều các tập mục ứng viên và
nó sẽ làm giảm khối lượng thời gian tính tốn. Q trình khai phá TMTX được thực
hiện theo hai pha: Pha xây dựng cây FP-tree và pha khai phá cây FP-tree bằng thuật tốn
FP-growth.
Mặc dù thuật tốn FP-growth có những ưu điểm (về tổ chức dữ liệu, bộ nhớ, thời
gian tính tốn) hơn thuật toán Apriori nhưng đối với CSDL giao tác lớn cần khai phá sẽ
khơng hiệu quả.
Để có thể áp dụng thuật tốn FP-growth trên các CSDL kích thước lớn, trong bài
viết này chúng tơi trình bày một phương pháp tiếp cận xấp xỉ. Thay vì tìm tập TMTX
trong CSDL cần khai phá, ta sẽ tìm tập chứa hầu hết các tập mục từ CSDL mẫu đại diện.
Độ hiệu quả của việc khai phá thông qua lấy mẫu sẽ càng cao khi kích thước của CSDL
ban đầu càng lớn, bởi vì cỡ mẫu n cần lấy tăng chậm so với cỡ tổng thể.
Nội dung tiếp theo của bài viết là như sau: Mục 2 giới thiệu về mơ hình bài toán và
thuật toán FP-Growth khai phá TMTX trong CSDL giao tác; Mục 3 trình bày phương pháp
tiếp cận xấp xỉ: khai phá TMTX thông qua khai phá mẫu đại diện và cuối cùng là kết luận.
2. Khai phá tập mục thường xuyên trong csdl giao tác và thuật toán fp-growth

2.1. Bài toán khai phá tập mục thường xuyên trong CSDL giao tác [5, 6]
Định nghĩa 1. Cho I= {i , i , … , i } là tập các phần tử. Mỗi phần tử trong I được
gọi là một mục (item). Một tập con X ⊆ Iđược gọi là một tập mục (itemset). Số phần tử
trong X kí hiệu là Card(X). Nếu Card(X) = k, (k ∈ Z) thì X được gọi là k-tập mục. Nếu
Card(X)=1 thì X là 1-tập mục hay còn được gọi là mục đơn.
Để đơn giản, thay vì viết k-tập mục {i , i , … , i } đôi khi ta viết i i … i . Chẳng
hạn, tập mục {a, b, c} được viết ngắn gọn là abc.
Định nghĩa 2. Một giao tác (transaction) là một bộ T = 〈TID
, X〉, với TID là định
danh giao tác (transaction identifier) duy nhất và X ⊆ Ilà một tập mục. Giao tác T gọi
là chứa tập mục Y nếu Y ⊆ T.
Định nghĩa 3. CSDL giao tác (transaction database) là một tập các giao tác
TDB = {T , T , … , T }.
Biểu diễn CSDL giao tác ngang : CSDL là một tập các giao tác. Trong đó, mỗi
giao tác bao gồm một định danh (thứ tự) TID và một danh sách các mục.
Ví dụ. Trong Bảng 1 dưới đây là biểu diễn ngang của CSDL giao tác.
Bảng 1. Biểu diễn ngang của CSDL giao tác
TID
T1

Tập các mục
abcdef

T2
T3

bcefh
acdefgh

286



Định nghĩa 4. Cho I= {i , i , … , i } là tập các mục và tập mục X ⊆ I
. Ta gọi độ
hỗ trợ (support) của X trong CSDL giao tác DT được ký hiệu supp(X), là tỷ lệ phần trăm
các giao tác trong DT chứa X, tức là:
supp(X) =

card({T ∈ DT|X ⊆ T})
card(DT)

Với card(TDB) là số các giao tác của DT.
Ta có: 0 ≤ supp(X) ≤ 1, ∀X ⊆ I
.
Định nghĩa 5. Cho tập mục X ⊆ Ivà ngưỡng độ hỗ trợ tối thiểu minsupp
(minimum support) được xác định bởi người dùng, 0 < minsupp ≤ 1. Nếu supp(X) ≥
minsupp thì X được gọi là TMTX (frequent itemset) với độ hỗ trợ tối thiểu minsupp,
hay ta nói X thỏa minsupp, trường hợp ngược lại ta nói X là tập khơng thường xun
(infrequent itemset), hay ta nói X khơng thỏa minsupp.
2.2. Thuật tốn FP-growth
Nội dung thuật tốn FP-growth [7, 8] với ý tưởng chính như sau:
- Nén toàn bộ các giao tác lên một cấu trúc cây, gọi là cây FP-tree, nhờ đó giảm
chi phí cho số lần duyệt CSDL giao tác. Mỗi nút trong cây FP-tree có một mục, các nút
chúng được sắp xếp để tiện cho việc chèn các giao tác lên cây và các nút xuất hiện
thường xuyên dễ dàng chia sẻ với các nút ít xuất hiện hơn, đồng thời các nút khơng
thường xuyên sẽ bị sớm loại bỏ mà không làm ảnh hưởng kết quả khai phá. Bước này
chỉ cần duyệt CSDL giao tác một lần.
- Áp dụng phương pháp chia để trị (devide and conquer). Quá trình khai phá dữ
liệu được chia làm thành các phần việc nhỏ hơn, ở đó tiến hành xây dựng các cây FPtree có điều kiện và khai phá các TMTX trên các cây FP-tree có điều kiện đã được tạo
ra. Do vậy, quá trình khai phá cây được phát triển dần các mẫu mà không sinh ra nhiều

tập mục ứng viên và đồng thời sẽ làm giảm khối lượng tính tốn. Bước xây dựng cây
FP-tree chỉ cần duyệt thêm một lần trên CSDL giao tác.
- Q trình khai phá thực hiện theo hai pha chính: (1) Xây dựng cấu trúc cây FPtree; (2) Khai phá cây FP-tree bởi thuật toán FP-growth.
3. Khai phá tập mục thường xun thơng qua mẫu đại diện
Thuật tốn FP-growth có ưu điểm hơn thuật toán Apriori [7], nhưng nếu khai thác
trên các CSDL lớn thì thuật tốn FP-growth sẽ khơng hiệu quả. Để áp dung thuật toán
FP-growth trên các CSDL lớn chúng tôi đề nghị phương pháp tiếp cận xấp xỉ. Thay vì
tìm tập tất cả cácTMTX trong CSDL cần khai phá, ta sẽ tìm tập chứa hầu hết các tập
mục này từ CSDL mẫu đại diện [1, 2, 3]
Trên thực tế các đối tượng cùng loại mà các nhà thống kê quan tâm nghiên cứu
được gọi là tổng thể. Tổng thể thường bao gồm một số lượng lớn, có khi rất lớn các đối
tượng. Nghiên cứu toàn bộ đối tượng trong tổng thể là việc làm khó khăn hoặc khơng
thể thực hiện được, chưa kể là có khi khơng có nghĩa. Vì vậy người ta thường dùng
phương pháp chọn mẫu, tức là từ một tổng thể có N đối tượng (N được gọi là kích thước
của tổng thể) rút ra n đối tượng (n được gọi là kích thước mẫu), tiến hành nghiên cứu
trên mẫu đó rồi căn cứ vào kết quả thu được mà suy rộng ra cho tổng thể. Các kết quả
suy rộng này không thể tránh khỏi những sai lệch. Độ lớn của các sai lệch phụ thuộc
287


vào hai yếu tố cơ bản là phương pháp chọn mẫu và kích thước mẫu. Vì vậy, vấn đề quan
trọng là làm sao đảm bảo cho mẫu phải phản ánh đúng đắn cấu trúc của tổng thể, tức là
mẫu phải mang tính đại diện để cho sai lệch do chọn mẫu càng nhỏ càng tốt. Kích thước
mẫu càng lớn, thì tính đại diện của mẫu càng cao, tuy nhiên khi đó chi phí cũng sẽ càng
lớn [1, 2, 3].
Trong thực hành, tùy vào tình huống cụ thể, người ta có thể áp dụng những phương
pháp chọn mẫu khác nhau. Mỗi phương pháp đều có ưu điểm và nhược điểm riêng. Có
một số phương pháp chon mẫu sau: Chọn mẫu ngẫu nhiên đơn giản (Simple Random
Sampling); Chọn mẫu ngẫu nhiên phân vùng (Stratified Random Sampling); Chọn mẫu
có hệ thống (Systematic Sampling); ... [1, 2, 3]

Để chọn mẫu khai phá dữ liệu, người ta thường sử dụng phương pháp chọn mẫu
ngẫu nhiên đơn giản (khơng hồn lại), vì những lý do sau: (1) Dễ mô phỏng và cài đặt.
(2) Việc chọn mẫu ngẫu nhiên đơn giản có thể mơ phỏng và thực hiện bằng cách sử
dụng các thuật toán (hàm) tạo số ngẫu nhiên. (3) Ước lượng tỷ lệ dựa trên mẫu ngẫu
nhiên đơn giản là ước lượng không chệch. (4) Không cần có bất kỳ một thơng tin tiên
nghiệm nào về quần thể [1, 2, 3].
3.1. Xác định cỡ mẫu trong cơ sở dữ liệu giao tác
Tư tưởng chính của thuật toán là như sau: Trước tiên, từ CSDL giao tác ban đầu,
chọn một mẫu ngẫu nhiên đơn giản các giao tác. Sau đó, áp dụng thuật tốn FP-growth
[7, 8] khai phá TMTX trên CSDL mẫu. Trong [1, 4] đã phân tích, chỉ ra việc chọn mẫu
ngẫu nhiên đơn giản như dưới đây:
Xác định cỡ mẫu
Giả sử CSDL DT bao gồm N giao tác, trong đó có SC(DT,X) giao tác chứa tập
mục X. Khi đó xác suất để một giao tác chứa X là p=sup(X)=SC(DT,X)/N.
Ký hiệu S là mẫu gồm n giao tác được chọn lần lượt bằng phương pháp chọn ngẫu
nhiên khơng hồn lại từ DT.
Gọi SC(S,X) là số giao tác trong S chứa tập mục X . Khi đó SC(S,X) tuân theo luật
phân phối siêu bội với hàm xác suất:
Pr

( , ) = )=

,

= 0,1, … ,

(1)

Giá trị kỳ vọng, phương sai của SC(S,X) lần lượt là [1]:
( , ) =


(2)

( , ) = 1−

(1 − ) ≈ 1 −

(1 − )

(3)

Với mẫu cỡ n, người ta thường lấy ̂ = ( , )/ làm giá trị ước lượng cho xác
suất p (tức support(DT,X)). Từ (2) và (3) suy ra:
( ̂) =
( ̂) = 1 −

(4)
(

)

≈ 1−

(

)

(5)

Vì E(p) = p, ̂ là một ước lượng không chệch của p.

Trong [1] đã chứng minh được rằng, khi n đủ lớn (n>=30), đại lượng ngẫu nhiên
chuẩn hóa
288


=

(

(6)

)

sẽ có phân phối tiệm cận phân phối chuẩn chuẩn tắc
( )=

(0,1) với hàm phân phối:

∫

√

(7)

Giả sử với sai số tuyệt đối d và xác suất rủi ro α cho trước, ta muốn ước lượng xác
suất p bằng p sao cho
(| − ̂ | < ) = 1 −

(8)


Ký hiệu z
là phân vị mức 1 − α 2 của đại lượng Z có phân phối (3.7), nghĩa
là z
là giá trị thỏa mãn hệ thức:
<

=1−

(9)

Khi đó
| |<

=1−

(10)

Kết hợp các hệ thức (6), (8) và (9) suy ra, nếu muốn ước lượng p với sai số tuyệt
đối d và xác suất rủi ro α cho trước thì cỡ mẫu n phải thỏa hệ thức:
=
=

Hay

1−
(
(

(


)

(11)

)

(12)

)

Trong công thức (11), p là giá trị chưa biết, cần ước lượng. Tuy vậy, vì tích p(1p) đạt cực đại là 1/4 khi p=1/2, ta có thể lấy
= max

(
(

)
)

=

(13)

Do cỡ mẫu là số nguyên, nên lấy
=

(14)

3.2. Thuật toán khai phá TMTX trong CSDL giao tác thông qua mẫu đại diện
3.2.1. Ý tưởng chính

Với cỡ mẫu n xác định theo (14), việc lấy mẫu S từ CSDL giao tác DT được tiến
hành như sau:
- Đánh số thứ tự tất cả các giao tác trong DT.
- Tạo n số nguyên ngẫu nhiên khác nhau trong khoảng [1, N],
- Lấy CSDL mẫu S là tập n giao tác có số thứ tự là các số nguyên ngẫu nhiên đã
tạo được.
Trong thực hành, sai số tuyệt đối d và rủi ro
và 0.01.
289

thường được chọn tương ứng là 0.05


3.2.2. Thuật tốn RSFPGrowth

Bảng 2. Bảng các kí hiệu trong thuật toán RSFPGrowth
Ký hiệu
DT
minsupp

Ý nghĩa
CSDL giao tác ban đầu
Độ hỗ trợ tối thiểu

Z

Phân vị mức 1 − /2 của phân phối chuẩn chuẩn tắc (tức là giá trị
của
(0,1))




Độ rủi ro

d

Cận trên của sai số

N

Tổng số giao tác trong CSDL ban đầu

n

Cỡ mẫu

S

Tập các giao tác được chọn vào mẫu

Nội dung thuật toán RSFPGrowth khai phá TMTX trên CSDL mẫu như sau:
Input: CSDL DT, tổng số giao tác N trong CSDL giao tác, cỡ mẫu n, hai ngưỡng hỗ trợ
minsupp, cận trên của sai số d, độ rủi ro .
Output: Tập các TMTX.
Method: Thuật toán RSFPGrowth
1) if n>=30
2)
3) {
4) z = Calculate();
5)


=

6) for (i = 1; i<=n; i++) do
7) a(i) = GenRandom(N);
8) sort(a);
9) for each transaction

Ti in DT (i = 1, 2, … , N) do

10) if (i = a[i]) then S = S  Ti ;
11) execute FP-Growth;
12) }
13) else
14) execute FP-Growth;

290


15) end.

Các thủ tục trong RSFPGrowth là như sau:
Calculate(): Tính

=

là phân vị mức

2 của phân phối chuẩn tắc
GenRandom(N): Tạo số nguyên ngẫu nhiên trong khoảng từ 1 đến N.


(0,1).

sort(a): Sắp xếp các phần tử của mảng a theo thứ tự giá trị tăng dần.
execute FP-Growth: Thực hiện thủ tục FPGRowth trên CSDL mẫu S.
3.2.3. Ví dụ

Để đơn giản cho quá trình xử lí tính tốn của ví dụ. Trong ví dụ này chúng tơi giả
sử có một CSDL lớn và sau khi chọn mẫu xong, đánh số định danh các giao tác ta được
CSDL giao tác gồm 10 giao tác như trong bảng 3 dưới đây:
Bảng 3. Bảng CSDL giao tác
TID

Tập các mục

1

acdef

2

bcf

3

abcde

4

def


5

ade

6

abce

7

cdef

8

abcde

9

ace

10

acde

Hãy tìm TMTX từ CSDL giao tác trên với ngưỡng độ hỗ trợ tối thiểu minsupp=5.
Quá trình thực hiện thuật tốn FP-growth được mơ tả như hai pha dưới đây.
Pha 1: Xây dựng cây FP-tree.
Ý tưởng chính: Duyệt một lần CSDL giao tác để tính độ hỗ trợ của các mục đơn,
loại bỏ các mục đơn không thỏa mãn ngưỡng độ hỗ trợ tối thiểu minsupp. Tiếp đến,

duyệt lại một lần CSDL giao tác, loại bỏ các mục không thường xuyên trong các giao
tác và sắp xếp các mục theo thứ tự giảm dần của độ hỗ trợ, sau đó chèn lần lượt các giao
tác lên cây FP-tree.
Duyệt CSDL lần thứ nhất, tính độ hỗ trợ của các mục đơn, ta có:
SC(a) = 7; SC(b) = 8; SC(c) = 6; SC(d) = 2; SC(e) = 3.
291


Mục “d” bị loại do không thỏa minsupp=3. Vậy L = {a, b, c, e}.
Sắp xếp các mục theo thứ tự giảm dần của độ hỗ trợ được bảng 4:
Bảng 4. Các mục đơn sau khi đã sắp xếp giảm dần theo độ hỗ trợ
Các mục

SC

b

8

a

7

c

6

e

3


d

2

Duyệt CSDL giao tác lần thứ hai, loại bỏ các mục không thường xuyên trong các
giao tác và sắp xếp lại các mục theo thứ tự giảm dần của độ hỗ trợ ta được bảng 8. Chèn
các giao tác Bảng lên cây FP-tree, ta thu được cây bởi hình 1.
Bảng 5. Sắp xếp các 1-tập mục thường xuyên theo thứ tự giảm dần
TID

Tập các mục

1

bae

2

bace

3

bc

4

ba

5


ac

6

bc

7

ac

8

b

9

bac

10

bae

292


Hình 8. Cây FP-tree sau khi chèn các giao tác của bảng 6
Pha 2: Khai phá cây FP-tree bởi thuật tốn FP-growth.
Ý tưởng chính: Xét trong bảng đầu mục của cây FP-tree lần lượt các mục từ dưới
lên, với mỗi mục xây dựng cây điều kiện, khai phá cây điều kiện cho mục này, loại bỏ

cây điều kiện sau khi khai phá xong. Xây dựng, khai phá và loại bỏ cây điều kiện cho
mục tiếp theo. Quá trình sẽ kết thúc sau khi xét tất cả các mục trong bảng đầu mục.
Qui trình thực hiện xây dựng, khai phá cây FP-tree xét lần lượt các mục “e”, “c”,
“a”, “b” (theo thứ từ dưới lên trong bảng đầu mục).
- Xây dựng và khai phá cây điều kiện của “e”:
CSDL điều kiện của “e” bao gồm các nhánh tiền tố {bac: 1; ba: 2}.
Từ CSDL điều kiện ta có cây FP-tree cho mục “e” trong hình 2

Hình 2. Cây FP-tree(e)
Từ bảng đầu mục ta có 2-tập mục ứng viên xuất hiện cùng với “e” và độ hỗ trợ
tương ứng là 〈ae: 3; be: 3; ce: 1〉. Tập mục “ce” không thỏa minsupp.
Nhập “ae” và “be” vào L, ta được L = {a, b, c, e, ae, be}.
Tiếp tục khai phá bằng cách phát triển dần 2-tập mục “ae” và “be”.
Khai phá cây điều kiện của “ae”, có một 3-tập mục ứng viên “bae” với độ hỗ trợ 3
thỏa minsupp.

293


Hình 3. Cây FP-tree(ae)
Khai phá cây điều kiện của “be”, thu được cây rỗng.
Vậy ta thu được L = {a, b, c, d, e, ae, be, bae}.
Xóa tất cả các nút “e” trên cây FP-tree và cây điều kiện của “e”.
- Xây dựng và khai phá cây điều kiện của “c”:
CSDL điều kiện của “c” bao gồm các nhánh tiền tố {ba: 2; b: 2, a: 2}.
Từ CSDL điều kiện ta có cây FP-tree cho mục “c” trong hình 4.

Hình 4. Cây FP-tree(c)
Từ bảng đầu mục ta có các 2-tập mục ứng viên xuất hiện cùng với “c” và độ hỗ trợ
tương ứng là 〈ac: 4; bc: 4〉, đều thỏa minsupp được nhập vào L.

Tiếp tục khai phá cây điều kiện của “ac”, thu được một 3-tập mục “bac” với độ hỗ
trợ là 2, không thỏa minsupp, khai phá cây điều kiện của “bc” ta thu được cây rỗng.
Vậy ta được L = {a, b, c, e, ae, be, bae, ac, bc}.
Xóa tất cả các nút “c” trên cây FP-tree và cây điều kiện của “c”.
- Xây dựng và khai phá cây điều kiện của “a”:
CSDL của “a” có một nhánh tiền tố {b: 5}. Ta có cây FP-tree cho mục “a” như
hình 5.

Hình 5. Cây FP-tree(a)
Dễ thấy chỉ có một 2-tập mục ứng viên “ba” với độ hỗ trợ trợ là 5, thỏa mãn
minsupp. Khai phá cây điều kiện của tập mục “ba” được cây rỗng.
Vậy ta được L = {a, b, c, e, ae, be, bae, ac, bc, ba}.
Xóa tất cả các nút “a” trên cây FP-tree và cây điều kiện của “a”.
- Xây dựng và khai phá cây điều kiện của “b”:
Ta thu được cây rỗng.
294


Cuối cùng ta thu được TMTX cùng với độ hỗ trợ như sau:
L = {a: 7, b: 8, c; 6, e: 3, ae: 3, be: 3, bae: 3, ac: 4, bc: 4, ba: 5}.
Kết luận
Trong bài viết này chúng tôi đề xuất thuật toán RSFPGrowth khai phá TMTX
trong CSDL lớn thơng qua mẫu đại diện. RSFPGrowth cho phép thay vì tìm tập tất
cả các TMTX trong CSDL lớn bằng cách tìm tập chứa hầu hết các TMTX từ tập
mẫu đại diện các giao tác. Độ hiệu quả của việc khai phá thơng qua lấy mẫu sẽ càng
cao khi kích thước của CSDL ban đầu càng lớn, bởi vì cỡ mẫu n cần lấy tăng chậm
so với cỡ tổng thể.
Thuật toán RSFPGrowth là công cụ hiệu quả để khai phá các luật kết hợp
(association rule), tập mục đóng (closed itemset), tập mục tuần tự (sequential itemset),
các phụ thuộc hàm (functional dependencies), ...

Thuật tốn RSFPGrowth có thể áp dụng cho các bài tốn khác nhau trong thực tiễn
như: phân tích đầu tư chứng khốn, phân tích giỏ hàng của siêu thị, phân tích các dịng
kích hoạt web, ...
Tài liệu tham khảo

[1] Trần Tuấn Điệp, Lý Hồng Tú (2003). Giáo trình lý thuyết xác suất và thống kê tốn
học, NXB Giao thơng Vận tải, Hà Nội.
[2] Trần Doán Phú (2008), Lý thuyết xác suất và Thồng kê toán, NXB Thống kê.
[3] Đặng Hùng Thắng (2009), Thống kê và ứng dụng, NXB Giáo dục
[4] Nguyễn Hưng Long (2012), Khai phá tập mục thường xuyên thông qua mẫu đại diện,
Kỷ yếu Hội thảo quốc gia lần thứ XV, Một số vấn đề chọn lọc của Công nghệ thông
tin và truyền thông – Hà Nội, 03-04/12/2012.
[5] Aggarwal, C. In C. Aggarwal (Ed.) (2007), Data Streams: Models and algorithms.
Springer,
[6] Agrawal R., Srikant, R., (1994), Fast Algorithms for Mining Association Rules. In:
20th Int. Conf. on Very Large Data Bases (VLDB), pp. 487–499.
[7] Han J., and Kamber M. (2000), Data Mining: Concepts and Techniques, Morgan
Kanufmann.
[8] Han J., Pei J., Yin Y., Mao R., (2004), Mining frequent patterns without candidate
generation: a frequent-pattern tree approach, Data Mining and Knowledge Discovery
8, pp. 53–87,.
[9]

Wu X, Kumar V., Ross Q. J., Ghosh J., Yang Q., Motoda H., McLachlan G. J., Angus
Ng., Liu B., Yu P. S., Zhou Z. H., Steinbach M., Hand D. J., Steinberg D., (2008), Top
10 algorithm in data mining, Knowledge and Information Systems, pp. 1-37.

295