Đề tài Thuật toán hiệu quả trong việc khai thác những luật kết hợp thời gian - ITARM
So sánh vớihaithuậttoánSPF vàTwain, tấtcảđềuchạy
trênnềnmáyWin Xp, code C#, 1.8 GHz Intel Core 2 Duo,
1GB ram
Tx: x làchiềudàitrungbìnhcủa1 transaction trongDB
Ly: y làchiềudàitrungbìnhlớnnhấtcóthểcócủa1 tậpphổ
biến
Dz: z làsốcáctransaction trongDB ban đầu(tínhtheohàng
nghìn)
dr: r làsốcáctransaction trongDB cậpnhật(tínhtheohàng
nghìn)
Nm: m làsốlượngitem (tínhtheohàngnghìn)
Ln: n làsốlượngtậpphổbiếncóthểcó(tínhtheohàng
nghìn)
Po: o làsốcácphânvùng
20 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 2299 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Đề tài Thuật toán hiệu quả trong việc khai thác những luật kết hợp thời gian - ITARM, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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. Đánhgiá 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
Dữ liệu thời gian tồn tại rộng rãi trong kinh tế, tài chính,
truyền thông, và các lĩnh vực khác như dự báo thời tiết
Temporal Association Rules(TAR) là sự thể hiện của các
luật kết hợp bằng việc kết hợp với thời gian.
Đặc trưng của dữ liệu thời gian là sự cập nhật liên tục do
đó các giải thuật được đề xuất để giải quyết các vấn đề
xử lý chỗi thời gian:
Progressive Partition Miner(PPM)
Segmented Progressive Filter (SPF)
Two end AssocIation miNer (Twain)
Incremental Temporal Association Rules Mining (ITARM)
4
Giới thiệu
• Incremental Temporal Association Rules Mining (ITARM)
Dựa trên nền của thuật toán Sliding-Window Filtering
Duy trì những tập tập phổ biến sau khi dữ liệu đã được cập
nhật
5
Mô tả thuật toán
1. 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:
Dbs,e :1 phần của dữ liệu bắt đầu từ Ps đến Pe
Ys,e : đối tượng có Ps là phân vùng bắt đầu và Pe 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
Các ký hiệu được sử dụng(tt):
Supp(xMCP(x)) là relative support của tập x
Conf(XY)MCP(XY) là độ tin cậy
8
Mô tả dữ liệu
MCP(DE) = (2,3) do MCP(D) = (1,3) và MCP(E) = (2,3)
Supp(DE) = 2/8 = 25%
Conf(DE) = 2/3 = 66,66%
min_sup=30% và min_conf = 75% 9
Giải thuật
10
Thuật toán ITARM
Input: DB, db, C2DB , min_sup
Output: L’, C2
DB+db
B1: tìm tất cả các ứng cử
viên(UCV) trong db (C2
db)
11
C2 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ậpnhật support của
cácUCV X trong C2DB:
x.suppDB+db = x.suppDB + x.suppdb
Cậpnhật X vàoC2DB+db
Cậpnhật các UCV còn
lại trong C2DB và C2db
vàoC2DB+db
12
C2 Start Count RS
AD 3 1 4 x 30% = 2
BC 1 5 12 x 30% = 4
DB 3 1 4 x 30% = 2
BE 3 1 4 x 30% = 2
BF 3 3 4 x 30% = 2
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ácUCV được lọc lại là BC, BF, CE
13
Thuật toán ITARM
B4:
Tìmcá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ậpnhật vào tập các UCV CDB+db
Dừng quá trình tìm kiếmkhi tập CkDB+db = Ø
14
Thuật toán ITARM
B5:
Tìmcác tập thời gian(TI) từ tập UCV CDB+db
Tìmcác tập thời gian con(SI) từ tập TI
15
TI’s SI’s
BC1,3 B1,3
C1,3
BF3,3 B3,3
F3,3
CE2,3 C2,3
E2,3
Thuật toán ITARM
B6:
Tính toán lại support count và lọc lại các UCV
16
Candidate itemset Count Relative support
SI’s B1,3 8 12 x 30% = 4
C1,3 6 12 x 30% = 4
B3,3 3 4 x 30% = 2
F3,3 3 4 x 30% = 2
C2,3 4 8 x 30% = 3
E2,3 4 8 x 30% = 3
TI’s BC1,3 5 12 x 30% = 4
BF3,3 3 4 x 30% = 2
CE2,3 3 8 x 30% = 3
Frequent itemsets
L1 B1,3
C1,3
B3,3
F3,3
C2,3
E2,3
L2 BC1,3
BF3,3
CE2,3
Thuật toán Update C2
Input: C2DB ,Pn ,min_sup
Output: C2DB
Với mỗi UCV X thuộc C2DB , nếu tồn tại X trong n
transaction T thuộc Pn:
X.supportDB = X.supportDB - n
VD:
Trong trường hợp P3 không nằmtrong tháng 3 mà là phần
thêmcủa tháng 2, tức là P2 = P2 + P3, và P2 được xem là db
17
C2DB count
BC 4
CE 2
DE 2
C2DB count
BC 2
Đánh giá và kết quả thuật toán
So sánh với hai thuật toán SPF và Twain, tất cả đều chạy
trên nềnmáyWin Xp, code C#, 1.8 GHz Intel Core 2 Duo,
1GB ram
Tx: x là chiều dài trung bình của 1 transaction trongDB
Ly: y là chiều dài trung bình lớn nhất có thể có của 1 tập phổ
biến
Dz: z là số các transaction trongDB ban đầu (tính theo hàng
nghìn)
dr: r là số các transaction trongDB cập nhật (tính theo hàng
nghìn)
Nm: m là số lượng item (tính theo hàng nghìn)
Ln: n là số lượng tập phổ biến có thể có (tính theohàng
nghìn)
Po: o là số các phân vùng
18
Đánh giá và kết quả thuật toán
19
CÁM ƠN THẦY VÀ CÁC BẠN
20
Các file đính kèm theo tài liệu này:
- incremental_temporal_association_rules_mining_itarm__1001.pdf