Tìm tất cả các episodes tuần tự (3/3):
Trong giai đoạn nhận dạng, chúng ta tìm tất cả
episodes phổ biến và tạo các episodes ứng viên có
kích thước 3. Lần nữa, hầu như tất cả các ứng viên
đều phổ biến.
Cuối cùng, thủ tục tương tựđược lặp cho các ứng
viên có kích thước là 4 và tìm được các episodes
xảy ra là DCAB trong 10-40, DABC trong 50-80,
CABD trong 20-50, CBDA trong 20-60, và BDAC
trong 40-80
Không tìm thấy các ứng viên có kích thước 5, do vậy
thuật toán kết thúc.
10 trang |
Chia sẻ: thienmai908 | Lượt xem: 1208 | Lượt tải: 0
Nội dung tài liệu Episodes và luật Episode, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Episodes và luật Episode
Chương 3
Bài tập4
Khái niệm cơ bản1
Thuật toán Winepi2
Thuật toán Minepi3
Nội dung
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 Episode 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”
Chương 3 Episodes và luật Episode
CÁC KHÁI NiỆM CƠ BẢN
Dữ liệu:
Dữ liệu là tập R các biến cố
Mỗi biến cố là một cặp (A, t), với
• A R là loại biến cố (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 biến cố
Các chuỗi biến cố 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
Chương 3 Episodes và luật Episode
CÁC KHÁI NiỆM CƠ BẢN
Ví dụ chuỗi dữ liệu tín hiệu báo động:
• Với:
– 10…150 là các thời điểm xảy ra sự kiện
– s = (D, 10), (C, 20), …, (A, 150)
– A, B, C và D là các loại sự kiện (ở đây là tín hiệu báo động)
– Ts (thời điểm bắt đầu) = 10 and Te (thời điểm kết thúc) = 150
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150
D C A B D A B C A D C A B D A
Chương 3 Episodes và luật Episode
CÁC KHÁI NiỆM CƠ BẢN
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 tín hiệu báo động, episode = (V, )
xảy ra trong phạm vi S nếu có cách thỏa loại sự kiện
(ví dụ loại tín hiệu báo động) trong V dùng các tín hiệu
báo động của S để thứ tự riêng phần được tôn trọng
Nhận xét: episodes chứa các tín hiệu báo động có
các tính chất nào đó và xảy ra theo một thứ tự riêng
phần nào đó.
Chương 3 Episodes và luật Episode
CÁC KHÁI NiỆM CƠ BẢN
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ự")
Chương 3 Episodes và luật Episode
CÁC KHÁI NiỆM CƠ BẢN
Ví dụ:
A B
Episode
tuần tự
A
B
Episode
song song
A
B
C
Episode vừa tuần tự
vừa song song
Chương 3 Episodes và luật Episode
CÁC KHÁI NiỆM CƠ BẢN
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
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
Ví dụ chuỗi dữ liệu tín hiệu báo động:
0 10 20 30 40 50 60 70 80 90
D C A B D A B C
• 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
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
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
Ts Te
t1 t2 t3 … … tn
event1 event2 event3 … … eventn
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
Cửa sổ trên chuỗi sự kiện S là chuỗi sự kiện S=(w,ts,te),
với ts 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
Ts Te
t1 t2 t3 tn
event1 event2 event3 … … eventn
Wts te
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
Theo định nghĩa, cửa sổ đầu và cuối trên chuỗi 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
Wts te
Ts Te
t1 t2 t3 tn
event1 event2 event3 … … eventn
Wts te
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
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ớiW(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
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
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
Meo 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
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
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
B
:
A
B
C:
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
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 WINEPI episode
Độ 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ổ đó.
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
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 (tín hiệu báo động) 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.
phần thân kết luận [bề rộng cửa sổ ] (f, c)
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
Input: Tập R các loại sự kiện/tín hiệu báo động , chuỗi sự kiện
s trên R, tập E 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)
Method:
1. Tính C1 := { E | || = 1};
2. i := 1;
3. while Ci do
4.(* Tính F(s, win, min_fr) := { Ci | fr(, s, win) min_fr};
5. i := l+1;
6.(** Tính Ci:= { E | || = I, and F||(s, win, min_fr) for
all E, };
(* = quét database , (** tạo ứng viên
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
Bài toán đầu tiên: cho chuỗi và episode, xác định
episode có xuất hiện trong chuỗi.
Tìm số các cửa sổ có episode xuất hiện
Các cửa sổ liền nhau có nhiều phần chung
Cách xử lý?
Thuật toán tăng cường (incremental algorithm)
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ự
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
Ví dụ chuỗi dữ liệu tín hiệu báo động:
• 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 giây (10-80)
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
0 10 20 30 40 50 60 70 80 90
D C A B D A B C
Bằng cách trượt cửa sổ, chúng ta có 11 cửa sổ (U1-U11):
• Nguỡng tần số được ấn định là 40%, ví dụ episode xảy ra
tối thiểu trong 5 của 11 cửa sổ.
U1
U2
U11
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
0 10 20 30 40 50 60 70 80 90
D C A B D A B C
WINEPI Approach
Chương 3 Episodes và luật Episode
Giả sử cần tìm tất cả các episodes song song:
Đầu tiên, tạo singletons, ví dụ episodes song song có
kích thuớc là 1 (A, B, C, D)
Tiếp đến nhận dạng các singletons phổ biến (ở đây
là tất cả )
Từ các episodes phổ biến này, tạo các episodes ứng
viên có kích thước là 2: AB, AC, AD, BC, BD, CD
Tiếp đến nhận dạng các episodes song song phổ
biến(ở đây là tất cả)
Từ các episodes phổ biến này, tạo các episodes phổ
biến có kích thước là 3: ABC, ABD, ACD, BCD
Khi nhận dạng các episodes phổ biến, chỉ có ABD
xuất hiện trong hơn 4 cửa sổ
Không có episodes ứng viên có kích thước là 4.
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
Tần suất Episode và các luật ví dụ với WINEPI:
D : 73%
C : 73%
A : 64%
B : 64% D A [40] (55%, 75%)
D C : 45%
D A : 55%
D B : 45% D A B [40] (45%, 82%)
C A : 45%
C B : 45%
A B : 45%
D A B : 45%
Chương 3 Episodes và luật Episode
THUẬT TOÁN WINEPI
Một cách tiếp cận khác để khám phá episodes
Không dùng cửa sổ trượt
Đối với từng episode quan tâm tiền năng, tìm số lần
xuất hiện chính xác của episode.
Các tiện lợi: dễ sửa đổi các giới hạn thời gian, nhiều
giới hạn thời gian cho một luật :
“Nếu A và B xảy ra trong phạm vi 15 giây, thì C sẽ
theo sau trong phạm vi 30 giây"
Bất tiện: dùng nhiều khoảng trống
Chương 3 Episodes và luật Episode
THUẬT TOÁN MINEPI
Cho episode và chuỗi sự kiện S, khoảng [ts,te]
là xuất hiện nhỏ nhất của S,
Nếu xảy ra trong cửa sổ ứng với khoảng
Nếu không xảy ra trong bất kỳ khoảng con đúng
nào
Tập các xuất hiện nhỏ nhất của episode trong
một chuỗi sự kiện cho trước được ký hiệu là
mo():
mo() = { [ts,te] | [ts,te] là sự xuất hiện nhỏ
nhất của }
Chương 3 Episodes và luật Episode
THUẬT TOÁN MINEPI
Ví dụ: Episode song song chứa các loại sự kiện A và
B có ba lần xuất hiện nhỏ nhất trong s là : {[30,40],
[40,60], [60,70]}, có một lần xuất hiện trong s là :
{[60,80]}
D C A B D A B C
0 10 20 30 40 50 60 70 80 90
A
B
A
B
C: :
Chương 3 Episodes và luật Episode
THUẬT TOÁN MINEPI
Luật Episode MINEPI cho xác suất điều kiện để tổ
hợp các sự kiện ( tín hiệu báo động) xảy ra trong một
thời khoảng khi cho trước tổ hợp khác các sự kiện
khác đã xuất hiện trong thời khoảng
Luật episode là [win1] [win2]
và là các episodes sao cho ( là episode
con của )
Nếu episode có xuất hiện nhỏ nhất trong khoảng
[ts,te] với te - ts win1, thì episode xảy ra trong
khoảng [ts,t'e] ứng với vài t'e sao cho t'e - ts win2
Chương 3 Episodes và luật Episode
THUẬT TOÁN MINEPI
Độ tin cậy của luật [win1] [win2] là xác suất điều
kiện để xảy ra khi cho trước xảy ra, dưới các ràng
buộc thời gian được chỉ định bởi các luật:
|mo()| / |mo()|
với |mo()| là số các xuất hiện nhỏ nhất [ts,te] của sao
cho te - ts win1 và |mo()| là số các xuất hiện như thế
và cũng có một xuất hiện của trong phạm vi khoảng
[ts,ts+win2]
Chương 3 Episodes và luật Episode
THUẬT TOÁN MINEPI
Tần suất của luật [win1] [win2] là |mo()|, với
số lần luật thỏa trong CSDL
Xét ví dụ:
Bài toán: tìm tất cả các episodes tuần tự bằng
cách dùng thời khoảng cực đại là 40 giây và kích
thuớc cửa sổ là 10, 20, 30 and 40 giây Ngưỡng
tần suất được gán cho một lần xuất hiện.
D C A B D A B C
0 10 20 30 40 50 60 70 80 90
Chương 3 Episodes và luật Episode
THUẬT TOÁN MINEPI
Tìm tất cả các episodes tuần tự (1/3):
Đầu tiên, tạo singletons, ví dụ episodes có kích thước
là 1 (A, B, C, D)
Trong khi tạo singletons, chúng ta cũng tạo bảng xuất
hiện cho chúng. Sau lần quét CSDL đầu tiên, chúng
ta không cần quét CSDL nữa mà dùng các bảng đảo
ngược được tạo lập.
Sau đó, nhận dạng các singletons phổ biến(với ví dụ
này là tất cả)
Từ các episodes phổ biến này, tạo các episodes ứng
viên có kích thước là 2: AB, BA, AC, CA, AD, DA,
BC, CB, BD, DB, CD, DC
Chương 3 Episodes và luật Episode
THUẬT TOÁN MINEPI
Tìm tất cả các episodes tuần tự(2/3):
Sau đó, dùng bảng đảo ngược để tạo xuất hiện nhỏ
nhất cho các ứng viên ví dụ cho AB nhận tất cả các
episodes con, có tên là A và B, rồi tính mo(AB) như
sau:
• Đọc xuất hiện đầu tiên của A (30-30), và tìm xuất hiện đầu
tiên theo sau B (40-40)
• Sau đó lấy xuất hiện thứ hai của A (60-60) và tìm xuất hiện
đầu tiên sau B (70-70)
• Rồi tiếp tục với BA
Chương 3 Episodes và luật Episode
THUẬT TOÁN MINEPI
Tìm tất cả các episodes tuần tự (3/3):
Trong giai đoạn nhận dạng, chúng ta tìm tất cả
episodes phổ biến và tạo các episodes ứng viên có
kích thước 3. Lần nữa, hầu như tất cả các ứng viên
đều phổ biến.
Cuối cùng, thủ tục tương tự được lặp cho các ứng
viên có kích thước là 4 và tìm được các episodes
xảy ra là DCAB trong 10-40, DABC trong 50-80,
CABD trong 20-50, CBDA trong 20-60, và BDAC
trong 40-80
Không tìm thấy các ứng viên có kích thước 5, do vậy
thuật toán kết thúc.
Chương 3 Episodes và luật Episode
THUẬT TOÁN MINEPI Các xuất hiện (tuần tự ) tối thiểu
+ các tần suất trong dữ liệu ví dụ
Chương 3 Episodes và luật Episode
IF D
THEN C
WITH [0] [10] 0.00 (0/2)
[0] [20] 0.50 (1/2)
[0] [40] 1.00 (2/2)
IF D
THEN A
C
WITH [0] [10] 0.00 (0/2)
[0] [40] 0.50 (1/2)
IF D
A
THEN C
WITH [40] [40] 0.50 (1/2)
[20] [40] 1.00 (1/1)
IF D
C
THEN A
B
WITH [40] [40] 0.50 (1/2)
[30] [40] 1.00 (1/1)
Chương 3 Episodes và luật Episode
THUẬT TOÁN MINEPI
IF D
A
B
THEN C
WITH [40] [40] 0.50 (1/2)
[30] [40] 1.00 (1/1)
• Dưới đây là xuất hiện tối thiểu
của các luật trong dữ liệu ví dụ:
D C A B D A B C
0 10 20 30 40 50 60 70 80 90
DC
DAB, DCAB
DC, DAC, DABC
DA DA
DAB
Chương 3 Episodes và luật Episode
THUẬT TOÁN MINEPI
Khai phá luật Episode:
Dựa trên kỹ thuật luật kết hợp
Dữ liệu hướng thời gian
Hai cách tiếp cận:
WINEPI với cửa sổ trượt
MINEPI với việc tìm sự xuất hiện nhỏ nhất
Các tiếp cận được dùng cho các mục tiêu khác nhau
Cần nghiên cứu thêm
Bài toán khám phá mẫu tuần tự (sequential pattern mining )
Thuật toán tăng cường cho bài toán sequential pattern
mining
Chương 3 Episodes và luật Episode
KẾT LuẬN
1. Cho chuỗi sự kiện sau đây:
A B R A K A D A B R A
Có bao nhiêu cửa sổ có bề rộng là 4 được xử lý để
tìm các episodes phổ biến theo tiếp cận WINEPI ?
Giả sử nguỡng min_fr là 0.3. Tìm các episode phổ
biến tuần tự và song song trong chuỗi trên ?
Tìm các epsiode tối đại ?
Chương 3 Episodes và luật Episode
BÀI TẬP
1. Cho chuỗi sự kiện sau đây:
A B R A K A D A B R A
Có bao nhiêu cửa sổ có bề rộng là 4 được xử lý để
tìm các episodes phổ biến theo tiếp cận WINEPI ?
Giả sử nguỡng min_fr là 0.3. Tìm các episode phổ
biến tuần tự và song song trong chuỗi trên ?
Tìm các epsiode tối đại ?
Chương 3 Episodes and luật Episode
BÀI TẬP
Các file đính kèm theo tài liệu này:
- udafyuawkhoahockithuatmaytinh (32).pdf