Tài liệu Một số phương pháp khai phá dữ liệu và ứng dụng trong bài toán lập thời khoá biểu

ĐẠI HỌC QUỐC GIA HÀNỘI KHOA CÔNG NGHỆ Ngô Văn Bình Mét sè ph-¬ng ph¸p khai ph¸ d÷ liÖu vµ øng dông trong bµi to¸n lËp thêi kho¸ biÓu LUẬN VĂN THẠC SĨ HÀ NỘI – 2004 ĐẠI HỌC QUỐC GIA HÀNỘI KHOA CÔNG NGHỆ Ngô Văn Bình Mét sè ph-¬ng ph¸p khai ph¸ d÷ liÖu vµ øng dông trong bµi to¸n lËp thêi kho¸ biÓu Chuyên ngành : Công nghệ thông tin Mã số : 1.01.10 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. VŨ ĐỨC THI Hà Nội - 2004 1 MỤC LỤC MỞ ĐẦU ................................................................................................................................. 3 CHƢƠNG 1. TỔNG QUAN .................................................................................................... 6 1.1. Tổng quan về cơ sở dữ liệu và khai phá dữ liệu. ............................................................ 6 1.1.1. Tổ chức và khai thác cơ sở dữ liệu truyền thống .................................................... 6 1.1.2. Khai phá dữ liệu và quá trình phát hiện tri thức. ..................................................... 7 1.2. Kho dữ liệu ................................................................................................................. 10 1.2.1. Sự cần thiết của kho dữ liệu ................................................................................. 10 1.2.2. Định nghĩa kho dữ liệu. ....................................................................................... 12 1.2.3. So sánh Kho dữ liệu và hệ quản trị cơ sở dữ liệu truyền thống. ............................ 14 1.2.4. So sánh hệ thống cơ sở dữ liệu tác nghiệp và hệ thống kho dữ liệu. ...................... 15 1.2.5. Dữ liệu trong Kho dữ liệu. ................................................................................... 17 1.2.6. Kiến trúc kho dữ liệu. .......................................................................................... 18 1.2.7. Ba mô hình của Kho dữ liệu. ................................................................................ 22 1.2.8. Hƣớng tiếp cận đề nghị khi phát triển Kho dữ liệu [9]. ......................................... 23 1.2.9. Từ Kho dữ liệu đến khai phá dữ liệu. ................................................................... 23 CHƢƠNG 2. KHAI PHÁ DỮ LIỆU....................................................................................... 26 2. 1. Giới thiệu khai phá dữ liệu. ........................................................................................ 26 2.1.1. Khai phá dữ liệu là gì ? ........................................................................................ 26 2.1.2. Động cơ thúc đẩy dùng khai phá dữ liệu. ............................................................. 26 2.2. Các ứng dụng của khai phá dữ liệu: ............................................................................. 27 2.2.1. Phân tích cơ sở dữ liệu và trợ giúp ra quyết định: ................................................. 27 2.2.2. Các ứng dụng khác. ............................................................................................. 28 2.3. Khai phá dữ liệu trong quá trình phát hiện tri thức ....................................................... 29 2.4. Khai phá dữ liệu và tin tức kinh doanh ........................................................................ 31 2.5. Kiến trúc điển hình của hệ thống khai phá dữ liệu. ...................................................... 31 2.6. Khai phá dữ liệu nơi hội tụ của rất nhiều kiến thức: ..................................................... 32 2.7. Trọng tâm chính trong khai phá dữ liệu. ...................................................................... 32 2.8. Những vấn đề không cần dùng khai phá dữ liệu .......................................................... 33 2.9. quá trình khai phá dữ liệu. ........................................................................................... 34 2.9.1. Truy cập và chuẩn bị dữ liệu. ............................................................................... 34 2.9.2. Quá trình khái phá dữ liệu. ................................................................................... 37 2.10. Các nhiệm vụ chính của khai phá dữ liệu ................................................................... 37 2.11. Các thành phần của giải thuật khai phá dữ liệu. ......................................................... 39 CHƢƠNG 3. CÁC PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU TRỰC QUAN .......................... 40 3.1. Quan sát các hoạt động không theo chủ quan............................................................... 40 3.2. Trực quan và đòi hỏi của nhận thức ............................................................................. 41 3.3. Vẽ sơ đồ dữ liệu trên lƣợc đồ trực quan. ...................................................................... 42 3.3.1. Thuật toán xác định vị trí [6] ................................................................................ 42 3.3.2. Điều khiển sự xuất hiện của các đối tƣợng trong các thể hiện. .............................. 45 3.3.3. Làm cho các hiển thị có thể hiểu đƣợc. ................................................................ 45 3.4. Những cách tiếp cận phân tích. .................................................................................... 46 3.4.1. Phân tích đặc điểm cấu trúc ................................................................................. 46 3.4.2. Phân tích cấu trúc mạng ....................................................................................... 48 3.4.3. Phân tích những mẫu thời gian. ............................................................................ 52 3.4.4. Thiết lập các lớp mẫu thời gian. ........................................................................... 52 2 CHƢƠNG 4. CÁC PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU THÔNG DỤNG. ...................... 54 4.1. Phƣơng pháp thống kê. ................................................................................................ 54 4.1.1. Phƣơng pháp thống kê. ........................................................................................ 54 4.1.2. Khi nào thì sử dụng phân tích thống kê: ............................................................... 55 4.2. Phƣơng pháp cây quyết định và luật. ........................................................................... 56 4.2.1. Phƣơng pháp cây quyết định và luật. .................................................................... 56 4.2.2. Khi nào dùng cây quyết định................................................................................ 58 4.3. Các luật kết hợp .......................................................................................................... 58 4.3.1. Luật kết hợp......................................................................................................... 58 4.3.2. Khi nào dùng các luật kết hợp .............................................................................. 59 4.4. Mạng Nơ ron. .............................................................................................................. 59 4.4.1. Mạng Nơ ron. ...................................................................................................... 59 4.4.2. Khi nào sử dụng phƣơng pháp học không có thầy. ............................................... 61 4.5. Giải thuật di truyền ..................................................................................................... 61 4.5.1. Giải thuật di truyền. ............................................................................................. 61 4.5.2. Khi nào sử dụng giải thuật Di truyền. ................................................................... 62 4.6. Các phƣơng pháp khai phá dữ liệu khác. ..................................................................... 62 4.6.1. Phân nhóm và phân đoạn. .................................................................................... 62 4.6.2. Phƣơng pháp suy diễn và quy nạp ........................................................................ 63 4.6.3. Các phƣơng pháp dựa trên mẫu. ........................................................................... 63 4.6.4. Khai phá dữ liệu văn bản. .................................................................................... 63 4.7. lựa chọn phƣơng pháp khai phá dữ liệu. ...................................................................... 64 4.8. ƣu thế và khó khăn của khai phá dữ liệu. ..................................................................... 64 4.8.1. Ƣu thế: ................................................................................................................ 64 4.8.2. Khó khăn. ............................................................................................................ 66 CHƢƠNG 5. GIẢI THUẬT DI TRUYỀN VÀ BÀI TOÁN LẬP THỜI KHOÁ BIỂU. .......... 70 5.1. Tổng quan giải thuật di truyền cổ điển. ........................................................................ 70 5.1.1. Ý tƣởng của giải thuật .......................................................................................... 70 5.1.2 Cấu trúc của GA cổ điển ....................................................................................... 71 5.2. GA và bài toán lập thời khoá biểu ở trƣờng cao đẳng công nghiệp hà nội. ................... 75 5.2.1. Giới thiệu ............................................................................................................ 75 5.2.2. Các định nghĩa. .................................................................................................... 77 5.2.3. Giải thuật di truyền cho thời khoá biểu................................................................. 79 5.2.4. Thiết kế cơ sở dữ liệu........................................................................................... 90 5.2.5. Chƣơng trình lập thời khoá biểu. .......................................................................... 93 KẾT LUẬN............................................................................................................................ 96 TÀI LIỆU THAM KHẢO ...................................................................................................... 98 PHỤ LỤC ............................................................................................................................ 100 3 MỞ ĐẦU Trong suốt hơn 40 năm phát triển, Cơ sở dữ liệu đã có những bƣớc tiến vô cùng quan trọng trong lịch sử Công nghệ thông tin. Từ mô hình Cơ sở dữ liệu quan hệ do E. Codd đề xuất từ những năm 60, các ứng dụng công nghệ thông tin đã thực sự biến việc lƣu trữ dữ liệu trở thành lƣu trữ thông tin. Ngày nay, bất cứ một tổ chức nào, với bất kỳ một mô hình hay quy mô nào cũng đều có những nhu cầu về lƣu trữ và khai thác thông tin. Khái niệm thông tin ở đây bao gồm cả thông tin về nội tại của tổ chức và thông tin về môi trƣờng (environment) và tổ chức hoạt động. Với những tiến bộ vƣợt bậc trong nghiên cứu lý thuyết cũng nhƣ cài đặt thực tế, các hệ quản trị cơ sở dữ liệu đã trở thành nền tảng, là xƣơng sống trong hoạt động của các tổ chức. Chúng ta có thể thấy những nhà cung cấp hệ quản trị cơ sở dữ liệu hàng đầu trên thế giới nhƣ ORACLE, Microsoft, IBM, Informix... Hệ quản trị cơ sở dữ liệu ngày nay không còn đơn thuần chỉ là một cơ cấu cho phép lƣu trữ số liệu (data) mà còn kèm theo đó là các công cụ (tools), tiện ích (utilities) hay các phƣơng pháp luận (methodologies) để chuyển đổi số liệu thành thông tin. Tập tất cả các công cụ do ngƣời dùng phát triển hoặc do các nhà cung cấp phần mềm tung ra để phục vụ cho mục đích hoạt động của tổ chức, đƣợc tối ƣu theo những yêu cầu nghiệp vụ của tổ chức đƣợc gọi là các ứng dụng hỗ trợ xử lý giao dịch trực tuyến (OLTP - Online Transactional Processing). Cao hơn nữa, với các yêu cầu kết xuất thông tin cô đọng hơn, nhằm hỗ trợ các yêu cầu phân tích của các nhà lãnh đạo, các nhà lập chiến lƣợc của một tổ chức, các ứng dụng cũng nhƣ nền tảng phát triển Xử lý phân tích trực tuyến (OLAP - Online Analytical Processing) ra đời. Lúc này dữ liệu đƣợc lƣu trữ và kết xuất dƣới dạng hƣớng chủ đề, phù hợp với những yêu cầu phân tích ra quyết định cụ thể. Trong thời đại ngày nay, con ngƣời đang sống trong một môi trƣờng xã hội phát triển cao với sự bùng nổ về dữ liệu. Khi trình độ xã hội càng phát triển thì kiến thức con ngƣời càng đƣợc phát triển đồng thời lƣợng dữ liệu cũng gia tăng theo mức dộ đó. Mặc dù trong môi trƣờng tràn ngập dữ liệu, nhƣng con ngƣời dƣờng nhƣ vẫn thiếu thông tin. Theo thống kê của một số tổ chức uy tín thì chỉ có 2%-3% lƣợng dữ liệu đƣợc chuyển thành thông tin có ích. Khi xã hội càng phát triển, lƣợng thông tin cần càng nhiều thì công việc tổ chức, khai phá dữ liệu ngày càng khó khăn. Nhƣ vậy, trong quá trình sử dụng và khai thác thông tin, ngƣời ta nhận thấy 4 rằng có rất nhiều tri thức còn tiềm ẩn trong dữ liệu. Đó có thể là các khuynh hƣớng kinh doanh, là các dự báo thị trƣờng, cũng có thể là mối quan hệ giữa các trƣờng hay nội dung dữ liệu... mà con ngƣời không hình dung ra đƣợc khi tiến hành mô hình hoá các hệ thống (system modelling). Vấn đề đặt ra là làm thế nào để khai thác thôngtin một cách có hiệu và dùng các phƣơng pháp nào để khai thác thôngtin. Để trả lời câu hỏi đó luận văn sẽ nghiên cứu về Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database) và cụ thể bài toán Khai phá dữ liệu (DataMining) làm trung tâm nghiên cứu. Nghiên cứu này mới chỉ dừng lại ở việc tìm hiểu các phƣơng pháp khai phá dữ liệu trong thực tế để có thể dựa vào đó nhƣ một tài liệu thám khảo, cuối cùng đƣa ra giải pháp để giải quyết bài toán lập thời khoá biểu – một bài toán NP khó. Với thời gian nghiên cứu chƣa đủ dài cũng nhƣ trình độ và tầm hiểu biết chƣa thực sự sâu sắc, chắc chắn việc nghiên cứu có nhiều thiếu sót và chƣa chặt chẽ. Nhƣng qua đây, em xin chân thành cảm ơn PGS.TS. Vũ Đức Thi Chủ tịch hội đồng Khoa học, Viện phó Viện Công nghệ Thông tin – Viện Khoa học Việt nam ngƣời đã tận tình hƣớng dẫn và giúp đỡ em trong toàn bộ quá trình nghiên cứu. Em cũng xin đƣợc bày tỏ lòng biết ơn đến các Thầy, Cô khoa Công nghệ - Đại học Quốc gia Hà nội đã tạo mọi điều kiện làm việc, học tập tốt nhất cũng nhƣ những ý kiến quý báu trong thời gian học Cao học giúp em có thể hoàn thành nghiên cứu này. Tôi xin đƣợc cảm ơn bạn bè, gia đình những ngƣời đã giúp đỡ tôi rất nhiều trong việc hoàn thành luận văn. Những đóng góp chính của luận văn:  Luận văn đã trình bày một phƣơng pháp khai phá dữ liệu bằng các công cụ trực quan và các phƣơng pháp thông dụng, trong các phƣơng pháp có trình bày rõ nên sử dụng nhƣ thế nào và sử dụng trong trƣờng hợp nào.  Luận văn trình bày về kho dữ liệu và cách sử dụng Kho dữ liệu. 5  Luận văn xây dựng phƣơng pháp giải quyết bài toán lập thời khoá biểu dựa trên giải thuật di truyền, một trong các phƣơng pháp khai phá dữ liệu. Nội dung của luận văn: Phần mở đầu của luận văn giới thiệu nội dung nghiên cứu, tính cấp thiết của đề tài và những đóng góp chính của luận văn. Chƣơng 1 giới thiệu các khái niệm cơ bản về khai phá dữ liệu, Kho dữ liệu và ứng dụng. Chƣơng 2 giới thiệu về khai phá dữ liệu nói chung, các ứng dụng của khai phá dữ liệu. Chƣơng 3 giới thiệu các phƣơng pháp khai phá dữ liệu trực quan. Chƣơng 4 giới thiệu các phƣơng pháp khai phá dữ liệu thông dụng, cách sử dụng và các trƣờng hợp nên dùng chúng. Chƣơng 5 nói về giải thuật di truyền, ứng dụng giải thuật di truyền vào bài toán lập thời khoá biểu, xây dựng bài toán lập thời khoá biểu. Phần kết luận nêu các đóng góp của luận văn và các hƣớng nghiên cứu tiếp theo. Phần phụ đƣa danh sách các modul chính trong chƣơng trình. 6 CHƢƠNG 1. TỔNG QUAN 1.1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU. 1.1.1. Tổ chức và khai thác cơ sở dữ liệu truyền thống Ngay từ những năm 60, việc dùng các phƣơng tiện tin học để tổ chức khai thác các cơ sở dữ liệu (CSDL) đã đƣợc phát triển. Cho đến nay, rất nhiều CSDL đã đƣợc xây dựng, phát triển và khai thác ở khắp các lĩnh vực hoạt động của con ngƣời và xã hội. Hiện nay, lƣợng thông tin trên thế giới cứ sau 24 tháng lại tăng gấp đôi. Ngày nay, với sự phát triển mạnh mẽ của công nghệ bán dẫn, tạo ra các hệ thống với dung lƣợng lớn, bộ xử lý tốc độ cao cùng và các công nghệ truyền hiện đại, ngƣời ta đã xây dựng các hệ thống thông tin hiện đại, trợ giúp mọi hoạt động kinh doanh, điều đó đã tạo ra khối dữ liệu khổng lồ, cần xử lý, nó 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. Nhiều hệ quản trị CSDL với các công cụ mạnh ra đời trợ giúp cho con ngƣời khai thác có hiệu quả các nguồn tài nguyên dữ liệu. Mô hình CSDL quan hệ và ngôn ngữ truy vấn cấu trúc (SQL-Structure Query Language) đã có vai trò hết sức quan trọng trong việc tổ chức và khai thác các CSDL đó. Cho đến nay, không một tổ chức kinh tế nào là không sử dụng các hệ quản trị CSDL và các hệ công cụ báo cáo, ngôn ngữ hỏi đáp nhằm khai thác các CSDL , phục vụ cho hoạt động tác nghiệp của mình. Theo sự phát triển đi lên của các hệ thống cơ sở dữ liệu, các hệ thống thông tin cũng đƣợc chuyên môn hoá, phát triển chuyên sâu theo các lĩnh vực ứng dụng nhƣ sản xuất, kinh doanh, tài chính, thị trƣờng.v.v.. 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ự ứng dụng trong kinh doanh không còn là dữ liệu đơn thuần của các hệ thống nữa mà cơ sở dữ liệu cần đem lại những "tri thức" hơn là chính những dữ liệu đó. Trong xã hội hiện nay, các hoạt động kinh doanh cần có các quyết định nhanh và 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 tăng nhanh 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. Điều này dẫn đến các mô hình CSDL truyền thống và ngôn ngữ hỏi không có khả năng đáp ứng đƣợc yêu cầu này. Để lấy đƣợc những thông tin có tính "tri thức" trong khối dữ 7 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 dữ liệu 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 đƣợc sử dụng chỉ 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ó đƣợc gọi là các kho dữ liệu. Tuy nhiên, việc sử dụng các cách khai thác dữ liệu theo khai thác truyền thống mới chỉ dừng lại ở cách khai thác dữ liệu với các 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". Kho dữ liệu đƣợc sử dụng để hỗ trợ cho phân tích trực tuyến (OLAP) có khả năng phân tích dữ liệu, xác định xem giả thuyết đúng hay sai nhƣng không thể đƣa ra các giả thuyết. Kỹ thuật học máy có thể đƣa ra giả thuyết, nhƣng trên các tập dữ liệu lớn trong kho dữ liệu thì chúng thể hiện khả năng rất kém. phƣơng pháp thống kê cũng không có cải tiến gì để phù hợp với sự phát triển của dữ liệu. Đây là lý do tại sao vẫn còn khối lƣợng lớn dữ liệu vẫn chƣa đƣợc khai thác và thậm chí đƣợc lƣu chủ yếu trong các kho dữ liệu không trực tuyến. Đ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. một công nghệ mới đƣợc nghiên cứu, đá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. 1.1.2. Khai phá dữ liệu và quá trình phát hiện tri thức. Việc sử dụng cơ sở dữ liệu vào hoạt động của một tổ chức đã đƣợc phát triển trong vòng 60 năm trở lại đây. Với dữ liệu đƣợc thu thập trong suốt quá trình hoạt động của một tổ chức, một nhu cầu đƣợc đặt ra là tìm kiếm và khai thác tri thức từ những dữ liệu đó. Đó chính là xuất phát điểm của bài toán Phát hiện tri thức từ cơ sở dữ liệu. Ngƣời ta nhận thấy rằng có rất nhiều tri thức mà chúng ta không lƣờng trƣớc đang còn tiềm ẩn trong dữ liệu, nhiệm vụ của chúng ta là phát hiện, khám phá các tri thức đó, phục vụ cho những nhu cầu sử dụng thông tin cao hơn, ví dụ nhƣ trong các hệ chuyên gia hay hệ hỗ trợ quyết định. Khai phá dữ liệu đƣợc định nghĩa nhƣ là quá trình chắt lọc hay khai phá tri thức từ một lƣợng lớn dữ liệu. Một ví dụ trực quan thƣờng đƣợc dùng là việc khai thác vàng từ đá và cát, một ngƣời khai thác muốn chắt lọc đƣợc vàng từ đá và cát 8 hơn là việc tìm phải đá hoặc cát. Thuật ngữ data mining ám chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ một lƣợng lớn các dữ liệu thô. Có nhiều thuật ngữ hiện đƣợc dùng cũng có nghĩa tƣơng tự với từ data mining nhƣ knowledge mining (khai phá tri thức), knowledge extraction (chắt lọc tri thức), data/ patern analysis (Phân tích dữ liệu/ mẫu), data archaeology (khảo cổ dữ liệu), data dredging (nạo vét dữ liệu). Nhiều ngƣời thƣờng nhầm lẫn khái niệm khai phá dữ liệu với các thuật ngữ khác là khai phá tri thức – Knowledge Discovery in Databases (KDD). Khai phá dữ liệu chỉ là một bƣớc trong quá trình KDD. KDD gồm có các quá trình theo thứ tự nhƣ sau [15]: 1. Làm sạch dữ liệu: Loại bỏ nhiễu và các dữ liệu không cần thiết. 2. Tích hợp dữ liệu: Các nguồn dữ liệu khác nhau tích hợp lại. 3. Lựa chọn dữ liệu: Các dữ liệu có liên quan tới quá trình phân tích đƣợc lựa chọn từ cơ sở dữ liệu. 4. Chuyển đổi dữ liệu: Các dữ liệu đƣợc chuyển đổi sang các dạng phù hợp cho quá trình xử lý. 5. Khai phá dữ liệu: Là một trong nhƣng bƣớc quan trọng nhất, trong đó sử dụng những phƣơng pháp thông minh để chắt lọc ra những mẫu dữ liệu. 6. Ước lượng mẫu: Quá trình đánh giá các kết quả tìm đƣợc thông qua các độ đo nào đó. 7. Biểu diễn tri thức: Quá trình này sử dụng các kĩ thuật biểu diễn và thể hiện trực quan các tri thức cho ngƣời dùng. Khai phá dữ liệu là giai đoạn chủ yếu của quá trình Phát hiện tri thức từ CSDL. Công đoạn khai phá tri thức đƣợc thực hiện sau các quá trình thu thập và tinh lọc dữ liệu, có nghĩa là chỉ tìm các mẫu hình tri thức (pattern) có ý nghĩa trên tập dữ liệu có hy vọng chứ không phải là trên toàn bộ CSDL nhƣ các phƣơng pháp thống kê trƣớc đây. Vì vậy khai phá dữ liệu bao gồm việc thử tìm mô hình phù hợp với dữ liệu và tìm kiếm các mẫu hình tri thức từ dữ liệu theo mô hình đó. Mặc dù mẫu hình 9 có thể tìm đƣợc từ bất kỳ một CSDL nào nhƣng chỉ những mẫu phù hợp với mục đích tìm kiếm mới đƣợc gọi là tri thức. Ta sẽ có những hàm số để đánh giá các tiêu chí mẫu nhƣ mới, có lợi, đáng xem xét. Độ mới của mẫu hình phụ thuộc vào khung phạm vi quy chiếu, có thể đối với hệ thống hoặc đối với ngƣời dùng. Ví dụ với dữ liệu của một công ty, quá trình Khai phá dữ liệu tìm ra đƣợc một luật nhƣ “Lợi tức thu đƣợc giảm vào mùa thu ở vùng phía Bắc”, đối với hệ thống thì rất mới, trƣớc kia chƣa hề có nhƣng bất cứ một cán bộ lập kế hoạch nào cũng nhận ra đƣợc điều này qua các báo cáo tài chính. Tính hữu dụng của mẫu có thể đo đƣợc qua sự liên quan đến mục đích tìm kiếm. Với một cán bộ phụ trách bảo trì máy tính ở công ty thì luật trên không có giá trị, mặc dù là mới đối với anh ta. Có thể qua công đoạn khai phá tri thức có rất nhiều mẫu đƣợc lấy ra nhƣng không phải mẫu nào cũng có giá trị, có thể là mới, hữu ích nhƣng lại tầm thƣờng, đặc biệt là khi áp dụng các kỹ thuật dựa trên thống kê. Do đó luôn phải có các tiêu chí và các hàm đánh các mẫu đáng xem xét, không tầm thƣờng. Tóm lại, Khai phá dữ liệu thực ra có thể coi là một quá trình xác định mẫu từ các Datawarehouse, sử dụng các kỹ thuật sẵn có nhƣ học máy, nhận dạng, thống kê, phân loại... và các kỹ thuật đƣợc phát triển bởi ngành nghiên cứu trí tuệ nhân tạo nhƣ Mạng nơ-ron nhân tạo (neutral network), các thuật toán di truyền (generic algorithm), quy nạp luật (rule induction)... Ta có thể xét đến một số bài toán chính đối với nghiên cứu về Khai phá dữ liệu [9]:  Bài toán phân lớp (classification): Tìm một ánh xạ (phân loại) từ một mẫu dữ liệu vào một trong các lớp cho trƣớc.  Bài toán hồi quy (regression): Tìm một ánh xạ hồi quy từ một mẫu dữ liệu vào một biến dự đoán có giá trị thực  Bài toán lập nhóm (clustering): Là việc mô tả chung để tìm ra các tập xác định hữu hạn các nhóm hay các loại để mô tả dữ liệu.  Bài toán tổng kết (summarization): Là việc đi tìm kiếm một mô tả chung tóm tắt cho một tập con dữ liệu. 10 1.2. KHO DỮ LIỆU 1.2.1. Sự cần thiết của kho dữ liệu Việc áp dụng công nghệ thông tin trong môi trƣờng nghiệp vụ hiện nay đã mang lại những hiệu quả to lớn, đặc biệt khi công nghệ ngày càng đƣợc phát triển và hoàn thiện, mở rộng qui mô áp dụng từ những ứng dụng đơn lẻ đến các hệ thống thông tin cỡ lớn. Các hệ thống thông tin từ chỗ chỉ xử lý đơn thuần các công việc hàng ngày thì tiến tới đáp ứng những yêu cầu ở mức độ cao hơn: các nhà quản lý điều hành không những biết đƣợc công việc đang diễn ra nhƣ thế nào mà còn nắm bắt đƣợc cái gì sẽ xảy ra sau đó, có nghĩa là thông tin phải mang tính phân tích và hệ thống thông tin có khả năng hỗ trợ quyết định. Tuy nhiên việc xây dựng một hệ thống thông tin nhƣ thế vấp phải một số hạn chế về mặt kỹ thuật, đặc biệt là khi kích thƣớc cũng nhƣ độ phức tạp của môi trƣờng thông tin tăng lên. Những hệ thống thông tin xây dựng theo phƣơng pháp truyền thống không làm hài lòng ngƣời sử dụng và ngay cả những nhà quản lý hệ thống thông tin. Vê phía ngƣời sử dụng, các khó khăn gặp phải là[9]: 1. Không thể tìm thấy dữ liệu cần thiết: - Dữ liệu rải rác ở rất nhiều hệ thống với các giao diện và công cụ khác nhau gây mất nhiều thời gian chuyển từ hệ thống này sang hệ thống khác. - Có thể có nhiều nguồn thông tin đáp ứng đƣợc đòi hỏi nhƣng chúng lại có những khác biệt và rất khó phát hiện thông tin nào là đúng và cần thiết. Không thể lấy ra đƣợc dữ liệu cần thiết. - Thƣờng xuyên phải có chuyên gia trợ giúp dẫn đến công việc dồn đống. Có những loại thông tin không thể lấy ra dƣợc nếu không mở rộng khả năng làm việc của hệ thống có sẵn. Không thể hiểu đƣợc dữ liệu tìm thấy. - Mô tả dữ liệu nghèo nàn và thƣờng xa rời với thuật ngữ nghiệp vụ quen thuộc. 2. Không thể sử dụng được dữ liệu tìm thấy: - Kết quả tìm thấy thƣờng không đáp ứng về bản chất dữ liệu và thời gian tìm kiếm. 11 - Dữ liệu phải chuyển đổi bằng thủ công vào môi trƣờng làm việc của ngƣời sử dụng. 3. Các vấn đề về hệ thống thông tin- Phát triển các chương trình khác nhau là không đơn giản : - Một chức năng đƣợc thể hiện ở rất nhiều chƣơng trình, nhƣng việc tổ chức và sử dụng lại nó là khó khăn do hạn chế về kỹ thuật. - Chuyển đổi dữ liệu từ các khuôn dạng tác nghiệp khác nhau để phù hợp với ngƣời sử dụng là rất khó khăn. Duy trì những chƣơng trình này gặp rất nhiều vấn đề. - Mỗi thay đổi ở một ứng dụng sẽ ảnh hƣởng đến tất cả các ứng dụng khác có quan hệ. - Thông thƣờng sự phụ thuộc lẫn nhau giữa các chƣơng trình không rõ ràng hoặc không xác định đƣợc. - Do sự phức tạp của công việc chuyển đổi cũng nhƣ toàn bộ quá trình bảo trì dẫn đến mã nguồn của các chƣơng trình trở nên hết sức phức tạp. Khối lƣợng dữ liệu lƣu trữ tăng rất nhanh. - Không kiểm soát đƣợc khả năng chồng chéo dữ liệu trong các môi trƣờng thông tin dẫn đến khối lƣợng dữ liệu tăng nhanh. quản trị dữ liệu phức tạp. - Thiếu những định nghĩa chuẩn, thống nhất về dữ liệu dẫn đến việc mất khả năng kiểm soát môi trƣờng thông tin. - Một thành phần dữ liệu tồn tại ở nhiều nguồn khác nhau. Giải pháp cho những vấn đề nêu trên là xây dựng kho dữ liệu. Kho dữ liệu ra đời ở những nƣớc công nghiệp phát triển, nơi mức độ cạnh tranh rất cao. Do sức ép cạnh tranh, các tổ chức (kinh doanh) cần phải quản lý phân tích tốt hoạt động hàng ngày và đƣa ra các quyết định đúng đắn, kịp thời cho các hoạt động trong tƣơng lai. Thông tin trở thành mặt hàng quan trọng cần đƣợc quản lý và khai thác. Kho dữ liệu ra đời đáp ứng đòi hỏi lƣu trữ và khai thác thông tin đó. Kho dữ liệu giúp tăng hiệu quả và sức mạnh cạnh tranh. Kho dữ liệu ra đời và phát triển đƣợc cũng nhờ phát triển mạnh mẽ của công nghệ thông tin ở các mặt: 12 - Khả năng lƣu trữ và xử lý khối lƣợng lớn thông tin. - Sự phát triển nhanh chóng của mạng máy tính, đặc biệt là mô hình tính toán Client/server Sự phát triển của các công cụ xây dựng chƣơng trình ứng dụng: các ngôn ngữ lập trình, các công cụ trợ giúp xây dựng và thiết kế CASE, các hệ quản trì CSDL tiên tiến... Với nhu cầu và khả năng trên, những dự án đầu tiên về Kho dữ liệu đã đƣợc xây dựng trong khoảng 1984-1988. Cho đến nhƣng năm 1994, ở các nƣớc phát triển, các dự án về Kho dữ liệu xây dựng mạnh mẽ. Cho tới nay, Kho dữ liệu vẫn là một thị trƣờng rất phát triển. Ban đầu các dự án về Kho dữ liệu đƣợc xây dựng chủ yếu ở các tổ chức lớn (nhà băng lớn, hãng hàng không,... ). Tại Việt nam, do nhu cầu tăng cao hiệu quả quản lý, do xu hƣớng hoá nhập vào thế giới với sức ép cạnh tranh ngày càng tăng từ nƣớc ngoài, do nỗ lực xây dựng công nghệ thông tin thành ngành công nghiệp mũi nhọn, các dự án về xây dựng những Kho dữ liệu đang dƣợc dần triển khai ở các cơ quan lớn của nhà nƣớc. Và cùng với việc quan tâm ngày càng tăng tới hệ trợ giúp quyết định, Kho dữ liệu với vai trò là cơ sở hạ tầng cung cấp dữ liệu cho hệ trợ giúp quyết định ngày càng trở nên quan trọng. 1.2.2. Định nghĩa kho dữ liệu. Kho dữ liệu có thể đƣợc định nghĩa bằng nhiều cách khác nhau nhƣng không nghiêm ngặt lắm, ta có thể định nghĩa kho dữ liệu nhƣ sau [9]: Kho dữ liệu (Data Warehouse-DW) là một tập hợp các dữ liệu có tính hướng chủ đề, tích hợp, gắn với thời gian và ổn định, được thiết kế cho việc hỗ trợ ra quyết định. Kho dữ liệu có thể gọi là một công trình xây dựng tổng hợp các dữ liệu từ những nguồn dữ liệu không đồng nhất, bao gồm các dữ liệu quá khứ và dữ liệu hiện tại, báo cáo phân tích và hỗ trợ quyết định. Kho dữ liệu do vậy thƣờng rất lớn, tới hàng trăm hay thậm chí hàng nghìn Gigabyte. Theo W. H. Inmon và R. D. Hackathom [9] định nghĩa : Kho dữ liệu là một sưu tập dữ liệu trợ giúp ra quyết định trong quản lý, với các đặc điểm: Hướng chủ đề (subject - oriented), Tích hợp(integrated), 13 Đa dạng thời gian (time-variant) Không hay thay đổi (nonvolatile). Cụ thể hơn : Hướng chủ đề : Trong Data Warehouse dữ liệu đƣợc mô hình hoá và thiết kế xoay quanh chủ đề chính của công trình cần xây dựng nhƣ khách hàng, sản phẩm, bán hàng…hơn là đi vào các giao tác riêng biệt hoặc các xử lý hàng ngày. Cung cấp cái nhìn đơn giản và súc tích xoay quanh các chủ đề bằng cách ngăn chặn các dữ liệu không hữu ích cho việc ra quyết định. Tích hợp : Trong Kho dữ liệu, các thông tin cần phải: - Sạch - Hợp lệ - Kết hợp đúng đắn. Dữ liệu đƣợc tích hợp từ nhiều nguồn hỗn tạp nhƣ: cơ sở dữ liệu quan hệ, các file, các bản ghi giao tác. Công nghệ làm sạch và tích hợp dữ liệu đƣợc áp dụng: các dữ liệu đƣa vào có thể không kiên định, không cùng kiểu mã hoá, không cùng đơn vị, do đó chúng phải đƣợc chuyển đổi khi đƣa vào kho. Đa dạng thời gian : Trong môi trƣờng kinh doanh cách quyết định là trực tuyến, do đó các dữ liệu cần phải chính xác tại thời điểm ra quyết định. Đây không phải là trƣờng hợp cho Kho dữ liệu, dữ liệu là xác đáng tại một vài thời điểm nhƣng không nhất thiết là hoàn toàn đúng. Điển hình, dữ liệu chỉ hoàn toàn chính xác tại thời điểm nạp vào Kho dữ liệu. Nhƣ vậy, mỗi dữ liệu trong Kho dữ liệu chỉ đúng tại một thời điểm nhất định vì vậy trong các thuộc tính thƣờng có thời gian. Dữ liệu lƣu trữ trong khoảng thời gian từ 5- 10 năm. Dữ liệu có thể đƣợc xem nhƣ những ảnh chụp liên tiếp trong thời gian dài. Không hay thay đổi : trong thực tế việc cập nhập dữ liệu (chèn, xoá, sửa) thƣờng xuyên xảy ra trên cơ sở các bản ghi. Kho dữ liệu không cập nhập nhƣ vậy, dữ liệu cập nhập vào kho dựa trên lịch đƣợc xử lý bởi ngƣời dùng. Theo cách tiếp cận này, dữ liệu chủ yếu đƣợc nạp vào một lần, sau đó chỉ đƣợc truy nhập để lấy ra. 14 Việc cập nhật dữ liệu ít xảy ra. Các kỹ thuật liên quan tới: phục hồi dữ liệu, đảm bảo toàn vẹn tham chiếu phát hiện và giải quyết tắc nghẽn,... thƣờng không cần thiết. 1.2.3. So sánh Kho dữ liệu và hệ quản trị cơ sở dữ liệu truyền thống. 1.2.3.1. Vấn đề tích hợp cơ sở dữ liệu hỗn tạp. * Phƣơng pháp truyền thống: 1. Xây dựng hoán đổi hoặc vật dàn xếp trên đỉnh của cơ sở dữ liệu hỗn tạp. 2. Áp dụng các điều khiển Query: - Khi một client yêu cầu một site, siêu từ điển đƣợc sử dụng để chuyển query của client thành query thích hợp để tạo site từ các site hỗn tạp, kết quả đƣợc tích hợp vào tập các câu trả lời chung. Vấn đề phức tạp trong lọc thông tin và tranh chấp tài nguyên. *Kho dữ liệu: Sử dụng công cụ update và khả năng thực thi cao. Thông tin từ các nguồn hỗn tạp đƣợc tích hợp cao hơn và đƣợc chứa trong các kho phục vụ cho các truy vấn hoặc các phân tích trực tiếp. 1.2.3.2. Vấn đề hoạt động * Dùng OLTP (on-line transaction processing)- Xử lý các giao tác trực tuyến - Thực hiện nhiệm vụ chính trong CSDL quan hệ truyền thống. - Phục vụ các hoạt đồng hàng ngày: mua, bán, đăng ký, thanh toán, lập bảng lƣơng, báo cáo… * Dùng OLAP (on-line analytical processing) – Xử lý phân tích trực tuyến - Dùng cho các nhiện vụ chính của hệ thống Kho dữ liệu. - Phục vụ phân tích dữ liệu và hỗ trợ ra quyết định. * Sự khác biệt trong khả năng của OLPT và OLAP [9]: OLPT OLAP Nội dung dữ liệu Hiện tại, chi tiết Lịch sử và hợp nhất Thiết kế CSDL Mô hình ER và ứng dụng Mục tiêu và chủ đề 15 OLPT OLAP Tổng quan Hiện tại cục bộ Tiến hoá, tích hợp Xử lý Update Chỉ đọc nhƣng truy vấn không phức tạp Ngƣời sử dụng Chuyên gia công nghệ thông Công nhân có tri thức (Công Chức năng Cách dùng tin nhân bậc cao) Công việc hàng ngày Hỗ trợ ra quyết định thông Có tính lặp đi lặp lại thƣờng Đặc biệt, không dự tính đƣợc trƣớc Truy cập Bằng khoá chính Bằng nhiều cách Đơn vị công việc Các giao tác ngắn và đơn giản Truy vấn phức tạp Số lƣợng bản ghi có 10 1.000.000 thể đƣợc truy cập Số ngƣời dùng Hàng trăm Hàng nghìn Độ lớn CSDL 100MB - GB 100GB – TB Đơn vị đo Số lƣợng giao tác Số lƣợng truy vấn và trả lời 1.2.4. So sánh hệ thống cơ sở dữ liệu tác nghiệp và hệ thống kho dữ liệu. Thông thƣờng, các cơ quan tổ chức trƣớc khi bắt đầu xây dựng Kho dữ liệu đều đã tin học hoá các hoạt động hàng ngày bằng xây dựng các hệ tác nghiệp (Online Transaction Processing - OLTPL). Và nguồn dữ liệu chủ yếu của Kho dữ liệu chính là từ hệ tác nghiệp. Nhưng tại sao lại phải xây dựng kho dữ liệu - một hệ thống tin học mới - khi đã có sẵn một hệ thống tin học là hệ tác nghiệp? Đó là vì tác nghiệp phục vụ cho tự dộng hoá các tác vụ thao tác hàng ngày, còn Kho dữ liệu phục vụ cho môi trƣờng thông tin ra quyết định, Kho dữ liệu đƣợc thiết kế hƣớng trợ giúp quá trình phân tác và ra quyết định, và mang những đặc điểm khác nhƣ sau: 16 Hệ thống tác nghiệp mang tính hướng tác vụ với những đặc điểm chính sau [9]: 1. Trợ giúp các công việc tức thời hàng ngày. 2. Chứa dữ liệu hiện thời, thể hiện trạng thái thực công việc. 3. Các hoạt động xảy ra trong hệ thống thƣờng đơn giản, giới hạn trong phạm vi nhất định, và kết quả gây ra thƣờng là việc cập nhập dữ liệu. 4. Đƣợc tối ƣu hoá cho việc xử lý nhanh các tác vụ định trƣớc, đặc biệt tập trung vào các hoạt động cập nhật. 5. Ngƣời dùng chủ yếu là những ngƣời làm những công việc Ở mức độ chi tiết, cụ thể nhƣ thƣ kí, ngƣời bán hàng,... 6. Thiết kế thƣờng khó hiểu và che dấu với ngƣời dùng. Kho dữ liệu được thiết kế hướng trợ giúp quá trình phân tích và ra quyết định, và mang những đặc điểm khác như sau [9]: 1. Trợ giúp quá trình quản lý và điều khiển công việc. 2. Chứa dữ liệu mang tính lịch sử, thể hiện cách nhìn ổn định của công việc trong một giai đoạn hay tại một thời điểm cụ thể đã qua. 3. Đƣợc tối ƣu hoá cho các câu hỏi truy vấn, chứ không phải các các hoạt động cập nhật. Các câu hỏi có thể đƣợc xác định trƣớc cho tới hoàn toàn không đƣợc xác định trƣớc. 4. Ngƣời dùng chủ yếu là đội ngũ quản lý để hiểu, phân tích, đánh giá và ra quyết định hên quan tới công việc. 5. Phải đƣợc thiết kế dễ hiểu và dễ sử dụng đối với ngƣời dùng. Tóm lại: Kho dữ liệu và cơ sở dữ liệu tác nghiệp có những điểm khác nhau chủ yếu sau : Hướng chủ thể: Kho dữ liệu tổ chức và đƣa ra dữ liệu từ khung nhìn của ngƣời dùng cuối. Còn hầu hết các cơ sở dữ liệu tác nghiệp thì tố chức dữ liệu từ khung nhìn của ứng dụng theo cách làm cho ứng dụng truy cập đƣợc dữ liệu một cách hiệu quả nhất. 17 Quản lý một khối lượng lớn thông tin: hầu hết các Kho dữ liệu chứa các dữ liệu quá khứ, cái thƣờng bị loại bỏ ra bởi các hệ tác nghiệp, do nó không còn cần thiết cho sản phẩm và ứng dụng tác nghiệp. Do phải quản lý một khối lƣợng lớn thông tin nên Kho dữ liệu cũng phải cung cấp các thủ tục phụ phục vụ cho việc tóm tắt và kết hợp nhằm phân loại khối lƣợng dữ liệu khổng lồ nói trên. Chính vì nhu cầu quản lý tất cả các dữ liệu quá khứ để thêm vào dữ liệu hiện tại cho nên Kho dữ liệu lớn hơn nhiều so với cơ sở dữ liệu tác nghiệp. Lưu trữ thông tin trên nhiều phương tiện: Vì khối lƣợng thông tin phải quản lý là rất lớn nên Kho dữ liệu thƣờng lƣu trữ dữ liệu trên nhiều phƣơng tiện khác nhau. Ghép nối nhiều phiên bản của lược đồ cơ sở dữ liệu: Kho dữ liệu phải lƣu trữ và quản lý các thông tin quá khứ. Vì các thông tin quá khứ đó đã đƣợc quản lý ở nhiều thời điểm khác nhau bởi nhiều phiên bản khác nhau của lƣợc đồ cơ sở dữ liệu nên Kho dữ liệu phải tổng hợp các thông tin đó lại.. Tóm tắt và kết hợp thông tin: Mức chi tiết đƣợc thấy trong các thông tin đƣợc lƣu trữ bởi cơ sở dữ liệu tác nghiệp thƣờng rất lớn để ra quyết định. Kho dữ liệu tóm tắt và kết hợp thông tin để đƣa ra theo cách thức mà ngƣời dùng có thể hiểu đƣợc. Tích hợp và liên kết thông tin từ nhiều nguồn dù liệu khác nhau: Vì các tổ chức đã sử dụng nhiều cơ sở dữ liệu và ứng dụng phần mềm khác nhau để quản lý công việc của chúng, Kho dữ liệu cần thiết để thu thập và tổ chức các dữ liệu mà các ứng dụng này đã thu thập đƣợc qua nhiều năm. 1.2.5. Dữ liệu trong Kho dữ liệu. Việc xây dựng Kho dữ liệu là một quá trình kỹ thuật thu thập, quản lý và khai thác tài liệu một cách lợp lý từ nhiều nguồn khác nhau để thiết lập một kho dữ liệu. Nó cung cấp những dữ liêu phù hợp, dễ hiểu cần thiết cho việc quản lý một phần hay toàn bộ công tác nghiệp vụ của một tổ chức. Để xây dựng Kho dữ liệu thì điều đầu tiên cần phải quan tâm là Kho dữ liệu bao gồm những dữ liệu nào. Tuỳ thuộc vào cách xem xét dữ liệu mà ta có 3 cách phân chia các kiểu dữ liệu sau: 18 Phân chia theo ngữ nghĩa của dữ liệu : theo ngữ nghĩa của dữ liệu thì Kho dữ liệu có 3 kiểu dữ liệu [9],[5]: Dữ liệu nghiệp vụ: là dữ liệu mà đƣợc dùng để điều hành và quản lý một công việc hay một tổ chức. Nó phản án hoạt động mà công việc phải tiến hành, phản ánh các đối tƣợng trong thế giới thực nhƣ khách hàng, địa điểm, sản phẩm…Nó đƣợc tạo ra và đƣợc sử dụng nhờ hệ xử lý giao dịch và hệ hỗ trợ quyết định. Dữ liệu thành phẩm: dữ liệu này có ý nghĩa thực chất riêng và giá trị của nó nằm trong nội dung nó biểu đạt chứ không phải nằm trong cái mà nó phản ánh. Dữ liệu thành phẩm đƣợc tạo ra, mua và bán nhƣ bất cứ sản phẩm vật lý nào khác, ví dụ nhƣ phim ảnh và sách báo đƣợc lƣu trữ dƣới dạng số hoá. Siêu dữ liệu: mô tả ý nghĩa của dữ liệu, dùng chỉ để định nghĩa hoặc mô tả dữ liệu nghiệp vụ hoặc dữ liệu thành phẩm. Nó có thể đƣợc định nghĩa nhƣ sau "Siêu dữ liệu (Meta data) là dữ liệu mô tả cấu trúc và ý nghĩa của dữ liệu trong kho dữ liêu nhằm xác định rõ dữ liệu này đƣợc tạo ra, truy nhập và sử dụng nhƣ thế nào. Phân chia theo cấu trúc của dữ liệu: Dữ liệu có thể đƣợc cấu trúc cao, bao gồm các trƣờng hoặc các bản ghi có quan hệ một cách rành mạnh với nhau. Hoặc là phi cấu trúc, nơi mà các kết cấu bên trong rất hay thay đổi, hoặc là có thể nằm giữa hai kiểu trên. Phân chia theo phạm vi của dữ liệu: Dữ liệu có thể là mang tính cá nhân ngƣời chủ của nó có thể thay đổi tuỳ thích. Hoặc là mang tính công cộng - việc sử dụng nó đƣợc chia sẻ cho cả cộng đồng, và mỗi sự thay đổi đói hỏi đƣợc quản lý một cách cẩn thận. 1.2.6. Kiến trúc kho dữ liệu. * Cách nhìn tổng quan về thiết kế Kho dữ liệu. Khi thiết kế Kho dữ liệu ngƣời ta đƣa ra bốn cách nhìn tổng quan nhƣ sau: 1. Cách nhìn từ trên xuống (Top – down): Chia Kho dữ liệu thành các phần có thông tin liên quan mật thiết với nhau. 2. Nguồn dữ liệu: Bỏ đi các thông tin bị lƣu trữ và quản lý bởi hệ điều hành.