Mở đầu Khai phá tập mục thường xuyên đóng vai trò quan trọng trong nhiều nhiệm vụ khai phá dữ liệu. Khai phá tập mục thường xuyên xuất hiện như bài toán con của nhiều lĩnh vực khai phá dữ liệu như khám phá luật kết hợp, khám phá mẫu tuần tự, phân tích tương quan, phân lớp, phân cụm dữ liệu, khai phá Web,… Bài toán khai phá tập mục thường xuyên được giới thiệu lần đầu bởi Agrawal vào năm 1993 khi phân tích cơ sở dữ liệu bán hàng của siêu thị [9] trong mô hình của bài toán khai phá luật kết hợp. Khai phá luật kết hợp là phát hiện những mối quan hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu, các mối quan hệ đó chính là các luật kết hợp. Khai phá luật kết hợp có hai bước: bước thứ nhất, tìm các tập mục thường xuyên thỏa mãn ngưỡng độ tối thiểu minsup cho trước, bước thứ hai, từ các tập mục thường xuyên tìm được, sinh ra các luật kết hợp thỏa mãn ngưỡng độ tin cậy minconf cho trước.
Mọi khó khăn của bài toán khai phá luật kết hợp tập trung ở bước thứ nhất, đó là khai phá tập mục thường xuyên thỏa mãn ngưỡng độ hỗ trợ cho trước. Kể từ khi Agrawa đề xuất, khai phá tập mục thường xuyên đã thu hút được sự quan tâm của nhiều nhà nghiên cứu, đã có hàng trăm kết quả nghiên cứu được công bố giới thiệu các thuật toán mới hay đề xuất các giải pháp nâng cao hiệu quả các thuật toán đã có. Tập mục thường xuyên đã có vai trò quan trọng trong nhiều ứng dụng thực tế như quản lý quan hệ khách hàng, nâng cao hiệu quả của thương mại điện tử, trong lĩnh vực tin sinh học, phân tích cấu trúc Protein và DNA, mở rộng truy vấn, phát hiện xâm nhập mạng…[13, 14, 15, 16]. Mô hình khai phá tập mục thường xuyên cơ bản có nhiều ứng dụng trong thực tế nhưng có những hạn chế, không đáp ứng đầy đủ yêu cầu của người sử dụng.
Ràng buộc về độ hỗ trợ và độ tin cậy của luật kết hợp chỉ mang ngữ nghĩa thống kê, không phản ánh được vai trò khác nhau của các thuộc tính cũng như đặc tính dữ liệu vốn có của chúng trong cơ sở dữ liệu. TIEU LUAN MOI download : skknchat@gmail.com 6 Để đáp ứng yêu cầu của thực tiễn, khai phá tập mục thường xuyên đã có nhiều cách thức mở rộng và ứng dụng, từ thay đổi phương pháp luận đến thay đổi đa dạng các kiểu dữ liệu, mở rộng các nhiệm vụ khai phá và đa dạng các ứng dụng mới. Trong những năm qua, đã có nhiều hướng mở rộng bài toán được quan tâm nghiên cứu. Chương một này sẽ trình bày các vấn đề cơ bản của bài toán khai pháp tập mục thường xuyên.
Một số khái niệm cơ bản về tập mục Định nghĩa 1.1: Cho tập mục (item) I={I1,I2,…,Im}. Một giao tác (transaction) T là một tập con của I, T⊆ I. Cơ sở dữ liệu giao tác là tập các giao tác DB={T1,T2, …, Tm}. Mỗi giao tác được gán một định danh Tid.
Một tập mục con X ⊆ I, gồm k mục phân biệt được gọi là k-tập mục. Giao tác T gọi là chứa tập mục X nếu X ⊆ T. Biểu diễn cơ sở dữ liệu giao tác: Cơ sở dữ liệu giao tác thường được biểu diễn ở dạng biểu diễn ngang, biểu diễn dọc và biểu diễn bởi ma trận giao tác. Biểu diễn ngang: cơ sở dữ liệu là một danh sách các giao tác.
Mỗi giao tác có một định danh Tid và một danh sách các mục dữ liệu trong giao tác đó. Giao tác Mục dữ liệu T1 A, C, D T2 B, C, E T3 A, B, C, E T4 B, E Bảng 1. Biểu diễn cơ sở dữ liệu giao tác ngang Biểu diễn dọc: Cơ sở dữ liệu là một danh sách các mục dữ liệu, mỗi mục dữ liệu có một danh sách tất cả các định danh của các giao tác chứa mục dữ liệu này. TIEU LUAN MOI download : skknchat@gmail.com 7 Mục dữ liệu Các giao tác A T1, T3 B T2, T3, T4 C T1, T2, T3 D T1 E T2, T3, T4 Bảng 2.
Biểu diễn cơ sở dữ liệu giao tác dọc Biểu diễn ma trận nhị phân: Cơ sở dữ liệu giao tác trên tập mục (item) được biểu diễn bởi ma trận nhị phân M = (mpq)mxn ở đó 1 ݇ℎ݅ ݅ ∈ ܶ ݉ = ൜ 0 ݇ℎ݅ ݅ ∉ ܶ Mục T1 T2 T3 T4 A 1 0 1 0 B 0 1 1 1 C 1 1 1 0 D 1 0 0 0 E 0 1 1 1 Bảng 3. Biểu diễn cơ sở dữ liệu giao tác ma trận I. Tập mục thường xuyên và luật kết hợp Định nghĩa 1.2: Cho tập mục X ⊆ I. Độ hỗ trợ (Support) của tập mục X trong cơ sở dữ liệu giao tác DB, ký hiệu sup(X), là tỷ lệ phần trăm của các giao tác chứa tập mục X trên tổng số giao tác trong DB, tức là: | {T ∈ DB | T ⊇ X } | sup( X ) = | DB | Định nghĩa 1.3: Cho tập mục X⊆I với ngưỡng hộ trợ tối thiểu (minimum support) minsup ∈ [0,1] (được xác định trước bởi người sử dụng).
X được gọi là tập mục thường xuyên (frequent itemset hoặc large itemset) với độ hỗ trợ tối TIEU LUAN MOI download : skknchat@gmail.com 8 thiểu minsup nếu sup(X) ≥ minsup, ngược lại X gọi là tập mục không thường xuyên.4: Một luật kết hợp là một biểu thức dạng X →Y, trong đó X và Y là các tập con của I, X∩Y=∅; X gọi là tiên đề, Y gọi là kết luận của luật. Luật kết hợp có hai thông số quan trọng là độ hỗ trợ và độ tin cậy. Như vậy độ hỗ trợ của luật kết hợp X →Y chính là xác suất P(X∪Y) của sự xuất hiện đồng thời của X và Y trong một giao tác. Ta có 0 ≤ sup (X →Y ) ≤ 1 Định nghĩa 1.6: Độ tin cậy (confidence) luật kết hợp, ký hiệu là conf(X→Y), là tỷ lệ phần trăm giữa số giao tác chứa X∪Y và số giao tác chứa X trong cơ sở dữ liệu DB.
Bài toán khai phá luật kết hợp Xác định tất cả X⇒ ⇒Y thỏa mãn độ hỗ trợ và độ tin cậy tối thiểu thì luật ⇒Y được gọi là luật kết hợp mạnh. X⇒ TIEU LUAN MOI download : skknchat@gmail. Một số tính chất của tập mục thường xuyên Cho cơ sở dữ liệu giao tác DB và ngưỡng độ hỗ trợ tối thiểu minsup. Các tập mục thường xuyên có tính chất sau: (1) Nếu X, Y là các tập mục và X ⊆ Y thì sup(X) ≥ sup(Y) (2) Nếu một tập mục là không thường xuyên thì mọi tập cha của nó cũng là không thường xuyên (3) Nếu một tập mục là thường xuyên thì mọi tập con khác rỗng của nó cũng là tập mục thường xuyên Tính chất (3) là tính chất quan trọng, nó được gọi là tính chất Apriori, tính chất này là cơ sở để rút gọn không gian tìm kiếm các tập mục thường xuyên.
Mô tả bài toán khai phá luật kết hợp Khai phá luật kết hợp là một kỹ thuật quan trọng của khai phá dữ liệu. Vấn đề này được Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất lần đầu vào năm 1993 [9]. Sau đó năm 1996 được Rakesh Agrawal, Heikki Mannia, Ramakrishnan Srikant, Hannu Toivonen, A.Inkeri Verkamo tiếp tục cải tiến. Ngày nay bài toán khai thác các luật kết hợp nhận được rất nhiều sự quan tâm của nhiều nhà khoa học.
Việc khai thác các luật như thế nào vẫn là một trong các phương pháp khai thác mẫu phổ biến nhất trong việc khám phá tri thức và khai thác dữ liệu (KDD – Knowledge Discovery and Data Minning). Mục đích chính của khai phá dữ liệu là trích rút tri thức một cách tự động, hiệu quả và “thông minh” từ kho dữ liệu. Trong hoạt động sản xuất kinh doanh, ví dụ kinh doanh các mặt hàng tại siêu thị, các nhà quản lý rất thích có được những thông tin mang tính thống kê như: “90% phụ nữ có xe máy màu đỏ và đeo đồng hồ Thụy Sỹ thì dùng nước hoa hiệu Chanel” hoặc “70% khách hàng là công nhân thì mua TV thường mua loại 21 inches”. Những thông tin như vậy rất hữu ích trong việc định hướng kinh doanh.
Vậy vấn đề đặt ra là liệu có tìm được các luật như vậy bằng các TIEU LUAN MOI download : skknchat@gmail.com 10 công cụ khai phá dữ liệu hay không? Câu trả lời là hoàn toàn có thể. Đó chính là nhiệm vụ khai phá luật kết hợp. Giả sử chúng ta có một CSDL D. Luật kết hợp cho biết phạm vi mà trong đó sự xuất hiện của tập các thuộc tính S nào đó trong các bản ghi (records) của D sẽ kéo theo sự xuất hiện của một tập những thuộc tính khác U cũng trong những bản ghi đó.
Mỗi luật kết hợp được đặc trưng bởi một cặp tỉ lệ hỗ trợ (support ration). Mỗi tỉ lệ hỗ trợ được biểu diễn bằng tỉ lệ % những bản ghi trong D chứa cả S và U. Vấn đề khám phá luật kết hợp được phát biểu như sau: Cho trước tỉ lệ hỗ trợ (support ration) θ và độ tin cậy (confidence) β Đánh số tất cả các luật trong D có các giá trị tỉ lệ hỗ trợ và tin cậy lớn hơn θ và β tương ứng. Ví dụ: Gọi D là CSDL mua bán và với θ = 40%, β = 90% Vấn đề phát hiện luật kết hợp được thực hiện như sau: Liệt kê (đếm) tất cả những quy luật chỉ ra sự xuất hiện một số các mục kéo theo một số mục khác.
Chỉ xét những quy luật mà tỉ lệ hỗ trợ lớn hơn 40% và độ tin cậy lớn hơn 90% Hay chúng ta hãy tưởng tượng, một công ty bán hàng qua mạng Internet. Các khách hàng được yêu cầu điền vào các mẫu bán hàng để công ty có một CSDL về các yêu cầu của khách hàng. Giả sử công ty quan tâm đến mối quan hệ “tuổi, giới tính, nghề nghiệp => sản phẩm”. Khi đó có thể có rất nhiều câu hỏi tương ứng với luật trên.
Ví dụ: trong lứa tuổi nào thì những khách hàng nữ là công nhân đặt mua mặt hàng gì đó, ví dụ áo dài chẳng hạn là nhiều nhất (thỏa mãn một ngưỡng nào đó)? Cho cơ sở dữ liệu giao tác DB, ngưỡng độ hỗ trợ tối thiểu minsup và ngưỡng độ tin cậy minconf. TIEU LUAN MOI download : skknchat@gmail.