MỞ ĐẦU Trong điều kiện và yêu cầu của thương trường, đòi hỏi phải có những phương pháp nhanh, phù hợp, tự động, chính xác và có hiệu quả để lấy được thông tin có giá trị. Các tri thức chiết xuất được từ cơ sở dữ liệu sẽ là một nguồn tài liệu hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt động hoặc trong việc ra quyết định sản xuất kinh doanh. Vì vậy, tính ứng dụng của khai thác luật kết hợp từ cơ sở dữ liệu là một vấn đề đang được quan tâm. Khai phá dữ liệu là giai đoạn quan trọng trong tiến trình khai thác tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ cho việc ra quyết định trong khoa học và kinh doanh.
Công nghệ Multimedia liên quan tới việc mô tả sự kết hợp các dạng thông tin khác nhau (âm thanh, hình ảnh, văn bản, video) dưới dạng tín hiệu số. Một cơ sở dữ liệu Multimedia đòi hỏi phải có các phương thức đặc biệt nhằm mục đích tối ưu hóa việc lưu trữ, truy cập và khai thác các dạng thông tin đặc biệt này. Luật kết hợp là phương tiện hữu ích để khám phá các mối liên kết trong dữ liệu. Khai phá luật kết hợp trong cơ sở dữ liệu Multimedia cho phép tiết kiệm chi phí và làm tăng hiệu suất làm việc.
9 TIEU LUAN MOI download : skknchat@gmail.com CHƢƠNG 1- TỔNG QUAN VỀ PHÁT HIỆN TRI THỨC VÀ KHAI PHÁ DỮ LIỆU 1. Phát hiện tri thức và khai phá dữ liệu Sự phát triển mạnh mẽ của công nghệ thông tin làm cho khả năng thu thập và xử lý thông tin của các hệ thống thông tin tăng một cách nhanh chóng. Số liệu thống kê đưa ra vào năm 2006 cho thấy tình trạng “ngập tràn thông tin mà thiếu thốn tri thức” hiện nay, tồn tại nhiều kho chứa dữ liệu khổng lồ có dung lượng tăng trưởng với tốc độ cao. Hàng triệu cơ sở dữ liệu đã được sử dụng trong các hoạt động sản xuất, kinh doanh, quản lý., trong đó có nhiều cơ sở dữ liệu cực lớn cỡ Gigabyte, thậm chí là Terabyte.
Ví dụ điển hình là Yahoo! có hơn 100TB, Google đã lưu trữ hơn 4 tỷ trang Web với dung lượng nhiều trăm TB; Alexa sau 7 năm đã có 500 TB [3]. Việc thu thập và lưu trữ các kho chứa dữ liệu khổng lồ được liệt kê trên đây dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ thành các tri thức có ích. Do vậy, khai phá dữ liệu (KPDL) nhằm phát hiện các tri thức mới giúp ích cho hoạt động của con người đã trở thành một lĩnh vực quan trọng của ngành Công nghệ thông tin. Quá trình phát hiện tri thức từ cơ sở dữ liệu Thông tin là một khái niệm trừu tượng, được thể hiện dưới nhiều dạng thức khác nhau.
Thông tin có thể được phát sinh, lưu trữ, biến đổi trong những vật mang tin (gọi là giá). Dữ liệu là sự biểu diễn thông tin và được thể hiện bằng các tín hiệu vật lý. Dữ liệu là một dãy các bit, các số và các ký hiệu, hoặc các “đối tượng” có một ý nghĩa nào đó khi được gửi cho một chương trình dưới một dạng nhất định. Sử dụng các bit để đo lường các 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.
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ó 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à dữ liệu có độ trừu tượng và tổ chức cao. [3] Phát hiện tri thức trong các cơ sở dữ liệu là một quy trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: hợp thức, mới, khả ích, và có thể hiểu được.
Khai phá dữ liệu là một bước trong quy trình phát hiện tri thức gồm có các thuật toán khai phá dữ liệu chuyên dùng dưới một số quy đị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. Nói một cách khác, mục đích của phát hiện tri thức và KPDL là tìm ra các mẫu và các mô 10 TIEU LUAN MOI download : skknchat@gmail.com hình đang tồn tại trong các cơ sở dữ liệu nhưng vẫn còn bị che khuất bởi hàng “núi” dữ liệu. Quá trình phát hiện tri thức được mô tả tóm tắt trên Hình 1.1: Quy trình phát hiện tri thức từ cơ sở dữ liệu Làm sạch dữ liệu (Data cleaning): Loại bỏ dữ liệu nhiễu hoặc dữ liệu không thích hợp. Tích hợp dữ liệu (Data integration): Tích hợp dữ liệu từ các nguồn khác nhau.
Chọn dữ liệu (Data Selection): Chọn những dữ liệu liên quan trực tiếp đến nhiệm vụ. Chuyển đổi dữ liệu (Data Transformation): Chuyển dữ liệu về những dạng phù hợp cho việc khai phá. KPDL (Data mining): Các kỹ thuật được áp dụng để 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á mẫu (Pattern evaluation): Đánh giá mẫu hoặc tri thức đã thu được.
Trình diễn dữ liệu (Knowledge Presentation): Biểu diễn những tri thức khai phá được cho người sử dụng. Nhiều người coi KPDL và khám phá tri thức trong cơ sở dữ liệu là như nhau. Tuy nhiên trên thực tế, KPDL là một bước trong quá trình phát hiện tri thức trong cơ sở dữ liệu, thi hành một thuật toán KPDL để tìm ra các mẫu từ dữ liệu theo khuôn dạng thích hợp. Xác định vấn đề 11 TIEU LUAN MOI download : skknchat@gmail.com Là một quá trình mang tính định tính với mục đích xác định được lĩnh vực yêu cầu phát hiện tri thức và xây dựng bài toán tổng kết.
Trong thực tế, các cơ sở dữ liệu được chuyên môn hóa và phân chia theo các lĩnh vực khác nhau như sản phẩm, kinh doanh, tài chính, … Với mỗi tri thức phát hiện được có thể có giá trị trong lĩnh vực này nhưng lại không mang nhiều ý nghĩa đối với một lĩnh vực khác. Vì vậy mà việc xác định lĩnh vực và định nghĩa bài toán giúp định hướng cho giai đoạn tiếp theo thu thập và tiền xử lý dữ liệu. Thu thập và tiền xử lý dữ liệu Các cơ sở dữ liệu thu được thường chứa rất nhiều thuộc tính nhưng lại không đầy đủ, không thuần nhất, có nhiều lỗi và các giá trị đặc biệt. Vì vậy, giai đoạn thu thập và tiền xử lý dữ liệu trở nên rất quan trọng trong quá trình phát hiện tri thức từ cơ sở dữ liệu.
Có thể nói rằng giai đoạn này chiếm từ 70% đến 80% giá thành trong toàn bộ bài toán. Người ta chia giai đoạn thu thập và tiền xử lý dữ liệu thành các công đoạn như: lựa chọn dữ liệu, làm sạch, làm giàu, mã hóa dữ liệu. Các công đoạn được thực hiện theo trình tự đưa ra được một cơ sở dữ liệu thích hợp cho các giai đoạn sau. Tuy nhiên, tùy từng dữ liệu cụ thể mà quá trình trên được điều chỉnh cho phù hợp vì người ta đưa ra một phương pháp cho mọi loại dữ liệu.
Chọn lọc dữ liệu: Đây là bước chọn lọc các dữ liệu có liên quan trong các nguồn dữ liệu khác nhau. Các thông tin được chọn lọc sao cho có chứa nhiều thông tin liên quan tới lĩnh vực cần phát hiện tri thức đã xác định trong giai đoạn xác định vấn đề. Làm sạch dữ liệu: Dữ liệu thực tế, đặc biệt dữ liệu lấy từ nhiều nguồn khác nhau thường không đồng nhất. Do đó cần có biện pháp xử lý để đưa về một cơ sở dữ liệu thống nhất phục vụ cho khai thác.
Nhiệm vụ làm sạch dữ liệu thường bao gồm: Điều hòa dữ liệu: Nhằm giảm bớt tính không nhất quán do dữ liệu lấy từ nhiều nguồn khác nhau. Phương pháp thông thường là khử các trường hợp trùng lặp dữ liệu và thống nhất các ký hiệu. Chẳng hạn, một khách hàng có thể có nhiều bản ghi do việc nhập sai tên hoặc do quá trình thay đổi một số thông tin cá nhân gây ra và tạo sự lầm tưởng có nhiều khách hàng khác nhau. Xử lý các giá trị khuyết: Tính không đầy đủ của dữ liệu có thể gây ra hiện tượng dữ liệu chứa các giá trị khuyết.
Đây là hiện tượng khá phổ biến. Thông thường, người ta có thể lựa chọn các phương pháp khác nhau để thực hiện việc xử lý các giá trị khuyết như: bỏ qua các bộ có giá trị khuyết, điểm bổ sung bằng tay, dùng một hằng chung để điền vào giá trị khuyết, dùng giá trị trung bình của mọi bản ghi cùng lớp hoặc dùng các giá trị mà tần suất xuất hiện lớn. 12 TIEU LUAN MOI download : skknchat@gmail.com Xử lý nhiễu và các ngoại lệ: Thông thường, nhiễu dữ liệu có thể là nhiễu ngẫu nhiên hoặc các giá trị bất thường. Để làm sạch nhiễu, người ta có thể sử dụng phương pháp làm trơn nhiễu hoặc dùng các giải thuật phát hiện ra các ngoại lệ để xử lý.
Làm giàu dữ liệu: Việc thu thập dữ liệu đôi khi không đảm bảo tính đầy đủ của dữ liệu. Một số thông tin quan trọng có thể thiếu hoặc không đầy đủ. Chẳng hạn, dữ liệu về khách hàng lấy từ một nguồn bên ngoài không có hoặc không đầy đủ thông tin về thu nhập. Nếu thông tin về thu nhập là quan trọng trong quá trình khai phá dữ liệu để phân tích hành vi khách hàng thì không thể chấp nhận đưa các dữ liệu khuyết thiếu vào được.
Quá trình làm giàu dư liệu cũng bao gồm việc tích hợp và chuyển đổi dữ liệu. Các dữ liệu từ nhiều nguồn khác nhau được tích hợp thành một kho thống nhất. Các khuôn dạng khác nhau của dữ liệu cũng được quy đổi, tính toán lại để đưa về một kiểu thống nhất, tiện cho quá trình phân tích. Đôi khi, một số thuộc tính mới có thể được xây dựng dựa trên các thuộc tính cũ.
Mã hóa: Các phương pháp dùng để chọn lọc, làm sạch, làm giàu dữ liệu sẽ được mã hóa dưới dạng các thủ tục, chương trình hay tiện ích nhằm tự động hóa việc kết xuất, biến đổi và di chuyển dữ liệu. Các hệ thống con đó có thể được thực thi định kỳ làm tươi dữ liệu phục vụ cho việc phân tích. Khai phá dữ liệu Giai đoạn khai phá dữ liệu được bắt đầu sau khi dữ liệu đã được thu thập và tiến hành xử lý.