Đồ án Khai phá và làm sạch dữ liệu

Lời cám ơn Cám ơn các thày cô giáo trường Đại học Dân lập Hải Phòng, đã dạy dỗ chúng em trong nhiều năm qua. Cám ơn thày Trần Hữu Nghị đã cho em một mái trường để cho chúng em có cơ hội học được những kiến thức bổ ích để có thể trở thành một công dân có ích cho xã hội. Xin chân thành cám ơn thày cô bộ môn Tin học đã truyền đạt kiến thức về công nghệ thông tin, một môn học bổ ích, là hành trang vững chắc để em tự tin trong những công việc được giao phó trong thời gian tới. Cám ơn thày Đỗ Trung Tuấn, trường đại học tự nhiên; cám ơn thày Vương Đạo Vy, trường đại học công nghệ, Đại học Quốc gia Hà nội đã giúp đỡ em trong quá trình thực tập, viết luận văn cũng như quá trình học tập trên ghế nhà trường. Đặc biệt là thày Đỗ Trung Tuấn đã tận tình giúp đỡ em trong quá trình thực tập, đã tạo điều kiện cho em được thực tập tại ban công nghệ trường Đại học quốc gia Hà Nội để em có thể đem kiến thức mình đã học được trên ghế nhà trường áp dung vào thực tiễn để em có thể nhận thấy mình đã trang bị được những gì còn thiếu những gì trong hành trang của mình. Cám ơn các anh chị trong ban công nghệ trường Đại học quốc gia Hà Nội đã tận tình chỉ bảo em trong quá trình thực tập tại ban. Cám ơn gia đình và người thân, đã tận tình giúp đỡ, chu cấp tài chính, động viên em trong suốt thời gian học tập tại trường. Xin cám ơn các bạn bè trong lớp và các bạn trong khoa cũng như sinh viên cả trường đã giúp đỡ tôi trong thời gian học tập cũng như trong thời gian làm thực tập tốt nghiệp. MỤC LỤC Lời cám ơn 1 MỤC LỤC 2 CHƯƠNG 1: Mở đầu 3 CHƯƠNG 2: CSDL và nhu cầu dữ liệu Meta 4 2.1. Mô hình dữ liệu quan hệ 4 2.2. Nhu cầu về dữ liệu meta 4 CHƯƠNG 3: Khai phá dữ liệu 6 3.1. Giới thiệu về khai phá dữ liệu 6 3.1.1. Giới thiệu chung 6 3.1.2. Về khai phá dữ liệu 7 3.1.3. Quá trình phát hiện tri thức trong CSDL 7 3.1.4. Nhiệm vụ chính trong khai phá dữ liệu 8 3.1.5. Các kĩ thuật khai phá dữ liệu 10 3.1.6. Ứng dụng của khai phá dữ liệu 12 3.1.7. Khai phá luật kết hợp và ứng dụng 13 3.2. Một thuật toán về khai phá dữ liệu 13 3.2.1. Ý tưởng thuật toán Apriori 13 3.2.2. Thuật toán Apriori 14 3.2.3. Ví dụ minh hoạ thuật toán Apriori 16 CHƯƠNG 4: Luật kết hợp và các tiếp cận 18 4.1. Khai phá luật kết hợp 18 4.2. Lý thuyết về luật kết hợp 18 4.3. Một số hướng tiếp cận trong khai phá luật kết hợp 20 CHƯƠNG 5: Thử nghiệm 21 5.1. Phân tích, thiết kế ứng dụng 21 5.1.1. Bài toán văn hoá 21 5.1.2. Mô tả dữ liệu 21 5.1.3. Áp dụng thuật toán khai phá dữ liệu. 22 5.2. Thực hiện khai phá dữ liệu 23 5.2.1. Giới thiệu chương trình 23 5.2.2. Kết quả chương trình 25 CHƯƠNG 6: Kết luận 28 6.1. Kết quả đạt dược của luận văn 28 6.2. Phát triển luận văn 28 Mở đầu Nhu cầu về xử lí dữ liệu trong cuộc sống số ngày nay là hiện thực và cấp bách. Công nghệ thông tin cho phép người ta xây dựng xã hội tri thức, biến thông tin thành tiền bạc và quyền lực. Từ vài thập niên gần đây, với sự phát triển mạnh mẽ của công nghệ thông tin và hệ thống truyền thông thế giới đã có những bước tiến triến mới mà ở đó thông tin và tri thức đóng vai trò rất quan trọng trong mọi mặt đời sống. Việc lưu trữ, tổ chức thông tin làm sao cho hiệu quả nhất là một vấn đề được đặt ra. Việc xử lí dữ liệu cần đến kiến thức về cơ sở dữ liệu (CSDL). Nghiên cứu CSDL yêu cầu nghiên cứu về (i) hệ thống thông tin; (ii) hệ quản trị file và hệ quản trị CSDL; (iii) mô hình dữ liệu; (iv) quản trị bên trong hệ quản trị CSDL… Trong CSDL, người ta dùng nhiều loại dữ liệu, với mục đích khác nhau. có dữ liệu về (i) số; (ii) văn bản; (iii) đồ hoạ; (iv) video; (iv) dữ liệu meta… Dữ liệu meta có vai trò quan trọng, cho biết mối quan hệ giữa các dữ liệu và tri thức về CSDL. Việc chỉ ra các dữ liệu meta có thể thực hiện thông qua tri thức người dùng khi mô tả các điều kiện toàn vẹn dữ liệu; qua mô hình dữ liệu về thế giới thực; qua việc khai phá dữ liệu. Luận văn này trình bày về một khía cạnh trong các khía cạnh nghiên cứu trên. Đó chính là khai phá dữ liệu. Luận văn được chia thành các chương : Chương 1. Mở đầu. Chương 2. CSDL và nhu cầu về dữ liệu meta. Chương 3. Khai phá dữ liệu. Chương 4. Luật kết hợp và các tiếp cận. Chương 5. Thử nghiệm việc khai phá dữ liệu. Chương 6. Kết luận CSDL và nhu cầu dữ liệu Meta Mô hình dữ liệu quan hệ Hiện nay mô hình dữ liệu được sử dụng rộng rãi nhất là mô hình dữ liệu quan hệ gọi tắt là mô hình quan hệ được E.F.Codd đề xuất năm 1970 và ngày càng có nhiều hệ quản trị CSDL cho mô hình này gọi là các hệ quản trị CSDL quan hệ. Mô hình được xây dựng dựa trên lý thuyết tập hợp nên dễ hiểu và dễ biểu diễn bằng toán học. Mô hình này bao gồm: Một hệ thống các ký hiệu để mô tả dữ liệu dưới dạng dòng và cột như quan hệ, bộ, thuộc tính, khoá chính, khoá ngoài,… Một tập hợp các phép toán thao tác trên dữ liệu như phép toán tập hợp, phép toán quan hệ. Ràng buộc toàn vẹn quan hệ. Nhu cầu về dữ liệu meta Trong vài thập niên với những tác động mạnh mẽ của các tiến bộ trong công nghệ công nghệ thông tin và truyền thông, các hệ thống dữ liệu phục vụ cho các lĩnh vực kinh tế xã hội đã phát triển, nhu cầu về dữ liệu ngày càng nhiều. Sự phong phú về dữ liệu, thông tin cùng với khả năng khai thác kịp thời chúng đã mang đến những năng xuất và chất lượng mới cho các công tác quản lý, hoạt động kinh doanh. Yêu cầu về các thông tin trong các lĩnh vực hoạt động đó đòi hỏi cao hơn, người quyết định không những cần dữ liệu mà còn cần có thêm nhiều hiểu biết, nhiều tri thức để hỗ trợ cho việc ra quyết định của mình. Những năm 90 của thế kỷ trước, nhu cầu khám phá tri thức mới là thực sự, với các nghiên cứu về tổ chức các kho dữ liệu và kho thông tin, các hệ trợ giúp ra quyết định, các thuật toán nhận dạng mẫu, phân lớp,...và đặc biệt là khai phá dữ liệu. Khai phá dữ liệu trở thành một trong những hướng nghiên cứu thu hút sự quan tâm của nhiều người nghiên cứu trong lĩnh vực khác nhau như hệ thống CSDL, thống kê, trí tuệ nhân tạo,... Kho dữ liệu có thể giúp khai thác thông tin bằng các công cụ truy vấn, chiết xuất thông tin và báo cáo cũng như được sử dụng để hỗ trợ việc phân tích trực tuyến, kiểm định các giả thuyết. Tuy nhiên chỉ có kho dữ liệu thì chưa thể có được tri thức, nếu dữ liệu được phân tích một cách thông minh thì chúng sẽ là nguồn tài nguyên vô cùng quý giá. Từ những khối lượng khổng lồ dữ liệu có sẵn, tìm ra những thông tin tiềm ẩn có giá trị, chưa được phát hiện, những xu hướng phát triển và những yếu tố tác động lên chúng là một điều hết sức cần thiết. Tiến hành như vậy chính là thực hiện quá trình phát hiện tri thức trong CSDL. Quá trình phát hiện tri thức gồm nhiều giai đoạn, trong đó giai đoạn khai phá dữ liệu là giai đoạn chủ yếu. Giai đoạn khai phá dữ liệu được thực hiện sau các khâu tinhlọc và tiền xử lý dữ liệu, nhằm tìm ra các mẫu, các xu hướng có ý nghĩa từ các tập dữ liệu. Chỉ có các mẫu, các xu hướng được xem là đáng quan tâm, theo một phương diện nào đó, mới được coi là tri thức. Tri thức là có ích khi nó có thể giúp đạt được mục đích của hệ thống hoặc người dùng. Các kỹ thuật khai phá dữ liệu được chia làm ba mảng cơ bản (i) phân lớp / phân cụm dữ liệu; (ii) các luật kết hợp; và (iii) khai phá chuỗi. Khai phá luật kết hợp trong những CSDL lớn lần đầu tiên xuất hiện vào năm 1993 và hiện tại đã và đang được nghiên cứu, phát triển rất mạnh, trở thành một khuynh hướng quan trọng của khai phá dữ liệu. Ở Việt Nam, trong những năm trở lại đây, nhu cầu về tự động khám phá tri thức từ các dữ liệu có sẵn nhằm tăng năng lực cạnh tranh của các ngành kinh tế đang phát triển nhanh.  Khai phá dữ liệu Giới thiệu về khai phá dữ liệu Giới thiệu chung Những năm 60 của thế kỷ trước, người ta bắt đầu sử dụng các công cụ tin học để tổ chức và khai thác các CSDL. Cùng với sự phát triển vượt bậc của các công nghệ điện tử và truyền thông, khả năng thu thập, lưu trữ và xử lý dữ liệu cho các hệ thống tin học không ngừng được nâng cao, theo đó, lượng thông tin được lưu trữ trên các thiết bị như đĩa từ, băng từ, đĩa CD-ROM,... không ngừng tăng lên. Theo thống kê sơ bộ, lượng thông tin trên các hệ thống tin học cứ sau 20 tháng lại tăng lên gấp đôi. Cuối thập kỷ 80 của thế kỷ 20, sự phát triển rộng khắp của các CSDL ở mọi quy mô đã tạo ra sự bùng nổ thông tin trên toàn cầu, vào thời gian này, người ta bắt đầu đề cập đến khái niệm khủng hoảng phân tích dữ liệu tác nghiệp để cung cấp thông tin với yêu cầu chất lượng ngày càng cao cho người làm quyết định trong các tổ chức tài chính, thương mại, khoa học. Người ta nói “Chúng ta đang chìm ngập trong dữ liệu mà vẫn đói tri thức”. Lượng dữ liệu khổng lồ này thực sự là một nguồn “tài nguyên” có nhiều giá trị bởi thông tin là yếu tố then chốt trong mọi hoạt động quản lý, kinh doanh, phát triển sản xuất và dịch vụ,... Nó giúp những người điều hành và quản lý có hiểu biết về môi trường và tiến trình hoạt động của các tổ chức trước khi ra quyết định để tác động đến quá trình hoạt động nhằm đạt được mục tiêu một cách hiệu quả và bền vững. Khai phá dữ liệu là một lĩnh vực mới, nhằm tự động khai thác những thông tin, những tri thức có tính tiềm ẩn, hữu ích từ những CSDL lớn cho các đơn vị, tổ chức, doanh nghiệp,... làm thúc đẩy khả năng sản xuất, kinh doanh, cạnh tranh cho các đơn vị, tổ chức. Các kết quả khoa học cùng những ứng dụng thành công trong khám phá tri thức, cho thấy khai phá dữ liệu có thể phát triển bền vững, mang lại nhiều lợi ích và có nhiều triển vọng, đồng thời có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Hiện nay, khai phá dữ liệu đã ứng dụng ngày càng rộng rãi trong các lĩnh vực, như thương mại, tài chính, điều trị y học, viễn thông tin – sinh,... Về khai phá dữ liệu Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỷ 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy trong tập dữ liệu. Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện tri thức trong CSDL, để chỉ toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn; trong đó khai phá dữ liệu là một bước đặc biệt trong toàn bộ quá trình, sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu hay các mô hình từ dữ liệu. Ở một mức độ trừu tượng nhất định có thể định nghĩa về khai phá dữ liệu : Data Mining là một quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong CSDL lớn. Khám phá tri thức (KDD) là mục tiêu chính của khai phá dữ liệu, do vậy hai khái niệm đó được xem như hai lĩnh vực tương đương nhau. Nhưng, nếu phân chia một cách tách bạch thì khai phá dữ liệu là một bước chính trong quá trình KDD. Quá trình phát hiện tri thức trong CSDL Khám phá tri thức trong CSDL (KDD) là lĩnh vực liên quan đến các ngành như: thống kê, học máy, CSDL, thuật toán, trực quan hoá dữ liệu, tính toán song song và hiệu năng cao,… Mục đích của quá trình phát hiện tri thức là rút ra tri thức từ dữ liệu trong CSDL lớn. Quá trình KDD là quá trình gồm nhiều giai đoạn và lặp lại, mà trong đó sự lặp lại có thể xuất hiện ở bất cứ bước nào. Quá trình đó có thể được mô tả theo hình sau:
Các bước thực hiện trong quá trình phát hiện tri thức Bước thứ nhất là tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu. Bước thứ hai là thu thập và xử lý thô, còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu, xử lý việc thiếu dữ liệu, biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết, bước này thường chiếm nhiều thời gian nhất trong toàn bộ qui trình phát hiện tri thức. Bước thứ ba là khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/và các mô hình ẩn dưới các dữ liệu. Bước thứ tư là hiển thị tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực hiện. Nhiệm vụ chính trong khai phá dữ liệu Mục đích của khai phá dữ liệu là chiết xuất các tri thức từ dữ liệu. Do đó có thể coi mục đích chính của khai phá dữ liệu sẽ là mô tả và dự đoán. Các mẫu mà khai phá dữ liệu phát hiện được nhằm vào các mục đích này. Dự đoán liên quan đến việc sử dụng các biến hoặc các trường trong CSDL để chiết xuất ra các mẫu là các dự đoán những giá trị chưa biết hoặc những giá trị trong tương lai của các biến đáng quan tâm. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con người có thể hiểu được. Nhiệm vụ chính của khai phá dữ liệu : Phân lớp, phân loại. Phân loại là việc xác định một hàm ánh xạ từ một mẫu dữ liệu vào một trong số các lớp đã được biết trước đó. Mục tiêu của thuật toán phân lớp là tìm ra mối quan hệ nào đó giữa thuộc tính dự báo và thuộc tính phân lớp. Như thế quá trình phân lớp có thể sử dụng mối quan hệ này để dự báo cho các mục mới. Các kiến thức được phát hiện biểu diễn dưới dạng các luật theo cách sau: “Nếu các thuộc tính dự báo của một mục thoả mãn điều kiện của các tiền đề thì mục đó nằm trong lớp chỉ ra trong kết luận”. Thí dụ một mục biểu diễn thông tin về nhân viên có các thuộc tính dự báo là: họ tên, tuổi, giới tính, trình độ học vấn, … và thuộc tính phân loại là trình độ lãnh đạo của nhân viên. Hồi quy. Hồi quy là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực. Có rất nhiều ứng dụng khai phá dữ liệu với nhiệm vụ hồi quy, ví dụ như dự đoán số lượng biomass xuất hiện trong rừng biết các phép đo vi sóng từ xa, đánh giá khả năng tử vong của bệnh nhân biết các kết quả xét nghiệm chẩn đoán, dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chỉ tiêu quảng cáo, dự đoán theo thời gian với các biến đầu vào là các giá trị của mẫu dự đoán trong quá khứ, v.v… Phân nhóm là việc mô tả chung để tìm ra các tập xác định các nhóm hay các loại để mô tả dữ liệu. Các nhóm có thể tách riêng nhau hoặc phân cấp hoặc gối lên nhau. Có nghĩa là một dữ liệu có thể vừa thuộc nhóm này, vừa thuộc nhóm kia. Các ứng dụng khai phá dữ liệu có nhiệm vụ phân nhóm như: phát hiện tập các khách hàng có phản ứng giống nhau trong CSDL tiếp thị, xác định các loại quang phổ từ các phương pháp đo tia hồng ngoại. Tóm tắt liên quan đến các phướng pháp tìm kiếm một mô tả tóm tắt cho một tập con dữ liệu. Ví dụ như việc lập bảng các độ lệch chuẩn và trung bình cho tất cả các trường. Các phương pháp phức tạp hơn liên quan đến nguồn gốc của các luật tóm tắt, khai thác mối liên hệ hàm giữa các biên. Các kỹ thuật tóm tắt thường được áp dụng cho các phân tích dữ liệu tương tác có tính thăm dò và tạo báo cáo tự động. Mô hình hóa phụ thuộc bao gồm việc tìm kiếm một mô hình mô tả sự phụ thuộc đáng kể giữa các biến. Các mô hình phụ thuộc tồn tại dưới hai mức: Mức cấu trúc của mô hình xác định (thường ở dạng đồ họa) các biến nào là phụ thuộc cục bộ với nhau Mức định lượng của một mô hình xác định độ mạnh của sự phụ thuộc theo một thước đo nào đó. Ví dụ như các mạng phụ thuộc xác suất sử dụng độc lập có điều kiện để xác định khía cạnh có cấu trúc của một mô hình và các xác suất hoặc tương quan để xác định độ mạnh của sự phụ thuộc. Các mạng phụ thuộc xác suất đang ngày càng tìm thấy nhiều ứng dụng trong các lĩnh vực khác nhau như phát triển các hệ chuyên gia y tế áp dụng tính xác suất từ các CSDL, thu thập thông tin, mô hình hóa gen di truyền của người. Phát hiện sự thay đổi và chuyển hướng. Tiếp cận tập trung vào khai thác những thay đổi đáng kể nhất trong dữ liệu từ các giá trị chuẩn hoặc được đo trước đó. Các kĩ thuật khai phá dữ liệu Các kĩ thuật tiếp cận Khám phá tri thức trong CSDL là một lĩnh vực liên ngành, bao gồm: Tổ chức dữ liệu, học máy, trí tuệ nhân tạo và các khoa học khác, sự kết hợp này có thể được diễn tả như trong hình dưới
Các lĩnh vực liên quan đến khám phá tri thức trong CSDL Trên quan điểm của học máy, các kỹ thuật trong Data Mining gồm: Học có giám sát: Là quá trình gán nhãn lớp cho các phần tử trong CSDL dựa trên một tập các ví dụ huấn luyện và các thông tin về nhãn lớp đã biết Học không có giám sát: Là quá trình phân chia một tập dữ liệu thành các lớp hay là cụm (clustering) dữ liệu tương tự nhau mà chưa biết trước các thông tin về lớp hay tập các ví dụ huấn luyện Học nửa giám sát: Là quá trình phân chia một tập dữ liệu thành các lớp dựa trên một tập nhỏ các ví dụ huấn luyện và một số các thông tin về một số nhãn lớp đã biết trước. Căn cứ vào lớp các bài toán cần giải quyết, khai phá dữ liệu có các kỹ thuật áp dụng sau : Phân lớp và dự đoán: xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ: phân lớp các bệnh nhân dữ liệu trong hồ sơ bệnh án. Hướng tiếp cận này thường sử dụng một số kỹ thuật của học máy như cây quyết định, mạng nơ ron nhân tạo. Phân lớp và dự đoán còn được gọi là học có giám sát. Luật kết hợp: Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong CSDL. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp tìm được. Có thể lấy một ví dụ đơn giản về luật kết hợp như sau: phân tích CSDL bán hàng nhận được thông tin về những khách hàng mua máy tính cũng có khuynh hướng mua phần mềm quản lý tài chính trong cùng lần mua được miêu tả trong luật kết hợp sau: “Mua máy tính ( Mua phần mềm quản lý tài chính” [Độ hỗ trợ: 4%, độ tin cậy: 70%]. Độ hỗ trợ và độ tin cậy là hai độ đo của sự đáng quan tâm của luật. Chúng tương ứng phản ánh sự hữu ích và sự chắc chắn của luật đã khám phá. Độ hỗ trợ 4% có nghĩa là: 4% của tất cả các tác vụ đã phân tích chỉ ra rằng máy tính và phần mềm quản lý tài chính là đã được mua cùng nhau. Còn độ tin cậy 70% có nghĩa là 70% các khách hàng mua máy tính cũng mua phân mềm quản lý tài chính. Phân tích chuỗi theo thời gian: Tượng tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao. Phân cụm: xếp các đối tượng theo từng cụm dữ liệu tự nhiên. Phân cụm còn được gọi là học không có giám sát. Mô tả khái niệm: thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản. Dạng dữ liệu có thể khai phá Do Data Mining được ứng dụng rộng rãi nên nó có thể làm việc với rất nhiều kiểu dữ liệu khác nhau. Sau đây là một số dạng dữ liệu điển hình: CSDL quan hệ, CSDL đa chiều, CSDL dạng giao dịch, CSDL quan hệ-hướng đối tượng, dữ liệu không gian và thời gian, Dữ liệu chuỗi thời gian, CSDL đa phương tiện, dữ liệu Text và Web,..,. Ứng dụng của khai phá dữ liệu Khai phá dữ liệu ứng dụng vào rất nhiều lĩnh vực. Sau đây là một số lĩnh vực khá điển hình: Kinh doanh Ngân hàng Bảo hiểm sức khỏe Y tế Khai phá luật kết hợp và ứng dụng Luật kết hợp là một biểu thức có dạng:
, trong đó
và
là tập các trường gọi là item. Ý nghĩa của các luật kết hợp khá dễ nhận thấy: Cho trước một CSDL có
là tập các giao tác - trong đó mỗi giao tác
là tập các item - khi đó
diễn đạt ý nghĩa rằng bất cứ khi nào giao tác
có chứa
thì chắc chắn
có chứa
. Độ tin cậy của luật (rule confidence) có thể được hiểu như xác suất điều kiện
. Ý tưởng của việc khai thác các luật kết hợp có nguồn gốc từ việc phân tích dữ liệu mua hàng của khách và nhận ra rằng “Một khách hàng mua mặt hàng X1 và X2 thì sẽ mua mặt hàng Y với xác suất là c%”. Ứng dụng trực tiếp của các luật này trong các bài toán kinh doanh cùng với tính dễ hiểu vốn có của chúng – ngay cả đối với những người không phải là chuyên gia khai thác dữ liệu – làm cho luật kết hợp trở thành một phương pháp khai thác phổ biến. Hơn nữa, luật kết hợp không chỉ bị giới hạn trong phân tích sự phụ thuộc lẫn nhau trong phạm vi các ứng dụng bán lẻ mà chúng còn được áp dụng thành công trong rất nhiều bài toán kinh doanh. Như vậy, khai phá luật kết hợp là một phương pháp xử lý thông tin quan trọng và phổ biến, nó nhằm khám phá m