Luật kết hợp: Một số khái niệm

Luật kết hợp dữ liệu

1. Hệ quả của thuật toán Aproiori

1.1. Giải thuật AprioriTid là phần mở rộng theo hướng tiếp cận cơ bản của giải thuật Apriori. Thay vì dựa vào cơ sở dữ liệu thô, giải thuật AprioriTID biểu diễn bên trong các giao tác bởi các ứng viên hiện hành.

1.2. Mô phỏng thuật toán

1.2.1. Bước 1: Quét tất cả các giao dịch để tìm tất cả các Item có độ Support lớn hơn Min Support và đưa ra tập Large 1 Item vào F1

1.2.2. Bước 2: Đưa toàn bộ các TID của giao dịch cùng các Items vào C’1 dưới dạng < TID,{X1} >

1.2.3. Bước 3: Xây dựng các cặp 2-Items từ F1 đưa vào tập ứng viên C2. Quét tất cả các giao dịch trong C’1 để tìm tất cả các tập Large 2-Items từ C2 đưa vào C’2 dưới dạng <TID,{X2}>, đồng thời đưa các cặp Large 2-Item ứng viên vào F2

1.2.4. Bước 4: Phát sinh luật. Xây dựng các cặp k-Items từ Fk-1 đưa vào tập ứng viên Ck. Quét tất cả các giao dịch trong C’k-1 để tìm tất cả các tập Large k-Items từ Ck đưa vào C’k dưới dạng <TID,{Xk}>, đồng thời đưa các tập Large k-Item vào Fk. Lặp lại bước 4 cho đến khi hết ứng viên mới.

2. Sinh ra các luật kết hợp từ tập “thường xuyên cùng nhau”

2.1. Luật kết hợp: Một quan hệ có dạng X => Y trong đó X,Y ⸦ I là các tập mục (Itemsets) . X được gọi là tiền đề, Y là mệnh đề kết quả.

2.2. Luật kết hợp có 2 vấn đề : Tìm tất cả các tập mục thường xuyên xảy ra mà có độ hỗ trợ lớn hơn hoặc bằng Minsup. Tạo ra các luật mong muốn sử dụng các tập mục hơn mà có độ tin cây lớn hơn hoặc bằng Mincof

2.3. Làm thế nào để sinh ra các luật từ các tập mục thường xuyên một cách có hiệu quả? Xét tổng quát, độ tin cậy không có đặc tính không đơn điệu (anti-monotone) c(ABC → D) có thể > hoặc <c(AB → D) „ Nhưng, độ tin cậy của các luật được sinh ra từ cùng một tập mục thường xuyên thì lại có đặc tính không đơn điệu ‰ Ví dụ: Với L = {A,B,C,D}: c(ABC → D) ≥ c(AB → CD) ≥ c(A → BCD) ‰ Độ tin cậy có đặc tính không đơn điệu đối với số lượng các mục ở vế phải của luật.

3. Thuật toán Apriori

3.1. Giới thiệu: Apriori là thuật toán khả sinh được đề xuất bởi R. Agrawal và R. Srikant vào năm 1993

3.2. Tư tưởng chính : Tìm tất cả tập phổ biến (frequent itemsets) Từ tập phổ biến sinh ra các luật kết hợp mạnh

3.3. các bước

3.3.1. 1. Duyệt (Scan) toàn bộ transaction database để có được support S của 1-itemset So sánh S với min_sup, để có được 1-itemset (L1)

3.3.2. 2. Sử dụng Lk-1 nối (join) Lk-1 để sinh ra candidate k-itemset. Loại bỏ các itemsets không phải là tập phổ biến thu được k-itemset

3.3.3. 3. Scan transaction database để có được support của mỗi candidate k-itemset So sánh S với min_sup để thu được tập phổ biến k (Lk)

3.3.4. 4. Lặp lại từ bước 2 cho đến khi Candidate set (C) trống (không tìm thấy tập phổ biến)

3.3.5. 5. Với mỗi tập phổ biến I, sinh tất cả các tập con s không rỗng của I.

3.3.6. 6. Với mỗi tập con s không rỗng của I, sinh ra các luật s => (I-s) nếu độ tin cậy (Confidence) của nó > =min_conf

4. Những khái niệm cơ bản

4.1. Giới thiệu luật kết hợp

4.1.1. Được giới thiệu từ năm 1993, bài toán khai thác luật kết hợp nhận được rất nhiều sự quan tâm của nhiều nhà khoa học.

4.2. Các định nghĩa

4.2.1. Định nghĩa 1: Độ hỗ trợ của X, ký hiệu support(X), là tỷ lệ phần trăm của các giao dịch hỗ trợ X trên tổng các giao dịch trong D

4.2.2. Định nghĩa 2: Một luật kết hợp có dạng R: X => Y, trong đó X, Y là tập các mục, X, Y I và X ∩Y = ∅. X được gọi là tiên đề . Y được gọi là hệ quả của luật. Hai thông số quan trọng của luật kết hợp là độ hỗ trợ (support) và độ tin cậy (confidence).

4.2.3. Định nghĩa 4: Độ tin cậy (confidence) là tỷ lệ phần trăm giữa số lượng các giao dịch chứa cả X và Y với số giao dịch có chứa X. Đơn vị tính %.

4.2.4. Định nghĩa 3: Độ hỗ trợ (support) của luật kết hợp X => Y là tỷ lệ phần trăm giữa số lượng các giao dịch chứa cả X và Y với tổng số các giao dịch có trong cơ sở dữ liệu. Đơn vị tính %.

4.3. Các tính chất

4.3.1. Tính chất 1: (Không hợp luật kết hợp) Nếu có X => Z và Y => Z trong D thì không nhất thiết X ∪ Y => Z là đúng. Tương tự : X => Y và X => Z thì không nhất thiết X => Y ∪ Z là đúng.

4.3.2. Tính chất 2: (Không tách luật) Nếu X ∪ Y => Z thì X => Z và Y => Z chưa chắc xảy ra. Tuy nhiên đảo lại: X => Y ∪ Z thì X => Y và X => Z

https://www.mindmeister.com/985793032/lu-t-k-t-h-p-d-li-u