24
Về mặt thực nghiệm demo xây dựng cây Fp-tree từ dữ
liệu cho trước và khai phá các tập phổ biến theo hai cách là
khai phá tuần tự (QFP-growth) và khai phá song song (cải tiến
QFP-Growth). Qua việc thực nghiệm đã cho thấy QFP-Growth
và cải tiến QFP-growth là những thuật toán mang lại hiệu quả
tốt so với các thuật toán trước đó.
Huớng nghiên cứu tiếp theo
Trên cơ sở những nghiên cứu đã được trình bày trong
luận văn, tiếp tục nghiên cứu sâu hơn các thuật toán khai phá
luật kết hợp song song , tìm cách cải tiến nhằm khắc phục các
nhược điểm của các thuật toán song song hiện có và các thuật
toán khai phá dữ liệu song song khác để áp dụng vào một số bài
toán khai phá dữ liệu phù hợp cho giai đoạn hiện nay như: quy
luật thị truờng, chứng khoán và bất động sản, dự đoán rủi ro tín
dụng, định huớng kinh doanh, y tế….

1
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

NGUYỄN THỊ LIÊN
KHAI PHÁ TẬP PHỔ BIẾN SỬ DỤNG THUẬT TOÁN

trữ vì hy vọng những dữ liệu này sẽ cung cấp cho họ những
thông tin quý giá một cách nhanh chóng để đưa ra những quyết
định kịp thời vào một lúc nào đó. Chính vì vậy, các phương
pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng
không đáp ứng được thực tế đã làm phát triển một khuynh
hướng kỹ thuật mới đó là Kỹ thuật phát hiện tri thức và khai
khai phá dữ liệu (KDP)
Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã và
đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác
nhau trên thế giới như thiên văn học, phân lớp văn bản, tóm tắt
văn bản tin sinh học, thương mại điện tử, quản lý quan hệ
khách hàng, viễn thông, thể thao, giải trí, đầu tư Tại Việt
Nam kỹ thuật này còn tương đối mới mẻ tuy nhiên cũng đang
23

KẾT LUẬN VÀ KIẾN NGHỊ
Luận văn đề cập đến các nội dung về phát hiện tri thức,
khai phá dữ liệu. Ứng dụng của khai phá dữ liệu là rất rộng và
có ích trong các hoạt động sản xuất, kinh doanh và trợ giúp cho
việc hoạch định chiến lược của các nhà quản lý cũng như hỗ trợ
ra quyết định. Tuy vậy vẫn còn rất nhiều những khó khăn,
thách thức trong việc ứng dụng và nghiên cứu các kỹ thuật khai
phá dữ liệu.
Về mặt lý thuyết, khai phá dữ liệu là một công đoạn
trong tiến trình lớn, tiến trình khám phá tri thức từ CSDL.
Phương pháp khai phá dữ liệu có thể là: phương pháp sử dụng
cây quyết định và luật, phương pháp phát hiện luật kết hợp, các
phương pháp dựa trên mẫu, các phương pháp phân lớp và hồi
quy phi tuyến tính…, Các phương pháp trên có thể áp dụng trên
dữ liệu thông thuờng và trên tập mờ.

Với thời gian và kiến thức còn hạn chế, luận văn này
không tránh khỏi những thiếu sót, rất mong được sự quan tâm
định hướng của các thày cô giáo, sự góp ý của của các bạn
đồng nghiệp để báo cáo hoàn thiện hơn.
CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
4
Chương này trình bày khái niệm khai phá dữ liệu, quá
trình khai phá dữ liệu và tóm tắt các phuong pháp khai phá dữ
liệu phổ biến. Trong các phương pháp khai phá dữ liệu, khai
phá các luật kết hợp là một trong những lĩnh vực đang đuợc
quan tâm và nghiên cứu mạnh mẽ.
1.1.Khái niệm và quá trình khai phá dữ liệu
1.1.1.Khái niệm
Khai phá dữ liệu là một tập hợp các kỹ thuật đuợc sử dụng
để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ
liệu trong một tập hợp dữ liệu khổng lồ và phức tạp, đồng thời
cung tìm ra các mẫu tiềm ẩn trong tập dữ liệu đó. Về bản chất
nó là giai đoạn duy nhất rút trích và tìm ra đuợ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.
1.1.2. Quá trình khai phá dữ liệu
Khai phá dữ liệu là một bước của quá trình phát hiện tri
thức (KDP). Quá trình phát hiện tri thức trải qua 5 giai đoạn
khác nhau mà khai thác dữ liệu chỉ là một giai đoạn phát hiện
tri thức. Sau đây là 5 giai đoạn của phát hiện tri thức
21
4.2. Chương trình minh hoạ
4.2.1 Dữ liệu thử nghiệm
f, a
, c, d, g, i, m, p 5
 Thu thập và tiền xử lý dữ liệu
 Xác định vấn đề:
 Khai thác dữ liệu
 Minh hoạ và đánh giá
 Đưa kết quả vào thực tế
1.2.Một số phương pháp khai phá dữ liệu
 Luật kết hợp
 Khai phá chuỗi theo thời gian
 Phân lớp và dự đoán
 Phân cụm / phân đoạn
 Hồi quy
 Mô tả khái niệm và tổng hợp hóa

CHƯƠNG 2: LUẬT KẾT HỢP
Trong chương 2 trình bày tổng quan về luật kết hợp, các
định nghĩa, tính chất liên quan đến luật kết hợp: độ hỗ trợ, độ
tin cậy, tập mục phổ biến, phát biểu bài toán khai phá luật kết
hợp.
Khai phá luật kết hợp trong CSDL có thể chia thành hai
bài toán con: (1) Tìm tất cả các tập mục phổ biến từ CSDL. (2)
Sinh ra các luật từ các tập mục phổ biến. Trong chương này
trình bày một số thuật toán cơ bản phát hiện tập mục phổ biến,
phát hiện luật kết hợp từ các tập mục phổ biến nhằm làm tiền
đề cho các nghiên cứu sau này như cải tiến thuật toán, thuật
toán song song.

và tổng số giao tác trong D (hay là phần trăm của các giao tác
trong D có chứa tập mục X), kí hiệu Supp(X). Ta có 0  suppp(X)  1 với mọi tập X.
Để dễ hình dung ta có thể coi Support chỉ mức độ “phổ
biến xảy ra” của mẫu.


|D|
|T X :D T|
(X) Supp



(2.1)
19
Tạo mẫu β = ai ;
β . support = ai .support;
F = F  β ;
Tạo cây gốc Temp-root với các con là con của ai
;
Call QFP-growth(Temp-root, ai );
}
18
temp_root>=ξ ) then call QFP-
growth(temp_root, β);
}
3.4 Mở rộng của thuật toán QFP-growth
Như vậy, thay vì tuần tự xét từng đối tượng ai của cây


1.
Nhận xét: Độ hỗ trợ và độ tin cậy chính là xác suất sau:
Supp(X Y) = P(X  Y).
Conf (XY) =P(Y/X) =Supp(X  Y)/Supp(X).
2.1.2. Khai phá luật kết hợp
Bài toán khai phá luật kết hợp trên một cơ sở dữ liệu được
chia thành hai bài toán nhỏ. Bài toán thứ nhất là tìm tất cả
các tập mục dữ liệu có độ hỗ trợ thỏa ngưỡng tối thiểu cho
trước, gọi là tập các tập mục dữ liệu thuờng xuyên. Bài toán
thứ hai là tìm ra những luật kết hợp từ những tập mục dữ
liệu thường xuyên thỏa độ tin cậy tối thiểu cho trước.
Bài toán 1: Tìm tất cả các tập mục phổ biến (các tập có
support lớn hơn hoặc bằng ngưỡng minsup)
Dữ liệu vào: Cho trước các tập mục I, cơ sở dữ liệu D,
các ngưỡng minsup và minconf.
Dữ liệu ra: Tìm tất cả các luật kết hợp X Y trên D
thoả mãn:
8
Support (XY)  minsup và confidence (X Y) 
minconf.
Bài toán 2: Khai phá luật kết hợp
Dữ liệu vào: I, D, minsup, minconf, L
k
={x
1
, x
2,…,
x
k

(Khai phá các mẫu phổ biến với cây FP-tree bằng các
mẫu riêng lẻ).
Input: Cây FP-tree và ngưỡng hỗ trợ tối thiểu ξ.
Output: Một tập đầy đủ các mẫu phổ biến F
Method: call QFP-growth(root, null).
Procedure QFP-growth(gốc Q, FP_prefix α)
for each ai trong cây Q, từ trên xuống dưới
1. ai .support = Tổng số lần xuất hiện của ai có
trong cây gốc Q ;
2. if ai .support > = ξ then
{ Tạo mẫu β = α  ai ;
β . support = ai .support;
F = F  β ;
Tạo cây có gốc tạm thời (temp_root) có
các con là con của ai;
if (temp_root có con) and (Tổng số lần
xuất hiện các con của
16
- Gồm các giao tác chứa p.
- Để tìm các mẫu phổ biến chứa p ta chỉ cần tìm các
mẫu phổ biến trong CPB và thêm p vào các mẫu đó.
* FP-Tree có điều kiện của p là cây FP-tree được xây
dựng với cơ sở có điều kiện của mẫu p.
Input: FP-tree, ngưỡng hỗ trợ tối thiểu ξ.
Output: Một tập đầy đủ các mẫu phổ biến F.
Phương pháp: gọi FP-growth (FP-tree, null).
Procedure FP-growth (Tree, α)
If (Cây chỉ có 1 nhánh đơn P) then
For each tổ hợp β của các nút trong P
{

2.2.2.1 Thuật toán sinh luật đơn giản
Nếu

a

 và luật a ( - a) có độ tin cậy nhỏ hơn minconf
thì ta không cần phải xem xét các luật có tiền đề là a’,

a’

a.
Chẳng hạn, nếu ABC D Có độ tin cậy nhỏ hơn minconf thì
ta không cần kiểm tra luật AB  CD vì AB

ABC nên
sup(AB)

sup (ABC) và do đó
)sup(
)sup(
)sup(
)sup(
AB
ABCD
ABC
ABCD
 <
minconf
2.2.2.2 Thuật toán sinh luật nhanh
Như đã đề cập ở trên với mỗi tập mục phổ biến , nếu luật a 

, do đó lu ật ( – c’)
c’ cũng thỏa minconf.
CHƯƠNG 3: THUẬT TOÁN QFP-GROWTH
Thuật toán kinh điển Apriori tìm tập mục phổ biến thực
hiện tốt bởi rútt gọn kích thước các tập ứng cử nhờ kỹ thuật tỉa.
Tuy nhiên, trong tình huống mà số các mẫu nhiều, mẫu dài
hoặc độ hỗ trợ cực tiểu thấp, các thuật toán Apriori gặp phải 2
chi phí lớn:
Chi phí cho số lượng khổng lồ các tập ứng cử. Ví dụ:
nếu cứ 10
4
tập 1-mục phổ biến thì thuật toán Apriori sẽ cần sinh
ra hơn 10
7
các ứng cử 2-mục và thực hiện kiểm tra sự xuất hiện
của chúng. Hơn nữa, để khám phá được một số mẫu phổ biến
kích thước (độ dài) là l, thuật toán phải kiểm tra (2
l
-2 ) các mẫu
phổ biến tiềm năng. Vớ dụ l=100, chẳng hạn là {a
1
,a
2
, ,a
100
},
nó phải sinh ra tổng số 2
100
 10
30

* Cơ sở có điều kiện của mẫu p (CPB) thoả mãn:
14
(kết hợp các cây con FP-tree thành 1 cây kết quả, không
tạo bảng chính và node liên kết trong cây kết quả FP-tree )
Input: Hai cây con FP-tree
Output: một cây FP-tree được trộn có tên FP-tree
<result>
Method: call FP-merge(FP-tree1, FP-tree2, result)
Procedure FP-merge(FP-tree1, FP-tree2, result)
1. While FP-tree2 !=NULL do
{ Lấy 1 dãy đối tượng từ lá đến gốc trong
FP-tree2.
n = leaf’s count ;
Coi dãy các đối tượng là [p|P].
Call merge-insert ([p|P], FP-tree1, n).
Xoá dãy đối tượng khỏi FP-tree2;
}
2. Rename FP-tree1 as FP-tree<result>;
(dãy [p|P], trong đó p là đối tượng cuối cùng và P là dãy các đối
tượng ở phía trước)
3.1.3.Thuật toán Merge-Insert
Thuật toán Merge-insert (chèn một dãy dữ liệu vào FP-tree)
Input: dãy dữ liệu, FP-tree node, count của đối tượng
cuối cùng trong dãy.
11
các CSDL thưa (sparse), với các CSDL dày (dense) thì thuật
toán thực hiện kém hiệu quả hơn.
Thuật toán tìm các tập phổ biến hiệu qủa hơn thuật toán
Apriori là thuật toán Fp-tree và Fp-Growth
3.1. Thuật toán song song xây dựng FP-Tree

1. If (T có nút con N) and (N.item-name = p) Then
N.count = N.count + 1;
Else
{ Tạo nút mới N;
N.item-name = p;
N.count = 1 ;
T.child = N ;
N.node-link = H[p].Node_link;
H[p].Node_link = N;
}
13
2. If P
≠
 then Call insert_tree (P, N). :1
3.1.1.2 Thuật toán song song xây dựng FP-Tree
Input: CSDL giao tác DB và ngưỡng min-sup ξ
Output: Cây FP-Tree
Method: Cây FP-tree được xây dựng theo các bước sau đây:
1. Giả sử có n bộ xử lý (BXL) p1, p2,…,pn; Phân chia
DB thành n phần DB1, DB2, …, DBn với kích thước giống
nhau
2. for ( j = 1; j ≤ n; j++) do ( đồng thời)
{ BXL pj quét CDSL DBj,
Xây dựng cây FP-treej, không tạo bảng
chính và node liên kết
}
3. while(n>1) do
for ( j = 1; j≤n; j=j+2) (đồng thời)
{ BXL pj gọi FP-merge( FP-treej, FP-
treej+1, int(j/2)+1 ) n = n / 2;