GVHD:
PGS.TS Lê Hoài Bắc
Học viên:
Vũ Hoàng Hải Sơn - 1211061
1
Nội Dung
1.
Giới Thiệu
2.
Mô tả thuật toán
3.
Đánh giá và kết quả của thuật toán
2
Giới thiệu

Có rất nhiều thuật toán được đề xuất tìm kiếm các luật
kết hợp (association rules) trong trường dữ liệu như:

Apriori

TreeProjection

FP-growth

Mining of generalized and multi-level rules

Mining of quantitative rules

…
3
Giới thiệu

Mô tả dữ liệu
2.
Giải thuật
6
Mô tả dữ liệu

Dữ liệu thời gian sẽ được phân vùng theo các mốc thời
gian như theo tháng, quý, năm

Các ký hiệu được sử dụng:

Db
s,e
:1 phần của dữ liệu bắt đầu từ P
s
đến P
e

Y
s,e
: đối tượng có P
s
là phân vùng bắt đầu và P
e
là kết
thúc
 MCP (Y): là thời gian thể hiện tối đa của đối tượng Y
7
Mô tả dữ liệu


2
db
)
11
C
2
Start Count
P1+P2
BC 1 4
CE 2 2
DE 2 2
p3
AD 3 1
BC 3 1
BD 3 1
BE 3 1
BF 3 3
CE 3 1
CF 3 1
DF 3 1
EF 3 1
Thuật toán ITARM

B2
:

Cập nhật support của
các UCV X trong C
2
DB

CE 2 3 8 x 30% = 3
CF 3 1 4 x 30% = 2
DE 2 2 8 x 30% = 3
DF 3 1 4 x 30% = 2
EF 3 1 4 x 30% = 2
Thuật toán ITARM

B3: Lọc các UCV có supp > min_supp
 Trong thuật toán này, supp được tính bằng số các trường
trong database có chứ X và min_supp được tính theo
công thức:

Các UCV được lọc lại là BC, BF, CE
13
Thuật toán ITARM

B4:
 Tìm các UCV gồm có k+1 đối tượng từ tập UCV thứ k
bằng phép kết Apriori (bắt đầu bằng k=2)

Cập nhật vào tập các UCV C
DB+db
 Dừng quá trình tìm kiếm khi tập C
k
DB+db
= Ø
14
Thuật toán ITARM

B5:

SI’s B
1,3
8 12 x 30% = 4
C
1,3
6 12 x 30% = 4
B
3,3
3 4 x 30% = 2
F
3,3
3 4 x 30% = 2
C
2,3
4 8 x 30% = 3
E
2,3
4 8 x 30% = 3
TI’s BC
1,3
5 12 x 30% = 4
BF
3,3
3 4 x 30% = 2
CE
2,3
3 8 x 30% = 3
Frequent itemsets
L1 B
1,3

2
DB
, nếu tồn tại X trong n
transaction T thuộc P
n
:
X.support
DB
= X.support
DB
- n

VD:

Trong trường hợp P3 không nằm trong tháng 3 mà là phần
thêm của tháng 2, tức là P2 = P2 + P3, và P2 được xem là db
17
C
2
DB
count
BC 4
CE 2
DE 2
C
2
DB
count
BC 2
Đánh giá và kết quả thuật toán