Chương 1. TỔNG QUAN VỀ PHÁT HIỆN TRI THỨC TRONG CƠ SỞ DỮ LIỆU 1. TỔNG QUAN VỀ PHÁT HIỆN TRI THỨC TRONG CƠ SỞ DỮ LIỆU 1. Phát hiện tri thức trong cơ sở dữ liệu Trong thập kỉ trước, loài người đã tập hợp được một khối lượng vô cùng lớn các dữ liệu trong nhiều lĩnh vực khác nhau.
Bằng việc sử dụng các kỹ thuật thống kê kết hợp với các công cụ quản trị tệp, nhiều công ty đã đạt được những thành công nhất định trong việc phân tích lượng dữ liệu này. Tuy nhiên, kích cỡ của các kho dữ liệu hiện tại và tốc độ xử lý dữ liệu đòi hỏi cần phải có những cách tiếp cận mới để xử lý những dữ liệu này. Một thế hệ mới của các kỹ thuật và công cụ thông minh hỗ trợ con người trong việc phân tích, tìm kiếm tri thức đã ra đời. Những kỹ thuật, công cụ này thuộc vào một lĩnh vực đang phát triển của Công nghệ thông tin được gọi là phát hiện tri thức trong cơ sở dữ liệu (KDD).
Thông thường, dữ liệu được hiểu như là một dãy các bits, hoặc các số và các ký hiệu, trong khi, tri thức được xem như là các dữ liệu tích hợp, bao gồm các sự kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể được hiểu, có thể được phát hiện, hoặc có thể được học. Nói cách khác, tri thức có thể được coi là các dữ liệu có độ trừu tượng và tổ chức cao. Hiện tại có một số định nghĩa khác nhau về phát hiện tri thức trong cơ sở dữ liệu.
Trong luận văn này, chúng tôi sử dụng định nghĩa về KDD của Frawley,v Piatetsky- Shapior và Matheus năm 1991. “Phát hiện tri thức trong cơ sở dữ liệu là một quá trình nhận dạng các mô hình có thể hiểu được, có lợi ích tiềm ẩn, khác thường, có giá trị trong dữ liệu”. TIEU LUAN MOI download : skknchat@gmail.com 7 Trong đó: Hình 1: một tập dữ liệu đơn giản với 2 lớp - Dữ liệu: là một tập các nhân tố F. Trong ví dụ đưa ra trong hình 1, F bao gồm 23 trường hợp thể hiện các giá trị nợ, thu nhập, và hiện trạng cho vay.
- Mẫu: là một biểu thức E trong ngôn ngữ L dùng để mô tả các yếu tố trong một tập con FE của F. E được gọi là một mô hình nếu nó đơn giản hơn so với việc liệt kê tất cả các yếu tố trong FE. Ví dụ, mô hình “ nếu thu nhập < $t thì người đó được ngầm định là vay nợ” sẽ là một mô hình cho việc lựa chọn tương ứng của t. Mô hình này được minh hoạ trong hình 2: Nợ t$ Thu nhập Hình 2: Sử dụng ngưỡng giá trị thu nhập để phân lớp dữ liệu cho vay nợ - Quá trình: thông thường quá trình KDD là quá trình nhiều bước, nó bao gồm cả việc chuẩn bị số liệu, tìm kiếm mô hình, đánh giá tri thức, làm mịn dữ liệu sau khi hiệu chỉnh.
TIEU LUAN MOI download : skknchat@gmail.com 8 - Có giá trị: các mô hình được phát hiện có giá trị với các dữ liệu mới với độ chắc chắn tương đối. - Khác thường: các mô hình là khác bình thường. Sự khác thường có thể đo bằng sự thay đổi của dữ liệu ( bằng cách so sánh giá trị hiện tại với giá trị trong quá khứ, cũng như giá trị mong muốn). - Lợi ích tiềm ẩn: các mô hình tiềm ẩn các khả năng có ích nào đó và chúng có thể đo được bằng một hàm tiện ích.
- Có thể hiểu được đầy đủ: một mục tiêu của KDD là tạo ra các mô hình có thể hiểu được để con người dễ dàng hơn trong việc nắm bắt các thông tin có trong dữ liệu. Điều này là khó để đo lường một cách tường minh, nó thường được thay thế bằng một độ đo đơn giản hơn. Hiện đang có nhiều độ đo đơn giản được sử dụng, chúng bao gồm các các độ đo thuần tuý (dựa trên kích cỡ của mô hình theo bit) cho tới ngữ nghĩa. Trên cơ sở các định nghĩa trên có thể đưa ra định nghĩa về khai phá dữ liệu và quá trình KDD - Khai phá dữ liệu là một bước trong quá trình KDD bao gồm các thuật toán khai phá dữ liệu, theo 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.
Lưu ý rằng, không gian các mô hình thường là hữu hạn và việc liệt kê các mô hình bao gồm cả việc tìm kiếm trong không gian này. - Quá trình KDD là một quá trình sử dụng các phương thức khai phá dữ liệu (thuật toán) để tìm ra (xác định) cái được cho rằng là tri thức theo các mô tả của các độ đo và các ngưỡng, sử dụng Cơ sở dữ liệu F với một vài tiền tiến trình xử lý, lấy mẫu, và chuyển đổi F cần thiết. TIEU LUAN MOI download : skknchat@gmail. Quá trình phát hiện tri thức trong cơ sở dữ liệu Quá trình phát hiện tri thức bao gồm một số bước như được thể hiện trong hình3: Tìm hiểu và đánh giá Khai phá dữ liệu Thực hiện chuyển đổi Tiền xử lý dữ liệu Hình thành và định nghĩa bài toán Hình 3: Tổng quan về các bước của quá trinh KDD - Bước thứ nhất là tìm hiểu lĩnh vực ứng dụng và hình thành bài toán.
Bước này có ý nghĩa quan trọng cho việc rút ra được các tri thức hữu ích và cho việc chọn các phương pháp khai phá dữ liệu thích hợp trong bước ba sao cho phù hợp với mục đích ứng dụng và bản chất của dữ liệu. - Bước thứ hai là xử lý thô, hay còn gọi là tiền xử lý dữ liệu nhằm loại bỏ các dữ liệu nhiễu hoặc các bất thường, xử lý các giá trị bị thiếu, sửa các lỗi mang tính hệ thống, tập hợp các thông tin cần thiết để mô hình hoặc tính toán nhiễu, quyết định các chiến lược xử lý các trường dữ liệu bị lỗi. - Bước thứ ba: thực hiện việc chuyển đổi phát hiện ra các đặc điểm hữu ích để biểu diễn lại dữ liệu sao cho phù hợp với mục tiêu cần đạt tới. Có thể sử dụng phương pháp rút bớt số chiều hoặc biến đổi dữ liệu để giảm bớt số lượng các biến.
TIEU LUAN MOI download : skknchat@gmail.com 10 - Bước thứ tư là khai phá dữ liệu, tức là trích ra các mẫu các mô hình ẩn trong dữ liệu. Một mô hình có thể được xem như một biểu diễn tổng thể của một cấu trúc nhằm tóm lược thành phần mang tính hệ thống có trong dữ liệu hoặc mô tả tập dữ liệu này có thể sinh sôi nảy nở ra sao. Trong khi, một mẫu là một cấu trúc cục bộ có khi chỉ liên quan tới một nhóm các biến và một số trường hợp. Các lớp chính của các phương pháp khai phá dữ liệu là mô hình dự đoán chẳng hạn như phân loại và hồi qui; phân đoạn ; mô hình phụ thuộc chẳng hạn như các mô hình đồ thị hoặc ước lượng mật độ; mô hình tóm lược, ví dụ như tìm các mối quan hệ giữa các trường, các liên kết; và mô hình thay đổi và phát hiện độ lệch trong dữ liệu và tri thức.
- Bước thứ năm: tìm hiểu và đánh giá tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán, hai mục tiêu chính của các hệ thống khám phá trong thực tế. Kinh nghiệm cho thấy rằng các mẫu hoặc các mô hình phát hiện được từ các dữ liệu không phải lúc nào cũng đáng quan tâm và có thể trực tiếp sử dụng được ngay, và quy trình KDD cần phải được lặp đi lặp lại có điều chỉnh theo các tri thức đã phát hiện được. Để có thể đánh giá các luật được áp dụng trong qui trình KDD, người ta thường chia dữ liệu thành hai tập, huấn luyện trên tập thứ nhất và kiểm chứng trên tập thứ hai. Có thể lặp lại qui trình này một số lần với các phần chia khác nhau, sau đó lấy trung bình các kết quả để ước lượng các luật thi hành.
Dưới đây là một số bước cơ bản trong quá trình phát hiện tri thức trong cơ sở dữ liệu: - Tìm hiểu rõ phạm vi ứng dụng: những tri thức có liên quan trước đây, các mục đích của người sử dụng,. - Tạo lập tập dữ liệu đích: chọn ra một tập dữ liệu, hoặc tập trung vào một tập con các biến hoặc các mẫu dữ liệu mà trên đó cần phải phát hiện ra các tri thức. - Quá trình làm sạch dữ liệu: các phép cơ bản như loại bỏ nhiễu hoặc các giá trị kỳ dị nếu hợp lý, xử lý các giá trị bị thiếu, sửa các lỗi mang tính hệ thống, tập hợp các lthông tin cần thiết để mô hình hoặc tính toán nhiễu, quyết định các chiến lược xử lý các trường dữ liệu bị lỗi. TIEU LUAN MOI download : skknchat@gmail.com 11 - Rút gọn và dự đoán dữ liệu: phát hiện ra các đặc điểm hữu ích để biểu diễn lại dữ liệu sao cho phù hợp với mục tiêu cần đạt tới.
Có thể sử dụng phương pháp rút bớt số chiều hoặc biến đổi dữ liệu để giảm bớt số lượng các biến. - Lựa chọn nhiệm vụ của khai phá dữ liệu: quyết định xem mục đích của qui trình KDD này là gì: phân loại, hồi qui, hay gộp nhóm, v. - Lựa chọn phương pháp khai phá dữ liệu: chọn các phương pháp sẽ sử dụng để tìm các mẫu trong dữ liệu. Trong đó kể cả việc quyết định xem các mô hình nào và các tham số nào là thích hợp.
- Khai phá dữ liệu: rút ra các mẫu, các mô hình: tìm kiếm các mẫu đáng chú ý dưới một dạng biểu diễn khác đi hoặc một tập các biểu diễn như vậy: các qui tắc phân loại hoặc các cây, gộp nhóm. - Phân tích ý nghĩa và đánh giá các mẫu,các mô hình, có thể quay lại xử lý một trong các bước trước đó trong trường hợp cần thiết. - Củng cố tri thức đã phát hiện được: tích hợp tri thức này vào hệ thống thực hành, hoặc tạo ra các báo cáo về nó và phân phát cho những người quan tâm. Kiểm tra lại xem tri thức này có gì trái với những tri thức đã có trước đây không.
TIEU LUAN MOI download : skknchat@gmail. Một số vấn đề của việc phát hiện tri thức trong cơ sở dữ liệu Các thuật toán khai phá dữ liệu trong KDD thường phải tiến hành tìm kiếm trên toàn bộ không gian của các dữ liệu, do đó kích cỡ của các cơ sở dữ liệu cũng là một vấn đề đáng quan tâm.