Thuật Toán FP-Growth - Khai Thác Luật Kết Hợp Từ Cơ Sở Dữ Liệu Giao ...

Thuật toán kinh điển Apriori tuy đã làm giảm đáng kể số lượng tập ứng viên nhờ kỹ thuật tỉa. Tuy nhiên, trong tình huống mà số lượng tập mục lớn, cơ sở dữ liệu nhiều giao tác hoặc độ hỗ trợ tổi thiểu nhỏ, thuật toán Apriori gặp phải hai vấn đề chi phí lớn:

 Chi phí cho số lượng khổng lồ các tập ứng cử. Ví dụ: nếu cứ 104 tập 1- mục phổ biến thì thuật toán Apriori sẽ cần sinh ra hơn 107 các ứng cử 2- mục và thực hiện kiểm tra sự xuất hiện của chúng.

 Đòi hỏi lặp lại nhiều lần duyệt CSDL để kiểm tra tập rất lớn các ứng cử. Số lần duyệt CSDL của thuậtt Apriori bằng độ dài của mẫu phổ biến dài nhất tìm được. Trong trường hợp mẫu phổ biến dài hơn và CSDL lớn, có nhiều bản ghi, điều này là không thể thực hiện được. Thuật toán Apriori chỉ thích hợp cho các CSDL thưa (sparse), với các CSDL dày (dense) thì thuật toán thực hiện kém hiệu quả hơn.

Thuật toán tìm các tập phổ biến hiệu quả hơn thuật toán Apriori là thuật toán FP-Growth được đề xuất năm 2000 bởi J.Han, J Pei, Y.Yin và R.Mao cho phép tìm tất cả các tập phổ biến mà không cần sinh tập ứng viên nhờ vào việc sử dụng cấu trúc cây FP-Tree. Thuật toán FP-Growth gồm hai bước: bước 1 xây dựng cây FP-Tree qua hai lần duyệt CSDL, bước 2 duyệt cây FP-Tree để sinh các tập phổ biến.

2.3.2.1. Cấu trúc cây FP – Tree

Cấu trúc FP-Tree (Frequent Pattern tree ) được giới thiệu lần đầu tiên bởi các tác giả J.Han, J.Pei và Y.Yin trong bài báo "Mining FrequentPatterns without Candidate Generation" đã khắc phục được nhược điểm của thuật toán Apriori là phải phát sinh và kiểm tra một lượng lớn các ứng viên.

Cấu trúc FP-tree được dùng để tổ chức lại CSDL cho thuận lợi hơn trong quá trình tìm tập phổ biến, đồng thời các thông tin được nén trong cây FP-tree với tỉ lệ tương đối cao. Những thuận lợi đó là:

 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 dịch 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ả.

Cây FP-tree là cấu trúc cây với một số đặc điểm sau:

 Có một nút cha được đánh nhãn NULL, những nút con nối với nút cha là những thành phần chung của nhiều giao dịch được nén lại với nhau (item prefix subtree), bên cạnh cũng có một mảng các danh mục đơn phổ biến (frequent-item header table).

 Mỗi nút trong item prefix subtree có ba trường dữ liệu: mã danh mục, số tích lũy và con trỏ liên kết. Mã danh mục tương ứng danh mục mà nút này đại diện, số tích lũy là số giao dịch có chứa chung phần danh mục này, con trỏ liên kết dùng để liên kết 2 nút đại diện chung một mã danh mục ở hai item prefix subtree khác nhau. Giá trị con trỏ liên kết mang giá trị rỗng khi là nút cuối cùng trong chuỗi liên kết.

2.3.2.2. Xây dựng cây FP-Tree Thuật toán tạo cây FP-tree:

Duyệt toàn bộ CSDL và xác định thứ tự của các danh mục giảm dần theo độ phổ biến và được đưa vào trong f-list. Dựa vào ngưỡng phổ biến người dùng đưa vào sẽ xác định những danh mục nào được tạo trong FP-tree và sắp xếp các danh mục trong từng giao dịch theo thứ tự trong f-list. Sau đó tạo cây FP-tree bằng cách lần lượt xét từng giao dịch trong CSDL đã được sắp xếp và loại bỏ những danh mục không đạt ngưỡng phổ biến.

Input: CSDL giao tác D, min-sup Output: Cây FP-Tree

Method

1. Duyệt D lần đầu để thu được tập F gồm các frequent item và support count của chúng. Sắp xếp các item trong F theo trật tự giảm dần của support count ta được danh sách L.

2. Tạo nút gốc R và gán nhãn “null”

Tạo bảng Header có |F| dòng và đặt tất cả các node –link chỉ đến null 3. For each giao tác T D {// Duyệt D lần 2

Chọn các item phổ biến của T đưa vào P; Sắp các item trong P theo trật tự L;

Call Insert_Tree(P, R); }

Procedure Insert_Tree(P, Node) {

1. Đặt P=[p|P-p] , với p là phần tử đầu tiên và P-p là phần còn lại của danh sách

2. Nếu Node có một nút con (child) chứa nhãn p thì tăng chỉ số đếm của nút con đó thêm 1. Nếu không có thì tạo nút con mới nhãn p với chỉ số đếm là 1, tạo liên kết với nút trong cây có cùng nhãn (hoặc được trỏ tới bởi bảng header)

Nếu P-p ≠ thì gọi Insert_Tree(P-p, child) }

Ví dụ minh họa xây dựng cây FP-Tree

Cho CSDL giao tác như dưới đây với độ hỗ trợ tối thiểu là 2. Duyệt CSDL lần đầu tiên để tìm ra các tập phổ biến 1 phẩn tử (tập L) và sắp xếp chúng theo thứ tự độ hỗ trợ giảm dần.

- Duyệt CSDL lần thứ hai để xây dựng cây FP-Tree: + Cây FP-Tree khi mới khởi tạo:

2.3.2.3. Duyệt cây FP-Tree để tìm các tập mục phổ biến (thuật toán FP- Growth)

1. Bắt đầu từ mỗi mẫu phổ biến có chiều dài 1 trong bảng header (từ item có sup nhỏ nhất), xây dựng cơ sở mẫu có điều kiện (conditional pattern base) tương ứng với mỗi mẫu

2. Xây dựng Conditional tree của mỗi cơ sở mẫu

3. Quay lại bước 1 và thực hiện cho đến khi Conditional tree là một đường dẫn đơn thì tạo các mẫu phổ biến từ Conditional Tree và tập điều kiện.

Input: cây FP-Tree của CSDL D, ngưỡng minSup Output: Một tập đầy đủ các mẫu phổ biến F

Method: Call FP-Growth(FP-Tree, null, minSup) Procedure FP-Growth(FP-Tree,prefix,minSup)

{

- If Tree chỉ chứa một đường dẫn đơn P then tạo ra các tập phổ biến kết hợp

giữa prefix và các tổ hợp của những danh mục trong P, độ phổ biến bằng giá trị tích lũy nhỏ nhất của các nút tham gia vào tổ hợp. (Sau đó kết thúc hàm)

else { lần lượt xét từng phần tử a trong header của FP-Tree và phát sinh mẫu

=prefix a có sup()= sup(a)

- Duyệt FP-Tree để có CSDL điều kiện  (ký hiệu CSDL) - Dựng cây FP-Tree cho CSDL (FP-Tree )

- FP-Tree ≠ call FP-Growth(FP-Tree , , minSup) } }

Ví dụ minh họa bước khai phá cây FP-Tree:

Xét cây FP-Tree đã xây dựng trên ví dụ ở trên.  Gọi hàm FP-Growth(FP-Tree0,null,2)

 Xét a=I3: β = null  I3 = I3:6 (sup(β)=6) (để cây điều kiện  không phải là cây chỉ chứa đường dẫn đơn - không tổng quát)

- Xây dựng Conditional FP-Tree (FP- Tree ) với tập mẫu: {I1, I2: 2},{I2: 2},{I1:2}}

- MinSup=2 - L={I1: 4, I2: 4}

- Tập mẫu: {{I1, I2:2} {I2:2},{I1:2}} - Call FP-Growth(FP-Tree , β,2)

 Tiếp theo xét ai = I2 ta có β =I2 U β = {I3:6, I2:4}  sup (β) = sup (I2)= 4

 Cơ sở mẫu có điều kiện: {{I1:2}}  Cây thu được có đường dẫn đơn  các mẫu phổ biến {I3, I2, I1:2}, {I2, I3: 4}  Xét a = I1 ta có β =I1 U β = {I3:6, I1:4}

 sup (β) = sup(I1)= 4

 Cơ sở mẫu có điều kiện {Ø}  Cây thu được: Null

Nhận xét về thuật toán FP-Growth:

- Ưu điểm: Thuật toán FP-growth khá hiệu quả vì sử dụng cấu trúc cây FP- tree và duyệt theo chiều sâu với mô hình chia để trị.

- Nhược điểm: Sử dụng thuật toán đệ quy nên có khả năng gây tràn bộ nhớ. Việc xây dựng cây FP-Tree tốn nhiều công sức. Năm 2003, nhóm tác giả Mohammad El-Hajj và Osmar R.Zaiane ở ĐH Alberta Edmonton, Canada đề xuất thuật toán không đệ quy khai phá cây FP-Tree đựa trên cấu trúc cây COFI-Tree.

CHƯƠNG 3. TÌM LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU