Chương 1: Tống quan về khai phá dữ liệu và luật kết hợp. Chương 2: Một số phương pháp khai phá luật kết hợp. Chương 3: Xây dựng ứng dụng tư vấn học tập 8 CHƢƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ LUẬT KẾT HỢP 1.
Tổng quan về khai phá dữ liệu 1. Mục đích của khai phá dữ liệu Mục đích của khai phá dữ liệu là chiết xuất ra các tri thức có lợi cho kinh doanh hay cho nghiên cứu khoa học,. Dó đó, ta có thể xem mục đích của khai phá dữ liệu sẽ là mô tả các sự kiện và dự đoán. Các mẫu khai phá dữ liệu phát hiện đƣợc nhằm vào 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 đối tƣợng (bản ghi) trong CSDL để 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 đá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 bao gồm Phân lớp dữ liệu (phân loại - classification) 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”. Ví 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.
9 Phân nhóm dữ liệu (clustering) Là việc mô tả chung đế tìm ra các tập hay các nhóm, loại mô tả dữ liệu. Các nhóm có thể tách nhau hoặc phân cấp hay gối lên nhau. Có nghĩa là dữ liệu có thể vừa thuộc nhóm này lại vừa thuộc nhóm khác. 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 quang phổ từ các phƣơng pháp đo tia hồng ngoại,.
Liên quan chặt chẽ đến việc phân nhóm là nhiệm vụ đánh giá dữ liệu, hàm mật độ xác suất đa biến/ các trƣờng trong CSDL. Hồi quy (regression) 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. Nhiệm vụ của hồi quy tƣơng tự nhƣ phân lớp, điểm khác nhau chính là ở chỗ thuộc tính đế dự báo là liên tục chứ không phải rời rạc. Việc dự báo các giá trị số thƣờng đƣợc làm bởi các phƣơng pháp thống kê cổ điển, chẳng hạn nhƣ hồi quy tuyến tính.
Tuy nhiên, phƣơng pháp mô hình hoá cũng đƣợc sử dụng, ví dụ: Cây quyết định. Ứng dụng của hồi quy là rất nhiều, ví dụ: Dự đoán số lƣợng sinh vật phát quang hiện thời trong khu rừng bằng cách dò tìm vi sóng bằng các thiết bị cảm biến từ xa; ƣớc lƣợng sác xuất ngƣời bệnh có thể chết bằng cách kiểm tra các triệu chứng; dự báo nhu cầu của ngƣời dùng đối với một sản phẩm,. Tổng hợp (summarization) Là công việc liên quan đến các phƣơng pháp tìm kiếm một mô tả tập con dữ liệu. Kỹ thuật tổng hợp thƣờng áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động.
Nhiệm vụ chính là sản sinh ra các mô tả đặc trƣng cho một lớp. Mô tả loại này là một kiểu tổng hợp, tóm tắt các đặc tính chung của tất cả hay hầu hết các mục của một lớp. Các mô tả đặc trƣng thể hiện theo luật có dạng sau: “Nếu một mục thuộc về lớp đã chỉ trong tiền đề thì mục đó có tất cả các thuộc tính đã nêu trong kết luận”. Lƣu ý rằng luật dạng 10 này có các khác biệt so với luật phân lớp.
Luật phát hiện đặc trƣng cho lớp chỉ sản sinh khi các mục đã thuộc về lớp đó. Mô hình hóa phụ thuộc (dependency modeling) Là việc tìm kiếm một mô hình mô tả sự phụ thuộc giữa các biến, thuộc tính theo hai mức: Mức cấu trúc của mô hình mô tả (thƣờng dƣới dạng đồ thị). Trong đó, các biến phụ thuộc bộ phận vào các biến khác. Mức định lƣợng mô hình mô tả mức độ phụ thuộc.
Những phụ thuộc này thƣờng đƣợc biểu thị dƣới dạng theo luật “nếu - thì” (nếu tiền đề là đúng thì kết luận đúng), về nguyên tắc, cả tiền đề và kết luận đều có thể là sự kết hợp logic của các giá trị thuộc tính. Trên thực tế, tiền đề thƣờng là nhóm các giá trị thuộc tính và kết luận chỉ là một thuộc tính. Hơn nữa hệ thống có thể phát hiện các luật phân lớp trong đó tất cả các luật cần phải có cùng một thuộc tính do ngƣời dùng chỉ ra trong kết luận. Quan hệ phụ thuộc cũng có thể biểu diễn dƣới dạng mạng tin cậy Bayes.
Đó là đồ thị có hƣớng, không chu trình. Các nút biểu diễn thuộc tính và trọng số của liên kết phụ thuộc giữa các nút đó. Phát hiện sự thay đổi và độ lệch (change and deviation dectection) Nhiệm vụ này tập trung vào khám phá hầu hết sự thay đổi có nghĩa dƣới dạng độ đo đã biết trƣớc hoặc giá trị chuẩn, phát hiện độ lệch đáng kể giữa nội dung của tập con dữ liệu thực và nội dung mong đợi. Hai mô hình độ lệch hay dùng là lệch theo thời gian hay lệch theo nhóm.
Độ lệch theo thời gian là sự thay đổi có ý nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự khác nhau của giữa dữ liệu trong hai tập con dữ liệu, ở đây tính cả trƣờng hợp tập con dữ liệu này thuộc tập con kia, nghĩa là xác định dữ liệu trong một nhóm con của đối tƣợng có khác đáng kể so với toàn bộ đối tƣợng không? Theo cách này, sai sót dữ liệuhay sai lệch so với giá trị thông thƣờng đƣợc phát hiện. 11 Vì những nhiệm vụ này yêu cầu số lƣợng và các dạng thông tin rất khác nhau nên chúng thƣờng ảnh hƣởng đến việc thiết kế và chọn phƣơng pháp khai phá dữ liệu khác nhau. Ví dụ nhƣ phƣơng pháp cây quyết định tạo ra đƣợc một mô tả phân biệt đƣợc các mẫu giữa các lớp nhƣng không có tính chất và đặc điểm của lớp.2 Định nghĩa khai phá dữ liệu Khai phá dữ liệu đƣợc dùng để mô tả quá trình phát hiện ra tri thức trong CSDL.
Quá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự báo trong kinh doanh, các hoạt động sản xuất,. Khai phá dữ liệu làm giảm chi phí về thời gian so với phƣơng pháp truyền thống trƣớc kia (ví dụ nhƣ phƣơng pháp thống kê). Sau đây là một số định nghĩa mang tính mô tả của nhiều tác giả về khai phá dữ liệu: Định nghĩa của Ferruzza: “Khai phá dữ liệu là tập hợp các phƣơng pháp đƣợc dùng trong tiến trình khám phá tri thức để chỉ ra sự khác biệt các mối quan hệ và các mẫu chƣa biết bên trong dữ liệu”. Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết định, trong đó chúng ta tìm kiếm các mẫu thông tin chƣa biết và bất ngờ trong CSDL” Định nghĩa của Fayyad: “Khai phá tri thức là một quá trình không tâm thƣờng nhận ra những mẫu dữ liệu có giá trị, mới, hữu ích, tiềm năng và có thể hiểu đƣợc” 12 1.3 Quá trình khám phá tri thức nh 1.
Quá trình khám phá tri thức [1] Quá trình khám phá tri thức từ CSDL là một quá trình có sử dụng nhiều phƣơng pháp và công cụ tin học nhƣng vẫn là một quá trình mà trong đó con ngƣời là trung tâm. Do đó, nó không phải là một hệ thống phân tích tự động mà là một hệ thống bao gồm nhiều hoạt động tƣơng tác thƣờng xuyên giữa con ngƣời và CSDL, tất nhiên là với sự hỗ trợ của các công cụ tin học. Ngƣời sử dụng hệ thống ở đây phải là ngƣời có kiến thức cơ bản về lĩnh vực cần phát hiện tri thức để có thể chọn đƣợc đúng các tập con dữ liệu, các lớp mẫu phù hợp và đạt tiêu chuẩn quan tâm so với mục đích. Tri thức mà ta nói ở đây là các tri thức rút ra từ các CSDL, thƣờng để phục vụ cho việc giải quyết một loạt nhiệm vụ nhất định trong một lĩnh vực nhất định.
Do đó, quá trình pháthiện tri thức cũng mang tính chất hƣớng nhiệm vụ, không phải là phát hiện mọi tri thức bất kỳ mà là phát hiện tri thức nhằm giải quyết tốt nhiệm vụ đề ra. 13 Gom dữ liệu (Gathering) 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 CSDL, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web. Trích lọc dữ liệu (Selection) Ở giai đoạn này lựa chọn những dữ liệu phù hợp với nhiệm vụ phân tích trích rút từ CSDL.
Làm sạch, tiền xử lý và chuẩn bị trƣớc dữ liệu (Cleansing, Pre- processing and Preparation) 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ẽ, logic. 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 = -1. 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” sẽ gây nên những kết quả sai lệch nghiêm trọng. Chuyển đổi dữ liệu (Transformation) Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đƣợc chuyển đối hay đƣợc hợp nhất về dạng thích hợp cho việc khai phá. Khai phá dữ liệu (Data Mining) Đây là một tiến trình cốt yếu.
Ở giai đoạn này nhiều thuật toán khác nhau đã đƣợc sử dụng một cách phù họp để trích xuất thông tin có ích hoặc các mẫu điển hình trong dữ liệu. Đánh giá kết quả mẫu (Evaluation of Result) Đây là giai đoạn cuối trong quá trình khai phá dữ liệu.