Thuật toán khai phá tập mục thường xuyên trong cơ sở dữ liệu lớn thông qua mẫu đại diện

Chia sẻ: Liễu Yêu Yêu | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

36
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết "Thuật toán khai phá tập mục thường xuyên trong cơ sở dữ liệu lớn thông qua mẫu đại diện" đề xuất thuật toán RSFPGrowth khai phá tập mục thường xuyên trong cơ sở dữ liệu lớn thông qua mẫu đại diện. Thuật toán RSFPGrowth cho phép thay vì tìm tập tất cả các tập mục thường xuyên trong cơ sở dữ liệu lớn bằng cách tìm tập chứa hầu hết các tập tập mục thường xuyên từ tập mẫu đại diện các giao tác. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thuật toán khai phá tập mục thường xuyên trong cơ sở dữ liệu lớn thông qua mẫu đại diện

THUẬT TOÁN KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN TRONG CƠ SỞ DỮ LIỆU LỚN THÔNG QUA MẪU ĐẠI DIỆN Nguyễn Hưng Long Khoa Hệ thống thông tin kinh tế và Thương mại điện tử, Đại học Thương mại Nguyễn Minh Hoàng Khoa Toán - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội Tóm tắt Bài viết đề xuất thuật toán RSFPGrowth khai phá tập mục thường xuyên trong cơ sở dữ liệu lớn thông qua mẫu đại diện. Thuật toán RSFPGrowth cho phép thay vì tìm tập tất cả các tập mục thường xuyên trong cơ sở dữ liệu lớn bằng cách tìm tập chứa hầu hết các tập tập mục thường xuyên từ tập mẫu đại diện các giao tác. Bởi vì khi cỡ mẫu n cần lấy cho tập mẫu sẽ tăng chậm so với cỡ tổng thể nên độ hiệu quả của việc khai phá tập tập mục thường xuyên thông qua lấy mẫu đại diện các giao tác sẽ càng cao khi kích thước của cơ sở dữ liệu ban đầu càng lớn. Từ khóa: Khai phá dữ liệu, tập mục thường xuyên, cơ sở dữ liệu, mẫu đại diện, FP- Growth 1. Mở đầu Trong những năm gần đây, khai phá dữ liệu (KPDL) đã trở thành đề tài thu hút sự quan tâm của nhiều nhà nghiên cứu và đã được ứng dụng thành công trong mọi mặt của đời sống - xã hội. Khai phá dữ liệu được định nghĩa là quá trình trích lọc không tầm thường những thông tin hữu ích chưa biết từ các cơ sở dữ liệu (CSDL) lớn (có chứa đến hàng vạn, triệu các giao tác). Khai phá tập mục thường xuyên (TMTX) được biết đến như là bài toán con của bài toán khai phá dữ liệu và đã được giới thiệu lần đầu tiên vào năm 1993 bởi Agrawal R. và Srikant R. [5, 6], thuộc Trung tâm nghiên cứu Almaden của IBM (Mỹ), nhằm phân tích CSDL bán hàng tại siêu thị. Qua quá trình phân tích sẽ giúp cho nhà phân tích lựa chọn các phương án tốt nhất trong hoạt động kinh doanh của siêu thị. Để giải quyết bài toán này, các tác giả đề xuất thuật toán Apriori. Tại hội nghị quốc tế về khai phá dữ liệu vào tháng 12 năm 2006 đã đánh giá thuật toán Apriori đứng trong top 10 thuật toán khai phá dữ liệu [9]. Hiện đã có nhiều nghiên cứu, xây dựng các thuật toán khai phá TMTX được dựa trên thuật toán Apriori (gọi là các thuật toán kiểu Apriori). Thuật toán Apriori và các thuật toán kiểu Apriori có hai nhược điểm lớn: Phải sinh ra khối lượng khổng lồ các tập ứng viên và duyệt CSDL giao tác nhiều lần. TMTX là công cụ hiệu quả để khai phá các luật kết hợp (association rule), tập mục đóng (closed itemset), tập mục tuần tự (sequential itemset), các phụ thuộc hàm (functional dependencies), ... Để khắc phục hạn chế của thuật toán Apriori, Han J. và cộng sự [7, 8] tại Trường Đại học Simon Fraser (Canada) đã đề xuất thuật toán FP-growth. Thuật toán FP-growth khai phá TMTX được xây dựng dựa trên những kĩ thuật cơ bản sau: (1) Nén toàn bộ CSDL giao tác lên một cấu trúc cây, gọi là cây FP-tree, nhờ đó giảm chi phí cho số lần duyệt CSDL giao tác trong quá trình khai phá. (2) Dùng phương pháp chia để trị (devide- 285
and-conquer), bằng cách trong quá trình xây dựng và khai phá dữ liệu được chia làm thành các bài toán nhỏ hơn, theo nghĩa xây dựng các cây FP-tree có điều kiện và khai phá các TMTX trên các cây FP-tree có điều kiện đã được tạo ra. Do vậy, quá trình khai phá cây được phát triển dần các mẫu mà không sinh ra nhiều các tập mục ứng viên và nó sẽ làm giảm khối lượng thời gian tính toán. Quá trình khai phá TMTX được thực hiện theo hai pha: Pha xây dựng cây FP-tree và pha khai phá cây FP-tree bằng thuật toán FP-growth. Mặc dù thuật toán FP-growth có những ưu điểm (về tổ chức dữ liệu, bộ nhớ, thời gian tính toán) hơn thuật toán Apriori nhưng đối với CSDL giao tác lớn cần khai phá sẽ không hiệu quả. Để có thể áp dụng thuật toán FP-growth trên các CSDL kích thước lớn, trong bài viết này chúng tôi trình bày một phương pháp tiếp cận xấp xỉ. Thay vì tìm tập TMTX trong CSDL cần khai phá, ta sẽ tìm tập chứa hầu hết các tập mục từ CSDL mẫu đại diện. Độ hiệu quả của việc khai phá thông qua lấy mẫu sẽ càng cao khi kích thước của CSDL ban đầu càng lớn, bởi vì cỡ mẫu n cần lấy tăng chậm so với cỡ tổng thể. Nội dung tiếp theo của bài viết là như sau: Mục 2 giới thiệu về mô hình bài toán và thuật toán FP-Growth khai phá TMTX trong CSDL giao tác; Mục 3 trình bày phương pháp tiếp cận xấp xỉ: khai phá TMTX thông qua khai phá mẫu đại diện và cuối cùng là kết luận. 2. Khai phá tập mục thường xuyên trong csdl giao tác và thuật toán fp-growth 2.1. Bài toán khai phá tập mục thường xuyên trong CSDL giao tác [5, 6] Định nghĩa 1. Cho I= {i , i , … , i } là tập các phần tử. Mỗi phần tử trong I được gọi là một mục (item). Một tập con X ⊆ Iđược gọi là một tập mục (itemset). Số phần tử trong X kí hiệu là Card(X). Nếu Card(X) = k, (k ∈ Z) thì X được gọi là k-tập mục. Nếu Card(X)=1 thì X là 1-tập mục hay còn được gọi là mục đơn. Để đơn giản, thay vì viết k-tập mục {i , i , … , i } đôi khi ta viết i i … i . Chẳng hạn, tập mục {a, b, c} được viết ngắn gọn là abc. Định nghĩa 2. Một giao tác (transaction) là một bộ T = 〈TID , X〉, với TID là định danh giao tác (transaction identifier) duy nhất và X ⊆ Ilà một tập mục. Giao tác T gọi là chứa tập mục Y nếu Y ⊆ T. Định nghĩa 3. CSDL giao tác (transaction database) là một tập các giao tác TDB = {T , T , … , T }. Biểu diễn CSDL giao tác ngang : CSDL là một tập các giao tác. Trong đó, mỗi giao tác bao gồm một định danh (thứ tự) TID và một danh sách các mục. Ví dụ. Trong Bảng 1 dưới đây là biểu diễn ngang của CSDL giao tác. Bảng 1. Biểu diễn ngang của CSDL giao tác TID Tập các mục T1 abcdef T2 bcefh T3 acdefgh 286
Định nghĩa 4. Cho I= {i , i , … , i } là tập các mục và tập mục X ⊆ I. Ta gọi độ hỗ trợ (support) của X trong CSDL giao tác DT được ký hiệu supp(X), là tỷ lệ phần trăm các giao tác trong DT chứa X, tức là: card({T ∈ DT|X ⊆ T}) supp(X) = card(DT) Với card(TDB) là số các giao tác của DT. Ta có: 0 ≤ supp(X) ≤ 1, ∀X ⊆ I . Định nghĩa 5. Cho tập mục X ⊆ Ivà ngưỡng độ hỗ trợ tối thiểu minsupp (minimum support) được xác định bởi người dùng, 0 < minsupp ≤ 1. Nếu supp(X) ≥ minsupp thì X được gọi là TMTX (frequent itemset) với độ hỗ trợ tối thiểu minsupp, hay ta nói X thỏa minsupp, trường hợp ngược lại ta nói X là tập không thường xuyên (infrequent itemset), hay ta nói X không thỏa minsupp. 2.2. Thuật toán FP-growth Nội dung thuật toán FP-growth [7, 8] với ý tưởng chính như sau: - Nén toàn bộ các giao tác lên một cấu trúc cây, gọi là cây FP-tree, nhờ đó giảm chi phí cho số lần duyệt CSDL giao tác. Mỗi nút trong cây FP-tree có một mục, các nút chúng được sắp xếp để tiện cho việc chèn các giao tác lên cây và các nút xuất hiện thường xuyên dễ dàng chia sẻ với các nút ít xuất hiện hơn, đồng thời các nút không thường xuyên sẽ bị sớm loại bỏ mà không làm ảnh hưởng kết quả khai phá. Bước này chỉ cần duyệt CSDL giao tác một lần. - Áp dụng phương pháp chia để trị (devide and conquer). Quá trình khai phá dữ liệu được chia làm thành các phần việc nhỏ hơn, ở đó tiến hành xây dựng các cây FP- tree có điều kiện và khai phá các TMTX trên các cây FP-tree có điều kiện đã được tạo ra. Do vậy, quá trình khai phá cây được phát triển dần các mẫu mà không sinh ra nhiều tập mục ứng viên và đồng thời sẽ làm giảm khối lượng tính toán. Bước xây dựng cây FP-tree chỉ cần duyệt thêm một lần trên CSDL giao tác. - Quá trình khai phá thực hiện theo hai pha chính: (1) Xây dựng cấu trúc cây FP- tree; (2) Khai phá cây FP-tree bởi thuật toán FP-growth. 3. Khai phá tập mục thường xuyên thông qua mẫu đại diện Thuật toán FP-growth có ưu điểm hơn thuật toán Apriori [7], nhưng nếu khai thác trên các CSDL lớn thì thuật toán FP-growth sẽ không hiệu quả. Để áp dung thuật toán FP-growth trên các CSDL lớn chúng tôi đề nghị phương pháp tiếp cận xấp xỉ. Thay vì tìm tập tất cả cácTMTX trong CSDL cần khai phá, ta sẽ tìm tập chứa hầu hết các tập mục này từ CSDL mẫu đại diện [1, 2, 3] Trên thực tế các đối tượng cùng loại mà các nhà thống kê quan tâm nghiên cứu được gọi là tổng thể. Tổng thể thường bao gồm một số lượng lớn, có khi rất lớn các đối tượng. Nghiên cứu toàn bộ đối tượng trong tổng thể là việc làm khó khăn hoặc không thể thực hiện được, chưa kể là có khi không có nghĩa. Vì vậy người ta thường dùng phương pháp chọn mẫu, tức là từ một tổng thể có N đối tượng (N được gọi là kích thước của tổng thể) rút ra n đối tượng (n được gọi là kích thước mẫu), tiến hành nghiên cứu trên mẫu đó rồi căn cứ vào kết quả thu được mà suy rộng ra cho tổng thể. Các kết quả suy rộng này không thể tránh khỏi những sai lệch. Độ lớn của các sai lệch phụ thuộc 287
vào hai yếu tố cơ bản là phương pháp chọn mẫu và kích thước mẫu. Vì vậy, vấn đề quan trọng là làm sao đảm bảo cho mẫu phải phản ánh đúng đắn cấu trúc của tổng thể, tức là mẫu phải mang tính đại diện để cho sai lệch do chọn mẫu càng nhỏ càng tốt. Kích thước mẫu càng lớn, thì tính đại diện của mẫu càng cao, tuy nhiên khi đó chi phí cũng sẽ càng lớn [1, 2, 3]. Trong thực hành, tùy vào tình huống cụ thể, người ta có thể áp dụng những phương pháp chọn mẫu khác nhau. Mỗi phương pháp đều có ưu điểm và nhược điểm riêng. Có một số phương pháp chon mẫu sau: Chọn mẫu ngẫu nhiên đơn giản (Simple Random Sampling); Chọn mẫu ngẫu nhiên phân vùng (Stratified Random Sampling); Chọn mẫu có hệ thống (Systematic Sampling); ... [1, 2, 3] Để chọn mẫu khai phá dữ liệu, người ta thường sử dụng phương pháp chọn mẫu ngẫu nhiên đơn giản (không hoàn lại), vì những lý do sau: (1) Dễ mô phỏng và cài đặt. (2) Việc chọn mẫu ngẫu nhiên đơn giản có thể mô phỏng và thực hiện bằng cách sử dụng các thuật toán (hàm) tạo số ngẫu nhiên. (3) Ước lượng tỷ lệ dựa trên mẫu ngẫu nhiên đơn giản là ước lượng không chệch. (4) Không cần có bất kỳ một thông tin tiên nghiệm nào về quần thể [1, 2, 3]. 3.1. Xác định cỡ mẫu trong cơ sở dữ liệu giao tác Tư tưởng chính của thuật toán là như sau: Trước tiên, từ CSDL giao tác ban đầu, chọn một mẫu ngẫu nhiên đơn giản các giao tác. Sau đó, áp dụng thuật toán FP-growth [7, 8] khai phá TMTX trên CSDL mẫu. Trong [1, 4] đã phân tích, chỉ ra việc chọn mẫu ngẫu nhiên đơn giản như dưới đây: Xác định cỡ mẫu Giả sử CSDL DT bao gồm N giao tác, trong đó có SC(DT,X) giao tác chứa tập mục X. Khi đó xác suất để một giao tác chứa X là p=sup(X)=SC(DT,X)/N. Ký hiệu S là mẫu gồm n giao tác được chọn lần lượt bằng phương pháp chọn ngẫu nhiên không hoàn lại từ DT. Gọi SC(S,X) là số giao tác trong S chứa tập mục X . Khi đó SC(S,X) tuân theo luật phân phối siêu bội với hàm xác suất: Pr ( , ) = )= , = 0,1, … , (1) Giá trị kỳ vọng, phương sai của SC(S,X) lần lượt là [1]: ( , ) = (2) ( , ) = 1− (1 − ) ≈ 1 − (1 − ) (3) Với mẫu cỡ n, người ta thường lấy ̂ = ( , )/ làm giá trị ước lượng cho xác suất p (tức support(DT,X)). Từ (2) và (3) suy ra: ( ̂) = (4) ( ) ( ) ( ̂) = 1 − ≈ 1− (5) Vì E(p) = p, ̂ là một ước lượng không chệch của p. Trong [1] đã chứng minh được rằng, khi n đủ lớn (n>=30), đại lượng ngẫu nhiên chuẩn hóa 288
= ( ) (6) sẽ có phân phối tiệm cận phân phối chuẩn chuẩn tắc (0,1) với hàm phân phối: ( )= ∫ (7) √ Giả sử với sai số tuyệt đối d và xác suất rủi ro α cho trước, ta muốn ước lượng xác suất p bằng p sao cho (| − ̂ | < ) = 1 − (8) Ký hiệu z là phân vị mức 1 − α 2 của đại lượng Z có phân phối (3.7), nghĩa là z là giá trị thỏa mãn hệ thức: < =1− (9) Khi đó | |< =1− (10) Kết hợp các hệ thức (6), (8) và (9) suy ra, nếu muốn ước lượng p với sai số tuyệt đối d và xác suất rủi ro α cho trước thì cỡ mẫu n phải thỏa hệ thức: ( ) = 1− (11) ( ) Hay = ( ) (12) Trong công thức (11), p là giá trị chưa biết, cần ước lượng. Tuy vậy, vì tích p(1- p) đạt cực đại là 1/4 khi p=1/2, ta có thể lấy ( ) = max ( ) = (13) Do cỡ mẫu là số nguyên, nên lấy = (14) 3.2. Thuật toán khai phá TMTX trong CSDL giao tác thông qua mẫu đại diện 3.2.1. Ý tưởng chính Với cỡ mẫu n xác định theo (14), việc lấy mẫu S từ CSDL giao tác DT được tiến hành như sau: - Đánh số thứ tự tất cả các giao tác trong DT. - Tạo n số nguyên ngẫu nhiên khác nhau trong khoảng [1, N], - Lấy CSDL mẫu S là tập n giao tác có số thứ tự là các số nguyên ngẫu nhiên đã tạo được. Trong thực hành, sai số tuyệt đối d và rủi ro thường được chọn tương ứng là 0.05 và 0.01. 289
3.2.2. Thuật toán RSFPGrowth Bảng 2. Bảng các kí hiệu trong thuật toán RSFPGrowth Ký hiệu Ý nghĩa DT CSDL giao tác ban đầu minsupp Độ hỗ trợ tối thiểu Z Phân vị mức 1 − /2 của phân phối chuẩn chuẩn tắc (tức là giá trị của (0,1))  Độ rủi ro d Cận trên của sai số N Tổng số giao tác trong CSDL ban đầu n Cỡ mẫu S Tập các giao tác được chọn vào mẫu Nội dung thuật toán RSFPGrowth khai phá TMTX trên CSDL mẫu như sau: Input: CSDL DT, tổng số giao tác N trong CSDL giao tác, cỡ mẫu n, hai ngưỡng hỗ trợ minsupp, cận trên của sai số d, độ rủi ro . Output: Tập các TMTX. Method: Thuật toán RSFPGrowth 1) if n>=30 2) 3) { 4) z = Calculate(); 5) = 6) for (i = 1; i
15) end. Các thủ tục trong RSFPGrowth là như sau: Calculate(): Tính = là phân vị mức 2 của phân phối chuẩn tắc (0,1). GenRandom(N): Tạo số nguyên ngẫu nhiên trong khoảng từ 1 đến N. sort(a): Sắp xếp các phần tử của mảng a theo thứ tự giá trị tăng dần. execute FP-Growth: Thực hiện thủ tục FPGRowth trên CSDL mẫu S. 3.2.3. Ví dụ Để đơn giản cho quá trình xử lí tính toán của ví dụ. Trong ví dụ này chúng tôi giả sử có một CSDL lớn và sau khi chọn mẫu xong, đánh số định danh các giao tác ta được CSDL giao tác gồm 10 giao tác như trong bảng 3 dưới đây: Bảng 3. Bảng CSDL giao tác TID Tập các mục 1 acdef 2 bcf 3 abcde 4 def 5 ade 6 abce 7 cdef 8 abcde 9 ace 10 acde Hãy tìm TMTX từ CSDL giao tác trên với ngưỡng độ hỗ trợ tối thiểu minsupp=5. Quá trình thực hiện thuật toán FP-growth được mô tả như hai pha dưới đây. Pha 1: Xây dựng cây FP-tree. Ý tưởng chính: Duyệt một lần CSDL giao tác để tính độ hỗ trợ của các mục đơn, loại bỏ các mục đơn không thỏa mãn ngưỡng độ hỗ trợ tối thiểu minsupp. Tiếp đến, duyệt lại một lần CSDL giao tác, loại bỏ các mục không thường xuyên trong các giao tác và sắp xếp các mục theo thứ tự giảm dần của độ hỗ trợ, sau đó chèn lần lượt các giao tác lên cây FP-tree. Duyệt CSDL lần thứ nhất, tính độ hỗ trợ của các mục đơn, ta có: SC(a) = 7; SC(b) = 8; SC(c) = 6; SC(d) = 2; SC(e) = 3. 291
Mục “d” bị loại do không thỏa minsupp=3. Vậy L = {a, b, c, e}. Sắp xếp các mục theo thứ tự giảm dần của độ hỗ trợ được bảng 4: Bảng 4. Các mục đơn sau khi đã sắp xếp giảm dần theo độ hỗ trợ Các mục SC b 8 a 7 c 6 e 3 d 2 Duyệt CSDL giao tác lần thứ hai, loại bỏ các mục không thường xuyên trong các giao tác và sắp xếp lại các mục theo thứ tự giảm dần của độ hỗ trợ ta được bảng 8. Chèn các giao tác Bảng lên cây FP-tree, ta thu được cây bởi hình 1. Bảng 5. Sắp xếp các 1-tập mục thường xuyên theo thứ tự giảm dần TID Tập các mục 1 bae 2 bace 3 bc 4 ba 5 ac 6 bc 7 ac 8 b 9 bac 10 bae 292
Hình 8. Cây FP-tree sau khi chèn các giao tác của bảng 6 Pha 2: Khai phá cây FP-tree bởi thuật toán FP-growth. Ý tưởng chính: Xét trong bảng đầu mục của cây FP-tree lần lượt các mục từ dưới lên, với mỗi mục xây dựng cây điều kiện, khai phá cây điều kiện cho mục này, loại bỏ cây điều kiện sau khi khai phá xong. Xây dựng, khai phá và loại bỏ cây điều kiện cho mục tiếp theo. Quá trình sẽ kết thúc sau khi xét tất cả các mục trong bảng đầu mục. Qui trình thực hiện xây dựng, khai phá cây FP-tree xét lần lượt các mục “e”, “c”, “a”, “b” (theo thứ từ dưới lên trong bảng đầu mục). - Xây dựng và khai phá cây điều kiện của “e”: CSDL điều kiện của “e” bao gồm các nhánh tiền tố {bac: 1; ba: 2}. Từ CSDL điều kiện ta có cây FP-tree cho mục “e” trong hình 2 Hình 2. Cây FP-tree(e) Từ bảng đầu mục ta có 2-tập mục ứng viên xuất hiện cùng với “e” và độ hỗ trợ tương ứng là 〈ae: 3; be: 3; ce: 1〉. Tập mục “ce” không thỏa minsupp. Nhập “ae” và “be” vào L, ta được L = {a, b, c, e, ae, be}. Tiếp tục khai phá bằng cách phát triển dần 2-tập mục “ae” và “be”. Khai phá cây điều kiện của “ae”, có một 3-tập mục ứng viên “bae” với độ hỗ trợ 3 thỏa minsupp. 293
Hình 3. Cây FP-tree(ae) Khai phá cây điều kiện của “be”, thu được cây rỗng. Vậy ta thu được L = {a, b, c, d, e, ae, be, bae}. Xóa tất cả các nút “e” trên cây FP-tree và cây điều kiện của “e”. - Xây dựng và khai phá cây điều kiện của “c”: CSDL điều kiện của “c” bao gồm các nhánh tiền tố {ba: 2; b: 2, a: 2}. Từ CSDL điều kiện ta có cây FP-tree cho mục “c” trong hình 4. Hình 4. Cây FP-tree(c) Từ bảng đầu mục ta có các 2-tập mục ứng viên xuất hiện cùng với “c” và độ hỗ trợ tương ứng là 〈ac: 4; bc: 4〉, đều thỏa minsupp được nhập vào L. Tiếp tục khai phá cây điều kiện của “ac”, thu được một 3-tập mục “bac” với độ hỗ trợ là 2, không thỏa minsupp, khai phá cây điều kiện của “bc” ta thu được cây rỗng. Vậy ta được L = {a, b, c, e, ae, be, bae, ac, bc}. Xóa tất cả các nút “c” trên cây FP-tree và cây điều kiện của “c”. - Xây dựng và khai phá cây điều kiện của “a”: CSDL của “a” có một nhánh tiền tố {b: 5}. Ta có cây FP-tree cho mục “a” như hình 5. Hình 5. Cây FP-tree(a) Dễ thấy chỉ có một 2-tập mục ứng viên “ba” với độ hỗ trợ trợ là 5, thỏa mãn minsupp. Khai phá cây điều kiện của tập mục “ba” được cây rỗng. Vậy ta được L = {a, b, c, e, ae, be, bae, ac, bc, ba}. Xóa tất cả các nút “a” trên cây FP-tree và cây điều kiện của “a”. - Xây dựng và khai phá cây điều kiện của “b”: Ta thu được cây rỗng. 294
Cuối cùng ta thu được TMTX cùng với độ hỗ trợ như sau: L = {a: 7, b: 8, c; 6, e: 3, ae: 3, be: 3, bae: 3, ac: 4, bc: 4, ba: 5}. Kết luận Trong bài viết này chúng tôi đề xuất thuật toán RSFPGrowth khai phá TMTX trong CSDL lớn thông qua mẫu đại diện. RSFPGrowth cho phép thay vì tìm tập tất cả các TMTX trong CSDL lớn bằng cách tìm tập chứa hầu hết các TMTX từ tập mẫu đại diện các giao tác. Độ hiệu quả của việc khai phá thông qua lấy mẫu sẽ càng cao khi kích thước của CSDL ban đầu càng lớn, bởi vì cỡ mẫu n cần lấy tăng chậm so với cỡ tổng thể. Thuật toán RSFPGrowth là công cụ hiệu quả để khai phá các luật kết hợp (association rule), tập mục đóng (closed itemset), tập mục tuần tự (sequential itemset), các phụ thuộc hàm (functional dependencies), ... Thuật toán RSFPGrowth có thể áp dụng cho các bài toán khác nhau trong thực tiễn như: phân tích đầu tư chứng khoán, phân tích giỏ hàng của siêu thị, phân tích các dòng kích hoạt web, ... Tài liệu tham khảo [1] Trần Tuấn Điệp, Lý Hoàng Tú (2003). Giáo trình lý thuyết xác suất và thống kê toán học, NXB Giao thông Vận tải, Hà Nội. [2] Trần Doán Phú (2008), Lý thuyết xác suất và Thồng kê toán, NXB Thống kê. [3] Đặng Hùng Thắng (2009), Thống kê và ứng dụng, NXB Giáo dục [4] Nguyễn Hưng Long (2012), Khai phá tập mục thường xuyên thông qua mẫu đại diện, Kỷ yếu Hội thảo quốc gia lần thứ XV, Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông – Hà Nội, 03-04/12/2012. [5] Aggarwal, C. In C. Aggarwal (Ed.) (2007), Data Streams: Models and algorithms. Springer, [6] Agrawal R., Srikant, R., (1994), Fast Algorithms for Mining Association Rules. In: 20th Int. Conf. on Very Large Data Bases (VLDB), pp. 487–499. [7] Han J., and Kamber M. (2000), Data Mining: Concepts and Techniques, Morgan Kanufmann. [8] Han J., Pei J., Yin Y., Mao R., (2004), Mining frequent patterns without candidate generation: a frequent-pattern tree approach, Data Mining and Knowledge Discovery 8, pp. 53–87,. [9] Wu X, Kumar V., Ross Q. J., Ghosh J., Yang Q., Motoda H., McLachlan G. J., Angus Ng., Liu B., Yu P. S., Zhou Z. H., Steinbach M., Hand D. J., Steinberg D., (2008), Top 10 algorithm in data mining, Knowledge and Information Systems, pp. 1-37. 295