- NGHIÊN CỨU MỘT SỐ KỸ THUẬT KHAI PHÁ DỮ LIỆU ỨNG DỤNG. - CHƢƠNG I: TỔNG QUAN VỀ DỮ LIỆU KHÔNG GIAN VÀ KHAI PHÁ DỮ LIỆU. - Tổng quan về dữ liệu không gian địa lý. - Mô hình dữ liệu Vector. - Khai phá dữ liệu. - Định nghĩa khai phá dữ liệu. - Nhiệm vụ chính trong khai phá dữ liệu. - Các phương pháp khai phá dữ liệu. - 10 CHƢƠNG 2: KHAI PHÁ DỮ LIỆU KHÔNG GIAN SỬ DỤNG CÂY QUYẾT ĐỊNH. - Phân lớp dữ liệu. - Cây quyết định ứng dụng trong phân lớp dữ liệu. - Xây dựng cây quyết định trong khai phá dữ liệu không gian. - Đề xuất phương pháp mới phân lớp dữ liệu không gian . - CHƢƠNG 3: KHAI PHÁ DỮ LIỆU KHÔNG GIAN BẰNG PHÂN CỤM DỮ LIỆU KHÔNG GIAN. - Nguồn dữ liệu đầu vào và phạm vi bài toán. - CSDL Cơ sở dữ liệu. - Bảng 1.4: Dữ liệu tọa độ cung. - Bảng 1.5: Mô tả dữ liệu đặc trưng cấu trúc Spaghetti. - Bảng 2.1: Dữ liệu thời tiết. - Bảng 2.5: Dữ liệu thời tiết xét thuộc tính độ ẩm dạng số. - Bảng 2.7: Dữ liệu thời tiết xét thuộc tính ngày. - Bảng 4.2: Kết quả so sánh thời gian thực hiện phân cụm cùng tập dữ liệu. - Hình 1.1: Đối tượng dữ liệu cơ bản điểm, đường vùng. - Hình 1.2: Biểu diễn đối tượng bằng mô hình dữ liệu Raster. - Hình 1.4: Minh họa dữ liệu Spaghetti. - Hình 1.5: Các bước của quá trình khai phá dữ liệu. - Hình 4.7: Kết quả phân cụm DBSCAN đối với dữ liệu thử nghiệm tự tạo. - 72 Hình 4.10: Đồ thị so thời gian thực hiện phân cụm của các thuật toán K-measn, DBSCAN và DBRS với cùng một tập dữ liệu đầu vào. - Việc dữ liệu tăng lên nhanh với quy mô lớn đòi hỏi phải được khai phá để trích chọn ra các tri thức hữa ích phục vụ cho công tác chuyên môn. - Chính điều này đã dẫn đến sự ra đời của lĩnh vực khai phá dữ liệu hay khai phá tri thức trong các CSDL.. - Khai phá dữ liệu là sự kết hợp của một số lĩnh vực bao gồm học máy, các hệ thống CSDL, thể hiện dữ liệu, thống kê và lý thuyết thông tin.. - Đã có nhiều nghiên cứu về khai phá dữ liệu trong các CSDL quan hệ và giao dịch, nhưng đối với các CSDL không gian vấn đề khai phá dữ liệu vẫn còn là những thách thức cần được giải quyết.. - Dữ liệu không gian là dữ liệu liên quan đến các đối tượng trong không gian. - Một CSDL không gian lưu trữ các đối tượng không gian bao gồm các kiểu dữ liệu không gian và các quan hệ không gian giữa các đối tượng. - Dữ liệu không gian mang thông tin hình học và khoảng cách thường được tổ chức theo các cấu trúc chỉ mục không gian và truy cập bằng các phương pháp truy cập không gian. - Khai phá dữ liệu không gian hay khai phá tri thức trong CSDL không gian là trích trọn ra các tri thức tiềm ẩn, các quan hệ không gian hay các mẫu chưa rõ lưu trữ trong các CSDL không gian.. - Và những tiến bộ của các CSDL không gian như cấu trúc dữ liệu không gian, lập luận không gian, tính toán hình học,…. - đã mở đường cho khai phá dữ liệu không gian. - Trở ngại lớn nhất trong khai phá dữ liệu không gian là hiệu quả của các thuật toán khai phá dữ liệu không gian do lượng dữ liệu. - không gian thường là có quy mô lớn, các kiểu dữ liệu không gian và các phương pháp truy cập không gian phức tạp.. - Các phương pháp khai phá dữ liệu không gian tập trung theo ba hướng chính là khai phá luật kết hợp không gian, phân lớp dữ liệu không gian và phân cụm dữ liệu không gian. - Với mong muốn nghiên cứu về phân lớp dữ liệu không gian sử dụng cây quyết định, luận văn đi sâu tìm hiểu một lĩnh vực nhỏ đó là phân lớp dữ liệu không gian sử dụng cây quyết định.. - Luận văn tập trung nghiên cứu kỹ thuật phân lớp không gian sử dụng cây quyết định và phân cụm dữ liệu nhằm trích rút ra các dữ liệu địa lý có ích tiềm ẩn bên trong. - Thu thập một số lớp dữ liệu bản đồ (bao gồm cả dữ liệu hình học và dữ liệu thuộc tính) để thử nghiệm với thuật toán phân lớp dữ liệu không gian sử dụng cây quyết định.. - Nghiên cứu một số thuật toán phân lớp dữ liệu quan hệ dựa trên cây quyết định đối với cơ sở dữ liệu truyền thống, đề xuất mở rộng áp dụng trên dữ liệu địa lý.. - Nghiên cứu một số thuật toán phân lớp dữ liệu quan hệ dựa trên phân cụm dữ liệu - Cài đặt chương trình thử nghiệm thuật toán lựa chọn trên dữ liệu hình học và dữ liệu thuộc tính của một số lớp bản đồ.. - Chƣơng 1: Tổng quan về dữ liệu không gian và khai phá dữ liệu. - Bao gồm các phần như: Giới thiệu khái quát về dữ liệu địa lý, khai phá dữ liệu, cây quyết định.. - Chƣơng 2: Khai phá dữ liệu không gian sử dụng cây quyết định. - Bao gồm: Giới thiệu một số kỹ thuật khai khai phá dữ liệu sử dụng cây quyết định trên cơ sở dữ liệu quan hệ truyền thống, vận dụng đề xuất thuật toán trong khai phá dữ liệu không gian.. - Chƣơng 3: Khai phá dữ liệu không gian bằng phân cụm dữ liệu.. - Bao gồm mô tả bài toán, xây dựng dữ liệu thử nghiệm, thiết kế chương trình, cài đặt thuật toán và đánh giá kết quả thử nghiệm.. - Kết luận trình bày những nghiên cứu về phân lớp dữ liệu không gian sử dụng cây quyết định, những đóng góp của luận văn và những định hướng nghiên cứu sắp tới.. - TỔNG QUAN VỀ DỮ LIỆU KHÔNG GIAN VÀ KHAI PHÁ DỮ LIỆU. - Tổng quan về dữ liệu không gian địa lý 1.1.1. - Đối tượng địa lý: Trên bản đồ, các đối tượng như trạm xe bus, bến tàu, trạm xăng là các thực thể dữ liệu quản lý, còn được gọi là đối tượng địa lý. - Dữ liệu địa lý và cơ sở dữ liệu địa lý: Dữ liệu địa lý là thông tin về các đối tượng địa lý được mã hóa trong máy tính. - Dữ liệu không gian và dữ liệu phi không gian: Một đối tượng địa lý chứa các thông tin dữ liệu không gian và dữ liệu phi không gian.. - Dữ liệu không gian: Dữ liệu không gian được sử dụng theo nghĩa rộng bao gồm các điểm đa chiều, các đường thẳng, hình khối,...và các đối tượng hình học nói chung.. - Trong luận văn, khái niệm dữ liệu không gian được hiểu đơn giản hơn, dữ liệu không gian mô tả các đối tượng địa lý được thể hiện dưới dạng hình học, được quản lý bằng hình thể và được biểu diễn dưới ba dạng đối tượng cơ bản là điểm, đường, vùng.. - Dữ liệu phi không gian: Một đối tượng địa lý ngoài các thuộc tính không gian còn có các thông tin thuộc tính khác. - Dữ liệu phi không gian đôi khi gọi tắt là dữ liệu thuộc tính.. - Hệ thống GIS: Khi đề cập đến dữ liệu địa lý, hệ thống thông tin địa lý (Geographic Information System - gọi tắt là GIS) thường được nhắc đến bởi GIS sử dụng dữ liệu địa lý. - phần cứng, phần mềm, dữ liệu và con người (người dùng và các quy định, chính sách liên quan đến duy trì, phát triển hệ thống).. - Có nhiều mô hình dữ liệu được sử dụng trong hệ thống thông tin địa lý, tuy nhiên, phổ biến nhất trong biểu diễn thành phần không gian của thông tin địa lý là hai mô hình dữ liệu cơ bản Vector và Raster.. - Mô hình dữ liệu Vector: sử dụng các đường hay điểm, được xác định tường minh bằng các tọa đọa x, y của chúng trên bản đồ.. - Ngoài giá trị tọa độ (x, y), điểm còn thể hiện kiểu điểm, màu, hình dạng và dữ liệu thuộc tính đi kèm. - Đối tượng dữ liệu cơ bản Điểm, Đường, Vùng. - Mô hình dữ liệu Raster: Sử dụng tập hợp các ô. - Biểu diễn đối tượng bằng mô hình dữ liệu Raster. - Mô hình dữ liệu Vector được sử dụng để miêu tả các đối tượng được xác định chính xác vị trí, kích thước và hình dạng. - Dữ liệu Vector có khả năng phân giải cao và in ấn xuất bản tương tự như bản đồ làm bằng tay. - Dữ liệu Vector cần ít không gian lưu trữ và duy trì mối quan hệ hình học dễ dàng. - Hai loại cấu trúc được biết đến trong mô hình dữ liệu Vector là cấu trúc Spaghetti và cấu trúc Topology. - Cấu trúc Spaghetti ra đời trước và được sử dụng cho đến ngày nay ở một số các phần mềm GIS như phần mềm Arcview GIS, ArcGIS, MapInfo,… Cấu trúc Topology ra đời trên nền tảng của mô hình dữ liệu cung – nút.. - Trong GIS, khi biết hình dạng hình học, vị trí, kích thước và hệ tọa độ của đối tượng chỉ mới đáp ứng được tính đầy đủ của dữ liệu GIS. - Dữ liệu tọa độ cung. - Trong cấu trúc dữ liệu Spaghetti, đơn vị cơ sở là các cặp tọa độ trên một không gian địa lý xác định. - Minh họa cho dữ liệu Spaghetti như hình vẽ sau:. - Minh họa dữ liệu Spaghetti Bảng mô tả đặc trưng của cấu trúc Spaghetti. - Mô tả dữ liệu đặc trưng cấu trúc Spaghetti. - Khai phá dữ liệu được dùng để mô tả quá trình phát hiện ra tri thức trong CSDL.. - Khai phá dữ liệu làm giảm chi phí về thời gian so với phương pháp truyền thống trước kia (ví dụ như phương pháp thống kê).. - Các bước của quá trình khai phá dữ liệu. - Bước 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. - 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á.. - 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. - 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.. - Nhiệm vụ chính trong khai phá dữ liệu bao gồm : Phân lớp, Hồi qui, Phân nhóm, Tổng hợp, Mô hình hoá sự phụ thuộc và Phát hiện sự biến đổi và độ lệch.. - Là việc dùng một hàm dự báo để từ các mẫu dữ liệu đã có hàm dự báo sẽ cho một giá trị thực. - 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ó nghĩa là dữ liệu có thể vừa thuộc nhóm này lại 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ị. - 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.. - Các thành phần của giải thuật khai phá dữ liệu: Giải thuật khai phá dữ liệu bao gồm 3 thành phần chính như sau: biểu diễn mô hình, kiểm định mô hình và phương pháp tìm kiếm.. - Mô tả mô hình rõ ràng thì học máy sẽ tạo ra mẫu có mô hình chính xác cho dữ liệu. - Khả năng miêu tả mô hình càng lớn thì càng làm tăng mức độ nguy hiểm do bị học quá và làm giảm đi khả năng dự đoán các dữ liệu chưa biết