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 Giới thiệu chung về luật kết hợp 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: n( A B ) support(A B) = P(A B ) = N Trong đó: N là tổng số giao dịch; n(A B ) là số giao dịch có chứa (A B ) Khai phá luật dãy Nguyễn Đình Văn TIEU LUAN MOI download : skknchat@gmail.com -9- 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: n( A B ) confidence(A B) = P(B | A ) = n( A) 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.
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.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.
Khai phá luật dãy Nguyễn Đình Văn TIEU LUAN MOI download : skknchat@gmail.com - 10 - 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.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 Khai phá luật dãy Nguyễn Đình Văn TIEU LUAN MOI download : skknchat@gmail.com - 11 - 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 Khai phá luật dãy Nguyễn Đình Văn TIEU LUAN MOI download : skknchat@gmail.com - 12 - 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.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.
Khai phá luật dãy Nguyễn Đình Văn TIEU LUAN MOI download : skknchat@gmail.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 ,. Ta sử dụng ký hiệu để biểu thị quan hệ “đƣợc chứa trong”. Tuy nhiên, dãy <(3) (5)> không đƣợc chứa trong <(3 5)> và ngƣợc lại.