HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA CÔNG NGHỆ THÔNG TIN 1
  
Tiểu luận
Chuyên đề công nghệ phần mềm
“Khai phá dữ liệu với Association Rule”

Giáo viên : GS.TS Trần Đình Quế
Sinh viên: Bùi Minh Hoài

HÀ NỘI, 4/2011
Association Rule
Mục lục
Chương 1: Giới thiệu đề tài 4
1.Đặt vấn đề 4
2.Mục đích 4
3.Nội dung tiểu luận 5
Chương 2: Association Rule 6
I.Một số khái niệm về data mining 6
1.Khai phá dữ liệu (data mining) 6
2.Các tác vụ khai phá dữ liệu (data mining tasks/functions) 7
II.Association Rule 8
1.Association Rule 8
3. Một số độ đo 10
4.Tiến trình 11
2)FP-growth algorithm 11
FP-growth (frequent pattern growth) sử dụng một mở rộng cấu trúc prefix-tree để lưu
trữ dữ liệu ở dạng nén. FP-growth chấp nhận hướng tiếp cận divide-and-conquer để
phân tích công việc khai phá và cở sở dữ liệu. Nó sử dụng phương thức khung mẫu
tăng dần để tránh tốn kém trong tiến trình đưa ra các ứng cử và kiểm thử được sử

1.Giới thiệu thuật toán 12
3.Thuật tóan 13
4.Ví dụ 15
5.Nhận xét về thuật toán Apriori 19
Tài liệu tham khảo 20
Bùi Minh Hoài_D07CNPM1 Page 3
Association Rule
Chương 1: Giới thiệu đề tài
1. Đặt vấn đề
Trong vài thập kỉ gần đây, cùng với sự phát triển của xã hội, khoa học kĩ thuật, sự
phát triển của công nghệ thông tin, việc sinh và lưu trữ dữ liệu cũng có nhiều kĩ
thuật tiến bộ. Tuy nhiên lượng dữ liệu ngày càng nhiều nên việc lưu trữ trở nên khó
khăn hơn và đòi hỏi phương pháp lưu trữ với hiệu quả tốt nhất.Thay vì việc phải lưu
trữ một lượng nhiều dữ liệu bao gồm cả dữ liệu có thể không cần thiết, người ta
thực hiện quá trình biến đổi dữ liệu thành thông tin có ích hay còn gọi là quá trình
khai phá dữ liệu(data mining) để biến dữ liệu thành thông tin hay tri thức phục vụ
cho các ứng dụng và loại bỏ được bớt các dữ liệu không cần thiết. Tùy theo loại dữ
liệu, loại tri thức muốn thu được từ dữ liệu mà ta sử dụng các phương pháp khai phá
phù hợp.
Bên cạnh đó khai phá dữ liệu còn giúp quá trình tìm thông kiếm thông tin tốt hơn
với người dùng hay việc chăm sóc khách hàng, bán hàng tốt hơn đối với các doanh
nghiệp. Chúng ta rất quen thuộc với việc tìm kiếm trên google, chúng ta đã thử đặt
câu hỏi tại sao google có thể tìm kiếm một cách nhanh và thông minh đến vậy và dữ
liệu vô cùng phong phú trên tất cả các mặt các lĩnh vực của đời sống xã hội?
Hay việc mua bán sách trực tuyến trên trang nổi tiếng amazon.com, bạn để ý rằng
mỗi khi bạn xem thông tin chi tiết về một quyển sách nào đó trên site thì bao giờ
cũng kèm theo 1 danh sách các quyển sách gợi ý mua kèm theo quyển bạn đang
xem, một thống kê cho thấy có tới trên 70% đầu sách được người dùng mua thêm
thông qua hình thức gợi ý này. Vậy điều gì làm cho việc bán sách hiệu quả đến như
vậy?

khai khá dữ liệu, các loại tri thức có thể đạt được sau quá trình khai phá.
Phần hai em sẽ đi sâu vào trình bày về Association rule, về các định nghĩa cũng như
các độ đo được sử dụng trong luật kết hợp. Một số thuật toán sẽ được giới thiệu và
trình bày thuật tóan cơ bản của association rule là Apriori Algorithm.
Association rule được ứng dụng chủ yếu trong lĩnh vực thương mại điện tử vì vậy
các ví dụ tương ứng trong bài tiểu luận em liên quan đến các dữ liệu của một siêu
thị, các ứng dụng của siêu thị đối với association rule để lấy các thông tin cần thiết
từ dữ liệu được lưu trữ để thực hiện các chiến lược của họ.
Bùi Minh Hoài_D07CNPM1 Page 5
Association Rule
Chương 2: Association Rule
I. Một số khái niệm về data mining
1. Khai phá dữ liệu (data mining)
Khám phá tri thức (knowledge discovery) là tiến trình khai phá tri thức từ dữ
liệu bao gồm chuỗi các bước thực hiện một các tuần tự: làm sạch và tích hợp dữ
liệu(data cleaning & integration), lựa chọn và biến đổi dữ liệu(data selection &
transformation), khai phá dữ liệu(data mining), đánh giá mẫu và biểu diễn tri
thức(evaluation & presentation).
Data mining là một bước trong tiến trình khám phá tri thức tuy nhiên……Vì vậy có
nhiều thuật ngữ khác nhau dung tương đương với data mining như: knowledge
discovery/mining in data/databases (KDD), knowledge extraction, data/pattern
analysis, data archeology, data dredging, information harvesting, business
intelligence
Vậy có thể hiểu một cách cụ thể hơn: Data mining là một quá trình trích xuất thông
tin có mối quan hệ hoặc có mối tương quan nhất định từ một kho dữ liệu lớn nhắm
mục đích dự đoán các xu thế, các hành vi trong tương lai hoặc tìm kiếm những tập
thông tin hữu ích mà bình thường không nhận diện được.
Lượng lớn dữ liệu có sẵn để khai phá?
 Là bất kì loại dữ liệu được lưu trữ hay lưu trữ tạm thời, có cấu trúc hay các
bản ghi có cấu trúc hay phi cấu trúc đều có thể là dữ liệ để khai phá.

được quan tâm. Bao gồm: tên kho dữ liệu/ cơ sở dữ liệu, các bảng dữ liệu
hay các khối dữ liệu, các điều kiện chọn dữ liệu, các tiêu chí gom nhóm dữ
liệu.
 Loại tri thức sẽ đạt được (kind of knowledge): loại tri thức đạt được sẽ tương
ứng với tác vụ khai phá dữ liệu sẽ thực thi. Một số loại tri thức đạt được như:
mô hình phân lớp, mô hình dự đóan, mô hình gom cụm, mô hình phân tích
phần tử biên, mô hình phân tích tiến hóa…
 Tri thức nền (background knowledge)
 Các độ đo (interestingness measures): các độ đo được đưa ra bởi người dung
thường đi kèm với các ngưỡng giá trị, giúp cho quá trình khai phá hoặc đánh
giá các mẫu được tìm thấy. Các độ đo được đưa ra tương ứng với các loại tri
thức đạt được và do đó tương ứng với các tác vụ khai phá dữ liệu được thực
thi. Các độ đo thường được đưa ra để kiểm tra tính đơn giản, tính chắc chắn,
tính hữu dụng của tri thức đạt được.
Bùi Minh Hoài_D07CNPM1 Page 7
Association Rule
 Các kỹ thuật biểu diễn tri thức/trực quan hóa mẫu (pattern visualization and
knowledge presentation): thể hiện các tri thức tìm thấy đến người dung, ví dụ
như: luật, bảng, báo cáo, biểu đồ, đồ thị, cây, khối.
Với mỗi tác vụ khai phá dữ liệu từ dữ liệu đầu vào để có tri thức đầu ra đều cần có
những giải thuật riêng. Mỗi giải thuật khai phá dữ liệu phải có bốn thành phần cơ
bản sau:
 Cấu trúc mẫu hay cấu trúc mô hình (model or pattern structure):
 Hàm tỉ số (score function): Hàm tỉ số là hàm xác định một cấu trúc mô
hình/mẫu đáp ứng tập dữ liệu đã cho tốt ở mức độ nào đó. Hàm tỉ số cho biết
liệu một mô hình có tốt hơn các mô hình khác hay không. Một vài hàm tỉ số
thông dụng: likelihood, sum of squared errors, misclassification rate…
 Phương pháp tìm kiếm và tối ưu hóa (optimization and search method):
phương pháp này nhằm xác định cấu trúc và giá trị các thông số đáp ứng tốt
nhất hàm tỉ số từ dữ liệu sẵn có

1
, i
2
,… ,i
n
} là một tập n phần tử gọi là item
T={ t
1
, t
2
,… ,t
n
} là tập các giao dịch gọi là database (transaction)
Mỗi giao dịch trên T có một mã giao dịch(ID) duy nhất và chứa một tập con các
item trên I được gọi là itemset.
Một rule được định nghĩa như một phép kéo theo có dạng X →Y mà ở đó X, Y ⊆ I
và X ∩ Y =∅. X, Y là tập các item trong itemset và X được gọi là antecedent (tiền
tố), Y được gọi là consequent (hậu tố) của mỗi rule tương ứng.
Để hiểu rõ hơn về các khái niệm đã được đưa ra chúng ta xét một ví dụ nhỏ cho
miền thương mại điện tử.
Ta có một tập các item I={milk, break, butter, beer} và một cơ sở dữ liệu nhỏ chứa
các item (1_các item có xuất hiện trong giao dịch, 0_item không xuất hiện trong
giao dịch) được biểu diễn như sau :
Transaction
ID
milk bread Butter Beer
1 1 1 0 0
2 0 0 1 0
3 0 0 0 1
4 1 1 1 0

lift của một rule X  Y là tỉ lệ quan sát được X và Y không phụ thuộc vào nhau
được tính như sau:
Bùi Minh Hoài_D07CNPM1 Page 10
Association Rule
conviction: là tỉ số
4. Tiến trình
Association rule thường được yêu cầu để thỏa mãn một giá trị minimum support và
minimum confidence được đưa ra bởi người dùng tại cùng một thời điểm.
Association rule được chia làm hai bước:
1) Bước 1: Sử dụng minimum support để tìm ra tất cả frequent itemset trong cơ
sở dữ liệu.
2) Bước 2: Từ frequent itemset đã tìm được ở bước 1 và ràng buộc về giá trị
minimum confidence đưa ra các định dạng rule.
5. Một số thuật tóan
Một số thuật tóan được sử dụng để tìm tập các Frequent itemset và đưa ra
Association rule từ tập dữ liệu ban đầu
1) Apriori algorithm
Là thuật tóan tốt nhất được biết để khai phá association rule. Nó sử dụng tìm kiếm
theo chiều rộng đểtính tóan các support trên tập itemset và sử dụng chức năng đưa
ra các ứng cử viên với tính chất apriori hay downward closure
2) FP-growth algorithm
FP-growth (frequent pattern growth) sử dụng một mở rộng cấu trúc prefix-
tree để lưu trữ dữ liệu ở dạng nén. FP-growth chấp nhận hướng tiếp cận
divide-and-conquer để phân tích công việc khai phá và cở sở dữ liệu. Nó
sử dụng phương thức khung mẫu tăng dần để tránh tốn kém trong tiến
trình đưa ra các ứng cử và kiểm thử được sử dụng trong Apriori.
3) GUHA procedure ASSOC
GUHA là một phương thức chung cho phân tích tìm kiếm dữ liệu dựa trên lý
thuyết của phép tính quan sát (observational calculi). Các thủ tục ASSOC là
một phương pháp GUHA, có ý nghĩa cho việc đưa ra các association rule

frequent itemset và association rule từ tập các item. Thuật tóan gồm hai bước:
a) Đưa ra các tập frequent itemset
b) Đưa ra các association rule
Input:
• Thông tin các giao dịch được lưu trong CSDL: mã giao dịch và các item
trong mỗi giao dịch
• Giá trị minsup
• Giá trị minconf
Bùi Minh Hoài_D07CNPM1 Page 12
Association Rule
Output:
• Các tập frequent itemset (bước 1)
• Các rule (bước 2)
3. Thuật tóan
a. Đưa ra Frequent Itemset
Ý tưởng: Thuật tóan tìm ra các tập Frequent Itemset dựa trên tích chất apriori hay
downward closure: nếu một tập itemset thỏa mãn giá trị minsup thì mọi tập con
không rỗng của nó cũng thỏa mãn minsup. Tích chất này đơn giản và dễ hiểu, ta có
thể thấy được rằng nếu một giao dịch chứa một tập các item X thì nó phải chứa bất
kì tập con không rỗng nào của X. Tích chất này cùng với giá trị minsup đã giúp loại
bỏ một số lượng lớn các itemset không phải là frequent.
Tìm kiếm các tập Frequent Itemset dựa theo thuật tóan tìm kiếm thông minh và giả
sử các item trong tập I được lưu trữ theo thứ tự bảng chữ cái.
Thuật tóan:
Thuật toán sinh tất cả các frequent itemset bằng cách quét qua dữ liệu nhiều lần.
Trong lần quét đầu tiên nó tính support của các tập chỉ gồm 1 item và xác định xem
item nào là frequent. Ta được F
1
là tập các frequent 1-itemset. Để xác định tập
frequent itemset k item (level 3) thực hiện 3 bước:

Bùi Minh Hoài_D07CNPM1 Page 13
Association Rule
Mã giả:
Algorithm Apriori(T)
1. C
1
← init-pass(T) //the first over T
2. F
1
← {f | f Є C
1
, f.count/n >= minsup }//n là số transaction trong T
3. For(k=2; F
k-1
≠ ᴓ; k++) do // subsequent pass over T
4. C
k
← candicate-gen(F
k-1
);
5. For each transaction t Є T do // scan the data once
6. For each candicate c Є C
k
do
7. If c is contained in t then
8. C.count++;
9. Endfor
10. Endfor
11. Return F← ;
Function candicate-gen(F

1
, i
2, …,
i
k-2
, i
‘
k-1
} // f
1
, f
2
khác nhau mỗi phần tử cuối cùng
5.
And i
k-1
< i
‘
k-1
do // theo thứ tự từ điển
6.
c ← {i
1
, i
2, …,
i
k-2
, i
k-1
, i

;
b. Đưa ra các Association Rule
Kết thúc bước 1 ta thu được các tập frequent itemset ở các level khác nhau, đến
bước 2 thực hiện việc đưa ra các rule thỏa giá trị minconf trên tập các frequent
itemset đã thu được. Việc có tiếp tục thực hiện bước 2 hay không là tùy thuộc vào
từng trườg hợp ứng dụng cụ thể, trong một số trường hợp chúng ta chỉ cần tìm ra
tập các frequent itemset cũng đã thỏa mãn yêu cầu của ứng dụng.
Bùi Minh Hoài_D07CNPM1 Page 14
Association Rule
Ý tưởng:
Xét tích chất: một rule (f-α)->α có giá trị thì (f-α
sub
)-> α
sub
cũng phải có giá trị, với
α
sub
là

một tập con không rỗng của α bởi vì support count của (f- α
sub
) luôn nhỏ hơn
hoặc bằng support count của (f- α).
Thuật toán:
Từ tập frequent itemset f:
• Đưa ra tất cả các rule mà hậu tố là 1 item
• Sử dụng các hậu tố của các rule đã xác định được và hàm candicate-gen(ở
bước 1) để đưa ra tất cả các hậu tố có 2 item có thể xuất hiện trên rule. Cứ
tiếp tục như vậy cho đến khi hậu tố là có k-1 item
Mã giả:

1. if (k> m+1) AND (H
m
≠∅
) then
2. H
m+1

←
candidate-gen(H
m
);
3. For each h
m+1
in H
m+1
do
4. Conf
←
f
k
.count / (f
k
– h
m+1
.count);
5. If (conf ≥ minconf) then
6. Output the rule (f
k
– h
m+1

Bước 1: Đưa ra các frequent itemset min_sup=40%
C1: F1:
Beer 4/5
Diaper 4/5
Baby Powder 2/5
Bread 1/5
Umbrella 1/5
Milk 2/5
Detergent 1/5
Coca Cola 1/5
C2: F2:
Bùi Minh Hoài_D07CNPM1 Page 16
Beer 4/5
Diaper 4/5
Baby Powder 2/5
Milk 2/5
Beer, Diaper 3/5
Beer, Bady Powder 1/5
Beer, Milk 2/5
Diaper, Bady Powder 2/5
Diaper, Milk 1/5
Bady Powder, Milk 0
Beer, Diaper 3/5
Beer, Milk 2/5
Diaper, Bady Powder 2/5
{Beer, Diaper, Baby powder}
{Beer, Diaper, Milk}
{Beer, Baby powder, Milk}
{Diaper, Baby powder, Milk}
Association Rule

Association Rule
5. Nhận xét về thuật toán Apriori
Trong ứng dụng thực tế, việc tìm tất cả các tập frequent itemset trong cơ sở dữ liệu
là vấn đề không đơn giản bởi vì:
 Số giao dịch trong cơ sỏ dữ liệu có thể rất lớn và có thể không phù hợp với
bộ nhớ của máy tính.
 Thuật toán dựa trên level-wise search. Nó có khả năng linh động là có thể
dừng tại bất cứ level nào. Điều này rất hữu ích trong thực tế vì trong nhiều
ứng dụng, các frequent itemsets hoặc rules dài là ko cần thiết vì khó sử dụng.
 Một khi minsup và minconf của tập các transactions T được cho trước, tập
các frequent itemsets có thể tìm được trong T là duy nhất. Bất kỳ thuật toán
nào cũng tìm được cùng một tập frequent itemset. Tính chất này ko đúng đối
với association rule minning trên những datamining task khác nhau
(classification hoặc clustering), với mỗi thuật toán khác nhau có thể sinh ra
các association rule rất khác nhau.
 Vấn đề chính với association rule mining là nó thường đưa ra một số lượng
lớn các itemsets và rules 10, 1000 hoặc nhiều hơn, gây khó khăn cho user
phân tích để tìm được những cái hữu ích.
Bùi Minh Hoài_D07CNPM1 Page 19
Association Rule
Tài liệu tham khảo
[1]
[2] Jiawei Han and Micheline Kamber, Data Mining:Concepts and Techniques
[3] Rakesh Agrawal and Ramakrishnan Srikant, Fast Algorithms for Mining
Association Rules.
[4] />[5]
Bùi Minh Hoài_D07CNPM1 Page 20