phần Mở đầu, Mục lục, Danh mục hình, Kết luận, Tài liệu tham khảo. Luận văn chia là 3 phần : Phần 1 : Tổng quan về khám phá tri thức và khai phá dữ liệu Phần này giới thiệu một cách tổng quát về quá trình khám phá tri thức nói chung và khai phá dữ liệu nói riêng. Các phương pháp, lãnh vực và các hướng tiếp cận trong khai phá dữ liệu. Phần 2 : Phân cụm dữ liệu và một số thuật toán trong phân cụm dữ liệu -7- Trong phần này trình bày khái niệm và mục tiêu của phân cụm dữ liệu, các yêu cầu, các cách tiếp cận cũng như các thách thức mà phân cụm dữ liệu đang gặp phải.
Một số phương pháp phân cụm dữ liệu như: phân cụm không phân cấp, phân cụm phân cấp, phân cụm dựa trên mật độ, phân cụm dữ liệu dựa vào lưới, phân cụm dựa trên mô hình … trong mỗi phương pháp trình bày một số thuật toán đại diện. Phần 3 : Ứng dụng phân cụm dữ liệu trong việc phân tích, đánh giá kết quả học tập của học sinh Phần này trình bày lý do chọn bài toán, các cơ sở để giải quyết bài toán (lý luận, thực tiễn, khoa học …). Cài đặt chương trình thử nghiệm ứng dụng kỹ thuật phân cụm trong lãnh vực giáo dục và một số kết quả thu được. Tổng quan về khám phá tri thức và khai phá dữ liệu 1.
Giới thiệu chung về khám phá tri thức và khai phá dữ liệu Trong những năm gần đây, sự phát triển mạnh mẽ của công nghệ thông tin và ngành công nghiệp phần cứng đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng nhanh một cách chóng mặt. Bên cạnh đó việc tin học hoá một cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng như nhiều lãnh vực hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu lưu trữ khổng lồ. Hàng triệu cơ sở dữ liệu đã được sử dụng trong các hoạt động sản xuất, kinh doanh, quản lí., trong đó có nhiều cơ sở dữ liệu cực lớn cỡ Gigabyte, thậm chí là Terabyte. 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 ngành công nghệ thông tin thế giới hiện nay. Thông thường, chúng ta coi dữ liệu như là một chuỗi các bits, hoặc các số và các ký hiệu hay là các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một chương trình dưới một dạng nhất định. Các bits thường được sử dụng để đo thông tin, và xem nó như là dữ liệu đã được loại bỏ phần tử thừa, lặp lại, và rút gọn tới mức tối thiểu để đặc trưng một cách cơ bản cho dữ liệu. Tri thức được xem như là các thông tin tích hợp, bao gồm các sự kiện và mối quan hệ giữa chúng, đã được nhận thức, khám phá, hoặc nghiên cứu.
Nói cách khác, tri thức có thể được coi là dữ liệu ở mức độ cao của sự trừu tượng và tổng quát. Khám phá tri thức hay phát hiện tri thức trong cơ sở dữ liệu là một quy trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng hợp, hợp thức, khả ích và có thể hiểu được. -9- Khai phá dữ liệu là một bước trong quá trình khám phá tri thức, gồm các thuật toán khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu. Nói cách khác, mục tiêu của khai phá dữ liệu là tìm kiếm các mẫu hoặc mô hình tồn tại trong cơ sở dữ liệu nhưng ẩn trong khối lượng lớn dữ liệu.
Quá trình khám phá tri thức Quá trình khám phá tri thức tiến hành qua 6 giai đoạn như hình [7]: Hình 1.1 : Quá trình khám phá tri thức Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. Về lý thuyết thì có vẻ rất đơn giản nhưng thực sự đây là một quá trình rất khó khăn gặp phải rất nhiều vướng mắc như : quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình, v. Gom dữ liệu: Tập hợp dữ liệu là bước đầu tiên trong quá trình khai phá dữ liệu. Đây là bước được khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng -10- dụng Web.
Trích lọc dữ liệu: Ở giai đọan này dữ liệu được lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đó phục vụ mục đích khai thác, ví dụ chọn tất cả những em học sinh có điểm Trung bình học kỳ lớn hơn 8.0 và có giới tính nữ. Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu: Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thường mắc phải trong khi gom dữ liệu là tính không đủ chặt chẽ, logíc. Vì vậy, dữ liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu.
Ví dụ : Điểm Trung bình = 12. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẻ nói trên. Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không được “làm sạch – tiền xử lý – chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch nghiêm trọng.
Chuyển đổi dữ liệu: Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đưa ra có thể sử dụng và điều khiển được bởi việc tổ chức lại nó, tức là dữ liệu sẽ được chuyển đổi về dạng phù hợp cho việc khai phá bằng cách thực hiện các thao tác nhóm hoặc tập hợp. Khai phá dữ liệu: Đây là bước mang tính tư duy trong khai phá dữ liệu. Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để trích ra các mẫu từ dữ liệu. Thuật toán thường dùng là nguyên tắc phân loại, nguyên tắc kết, v.
Đánh giá các luật và biểu diễn tri thức: Ở giai đoạn này, các mẫu dữ liệu được chiết xuất ra bởi phần mềm khai phá dữ liệu. Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức (Knowlege) cần chiết xuất ra. Đánh giá sự hữu ích của các mẫu biểu diễn tri thức dựa trên một số phép -11- đo.
Sau đó sử dụng các kỹ thuật trình diễn và trực quan hoá dữ liệu để biểu diễn tri thức khai phá được cho người sử dụng. Trên đây là 6 giai đoạn của quá trình khám phá tri thức, trong đó giai đoạn 5 - khai phá dữ liệu (hay còn gọi đó là Data Mining) là giai đoạn được quan tâm nhiều nhất. Quá trình khai phá dữ liệu Khai phá dữ liệu là một giai đoạn quan trọng trong quá trình khám phá tri thức. Về bản chất là giai đoạn duy nhất tìm ra được thông tin mới, thông tin tiềm ẩn có trong cơ sở dữ liệu chủ yếu phục vụ cho mô tả và dự đoán.
Mô tả dữ liệu là tổng kết hoặc diễn tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu mà con người có thể hiểu được. Dự đoán là dựa trên những dữ liệu hiện thời để dự đoán những quy luật được phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu trên cơ sở đó chiết xuất ra các mẫu, dự đoán được những giá trị chưa biết hoặc những giá trị tương lai của các biến quan tâm. Quá trình khai phá dữ liệu bao gồm các bước chính được thể hiện : Hình 1.2 : Quá trình khai phá dữ liệu - Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết. - Xác định các dữ liệu liên quan: Dùng để xây dựng giải pháp.
-12- - Thu thập và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và tiền xử lý chúng sao cho thuật toán khai phá dữ liệu có thể hiểu được. Đây là một quá trình rất khó khăn, có thể gặp phải rất nhiều các vướng mắc như: dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp), quản lý tập các dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi), v. - Thuật toán khai phá dữ liệu: Lựa chọn thuật toán khai phá dữ liệu và thực hiện việc khai phá dữ liệu để tìm được các mẫu có ý nghĩa, các mẫu này được biểu diễn dưới dạng luật kết hợp, cây quyết định. tương ứng với ý nghĩa của nó.
Các phương pháp khai phá dữ liệu Với hai mục đích khai phá dữ liệu là Mô tả và Dự đoán, người ta thường sử dụng các phương pháp sau cho khai phá dữ liệu [3]: - Luật kết hợp (association rules) - Phân lớp (Classfication) - Hồi qui (Regression) - Trực quan hóa (Visualiztion) - Phân cụm (Clustering) - Tổng hợp (Summarization) - Mô hình ràng buộc (Dependency modeling) - Biểu diễn mô hình (Model Evaluation) - Phân tích sự phát triển và độ lệch (Evolution and deviation analyst) - Phương pháp tìm kiếm (Search Method) -13- Có nhiều phương pháp khai phá dữ liệu được nghiên cứu ở trên, trong đó có ba phương pháp được các nhà nghiên cứu sử dụng nhiều nhất đó là : Luật kết hợp, Phân lớp dữ liệu và Phân cụm dữ liệu. Các lĩnh vực ứng dụng thực tiễn của khai phá dữ liệu Khai phá dữ liệu là một lĩnh vực mới phát triển những thu hút đựợc khá nhiều nhà nghiên cứu nhờ vào những ứng dụng thực tiễn của nó. Sau đây là một số lĩnh vực ứng dụng thực tế điển hình của khai phá dữ liệu : - Phân tích dữ liệu và hỗ trợ ra quyết định - Phân lớp văn bản, tóm tắt văn bản, phân lớp các trang Web và phân cụm ảnh màu - Chuẩn đoán triệu chứng, phương pháp trong điều trị y học - Tìm kiếm, đối sánh các hệ Gene và thông tin di truyền trong sinh học - Phân tích tình hình tài chính, thị trường, dự báo gía cổ phiếu trong tài chính, thị trường và chứng khoán - Phân tích dữ liệu marketing, khách hàng. - Điều khiển và lập lịch trình - Bảo hiểm - Giáo dục.