Phương Pháp Khai Thác Theo Chiều Ngang Để Trích Xuất Các Tập Phổ Biến

Mã các giao tác

- Tiếp sau đó người nghiên cứu sẽ tiến hành giai đoạn thứ hai: tập trung tìm hiểu và nghiên cứu thuật toán khai thác tập phổ biến đầy đủ theo chiều ngang, trong thuật toán có sử dụng ma trận bit để nén tập dữ liệu. Bên cạnh đó, sử dụng phương pháp phân chia và cắt tỉa nhằm lược bỏ các giao tác không thỏa độ phổ biến để rút ngắn thời gian khai thác các tập phổ biến cũng được áp dụng, cuối cùng là cài đặt thuật toán và đánh giá kết quả thực nghiệm.

Với mục tiêu này, phạm vi nghiên cứu của luận văn là các thuật toán về khai thác tập phổ biến, khai thác dữ liệu duyệt theo hạng mục từ dưới lên, kỹ thuật phân chia và cắt tỉa, sau đó là xây dựng chương trình thực nghiệm để đánh giá kết quả đạt được.

1.3. Phương pháp nghiên cứu

Nghiên cứu tổng quan về khai thác dữ liệu, khai thác tập phổ biến và tiến hành nghiên cứu các tài liệu có liên quan đến luận văn.

Tìm hiểu các thuật toán khai thác tập phổ biến để tìm các phương pháp khai thác trong cơ sở dữ liệu có số lượng lớn các giao tác.

Xây dựng chương trình thực nghiệm và kiểm chứng, đánh giá kết quả đạt được.

1.3.1. Phương pháp nghiên cứu tài liệu

- Nghiên cứu các tài liệu và bài báo liên quan là cơ sở lý luận của luận văn.

- Nghiên cứu các cách tiếp cận, các kỹ thuật, các phương pháp, hiện trạng đã được công bố của các tác giả trong và ngoài nước có liên quan đến lĩnh vực khai thác tập phổ biến nói riêng và lĩnh vực khai thác tập phổ biến trong khai thác dữ liệu nói chung.

- Nghiên cứu các xu thế và hướng phát triển tương lai liên quan đến luận văn.

- Nghiên cứu các tài liệu khác liên quan phục vụ cho việc nghiên cứu của luận văn.

1.3.2. Phương pháp thực nghiệm

- Tiến hành thực nghiệm trên các bộ dữ liệu thực tế và bộ dữ liệu chuẩn để so sánh kết quả với kết quả của các phương pháp đã công bố trong và ngoài nước có liên quan đến luận văn.

1.3.3. Phương pháp thống kê, phân tích dữ liệu

- Thống kê, tổng hợp các số liệu trong quá trình thực nghiệm để từ đó phân tích, đánh giá và đưa ra những kết luận hoặc điều chỉnh nội dung nghiên cứu.

1.4. Bố cục luận văn

Luận văn được trình bày trong năm chương và tài liệu tham khảo với cấu trúc như sau:

Chương 1: Tổng quan

Chương này trình bày tổng quan về lĩnh vực nghiên cứu.

Chương 2: Cơ sở lý thuyết

Trong chương này, luận văn sẽ trình bày một số khái niệm, định nghĩa và tính chất của tập phổ biến, tập phổ biến đóng một số tiếp cận trong khai thác tập phổ biến. Ngoài ra, trong chương cũng trình bảy các thuật toán làm cơ sở nghiên cứu cho chương tiếp theo.

Chương 3: Phương pháp khai thác theo chiều ngang để trích xuất các tập phổ biến

Trong chương này, luận văn sẽ trình bày các nghiên cứu về sử dụng cấu trúc vector bit trong khai thác dữ liệu, sử dụng phương pháp chia để trị và cắt tỉa trong khai thác ngang.

Chương 4: Kết quả thực nghiệm và đánh giá

Chương này sẽ trình bày kết quả thực nghiệm và một số nhận xét đánh giá về vấn đề đã được nghiên cứu.

Chương 5: Kết luận

Chương này sẽ trình bày kết quả thực nghiệm và một số nhận xét đánh giá về vấn đề đã được nghiên cứu.

1.5. Kết luận chương

Các dữ liệu có ích tồn tại trong các CSDL có ý nghĩa rất lớn trong nhiều ngành, lĩnh vực. Do đó việc phát hiện và trích xuất các dữ liệu tìm ẩn từ các tập dữ liệu lớn ngày càng trở nên cần thiết, đặc biệt trong gia đoạn hiện nay khi mà sự phát triền nhanh chóng của các ứng dụng công nghệ thông tin ở nhiều lĩnh vực trong đời sống xã hội. Trong chương này, luận văn trình bày tổng quan về lĩnh vực nghiên cứu khai thác dữ liệu. Trong khai thác dữ liệu, kỹ thuật khai tác tập phổ biến là một trong những lĩnh vực đang được quan tâm và nghiên cứu mạnh mẽ.

Chương 2. CƠ SỞ LÝ THUYẾT

2.1. Giới thiệu tổng quan

Bài toán xác định luật kết hợp lần đầu tiên được Agrawal. R [3] giới thiệu vào năm 1993. Khai phá luật kết hợp là một kỹ thuật được sử dụng trong khai phá dữ liệu nhằm tìm ra các phần tử thường xuyên xuất hiện lặp đi lặp lại (hay phổ biến) trong cơ sở dữ liệu, từ đó rút ra được các luật về ảnh hưởng của một tập phần tử dẫn đến sự xuất hiện của tập phần tử khác.

Các thuật toán khai phá luật kết hợp tìm kiếm các mối liên kết giữa các phần tử trong cơ sở dữ liệu. Những nghiên cứu về luật kết hợp gần đây tập trung xây dựng các thuật toán khai phá luật kết hợp mới, hiệu quả hoặc cải tiến hay phát triển các thuật toán hiệu quả hơn từ các thuật toán đã có.

Chúng ta xem xét một bài toán về khai phá luật kết hợp như sau: phân tích hóa đơn mua hàng của khách hàng khi đi siêu thị. Việc khai phá luật kết hợp trong bài toán này nhằm tìm ra các luật kết hợp giữa các mặt hàng mà khách hàng đã mua. Thí dụ một số luật kết hợp rút ra được sau khi phân tích hóa đơn khách hàng mua: 60% khách hàng mà mua “bánh mì” tại siêu thị thì đều mua “sữa” chúng ta thấy có sự kết hợp giữa “bánh mì” với “sữa”. Những luật kết hợp như vậy rất có ích trong việc giúp các nhà quản lý nắm bắt được thói quen mua hàng của khách hàng khi mua một (hoặc một số) mặt hàng này thì khách hàng có xu hướng mua thêm một số mặt hàng nào nữa. Từ đó đề ra những chiến lược quản lý hợp lý.

Như vậy, khai phá luật kết hợp có thể giải quyết được bài toán hết sức đời thường như: khách hàng vào siêu thị sẽ mua mặt hàng nào? Những mặt hàng nào mà khách hàng kết hợp cùng mua. Tất nhiên, khai phá luật kết hợp cũng có nhiều ý nghĩa trong các lĩnh vực khác như tài chính, y học, công nghệ… Nhiệm vụ chính của khai phá luật kết hợp là phát hiện ra các tập con cùng xuất hiện trong một khối lượng giao tác lớn của một cơ sở dữ liệu cho trước. Nói cách khác, thuật toán khai phá luật kết hợp cho phép tạo ra các luật mô tả các sự kiện xảy ra đồng thời (một cách thường xuyên) như thế nào. Bài toán tìm luật kết hợp là bài toán cơ bản trong khai thác dữ liệu gồm hai bước chính:

Bước 1: Tìm tất cả các tập phổ biến theo ngưỡng phổ biến cho trước,

Bước 2: Tìm ra luật kết hợp dựa vào tập phổ biến đã tìm thấy ở Bước 1.

Nội dung luận văn này cũng đi sâu vào nghiên cứu thuật toán để tìm các tập phổ biến hiệu quả hơn.

2.2. Các khái niệm và định nghĩa

2.2.1. Hạng mục

Cho I là một tập các thuộc tính nhị phân. Cho I = {I1, I2, …, Im}, mỗi Ik (1km) là một hạng mục.

2.2.2. Tập hạng mục

Một tập 𝑋 ⊆ 𝐼 là một tập các hạng mục.

2.2.3. Cơ sở dữ liệu giao tác

Một CSDL giao tác là một tập gồm nhiều hạng mục, mỗi hạng mục là một giao tác được định danh bởi một giá trị duy nhất là mã giao tác.

Mã giao tác	Nội dung giao tác
1	a, b, d, e
2	b, c, e
3	a, b, d, e
4	a, b, c, e
5	a, b, c, d, e
6	b, c, d

Có thể bạn quan tâm!

Xem toàn bộ 84 trang tài liệu này.

Một CSDL giao tác trên I là một tập các định danh giao tác T = {t1, t2,…,tn}, với ti (1in) là một định danh giao tác trên I chứa một tập các danh mục dữ liệu X ⊆ I. Ví dụ 2.1: Trong bài toán giỏ hàng, cơ sở dữ liệu giao tác là các lần mua hàng của mỗi khách hàng, cho biết trong một lần mua hàng, khách hàng mua những mặt hàng nào.

Bảng 2.1 Cơ sở dữ liệu mẫu

2.2.4. Độ phổ biến

Cho CSDL bao gồm: Tập các danh mục I, tập danh mục X I và tập các giao tác D Độ phổ biến của X trong D có ký hiệu là sup(X) và được định nghĩa là số giao tác mà X xuất hiện trong D.

Ví dụ 2.2: Sử dụng CSDL ví dụ 2.1 với số lượng 6 giao tác. Tập danh mục {a, b, c, d, e}

Với CSDL mẫu trong bảng 2.1, thì ta có:

Tập danh mục I = {a, b, c, d, e} và tập giao tác D gồm có 6 giao tác: {abde, bce, abde, abce, abcde, bcd}

Độ phổ biến của tập danh mục X1 = {a} là số giao tác trong D có chứa {a}, do đó sup(X1) = 4

Như vậy tương tự ta có: X2 = {a, d} => độ phổ biến của X2 là sup(X2) = 3

2.2.5. Tập phổ biến:

Tập X I được gọi là tập phổ biến nếu sup(X) minsup, với minsup là giá trị do người dùng chỉ định.

Ví dụ 2.3: Ta xét lại CSDL mẫu trong bảng 2.1, với minsup = 3 (50%) thì tập X2 =

{a, d} là tập phổ biến vì có sup(X2) = 3  minsup. Tương tự ta có với X3 = {a, b, d} thì sup(X3) = 3  minsup và X3 cũng là tập phổ biến. Ngược lại, với X4 = {b, c, d} thì sup(X4) = 2 < minsup, vì vậy X4 không phải là tập phổ biến.

2.2.6. Tập phổ biến đóng:

Cho I = {i1, i2, …, im} là tập các hạng mục. Cho T = {t1, t2, …, tn} là tập các mã giao tác. Kết nối Galois

Ta có t : 2I → 2T được định nghĩa như hàm sau:

t(X) = {t ∈ T | X ⊆ i(t)} (1)

Ta có i : 2T → 2I được định nghĩa như hàm sau:

i(Y ) = {i ∈ I | ∀t ∈ Y, t chứa x} (2)

Ánh xạ (1): t(X) lấy tất cả tid của giao tác có chứa tập hạng mục X. Ánh xạ (2): i(Y) lấy tất cả hạng mục tồn tại trong tất cả giao tác Y.

Toán tử đóng: 𝒄 = 𝒊 ∘ 𝒕

Tập hạng mục X là tập đóng nếu c(X) = X.

Tập phổ biến đóng: là tập hạng mục đóng thỏa ngưỡng minsup cho trước.

Ví dụ 2.4: Ta xét lại CSDL mẫu trong bảng 2.1 với minsup = 30%. Kiểm tra ae, bc có phải là tập phổ biến đóng?

Sử dụng toán tử đóng:

c(ae) = i(t(ae)) = i(1345) = abe

c(bc) = i(t(bc)) = i(2456) = bc

Vậy bc là tập phổ biến đóng, ae không là tập phổ biến đóng.

Tóm tắt định nghĩa: Tập phổ biến đóng là tập phổ biến mà không có tập nào bao nó có cùng độ phổ biến.

Với F là tập hợp gồm tất cả tập phổ biến.

F = {X | X ⊆ I và sup(X) ≥ minsup}

Gọi C là tập hợp gồm tất cả tập phổ biến đóng.

C = {X | X ∈ F và ∄𝑌 ⊃ 𝑋 mà 𝑠𝑢𝑝(𝑋) = 𝑠𝑢𝑝(𝑌)}

Một tập Y là một tập phổ biến đóng nếu nó là phổ biến và không tồn tại tập cha X⊃ Y và sup(X) = sup(Y).

Ví dụ 2.5:

Mã giao tác

Nội dung giao tác	Sắp xếp theo độ phổ biến giảm dần
1	a, c, f, m, p	f, c, a, m, p
2	a, c, d, f, m, p	f, c, a, m, p
3	a, b, c, f, g, m	f, c, a, b, m
4	b, f, i	f, b
5	b, c, n, p	c, b, p

Bảng 2.2 Cơ sở dữ liệu mẫu hạng mục được sắp xếp

Giả sử minsup =2, chúng ta có thể tìm kiếm và sắp xếp danh sách các hạng mục phổ biến theo độ phổ biến giảm dần. Danh sách hạng mục đã được sắp xếp được gọi là f_list. Trong ví dụ này f_list = {f: 4, c: 4, a: 3, b: 3, m: 3, p: 3}. Các hạng mục phổ biến trong mỗi giao tác đều được sắp xếp theo f_list và hiển thị trong cột thứ ba của bảng 2.2. Tập {fc} là một tập phổ biến gồm 2 hạng mục với độ phổ biến là 3, nhưng nó không phải là tập đóng, bởi vì có một tập cha {fcam} mà độ phổ biến cũng là 3. Vậy {fcam} là một tập phổ biến đóng.

2.2.7. Các tính chất của tập phổ biến

Tính chất 1:

Độ phổ biến của tập con lớn hơn tập cha.

Cho hai tập phổ biến X, Y với X  Y thì sup(X)  sup(Y)

Tính chất 2 :

Mọi tập con của một tập phổ biến đều là tập phổ biến.

X là tập phổ biến và Y  X thì sup(Y)  sup(X)  minsup, vì vậy Y cũng là tập phổ biến.

Tính chất 3 :

Mọi tập cha của một tập không phổ biến thì cũng không phổ biến.

X là tập không phổ biến và Y  X thì sup(Y)  sup(X) < minsup, vì vậy Y cũng không phải là tập phổ biến.

2.2.8. Cách biểu diễn dữ liệu

Trong các cơ sở dữ liệu quan hệ, thông thường dữ liệu sẽ được lưu trữ theo chiều ngang. Tức là các bảng dữ liệu hai chiều sẽ gồm N dòng tương ứng với các giao tác, và M cột tương ứng với các danh mục. Việc bố trí theo chiều ngang giúp cho việc xác định các danh mục thuộc về một giao tác đơn giản nhanh chóng. Tuy nhiên khi cần xác định một danh mục cụ thể thuộc vào những giao tác nào thì cách bố trí theo chiều ngang lại gây ra khó khăn, khi đó ta phải duyệt tất cả các giao tác có trong CSDL và ghi nhận những giao tác có chứa danh mục cụ thể đó.

Ví dụ 2.6: Trong CSDL mẫu ở bảng 2.1, muốn biết danh mục a xuất hiện trong những giao tác nào thì ta phải duyệt hết tất cả các danh mục xem giao tác nào chứa a thì liệt kê ra, kết quả các giao tác chứa a là tập {1, 3, 4, 5}

Có thể nhận thấy với các CSDL lớn thì việc xác định những giao tác có chứa một danh mục là rất tốn kém. Trong lúc đó việc xác định những giao tác có chứa một danh mục cụ thể lại là công việc thường xuyên để tính độ phổ biến của một tập danh mục. Để tăng tốc độ khai thác tìm tập phổ biến, chúng ta có thể sử dụng cách bố trí dữ liệu theo chiều dọc. Nghĩa là bảng dữ liệu có sự đảo chiều, các dòng biến thành các cột và ngược lại :

Ví dụ 2.7: CSDL mẫu trong bảng 2.1 được biểu diễn theo chiều dọc như sau :

Mã danh mục

Bảng 2.3 Minh họa dữ liệu định dạng theo chiều dọc

Lúc này việc xác định xem danh mục a có độ phổ biến bao nhiêu trong CSDL bố trí theo chiều dọc trở nên đơn giản bằng cách xác định dòng trong bảng tương ứng với mã danh mục a, kết quả là tập giao tác {1, 3, 4, 5} và sup(a) = 4

Các thuật toán khai thác tập phổ biến hiện nay sử dụng tập cơ sở dữ liệu theo chiều ngang hoặc chiều dọc. Cơ sở dữ liệu theo chiều ngang tương tự như tập dữ liệu giao tác trong thực tế với mỗi dòng trong cơ sở dữ liệu là một giao tác với một hoặc nhiều hạng mục. Trong khi đó, với cơ sở dữ liệu theo chiều dọc thì mỗi dòng bao gồm một hạng mục và tất cả định danh các giao tác (gọi là transaction ID) có chứa hạng mục đó. Tuy nhiên cách bố trí dữ liệu theo chiều dọc sẽ gây khó khăn trong việc quản lý bộ nhớ vì bảng dữ liệu gia tăng kích thước theo chiều ngang thay vì theo chiều dọc.

Ngoài ra, danh sách giao tác cũng có thể biểu diễn bằng cách nén trong ma trận bit. Theo cách này, nếu mục dữ liệu I xuất hiện trong giao tác t thì bit thứ i của t trong ma trận bit sẽ mang giá trị 1, ngược lại nó sẽ có giá trị 0. Với dữ liệu được nén theo phương pháp này, thì ma trận bit được sử dụng theo chiều dọc. Cách định dạng này có thể giảm không gian bộ nhớ hơn định dạng dữ liệu ngang và định dạng dữ liệu dọc. Tuy nhiên, phương pháp này chỉ đạt hiệu quả tốt nhất trên ma trận đặc (có nhiều bit 1).

Ví dụ 2.8:

CSDL mẫu trong bảng 2.1 được nén trong ma trận bit như sau:

Mã giao tác

a	b	c	d	e
1	1	1	0	1	1
2	0	1	1	0	1
3	1	1	0	1	1
4	1	1	1	0	1
5	1	1	1	1	1
6	0	1	1	1	0

Bảng 2.4 Minh họa dữ liệu biểu diễn bằng ma trận bit