Chương 1: Tổng quan về khai phá dữ liệu nói chung và khai thác webói riêng Chương 2: Cơ sở lý thuyết Chương 3: Xây dựng hệ thống chắt lọc thông tin sản phẩm trên web Cuối cùng là kết luận và hướng phát triển tiếp theo của đề tài. TIEU LUAN MOI download : skknchat@gmail.com 3 CHƢƠNG I: GIỚI THIỆU CHUNG 1.1 Tổng quan về phát hiện tri thức và khai phá dữ liệu 1.1 Quá trình phát hiện tri thức 1.1 Phát hiện tri thức Thông thường, dữ liệu được coi như một dãy các bit, hoặc các số và các ký hiệu, hoặc các “đối tượng” với một ý nghĩa nào đó khi được gửi đến một chương trình dưới một dạng nhất định. Ta sử dụng các bit để đo lượng thông tin và xem nó như là các dữ liệu đã được lọc bỏ các dư thừa, được 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. Chúng ta có thể xem tri thức như là các thông tin 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 ra, đượ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à dữ liệu có độ trừu tượng và tổ chức cao. Sử dụng thông tin hiệu quả là yếu tố thành công và mang tính sống còn trong mọi lĩnh vực nghiệp vụ hiện nay. Điều đó có nghĩa là, từ dữ liệu có sẵn phải lấy được những thông tin tiềm ẩn có giá trị mà trước đó chưa được phát hiện, tìm ra những xu hướng phát triển và những yếu tố tác động lên chúng.
Thực hiện công việc này chính là quá trình phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in DataBase – KDD) mà trong đó kỹ thuật cho phép lấy ra các tri thức gọi là kỹ thuật khai phá dữ liệu (Data mining). Tri thức có thể hiểu là một biểu diễn trong một ngôn ngữ nào đó diễn đạt một hoặc một vài mối quan hệ giữa các thuộc tính trong dữ liệu. Các ngôn ngữ thường được dùng để biểu diễn tri thức là các khung (frames), các đồ thị, các luật (rules), các công thức chính trong ngôn ngữ logic mệnh đề hoặc tân từ cấp một hay các hệ thống phương trình. Quá trình phát hiện tri thức mang tính hướng nhiệm vụ, tức là không hướng đến sự phát hiện mọi tri thức bất kì mà nhằm giải quyết tốt một nhiệm vụ cụ thể nhất định.
Vì vậy, quá trình phát hiện tri thức là quá trình hoạt động tương tác giữa người sử dụng hoặc chuyên gia phân tích với các công cụ tin học.2 Các giai đoạn của quá trình phát hiện tri thức Mục đích của quá trình phát hiện tri thức là rút ra tri thức từ dữ liệu trong cơ sở dữ liệu (CSDL) lớn. Quá trình KDD gồm nhiều giai đoạn và được lặp lại, mà trong đó sự lặp lại có thể xảy ra ở bất cứ thời điểm nào cần thiết. Quá trình đó có thể mô tả như trong hình 1.1 TIEU LUAN MOI download : skknchat@gmail.1: Quy trình phát hiện tri thức 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 sẽ quyết định cho việc trích rút các tri thức hữu ích và cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và với bản chất của dữ liệu.
Bước thứ hai là thu thập và xử lý thô, hay còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu, giải quyết tình huống thiếu dữ liệu, biến đổi và rút gọn dữ liệu nếu cần thiết. Bước này thường chiếm nhiều thời gian nhất trong toàn bộ quá trình phát hiện tri thức. Bước thứ ba là khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/và các mô hình tiềm ẩn dưới các dữ liệu. Bước thứ tư là nắm hiểu tri thức đã tìm được và đặc biệt là làm sáng rõ các tri thức bằng các mô tả và hay suy luận.
Bước thứ năm là củng cố, tinh chế các tri thức được phát hiện. Kết hợp các tri thức thành hệ thống. Giải quyết các xung đột tiềm tàng trong tri thức khai thác được. Sau đó tri thức được chuẩn bị sẵn sang cho ứng dụng.
Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực hiện.2 Khai phá dữ liệu 1.1 Định nghĩa Khai phá dữ liệu được định nghĩa là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong các nguồn dữ liệu lớn. Hiện nay, ngoài thuật ngữ khai phá dữ liệu, người ta còn dùng một số thuật ngữ khác có ý nghĩa tương tự như khai phá tri thức từ cơ sở dữ liệu (knowlegde mining from databases), trích lọc dữ liệu (knowlegde extraction), phân tích dữ liệu/mẫu TIEU LUAN MOI download : skknchat@gmail.2 Các hoạt động khai phá dữ liệu Một quá trình khai phá dữ liệu (KPDL) bao gồm năm giai đoạn chính sau: (1) Tìm hiểu nghiệp vụ và dữ liệu (2) Chuẩn bị dữ liệu (3) Mô hình hóa dữ liệu (4) Hậu xử lý và đánh giá mô hình (5) Triển khai tri thức Quá trình này có thể được lặp lại nhiều lần hay nhiều giai đoạn dựa trên phản hồi từ kết quả của các giai đoạn sau. Tham gia chính trong quá trình KPDL là các nhà tư vấn (NTV) và phát triển chuyên nghiệp trong lĩnh vực KPDL. [1] Trong giai đoạn đầu tiên, Tìm hiểu nghiệp vụ và dữ liệu, NTV nghiên cứu kiến thức về lĩnh vực sẽ áp dụng, bao gồm các tri thức cấu trúc về hệ thống và tri thức, các nguồn dữ liệu hiện hữu, ý nghĩa, vai trò và tầm quan trọng của các thực thể dữ liệu.
Việc nghiên cứu này được thực hiện thông qua việc giao tiếp giữa NTV và người dùng. Khác với phương pháp giải quyết vấn đề truyền thống mà ở đó bài toán được xác định chính xác ngay ở bước đầu tiên, ở đây NTV cần tìm hiểu các yêu cầu đầu tiên của người dùng và đề nghị các bài toán tiềm năng có thể phải giải quyết với nguồn dữ liệu đã cho. Tập các bài toán tiềm năng được tinh chỉnh và làm hẹp lại trong các giai đoạn sau. Các nguồn và đặc tả dữ liệu có liên quan đến tập các bài toán tiềm năng cũng được xác định chính xác dần.
Giai đoạn Chuẩn bị dữ liệu sử dụng các kỹ thuật tiền xử lý để biến đổi và cải thiện chất lượng dữ liệu làm thích hợp với những yêu cầu của các giải thuật học. Phần lớn các giải thuật KPDL hiện nay chỉ làm việc trên một tập dữ liệu đơn và phẳng, do đó dữ liệu phải được trích xuất và biến đối từ các dạng có sẵn trong CSDL phân tán (loại quan hệ hay hướng đối tượng) sang dạng CSDL quan hệ đơn giản với một bảng dữ liệu. Các giải thuật tiền xử lý tiêu biểu bao gồm: (a) Xử lý dữ liệu bị thiếu/mất: các dữ liệu bị thiếu sẽ được thay thế bởi các giá trị thích hợp. (b) Khử sự trùng lặp: các đối tượng dữ liệu trùng lặp sẽ bị loại bỏ đi.
Kỹ thuật này không sử dụng cho các tác vụ liên quan đến phân bố dữ liệu. (c) Giảm nhiễu: nhiễu và các đối tượng nằm ngoài khỏi phân bố chung sẽ bị loại đi khỏi dữ liệu. (d) Chuẩn hóa: miền giá trị của dữ liệu sẽ được chuẩn hóa. TIEU LUAN MOI download : skknchat@gmail.com 6 (e) Rời rạc hóa: các dữ liệu số sẽ được biến đổi ra các giá trị rời rạc.
(f) Trích rút và xây dựng đặc trưng mới từ các thuộc tính đã có. (g) Giảm chiều: dữ liệu của các thuộc tính chứa ít thông tin sẽ được loại bỏ. Các bài toán cần giải quyết được hình thành trong giai đoạn Mô hình hóa dữ liệu. Các giải thuật được áp dụng trong giai đoạn hai sẽ sử dụng dữ liệu đã tiền xử lý để tìm kiếm các qui tắc tiềm ẩn và chưa biết.
Công việc quan trọng nhất trong giai đoạn này là lựa chọn kỹ thuật phù hợp để giải quyết các vấn đề đặt ra. Để làm điều này, các bài toán được phân loại vào một trong những nhóm bài toán chính trong KPDL dựa trên đặc tả của chúng. Các mô hình kết quả của giai đoạn ba sẽ được hậu xử lý và đánh giá trong giai đoạn 4. Dựa trên các đánh giá của người dùng sau khi kiểm tra trên các tập thử, các mô hình sẽ được tinh chỉnh và kết hợp lại nếu cần.
Chỉ các mô hình đạt được mức yêu cầu cơ bản của người dùng mới đưa ra triển khai trong thực tế. Trong giai đoạn này, các kết quả được biến đổi từ dạng học thuật sang dạng phù hợp với nghiệp vụ và dễ hiểu hơn cho người dùng. Trong giai đoạn cuối, Triển khai tri thức, các mô hình được đưa vào những hệ thống thông tin thực tế dưới dạng các môđun hỗ trợ việc đưa ra quyết định. Mối quan hệ chặt chẽ giữa các giai đoạn trong quá trình KPDL là rất quan trọng cho việc nghiên cứu KPDL.
Một giải thuật trong KPDL không thể được phát triển độc lập, không quan tâm đến bối cảnh áp dụng mà thường được xây dựng để giải quyết một mục tiêu cụ thể. Do đó, sự hiểu biết bối cảnh vận dụng là rất cần thiết. Thêm vào đó, các kỹ thuật được sử dụng trong các giai đoạn trước có thể ảnh hưởng đến hiệu quả của các giải thuật sử dụng trong các giai đoạn tiếp theo.3 Các bài toán thông dụng trong Khai phá dữ liệu Trong KPDL, các bài toán có thể phân thành bốn loại chính. Bài toán thông dụng nhất là bài toán Phân lớp.
Với một tập các dữ liệu huấn luyện cho trước và sự huấn luyện của con người, các giải thuật phân loại sẽ lọc ra bộ phân loại (classifier) dùng để phân các dữ liệu mới vào một trong những lớp đã được xác định trước. Nhận dạng cũng là một bài toán thuộc kiểu Phân loại. Với mô hình học tương tự như bài toán Phân loại, lớp bài toán Dự đoán sẽ lọc ra các bộ dự đoán. Khi có dữ liệu mới đến, bộ dự đoán sẽ dựa trên thông tin đang có để đưa ra một giá trị số học cho hàm cần dự đoán.
Bài toán tiêu biểu trong nhóm này là dự đoán giá sản phẩm để lập kế hoạch trong kinh doanh. Các giải thuật Tìm luật liên kết (Association Rule) nhằm tìm kiếm các mối liên kết giữa các phần tử dữ liệu, ví dụ như nhóm các món hàng thường được mua kèm với nhau trong siêu thị. TIEU LUAN MOI download : skknchat@gmail.com 7 Các kỹ thuật Phân cụm (Clustering) sẽ nhóm các đối tượng dữ liệu có tính chất giống nhau vào cùng một nhóm.