Để sử dụng cách tiếp cận này trong việc khai thác mô hình phổ biến trên cơ sở dữ liệu giao tác, trước hết chúng ta sẽ xem xét một số định nghĩa và sau đó sẽ trình bày phương pháp theo chiều ngang.
3.2.2. Định nghĩa 1:
Tập dữ liệu theo thứ tự là một cơ sở dữ liệu giao tác mà các hạng mục của cơ sở dữ liệu giao tác được sắp xếp theo thứ tự tăng dần độ phổ biến, nếu trùng độ phổ biến thì xếp theo thứ tự từ điển.
Ví dụ 3.3: Ta xét lại bảng 3.1. Tập dữ liệu D là tập dữ liệu cắt tỉa với minsup=2, sắp xếp các hạng mục thứ tự tăng dần theo độ phổ biến, nếu trùng độ phổ biến thì xếp theo thứ tự từ điển.
3.2.3. Định nghĩa 2:
Loại bỏ hạng mục X trong cơ sở dữ liệu giao tác D: cho mỗi hạng mục X trong cơ sở dữ liệu giao tác D các hạng mục đã sắp xếp theo thứ tự, ta sẽ loại bỏ tất cả các mục trước X, mục X và tất cả các hàng không chứa X, ký hiệu X-cond D.
Ví dụ 3.4:
b, a, c |
a, c |
d, b |
a, c |
b, a |
a, c |
b, c |
d, b, a, c |
Có thể bạn quan tâm!
-
Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến - 5 -
Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến - 6 -
Phương Pháp Tìm Kiếm Theo Chiều Rộng Và Theo Chiều Sâu -
Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến - 9 -
Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến - 10
Xem toàn bộ 84 trang tài liệu này.
d-cond D |
b |
b, a, c |
b-cond D |
a, c |
a |
c |
a, c |
a-cond D |
c |
c |
c |
c |
c |
c-cond D |
NULL |
Hình 3.4 Loại bỏ mục d, b, a, c của tập dữ liệu D
3.2.4. Định nghĩa 3:
Loại bỏ Y|X trong cơ sở dữ liệu giao tác Y-cond D: chúng ta có thể định nghĩa loại bỏ Y|X tương tự như định nghĩa 2 như sau: loại bỏ tất cả các mục trước X, mục X và tất cả các hàng không chứa X trong cơ sở dữ liệu giao tác Y-cond D, ký hiệu Y|X-cond.
b-cond D |
a, c |
a |
c |
a, c |
Ví dụ 3.5:
b|a-cond |
c |
c |
b|c-cond |
NULL |
Hình 3.5 Loại bỏ b|a, b|c của tập dữ liệu cắt tỉa b-cond
Như vậy, mỗi hạng mục phổ biến có thể được trích xuất từ tập dữ liệu loại bỏ X, chứa mục X. Bằng chứng, dựa vào định nghĩa 2, ta thấy tất cả các hàng không chứa X được loại bỏ khỏi tập dữ liệu loại bỏ X. Vì vậy, đối với mỗi hàng của tập dữ liệu loại bỏ X, X có xuất hiện trong hàng. Do đó, nếu tần số của tập Y bằng hoặc lớn hơn minsup, cho tất cả chúng, mục X có mặt và X Y là một mẫu phổ biến.
Kết quả là chúng ta có thể trích xuất tất cả các mẫu phổ biến có chứa X và không chứa các mục trước X trong tập dữ liệu thứ tự từ loại bỏ X. Vì chúng ta đã chia mô hình trích xuất của cơ sở dữ liệu sang một số lớp khác nhau dựa trên các mục chứa hoặc thiếu, chúng ta có thể sử dụng kết quả này để trích xuất tập hợp tất cả các mẫu phổ biến của tập dữ liệu tương ứng.
Ví dụ 3.6: Hình 3.4 thể hiện mức đầu tiên của phương pháp khai thác theo chiều ngang trên cơ sở dữ liệu giao tác của bảng 3.1. Hình 3.5 cho thấy dữ liệu đã loại bỏ b, loại bỏ a, và c đã loại bỏ. Vậy ta thấy rằng mỗi mẫu được trích xuất phổ biến từ tập dữ liệu loại bỏ X đã chứa mục X.
3.3. Biểu diễn tập dữ liệu trên ma trận bit
Ý tưởng chính của phương pháp khai thác ngang dựa trên phương pháp chia để trị, cắt tỉa và loại bỏ hạng mục để khai thác tập hợp tất cả các hạng mục phổ biến
của một tập dữ liệu, đầu tiên chúng ta xây dựng ma trận bit được cắt tỉa cột theo thứ tự của tập dữ liệu. Đối với mỗi hạng mục có trong ma trận bit này, chẳng hạn như X, ta có thể xây dựng ma trận X-cond DB của ma trận bit chính.
Ví dụ 3.7: Ta xét lại ví dụ 3.1 bảng 3.1. Cho một tập dữ liệu giao tác I có m dòng, mỗi dòng gọi là một giao tác. Trên mỗi giao tác chứa tập các phần tử, mỗi phần tử tương ứng với một hạng mục dữ liệu, một tập các mục dữ liệu được gọi là tập hạng mục. Ta xây dựng một ma trận bit dựa trên tập dữ liệu I như sau:
Một dòng của ma trận bit ương ứng với một dòng của I.
Mỗi cột trên ma trận bit tương ứng với một hạng mục trên I (hạng mục được sắp xếp thứ tự tăng dần theo độ phổ biến, nếu trùng độ phổ biến thì xếp theo thứ tự từ điển).
Gọi aij là giá trị của ô tại dòng thứ i cột thứ j của ma trận bit (1 i m, 1 j n). aij = 1 nếu giao dịch thứ i có chứa item trùng với item trên cột thứ j của ma trận bit, ngược lại aij = 0. Như vậy, từ tập dữ liệu ban đầu ta sẽ tạo ra được một ma trận bit tương ứng.
f | g | h | i | j | k | l | m | n | p | q | r | d | b | a | c | |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
Bảng 3.2 Ma trận bit tập dữ liệu giao tác I
Từ ma trận bit bảng 3.2, với minsup = 2, ta sẽ loại bỏ đi các cột tương ứng với các hạng mục e, f, g, h, i, j, k, l, m, n, p, q, r vì độ phổ biến của các hạng mục này không thỏa minsup, kết quả ta thu được một ma trận bit D như bảng 3.3
b | a | c | |
0 | 1 | 1 | 1 |
0 | 0 | 1 | 1 |
1 | 1 | 0 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 1 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
d
Bảng 3.3 Ma trận bit D sau khi lược bỏ các cột không thỏa minsup = 2
Loại bỏ hạng mục d trong ma trận bit D, với minsup = 2, loại bỏ đi cột tương ứng với các hạng mục d và các dòng không chứa d trong ma trận bit bảng 3.3 và thu được ma trận bit d-cond D như bảng 3.4.
a | c | |
1 | 0 | 0 |
1 | 1 | 1 |
Bảng 3.4 Ma trận bit d-cond D sau khi lược bỏ cột d với minsup = 2
Tính độ phổ biến hạng mục như sau: vì mỗi bộ xử lý của mảng lưu trữ vector bit đại diện cho một phần tử nên cần chuyển bộ dữ liệu sang chiều dọc bởi ma trận chuyển đổi bit tương ứng được trình bày trong bảng 3.5
b | 1 | 1 | 2 |
a | 0 | 1 | 1 |
c | 0 | 1 | 1 |
Độ phổ biến của mục b
Bảng 3.5 Ma trận bit chuyển đổi từ tập phần tử tương ứng với bảng 3.4
Cắt tỉa ma trận bit d-cond D, với minsup = 2, loại bỏ đi cột và dòng tương ứng với các hạng mục không thỏa với minsup=2 trong ma trận bit bảng 3.4 và thu được ma trận bit Tỉa d-cond bit như bảng 3.6.
1 |
1 |
Bảng 3.6 Ma trận bit Tỉa d-cond D
3.4. Thuật toán MRIH
Input:
M_D: bitVector array[0..m] of boolean // ma trận bit D m: integer //số dòng của ma trận M_D
n: integer //số cột của ma trận M_D
x: String //hạng mục phổ biến được trích từ M_D
Output:
S: String //tập hạng mục phổ biến
Procedure MRIH (M_D, x)
1. M_X: bitVector array[0..m] of boolean // ma trận bit X-cond D
2. i : integer
3. Output (file, x)
4. if (Support(Items(n-1)) >= minsup) then
5. Output (file, x+’n-1’)
6. for each item y of M_D from 0 to n-2 do
7. if (Support(y) >= minsup) then
8. for i= 0 to m-1 do
9. if (M_D[i] includes y) then
10. apend(row[i]) of M_D to M_X with
11. afer column item y to item n-1 (X-cond D)
12. for each item z of M_X do
13. if (Support(z) < minsup) then
14. Delete column and row z
15. of M_X (Tỉa X-cond D)
16. if (M_X!= NULL and Len(M_X)>=minsup) then
17. if (bitVector(M_X)==1)
18. Output (file, X+’y’+’Items(M_X)’)
19. else
20. MRIH(M_X, x+’y’)
21. Output (file, x+’y’)
22. return
Hình 3.6 Thuật toán MRIH
3.5. Minh họa thuật toán trên dữ liệu mẫu
Ví dụ 3.8: Sử dụng lại CSDL ví dụ 3.1 bảng 3.1
Bước 1: Tỉa CSDL giao tác với minsup =2, sắp xếp hạng mục thứ tự tăng dần theo độ phổ biến nếu trùng độ phổ biến thì sắp theo thứ tự từ điển ta được tập dữ liệu D. Bước 2: Xây dựng ma trận bit cho tập dữ liệu D như bảng 3.3
{ac} là tập phổ biến
{db} là tập phổ biến
{bac} là tập phổ biến
{bc} là tập phổ biến
{c} là tập phổ biến
d-cond D |
b |
b, a, c |
b-cond D |
a, c |
a |
c |
a, c |
a-cond D |
c |
c |
c |
c |
c |
c-cond D |
NULL |
Bước 3: Khai thác theo thuật toán như sau:
Tập dữ liệu D | |
b, a, c | |
a, c | |
d, b | |
a, c | |
b, a | |
a, c | |
b, c | |
d, b, a, c | |
b|a-cond |
c |
c |
b|c-cond |
NULL |
Tỉa d-cond D |
b |
b |
Tỉa b-cond D |
a, c |
a |
c |
a, c |
Hình 3.7 Khai thác tất cả hạng mục của tập dữ liệu D
3.6. Kết luận chương
Chương này đã trình bày biểu diễn tập dữ liệu trên ma trận bit, kỹ thuật xây dựng và khai thác dữ liệu dựa trên cấu trúc cây tìm kiếm, với kỹ thuật phân chia và cắt tỉa của thuật toán để khai thác theo chiều ngang trích xuất các tập phổ biến. Vấn đề đặt ra là cần thực nghiệm để kiểm tra tính hiệu quả của thuật toán, nội dung này được trình bày trong chương 4.
Chương 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ THUẬT TOÁN
Trong chương này, luận văn mô tả các cơ sở dữ liệu sẽ được sử dụng cho chương trình, ghi nhận kết quả, từ đó đưa ra nhận xét và hướng phát triển tiếp theo. Để đo tính hiệu quả của thuật toán MRIH, chương trình được thực hiện trên 2 CSDL: CSDL từ ví dụ mẫu (Dataset.txt) xuyên suốt trong chương 2 và chương 3 để kiểm chứng độ chính xác của chương trình.
Để có cơ sở đánh giá kết quả nghiên cứu và chứng minh tính hiệu quả của thuật toán, thuật toán được lập trình với ngôn ngữ Python 3.5. Máy tính chạy chương trình thử nghiệm là Window 10 với cấu hình CPU Intel Core i5 2.7GHz, 4 GB RAM và ổ cứng 1 TB:
Các CSDL thử nghiệm lấy từ http://fimi.ua.ac.be/data/
4.1. Mô tả dữ liệu
CSDL từ ví dụ mẫu (Dataset.txt) xuyên suốt trong chương 2 và chương 3 để kiểm chứng độ chính xác của chương trình.
Tên CSDL | Kích thước (size) | Số lượng giao tác (transaction) | Số lượng hạng mục (items) | |
1 | Dataset | 1 KB | 8 | 17 |
Bảng 4.1 Bảng mô tả CSDL mẫu (Dataset.txt)
CSDL được tải từ nguồn http://fimi.ua.ac.be/data/, với cấu trúc của CSDL được mô tả trong bảng 4.2
Tên CSDL | Kích thước (size) | Số lượng giao tác (transaction) | Độ dài trung bình giao tác (average transaction length) | Số lượng hạng mục (items) | |
1 | T10I4D100K (D1) | 3.93M | 100000 | 10 | 870 |
2 | T40I10D100K (D2) | 15.12M | 100000 | 39 | 942 |
3 | Mushroom | 0.56M | 8124 | 23 | 119 |
4 | Retail | 3.97M | 88162 | 10 | 16469 |
5 | Accident | 33.8M | 340183 | 34 | 468 |
Bảng 4.2 Bảng mô tả các CSDL