Luận văn Thạc sĩ Khoa học máy tính: Phương pháp lan truyền độ tương tự trong phân cụm dữ liệu và ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:65

Thêm vào BST

Báo xấu

13
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung nghiên cứu của luận văn là tìm hiểu tổng quan về phân cụm dữ liệu; các điểm đặc thù của bài toán phân cụm dữ liệu địa lý; Một số đặc điểm của thuật toán lan truyền độ tương tự, trên cơ sở lý thuyết toán học hoặc phân tích thực nghiệm. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Phương pháp lan truyền độ tương tự trong phân cụm dữ liệu và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TẠ DUY KHÁNH PHƢƠNG PHÁP LAN TRUYỀN ĐỘ TƢƠNG TỰ TRONG PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TẠ DUY KHÁNH PHƢƠNG PHÁP LAN TRUYỀN ĐỘ TƢƠNG TỰ TRONG PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS NGUYỄN ĐÌNH HÓA Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTNii http://www.lrc.tnu.edu.vn
LỜI CÁM ƠN Đầu tiên, tôi xin gửi lời cảm ơn sâu sắc đến thầy giáo, cán bộ hướng dẫn khoa học PGS.TS Nguyễn Đình Hóa đã tận tình hướng dẫn tôi từ những buổi đầu tiên khi tiếp cận với đề tài khoa học. Trong quá trình làm luận văn, tôi cũng nhận được sự giúp đỡ rất nhiệt tình từ nhóm nghiên cứu của TS. Lê Hoàng Sơn tại Trung tâm tính toán hiệu năng cao, trường ĐH KHTN và đề tài NCKH cấp ĐHQG, mã số GG.14.60. Tôi xin bày tỏ lòng biết ơn đến các thầy cô giáo ở trường Đại học Công nghệ thông tin và Truyền thông – Đại học Thái Nguyên, các cán bộ Trung tâm Đông Đô - Hà Nội, đã tận tình giảng dạy và tạo mọi điều kiện cho tôi học tập, nghiên cứu và hoàn thành luận văn này. Tôi xin chân thành cảm ơn các bạn học viên lớp CK12H, CK13H – Khoa học máy tính đã giúp đỡ, tạo điều kiện cho tôi trong suốt quá trình học tập và thực hiện luận văn. Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc nhất đến gia đình, đồng nghiệp và bạn bè tôi, những người đã động viên, tạo mọi điều kiện cho tôi lao động và học tập trong suốt thời gian qua. Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng cá nhân tôi, không sao chép của ai. Luận văn là do tôi tự nghiên cứu, đọc, dịch tài liệu, tổng hợp và thực hiện. Nội dung lý thuyết trong luận văn có sử dụng một số tài liệu tham khảo như đã trình bày trong phần tài liệu tham khảo. Chương trình phần mềm và những kết quả trong luận văn là trung thực và chưa được công bố trong bất kỳ một hệ thống nào khác. Một lần nữa, xin chân thành cảm ơn! Số hóa bởi Trung tâm Học liệu – ĐHTN i http://www.lrc.tnu.edu.vn
MỤC LỤC LỜI CÁM ƠN ....................................................................................................... i MỤC LỤC………………………………………………………………………ii DANH MỤC CÁC TỪ VIẾT TẮT ................................................................... iv DANH MỤC CÁC HÌNH VẼ............................................................................. v MỞ ĐẦU .............................................................................................................. 1 CHƢƠNG 1: HỆ THỐNG THÔNG TIN ĐỊA LÝ VÀ PHÂN CỤM DỮ LIỆU ĐỊA LÝ ...................................................................................................... 6 1.1 Tổng quan về hệ thống thông tin địa lý ................................................... 6 1.1.1 Lịch sử ra đời ........................................................................................ 6 1.1.2 Định nghĩa............................................................................................. 7 1.1.3 Các thành phần của hệ thống thông tin địa lý ...................................... 8 1.1.4 Dữ liệu trong hệ thống thông tin địa lý .............................................. 10 1.2 Phân cụm dữ liệu địa lý.......................................................................... 11 1.2.1 Phân cụm dữ liệu ................................................................................ 11 1.2.2 Một số kỹ thuật phân cụm dữ liệu ...................................................... 12 1.2.2.1 Thuật toán phân cụm theo cây phân cấp.......................................... 13 1.2.2.2 Thuật toán phân cụm phân hoạch : Phân cụm k-means .................. 14 1.2.2.3 Phân cụm mờ ................................................................................... 16 1.3 Dữ liệu địa lý và vấn đề phân cụm đối tƣợng địa lý ............................ 17 1.3.1 Cấu trúc dữ liệu trong GIS.................................................................. 18 1.3.1.1 Hai mô hình dữ liệu không gian ...................................................... 18 1.3.1.2 Dữ liệu thuộc tính ............................................................................ 19 1.3.2 Các vấn đề trong phân cụm dữ liệu địa lý ......................................... 20 CHƢƠNG 2: PHÂN CỤM BẰNG THUẬT TOÁN LAN TRUYỀN ĐỘ TƢƠNG TỰ ....................................................................................................... 22 2.1 Các khái niệm cơ sở ................................................................................. 22 2.1.1 Ý tưởng thuật toán .............................................................................. 22 2.1.2 Các công thức chính trong thuật toán AP ...................................... 24 2.1.3 Thuật toán AP nguyên thủy ............................................................... 25 2.2 Thuật toán lan truyền AP tự thích nghi ............................................... 27 2.2.1 Phương pháp thích ứng giảm dần ....................................................... 28 2.2.2 Kỹ thuật thích nghi p-scanning ........................................................... 30 Số hóa bởi Trung tâm Học liệu – ĐHTNii http://www.lrc.tnu.edu.vn
2.3 Thuật toán lan truyền AP với tập dữ liệu hỗn hợp kiểu số và kiểu phân loại ......................................................................................................... 31 2.3.1 Khoảng cách và ý nghĩa ...................................................................... 32 2.3.2 Phương pháp ....................................................................................... 32 2.3.3 Cải thiện độ đo tương tự ..................................................................... 34 2.3.4 Thích nghi thuật toán lan truyền ......................................................... 36 CHƢƠNG 3: XÂY DỰNG ỨNG DỤNG PHÂN CỤM DỮ LIỆU ĐỊA LÝ 39 3.1 Bài toán thực tế và cách tiếp cận phân cụm dữ liệu............................. 39 3.1.1 Bài toán khai thác các dữ liệu quan trắc khí tượng ............................ 39 3.1.2 Lựa chọn giải pháp kỹ thuật công nghệ .............................................. 40 3.2 Các phần mềm GIS ................................................................................ 40 3.3 Tìm hiểu về phần mềm mã nguồn mở MapWindow ........................... 42 3.4 Thiết kế một plug-in trên phần mềm mã nguồn mở Mapwindown ... 44 3.4.1 Thêm một plug-ins từ Visual Studio vào MapWindow ..................... 44 3.4.2 Xây dựng ứng dụng với Active X map control trong Visual Studio .. 45 Kết quả chạy thử nghiệm .............................................................................. 53 KẾT LUẬN ........................................................................................................ 56 1. Một số kết quả đạt được của luận văn ..................................................... 56 2. Những hạn chế và hướng phát triển ......................................................... 56 TÀI LIỆU THAM KHẢO ................................................................................ 57 Số hóa bởi Trung tâm Học liệu – ĐHTNiii http://www.lrc.tnu.edu.vn
DANH MỤC CÁC TỪ VIẾT TẮT Từ STT Từ tiếng Anh Ý nghĩa viết tắt 1 GIS Geographical Hệ thống thông tin địa lý Information System 2 AP affinity propagation Thuật toán lan truyền độ tương tự 3 CSDL Database Cơ sở dữ liệu 4 SIL Silhouette Công thức Silhouette 5 DEM Digital Elevation Model Mô hình kỹ thuật số độ cao 6 DTM Digital Terrain Model Mô hình kỹ thuật số các địa hình 7 TIN Triangulated Irregular Lưới tam giác không đều Network 8 SQL Structured Query Ngôn ngữ truy vấn có cấu trúc Language Số hóa bởi Trung tâm Học liệu – ĐHTNiv http://www.lrc.tnu.edu.vn
DANH MỤC CÁC HÌNH VẼ Hình 1.1: Các thành phần của hệ thống thông tin địa lý Gis Hình 1.2: Thuật toán phân cụm K-means Hình 1.3: Cấu trúc vector và raster Hình 2.1: Đồ thị Affinity Propagation (AP) Hình 2.2: Minh họa hiệu năng của ba kỹ thuật rời rạc hóa khác nhau Hình 3.1: Phần mềm mã nguồn mở Mapwindow Hình 3.2: Kiếm tra plug-ins vừa add trong MapWindow Hình 3.3: Kéo thả Map Control vào form Hình 3.4: Kéo Legend vào form Hình 3.5: Kéo thêm DataGridView vào form Table Hình 3.6: Giao diện plugin APCluster Số hóa bởi Trung tâm Học liệu – ĐHTNv http://www.lrc.tnu.edu.vn
MỞ ĐẦU 1. Đặt vấn đề Nguồn dữ liệu dồi dào cung cấp nhiều thông tin, từ đó nhân loại đúc rút thành tri thức trong quá trình phát triển xã hội loài người. Với sự phát triển của công nghệ điện toán và hệ thống lưu trữ dữ liệu thì khối lượng tài nguyên số ngày càng trở nên phong phú và đồ sộ. Trong xã hội hiện đại, thông tin đóng một vai trò then chốt. Nhu cầu xử lý dữ liệu, trích rút thông tin, kịp thời khai thác chúng để mang lại những hiệu quả thiết thực cho công tác quản lý, hoạt động sản xuất kinh doanh,… ngày càng trở nên cấp thiết. Khai phá dữ liệu nói chung để trích rút thông tin và phân cụm dữ liệu nói riêng là một trong những trọng tâm nghiên cứu của khoa học máy tính. Phân cụm dữ liệu là một trong những biện pháp để tìm kiếm tri thức, khi ta chưa biết nhiều thông tin về miền ứng dụng. Phân cụm được coi như một công cụ độc lập để xem xét phân bố dữ liệu, là bước tiền xử lý cho các bước sau. Phân cụm dữ liệu hiện có nhiều ứng dụng trong hầu hết các lĩnh vực hoạt động kinh tế, xã hội. Có nhiều phương pháp và thuật toán phân cụm dữ liệu khác nhau, tùy theo cách tiếp cận bài toán dưới góc độ nào. Một phương pháp mới được đề xuất tương đối gần đây là Phương pháp lan truyền độ tương tự. Thuật toán lan truyền độ tương tự (Affinity Propagation - AP) là thuật toán phân cụm dữ liệu được đưa ra bởi Frey & Dueck vào năm 2007 dựa trên ý tưởng thuật toán lan truyền độ tin cậy trong suy diễn trên mạng xác xuất Bayes, dựa trên cơ sở toán học của lý thuyết xác suất. Thuật toán lan truyền làm việc dựa trên sự tương đồng (affinity nghĩa là sự giống nhau, sự tương thích, sự hấp dẫn) giữa các cặp điểm dữ liệu và đồng thời xem xét tất cả các điểm dữ liệu như các tâm cụm tiềm năng, theo thuật ngữ ở đây là tất cả các điểm dữ liệu đều là hình mẫu (exemplar) tiềm năng, và trao đổi các thông điệp giá trị thực cho đến khi có được tập hình mẫu tốt (phân cụm tương ứng). Số hóa bởi Trung tâm Học liệu – ĐHTN1 http://www.lrc.tnu.edu.vn
Thuật toán phân cụm AP có một số ưu điểm: cho kết quả phân cụm tốt, đặc biệt là trong trường hợp có số lượng lớn các cụm, phát hiện cụm có hình dáng bất kỳ, không yêu cầu phải xác định trước số cụm. Nó cũng cho phép dễ dàng thực hiện phân cụm thỏa mãn một số điều kiện xác định trước nào đó, tức là phân cụm bán giám sát. Đặc tính này thích hợp cho phân cụm dữ liệu trong GIS vì những ràng buộc điều kiện địa hình tự nhiên hoặc quản lý hành chính cần tính đến trong các bài toán thực tế. Luận văn chọn đề tài “Phương pháp lan truyền độ tương tự trong phân cụm dữ liệu và ứng dụng” là hướng nghiên cứu chính, với mục tiêu khám phá những điểm mạnh, điểm yếu của phương pháp này, hiểu biết sâu thêm về một cách tiếp cận phân cụm, đồng thời nâng cao kỹ năng thực hành triển khai ứng dụng. 2. Đối tƣợng và phạm vi nghiên cứu Đối tượng nghiên cứu là các phương pháp phân cụm dữ liệu, tập trung vào thuật toán lan truyền độ tương tự. Phạm vi nghiên cứu là các điểm mạnh, điểm yếu và tiềm năng ứng dụng phương pháp lan truyền độ tương tự trong phân cụm dữ liệu địa lý. 3. Hƣớng nghiên cứu của đề tài Luận văn dự kiến hướng nghiên cứu là: Nghiên cứu lý thuyết: tìm hiểu sâu hơn về thuật toán lan truyền độ tương tự, trên cơ sở nắm vững bản chất của phương pháp lan truyền độ tin cậy trong suy diễn trên mạng xác xuất Bayes. dựa trên cơ sở toán học của lý thuyết xác suất. Nghiên cứu ứng dụng: Cài đặt thử nghiệm thuật toán với dữ liệu mô phỏng để đánh giá, phân tích đánh giá kết quả; thử với dữ liệu thực tế. 4. Những nội dung nghiên cứu chính Số hóa bởi Trung tâm Học liệu – ĐHTN2 http://www.lrc.tnu.edu.vn
Nội dung nghiên cứu của luận văn bao gồm: Tìm hiểu tổng quan về phân cụm dữ liệu; các điểm đặc thù của bài toán phân cụm dữ liệu địa lý; Một số đặc điểm của thuật toán lan truyền độ tương tự, trên cơ sở lý thuyết toán học hoặc phân tích thực nghiệm. Về thực hành: Cài đặt thử nghiệm thuật toán với dữ liệu mô phỏng để đánh giá, phân tích đánh giá kết quả; thử với dữ liệu thực tế. Làm quen với hệ thống thông tin địa lý nguồn mở; cơ sở dữ liệu địa lý; cách viết plugin tích hợp phép phân tích dữ liệu địa lý. 5. Phƣơng pháp nghiên cứu Phương pháp nghiên cứu lý thuyết: tổng quan, phân tích các kết quả nghiên cứu đã có, nhận biết các ưu nhược điểm, lựa chọn cách tiếp cận phù hợp nhất để giải quyết bài toán ứng dụng. Nghiên cứu thực nghiệm qua phân tích kết quả thử nghiệm với dữ liệu mô phỏng; dữ liệu thực tế; so sánh đánh giá và kết luận. 6. Ý nghĩa khoa học của đề tài Đề tài nghiên cứu có ý nghĩa khoa học, góp phần làm hiểu biết sâu sắc hơn phương pháp lan truyền độ tương tự trong phân cụm dữ liệu. Ứng dụng thực tế: phân cụm dữ liệu môi trường, không khí, thời tiết… nhận được từ các trạm quan trắc khí tượng để xác định những tiểu vùng môi trường khí tượng trong một địa phương, khu vực. 7. Bố cục của luận văn Luận văn bao gồm 3 chương cùng với phần Mở đầu, phần Kết luận, phần Mục lục, phần Tài liệu tham khảo. Chương 1: Tổng quan về phân cụm dữ liệu GIS và phân cụm dữ liệu địa lý: Trình bày các khái niệm cơ bản, các cách tiếp cận, phương pháp, thuật toán; Số hóa bởi Trung tâm Học liệu – ĐHTN3 http://www.lrc.tnu.edu.vn
Chú trọng các kết quả đã biết về đánh giá điểm mạnh điểm yếu. Số hóa bởi Trung tâm Học liệu – ĐHTN4 http://www.lrc.tnu.edu.vn
Chương 2: Phương pháp lan truyền độ tương tự trong phân cụm dữ liệu Trình bày tổng quan một số phương pháp Chương 3: Xây dựng chương trình thử nghiệm Giới thiệu bài toán thử nghiệm. Dữ liệu thử nghiệm. Thiết kế hệ thống. Viết chương trình thử nghiệm. Dự định sử dụng ngôn ngữ lập trình C# để xây dựng chương trình demo Kết luận và hướng phát triển của luận văn Số hóa bởi Trung tâm Học liệu – ĐHTN5 http://www.lrc.tnu.edu.vn
CHƢƠNG 1 HỆ THỐNG THÔNG TIN ĐỊA LÝ VÀ PHÂN CỤM DỮ LIỆU ĐỊA LÝ 1.1 Tổng quan về hệ thống thông tin địa lý 1.1.1 Lịch sử ra đời Từ lâu bản đồ luôn là một công cụ thông tin quen thuộc đối với loài người. Trong quá trình phát triển kinh tế kĩ thuật, bản đồ luôn được cải tiến sao cho ngày càng đầy đủ thông tin và chính xác hơn. Với sự đa dạng của các loại bản đồ trong việc thể hiện các đối tượng khác nhau trên bề mặt trái đất, các nhà quy hoạch nhận thức được sự cần thiết trong xử lý đồng thời nhiều hơn một bản đồ. Các mô hình đồ họa cổ điển xử lý thông tin bản đồ gặp rất nhiều khó khăn trong xử lý đồng thời dữ liệu không gian và dữ liệu thuộc tính. Điều này đã dẫn đến sự phát triển các phương pháp và kỹ thuật xử lý tổng hợp thông tin nhằm phục vụ tốt hơn cho công tác quy hoạch và ra quyết định. Trong những năm đầu thập kỉ 60 (1963-1964) các nhà khoa học ở Canada đã cho ra đời hệ thông tin địa lý. Hệ thống thông tin địa lý kế thừa mọi thành tựu trong ngành bản đồ cả về ý tưởng lẫn thành tựu của kỹ thuật bản đồ. Hệ thông tin địa lý bắt đầu hoạt động bằng việc thu thập dữ liệu theo định hướng tuỳ thuộc vào mục tiêu đặt ra. Cùng với Canada, các trường đại học tại Mỹ cũng tiến hành nghiên cứu và xây dựng hệ thống thông tin địa lý và càng ngày nhu cầu sử dụng, nghiên cứu hệ thống thông tin địa lý càng được quan tâm nhiều hơn. Một số mốc lịch sử trong quá trình hình thành và phát triển công nghệ GIS:  1963 – Phòng đồ họa vi tính của trường đại học tổng hợp Harvard (R.Fisher, J. Dangermond, D. Sinton, N. Chrisman, G. Dutton, S. Morehouse, T.Peuker). Số hóa bởi Trung tâm Học liệu – ĐHTN6 http://www.lrc.tnu.edu.vn
 1963 – thành lập Hiệp hội các hệ thống thông tin đô thị và khu vực (URISA).  1964 – Symap ra đời (Hệ thống phần mềm vẽ bản đồ cơ sở do Đại học tổng hợp Harvard xây dựng).  Giữa những năm 1960 – Tổng cục điều tra dân số của Mỹ xây dựng quy trình vẽ bản đồ địa chính theo địa chỉ (D. Cooke, M. White xây dựng lý thuyết về quan hệ không gian cho các dữ liệu địa lý).  1967 – GIS Canađa ra đời (R. Tomlinson là tác giả của thuật ngữ GIS).  1967 – Thành lập Cơ quan đo vẽ bản đồ thực nghiệm ở Anh (Boyle, Rhind).  1969 – Thành lập Intergraph và ESRI (Dangermond và Morehouse).  1973 – Các hội nghị về Hệ thống thông tin đô thị (URPIS) được tổ chức tại Australia dẫn đến sự thành lập của Tổ chức các hệ thống thông tin đô thị Ôxtrâylia (AURISA) vào năm 1975.  1974 – Các hội nghị về AutoCarto được tổ chức.  1973 – ODYSSEY (tiền thân của phần mềm GIS do trường đại học Harvard xây dựng) ra đời.  1978 – Hệ thống hiển thị thông tin nội địa Nhà Trắng (Mỹ) ra đời.  1980 – Phần mềm ArcINFO ra đời.  1987 - Phần mềm MapINFO ra đời.  1987- Tạp chí GIS quốc tế ra đời. 1.1.2 Định nghĩa Hệ thông tin địa lý GIS (Geographical Information System) là tập hợp các công cụ để thu thập, lưu trữ, chỉnh sửa, truy cập, phân tích và cập nhật các thông Số hóa bởi Trung tâm Học liệu – ĐHTN7 http://www.lrc.tnu.edu.vn
tin địa lý cho một mục đích chuyên biệt. Ngoài ra cũng có nhiều định nghĩa khác về GIS: GIS là công cụ trên cơ sở nền máy tính để lập bản đồ và phân tích những hiện tượng đang tồn tại và các sự kiện xảy ra trên trái đất (Environmental System Research Institute ESRI – Mỹ). GIS là hệ thống phần cứng, phần mềm và các thủ tục được thiết kế nhằm thu thập, quản lý, xử lý, phân tích, mô hình hóa và hiển thị các dữ liệu quy chiếu không gian để giải quyết các vấn đề quản lý và lập kế hoạch (National Center for Geography Information and Analysis NCGIA – Mỹ). GIS là một tập hợp các nguyên lý, phương pháp, dụng cụ và dữ liệu quy chiếu không gian được sử dụng để nhập, lưu trữ, chuyển đổi, phân tích, lập mô hình, mô phỏng và lập bản đồ các hiện tượng, sự kiện trên trái đất, nhằm sản sinh các thông tin thiết thực hổ trợ cho việc ra quyết định (Thesriault – Canada). 1.1.3 Các thành phần của hệ thống thông tin địa lý GIS bao gồm 5 thành phần chính là: phần cứng, phần mềm, dữ liệu, con người và các chính sách. Hình 1.1: Các thành phần của hệ thống thông tin địa lý Gis Số hóa bởi Trung tâm Học liệu – ĐHTN8 http://www.lrc.tnu.edu.vn
Phần cứng Phần cứng là hệ thống các thiết bị có nhiệm vụ chạy các chương trình GIS nhằm thực hiện các yêu cầu về thu thập, phân tích, tính toán, xử lý, truy vấn dữ liệu. Hệ thống phần cứng gồm:  Thiết bị nhập: Chuột, bàn phím, máy quét ảnh, bàn số hoá, máy quét bản đồ.  Thiết bị xử lý: Máy tính - cụ thể là bộ xử lý trung tâm.  Thiết bị xuất: Máy in, máy chiếu, máy vẽ.  Thiết bị lưu trữ: Đĩa từ, đĩa quang, đĩa cứng. Phần mềm Tuỳ vào nhu cầu sử dụng và tuỳ vào từng sản phẩm mà các phần mềm có thể khác nhau. Tuy nhiên, các thành phần chính của các phần mềm GIS gồm có :  Nhập và tìm kiếm dữ liệu  Lưu trữ và quản lý cơ sở dữ liệu  Xuất dữ liệu  Chỉnh sửa dữ liệu  Tương tác với người sử dụng Dữ liệu Có thể coi dữ liệu là thành phần quan trọng nhất của mọi hệ thống cơ sở dữ liệu cũng như hệ thống GIS. Dữ liệu này có thể thu thập từ trắc địa, viễn thám hoặc mua lại từ các nhà cung cấp để xử lý, phân tích, và là cơ sở để phát triển và nghiên cứu GIS. Hệ GIS sẽ kết hợp dữ liệu không gian với các nguồn dữ liệu khác, thậm chí có thể sử dụng hệ quản trị cơ sở dữ liệu để tổ chức lưu giữ và quản lý dữ liệu. Số hóa bởi Trung tâm Học liệu – ĐHTN9 http://www.lrc.tnu.edu.vn
Con người Là đối tượng chính sử dụng GIS vào việc học tập, nghiên cứu, ra quyết định. Người sử dụng GIS có thể là những chuyên gia kỹ thuật, người thiết kế và duy trì hệ thống, hoặc những người dùng GIS để giải quyết các vấn đề trong công việc. Chính sách Là yếu tố quan trọng quyết định đến sự thành công của việc phát triển công nghệ GIS. 1.1.4 Dữ liệu trong hệ thống thông tin địa lý Cơ sở dữ liệu nền GIS là cơ sở dữ liệu mà những lĩnh vực trong công tác quản lý tài nguyên môi trường cần đến nó và sử dụng chúng. Cơ sở dữ liệu nền GIS là phần giao của từng cơ sở dữ liệu trong công tác quản lý tài nguyên môi trường. Cơ sở dữ liệu nền GIS bao gồm hai phần:  Cơ sở dữ liệu không gian (bản đồ nền).  Cơ sở dữ liệu thuộc tính chung. Bản đồ nền Bản đồ nền là bản đồ chỉ bao gồm yếu tố nền cơ sở địa lý. Nó là cơ sở để xác định vị trí địa lý của các đối tượng trong dữ liệu chuyên ngành. Nền cơ sở địa lý của bản đồ là tập hợp những yếu tố thuỷ văn, giao thông, dân cư, biên giới quốc gia, địa giới hành chính, địa danh và địa hình để làm cơ sở thể hiện cách nội dung khác trên bản đồ. Bản đồ nền được phân thành hai nhóm: bản đồ địa lý chung và địa lý chuyên đề. Bản đồ địa lý chung là bản đồ thể hiện mọi đối tượng, hiện tượng địa lý của bề mặt trái đất, bao gồm đầy đủ các đối tượng và hiện tượng kinh tế, văn Số hóa bởi Trung tâm Học liệu – ĐHTN10 http://www.lrc.tnu.edu.vn
hóa, xã hội như thủy văn, địa hình, thực vật, đất đai, dân cư, giao thông, công nghiệp, nông nghiệp, lâm nghiệp văn hóa, hành chính – chính trị. Bản đồ địa lý chuyên đề là loại bản đồ trên đó thể hiện rõ ràng, nổi bật và hoàn thiện một hoặc một số các yếu tố đã được thể hiện trên bản đồ địa lý chung. Cơ sở dữ liệu thuộc tính chung Là những số liệu phi không gian mô tả về các đặc tính, đặc điểm và các hiện tượng xảy ra tại các vị trí địa lý xác định, ví dụ: tên đường phố, số lượng dân số tại một khu vực, lượng mưa hàng năm tại một khu vực. Trên bản đồ, các sự vật trên thế giới thực được thể hiện qua tập các điểm, đường và miền, còn các ký hiệu, nhãn thể hiện các thông tin về thuộc tính của sự vật đó. 1.2 Phân cụm dữ liệu địa lý 1.2.1 Phân cụm dữ liệu Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định. Phân cụm dữ liệu là sự phân chia một cơ sở dữ liệu lớn thành các nhóm dữ liệu mà trong đó các đối tượng là tương tự nhau. “Phân cụm dữ liệu là quá trình tổ chức các đối tượng thành từng nhóm mà các đối tượng ở mỗi nhóm đều tương tự nhau theo một tính chất nào đó, những đối tượng không tương tự tính chất sẽ ở nhóm khác.” Dữ liệu địa lý là dữ liệu bao gồm dữ liệu không gian và dữ liệu thuộc tính được kết hợp với nhau một cách tương ứng. Dữ liệu địa lý có thể là các bản đồ số trên máy vi tính, các mô hình mô phỏng hình dáng bề mặt trái đất, các cơ sở dữ liệu ảnh bề mặt trái đất. Số hóa bởi Trung tâm Học liệu – ĐHTN11 http://www.lrc.tnu.edu.vn
Dữ liệu địa lý ngày một phát triển với lượng dữ liệu ngày càng lớn và phức tạp hơn, đòi hỏi các nhà nghiên cứu cần có những phương pháp, kỹ thuật để phân tích và khai phá dữ liệu hiệu quả hơn. Trong những năm gần đây, việc nghiên cứu và khai phá dữ liệu đã có xu hướng chuyển từ cơ sở dữ liệu quan hệ và cơ sở dữ liệu giao dịch sang cơ sở dữ liệu không gian. Khám phá tri thức từ dữ liệu không gian có thể được thực hiện dưới nhiều hình thức khác nhau như sử dụng các quy tắc đặc trưng và quyết định, trích rút và mô tả các cấu trúc hoặc cụm nổi bật, kết hợp không gian. Ứng dụng của phân cụm dữ liệu địa lý Phân cụm dữ liệu địa lý được ứng dụng trong nhiều lĩnh vực khác nhau:  Y tế: Xác định và khoanh vùng các ổ dịch giúp cho việc điều trị, quản lý, phòng chống lây lan sang các khu vực khác.  Nông – lâm nghiệp: Nhận dạng các vùng đất, điều kiện địa lý phù hợp với loại cây trồng tương ứng.  Sinh học: Phân loại động – thực vật thông qua các Gen tương đồng của chúng.  Kinh tế: Phân cụm các nhóm khách hàng quan trọng theo từng vùng miền.  Xã hội – phòng chống tội phạm: Khoanh vùng các khu vực là điểm nóng về tội phạm. 1.2.2 Một số kỹ thuật phân cụm dữ liệu - Thuật toán phân cụm có thể là kiểu phân cấp. một trong hai dạng – gộp dần, hoặc chia tách dần "từ trên xuống". Gộp dần: bắt đầu với mỗi cụm là một Số hóa bởi Trung tâm Học liệu – ĐHTN12 http://www.lrc.tnu.edu.vn
phần tử , hợp nhất liên tiếp thành các cụm ngày càng lớn hơn. Chia tách : bắt đầu với toàn bộ tập hợp, phân chia tiếp thành các cụm nhỏ hơn. - Kiểu phân hoạch thường xác định tất cả các cụm một lần, cùng lúc. Cũng có thể sử dụng như các thuật toán chia tách nói trên. - Dựa trên mật độ để khám phá các cụm hình dạng tùy ý. Một cụm là một vùng, trong đó mật độ của các đối tượng dữ liệu vượt quá một ngưỡng nào đó. DBSCAN và OPTICS là hai thuật toán điển hình loại này. 1.2.2.1 Thuật toán phân cụm theo cây phân cấp Tạo ra một hệ thống các cụm, có thể biểu diễn trong một cấu trúc cây. Gốc cây là một cụm duy nhất có chứa tất cả các phần tử, và lá tương ứng với từng phần tử. Các thuật toán : gộp dần hoặc chia tách dần. Có thể sử dụng bất kỳ độ đo hợp lệ nào của sự tương tự giữa các cặp quan sát (phần tử). Chọn cụm để sáp nhập hoặc chia tách theo một tiêu chí nối liên kết, là một hàm của khoảng cách từng đôi giữa các quan sát. Cắt cây ở độ cao nhất định sẽ cho một phân cụm đạt một độ chính xác đã chọn. Thông thường, khoảng cách giữa hai cụm A,B là một trong những độ đo sau đây: • Khoảng cách tối đa giữa các cặp phần tử của mỗi cụm (còn gọi là phân cụm liên kết đầy đủ): max{ d(x,y): , } • Khoảng cách tối thiểu giữa các cặp phần tử của mỗi cụm (còn gọi là phân cụm liên kết đơn lẻ - single link): min{ d(x,y): , } Số hóa bởi Trung tâm Học liệu – ĐHTN13 http://www.lrc.tnu.edu.vn