CHƯƠNG 1 KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP 1. Khai phá dữ liệu 1. Quá trình phát hiện tri thức từ cơ sở dữ liệu Trong thời đại hiện đại của thế kỷ 21, với sự phát triển vượt bậc của công nghệ thông tin, các hệ thống thông tin có thể lưu trữ một khối lượng lớn dữ liệu về hoạt động hàng ngày của chúng. Lượng dữ liệu được lưu trữ dẫn đến một đòi hỏi cấp bách phải có những kỹ thuật mới, những công cụ tự động mới trợ giúp con người một cách thông minh trong việc chuyển đổi một lượng lớn dữ liệu thành thông tin hữu ích.
Một số nhà khoa học xem khai phá dữ liệu như là một cách gọi khác của một thuật ngữ cũng rất thông dụng là khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases – KDD)[5], vì cho rằng mục đích của quá trình khám phá tri thức là thông tin và tri thức có ích, nhưng đối tượng mà chúng ta phải xử lý rất nhiều trong suốt quá trình khám phá tri thức lại chính là dữ liệu. Một số nhà khoa học khác thì xem khai phá dữ liệu như là một bước chính trong quá trình khám phá tri thức. Hiểu quá trình khám phá, phát hiện tri thức ở đây là gì? Thông thường chúng ta coi dữ liệu như là một dãy các bit, các số và các ký hiệu, hoặc các “đối tượng” được gửi cho một chương trình dưới một định dạng nhất định nào đó. Chúng ta sử dụng các bit để đo lường thông tin, khi sử dụng xem nó như là dữ liệu đã được lọc bỏ dư thừa, được rút gọn tới mức tối thiểu.
Bít được dùng làm đơn vị đặc trưng cho dữ liệu. Chúng ta có thể xem tri thức như là các thông tin tích hợp, bao gồm các sự kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể được học, được hiểu, được phát hiện ra. Nói cách khác, tri thức có thể coi là dữ liệu có độ trừu tượng và tổ chức cao.
Thuật ngữ KPDL ra đời vào những năm cuối của thập kỷ 1980. Khai phá dữ liệu bao gồm nhiều hướng tiếp cận, là sự kết hợp của nhiều ngành như: Cơ sở dữ liệu; Học máy; Trí tuệ nhân tạo; Lý thuyết thông tin; Xác suất thống kê; Tính toán hiệu năng cao và các phương pháp tính toán mềm v. Có rất nhiều định nghĩa khác nhau về "KPDL" đã được đưa ra, ta có thể hiểu khai phá dữ liệu là quá trình tìm kiếm những thông tin (tri thức) có ích, tiềm ẩn và mang tính dự đoán trong các khối cơ sở dữ liệu lớn. 4 KPDL là cốt lõi của quá trình khám phá tri thức.
Nó gồm có các giải thuật KPDL chuyên dùng, dưới một số quy định về hiệu quả tính toán chấp nhận được. KPDL là nhằm tìm ra những mẫu mới, mẫu có tính chất không tầm thường, những thông tin tiềm ẩn mang tính dự đoán chưa được biết đến và có khả năng mang lại lợi ích cho người sử dụng. Nói tóm lại, mục đích chung của việc phát hiện tri thức từ dữ liệu và KPDL là tìm ra các mẫu được quan tâm nhất tồn tại trong cơ sở dữ liệu, nhưng chúng lại bị che dấu bởi một số lượng lớn dữ liệu. Quá trình khám phá tri thức được tiến hành qua các bước sau [5]: Các Tri thức Các mẫu Dữ liệu đã sạch Dữ liệu đã chọn 5.Đánh giá và biểu diễn tri thức knowledge representation & evaluation 4.Khai phá dữ liệu Kho data mining dữ 3.Biến đổi dữ liệu liệu data transformation 2.
Tiền xử lý dữ liệu data preprocessing 1. Trích chọn dữ liệu data selection Hình 1. Quá trình khám phá tri thức Bước 1: Trích chọn dữ liệu (data selection): là bước trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (databases, data warehouses). Bước 2: Tiền xử lý dữ liệu (data preprocessing): là bước làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, v.
v), rút gọn dữ liệu (sử dụng các phương pháp thu gọn dữ liệu, histograms, lấy 5 mẫu, .v ), rời rạc hoá dữ liệu (dựa vào histograms, entropy, phân khoảng, v. Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và được rời rạc hoá. Bước 3: Biến đổi dữ liệu (data transformation): là bước chuẩn hoá và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở bước sau. Bước 4: Khai phá dữ liệu (data mining): đây là bước quan trọng và tốn nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật khai phá(phần lớn là các kỹ thuật của machine learning) để khai phá, trích chọn được các mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu.
Bước 5: Đánh giá và biểu diễn tri thức (knowledge representation & evaluation): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã được khai phá ở bước trên biểu diễn theo dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật,. Đồng thời bước này cũng đánh giá những tri thức khai phá được theo những tiêu chí nhất định. Trong giai đoạn khai phá dữ liệu, có thể cần sự tương tác của người dùng để điều chỉnh và rút ra các tri thức cần thiết nhất. Các tri thức nhận được cũng có thể được lưu và sử dụng lại.
Quá trình khai phá dữ liệu Với những dữ liệu đã thu thập, ta tiến hành tích hợp và chỉnh sửa dữ liệu, lọc dữ liệu, đây là quá trình tiền xử lý. Dữ liệu được thu thập từ nhiều nguồn khác nhau, qua những dữ liệu trực tiếp ta thống kê tóm tắt, trong khi đó có thể có những sự sai sót, dư thừa và trùng lặp. Lọc dữ liệu là cắt bỏ những dư thừa để dữ liệu được định dạng thống nhất. Quá trình khai phá dữ liệu được thể hiện bởi hình 1.3 sau: Thống kê tóm tắt Xác định Xác định dữ Thu thập và Giải thuật Mẫu nhiệm vụ liệu liên quan tiền xử lý DL khai phá DL Dữ liệu trực tiếp 6 Hình 1.3: Quá trình khai phá dữ liệu Công việc tiếp theo sử dụng các thuật toán khác nhau để khai phá các tri thức tiềm ẩn trong kho dữ liệu sau khi đã xử lý và được thống kê tóm tắt,….
Kết quả của quá trình khai phá dữ liệu là đạt được nhiệm vụ đặt ra. Nhiều kỹ thuật khai phá dữ liệu được ứng dụng cho một nguồn dữ liệu, các kỹ thuật cho các kết quả có thể khác nhau. Các kết quả được ước lượng bởi những quy tắc nào đó, nếu cuối cùng kết quả không thỏa mãn yêu cầu, chúng ta phải làm lại với kỹ thuật khác cho đến khi có kết quả mong muốn. Các ứng dụng của khai phá dữ liệu Vào những năm của thế kỷ XX, khi công nghệ thông tin bùng nổ cả về bề rộng và chiều sâu, ảnh hưởng đến hầu hết các lĩnh vực khoa học, kinh tế và đời sống xã hội.
Dữ liệu ngày càng tăng theo thời gian, người ta coi khai phá dữ liệu là quá trình phân tích cơ sở dữ liệu nhằm phát hiện ra các thông tin mới và giá trị, thường thể hiện dưới dạng các mối quan hệ chưa biết đến giữa các mục dữ liệu. Nhờ phân tích các dữ liệu mà các doanh nghiệp có khả năng dự báo trước một số hành vi ứng xử của khách hàng. Công nghệ thông tin phát triển đồng nghĩa với việc phát triển các phần mềm ứng dụng. Phần mềm khai phá dữ liệu là một công cụ phân tích dùng để phân tích dữ liệu.
Nó cho phép người sử dụng phân tích dữ liệu theo nhiều góc nhìn khác nhau, phân loại dữ liệu theo những quan điểm riêng biệt và tổng kết các mối quan hệ đã được bóc tách. Hiện nay, kỹ thuật khai phá dữ liệu đang được áp dụng một cách rộng rãi trong rất nhiều lĩnh vực kinh doanh và đời sống khác nhau như: Thương mại: Phân tích dữ liệu bán hàng và thi trường, phân tích đầu tư, quyết định cho vay, phát hiện gian lận, … Thông tin sản xuất: Điều khiển và lập kế hoạch, hệ thống quản lý, phân tích kết quả thử nghiệm, … Thông tin khoa học: dự báo thời tiết, CSDL sinh học: Ngân hàng gen, …khoa học địa lý: dự báo động đất, … Trong y tế, marketing, ngân hàng, viễn thông, du lịch, internet… Những gì thu được từ khai phá dữ liệu thật đáng giá. Điều đó được chứng minh bằng thực tế: Chẩn đoán bệnh trong y tế dựa trên kết quả xét nghiệm đã giúp cho bảo hiểm y tế phát hiện ra nhiều trường hợp xét nghiệm 7 không hợp lý, tiết kiệm được nhiều kinh phí mỗi năm; Trong dịch vụ viễn thông đã phát hiện ra những nhóm người phổ biến gọi cho nhau bằng mobile và thu lợi hàng triệu USD; IBM Suft-Aid đã áp dụng khai phá dữ liệu vào phân tích các lần đăng nhập Web vào các trang liên quan đến thị trường để phát hiện sở thích khách hàng, từ đó đánh giá hiệu quả của việc tiếp thị qua Web và cải thiện hoạt động của các Website; trang Web mua bán qua mạng cũng tăng doanh thu nhờ áp dụng khai phá dữ liệu trong việc phân tích sở thích mua bán của khách hàng. Khai phá luật kết hợp trong cơ sở dữ liệu 1.
Các khái niệm cơ sở Mô hình đầu tiên của bài toán khai phá luật kết hợp là mô hình nhị phân (hay còn gọi là mô hình cơ bản) được R. Swami đề xuất vào năm 1993 [4], xuất phát từ nhu cầu phân tích dữ liệu của cơ sở dữ liệu giao tác, phát hiện các mối quan hệ giữa các tập mục hàng hóa (Itemsets) đã bán được tại các siêu thị. Việc xác định các quan hệ này không phân biệt vai trò khác nhau cũng như không dựa vào các đặc tính dữ liệu vốn có của các mục dữ liệu mà chỉ dựa vào sự xuất hiện cùng lúc của chúng. Phần tiếp sau đây nêu một số khái niệm cơ bản dẫn đến bài toán khai phá tập mục phổ biến và luật kết hợp.
Cơ sở dữ liệu giao tác Định nghĩa 2.1: Cho tập các mục (item) I i1 , i2 ,. Một giao tác (transaction) T là một tập con của I, TI. Cơ sở dữ liệu giao tác là một tập các giao tác DB T1 ,T2 ,. 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à một k-tập mục. Giao tác T gọi là chứa tập mục X nếu X T .