Chương 1. Giới thiệu Khai phá dữ liệu 1. Tổng quan Khai phá dữ liệu Khai phá dữ liệu là một khái niệm ra đời cuối những năm 80 của thế kỷ trước. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện các thông tin có giá trị tiềm ẩn trong dữ liệu lớn.Về bản chất, khai phá dữ liệu 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 hình có tính chính quy trong tập dữ liệu.
Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD) để chỉ toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn [11]. Trong đó, khai phá dữ liệu là một bước đặc biệt trong toàn bộ quá trình, sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu hay các mô hình từ dữ liệu. Ở một góc độ nào đó, khái niệm khai phá dữ liệu và khai phá tri thức nhiều khi được coi là một. Tuy nhiên, nếu xét kỹ thì khai phá dữ liệu chỉ là một khâu quan trọng trong khai phá tri thức.
Một quá trình phát hiện tri thức trong cơ sở dữ liệu bao gồm các giai đoạn chính sau : (1) Làm sạch dữ liệu (Data Cleaning): Khử nhiễu và các dữ liệu mâu thuẫn. (2) Tích hợp dữ liệu (Data Integration): Kết hợp nhiều nguồn dữ liệu khác nhau. (3) Lựa chọn dữ liệu (Data Selection): Chắt lọc lấy những dữ liệu liên quan đến nhiệm vụ phân tích sau này. (4) Biến đổi dữ liệu (Data Transformation): Biến đổi dữ liệu thu được về dạng thích hợp cho quá trình khai phá.
(5) Khai phá dữ liệu (Data Mining): Sử dụng những phương pháp thông minh để khai thác dữ liệu nhằm thu được các mẫu mong muốn. (6) Đánh giá kết quả (Pattern Evaluation): Sử dụng các độ đo để đánh giá kết quả thu được. (7) Biểu diễn tri thức (Knowledge Presentation): Sử dụng các công cụ biểu diễn trực quan để biểu diễn những tri thức khai phá được cho người dùng. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 Quá trình này có thể được lặp lại nhiều lần, một hay nhiều giai đoạn trước có thể được lặp lại dựa trên phản hồi từ kết quả của các giai đoạn sau.
Đánh giá và trình diễn Dữ liệu khái Tri thức phá Mẫu Lựa chọn và chuyển dạng Dữ liệu chuyển Kho dữ dạng Làm sạch và tích hợp liệu Dữ liệu Hình 1.1: Quá trình phát hiện tri thức trong cơ sở dữ liệu Một số phương pháp khai phá dữ liệu tiêu biểu: Phân lớp (Classification) : Khai thác một hàm đã được huấn luyện trước để phân loại một đối tượng dữ liệu vào một trong các lớp được định nghĩa trước. Hồi qui (Regression) : Khai thác một hàm đã được huấn luyện trước để ánh xạ một đối tượng dữ liệu thành một giá trị thực là kết quả dự báo. Phân cụm (Clustering) : Giải quyết vấn đề tìm kiếm, phát hiện số lượng hữu hạn các cụm mô tả một tập hợp dữ liệu ban đầu không có nhãn. Đó là quá trình tìm cách nhóm các đối tượng đã cho vào các cụm, sao cho các đối tượng trong cùng một cụm tương tự nhau (similar), và các đối tượng khác cụm thì không tương tự nhau (dissimilar).
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 Tổng hợp (Summarization) : Quá trình bao gồm các phương pháp để tìm một mô tả xúc tích cho một tập (hoặc một tập con) dữ liệu. Mô hình hóa ràng buộc (Dependency Modeling) : Tìm một mô hình cục bộ mô tả các ràng buộc quan trọng giữa các biến hoặc giữa các giá trị của một đặc trưng trong một tập dữ liệu hoặc trong một phần của tập dữ liệu Phát hiện biến đổi và độ lệch (Change and Deviation Detection): Khai phá những biến đổi quan trọng nhất trong tập dữ liệu. Trong giai đoạn tiền xử lý số liệu, việc trích chọn thuộc tính đóng vai trò quan trọng. Tổng quan trích chọn thuộc tính Về cơ bản việc trích chọn thuộc tính có ích sẽ bao gồm hai công đoạn cơ bản gồm công đoạn xây dựng dữ liệu và công đoạn trích chọn thuộc tính.
Xây dựng dữ liệu là tạo ra bộ các thuộc tính, một công việc rất quan trọng trong việc phân tích số liệu. Yêu cầu đặt ra phải đảm bảo không để mất quá nhiều thông tin có ích đồng thời không được quá tốn kém chi phí tài nguyên và thời gian. Công đoạn trích chọn nhằm tìm ra thuộc tính đại diện phù hợp yêu cầu phân tích, loại bỏ thuộc tính dư thừa, thuộc tính nhiễu, tăng hiệu suất và kết quả khai phá dữ liệu. Có rất nhiều phương pháp và các hướng tiếp cận khác nhau, tựu chung lại đều hướng đến mục tiêu : Tăng tốc độ thuật toán Giảm không gian lưu trữ dữ liệu Tăng kết quả phân lớp, đoán nhận Giúp biểu diễn, minh họa dữ liệu dễ dàng hơn Để đánh giá độ tốt của một tập con đặc trưng phụ thuộc vào yêu cầu cụ thể khi phân tích dữ liệu, mọi công việc trong toàn bộ quá trình cũng đều hướng mục tiêu đạt được yêu cầu cụ thể trên.
Về cơ bản chúng ta có thể phân loại các phương pháp trích chọn theo hai cách tiếp cận khác nhau là Filter và Wrapper được trình bày trong các tài liệu [3, 13]. Lược đồ thực hiện [2] được giản hóa trong hai hình vẽ dưới đây. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 Trích lọc tập con của danh Thuật toán Dữ liệu sách các thuộc tính phân lớp Hình 1.2 : Hướng tiếp cận Filter Theo mô hình Filter, các thuộc tính được chọn độc lập với thuật toán khai phá dữ liệu. Ngược lại, mô hình Wrapper các thuộc tính được chọn phụ thuộc theo một nghĩa nào đó với thuật toán khai phá dữ liệu Dữ liệu huấn Thuật toán Dữ liệu Tìm kiếm thuộc tính phấn lớp huấn (Kiểm chứng) Tập thuộc tính Đánh giá kết quả Tập thuộc luyện lựa chọn tính Đánh giá thuộc tính Tập các thuộc Tính toán các tính lựa chọn giả thiết Thuộc tính phân lớp Đánh giá Dữ liệu kết quả Thuật toán phân kiểm tra lớp (Dự đoán) Hình 1.3 : Hướng tiếp cận Wrapper Mô hình Filter đánh giá mỗi cá thể bằng một vài tiêu chuẩn hay độ đo nào đó, rồi chọn ra tập con các thuộc tính được đánh giá cao nhất.
Nhìn chung, Filter coi tiến trình của trích chọn thuộc tính như tiến trình thực thi trước, sau đó mới sử dụng thuật toán để phân lớp. Mô hình Wrapper sử dụng một thuật toán tìm kiếm để đánh giá tập con các thuộc tính coi như là một nhóm hơn là một cá thể riêng lẻ. Cốt lõi của mô hình Wrapper là một thuật toán máy học cụ thể. Nó đánh giá độ tốt của những tập con đặc trưng tùy theo độ chính xác học của tập con, điều này xác định thông qua một tiêu chí nào đó.
Những thuật toán tìm kiếm cũng sử dụng hàm đánh giá kinh nghiệm (heuristics) để hướng dẫn việc tìm kiếm tập trung vào các đối tượng có triển vọng. Công việc cần thực hiện trong thuật toán trích chọn bao gồm : LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 - Phương pháp để sinh ra tập thuộc tính đặc trưng : (Có thể hiểu tương ứng với các chiến lược tìm kiếm). Đầu ra của bộ sinh sẽ xác định thuật toán trích chọn đặc trưng. Có hai chiến lược để sinh tập con : Đầy đủ (Complete) : Áp dụng chiến lược tìm kiếm vét cạn để sinh tập con.
Đối với hầu hết các hệ thông máy thực, chiến lược này không phù hợp do đỏi hỏi tài nguyên quá lớn Kinh nghiệm (Heuristically) : Để giảm bớt không gian tìm kiếm, kết quả thu được ở mức chấp nhận được, chiến lược sinh tập con đặc trưng dựa vào kinh nghiệm nào đó, có ba kỹ thuật điển hình là lựa chọn tiến (Forward Selection), lược bỏ lùi (Backward Elimination) và lựa chọn hai hướng (Bi – direction Selection). - Định nghĩa hàm đánh giá : (đưa ra các tiêu chí để có thế xác định một thuộc tính hay nhóm thuộc tính là tốt hay không tốt). Bộ đánh giá của những mô hình thuật toán khác nhau là khác nhau. Bộ đánh giá mô hình Filter thường là các hàm đánh giá, trong khi mô hình Wrapper là độ học chính xác đạt được bởi quá trình thực thi thuật toán học máy điều khiển trên hệ thống học.
Hàm đánh giá : hàm đánh giá thường dùng như xấp xỉ chất lượng (Approxination Quality), độ quan trọng (Feature Importance), trọng số của thuộc tính (Feature Weight) Học chính xác : mô hình Wrapper, dữ liệu chia ngẫu nhiên thành hai tập, tập huấn luyện và tập kiểm tra. Độ chính xác đạt được trong trường hợp này là giá trị ngẫu nhiên. Để tăng cường độ ổn định mô hình Wrapper chúng ta thường sử dụng kỹ thuật kiểm tra chéo (Cross Validation) - Ước lượng hàm đánh giá đó : kiểm chứng lại xem hàm đánh giá có thực sự phù hợp và hiệu quả với bộ dữ liệu không 2. Kết luận Trích chọn thuộc tính giúp tìm ra những đặc trưng tốt nhất, đồng thời loại bỏ nhiễu, giảm bớt chiều trong dữ liệu.
Hai mô hình phổ biến trong phương pháp trích chọn thuộc tính đặc trưng là Filter và Wrapper. Mỗi mô hình đều có những ưu điểm và nhược điểm riêng. Tùy từng yêu cầu và trường hợp cụ thể mà ta có thể áp dụng một trong hai mô hình này. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 Chương 2.
Họ thuật toán k-Láng giềng gần nhất và Thuật toán Di truyền 2. Họ thuật toán k-Láng giềng gần nhất 2. Khái niệm Nếu không có cái ngẫu nhiên đi cùng với cái tất nhiên, khoa học thống kê sẽ không ra đời. Một trong những nhiệm vụ cơ bản của thống kê là đi ước lượng cái chắc chắn tương đối trong cái không chắc chắn (bất định).
Để làm việc với cái không chắc chắn này, thống kê chủ yếu dựa vào khái niệm về khoảng cách. Từ việc tính toán khoảng cách các điểm, tính độ lệch chuẩn, phương sai của biến ngẫu nhiên cho đến các công cụ xa hơn là các công cụ phân tích tương quan, phương sai, phân tích các yếu tố (tạm dịch từ factor analysis), phân tích các thành phần trọng yếu (tạm dịch từ principal component analysis), phân tích cụm (tạm dịch từ cluster analysis)… đều dựa trên khái niệm khoảng cách. Ngoài ra khoảng cách cũng không chỉ đơn giản là độ dài đường nối điểm này tới điểm kia, là sự xa và gần như thông thường vẫn dùng, khoảng cách còn có khoảng cách giàu nghèo, khoảng cách học vấn. nhìn chung khoảng cách còn nên được hiểu rộng hơn như là sự khác biệt (difference), đôi khi còn được xem là lỗi (error).