Luận văn Một số thuật toán khai phá luật dãy và ứng dụng thử nghiệm vào hệ thống quản lý khách hàng và tính hóa đơn nước

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN ĐÌNH VĂN MỘT SỐ THUẬT TOÁN KHAI PHÁ LUẬT DÃY VÀ ỨNG DỤNG THỬ NGHIỆM VÀO HỆ THỐNG QUẢN LÝ KHÁCH HÀNG VÀ TÍNH HÓA ĐƠN NƯỚC LUẬN VĂN THẠC SĨ Hà Nội - 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN ĐÌNH VĂN MỘT SỐ THUẬT TOÁN KHAI PHÁ LUẬT DÃY VÀ ỨNG DỤNG THỬ NGHIỆM VÀO HỆ THỐNG QUẢN LÝ KHÁCH HÀNG VÀ TÍNH HÓA ĐƠN NƯỚC Ngành: Công Nghệ Thông Tin Chuyên ngành: Hệ Thống Thông Tin Mã số: 60.48.05 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Hà Quang Thụy Hà Nội - 2011 - 3 - Khai phá luật dãy Nguyễn Đình Văn LỜI CAM ĐOAN Tôi xin cam đoan luận văn này với đề tài “Một số thuật toán khai phá dãy và ứng dụng thử nghiệm vào hệ thống quản lý khách hàng và tính hóa đơn nước” là công trình do tôi nghiên cứu và hoàn thành dưới sự hướng dẫn của PGS. TS. Hà Quang Thụy, trong luận văn có sử dụng một số tài liệu tham khảo như đã nêu trong phần “Tài liệu tham khảo”. Tác giả luận văn Nguyễn Đình Văn - 4 - Khai phá luật dãy Nguyễn Đình Văn MỤC LỤC MỞ ĐẦU.............................................................................................................................. 6 CHƯƠNG 1 – KHÁI QUÁT CHUNG VỀ LUẬT DÃY VÀ KHAI PHÁ LUẬT DÃY ...... 8 1.1 Giới thiệu chung về luật kết hợp ............................................................................ 8 1.1.1 Khái niệm luật kết hợp................................................................................... 8 1.1.2 Các ứng dụng điển hình của luật kết hợp........................................................ 9 1.1.3 Thuật toán Apriori ....................................................................................... 10 1.2 Luật dãy .............................................................................................................. 12 1.2.1 Khái niệm luật dãy và ví dụ.......................................................................... 12 1.2.2 Một số ứng dụng.......................................................................................... 14 1.2.3 Luật dãy và luật kết hợp: một số đối sánh..................................................... 16 1.2.4 Sơ bộ về các phương pháp khai phá luật dãy................................................ 17 CHƯƠNG 2 – CÁC PHƯƠNG PHÁP KHAI PHÁ LUẬT DÃY ........................................ 21 2.1 Khái quát về khai phá luật dãy............................................................................. 21 2.2 Các thuật toán khởi thủy ...................................................................................... 23 2.2.1 Thuật toán AprioriAll .................................................................................. 23 2.2.2 Thuật toán AprioriSome............................................................................... 27 2.2.3 Thuật toán GSP (Generalized Sequential Patterns) ....................................... 30 2.3 Hai phương pháp khai phá luật dãy...................................................................... 36 2.3.1 Khai phá dãy sử dụng kỹ thuật phân vùng (thuật toán Dynamic DISC-all) ... 36 2.3.2 Khai phá luật dãy bằng mã hóa khối cơ bản với thuật toán PRISM............... 38 CHƯƠNG 3 – ĐỀ XUẤT ỨNG DỤNG KHAI PHÁ LUẬT DÃY TRONG HỆ THỐNG QUẢN LÝ KHÁCH HÀNG VÀ TÍNH HÓA ĐƠN NƯỚC ............................................... 43 3.1 Tổng quan về hệ thống quản lý khách hàng và tính hóa đơn nước ........................ 43 3.1.1 Phân hệ quản lý khách hàng................................................................................. 44 3.1.2 Phân hệ lập và in hóa đơn .................................................................................... 46 3.1.3 Phân hệ thanh toán hóa đơn và quản lý nợ ........................................................... 48 3.1.4 Phân hệ báo cáo thống kê..................................................................................... 49 3.2 Phát biểu bài toán ................................................................................................ 50 3.3 Mô hình giái quyết............................................................................................... 52 3.4 Thực nghiệm và đánh giá..................................................................................... 55 3.4.1 Giới thiệu thực nghiệm ........................................................................................ 55 3.4.2 Kết quả thực nghiệm và nhận xét ......................................................................... 57 KẾT LUẬN ........................................................................................................................ 58 - 5 - Khai phá luật dãy Nguyễn Đình Văn CÁC ĐỊNH NGHĨA VÀ CHỮ VIẾT TẮT Chữ viết tắt Diễn giải Candidate Ứng viên CSDL Cơ sở dữ liệu Element Thành phần dãy Frequent item Phần tử thường xuyên Gcd Hàm tính ước số chung lớn nhất Item Phần tử Itemset Tập hợp các phần tử (item) xảy ra cùng lúc Large sequence Dãy phổ biến Maximal sequence Dãy tối đa, dãy phổ biến nhất Projected database CSDL quy chiếu Sequence Dãy Support Độ hỗ trợ Support threshold Ngưỡng hỗ trợ Supsequence Dãy con Threshold Ngưỡng - 6 - Khai phá luật dãy Nguyễn Đình Văn MỞ ĐẦU Khai phá luật dãy là một trong những lĩnh vực rất quan trọng trong nghiên cứu khai phá dữ liệu của thập kỷ gần đây và ngày càng được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau. Vì trong thực tế, dữ liệu dãy tồn tại rất phổ biến, như dãy dữ liệu mua sắm của khách hàng, dữ liệu điều trị y tế, các dữ liệu liên quan đến các thảm họa tự nhiên, dữ liệu xử lý khoa học và kỹ thuật, dữ liệu chứng khoán và phân tích thị trường, dữ liệu các cuộc gọi điện thoại, nhật ký truy cập web, dãy ADN biểu thị gen ... Mục đích chính của khai phá luật dãy là tìm kiếm và phát hiện tất cả các dãy con lặp đi lặp lại trong một CSDL theo yếu tố thời gian. Hiện nay, trên thế giới đã có rất nhiều nhóm tác giả nghiên cứu đề xuất các thuật toán với các phương pháp tiếp cận khai phá luật dãy khác nhau [1,2,5-12,14-16] nhằm giải quyết sự đa dạng của các loại bài toán cũng như đưa ra các hướng cải tiến nhằm giảm thiểu chi phí thời gian và tài nguyên hệ thống. Luận văn này nghiên cứu một số thuật toán khai phá luật dãy, trong đó tập trung chủ yếu vào các thuật toán AprioriAll, AprioriSome [1], vì đây là những thuật toán rất nổi tiếng trong lĩnh vực khai phá luật dãy và phù hợp với việc ứng dụng thử nghiệm vào Hệ thống Quản lý khách hàng và tính hóa đơn nước. Luận văn tiếp tục khóa luận tốt nghiệp đại học trước đây của tôi (Nguyễn Đình Văn (2003), Phân tích thiết kế hệ thống và ứng dụng vào bài toán quản lý khách hàng và tính hóa đơn nước) trong việc bổ sung những tính năng nâng cao cho hệ thống. Luận văn hy vọng phát hiện được một số luật dãy, chẳng hạn như dãy thời gian tiêu thụ nước nhiều nhất trong năm, dãy dịch chuyển mức tiêu thụ nước theo mục đích sử dụng (sinh hoạt, sản xuất, kinh doanh, công cộng, …), phát hiện những trường hợp bất thường trong sử dụng nước (tỉ lệ đăng ký sử dụng và thực tế sử dụng nước), mức độ thất thoát nước và nguyên nhân thất thoát nước … để lãnh đạo xí nghiệp có thể đưa ra các biện pháp quản lý, các chiến lược sản xuất, kinh doanh phù hợp. Luận văn được trình bày gồm có phần mở đầu, ba chương và phần kết luận. Trong chương một, luận văn tập trung chủ yếu vào giới thiệu tổng quan về luật dãy và khái phá luật dãy. Vì luật dãy có những mối liên hệ gần gũi với luật kết hợp và một số thuật toán khai phá luật dãy trong luận văn là mở rộng của thuật toán điển hình Apirori khai phá luật kết hợp, nên phần này sẽ trình bày khái quát về luật kết hợp, một số đối sánh giữa luật dãy và luật kết hợp. Giới thiệu sơ bộ các phương pháp tiếp cận khai phá luật dãy và các thuật toán điển hình tương ứng. Nội dung của chương này được tổng hợp từ các tài liệu [1,3-4,13]. Trong chương hai, luận văn tập trung giới thiệu các thuật toán khai phá luật dãy như AprioriAll [1], AprioriSome [1], GSP [2] là những thuật toán khởi thủy khai phá luật dãy. Giới thiệu hai phương pháp khai phá luật dãy được công bố thời gian gần đây - 7 - Khai phá luật dãy Nguyễn Đình Văn là “Khai phá luật dãy sử dụng kỹ thuật phân vùng” [10] và “Khai phá luật dãy bằng mã hóa khối cơ bản” [16]. Trong chương ba, luận văn giới thiệu tổng quan về Hệ thống Quản lý khách hàng và tính hóa đơn nước, đồng thời đề xuất ứng dụng khai phá luật dãy với thuật toán AprioriAll. Trong đó, đưa ra yêu cầu đầu bài và mô hình cụ thể giải quyết bài toán. Luận văn sử dụng dữ liệu mô phỏng của Xí nghiệp kinh doanh nước sạch Hoàn Kiếm làm dữ liệu thử nghiệm để thực thi chương trình, đánh giá kết quả thực nghiệm. Luận văn được hỗ trợ một phần từ Đề tài QG.10-38. Luận văn được thực hiện dưới sự hướng dẫn của PGS. TS. Hà Quang Thụy – trường Đại học Công Nghệ. Em xin bày tỏ lòng biết ơn sâu sắc tới Thầy đã hướng dẫn và có ý kiến chỉ dẫn quý báu trong quá trình em thực hiện luận văn. Xin chân thành cảm ơn Thạc sĩ Đặng Tiểu Hùng – Công ty CSE đã đóng góp nhiều ý kiến bổ ích để bản luận văn được hoàn thiện hơn. Cuối cùng xin bày tỏ lòng biết ơn tới những người thân trong gia đình, bạn bè đã động viên và giúp đỡ để tác giả hoàn thành bản luận văn này. - 8 - Khai phá luật dãy Nguyễn Đình Văn CHƯƠNG 1 – KHÁI QUÁT CHUNG VỀ LUẬT DÃY VÀ KHAI PHÁ LUẬT DÃY Khai phá luật dãy là một chủ đề thiết thực và quan trọng trong khai phá dữ liệu với nhiều ứng dụng như là trong phân tích giao dịch mua hàng của khách hàng, khai thác weblogs, khai thác các dãy ADN, nghiên cứu dữ liệu trong các bài toán khí tượng - thủy văn như dự báo thời tiết, các thảm họa tự nhiên như động đất, sóng thần... Các thuật toán khai phá luật dãy kế thừa nhiều từ các thuật toán khai phá luật kết hợp, và nhiều thuật toán trong số đó là mở rộng của các thuật toán khởi thủy, ở đó sự khác biệt chính là trong khai phá luật dãy đưa ra các phân tích liên giao dịch (inter- transaction), trong khi đó khai phá luật kết hợp là tìm luật về mối liên quan giữa các phần tử trong cùng một giao dịch (intra- transaction). Trước tiên, ta cần tìm hiểu một số vấn đề của luật kết hợp. 1.1 Giới thiệu chung về luật kết hợp 1.1.1 Khái niệm luật kết hợp Mục đích của luật kết hợp (Association Rule) là tìm ra các mối liên hệ giữa các đối tượng trong khối lượng lớn dữ liệu [4]. Nội dung của luật kết hợp được phát biểu như sau: Cho tập các phần tử I = {i1, i2, …, im}. Cho CSDL D là tập các giao dịch, trong đó mỗi giao dịch T là một tập các phần tử, tức là T  I. Mỗi giao dịch được gắn với một định danh gọi là TID. Cho A là tập các phần tử. Giao dịch T được gọi là chứa A nếu và chỉ nếu A  T. Một luật kết hợp có dạng A  B, trong đó A  I, B  I và A  B = Ø. Độ hỗ trợ (support) và độ tin cây (confidence) là 2 tham số dùng để đo lường luật kết hợp. Luật A  B trong tập giao dịch D với độ hỗ trợ (support) s, kí hiệu là support(A  B), trong đó s là tỉ lệ phần trăm của các giao dịch trong D mà có chứa A  B. Hay là xác suất P(A  B ). Công thức để tính độ hỗ trợ của luật A  B như sau: support(A  B) = P(A  B ) = N Bn )A (  Trong đó: N là tổng số giao dịch; n(A  B ) là số giao dịch có chứa (A  B ) - 9 - Khai phá luật dãy Nguyễn Đình Văn Luật A  B có độ tin cậy (confidence) c trong tập giao dịch D, kí hiệu là confidence(A  B), trong đó c là tỉ lệ phần trăm của các giao dịch trong D có chứa A và cũng chứa B. Hay là xác suất P(B | A). Công thức để tính độ tin cậy của luật A  B là xác suất có điều kiện B khi đã biết A, như sau: confidence(A  B) = P(B | A ) = )( )A ( An Bn  Trong đó: n(A) là số giao dịch chứa A; n(A  B ) là số giao dịch có chứa (A  B ) Các luật đáp ứng được (lớn hơn hoặc bằng) cả ngưỡng hỗ trợ tối thiểu (min_sup) và ngưỡng tin cậy tối thiểu (min_conf) được gọi là các luật mạnh (strong rules). Thông thường, ta viết độ hỗ trợ và độ tin cậy là các giá trị giữa khoảng 0% và 100% thay vì từ 0 đến 1.0. min_sup và min_conf gọi là các giá trị ngưỡng (threshold) và phải xác định trước khi sinh các luật kết hợp. 1.1.2 Các ứng dụng điển hình của luật kết hợp Một số ứng dụng điển hình như: phân tích giỏ hàng (market basket analysis), đưa ra chiến lược tiếp thị, thiết kế bài trí gian hàng, chiến lược bán hàng khuyến mại, các bài toán phân lớp, phân cụm, ... Market basket analysis: Chẳng hạn, một người quản lý một chi nhánh bán hàng, họ muốn biết thêm về thói quen mua sắm của khách hàng. Cụ thể như họ muốn biết rằng “Trong mỗi lần mua sắm, khách hàng thường mua các nhóm mặt hàng nào cùng nhau?”. Để trả lời câu hỏi này, việc phân tích giỏ khách hàng sẽ được thực hiện trên dữ liệu mua bán lẻ của khách hàng đã được lưu trữ. Sau đó có thể sử dụng kết quả đó để lên kế hoạch tiếp thị, chiến lược quảng cáo hoặc dự định bổ sung các danh mục hàng hóa mới. Việc phân tích giỏ hàng có thể giúp bạn thiết kế gian hàng với các cách bài trí hàng hóa khác nhau. Các mặt hàng thường xuyên được mua với nhau có thể được đặt ở gần nhau để thúc đẩy việc bán hàng. Nếu khách hàng mua máy tính cũng có xu hướng mua phần mềm diệt virus cùng lúc, cũng thế, đặt màn hình gần với các phần mềm hiển thị có thể giúp tăng doanh số bán hàng của cả hai. Trong một chiến lược khác, bố trí phần cứng và phần mềm ở hai đầu của cửa hàng có thể lôi kéo khách hàng mua những mặt hàng khác trên đường di chuyển giữa hai vị trí. Ví dụ, sau khi quyết định mua một máy tính đắt tiền, trong khi đến mua phần mềm diệt virus, khách hàng quan sát thấy hệ thống an ninh gia đình được trưng bày và có thể quyết định mua. Việc phân tích giỏ hàng cũng có thể giúp các nhà bán lẻ đưa ra các kế hoạch bán hàng giảm giá. Thông thường, khách hàng có xu hướng mua máy tính và máy in với nhau, khi đó có thể bán giảm giá máy in nếu khách hàng mua máy tính. - 10 - Khai phá luật dãy Nguyễn Đình Văn Trong gian hàng, mỗi mặt hàng gắn với một biến Boolean biểu thị sự có mặt hay vắng mặt của mặt hàng đó. Tiếp đến, mỗi giỏ hàng có thể được thể hiện bởi một vector Boolean các giá trị được gán cho các biến đó. Các vector Boolean biểu thị các mẫu mua hàng mà ở đó các mặt hàng được kết hợp một cách thường xuyên hoặc được mua với nhau. Các mẫu này có thể được biểu thị ở dạng các luật kết hợp. Ví dụ, khách hàng mua máy tính cũng có xu hướng mua phần mềm diệt virus cùng lúc, có thể được biểu diễn với luật kết hợp như sau: computer  antivirus_software [support = 2%, confidence = 60%] support = 2% nghĩa là có 2% trong tất cả các giao dịch được phân tích cho thấy máy tính và phần mềm diệt virus được mua cùng lúc. confidence = 60% nghĩa là có 60% số lượng khách hàng đã mua máy tính thì cũng mua phần mềm. Thông thường, các luật kết hợp được quan tâm nếu chúng đáp ứng được cả ngưỡng hỗ trợ tối thiểu và ngưỡng tin cậy tối thiểu. Các ngưỡng này có thể được thiết lập bởi người dùng. Một số thuật toán thường được sử dụng cho khai phá luật kết hợp như: Apriori, Eclat, Frequent-Pattern tree, … .Dưới đây sẽ trình bày chi tiết thuật toán Apriori vì thuật toán này được mở rộng để sử dụng cho khai phá luật dãy. 1.1.3 Thuật toán Apriori Tư tưởng của thuật toán Apriori là: - Tìm tất cả các tập thường xuyên (frequent itemsets): k-itemset (itemsets gồm k items) được dùng để tìm (k+1)-itemset. - Đầu tiên tìm 1-itemset (ký hiệu L1); L1 được dùng để tìm L2 (2-itemsets); L2 được dùng để tìm L3 (3-itemset) và tiếp tục cho đến khi không có k-itemset được tìm thấy. - Từ các tập thường xuyên (frequent itemsets) sinh ra các luật kết hợp mạnh (các luật kết hợp thỏa mãn 2 tham số min_sup và min_conf)  Thuật toán Apriori [4] Join Step: Ck is generated by joining Lk-1with itself. Prune Step: Any (k-1)-itemset that is not frequent cannot be a subset of a frequent k-itemset. Pseudo-code: Ck: Candidate itemset of size k Lk: frequent itemset of size k L1 = {frequent items}; for (k = 1; Lk !=Ø; k++) do Ck+1 = candidates generated from Lk for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support end - 11 - Khai phá luật dãy Nguyễn Đình Văn return kLk Cụ thể, thực hiện theo các bước sau: Bước 1: Duyệt toàn bộ CSDL để có được độ hỗ trợ s của 1-itemset, so sánh s với min_sup, để có được 1-itemset (L1) Bước 2: Thực hiện phép nối (join) Lk-1 với Lk-1 để sinh ra tập ứng viên k-itemset. Loại bỏ các tập không phải là tập thường xuyên ta thu được k-itemset Bước 3: Duyệt CSDL để có được độ hỗ trợ s của mỗi tập ứng viên k-itemset, so sánh s với min_sup để loại bỏ các tập không phải là tập thường xuyên (có s < min_sup), thu được tập thường xuyên k–itemset (Lk) Bước 4: Lặp lại từ bước 2 cho đến khi tập ứng viên là rỗng (không tìm thấy tập thường xuyên). Bước 5: Với mỗi tập thường xuyên I, sinh tất cả các tập con s không rỗng của I Bước 6: Với mỗi tập con s không rỗng của I, sinh ra các luật s => (I-s) nếu độ tin cậy (confidence) của nó > = min_conf Chẳn hạn với I= {A1,A2,A5},các tập con của I: {A1}, {A2}, {A5}, {A1,A2},{A1,A5},{A2,A5} sẽ có các luật sau {A1} => {A2,A5},{A2} =>{A1,A5},{A5} =>{A1,A2} {A1,A2} =>{A5},{A1,A5} =>{A2},{A2,A5} => {A1}  Ví dụ: Giả sử ta có có sở dữ liệu giao dịch như sau : Thuật toán Apriori khai phá luật kết hợp được mô tả qua các bước sau - 12 - Khai phá luật dãy Nguyễn Đình Văn Ta có tập thường xuyên I ={B,C,E}, với min_conf = 80% ta có 2 luật kết hợp là {B,C} => {E} và {C,E} => {B} 1.2 Luật dãy 1.2.1 Khái niệm luật dãy và ví dụ Ta giới thiệu vấn đề dựa trên quá trình mua bán hàng và một CSDL lưu trữ thông tin giao dịch mua bán hàng bao gồm các thông tin về mã khách hàng (customer-id), thời gian giao dịch (transaction-time) và các mặt hàng trong giao dịch.  Các khái niệm Một itemset là một tập không rỗng các phần tử (item). Một dãy (sequence) là một danh sách có thứ tự các itemset. Không mất tính tổng quát, chúng ta giả sử rằng một tập các phần tử được ánh xạ tới một tập các số nguyên liền kề. Ta biểu thị itemset i bởi (i1i2...im), trong đó ij là một phần tử. Ta biểu thị dãy s bởi (s1s2...sn), trong đó sj là một itemset. - 13 - Khai phá luật dãy Nguyễn Đình Văn Dãy (a1a2...an) được chứa trong dãy (b1b2...bn) nếu ở đó tồn tại các số nguyên i1 < i2 < ... < in sao cho a1  bi1 , a2  bi2 , ..., an  bin. Ta sử dụng ký hiệu  để biểu thị quan hệ “được chứa trong”. Ví dụ, dãy  , vì ((3)  (3 8), (4 5)  (4 5 6) và (8)  (8). Tuy nhiên, dãy không được chứa trong và ngược lại. Phần tử 3 và 5 trong dãy mô tả chúng không nằm trong cùng một lần giao dịch, trong khi phần tử 3 và 5 trong dãy mô tả chúng nằm trong một lần giao dịch. Trong một tập các dãy, một dãy s là lớn nhất hay tối đa (maximal) nếu s không được chứa trong bất kỳ dãy nào khác. Tất cả các giao dịch của cùng một khách hàng có thể được xem như là một dãy. Trong đó, mỗi giao dịch được xem như một tập các phần tử, và danh sách các giao dịch theo thứ tự tăng dần về thời gian giao dịch tương ứng với một dãy. Chúng ta gọi đó là một dãy khách hàng (customer-sequence). Ta biểu thị các giao dịch của một khách hàng được sắp xếp thứ tự tăng dần theo thời gian là (T1, T2, ..., Tn). Tập các phần tử (item) trong Ti được biểu thị bởi itemset(Ti). Dãy customer-sequence của một khách hàng là một dãy . Một khách hàng hỗ trợ một dãy s nếu s được chứa trong dãy customer-sequence đối với khách hàng đó. Độ hỗ trợ của một dãy được định nghĩa là số khách hàng hỗ trợ dãy đó. Các dãy tối đa trong số tất cả các dãy phổ biến đáp ứng mức hỗ trợ tối thiểu cụ thể nào đó được gọi là luật dãy hay mẫu dãy (sequential patterns). [1] Ta gọi dãy đáp ứng độ hỗ trợ tối thiểu là dãy phổ biến (large sequence)  Ví dụ Cho CSDL mua bán hàng thể hiện trong hình 1.1. Transaction Time Customer Id Items Bought June 10 '93 June 12 '93 June 15 '93 June 20 '93 June 25 '93 June 25 '93 June 25 '93 June 30 '93 June 30 '93 July 25 '93 2 5 2 2 4 3 1 1 4 4 10, 20 90 30 40, 60, 70 30 30, 50, 70 30 90 40, 70 90 Hình 1.1: CSDL gốc CSDL trong hình 1.2 đã được sắp xếp theo mã khách hàng (customer-id) và thời gian giao dịch. Customer Id Transaction Time Items Bought 1 June 25 '93 30 - 14 - Khai phá luật dãy Nguyễn Đình Văn 1 June 30 '93 90 2 2 2 June 10 '93 June 15 '93 June 20 '93 10, 20 30 40, 60, 70 3 June 25 '93 30, 50, 70 4 4 4 June 25 '93 June 30 '93 July 25 '93 30 40, 70 90 5 June 12 '93 90 Hình 1.2: CSDL được sắp xếp theo Khách hàng ID và thời gian giao dịch CSDL hình 1.3 thể hiện như là một tập các dãy khách hàng (customer-sequence). Customer Id Customer Sequence 1 2 3 4 5 Hình 1.3: CSDL theo dãy khách hàng (customer-sequence) Với mức hỗ trợ tối thiểu là 25%, tức là xuất hiện tối thiểu 2 trong tổng số 5 khách hàng, hai dãy và là lớn nhất trong số các dãy đáp ứng điều kiện giàng buộc hỗ trợ, và là các mẫu dãy mong muốn. Mẫu dãy xuất hiện trong các giao dịch của khách hàng 1 và 4. Mẫu dãy xuất hiện trong giao dịch của khách hàng 2 và 4.(Vì (40 70) là tập con của (40 60 70) nên cũng được tính cho khách hàng 2). Ví dụ về một dãy mà không có hỗ trợ tối thiểu là dãy , dãy này chỉ xuất hiện trong giao dịch của khách hàng 2. Các dãy , , , , , , mặc dù thỏa mãn hỗ trợ tối thiểu, nhưng chúng không phải dãy tối đa nên không phải là kết quả cần tìm. Sequential Patterns with support > 25% Hình 1.4: Tập kết quả 1.2.2 Một số ứng dụng  Khai phá dãy cho các mẫu hành vi người dùng trong lĩnh vực thương mại điện thoại di động [7] Sự phát triển của máy tính và các công nghệ truyền thông gần đây giúp cho các hệ thống liên lạc cá nhân (Personal Communication Systems - PCSs) ngày càng trở nên phổ biến, đặt ra vấn đề về quản lý thông tin di động. - 15 - Khai phá luật dãy Nguyễn Đình Văn Mô hình hóa một cách hiệu quả các mẫu hành vi của người sử dụng trong các hệ thống điện thoại di động đem lại lợi ích không chỉ cho người sử dụng trong những truy cập thông minh, mà còn đem lại lợi nhuận tài chính cho các nhà cung cấp dịch vụ di động như quảng cáo. Trong môi trường web, người sử dụng di động có thể yêu cầu các loại hình dịch vụ khác nhau và ứng dụng của điện thoại di động, PDA hay máy tính xách tay từ bất cứ đâu tại bất kỳ thời gian nào thông qua GSM, GPRS hoặc mạng không dây. Rõ ràng là những hành vi của người sử dụng điện thoại di động (trong đó vị trí và dịch vụ vốn đã cùng tồn tại) trở nên phức tạp hơn so với các hệ thống web truyền thống. Để giúp người sử dụng thu nhận được thông tin mong muốn trong một thời gian ngắn là một trong những ứng dụng nhiều hứa hẹn, đặc biệt khi mà người dùng không có nhiều thời gian để lướt nhiều trang web. Hệ thống quản lý thông tin di động lưu trữ và cập nhật các thông tin vị trí của người sử dụng điện thoại di động, những người được phục vụ bởi hệ thống. Một chủ đề nóng trong lĩnh vực nghiên cứu quản lý thông tin di động là dự đoán di động. Dự đoán di động có thể được định nghĩa là dự đoán vị trí di chuyển tiếp theo của người sử dụng di động giữa các vùng trong hệ thống liên lạc cá nhân PCS hoặc mạng GSM. Dự đoán đó có thể được sử dụng để tăng hiệu quả của PCSs. Sử dụng dự đoán di chuyển, hệ thống có thể phân bổ nguồn tài nguyên một cách hiệu quả khả năng di chuyển đến các vùng thay vì phân bổ nguồn tài nguyên một cách không có định hướng trong các vùng lân cận của người sử dụng điện thoại di động. Hiệu quả phân bổ nguồn tài nguyên cho người dùng di động sẽ cải thiện việc sử dụng tài nguyên và giảm độ trễ trong việc tiếp cận các nguồn tài nguyên. Dự báo chính xác thông tin vị trí cũng rất quan trọng trong xử lý các truy vấn phụ thuộc vào vị trí của người dùng di động. Khi người dùng đưa ra một truy vấn liên quan đến vị trí, câu trả lời cho truy vấn sẽ phụ thuộc vào vị trí hiện tại của người dùng. Nhiều phạm vi ứng dụng bao gồm cả lĩnh vực chăm sóc sức khỏe, khoa học sinh học, quản lý khách sạn, và lợi ích quân sự từ hiệu quả xử lý các truy vấn phụ thuộc vào vị trí. Với hiệu quả dự đoán về vị trí, có thể thể trả lời các truy vấn liên quan đến vị trí di chuyển tiếp theo của người sử dụng. So với số lượng công việc thực hiện cho việc cập nhật vị trí, một số ít đã được thực hiện trong lĩnh vực dự báo di chuyển. Những công việc này có một số hạn chế, được giải thích như sau:  Một số trong đó là sự không nỗ lực tìm kiếm các mẫu thông tin di động. Thay vào đó, các mẫu này được giả định là có sẵn. Những mẫu này sau đó được sử dụng để dự báo di chuyển.  Việc dự đoán được dựa trên khả năng phân bố của tốc độ và hướng của người sử dụng điện thoại di động. Để thu thập những thông tin như vậy, cần thiết phải có những công cụ rất tinh vi và tốn kém như hệ thống định vị toàn cầu (Global Positioning System - GPS). - 16 - Khai phá luật dãy Nguyễn Đình Văn Nhằm khắc phục những hạn chế trên, người ta đã phát triển một thuật toán dự đoán di động hiệu quả. Những qui luật này được gọi là các mẫu di động. Sau đó, các luật di động này được trích xuất ra từ các mẫu di động. Các quy tắc di động được gắn với quỹ đạo hiện tại của một người sử dụng điện thoại di động, và được sử dụng cho các dự đoán hướng di chuyển tiếp theo của người dùng. Thuật toán dự đoán này là khai phá các mẫu di động của người dùng và sinh ra các luật di động, được thực hiện offline bởi hệ thống. Tuy nhiên, dự báo di chuyển được thực hiện online. Điều đó có nghĩa là bất cứ khi nào người dùng có ý định thực hiện một di chuyển trong một khu vực nhất định, một yêu cầu dự đoán sẽ được gửi đến hệ thống và dự đoán được thực hiện bởi hệ thống bằng cách sử dụng các luật di động dựa trên thuật toán dự đoán. Hình 1.5: Kiến trúc tổng thể của hệ thống quản lý thông tin di động 1.2.3 Luật dãy và luật kết hợp: một số đối sánh Vấn đề của luật kết hợp là tìm kiếm các mẫu thường xuyên, các liên kết, các mối tương quan, hoặc các cấu trúc có quan hệ nhân quả giữa tập các phần tử hoặc các đối tượng trong các CSDL giao dịch, CSDL quan hệ, các kho thông tin khác. Lĩnh vực khai phá luật kết hợp được phát triển với nhiều mục đích như thực hiện phân tích thói quen mua bán hàng, trong đó cần tìm những mặt hàng được mua với nhau nhiều nhất. Như trong khai phá web, khai phá luật kết hợp tìm các trang web liên quan được truy cập theo đợt, điều đó sẽ cung cấp những ước tính nhất định về xác suất truy cập web. Ví dụ như “Nếu một người truy cập trang CNN thì có đến 60% khả năng họ sẽ truy cập trang ABC News trong tháng đó”. Trong khi đó, vấn đề của luật dãy là tìm kiếm các mẫu có liên quan đến yếu tố thời gian trên một CSDL dãy (các phần tử được sắp thứ tự), ví dụ như CSDL nhật ký duyệt web. Khai phá luật dãy được xem là mở rộng của khai phá luật kết hợp, vì luật kết hợp chỉ khảo sát các mẫu không có liên quan đến yếu tố thời gian. Khai phá luật dãy có vai trò rất quan trọng trong nhiều ứng dụng thực tế, ví dụ như việc phát hiện tri - 17 - Khai phá luật dãy Nguyễn Đình Văn thức trong dữ liệu nhật ký web, do nhật ký web được sắp xếp theo thời gian. Khi đó, khai phá luật dãy có thể cho kết quả như “Nếu người dùng truy cập trang X, sau đó truy cập trang Y, thì c% khả năng sẽ truy cập trang Z”. 1.2.4 Sơ bộ về các phương pháp khai phá luật dãy  Phương pháp dựa trên Apriori (Apriori-based method) Thuật toán GSP dựa trên nguyên tắc duyệt dữ liệu theo chiều rộng (breadth-first), mở rộng của mô hình A-priori. Thuật toán GSP sử dụng phương pháp “Tạo – Tỉa” (“Generating-Pruning”) được định nghĩa trong (Agrawal và cộng sự, 1993.) và thực hiện theo cách sau đây. Dãy ứng viên có độ dài (k +1) được tạo ra sử dụng phép nối hai dãy phổ biến, s1 và s2, có độ dài k, nếu dãy con thu được bằng cách lược bỏ phần tử đầu tiên của s1 trùng với dãy con thu được bằng cách lược bỏ phần tử cuối cùng của s2. Với ví dụ trong Hình 1.6, và k = 2, ta có s1 là và s2 là <(DVD- R) (Video Soft)>, khi đó dãy ứng viên sẽ là bởi dãy con được nói đến ở trên là (chung của s1 và s2). Một phương pháp khác sử dụng nguyên lý "Generating-Pruning" là PSP (Masseglia et al., 1998). Sự khác biệt chính với GSP là các ứng viên cũng như các dãy phổ biến được quản lý trong một cấu trúc hiệu quả hơn. Các phương pháp trình bày cho đến nay được thiết kế để phụ thuộc ít nhất có thể vào bộ nhớ chính. Vì chúng cần phải tải toàn bộ CSDL (hoặc một ánh xạ của CSDL) trong bộ nhớ chính. Phương pháp này đạt hiệu quả cao khi CSDL có thể phù hợp với bộ nhớ. Cust June 04, 2004 June 05, 2004 June 06, 2004 June 07, 2004 C1 Camcorder, MiniDV Digital Camera MemCard USB Key C2 Camcorder, MiniDV DVD Rec, DVD-R Video Soft C3 DVD Rec, DVD-R MemCard Video Soft USB Key C4 Camcorder, MiniDV Laptop DVD Rec, DVD-R Hình 1.6: Các dãy dữ liệu của 4 khách hàng mua trong 4 ngày  Phương pháp dựa trên định dạng dọc (Vertical format-based method) Trong (Zaki, 2001), tác giả đề xuất thuật toán SPADE (Sequential PAttern Discovery using Equivalent Class – Khai phá mẫu dãy sử dụng lớp tương đương). Ý tưởng chính của phương pháp này là một phân cụm các dãy phổ biến dựa trên các tiền tố phổ biến của chúng và tính các dãy ứng viên nhờ một ánh xạ của CSDL (nạp trong bộ nhớ chính). SPADE chỉ cần quét CSDL ba lần để trích xuất các mẫu dãy. Lần quét đầu tiên nhằm tìm kiếm các phần tử thường xuyên, lần thứ hai để tìm kiếm các dãy phổ biến có độ dài 2 (length 2) và lần cuối cùng để kết hợp các dãy phổ biến có độ dài 2, một bảng chứa định danh tương ứng của các dãy và tập các phần tử trong CSDL (ví dụ như dữ liệu dãy có chứa các dãy phổ biến và mốc thời gian tương ứng). Dựa trên những biểu diễn này trong bộ nhớ chính, độ hỗ trợ của các dãy ứng viên có độ dài k là kết quả của phép nối (join) trên các bảng liên quan đến các dãy phổ biến có độ dài (k - 1) có thể sinh ra ứng viên này (như vậy, mọi thao tác sau khi khai phá các dãy phổ - 18 - Khai phá luật dãy Nguyễn Đình Văn biến có chiều dài 2 được thực hiện trong bộ nhớ). SPAM (Ayres et al., 2002) là một phương pháp khác mà cần phải ánh xạ CSDL trong bộ nhớ chính. Các tác giả đã đề xuất ánh xạ CSDL theo không gian điểm ảnh định dạng dọc (vertical bitmap) cho việc thể hiện các ứng viên và tính độ hỗ trợ.  Các phương pháp dựa trên việc phát triển mẫu (Pattern growth based methods) Một cách tiếp cận khởi đầu cho khai thác mẫu dãy thực hiện phép chiếu đệ quy các dữ liệu dãy thành các CSDL nhỏ hơn. Đề xuất trong (Han et al., 2000), FreeSpan là thuật toán đầu tiên xem xét phương pháp quy chiếu mẫu (pattern-projection) trong khai phá mẫu dãy. Công trình được tiếp tục với PrefixSpan, (Pei et al., 2001), dựa trên nghiên cứu về số lượng các ứng viên được đề xuất bởi phương pháp Generating- Pruning. Bắt đầu từ các phần tử thường xuyên của CSDL, PrefixSpan sinh ra CSDL quy chiếu với phần dữ liệu dãy còn lại. Các CSDL quy chiếu như vậy chứa các hậu tố của dữ liệu dãy từ CSDL gốc, được nhóm theo các tiền tố. Quá trình này được lặp đi lặp lại một cách đệ quy cho đến khi không có phần tử thường xuyên nào được tìm thấy trong các CSDL quy chiếu. Ở mức này, mẫu dãy phổ biến là đường đi của các phần tử thường xuyên đến CSDL quy chiếu đó.  Các mẫu dãy đóng (Closed Sequential Patterns) Mẫu dãy đóng là mẫu dãy mà không được chứa trong mẫu dãy khác có cùng mức hỗ trợ. Xét CSDL minh họa trong hình 1.6, mẫu dãy phổ biến <(DVD Rec) (Video Soft)> không phải là mẫu dãy đóng vì nó được chứa trong mẫu dãy s2 và có cùng độ hỗ trợ (50%). Mặt khác, mẫu dãy là mẫu dãy đóng vì nó được chứa trong mẫu dãy s1 nhưng có độ hỗ trợ là 75%, khác với độ hỗ trợ của s1 là 50%. Thuật toán đầu tiên cho việc trích xuất các mẫu dãy đóng là CloSpan (Yan et al., 2003) với việc phát hiện các mẫu tuần tự không đóng, tránh được một số lượng lớn các lần gọi đệ quy. Thuật toán CloSpan dựa trên việc phát hiện các mẫu tuần tự có độ dài 2, ví dụ như “A luôn xảy ra trước hoặc sau B”. Xét CSDL trong hình 1.6, chúng ta biết rằng là một mẫu thường xuyên. Các tác giả của thuật toán CloSpan đề xuất các phương pháp liên quan để chứng minh rằng luôn luôn xảy ra trước . Dựa vào quan sát này, CloSpan có thể chỉ ra rằng là mẫu thường xuyên mà không cần bất kỳ lần quét CSDL nào nữa. Thuật toán BIDE (Wang và Han, 2004) là mở rộng của thuật toán CloSpan như sau. Đầu tiên, thông qua một phần mở rộng dãy mới, được gọi là BI-Directional Extension, thuật toán sử dụng cả hai phương pháp là mẫu tiền tố và kiểm tra thuộc tính đóng để phát triển. Thứ hai, để lược bớt không gian tìm kiếm sâu hơn so với phương pháp tiếp cận trước, thuật toán đề nghị một phương pháp lược bớt gọi là BackScan. Ý tưởng chính của phương pháp này là để tránh mở rộng dãy bằng cách phát hiện trước phần mở rộng đã được chứa trong một dãy rồi. - 19 - Khai phá luật dãy Nguyễn Đình Văn  Khai phá mẫu dãy tăng dần (Incremental Mining of Sequential Patterns) Khi CSDL phát triển, vấn đề duy trì các mẫu dãy trong một thời gian dài trở nên rất cần thiết vì một số lượng lớn các bản ghi mới có thể được thêm vào CSDL. Để phản ánh hiện trạng của CSDL, ở đó các mẫu dãy trước đó sẽ trở nên không thích hợp và các mẫu dãy mới có thể xuất hiện, các cách tiếp cận hiệu quả mới đã được đề xuất. (Masseglia et al, 2003.) đề xuất một giải thuật hiệu quả, được gọi là ISE, để tính toán các dãy phổ biến trong CSDL cập nhật. Giải thuật ISE giảm thiểu chi phí tính toán bằng cách tái sử dụng các thông tin tối thiểu từ các dãy phổ biến cũ, tức là độ hỗ trợ của các dãy phổ biến. Các tính năng chính mới của ISE là tập các dãy ứng viên cần kiểm tra được giảm đáng kể. Các thuật toán SPADE đã được mở rộng trong thuật toán ISM (Parthasarathy et al, 1999.). Để cập nhật mức hỗ trợ và liệt kê các dãy phổ biến, ISM duy trì “các dãy phổ biến tối đa” (“maximally frequent sequences”) và “các dãy không thường xuyên tối thiểu” (“minimally infrequent sequences”). KISP (Lin và Lee, 2003) cũng đề xuất để tận dụng những kiến thức đã được tính toán trước và tạo ra một nền tảng kiến thức cho các truy vấn bổ sung về mẫu dãy và các giá trị hỗ trợ khác nhau.  Mở rộng vấn đề dựa trên việc trích xuất các mẫu dãy (Extended Problems Based on the Sequential Pattern Extraction) Được thúc đẩy bởi các ứng dụng tiềm năng cho khai phá mẫu dãy, nhiều mở rộng của định nghĩa ban đầu đã được đề xuất có thể liên quan đến việc bổ sung các ràng buộc hoặc định dạng của các mẫu. Trong (Pei et al., 2002) tác giả đã liệt kê một số những ràng buộc hữu ích nhất cho việc trích xuất các mẫu dãy. Những ràng buộc này có thể được xem như là những bộ lọc được áp dụng cho việc trích xuất các mẫu, nhưng hầu hết các phương pháp thông thường dùng chúng cho việc liệt kê trong suốt quá trình xử lý. Các bộ lọc này có thể liên quan tới các phần tử (“trích xuất các mẫu chỉ chứa các phần tử Camcorder”) hoặc theo độ dài của mẫu. Định nghĩa mẫu dãy cũng đã được điều chỉnh bởi một số nghiên cứu. Ví dụ (Kum et al., 2003) đã đề xuất ApproxMap để khai phá các mẫu dãy gần đúng. ApproxMap đầu tiên đề xuất phân cụm dữ liệu dãy dựa trên các phần tử của chúng. Sau đó, mỗi cụm ApproxMap cho phép trích xuất các mẫu dãy gần đúng liên quan tới các cụm này. Ta xét các CSDL trong hình 1.6 như một cluster. Bước đầu tiên của quá trình trích xuất là cung cấp các dữ liệu dãy của cluster với một sự liên kết tương tự như của tin sinh học. Camcorder, MiniDV DigiCam MemCard USB Key Camcorder, MiniDV DVD Rec, DVD-R Video Soft DVD Rec, DVD-R MemCard Video Soft USB Key Camcorder, MiniDV Laptop DVD Rec, DVD-R - 20 - Khai phá luật dãy Nguyễn Đình Văn Camcorder: 3 MiniDV: 3 DigiCam: 1 Laptop: 1 DVD Rec: 3 DVD-R: 3 MemCard: 2 Video Soft: 2 USB Key: 2 Hình 1.7: Các liên được đề xuất đối với dữ liệu dãy của Hình 1.6 Dãy cuối cùng trong Hình 1.7 thể hiện dãy trọng số thu được bởi ApproxMap trên dãy Hình 1.6. Với độ hỗ trợ 50%, dãy trọng số cho các mẫu gần đúng được đưa ra như sau: <(Camcorder: 3, MiniDV: 3) (DVD Rec: 3, DVD-R: 3) (MemCard: 2) (Video Soft: 2) (USB Key: 2)>. - 21 - Khai phá luật dãy Nguyễn Đình Văn CHƯƠNG 2 – CÁC PHƯƠNG PHÁP KHAI PHÁ LUẬT DÃY 2.1 Khái quát về khai phá luật dãy Khai phá luật dãy xử lý dữ liệu điển hình là các dãy [3] (một dãy là một tập hợp các phần tử được sắp thứ tự). So với vấn đề luật kết hợp, luật dãy nghiên cứu dữ liệu đưa ra các phân tích “liên giao dịch” (inter-transaction) [1]. Có rất nhiều ứng dụng về khai phá mẫu dãy và vấn đề cũng được định nghĩa theo những cách khác nhau với mức độ thay đổi không đáng kể. Kết hợp với các giải pháp hiệu quả, những vấn đề này có thể phù hợp với dữ liệu thực tế có mốc thời gian (timestamp) (khi mà luật kết hợp đã không giải quyết được) và cung cấp những kết quả hữu ích. Ta sử dụng CSDL giao dịch mua bán hàng làm ví dụ, với các thông tin về: định danh của dãy hoặc định danh khách hàng (sequence-id or customer-id), thời gian giao dịch (transaction-time) và mặt hàng liên quan trong giao dịch (item). Một CSDL như vậy được gọi là CSDL dãy. Chính xác hơn, mỗi giao dịch là một tập hợp các mặt hàng (itemset) và mỗi dãy là một danh sách các giao dịch được sắp xếp theo thời gian giao dịch. Đối với hiệu quả của việc trợ giúp ra quyết định, mục đích là để tìm ra những thói quen tiêu biểu của người dùng. Để làm được việc đó, đòi hỏi phải có một CSDL dãy và đưa ra giá trị hỗ trợ tức là số lần xuất hiện trong CSDL. Một mẫu dãy phổ biến là một dãy mà tần xuất xuất hiện trong CSDL vượt ngưỡng quy định. Vấn đề tìm kiếm tất cả các mẫu thường xuyên từ lượng dữ liệu khổng lồ đòi hỏi chi phí về mặt thời gian là rất lớn. Thông thường, việc kiểm tra của tất cả các kết hợp có thể trong dữ liệu là vấn đề khó và những thuật toán mới tập trung vào dữ liệu dãy được coi là quan trọng đối với một tổ chức. Khai phá luật dãy có thể được áp dụng rộng rãi trên các ứng dụng từ nhiều loại dữ liệu có thời gian liên quan. Ví dụ, từ một CSDL mua bán hàng, một mẫu dãy có thể được dùng để phát triển các chiến lược tiếp thị và sản phẩm; Bằng cách phân tích weblog, các mẫu dãy rất hữu ích cho việc xây dựng website công ty giúp khách hàng truy cập một cách dễ dàng các liên kết phổ biến nhất (Kosala và Blockeel, 2000); Ta cũng có thể thấy CSDL báo động mạng viễn thông, phát hiện xâm nhập (Hu và Panda, 2004), các dãy ADN (Zaki, 2003), … Chúng ta chia vấn đề khai phá luật dãy thành các giai đoạn sau đây:  Giai đoạn sắp xếp (Sort Phase): CSDL (D) được sắp xếp, với mã khách hàng (custorm-id) là khóa chính và thời gian giao dịch (transaction-time) là khóa phụ. Bước này chuyển đổi ngầm cơ sơ dữ liệu giao dịch gốc thành CSDL dãy khách hàng.  Giai đoạn Litemset (Litemset Phase): Trong giai đoạn này, chúng ta tìm tập tất cả litemsets L, đồng thời cũng tìm kiếm tập tất cả các dãy phổ biến 1-sequence, vì tập này cũng là { | l  L}. - 22 - Khai phá luật dãy Nguyễn Đình Văn Với giao dịch của một khách hàng, độ hỗ trợ được tính tăng lên chỉ một lần ngay cả khi khách hàng mua cùng một tập các sản phẩm trong hai hay nhiều giao dịch khác nhau. Tập hợp các litemsets được ánh xạ tới một tập hợp các số nguyên liên tiếp. Sau bước xử lý litemsets để có được các thực thể duy nhất, việc ánh xạ này giúp ta có thể so sánh hai litemsets có bằng nhau hay không trong thời gian cố định, và giảm số lần cần thiết để kiểm tra nếu một dãy được chứa trong dãy khách hàng.  Giai đoạn chuyển đổi (Transformation Phase): Như chúng ta sẽ thấy trong giai đoạn dãy (Sequence Phase), cần phải xác định lặp đi lặp lại nhiều lần để đưa ra một tập các dãy phổ biến (large sequences) được chứa trong một dãy khách hàng. Để thực hiện điều này một cách nhanh chóng, ta chuyển đổi mỗi dãy khách hàng thành một đại diện thay thế. Trong một dãy khách hàng được chuyển đổi, mỗi giao dịch được thay thế bằng tập tất cả các litemsets được chứa trong giao dịch đó. Nếu một giao dịch không chứa bất kỳ litemset nào, nó không được giữ lại trong dãy chuyển đổi. Nếu một dãy khách hàng không chứa bất kỳ litemset nào thì dãy này bị loại bỏ trong CSDL chuyển đổi. Tuy nhiên, nó vẫn góp phần vào việc tính tổng số lượng khách hàng. Một dãy các khách hàng khi đó được thể hiện bởi một danh sách tập các litemsets. Mỗi tập litemsets được biểu diễn bởi {l1, l2, ..., ln}, trong đó li là một litemset. CSDL chuyển đổi này gọi là DT. Tiếp tục sử dụng CSDL trong phần 1.2 làm ví dụ, việc chuyển đổi CSDL Hình 1.3 được thể hiện trong Hình 2.1. Ví dụ, trong trong việc chuyển đổi dãy khách hàng với Id 2, giao dịch (10 20) bị loại bỏ vì nó không chứa bất kỳ litemset nào và giao dịch (40 60 70) được thay thế bằng tập litemsets {(40),(70), (40 70)}. Customer Id Original Customer Sequence Transformed Customer Sequence After Mapping 1 2 3 4 5 < (10 20) (30) (40 60 70) > < {(30)} {(40), (70), (40 70)}> < {(30)} {(40), (70), (40 70)} {(90)}> <{1} {2,3,4} {5}> Hình 2.1: CSDL đã được chuyển đổi từ Hình 1.3  Giai đoạn dãy (Sequence Phase): Ta sử dụng tập các litemsets để tìm các dãy ứng viên. Cấu trúc chung là thực hiện các quá trình duyệt lặp đi lặp lại trên dữ liệu. Trong mỗi lần duyệt, ta bắt đầu với một tập khởi tạo các dãy phổ biến. Ta sử dụng tập khởi tạo này để sinh ra các dãy phổ biến mới, tiềm năng, gọi là các dãy ứng viên (candidate sequences). Tìm độ hỗ trợ cho các dãy ứng viên này trong suốt quá trình duyệt dữ liệu. - 23 - Khai phá luật dãy Nguyễn Đình Văn Tại lần duyệt cuối cùng của mỗi bước, xác định dãy nào trong các dãy ứng viên là dãy phổ biến thực sự. Các dãy ứng viên phổ biến trở thành khởi tạo cho lần duyệt tiếp theo. Trong lần duyệt đầu tiên, tất cả các 1-sequences với độ hỗ trợ tối thiểu, được chứa trong giai đoạn litemset, tạo nên tập khởi tạo.  Giai đoạn tìm dãy tối đa (Maximal Phase): Tìm các dãy tối đa trong tập các dãy phổ biến (large sequences). Giai đoạn này được kết hợp với giai đoạn dãy (Sequence Phase) để giảm chi phí thời gian trong việc tính các dãy không tối đa. Tập tất cả các dãy phổ biến S được tìm thấy trong giai đoạn dãy, thuật toán tiếp theo đây có thể được sử dụng để tìm các dãy tối đa. Với n là độ dài của dãy dài nhất. for ( k = n; k > 1; k – – ) do foreach k-sequence sk do Delete from S all subsequences of sk 2.2 Các thuật toán khởi thủy Phần này giới thiệu ba thuật toán cơ bản khai phá luật dãy bao gồm: AprioriAll, AprioriSome, GSP. Đây là những thuật toán rất phổ biến trong khai phá luật dãy. 2.2.1 Thuật toán AprioriAll  Thuật toán AprioriAll L1 = {large 1-sequences}; // Result of the litemset phase for ( k = 2; Lk-1 ≠Ø; k++ ) do begin Ck New candidates generated from Lk-1 (see Apriori Candidate Generation). foreach customer-sequence c in the database do Increment the count of all candidates in Ck that are contained in c. Lk = Candidates in Ck with minimum support. end Answer = Maximal Sequences in k Lk; Hình 2.2: Thuật toán AprioriAll Trong mỗi lần duyệt, ta sử dụng các dãy phổ biến từ lần duyệt trước đó để tạo ra các dãy ứng viên, sau đó tính độ hỗ trợ của chúng bằng cách duyệt toàn bộ CSDL. Tại lần duyệt cuối cùng tại mỗi bước, độ hỗ trợ của các ứng viên được sử dụng để xác định các dãy phổ biến cho bước tiếp theo. Trong lần duyệt đầu tiên, đầu ra của giai đoạn litemset được sử dụng để khởi tạo tập các dãy phổ biến 1-sequences. - 24 - Khai phá luật dãy Nguyễn Đình Văn  Sinh các dãy ứng viên (Apriori Candidate Generation): Hàm apriori-generate có dữ liệu đầu vào là Lk-1: tập tất cả các dãy phổ biến (k-1)-sequences. Hàm thực hiện như sau: insert into Ck select p.litemset1, p.litemset2, ..., p.litemsetk-1, q.litemsetk-1 from Lk-1 p, Lk-1 q where p.litemset1 = q.litemset1, . . ., p.litemsetk-2 = q.litemsetk-2; Next, delete all sequences c  Ck such that some (k-1)-subsequence of c is not in Lk-1: forall sequences c  Ck do forall (k-1)-subsequences s of c do if (s  Lk-1) then delete c from Ck; Hình 2.3: Hàm apriori-generate Tiếp tục với CSDL trong phần 1.2, xét tập các dãy 3-sequences L3 trong Hình 2.4. Nếu L3 được lấy làm đầu vào cho hàm apriori-generate, ta sẽ nhận được các dãy như trong hình 2.5 sau khi thực hiện phép nối. Sau khi lược bớt các dãy có dãy con không thuộc L3 ta được kết quả là các dãy trong hình 2.6. Ví dụ, dãy bị lược bỏ đi vì có dãy con không thuộc L3. Sequence Support 2 2 3 2 2 Hình 2.4: Large 3-Sequences Hình 2.5: Candidate 4-Sequences (after join) Hình 2.6: Candidate 4-Sequences (after pruning) Ta cần chứng minh rằng Ck  Lk. Rõ ràng là bất kỳ dãy con nào của một dãy phổ biến cũng cần có độ hỗ trợ tối thiểu. Do đó, nếu ta mở rộng mỗi dãy trong Lk-1 với tất cả tập các phần tử phổ biến có thể, sau đó xóa tất cả những dãy mà có dãy con (k-1)- - 25 - Khai phá luật dãy Nguyễn Đình Văn subsequences của chúng mà không nằm trong Lk-1, điều này có thể không đúng với một superset của các dãy trong Lk. Phép nối này tương đương với việc mở rộng Lk-1 với mỗi tập phần tử phổ biến và sau đó lược bỏ các dãy mà có dãy con (k-1)-subsequences không nằm trong Lk-1. Vì vậy, sau bước thực hiện phép nối, Ck  Lk. Cũng với lập luận tương tự, tại bước lược bỏ, ta cũng xóa từ Ck tất cả các dãy mà có các dãy con (k-1)-subsequences không nằm trong Lk-1, và không xóa bất kỳ dãy nào có thể nằm trong Lk. Ví dụ: Xét CSDL với các dãy khách hàng trong hình 2.7. Các dãy khách hàng được chuyển đổi, ở đó mỗi giao dịch được thay thế bởi tập các litemsets chứa trong giao dịch và các litemsets được thay thế bởi các số nguyên. Độ hỗ trợ tối thiểu được đưa ra cụ thể là 40%. Lần duyệt đầu tiên trên CSDL được thực hiện trong giai đoạn litemset, và ta xác định được dãy phổ biến 1-sequences thể hiện trong hình 2.8. Sau khi kết thúc các lần duyệt thứ 2, 3, 4, các dãy phổ biến cùng với độ hỗ trợ của chúng được thể hiện trong các hình 2.9, hình 2.10, và hình 2.11 tương ứng. Không có ứng viên nào được tạo trong lần duyệt thứ 5. Các dãy phổ biến tối đa là ba dãy như hình 2.12. Hình 2.7: Dãy khách hàng Sequence Support 4 2 4 4 2 Hình 2.8: Dãy phổ biến 1-sequences Sequence Support 2 4 3 3 2 2 3 2 2 Hình 2.9: Dãy phổ biến 2-sequences - 26 - Khai phá luật dãy Nguyễn Đình Văn Sequence Support 2 2 3 2 2 Hình 2.10: Dãy phổ biến 3-sequences Sequence Support 2 Hình 2.11: Dãy phổ biến 4-sequences Sequence Support 2 2 2 Hình 2.12: Dãy phổ biến 5-sequences  Hàm tìm dãy con (Subsequence Function): Các dãy ứng viên Ck được lưu trữ bằng cây hash-tree, nút của hash-tree hoặc là chứa danh sách các dãy (nút lá) hoặc chứa một bảng băm (nút trung gian). Trong nút trung gian, mỗi bucket của bảng băm trỏ tới một nút khác. Gốc của hash-tree được định nghĩa có độ sâu là 1. Một nút trung gian tại độ sâu d trỏ tới các nút có độ sâu d + 1. Các dãy được lưu trữ tại các lá. Khi ta thêm một dãy c, ta sẽ bắt đầu từ gốc và duyệt xuống cho tới khi đến lá cây. Tại một cây trung gian có độ sâu d, ta quyết định chọn nhánh nào để đi tiếp bằng cách áp dụng một hàm băm cho litemset thứ d của dãy. Tất cả các nút được tạo ban đầu là những nút lá. Khi số lượng dãy trong một nút lá vượt quá ngưỡng thì nút lá được chuyển thành nút trung gian. Bắt đầu từ nút gốc, hàm tìm dãy con (subsequence function) tìm tất cả các ứng viên được chứa trong dãy khách hàng c. Nếu ta đang ở nút lá, ta tìm các dãy trong nút lá được chứa trong dãy c và bổ sung tham chiếu tới chúng vào tập kết quả. Nếu ta đang ở tại nút trung gian và đã đạt được bằng cách băm litemset i, ta thực hiện băm trên mỗi litemset trong c mà xuất hiện trong một giao dịch sau khi giao dịch chứa i và áp dụng đệ quy thủ tục này cho các nút trong bucket tương ứng. Đối với nút gốc, ta thực hiện băm trên mọi litemset trong c. Để thấy tại sao hàm tìm dãy con trả về tập các tham chiếu mong muốn, xem xét những gì xảy ra tại nút gốc. Đối với bất kỳ dãy s nào được chứa trong dãy khách hàng c, litemset đầu tiên của s phải ở trong c. Tại nút gốc, bằng cách băm trên mỗi litemset trong c, ta đảm bảo rằng chỉ bỏ qua các dãy mà bắt đầu bằng một litemset không nằm trong c. Lập luận tương tự áp dụng ở độ sâu hơn. Chỉ bổ sung nhân tố đó khi các litemsets trong bất kỳ dãy ứng viên hoặc dãy phổ biến thể hiện cho một tập các phần tử được mua trong các giao dịch khác nhau, nếu chúng ta đạt đến nút hiện hành bằng - 27 - Khai phá luật dãy Nguyễn Đình Văn cách băm litemset i, ta chỉ cần xem xét các litemsets trong c xảy ra trong các giao dịch sau khi các giao dịch có chứa i. 2.2.2 Thuật toán AprioriSome  Thuật toán AprioriSome được trình bày như sau: // Forward Phase L1 = {large 1-sequences}; // Result of the litemset phase C1 = L1; // so that we have a nice loop condition last = 1; // we last counted Clast for ( k = 2; Ck-1 ≠ Ø and Llast ≠ Ø; k++ ) do begin if (Lk-1 known) then Ck = New candidates generated from Lk-1; else Ck = New candidates generated from Ck-1; if ( k = = next(last) ) then begin foreach customer-sequence c in the database do Increment the count of all candidates in Ck that are contained in c. Lk = Candidates in Ck with minimum support. last = k; end end // Backward Phase for ( k – – ; k >= 1; k – – ) do if ( Lk was not determined in the forward phase ) then begin Delete all sequences in Ck contained in some Li, i > k; foreach customer-sequence c in DT do Increment the count of all candidates in Ck that are contained in c. - 28 - Khai phá luật dãy Nguyễn Đình Văn Lk = Candidates in Ck with minimum support. end else begin // Lk already known Delete all sequences in Lk contained in some Li, i > k. end Answer = k Lk; Hình 2.13: Thuật toán AprioriSome Trong giai đoạn duyệt xuôi (forward pass), chúng ta chỉ tính các dãy có độ dài nhất định. Ví dụ, chúng ta có thể tính các dãy độ dài 1, 2, 4 và 6 trong các lần duyệt xuôi và tính các dãy độ dài 3 và 5 trong các lần duyệt ngược. Hàm next có tham số là độ dài của dãy được tính trong lần duyệt trước và trả về độ dài của dãy trong lần duyệt tiếp theo. Vì vậy, hàm này xác định chính xác các dãy được tính, và cân bằng một cách tốt nhất giữa chi phí thời gian trong việc tính các dãy không tối đa và việc tính phần mở rộng của các dãy ứng viên không phổ biến. Một hạn chế là next(k) = k +1 (k là chiều dài mà ứng viên đã được tính trước đó), khi tất cả các dãy không tối đa được tính, nhưng không tính cho mở rộng của các dãy ứng viên không phổ biến. Trong trường hợp này, thuật toán AprioriSome suy biến thành AprioriAll. Một hạn chế khác, hàm next(k) = 100 * k, trong khi hầu như không tính các dãy phổ biến không tối đa, nhưng rất nhiều mở rộng của các ứng viên không phổ biến được tính. function next(k: integer) begin if (hitk < 0.666) return k + 1; elsif (hitk < 0.75) return k + 2; elsif (hitk < 0.80) return k + 3; elsif (hitk < 0.85) return k + 4; else return k + 5; end Lấy hitk biểu thị tỷ lệ giữa số lượng các dãy phổ biến k-sequences với số lượng các dãy ứng viên k-sequences (tức là |Lk| / |Ck|). Chúng ta sử dụng hàm next trong các thử nghiệm dưới đây. Bằng trực quan và kinh nghiệm cho thấy rằng, tỷ lệ về số lượng các ứng viên trong lần duyệt hiện tại có độ hỗ trợ tối thiểu tăng lên, chi phí thời gian tính cho phần mở rộng của các dãy ứng viên không phổ biến giảm xuống khi chúng ta bỏ qua độ dài. Ta sử dụng hàm apriori-generate đã nêu trong phần 2.2.1 để tạo ra các dãy ứng viên mới. Tuy nhiên, tại lần duyệt thứ k, ta không có được tập dãy phổ biến Lk-1 sẵn có - 29 - Khai phá luật dãy Nguyễn Đình Văn vì ta đã không tính các dãy ứng viên (k – 1)-candidate. Trong trường hợp này, ta sử dụng tập Ck-1 các ứng viên để tạo ra Ck , điều đó hoàn toàn đúng vì Ck-1  Lk-1 Trong giai đoạn duyệt ngược (backward phase), chúng ta tính các dãy có độ dài mà ta đã bỏ qua trong suốt giai đoạn duyệt xuôi, sau lần loại bỏ đầu tiên tất cả các dãy được chứa trong một số dãy phổ biến. Các dãy không phổ biến không thể được lựa chọn vì ta chỉ quan tâm đến các dãy tối đa. Ta cũng loại bỏ các dãy phổ biến không phải dãy tối đa được tìm thấy trong giai đoạn xuôi. Khi thực thi, các giai đoạn duyệt xuôi và duyệt ngược được xen kẽ để giảm bộ nhớ sử dụng cho việc lưu trữ các ứng viên. Tuy nhiên, chúng ta đã bỏ qua chi tiết này trong hình 2.13 để đơn giản hóa việc trình bày. Hình 2.14: (C3) Hình 2.15: C3 sau khi loại bỏ các dãy con của L4  Ví dụ Sử dụng lại CSDL trong ví dụ ở thuật toán AprioriAll, ta tìm được dãy phổ biến 1-sequences, trong giai đoạn litemset, thể hiện trong hình 2.8 (lần duyệt đầu tiên trên CSDL). Để minh hoạ một cách đơn giản, f(k) = 2k. Trong lần duyệt thứ hai, ta tính C2 để có được L2 (hình 2.9). Sau lần duyệt thứ ba, gọi hàm apriori-generate với L2 làm tham số để có được C3. Các ứng viên trong C3 được thể hiện trong hình 2.14. Ta không tính C3, và do đó không sinh ra L3. Tiếp theo, gọi hàm apriori- generate với C3 làm tham số để có được C4, mà khi lược bớt, được kết quả C4 như hình 2.6. Sau khi tính C4 để có được L4 (hình 2.11), ta tiếp tục tạo ra C5 và cho kết quả C5 là rỗng. Sau đó chúng ta bắt đầu với giai đoạn duyệt ngược (backward phase). Không có gì bị loại bỏ từ L4 vì không có dãy lớn hơn. Ta đã bỏ qua việc tính mức hỗ trợ cho các dãy trong C3 ở giai đoạn xuôi (forward phase). Sau khi loại bỏ trong C3 những dãy là dãy con của các dãy trong L4, tức là các dãy con của , chúng ta thu được các dãy ở hình 2.12. Chúng sẽ được tính để nhận như là dãy phổ biến tối đa 3- sequences. Tiếp theo, tất cả các dãy trong L2 trừ được loại bỏ vì chúng được chứa trong một số dãy dài hơn. Cũng với lý do, tất cả các dãy trong L1 cũng được loại bỏ. - 30 - Khai phá luật dãy Nguyễn Đình Văn Trong ví dụ này, thuật toán AprioriSome chỉ tính hai dãy 3-sequences so với sáu dãy 3-sequences được tính bởi thuật toán AprioriAll, và nó không tính bất kỳ dãy nào không được tính bởi AprioriAll . Tuy nhiên, nhìn chung, thuật toán AprioriSome sẽ tính một số mở rộng của các dãy ứng viên không phổ biến, mà không được tính bởi AprioriAll. Điều đó sẽ xảy ra trong ví dụ này nếu C4 tạo ra từ C3 lớn hơn C4 tạo ra từ L3.  Nhận xét Ưu điểm chính của thuật toán AprioriSome so với AprioriAll là tránh được việc tính độ hỗ trợ của nhiều dãy không phải là lớn nhất. Tuy nhiên, lợi thế này sẽ bị giảm đi vì hai lý do. Thứ nhất, trong thuật toán AprioriAll sử dụng Lk-1 để sinh các dãy ứng viên Ck, trong khi thuật toán AprioriSome đôi lúc sử dụng Ck-1 để sinh Ck. Vì Ck-1  Lk-1, do đó số dãy ứng viên Ck được sinh sử dụng thuật toán AprioriSome có thể lớn hơn. Thứ hai, mặc dù AprioriSome bỏ qua việc tính các ứng viên ở một số độ dài, tuy nhiên chúng đã được sinh ra và lưu trữ trong bộ nhớ. Nếu bộ nhớ bị đầy, AprioriSome buộc phải tính tập các ứng viên cuối cùng được tạo ra. Điều này làm giảm độ chênh lệch giữa hai tập ứng viên thực sự được tính, và khi đó AprioriSome sẽ tương tự như AprioriAll. So sánh hiệu suất thực hiện giữa hai thuật toán AprioriSome và AprioriAll cho thấy AprioriSome hiện tốt hơn khi độ hỗ trợ ở các mức thấp hơn, vì có nhiều dãy phổ biến hơn, và do đó có nhiều dãy không tối đa hơn. 2.2.3 Thuật toán GSP (Generalized Sequential Patterns) Thuật toán GSP khai phá mẫu dãy tổng quát. Theo đánh giá dựa trên thực nghiệm sử dụng dữ liệu mô phỏng và dữ liệu thực tế cho thấy GSP là nhanh hơn nhiều lần so với thuật toán AprioriAll đã được giới thiệu ở trên. Có hai lý do chính [2]: - Thuật toán GSP tính số lượng ứng viên ít hơn so với AprioriAll - Thuật toán AprioriAll phải tìm kiếm lần đầu tập các phần tử phổ biến xuất hiện trong mỗi thành phần của một dãy trong thời gian chuyển đổi dữ liệu, và sau đó tìm trong dữ liệu chuyển đổi các dãy ứng viên tồn tại trong đó. Điều này thường dẫn đến chậm hơn so với tìm kiếm trực tiếp các dãy ứng viên. Cấu trúc cơ bản của thuật toán GSP tìm kiếm mẫu dãy là thuật toán duyệt dữ liệu nhiều lần, lần duyệt đầu tiên xác định độ hỗ trợ của từng phần tử, tức là số lượng dữ liệu dãy có chứa các phần tử. Kết thúc lần duyệt đầu tiên, thuật toán đưa ra được các phần tử thường xuyên, nghĩa là thỏa mãn độ hỗ trợ tối thiểu. Mỗi phần tử như vậy tiết lộ một dãy phổ biến 1-element chứa phần tử đó. Mỗi dãy con bắt đầu duyệt với tập khởi đầu là các dãy phổ biến được tìm thấy trong lần duyệt trước đó. Tập khởi đầu được sử dụng để sinh ra các dãy phổ biến tiềm năng mới, gọi là các dãy ứng viên. Mỗi dãy ứng viên có ít nhất một phần tử thuộc dãy khởi đầu, vì thế tất cả các dãy ứng viên - 31 - Khai phá luật dãy Nguyễn Đình Văn trong một lần duyệt sẽ có cùng số phần tử. Độ hỗ trợ cho các dãy ứng viên này được tìm thấy trong qúa trình duyệt dữ liệu. Kết thúc lần duyệt, thuật toán xác định các dãy ứng viên thường xuyên thực sự. Những ứng viên thường xuyên này trở thành tập khởi đầu cho lần duyệt tiếp theo. Thuật toán kết thúc khi không tìm được dãy phổ biến nào ở cuối lần duyệt, hoặc khi không có dãy ứng viên nào được sinh ra. Ta cần chỉ rõ hai điểm mấu chốt của thuật toán là cách sinh các dãy ứng viên (Candidate generation) và cách tính độ hỗ trợ để xác định dãy ứng viên (Counting candidates).  Sinh dãy ứng viên (Candidate Generation) Xét một dãy có k phần tử, gọi là k-sequence (nếu một phần tử xuất hiện nhiều lần trong các thành phần khác nhau của một dãy, mỗi lần xuất hiện được tính vào giá trị của k.). Gọi Lk biểu thị tập tất cả các dãy phổ biến k-sequence và Ck biểu thị tập các dãy ứng viên k-sequence. Cho Lk-1 là tập tất cả các dãy phổ biến (k-1)-sequence, ta cần tạo ra tập cha (superset) của tập tất cả các dãy phổ biến k-sequence. Đầu tiên, ta định nghĩa khái niệm về một dãy con liên tục. Định nghĩa: Cho dãy s = và một dãy con c, c là dãy con liên tục của s nếu thỏa mãn bất kỳ điều kiện nào sau đây [2]: 1. c nhận được từ s bằng cách lược bỏ phần tử s1 hoặc sn. 2. c nhận được từ s bằng cách lược bỏ một phần tử từ thành phần si mà si có ít nhất hai phần tử. 3. c là dãy con liên tục của c’, và c’ là dãy con liên tục của s. Ví dụ: Giả sử có dãy s = . Khi đó, các dãy con liên tục của s là ; ; . Các dãy không phải là dãy con liên tục của s như: ; Trong [1] cho thấy rằng, dữ liệu dãy có chứa dãy s cũng sẽ chứa bất kỳ dãy con liên tục nào của s. Nếu không có ràng buộc về khoảng thời gian tối đa max-gap, dữ liệu dãy sẽ chứa tất cả các dãy con của s (bao gồm cả các dãy con không liên tục). Đặc tính này cung cấp cơ sở cho thủ tục sinh dãy ứng viên. Thực hiện sinh các dãy ứng viên qua hai bước: 1. Giai đoạn nối (Join Phase): Thực hiện sinh các dãy ứng viên bằng phép nối Lk- 1 với Lk-1. Một dãy s1 nối với s2 nếu dãy con thu được bằng cách loại bỏ phần tử đầu tiên của s1 và dãy thu được bằng cách loại bỏ phần tử cuối cùng của s2 là giống nhau. Dãy ứng viên được sinh bằng phép nối s1 với s2 là dãy s1 được mở rộng với phần tử cuối cùng trong s2. Phần tử được thêm trở nên thành phần riêng biệt nếu đó là một thành phần riêng biệt trong s2, và một phần của - 32 - Khai phá luật dãy Nguyễn Đình Văn thành phần cuối cùng của s1 khác. Khi thực hiện nối L1 với L1, ta cần thêm vào phần tử trong s2 một phần của itemset cũng như một thành phần riêng biệt, vì cả hai và đều cho cùng một dãy khi loại bỏ phần tử đầu tiên. (Ta thấy rằng s1 và s2 là các dãy con liên tục của các dãy ứng viên mới.) 2. Giai đoạn thanh loại (Prune Phase): Ta loại bỏ các dãy ứng viên có dãy con liên tục (k-1)-subsequence mà có độ hỗ trợ nhỏ hơn độ hỗ trợ tối thiểu. Nếu không tính ràng buộc thời gian max-gap, ta cũng loại bỏ các dãy ứng viên mà có bất kỳ dãy con nào không thỏa mãn độ hỗ trợ tối thiểu. Ví dụ: Hình 2.16 cho thấy L3, và C4 sau khi thực hiện giai đoạn nối và thanh loại. Trong giai đoạn nối, dãy nối với để sinh ra dãy và nối với để sinh ra dãy . Các dãy còn lại không được nối với bất kỳ dãy nào trong L3. Chẳng hạn, dãy không được nối với bất kỳ dãy nào vì không có dãy nào có dạng hoặc . Trong giai đoạn thanh loại, dãy bị loại bỏ vì dãy con liên tục của nó là không thuộc L3. Candidate 4-Sequences Frequent 3-Sequences after join after pruning Hình 2.16: Ví dụ sinh dãy ứng viên  Tính độ hỗ trợ các ứng viên (Counting Candidates) Trong quá trình duyệt dữ liệu, ta đọc mỗi dữ liệu dãy tại một thời điểm và tăng độ hỗ trợ của các ứng viên có trong dữ liệu dãy. Như vậy, với một tập các dãy ứng viên C và một dữ liệu dãy d, ta cần tìm tất cả các dãy trong C có chứa d. Ta sử dụng hai kỹ thuật sau để giải quyết vấn đề này: 1. Sử dụng cấu trúc dữ liệu hash-tree để giảm số lượng các ứng viên trong C đã được kiểm tra cho một dữ liệu dãy. 2. Biến đổi đại diện của dữ liệu dãy d để có thể tìm kiếm ứng viên là dãy con của d một cách hiệu quả. Giảm số lượng các ứng viên cần kiểm tra: a. Thêm các dãy ứng viên vào hash-tree: Khi thêm một dãy s, ta bắt đầu đi từ nút gốc cho tới khi tìm được một nút lá. Tại nút trung gian có độ sâu p, ta lựa chọn nhánh tiếp theo bằng cách áp dụng một hàm băm cho phần tử thứ p của dãy. Lưu ý là ta áp dụng hàm băm đến phần tử thứ p, không phải là thành - 33 - Khai phá luật dãy Nguyễn Đình Văn phần thứ p. Tất cả các nút được khởi tạo bước đầu là các nút lá. Khi số lượng các dãy trong một nút lá vượt quá một ngưỡng, nút lá khi đó được chuyển đến nút trung gian. b. Tìm các dãy ứng viên được chứa trong dữ liệu dãy: Bắt đầu từ nút gốc, ta tìm tất các các ứng viên được chứa trong dữ liệu dãy d. Áp dụng thủ tục sau, dựa trên các loại nút bao gồm:  Nút trung gian là nút gốc: Áp dụng hàm băm cho mỗi phần tử trong d, và áp dụng đệ quy thủ tục này tới nút nằm trong bucket tương ứng. Với bất kỳ dãy s được chứa trong dữ liệu dãy d, phần tử đầu tiên của s phải nằm trong d. Thực hiện băm trên mọi phần tử trong d, ta đảm bảo rằng chỉ bỏ qua các dãy bắt đầu với một phần tử không nằm trong d.  Nút trung gian không phải là nút gốc: Giả sử ta đến nút này bằng việc thực hiện băm phần tử x có thời gian giao dịch (transaction-time) là t. Áp dụng hàm băm tới mỗi phần tử trong d có thời gian giao dịch trong khoảng [t – window-size, t + max(window-size, max-gap)] và áp dụng đệ quy thủ tục này tới các nút trong bucket tương ứng. Để thấy tại sao kết quả trả về là tập các ứng viên, xét một dãy ứng viên s với hai phần tử liên tục là x và y. Cho x là phần tử được chứa trong giao dịch d với thời gian giao dịch là t. Vì d chứa s nên thời gian giao dịch tương ứng với y cần phải trong khoảng [t – window-size, t + window-size] nếu y là một phần của cùng thành phần chứa x, hoặc trong khoảng thời gian (t, t + max-gap] nếu y là một phần của thành phần kế tiếp. Do đó nếu chúng ta đạt đến nút này bằng thực hiện băm trên một phần tử x với thời gian giao dịch t, y phải được chứa trong một giao dịch có thời gian giao dịch ở trong khoảng [t – window-size, t + max (window-size, max-gap)] cho dữ liệu dãy để hỗ trợ các dãy. Như vậy chúng ta chỉ cần áp dụng hàm băm tới các phần tử trong d có thời gian giao dịch nằm trong khoảng thời gian trên, và kiểm tra các nút tương ứng.  Nút lá: Đối với mỗi dãy s là nút lá, ta kiểm tra xem d có chứa s, và thêm s vào tập kết quả nếu cần thiết. (Chúng ta sẽ thảo luận dưới đây cách chính xác để tìm d chứa một dãy ứng viên cụ thể.) Từ đó ta kiểm tra mỗi dãy được chứa trong nút này, và không bỏ qua bất kỳ dãy nào. Kiểm tra dữ liệu dãy chứa một dãy cho trước: Cho dữ liệu dãy d, và một dãy ứng viên s = . Trước tiên ta mô tả thuật toán để kiểm tra nếu d chứa s, giả sử tồn tại một thủ tục tìm kiếm sự xuất hiện đầu tiên của một thành phần của s ở d sau một thời gian nhất định, và sau đó mô tả thủ tục này. - 34 - Khai phá luật dãy Nguyễn Đình Văn Thuật toán này kiểm tra nếu dữ liệu dãy d chứa một dãy ứng viên s luân phiên giữa hai giai đoạn. Thuật toán bắt đầu với giai đoạn duyệt xuôi từ phần tử đầu tiên.  Giai đoạn duyệt xuôi (forward phase): Thuật toán tìm thành phần kế tiếp của s trong d miễn là hiệu số giữa thời gian kết thúc của thành phần đã được tìm thấy và thời gian bắt đầu của thành phần trước đó là ít hơn khoảng max-gap. (Nhắc lại rằng đối với mỗi thành phần si, thời gian bắt đầu start-time(si) và thời gian kết thúc end-time(si) tương ứng với thời gian giao dịch đầu tiên và cuối cùng của tập các giao dịch có chứa si). Nếu hiệu số này nhiều hơn max-gap, thuật toán sẽ chuyển sang giai đoạn duyệt ngược. Nếu một thành phần không được tìm thấy tức là dữ liệu dãy không chứa s.  Giai đoạn duyệt ngược (backward phase): Thuật toán thực hiện quay lui và xét (kéo lên) các thành phần liền trước. Nếu si là thành phần hiện tại và thời gian kết thúc end-time(si) = t, thuật toán tìm tập các giao dịch đầu tiên có chứa si mà có thời gian giao dịch sau (t – max-gap). Thời gian bắt đầu đối với si–1 (sau khi si–1 được xét đến) có thể sau thời gian kết thúc end-time của si. Trong khi xét si–1 có thể đòi hỏi phải xét cả si–2 bởi vì ràng buộc max-gap giữa si–1 và si–2 có thể không còn được thỏa mãn. Thuật toán thực hiện quay lui cho đến khi hoặc là ràng buộc max-gap giữa thành phần vừa xét và thành phần liền trước thỏa mãn, hoặc là thành phần đầu tiên được lấy lên. Sau đó thuật toán chuyển sang giai đoạn duyệt xuôi để tìm các thành phần của s trong d bắt đầu từ thành phần liền sau của thành phần cuối cùng được lấy lên của giai đoạn duyệt ngược. Nếu không có bất kỳ thành phần nào được lấy lên (nghĩa là không có tập dãy con của các giao dịch có chứa thành phần) khi đó dữ liệu dãy không chứa s. Thủ tục thực hiện lặp đi lặp lại, hoán đổi giữa giai đoạn duyệt xuôi và duyệt ngược cho tới khi tất cả các thành phần được tìm thấy. Ví dụ: Cho dữ liệu dãy trong Hình 2.17. Xét trường hợp max-gap là 30, min-gap là 5 và window-size là 0. Với dãy ứng viên , (forward phase) trước tiên ta cần tìm (1, 2) tại thời gian giao dịch 10, tiếp theo tìm thành phần (3) tại thời gian giao dịch 45. Khi đó khoảng thời gian giữa hai thành phần (35 ngày) lớn hơn max-gap, (backward phase) lấy lên thành phần (1, 2). Tìm lần xuất hiện đầu tiên của (1, 2) sau thời gian 15, bởi vì thời gian kết thúc end-time((3)) = 45 và max-gap là 30, và vì vậy thậm chí nếu (1, 2) xảy ra tại một số thời điểm trước 15, nó vẫn sẽ không thỏa mãn ràng buộc max-gap. Ta tìm (1, 2) tại thời gian 50. Vì đây là thành phần đầu tiên nên không phải kiểm tra xem liệu ràng buộc max-gap có nằm giữa (1, 2) và thành phần trước đó có thỏa mãn không. Ta chuyển sang bước tiếp theo. Vì (3) không còn xảy ra lớn hơn 5 ngày sau (1, 2), cần tìm sự xuất hiện tiếp theo của (3) sau thời gian 55. Ta - 35 - Khai phá luật dãy Nguyễn Đình Văn tìm thấy (3) tại thời gian 65. Khi ràng buộc giữa (3) và (1, 2) thõa mãn, ta tiếp tục di chuyển tiếp và tìm thấy (4) tại thời gian 90. Ràng buộc max-gap giữa (4) và (3) được thỏa mãn. Transaction-Time Items Item Times 10 25 45 50 65 90 95 1, 2 4, 6 3 1, 2 3 2, 4 6 1 2 3 4 5 6 7 → 10 → 50 → NULL → 10 → 50 → 90 → NULL → 45 → 65 → NULL → 25 → 90 → NULL → NULL → 25 → 95 → NULL → NULL Hình 2.17: Dữ liệu dãy Hình 2.18: Item xuất hiện theo thời gian Để tìm kiếm một cách hiệu quả một phần tử đơn lẻ (item), ta sử dụng mảng để lưu trữ tất cả các phần tử có trong dữ liệu dãy và thời gian giao dịch, dữ liệu dãy trong Hình 2.17 được biến đổi như Hình 2.18, nhằm hỗ trợ cho việc tìm kiếm lần xuất hiện đầu tiên của một thành phần trong dữ liệu dãy sau thời gian t. Thuật toán duyệt một lần tất cả các phần tử trong thành phần và tìm thời gian giao dịch đầu tiên của mỗi phần tử lớn hơn t. Nếu hiệu số giữa thời gian bắt đầu và thời gian kết thúc nhỏ hơn hoặc bằng với window-size thì chấp nhận. Nếu không, t được lấy là hiệu số giữa thời gian kết thúc và window-size, thủ tục tiếp tục được lặp lại. Ví dụ: Cho dữ liệu dãy trong Hình 2.17, giả sử window-size = 7 ngày, ta phải tìm lần xuất hiện đầu tiên của thành phần (2, 6) sau thời gian t = 20. Ta tìm phần tử 2 tại thời gian 50, phần tử 6 tại thời gian 25. Vì end-time((2,6)) – start-time((2,6)) > 7 nên ta đặt t là 43 (= end-time((2,6)) – window-size) và thử lại. Phần tử 2 còn lại tại thời gian 90, trong khi phần tử 6 tiếp theo tại thời gian 95. Vì khoảng thời gian giữa 90 và 95 nhỏ hơn window-size nên ta bỏ qua.  Phân loại Cách tiếp cận cơ bản là thay thế mỗi dữ liệu dãy d với một dãy mở rộng d’, trong đó, mỗi giao dịch d’i của d’ chứa các phần tử trong giao dịch di của d tương ứng, cũng như tất cả các “ancestor” (tổ tiên) của mỗi phần tử trong di. Ví dụ, một dữ liệu dãy có thể được thay thế với dãy mở rộng . Sau đó, ta thực GSP trên các dãy mở rộng này. Có hai cách tối ưu hóa để cải thiện đáng kể hiệu suất thực hiện. Cách thứ nhất là tính toán trước các “ancestor” của mỗi phần tử và loại bỏ các “ancestor” không có trong bất kỳ dãy ứng viên nào được tính trước khi thực hiện duyệt dữ liệu. Ví dụ, nếu (2), (3) và (4) không nằm trong bất kỳ dãy ứng viên nào được tính trong lần duyệt hiện tại, ta sẽ thay thế dãy với dãy mở rộng (thay vì dãy mở rộng ). Cách tối ưu hóa thứ hai là không tính các mẫu dãy với một thành phần có chứa cả phần tử x và phần tử y là ancestor của x, vì độ hỗ trợ của - 36 - Khai phá luật dãy Nguyễn Đình Văn các dãy này sẽ luôn giống độ hỗ trợ cho các mẫu dãy không có y. (Bất kỳ giao dịch nào chứa x cũng sẽ chứa y.) 2.3 Hai phương pháp khai phá luật dãy 2.3.1 Khai phá dãy sử dụng kỹ thuật phân vùng (thuật toán Dynamic DISC-all) Thuật toán Dynamic DISC-all bao gồm hai giai đoạn, phân vùng (partitioning) và so sánh [10]. Ban đầu, một lược đồ phân vùng được sử dụng để sinh một cách đệ quy các phân vùng cấp k, ở đó có thể khai phá được các dãy k thường xuyên. Phép đo về cách phân vùng sẽ giúp ích cho nhiệm vụ khai phá trên mỗi phân vùng như thế nào sẽ được tính toán để quyết định liệu có nên chuyển sang giai đoạn so sánh hay không. Ví dụ, như trong hình 2.19, một giai đoạn chuyển đổi xuất hiện sau các dãy-3 thường xuyên, trong phân vùng một, mức 3 được khai phá. Trong giai đoạn phân vùng, chúng ta có thể áp dụng bất kỳ chiến lược DP nào như lược đồ phân vùng đa cấp trong [Chiu, D.Y., Wu, Y.H., Chen, A.L.P. (2004)] và lược đồ quy chiếu CSDL trong [Pei, J.,Han, J.W., Mortazavi-Asl,B., Pinto, H.,Chen, Q.,Dayal,U., Hsu, M.C. (2001)]. Trong giai đoạn so sánh, chúng ta áp dụng lược đồ Khám phá dãy-k thường xuyên [Chiu, D.Y., Wu, Y.H., Chen, A.L.P. (2004)], là lược đồ kết hợp chiến lược DISC với chiến lược CP để đạt được hiệu suất tốt hơn. Trong phần này, chúng ta giới thiệu phương pháp tiếp cận cho việc chuyển tiếp giai đoạn động và cây-AVL cách vị trí (locative AVL-tree) hỗ trợ chiến lược DISC. Hình 2.19: Thuật toán Dynamic DISC-all  Sự chuyển tiếp giai đoạn động Các chiến lược DP [Ho, C.C., Li, H.F., Kuo, F.F., Lee, S.Y. (2006)] giảm chi phí cho việc liệt kê các dãy con nhưng phải chịu các chi phí chung cho việc phân vùng. Việc sử dụng chiến lược DP đơn lẻ không áp dụng cho các trường hợp có nhiều phân - 37 - Khai phá luật dãy Nguyễn Đình Văn vùng gần giống như là phân vùng cha mẹ của chúng. Trong những trường hợp này, Dynamic DISC-all nên chuyển sang giai đoạn so sánh. Do đó, việc có một chỉ dẫn tốt để có thể kích hoạt sự chuyển tiếp giai đoạn đúng thời điểm là rất cần thiết. Cho tổng số dãy khách hàng trong phân vùng P được ký hiệu là Size(P). Để quyết định xem việc phân vùng sẽ mang lại lợi ích nhiều hơn chi phí, một ý tưởng cơ bản là xem xét tỷ lệ của Size(P) với Size(Q), trong đó Q là phân vùng cha của P. Vì tổng số hỗ trợ đếm được của một phần tử trong Q có nghĩa là số lượng các dãy khách hàng hỗ trợ phần tử đó, Size(P) có thể thu được ngay lập tức khi tổng số hỗ trợ đếm được của các phần tử trong Q được tính toán. Hơn nữa, vì chiến lược DP thao tác trên phân vùng cha Q và sau đó tạo ra các phân vùng con, nên có thể thu được Size(P) mà không cần quá nhiều chi phí. Bây giờ hãy xem xét tỷ lệ của Size(P) với Size(Q). Tỷ lệ càng cao, thì phân vùng Q sẽ mang lại càng ít lợi ích. Trường hợp xấu nhất là khi tỷ lệ này bằng 1. Dựa trên ý tưởng này, có ba thước đo có thể được xem như là định hướng cho giai đoạn chuyển tiếp. Chúng ta lấy hình 2.20 như một minh hoạ, nơi mà tất cả các phân vùng cấp-k đã được tạo ra. Hình 2.20: Ba thước đo kích hoạt sự chuyển tiếp giai đoạn Tiếp theo, chúng ta lần lượt thảo luận về những hạn chế của thước đo dựa trên phân vùng con (child-based measure) và thước đo dựa trên phân vùng anh em (sibling- based measure). Trước tiên, child-based measure tạo ra quyết định riêng lẻ cho mỗi phân vùng con. Việc tạo ra quyết định cho một phân vùng cần quét toàn bộ phân vùng cha của nó. Một cách tương phản, child-based measure phải quét phân vùng cha nhiều lần, trong khi parent-based measure tạo ra tất cả các phân vùng con bằng cách quét các phân vùng cha chỉ một lần. Thứ hai, khi các sibling-based measure được lựa chọn, hai phân vùng anh em Q1 và Q2 có thể thích hợp với các chiến lược khác nhau. Giả sử rằng chỉ có hai phân vùng con, P11 và P12, chúng có các kích thước gần với Size(Q1). Điều đó ngụ ý rằng Q1 sẽ không phù hợp với chiến lược DP. Mặt khác, Q2 có thể thích hợp với chiến lược DP. Kết quả là, sibling-based measure cần dàn xếp mâu thuẫn giữa Q1 và Q2. So sánh với các thước đo khác, parent-based measure chỉ xem xét tỷ lệ giữa các phân vùng cha và các phân vùng con của nó. Do vậy, trong - 38 - Khai phá luật dãy Nguyễn Đình Văn Dynamic DISC-all chúng ta áp dụng tiêu chuẩn thước đo parent-based measure, biện pháp dựa vào cha, được gọi là tỷ lệ rút gọn, như một chỉ dẫn cho việc chuyển tiếp giai đoạn. Tỷ lệ rút gọn (Reduction rate): Cho một phân vùng Q, tổng số phân vùng con của nó được biểu diễn là NQ. Tỷ lệ rút gọn của Q (viết tắt là RRQ) có nghĩa là tỷ số của sự khác biệt trung bình giữa Size(Q) và kích thước của phân vùng con của nó với Size(Q), được tính toán theo công thức sau: Cho một ngưỡng γ , nếu RRQ cao hơn γ , giai đoạn phân vùng sẽ được tiếp tục; nếu không thì một sự chuyển đổi giai đoạn sẽ xuất hiện. Ta gọi γ là tỷ lệ rút gọn tối thiểu. Hình 2.21 là thuật toán chính của Dynamic DISC-all, bao gồm các phép tính của tỷ lệ rút gọn (bước 2) và giai đoạn so sánh (các bước 3–5). Tại bước 2, tỷ lệ rút gọn của một phân vùng P(S) được tính bởi công thức (2), sử dụng tổng số hỗ trợ đếm được, thu được trong bước 1. Tại bước 4, ta áp dụng phương pháp tiếp cận từ dưới lên và gọi lược đồ khai phá dãy k thường xuyên để tìm các dãy phổ biến còn lại với tiền tố S. Lưu ý rằng trong các bước ban đầu, P(S) là CSDL ban đầu và k = 0. Có nghĩa là thuật toán Dynamic DISC-all luôn quét các CSDL ban đầu một lần để tìm tất cả các dãy 1 thường xuyên. Sau đó, nó tính toán tỷ lệ rút gọn để quyết định liệu có nên tiếp tục giai đoạn phân vùng hay chuyển sang giai đoạn so sánh. Hình 2.21: Giải thuật chính của Dynamic DISC-all 2.3.2 Khai phá luật dãy bằng mã hóa khối cơ bản với thuật toán PRISM Có 3 khía cạnh của thuật toán PRISM cần giải thích rõ (i): Chiến lược không gian kiến trúc nhánh ngang; (ii) Cấu trúc dữ liệu thường được sử dụng thể hiện CSDL và thông tin ứng viên trung gian; (iii) Làm thế nào để tính toán độ hỗ trợ cho ứng viên; Khối cơ bản sẽ xác định dãy phổ biến của mỗi ứng viên. Cụ thể như sau:  Không gian tìm kiếm - 39 - Khai phá luật dãy Nguyễn Đình Văn Dãy thứ tự từng phần được tạo bởi dãy con liên quan được biểu diễn như một cây tìm kiếm. Cây tìm kiếm dãy được định nghĩa đệ qui như sau: Gốc của cây tìm kiếm ở mức 0 và gán nhãn với dãy null . Một nút mức k được gán nhãn với dãy S, nghĩa là một dãy k được mở rộng lặp đi lặp lại bằng cách thêm một phần tử (item) từ I tạo ra một nút con ở mức (k+1) nghĩa là dãy (k+1). Có hai cách để mở rộng dãy bởi cùng một phần tử: mở rộng dãy và mở rộng tập phần tử. Trong một dãy mở rộng, một phần tử được nối thêm lặp đi lặp lại một cách tuần tự vào cuối mỗi mẫu như một tập phần tử mới. Trong một tập phần tử mở rộng, một phần tử được thêm vào tập phần tử cuối cùng trong một mẫu. Tập phần tử mở rộng với điều kiện phần tử thêm vào đã sắp xếp theo thứ tự từ điển lớn hơn tất cả các phần tử trong tập phần tử cuối cùng. Vì thế, với cách mở rộng dãy thì kích thước của dãy luôn luôn tăng lên trong khi đó với cách mở rộng tập phần tử thì không. Ví dụ nếu chúng ta có một nút S=ab→a và một phần tử b để mở rộng S và như vậy dãy mở rộng là ab→a→b còn tập phần tử mở rộng sẽ là ab →ab. Hình 2.22 biểu diễn một ví dụ của cây tìm kiếm dãy thành phần với 2 phần tử a và b. Ví dụ chỉ ra rằng dãy tăng kích thước lên 3 (chỉ những nhánh con dưới phần tử a được hiển thị). Hình 2.22: Cây tìm kiếm dãy thành phần: mũi tên nét liền biểu thị các dãy mở rộng, mũi tên nét đứt biểu thị tập phần tử mở rộng Về bản chất thì tất cả các phương thức khai phá dãy theo cách mở rộng dãy hoặc mở rộng tập các phần tử đều sử dụng đến cây tìm kiếm. Sự khác biệt chính nằm ở chỗ độ hỗ trợ cho các mẫu ứng viên được quyết định như thế nào. Dưới đây mô tả thuật toán PRISM tính toán tần suất cho mỗi cách mở rộng.  Mã hóa khối cơ bản - 40 - Khai phá luật dãy Nguyễn Đình Văn Ví dụ trong hình 2.23(a) gồm 5 dãy có độ dài khác nhau với các phần tử I ={a,b, c}; Với G ={2,3,5,7} là tập sinh đầu tiên, chúng ta sẽ xem xét việc cấu trúc PRISM mã hóa khối cơ bản cho phần tử a như thế nào. Tại bước đầu tiên, cấu trúc PRISM sẽ mã hóa khối cơ bản về vị trí trong mỗi dãy. Ví dụ khi a xuất hiện ở vị trí 1, 4 và 6 trong dãy 1 (với giả thiết rằng vị trí đầu tiên xác định là 1) chúng ta có bit được mã hóa (bit-encoding) tương ứng là 100101, chuyển dãy sang dạng véctơ với độ dài là bội số của |G|= 4, ta có A = 10010100, hai bit được in đậm là hai bít thêm vào. Khi đó ta có ν(A)=ν(1001)ν(0100) ={14,3}. Vị trí được mã hóa của a cho tất cả các dãy được mô tả trong hình 2.23(b). Việc tiếp theo là mã hóa khối cơ bản cho dãy. Khi a xuất hiện trong tất cả các dãy trừ vị trí thứ tư khi đó chúng ta biểu diễn dãy véc tơ dãy sẽ là 11101000 sau khi thêm các bít vào cuối. Khi đó khối mã hóa cơ bản được biểu diễn trong hình 2.23(c), ν(A) = ν(1110)ν(1000)={30,2}. Việc mã hóa cho phần tử a về vị trí ở tất cả các dãy và khối cơ bản được mô tả trong hình 2.23(d). Một khối Ai = 0000 = 0 với ν(Ai) = {1} = 1 được coi là một khối rỗng. Lưu ý rằng việc mã hóa đầy đủ cho tất cả các vị trí khối rỗng còn lại, ví dụ a không xuất hiện tại khối thứ 2 tại vị trí thứ 5, khi đó dãy dãy véctơ là 0000 và mã cơ bản là {1}. Để loại trừ những khối rỗng, PRISM chỉ giữ lại những khối không rỗng khi mã hóa cơ bản. Cần giữ vị trí của mỗi khối trong dãy đáp ứng được yêu cầu. Hình 3e chỉ ra việc mã hóa khối cơ bản của phần tử a khi loại bỏ những khối rỗng. Khối của dãy đầu tiên là 30, ||30||G = 3, vậy có 3 dãy hợp lệ trong khối . Với mỗi dãy, chúng ta lưu vị trị vào khối các vị trí. Ví dụ, nếu vị trí của dãy {1} là 1 và hai phần tử đầu tiên trong khối vị trí là của dãy này thì vị trí khối tương ứng với dãy thứ 2 là 3 và vị trí trong khối tương ứng với dãy thứ 3 là 4 nếu dãy 2 và 3 chỉ cần một phần tử trong khối vị trí. Với cách biểu diễn này, mọi việc trở nên rất rõ ràng khi mã hóa cơ bản cho c. Với việc mã hóa đầy đủ sẽ chứa nhiều thông tin dư thừa, bằng cách khử đi các thông tin này trong mã hóa khối cơ bản, chúng ta có ví dụ nêu trong hình 2.23(e). (a) - 41 - Khai phá luật dãy Nguyễn Đình Văn (b) (c) (d) (e) Hình 2.23: Ví dụ mã hóa khối cơ bản: (a) CSDL; (b) Mã hóa vị trí của a; (c) Mã hóa dãy của a; (d) Khối cơ bản của a, b,c; (e) Mã hóa khối cơ bản của a, b, c Độ hỗ trợ của dãy S được xác định ngay từ khối của dãy trong mã hóa khối cơ bản. Đặt ε(S) = (SS ,PS ) thể hiện việc mã hóa khối cơ bản cho dãy S với SS là tập tất cả các khối của dãy được mã hóa, PS là tập tất cả các khối vị trí được mã hóa của S  Tính toán độ hỗ trợ thông qua phép nối (join) khối cơ bản Sau đây chúng ta sẽ chỉ ra rằng độ hỗ trợ của tập phần tử và dãy mở rộng được thực hiện thông qua kết hợp khối cơ bản. Giả sử rằng chúng ta có một số nút của S trong cây tìm kiếm dãy với S là mức k, đặt P là nút cha của S có mức k-1. Giả sử chúng ta có mã hóa khối cơ bản cho P là ε(P). Như minh họa trong hình 2, S được mở rộng bởi một nút nào đó cùng cấp dưới nút cha P. Ví dụ nếu P = ab, và S = ab →a, có - 42 - Khai phá luật dãy Nguyễn Đình Văn thể tạo ra sự mở rộng khác của S bằng sự mở rộng của P tạo ra nút anh em T = S = ab →b Các phần tử a và b có thể được sử dụng để mở rộng S = ab → a. Có hai dãy mở rộng, cụ thể là ab → a → a và ab → a → b, và một tập được suy ra bởi ab → ab. Trong thực tế, độ hỗ trợ cho bất kỳ sự mở rộng luôn luôn là kết quả của việc kết hợp khối mã hóa căn bản 2 nút (có thể giống nhau) ở bên dưới tiền tố P. Ví dụ, ε(ab → a → b) là thu được kết quả của một dãy khối cơ bản ε(ab → a) và ε(ab → b), nhưng ngược lại ε(ab → ab) được sử dụng như kết quả tập phần tử khối cơ bản ε(ab → a) và ε(ab→ b). Quá trình liệt kê dãy phổ biến được bắt đầu với gốc của cây tìm kiếm như nút gốc P =  và PRISM giả sử rằng ban đầu chúng ta đã biết mã hóa khối cơ bản cho tất cả các phần tử đơn lẻ. PRISM sau đó thực hiện đệ quy cho mỗi nút trong cây tìm kiếm, tính toán độ hỗ trợ thông qua việc kết hợp các khối cơ bản, và các khối mới được giữ lại khi chúng được sử dụng thường xuyên. Tìm kiếm thực chất là đệ quy, sự khác biệt chủ yếu là cho một nút S bất kỳ, tất cả các phần mở rộng của nó được đánh giá trước khi gọi đệ quy. Khi gọi đệ quy không tìm thấy dãy phổ biến mới thì quá trình tìm kiếm được dừng lại. Ví dụ minh họa như hình 2.23(e). - 43 - Khai phá luật dãy Nguyễn Đình Văn CHƯƠNG 3 – ĐỀ XUẤT ỨNG DỤNG KHAI PHÁ LUẬT DÃY TRONG HỆ THỐNG QUẢN LÝ KHÁCH HÀNG VÀ TÍNH HÓA ĐƠN NƯỚC 3.1 Tổng quan về hệ thống quản lý khách hàng và tính hóa đơn nước Hệ thống Quản lý khách hàng và tính hóa đơn nước là hệ thống thông tin chính của Công ty Kinh doanh Nước sạch Hà Nội (từ nay được gọi tắt là hệ thống) để đảm bảo hoạt động sản xuất kinh doanh của công ty. Hình 3.1: Mô hình triển khai hệ thống cấp nước Hà Nội Hệ thống có một kho dữ liệu lớn với quy mô gần 500 000 khách hàng và các dữ liệu được cập nhật hàng ngày. Hệ thống bao gồm các phân hệ sau:  Quản lý thông tin Khách hàng  Lập và In Hóa đơn  Thanh toán Hóa đơn và Quản lý nợ  Báo cáo thống kê - 44 - Khai phá luật dãy Nguyễn Đình Văn Mỗi phân hệ được chia thành nhiều chức năng năng đáp ứng đầy đủ các yêu cầu nghiệp vụ quản lý khách hàng và hóa đơn. 3.1.1 Phân hệ quản lý khách hàng Thông tin khách hàng sử dụng nước được quản lý trong hệ thống bao gồm từ khi nhập mới thông tin khách hàng, thay đổi thông tin (nếu có yêu cầu) trong suốt quá trình phát sinh hóa đơn đến khi có yêu cầu cắt nước (hủy mã khách hàng). Hình 3.2: Sơ đồ quy trình phát sinh khách hàng mới Khách hàng mới sau khi khai báo sẽ được hệ thống tự động sinh ra một mã số duy nhất gọi là mã khách hàng có độ dài 9 chữ số theo quy tắc: XX-XXXXXX-X. Hai chữ số đầu bao gồm: chữ số thứ nhất là mã của đơn vị trực tiếp quản lý khách hàng, chữ số thứ hai là mã của đối tượng sử dụng nước mà khách hàng thuộc vào. Sáu chữ số tiếp theo là số tăng dần trong dãy số tự nhiên bắt đầu từ 1 đến 999999. Chữ số cuối cùng là mã kiểm tra tính hợp lệ của cả dãy số mã khách hàng (mã check), mã này được sinh theo một quy tắc nhất định trong quá tình xây dựng phần mềm để đảm bảo tính duy nhất của mã khách hàng. - 45 - Khai phá luật dãy Nguyễn Đình Văn Theo quy tắc trên, chỉ cần nhìn vào thông tin mã khách hàng cũng nhận biết được khách hàng thuộc phạm vi quản lý của đơn vị nào, thuộc đối tượng sử dụng nào và khoảng thời gian được khai báo vào hệ thống. Khách hàng mới luôn phải thuộc về một trong hai đối tượng sử dụng Tư nhân hoặc Cơ quan. Mỗi đối tượng sử dụng lại có mục đích sử dụng nước (để áp giá) ngầm định khác nhau: đối tượng Tư nhân có mục đích sử dụng ngầm định là Sinh hoạt, đối tượng Cơ quan có mục đích ngầm định là Sản xuất. Khi khai báo thông tin khách hàng mới hệ thống tự động gán mục đích sử dụng nước cho khách hàng nếu mục đích sử dụng không có gì khác so với ngầm định. Thông tin khách hàng mới gồm: thông tin về nhân thân như họ tên, địa chỉ, số điện thoại, mã số thuế…Với khách hàng Tư nhân, nếu một mã khách hàng có trên một hộ sử dụng nước thì ngoài thông tin khách hàng chính sẽ có phần khai báo thông tin hộ khách hàng cùng sử dụng (họ tên, địa chỉ, số hộ khẩu). Phần lớn khách hàng phát sinh mới hiện nay đều sử dụng đồng hồ, chỉ một số rất ít khách hàng vì lý do đặc biệt nào đó sử dụng nước khoán theo tháng. Nếu khách hàng dùng đồng hồ thì thông tin khách hàng bao gồm cả thông tin về đồng hồ đang sử dụng. Một số khách hàng thay vì trả tiền lắp đồng hồ một lần cho công ty Nước sạch thì sẽ trả dần hàng tháng gọi là trả tiền thuê bao đồng hồ. Tiền thuê bao này được tính kèm trên hóa đơn tiền nước. Đối với khách hàng trả tiền thuê bao khi khai báo thông tin khách hàng mới phải khai báo thông tin này gồm số tiền phải trả mỗi tháng và số tháng cần phải trả. Khách hàng mới khi khai báo thông tin vào hệ thống được được xếp luôn vào sổ đọc và có trạng thái là Đang sử dụng nước, được đưa ngay vào quy trình ghi đọc đồng hồ phát sinh hóa đơn ở kỳ gần nhất. Có thể tìm kiếm thông tin khách hàng theo tên và địa chỉ (số nhà, đường phố). Có thể sửa đổi thông tin khách hàng gồm: họ tên, địa chỉ, mã số thuế, số tài khoản…, thông tin đồng hồ, mục đích sử dụng, danh sách hộ dùng chung đầu máy, quá trình gán sổ đọc. Có thể sửa thông tin đồng hồ cho khách hàng nếu cần. Trong quá trình ghi thu, thông tin chỉ số đồng hồ trên hệ thống có thể sai khác với thông tin chỉ số đồng hồ thực tế do nhiều nguyên nhân như nhân viên đọc chỉ số tự bịa số không đi đọc đồng hồ…, hệ thống cho phép chốt lại chỉ số đồng hồ của khách hàng, chỉ số chốt sẽ được dùng làm chỉ số cũ của kỳ ghi đọc gần nhất tiếp theo. Một số trường hợp khai báo nhầm tiền thuê bao hoặc đang trả thuê bao mà khách hàng muốn trả luôn một lần bằng hóa đơn tài chính thì hệ thống cho phép xóa thuê bao. - 46 - Khai phá luật dãy Nguyễn Đình Văn Khách hàng không còn nhu cầu sử dụng nước hoặc bị trùng mã (một khách hàng được khai báo nhiều lần vào hệ thống) hoặc thuộc khu vực bị giải tỏa… nếu có yêu cầu sẽ được cắt nước (hủy mã) trên hệ thống để loại khách hàng ra khỏi danh sách khách hàng Đang sử dụng nước và không phát sinh hóa đơn. Những khách hàng này sẽ được chuyển sang trạng thái Cắt nước và được cập nhật thông tin ngày cắt nước. Khách hàng có trạng thái là Cắt nước sẽ không tham gia vào bất cứ quy trình nghiệp vụ nào của hệ thống mà chỉ để phục vụ công tác tra cứu. 3.1.2 Phân hệ lập và in hóa đơn Hiện mỗi kỳ hoá đơn tương đương với một tháng. Trong mỗi tháng, hoá đơn được tính vào khoảng từ ngày 1 đến ngày 15 và được chia làm nhiều đợt đối với từng đối tượng khách hàng (Tư nhân, Cơ quan). Mỗi đợt hoá đơn lại được chia làm nhiều Khối hóa đơn, mỗi Khối gồm nhiều Sổ đọc, mỗi Sổ đọc gồm nhiều khách hàng. Số đọc còn được gán vào ô, cụm cấp nước phục vụ yêu cầu quản lý phân cấp. Hệ thống cho phép sắp xếp lại khách hàng trong sổ đọc: chuyển khách hàng từ sổ đọc này sang số đọc khác hoặc đảo vị trí trong cùng một sổ đọc, vị trí khách hàng trong sổ đọc được lưu để in hóa đơn theo thứ tự sổ đọc. Tại một thời điểm khách hàng chỉ thuộc vào một quyển sổ đọc. Có thể tra cứu lịch sử gán sổ đọc của khách hàng. Sổ đọc được gán cho nhân viên ghi đọc đồng hồ và nhân viên thu và có thể tra cứu lịch sử gán nhân viên này. Sổ đọc sau khi được sắp xếp lại khách hàng và gán nhân viên ghi, thu sẽ được in theo khối để nhân viên ghi chỉ số đem đi đọc đồng hồ. Trường hợp in giữa chừng bị lỗi có thể in lại tiếp tục từ đoạn bị lỗi. Thông tin chỉ số đồng hồ được nhập vào hệ thống theo sổ đọc để tính hóa đơn, sổ đọc nhập xong chỉ số được đánh dấu là Nhập đọc số trong bảng Theo dõi tiến độ công việc. Mục đích sử dụng nước của khách hàng được thay đổi hoặc bổ sung nếu có yêu cầu từ phía nhân viên ghi đọc. Các điều chỉnh tăng giảm đặc biệt như thu thêm nước tiêu thụ của đồng hồ cũ (trường hợp khách hàng thay đồng hồ giữa kỳ), trừ phần trăm nước thất thoát, trừ nhờ thu… cho khách hàng cũng được khai báo vào hệ thống trước khi tính hóa đơn Việc tính hóa đơn được thực hiện theo khối, một khối đủ điều kiện tính hóa đơn khi toàn bộ sổ đọc của một khối đó được nhập chỉ số đồng hồ đầy đủ (bước làm việc của số đọc trong bảng Theo dõi tiến độ công việc là Nhập đọc số). Tất cả khách hàng có tiêu thụ hoặc không có tiêu thụ nhưng đang phải trả thuê bao sẽ được tính hoá đơn.. Những thông tin liên quan đến việc tính hóa đơn phải được thực hiện trước khi tính hóa đơn, khi sổ đọc đã được khóa số. Trong quá trình tính hóa đơn, trường hợp nào bị - 47 - Khai phá luật dãy Nguyễn Đình Văn lỗi sẽ được thông báo sau khi tính xong cả khối, khi đó chỉ cần tính lại sổ đọc hoặc hóa đơn lỗi. Hóa đơn đã tính được in ra bảng kê (sổ soát) để nhân viên ghi đọc rà soát lại, nếu phát hiện sai sót, nhầm lẫn thì hệ thống cho phép sửa bảng kê. Việc in bảng kê có thể lựa chọn in bảng kê đầy đủ hoặc in bảng kê biến động đặc biệt hoặc in bảng kê rút gọn. Trường hợp in giữa chừng bị lỗi có thể in lại tiếp tục từ đoạn bị lỗi. Hóa đơn đã soát bảng kê được phát hành theo khối để sẵn sàng cho việc in hóa đơn. Hóa đơn được in hàng loạt theo khối hoặc đơn lẻ đối với các trường hợp sửa, bổ sung. Thao tác in hàng loạt nếu gặp lỗi bị ngừng giữa chừng có thể in tiếp từ đoạn bị ngừng. Trường hợp phần chi tiết các khoản áp giá trên hóa đơn dài quá số dòng có thể in trên hóa đơn (6 dòng) có thể in Phụ lục kèm theo hóa đơn Hệ thống cho phép quản lý số seri tài chính trên mỗi hóa đơn được in, có thể tìm kiếm, tra cứu hóa đơn dựa vào số seri này: hóa đơn sau khi in được đánh số seri tự động theo khối hoặc nhập đơn lẻ từng hóa đơn, trong một khối hoặc số đọc có thể đánh số seri từ hóa đơn này đến hóa đơn khác, ngược lại có thể hủy đánh số hóa đơn để làm lại nếu nhầm lẫn. Hóa đơn đã in nếu có sai sót được nhập danh sách yêu cầu sửa để xử lý, hóa đơn quá kỳ phát sinh nếu có yêu cầu sẽ được bổ sung. Trong một tháng làm việc có thể sửa hoặc bổ sung ngay hóa đơn tháng đó hoặc hóa đơn các tháng đã qua nếu hóa đơn cần sửa chưa được thanh toán. - 48 - Khai phá luật dãy Nguyễn Đình Văn Bắt đầu Kết thúc Điều chỉnh mục đích sử dụng nước Điều chỉnh tăng giảm đặc biệt Gán sổ đọc vào ô/ cụm cấp nước Tính hóa đơn Sắp xếp khách hàng vào sổ đọc DS ô/cụm cấp nước DS khách hàng Gán sổ đọc cho nhân viên Danh sách nhân viên Mục đích sử dụng nước Nhập đọc số In bảng kê Sửa bảng kê Phát hành hóa đơn In hóa đơn Hình 3.3: Sơ đồ quy trình lập và in hóa đơn 3.1.3 Phân hệ thanh toán hóa đơn và quản lý nợ Thông thường hóa đơn được thanh toán bằng hình thức trả tiền một lần. Do có nhiều hình thức thanh toán khác nhau như nhờ thu, chuyển khoản, séc… nên một hoá đơn có thể được chia ra trả tiền nhiều lần, một hoá đơn còn có thể được - 49 - Khai phá luật dãy Nguyễn Đình Văn trả thừa tiền để dành cho những lần thanh toán tiếp theo của chính khách hàng đó hoặc khách hàng liên quan (khách hàng mẹ-con, “mẹ” trả tiền cho “con”). Đối với những hoá đơn trả tiền nhiều lần, số tiền cùng ngày thu, nhân viên thu của mỗi lần được nhập vào hệ thống, khi hoá đơn đã được trả đủ tiền và có cuống thì hóa đơn sẽ được thanh toán. Hệ thống cho phép nhập và tính vào doanh thu cả những khoản tiền được cắt về từ ngân hàng mà chưa biết là của khách hàng nào, với những khoản như vậy, số tiền ngày nhận và nhân viên thu sẽ được nhập vào hệ thống. Số tiền này sẽ được chia vào hóa đơn khi đã xác định được nguồn gốc. Sau khi kết thúc thu một tháng, hệ thống cho phép in các báo cáo theo dõi nợ theo từng đơn vị, từng năm, từng tháng, từng khối., sổ đọc, ô, cụm. Thời điểm để in báo cáo nợ là kết thúc tháng thu và trước khi sửa hoá đơn tháng kế tiếp. Các hoá đơn nợ sẽ được theo dõi vô thời hạn cho đến khi thu được hoặc bị cắt góc (một hình thức huỷ nợ những hoá đơn không thu được tiền). 3.1.4 Phân hệ báo cáo thống kê Hệ thống báo cáo đươc phân chia tương ứng với các quy trình quản lý khách hàng, đồng hồ, hóa đơn ghi, thu Các báo cáo cũng chia ra theo thời gian lấy số liệu là hàng ngày, hàng tuần hay hàng tháng Hệ thống cung cấp những báo cáo tổng hợp số liệu và các báo cáo danh sách chi tiết để đối chiếu, kiểm tra. Có nhiều mức độ báo cáo tổng hợp như tổng hợp toàn công ty, toàn xí nghiệp, tổng hợp theo các ô, cụm, tổng hợp theo nhân viên ghi, tổng hợp theo năm, tháng hóa đơn Các báo cáo có thể lấy dữ liệu trực tiếp khi thực hiện hoặc lấy dữ liệu đã được tổng hợp từ trước (bằng chức năng Tổng hợp số liệu báo cáo). Ví dụ một trong các báo cáo quan trọng của hệ thống là báo cáo tình hình phát sinh hóa đơn. - 50 - Khai phá luật dãy Nguyễn Đình Văn Hình 3.4: Kết quả báo cáo Tình hình phát sinh hóa đơn 3.2 Phát biểu bài toán Như đã trình bày tổng quan hệ thống ở trên, bài toán đặt ra là ứng dụng khai phá luật dãy trong hệ thống quản lý khách hàng và tính hóa đơn nước, tìm ra khoảng thời gian trong năm mà trên 60% khách hàng có lượng nước tiêu thụ nhiều nhất trong năm. Thông tin hoá đơn của một khách hàng trong một kỳ (tháng) được lưu trữ trong bảng dữ liệu có cấu trúc cơ bản như sau: STT Tên trường Kiểu dữ liệu Mô tả 1 YEAR NUMBER(4) Năm hóa đơn 2 PERIOD NUMBER(2) Kỳ (tháng) hóa đơn trong năm 3 BILL_NO VARCHAR2(16) Số hóa đơn 4 CUST_ID NUMBER(10) Mã khách hàng 5 CUST_NAME VARCHAR2(90) Tên khách hàng 6 CONSUMPTION NUMBER(12) Lượng nước tiêu thụ trong kỳ 7 LAST_READING NUMBER(12) Chỉ số đồng hồ lần đọc trước 8 THIS_READING NUMBER(12) Chỉ số đồng hồ lần đọc hiện tại 9 AMOUNT NUMBER(15) Tiền nước 10 … - 51 - Khai phá luật dãy Nguyễn Đình Văn Hình 3.5: Cấu trúc bảng dữ liệu BILLS Trong bảng thông tin hóa đơn, ta chọn ra các thuộc tính bao gồm mã khách hàng, thời gian phát sinh hóa đơn, lượng nước tiêu thụ là những thông tin đặc thù, cần thiết cho quá trình khai phá luật dãy trong bài toán này. Ví dụ dữ liệu mô phỏng năm 2010 của Xí nghiệp kinh doanh nước sạnh Hoàn Kiếm như sau: Mã khách hàng Tên khách hàng Tháng Năm Lượng nước tiêu thụ (m3) 210004040 Phạm Văn Bá 1 2010 17 210004040 Phạm Văn Bá 2 2010 14 210004040 Phạm Văn Bá 3 2010 12 210004040 Phạm Văn Bá 4 2010 17 210004040 Phạm Văn Bá 5 2010 21 210004040 Phạm Văn Bá 6 2010 22 210004040 Phạm Văn Bá 7 2010 21 210004040 Phạm Văn Bá 8 2010 22 210004040 Phạm Văn Bá 9 2010 13 210004040 Phạm Văn Bá 10 2010 14 210004040 Phạm Văn Bá 11 2010 19 210004040 Phạm Văn Bá 12 2010 18 210004115 Chùa Thái Cam (Che) 1 2010 22 210004115 Chùa Thái Cam (Che) 2 2010 20 210004115 Chùa Thái Cam (Che) 3 2010 12 210004115 Chùa Thái Cam (Che) 4 2010 29 210004115 Chùa Thái Cam (Che) 5 2010 30 210004115 Chùa Thái Cam (Che) 6 2010 33 210004115 Chùa Thái Cam (Che) 7 2010 32 210004115 Chùa Thái Cam (Che) 8 2010 33 210004115 Chùa Thái Cam (Che) 9 2010 25 210004115 Chùa Thái Cam (Che) 10 2010 24 210004115 Chùa Thái Cam (Che) 11 2010 23 210004115 Chùa Thái Cam (Che) 12 2010 24 210007634 Ngô Quang Tú 1 2010 5 210007634 Ngô Quang Tú 2 2010 5 210007634 Ngô Quang Tú 3 2010 3 - 52 - Khai phá luật dãy Nguyễn Đình Văn 210007634 Ngô Quang Tú 4 2010 22 210007634 Ngô Quang Tú 5 2010 30 210007634 Ngô Quang Tú 6 2010 29 210007634 Ngô Quang Tú 7 2010 31 210007634 Ngô Quang Tú 8 2010 30 210007634 Ngô Quang Tú 9 2010 16 210007634 Ngô Quang Tú 10 2010 17 210007634 Ngô Quang Tú 11 2010 18 210007634 Ngô Quang Tú 12 2010 27 210007689 Đinh Thị Bảo 1 2010 14 210007689 Đinh Thị Bảo 2 2010 13 210007689 Đinh Thị Bảo 3 2010 21 210007689 Đinh Thị Bảo 4 2010 19 210007689 Đinh Thị Bảo 5 2010 23 210007689 Đinh Thị Bảo 6 2010 23 210007689 Đinh Thị Bảo 7 2010 26 210007689 Đinh Thị Bảo 8 2010 26 210007689 Đinh Thị Bảo 9 2010 18 210007689 Đinh Thị Bảo 10 2010 16 210007689 Đinh Thị Bảo 11 2010 22 210007689 Đinh Thị Bảo 12 2010 21 … Hình 3.6: Dữ liệu mô phỏng bảng hóa đơn BILLS 3.3 Mô hình giái quyết CSDL thông tin tiêu thụ nước trong năm của khách hàng trong hình 3.6 đã được sắp xếp theo thứ tự Mã khách hàng, Kỳ (tháng) hóa đơn, ta cần thực hiện biến đổi sang CSDL dãy. Các giá trị tính lượng nước tiêu thụ được quy đổi thành các loại <Không giảm, Tháng>, , trong đó: “Không giảm”, “Giảm” là lượng nước (m3) tháng đang xét , so với tháng ngay trước đó. “Tháng” là số hiệu các tháng trong năm: 1-12. Với mỗi khách hàng, dãy thông tin tiêu thụ nước theo chu kỳ hóa đơn được biểu diễn: . Trong đó, T thể hiện giá trị Không giảm, G thể hiện giá trị Giảm so với tháng trước đó. - 53 - Khai phá luật dãy Nguyễn Đình Văn Để thuận tiện cho việc biểu diễn thông tin và xử lý dữ liệu, ta có thể viết thu gọn dãy trên thành: Khi tính độ hỗ trợ s của một ứng viên bất kỳ (có độ tối đa là độ dài của dãy, = 12), mỗi một dãy khách hàng sẽ có 12 lần so sánh, tương ứng với các dãy như sau: ……………………….. Biến đổi về dạng rút gọn ta được 12 dãy tương ứng: ………….. . Dấu cách được sử dụng để phân biệt vị trí của tháng 1 và 12. Từ vị trí của dấu cách trong dãy, ta có thể dịch được dãy rút gọn thành dãy đầy đủ thông tin. VD: Tính độ hỗ trợ s của dãy trong C3. Với dãy khách hàng , ta lần lượt thực hiện 12 lần so sánh: , , , , …, , . Kết quả khớp một lần với dãy bắt đầu từ tháng 4 . Lúc đó, độ hỗ trợ s của dãy sẽ được tính tăng thêm 1 lần. Độ hỗ trợ của dãy s tính trong toàn bộ dữ liệu là giá trị lớn nhất của một trong 12 lần tính. Lần 1 so sánh dãy ứng viên với tất cả các dãy khách hàng có phần tử bắt đầu là tháng 1, được kết quả s1. Lần 2 so sánh dãy ứng viên với tất cả các dãy khách hàng có phần tử bắt đầu là tháng 2, được kết quả s2. Tương tự thực hiện đến s12. Độ hỗ trợ s = max(s1, s2, …, s12). Khi có kết quả khai phá luật dãy thu được trong Lk ở lần duyệt cuối cùng, căn cứ vào dãy kết quả, độ hỗ trợ để tìm khoảng thời gian thỏa mãn yêu cầu của đề bài. - 54 - Khai phá luật dãy Nguyễn Đình Văn Sử dụng thuật toán AprioriAll đã nêu trong phần 2.2.1 để giải quyết bài toán. Duyệt CSDL để tính độ hỗ trợ S cho mỗi dãy ứng viên S >= min_sup Xóa các dãy c trong Ck nếu dãy con (k-1)-subsequence của c  Lk-1 Bổ sung vào Lk Sinh tập = Null Maximal Sequences in k Lk Bắt đầu Duyệt CSDL để lấy tất cả các phần tử và độ hỗ trợ S của mỗi phần tử S >= min_sup Bổ sung vào L1 Lk-1 join Lk-1 để sinh tập ứng viên Ck Đúng Đúng Đúng Sai - 55 - Khai phá luật dãy Nguyễn Đình Văn 3.4 Thực nghiệm và đánh giá 3.4.1 Giới thiệu thực nghiệm Sử dụng 6672 bản ghi dữ liệu thực tế của Xí nghiệp kinh doanh nước sạch Hoàn Kiếm làm dữ liệu thử nghiệm. Bước 1: Từ CSDL gốc, thực hiện chuyển đổi sang CSDL dãy (Hình 4.2) Hình 4.1: CSDL gốc - 56 - Khai phá luật dãy Nguyễn Đình Văn Hình 4.2: CSDL dãy sau khi chuyển đổi Bước 2: Nhập ngưỡng min_sup, thực hiện thuật toán AprioriAll Hình 4.3: Kết quả khai phá luật dãy áp dụng AprioriAll - 57 - Khai phá luật dãy Nguyễn Đình Văn