CHƯƠNG 1: KHAI PHÁ LUẬT KẾT HỢP Nắm được những kiến thức cơ bản về khai phá dữ liệu và những khái niệm liên quan đến khai phá luật kết hợp như: tập mục dữ liệu, cơ sở dữ liệu giao tác, biểu diễn của cơ sở dữ liệu giao tác, độ hỗ trợ và độ tin cậy của tập mục dữ liệu, tập mục thường xuyên, bài toán khai phá luật kết hợpv.v…Trong phần tiếp theo của chương này, học viên sẽ trình bày hai thuật toán đầu tiên của khai phá luật kết hợp là AIS và Apriori.Thuật toán Apriori là một nội dung cơ sở để phục vụ cho nội dung chính của luận văn.1 Tổng quan về khai phá dữ liệu Khai phá dữ liệu (Data Mining) là một khái niệm ra đời vào những năm cuối của thập kỷ 1980. Chúng ta có thể hiểu một cách sơ lược rằng khai phá dữ liệu là quá trình tìm kiếm những thông tin (tri thức) hữu ích, tiềm ẩn và mang tính dự báo trong các tập dữ liệu lớn. Theo [7]: Khai phá dữ liệu là một quá trình phức tạp để tìm kiếm những mẫu hoặc những tri thức có giá trịtừ một lượng lớn dữ liệu. Các nguồn dữ liệu có thể bao gồm cơ sở dữ liệu, kho dữ liệu, các trang web, các kho thông tin khác, hoặc dữ liệu được nhập vào hệ thống một cách tự động.
Khai phá dữ liệu gồm những bước sau [7]: 1. Làm sạch dữ liệu: dữ liệu sau khi thu thập được có thể bị lỗi, nhiễu, không đầy đủ, có mâu thuẫn.Những dữ liệu dạng này được xem như thông tin dư thừa, gây nên những kết quả sai lệch. Do đó, cần phải làm sạch dữ liệu như gán các giá trị còn thiếu, sửa chữa các dữ liệu nhiễu/lỗi. Tích hợp dữ liệu: dữ liệu từ nhiều nguồn có thể được tích hợp với nhau.
Trích lọc dữ liệu: lấy ra những tập dữ liệu từ cơ sở dữ liệu ban đầu theo một số tiêu chí nhất định. Chuyển đổi dữ liệu: dữ liệu được chuyển từ bộ giá trị này sang một bộ giá trị thay thế phù hợp cho việc khai phá dữ liệu. Khai phá dữ liệu: sử dụng một kỹ thuật phương pháp nào đó để lấy ra được những mẫu dữ liệu (patterns. Đánh giá các mẫu: đánh giá những mẫu theo tiêu chí nào đó.
Biểu diễn tri thức: biểu diễn các mẫu trích xuất được dưới dạng dễ hiểu như đồ thị, hình vẽ, bảng,… Một số kỹ thuật được sử dụng trong khai phá kết hợp (chính là được sử dụng trong bước 5 của khai phá dữ liệu): Phân loại: phương pháp phân loại cho phép chúng ta phân loại một đối tượng vào một lớp. Mỗi lớp được đặc trưng bởi một số thuộc tính nào đó.Ví dụ chúng ta có z 10 thể phân loại thành các lớp xe máy khác nhau theo các thuộc tính như nhãn hiệu, phân khối, màu sắc. Khi có một chiếc xe mới chúng ta so sánh thuộc tính của nó với thuộc tính của những lớp đã được định nghĩa để phân xe đó vào một lớp cụ thể. Quá trình phân loại dữ liệu thường gồm hai bước: xây dựng mô hình và sử dụng mô hình để phân loại dữ liệu.
Bước 1(bước học): Xây dựng mô hình dựa trên việc phân tích các mẫu dữ liệu cho trước. Bước 2 (bước phân loại): Sử dụng mô hình để phân loại dữ liệu. Phân cụm: Phân cụm dữ liệu là quá trình chia một tập dữ liệu ban đầu vào các tập con (subsets). Mỗi một tập như vậy gọi là một cụm (cluster).
Các phần tử trong cùng một cụm thì tương tự nhau (similar), các phần tử trong các cụm khác nhau thì sẽ phi tương tự với nhau (dissimilar). Những phương pháp phân cụm khác nhau có thể sẽ sinh ra các cụm khác nhau trên cùng tập dữ liệu ban đầu. Phân cụm được sử dụng rộng rãi trong nhiều ứng dụng như kinh doanh thông minh (business intelligence), nhận dạng ảnh, tìm kiếm web, sinh học và an ninh,… Hồi quy: Theo Wikipedia, hồi quy là một phương pháp thống kê mà giá trị kỳ vọng của một hay nhiều biến ngẫu nhiên được dự đoán dựa vào điều kiện của các biến ngẫu nhiên (đã tính toán) khác. Cụ thể, có hồi qui tuyến tính, hồi qui lôgic, hồi qui Poisson và học có giám sát.
Khai phá luật kết hợp: nhằm phát hiện ra những phần tử nào thường hay đi kèm với nhau.2 Giới thiệu về khai phá luật kết hợp Khai phá luật kết hợp (Mining association rules) lần đầu được RakeshAgrawal Agrawal đưa ra vào năm 1993 [5]. Khai phá luật kết hợp là một kỹ thuật được sử dụng trong khai phá dữ liệu nhằm tìm ra các phần tử thường xuất hiện cùng nhau trong cơ sở dữ liệu;từ đấyrút ra được các luật về ảnh hưởng của một tập phần tử dẫn đến sự xuất hiện của tập phần tử khác. Ví dụ, sự xuất hiện của A kéo theo sự xuất hiện của B nên ta có luật kết hợp (A→B). Dạng luật như vậy được gọi là luật kết hợp và quá trình tìm ra được các luật kết hợp được gọi là khai phá luật kết hợp.
Luật kết hợp là dạng luật khá đơn giản nhưng mang lại khá nhiều ý nghĩa. Thông tin mà luật kết hợp cung cấp hỗ trợ đáng kể trong quá trình đưa ra quyết định. Các giải thuật khai phá luật kết hợp tìm kiếm các mối liên kết giữa các phần tử dữ liệu, ví dụ như nhóm các món hàng thường được mua kèm với nhau trong siêu thị. Những nghiên cứu về luật kết hợp gần đây tập trung xây dựng các thuật toán khai phá luật kết hợp mới, hiệu quả hoặc cải tiến, phát triển các thuật toán hiệu quả hơn từ các thuật toán đã có.
Chúng ta xem xét một bài toán kinh điển về khai phá luật kết hợp được nêu ra trong [7]: bài toán phân tích giỏ hàng. Khách hàng vào siêu thị mua hàng. Họ sẽ bỏ z 11 vào giỏ hàng của họ những mặt hàng mà họ cần mua.Khai phá luật kết hợp trong bài toán này nhằm tìm ra các luật kết hợp giữa các mặt hàng mà khách hàng đã mua. Một số luật kết hợp rút ra được sau khi phân tích các mặt hàng được mua: “98% khách hàngmàmua tạp chí thể thao thì đều mua các tạp chí về ôtô” sự kết hợp giữa “tạp chí thể thao” với “tạp chí về ôtô”.
“60% khách hàng mà mua bia tại siêu thị thì đều mua bỉm trẻ em” sự kết hợp giữa “bia” với “bỉm trẻ em”. Những luật kết hợp như vậy rất có ích trong việc giúp các nhà quản lý nắm bắt được thói quen mua hàng của khách hàng, khi mua một (hoặc một số) mặt hàng này thì khách hàng có xu hướng mua thêm một số mặt hàng nào nữa. Từ đấy có những chiến lược quản lý hợp lý. Như vậy, khai phá luật kết hợp có thể giải quyết được bài toán hết sức đời thường như: hàng triệu khách hàng vào siêu thị sẽ mua mặt hàng nào? Những mặt hàng nào mà khách hàng kết hợp cùng mua.
Tất nhiên, khai phá luật kết hợp cũng có nhiều ý nghĩa trong các lĩnh vực khác như tài chính, y học, công nghệ… Khai phá luật kết hợp nhằm tìm ra sự tương quan (correlations) của các sự kiện xuất hiện thường xuyên một cách đồng thời. Nhiệm vụ chính của khai phá luật kết hợp là phát hiện ra các tập con cùng xuất hiện trong một khối lượng giao dịch lớn của một cơsởdữliệu cho trước. Nói cách khác, thuật toán khai phá luật kết hợp cho phép tạo ra các luật mô tảcác sựkiện xảy ra đồng thời (một cách thường xuyên) nhưthếnào. Bài toán khai phá luật kết hợp được chia thành hai bài toán nhỏ: Bài toán 1: Tìm các tập mục dữ liệu thường xuyên theo một ngưỡng S0 cho trước.
Bài toán 2: Từ các tập mục dữ liệu thường xuyên tìm được ở bài toán 1, tìm các luật kết hợp thỏa mãn độ tin cậy cho trước. Bài toán thứ hai là bài toán đơn giản. Hầu hết các nghiên cứu về luật kết hợp tập trung vào bài toán thứ nhất. Nội dung luận văn này cũng đi sâu vào nghiên cứu một số thuật toán để tìm các tập mục dữ liệu thường xuyên.3 Một số khái niệm cơ bản [3, 5, 7] 1.1 Cơ sở dữ liệu giao tác Tập hợp các mục dữ liệuI={x1, x2, …, xn} là tập n thuộc tính (mục dữ liệu) riêng biệt.
Mỗi xi ∈ I gọi là một mục dữ liệu (item) hay là một thuộc tính. Ví dụ: I= {bánh mì, sữa, bỉm,…). Một giao tác chứa một tập con {x , x , … , x } ⊆ I. Đặt ti = {x , x , … , x } , ti được gọi là định danh của giao tác{x , x , … , x }.
Một cơ sở dữ liệu giao tác (Transaction Database) trên I là một tập các định danh giao tác T = {t1, t2,…,tm}, với ti là một định danh giao tác trên Ichứa một tập các mục dữliệu X ⊆ I. Ví dụ, trong bài toán giỏ hàng, cơ sở dữ liệu giao tác là các lầnmua z 12 hàng của mỗi khách hàng, cho biết trong một lần mua hàng, khách hàng mua những mặt hàng nào. Mỗi tập con X ⊆ I chứa k mục dữ liệu được gọi là tập mục k phần tử (k-itemset). Khi đó ta nói rằng lực lượng của X bằng k (||X|| = k).
Trong trường hợp không quan tâm đến số mục dữ liệu của X, ta gọi tắt X là tập mục dữ liệu. Biểu diễn cơ sở dữ liệu giao tác: Ma trận giao tác: cho một cơ sở dữ liệu giao tác T = {t1, t2,…,tm} trên tập mục dữ liệu I={x1, x2, …, xn}. Ma trận giao tác của T là ma trận m×n được định nghĩa: 1 ℎ ∈ = 0 ℎ ∉ Với một cơ sở dữ liệu giao tácTnhư sau thì ta sẽ có ma trận giao tác như trong bảng 1.1: Ma trận giao tác của cơ sở dữ liệu giao tác T x0 x1 x2 x3 x4 t0 1 1 1 0 0 t1 1 1 1 1 1 t2 1 0 1 1 0 t3 1 0 1 1 1 t4 1 1 1 1 0 -Biểu diễn ngang: Một cơ sở dữ liệu là một danh sách các giao tác. Mỗi giao tác chứa danh sách những mục dữ liệu trong giao tác đó.
Như vậy chúng ta có thể hình dung theo cách này thì các mục dữ liệu được biểu diễn theo chiều ngang.