1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN THỊ HƢƠNG NGHIÊN CỨU GIẢI PHÁP NÂNG CAO TỐC ĐỘ HIỂN THỊ DỮ LIỆU TRÊN BẢN ĐỒ TRỰC TUYẾN LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 2015 z 2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN THỊ HƢƠNG NGHIÊN CỨU GIẢI PHÁP NÂNG CAO TỐC ĐỘ HIỂN THỊ DỮ LIỆU TRÊN BẢN ĐỒ TRỰC TUYẾN Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS NGUYỄN HẢI CHÂU Hà Nội – 2015 z 3 LỜI CAM ĐOAN Tôi xin cam đoan nội dung và những kết quả của luận văn tốt nghiệp này là do tôi tự nghiên cứu dưới sự hướng dẫn của PGS.TS Nguyễn Hải Châu. Trong toàn bộ nội dung của luận văn, những nội dung được trình bày là của cá nhân tôi hoặc được tổng hợp từ nhiều nguồn tài liệu khác. Tất cả các tài liệu tham khảo đều được trích dẫn rõ ràng ở phần cuối của luận văn. Tôi xin cam đoan những lời trên là sự thật.
Nếu sai tôi xin hoàn toàn chịu trách nhiệm. Hà Nội, ngày 20 tháng 11 năm 2015 Học viên Trần Thị Hương z 4 LỜI CẢM ƠN Tôi xin gửi lời cảm ơn sâu sắc tới PGS.TS Nguyễn Hải Châu, người đã tận tình chỉ bảo tôi những kiến thức chuyên môn, phương pháp nghiên cứu khoa học đồng thời cũng là tấm gương trong mọi mặt của cuộc sống để tôi học tập và noi theo. Tôi xin chân thành cảm ơn các thầy, cô giáo trường Đại học Công nghệ đã cung cấp cho tôi những kiến thức bổ ích trong thời gian tôi học tập tại trường. Cuối cùng tôi xin gửi lời cảm ơn tới gia đình tôi đã luôn ủng hộ tôi trên con đường học tập và nghiên cứu với nhiều khó khăn, vất vả.
Mặc dù tôi đã cố gắng hết sức trong quá trình làm luận văn nhưng không thể tránh khỏi thiếu sót, rất mong nhận được những góp ý của thầy cô và các bạn. Hà Nội, ngày 20 tháng 11 năm 2015 Học viên Trần Thị Hương z 5 MỤC LỤC LỜI CAM ĐOAN .5 DANH MỤC CHỮ VIẾT TẮT.7 DANH MỤC HÌNH .8 DANH MỤC BẢNG BIỂU. Khái quát hóa bản đồ. Lịch sử phát triển và các khái niệm đang tồn tại.
Định nghĩa, ý nghiã, mục đích và các nhân tố. Khái quát hóa bản đồ số và các quy tắc khái quát hóa bản đồ. Lược giản hóa bản đồ từ tập dữ liệu điểm cụm. Phân tích cụm là gì?.
Các kĩ thuật phân cụm. Giới thiệu hệ quản trị cơ sở dữ liệu PostgreSQL. Các đặc điểm của PostgreSQL. Ưu nhược điểm của PostgreSQL.
GIẢI PHÁP NÂNG CAO TỐC ĐỘ HIỂN THỊ DỮ LIỆU ĐỊA LÝ TRÊN BẢN ĐỒ TRỰC TUYẾN. Giới thiệu các kĩ thuật phân cụm. Các thuật toán phân cụm cơ bản. Các độ đo sử dụng trong phân cụm.
Gộp nhóm với thuật toán phân vùng K-means. Giới thiệu về thuật toán phân vùng K-means. Cấu trúc của thuật toán phân vùng K-means. Gộp nhóm với thuật toán phân cấp Agglomerative Hirearchical (AH).
Giới thiệu về thuật toán phân cấp. Cấu trúc của thuật toán phân cấp. So sánh thuật toán K-means và thuật toán AH. Thuật toán K-means.
Thuật toán AH. Xây dựng bộ CSDL thực nghiệm. Import dữ liệu vào hệ quản trị CSDL PostgreSQL. Lập trình xây dựng trang Web thử nghiệm.
Xây dựng trang Web và hiển thị dữ liệu điểm ATM. Ứng dụng thuật toán phân cấp Agglomerative Hirearchical lập trình tăng tốc độ hiển thị dữ liệu điểm ATM .59 TÀI LIỆU THAM KHẢO.60 z 7 DANH MỤC CHỮ VIẾT TẮT Ký hiệu Diễn giải Tiếng Việt AH Agglomerative Hirearchical Phân cấp gộp API Application Programming Interface Giao diện lập trình ứng dụng ATM Automatic Teller Machine Máy rút tiền tự động DBMS Database Management System Hệ quản trị cơ sở dữ liệu GIS Geographical Information System Hệ thống thông tin địa lý GPS Global Positioning System Hệ thống định vị toàn cầu z 8 DANH MỤC HÌNH Hình 1. Sự khác biệt giữa khái quát hóa bản đồ và tỷ lệ hóa bản đồ…………. Khái quát hóa bản đồ ……………….
Phương pháp hình sao và phương pháp bậc thang trong kỹ thuật khái quát hóa …………………………………………………………………………………. Lược giản hóa đối với một tập điểm …………………………………. Lựa chọn các điểm gần nhất để nhóm. Loại bỏ các điểm gần tâm cụm…………………………………………….
Sự khác biệt giữa các dữ liệu điểm gốc và các dữ liệu điểm sau khi khái quát hóa lúc bản đồ được phóng to………………………………………………………. Việc thể hiện tập dữ liệu điểm gốc và tập dữ liệu điểm sau khi khái quát hóa về tỷ lệ 1:10. Các cách khác nhau để phân cụm cùng một tập điểm ………………. Thuật toán phân cụm phân cấp 1……………………………………….
Thuật toán phân cụm phân cấp 2 …………………………………………34 Hình 2.2: Thuật toán phân vùng………………………………………………………34 Hình 2. Quy trình hoạt động của thuật toán k-means…………………. Gán k tâm cụm một cách ngẫu nhiên………………………………………36 Hình 2. Gán mỗi điểm vào một cụm gần nhất …………………………….
Tâm của mỗi cụm dịch chuyển sau khi được tính toán lại …………. Gán lại các điểm vào các cụm gần nhất và lặp lại…………………………. Thuật toán phân cụm phân cấp……………………………………………. Quá trình chạy thuật toán phân cấp phân cụm…………………….
Quy trình thuật toán phân cấp phân cụm………………………………. Một cây phân cấp của thuật toán phân cụm AH…………………. Biên tập dữ liệu trên phần mềm ArcGIS…………………………. Cấu trúc bảng thuộc tính của dữ liệu………………………………………48 Hình 3.
Bảng thuộc tính của dữ liệu ATM khu vực Hà Nội……………. Hộp thoại tạo Databases…………………………………. Cơ sở dữ liệu ATM Thành phố Hà Nội ……………………………………50 Hình 3. Hộp thoại đưa shapefile lên Databases…………………………….
Hộp thoại Import Options………………………………………. Cơ sở dữ liệu trong Databases db_test – atm………………………………52 Hình 3. Trang Web đơn giản với bản đồ nền GoogleMap……………. Mã tạo trang Web với bản đồ nền GoogleMap…….
Hiển thị dữ liệu điểm ATM trên Web……………………………. Minh họa quá trình gộp nhóm bằng thuật toán AH………………….55 z 10 DANH MỤC BẢNG BIỂU Bảng 1. Minh họa các quy tắc khái quát hóa……………………………………17 Bảng 1. So sánh hiệu suất lưu trữ số liệu …………………………….
So sánh một số tính năng cơ bản………………………………………30 Bảng 1. So sánh phương thức quản lý và phân vùng. So sánh một số tính năng cơ bản………………………………………31 Bảng 1. So sánh phương thức quản lý và phân vùng………………………….
Các hạng mục xây dựng trang Web thử nghiệm………………………. Thống kê hiệu suất phân cụm với thuật toán AH……………………. Tính cấp thiết của đề tài Công nghệ thông tin là một ngành khoa học đang phát triển rất mạnh và được áp dụng trong rất nhiều ngành khoa học khác, giúp cho con người xử lý công việc một cách nhanh hơn, chính xác hơn và hiệu quả hơn. Ngày nay, xu thế ứng dụng bản đồ số qua bản đồ số giúp nâng cao hiệu quả làm việc mà lại tiết kiệm rất nhiều trong công tác lưu trữ và chia sẻ.
Tuy nhiên, việc thể hiện các đối tượng không gian trên bản đồ với số lượng lớn là vấn đề khó, vẫn đang dần được khắc phục. Phương pháp chủ yếu được sử dụng hiện nay là khái quát hóa bản đồ thông qua các quy tắc nhất định. Luận văn này tập trung chủ yếu vào khái quát hóa dữ liệu dạng điểm nhằm nâng cao tốc độ hiển thị dữ liệu dạng điểm trên Web. Phân cụm dữ liệu là quá trình nhóm các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng cùng cụm là tương tự nhau còn các đối tượng khác cụm thì không tương tự nhau.
Phân cụm chính là nhiệm vụ chính trong khai phá dữ liệu và là một kỹ thuật phổ biến để phân tích số liệu thông tin, các hệ trợ giúp quyết định, các thuật toán nhận dạng mẫu và phân lớp mẫu,…và đặc biệt là khai phá dữ liệu. Ngày nay có rất nhiều các kỹ thuật phân cụm được sử dụng, nhưng không phải kỹ thuật phân cụm nào cũng có thể giải quyết tốt tất cả các vấn đề của quá trình phân cụm. Phân cụm là kỹ thuật được sử dụng rất hiệu quả và phổ biến trong khai phá dữ liệu và thông tin (Seo & Sheiderman, 2002), đồng thời nó được sử dụng để đơn giản hóa các cụm điểm (Lu và nnk, 2001). Cùng với sự phát triển của GIS, kỹ thuật này thể hiện nhiều điểm mạnh vượt trội, đáp ứng được các yêu cầu của khái quát hóa bản đồ số và đảm bảo được các đặc tính phân bố, cấu trúc của cụm dữ liệu.
Tuy nhiên, phân cụm vẫn còn là khái niệm khá mới mẻ đối với các nhà bản đồ học và nhà nghiên cứu ở Việt Nam. Vì những lý do trên, học viên quyết định chọn đề tài “Nghiên cứu giải pháp nâng cao tốc độ hiển thị dữ liệu trên bản đồ trực tuyến”. Mục tiêu và nhiệm vụ của đề tài + Đúc kết được những vấn đề lý thuyết căn bản của bản đồ trực tuyến hiện đại, những vấn đề về công nghệ liên quan và xây dựng quy trình công nghệ thành lập và phát hành bản đồ trên mạng. + Tìm hiểu về các thuật toán gộp điểm giúp nâng cao tốc độ hiển thị dữ liệu dạng điểm trên Web.
+ Sản phẩm thử nghiệm phải đạt chất lượng của bản đồ là nâng cao tốc độ hiển thị dữ liệu địa lý dạng điểm. Khái quát hóa bản đồ 1. Lịch sử phát triển và các khái niệm đang tồn tại Khái quát hóa bản đồ được các nhà địa lý và các nhà bản đồ học thảo luận và phân tích từ đầu thế kỷ 20. Các nhà bản đồ học đã gặp rất nhiều khó khăn trong nhiều thập kỷ trong việc khái quát hóa bản đồ và việc thể hiện bề mặt trái đất trên mặt phẳng bản đồ.Trải qua 1 thế kỷ, các định nghĩa, quan điểm mà các nhà địa lý và các nhà bản đồ học đưa ra rất đa dạng.
- Từ việc xem khái quát hóa bản đồ như là một quá trình chủ quan đến việc xem khái quát hóa bản đồ như là một phương pháp vẽ bản đồ khoa học khách quan: Năm 1921 Max Eckert lần đầu tiên đưa ra khái niệm khái quát hóa bản đồ, ông cho rằng thực chất khái quát hóa bản đồ nằm ở việc đối với các đối tượng vẽ bản đồ tiến hành chọn lọc và khái quát, nhân tố chủ yếu để dẫn dắt là công dụng của bản đồ, điều này đến nay vẫn hoàn toàn chính xác. - Erwin Raisz (Tổng quan về bản đồ học, 1948) đã trình bày một quan điểm khá đơn giản về khái quát hóa. Theo Raisz, không có quy tắc rõ ràng nào cho khái quát hóa bản đồ nhưng nó bao gồm các bước để kết hợp, loại bỏ một số yếu tố và lược giản hóa dữ liệu. - Từ thập kỉ 60 đến thập kỉ 80 của thế kỷ 20, nhiều học giả đã nghiên cứu về mô hình khái quát hóa bản đồ và mô hình bản đồ.