CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU, KHAI PHÁ QUAN ĐIỂM 1.1 Khai phá dữ liệu Công nghệ thông tin ngày càng phát triển thì các hệ thống thông tin ngày càng mở rộng để lưu trữ một lượng lớn các dữ liệu đã có và đang tích tụ thêm, thêm vào đó là việc lưu trữ dữ liệu trực tuyến với dung lượng lớn nhiều khi đã làm cho ta choáng ngợp và không biết làm thế nào để có những thông tin hữu ích đang cần. Quá trình lấy ra được những dữ liệu hữu ích được gọi quá trình khai phá tri thức. Những dữ liệu đó là các tri thức học được. Có nhiều khái niệm về khai phá dữ liệu, trong đó có khái niệm sau đây dễ nhớ, dễ hiểu: “Khai phá tri thức là tìm ra tri thức trong dữ liệu”.
[E1] Quá trình khai phá tri thức: Hình 1: Quá trình khai phá dữ tri thức LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Quá trình khai thác tri thức không chỉ là một quá trình tuần tự từ bước đầu tiên đến bước cuối cùng mà là một quá trình lặp và có quay trở lại các bước đã qua, chi tiết 7 bước: 1) Làm sạch dữ liệu (Data Cleaning): Dữ liệu được thu thập từ các nguồn được xử lý bỏ dữ liệu nhiễu và không phù hợp. 2) Tích hợp dữ liệu (Data Integration): Dữ liệu có thể được kết hợp từ nhiều nguồn khác nhau, sau khi làm sạch và tiền xử lý được hợp nhất thành những kho dữ liệu (data warehouses). 3) Trích chọn dữ liệu (Data Selection): Lựa chọn ra những dữ liệu liên quan đến nhiệm vụ phân tích từ kho dữ liệu. 4) Chuyển đổi dữ liệu (Data Transformation): Dữ liệu được chuyển đổi sang dạng phù hợp và thống nhất cho quá trình xử lý.
5) Khai phá dữ liệu (Data mining): Là một bước quan trọng, trong đó các phương pháp thông minh được áp dụng để lấy ra được dữ liệu mới làm cơ sở cho tri thức. 6) Đánh giá mẫu (Pattern Evaluation): Dùng các biện pháp là các thước đo để đánh giá kết quả tìm được. 7) Trình diễn dữ liệu (Data Presentation): Biểu diễn và thể hiện trực quan dữ liệu đã khai phá cho người dùng. Như vậy, khai phá dữ liệu là một phần không thể thiếu trong khai phá tri thức.
Từ bước 1 đến bước 4 là quá trình tiền xử lý dữ liệu chuẩn bị cho quá trình khai phá, đến bước 5 khai phá dữ liệu có thể tương tác với người dùng hoặc lưu trữ như kiến thức mới trong cơ sở tri thức. Do vậy khai phá dữ liệu là một phần trong khai phá tri thức song thuật ngữ này hay được dùng để tham khảo cho toàn bộ quá trình khai phá tri thức. Khai phá dữ liệu được định nghĩa: là quá trìnhkhám phá các mẫu và tri thức mới từ kho dữ liệu khổng lồ. [E1] LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Các phương pháp khai phá dữ liệu Hiện nay chưa có một tiêu chuẩn nào trong việc quyết định sử dụng phương pháp khai phá dữ liệu nào vào trường hợp nào thì có hiệu quả nhất.
Có rất nhiều kỹ thuật, mỗi kỹ thuật được sử dụng cho nhiều bài toán khác nhau. Do vậy, nếu căn cứ vào bài toán cần giải quyết thì khai phá dữ liệu được chia ra các phương pháp sau: * Phân lớp (classification) và dự đoán (prediction): Với một tập dữ liệu huấn luyện có trước các giải thuật và công cụ sẽ xếp các đối tượng và một trong các lớp đã biết trước. Bài toán dự đoán tương đương với bài toán phân lớp, khi có đối tượng mới bộ dự đoán dựa trên thông tin đang có để đưa ra giá trị số học cho hàm cần dự đoán. * Phân cụm (clutering): Phân các đối tượng theo từng cụm, đối tượng và tên cụm chưa được biết trước nên gọi phân cụm là học không giám sát.
* Tổng hợp (summarization): Công việc liên quan đến các phương pháp tìm kiếm mô tả tập con dữ liệu, đó chính là sinh ra các mô tả đặc trưng cho một lớp. * Qui hồi (regression): Là bài toán 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. Bài toán qui hồi có nhiệm vụ tương tự bài toán phân lớp song các thuộc tính dự báo trong bài toán này là liên tục chứ không rời rạc. * Mô hình ràng buộc (dependency modeling): 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ả sự phụ thuộc bộ phận của các biến phụ vào các biến khác, thường biểu diễn dưới dạng đồ thị.
- Mức định lượng mô hình mô tả mức độ phụ thuộc, thường biểu diễn dưới dạng luật “nếu - thì”. * Dò tìm biến đổi và độ lệch (change and deviation dectection): LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 Xác định 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. Thường dùng 2 mô hình đo độ lệch: - Lệch theo thời gian: thay đổi có ý nghĩa của dữ liệu theo thời gian. - Lệch theo nhóm: sự khác nhau giữa hai tập con dữ liệu, 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, qua đó phát hiện những sai sót dữ liệu và sai lệch so với giá trị thông thường.3 Các kỹ thuật khai phá dữ liệu Học máy nghiên cứu và xây dựng các kĩ thuật cho phép các hệ thống "học" tự động từ dữ liệu để giải quyết những vấn đề cụ thể.
Trong khai phá dữ liệu, học máy để dự đoán một số thông tin của dữ liệu dựa trên những đặc tính đã biết. Các phương pháp trong lĩnh vực học máy gồm có: Học máy Học giám sát Học bán giám sát Học không giám sát Hình 2: Các kỹ thuật Khai phá dữ liệu * Kỹ thuật học có giám sát (Supervise Machine Learning) Học có giám sát là một kĩ thuật của ngành học máy để xây dựng một hàm (function) từ dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm các cặp gồm đối tượng đầu vào (thường dạng vector), và đầu ra mong muốn. Đầu ra của một hàm có thể là một giá trị liên tục (gọi là qui hồi), hay có thể là dự đoán một nhãn phân loại cho một đối tượng đầu vào (gọi là phân loại).
Một số thuật toán thường được lựa chọn khi xây dựng bộ phân lớp gồm có: máy vector hỗ trợ (Support Vector Machine - SVM); K láng giềng gần nhất (K Nearest Neighbours); tiếp cận xác suất thống kê (Naïve Bayes); Cây quyết định (Decision Tree); sử dụng mạng nơron (Neural Network); dựa trên vector LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 trọng tâm (Centroid–base vector); tuyến tính bình phương nhỏ nhất (Linear Least Square Fit). * Kỹ thuật học bán giám sát (semi-supervised learning) Kỹ thuật này sử dụng cả dữ liệu đã gán nhãn và chưa gán nhãn để huấn luyện - điển hình là một lượng nhỏ dữ liệu có gán nhãn cùng với lượng lớn dữ liệu chưa gán nhãn. Học bán giám sát đứng giữa học không giám sát (không có bất kì dữ liệu có nhãn nào) và có giám sát (toàn bộ dữ liệu đều được gán nhãn). Nhiều nhà nghiên cứu nhận thấy dữ liệu không gán nhãn, khi được sử dụng kết hợp với một ít dữ liệu có gán nhãn, có thể cải thiện đáng kể độ chính xác.
Để gán nhãn dữ liệu cho một bài toán học máy thường đòi hỏi một chuyên viên có kĩ năng để phân loại bằng tay các ví dụ huấn luyện. Khi đó, học bán giám sát có giá trị thực tiễn lớn lao. Một ví dụ cho kỹ thuật học máy bán giám sát là đồng huấn luyện (co- training), trong đó hay nhiều bộ học được huấn luyện cùng một tập ví dụ nhưng mỗi bộ sử dụng một tập đặc trưng khác nhau, lý tưởng nhất là độc lập với nhau. Một cách tiếp cận khác là mô hình hoá phân phối xác suất đồng thời của các đặc trưng và nhãn.
Với dữ liệu chưa gán nhãn, có thể coi nhãn là “dữ liệu còn thiếu”. Các kỹ thuật xử lý dữ liệu còn thiếu như là lấy mẫu Gibbs và tối ưu kỳ vọng có thể được sử dụng để ước lượng tham số. * Kỹ thuật học không giám sát (Unsupervise Machine Learning) Khác với kỹ thuật học có giám sát là không biết trước số đầu ra tương ứng với tập dữ liệu đầu vào. Trong học không có giám sát, một tập dữ liệu đầu vào được thu thập.
Học không có giám sát thường dùng với các đối tượng đầu vào như là một tập các biến ngẫu nhiên. Sau đó, một mô hình mật độ kết hợp sẽ được xây dựng cho tập dữ liệu đó. Học không giám sát là phương pháp học sử dụng cho lớp bài toán gom cụm, phân cụm (clustering). Phương pháp học không giám sát: - Để thực hiện phân cụm, trước tiên cần một tập dữ liệu huấn luyện (training dataset) - là một tập các ví dụ học (training examples/instances).
Trong đó, mỗi ví dụ học chỉ chứa thông tin biểu diễn (ví dụ: một vector các giá trị LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 15 thuộc tính), mà không có bất kỳ thông tin gì về nhãn lớp hoặc giá trị đầu ra mong muốn (expected output). - Áp dụng một thuật toán học không có giám sát (ví dụ k-means) để học hàm/mô hình mục tiêu (trong trường hợp này là hàm phân cụm ứng với thuật toán được chọn). - Sử dụng một phương pháp thử nghiệm (có thể kết hợp với một tập dữ liệu có gán nhãn) để đánh giá hiệu năng của hàm mục tiêu học được. Một số thuật toán học không giám sát: có nhiều thuật toán học không giám sát được ra đời và phát triển nhằm giải quyết bài toán phân cụm phục vụ khai thác hiệu quả nguồn dữ liệu chưa gán nhãn nhiều và rất đa dạng.
Việc lựa chọn sử dụng thuật toán nào tuỳ thuộc vào dữ liệu và mục đích của từng bài toán. Trong đó các thuật toán thường được sử dụng như: k-means, HAC (Hierarchical Agglomerative Clustering), SOM (Self-Organizing Map),.4 Các thách thức trong khai phá dữ liệu Trong tài liệu [E2] đã nêu ra một số thách thức trong khai phá dữ liệu như sau: - Phát triển một lý thuyết thống nhất của khai thác dữ liệu: Có rất nhiều kỹ thuật được thiết kế để khai thác các vấn đề nhưng không có lý thuyết thống nhất. Phân loại, phân nhóm, luật kết hợp,… hay các cách tiếp cận khác như thống kê, học máy,… tuy vậy đây sẽ cơ sở cho các nghiên cứu trong tương lai.