zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Khai phá dữ liệu - Chương 3: Dãy phổ biến

Chia sẻ: Lê Trinh Vàng | Ngày: | Loại File: PPT | Số trang:37

Báo xấu

97
lượt xem 18
download

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

Luật kết hợp mô tả các sự kiện xuất hiện cùng nhau trong dữ liệu Ví dụ: "IF khách hàng mua sản phẩm A với số lượng 10 THEN sẽ mua sản phẩm B với số lượng 20. Các luật dãy phổ biến mô tả quan hệ thời gian giữa các sự kiện Ví dụ: IF hôm nay khách hàng mua sản phẩm A THEN sau 1 tuần khách hàng sẽ mua tiếp sản phẩm B và C” Tập R các loại sự kiện. Mỗi sự kiện là một cặp (A, t), với A  R là loại sự kiện (ví dụ loại...

Chủ đề:

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

Lưu

Nội dung Text: Khai phá dữ liệu - Chương 3: Dãy phổ biến

Chương 3: Dãy phổ biến 1
Chương 3: Dãy phổ biến 1. CÁC KHÁI NiỆM CƠ BẢN Luật kết hợp mô tả các sự kiện xuất hiện cùng nhau trong dữ liệu – Ví dụ: "IF khách hàng mua sản phẩm A với số lượng 10 THEN sẽ mua sản phẩm B với số lượng 20. Các luật dãy phổ biến mô tả quan hệ thời gian giữa các sự kiện – Ví dụ: IF hôm nay khách hàng mua sản phẩm A THEN sau 1 tuần khách hàng sẽ mua tiếp sản phẩm B và C” 2
1. CÁC KHÁI NiỆM CƠ BẢN (tt) – Tập R các loại sự kiện. – Mỗi sự kiện là một cặp (A, t), với • A ∈ R là loại sự kiện (ví dụ loại tín hiệu báo động ) • t là một số nguyên xác định thời điểm xuất hiện của sự kiện – Chuỗi sự kiện S trên R là bộ ba (s, Ts, Te) • Ts là thời điểm bắt đầu và Te là thời điểm kết thúc • Ts < Te là các số nguyên • S = 〈 (A1, t1), (A2, t2), …, (An, tn) 〉 • Ai ∈ R và Ts ≤ ti < Te với mọi i=1, …, n` 3
1. CÁC KHÁI NIỆM CƠ BẢN (tt) Ví dụ chuỗi sự kiện: D C A B D A B C A D C A B D A 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 • Trong đó: – A, B, C, D: là các loại sự kiện – 10…150 là các thời điểm xảy ra sự kiện – S = 〈 (D, 10), (C, 20), …, (A, 150) 〉 – Ts (thời điểm bắt đầu) = 10 and Te (thời điểm kết thúc) = 150 4
2. DÃY PHỔ BiẾN TRONG MỘT CHUỖI (Episode) Episodes: – Episode là cặp (V, ≤ ) • V là tập hợp các loại sự kiện,ví dụ loại tín hiệu báo động ∀ ≤ là thứ tự riêng phần trên V – Cho chuỗi S các sự kiện, episode α = (V, ≤ ) xảy ra trong phạm vi S nếu các loại sự kiện trong V xuất hiện trong S theo thứ tự được xác định bằng quan hệ thứ tự. 5
2. DÃY PHỔ BiẾN TRONG MỘT CHUỖI (Episode) Các thứ tự riêng phần phổ dụng như: – Thứ tự toàn phần • Các vị từ của mỗi episode có thứ tự cố định • Các episodes như vậy được gọi là tuần tự (hay “có thứ tự") – Các thứ tự riêng phần hiển nhiên • Không xét trật tự của các vị từ • Các episodes này được gọi là song song (hay “không có thứ tự") 6
2. DÃY PHỔ BiẾN TRONG MỘT CHUỖI (Episode) Ví dụ: A B A A C B B Episode Episode Episode vừa tuần tự tuần tự song song vừa song song 7
3. THUẬT TOÁN WINEPI Tên của phương pháp WINEPI xuất phát từ kỹ thuật dùng cửa sổ truợt Nhận xét: – Cửa sổ được trượt qua chuỗi dữ liệu các sự kiện – Mỗi cửa sổ là một “khung ảnh" giống như một dòng của CSDL – Tập các “khung ảnh" tạo thành các dòng của CSDL 8
3. THUẬT TOÁN WINEPI (tt) Ví dụ chuỗi dữ liệu sự kiện: D C A B D A B C 0 10 20 30 40 50 60 70 80 90 • Bề rộng cửa sổ là 40 giây • Cửa sổ đầu/cuối chỉ chứa sự kiện đầu/cuối 9
3. THUẬT TOÁN WINEPI (tt) Cho tập E các loại sự kiện, chuỗi sự kiện S = (s,Ts,Te) là một chuỗi có thứ tự các sự kiện eventi sao cho eventi ≤ eventi+1 với mọi i=1, …, n-1, và Ts ≤ eventi < Te với mọi i=1, …, n event1 event2 event3 … … eventn Ts Te t1 t2 t3 … … tn 10
3. THUẬT TOÁN WINEPI (tt) Cửa sổ trên chuỗi sự kiện S là chuỗi sự kiện Sw=(w,ts,te), với ts < Te, te > Ts, và w chứa các cặp (event, t) của s mà ts ≤ t < te Giá trị ts ≤ t < te được gọi là bề rộng cửa sổ W event1 event2 event3 … … eventn Ts Te t1 t2 t3 ts W te t n 11
3. THUẬT TOÁN WINEPI (tt) Theo định nghĩa, cửa sổ đầu và cuối trên chuỗi có thể vuơn ra ngoài chuỗi, do vậy cửa sổ đầu tiên chỉ chứa thời điểm đầu và cửa sổ cuối cùng chỉ chứa thời điểm cuối event1 event2 event3 … … eventn Ts Te ts W te t1 t2 t3 tn ts W te 12
3. THUẬT TOÁN WINEPI (tt) Tần suất (độ hỗ trợ với luật kết hợp) của episode α là tỷ số giữa các cửa sổ có xuất hiện với tổng số các cửa sổ khả dĩ. |Sw ∈ W(S, W) | α xuất hiện trong Sw | fr(α, S, W) = |W(S, W)| Với W(S, W) là tập tất cả các cửa sổ Sw của chuỗi S sao cho bề rộng cửa sổ là W 13
3. THUẬT TOÁN WINEPI (tt) Khi tìm episodes cần sử dụng một ngưỡng tần suất min_fr Episode α là phổ biến nếu fr(α, s, win) ≥ min_fr Ví dụ, “nếu tần suất của α vượt quá ngưỡng tần suất nhỏ nhất trong phạm vi chuỗi dữ liệu s và với bề rộng cửa sổ win" F(s, win, min_fr): tập hợp các episodes phổ biến trong s ứng với win và min_fr Apriori: Nếu episode α là phổ biến trong chuỗi sự kiện s, thì tất cả các episodes con β  α là phổ biến 14
3. THUẬT TOÁN WINEPI (tt) Luật episode rule là biểu thức β ⇒ α, với β và α là các episodes sao cho β là episode con của α Episode β là episode con của α (β  α), nếu đồ thị biểu diễn β là đồ thị con của đồ thị biểu diễn α. A A β: γ: C B B 15
3. THUẬT TOÁN WINEPI (tt) Phân số fr(α, S, W) : tần suất của toàn bộ episode fr(β, S, W) : tần suất của episode vế trái là độ tin cậy của luật β ⇒ α Độ tin cậy được xem như xác suất điều kiện của toàn bộ của α xảy ra trong cửa sổ khi cho trước β xảy ra trong cửa sổ đó. 16
3. THUẬT TOÁN WINEPI (tt) Nhận xét: – Các luật WINEPI giống luật kết hợp nhưng có thêm yếu tố thời gian: Nếu sự kiện thỏa về trái của luật xuất hiện theo thứ tự bên phải trong phạm vi W đơn vị thời gian, thì cũng xuất hiện trong phần kết luận (vế phải ) xuất hiện trong vị trí được mô tả bởi quan hệ thứ tự ≤ , trong phạm vi W đơn vị thời gian. 17
3. THUẬT TOÁN WINEPI (tt) Input Tập R các loại sự kiện, chuỗi sự kiện S trên R, tập E Input: các episodes, bề rộng cửa sổ win, và nguỡng tần suất min_fr Output Tập hợp F(s, win, min_fr) Output: Method: Method 1.Tính C1 := {α ∈ E | |α| = 1}; 2. k := 1; 3.while Ck≠ ∅ do 4. Tính F(s, win, min_fr) = {α ∈ Ck | fr(α, s, win) ≥ min_fr}; //Quét CSDL 5. k := k+1; 6. Tính Ck= {α ∈ E | |α| = k, and β ∈ F|β|(s, win, min_fr) cho tất cả β ∈ E và β  α // tạo ứng viên 18 7. End While
3. THUẬT TOÁN WINEPI (tt) Bài toán: cho chuỗi sự kiện và episode, xác định episode có xuất hiện trong chuỗi sự kiện đó không. Tìm số các cửa sổ có chứa một lần xuất hiện của episode. Cách xử lý? – Giống ý tưởng luật kết hợp – Episode ứng viên là tổ hợp của hai episodes có kích thước nhỏ hơn – Các episodes song song, episodes tuần tự 19
3. THUẬT TOÁN WINEPI (tt) Ví dụ chuỗi dữ liệu sự kiện: D C A B D A B C 0 10 20 30 40 50 60 70 80 90 • Bề rộng cửa sổ là 40 giây, buớc di chuyển là 10 giây • Chiều dài của chuỗi là 70 (10-80) 20

CÓ THỂ BẠN MUỐN DOWNLOAD

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 © 2022-2032 TaiLieu.VN. All rights reserved.