Nội dung

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG PHAN VĂN DƢƠNG KHAI PHÁ DỮ LIỆU VÀ ỨNG DỤNG TRONG TƢ VẤN TUYỂN SINH TRƢỜNG CAO ĐẲNG NGHỀ TRUNG BỘ Chuyên ngành : Khoa học máy tính Mã số : 60.48.01 TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng - Năm 2012 Công trình được hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: PGS.TSKH. TRẦN QUỐC CHIẾN Phản biện 1 : TS. NGUYỄN THANH BÌNH Phản biện 2 : TS. LÊ XUÂN VINH Luận văn được bảo vệ tại Hội đồng chấm Luận văn tốt nghiệp thạc sĩ kỹ thuật họp tại Đại học Đà Nẵng vào ngày 19 tháng 01 năm 2013 Có thể tìm hiểu luận văn tại: - Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng; - Trung tâm Học liệu, Đại học Đà Nẵng; 1 MỞ ĐẦU 1. LÝ DO CHỌN ĐỀ TÀI Trong vài thập niên gần đây, cùng với sự thay đổi và phát triển không ngừng của ngành công nghệ thông tin, luồng thông tin được chuyển tải mau lẹ đến chóng mặt, ước tính cứ khoảng 20 tháng lượng thông tin trên thế giới lại tăng gấp đôi. Với sự việc đó dẫn đến sự bùng nổ thông tin, làm cho các nhà quản lý rơi vào tình trạng “ngập luật thông tin”. Chính vì vậy, các chuyên gia cho rằng, hiện nay chúng ta đang sống trong một xã hội “rất giàu về thông tin nhưng nghèo về tri thức”. Những người ra quyết định trong các tổ chức tài chính, thương mại, khoa học…không muốn bỏ sót bất cứ thông tin nào, họ thu thập, lưu trữ tất cả mọi thông tin vì cho rằng trong nó ẩn chứa những giá trị nhất định nào đó. Trước tình hình đó, giải pháp hiệu quả giúp phân tích khối lượng lớn dữ liệu đó là khai phá dữ liệu. Với kỹ thuật khai phá dữ liệu, tác giả muốn nghiên cứu ứng dụng trong phân tích số liệu tuyển sinh để phát hiện những tri thức về công tác tư vấn tuyển sinh. Hiện nay, lĩnh vực giáo dục đang phát triển mạnh mẽ, hệ thống trường lớp đang ngày được mở rộng, khả năng cạnh tranh thu hút Học sinh - Sinh viên (HSSV) giữa các trường ngày một quyết liệt hơn. Vì vậy, công tác tuyển sinh là một trong những vấn đề quan tâm hàng đầu của các cơ quan giáo dục, đã có rất nhiều chương trình tư vấn tuyển sinh rộng khắp trên tất cả các tỉnh, thành trong cả nước với nhiều hình thức phong phú. Tuy nhiên, thực tế thí sinh còn cảm thấy thiếu thông tin về các trường, các ngành nghề mà mình quan tâm. Với mục đích trên, luận văn đi vào tìm hiểu khai phá dữ liệu và xây dựng hệ thống hỗ trợ tư vấn tuyển sinh cho Trường Cao đẳng nghề Cơ điện – Xây dựng & Nông lâm Trung bộ. 2 2. MỤC ĐÍCH NGHIÊN CỨU Mục đích của đề tài là tìm hiểu các kỹ thuật khai phá dữ liệu, ứng dụng các kỹ thuật khai phá dữ liệu trong phân tích số liệu tuyển sinh, nhằm phát hiện ra các đặc điểm chung của HSSV trong việc lựa chọn Trường - Ngành Nghề học tập, hỗ trợ Ban Tuyển Sinh có những nhận định và đề ra những biện pháp phù hợp. 3. ĐỐI TƢỢNG VÀ PHẠM VI NGHIÊN CỨU - Các kỹ thuật khai phá dữ liệu. - Một số chương trình, mã nguồn mở ứng dụng khai phá dữ liệu. - Áp dụng các thuật toán khai phá dữ liệu trên cơ sở dữ liệu lưu trữ. (Hoạt động nghiên cứu được khảo sát trong lĩnh vực công tác tư vấn tuyển sinh). 4. PHƢƠNG PHÁP NGHIÊN CỨU - Phương pháp nghiên cứu lý thuyết: Tìm hiểu và lựa chọn phương pháp khai phá dữ liệu thích hợp. - Thu thập thống kê số liệu từ nguồn dữ liệu công tác tuyển sinh. - Phương pháp nghiên cứu thực nghiệm: Phân tích thiết kế hệ thống, triển khai xây dựng ứng dụng. 5. Ý NGHĨA ĐỀ TÀI Ý nghĩa khoa học: - Cung cấp một cách nhìn tổng quan về phát hiện tri thức và khai phá dữ liệu. - Áp dụng các thuật toán khai phá dữ liệu trên cơ sở dữ liệu tuyển sinh. (Dữ liệu thu thập từ Trường Cao Đẳng Nghề Cơ Điện – Xây Dựng & Nông Lâm Trung Bộ) - Phát hiện ra các đặc điểm chung của HSSV hỗ trợ Ban Tuyển Sinh có những nhận định cụ thể và đề ra các giải pháp hữu hiệu. 3 Ý nghĩa thực tiễn: - Chương trình được sử dụng cho Ban Tuyển Sinh nhằm phát huy hiệu quả công tác tuyển sinh, hỗ trợ cho HSSV trong việc lựa chọn Trường - Ngành Nghề học tập. - Chương trình là một giải pháp tin học hóa trong công tác tuyển sinh. Giải pháp giúp tạo lập một thống thông tin tích hợp, phục vụ hiệu quả công tác tuyển sinh. 6. CẤU TRÚC LUẬN VĂN Báo cáo của luận văn được tổ chức thành 3 chương CHƢƠNG 1 TỔNG QUAN KHO DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU 1.1 TỔNG QUAN VỀ KHO DỮ LIỆU 1.1.1 Định nghĩa kho dữ liệu Kho dữ liệu là tuyển tập các cơ sở dữ liệu tích hợp, hướng chủ đề, được thiết kế để hỗ trợ cho chức năng trợ giúp quyết định. 1.1.2 Mục đích kho dữ liệu - Đáp ứng mọi yêu cầu về thông tin của người sử dụng. - Hỗ trợ để các nhân viên của các tổ chức thực hiện hiệu quả công việc của mình. - Giúp các tổ chức, xác định, quản lý, điều hành một cách hiệu quả và chính xác. - Tích hợp dữ liệu và các siêu dữ liệu từ nhiều nguồn dữ liệu. Muốn đạt được những yêu cầu trên thì DW phải đảm bảo các mục tiêu: Truy cập dễ dàng, thông tin nhất quán, thích nghi với sự thay đổi, hỗ trợ ra quyết định, bảo mật. 1.1.3 Các đặc tính của kho dữ liệu 4 a. Hướng chủ đề b. Tính tích hợp c. Tính bền vững d.Gắn với thời gian và có tính lịch sử e. Dữ liệu tổng hợp 1.1.4 Kiến trúc của kho dữ liệu Mô hình kiến trúc kho dữ liệu gồm 3 thành phần: Dữ liệu nguồn, khu vực xử lý và kho dữ liệu. Hình 1.1 Kiến trúc kho dữ liệu 1.1.5 Các cách thức khai thác kho dữ liệu - Theo cách khai thác truyền thống hỏi đáp và báo cáo. - Dùng để hỗ trợ cho xử lý phân tích trực tuyến. - Khai phá dữ liệu. 1.2 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.2.1 Tại sao cần phát hiện tri thức Ngày nay, sự phát triển của Công nghệ thông tin (CNTT) và ngành công nghiệp phần cứng đã làm lưu lượng thông tin tăng rất nhanh. 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. 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 CNTT thế giới hiện nay. 5 1.2.2 Khám phá tri thức và khai phá dữ liệu Khám phá tri thức từ cơ sở dữ liệu được định nghĩa như là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các Cơ sở dữ liệu (CSDL), kho dữ liệu. Khai phá dữ liệu (DM) 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 kho dữ liệu. Về bản chất, DM 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 tri thức trong tập dữ liệu. 1.2.3 Kiến trúc của hệ thống khai phá dữ liệu Giao diện người dùng Đánh giá mẫu Mô tơ khai phá dữ liệu (Data Mining Engine) Cơ sở tri thức CSDL hay kho dữ liệu phục vụ Làm sạch, tích hợp, lọc dữ liệu CSDL, Kho dữ liệu, WWW, Nguồn lƣu trữ khác Hình 1.5. Kiến trúc của hệ thống khai phá dữ liệu 1.2.4 Quá trình khai phá dữ liệu Quy trình khai phá dữ liệu là một chuỗi lập và tương tác gồm các bước bắt đầu với dữ liệu thô và kết thúc với tri thức. Quá trình khai phá dữ liệu được thể hiện bởi mô hình sau: 6 Thống kê và tóm tắt Tiền xử lý dữ liệu Giải thuật khai phá dữ liệu Dữ liệu trực tiếp Thu thập, trích lọc dữ liệu liên quan Mẫu Xác định nhiệm vụ Hình 1.6 Quá trình khai phá dữ liệu 1.2.5 Các kỹ thuật khai phá dữ liệu Trong thực tế có nhiều kỹ thuật khai phá dữ liệu khác nhau và được chia thành hai nhóm chính: kỹ thuật khai phá dữ liệu mô tả, kỹ thuật khai phá dữ liệu dự đoán. Một số kỹ thuật phổ biến thường được sử dụng để khai phá dữ liệu hiện nay là: phân cụm dữ liệu, khai phá luật kết hợp, hồi quy, Phân lớp dữ liệu, giải thuật di truyền, mạng nơron. 1.2.6 Lợi thế của khai phá dữ liệu so với các phƣơng pháp khác - So với phương pháp học máy, khai phá dữ liệu có lợi thế hơn ở chỗ nó có thể sử dụng các CSDL chứa nhiễu, dữ liệu không đầy đủ hoặc biến dổi liên tục. - Phương pháp hệ chuyên gia, các ví dụ của chuyên gia thường ở mức chất lượng cao hơn nhiều so với dữ liệu trong CSDL và chúng chỉ bao hàm các trường hợp quan trọng, đòi hỏi phải có sự tham gia của các chuyên gia trong việc phát hiện tri thức. - Phương pháp thống kê, có thể thấy phương pháp thống kê còn có một số điểm yếu mà khai phá dữ liệu đã khắc phục được: không phù hợp với các kiểu dữ liệu có cấu trúc trong rất nhiều các CSDL, 7 không sử dụng tri thức sẵn có về lĩnh vực, cần có sự hướng dẫn của người dùng để xác định phân tích dữ liệu như thế nào và ở đâu. 1.2.7 Các dạng dữ liệu có thể khai phá Khai phá dữ liệu có khả năng chấp nhận một số kiểu dữ liệu khác nhau điển hình như sau: Cơ sở dữ liệu quan hệ, cơ sở dữ liệu giao tác, cơ sở dữ liệu đa phương tiên… 1.2.8 Những thách thức trong khai phá dữ liệu a. Các vấn đề về cơ sở dữ liệu b. Các vấn đề khác 1.3 MỐI QUAN HỆ GIỮA KHO DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU Kho dữ liệu và khai phá dữ liệu có thể đứng độc lập với nhau, tuy nhiên khi kết hợp được kho dữ liệu với khai phá dữ liệu thì chúng hỗ trợ, phục vụ cho nhau. Dữ liệu trong kho dữ liệu đã làm sạch, tích hợp, tổ chức có cấu trúc, phù hợp cho việc khai phá dữ liệu, cơ sở hạ tấng của kho dữ liệu hỗ trợ rất tốt cho việc khai phá dữ liệu. 1.4 TỔNG KẾT CHƢƠNG 1 Trong nội dung chương này, tôi đã trình bày tổng quan các vấn đề về kho dữ liệu và khai phá dữ liệu. Phần tiếp theo của luận văn này, tôi xin trình bày cơ sở lý thuyết về khai phá dữ liệu dùng luật kết hợp và phân lớp với cây quyết định. Từ đó, xây dựng hệ thống dự đoán dựa trên khai phá dữ liệu bằng cây quyết định. CHƢƠNG 2. KHAI PHÁ DỮ LIỆU BẰNG LUẬT KẾT HỢP VÀ PHÂN LỚP VỚI CÂY QUYẾT ĐỊNH 2.1. KHAI PHÁ DỮ LIỆU BẰNG LUẬT KẾT HỢP 2.1.1. Các khái niệm cơ bản Định nghĩa 2.1: Hạng mục (Item) 8 Là một thuộc tính nào đó i k của đối tượng đang xét trong cơ sở dữ liệu. ( ik : k 1...m , với m là số thuộc tính của đối tượng). Định nghĩa 2.2: Tập các hạng mục (Itemset) I i1 , i2 ,...,im Là tập hợp các thuộc tính của đối tượng đang xét trong cơ sở dữ liệu. Định nghĩa 2.3: Giao dịch (transaction) Là tập các hạng mục trong cùng một đơn vị tương tác, mỗi giao dịch được xử lý một cách nhất quán mà không phụ thuộc vào các giao dịch khác. Định nghĩa 2.4: Cơ sở dữ liệu giao dịch D Là tập các giao dịch mà mỗi giao dịch được đánh nhãn với một định D danh duy nhất T1 ,T2 ,...,Tn ,Ti (cơ sở dữ liệu giao dịch I ). Định nghĩa 2.5: Độ hỗ trợ (Supp) Độ hỗ trợ (Supp) của tập các hạng mục X trong cơ sở dữ liệu giao dịch D là tỷ lệ giữa số các giao dịch chứa X trên tổng số giao dịch trong D. Supp X {T DX | D| T} (2.1) Định nghĩa 2.6: Tập phổ biến: Là tập các hạng mục có độ hỗ trợ thoả mãn độ hỗ trợ tối thiểu (minsupp - là một giá trị do người dùng xác định trước). Nếu tập mục X có thì ta nói X là một tập các mục phổ biến. Tập phổ biến tối đại là tập phổ biến và không tồn tại tập nào bao nó. Tập phổ biến đóng là tập phổ biến và không tồn tại tập nào bao nó có cùng độ hỗ trợ như nó. Định nghĩa 2.7: Luật kết hợp