Thuật toán khai phá mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 14 (34), tháng 12/2015<br /> <br /> <br /> Thuật toán khai phá mẫu dãy thƣờng xuyên trọng số<br /> chuẩn hóa với khoảng cách thời gian<br /> Mining Normalized Weighted Frequent Sequential Patterns with Time Intervals<br /> Algorithm<br /> Trần Huy Dƣơng, Vũ Đức Thi<br /> <br /> Abstract: In this paper, we propose a method for hướng cải tiến nhằm giảm thiểu chi phí thời gian và tài<br /> mining normalized weighted frequent sequential nguyên hệ thống.<br /> patterns with time intervals, we are not only interested Các thuật toán kể trên khai phá mẫu dãy chỉ quan<br /> in the number of occurrences of the sequence (the tâm đến số lần xuất hiện (hay độ hỗ trợ) của các mẫu<br /> support), but also concerned about their levels of dãy; thuật toán do Hirate và Yamana [10] đề xuất cho<br /> importance (weighted). We use the binding between phép khai phá các mẫu dãy có quan tâm đến giá trị của<br /> the support and weight of the set range to candidates khoảng cách thời gian giữa các dãy. Tuy nhiên, các<br /> in mining normalized weighted frequent sequential thuật toán này cơ bản chưa quan tâm đến sự ràng buộc<br /> patterns with time intervals while maintaining the giữa khoảng cách thời gian giữa các dãy và mức độ<br /> downward closure property nature which allows a quan trọng khác nhau của các mục dữ liệu. Vì vậy, bài<br /> balance between support and the weight of a báo nhằm đề xuất một phương pháp khai phá mẫu dãy<br /> sequence. trọng số chuẩn hóa với khoảng cách thời gian, chúng<br /> Keywords: Data mining, frequent sequential tôi không chỉ quan tâm đến số lần xuất hiện của các<br /> patterns, time intervals, weighted, sequential patterns. dãy (độ hỗ trợ) mà còn quan tâm đến khoảng cách thời<br /> gian giữa các dãy và mức độ quan trọng khác nhau<br /> I. GIỚI THIỆU (trọng số) của chúng. Chúng tôi sử dụng tính chất ràng<br /> Khai phá mẫu dãy (Mining Sequential Patterns) là buộc giữa độ hỗ trợ, khoảng cách thời gian và trọng số<br /> một trong những lĩnh vực rất quan trọng trong nghiên của dãy để sinh các tập ứng viên trong khai phá mẫu<br /> cứu khai phá dữ liệu và được áp dụng trong nhiều lĩnh dãy thường xuyên trọng số chuẩn hóa với khoảng cách<br /> vực khác nhau. Trong thực tế các dữ liệu dãy tồn tại thời gian trong khi vẫn sử dụng tính chất phản đơn<br /> rất phổ biến như dãy dữ liệu mua sắm của khách hàng, điệu cho phép cân bằng độ hỗ trợ, khoảng cách thời<br /> dữ liệu điều trị y tế, nhật ký truy cập web, v.v... Mục gian và trọng số của một dãy.<br /> đích chính của khai phá mẫu dãy là phát hiện tất cả Phần còn lại của bài báo như sau: Phần II trình bày<br /> các dãy con xuất hiện lặp lại trong một CSDL theo các nghiên cứu liên quan. Phần III trình bày bài toán<br /> yếu tố thời gian. và đề xuất thuật toán khai phá mẫu dãy thường xuyên<br /> Hiện nay trên thế giới có nhiều nhóm tác giả trọng số chuẩn hóa với khoảng cách thời gian<br /> nghiên cứu đề xuất các thuật toán với các phương WIPrefixSpan dựa trên giải thuật khai phá mẫu dãy<br /> pháp tiếp cận khai phá mẫu dãy khác nhau như thường xuyên PrefixSpan [3] và thuật toán do Hirate<br /> AprioriAll [1], GSP [2], PrefixSpan [3], SPADE [4], và Yamana [10] đề xuất. Phần IV trình bày kết quả<br /> SPAM [5], CloFS-DBV [13] v.v... nhằm giải quyết sự thực nghiệm và so sánh giải thuật đề nghị<br /> đa dạng của các loại bài toán cũng như đưa ra các (WIPrefixSpan), WPrefixSpan [11] và giải thuật<br /> IPrefixSpan[10] trên bộ dữ liệu BMS-WebView. Kết<br /> - 72 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 14 (34), tháng 12/2015<br /> <br /> <br /> luận và hướng phát triển được thể hiện trong phần (t1,3,s3),..., (t1,m,sm)} với sj I trong đó (1 ≤ j ≤ m) là<br /> cuối. một tập mục được gọi là thành phần của dãy và sj có<br /> II. CÁC NGHIÊN CỨU LIÊN QUAN dạng (i1i2… ik) và it là một mục dữ liệu thuộc I, và t,<br /> là khoảng cách thời gian giữa dãy s và s. Một dãy Sm<br /> Năm 1995, Agrawal và Srikant phát triển bài toán<br /> khai phá mẫu dãy phổ biến [1] và đề nghị thuật toán bị loại nếu chỉ có duy nhất một mục dữ liệu it I. Một<br /> AprioriAll một thuật toán dựa trên thuật toán Apriori mục dữ liệu chỉ xuất hiện 1 lần trong thành phần của<br /> để khai thác mẫu dãy phổ biến. Cũng giống như sj, nhưng có thể xuất hiện nhiều lần trong các thành<br /> Apriori, AproiriAll quét CSDL nhiều lần và dựa vào phần của một dãy Sm.<br /> phương pháp sinh ứng viên nên tốn thời gian khai phá. Kích thước |Sm| của một dãy là số lượng của các<br /> Năm 2001, Pei và các đồng sự đề nghị thuật toán thành phần trong dãy Sm. Độ dài l(Sm) của dãy là tổng<br /> PrefixSpan [3], một thuật toán dựa trên phương pháp số mục dữ liệu trong dãy Sm. Một cơ sở dữ liệu dãy S<br /> phát triển mẫu dãy. Thuật toán không phải quét CSDL = {S1, S2, …, Sn} là một tập các bộ dữ liệu (sid,Sk) với<br /> nhiều lần nên thời gian khai phá giảm đi đáng kể so sid là định danh của một dãy và Sk là một dãy dữ liệu<br /> với AprioriAll [1]. Các thuật toán sau đó được phát có dạng {(t1,1,s1), (t1,2,s2), (t1,3,s3),..., (t1,m,sm)}.<br /> triển nhằm tối ưu hóa quá trình khai phá mẫu dãy có Định nghĩa 1. (Dãy dữ liệu có khoảng cách thời<br /> thể kể đến như SPADE [4], SPAM [5]. gian): Một dãy dữ liệu có khoảng cách thời gian có<br /> Ngoài ra, các kỹ thuật dựa trên chuỗi bit động để dạng:<br /> khai phá mẫu dãy đóng cũng được đề nghị trong [13]. Sm = (1)<br /> Đối với khai phá mẫu trên CSDL có trọng số thì Với t,, là khoảng cách thời gian giữa dãy s và s có<br /> các thuật toán khai phá mẫu dãy nêu trên không quan dạng:<br /> tâm tới mức độ quan trọng của từng mẫu (trọng số của<br /> mẫu). Trên thế giới có nhiều tác giả đã nghiên cứu về t, = s.time - s.time (2)<br /> trọng số, có thể kể đến là các công trình khai phá tập Định nghĩa 2. (Độ hỗ trợ của một dãy) : Độ hỗ<br /> mục có trọng số [6-9], [14-16], mẫu dãy có trọng số trợ của một dãy Sa trong một cơ sở dữ liệu dãy S là số<br /> [12,15]. Các thuật toán [12,15] tuy khai phá mẫu dãy lượng xuất hiện các bản ghi trong S có chứa dãy Sa .<br /> trên CSDL có trọng số nhưng chưa quan tâm đến các<br /> ràng buộc giữa trọng số, độ hỗ trợ và khoảng cách thời Định nghĩa 3. (Trọng số chuẩn hóa của dãy):<br /> gian của dãy. ChoI={i1, i2, …, in} là tập hợp các mục dữ liệu. Mỗi<br /> mục ijI được gán một trọng số wj, j = 1,...,n. Khi đó<br /> III. KHAI PHÁ MẪU DÃY THƢỜNG XUYÊN trọng số chuẩn hóa của một dãy  = có độ dài k và sj có dạng (i1i2…<br /> THỜI GIAN ik) được tính bằng công thức:<br /> III.1. Các thuật ngữ mô tả bài toán<br /> () ∑  (3)<br /> Cho I = {i1, i2, …, in} là tập hợp các mục dữ liệu.<br /> Mỗi mục ij I được gán một trọng số wj với giá trị Định nghĩa 4. (Độ hỗ trợ với trọng số chuẩn hóa<br /> j=1,...,n. của dãy):<br /> <br /> Một dãy Sm là một danh sách được sắp xếp theo Ta gọi đại lượng NWsupport() của dãy  là độ hỗ<br /> thứ tự của các mục dữ liệu dạng {(t1,1,s1), (t1,2,s2), trợ với trọng số chuẩn hóa của dãy :<br /> - 73 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 14 (34), tháng 12/2015<br /> <br /> <br /> () () () xuyên trọng số chuẩn hóa với khoảng cách thời<br /> ( ∑ ) () (4) gian trong S, tức là tìm tập L:<br /> <br /> L = {Sa ⊆ S | NWsupport(Sa )  wminsup và t, thỏa<br /> Định nghĩa 5. (Ràng buộc khoảng cách thời<br /> gian): Cho một dãy < (t1,1,s1), (t1,2,s2), (t1,3,s3),..., mãn tính chất các ràng buộc C1, C2, C3, C4} (6)<br /> (t1,m,sm)>, các ràng buộc khoảng cách thời gian giữa  Mẫu dãy thường xuyên trọng số chuẩn hóa với<br /> các dãy được định nghĩa theo [10]: khoảng cách thời gian không thỏa mãn tính chất<br /> phản đơn điệu, nghĩa là tập con của một mẫu dãy<br />  C1 = min_time_interval là giá trị nhỏ nhất giữa<br /> thường xuyên trọng số chuẩn hóa với khoảng<br /> hai dãy liền kề, tức là ti,i+1  min_time_interval.<br /> cách thời gian không nhất thiết phải là mẫu dãy<br />  C2 = max_time_interval là giá trị lớn nhất giữa thường xuyên trọng số chuẩn hóa với khoảng<br /> hai dãy liền kề, tức là ti,i+1 ≤ max_time_interval. cách thời gian.<br /> <br />  C3 = min_whole_interval là giá trị nhỏ nhất III.2. Cơ sở toán học<br /> giữa dãy đầu và dãy cuối, tức là ti,m  Chúng tôi đề xuất một thuật toán khai phá mẫu dãy<br /> min_whole_interval. thường xuyên trọng số chuẩn hóa với khoảng cách<br /> thời gian (WIPrefixSpan), trong đó các Định nghĩa 7,<br />  C4 = max_whole_interval là giá trị lớn nhất<br /> 8, 9 dựa trên giải thuật khai phá mẫu dãy thường<br /> giữa dãy đầu và dãy cuối, tức là ti,m ≤<br /> xuyên PrefixSpan [3] và của Hirate vàYamana[10] với<br /> max_whole_interval.<br /> cách tiếp cận chính là tìm cách đưa các ràng buộc<br /> Định nghĩa 6. (Mẫu dãy thƣờng xuyên trọng số trọng số, ràng buộc khoảng cách thời gian và độ hỗ trợ<br /> chuẩn hóa với khoảng cách thời gian): Cho một trong thuật toán khai phá mẫu dãy đảm bảo tính chất<br /> CSDL dãy S có khoảng cách thời gian giữa các dãy, phản đơn điệu.<br /> mỗi mục ij⊆ I được gán một trọng số wj, một ngưỡng Để tránh phải thực hiện kiểm tra tất cả khả năng<br /> hỗ trợ tối thiểu wminsup, các ràng buộc khoảng cách kết hợp của một dãy các ứng cử viên tiềm năng, ta có<br /> thời gian C1, C2, C3, C4. Một dãy  được gọi là mẫu thể thay thế các thứ tự của các mục dữ liệu trong từng<br /> dãy thường xuyên trọng số chuẩn hóa với khoảng cách thành phần trong dãy. Khi đó các mục trong một thành<br /> thời gian nếu thỏa mãn tính chất: phần của một dãy có thể được liệt kê theo 1 trật tự mà<br /> không mất tính tổng quát và có thể giả định rằng thứ<br /> NWSupport()  wminsup và t, thỏa mãn tính<br /> tự này luôn luôn được liệt kê theo thứ tự bảng chữ cái.<br /> chất các ràng buộc C1, C2, C3, C4 (5)<br /> Ví dụ như dãy < (0,a) (1,acb) (2,ac) > thể hiện<br /> Khi đó bài toán khai phá mẫu dãy thường xuyên thông tin đi siêu thị của khách hàng, tại thời điểm 0 thì<br /> trọng số chuẩn hóa với khoảng cách thời gian được khách hàng mua mặt hàng a, thời điểm 1 thì khách<br /> phát biểu như sau: hàng mua các mặt hàng a,c,b và thời điểm 2 thì khách<br />  Cho một CSDL dãy S có khoảng cách thời hàng mua các mặt hàng a,c. Khi đó, việc thể hiện dãy<br /> gian giữa các dãy, mỗi mục ij I được gán một ban đầu thành dãy là tương tự vì<br /> trọng số wj, một ngưỡng hỗ trợ tối thiểu thể hiện đúng từng mặt hàng khách hàng đã mua trong<br /> wminsup, các ràng buộc khoảng cách thời gian từng thời điểm cụ thể. Với quy ước như vậy thì sự<br /> C1, C2, C3, C4. Tìm tất cả các mẫu dãy thường biểu hiện của một dãy là duy nhất.<br /> <br /> <br /> <br /> - 74 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 14 (34), tháng 12/2015<br /> <br /> <br /> Nếu ta theo thứ tự của các tiền tố của một dãy và Với j= 3, thì s’3= (0,r), vì vậy hậu tố là<br /> CSDL điều kiện của tiền tố đó chỉ có các hậu tố của<br /> Postfix(a,sb,t1,b) = <br /> một dãy thì ta có thể kiểm tra các dãy con theo thứ tự<br /> sắp xếp trên và CSDL điều kiện theo tiền tố đó. Định nghĩa 8. (CSDL điều kiện theo tiền tố<br /> Định nghĩa 7. (Tiền tố và Hậu tố trong dãy có trong dãy có khoảng cách thời gian): Cho một cơ<br /> khoảng cách thời gian): Các mục dữ liệu trong một sở dữ liệu dãy S có khoảng cách thời gian và một dãy<br /> thành phần của dãy đã sắp xếp thứ tự chữ cái [3]. Cho b có dạng. Khi đó<br /> một dãy a = , một một CSDL điều kiện theo tiền tố b được định nghĩa là<br /> dãy sb là một tập các ij⊆ I. Khi đó tồn tại một giá trị j S|b, gồm các hậu tố (Postfix) của các dãy trong S với<br /> tiền tố b được xây dựng theo Định nghĩa 7.<br /> (1 ≤ j ≤ m) sao cho sb⊆sj và t1,b= t1, j .<br /> Ta định nghĩa tiền tố trong dãy có khoảng cách thời Dựa trên Định nghĩa 3, có thể thấy NW() luôn<br /> gian của a với các giá trị sb, t1,b như sau: nhỏ hơn hay bằng MaxW với MaxW là giá trị lớn nhất<br /> Prefix (a,sb, t1,b) = của trọng số trong các mục trong S. Vì vậy, thay vì<br /> (7) khai phá mẫu dãy thường xuyên thỏa Định nghĩa 6, ta<br /> đưa bài toán về dạng khai thác các mẫu dãy thỏa Định<br /> Khi đó hậu tố trong dãy có khoảng cách thời gian<br /> nghĩa 9 dưới đây, sau đó tính giá trị NWSupport của<br /> của a với giá trị sb, t1,b được định nghĩa:<br /> các mẫu dãy thu được để tìm các mẫu dãy thường<br /> Postfix (a,sb, t1,b) = xuyên.<br /> (8)<br /> Định nghĩa 9. (Mẫu dãy ứng viên): Cho một<br /> Với s’j là một tập con của sj sau khi đã trừ đi tập sb.<br /> ngưỡng hỗ trợ tối thiểu wminsup. Một dãy  được gọi<br /> Khi s’j = , thì hậu tố của a với giá trị sb, t1,b là:<br /> là dãy ứng viên mẫu dãy thường xuyên trọng số chuẩn<br /> Postfix (a,sb, t1,b) = hóa với khoảng cách thời gian nếu thỏa mãn tính chất:<br /> Mặt khác, khi không tồn tại một giá trị j thì hậu tố Support() * MaxW  wminsup và thỏa mãn các<br /> của a với các giá trị sb, t1,b trở thành: tính chất C1, C2, C3, C4 (9)<br /> Prefix (a,sb, t1,b) =  Với MaxW là giá trị lớn nhất của trọng số trong<br /> các mục trong S, mẫu dãy ứng viên được xây dựng<br /> Postfix (a,sb, t1,b) = <br /> nhằm mục đích tỉa bớt không gian tìm kiếm mà vẫn<br /> Ví dụ : đảm bảo tính phản đơn điệu trong khai phá mẫu dãy<br /> thường xuyên trọng số chuẩn hóa với khoảng cách<br /> Cho một dãy a = , khi đó<br /> thời gian.<br /> Với tiền tố sb= (0,p) ta xây dựng các hậu tố của dãy<br /> III.3. Ví dụ khai phá mẫu dãy thƣờng xuyên trọng<br /> a như sau:<br /> số chuẩn hóa với khoảng cách thời gian<br /> Với j= 1, thì s’1= , vì vậy hậu tố là<br /> Cho một CSDL dãy S với khoảng cách thời gian<br /> Postfix(a,sb,t1,b) = như Bảng 1, giá trị các trọng số của các mục dữ liệu<br /> như Bảng 2, giá trị wminsup =1,5 và các giá trị C1=1;<br /> Với j= 2, thì s’2= (0,qr), vì vậy hậu tố là<br /> C2=2; C3=2; C4=3. Khi đó việc khai phá các mẫu dãy<br /> Postfix(a,sb,t1,b) = thường xuyên trọng số chuẩn hóa với khoảng cách<br /> <br /> <br /> - 75 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 14 (34), tháng 12/2015<br /> <br /> <br /> thời gian trong CSDL dãy S theo phương pháp Giá trị trọng số các mục theo Bảng 2 là (a=0,9;<br /> WIPrefixSpan được thực hiện theo các bước như sau: b=0,75; c=0,8; d=0,85; e=0,75; f=0,7)<br /> Bảng 1. Cơ sở dữ liệu dãy S Giá trị MaxW = 0.9; Giá trị wminsup = 1,5<br /> Kiểm tra theo Định nghĩa 9, loại mục , <br /> iSID Dãy dữ liệu<br /> và do giá trị:<br /> 10 <br /> support(*MaxW = 1*0,9=0,9 < wminsup;<br /> 20 support()*MaxW = 1*0,9=0,9 < wminsup;<br /> 30 support()*MaxW = 1*0,9=0,9 < wminsup;<br /> Khi đó ta có các ứng viên mẫu dãy thường xuyên<br /> trọng số chuẩn hóa với khoảng cách thời gian có độ<br /> Bảng 2. Giá trị trọng số của các mục dữ liệu<br /> dài 1 là:<br /> Tên mục Trọng số<br /> Q1 = , ,<br /> a 0.9 Kiểm tra theo Định nghĩa 6 với các ứng viên trong<br /> b 0.75 Q1, khi đó ta có các mẫu dãy thường xuyên trọng số<br /> chuẩn hóa với khoảng cách thời gian có độ dài 1 được<br /> c 0.8 nạp vào L là:<br /> d 0.85 NWsupport() = 3*0,9 =2,7 > wminsup;<br /> <br /> e 0.75 NWsupport() = 2*0,75 =1,5 = wminsup;<br /> <br /> f 0.7 NWsupport() = 2*0,8 =1,6 > wminsup.<br /> <br /> Kết quả L tại Bước 1 là :<br /> Bƣớc 1: Tìm các ứng viên của mẫu dãy thƣờng L = {, ,}<br /> xuyên với trọng số chuẩn hóa có độ dài 1<br /> Bƣớc 2: Chia không gian tìm kiếm<br /> Duyệt CSDL dãy S lần đầu tiên để tìm tất cả các<br /> Toàn bộ các ứng viên và mẫu dãy thường xuyên<br /> ứng viên của mẫu dãy thường xuyên trọng số chuẩn<br /> trọng số chuẩn hóa với khoảng cách thời gian được<br /> hóa với khoảng cách thời gian có độ dài 1, thực hiện<br /> khai phá trong các phân vùng gồm 03 vùng tương ứng<br /> đếm độ hỗ trợ của mỗi mục.<br /> với 03 tiền tố gồm:<br /> Một mục có độ dài 1 có thể không phải là một mẫu<br /> dãy thường xuyên có trọng số chuẩn hóa nhưng có thể  Mẫu dãy với tiền tố <br /> kết hợp với các mục khác có độ hỗ trợ lớn hơn hoặc  Mẫu dãy với tiền tố <br /> trọng số lớn hơn để trở thành mẫu dãy thường xuyên  Mẫu dãy với tiền tố <br /> có trọng số trong các mẫu có độ dài lớn hơn. Bƣớc 3: Khai phá các tập con ứng viên và mẫu<br /> Khi đó ta có các giá trị độ hỗ trợ của mỗi mục như dãy thƣờng xuyên trọng số chuẩn hóa với khoảng<br /> sau: cách thời gian<br /> support() = 3, support() = 2, Các tập con ứng viên và mẫu dãy thường xuyên<br /> support() = 2, support() = 1, trọng số chuẩn hóa với khoảng cách thời gian được<br /> support() = 1, support() = 1 khai phá bằng cách xây dựng các CSDL điều kiện<br /> <br /> - 76 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 14 (34), tháng 12/2015<br /> <br /> <br /> tương ứng với các tiền tố và khai phá chúng bằng support()*MaxW = 1*0,9=0,9<br /> phương pháp đệ quy. Các bước thực hiện như sau: support()*MaxW = 1*0,9=0,9<br /> A. Tìm các ứng viên và các mẫu dãy thường support()*MaxW = 1*0,9=0,9<br /> xuyên trọng số chuẩn hóa với khoảng cách<br /> support()*MaxW = 1*0,9=0,9<br /> thời gian với tiền tố và các ràng buộc<br /> support()*MaxW = 1*0,9=0,9<br /> thời gian C1, C2, C3, C4<br /> Các ứng viên có độ dài 2 với tiền tố thỏa<br /> Khi đó CSDL điều kiện với tiền tố sẽ bao gồm<br /> mãn độ hỗ trợ với trọng số lớn nhất là :<br /> các hậu tố được xây dựng theo Định nghĩa 7:<br /> , ,<br /> Bảng 3. Cơ sở dữ liệu điều kiện với tiền tố <br /> Kiểm tra các ứng viên trên với tính chất ràng buộc<br /> iSID Dãy dữ liệu<br /> thời gian C1=1; C2=2; C3=2; C4=3. Khi đó, ứng viên<br /> bị loại do không thỏa mãn tính chất C2 =<br /> 10 2. Vì vậy:<br /> < (0,c)><br /> Q2 = , <br /> 20 <br /> Kiểm tra theo Định nghĩa 6 với các ứng viên trong<br /> <br /> 30 Q2, khi đó ta có các mẫu dãy thường xuyên trọng<br /> <br /> số chuẩn hóa với khoảng cách thời gian có độ dài 2<br /> với tiền tố được nạp vào L.<br /> Bằng cách quét CSDL điều kiện với tiền tố ,<br /> độ hỗ trợ của các mục dữ liệu của nó là: Kiểm tra độ hỗ trợ với trọng số chuẩn hóa của các<br /> ứng viên , :<br /> support()= 1; support()= 1;<br /> support()= 1; support()= 1; NWsupport() = 2*(0,9+0,75)/2=1,65<br /> support()= 2; support()= 2;<br /> NWsupport(,<br /> với khoảng cách thời gian với mỗi tiền tố tương ứng<br /> - Nạp R = {R, }.<br /> <br /> - 78 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 14 (34), tháng 12/2015<br /> <br /> <br /> - Kiểm tra điều kiện (http://www.philippe-fournier-viger.com/spmf/<br /> support()*NW()  wminsup , nếu thỏa mãn L={L, datasets/BMS1_spmf). Bộ dữ liệu BMS-WebView<br /> }. được sinh ngẫu nhiên các dữ liệu chiều thời gian,<br /> khoảng cách thời gian giữa 2 tập mục kề nhau trong 1<br /> b) Thực hiện R = WIPrefixSpan(<br /> chuỗi bất kỳ được sinh ngẫu nhiên từ 0-10. Giá trị<br /> ISDB|,R,W,wminsup, C1, C2, C3, C4). trọng số của các mục trong thuật toán WIPrefixSpan<br /> Kết thúc lặp trong khoảng 0,2≤ wj ≤ 0,9 .<br /> Trong phần thử nghiệm này, chúng tôi chạy thử<br /> 4) Kết quả tập L.<br /> nghiệm bộ dữ liệu BMS-WebView với các ngưỡng hỗ<br /> Kết thúc. trợ wminsup khác nhau (từ 0,01%-0,1%). Các thuật<br /> Thủ tục WIPrefixSpan (ISDB|,R,W,wminsup, C1, toán IPrefixSpan[10] và WIPrefixSpanđược đưa thêm<br /> C2, C3, C4) các ràng buộc thời gian: C1 = 0, C2=3, C3=0, C4=50<br /> Bắt đầu: Tất cả các thực nghiệm được tiến hành trên một<br /> máy tính có bộ xử lý Intel Core2 Dual 2.53GHz với<br /> 1) Duyệt ISDB| để tìm tất cả các cặp dãy<br /> 3GB bộ nhớ chính, chạy Microsoft Windows XP SP3.<br /> với  và giá trị khoảng cách thời gian giữa dãy đó với<br /> Các thuật toán được thực hiện bởi ngôn ngữ lập trình<br />  trong cặp này (định nghĩa là (Δt,i)) thỏa mãn các<br /> Java 1.6 trên Eclipse.<br /> điều kiện support (i)* MaxW  wminsup, C1, và C2.<br /> Trong trường hợp tổng quát, độ phức tạp của thuật<br /> 2) Đặt  =. toánWIPrefixSpan là O(NL), trong đó N là số lượng<br /> 3) Kiểm tra xem có thỏa mãn điều kiện C4 các mục trong tập dữ liệu và L là chiều dài lớn nhất<br /> 4) Chỉ khi thỏa mãn điều kiện C4 dãy dữ liệu trong toàn bộ các giao dịch.<br /> a) Thực hiện R = WIPrefixSpan  So sánh về thời gian chạy: Kết quả từ Hình 1<br /> (ISDB|,R,W,wminsup, C1, C2, C3, C4). cho thấy khi đưa thêm ràng buộc thời gian vào thì<br /> b) Khi  thỏa mãn điều kiện C3, thời gian chạy của thuật toán giảm đi đáng kể.<br /> Thuật toán WPrefixSpan có thời gian thực thi lâu<br /> R = {R, }.<br /> hơn so với 2 thuật toán IPrefixSpan và<br /> c) Kiểm tra điều kiện WIPrefixSpan khi ngưỡng hỗ trợ giảm dần.<br /> support()*NW()  wminsup , nếu thỏa mãn L={L,<br />  So sánh về số mẫu dãy thường xuyên tìm<br /> }. được: Hình 2, ta có thể thấy thuật toán<br /> 5) Kết quả tập L. WIPrefixSpan đã giảm đáng kể số mẫu dãy thường<br /> Kết thúc. xuyên tìm được so với 2 thuật toán IPrefixSpan và<br /> WPrefixSpan. Do thuật toán đưa thêm ràng buộc<br /> IV. KẾT QUẢ THỰC NGHIỆM thời gian và trọng số, không gian tìm kiếm đã được<br /> Trong phần này, chúng tôi trình bày kết quả thực rút gọn đáng kể.<br /> nghiệm thuật toán WIPrefixSpan so với thuật toán do  Chúng tôi thử nghiệm thuật toán<br /> IprefixSpan [10] và thuật toán WPrefixSpan[11] trên WIPrefixSpan với các giá trị điều kiện từ ĐK1 đến<br /> bộ dữ liệu UCI Machine Learning: BMS-WebView ĐK7 với các giá trị ràng buộc thời gian C1, C2, C3,<br /> với 59601 dãy dữ liệu, 497 mục dữ liệu, chiều dài C4 tương ứng như Bảng 5,thuật toán vẫn sử dụng<br /> trung bình 1 dãy gồm 2,42 mục dữ liệu, gồm một số bộ dữ liệu BMS-WebView và bộ trọng số sinh<br /> dãy dài (hơn 318 dãy chứa nhiều hơn 20 mục) ngẫu nhiên trong khoảng từ 0,2 đến 0,9 với<br /> - 79 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 14 (34), tháng 12/2015<br /> <br /> <br /> ngưỡng hỗ trợ wminsup = 0,01%. Như Bảng 5, ta phép thu nhỏ đáng kể không gian tìm kiếm để khai<br /> có thể thấy số lượng mẫu dãy thường xuyên tìm phá mẫu dãy thường xuyên. Việc đưa giá trị trọng số<br /> được thay đổi theo từng điều kiện ràng buộc thời của các mục dữ liệu trong CSDL dãy có khoảng cách<br /> gian khác nhau. Như vậy ta có thể thông qua việc thời gian cho phép quan tâm tới sự ràng buộc giữa độ<br /> thay đổi các ràng buộc thời gian để tỉa bớt các dữ hỗ trợ, trọng số và khoảng cách thời gian của các dãy,<br /> liệu không quan trọng và làm giảm không gian tìm đồng thời trong quá trình xây dựng các CSDL điều<br /> kiếm của thuật toán. kiện theo tiền tố, sử dụng điều kiện kiểm tra để thực<br /> hiện tỉa những mục không phải là ứng viên của mẫu<br /> 60 dãy thường xuyên trọng số chuẩn hóa với khoảng cách<br /> WPrefixSpa thời gian cho phép giảm không gian tìm kiếm nhưng<br /> Thời gian (giây)<br /> <br /> <br /> <br /> <br /> 50<br /> n<br /> 40 vẫn đảm bảo tính phản đơn điệu trong giải thuật.<br /> 30 Bảng 5. Số mẫu dãy thường xuyên theo các giá trị<br /> 20 điều kiện ràng buộc thời gian khác nhau<br /> 10 Điều ĐK ĐK ĐK ĐK ĐK ĐK ĐK<br /> kiện 1 2 3 4 5 6 7<br /> 0<br /> Khoảng<br /> 0,010,020,030,040,050,060,070,080,090,10 thời gian<br /> wminsup (%) x x 1 5 x x x<br /> nhỏ nhất<br /> (C1):<br /> Hình 1: Thời gian chạy Khoảng<br /> thời gian<br /> 5 5 x x x x x<br /> lớn nhất<br /> 4500 WPrefixSpan (C2):<br /> 4000 IPrefixSpan Tổng<br /> 3500 quãng<br /> WIPrefixSpan<br /> Số mẫu dãy thường xuyên<br /> <br /> <br /> <br /> <br /> 3000 thời gian x x 5 10 1 5 x<br /> 2500 nhỏ nhất<br /> 2000 (C3):<br /> 1500 Tổng<br /> 1000 quãng<br /> 500 thời gian 10 50 x x x x x<br /> 0 lớn nhất<br /> 0,01 0,02 0,03 0,04 0,05 0,06 0,07 0,08 0,09 0,10 (C4):<br /> wminsup (%) Số mẫu<br /> dãy 126 169 126 210<br /> 966 966 582<br /> thường 8 1 8 9<br /> xuyên<br /> Hình 2. Số mẫu dãy thường xuyên<br /> <br /> Trong tương lai, chúng tôi sẽ tiếp tục nghiên cách<br /> V. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN thức làm giảm không gian tìm kiếm hơn nữa. Ngoài<br /> Trong bài báo này chúng tôi nghiên cứu và phát ra, chúng tôi sẽ nghiên cứu mở rộng giải thuật của<br /> triển thuật toán WIPrefixSpan phát hiện mẫu dãy chúng tôi cho bài toán khai phá mẫu chuỗi đóng.<br /> thường xuyên trọng số chuẩn hóa với khoảng cách<br /> TÀI LIỆU THAM KHẢO<br /> thời gian theo cách mô hình tăng trưởng mẫu dãy ứng<br /> viên. Với cách tiếp cận này giải thuật không cần sinh [1] R.AGRAWAL, AND R.SRIKANT,“Mining sequential<br /> các ứng viên dãy ban đầu theo các cách tiếp cận thông patterns”.In Proceedings of the International Conference<br /> thường như AprioriAll[1]. Chúng tôi sử dụng phương on Data Engineering (ICDE), pp. 3-14, IEEE Computer<br /> Society (1995).<br /> pháp xây dựng các CSDL điều kiện theo tiền tố cho<br /> - 80 -<br />  Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 14 (34), tháng 12/2015<br /> <br /> <br /> [2] R.AGRAWAL, AND R.SRIKANT,“Mining sequential [10] Y.HIRATE, H.YAMANA,“Generalized Sequential<br /> patterns: generallizations and performance Pattern Mining with Item Intervals”, JCP,Vol. 1, No. 3,<br /> improvements”. Proceedings of the International pp. 51-60 (2006).<br /> Conference on Extending DataBase Technology [11] T.H.DUONG, V.D.THI,“Thuật toán khai phá mẫu dãy<br /> (EDBT), Lecture Notes in Computer Science, Vol. 1057, thường xuyên với trọng số chuẩn hóa sử dụng CSDL<br /> pp. 3-17 (1996). tiền tố”. Kỷ yếu hội nghị Khoa học Quốc gia lần thứ VI<br /> [3] J.PEI, J.HAN, B.M.ASI, H.PINO,“PrefixSpan: Mining – Nghiên cứu cơ bản và ứng dụng CNTT (FAIR), pp.<br /> Sequential Patterns Efficiently by Prefix-Projected 502-511 (2013).<br /> Pattern Growth”. Proceedings of the Seventeenth [12] G.C.LAN, T.P.HONG, H.Y.LEE,“An efficient<br /> International Conference on Data Engineering, pp.215- approach for finding weighted sequential patterns from<br /> 224 (2001). sequence databases”, Applied Intelligence, Vol. 41,<br /> [4] M.ZAKI, “An Efficient Algorithm for Mining Frequent No. 2, pp. 439-452 (2014).<br /> Sequences”, Machine Learning, Vol. 40, pp. 31–60, [13] M.T.TRAN, B.LE, B.VO,“Combination of dynamic bit<br /> 2000. vectors and transaction information for mining<br /> [5] J.AYRES, J.GEHRKE, T.YIU,ANDJ.FLANNICK, frequent closed sequences efficiently”, Engineering<br /> “Sequential Pattern Mining using Bitmap Applications of Artificial Intelligence, Vol. 38, pp. 183-<br /> Representation”, in Proc. of ACM SIGKDD’02, pp. 189 (2015).<br /> 429–435, 2002. [14] B.VO, F.COENEN,B.LE,“A new method for mining<br /> [6] M.S.KHAN, M. MUYEBA, F. COENEN,“Weighted Frequent Weighted Itemsets based on WIT-<br /> Association Rule Mining from Binary and Fuzzy Data”. trees”. Expert Systemswith Applications, Vol. 40, No.<br /> In Proceedings of 8th Industrial Conference, ICDM 4, pp. 1256-1264 (2013).<br /> 2008,pp. 200-212 (2008). [15] U.YUN, G.PYUN, E.YOON,“Efficient Mining of<br /> [7] F.TAO, F.MURTAGH, M.FARID,“Weighted Robust Closed Weighted Sequential Patterns Without<br /> Association Rule Mining Using Weighted Support and Information Loss”, International Journal on Artificial<br /> Significance Framework”. In Proceedings of 9th ACM Intelligence Tools, Vol. 24, No. 1, 28 pages (2015).<br /> SIGKDD Conference on Knowledge Discovery and [16] U.YUN, K.H.RYU,“Approximate weighted<br /> Data Mining, pp. 661–666 (2003). frequent pattern mining with/without noisy<br /> [8] U.YUN,“An efficient mining of weighted frequent environments”, Knowledge-Based Systems, Vol. 24,<br /> patterns with length decreasing support No. 1, pp. 73-82 (2011).<br /> constraints”, Knowledge-Based Systems, Vol. 21, No.<br /> 8, pp. 741–752 (2008).<br /> [9] U.YUN, J.J.LEGGETT,“WFIM: weighted frequent<br /> itemset mining with a weight range and a minimum Ngày nhận bài: 11/05/2015<br /> weight”, In 5th SIAM Int. Conf. on Data Mining, pp.<br /> 636–640 (2005).<br /> <br /> <br /> <br /> <br /> - 81 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 14 (34), tháng 12/2015<br /> <br /> <br /> SƠ LƢỢC VỀ TÁC GIẢ<br /> <br /> TRẦN HUY DƢƠNG VŨ ĐỨC THI<br /> Sinh năm:1975 Sinh năm 1949 .<br /> Tốt nghiệp ĐH Bách khoa Hà Nội Tốt nghiệp ĐH Tổng hợp Hà Nội<br /> năm 1997, ngành CNTT. Bảo vệ năm 1971. Bảo vệ luận án tiến sỹ tại<br /> luận văn Thạc sĩ tại ĐH Bách khoa Viện Hàn lâm Khoa học Hungary,<br /> Hà Nội năm 2000, ngành CNTT. năm 1987, chuyên ngành Cơ sở dữ<br /> liệu, CNTT. Nhận học hàm Phó giáo<br /> Lĩnh vực nghiên cứu: Khai phá dữ<br /> sư năm 1991, Giáo sư năm 2009.<br /> liệu, cơ sở dữ liệu và học máy.<br /> Lĩnh vực nghiên cứu: Cơ sở dữ liệu<br /> Điện thoại: 0903234934<br /> và hệ thống thông tin, khai phá dữ liệu và học máy.<br /> Email: huyduong@ioit.ac.vn<br /> Điện thoại: 0903221304.<br /> Email: vdthi@vnu.edu.vn<br /> <br /> <br /> <br /> <br /> - 82 -<br />