Phương Pháp Tìm Kiếm Theo Chiều Rộng Và Theo Chiều Sâu

2.4. Một số chiến lược khai thác tập phổ biến

Cho một tập phổ biến F, tập đầy đủ các tập phổ biến có hơn 2F phần tử. Hình 2.19 chỉ ra những thành phần của một tập phổ biến đóng:

Root

f:4

c:4

b:3

fb:2

cb:2

cp:3

fcam:3

fcamp:2

Hình 2.19 Các thành phần của tập phổ biến đóng

Root

f:4

c:1

b:1

c:3

b:1

a:3

p:1

m:2

b:1

p:2

m:1

Hình 2.20 Ví dụ cây FP-Tree.

2.4.1. Phương pháp tìm kiếm theo chiều rộng và theo chiều sâu

Phương pháp tìm kiếm theo chiều rộng sử dụng các tập phổ biến ở cấp hiện tại với chiều dài k để tạo ra các ứng viên ở cấp tiếp theo với chiều dài k+1, và quét cơ sở dữ liệu mới là cần thiết để đếm độ phổ biến của các ứng viên với chiều dài k+1. Bởi vì quét dữ liệu quá nhiều lần nên nó không thích hợp để khai thác mô hình dài.

Ngược lại, phương pháp tìm kiếm theo chiều sâu chỉ tìm kiếm trong các cây con của một tập hợp khi tập đó là tập phổ biến. Khi các tập phổ biến trở nên dài hơn, DFS thu nhỏ không gian tìm kiếm một cách nhanh chóng. Kết quả là, phương pháp DFS thường tốt hơn BFS trong khai thác dữ liệu dài.

2.4.2. Định dạng theo chiều ngang và định dạng theo chiều dọc

Định dạng theo chiều dọc: một danh sách mã giao tác (tid-list) được giữ cho từng hạng mục, tid-list có thể lớn đối với bộ dữ liệu dày đặc. Để tìm các tập phổ biến, cần phải tìm giao của các tid-list với nhau (rất tốn chi phí), và với mỗi tập giao tìm được thì chỉ có một tập phổ biến.

Định dạng theo chiều ngang: mỗi giao tác được ghi nhận như là một danh sách các hạng mục. Chúng đòi hỏi ít không gian, và với mỗi lần quét cơ sở dữ liệu, chúng tìm thấy nhiều tập phổ biến cục bộ mà có thể được sử dụng để phát triển các tập tiền tố để tạo tập phổ biến.

2.4.3. Kỹ thuật nén dữ liệu

Một cơ sở dữ liệu giao tác thường là rất lớn. Nếu một cơ sở dữ liệu có thể được nén và chỉ các thông tin liên quan đến việc khai thác được lưu giữ, thì khai thác có thể có hiệu quả. Cây FP-Tree và Diffset là hai ví dụ điển hình. Cây FP-Tree của một CSDL là một cây tiền tố của danh sách các hạng mục phổ biến trong các giao tác. Ý tưởng này có thể được minh họa trong ví dụ như sau:

Ví dụ 2.17: Cây FP-Tree được xây dựng như sau: Quét các cơ sở dữ liệu một lần để tìm ra bộ các hạng mục phổ biến và sắp xếp chúng với độ phổ biến giảm dần để có được f_list (xem Ví dụ 2.5). Để chèn một giao tác vào cây FP-Tree, các hạng mục không phổ biến được xóa và hạng mục còn lại trong các giao tác đều được sắp xếp theo thứ tự của f_list, tức là, các mục ít phổ biến nhất là ở lá, và các hạng mục với độ phổ biến cao hơn ở một cấp cao hơn trong cây FP-Tree. Hình 2.19 cho thấy cây FP-Tree. Cấu trúc cây FP-Tree có một số lợi thế trong khai thác tập phổ biến. Trước hết, cây FP-Tree thường có một tỉ lệ nén cao trong khi biểu diễn tập CSDL bởi vì:

Những danh mục không đủ độ phổ biến được loại ngay từ đầu, vì vậy việc tìm tập phổ biến chỉ thao tác trên một số lượng danh mục nhỏ hơn nhiều so với toàn bộ các danh mục.

Nhiều giao tác sẽ được nén chung trong cây FP-Tree và việc này giúp giảm bớt khá nhiều thao tác trong quá trình xác định độ phổ biến của tập danh mục.

Cấu trúc FP-tree cho phép thực hiện tìm kiếm theo chiều sâu và áp dụng mô hình chia để trị khá hiệu quả.

Diffset là một thuật toán nén các tid-set hiệu quả cho phương pháp áp dụng các định dạng dữ liệu theo chiều dọc. Đối với một thuật toán định dạng theo chiều dọc giống như thuật toán CHARM, tính toán độ phổ biến đòi hỏi các nút giao nhau trên tidsets, khi tidset quá lớn, không chỉ các tidsets tiêu tốn nhiều bộ nhớ, những tập giao của các tidset cũng gây tốn bộ nhớ. Để tránh điều đó, CHARM phát triển một kỹ thuật Diffset chỉ giữ lại sự khác biệt của các tid và các tập ứng viên khi nó sản sinh ra tập phổ biến.

2.4.4. Kỹ thuật loại bỏ để khai thác tập phổ biến

Định nghĩa 1: (Item merging) Giả sử X là một tập phổ biến và tất cả các giao tác có chứa tập danh mục X, đồng thời mọi giao tác này cũng chứa tập danh mục Y

≠ ∅ với Y ∩ X = ∅ và không tồn tại tập Y’ tương tự như Y với Y ⊂ Y’ (có nghĩa là Y là tập lớn nhất có thể có). Thì có thể kết luận là tập X ∪ Y là một tập phổ biến đóng có sup (X ∪ Y) =|Transaction|; và những tập phổ biến chứa X mà không chứa Y thì không thể là tập phổ biến đóng.

Ví dụ 2.18: Trong ví dụ 2.5 hiển thị trong bảng 2.2, cơ sở điều kiện cho tập tiền tố {fc: 3} là {(a, m, p), (a, m, p), (a, b, m)} (mục d và g là không phổ biến và bị loại), từ đó chúng ta có thể thấy mỗi giao tác của nó chứa hạng mục {am} nhưng không có tập cha của {am}. Hạng mục {am} có thể được sáp nhập với {fc} để tạo thành một tập phổ biến {fcam: 3}, và ta không cần phải khai thác tập phổ biến đóng chứa {fc} nhưng không chứa {am}.

Định nghĩa 2: (sub-itemset pruning) [5]: Xét X là tập phổ biến. Nếu X là một tập hợp con của một tập phổ biến đóng Y và sup (X) = sup (Y) thì X và tất cả các tập con của X không thể là một tập phổ biến đóng và do đó có thể được loại bỏ.

Ví dụ 2.19: Nhiều thuật toán khai thác mô hình phổ biến theo các mô hình chia để trị. Trong ví dụ hình 2.20, một mô hình chia để trị từ trên xuống theo thứ tự f_list thể hiện trong Ví dụ 2.5 (ngược lại, một mô hình chia để trị từ dưới lên sẽ làm theo thứ tự ngược lại của f_list):

(1) khai thác mẫu có chứa mục f,

(2) khai thác các mẫu có chứa mục c nhưng không có f,

(3) khai thác các mô hình có chứa một hạng mục nhưng không có f cũng không c, ..., Và cuối cùng là khai thác các mô hình chỉ chứa p. Tại một số điểm mà chúng ta muốn khai thác các mô hình với tiền tố {ca: 3}, chúng ta sẽ tìm thấy rằng {ca:3} là một tập hợp con riêng của tập phổ biến đóng {fcam: 3} đã tìm thấy với cùng độ phổ biến, ta có thể dừng khai thác các mô hình đóng với tiền tố {ca: 3}.

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

Trong chương này, luận văn đã trình bày một số khái niệm về tập phổ biến, và trình bày một số thuật toán nền tảng để tìm các tập phổ biến sử dụng phương pháp sinh ứng viên như thuật toán Apriori, thuật toán FP-Growth...

Trong thực tế có các cơ sở dữ liệu đặc biệt như: số hạng mục và số giao tác rất lớn dẫn đến việc khai thác theo phương pháp truyền thống thường gặp phải hạn chế về không gian lưu trữ cũng như hiệu năng tính toán do số lượng các ứng viên xuất hiện trong quá trình khai thác tăng theo cấp độ hàm mũ, dữ liệu được xuất ra dư thừa nhưng không có đủ thông tin phù hợp để khai thác,.v.v. Để giải quyết những hạn chế của phương pháp truyền thống gần đây những hướng tiếp cận là các phương pháp và kỹ thuật mới, bao gồm phương pháp tìm kiếm mới, cấu trúc dữ liệu hiện đại và kỹ thuật nén mới và áp dụng kỹ thuật chia để trị tiêu biểu Disclosed [15] là thuật toán hiệu quả đầu tiên khai thác theo chiều sâu, từ trên xuống cho các tập phổ biến đóng. Một thuật toán khai thác các tập phổ biến thường gọi là PIETM [16] được đề xuất, phát hiện ra các tập phổ biến theo cách từ dưới lên bằng hai lần quét cơ sở dữ liệu.

Sau khi nghiên cứu các thuật toán khai thác tập phổ biến dựa trên cấu trúc cây tìm kiếm theo chiều ngang, thì trong chương tiếp theo của luận văn học viên sẽ trình bày một hướng tiếp cận đó là sử dụng ma trận bit để nén tập dữ liệu. Bên cạnh đó, sử dụng kỹ thuật 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ũng được áp dụng.

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

3.1. Khai thác dữ liệu theo cấu trúc cây tìm kiếm

Trong thực tế thường có hai phương án xây dựng cấu trúc cây tìm kiếm: Duyệt theo hạng mục và duyệt theo giao tác. Tùy thuộc vào đặc điểm của tập dữ liệu mà phương án thích hợp sẽ được lựa chọn.

3.1.1. Cây tìm kiếm duyệt theo giao tác

Là phương pháp tiếp cận theo chiều dọc, trong đó, cây tìm kiếm được xây dựng dựa trên số hàng và cho mỗi nút của cây, hạng mục thông thường của tất cả các số hàng của nó được xem xét.

Chiến lược tìm kiếm từ dưới lên: Cây tìm kiếm được xây dựng từ tập các nút, mỗi nút là sự kết hợp của một số dòng (gọi là tập dòng hay rowset) trong tập dữ liệu ban đầu. Mức đầu tiên trong cây là nút gốc có giá trị rỗng. Mức thứ hai có m nút (với m là số dòng trong tập dữ liệu), mỗi nút được biểu diễn bằng một mã định danh dòng (ký hiệu là row-id). Nếu gọi x là một nút ở mức thứ hai; ở mức thứ ba, các nút con của x sẽ được xây dựng bằng cách kết hợp x với một trong các row-id lớn hơn x. Như vậy, với mỗi y > x, xy là nút con của nút x được tạo ra ở mức thứ ba. Các nút ở mức tiếp theo của cây sẽ được xây dựng theo cách tương tự. Thí dụ ta có CSDL có 4 giao tác, hình 3.1 biễu diễn cây tìm kiếm từ dưới lên

{}

1 2 34

12 13 14 23 2434

123 134

234

1234

Hình 3.1 Biễu diễn cây tìm kiếm từ dưới lên

Chiến lược tìm kiếm từ trên xuống: Ngược lại với phương pháp tìm kiếm từ dưới lên, phương pháp tìm kiếm từ trên xuống bắt đầu từ rowset lớn nhất đến rowset nhỏ nhất.

1234

123 124 134234

12 13 23

12 1424

13 14 34 23 24 34

1 2 3 4

Hình 3.2 Biểu diễn cây tìm kiếm từ trên xuống

3.1.2. Cây tìm kiếm duyệt theo hạng mục

Trong cách này, chúng ta xem xét tập hợp tất cả các hạng mục (cột) được sử dụng trong tập dữ liệu và do đó là sẽ tìm số lượng giao tác (hàng) của tập dữ liệu chứa các kết hợp khác nhau của các mục. Chúng ta gọi phương pháp này là phương pháp ngang và gọi các thuật toán liên quan của nó như là các thuật toán ngang.

Cây tìm kiếm được xây dựng từ các nút, mỗi nút được kết hợp từ các hạng mục trong tập dữ liệu ban đầu. Nút đầu tiên tương ứng mức 1 trên cây là nút gốc có giá trị rỗng. Mức thứ 2 gồm n nút (với n là số lượng hạng mục không trùng nhau trong tập dữ liệu), mỗi nút được biểu diễn bằng một hạng mục trong tập dữ liệu. Nếu gọi x là một nút ở mức thứ hai, ở mức thứ ba, các nút con của x sẽ được xây dựng bằng cách kết hợp x với một trong các hạng mục chưa xuất hiện trong x, tương tự cho các mức tiếp theo.

Ví dụ 3.1: Ta xét lại cơ sở dữ liệu giao tác của ví dụ 2.16 bảng 2.13. Cơ sở dữ liệu này có 4 mục được sắp xếp theo độ phổ biến tăng dần nếu trùng độ phổ biến thì sắp theo thứ tự từ điển.

Nội dung	Tập dữ liệu D
1	a, b, c, e	b, a, c
2	a, c, f, g	a, c
3	b, d, h	d, b
4	a, c, i, j, k	a, c
5	a, b, l	b, a
6	a, c, m, n	a, c
7	b, c, p	b, c
8	a, b, c, d, q, r	d, b, a, c

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

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

Mã giao tác

Bảng 3.1 Tập dữ liệu D được cắt tỉa với minsup=2.

Hình 3.3 trình bày cây tìm kiếm duyệt theo hạng mục với tập dữ liệu D bảng 3.1 có 4 hạng mục là d, b, a, c. Mở rộng mục d, b, a trong không gian tìm kiếm của thuật toán ngang của tập dữ liệu D bảng 3.1

{}

d c

db da dc ba bc ac

dba dac

dbac

bac

Hình 3.3 Mở rộng mục d, b, c trong không gian tìm kiếm của thuật toán ngang của tập dữ liệu bảng 3.1

Hình 3.3 cho thấy không gian tìm kiếm của các thuật toán nằm ngang cho tập dữ liệu của bảng 3.1. Các thuật toán khai thác duyệt theo hạng mục thường được sử dụng để khai thác các tập dữ liệu có đặc điểm ít hạng mục và nhiều giao tác như các tập dữ liệu trong thương mại. Tuy nhiên, với các tập dữ liệu có đặc điểm số hạng mục thì nhiều nhưng số giao tác lại ít, thì các thuật toán khai thác dữ liệu duyệt theo hạng mục thường gặp phải hạn chế về không gian lưu trữ cũng như hiệu năng tính toán do

số lượng các ứng viên xuất hiện trong quá trình khai thác tăng theo cấp độ hàm mũ. Vì vậy, các thuật toán được xây dựng dựa theo cấu trúc cây tìm kiếm duyệt theo giao tác được xem là giải pháp khá hiệu quả đối với lớp bài toán này.

Trong luận văn này kết hợp phương pháp tiếp cận ngang với kỹ thuật phân chia để trị, sử dụng một số định nghĩa để thiết lập giao tác giữa số hàng và hạng mục trong tập dữ liệu được chia và để trích xuất các tập phổ biến từ tập dữ liệu rất lớn các hạng mục.

3.2. Phương pháp khai thác ngang

Trong chương này trình bày phương pháp khai thác ngang bao gồm: mô tả một số định nghĩa và ví dụ. Sau đó, trình bày thuật toán Mining Row Item Horizontal (MRIH).

3.2.1. Sử dụng phương pháp chia để trị trong khai thác ngang

Phương pháp khai thác ngang được xây dựng dựa trên phương pháp phân chia để trị. Trong cách tiếp cận này, chúng ta chia ra một tập dữ liệu dựa trên các mô hình phổ biến của của tập dữ liệu. Nhìn chung, chúng ta có thể phân chia các mô hình được khai thác của từng tập dữ liệu trong các loại khác nhau dựa trên các mục có trong mỗi mẫu. Với mục đích này, trước tiên chúng ta nên sắp xếp các mục trong mỗi giao tác theo thứ tự (thứ tự dựa trên các giá trị phổ biến tăng dần) và sau đó phân loại các mẫu phổ biến theo thứ tự như sau: Các mẫu có chứa mục đầu tiên (theo thứ tự chung) sẽ là các thành viên của thể loại đầu tiên, mẫu có chứa mục thứ hai và không chứa mục đầu tiên sẽ là thành viên của thể loại thứ hai, các mẫu có chứa mục thứ ba và không chứa các mục đầu tiên và thứ hai sẽ là thành viên của nhóm thứ ba và tiếp tục như vậy như vậy cho đến hết hạng mục.

Ví dụ 3.2: Ta xét lại cơ sở dữ liệu giao tác ví dụ 3.1 được cắt tỉa như bảng 3.1. Cơ sở dữ liệu này có 4 mục được sắp xếp theo độ phổ biến tăng dần nếu trùng độ phổ biến thì sắp theo thứ tự từ điển. Chúng ta có thể chia mô hình trích xuất của tập dữ liệu này thành 4 lớp khác biệt như sau:

1) Các mẫu chứa d.

2) Các mẫu có chứa b và không chứa d.

3) Các mẫu có chứa a và không chứa d và b.

4) Các mẫu chỉ chứa c.