MỞ ĐẦU 1. Với sự phát triển của máy tính và mạng internet, việc tin học hóa các lĩnh vực trong đời sống xã hội ngày càng sâu rộng, dẫn đến lưu lượng dữ liệu tạo ra gia tăng một cách nhanh chóng, con người đang sở hữu kho dữ liệu phong phú, đa dạng và khổng lồ. Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ kia thành các tri thức có ích. Mặt khác, trong môi trường cạnh tranh thì người ta ngày càng cần có thông tin với tốc độ nhanh để giúp cho việc ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả lời dựa trên khối lượng dữ liệu khổng lồ đã có.
Tiến hành các công việc như vậy chính là quá trình phát hiện tri thức trong cơ sở dữ liệu, trong đó kỹ thuật khai phá dữ liệu cho phép phát hiện tri thức tiềm ẩn ấy. Từ đó, các kỹ thuật khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền Công nghệ thông tin thế giới hiện nay nói chung và Việt Nam nói riêng. Rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của mình và thu được những lợi ích to lớn. Các kỹ thuật phát hiện tri thức và khai phá dữ liệu được thực hiện qua nhiều giai đoạn và sử dụng nhiều kỹ thuật: phân lớp (classification), phân cụm (clustering), phân tích sự tương tự (similarity analysis), tổng hợp (summarization), luật kết hợp (association rules), … Một trong những nội dung cơ bản và phổ biến trong khai phá dữ liệu là phát hiện các luật kết hợp và phân lớp dựa trên luật kết hợp.
Phương pháp này nhằm tìm ra các tập thuộc tính thường xuất hiện đồng thời trong cơ sở dữ liệu và rút ra các luật về ảnh hưởng của một tập thuộc tính dẫn đến sự xuất hiện của một hoặc nhiều tập thuộc tính khác như thế nào? Do đó việc phát hiện ra các luật kết hợp là một bước rất quan trọng trong khai phá dữ liệu. Giáo dục là một lĩnh vực quan trọng của đời sống xã hội được người người quan tâm, nhà nhà quan tâm, việc đáp ứng nhu cầu học tập của người dân khi dân số càng tăng nhanh là một thử thách đối với cơ quan chức năng. Việc có thể dự báo với những số liệu chính xác cao là một thông tin vô cùng quý giá để cấp có thẩm quyền căn cứ xxiii vào đó ban hành những quyết sách đúng đắn phù hợp thực tế, chuẩn bị tốt cho một năm học đầy hứa hẹn, câu chuyện về thiếu trường lớp, tệ nạn học đường đang làm các nhà quản lý giáo dục và xã hội phải tốn rất nhiều thời gian, công sức, tài chính để xử lý. Một trong những tồn tại đó là số lượng học sinh nghỉ bỏ học và xa vào tệ nạn xã hội do nhiều nguyên nhân, nếu vấn đề này không được quan tâm giải quyết số lượng học sinh này sẽ gây nhiều hệ lụy khó lường cho an ninh và phát triển xã hội vì thế hệ kế cận là tương lại của đất nước.
Vậy cần có một giải pháp cho vấn đề này là dự báo số lượng học sinh nghỉ bỏ hàng năm phục vụ cho công tác quản lý giáo dục tại các trường học ngăn ngừa tình trạng các em bỏ học giữa chừng và chuẩn bị các trung tâm dạy nghề, cai nghiện, phục hồi chức năng … để các em có cơ hội tiếp tục học tập thành những công dân có ích, thành người dân lương thiện. Mục đích yêu cầu, đối tượng, phạm vi nghiên cứu. Mục đích yêu cầu: Tìm hiểu bài toán khai phá luật kết hợp. Tìm hiểu bài toán phân lớp dựa trên luật kết hợp dự báo.
Tìm hiểu bài toán dự báo tình hình nghỉ bỏ học của học sinh và cài đặt giải thuật CPAR-GR phân tích số liệu để đưa ra dự báo số lượng học sinh có nguy cơ bỏ học tại các cơ sở giáo dục trung học. Đối tượng nghiên cứu Luật kết hợp, Phân lớp kết hợp Một số giải thuật phân lớp dựa trên luật kết hợp. Dữ liệu nghỉ bỏ học của học sinh trung học. Phạm vi nghiên cứu: Nghiên cứu giải thuật phân lớp dựa trên luật kết hợp dự báo.
Nhiệm vụ và phương pháp. Tìm hiểu về giải thuật phân lớp kết hợp. Tìm hiểu giải thuật phân lớp dựa trên luật kết hợp dự báo. Tìm hiểu giải thuật cải tiến của giải thuật phân lớp dựa trên luật kết hợp dự báo.
xxiv Sử dụng luật phân lớp kết hợp để phân tích dữ liệu học sinh đưa ra kết luận về tình trạng học sinh nghỉ bỏ học. Kết quả đạt được. Trình bày khái quát các khái niệm liên quan đến luật kết hợp, phân lớp kết hợp từ đó có cơ sở nghiên cứu phân lớp dựa trên luật kết hợp dự báo. Tìm hiểu các thuật toán sử dụng luật kết hợp để phân lớp như FOIL, PRM, CPAR, CPAR-GR (một cải tiến của CPAR).
Có sự đối chiếu, so sánh về hiệu suất, độ chính xác thông qua thực nghiệm để đưa ra nhận xét kết luận về ưu điểm của các cải tiến trong giải thuật ra đời sau. Cài đặt giải thuật CPAR-GR, xây dựng thành ứng dụng dự báo tình hình nghỉ bỏ học của học sinh dựa vào số liệu thu thập từ các trường trung học. Tiến hành thực nghiệm với số liệu của 6 cơ sở dữ liệu để đối chiếu kết quả. xxv Chương 1.
TỔNG QUAN VỀ PHÂN LỚP DỰA TRÊN LUẬT KẾT HỢP. Giới thiệu luật kết hợp và một số khái niệm cơ bản. Giới thiệu luật kết hợp. 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 trong các siêu thị.
Swami đã lần đầu tiên đề xuất mô hình khai phá luật kết hợp nhị phân (hay còn gọi là mô hình cơ bản). Với mô hình này việc xác định các quan hệ chỉ dựa vào sự xuất hiện cùng lúc của mục dữ liệu mà 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 đó. Phát biểu bài toán: Cho cơ sở dữ liệu giao tác D, với ngưỡng độ phổ biến tối thiểu minsup và ngưỡng độ tin cậy tối thiểu minconf. Yêu cầu tìm tất cả các luật kết hợp X→Y trên cơ sở dữ liệu D sao cho sup(X→Y) > minsup và conf (X→Y) > minconf.
[1] Các bước cơ bản để tìm luật kết hợp từ cơ sở dữ liệu D: Tìm tất cả các tập mục phổ biến (Mining frequent itemsets) từ cơ sở dữ liệu D với ngưỡng phổ biến tối thiểu minsup. Bước này thường có độ phức tạp tính toán cao và chiếm phần lớn thời gian của giải thuật khai phá luật kết hợp. Ví dụ: với I = {i1, i2, i3, …, i100} số tập con sẽ có là 2100 -1 1. Tạo tất cả các luật mạnh (Generating strong rules) từ các tập mục phổ biến được tìm ra ở bước trước với ngưỡng độ tin cậy tối thiểu minconf.
1 Dữ liệu thô Mối quan hệ giữa Các tập mục Người + Giao tác. dùng + Dữ liệu quan hệ + Luật Tiền xử lý Khai phá Giao tác loại hàng 1001 L1, L2, L3 Cấu hình luật: L1, L2, L3, 3156 L1, L3 Antecedent→Consequent[support, confidence] L4, L5 L1 L3 [50%, 67,6%] 1014 L1, L4 … 5782 L2, L4, L5 … Hình 1.1 Mô hình giải bài toán tạo luật kết hợp 1. Một số khái niệm cơ bản. Phần tử (Item) là một giá trị trong tập hợp các mẫu, đối tượng đang được xem xét trong quản lý thực tế được ký hiệu I = i1, i2, i3, …, in, trong đó mỗi giá trị ik được coi là một mục hay một phần tử.
[1] Ví dụ: - Danh mục hàng hóa trong siêu thị I = thịt, cá, trứng sữa, quần, áo, giày, dép, … - Danh mục thuốc bán tại Nhà thuốc I = {Oral liquid, cyclizine, dexamethasone, diazepam, docusate sodium, fluoxetine, hyoscine butylbromide, … Tập phần tử. Tập phần tử (Itemset) là tập hợp con của tập hợp tất cả các phần tử trong cơ sở dữ liệu đang xét, ký hiệu là X I còn được gọi với tên khác là tập mục. Nếu trong tập X có k mục (|X| = k) thì X được gọi là k-itemset. [1] Ví dụ: Ta có tập mục I = {A, B, C, D, E, F} Cơ sở dữ liệu giao dịch D = {T1, T2, T3, T4, T5, T6} Trong đó: T1 = {A, B, D, E} T2 = {A, E, F} 2 T3 = {B, D, E} T4 = {A, E} T5 = {A, C, D, E, F} T6 = {B, C, E} Transaction ID List of Item_IDs T100 I1, I2, I5 T200 I2, I4 T300 I2, I3 T400 I1, I2, I4 T500 I1, I3 T600 I2, I3 T700 I1, I3 T800 I1, I2, I3, I5 T900 I1, I2, I3 Hình 1.2 Minh họa định nghĩa Item, Itemset, Transaction Tập mục phổ biến.
Độ phổ biến của một tập mục (Support) trong cơ sở dữ liệu giao tác được định nghĩa như sau: Định nghĩa 1: Độ phổ biến của một tập mục X trong cơ sở dữ liệu D là tỷ số giữa các bản ghi T D có chứa tập X với tổng số giao tác trong D. [1] |{T | T D và X T }| Supp(X) = |D| Ta có: 0 ≤ Supp(X) ≤ 1 với mọi tập mục X. Tập mục X được gọi là tập mục phổ biến (frequent itemset) trong D nếu Supp(X) lớn hơn hoặc bằng ngưỡng độ phổ biến tối thiểu do người dùng đặt ra. Ví dụ: Có cơ sở dữ liệu D gồm các giao tác: T1 = {thịt, sữa, bánh mỳ, gạo, bơ} T2 = {sữa, quần, bia} 3 T3 = {sữa, bánh mỳ, bơ} T4 = {thịt, trứng} T5 = {thịt, bánh mỳ, khoai tây, cá, giày} Tập mục X {sữa, bánh mỳ, bơ} có độ phổ biến là 2/5 = 0.4 hay 40% số giao tác có trong cơ sở dữ liệu D.
Luật kết hợp. * Trong cơ sở dữ liệu giao tác luật kết hợp được định nghĩa như sau: Định nghĩa 1: Cho tập I = {i1, i2, … ,in} là tập n thuộc tính nhị phân gọi là các phần tử (item). Cho D = {T1, T2, … ,Tm} là tập các giao tác gọi là cơ sở dữ liệu. Mỗi giao tác trong D có một mã định danh duy nhất và chứa các tập mục trong I.
Một mối quan hệ giữa 2 tập mục X và Y có dạng X Y, trong đó X, Y I và X Y = được gọi là luật kết hợp.