Đề tài Nghiên cứu sự phát triển của công nghệ cơ sở dữ liệu và khai phá dữ liệu

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN ---oOo--- BÁO CÁO ĐỀ ÁN MÔN HỌC PHƯƠNG PHÁP LUẬN NGHIÊN CỨU KHOA HỌC Đề tài : NGHIÊN CỨU SỰ PHÁT TRIỂN CỦA CÔNG NGHỆ CƠ SỞ DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU Giảng viên hướng dẫn: GS.TSKH Hoàng Kiếm Học viên thực hiện: CH1101021 – Đỗ Văn Luyện Tp.Hồ Chí Minh ngày 13 tháng 04 năm 2012 GIỚI THIỆU ĐỀ TÀI. .......................................................................................................................... 3 1. Sự phát triển công nghệ cơ sở dữ liệu và tầm quan trọng của khai phá dữ liệu. ......................... 4 1.1 Sự phát triển công nghệ cơ sở dữ liệu và sự ra đời của công nghệ khai phá dữ liệu. ........... 4 1.2 Tầm quan trọng của khai phá dữ liệu. .................................................................................. 6 2. Khai thác dữ liệu là gì ? ................................................................................................................. 8 2.1 Các bước để khai phá dữ liệu ................................................................................................ 8 2.2 Kiến trúc một hệ thống khai thác dữ liệu điển hình. ........................................................... 10 3. Kiểu dữ liệu khai thác trong khai thác dữ liệu. .......................................................................... 13 3.1 Nguyên tắc. ........................................................................................................................... 13 3.2 Những thách thức khai thác dữ liệu trong các hệ thống lưu trữ điển hình. ....................... 13 4. Các nguyên tắc sáng tạo điển hình dùng trong phát triển công nghệ cơ sở dữ liệu và khai phá dữ liệu. ................................................................................................................................................. 17 4.1 Nguyên tắc phân nhỏ ............................................................................................................ 17 4.2 Nguyên tắc “tách khỏi ” ....................................................................................................... 17 4.3 Nguyên tắc sao chép. ............................................................................................................ 17 4.4 Nguyên tắc phản hồi. ............................................................................................................ 18 4.5 Nguyên tắc kết hợp............................................................................................................... 18 5. Tổng kết ....................................................................................................................................... 18 GIỚI THIỆU ĐỀ TÀI. Cùng với sự phát triển của khoa học kỹ thuật là sự bùng nổ của công nghệ dữ liệu mới như World Wide Web, data stream… đã đặt ra một yêu cầu cấp thiết cho các kỹ thuật mới và công nghệ tự động để có thể chuyển đổi một lượng lớn dữ liệu thành các thông tin hữu ích và đưa ra các dự báo hữu ích cho người sử dụng, Khai thác dữ liệu ra đời nhằm giải quyết những vấn đề trên. Vì thông tin có thể thay đổi liên tục và rộng lớn nên đây là một ngành khoa học đỏi hỏi phải luôn nâng cấp và tối ưu hóa tri thức hiện có để có thể phục vụ tốt hơn nhu cầu của người sử dụng. Trong bài tiểu luận này em xin được trình bày sự phát triển của công nghệ cơ sở dữ liệu từ lúc hình thành cho đến ngày nay để thấy được vai trò của công nghệ khai phá dữ liệu là to lớn như thế nào. Tiếp đến em xin được kể ra những thách thức mà ngành khoa học này gặp phải trong quá trình nghiên cứu và phát triển. Tại vì thời gian không cho em được nghiên cứu nhiều và nghiên cứu sâu em xin chỉ trình kể ra những thách thức mà hiện nay các nhà khoa học đang gặp phải. Hiện nay có một số công ty lớn như Facebook, Google…đã và đang giải quyết được một trong số các thách thức trong khai phá dữ liệu như là Search Engine và Social Network và họ cũng đã đang và rất thành công trong lĩnh vực của mình. 1. Sự phát triển công nghệ cơ sở dữ liệu và tầm quan trọng của khai phá dữ liệu. 1.1 Sự phát triển công nghệ cơ sở dữ liệu và sự ra đời của công nghệ khai phá dữ liệu. Khai thác dữ liệu là một trong những ngành khoa học thu hút rất nhiều sự chú ý trong những năm gần đây, do có một số lượng dữ liệu lớn và cần thiết để chuyển các dữ liệu đó thành thông tin hữu ích. Các thông tin và kiến thức thu được có thể sử dụng trong các ứng dụng khác nhau từ phân tích thị trường, phát hiện gian lận, kiểm soát sản xuất và khoa học thăm dò. Khai thác dữ liệu có thể xem như là một kết quả của sự tiến hoá tự nhiên của công nghệ thông tin. Sự phát triển của công nghiệp cơ sở dữ liệu cho ta biết tại sao khai phá dữ liệu đóng một vai trò quan trọng trong sự phát triển của nền công nghiệp công nghệ thông tin ngày nay. Kể từ khi công nghệ năm 1960, cơ sở dữ liệu và thông tin đã được phát triển từ hệ thông xử lý tập tin nguyên thuỷ. Việc nghiên cứu và phát triển trong các hệ thống cơ sở dữ liệu từ những năm 1970 đã có một quá trình phát triển từ các hệ thống cơ sở dữ liệu và mạng lưới phân cấp tới sự phát triển của hệ thống cơ sở dữ liệu quan hệ (nơi dữ liệu được lưu trữ trong các cấu trúc bảng quan hệ ), các công cụ mô hình hoá dữ liệu và lập chỉ mục. Ngoài ra người sử dụng đã bước đầu sử dụng ngôn ngữ truy vấn để truy xuất dữ liệu một cách linh hoạt và thuận tiện. Lúc này để các phương pháp xử lý giao dịch trực tuyến (OLTP) nơi truy vấn truy xuất dữ liệu được xem như một giao tác cơ bản thì người dùng bắt đầu phải tối ưu hoá các xử lý truy vấn để các ứng dụng được sử dụng một cách hiệu quả. Data Collection and Database Creation ( 1960s and earlier) -Dữ liệu xử lý trên file thuần tuý Database Management System ( 1970s – 1980s) -Phát triển hệ thống cơ sở dữ liệu : Dữ liệu được lưu trữ trong cấu trúc bảng quan hệ. - Phát triển công cụ mô hình hoá dữ liệu : Mô hình quan hệ giữa các đối tượng, thực thể… - Lập chỉ mục và các phương pháp truy xuất dữ liệu : Cây B-Tree, bảng băm, … - Các ngôn ngữ truy vấn dữ liệu ( query languages) : SQL,…và tối ưu hoá xử lý truy vấn. - Phát triển hệ thống giao tiếp người dùng : User interfaces, forms, report… Advanced Database System (mid - 1980s - present) - Phát triển mô hình quan hệ đối tượng mở rộng, hướng đối tượng mở rộng và đối tượng quan hệ. - Phát triển cơ sở dữ liệu theo định hướng ứng dụng Advanced Data Analysis : Data Warehousing and Data Mining (late 1980s - present) - Data warehousing và OLAP - Khai phá dữ liệu và tìm kiếm tri thức. - Phát triển các ứng dụng khai phá dữ liệu chuyên sâu : Web mining, text mining, time-series analysis…. Web-based database ( 1990s - present) - Phát triển dựa trên XML database. - Thông tin và dữ liệu được tích hợp cùng nhau. New Generation of Integrated Data and Information Systems. ( present - future) Công nghệ cơ sở dữ liệu từ những năm 1980 đã được đặc trưng bới sự áp dụng phổ biến các công nghệ quan hệ, các nghiên cứu độc lập và sự phát triển hoạt động trên các hệ thống cơ sở dữ liệu mới. Sự ra đời của các mô hình quan hệ mở rộng, hướng đối tượng và các mô hình suy luận đã thúc đẩy sự phát triển của các hệ cơ sở dữ liệu tiên tiến hơn như các hệ thống cơ sở dữ liệu theo định hướng ứng dụng, bao gồm cả không gian, đa phương tiện, cảm biến và cơ sở dữ liệu khoa học kỹ thuật, cơ sở tri thức và các ứng dụng thông tin văn phòng phát triển mạnh mẽ trong thời kỳ này. Các vấn đề liên quan đến phân phối dữ liệu, chia sẻ dữ liệu đươc nghiên cứu rộng rãi. Lúc này hệ thống cơ sở dữ liệu và Internet dựa trên hệ thống thông tin World Wide Web (WWW) cũng đã xuất hiện và đóng một vai trò quan trọng sự phát triển của ngành công nghiệp thông tin. 1.2 Tầm quan trọng của khai phá dữ liệu. Các tiến bộ vượt bậc trong công nghệ phần cứng máy tính đã dẫn đến nguồn cung cấp lớn các máy tính mạnh mẽ, dung lượng lưu trữ trong các thiết bị ngày càng lớn. Công nghệ này thúc đẩy sự phát triển ngành công nghiệp cơ sở dữ liệu và thông tin, làm cho một số lượng lớn các cơ sở dữ liệu và kho thông tin có sẵn cho quản lý giao dịch, thông tin truy hồi và phân tích dữ liệu. Dữ liệu có thể được lưu trữ trong nhiều loại khác nhau của cơ sở dữ liệu và kho thông tin. Một kho lưu trữ nhiều nguồn dữ liệu không đồng nhất tổ chức theo một lược đồ thống nhất tại một trang web duy nhất để tạo điều kiện thuận lợi cho việc ra quyết định quản lý. Công nghệ dataWarehousing bao gồm dữ liệu, tích hợp và làm sạch dữ liệu, phân tích dữ liệu trực tuyến (OLAP), kỹ thuật phân tích các chức năng, hợp nhất và tập hợp cũng như khả năng xem xét thông tin ở nhiều ở nhiều góc khác nhau. Ngoài ra một lượng lớn dữ liệu có thể được tích luỹ vượt quá kiến trúc cơ sở dữ liệu và kho dữ liệu. Ví dụ điển hình là các dòng data trong World Wide Web, nơi có các dòng dữ liệu liên tục, trong các ứng dụng như các mạng cảm biến, phân tích định tuyến Router… thì phân tích và sử dụng dữ liệu hiệu quả trở thành một nhiệm vụ đầy thử thách. Sự phong phú của dữ liệu cùng với sự cần thiết cho các công cụ phân tích dữ liệu mạnh mẽ, thu thập và lưu trữ trong kho dữ liệu lớn và rất nhiều các ứng dụng khác vượt xa khả năng của con người để hiểu và cẩn phải có một công cụ mạnh mẽ để làm những việc như vậy Kết quả là các dữ liệu thu thập trong các kho dữ liệu lớn trở thành những dữ liệu lưu trữ rất hiếm khi sử dụng và truy cập. Do đó các quyết định quan trọng thường được thực hiện không dựa trên các dữ liệu thông tin phong phú được lưu trữ trong kho dữ liệu mà là những quyết định mang tính trực giác, đơn giản là vì các nhà sản xuất không có đủ các công cụ trích xuất các kiến thức từ một kho dữ liệu lớn. => Công cụ khai thác dữ liệu được ra đời để thực hiện việc phân tích dữ liệu và có thể phát hiện ra cá mô hình dữ liệu quan trọng góp phần rất lớn trong sự phát triển của doanh nghiệp. 2. Khai thác dữ liệu là gì ? 2.1 Các bước để khai phá dữ liệu Nói một cách đơn giản khai thác dữ liệu dùng để “giải nén” hoặc “khai thác” kiến thức từ một số lượng lớn dữ liệu. Các bước để khai phá dữ liệu:  Làm sạch dữ liệu: loại bỏ những thành phần gây nhiễu, khó xác định quy luật).  Tích hợp dữ liệu : Dữ liệu có thể được tích hợp từ nhiều nguồn khác nhau.  Lựa chọn dữ liệu : Chọn lựa dữ liệu có liên quan đến quá trình phân tích được lấy từ cơ sở dữ liệu.  Chuyển đổi dữ liệu: Dữ liệu được chuyển đổi thành các hình thức thích hợp với các hệ cơ sở tri thức, cơ sở dữ liệu khác nhau…  Khai thác dữ liệu: Các phương pháp thông minh được áp dụng để trích xuất ra các mẫu dữ liệu, các mô hình dữ liệu.  Đánh giá các mẫu, mô hình: Đánh giá mô hình đại diện cho kiến thức thu được.  Trình bày tri thức. Flat files Databases Data Warehouse Patterns Knowledge Cleaning and integration Data mining Evaluation and Presentation Hai bước đầu là quá trình tiền xử lý cho việc khai phá dữ liệu. Khai phá dữ liệu cần phải được hỗ trợ từ người dùng và các cơ sở tri thức hiện có. Các mẫu, phát hiện mới được thể hiện cho người sử dụng và được lưu trữ như là kiến thức mới trong cơ sở tri thức. Khai thác dữ liệu lúc này chỉ là một bước trong toàn bộ quá trình, là một trong những bước cần thiết bởi vì nó phát hiện ra các mô hình ẩn để đánh giá. 2.2 Kiến trúc một hệ thống khai thác dữ liệu điển hình. DataMining với tên gọi của nó với nghĩa cơ bản là phát hiện kiến thức. Tuy nhiên trong ngành công nghiệp, trong các công nghệ truyền thông và trong nnghiên cứu cơ sở dữ liệu khai thác dữ liệu đang dần phổ biến hơn so với thuật ngữ ban đầu. Rộng hơn thì DataMining là quá trình phát hiện kiến thức từ một lượng lớn dữ liệu được lưu trữ trong cơ sở dữ liệu, kho dữ liệu hoặc kho lưu trữ các thông tin khác. Kiến trúc của một hệ thống khai thác dữ liệu điển hình có các thành phần chính như sau :  Cơ sở dữ liệu, kho dữ liệu, World Wide Web, hoặc kho lưu trữ các thông tin khác: Trên các hệ thống dữ liệu này phải làm sạch dữ liệu (loại bỏ những thành phần gây nhiễu trong dữ liệu), sử dụng kỹ thuật tích hợp dữ liệu để có thể sử dụng dữ liệu một cách hiệu quả.  Hệ quản trị cơ sở dữ liệu hoặc máy chủ kho dữ liệu : Có nhiệm vụ trong việc lấy dữ liệu có liên quan dựa trên yêu cầu khai thác dữ liệu của người dùng.  Cơ sở tri thức (knowledge base): Đây là những kiến thức tên miền (domain) được sử dụng để hướng dẫn tìm kiếm hoặc đánh giá các mẫu tìm kiếm thú vị. Những kiến thức có thể bao gồm các khái niệm phân cấp được sử dụng để tổ chức các thuộc tính hoặc các giá trị thuộc tính thành các cấp độ trừu tượng khác nhau. Kiến thức chẳng hạn như niềm tin của người sử dụng có thể được sử dụng để đánh giá mức độ lý thú của một sản phẩm.  Datamining engine: Engine này là cần thiết để hệ thống khai thác dữ liệu bao gồm một tập hợp các phân hệ chức năng cho các nhiệm vụ chẳng hạn như tính chất, phân loại, dự báo, phân tích cụm, phân tích định tuyến và phân tích sự tiến hóa…  Các mô hình đánh giá (Pattern evaluation module): Thành phần này thường được sử dụng để so sánh, tương tác với các module khai thác dữ liệu để tập trung tìm kiếm ra một mô hình mới thú vị. Nó có thể sử dụng các phương pháp khác nhau để lọc ra các mẫu phảt hiện.  Giao diện người dùng ( User interface): Là một giao tiếp giữa người dùng và hệ thống khai thác dữ liệu, cho phép người dùng tương tác với hệ thống bằng cách thiết lập một truy vấn khai thác dữ liệu , cung cấp thông tin để giúp tập trung tìm kiếm và thực hiện thăm dò khai thác dữ liệu dựa trên khai thác dữ liệu trung gian kết quả. Ngoài ra thành phần này cho phép người dùng duyệt các lược đồ cơ sở dữ liệu và kho dữ liệu hoặc cấu trúc dữ liệu, đánh giá mô hình khai thác, và hình dung ra các mô hình trong các hình thức khác nhau. Từ quan điểm kho dữ liệu (data warehouse), khai thác dữ liệu có thể được xem như là một giai đoạn tiên tiến về xử lý phân tích trực tuyến (OLAP). Mặc dù có rất nhiều hệ thống khai thác dữ liệu trên thị trường nhưng không phải tất cả trong số đó thể thực hiện khai thác dữ liệu một cách hiệu quả. Một phân tích dữ liệu hệ thống không thể xử lý một lượng lớn dữ liệu phải được phân loại một cách thích hợp. Một hệ thống có thể chỉ có một kiểu dữ liệu hoặc truy vẫn thông tin, bao gồm cả việc tìm kiếm các giá trị tổng hợp hoặc thực hiện truy vấn trả lời suy luận trong cơ sở dữ liệu lớn cần được phân loại một cách thích hợp hơn là một hệ thống cơ sở dữ liệu, một hệ thống truy xuất thông tin, hoặc một hệ thống cơ sở dữ liệu suy luận. Khai thác dữ liệu liên quan đến việc tích hợp các kỹ thuật lừ nhiều lĩnh vực như cơ sở dữ liệu, công nghệ kho dữ liệu, số liệu thống kê, máy học, máy tính hiệu suất cao, nhận dạng mẫu, mạng neural, phân tích dữ liệu trực quan, thu hồi thông tin, hình ảnh và xử lý tín hiệu và phân tích các dữ liệu không gian và thời gian. 3. Kiểu dữ liệu khai thác trong khai thác dữ liệu. 3.1 Nguyên tắc. Về nguyên tắc khai thác dữ liệu nên được áp dụng đối với bất kỳ loại kho dữ liệu, cũng như dữ liệu tạm thời chẳng hạn như dữ liệu dòng (data stream). Do đó phạm vi kiểm tra thường trên các quan hệ cơ sở dữ liệu, kho dữ liệu, các dòng dữ liệu, World Wide Web…Hệ thống cơ sở dữ liệu cao cấp bao gồm các đối tượng cơ sở dữ liệu quan hệ và cơ sở dữ liệu theo định hướng ứng dụng cụ thể chẳng hạn như cơ sở dữ liệu không gian, cơ sở dữ liệu chuỗi thời gian (time-series databases), cở sở dữ liệu văn bản, cơ sở dữ liệu đa phương tiện. 3.2 Những thách thức khai thác dữ liệu trong các hệ thống lưu trữ điển hình. Những thách thức và kỹ thuật khai thác có thể khác nhau cho mỗi hệ thống lưu trữ.  Cơ sở dữ liệu quan hệ : Hệ quản trị cơ sở dữ liệu (DBMS) bao gồm tập dữ liệu có liên quan đến nhau, được biết đến như là một cơ sở dữ liệu, và thiết lập chương trình phần mềm quản lý và truy cập dữ liệu. Thách thức khi mà khai phá dữ liệu trên cơ sở dữ liệu quan hệ này là đó là tối ưu hóa và xử lý truy vấn dữ liệu.  Data Warehouses : Là kho lưu trữ thông tin thu thập từ nhiều nguồn, được lưu trữ thành một cấu trúc thống nhất. Các thách thức khi mà khai phá dữ liệu trên kho thông tin rộng lớn này đó là việc tối ưu hóa và xử lý truy vấn dữ liệu trên các kho dữ liệu.  Các hệ thống thông tin và dữ liệu nâng cao: Hệ thống cơ sở dữ liệu quan hệ đã được sử dụng rộng rãi trong các ứng dụng (Applications) . Với sự tiến bộ của công nghệ cơ sở dữ liệu, các loại khác nhau của dữ liệu mới và thông tin hệ thống tập tin gốc đã nổi lên và đang phát triển để giải quyết yêu cầu của các ứng dụng mới. Các ứng dụng cơ sở dữ liệu mới bao gồm xử lý dữ liệu không gian (như là bản đồ), dữ liệu thiết kế kỹ thuật (như thiết kế của các tòa nhà, các thành phần hệ thống), siêu văn bản và dữ liệu đa phương tiện (bao gồm cả văn bản, video, hình ảnh, dữ liệu âm thanh), dữ liệu thời gian thực (dữ liệu chứng khoán), dòng dữ liệu (như là video, dữ liệu cảm biến), World Wide Web (được phân bố rộng rãi trong các kho lưu trữ thông tin được cung cấp bởi mạng Internet). Các ứng dụng này yêu cầu cấu trúc dữ liệu hiệu quả và khả năng mở rộng các phương pháp để xử lý cấu trúc đối tượng phức tạp. Để đáp ứng những nhu cầu này thì hệ thống cơ sở dữ liệu tiên tiến và ứng dụng theo định hướng hệ thống cơ sở dữ liệu cụ thể đã được phát triển bao gồm hệ thống cơ sở dữ liệu quan hệ hướng đối tượng (object-relational database systems), hệ thống dữ liệu thời gian thực (time-series database systems), hệ thống cơ sở dữ liệu xử lý văn bản (text database system) và dữ liệu đa phương tiện (multimedia database system), hệ thống dữ liệu dòng (data stream management systems), hệ thống thông tin toàn cầu Web-based ( Web-bases global information systems).  Cơ sở dữ liệu quan hệ hướng đối tượng ( Object-Relational Databases) Mô hình này được xây dựng dựa trên mô hình dữ liệu đối tượng – quan hệ. Nó được kế thừa từ các khái niệm của cơ sở dữ liệu hướng đối tượng. Mỗi thực thể được xem như là một đối tượng. Các hành động của thực thể được coi như là một thược tính của đối tượng.  Dữ liệu dòng thời gian ( Time-Series Databases and Sequence Databases). Một cơ sở dữ liệu thời gian lưu trữ dữ liệu quan hệ bao gồm các thuộc tính liên quan đến thời gian. Ví dụ như Google muốn biết từ khóa nào của ngày hôm nay phổ biến hơn ngày hôm qua. Yahoo muốn biết trang nào của họ ít được quan tâm trong một giờ qua, hay nhân viên của một siêu thị muốn kiểm soát được hàng tồn kho, cập nhật giá (thị trường chứng khoán)….  Cơ sở dữ liệu không gian (Spatial Databases and Spatiotemporal Databases). Không gian cơ sở dữ liệu lưu trữ thông tin liên quan đến không gian. Ví dụ như cơ sở dữ liệu địa lý (bản đồ), cơ sở dữ liệu hình ảnh y tế, vệ tinh…  Text Databases and Multimedia Databases. Cơ sở dữ liệu văn bản không có cấu trúc và cơ sở dữ liệu văn bản có cấu trúc như XML/HTML. Việc phát triển và khai thác dữ liệu văn bản có cấu trúc thường được sử dụng thường xuyên và có thể được thực hiện bằng cách sử dụng hệ thống cơ sở dữ liệu quan hệ. Cơ sở dữ liệu đa phương tiện như lưu trữ hình ảnh, âm thanh, video. Nhu cầu của người sử dụng trên cơ sở dữ liệu này nhiều nên thách thức trong khai phá dữ liệu là phải hỗ trợ được nhiều người dùng và phải được tích hợp với các phương pháp khai thác dữ liệu khác, khai thác nhiều tính năng từ dữ liệu đa phương tiện…  Data Stream. Nhiều ứng dụng hiện nay đã và đang sử dụng một loại dữ liệu mới để phân tích, khám phá các mô hình trong các dòng dữ liệu. Ví dụ chúng ta có thể phát hiện sự xâm lấn của một mạng máy tính dựa trên bất thường của dòng tin nhắn có thể được phát hiện bằng cách phân nhóm các dòng dữ liệu.  The World Wide Web. World Wide Web và các dịch vụ phân phối và chuyển tải