Tài liệu Phát hiện luật kết hợp ứng dụng trong cơ sở dữ liệu quản lý sinh viên

0 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LÊ XUÂN LƢỢNG PHÁT HIỆN LUẬT KẾT HỢP ỨNG DỤNG TRONG CƠ SỞ DỮ LIỆU QUẢN LÝ SINH VIÊN Chuyên nghành: Khoa học máy tính Mã số: 60.48.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Ngƣời hƣớng dẫn khoa học: TS Vũ Mạnh Xuân THÁI NGUYÊN - 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i LỜI CAM ĐOAN Tôi xin cam đoan toàn bộ nội dung trong Luận văn hoàn toàn theo đúng nội dung đề cương cũng như nội dung mà cán bộ hướng dẫn giao cho. Nội dung luận văn, các phần trích lục các tài liệu hoàn toàn chính xác. Nếu có sai sót tôi hoàn toàn chịu trách nhiệm. Tác giả luận văn Lê Xuân Lượng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii MỤC LỤC Lời cam đoan .................................................................................................................. i Mục lục ...............................................................................................................ii Danh mục các chữ viết tắt ....................................................................................... iv Danh mục các bảng ................................................................................................... v Danh mục các hình vẽ ............................................................................................. vi MỞ ĐẦU ............................................................................................................................ 1 Chƣơng 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU........................................................................................................ 3 1.1. Một số khái niệm về cơ sở dữ liệu ........................................................ 3 1.1.1. Cơ sở dữ liệu ................................................................................... 3 1.1.2. Hệ quản trị cơ sở dữ liệu ................................................................. 4 1.2. Tổ chức và khai thác cơ sở dữ liệu truyền thống ................................... 5 1.3. Kho dữ liệu ............................................................................................ 6 1.3.1. Đinh nghĩa kho dữ liệu.................................................................... 6 1.3.2. Cấu trúc của kho dữ liệu ................................................................. 7 1.3.3. Mục đích của việc xây dựng kho dữ liệu ........................................ 9 1.4. Khai phá dữ liệu ................................................................................... 11 1.4.1. Khái niệm ...................................................................................... 11 1.4.2. Các bước của quá trình phát hiện tri thức ..................................... 11 1.4.3. Một số phương pháp khai phá dữ liệu ......................................... 13 1.4.3.1. Phương pháp suy diễn và quy nạp ......................................... 13 1.4.3.2. Cây quyết định và luật ........................................................... 14 1.4.3.3. Phân nhóm và phân đoạn ....................................................... 16 1.4.3.4. Phương pháp ứng dụng K-láng giềng gần ............................. 16 1.4.3.5. Các phương pháp dựa trên mẫu ............................................. 17 1.4.3.6. Phát hiện các luật kết hợp ...................................................... 17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii 1.4.4. Nhiệm vụ chính của khai phá dữ liệu ........................................... 19 1.4.5. Những khó khăn trong nghiên cứu khai phá dữ liệu .................... 21 1.4.6. Một số ứng dụng khai phá dữ liệu ................................................ 24 Chƣơng 2. PHÁT HIỆN LUẬT KẾT HỢP .............................................................. 25 2.1. Các khái niệm và tính chất của luật kết hợp ........................................ 25 2.1.1. Một số khái niệm .......................................................................... 25 2.1.2. Thuật toán cơ bản .......................................................................... 28 2.1.3. Tính chất của luật kết hợp và tập mục phổ biến ........................... 32 2.1.4. Một số hướng tiếp cận trong khai phá luật kết hợp ...................... 33 2.2. Một số thuật toán phát hiện luật kết hợp .............................................. 35 2.2.1. Thuật toán AIS .............................................................................. 35 2.2.2. Thuật toán SETM .......................................................................... 36 2.2.3. Thuật toán Apriori ......................................................................... 38 2.2.4. Thuật toán Apriori-TID................................................................. 44 2.2.5. Thuật toán Apriori-Hybrid ............................................................ 46 2.2.6. Thuật toán PARTITION ............................................................... 47 2.2.7. Sinh các luật kết hợp từ tập mục phổ biến ................................... 48 Chƣơng 3. ỨNG DỤNG PHÁT HIỆN LUẬT KẾT HỢP KHAI PHÁ DỮ LIỆU QUẢN LÝ SINH VIÊN....................................................... 52 3.1. Đặt vấn đề ............................................................................................ 52 3.2. Xây dựng chương trình demo thuật toán Apriori ứng dụng phát hiện luận kết hợp trong CSDL quản lý sinh viên ......................... 54 3.2.1. Các bước tiến hành khai phá dữ liệu quản lý sinh viên ................ 54 3.2.2. Xây dựng bảng cơ sở dữ liệu để khai phá ..................................... 54 3.2.3. Chương trình demo ....................................................................... 57 3.2.4. Một số kết quả thử nghiệm ........................................................... 58 KẾT LUẬN .......................................................................................................................... 64 TÀI LIỆU THAM KHẢO ............................................................................................... 65 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv DANH MỤC CÁC CHỮ VIẾT TẮT Ký hiệu Diễn giải supp: Độ hỗ trợ (support) conf: Độ tin cậy (confidence) minsup: Ngưỡng độ hỗ trợ tối thiểu mincof: Ngưỡng độ tin cậy tối thiểu SQL: Structured Query Language KDD: Kownledge Discovery in Database FI: Frenquent Itemset MFI: Maximally Frequent Itemset CSDL: Cơ sở dữ liệu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v DANH MỤC CÁC BẢNG Bảng 2.1. Giao dịch mua hàng ........................................................................ 30 Bảng 2.2. Tính độ hỗ trợ cho các tập hợp chứa các mặt hàng ........................ 30 Bảng 2.3. Các luật kết hợp và độ tin cậy của chúng ....................................... 31 Bảng 2.4. Ma trận biểu diễn cơ sở dữ liệu ...................................................... 43 Bảng 2.5. Vector biểu diễn nhị phân cho tập 1 thuộc tính .............................. 43 Bảng 2.6. Vector biểu diễn nhị phân cho các tập 2 thuộc tính ....................... 43 Bảng 2.7. Vector biểu diễn nhị phân cho các tập 3 thuộc tính ....................... 44 Bảng 2.8. Vector biểu diễn nhị phân cho các tập 4 thuộc tính ....................... 44 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vi DANH MỤC CÁC HÌNH VẼ Hình 1.1. Cấu trúc kho dữ liệu .......................................................................... 8 Hình 1.2. Quy trình phát hiện tri thức ............................................................. 12 Hình 1.3. Mẫu kết quả với phương pháp cây quyết định ................................ 15 Hình 3.1. Sơ đồ khai phá dữ liệu quản lý sinh viên ........................................ 54 Hình 3.2. Bảng cơ sở dữ liệu khai phá ............................................................ 56 Hinh 3.3. Giao diện chính của chương trình demo ......................................... 57 Hình 3.4. Giao diện “Thao tác với CSDL” ..................................................... 58 Hình 3.5. Kết quả khai phá lần thứ 1 .............................................................. 59 Hình 3.6. Kết quả thử nghiệm lần thứ 2.......................................................... 60 Hình 3.7. Kết quả thử nghiệm lần thứ 3.......................................................... 61 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 MỞ ĐẦU Một trong những ứng dụng quan trọng nhất của công nghệ thông tin trong đời sống là giúp giải quyết các bài toán quản lý. Kể từ khi máy tính điện tử trở thành một công cụ lao động quan trọng thì một trong những nhu cầu đầu tiên là lưu trữ, tìm kiếm và xử lý số liệu thống kê. Đến nay, các cơ sở dữ liệu đã trở nên khổng lồ và người ta mong muốn kho dữ liệu đó cần được khai thác hiệu quả hơn trên nhiều bình diện. Trong những năm gần đây, khai phá dữ liệu (Data mining) đã trở thành một trong những hướng nghiên cứu lớn nhất của lĩnh vực khoa học máy tính và công nghệ thông tin. Khai phá dữ liệu đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực kinh doanh và đời sống khác nhau: marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet… Việc khai phá dữ liệu từ kho dữ liệu có nhiều hướng tiếp cận. Các bài toán chủ yếu trong khai thác dữ liệu là: Khai thác chuỗi, khai thác web, đặc biệt là việc phát hiện luật kết hợp (association rules mining) và việc gom cụm (clustering), phân lớp (classification) dữ liệu,... Trong đó, phát hiện luật kết hợp là một trong những nội dung quan trọng của khai phá dữ liệu và là một lĩnh vực nghiên cứu nhiều triển vọng với khả năng ứng dụng cao vào thực tế. Vì tất cả nhưng lí do trên mà tôi đã chọn đề tài luận văn: “Phát hiện luật kết hợp ứng dụng trong cơ sở dữ liệu quản lý sinh viên” làm chủ đề nghiên cứu của mình. Mục đích của luận văn là nghiên cứu những vấn đề cơ bản về phát hiện luật kết hợp, một số thuật toán khai phá dữ liệu đã được giới thiệu. Trên cơ sở đó áp dụng vào một bài toán cụ thể là cài đặt chương trình phát hiện luật kết hợp từ cơ sở dữ liệu quản lý sinh viên nhằm rút ra những kết luận hữu ích cho quá trình đào tạo và quản lý sinh viên. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 Với mục tiêu đó, luận văn được trình bày trong 3 chương: Chương 1: Tổng quan về cơ sở dữ liệu và khai phá dữ liệu Chương 2: Phát hiện luật kết hợp Chương 3: Phát hiện luật kết hợp trong cơ sở dữ liệu quản lý sinh viên Ngoài phần tổng hợp những kiến thức về khai phá dữ liệu, các thuật toán phát hiện luật kết hợp, luận văn cũng đã trình bày kết quả thử nghiệm qua một bài toán cụ thể để minh họa. Để có được kết quả này tôi đã nhận được sự quan tâm, động viên, giúp đỡ rất nhiều của các Thầy giáo, Cô giáo trong Khoa Công nghệ thông tin Đại học Thái Nguyên cũng như của bạn bè, đồng nghiệp, đặc biệt là sự chỉ bảo tận tình của TS. Vũ Mạnh Xuân và sự nỗ lực của bản thân, đến nay tôi đã hoàn thành đề tài. Tuy nhiên trong quá trình làm việc, mặc dù đã cố gắng, nỗ lực hết sức nhưng không thể tránh khỏi thiếu sót, em kính mong nhận được sự chỉ bảo của các thầy cô để đề tài được hoàn thiện hơn. Tôi xin chân thành cảm ơn ! Thái Nguyên, ngày 29 tháng 09 năm 2011 Học viên Lê Xuân Lượng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Chƣơng 1 TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU Chương này trình bày những nét khái quát về cơ sở dữ liệu, kho dữ liệu và một số phương pháp khai phá dữ liệu. 1.1. Một số khái niệm về cơ sở dữ liệu (CSDL) 1.1.1. Cơ sở dữ liệu Cơ sở dữ liệu (Database) là một hệ thống các thông tin có cấu trúc được lưu trữ trên các thiết bị lưu trữ thông tin thứ cấp (như băng từ, đĩa từ ...) để có thể thỏa mãn yêu cầu khai thác thông tin đồng thời của nhiều người sử dụng hay nhiều chương trình ứng dụng với nhiều mục đích khác nhau. Như vậy đặc trưng của cơ sở dữ liệu là: - Giảm sự trùng lặp thông tin xuống mức thấp nhất và do đó bảo đảm được tính nhất quán và toàn vẹn dữ liệu. - Đảm bảo dữ liệu có thể được truy xuất theo nhiều cách khác nhau. - Khả năng chia sẻ thông tin cho nhiều người sử dụng và nhiều ứng dụng khác nhau. Các loại cơ sở dữ liệu [2] - Cơ sở dữ liệu dạng file: dữ liệu được lưu trữ dưới dạng các file có thể là text, ascii, *.dbf. Tiêu biểu cho cơ sở dữ liệu dạng file là *.mbd Foxpro - Cơ sở dữ liệu quan hệ: dữ liệu được lưu trữ trong các bảng dữ liệu gọi là các thực thể, giữa các thực thể này có mối liên hệ với nhau gọi là các quan hệ, mỗi quan hệ có các thuộc tính, trong đó có một thuộc tính là khóa chính. Các hệ quản trị hỗ trợ cơ sở dữ liệu quan hệ như: MS SQL server, Oracle, MySQL... - Cơ sở dữ liệu hướng đối tượng: dữ liệu cũng được lưu trữ trong các bản dữ liệu nhưng các bảng có bổ sung thêm các tính năng hướng đối tượng như lưu trữ thêm các hành vi, nhằm thể hiện hành vi của đối tượng. Mỗi bảng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 xem như một lớp dữ liệu, một dòng dữ liệu trong bảng là một đối tượng. Các hệ quản trị có hỗ trợ cơ sở dữ liệu quan hệ như: MS SQL server, Oracle, Postgres. - Cơ sở dữ liệu bán cấu trúc: dữ liệu được lưu dưới dạng XML, với định dạng này thông tin mô tả về đối tượng thể hiện trong các tag. Đây là cơ sở dữ liệu có nhiều ưu điểm do lưu trữ được hầu hết các loại dữ liệu khác nhau nên cơ sở dữ liệu bán cấu trúc là hướng mới trong nghiên cứu và ứng dụng. Với sự giúp sức của công nghệ thông tin và truyền thông còn người đã tạo ra những hệ thống thông tin được tổ chức dưới dạng CSDL ở tất cả các ngành nghề lĩnh vực trong xã hội, phục vụ nhiều mục đích khác nhau như: Hệ thống thông tin địa lý GIS, hệ thống thông tin tài chính, ngân hàng, quản lý kinh doanh, quản lý điều hành… Các thông tin có tổ chức này được quản lý, khai thác qua một hệ thống phần mềm khai thác hoặc Hệ quản trị cơ sở dữ liệu 1.1.2. Hệ quản trị cơ sở dữ liệu Hệ quản trị cơ sở dữ liệu (Database Management System): là phần mềm hay hệ thống được thiết kế để quản trị một cơ sở dữ liệu. Cụ thể, các chương trình thuộc loại này hỗ trợ khả năng lưu trữ, sửa chữa, xóa và tìm kiếm thông tin trong một cơ sở dữ liệu (CSDL). Có rất nhiều loại hệ quản trị CSDL khác nhau: từ phần mềm nhỏ chạy trên máy tính cá nhân cho đến những hệ quản trị phức tạp chạy trên một hoặc nhiều siêu máy tính. Qua nhiều năm phát triển, hệ quản trị CSDL ngày nay rất phong phú và đa dạng được xây dựng trên các mô hình dữ liệu khác nhau như: - Mô hình cơ sở dữ liệu quan hệ - Mô hình CSDL phân tán - Mô hình CSDL hướng đối tượng - Mô hình CSDL suy diễn… Tuy nhiên, đa số hệ quản trị CSDL trên thị trường đều có một đặc điểm chung là sử dụng ngôn ngữ truy vấn theo cấu trúc mà tiếng Anh gọi là Structured Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 Query Language (SQL). Các hệ quản trị CSDL phổ biến được nhiều người biết đến là MySQL, Oracle, PostgreSQL, SQL Server, DB2, Infomix,... Phần lớn các hệ quản trị CSDL kể trên hoạt động tốt trên nhiều hệ điều hành khác nhau như Linux, Unix và MacOS ngoại trừ SQL Server của Microsoft chỉ chạy trên hệ điều hành Windows. 1.2. Tổ chức và khai thác cơ sở dữ liệu truyền thống Việc dùng các phương tiện tin học để tổ chức và khai thác các cơ sở dữ liệu đã được phát triển từ những năm 60. Từ đó cho đến nay, rất nhiều cơ sở dữ liệu đã được tổ chức, phát triển và khai thác ở mọi quy mô và ở khắp các lĩnh vực hoạt động của con người và xã hội. Theo như đánh giá cho thấy, lượng thông tin trên thế giới cứ sau 20 tháng lại tăng gấp đôi. Kích thước và số lượng cơ sở dữ liệu thậm chí còn tăng nhanh hơn. Năm 1989, tổng số cơ sở dữ liệu trên thế giới vào khoảng 5 triệu, hầu hết đều là các cơ sở dữ liệu cỡ nhỏ được phát triển trên DBaseIII. Với sự phát triển mạnh mẽ của công nghệ điện tử tạo ra các bộ nhớ có dung lượng lớn, bộ xử lý tốc độ cao cùng với các hệ thống mạng viễn thông, người ta đã xây dựng các hệ thống thông tin nhằm tự động hóa mọi hoạt động kinh doanh của mình. Điều này đã tạo ra một dòng dữ liệu tăng lên không ngừng vì ngay từ các giao dịch đơn giản nhất như một cuộc gọi điện thoại, kiểm tra sức khỏe, sử dụng thẻ tín dụng,… đều được ghi vào trong máy tính. Cho đến nay, con số ày đã trở nên khổng lồ, bao gồm các cơ sở dữ liệu cực lớn cỡ gigabytes và thậm chí terabytes lưu trữ các dữ liệu kinh doanh, ví dụ như dữ liệu thông tin khách hàng, dữ liệu lịch sử các giao dịch, dữ liệu bán hàng, dữ liệu các tài khoản, các khoản vay, sử dụng vốn,… Nhiều hệ quản trị cơ sở dữ liệu mạnh với các công cụ phong phú và thuận tiện đã giúp con người khai thác có hiệu quả các nguồn tài nguyên dữ liệu. Mô hình cơ sở dữ liệu quan hệ và ngôn ngữ vấn đáp chuẩn (SQL) đã có vai trò hết sức quan trọng trong việc tổ chức và khai thác các cơ sở dữ liệu đó. Cho đến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 nay, không một tổ chức nào là không sử dụng các hệ quản trị cơ sở dữ liệu và các hệ công cụ báo cáo, ngôn ngữ hỏi đáp nhằm khai thác các cơ sở dữ liệu phục vụ cho hoạt động tác nghiệp của mình. 1.3. Kho dữ liệu (data warehouse) Cùng với việc tăng không ngừng khối lượng dữ liệu, các hệ thống thông tin cũng được chuyên môn hóa, phân chia theo các lĩnh vực ứng dụng như: Quản lý, sản xuất, tài chính, buôn bán thị trường,... Như vậy, bên cạnh chức năng khai thác dữ liệu có tính chất tác nghiệp, sự thành công trong mọi lĩnh vực không còn là năng suất của các hệ thống thông tin nữa mà là tính linh hoạt và sẵn sàng đáp lại những yêu cầu trong thực tế, CSDL cần đem lại những “tri thức” hơn là chính những dữ liệu đó. Các quyết định cần phải có càng nhanh càng tốt và phải chính xác dựa trên những dữ liệu sẵn có trong khi khối lượng dữ liệu cứ sau 20 tháng lại tăng gấp đôi làm ảnh hưởng đến thời gian ra quyết định cũng như khả năng hiểu hết được nội dung dữ liệu. Lúc này các mô hình CSDL truyền thống và ngôn ngữ SQL đã cho thấy không có khả năng thực hiện công việc này. Để lấy được những thông tin có tính “tri thức” trong khối dữ liệu khổng lồ này, người ta đã đi tìm những kỹ thuật có khả năng hợp nhất các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển đổi thành một tập hợp các cơ sở dữ liệu ổn định, có chất lượng, chỉ được sử dụng riêng cho một vài mục đích nào đó. Các kỹ thuật đó được gọi chung là kỹ thuật tạo kho dữ liệu (data warehousing) và môi trường các dữ liệu đó được gọi là các kho dữ liệu. 1.3.1. Đinh nghĩa kho dữ liệu Kho dữ liệu là một môi trường có cấu trúc các hệ thống thông tin, cung cấp cho người dùng các thông tin khó có thể truy nhập hoặc biểu diễn trong các CSDL tác nghiệp truyền thống, nhằm mục đích hỗ trợ việc ra quyết định Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 mang tính lịch sử hoặc hiện tại. Theo W.H.Inmon, có thể định nghĩa kho dữ liệu như sau: “Một kho dữ liệu là một tập hợp dữ liệu tích hợp hướng chủ đề có tính ổn định, thay đổi theo thời gian nhằm hỗ trợ cho việc ra quyết định. Nói cách khác, một kho dữ liệu bao gồm: - Một hoặc nhiều công cụ để chiết xuất dữ liệu từ bất kỳ dạng cấu trúc dữ liệu nào. - Cơ sở dữ liệu tích hợp hướng chủ đề ổn định được tổng hợp từ các dữ liệu bằng cách lập bảng dữ liệu của dữ liệu.” Một kho dữ liệu có thể được coi là một hệ thống thông tin với những thuộc tính sau: - Là một cơ sở dữ liệu được thiết kế có nhiệm vụ phân tích, sử dụng các dữ liệu từ các ứng dụng khác nhau. - Hỗ trợ cho một số người dùng có liên quan với các thông tin liên quan. - Là dữ liệu chỉ đọc. - Nội dung của nó được cập nhật thường xuyên theo cách thêm thông tin. - Chứa các dữ liệu lịch sử và hiện tại để cung cấp các xu hướng thông tin. - Chứa các bảng dữ liệu có kích thước lớn. - Một câu hỏi thường trả về một tập kết quả liên quan đến toàn bộ bảng và các liên kết nhiều bảng. 1.3.2. Cấu trúc của kho dữ liệu Cấu trúc kho dữ liệu được xây dựng dựa trên hệ quản trị CSDL quan hệ, có chức năng giống như một kho lưu trữ thông tin trung tâm. Trong đó, dữ liệu tác nghiệp và phần xử lý được tách riêng khỏi quá trình xử lý kho dữ liệu. Kho lưu trữ trung tâm được bao quanh bởi các thành phần được thiết kế để làm cho kho dữ liệu có thể hoạt động, quản lý và truy nhập được từ người dùng đầu cuối cũng như từ các nguồn dữ liệu [10]. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 Hệ thống phân phối thông tin Các công cụ hỏi đáp, báo cáo MetaData Các công cụ OLAP Chiết xuất dữ liệu Làm sạch dữ liệu Nạp dữ liệu. Data Mart Các công cụ khai phá dữ liệu Kho dữ liệu trong DBMS Dữ liệu nguồn Các công cụ trợ giúp và các ứng dụng Hình 1.1. Cấu trúc kho dữ liệu Như trên Hình 1.1 cho thấy, kho dữ liệu bao gồm 7 thành phần: - Dữ liệu nguồn (là các ứng dụng tác nghiệp hoặc các kho dữ liệu tác nghiệp) và các công cụ chiết xuất, làm sạch và chuyển đổi dữ liệu. - Kho dữ liệu về dữ liệu (MetaData) - Các kỹ thuật xây kho - Kho dữ liệu thông minh hay dữ liệu theo chủ đề (Data marts): là nơi các dữ liệu được khoanh vùng theo chủ đề đến một giới hạn nào đó và có thể được thay đổi cho phù hợp với nhu cầu của từng bộ phận người dùng. Với các kho dữ liệu này, cũng có thể xây dựng một kho dữ liệu theo cách tiếp cận từng giai đoạn kế tiếp, nghĩa là với một tập hợp các kho dữ liệu thông minh, ta tạo ra một kho dữ liệu; ngược lại, một kho dữ liệu có thể được phân tích thành nhiều kho dữ liệu thông minh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 - Các công cụ vấn đáp (query), báo cáo (reporting), phân tích trực tiếp (OLAP) và khai phá dữ liệu (data mining). Đây chính là các cách khai thác kho dữ liệu để đem lại những “tri thức” hơn là đem lại chính những dữ liệu thô. Điểm mạnh và yếu của các kỹ thuật này ta sẽ phân tích kỹ hơn ở những phần sau. - Quản trị kho dữ liệu. - Hệ thống phân phối thông tin. 1.3.3. Mục đích của việc xây dựng kho dữ liệu Mục tiêu chính của kho dữ liệu nhằm đáp ứng các tiêu chuẩn cơ bản: - Phải có khả năng đáp ứng mọi yêu cầu về thông tin của người sử dụng. - Hỗ trợ để các nhân viên của tổ chức thực hiện tốt, hiệu quả công việc của mình, ví dự như: có những quyết định hợp lý, nhanh và bán được nhiều hàng hơn, năng suất cao hơn, thu được lợi nhuận cao hơn,… - Giúp cho tổ chức xác đinh, quản lý và điều hành các dự án, các nghiệp vụ một các hiệu quả và chính xác. - Tích hợp dữ liệu và siêu dữ liệu từ nhiều nguồn khác nhau. Muốn đạt được những yêu cầu trên thì kho dữ liệu phải: - Tăng chất lượng dữ liệu bằng các phương pháp làm sạch và tinh lọc. - Tổng hợp và kết nối dữ liệu - Đồng bộ hoá các nguồn dữ liệu với kho dữ liệu. - Phân định và đồng nhất các hệ quản trị CSDL tác nghiệp như là các công cụ chuẩn để phục vụ cho kho dữ liệu. - Quản lí siêu dữ liệu (metadata) - Cung cấp thông tin tích hợp, tóm tắt hoặc được liên kết, tổ chức theo các chủ đề. Một số lợi ích của việc xây dựng kho dữ liệu trong nhiều lĩnh vực có thể kể đến như sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 * Đối với quản lý nhà nước: - Giúp các nhà lãnh đạo đưa ra những quyết định mang tính chiến lược để phát triển kinh tế xã hội. - Giúp người lãnh đạo quản lý, chỉ đạo một cách chính xác và kịp thời. - Định hướng phát triển kinh tế xã hội mang tính chiến lược. * Đối với doanh nghiệp: - Lợi ích tiềm ẩn trong đầu tư. - Lợi nhuận trong cạnh tranh. - Tăng tính hiệu quả trong việc đưa ra quyết định đầu tư tài chính. * Đối với nghiên cứu khoa học: Tìm ra các quy luật tự nhiên, vật lý, sinh học, tội phạm học... từ những dữ liệu thống kê, thu thập qua điều tra khảo sát. * Đối với việc đào tạo và phát triển nguồn nhân lực: - Tìm ra su hướng phát triển của tương lại - Tìm ra nhu cầu của việc học tập, sở trường của từng học viên để có kế hoạch, chiến lược bố trí giảng viên, tổ chức lớp học,... - Định hướng đào tạo Tuy nhiên kho dữ liệu mới chỉ là cách khai thác với kỹ thuật cao để đưa ra các dữ liệu tinh và chính xác hơn chứ chưa đưa ra được dữ liệu “tri thức”. Hơn nữa, kích thước quá lớn và tính chất phức tạp của kho dữ liệu làm cho nó rất khó có thể được sử dụng cho những mục đích như đưa ra các giả tuyết từ các thông tin mà chương trình ứng dụng cung cấp. Trước đây, kỹ thuật học máy thường được sử dụng để tìm ra những giả thuyết từ các thông tin dữ liệu thu thập được. Tuy nhiên, thực nghiệm cho thấy chúng thể hiện khả năng rất kém khi áp dụng với các tập dữ liệu lớn trong kho dữ liệu này. Phương pháp thống kê tuy ra đời đã lâu nhưng không có gì cải tiến để phù hợp với sự phát triển của dữ liệu. Đây chính là lý do tại Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 sao một khối lượng lớn dữ liệu vẫn chưa được khai thác và thậm chí được lưu trữ chủ yếu trong các kho dữ liệu không trực tuyến (off-line). Điều này tạo nên một lỗ hổng lớn trong việc hỗ trợ phân tích và tìm hiểu dữ liệu, tạo ra khoảng cách giữa việc tạo ra dữ liệu và việc khai thác các dữ liệu đó.Trong khi đó, càng ngày người ta càng nhận thấy rằng, nếu được phân tích thông minh thì dữ liệu sẽ là một nguồn tài nguyên quý giá trong cạnh tranh trên thương trường. Giới tin học đã đáp ứng lại những thách thức trong thực tiễn cũng như trong nghiên cứu khoa học bằng cách đã đưa ra một phương pháp mới đáp ứng cả nhu cầu trong khoa học cũng như trong hoạt động thực tiễn. Đó chính là công nghệ Khai phá dữ liệu (data mining). 1.4. Khai phá dữ liệu 1.4.1. Khái niệm Khai phá dữ liệu là một khái niệm ra đời vào những năn cuối của thập kỷ 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). 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 (regularities) 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 (Kownledge 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. 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 (pattern) (hay các mô hình) từ dữ liệu. 1.4.2. Các bước của quá trình phát hiện tri thức (KDD) Quy trình phát hiện tri thức thường tuân theo các bước sau: [4] Bước thứ nhất: Hình thành và xác định bài toán. Bước này tìm hiểu lĩnh vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ cần phải Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 hoàn thành. Điều này sẽ quyết định cho việc rút ra được 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à bản chất của dữ liệu Bước thứ hai: Thu thập và tiền xử lý dữ liệu: Tiến hành thu thập và xử lý thô, còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (làm sạch dữ liệu), xử lý việc thiếu dữ liệu (làm giàu dữ liệu), biến đổi dữ liệu 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ộ qui trình phát hiện tri thức do dữ liệu được lấy từ nhiều nguồn khác nhau, không đồng nhất… có thể gây ra các nhầm lẫn. Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và rời rạc hoá. Hình thành và Định nghĩa bài toán Thu thập và Tiền xử lý dữ liệu Khai phá dữ liệu Rút ra các tri thức Phân tích và kiểm định kết quả Sử dụng các tri thức phát hiện đƣợc Hình 1.2. Quy trình phát hiện tri thức Bước thứ ba: Khai phá dữ liệu, rút ra các tri thức: Trích ra các mẫu hoặc/ và các mô hình ẩn dưới các dữ liệu. Giai đoạn này rất quan trọng, bao gồm các công đoạn như: chức năng, nhiệm vụ và mục đích của khai phá dữ liệu, dùng phương pháp khai phá nào? Thông thường, các bài toán khai phá dữ liệu bao gồm: các bài toán mang tính mô tả - đưa ra tính chất chung nhất của dữ liệu, các bài toán dự báo - bao gồm cả việc phát hiện các suy diễn dựa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 trên dữ liệu hiện có. Tuỳ theo bài toán xác định được mà ta lựa chọn các phương pháp khai phá dữ liệu cho phù hợp. Bước thứ tư: Sử dụng các tri thức phát hiện được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. 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. Các kết quả của quá trình phát hiện tri thức có thể được đưa và ứng dụng trong các lĩnh vực khác nhau. Do các kết quả có thể là các dự đoán hoặc các mô tả nên chúng có thể được đưa vào các hệ thống hỗ trợ ra quyết định nhằm tự động hoá quá trình này. Tóm lại: KDD là một quá trình kết xuất ra tri thức từ kho dữ liệu mà trong đó khai phá dữ liệu là công đoạn quan trọng nhất. 1.4.3. Một số phương pháp khai phá dữ liệu [4] Khai phá dữ liệu là lĩnh vực mà con người luôn tìm cách đạt được mục đích sử dụng thông tin của mình. Quá trình khai phá dữ liệu là quá trình phát hiện mẫu, trong đó phương pháp khai phá dữ liệu để tìm kiếm các mẫu đáng quan tâm theo dạng xác định. Có thể kể ra đây một vài phương pháp như: Sử dụng công cụ truy vấn, xây dựng cây quyết định, dựa theo khoảng cách (K-láng giềng gần), giá trị trung bình, phát hiện luật kết hợp,… Các phương pháp trên có thể được phỏng theo và được tích hợp vào các hệ thống lai để khai phá dữ liệu theo thống kê trong nhiều năm nghiên cứu. Tuy nhiên, với dữ liệu rất lớn trong kho dữ liệu thì các phương pháp này cũng đối diện với thách thức về mặt hiệu quả và quy mô. 1.4.3.1. Phương pháp suy diễn và quy nạp Một cơ sở dữ liệu là một kho thông tin nhưng các thông tin quan trọng hơn cũng có thể được suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để thực hiện việc này là suy diễn và quy nạp. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn