IT-Tree và thuật toán Apriori

IT-TREE VÀ THUẬT TOÁN APRIORI

TRẦN ĐÌNH NGHĨA(*),
NGUYỄN QUỐC HUY(**)

TÓM TẮT

Khám phá itemsets là công việc quan trọng trong khai thác dữ liệu. Nhờ đó mà ta có thể khai
thác luật kết hợp từ các itemsets đó. Tuy nhiên, không gian tìm kiếm trong giai đoạn tìm các
itemsets cần thiết thì rất lớn theo từng bước, độ dài k của các item. Do vậy, chúng ta cần phải
quan tâm đến việc rút gọn không gian tìm kiếm. Apriori (2,7) là một tính chất quan trọng, nhờ đó
mà ta có thể loại bỏ những itemsets không cần thiết ở các bước sau. Thuật toán Apriori (2,7) là
thuật toán kinh điển trong việc khai thác tập phổ biến. IT-Tree (1,3,4,5) (tidset-itemset search
tree) là một cấu trúc cây được Zaki và các đồng nghiệp đưa ra, có nhiều điểm giống thuật toán
Apriori.

ABSTRACT

Mining itemsets is significant work in data mining. Therefore, we can mine association rules
from these itemsets. However, the search space in mining itemsets phase is very large if the
length k of itemsets grows up. Thus, it is necessary to interest in reducing the search space.
Apriori [2] is an important property from which we can remove unnecessary itemsets in the next
steps. Apriori algorithm [2] is a classic algorithm in mining frequent itemsets. IT-Tree [1,3]
(tidset-itemset search tree) is a tree structure proposed by Zaki et al with many factors the same
as Apriori algorithm.

1. GIỚI THIỆU

Khai thác các itemsets là công việc rất cần thiết trong lĩnh vực khai thác dữ liệu và rất phổ biến
trong các ứng dụng phân tích thị trường, thiết kế catalog, và phân khúc khách hàng. Bài toán
khai thác itemsets sẽ rất lớn nếu cơ sở dữ liệu lớn, khi đó không gian tìm kiếm sẽ rất lớn và sẽ
không thực hiện được trong thực tế. Do vậy, vấn đề giảm không gian tìm kiếm rất cần thiết để
hiện thực bài toán này trong thực tế. Hiện nay thuật toán Apriori được xem là mẫu mực để giải
quyết bài toán này, gần đây cấu trúc IT-Tree cũng đóng góp không nhỏ vào bài toán khai thác
itemsets.

Thuật toán Apriori sinh ra các tập ứng viên để tính trong một lần duyệt bằng việc sử dụng chỉ các
itemsets đã được thấy là phổ biến trong lần duyệt trước mà không cần quan tâm đến các giao tác
trong cơ sở dữ liệu (CSDL). Cơ sở của điều đó là bất kỳ tập con nào của itemsets phổ biến phải
là phổ biến, đây là tính chất Apriori. Vì vậy, các tập ứng cử có k-item có thể được sinh ra bằng
cách kết nối các tập phổ biến có (k - 1)-item, và xoá các tập ứng viên nếu nó có chứa bất kỳ một
tập con nào mà không phải là phổ biến. Thủ tục này nói chung dẫn đến một số nhỏ hơn nhiều các
tập ứng cử viên, nói cách khác nó khá hiệu quả trong việc "tỉa gọn" không gian tìm kiếm.

IT-Tree có cách tiếp cận đơn giản là dựa trên phần giao nhau của tập các giao tác để tính độ phổ
biến và khái niệm mới lớp tương đương nhằm chia không gian xử lý ban đầu thành tập các
không gian nhỏ độc lập giúp cho việc tìm kiếm nhanh hơn. Một điểm mới nữa của phương pháp
IT-tree là dựa trên phần khác nhau trên Tidset của các tập dữ liệu nhằm làm giảm kích thước bộ
nhớ yêu cầu và giúp cho việc tính độ phổ biến nhanh hơn.


, **)Th.S, Khoa Công nghệ thông tin, Trường Đại học Sài Gòn
(*) (
Để giảm kích thước bộ nhớ lưu Tidset, tác giả của IT-Tree là Zaki và Gouda đề nghị lưu Diffset
(tập khác nhau giữa Tidset(X) so với Tidset(Y)), Diffset có kích thước khá nhỏ so với Tidset nên
dung lượng bộ nhớ giảm đáng kể. IT-Tree thỏa tính chất Apriori.




Hình 1.1 Thuật toán Apriori

Thuật toán Apriori sử dụng độ hỗ trợ tối thiểu (minsup) để loại bỏ các ứng viên không thoả
minsup. Giá trị minsup do người dùng đưa ra.

Định nghĩa 1. Độ hỗ trợ của itemset: Độ hỗ trợ (Support) của một tập X trong tập các giao tác
D, kí kiệu supp(X) xác định như sau:

T  D/T  X
supp(X) ; Miền giá trị: 0 Supp(X) 1 với mọi tập X.
D

Định nghĩa 2. Lớp tương đương: Cho I là tập các danh mục và X  I . Gọi hàm p(X, k) =
X[1:k] gồm k phần tử đầu của X và một quan hệ tương đương dựa vào tiền tố  K trên itemset
như sau: X , Y  I , X k Y  p( X , k )  p(Y , k ) . Hai itemset có cùng một lớp tương đương
khi và chỉ khi chúng chia sẻ k phần tử đầu.

Mỗi nút trong IT-Tree đại diện cặp Itemset-Tidset X  t (X ) , thực tế là lớp tiền tố. Tất cả các nút
con của nút X thuộc về lớp tương đương vì chúng cùng tiền tố X.

Bảng 1.1: Cơ sở dữ liệu giao tác

Mã giao tác A C D T W
t1 1 1 0 1 1
t2 0 1 1 0 1
t3 1 1 0 1 1
 t4 1 1 1 0 1
t5 1 1 1 1 1
t6 0 1 1 1 0

Kí hiệu lớp tương đương là P  l1 , l 2 ,..., l n , trong đó P là nút cha và mỗi li là một mục dữ liệu
đơn, đại diện cho nút Pl i  t ( Pl i ) . Chẳng hạn, nút gốc của cây tương ứng với lớp [] =
{A,C,D,T,W}, nút trái cùng của gốc là lớp [A] chứa tất cả các itemset có A là tiền tố, nghĩa là tập
{C,D,T,W}. Như vậy, mỗi lớp thành viên đại diện cho một con của nút cha. Một lớp đại diện
cho các mục dữ liệu mà các mục dữ liệu đó là tiền tố để có thể mở rộng thành các lớp mới. Rõ
ràng, không có cây con nào của một tiền tố không tồn tại được xét. Điểm mạnh của phương pháp
lớp tương đương là không gian xử lí ban đầu được chia thành các phần nhỏ độc lập. Đối với mỗi
nút gốc con của nút X, có thể xem như một vấn đề mới hoàn toàn; mỗi nút có thể sinh ra các
itemset bên dưới.




Hình 1.2. Cấu trúc IT-Tree của bảng 1.1

2. SO SÁNH

Dựa vào tính chất Apriori, cả 2 đều áp dụng để tỉa các itemsets không cần thiết để giảm không
gian tìm kiếm. IT-Tree cũng thoả tính Apriori. Như hình vẽ 1.2, ta thấy các nút con xuất hiện
trên một tập giao tác nào đó thì các nút cha chắc chắn cũng sẽ xuất hiện trên tập giao tác đó.
Ngược lại, nếu nút cha chỉ cần không xuất hiện trên 1 giao tác nào cả thì tập con – là tập cha hợp
với 1 item nào đó – cũng sẽ không xuất hiện trên toàn cơ sở dữ liệu. Từ đó ta có thể tiên nghiệm
được nhờ vào tính chất này để loại bỏ cả nhánh lớp tương đương có chứa tiền tố mà đã xác định
là không xuất hiện trên cơ sở dữ liệu giao tác.

2.1. Ý tưởng tỉa itemsets giữa thuật toán Apriori và IT-Tree

Giải thuật phổ biến nhất của loại này là giải thuật Apriori, trong đó có trình bày tính chặn dưới
của itemset thỏa minsup. Giải thuật Apriori sử dụng các tính chất này bằng cách tỉa bớt những
ứng viên thuộc tập không phổ biến trước khi tính độ phổ biến của chúng. Cách tối ưu có thể thực
hiện được vì các giải thuật tìm kiếm ưu tiên theo chiều rộng (BFS) bảo đảm rằng các giá trị hỗ
trợ của các tập của một ứng viên đều được biết trước. Giải thuật Apriori đếm tất cả các ứng viên
có k phần tử trong một lần đọc CSDL. Phần cốt lõi của bài toán là xác định các ứng viên trong
mỗi giao tác. Thuật toán Apriori tỉa các itemsets không phổ biến.

IT-Tree áp dụng lí thuyết lớp tương đương, dựa vào hình vẽ 1.2 là minh hoạ của bảng cơ sở dữ
liệu giao tác 1.1, ta thấy các lớp con của một lớp nào đó là: một itemsets gồm các item. Mỗi item
xuất hiện trên một số giao tác, và tập các giao tác chứa item đó gọi là tập giao tác (tidset). Một
itemset gồm nhiều item, nên tidset của itemset đó là phần giao của các tidset con. Do vậy, trên
IT-Tree sẽ không xuất hiện những itemset mà có tập tidset rỗng, điều đó tương đương với việc
itemset đó không xuất hiện trên CSDL và sẽ vô nghĩa khi xét đến nó. IT-Tree tỉa các itemsets
không xuất hiện trên CSDL.

2.2. Điểm yếu của thuật toán Apriori và điểm mạnh của IT-Tree

Như thuật toán Apriori trong hình 1.1, dòng 3 là thủ tục apriori_gen dùng để sinh các ứng viên.
Thủ tục apriori_gen sinh ra tập ứng viên mới k-itemsets từ (k-1)-itemsets, tham khảo hình 2.1.
Trong thủ tục này một (k-1)-itemsets kết nối với các item khác trong Lk-1 và tạo ra 1 ứng viên
mới có k items và tính độ hỗ trợ của ứng viên đó. Nếu ứng viên nào thoả độ hỗ trợ thì lưu vào
tập Ck.

Để thấy rõ điểm yếu của thuật toán Apriori, giả sử thực hiện một bài toán có độ hỗ trợ tối thiểu
(minsup) là 0. Lúc đó cơ sở dữ liệu có n item thì sẽ có 2n ứng viên, nếu n lớn thì số ứng viên quá
lớn.

Lý do là thủ tục apriori_gen luôn luôn phải thực hiện công việc kết nối, đối với các item vô nghĩa
kết nối với (k-1)-itemsets cho ra một k-itemsets vô nghĩa. Sau đó còn phải tốn một thao tác để
tính độ hỗ trợ cho itemsets vô nghĩa đó mới có thể xác định itemsets đó không thuộc tập C k.
Ngoài ra, nếu độ hỗ trợ tối thiểu minsup bị thay đổi thì thuật toán sẽ phải thực hiện lại từ đầu,
điều này sẽ rất mất thời gian.




Hình 2.1. Thủ tục apriori_gen

Phương pháp IT-tree có một số điểm mạnh như sau:

i) Đọc CSDL một lần và lưu vào tập [] = {1 – itemset}, vì khi sinh các tập phổ biến khác ở
mức kế, thuật toán chỉ đơn giản hợp hai tập phổ biến ở mức trên lại thành tập mới, Tidset
mới được tính bằng cách giao hai Tidset của các tập tạo ra nó. Như vậy, nếu dung lượng bộ
nhớ đủ chứa thì phương pháp này chỉ cần đọc CSDL một lần.
ii) Không cần phải sinh ứng viên như họ thuật toán Apriori. Điều này kéo theo không cần phải
có thao tác tính độ hỗ trợ không cần thiết để xác định ứng viên đó có phổ biến hay không.
Giả sử độ hỗ trơ tối thiểu (minsup) là 0 thì cũng không ảnh hưởng gì đến việc sinh ứng viên.
iii) Có thể dùng thuật toán song song để khai thác tập phổ biến.
2,3. Ứng dụng trong bài toán tìm luật kết hợp

Bài toán tìm luật kết hợp có 2 giai đoạn. Giai đoạn 1 tìm tập phổ biến, giai đoạn 2 tìm luật kết
hợp từ các tập phổ biến đó. Trong việc tìm luật tập phổ biến có các thuật toán tiêu biểu sau
Apriori, Apriori-Gen, Apriori-Tid, FP-Growth (2,7).

Bài toán luật kết hợp [8,9,10,11,12]

Cho một tập các giá trị I, một cơ sở dữ liệu giao dịch D, độ hỗ trợ tối thiểu minsup, độ tin cậy
mincof, tìm các luật kết hợp dạng X  Y trên D thoả mãn điều kiện Support(X  Y) ≥ minsup và
Confidence(X  Y) ≥ mincof.

 Xác định các tập phổ biến:

Việc xác định các tập phổ biến gồm có hai bước chính sau đây:
- Xác định các tập ứng viên (Ck).
- Xác định các tập phổ biến (L) dựa vào tập ứng viên

Để xác định tập ứng viên, ta thực hiện các bước sau đây:
- Tìm các tập ứng viên một itemset.
- Quét CSDL D để xác định độ hỗ trợ của các tập ứng cử viên. Trong vòng đầu tiên, các tập ứng

cử viên cũng chính là tất cả các mục có trong CSDL. Tại vòng thứ k (k>1), các tập ứng cử viên
được xác định dựa vào các tập phổ biến đã xác định tại vòng k – 1, sử dụng hàm Apriori-gen()
(2). Sau khi đã xác định được các tập ứng cử viên, thuật toán quét từng giao dịch trong CSDL để
tính độ hỗ trợ của các tập ứng cử viên. Quá trình xác định các tập phổ biến sẽ kết thúc khi không
xác định được thêm tập phổ biến nào nữa.

Nội dung hàm Apriori-gen(). Hàm Apriori-gen() thực hiện hai bước (2,9):
- Bước đầu tiên, Lk – 1 được kết nối với chính nó thu được Ck.
- Bước thứ hai, Apriori_gen() xoá tất cả các itemsets từ kết quả kết nối mà có một số tập con (k –
1) không có trong Lk – 1. Sau đó nó trả về itemsets phổ biến kích thước k còn lại.

 Sinh các luật kết hợp từ tập phổ biến:

Việc phát hiện các tập phổ biến rất tốn kém về mặt tính toán. Tuy nhiên, ngay khi tìm được tất cả
các tập phổ biến (l  L), ta có thể dễ dàng sinh ra các luật kết hợp có thể có bằng các bước như
sau:

- Tìm tất cả các tập con không rỗng x, của tập phổ biến l  L.
- Với mỗi tập con x tìm được, ta xuất ra luật dạng x  (l - x) nếu tỉ lệ Support(l)/Support(x) ≥
mincof ( %).

 Ứng dụng IT-Tree trong giai đoạn xác định tập phổ biến:

Nhận xét thấy chỉ có những itemset nào có tập giao tác khác rỗng thì mới có thể xuất hiện trong
giao tác, lúc đó mới tính độ hỗ trợ và so sánh với minsup. Còn lại những itemset có tập giao tác
bằng rỗng thì không xuất hiện trong cơ sở dữ liệu đó. Ví dụ một tập các món hàng mà không
được bán lần nào hết thì tập món hàng đó không xuất hiện trong hoá đơn bán hàng. Do vậy ta có
thể tỉa bớt những tập đó trong quá trình sinh tập k-itemsets từ tập (k-1)-itemsets để giảm bớt
không gian xử lí. Để ứng dụng IT-Tree ta cần thay thế hàm Apriori_gen trong thuật toán Apriori
thành hàm IT_Tree, như trong hình 2.2, để sinh ra một k-itemset từ hai (k-1)-itemsets ta cần phải
xét đến hai yếu tố:

1. Hai (k-1)-itemsets phải cùng tiền tố
2. Giao hai tập giao tác của hai (k-1)-itemsets, nếu tập giao khác rỗng thì k-itemset được thêm
vào tập Ck.

1. IT_Tree([P], minsup)
2. for all li  [P] do
3. [Pi] = 
4. for all lj  [P], with j > i do
5. I = lj
6. T = t(li)  t(lj)
7. if Pi .Support()  minsup then
8. [Pi] = [Pi]  { I  T }
9. IT_Tree ([Pi], minsup)

Hình 2.2: Hàm IT_Tree tìm itemsets phổ biến

Trong hàm IT_Tree [1,3,4,5,12] gọi P  l1 , l 2 ,..., l n là lớp tương đương, trong đó P là nút cha
và mỗi li là một mục dữ liệu đơn, đại diện cho nút Pl i  t ( Pl i ) . Dòng 9 gọi đệ quy lại hàm
IT_Tree để tính tiếp cho lớp tương đương tính từ nút [Pi].

3. KẾT LUẬN

IT-Tree là hình ảnh minh họa trường hợp tổng quát của thuật toán Apriori. Nhưng với tổ chức
như IT-Tree, ta có thể đọc CSDL chỉ một lần và sử dụng tập tidset để tính độ hỗ trợ nếu cần. Để
giải quyết một thuật toán hiệu quả về khai thác itemsets trên CSDL lớn, ta cần phải quan tâm đến
2 vấn đề:

- Rút gọn không gian tìm kiếm
- Giảm thiểu việc đọc thông tin từ cơ sở dữ liệu

IT-Tree có thể xem là cấu trúc dữ liệu lí tưởng để cải tiến được những thuật toán có liên quan
đến khai thác itemsets, nên nó là công cụ hữu ích nếu chúng ta làm việc với các vấn đề khai thác
luật kết hợp và khai thác itemsets có ích. Thuật toán IT-Tree có thể thay thế hoàn toàn các thuật
toán họ Apriori để thực hiện tối ưu giai đoạn tìm itemsets theo một tiêu chí nào đó, ví dụ như độ
hỗ trợ và độ có ích.

Chúng tôi đã tiến hành thử nghiệm thuật toán khai thác các itemsets phổ biến trên một số CSDL
giao tác tạo được bằng phương pháp tạo ma trận số ngẫu nhiên. Căn cứ vào các kết quả thử
nghiệm và việc phân tích cấu trúc thuật toán, chúng tôi nhận thấy thực hiện theo IT-Tree có
những ưu điểm vượt trội so với các thuật toán họ Apriori.

Ngoài ra, tính chất Apriori kết hợp với ý tưởng IT-Tree còn có thể áp dụng được trong bài toán
khai thác đồ thị con phổ biến là bài toán được nhiều người quan tâm và nghiên cứu trong lĩnh
vực khai thác dữ liệu.

CHÚ THÍCH
[1]. Các từ khoá: tập phổ biến, IT-Tree, tập có ích, itemsets

TÀI LIỆU THAM KHẢO

1. Nguyễn Quốc Huy (2008) , “Khai thác itemsets có ích từ cơ sở dữ liệu”, Luận văn thạc sĩ
Tin học, ĐH KHTN, ĐHQG TP.HCM.
2. Nguyễn Thanh Thuỷ, Khai phá dữ liệu – Kĩ thuật và ứng dụng. Bài giảng trường thu Hệ mờ
và ứng dụng, Hà Nội, tháng 8-2001.
3. Le, B., Nguyen, H., Cao, T.A.,Vo, B.: A Novel Algorithm for Mining High Utility Itemsets.
In: IEEE 1st Asian Conference on Intelligent Information and Database Systems, April 1- 3,
2009, Quang Binh, Vietnam, pp. 13 - 17 (2009).
4. Bac Le., Huy Nguyen., Bay Vo.: Mining high Utility Itemsets from Vertical distributed
Databases. In: IEEE RIFV’09, July, 2009, Danang, Vietnam.
5. Bac Le., Tu Bao Ho., Huy Nguyen., Bay Vo.: Parallel Method for Mining High Utility
Itemsets from Vertically Partitioned Distributed Databases. In: Springer KES’09, Sep, 2009,
Santiago, Chile.
6. C. J. Matheus and P. K. Chan and G. Piatetsky-Shapiro, Systems for knowledge discovery in
databases, Ieee Trans. On Knowledge And Data Engineering, vol 5, pp 903-913, 1993
url=http://citeseer.nj.nec.com/177052.html
7. Christian Borgelt and Rudolf Kruse, Department of Knowledge Processing and Language
Engineering School of Computer Science. Induction of Association Rules:
AprioriImplementation.Otto-von-Guericke-UniversityofMagdeburg Universităatsplatz 2, D-
39106 Magdeburg, Germany.
8. Jiawei Han and Yongjian Fu, Dynamic Generation and Refinement of Concept Hierarchies
for Knowledge Discovery in Databases,KDD Workshop, pp 157-168, 1994,
url=http://citeseer.nj.nec.com/han94dynamic.html
9. Jiawei Han, Jian Pei, Yiwen Yin. Mining Frequent Patterns without Candidate Generation.
SIGMOD Conference 2000.
10. Jiawei Han and Micheline Kamber, Data mining: Concepts and Techniques. Academic
Press 2001.
11. J. Han, Y. Cai, and N. Cercone. Data-driven Discovery of Quantitative Rules in Relational
Databases. IEEE Trans. Knowledge and Data Eng., 5:29--40, 1993.
url=http://citeseer.nj.nec.com/agrawal93mining.html
12. R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In Proc. 1994
Int.Conf.VLDB,Santiago,Chile,Sept.1994. rl=citeseer.nj.nec.com/article/agrawal94fast.html