phần Mở đầu, Mục lục, Danh mục hình, Kết luận, Tài liệu tham khảo. Nội dung chính của luận văn đƣợc trình bày trong 04 chƣơng nhƣ sau: Chƣơng 1: Tổng quan về khai phá tri thức trong cơ sở dữ liệu không gian. Chƣơng 2: Các cách tiếp cận của kỹ thuật phân nhóm. Chƣơng 3: Các giải thuật phân nhóm trên cơ sở dữ liệu không gian lớn.
Chƣơng 4: Xác định tham số, cài đặt thử nghiệm và đánh giá kết quả. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ 6 Chƣơng 1 TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ CƠ SỞ DỮ LIỆU KHÔNG GIAN 1. Khai phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD) 1. Sự ra đời của khai phá tri thức trong cơ sở dữ liệu Trong những năm gần đây, cùng với sự thay đổi và phát triển không ngừng của ngành công nghệ thông tin nói chung và trong các ngành công nghệ phần cứng, phần mềm, truyền thông và hệ thống các dữ liệu phục vụ trong các lĩnh vực kinh tế xã hội nói riêng đã 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.
Bên cạnh đó việc tin học hóa một cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng nhƣ nhiều lĩnh vực hoạt động khác đã tạo ra cho chúng ta một lƣợng dữ liệu lƣu trữ khổng lồ. Hàng triệu CSDL đã đƣợc sử dụng trong các hoạt động sản xuất, kinh doanh, quản lí…, trong đó có nhiều CSDL cực lớn cỡ Gigabyte, thậm trí là Terabyte. 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 để tự động chuyển đổi lƣợng dữ liệu khổng lồ kia thành các tri thức có ích. Sự phát triển nhanh chóng của một lƣợng lớn dữ liệu đƣợc thu thập và lƣu trữ trong các cơ sở dữ liệu lớn đã vƣợt ra ngoài khả năng của con ngƣời để có thể hiểu hết đƣợc chúng nếu không có những công cụ hỗ trợ tốt.
Kết quả là, dữ liệu thu thập đƣợc trong một lƣợng lớn cơ sở dữ liệu đã trở thành những đống dữ liệu mà ít khi đƣợc xem xét đến. Do vậy, việc đƣa ra những quyết định thƣờng không dựa vào những thông tin hoặc dữ liệu thu thập đƣợc mà chỉ dựa vào nhận thức, suy đoán của ngƣời đƣa ra quyết định, đơn giản là vì họ không có những công cụ giúp cho việc lấy ra những tri thức từ lƣợng lớn dữ liệu. Tình huống này đã đặt chúng ta trong hoàn cảnh nhiều dữ liệu nhƣng thiếu thông tin, thiếu tri thức. Với một khối lƣợng lớn dữ liệu nhƣ vậy rõ ràng là các phƣơng pháp thủ công truyền thống áp dụng để phân tích dữ liệu nhƣ chia bảng hoặc ngôn ngữ truy vấn ad-hoc đã không thể áp dụng đƣợc nữa.
Dẫn đến nhu cầu về một kỹ thuật mới có các đặc tính thông minh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ 7 và khả năng tự động để hỗ trợ con ngƣời tìm kiếm thông tin hữu ích trong một núi dữ liệu lộn xộn. Kỹ thuật đó đƣợc gọi là khai phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database - KDD). Khai phá tri thức trong cơ sở dữ liệu đƣợc định nghĩa bởi Fayyad nhƣ sau: “Knowledge discovery in databases is the non-trivial process of identifying valid, novel, potentially, and ultimately understandable patterns in data”. Khái niệm khai phá dữ liệu Khai phá dữ liệu (Data Mining) là một khái niệm ra đời vào những năm cuối của thập kỷ 1980.
Nó là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong lƣợng lớn dữ liệu đƣợc lƣu trữ trong các CSDL, kho dữ liệu….Hiện nay, ngoài thuật ngữ khai phá dữ liệu, ngƣời ta còn dùng một số thuật ngữ khác có ý nghĩa tƣơng tự nhƣ: Khai phá tri thức từ CSDL, trích lọc dữ liệu, phân tích dữ liệu mẫu, khảo cổ dữ liệu, nạo vét dữ liệu. Nhiều ngƣời coi Khai phá dữ liệu và một thuật ngữ thông dụng khác là Phát hiện tri thức trong CSDL (Knowledge Discovery in Databases - KDD) là nhƣ nhau. Tuy nhiên trên thực tế, khai phá dữ liệu chỉ là một bƣớc thiết yếu trong quá trình Phát hiện tri thức trong CSDL. Có thể nói Data Mining là giai đoạn quan trọng nhất trong tiến trình Phát hiện tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh.
Quá trình khai phá tri thức trong cơ sở dữ liệu Quá trình khai phá tri thức trong cơ sở dữ liệu bao gồm các giai đoạn sau: 1. Trƣớc tiên cần xác định và hiểu rõ đƣợc lĩnh vực ứng dụng và nhiệm vụ đặt ra là xác định các tri thức đã có và mục đích của ngƣời sử dụng. Tạo lập đƣợc một tập dữ liệu đích: Chọn lựa từ cơ sở dữ liệu một tập con dữ liệu với các giá trị biến và các mẫu đƣợc quan tâm mà trên đó ta có thể thực hiện việc tìm kiếm, phát hiện tri thức. Làm sạch và tiền xử lý dữ liệu: Thực hiện các thao tác cơ bản nhƣ loại bỏ nhiễu hoặc loại bỏ các phần không cần thiết, bổ sung thêm các thông tin cần thiết Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.
Thực hiện các phƣơng pháp chuyển đổi để làm giảm bớt số chiều của dữ liệu để tập trung vào những thuộc tính chủ chốt đối với việc phát hiện tri thức. Khai phá dữ liệu: Quá trình áp dụng các giải thuật về tìm kiếm tri thức để đƣa ra đƣợc những thông tin cần thiết và tiềm ẩn trong tập dữ liệu. Đánh giá, giải thích, thử lại các mẫu đã đƣợc khai phá, có thể lặp lại một hoặc nhiều bƣớc kể trên để thu đƣợc các kết quả tốt hơn. Sử dụng các tri thức phát hiện đƣợc: Hợp nhất các tri thức thu đƣợc vào một hệ thống làm việc, hoặc đƣa ra các tài liệu về tri thức thu đƣợc từ dữ liệu về một vấn đề quan tâm.
Giải quyết các xung đột tiềm tàng trong tri thức khai thác đƣợc.1: Các bƣớc trong quá trình khám phá tri thức KDD Khai phá dữ liệu (Data mining) chỉ là một bƣớc trong quá trình khai phá tri thức trong cơ sở dữ liệu. Tuy nhiên đây là giai đoạn đóng vai trò quan trọng nhất, có ảnh hƣởng rất lớn đến chất lƣợng cũng nhƣ hiệu quả của toàn bộ quá trình khai phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD). Các nhiệm vụ của khai phá dữ liệu Nhìn chung, mục đích chính của khai phá dữ liệu là dự đoán (prediction) và mô tả (description). Dự đoán là việc sử dụng các biến hoặc các trƣờng trong cơ sở dữ liệu để đƣa ra dự đoán về những giá trị chƣa biết hoặc những giá trị chờ đợi trong tƣơng lai.
Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con ngƣời có thể hiểu đƣợc. Để đạt đƣợc hai mục đích này, nhiệm vụ chính của khai phá dữ liệu gồm: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ 9 Phân lớp (Classification), hồi quy (Regression), phân nhóm (Clustering), tóm tắt (Summarization), mô hình hoá phụ thuộc (Dependency modeling), phát hiện sự thay đổi và lạc hƣớng (Change and deviation detection). Phân lớp là phân loại một mẫu dữ liệu vào một trong số các lớp đã xác định. Hồi quy 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 (real -valued prediction variable).
Phân nhóm là việc mô tả chung để tìm ra tập xác định các nhóm hay các loại để mô tả dữ liệu. Tổng kết liên quan đến các phƣơng pháp tìm kiếm mô tả tóm tắt cho một tập con dữ liệu. Mô hình hoá phụ thuộc bao gồm việc tìm kiếm một mô hình mô tả sự phụ thuộc đáng kể giữa các biến. Phát hiện sự thay đổi và lạc hƣớng bao gồm khai thác những thay đổi đáng kể trong dữ liệu từ các giá trị chuẩn hoặc đƣợc đo trƣớc đó.[3] Trong các phƣơng pháp trên, phân nhóm đƣợc sử dụng rộng rãi nhất và đôi khi đƣợc coi là tiền xử lý dữ liệu cho những phƣơng pháp khác.
Vì thế khi cần xây dựng một ứng dụng cho KDD vào thực tế vấn đề đầu tiên ngƣời ta phải quan tâm tới là chia dữ liệu thành từng nhóm. Việc phân nhóm giúp cho chúng ta có cái nhìn tổng quan hơn về từng khối dữ liệu. Đặc biệt khi việc phân nhóm tốt, thời gian xem xét cơ sở dữ liệu đƣợc giảm xuống bởi vì chúng ta không nhất thiết phải tìm kiếm trong toàn bộ cơ sở dữ liệu mà chỉ phải tìm kiếm ở một lớp (nhóm) các dữ liệu trong cơ sở dữ liệu lớn. Phân nhóm (Clustering) và các cách tiếp cận chính 1.
Phân nhóm và các ứng dụng a. Khái niệm Phân nhóm (clustering) là quá trình nhóm một tập các đối tƣợng vật lý hoặc trừu tƣợng thành các nhóm hay các lớp đối tƣợng tƣơng tự nhau. Một lớp (cluster) là một tập các đối tƣợng dữ liệu trong đó các đối tƣợng trong cùng một lớp có sự tƣơng tự hoặc giống nhau và ít tƣơng tự hoặc khác nhau so với các đối tƣợng thuộc lớp khác. độ tƣơng tự đƣợc xác định theo một tiêu chuẩn nào đó, tuỳ thuộc vào từng ứng dụng cụ thể và đƣợc xác định trƣớc.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ 10 Không giống nhƣ trong quá trình phân loại (classification), ta thƣờng biết trƣớc tính chất hay đặc điểm của các đối tƣợng trong cùng một lớp và dựa vào đó để ấn định một đối tƣợng mới vào lớp của nó. Thay vào đó, trong quá trình phân nhóm ta không hề biết trƣớc tính chất của các lớp mà phải dựa vào mối quan hệ giữa các đối tƣợng để tìm ra sự giống nhau giữa các đối tƣợng theo một độ đo nào đó đặc trƣng cho mỗi lớp. Một ví dụ cho việc phân nhóm để tìm hiểu về các vì sao và nhiệt độ của nó. Biểu đồ trên hình 1.2 đƣợc gọi là biểu đồ Hertzsprung-Russell với trục tung là độ sáng và trục hoành là nhiệt độ (theo độ K).2: Biểu đồ Hertzsprung-Russell Có thể thấy đƣợc rằng những ngôi sao trong biểu đồ thuộc vào một trong 3 lớp và trong mỗi lớp mối quan hệ giữa nhiệt độ và độ sáng là nhƣ nhau.
Giữa các lớp khác nhau mối quan hệ đó cũng khác nhau. Các ứng dụng của phân nhóm Đây là một hoạt động quan trọng của con ngƣời.