Tài liệu Luận án ứng dụng phương pháp hồi quy bayes vào việc dự báo thời tiết

LỜI CAM ĐOAN Tôi xin cam đoan đề tài khoa học “Ứng dụng phương pháp hồi quy Bayes vào việc dự báo thời tiết” này là công trình nghiên cứu của bản thân tôi. Các số liệu và kết quả nghiên cứu trong luận văn này là trung thực, được trích dẫn từ các tài liệu tham khảo như đã trình bày trong luận văn và đã được giáo viên hướng dẫn khoa học thông qua nội dung và đồng ý cho ra bảo vệ trước hội đồng khoa học. Người viết luận văn Nguyễn Thị Thu Hòa MỤC LỤC Trang phụ bìa Lời cam đoan Mục lục Danh mục các từ viết tắt Danh mục các hình vẽ Danh mục các bảng LỜI MỞ ĐẦU ............................................................................................................1 CHƯƠNG I. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ........................................3 1.1. Khái niệm về khai phá dữ liệu (Data mining) ...............................................3 1.2. Kiến trúc của một hệ thống khai phá dữ liệu.................................................3 1.3. Các giai đoạn của quá trình khai phá dữ liệu ................................................4 1.4. Chức năng khai phá dữ liệu ...........................................................................7 1.4.1. Phân lớp (classification) .........................................................................7 1.4.2. Hồi quy (regression) ...............................................................................8 1.4.3. Phân cụm (clustering) .............................................................................8 1.4.4. Tổng hợp (summarization) .....................................................................8 1.4.5. Phân tích sự phát triển và độ lệch (evolution and deviation analysis) ...8 1.5. Một số thuật toán khai phá dữ liệu ................................................................ 9 1.5.1. Phân lớp bằng cây quyết định .................................................................9 1.5.2. Phương pháp gom nhóm K – Means ....................................................26 1.6. Một số ứng dụng của khai phá dữ liệu ........................................................ 27 1.7. Khai phá dữ liệu và một số phần mềm ứng dụng ........................................28 1.7.1. Phần mềm Weka ...................................................................................28 1.7.2. Chương trình dự báo thời tiết eWeather ...............................................29 CHƯƠNG II. GIỚI THIỆU CHUNG VỀ DỰ BÁO THỜI TIẾT VÀ CƠ SỞ LÝ THUYẾT ĐỂ DỰ BÁO THỜI TIẾT .............................................................. 33 2.1. Khái niệm về thời tiết và các phương pháp dự báo thời tiết .......................33 2.1.1. Thời tiết và khí hậu ...............................................................................33 2.1.2. Các phương pháp dự báo thời tiết ......................................................... 33 2.2. Bản đồ thời tiết ............................................................................................ 38 2.2.1. Bản đồ SyNốp .......................................................................................39 2.2.2. 2.3. Bản đồ Faximin .....................................................................................40 Các nhân tố ảnh hưởng đến thời tiết ............................................................ 41 2.3.1. Nhiệt độ không khí trung bình .............................................................. 41 2.3.2. Độ ẩm không khí trung bình .................................................................41 2.3.3. Mây .......................................................................................................42 2.3.4. Mưa .......................................................................................................42 2.4. Cơ sở lý thuyết ............................................................................................. 43 2.4.1. Một số khái niệm cơ bản.......................................................................43 2.4.2. Phát biểu định lý Bayes ........................................................................46 2.4.3. Mạng Bayes (Bayesian Network) ......................................................... 46 2.4.4. Cách xây dựng mạng Bayes..................................................................48 2.4.5. Phân lớp Naive Bayes ...........................................................................49 Chương III. ỨNG DỤNG BAYESIAN ĐỂ XÂY DỰNG CHƯƠNG TRÌNH DỰ BÁO THỜI TIẾT ....................................................................................................52 3.1. Đặt vấn đề .......................................................................................................52 3.2. Phân tích bài toán ............................................................................................ 52 3.3. Hệ thống chương trình ....................................................................................53 3.3.1. Dữ liệu thu thập ........................................................................................ 53 3.3.2. Giao diện chương trình .............................................................................53 3.4. Một số kết quả dự báo thời tiết .......................................................................56 3.5. So sánh kết quả dự đoán và kết quả thực tế ..................................................588 KẾT LUẬN ............................................................................................................. 59 TÀI LIỆU THAM KHẢO PHỤ LỤC DANH MỤC CÁC TỪ VIẾT TẮT Ac: Altocumulus As: Altostratus ASP: Active Server Pages Cb: Cumulonimbus Cc: Cirrocumulus Cs: Cirrostratus CSDL: Cơ sở dữ liệu (Databases) DAG: Directed Acyclic Graph DHTNĐ: Dải hội tụ nhiệt đới GIF: Graphics Interchange Format HTM: Hierarchical Temporal Memory HTML: HyperText Markup Language ID3: Iterative Dichotomiser version 3 IP: Internet Protocol JPEG: Joint Photographic Experts Group KDD: Knowledge Discovery in Databases KPDL: Khai phá dữ liệu KTTV: Khí tượng thủy văn MDL: Minimum Description Length ML: Maximum Likelihood NB: Naive Bayes NBC: Naive Bayes Classifier Ns: Nimbostratus PDF: Portable Document Format POP3: Post Office Protocol version 3 RAMS – VNU: The Regional Atmospheric Modeling System SLIQ: Superived Learning In Quest SMTP: Simple Mail Transfer Protocol SPRINT: Scalable PaRallelization INduction of decision Tree SQL: Structure Query Language Ti (Ci): Cirrus TTXVN: Thông tấn xã Việt Nam VB: Visual Basic WML: Wireless Markup Language XML: Extensible Markup Language DANH MỤC CÁC HÌNH VẼ Hình 1.1. Khai phá tri thức trong cơ sở dữ liệu điển hình .......................................3 Hình 1.2. Mô hình mô tả quá trình khai phá dữ liệu ...............................................5 Hình 2.1. Mây Vũ tích (Cumulonimbus – Cb) ......................................................37 Hình 2.2. Mây Trung tích (Altocumulus - Ac) ......................................................37 Hình 2.3. Mây Vũ tầng (Nimbostratus – Ns) ........................................................ 37 Hình 2.4. Mây Ti tích (Cirrocumulus - Cc) ......................................................... 37 Hình 2.5. Mây tầng tích (Stratocumulus – Sc) ......................................................38 Hình 2.6. Mây Ti (Ci) - (Cirrus) .......................................................................... 38 Hình 2.7. Mây trung tầng (Altostratus – As) ......................................................... 38 Hình 2.8. Bản đồ SyNốp ........................................................................................ 39 Hình 2.9. Mô hình xoáy thuận ............................................................................. 40 Hình 2.10. Mô hình xoáy nghịch ......................................................................... 40 Hình 2.11. Bản đồ thời tiết xoáy thuận ..................................................................40 Hình 3.1. Giao diện giới thiệu chương trình .......................................................... 54 Hình 3.2. Giao diện nhập dữ liệu dự đoán ............................................................. 55 Hình 3.3. Giao diện kết quả chương trình sau khi dự đoán ...................................55 Hình 3.4. Giao diện dự đoán thời tiết của một ngày bất kì trong tháng 12 ...........56 Hình 3.5. Giao diện dự đoán thời tiết của một ngày bất kì trong tháng 10 ...........56 Hình 3.6. Giao diện dự đoán thời tiết của một ngày bất kì trong tháng 2 ............57 Hình 3.7. Giao diện dự đoán thời tiết của một ngày bất kì trong tháng 5 .............57 Hình 3.8. Biểu đồ so sánh kết quả dự đoán và kết quả thực tế…………………..58 DANH MỤC CÁC BẢNG Bảng 1.1. Bảng dữ liệu về thời tiết .. ....................................................................... 12 Bảng 2.1. Bảng xác suất đồng thời ......................................................................... 44 1 LỜI MỞ ĐẦU Trong những năm gần đây, 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à lưu trữ thông tin của các hệ thống thông tin tăng nhanh một cách chóng mặt. Sự bùng nổ 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 để chuyển đổi lượng dữ liệu khổng lồ kia thành các tri thức có ích. Từ đó, các kĩ thuật khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền công nghệ thông tin trên thế giới hiện nay. Quá trình này khai phá dữ liệu giúp người sử dụng thu được những thông tin hữu ích trong nhiều lĩnh vực. Việc khai phá dữ liệu tỏ ra đặc biệt hiệu quả vì từ những số liệu cụ thể, nó sẽ cung cấp thông tin bổ ích cho con người dựa trên những cơ sở khoa học đáng tin cậy. Với những ưu điểm đó, 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 đời sống khác nhau. Hiện nay, khoa học công nghệ phát triển như vũ bão, việc khai phá dữ liệu đang là vấn đề được nhiều nhà quản lí và đầu tư quan tâm bởi lợi ích mà nó mang lại. Nó có khả năng cung cấp các thông tin tiềm ẩn trong các cơ sở dữ liệu lớn mà con người không thể làm được. Luận văn với đề tài “Ứng dụng phương pháp hồi quy Bayes vào việc dự báo thời tiết” khảo sát lĩnh vực khai phá dữ liệu dùng mạng Bayes. Luận văn tập trung vào phương pháp hồi quy Bayes để đi sâu vào việc khai phá dữ liệu từ các thông tin thu thập được để dự báo thời tiết cho những ngày sắp tới. Nội dung của luận văn được trình bày trong 3 chương với các nội dung cơ bản sau: Chương I. Tổng quan về khai phá dữ liệu: Giới thiệu tổng quan về quá trình khai phá dữ liệu, kiến trúc của một hệ thống khai phá dữ liệu, nhiệm vụ chính, các phương pháp khai phá dữ liệu và một số giải thuật khai phá dữ liệu. Chương II. Giới thiệu chung về dự báo thời tiết và cơ sở lý thuyết để dự báo thời tiết: Giới thiệu chung về dự báo thời tiết, các yếu tố ảnh hưởng đến thời tiết và các phương pháp dự báo thời tiết; đồng thời giới thiệu về định lý Bayes, tổng quan về mạng Bayes, cách xây dựng mạng Bayes và thuật toán phân lớp Naive Bayes. Chương III. Ứng dụng mạng Bayes để xây dựng chương trình dự báo thời tiết. 2 Mặc dù đã hết sức nỗ lực, song do thời gian và kinh nghiệm nghiên cứu khoa học còn hạn chế nên không thể tránh khỏi những thiếu sót. Em rất mong nhận được sự góp ý của các thầy cô và bạn bè đồng nghiệp để hiểu biết của mình ngày một hoàn thiện hơn. Qua luận văn này em xin chân thành cảm ơn: TS. Hoàng Thị Lan Giao – Khoa Công nghệ thông tin, trường Đại học Khoa học Huế đã tận tình giúp đỡ, động viên, hướng dẫn em nghiên cứu và hoàn thành luận văn này. Em xin chân thành cảm ơn các thầy cô giáo và các bạn trong khoa công nghệ thông tin đã có những góp ý hữu ích trong quá trình thực hiện bản luận văn. Bên cạnh đó, em cũng vô cùng cảm ơn sự giúp đỡ nhiệt tình và động viên khích lệ của người thân trong gia đình em, bạn bè và đồng nghiệp trong suốt quá trình thực hiện luận văn. Biên Hòa, tháng 9 năm 2013 Người viết luận văn Nguyễn Thị Thu Hòa 3 CHƯƠNG I. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1. Khái niệm về khai phá dữ liệu (Data mining) Khai phá dữ liệu[13] là quá trình khai thác (rút trích) những thông tin tiềm ẩn có tính dự đoán, những thông tin có nhiều ý nghĩa, hữu ích từ những cơ sở dữ liệu lớn, nó được coi như là một bước trong quá trình khám phá tri thức (Knowledge Discovery in Databases – KDD). Khai phá dữ liệu là giai đoạn quan trọng nhất trong tiến trình khám phá tri thức từ cơ sở dữ liệu, các tri thức này có rất nhiều ý nghĩa, là cơ sở hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh. Khai phá dữ liệu là giai đoạn thiết yếu, đây là bước quan trọng và tốn nhiều thời gian nhất của toàn bộ quá trình khám phá tri thức, là bước áp dụng những kỹ thuật khai phá để khai thác, trích xuất thông tin có ích, những mẫu điển hình, những mối liên hệ đặc biệt có nhiều giá trị, mang nhiều ý nghĩa từ dữ liệu. 1.2. Kiến trúc của một hệ thống khai phá dữ liệu Khai phá dữ liệu là quá trình rút trích thông tin bổ ích từ những kho dữ liệu lớn, là quá trình chính trong khai phá tri thức từ cơ sở dữ liệu. Kiến trúc của một hệ thống khai phá dữ liệu[13] có các thành phần như sau: Nguồn[13] Hình 1.1. Khám phá tri thức trong cơ sở dữ liệu điển hình 4 - Cơ sở dữ liệu, kho dữ liệu hoặc lưu trữ thông tin khác: Đây là một hay các tập cơ sở dữ liệu, các kho dữ liệu, các trang tính hay các dạng khác của thông tin được lưu trữ. Các kỹ thuật làm sạch dữ liệu và tích hợp dữ liệu có thể được thực hiện. - Máy chủ cơ sở dữ liệu (Database or Warehouse Server): Máy chủ có trách nhiệm lấy những dữ liệu thích hợp dựa trên những yêu cầu khám phá của người dùng. - Cơ sở tri thức (Knowledge-base): Đây là miền tri thức dùng để tìm kiếm hay đánh giá độ quan trọng của các mẫu kết quả thu được. Tri thức này có thể bao gồm một sự phân cấp khái niệm dùng để tổ chức các thuộc tính hay các giá trị thuộc tính ở các mức trừu tượng khác nhau. - Máy khai phá dữ liệu (Data mining engine): Là một hệ thống khai phá dữ liệu cần phải có một tập các modul chức năng để thực hiện công việc, chẳng hạn như kết hợp, phân lớp, phân cụm. - Modul đánh giá mẫu (Pattern evaluation): Bộ phận tương tác với các modul khai phá dữ liệu để tập trung vào việc duyệt tìm các mẫu đáng được quan tâm. Nó có thể dùng các ngưỡng về độ quan tâm để lọc mẫu đã khám phá được. Cũng có thể modul đánh giá mẫu được tích hợp vào modul khai phá dữ liệu, tùy theo cách cài đặt của phương pháp khai phá dữ liệu được dùng. - Giao diện đồ họa cho người dùng (Graphical user interface): Bộ phận này cho phép người dùng giao tiếp với hệ thống khai phá dữ liệu. Thông qua giao diện này người dùng tương tác với hệ thống bằng cách đặc tả một yêu cầu khai phá hay một nhiệm vụ, cung cấp thông tin trợ giúp cho việc tìm kiếm và thực hiện khai phá thăm dò trên các kết quả khai phá trung gian. Ngoài ra bộ phận này còn cho phép người dùng xem các lược đồ cơ sở dữ liệu, lược đồ kho dữ liệu, các đánh giá mẫu và hiển thị các mẫu trong các khuôn dạng khác nhau. 1.3. Các giai đoạn của quá trình khai phá dữ liệu Quá trình khai phá dữ liệu[13] được trải qua các bước sau: B1: Xác định vấn đề và không gian dữ liệu để giải quyết vấn đề (problem understanding and data understanding). Là 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 hoàn thành. Bước này sẽ quyết định 5 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. B2: Chuẩn bị dữ liệu (data preparation) bao gồm các quá trình: làm sạch dữ liệu (data cleaning), tích hợp dữ liệu (data integration), chọn dữ liệu (data selection), biến đổi dữ liệu (data transformation), bước này thường chiếm nhiều thời gian nhất trong toàn bộ quy trình phát hiện tri thức. Do dữ liệu được lấy từ nhiều nguồn dữ liệu 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 hóa. B3: Khai phá dữ liệu, rút ra các tri thức. Là khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/ và các mô hình ẩ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 trên cơ sở dữ liệu hiện có. Tùy 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. B4: Triển khai (deployment). Là hiểu tri thức đã tìm đượ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 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 vào các lĩnh vực khác nhau của đời sống xã hội. 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 hóa quá trình này. Nguồn[13] Hình 1.2. Mô hình mô tả quá trình khai phá dữ liệu 6 Trong đó: -Làm sạch dữ liệu: Đối với giá trị thiếu, ta có thể thực hiện theo các phương pháp sau: + Bỏ qua các bộ: phương pháp này không phải lúc nào cũng hiệu quả trừ khi các bộ có chứa một số thuộc tính không thực sự quan trọng. + Điền vào các giá trị thiếu bằng tay: phương pháp này thường tốn thời gian và có thể không khả thi cho một tập dữ liệu nguồn lớn với nhiều giá trị bị thiếu. + Sử dụng các giá trị quy ước để điền vào cho giá trị thiếu: thay thế các giá trị thuộc tính thiếu bởi cùng một hằng số quy ước. Tuy vậy điều này cũng có thể khiến cho chương trình khai phá dữ liệu hiểu nhầm trong một số trường hợp và đưa ra các kết luận không hợp lý. + Sử dụng các thuộc tính có nghĩa là để điền vào cho các giá trị thiếu. + Sử dụng các giá trị của các bộ cùng thể loại để thay thế cho giá trị thiếu. + Sử dụng giá trị có tỉ lệ xuất hiện cao để điền vào cho các giá trị thiếu. Điều này có thể xác định bằng phương pháp hồi quy, các công cụ suy luận dựa trên lý thuyết Bayes hay cây quyết định. Đối với dữ liệu nhiễu: Nhiễu dữ liệu là một lỗi ngẫu nhiên hay do biến động của các biến trong quá trình thực hiện, hoặc sự ghi chép nhầm lẫn không được kiểm soát… Để khắc phục điều này ta có thể làm mịn thuộc tính để loại bỏ dữ liệu nhiễu bằng các kỹ thuật làm mịn như binning, hồi quy hay nhóm cụm … -Tích hợp dữ liệu: Trong nhiều bài toán phân tích, chúng ta phải đồng ý rằng nguồn dữ liệu dùng để phân tích không thống nhất. Để có thể phân tích được, các dữ liệu này cần phải được tích hợp, kết hợp thành một kho dữ liệu thống nhất. Về dạng thức, các nguồn dữ liệu có thể được lưu trữ rất đa dạng từ: các cơ sở dữ liệu phổ dụng, các tập tin flat – file, các dữ liệu khối… Việc tích hợp luôn cần các thông tin diễn tả tính chất của mỗi thuộc tính (siêu dữ liệu) như: tên, ý nghĩa, kiểu dữ liệu, miền xác định, các quy tắc xử lý giá trị rỗng, bằng không…Các siêu dữ liệu sẽ được sử dụng để giúp chuyển đổi các dữ liệu. Do vậy bước này cũng liên quan đến quá trình làm sạch dữ liệu. -Biến đổi dữ liệu: 7 Trong phần này các dữ liệu sẽ được biến đổi sang các dạng phù hợp cho việc khai phá dữ liệu. Các phương pháp thường thấy như: + Làm mịn: phương pháp này loại bỏ các trường hợp nhiễu khỏi dữ liệu ví dụ như các phương pháp binning, hồi quy, nhóm cụm. + Tổng hợp: trong đó tổng hợp hoặc tập hợp các hành động được áp dụng trên dữ liệu. Bước này thường được sử dụng để xây dựng một khối dữ liệu cho việc phân tích. + Khái quát hóa dữ liệu, trong đó các dữ liệu mức thấp hoặc thô được thay thế bằng các khái niệm ở mức cao hơn thông qua kiến trúc khái niệm. + Chuẩn hóa, trong đó các dữ liệu của thuộc tính được quy về các khoảng giá trị nhỏ . + Xác định thêm thuộc tính, trong đó các thuộc tính mới sẽ được thêm vào nguồn dữ liệu để giúp cho quá trình khai phá. 1.4. Chức năng khai phá dữ liệu Các kỹ thuật khai phá dữ liệu thực hiện 2 chức năng chính: - Chức năng mô tả: mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong cơ sở dữ liệu, các kỹ thuật này gồm có: phân cụm (Clustering), tổng hợp (Summarization), trực quan hóa (Visualization), phân tích sự phát triển và độ lệch (Evolution and deviation analysis), phân tích luật kết hợp (Association rules),… - Chức năng dự đoán: đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời, các kỹ thuật này gồm có: phân lớp (Classification), hồi quy (Regression), cây quyết định (Decision tree),... 1.4.1. Phân lớp (classification) Là việc xác định một hàm ánh xạ từ một mẫu dữ liệu vào một trong số các lớp đã được biết trước đó. Mục tiêu của thuật toán phân lớp là tìm ra mối quan hệ nào đó giữa thuộc tính dự báo và thuộc tính phân lớp. Như thế quá trình phân lớp có thể sử dụng mối quan hệ này để dự báo cho các mục mới. Các kiến thức được phát hiện biểu diễn dưới dạng các luật theo cách sau: “Nếu các thuộc tính dự báo của một mục thỏa mãn điều kiện của các tiền đề thì mục nằm trong lớp chỉ ra trong kết luận.” 8 1.4.2. Hồi quy (regression) Là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực. Nhiệm vụ của hồi quy tương tự như phân lớp, điểm khác nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không phải là rời rạc. Việc dự báo các giá trị số thường được làm bởi các phương pháp thống kê cổ điển, chẳng hạn như hồi quy tuyến tính. Tuy nhiên, phưong pháp mô hình hóa cũng được sử dụng, ví dụ: cây quyết định. 1.4.3. Phân cụm (clustering) Là việc mô tả chung để tìm ra các tập hay các nhóm, loại mô tả dữ liệu. Các nhóm có thể tách nhau hoặc phân cấp hay gối lên nhau. Có nghĩa là dữ liệu có thể vừa thuộc nhóm này vừa thuộc nhóm khác. Các ứng dụng khai phá dữ liệu có nhiệm vụ phân nhóm như phát hiện tập các khách hàng có phản ứng giống nhau trong CSDL tiếp thị; xác định các quang phổ từ các phương pháp đo tia hồng ngoại, … liên quan chặt chẽ đến việc phân nhóm là nhiệm vụ đánh giá dữ liệu, hàm mật độ xác suất đa biến/ các trường hợp trong CSDL. 1.4.4. Tổng hợp (summarization) Là công việc liên quan đến các phương pháp tìm kiếm một mô tả tập con dữ liệu. Kỹ thuật tổng hợp thường áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động. Nhiệm vụ chính là sản sinh ra các mô tả đặc trưng cho một lớp. Mô tả loại này là một kiểu tổng hợp, tóm tắt các đặc tính chung của tất cả hay hầu hết các mục của một lớp. Các mô tả đặc trưng thể hiện theo luật có dạng sau: “Nếu một mục thuộc về lớp đã chỉ trong tiền đề thì mục đó có tất cả các thuộc tính đã nêu trong kết luận”. Lưu ý rằng luật dạng này có các khác biệt so với luật phân lớp. Luật phát hiện đặc trưng cho lớp chỉ sản sinh ra khi các mục đã thuộc về lớp đó. 1.4.5. Phân tích sự phát triển và độ lệch (evolution and deviation analysis) Nhiệm vụ này tập trung vào khám phá hầu hết sự thay đổi có nghĩa dưới dạng độ đo đã biết trước hoặc giá trị chuẩn, phát hiện độ lệch đáng kể giữa nội dung của tập con dữ liệu thực và nội dung mong đợi. Hai mô hình độ lệch hay dùng là lệch theo thời gian hay lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có ý nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự khác nhau giữa dữ liệu trong hai tập con dữ liệu, ở đây tính cả trường hợp tập con dữ liệu này thuộc tập con kia, nghĩa là xác định dữ liệu trong một nhóm con của đối tượng có khác đáng kể so 9 với toàn bộ đối tượng không? Theo cách này, sai sót dữ liệu hay sai lệch so với giá trị thông thường được phát hiện. Vì những nhiệm vụ này yêu cầu số lượng và các dạng thông tin rất khác nhau nên chúng thường ảnh hưởng đến việc thiết kế và chọn phương pháp khai phá dữ liệu khác nhau. Ví dụ như phương pháp cây quyết định tạo ra được một mô tả phân biệt được các mẫu giữa các lớp nhưng không có tính chất và đặc điểm của lớp. 1.5. Một số thuật toán khai phá dữ liệu 1.5.1. Phân lớp bằng cây quyết định Phân lớp là một lĩnh vực rất quan trọng trong khai phá dữ liệu. Có nhiều giải thuật để xây dựng cây quyết định như: ID3, C4.5, SLIQ, SPRINT,… Tại mỗi nút việc phân chia có thể dựa trên Entropy (ID3, C4.5) hay là dựa trên số đo Gini (SLIQ, SPRINT). Các giải thuật SLIQ, SPRINT sử dụng các tập tin trên đĩa cứng nên có thể mở rộng cho các tập số liệu lớn. Các bước tiến hành phân lớp bao gồm: xây dựng cây quyết định, tỉa cây và rút các luật. Việc phân lớp dựa trên cây quyết định rất thích hợp cho việc khai phá dữ liệu vì cây quyết định có thể được xây dựng khá nhanh. Độ phức tạp của giải thuật chủ yếu phụ thuộc vào giai đoạn tạo cây và bằng O(m*n*logn) với n là số đối tượng (bản ghi) của dữ liệu và m là số các thuộc tính. Một ưu điểm khác là cấu trúc của cây quyết định đơn giản và dễ hiểu. Ngoài ra phân lớp dựa trên cây quyết định còn cho kết quả tương đương và nhiều khi tốt hơn các phương pháp phân lớp khác, từ cây quyết định có thể dễ dàng rút ra các luật. 1.5.1.1. Xây dựng cây quyết định a. Chọn thuộc tính để phân chia Nếu thuộc tính chỉ có thể nhận một trong hai giá trị là đúng hoặc sai thì chúng ta gọi là thuộc tính Boolean. Trường hợp thuộc tính có thể nhận giá trị từ một tập các giá trị đã được phân loại cho trước, chúng ta gọi là thuộc tính category (phân loại). Thuộc tính Boolean là một trường hợp đặc biệt của thuộc tính category. Nếu thuộc tính có giá trị là một số thực thì chúng ta gọi là thuộc tính số. Ví dụ: date {thứ hai, …, chủ nhật} là thuộc tính category lượng mưa [0, ) là thuộc tính số Tại mỗi nút, chúng ta tìm thuộc tính mà cho chúng ta nhiều thông tin nhất (thuộc tính phân chia). Đó là thuộc tính mà khi phân nhánh sẽ tạo ra những tập số 10 liệu con đồng nhất hơn, giúp cho chúng ta hạn chế các bước kiểm tra và phân nhánh tiếp theo. Điều này cũng đảm bảo cho việc tìm ra một cây quyết định đơn giản nhất. Số đo dùng để chọn thuộc tính phân chia tại các nút thường hay được sử dụng đó là số đo Gini hoặc Entropy [9]. Giả sử S (tập các số liệu mẫu dùng để tạo cây) có s mẫu tin, thuộc tính dự đoán có m giá trị phân biệt (như vậy chúng ta có m lớp C i, i=1..m), si là số các mẫu tin trong S thuộc lớp Ci. Số đo Gini được định nghĩa như sau: m I (S1 , S2 ,..., Sm )  1   pi2 i 1 Entropy được định nghĩa như sau: m I (S1 , S2 ,..., Sm )   pi log 2 ( pi ) i 1 với pi là xác suất một mẫu tin bất kì thuộc lớp Ci và được tính bằng si/s Giả sử thuộc tính A có n giá trị khác nhau {a1, a2, …, an}. Thuộc tính A có thể dùng để chia S thành n tập con {S1, S2, …, Sn}, với Sj chứa các mẫu tin trong S có giá trị của thuộc tính A là aj. Nếu A được chọn làm thuộc tính phân chia, thì các tập con sẽ tương ứng với các nhánh mọc từ nút chứa tập S. Gọi s ij là số các mẫu tin của lớp Ci trong tập con Sj. Sau khi phân nhánh theo thuộc tính A n S1 j  ...  Smj j 1 S G ( A)   I ( S1 j ,..., S mj ) G(A) càng nhỏ thì các tập con càng đồng nhất hơn (tức là tập trung vào một lớp nào đó). Như vậy bằng việc phân nhánh theo thuộc tính A, chúng ta đã mã hóa được một lượng thông tin là: Gain( A)  I  s1 , s2 ,..., sm   G( A) Giải thuật ID3, C4.5 tính Gain(A) cho từng thuộc tính. Thuộc tính A nào mà cho Gain(A) lớn nhất sẽ được chọn để phân nhánh tập S. Thuộc tính số: Chúng ta dùng phân chia nhị phân dạng A  v , với v là số thực. Trước tiên chúng ta sắp xếp các giá trị của thuộc tính A theo thứ tự từ nhỏ tới lớn (v1, v2, …, vn). Có n – 1 điểm phân chia là điểm giữa của vi và vi+1. Chúng ta lần lượt xét tất cả các điểm này và chọn điểm cho giá trị Gain(A) lớn nhất. 11 Thuộc tính category: Đặt S(A) là tập các giá trị của thuộc tính A. Một điểm phân chia theo thuộc tính A sẽ có dạng A  S ' , với S '  S . Giả sử A có n giá trị phân biệt, khi đó số tập con của S sẽ là 2n. Với n nhỏ ( n  10 ) thì chúng ta xét tất cả các tập S’ để chọn tập cho giá trị Gain(A) lớn nhất. Nếu n lớn thì chúng ta thực hiện như sau: chúng ta bắt đầu bằng tập S’ trống, sau đó lần lượt thêm vào S’ các giá trị của A sao cho Gain(A) là tốt nhất và chúng ta dừng quá trình này khi việc mở rộng S’ không làm cho Gain(A) lớn lên[18]. Nếu n không lớn thì chúng ta cũng có thể thực hiện việc phân chia bằng cách như sau: chọn một giá trị của tập S(A) sao cho Gain(A) lớn nhất. Tiến hành việc phân chia theo giá trị này. Các giá trị còn lại của S(A) sẽ được lưu lại và sẽ được dùng để tham gia vào việc phân chia các nút con tiếp theo. Cách này có ưu điểm là việc tính toán sẽ đơn giản hơn và chúng ta cũng luôn nhận được các giá trị tốt nhất của thuộc tính A. b. Phép kiểm tra để chọn phép phân chia tốt nhất Độ lợi thông tin (Information gain) - Information gain[9] là đại lượng được sử dụng để chọn lựa thuộc tính với information gain lớn nhất. - Cho P và N là hai lớp và S là một tập dữ liệu có p phần tử lớp P và n phần tử lớp N. - Khối lượng thông tin cần thiết để quyết định một mẫu tùy ý có thuộc về lớp P hay N hay không là: Info( p, n)  Entropy ( p n p p n n , ) log 2  log 2 pn pn pn pn pn pn - Cho các tập {S1, S2 , …, Sv} là một phân hoạch trên tập S, khi sử dụng thuộc tính A. - Cho mỗi Si chứa pi mẫu lớp P và ni mẫu lớp N - Entropy, hay thông tin mong muốn cần thiết để phân lớp các đối tượng trong tất cả các cây con Si là: v Entropy( A)   i 1 pi  ni Info( pi , ni ) pn - Thông tin có được bởi việc phân nhánh trên thuộc tính A là: 12 Gain( A)  Info( p, n)  Entropy ( A) Ví dụ: cho bảng dữ liệu về thời tiết như sau: Bảng 1.1. Bảng dữ liệu thời tiết Nguồn[13] Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Tennis Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát TB Nhẹ Có Mưa Mát TB Mạnh Không Âm u Mát TB Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát TB Nhẹ Có Mưa Ấm áp TB Nhẹ Có Nắng Ấm áp TB Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng TB Nhẹ Có Mưa Ấm áp Cao Mạnh Không Từ bảng dữ liệu trên ta có: • Lớp P: Chơi_tennis = “Có” • Lớp N: Chơi_tennis = “Không” • Thông tin cần thiết để phân lớp một mẫu được cho là: 13 Info( p, n)  Info(9,5)   9 9 5 5 log 2  log 2  0.940 14 14 14 14 + Xét thuộc tính “Quang cảnh” ta có:  “Quang cảnh” = “Nắng”: 2 3 2 2 3 3 Info([2,3])  entropy( , )   log 2 ( )  log 2 ( )  0.971 5 5 5 5 5 5  “Quang cảnh” = “Âm u”: Info([4,0])  entropy(1,0)  1log2 (1)  0log2 (0)  0 Do không có log2(0) nên ta quy ước nó bằng 0  “Quang cảnh” = “Mưa”: 3 2 3 3 2 2 Info([3, 2])  entropy( , )   log 2 ( )  log 2 ( )  0.971 5 5 5 5 5 5  Entropy cho phép phân chia trên thuộc tính “Quang cảnh”: 5 4 5 Info(2,3)  Info(4, 0)  Info(3, 2) 14 14 14 5 4 5   0.971   0   0.971  0.694 14 14 14 Entropy (Quangcanh)  Do đó ta có: Gain(quangcanh)  Info(9,5)  entropy(quangcanh)  0.940  0.694  0.246 + Xét thuộc tính “Độ ẩm” ta có:  “Độ ẩm” = “Cao”: 3 4 3 3 4 4 Info([3, 4])  entropy( , )   log 2 ( )  log 2 ( )  0.985 7 7 7 7 7 7  “Độ ẩm” = “TB”: 6 1 6 6 1 1 Info([6,1])  entropy( , )   log 2 ( )  log 2 ( )  0.592 7 7 7 7 7 7 Entropy( Doam)  7 7 7 7 Info(3, 4)  Info(6,1)   0.985   0.592  0.789 14 14 14 14 Gain( Doam)  Info(9,5)  entropy( Doam)  0.940  0.789  0.151 Tương tự cho các thuộc tính còn lại ta có: Gain(Quangcanh )  0.246 Gain( Doam)  0.151 Gain(Gio)  0.048 Gain( Nhietdo )  0.029