» Luận Văn - Báo Cáo

» Công nghệ thông tin

Tiểu luận: 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

Chia sẻ: Sdgvfcxg Sdgvfcxg | Ngày: | Loại File: PDF | Số trang:20

0

Báo xấu

63
lượt xem 7
download

Tiểu luận: 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

Mô tả tài liệu

Download Vui lòng tải xuống để xem tài liệu đầy đủ

ITARM - Incremental Temporal Association Rules Mining 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. Cùng tìm hiểu thuật toán này qua bài tiểu luận 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tiểu luận: 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

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  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(XY)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 C2 Start Count  Input: DB, db, C2DB , min_sup P1+P2  Output: L’, C2DB+db BC 1 4 CE 2 2  B1: tìm tất cả các ứng cử DE 2 2 viên(UCV) trong db (C2db) 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 11
Thuật toán ITARM  B2 : C2 Start Count RS  Cập nhật support của AD 3 1 4 x 30% = 2 các UCV X trong C2DB: BC 1 5 12 x 30% = 4 x.suppDB+db = x.suppDB + x.suppdb DB 3 1 4 x 30% = 2 BE 3 1 4 x 30% = 2  Cập nhật X vào C2DB+db BF 3 3 4 x 30% = 2  Cập nhật các UCV còn CE 2 3 8 x 30% = 3 lại trong C2DB và C2db CF 3 1 4 x 30% = 2 vào C2DB+db DE 2 2 8 x 30% = 3 DF 3 1 4 x 30% = 2 EF 3 1 4 x 30% = 2 12
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 CDB+db  Dừng quá trình tìm kiếm khi tập CkDB+db = Ø 14
Thuật toán ITARM  B5:  Tìm các tập thời gian(TI) từ tập UCV CDB+db  Tìm các tập thời gian con(SI) từ tập TI TI’s SI’s BC1,3 B1,3 C1,3 BF 3,3 B3,3 F3,3 CE2,3 C2,3 E2,3 15
Thuật toán ITARM  B6:  Tính toán lại support count và lọc lại các UCV Candidate itemset Count Relative support Frequent itemsets SI’s B1,3 8 12 x 30% = 4 L1 B1,3 C1,3 6 12 x 30% = 4 C1,3 B3,3 3 4 x 30% = 2 B3,3 F3,3 3 4 x 30% = 2 F3,3 C2,3 4 8 x 30% = 3 C2,3 E2,3 4 8 x 30% = 3 E2,3 TI’s BC 1,3 5 12 x 30% = 4 L2 BC1,3 BF 3,3 3 4 x 30% = 2 BF 3,3 CE2,3 3 8 x 30% = 3 CE2,3 16
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ằ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 C2DB count BC 4 C2DB count CE 2 BC 2 DE 2 17
Đá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ền máy Win 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 trong DB  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 trong DB ban đầu (tính theo hàng nghìn)  dr: r là số các transaction trong DB 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 theo hà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Ó THỂ BẠN MUỐN DOWNLOAD

LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Tài Chính Ngân Hàng

172 tài liệu

758 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.